Decode: Generate One Position at a Time

In Prefill: Process the Prompt and Build the Cache, you saw how the model processes all prompt tokens in parallel, builds the initial KV cache, and produces the very first output token. Now the prompt is exhausted. The model must generate token P+1, then P+2, and so on — one at a time. This lesson follows each new position through the decode loop.

---

Why Decode Is Strictly Sequential

During prefill, every token in the prompt is known before the forward pass begins. The model can multiply large matrices across all P positions simultaneously.

Decode is different. To generate token t+1, you must first sample token t. Token t becomes the single-token input for the next forward pass. This autoregressive loop cannot be parallelized across future positions — there is no “future” yet.

The Autoregressive Dependency

Step 1: Input = prompt tokens [0, 1, 2, ..., P-1]     → Output = token P
Step 2: Input = token P                               → Output = token P+1
Step 3: Input = token P+1                             → Output = token P+2
...
Step t: Input = token P+t-1                           → Output = token P+t

Each step depends on the previous step’s output. This is why decode latency is measured per token (Inter-Token Latency, or ITL), not as a single batch.

Key distinction: Prefill parallelism comes from having all inputs upfront. Decode parallelism can only come from multiple independent requests (continuous batching), not from multiple positions within one request.

---

Single-Token Attention with the KV Cache

At each decode step, the input is exactly one token vector of shape [1, d_model]. Let’s trace what happens at a single transformer layer.

Projections: One Query, One Key, One Value

x_new ∈ [1, d_model]           # Single new token embedding (after residual + norm)

q_new = x_new @ W_Q   ∈ [1, d_k]   # One query vector
k_new = x_new @ W_K   ∈ [1, d_k]   # One key vector
v_new = x_new @ W_V   ∈ [1, d_v]   # One value vector

Notice: q_new, k_new, v_new each have batch dimension 1 and sequence dimension 1. They are row vectors.

Cache Update: Append the New Key and Value

The KV cache from prefill (and previous decode steps) already holds all past keys and values:

K_cache ∈ [B, H_kv, T_past, d_head]   # Before append
V_cache ∈ [B, H_kv, T_past, d_head]

After computing k_new and v_new for the current token, we append them:

K_cache ← concatenate([K_cache, k_new], axis=2)   # Shape becomes [B, H_kv, T_past+1, d_head]
V_cache ← concatenate([V_cache, v_new], axis=2)   # Shape becomes [B, H_kv, T_past+1, d_head]

Now the cache length is T_past + 1. This grows by exactly one position per generated token.

Attention: One Query Against the Full Cache

The attention score computation is now a 1D row vector, not a square matrix:

scores = q_new @ K_cache^T
       = [1, d_k] @ [d_k, T_past+1]
       = [1, T_past+1]

This produces T_past + 1 scalar scores — one for the new query against each cached key (including the new key we just appended).

No Causal Mask Needed

In prefill, we needed a causal mask because the query at position i must not attend to positions j > i. Here, every entry in K_cache is a past token (or the current token). The new query is allowed to attend to all of them. No mask is required.

Why this works: The autoregressive property is enforced by the loop structure — we only ever append the current token after computing its attention. The cache contains exactly the tokens that are allowed to be seen.

Softmax and Value Blend

weights = softmax(scores / √d_k)    # Shape [1, T_past+1], sums to 1.0
output  = weights @ V_cache          # [1, T_past+1] @ [T_past+1, d_v] = [1, d_v]

The result is a single output vector of shape [1, d_v] for this head at this layer. This continues through the output projection, residual, and feed-forward network — exactly as in prefill, but with sequence length 1.

---

The Memory-Bandwidth Bottleneck

This is the most important performance fact about decode: it is memory-bandwidth-bound, not compute-bound.

Arithmetic Intensity Comparison

Phase	Weight Bytes Read	KV Cache Bytes Read	FLOPs Per Token	Arithmetic Intensity
Prefill (P=1000)	~14 GB (once)	0	~14 TFLOPs	~1000 FLOPs/byte
Decode (per token)	~14 GB	~0.25 MB (grows)	~14 GFLOPs	~1 FLOP/byte

In decode with batch size B=1:

• The GPU must load all model weights (e.g., 14 GB for a 7B model in FP16) from VRAM into registers/cache for every single token.
• But it only performs 2 × N FLOPs per token (e.g., 14 billion FLOPs = 14 GFLOPs).
• Arithmetic intensity ≈ 1 FLOP per byte.

