KV cache fundamentals

Sneha’s code review comment was still open on Arjun’s pull request the next morning. It was one line long.

“What exactly does the provider keep for five minutes? We send the full text every time. If it’s not our text, what is it, and why does one changed character at the start throw all of it away?”

Arjun had typed three different answers and deleted all of them. Each one used the word “cache” to explain the word “cache”.

He took his laptop to Priya’s desk. “I can make prompt caching work,” he said. “I can’t explain it. Sneha’s question is fair.”

Priya smiled and picked up a marker. “Good. Most people who use prompt caching never ask. To answer it, we need to go inside the model for half an hour. You’ll come out understanding why prompt caching has every rule it has, why long conversations are expensive to host, and why your answers type out one word at a time.”

How a model writes, one token at a time

“Start with what you know from Module 01,” Priya said. “How does a model produce an answer?”

“It predicts the next token. A token is a word-piece, roughly three-quarters of a word. The model looks at all the text so far, picks a likely next token, adds it to the end, and repeats.”

“Exactly. So if the prompt is ‘The Baner store closes at’ and the answer is ‘9 pm.’, how many times does the model run?”

“Three. Once for ‘9’, once for ‘pm’, once for the full stop.”

“And what does it look at each time?”

“Everything so far. The prompt plus whatever it has written.”

That is the autoregressive loop: each new token is predicted from all the tokens before it, then becomes part of the input for the next prediction. It is why answers stream out word by word, as you saw in Module 19.

Arjun’s naive picture

Arjun had always pictured the loop like this:

tokens = tokenize("The Baner store closes at")
for step in range(3):
    next_token = model.predict_next(tokens)   # reads ALL tokens, from scratch
    tokens.append(next_token)

In this picture, every step runs the whole model over the whole sequence again. Step 1 processes 5 tokens. Step 2 processes 6. Step 3 processes 7. That is 18 token-passes (one token going through every layer of the model) to write three tokens.

“Now scale it,” Priya said. “Generate 1,000 tokens, starting from one.”

He worked it out on the board: 1 + 2 + 3 + … + 1,000 = 500,500 token-passes.

“And if the model only did the new token’s work each step?”

“1,000.”

“Five hundred times less work. Now make it Crumb’s handbook bot: a 30,000-token prompt and a 300-token answer.”

Each of the 300 steps would reprocess at least 30,000 tokens. That is 300 × 30,000 plus a little, about 9 million token-passes, against roughly 30,300 if each step did only its own work. The naive picture is not how any real system runs. But it is the right starting point, because the trick that fixes it is exactly what prompt caching sells you.

This growth pattern is called quadratic: double the length and the work roughly quadruples. Anything quadratic becomes painful fast.

The cards on the table

Priya drew a long meeting table.

“Imagine a meeting at Crumb where people speak one after another. Every time someone speaks, they leave an index card on the table. On the front of the card, they write a short label saying what their point is about: ‘closing time’, ‘Baner store’, ‘a place’. On the back, they write what they actually contributed.”

“When a new person is about to speak, they first write down what they are looking for. Then they scan the fronts of all the cards, find the ones that match what they are looking for best, and read the backs of those cards, paying most attention to the closest matches. Then they speak, and leave their own card.”

“The front is the key, the back is the value, and what the new person is looking for is the query,” Arjun said. He had seen the words before without understanding them.

“Right. Now here is the important question. When the seventh person speaks, do the first six need to rewrite their cards?”

He thought about it. “No. Their cards describe what they said. Nothing the seventh person says changes what the first six said.”

“So you can leave the cards on the table and reuse them. That stack of cards is the KV cache. Without it, every time someone new spoke, everyone before them would have to stand up and rewrite their card from scratch. That’s your naive loop.”

Where the analogy breaks: a real model has one table per layer (one stage of processing in the model; mid-size models have dozens), so every token leaves a card at each of them. The cards hold lists of numbers, not words. And the new speaker does not pick a few cards; they read all of them, blended by how well each one matches.

Queries, keys and values, in plain words

Now the real terms, one level down. You met attention in Module 01: the step where each token looks back at the earlier tokens that matter to it. Here is what that looks like inside.

At every layer, each token produces three vectors (a vector is a list of numbers):

• A query: “what am I looking for in the earlier text?”
• A key: “this is what I can offer, as a label others can match against.”
• A value: “this is the information I pass on if someone attends to me.”

When a new token is processed, its query is compared with the keys of every earlier token (and its own). The comparison gives a score for each earlier token. The scores are turned into weights that add up to 1, and the token takes a weighted blend of the earlier tokens’ values. That blend is what it “learned” from the context at that layer, and it feeds into the next layer.

Two facts make the KV cache possible:

1. A token only looks backward. In a model that writes text, tokens attend only to tokens before them. So adding a new token at the end cannot change any earlier token’s keys or values.
2. Only the newest token needs a query. Old tokens have already done their looking. The model needs the newest token’s query, plus the keys and values of everything before it.

