Learn · LLM inference
Batching and scheduling: who runs in the next step
Prefill wants many tokens per step to keep the GPU’s matrix units busy. Decode produces one token per sequence per step and wants many sequences per step to share the weight read. Both are solved by batching. The part of the server that decides what goes into each step is the scheduler.
The idea
A GPU runs the model in steps (also iterations): one forward pass over whatever tokens were chosen, every 1 to 100 ms. The scheduler’s job is to fill each step well. Think of kube-scheduler with a millisecond cycle: every step it looks at the queue, the free KV memory and the token budget, and binds work to the next forward pass.
An everyday picture: a metro, not a tour bus.
| Tour bus (static batching) | Metro (continuous batching) | |
|---|---|---|
| Leaves when | it is full | every step, full or not |
| New passengers | wait for the next bus | board at the next stop |
| A passenger who is done | stays on until the last one is done | gets off at the next stop |
| Seats | one per passenger, sized for the longest trip | a fixed number of tokens per step, shared |
Where the analogy breaks. A prompt is a big group that may not fit one train: it boards in chunks over several steps. A decoding request takes one seat per step, every step, until it ends. And each passenger carries luggage that grows every step (its KV cache); when the racks are full, someone is put off the train (preemption).
The questions each part answers:
- Token budget (
max_num_batched_tokens): how much work fits in one step? Bigger means fewer steps for a prompt, but every step gets longer. - Sequence cap (
max_num_seqs): how many requests may share one step? - Free KV memory: does this request’s new KV fit? If not, it waits, or someone is evicted.
- Order: who goes first? vLLM puts running decodes first, so a decoding user never waits behind a whole long prompt.
- ArriveA request arrives with its prompt tokens and waits in the queue.
- AdmitBefore every step the scheduler checks the three limits: token budget left, sequence cap, free KV memory.
- RunEverything chosen runs in one forward pass: one token for each decoding request, a chunk of each prompt.
- Stream or loopEach request whose prompt is done gets one token, streamed to the user. If it is not finished, it is back in the next step as a decode.
Worked example: five requests, one step at a time
Five made-up requests and a toy budget of 16 tokens per step (real servers use thousands, such as 8,192). Each row shows arrival step, prompt and output length (10p/3o is 10 prompt tokens, 3 output tokens). The schedule is computed by a small simulator of vLLM’s rule: running decodes first, then prompts in arrival order, chunking the one that does not fit.
Continuous batching, budget 16
Step 1
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | ||||||
| B | P 4 ✓ | ||||||
| C | |||||||
| D | |||||||
| E | |||||||
| tokens used of 16 | 14 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
A's whole prompt (10), then B's whole prompt (4): 14 of 16 tokens.
Nothing is decoding yet, so the whole budget goes to prompts. Both prompts finish in this one step, and each gets its first output token from it.
Step 2
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | |||||
| B | P 4 ✓ | D 1 | |||||
| C | P 14 | ||||||
| D | |||||||
| E | |||||||
| tokens used of 16 | 14 | 16 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes A, B (2 tokens), then C chunk (14 of 24 left): 16 of 16 tokens.
C arrived. A and B now decode: one token each, scheduled first. The tokens left go to C, whose 24-token prompt does not fit: it is cut into a chunk. That is chunked prefill.
Step 3
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | D 1 | ||||
| B | P 4 ✓ | D 1 | D 1 | ||||
| C | P 14 | P 10 ✓ | |||||
| D | |||||||
| E | |||||||
| tokens used of 16 | 14 | 16 | 12 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes A, B (2 tokens), then C's last chunk (10, prompt done): 12 of 16 tokens. A produces its last token and leaves.
C finishes its prompt beside two decodes. A has all its output tokens and leaves at once; its KV blocks are freed for others.
Step 4
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | D 1 | ||||
| B | P 4 ✓ | D 1 | D 1 | D 1 | |||
| C | P 14 | P 10 ✓ | D 1 | ||||
| D | P 5 ✓ | ||||||
| E | |||||||
| tokens used of 16 | 14 | 16 | 12 | 7 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes B, C (2 tokens), then D's whole prompt (5): 7 of 16 tokens. C produces its last token and leaves.
D joins in the step after it arrives: no waiting for a batch to end. C needed only 2 output tokens, so it is already gone.
Step 5
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | D 1 | ||||
| B | P 4 ✓ | D 1 | D 1 | D 1 | D 1 | ||
| C | P 14 | P 10 ✓ | D 1 | ||||
| D | P 5 ✓ | D 1 | |||||
| E | P 3 ✓ | ||||||
| tokens used of 16 | 14 | 16 | 12 | 7 | 5 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes B, D (2 tokens), then E's whole prompt (3): 5 of 16 tokens.
E joins the same way. The step mixes two decodes and a whole prompt.
Step 6
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | D 1 | ||||
| B | P 4 ✓ | D 1 | D 1 | D 1 | D 1 | D 1 | |
| C | P 14 | P 10 ✓ | D 1 | ||||
| D | P 5 ✓ | D 1 | D 1 | ||||
| E | P 3 ✓ | D 1 | |||||
| tokens used of 16 | 14 | 16 | 12 | 7 | 5 | 3 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes B, D, E (3 tokens): 3 of 16 tokens. B and E produce their last tokens and leave.
Only decodes are left. B and E finish together.
Step 7
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A | P 10 ✓ | D 1 | D 1 | ||||
| B | P 4 ✓ | D 1 | D 1 | D 1 | D 1 | D 1 | |
| C | P 14 | P 10 ✓ | D 1 | ||||
| D | P 5 ✓ | D 1 | D 1 | D 1 | |||
| E | P 3 ✓ | D 1 | |||||
| tokens used of 16 | 14 | 16 | 12 | 7 | 5 | 3 | 1 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
Decodes D (1 token): 1 of 16 tokens. D produces its last token and leaves.
The last request runs alone. With no new arrivals the step is nearly empty: continuous batching cannot invent work.
Same requests, static batching
| request ↓ step → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | wait | 10+6 | 0+8 | wait | wait | wait | D 1 | D 1 | idle | idle | idle | ||||
| B | wait | wait | 4+4 | 0+16 | wait | wait | D 1 | D 1 | D 1 | D 1 | D 1 | ||||
| C | wait | wait | wait | P 16 | P 8 | D 1 | idle | idle | idle | idle | |||||
| D | wait | wait | wait | wait | wait | wait | wait | wait | P 5 | D 1 | D 1 | D 1 | |||
| E | wait | wait | wait | wait | wait | wait | wait | 3+2 | D 1 | idle | idle | ||||
| tokens used of 16 | 0 | 16 | 16 | 16 | 16 | 8 | 3 | 2 | 1 | 1 | 1 | 10 | 2 | 1 | 1 |
P n prefill chunk · P n ✓ prompt done, first token · D 1 decode · wait queued · n+m n tokens + m padding · idle slot held after finishing
The static server waits for a full group of 3 (step 1 is empty), pads A’s and B’s prompts to C’s 24 tokens, and holds every slot until the group’s longest output ends. D and E, which arrived at steps 4 and 5, start only at step 12.
- Steps to finish all
- 7 vs 15
- continuous vs static
- Mean latency
- 3.6 vs 9.2
- steps, arrival to last token
- Padding tokens
- 0 vs 36
- computed for nothing
- Idle slot-steps
- 0 vs 9
- finished, still holding a slot
The step that finishes a prompt also samples that request's first output token (✓). Hover a cell for details.
Both servers did the same useful work (58 tokens: every prompt token, plus every output token after the first). Continuous batching packs it into fewer steps because nobody waits for a batch boundary. This is the Orca idea (iteration-level scheduling, OSDI 2022), now standard in vLLM, SGLang and TensorRT-LLM. It depends on paged KV memory: requests of very different lengths share a step because each has its own block table, with no padding.
The rule, and the budget trade
vLLM treats every request the same way: it knows tokens and has computed KV for of them. A step gives it some of the remaining : one token for a request in decode, as many as fit for a prompt. Each step is limited by:
- Token budget:
max_num_batched_tokens, for example 8,192 tokens. - Sequence limit:
max_num_seqs. - KV memory: new tokens must fit in free (or evictable) KV blocks.
With chunked prefill on, vLLM fills a step with all running decodes first, then prefills with the leftover budget (optimization guide). The same rule at production scale:
- Step n60 decodes take 60 tokens. The remaining 8,132 go to the first chunk of prompt X.
- Step n+1One decoding request finished and left. 59 decodes, and 8,133 more tokens of X.
- Step n+2X’s last 3,735 tokens finish. Prompt Y (600 tokens) arrived and fits in the leftover budget, so it runs whole, at once.
The budget sets the trade-off between the two kinds of user. A small budget (the guide’s example is 2,048) keeps steps short, so decoding users get a better ITL (inter-token latency); a large one finishes prompts in fewer steps, so new users get a better TTFT (time to first token) and the GPU better throughput. The guide recommends budgets above 8,192 for throughput on large GPUs. Try it:
Toy model of an aggregated server (prefill and decode on one GPU), vLLM order: decodes first, then prompt chunks. Step time ≈ per step, an assumed model: a fixed overhead plus gpt-oss-120b's ~9 GFLOP per token at 30% of one MI355X's peak. It ignores that decode tokens also read their KV and that later chunks attend to more context, so real decode-heavy steps are slower.
Defaults: 10 requests per second, 50 ms each (illustrative). Little's law holds for long-run averages of any stable queue; it says nothing about bursts.
Head-of-line blocking: three requests, one queue
Take a prefill-only server with an 8,192-token budget. A 30,000-token prompt arrives; about 50 ms later two short prompts (200 and 800 tokens) arrive behind it.
- The long prompt takes whole steps. It needs four chunks: three full 8,192-token steps and a remainder of 5,424. First come, first served gives it the whole budget in steps 1–3.
- The short prompts wait. They need only a few milliseconds of compute, but there is no budget left for them until step 4.
- All three share the last step. Step 4 holds 5,424 + 200 + 800 = 6,424 tokens. The short requests’ forward passes end together with the long one’s.
The short requests wait for three full steps, a few hundred milliseconds, for work that alone needs a few tens. Chunking bounded each step, but it did not let them jump the queue. Mitigations are policy: a smaller budget, --long-prefill-token-threshold (caps a long prompt’s share of each step; off by default), --scheduling-policy priority, or separate replicas for long prompts. The same effect from the prefill side: Prefill.
Admission, waiting and preemption
- Queueing. Requests that do not fit wait. The default order is first-come-first-served;
--scheduling-policy prioritylets each request carry a priority. - Preemption. If running sequences grow and KV blocks run out, the scheduler evicts some (by default it frees their KV and later recomputes it). Victims see a pause;
vllm:num_preemptionscounts them. - Load signals.
vllm:num_requests_running,vllm:num_requests_waitingandvllm:num_requests_waiting_by_reasonshow the queue;vllm:request_queue_time_secondsshows how long requests waited.
Sizing with Little’s law
Little’s law links three long-run averages: . A replica receiving 10 requests per second that spends 50 ms on each has on average 0.5 requests in flight: busy about half the time, and most engine steps run a single request. Try other rates in the second calculator box above.
Averages hide bursts: the head-of-line example above can happen on a replica that is idle most of the time. Size for peak arrival rate and the latency target, not for the average.
Disaggregation is a scheduling decision
In an aggregated server every step mixes prefill chunks and decodes, and each hurts the other: a big chunk lengthens the step every decoding user waits for (the calculator’s ITL), and a big decode batch takes budget from prefills (its TTFT). DistServe and Splitwise showed that putting the two phases on separate machines removes that interference and lets each side be sized for its own target: TTFT for prefill, ITL for decode.
In a disaggregated server, prefill workers run no decodes, so their scheduler only fits prompts into the token budget, and the decode workers batch decodes on their own. A router picks a prefill worker and a decode worker per request; there need not be a fixed 1:1 mapping between them.
Routing across replicas
With many replicas, which replica gets a request matters as much as how each schedules:
- Least-loaded: spread queue depth evenly.
- Cache-aware: send a request where its prefix is already cached. When a large share of prompt tokens comes from cache, a routing change that breaks affinity multiplies prefill compute.
- Length-aware: keep very long prompts away from replicas serving latency-sensitive short ones (the cure for the head-of-line example).
Common misconceptions
- “Batch size is a fixed setting.” With continuous batching it changes every step; the settings are upper limits.
- “Bigger batches are always better.” They raise throughput but lengthen each step, which every user in it feels as ITL.
- “Chunked prefill fixes long prompts blocking short ones.” It stops one giant step; short requests can still wait behind the chunks, as in the example above.
Further reading
- vLLM optimization and tuning (chunked prefill, preemption)
- vLLM engine arguments (
max_num_batched_tokens,max_num_seqs,scheduling_policy,long_prefill_token_threshold) - Sarathi-Serve (chunked prefill and stall-free batching)
- DistServe · Splitwise (prefill/decode disaggregation)
- PagedAttention / vLLM
- vLLM metrics
- Little’s law