KV-cache optimization: Worked examples — AI-ML deep dive

Before we start, one tiny reminder of the symbols we will lean on, so nobody is left behind:

Definition The four characters

$L$ — the sequence length, i.e. how many tokens are in the running so far. Picture a row of boxes, one per word.
$d$ — the model width (also called hidden size): how many numbers describe one token. Picture the height of each box.
$h$ — the number of heads: how many independent attention "viewpoints" the model runs in parallel. Picture each token's box sliced into $h$ thin vertical strips, one strip per head.
$d_{k}$ — the head dimension: how many numbers one attention head sees (the height of one strip). Usually $d = h \times d_{k}$ , so the strips reassemble into the full box.

A "K" or "V" for one token is a little rectangle of shape $h \times d_{k}$ (all strips, side by side). Stack $L$ of them and you get the cache: a $L \times h \times d_{k}$ block. That block is the star of every example below.

The scenario matrix

Every KV-cache question is really one of these cells. The examples that follow each declare which cell(s) they cover.

#	Case class	Concrete trigger	Covered by
A	Empty / first token ( $L = 1$ )	prefill of the very first token, cache starts empty	Ex 1
B	Growing cache, one step	append token $t$ , attend over $t$ positions	Ex 2
C	Prefill vs decode asymmetry	a whole prompt goes in at once, then decode one-by-one	Ex 3
D	Zero / degenerate input	$L = 0$ , or single-head ( $h = 1$ ), or $d_{k}$ tiny	Ex 4
E	Limiting behaviour ( $L \to \infty$ )	when does cache memory overtake model weights?	Ex 5
F	Head-layout variants	standard vs MQA vs GQA cache size	Ex 6
G	Real-world word problem	"will a 32 GB GPU serve this?" — deployment sizing	Ex 7
H	Exam twist	sliding window: cache stops growing, find the break-even token	Ex 8

We attack them in order. Cells A–C are the mechanics, D–E the edge and limit, F–H the engineering reality.

Example 1 — Cell A: the empty cache, first token

Forecast: Guess now — before we compute anything, how many rows does the cache have? And after one token?

Steps:

Before generation, the cache is empty. Its shape is $0 \times 4 \times 64$ — literally zero rows. Why this step? Caching is incremental; there is nothing to remember before the first token exists. This is the base case every loop starts from.
Compute the first token's projections: $K_{1} = W_{K} x_{1}$ and $V_{1} = W_{V} x_{1}$ , each of shape $4 \times 64$ . Why this step? $x_{1}$ is the embedding of token 1 (a length- $d$ vector). Multiplying by the fixed matrix $W_{K}$ produces this token's key across all 4 heads. Same for value. See the projection step.
Append. Cache goes from $0 \times 4 \times 64$ to $1 \times 4 \times 64$ . Why this step? Appending is the whole trick: we grow by exactly one row per token.
Count stored numbers. Two matrices (K and V), each $4 \times 64 = 256$ numbers: $2 \times 1 \times 4 \times 64 = 512 numbers = 512 \times 2 = 1024 bytes = 1 KB .$ Why this step? This is the per-token memory formula from the parent note, evaluated at $L = 1$ .

Verify: The attention for token 1 must attend only to position 1 — a $4 \times 1$ score (one score per head, one position). With a cache of exactly 1 row that is exactly what we get. Units check: $numbers \times bytes/number = bytes$ . ✓

Example 2 — Cell B: one growth step, the 3rd token

Forecast: How wide (how many columns) is the score row for token 3?

Steps:

