Prefill and Decode
The Two Stages of LLM Inference
Introduction
Have you ever wondered what happens as soon as you submit a prompt to ChatGPT? Today, we're going to be looking at the workflow that generates responses to your prompts in pretty much all large language models. When a large language model generates a response, it doesn't do everything in one step. The inference process splits into two distinct phases: prefill and decode. Each phase has different computational characteristics, different bottlenecks, and different implications for how efficiently a model can serve requests at scale. Understanding these two stages is useful for anyone deploying or optimising LLMs in production. It explains why long prompts are expensive, why generation can feel slow even after the first token appears, and where most current research is focused.
The Prefill Stage
Prefill is the first phase of inference. When a prompt arrives, the model converts the entire input into tokens and processes them all at once. It runs a forward pass over every input token simultaneously, computing attention scores and building the key-value (KV) cache.
The KV cache is a critical data structure. It stores the intermediate attention representations for every input token so the decode phase doesn't have to recompute them. Think of it as the model's working memory for a given request.
Characteristics
Parallel computation: Because all input tokens are available upfront, prefill runs as a single large matrix operation. This makes it well-suited to GPU hardware, which is built for parallelism.
Compute-bound: Prefill is limited by raw computational throughput. The more tokens in the prompt, the more computation is required.
Quadratic scaling: Standard attention mechanisms scale quadratically with sequence length. Doubling the prompt length roughly quadruples the prefill cost. This is the core bottleneck for long-context models.
The Decode Stage
Once prefill is complete, the model moves into the decode phase. Here, it generates output tokens one at a time. Each new token is predicted based on all previously generated tokens and the KV cache built during prefill. This repeats until the model hits a stopping condition, such as a maximum token count or an end-of-sequence token.
This sequential process is called autoregressive generation. Unlike prefill, there's no opportunity to parallelise across output tokens, because each token depends on the one before it.
Characteristics
Sequential generation: Tokens are produced one at a time. The model can't skip ahead or batch output tokens the way it batches input tokens during prefill.
Memory-bound: Decode is limited by memory bandwidth rather than compute. The GPU spends most of its time reading the KV cache, not running heavy matrix operations, which leads to lower utilisation of available compute resources.
Consistent per-token cost: Unlike prefill, decode cost per token stays relatively flat regardless of prompt length, because the KV cache is already built.
Key Differences at a Glance
Prefill
Decode
Input
Full prompt (all tokens at once)
One token at a time
Computation
Parallel (matrix operations)
Sequential (autoregressive)
GPU utilisation
High, compute-bound
Lower, memory-bound
Primary output
KV cache
Generated tokens
Speed
Fast for short prompts, slow for long ones
Consistently slower per token
Bottleneck type
Quadratic attention complexity
Memory bandwidth
Why the Prefill Bottleneck Matters
For short prompts, prefill is fast and rarely a concern. The problem shows up at scale: when context windows grow to tens or hundreds of thousands of tokens, prefill latency becomes the dominant cost of a request.
This has direct consequences in production. A model serving long documents, codebases, or extended conversations will spend a disproportionate amount of time in the prefill phase before generating even the first output token. This is sometimes called time-to-first-token (TTFT) latency, and it degrades user experience significantly in interactive applications.
The quadratic attention mechanism is the root cause. For a sequence of length N, the attention computation requires O(N^2) operations. This is manageable at 1K or 4K tokens but becomes a serious constraint at 64K or 128K tokens, which modern long-context models routinely support.
Recent Research: FlashPrefill V2
One of the most significant recent advances in prefill optimisation is FlashPrefill V2, published in August 2026 by Fan, Huang, Wu, Wang, and He. The paper tackles the quadratic bottleneck directly by introducing block-sparse attention for the prefill phase.
The core idea is that not all attention connections in a long sequence are equally important. FlashPrefill V2 identifies the most significant attention patterns dynamically and skips the rest, reducing computation without meaningfully degrading output quality. A mean correction term is applied to keep approximation errors under control, even at extreme sparsity levels. (Fan et al., 2026)
Key Technical Contributions
Block-sparse attention: Attention is computed only over the most relevant token blocks, reducing the effective complexity of prefill for long sequences. (Fan et al., 2026)
Production-ready implementation: FlashPrefill V2 redesigns the sparse attention operator with PackGQA memory access, warp specialisation, and pingpong pipelining, aligning it with FlashAttention-3/4. It also supports FP8 inference for quantised deployments. (Fan et al., 2026)
Framework integration: The system supports paged KV cache and continuous batching natively, so it can integrate directly as an attention backend in modern inference frameworks such as SGLang. (Fan et al., 2026)
Benchmark Results
Evaluations on NVIDIA H20 GPUs at 128K context length show:
47.26x speedup over FlashAttention-2 under FP8 precision. (Fan et al., 2026)
27.19x speedup over FlashAttention-2 under BF16 precision. (Fan et al., 2026)
30.49x speedup over an FA3/4-aligned dense baseline under FP8. (Fan et al., 2026)
These are substantial gains for a system designed for practical deployment rather than isolated benchmark performance. (Fan et al., 2026)
Conclusion
Prefill and decode are fundamentally different computational problems. Prefill is parallel and compute-intensive, and it scales poorly with sequence length. Decode is sequential and memory-bound, constrained by how quickly the system can read the KV cache.
As context windows keep growing, prefill efficiency is becoming one of the most important factors in LLM serving. Research like FlashPrefill V2 shows that sparse attention can deliver order-of-magnitude improvements in prefill throughput without sacrificing output quality, and these techniques are moving from academic prototypes into production-ready systems. (Fan et al., 2026)
We hope this was a good read. If you're interested in stuff like this, please stay tuned as we will continue our journey into the nitty-gritty of LLMs.
References
Fan, Q., Huang, H., Wu, Z., Wang, B., & He, R. (2026). FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving. arXiv preprint arXiv:2608.19758. https://doi.org/10.48550/arXiv.2608.19758
Last updated