The scheduler: queues, fairness and admission control

The loop, and the five questions inside it

Continuous batching recast serving as a loop rather than a batch job: every iteration the engine forms a fresh batch from whichever sequences are resident. The training guide's continuous batching section explains why that loop exists and how it hides decode latency behind prefill; the scheduler is the policy that runs inside the loop, and it is where the latency tail is actually made. At each tick it answers five questions at once.

• Admission. Which requests from the waiting queue may occupy one of the max_num_seqs batch slots this iteration?
• Order. When more requests are admissible than fit, which ones go first?
• Preemption. When the KV pool is exhausted, which running sequence is evicted — and does it recompute its prefill or swap its blocks to host memory (Part 5)?
• Chunking. How is the per-iteration prefill token budget split between a long prompt being prefilled and the decode steps already in flight (Part 6)?
• Placement. In a disaggregated or replicated deployment, which worker sees the request at all (Part 13, Part 19)?

These are one policy expressed in five places. A scheduler that admits greedily but orders badly produces exactly the symptom this page is about: a median that looks healthy and a p99 that does not. The budget it is dividing is fixed by the arrival rate and the service time, which is where queueing theory enters. A recap of the prefill/decode split from the training guide is worth one line — decode is memory-bandwidth-bound at roughly 1–2 FLOPs/byte, prefill is compute-bound — and then the interesting part begins: a scheduler can only rearrange when that work happens, never how much of it exists.

Little's law is the invariant every scheduling choice trades against. If the arrival rate is 8 req/s and the SLO allows 1.5 s, then at most 12 requests may be in flight; admit a 13th and someone misses. Read it backwards and it turns queue length into a capacity estimate — the basis of the control signal in step 6.

The default, and its structural flaw

First-come, first-served is the default waiting-queue order in most engines, and it is genuinely fair in the queueing sense: no request can be delayed by a later arrival, so variance is low and nobody can game the queue. Its flaw only appears when job sizes are heavy-tailed, which for LLMs they are: prompt lengths are well modelled as log-normal with a coefficient of variation near 0.7, and agentic traces add 100K-token prompts next to 200-token chat turns (tools and agents).

Under FCFS one long prefill at the head blocks every short request behind it. That is head-of-line (HOL) blocking, and it is a pure ordering cost: a 4,000-token prompt at roughly 2,000 prefill tokens/s occupies the batch for about two seconds, during which a 120-token request behind it cannot start. Chunked prefill bounds the damage by splitting the long prefill into token chunks and interleaving them with decode, so the short request starts within a chunk rather than after the whole prompt — but chunking does not reorder the queue. The short request still waits behind however many long prefills were already admitted. Only reordering removes HOL blocking.

The magnitude of the ordering effect is visible in production traces: vLLM served agentic workloads with 3.8× higher throughput and 46× lower P50 TTFT than its baseline. Some of that is prefix-cache hits (Part 8), but a large share is simply keeping short requests from queueing behind long ones.

The theoretically optimal answer, and why it is dangerous

Shortest-job-first and its preemptive twin, shortest-remaining-processing-time, are the classic answer to HOL blocking. SRPT is provably optimal for mean response time on a single server, and SJF is optimal among non-preemptive disciplines under the same objective — these are old queueing-theory results, not LLM-specific. Both require knowing the service time before the job runs. For an LLM, the prefill length is known exactly (it is the prompt), which is why an engine can already order on it; the decode length is not, so length prediction means predicting the output.

Because the distribution is heavy-tailed, that optimality is narrow. SJF and SRPT buy their low median by stranding the long tail: in the bake-off below, oracle-SJF cuts p50 from about 1.9 s under FCFS to about 0.6 s, and simultaneously pushes p99 from about 4.2 s to about 12 s. The tail is exactly where the users who submitted long reasoning requests live (reasoning), and it is where an SLO is written. Optimising the mean and meeting a quantile are different objectives, and here they point in opposite directions.

Prediction is the practical obstacle. Output length is guessed from the prompt by a regression or classifier, and reasoning models that emit thousands of thinking tokens are the hardest case. The accuracy slider below perturbs the oracle: it preserves the exact multiset of job lengths and only changes how well the scheduler knows which request is which. At 80% accuracy the tail is already worse than the oracle's; at 0% the ordering is a random permutation of the same job lengths, the starvation count climbs, and p99 grows past 14 s even though the median stays flattering — the median is exactly the part a mis-ordered queue does not strand. Prediction error is not a rounding error — it is the whole policy.

What to do when the optimal policy is unfair

The failure mode of SJF and SRPT is starvation: a long request can be overtaken indefinitely because a fresh short request always looks better. The starvation counter in step 3 is the metric to watch, not the median. Aging fixes it by adding a request's accumulated wait to its effective priority so that it eventually wins the ordering decision — classic anti-starvation, and the reason FCFS with aging is a safe default when lengths cannot be predicted. The engine's own aging weight is coarse: it credits one unit of priority per 1,000 ms of wait, so the tier gap must be scaled to the SLO horizon or aging is either inert or a hard priority floor.

