Prefill vs. Decode: The Two Phases of Inference

Why can the pause before the first output token differ so much from the gaps between later tokens? Serving a request has two model-computation phases: prefill, which processes known prompt tokens, and decode, which processes newly selected tokens one step at a time. Queueing, scheduling and transport contribute additional delays.

Prerequisites

You should be comfortable with the basics of transformer inference from Post 5.1, specifically the idea that training processes full sequences in parallel while inference generates one token at a time. That post also builds the hardware intuition this one leans on: arithmetic intensity, the roofline model, and the ridge point that separates memory-bound work from compute-bound work. You'll also want a working sense of matrix multiplication shapes (what happens when you multiply an $(n, d)$ matrix by a $(d, d)$ matrix) and the self-attention mechanism from Arc 4.

The setup

In Post 5.1 we talked about the gap between training and inference. During training, you shove the full sequence through the model in one parallel forward pass. During inference, you generate one token at a time, feeding each output back as input to produce the next.

Before sampling the first output token, the model processes the known prompt. That work can use multi-row matrix products even though later generated tokens depend on earlier selections.

Prefill: processing the prompt

When your prompt arrives at the model, all the tokens already exist. The prompt tokens are known; its final position will predict the first output token. The model just needs to build up its internal representation of the entire prompt, computing attention patterns and filling in the key-value cache for every token.

This looks a lot like a training forward pass. You stack all the prompt tokens into a matrix, multiply through the weight matrices in parallel, compute self-attention across the full sequence, and produce a hidden state for every position simultaneously. If your prompt has 1,000 tokens, the model processes all 1,000 in one big batch of matrix multiplications.

The key computation at each attention layer is:

where $M$ is zero at allowed causal positions and $-\infty$ elsewhere, and $X$ is the full prompt matrix with shape $(n_\text{prompt}, d_\text{model})$. That $QK^T$ multiplication produces an $(n_\text{prompt} \times n_\text{prompt})$ attention matrix. For a 2,000-token prompt, that's a 4-million-element matrix at each head, at each layer.

Long prefills often have enough parallel work to become compute-bound. Short prompts, small kernels, communication, and memory traffic can still limit utilization. Attention adds an $O(n^2 d)$ arithmetic term, while the projection/FFN work scales roughly linearly with token count.

Prefill contributes to time-to-first-token (TTFT) alongside queueing, request processing, scheduling, and transport. Longer prompts increase this work unless a cached prefix can be reused.

After prefill completes, the model has two things: a prediction for the first output token, and a KV cache populated with keys and values for every prompt token. We'll cover it in detail in Post 5.4, but the short version is: it stores the K and V projections so the model doesn't have to recompute them for the prompt tokens during generation.

Decode: generating one token at a time

Once the first token is produced, we enter the decode phase, processing one new position at a time.

At each decode step, you feed in exactly one new token. The model computes Q, K, V for that single token, appends the new K and V to the cache, then computes attention against the entire cache (all the prompt tokens plus all previously generated tokens). Out comes a probability distribution over the vocabulary, you sample a token, and repeat.

Instead of multiplying an $(n, d)$ matrix by $(d, d)$ weight matrices, you're multiplying a $(1, d)$ vector by $(d, d)$ weight matrices. One row for one token. The actual arithmetic is tiny compared to prefill.

For a dense model at batch size one, decode is often limited by memory traffic. FP16 weights for a 7-billion-parameter model occupy about 14 GB. Each step reads layer weights while processing one new row; the next step must traverse those layers again. Long contexts also require substantial K/V traffic. The bottleneck changes with batch size, model architecture, and hardware.

The arithmetic intensity is low. For a dense projection, one input row does about two FLOPs per weight; $n$ rows can reuse each weight for about $2n$ FLOPs. When memory transfers take longer than the arithmetic, decode is memory-bound.

This is the roofline picture from Post 5.1, with prefill and decode landing on opposite sides of the ridge: prefill up around 1,000 FLOPs per byte, decode down at 1. The exact same hardware, running the exact same model weights, hits a completely different bottleneck depending on whether it's processing a batch of prompt tokens or a single generated token.

The time between consecutive generated tokens is your inter-token latency (ITL). In a weight-dominated regime, ITL may change little over a range of prompt lengths. But decode attention reads more cached K/V as context grows; at long contexts or large batches that traffic can dominate.

Two metrics the user actually feels

TTFT measures the initial wait before the first visible answer token. Queueing and scheduling can contribute as much as the model work.

ITL is the spacing between streamed tokens. An assumed 25 ms interval corresponds to 40 tokens per second for one request; 100 ms corresponds to 10. How that feels depends on tokenization, display buffering, and what the reader is doing.

