LLM & VLM courseBlog
80Track 5: LLM inference and serving · session 3 of 65

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.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 26 and 78 (attention variants and the KV cache, the generation loop)

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\):

\[ \mathbf{o}_t = \sum_{j=1}^{t} \softmax_j\!\left( \frac{\mathbf{q}_t \cdot \mathbf{k}_j}{\sqrt{d_h}} \right) \mathbf{v}_j, \qquad K_{1:t} = \begin{bmatrix} K_{1:t-1} \\ \mathbf{k}_t^{\top} \end{bmatrix}, \quad V_{1:t} = \begin{bmatrix} V_{1:t-1} \\ \mathbf{v}_t^{\top} \end{bmatrix} \tag{80.1} \]
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.
\[ \text{rows}_{\text{no cache}} = \sum_{t=P}^{P+N-1} t = N P + \frac{N(N-1)}{2}, \qquad \text{rows}_{\text{cache}} = P + N - 1 \tag{80.2} \]
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.

query (used once)key (cached)value (cached)softmax weight
One step for the token at position \(t\)
  1. \(\mathbf{x}_t \leftarrow\) embed(token \(t\)) // prefill: all \(P\) rows
  2. \(\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\)
  3. append \(\mathbf{k}_t, \mathbf{v}_t\) to the cache \(K, V\)
  4. \(s_j \leftarrow \mathbf{q}_t \cdot \mathbf{k}_j / \sqrt{d_h}\) for \(j = 1, \dots, t\)
  5. \(\alpha \leftarrow \softmax(s)\)
  6. \(\mathbf{o}_t \leftarrow \sum_j \alpha_j \mathbf{v}_j\)
  7. emit the next token; \(t \leftarrow t + 1\)
Figure 1. One attention head (\(d_h = 4\), fixed toy weights, no position encoding) while the model continues the prompt “The cat sat on”. Each row is a token; the cells hold the real numbers of \(\mathbf{q}\), \(\mathbf{k}\) and \(\mathbf{v}\). A thick outline marks what is computed in the current step; the lines show the newest query reading every cached key. The algorithm line that runs now is highlighted, and the panel next to it shows formula (80.1) with the live numbers. The bars at the bottom count the rows pushed through the model with a cache and without one, formula (80.2). The next tokens come from the fixed text, so the example stays readable; the attention arithmetic is real.
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

\[ \mathcal{C} = \big\{ (K^{(\ell)}, V^{(\ell)}) \big\}_{\ell=1}^{L}, \qquad K^{(\ell)}, V^{(\ell)} \in \R^{B \times n_{kv} \times T \times d_h} \tag{80.3} \]
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).

Algorithm 1: generation with a KV cache
  1. input: prompt tokens \(x_1, \dots, x_P\); model with \(L\) layers; maximum new tokens \(N\)
  2. 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
  3. \(y_1 \leftarrow\) choose from the logits of position \(P\) // greedy, sampling, ... (session 79)
  4. for \(n = 1, \dots, N-1\):
  5.   \(t \leftarrow P + n\) // position of the token fed in now = current cache length + 1
  6.   embed \(y_n\); in each layer: compute \(\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t\) (RoPE at position \(t\))
  7.     append \(\mathbf{k}_t, \mathbf{v}_t\) to the layer’s cache
  8.     attend \(\mathbf{q}_t\) to all \(t\) cached keys and values, formula (80.1); no mask needed: the cache holds only the past
  9.   \(y_{n+1} \leftarrow\) choose from the logits; stop at the end-of-sequence token
  10. 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:

\[ s = 2 \cdot L \cdot n_{kv} \cdot d_h \cdot b \ \ \text{bytes per token}, \qquad M_{\text{KV}} = s \cdot \sum_{i=1}^{B} T_i \tag{80.4} \]
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\)”.

Worked example: three real models

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.

