Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 ยท Inference and Optimization

The KV Cache

Understand why LLMs cache keys and values, verify in NumPy that caching gives identical outputs with far less work, and calculate KV cache memory for real model shapes.

LLMs generate one token at a time. Each new token needs attention over all previous tokens. Naively, every step would recompute the keys and values of the whole prefix from scratch, and generating n tokens would cost on the order of n^2 projections. The KV cache stores the keys and values already computed, so each step computes only the new token's key and value, then attends to the cached ones.

This one trick is why interactive chat is fast. It is also why long conversations eat GPU memory.

Why the cache is valid

In decoder-only models, attention is causal: token t attends only to tokens 0..t. The key and value vectors of token i depend only on token i's hidden state, which depends only on earlier tokens. When a new token arrives, the earlier tokens' keys and values do not change. So we can keep them.

flowchart LR
    subgraph Step_t["Step t"]
    N["new token x_t"] --> Q["q_t"]
    N --> K["k_t, v_t"]
    end
    K --> C["append to cache K[0..t], V[0..t]"]
    C --> AT["attention(q_t, K, V)"]
    Q --> AT
    AT --> O["output for token t"]

Only one query, key and value are computed per step; the rest is read from memory.

Prove it: cached equals uncached

We implement single-head causal attention two ways and compare. Weights are random; the point is the identity of the results and the count of projections.

Python Cached and uncached attention agree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The outputs match to floating-point precision. The projection count drops from T(T+1)/2 to T. The attention dot products still scale with the prefix length (each step reads all cached keys), but the saving of the expensive matrix multiplies is large.

Prefill and decode

Serving a request has two phases:

  • Prefill: process the whole prompt in parallel and fill the cache. This is compute-bound; a long prompt means a noticeable wait for the first token (time to first token).
  • Decode: generate one token per step, reading weights and cache. This is memory-bandwidth-bound: each step moves all model weights and the cache through the GPU for a single token of work. That is why batching many requests together (serving) raises throughput.

How big is the cache?

Per token and per layer, we store one key and one value vector for each KV head:

Text
bytes = 2 (K and V) x layers x kv_heads x head_dim x bytes_per_value x tokens x batch
Python KV cache memory calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A single 32k-token sequence with plain multi-head attention needs 16 GiB of cache, which rivals the weights. With a batch, the cache often exceeds the model. So long contexts and big batches are limited by cache memory, not by compute.

Shrinking the cache

  • Multi-query attention (MQA): all query heads share one key/value head.
  • Grouped-query attention (GQA): groups of query heads share a KV head. Nearly the quality of full multi-head attention with a fraction of the cache. Common in modern open models.
  • Multi-head latent attention (MLA): caches a compressed latent from which keys and values are reconstructed.
  • Quantized cache: store K and V in 8 or 4 bits (quantization).
  • Sliding-window attention: keep only the last w tokens in some layers.
  • Eviction and compression: drop or merge tokens with low attention.
  • Paged attention: allocate the cache in small fixed-size blocks, like virtual memory pages, so no space is lost to fragmentation and prompt prefixes can be shared between requests.
  • Prefix caching: reuse the cache for a shared system prompt or document, so only the new part is prefilled.

Practical consequences

  1. Long prompts raise first-token latency (prefill) and memory use for the whole request lifetime.
  2. A shared system prompt is cheap with prefix caching, and expensive without it.
  3. Providers charge differently for cached input tokens for exactly this reason.
  4. When estimating capacity, compute GPU memory - weights, then divide by the cache size per request.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can the keys and values of earlier tokens be cached?

    A token cannot see the future, so adding a new token does not change earlier tokens' keys and values.
  2. 2. Which phase is typically memory-bandwidth-bound?

    Each decode step reads all the weights and cache for very little arithmetic.
  3. 3. What does grouped-query attention reduce?

    Several query heads share one KV head, so fewer key/value vectors are stored per token.
  4. 4. A model has 32 layers, 8 KV heads, head_dim 128, fp16. How many bytes of cache per token?

    K and V (2) x layers x KV heads x head_dim x 2 bytes = 131,072 bytes, which is 128 KiB per token.

Summary

  • The KV cache stores past keys and values so each step computes only one new token's projections.
  • Cached and uncached attention produce identical results.
  • Cache memory grows with layers, KV heads, context length and batch size and often dominates GPU memory.
  • GQA, quantized caches, paging and prefix caching make long contexts affordable.

Next: Weight Quantization