The three regimes of agentic KV eviction

On real Claude Code traces under memory pressure, LRU does 60 percent more recompute than a strong offline oracle, so there is real room for a smarter eviction policy. Three papers this year each proposed one. I built a shared benchmark, reimplemented all three plus a contender of my own, and scored them against the oracle. Two findings you can use before any of the detail:

Idle-based eviction is actively harmful on agent workloads. A naive “drop anything idle longer than N” policy (a strawman, not Continuum’s gap-aware protection, which I reconstruct and test separately) pays up to 16x the oracle’s recompute, because on append-mostly agent prefixes an idle block is not dead, it is re-read on the next turn. If your evictor treats idle time as a reason to drop KV, stop.

Almost nothing beats LRU. Of the published policies, only SAGA’s WA-LRU clears plain recency, and only by about 4 points, by using reuse as a light correction to recency. Frequency scoring and gap-aware protection tie it or lose. The one signal that reliably helps is lifecycle retirement, reclaiming KV that a compaction has made dead, and even that only in a narrow band of memory pressure, by a variable amount centered near 15 percent, and only on deep multi-turn sessions.

Which one applies depends on how full your cache is. It sorts into three regimes, and the map below is the whole result in one picture.

What to do Monday. For most deployments: do not touch your evictor, LRU is within a point of everything tested here. The one case worth checking is deep multi-turn agents under memory pressure. A two-line test for whether you are in the band where it matters: (1) is your KV cache smaller than the combined working set of your concurrent sessions, roughly half of it or less? and (2) do your sessions run many turns that re-read a growing prefix? If both are yes, lifecycle-aware eviction (reclaim KV on a compaction or termination signal) is worth a look. If either is no, LRU is already near-optimal and eviction is not your bottleneck.

Where this sits in your stack. Prefix dedup (SGLang’s RadixAttention, vLLM’s automatic prefix caching) and KV offload (LMCache) are the first-order levers, and they are orthogonal to this: they decide what to share and what to move. This benchmark asks the next question, what to evict once the cache is still full after those, which is the decision LMCache’s eviction layer makes today with LRU. It is deliberately the second-order knob. The finding that LRU is hard to beat there is worth knowing precisely because it tells you to spend your effort on the first-order levers first.

The map

The inverted-U is the textbook cache-size sensitivity curve, not a finding. The finding is which signals cash that gap in: only lifecycle retirement (blue) reliably does, in the band, and even that with wide error bars; protection (red) and pricing hurt or fail to replicate.

That is the whole result. The rest is how I know it, and how hard I tried to break it. It is preliminary by design: the durable artifact is the harness, and these numbers are its first entries, not its last.

The gap nobody measured

When you serve an agent, the KV cache fills with the conversation prefix: system prompt, tool outputs, reasoning, prior turns. Under many concurrent sessions the cache overflows and you have to drop some of that state. Whatever you drop and then need again gets recomputed, which is a prefill you already paid for once. The eviction policy decides which state to keep.

Three groups attacked this in 2026 from different directions:

• Continuum / CacheTTL (arXiv 2511.02230): keep KV alive through predicted tool-call gaps with a time-to-live, so state does not get harvested during the idle windows an agent spends waiting on a tool.
• Retired-cache lifecycle eviction (arXiv 2605.06472): when the workflow signals a block is done (a termination or compaction message), reclaim it.
• SAGA Workflow-Aware LRU (arXiv 2605.00528): score each block by recency, reuse probability, and size, and evict the worst.

Each paper reports wins on its own setup. None share a workload, a metric, or a baseline, so there was no way to answer the only question an operator has: on my traffic, which one should I run? That is the question a benchmark exists to answer, and there was not one.

The benchmark

agentic-kv-bench is a harness for exactly this comparison: real traces, an offline oracle, the published policies reimplemented as baselines, and a small interface anyone can implement.

Real traces. The workload is the public kv-cache-tester corpus, 739 anonymized Claude Code sessions. These are append-mostly prefixes with real compaction events and real tool-call structure, not synthetic chat. Memory pressure comes from interleaving many sessions onto one timeline, because a single conversation never overflows a sane cache; a fleet of them does.

An oracle, so the numbers mean something. Every policy is scored as a percent of a cost-aware Belady oracle that evicts with perfect knowledge of the future. 100 percent means you matched it; 160 means 60 percent more avoidable recompute than a policy that could see the future. One honest caveat: Belady is provably optimal only for uniform cost and size, and this workload has neither, so the oracle is a strong offline baseline, not a proven optimum, and I call it that in the repo. Reporting percent-of-oracle instead of raw hit rate is what makes a 2 percent win distinguishable from a 40 percent one, and what tells you when a workload has no room to win at all.

