The pass: the maître d' who builds every round — vLLM's scheduler step

· By José Manuel Román
Contents

Part of the under the engine series. Earlier posts looked at the silicon that runs the kernels (SMs and CUDA graphs) and at loading the weights (from disk to HBM). This one goes up a floor: who decides what runs in each forward. Before the GPU launches a single kernel, someone has had to build this round’s order. That someone is the scheduler, and it is the heart of continuous batching.

TL;DR

An LLM server does not serve one whole request and then the next: it advances every live request at once, a little on each engine iteration. The piece that decides how far each one advances in each step is the scheduler, and its output is deceptively simple: a dictionary {req_id: number of tokens} that the model runner turns into a single forward on the GPU. vLLM V1’s most important decision was to erase the distinction between prefill and decode: for the scheduler, a prompt token and a freshly generated token are the same thing, tokens that need processing, and that is why it can put a 4000-token prompt in the same batch as 200 one-token decodes. There are four pieces: the token budget (max_num_batched_tokens), a fixed-size tray filled every round; chunked prefill, which splits a huge prompt into chunks so it does not hog the tray and blow up everyone else’s latency; the two queues (waiting, in arrival order, and running); and preemption, because when the KV cache runs out somebody has to get off the train. This post explains the loop, the arithmetic of the budget and of concurrency, the 10 knobs and the headline trap: raising the budget improves throughput but worsens ITL (inter-token latency), and almost nobody measures both at once. On the generic 4×H100 SXM cluster.

Where you are: the pass, before the kitchen starts

Picture the pass of a restaurant with a busy dining room. There is no one cook per customer; there is a shared kitchen and a maître d’ who, every few seconds, looks at all the open orders and builds a tray to send to the stoves. That tray holds, say, 8000 “units of work”. The maître d’ decides what goes in: tables already eating (requests in decode) get one more dish each; new tables that have just ordered (requests in prefill, with their whole prompt still to process) get as much of their order as fits in whatever is left of the tray. The tray goes out, the kitchen executes it in one go, and it starts again. Hundreds of times per second.

That maître d’ is the scheduler. The kitchen is the GPU running a forward pass. And the house rule is that the kitchen never stops to wait for a single table: if a new order is enormous (a 30,000-token prompt), it is not sent whole in one go blocking everyone else, it is sent in chunks. That is, in one sentence, the whole mechanics of vLLM’s scheduler.

The engine loop: one dictionary per iteration

The inference engine is a very short loop. On each pass:

  1. The scheduler looks at the queues and produces a decision.
  2. The model runner runs a forward with that batch on the GPU.
  3. The sampler draws one new token for each active sequence.
  4. State is updated (KV cache, positions, finished requests) and it goes back to 1.

The surprising part is the shape of the decision in step 1. In vLLM V1 it is not a complex structure with phases: it is literally a dictionary

$$\text{schedule} = \{\, \text{req id} \rightarrow n_\text{tokens} \,\}$$

that says, for each request entering this round, how many tokens of it get processed. For a request that is generating text, n_tokens = 1 (one autoregressive step). For a new request, n_tokens can be the entire length of its prompt. And it can be anything in between, a chunk of prompt, under chunked prefill, prefix caching or speculative decoding (vLLM V1 docs).

Scheduler{req_id: n_tokens}Model runner1 forward (GPU)Sampler+1 token / seqUpdateKV, positionsone iteration = one step (ms order on H100)

That the decision fits in a {id: number} dictionary is not a neat implementation detail: it is why continuous batching works. Because the scheduler does not think in “phases” but in “how many tokens for each”, it can mix requests at any point of their life in the same forward. The GPU receives a single heterogeneous token tensor and processes it in one go.

The death of the prefill/decode distinction

This is the idea that costs the most effort and matters the most. In the first LLM server architectures, a request lived in two separate phases: first prefill (process the whole prompt and fill the KV cache), then decode (generate token by token). The scheduler had to choreograph the move from one phase to the other, and mixing them was hard.

vLLM V1 removed the distinction (V1 design). The scheduler treats prompt tokens and generated tokens uniformly: they are all tokens the model has to process in a forward. The practical consequence is enormous. A 4000-token prompt and a sequence that has generated 800 tokens and needs one more are, to the scheduler, “4000 tokens of request A” and “1 token of request B”. They fit together on the same tray. There is no phase choreography, just a budget to hand out.

