KV-caching: why generation is fast and where the memory goes

The attention-head article distinguished learned projection matrices from the queries, keys, and values computed for an input. The block article followed their mixtures into residual updates. Here we add the time dimension: what can a causal decoder reuse when it appends another token?

A prompt is processed in a parallel forward pass. Generation then adds tokens one at a time. Earlier causal representations do not depend on newly appended tokens, so their keys and values can be stored and reused. This article derives that cache and its memory cost.

Why generation repeats itself

Recall the one structural fact that makes a decoder a decoder: the causal mask. In a decoder block, self-attention is masked so that token t can attend only to tokens 1..t — itself and everything before it, never anything after. (This is the single bit that separates a GPT decoder from a BERT encoder; everything else inside the block is identical.) That mask is what lets the model generate left to right: each position’s output depends only on positions already written.

Generation, then, is a loop. Feed the prompt, read the distribution at the last position, sample a token, append it to the sequence, and feed the whole thing back in to get the next one. Repeat until done. The crucial detail is what the model has to compute each time around. Because Q, K, and V are produced fresh on every forward pass, a naive implementation that simply re-runs the model on the growing sequence recomputes the keys and values of every token, at every layer, on every single step — even though all but the newest token are identical to the step before. Token 5’s key vector is the same whether the model computes it when the sequence is 5 tokens long or 500 tokens long. The naive loop computes it 495 times anyway.

Count the work. To emit the token at position t, a full forward pass over t tokens builds a t × t attention score matrix per head — O(t²) work. Do that for each of n generated tokens and the total is O(n³): cubic cost to produce a linear amount of text. The quadratic-per-step term is pure waste, because the only genuinely new information at step t is the single most recent token. Everything else is being recomputed for no reason.

The cache: compute the new token, remember the rest

The fix follows directly from the observation. If past tokens’ keys and values never change, store them. Maintain a running buffer — the KV cache — holding K and V for every token seen so far, at every layer. Then each generation step does only the irreducible work:

1. Compute Q, K, V for the single new token (one row, not the whole sequence).
2. Append that token’s K and V to the cache.
3. Attend the new token’s one query against the entire cached K and V.
4. Read the output, sample the next token, go to 1.

The per-step cost collapses from O(t²) to O(t) — one query against t keys instead of a full t × t matrix — and the total from O(n³) to O(n²). That is the whole reason interactive generation is fast enough to stream a response word by word instead of stalling longer at every token.

Notice the asymmetry that gives the cache its name. We keep K and V but throw away every past query. This is not an oversight — a past token’s query is genuinely never needed again. A query’s only job is to produce that token’s output, which happened on the step that token was the newest one and will never be revisited. Keys and values, by contrast, are read by every future token’s query. So the thing worth caching is exactly K and V, and the thing safe to discard is Q. It is a KV cache, not a QKV cache, for a reason.

Two regimes: prefill and decode

The loop above hides a split worth naming, because it explains why “time to first token” and “time per subsequent token” are governed by different hardware limits. Processing the prompt is a single parallel pass over all its tokens at once — exactly the full-sequence computation from the block article — and it fills the cache for every prompt position in one shot. This prefill phase is compute-bound: big matrix multiplies that saturate the GPU’s arithmetic units. Decode — the one-token-at-a-time loop afterward — is the opposite. Each step does tiny matmuls but must stream the entire cache out of memory to attend against it, so it is memory-bandwidth-bound and leaves most of the GPU’s compute idle. (The same roofline distinction the GPU execution model article draws between compute- and bandwidth-bound kernels.) The takeaway: prefill cost scales with prompt length and compute; decode cost scales with the cache size you have to re-read every step. Which points straight at the cache as the thing that matters.

The cost ledger: where the memory goes

Caching trades computation for memory, and the bill comes due in gigabytes. For standard multi-head attention, each layer stores one key and one value per token across all heads. With total key and value widths both equal to model width d, N layers, and a fixed storage precision:

KV bytes per token ≈ 2 · N · d · (bytes per value)

The 2 is the pair (K and V); N is the number of layers, each with its own cache; d is the model width summed across all heads. For GPT-3 at fp16 that is 2 × 96 × 12288 × 2 bytes ≈ 4.7 MB per token. A 2048-token context holds about 9.6 GB of cache; hypothetically extend that same configuration to a 200K-token context and the cache alone is ~940 GB — far beyond any single GPU.

Now put that number next to the model’s weights, because the comparison is the whole point. GPT-3’s weights are fixed: 175B × 2 bytes = 350 GB at fp16, the same whether one user is connected or a thousand. The cache is what grows — linearly with context length, and again linearly with the number of requests batched together, since every concurrent request carries its own cache. On a serving node, weights are a one-time deduction from memory; everything left over is divided among the live requests’ caches. So the number of users you can serve at once, and the longest context you can offer, are both set not by the model’s size but by how much KV cache fits in the memory the weights didn’t already claim. At long context the cache dwarfs the weights — 940 GB against 350 GB — and the model you spent millions training becomes the small object in the memory budget. (This is the inference side of the picture where the memory goes lays out in full.)

This is why an entire layer of systems engineering exists around the cache rather than around the model. PagedAttention manages it like operating-system virtual memory, allocating it in fixed pages to kill fragmentation. Prefix caching reuses the cache for a shared system prompt across many requests instead of rebuilding it each time. KV-cache quantization stores K and V in int8 or fp8 to halve or quarter the footprint. Each is a direct assault on the 2 · N · d · context · batch bytes above; the inference-optimization article works through how they do it.

The bottleneck, named

Strip the ledger to its lever. The cache size is 2 · N · d · context · batch · bytes. Context and batch are demands from users — you do not get to shrink those without offering a worse product. Bytes-per-value is what quantization attacks. That leaves the 2 · N · d term, baked into the architecture, where d is really n_heads · d_head — and the part of it that the model designer can change without touching what the model learns is the number of key/value heads.

That single observation is the hook for everything that comes next. If most of the cache is “one K and one V per attention head per layer,” then the way to shrink it is to have fewer keys and values than you have heads doing the querying. There are two ways to do that:

• Share them — let several query heads read from one shared K/V head. This is grouped-query attention, the subject of the next article, and it is now the default in nearly every new open-weight decoder.
• Compress them — project K and V down into a small shared latent vector and cache that instead. This is multi-head latent attention, which the blog covers as the destination of the latent bottleneck.

Both start from the number on this page. KV-caching is what makes generation tractable; the cache it creates is what makes generation expensive; and the rest of modern attention design is the running argument over how to make that cache smaller without making the model worse.