The KV Cache: An LLM's Short-Term Memory, and Its Bill

Why an LLM keeps notes on every token, how big they get (16 GiB for one 128K-token Llama 3.1 8B chat), and why the old way of storing them wasted most of the memory.

Part 1 ended with a rule. A decode step reads all the model's weights from memory, whether it writes one token or a hundred. So a GPU is only productive when it decodes many conversations at once. The catch was in the last line: every conversation in that batch needs its own memory for its notes. Those notes are called the KV cache.

one decode step, four conversations in the batchmodel weightsread from memory once per stepconversation Anotes on A's pastconversation Bnotes on B's pastconversation Cnotes on C's pastconversation Dnotes on D's pastGPU memoryweightsABCDfreeEvery conversation in the batch keeps its own notes in GPU memory, next to the weights.
One decode step reads the weights once and serves every conversation in the batch. Each conversation also keeps its own notes in GPU memory. This part is about those notes.

This part answers four questions about the notes. What are they? Why does the model keep them? How big do they get? And why did the first serving systems waste most of the memory they set aside for them? The last answer is the problem that Part 3 solves.

What the model needs from the past

Start with the loop from Part 1. To write the next token, the model takes everything so far, runs it through its stack of layers and gets one new token. Then it appends that token and runs again.

Here is the question that Part 1 skipped. When the model writes token 500, how does it use tokens 1 to 499? A word like "it" means nothing on its own. To write the next word well, the model must find out what "it" refers to, and that answer sits somewhere earlier in the text.

The part of each layer that looks back at earlier tokens is called attention. To understand the KV cache, you need to understand attention first. Attention is a lookup, and a small example shows all of it.

Attention: a lookup with a question, labels and contents

Think of a library with a card for every book. Each card has a label on the front (what the book is about) and the contents inside. You walk in with a question. You compare your question with every label, pick the cards that match best, and read mostly their contents.

Attention does the same thing with vectors. At each layer, every token makes three vectors from its own vector:

  • a query: the question this token asks ("which earlier word do I refer to?");
  • a key: the label it shows to later tokens ("I am a noun, an animal");
  • a value: the content it hands over when a later token picks it.

Each of the three comes from multiplying the token's vector by a fixed matrix of weights. The model learned these three matrices during training, and they stay the same at inference.

one token at one layervector of "cat"× W_qquery qused now, then thrown away× W_kkey kkept: later tokens compare with it× W_vvalue vkept: later tokens mix it inThree fixed weight matrices turn the same token vector into three different vectors.
One token at one layer. The same vector, multiplied by three different weight matrices, gives a query, a key and a value. Only the key and the value are needed again later.

A lookup with tiny numbers

Take the text "The cat sat" and a new token, "it". To keep the arithmetic small, every key, value and query here has only 2 numbers. Real models use 64 or 128 numbers per head, but the steps are the same.

The three earlier tokens have these keys and values:

TokenKeyValue
The[0, 1][1, 0]
cat[3, 0][0, 4]
sat[1, 1][2, 2]

The new token "it" asks with the query [1, 0]. Attention now takes three steps.

Step 1: compare the query with every key. The comparison is a dot product: multiply the numbers in matching positions and add the results. For "cat", that is 1 × 3 + 0 × 0 = 3. For "The" it is 0, and for "sat" it is 1. A higher score means a better match.

Step 2: turn the scores into weights. First divide each score by the square root of the vector length, here √2. This keeps scores from growing too large in long vectors. Then apply softmax: raise e to the power of each score and divide by the total. The weights come out as 0.088, 0.734 and 0.178, and they add up to 1.

Step 3: mix the values. Multiply each value by its weight and add them up. The answer is [0.44, 3.29]. It is mostly the value of "cat", because the key of "cat" matched the query best.

the new token "it" asks with its query q = [1, 0]step 1: compare q with every keystep 2: turn scores into weightsstep 3: mix the valuesThek = [0, 1]q·k = 00 / √2 = 0.000.088v = [1, 0]× 0.088catk = [3, 0]q·k = 33 / √2 = 2.120.734v = [0, 4]× 0.734satk = [1, 1]q·k = 11 / √2 = 0.710.178v = [2, 2]× 0.178softmax: the weights sum to 1answer = [0.44, 3.29]The answer is mostly the value of "cat", because its key matched the query best.
The whole lookup with tiny numbers. The query of "it" is compared with three keys, the scores become weights that add up to 1, and the answer is a weighted mix of the three values. A PyTorch attention function gives the same answer, [0.44, 3.29].

The three steps fit in one line. Here QQ is the query, KK holds the keys of all earlier tokens, VV holds their values and dd is the length of one key:

attention(Q,K,V)=softmax(QK⊤d)V\text{attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^\top}{\sqrt{d}}\right) V

Read it from the inside out. QK⊤Q K^\top is step 1, one dot product for every key. Dividing by d\sqrt{d} and the softmax are step 2. Multiplying by VV is step 3. Our script checked the hand result against PyTorch's own attention function, and both give [0.44, 3.29].

Now look at what the lookup needed. It needed one query, from the new token only. It needed the key and the value of every earlier token. The next section is about where those keys and values come from on each step.

The waste hiding in the loop

A model like Llama writes from left to right. Each token may look only at the tokens before it, never at the tokens after it. So adding a new token at the end changes nothing about the tokens already there.

That has a strong consequence. The key and value of "cat" at layer 5 depend only on "The cat" and on the fixed weights. When "sat", "on" and "the" arrive later, the key of "cat" stays exactly the same. It was the same on step 3 and it will be the same on step 300.

