What are KV caches really?

KV caching lies sufficiently deep within the guts of how transformers work that really understanding how it can be used goes beyond any simple analogy. This is why the Internet is full of explanations of KV caching that are either grossly oversimplified (and therefore imply that KV caching is more useful than it really is) or dive straight into mathematical formalism (and therefore are incomprehensible to dumb-dumbs like me).

So I will try to thread that needle and explain how KV caching works in terms of how dumb-dumbs like me actually experience them.

What are keys, values, and KV caches?

Keys, values, and KV caches only make sense if you first understand what's happening when you ask a chatbot a question. There are fundamentally two steps to inferencing: prefill and decode. And anyone who's used ChatGPT or Claude has seen them firsthand.

What is prefill?

This is prefill:

When you ask a chatbot a question, there will be a lag before output starts being spit out. This lag the result of the prefill step running your query through the LLM. There are a bunch of terms that are related to this:

• Tokens are what LLMs ingest and spit out. They are approximately equivalent to a word in English.
• Time to first token is the lag time between you submitting your query and the first bits of output being generated. That is, it is the time it takes to perform prefill.
• Prefix is your initial query ("What are the key takeaways..."). It is usually combined with bunch of additional text (which you don't typically see) that gets sent to the LLM when you first ask your question.
• Prefill is the process of running the prefix through the model to get it to the point where it can begin predicting the next token and generating output.
• Keys and values are what the prefill step is calculating in silence. "KV" is shorthand for "key" and "value," and keys/values are parts of the model's internal machinery. LLMs generate multiple keys and values for each token they ingest, but keys and values are unique to each token. Different tokens never share the same keys or values.

The time to first token is directly related to how much work a GPU has to do to prefill the prefix. The longer your question, or the more context that has to be included in it (e.g., if it is pulling in context from the Internet or uploaded documents, or if it has a lengthy system prompt), the longer prefill will take.

What is decode?

This is decode:

Decode is what is happening as the chatbot is spitting out its response to your question. If you look closely at decode as it happens, you'll notice that it generates output word-by-word (or token-by-token); this is because decode is a loop where:

1. The model starts with the prefilled prefix and all the calculated keys and values.
2. The model uses ALL the keys and values to predict a good next token. That next token is what you see as the first bit of output.
3. The model then appends that first output token to the prefix.
4. The model then calculates the keys and values for the output token from step #3.
5. The model loops back to step #2.

Another way of visualizing this decode loop is this:

Each iteration of the loop generates one additional output token using all previous tokens' keys and values. It repeats this until the model predicts that there is no next token.

The time to generate the next output token is called time between tokens (TBT).

What makes keys and values cacheable?

Every time an LLM spits out a next word or token, it is using every previous token in that conversation to predict the best next word; in the above examples,

• The first output token (Good) is generated based on the prefix's keys and values
• The second output token (question) is generated using the keys and values belonging to the prefix and Good
• The third output token (to) is generated using the keys and values belonging to the prefix, Good, and question

Equally important is the fact that each output token does NOT depend on any future tokens that haven't yet been generated. As a result, keys and values have two properties that make them ideal for caching after they've been calculated:

1. Keys and values for each output token never change after they're generated
2. Keys and values for each output token are used every time a subsequent output token is generated

This is why KV caches exist. They store the computed keys and values of every token in the prefix and every output token, and these keys and values are repeatedly re-loaded into GPU cores' registers as output tokens are generated during the decode process. And as each new output token is generated, its keys and values get calculated as well, and they are appended to the KV cache so they can be used to generate future tokens.

KV cache is the reason why prefill time (time to first token; TTFT) is so much longer than the lag between each iteration of the decode loop (time between tokens; TBT):

• Prefill has to compute keys and values for every token in the entire prefix
• Each iteration of decode only needs to compute keys and values for a single token (the other keys and values can just be loaded from KV cache).

KV cache is also the reason why prefill is compute-bound (benefitting from more GPU FLOPS) while decode is memory bandwidth-bound (benefitting from more HBM TB/s); prefill requires computing keys and values for a lot of tokens in the prefix, while decode requires computing keys and values for one token. The rest of decode's time is spent reading cached KVs from memory.

EVERYBODY uses KV caches

KV caches provide such a huge speedup for decode that, in reality, everybody already uses KV caches. They are essential during decode.

Without a KV cache, you'd experience the prefill lag every time the LLM spits out a single next token. What's worse, that prefill time would get longer and longer, because the amount of tokens that would have to be prefilled would be getting longer as output tokens are appended to the prefix. The scaling is terrible; if calculating keys and values for one token takes a second...

• after the second token, recomputing all keys and values would take 4 seconds
• after the third token, recomputing would take 9 seconds
• after the fourth token, recomputing would take 16 seconds

Carrying out just a few back-and-forths with a chatbot would be excruciatingly slow without KV caches. A chatbot without a KV cache would just grind to a halt before it could finish outputting a single response.

Slow KV caches are only useful for offload

For a KV cache to be useful, it has to be faster than recomputing keys and values. The time it takes to recompute keys and values must be longer than the time it takes to read keys and values from cache. Recalling that the cost of recomputing the entire prefix depends on the length of the prefix, this means that KV caches are more useful as prefixes get really long.

This has a few implications:

1. The KV cache used during decode is always stored in GPU HBM. Going off-GPU every time a new token is being generated makes using a GPU pointless for decode. This is why decode performance depends on memory bandwidth more than FLOPS.
2. Slow KV caches are only useful for prefill, not during decode, and only when the amount of prefix that must be prefilled is long. The longer the prefix, the slower the KV cache can be and still be faster than recomputing all keys and values.

In practice, this means a slow KV cache is only useful when a new query is sent to an existing back-and-forth conversation. But even then, there are limitations:

Prefixes must be identical in order for their keys and values to be useful. Because each output token depends on all the tokens that came before it, any differences in a prefix makes everything that follows the change useless. This is fine for a single chat session that keeps extending itself, but it makes re-using KV caches across different prompts impossible for many common scenarios. For example, consider two people who ask the same chatbot the following:

• User 1: What are the key takeaways I want the audience to have...
• User 2: Tell me the key takeaways I want the audience to have...

Even though most of the question is identical (the key takeaways...), the fact that the first letter of the prompt is different means their KV caches will be completely useless to each other. You cannot cache just the common parts (the key takeaways ...) because their keys and values were generated based on the tokens that came before them in the prompt, and those tokens were not the same (What are vs. Tell me).

There are techniques that relax this constraint. However, they pose a security risk; chunks of cached keys and values "remember" what came before them, and there's no way to scrub that memory without defeating the purpose of caching. As a result, one person's query might be influenced by someone else's query if they share chunks of cached keys and values, and in the extreme case, it may be possible to infer what other people are querying.

Sharing KV caches across users can happen. If those two people asked the following:

• User 1: What are the key takeaways I want the audience to have...
• User 2: What are the key takeaways the audience should have...

There is a shared prefix of What are the key takeaways for whom the keys and values are identical. In principle, User 2 could benefit from User 1's cached keys and values for that shared prefix; this would make User 2's time to first token a little quicker than User 1's. However, this can also be the basis for a security problem because it allows User 2 to infer that her query shares the same prefix as someone else's. For this reason, production multi-user inferencing environments do not allow KV caches to be shared across users.

In practice, shared prefixes occur in the system prompt--that is, the secret instructions that the chatbot sees before it gets to your question. The system prompt is typically shared across all chat sessions because the chatbot is supposed to follow the same fundamental instructions regardless of the user request. As a result, shared KV caches are useful for chatbots with long system prompts; for example, the Claude models have very long system prompts which Anthropic makes public.

Slow KV caches can be useful

We're narrowed down that slow KV caches (like those stored on SSDs or on remote storage) have a pretty narrow scope.

Sharing prefixes across conversations: Long system prompts or common questions will have identical keys and values, and it may be faster to read them from storage into GPU memory than it would take to recompute them at the start of every conversation.

Offloading KV cache when there are long delays between successive: It may take me a minute or two to read a chatbot's response to my question, and during that time, the GPU is sitting idle. In a busy environment, it is more efficient to dump all keys and values from GPU memory to a slow KV cache, then use that GPU to serve someone else's query. This is called KV cache offload. When I am ready to ask another question, my keys and values can sometimes be reloaded into GPU memory from storage faster than it would take to recompute the entire conversation history's keys and values. This is less about performance and more about efficiently juggling users to keep GPU utilization high.

There are more sophisticated efficiency techniques like disaggregated inferencing which can also use slow KV caches to juggle more users and queries in a production environment. As with case #2 above (KV cache offloading when there are long delays between turns), this is a sophisticated efficiency optimization for inferencing and is primarily being applied in massive inferencing systems such as those deployed by hyperscalers.

Broadly speaking, these ultra-high efficiency, multi-user scenarios are where slow KV caches deliver the most benefit. Any time there are pauses within the back-and-forth of inferencing, KV cache offload can be used to free up a GPU to serve someone else's pending query if the cost of offloading and reloading is lower than recomputing. This criteria tends to appear most often in two cases:

1. Interacting with codebases and rich media. This could be someone asking a lot of questions about a large codebase that has been loaded into the model's context. Or it could be someone interacting with rich media like videos, which themselves take up a lot of context space.
2. Tool calling. Every time an agent or LLM has to call an external tool (whether it be basic websearch or calling another agent), it has to wait for a response before it can continue inferencing. If this wait time is long, KV cache offloading can be used to allow another inferencing session to use the GPU while the tool is doing its work. Agentic workflows can create huge working contexts as well, making it easier to justify offloading KV cache instead of recomputing.

Understanding vendor claims

I write all this because AI infrastructure vendors have been running amok, making bold claims about how their KV caching software can give incredible speedups. Below are a few claims I found within a few minutes of Googling.

Claim #1:

• Traditional recompute approach (112K token context): 57 seconds processing time
• (redacted) with KV Cache: 2.1 seconds loading time
• Result: Over 27X faster performance

Claim #2:

... we observed dramatic improvements in both speed and scalability—delivering up to 75X faster prefill times for long-context prompts, ...

Claim #3:

... boost LLM inference efficiency by 90% and TTFT by 20x using KV Cache Offload ...

Claim #4:

... consistently accelerated inference—delivering up to twenty times and six times respectively for larger, large context multi-GPU models ...

In all of these cases, these claims are comparing the cost of recomputing all keys and values from scratch (prefill) to simply loading cached keys and values from each company's respective product. They all claim to improve TTFT explicitly (#2 and #3) or implicitly (#1 and #4), but none of them make any statements about decode or end-to-end inferencing speedups--because remember, the KV cache used during decode MUST fit into GPU memory.

Slow KV caches, such as those supported by the above vendors' products, are only valuable when the cost to prefill is higher than the cost of reading from storage. And the cost to prefill is higher with longer prefixes. If you look closely, these claims specifically say their speedups are for "long context" tests, because these slow KV caches are much less useful when the prefix is shorter.

Let's take a closer look.

Claim #1

• Traditional recompute approach (112K token context): 57 seconds processing time
• (redacted) with KV Cache: 2.1 seconds loading time
• Result: Over 27X faster performance

In this first example, prefilling from scratch is faster than using their KV cache if you are prefilling 4K tokens (112K tokens divided by 27x) or less. For reference, this blog post is about 2,600 tokens, and it would be faster to prefill it than load it from this vendor's KV cache.

By comparison, the 112K token context they tested is about the length of The Hobbit by Tolkien.

Claim #2

... we observed dramatic improvements in both speed and scalability—delivering up to 75X faster prefill times for long-context prompts, ...

This 75x claim is based on the time to first token when prefilling from scratch versus loading all keys and values from storage. They used a prefix with 128,000 tokens to demonstrate this speedup. So again, this reflects the speed of recomputing all keys and values for the entirety of The Hobbit versus reading it from storage.

Claim #3

... boost LLM inference efficiency by 90% and TTFT by 20x using KV Cache Offload ...

As with above, this is a measurement of prefill improvement, and this was also made using 128K tokens.

It is tempting to say that this vendor's claim of 20x must mean its storage solution is slower than the vendor claiming 75x. However, this is not the case! The 75x vendor was using a smaller model (70 billion parameters), whereas this 20x vendor was using a bigger model. Bigger models mean more keys and values, more parameters, and more aggregate GPU memory required to serve them.

As a result, the difference between this claim's 20x and the earlier claim's 75x here reflects some combination of actual KV cache performance, GPU server configuration, and the differences in how the model was distributed over the GPUs used in the test. It's apples and oranges.

... consistently accelerated inference—delivering up to twenty times and six times respectively for larger, large context multi-GPU models ...

Again, this 20x claim is based on 128K tokens (The Hobbit) being prefilled. This vendor actually showed plots along with this claim, and to their credit, the plots reveal that the speedup drops dramatically with smaller prefix sizes.

Critically evaluating claims

I don't say all this just to dunk on vendors selling software that is positioned to accelerate KV caching; every vendor is on the same bandwagon and trying to claim success in whatever dimensions of the AI industry they can. However, it is important to understand that these huge speedups are the result of setting up a test where the cost of prefill is very high.

It's not hard to come up with these scenarios where the cost of recomputing prefill is extreme compared to the cost of simply reading the precomputed keys and values from storage. If you want a KV cache to look really fast, the recipe is simple:

1. Only look at prefill performance. It's the only place that slow KV caches are relevant. Decode performance on a slow KV cache will look atrocious no matter what, which is why nobody does it.
2. Pick a model with a ton of parameters. More parameters means that prefill (and decode) require more computations.
3. Test with a very large context window, and fill it to the brim with input tokens. Longer prefixes make prefill take longer.
4. Run your GPUs at lower power. This reduces its FLOPS (increasing prefill time) but doesn't change its PCIe bandwidth (so I/O time stays the same).

The result would be a very slow prefill compared to the speed of reading cached keys and values from storage. This will result in a bombastic speedup.