Iteration-level scheduling
Explain why completed sequences should leave a batch immediately
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Autoregressive decode steps
- Static batching
- Queueing
Eight requests enter the 7-billion-parameter server together. Seven stop after 32 output tokens; one continues for 512. A static batch keeps all eight batch positions reserved until the long request finishes, so the seven completed positions perform no useful request work for 480 later model iterations. An iteration log makes the waste visible as seven finished sequence identifiers remaining in the batch table.
Modify the server so the scheduler rebuilds the active sequence list after every forward pass. After iteration 32, the seven completed requests leave and waiting requests can occupy the released positions. Orca calls this iteration-level scheduling. Modern serving systems often use the phrase continuous batching for the broader practice of changing batch membership as requests arrive and finish. The GPU timeline should show useful rows replacing empty positions, while request logs show earlier starts for queued work.
A static batch is formed once and remains together until every sequence finishes. Short outputs complete and leave empty slots while the longest sequence determines batch lifetime. Iteration-level scheduling revisits membership after each decode step: finished work leaves, new work enters, and preempted work can wait. The GPU sees a changing token batch rather than a fixed request batch.
Iteration-level scheduling, introduced in Orca, invokes the execution engine for one model iteration and then forms the next batch again. Continuous batching implementations use this opportunity to remove completed sequences and admit other work. The terms are often used together, but the important mechanism is the repeated scheduling point between model iterations.
Iteration-level scheduling raises utilization under variable output lengths, but the policy turns scheduler overhead and fairness into part of the token critical path. The scheduler must choose among new prefill, ongoing decode, resumed requests, and priorities while respecting cache capacity. A decision that maximizes scheduled tokens for one iteration can still reduce long-term goodput or cause latency misses.
Track request state at iteration boundaries
Represent each request with its phase, unprocessed prompt tokens, generated tokens, stopping state, KV blocks, sampling state, deadline, priority, and tenant policy. A request can move from waiting to prefill, from prefill to decode, from running to preempted, and from decode to completed or canceled. Record the reason for every transition.
At an iteration boundary, the scheduler chooses a token budget and a sequence budget. Each selected decode sequence normally contributes one new token. A selected prefill can contribute many tokens or one chunk. The resulting batch determines matrix shapes, cache reads and writes, communication, and the time until the next scheduling point.
Orca also described selective batching because not every model operation batches requests in the same way. Modern engines use architecture- and kernel-specific batching paths, but the principle remains: batching policy must match operation semantics. The scheduler cannot assume that arbitrary request phases or shapes can be concatenated without metadata and kernel support.
Allocate progress among competing requests
First-come-first-served provides a predictable admission order, but a large prefill can delay later short requests. Shortest-work or deadline-aware policies can improve some latency distributions while starving long requests whose remaining work is always larger. Priority classes require quotas, aging, or reserved capacity when continuous high-priority traffic is possible.
Decode service is especially visible because users observe token cadence. A policy can reserve a token budget for active decode and use remaining capacity for prefill. The reservation protects TPOT but can cause a large prompt to make very slow progress during heavy decode load. Report first-token latency by prompt length and service class so the trade remains visible.
Preemption is a memory decision as well as a scheduling decision. An engine can retain KV while a request waits, swap state to another memory tier, discard it and recompute later, or reject the competing admission. Current vLLM V1 documentation, for example, describes recomputation as its default preemption mode. The preferred choice depends on state size, transfer bandwidth, prompt cost, and expected wait.
Keep scheduler work off the device critical path
Decode iterations can be short, so CPU work between them can create visible GPU gaps. Scheduling, block-table construction, sampling, detokenization, distributed coordination, and launch submission must complete before the next iteration is ready. Measure the interval from one device iteration ending to the next beginning and attribute its host work.
Move independent scheduler work earlier or overlap the work with current device execution when the implementation permits. Preallocate metadata, batch allocator operations, and avoid blocking calls on the scheduling thread. Scheduling changes must preserve cancellation and admission correctness; stale metadata cannot refer to freed KV blocks.
Trace every iteration with the selected request IDs, token counts by phase, policy reason, allocation changes, and execution duration. A request's TTFT and TPOT can then be reconstructed from actual choices. Aggregate throughput alone cannot reveal starvation or repeated preemption.
Worked example: Replacing a static mixed-length batch
Eight requests start together. Seven finish after 32 output tokens; one produces 512. Under static batching, seven batch positions remain assigned to finished requests and perform no useful token work for 480 iterations.
- With iteration-level scheduling, remove each completed request at its finish step and admit waiting sequences into freed cache and token slots.
- Measure improved active-token count and total throughput, but also account for per-iteration scheduler and metadata cost.
- Test fairness when a continuous stream of short requests arrives. The long request should still advance according to the service policy.
- Compare TTFT and TPOT distributions under the same arrival trace. Increased throughput is useful only if admission delay and iteration variability remain within objectives.
Conclusion: Iteration-level scheduling removes seven completed sequences after token 32 and makes those execution and cache slots available to waiting work. The scheduler must still guarantee progress for the 512-token request and must keep per-iteration host work below the decode cadence.
Common errors
- Calling every dynamically changing batch continuous batching without examining iteration-level admission and removal.
- Maximizing active tokens each step. Long iterations can damage TPOT and deadlines even when throughput rises.
- Ignoring scheduler time because it runs on CPU. Gaps between short decode kernels can make host policy the critical path.
Reference summary
A static batch retains its original membership until the longest request completes. Iteration-level scheduling forms a new execution batch after a model iteration, so completed sequences leave and waiting work can enter. Rebuilding membership recovers slots that variable output lengths would otherwise leave unused.
Each iteration allocates a token budget and a sequence budget among prefill, decode, and resumed work. The policy affects batch shape, KV ownership, TTFT, TPOT, fairness, and preemption. Scheduler and metadata work must complete fast enough to avoid gaps between decode iterations.
- Token budget caps total scheduled tokens; sequence budget caps active request count.
- Decode usually advances one token per active sequence; prefill can contribute many tokens.
- Scheduling policy trades throughput, TTFT, TPOT, fairness, and cache locality.
- Preemption may swap, recompute, or discard cache state when capacity is insufficient.
- Priority classes require starvation protection and measurable guarantees.
Knowledge check
Why does continuous batching help more when output lengths vary widely?
Show the answer guide
- In a static batch, all sequence slots commonly remain tied to the batch until the longest output finishes. When output lengths vary widely, completed short sequences leave inactive slots while the long tail continues.
- Continuous batching removes a completed or blocked sequence at an iteration boundary and admits another ready sequence. Vacated token rows and KV capacity can therefore return to useful work without waiting for the longest original member.
- Wide output-length variance increases the expected gap between early completions and the last completion, so it creates more idle slot-time for continuous batching to recover.
- When output lengths are almost equal, static members finish together and little slot-time is stranded. Continuous scheduling still adds flexibility, but its throughput advantage is smaller and must exceed scheduler overhead.
Measure stranded slot-time from variable outputs
Simulate or run a server with batch capacity 16 under static and continuous batching. Use two declared workloads with identical mean output length: one where every request generates 128 tokens, and one where lengths are 8, 16, 32, 64, 128, 256, 512, and 1024 tokens with stated probabilities. Keep the arrival queue nonempty and use the same decode-time model or server configuration.
Evidence to keep: Submit the simulator or server configuration, request trace, a scheduler timeline showing membership by decode iteration, a table of completed tokens, requests, idle slot-iterations, and latency for both workloads and policies, and a causal conclusion connecting recovered slot-time to output-length variance.
Dynamic membership needs an allocator that can grow and release sequence state incrementally. Paged KV storage supplies that flexibility.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- Orca: Iteration-Level Scheduling↗
- PagedAttention / vLLM↗
- SGLang↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.