Iteration-Level Scheduling (Continuous Batching)
Iteration-level scheduling, sold as continuous or in-flight batching, re-forms the batch at every forward step instead of once per batch of requests. Finished sequences leave and queued ones join on the next step, which decides how much of a GPU's decode capacity real traffic with uneven output lengths can use.
TL;DR: A static batch waits for its longest request before admitting the next batch. Iteration-level scheduling can refill each finished slot on the next step. The gain comes from recovering idle slots; its size depends on output lengths, queue depth, memory and the cost of each iteration. Slot utilization is not GPU utilization, and a utilization ratio is not automatically a wall-clock speedup.
The mechanism
Request-level batching collects requests, runs prefill for all of them, and decodes in lockstep until every sequence has emitted its end token. A sequence that finishes at step 50 keeps its slot, and its share of each step's compute, until the slowest one finishes at step 900. New arrivals wait for the whole batch to drain.
Iteration-level scheduling, introduced as such by Orca (Yu et al., OSDI 2022), moves the scheduling decision inside the generation loop. Before each forward pass the scheduler looks at the running set and the queue, drops sequences that finished, admits waiting ones if memory and token limits allow, and builds one batch for this step only. The paper's selective batching runs compatible operations together while handling attention separately for each request's history. Modern ragged-batch implementations flatten tokens into a shared linear-layer matrix and use per-request boundaries for attention.
How much it buys
A static batch occupies slots for steps and does useful token-steps. Across repeated independent batches, the ratio of total useful work to total slot capacity approaches . This is a ratio of expectations, not the expectation of a single batch's ratio. In a continuous approximation with independent exponential lengths of mean , the expected maximum is , with the harmonic number:
With a permanently backlogged queue and no admission constraints, continuous batching keeps every slot busy. Its ideal slot-utilization gain is then . Turning that into a time-based throughput ratio requires constant iteration duration and ignores prefill, scheduling, memory limits and the final queue drain.
toy batch B = 4, output lengths 50, 120, 300, 900 tokens
static slot-steps = 4 x 900 = 3,600; useful = 50 + 120 + 300 + 900 = 1,370
utilization = 1,370 / 3,600 = 38.1%
exponential B = 8: H_8 = 2.718 -> 36.8% -> 2.72x
B = 32: H_32 = 4.058 -> 24.6% -> 4.06x
B = 64: H_64 = 4.744 -> 21.1% -> 4.74x
uniform every L equal -> max = mean -> 100% -> 1.00x
sanity the gain grows with batch size and with length variance, and is
zero for equal lengths, so it is a property of the traffic
Try a finite queue where the assumptions are visible. Eight requests A through H need [2, 6, 3, 8, 2, 4, 5, 2] output tokens, all arrive before step 1, and two slots each emit one token per iteration. Prefill is excluded. Static pairs take iterations; refilling slots independently finishes in 17. Both emit tokens. Static utilization is ; continuous utilization is . The last request still leaves a draining tail. Step through both schedules, then switch to equal lengths and observe the advantage disappear.
Refilling a slot adds that sequence's linear work and KV reads. A small, weight-bound batch can absorb the linear work without much extra time; long contexts can make KV traffic dominate. Admission of a prompt also adds prefill work. The scheduler improves use of capacity, but the phase-by-phase cost model decides how long an iteration takes.
| Scheme | When the batch changes | Wasted capacity | New request waits for |
|---|---|---|---|
| Static (request-level) | once per batch | idle slots until the longest ends | the whole batch to finish |
| Dynamic (timeout-based) | once per batch, formed on a timer | same as static once running | the timer, then the batch |
| Iteration-level | every forward step | draining tails or admission limits | the next eligible step |
The admission decision
A slot is only one constraint. The scheduler also needs KV blocks, a per-step token budget and an execution shape the engine supports. Distinguish request concurrency from tokens scheduled: a decoding request usually contributes one new token, while a prompt can contribute a chunk. A queue can be non-empty while capacity remains unused because its next requests cannot fit. Check the engine's versioned configuration and scheduler trace before attributing such gaps to a lack of traffic.
Where it breaks
Admitting every waiting request as soon as a slot frees is how the KV pool fills. A sequence admitted with a short prompt keeps growing, and when the pool is exhausted mid-decode the scheduler must preempt a running sequence, which costs its recomputation later. Admission therefore has to look at free blocks, not only at slots.
Admitting a long prompt into a running decode batch can stretch the step for every active user. Chunked prefill limits how many prompt tokens compete with decode in one iteration. Its token budget trades prompt progress against inter-token latency; it is not a universal latency bound because token cost varies with the model, context and hardware.
The CPU becomes visible. Rebuilding the batch, slot mappings and sampling inputs every few milliseconds is real work in Python, and a scheduler that takes 2 ms per 5 ms step leaves the GPU idle 2 of every 7 ms unless scheduling overlaps execution. And continuous batching raises throughput, not single-request speed: a lone user sees no change.
What interviewers listen for
Explain the idle slots the policy recovers and the assumptions behind any gain. Separate useful slot-steps from measured tokens per second. Then identify the costs: growing KV pressure can cause preemption, and prompt admission can stretch decode iterations. A strong answer compares both throughput and inter-token latency under the same traffic trace.
Say it in 30 seconds
"Static batching runs a batch until its longest sequence ends, so short sequences hold idle slots; with exponential output lengths that wastes all but one over the harmonic number of the batch size, about 79% at batch 64. Iteration-level scheduling rebuilds the batch every forward step, so a finished sequence's slot is refilled immediately. Linear layers run over the flattened tokens and attention runs per sequence, which is what lets that work. The cost moves to KV memory pressure and prefill interference."