4 ms·
LRU is harder to beat than the KV-cache papers suggest
- gauravapiscean 2mo agoAuthor 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.
- Shadowmist 2mo ago> Author here. The best kind of correct.
- r_lee 2mo agojust curious, why the LLM writing even here? it's just a bit disheartening to read Claude output for such a small comment like this.. it'd be great to read your own writings even if it's not as "perfect"
- pmarreck 2mo agoOne side effect of extremely-accessible, high-quality English translation and, more importantly, English-grammar-and-idiosyncrasy-obeying AI, is that there will be more and more text that looks like this which comes from foreign, non-native-English countries. Just FYI. This will be especially true from non-English cultures where "avoiding shame" is high on the list of motivations. Consider the upside, though: A much broader range of written perspectives written in high-quality, if slightly annoying, English. I'm already seeing the benefit of this on X thanks to its autotranslation btw: I follow a few Chinese-language accounts now that I would have never been able to digest otherwise.
- HarHarVeryFunny 2mo agoWhy/when would people expect agents to be idling? I'd have thought they'd be busy (using cached prompt-prefixes) until they were finished.
- what 2mo agoMaybe waiting on a slow tool call or subagent or something?
- gauravapiscean 2mo agoHere is the repo link: https://github.com/gauravapiscean/agentic-kv-cache https://github.com/gauravapiscean/agentic-kv-cache
- achierius 2mo agoInteresting! 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.
- eru 2mo ago> 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!
- phoghed 2mo agoThat line doesn’t strike me as overtly AI written, overall yes though
- cryptonector 2mo agoThe whole thing is clearly written by Claude.
- phoghed 2mo agoYes I covered that after the comma if you didn’t make it that far. This sentence quoted just doesn’t seem like the AI smoking gun to choose given the rest of the content.
- eru 2mo agoIt was just the first example that stuck out to me. I didn't do an exhaustive check to look for the worst offender.
- phoghed 2mo agoSorry I assumed you read the whole thing, forgot where I was for a moment
- cryptonector 2mo agoYeah, we have a habit of not bothering to read LLM-generated prose.
- bob1029 2mo agoLRU 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.
- jayd16 2mo agoIt makes them yes-men.
- jeffbee 2mo agoThis 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.
- augment_me 2mo agoWhat 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.
- babelfish 2mo agoyou can just ask it to explain those things!
- augment_me 2mo agoSure, and it will explain it to you from the same embedding space that yielded the solution that LRU cache is unbeatable.
- deleted 2mo ago[deleted]
- Twirrim 2mo agoIt'll just be telling you what the data it ingested claims. Not what is necessarily true. It's as subject to garbage in, garbage out as anything, and you don't know what it's actually trained on.
- alansaber 2mo agoSometimes it's good enough to acknowledge a correct answer, and slowly build intuition towards it. Academic problem solving is rarely a straight path, anyway.
- lukeschlather 2mo ago
- epistasis 2mo agoThe settings may change, but the two major problems in CS remain the same: cache invalidation, naming things, and off by one errors.
- deleted 2mo ago[deleted]
- talolard 2mo agoI 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.
- chaboud 2mo agoI'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 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.
- wongarsu 2mo agoBased 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
- imtringued 2mo ago>Cross-request KV prefix caching is the largest practical lever in agentic LLM serving. It's why your coding agent's fiftieth turn costs a fraction of its first. 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.
- 1a1a11a 2mo agoIt is such as shame: we tell you that we are writing a paper on this exact topic and you created a GitHub and advertises everywhere