Beyond a Forward Pass · Part 3 of 5 · LLM inference · July 2026
Part 3 of 5. The working memory of autoregressive generation — sized wrong it kills batch size; managed like an OS it unlocks continuous batching.
In self-attention, each new token attends to keys and values of all previous tokens. Without caching, decode step t would recompute K and V for tokens \(1,\ldots,t\) every time — asymptotic disaster. The KV cache stores those tensors and appends a row (per layer, per head group) for each new token.
Prefill writes the prompt’s K/V. Each decode step reads the cache, writes one new slice, and samples the next token. This is the state that makes multi-turn chat “remember” earlier turns without re-running the whole history from scratch every time — though naively re-prefill still happens if you do not keep the cache (or a prefix of it) alive.
For a standard multi-head setup (adjust for GQA/MQA):
bytes_per_token ≈ 2 * n_layers * n_kv_heads * d_head * bytes_per_elem
# 2 = key + value
total_kv ≈ batch * seq_len * bytes_per_token
Concrete paper number for OPT-13B in FP16: \[ 2 \times 5120 \times 40 \times 2 \approx 800\ \text{KB of KV per token} \] so a single 2048-token request can need ~1.6 GB of KV alone — before batching. Profiled pre-paging systems often kept only ~20–38% of reserved KV memory holding real token state; the rest was reservation and fragmentation waste. Scale by batch and context and you exhaust a 40–80 GB GPU after weights. This is why:
Early systems reserved a contiguous KV buffer up to max_seq_len per request.
Three wastes appear (as the PagedAttention paper diagrams):
Continuous batching (Part 1) makes this worse if unmanaged: sequences constantly enter and leave; contiguous allocators thrash. You need an allocator designed for dynamic, append-only per-sequence tensors.
PagedAttention (vLLM) borrows OS paging:
Wastage drops to roughly the unused portion of the last block (< block size), not the entire unused max context. That reclaimed memory becomes higher batch size → higher throughput under continuous batching.
Once you have block tables, you can share physical blocks across sequences with the same prefix (beam search, parallel samples, system prompt). Reference counts + copy-on-write when a sequence diverges. This is the bridge into prefix caching (Part 4).
Attention is not one algorithm in production:
The engineering win of vLLM was not only the allocator — it was rewriting attention to tolerate non-contiguous KV without giving back the memory savings in kernel overhead.
Nishihara’s third point is broader than paging: policy questions.
| Policy | Idea | When |
|---|---|---|
| Keep hot prefixes | System prompts, RAG templates, agent scaffolds | High reuse rate |
| Evict cold multi-turn | LRU/LFU on idle sessions | Memory pressure |
| Recompute | Drop KV and re-prefill | When recompute < stall cost of swap |
| Offload | CPU/NVMe KV offload | Huge context, patient latency |
There is no universal policy. Chat with sticky sessions wants long-lived cache. Stateless request APIs may only cache automatic prefixes. Agents with huge tool traces force hard choices between context editing (drop tool outputs) and memory hierarchy (offload).
Next: using that cache across requests and machines — prefix-aware caching and routing.