The KV cache and prefix caching

Attention at every layer turns each position into three vectors: a query, a key and a value. The query is what that position is currently asking for; the key and value are what it offers to positions that come after it. Because attention is causal — nothing later can influence anything earlier — position 1,847's contribution does not change when token 2,001 arrives. The work of computing what it offers needs to happen exactly once.

This chapter is about the state that follows from that observation: what prefill stores, how large it is, and what it costs. The size governs how many requests fit on a GPU and reappears in every capacity question later in this topic. The reuse governs two things that look unrelated and are the same mechanism — why lengthening a prompt is cheap in a way that lengthening an answer is not, and why a server that has already seen your system prompt can skip most of the work of reading it again.

What prefill stores and decode reads#

Someone rewriting a generation loop by hand, to get control over sampling, will usually write the honest version first:

tokens = tokenizer.encode(prompt)          # 2,000 tokens
for _ in range(300):
    logits = model(torch.tensor([tokens])).logits[0, -1]
    tokens.append(sample(logits))

It produces correct output and it takes about 25 seconds on the same H100 that a serving stack finishes in 2.2. The reason is visible in the loop: every iteration passes the whole sequence to the model again. Step 1 runs a forward pass over 2,000 positions, step 2 over 2,001, step 300 over 2,299, and each of those is a full prefill costing roughly 80 ms. Three hundred of them is 24 seconds, and the ratio to 2.10 seconds of real decode time is not a constant — at 1,000 output tokens the naive loop would be forty times slower, because its cost grows with the square of the sequence length while the real one grows linearly.

The gap between those two loops is one line of state. When token 2,001 arrives, it needs its own query, and it needs the keys and values of all 2,000 positions before it — which are exactly the keys and values prefill already computed. Those retained keys and values are the KV cache. Prefill computes them for every prompt position at every layer and writes them into GPU memory. Each decode step then computes a query, key and value for one new position, appends that key and value to the cache, and attends the new query over everything stored. The forward pass still touches all the model's weights, which is where its 16 GB of traffic comes from, but it only ever computes fresh activations for a single position.

Three vectors come out of each position and exactly two of them are kept, and pinning down why explains the cache's name and its size in the same breath. A position's query is used once, in the attention computation for that position, and is then finished with — nothing later ever consults it again. A position's key and value are consulted by every position that comes after it, once per step, for as long as the sequence keeps growing. And because attention is causal, what a position offers is computed from itself and the positions before it alone, so it cannot change when new tokens arrive: the key position 1,847 presents to position 2,300 is the identical object it presented to position 2,001. Something consulted many times and guaranteed not to change is precisely what a cache is for, and something consulted once and discarded is not. Keys and values are therefore cached, queries are not, and the per-token size of the cache carries a factor of two rather than a factor of three.

The size is worth computing once. Per token it is two vectors, K and V, per layer, per key/value head, at the head dimension, in whatever precision the cache is kept:

def kv_bytes_per_token(layers, kv_heads, head_dim, dtype_bytes=2):
    return 2 * layers * kv_heads * head_dim * dtype_bytes

# Llama 3.1 8B: 32 layers, 8 KV heads (grouped-query attention), head_dim 128
per_token = kv_bytes_per_token(32, 8, 128)      # 131,072 bytes = 128 KiB
print(per_token * 2000 / 2**20)                 # 256.0 MiB for the prompt
print(per_token * 2300 / 2**20)                 # 287.5 MiB at end of generation
print(per_token * 2300 * 64 / 2**30)            # 18.0 GiB for 64 such requests

On an 80 GB card holding 16 GB of weights and a few gigabytes of activations and workspace, roughly 60 GB is left for cache, which is about 490,000 tokens, or around 210 concurrent requests of the shape above. That number is the real capacity limit of the box, and it is a memory limit rather than a compute one. It is also why serving engines allocate the cache in fixed blocks with a per-sequence block table — the PagedAttention design — instead of reserving a contiguous slab per request at its maximum possible length: contiguous reservation wastes most of the memory on sequences that stop early, and the difference between the two schemes is a factor of several in how many requests fit.

