Setup & the O(n²) wall·4 min
What you're building
0 / 1
You already wrote a GPT-2 124M forward pass that recomputes K and V for the entire sequence on every token — the O(n²) toy. Here you turn it into a real inference engine: compute K/V for only the new token, cache the rest, and prove the cached logits are identical — within tight tolerance — to the slow recompute. Same model, same numbers, a fraction of the work per token.
The bookmark
Recompute is re-reading the entire book from page one to write each next word. The KV cache is your bookmark plus margin notes — you only read the new sentence and glance at notes you already made.
The journey
Eight chapters, each one rung on a ladder from the toy to the engine:
- The wall — feel, then quantify, why recompute doesn't scale (this chapter).
- The cache struct — a growable per-layer K/V store with exact shapes.
- Single-step + one-layer proof — attention for one new token over a cached history, proved equal to recompute.
- Prefill — process the whole prompt at once and populate every layer's cache.
- Full decode + per-step identity — cached attention through all 12 layers, with every step's logits matching recompute.
- Generate loop — prefill + cached decode + greedy sampling into a usable generator.
- Prefix cache — save a cache after a shared prefix and reuse it across prompts.
- Capstone — make the speed and memory win rigorous and deterministic.