Iteration-level scheduling is the deceptively small idea that a language-model server should make a fresh scheduling decision before every single forward pass — every token — rather than once per request. Classic servers schedule at request granularity: a request is admitted to a batch, the batch runs to completion, and only then does the scheduler look again. Iteration-level scheduling shrinks that quantum from ‘a whole generation’ to ‘one step,’ and that single change is what makes modern LLM serving work. It is the mechanism underneath continuous batching, the place where priority and fairness are actually enforced, and the reason a slow request no longer blocks a fast one. This piece stays on the scheduling policy itself: what the quantum is, the decision loop that runs each iteration, how ordering policies plug in, and where it bites on CPU.
Request-level versus iteration-level scheduling
A scheduler’s quantum is the unit of work it commits to before it is allowed to reconsider. Traditional batch serving uses a request-sized quantum: pick a set of requests, run them together until the last one emits its end-of-sequence token, then schedule the next batch. Because generation lengths vary wildly — one reply is 12 tokens, another is 800 — the whole batch is held hostage by its longest member. Requests that finished early sit idle in their slots, and new arrivals wait outside the door until the entire batch drains.
Iteration-level scheduling redefines the quantum as a single decode iteration: one forward pass that advances every active sequence by exactly one token. After that pass the scheduler regains control and re-decides everything. Nothing is committed beyond the next step. Introduced by the Orca serving system, this is the pivot from ‘schedule a job’ to ‘schedule a step,’ and every capability below follows from it.
The forward pass as the scheduling quantum
Why is a single forward pass the natural atom? Because autoregressive decoding already proceeds one token at a time. Given a running sequence, the model consumes the last token, reads the cached keys and values for all prior positions, and produces a distribution over the next token: logits = f(x_t, KV_cache). That step is indivisible — you cannot stop halfway through a matrix multiply — but the boundary between two steps is a clean, cheap place to intervene.
Crucially, the batch dimension is free to change at that boundary. A decode step over a batch of B sequences is a set of shape-[B, d] operations; making B larger or smaller for the next step costs nothing structurally — you just assemble a different set of rows. The KV cache for each sequence persists in memory independently of the batch it rides in, so the per-token boundary is where the scheduler can add a sequence, drop one, or reorder them without disturbing anyone’s state. The quantum is one step because one step is the finest granularity the model itself exposes.
The per-iteration decision loop
At each iteration the scheduler runs a short, fixed routine before it hands a batch to the model. Conceptually:
while server is running:
finished = [s for s in running if s.emitted_eos or s.at_max_len]
release(finished) # free KV slots, return responses
while can_admit(waiting) and free_kv_blocks() > 0:
running.add( pick_next(waiting) ) # policy decides who
batch = compose(running) # rows for this forward pass
logits = model.step(batch) # ONE token for every row
append_tokens(running, logits)Three decisions happen every pass: release sequences that just finished (this iteration, not at end of batch), admit waiting requests into the freed capacity, and compose the batch that runs next. The loop body executes once per generated token across the whole server, so it must be cheap — a few list operations and a memory check, not a heavy optimizer. Its cost is amortized against a full forward pass, which dominates, so the scheduling overhead is comfortably in the noise.
Scheduling policies: FCFS versus priority
The loop above has one open slot: pick_next(waiting). That is the policy, and iteration-level scheduling is agnostic to which one you plug in. The simplest is first-come, first-served: keep the waiting queue in arrival order and admit from the front whenever a KV slot frees up. FCFS is predictable and starvation-free — every request eventually reaches the head — but it cannot express that some requests matter more.
A priority policy instead keys the queue on a score: an interactive chat outranks a bulk batch job, a paying tier outranks free traffic, or a request near its deadline is bumped up. Because the scheduler re-evaluates every iteration, priority is not just an admission decision made once — it can be re-checked continuously, so a newly arrived high-priority request is considered at the very next step rather than after the current batch drains. The fine granularity is precisely what makes priority responsive instead of advisory — the iteration boundary is where any such policy actually takes effect.
How the granularity enables continuous batching
Continuous batching — letting requests join and leave a running batch at any time — is often described as a technique in its own right, but mechanically it is simply what iteration-level scheduling lets you do. If the scheduler only regained control at the end of a request-sized batch, there would be no moment at which a finished sequence could be swapped out for a waiting one. The per-token boundary creates that moment, over and over.
Because each sequence carries its own KV cache and its own position counter, removing a finished sequence and slotting a fresh one into the batch is just an edit to the set of rows fed to the next forward pass. No batch is ever ‘drained and refilled’ as a unit; membership is fluid step to step. This is why the two ideas are always mentioned together: continuous batching is the behaviour, iteration-level scheduling is the enabling mechanism. The throughput math of that behaviour is developed in the continuous-batching companion; the point here is that without the fine quantum, there is nowhere to make the swap.
Prefill and decode in one iteration
Not every sequence in a batch is at the same phase. A freshly admitted request must first be prefilled — its whole prompt of P tokens pushed through to populate the KV cache — before it can decode one token at a time. Prefill is compute-heavy and processes P positions at once; decode is memory-bound and processes a single position. Iteration-level scheduling has to decide, each step, how to mix the two.
The naive choice is to run a prefill as its own iteration, but a large prompt then stalls every decoding sequence for that step — a latency spike for everyone. Schedulers therefore either interleave prefills between decode steps, or chunk a long prefill into several smaller pieces spread across successive iterations so each step stays bounded in size. Selective, ragged batching (Orca) lets sequences at different lengths share a step at all. The scheduler’s per-iteration job is thus not only who runs but in what phase, keeping each forward pass roughly uniform in cost.
A worked example
Take a server with room for 4 concurrent sequences and a queue of six requests R1…R6, under FCFS. Suppose R1 will emit 6 tokens, R2 2 tokens, R3 5, R4 3, and R5, R6 are waiting.
iter batch events
1 R1 R2 R3 R4 all step once
2 R1 R2 R3 R4 R2 finishes (2 tokens) -> free slot
3 R1 R3 R4 R5 R5 admitted at once (not after batch)
4 R1 R3 R4 R5 R4 finishes (3) -> admit R6
5 R1 R3 R5 R6 ...
6 R1 R3 R5 R6 R1 finishes (6)The key line is iteration 3: the instant R2 hits its end-of-sequence token, its slot is reclaimed and R5 starts on the next step. Under request-level scheduling, R5 and R6 would wait until R1 — the longest — drained at iteration 6, leaving finished slots idle for up to four steps. The fine quantum converts that dead time directly into served tokens.
Fairness, starvation, and preemption
Fine-grained rescheduling introduces its own hazard: a policy that always favours the ‘best’ request can starve the rest. Under strict priority, a steady stream of high-priority arrivals means a low-priority request at the back of the queue may never be admitted. Because the decision is remade every iteration, starvation can be relentless rather than occasional. Schedulers counter this with aging — a waiting request’s effective priority rises the longer it waits — so it eventually outranks fresh arrivals and gets its turn. FCFS sidesteps the problem entirely but gives up differentiation.
The same granularity also permits preemption: a running sequence can be paused between iterations, its KV cache either kept resident or evicted to host memory (and recomputed or swapped back later), so a more urgent request can take its slot immediately. Preemption is only coherent because state lives outside the batch and the boundary between steps is clean. The cost is the book-keeping and possible recompute of an evicted sequence — a knob the policy trades against responsiveness.
Implications for small models on CPU
On a CPU serving a small language model the arithmetic changes but the argument sharpens. A CPU sustains a much smaller effective batch than a GPU, so every slot is precious and idle slots hurt proportionally more — iteration-level scheduling’s elimination of end-of-batch dead time is a direct win. At the same time, a single forward pass on CPU takes longer in wall-clock terms, which means the scheduler’s per-iteration overhead is even more thoroughly amortized: a few microseconds of queue manipulation against tens of milliseconds of compute is free.
The subtler CPU consideration is prefill. With limited compute, a big prompt’s prefill can dominate a step and stall interactive decoders badly, so chunked prefill and small step sizes matter more, not less. And because CPU deployments are often memory-constrained, the KV-slot budget that gates can_admit is tight, so the scheduler spends much of its time deciding admissions against that ceiling.
Common pitfalls
The first pitfall is conflating iteration-level scheduling with continuous batching: the former is the mechanism (schedule every forward pass), the latter is one behaviour it enables. Treating them as synonyms hides the fact that priority, fairness, and preemption ride on the same mechanism.
Second, forgetting that admission is gated by KV-cache memory, not by a request count. A scheduler that admits by slot count alone will over-commit and be forced into emergency preemption when the cache fills. Third, letting the per-iteration policy grow expensive — the loop runs once per token per server, so an O(n log n) re-sort of a huge queue every step can quietly become real overhead; keep it incremental. Fourth, ignoring starvation under priority: without aging, a differentiated policy silently strands its lowest tier. Each pitfall is a case of forgetting that the step boundary is powerful precisely because it is constantly exercised.