Now picture a model without notes. On every step it would run the whole text through every layer again. It would compute every key and value again, only to get the same numbers as last time. It is like a writer who rereads the whole book from page one before each new sentence.

The fix is to keep notes. After a token's key and value are computed at a layer, store them. On the next step, compute the key and value of the new token only, add them to the store, and read the old ones back. That store is the KV cache.

no cache: recompute K and V for all tokensKV cache: compute only the new tokensteps 1 to 6 (rows), tokens (columns)steps 1 to 6 (rows), tokens (columns)orange = computed this stepaqua = read from the cache
Without a cache, every step computes keys and values for every token so far (orange). With a cache, every step computes one new row and reads the rest from memory (green).

What the cache saves, measured

How much time do the notes save? We measured the time to produce one more token on Qwen2.5-0.5B, the small model from Part 1, on the GPU of an Apple M5 Pro. Without a cache, the model runs the whole text again. With a cache, it runs only the new token.

0100200300400500128 tokens, no cache: 13.6 ms13.6128 tokens, KV cache: 9.9 ms9.9128 tokens so far512 tokens, no cache: 27.3 ms27.3512 tokens, KV cache: 10.3 ms10.3512 tokens so far2048 tokens, no cache: 94.9 ms94.92048 tokens, KV cache: 10.9 ms10.92,048 tokens so far4096 tokens, no cache: 200.7 ms2014096 tokens, KV cache: 11.0 ms11.04,096 tokens so far8192 tokens, no cache: 449.1 ms4498192 tokens, KV cache: 11.5 ms11.58,192 tokens so farno cacheKV cachetime to produce the next token, milliseconds
Time to produce the next token on Qwen2.5-0.5B (Apple M5 Pro GPU). Without a cache the cost climbs with the length of the text; with a cache it stays almost flat.
Tokens so farNo cacheKV cacheSlower without
12813.6 ms9.9 ms1.4x
51227.3 ms10.3 ms2.7x
2,04894.9 ms10.9 ms8.7x
4,096200.7 ms11.0 ms18x
8,192449.1 ms11.5 ms39x

Without a cache, every new token costs a full prefill of the whole text. Compare the no-cache column with Part 1's prefill table: the numbers match. So a long answer gets slower with every token it writes, and at 8,192 tokens each step is 39 times slower. With a cache, each step costs about the same, whatever the length. Every serious inference engine uses one.

The price is in the word "store". The cache swaps compute for memory, and the next sections show how fast that memory adds up.

What exactly is stored

A real model does attention many times for each token, not once. It has a stack of layers, and each layer has its own attention. Inside each layer, attention is split into several heads: smaller lookups that run side by side, each with its own keys and values.

So for every token, the cache keeps one key and one value per KV head, in every layer. Each key and each value is a vector of head_dim numbers, and each number takes a fixed number of bytes.

what the cache keeps for ONE token of Llama 3.1 8B"cat"layer 1layer 2layer 3⋮layer 32inside one layer: 8 KV headsKVKVKVKVKVKVKVKVeach K and each V is a list of 128 numbers (head_dim)each number takes 2 bytes (bfloat16)2 (K and V) × 32 layers × 8 heads × 128 numbers × 2 bytes= 131,072 bytes = 128 KiB per tokenOne token leaves 512 small vectors behind: a key and a value for every head of every layer.
What the cache keeps for one token of Llama 3.1 8B. In each of the 32 layers, each of the 8 KV heads stores a key and a value of 128 numbers, at 2 bytes per number.

Is that the real layout? We can look inside a running model. We ran a 100-token prompt through Qwen2.5-0.5B and opened its cache. Layer 0 holds a key tensor of shape (1, 2, 100, 64): 1 sequence, 2 KV heads, 100 tokens and 64 numbers per key. There are 24 layers, each with keys and values.

plain text
== 2. The KV cache of a real model: Qwen2.5-0.5B, bfloat16
  config: layers 24, query heads 14, KV heads 2, head_dim 64, device mps
  100 tokens: 24 layers, key tensor of layer 0 (1, 2, 100, 64) torch.bfloat16, cache 1,228,800 bytes
  200 tokens: 24 layers, key tensor of layer 0 (1, 2, 200, 64) torch.bfloat16, cache 2,457,600 bytes
  measured: 12,288 bytes per token; formula 2 x 24 x 2 x 64 x 2 = 12,288 bytes

The cache for 200 tokens is exactly twice the cache for 100 tokens. Every token adds the same 12,288 bytes. That gives a formula you can apply to any model.

The size formula

Every number in the formula comes from a model's config.json file. Here is the file for Llama 3.1 8B, the main example of this part:

Llama-3.1-8B config.json (excerpt){ "hidden_size": 4096, "num_attention_heads": 32, "num_hidden_layers": 32, "num_key_value_heads": 8, "head_dim": 128, "torch_dtype": "bfloat16", "max_position_embeddings": 131072}2K and V× 32layers× 8KV heads× 128head_dim× 2 bytesbfloat16= 131,072 bytes= 128 KiB for every token
The four fields in a model config that decide the size of its KV cache: the number of layers, the number of key/value heads, the head dimension and the data type.
KV bytes per token=2×layers×KV heads×head dim×bytes per number\text{KV bytes per token} = 2 \times \text{layers} \times \text{KV heads} \times \text{head dim} \times \text{bytes per number}

