KV Cache

What You’ll Learn

You’ll learn why naive autoregressive generation wastes work by recomputing the same K and V vectors at every step, and how the KV cache cuts that redundant projection work to linear growth. You’ll also trace what gets cached, why Q is not reused, and why cache memory becomes a serving bottleneck.

The Waste: Recomputing What Hasn’t Changed

During inference, a transformer generates text one token at a time. At step 4, the sequence is “The cat sat on” and the model runs self-attention over all 4 tokens to predict word 5.

Here’s the thing. At step 3, the model already computed K and V for “The”, “cat”, and “sat”. At step 4, it computes K and V for “The”, “cat”, “sat”, and “on”. Three of those four are identical to what it already computed one step ago. “The” hasn’t changed. Its embedding is the same. The weight matrices are the same. So the result is exactly the same numbers, recomputed for no reason.

(Forgot how Q, K, V work? Review Self-Attention)

Step through the animation below. Watch how the red “redo” cells pile up on the left side (no cache), while the right side (with cache) only ever does one new computation per step.

K/V Computations: Without vs. With Cache

Step 1: "The"

New computation Redundant (wasted) Cached (free)

First token: both approaches are identical. Compute K and V for "The".

What to look for: By step 4, the left side has done 10 K/V computations, but only 4 are unique. The right side does exactly 4, one per token. The gap grows with every step.

The Cost of Redundancy

For a sequence of length $n$ , generation without caching computes K and V a total of $1 + 2 + 3 + \cdots + n$ times. That’s quadratic growth for work that should be linear. Double the sequence length, and you do roughly four times the computation.

What if we just saved the results?

Without caching, total K/V computations for a sequence of length $n$ :

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)$

With caching, total K/V computations:

$\sum_{i=1}^{n} 1 = n = O(n)$

Each K/V computation costs $O(d^2)$ (multiplying a $d$ -dimensional embedding by a $d \times d$ weight matrix). So the total savings go from $O(n^2 d^2)$ to $O(n d^2)$ .

Note: the attention step itself is still $O(n^2 d)$ across all steps (because step $i$ attends over $i$ cached keys). The cache doesn’t eliminate this quadratic cost. It eliminates the redundant projection cost.

Quick Check

At generation step 50, how many K/V projections does the model compute with a KV cache?

Your turn

Choose an answer to check your understanding.

Attempts: 0

The Idea: Compute Once, Reuse Forever

Think of it like building a guest list for a growing dinner party. Every time a new guest arrives, you don’t re-interview everyone who’s already at the table. You already know their names (K) and what dish they brought (V). You only need to learn about the new arrival, then add them to the list.

Where the analogy breaks: at a real dinner party, guests might change their minds about what they brought. In a transformer, K and V for a given token are locked in the moment they’re computed. They depend only on that token’s embedding and the fixed weight matrices. Nothing about later tokens can change them.

Worked Example with Real Numbers

Step through the visualization below. It shows the actual matrix multiplications at each step and the cache growing row by row. All the numbers are computed from the same weight matrices, so you can verify with a calculator.

KV Cache: Step-by-Step

Step 1: Process "The"

New Computation

Token: "The" Embedding: [1, 0.5]

K = [1×0.1 + 0.5×0.2, 1×0.3 + 0.5×0.4] = [0.2, 0.5]

V = [1×0.5 + 0.5×0.3, 1×0.1 + 0.5×0.7] = [0.65, 0.45]

Cache Contents (1 entry)

Token	K	V	Status
"The"	[0.2, 0.5]	[0.65, 0.45]	new

Compute K and V for "The" by multiplying its embedding [1.0, 0.5] by the weight matrices. Store the result in the cache.

What to look for: At each step, only the “new” row is computed. The “cached” rows (green) carry forward unchanged from the previous step. The cache table grows by exactly one row per step.

Closing the Loop

What happens with these cached values? At step 3, the model computes Q for “sat”, then scores it against all three cached K vectors to get attention weights. Those weights blend the three cached V vectors into a context vector, which feeds into the rest of the transformer layer (feed-forward network, layer norm) to produce a probability distribution over the vocabulary. The highest-probability token becomes the prediction for position 4.

The cache grows by one row per step, and the attention computation uses the full cache every time. That’s the trade-off: we save compute but use more memory.

