Continuous Batching: From Static to Iteration-Level Scheduling

The problem with static batching

LLM generation is autoregressive: each iteration (one forward pass) produces one token for every request in the batch. Output lengths vary a lot within a batch.

Static batching ties the batch together. A request that finishes early cannot leave, so its slot idles (the hatched cells below, called bubbles) until the slowest request in the batch completes. Requests arriving mid-batch queue even when slots are visibly empty.

There are two kinds of bubbles here: a finished request whose slot stays locked by the batch (hover to see which request), and slots that were never filled when the batch formed. These map to static batching’s two pain points:

1. When one request runs long, every other request has to wait even after finishing;
2. A batch may form under-filled, and no new request can join mid-batch until the whole batch completes.

Both drag down GPU utilization.

Iteration-level scheduling

ORCA moved the scheduling granularity from a whole batch down to a single iteration, and SGLang and other mainstream engines work this way today: when a request completes, its slot frees immediately, and the request at the head of the queue takes it on the next step. Same request stream:

As long as the queue is non-empty, no slot sits idle (work-conserving).

Comparison

Same requests, same timeline. Switch scenarios to see where the gap is widest:

• Equal-length, unsteady arrivals: a real gap. Even with every request the same length, staggered arrivals mean static batching keeps forming under-filled batches, wasting GPU capacity.
• Long-tail outputs: the widest gap. Every static batch is dragged by its longest request (head-of-line blocking), and real LLM traffic is long-tailed.
• Equal-length burst: with identical lengths and simultaneous arrival the two tie exactly, the one case where static loses nothing. It shows that static’s waste comes entirely from length variance and arrival spread. Production traffic has exactly both, so in real deployments continuous batching’s gains are even better than the idealized lab result.

Notes

1. Why can requests swap mid-run? During decode each request only depends on its own KV cache; requests are independent along the batch dimension.
2. Memory becomes the new bottleneck: once admission is no longer gated by batch boundaries, concurrency is limited by KV cache memory. That is the problem PagedAttention addresses.
3. Prefill preempts decode: a newly admitted request runs prefill first (the light cells; simplified to a single iteration here, far heavier than one iteration in real systems), which slows down everyone else’s token cadence. Chunked prefill and prefill/decode disaggregation both target this.

Diagram ↔ real system