Skip to content
AI Engineer Guide.

concept · concepts · intermediate · concept 27 of 33

KV cache

0 of 33 complete

Why it matters

A decoder generates one token at a time, and each step attends over everything before it. Without stored state, step tt would recompute keys and values for all t−1t-1 previous positions, so producing nn tokens would cost work proportional to n2n^2 — the same quadratic term as prefill, paid again and again.

The cache removes that recomputation. It also creates the constraint that shapes inference economics: memory per request grows linearly with context, and concurrency multiplies it. If you have wondered why a long-context endpoint admits fewer concurrent requests, or why output tokens are often priced above input tokens, this arithmetic is a large part of the answer.

Mental model: prep work kept on the counter

A cook preparing a long dish chops vegetables for each step. Without organisation, every new step re-chops everything used so far. With a tray of prepped ingredients, each step only chops the new item and reaches for the tray.

Keys and values are the prepped tray; the query is the new item. Attention still runs over everything, but the expensive projections for past tokens are not repeated.

The analogy breaks in one place that matters for capacity planning: the tray grows with every step and cannot be shared between tables. Each concurrent request needs its own tray, and at long context the trays — not the cooks — are what limit how many tables the kitchen can serve.

How it works

A per-request cache in a fixed block poolInteractive
4/16 slots occupiedlivefree

Step · 1 of 10

A's prompt fills four blocks

A's 16-token prompt is written into four blocks of four positions each. Four of sixteen slots are live and sixteen tokens are cached. A buffer sized to the maximum context would have reserved the whole window; here only the positions A actually has are allocated.

Next: A decodes four tokens

Live blocks
4
Sequences
1
Cached tokens
16
Free blocks
12
Rejected
0
Step 1/10 · A's prompt fills four blocks

Figure. Sixteen fixed blocks of four token positions each for one layer of one device. Four requests arrive at different times. A, B and C decode; A finishes and releases its six blocks, while B, C and D remain live at the end. A fifth request is refused because it needs four blocks and only two are free. Different prefixes mean no sharing in this figure, so each request's blocks are private. Counts are synthetic; real engines hold thousands of blocks.

What to notice. Every live block belongs to exactly one sequence, and only a finishing sequence returns its blocks. Concurrency and output length both raise the block count: at step 6 A's six blocks are released, and by step 9 the three remaining sequences hold fourteen. The pool is not a cache that can evict for free: with no policy, the last step refuses E before its first token rather than displacing a prefix. Prefix sharing, quantisation and paged tables are separate mechanisms and are not drawn.

Text version

A 16-slot block pool, four positions per block, one layer. Step 1: A's 16-token prompt fills A0 to A3, 4 live, 16 tokens. Step 2: A decodes four tokens into A4, 5 live, 20 tokens. Step 3: four more into A5, 6 live, 24 tokens. Step 4: B has a different prefix and allocates B0 to B2, 9 live, 36 tokens. Step 5: C adds C0 to C4, 14 live, 56 tokens, 2 free. Step 6: A finishes and A0 to A5 are released, 8 live, 32 tokens. Step 7: D takes four of A's slots with D0 to D3, 12 live, 48 tokens. Step 8: C adds C5, 13 live, 52 tokens. Step 9: B adds B3, 14 live, 56 tokens, 2 free. Step 10: E needs four blocks with two free, so admission rejects E; 14 live and 1 rejected. Counters show live blocks 4, 5, 6, 9, 14, 8, 12, 13, 14, 14; sequences 1, 1, 1, 2, 3, 2, 3, 3, 3, 3; cached tokens 16, 20, 24, 36, 56, 32, 48, 52, 56, 56; free blocks 12, 11, 10, 7, 2, 8, 4, 3, 2, 2; rejected 0 until step 10 then 1.

  1. Prefill the prompt. Process all prompt tokens in parallel. Each layer computes keys and values for every position and stores them in per-layer cache tensors.
  2. Start decoding. For the first output token, compute only its query, key and value. Append the new key and value to the cache.
  3. Attend over the cache. The new query scores against all cached keys, the softmax produces weights over the whole prefix, and the weighted sum uses cached values.
  4. Sample and repeat. Take the chosen token, feed it back as the next input, and repeat steps 2–3 until a stop condition.
  5. Respect positions. Each new token needs its correct position id. After truncation, compaction or cache reuse, positions must be recomputed to match the cached prefix, not the raw input index.
  6. Size the cache. Compute bytes per token per layer, multiply by layers, tokens and concurrent requests.
  7. Reduce it. Share key/value heads (multi-query or grouped-query attention), quantise the cache, page it so memory is allocated in blocks rather than reserved for the maximum length, or reuse a shared prefix.
  8. Invalidate correctly. A cache is only valid for the exact prefix that produced it. Any edit to the prompt, system message or tool list invalidates everything after the change.

The math

Cache size per sequence:

bytes=2×L×Hkv×dhead×n×b,\text{bytes} = 2 \times L \times H_{kv} \times d_{\text{head}} \times n \times b,

where LL is layers, HkvH_{kv} key/value heads, nn cached tokens and bb bytes per element. The leading 2 is for both keys and values.

Decode reads essentially the whole cache at every step, so the arithmetic intensity is low:

bytes read per generated token≈cache size,FLOPs per token≈2P,\text{bytes read per generated token} \approx \text{cache size}, \qquad \text{FLOPs per token} \approx 2P,

with PP the parameter count. At long context the read dominates, which makes decode memory-bandwidth-bound rather than compute-bound.

A minimal implementation

import numpy as np
 
