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

Abstract

As LLM context lengths push into hundreds of thousands of tokens, prefill computation rapidly dominates serving costs. Modern inference engines use prefix caching to retain previously computed key-value (KV) states across requests within a session. However, modern serving systems almost universally default to Least Recently Used (LRU) eviction, raising a fundamental question: do decades of traditional cache-management techniques transfer directly to LLM serving?

In this talk, we examine prefix-cache eviction through the first large-scale empirical study on production traces comprising over 20 billion processed tokens across both capacity-constrained accelerator memory (HBM) and large disaggregated memory pools (DRAM/SSD). Evaluating online eviction algorithms against Belady’s offline oracle reveals a surprising result: advanced policies offer little benefit over simple LRU, and frequency-based policies actively collapse, even though substantial headroom to the offline optimum remains. We show this mismatch stems from fundamental workload differences: prefix reuse is driven by the steady pacing of active sessions, making recency an unusually strong predictor while rendering frequency misleading. Furthermore, prefix caching diverges from traditional caching due to extreme footprint skew and non-uniform miss costs, where attention recomputation grows quadratically with token depth. To bridge the gap toward optimality, we outline practical design principles for prefix-cache management: retaining LRU as a baseline, conditionally deploying quick demotion to filter transient one-hit prompts, introducing compute-aware eviction paired with partial-node chunking to prevent attention fragmentation, and adapting eviction granularity to the memory tier.

Bio

Yiyu Liu is a Ph.D. student in Computer Science at Harvard University, co-advised by Prof. Juncheng Yang and Prof. Minlan Yu. His research focuses on systems for machine learning, with a focus on improving the performance and efficiency of emerging AI workloads. He received his bachelor’s degree in Computer Science at Shanghai Jiao Tong University and has previously published work at ASPLOS and MLSys.