A language model does not write an answer in one shot. It runs a full forward pass to produce one token, appends that token to its own input, and runs again. A 300-token reply costs 300 sequential passes through billions of parameters — and nobody, including the model, knows it will be 300 until the end-of-sequence token actually appears.
Your serving system therefore has to schedule work whose duration it cannot measure, cannot predict, and cannot cancel early. Every difficulty in LLM serving flows from that one fact.
Why batch at all
During decode the GPU is not short of arithmetic, it is short of memory bandwidth. To produce a single token for a single user it must stream every weight in the model out of HBM and then do a trivial amount of maths with them. Serving one request at a time wastes almost the entire card.
Batch thirty-two sequences and you stream those same weights once and reuse them for thirty-two tokens:
def step_cost_ms(batch, prefill_tokens):
return (22.0 # fixed: kernel launches + streaming weights
+ 0.35 * batch # decode: another sequence is nearly free
+ 60.0 * prefill_tokens / 1000)
step_cost_ms(batch=1, prefill_tokens=0) # 22.4 ms -> 1 token
step_cost_ms(batch=32, prefill_tokens=0) # 33.2 ms -> 32 tokens
Thirty-two times the output for one and a half times the time. Batch size, not clock speed, is what your throughput graph really tracks.
The obvious way to batch is the wrong way
Request-level (static) batching does what you would do with any other workload: collect N requests, pad them into one tensor, run the generation loop until they are all finished, return the results together, take the next N.
The flaw is structural. The loop only exits when the slowest member finishes, so a request that emitted EOS after twelve tokens keeps occupying its row of the tensor for however many hundreds of steps the longest member needs. Its slot is computed on every pass and contributes nothing.
That gives static batching a makespan with a clean closed form — each group costs its longest member:
def static_makespan(reqs, cap, chunk):
t = 0
for g in [reqs[i:i + cap] for i in range(0, len(reqs), cap)]:
start = max(t, max(r["arrive"] for r in g)) # wait for the batch to fill
max_pf = max(prefill_steps(r["prompt"], chunk) for r in g)
max_out = max(r["out"] for r in g) # the hostage-taker
t = start + max_pf + max_out - 1
return t
Put a number on the waste. Call one batch slot occupied for one forward pass a slot-step, and call it useful only if a real token came out of it:
useful = sum(step["active"] for step in log)
total = cap * len(log)
print(useful / total) # 0.22 static / 0.69 continuous
On a realistic long-tailed workload across eight slots, static batching lands near 22%. More than three quarters of a very expensive GPU spent computing padding. It gets worse as the batch gets bigger, because a larger group is more likely to contain one giant member that everybody else has to wait for.
Iteration-level scheduling
The fix is to stop treating the batch as a unit of work. A batch only has to be a unit of one forward pass; nothing requires the same sequences to be in it next pass.
This was published as Orca (OSDI 2022) under the name iteration-level scheduling. vLLM, TGI, TensorRT-LLM and SGLang all ship it, usually calling it continuous or in-flight batching. The whole idea is three phases:
def run_continuous(reqs, cap, chunk):
slots, t, qi, done = [None] * cap, 0, 0, 0
while done < len(reqs):
# 1. ADMIT - fill every free slot from the head of the queue
for s in range(cap):
if slots[s] is None and qi < len(reqs) and reqs[qi]["arrive"] <= t:
slots[s] = new_state(reqs[qi], chunk); qi += 1
# 2. STEP - exactly one forward pass over the resident sequences
for r in filter(None, slots):
r.advance() # prefill chunk, or emit one token
# 3. RETIRE - EOS frees the slot immediately, not at batch end
for s in range(cap):
if slots[s] and slots[s].finished:
slots[s] = None; done += 1
t += 1
A sequence that finishes at step t is replaced at step t+1. That is the entire trick, and on the demo's default trace — 64 requests, 8 slots, long-tailed output lengths — it takes 1 122 forward passes instead of 3 470, moves utilisation from 22% to 69%, and multiplies throughput by 3.11×. Same weights, same hardware model, same requests.
Prefill and decode are two different animals
Prefill reads the whole prompt at once and computes its key/value tensors in parallel: thousands of tokens of matrix multiplication, compute-bound and expensive. Decode produces one token per sequence per step: a tiny amount of maths dominated by streaming weights, bandwidth-bound and nearly free per extra sequence.
Mix them naively and you get the classic pathology — one user pastes a 4 000-token document, its prefill lands in a decode iteration, and every other user's stream visibly freezes for that step. Look at the cost model again: step_cost_ms(batch=16, prefill_tokens=4000) is 268 ms against 27.6 ms for the same batch with no prefill.
Chunked prefill slices the prompt into fixed pieces so no single step is ever owned by one user's prompt:
def prefill_steps(prompt, chunk):
return max(1, math.ceil(prompt / chunk))
# vLLM: enable_chunked_prefill=True, max_num_batched_tokens=512
A useful detail falls out of this: the last prefill chunk already produces the first output token, which is why TTFT is essentially queueing plus prefill time.
KV-cache memory, not FLOPs, caps the batch
It is tempting to think batch size is limited by arithmetic. It is not — a decode step barely notices ten extra sequences. What runs out is memory. Every resident sequence holds a KV-cache that grows by one entry per layer per attention head for every token it has ever seen, in the same HBM as the weights:
def kv_bytes_per_token(layers, kv_heads, head_dim, dtype=2):
return 2 * layers * kv_heads * head_dim * dtype # K and V
per_token = kv_bytes_per_token(32, 8, 128) # Llama-3-8B bf16 -> 128 KiB/token
max_tokens = (0.92 * 80e9 - 16e9) / per_token # ~ 450,000 tokens
cap = int(max_tokens // 2048) # ~ 220 concurrent 2k-token chats
That number is your maximum batch size. It is also why PagedAttention and continuous batching are two halves of one story: the scheduler decides who runs, paging decides how many fit.
And because output length is unknown, a batch that fitted at admission can overflow twenty steps later. The server must then preempt — swap a victim's KV out to host RAM, or drop it and recompute the prefill on retry (usually cheaper than a PCIe round trip). Preemption is a correctness mechanism, not a tuning option, but a rising preemption counter means you over-committed.
The honest part
Continuous batching does not make the GPU faster. It stops variance in output length from wasting it. Set the slot cap to 1, or make every request the same length, and the speed-up collapses to exactly 1.00 — because static batching wastes nothing in those cases. The demo's skew sweep is blunt about this: ×1.00 at skew 0, ×2.31 at skew 0.3, ×3.11 at skew 0.6.
There is also a real cost. More sequences resident means each forward pass is fractionally slower, so a single request can finish later than it would on an idle machine even while the fleet gets three times faster. Throughput and per-request latency are different objectives, and the scheduler is optimising the first. Report goodput instead: requests per second that still met your TTFT and inter-token latency targets.
Tune max_num_seqs up until p95 TTFT breaks your SLO, then stop.
The page below runs the whole thing as a real discrete-event simulator — one seeded trace of arrivals and unknown output lengths, replayed through both schedulers, with a live slot×step occupancy timeline showing the padding under static batching and the tight packing under continuous. 60 assertions verify the engine against independent closed-form and brute-force implementations: https://dev48v.infy.uk/ai/days/day60-continuous-batching.html
Top comments (0)