Topic 01: KV Caching & Autoregressive Decoding Dynamics

Overview: Why autoregressive LLM decoding without caching suffers from $\mathcal{O}(T^2)$ redundant compute, how storing past Key and Value tensors decouples step latency to $\mathcal{O}(1)$, mathematical derivation of FLOPs saved, and why the decode phase achieved up to 29.1x GPU speedup and 9.8x CPU speedup.


1. The Problem: Autoregressive Decoding without Caching

Autoregressive Large Language Models generate text one token at a time. To generate token $t+1$, the model conditions on the entire previous token sequence $x_1, x_2, \dots, x_t$.

The Quadratic Compute Penalty ($\mathcal{O}(T^2)$)

In standard un-cached inference (such as baseline nanoGPT):

Total token forward passes across generating $O$ output tokens:

$$\text{Total Tokens Processed} = \sum_{k=0}^{O-1} (P + k) = O \cdot P + \frac{O(O-1)}{2} = \mathcal{O}(P \cdot O + O^2)$$

For long context windows, re-projecting the exact same historical tokens through 12 layers of multi-head linear transformations ($W_q, W_k, W_v$) wastes massive GPU compute cycles on values that never change.


2. The KV Cache Solution: Linear Compute ($\mathcal{O}(T)$)

Self-attention computes:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^T}{\sqrt{d_k}}\right) V$$

Notice that for the newest token $t$:

  1. We only need the output at row $t$. That output is determined entirely by Query vector $q_t$.
  2. $q_t$ computes dot products with all past Keys $k_1, \dots, k_t$, producing attention weights that take a weighted sum over past Values $v_1, \dots, v_t$.
  3. Past Keys ($k_1 \dots k_{t-1}$) and Values ($v_1 \dots v_{t-1}$) depend only on past tokens and model weights. Because the past tokens do not change during generation, their $K$ and $V$ tensors never change!

Therefore, we can store past Keys and Values in memory and compute $Q, K, V$ for only the 1 newly generated token at each decode step.

Step 0 (Prefill):   Prompt [tok_1 ... tok_P]  ──► Compute Q, K, V  ──► Cache K, V (size P)
Step 1 (Decode):    New Token [tok_P+1]       ──► Compute q, k, v  ──► Concat to Cache (size P+1)
Step 2 (Decode):    New Token [tok_P+2]       ──► Compute q, k, v  ──► Concat to Cache (size P+2)

Total token forward passes with KV caching:

$$\text{Total Tokens Processed} = P + \sum_{k=1}^O 1 = P + O = \mathcal{O}(P + O)$$

3. Prefill Phase vs. Decode Phase Mechanics

Dimension Prefill Phase (Step $i=0$) Decode Phase (Step $i > 0$)
Input Tensor ($X$) Prompt sequence: $(B, P, C)$ Single newest token: $(B, 1, C)$
Sequence Length ($T$) $T = P$ (e.g. 32 to 256) $T = 1$
Position Offset `pos_offset = 0` `pos_offset = curr_pos` (historical length)
Position Embeddings `pos = torch.arange(0, P)` `pos = torch.arange(curr_pos, curr_pos + 1)`
Key/Value Cache Action Initialize: `cache_k = k`, `cache_v = v` Concatenate: `torch.cat((cache_k, k), dim=2)`
Context Length ($T_{ctx}$) $T_{ctx} = P$ $T_{ctx} = T_{past} + 1$
Causal Masking `is_causal = True` (triangular mask) `is_causal = False` (unmasked: row attends to all keys)
Hardware Bottleneck Compute-Bound (large Matrix-Matrix GEMM) Memory-Bandwidth Bound (GEMV fetching KV cache)

4. Multi-Head Attention Tensor Shapes Step-by-Step

