Continuous Batching

We left the KV cache math with a number: an 80 GB GPU running Llama-2-13B can hold maybe 35 concurrent requests, and throughput is roughly proportional to how many you actually keep working at once. The catch is that “can hold 35” and “is usefully running 35” are different things. Because decode is memory-bound, the only way to make decode efficient is to batch — one read of the weights from HBM should serve as many requests as possible. This page is about the scheduling discipline that keeps that batch genuinely full, and the throughput-versus-latency trade it forces.

Why batching is the whole game

In decode, each step reads the entire weight matrix set from HBM to produce one token. If you do that for a single request, the expensive compute units are mostly idle — you paid the full memory-bandwidth cost to compute one token’s worth of math. Run 32 requests through the same weight read and you have amortized that read across 32 tokens. The cost throughline in one line: batching turns one HBM weight-read into many tokens, so the per-token dollar cost falls roughly linearly with batch size until you run out of KV memory or saturate compute.

So we want big batches. The problem is how requests enter and leave them.

Static batching wastes the GPU

The naive approach — static batching — assembles a batch, runs it to completion, then starts the next. But requests in a batch finish at wildly different times: one answer is 20 tokens, another is 800. With static batching, every request is held hostage by the longest one in its batch.

Static batch of 4 — all must finish together, shorter ones pad/idle

req A |####|------------------|   done at t=4, then 14 idle steps
req B |##################|        done at t=18 (the straggler)
req C |##|----------------|       done at t=2, then 16 idle steps
req D |#########|----------|      done at t=9, then 9 idle steps
       ^ useful work          ^ wasted GPU lanes (padding + idle)

Two costs hide here. Idle lanes: once A, C, and D finish, their slots in the batch do nothing but wait for B, yet they still occupy KV memory and a compute lane. Padding: to make the batch a clean rectangle, short sequences are padded to the longest length, so the GPU literally computes on filler tokens. With realistic output-length variance, static batching can waste well over half the GPU’s decode capacity.

Continuous batching keeps lanes full

Continuous batching (also called in-flight or iteration-level batching) makes the scheduling decision at every token step instead of every request. After each decode iteration, the scheduler checks: did any request emit its end-of-sequence token? If so, evict it and free its KV blocks immediately. Is there a waiting request and free KV space? Admit it into the now-open slot — even mid-generation for its neighbors.

Continuous batching — evict on finish, admit waiting reqs at once

slot1 |A A A A|E E E E E E E E E|   A finishes → E admitted instantly
slot2 |B B B B B B B B B B B B B|   the long straggler blocks no other lane
slot3 |C C|F F F F F F F F F F F|   C finishes early → F fills the gap
slot4 |D D D D D D D D|G G G G G|   D finishes → G fills the gap
       ^ no slot ever idles while other work is queued

The straggler B no longer freezes the whole batch; the other lanes have already moved on to E, F, and G. The GPU stays packed, so the amortization from the previous section is realized continuously rather than collapsing every time one request finishes early.

Prefill and decode share the engine

A subtlety: a freshly admitted request must first do prefill (process its whole prompt) before it can decode. Schedulers interleave these — a step may prefill new arrivals while decoding existing ones — and how aggressively they mix the two is a tuning knob that trades first-token latency against steady-state throughput.

The throughput-versus-latency trade

Continuous batching does not make any single request faster — it makes the system serve more requests per second on the same hardware. Those are different objectives that pull in opposite directions:

Lever	Throughput (tokens/sec, all users)	Latency (one user’s TPOT)
Larger max batch	↑ (more amortization)	↑ (each step does more work)
Smaller max batch	↓	↓

A bigger batch reads the weights once and serves more tokens, raising throughput and lowering dollar-per-token — but each decode step now does more arithmetic, so any individual user waits slightly longer between tokens. The right operating point depends on your product: a batch chat assistant optimizes throughput; an interactive coding tool caps batch size to protect latency. There is no universally correct setting, only the trade made on purpose.

The cost win, quantified

If static batching leaves the GPU ~50% idle and continuous batching gets it to ~90%, you serve roughly 1.8× the tokens per second on the same GPU — meaning ~1.8× lower dollar-per-token with no new hardware and no model change. That is why every serious serving stack does iteration-level scheduling.

Continuous batching is necessary but not sufficient: it can only admit a new request if there is free KV memory, and the static, pre-reserved memory layout of early systems made “free KV space” far rarer than it should have been. Fixing that is the job of the next page.

It actually happened — Orca introduces iteration-level scheduling (OSDI 2022)

Continuous batching has a birthplace: Orca, presented at OSDI 2022 (Yu et al.). Before it, serving systems batched at the request level — exactly the static batching whose idle lanes we sketched above. Orca’s contribution was iteration-level scheduling: re-evaluate batch membership after every single token step, returning finished sequences and admitting waiting ones immediately. The same idea — under the names continuous or in-flight batching — was then built into vLLM, TensorRT-LLM, and Hugging Face TGI, and is now table stakes. It is a rare systems win with essentially no throughput downside: the only thing it spends is scheduler bookkeeping, which is negligible next to a decode step that reads gigabytes of weights from HBM.

The architect’s lens

Continuous batching is the scheduling discipline that realizes batching’s payoff — the five questions:

• Why does it exist? Because decode is memory-bound, one HBM weight-read should serve many requests — but static batching holds every request hostage to the longest in its batch, so when outputs vary (20 tokens vs 800) most lanes sit idle.
• What problem does it solve? The idle-lane and padding waste of uneven output lengths: by deciding batch membership every token step — evicting finished requests and admitting waiting ones immediately — it keeps the GPU packed, lifting utilization from ~50% to ~90% (≈1.8× more tokens/sec on the same card).
• What are the trade-offs? Throughput vs latency: a larger max batch amortizes the weight-read across more tokens (lower $/token) but makes each decode step do more work, so an individual user’s TPOT rises. The only overhead is scheduler bookkeeping, negligible next to a multi-GB weight read.
• When should I avoid it? You don’t disable it, but you cap the batch for an interactive, latency-sensitive product to protect TPOT; at batch 1 there is nothing to amortize.
• What breaks if I remove it? You fall back to static batching — short requests wait for the straggler, the GPU sits ~50% idle, throughput roughly halves and dollar-per-token roughly doubles, and a new request can’t join until the whole batch drains.

Check your understanding

1. Why does decode require batching to be efficient at all? Tie it to a hardware fact.
2. Name the two distinct sources of waste in static batching and explain each in one sentence.
3. What decision does continuous batching make at every token step that static batching makes only once per batch?
4. Continuous batching raises throughput but can slightly raise per-user latency. Why?
5. What resource limits how many waiting requests a continuous-batching scheduler can admit, linking this page to the previous one?

Show answers

1. Decode is memory-bandwidth-bound: each step reads the full weight set from HBM to make one token, leaving compute idle. Batching amortizes that single weight-read across many requests, so the otherwise-wasted compute does useful work.
2. Idle lanes: short requests finish early but their slot waits for the longest request, holding memory and a lane while doing nothing. Padding: sequences are padded to the longest length so the GPU computes on filler tokens.
3. Whether to evict any finished request and admit any waiting one — scheduling at the iteration (token) level rather than fixing the batch membership for the whole run.
4. A larger batch makes each decode step do more arithmetic, so the time between one user’s tokens (TPOT) increases even though total tokens/sec across all users rises.
5. Free KV cache memory. A new request needs KV space (and prefill) to join; if HBM is already full of other requests’ KV, it must wait — which is why packing KV efficiently (next page) directly raises effective batch size.