KV cache explained

Generating each new token would otherwise recompute attention over the whole sequence. The KV cache stores that work so each step is incremental. It is also the reason serving is bounded by memory rather than compute.

A transformer generates text one token at a time. To produce token N+1, the model attends over all N previous tokens. Without caching, each step recomputes the attention keys and values for every earlier token, so the cost of generating a sequence grows quadratically with its length. The KV cache removes that recomputation, and in doing so becomes the dominant memory consumer in a serving system.

What is cached

In each attention layer, every token produces a key vector and a value vector. These depend only on the token and the tokens before it, so once computed they never change. The cache stores them, per layer, per token. At step N+1 the model computes K and V for the new token only, appends them, and attends over the full cached set.

How much memory it takes

Per token, the cache holds one key and one value vector per layer per attention head:

bytes per token = 2 (K and V)
                × layers
                × kv_heads
                × head_dim
                × bytes per element

For a model with 32 layers, 8 KV heads (grouped-query attention), head dimension 128, in 16-bit precision:

2 × 32 × 8 × 128 × 2 = 131,072 bytes ≈ 128 KB per token

A 4,000-token context is 512 MB. A 32,000-token context is 4 GB. Sixteen concurrent requests at 8,000 tokens each is 16 GB, on a device that may have 80 GB in total and needs a large fraction of it for the weights. The cache, not the weights, is what limits how many requests a replica can hold at once.

Older models without grouped-query attention (32 KV heads instead of 8) are four times worse.

Two phases

Prefill processes the prompt in one parallel pass and fills the cache for all prompt tokens. It is compute-bound: matrix multiplications over thousands of tokens.

Decode generates one token per step. Each step reads the entire cache for the sequence and the entire weight set, and does a comparatively small amount of arithmetic. It is memory-bandwidth-bound: the time is spent moving bytes, not computing on them.

This split explains most serving behaviour. Time to first token is prefill; time per token is one decode step; batching helps decode because the weights are read once for every sequence in the batch.

Allocation

The naive approach reserves cache space for each request's maximum possible length at admission. A request that might generate 4,000 tokens reserves 512 MB whether it uses 50 tokens or 4,000. Memory is fragmented and mostly empty.

Paged allocation, introduced by vLLM as PagedAttention, divides the cache into fixed-size blocks (typically 16 tokens) and allocates them on demand as the sequence grows, with a block table mapping each sequence's logical positions to physical blocks. Utilisation rises from around 20 to 40 percent to above 90 percent, which translates directly into more concurrent sequences per device.

Sharing

Two requests with the same prompt prefix produce identical K and V for that prefix. Prefix caching keeps blocks for common prefixes resident and lets new requests reference them instead of recomputing. For a system prompt of 1,000 tokens shared by every request, this removes 1,000 tokens of prefill per request and 128 MB of cache per request. SGLang's RadixAttention generalises this to a tree of shared prefixes.

Reducing the footprint

• Quantisation of the cache to 8-bit halves it; some engines support 4-bit.
• Grouped-query attention reduces KV heads at training time; most current models use it.
• Sliding-window attention caps the cache at a fixed window for some layers.
• Eviction of the least recently used blocks under pressure, with recomputation on return. This is a throughput trade, not a free reduction.

Summary

The KV cache converts quadratic generation into linear at the cost of memory proportional to sequence length. That memory, not compute, is the binding constraint in serving, which is why the techniques that matter most, paged allocation, prefix sharing, and quantisation, are all about the cache rather than the model.