This unlocks the pattern that really pays: mixing prefill and decode in every step. Prefill is compute-bound work (a lot of matrix to multiply); decode is memory-bound (little compute, a lot of KV to move). Mixing them in the same batch fills the gaps: while the GPU is busy with the heavy prefill, it advances the light decodes “for free”. It is the same efficiency principle as continuous batching, taken to its cleanest form.

The token budget: the fixed-size tray

The tray has a size: max_num_batched_tokens. It is the maximum number of tokens the scheduler can put in a single step (vLLM optimisation). The policy, with chunked prefill on (it always is in V1), is clear:

  1. Decodes first. Room is reserved for one token per request in the running queue. They are cheap, and they are diners already eating: they are not left waiting.
  2. What is left goes to prefills. With the remaining budget, prompt tokens from waiting requests are added, in arrival order (FCFS), split into chunks if needed.

An example with numbers. Budget max_num_batched_tokens = 8192, and at this instant there are 200 requests generating:

$$\text{decode} = 200 \times 1 = 200 \text{ tokens}$$ $$\text{free budget} = 8192 - 200 = 7992 \text{ tokens for prefill}$$

If a new request arrives with a 4000-token prompt, it fits whole in this step (4000 < 7992) and 3992 are left for another. If one arrives with 30,000 tokens, it does not fit: the scheduler sends it a 7992-token chunk this step, and the remaining 22,008 in later steps. That is chunked prefill.

Tray: max_num_batched_tokens = 8192 tokens/step200 decode7992 for prefill (a 4000-token prompt fits whole; a 30000-token one goes in chunks)Decode first (diners eating) · prefill fills the rest (FCFS) · if it does not fit, it is chunked

The budget matters because it fixes how many forwards are needed to swallow a prompt. A 30,000-token prompt with an 8192 tray takes 4 steps in prefill alone before it emits its first token. With a 2048 tray it takes 15 steps, but each of those steps leaves more room for other people’s decodes, so the other diners feel the jam less.

The two queues and preemption: when someone gets off the train

The scheduler handles two queues. The waiting queue holds requests that have not started yet (their prompt has not been processed), served in arrival order, FCFS by default, though there is a priority policy. The running queue holds those already alive and generating (vLLM scheduling).

There is a second budget, harder than the token one: the KV cache. Every live token occupies KV blocks in HBM, and they are finite (gpu_memory_utilization fixes them). When the scheduler wants to advance the running requests but there are no free blocks for the next token’s KV, someone has to get off: that is preemption.

vLLM V1 preempts by RECOMPUTE by default, not by SWAP (V1 guide). The difference:

  • SWAP: copy the victim’s KV to host RAM and bring it back later. It moves gigabytes across PCIe (see the PCIe and P2P post).
  • RECOMPUTE: throw the victim’s KV away and, when there is room again, redo its prefill from scratch. It sounds expensive, but in the V1 architecture it works out cheaper than swapping, because prefill is work the GPU does very fast and you save the round trip across the bus.

The victim is usually the newest request in the running queue (so as not to penalise whoever has been waiting longest for their answer). The danger is thrashing: admit too many requests at once and the system enters a preempt-recompute-preempt cycle that drives throughput into the floor. That is why the second ceiling exists.

The arithmetic that matters: concurrency and the budget trade-off

How many requests fit at once. The real concurrency limit is not max_num_seqs (the nominal ceiling on simultaneous sequences); it is usually the KV cache. If a node has $B$ free KV blocks, each block holds $b$ tokens (16 by default), and each request occupies $L$ context tokens on average, the maximum sustainable concurrency is:

$$N_\text{max} \approx \frac{B \cdot b}{L}$$

Take a 70B model in FP16 on 4×H100 SXM (320 GB), with the bulk of HBM in weights and, say, ~120 GB free for KV. With a KV of ~0.3 MB/token (an order-of-magnitude figure, it depends on layers and heads), that is ~400,000 KV tokens. With average contexts of 4000 tokens:

$$N_\text{max} \approx \frac{400000}{4000} = 100 \text{ concurrent requests}$$

Raising max_num_seqs to 400 does not give you 400 concurrent: it gives you preemption and thrashing as soon as contexts grow. The KV rules.

The budget trade-off. Raising max_num_batched_tokens puts more work in each forward, so fewer forwards for the same total work, and more throughput. But a large budget lets a huge prefill occupy almost the whole tray in one step, and that step takes longer, so everyone else’s decodes wait for that entire step, and ITL (inter-token latency) rises for everybody. The rule of thumb (vLLM optimisation):

