CAS logo CAS NLP LABInteractive Tutorial Series ← Series

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.

O(N²) → O(N)TOTAL PROJECTIONS1 pass/token vs t passes
100% ExactBITWISE PARITYMax diff < 1e-6 vs naive
K & V OnlyPAST Q DISCARDEDOnly q_t asks the question
2 PhasesPREFILL VS DECODEGEMM (TTFT) vs GEMV (TPOT)
2·L·B·H·S·d_hEXACT VRAM COSTSeparate shelf per layer
SIX VISUAL LESSONS

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.

SEQUENCE LENGTH GENERATED (N TOKENS) 512 tokens
Without KV Cache (Naive):
0
With KV Cache (Append Once):
0
CUMULATIVE SCALING GRAPH

O(N²) Parabola vs O(N) Flat Line

Hover or click curve to inspect any N
GEOMETRIC VISUAL PROOF TOOL

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.

Primary Paper Reference (Pope et al., 2023): https://arxiv.org/abs/2211.05102 ↗
USER PROMPT LENGTH (PREFILL TOKENS P) 512 prompt tokens
MODEL REPLY LENGTH (DECODE STEPS G) 128 generated tokens

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.

KV CACHE FORMULA: 2 (K&V) × L × B × H × S × d_h × bytes
■ Static Model Weights ■ Dynamic KV Cache Growth
Layers (L)32 layers
Attention Heads (H)32 heads
Head Dimension (d_h)128 d_head
Sequence Context Length (S)4,096 tokens
Concurrent Batch Size (B)1 batch

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.

PURE KV CACHE · PYTORCH, KERAS 3 & TRANSFORMERS

12 MASTERY CHECK

Eight questions — verify your visual and mathematical KV Cache intuition.

YOUR SCORE

0 / 8