Fair accounting. A block’s first load is a compulsory miss that every policy pays, so it is not scored; only an evicted-then-reaccessed block, an avoidable recompute, counts. A policy can never evict a block the current request still needs. Block granularity is a simulation knob, held equal across policies. The point of all this plumbing is that the only thing separating two numbers is the eviction decision.

A small interface. A policy implements one method, evict, and optionally consumes lifecycle hints. The published baselines ship in the box. Your policy is a few lines and runs against the same traces and oracle as everyone else.

The ladder

I ran the policies as a ladder, cheapest signal first. Every headline number was pre-registered: the prediction committed before the run, the result in a later commit, so the whole sequence including the predictions I got wrong is checkable in the commit history.

A disclosure up front, because it matters for how much to trust everything below: these numbers are on 11 interleaved sessions, a sample spanning the 739-trace corpus, not the whole thing. Eleven is small, and I show later exactly where that bites. Start at the hardest pressure, where the cache holds about a third of the combined working set.

One label needs a guard rail before anyone screenshots that table. The idle-TTL row is a deliberate strawman: a naive “evict anything idle longer than N” policy, not Continuum’s actual mechanism, which is gap-aware protection (keeping KV alive through predicted tool-call gaps). Naive idle expiry is the counterexample Continuum was built to beat, so its number here is evidence for Continuum’s premise, not a score against Continuum. The faithful Continuum mechanism is the separate row below (160.5), and it earns its own discussion.

None of this should surprise anyone who has worked on caches: clever policies routinely lose to plain recency outside their motivating workload, and forty years of eviction literature is mostly that story. The twist worth stating is that these three policies were built for this workload, and most still do not clear LRU on it. Idle-time expiry and frequency both do worse than plain recency. On append-mostly agentic prefixes a block that has been idle is not dead, it is just between reads; the best-tuned idle-TTL still trails LRU (176 versus 160), and at an aggressive setting it pays 16x. Frequency (GDSF) over-protects long-lived prefix blocks and also loses. WA-LRU is the only classic policy that beats LRU here, by about 4 points (156.8), and only by using reuse as a small correction to recency rather than a signal of its own. Its best weights on these exact traces reach 155.4, but that is tuned on the evaluation set, so the untuned 156.8 is the number I stand behind.

Continuum is the one to watch, because its mechanism is the only one that directly targets the idle-is-not-dead property: protect a session’s KV through tool-call gaps instead of harvesting it. The idea is right. But my faithful reconstruction lands exactly on LRU (160.5) at every horizon, for a reason the ladder already exposed. Because the whole prefix is re-read each turn, recency is already protecting the blocks that will return, so session-gap protection has nothing left to add, and at a real horizon it starts protecting stale sessions and actively hurts. One caveat keeps this fair: I ran the inference-only version, which estimates gaps from session recency; the paper predicts them from workflow structure, and that hint-driven version I have not run. It is the natural next rung, and it is where Continuum’s real contribution would show up if it does.

The genuinely counterintuitive result is that the lifecycle hint, the thing the whole design was built toward, barely moves the number at this pressure: retired-cache with hints is 159.3 against LRU’s 160.5. The reclaimed blocks are real, roughly 80 percent of cache capacity turns out to be KV that, in hindsight, is never read again, but under heavy churn the freed space is instantly re-consumed. The dead blocks were not the binding constraint. The room here is in the ordering of live-block evictions, which lifecycle information does not touch. (The hint here is an idealization: it uses ground-truth “never read again,” which is what a framework’s compaction signal would approximate, degraded on purpose by the harness’s drop-and-delay switches.)

At this pressure, recency wins, and none of the four published policies clears it by more than a rounding error.

Why the shape is not new, and what is

I swept pressure to get that map, and the shape of it is one you have seen: the gap between LRU and the oracle is a classic function of cache size, near zero when the cache is tiny (everything misses) or huge (everything fits), and widest when the working set is right around capacity. The inverted-U is not the finding. What is worth measuring is which signals cash that gap in on agentic traces, and how much, and there the answer is specific and mostly negative: in the band the one signal that reliably helps is lifecycle retirement (stated carefully in the next section); Continuum’s gap protection goes the other way and costs misses; the economic policy’s pricing looks best of all on the full sample and then does not survive resampling. The honest one-line map is narrower than “smart policies win in the middle”: lifecycle information helps in the middle, sometimes, by a variable amount; the other two signals do not.

