Learn · LLM inference

Batching and scheduling: who runs in the next step

Updated 10 Nov 2026 · 8 min read

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.
The scheduler loop
New requestprompt tokensWaiting queuefirst come, first servedRuns before every engine step. Decodes first, then prompt chunks until the token budget is used.Schedulerbudget · sequence cap · free KVOne forward passall chosen tokens togetherSampleone token per finished prompt ordecodeStreamed to the userarrivesadmit if it fitsthis step’s batchlogitstokennot finished: decode nextstep
  1. ArriveA request arrives with its prompt tokens and waits in the queue.
  2. AdmitBefore every step the scheduler checks the three limits: token budget left, sequence cap, free KV memory.
  3. RunEverything chosen runs in one forward pass: one token for each decoding request, a chunk of each prompt.
  4. 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.
One engine step. A request goes round this loop once per output token.

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 →1234567
A arr 1 · 10p/3oP 10 ✓
B arr 1 · 4p/6oP 4 ✓
C arr 2 · 24p/2o
D arr 4 · 5p/4o
E arr 5 · 3p/2o
tokens used of 1614

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1
B arr 1 · 4p/6oP 4 ✓D 1
C arr 2 · 24p/2oP 14
D arr 4 · 5p/4o
E arr 5 · 3p/2o
tokens used of 161416

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1D 1
B arr 1 · 4p/6oP 4 ✓D 1D 1
C arr 2 · 24p/2oP 14P 10 ✓
D arr 4 · 5p/4o
E arr 5 · 3p/2o
tokens used of 16141612

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1D 1
B arr 1 · 4p/6oP 4 ✓D 1D 1D 1
C arr 2 · 24p/2oP 14P 10 ✓D 1
D arr 4 · 5p/4oP 5 ✓
E arr 5 · 3p/2o
tokens used of 161416127

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1D 1
B arr 1 · 4p/6oP 4 ✓D 1D 1D 1D 1
C arr 2 · 24p/2oP 14P 10 ✓D 1
D arr 4 · 5p/4oP 5 ✓D 1
E arr 5 · 3p/2oP 3 ✓
tokens used of 1614161275

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1D 1
B arr 1 · 4p/6oP 4 ✓D 1D 1D 1D 1D 1
C arr 2 · 24p/2oP 14P 10 ✓D 1
D arr 4 · 5p/4oP 5 ✓D 1D 1
E arr 5 · 3p/2oP 3 ✓D 1
tokens used of 16141612753

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 →1234567
A arr 1 · 10p/3oP 10 ✓D 1D 1
B arr 1 · 4p/6oP 4 ✓D 1D 1D 1D 1D 1
C arr 2 · 24p/2oP 14P 10 ✓D 1
D arr 4 · 5p/4oP 5 ✓D 1D 1D 1
E arr 5 · 3p/2oP 3 ✓D 1
tokens used of 161416127531

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

Static batching: groups of 3, prompts padded to the group's longest
request ↓ step →123456789101112131415
A arr 1 · 10p/3owait10+60+8waitwaitwaitD 1D 1idleidleidle
B arr 1 · 4p/6owaitwait4+40+16waitwaitD 1D 1D 1D 1D 1
C arr 2 · 24p/2owaitwaitwaitP 16P 8D 1idleidleidleidle
D arr 4 · 5p/4owaitwaitwaitwaitwaitwaitwaitwaitP 5D 1D 1D 1
E arr 5 · 3p/2owaitwaitwaitwaitwaitwaitwait3+2D 1idleidle
tokens used of 1601616161683211110211

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 NN tokens and has computed KV for CC of them. A step gives it some of the remaining N−CN - C: one token for a request in decode, as many as fit for a prompt. Each step is limited by:

  1. Token budget: max_num_batched_tokens, for example 8,192 tokens.
  2. Sequence limit: max_num_seqs.
  3. 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:

Three consecutive steps in an aggregated server
STEP N+2STEP N+1STEP N60 decodes60 tokensPrompt X, chunk 18,132 of 20,000 tokens59 decodesone request finished and leftPrompt X, chunk 28,133 tokens59 decodes59 tokensPrompt X, last chunk3,735 tokensPrompt Y, whole600 tokens, joins at once
  1. Step n60 decodes take 60 tokens. The remaining 8,132 go to the first chunk of prompt X.
  2. Step n+1One decoding request finished and left. 59 decodes, and 8,133 more tokens of X.
  3. 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.
Budget 8,192 tokens. Decodes go first; a 20,000-token prompt is spread over three steps; a new request joins as soon as there is budget.

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:

Token budget: what decoding users and a new long prompt each feel
Prompt tokens per step
Steps to finish the prompt
Step time = ITL for decoders, while the prompt runs
ITL with no prompt in the step
Prefill part of the prompt's TTFT

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.

Little's law: requests in flight = arrival rate × time in system
Requests in flight, on average
If one runs at a time: share of time busy

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.

  1. 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.
  2. The short prompts wait. They need only a few milliseconds of compute, but there is no budget left for them until step 4.
  3. 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 priority lets 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_preemptions counts them.
  • Load signals. vllm:num_requests_running, vllm:num_requests_waiting and vllm:num_requests_waiting_by_reason show the queue; vllm:request_queue_time_seconds shows how long requests waited.

Sizing with Little’s law

Little’s law links three long-run averages: requests in the system=arrival rate×time in the system\text{requests in the system} = \text{arrival rate} \times \text{time in the system}. 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