Back to series
· 10 min read

Execution Mechanisms of Prefill and Decode: Two Core Stages of Large Model Inference


I. Why Distinguish Between Prefill and Decode?

Large language models generally use autoregressive generation, predicting the next Token based on the existing context each time.

Suppose the user input is:

Explain how Transformer works.

The model needs to process the entire input first, then begin generating the answer.

These two processes differ significantly in how they compute:

  • Prefill (prefill phase): processes the complete Prompt, computes attention and hidden states for each layer, and builds the KV Cache.
  • Decode (decoding phase): based on the existing KV Cache, processes the newly generated Token each time and gradually generates subsequent content.

Although they use the same set of model parameters, their execution methods, degree of computational parallelism, hardware resource requirements, and performance bottlenecks are not the same.

II. Prefill Stage: Parallel Processing of the Input Context

1. Core Tasks of Prefill

The main job of Prefill is to convert the user-input Prompt into tensors that the model can process, and complete the forward computation of each Transformer layer.

Suppose the input is tokenized into:

[101, 205, 318, 420, 512, 630]

The input sequence length is 6.

The model processes all 6 Tokens at once, rather than processing them one by one as in Decode.

Prefill mainly completes the following tasks:

  1. Convert Token IDs into Embeddings.
  2. Add positional information to the input sequence, such as RoPE.
  3. Pass through Self-Attention and FFN in each Transformer layer.
  4. Compute and save Key and Value at each layer.
  5. Use the hidden state at the last valid position to predict the first output Token.

2. Prefill Execution Flow

