Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders
2026-08-20 • Databases
DatabasesMachine Learning
AI summaryⓘ
The authors tested several ways to decide which stored answers to keep or remove in a system that reuses responses from language models based on query similarity. They found that the LFU (Least Frequently Used) method worked best and others didn't improve much. They explain that the system's design limits the benefit of more complex eviction methods due to how new entries are added and matched. Additionally, they discovered that many 'hits' in the cache aren't actually interchangeable answers, reducing the effective usefulness of semantic caching. Finally, thresholds used to decide similarity don't work the same across different embedding models.
semantic cachelanguage modelquery embeddingcache eviction policyLFUnearest neighborembedding thresholdanswer substitutabilitycross-encoderexact lookup
Authors
Yash Kulkarni, Shubham Harkare, Arvind Suresh Yogesh Babu
Abstract
Semantic caches reuse an LLM response when the incoming query embedding lies near a cached query, but proposed eviction policies have rarely been compared under one protocol. Using CLEVER, we evaluate FIFO, LRU, LFU, ARC, GDSF, a single-pass streaming adaptation of SISO, and a semantic-redundancy policy across three ordered, deduplicated query corpora, three cache capacities, and two encoders. No evaluated policy improves on LFU by more than 0.041 percentage points in any of the eighteen settings. Replacement is not irrelevant: FIFO and streaming SISO trail LFU by as much as 8.67 and 8.55 points, respectively, at tight capacity. We explain the missing upside with a conditional packing result. Under exact lookup and insert-on-miss, a newly inserted entry cannot have a resident neighbor within the hit radius, so a geometry-aware eviction rule receives little new redundancy signal. A separate audit exposes a larger problem with the evaluated operating point. At MiniLM's median nearest-neighbor threshold, only 2.1-3.9% of sampled LMSYS and QQP hits are judged answer-substitutable, reducing raw hit rates of 51-60% to quality-adjusted rates of 1.1-2.2%. The cross-encoder study further shows that thresholds do not transfer between embedding models. LFU is the strongest simple default in this protocol; deployment decisions should first establish answer validity and then test sub-point policy differences with exact search.