Evaluating Cache Eviction Policies for LLMs
Listen to the summary
Uses a voice available on your device
Audio options
On this page 4 sections
Related concepts 2 concepts
Key Takeaways
- Least Frequently Used (LFU) consistently outperforms other eviction policies across eighteen tested configurations.
- At tight cache capacities, both FIFO and streaming SISO policies trail LFU by margins as high as 8.67 and 8.55 percentage points.
- No tested policy improved upon LFU by more than 0.041 percentage points.
- Raw hit rates for semantic caches can be misleading, as quality-adjusted hit rates drop from 51 to 60 percent down to 1.1 to 2.2 percent.
Summary & Methodology Analysis
The researchers evaluated cache eviction strategies using datasets including LMSYS-Chat-1M, Quora Question Pairs, and MOSS. Queries were encoded into 384-dimensional vectors using the all-MiniLM-L6-v2 sentence-transformer, with additional testing using the 768-dimensional gte-base encoder. The study focused on standard metrics like hit rate, but also introduced a quality-adjusted hit rate audit to measure whether cached responses are truly answer-substitutable, rather than just semantically similar. This audit revealed that while raw hit rates might look high, the utility of the cached responses is significantly lower than expected.
Interactive System Flowchart
Cross-Examination & FAQs
A deeper dive clarifying mechanics, constraints, and baseline evaluations.
Q1. Does a more complex eviction policy lead to better cache performance?
No. The study shows that no evaluated policy improved on LFU by more than 0.041 percentage points across eighteen settings.
Q2. Does cache capacity matter when choosing an eviction policy?
Yes. At tight cache capacity, simpler policies like FIFO and streaming SISO perform significantly worse than LFU, trailing by up to 8.67 and 8.55 percentage points.
Q3. What is the main finding regarding hit rates?
Raw hit rates can be deceptive. While raw hit rates reached 51 to 60 percent, quality-adjusted rates dropped to 1.1 to 2.2 percent after accounting for answer-substitutability.
Q4. What datasets were used in this evaluation?
The study used LMSYS-Chat-1M, Quora Question Pairs, and MOSS.
Q5. Which encoders were used to process queries?
The researchers used the all-MiniLM-L6-v2 model for 384-dimensional vectors and the gte-base model for 768-dimensional vectors.
Q6. What are the limitations of the input data used?
The eviction inputs use ordered, deduplicated corpora rather than production request traces.
Q7. Does the quality-adjusted hit rate result apply to the entire experiment?
No. The audit was performed on a sample covering MiniLM, seed 42, 10 percent capacity, and six policies; it does not extend to the full experimental matrix.
Q8. Does the packing condition used account for all LLM scenarios?
No. The packing condition assumes exact insert-on-miss and does not cover arbitrary prefill, approximate-search errors, or policies that change stored representations.
Q9. How do FIFO and streaming SISO compare to LFU?
At tight capacity, they perform worse, trailing LFU by as much as 8.67 and 8.55 percentage points respectively.