The KV Cache

Where keys and values come from

Inside every transformer layer, self-attention lets each token look at every previous token to decide what's relevant. To do that, each token is projected into three vectors:

• Query (Q) — "what am I looking for?"
• Key (K) — "what do I contain?", used to match against queries
• Value (V) — "what do I actually contribute?", weighted by the match score

Attention for a token computes how well its query matches every previous token's key, turns those match scores into weights, and produces a weighted sum of every previous token's value:

The critical observation: the key and value vectors for a given token never change, no matter how many more tokens are generated afterward. Token 5's key and value are fixed the moment token 5 is processed. Only the query changes at each new step, because it's a new token asking the question.

What the cache actually stores

The KV cache stores every previous token's key and value vectors, for every layer and every attention head, so they can be reused instead of recomputed.

At decode step $n$, instead of recomputing keys/values for tokens $1 \dots n-1$, the model:

1. Computes K and V for only the new token
2. Appends them to the cache
3. Computes attention using the new query against all cached keys/values

def decode_step(model, new_token, kv_cache):
    q, k, v = model.project(new_token)
    kv_cache.append(layer_idx, k, v)          # O(1) append, not recomputation

    all_k, all_v = kv_cache.get(layer_idx)    # everything seen so far
    output = attention(q, all_k, all_v)
    return output, kv_cache

This turns the $O(N^2)$ total cost from the previous lesson back into $O(N)$: each token's keys and values are computed exactly once, ever.

Why the cache is huge

The KV cache's size is the dominant memory cost during decoding for long sequences — often larger than the model weights themselves. The formula:

where $L$ is the number of layers, $H$ is the number of attention heads (or KV heads, see below), $d_h$ is the head dimension, $N$ is sequence length, $b$ is bytes per number (2 for FP16), and $P$ is the number of concurrent requests. The leading 2 accounts for storing both K and V.

Worked example. A 70B-parameter model with 80 layers, 64 KV heads, head dimension 128, running at FP16:

• Per token, per layer: $2 \times 64 \times 128 \times 2\text{ bytes} = 32{,}768$ bytes ≈ 32 KB
• Per token, across all 80 layers: $32\text{ KB} \times 80 ≈ 2.5$ MB
• For a single 4,000-token conversation: $2.5\text{ MB} \times 4{,}000 ≈ 10$ GB

Ten gigabytes of cache — for one conversation — on top of 140 GB of model weights. Serving 20 concurrent long conversations would need 200 GB just for caches. This single number explains why naive serving systems run out of memory long before they run out of compute, and it's the direct motivation for both multi-query attention (below) and PagedAttention (covered in the Serving Systems module).

Multi-head, multi-query, and grouped-query attention

The formula above has a lever most people don't expect: the number of KV heads doesn't have to equal the number of query heads.

• Multi-head attention (MHA) — the original design. Every query head has its own key/value heads. Best quality, largest cache.
• Multi-query attention (MQA) — all query heads share a single key/value head. Cache shrinks by a factor of $H$ (the head count), at some cost to quality.
• Grouped-query attention (GQA) — a middle ground: query heads are split into groups, and each group shares one KV head. Used by most modern production models (Llama, Mistral and others) because it recovers most of the quality of MHA while keeping most of the cache savings of MQA.

This is a training-time architectural choice, not something you can bolt on at serving time — but it's essential context, because it explains why some open-weight models are dramatically cheaper to serve at long context lengths than others of the same parameter count.

Cache reuse across requests: prefix caching

If two requests share a common prefix — the same system prompt, the same few-shot examples, the same document being asked multiple questions about — their KV cache entries for that shared prefix are identical, because attention only depends on the tokens before a given position, not on what comes after.

Prefix caching (also called automatic prefix caching or context caching) stores the KV cache for previously-seen prefixes and reuses it for new requests that start with the same tokens, skipping prefill for the shared portion entirely.

Request A:  [ system prompt |   doc   ] [ question 1 ]
Request B:  [ system prompt |   doc   ] [ question 2 ]
             \_______________________/   \__________/
                shared prefix —           new tokens —
                KV cache reused,          uncached suffix
                no prefill needed         prefill required

Both requests start with the exact same tokens, so Request B's shared portion reuses the KV cache Request A already computed. Only the new tokens on the right — the actual question — need to go through prefill.

For workloads with a long, shared system prompt and many short user turns — chatbots, RAG pipelines answering many questions about the same document — this can eliminate the majority of prefill compute across a session. It's one of the highest-leverage, lowest-risk optimizations available in modern serving frameworks, and it requires zero changes to the model itself.

What eviction and paging have to solve

Because the cache grows with every generated token and shrinks only when a request finishes, a serving system has to answer:

• Where does a new request's cache live if memory is fragmented from requests of different lengths finishing at different times?
• What happens when the cache genuinely doesn't fit — do you evict, reject, or offload to CPU memory?
• How do you avoid copying enormous cache blocks around just to keep a contiguous memory layout?

These are systems problems, not model problems, and they're serious enough to warrant purpose-built memory management, which is exactly what PagedAttention (Serving Systems module) was designed to solve — borrowing the idea of paged virtual memory from operating systems and applying it to KV cache blocks.

Summary

The KV cache stores each token's key and value vectors so attention never has to recompute them, turning quadratic decode cost back into linear cost — but at the price of memory that often exceeds the model weights themselves for long sequences. Architectural choices like grouped-query attention shrink the cache at the source; prefix caching reuses it across requests with shared context; and managing its layout in memory efficiently is one of the central systems problems in modern LLM serving.