KV-cache vs. naive
From Chapter 29 of Large Language Models from the Ground Up. Generating text one token at a time, a naive model re-derives every previous token's keys and values on every single step. The KV-cache stores them once and appends just the new row. The saving is quadratic.
Generate a sequence of length T, both ways
Pick a target length, then Play. Each step, the naive panel fills a whole new row of the T×T work triangle; the cached panel adds a single row. The counters and waste factor update live.
Generated 0 / 64 tokens.
Naive — recompute all
Step i redoes the K/V for positions 1…i. The lit triangle is the wasted work.
KV-cache — append one
Earlier rows are stored, not recomputed. Step i computes exactly one new K/V row.
The naive side fills a triangle — about T²⁄2 cells — while the cache fills a single column of T cells. That gap is why the KV-cache is non-optional in production. At T = 128 the naive model does ≈64× the work; at an 8k context it is ≈4,000×. The cache trades compute for memory: those stored rows are exactly the "KV-cache" that dominates GPU memory during long-context inference (Chapter 29 sizes it, and Chapters 29/30 show how GQA and sliding windows shrink it).