For Batch $B$, Number of Heads $nh=12$, Head Dimension $hs=64$, Embedding $C = nh \times hs = 768$:

  1. Linear Projection:

    Pass single token vector $X \in \mathbb{R}^{B \times 1 \times C}$ through `c_attn` linear projection:

    $$Q \in \mathbb{R}^{B \times 12 \times 1 \times 64}, \quad K_{new} \in \mathbb{R}^{B \times 12 \times 1 \times 64}, \quad V_{new} \in \mathbb{R}^{B \times 12 \times 1 \times 64}$$
  2. Cache Concatenation along dim 2:
    self.cache_k = torch.cat((self.cache_k, k), dim=2)  # Shape: (B, 12, T_ctx, 64)
    self.cache_v = torch.cat((self.cache_v, v), dim=2)  # Shape: (B, 12, T_ctx, 64)
  3. Attention Score Computation:

    Multiply single Query token against all historical Keys:

    $$\text{Scores} = \frac{Q @ K_{cache}^T}{\sqrt{hs}} \in \mathbb{R}^{B \times 12 \times 1 \times T_{ctx}}$$
  4. Softmax Normalization: $$\text{Attn\_Weights} = \text{softmax}(\text{Scores}, \text{dim}=-1) \in \mathbb{R}^{B \times 12 \times 1 \times T_{ctx}}$$
  5. Value Aggregation: $$\text{Output} = \text{Attn\_Weights} @ V_{cache} \in \mathbb{R}^{B \times 12 \times 1 \times 64}$$
  6. Output Projection:

    Reshape to $(B, 1, 768)$ and pass through `c_proj` linear layer.


5. Why Decode Step Latency Scales by 29.1x on GPU

In our benchmarks, we measured two distinct metrics:

  1. End-to-End Generation Wall-Clock: Includes initial prefill plus all decode steps. Yielded 9.83x on CPU and 3.18x on GPU at input=256, output=64.
  2. Per-Token Decode Step Acceleration: When generating tokens late in the sequence (e.g. at context 1,024), comparing a single decode step without cache (re-forwarding 1,024 tokens) versus with cache (forwarding 1 token) yielded a speedup of 29.1x on GPU.
💡 Why does late decode step speedup reach ~29x?
At context length 1,024, forwarding all 1,024 tokens through 12 Transformer layers requires: $$12 \text{ layers} \times \left(2 \times 1024 \times 768 \times 2304 \text{ (QKV GEMM)} + 2 \times 12 \times 1024^2 \times 64 \text{ (Attn)} + 2 \times 1024 \times 768 \times 3072 \times 2 \text{ (MLP)}\right)$$ In contrast, forwarding 1 token with KV cache requires only: $$12 \text{ layers} \times \left(2 \times 1 \times 768 \times 2304 + 2 \times 12 \times 1 \times 1024 \times 64 + 2 \times 1 \times 768 \times 3072 \times 2\right)$$ The FLOP ratio is $>30\times$. Because an RTX 3050 has high memory bandwidth and Tensor Cores, the single-token step executes in <1 ms while the 1,024-token forward takes ~25 ms, delivering a 29.1x decode acceleration.

6. The Hidden Memory Cost of Naive `torch.cat`

While KV caching eliminates compute, our benchmark revealed an interesting memory behavior on GPU:

Observation: At matched input/output lengths (e.g., 256 prompt, 64 output), KV-cached generation used slightly more peak allocated memory than un-cached generation (521.0 MB vs 495.9 MB)!

Root Cause:


7. Interview Review Q&A

Q1: How much memory does a KV cache consume in bytes?

Answer: The formula across an entire Transformer model is:

$$\text{Bytes} = 2 \times \text{num\_layers} \times \text{num\_heads} \times \text{head\_dim} \times \text{seq\_len} \times \text{precision\_bytes} \times \text{batch\_size}$$

For GPT-2 Small (12 layers, 12 heads, head dim 64, fp32 = 4 bytes) at sequence length 1,024 and batch size 1:

$$\text{Memory} = 2 \times 12 \times 12 \times 64 \times 1024 \times 4 \times 1 = 75,497,472 \text{ bytes} \approx 72.0 \text{ MB}$$

Q2: Why is unmasked attention used during single-token decoding?

Answer: During single-token decoding, $T=1$ and $T_{ctx} > 1$. The query token represents the newest position ($T_{ctx}-1$). By definition of causality, this newest token is allowed to attend to all previous tokens $0 \dots T_{ctx}-1$. Because there are no "future" tokens passed in $Q$, a triangular causal mask is completely unnecessary—all key positions are valid past context.