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

> 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!

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.

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.

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

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

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.

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.