m02 — The KV Cache Tier (Prefix Caching at Fleet Scale)

A fully worked design. Reusing computed KV across requests, across replicas, and across time. The design is small and the arithmetic is unusually decisive: one calculation tells you which storage tiers are worth building and which are strictly worse than doing the work again.

Very few candidates do that calculation. Doing it is most of the value of this design.

Run it first. A companion page builds this as numbered, independently runnable blocks: what a contiguous allocator wastes, paging and prefix sharing, and the fetch-versus-recompute break-even derived: Hands-On — Paged KV, Block by Block. Every number on it was produced by running the code.

Table of Contents

• The Prompt
• 1. Requirements and Scope
• 2. Scale Numbers
• 3. API Surface
• 4. Data Model
• 5. High-Level Architecture
• 6. Deep Dive A: The Break-Even Bandwidth
• 7. Deep Dive B: Cache Keys, or How to Serve Wrong Answers Fast
• 8. Failure and Recovery
• 9. Bottlenecks and Evolution
• 10. Tradeoffs Explicitly Rejected
• The Hostile Critique
• The Revision
• References

The Prompt

"Our customers send the same system prompts and the same document context over and over. We're re-running prefill for all of it. Design a cache so we stop."

The word "cache" is doing a lot of hidden work here and you should unpack it in the first minute. A cache trades storage and bandwidth for compute. That trade is normally obviously good, because storage is cheap and compute is expensive.

Here it is not obviously good, because the thing being cached is enormous. KV for a 2,000-token prefix on a 70B model is 625 MiB — for one prefix, for one request shape. Ten thousand of them is 6 TiB. And retrieving 625 MiB takes real time, which has to be compared against the ~71 ms it would take to just recompute it.

So the opening question is not "how do I cache this", it is "at what bandwidth does caching stop being worth it". That question has a clean answer, it is deep dive A, and it decides the architecture.

1. Requirements and Scope

Clarifying questions asked

"What is the reuse actually like — same tenant, or across tenants?" Assumed: overwhelmingly within a tenant — one customer's application sends the same template thousands of times a day. Cross-tenant reuse exists (public model system prompts) but is small, and as m01's R3 establishes, sharing across tenants is a timing side channel. So: tenant-scoped by default.

"Are we optimizing TTFT or cost?" Both, and they point the same way for a hit and opposite ways for a miss — a cache lookup that misses adds latency and produces nothing. Assumed: TTFT is the SLO, cost is the reason for the project. That ordering means a miss must be cheap, which constrains lookup to something we can do in single-digit milliseconds.

"What's the prefix length distribution?" The number that decides everything. Assumed: system prompts 200–2,000 tokens (high reuse), RAG document context 2,000–20,000 (moderate reuse, per-document), conversation history 500–8,000 (reused only by the same conversation's next turn). Three populations with completely different reuse patterns, and one cache policy cannot serve all three well.

"Is a cache hit allowed to change the output?" No — and this is the requirement people forget. A cached KV must be bit-identical to what prefill would have produced, or the same prompt returns different answers depending on cache state. That is a correctness requirement, it constrains the cache key hard, and it is deep dive B.

Functional

1. Look up the longest cached prefix of an incoming token sequence.
2. Materialize its KV into the serving replica's HBM before decode.
3. Store the KV of newly computed prefixes worth keeping.
4. Evict under memory pressure without breaking in-flight requests.
5. Invalidate on anything that changes what prefill would produce.

Non-functional

Explicitly out of scope

• The KV cache within a single decode (that is PagedAttention — WARMUP §4.3).
• Semantic caching (returning a stored answer for a similar question). Different problem, different risk profile, §10.
• Cross-region replication. Prefix caches are cheap to rebuild; replicating them is not worth it.

2. Scale Numbers

KV per token, 70B with GQA-8, FP16:

2 (K and V) × 80 layers × 8 kv_heads × 128 head_dim × 2 bytes = 327,680 B = 320 KiB / token

320 KiB per token. Internalize this number — it is the reason this design is hard.

Working-set size. Suppose 2,000 tenants each with ~5 distinct templates averaging 1,500 tokens:

2,000 × 5 × 1,500 tokens × 320 KiB = 4.4 TiB

4.4 TiB against a replica's ~172 GiB of HBM — and that HBM is already needed for in-flight requests' KV. So the cache cannot live in HBM alone. That forces a tier, and the tier choice is decided by arithmetic, not preference (deep dive A).

Hit rate is the number you must refuse to guess. State the range and its drivers:

"It depends on the workload, here is what it depends on, and here is how I would measure it before promising a number" is a strong answer. A confident "about 70%" is a weak one, and the follow-up will be "based on what?"

Value of a hit. At 60% hit rate on 1,500-token prefixes, at 83 rps (m01 §2):

prefill avoided = 83 × 0.6 × 1,500 = 74,700 tok/s
                = 74,700 / 28,000 tok/s per replica = 2.7 replicas of compute

Against a fleet of ~11 decode replicas, that is the entire prefill load and then some — recall prefill was 21% of the fleet. So a good hit rate does not shave a few percent; it can remove prefill as a capacity concern. That is why this is worth a design and not a config flag.

3. API Surface

The cache is a library inside the replica plus a shared store, not a network service on the hot path. That is the same shape as d03 and for the same reason: a network hop on the critical path costs more than the thing it coordinates.

# In the replica, before scheduling prefill:
hit = cache.lookup(key_prefix, token_ids)
#   -> Hit(matched_tokens: int, blocks: list[BlockRef], tier: str)
#   -> Miss()

cache.materialize(hit)          # ensure blocks are in HBM; may copy from host/remote
cache.store(key_prefix, token_ids, blocks, policy)   # after prefill, async

# Control plane
GET  /cache/stats?tenant=...    -> hit_rate, bytes, evictions, tier_breakdown
POST /cache/invalidate          {model_version} -> 202

lookup returns matched_tokens, not a boolean. Prefix caching is a partial match: a request sharing the first 1,400 tokens of a 1,500-token cached prefix should get 1,400 tokens free and prefill only 100. A boolean API throws that away and makes the cache far less useful than it should be — this is a real API-design decision, not a detail.

store takes a policy, because the three populations from §1 want different treatment:

Conversation history is the interesting case. It has near-100% reuse for ~30 seconds and 0% after. An LRU treats it like everything else and fills the cache with dead conversations. A TTL tied to the session, not to access recency, is the correct policy — and noticing that different populations need different policies is worth more than any single policy choice.

4. Data Model

The index is a radix tree over token blocks, not a flat hash map. Reason: prefix matching is the operation, and a hash map can only answer "do you have exactly this?"

Block = 16 tokens (aligned; matches the paged-attention block size)

radix tree, per (tenant, model_version):
    root
     ├── [sys prompt blocks 0..31] ── ref=1400, last=t0
     │      ├── [user template A]  ── ref=200
     │      └── [user template B]  ── ref=140
     └── [other prefix] ...

BlockMeta = (block_hash, tier, location, ref_count, last_access, bytes)

Block-aligned matching, and the alignment matters. A prefix match must end on a block boundary, because KV is allocated and copied in blocks. A 1,507-token match is truncated to 1,504 (94 blocks). You lose up to 15 tokens per match — negligible, and worth stating so the interviewer knows you have thought about the granularity rather than assuming token-level matching that the memory system cannot express.

ref_count is not an optimization, it is the eviction-safety mechanism. Blocks referenced by an in-flight request must not be evicted; a request whose prefix blocks vanish mid-decode produces garbage. Ref-counted, released on request completion.

Three tiers, one location field:

That last row is deep dive A, and it is the finding.

5. High-Level Architecture

                  request (token_ids)
                        │
              ┌─────────▼──────────┐
              │  REPLICA scheduler │
              └─────────┬──────────┘
                        │ lookup(tenant, model_ver, tokens)
              ┌─────────▼──────────────────────────────┐
              │ LOCAL RADIX INDEX  (in-process, ~1 us) │
              │  covers T0 + T1 on this host            │
              └────┬──────────────────────────┬─────────┘
                   │ local hit                │ local miss
                   │                          │
        ┌──────────▼─────────┐    ┌───────────▼──────────────┐
        │ T0 HBM   0.2 ms    │    │ GLOBAL INDEX (Redis)     │
        │ T1 DRAM  10 ms     │    │  hash -> which hosts     │
        │  -> DMA into HBM   │    │  ~1 ms                    │
        └────────────────────┘    └───────────┬──────────────┘
                                              │ remote hit
                                  ┌───────────▼──────────────┐
                                  │ T2 peer host over RDMA   │
                                  │ 26 ms for 625 MiB        │
                                  └───────────┬──────────────┘
                                              │ miss everywhere
                                  ┌───────────▼──────────────┐
                                  │ PREFILL (71 ms) + store  │
                                  └──────────────────────────┘

Five decisions:

1. The local index is in-process and covers only local tiers. A lookup that hits locally never touches the network. Since most reuse is a tenant hitting the same replica repeatedly (routing is sticky-ish by tenant, §9), the local hit rate carries most of the value.

2. The global index is a hint, not a source of truth. It maps block-hash → hosts, refreshed asynchronously. It can be stale in both directions: a listed host may have evicted (fall through to prefill, costing 1 ms) or an unlisted host may have it (a missed opportunity, costing nothing). Neither staleness direction is a correctness problem, only a performance one — which is exactly the property that lets the global index be cheap and eventually consistent.

3. No NVMe tier, on the arithmetic in deep dive A. This is the design's most load-bearing negative decision and the one to lead with.

4. Store is asynchronous and best-effort. Writing to the cache must never delay the response. If the store queue is full, drop the write — a lost cache entry costs one future recompute.

5. The unit of transfer is a block run, not a block. 94 blocks moved as one DMA rather than 94 transfers; at 625 MiB the per-transfer overhead would otherwise dominate. Obvious once stated, easy to get wrong in implementation, and mentioning it signals you have moved data at this size before.

6. Deep Dive A: The Break-Even Bandwidth

The question

A cache hit replaces computing the KV with fetching it. That is only a win if fetching is faster. So:

At what bandwidth does fetching cached KV become slower than recomputing it?

The derivation

Per token of prefix:

bytes to fetch   = kv_bytes_per_token                      = 320 KiB      (70B, GQA-8, FP16)
FLOPs to recompute = 2N                                    = 140 GFLOP    (70B)
time to recompute  = 2N / aggregate_FLOPS

Fetching wins when bytes / BW < 2N / FLOPS, so:

\[ \text{BW}_{\text{break-even}} = \frac{\text{kv_bytes_per_token} \times \text{FLOPS}}{2N} \]

Note what is absent: the prefix length. It cancels. The break-even bandwidth is a property of the model and the hardware, not of the request. That is the elegant part and it is worth saying out loud — it means you can decide the tiering once, statically, rather than per request.

The numbers

70B, GQA-8, FP16 KV, H100 at 989.5 TFLOP/s dense per GPU:

Now compare against real media, and the tiering decides itself:

A local-NVMe KV cache tier is slower than not having one. For a 2,000-token prefix: 94 ms to read from NVMe versus 71 ms to recompute from scratch on the GPUs you already own. You would be adding a storage tier, an eviction policy, a failure mode, and operational surface to make the system slower.

This is the finding, it is counterintuitive (disk caches are almost always a win), and it is counterintuitive precisely because KV is unusually large relative to the compute that produces it. Say that — it shows you know why the usual intuition fails here rather than having memorized an exception.

The three ways the answer changes

The break-even moves, and knowing which direction each lever pushes is the follow-up:

1. FP8 KV halves the bytes → break-even halves (TP4: 9.3 → 4.6 GB/s). NVMe at 7 GB/s becomes viable. One quantization decision flips an entire architectural conclusion.
2. More tensor parallelism raises aggregate FLOPS → break-even rises. At TP8 you need 18.5 GB/s, and 200 GbE at 25 GB/s is only 1.35× clear — uncomfortably close. Bigger models with more GPUs make remote KV caching progressively worse, which is the opposite of the usual intuition that more hardware makes more things affordable.
3. MLA-style architectures (DeepSeek-V2/V3) compress KV by an order of magnitude. That drops the break-even by the same factor and makes every tier viable. The architecture of the model decides the architecture of your cache — a good sentence to have.

What to actually say in the round

"Before choosing tiers I want the break-even bandwidth. KV is 320 KiB per token; recompute is 2N FLOPs per token, so on TP4 H100 that's 35 microseconds — break-even is about 9 GB/s, and it's independent of prefix length. DRAM and RDMA clear it comfortably; NVMe at 7 GB/s does not, so I won't build a disk tier. If we move to FP8 KV that halves and I'd revisit it."

Sixty seconds, one derivation, and it eliminates a component. That is what "identify the hard part and size it" looks like in this round.

7. Deep Dive B: Cache Keys, or How to Serve Wrong Answers Fast

The failure mode

A cache hit must produce exactly the KV that prefill would have produced. If it does not, the model continues from subtly wrong state and generates a plausible, different, wrong answer — with no error, no alarm, and no way for the user to tell.

This is the worst class of bug in the system: silent, non-deterministic (depends on cache state), and invisible to every health check. It deserves the deep dive more than the performance question does, and choosing to spend a deep dive on it is itself a signal.

Everything the KV depends on

The naive key is hash(token_ids). Here is what else prefill depends on:

The position row is the one that catches people. Prefix caching only works for a prefix — tokens starting at position 0. You cannot cache "the middle chunk that appears in many documents" and splice it in at an arbitrary offset, because RoPE has already rotated K by the position. This is why the cache is a prefix cache and not a substring cache, and it is a question interviewers like precisely because the naive answer ("cache any repeated chunk") sounds obviously right.

The key

CacheKey = (
    tenant_id,           # isolation (security, not correctness)
    model_id,
    weights_version,     # exact artifact digest, not a tag like "latest"
    tp_degree,
    kv_dtype,
    rope_config_hash,
    attn_impl_id,
)
# Block hashes chain, so a block's identity includes all its ancestors:
block_hash[0] = H(CacheKey, tokens[0:16])
block_hash[i] = H(block_hash[i-1], tokens[16i:16i+16])

The chained hash is what makes prefix matching correct. Block i's identity depends on every preceding block, so two sequences that diverge at block 3 cannot share block 4 even if its 16 tokens are identical. Without chaining, prefix matching would happily splice blocks from unrelated sequences and produce exactly the silent-corruption failure above.

Chaining also gives invalidation for free: change any component of CacheKey and every block hash changes, so a model rollout does not need an invalidation sweep — the new version simply finds an empty cache. Old entries age out by LRU.

The rollout consequence, stated plainly

A weights rollout cold-starts the cache. Hit rate goes to zero and prefill load jumps by whatever the cache was absorbing — from §2, potentially the equivalent of ~2.7 replicas appearing instantly.

So the rollout is a capacity event, not just a deployment, and the design must say so:

• Roll out gradually (canary → 10% → 50% → 100%) so the cache refills incrementally.
• Provision for the cold-cache prefill load during the rollout window, or the rollout itself causes the TTFT breach.
• Alarm on hit rate, and treat "hit rate did not recover within 30 minutes" as a rollback signal — it usually means a key component changed that you did not intend to change.

"The cache makes deploys a capacity event" is the kind of second-order consequence that distinguishes a senior answer from a correct one.

Determinism, and an honest limit

Even with a perfect key, GPU matmul is not bit-deterministic across different batch shapes — reduction order changes with batch size. So the KV computed for a prompt in a batch of 4 may differ in the last bits from the same prompt in a batch of 60.

Consequence: a cached prefix can be slightly different from a freshly computed one, which means a cache hit can change the output for a prompt near a sampling boundary.

The honest position — and this is a case where the right answer is to bound the problem rather than claim to have solved it:

• This is already true without caching (the same prompt in different batches already differs), so caching does not introduce non-determinism, it only adds one more source.
• Customers who need reproducibility need temperature=0 and a seed and an acknowledgement that bit-exact reproducibility across a fleet is not offered. Most providers document exactly this.
• If bit-exact reproducibility were a hard requirement, it forces deterministic kernels and fixed batch shapes, which costs a large fraction of throughput. That is a product decision with a price tag, and the design's job is to state the price, not to pretend the choice is free.

8. Failure and Recovery

Every cache failure degrades to "recompute", and that is the property that makes this design safe. Say it explicitly, because it is the reason the cache can be aggressive elsewhere: there is no failure mode where the cache returns wrong data as long as the key is right — only failures where it returns no data. A cache whose worst case is the uncached system is one you can deploy without a fallback plan.

On thrash — the interesting failure. When the working set exceeds capacity, LRU degrades to nearly 0% hit rate while doing 100% of the eviction work: every entry is evicted before its second use. The system is now paying storage, bandwidth, and index cost for negative value.

Detect it as evictions_per_second > stores_per_second × 0.9 sustained, and respond by becoming more selective, not less:

# Admission policy: only cache what has already proven it will be reused.
# Track candidate prefixes in a small counting sketch; store only on the
# SECOND sighting. One-shot prefixes never enter the cache at all.
if sketch.count(block_hash) >= 2:
    cache.store(...)

This is TinyLFU's insight and it applies exactly: under pressure, the scarce resource is not space but the right to occupy it. A one-hit-wonder that evicts a hot system prompt is a net loss, and LRU cannot tell the difference. Cost: a two-sighting delay before anything is cached, which is irrelevant for the reused prefixes that matter.

9. Bottlenecks and Evolution

Now: the bottleneck is HBM capacity for T0, and it is in direct competition with in-flight requests' KV — the cache and the workload consume the same bytes. That tension is the defining property of this design and it is worth naming: this is not a cache in front of a resource, it is a cache made of the resource.

Interventions in order:

1. Tenant-affinity routing. If a tenant's requests land on the same 2–3 replicas, local hit rate rises sharply and T2 traffic falls. The cost is worse load balance and a hot-tenant problem, so it is affinity with a headroom escape hatch: prefer the affine replicas until their occupancy exceeds a threshold, then spill. This is consistent hashing with bounded loads, and it is the highest-leverage single change available here.
2. FP8 KV cache. Halves every size and halves the break-even bandwidth (§6). Doubles effective cache capacity and makes cheaper tiers viable. Blocked on quality measurement (m05).
3. Cache-aware routing. Route to the replica that already holds the longest matching prefix, rather than to the emptiest. This inverts m01's routing rule and the conflict must be resolved explicitly: route on cache locality when the saving exceeds the queueing cost. Concretely, prefer a warmer replica if matched_tokens × 35 µs > extra_queue_delay. Numbers decide, not preference.
4. Deduplicate across tenants for platform-owned prefixes only — our own system preambles, which leak nothing (§7, m01 R3).
5. Compressed KV (product quantization, low-rank). Speculative; the decompression cost eats into exactly the budget from §6. Only worth it if decompression is faster than 9.3 GB/s of equivalent recompute, which is the same break-even question in a different costume — and noticing that it is the same question is the point.

10. Tradeoffs Explicitly Rejected

Rejected: an NVMe tier. §6. At 7 GB/s it is below the 9.3 GB/s break-even — slower than recomputing. Revisit only with FP8 KV, which halves the break-even to 4.6 GB/s.

Rejected: object storage for "cold" KV. ~1 GB/s. Nine times worse than the NVMe idea that was already rejected. The temptation is that S3 is cheap per byte; the flaw is that the currency here is latency, not bytes.

Rejected: a dedicated network KV-cache service (all replicas fetch from a central store). It turns every prefill into a network dependency, adds a failure domain, and the arithmetic says local DRAM is 2.6× faster than the network at the same capacity scale. Peer-to-peer with a hint index gets most of the benefit at none of the coupling.

Rejected: token-level (non-block-aligned) matching. Gains up to 15 tokens per match — about 1% of a 1,500-token prefix — and costs the ability to move KV in aligned blocks, which is the entire memory-management design. Wrong trade by two orders of magnitude.

Rejected: semantic caching (embed the prompt; on a near-match return the stored answer). Different system entirely, and the risk profile is not comparable: prefix caching is provably output-identical, semantic caching returns an answer to a question that was not asked. There are products where that is acceptable (FAQ deflection). An LLM API is not one of them, and conflating the two in this round is a serious error.

Rejected: caching across model versions with "compatible" weights. There is no such thing as compatibly different weights for this purpose. Any weight change changes every K and V.

Rejected: keying on the prompt string rather than token IDs. Two different strings can tokenize identically and one string can tokenize differently across tokenizer versions. Token IDs are the model's actual input; the string is an encoding of it. Key on what the model sees.

The Hostile Critique

C1. "Your break-even math compares fetch bandwidth to recompute time. But a cache hit doesn't just save time, it frees the GPU to do other work. During those 71 ms of recompute the GPU can't decode for anyone else. Your calculation treats GPU-seconds and PCIe-seconds as interchangeable. They cost different amounts. Redo it."

C2. "T1 is host DRAM, ~500 GiB per host. Your working set is 4.4 TiB across the fleet. With tenant-affinity routing off, each host sees a random slice of that — so what fraction of 4.4 TiB does one host's 500 GiB actually cover, and what does that do to your hit rate?"

C3. "You store asynchronously and 'drop the write if the queue is full'. Under load the queue is always full — that's when you're prefilling most. So your cache stops accepting writes exactly when the workload that would populate it is heaviest. When does it ever warm up?"

C4. "Conversation history gets session_ttl because it's 'reused exactly once'. An agent loop re-sends the whole transcript every step, twenty steps deep. That's your 70–95% hit-rate case. Is that history, or is it a system prompt? Which policy does it get, and who decides?"

C5. "The chained block hash includes CacheKey, which includes tp_degree. You run TP4 for 70B and TP8 for the frontier model, and you're planning to move 70B to TP8 for latency. On that day, what fraction of your cache survives, and what did you just do to the fleet?"

C6. "You reject NVMe on bandwidth. But you compare NVMe bandwidth to prefill on an idle GPU. At 90% KV occupancy your GPUs aren't idle — the prefill queues behind other work. So the real recompute latency isn't 71 ms, it's 71 ms plus queueing. Does NVMe come back?"

The Revision

R1 — The comparison must be in cost, not just latency (answers C1)

The critique is right that the units were wrong, and correcting it strengthens the conclusion rather than reversing it — which is worth noticing, because it means the original answer was right for an incomplete reason.

Two distinct questions were collapsed into one:

• Latency: does the user wait less? Compare fetch time to recompute time. (What §6 did.)
• Capacity: does the fleet serve more? Compare GPU-seconds saved to the cost of the fetch path.

The capacity comparison:

recompute 2,000 tokens on TP4 = 71 ms x 4 GPUs = 284 GPU-ms  @ $2.50/hr = $0.000197
fetch 625 MiB over PCIe        = 10 ms of DMA, ~0 GPU compute (DMA engine, async)

The fetch consumes almost no GPU time at all — the copy runs on the DMA engine and overlaps with compute for other requests. So on the capacity axis the cache is worth far more than the latency comparison suggests: it does not just make one request faster, it hands 284 GPU-ms back to the fleet.

Change: the tiering rule becomes two rules, and they can disagree.

Tier is worth building if EITHER:
  (a) fetch_latency < recompute_latency          [helps TTFT]
  (b) fetch_gpu_cost < recompute_gpu_cost        [helps capacity]

Under (b), NVMe is not obviously dead: 94 ms of NVMe read costs ~0 GPU-seconds versus 284 GPU-ms of recompute. So for latency-insensitive traffic — the batch API from m01 §9 — an NVMe tier is a genuine capacity win even though it is a latency loss.

Revised conclusion, stated precisely: no NVMe tier for the interactive fleet; an NVMe tier is defensible for the batch fleet. That is a better answer than the original, and it came from the critique noticing that GPU-seconds and PCIe-seconds are not the same currency.

Cost: two tiering policies to operate instead of one. Worth it only if the batch fleet is large enough to matter — so this is a "revisit when batch exceeds ~20% of volume" item, not a build-now item, and the design should say so rather than leaving it as an option.

R2 — Affinity is not optional, it is what makes the cache work at all (answers C2)

The critique's arithmetic is correct and it invalidates the tiering as originally presented. Without affinity, one host's 500 GiB covers 500 GiB / 4.4 TiB ≈ 11% of the working set. If requests arrive uniformly, the local hit rate is bounded by roughly that — call it 11%, against the 60% the design's value case assumed. The value case was off by 5×.

Change: tenant affinity moves from §9 "future improvement" to a required component.

# Rendezvous hash the tenant onto a small home set, with a headroom escape.
homes = rendezvous_top_k(tenant_id, replicas, k=3)
for r in homes:
    if r.kv_occupancy < 0.85:
        return r
return least_loaded(replicas)      # spill; accept the cache miss

With k=3 and 2,000 tenants over 44 replicas, each replica is home to ~136 tenants whose combined working set is 136 × 5 × 1,500 × 320 KiB ≈ 311 GiB — which fits in 500 GiB of host DRAM. The cache goes from covering 11% of a random slice to covering ~100% of a relevant slice.

That is the whole design, and it was buried in a list. The correction: the cache does not work without routing that makes it work. State affinity as a first-class requirement in §1, not as an optimization.

Cost: worse load balance (a hot tenant loads its home replicas), a rebalancing problem when replicas join or leave, and a spill path whose hit rate is near zero. The occupancy escape hatch bounds the first; rendezvous hashing bounds the second (only 1/n of tenants move per membership change); the third is accepted and measured as spill_rate.

R3 — Store admission must be prioritized, not dropped (answers C3)

The critique identifies a genuine self-defeating loop: the cache refuses writes exactly when prefill volume — the source of cache entries — is highest, so under sustained load it never warms.

Change: the store queue becomes a priority queue with the admission filter applied at enqueue, not a bounded FIFO with tail-drop.

def maybe_store(prefix):
    if sketch.count(prefix.head_hash) < 2:
        return                       # one-shot: never worth a queue slot (§8)
    priority = prefix.matched_len * sketch.count(prefix.head_hash)
    store_q.push(priority, prefix)   # evicts the LOWEST-priority entry when full

Two properties, both necessary:

1. Tail-drop becomes value-drop. A full queue drops the least valuable pending write rather than the newest one. A hot 2,000-token system prompt is never dropped in favour of a one-off.
2. The filter runs before the queue, not after. One-shot prefixes never consume a slot at all, which is where most of the pressure came from.

And the deeper correction the critique implies: dropping cache writes under load is backwards. Under load the fleet needs the cache more, so the correct response to pressure is to become more selective, not to stop. The original design's "drop the write" was the reflex answer for an ordinary async queue and the wrong one for this queue.

Cost: the sketch (a small count-min sketch, a few MB) and priority-queue overhead on a path that was O(1). Both are off the request path.

R4 — Policy must be inferred from observed reuse, not declared by callers (answers C4)

The critique exposes a category error in §3: I invented three populations and assigned each a policy, but the caller cannot reliably say which population a prefix belongs to — and the agent-loop case, which is the single most valuable one, does not fit any of the three. An agent transcript is "history" by origin and "system prompt" by reuse pattern.

Change: delete the caller-supplied policy. Infer it.

# Two observed quantities decide everything; no caller declaration.
reuse_count = sketch.count(head_hash)          # how often it has been seen
reuse_recency = now - last_hit                 # how recently

if reuse_count >= HOT and bytes < PIN_MAX:     # small + frequently reused
    tier = T0_PINNED                           #   -> the "system prompt" case
elif reuse_count >= 2:
    tier = T1                                  #   -> the "reused context" case
else:
    tier = DO_NOT_STORE                        #   -> one-shot
# Eviction is TinyLFU-style: frequency-aware, so a 20-step agent transcript
# earns promotion by step 3 without anyone declaring it special.

An agent loop's transcript is re-sent every step, so by the third step its count crosses the threshold and it is treated as hot — automatically, and for the right reason. A dead conversation stops being hit and ages out by frequency decay.

Cost: the first two uses of any prefix are not cached, so a 20-step agent loop pays full prefill twice. Against 18 hits, negligible.

The general lesson worth stating: a policy the caller must declare is a policy that will be declared wrong. Prefer inferring from behaviour you can observe, especially when the important case is one you did not anticipate — which is precisely the case the critique found.

R5 — TP degree must not be in the key; it must be in the layout (answers C5)

The critique identifies a real operational cliff. tp_degree in CacheKey means the TP4 → TP8 migration invalidates 100% of the cache at the moment of the change — and by §7, a cold cache is a capacity event. Doing that simultaneously with a parallelism migration that is itself a capacity change is how a routine latency improvement becomes an outage.

Change: store KV in a TP-independent canonical layout and shard on materialization.

Stored:      [layer][kv_head][block][head_dim]     — logical, TP-agnostic
Materialize: rank r takes kv_heads where (h % tp) == r

For GQA-8 with TP4, each rank owns 2 KV heads; with TP8, each owns 1. Both are slices of the same logical array, so the same stored blocks serve both. tp_degree leaves the key entirely.

Cost, stated honestly: materialization is now a strided gather rather than a flat copy, which is slower — call it 15–25% on the DMA. Against the §6 margin (PCIe is 6.9× above break-even) that is comfortably affordable, and it buys a TP migration that is a rolling change instead of a fleet event.

The check the critique implies, generalized: for every field in a cache key, ask what operation changes it and what that operation costs when it invalidates everything. Applying it to the rest of §7's key:

• weights_version — invalidation is correct and unavoidable; a rollout must be gradual (§7).
• kv_dtype — same; an FP8 migration is a cache-cold event and must be planned as one.
• rope_config_hash, attn_impl_id — rare, and invalidation is correct.
• tp_degree — not a correctness input at all, once the layout is canonical. It was in the key because of an implementation detail, which is the wrong reason for anything to be in a key.

R6 — Queueing does not rescue NVMe, and here is the number (answers C6)

The critique is right that the comparison used an idle-GPU recompute time, and it is a fair challenge. But working it through, it does not change the answer for the interactive fleet — and being able to show that is better than conceding.

Under queueing, both sides degrade, not just recompute:

recompute path:  queue_delay + 71 ms                 (GPU is contended)
NVMe path:       94 ms + queue_delay_for_the_100 ms  (the tail still needs GPU work
                                                      to integrate, plus PCIe contention)

The NVMe read does not eliminate GPU queueing — a cache hit still enters the same scheduler for decode. So queue delay appears on both sides and largely cancels. What does not cancel:

• NVMe bandwidth is shared across all concurrent fetches on the host. At 90% occupancy there are many; 7 GB/s divided by 8 concurrent fetches is 0.9 GB/s effective, which is ten times below break-even, not 0.75×. Contention makes NVMe worse, not better.
• Recompute throughput is what queueing degrades, and R1 already establishes that the cache's main value on a loaded fleet is capacity, which is served by T1/T2 at 6.9×/2.7× margin.

So: no, NVMe does not come back for the interactive fleet — and it gets worse under exactly the conditions the critique proposed, because the shared resource contends where the private one does not. It remains defensible for the batch fleet (R1), where latency is not the currency.

Change: measure it rather than argue it. The design ships a shadow-mode measurement — store to NVMe, fetch from NVMe, discard the result, and record the achieved bandwidth under real concurrency. If measured NVMe bandwidth at p95 concurrency exceeds the break-even, the tier turns on by config. A disagreement about a number is best settled by instrumenting the number, and building the instrument is cheap because the failure mode is "treat as miss".

References

• ../WARMUP.md#51-prefix-caching — prefix caching from zero
• ../WARMUP.md#32-the-kv-cache-derived — where 320 KiB/token comes from
• ../gpu_math.py — the break-even arithmetic, reproducible
• m01-llm-api-platform.md — the platform this caches for; R3 there is the tenant-scoping decision
• m05-eval-harness.md — what must exist before FP8 KV can be turned on
• ../../systems-design/WARMUP.md#48-partitioning — rendezvous hashing and bounded loads, used in R2
• ../../coding/WARMUP.md#chapter-3-caches-and-intrusive-data-structures — LRU/TinyLFU mechanics as a coding problem
• Zheng, L. et al. SGLang: Efficient Execution of Structured Language Model Programs. — RadixAttention, the radix-tree prefix cache
• Kwon, W. et al. PagedAttention. SOSP 2023 — block-aligned KV management
• Einziger, G. et al. TinyLFU: A Highly Efficient Cache Admission Policy. — the admission filter in §8/R3
• DeepSeek-AI. DeepSeek-V2. — MLA and what an order-of-magnitude smaller KV does to this design