When large language model prompts flood enterprise infrastructure, semantic caches attempt to save expensive compute cycles by recycling previous responses whenever a new user query hits close to an existing vector in memory. A rigorous new benchmarking study demonstrates that decades of sophisticated cache eviction theory collapse in the semantic domain, proving that Least Frequently Used (LFU) policies perform virtually identically to advanced, geometry-aware alternatives.
By putting seven distinct eviction strategies through a unified evaluation framework dubbed CLEVER, researchers found that no complex policy managed to beat basic LFU by more than 0.041 percentage points across 18 diverse testing environments. The findings upend common assumptions about memory management in vector-based AI systems, suggesting that engineering efforts currently misdirected toward algorithmic complexity should instead focus on response validity.
The Core Discovery
The research team systematically evaluated seven eviction policies—including FIFO, LRU, LFU, ARC, GDSF, a streaming adaptation of SISO, and a dedicated semantic-redundancy policy—across three deduplicated query corpora, three cache capacities, and two distinct encoders. The empirical takeaway is stark: replacement policies matter primarily at their worst, not their best. While naive strategies like First-In, First-Out (FIFO) and streaming SISO lagged behind LFU by up to 8.67 and 8.55 percentage points under tight capacity constraints, no advanced algorithm could push past LFU’s baseline performance.
To explain this surprising parity, the authors formulated a mathematical proof termed the conditional packing result. Under exact lookup and insert-on-miss protocols, a newly inserted cache entry is mathematically guaranteed not to possess a resident neighbor within the defined similarity hit radius. Consequently, geometry-aware eviction algorithms starve for actionable redundancy signals, rendering their complex spatial calculations largely redundant.
The Pre-Existing Bottleneck
Traditional computer science has spent decades perfecting cache eviction algorithms for exact-match memory systems, such as CPU caches or web proxies. In those domains, tracking access recency (LRU) or frequency (LFU) yields massive performance differentials because every byte is an exact binary match.
Transitioning these concepts to Large Language Models introduced semantic caching, where hits are determined not by exact string matching, but by cosine similarity between high-dimensional vector embeddings. As semantic caching gained popularity to curb GPU inference costs, developers began importing intricate cache eviction policies—such as Adaptive Replacement Cache (ARC) or Greedy-Dual-Size-Frequency (GDSF)—under the assumption that geometric proximity demands spatial eviction logic. This assumption went largely unchallenged until now, lacking a standardized, end-to-end evaluation benchmark to test whether geometric complexity actually translates to higher hit rates in production AI workloads.
How the Mechanism Works
To resolve this ambiguity, the researchers built CLEVER to simulate and stress-test cache behavior under controlled, reproducible conditions. They processed ordered, deduplicated query streams against varying memory budgets, testing how different algorithms decide which cached prompt-response pair to discard when the memory buffer fills up.
The underlying mathematical bottleneck lies in the geometry of high-dimensional vector spaces. When a query misses the cache, the system computes its embedding and inserts it into the memory bank. Because the insertion protocol dictates that any incoming query must fall outside the similarity hit radius of existing entries (otherwise it would have registered as a hit), the local neighborhood of a fresh insertion is completely empty. Sophisticated eviction policies that attempt to analyze the spatial clustering or local density of incoming vectors therefore receive virtually no differentiating signal. They operate on historical access metadata that ultimately correlates no better with future utility than simple access frequency.
Empirical Results & Benchmarks
The study’s experimental sweep evaluated the seven policies across combinations of corpora, capacities, and encoders. The results quantified both the ceiling of algorithmic optimization and a far more alarming reality regarding semantic cache utility.
| Eviction Policy | Performance vs. LFU (Max Delta) | Behavior at Tight Capacity |
|---|---|---|
| LFU (Least Frequently Used) | Baseline (0.00%) | Strongest simple default |
| ARC (Adaptive Replacement) | < 0.041 percentage points | Comparable to LFU |
| GDSF (Greedy-Dual-Size-Frequency) | < 0.041 percentage points | Comparable to LFU |
| FIFO (First-In, First-Out) | Trails by up to 8.67 points | Degraded efficiency |
| Streaming SISO | Trails by up to 8.55 points | Degraded efficiency |
However, the paper’s most disruptive audit targeted the semantic cache hit rate itself. When evaluating the operating point of MiniLM at its median nearest-neighbor threshold, the researchers discovered that only 2.1% to 3.9% of sampled hits from LMSYS and QQP datasets were actually judged answer-substitutable by human or rigorous automated standards. This semantic drift collapses raw cache hit rates of 51% to 60% down to a dismal quality-adjusted hit rate of just 1.1% to 2.2%.
Practical Constraints & Commercial Horizon
These findings impose immediate constraints on how engineering teams should architect LLM caching infrastructure. First, developers can safely abandon complex, memory-heavy spatial eviction algorithms in favor of robust, lightweight LFU implementations, saving computational overhead on the caching layer itself.
Second, and more critically, the commercial viability of semantic caching faces a severe validation bottleneck. High raw hit rates are dangerously misleading if the cached response fails to answer the user’s semantically adjacent query accurately. Furthermore, the cross-encoder study revealed a severe transferability limitation: similarity thresholds do not translate across different embedding models, meaning every swap of an underlying encoder requires recalibrating similarity boundaries from scratch. Production deployment decisions must therefore prioritize rigorous answer-validity checks over micro-optimizations in eviction policy.
Paper & Author Citations
This research was conducted by Yash Kulkarni, Shubham Harkare, and Arvind Suresh Yogesh Babu. The complete study, titled Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders, is available as an open-access preprint via arXiv (arXiv:2608.20280v1).
