KV-cache optimization: Visual walkthrough — AI-ML deep dive

Before we start, three words we will use over and over. We define them once, in plain language, and never before:

Step 1 — One word at a time (what "autoregressive" means)

WHAT. A model like GPT writes text one token at a time. To write token 4 it must first have written tokens 1, 2, 3. It cannot skip ahead.

WHY. This left-to-right rule is called causality: a word may only look at words before it, never after. That single restriction is the seed of everything on this page — it is exactly what makes past work reusable.

PICTURE. Each new step adds one square on the right. The arrows show that a new word looks backward only — never forward.

token 1 x_{1} \to token 2 x_{2} \to token 3 x_{3} \to new x_{4}

$x_{t}$ — the embedding (a list of numbers) of the word at position $t$ .
The $\to$ arrows mean "generated after," strictly left to right.

Step 2 — What each new word must compute

WHAT. When word $x_{t}$ arrives, the model multiplies it by three fixed weight-matrices to make its three characters:

Q_{t} = W_{Q} x_{t}, K_{t} = W_{K} x_{t}, V_{t} = W_{V} x_{t}

$W_{Q}, W_{K}, W_{V}$ — fixed number-tables (learned during training, frozen now). "Fixed" is the key word.
$x_{t}$ — the incoming word vector, length $d$ .
$Q_{t}, K_{t}, V_{t}$ — the three output vectors, each also length $d$ .

WHY. Because $W_{K}$ and $W_{V}$ never change during generation, the key and value a word produces are stamped once and stay forever. This is the deep reason caching is even possible — nothing about $K_{1}$ depends on how many words come later.

PICTURE. The word enters the box on the left; three arrows leave with $Q, K, V$ . Notice $K$ and $V$ carry a little padlock 🔒 — once made, they are frozen.

Step 3 — The naive way: recompute everything (the growing staircase)

WHAT. Suppose we do not cache. To generate token $t$ , a plain transformer treats the whole prefix as a brand-new sequence and recomputes $K_{1}, V_{1}, \dots, K_{t}, V_{t}$ from scratch — even though $K_{1}$ was already computed $t - 1$ times before.

WHY. A raw forward pass has no memory between steps. It only knows "here is a sequence of $t$ tokens, produce their projections." So the work per step grows with $t$ .

PICTURE. Each step is a bar; step $t$ is $t$ blocks tall. Together they form a triangle — a staircase that keeps getting taller.

Cost of one word's projection is roughly $d^{2}$ multiply-adds (a length- $d$ vector times a $d \times d$ table). At step $t$ we redo this for $t$ words:

work at step t = words redone t \times cost each d^{2}

Add up every step from $1$ to $L$ :

t = 1 \sum L t d^{2} = d^{2} \frac{L ( L + 1 )}{2} = O (L^{2} d^{2})

$\sum_{t = 1}^{L} t$ — "1 + 2 + 3 + … + L," the area of the triangle, equal to $\frac{L ( L + 1 )}{2}$ .
The $L^{2}$ is the quadratic curse: double the text, quadruple the wasted work.

Step 4 — The cached way: compute once, remember (the flat road)

