Skip to content

CONCEPT Cited by 5 sources

Bin-packing

Bin-packing is the combinatorial-optimisation problem of placing a set of items with known sizes into the smallest number of fixed-capacity bins (or equivalently: maximising the efficiency with which a fixed set of bins is filled). Classical bin-packing is NP-hard in its general form. Cluster-scheduling variants are multi-dimensional (CPU, RAM, disk, network, GPU, TPU, affinity, anti-affinity, QoS), which only adds difficulty.

Bin-packing is the core decision primitive of almost every cluster scheduler the wiki touches:

  • Borg — Google's cluster manager; the 2025-07-29 RLM post names "a specialized bin-packing algorithm used to efficiently allocate tasks to resources" as the engine whose output the RLM predicts (Source: sources/2025-07-29-google-simulating-large-systems-with-regression-language-models).
  • Kubernetes scheduler — its scoring / filtering loop is a multi-dimensional bin-packer over pod resource requests.
  • Karpenter — AWS's K8s-native autoscaler picks instance types by solving a bin-packing problem over pending pods vs. instance SKUs.
  • EKS Auto Mode — encapsulates a Karpenter-style bin-packer behind a managed-data-plane API.
  • Apache Mesos, HashiCorp Nomad, YARN, Slurm — all variants of the same primitive.

A special case of the general assignment problem

Bin-packing is the capacity-only special case of the more general assignment problem: assign objects to bins to optimize objectives under constraints. Bin-packing fixes the objective (minimize bins used / maximize fill) and the constraint (per-bin capacity); the general assignment framing adds arbitrary objectives (fault-domain spread, latency, cross-dimension balance) and arbitrary constraints. Meta's Rebalancer treats bin-packing, service placement, task placement, and traffic routing as one primitive — packing efficiency is one of the objectives its service-placement spec optimizes (Source: sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library).

Why it's expensive at scale

The scheduler doesn't just solve one bin-packing instance — it re-solves as jobs arrive, fail, scale, or get preempted, and it considers many candidate placements per decision. At Google-fleet scale, running the full combinatorial solver on every candidate is what motivates replacing it with a cheap ML approximator: a predictor that estimates the outcome of the bin-packer is orders of magnitude cheaper per query than actually running it.

As a prediction target (not just a solver)

The 2025-07-29 RLM work treats bin-packing differently from most scheduler literature: the bin-packer is not the thing being improved — it's the thing being predicted. The RLM's target is the bin-packer's numeric output (MIPS per GCU) on a given cluster state. This is a slightly unusual framing that shows up when:

  • The authoritative solver is too slow to run in the inner loop.
  • You need a fast answer that tracks what the slow solver would have said.
  • Uncertainty-flagged cases can fall back to the slow solver.

In that framing, bin-packing is the performance-prediction target function, not a design concern of the predictor itself.

Standard approximation strategies (the solver side)

Outside the RLM framing, bin-packing at cluster scale uses well-known heuristic approximators:

  • First Fit / Best Fit / Worst Fit / Next Fit Decreasing — classical O(n log n) heuristics with approximation-ratio guarantees.
  • Linear relaxation + rounding — solve the LP relaxation, round to integers.
  • Score-based placement — score each (pod, node) pair by a weighted sum of fit metrics; pick the highest-scoring candidate. Kubernetes scheduler canonical.
  • Bin-packing-aware autoscaling — Karpenter's "pick an instance type that maximally absorbs the pending pods."

The 2025-07-29 post doesn't describe Borg's specific bin-packing algorithm — only that it's "specialised" and used inside the digital-twin backtester to generate the MIPS-per-GCU training signal.

Online bin-packing with unknown disappearance times

Cloud VM allocation is a special instance: online bin-packing where the pieces appear and disappear at times unknown at placement. The 2025-10-17 Google LAVA post opens with the framing directly — "a puzzle game similar to Tetris with pieces rapidly falling onto a stack. Some fit perfectly. Others don't… the 'pieces' (or VMs) appear and disappear, some with a lifespan of only minutes, and others, days" (Source: sources/2025-10-17-google-solving-virtual-machine-puzzles-lava).

This variant has two named operational failure modes distinct from static bin-packing:

  • Resource stranding — remaining per-host resources too small or unbalanced to host any candidate new piece; the host is not empty but the leftover is unusable.
  • Empty-host loss — the cluster's reserve of fully-empty hosts (needed for maintenance + large- VM provisioning) erodes when placement ignores lifetime.