Modern GPUs have massive compute (300+ TFLOPS on H100, 82 TFLOPS on RTX 4090) but memory bandwidth of only 1–3 TB/s.

Concrete Timing Example

GPU: RTX 4090 (1008 GB/s peak memory bandwidth, ~800 GB/s achieved) Model: 7B parameters, FP16 = 14 GB weights

Time to load weights = 14 GB / 800 GB/s = 0.0175 s = 17.5 ms
Time to compute 14 GFLOPs on 82 TFLOPS = 14e9 / 82e12 = 0.00017 s = 0.17 ms

The GPU spends 99% of its time waiting for memory transfer. The compute units sit idle.

This is why batch size matters. With larger batches, the same weights are reused across multiple requests, amortizing the memory reads. Continuous batching keeps the GPU fed.

---

Inter-Token Latency (ITL) and Tokens Per Second

Because decode is memory-bandwidth-bound, we can estimate latency directly from hardware specs.

ITL Formula

ITL ≈ (Model_Weight_Bytes + KV_Cache_Bytes_Per_Token) / Achieved_Memory_Bandwidth

• Model_Weight_Bytes = total model size in bytes (e.g., 14 GB for 7B FP16)
• KV_Cache_Bytes_Per_Token = bytes added to cache per generated token
• Achieved_Memory_Bandwidth = realistic HBM bandwidth (not peak)

Tokens Per Second (TPS)

TPS = 1 / ITL

Why ITL Grows With Context Length

The KV cache grows by 2 × L × H_kv × d_head × bytes_per_element per token. As the cache grows:

• More cache bytes must be read per token (the attention scores touch the full cache)
• Eventually the cache no longer fits in L2 cache, forcing more HBM reads
• ITL increases gradually with context length

---

Hands-On Exercise 1: Single-Step Attention with KV Cache Hand Calculation

Problem: Compute the attention output for a single decode step by hand.

Given:

• Existing cache (2 past tokens):
  • k_0 = [1.0, 0.0], v_0 = [1.0, 0.0]
  • k_1 = [0.0, 1.0], v_1 = [0.0, 1.0]
• New token 2 arrives:
  • q_2 = [2.0, 2.0]
  • k_2 = [1.0, 1.0]
  • v_2 = [2.0, 2.0]
• Head dimension d_k = 2 (so √d_k = √2 ≈ 1.4142)

Step-by-step Solution:

Step 1: Append k_2 to cache → 3 keys in cache

K_cache = [[1.0, 0.0],    # k_0
           [0.0, 1.0],    # k_1
           [1.0, 1.0]]    # k_2 (newly appended)
V_cache = [[1.0, 0.0],    # v_0
           [0.0, 1.0],    # v_1
           [2.0, 2.0]]    # v_2 (newly appended)

Step 2: Dot products q_2 · k_i for each cached key

q_2 · k_0 = 2(1.0) + 2(0.0) = 2.0
q_2 · k_1 = 2(0.0) + 2(1.0) = 2.0
q_2 · k_2 = 2(1.0) + 2(1.0) = 4.0

Raw scores = [2.0, 2.0, 4.0]

Step 3: Scale by √d_k = √2 ≈ 1.4142

Scaled = [2.0/1.4142,  2.0/1.4142,  4.0/1.4142]
       ≈ [1.4142,      1.4142,      2.8284]

Step 4: Exponentials

exp(1.4142) ≈ 4.1132
exp(1.4142) ≈ 4.1132
exp(2.8284) ≈ 16.9183

Sum = 4.1132 + 4.1132 + 16.9183 = 25.1447

Step 5: Softmax (divide by sum)

p_0 = 4.1132 / 25.1447 ≈ 0.1636
p_1 = 4.1132 / 25.1447 ≈ 0.1636
p_2 = 16.9183 / 25.1447 ≈ 0.6728

Verify: 0.1636 + 0.1636 + 0.6728 = 1.0000 ✓

Step 6: Weighted sum of values

output = 0.1636 × [1.0, 0.0] + 0.1636 × [0.0, 1.0] + 0.6728 × [2.0, 2.0]
       = [0.1636, 0.0] + [0.0, 0.1636] + [1.3456, 1.3456]
       = [1.5092, 1.5092]

Final Answer: Attention output = [1.5092, 1.5092]