Why Not Cache Q?

A common question: if we cache K and V, why not cache Q too?

Think back to the dinner party. K is your name tag (“I’m token 3, here’s what I contain”). V is the dish you brought (“here’s the information I carry”). These don’t change when new guests arrive.

Q is different. Q is the question the new arrival asks: “Who here is relevant to me?” Each new token asks its own unique question. Token 50’s query has never existed before (token 50 didn’t exist until this step), so there’s nothing to cache.

There’s a deeper reason too. During generation, we only need Q for the single new token. We need K and V for all tokens (so the new token can attend to the full history). Caching saves work when you’d otherwise recompute the same values repeatedly. Q for the new token is computed exactly once and used once. No repetition, no savings from caching.

Fill in the Blanks

The KV cache stores and vectors from previous tokens. The vector is not cached because it's only needed for the new token being generated.

Fill in every blank, then check your answer.

The Trade-off: Memory

Caching is not free. For each layer and each attention head, we store two vectors (K and V) per token in the sequence. For long sequences and large models, this adds up fast.

Drag the sequence length slider below. Watch how memory scales, especially for the larger models.

KV Cache Memory (per request)

Sequence length:

GPT-2 (124M)

75 MB

LLaMA 7B

1.1 GB

GPT-3 (175B)

9.7 GB

At 2K tokens, GPT-3's KV cache alone uses 9.7 GB per request. Serving 100 users simultaneously requires 966 GB just for caches.

What to look for: GPT-3’s cache grows to multiple gigabytes even for modest sequence lengths. And this is per request. A server handling 100 concurrent users multiplies that cost by 100.

This memory pressure is exactly why techniques like Grouped-Query Attention (GQA) exist: by sharing K/V heads across multiple query heads, the cache shrinks proportionally.

Quick Check

Why is the KV cache a bigger problem for serving than for single-user inference?

Your turn

Choose an answer to check your understanding.

Attempts: 0

Quick Summary

Step	What happens	Intuition
New token arrives	Compute K, V, Q for that token only	Only the new guest needs an interview
Attention	Q attends over all cached K vectors	New guest looks at everyone’s name tags
Weighted sum	Blend all cached V vectors using attention weights	New guest collects relevant dishes
Update cache	Append new K, V to the cache	Add the new guest to the list

Prefill vs. Decode

Real inference has two phases with very different performance characteristics.

Prefill: The user’s prompt arrives all at once. All tokens can be processed in parallel (just like training), and their K/V vectors populate the cache in one batch. This phase is compute-bound because it involves large matrix multiplications over the full prompt.

Decode: Tokens are generated one at a time using the cache. This phase is memory-bound. The bottleneck is reading the growing KV cache from GPU memory at each step, not the arithmetic itself. The GPU spends most of its time waiting for data to arrive from memory, not doing math.

This distinction matters for system design. Prefill benefits from large batch sizes and raw compute throughput. Decode benefits from memory bandwidth and keeping cache sizes small.

KV Cache Compression

Several techniques reduce cache memory:

Quantization: Store K/V in FP8 or INT8 instead of FP16, halving or quartering memory at the cost of small precision loss.
Sliding window attention: Only cache the last $w$ tokens (used by Mistral). Older tokens fall out of the window. This works because most attention in practice is local.
PagedAttention (vLLM): Manages cache memory like an OS manages virtual memory pages. Eliminates fragmentation from variable-length sequences sharing GPU memory.

Why Not Cache the Layer Output?

Each layer’s output depends on the attention pattern over all tokens, including the new one. Since the new token changes which values get blended (by adding a new entry to attend to), the output for every position could in principle change. Unlike K and V (which depend only on the individual token’s embedding), the layer output is a function of the full sequence. Caching it wouldn’t help.

Learning Checklist

I can explain why naive autoregressive generation recomputes K and V unnecessarily
I can trace through the cache update process step by step with concrete numbers
I understand why Q is not cached but K and V are
I can estimate the memory cost of a KV cache given model dimensions
I know the difference between prefill (compute-bound) and decode (memory-bound) phases

Ready to understand the other major bottleneck in transformers? Self-Attention Complexity breaks down exactly where the quadratic cost comes from and what researchers are doing about it.