Serving loop with memory accounting
  1. \(s \leftarrow 2 \cdot L \cdot n_{kv} \cdot d_h \cdot b\) // (80.4)
  2. \(M_W \leftarrow N_{\text{params}} \cdot 2\); prefill: \(T \leftarrow P\)
  3. repeat (one decode step for all \(B\) requests):
  4.   \(T \leftarrow T + 1\)
  5.   \(M_{\text{KV}} \leftarrow s \cdot B \cdot T\)
  6.   if \(M_W + M_{\text{KV}} \gt u\, M_{\text{GPU}}\): stop, out of memory
  7.   rows: cache \(+B\); no cache \(+B \cdot T\) // (80.2)
  8.   \(t_{\text{step}} \ge (M_W + M_{\text{KV}}) / \text{BW}\) // (80.9)
Figure 2. The KV cache growing during decoding, formula (80.4) with live numbers. Prompt \(P = 512\) tokens, bfloat16 weights and cache, one 80 GB GPU with \(u = 0.9\), bandwidth 3.35 TB/s. Each frame jumps forward by the same number of decode steps. Top: GPU memory (grey weights, one colored strip per request, the 10% reserve hatched). Left: weights + cache against the context length \(T\); the red line is \(u\, M_{\text{GPU}} = 72\) GB. Right: total compute of the run so far, with a cache (green) and without one (orange, recomputing every row). Llama 2 7B’s real context is 4,096 tokens; longer runs are a what-if.
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_size 5120, 32 query heads and 8 key–value heads, but head_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 has head_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 of kv_lora_rank = 512 numbers plus one RoPE key of qk_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:

\[ s_{\text{MHA}} = 2 L\, n_h\, d_h\, b, \qquad s_{\text{GQA}} = 2 L\, n_{kv}\, d_h\, b, \qquad s_{\text{MLA}} = L\,(d_c + d_h^R)\, b \tag{80.5} \]
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)
ModelAttention\(L\)Stored per layer\(s\) (bfloat16)One 32k sequence
Llama 2 7BMHA, 32 heads32\(2 \times 32 \times 128 = 8192\)512 KiB16 GiB
Llama 3 8BGQA, 32 / 832\(2 \times 8 \times 128 = 2048\)128 KiB4 GiB
Qwen2.5 7BGQA, 28 / 428\(2 \times 4 \times 128 = 1024\)56 KiB1.75 GiB
Mistral NeMo 12BGQA, 32 / 840\(2 \times 8 \times 128 = 2048\)160 KiB5 GiB
Llama 3 70BGQA, 64 / 880\(2 \times 8 \times 128 = 2048\)320 KiB10 GiB
DeepSeek-V3 (671B)MLA, 128 heads61\(512 + 64 = 576\)68.6 KiB2.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:

FactorMethodEffect on the cacheWhere
\(n_{kv} d_h\)GQA, MQA, MLAfewer stored numbers per layer; needs (re)trainingsession 97
\(b\)FP8 / INT8 / INT4 cache2–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 informationsession 117
\(\sum T_i\) in practicepaging, prefix sharingno reserved-but-empty memory; share common promptssession 134
\(L\)share caches across layersfewer 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.

\[ \text{slot}(i) = i \bmod W, \qquad M_{\text{KV}} = s \cdot \min(T, W) \ \text{ per sequence} \tag{80.6} \]

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:

\[ M_{\text{peak}} \approx M_W + M_{\text{KV}} \le u \cdot M_{\text{GPU}}, \qquad M_W = N_{\text{params}} \cdot b_W \tag{80.7} \]
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:

\[ T_{\text{total}} = \frac{u\, M_{\text{GPU}} - M_W}{s}, \qquad B_{\max} = \left\lfloor \frac{T_{\text{total}}}{T} \right\rfloor \tag{80.8} \]

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.

Worked example: how many users fit?

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.

Figure 3. A memory planner built on formulas (80.4), (80.7) and (80.8), with \(u = 0.9\). The bar is the total GPU memory: weights, the room left for the KV cache (cut into one block per user of \(T\) tokens), and the 10% reserve for activations and overhead. Parameter counts are computed from each model’s config file; 4-bit weights ignore the small scale factors.
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”:

\[ t_{\text{step}} \ge \frac{M_W + s \sum_{i=1}^{B} T_i}{\text{BW}} \tag{80.9} \]
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

