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

summary

Least Recently Used (LRU) caching is significantly more resilient for agentic LLM workloads than current research suggests because most cache misses in capacity-constrained environments are caused by large working sets in tight tool-calling loops rather than idle sessions. While some literature focuses on the impact of provider-imposed timeouts (TTL), these timeouts rarely trigger in capacity-bound systems where LRU already evicts data before timers expire. Consequently, complex liveness-prediction policies often fail to outperform simple LRU because they target a problem that is not the primary driver of recomputation in these settings.

key points

1. Most recompute tokens in capacity-bound caches come from requests arriving within 10 seconds of the previous turn, meaning the issue is a lack of total space rather than poorly timed evictions.
2. Attempts to implement advanced policies—including Bayesian liveness estimators and cost-aware eviction—consistently performed worse than the LRU-leaf baseline on real-world agent traces.
3. A common simulator bug often makes non-recency policies appear worse than LRU because they may evict the prefix they are currently building unless explicit pinning is implemented.

who should read it

Software engineers and researchers working on LLM inference optimization, specifically those implementing KV-cache management or prefix caching in serving stacks.

discussion skeptical