Production APIs rarely have one SLO. A two-tier scheme gives interactive traffic strict precedence and pushes batch work into the leftover capacity — the same economics that make batch inference cheap. Multi-SLO scheduling generalises this: rather than one queue, each class carries its own latency target, and the scheduler admits whichever request is furthest from meeting its target. Prefill and decode pull in opposite directions here. Admitting a long prefill helps that request's TTFT but spikes inter-token latency for everyone already decoding, so chunk size is itself a scheduling parameter (Part 3). When you tune these knobs, measure the SLO with the same rigour you would apply to model quality (evaluation).

Goodput versus offered load

Everything above assumes the queue is finite in policy but infinite in effect. Under overload that assumption is what kills you. Past capacity, a naive system keeps accepting work; queueing delay grows without bound, clients time out and retry, and the retries add load on top of the work already queued. Effective goodput — requests per second that actually meet their SLO — then collapses even though raw GPU throughput looks flat or slightly higher. This is congestion collapse, and it is a scheduling problem, not a capacity problem.

Admission control is the fix: bound the number of in-flight requests (a queue-depth cap, or max_num_seqs plus a waiting-queue limit) and shed at the edge with a 429 once the bound is hit, so the work you do admit finishes inside its SLO. The demo shows a modelled goodput curve: without shedding, goodput peaks a little above capacity and then falls as retries and timeouts consume the machine; with a shed threshold at capacity it stays flat. Shedding early looks wasteful — you reject work you could technically start — but the accepted work meets its target, which is the definition of goodput. A measured version of the same effect: the Mooncake deployment gained its throughput and TTFT improvements precisely because keeping queues short is worth more than keeping them busy.

What to measure, and what to scale on

Queue depth is the right control signal because Little's law relates it directly to the SLO. Given an arrival rate and a latency target, L = λW fixes how many requests may be in flight; anything above that is guaranteed to miss. A serving deployment should therefore publish the waiting-queue length, the running-batch size and KV-cache utilisation as first-class metrics, and autoscale on them rather than on GPU utilisation. A saturated decode server shows high memory-bandwidth utilisation and low SM occupancy while its queue grows, so utilisation hides the problem that queue length exposes (Part 19).

Queue depth also drives the internal decisions. The prefill token budget is chosen so the waiting queue drains at the SLO rate, and KV-block pressure is what triggers preemption in the first place (Part 5). Long-context requests make the signal noisy, because a single 100K-token prompt consumes many blocks and distorts per-request depth (Part 15); when the workload skews long, account in tokens, not requests. The same caveat applies at the model level: attention cost per token grows with context, so a head count that looks short in requests can be long in compute.

One GPU, many customers

Without per-tenant scheduling, a tenant that submits long prompts damages every other tenant sharing the replica — the noisy-neighbour effect. The demo below runs a short, interactive tenant B alongside a long-prompt batch tenant A under three regimes: global FCFS, tenant-aware priority, and full isolation. Under FCFS, B's p99 TTFT runs into seconds; give B precedence and it drops by an order of magnitude without touching the hardware. The mechanism is packet scheduling borrowed from networking: weighted fair queueing or deficit round-robin gives each tenant a share of the batch slot per iteration, and per-tenant token buckets cap how far ahead any tenant can get. LoRA serving adds a wrinkle — many tenants share one base model, so fairness is enforced on adapters and request queues, not on weights (Part 17).

Goodput-aware scheduling closes the loop. Instead of maximising tokens per second, the scheduler maximises the number of requests that meet both their TTFT and TPOT targets, and routes or sheds the rest. Disaggregated deployments make this explicit: separate prefill and decode pools, each scheduled against its own SLO, are how DistServe reports 7.4×/12.6× more goodput than a colocated baseline. The general rule is uncomfortable but simple — when you cannot serve everything well, decide who you are going to serve well, and encode that decision in the admission policy rather than discovering it in the p99.

Cheat sheet

Scheduling policies at a glance

Further reading

References

• Yu et al., “Orca: A Distributed Serving System for Transformer-Based Generative Models”, OSDI 2022 — iteration-level scheduling and continuous batching.
• Kwon et al., “Efficient Memory Management for Large Language Model Serving with PagedAttention”, SOSP 2023 — vLLM, paged KV and preemption.
• Agrawal et al., “Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve”, OSDI 2024 — chunked prefill and stall-free batching.
• Dean & Barroso, “The Tail at Scale”, Communications of the ACM 2013 — tail latency and queueing in large systems.
• Little, “A Proof for the Queuing Formula: L = λW”, Operations Research 1961 — the invariant behind queue-depth control.
• Demers, Keshav & Shenker, “Analysis and Simulation of a Fair Queueing Algorithm”, SIGCOMM 1989 — weighted fair queueing.
• Zhong et al., “DistServe: Disaggregating Prefill and Decoding for Goodput-optimized LLM Serving”, OSDI 2024 — the goodput framing used in step 7.

Terms used above are collected in the series glossary.