TracksStudyAbout
Sign in
Start studying
Module 6 · LLMs Module contents
Module 6  ·  Card 17 / 22intermediate

The KV Cache

Generation is one token at a time, and each new token attends to every token before it.

Recomputing the keys and values for the whole prefix on every step would be enormously wasteful.

So they are computed once and kept, and each step appends only the new token's key and value.

That turns quadratic recomputation into a single extra column per step, which is what makes chat usable.

The cache grows with context and batch size, and on long conversations it, not the weights, fills the GPU.

Back Next
Learn in depth ↓
Module 06 · LLMs · 22 concepts
In depth  /  15 lines

The KV Cache, in more detail

Generating text is autoregressive: the model produces one token, appends it, and runs again.

At each step, self-attention needs a key and a value for every token in the sequence so far.

Computing those from scratch every step would repeat almost the entire prefix's work each time.

For a thousand-token response that is roughly a thousand redundant passes over the same text.

The KV cache removes the redundancy by storing each token's keys and values the first time they are computed.

A generation step then computes a key and value for one new token and appends them to the cache.

Attention reads the whole cache but only writes one column, so the per-step cost becomes linear.

This is why the first token of a response is slow and the rest arrive quickly.

That first pass, filling the cache from the prompt, is called prefill and is compute-bound.

The steps after it are decode, and they are bound by memory bandwidth rather than arithmetic.

The cache is not small: its size scales with layers, heads, context length and batch size together.

On long-context serving it routinely exceeds the memory taken by the model weights themselves.

That is the pressure behind multi-query and grouped-query attention, which share keys and values across heads.

It is also why serving systems such as vLLM page the cache in blocks rather than one contiguous slab.

Understanding the cache explains most of what is otherwise mysterious about inference cost and latency.

Deep dive

What is underneath The KV Cache

What is being cached

Generating a token requires attending to every previous token's keys and values. Those do not change once computed, so they are stored rather than recomputed.

K1:t=[k1,…,kt]V1:t=[v1,…,vt]K_{1:t} = [k_1, \ldots, k_t] \qquad V_{1:t} = [v_1, \ldots, v_t]

At step t+1t + 1 the model computes one new query, one new key and one new value, appends the last two to the cache, and attends over the whole thing.

Without the cache, generating token 1000 would mean recomputing the keys and values for all 999 before it, at every single step.

What it saves

without cache: O(n2) per tokenwith cache: O(n)\text{without cache: } O(n^2) \text{ per token} \qquad \text{with cache: } O(n)

Over a full sequence that is the difference between cubic and quadratic total work.

The cache is why the first token of a response is slow and every token after it is fast: the first pays for the whole prompt, the rest pay for one position each.

What it costs

This is the formula that actually matters, because it is what limits how long a context you can serve.

M=2⋅L⋅n⋅h⋅dh⋅b⋅pM = 2 \cdot L \cdot n \cdot h \cdot d_h \cdot b \cdot p
  • 22: one for keys, one for values.
  • LL: number of layers.
  • nn: sequence length so far.
  • hh: number of attention heads.
  • dhd_h: dimension per head.
  • bb: batch size, because every sequence in the batch has its own cache.
  • pp: bytes per number: 2 for fp16, 1 for int8.

A real number

For a 70B model with 80 layers, 64 heads of width 128, in fp16, one sequence of 8192 tokens:

M=2×80×8192×64×128×1×2=21.5 GBM = 2 \times 80 \times 8192 \times 64 \times 128 \times 1 \times 2 = 21.5 \text{ GB}

The weights of that model in fp16 are about 140 GB. The cache for eight such sequences is another 172 GB.

So at long context and any real batch size, the cache is larger than the model, and it is the cache that decides how many users a GPU can serve at once.

One step, in order

  1. Embed the new token and run it through the first layer.
  2. Compute its query, key and value.
  3. Append the key and value to that layer's cache.
  4. Attend the single new query over the whole cached key and value.
  5. Repeat for every layer, then sample the next token.

Why grouped-query attention exists

MGQA=2⋅L⋅n⋅g⋅dh⋅b⋅pM_{\text{GQA}} = 2 \cdot L \cdot n \cdot g \cdot d_h \cdot b \cdot p
  • gg: the number of key-value groups, far fewer than the number of heads.

Sharing one set of keys and values across several query heads divides the cache by h/gh / g directly.

At 64 heads and 8 groups that is an eightfold reduction, which is the difference between 21.5 GB and 2.7 GB. It is why most large open models released since 2023 use it.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1
What does the KV cache store between generation steps?
Concepts these five lines lean on
Self-AttentionAttentionServing Frameworks
LLMs

22 concepts in this module, then a graded test with every answer explained.

Study this module →
↑↓ move↵ openesc close