KV Cache: The Memory That Makes Generation Affordable

The KV cache is the reason generating the thousandth token costs about the same as generating the tenth. It is also the reason a server that happily holds two hundred short conversations falls over on twenty long ones. Both facts come out of one formula, which is short enough to do in your head.

Why a cache exists at all

Attention at step t needs a key and a value vector for every token from 1 to t. Those vectors depend only on the token and its position, not on anything that happens later — so once computed, they never change. Without a cache, every decode step would recompute the keys and values for the entire history, making generation quadratic in output length. With one, each step computes K and V for exactly one new token and reads the rest.

The cost of that trade is memory, and memory on an inference server is the scarce resource. Weights are fixed; the KV cache is the part that grows with every user and every token they produce.

It is worth seeing how bad the alternative is. Without a cache, generating n tokens means recomputing the keys and values for a sequence that grows by one each step, so the total work is proportional to 1 + 2 + … + n, which is n²/2. A 1,000-token answer would cost roughly five hundred times a single step instead of a thousand. The cache converts quadratic work into linear work and pays for it in memory that scales linearly. That is the entire trade, and every subsequent refinement — grouped-query attention, paged allocation, quantised caches, prefix sharing — is an attempt to make the memory side of it cheaper.

The formula

Per token, per sequence, the cache holds one key vector and one value vector for each attention layer, sized by the number of key/value heads (not query heads — that distinction is the whole of grouped-query attention) times the head dimension:

bytes_per_token = 2 * layers * kv_heads * head_dim * bytes_per_element
                  ^
                  one K and one V

Everything in it is on the model card. bytes_per_element is 2 for FP16 or BF16, 1 for an FP8 cache, and there is nothing else in the expression — no batch size, no context length. Multiply by the number of tokens for one sequence, and by the number of sequences for the server.

Worked: an 8B model on one 80 GB card

Take the published dimensions of Llama 3 8B: 32 layers, 8 key/value heads, head dimension 128, served in BF16.

bytes_per_token = 2 * 32 * 8 * 128 * 2
                = 131,072 bytes
                = 128 KiB per token

one 8k-token conversation  = 8192 * 128 KiB  = 1.0 GiB
one 128k-token context     = 131072 * 128 KiB = 16 GiB

Now the budget. Weights in BF16 are 8e9 × 2 = 16 GB. On an 80 GB card, allowing say 4 GB for activations, fragmentation and the runtime, roughly 60 GB is left for cache. Assumptions stated; do the division:

cache budget      ~= 60 GiB
tokens it holds   ~= 60 * 1024 * 1024 / 128  =  491,520 tokens

  ... as 8k-token sessions      ->  ~60 concurrent
  ... as 2k-token sessions      ->  ~240 concurrent
  ... as one 128k-token session ->  ~3 concurrent

Three things fall out of that table immediately. Concurrency is a function of context length, not of user count. A single 128k-token session consumes what forty 3k-token sessions would. And the marginal cost of “just paste the whole document in” is not the prefill tokens on your invoice — it is a slice of the server’s concurrency for as long as your session is alive.

There is one more saving available, and it is the bridge to prompt caching. Two requests that begin with the same tokens produce identical K and V entries for that prefix, so a server using paged allocation can point both sequences at the same physical blocks rather than storing two copies. With a 4,000-token shared system prompt and fifty concurrent users, that is the difference between 50 × 500 KiB and a single 500 KiB copy — and once those blocks are shared, the prefill that would have produced them can be skipped too. Prefix sharing and prompt caching are the same mechanism seen from the memory side and the billing side.

What grouped-query attention actually bought

Run the same formula with the older multi-head arrangement, where the number of key/value heads equals the number of query heads. Llama 3 8B has 32 query heads, so:

MHA equivalent = 2 * 32 * 32 * 128 * 2 = 524,288 bytes = 512 KiB/token

  128 KiB/token  (8 KV heads, GQA)
  512 KiB/token  (32 KV heads, MHA)   -> 4x the cache, same model size

Grouped-query attention lets several query heads share one key/value head. It changes the weights barely at all and the cache by the sharing ratio — a 4× reduction here, 8× in the 70B configuration. That is the entire reason it was adopted, and it is why long-context serving became commercially plausible around the same time. Multi-head latent attention, used by more recent models, pushes the same idea further by storing a compressed latent instead of full K and V.

What happens when it runs out

The cache is not optional, so a server out of KV memory has only unpleasant options, and which one it picks is visible to you as behaviour:

• Refuse admission. New requests wait in the queue rather than joining the batch. You see latency, not an error.
• Preempt and recompute. Evict a running sequence’s cache, and when it is rescheduled, prefill it again from scratch. You see a long stall in the middle of a stream.
• Swap to host memory. Move a sequence’s cache over PCIe and back. Cheaper than recomputing for long prompts, and still a stall.
• Fragment. Classic implementations reserved a contiguous block sized for max_tokens, wasting everything not used. Paged allocation — the idea behind vLLM’s PagedAttention, published by Kwon et al. at SOSP 2023 — stores the cache in fixed-size blocks like virtual memory pages, which is what made high concurrency practical.

All four are invisible from the API. What you can do about them is bounded: keep contexts as short as the task allows, set max_tokens honestly rather than to the model maximum, and treat a mid-stream stall as a scheduling event rather than a network fault.