Systems labAdvanced120 min estimateOriginal publication

Continuous Batching and Queueing

Schedule token work, not request counts: separate prefill and decode demand, budget KV state, bound starvation, and admit only the mix whose tail latency the system can still defend.

Authorship: InterviewsVector
Published / updated: 2026-09-26 / 2026-09-26
Review status: Artifact tests passing · primary sources recorded

Original InterviewsVector teaching. Executable artifacts are deterministic illustrative audits with focused tests and recorded primary sources; they do not claim device benchmarks, production capacity, statistical validation, hardware qualification, or universal model quality.

The decision in one pass

Continuous batching rebuilds the active batch at iteration boundaries as requests arrive, finish, cancel, block, or are preempted. Capacity must therefore be expressed in token work and KV state, not requests per second alone. Model prefill and decode separately: prefills expose parallel compute but can monopolize an iteration; decodes perform small sequential steps, hold KV memory for their lifetime, and are sensitive to time per output token. Define the request-shape distribution, arrival process, priority classes, SLOs for queue delay, time to first token and time per output token, token and memory budgets, chunked-prefill policy, fairness bound, cancellation semantics, and admission headroom. Use measured service curves for the exact model, precision, kernel, scheduler, device, and concurrency; analytical queueing or fluid models are screening tools. When utilization approaches the operating limit, queue and tail latency can grow sharply, so reject or degrade work before memory or latency collapses, and preserve per-class fairness and rollback evidence.

Why this matters

Two requests can consume radically different resources: a long prompt creates a large prefill burst and KV allocation, while a long answer holds state and serial decode work over many iterations. Static batches leave capacity idle when one sequence finishes. Naive continuous batching can improve throughput yet let long prefills delay active decodes, let high-priority traffic starve other tenants, fragment KV memory, or turn a burst into an unbounded queue. An average latency chart can remain green while one class misses every tail SLO.

You will be able to

Separate arrival rate, prompt tokens, output tokens, concurrency, prefill service, decode service, and KV occupancy by request class.
Explain iteration-level continuous batching, chunked prefill, paging, preemption, cancellation, and priority as explicit scheduler policies.
Derive capacity and latency screening bounds without presenting a fluid or queueing approximation as a measured SLO.
Design admission, overload, fairness, and degradation behavior that protects active sequences and tenants.
Validate a scheduler with representative and adversarial traffic distributions, traces, and failure injection.

Prerequisite contract

Your Vector Loop for this lab

01
Model
Map request classes, arrivals, prompt and output shapes, prefill and decode service, KV lifetime, priorities, cancellations, SLOs, admission, and device topology.
02
Derive
Derive per-class token demand, prefill and decode utilization, queue and service floors, active-sequence and KV bounds, fairness, and overload thresholds.
03
Build
Build a deterministic integer fluid model over invented traffic and a self-consistent scheduler profile; do not simulate or benchmark production serving.
04
Stress
Burst long prefills, lengthen outputs, skew tenants, cancel late, fragment KV, saturate one partition, exhaust active slots, and make priority unfair.
05
Operate
Monitor queue age, TTFT, TPOT, end-to-end latency, tokens, KV allocation, preemption, cancellation, fairness, utilization, admission, rejection, and recovery by class.
06
Defend
Defend the policy under mixed shapes and overload, and state which analytical assumptions require trace replay or load-test evidence.

Prefill and decode are different workloads sharing one device

Prefill processes many prompt tokens with substantial parallel work and creates KV state. Decode usually advances each active sequence by one sampled token per iteration, repeatedly reading weights and that sequence's cache. A long prefill can use the device efficiently while delaying the next token for already-streaming users. A short prompt with a long answer may have low TTFT but occupy a decode slot and KV memory for far longer. Capacity must retain both token dimensions and their lifetime.

Signal	Prefill interpretation	Decode interpretation
tokens	burst of prompt work	serial iterations until stop or limit
latency	queue plus prompt service drives TTFT	iteration cadence drives TPOT
memory	allocates KV proportional to accepted context	retains and grows KV across output
batching	large chunks increase efficiency but can block	more active sequences share each iteration
cancellation	can avoid unstarted prompt work	must free KV and stop future steps promptly

token_demand = Σ λ_class · (E[prompt_tokens] + E[output_tokens]); KV_peak ≠ token_demand

Token throughput screens service capacity, while KV depends on concurrent sequence lengths and allocation behavior. One cannot substitute for the other, and means are insufficient for tail admission.

Make every iteration a policy decision

01Admit or rejectReserve token, active-sequence, KV, and deadline headroom before work enters the device queue; do not rely on eventual eviction as admission control.
02Select active workBalance decode continuity, prefill progress, priority, tenant share, deadline, age, cache locality, and the maximum batch token budget.
03Chunk long prefillsBound how much prefill work can occupy an iteration so active decodes make progress, while accounting for repeated launch or scheduling overhead.
04Retire and reclaimOn stop, error, timeout, disconnect, or cancellation, halt future work, release KV pages, update accounting, and make client-visible outcome semantics explicit.