\[ B \cdot T^{*} \cdot s = M_W \quad \Longrightarrow \quad T^{*} = \frac{M_W}{B\, s} \tag{80.10} \]

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.

Worked example: decode step time of Llama 3 8B on an H100

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]

Figure 4. The time of one decode step, lower bound (80.9), on an H100 (3.35 TB/s), bfloat16. The horizontal axis is the context length per sequence (log scale, 1k to 128k). The grey band is the time to read the weights; the orange band on top is the time to read the KV caches of the whole batch. The dashed line marks \(T^{*}\), formula (80.10), where both are equal. Combinations that do not fit in 80 GB are marked.
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:

\[ \eta_{\text{contig}} = \frac{\sum_i T_i}{B \cdot T_{\max}}, \qquad \eta_{\text{paged}} = \frac{\sum_i T_i}{\beta \sum_i \lceil T_i / \beta \rceil} \tag{80.11} \]
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.

Paged allocation during decoding
  1. arrival: contiguous reserves \(T_{\max}\) slots; paged: none
  2. each decode step, for every running request \(i\):
  3.   \(T_i \leftarrow T_i + 1\)
  4.   if \(T_i \bmod \beta = 1\): take a free block, add it to the block table
  5.   write \(\mathbf{k}, \mathbf{v}\) into slot \((T_i - 1) \bmod \beta\) of the last block
  6.   if request \(i\) emits its end token: it stops growing
Figure 5. Twelve requests with fixed final lengths between 37 and 1,000 tokens (5,009 in total), decoded together; each frame is 20 decode steps. Left: each request reserves \(T_{\max}\) tokens of contiguous cache at arrival (light) and fills it slowly (solid). Right: paged allocation in blocks of \(\beta\) tokens, allocated only when the last block is full; blocks taken in the current frame have a thick outline. The panel computes both utilizations with formula (80.11) at every frame.
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

Algorithm 2: capacity planning for a deployment
  1. input: config file, GPU memory \(M_{\text{GPU}}\) and bandwidth BW, precisions \(b_W, b\), target context \(T\), utilization \(u\)
  2. \(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)
  3. \(M_W \leftarrow N_{\text{params}} \cdot b_W\)
  4. if \(M_W \ge u\, M_{\text{GPU}}\): stop, the model does not fit; use more GPUs or smaller weights
  5. \(T_{\text{total}} \leftarrow (u\, M_{\text{GPU}} - M_W) / s\); \(\;B_{\max} \leftarrow \lfloor T_{\text{total}} / T \rfloor\) // formula (80.8)
  6. if \(B_{\max} = 0\): reduce \(T\), quantize the cache, or add GPUs
  7. \(t_{\text{step}} \leftarrow (M_W + s\, B_{\max} T) / \text{BW}\) // lower bound (80.9)
  8. 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

SettingWhat happens to the cacheMain concern
Chat assistantsCache grows over the conversation; the prefix cache of earlier turns can be kept between messagesMany users × long histories; prefix caching saves prefill
Long-document QA, RAGLong prompt in prefill (tens of thousands of tokens), short answerCache size at long \(T\) limits batch (80.8)
Agents and tool useVery long, growing contexts with shared system promptsPrefix sharing across calls; cache eviction policy
Parallel sampling, beam searchSeveral continuations share the prompt’s cache; vLLM shares blocks with copy-on-write [Certain]Do not copy the prompt cache \(n\) times
Speculative decodingDraft and target models each keep a cache; rejected tokens must be removed from itRolling back cache rows (session 128)
VLM image QAHundreds 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 detectionThousands to tens of thousands of frame tokens per videoToken pooling per frame, retrieval of a few clips instead of all frames
Streaming video and live captioningUnbounded input streamSliding 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_dim when it exists.
  • Trusting num_key_value_heads for 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
