#Caching

Most of what a language model computes for a request has already been computed before. The system prompt (the fixed instructions an app puts before every conversation) is the same for every user. A chat resends the whole conversation each turn. An agent, a model that calls tools in a loop until a task is done, re-reads the same tool definitions hundreds of times. Caching is the art of not doing that work twice, and next to batching it is the biggest lever on the cost and speed of serving an LLM.

#The KV cache, recapped

In Fast inference we met the KV cache: while generating, the model keeps every earlier token's keys and values (the only parts of a token that later tokens read) so each new token only computes its own. Three facts from there drive this whole chapter:

• A token's keys and values depend only on itself and the tokens before it, because attention is causal. The same prefix always produces the same cache, no matter which request it belongs to or what comes after it.
• Building the cache for a prompt is exactly what prefill does, and for a long prompt prefill is most of the work before the first token appears.
• The cache is big: about 128 KB per token for a Llama 3 8B-sized model, gigabytes for a long conversation, all of it in GPU memory that is limited to tens of gigabytes (capacity).

The first fact makes reuse possible: a prefix seen before can skip its prefill. The other two make it worth the trouble.

#Prefix caching: share what requests have in common

Because a cache entry depends only on its prefix, two requests that start with the same tokens can share those entries. "The same" means identical token by token from the very first one: if two prompts differ at token 10, they can share only tokens 1 to 9. Serving engines keep finished caches around and index them in a radix tree (a tree in which requests that start the same way share a branch, as in SGLang's RadixAttention or vLLM's automatic prefix caching). A new request walks the tree as far as its tokens match, reuses everything along the path, and only runs prefill on the rest.

Notice the follow-ups. The answer generated for request 1 was cached as it was generated, so when the user replies, the entire conversation is a hit and only the new message is computed. That is why a long chat does not get slower turn after turn as much as you might expect.

When memory runs out, the engine evicts (deletes) the least recently used leaves, the tree's end branches, first. Shared trunks like the system prompt are used constantly and stay.

#Prompt caching in APIs

Hosted model APIs expose the same idea as prompt caching. Some do it automatically for any repeated prefix; others let you mark a breakpoint explicitly. Either way the pricing has the same shape: the provider skips the prefill for cached tokens and passes on much of the saving, so cached input tokens are billed at a steep discount (commonly 50 to 90% off). Some providers charge a small premium to write the cache the first time. The cache lives for minutes to hours depending on the provider, not for days, so it pays off when the same prefix is reused often.

The cache matches prefixes, token by token. One changed token invalidates everything after it. That gives one practical rule:

Caching saves more than money. Skipping prefill on 25,000 tokens cuts the time to first token from seconds to a fraction of a second, which is what makes long system prompts and big tool catalogs practical in interactive apps.

#PagedAttention: memory like an operating system

Reuse needs a cache that can be shared and grown cheaply. Early serving systems gave each request one contiguous chunk of GPU memory. Nobody knows in advance how long an answer will be, so the chunk was sized for the maximum length. Most of it sat empty, and identical prefixes were stored again and again. Wasted cache memory means fewer sequences fit on the GPU, so batches are smaller and every user waits longer (batching).

PagedAttention (introduced with vLLM) borrows the idea of virtual memory, the trick an operating system uses to make scattered pages of memory look like one continuous piece. The cache is cut into fixed-size blocks of, say, 16 tokens. Each sequence has a block table listing which physical blocks hold its tokens, in order. Blocks are allocated one at a time as the sequence grows, can sit anywhere in memory, and can be shared: two block tables may point at the same block, with a reference count (how many sequences use the block). When a sequence needs to write into a shared block, it gets a private copy first (copy-on-write).

With paging, waste is limited to the unfilled part of each sequence's last block, so many more sequences fit on one GPU at once. More sequences per batch means higher throughput, which is why essentially every modern serving engine works this way, and why prefix caching can be implemented as nothing more than shared blocks.

#Making the cache smaller

When even a well-packed cache is too big, there are three families of fixes.

Store fewer heads. Grouped-query and multi-query attention (Fast inference) share keys and values across query heads. Multi-head latent attention goes further and stores one small compressed vector per token, from which keys and values are rebuilt; see Beyond the classic transformer.

Store fewer bits. Keys and values can be quantized to 8 or even 4 bits, halving or quartering the cache with a small loss in quality, the same idea as weight quantization in chapter 13.

Store fewer tokens. Throw some tokens out of the cache entirely. Which ones matters a lot:

• A sliding window keeps the last few thousand tokens. Surprisingly, it breaks badly once the very first tokens fall out. Softmax has to put its weight somewhere, and models learn to dump spare attention onto the first token, so it acts as a sink (chapter 5). Remove it and the weight lands on other tokens instead, scrambling every layer's output. StreamingLLM simply keeps a few sink tokens plus the window and runs stably on endless streams.
• Heavy-hitter methods such as H2O keep the tokens that have collected the most attention so far, plus recent ones. Later methods (SnapKV and others) choose per head and per layer.

Eviction is lossy: a dropped token can never be looked at again. It suits streaming and very long generations; for questions about a document, retrieval or a bigger cache is safer.

#Caching whole answers

At the top of the stack, an application can cache entire responses. An exact-match cache returns the stored answer for an identical request. A semantic cache embeds each question (chapter 3) and returns a stored answer when a new question is similar enough, for example cosine similarity above 0.95. It is fast and cheap, but the threshold is a trade-off: too low and users get answers to slightly different questions.

#Summary

• Keys and values depend only on the prefix, so any shared prefix can share its cache.
• Prefix caching (radix trees in the server, prompt caching in APIs) skips prefill for repeated prefixes: put static content first.
• PagedAttention stores the cache in blocks with block tables, sharing and copy-on-write, so far more requests fit in memory.
• The cache itself shrinks through fewer KV heads (GQA, MLA), fewer bits (KV quantization) or fewer tokens (sinks, sliding windows, heavy hitters).
• Applications can also cache whole answers, by exact match or by embedding similarity.

The cache grows with every token of context. The next chapter asks what happens when that context gets really long: Long context.