Paged KV allocation reduces contiguous-allocation waste and enables flexible sharing or preemption policies, but it does not create memory. Metadata, internal fragmentation, copy-on-write, prefix-cache ownership, eviction, and page-table operations still need accounting. Preemption may protect a deadline while wasting recomputation or transfer work; its cost belongs in the service model.

Choose an operating point below collapse

Utilization is not an SLO. As demand approaches effective service capacity, small variance or bursts can produce disproportionate queue growth. Token shapes, service times, arrivals, dependencies, and scheduling are not generally memoryless, so a simple queue formula is a screening approximation. Derive a safe operating envelope from measured service curves and validate it with trace replay and load tests that preserve correlations and tail shapes.

Little's Law: L = λW for a stable observed system; it does not guarantee stability or a latency distribution

Use consistent units and boundaries to reconcile average concurrency, throughput, and time. If the system is changing, dropping requests, or unstable, the interpretation needs explicit accounting.

Overload control	Protects	Trade-off to disclose
admission reject	active requests and latency	availability and client retry pressure
prompt/output cap	token and KV budget	task completeness and user expectation
priority or tenant quota	critical classes and isolation	fairness, starvation, and unused reserved capacity
smaller or fallback model	latency and cost	quality, safety, and version attribution
preempt or swap	urgent progress and device memory	recompute, transfer, and tail amplification

Audit one declared scheduler and traffic mix

batching_capacity_model.py

1def audit_batching(contract: BatchingContract, workload: BatchingWorkload) -> BatchingReport:
2    contract = validate_record(contract, BatchingContract)
3    workload = validate_record(workload, BatchingWorkload)
4    if workload.scope != contract.scope or workload.contract_content_id != contract.content_id:
5        raise ValueError("workload belongs to another batching contract")
6    # Screen total, prefill, decode, queue, service, fairness, active-slot, and KV bounds.

Expected output

example=illustrative_only
decision=CAPACITY_WITHIN_DECLARED_BOUND
utilization_permille=180;prefill=250;decode=75
queue_ms=5;worst_ttft_ms=185;tpot_ms=20
peak_kv_bytes=8808038400
claim=LOCAL_FLUID_CAPACITY_MODEL_NOT_QUEUEING_OR_DEVICE_BENCHMARK

Verify: python3 -m unittest discover courses/ai-engineering/reference-impl/continuous_batching

The invented fixture splits 40,000 token/s into declared prefill and decode partitions, caps a prefill chunk at what its partition can serve in one 20 ms iteration, and models two request classes. The audit reports 18 percent total, 25 percent prefill, and 7.5 percent decode utilization; a five-millisecond fluid queue approximation; a 185 ms worst declared TTFT floor; 20 ms TPOT; and about 8.8 GB of peak KV state. It derives latency floors from service capacity and peak concurrency rather than trusting inconsistent scheduler fields.

This is not a discrete-event simulation, latency distribution, device benchmark, or production SLO. It ignores arrival correlation, kernel shape, allocator fragmentation, preemption cost, prefix-cache hits, speculative decoding, and hardware contention. The arithmetic can reject an impossible or over-budget plan; a passing plan still needs trace replay, load testing, and staged production evidence.

Choose the first batching control to move

Inspect an illustrative prefill/decode mix, utilization, queue delay, TTFT, KV demand, and fairness bound. Predict which capacity boundary fails first without running a scheduler.

Choose a scheduler action from queue evidence

Connect prefill work, decode cadence, admission, priority, and KV headroom. Predict the bounded scheduling change that addresses the measured failure without guessing from average throughput.

Scheduler trace

Long prefills block active decodesA few large prompts occupy the scheduler while interactive token latency spikes.Finished requests leave idle batch slotsMemory is healthy, but new work waits for the slowest sequence in each fixed batch.Bulk generation starves interactive trafficAggregate throughput is high while a small latency-sensitive class misses its queue SLO.Admission outruns KV capacityThroughput rises until paging churn and allocation retries destabilize every request class.

Requests, capacities, timings, and policies are synthetic. The lab changes no live scheduler or traffic assignment.

Batching-policy evidence
Signal	Operating constraint	Observed evidence
Prefill share	Below 45% per scheduling window	82% during spikes
Decode inter-token p99	At most 80 ms	241 ms
Queue depth	Below 96 requests	38 requests
HBM headroom	At least 10%	19%

Illustrative measurements only. The recommended action stays hidden until you check a prediction.

Which scheduler action addresses this failure?

Use continuous admission at the current boundsChunk or isolate long prefillsReserve capacity for latency-sensitive trafficCap admission until memory headroom returns

Choose an action before checking the operating contract.

Operate per-class queues and resource lifetimes

Instrument arrival, admission, queue, prefill start and finish, first token, every decode iteration or bounded aggregate, completion, cancellation, eviction, preemption, and KV release with model and scheduler versions. Report distributions by request class, tenant, priority, prompt and output bucket, cache hit, fallback, and device pool. Measure fairness over time rather than assuming a priority cap enforces it.

