Prefill vs. Autoregressive Decode: Computation and Memory Access

Hello, and welcome to the LLM inference module. This module moves from how a Transformer is trained to what actually happens when it serves an interactive request on GPUs. The central operational fact is that inference is not one uniform workload: processing a prompt and generating its answer stress the GPU in fundamentally different ways.

In this lesson, you will distinguish prefill from autoregressive decode at the level that matters for serving design: parallelism, matrix shapes, model-weight reuse, KV-cache traffic, and the resulting compute- versus memory-bandwidth bottlenecks. This distinction underlies later decisions about batching, capacity, latency metrics, cache management, and prefill/decode disaggregation.

---

One request, two GPU workloads

A causal LLM generates a completion conditioned on everything that precedes it. Given a prompt of $S$ tokens, it must first establish the model’s internal attention state for that entire prompt. It can then produce output tokens, but each new token becomes part of the context required for the next one.

Operationally, a request has two phases:

1. Prefill processes all currently uncached prompt tokens. It produces the logits used to choose the first output token and writes attention state into the KV cache.
2. Decode repeatedly processes one newly chosen token per active sequence, reads the prior context from the KV cache, produces logits for the next token, and appends new KV state.

Tokenization and detokenization may happen on CPUs, but the expensive neural-network forward passes and the KV cache reside on GPU memory.

The following short video provides the useful hardware-level intuition: arithmetic intensity is the amount of computation achieved per byte moved from high-bandwidth memory (HBM).

A useful correction to a common intuition: prefill is only one model forward pass, but it is not necessarily fast. A long prompt can make time to first token substantial. Decode, meanwhile, has a relatively small amount of work per step but must repeat that step once for every generated token. A 1,000-token response creates roughly 1,000 sequential decode iterations for that request.

---

Prefill: exploit parallelism across the prompt

Suppose the prompt contains $S$ token embeddings, each with hidden dimension $H$. At a linear layer, the activation has a shape resembling $S\times H$. The model applies the same weight matrix to all $S$ rows at once. This is a large matrix-matrix multiplication, or GEMM.

For an attention head of dimension $d$, prefill conceptually computes:

$$Q=X{W}_Q,K=X{W}_K,V=X{W}_V$$

where:

$$Q,K,V\in {\mathbb{R}}^{S\times d}$$

Causal attention then forms a score matrix:

$$\mathrm{Attention}(Q,K,V)=\mathrm{softmax}\left(\frac{Q{K}^T}{\sqrt{d}}+M_{\text{causal}}\right)V$$

The causal mask ensures a position can attend only to earlier positions and itself. Although optimized kernels such as FlashAttention avoid materializing the full $S\times S$ score matrix in HBM, the mathematical attention work still reflects interactions among prompt positions.

The decisive systems property is weight reuse. A tile of model weights loaded from HBM can participate in computation for many prompt-token rows before it is evicted from on-chip memory. Large GEMMs also map well onto Tensor Cores. Consequently, prefill usually has high arithmetic intensity:

$$\text{Arithmetic intensity}=\frac{\text{FLOPs performed}}{\text{bytes moved from HBM}}$$

High arithmetic intensity generally places prefill near the GPU’s compute ceiling. In ordinary language: the accelerator has plenty of useful arithmetic to do after loading data, so raw compute throughput is often the limiting resource.

What grows when prompts get longer?

Prefill includes several types of work:

• Dense layers and projections scale roughly linearly with the number of input tokens.
• Attention work grows roughly as $O(S^2)$ for full causal attention because many query-key relationships are evaluated.
• KV-cache writes grow roughly linearly with $S$: each prompt position contributes a key and value vector at every Transformer layer.

For modest contexts, dense layers may dominate runtime. At long contexts, attention can become the major prefill cost. Thus, a 32,000-token RAG prompt is not merely “64 times more input” than a 500-token prompt; its attention workload can grow much more sharply.

At the service level, prefill is most closely associated with time to first token (TTFT). Reducing its duration improves how quickly a user sees the model begin responding.

---

Decode: sequential generation with cached history

After prefill chooses the first generated token, the model starts decoding. At decode step $t$, it processes only the embedding for the newest token. It does not rerun the entire model over every previous token.

For attention, it computes a new query, key, and value for the latest position:

$$q_t=x_t{W}_Q,k_t=x_t{W}_K,v_t=x_t{W}_V$$

The new $k_t$ and $v_t$ are appended to the cache. The query $q_t$ attends over all cached keys and values:

$$\mathrm{Attention}(q_t,K_{\text{cache}},V_{\text{cache}})=\mathrm{softmax}\left(\frac{q_t{K}_{\text{cache}}^T}{\sqrt{d}}\right)V_{\text{cache}}$$

The cache stores keys and values, not past queries. A past query was only needed when its own token was being computed. Past keys and values are needed again because every future token may attend to those previous positions.

The KV cache prevents a disastrous alternative: recomputing $K$ and $V$ for the whole history at every output token. It turns repeated full-sequence recomputation into incremental state growth.

It does not make history free. At each decode step, attention must still read the cached keys and values for the relevant context. As a conversation grows, the cache consumes more HBM capacity and each decode step usually requires more cache bandwidth.

There are three important forms of GPU-resident memory during serving:

