When we talk about LLMs, we usually talk about what they can do, like write code, summarize documents, explain things, and so on. But under all of that, there is a whole set of problems that has less to do with “intelligence” and more to do with making the system run efficiently.
One of those problems is memory. Every time an LLM generates a new token, it still has to use the information that came before. And as the context gets longer, there is a lot of that information to deal with.
So a very natural question comes up:
If the model has already processed the previous tokens, why should it keep doing the same work again?
That question leads us to the KV cache. And, quite unexpectedly, it also leads us back to something that Operating Systems have been doing for decades.
Why decoding keeps repeating work
To understand what happens, we first need to look at how an LLM processes text. There are two important stages during inference: Prefill and Decode.
When you send a prompt to a model, the model first processes the input tokens. This is known as the prefill phase.
For example, suppose your prompt is:
“Explain how photosynthesis works in simple language”
The model can process the tokens in that prompt largely in parallel, thanks to GPUs!
But then comes the “generation” part that matters the most for users. During this phase, the model starts producing the answer one token at a time. This is the decode phase, and it is autoregressive, which basically means: the next token depends on the tokens that came before it
So, if the model has generated:
“Photosynthesis is the process by which”
it now has to figure out what comes next.
Maybe it generates:
“plants”
then: “convert”
then: “light” and so on.
So each new token depends on the existing context. And that is where the inefficiency starts to show up.
To understand that, let's use a smaller example:
“The tired engineer drank the cold coffee.”
Suppose the model is currently generating the word “coffee.”
To generate that token, the model needs information from the previous tokens:
The → tired → engineer → drank → the → cold
But when it generated “cold,” it had already processed the information associated with:
The → tired → engineer → drank → the
And when it generated “the,” it had already processed:
The → tired → engineer → drank
So every time a new token is generated, the model has to look at all the tokens that came before it. As the sequence gets longer, that means revisiting more and more of the same history again.
The model still needs to perform a new attention operation for the newly generated token, because the Query for that token is new. You can look at the attention formula for reference:
$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
A natural question comes up here, can anything be reused from the previous tokens? And if yes, then what exactly can be reused?
A quick detour to Q, K and V
This is where the Transformer attention mechanism becomes useful. For every token, the attention mechanism produces three vectors: Query (Q), Key (K), and Value (V)
The terminology sounds pretty abstract at first, but the intuition is very simple.
Think of a Query as:
“What am I looking for right now?”
A Key is just:
“What kind of information do I contain?”
And a Value is:
“Here is the information itself.”
When a new token is being generated, its Query is used to determine which previous tokens are relevant. The model then compares that Query with the Keys from earlier tokens. If a particular Key looks relevant, the corresponding Value contributes more strongly to the final attention output.
So why do we cache K and V, but not Q?
The Query changes with every new token because it represents what the current token is looking for. The Keys and Values belong to the tokens already in the context, so once we've computed them, we can reuse them when the next token arrives. This is literally what the KV cache stores.
(For now, you do not need to understand all the nitty-gritties revolving matrix multiplication to understand why the KV cache exists. But if you want to go deeper into the attention mechanism itself, I have a separate Transformers blog for that)
Note: The “cache” that we are talking about here is not related to CPU level hardware caches like L1, L2, or L3. Despite sharing the word “cache,” they serve very different purposes.
What the KV cache saves
This is worth pointing out because the KV cache is often explained as if it makes the model “remember” previous tokens. But that is not really what is happening. The model still has the previous tokens as part of its context.
The KV cache is just an optimization technique for the computation required to attend to that context. Without caching, the system may have to repeatedly compute the Key and Value vectors for previous tokens as decoding progresses. With caching, those K and V tensors are computed once and kept. Then, when the next token is generated, the model computes the new Query and uses it against the stored Keys and Values.
So the whole process becomes something like:
A new token arrives
→ compute its Query → look at cached Keys → use the corresponding cached Values → generate the next token
instead of repeatedly rebuilding the K/V information for the entire history.
If you only have 20 tokens, this may not sound like a huge deal. But if you have thousands of tokens, it makes a very big difference!
Prefill vs Decode
This is where things usually start to feel a little confusing, because prefill and decode are very different at the hardware level.
During prefill, the model receives a large chunk of tokens all at once. That gives the GPU plenty of work it can process in parallel, so even though a lot is happening, it can feel surprisingly fast.
On the other hand, decode works very differently. Here the model generates one token at a time. The amount of new computation per step is small, but the new token still needs to use all the K/V tensors we have cached so far. So the bottleneck is different in the two phases. In many serving workloads, prefill is compute-bound, while decode is memory-bound.
A GPU is not just a big compute engine. It also has to keep moving data between memory and the compute units. If that movement is slow, the GPU can end up waiting around even when it has plenty of compute available.
The KV cache is a good example of that.
The memory problem
The obvious reaction to all of this is:
Great. Just cache everything!
And that works, definitely! At least until you see how much memory that cache can start eating up.
Every new token adds more K and V tensors to the cache. Then it grows really fast with every layer having its own K and V, every active request having its own separate context, and all of that grows enormously with the sequence length, the model design, the precision you store things in, and how many requests you're serving at the same time!
That's a lot. A simplified way to think about KV cache memory is:
$$ \text{KV Cache Size} = 2 \times L \times H_{KV} \times D \times S \times B \times P $$
where:
- 2 is because you store both Keys and Values
- L is the number of transformer layers
- Hₖᵛ is the number of key/value heads
- D is the size of each attention head
- S is the sequence length in tokens
- B is the number of concurrent requests, and
- P is the number of bytes used to store each value
The main thing here is what happens when S and B go up. A longer context means a bigger cache, and more users also means a bigger cache. In real systems, both usually increase together.
This is the point where serving an LLM shifts from being just a compute problem to becoming a memory management problem.
A quick example
Let's take the model LLaMA-2-7B. It has 32 transformer layers, 32 attention heads, and a head dimension of 128. Since it uses standard Multi-Head Attention, we also have 32 K/V heads to store in the cache.
Using FP16, a sequence of 4,096 tokens, and B = 1 (single request), the KV-cache for just one request is roughly:
$$ 2 \times 32 \times 32 \times 128 \times 4096 \times 2 = 2{,}147{,}483{,}648 \text{ bytes} \approx 2.15\text{ GB} $$
That's 2.15 GB just for the KV cache of one request! And of course, the model weights need memory too, along with activations, CUDA/runtime overhead, and everything else running on the GPU. So this means, a GPU cannot give all of its memory to the KV cache.
For reference, an NVIDIA H100 SXM comes with 80 GB of GPU memory.
80 GB might sound like a lot, but the model weights already take up a big chunk of that space. Then you have the KV caches from all the requests currently running on the GPU. With so many requests, the memory disappears pretty quickly.
So serving an LLM isn't just about fitting the model onto the GPU. You also need enough memory left for the requests you're serving at the same time. And as those requests generate more tokens, their KV caches keep growing. This is when KV-cache management becomes important.
The original PagedAttention paper addresses this problem clearly. The paper shows how inefficient KV-cache memory allocation can waste memory and hurt LLM serving throughput.
Memory Fragmentation
Before PagedAttention, most serving systems reserved one contiguous chunk of KV-cache memory for each request. Now, think about a busy server. One user sends a 200-token prompt, another sends a 2,000 token paragraph.
If we keep reserving big continuous chunks of GPU memory for requests like these, we end up wasting more memory than we might expect. That usually shows up in two ways.
Internal fragmentation
Internal fragmentation occurs when we reserve more memory than the request actually uses.
Say we reserve a lot of space for a maximum context of 4,096 tokens, but the request only uses 500. The rest of that space is still tied up. The memory is there, but it is just sitting unused, and you cannot use it.
External fragmentation
Now imagine the server running for a while. Requests keep coming in and finishing, so memory gets freed up in different places. After a while, the free space isn't sitting in one big chunk anymore. It's scattered across smaller gaps. So you might have enough free memory overall, but not enough of it in one continuous block to fit the next request.
If you have studied Operating Systems before, this might sound familiar. OSes have had to deal with limited memory for a long time. Physical memory is finite, but programs don't always use the same amount of memory throughout their lifetime. Some data is needed for a short time, while other data stays around for much longer. Trying to fit everything into one big contiguous chunk can leave a lot of unused space and make memory management harder.
The solution to this is paging. Instead of requiring a program's memory to be stored in one continuous block, the OS breaks it into smaller, fixed-size pages. These pages can be placed anywhere in physical memory, and the page table keeps track of where each one is.
The program doesn't need to care where those pages are physically stored. It still sees its memory as one continuous address space. And this same idea turned out to be useful for PagedAttention too!
Paging the KV Cache
PagedAttention, introduced with vLLM, takes the same idea from OS paging and applies it to the KV cache. Instead of allocating one big continuous chunk of GPU memory for a request's entire KV cache, PagedAttention breaks the cache into smaller blocks. These blocks can be placed anywhere there is enough free GPU memory. A block table keeps track of where each part of the sequence is stored.
So, even though the KV cache may be scattered across GPU memory, the model can still treat it as one continuous sequence. This makes memory allocation much more flexible and avoids wasting large chunks of GPU memory just because a request needs a different amount of space.
The original PagedAttention paper also reports very low KV-cache memory waste and significant throughput improvements compared with earlier serving systems, especially as sequence lengths and workloads increase.
Sharing the KV cache
A nice thing about managing memory in blocks is that sharing becomes easier. Let's say multiple requests start with the same long system prompt. Why should we compute and store the same prefix again and again? With prefix caching, the KV state for that shared prefix can simply be reused across requests.
RAG and CacheBlend
RAG makes this a little more interesting. Imagine the same document getting retrieved for many different requests. The model has to process that document every time, even though it has already seen it before. So naturally, you'd want to cache its KV state.
The problem is that the KV representation of a piece of text can depend on the context around it. So you can't always take a cached chunk and drop it into a different prompt and expect the same result.
That's what CacheBlend tries to handle. It keeps the KV cache for the parts it can reuse, and recomputes only the tokens that are affected by the new context. The paper reports lower time-to-first-token (TTFT) and higher throughput than recomputing the full KV cache.
But PagedAttention doesn't make the KV cache smaller. It just manages the memory better. Once we fix the memory-management side of the problem, the next question becomes: can we reduce the cache itself?
Well yes! And that brings us to MQA and GQA.
MQA and GQA
In Multi-Head Attention, each Query head has a corresponding Key and Value head. So if a model has 32 attention heads, we have 32 sets of K and V in the KV cache.
But Multi-Query Attention (MQA) is different from this. Instead of having a separate K/V head for every Query head, all the Query heads share the same K/V heads. So we still have 32 Query heads, but only one set of K/V to store. That's a pretty big reduction in the KV cache!
However, Grouped-Query Attention (GQA) sits in the middle. The Query heads are split into groups, and the heads in each group share a K/V head. For example, 32 Query heads could share 8 K/V heads, with 4 Query heads using each one.
So MQA uses very few K/V heads, while GQA keeps more of them. You save memory without making all the Query heads share the same K/V. Llama 3 uses GQA in both its 8B and 70B models.
KV-cache quantization
So far, we have looked at ways to reduce the KV cache by changing how many K/V heads we store. But there is another way to cut it down, by storing each value using fewer bits.
If the KV cache is stored in FP16, each value takes 16 bits. If we use a lower-precision format, the cache takes less memory. That is the basic idea behind KV-cache quantization.
For example, moving from FP16 to 8-bit storage cuts the memory needed for the cache roughly in half. That can make a big difference when the cache is already taking up gigabytes.
There is a catch, though. Lower precision introduces approximation error, and using too little precision can affect model quality. So the goal is not to use as few bits as possible, but to find a precision that saves enough memory while keeping the effect on quality small.
In practice, 8-bit KV-cache quantization is often a useful middle ground, while going lower can become more sensitive to the model.
The bottleneck
At this point, there's more to worry about than just the KV cache. We have compute, memory capacity, memory bandwidth, latency, throughput, and GPU utilization, all affecting each other!
A GPU can have plenty of compute and still spend a lot of time moving data around. You can have enough memory and still waste a lot of it through poor allocation. And something that works well for one request can behave very differently when hundreds of requests arrive together.
So it's not just about how fast the GPU is, but also about how well we're using it.
It is easy to look at PagedAttention and think, okay, GPU memory management is solved. But it is not that simple. PagedAttention solves an important part of the problem, but it is not the only approach. For example, vAttention takes a different approach. The KV cache is kept virtually contiguous, even though the actual physical memory holding it can be scattered around the GPU.
The idea is to let the attention kernel see one continuous KV cache while the system handles where the data actually lives. This means the kernels don't have to be redesigned around a paged KV-cache layout. During evaluation, the authors found that vAttention could improve serving throughput over PagedAttention-based implementations in some cases.
The next time you send a long prompt to an LLM and wait for it to output the first token, there's a lot happening under the hood. The model processes the input, builds the K/V representations, stores them in GPU memory, and then keeps reusing them as it generates each new token. For every new token, a new Query is created and used with the K/V tensors stored so far.
At the same time, the serving system has to manage the KV cache for all the requests running on the GPU. As a user, you type a prompt and get your answer a few seconds later.
But as the KV cache grows, it uses more GPU memory. How that memory is managed can affect how many requests the GPU can handle at once.
That's what makes the KV cache interesting. A small optimization inside attention ends up connecting attention, GPU memory, operating systems, and inference systems all at once!