Why cache: recomputation in autoregressive decoding

Serial generation reprocesses its own prefix at every step, so cost grows faster than length. The cache is the one idea that removes that repeated work, and every later unit builds on it.

explain
derive

You can now

Explain why cached keys and values remove repeated projection and attention work while queries stay token-specific.
Derive naive versus cached attention work across generated tokens and name the terms that remain.
Compute the repeated-prefix share for a generation length from the triangular sum.

Covers

Autoregressive dependency and naive prefix recomputation
Cached keys and values versus token-specific queries

Study, in this order

3 steps

Modern LLM Notebook 21: why generation is slow
Modern LLM Notebook - KV cache and inference acceleration

Section 1 (naive_generation_cost table for 10 to 2000 tokens with 99.8 percent repeated work at 1000 tokens, plus the \(O(N^2)\) versus \(O(N)\) plot)

Done
Raschka `ch04/03_kv-cache` README: how it works
LLMs from Scratch companion - KV cache and GQA

How it works (Time flies then Time flies fast figures with identical keys and values for the first two tokens) and KV cache advantages and disadvantages (per-step work \(O(n^2)\) versus \(O(n)\), memory grows linearly)

Done
Modern LLM Notebook 21 Section 2: KV cache saves \(K\) and \(V\) only
Modern LLM Notebook - KV cache and inference acceleration

Section 2 through the AttentionWithKVCache class and the 5-token equivalence check (max diff 2e, cache shapes [1,4,1,8] growing to [1,4,5,8])

Done

Focus on

Each new token depends on all past tokens, so naive generation reruns the full prefix. The triangular sum 1 to \(n\) is the proxy for that repeated work.
Past tokens never change, so their \(K\) and \(V\) projections stay valid. The new token still needs a fresh \(Q\) to score against cached \(K\).
The cache removes \(K\) and \(V\) recomputation and past hidden-state work. It does not remove the new \(Q\) projection or the read of cached \(K\) and \(V\).
Cached and uncached runs compute the same function. Identical outputs are the correctness check, not a coincidence.

Reproduce closed-book

Derive the triangular naive cost \(n(n+1)/2\) for \(n\) tokens, the cached per-step new-token cost, and the 99.8 percent repeated-work share at \(n\) equal to 1000.

Traps

Thinking the cache skips attention. It skips recomputing past \(K\) and \(V\), but each step still reads the full cache to score the new query.
Caching the query. Queries are token-specific, so caching them across steps is wrong; only \(K\) and \(V\) persist.
Reading speedup from multiply counts as GPU time. Counts prove the scaling change; wall time needs warmup and synchronization, which belong to the measurement unit.

Practice

No Magic `microkv.py`: no-cache versus cached multiply comparison

generate_no_cache versus generate_with_cache with GEN_LEN 16, the assert that both token lists match, the per-step multiply table and the linear memory-growth table

CPU multiply counts only. Do not present wall time as GPU or serving evidence.

Self-test

Why are \(K\) and \(V\) reusable across steps but \(Q\) is not?
Under the triangular proxy, what share of work is repeated prefix processing when generating 1000 tokens?
microkv.py asserts the cached and uncached token lists are identical. Does the cache change the sampling distribution?
In the Modern 21 demo with d_model 32 and 4 heads, what is the \(K\) cache shape at step 5 and what does each dim mean?

Completion criterion

Stop when

You derive the triangular share by hand and your microkv.py run shows identical tokens with per-step multiplies falling from growing to flat.

Mark passed, then open 5.2 Only mark this when you can do it without notes.

Leads to

5.2 Building a KV cache Build the cache you just motivated.
5.5 Two regimes: prefill and decode See how the two phases stress hardware differently.

Comes after

3.6 Decoding policies: from greedy to nucleus samplingSee why serial generation needs a cache before measuring it.
3.7 Stopping rules and reproducible generationKeep the same stopping and sampling contract while removing recomputation.

Resources for this unit

LLMs from Scratch companion - KV cache and GQA
Sebastian Raschkaprimaryimplementation
Use ch04/03_kv-cache and ch04/04_gqa with the chapter model code. Add explicit per-layer ownership, position offsets, variable lengths, EOS compaction and MHA-versus-GQA cache arithmetic to the runnable comparison.
Modern LLM Notebook - KV cache and inference acceleration
Walking Labsrequiredimplementation
Use the KV-cache portions of English notebooks 11-mla-kv-cache and 21-inference-acceleration. Skip MLA and advanced acceleration as core work. Recalculate cache sizes and verify timing after warmup and explicit synchronization.

Also in this section

Stanford CS336 - Lecture 10 Inference
Stanford Universityrequiredtheory
Use the Spring 2026 inference lecture to connect KV arithmetic, phase behavior and batching vocabulary. Keep kernels, distributed serving and expensive performance experiments for the later tracks.
How to Scale Your Model - inference chapter
JAX MLdepththeory
After cache equivalence and phase measurement pass, read the inference chapter for arithmetic intensity, parallelism and production-scale reasoning. Treat it as the handoff to inference and performance tracks, not required foundation work.
AI Performance Engineering - inference-engine bridge
Waferdepthreference
Use Sections 4 and 5 only after this gate to choose the next inference, KV-cache, scheduling, quantization or distributed-serving resource. Do not treat its GPU and kernel material as unfinished LLM Foundations work.
No Magic - micro KV or paged-cache simulation
No Magicoptionalpractice
Use one small CPU simulation such as microkv.py or micropaged.py only to visualize state ownership. Do not present Python timing as GPU or serving-performance evidence.