Cache before: $2 \times 4 \times 64$ (tokens 1,2). Why this step? We only re-read; we never recompute $K_{1}, K_{2}$ . That is the point of the cache.
Compute the new token's key and value: $K_{3} = W_{K} x_{3}$ and $V_{3} = W_{V} x_{3}$ , each of shape $4 \times 64$ , where $x_{3}$ is token 3's embedding. Why this step? Only token 3 is genuinely new, so only its K and V need computing — the reusable "what previous tokens offer" pieces that we will append to the cache.
Compute the new query separately: $Q_{3} = W_{Q} x_{3}$ , also $4 \times 64$ — and we do not cache it. Why this step? $Q_{3}$ encodes "what token 3 is looking for". Every future token brings its own fresh query, and old queries are never re-attended, so caching $Q$ would waste memory for nothing (this is Mistake 1 in the parent). Keys and values are remembered; queries are always thrown away after one use.
Append K and V: cache becomes $3 \times 4 \times 64$ . ( $Q_{3}$ is not appended.)
Score shape. For each head, $Q_{3}$ (a $1 \times 64$ vector) dots against 3 cached keys ( $3 \times 64$ ): $scores = \frac{Q _{3} K _{1 : 3}^{⊤}}{64} \in R^{4 \times 3} .$ Why this step? One row per head (4), one column per attended position (3). The $d_{k} = 64 = 8$ scaling keeps the dot products from blowing up (from scaled dot-product attention).

Figure 1 — cache append and score fan-out. On the left, the two lavender rows are the frozen cache ( $K_{1}, K_{2}$ ) that we never recompute; the coral row ( $K_{3}$ , marked NEW) is the single row we just appended, making the cache $3 \times 4 \times 64$ . On the right, the mint box is the fresh query $Q_{3}$ — trace the three coral arrows: $Q_{3}$ reaches back to each of the 3 cached keys, and the vertical slate arrow (labelled "/ 8") divides by $64$ before the butter box collects the result: a $4 \times 3$ score, one row per head, three columns for the three attended positions. Notice $Q_{3}$ has no arrow into the cache — it is used once and discarded, exactly as step 3 argued.

Verify: Look at the figure — the new row (coral) is height-1, and the score arrow fans out to exactly 3 cached columns. Column count = current token index = 3. ✓ And $64 = 8$ , a clean integer. ✓

Example 3 — Cell C: prefill vs decode

Forecast: Will the cached run be roughly $L$ times cheaper, or something in between because of the big prefill chunk?

Steps:

Fix the unit. Projecting one token means multiplying its $d$ -vector $x_{t}$ by each of $W_{K}, W_{Q}, W_{V}$ (each $d \times d$ ), which costs $O (d^{2})$ multiply-adds. We call that one block. Projecting $n$ tokens is $n$ independent such products, so it costs exactly $n$ blocks — whether done one-at-a-time or fused into a single $(n \times d) \cdot (d \times d)$ batched matmul. Why this step? A batched matmul does not do less arithmetic than $n$ separate ones — it packs the same $n$ token-products into one call for hardware efficiency. So "10 tokens in one matmul" is still 10 blocks of work, not 1. This is why prefill of $P$ tokens costs $P$ blocks, not a constant.
Naive projection cost. At each token position $t$ the naive model recomputes K,V for all $t$ positions: $\sum_{t = 1}^{15} t = \frac{15 \cdot 16}{2} = 120$ blocks. Why this step? Without a cache, generating token $t$ treats the sequence as fresh — $t$ projections each time.
Cached projection cost. Prefill projects all $P = 10$ prompt tokens once (10 blocks, by step 1), then each of the $G = 5$ decode steps projects exactly 1 new token (5 blocks): $10 + 5 = 15$ blocks. Why this step? The cache means we never redo the prompt's K,V, and each decode step adds only its single new token.
Speed ratio. $120/15 = 8$ . Why this step? This is the concrete cash value of the theoretical " $\times L$ " speed-up — but it lands at 8, not 15, because the naive sum is $L (L + 1) /2$ , not $L^{2}$ , and the cached cost equals $L$ .

Verify: General check: naive $= \frac{L ( L + 1 )}{2}$ , cached $= L$ , ratio $= \frac{L + 1}{2}$ . For $L = 15$ : $\frac{16}{2} = 8$ . ✓ Matches step 4. The parent's " $\times L$ " is the big-O scaling; the exact ratio is $\frac{L + 1}{2}$ .

Example 4 — Cell D: degenerate inputs

Forecast: Which of these gives zero bytes, and which gives the smallest non-zero cache?

Steps:

