Chapter 7 — Advanced Batching Strategies

Seventh post of the chapter-by-chapter walkthrough of LLM Primer VI: Scaling AI Systems. The chapter that shows why batching is not an optimization but the load-bearing move that makes bandwidth-bound decoding tractable — and why the batch is a verb, not a noun.

Why this chapter exists

A single decode step reads tens of gigabytes of weights from HBM to produce one token. If the GPU is streaming those weights anyway, it can produce a token for many requests in the same step at almost zero marginal cost. Batching is therefore not an optimization in the ordinary sense — it is the only way to make decoding economically tractable on memory-bandwidth-bound hardware. But the obvious way to batch collapses on contact with the real world, because requests are different lengths and finish at different times. Chapter 7 walks from the naive scheme that almost works to the iteration-level scheduler that production engines actually run, and names the debt that scheduler creates for Chapter 8 to pay.

7.1 Static batching is defeated by the fastest-finisher problem

Static batching is what everyone writes first: collect requests until batch size B or a timeout, run prefill on the whole batch at length S_max, run a decode loop until every sequence in the batch has emitted EOS. The two costs are catastrophic in combination. Padding — the 50-token prompt in the same batch as the 4,000-token prompt pays for 80× the prefill work it needs. Fastest-finisher — the decode loop runs until every sequence finishes, so a batch with one 20-token request and one 2,000-token request spends 99 percent of its time with 31 slots producing tokens that will be thrown away. Mean throughput looks acceptable and tail latency is dominated by whichever long request the batch happened to contain. Dynamic batching (variable timeout, allow late arrivals into the pending batch) softens the wait but does not change the fundamental scheme; it inherits the same fastest-finisher problem once decode begins.

7.2 Continuous batching schedules per iteration, not per request

Continuous batching — Orca's iteration-level scheduling, NVIDIA's in-flight batching, "the central trick" of vLLM and TGI — is the change of variable. Instead of committing a batch for the duration of generation, the scheduler revisits the batch composition at every decode step. After each step: finished sequences leave their slots and free their KV; new sequences from the queue enter the freed slots; the joint decode step runs on the new active set. Two properties of LLM decoding make this possible. Every decode step is structurally the same operation — the kernel does not care which sequence is in slot 7 versus slot 11. And each sequence carries its own KV cache independently, so its memory simply becomes available when it leaves. The unit of fairness becomes the iteration, not the request: a 20-token request finishes after roughly 20 iterations regardless of who else is in the batch, and a 2,000-token request occupies one slot for as long as it needs without holding others hostage. On real long-tail traffic — mixtures of short chat turns and long RAG completions — GPU utilization on a 70B model climbs from the 10–20 percent range typical of static batching to 60–80 percent, and p99 latency tightens dramatically.

7.3 Chunked prefill unifies prefill with decode on the same chip

Continuous batching still leaves a tension. New arrivals need prefill, which is compute-bound and prefers long sequences per pass. In-flight sequences need decode, which is memory-bandwidth-bound and prefers wide batches. Running a full prefill on a fresh 4,000-token prompt in the same forward pass as the decode step for thirty ongoing sequences either delays the ongoing decodes (bad TTFT for existing users) or delays the new arrival's prefill (bad TTFT for the new user). Chunked prefill splits the prefill into pieces — say 512 tokens at a time — and interleaves those chunks with the decode steps of active sequences. The single forward pass now carries some new-prompt prefill work and some ongoing-decode work simultaneously, and the two phases share the same weight streams. Prefill's compute-bound character absorbs the arithmetic; decode's bandwidth demand is amortized across more useful work per byte. The two phases stop being antagonistic on a single chip. The remaining case — enough traffic that they still fight — is the setup for disaggregated serving in Chapter 12.

What Chapter 7 sets up

Continuous batching does its job, and in doing so exposes the KV cache as the binding constraint on concurrency. Each active sequence carries its own KV, sized in proportion to its current length; sequences enter and leave every step; the engine cannot know in advance how long any of them will be. A naive one-slab-per-slot layout gives back most of the batching win. Chapter 8 brings the operating-system solution across: split the cache into small physical blocks, decouple them from logical token positions with a page table, and let an eviction policy reclaim or share blocks across sequences. PagedAttention is the move that makes continuous batching's KV problem tractable.

Next — Chapter 8: Next-Generation KV Cache Management. PagedAttention, H2O eviction, InfiniGen, and the prefix-caching economy.