Similarity Is Not Validity: Defending LLM Semantic Caches Against Poisoning

Zihan Zhang; Shuangjie Yao; Zesen Liu; Zhixiang Zhang; Wai Ip Lai; Dung Hiu Hilton Yeung; Chun Kit Zhang; Fuchen Ma

cs.CRSep 28, 2026

Similarity Is Not Validity: Defending LLM Semantic Caches Against Poisoning

Authors: Zihan Zhang, Shuangjie Yao, Zesen Liu, Zhixiang Zhang, Wai Ip Lai, Dung Hiu Hilton Yeung, Chun Kit Zhang, Fuchen Ma, +3 more

Organizations: The Hong Kong University of Science and Technology · Tsinghua University

Abstract

Semantic caches reduce LLM serving costs by reusing previously generated answers for semantically similar queries. However, retrieval is based solely on embedding similarity between the incoming query and cached queries. This design enables cache poisoning: an attacker can cache a malicious response under a query with high cosine similarity to benign requests. The vulnerability stems from a gap between retrieval similarity and answer validity. From an information-bottleneck perspective, query embeddings can lose information needed to distinguish valid from invalid cache hits, which limits any matching algorithm that uses only these embeddings. We propose a novel defense that recovers this necessary information from the raw text of the cache key. Across poisoning attacks, adversarial queries share a rewrite-residual structure: they pair a rewrite of the target query with residual content. The rewrite maintains high similarity, while the residual elicits the malicious response. Deleting the residual makes the remaining rewrite more similar to the incoming query. We exploit this structure using Deletion Gain to search shortened variants of the cached query for similarity gains, and an Answer Check to test whether the removed text contributes to the stored answer. We prove that Deletion Gain stays positive when a deletion leaves text close enough to the rewrite, and we search for such deletions with a sliding window. Across three poisoning attack classes, our defense blocks 82.0% to 98.2% of poisoned entries at a 5% false-positive rate, with negligible serving overhead.

Figures & tables

Figure 1: Deletion increases the similarity score of the poisoned entry. Both entries pass the retrieval threshold for the incoming query. The benign key is a paraphrase of the query, and the poisoned key adds a residual (red box) to a rewrite of the query. Deletion Gain deletes segments of the key (dashed boxes) and takes the largest change in cosine similarity to the query. For the benign key, every deletion lowers similarity, so the cache serves the hit. For the poisoned key, deleting the residual increases similarity, so the cache rejects the hit.

Figure 2: Cache poisoning and our defense. (1) The attacker sends a poisoned key that combines a rewrite of the target query with a residual. The LLM returns a malicious answer

y

, and the cache stores the key with this answer. (2) A benign query

q

hits this poisoned entry. Deletion Gain deletes part of the key, and the resulting shortened key is more similar to the query than the full key. The Answer Check triggers when this deletion lowers similarity to the stored answer. When both checks trigger, the cache rejects the hit and the LLM answers the query.

Method	CAP ( $n{=}800$ )		SCP ( $n{=}798$ )		KCA ( $n{=}798$ )		Worst		ms/hit $\downarrow$
Method	BR $\uparrow$	ASR $\downarrow$	BR $\uparrow$	ASR $\downarrow$	BR $\uparrow$	ASR $\downarrow$	BR $\uparrow$	ASR $\downarrow$	ms/hit $\downarrow$
Cosine	0.240	0.220	0.372	0.486	0.955	0.041	0.240	0.486	-
Perplexity	0.046	0.278	0.024	0.788	0.425	0.531	0.024	0.788	78.7
Multi-embedding	0.313	0.211	0.361	0.496	0.986	0.013	0.313	0.496	20.8
Key salting	0.375	0.184	0.614	0.276	1.000	0.000	0.375	0.276	-
LLM judge	0.723	0.064	0.695	0.236	1.000	0.000	0.695	0.236	4440

Table 1: Block rate, end-to-end attack success, and serving overhead on e5. All metrics use the same poisoned entries and a 5% FPR budget. ASR includes retrieval and the judge’s label. Bold and underline mark the best and second-best values per column. Worst takes the lowest BR and highest ASR over the three classes. A dash marks no added cost.

Table 2: Adaptive robustness and transfer across embedding models at a 5% FPR budget.

