Least-frequently-used (LFU) replacement—the rule that favors entries used most often—was the hardest policy to beat in a broad test of semantic caches for large language models. Across 18 dataset–capacity–encoder settings, the largest reported gain over LFU was 0.041 percentage points, from GDSF on LMSYS at 20% capacity with MiniLM.
Researchers compared seven eviction policies—the rules that decide which stored entries to remove when a cache fills—on three ordered, deduplicated corpora: LMSYS-Chat-1M, Quora Question Pairs and MOSS. Each contained 100,000 processed queries. The tests used cache capacities of 10%, 20% and 30% of each corpus and two embedding encoders.
The gap showed up under pressure
Queries were processed in row order after exact repetitions were removed, and the fixed final 70% was measured after a capacity-sized prefill. The system combined an index benchmark, a cost-based router, a seven-policy eviction layer and an LLM-based audit of whether a sampled hit could substitute for an answer.
The clearest separation appeared at the tightest capacity tested. At 10% with MiniLM, LFU reached a 57.0% hit rate on LMSYS and 60.0% on QQP. FIFO was 6.33 percentage points lower on LMSYS and 8.67 points lower on QQP; streaming SISO was 6.34 and 8.55 points lower.
As capacity increased, hit rates rose and the LFU–LRU gap narrowed. Yet the more elaborate policies remained expensive: semantic eviction took 5.83 to 8.24 times LRU’s per-query time, while streaming SISO took 2.8 to 5.2 times LRU’s time in sparse cells. In the reported MiniLM LRU profile at 10% capacity, the largest measured density was 2.5 × 10−3, 40 times below μ = 0.1, supporting the authors’ view that little redundancy signal was available for geometry-aware eviction.
The embedding model changed the benchmark
Applying the MiniLM-calibrated 0.90 threshold to gte-base produced a degenerate result: a 1.0 hit rate with zero misses and zero evictions. After recalibration, ARC and LFU were within 0.01 percentage points in all nine dataset–capacity cells, but at 10% LMSYS capacity LFU was 0.760 with gte-base versus 0.570 with MiniLM, a 19.0-point difference.
That makes the similarity threshold a central part of the comparison, not a setting that can simply be copied between encoders. In a random-cache-fill router benchmark, the five-seed mean threshold was 0.772 ± 0.015, with a 60.43% hit rate and 60.33% nominal latency savings. The quality audit, however, used a 0.90 threshold.
A hit was not always a reusable answer
At that 0.90 threshold, the raw LMSYS hit rate ranged from 50.7% to 57.0%, but the quality-adjusted rate—raw hits multiplied by judged answer-substitutability—was only 1.6% to 2.2%. QQP showed the same warning: 51.4% to 60.0% raw versus 1.1% to 1.8% quality-adjusted.
MOSS produced a much higher raw hit rate of 97.6%, yet its quality-adjusted rate was 24.1% to 26.4%. The audit did not establish a quality ranking among the six policies it examined: the Wilson 95% intervals for YES judgments overlapped within each dataset. Two judge runtimes agreed on 98.55% of 1,931 overlapping verdicts, with Cohen’s κ = 0.826.
A useful baseline, not a universal rule
The conclusion is bounded by the replay design. The eviction inputs were ordered, deduplicated corpora rather than production request traces, and the policy matrix used approximate HNSW search. In a separate benchmark on 499K vectors, HNSW achieved Recall@1 of 0.989 at P50 latency of 0.52 ms—34 times faster than exact Flat search, with a 1.1-point recall loss.
For semantic-cache engineering, the practical message is modest: LFU is a strong simple baseline under this protocol, while threshold calibration and answer validity deserve attention before small policy differences are treated as meaningful. The preprint does not establish universal LFU optimality, answer-preserving latency savings or live-production performance.
The document is an arXiv preprint dated 20 Aug 2026. Its code, configuration files, raw result artifacts and per-run provenance manifests are available from the authors on request.
Paper data and sources
Original title: Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders
Authors: Yash Kulkarni, Shubham Harkare, Arvind Suresh Yogesh Babu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text