WHAT. Keep a notebook — the KV-cache. When word $t$ arrives, compute only its own $K_{t}, V_{t}$ (one word's worth), then glue them onto the notebook:

Cache_{K} \leftarrow [Cache_{K}; K_{t}], Cache_{V} \leftarrow [Cache_{V}; V_{t}]

The semicolon $;$ means "stack a new row underneath." The notebook grows by exactly one row per step.
Old rows are never touched — they are the frozen 🔒 keys/values from Step 2.

WHY. Because those old rows can never change (frozen weights, past words fixed), re-deriving them is pure waste. We pay the $d^{2}$ cost once per word, ever.

PICTURE. Now every step is the same height (one block). The staircase collapses into a flat road of length $L$ .

t = 1 \sum L one word 1 \times d^{2} = L d^{2} = O (L d^{2})

The inner count is now $1$ , not $t$ — that is the whole trick.

Step 5 — Where the factor $L$ is born (triangle ÷ rectangle)

WHAT. Divide the two totals.

Speedup = \frac{L ^{2} d ^{2} naive, triangle}{cached, road L d ^{2}} = L

WHY. The saving is exactly the sequence length. Write 2048 tokens → about 2048× less projection work. This is not an approximation trick; it is the ratio of a triangle's area to a rectangle's.

PICTURE. Overlay the tall triangle (naive) on the flat bar (cached). The triangle's area over the bar's area is the ratio $L /1$ — the factor $L$ made visible.

Step 6 — Attention still needs a Query (why $Q$ is NOT cached)

WHAT. We cache $K$ and $V$ . We do not cache $Q$ . At step $t$ we still compute a fresh $Q_{t}$ and score it against all cached keys:

scores_{t} = \frac{Q _{t} [ K _{1} , \dots , K _{t} ] ^{⊤}}{d _{k}}

$Q_{t}$ — the one fresh query for the new word (its curiosity is unique to it).
$[K_{1}, \dots, K_{t}]^{⊤}$ — every cached key, lined up as columns to compare against.
$d_{k}$ — a shrink factor that keeps the numbers from blowing up ( $d_{k}$ = size of one head); it does not affect the counting argument.

WHY. A Key/Value is "what a word offers" — that never changes, so cache it. A Query is "what the current word is asking" — a brand-new question every step, so it cannot be reused. Caching $Q$ would answer the wrong question.

PICTURE. One glowing new query arrow fires backward across all the padlocked keys. The query is new; the keys are all old-and-frozen.

Step 7 — Edge cases: the corners where things could break

WHAT. Check the boundaries so no reader ever hits an unshown case.

Case A — the very first token ( $t = 1$ ). The notebook starts empty. We compute $K_{1}, V_{1}$ , the cache becomes one row, and $Q_{1}$ attends to just itself. No division problem, no "attend to nothing" — the flat road has length 1.

Case B — the causal mask must still apply. Even with a cache, a word may only look at rows $\leq t$ . Since we append $K_{t}$ only when word $t$ arrives, the cache physically cannot contain future keys — the append order enforces the mask for free. (During prefill of a given prompt, an explicit mask is still applied.)

Case C — the sliding window (bounded memory). If we only ever keep the last $W$ rows, memory stops growing: $O (W)$ instead of $O (L)$ . The road becomes not just flat but of fixed length. Cost: words older than $W$ steps are forgotten. See sparse attention.

Case D — memory, the price we pay. Speed is free of extra memory per step, but the notebook itself grows linearly: $2 \times n_{layers} \times L \times h \times d_{k} \times bytes$ . This is the trade explored in inference optimization and shrunk further by quantization and multi-/grouped-query attention.

PICTURE. A single strip: an empty box (t=1), a triangle grayed-out above the diagonal (mask blocks the future), and a fixed-width window sliding along a long ribbon.

The one-picture summary

The tall triangle (recompute-everything) versus the flat road (compute-once), with the padlocked notebook feeding the fresh query — the whole derivation in a single frame.

Recall Feynman retelling — say it back in plain words

Imagine writing an essay where, before adding each new sentence, you re-read the entire essay from the start. Sentence 100 makes you re-read 99 sentences you already know. That re-reading is the naive cost — the growing staircase, $L^{2}$ .

Now imagine you keep a notebook of one summary line per sentence you've written. To add a new sentence you glance at the notebook (already there) and jot one new line. Same story, but your work per sentence is now constant — the flat road, $L$ .

Two facts make the notebook trustworthy: (1) the model's weights are frozen, so a past word's Key/Value can never change — safe to store; (2) you only ever write forward, so the notebook can never leak a future word — the causal rule holds for free. Divide the staircase by the road and out pops the speedup: exactly the sequence length $L$ . The one thing you can't store is the Query, because every new word asks a brand-new question.

Recall Quick self-check

Why is the naive projection cost $O (L^{2} d^{2})$ ? ::: Each step $t$ recomputes $t$ words' projections at $d^{2}$ each; summing $1 + 2 + \dots + L = \frac{L ( L + 1 )}{2} = O (L^{2})$ gives $O (L^{2} d^{2})$ . Why exactly $L$ speedup and not something else? ::: It's the ratio of the triangle area $\frac{L ^{2}}{2} d^{2}$ to the flat road $L d^{2}$ , which equals $L$ . Why cache $K, V$ but never $Q$ ? ::: $K, V$ = "what a past word offers," frozen and reusable; $Q$ = "what the current word asks," new every step. What enforces the causal mask automatically in cached generation? ::: We only append $K_{t}$ when word $t$ arrives, so future keys are never physically present in the cache.

See also: Transformer architecture · Beam search (multiplies cache by beam width) · LLM deployment.