BudgetEffectAt the cost of
Low (e.g. 2048)more interleaving, stable ITLless peak throughput
High (e.g. 16384)maximum throughputITL spikes when a large prefill arrives

There is no “correct” value: there is a point for your load. And you only find it by measuring throughput and ITL at the same time, which is exactly what almost nobody does.

The scheduler’s 10 knobs

#KnobWhat it controlsCost if you overdo it
1max_num_batched_tokenstray size per stephigh ITL if too large
2max_num_seqsnominal concurrency ceilingpreemption if the KV falls short
3gpu_memory_utilizationKV blocks availableOOM if too high
4chunked prefill (threshold)prompt chunk sizechunking overhead if too fine
5policy (fcfs/priority)who gets served firststarvation of low priority
6preemption modeRECOMPUTE vs SWAPPCIe traffic / recompute
7enable_prefix_cachingreuse prefix KVlittle; almost always on
8max_model_lenmaximum context per requestpessimistic KV reservation
9CUDA graph sizesalign batch with bucketspadding / capture (see below)
10speculative tokensextra tokens per stepwasted work if acceptance drops

How it connects to the rest of the stack

With continuous batching. The scheduler is continuous batching turned into code. The batching post explains the what (advance every request at once); this one explains the how (the per-step token dictionary).

With the KV cache and the block manager. The second budget, the blocks, is managed by the PagedAttention block manager. The scheduler asks for blocks; if there are none, it preempts. The two pieces are coupled through memory.

With CUDA graphs. CUDA graphs are captured for specific batch sizes (buckets). The scheduler should produce batches whose size lands in those buckets to avoid padding; otherwise part of the graph’s benefit is lost.

With chunked prefill and the prefix cache. Chunking a prompt interacts with prefix caching: chunks that match an already cached prefix skip the compute, and the scheduler reflects that by lowering that request’s n_tokens.

With speculative decoding. Speculative decoding makes a step verify several tokens at once; the scheduler models it as n_tokens > 1 for a request in decode.

With disaggregated serving. In disaggregated prefill/decode there are two schedulers, one per pool, each with its own budget; the phase distinction that V1 erased inside an engine reappears between engines.

With autoscaling. The metrics that drive autoscaling with KEDA, waiting-queue length and preempted requests, come straight out of the scheduler’s state.

Traps and things that are not what they look like

“Raising max_num_batched_tokens always helps.” It improves throughput and worsens ITL. If you only look at tokens/s in a large-batch benchmark, you “confirm” that more is better; in interactive production, your users feel the stutter. Measure both metrics or you are not measuring.

“The engine does all the prefills first and then the decodes.” That is the old architecture’s intuition. In V1 there are no phases: each step mixes prefill and decode according to the budget. Reasoning with the phase model leads to wrong conclusions about why latency rises.

“More max_num_seqs = more throughput.” Only until the KV cache runs out. Past that, more nominal concurrency produces preemption, and cascading preemption (thrashing) lowers throughput. The real ceiling is the KV, not the parameter.

“RECOMPUTE is a waste, SWAP is better.” In V1, RECOMPUTE usually wins: prefill is extremely fast on GPU and SWAP puts a gigabyte-scale round trip across PCIe on the critical path. Switching to SWAP “to avoid recomputing” can make latency worse.

“The scheduler is the bottleneck.” Almost never. The decision is a dictionary built in microseconds; the cost of the round is the forward on the GPU, three orders of magnitude above. If your scheduling CPU shows up in the profiler, the problem is usually host-thread jitter (see NUMA and CPU isolation), not the scheduler logic.

Chunked prefill that is too fine. Tiny chunks make a large prompt take many steps and add fixed per-step overhead. Chunking is there to bound the ITL impact, not to pulverise the prompt.

Conclusion

All the power of a modern LLM server, swallowing hundreds of requests at once without any of them blocking the rest, rests on a decision that fits in a {request: how many tokens} dictionary, taken hundreds of times per second. The idea that made it possible was not a faster kernel or a bigger GPU: it was to stop thinking in phases. When a prompt token and a generated token are the same thing, the scheduler can fill every tray by mixing the heavy and the light, and the kitchen never stops. The rest is two budgets, tokens and KV blocks, and a rule for when the second runs out. The maître d’ does not cook; he only decides what goes to the stoves in each round. But that decision, repeated without pause, is what separates an idle GPU waiting for orders from a kitchen running flat out. And the uncomfortable lesson for whoever is tuning: throughput and latency meet in the budget, and optimising one blindly means worsening the other without noticing.

See also

References