Summary
Continuous batching rebuilds the active request set between model iterations, allowing queued work to replace a completed request.
Consider two decode positions: A needs five more iterations, B two, and queued C three. C’s prefill is complete; all required KV reservations fit. Each occupied cell below represents one scheduled decode iteration, not prompt processing.
When can C use B’s position without disturbing A’s ordered state?
B ends after iteration 2; C is ready
Refill B's finished slot with C on the next iteration
Derivation
Must A finish before C can occupy B’s released slot?
Static membership uses of ten positions: 70% occupancy. Continuous membership uses : 100% occupancy, with C finished after iteration 5. This is not a measured throughput gain: iteration durations can differ.
The mechanism
Maintain a queue and request-state ledger keyed by request ID, not batch row.
| Request | Phase | Remaining iterations | Owned state |
|---|---|---|---|
| A | Decode | Valid KV length, positions, stop count, RNG | |
| B | Decode | Same fields, separately owned | |
| C | Ready/queued | Completed prefill and reserved capacity |
- Select decode tokens and eligible prefill chunks within token, memory and fairness limits.
- Run the supported batch; update each request’s valid KV, position and sampling state.
- On EOS,
max_tokensor cancellation, release that request’s owned references safely. - Rebuild membership for the next iteration; preserve each continuing request’s identity and order.
Packed offsets such as cu_seqlens can isolate variable-length sequences.
Paging is one cache-management choice, not a requirement of continuous scheduling.
Change the prefill or capacity constraint
1. C’s eight-token prompt is unfinished
Picture and change: permit prefill alongside two continuing decoders under a four-token iteration budget. Reserve two decode tokens, leaving at most two prompt tokens per iteration.
Check: four two-token chunks finish the prompt, assuming both decoders remain active. Track the prompt cursor and existing KV together. C cannot use first-token logits before its final prefill chunk completes.
Use when: long prefills threaten existing requests’ inter-token latency.
2. A free row lacks KV capacity
Picture and change: C needs three additional KV blocks, but only two are free. Defer admission or use an explicitly supported preemption policy.
Check: an empty row does not authorize allocation; cancellation must release only C’s references.
Use when: context lengths make row counts a poor memory proxy.
Failure and transfer
Moving A to another row while retaining row-indexed KV or sampler state can mix requests. A global RNG can also change A’s sampled string after C joins.
B finishes, but C’s prompt is unprocessed. Can C immediately decode?
Check your answer
No. Schedule prefill within both budgets; completed prefill supplies initial KV and the first-token distribution.
Prefill vs. decode
Prefill processes prompt positions; cached decode appends to per-request state. Small-batch decode can amortize weight traffic across requests, but bottlenecks depend on workload and hardware. See prefill versus decode and GPU memory bounds.
Tradeoffs
Batch size affects latency, compute and KV traffic; it does not guarantee throughput improvements. Admission, queue age and preemption policies determine fairness under memory pressure. GQA/MQA change architecture and cache size; paging addresses allocation, not all possible bottlenecks.
Common pitfalls
Measure arrival/length distributions, scheduler overhead, latency targets and memory capacity. A single-request profile does not establish serving throughput. Distinguish concurrency from context length; idle positions do not mean the whole GPU is idle.
References: Orca, SARATHI, PagedAttention.