Production Traces From Two Companies Show 14 Eviction Policies Barely Beat LRU for Agentic LLM Prefix Caches

arXiv·medium signalXBlueskyLinkedInCopy link

Liu, Yu and Yang (arXiv 2609.28870) replay production agentic traces from two companies against 14 eviction algorithms in both HBM-constrained and large memory-pool settings, and find that policies designed for traditional caches give little over LRU despite a large gap to Belady. The cause is structural: active sessions resend growing context at a regular pace, which makes recency unusually predictive. They recommend keeping LRU as the base and adding quick demotion for one-hit prefixes, compute-aware partial eviction for expensive misses, and capacity-dependent granularity, and they plan to release the traces and simulator. The paper lands the same week kvcached is trending on GitHub.