The KV cache
When a model writes text, it keeps the keys and values of all earlier tokens in GPU memory so it never has to compute them again. This store, the KV cache, turns generation from quadratic work into linear work, but it grows with every token and every user. This session shows why only K and V are cached, how to compute the cache size of any model from its config file, and why weights plus KV cache decide how long a context and how big a batch one GPU can serve.
What you will learn
- Why caching keys and values gives exactly the same output, and why queries, attention scores and outputs are not cached
- How much work the cache saves: the token count with and without a cache
- The size formula 2 · L · n_kv · d_h · bytes per token, and how to read it from a config file without the usual traps
- How MHA, GQA, MLA, sliding windows and lower precision change the cache
- Peak memory ≈ weights + KV cache: how to compute the largest batch or the longest context that fits on a GPU
- Why each decode step must read the whole cache, and when the cache costs more time than the weights
- Why reserving memory for the maximum length wastes most of it, and how paging (vLLM) fixes this
Why this matters
To write token number 4,001, a language model must attend to the 4,000 tokens before it. Computing their keys and values again at every step would be far too slow. So the model computes them once and keeps them in GPU memory. This store is the KV cache. It is the single most important data structure in LLM inference: it makes generation fast, and it is also what fills the GPU.
Two numbers show the problem. The vLLM paper looks at OPT-13B, a model with 40 layers and width 5,120. Its cache needs about 800 KB for every token, and up to 1.6 GB for one request of 2,048 tokens. On a 40 GB A100, about 65% of the memory holds the weights and close to 30% holds the cache. [Certain, numbers from the vLLM paper] So the number of users one GPU can serve at the same time is set by the cache, not by the speed of the GPU. The efficient-inference survey states the rule we will use all session: the peak memory of generation is approximately the memory of the model weights plus the memory of the KV cache. [Certain, survey Section 2.2]
Session 26 introduced the cache and the size formula, and showed how MQA, GQA and MLA shrink it. In session 78 we split generation into prefill (process the prompt in parallel) and decode (one token per step), and session 79 chose the next token from the logits. This session looks at the cache itself, as an engineer who must serve a model:
- Why we cache K and V, and why not Q (or the attention output, or the hidden state).
- How much compute the cache saves, and what it costs in memory, with real models.
- How MHA, GQA and MLA change the cache, and how to read a config file without the classic traps.
- Peak memory ≈ weights + KV cache: the largest batch and the longest context that fit on a GPU.
- Why each decode step reads the whole cache, and why reserving memory for the longest possible answer wastes most of it.
Interviewers ask about this all the time: “Why not cache the queries?”, “How big is the cache of Llama 3 70B at 32k tokens and batch 8?”, “Your 70B model fits on two GPUs; why can it serve almost nobody?”, “Why does the time per token grow with context length?”. By the end you can answer each one with a formula and a number. The next session, session 81, turns these memory numbers into latency and throughput.
Generation with and without a cache
What a new token needs
Look at one attention layer during decoding. The new token sits at position \(t\). Its hidden vector \(\mathbf{h}_t\) gives a query, a key and a value for each head, as in session 19. Its output is a weighted sum over all positions up to \(t\):
- Read the symbols
- \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t\)
- the query, key and value of the new token (for one head; every head does the same)
- \(d_h\)
- the size of one head (128 in most large models)
- \(K_{1:t-1}, V_{1:t-1}\)
- the keys and values of all earlier tokens, one row per token. This is the KV cache of this layer and head.
- the stacking on the right
- a decode step adds exactly one new row to \(K\) and one to \(V\); the old rows stay as they are
Read (80.1) from the point of view of memory. The new token needs three kinds of things:
- Its own query \(\mathbf{q}_t\). It is used in this step and never again: a later token \(t' \gt t\) uses its own query \(\mathbf{q}_{t'}\), not \(\mathbf{q}_t\).
- The keys and values of all earlier tokens. Every later step needs them again.
- Its own key and value. Needed now, and by every later token.
So keys and values are written once and read at every later step; queries are read once. This is the whole reason why the cache holds K and V. [Certain]
Why the old keys and values never change
There is a condition hidden here: the stored rows must stay correct when new tokens arrive. They do, because of the causal mask (session 18). In layer 1, the key \(\mathbf{k}_j = W^K \mathbf{h}_j\) depends only on token \(j\). The output of layer 1 at position \(j\) attends only to positions \(\le j\). So the input of layer 2 at position \(j\) depends only on tokens \(1, \dots, j\), and so on through all layers. Adding token \(t\) cannot change anything at positions \(j \lt t\). So every cached row is still exactly right. [Certain]
This also tells us when a cache does not work. In a bidirectional encoder such as BERT, every position looks at every other position. A new token would change the hidden states of all earlier tokens, so every stored key would be stale. That is why encoders do not generate text token by token with a cache. A prefix LM (bidirectional over the prompt, causal over the answer) can still cache: the prompt is fixed once prefill is done.
How much work the cache saves
Count how many token positions go through the full model (all layers, all matrix multiplications) to produce \(N\) new tokens after a prompt of \(P\) tokens:
- No cache: to make each new token, run the model on the whole sequence so far. The first token needs \(P\) positions, the second \(P+1\), and the last \(P + N - 1\).
- With cache: prefill runs the \(P\) prompt positions once; each later step runs only the one newest token.
- Read the symbols
- \(P\)
- prompt length in tokens
- \(N\)
- number of tokens to generate
- rows
- token positions pushed through every layer. Each row costs about \(2 \times\) (number of parameters) FLOPs (session 25).
- \(N - 1\)
- the last generated token is never fed back in, so it never gets a cache row
Without a cache the work grows with \(N^2\); with a cache it grows with \(N\). For \(P = N = 1{,}000\): \(1{,}499{,}500\) rows against \(1{,}999\), a factor of 750. The cache does not remove all growth: each decode step still computes \(t\) attention scores against the cache, so attention work per step grows with \(t\). But this part is small next to the matrix multiplications at normal lengths, and it does not repeat the projections and the MLP for old tokens.
Figure 1 runs this loop for real on a tiny model. One attention head with \(d_h = 4\) reads the text “The cat sat on the mat and purred”. Every number you see (the query, the cached keys and values, the scores, the softmax weights and the output) is computed in your browser at each step, with formula (80.1). Switch to “no cache” to see the same step done by recomputing every row.
- \(\mathbf{x}_t \leftarrow\) embed(token \(t\)) // prefill: all \(P\) rows
- \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t \leftarrow W^Q\mathbf{x}_t,\ W^K\mathbf{x}_t,\ W^V\mathbf{x}_t\)
- append \(\mathbf{k}_t, \mathbf{v}_t\) to the cache \(K, V\)
- \(s_j \leftarrow \mathbf{q}_t \cdot \mathbf{k}_j / \sqrt{d_h}\) for \(j = 1, \dots, t\)
- \(\alpha \leftarrow \softmax(s)\)
- \(\mathbf{o}_t \leftarrow \sum_j \alpha_j \mathbf{v}_j\)
- emit the next token; \(t \leftarrow t + 1\)
How to read Figure 1
Press Play, or Step through it. The first five steps are prefill: the four prompt rows are projected in parallel, their keys and values are stored, and the last row (“on”) attends to all four keys; the other prompt rows do the same over their own prefixes, which we do not draw. Then each decode step does five things for one new token: project it (one thick row), append its key and value to the cache (they pop in), score the query against every cached key, turn the scores into softmax weights (purple bars), and mix the values into \(\mathbf{o}_t\). Old queries are shown as empty dashed boxes: nobody needs them again. Now switch to “no cache”: at every step all rows are recomputed (all thick), and the panel checks that the recomputed keys are exactly the cached ones (difference 0). The bars at the bottom grow 4, 5, 6, 7 with a cache and 4, 9, 15, 22 without. With a prompt of 2 tokens they grow 2, 3, …, 7 and 2, 5, 9, 14, 20, 27. The final token, “purred”, is generated but never fed back in, so it has no cache row.
Why not cache something else?
A good interview answer also explains the other options.
- Cache the queries? Useless: an old query is never used again (see 80.1).
- Cache the attention scores or attention outputs? The scores of the new token are against all old keys, and they are new every step. The outputs \(\mathbf{o}_j\) of old tokens are not needed at all: after layer \(\ell\), the old token’s contribution to the future is fully contained in its keys and values of layer \(\ell + 1\).
- Cache the hidden state \(\mathbf{h}_j\) and recompute K and V from it? This is a real option. It stores \(d\) numbers per layer instead of \(2 n_{kv} d_h\). For Llama 2 7B (MHA, \(d = 4096\), \(2 n_{kv} d_h = 8192\)) that halves the memory. But every decode step must then multiply all \(t\) stored hidden states by \(W^K\) and \(W^V\) again, which is exactly the work the cache was meant to avoid. For a GQA model like Llama 3 8B, \(2 n_{kv} d_h = 2048\) is already smaller than \(d = 4096\), so there is nothing to win. [Certain, from the shapes] MLA (session 26) is the smart version of this idea: it caches a small learned latent vector and folds the up-projection into the query, so no recomputation is needed.
The cache as a data structure
In code the cache is a pair of tensors per layer. A common layout is (batch, key–value heads, tokens, head size), so the whole cache is
- Read the symbols
- \(L\)
- number of layers; each layer has its own cache, because each layer has its own keys and values
- \(B\)
- number of sequences served together (the batch)
- \(n_{kv}\)
- number of key–value heads: \(n_h\) for MHA, fewer for GQA, 1 for MQA
- \(T\)
- number of tokens stored so far; it grows by one at every decode step
Hugging Face transformers uses this layout in its default “dynamic” cache and appends with a concatenation at each step. [Likely] Concatenation copies the whole tensor, so the copying grows with \(T\) at every step. Fast systems avoid this: they preallocate a buffer and write into it (a “static” cache, which also suits CUDA graphs and torch.compile), or they store the cache in fixed-size blocks (vLLM’s PagedAttention, below).
- input: prompt tokens \(x_1, \dots, x_P\); model with \(L\) layers; maximum new tokens \(N\)
- prefill: run all \(P\) tokens in parallel with a causal mask; in every layer \(\ell\) store \(K^{(\ell)}_{1:P}, V^{(\ell)}_{1:P}\) // one big matrix multiply per weight
- \(y_1 \leftarrow\) choose from the logits of position \(P\) // greedy, sampling, ... (session 79)
- for \(n = 1, \dots, N-1\):
- \(t \leftarrow P + n\) // position of the token fed in now = current cache length + 1
- embed \(y_n\); in each layer: compute \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t\) (RoPE at position \(t\))
- append \(\mathbf{k}_t, \mathbf{v}_t\) to the layer’s cache
- attend \(\mathbf{q}_t\) to all \(t\) cached keys and values, formula (80.1); no mask needed: the cache holds only the past
- \(y_{n+1} \leftarrow\) choose from the logits; stop at the end-of-sequence token
- return \(y_1, \dots, y_N\); free the cache (or keep it for the next turn of the chat)
The last line matters in chat. The next user message starts with the whole conversation so far. If the server keeps the cache of that prefix, the next prefill only needs the new message. This is prefix caching, covered in session 134.
The size formula
Count the numbers in (80.3): two tensors (K and V) per layer, each with \(n_{kv} \cdot d_h\) numbers per token. Multiply by the bytes per number and by the tokens of all sequences:
- Read the symbols
- \(s\)
- the cache size of one token, over all layers. Learn this number for the models you use.
- \(2\)
- one key and one value
- \(b\)
- bytes per number: 2 for bfloat16 or float16, 1 for FP8 or INT8
- \(T_i\)
- the current length (prompt + generated so far) of sequence \(i\). With equal lengths the sum is just \(B \cdot T\).
The cache grows linearly with context and with batch. The weights do not grow at all. Writing the cost per token, as \(s\), makes capacity questions easy: “how many tokens fit” is just “free memory ÷ \(s\)”.
OPT-13B (the vLLM example; MHA, \(L = 40\), \(n_h d_h = 5120\), FP16): \(s = 2 \times 40 \times 5120 \times 2 = 819{,}200\) bytes = 800 KiB per token. A request of 2,048 tokens: \(819{,}200 \times 2048 = 1.68 \times 10^9\) bytes, the “1.6 GB” of the paper.
Llama 3 8B (GQA, \(L = 32\), \(n_{kv} = 8\), \(d_h = 128\), bfloat16): \(s = 2 \times 32 \times 8 \times 128 \times 2 = 131{,}072\) bytes = 128 KiB. One sequence of 8,192 tokens: 1 GiB. Of 131,072 tokens (its full context): 16 GiB, about as big as its 16.1 GB of weights.
Llama 3 70B (GQA, \(L = 80\), \(n_{kv} = 8\), \(d_h = 128\)): \(s = 327{,}680\) bytes = 320 KiB. A batch of 8 sequences of 32,768 tokens: \(327{,}680 \times 32{,}768 \times 8 = 85.9\) GB = 80 GiB, a whole GPU just for the cache.
Formula (80.4) is easier to feel when it runs. Figure 2 serves a batch of \(B\) requests on one 80 GB GPU and lets the decode loop run. At every frame, each request has grown by the same number of tokens. The cache bar grows in a straight line, one strip per request, until weights plus cache hit the 90% line and the server runs out of memory. The right panel counts the compute of the same run, with and without a cache, using (80.2) and about \(2 \times\) (number of parameters) FLOPs per row.
- \(s \leftarrow 2 \cdot L \cdot n_{kv} \cdot d_h \cdot b\) // (80.4)
- \(M_W \leftarrow N_{\text{params}} \cdot 2\); prefill: \(T \leftarrow P\)
- repeat (one decode step for all \(B\) requests):
- \(T \leftarrow T + 1\)
- \(M_{\text{KV}} \leftarrow s \cdot B \cdot T\)
- if \(M_W + M_{\text{KV}} \gt u\, M_{\text{GPU}}\): stop, out of memory
- rows: cache \(+B\); no cache \(+B \cdot T\) // (80.2)
- \(t_{\text{step}} \ge (M_W + M_{\text{KV}}) / \text{BW}\) // (80.9)
How to read Figure 2
Press Play with Llama 3 8B and \(B = 16\). The strips grow together, in a straight line, because every request adds \(s\) = 131,072 bytes per token. The run stops at \(T\) = 26,674 tokens: there 16 caches of 3.5 GB each plus 16.06 GB of weights reach 72 GB. Now set \(B = 64\): it stops at 6,668 tokens, four times earlier, because \(B \cdot T\) is fixed. Switch to Llama 2 7B: its MHA cache is 4 times larger per token, and the run stops about 4 times earlier (6,976 tokens at \(B = 16\)). Qwen2.5 7B, with 4 key–value heads, goes furthest. In the right panel, the orange curve bends upward (quadratic) while the green one stays a straight line close to zero: at \(T = 8{,}192\) the run without a cache needs about 4,000 times more compute. The panel under the plots also shows the lower bound on the step time, which grows with the cache.
Reading the formula from a config file
All four numbers are in the model’s config.json: num_hidden_layers (\(L\)), num_key_value_heads (\(n_{kv}\)), head_dim (\(d_h\)) and torch_dtype (\(b\)). Two traps catch many people:
- \(d_h\) is not always hidden size ÷ heads. Mistral NeMo 12B has
hidden_size5120, 32 query heads and 8 key–value heads, buthead_dim= 128, not 5120 / 32 = 160. [Certain, from its config.json] The correct cache is \(2 \times 40 \times 8 \times 128 \times 2 = 163{,}840\) bytes = 160 KiB per token; using 160 gives 200 KiB, 25% too much. If the file hashead_dim, use it. - MLA models report a misleading head count. DeepSeek-V3’s config has
num_key_value_heads= 128, but it does not cache 128 heads. It caches one latent ofkv_lora_rank= 512 numbers plus one RoPE key ofqk_rope_head_dim= 64 numbers per layer, over 61 layers. [Certain, from its config.json] That is \(61 \times 576 \times 2 = 70{,}272\) bytes = 68.6 KiB per token in bfloat16. The naive formula with 128 heads of size 128 would give 3.8 MiB, 56 times too much.
KV cache with MHA, GQA and MLA
Session 26 explained these designs in depth; here is what they mean for the cache. Only the middle factor of (80.4) changes:
- Read the symbols
- \(n_h\)
- number of query heads. In MHA every query head has its own key and value head.
- \(n_{kv}\)
- in GQA, groups of \(n_h / n_{kv}\) query heads share one key head and one value head (MQA is \(n_{kv} = 1\))
- \(d_c\)
- in MLA, the size of the compressed latent vector stored per token per layer (512 in DeepSeek-V2 and V3)
- \(d_h^R\)
- in MLA, the size of the small shared key that carries the RoPE position (64)
- no factor 2 for MLA
- the one latent replaces both the keys and the values; both are rebuilt from it (or the rebuild is folded into the query and output matrices)
| Model | Attention | \(L\) | Stored per layer | \(s\) (bfloat16) | One 32k sequence |
|---|---|---|---|---|---|
| Llama 2 7B | MHA, 32 heads | 32 | \(2 \times 32 \times 128 = 8192\) | 512 KiB | 16 GiB |
| Llama 3 8B | GQA, 32 / 8 | 32 | \(2 \times 8 \times 128 = 2048\) | 128 KiB | 4 GiB |
| Qwen2.5 7B | GQA, 28 / 4 | 28 | \(2 \times 4 \times 128 = 1024\) | 56 KiB | 1.75 GiB |
| Mistral NeMo 12B | GQA, 32 / 8 | 40 | \(2 \times 8 \times 128 = 2048\) | 160 KiB | 5 GiB |
| Llama 3 70B | GQA, 64 / 8 | 80 | \(2 \times 8 \times 128 = 2048\) | 320 KiB | 10 GiB |
| DeepSeek-V3 (671B) | MLA, 128 heads | 61 | \(512 + 64 = 576\) | 68.6 KiB | 2.1 GiB |
[Certain for the shapes, from the config files; Llama 2 7B has a real context of 4,096 tokens, so its 32k column is a what-if.] Two lessons stand out. First, the move from MHA to GQA cut the cache of a 7–8B model by 4×, and Qwen2.5 7B goes to 9× by keeping only 4 key–value heads. Second, the biggest model in the table, DeepSeek-V3 with 671B parameters, has a smaller cache per token than Llama 3 8B. The cache depends on the attention design and the number of layers, not on the parameter count.
Other ways to make the cache smaller
Formula (80.4) has five factors, and each one is a family of methods covered later in Track 5:
| Factor | Method | Effect on the cache | Where |
|---|---|---|---|
| \(n_{kv} d_h\) | GQA, MQA, MLA | fewer stored numbers per layer; needs (re)training | session 97 |
| \(b\) | FP8 / INT8 / INT4 cache | 2–4× smaller; small accuracy cost. vLLM has an FP8 cache option (--kv-cache-dtype fp8). [Certain] | session 110 |
| \(T\) | sliding window, attention sinks, eviction (StreamingLLM, H2O) | keep only some tokens; may lose far-away information | session 117 |
| \(\sum T_i\) in practice | paging, prefix sharing | no reserved-but-empty memory; share common prompts | session 134 |
| \(L\) | share caches across layers | fewer caches, needs training [Likely] | session 97 |
The sliding window deserves a closer look, because it changes the shape of the growth. Mistral 7B attends only to the last \(W = 4096\) tokens in each layer. The paper uses a rolling buffer: the key and value of position \(i\) go to slot \(i \bmod W\), overwriting the token that just left the window.
The cache stops growing at \(W\) tokens: for Mistral 7B (\(s\) = 128 KiB) at most 512 MiB per sequence, however long the text. The paper reports that at 32k tokens this cuts cache memory by 8× without hurting quality. [Certain that the paper reports this] (\(32{,}768 / 4096 = 8\).) Newer models often mix a few full-attention layers with many sliding-window layers to keep long-range recall. [Likely]
Peak memory ≈ weights + KV cache
The memory budget
During serving, GPU memory holds four things: the weights, the KV cache, the activations of the current step, and overhead (CUDA context, kernels’ work buffers, the memory allocator’s slack). In decoding, the activations are small, because each step processes only one new token per sequence. So:
- Read the symbols
- \(M_W\)
- weight memory: number of parameters × bytes per weight (2 for bfloat16, 1 for 8-bit, about 0.5 for 4-bit plus small scale factors)
- \(M_{\text{KV}}\)
- the cache, formula (80.4)
- \(M_{\text{GPU}}\)
- total GPU memory (summed over GPUs if the model is split across them)
- \(u\)
- the fraction of memory we allow ourselves to use, for example 0.9; the rest covers activations and overhead. vLLM calls this
gpu_memory_utilization; its default has changed between versions, so check yours.
Solve (80.7) for the cache. The memory left after the weights, divided by \(s\), is the total number of tokens the server can hold, for all users together. Divide by the context length to get the largest batch:
This is the main limit for long context and big batches. Context length and batch size trade one for one: the product \(B \cdot T\) is fixed by the memory left after the weights.
Llama 3 8B on one H100 (80 GB), all bfloat16, \(u = 0.9\). \(N_{\text{params}} = 8.03\) billion, so \(M_W = 16.06\) GB. Room for the cache: \(0.9 \times 80 - 16.06 = 55.94\) GB. With \(s = 131{,}072\) bytes: \(T_{\text{total}} = 55.94 \times 10^9 / 131{,}072 \approx 426{,}800\) tokens. At \(T = 8192\) per user: \(B_{\max} = 52\). At \(T = 32{,}768\): 13. At the full 131,072: only 3.
Llama 3 70B on two H100s (160 GB), bfloat16. \(N_{\text{params}} = 70.55\) billion, \(M_W = 141.1\) GB. Room: \(0.9 \times 160 - 141.1 = 2.9\) GB, which is \(2.9 \times 10^9 / 327{,}680 \approx 8{,}800\) tokens in total. The model fits, but it can serve one user with an 8k context. The deployment “works” and is useless.
Same, with 8-bit weights. \(M_W = 70.6\) GB, room 73.4 GB: about 224,000 tokens. With an 8-bit cache too, \(s\) halves to 160 KiB and the room holds about 448,000 tokens, 51 times more than the first setup. This is why weight quantization and KV-cache quantization are so often used together.
Figure 3 lets you do this calculation for other models, GPUs and precisions.
How to read Figure 3
Start with Llama 3 8B on 80 GB at 8,192 tokens: 52 users fit (52 blocks in the green area). Move the context slider right: each step doubles \(T\) and halves the users, because \(B \cdot T\) is fixed. Switch to Llama 2 7B: its MHA cache is 4× bigger per token, so only 27 users fit at 4,096 tokens, although its weights are smaller. Now pick Llama 3 70B on 2 × 80 GB: the weights take almost everything. Switch to 8-bit weights and an 8-bit cache and watch the room grow. On 24 GB, Qwen2.5 7B in 16-bit still holds about 111,000 tokens thanks to its 4 key–value heads.
Why the cache also costs time
Memory is not the only cost. In every decode step, each sequence’s new query must read all of that sequence’s cached keys and values, in every layer. Decoding is memory-bound: the GPU spends its time moving bytes from its main memory (HBM), not doing arithmetic (session 82). So a good lower bound for the time of one decode step is “bytes read ÷ memory bandwidth”:
- Read the symbols
- \(M_W\)
- the weights are read once per step and shared by the whole batch
- \(s \sum T_i\)
- the cache is read once per step too, but it is not shared: each sequence has its own
- BW
- memory bandwidth, about 3.35 TB/s on an H100 SXM [Certain, NVIDIA spec]
This shows the difference between the two parts. Batching makes the weights cheap: one read of the weights serves \(B\) users. It does nothing for the cache: \(B\) users mean \(B\) caches to read. The cache costs as much time as the weights when
For Llama 3 8B in bfloat16, \(T^{*} = 16.06 \times 10^9 / 131{,}072 \approx 122{,}500\) tokens for a single user, but only about 3,800 tokens with a batch of 32. In real servers with big batches, reading the cache often costs more time than reading the weights. This is why GQA, MLA and cache quantization make decoding faster, not only smaller.
One user, 4,096 tokens: \((16.06 + 4096 \times 131{,}072 / 10^9) / 3.35 = (16.06 + 0.54)/3.35\) GB per TB/s \(= 4.95\) ms. The cache is 3% of the bytes.
One user, 131,072 tokens: \((16.06 + 17.18) / 3.35 = 9.92\) ms, twice as slow, and the cache is 52% of the bytes.
32 users, 8,192 tokens each: \((16.06 + 34.36)/3.35 = 15.05\) ms per step, so each user gets at most 66 tokens per second, and the server makes at most 2,126 tokens per second. The cache is 68% of the bytes read. These are lower bounds: real kernels reach maybe 60–80% of peak bandwidth. [Likely]
How to read Figure 4
With batch 1, the grey weight band dominates until very long contexts: the cache only matters beyond \(T^{*}\) ≈ 122k tokens for Llama 3 8B. Move the batch slider to 32: the orange band rises 32 times higher and \(T^{*}\) moves left to about 3.8k tokens. Now the cache, not the model, sets the speed. Switch to Llama 2 7B (MHA): the same batch and context cost about 3× more time. Switch to Qwen2.5 7B (4 KV heads): the cache band becomes thin. The readout gives the step time, the tokens per second per user and for the server, and whether the cache fits on an 80 GB GPU.
Where the memory goes: reserved vs used
Formula (80.4) counts only tokens that exist. Early serving systems used more memory than that. A request may stop after 20 tokens or after 2,000, and the server does not know in advance. If it stores each sequence’s cache in one contiguous block, it must reserve a block for the maximum length when the request arrives. Most of that block is never used.
The vLLM paper measured this: in the systems it studied, only 20.4% to 38.2% of the KV cache memory held actual token states. [Certain, numbers from the vLLM paper] The rest was reserved for tokens that were not yet (or never) generated, internal fragmentation (space inside a reservation that stays empty), and external fragmentation (gaps between reservations that are too small to use).
vLLM’s fix, PagedAttention, borrows the idea of virtual memory from operating systems. The cache is cut into fixed-size blocks of \(\beta\) tokens (16 by default in the paper [Certain]). A sequence gets a new block only when its last block is full, and a block table maps the sequence’s logical blocks to physical blocks anywhere in memory. The only waste is the unfilled part of each sequence’s last block:
- Read the symbols
- \(\eta\)
- memory utilization: the fraction of reserved cache memory that holds real tokens
- \(T_{\max}\)
- the maximum length reserved per request in the contiguous scheme
- \(\beta\)
- the block size in tokens
- \(\lceil T_i / \beta \rceil\)
- blocks used by sequence \(i\): its length divided by the block size, rounded up. The waste is less than one block per sequence.
The paper reports that vLLM raises throughput by 2–4× over the systems it compared, at the same latency, mostly because more sequences fit in the same memory. [Certain that the paper reports this] Figure 5 lets you compare the two schemes on twelve requests. The full story (block tables, copy-on-write for parallel sampling, prefix sharing) is in session 134.
- arrival: contiguous reserves \(T_{\max}\) slots; paged: none
- each decode step, for every running request \(i\):
- \(T_i \leftarrow T_i + 1\)
- if \(T_i \bmod \beta = 1\): take a free block, add it to the block table
- write \(\mathbf{k}, \mathbf{v}\) into slot \((T_i - 1) \bmod \beta\) of the last block
- if request \(i\) emits its end token: it stops growing
How to read Figure 5
Press Play. On the left, the whole reservation exists from the first step, so utilization starts near 0% and only reaches about 20% when every request is done (with \(T_{\max} = 2048\), at the low end of the 20–38% the vLLM paper measured). On the right, a new block appears only when a request’s last block is full. With blocks of 16, utilization is 62.5% in the first frame (20 tokens in 2 blocks of 16) and above 89% from the fifth frame on. At the end, raise \(T_{\max}\) to 8,192 (a typical “max tokens” for a long-context model): contiguous utilization falls to about 5%, so you would fit about 20× fewer users than the memory allows. The paged scheme does not care about \(T_{\max}\). With blocks of 16 its final utilization is above 98%; with very large blocks (256) the last-block waste grows again. Small blocks waste less memory but need a bigger block table and more scattered reads, which is the trade-off behind the default of 16.
Multimodal and long inputs
For a VLM the cache does not care where a token came from. In LLaVA-style models (session 186), each image becomes a sequence of visual tokens that go through the language model like text, so each one gets a cache row in every layer. LLaVA-1.5 turns a \(336 \times 336\) image into \((336/14)^2 = 576\) tokens. [Certain] Its language model is Vicuna-7B, which has the Llama 2 7B shape with MHA, so one image adds \(576 \times 512\) KiB = 288 MiB of cache. [Certain for the arithmetic] The book’s Chapters 3 and 7 discuss the KV cache in this setting.
Video makes this much larger. A naive video model that keeps 576 tokens for each of 64 frames holds 36,864 visual tokens: 18 GiB of cache with that MHA model, or 4.5 GiB with a Llama 3 8B-sized GQA model, for a single question. This is a main reason why video LLMs pool or merge visual tokens per frame (session 206), and why streaming video assistants need sliding windows or eviction. [Certain for the arithmetic; the design reasons are Likely]
Models that add vision through cross-attention (Flamingo-style, session 20) have a different pattern: the image keys and values are computed once from the image encoder and stay fixed during decoding, so that part of the cache does not grow with generated text. The same holds for encoder–decoder models such as Whisper, which cache the encoder’s keys and values once per input. [Certain]
A complete example in PyTorch
- input: config file, GPU memory \(M_{\text{GPU}}\) and bandwidth BW, precisions \(b_W, b\), target context \(T\), utilization \(u\)
- \(s \leftarrow 2 L\, n_{kv}\, d_h\, b\) (or \(L(d_c + d_h^R) b\) for MLA) // use head_dim from the file, formula (80.4)
- \(M_W \leftarrow N_{\text{params}} \cdot b_W\)
- if \(M_W \ge u\, M_{\text{GPU}}\): stop, the model does not fit; use more GPUs or smaller weights
- \(T_{\text{total}} \leftarrow (u\, M_{\text{GPU}} - M_W) / s\); \(\;B_{\max} \leftarrow \lfloor T_{\text{total}} / T \rfloor\) // formula (80.8)
- if \(B_{\max} = 0\): reduce \(T\), quantize the cache, or add GPUs
- \(t_{\text{step}} \leftarrow (M_W + s\, B_{\max} T) / \text{BW}\) // lower bound (80.9)
- report \(B_{\max}\), tokens/s per user \(\le 1/t_{\text{step}}\), and server tokens/s \(\le B_{\max}/t_{\text{step}}\)
The code below builds a tiny two-layer attention model with GQA (8 query heads, 2 key–value heads). It generates 12 tokens twice: once by re-running the whole sequence each step, and once with a KV cache. It checks that both give the same tokens, counts the rows of work as in (80.2), and checks the cache size against (80.4). It uses float64 so that the two paths agree exactly, and a fixed seed, so it is deterministic.
import torch, torch.nn.functional as F torch.manual_seed(0) torch.set_default_dtype(torch.float64) # exact comparison, no float noise V, d, L, n_h, n_kv, d_h = 50, 64, 2, 8, 2, 8 # tiny GQA model: 4 query heads per KV head r = n_h // n_kv emb = torch.randn(V, d) * 0.5 layers = [dict(Wq=torch.randn(d, n_h * d_h) / d**0.5, Wk=torch.randn(d, n_kv * d_h) / d**0.5, Wv=torch.randn(d, n_kv * d_h) / d**0.5, Wo=torch.randn(n_h * d_h, d) / d**0.5) for _ in range(L)] def attn_layer(W, x, cache, pos0): """x: (T_new, d) new tokens only. cache: dict with 'k','v' of shape (n_kv, T_old, d_h) or None.""" T = x.shape[0] q = (x @ W["Wq"]).view(T, n_h, d_h).transpose(0, 1) # (n_h, T, d_h) k = (x @ W["Wk"]).view(T, n_kv, d_h).transpose(0, 1) # (n_kv, T, d_h) v = (x @ W["Wv"]).view(T, n_kv, d_h).transpose(0, 1) if cache is not None: if "k" in cache: # append the new rows k = torch.cat([cache["k"], k], dim=1); v = torch.cat([cache["v"], v], dim=1) cache["k"], cache["v"] = k, v # store K and V, never Q S = k.shape[1] # all keys: old + new k = k.repeat_interleave(r, dim=0); v = v.repeat_interleave(r, dim=0) # GQA: share KV heads s = q @ k.transpose(1, 2) / d_h**0.5 # (n_h, T, S) qpos = pos0 + torch.arange(T)[:, None]; kpos = torch.arange(S)[None, :] s = s.masked_fill(kpos > qpos, float("-inf")) # causal mask with absolute positions o = (F.softmax(s, -1) @ v).transpose(0, 1).reshape(T, n_h * d_h) return x + o @ W["Wo"] def forward(ids, caches=None, pos0=0): x = emb[ids] for i, W in enumerate(layers): x = attn_layer(W, x, None if caches is None else caches[i], pos0) return x @ emb.T # logits, tied output layer prompt, N = [3, 14, 15, 9, 26], 12 # 1) no cache: rerun the whole sequence at every step ids, rows_nc = list(prompt), 0 for _ in range(N): logits = forward(torch.tensor(ids)); rows_nc += len(ids) ids.append(int(logits[-1].argmax())) out_nc = ids[len(prompt):] # 2) with cache: prefill once, then one new token per step caches = [dict() for _ in range(L)] logits = forward(torch.tensor(prompt), caches, 0); rows_c = len(prompt) ids = list(prompt) + [int(logits[-1].argmax())] for _ in range(N - 1): logits = forward(torch.tensor(ids[-1:]), caches, len(ids) - 1); rows_c += 1 ids.append(int(logits[-1].argmax())) out_c = ids[len(prompt):] print("same tokens:", out_nc == out_c) print("token rows through the model:", rows_nc, "vs", rows_c) T = caches[0]["k"].shape[1] numel = sum(c["k"].numel() + c["v"].numel() for c in caches) print("cached tokens:", T, "| numbers in cache:", numel, "| formula 2*L*n_kv*d_h*T =", 2 * L * n_kv * d_h * T)
Output: same tokens: True, token rows through the model: 126 vs 16, and cached tokens: 16 | numbers in cache: 1024 | formula 2*L*n_kv*d_h*T = 1024. Check the numbers with (80.2): \(P = 5\), \(N = 12\) gives \(12 \times 5 + 66 = 126\) and \(5 + 11 = 16\). The cache holds 16 tokens, not 17, because the last token was never fed in. Note the pos0 argument: in a decode step the new token’s query must be compared with keys at positions \(0, \dots, t\), and with RoPE it must be rotated by its true position, not by 0. Forgetting this offset is a classic bug. In real bfloat16 models the two paths can differ in the last bits, because a batched prefill and a one-row decode sum numbers in a different order; with greedy decoding this can very rarely flip a token. [Likely]
Where this is used
| Setting | What happens to the cache | Main concern |
|---|---|---|
| Chat assistants | Cache grows over the conversation; the prefix cache of earlier turns can be kept between messages | Many users × long histories; prefix caching saves prefill |
| Long-document QA, RAG | Long prompt in prefill (tens of thousands of tokens), short answer | Cache size at long \(T\) limits batch (80.8) |
| Agents and tool use | Very long, growing contexts with shared system prompts | Prefix sharing across calls; cache eviction policy |
| Parallel sampling, beam search | Several continuations share the prompt’s cache; vLLM shares blocks with copy-on-write [Certain] | Do not copy the prompt cache \(n\) times |
| Speculative decoding | Draft and target models each keep a cache; rejected tokens must be removed from it | Rolling back cache rows (session 128) |
| VLM image QA | Hundreds of visual tokens per image enter the cache (576 for LLaVA-1.5) | Images can cost more cache than the text |
| Video QA, Video-RAG, key-moment detection | Thousands to tens of thousands of frame tokens per video | Token pooling per frame, retrieval of a few clips instead of all frames |
| Streaming video and live captioning | Unbounded input stream | Sliding window or attention sinks (80.6) to keep the cache bounded |
Common mistakes
- Forgetting the factor 2. The cache holds keys and values. (MLA is the exception: one latent stands for both.)
- Using \(n_h\) instead of \(n_{kv}\). For Llama 3 70B this overestimates the cache by 8×.
- Computing \(d_h\) as hidden size ÷ heads. Wrong for Mistral NeMo (128, not 160) and other models; read
head_dimwhen it exists. - Trusting
num_key_value_headsfor MLA models. DeepSeek-V3 says 128, but caches a 576-number latent per layer. - Planning only for the weights. “It fits on two GPUs” says nothing about how many users it can serve; do formula (80.8).
- Mixing GB and GiB, or bfloat16 and FP8 bytes, in one calculation.
- Wrong position for the new token. The decode token’s position (for RoPE and for the mask) is the current cache length, not 0.
- Reserving the maximum length per request in a contiguous buffer; most of it stays empty (Figure 5).
Interview questions
Why do we cache keys and values but not queries?basic
Does the KV cache change the model’s output?basic
Why can’t BERT use a KV cache to generate text?core
How much compute does the KV cache save?core
Compute the KV cache of Llama 3 70B for batch 8 at 32k tokens.core
A 70B model in bfloat16 fits on two 80 GB GPUs. Is that a good deployment?core
Why does time per output token grow with context length, and why more with a big batch?core
Why are GQA and MLA said to make decoding faster, not only smaller?core
Why would you not cache the layer input \(\mathbf{h}\) instead of K and V?advanced
What does a sliding window do to the cache, and how is it stored?core
Why did early serving systems waste most of their KV cache memory, and what does PagedAttention change?advanced
How does a VLM’s image affect the cache? What about video?advanced
Exercises
- Qwen2.5 7B has 28 layers, 4 key–value heads and \(d_h = 128\). Compute \(s\) in bfloat16 and the cache for 16 users at 32,768 tokens.
- Mistral NeMo 12B: compute \(s\) with the correct
head_dim, and the cache for one 128k-token sequence. How large is the error if you use hidden size ÷ heads? - With formula (80.2), how many rows of work does generating 200 tokens after a 50-token prompt need, with and without a cache?
- Llama 2 7B (13.5 GB of weights, \(s\) = 512 KiB) on an 80 GB GPU with \(u = 0.9\): how many users of 4,096 tokens fit? Compare with Llama 3 8B at the same context (Figure 3).
- For Llama 3 8B in bfloat16, at what context length does the cache cost as much time as the weights with batch 16? (Formula 80.10.)
- Ten requests have lengths 100, 150, …, 550 tokens (steps of 50). Compute the utilization of contiguous reservation with \(T_{\max} = 2048\), and of paging with \(\beta = 16\).
Answerscheck
Key takeaways
- A new token needs its own query once, but every earlier key and value again at every step. The causal mask keeps old keys and values fixed, so caching them is exact (80.1).
- The cache turns quadratic recomputation into linear work: \(P + N - 1\) rows instead of \(NP + N(N-1)/2\) (80.2).
- Size: \(s = 2 L\, n_{kv}\, d_h\, b\) bytes per token, times all tokens of all users (80.4). Read
head_dimand the MLA fields from the config file; do not trust hidden ÷ heads ornum_key_value_headsblindly. - MHA → GQA → MLA shrinks the middle factor (80.5): 512 KiB (Llama 2 7B) → 128 KiB (Llama 3 8B) → 68.6 KiB (DeepSeek-V3, 671B parameters).
- Peak memory ≈ weights + KV cache (80.7). The room left after the weights, divided by \(s\), is the total token budget; batch × context is fixed by it (80.8).
- Each decode step reads the weights once but every user’s cache separately (80.9); with big batches the cache, not the model, sets the speed (80.10).
- Reserving the maximum length wastes most of the cache; paging in small blocks keeps utilization near 100% (80.11).
Key formulas
References for this session
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 3: Vision Language Model Training
- Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 7: Deploying Models for Inference at Scale
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 3: Vision Language Model Training
- Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 7: Deploying Models for Inference at Scale
- Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
- DeepSeek-AI (2024). DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model
- DeepSeek-AI (2024). DeepSeek-V3 Technical Report
- Jiang et al. (2023). Mistral 7B
- Llama Team, Meta (2024). The Llama 3 Herd of Models
- Liu et al. (2023). Improved Baselines with Visual Instruction Tuning
- Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
- Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures