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 ↓
BR ↑
ASR ↓
BR ↑
ASR ↓
BR ↑
ASR ↓
BR ↑
ASR ↓
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 (%) ↓
5.3
5.0
5.9
Hit-rate loss (%)
30.6
3.5
7.4
Table 3: Real prompts from the vCache benchmarks at τ=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 ↓
Class
Construction
n
AUC ↑
BR ↑
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.
Flag rate
Block rate (BR)
AUC
NLI
Attack
LLM judge
Erase-and-check
Salt prefix
Salt suffix
Salt template
LaCache bge-large
LaCache e5
AUC ↑
BR ↑
ASR ↓
CAP
0.743
0.000
0.349±0.045
0.265
0.286
0.752
0.758
0.942
0.685
0.098
SCP
0.752
0.000
0.587±0.047
0.502
0.507
0.761
0.761
0.952
0.675
0.252
KCA
1.000
1.000
0.999±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 )
AUC ↑
BR ↑
ASR ↓
AUC ↑
BR ↑
ASR ↓
AUC ↑
BR ↑
ASR ↓
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.
Method
CAP
SCP
KCA
BR over all poisoned entries
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 ↑
Matched AUC ↑
BR ↑
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.
Uses
Wrapper FPR ↓
Input
Answer
Attack labels
Blocked ↑
AUC ↑
ComQA
Natural Questions
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
DG>η
γ
δ∗
cos(E(s∗),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 DG>η are fractions of entries, and the last three columns are medians. δ∗=cos(E(r),E(q))−cos(E(s∗),E(q)) , so that DG=γ−δ∗ .
Table 13: Harmless-wrapper FPR ( ↓ ) 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 (%) ↓
FPR (%) ↓
DG only
14/442
3.17
3.65
DG + Answer Check, fixed η
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 τ=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
λ=0
λ=1
λ=5
4 words
0.583 → 0.104
0.583 → 0.063
0.583 → 0.063
8 words
0.604 → 0.104
0.583 → 0.125
0.583 → 0.063
Appendix
Table 15: Known-query gradient attack by loss weight λ and suffix length. Each cell gives ASR without a defense → 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.
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.
Semantic caching has emerged as a pivotal technique for scaling LLM applications, widely adopted by major providers including AWS and Microsoft. By utilizing semantic embedding vectors as cache keys, this mechanism effectively minimizes latency and redundant computation for semantically similar queries. In this work, we conceptualize semantic cache keys as a form of fuzzy hashes. We demonstrate that the locality required to maximize cache hit rates fundamentally conflicts with the cryptographic avalanche effect necessary for collision resistance. Our conceptual analysis formalizes this inherent trade-off between performance (locality) and security (collision resilience), revealing that semantic caching is naturally vulnerable to key collision attacks. While prior research has focused on side-channel and privacy risks, we present the first systematic study of integrity risks arising from cache collisions. We introduce CacheAttack, an automated framework for launching black-box collision attacks. We evaluate CacheAttack in security-critical tasks and agentic workflows. It achieves a hit rate of 86% in LLM response hijacking and can induce malicious behaviors in LLM agent, while preserving strong transferability across different embedding models. A case study on a financial agent further illustrates the real-world impact of these vulnerabilities. Finally, we discuss mitigation strategies.
Zhixiang Zhang, Zesen Liu, Yuchong Xie +2
Department of Computer Science and Engineering, The Hong Kong University of Science and Technology · Fudan University
To reduce LLM costs and latency, semantic caching systems must accurately identify when a new prompt matches a cached one. Current methods often rely on simplistic similarity measures, which limit their effectiveness. We introduce MVR-cache, a novel semantic caching approach that significantly improves retrieval accuracy by integrating Multi-Vector Retrieval (MVR). MVR-cache is built upon a learnable segmentation model that intelligently splits prompts, enabling fine-grained similarity comparisons via MaxSim. We derive the model's training objective from a rigorous theoretical analysis. This can ensure that optimizing this objective directly maximizes cache hits under strict correctness constraints. To solve the resulting non-differentiable combinatorial optimization problem, we leverage a reinforcement learning-based training strategy with the theoretically grounded objectives as the reward. Experimental results on established benchmarks across diverse tasks confirm that in comparison to the state-of-the-art, MVR-cache consistently increases the cache hit rates by up to 37% while maintaining the same correctness guarantees. MVR-cache is available at https://github.com/PKU-SDS-lab/MVR-Cache
Ali Noshad, Zishan Zheng, Yinjun Wu
School of Computer Science, Peking University, Beijing, China · School of Information, Renmin University of China, Beijing, China