(a) $L = 0$ . Total cache $= 2 \times L \times h \times d_{k} \times bytes = 0$ . Why this step? Empty sequence → nothing to store. Confirms the formula degrades gracefully; no divide-by-zero, no negative memory.
(b) $h = 1$ . Per token $= 2 \times 1 \times 64 \times 2 = 256$ bytes. Why this step? A single-head model collapses $h \times d_{k}$ to just $d_{k}$ . This is also the MQA per-token figure (one shared K/V) — a preview of Ex 6.
(c) $d_{k} = 1$ , $h = 8$ . Per token $= 2 \times 8 \times 1 \times 2 = 32$ bytes. Why this step? Shrinking the head dimension to 1 makes each key/value a single scalar. Still 8 heads, so 8 scalars for K + 8 for V = 16 numbers = 32 bytes.

Verify: (a) $= 0$ . ✓ (b) $256$ bytes, non-zero and smallest of the "real" cases per number of heads. (c) $32$ bytes is actually the smallest total here. Ordering: $0 < 32 < 256$ . ✓ Every formula stays finite and non-negative under degenerate inputs.

Example 5 — Cell E: the crossover limit ( $L \to \infty$ )

Forecast: Thousands of tokens? Millions? Guess the order of magnitude.

Steps:

Per-token full-model cache. $2 \times n_{layers} \times h \times d_{k} \times bytes = 2 \times 12 \times 12 \times 64 \times 2 = 36, 864$ bytes $= 36$ KB. Why this step? This is the parent's formula summed over layers, per token. Every new token adds this fixed slab.
Set cache = weights. Solve $L \times 36, 864 = 500 \times 1 0^{6}$ : $L = \frac{500 , 000 , 000}{36 , 864} \approx 13, 563 tokens .$ Why this step? Cache grows linearly in $L$ while weights are constant — so there is always a crossover. Past it, memory is dominated by cache, not the model.
Interpret the limit. As $L \to \infty$ the cache dwarfs everything: $lim_{L \to \infty} \frac{cache}{weights} = \infty$ . This is why MQA/GQA and sliding windows exist (Ex 6, 8). Why this step? The whole "advanced optimizations" section of the parent is a response to this unbounded growth.

Verify: $36, 864 \times 13, 563 \approx 5.0 \times 1 0^{8} = 500$ MB. ✓ Linear-in- $L$ growth means the ratio has no finite bound. ✓ (Here MB = $1 0^{6}$ bytes, decimal — see Ex 7 for a units clarification.)

Example 6 — Cell F: standard vs MQA vs GQA

Forecast: MQA should be some big divisor smaller. By exactly what factor, and where does GQA land?

Steps:

(a) Standard. $2 \times h \times d_{k} \times 2 = 2 \times 64 \times 128 \times 2 = 32, 768$ bytes $= 32$ KB. Why this step? Every query head keeps its own K and V. This is the baseline the parent's formula gives.
(b) MQA. One shared K/V head: $2 \times 1 \times 128 \times 2 = 512$ bytes. Why this step? MQA replaces $h$ K/V heads with a single one. Reduction $= 64/1 = 64 \times$ .
(c) GQA, $g = 8$ . $2 \times 8 \times 128 \times 2 = 4096$ bytes $= 4$ KB. Why this step? GQA keeps one K/V per group. With 8 groups the reduction is $64/8 = 8 \times$ — the parent's stated Llama-2 figure.

Figure 2 — cache size staircase. Three bars, tallest to shortest: the lavender bar is standard multi-head at 32,768 bytes/token/layer (all 64 K/V heads kept); the mint bar is GQA with 8 groups at 4,096 bytes (labelled "8x smaller"); the coral bar is MQA at 512 bytes (labelled "64x smaller"). Read left-to-right and the staircase drops each time we share K/V heads across more queries — the height literally is the memory bill, so a shorter bar is a cheaper cache. GQA sits deliberately between the two extremes: much of MQA's saving, little of its quality loss.

Verify: Standard $32768$ B; MQA $512$ B → ratio $32768/512 = 64$ . ✓ GQA $4096$ B → ratio $32768/4096 = 8$ . ✓ GQA sits between MQA and standard, exactly as the figure's staircase shows. ✓

Example 7 — Cell G: real-world deployment sizing

Forecast: With plenty of GPU headroom, is the cache even a problem here — yes or no?

Steps:

