The problem: static batching and its dead time
Start with the naive approach. A server collects B requests, stacks their prompts into one batch of shape [B, ...], and runs generation until all of them stop. This is static (or request-level) batching, and its flaw is structural: autoregressive outputs have very different lengths. One request emits 15 tokens, another emits 600. Because the batch is fixed for its whole lifetime, the short sequence finishes at step 15 and then its slot sits there, doing nothing useful, for 585 more steps while the batch waits on the longest member.
The GPU still runs a forward pass over that slot every step, but the tokens it produces are discarded padding — you pay full matrix-multiply cost for a slot that already returned its answer. The batch runs at the speed of its slowest member, and every request shorter than the maximum donates idle capacity. With realistic length variance, that donation is enormous.
Quantifying the waste: the utilization ratio
Make it precise. Let a static batch hold sequences with output lengths L_1, …, L_B. The batch occupies all B slots for max_i L_i iterations, so it consumes B · max_i L_i slot-iterations of compute. But the number of useful tokens produced is only Σ_i L_i. The slot-utilization is therefore:
U_static = (Σ_i L_i) / (B · max_i L_i)
= mean(L) / max(L)The whole story is in that second form: static-batch efficiency is the ratio of mean output length to maximum output length. If every request produced the same number of tokens, mean = max and U = 1. But real traffic has heavy-tailed lengths, so max is dragged far above mean by a few long generations and U collapses toward 0.3–0.5 — half your compute, or more, evaporates into padding.
The fix: schedule per iteration, not per request
Continuous batching, introduced by Orca (Yu et al., OSDI 2022), attacks the problem at its root: the batch is no longer fixed for the life of a request. The scheduler treats a single generation step — one forward pass that advances every active sequence by one token — as the unit of scheduling. Between one step and the next, it is free to change who is in the batch.
Concretely, after each iteration the runtime checks which sequences emitted an end-of-sequence token or hit their length cap. Those are evicted — output returned, slot released — and any queued requests are then admitted into the freed slots, so the next forward pass runs over a newly composed batch. A sequence no longer waits for the batch it arrived with to drain; it joins at the next step and leaves the moment it is done. The batch is a living set, not a fixed cohort.
The admit/evict loop
The scheduler’s core is a loop that runs once per decode step. In pseudocode:
while running or queue:
# 1. admit: fill free slots from the queue,
# subject to KV-cache memory budget
while queue and can_allocate_kv(queue.peek()):
batch.add(queue.pop()) # runs prefill
# 2. step: one forward pass, +1 token per active seq
logits = model.forward(batch)
batch.append_sampled_tokens(logits)
# 3. evict: retire finished sequences, free their KV
for seq in batch.finished():
emit(seq); batch.remove(seq); free_kv(seq)Admission and eviction are cheap bookkeeping around the one expensive operation, the forward pass. There is no idle draining phase: the instant a slot opens, a queued request’s prefill fills it, so the batch stays as close to full as the queue and memory allow. This is why the technique is also called in-flight batching — new work is injected while other work is still in flight.
Throughput math: continuous versus static
Model the steady state. Suppose each iteration takes a roughly constant t_iter seconds (decode is memory-bandwidth bound, so per-step time is nearly flat across batch sizes up to the bandwidth roofline) and the server holds up to B active slots. Static batching produces tokens at:
throughput_static = (Σ_i L_i) / (max_i L_i · t_iter)
≈ (B · mean(L)) / (max(L) · t_iter)Continuous batching, when the request queue is non-empty, keeps all B slots occupied with useful work almost every step, so it approaches throughput_cont ≈ B / t_iter — one useful token per slot per iteration. The speedup is therefore roughly max(L) / mean(L), the inverse of the static utilization. For heavy-tailed length distributions that is commonly a 2× to 4× gain, and Orca reported far larger margins against baselines that also padded. The wider your length distribution, the bigger the win: continuous batching converts length variance from a penalty into a non-issue.
A worked example
Take a batch of four requests with output lengths L = [20, 100, 400, 500] and one queued request of length 300 behind them. Under static batching the batch runs for max(L) = 500 iterations. Useful tokens = 20 + 100 + 400 + 500 = 1020; slot-iterations spent = 4 × 500 = 2000. So U_static = 1020 / 2000 = 51%, and the queued request cannot even start until step 500.
Under continuous batching, the length-20 sequence finishes at step 20 and the waiting length-300 request is admitted immediately into that slot, running steps 21–320. Instead of a slot going dark for hundreds of steps, it is recycled the moment it empties. Over the same wall-clock window the server retires five requests in roughly the time static batching needed for four, and slot utilization climbs from 51% toward the high 90s — a throughput gain that came from scheduling alone, not a faster kernel.
The ragged-batch problem
Iteration-level batching creates a subtlety static batching hides. At any given step the active sequences are at different positions: one is 12 tokens deep, another 380, a freshly admitted one is doing its prompt prefill. Their key/value histories therefore have different lengths, so the batch is ragged — a set of variable-length rows, not a clean rectangle.
The naive way to run attention over such a batch is to pad every sequence to the longest one, but that reintroduces exactly the wasted compute continuous batching set out to kill. Real implementations avoid the pad entirely with variable-length attention kernels — unpadded ‘varlen’ or nested layouts that store sequences packed end-to-end with a cumulative-length index, so each query attends only over its own true history. Continuous batching without a ragged-aware kernel gives back much of what it earns; the two are designed to work together.
The real ceiling: KV-cache memory, not compute
Notice the admission check in the loop was gated on can_allocate_kv(...), not on a fixed slot count. That is the crux. Every active sequence holds a KV cache whose size grows with its current length:
kv_bytes(seq) = 2 · L_seq · n_layers · n_kv_heads
· d_head · bytes_per_elemThe factor of 2 is keys and values. The batch is admissible only while the sum of these caches fits the memory reserved for KV, so the effective batch size is not a constant B — it is however many sequences currently fit, which shrinks as sequences lengthen. A server may admit 40 short requests but hold only 8 once each has generated thousands of tokens. This is why paged KV allocation (PagedAttention) matters so much: by handing out KV memory in small fixed blocks instead of one contiguous reservation per sequence, it slashes fragmentation and packs more live sequences into the same memory, directly raising the achievable batch and thus throughput.