SmartEvict: An Empirical Study of Learned and Heuristic Eviction Policies for Semantic LLM Caches

Semantic LLM caches require effective eviction policies to manage limited capacity while minimizing regeneration cost. Most deployed systems rely on simple recency-based heuristics such as LRU or FIFO. Recent work suggests that learned, cost-aware eviction policies could outperform these baselines, but it remains unclear whether such policies outperform strong cost-aware heuristics under realistic conversational workloads. We present SmartEvict, a learned cost-aware semantic cache eviction policy, and perform an extensive empirical evaluation against LRU, FIFO, GDSF, and CostWeightedRecency across synthetic workloads and three real conversational traces (LMSYS-Chat-1M, WildChat-1M, and a customer-support corpus). Across the evaluated workloads, cost-aware policies—learned and heuristic alike—consistently outperform recency-only baselines. However, strong cost-aware heuristics, particularly GDSF, remain highly competitive with and frequently exceed the learned policy. Across the three evaluated real-world conversational traces, we observe a relationship, consistent in direction and magnitude but based on only three independent data points, between a workload's reuse density (measured as the fraction of eviction candidates never previously reused) and the relative advantage of the heuristic policy. We additionally identify cache pressure as a second, partially understood axis that can shift this relationship independently of reuse density. These results suggest that selecting a semantic cache eviction policy should depend on measurable workload characteristics rather than assuming that learned policies universally dominate heuristic approaches. We find that strong cost-aware heuristics remain difficult to surpass, and identify measurable workload characteristics associated with their advantage-providing empirical guidance for policy selection in semantic caching systems.