When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

arXiv:2609.28870 · cs.DC, cs.LG · Submitted 2026-09-24 · Read on arXiv

cs.DC, cs.LG

Submitted: 2026-09-24

Updated: 2026-10-01

Comments: 20 pages, 20 figures, 6 tables

Code: https://github.com/cacheMon/cache_

License: http://creativecommons.org/licenses/by/4.0/

The gist: Long-running LLM applications repeatedly send growing context, making prefix caching critical for reducing prefill cost.

Terminology

Abstract

Long-running LLM applications repeatedly send growing context, making prefix caching critical for reducing prefill cost. Yet prefix-cache behavior under agentic workloads remains poorly understood. We study production traces from two companies and evaluate 14 eviction algorithms across HBM-constrained and large memory-pool settings. Despite a large gap to Belady, sophisticated policies designed for traditional caches provide little benefit over LRU. The reason is structural: prefix reuse is dominated by the regular pacing of active sessions, making recency unusually predictive. Prefix caching nevertheless introduces new challenges, including heavy-tailed session footprints and highly variable miss costs as attention computation grows with sequence length. We introduce the compute-savings ratio and two offline oracles to quantify these effects. Our results show that effective prefix-cache management should retain recency as its foundation while selectively adding quick demotion for one-hit prefixes, compute-aware partial eviction for expensive misses, and capacity-dependent eviction granularity. We will release the traces and simulator to support future research.

Sources

Related papers