Read it from left to right. The 2 counts the key and the value. Layers and KV heads count how many keys and values each token leaves behind. Head dim is the length of each one. Bytes per number is 2 for the 16-bit formats that models usually run in.

Check it on Qwen2.5-0.5B first: 2×24×2×64×2=12,2882 \times 24 \times 2 \times 64 \times 2 = 12{,}288 bytes, which is exactly what we measured. Now Llama 3.1 8B: 2×32×8×128×2=131,0722 \times 32 \times 8 \times 128 \times 2 = 131{,}072 bytes. That is 128 KiB for every token of every conversation the GPU serves.

How big it gets

The cache grows by one entry per token, so its size is the formula times the number of tokens. Llama 3.1 8B accepts up to 131,072 tokens (128K). One conversation at that length needs 131,072×128131{,}072 \times 128 KiB, which is 16 GiB.

Qwen2.5-0.5B: 12.0 KiBQwen2.5-0.5B12.0 KiB1.5 GiB for a 128K-token contextLlama-2-7B (MHA): 512 KiBLlama-2-7B (MHA)512 KiB64.0 GiB for a 128K-token contextLlama-3.1-8B (GQA): 128 KiBLlama-3.1-8B (GQA)128 KiB16.0 GiB for a 128K-token contextLlama-3.1-70B (GQA): 320 KiBLlama-3.1-70B (GQA)320 KiB40.0 GiB for a 128K-token context
KV cache per token, and for one 128K-token conversation, for four models, from each model's config.
ModelLayersKV headsHead dimPer tokenOne 128K-token conversation
Qwen2.5-0.5B2426412 KiB1.5 GiB
Llama 3.1 8B328128128 KiB16 GiB
Llama 3.1 70B808128320 KiB40 GiB
Llama 2 7B3232128512 KiB64 GiB

Look at the Llama 3.1 8B row again. The weights of this model take about 16 GB. One conversation at full length needs a cache of the same size. One long chat costs as much memory as the whole model.

Now put that on a real GPU. An NVIDIA H100 has 80 GB of memory. The weights of Llama 3.1 8B take 16.1 GB (8.03 billion numbers at 2 bytes each). One 128K-token cache is 17.2 GB. After the weights, the card has room for only three such conversations.

one 80 GB H100 serving Llama 3.1 8B, conversations at the full 128K tokensweights 16.1 GBconv. 1: 17.2 GBconv. 2: 17.2 GBconv. 3: 17.2 GB12.3 GB0 GB80 GBA fourth full conversation needs 17.2 GB and does not fit in the 12.3 GB left over.(The model also needs some working memory, so the real room is a little smaller.)
An 80 GB H100 serving Llama 3.1 8B. After the 16.1 GB of weights, three full-length conversations of 17.2 GB each fill most of the card, and a fourth does not fit.

Part 1 showed that throughput grows with the batch. Here the batch is three. Most conversations are much shorter than 128K tokens, so a real server fits more. But the point stands: the cache, not compute, sets how many conversations a GPU can hold.

Shrinking the notes

The table above holds a surprise. Llama 2 7B and Llama 3.1 8B are about the same size, but the older model needs four times more cache per token. The difference is one number in the config: 32 KV heads against 8.

Fewer key and value heads: MHA, GQA and MQA

In the original transformer, every query head has its own key head and value head. That is multi-head attention (MHA). Llama 2 7B works this way: 32 query heads and 32 KV heads.

The idea behind the newer designs is that query heads can share keys and values. Each query head still asks its own question. But a group of query heads compares against the same keys and mixes the same values. Only the shared keys and values go into the cache.

multi-head (MHA)8 KV heads to cachegrouped-query (GQA)KVKV2 KV heads to cachemulti-query (MQA)KV1 KV head to cacheorange = query heads (not cached). aqua = key/value heads (cached for every token).
In multi-head attention every query head has its own key and value head. Grouped-query attention lets several query heads share one; multi-query attention shares a single one across all.
  • Multi-query attention (MQA) shares one key head and one value head across all query heads.
  • Grouped-query attention (GQA) sits between the two: each group of query heads shares one KV head. Llama 3.1 8B has 32 query heads in 8 groups of 4.

What would Llama 3.1 8B cost under each design? Keep 32 layers, a head dim of 128 and 2 bytes, and change only the number of KV heads:

DesignKV headsPer token128K-token conversation
MHA32512 KiB64 GiB
GQA (the real model)8128 KiB16 GiB
MQA116 KiB2 GiB

Compressed keys and values: MLA

A third design stores something smaller than the keys and values. Multi-head latent attention (MLA), from DeepSeek, squeezes each token's keys and values into one short vector, called a latent vector. At attention time, the model expands it back. The cache holds only the short vector.

Fewer bytes per number: a quantised cache

The other lever is precision. The cache normally uses 2 bytes per number. An 8-bit format, such as FP8, stores each number in 1 byte. The numbers keep fewer digits, and the cache takes half the memory.

one key of 8 numbers, stored two waysbfloat160.81-1.20.052.3-0.41.10.66-2.016 bytesFP88 bytes: half the memory, slightly rounder numbersEach number keeps fewer digits. The cache halves; quality usually changes very little, but measure it.
The same key stored at 2 bytes per number and at 1 byte per number. The 8-bit version takes half the memory, and each number is a little less exact.

For Llama 3.1 8B, an FP8 cache needs 64 KiB per token, so 8 GiB for a 128K-token conversation instead of 16 GiB. The vLLM engine offers this with the flag --kv-cache-dtype fp8. The cost is a small risk to accuracy, so measure it on your own tasks before you use it.