So the model keeps every earlier token’s keys and values in memory, layer by layer. Each step it computes the query, key and value for one new token, compares that query against all the stored keys, blends the stored values, appends the new key and value to the store, and moves on.

Following five words through the cache

Here is one sentence traced end to end. To keep it readable, assume each word is one token: The, Baner, store, closes, at (a real tokenizer may split “Baner” into two pieces). The model will write 9, pm, ..

Step	Without a KV cache: tokens processed	With a KV cache: tokens processed	New token’s query compared with	Keys and values stored afterwards
1 (read the prompt)	5: The, Baner, store, closes, at	5: same	Each prompt token’s own earlier tokens	5
2 (after writing “9”)	6: all of the above plus 9	1: “9”	6 keys (5 stored + its own)	6
3 (after writing “pm”)	7: all plus 9, pm	1: “pm”	7 keys	7
Total	18 token-passes	7 token-passes

Look at step 2 closely. With the cache, the model does not touch The, Baner, store, closes or at again, except to read their stored keys and values. It runs 9 through every layer once. At each layer, 9’s query is compared with six keys, the best-matching values (most likely closes and at, which tell it a time is expected) get the most weight, and the result moves up to the next layer. At the top, the model predicts pm.

Two honest details:

• The comparison step still grows: at step 1,000, the new token’s query is compared with 1,000 keys. But comparing is cheap next to running a token through all the model’s layers, so for typical lengths the cache turns the dominant cost from quadratic into roughly linear.
• The result is exactly the same with and without the cache (apart from tiny rounding differences in the arithmetic). The KV cache is a pure speed-up. It does not approximate anything.

Here is the same idea as an animation. Step through it and watch which work is reused:

The price of remembering

The KV cache trades computation for memory. Every token in the conversation leaves a key and a value at every layer, and they sit in the GPU’s memory (the graphics processor that runs the model, whose fast memory is small and expensive) for as long as the conversation is active.

You can estimate the size with one formula:

KV cache bytes = 2 (key and value) × layers × KV heads × head size × bytes per number × tokens

The new words:

• An attention head is one of several parallel “lookers” in each layer, each matching on a different kind of relationship. KV heads is how many separate sets of keys and values a layer stores.
• The head size is the length of each key or value vector.
• Bytes per number is 2 for the common 16-bit format.

A worked number, for an illustrative mid-size open model roughly the shape of today’s 8-billion-parameter models: 32 layers, 8 KV heads, a head size of 128, 16-bit numbers.

• Per token: 2 × 32 × 8 × 128 × 2 = 131,072 bytes, about 128 KB.
• For one handbook request of 30,000 tokens: 30,000 × 128 KB ≈ 3.9 GB.
• For 20 store managers with handbook conversations open at once: about 79 GB.

These numbers are illustrative; real models differ, and providers do not publish all their details. But the shape is right. A large data-centre GPU might have 80 GB of memory, and the model’s own weights already take around 16 GB at 16 bits for a model this size. Twenty long conversations would not fit beside them. Long contexts and many simultaneous users eat GPU memory, and that, not arithmetic, is often what limits how many people one GPU can serve.

Engineers fight this with a few techniques you will meet properly in Module 32:

• Grouped-query attention. Many query heads share a smaller number of KV heads. Our example model already does this: it has 32 query heads but only 8 KV heads. Without sharing, the cache would be four times larger, about 15.7 GB for one 30,000-token request.
• Paged attention. Used by the vLLM serving engine, it stores the cache in small fixed-size blocks, like pages in a notebook, instead of one long reserved strip per conversation. That wastes far less memory, so more conversations fit at once.
• Quantised KV cache. Storing keys and values in 8 bits instead of 16 halves the memory, at a small cost in accuracy. Quantisation (storing numbers with fewer bits) is the same trick you used on model weights with Ollama in Module 20.

Prompt caching, seen from the inside

Now Sneha’s original question has a precise answer. When Anthropic or OpenAI “caches your prompt”, the provider keeps the KV cache it built while reading your prefix, instead of throwing it away when the request ends. On the next request with the same prefix, it loads those keys and values and starts work at the first new token.

Every rule from the last two lessons follows:

• Exact prefix match. Stored keys and values for a token depend on every token before it.
• Per model. The numbers come from one model’s internal weights. A different model, or a new version of the same model, computes different keys and values from the same text.
• A lifetime of minutes. Gigabytes of fast memory per long prompt are expensive to hold. Unused entries are evicted.
• A write premium. Keeping and moving the cache costs the provider memory and bandwidth.
• Cheap reads and a faster first token. Reading 30,000 tokens is mostly the work of computing their keys and values through every layer. Loading saved ones skips that work.

Try it: see the KV cache on your laptop

You can measure the KV cache yourself with GPT-2, a small open model from Hugging Face (Module 11) that runs fine on a laptop CPU. The generate() function uses the cache by default; use_cache=False turns it off so the model reprocesses the whole sequence every step, like Arjun’s naive loop.

uv add transformers torch

import time