One claim I want to make and cannot: that the band is where fleets run. It is plausible, you would not provision at a third of your working set or at slack, but I have no serving data to back it, so treat it as a hypothesis, not a result.

How much to trust the middle

The middle regime is where it is easiest to fool yourself, so I ran it three ways.

Retirement, leave-one-out. Drop one session at a time and remeasure. The full-sample band benefit is about 26 percent; the leave-one-out mean is about 15 percent, range 0 to 34, and two of the eleven sessions carry most of it. The good news is it never goes negative, so the sign is robust: retirement helps. The bad news is the magnitude is a coin flip between small and large, and 26 percent was the optimistic tail.

Pricing, leave-one-out. The economic policy showed 18 percent at one point in the band. Same test: the leave-one-out range is 1 to 26 percent at one cache size and negative 72 to positive 16 at the next. A single session flips it from a large win to a large loss. The sign is not robust, so pricing is not established. I registered “modest, not a dramatic win” before running, and the resampling agrees with the prediction, not the 18.

The sample itself, and this is the one that should worry you most. I drew fresh random session sets from the full 739 traces and remeasured. Most show almost no scored pressure in the band: a few hundred avoidable misses or fewer, several exactly zero, against the stride sample’s several thousand. My first guess was that random draws are simply too small to register, but scaling them up refutes that cleanly: a 40-session draw with four times the token volume still produces about 150 misses, not thousands. The real driver is turn depth. Scored misses come from deep, multi-turn sessions that re-read their growing prefix over and over, and those re-reads are the only thing a policy can save; a session read once or twice just pays compulsory misses that nobody is scored for. Deep sessions are rare in the corpus and over-represented in the stride sample, so a random draw of mostly-shallow sessions has little for any policy to work with. The honest boundary is therefore about workload shape, not cache sizing: these results characterize deep multi-turn agent sessions under pressure, and a corpus-level magnitude needs a draw that deliberately represents the turn-depth distribution.

What survives all three checks is thin, and I will claim only this: on samples under real pressure, lifecycle retirement reliably (sign-robustly) recovers some avoidable recompute in a mid-pressure band, by a variable amount centered near 15 percent. Everything past that sentence is a hypothesis with a number attached, and the number needs the full corpus to firm up. That run is the next measurement; the corpus is cloned and the code is done, so it is compute, not invention.

What this cannot claim yet

First, the conversion, because it is the number an operator actually budgets in. A 15 percent cut in avoidable recompute is a latency or dollar win only if avoidable recompute is a material share of your prefill, and prefill a material share of your latency. This benchmark measures the recompute; it does not measure that chain. The Phase 4 vLLM run does, on real hardware, and until then every number here is simulation-relative: percent of an offline oracle, not milliseconds of TTFT or dollars per thousand requests. Size the prize against your own prefill share before you spend an engineer on it.

Beyond that, four boundaries. The corpus is one workload family, agentic coding sessions, so none of this speaks to chat or RAG or other agent shapes. Continuum’s number is the inference-only reconstruction; the workflow-hint version the paper actually contributes is unrun, and it is the most likely of everything here to change a conclusion, so read the Continuum result as “gap protection estimated from recency does not help,” not “Continuum does not help.” The pressure sweep is static: sessions start together and pressure is set by shrinking the cache, not by a live arrival process, so the regime boundaries may move under realistic bursty load. And the cost model that lets the economic policy price blocks is an assumed per-kind profile, not a measured one, with the offload and refuse actions stubbed, because the migrate-versus-recompute costs that make them real are the next measurement, on real hardware. Every one of these is stated in the repo, and each is a place the benchmark gets sharper.

An invitation

If you wrote one of these policies: I reimplemented yours as a baseline, and I will have gotten details wrong. Corrections are the point. Open an issue, or send a policy that beats mine in the band.

Running your own is pip install git+https://github.com/fishercort/agentic-kv-bench and one class. The interface is one required method, evict, which returns the blocks to drop, plus optional hooks (on_access, on_hint, place) that default to no-ops. The harness owns correctness: your evict() cannot corrupt the benchmark, it can only change your score. The worst a buggy policy does is lose.

The benchmark, the oracle, the baselines, and every result above, including my own registered prediction refuted in the commit history, are at github.com/fishercort/agentic-kv-bench.