LLM Inference #8: Chunked Prefill
Three users are streaming answers. A fourth sends a long prompt, and their streams pause. How chunked prefill shares each iteration, what the token budget buys, and how vLLM implements it.
Three users are halfway through their answers. Tokens arrive steadily. A fourth user sends a 4,096-token document, and the streams pause while the GPU processes it.
The fourth request has no reusable prefix. The prefix cache cannot help. There is room for its KV, so the paged allocator cannot help either. The problem is how much work the scheduler puts into one iteration.
Chunked prefill splits that work across iterations. The new user waits through several chunks, while the existing users keep getting turns to decode.
One long prompt holds up everyone else
Prefill and decode ask the GPU to do different amounts of work. A decode request usually contributes one new input token per iteration. A prefill request can contribute thousands.
With continuous batching, those requests can share an iteration. If the scheduler includes the whole new prompt, the iteration has to process it before returning its results. The users already streaming see a longer gap between tokens.
On a narrow screen, scroll the diagrams sideways.
You could let the running requests finish before admitting the prompt. That protects their streams, but a long answer can leave the new user waiting a long time. Giving the prompt its own full iteration has the opposite problem. The new user makes progress while everyone else waits.
The scheduler needs a way to admit some prompt work without admitting all of it.
Give the prompt part of each iteration
Instead of processing 4,096 prompt tokens in one iteration, process a portion, keep its KV, and continue later. Put the existing decode requests in those iterations too.
This is chunked prefill. Sarathi-Serve describes how to combine prefill chunks with ongoing decodes to control the throughput and latency tradeoff.
There is a throughput reason to mix them too. Prefill’s many input tokens give the GPU substantial matrix work. Small decode batches spend more of their time moving weights and KV from memory. A mixed batch can use the GPU better than separate turns for each, though the gain depends on the workload.
The GPU still does prefill work. Each mixed iteration can take longer than a decode-only iteration. Splitting a prompt gives the scheduler more points at which it can return decode results. It does not make the prompt’s computation disappear.
The new request produces its first answer token only after the final prefill chunk. Returning between chunks helps the users already decoding.
A 1,024-token budget, worked through
Suppose one iteration can schedule at most 1,024 input tokens. Requests A, B, and C are already decoding. Each needs one token processed to produce its next token. Request D arrives with the 4,096-token prompt.
Give A, B, and C one token each. That leaves 1,021 tokens for D.
Keep that order and assume A, B, and C continue streaming. No request finishes or arrives. There are no prefix-cache hits, and there is enough KV space. This example also leaves speculative decoding and the extra per-request chunk cap disabled.
| Iteration | A, B, C input tokens | D prompt tokens | D prompt tokens processed so far |
|---|---|---|---|
| 1 | 3 | 1,021 | 1,021 |
| 2 | 3 | 1,021 | 2,042 |
| 3 | 3 | 1,021 | 3,063 |
| 4 | 3 | 1,021 | 4,084 |
| 5 | 3 | 12 | 4,096 |
A, B, and C each get a decode result in every iteration. D reaches the end of its prompt in iteration 5 and can produce its first output token. In the next iteration, D becomes another ordinary one-token decode request.
The budget counts input positions processed in this iteration. It does not count the entire stored context, and it does not count output tokens returned to clients. The first iteration processes 1,024 positions but returns only three answer tokens.
The next chunk still sees the earlier tokens
Splitting a prompt does not split it into independent documents. The later tokens still need the earlier context.
After D’s first chunk, the runtime retains the KV for positions 0 through 1,020. The next chunk processes positions 1,021 through 2,041. Its attention reads the earlier KV as well as the allowed positions inside its own chunk.
Causal attention makes the split possible. Earlier positions never need information from later ones. Keeping their KV lets the runtime continue without recomputing them.
There is no smaller context window here. At the end, D still has KV for the full prompt. Chunking changes when the runtime computes those positions. Different kernel shapes can introduce floating-point differences, but the intended attention calculation and context stay the same.
Smaller chunks trade prompt progress for shorter interruptions
A smaller token budget limits how much prefill can share an iteration with decode. Existing streams usually get shorter interruptions, while the new prompt needs more iterations before its first token.
A larger budget lets the prompt make more progress per turn. It also allows more work into an iteration that existing streams must wait for. Larger chunks can use the GPU more efficiently, so cutting the budget as far as possible is rarely a good goal.
Token count is only a rough control on iteration time. Processing 1,000 new positions after a long context can cost more than processing the first 1,000 positions. Model size, batch composition, and attention kernels also matter. A 1,024-token budget is not a promise to finish within a fixed number of milliseconds.
When comparing budgets, measure time to first token for new requests and the gaps between tokens for existing streams. Include tail latency under load. An average throughput number can hide the pauses this feature is meant to reduce.
Follow one chunk through vLLM
The walkthrough below uses vLLM V1 at revision a16bfee. The links point to that revision rather than a moving branch. It follows ordinary text generation with full attention and no speculative decoding.
The scheduler counts how much input remains
Request holds the prompt, output tokens, and num_computed_tokens. For the ordinary path, the gap between the known tokens and that counter is the work still to schedule.
For a new 4,096-token prompt, the gap starts at 4,096. After its first 1,021 positions, the gap is 3,075. During ordinary decode, the most recently sampled token has no KV yet, so the gap is one.
The same accounting can describe both phases. Chunked prefill needs no separate job for each chunk.
The iteration has a budget, not a fixed chunk size
SchedulerConfig defines max_num_batched_tokens. The scheduler’s max_num_scheduled_tokens defaults to that value. With speculation disabled and no separate override, the two budgets match.
schedule() visits running requests before admitting waiting requests. It limits each request’s work to the budget still available. That is where our 1,021-token chunk comes from. The scheduler spends three tokens on A, B, and C, then gives D what remains.
When chunking is disabled, the waiting-request path does not admit a prompt whose required work exceeds the remaining budget. With chunking enabled, it can admit the portion that fits.
The line that takes that portion is:
1
num_new_tokens = min(num_new_tokens, request_token_budget)
There is an optional long_prefill_token_threshold. It can cap one request’s contribution when several requests compete. Zero disables that extra cap. Chunk sizes can therefore change from iteration to iteration as the other requests change.
Running does not always mean decoding
A partly prefilled request stays in the running list. On the next iteration it can compete for tokens alongside decoders.
The optimization guide describes the policy as prioritizing decode. The running-request loop in this revision follows list order and can encounter a partial prefill before a decoder. It does not first collect every decoder into a separate group.
Our example puts A, B, and C ahead of D and keeps that order. A different order or a crowded budget can produce a different schedule. Chunked prefill alone is not a guarantee that every stream advances on every iteration.
KV allocation and model execution finish the job
Before admitting D, the scheduler asks allocate_slots for its KV space. scheduler_reserve_full_isl defaults to true in this revision. Admission checks whether the full input can fit, even though this iteration processes only a chunk. Splitting the compute does not remove the memory requirement.
SchedulerOutput carries the token counts and request data to the worker. For our first iteration, the counts are:
1
2
3
4
A: 1
B: 1
C: 1
D: 1021
The GPU runner’s prepare_inputs builds the batch’s token positions and sequence lengths. prepare_attn supplies the attention metadata, including the block tables. D’s second chunk uses a longer sequence length than its number of new tokens, because its earlier KV still belongs to the context.
_update_after_schedule advances the counter by the assigned count:
1
request.num_computed_tokens += num_scheduled_token
The scheduler records this progress before GPU completion so it can prepare later work. It also tracks in-flight tokens. Treat this as scheduled progress when reading the asynchronous path.
After four 1,021-token chunks, D’s counter reaches 4,084. The next turn schedules the last 12 positions. The scheduler gets chunked prefill from token counts, retained KV, and a budget applied repeatedly.
Summary
- A whole long prefill can stretch one iteration and interrupt existing token streams.
- Chunked prefill spreads the prompt across iterations, which can also carry decode work.
- Later chunks attend to earlier KV. They continue the same prompt with the same context.
- Smaller budgets usually reduce interruptions but delay prompt completion. A token budget does not set a fixed time limit.
- vLLM tracks each request’s progress and assigns work from the remaining budget. Partial prefills remain running requests, so list order matters.
- Chunking changes the compute schedule. The full prompt still needs KV space.
References
- Agrawal et al., Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve, OSDI 2024. Paper and talk
- vLLM V1 source at revision
a16bfee, linked beside the symbols used above - vLLM optimization guide, for the documented policy and tuning discussion