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.