Continuous batching — also called iteration-level scheduling — is the single change that turned autoregressive LLM serving from a GPU-starved workload into a throughput machine. The idea is almost embarrassingly simple: instead of forming a batch of requests, running it to completion, and only then starting the next batch, the scheduler reforms the batch after every token-generation step, admitting queued requests into slots that just freed up and evicting sequences that just finished. That one move — scheduling at the granularity of a single decode iteration rather than a whole request — is what lets a server keep its matrix engines busy when requests have wildly different output lengths. This piece works through the arithmetic: where static batching leaks utilization, how the admit/evict loop plugs the leak, why the batch is ‘ragged,’ and why the true ceiling is KV-cache memory, not compute.
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.
Latency trade-offs: throughput is not free
Continuous batching optimizes aggregate throughput, and that objective can quietly tax an individual request. Two effects matter. First, the more sequences you pack into a step, the larger the per-step matrix multiplies, so each token’s decode gets slightly slower — higher throughput, marginally higher time-per-output-token for any single user. Second, a request may wait in the queue when the batch is memory-full, adding to its time-to-first-token.
So the batch size is a dial between throughput and latency, not a free lunch. Serving systems cap the batch (or the admitted tokens per step) to protect tail latency, or let it run large to maximize tokens per second and dollar. An interactive chat endpoint guards TTFT and per-token latency; an offline batch-generation job pushes the batch as high as memory allows. Continuous batching does not remove the trade-off; it moves the whole throughput/latency frontier outward, so every operating point beats static batching’s.
Implications for small models and CPU serving
The same math applies when the ‘GPU’ is a CPU running a small language model, but the balance shifts. On CPU, decode is even more firmly memory-bandwidth bound and core counts are modest, so the batch sizes that keep the hardware busy are smaller — you saturate bandwidth with a handful of sequences rather than dozens. It still helps, because the utilization argument is about length variance, not raw scale: recycling a slot the instant a short generation finishes is valuable whether the batch holds 4 sequences or 400.
The KV-memory ceiling is often friendlier on CPU, where system RAM is plentiful compared with GPU VRAM, so the binding constraint tends to be compute and bandwidth rather than cache capacity. The takeaway for small-model serving: enable continuous batching to smooth over mixed request lengths, but tune the maximum batch to your bandwidth roofline rather than chasing the huge batches that only make sense on high-VRAM accelerators.
Common pitfalls
Three mistakes recur. First, pairing continuous batching with a padded attention kernel: you reintroduce the ragged waste and wonder why throughput underdelivers — you need a varlen/unpadded kernel for the scheduling win to survive into the attention op. Second, sizing the batch by slot count instead of memory: because KV grows with length, a batch that fits at admission can exhaust memory later, forcing eviction, recomputation, or out-of-memory stalls; admit against a live memory budget, not a fixed B.
Third, ignoring prefill interference: letting a giant prompt’s prefill share a step with latency-sensitive decodes spikes everyone’s time-per-token, which shows up as jittery tail latency a throughput average hides, so measure per-token latency distributions too. Get these three right — ragged-aware attention, memory-based admission, and prefill-aware stepping — and continuous batching delivers the multiplicative throughput gain its arithmetic promises.