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

What I feel a bit annoyed by, and what I feel obviously LLM-run ablations like this fail to capture, is any kind of reflection around previous research or any kind of proof that this is the best you can do. You don't know, you pulled the lever and you got something, is the best? Can you do better? What is the constraint?

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.

> It didn't work, and why it didn't work turned out to be more interesting than the policy would have been.

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!

LRU seems like the ideal strategy for most things LLM-related. Everything in this realm is about recency bias. I think it is a feature in this context, not a problem.

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.

I work on inference at a neocloud, but opinions are my own .

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.

The settings may change, but the two major problems in CS remain the same: cache invalidation, naming things, and off by one errors.

I've been building latency-sensitive LLM systems for a while, and I've come to rely heavily on pre-fill-considerate mechanics like ping-pong overlapped async context construction. For interactive mechanics, the worst case, even if rare, is problematic.

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.

Based on the tables in part 4 it seems like some of the policies would have started overtaking LRU at larger KV-cache sizes.

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

This is almost unreadable. The "papers" are never referenced anywhere, so the claims being refuted cannot be evaluated. The whole fact of the TTL doesn't seem relevant at all. There are many, many well-researched admission and eviction policies that this readme doesn't mention. I just don't get why we are reading this.

Here is the repo link: https://github.com/gauravapiscean/agentic-kv-cache

Interesting! I admit the AI-written text is rough to read, it could have used a pass or two from an actual human. E.g. "Publishing it unresolved rather than tuning until it matches." -- thanks for not lying, I guess?

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.

Author here. Context for why I did this:

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.