Memory category	Behavior during prefill	Behavior during decode
Model weights	Read through each layer, with reuse across all prompt tokens	Read through each layer again for every generated token
KV cache	Written for every prompt token and layer	Read as past context; extended by one token per layer each step
Temporary activations	Can be substantial because many prompt tokens are active together	Smaller per step, though many concurrent sequences still require workspace

The cache is therefore both an optimization and a capacity commitment. Once a request begins generation, its cache stays allocated until that sequence finishes, is cancelled, or is evicted.

---

Why decode is usually memory-bound

The matrix shapes change radically from prefill to decode.

During prefill, a weight matrix is multiplied by a matrix containing many token activations. During decode for one request, the same weight matrix is multiplied by a single activation vector. This is a matrix-vector multiplication, or GEMV, rather than a large GEMM.

A rough, deliberately simplified view makes the effect clear. Let:

• $P$ be the number of model parameters,
• $b$ be bytes per weight element,
• $B$ be the number of active sequences batched together,
• $S$ be the number of prompt tokens processed per sequence in prefill.

Ignoring details such as attention and layer structure, a prefill pass performs work approximately proportional to:

$$2PBS$$

while moving model weights on the order of:

$$Pb$$

This yields a rough weight-related arithmetic intensity of:

$$I_{\text{prefill}}\approx \frac{2BS}{b}$$

For a single decode iteration, only one new token from each of $B$ sequences is processed:

$$I_{\text{decode}}\approx \frac{2B}{b}$$

The exact quantities vary by architecture and kernel, but the contrast is robust: prefill gets an extra factor proportional to prompt length $S$ of reuse. Decode does not.

This creates the usual performance profile:

Property	Prefill	Autoregressive decode
Tokens computed per sequence	All new prompt tokens	One new token
Dominant dense operation	Large GEMM	GEMV or small GEMM
Dependency within a request	Prompt positions are mostly parallelizable	Next token depends on the prior token
Weight reuse	High across prompt tokens	Low per active sequence per step
Attention context	Prompt tokens	Entire accumulated KV cache
Usual bottleneck	Tensor Core compute	HBM bandwidth
Principal user-facing effect	TTFT	Inter-token latency

“Usually” matters. These labels are workload diagnoses, not laws of nature.

• Large decode batches increase reuse because the GPU processes one new token for many sequences together. A serving engine uses this to improve throughput.
• Very short prompts may have too little work to fully utilize the GPU during prefill.
• A short new suffix attached to a huge cached prefix can make a nominal prefill behave more like decode: there are few new query tokens but a long KV context to read.
• Speculative decoding can verify multiple proposed tokens together, increasing effective matrix sizes and potentially moving decode toward a more compute-heavy regime.

Still, for the interactive serving workloads encountered most often, the practical rule holds:

Optimize prefill for compute throughput and decode for memory bandwidth, cache efficiency, and sustained batching.

A faster-compute GPU can strongly improve a compute-bound prefill. But if decode is bounded by reading multi-gigabyte model weights and growing KV state from HBM, extra floating-point capability alone may provide little improvement to tokens per second.

---

The serving consequence: throughput is not one number

A request’s serial decode dependency limits latency for that request: token $t+1$ cannot be generated until the model has processed token $t$. Yet a GPU can decode one token for many different requests in the same iteration. This is why serving systems try to keep a rolling batch of active sequences.

The tension is straightforward:

• A large prefill can efficiently use GPU compute but may delay decode tokens for users already streaming.
• A decode-heavy batch can protect inter-token latency but may postpone new prompts and worsen TTFT.
• More active sequences improve decode batching but consume additional KV-cache memory.
• Longer contexts increase useful user context, but reduce the number of concurrent requests that fit in GPU memory and increase decode-time cache reads.

This is the origin of mechanisms such as chunked prefill and continuous batching. Rather than treating a long incoming prompt as one indivisible block, an engine can process it in chunks while continuing to schedule decode work for existing users. The detailed scheduling policies come later; for now, recognize the reason they exist: prefill and decode compete for the same accelerator while optimizing different user-visible goals.

For an interview or design review, use this compact diagnostic:

1. Identify whether the complaint is slow first-token response, slow streaming, low aggregate throughput, or GPU out-of-memory.
2. Separate prompt-token volume from generated-token volume and current context length.
3. Determine whether the limiting work is large compute-rich GEMMs, repeated weight reads, or KV-cache reads and capacity.
4. Only then propose a remedy: more compute, more memory bandwidth, better batching, shorter effective context, cache optimization, or scheduling changes.

---

Key takeaways

LLM serving consists of two distinct phases:

• Prefill processes all new prompt tokens in parallel, writes their KV state, uses large matrix multiplications, and is generally compute-bound.
• Decode generates one token per sequence at a time, reuses cached keys and values instead of recomputing history, repeatedly streams weights and reads KV state, and is generally memory-bandwidth-bound.
• The KV cache trades GPU memory capacity and memory bandwidth for avoidance of repeated historical computation.
• Long prompts primarily pressure TTFT and can incur quadratic attention work; long contexts increase per-token decode cache reads and reduce concurrency capacity.
• Batching improves hardware utilization, but scheduling must balance TTFT, inter-token latency, throughput, and cache memory.

Next, you will turn this qualitative model into inference timing metrics: time to first token, inter-token latency, end-to-end latency, and token throughput from an execution timeline.