Interpretation: The new token attends most strongly to itself (weight 0.67) because its key is most similar to its query. The cached tokens contribute the remaining attention mass.

---

Hands-On Exercise 2: Decode Latency from Hardware Memory Bandwidth

Problem: Calculate the memory-limited Inter-Token Latency and throughput for a 7B model on a specific GPU.

Given:

• Model: 7B parameters in FP16 → 14 GB = 14 × 10⁹ bytes
• GPU achieved memory bandwidth: 800 GB/s

Step-by-step Solution:

Step 1: Calculate memory-limited ITL

ITL = Model_Weight_Bytes / Achieved_Bandwidth
    = 14 GB / 800 GB/s
    = 0.0175 seconds
    = 17.5 ms

Step 2: Calculate tokens per second (TPS)

TPS = 1 / ITL
    = 1 / 0.0175
    ≈ 57.1 tokens/second

Final Answer: ITL ≈ 17.5 ms, Throughput ≈ 57.1 tokens/s

Note: This assumes the KV cache fits in fast cache (L2/HBM) and its read cost is negligible compared to weight loading. For long contexts, add KV_Cache_Bytes_Per_Token / Bandwidth to the numerator. Real-world ITL will be slightly higher due to kernel launch overhead, softmax, and FFN memory traffic.

---

Hands-On Exercise 3: KV Cache Growth Trace Across Generation Steps

Problem: Calculate how much the KV cache grows per token and the total growth for a multi-token generation.

Given:

• Model: L = 32 layers, H_kv = 8 KV heads, d_head = 128
• Precision: BF16 (2 bytes per element)
• Generate: 500 tokens

Step-by-step Solution:

Step 1: Bytes per token per layer Each token adds one Key vector and one Value vector per KV head:

Elements per layer = 2 × H_kv × d_head × 1
                   = 2 × 8 × 128 × 1
                   = 2,048 elements
Bytes per layer    = 2,048 × 2 bytes
                   = 4,096 bytes = 4 KiB

Step 2: Bytes per token across all layers

Total bytes per token = L × bytes_per_layer
                      = 32 × 4,096
                      = 131,072 bytes
                      = 128.0 KiB

Step 3: Total growth for 500 tokens

Total growth = 500 × 131,072
             = 65,536,000 bytes
             = 62.5 MiB

Final Answer: 128 KiB per token, 62.5 MiB for 500 tokens

Context: For a 24 GB GPU, 62.5 MiB is modest. But at 4K context with 32 layers and 128 head dim, the cache reaches ~256 MiB before generation even starts. Long-context serving requires cache management (paging, eviction, quantization) covered in Track 00 Part V.

---

Summary Reference Table: Prefill vs Decode

Aspect	Prefill (Phase 1)	Decode (Phase 2)
Input length	P tokens (full prompt)	1 token (newly generated)
Execution mode	Massively parallel (large GEMMs)	Sequential (one position per step)
Primary bottleneck	Compute-bound (GPU FLOPS)	Memory-bandwidth-bound (HBM reads)
Arithmetic intensity	High (weights reused across P tokens)	Low (~1 FLOP/byte)
KV cache	Written (built from scratch)	Read + appended (incrementally)
Attention shape	[P, P] square matrix	[1, T_past+1] row vector
Causal mask	Required (lower-triangular)	Not needed (all past is valid)
Latency metric	Time to First Token (TTFT)	Inter-Token Latency (ITL) / TPS
Scaling with length	FLOPs ∝ P → TTFT ∝ P	Cache size ∝ P + t → ITL grows with context
Parallelism	Across P tokens	Across batch requests only

---

Primary Source Citations

• Pope et al. (2022), Efficiently Scaling Transformer Inference — arXiv:2211.05102 (Prefill/decode distinction, compute vs memory bounds, KV cache mechanics)
• Shazeer (2019), Fast Transformer Decoding: One Write-Head is All You Need — arXiv:1911.02150 (Single-query decode, cache append mechanics, memory-bound analysis)
• Yu et al. (2022), Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022) — arXiv:2208.08200 (Iteration-level scheduling, continuous batching, decode throughput optimization)

---

What Comes Next

• Next lesson: Prefill vs. Decode: A Worked Latency Example — Compare phase costs and tensor shapes, then calculate how prompt and output lengths change total request latency.
• Previous lesson: Prefill: Process the Prompt and Build the Cache
• Track overview: Start Here: LLM Foundations