In formula (80.1), the new token’s output needs its own query and the keys and values of all tokens up to itself. Its query is used only in this step: later tokens use their own queries. Its key and value are needed by every later token. Because of the causal mask, old keys and values never change when new tokens arrive, so they can be computed once and reused. Caching queries would cost memory and never be read.
Does the KV cache change the model’s output?basic
Mathematically, no. With a causal mask, the hidden state of token \(j\) in every layer depends only on tokens \(1..j\), so the cached keys and values are exactly what a full recomputation would produce. In floating point, a batched prefill and a one-token decode can sum in different orders and differ in the last bits, which can very rarely flip a greedy token. The test in the PyTorch section shows identical tokens in float64.
Why can’t BERT use a KV cache to generate text?core
BERT is bidirectional: every position attends to every other. Appending a token changes the hidden states, and so the keys and values, of all earlier positions in all layers above the first. The cached values would be stale. A causal (or prefix-causal) model guarantees that earlier positions never see later ones, which is what makes the cache valid.
How much compute does the KV cache save?core
Without a cache, generating \(N\) tokens after a \(P\)-token prompt pushes \(NP + N(N-1)/2\) token positions through the model; with a cache, \(P + N - 1\) (80.2). For \(P = N = 1000\) that is about 1.5 million against 2 thousand, a factor of 750. What remains is attention over the cache, which grows linearly with the context per step, but avoids redoing the projections and MLPs of old tokens.
Compute the KV cache of Llama 3 70B for batch 8 at 32k tokens.core
\(L = 80\), \(n_{kv} = 8\), \(d_h = 128\), bfloat16. Per token: \(2 \times 80 \times 8 \times 128 \times 2 = 327{,}680\) bytes = 320 KiB. Total: \(327{,}680 \times 32{,}768 \times 8 = 85.9\) GB = 80 GiB. With MHA (64 KV heads) it would be 8× more, 640 GiB.
A 70B model in bfloat16 fits on two 80 GB GPUs. Is that a good deployment?core
No. Weights take 141 GB of 160. With 10% reserved, about 2.9 GB is left for the cache: around 8,800 tokens in total with 320 KiB per token, so about one user at 8k context. Peak memory ≈ weights + KV cache (80.7) means the batch is near 1 and the GPUs are idle most of the time. Options: 8-bit weights (room grows to ~73 GB, ~224k tokens), an 8-bit cache (doubles that), or more GPUs.
Why does time per output token grow with context length, and why more with a big batch?core
Decoding is memory-bound: each step reads the weights once and every sequence’s cache once (80.9). Weights are shared across the batch, the caches are not. So the cache term grows with \(B \cdot T\). The cache read time equals the weight read time at \(T^{*} = M_W / (B s)\): about 122k tokens for Llama 3 8B at batch 1, but only about 3.8k at batch 32. Beyond that, the cache dominates the step time.
Why are GQA and MLA said to make decoding faster, not only smaller?core
Because decode time is bytes read ÷ bandwidth, and the cache is a growing part of the bytes. GQA with 8 KV heads reads 4× fewer cache bytes than MHA with 32; MLA in DeepSeek-V3 reads 576 numbers per layer per token. The FLOPs barely change, but the bytes do, and bytes set the time. Fewer cache bytes per user also allow a bigger batch, which spreads the weight reads over more users.
Why would you not cache the layer input \(\mathbf{h}\) instead of K and V?advanced
It can be smaller (\(d\) numbers vs \(2 n_{kv} d_h\); half for an MHA model with \(d_h n_h = d\)), but each decode step would have to multiply all \(t\) stored vectors by \(W^K\) and \(W^V\) again, which reintroduces the work the cache exists to avoid. With GQA, \(2 n_{kv} d_h\) is already smaller than \(d\) (2,048 vs 4,096 in Llama 3 8B). MLA is the trained version of the idea: it stores a small latent and absorbs the up-projection into the query and output matrices, so nothing is recomputed per old token.
What does a sliding window do to the cache, and how is it stored?core
With window \(W\), each token attends only to the last \(W\) tokens of that layer, so older keys and values can be dropped. Mistral 7B stores them in a rolling buffer: position \(i\) goes to slot \(i \bmod W\) (80.6). The cache stops growing at \(W\) tokens per sequence (512 MiB for Mistral 7B with \(W = 4096\)); at 32k tokens this is an 8× saving. Information from beyond the window can still flow through the stack of layers, but only indirectly.
Why did early serving systems waste most of their KV cache memory, and what does PagedAttention change?advanced
They stored each request’s cache contiguously and reserved space for the maximum possible length, because output length is unknown in advance. Most of that space was never filled, and fixed-size reservations caused fragmentation: the vLLM paper measured only 20.4–38.2% of cache memory holding real tokens. PagedAttention splits the cache into small blocks (16 tokens by default) allocated on demand, with a block table per sequence, so waste is under one block per sequence. It also lets sequences share blocks (parallel sampling, common prefixes) with copy-on-write. The paper reports 2–4× higher throughput.
How does a VLM’s image affect the cache? What about video?advanced
In decoder-only VLMs (LLaVA style), visual tokens are ordinary tokens for the language model, so each gets a cache row in every layer. LLaVA-1.5 uses 576 tokens per image; with its Llama 2 7B-shaped MHA language model that is 288 MiB per image. Video multiplies this by the number of frames: 64 frames × 576 tokens is 18 GiB for that model. Hence frame token pooling, frame selection, retrieval of a few clips, and sliding windows for streaming. Cross-attention VLMs compute the image keys and values once; that part of the cache is fixed and does not grow with generated text.