All of these levers make each token cheaper. None of them changes the shape of the problem. The cache still grows by one entry per token, for every conversation, as long as it runs.

How many conversations fit on a real GPU

Now we can answer the question an inference engineer asks first about any deployment: how many conversations can this GPU hold at once? The size formula is all you need. Take the GPU's memory, take away the weights and some working memory, and divide what is left by the cache of one conversation.

Think of a car park. The building has a fixed number of spaces. Some are taken by staff cars all day, which are the weights. A few are kept free for deliveries, which is the working memory. The rest is for visitors. How many visitors fit depends on the size of each car, and a long conversation is a long car.

A small example first

Take the H100 from above, with Llama 3.1 8B and conversations of 4,096 tokens.

  1. Memory for the cache. Keep 10% of the 80 GB as working memory, which leaves 72 GB. The weights take 16.1 GB, so 55.9 GB is left for the cache.
  2. Cache per conversation. At 128 KiB per token, 4,096 tokens need 512 MiB, or 0.54 GB.
  3. Divide. 55.9 GB ÷ 0.54 GB = 104 conversations.

With an FP8 cache, each token needs 64 KiB, so the same memory holds twice as many: 208. Conversations of 32,768 tokens are 8 times larger, so only 13 fit, or 26 with FP8.

Three GPUs, two models

A newer GPU has more memory, and the weights stay the same size. So most of the extra memory goes to the cache. These numbers come from the script p2_gpu_capacity.py, with the same 10% kept for working memory.

Model and GPUsMemory for the cache4,096 tokens, BF16 cache4,096 tokens, FP8 cache32,768 tokens, BF1632,768 tokens, FP8
8B on 1 H100 (80 GB)55.9 GB1042081326
8B on 1 H200 (141 GB)110.8 GB2064122551
8B on 1 B200 (180 GB)145.9 GB2715433367
70B on 4 H100146.9 GB1092181327
70B on 2 H200112.7 GB831671020
70B on 2 B200182.9 GB1362721734
Llama 3.1 8B (BF16 weights) on one GPU, conversations of 4,096 tokensH100 80 GBweightsKV cache 56 GB104 conversations with a BF16 cache, 208 with FP8H200 141 GBweightsKV cache 111 GB206 conversations with a BF16 cache, 412 with FP8B200 180 GBweightsKV cache 146 GB271 conversations with a BF16 cache, 543 with FP8Llama 3.1 70B (141.1 GB of weights) needs several GPUs; bars show the total over all of them4 x H100 80 GBweightsKV 147 GB109 conversations with a BF16 cache, 218 with FP82 x H200 141 GBweightsKV 113 GB83 conversations with a BF16 cache, 167 with FP82 x B200 180 GBweightsKV 183 GB136 conversations with a BF16 cache, 272 with FP8weightsKV cache10% kept for working memory
GPU memory after the weights, and how many 4,096-token conversations fit in it. For Llama 3.1 8B a bigger GPU gives almost all of its extra memory to the cache. Llama 3.1 70B needs several GPUs before any memory is left for the cache.

Why 70B needs several GPUs

Llama 3.1 70B has 70.6 billion weights, which is 141.1 GB in BF16. With 10% kept for working memory, an H100 offers 72 GB and an H200 offers 127 GB. Neither can hold the weights. A B200 offers 162 GB, so the weights fit, but only 20.9 GB is left for the cache: 15 conversations of 4,096 tokens.

So the model is split across several GPUs, and each GPU holds a share of every layer. On H100s, two GPUs would hold the weights with only 2.9 GB to spare, which is about 2 conversations. Four H100s leave 146.9 GB for the cache. The split must divide the model's 8 KV heads evenly, so the usual counts are 1, 2, 4 or 8 GPUs. The weights and the cache are then shared out in the same way. Part 3 shows how the cache works on split GPUs, and Part 7 covers the split itself.

Note one more effect in the table. Per token, the 70B model's cache is 320 KiB, 2.5 times the 8B model's. So four H100s with 146.9 GB of cache hold only about as many 70B conversations as one H100 holds for the 8B model.

What this number means for the batch

This number caps the batch from Part 1. A decode step can only include conversations whose notes are in GPU memory. On one H100 with 4,096-token conversations, the batch can never pass 104. But Part 1 showed that the ridge of an H100 is near a batch of 295. So memory, not compute, stops the batch first, as Part 1 said.

The table is also the best case. It assumes every byte of cache memory holds real tokens. The next sections show that the first serving systems got nowhere near that.

The cache is read on every step

Size is the first cost of the cache. The second cost takes us back to Part 1.

Part 1 showed that a decode step is slow because it must read all the weights from GPU memory. Memory delivers only so many bytes per second. That rate is the memory bandwidth. Now look again at the attention lookup. To write one token, the new query is compared with the key of every earlier token, and every value is mixed in. So every decode step must also read the whole cache of every sequence in the batch.

On an H100, with a bandwidth of 3.35 TB per second, reading the 16.1 GB of Llama 3.1 8B weights takes at least 4.8 ms. Reading the 17.2 GB cache of one 128K-token conversation takes at least 5.1 ms more. For a long conversation, the cache costs as much reading time as the whole model, on every step.

the least time one decode step can take on an H100 (3.35 TB/s), Llama 3.1 8Bshort chat (cache tiny)weights 4.8 msone 128K-token chatweights 4.8 msits cache 5.1 msReading a long cache costs as much time as reading the whole model again, on every step.
The least time one decode step can take on an H100, from bandwidth alone. A short chat reads the weights. A 128K-token chat also reads its cache, which roughly doubles the time.

