Autoregressive serving does not give every request the same completion point. One sequence may emit an end token after a few decode steps while another remains active for hundreds. If the serving engine keeps the original request batch fixed until every member finishes, completed sequences leave execution capacity stranded behind longer sequences.
Iteration-level scheduling moves the scheduling boundary inward. Instead of treating an entire request as the indivisible scheduling unit, the engine returns to the scheduler after a model iteration. Finished sequences can leave, waiting work can enter, and the next iteration can run with a different set of active sequences.
A request batch can become sparse over time
Consider four requests admitted together:
iteration 1: A B C D
iteration 2: A B C D
iteration 3: A B D
iteration 4: A D
iteration 5: DA request-level policy that owns the batch until D finishes cannot necessarily fill the empty positions with queued requests. The accelerator still executes decode work, but the useful batch width falls as shorter sequences complete.
The effect follows from autoregressive generation itself. Output length is data-dependent, and termination can occur at different iterations even when requests entered together. A fixed batch therefore couples admission of new work to the slowest surviving member.
Iteration-level scheduling removes that coupling:
iteration 1: A B C D
iteration 2: A B C D
iteration 3: A B E D
iteration 4: A F E D
iteration 5: G F E DThe letters only illustrate membership. A production scheduler also has to account for token budgets, sequence limits, KV-cache capacity, priorities, prefill work, and implementation-specific execution constraints.
The scheduling unit changes, not the autoregressive dependency
Rescheduling after an iteration does not make one sequence generate future tokens in parallel. A decode token still depends on the sequence state produced by earlier tokens.
The change is across requests. At an iteration boundary, the server has a set of sequences that are ready for more model work. It can choose a new batch from that set rather than preserving batch membership from an earlier admission decision.
This distinction separates two forms of concurrency:
inside one sequence:
token t -> token t+1 -> token t+2
across sequences:
iteration k = {A_k, B_k, C_k, ...}
iteration k+1 = {A_k+1, D_k+1, E_k+1, ...}The second set can change even though each individual sequence remains autoregressive.
KV state makes replacement practical but constrains admission
A continuing sequence cannot restart from its full text on every iteration without discarding most of the benefit of incremental decoding. Serving engines retain key/value state for prior tokens so the next decode step can extend the sequence from cached state.
That state also gives scheduling a memory dimension. Admitting a waiting request is not only a question of an available batch slot. Its prompt and subsequent generation require KV-cache capacity, and active sequences consume more cache as their token counts grow.
A scheduler can therefore have compute room for another sequence while lacking safe cache capacity for it. Conversely, freeing a completed sequence can release both a scheduling position and its associated cache allocation.
The exact allocation mechanism is implementation-specific. Contiguous caches, paged caches, eviction policies, recomputation, and prefix reuse impose different costs. Iteration-level scheduling supplies a finer decision point; it does not define a universal KV-memory policy.
Prefill and decode create unequal iteration work
New requests normally begin with prompt processing, while established requests may need only their next decode token. Those operations have different token counts and execution characteristics.
A scheduler that admits new requests between decode iterations must decide how prompt work shares an iteration with active generation. Some systems separate phases; others support forms of mixed or selective batching; some split long prefills into chunks.
This makes “replace a finished request immediately” an abstraction rather than a guarantee that any waiting request can enter at no cost. The next batch must still satisfy the engine’s token budget and execution contract.
Modern serving configurations expose this boundary directly. For example, vLLM defines limits on the number of tokens and sequences processed in an iteration. Those controls are implementation settings, not properties of Transformer architecture.
Iteration boundaries expose a latency-throughput policy surface
Frequent rescheduling gives the engine more opportunities to admit work, but the policy still determines which work wins those opportunities.
First-come-first-served admission can favor queue order. Priority scheduling can move selected requests ahead. A token budget can limit large prefills. Cache pressure can prevent admission even when a request has waited longer than others.
As a result, iteration-level scheduling should not be equated with a specific fairness or latency guarantee. It changes the granularity at which policy can act. Queue discipline, resource accounting, and preemption rules remain separate choices.
The mechanism established by systems such as Orca is narrower and more durable: scheduling at model-iteration granularity allows batch membership to track changing request state instead of remaining fixed for the lifetime of the original batch.
Dynamic membership is the central invariant
The useful property is not a particular batch size. It is that completion of one sequence does not force its former capacity to remain tied to unrelated long-running sequences.
At each scheduling boundary, the engine can reconcile three changing sets:
running sequences
finished sequences
waiting sequencesIt then forms the next executable batch subject to compute and memory constraints. This turns variable output length from a fixed-batch occupancy problem into a repeated resource-allocation decision.
The boundary is still concrete: the scheduler can only react at points where the execution engine returns control. Iteration-level scheduling places those points between model iterations, giving an LLM server a chance to reshape the batch as generation progresses.