The caching lineage: the researchers, the papers, the code

TL;DR. Caching is the deepest rabbit hole in this book, and it has a family tree. This chapter walks it by the people who built it: the KV cache's raw arithmetic (half a megabyte per token for a 7B model in fp16), the architectural shrinkers (Shazeer's MQA, Ainslie's GQA, DeepSeek's MLA at a 93.3% cut), Tri Dao's FlashAttention kernels, Woosuk Kwon and Zhuohan Li's PagedAttention (vLLM, SOSP 2023), Lianmin Zheng and Ying Sheng's RadixAttention (SGLang, NeurIPS 2024), Yale's Prompt Cache (position-independent reuse), Junchen Jiang's UChicago line that turned the cache into shippable data (CacheGen, CacheBlend, LMCache), Mooncake's datacenter-scale version, and the lossy branch (StreamingLLM, H2O, SnapKV, KIVI). A from-scratch lab replays one Claude Code working day as a radix tree over four cache policies (recompute-all 100%, per-stream 19%, global radix 12%, LRU-capped 34%) and shows why your fleet's prompts are a tree with one hot spine. The chapter closes where the ideas reach your bill: Anthropic's exact current cache parameters, verified against the live docs.

Contents

The object itself: KV bytes per token
The family tree
The lab: your working day as a radix tree
Reading the lab
Where the tree meets your bill: Anthropic's exact rules
The reading list
Further reading
Takeaways

Chapter 6 built the KV cache from attention math and Chapter 8 demoed paging and prefix sharing in vLLM and SGLang. This chapter is the layer under both: who invented each piece, in what paper, with what code, so that when you want to go deeper on any link in the chain you know exactly which door to knock on. Facts were verified against the papers, proceedings, and repositories in July 2026; star counts are that snapshot, rounded.

The object itself: KV bytes per token

Everything in this chapter exists because of one number. A transformer caches, per token, two vectors (K and V) per layer per KV head:

$$\text{bytes per token} = 2 \times n_{layers} \times n_{kv_heads} \times d_{head} \times \text{bytes per value}$$

For a classic 7B model (32 layers, 32 KV heads, head dim 128, fp16), that is $2 \times 32 \times 32 \times 128 \times 2 = 524{,}288$ bytes: half a megabyte per token. A 4k-token conversation holds 2 GB of cache; a hundred concurrent users hold 200 GB, which is more than the GPU. Every branch of the family tree below is one strategy against that number: make it smaller by architecture, waste less of it, share it, ship it, or throw parts of it away.

The family tree

Read the stack bottom-up; each layer attacks the number differently, and each has a name, a paper, and a repo attached.

Architecture: cache fewer heads. Noam Shazeer started it in 2019 with MQA ("Fast Transformer Decoding: One Write-Head is All You Need", arXiv 1911.02150): all query heads share a single K/V head, dividing the cache by the head count. Joshua Ainslie and colleagues at Google made it practical with GQA (EMNLP 2023, arXiv 2305.13245): a middle count of KV heads, uptrained from existing checkpoints, near-MQA savings at near-full quality, and the default in most modern open models (a GQA 8-head Llama-class 8B caches 128 KB per token, 4x less than the arithmetic above). DeepSeek's MLA (in the DeepSeek-V2 report, arXiv 2405.04434, covered for its attention side in Chapter 14) compresses K and V jointly into one small latent vector, and its abstract states the result plainly: a 93.3% KV-cache reduction. The cache you rent from any provider is shaped by this layer before a single systems trick runs.

Kernel: waste no memory traffic. Tri Dao (Stanford PhD, now Princeton and Together AI) wrote the kernel everyone runs: FlashAttention (arXiv 2205.14135, with Dan Fu, Stefano Ermon, Atri Rudra, Christopher Ré), exact attention tiled so the computation stays in on-chip SRAM instead of thrashing HBM; FlashAttention-2 (arXiv 2307.08691, solo) re-cut the work partitioning for ~2x; FlashAttention-3 (arXiv 2407.08608, Shah, Bikshandi, Zhang, Thakkar, Ramani, Dao) exploits Hopper's asynchrony and FP8. Repo: Dao-AILab/flash-attention (BSD-3, ~24.5k stars). Not a cache technique itself, but the reason attention over a long cached prefix is fast enough to be worth caching.

