Two phases, one shared batch

An LLM server runs two very different workloads on the same hardware. Prefill ingests a whole prompt of L tokens in one dense, parallel forward pass — a big, compute-bound GEMM over [L, d]. Decode generates one token at a time, a skinny [1, d] matrix-vector product per running request, and is memory-bandwidth-bound. A modern server batches many requests together to keep the device busy, so at any instant the batch contains a mix: some sequences are still decoding their reply, and occasionally a new request arrives that must be prefilled.

The trouble is that these two jobs fight over the same iteration. A decode step for a batch of B requests touches B new tokens. A prefill of a long prompt touches L tokens — possibly thousands at once. When the scheduler tries to run that prefill as a single unit, it produces one enormous iteration whose duration is set by L, not by B. Everything else in the batch is held hostage until it finishes.

Advertisement

The stall: head-of-line blocking

Concretely, imagine ten users mid-reply, each expecting a fresh token roughly every 30 ms — a smooth inter-token latency (ITL). Now an eleventh user pastes a 6,000-token document. A prefill-first scheduler runs that prefill in one iteration that might take 300 ms. For that whole window the ten streaming users get nothing: their next token is stuck behind the giant prefill. This is classic head-of-line blocking, and it shows up as an ugly ITL spike — the stream freezes, then lurches.

You cannot fix this by simply prioritizing decodes and deferring the prefill either: then the new user’s time-to-first-token (TTFT) balloons while they wait for a gap in decoding. The two objectives — low TTFT for arrivals and low, steady ITL for streams — are in direct tension whenever a prefill is large enough to dominate an iteration. Chunking is what lets you serve both at once instead of trading one for the other.

Advertisement

The core idea: split the prompt

Chunked prefill breaks the atomic assumption. Instead of processing all L prompt tokens in one forward pass, it slices the prompt into chunks of size C and feeds one chunk per iteration:

n_chunks = ceil(L / C)

  chunk 1:  tokens [0   .. C)      -> partial forward pass
  chunk 2:  tokens [C   .. 2C)     -> partial forward pass
  ...
  chunk k:  tokens [(k-1)C .. kC)  -> the new tokens attend to
                                       ALL previous tokens via KV cache

Each chunk runs the full stack of layers, but only over its C new positions. Crucially, the keys and values of earlier chunks are already sitting in the KV cache, so chunk k’s tokens still attend to the entire prefix [0, kC) — there is no loss of context or accuracy. The first token is emitted only after the last chunk completes; chunking changes the schedule of the prefill work, not its result.

Piggybacking decode onto each chunk

Splitting the prompt is only half the trick. The real payoff comes from what you do with the leftover capacity of each iteration. A prefill chunk of C tokens is small; the batch can afford to process more tokens in the same step. So the scheduler co-schedules the chunk together with the decode steps of every other running request — each contributes its one new token — forming a single fused batch:

iteration tokens = C (one prefill chunk)
                 + D (one decode token per running request)

This is the Sarathi-Serve insight (Agrawal et al., 2023): because decode is memory-bound and prefill is compute-bound, they use different parts of the hardware, and fusing them into one iteration is nearly free. The decodes ride along on a pass that had to load the weights anyway, raising the arithmetic intensity of an otherwise wasteful decode-only step. Nobody stalls: the ten streaming users keep getting a token every iteration, and the long prompt advances one chunk at a time in the background.

The token budget that keeps iterations uniform

The scheduler’s knob is a fixed per-iteration token budget B — the maximum number of tokens any single iteration may process. Each step first admits the mandatory decode tokens (one per running request, D of them), then fills the remaining room with a prefill chunk:

C = B - D            (chunk size adapts to the decode load)

  every iteration processes ~B tokens
  =>  every iteration costs ~the same wall-clock time
  =>  ITL is smooth and predictable

Because the total token count per step is clamped near B, the iteration time barely varies whether or not a prefill is in flight. When many requests are decoding, D is large and the prefill chunk shrinks to fit; when the batch is quiet, a bigger chunk slides in and prefill races ahead. This adaptive C = B - D is what converts a bursty, spiky workload into a stream of near-identical iterations — the whole point of the exercise.