flowchart TB
    A["User input Prompt"] --> B["Tokenizer encoding"]
    B --> C["Generate Token IDs"]
    C --> D["Embedding and positional information"]
    D --> E["Transformer layer 1"]
    E --> F["Compute Q, K, V"]
    F --> G["Self-Attention and FFN"]
    G --> H["Save this layer's K, V to KV Cache"]
    H --> I["Continue executing subsequent Transformer layers"]
    I --> J["Obtain the hidden state at the last position"]
    J --> K["LM Head computes Logits"]
    K --> L["Generate the first output Token"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style L fill:#E5F0E9,stroke:#83A995,color:#315D49

Note: each layer computes its own K, V separately and writes them to the KV Cache of the corresponding layer. The KV Cache is not generated only in the last layer; it runs through the entire Transformer network.

3. Why Can Prefill Be Computed in Parallel?

This is the key to understanding the difference between Prefill and Decode.

In the Prefill stage, all Tokens in the input sequence are already determined.

Although the Decoder-only Transformer uses causal attention, which restricts each Token to attending only to the current position and previous positions, this does not mean that computation must be performed Token by Token in order.

For example, for the input sequence:

Token 1: I
Token 2: love
Token 3: AI
Token 4: technology

Causal attention allows:

  • Token 1 to attend to Token 1.
  • Token 2 to attend to Token 1 and Token 2.
  • Token 3 to attend to Token 1, Token 2, and Token 3.
  • Token 4 to attend to Token 1, Token 2, Token 3, and Token 4.

The attention computation at each position can be completed in parallel via matrix operations.

The causal constraint is implemented through the Attention Mask, not through serial execution.

Its attention matrix can be expressed as:

A = \operatorname{Softmax} \left( \frac{QK^T}{\sqrt{d_k}}+M \right)

Where:

  • Q: Query at all input positions.
  • K: Key at all input positions.
  • d_k: Key vector dimension.
  • M: Causal attention mask.
  • A: Attention weight matrix.

For future positions, the corresponding mask values are negative infinity, making the weights after Softmax zero.

Schematic of the causal mask structure:

flowchart TB
    A["Input sequence"] --> B["Compute Q, K, V for all positions in parallel"]
    B --> C["Compute QKᵀ attention scores"]
    C --> D["Apply Causal Mask"]
    D --> E["Softmax to obtain attention weights"]
    E --> F["Weighted aggregation of V"]
    F --> G["Obtain outputs for each position"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#E5F0E9,stroke:#83A995,color:#315D49

Therefore, Prefill can fully utilize the GPU's matrix parallel computing capability.

4. Computational Complexity of Prefill

Let:

  • B: Batch Size.
  • S: Input sequence length.
  • d: Model hidden dimension.
  • L: Number of Transformer layers.

For a standard Transformer, the main computation can be roughly divided into two parts:

Linear projections and FFN:

O(BSd^2)

Self-Attention:

O(BS^2d)

Therefore, the overall computational complexity can be approximated as:

O\left(LB(Sd^2+S^2d)\right)

As the sequence length S increases, the quadratic term in the attention computation becomes increasingly important.

Note that:

  • This is the approximate computational complexity of standard dense attention.
  • FlashAttention can optimize memory access and intermediate result storage, but it does not change the main asymptotic computational complexity of standard full attention.
  • Structures such as GQA, MQA, and sparse attention may change the specific computation and storage costs.

5. Performance Characteristics of Prefill

Prefill usually has a high degree of computational parallelism.

It can organize the matrix operations of a large number of tokens into larger GPU kernels, fully utilizing the GPU's compute units and Tensor Cores.

However, Prefill also has significant resource pressure:

  • The longer the input sequence, the greater the Attention computation.
  • The larger the batch size, the higher the overall computation and activation memory requirements.
  • Each layer needs to generate and store K and V.
  • Long contexts can cause KV Cache to consume a large amount of GPU memory.

Therefore, the Prefill stage is usually more susceptible to factors such as compute capacity and memory bandwidth; the specific bottleneck depends on the model, sequence length, batch size, and hardware.

III. Decode Stage: Generating Output Token by Token

1. Core Task of Decode

After Prefill is complete, the model already has the KV Cache corresponding to the input prompt.

Next, it enters the Decode stage.

The core task of Decode is:

  1. Receive the token generated in the previous step.
  2. Compute the Query, Key, and Value of that token at each layer.
  3. Compute attention using the historical KV Cache.
  4. Append the current token's K and V to the cache.
  5. Obtain the hidden state of the current token.
  6. Predict the next token through the LM Head.

The biggest difference from Prefill is:

Decode usually processes only one new token at each step, rather than recomputing the entire historical sequence.

2. Decode Execution Flow

flowchart TB
    A["Prefill completed"] --> B["Existing historical KV Cache"]
    B --> C["Input current Token"]
    C --> D["Embedding and positional encoding"]
    D --> E["Execute Transformer layer by layer"]
    E --> F["Compute Q, K, V for the current Token"]
    F --> G["Read historical KV Cache"]
    G --> H["Compute attention of the current Token over historical context"]
    H --> I["Append K, V of the current Token"]
    I --> J["Obtain the hidden state of the current Token"]
    J --> K["LM Head computes Logits"]
    K --> L["Sample or select the next Token"]
    L --> M{"Is the stop condition met?"}
    M -->|"No"| C
    M -->|"Yes"| N["Output generated result"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style L fill:#EAF3EC,stroke:#83A995,color:#315D49
    style M fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style N fill:#E5F0E9,stroke:#83A995,color:#315D49

Here is a common point of confusion:

In the Decode phase, each time a Token is generated, it must pass through all Transformer layers of the model, not just the last layer.

Each layer reads its own historical K, V and computes the attention result for the current Token.

3. Why does Decode need KV Cache?

Suppose the input Prompt has 1000 Tokens, and the model needs to generate 100 Tokens.

If KV Cache is not used, every time a Token is generated, all previous context must be reprocessed.

The computation will repeatedly calculate the Key and Value of many historical Tokens.

The core role of KV Cache is to save the K, V computed for historical Tokens at each layer, so that subsequent generation can reuse them directly.

Suppose the following has already been generated:

Prompt:  A B C D
Output:  E F

The next step is to predict G.

At this point:

  • The K, V of A, B, C, D have already been saved in the cache.
  • The K, V of E, F have also been written into the cache in sequence.
  • The current input is the Token representation corresponding to F (in actual execution, this is usually the latest Token selected in the previous step).
  • The model computes the Q, K, V of the current Token.
  • The current Query computes attention with all historical Keys.
  • The current Value is appended to the cache.

Note that when generating the first output Token, the hidden state of the last input position from Prefill is used. Only when generating the second output Token is the first generated Token used as the new Decode input.

4. Attention computation in Decode

Suppose the historical context length is T, and only one new Token is input at present.

The shape of the current Query can be simplified as:

Q_{new}\in \mathbb{R}^{B\times 1\times d_k}

The shape of the historical Key is:

K_{cache}\in \mathbb{R}^{B\times T\times d_k}

Attention scores for the current Token:

Scores=\frac{Q_{new}K_{cache}^T}{\sqrt{d_k}}

Attention output:

Attention(Q_{new},K_{cache},V_{cache}) = Softmax(Scores)V_{cache}

Here, there is no need to recompute the K, V of historical Tokens.

Each layer only needs to compute the Q, K, V of the current Token and read the cache of the corresponding layer.

This is why KV Cache can significantly reduce repeated computation.

5. Computational complexity of Decode

For a single new Token, suppose the current context length is T and the hidden dimension is d.

The computational cost of the current Token's linear projections and FFN is approximately:

O(d^2)

The computational cost of attention between the current Query and historical Keys is approximately:

O(Td)

Therefore, the computational cost of a single Token across all layers can be approximated as:

O\left(L(d^2+Td)\right)

If N Tokens are generated consecutively, and the Prefill cost of the input Prompt is not considered, the cumulative computational cost of the attention part is approximately:

O\left(Ld\sum_{t=1}^{N}(S+t)\right)

where S is the initial Prompt length.

Expanded, this becomes:

O\left(Ld(NS+\frac{N(N+1)}{2})\right)

KV Cache avoids recomputing the historical K and V at every step, but it does not eliminate the attention computation of the current Query over historical Keys and Values.

Therefore, as the context keeps growing, the KV Cache that each Decode step must read also becomes larger and larger.

6. Why Is Decode Easily Limited by Memory Bandwidth?

Each Decode step typically processes only a small number of new Tokens.

For large models, the model weights are very large in scale, but the amount of data computed in a single step is relatively limited.

When executing Decode, the GPU needs to continuously read:

  • Model weights.
  • Historical KV Cache.
  • Intermediate activations of the current Token.
  • Other data required for inference.

When compute units are waiting for data to be transferred from memory, the GPU's compute capability may not be fully utilized.

This often makes Decode appear memory-bandwidth-bound (Memory-Bound).

Especially when the Batch Size is small, the scale of a single-step matrix computation is limited, and the cost of reading model weights and the KV Cache may account for a large proportion.

But this is not an absolute rule:

  • As Batch Size increases, weight reads can be shared across multiple requests, raising compute density.
  • Ultra-long contexts increase the volume of KV Cache reads.
  • Quantization, GQA, MQA, and inference kernel optimizations shift the balance between computation and memory access.
  • On certain hardware and models, Decode may also be limited by compute capability.

IV. Core Differences Between Prefill and Decode

1. Comparison of Execution Mechanisms

Comparison Dimension Prefill Decode
Input content Full Prompt Current new Token
Processing mode Multiple Tokens in parallel Typically one Token at a time
Attention Causal attention within the input sequence Attention of the current Token over the historical context
KV Cache Creates and writes the K, V of the Prompt Reads the historical cache and appends the new K, V
Computational parallelism Usually high Low for a single request at a single step
Primary pressure Compute volume, activations, and memory Memory access for weights and KV Cache
Output Prediction result for the first generated Token Prediction results for subsequent Tokens
Typical metric TTFT TPOT

Here, "Token by Token" means that a single autoregressive generation sequence must wait for the previous step's Token to be determined before it can continue. An inference service can still schedule multiple requests at the same time, and can also process multiple sequences within one Batch.

2. Computational Characteristics of the Two Stages

Prefill: parallelism along the sequence dimension

Token 1  Token 2  Token 3  Token 4  Token 5
   │        │        │        │        │
   └────────┴────────┴────────┴────────┘
                    │
       Parallel matrix computation
                    │
             Build KV Cache

Decode: single-sequence autoregressive generation

Token 1
   │
   ▼
Token 2
   │
   ▼
Token 3
   │
   ▼
Token 4
   │
   ▼
Token 5

In actual production inference systems, the Decode of multiple requests can be co-scheduled through Continuous Batching, so "one Token at a time per request" should not be misunderstood as "the entire GPU can only process one Token at a time".

3. Comparison of Performance Bottlenecks

Dimension Prefill Decode
Primary computation Large-scale matrix operations Small-step incremental computation
GPU utilization Usually high May be low with small batch sizes
Compute density Usually high Usually low
Memory bandwidth Important Usually more sensitive
Impact of long context Attention computation grows noticeably KV Cache reads grow noticeably
Optimization directions Efficient attention, batching, tiled computation KV Cache management, batching, quantization, memory access optimization

V. KV Cache: The Key Mechanism Linking Prefill and Decode

KV Cache is the most important data structure connecting the two phases.

1. What Does KV Cache Store?

In each layer of the Transformer, attention computes:

Q=XW_Q
K=XW_K
V=XW_V

Where:

  • X: the input hidden state of the current layer.
  • W_Q: the Query projection matrix.
  • W_K: the Key projection matrix.
  • W_V: the Value projection matrix.

During inference, the K and V of historical tokens are saved.

The logical structure of the KV Cache can be expressed as:

KVCache= \{(K_1,V_1),(K_2,V_2),\ldots,(K_L,V_L)\}

where L is the number of Transformer layers.

Each layer maintains its own K and V cache.

2. How KV Cache Grows

Assume:

  • Number of Transformer layers: L
  • Batch size: B
  • Current context length: T
  • Number of KV heads: H_{kv}
  • Dimension of each head: D
  • Bytes per element: P

The memory footprint of the KV Cache is approximately:

M_{KV}=2L B T H_{kv} D P

where the factor 2 accounts for the two caches, Key and Value.

For example:

  • Layers: 32
  • Batch size: 1
  • Context length: 8192
  • Number of KV heads: 32
  • Head dimension: 128
  • Data type: FP16, 2 bytes per element

Then:

M_{KV} = 2\times32\times1\times8192\times32\times128\times2
=4,294,967,296\ Bytes

which is about 4 GiB.

This means the KV Cache for a single request alone can occupy several GiB of GPU memory.

If GQA or MQA is used, the number of KV heads is reduced, and the KV Cache footprint drops accordingly.

Actual memory usage is also affected by cache allocation strategy, alignment, paging, batching, and framework implementation.

3. How Do Prefill and Decode Share the KV Cache?

flowchart TB
    A["Input Prompt"] --> B["Prefill"]
    B --> C["Compute K, V for all input tokens"]
    C --> D["Write to the KV Cache of each layer"]
    D --> E["Decode starts"]
    E --> F["Read past KV Cache"]
    F --> G["Compute Q, K, V for the current token"]
    G --> H["Append K, V of the current token"]
    H --> I["Update KV Cache"]
    I --> J["Next Decode round"]
    J --> F

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style H fill:#EAF3EC,stroke:#83A995,color:#315D49
    style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style J fill:#EAF3EC,stroke:#83A995,color:#315D49

The lifecycle of KV Cache is usually tied to the generation process of a single request:

  • Prefill creates the cache.
  • Decode continuously reads from and appends to the cache.
  • After the request ends, the cache can be released or returned to the cache pool.
  • If the system supports Prefix Caching, the KV Cache of some shared prefixes can be reused, but conditions such as model, position, and attention configuration must be compatible.

6. TTFT and TPOT: How to Measure the Performance of the Two Stages?

To understand Prefill and Decode, you also need to understand two core performance metrics for LLM inference services.