The KV Cache: How Saving Past Work Turns 1,275 Computations Into 50

I was running a language model fully locally: no API, no network call, just the model's weights (the numbers it learned during training) on my own machine. The first token (a word or a piece of a word) took noticeably longer to appear than the ones after it.

My first assumption was that the model was "warming up", some one-time setup cost. A large part of the explanation turned out to be structural, and it has a name: the KV cache. A cache is a saved copy kept so you don't redo work, and "KV" stands for Key and Value, two lists of numbers that attention (the step where a model looks back at earlier words) builds for every token.

After the first step, every new token is cheap because it computes only its own Key and Value and reuses the saved ones for everything before it. It's one of those pieces of behind-the-scenes machinery that people who build with AI rely on every day without ever being asked to explain it.

What Generation Actually Repeats

A language model generates one token at a time. To produce token N, it runs the tokens before it through self-attention. Each token gets a Query (roughly, what it is looking for), a Key (what it offers to others), and a Value (the information it hands over), each a list of numbers called a vector. The new token compares its Query against every earlier token's Key to decide how much attention to pay to each one.

Why would anything need recomputing? Because the naive version of the loop rebuilds the Key and Value vectors for the entire sequence so far at every step, not just for the newest word. Generate token 50 and you recompute Keys and Values for tokens 1 through 49 again, just to add one more token to the end.

That adds up fast. In the companion code, a 50-token run does 1,275 Key/Value computations the naive way (1 + 2 + ... + 50, which is N(N+1)/2 and grows roughly with the square of N), when 50, one per token, would do. The toy uses fixed random inputs and a single attention head, so it counts Key/Value work rather than generating real words.

The Insight: Past Keys and Values Never Change

Why can past Keys and Values be reused at all? Because in a text generator, each token can only look backward. Token 12 attends only to tokens 1 through 12, so nothing generated afterward can alter it. Once its Key and Value are computed, they are fixed.

Only the new token's Query needs to look at everything that came before. It doesn't need anyone else's Query, just its own, compared against every Key that already exists.

So instead of recomputing, you store. Every time a token is processed, its Key and Value get saved. The next token computes only its own Query, Key, and Value, then looks back over the saved entries plus its own new one. In the companion run, that is 50 Key/Value computations instead of 1,275, a 25.5x difference. The outputs of the two loops matched to within floating-point rounding (largest difference 1.67e-15, effectively zero).

Why the First Token Feels Slow

If the cache makes later tokens cheap, why isn't the first one cheap too? Because before generation starts, there is no cache yet. The whole prompt (the text you send in) has to be run through the model to build Keys and Values for every token in it. This is called the "prefill" phase, and its cost grows with how long the prompt is.

After prefill, the model is in the "decode" phase, producing the reply one token at a time. Each step computes one new Key and Value and reuses the saved ones. It still compares its Query against every saved Key, so the work per token grows a little as the sequence gets longer, but the expensive part is no longer repeated. This is the structural reason a long prompt causes a longer pause before the first word appears. The companion code counts Key/Value work only; it does not time anything, so how big the pause is on your machine is something to measure yourself.

The Cost Nobody Mentions: Memory

If the cache is so useful, why not keep everything forever? Because it uses more memory to save work. Every token in the sequence, at every layer (one stage of the model's processing; models stack dozens), and in every key/value head (one of several parallel "viewpoints" inside a layer), needs its Key and Value stored for as long as that sequence stays in context.

The arithmetic is simple. One head, one layer, 50 tokens, with each Key and Value vector holding 64 numbers stored in float32 (4 bytes per number), takes 2 × 50 × 64 × 4 = 25,600 bytes. For scale, a hypothetical model with 32 layers, 32 heads, 128 numbers per head, stored in fp16 (2 bytes per number), holding 4,096 tokens needs 2.00 GiB (about 2 billion bytes) for a single sequence. That figure is for one conversation, so serving many at once multiplies it by the number of sequences held in memory.

This is why longer context windows (how much text the model can hold in view at once) are expensive to run, and why running a model fully locally means watching RAM climb as a conversation grows, even though the model's own weights don't change size.

The cache that makes generation fast is the same cache that limits how much context you can hold before running out of memory. You can shrink that cost but not skip it. Common ways to manage it are storing the cached numbers at lower precision (quantizing), deleting old entries (evicting), and letting several heads share one saved copy.

Get the Code

A script that runs the attention loop both ways, checks that the answers match, and does the memory arithmetic: KVCache.py.

Summary

The KV cache exists because a token's Key and Value never change once computed. Saving them turns generation from recomputing every earlier token at each step into computing one new Query, Key, and Value per token: 50 Key/Value computations instead of 1,275 in the companion run, with matching outputs. The price is memory, which grows with sequence length, layers, and heads. The same cache that makes later tokens cheap is what limits how much context you can hold.