Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders

Yash Kulkarni; Shubham Harkare; Arvind Yogesh Suresh Babu

cs.DBAug 20, 2026

Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders

Authors: Yash Kulkarni, Shubham Harkare, Arvind Yogesh Suresh Babu

Organizations: University of Michigan Ann Arbor, Michigan, USA

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.

Figures & tables

Parameter	Symbol	Value	Justification
Recency weight	$\alpha$	1.0	Recency in utility denom.
Frequency weight	$\beta$	1.0	Frequency in utility denom.
Denominator floor	$\varepsilon$	$10^{-9}$	Prevents division by zero
Smoothing constant	$\mu$	0.1	Laplace-style smoothing
Neighbor sample cap	$S$	1024	Bounds $O(S)$ insert cost
Penalty coefficient	$\lambda$	2.0	Suppresses false accepts

Table 1. Hyperparameter configuration for the semantic eviction policy and the adaptive router.

Cache Size	LRU	LFU	Semantic
10%	$0.7802\pm 0.0001$	$\mathbf{0.7835\pm 0.0000}$	$0.7808\pm 0.0000$
20%	$0.8453\pm 0.0000$	$0.8453\pm 0.0000$	$0.8453\pm 0.0000$
30%	$0.8756\pm 0.0000$	$0.8756\pm 0.0000$	$0.8756\pm 0.0000$

Table 2. Cache hit rate (mean

\pm

std) across three seeds (42, 123, 456) at three cache capacities. Differences across policies are at most 0.34 pp in this experiment.

Cache Size	LRU	LFU	Semantic	Sem./LRU
10%	1.45 ms	2.53 ms	8.47 ms	$5.83\times$
30%	1.90 ms	3.67 ms	15.70 ms	$8.24\times$

Table 3. Mean per-query processing time across three seeds. Semantic/LRU reports multiplicative overhead relative to LRU.

	LMSYS			QQP			MOSS
Policy	Raw	YES [95% CI]	QA	Raw	YES [95% CI]	QA	Raw	YES [95% CI]	QA
LRU	55.5	3.6 [2.6, 4.9]	2.0	57.5	2.5 [1.7, 3.7]	1.4	97.6	25.1 [22.5, 27.9]	24.5
LFU	57.0	3.9 [2.9, 5.3]	2.2	60.0	2.6 [1.8, 3.8]	1.6	97.6	26.1 [23.5, 28.9]	25.5
Semantic	55.9	3.1 [2.2, 4.4]	1.7	58.7	3.1 [2.2, 4.4]	1.8	97.6	26.1 [23.5, 28.9]	25.5
ARC	57.0	3.3 [2.4, 4.6]	1.9	60.0	2.6 [1.8, 3.8]	1.6	97.6	26.1 [23.5, 28.9]	25.5
GDSF	56.8	3.9 [2.9, 5.3]	2.2	59.5	2.3 [1.5, 3.4]	1.4	97.6	24.7 [22.1, 27.5]	24.1

Table 4. Judged hit quality at 10% cache (MiniLM, seed 42): raw hit rate (%), answer-substitutable (YES) fraction with Wilson 95% CI (

n{=}1000

per cell), and quality-adjusted hit rate QA

=

Raw

\times

YES (%). Within every dataset the YES intervals of all six policies overlap.

Claim	Artifact
Index Pareto frontier (Fig. 1 )	results/benchmarks/index_benchmark_*.json
Adaptive routing, 60.33% savings at $\theta{=}0.772$ (Fig. 2 )	results/routing/routing_eval_multi_seed.json
Three-policy full-LMSYS eviction (Fig. 3 , Table 2 )	results/eviction/eviction_results_multi_seed.json
Seven-policy matrix (Figs. 4 , 5 )	results/eviction/phase6_matrix_* , results/eviction/phase10_fifo_*
Recalibrated gte-base replication (Sec. 3.5 )	results/eviction/phase6_recal_*
Judged hit quality (Table 4 , Figs. 6 , 7 )	results/judge/ , paper/tables/phase8_judge_table.tex

Table 5. Claim-to-artifact map. Paths are relative to the repository root.

Semantic Caching

Semantic caching reuses results for meaningfully similar queries to reduce the latency and cost of AI, retrieval, and database systems.

See all 22 papers

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches
May 12, 2026Shaoke Fang, Ziang Li, Wenfei Wu +3LLM Inference Efficiency KV Caching
Peking University · FirestAI · Tsinghua University +2
When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Jul 1, 2026Yushi Sun, Bowen Cao, Wai LamLearning-Augmented Algorithms Semantic Caching
LIGHTSPEED, Tencent · Shenzhen, China · The Chinese University of Hong Kong +1
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
Sep 24, 2026Yiyu Liu, Minlan Yu, Juncheng YangLLM Inference Efficiency KV Caching
Harvard University

May 12, 2026J/K move · Enter open · S save

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches

Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji+2

Peking University · FirestAI · Tsinghua University+2

LLM Inference Efficiency KV Caching KV-Cache Eviction Prefix Caching

Open paper AskPDF arXiv

Prefix caching is a key optimization in Large Language Model (LLM) serving, reusing attention Key-Value (KV) states across requests with shared prompt prefixes to reduce expensive prefill computation. However, its benefit depends critically on the eviction policy as GPU memory is scarce, and existing policies such as LRU largely treat cached blocks uniformly. This view ignores a fundamental property of LLM prompts: not all tokens are equally worth caching. We show that different token types within a prompt, including system prompts, user queries, tool outputs, model responses, and chain-of-thought reasoning, exhibit up to 756x variation in reuse rates, yet no existing eviction policy exploits this signal. In this paper, we present SAECache (Semantic-Adaptive Eviction for prefix caches), a semantic-adaptive prefix cache eviction policy that addresses this gap through three innovations: (1) a multi-queue architecture that routes KV blocks to task-specific queues with tailored priority metrics, capturing both session reuse in multi-turn requests and structural reuse in templated single-turn requests; (2) a semantic-aware token weighting mechanism that learns the reuse value of different token types online through eviction feedback; and (3) a fully adaptive online learning schema for all parameter updates, including log-normal timing parameters, position decay power, queue weights, and meta-parameters, which eliminates manual tuning and enables automatic adaptation to deployment-specific workload characteristics. Through extensive evaluation across heterogeneous workloads, we demonstrate that SAECache achieves 1.4x-2.7x TTFT improvement over production-style baselines, while fixed-parameter alternatives can degrade by up to 2.7x under workload mismatch -- a failure mode our adaptive approach avoids entirely.

Abstract

Semantic Caching

Explore similar work

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches

When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse