LLM Batch Inference Bin Packing: Fill GPUs Without Trapping Short Requests

Your offline summarization job has 20,000 documents. The first batch combines one 200-token prompt with seven 12,000-token prompts, pads every sequence to the longest shape, and turns an apparently full GPU into an expensive waiting room.

LLM batch inference bin packing is the work of grouping requests so compute, key-value cache memory, and service deadlines are used efficiently. The goal is not the largest possible batch. It is the most useful work completed per unit of constrained capacity.

Define the Resources You Are Packing

A request has at least two sizes: prompt tokens that must be prefetched and output tokens that will be decoded. Prompt length may be known at admission time; output length is usually an estimate or hard maximum.

Memory pressure depends heavily on model weights and the key-value cache. Compute pressure differs between prefill and decode. Prefill processes many prompt tokens in parallel and is often compute intensive. Decode advances active sequences token by token and can become memory-bandwidth bound.

Represent each job with normalized input tokens, expected output tokens, maximum output tokens, priority, deadline, model and adapter identity, and any sampling constraints that affect compatibility. Record observed output distributions by workload instead of assigning one global guess.

Do not mix tenant isolation with packing convenience. If requests require separate adapters, encryption domains, or data residency, those boundaries are hard constraints before utilization is optimized.

Bucket by Shape Before You Optimize the Bin

Start with coarse prompt-length buckets such as powers of two. Batching requests of similar length reduces padding in static engines and makes prefill duration more predictable. Separate very long contexts so one outlier does not delay a group of short jobs.

Within each bucket, use a simple policy first: earliest deadline, then first fit by estimated token budget. Cap total prompt tokens, active sequences, and projected cache blocks independently. A sequence-count limit alone is unsafe because four huge contexts can require more memory than dozens of short ones.

If the engine supports continuous batching, completed sequences can leave and waiting sequences can join between decode steps. This reduces the cost of imperfect initial bins, but admission still matters. Filling every cache block with low-priority long jobs can prevent an urgent short request from entering.

Reserve headroom for estimation error and runtime overhead. Treat an out-of-memory restart as a failed capacity policy, not an acceptable way to discover the true limit.

Prevent Head-of-Line Blocking and Starvation

Separate interactive and offline service classes when their latency goals differ. Interactive traffic may use small batches with strict queue limits; offline traffic can absorb larger windows and opportunistically consume spare capacity.

Aging prevents starvation: gradually increase a waiting job’s effective priority. Also set a maximum queue time after which the scheduler must run the job, move it to a dedicated long-context pool, or fail explicitly. Silent indefinite waiting makes utilization graphs look healthy while work disappears operationally.

Chunked prefill can interleave portions of a long prompt with decode work, depending on the serving engine. Test it with real context shapes because aggressive chunking may improve time-to-first-token for some requests while reducing overall throughput.

Cancellation must immediately release reservations. A disconnected client whose sequence remains active wastes both cache and decode slots.

Measure Completed Work, Not Batch Size

Track tokens per second separately for prefill and decode, cache-block utilization, padding waste, queue time by service class, time to first token, inter-token latency, deadline misses, cancellations, and out-of-memory prevention events.

Replay production-like traces with the same burstiness and length distribution. Uniform synthetic requests hide the exact shape mismatch the scheduler must solve. Include adapter switches, long-context outliers, early end-of-sequence behavior, and clients that cancel midway.

Compare policies on cost per completed request and deadline attainment, not peak tokens per second alone. A scheduler that wins a throughput benchmark by delaying every short request may be wrong for the product.

Good bin packing is deliberately boring. It uses explicit resource dimensions, predictable buckets, bounded waiting, and measured headroom. The GPU should stay busy because the scheduler understands the workload—not because every queue was poured into the same batch.