Figure 3: Adaptive robustness and serving cost. Left: retrieved search candidates that our defense blocks or accepts, as a share of all retrieved candidates. Hatching marks poisoned responses, and labels give the poisoned share of each bar. Round 1 holds the attacker’s first candidates, and round 2 holds its revised candidates after it sees their DG scores. Right: mean BR at 5% FPR versus added serving latency for Ours and the baselines.

Figure 4: Cosine overlap and DG separation (CAP, e5). Left: benign and poisoned entries overlap in cosine similarity above the retrieval threshold. Right: DG separates them.

Figure 5: Detection–cost trade-off across segmentations. Rows rank segmentations by DG-only worst-class BR. The right columns give relative serving cost and the DG threshold. Diamonds mark the Pareto frontier. Open markers cannot segment some short benign keys.

	LMArena	Search	Classif.
Prompts	63,796	60,000	45,000
Valid hits (%)	15.8	14.2	53.3
FPR (%) $\downarrow$	5.3	5.0	5.9
Hit-rate loss (%)	30.6	3.5	7.4

Table 3: Real prompts from the vCache benchmarks at

\tau=0.90

. FPR is on held-out valid hits. Hit-rate loss is the fraction of held-out hits that Ours rejects.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

			Detection		ASR $\downarrow$
Class	Construction	$n$	AUC $\uparrow$	BR $\uparrow$	None	Cosine	Ours
CAP	compress-append	267	0.976	0.929	0.356	0.221	0.004
	blend	267	0.974	0.831	0.371	0.288	0.007
	fuse	266	0.940	0.699	0.173	0.150	0.008
	Overall	800	0.963	0.820	0.300	0.220	0.006
SCP	introduce	267	0.984	0.884	0.517	0.457	0.064

Appendix

Table 4: Detection and end-to-end attack success by construction on e5. All metrics use the same entries; Cosine and Ours use a 5% FPR budget.

Attack	LLM judge	Erase-and-check	Salt prefix	Salt suffix	Salt template	LaCache bge-large	LaCache e5	AUC $\uparrow$	BR $\uparrow$	ASR $\downarrow$
	Flag rate		Block rate (BR)			AUC		NLI
CAP	0.743	0.000	$0.349\pm 0.045$	0.265	0.286	0.752	0.758	0.942	0.685	0.098
SCP	0.752	0.000	$0.587\pm 0.047$	0.502	0.507	0.761	0.761	0.952	0.675	0.252
KCA	1.000	1.000	$0.999\pm 0.001$	1.000	0.999	0.998	0.997	0.977	0.878	0.117

Appendix

Table 5: Additional baseline results across the three attack classes. Flag rates use each method’s native decision rule. Salt BRs are means over five salts, with the s.d. shown for the prefix placement. NLI uses the same poisoned entries, benign controls, and 5% FPR budget as Table 1 .

Method	CAP ( $n{=}800$ )			SCP ( $n{=}798$ )			KCA ( $n{=}798$ )
Method	AUC $\uparrow$	BR $\uparrow$	ASR $\downarrow$	AUC $\uparrow$	BR $\uparrow$	ASR $\downarrow$	AUC $\uparrow$	BR $\uparrow$	ASR $\downarrow$
Full-key Echo	0.738	0.215	0.280	0.836	0.346	0.516	0.979	0.941	0.011
Answer Check only	0.860	0.663	0.033	0.955	0.828	0.104	0.985	0.975	0.018
Response perplexity	0.754	0.408	0.048	0.790	0.546	0.278	0.832	0.476	0.461
LLM judge + answer	0.716	0.000	0.300	0.743	0.000	0.802	0.839	0.000	0.916
Qwen3-8B judge	0.843	0.414	0.199	0.757	0.237	0.617	0.999	1.000	0.000

Appendix

Table 6: Ablations and answer-aware baselines on e5 on the entries of Table 1 , at a 5% FPR budget. The Answer Check alone has two thresholds, and its AUC is the upper envelope over both. “+ answer” adds the stored answer to the judge prompt. Green marks the best value per column.

	CAP				SCP				KCA
Method	10%	5%	2%	1%	10%	5%	2%	1%	10%	5%	2%	1%
Cosine	0.439	0.240	0.123	0.070	0.628	0.372	0.185	0.061	0.996	0.955	0.806	0.569
Perplexity	0.120	0.046	0.019	0.015	0.054	0.024	0.009	0.005	0.560	0.425	0.243	0.118
Response perplexity	0.504	0.408	0.305	0.256	0.579	0.546	0.491	0.455	0.551	0.476	0.407	0.341
NLI	0.848	0.685	0.379	0.264	0.805	0.675	0.510	0.444	0.984	0.878	0.604	0.436
Multi-embedding	0.480	0.313	0.196	0.104	0.640	0.361	0.174	0.058	0.996	0.986	0.871	0.739

