Ch 26. Caching: reusing the work

The chat in Ch 24 re-sent the whole conversation on every call, and the model read it all again. Even within one reply, it re-reads everything before each new token (Ch 11). Does it really redo all that work every time?

The chat in Ch 24 re-sent the whole conversation on every call: 163 tokens after the first exchange, and 633 by the time you asked your question. Inside each call, the token loop from Ch 11 does the same: to pick each new token, the model reads everything before it again. Does it really redo all that work every time?

It doesn’t have to. In attention (Ch 9), each token makes a key and a value that depend only on the text before it, so they never change once worked out. The model can store them and reuse them: this store is the KV cache. Step through GPT-2 small finishing “The cat sat on the” with the cache off and on:

It doesn’t have to. Remember how attention works (Ch 9): every token makes a query, a key, and a value. Each token can only look at the tokens before it, so its key and value depend only on the text before it, and adding more text later doesn’t change them. The model can work them out once and keep them. This store is the KV cache: with it, each new token only computes its own key and value, and its query is matched against the stored ones. Step through GPT-2 small finishing “The cat sat on the” with the cache off and on:

Without the cache, each new token took longer than the last, and 500 tokens took 43.0 seconds. With it, each took about the same time, about 20 milliseconds, and the run took 10.0 seconds. Both runs wrote exactly the same text.

Without the cache, every step runs the whole text through all 12 blocks again, so each step costs a little more than the last. Measured on a laptop, the time per new token grew from 23 to 139 milliseconds over 500 tokens, and the whole run took 43.0 seconds. With the cache, each token took about 20 milliseconds, and the run took 10.0 seconds. Both runs picked exactly the same 500 tokens; their scores differed by at most 0.01, from rounding when the same sums are added up in a different order.

Counting the work

Without the cache, step $t$ (counting from 0) runs all $p+t$ tokens through the model, so $n$ new tokens after a $p$-token prompt take

token passes. For the 5-token prompt and 500 tokens here, that’s 127,250, against 504 with the cache: 252 times as many. Yet the run took only 4.3 times as long. Running one token through the model is mostly waiting for its weights to arrive from memory, and many tokens in the same pass share that trip, so the extra tokens are cheap.^[1] With the cache, each step still compares its query with every stored key, so the time per token crept up a little, from about 19 to 20 milliseconds.

The price is memory: GPT-2 small stores 18,432 numbers for every token, and for large models and long prompts the cache runs to gigabytes.^[1]

The price is memory. GPT-2 small stores a key and a value in each of its 12 blocks for every token: 2 × 12 × 768 = 18,432 numbers per token. For large models and long prompts the cache runs to gigabytes, and keeping it small is a big part of serving them efficiently.^[1][1] Some other kinds of models avoid it by keeping a fixed-size memory instead.

The cache for a bigger model

Qwen2.5-1.5B-Instruct, the model in the Harnesses chapters, has 28 blocks, and its attention has 12 heads of 128 numbers each. A key and a value for every head would be 2 × 28 × 12 × 128 = 86,016 numbers per token. It stores far fewer, because its 12 heads share 2 sets of keys and values, an arrangement called grouped-query attention: 2 × 28 × 2 × 128 = 14,336 numbers, six times fewer.^[2] At 2 bytes each, that’s about 29 KB per token, and about 0.94 GB for a full 32,768-token context.

The cache for one reply is thrown away when the reply is done. But a chat’s next call starts with the same text as the last, plus a little more. So model providers keep the cache for the start of a prompt for a while, and reuse it when a new prompt starts the same way. This is prompt caching, and it makes those tokens much cheaper.^[2][3] Work that can wait is cheaper too: Anthropic charges half price for requests sent in a batch and answered later instead of straight away.^[4]

The KV cache for one reply is thrown away when the reply is done. But a chat’s next call starts with exactly the same text, plus a little more. So model providers keep the cache for the start of a prompt for a while, from minutes to hours, and a later prompt that starts the same way, token for token, picks up from there. This is prompt caching. Providers charge a tenth of the normal price or less for tokens read from the cache, and the reply starts sooner, because there is less to work through first.^[2][3][3][4] Cached tokens still count toward the context window, though: caching changes what they cost, not how much room they take.^[4][5] Work that can wait is cheaper too: Anthropic’s Batch API, which answers requests later instead of straight away, charges half price for both input and output tokens.^[5][6]

The match has to be exact, from the very first token: change one early word and everything after it has to be worked out again. See what that means for the Ch 24 session:

The match has to be exact, from the very first token. Change one early word and every key and value after it is different, because each depends on all the text before it. So the cache only helps up to the first difference. See what that means for the Ch 24 session:

With cached tokens at a tenth of the price, a call costs about $\text{new}+0.1\times \text{cached}$ in full-price tokens. Only appending sends 2,975 tokens, 2,342 of them cached, so it costs about 633 + 234 = 867: 29% of the uncached price. Putting the time at the top costs all 2,975.