Explainer
A long prompt should not stall everyone else
Sixteen people are mid-reply when someone pastes a 16K-token document. A scheduler that runs that prompt’s prefill as its own step freezes all sixteen streams for nearly two seconds. Cut the prompt into chunks and run each chunk inside a decode step, and nobody notices it arrived. Below, the same arrival handled both ways on one clock.
Prefill and decode are opposite kinds of work. A prefill step is compute-bound: thousands of tokens of arithmetic against one read of the weights. A decode step is memory-bound: one token per request, the same read of the weights, and the tensor cores mostly idle. Put them in the same step and the idle compute of one carries the arithmetic of the other.
The prompt is being prefilled. In the top row nobody else gets a token until it is done, 1.84 s of silence for 16 streams. In the bottom row every step still carries the batch’s decode, and the prompt moves 256 tokens per step.
The stall is the whole prefill, and the prefill is long. On four A100s Llama 3 70B prefills at about nine thousand tokens a second once it is compute-bound, so a 16K prompt takes 1.8 seconds and a 64K prompt seven. A scheduler that gives prefill its own iteration hands that entire time to every stream in the batch as one inter-token gap. The median gap is still 25 milliseconds; the tail is seconds. This is what a p99 inter-token latency of two seconds usually is: not slow decode, but someone else’s prompt.
The right chunk is the ridge point. A decode step for the batch is bound by reading 140 GB of weights, which takes about 23 milliseconds, during which the cores could have processed roughly two hundred tokens of prefill. A chunk of that size rides inside the step almost free. Below it the chunk is free but the prompt crawls; above it every chunk makes the step compute-bound and the stall grows with the chunk. The two panels above are the two halves of that trade, and the knee in both sits at the same place, the ridge from the prefill and decode page.
The prompt pays almost nothing for it. With a 256-token chunk and sixteen decoders, the 16K prompt reaches its first token six percent later than it would have running alone, and everyone else’s longest gap drops from 1.8 seconds to 30 milliseconds. That is not a trade so much as a free lunch bought with compute that was already idle, which is the same compute that speculative decoding spends on guesses. A deployment gets to spend it once.
What this model leaves out
One prompt arrives, once. Real traffic arrives continuously, and a scheduler with a token budget per step fills it with as many chunks from as many prompts as fit, which is what Sarathi-Serve calls stall-free scheduling. The single arrival here shows the mechanism; the budget is the policy built on it.
Attention over the prompt’s earlier chunks is not charged. Each chunk attends to everything before it, so later chunks of a long prompt cost more than earlier ones, and a 64K prompt pays more for its last chunk than this page shows. The roofline omission is the same one the prefill and decode page makes, and it matters more here.
The decoding requests all have the same context and none of them finishes or arrives during the run. The prefill-first row also gives the prompt priority over waiting decodes, which is the scheduling vLLM shipped with for a long time and what most people mean by the stall; a decode-first scheduler has the opposite problem, prompts that starve.
Read next
- explainers/
- Two phases, two bottlenecks
The roofline these step times come from, and the ridge that sets the chunk size.
- Verifying five tokens costs the same as making one
The other thing the idle compute in a decode step can be spent on.
- A batch is only as fast as its slowest member
Where the batch these chunks ride in comes from.
- feed/
- glossary/