Cache replacement strategies for AI context reuse favor simple recency based rules
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
Distributed, Parallel, and Cluster ComputingMachine Learning
Summary
Large language models (LLMs) often reuse parts of previous conversations to save time and computing cost, but it’s tricky to decide which parts to keep in memory. The authors looked at real-world data and tested many methods for clearing cache memory, finding that simple rules based on recent use worked nearly as well as complex ones. They also discovered that some special strategies can help with certain tricky cases, like when some parts are used only once or costly to recompute. This work helps improve how AI systems manage memory to run more efficiently.
What this means in practice
- •For ai system engineers: Reduce computational costs in LLM-based applications by implementing cache eviction policies prioritizing recent usage and selectively demoting seldom reused states.
- •For cloud infrastructure teams: Optimize memory management for AI workloads with variable session lengths by adapting cache eviction granularity based on capacity and compute cost.
Authors
Yiyu Liu, Minlan Yu, Juncheng Yang
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.