THE TRANSFORMER DEEP CUTS · CHAPTER 06
Generating text one token at a time repeats a lot of work. The KV cache removes the repetition. Then the cache itself becomes the problem. This chapter is about both.
Picture a reader working through a long mystery novel. After each page, they write one index card. The card's title says what the page is about ("the gardener lied"). The card's body holds the detail.
When a new question comes up ("who had the key to the shed?"), the reader does not reread the whole book. They hold the question against the card titles, pick the cards that match, and read those bodies.
That is attention. The query is the question, the keys are the card titles, and the values are the card bodies. Keeping the cards between pages, instead of rewriting them all, is the KV cache.
The rest of this chapter is about the size of the card box. The cache makes each step cheap. But every card for every past token stays in memory. Long contexts and many users fill that memory fast. MQA, GQA and sliding windows are three ways to keep fewer cards.
A decoder-only model writes text in two phases.
Here is the catch. Without a cache, every decode step pushes the entire sequence through every layer again. But in a causal model, a past token's keys and values never change. Token 3 cannot see token 7, so adding token 7 leaves token 3's numbers exactly as they were. We are recomputing answers we already have.
Interactive · Decoding step by step
How much work does each decode step do, with and without a cache?
The waste grows fast. Start from a one-token prompt and generate 1,000 tokens. Without a cache, the model processes \(1 + 2 + \dots + 1000\) = 500,500 token-passes. With a cache, it processes 1,000, one per step.
Past keys and values never change in a causal model, so compute each one once and keep it.
Symbols used in this chapter:
| Symbol | Meaning | Llama 3 8B |
|---|---|---|
| L | number of layers | 32 |
| H | query heads per layer | 32 |
| H_kv | key/value heads per layer | 8 |
| d_h | size of one head | 128 |
| b | bytes per number (bf16 = 2) | 2 |
| T | tokens in the sequence so far | — |
| B | sequences in the batch (users) | — |
At decode step \(t\), one head only needs the newest token's query \(q_t\), plus the keys and values of every token so far:
the output for the newest token is a weighted mix of all values so far. The weights come from how well its query matches each key.
So each step adds just one row to each matrix:
take the cached keys and values, and append the new token's key and value at the bottom.
Why not cache queries too? Because a past query is never used again. Only the newest token asks a question. Old tokens' questions were already answered in earlier steps.
prefill → decode → append K/V → never cache Q
One cache per layer. append grows it along the token axis. gqa_attention works for a whole prompt (prefill) and for one new token (decode). It also handles shared key/value heads, which we need in section 06.
import torch import torch.nn.functional as F class KVCache: """Keys and values of every token seen so far, for one layer.""" def __init__(self): self.k = None # (batch, n_kv_heads, tokens_seen, head_dim) self.v = None def append(self, k_new, v_new): if self.k is None: self.k, self.v = k_new, v_new else: self.k = torch.cat([self.k, k_new], dim=2) self.v = torch.cat([self.v, v_new], dim=2) return self.k, self.v def gqa_attention(q, k, v): """q: (B, n_heads, T_new, d) k, v: (B, n_kv_heads, T_all, d)""" group = q.shape[1] // k.shape[1] # query heads per KV head k = k.repeat_interleave(group, dim=1) # each KV head serves its group v = v.repeat_interleave(group, dim=1) t_new, t_all = q.shape[2], k.shape[2] scores = q @ k.transpose(-2, -1) / q.shape[-1] ** 0.5 # Causal mask. The new queries sit at the END of the sequence. pos_q = torch.arange(t_all - t_new, t_all).unsqueeze(1) pos_k = torch.arange(t_all).unsqueeze(0) scores = scores.masked_fill(pos_k > pos_q, float("-inf")) return F.softmax(scores, dim=-1) @ v
torch.cat(..., dim=2) — dim 2 is the token axis, so the cache grows by one row per step.pos_q — during decode, t_new = 1 and the single query sits at the last position. The mask then lets it see every cached token.q, k, v inputs come from the usual linear projections of the new token. With RoPE, rotate k before appending it.In a causal model, token \(i\)'s hidden state in layer \(\ell\) depends only on tokens \(1 \dots i\) in layer \(\ell - 1\). By induction over layers, nothing about token \(i\) changes when later tokens arrive. So its key and value in every layer are fixed the moment it is processed. The cached run and the uncached run do the same arithmetic on the same numbers. Results match up to floating-point rounding. The check script confirms this for MHA, GQA and MQA.
Every layer stores one key and one value vector per KV head, per token. Multiply it out:
two tensors (K and V), times layers, times KV heads, times head size, times bytes per number. Then times tokens and users.
For Llama 3 8B, one token costs \(2 \cdot 32 \cdot 8 \cdot 128 \cdot 2\) = 131,072 bytes = 128 KiB. That sounds small. Now scale it.
You serve Llama 3 8B to 32 users at once. Each conversation is 8,192 tokens long.
The cache is twice the size of the model. The weights are shared by every user, but each user brings their own cache. That is why the cache, not the model, usually limits how many users fit on one GPU.
128 KiB → 1 GiB → 32 GiB → weights 15 GiB
| Model | Attention | KV heads | Cache per token |
|---|---|---|---|
| Llama 2 7B | MHA | 32 | 512 KiB |
| Llama 3 8B | GQA | 8 | 128 KiB |
| Llama 3 70B | GQA | 8 | 320 KiB |
| Mistral 7B | GQA + sliding window | 8 | 128 KiB, capped at 4,096 tokens |
Interactive · Cache calculator
When does the cache outgrow the model?
Decoding is limited by memory traffic, not math. Each step reads all the weights plus the whole cache from GPU memory, just to produce one token per user. A smaller cache means more users per GPU and faster steps.
The cache formula has one knob that does not change what the model can compute per token: \(H_{kv}\). In standard multi-head attention (MHA), every query head has its own key and value head, so \(H_{kv} = H\).
Multi-query attention (MQA, Shazeer 2019) keeps all \(H\) query heads but gives them a single shared key head and value head. Back to the notebook: 32 readers still ask 32 different questions, but they all look at one shared card box.
PaLM and Falcon-7B used MQA. Most newer models use the middle ground below.
Grouped-query attention (GQA, Ainslie et al. 2023) splits the query heads into \(H_{kv}\) teams. Each team shares one key head and one value head.
every group of g neighbouring query heads reads the same keys and values.
Interactive · Head groups
With 8 query heads, which heads share keys and values?
| Tensor | Shape | Note |
|---|---|---|
| new token's hidden state | (B, 1, 4096) | \(H \cdot d_h = 32 \cdot 128\) |
| q | (B, 32, 1, 128) | one query per head |
| k, v for the new token | (B, 8, 1, 128) | only 8 heads are projected |
| cache K and V after appending | (B, 8, T, 128) | this is what lives in memory |
K, V after repeat_interleave | (B, 32, T, 128) | a view for the math, not stored |
| attention scores | (B, 32, 1, T) | still 32 heads of scores |
GQA shrinks what is stored and read. The score math still runs for all 32 query heads. Real kernels skip the copy and index the shared head directly.
Llama 2 70B, every Llama 3 model and Mistral 7B use GQA with 8 KV heads. The original paper found quality close to MHA, at speed close to MQA.
You do not have to train from scratch. Ainslie et al. convert an MHA checkpoint by mean-pooling the key and value projection weights of the heads in each group into one head. Then they continue training ("uptraining") for about 5% of the original pre-training compute. The converted model recovers most of the MHA quality.
MQA and GQA shrink the cost per token. A sliding window attacks the other factor, \(T\). Each token attends only to the last \(W\) tokens, itself included:
causal → window → −∞ rest → i mod W
look back at most W − 1 tokens. Anything older is outside the window.
A token outside the window still matters, just indirectly. Layer 1 lets token \(i\) see back \(W\) tokens. Layer 2 sees tokens that themselves saw back \(W\). After \(L\) layers, information can travel about \(L \cdot W\) tokens. For Mistral 7B, 32 × 4,096 = 131,072, so about 131K tokens.
If no token ever looks back more than \(W\), the cache never needs more than \(W\) slots. Mistral stores token \(i\) in slot \(i \bmod W\), overwriting the oldest entry:
the slots are used in a circle. When the buffer is full, the newest token replaces the one W steps back.
With a 4,096-token window, a Mistral 7B conversation never holds more than 128 KiB × 4,096 = 512 MiB of cache. At 32,768 tokens, a full cache would need 4 GiB, so the window saves 8×.
Interactive · Window and buffer
Which past tokens can a token see, and where are they stored?
Rolling buffer after the current token:
Some newer models mix the two. Gemma 2 alternates sliding-window layers with full-attention layers, so some layers keep long-range memory while the rest stay cheap.
Every idea in this chapter shrinks one factor of \(2 \cdot L \cdot H_{kv} \cdot d_h \cdot b \cdot T \cdot B\).
| Idea | Factor it shrinks | Cache per token* | Quality | Used by |
|---|---|---|---|---|
| MHA | — (baseline) | 512 KiB | baseline | GPT-2, Llama 2 7B |
| MQA | \(H_{kv} \to 1\) | 16 KiB | small drop | PaLM, Falcon-7B |
| GQA | \(H_{kv} \to\) a few | 128 KiB | close to MHA | Llama 3, Mistral 7B |
| Sliding window | \(T \to W\) | same per token, capped length | loses direct long-range view | Mistral 7B, Gemma 2 (mixed) |
| MLA | replaces K and V with a small latent | 576 numbers per layer | at or above MHA | DeepSeek-V2, V3 |
The last row is a different kind of trick. Instead of sharing keys and values, MLA compresses them. DeepSeek-V3 caches just 576 numbers per token per layer (a 512-number latent plus a 64-number position key). That idea gets its own chapter in Decoding DeepSeek.
"The cache stores attention scores." It stores keys and values. Scores depend on the new query, so they are recomputed every step.
"GQA reduces the attention math." Mostly it reduces memory and memory traffic. All query heads still compute their own scores.
Caching keys before RoPE. With rotary positions, rotate each key by its own position first, then cache it. Otherwise you must re-rotate the whole cache every step.
"A window of W means the model forgets everything older." Stacked layers pass information further back, about \(L \cdot W\) tokens. The view is indirect, but it exists.
Sizing a server by model weights alone. The weights are shared. The cache is per user and grows with context. Size for the cache.
Only the newest token's query is ever used. Past queries were consumed in earlier steps and are not needed again.
\(g = 32 / 8 = 4\) query heads per KV head. The cache is 4× smaller (128 KiB vs 512 KiB per token).
The weights stay the same, because they are shared. The cache doubles.
Slot \(9 \bmod 4 = 1\). It overwrote token 5.
No. It produces the same numbers as a full pass, up to floating-point rounding. It only skips repeated work.