# Learning note — KV cache & prefix reuse

Companion to [`sub-apps/sim-kv-cache.html`](../sub-apps/sim-kv-cache.html). This note holds the
evidence and the reasoning path; the sim holds the reflexes. Calibrated to the harness-research corpus register — every
arXiv ID below is registered in `harness-research/ledger/ledger.json`.

## The question that generates everything

**What exactly does the provider key its cache on?**

Answer: an *exact token-prefix match*. During prefill the model computes attention keys/values (K/V) for every
token of your prompt, layer by layer. If the next request starts with the identical token sequence, those K/V
tensors are reused and prefill is skipped for the shared span — that is the whole mechanism. Everything else in
this note is a consequence of the answer:

- reuse is **all-or-nothing at the first differing token** (no partial credit past the divergence point),
- the key is **bytes, not meaning** — a paraphrase misses as hard as a typo,
- anything that changes the rendered prefix — a timestamp, a username, a random ID, a reordered list, a
  compaction, a model switch — is a key mutation.

The sim's fingerprint chip exists to make the key visible: watch it turn amber the moment one character
diverges, before you even send.

This is the *cross-request* story (skip prefill when the next call starts with the same bytes). The
*in-request* story — why that cache exists, why it grows with T, why decode is bandwidth-bound — is
[why KV grows](kv-growth.md). The *quality* story — why those same extra tokens make recall die — is
[why recall dies](context-rot.md). Prefix reuse does not shrink this request's resident KV.
Mooncake (`2407.00079`) is the same reuse tax at cluster scale (prefill/decode split + DRAM/SSD
pool). MLA / DSA / KDA are look / thin / store — [look vs store](look-vs-store.md).

```
request N   [ SYS ][ context ][ user msg ]        ──prefill──▶  K/V cached
request N+1 [ SYS ][ context ][ user msg' ]       ──▶ identical prefix: K/V reused, prefill skips the span
request N+2 [ SYS'][ context ][ user msg ]        ──▶ one char at position ~4: cache DEAD, full prefill again
```

## Evidence base

| Ledger id | Finding | Why it matters for the mental model |
|---|---|---|
| `2608.00101` (Copilot traces) | Production scale (761M calls): intra-turn KV hit rate ~90%, collapsing to ~55% across turn boundaries; model switches and compaction are drastic invalidators | The cliff is real and measured — reuse decays exactly where prefixes stop being byte-identical |
| `2407.00079` (Mooncake) | Kimi serving: KV-centric disagg + DRAM/SSD pool; up to 525% throughput, +75% real requests | Same key (reuse prefill), bigger substrate. Still does not shrink this request’s T |
| `2607.29678` (TokTier) | Once prefix-hit rate nears 0.99, the *front end* (tokenization) becomes the TTFT bottleneck (10%→64%); exact incremental re-tokenization cuts vLLM TTFT 16–34% | Cache-stable prefixes work so well the next bottleneck moves elsewhere; also: even the key-encoding step must be exact and stateful |
| `2608.19662` (ReCache) | Tool schemas recur but in different orders, so standard prefix caching never hits; composition-invariant KV blocks fix it architecturally: 3.655× TTFT at parity accuracy | Order-dependence is the failure mode even when *content* is stable; the ordering contract is the fix |
| `2608.15584` (GraniKV) | Shared prefixes want contiguous storage, private suffixes want token-granular paging; splitting them: 2.16× throughput where uniform schemes collapse | The prefix/suffix split is physical, not stylistic — it is worth engineering structure around |
| `2608.19677` (CacheRoute) | Planned prefix-affinity routing lifts hit rate 64→93% and 2.3× QPS at p99 SLO — with published workloads where affinity recovers too little | Reuse is also a *placement* decision; and it fails measurably on low-reuse traffic |
| `2607.28069` (SemPIC) | Learned position-independent document KVs reach F1 0.60 vs 0.62 for full recomputation | Beyond-exact-prefix reuse is not yet free — exactness is still the deployable contract |
| `2608.15939` (Aborted but Not Forgotten) | KV retained after branch aborts leaks attended state across 7 model families | Reuse has *correctness* obligations, not just speed ones — a hazard for any agentic branch-and-resume |
| `2608.15127` (AgentSysBench) | Tool-result caching removed 35.2% of redundant searches (−19.3% search latency) | The same key-reuse discipline pays at the application layer, not just the K/V layer |