Appendix

Table 7: BR at four nominal FPR budgets (e5), with thresholds refit at each budget. “+ answer” adds the stored answer to the judge prompt. Green: best per class and budget.

Method	CAP	SCP	KCA
Cosine	0.844	0.905	0.986
Perplexity	0.585	0.528	0.827
Multi-embedding	0.845	0.905	0.990
Key salting	0.872	0.948	0.998
LLM judge	0.918	0.939	0.999
LaCache	0.758	0.761	0.997

Appendix

Table 8: AUC on e5 for the entries of Table 1 . Ours reports Deletion Gain, since its conjunction with the Answer Check has no ranking score. Bold and underline mark the best and second-best values per column.

BR over all poisoned entries
Method	CAP	SCP	KCA
Cosine	0.240 [0.174, 0.360]	0.372 [0.263, 0.519]	0.955 [0.927, 0.986]
Perplexity	0.046 [0.022, 0.082]	0.024 [0.011, 0.041]	0.425 [0.332, 0.511]
NLI	0.685 [0.488, 0.770]	0.675 [0.572, 0.737]	0.878 [0.738, 0.964]
Multi-embedding	0.313 [0.234, 0.406]	0.361 [0.265, 0.490]	0.986 [0.955, 0.995]
Key salting	0.375 [0.265, 0.512]	0.614 [0.534, 0.725]	1.000 [1.000, 1.000]

Appendix

Table 9: 95% confidence intervals for Tables 1 and 2(b) , with NLI from Table 5 . AUC uses DG; BR uses Ours in the model comparison. Intent-grouped bootstrap; LaCache BR uses conditional Wilson intervals (Appendix D.5 ).

Model	Pooling	Collision	Cosine AUC $\uparrow$	Matched AUC $\uparrow$	BR $\uparrow$
e5	CLS	0.964	0.844	0.939	0.820
e5	Mean + prefix	0.956	0.837	0.910	0.813
gte	CLS	0.993	0.826	0.908	0.735
gte	Mean	0.979	0.846	0.903	0.785
MiniLM	CLS	0.673	0.789	0.902	0.705
MiniLM	Mean	0.543	0.815	0.873	0.735

Appendix

Table 10: Pooling recipes on CAP. Collision is the fraction of poisoned entries passing the retrieval threshold. Native recipes match the CLS benign hit rate. Matched AUC uses DG only; BR uses Ours. Green compares recipes within each model.

Input	Answer	Attack labels	Blocked $\uparrow$	AUC $\uparrow$	ComQA	Natural Questions
	Uses				Wrapper FPR $\downarrow$
Key and query embeddings	✗	✓	0.615	0.572	0.074	0.035
+ answer embedding	✓	✓	0.763	0.736	0.066	0.034
DG, ADL, and Echo	✓	✓	0.967	0.769	0.088	0.095
Ours	✓	✗	0.979	–	0.076	0.096

Appendix

Table 11: Information bottleneck test on e5, with CAP held out from training (5% FPR budget on bare benign entries, means over five seeds). Blocked is the share of poisoned CAP hits that are blocked, and AUC separates poisoned from failed CAP attacks. Wrapper FPR uses the LLM-written wrappers of Table 13 . Green marks the best value of each metric.

Attack	$n$	P1	$\mathrm{DG}>\eta$	$\gamma$	$\delta^{\ast}$	$\cos(E(s^{\ast}),E(r))$
CAP compress-append	267	0.880	0.970	0.019	$-0.004$	0.994
SCP	798	0.987	0.989	0.034	0.000	0.997

Appendix

Table 12: Recovery on attacks with a known rewrite

r

(e5). P1 and

\mathrm{DG}>\eta

are fractions of entries, and the last three columns are medians.

\delta^{\ast}=\cos(E(r),E(q))-\cos(E(s^{\ast}),E(q))

, so that

\mathrm{DG}=\gamma-\delta^{\ast}

Table 13: Harmless-wrapper FPR (

\downarrow

) on e5, with Ours jointly calibrated on bare benign hits at a 5% budget. Green marks the best value per row.