Our small model shows the same effect in a real run. Here is the decode step time as the context grows, for 1 sequence and for 16 sequences at once:

01020304002,0484,0966,1448,192batch 1, 128 tokens of context: 10.2 ms per stepbatch 1, 1,024 tokens of context: 11.5 ms per stepbatch 1, 4,096 tokens of context: 10.9 ms per stepbatch 1, 8,192 tokens of context: 11.5 ms per stepbatch 1: 11.5 msbatch 16, 128 tokens of context: 11.3 ms per stepbatch 16, 1,024 tokens of context: 15.4 ms per stepbatch 16, 4,096 tokens of context: 23.4 ms per stepbatch 16, 8,192 tokens of context: 35.9 ms per stepbatch 16: 35.9 mstokens already in the context (each sequence)ms per decode step
Time per decode step as the context grows, on Qwen2.5-0.5B (Apple M5 Pro GPU). One sequence barely notices; sixteen long sequences more than triple the step time.
Context per sequence1 sequence16 sequences
128 tokens10.2 ms11.3 ms
1,02411.5 ms15.4 ms
4,09610.9 ms23.4 ms
8,19211.5 ms35.9 ms

For one sequence the line is flat. This model's cache is small, 12 KiB per token, so even 8,192 tokens is only 96 MiB. That is tiny next to the 0.99 GB of weights. For 16 sequences at 8,192 tokens each, the cache is 1.5 GiB, bigger than the weights. Every step must read all of it, and the step time more than triples.

So decode is limited by memory reads twice over. Each step reads the weights once, and it reads the cache of every sequence once. Long contexts and big batches make the second read the larger one. This is also why the shrinking methods above make decode faster, not only cheaper: fewer bytes in the cache means fewer bytes to read.

Nobody knows how long the answer will be

So far the cache sounds like a sizing problem: work out the bytes and buy enough memory. The real difficulty is that a request's cache grows while the request runs, and nobody knows in advance how far it will grow.

When a request arrives, the server knows the length of its prompt. It does not know the length of the answer. The model decides that on its own, token by token, when it writes its end token. The answer could be 3 tokens or 3,000.

How much does the length vary? The vLLM series on this site asked a small model, OPT-125M, the question from Part 1 twenty times. It used random sampling and a limit of 200 tokens:

20 answers to "What is the capital of France?" (OPT-125M, random sampling, limit 200 tokens)23345615192327282935487388151200200200hit the limitanswer length in tokens (one bar per answer, sorted from short to long)
Twenty answers to the same question from OPT-125M with random sampling. The lengths run from 2 to 200 tokens, and three answers hit the 200-token limit. Nothing in the prompt tells the server which length it will get.

The same question gave answers from 2 to 200 tokens. Across 2,000 real answers in the Alpaca dataset, the median answer has 43 tokens. But one answer in ten has 127 tokens or more, and the longest has 499. (The vLLM Part 2 page has the script and its output.)

Every server sets an upper limit. The model has a maximum length, such as 2,048 tokens for OPT or 131,072 for Llama 3.1 8B. A request can also set its own limit on new tokens, often called max_tokens. These limits say how big the cache could get. They say nothing about how big it will get.

How older systems stored the cache: one slab per request

To see why the size matters so much, we need one fact about how GPU programs keep data in memory.

Deep learning libraries such as PyTorch expect each tensor to be contiguous. That makes reading fast and simple. To find token 5 of a cache that starts at address 1,000, the code computes 1,000 + 5 × (bytes per token) and jumps there. No lookup table is needed.

The catch comes when the cache grows. Picture a group of friends at a theatre who want seats side by side. If a stranger already sits in the next seat, a late friend cannot join the row. In memory, if another request's data sits right after request A's cache, A has no room to add its next token.

a contiguous cache: token i sits at start + i × (bytes per token)0123456request A, start address 1000token 5 is at 1000 + 5 × 128 KiB: one multiply, one add, no lookupthe catch: A cannot grow if someone sits right behind itAAAAAAABBBBBBA's next token must go in slot 7, but B already owns it.So a contiguous system books all the room A might ever need on day one.
Top: in a contiguous cache, the address of any token is one multiply and one add. Bottom: request A cannot grow, because request B owns the slot right behind it.

The systems before vLLM, such as FasterTransformer and Orca, chose the safe answer. When a request arrives, they book one contiguous slab of memory big enough for the longest output the request could ever produce. Then the cache can grow into its own slab, and it never runs into a neighbour.

That last line is the whole problem. A slab sized for the maximum is safe, but most of it sits empty. The vLLM paper splits that empty space into three kinds of waste. Each has a different cause, so we take them one at a time, each on a small memory of slots.

In the pictures below, GPU memory is a row of slots. One slot holds the keys and values of one token, for all layers. For Llama 3.1 8B, one slot would be 128 KiB.

Waste 1: reserved slots

Picture a friend who saves a row of seats at a cinema for friends who will arrive during the trailers. The seats will be used. But until each friend arrives, the seat is empty, and nobody else may sit in it.

Request A shows the same thing. Its slab has 8 slots. Its prompt has 3 tokens, and over its life it will write 5 more, so in the end all 8 slots will hold a token.