## The dominant direction: discipline, not cleverness

The window's converged finding (harness-research area 09, direction 1): cache reuse is bought by an
**ordering contract between client and server** — shared material arrives byte-identically and first; volatile
material arrives last; determinism holds everywhere upstream (stable sorts, no timestamps inside cached
regions, frozen schema ordering). ReCache showed content stability is not enough (order kills it); Copilot
showed session stability is not enough (compaction and model switches kill it); TokTier showed that when you
get all of it right, the win is large enough that tokenization becomes your problem instead.

This is why production guidance leads with **cache-stable rendering**, and why it is a *rendering* rule rather
than a caching rule: the cache is the provider's; the bytes are yours.

## The invalidation cliff, priced

The sim models a hit as ~200 ms of TTFT saved. Real deployments price the cliff in three currencies:

1. **Latency** — full re-prefill on every invalidated request (TokTier's front-end numbers show how large
   prefill-adjacent costs loom at scale).
2. **Cost** — prefill tokens are billed; re-prefilling the same prefix repeatedly is paying repeatedly for
   bytes you already sent.
3. **Cache occupancy** — provider prefix caches are finite; mutated keys evict useful ones (CacheRoute's
   whole job is reconciling this with load balancing).

The Copilot cliff (90%→55%) is the honest baseline: even a disciplined code assistant loses ~35 points of hit
rate at turn boundaries. The lesson is not "hits are guaranteed"; it is "the bytes you control are the hit rate
you get."

## Contested points

- **How far past exact-prefix can reuse go?** SemPIC's position-independent KVs land measurably short of
  recomputation; ReCache's composition-invariant blocks win *by restructuring what is cached*, not by relaxing
  matching. Exactness with better layout currently beats fuzziness.
- **Is retained KV safe to reuse after a branch?** `2608.15939` says no without a rollback-consistency
  guarantee (state leakage across 7 model families). Treat agentic branch-resume + KV retention as a hazard
  pair until a deep-read says otherwise.
- **Mooncake vs GPU prefix cache.** Same currency (skip recompute). Mooncake
  moves the KV object onto DRAM/SSD across prefill/decode clusters. The key is
  still exact. Layout/byte-stability still decide whether the pool hits.
- **Who owns stability?** TokTier had to *prove* tokenization exactness with differential campaigns
  (1.5×10¹⁰ split checks, zero divergence) — implying no layer can assume another layer preserved the prefix.
  Conformance testing of rendered prompts (longest-common-prefix fraction across consecutive requests) is an
  open gap in the literature (area 09, unpicked #2).

## Direction of thinking — the transferable moves

1. **When a system reuses work, find the exact key it reuses on.** Not the approximate key, not the intent of
   the key — the bytes.
2. **Then stop mutating the key.** The fix is almost never "better caching"; it is determinism upstream of the
   cache: stable serialization, volatile content last, no hidden entropy (timestamps, IDs, ordering).
3. **Measure the hit rate; don't argue about it.** LCP fraction across consecutive requests is computable
   anywhere; the Copilot cliff shows intuition about "mostly stable" is unreliable.
4. **Reuse is a correctness surface too.** Anything reused across contexts (KV, tool results, memoized
   decisions) needs an invalidation story and, for stateful reuse, a rollback story.

## Open questions

- Byte-stability conformance linting for harness-rendered prompts — genuinely absent in the window (high-confidence gap).
- Compaction *scheduling* as a first-class cache event: when to compact, priced against the KV it destroys (med confidence).
- Position-independent or semantic KV reuse that actually reaches recomputation parity — SemPIC is a marker, not a mechanism.

## Try it

Open [the sim](../sub-apps/sim-kv-cache.html): send twice (cold → hit), change the system prompt
(miss + old/new prefix diff), then hand-edit a single character and watch the fingerprint flip amber *before*
the request fires. The stats bar is the experiment: keep the prompt stable for ten sends, then mutate it once
and count.