LFU was hard to beat
A benchmark of seven rules for deciding which entries to remove from an LLM’s semantic cache found almost no advantage over LFU, the least-frequently-used policy. Across 18 dataset–capacity–encoder settings, the biggest gain over LFU was 0.041 percentage points, recorded by GDSF on LMSYS at 20% capacity with MiniLM.
The result did not mean every policy performed alike. FIFO and streaming SISO trailed LFU by as much as 8.67 and 8.55 percentage points, respectively, when capacity was tight. The comparison gave every policy the same ordered corpus, index, threshold, measured suffix and cache capacity.
The hit-rate problem
The test used three ordered, deduplicated corpora of 100,000 queries each: LMSYS, Quora Question Pairs and MOSS.
Raw hits looked much better than answer-substitutable hits. At the 0.90 distance threshold, LMSYS produced raw hit rates of 50.7% to 57.0%, but only 1.6% to 2.2% remained after the audit judged whether the cached answer could be substituted. QQP fell from 51.4–60.0% to 1.1–1.8%, while MOSS fell from 97.6% to 24.1–26.4%.
The audit did not establish a quality ranking among the policies. Within each dataset, the Wilson 95% intervals for the judged YES fractions of all six audited policies overlapped, so the sample could not show a quality difference between them.
The check was directional rather than a human-validated quality score, using one judge family and no human labels. Its adjusted rates should therefore be read as evidence from the tested audit, not as a definitive measure of answer quality.
Engineering choices changed the picture
The primary setup used 384-dimensional all-MiniLM-L6-v2 vectors; a replication re-embedded all three datasets with 768-dimensional gte-base vectors. When the MiniLM-calibrated 0.90 distance threshold was carried directly over to gte-base, every tested query hit: the final hit rate was exactly 1.0, with zero misses and zero evictions.
A separate benchmark with 499,000 vectors found HNSW, an approximate vector-search index, reached Recall@1 of 0.989 at a median latency of 0.52 milliseconds. Exact Flat search took 17.4 milliseconds, making HNSW 34 times faster in that test, but with a 1.1-point recall loss.
That trade-off is important when reading the policy comparison. HNSW was used for every policy, and its static Recall@1 loss was 2.2 percentage points—larger than the leading-policy differences. The study notes that false misses can change the later cache state, so exact-index replication is needed before treating sub-point rankings as robust.
A possible explanation for the weak semantic showing
The authors point to a possible structural reason semantic policies gained so little. Under the stated exact insert-on-miss condition, an inserted entry has no redundancy edge to a resident entry when the redundancy radius r is no larger than the hit radius h. That leaves little resident overlap for a redundancy-based rule to use.
The reference LMSYS cache also showed sparse local redundancy: only 0.43% of 36.7 million pairwise distances were at or below the 0.90 eviction threshold, and 0.29% were at or below the router threshold. Across the semantic runs, mean redundancy was 2.2–2.9 × 10−5, with a maximum observed value of 0.035.
A baseline, not a universal verdict
In a separate random-fill routing experiment, the selected threshold averaged 0.772 ± 0.015, alongside a 60.43% hit rate and 60.33% nominal latency savings. The router used cosine similarity as a quality proxy rather than answer-grounded validation, so those savings do not by themselves show that the returned answers were substitutable.
The practical conclusion is narrow. Under this protocol, LFU is a reasonable baseline for cache eviction, but the study does not show that it is best on production traces, workloads with repetition or other cache semantics. The results instead point to two checks before further tuning: calibrate thresholds for each encoder and validate answer substitutability.
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