request A books 8 slots; its prompt has 3 tokens; it will write 5after the prompt3 hold tokens, 5 waitafter 2 new tokens5 hold tokens, 3 waitfinishedall 8 hold tokenspromptwrittenreservedThe reserved slots are empty for now. They will be used, but until then no other request can use them.
Reserved slots. Request A books 8 slots. After its prompt, 5 slots wait for future tokens. After 2 new tokens, 3 still wait. Only at the very end are all 8 in use.

Follow it step by step. After the prompt, 3 slots hold tokens and 5 are reserved: booked for tokens that do not exist yet. After 2 new tokens, 5 slots hold tokens and 3 are still reserved. Only when the answer ends are all 8 slots full.

Now scale it up. Suppose a request will write a 500-token answer, and its slab already covers that length. On its first decode step, 499 of its answer slots are reserved and empty. One slot fills per step. So over the life of the answer, about half of its answer slots are empty at any moment.

The cost is not lost data. The cost is timing. The memory sits idle exactly while other requests in the queue could have used it.

Waste 2: internal fragmentation

Now picture a booking at a restaurant: a table for eight. Only four guests come. The other four chairs stay empty all evening, and the restaurant cannot give them to anyone else, because they belong to your table.

Request B shows the same thing. Its slab has 8 slots, because 8 is its maximum length. Its prompt has 2 tokens. Its answer ends after 2 tokens, when the model writes its end token.

request B books 8 slots; its prompt has 2 tokens; its answer stops after 2after the promptnobody knows yetanswer done4 slots never usedpromptwrittenreservednever usedThe red slots sat empty for the whole life of B. That memory did nothing at all.
Internal fragmentation. Request B books 8 slots, but its answer ends after 2 tokens. The last 4 slots of its booking are never used, for the whole life of the request.

Request B used 4 of its 8 slots. The other 4 were empty from start to finish. This is internal fragmentation: memory inside a booking that the owner never uses. "Internal" means the waste sits inside a slab that someone owns.

Note the difference from reserved slots. A reserved slot will be used later. An internally fragmented slot will never be used. But at the moment of booking, the server cannot tell the two apart. Both are just empty slots in a slab, and only the end of the answer shows which was which.

At real sizes this waste is large. Take a request with a 100-token prompt, a slab for OPT's maximum of 2,048 tokens, and an answer of 43 tokens, the Alpaca median. It fills 143 of its 2,048 slots, about 7%. The other 1,905 slots are internal fragmentation.

Waste 3: external fragmentation

The third waste sits between slabs, not inside them. Picture a street with no marked parking bays. Cars of different lengths park along it, and some of them leave. Now the free spaces add up to enough room for a bus, but no single gap is long enough, so the bus cannot park.

Here is the same thing in a memory of 24 slots. Four requests have booked slabs of different sizes: A has 8, B has 4, C has 6 and D has 6. Then B and D finish and give their slabs back.

a GPU memory of 24 slots, booked by four requests of different sizesall four runningAAAAAAAABBBBCCCCCCDDDDDDB and D finishAAAAAAAACCCCCCgap of 4gap of 6E needs 7EEEEEEErefused: 10 slots are free, but no single gap holds 7Free memory exists, yet it is cut into pieces that are each too small for the next request.
External fragmentation. After B and D finish, 10 slots are free, in a gap of 4 and a gap of 6. Request E needs 7 slots in one piece, so it is refused, although enough memory is free in total.

Now 10 slots are free. Request E arrives and needs a slab of 7. Ten is more than seven, but the free slots sit in two gaps, of 4 and 6. Neither gap holds 7 in one piece, so E must wait. This is external fragmentation: free memory cut into gaps that are each too small to use.

Slabs of different sizes cause these gaps. They come in different sizes because each request has its own prompt length and its own limit. Many memory allocators also round each booking up, for example to a power of two, which makes the sizes even more uneven. The vLLM paper names one such allocator, the buddy allocator.

Why not slide the slabs together to close the gaps? That is called compaction, and it means copying the cache of every request that moves. A cache can be many gigabytes, and no request can write a token while its cache is in motion. The paper calls compaction "impractical" for a fast serving system, and it does nothing for the first two wastes anyway.

All three wastes at once

In a real server, all three wastes happen at the same time. Here is one moment in a 24-slot memory, with two requests and the gaps around them:

one moment in a 24-slot memory: request A, a gap, request B, free slotsAAAAAAAABBBBBBBBA books 8B books 8gap 3free 5promptwrittenreservednever usedfreeholding tokens: 8 slots; reserved for later tokens: 3; never used (internal fragmentation): 5free: 8, but in gaps of 3 and 5, and the next request needs 6 in one piece (external fragmentation)Only 8 of 24 slots (33%) hold real keys and values.
All three wastes at one moment. Of 24 slots, 8 hold tokens, 3 are reserved for later tokens, 5 will never be used, and 8 are free but cut into gaps of 3 and 5, too small for the next request of 6.

Count the slots. Request A holds 5 tokens, has 2 reserved slots and 1 slot it will never use. Request B holds 3 tokens, has 1 reserved slot and 4 it will never use. Between and after them, 8 slots are free, in gaps of 3 and 5, and the next request needs 6. So only 8 of the 24 slots, 33%, hold real keys and values.

The vLLM paper draws the same picture with real words and real slab sizes:

How much memory was really wasted

The authors measured the three wastes in real serving runs. Orca, the leading system they compared with, is not public, so they built their own version of it in three variants. The variants differ only in how much space each request books for its answer:

  • Orca (Max) books the model's maximum length, 2,048 tokens, for every request.
  • Orca (Pow2) books at most twice the real answer length, rounded up to a power of two. An answer of 25 tokens gets 32 slots.
  • Orca (Oracle) books exactly the real answer length. No real system can do this, because it needs to know the future. It shows the best that slab booking could ever do.

