LECTURE 21 · TRANSFORMER KV CACHE · Vaswani et al. (2017) & Pope et al. (MLSys 2023 · arXiv:2211.05102)
The KV Cache — see every tensor, stop recomputing the past
Every autoregressive Transformer writes one token at a time. Without a cache, generating token t re-computes the Keys and Values of all t − 1 previous tokens over and over. Caching past Key (K) and Value (V) matrices slashes forward projection work from quadratic O(N²) down to linear O(N) — with zero approximation error.
Everything you need to master the KV Cache
02 THE AUTOREGRESSIVE RECOMPUTATION TRAP · O(N²) → O(N)
Why decoding without cache burns O(N²) work — and how KV Cache flattens it to O(N)
Suppose a model generates N tokens one word at a time. Naive decoding redoes tokens 1..t-1 at every step (1 + 2 + ... + N = N(N+1)/2 = O(N²), a full 2D triangle). KV caching keeps past keys and values frozen so each step processes 1 token (1 + 1 + ... + 1 = N = O(N), a thin 1D line). Explore both the live scaling curve and interactive triangle-to-line visual tool below.
O(N²) Parabola vs O(N) Flat Line
Why 1+2+...+N Triangle Flattens to Line N
Numbers show how huge the waste is — now watch it happen vector by vector inside the interactive visual studio.
03 SPECIAL VISUAL LEARNING STUDIO · INTERACTIVE MATRIX & CACHE SIMULATOR
See the KV Cache come alive token by token
Pick a sentence (or type up to 6 words of your own), press Next ▶ or ▶ Auto-Play, and switch across 4 visual lenses: (1) side-by-side Red Wasted Naive Matrices vs Green Frozen Cache Shelves, (2) interactive Attention Dot-Product X-Ray, (3) Prefill vs Decode split, and (4) Multi-Layer [2, L, H, S, d_h] stack.
04 CAUSAL INVARIANCE PROOF
Why past K and V never change — and why Q is thrown away
The two most common student questions: “Why can we safely reuse old Keys and Values without recalculating them?” and “Why don’t we cache Queries Q too?” Toggle the three rules below and watch the causal attention grid prove both answers visually.
05 PREFILL VS DECODE · POPE ET AL. (MLSYS 2023 · ARXIV:2211.05102)
Two hardware regimes: Compute-Bound Prefill vs Bandwidth-Bound Decode
Plain-English Intuition: Think of loading a moving truck. Prefill puts all P words of your prompt onto one big truck and drives the highway once — the GPU reads model weights once and fills the entire K/V cache in parallel. Decode generates your answer one single word at a time, so for every single new word the GPU must haul the entire weight + KV cache truck across memory again just to carry 1 word! Drag P and G below to watch both stages live.
06 BY-HAND NUMERICAL VERIFICATION (d = 4 FLOATS)
Six-decimal proof: Naive full matrix ≡ KV Cache
Step through four real 4D vectors for ["The", "cat", "sits", "on"] calibrated to FP64. Inspect every dot score q_t · K_cacheᵀ / √4, softmax weight α_t, and blended output o_t — proving bit-for-bit equality with full naive 4 × 4 causal self-attention.
07 SINGLE DECODER LAYER ARCHITECTURE
Architectural Schematic: Exact dataflow & GPU KV Cache Vault inside every Transformer block
Switch between model scales (GPT-2 Small, LLaMA-7B, LLaMA-13B) and filter by pipeline stage to inspect every block in Decoder Layer l during a cached Decode step. Follow the upper Residual Highway (+ x_t), see the fresh q_t stay 1 token wide, and watch new (k_t, v_t) slices append directly into the dedicated dashed-teal GPU VRAM KV Cache Bank before expanding back into FFN.
08 THE MEMORY COST OF SPEED
Exact KV Cache VRAM calculator: 2 · L · B · H · S · d_h · b
Speed comes at a steep GPU VRAM price: saving every token's K and V tensors across all L layers and H heads grows linearly with batch size B and context length S. Pick a standard Transformer preset or adjust every dimension live.
09 PRODUCTION DEBUGGING LAB
Four classic bugs when implementing KV Cache in real code
Knowing the diagram is half the battle — shipping bug-free KV caching in PyTorch means avoiding silent position-index resets, avoiding O(N²) torch.cat copies, keeping caching disabled in training, and left-padding batched prompts.
10 ARCHITECTURE COMPARISON LEDGER
Naive Decoding vs Dynamic KV Cache vs Static KV Buffer
Side-by-side complexity, memory allocation, CUDA graph compatibility, and numerical accuracy summary across all three execution strategies.
| Property / Engineering Axis | Naive Decoding (No Cache) | Dynamic KV Cache (torch.cat) | Static Pre-Allocated KV Buffer |
|---|
Every mechanism above — from-scratch PyTorch, runnable Keras 3 KV Cache, exact equivalence test, zero-copy static buffer, and HuggingFace integration — in clean Python.
11 CODE LAB · PYTORCH, KERAS 3 & HUGGINGFACE
The KV Cache, in clean runnable PyTorch & Keras 3
Switch through five complete scripts: (1) minimal CausalSelfAttentionWithCache in PyTorch, (2) complete Keras 3 KerasCausalAttentionWithCache(layers.Layer) using backend-agnostic keras.ops + Prefill/Decode loop, (3) automated allclose parity check proving Naive == Cached, (4) zero-copy StaticKVCache buffer avoiding repeated concatenations, and (5) inspecting real HuggingFace past_key_values tensor shapes.
12 MASTERY CHECK