The KV cache and context growth

Generating the 500th token of an answer does not re-read the first 499 from scratch — if it did, long outputs would slow to a crawl. The trick that prevents that is the KV cache, and it is the most important data structure in serving. It turns quadratic re-computation into a lookup — and in doing so becomes the biggest, most volatile consumer of GPU memory you have to manage. Understand it and most serving behaviour (batch limits, context caps, why prefix caching matters) stops being mysterious.

What you will understand by the end

• What the KV cache holds and why it makes decode fast.
• Why its size grows with every token and every concurrent request.
• How to estimate KV-cache memory, and why it — not the weights — usually caps batch size.
• Why prefix caching and paged memory exist.

Why the cache exists

Recall from Transformer and attention intuition that attention compares the current token against every previous token using per-token key (K) and value (V) vectors. Those K and V vectors depend only on the tokens that came before, so they never change once computed. Recomputing them for the whole history at every step would make generating token n cost work proportional to n — the total cost of an answer would grow with the square of its length.

The KV cache is the obvious fix: compute each token's K and V once, store them, and at every later step just read them back.

  WITHOUT a KV cache            WITH a KV cache
  step 1: process [t1]          step 1: process [t1]        → store K,V for t1
  step 2: process [t1 t2]       step 2: process [t2] only   → append K,V for t2
  step 3: process [t1 t2 t3]    step 3: process [t3] only   → append K,V for t3
  ...re-reads whole history     ...each step does O(1) new work, reads cached K,V
  cost per step GROWS           cost per step is ~CONSTANT

Why keys and values, but not queries

A fair question: why cache K and V but never Q? Attention at the current step uses the query of only the newest token, matched against the keys and values of every previous token. A past token's query is never consulted again once its token has been produced, so there is nothing to keep. That asymmetry is the whole design: each decode step computes one fresh query, appends exactly one new key and one new value to the cache, and reads the rest back. The cache grows by precisely one row per generated token — never more.

The cost: it grows two ways at once

Nothing is free — you traded compute for memory. The cache holds a K and a V vector for every token, in every layer, for every request being served. Its size grows along two axes simultaneously:

• Longer context → bigger cache. Every new token (prompt or generated) appends another entry. A request with a 4,000-token context holds 4,000 tokens' worth of K/V.
• More concurrent requests → more caches. Each request in the batch has its own KV cache. Serving 50 users at once means 50 independent caches resident in HBM.

A back-of-the-envelope size:

  KV bytes ≈ 2 (K and V) × layers × kv_heads × head_dim × bytes_per_elem
            × sequence_length × batch_size
            └──────────── per-token, per-request ────────────┘

The first line is a per-token constant fixed by the model; the second line is what you control at serve time. The product is what sits in HBM alongside the weights — and it scales linearly with both how long the conversations are and how many run at once.

The kv_heads term in that first line is not a constant either: it is an architecture knob. Attention variants like GQA and MQA deliberately shrink it — sharing key/value heads across many query heads to make the cache (and decode bandwidth) smaller. That is the subject of the next chapter.

The cache is what caps your batch

Put the two facts together and you get the central serving constraint:

   HBM capacity  =  model weights (fixed)  +  KV cache (grows with batch × context)
                                              └── this is the part that runs out ──┘

Because the weights are a fixed cost paid once, the free HBM after loading the model is a KV-cache budget, and that budget is what really decides how many requests you can run concurrently and how long their contexts can be. This is why batching and KV cache are two sides of one coin: the batch size you can sustain is set by how much KV cache fits.

Two techniques exist precisely to stretch that budget.

Paging: stop reserving worst-case blocks

The naive way to hold a request's cache is one contiguous block sized for its worst-case length. That wastes memory two ways: internal fragmentation — a request that stops early leaves most of its reserved block unused — and external fragmentation — freed blocks are the wrong size for the next request, so gaps go unused. Paged attention (the idea behind vLLM's PagedAttention) borrows the operating system's trick: split the cache into small fixed-size blocks (commonly 16 tokens), allocated on demand as a request generates. A per-request block table — a page table — maps the request's logical token positions to wherever its blocks physically sit, and a shared free-block list hands blocks out and reclaims them when a request finishes. Because blocks need not be contiguous, the wasted headroom nearly disappears and far more requests fit in the same HBM; the attention kernel just computes over the scattered blocks, combining the partial results as it goes.

Prefix caching: reuse a shared prompt

When many requests share the same leading tokens — a big system prompt, a schema, a glossary — their K/V for that shared prefix are identical. Prefix caching computes them once and reuses them across requests, saving both the prefill compute and a duplicate copy of the cache. Engines can do this automatically, detecting shared prefixes as requests arrive (much like a CPU cache); that is distinct from the explicit prompt-caching APIs some hosted providers expose, where you mark the cacheable span yourself. Either way the win is the same: pay for the shared prefix once, not once per request.

Mental model

The KV cache is remembered attention: compute each token's key/value once, keep it, and look it up forever after. It makes decode cheap per step, but it grows with every token and every concurrent request — so the free memory after the weights is really a batch-size budget.

Common mistakes

• Sizing VRAM for weights only. The cache is a first-class memory consumer; ignore it and you OOM the moment you batch or lengthen context.
• Treating context length as free. Doubling context roughly doubles the KV cache per request — it costs memory, and often tail latency, not just "more input."
• Forgetting each request has its own cache. Concurrency multiplies KV memory; a batch of 64 is 64 caches, not one shared one.
• Leaving prefix caching off with a big shared prompt. You pay to recompute the same prefix on every request — often the single biggest throughput leak.

Practical guidance

• Budget HBM as weights + peak KV cache, where peak KV ≈ per-token cost × max context × max concurrent requests you intend to support.
• If you need more concurrency, look at the KV budget first: paged attention, shorter context caps, or quantizing the KV cache buy batch size directly.
• Turn prefix caching on whenever requests share a system prompt/schema — it is usually free throughput.
• Measure the KV pool utilisation under real load; whether you are KV-bound or compute-bound decides which lever (memory vs. GPU) actually helps.

Summary

• The KV cache stores each token's key/value vectors so decode never re-reads the history — turning quadratic re-computation into a lookup and making decode memory-bound.
• It grows with context length × batch size, and can rival the weights in HBM.
• The free memory after loading the model is a batch-size budget; KV cache, not weights, usually caps concurrency and context.
• Paged attention and prefix caching stretch that budget — the latter was worth 3–4× throughput on this project's shared-prompt workload.

Knowledge check

A model loads fine and answers single requests, but OOMs when you raise concurrency to 64. What is filling the memory, and name two ways to serve more requests without a bigger GPU.

The KV cache — each of the 64 requests holds its own, and together they exceed the free HBM left after the weights. Ways to fit more: paged attention (eliminate the per-request worst-case reservation), prefix caching (share the common prompt's cache), a shorter context cap, or quantizing the KV cache to fewer bits — all of which shrink KV memory rather than adding silicon.

Why does a long shared system prompt make prefix caching so valuable?

Because every request's key/value vectors for the shared leading tokens are identical. Without prefix caching each request re-runs prefill over that whole prompt and stores its own copy; with it, the prefix is computed once and reused — saving both the repeated prefill compute and the duplicated cache, which on this project was worth 3–4× throughput.

Related chapters

• Attention variants (MHA/MQA/GQA/MLA) — shrinking kv_heads to make the cache smaller
• Transformer and attention intuition — where the K and V vectors come from
• Prefill and decode — prefill fills the cache; decode reads it
• Batching and concurrency — the KV budget is what caps the batch
• Inside an NVIDIA GPU — the HBM the cache lives in, and why it is the scarce resource