What the waste costs: a smaller batch

Why does wasted memory matter so much? Go back to the rule from Part 1. Throughput grows with the number of sequences in each decode step. Each sequence needs its cache in memory. So memory that holds nothing is memory that could have held another sequence.

The question for Part 3

Put the three wastes side by side, and each one points to what a better design must do:

  1. Reserved slots come from booking memory before the tokens exist. A better design gives memory to a request only when a new token actually needs it.
  2. Internal fragmentation comes from booking for the maximum length. A better design never books more than a small amount beyond what the request has already written.
  3. External fragmentation comes from slabs of different sizes that must each be one unbroken piece. A better design lets a request use free memory wherever it is, in pieces that all fit.

But the old design had a reason for its slabs. Attention reads keys and values fast because they sit in one contiguous run. If a request's cache is spread across memory, how does attention find its tokens? And how can memory grow in small pieces without a slab?

Operating systems faced the same problem with programs in the 1960s, and they solved it with an idea called paging. Part 3 shows how vLLM applied that idea to the KV cache, and what happens to each of the three wastes.

The scripts behind the numbers

The cache and no-cache timings and the decode step times come from the measurement below (Qwen2.5-0.5B, bfloat16, Apple M5 Pro GPU, median of 5 runs):

python
import statistics, time
import torch
from transformers import AutoModelForCausalLM, DynamicCache

DEV, sync = "mps", torch.mps.synchronize          # "cuda", torch.cuda.synchronize on NVIDIA
model = AutoModelForCausalLM.from_pretrained("Qwen/Qwen2.5-0.5B", dtype=torch.bfloat16).to(DEV).eval()

def median_ms(fn, reps=5):
    fn(); sync()
    ts = []
    for _ in range(reps):
        sync(); t = time.perf_counter(); fn(); sync(); ts.append(time.perf_counter() - t)
    return statistics.median(ts) * 1000

with torch.inference_mode():
    for n in (128, 512, 2048, 4096, 8192):
        x = torch.randint(0, model.config.vocab_size, (1, n), device=DEV)
        # no cache: producing the next token means running the whole sequence again
        no_cache = median_ms(lambda: model(input_ids=x, use_cache=False, logits_to_keep=1))
        # cache: run the prompt once, then each new token is a single-token step
        cache = DynamicCache()
        out = model(input_ids=x, past_key_values=cache, logits_to_keep=1)
        tok = out.logits[:, -1:].argmax(-1)
        def step():
            global tok
            o = model(input_ids=tok, past_key_values=cache, logits_to_keep=1)
            tok = o.logits[:, -1:].argmax(-1)
        print(f"{n:5d} tokens: no cache {no_cache:6.1f} ms, cache {median_ms(step):5.2f} ms")

The other new numbers come from p2_kv_numbers.py: the attention example, the measured cache, the sizes, the H100 times and the slot counts. Its full output:

plain text
== 1. Attention as a lookup: a query, three keys, three values
  The  key [0.0, 1.0]  q.k = 0  /sqrt(2) = 0.00  weight = 0.088
  cat  key [3.0, 0.0]  q.k = 3  /sqrt(2) = 2.12  weight = 0.734
  sat  key [1.0, 1.0]  q.k = 1  /sqrt(2) = 0.71  weight = 0.178
  answer = 0.088*[1.0, 0.0] + 0.734*[0.0, 4.0] + 0.178*[2.0, 2.0] = [0.44, 3.29]
  PyTorch scaled_dot_product_attention gives [0.44, 3.29]

== 2. The KV cache of a real model: Qwen2.5-0.5B, bfloat16
  config: layers 24, query heads 14, KV heads 2, head_dim 64, device mps
  100 tokens: 24 layers, key tensor of layer 0 (1, 2, 100, 64) torch.bfloat16, cache 1,228,800 bytes
  200 tokens: 24 layers, key tensor of layer 0 (1, 2, 200, 64) torch.bfloat16, cache 2,457,600 bytes
  measured: 12,288 bytes per token; formula 2 x 24 x 2 x 64 x 2 = 12,288 bytes

== 3. KV bytes per token = 2 x layers x KV heads x head_dim x bytes
  Qwen2.5-0.5B    24 layers   2 KV heads   64 dims:     12 KiB/token,   1.5 GiB for 131,072 tokens
  Llama 3.1 8B    32 layers   8 KV heads  128 dims:    128 KiB/token,  16.0 GiB for 131,072 tokens
  Llama 3.1 70B   80 layers   8 KV heads  128 dims:    320 KiB/token,  40.0 GiB for 131,072 tokens
  Llama 2 7B      32 layers  32 KV heads  128 dims:    512 KiB/token,  64.0 GiB for 131,072 tokens
  Llama 3.1 8B with other attention layouts (32 layers, head_dim 128, 2 bytes):
    MHA, 32 KV heads   512 KiB/token,  64.0 GiB for 128K tokens
    GQA, 8 KV heads    128 KiB/token,  16.0 GiB for 128K tokens
    MQA, 1 KV head      16 KiB/token,   2.0 GiB for 128K tokens
    GQA + 8-bit cache    64 KiB/token,   8.0 GiB for 128K tokens
  Qwen2.5-0.5B, 16 sequences x 8,192 tokens: 1.50 GiB of cache