Serving memory: page it. Woosuk Kwon and Zhuohan Li (co-first authors, UC Berkeley, Ion Stoica's Sky lab) published PagedAttention at SOSP 2023 ("Efficient Memory Management for Large Language Model Serving with PagedAttention", arXiv 2309.06180, with Ying Sheng, Lianmin Zheng, and others): treat KV memory like OS virtual memory, fixed-size blocks, no fragmentation, sharing possible. The repo is vLLM (vllm-project/vllm, Apache-2.0, ~86k stars), and its automatic prefix caching is worth reading in the design doc because the mechanism is exactly our lab's: each full block's hash is computed from the parent block's hash plus the block's token ids plus "extra keys" (LoRA id, multimodal hashes, and cache salts for multi-tenant isolation), only full blocks are cached, and eviction is LRU. On by default in vLLM V1.

Cross-request sharing: grow a tree. Lianmin Zheng and Ying Sheng (Berkeley and Stanford; the same two names behind Vicuna, Chatbot Arena, and the LLM-as-judge paper Chapter 42 leans on) published SGLang at NeurIPS 2024 (arXiv 2312.07104): its RadixAttention keeps the KV of all past requests in one radix tree keyed by token prefixes, LRU-evicted, so any new request reuses the longest shared prefix automatically, across users and programs. Repo: sgl-project/sglang (Apache-2.0, ~30k stars). This is the idea our lab reduces to 40 lines, and the idea Anthropic sells as prompt caching.

Position-independent reuse: break the prefix rule. In Gim and Lin Zhong's group at Yale published Prompt Cache at MLSys 2024 (arXiv 2311.04934): precompute attention states for reusable prompt modules and reuse them even when the module appears at a different position in a new prompt. Research code at yale-sys/prompt-cache (MIT).

The cache as data: ship it. Junchen Jiang's group at UChicago noticed the cache is worth moving between machines. CacheGen (SIGCOMM 2024, arXiv 2310.07240, first author Yuhan Liu) compresses KV tensors into bitstreams sized to available bandwidth (3.5 to 4.3x smaller). CacheBlend (EuroSys 2025 best paper, arXiv 2405.16444, first author Jiayi Yao) fuses precomputed non-prefix KV chunks for RAG and selectively recomputes the few tokens (mostly chunk boundaries) that cross-chunk attention actually needs, which lifts the prefix-only restriction at a controlled quality cost. Both feed LMCache (LMCache/LMCache, Apache-2.0, ~10.6k stars): a production KV layer that tiers the cache across GPU, CPU DRAM, disk, and remote stores, and ships as the KV-offloading component of the official vLLM production stack. At datacenter scale the same thesis is Mooncake (Moonshot AI and Tsinghua, FAST 2025 best paper, arXiv 2407.00079): disaggregate prefill from decode and pool the fleet's idle DRAM and SSD into one distributed KV store; its transfer engine and store are open source (kvcache-ai/Mooncake, Apache-2.0) and integrate with vLLM, SGLang, and LMCache. The through-line: recomputing tokens is now often more expensive than storing and shipping their KV, which is the economics under every price multiplier in this book.

The lossy branch: keep less. Four papers define the compression-and-eviction frontier, one sentence each. StreamingLLM (Guangxuan Xiao, Song Han's MIT lab, ICLR 2024, arXiv 2309.17453, mit-han-lab/streaming-llm): the first few tokens act as "attention sinks," so keeping them plus a recent window lets a model stream far past its training length. H2O (Zhenyu Zhang, UT Austin, NeurIPS 2023, arXiv 2306.14048): a few "heavy hitter" tokens dominate attention mass, so evict everything that is neither heavy nor recent. SnapKV (Yuhong Li and colleagues at UIUC and Cohere, NeurIPS 2024, arXiv 2404.14469): the prompt's own tail reveals which positions each head attends to, so compress the prompt KV before generation even starts (8.2x memory at 16k context). KIVI (Zirui Liu and Xia Hu's Rice group, ICML 2024, arXiv 2402.02750, jy-yuan/KIVI): quantize keys per-channel and values per-token down to 2 bits, tuning-free, because that is where each tensor's outliers live. These trade fidelity for space, which providers so far do not do to your prompt cache; they matter when you serve models yourself under memory pressure.

Don't be confused. Prefix caching (vLLM, SGLang, Anthropic) reuses exact attention states and changes nothing about the output; the reuse rule is "identical prefix, identical KV." Position-independent reuse (Prompt Cache, CacheBlend) and the lossy branch (StreamingLLM, H2O, SnapKV, KIVI) relax exactness: they reuse or discard states the math says are approximately right, and buy their gains with a measured quality cost. The first family is a billing optimization; the second is a modeling decision.

The lab: your working day as a radix tree

The lab replays a realistic Claude Code day (a main session with a mid-conversation retry branch, three subagents, and tomorrow morning's fresh session) through four cache policies, counting recomputed prefill tokens, then prints the traffic as the tree it secretly is.

"""A fleet-wide prefix cache from scratch: the radix-tree view of your tokens.

The research lineage this lab compresses: vLLM's automatic prefix caching
hashes fixed-size blocks of the prompt so identical prefixes share KV memory;
SGLang's RadixAttention organizes those shared prefixes as a radix tree with
LRU eviction, so an entire FLEET of requests (a session, its subagents, the
retry branch, tomorrow's session) pays for each common prefix once. Anthropic's
prompt caching is the same idea sold per-request.

This lab replays one realistic Claude Code working day as ~30 requests over
four cache policies and counts the prefill tokens each policy recomputes:

  none        no cache: every request recomputes its whole prompt
  per-stream  each conversation caches only its own prefix (no sharing)
  global      one shared block store across the fleet (radix behavior)
  global+LRU  the same, under a memory cap that forces eviction

It then prints the fleet's prompts as the radix tree they really are.
Deterministic, standard library only. Run:  python3 radix_cache.py
"""

BLOCK = 128   # tokens per cache block, in the spirit of vLLM's block tables

# ---------------------------------------------------------------------------
# The workload: one day of Claude Code, as (stream, [(label, tokens), ...]).
# ---------------------------------------------------------------------------
SYSTEM = ("system+tools", 2900)
CMD    = ("CLAUDE.md", 1200)

def main_prefix(t, branch=False):
    """The main conversation's prompt at turn t (each turn adds ~900 tok)."""
    turns = [(f"main turn {k}", 900) for k in range(1, min(t, 7) + 1)]
    if t > 7:
        tag = "B" if branch else ""
        turns += [(f"main turn {k}{tag}", 900) for k in range(8, t + 1)]
    return [SYSTEM, CMD] + turns

requests = []
for t in range(1, 10):                       # main session, turns 1..9
    requests.append(("main", main_prefix(t)))
for j in (1, 2, 3):                          # three subagents mid-session
    base = [SYSTEM, CMD, (f"sub{j} task", 400)]
    for t in range(4):
        requests.append((f"sub{j}", base + [(f"sub{j} turn {k}", 600) for k in range(1, t + 1)]))
for t in range(8, 11):                       # user rewinds to turn 7, branches
    requests.append(("main", main_prefix(t, branch=True)))
for t in range(1, 7):                        # tomorrow: new session, same repo
    requests.append(("day2", [SYSTEM, CMD] + [(f"day2 turn {k}", 800) for k in range(1, t + 1)]))

def blocks_of(prompt):
    """Flatten a prompt into chained block keys; a block's key encodes the
    ENTIRE prefix before it, which is what makes prefix identity exact."""
    chain, out = "", []
    for label, tokens in prompt:
        n, rem = divmod(tokens, BLOCK)
        sizes = [BLOCK] * n + ([rem] if rem else [])
        for i, size in enumerate(sizes):
            chain += f"|{label}#{i}"
            out.append((chain, size))
    return out

# ---------------------------------------------------------------------------
# The four policies.
# ---------------------------------------------------------------------------
def run(policy, cap=None):
    stores, clock, computed, total = {}, 0, 0, 0
    for stream, prompt in requests:
        key = stream if policy == "per-stream" else "shared"
        store = stores.setdefault(key, {})
        hitting = policy != "none"
        for chain, size in blocks_of(prompt):
            clock += 1
            total += size
            if hitting and chain in store:
                store[chain] = clock          # LRU touch
            else:
                computed += size
                if policy != "none":
                    store[chain] = clock
                    hitting = False           # past first miss, all is new
        if cap:
            while len(store) > cap:           # evict least-recently-used block
                store.pop(min(store, key=store.get))
    return computed, total

print(f"=== One working day, {len(requests)} requests, four cache policies ===")
print(f"{'policy':<24}{'prefill tok':>13}{'vs none':>9}{'hit rate':>10}")
print("-" * 56)
base = None
for name, policy, cap in [("none (recompute all)", "none", None),
                          ("per-stream cache", "per-stream", None),
                          ("global radix store", "global", None),
                          ("global + LRU cap 90 blk", "global", 90)]:
    computed, total = run(policy, cap)
    base = base or computed
    print(f"{name:<24}{computed:>13,}{computed / base:>9.0%}"
          f"{1 - computed / total:>10.0%}")
print("-" * 56)

# ---------------------------------------------------------------------------
# The fleet's prompts ARE a tree. Print it (single-child chains merged).
# ---------------------------------------------------------------------------
tree = {}
for _, prompt in requests:
    node = tree
    for label, tokens in prompt:
        entry = node.setdefault((label, tokens), [0, {}])
        entry[0] += 1
        node = entry[1]

def show(node, depth=0):
    for (label, tokens), (count, kids) in node.items():
        path, tok = [label], tokens
        while len(kids) == 1:                 # merge single-child chains
            (l2, t2), (c2, k2) = next(iter(kids.items()))
            if c2 != count:
                break
            path.append(l2); tok += t2; kids = k2
        name = path[0] if len(path) == 1 else f"{path[0]} .. {path[-1]}"
        print(f"  {'| ' * depth}+ {name:<28} {tok:>6,} tok  x{count} requests")
        show(kids, depth + 1)

print("\n=== The radix view: every node is paid for once, not once per path ===")
show(tree)

print("""
Lesson: a coding agent's traffic is not a list of prompts, it is a TREE with
one hot spine (system prompt, CLAUDE.md) and many branches (turns, subagents,
retries, tomorrow). 'none' pays per path. Per-stream caching pays the spine
once per branch. A global radix store pays each node once, which is why the
subagents and the day-2 session cost almost nothing to warm up. The LRU row
is the production caveat: under memory pressure the tree forgets its least-
used branches, and the main session pays to regrow them (SGLang schedules
cache-aware to keep exactly this from thrashing).""")

Verified output:

=== One working day, 30 requests, four cache policies ===
policy                    prefill tok  vs none  hit rate
--------------------------------------------------------
none (recompute all)          220,200     100%        0%
per-stream cache               42,700      19%       81%
global radix store             26,300      12%       88%
global + LRU cap 90 blk        75,600      34%       66%
--------------------------------------------------------

=== The radix view: every node is paid for once, not once per path ===
  + system+tools .. CLAUDE.md     4,100 tok  x30 requests
  | + main turn 1                     900 tok  x12 requests
  | | + main turn 2                     900 tok  x11 requests
  | | | + main turn 3                     900 tok  x10 requests
  | | | | + main turn 4                     900 tok  x9 requests
  | | | | | + main turn 5                     900 tok  x8 requests
  | | | | | | + main turn 6                     900 tok  x7 requests
  | | | | | | | + main turn 7                     900 tok  x6 requests
  | | | | | | | | + main turn 8                     900 tok  x2 requests
  | | | | | | | | | + main turn 9                     900 tok  x1 requests
  | | | | | | | | + main turn 8B                    900 tok  x3 requests
  | | | | | | | | | + main turn 9B                    900 tok  x2 requests
  | | | | | | | | | | + main turn 10B                   900 tok  x1 requests
  | + sub1 task                       400 tok  x4 requests
  | | + sub1 turn 1                     600 tok  x3 requests
  | | | + sub1 turn 2                     600 tok  x2 requests
  | | | | + sub1 turn 3                     600 tok  x1 requests
  | + sub2 task                       400 tok  x4 requests
  | | + sub2 turn 1                     600 tok  x3 requests
  | | | + sub2 turn 2                     600 tok  x2 requests
  | | | | + sub2 turn 3                     600 tok  x1 requests
  | + sub3 task                       400 tok  x4 requests
  | | + sub3 turn 1                     600 tok  x3 requests
  | | | + sub3 turn 2                     600 tok  x2 requests
  | | | | + sub3 turn 3                     600 tok  x1 requests
  | + day2 turn 1                     800 tok  x6 requests
  | | + day2 turn 2                     800 tok  x5 requests
  | | | + day2 turn 3                     800 tok  x4 requests
  | | | | + day2 turn 4                     800 tok  x3 requests
  | | | | | + day2 turn 5                     800 tok  x2 requests
  | | | | | | + day2 turn 6                     800 tok  x1 requests

Lesson: a coding agent's traffic is not a list of prompts, it is a TREE with
one hot spine (system prompt, CLAUDE.md) and many branches (turns, subagents,
retries, tomorrow). 'none' pays per path. Per-stream caching pays the spine
once per branch. A global radix store pays each node once, which is why the
subagents and the day-2 session cost almost nothing to warm up. The LRU row
is the production caveat: under memory pressure the tree forgets its least-
used branches, and the main session pays to regrow them (SGLang schedules
cache-aware to keep exactly this from thrashing).

Reading the lab

The chained block key is the whole trick. Each block's key encodes the entire prefix before it (in the lab, by string concatenation; in vLLM, by hashing the parent's hash with the block's token ids). That is what makes "same prefix" checkable in O(1) per block, and it is why any divergence, one changed token, splits the tree at that exact point and orphans everything after it. Chapter 24's invalidation rules are this data structure viewed from the bill.
Per-stream versus global is the subagent line item. Per-stream caching (each conversation only reusing its own history) recomputes 42,700 tokens; the global store, 26,300. The whole difference is the spine: three subagents and the day-2 session each re-paying 4,100 tokens versus riding the shared trunk. Chapter 44 finds exactly this in a real transcript: a "fresh" session whose very first call reads 15,853 tokens it never paid to write.
The branch costs one node, not a re-derivation. The turn-8 retry (8B) attaches at turn 7's node. Under any prefix cache, editing or rewinding a conversation only re-pays from the divergence point; the tree makes that visually obvious.
The LRU row is the honest asterisk. Cap the store at 90 blocks and the recompute rate triples to 34%: the subagent burst evicts the main session's deep turns, and the main session pays to regrow them on its next turn. This is why RadixAttention's paper spends its pages on cache-aware scheduling, and why provider caches have TTLs: memory for other people's trees is not free.

Where the tree meets your bill: Anthropic's exact rules

The product version of everything above, verified against the live documentation in July 2026 (the numbers drift; the doc is the authority):

Prices. Cache writes cost 1.25x base input for the 5-minute TTL, 2x for the 1-hour TTL; reads and refreshes cost 0.1x. Both TTLs are generally available (cache_control: {"type": "ephemeral", "ttl": "5m" | "1h"}, default 5m); no beta header, and longer-TTL blocks must precede shorter-TTL ones.
Breakpoints and the lookback. Up to 4 breakpoints per request. A write happens only at a breakpoint (a hash of the prefix ending there); a read walks backward from each breakpoint, one block at a time, up to 20 positions, looking for a prefix hash already in the cache. That 20-block backward walk is the radix tree's longest-shared-prefix search, bounded for latency.
Minimums. The shortest cacheable prompt varies by model: 512 tokens on Claude Fable 5, 1,024 on Opus 4.8 and Sonnet 5, 2,048 on Opus 4.7, 4,096 on Opus 4.6 and Haiku 4.5. Breakpoints below the minimum are silently ignored (Chapter 6 demonstrated the failure mode).
The hierarchy. tools then system then messages; a change at any level invalidates that level and everything after it. Thinking blocks cannot carry their own breakpoints but are cached inside previous assistant turns; on Opus 4.5+ and Sonnet 4.6+ they survive added user content, where older models stripped them and broke the cache.
The refresh. Every read refreshes the entry's clock at the 0.1x price, which is why one request per TTL window keeps a session warm indefinitely, and why Chapter 44's five TTL lapses were all gaps longer than the hour.
Claude Code. The cost docs state it directly: prompt caching is applied automatically, alongside auto-compaction. The autopsy shows what "automatically" buys: the 1-hour tier, on every write.

Remember. One mental model unifies the research and the bill: your organization's prompts form one radix tree, and you pay once per node, not once per path, with two asterisks attached: nodes expire (TTL, LRU) and any upstream edit creates a new branch and orphans the old one. Every practical rule in Chapter 45's caching section is a corollary.

The reading list

If you want the primary sources, in reading order per person or group:

Who	Read first	Then	Code
Kwon & Li (Berkeley Sky)	PagedAttention (SOSP 23, 2309.06180)	vLLM's `prefix_caching` design doc	`vllm-project/vllm`
Zheng & Sheng	SGLang / RadixAttention (NeurIPS 24, 2312.07104)	their LLM-as-judge paper (2306.05685)	`sgl-project/sglang`
Tri Dao	FlashAttention (2205.14135)	FA-2, FA-3 (2307.08691, 2407.08608)	`Dao-AILab/flash-attention`
Junchen Jiang (UChicago)	CacheGen (SIGCOMM 24, 2310.07240)	CacheBlend (EuroSys 25 best paper, 2405.16444)	`LMCache/LMCache`
Gim & Zhong (Yale)	Prompt Cache (MLSys 24, 2311.04934)		`yale-sys/prompt-cache`
Song Han's lab (MIT)	StreamingLLM (ICLR 24, 2309.17453)	SnapKV, H2O, KIVI for the frontier	`mit-han-lab/streaming-llm`
Moonshot + Tsinghua	Mooncake (FAST 25 best paper, 2407.00079)		`kvcache-ai/Mooncake`
Shazeer / Ainslie / DeepSeek	MQA (1911.02150)	GQA (2305.13245), DeepSeek-V2 for MLA (2405.04434)	in every modern model

Takeaways

The KV cache is half a megabyte per token for a classic 7B in fp16; every branch of the lineage attacks that number: architecture shrinks it (MQA, GQA, MLA at 93.3%), kernels stop wasting traffic on it (FlashAttention), serving pages it (PagedAttention), trees share it (RadixAttention), networks ship it (CacheGen, CacheBlend, LMCache, Mooncake), and the lossy branch throws parts away (StreamingLLM, H2O, SnapKV, KIVI).
The names to know: Kwon and Li (vLLM), Zheng and Sheng (SGLang, and the judge paper), Dao (FlashAttention), Jiang's UChicago group (the cache-as-data line), Gim and Zhong (Prompt Cache), Han's MIT lab (sinks), Shazeer to DeepSeek (architecture).
The lab's four-policy replay: recompute-all 100%, per-stream 19%, global radix 12%, LRU-capped 34%. The fleet's prompts are a tree; you pay per node, and eviction plus upstream edits are the only things that make you pay twice.
Anthropic's product encodes the same tree: 4 breakpoints, a 20-block backward hash walk, tools-system-messages invalidation, per-model minimums (512 on Fable 5, 1,024 on Opus 4.8), 0.1x refresh-on-read, and 2x for the 1-hour tier Claude Code buys automatically.
Exact reuse (prefix caching) is a billing optimization; position-independent and lossy reuse are modeling decisions with a quality bill. Know which family a tool is from before trusting its ratio.

👉 The lineage gives you the ideas and the lab gives you the tree; what neither gives you is your numbers. The next chapter opens the transcripts on this machine and autopsies a real 272-call session: the 97.5% hit rate, the six invalidations, and the twenty dollars that walking away cost. Continue to The live cache autopsy.

Context Engineering in Depth