Chapter 38 — The memory trick that makes it fast (the KV cache)

The problem

Generating token 100 means running the model over tokens 1–99 again... and token 101 means running over 1–100... That would be enormously wasteful. Generating a 1,000-token answer would cost the same as processing 500,000 tokens.

The insight

Look back at attention (Chapter 24). For each token you compute a key and a value. Crucially:

A token's key and value never change once computed. Token 5's key depends only on token 5 and what came before it — and thanks to the causal mask, later tokens can't affect it.

So: compute them once, store them, reuse them. That store is the KV cache.

Generating "The cat sat on the mat":

step 1: process "The"    -> compute K,V for "The"     -> CACHE: [The]
step 2: process "cat"    -> compute K,V for "cat"     -> CACHE: [The, cat]
        attention uses the cached K,V for "The" -- no recomputation
step 3: process "sat"    -> compute K,V for "sat"     -> CACHE: [The, cat, sat]
        ...

Each step: ONE new token's worth of work, plus a lookup over the cache.

Without it, generation would be quadratic in length. With it, it's linear. Every serving system uses it.

The cost: memory, and it grows

The cache holds a key and a value vector for every token, every layer, every attention head.

KV cache size = 2 (K and V)
              x number of layers
              x number of key/value heads
              x dimensions per head
              x number of tokens so far
              x number of concurrent users
              x bytes per number

Concrete example — a 13B model with 40 layers, 40 heads of 128 dims, 2 bytes per number:

per token, per user:  2 x 40 x 40 x 128 x 2 bytes  =  819,200 bytes  ~= 0.8 MB

   4,000-token conversation, ONE user:   ~3.2 GB
   4,000-token conversation, 32 users:  ~100 GB      <- more than the model itself!

This is why long context is expensive, and why serving many users simultaneously is hard. The KV cache, not the model weights, is usually the binding constraint.

How engineers shrink it

Technique	What it does
GQA / MQA (grouped/multi-query attention)	many query heads share a few key/value heads -> 4–8x smaller cache. This is why almost every modern LLM uses GQA (Chapter 25).
KV cache quantisation	store keys/values in 8-bit instead of 16-bit -> half the size
PagedAttention (vLLM)	manage the cache in small fixed blocks like operating-system virtual memory -> almost no wasted space, and blocks can be shared between requests
Sliding window	only keep the last N tokens' cache -> constant size, but the model forgets the far past
Prefix caching	if many requests share the same beginning (a system prompt, a document), compute its cache once and reuse it — this is what "cached input tokens" pricing means

Practice (10 min) — measure the speedup

import time, torch
from transformers import AutoTokenizer, AutoModelForCausalLM

name = "Qwen/Qwen2.5-0.5B-Instruct"
tok = AutoTokenizer.from_pretrained(name)
model = AutoModelForCausalLM.from_pretrained(name); model.eval()

ids = tok("Once upon a time in a distant land", return_tensors="pt").input_ids

for use_cache in [True, False]:
    t0 = time.time()
    with torch.no_grad():
        model.generate(ids, max_new_tokens=120, do_sample=False,
                       use_cache=use_cache, pad_token_id=tok.eos_token_id)
    print(f"use_cache={use_cache!s:5}  {time.time()-t0:6.2f}s")

The use_cache=False run will be dramatically slower, and the gap widens with longer outputs. You have just measured the single most important optimisation in LLM serving.

Check yourself

Why can a token's key and value be cached and reused?
What is the main cost of the KV cache?
Why does GQA exist?
Why does a long conversation get slower and more expensive over time?