from transformers import AutoModelForCausalLM, AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")
model = AutoModelForCausalLM.from_pretrained("gpt2")
inputs = tokenizer("The Baner store closes at", return_tensors="pt")

outputs = {}
for use_cache in (True, False):
    start = time.perf_counter()
    out = model.generate(
        **inputs,
        max_new_tokens=200,
        min_new_tokens=200,          # force exactly 200 new tokens for a fair race
        do_sample=False,             # greedy: same choice every time
        use_cache=use_cache,
        pad_token_id=tokenizer.eos_token_id,
    )
    outputs[use_cache] = out
    print(f"use_cache={use_cache}: {time.perf_counter() - start:.1f} s")

print("Same text:", tokenizer.decode(outputs[True][0]) == tokenizer.decode(outputs[False][0]))

What the new lines do:

• AutoModelForCausalLM.from_pretrained("gpt2") downloads GPT-2 (about 500 MB) the first time. A causal language model is one that predicts the next token from earlier ones only.
• do_sample=False makes the model always pick its top choice, so both runs should produce the same text.
• min_new_tokens=200 stops the model from finishing early, so both runs do the same amount of writing.

Output on Arjun’s laptop (yours will differ):

use_cache=True: 2.8 s
use_cache=False: 10.9 s
Same text: True

Same text, about four times slower without the cache. Now change both token counts to 50, then to 600, and run it again. The gap should be small at 50 and much larger at 600, because the work without the cache grows quadratically. If “Same text” ever prints False, a rounding difference changed one close choice; the cache is still exact in principle.

Library APIs change quickly. If a name has moved, check the docs linked below.

Where it breaks

Arjun posted his answer to Sneha’s review, with the five-word table. Then Priya made him list the misconceptions he had held that morning.

• “The cache stores answers.” No. It stores keys and values for prompt tokens. Every answer is generated fresh.
• “The KV cache means the model remembers me between conversations.” No. It lives for one request, or for a few minutes when a provider keeps it for prompt caching. The model is still stateless: it learns nothing from your conversation, and its weights never change.
• “With a KV cache, every new token costs the same.” Nearly, but not quite. Each new token still compares its query with every stored key, so token 30,001 does a bit more work than token 301. Very long contexts make each step slightly slower.
• “Memory is the provider’s problem.” Not when you host the model yourself. In Module 20 you ran models with Ollama; its num_ctx option sets the context length, and raising it reserves more memory for the KV cache. Set it to 32,000 on a laptop and you may run out of memory or slow to a crawl.

Common mistakes

• Thinking prompt caching stores your text. It stores the model’s computed keys and values for your text. That is why it is per model and needs an exact prefix.
• Expecting a cache hit after editing anything early in the prompt. Every later token’s keys and values depend on the edit. Keep the front stable.
• Ignoring KV memory when self-hosting. Long contexts times many users can exceed GPU memory before the GPU’s arithmetic is busy. Budget memory per conversation with the formula above.
• Assuming a disabled cache only changes speed a little. Without it, generation work grows quadratically with length. At hundreds of tokens, that is several times slower; at thousands, far worse.
• Mixing up the KV cache and prompt caching. The KV cache exists inside every request. Prompt caching is a provider feature that keeps it between requests for a prefix.

Recap

• A model writes one token at a time, and each token looks back at all earlier tokens through attention.
• At every layer, each token produces a query, a key and a value; a new token’s query is compared with all earlier keys to blend their values.
• Because tokens only look backward, earlier keys and values never change, so the model stores them: that is the KV cache. It turns 500,500 token-passes into 1,000 for a 1,000-token answer.
• The KV cache costs memory: about 2 × layers × KV heads × head size × bytes × tokens, roughly 128 KB per token for an illustrative mid-size model.
• Prompt caching is the provider keeping the KV cache for your prefix between requests, which is why it needs an exact prefix, is per model, expires, and charges a write premium.

That afternoon Meera stopped by. “Sneha says you finally explained the cache properly. Try me.”

“When the model reads our handbook, it writes a little card of notes for every word, about what that word means in context. Those cards are most of the work. Prompt caching means the provider keeps the cards for five minutes. But each card depends on every word before it, so if we change the first line, every card after it is wrong and has to be rewritten.”

“I followed that.” She turned her tablet towards him, the handbook bot open on it. “Now explain this. I asked a question. It sat there thinking for two seconds, then it typed the answer out slowly, like someone with one finger. And on your price list, the words it writes cost five times the words we send. Why?”

Arjun opened his mouth, then closed it. Priya was already drawing a kitchen on the whiteboard.

Go deeper

• The Illustrated Transformer, with diagrams of queries, keys and values: https://jalammar.github.io/illustrated-transformer/
• Attention Is All You Need, the original transformer paper: https://arxiv.org/abs/1706.03762
• vLLM documentation, including paged attention: https://docs.vllm.ai
• Hugging Face documentation for generate() and caching: https://huggingface.co/docs
• Module 30 builds a transformer from scratch, and Module 32 goes deeper into KV caches, paged attention and FlashAttention.