Configuration	Successes / attacks	ASR (%) $\downarrow$	FPR (%) $\downarrow$
DG only	14/442	3.17	3.65
DG + Answer Check, fixed $\eta$	16/442	3.62	1.46
DG + Answer Check, joint calibration	4/442	0.90	5.11

Appendix

Table 14: Answer Check ablation on KCA with held-out intents (e5). Thresholds are calibrated on 225 benign intents, and 274 held-out intents provide 442 attack and 274 benign pairs. All rows use

\tau=0.90

. The second row keeps the DG-only threshold, and the third row refits it at the same nominal 5% FPR budget. A success requires retrieval, acceptance, and an injection-success verdict. Without a defense, ASR is 90.95%. Cosine-only ASR and FPR are 3.62% and 4.74%.

Suffix	$\lambda=0$	$\lambda=1$	$\lambda=5$
4 words	0.583 $\to$ 0.104	0.583 $\to$ 0.063	0.583 $\to$ 0.063
8 words	0.604 $\to$ 0.104	0.583 $\to$ 0.125	0.583 $\to$ 0.063

Appendix

Table 15: Known-query gradient attack by loss weight

\lambda

and suffix length. Each cell gives ASR without a defense

\to

with Ours.

	GPTCache	+ DG only	+ DG + Answer Check (Ours)
Served from the cache	1.000	0.936	0.926
Served from a poisoned entry	0.016	0.005	0.004
Served a poisoned answer	0.004	0.000	0.000

Appendix

Table 16: GPTCache workload replay. Each cell is a share of all queries in the trace.

Attack class	Variants per entry	Latency p50 (ms/hit)	Latency p95 (ms/hit)	Storage (kB/entry)
CAP	15	0.021	0.022	11.4
SCP	65	0.060	0.065	49.7
KCA	135	0.115	0.120	103.7

Appendix

Table 17: Verification cost per attack class. Latency covers the complete check on one CPU thread. Storage counts the float16 variant vectors of one entry.

Explore similar work

LaCache: Robust Semantic Caching for LLM Serving
Aug 3, 2026Jiacheng Liang, Yuhui Wang, Tanqiu Jiang +1Attacker Large Language Model Large Language Model Serving
Stony Brook University
From Similarity to Vulnerability: Key Collision Attack on LLM Semantic Caching
Jan 30, 2026Zhixiang Zhang, Zesen Liu, Yuchong Xie +2Attacker Large Language Model Large Language Model Memory
Department of Computer Science and Engineering, The Hong Kong University of Science and Technology · Fudan University
MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
May 24, 2026Ali Noshad, Zishan Zheng, Yinjun WuCache Similarity and Metrics
School of Computer Science, Peking University, Beijing, China · School of Information, Renmin University of China, Beijing, China

Aug 3, 2026, cs.AIJ/K move · Enter open · S save

LaCache: Robust Semantic Caching for LLM Serving

Jiacheng Liang, Yuhui Wang, Tanqiu Jiang, Ting Wang

Stony Brook University

Attacker Large Language Model Large Language Model Serving

Open paper AskPDF arXiv

Semantic caching, which reuses responses to semantically similar requests via their embeddings, has seen growing adoption in LLM serving, offering faster responses and reduced costs. Yet existing schemes are fundamentally vulnerable to cache-collision attacks, wherein an adversary pollutes the cache by injecting crafted queries, corrupting responses to subsequent legitimate requests. We present LaCache, a novel semantic caching scheme that addresses this vulnerability through a conceptually simple yet principled redesign. The key insight is that while the adversary has full control over the adversarial query, it has far less control over its response, which must simultaneously satisfy multiple semantic constraints. Rather than checking only the cache hit of a query, LaCache additionally checks the cache hit of its first k (speculatively) decoded tokens. This design yields two concrete benefits. First, it provides formally guaranteed resilience against cache-collision attacks: we prove that it is impossible to craft adversarial queries that simultaneously elicit malicious responses and collide with benign queries. Second, the enriched index supplies additional semantic context for cache retrieval, improving response relevance. Empirical evaluation across diverse LLMs and benchmarks validates both LaCache's security guarantees and efficiency gains, pointing to a promising direction for robust semantic caching.

Abstract

Explore similar work

LaCache: Robust Semantic Caching for LLM Serving

From Similarity to Vulnerability: Key Collision Attack on LLM Semantic Caching

MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation