Cached prefixes are best-effort, not guaranteed: the same prompt hits at 3 a.m. and misses at peak, and nothing in the response tells you which happened or why.
Why you'd careThe thing you have already noticed
Your cache hit rate was 95 percent in staging and is 40 percent at two in the afternoon in production. Nobody changed your prompt. What changed is that other traffic filled the block pool and the server recycled your prefix to make room. Eviction is the part of caching that no API reference describes: the cache is a fixed pool, prefixes survive only while there is space, and blocks nothing is currently reading go first. Vendors document a lifetime — Anthropic a five-minute TTL refreshed on use, OpenAI an inactivity window of roughly five to ten minutes — and that is true but incomplete, because capacity pressure evicts long before the clock does. On your own vLLM or SGLang server you can watch it happen in the free-block count.
In and outWhat goes in, what comes out
| In | An allocation request that would push the free-block count below the watermark, per-block reference counts, last-access ordering over free blocks, and — in a radix-tree cache — the current leaf set plus the token-hash chain identifying each node. |
|---|---|
| Process | Filter to blocks no running sequence references, rank them (least-recently-used order over the free list in vLLM, leaf-first LRU over the radix tree in SGLang), then free enough to satisfy the request and delete the matching index entries so later lookups miss cleanly rather than returning a dangling block. |
| Out | Reclaimed physical blocks returned to the pool, a smaller prefix index, and a future cache miss for whoever owned the evicted chain — surfaced nowhere, and indistinguishable at the API from a genuinely first-ever request. |
No live state is at risk; reference counting makes an in-use block ineligible by construction. What is irreversibly lost is compute you already paid for. Eviction is all-or-nothing per block, and because prefixes form chains, the reusable part of a conversation is only as long as its shortest surviving link — losing one block in the middle strands every block after it, which is precisely why engines evict from the leaves inward.
ConceptThe idea underneath
Nothing here is a property of the model. This is cache replacement — the same question a CPU asks about a cache line and an operating system asks about a page — with two twists that make the textbook answer wrong.
The first twist is that entries are chained. A prefix cache is a tree, not a flat set of independent items: the node holding tokens 1 to 512 is the parent of every conversation that shares that opening. Evicting an interior node would strand its whole subtree, which is why engines such as SGLang evict leaves first and walk inward, and why reference counting is mandatory rather than an optimisation — a block any running sequence still points at is not a candidate at any price.
The second twist is that entries do not cost the same to replace. In a CPU cache, every line costs one memory fetch to refill. Here, a four-block leaf costs 64 tokens of prefill to rebuild while a 200-block trunk costs 3,200 — a fifty-fold difference in the value of keeping it. Plain LRU is blind to that, which is why cost-aware policies from the web-caching literature, GreedyDual-Size among them, are the right theoretical frame: rank by recency scaled by recomputation cost, not by recency alone. Most engines ship LRU anyway, because refcounted leaf-ordered LRU is cheap to maintain under the allocator's lock and good enough in practice. When you measure hit rate, the honest yardstick is not 100 percent but Belady's optimal — evict the block whose next use is furthest away — which no online policy can reach, because it requires knowing the future.
At a glanceSee it
Eviction filters out in-use blocks, ranks the rest leaf-first by recency, and frees them back to the pool.
The knobsHyperparameters and nuance
- enable_prefix_caching(vLLM) — with reuse off, blocks are freed the instant a request ends and there is no eviction policy to speak of. Turning it on is what creates the pool of cold-but-valuable blocks this stage manages, and the pressure that follows.
- disable_radix_cache(SGLang, default off) — the same switch for the radix tree. Left off you keep leaf-first LRU over a shared prefix tree; set it and every request prefills from scratch, making hit rate zero by construction.
- gpu_memory_utilization(vLLM) / mem_fraction_static (SGLang) — pool size, which is really eviction pressure. Too small and the policy runs on nearly every allocation; too large and you OOM at peak activation, which presents as an unrelated crash.
- preemption(engine behaviour, not a parameter you set) — the escalation path when eviction cannot free enough for a running sequence. vLLM V1 preempts by recomputation only; the V0
--preemption-modeswitch and itsswapoption have been removed. This is where a hit-rate problem turns into a latency problem your users feel, and the pool-size knobs above are what you tune against it. - ttl on cache_control(Anthropic:
"5m"or"1h") — the only lever a hosted API offers. You cannot pin a prefix or inspect the pool; you can pay 2x on the write instead of 1.25x to keep an entry alive across longer gaps in your traffic.
EffectHow this stage moves the answer
Block eviction is lossless — you lose computed work, not information — so its effect on the answer is entirely second-order, by three routes. A miss turns a 50 ms cache read into a multi-second prefill, which under a client timeout becomes a truncated stream or a retry. Under real pressure, failing to evict enough escalates to preemption, and a preempted sequence that resumes in a different batch can diverge at a near-tie. The third route is a naming collision worth knowing about: token-level KV eviction, which drops individual positions judged unimportant so more context fits in the same memory, is a completely different mechanism wearing the same word — and that one changes answers directly. It degrades exact recall over the discarded span first, so the model keeps writing fluently while quietly losing the ability to quote what it threw away. Check which one your stack means.
EvalsWhat it does to your measurements
Hit rate is the metric, and reporting it as a single number is the mistake: it is a function of concurrency, tenant mix and prefix diversity, so it belongs on a curve against load. Alongside it, watch prefill tokens per request against prompt tokens per request — the gap is your real reuse — and the count of blocks evicted and then recomputed, which is work you already paid for once. The silent invalidation is running a latency or cost benchmark on an idle box. With no pressure nothing is ever evicted, so a 200-prompt suite looped repeatedly reports near-total hit rate and a p99 production never reproduces. Cost models built from a low-traffic pilot understate spend, and they understate it worse as you add tenants, because every new distinct prefix competes for the same fixed pool.
Failure modesWhen it goes wrong
- Hit rate falls as traffic rises, with a knee rather than a slopethe working set of distinct prefixes crossed the pool size; below the knee everything fits, above it almost nothing survives between uses.
- One tenant's long prompts destroy everyone else's hit ratea single 100k-token prefix occupies thousands of blocks, and plain LRU has no concept of fairness or per-tenant budget.
- A miss on a prompt you sent thirty seconds agocapacity eviction, not TTL expiry. Vendors document an inactivity window; none of them promise capacity.
- Recomputed prefill spikes with no change in request volumethe shape of traffic changed, not its size: more distinct prefixes at the same token count fans the tree out and leaves get evicted before anyone reuses them.
- Enabling prefix caching made throughput slightly worsea workload with no shared prefixes pays the hashing and bookkeeping cost and gets nothing back.
PapersWhere this comes from
- SGLang: Efficient Execution of Structured Language Model ProgramsZheng et al., 2024 (arXiv 2312.07104). Introduced RadixAttention: a radix tree of cached prefixes with reference counting and an LRU order that removes leaves first so no live path is stranded. This is the reference design for block eviction.
- H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language ModelsZhang et al., 2023 (arXiv 2306.14048). Established the other kind of eviction, dropping individual tokens' keys and values based on accumulated attention scores — the paper to read to understand why token eviction trades memory for accuracy while block eviction only trades memory for recompute.
- Efficient Streaming Language Models with Attention SinksXiao et al., 2023 (arXiv 2309.17453). Showed that discarding the earliest tokens collapses generation quality unless a few initial sink tokens are retained, which is the sharpest available demonstration that cached positions are not interchangeable.