== 4. One decode step of Llama 3.1 8B on an H100 must read (3.35 TB/s)
  weights 16.1 GB -> at least 4.8 ms
  one 128K-token cache 17.2 GB (16 GiB) -> at least 5.1 ms more
  on an 80 GB H100, after the weights: room for 3 such conversations at full length (63.9 GB / 17.2 GB)

== 5. Toy GPU memory: a row of 24 slots, one slot = the K and V of one token (all layers)
  reserved: A books 8, prompt 3, wrote 2 -> holds 5, 3 reserved for tokens still to come
  internal: B books 8, uses 4, 4 never used
  external: AAAAAAAABBBBCCCCCCDDDDDD -> B, D finish -> AAAAAAAA....CCCCCC......; free 10 in gaps [4, 6]; E needs 7 in one piece: refused
  all three: PPPWWRRI___PPWRIIII_____ (24 slots): tokens 8, reserved 3, never used 5, free 8 in gaps of 3 and 5 (next request needs 6: refused); holding tokens 33%

The GPU capacity table comes from p2_gpu_capacity.py, which only does arithmetic on the configs and the vendor specs. Its full output:

plain text
Llama 3.1 8B: 8,030,261,248 weights -> 16.1 GB in BF16; KV per token BF16 128 KiB, FP8 64 KiB
Llama 3.1 70B: 70,553,706,496 weights -> 141.1 GB in BF16; KV per token BF16 320 KiB, FP8 160 KiB
assumption: 10% of GPU memory kept for working memory

Llama 3.1 8B   on 1 x H100 80GB : weights  16.1 GB per GPU, KV memory   55.9 GB in total =   426,784 tokens BF16 /   853,568 FP8 | conversations that fit: 4,096 tok BF16  104, FP8  208; 32,768 tok BF16  13, FP8  26
Llama 3.1 8B   on 1 x H200 141GB: weights  16.1 GB per GPU, KV memory  110.8 GB in total =   845,638 tokens BF16 / 1,691,276 FP8 | conversations that fit: 4,096 tok BF16  206, FP8  412; 32,768 tok BF16  25, FP8  51
Llama 3.1 8B   on 1 x B200 180GB: weights  16.1 GB per GPU, KV memory  145.9 GB in total = 1,113,429 tokens BF16 / 2,226,859 FP8 | conversations that fit: 4,096 tok BF16  271, FP8  543; 32,768 tok BF16  33, FP8  67

Llama 3.1 70B  on 2 x H100 80GB : weights  70.6 GB per GPU, KV memory    2.9 GB in total =     8,827 tokens BF16 /    17,654 FP8 | conversations that fit: 4,096 tok BF16    2, FP8    4; 32,768 tok BF16   0, FP8   0
Llama 3.1 70B  on 4 x H100 80GB : weights  35.3 GB per GPU, KV memory  146.9 GB in total =   448,280 tokens BF16 /   896,561 FP8 | conversations that fit: 4,096 tok BF16  109, FP8  218; 32,768 tok BF16  13, FP8  27
Llama 3.1 70B  on 2 x H200 141GB: weights  70.6 GB per GPU, KV memory  112.7 GB in total =   343,910 tokens BF16 /   687,820 FP8 | conversations that fit: 4,096 tok BF16   83, FP8  167; 32,768 tok BF16  10, FP8  20
Llama 3.1 70B  on 4 x H200 141GB: weights  35.3 GB per GPU, KV memory  366.5 GB in total = 1,118,446 tokens BF16 / 2,236,893 FP8 | conversations that fit: 4,096 tok BF16  273, FP8  546; 32,768 tok BF16  34, FP8  68
Llama 3.1 70B  on 1 x B200 180GB: weights 141.1 GB per GPU, KV memory   20.9 GB in total =    63,759 tokens BF16 /   127,518 FP8 | conversations that fit: 4,096 tok BF16   15, FP8   31; 32,768 tok BF16   1, FP8   3
Llama 3.1 70B  on 2 x B200 180GB: weights  70.6 GB per GPU, KV memory  182.9 GB in total =   558,143 tokens BF16 / 1,116,287 FP8 | conversations that fit: 4,096 tok BF16  136, FP8  272; 32,768 tok BF16  17, FP8  34

70B on one H100 80GB: usable 72 GB vs weights 141.1 GB -> does not fit
70B on one H200 141GB: usable 127 GB vs weights 141.1 GB -> does not fit
70B on one B200 180GB: usable 162 GB vs weights 141.1 GB -> fits, 20.9 GB left for KV

References

  1. W. Kwon et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023. (Figures 1, 2, 3 and 13; 800 KB per token for OPT-13B; 20.4% to 38.2% of KV memory used in existing systems.)
  2. A. Vaswani et al. Attention Is All You Need. NeurIPS 2017.
  3. N. Shazeer. Fast Transformer Decoding: One Write-Head is All You Need. 2019.
  4. J. Ainslie et al. GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints. EMNLP 2023.
  5. DeepSeek-AI. DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model. 2024.
  6. G.-I. Yu et al. Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI 2022.
  7. NVIDIA, H100 Tensor Core GPU (3.35 TB/s memory bandwidth, 80 GB), H200 (141 GB) and the Blackwell datasheet (HGX B200: 180 GB per GPU).
  8. vLLM documentation: Quantized KV cache.
  9. Model configs: Llama 3.1 8B, Llama 3.1 70B, Qwen2.5-0.5B.

Next: Part 3: How vLLM Serves Thousands, where paging removes the three wastes.