- 1Reap any requests that finished generation in the previous step (EOS, stop sequence, or max_tokens hit) and free their KV blocks
- 2Run one batched decode step over the resulting set of active requests, advancing each by exactly one token
- 3Admit waiting requests up to the budget, performing prefill (or chunked prefill) for newly admitted ones
- 4Compute the available KV block budget given current GPU memory and any in flight reservations
- 5If memory pressure remains, preempt lowest priority running requests by swapping their KV to CPU or marking them for recompute
Each scheduler iteration runs: reap finished requests and free their KV, compute the block budget, admit waiting requests, preempt under pressure, then run one batched decode step.
Picture a small ferry that crosses a river over and over. Before each crossing, the captain first lets off everyone who reached their stop, freeing up seats. Then he counts how many seats are now open. He waves new passengers aboard up to that count. If he somehow over-promised and the boat is too heavy, he asks the lowest-priority passengers to step off and wait for a later trip. Only then does he actually cross the river once, moving everyone forward by one stop. Next trip, he repeats the whole routine. The crossing itself is always the last thing, because the captain wants the fullest, safest boat before spending the fuel.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Continuous batching is the single largest throughput lever in modern LLM serving, and the scheduler that drives it is one of the most quoted senior interview topics. The naive alternative, static batching, groups a fixed set of requests, runs them together, and waits for the slowest one to finish before starting the next group. That wastes the GPU badly: short requests finish early and their slots sit idle while a long request drags on.
Continuous batching, sometimes called in-flight batching, instead rebuilds the active batch on every decode step. Requests join and leave mid-flight. The scheduler runs a tight loop, and within each iteration the steps follow a strict order that is not arbitrary. The order encodes a resource invariant: you free memory before you measure it, you measure before you hand it out, and you run the expensive forward pass only once the batch is as dense as the memory ceiling legally allows.
This deep dive walks through each step of one iteration, explains why it sits exactly where it does, and connects the loop to the paged-attention primitive that makes block-level allocation cheap enough for this to work at all. By the end you should be able to recite the order and, more importantly, defend each position from first principles.
Why token-level scheduling beats whole-request batching
In a transformer decode loop the GPU is memory-bandwidth-bound, not compute-bound. Each step streams the entire KV cache from HBM to compute one new token per sequence. The marginal cost of adding another sequence to that step is small, because the bottleneck is the cache read, not the matmul. This is exactly why batching is the biggest single throughput lever in inference.
Static batching fails to exploit this. It admits a group, runs it to completion, and leaves freed slots idle until the whole group drains. A batch with one 2000-token generation and seven 50-token generations wastes seven slots for most of its life.
Continuous batching fixes the idle-slot problem by scheduling at the granularity of a single token. After every decode step the batch is reconstituted. Finished sequences leave, waiting sequences enter, and the GPU stays densely packed. The cost of this flexibility is a scheduler that must run a careful bookkeeping routine before every forward pass.
That routine is the five-step iteration this question asks you to order. It is essentially a memory manager wrapped around a single GPU kernel launch. The scheduler does not run the matmul itself; it decides which sequences belong in the next batch, allocates and frees their KV blocks, and then hands the assembled batch to the model. Because this happens every token, the bookkeeping must be cheap, which is exactly what paged allocation buys. The throughput payoff is large: continuous batching commonly delivers several times the tokens per second of static batching on the same hardware, almost entirely by eliminating idle slots.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- vLLM's scheduler implements exactly this iteration-level loop, freeing KV blocks on completion before recomputing the admission budget each step.
- SGLang runs continuous batching with RadixAttention prefix sharing, admitting requests against a live block budget every decode step.
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy must reaping finished requests happen before computing the KV-block budget?
A finished sequence keeps holding its KV blocks until reaped. Budgeting before reaping reads stale occupancy, so you under-admit and waste capacity. Free first, then the measured free-block count is accurate, then admit against it.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Putting the decode step first or admitting new requests before freeing finished ones. You must reclaim KV blocks before you can know the true budget for admission.
60 second bullets to scan on the way to the call.
Why finished requests must be reclaimed before the budget is measured
What the KV-block budget depends on and how reservations affect it
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.