Alert on oldest queue age, per-class TTFT and TPOT, active slots, token budgets, KV allocation and fragmentation, preemption, cancellation lag, and admission rejection.
Load-test bursts, correlated long prompts, long outputs, disconnects, stop sequences, mixed priorities, tenant skew, dependency slowdown, device loss, and recovery.
Propagate backpressure to gateways and clients with retry budgets and jitter; a rejected request that retries immediately can amplify overload.
Canary scheduler changes with stable assignment and rollback, and retain the prior policy until delayed tail and fairness evidence is complete.

Operate at three altitudes

Production lens

— Measure queue, TTFT, TPOT, completion, cancellation lag, token work, active sequences, KV allocation and fragmentation, preemption, fairness, admission, rejection, and fallback by class and tenant.
— Derive admission from measured service curves and peak memory under representative mixtures, keep failover and burst headroom, and propagate bounded backpressure upstream.
— Version and canary scheduler, model, precision, kernels, token limits, priorities, and paging policy together; preserve a tested rollback and trace cohort attribution.

Staff lens

— Own batching as a contract across product SLOs, gateway admission, scheduler fairness, model and kernel service curves, KV memory, tenant policy, and client retry behavior.
— Require capacity reviews to show distributions and adversarial mixtures, not a single requests-per-second number that erases token shape and resource lifetime.

Interview defense

Throughput improved after enabling continuous batching, but streaming users see periodic token stalls when long prompts arrive. How do you fix it?

I would separate prefill and decode demand by request class and correlate stalls with iteration composition, queue age, prompt chunks, active sequences, KV state, preemption, and exact scheduler version. A long prefill is likely monopolizing iterations, so I would test chunked prefill or an explicit prefill budget that guarantees decode progress, then quantify the efficiency and TTFT trade-off. Admission must reserve token, active-slot, and KV headroom, and fairness needs a measured bound across priorities and tenants. I would replay representative traces and adversarial bursts, validate TTFT and TPOT distributions rather than averages, canary the policy with stable assignment, and preserve rollback. If utilization is near the safe limit, I would reject or degrade work instead of tuning the queue indefinitely.

Expect the interviewer to press on

— Why does requests per second hide batching capacity?
— How can chunked prefill improve TPOT but hurt another metric?
— What must cancellation reclaim and how quickly?

Misconceptions to remove

“Continuous batching improves throughput without changing semantics.”

Scheduling changes queueing, token cadence, priorities, cancellation, preemption, memory lifetime, and which work is rejected or delayed; these are user-visible product semantics.

“Low average utilization means the service has capacity.”

Bursts, long-tail token shapes, separate prefill or decode saturation, KV exhaustion, tenant skew, and fragmentation can violate tail SLOs despite a low average.

“Paged KV memory eliminates cache capacity problems.”

Paging improves allocation flexibility and reduces some waste, but physical memory, metadata, internal fragmentation, ownership, eviction, and transfer costs remain finite.

Check your model

1. Why model prefill and decode capacity separately?

They have different parallelism, latency effects, token cadence, and memory lifetimes; one partition can saturate while aggregate token utilization looks acceptable.

2. What does a chunked-prefill limit protect?

It bounds how much prefill work can occupy an iteration so active decode sequences can make progress, at the cost of more chunks and possible overhead or TTFT change.

3. Why is a fluid queue estimate insufficient for an SLO?

Real arrivals and service are bursty, correlated, shape-dependent, stateful, and scheduled; tail distributions, memory, preemption, and failures require trace replay, load tests, and measured production evidence.

Prove the mechanism

Extend the artifact with a third background class, explicit tenant shares, and cancellation lag. Prove overload rejects or degrades the background class before interactive TPOT or KV limits fail.

Add a production constraint

Design and test a serving policy for chat, batch summarization, and agent traffic. Include measured service curves, prefill chunks, decode fairness, priorities, tenant quotas, prefix reuse, paging, preemption, speculative decoding, cancellation, backpressure, failures, canary, and rollback.

Artifact: Continuous batching capacity model

courses/ai-engineering/reference-impl/continuous_batching/batching_capacity_model.py

Download reference implementation

Primary references and next links

References

1. Orca: A Distributed Serving System for Transformer-Based Generative Models
Yu et al.. Primary OSDI research on iteration-level scheduling for distributed generative-model serving.
2. Efficient Memory Management for Large Language Model Serving with PagedAttention
Kwon et al.. Primary vLLM research on paged KV-cache management and high-throughput LLM serving.
3. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
Agrawal et al.. Primary research on chunked prefills and scheduling trade-offs between serving throughput and latency.
4. Triton Inference Server: Models and Schedulers
NVIDIA. Official serving guidance on dynamic batching, queue policy, priorities, and timeout controls.

Continue through the graph

The KV Cache Capacity Plan →
Translate active sequence shapes into KV bytes, paging, and concurrency limits.
The Accelerator Memory Hierarchy →
Connect scheduler token work and KV traffic to device and interconnect limits.

Glossary: continuous batching · iteration-level scheduling · prefill · decode · time to first token · time per output token · chunked prefill · KV paging · admission control · backpressure · starvation