LRU is harder to beat than the KV-cache papers suggest

As an individual researcher, you do not have 22M$ to run a massive brute-force search for your problem. You are constrained to your little subscription and you will barely dip your toe in the sea of possible solutions to a problem. So letting Claude run an autoresearch loop on your problem and then having it summarize it for you brings 0 value because you dont know what the downsides and trade-offs of LRU caches were, and how you would possible solve it.

Spoken like a true Claude.

Snarking aside, I am glad that our AI agents make it cheap enough to do these experiments and publish these write-ups that people finally bother to publish null findings. Very useful!

When I give an agent a piece of corrected information regarding a long running task, the last thing I want it to do is try and statistically compensate for the fact that it is new information. I want this new information to dominate the old information.

The economics and thus tools you can throw at inference change at various scales . As a “blunt” contrived example , on a gb300 the GPUs communicate super fast over nvlink, and the cards can offload kv cache to dram and then disk, “fast enough “ for these tool heavy agentic workloads.

Which come together to mean that at high enough scale and in the right scenario, we can work with wild ttls on the kv cache and still comfortably hit SLAs and tokenomics.

This is incorrect. If you are generating the 51th turn, then prefix caching makes the turns 1 to 50 cost a fraction of what they normally cost, to generate the 51th turn. Generating the 51th turn is more costly because it is not in the cache yet.

Unfortunately there is no way to steelman the statement, since quadratic scaling of attention means that the cost goes up even if you assume perfect caching of past inputs.

What the author actually means is something more mundane. The initial prompt is massive in a standard coding harness and this means prompt processing takes much longer than expected, creating the misleading impression that costs go down.

Edit: I noticed the word cross request too late. In that case the harness prompt is expected to be cached from other users, in which case the first message actually has a massive unfair advantage.

A toy/simplified version lives here: https://github.com/chaboud/goulash

Consideration of mutation rate (a sort of temporal Shannon-ish coding/ordering) lives in there (with some RoPE-friendly structuring). Note: That was a vacation project, not the day job, but similar principles apply even with larger models.

And while the range of cache sizes chosen is reasonable based on the table about Moonshot's number at the start, the finding that all tested KV-cache sizes are so small that the 5-minute eviction never triggers should have been reason enough to reevaluate that choice

Fun:

> In my first run, Belady — an offline oracle — lost to LRU. That's not a result, that's a broken harness, and it's worth publishing because I expect it to be common.

> The cause: inserting a long chain into a near-full cache lets a policy evict the very prefix it is currently building. LRU is accidentally immune because just-inserted blocks have the newest timestamp.

There's a growing literature arguing LRU is the wrong eviction policy for agentic LLM serving, because agent sessions idle and LRU can't distinguish a paused session from a dead one. I found the argument convincing and built a simulator to exploit it. Three separate mechanisms, all lost to plain radix-leaf LRU.

The reason turned out to be more useful than the policy. When I measured — policy-independently — where recompute actually comes from on 393 real Claude Code sessions, requests arriving after a gap longer than the 5-minute provider TTL account for 17.5% of it. Requests arriving within 10 seconds account for 33.1%. The dominant waste is tight tool loops whose 88k-token working sets exceed cache capacity, not sessions idling past a TTL. That's a capacity problem, and liveness prediction can't touch it.