KV cache: the engine behind fast LLM inference

Distilled from Jayanth Sanku’s article on KV cache.

A transformer generates text one token at a time, and each new token attends to every token before it. The naive way to do that recomputes the attention inputs for the entire prefix on every step — so producing the 1000th token redoes the work of the previous 999. That is the difference between linear and quadratic generation, and it is the reason a long ChatGPT reply would otherwise crawl to a halt. The KV cache removes the redundancy by storing the per-token tensors that never change once computed.

Concept

KV cache

Cache the per-token Key and Value tensors so each decoding step computes attention for the new token only, not the whole prefix.

Attention for one token is softmax(Q · Kᵀ / √d) · V. The Query comes from the current token, but the Keys and Values come from all prior tokens — and a past token’s K and V never change once it is generated. So the model computes K and V once per token, appends them to a growing cache, and at every later step reuses the cache instead of recomputing it. Only the new token’s Q, K, and V are fresh work.

The steps below show what changes between recomputing the prefix and caching it.

What happens at each decoding step

1. Receive the new token

   The token sampled from the previous step becomes the current input.

2. Project Q, K, V for this token only

   Compute the Query, Key, and Value for the new token. The prefix’s K and V are not recomputed.

3. Attend against the cache

   Score the new Query against every cached Key, then take the weighted sum over the cached Values: softmax(Qₙ · Kᵀ / √d) · V.

4. Append and repeat

   Push the new token’s K and V into the cache so the next step can attend to them. The cache grows by one token’s worth of tensors per step.

Why it matters

Without the cache, every decoding step re-runs the full forward pass over the entire prefix: step t reprocesses t tokens, so emitting n tokens costs 1 + 2 + ... + n — O(n²) total, a latency that compounds as the conversation lengthens. With the cache, each step runs the full forward pass for the one new token and reuses the stored K and V for the rest. The only part that still grows with context is the attention scores themselves — the new query dotted against every cached key, O(n) per step — but that is cheap arithmetic next to the model forward pass the cache no longer repeats. So the dominant cost drops from quadratic to linear, which is what lets responses stream smoothly instead of slowing to a crawl as context grows.

The cost: memory

The cache is not free — it trades compute for memory, and that memory is the binding constraint at scale.

• It grows with context length. Every token adds K and V tensors for every layer and every attention head. A long context can consume gigabytes of GPU memory purely for the cache.
• It scales with the batch. Serving many sequences concurrently multiplies the cache footprint, and the allocations have wildly different lifetimes — naive contiguous allocation fragments memory badly.
• It is bounded by the context window. The maximum cache size is tied to the model’s maximum context; a longer supported window means a larger worst-case cache to provision for.

How serving systems tame the cost

Paged KV cache

Allocate the cache in fixed-size blocks (pages) instead of one contiguous buffer, the way an OS pages memory. Eliminates fragmentation and lets sequences share blocks — the core trick behind vLLM's PagedAttention.

Quantized KV cache

Store the cached K and V at lower precision (e.g. FP16 to INT8) to roughly halve the footprint, trading a little numerical accuracy for much more headroom.

Eviction / token dropping

In very long contexts, drop or compress the cache entries for low-attention tokens so the cache stops growing without truncating the visible context entirely.

FlashAttention

A memory-efficient attention kernel that avoids materializing the full attention matrix in HBM, reducing memory traffic and pairing well with a large KV cache.

What to remember