TTFT and ITL measure different parts of the response. Reducing queueing or reusing a cached prompt can lower TTFT. Weight reuse, memory traffic, attention kernels, and scheduling can affect decode latency. Measure the limiting resource before choosing hardware or a parallelism strategy.

Weight reuse can make prompt processing cheaper per token than batch-one decode. That difference is one input to serving cost; provider pricing also reflects the deployment and commercial policy, so a roofline calculation alone cannot predict input or output prices.

A worked example

Assume a 1,000-token prompt takes 57 ms to prefill and subsequent tokens take 25 ms each. These are illustrative timings, not a hardware benchmark. You want a 200-token response; the first token comes from prefill, leaving 199 decode steps.

Under these assumed timings, prefill takes 57 ms and the 199 decode steps take 4.975 seconds. Decode accounts for over 98% of the modeled time.

Implementation sketch

Here's the core prefill/decode loop, with KV cache management and sampling details left to the model and sampler interfaces.

Why this gets worse with long prompts

The example above used a modest 1,000-token prompt. But modern applications routinely stuff 10,000 to 100,000 tokens of context into the prompt. RAG pipelines retrieve chunks of documents. Agents inject tool results. System prompts carry extensive instructions.

At the same assumed linear prefill rate, 50,000 prompt tokens would take about 2.86 seconds before the first output. That is substantial, but still less than the example’s 4.975 seconds of subsequent decode. This extrapolation omits growing attention work and is not a hardware prediction.

The quadratic attention cost makes this worse than linear. That $(n \times n)$ attention matrix for 50,000 tokens has 2.5 billion entries per head per layer. FlashAttention helps enormously by avoiding materializing this matrix, but the compute still scales quadratically with sequence length.

Keeping ITL at 25 ms is a simplification of the example. A 50,000-token cache adds substantial attention traffic; measure both TTFT and ITL when increasing context.

Chunked prefill

Suppose one user submits a 50,000-token prompt while another request is decoding. If the scheduler runs the full prefill before the next decode step, the second request waits for that entire pass. Its stream pauses even though its own next-token work is small.

Agrawal et al. proposed a solution called chunked prefill in their Sarathi paper. Break the long prompt into smaller chunks (say, 512 or 2,048 tokens at a time) and interleave prefill chunks with decode steps from other requests.

Between chunks, the scheduler can run decode steps for other requests. Interleaving spreads the first request’s prefill over more wall-clock time while giving the second request earlier opportunities to receive tokens. The resulting delays depend on chunk size and scheduling policy.

Smaller chunks give more opportunities to interleave decode steps, reducing tail latency for other users. But they also reduce the arithmetic intensity of the prefill computation, pushing it closer to the memory-bound regime. A chunk of 512 tokens still has reasonably high arithmetic intensity (you're doing 512 rows of matrix math per weight load), but a chunk of 32 tokens starts to look more like decode. The appropriate chunk size depends on hardware, model, traffic, and latency targets.

Chunking can reduce peak temporary activation memory by limiting how many new query positions are processed together. It does not remove the KV state for earlier chunks, and attention work still depends on the accumulated context. Kernel tiling and the chunk budget determine the actual memory and runtime tradeoff.

Batching: sharing weight reads across requests

A decode batch combines new positions from independent requests. In the weights-only model, processing 32 requests together supplies 32 rows of arithmetic per weight read instead of one, moving the workload rightward on the roofline.

Larger batches can improve weight reuse, but also require KV storage for more requests. Thirty-two concurrent sequences may need thirty-two private caches, apart from any compatible shared prefixes. A single 70B-model cache at 128K context can exceed 10 GB. PagedAttention (Post 6.3) reduces wasted allocation so more of the available memory can hold useful cache entries.

Common misconceptions

"Prefill and decode have the same cost per token." The dense projection/FFN FLOPs per token are similar; their memory amortization differs. Prefill can reuse a weight load across many rows. Attention costs also depend on how much context each position attends to.

"Longer prompts mean slower generation." Longer prompts mean slower TTFT (longer prefill). ITL can also increase because every new query reads the longer cache. The effect depends on whether weights, cache traffic, compute, or communication dominate.

What's next

The next post, Why One New Token Means One New Row, traces a single decode step through the attention matrices. After that, Post 5.4 derives the KV cache by asking what's redundant across those steps.

Additional reading (and watching)

• Dao, T., et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. NeurIPS 2022.

• Agrawal, A., et al. (2023). Sarathi: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills.

• Kwon, W., et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.

• Yu, G., et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI 2022.

• Patel, P., et al. (2024). Splitwise: Efficient Generative LLM Inference Using Phase Splitting. ISCA 2024. Splits prefill and decode onto separate machine pools and quantifies the savings.

• Zheng, L., et al. (2023). Efficiently Programming Large Language Models using SGLang. Introduces RadixAttention and prefix caching as first-class scheduling primitives, building directly on the prefill/decode asymmetry.