Per-user cache (standard). From Ex 5, per-token full-model cache $= 36, 864$ bytes. For 2048 tokens: $2048 \times 36, 864 = 75, 497, 472$ bytes. In binary MiB ( $/ 2^{20}$ ): $75, 497, 472/1, 048, 576 = 72.0$ MiB exactly. Why this step? One user's cache = per-token slab $\times$ context length. The bytes divide cleanly by $2^{20}$ , so 72 MiB is exact, not rounded.
8 users + weights. $8 \times 72 MiB + 500 MiB = 576 + 500 = 1076$ MiB $\approx 1.05$ GiB. Why this step? Concurrent requests each need their own cache; weights are shared once. Total must fit the 32 GiB budget.
Fit check. $1076 MiB ≪ 32 \times 1024 = 32, 768 MiB$ → yes, fits easily. After reserving weights, budget for caches $= 32, 768 - 500 = 32, 268$ MiB, so $max users = ⌊ \frac{32 , 268}{72} ⌋ = ⌊ 448.2 ⌋ = 448 users (standard) .$ Why this step? The cache, not the weights, is the scaling bottleneck for concurrency — this is the core inference-optimization insight.
MQA switch. MQA shrinks K/V by the head factor $h = 12$ , so per-user cache $= 72/12 = 6$ MiB. Max users $= ⌊ 32, 268/6 ⌋ = 5378$ . Why this step? Cutting cache $12 \times$ multiplies serveable concurrency by roughly $12 \times$ (448 → ~5378). This is why production LLMs use MQA/GQA — see deployment.

Verify: Standard: $8 \times 72 + 500 = 1076$ MiB, and $1076 < 32768$ MiB. ✓ Max standard users $= 448$ ; MQA $= 5378$ ; ratio $\approx 12$ . ✓ Units: MiB / (MiB/user) = users, all binary throughout. ✓

Example 8 — Cell H: exam twist, sliding window break-even

Forecast: Does the window cache save memory from token 1, or only after some threshold?

Steps:

Growth laws. Full cache rows $= t$ (grows forever). Window cache rows $= min (t, W) = min (t, 512)$ . Why this step? Sliding window drops the oldest token once you exceed $W$ , so its size plateaus at 512 — constant memory, from the parent's "Sliding Window" section.
First difference. For every $t \leq 512$ both caches hold $t$ rows (nothing dropped yet), so they are identical. At $t = 513$ the full cache has 513 rows but the window has already evicted token 1 and holds only $min (513, 512) = 512$ . So they first differ at $t = 513 = W + 1$ . Why this step? Below the window size there is no saving at all; the saving begins exactly one token past $W$ . That threshold $t = W + 1$ is the "break-even" the question asks for.
Ratio at $t = 4096$ . Full $= 4096$ rows; window $= min (4096, 512) = 512$ rows. $ratio = \frac{4096}{512} = 8.$ Why this step? At long context the window is $8 \times$ smaller here — the tradeoff is losing dependencies older than 512 tokens (relevant to long-horizon decoding where distant context can matter).
Limit behaviour. Window memory is $O (W)$ constant while full is $O (t)$ linear, so as $t \to \infty$ the ratio $t / W \to \infty$ : the saving grows without bound. Why this step? This is the whole point of sliding-window attention for 100K+ token contexts — memory stops growing entirely.

Verify: $min (513, 512) = 512 \neq = 513$ and $min (512, 512) = 512 = 512$ → first divergence at $t = 513 = W + 1$ . ✓ $4096/512 = 8$ . ✓ Ratio $t / W$ is unbounded as $t \to \infty$ . ✓

Recall Self-check

With-cache projection cost vs naive, exact ratio for length $L$ ? ::: $\frac{L + 1}{2}$ (not $L$ — that's the big-O). When does KV-cache first differ from a length- $W$ window cache? ::: At token $t = W + 1$ . MQA cache reduction factor vs standard multi-head with $h$ heads? ::: $h \times$ (one shared K/V head). Why is $Q$ never cached? ::: Each new token needs a fresh query ("what it's looking for"); old queries are never re-attended. Per-token full-model cache formula? ::: $2 \times n_{layers} \times h \times d_{k} \times bytes$ .

Related: 6.3.1-model-quantization shrinks the bytes-per-number factor in every formula above — orthogonal to head-count tricks, and stacks with them.