As large language models (LLMs) become more common in applications like chatbots and search engines, optimizing how they handle repeated queries is increasingly important. One promising approach is semantic caching, which reuses previous LLM responses when new queries are similar enough to cached ones. But a key question remains: when the cache is full, which eviction policy—i.e., which cached entry to remove—best balances storage limits and response quality? A newly published research paper systematically compares several popular cache eviction strategies to find out.
Key Takeaways
- Among multiple eviction policies tested—including FIFO, LRU, LFU, ARC, GDSF, and others—Least Frequently Used (LFU) consistently performs best or near-best across various workloads, cache sizes, and query encoders.
- Some policies like FIFO and streaming adaptations of SISO lag behind LFU by significant margins, especially when cache capacity is tight.
- The study reveals that semantic redundancy signals (how much a new query overlaps with cached ones) provide limited guidance for eviction decisions under current exact lookup methods.
- Only a small fraction (around 2-4%) of cache hits actually produce valid answer substitutions, suggesting that raw hit rates overestimate the practical benefit of semantic caching.
Semantic caching works by storing embeddings—numerical representations—of past queries and their responses. When a new query arrives, the system compares its embedding to those in the cache. If a close enough match is found, the cached response can be reused, saving computational effort and speeding up responses. However, caches have limited size, so deciding which cached entry to evict when adding a new one is crucial. Eviction policies like FIFO (first-in, first-out), LRU (least recently used), and LFU (least frequently used) have been widely studied in traditional caching but their effectiveness in semantic caching for LLMs had not been comprehensively evaluated under consistent testing conditions.
To address this, the researchers used a benchmarking framework called CLEVER to evaluate seven eviction policies across three different query datasets, three cache sizes, and two embedding encoders. These policies ranged from simple heuristics like FIFO to more complex ones like ARC (adaptive replacement cache) and GDSF (greedy dual-size frequency). They also tested a semantic-redundancy policy that tries to evict entries based on how much they overlap semantically with new queries.
The study found that LFU uniformly outperformed or matched other policies in hit rates, though the margin over the next best policy was small—no more than 0.041 percentage points in any tested scenario. In contrast, FIFO and the streaming SISO method performed noticeably worse, especially when the cache was small. The researchers explain this by showing that under exact lookup conditions—where a new query must be within a strict embedding distance to count as a hit—a newly inserted cache entry rarely has a neighboring entry within that distance. This limits the usefulness of eviction policies that rely on semantic redundancy signals.
Perhaps more strikingly, the team conducted an audit of cache hits to assess their actual usefulness. They found that while raw hit rates ranged from 51% to 60%, only about 2.1% to 3.9% of those hits were judged to be substitutable answers—meaning the cached response would be an appropriate substitute for the new query. This suggests that many cache hits might be superficial matches that do not truly save computation or improve response quality. Additionally, the study showed that thresholds for deciding hits do not transfer well between different embedding models, complicating deployment decisions.
These findings highlight important considerations for organizations looking to implement semantic caching in LLM-powered systems. LFU stands out as a strong default eviction policy under current protocols, but the overall effectiveness of semantic caching depends heavily on verifying that cache hits correspond to valid answer substitutions. Future work may explore more flexible matching methods and embedding models that better capture answer relevance. For now, system designers should carefully evaluate answer validity before focusing on fine-tuning eviction strategies.
Based on research published on arXiv by Yash Kulkarni, Shubham Harkare, Arvind Suresh Yogesh Babu.