All concepts

KV Cache

Cache past keys and values so each new token costs O(n) instead of O(n²).

Transformers & LLMs · Advanced · ~8 min

In plain English

While writing a sentence, you don't re-read everything you've written before each new word. The KV cache is the model's memory of that reading, kept between steps.

Why it's worth your time

Without it generation is quadratic and unusably slow. With it, memory becomes your serving bottleneck — which is the real production trade.

If you remember three things

  • Cache the keys and values for tokens already processed
  • Turns per-token cost from O(n²) into O(n)
  • Cache size grows linearly with context AND with batch size

Overview

During autoregressive generation, the keys and values of previous tokens don't change. Caching them means each new token only computes its own query against the cached K/V, turning quadratic recompute into linear — the single biggest LLM inference optimization.

How it works

  1. Prime the cache The prompt is processed once; every token's keys and values are stored in the KV cache.
  2. New token → just a query Each generation step computes only the new token's Q, K, V — not the whole prefix again.
  3. Attend to the cache The new query attends against all cached keys/values — O(n) per token instead of recomputing O(n²).
  4. Generate the next token The model produces the next token from that attention.
  5. Append its K/V The new token's keys and values are appended to the cache, ready for the next step.
  6. Stream, token by token Repeat per token. The cache grows with length, so its memory — not compute — usually caps serving throughput.

In an interview

The KV cache stores the key and value vectors of already-generated tokens so each new token only computes attention against the cache instead of recomputing everything. It turns per-token generation from O(n²) to O(n) compute, at the cost of memory that grows with sequence length.

Production defaults

Size
2 × layers × kv_heads × head_dim × tokens × bytes. Compute it before promising a concurrency number
Shrink it
grouped-query attention first, then KV quantization to 8-bit
Serving
paged attention (vLLM) removes the fragmentation that wastes most of the cache in practice

What breaks

  • OOM at high concurrency but not at batch 1 — KV cache, not weights. It scales with batch × context; the weights are constant.
  • First token slow, rest fast — Expected. Prefill processes the whole prompt at once; decode reuses the cache.

Watch it explained

KV Cache Explained — Arize AI, 4:08

Related