Exercises

  1. 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.
  2. 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?
  3. With formula (80.2), how many rows of work does generating 200 tokens after a 50-token prompt need, with and without a cache?
  4. 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).
  5. 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.)
  6. 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
1. \(s = 2 \times 28 \times 4 \times 128 \times 2 = 57{,}344\) bytes = 56 KiB. Cache: \(57{,}344 \times 32{,}768 \times 16\) bytes = 28 GiB. 2. \(s = 2 \times 40 \times 8 \times 128 \times 2 = 163{,}840\) bytes = 160 KiB; at 131,072 tokens: 20 GiB. With \(d_h = 160\): 200 KiB and 25 GiB, 25% too high. 3. No cache: \(200 \times 50 + 200 \times 199/2 = 10{,}000 + 19{,}900 = 29{,}900\). With cache: \(50 + 199 = 249\), about 120× fewer. 4. Room: \(72 - 13.48 = 58.5\) GB; per user \(524{,}288 \times 4096 = 2.15\) GB; \(B_{\max} = 27\). Llama 3 8B: room 55.9 GB, per user 0.54 GB, \(B_{\max} = 104\), almost 4× more thanks to GQA. 5. \(T^{*} = 16.06 \times 10^9 / (16 \times 131{,}072) \approx 7{,}660\) tokens. 6. Total tokens \(= 3{,}250\). Contiguous: \(3250 / 20{,}480 = 15.9\%\). Paged: blocks \(\lceil T_i / 16 \rceil\) = 7, 10, 13, 16, 19, 22, 25, 29, 32, 35, total 208 blocks = 3,328 token slots, so \(3250 / 3328 = 97.7\%\).

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_dim and the MLA fields from the config file; do not trust hidden ÷ heads or num_key_value_heads blindly.
  • 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

\[ s = 2 L\, n_{kv}\, d_h\, b, \qquad M_{\text{KV}} = s \sum_i T_i, \qquad s_{\text{MLA}} = L\,(d_c + d_h^R)\, b \]
\[ M_W + M_{\text{KV}} \le u\, M_{\text{GPU}}, \qquad B_{\max} = \left\lfloor \frac{u M_{\text{GPU}} - M_W}{s\, T} \right\rfloor, \qquad t_{\text{step}} \ge \frac{M_W + s \sum_i T_i}{\text{BW}} \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  3. Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 3: Vision Language Model Training
  4. Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 7: Deploying Models for Inference at Scale
  5. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  6. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  7. Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 3: Vision Language Model Training
  8. Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 7: Deploying Models for Inference at Scale
  9. Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
  10. DeepSeek-AI (2024). DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model
  11. DeepSeek-AI (2024). DeepSeek-V3 Technical Report
  12. Jiang et al. (2023). Mistral 7B
  13. Llama Team, Meta (2024). The Llama 3 Herd of Models
  14. Liu et al. (2023). Improved Baselines with Visual Instruction Tuning
  15. Xiao et al. (2023). Efficient Streaming Language Models with Attention Sinks
  16. Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures