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.
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$.
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.
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$:
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)$$| 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) |
For Batch $B$, Number of Heads $nh=12$, Head Dimension $hs=64$, Embedding $C = nh \times hs = 768$:
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}$$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)
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}}$$Reshape to $(B, 1, 768)$ and pass through `c_proj` linear layer.
In our benchmarks, we measured two distinct metrics:
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:
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}$$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.