Every factor in that formula is a question about where the numbers live, and reading it aloud is quicker than memorising it. The leading two is the key and the value. The layer count is there because attention happens once per layer and each layer keeps its own keys and values, so a thirty-two-layer model stores thirty-two independent copies of this state for every position. The key/value head count multiplied by the head dimension is the width of one such vector: eight heads at 128 numbers each. The final factor is the storage precision, two bytes a number in bfloat16. Multiply the four together and one token of one request costs 131,072 bytes, which is 128 KiB.

The capacity arithmetic that follows is two divisions with nothing hidden in them. Free memory divided by cost per token gives tokens, so roughly 60 GB of space at 128 KiB a token is about 490,000 tokens the card can hold at once. Tokens divided by tokens per request gives requests, and since a finished request of this shape occupies 2,300 positions, 490,000 divided by 2,300 is around 210 of them. What makes that the box's real limit rather than one constraint among several is an asymmetry between the two things sharing the memory. The weights are paid for once for the whole server however many requests it serves. The cache is paid for once per position per request. So the weights enter the capacity calculation only as a fixed subtraction at the start, and everything after that subtraction is cache.

Note which term is missing from that formula: the number of query heads. Grouped-query attention, an attention layout in which several query heads share a single key/value pair rather than each carrying its own, was adopted largely to shrink this number — the same model with 32 KV heads instead of 8 would need 512 KiB per token and four times the memory for the same traffic. Multi-head latent attention in the DeepSeek line compresses it further by storing a low-rank projection instead of the full keys and values. These are not incidental optimisations; the KV cache is the reason a GPU with 80 GB of memory and a 16 GB model cannot serve unlimited concurrent requests.

The prompt is paid once, the output is paid every step#

Two consequences follow directly, and they are the whole reason to care about the mechanism.

A longer prompt costs more prefill and almost nothing per decode step. Doubling from 2,000 to 4,000 tokens roughly doubles prefill arithmetic and so roughly doubles time to first token, from 95 ms to a little over 190 ms. It does not double inter-token latency, because a decode step's dominant cost is the 16 GB weight read, which is indifferent to how long the sequence is. There is a second-order effect: the decode step also reads the KV cache, and that read grows with sequence length. At 2,300 tokens the cache is 287 MiB, which at 3.35 TB/s costs 86 microseconds against a 7,000-microsecond step — 1.2%, invisible. At 32,000 tokens it is 4 GB per step, which is comparable to the weight read itself, and inter-token latency roughly doubles. Flat means flat within the range where the KV read is small, which for an 8B model with grouped-query attention is most of the context window.

A longer output costs one full decode step per additional token, with no amortisation available. Going from 300 to 600 output tokens adds 300 × 7 ms = 2.1 seconds to total time, and there is no cache, no batching and no hardware that removes the serial dependency, because token 601 genuinely cannot be computed before token 600 exists. Speculative decoding attacks this by having a small draft model propose several tokens and verifying them in one pass of the large model, which turns some decode steps into something more prefill-shaped; it is the main line of attack on the serial bound and it is out of scope here beyond knowing it exists.

A prefix already in the cache can skip its prefill#

If the state prefill leaves behind is reusable across steps of one request, the obvious next question is whether it is reusable across requests, and for a shared prefix it is. Many production prompts begin with the same 1,800 tokens of system instructions, tool definitions and few-shot examples, followed by a short user turn. A server with prefix caching hashes the prompt block by block, finds that the first 1,800 tokens match blocks it already holds, and starts prefill at position 1,801.

cold:  prefill 2,000 tokens   ->  TTFT  95 ms
warm:  prefill   200 tokens   ->  TTFT  21 ms

Most of the remaining 21 ms is fixed overhead — tokenisation, scheduling, the first sampling step — rather than model arithmetic, which is why the saving is not perfectly proportional to the tokens skipped.

Hosted APIs expose the same mechanism under names like prompt caching, usually with an explicit marker in the request and a usage field in the response reporting how many input tokens were read from cache rather than processed. The billing follows the physics: cached input tokens are discounted heavily because the provider skipped their prefill, while output tokens are never discounted, because no cache removes a decode step.

