CSE Roadmap

Specialist tier · about 5 hours · 12 parts

Part 2 of 12 · 2 min read

The KV cache turns quadratic recomputation into linear work, and costs memory

Without a cache, generating each new token means recomputing attention over every token that came before it, again and again.

Think of writing a long essay by re-reading the entire thing from the start every time you add one sentence. Compare that with keeping a running outline of what you have already covered. Then you only need to look at the new part.

In plain words: without a KV cache, producing the Nth token means recomputing attention over all N-1 previous tokens from scratch, which grows quadratically with output length — caching the keys and values of earlier tokens so each new step only processes the newest token turns that into linear work, at the cost of memory to store the cache.

A worked example. Starting from a 5-token prompt and generating 160 tokens: without a cache, the model processes 13,520 total positions (recomputing the growing prefix at every step); with a cache, it processes only 165 positions — the prompt plus one new token per step. The outputs are identical either way, down to a maximum logit difference near 7e-15 — caching changes speed, not what the model computes. But that speed comes at a cost: at a sequence length of 8,192 tokens, the 16-bit cache per sequence is 8 times smaller per shrink in sequence length (512→2,048→8,192 give 128, 32, 8 max sequences fitting per GPU) — the cache grows linearly with sequence length and directly limits how many requests fit in memory at once.

The key lines. From code/mini-inference/memory.py:

# from code/mini-inference/memory.py
def kv_cache_bytes(batch, seq, layers, d_model, bytes_per_value=2, kv_fraction=1.0):
    """2 (K and V) x B x S x L x H x M, times kv_fraction (n_kv_heads / n_heads for grouped-query attention)."""
    if min(batch, seq, layers, d_model) < 0 or not 0 < kv_fraction <= 1:
        raise ValueError("sizes must be non-negative and kv_fraction in (0, 1]")
    return 2 * batch * seq * layers * d_model * bytes_per_value * kv_fraction

Read it as: cache size scales directly with batch and sequence length, multiplied together. Doubling either one doubles the cache. That is exactly why long conversations and large batches compete for the same limited GPU memory.

Prefill and decode, KV cache

Prefill processes all input tokens in parallel to build the cache and the first output token; decode generates one token per step, reading the whole model and cache each time. The KV cache stores the attention keys and values of earlier tokens so each decode step only computes the new token's contribution.

Example: the 13,520-to-165 positions comparison above is the entire value of the cache in one number — it's the difference between recomputing every prior token at every step and computing only the newest one.