def kv_bytes(layers: int, kv_heads: int, d_head: int, tokens: int, bytes_per_elem: int = 2) -> int:
    return 2 * layers * kv_heads * d_head * tokens * bytes_per_elem
 
class KVCache:
    """Per-layer cache of keys and values; one instance per sequence."""
    def __init__(self, layers: int):
        self.k: list[np.ndarray] = [None] * layers   # (heads, tokens, d_head)
        self.v: list[np.ndarray] = [None] * layers
 
    def append(self, layer: int, k: np.ndarray, v: np.ndarray) -> None:
        self.k[layer] = k if self.k[layer] is None else np.concatenate([self.k[layer], k], axis=1)
        self.v[layer] = v if self.v[layer] is None else np.concatenate([self.v[layer], v], axis=1)
 
    def length(self, layer: int) -> int:
        return 0 if self.k[layer] is None else self.k[layer].shape[1]
 
cache = KVCache(layers=2)
for step in range(4):
    cache.append(0, np.random.randn(8, 1, 128), np.random.randn(8, 1, 128))
    cache.append(1, np.random.randn(8, 1, 128), np.random.randn(8, 1, 128))
 
print(cache.length(0), kv_bytes(32, 8, 128, 8192) / 2**30, "GiB")

In a real implementation you pre-allocate a buffer and write at an offset; concatenate per step copies the whole cache and would erase the benefit. The toy version is for shapes, not throughput.

Trade-offs

ChoiceGood forCostFails when
No cache (recompute)Debugging, tiny models, stateless batchesO(n²) work per generated tokenOutput is longer than a few tokens
Full KV cacheStandard serving, best per-token latencyMemory grows with context × concurrencyLong contexts and many concurrent users
GQA / MQAReducing cache and read bandwidthFewer distinct key/value representationsQuality is sensitive and head sharing is too aggressive
Quantised cacheFitting more sequences per devicePrecision loss, extra kernelsTasks need fine numeric or factual precision
Paged / offloaded cacheHigh concurrency, near-capacity memoryIndirection, paging overheadSequences are short and allocation is already cheap
Trade-off mapInteractive

Good for

Debugging, tiny models, stateless batches

Cost

O(n²) work per generated token

Fails when

Output is longer than a few tokens

  1. Output is longer than a few tokens
  2. Long contexts and many concurrent users
  3. Quality is sensitive and head sharing is too aggressive
  4. Tasks need fine numeric or factual precision
  5. Sequences are short and allocation is already cheap

Figure. Each choice with what it buys, what it costs, and the case where it loses.

What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.

Text version

Four trade-offs: No cache (recompute) is good for Debugging, tiny models, stateless batches, costs O(n²) work per generated token, and fails when Output is longer than a few tokens. Full KV cache is good for Standard serving, best per-token latency, costs Memory grows with context × concurrency, and fails when Long contexts and many concurrent users. GQA / MQA is good for Reducing cache and read bandwidth, costs Fewer distinct key/value representations, and fails when Quality is sensitive and head sharing is too aggressive. Quantised cache is good for Fitting more sequences per device, costs Precision loss, extra kernels, and fails when Tasks need fine numeric or factual precision. Paged / offloaded cache is good for High concurrency, near-capacity memory, costs Indirection, paging overhead, and fails when Sequences are short and allocation is already cheap

Failure modes

Cache and position mismatch. After truncating the prompt or compacting history, position ids no longer match the cached prefix, and output degrades oddly rather than failing. Debugging step: recompute a full forward pass for the same prefix and compare logits with the cached run at the first divergent step.

Stale cache after a prompt edit. A prefix cache is reused even though the system message changed, so the model answers against old instructions. Debugging step: hash the exact token ids of the prefix and include the hash in the cache key; never key on a template name.

Memory exhaustion under concurrency. Throughput collapses or requests are rejected as concurrent sequences grow. Debugging step: track cache bytes per request and peak concurrent sequences; the product is your real memory floor.

Cache leaked between requests. A shared mutable cache carries one user's context into another's answer. Debugging step: assert cache ownership per request id and add a test that two different prefixes never share entries.

In production

Capacity planning starts from cache arithmetic, not from parameter count. Compute bytes per token for your model, multiply by the p95 context length you intend to support, then by the concurrency you promise. The result tells you how many sequences fit on a device.

Prefix caching is the highest-leverage optimisation for applications with a stable system prompt: identical prefixes reuse cached keys and values, so prefill cost drops for every request after the first. It requires byte-identical prefixes, which makes prompt-template discipline a performance concern as well as a quality one.

Chunked prefill and continuous batching exist to keep the decode loop busy while new prompts arrive. Both are cache-management strategies — they decide whose cache gets memory and when.

Common misconceptions

People think: The KV cache speeds up prefill by remembering the prompt.

Actually: It is built during prefill and used during decode. Prefix reuse can avoid repeated prefill, but the cache's core purpose is stopping per-step recomputation of past tokens.

People think: The cache stores all intermediate activations, so it is roughly the size of the model.

Actually: It stores only keys and values per layer. That is far smaller than all activations, but it grows with context and concurrency, which is why it dominates at long lengths.

A third: that a cache is a model-level optimisation. It is request-level state, and its correctness depends on exact prefix identity, not on belonging to the same model.

Interview angle

A strong answer distinguishes prefill from decode, derives cache size from layers, KV heads and tokens, and explains why decode is bandwidth-bound. The usual follow-up — "how would you serve twice the context length?" — has several valid answers: fewer KV heads, quantisation, paging, or admitting a lower concurrency. Naming the trade-off matters more than naming the technique. Continue with prefill and decode and GQA and MQA, or see /interview.

Sources