Both are second-order effects of placement decisions made without lifetime information. The LAVA family's answer is ML-based lifetime prediction with continuous reprediction + learned lifetime distributions driving LARS-style rebalancing (see systems/lava-vm-scheduler).

Bin-packing over time vs over space (2026-02-11)

Google Research's 2026-02-11 scheduling-under-time-varying- capacity post introduces the over-time sibling of the over-space online bin-packing captured in the 2025-10-17 LAVA post. Where LAVA allocates VMs into host capacity (CPU / RAM / disk are the dimensions), the 2026-02-11 paper allocates batch jobs into a wall-clock capacity profile (time is the dimension) (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

Both share the "commit under uncertainty about future arrivals" hazard and both are online. The primitives differ:

  • LAVA / over-space: learned lifetime predictions + continuous reprediction + [[patterns/lifetime-aware- rescheduling|lifetime-aware rescheduling]] targeting resource stranding and empty-host loss.
  • 2026-02-11 / over-time: competitive-ratio analysis across preemption regimes + tentative-schedule revision targeting worst-case throughput under adversarial job-arrival sequences. The earliest-finish-job greedy achieves the ½-competitive offline-matching bound under interrupt-and- restart preemption; [[concepts/common-deadline- scheduling|common deadlines]] restore constant-competitive bounds under the stricter interrupt-without-restart model.

The two papers together pin "scheduling-as-online-bin- packing" as a two-dimensional shape — over-space allocation with lifetime uncertainty (Tetris where pieces disappear) and over-time allocation with capacity variation (schedule jobs into a varying time budget). Both appear on Google's production Borg substrate; the over-time paper is a theoretical contribution while the over-space paper has a deployment-shaped narrative.

Seen in

  • sources/2025-07-29-google-simulating-large-systems-with-regression-language-models — Borg's bin-packing algorithm is the RLM's prediction target.
  • sources/2026-01-12-aws-salesforce-karpenter-migration-1000-eks-clusters — Salesforce's 1,000-cluster migration names bin-packing as the Karpenter primitive that (a) reduces stranded capacity vs Cluster Autoscaler's conservative heuristics, (b) delivers 5% FY2026 cost savings
  • projected 5-10% FY2027, (c) enables heterogeneous instance types (GPU / ARM / x86) in a single NodePool because the scheduler can pick whichever shape best absorbs pending pods. Also surfaces the singleton- workload failure mode: consolidation's re-packing can terminate 1-replica pods without warning, requiring guaranteed- pod-lifetime and workload-aware disruption policies to safeguard them. Canonical wiki solver-side at production scale instance.
  • sources/2025-10-17-google-solving-virtual-machine-puzzles-lava — Google Research's LAVA / NILAS / LARS algorithmic family for online VM bin-packing with lifetime uncertainty. Canonical wiki instance of bin-packing as a policy-intervention target (augment the placement policy with learned lifetime predictions + continuous reprediction) rather than a solver-output or solver-call target. Names the two operational failure modes resource stranding and empty-host loss that differentiate this bin-packing variant from the static case.
  • sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity — Google Research's over-time sibling to the LAVA over-space work: online scheduling under time-varying capacity as bin-packing-over-wall-clock. Canonical wiki instance of the over-time framing of the primitive — [[concepts/competitive- ratio|competitive-ratio]] analysis across three preemption regimes, with interrupt-and- restart recovering the offline ½-competitive bound via earliest-finish-job greedy, and common deadlines enabling constant-competitive bounds under the stricter interrupt-without-restart model.

  • sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library — Meta's Rebalancer treats bin-packing as one instance of the general assignment problem: its service-placement spec optimizes packing efficiency as one objective alongside fault-domain spread. Canonical wiki instance of bin-packing generalized into a reusable assignment-solver framework with declarative specs + dual (MIP + local-search) backends.

  • sources/2026-09-30-databricks-a-practical-guide-to-cost-optimization-with-lakebase-postgre — Bin-packing applied to data-sync pipelines, not just VMs/pods. Databricks' Lakebase cost guide recommends "binpack, or group, multiple tables into a single sync pipeline" so that several Delta tables syncing into Lakebase share the same underlying compute. Especially valuable for Continuous (always-running) syncs, where per-table pipelines would each pay for separate continuously-running compute. A nice reminder that the bin-packing primitive — pack items into fewer fixed-capacity bins — generalizes from scheduler placement to amortizing a shared always-on compute unit across multiple logical workloads (here, SDP pipeline compute across tables).

Last updated · 766 distilled / 2,225 read