The rules for getting a hit are stricter than people expect. The match must start at position 0 and be a contiguous prefix, because the keys and values of position 900 depend on every position before it; a prompt that shares 1,800 tokens with a cached one but differs at token 3 shares nothing. This is the mechanical reason to put stable content at the front of a prompt and volatile content — a timestamp, a request ID, a user name — at the end. It is also why serving stacks quantise the match to fixed-size blocks, typically 16 tokens: a hit is measured in whole blocks, so the last partial block is recomputed.

Why one early difference destroys the entire match has to be derived rather than asserted, because "the prefix must be exact" sounds like a rule somebody chose and it is not one. A position's key and value are computed from that position's representation, and that representation is the output of every layer below it, each of which attended over all the positions before it. The key stored for position 900 is therefore a function of tokens one through 900 rather than of token 900 on its own. Change token 3 and position 900's key becomes a different vector — not slightly different in a way that might be tolerated, but the result of a different computation, with no usable relationship to the one in the cache. Nothing is left to reuse, and that is a fact about how the model computes rather than a limitation of the cache. Serving stacks make the rule cheap to enforce by chaining the identifiers they hash: a block's identifier covers the tokens in that block together with the identifier of the block before it, so two sequences agree on a block's identifier only if they agree on everything up to and including that block. A prefix match then reduces to a lookup, and a non-prefix match cannot be expressed at all.

Why the first measurement lies#

All of this makes the first request you send to a fresh server unrepresentative of everything that follows, and unrepresentative in more than one direction at once.

The prefix cache is empty, so a request that would hit in production pays full prefill. The GPU-side optimisations that a server applies to itself on the way up have not finished either: CUDA graphs record a whole forward pass as one replayable unit so that thousands of individual kernel launches become one, and kernel autotuning picks the fastest available implementation of each operation for the shapes actually being run, and until both have happened the first few forward passes execute through slower generic paths. On a vLLM-style server — vLLM being the widely used open-source inference engine whose scheduler and cache design most current stacks follow — this alone can add hundreds of milliseconds to the first request. Weights may still be paging in from host memory or disk. Memory allocators have not reached steady state, and the first large allocation is genuinely slower than the thousandth.

The direction of the error is not consistent, which is what makes it dangerous. Cold caches and cold kernels make the first request slower than production. Meanwhile the server has no other traffic, so there is no queue, no batch to share decode capacity with, and no competing prefill in front of yours — all of which make that same first request faster than production. A single cold measurement is the sum of one effect that inflates the number and several that deflate it, and there is no way to reason backwards from the total to either one.

The practical version of that is a warmup, and the practical version of the warmup is not one throwaway request. You need enough traffic to populate the prefix cache with the prompts you are about to measure, to trigger graph capture at the batch sizes you will actually run, and to reach a steady state in memory allocation — in practice a few dozen requests of the same shape before you start recording.

Prefix caching is also not a response cache, and confusing the two produces bad expectations in both directions. A response cache returns a stored answer and does no model work at all; prefix caching skips part of prefill and then generates normally, so it changes latency and leaves the output distribution untouched. It does not reduce memory pressure either — it spends memory to save compute, and cached prefixes compete for the same GPU memory the KV caches of live requests need, which is why servers evict them under load. Nor is it a semantic cache: the match is on exact token IDs, so a paraphrase of a cached system prompt is a complete miss.

One piece of retained state explains all of it. Because prefill's keys and values survive, a decode step is incremental rather than quadratic; because they are addressable by prefix, an identical opening can skip work across requests; and because they occupy memory proportional to tokens held, the cache rather than the model weights is what limits concurrency. The same fact also sets the shape of any honest measurement, since a server that has not yet built this state is not the server your users are talking to.

Knowing that prompt length lands on prefill and output length lands on decode is a prediction, and predictions are worth testing rather than trusting, particularly since the slopes bend at long context and under load. The next chapter runs the experiment: vary the two lengths independently, record both metrics, and read the result back as an attribution rather than as "it got slower".