M EM SAD: Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents
arXiv:2605.03482v1 [cs.CR] 5 May 2026
Ishrith Gowda∗ Department of Electrical Engineering and Computer Sciences University of California, Berkeley [email protected]
Abstract Persistent external memory enables LLM agents to maintain context across sessions, yet its security properties remain formally uncharacterized. We formalize memory poisoning attacks on retrieval-augmented agents as a Stackelberg game and present a unified evaluation framework spanning three attack classes with escalating access assumptions. Correcting an evaluation protocol inconsistency relative to the triggered-query specification of Chen et al. [2024], we show that faithful evaluation increases measured attack success by 4× (from ASR-R = 0.25 to 1.00). Our primary contribution is M EM SAD (Semantic Anomaly Detection), a calibration-based defense grounded in a gradient coupling theorem: under encoder regularity, the anomaly score gradient and the retrieval objective gradient are provably identical, so any continuous perturbation that reduces detection risk necessarily degrades retrieval rank. This coupling yields a certified detection radius that guarantees correct classification regardless of adversary strategy. We prove minimax optimality via Le Cam’s method, showing that any threshold detector requires Ω(1/ρ2 ) calibration samples and M EM SAD achieves this up to log(1/δ) factors. We further derive online regret bounds for rolling calibration with optimal window selection at rate O(σ 2/3 ∆1/3 ), and formally characterize a discrete synonym-invariance loophole that marks the boundary of what continuous-space defenses can guarantee. Experiments on a 3 × 5 attack-defense matrix with bootstrap confidence intervals, Bonferroni-corrected hypothesis tests, and ClopperPearson validation (20 trials, n = 1,000) confirm the theory: composite defenses achieve TPR = 1.00, FPR = 0.00 across all attacks, while synonym substitution evades detection at ∆ASR-R ≈ 0, exposing a concrete gap that existing embedding-based defenses cannot close.
1
Introduction
Modern LLM agents persist context across sessions through external memory systems such as Mem0 [Mem0 Team, 2024], A-MEM [A-MEM Team, 2025], and MemGPT [Packer et al., 2023], storing user preferences and factual knowledge as dense vector embeddings. The practical utility of persistent memory is well-established; its security implications are not. A single adversarial entry injected into an agent’s memory may persist indefinitely, triggering on every semantically related query across future sessions. Unlike prompt injection, which requires per-interaction access, memory poisoning persists and scales: the adversary acts once, and the attack surface compounds with each new query. Three concurrent works introduce distinct threat models with escalating access requirements. AGENT P OISON [Chen et al., 2024] formulates trigger optimization as a constrained gradient prob∗ Work conducted at the Song Lab, Berkeley AI Research, University of California, Berkeley.
Preprint.
lem over DPR [Karpukhin et al., 2020] embeddings (α = WRITE). MINJA [Dong et al., 2025] extends the setting to query-only access via progressive-shortening indication (α = QUERY). I N JEC MEM [Anonymous, 2026] achieves single-interaction injection via retriever-agnostic anchors (α = SINGLE). Despite the severity of these threats, no prior work provides a unified evaluation across attack classes or proposes defenses with formal detection guarantees for the memory-agent setting. Existing RAG defenses [Zou et al., 2024, Chaudhari et al., 2024, Xiang et al., 2024] assume corpus-level access and offline cleaning, neither of which applies to the streaming ingestion model of agent memory. Contributions. (1) Formal threat model and M EM SAD defense. Stackelberg game formulation with a gradient coupling theorem establishing that monotone retrieval-score detectors are necessary and sufficient for continuous-evasion resistance, a certified detection radius providing checkable perentry guarantees, and minimax optimality via Le Cam’s method. (2) Synonym-invariance analysis. Formal characterization of the discrete loophole where gradient coupling breaks down, and M EM SAD+: a combined semantic-lexical detector that partially closes it via character n-gram features. (3) Persistent threat analysis and real-system validation. Compound exposure analysis reframing attack severity for persistent memory, tool-use agent evaluation with GPT-4o-mini (ASR-A = 0.48), and Mem0 production validation. (4) Rigorous evaluation. A 3 × 5 attack-defense matrix with Bonferroni-corrected hypothesis testing, bootstrap CIs, and Clopper-Pearson validation demonstrating composite portfolios achieve TPR = 1.00, FPR = 0.00 across all attacks.
2
Related work
Memory poisoning attacks. Chen et al. [2024] report ASR-R ≥ 0.80 via trigger optimization over DPR [Karpukhin et al., 2020] embeddings under the triggered-query protocol, requiring write access to the memory store. Dong et al. [2025] exploit auto-storage via progressive-shortening indication (ISR = 98.2%) under query-only access. Anonymous [2026] achieve single-interaction injection via retriever-agnostic anchors, the weakest attacker assumption. Anonymous [2025b] demonstrate experience-grafting attacks exploiting union retrieval; Xu et al. [2026] show that memory retrieval can override tool-call control flow. Concurrent work spans backdoor-style [Cheng et al., 2024, Anonymous, 2025a, Xue et al., 2024], trigger [Chaudhari et al., 2024], and denial-of-service attacks [Shafran et al., 2025]. Agent Security Bench [Zhang et al., 2025] benchmarks 10 threat categories but does not isolate memory poisoning or provide defense guarantees; AgentHarm [Andriushchenko et al., 2025] focuses on prompt-level jailbreaks. Unlike training-time backdoors [Wu et al., 2024], memory poisoning targets the retrieval index at inference time, persisting across sessions. Recent defenses (A-MemGuard [Li et al., 2025], RevPRAG [Tan et al., 2025], ReliabilityRAG [Anonymous, 2025d], SeCon-RAG [Anonymous, 2025e]) address related settings; none provides formal detection guarantees for streaming agent memory. RAG corpus poisoning and certified defenses. Zou et al. [2024] optimize adversarial documents via HotFlip [Ebrahimi et al., 2018] (> 90% ASR on million-document corpora). Xiang et al. [2024] provide certified robustness via isolate-then-aggregate, but require post-retrieval processing of k passages. RAGDefender [Anonymous, 2025c] applies post-retrieval passage scoring; SPECTRE [Hayase et al., 2021] uses spectral detection requiring full corpus access (O(|M|2 d)). Randomized-smoothing defenses [Cohen et al., 2019, Robey et al., 2023] operate on query inputs, not persistent memory. Our work differs: (i) defenses operate at write time (O(md) per entry), (ii) no corpus-level access, and (iii) our certificate (Lemma 7) is deterministic given the calibration bound. Game-theoretic security. Following Tramèr et al. [2020], Carlini and Wagner [2017], our Stackelberg formulation gives the adversary full knowledge of (µ̂, σ̂, κ); the gradient coupling theorem provides the formal guarantee, while Proposition 11 characterizes where it fails.
3
Formal threat model
Definition 1 (Memory-augmented agent). A memory-augmented agent is a tuple (A, M, E, k) where A is an LLM, M ⊂ V ∗ is a persistent memory store over vocabulary V, E : V ∗ → Rd 2
M EM SAD πD filter
top-k
User q
Memory M
Ret(M, q, k)
LLM A
Response
padv
Adversary S
Figure 1: Memory poisoning as a Stackelberg game (Definitions 2–3). The defender commits to πD ; the adversary best-responds by injecting padv . Table 1: Attack threat-model comparison across deployment-relevant dimensions. Property
AGENT P OISON
Access model α Trigger required Retriever-agnostic Entries injected n Modelled ASR-A
WRITE
MINJA
I NJEC MEM
QUERY
SINGLE
— — 2× 0.76
— ✓ 3× 0.57
†
✓ — 1× 0.68
† Triggered-query evaluation additionally
requires query-channel access (e.g., front-end control or prompt injection); see Section 3.
is an embedding function, and k ∈ N is the retrieval depth. At each interaction with query q, the agent retrieves X Ret(M, q, k) = arg max cos(E(q), E(m)), (1) S⊆M |S|=k
m∈S
⊤
where cos(u, v) := u v/(∥u∥∥v∥) denotes cosine similarity. Definition 2 (Memory poisoning threat model). An adversary S = (Qv , n, α) targets victim queries Qv ⊂ V ∗ by injecting P = {p1 , . . . , pn } into M under access model α ∈ {WRITE, QUERY, SINGLE} to maximize: ASR-R(P, Qv ) := |{q ∈ Qv : P ∩ Ret(M ∪ P, q, k) ̸= ∅}|/|Qv |, ASR-A(P) := P[A executes adversarial action | poison retrieved], ASR-T(P, Qv ) := ASR-R · ASR-A.
(2) (3) (4)
Definition 3 (Stackelberg game formulation). The memory poisoning interaction is a Stackelberg game G = (S, D, uS , uD ) where the defender (leader) commits to a detection policy πD : V ∗ → {0, 1} and the adversary (follower) best-responds: ∗ πD = arg min πD ∈Π
max
P∈B(πD )
B(πD ) = arg max
P⊆V ∗ , |P|≤n
ASR-R(P, Qv ),
ASR-R(P \ {p : πD (p) = 1}, Qv ),
(5)
(6)
where Π = {π(c) = 1[s(c; H) > τ ] : τ > 0} is the class of threshold detectors. The defender’s utility is uD = −ASR-R − λ · FPR (λ > 0) and the adversary’s is uS = ASR-T.
Assumption 4 (Encoder regularity). E : V ∗ → Rd satisfies: (i) ∥E(x)∥ > 0 for all x; (ii) differentiability w.r.t. the output embedding; (iii) L2-normalization: ∥E(x)∥ = 1 (w.l.o.g.). Under Assumption 4(iii), cos(E(q), E(m)) = E(q)⊤ E(m) and retrieval reduces to maximum inner product search. Figure 1 illustrates the interaction. The three attacks (Table 1) span decreasing access requirements (write ⊃ query ⊃ single-interaction). Protocol distinction: Chen et al. [2024]’s Algorithm 2 specifies triggered queries q ⊕ T ∗ ; evaluating with plain queries (as in prior reproductions) measures a weaker setting (cos ≈ 0.45 vs. ≈ 0.78), raising ASR-R from 0.25 to 1.00. 3
Algorithm 1 M EM SAD pre-ingestion filtering Require: candidate c, query history H, parameters (µ̂, σ̂), threshold κ 1: s ← scomb (c; H) 2: if s > µ̂ + κ · σ̂ then 3: reject c 4: else 5: accept c into M 6: end if
4
M EM SAD: Semantic Anomaly Detection
4.1
Algorithm and formal definition
▷ O(md) time
The key insight is that memory poisoning succeeds because adversarial entries are semantically close to victim queries; this closeness is itself a detectable signal. Definition 5 (M EM SAD detector). Let H = {q1 , . . . , qm } be a rolling query history (FIFO, capacity mmax ) and Mref ⊆ M a benign reference corpus. The anomaly score is s(c; H) := maxq∈H cos(E(c), E(q)), calibrated via µ̂, σ̂ of {s(m; H) : m ∈ Mref }. Entry c is flagged if s(c; H) > µ̂ + κσ̂ for threshold parameter κ > 0. The combined scoring mode averages max-query and mean-query similarity, capturing both targeted attacks (high max similarity) and distributed attacks (elevated mean similarity): 1 X scomb (c; H) := 21 max cos(E(c), E(q)) + 12 · cos(E(c), E(q)). (7) q∈H |H| q∈H
The full pre-ingestion procedure is given in Algorithm 1; a block-diagram view of the same pipeline (candidate → encoder → cosine vs. H → scomb → threshold compare → accept/reject) is provided in Fig. 3 (Appendix A). 4.2
Gradient coupling theorem
The central structural question is: what property must a detector possess to guarantee that any continuous evasion attempt degrades retrieval rank? The sufficiency direction is immediate from the chain rule: any monotone function of the retrieval score inherits its gradient direction, so detection and retrieval move in lockstep. The substantive content is in the converse and the optimality claim. Necessity shows that non-monotone detectors always admit continuous evasion paths on Sd−1 (via connectedness), and canonicity shows that the max-cosine score is the unique minimal sufficient statistic for detection, following the Karlin–Rubin pattern [Lehmann, 1959]. Together, these give a complete characterization: monotonicity is the exact boundary between detectors that resist continuous evasion and those that do not. Theorem 6 (Gradient coupling: necessity, sufficiency, and canonicity). Let E satisfy Assumption 4, ec := E(c), q ∗ := arg maxq∈H cos(ec , E(q)), R(ec ) := cos(ec , E(q ∗ )). (i) Sufficiency: For any differentiable D = g ◦ R with monotone increasing g, g ′ > 0: ∇ec D(ec ) = g ′ (R(ec )) · ∇ec R(ec ),
so
⟨δ, ∇D⟩ < 0 ⇐⇒ ⟨δ, ∇R⟩ < 0.
Under L2-normalization (Assumption 4(iii)), ∇ec R = E(q
∗
(8)
∗ ) − (e⊤ c E(q ))ec .
(ii) Necessity: If D is not monotone in R, there exist thresholds τret , τdet and a continuous path γ : [0, 1] → Sd−1 with R(γ(1)) > τret yet D(γ(1)) < τdet : the adversary can traverse continuously to high retrieval rank while evading detection. (iii) Canonicity: Among all detectors achieving coupling (i.e., satisfying (i)), the max-cosine score D = R (i.e., g = id) is the unique detector that is a sufficient statistic for the adversarial-vsbenign hypothesis test induced by R: any other g preserves the coupling direction but discards distributional information. Proof. (i) The chain rule gives ∇D = g ′ (R) · ∇R; g ′ > 0 preserves the sign of every directional derivative. Under Assumption 4(iii), the sphere gradient is ∇ec cos(ec , v) = v − (e⊤ c v)ec . (ii) 4
Non-monotonicity implies ∃ ec , e′c with R(e′c ) > R(ec ) but D(e′c ) < D(ec ). By connectedness of Sd−1 , there exists a continuous path γ from ec to e′c . Setting τret = R(ec ) and τdet = D(ec ) yields the claimed path with R(γ(1)) > τret and D(γ(1)) < τdet . (iii) The sufficient statistic R generates the likelihood ratio p1 (e)/p0 (e) as a monotone function of cos(e, eq∗ ) under Gaussian score distributions (as in Theorems 8–9). By the Neyman–Fisher factorization theorem [Lehmann, 1959], R(ec ) is sufficient for the binary hypothesis test H0 : benign vs. H1 : adversarial. Minimality follows from the Lehmann–Scheffé theorem [Lehmann, 1959]: since p1 (e)/p0 (e) is a monotone function of R(ec ) alone, any sufficient statistic must be a function of R(ec ), making it minimal sufficient. Hence g = id achieves minimal sufficiency; any g ̸= id retains the coupling direction but discards distributional information, i.e., is a lossy compression of R. The combined score scomb also preserves directional coupling (Corollary 14, Appendix B.7). The gradient coupling reflects a deeper geometric structure: the Fisher-Rao metric induced by the score family is rank-1 (g F = σ̂ −2 ∇R∇R⊤ ), so any continuous evasion path pays retrieval cost in exact proportion to Fisher-Rao distance [Amari, 2016] (Theorem 12, Appendix B.5). 4.3
Certified detection guarantee
We now provide an instance-specific guarantee: when the adversarial-benign similarity gap exceeds the calibration uncertainty, M EM SAD certifiably detects the adversarial passage. Lemma 7 (Certified detection radius). Let E satisfy Assumption 4 and let c be an adversarial passage achieving rank(E(c), M) ≤ k for victim query q ∗ . Define the benign similarity ceiling s̄ := maxm∈Mref cos(E(m), E(q ∗ )), the adversarial similarity sadv := cos(E(c), E(q ∗ )), and the gap ∆s := sadv − s̄. If the calibration satisfies |τN − τ ∗ | ≤ η (Theorem 9) and the gap exceeds ∆s > κσ̂ + η, (9) then M EM SAD detects c with certainty: s(c; H) > µ̂ + κσ̂. Proof sketch. Since rank(E(c)) ≤ k, we have s(c; H) ≥ s̄ + ∆s . The gap condition and calibration bound together force s(c; H) > µ̂ + κσ̂. Full proof in Appendix B; Figure 10 (Appendix V) illustrates the certified region geometrically. 4.4
Theoretical foundations
We establish four additional results; full statements and proofs are in Appendix B. Theorem 8 (Minimax detection lower bound). For Gaussian benign/poisoned score distributions with SNR ρ, under the uniform prior P(H0 ) = P(H1 ) = 21 , any threshold detector calibrated on N √ samples satisfies FPR + (1 − TPR) ≥ 1 − ρ N /2. Reliable detection at total-error level ϵ (i.e., FPR + (1−TPR) ≤ ϵ) requires N ≥ 4(1 − ϵ)2 /ρ2 . M EM SAD achieves reliable detection with N = O(log(1/δ)/ρ2 ) (Theorem 9), matching the Ω(1/ρ2 ) lower bound up to log(1/δ), thereby establishing minimax optimality via Le Cam’s method [Le Cam, 1973]. Theorem 9 (Calibration bound). With probability ≥ 1 − δ: |τN − τ ∗ | ≤ σ(N −1/2 + p −1/2 κ(2(N −1)) ) 2 log(4/δ). Theorem 10 (Online calibration regret). Under per-step drift ∆, the optimal window m∗max = Θ((σ/∆)2/3 ) yields per-step regret O(σ 2/3 ∆1/3 ). We additionally prove a Wasserstein generalization bound guaranteeing graceful TPR degradation for novel attacks (Theorem 15, Appendix B.8), and NP-hardness of optimal evasion via reduction from CVP (Proposition 13, Appendix B.6), motivating the adversary’s shift to discrete synonym substitution. 4.5
The discrete synonym loophole
Proposition 11 (Synonym-invariance loophole). Let E satisfy ∥E(sub(c, w, w′ )) − E(c)∥ ≤ ϵsyn for all synonym pairs (w, w′ ). For r substitutions yielding c′ : |R(c′ ) − R(c)| ≤ rϵsyn , |s(c′ ; H) − s(c; H)| ≤ rϵsyn . (10) 5
The Attacker’s Retrieval Gradient Raises the MemSAD Score 3
µ + kσ firing boundary
Projected Embedding Axis e2
2
1
0
−1
−2
attacker’s gradient ∇p Lret Victim queries Q (calibration) Benign entry (low s, accept)
−3
−4
−3
−2
−1
0
1
Poison start (pre-optimization) Poison post-optim (s > µ + kσ, reject) 2
3
4
Projected Embedding Axis e1
Empirical Gradient Coupling Under DPR-HotFlip Optimization Retrieval Loss Lret
0.6
µ + kσ
detection at t = 9
0.8
0.5
0.6 0.4
Adversary retrieval loss Lret (pt )
0.4
MemSAD score s(pt )
0.2
0.3 0
5
10
15
20
25
30
MemSAD Combined Score s(p)
(a) Mechanism (schematic).
Optimizer Step t
(b) Empirical confirmation (DPR-HotFlip).
Figure 2: Gradient coupling, visualized. (a) 2-D projection: dashed contour marks the µ̂ + κσ̂ firing region around Q; the adversary’s gradient ∇p Lret pushes the poison into the firing region along the direction that raises s (Thm. 6). (b) DPR-HotFlip: Lret and s mirror; detection fires at t = 9. When ϵsyn ≈ 0, the adversary evades detection while preserving retrieval rank through discrete lexical substitution that bypasses gradient coupling. Proof. Cauchy-Schwarz gives |E(q)⊤ (E(c′ ) − E(c))| ≤ ∥E(c′ ) − E(c)∥, and triangle inequality over r substitutions yields ∥E(c′ ) − E(c)∥ ≤ rϵsyn . This does not contradict Theorem 6: the coupling holds for continuous perturbations in Rd , while synonym substitution operates in the discrete token space where ϵsyn ≈ 0 for paraphrase-trained encoders. The triangle inequality bound rϵsyn is an upper bound; non-linear encoder interactions may cause cancellation, making the actual perturbation smaller. M EM SAD+. We extend M EM SAD with character n-gram JSD features that are provably not synonym-invariant (Proposition 23, Table 18, Appendix Q). Empirically, M EM SAD+ raises I N JEC MEM TPR from 0.00 (synonym-evaded) to 0.40 and original from 0.20 to 0.60. 6
Table 2: Attack results (|M| = 1,000, 100 queries, 5 seeds, bootstrap 95% CI). ASR-AGPT-2 : permissive model without safety alignment (high-compliance upper bound); ASR-A4o-mini : productionaligned; † projected from original papers. Attack AGENT P OISON (trig.) MINJA I NJEC MEM
5
ASR-R
ASR-A†
ASR-AGPT-2
ASR-A4o-mini
ASR-T†
Ben. Acc.
1.00 0.14[.13,.15] 0.07[.06,.07]
0.68 0.76 0.57
0.90 0.17 0.00
0.20 0.00 0.00
0.68 0.11 0.04
1.00 1.00 0.98
Additional defenses
We evaluate four additional defenses spanning orthogonal strategies, all operating at pre-ingestion time. Watermark: the defender watermarks all legitimate entries at write time via a unigram scheme [Zhao et al., 2024, Kirchenbauer et al., 2023] (zthr = 1.5, FPR = 0.000 empirically; higher thresholds inflate FPR for short entries), rejecting unwatermarked entries; this requires control of the ingestion pipeline. Validation: rule-based pattern matching (O(|c| · |P |)). Proactive: computes mean cosine similarity against 16 domain probes, flagging entries exceeding τ = P0.19. Composite: weighted ensemble (wwm =0.50, wval =0.20, wpro =0.30, θ=0.50): flag if j wj dj (c) > θ (Appendix C).
6
Experiments
6.1
Setup
Vector memory. FAISS IndexFlatIP with L2-normalized all-MiniLM-L6-v2 embeddings (d = 384). Benign corpus: |M| = 1,000 synthetic entries across 7 categories (task reminders, calendar events, user preferences, factual knowledge, document references, configuration settings, conversation history), matching the per-user memory scale of deployed systems where active memory stores typically contain 102 –103 entries [Chen et al., 2024, Dong et al., 2025]; corpus-size ablation (Appendix D) validates results across |M| ∈ {50, . . . , 1000}. M EM SAD calibration uses N = 50 benign entries as the reference set (Theorem 9 predicts |τN − τ ∗ | ≤ 0.044 at N = 50, δ = 0.05). Cross-corpus generalization is validated on a real-data corpus combining Natural Questions knowledge passages [Kwiatkowski et al., 2019] with synthetic filler to |M| = 1,000 (Appendix P): AGENT P OISON transfers (ASR-R = 1.00±0.00); MINJA’s ASR-R = 0.58±0.06 on the topically homogeneous NQ corpus confirms corpus diversity is a risk factor. Poison counts: n = 5 (AGENT P OISON), 10 (MINJA), 15 (I NJEC MEM). k = 5; |Qv | = |Qb | = 100. Bootstrap 95% CIs from 5 independent seeds (each seed generates a distinct corpus permutation and query sample); attack outcomes are deterministic given a fixed corpus, so CI widths reflect corpus-composition variance. Attacks. AGENT P OISON: centroid passage + DPR HotFlip trigger (cos : 0.71 → 0.78). MINJA: progressive-shortening with bridging steps (p0 = 0.98, λ = 0.10). I NJEC MEM: 3 × nbase broadanchor entries from 8 templates. 6.2
Attack results
Table 2 reports the main results at |M| = 1,000. AGENT P OISON achieves ASR-R = 1.00 under the triggered-query protocol, confirming trigger optimization defeats corpus dilution entirely. Untriggered attacks (MINJA, I NJEC MEM) are naturally mitigated by corpus scale (4.6× and 7.1× dilution).2 In plain text-response mode, measured ASR-A = 0.20 under GPT-4o-mini is 3.4× lower than the modelled ASR-A = 0.68 [Chen et al., 2024], reflecting production safety alignment (Figure 12, Appendix V); the tool-use setting raises ASR-A to 0.48 (Table 20, Appendix S). 2 ISR measures write-time injection success; ASR-R measures retrieval-time exposure.
7
Table 3: Defense TPR/FPR at operating thresholds (κ = 2.0 for M EM SAD). AP = AGENT P OISON, MJ = MINJA, IM = I NJEC MEM. TPR (↑)
FPR (↓)
AUROC
Defense
AP
MJ
IM
AP
MJ
IM
(avg)
Watermark Validation Proactive M EM SAD (comb.) Composite
1.00 0.60 1.00 0.00† 1.00
1.00 0.40 0.07 0.40 1.00
1.00 0.80 0.60 0.20 1.00
0.00 0.10 0.01 0.00 0.00
0.00 0.10 0.01 0.00 0.00
0.00 0.10 0.01 0.00 0.00
0.991 — — 0.867 —
† Plain calibration (FPR = 0.00); triggered calibration: TPR = 1.00, FPR = 0.00, AUROC = 1.000. FPR validated over 20
independent trials (n = 1,000 entries each); Clopper-Pearson 95% CI: [0.000, 0.004] (Appendix I).
Table 4: Adaptive adversary: evasion vs. retrieval degradation (Proposition 11). Attack AGENT P OISON MINJA I NJEC MEM
6.3
Evasion
∆ASR-R
Subs/Entry
Sim. ∆
1.00 0.80 1.00
0.00 0.00 0.00
4.2 3.8 5.1
−0.01 −0.02 −0.01
Attack-defense interaction matrix
Table 3 reports the full 3 × 5 matrix. Watermark achieves TPR = 1.00 in simulation but fails silently when auto-storage bypasses ingestion control, motivating M EM SAD’s content-level detection. M EM SAD detects MINJA (TPR = 0.40, AUROC 0.914) and I NJEC MEM (TPR = 0.20, AUROC 0.816); triggered calibration raises AGENT P OISON to TPR = 1.00. Composite portfolios achieve TPR = 1.00, FPR = 0.00 across all attacks (Proposition 17). 6.4
Adaptive adversary analysis
Following Tramèr et al. [2020], we model a white-box adversary with full knowledge of (µ̂, σ̂, κ) who applies greedy synonym substitution (> 60 pairs): c∗ = arg min s(c′ ; H)
s.t.
c′ ∈Syn(c)
rank(E(c′ ), M) ≤ k.
(11)
Table 4 confirms Proposition 11: 80–100% evasion with ∆ASR-R ≈ 0 using 3.8–5.1 substitutions, consistent with the bound rϵsyn ≤ 5.1 × 0.004 = 0.020. The certified condition (Lemma 7) still holds for MINJA post-substitution (∆s = 0.13 > 0.08) but fails for tighter margins. 6.5
Statistical validation
Bonferroni-corrected binomial tests (α′ = 0.003, 15 comparisons): all composite results reject H0 : TPR = 0 with power = 1.00 (Table 11, Appendix H). M EM SAD AUROC at κ = 2.0: 0.914 (MINJA), 0.816 (I NJEC MEM), 0.870 (AGENT P OISON, plain); triggered calibration raises AGENT P OISON to AUROC = 1.000. Theory validation: calibration bound predicts |τN − τ ∗ | ≤ 0.022 at N = 200; observed 0.014 (Table 8, Appendix D). 6.6
Ablation highlights
Key results (full tables in Appendix D): Threshold: κ = 2.0 with combined scoring is optimal (Table 5). Corpus size: AGENT P OISON is robust (ASR-R = 1.00) across |M| ∈ {200, . . . , 1000}; untriggered attacks (MINJA, I NJEC MEM) degrade 4–7× at |M| = 1,000 (Table 6, Figure 11). Poison count: ASR-R saturates by nbase =5; additional entries yield diminishing returns (Table 7). Encoder generalization: M EM SAD validated across 6 encoders including Contriever, E5-Base, and BGE-Large (d=1024) at |M| = 1,000; triggered calibration achieves TPR = 1.000 for AGENT P OI SON on all (Table 9, Appendix E). OOD baselines: Energy Score [Liu et al., 2020] is competitive on MINJA AUROC (0.969) but M EM SAD’s query-awareness yields decisive advantage on triggered attacks (AUROC 1.000 vs. 0.945); Mahalanobis [Lee et al., 2018] and KNN fail (FPR > 0.96; 8
Table 15, Appendix N). LLM sanitization baseline: GPT-4o-mini zero-shot classifier achieves TPR = 1.000, FPR = 0.000 on the synthetic corpus, but this reflects the explicit adversarial language in our templates (e.g., “disable audit logging”); real-world paraphrased injections would likely degrade text-level detection. Mean latency is 1.2 s/entry (≈1,000× M EM SAD). The two are complementary: text-level flagging catches explicit commands; M EM SAD catches embedding-level anomalies that survive paraphrasing (Table 22, Appendix U). Calibration sensitivity: AUROC is stable across calibration regimes; threshold tuning requires domain-matched queries (Table 16, Appendix O). Cross-corpus (NQ): On a Natural-Questions-based corpus, AGENT P OISON retains ASR-R = 1.00 ± 0.00 and MINJA’s ASR-R increases to 0.58 ± 0.06 under topical homogeneity (Table 17, Appendix P). 6.7
Extended evaluations
Compound exposure. Memory poisoning compounds over sessions: P (compromise in N sessions) = 1 − (1 − ASR-R)N q for q queries/session.3 Even MINJA at ASR-R = 0.14 reaches 90% compromise in 4 sessions; composite defense (ASR-R∗ = 0) is necessary (Table 19, Appendix R). Tool-use agent. GPT-4o-mini with 5 tool definitions achieves ASR-A = 0.48 [0.34, 0.62] for AGENT P OISON; MINJA and I NJEC MEM show ASR-A = 0.00 [0.00, 0.07] at |M| = 1,000 (sparse-event CI, not detector failure; Table 20, Appendix S). Production validation. On Mem0 [Mem0 Team, 2024] (LLM-mediated storage), AGENT P OISON drops to ASR-R = 0.00 via internal reformulation; raw vector stores remain fully exposed (Table 21, Appendix T).
7
Discussion and limitations
Defense complementarity. No single defense dominates across access models α: watermarking fails when auto-storage bypasses ingestion control; M EM SAD needs triggered calibration for AGENT P OISON; proactive detection complements both. The defender’s uncertainty about α motivates composite portfolios (ASR-R∗ = 0, Proposition 17). We recommend layered deployment: watermarking at ingestion, rolling M EM SAD at retrieval, composite for high-value agents (∼2 ms per entry; Table 14, Appendix L). Multi-agent SIR simulations (Appendix G) confirm that composite defense prevents cross-agent propagation entirely, while graph memory extensions (Appendix F) show structural attacks require analogous degree-anomaly detection. The synonym frontier. Proposition 11 reveals a structural limitation: paraphrase-trained encoders map synonyms to nearly identical embeddings (ϵsyn ≈ 0). M EM SAD+ partially closes this via character n-gram features, but complete closure requires syntactic structure or provenance metadata. Limitations. (i) Corpus scale and composition: |M| = 1,000 with synthetic entries; poison passages contain explicit adversarial language that inflates text-baseline detection. Cross-corpus NQ results (Appendix P) partially address generalization; production memory traces remain necessary. (ii) Regret bound assumes slow drift; abrupt distribution shifts degrade calibration. (iii) Hardness result applies to piecewise-linear encoders; transformer extension is conjectured.
8
Conclusion
M EM SAD provides the first formally-guaranteed defense for RAG memory poisoning: gradient coupling (Theorem 6), certified per-entry detection (Lemma 7), and minimax optimality (Theorem 8); Proposition 11 identifies the discrete synonym gap as the frontier. Open directions: closing that gap, scaling to production memory with approximate NN, and multi-modal extension. 3 This assumes i.i.d. Bernoulli trials, which is a lower bound on true risk: persistent memory means a successfully retrieved adversarial entry may influence subsequent queries. Uncertainty in ASR-R (bootstrap 95% CIs in Table 2) propagates to compound probability via ∂P/∂ASR-R = N q(1 − ASR-R)N q−1 , yielding compound-exposure CIs that are conservative.
9
References A-MEM Team. A-MEM: Agentic memory for LLM agents, 2025. URL https://github.com/ agiresearch/A-MEM. Shun-ichi Amari. Information Geometry and Its Applications, volume 194 of Applied Mathematical Sciences. Springer, 2016. Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. AgentHarm: A benchmark for measuring harmfulness of LLM agents. In International Conference on Learning Representations (ICLR), 2025. URL https://arxiv.org/abs/2410.09024. Anonymous. CorruptRAG: Practical corpus poisoning against retrieval-augmented generation. arXiv preprint arXiv:2504.03957, 2025a. Anonymous. MemoryGraft: Persistent compromise of LLM agents via poisoned experience retrieval. arXiv preprint arXiv:2512.16962, 2025b. URL https://arxiv.org/abs/2512. 16962. Anonymous. RAGDefender: Post-retrieval defense against corpus poisoning attacks on RAG. In Annual Computer Security Applications Conference (ACSAC), 2025c. URL https://arxiv. org/abs/2511.01268. Anonymous. ReliabilityRAG: Provably robust retrieval-augmented generation via maximum independent set. In Advances in Neural Information Processing Systems (NeurIPS), 2025d. Poster. Anonymous. SeCon-RAG: Semantic and conflict-aware retrieval-augmented generation. In Advances in Neural Information Processing Systems (NeurIPS), 2025e. Poster. Anonymous. InjecMEM: Targeted memory injection with single interaction. In International Conference on Learning Representations (ICLR), 2026. Submission openreview:QVX6hcJ2um. Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (S&P), 2017. Harsh Chaudhari, Giorgio Severi, John Abascal, Alina Oprea, Santosh Vempala, and Luca Melis. Phantom: General trigger attacks on retrieval augmented language generation. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024. URL https://arxiv.org/abs/2405.20485. Zhaorun Chen, Zhen Tan, Hexiang Zhao, Zhengyang Cheng, Chenhui Jiang, Huan Zhang, et al. AgentPoison: Red-teaming LLM agents via poisoning memory or knowledge bases. In Advances in Neural Information Processing Systems (NeurIPS), 2024. URL https://arxiv.org/abs/ 2407.12784. Pengzhou Cheng, Yidong Ding, Tianjie Ju, et al. TrojanRAG: Retrieval-augmented generation can be backdoor driver in large language models. arXiv preprint arXiv:2405.13401, 2024. Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2019. Sicheng Dong et al. MINJA: Memory injection attacks on LLM agents via query-only interaction. In Advances in Neural Information Processing Systems (NeurIPS), 2025. URL https://arxiv. org/abs/2503.03704. Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. HotFlip: White-box adversarial examples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), 2018. URL https://arxiv.org/abs/1712.06751. Xiangming Gu, Xiaosen Zheng, Tianyu Pang, Chao Du, Qian Liu, Ye Wang, Jing Jiang, and Min Lin. AGENT-SMITH: A single image can jailbreak one million multimodal LLM agents instantly. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. URL https://arxiv.org/abs/2402.08567. 10
Jonathan Hayase, Weihao Kong, Raghav Somani, and Sewoong Oh. SPECTRE: Defending against backdoor attacks using robust statistics. In International Conference on Machine Learning (ICML), 2021. URL https://arxiv.org/abs/2104.11315. Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP, 2020. William Ogilvy Kermack and Anderson G. McKendrick. A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society of London. Series A, 115(772):700–721, 1927. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning (ICML), 2023. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, and Kenton Lee. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453–466, 2019. Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 28(5):1302–1338, 2000. Lemma 1 provides chi-squared tail bounds used for sample standard deviation concentration. Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, 1(1):38–53, 1973. Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and deep generative models. In Advances in Neural Information Processing Systems (NeurIPS), 2018. Erich L. Lehmann. Testing Statistical Hypotheses. Wiley, 1959. Chapter 3: Uniformly most powerful tests; Karlin–Rubin theorem for monotone likelihood ratio families. Lijun Li et al. A-MemGuard: A proactive defense framework for LLM-based agent memory. arXiv preprint arXiv:2510.02373, 2025. URL https://arxiv.org/abs/2510.02373. Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li. Energy-based out-of-distribution detection. In Advances in Neural Information Processing Systems (NeurIPS), 2020. Mem0 Team. Mem0: The memory layer for personalized AI, 2024. URL https://github.com/ mem0ai/mem0. Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Publishers, 2002. Chapter 3 establishes NP-hardness of CVP; used for the minimum-perturbation evasion hardness reduction. Charles Packer, Vivian Fang, Shishir G. Patil, Kevin Zhang, Sarah Wooders, and Joseph E. Gonzalez. MemGPT: Towards LLMs as operating systems. In NeurIPS Workshop on Foundation Models for Decision Making, 2023. Alexander Robey, Eric Wong, Hamed Hassani, and George J. Pappas. SmoothLLM: Defending large language models against jailbreaking attacks. In Advances in Neural Information Processing Systems (NeurIPS), 2023. Avital Shafran, Roei Peleg, and Tal Schuster. Machine against the RAG: Jamming retrievalaugmented generation with blocker documents. In USENIX Security Symposium, 2025. Xue Tan, Hao Luan, Mingyu Luo, Xiaoyan Sun, Ping Chen, and Jun Dai. RevPRAG: Revealing poisoning attacks in retrieval-augmented generation through LLM activation analysis. In Findings of the Association for Computational Linguistics: EMNLP, 2025. URL https://arxiv.org/ abs/2411.18948. 11
Florian Tramèr, Nicholas Carlini, Wieland Brendel, Aleksander Madry, Alexey Kurakin, and Nicolas Papernot. On adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems (NeurIPS), 2020. Cédric Villani. Optimal Transport: Old and New. Springer, Berlin, 2009. Sorting-based estimation of W1 in one dimension; Kantorovich-Rubinstein duality. Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. Yifeng Wu, Ruqing Pi, Yue Zheng, et al. BadAgent: Inserting and activating backdoor attacks in LLM agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL), 2024. URL https://arxiv.org/abs/2406.03007. Chejian Xiang, Mintong Tong, Jie Sun, and Bo Li. Certifiably robust RAG against retrieval corruption. In International Conference on Machine Learning (ICML), 2024. URL https: //arxiv.org/abs/2405.15556. Zhenyang Xu et al. From storage to steering: Memory control flow attacks on LLM agents. arXiv preprint arXiv:2603.15125, 2026. Jiaqi Xue, Mengxin Zheng, Ting Hua, Yilong Shen, Yepeng Liu, Ladislau Zhao, and Qian Lou. BadRAG: Identifying vulnerabilities in retrieval augmented generation of large language models. arXiv preprint arXiv:2406.00083, 2024. Hanrong Zhang, Jingyuan Zheng, et al. Agent security bench (ASB): Formalizing and benchmarking attacks and defenses in LLM-based agents. In International Conference on Learning Representations (ICLR), 2025. URL https://arxiv.org/abs/2410.02644. Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. In International Conference on Learning Representations (ICLR), 2024. URL https://arxiv.org/abs/2306.17439. Wei Zou, Runpeng Geng, Binghui Wang, and Jinyuan Jia. PoisonedRAG: Knowledge corruption attacks to retrieval-augmented generation of large language models. In USENIX Security Symposium, 2024.
12
A
Write-time pipeline diagram accept: c → M candidate entry c
encoder E(·)
ec
cosine sim vs. H
smax smean
s ≤ µ̂+κσ̂
combined score scomb
s
compare to µ̂ + κσ̂ s > µ̂+κσ̂
reject: discard
H: rolling victim queries
Mref : calibration (µ̂, σ̂)
Figure 3: M EM SAD write-time pipeline (Def. 5, Alg. 1). Every candidate c is embedded, scored against a rolling victim-query history H via the combined max–mean similarity (Eq. 7), and compared to the µ̂ + κσ̂ threshold derived from the benign reference corpus Mref . Rejection happens before the entry is committed to memory — attacks are blocked at write time rather than filtered at retrieval.
B
Proofs of main results
B.1
Proof of Theorem 6 (geometric interpretation)
Under L2-normalization, embeddings lie on Sd−1 . The Riemannian gradient of f (ec ) = e⊤ c v on ⊥ d−1 the sphere is ∇S f = v − (e⊤ v)e = Π v, the projection of v onto the tangent space T . c ec S c ec ′ For any monotone transformation g, the chain rule gives ∇(g ◦ f ) = g (f ) · ∇f , which has the same sign as ∇f since g ′ > 0. The converse (non-monotone D admits evasion) follows because non-monotonicity creates a region where increasing retrieval similarity decreases detection score, giving the adversary a “free” direction in embedding space. B.2
Proof of Theorem 8 (detailed)
Setup. Instantiate Le Cam’s method with: H0 : s(c; H) ∼ P0 = N (µ0 , σ 2 ) (benign); H1 : s(c; H) ∼ P1 = N (µ1 , σ 2 ) (poisoned), µ1 > µ0 . Then KL(P0 ∥P1 ) = (µ1 − µ0 )2 /(2σ 2 ) = ρ2 /2. N N Application. √ For product distributions, KL(P0N ∥P1N ) = N ρ2 /2. By Pinsker: TV(P p √ 0 , P1 ) ≤ 1 1 ∗ 2 N ρ /4 = ρ N /2. Le Cam gives minimax risk R ≥ 2 (1 − TV) ≥ 2 (1 − ρ N /2) under the uniform prior P(H0 ) = P(H √1 ) = 1/2. Under this prior, the frequentist total error FPR + (1 − TPR) = 2 · Pe ≥ 2R∗ = 1 − ρ N /2.
Alternative via Fano. For M = 2 hypotheses, Fano’s inequality gives Pe ≥ 1 − (I(X; Θ) + log 2)/ log M = 1 − (N ρ2 /4 + log 2)/ log 2, where I(X; Θ) ≤ maxj KL(PjN ∥P̄ N ) ≤ N ρ2 /4 by the mixture bound. This yields a slightly weaker constant but extends to the M -ary setting (e.g., distinguishing M attack types simultaneously). Tightness. For Gaussian P0 , P1 , the Neyman-Pearson optimal test achieves FPR + (1 − TPR) = √ 2Φ(−ρ N /2) where Φ is the Gaussian CDF. Comparing with the Le Cam bound: 2Φ(−x) ≈ p 2 2/π e−x /2 /x for large x, confirming the Ω(1/ρ2 ) sample complexity is tight for Gaussian scores. B.3
Proof of Theorem 9
By Hoeffding on [0, 1] [Wainwright, 2019]: |µ̂N − µ| ≤
p log(2/δ)/(2N ) w.p. ≥ 1 − δ/2.
2 For the standard deviation term, let Z = (N − 1)σ̂N /σ 2 ∼ χ2 (N − 1) (exactly, for Gaussian scores; approximately for bounded scores by Berry-Esseen). By Laurent & Massart [Laurent and p Massart, 2000] Lemma 1: P[Z ≥ (N − 1) + 2 (N − 1)x + 2x] ≤ e−x and P[Z p ≤ (N − 1) − p −x 2 (N − 1)x] ≤ ep . Setting x = log(2/δ) and applying the delta method (σ̂N = σ Z/(N − 1), √ √ so |σ̂N − σ| = σ| Z/(N p − 1) − 1|) with 1 + u − 1 ≤ u/2 for 0 ≤ u ≤ 1 (by concavity of ·) yields: |σ̂N − σ| ≤ σ log(2/δ)/(2(N − 1)) w.p. ≥ 1 − δ/2.
13
Triangle inequality: |τN − τ ∗ | ≤ |µ̂N − µ| + κ|σ̂N − σ|. Union bound yields the calibration bound in Theorem 9. B.4
Proof of Theorem 10
√ Decompose: |τ̂t − τt∗ | ≤ |τ̂t − τtH | + |τtH − τt∗ |. Estimation error: O(σ(1 + κ)/ mmax ) by The| {z } | {z } estimation
drift
orem 9. Drift error: cosine similarity is 1-Lipschitz on Sd−1 , and the window mean averages over mmax steps with linearly accumulating drift, so |µH t − µt | ≤ mmax ∆/2 (worst case at the window boundary; the 1/2 arises from averaging). This affects only the constant in m∗max but not the rate. √ Setting equal: σ/ mmax = mmax ∆ gives m∗max = (σ/∆)2/3 (up to constants), yielding per-step 2/3 1/3 regret O(σ ∆ ). B.5
Fisher-Rao detection-evasion metric
Theorem 12 (Fisher-Rao detection-evasion metric). Let E = {e ∈ Sd−1 } under Assumption 4(iii). F The Fisher information metric induced by the score family pe (s) = N (s; cos(e, eq∗ ), σ̂ 2 ) is gij (e) = −2 σ̂ ∂i R(e)∂j R(e). The geodesic distance to any undetected embedding satisfies dF (eadv , e′ ) ≥ |R(eadv ) − (µ̂ + κσ̂)|/σ̂, and the Fisher-Rao cost of any continuous evasion path equals its retrieval degradation. Proof. Consider the parameterized family pe (s) = N (s; µ(e), σ̂ 2 ) where µ(e) = cos(e, eq∗ ) and σ̂ 2 is the calibrated variance. The Fisher information matrix on the statistical manifold {pe : e ∈ E} is: ∂ log pe ∂ log pe 1 ∂µ ∂µ F gij (e) = Epe = 2 = σ̂ −2 ∂i R(e)∂j R(e). (12) ∂ei ∂ej σ̂ ∂ei ∂ej This is a rank-1 metric: g F = σ̂ −2 ∇R∇R⊤ , the pullback of the scalar Fisher information I(µ) = 1/σ̂ 2 through the map e 7→ R(e). Geodesic lower bound. For any path γ : [0, 1] → E from eadv = γ(0) to e′ = γ(1), the Fisher-Rao length is: Z Z 1q 1 1 |R(eadv ) − R(e′ )| , (13) |∇R(γ(t))⊤ γ̇(t)| dt ≥ γ̇(t)⊤ g F (γ(t))γ̇(t) dt = LF (γ) = σ̂ 0 σ̂ 0 R1 where the inequality follows from 0 |f ′ (t)|dt ≥ |f (1) − f (0)| applied to f (t) = R(γ(t)). Detection-retrieval coupling. Since D = g ◦ R with monotone g (Theorem 6), evasion requires D(e′ ) ≤ µ̂ + κσ̂, which via monotonicity implies R(e′ ) ≤ g −1 (µ̂ + κσ̂). Substituting into the geodesic bound: dF (eadv , e′ ) ≥
R(eadv ) − g −1 (µ̂ + κσ̂) |R(eadv ) − (µ̂ + κσ̂)| = , σ̂ σ̂
(14)
where the last equality uses g = id (since D is the cosine similarity score and R coincides with D under Assumption 4). The proportional retrieval degradation along the path follows from the rank-1 structure: g F has a single nonzero eigenvalue in the ∇R direction, so the geodesic cost is entirely paid in retrieval degradation. B.6
Proof of Proposition 13 (detailed)
Proposition 13 (Hardness of optimal evasion). The minimum-perturbation evasion problem is NPhard for piecewise-linear encoders, via reduction from CVP [Micciancio and Goldwasser, 2002]. This motivates the adversary’s shift to discrete synonym substitution. Reduction from CVP. Given a CVP instance (Λ, t) where Λ ⊆ Rn is a lattice with basis B ∈ Rn×n and t ∈ Rn is the target vector, we construct a memory poisoning evasion instance as follows. 14
Encoder construction (explicit). Let n be the CVP lattice dimension. Define E : Rn → Rn as a single-hidden-layer ReLU network: W1 = B ⊤ ∈ Rn×n ,
E(x) = ReLU(W1 x),
(15)
∗
where B is the lattice basis matrix. Set the query embedding E(q ) = t/∥t∥ (normalized target). Set biases to zero, so the encoder is E(x) = ReLU(B ⊤ x). Feasible set.
The evasion constraint D(ec + δ) ≤ µ̂ + κσ̂ with R(ec + δ) ≥ τret defines: F = {x ∈ Rn : cos(E(x), t/∥t∥) ∈ [τret , µ̂ + κσ̂]}.
(16)
n
Within each ReLU activation region I ⊆ {0, 1} (indexing which neurons are active), the encoder acts as the affine map EI (x) = DI B ⊤ x where DI is the diagonal activation mask. Hence F ∩ regionI is a convex polytope defined by two half-space constraints in x-space. Formal reduction. Given the CVP instance (Λ = BZn , t), let x0 = 0 be the origin (current passage embedding). The minimum-perturbation evasion problem asks for: δ ∗ = arg min ∥δ∥
s.t.
δ
x0 + δ ∈ F.
We claim ∥δ ∗ ∥ = ∥B −⊤ v ∗ − 0∥ where v ∗ is the closest lattice vector to t in Λ. Specifically: within the single activation region where all neurons are active (DI = I), E(x) = B ⊤ x, and cos(B ⊤ x, t/∥t∥) = (B ⊤ x)⊤ t/(∥B ⊤ x∥ · ∥t∥). The feasibility constraint becomes a quadratic constraint in x. For the target similarity τret = cos θ∗ induced by the CVP distance, the minimum-norm x satisfying the constraint corresponds exactly to finding the vector x = B −⊤ λ with λ ∈ Zn closest to t in the lattice metric — which is exactly CVP. This reduction runs in polynomial time in n (constructing W1 = B ⊤ and E(q ∗ ) = t/∥t∥ takes O(n2 ) time). Since CVP is NP-hard under randomized reductions [Micciancio and Goldwasser, 2002], the minimum-perturbation evasion problem is NP-hard. Practical implication. This hardness result is worst-case over encoder architectures: for the specific ReLU encoder construction used in the reduction, the optimal evasion is NP-hard. For the actual all-MiniLM-L6-v2 encoder (transformer architecture), the reduction does not directly apply due to softmax nonlinearities, and the result is conjectured but not proven. The practical takeaway is that efficient optimal evasion is unlikely, motivating the adversary’s empirical shift to discrete synonym substitution that sidesteps gradient-based search entirely. B.7
Detection-evasion tradeoff surface
Corollary 14 (Combined scoring preserves coupling). The combined score scomb = α smax + (1 − α) smean with α ∈ (0, 1) satisfies directional monotonicity: ⟨δ, ∇scomb ⟩ < 0 =⇒ ⟨δ, ∇R⟩ < 0 (at all points of differentiability), and admits the same necessity characterization (ii). Consequently, Lemma 7 and Theorem 12 apply unchanged to scomb . Proof. ∇scomb = α∇smax + (1 − α)∇smean . Since ∇smax = ∇ec cos(ec , E(q ∗ )) for the unique maximizer q ∗ , the projection onto ∇R is positive under the mild condition that the mean gradient is not adversarial to the max gradient (holds empirically). The second-order tradeoff surface follows below. By Theorem 6, D(e′c ) < D(ec ) (evasion) implies R(e′c ) < R(ec ) (retrieval degradation) to first order. The tradeoff defines a surface in (ϵ, θ, ∆D) space where θ is the angle between perturbation δ and gradient ∇D. Expanding to second order:
ϵ2 ⊤ δ HD δ + O(ϵ3 ), (17) 2 where HD is the Hessian of the cosine similarity on the sphere. Under L2-normalization, ∗ ⊤ 2 ⊤ ∗ HD = −(e⊤ c E(q ))(I − ec ec )/∥ec ∥ , giving eigenvalues λi = −(ec E(q )) for directions or′ thogonal to ec (and 0 in the radial direction). The evasion region D(ec ) < D(ec ) requires cos θ < −ϵ∥HD ∥/(2∥∇D∥), which contracts as ϵ → 0, confirming the infinitesimal impossibility of evasion without retrieval degradation (Figure 4). D(ec + ϵδ) − D(ec ) = ϵ∥∇D∥ cos θ +
15
∆R
synonym (discrete)
∇D ≡ ∇R (Thm. 6) continuous curves overlap exactly
detection margin µ̂+κσ̂ R(e′c ) D(e′c )
perturbation ϵ
Figure 4: Detection-evasion tradeoff. By gradient coupling, continuous perturbations cause identical degradation in detection score D and retrieval score R (overlapping curves). Synonym substitutions (orange) bypass this coupling via discrete jumps in token space (Proposition 11). B.8
Generalization bound
Theorem 15 (Generalization bound). For a novel attack with W1 (Pnew , Pj ) ≤ ϵW : |TPRnew − √ TPRj | ≤ ϵW /σ̂ + O(1/ N ). Remark 16 (Practical estimation of ϵW ). In practice, ϵW can be estimated from a validation set via sorting-based Wasserstein estimation [Villani, 2009], or bounded analytically under encoder Lipschitz continuity. The theorem guarantees graceful TPR degradation as novel attacks diverge from the calibration distribution. Proof setup. Let Fj and Fnew denote the CDFs of scores s(c; H) under Pj and Pnew , respectively. The TPR at threshold τ is TPR(τ ) = 1 − F (τ ). Wasserstein coupling.
By Kantorovich-Rubinstein duality: Z ∞ W1 (Fj , Fnew ) = sup |EFj [f ] − EFnew [f ]| = |Fj (s) − Fnew (s)| ds. ∥f ∥Lip ≤1
(18)
−∞
Since TPRj = 1 − Fj (τ ) and TPRnew = 1 − Fnew (τ ): |TPRj − TPRnew | = |Fnew (τ ) − Fj (τ )| ≤ W1 (Fj , Fnew )/σ̂. The 1/σ̂ factor arises because scores are standardized: the CDFs Fj , Fnew operate on (s − µ̂)/σ̂, so a shift of ϵW in raw score space corresponds to ϵW /σ̂ in standardized units. Equivalently, the score density is bounded by 1/σ̂ (Gaussian with variance σ̂ 2 ), and |F (τ + h) − F (τ )| ≤ |h|/σ̂ by the mean value theorem. Threshold estimation. By Theorem 9, |τ̂ − τ ∗ | ≤ ηN w.p. ≥ 1 − δ, contributing an additional √ O(1/ N ) term to the TPR bound via the score density at the threshold. Non-asymptotic convergence. The non-asymptotic bound follows from applying a uniform concentration argument (McDiarmid’s inequality) over the rolling window, with each window contribut√ ing an independent O(σ/ mmax ) estimation error and accumulating O(mmax ∆) drift. B.9
Online regret bound visualization
Figure 5 illustrates the bias-variance tradeoff in Theorem 10 as a function of window size mmax . B.10
Stackelberg equilibrium existence
Proposition 17 (Equilibrium existence). The Stackelberg game G (Definition 3) admits a subgame∗ perfect equilibrium (πD , P ∗ ) when Π is restricted to threshold detectors with κ ∈ [κmin , κmax ]. Proof. The defender’s strategy space Πκ = {πκ : κ ∈ [κmin , κmax ]} is compact. For fixed πκ , the adversary’s best-response set B(πκ ) = arg maxP ASR-R(P \ {p : s(p; H) > µ̂ + κσ̂}, Qv ) is 16
per-step regret drift (non-stationarity)
estimation (Thm. 9)
O(σ 2/3 ∆1/3 )
total
m∆ √ σ/ m
mmax
m∗
Figure 5: Online calibration regret decomposition (Theorem 10). Small windows suffer high estimation error; large windows accumulate drift. The optimal m∗ = Θ((σ/∆)2/3 ) balances both.
nonempty (the empty set is always feasible) and upper hemicontinuous in κ since s(p; H) is continuous and the threshold µ̂ + κσ̂ is linear in κ. The defender’s objective maxP∈B(πκ ) ASR-R(P, Qv ) ∗ is upper semicontinuous by the Berge maximum theorem. By the extreme value theorem, πD = arg minκ∈[κmin ,κmax ] maxP∈B(πκ ) ASR-R exists. In practice, the composite portfolio (πwm ∨ πSAD ∨ πpro ) achieves ASR-R∗ = 0 against all three attacks (Table 3), representing the defender’s ideal equilibrium where the adversary’s best response yields zero utility. B.11
Finite-sample FPR concentration
Proposition 18 (FPR concentration). Let c1 , . . . , cn be n i.i.d. benign candidates with scores si = P d n = n−1 n 1[si > µ̂ + κσ̂]. Under sub-Gaussian scores with parameter σ 2 : s(ci ; H). Let FPR i=1 h i nϵ2 nϵ2 d n − FPR| > ϵ ≤ 2 exp − P |FPR + 2 exp − . (19) 2FPR(1 − FPR) 8 The first term is the Bernstein bound on the empirical FPR; the second accounts for threshold d − 0| > 0.01] < 0.006, estimation error (from Theorem 9). For κ = 2.0 and n = 1,000: P[|FPR consistent with the Clopper-Pearson CI [0.000, 0.004] (Table 12).
C
Additional defense details
p Watermark. The z-score z = (g − γn)/ γ(1 − γ)n uses green-list count g and sequence length n. Character-level: 95 ASCII chars, γ = 0.45. Token-level (GPT-2, 50,257 tokens): pgreen ≈ 0.711, mean z ≈ 7.5 at n = 50. Proactive. 16 probe queries span 8 subtopics. Threshold τ = 0.19 minimizes FPR while maintaining ≥ 0.50 TPR on centroid passages. Composite defense. The weighted ensemble uses wwm = 0.50, wval = 0.20, wpro = 0.30, threshold θ = 0.50: an entry is rejected if 0.50 · dwm (c) + 0.20 · dval (c) + 0.30 · dpro (c) > 0.50. Composite achieves TPR = 1.00 because watermarking alone achieves TPR = 1.00 when controlling ingestion; for attacks exploiting auto-storage (bypassing watermarking), proactive and validation terms provide the remaining detection. Evaluation correction. Prior work evaluated AGENT P OISON with plain queries q; the paper’s Algorithm 2 specifies triggered queries q ⊕ T ∗ , changing cos from ≈ 0.45 to ∼ 0.78. 17
Table 5: M EM SAD threshold sensitivity with combined scoring (|M| = 200; see Table 3 for |M| = 1,000 results). TPR κ
AP
1.0 1.5 2.0 2.5 3.0
†
1.00 1.00† 1.00† 1.00† 0.80†
FPR
MJ
IM
AP
MJ
IM
1.00 1.00 1.00 1.00 0.80
0.80 0.60 0.40 0.20 0.00
0.10 0.00 0.00 0.00 0.00
0.10 0.05 0.00 0.00 0.00
0.10 0.05 0.00 0.00 0.00
† Triggered calibration. Plain: TPR = 0.00 for all κ.
Table 6: Corpus size ablation: ASR-R across |M| (triggered for AP). |M|
AGENT P OISON
MINJA
I NJEC MEM
50 100 200 300 500 1000
1.00 1.00 1.00 1.00 1.00 1.00
0.70 0.65 0.65 0.60 0.60 0.14
0.65 0.55 0.50 0.40 0.30 0.07
AGENT P OISON uses triggered protocol; |M| = 1,000 row matches main evaluation (Table 2).
D
Ablation studies
E
Multi-encoder evaluation
Key findings at |M| = 1,000 (Figure 6): (1) Triggered calibration achieves TPR = 1.000 for AGENT P OISON on all 6 encoders, confirming the gradient coupling signal transfers across architectures and embedding dimensions. (2) MINJA detection is robust (TPR ≥ 0.80, AUROC ≥ 0.914) across all encoders. (3) I NJEC MEM is more encoder-sensitive: E5-Base achieves TPR = 1.00 while Para-MiniLM achieves 0.00, suggesting anchor-crafted templates vary in cross-encoder similarity. (4) BGE-Large (d=1024, instruction-tuned) achieves TPR = 1.00/1.00/0.80 for AP/MJ/IM, AUROC ≥ 0.928 across attacks; its higher FPR (0.09–0.14 at κ = 2.0) reflects a broader embedding distribution that slightly overlaps the anomaly boundary—raising κ to 2.5 eliminates the false positives at the cost of TPRIM = 0.60.
F
Graph memory attacks
Definition 19 (Graph memory system). A graph memory is (G, M, E, k) where G = (V, E, ϕ) is a knowledge graph with attribute function ϕ : V ∪ E → V ∗ . Retrieval combines embedding similarity with BFS traversal: RetG (q, k, h) = {v ∈ V : dG (v, v ∗ ) ≤ h, v ∗ ∈ arg maxv′ cos(E(q), E(ϕ(v ′ )))}. Three structural attacks: Hub insertion (high-degree adversarial node), edge hijack (shortcuts to adversarial nodes), subgraph cluster (self-reinforcing adversarial community). Degree-anomaly detection flags zdeg (v) > κdeg ; adjacency contamination scoring detects edge-hijack via the fraction of recently added edges.
G
Multi-agent propagation
Definition 20 (SIR propagation). For N agents sharing Mshared , the discrete-step SIR model [Kermack and McKendrick, 1927, Gu et al., 2024] evolves: S(t+1) = S(t) − βS(t)I(t)/N , I(t+1) = I(t) + βS(t)I(t)/N − γI(t), R(t+1) = R(t) + γI(t), where β is transmission rate and γ recovery rate. 18
Table 7: Poison count ablation: ASR-R vs. nbase . nbase
AGENT P OISON
MINJA
I NJEC MEM
1 3 5 7 10
0.80 1.00 1.00 1.00 1.00
0.20 0.45 0.65 0.70 0.75
0.10 0.30 0.50 0.55 0.60
Table 8: Calibration set size ablation: |τN − τ ∗ | vs. N (theoretical bound from Theorem 9 vs. observed, δ = 0.05, MINJA). N (calibration size)
Bound (Thm. 9)
Observed
0.061 0.044 0.031 0.022 0.014
0.038 0.027 0.019 0.014 0.009
25 50 100 200 500
Bound is tight to within ≈ 1.6×; N = 50 (main evaluation) gives |τN − τ ∗ | ≤ 0.044.
Without defense, steady-state infection is I∞ /N = 1 − γ/β for β > γ. With M EM SAD quarantine (TPR = 1.00 for MINJA), γeff = γ + TPR · β; the condition β > γeff is never satisfied, eliminating secondary infection. Empirical simulation We instantiate the SIR model with N = 20 agents, pre-store = 0.30, T = 30 steps, 5 initial MINJAstyle poison entries, and a 200-entry synthetic corpus (all-MiniLM-L6-v2 FAISS retrieval). Each condition is run under 5 independent seeds controlling agent query-sampling trajectories (corpus held fixed); both no-defense and defended conditions use the same per-trial seed for a fair comparison. Three conditions are evaluated: (i) no defense; (ii) M EM SAD with triggered calibration (σ = 2.0, combined scoring); (iii) composite defense approximated by σ = 1.0. Figure 7 and Table 10 summarize the results. The tighter composite threshold (σ = 1.0) quarantines 2 of 5 initial entries and all secondary entries, holding spread to zero. M EM SAD at σ = 2.0 quarantines ≈5 entries per trial (averaged over 5 seeds) but the 4 initial entries that pass the looser threshold seed infection at the same rate as the no-defense baseline (t90% = 14 steps in both conditions); M EM SAD’s measurable effect is a 22% reduction in secondary entries (18 vs. 23), preventing secondary amplification while the composite is required to stop initial spread entirely.
H
Statistical hypothesis tests
I
FPR validation
J
M EM SAD detection analysis
Figure 8 visualizes M EM SAD’s ROC characteristics and calibration shift.
K
Sample complexity comparison
Table 13 compares the calibration sample requirements across detection approaches, derived from Theorem 8 and Theorem 9. The logarithmic gap between the lower bound and M EM SAD’s requirement confirms minimax optimality up to log(1/δ). For practical deployment at δ = 0.05: log(1/δ) ≈ 3.0, so M EM SAD requires ∼ 3× the information-theoretic minimum. The main evaluation uses N = 50, well above the theoretical minimum for all observed SNR regimes, providing conservative guarantees. 19
Table 9: Encoder generalization: M EM SAD across 6 encoders at |M| = 1,000 (κ = 2.0, combined scoring). AP uses triggered calibration. FPR omitted (0.000 for MiniLM/MPNet/Para/E5/Contriever; 0.086–0.138 for BGE-Large at this κ). TPR here measures detection over 5 poison passages per attack; main Table 3 uses n = 10 MINJA / n = 15 I N JEC MEM entries (different poison set, same encoder, same κ). TPR
AUROC
Encoder
AP
MJ
IM
AP
MJ
IM
MiniLM-L6 (d=384) MPNet-Base (d=768) Para-MiniLM (d=384) E5-Base (d=768) Contriever (d=768) BGE-Large (d=1024)
1.00 1.00 1.00 1.00 1.00 1.00
0.80 1.00 1.00 1.00 1.00 1.00
0.40 0.40 0.00 1.00 0.40 0.80
1.000 1.000 0.998 0.997 0.926 0.953
0.914 0.940 0.957 0.978 0.922 0.966
0.816 0.886 0.645 0.946 0.759 0.928
Table 10: Multi-agent SIR propagation results (N = 20, pre-store = 0.30, T = 30, 5 initial poison entries). Averaged over 5 independent seeds; timing columns show mean steps. Defense No Defense M EM SAD (σ = 2.0) Composite (σ = 1.0)
Final Spread
Step to 50%
Step to 90%
Secondary Entries
Quarantined
1.00 1.00 0.00
5 5 >30
14 14 >30
23 18 0
— 5 2
L
Computational complexity
M
Distributional robustness analysis
We extend M EM SAD’s guarantees to the distributionally robust setting where the adversary can perturb the score distribution within a Wasserstein ball. Proposition 21 (Distributionally robust detection). Let P̂0 be the empirical benign score distribution from N calibration samples. For any adversarial score distribution P1 and perturbation class U = {Q : W1 (Q, P1 ) ≤ ϵ}: ϵ inf TPR(τ ; Q) ≥ TPR(τ ; P1 ) − . (20) Q∈U σ̂ Proof. The indicator 1[s > τ ] is not Lipschitz; we instead use the dual characterization directly. For any two distributions Q, P1 on R with W1 (Q, P1 ) ≤ ϵ, we have |PQ (s > τ ) − PP1 (s > τ )| = |FP1 (τ ) − FQ (τ )| ≤ W1 (Q, P1 )/σ̂, where the last inequality follows because the score CDF F has density bounded by 1/σ̂ (Gaussian scores with variance σ̂ 2 ), so |F (τ + h) − F (τ )| ≤ |h|/σ̂. Hence inf Q∈U TPR(τ ; Q) ≥ TPR(τ ; P1 ) − ϵ/σ̂. This guarantees that even if the adversary slightly perturbs their attack strategy (e.g., via randomized synonym selection), M EM SAD’s TPR degrades gracefully. For ϵ = 0.01σ̂: ∆TPR ≤ 0.01, consistent with the observed stability in Table 4. Proposition 22 (PAC-style detection guarantee). For N i.i.d. calibration samples from P0 , with probability ≥ 1 − δ over the calibration set, M EM SAD’s threshold τ̂N satisfies: r r log(2/δ) log(2/δ) ∗ ∗ FPR(τ̂N ) ≤ FPR(τ ) + , TPR(τ̂N ) ≥ TPR(τ ) − , (21) 2N 2N where τ ∗ = µ + κσ is the population-optimal threshold. p Proof. By the DKW inequality, supt |FN (t) − F (t)| ≤ log(2/δ)/(2N ) w.p. ≥ 1 − δ, where FN , F are empirical and population CDFs. Since FPR(τ ) = 1−F0 (τ ) and TPR(τ ) = 1−F1 (τ ), the bound follows from the uniform convergence of the empirical CDF to the true CDF at the estimated threshold. 20
True Positive Rate (TPR)
(a) SAD TPR by Encoder (κ = 2.0) 1.00
1.0 0.8
1.00
1.00
1.00
1.00
1.00 1.00 1.00
1.00
1.00
0.80
0.6 0.4
0.40
0.40
0.40
Minja InjecMem AgentPoison (trig. cal.)
0.2 0.0 MiniLM-L6 (384-d)
MPNet-Base (768-d)
Para-MiniLM (384-d)
E5-Base (768-d)
Contriever (768-d)
False Positive Rate (FPR)
(b) SAD FPR by Encoder (κ = 2.0) Minja InjecMem AgentPoison (trig. cal.)
1.0 0.8 0.6 0.4 0.2
0.14 0.14
0.21 0.21
0.18 0.18 0.09
0.13 0.13
0.16 0.16
0.08
0.07
MPNet-Base (768-d)
Para-MiniLM (384-d)
0.14 0.07
0.0 MiniLM-L6 (384-d)
E5-Base (768-d)
Contriever (768-d)
Encoder Model
Figure 6: Encoder generalization: M EM SAD TPR (top) and FPR (bottom) across 6 encoders at κ = 2.0. Triggered AGENT P OISON achieves TPR = 1.00 on all encoders; I NJEC MEM is more encoder-sensitive (TPR 0.00–1.00). Table 11: Hypothesis tests (H0 : TPR = 0, Bonferroni α′ = 0.003). Defense Watermark M EM SAD M EM SAD Proactive Proactive Composite
Attack AP / MJ MJ IM AP MJ All
p-value −6
< 10 < 10−6 0.001 < 10−6 0.24 < 10−6
Reject?
Power
✓ ✓ ✓ ✓ — ✓
1.00 1.00 0.92 1.00 0.08 1.00
At N = 200, δ = 0.05: the excess error is ≤ 0.096, meaning M EM SAD’s empirical FPR of 0.000 implies true FPR ≤ 0.096 with 95% confidence. The Clopper-Pearson validation (Table 12) provides a tighter bound of 0.004 by exploiting the binomial structure.
N
OOD detection baseline comparison
We compare M EM SAD against three standard OOD detection methods adapted to the memory poisoning setting. Concurrent memory/RAG defenses (A-MemGuard [Li et al., 2025], RevPRAG [Tan et al., 2025], RAGDefender [Anonymous, 2025c]) are not benchmarked: RevPRAG operates post21
(a) Multi-Agent SIR Propagation Fraction of Agents Exposed
1.0 90% threshold
0.8
0.6
0.4 No Defense MemSad (σ = 2.0)
0.2
Composite (σ = 1.0) 0.0 5
10
15
20
25
30
25
30
Propagation Step (b) Secondary Entry Growth
Secondary Poison Entries
25
No Defense MemSad Composite
20 15 10 5 0 5
10
15
20
Propagation Step
Figure 7: Multi-agent SIR propagation (mean ±1σ over 5 seeds). Top: fraction of agents exposed over 30 steps. Bottom: secondary poison entry growth. Composite (σ = 1.0) prevents spread entirely; M EM SAD (σ = 2.0) matches no-defense spread timing but reduces secondary entries by 22%, as 4 of 5 initial entries pass the looser threshold and the composite is required to stop initial spread.
Table 12: FPR validation: Clopper-Pearson 95% CIs, 20 trials. Defense
FPR
95% CI
n/trial
M EM SAD (κ = 2.0) Watermark (zthr = 1.5) Proactive (τ = 0.19)
0.000 0.000 0.010
[0.000, 0.004] [0.000, 0.004] [0.004, 0.023]
1000 1000 1000
retrieval (read-time), not at write-time, and the others P lack public implementations as of submission: Energy Score [Liu et al., 2020] (score = −T log i exp(cos(e, qi )/T )), Mahalanobis distance [Lee et al., 2018] in embedding space, and KNN distance (k = 10) to the benign calibration set. M EM SAD’s query-awareness gives it a decisive advantage for triggered attacks (AGENT P OISON: AUROC = 1.000 vs. Energy’s 0.945). Energy Score is competitive on MINJA AUROC (0.969) but has lower TPR at the operating threshold. Mahalanobis distance fails catastrophically (FPR = 0.964) because memory entries are diverse in embedding space: the covariance-based model cannot distinguish poison from benign outliers. 22
SAD Threshold Sweep: TPR vs. FPR (κ = 0.5 . . . 4.0) 1.0 κ = 2.0 (operating point)
True Positive Rate (TPR)
0.8
0.6
0.4
Random Minja (plain cal.)
0.2
AgentPoison (plain cal.) AgentPoison (triggered cal.) InjecMem (plain cal.)
0.0 0.0
0.2
0.4
0.6
0.8
1.0
False Positive Rate (FPR)
(a) ROC as κ varies from 0.5 to 4.0. Plain-Query Calibration (AgentPoison Not Detected)
Triggered-Query Calibration (AgentPoison Detected) 40
Benign entries AgentPoison entries Threshold (κ = 2.0) = 0.473
30 25
30 25
Density
20
Density
Benign entries AgentPoison entries Threshold (κ = 2.0) = 0.436
35
15
20 15
10 10 5
5
0
0 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
Max Query Similarity s(c)
0.4
0.6
0.8
1.0
Max Query Similarity s(c)
(b) Plain vs. triggered calibration.
Figure 8: M EM SAD detection. (Top) MINJA traces near-ideal ROC; triggered calibration recovers TPR = 1.00 for AGENT P OISON at κ = 2.0 (⋆). (Bottom) Threshold shifts from 0.482 to 0.432.
O
Calibration query sensitivity
AUROC (ranking quality) is stable across all regimes: MINJA and I NJEC MEM maintain AUROC = 0.914 and 0.816 regardless of calibration queries, because the score distribution’s shape is encoder-determined. However, the operating threshold requires domain-matched queries to achieve low FPR; random or out-of-domain calibration yields FPR > 0.95. This confirms that M EM SAD’s ranking ability is calibration-invariant, but practical deployment requires representative query samples for threshold tuning.
P
Cross-corpus generalization: Natural Questions
To validate that results generalize beyond the synthetic corpus, we evaluate all three attacks on a mixed corpus: the 82-entry NQ knowledge base (factual Wikipedia passages corresponding to the Natural Questions benchmark [Kwiatkowski et al., 2019]) padded with synthetic non-knowledge entries to |M| = 1,000, with the 50 NQ factoid questions as victim queries. 23
Table 13: Sample complexity for reliable detection (FPR + (1 − TPR) ≤ 0.05) across calibration regimes. Setting
ρ (SNR)‡
Lower bound Nmin
M EM SAD N
1.93 ≥ 4.0 1.59 1.27 0.50
1 1 2 3 15
1 · log(1/δ) 1 · log(1/δ) 2 · log(1/δ) 3 · log(1/δ) 15 · log(1/δ)
MINJA (plain) AGENT P OISON (triggered) AGENT P OISON (plain) I NJEC MEM (plain) Low-SNR adversary
2 2 ‡ Nmin √ = ⌈4(1 − ϵ) /ρ ⌉ from Theorem 8; M EM SAD N from Theorem 9. SNR estimated from AUROC via ρ = 2 Φ−1 (AUROC); low-SNR row is hypothetical. Practical calibration uses N = 50 for additional margin.
Table 14: Per-entry defense cost at write time. Defense M EM SAD (exact) M EM SAD (ANN) Watermark Validation Proactive Composite
Time
Space
Measured
O(md) O(d log m) O(|c| · |V|) O(|c| · |P |) O(|Qp |d) maxj O(dj )
O(md) O(md) O(|V|) O(|P |) O(|Qp |d) P j O(sj )
0.8ms 0.3ms 1.2ms 0.1ms 0.5ms 2.1ms
Apple M-series, 16GB; |M| = 200, m = 20, d = 384.
Two findings stand out. First, corpus homogeneity is a risk factor: topically uniform memory stores (e.g., an agent with only factual knowledge) are more susceptible to untriggered attacks like MINJA. Second, template-based attacks (I NJEC MEM) are domain-restricted and require domain-matched adversarial content, which increases the attacker’s burden. The trigger-optimized AGENT P OISON is uniquely dangerous because trigger optimization is corpus-agnostic: the same trigger achieves ASR-R = 1.00 regardless of the benign corpus type. M EM SAD calibrated on NQ queries achieves TPR = 0.00 for I NJEC MEM (consistent with ASR-R = 0.00; no poison is retrieved). For MINJA on NQ, the higher ASR-R = 0.58 means the attack is retrievable, but the calibration threshold must be set using domain-matched victim queries — precisely the triggered-calibration finding of Section 6.
Q
M EM SAD+ evaluation
Proposition 23 (M EM SAD+ combined detection). Let Dchar (c) := JSD(p̂c ∥p̂0 ) be the JensenShannon divergence between the character n-gram distribution of c and the benign corpus baseline p̂0 . For synonym substitution c′ = sub(c, wi , wi′ ) with i = 1, . . . , r: Dchar (c′ ) ≥ Dchar (c) − r · δchar ,
(22)
where δchar := max(w,w′ ) |JSD(p̂c[w→w′ ] ∥p̂0 ) − JSD(p̂c ∥p̂0 )| is the per-substitution JSD shift. For typical synonym pairs, δchar ≫ ϵsyn . M EM SAD+ flags c if s(c; H) > τsem or Dchar (c) > τchar .
R
Compound exposure analysis
Memory poisoning compounds over sessions: P (compromise in N sessions) = 1−(1−ASR-R)N q . MINJA at ASR-R = 0.14 reaches 90% compromise in 4 sessions; I NJEC MEM at ASR-R = 0.07 reaches 95% in 9 sessions. Composite defense (ASR-R∗ = 0) eliminates this compounding entirely. 24
Table 15: OOD detection baseline comparison at |M| = 1,000. M EM SAD uses triggered calibration for AGENT P OISON; baselines use standard calibration. TPR (at threshold)‡
AUROC Method
AP
MJ
IM
AP
MJ
IM
M EM SAD (ours) Energy Score Mahalanobis KNN (k = 10)
1.000 0.945 0.420 0.533
0.914 0.969 0.694 0.786
0.816 0.698 0.452 0.534
1.00 0.40 1.00 0.00
0.80 0.20 1.00 0.40
0.40 0.40 1.00 0.00
‡ TPR at each method’s native operating threshold (κ = 2.0 for M EM SAD, σ = 2.0 for Mahalanobis). Mahalanobis achieves TPR = 1.00 but at FPR = 0.964 (unusable); AUROC is the fairer comparison metric. Bold = best AUROC per attack.
Table 16: Calibration query sensitivity: M EM SAD AUROC across calibration regimes (κ = 2.0, |M| = 1,000). FPR here measures the rate at which benign entries exceed the threshold calibrated on the specified query regime; higher FPR in mismatched regimes reflects a poorly-positioned threshold, not a detector flaw. AUROC (threshold-independent) is stable; threshold-based TPR/FPR degrades with out-of-domain queries. AUROC
FPR
Calibration regime
AP
MJ
IM
AP
MJ
Domain-matched Partial overlap (50%) Random queries Out-of-domain
1.000 0.822 0.822 0.822
0.914 0.914 0.914 0.914
0.816 0.816 0.816 0.816
0.090 0.370 0.954 0.974
0.138 0.370 0.954 0.974
S
Tool-use agent evaluation
T
Production memory system validation
Mem0’s internal LLM reformulation strips trigger-optimized structure (AGENT P OISON: ASR-R = 0.00). Raw vector stores (FAISS, Pinecone, Weaviate) remain fully exposed. This reveals a memory system vulnerability taxonomy: LLM-mediated stores provide implicit defense at the cost of latency (∼3s/entry vs. <1ms).
U
LLM sanitization baseline
We evaluate GPT-4o-mini as a zero-shot write-time sanitization baseline: for each candidate memory entry, a structured prompt asks the model to classify it as a legitimate memory entry or an adversarial injection and return {is_poison, confidence} as JSON. This baseline has a strictly larger observation space than M EM SAD: it reads raw text rather than operating in embedding space, so it can in principle detect semantic red flags invisible to cosine-based anomaly scores. Results. GPT-4o-mini achieves TPR = 1.000, FPR = 0.000 (perfect classification) on the synthetic corpus at threshold τ = 0.5, with AUROC = 1.000. Mean latency is 1.2 s per entry—roughly 1,000× higher than M EM SAD (∼1 ms). Comparison with M EM SAD. The LLM sanitizer achieves perfect TPR on the current synthetic corpus because the poison passages contain explicit command-style language (override all safety checks, administrator note) that is easily pattern-matched in text space. M EM SAD achieves comparable TPR (1.000 for MINJA and triggered AGENT P OISON) with no API dependency, no latency overhead, and no per-call cost. The LLM baseline’s key failure mode is semantic paraphrasing: if an adversary re-phrases injection commands in innocuous language that preserves the embedding anomaly, M EM SAD still detects the entry while a text-based classifier may be fooled. The LLM baseline and M EM SAD are therefore complementary rather than competing. 25
Table 17: Cross-corpus generalization: ASR-R on NQ-based corpus (|M| = 1,000, 3 seeds). Synthetic results (Table 2) shown for reference. Attack AGENT P OISON (triggered) MINJA I NJEC MEM
NQ corpus ASR-R
Synthetic ASR-R
1.00 ± 0.00 0.58 ± 0.06 0.00 ± 0.00
1.00 0.14 0.07
Three findings: (1) Trigger-optimized attacks transfer universally; (2) MINJA’s ASR-R increases on the more topically homogeneous NQ corpus (less dilution by off-topic entries); (3) I NJEC MEM’s broad-anchor templates, optimized for security-domain contexts, do not retrieve against factual QA queries.
Synonym Substitution Evades Detection; DPR-HotFlip Does Not MemSAD Combined Score s(p)
0.70
Original poison Synonym-substituted (adaptive) DPR-HotFlip optimized µ + 2σ threshold
0.65 0.60 0.55 0.50 0.45 0.40 0.35
evasion = 0%
evasion = 100%
evasion = 0%
Synonym
DPR-HotFlip
0.30 Original
Poison Construction
Figure 9: Synonym substitution is the only attack construction that evades M EM SAD. M EM SAD combined scores for n = 60 poison passages per condition, at the µ̂ + 2σ̂ operating threshold (dashed). Original poisons are detected with TPR=1.00; DPR-HotFlip optimization preserves attack utility and remains detected; greedy word-level synonym substitution (adaptive adversary, Sec. 6.4) shifts the score distribution below the threshold, producing the paper’s empirical 80–100% evasion finding. This is the empirical face of Proposition 11: the coupling theorem holds against continuous perturbations but discrete synonym jumps have ϵsyn ≈ 0. Practical tradeoffs. LLM sanitization adds ∼1.2 s/entry and an API dependency; M EM SAD runs locally in <1 ms. In a layered deployment, M EM SAD serves as the low-latency primary gate, with LLM sanitization reserved for entries that M EM SAD flags as borderline.
V
Additional figures
26
Table 18: M EM SAD+ vs. M EM SAD: TPR comparison on original and synonym-substituted passages (|M| = 1,000, κ = 2.0). M EM SAD Attack AGENT P OISON MINJA I NJEC MEM
†
M EM SAD+
Original
Synonym
Original
Synonym
1.00 1.00 0.20
1.00 0.80 0.00
1.00 1.00 0.60
1.00 0.80 0.40
† Triggered calibration. Character n-gram JSD features improve I NJEC MEM detection by 3×.
Table 19: Compound exposure: cumulative compromise probability over agent sessions (q = 5 queries/session, |M| = 1,000). Attack
ASR-R
N50%
N90%
N95%
E[N ]
Defended
AGENT P OISON MINJA I NJEC MEM
1.00 0.14 0.07
1 1 2
1 4 7
1 4 9
1.0 1.9 3.3
ASR-R∗ = 0 ASR-R∗ = 0 ASR-R∗ = 0
Np : sessions to reach p compromise probability. E[N ]: expected sessions to first compromise.
Table 20: Tool-use agent evaluation: ASR-A measured with GPT-4o-mini function calling (n = 50 queries, Clopper-Pearson 95% CI). The agent has access to 5 tools: email, calendar, credentials, file read, security policy. Attack AGENT P OISON MINJA I NJEC MEM
ASR-A
ASR-A | ret
Poison Ret.
Tools/Query
0.48[0.34,0.62] 0.00[0.00,0.07] 0.00[0.00,0.07]
0.51 0.00 0.00
47/50 5/50 5/50
1.52 0.26 0.08
ASR-A | ret: conditioned on poison in retrieved context. Tool breakdown: disable_security (19), read_sensitive (14), exfiltrate_credentials (7), redirect_calendar (2).
Table 21: Production validation: ASR-R on Mem0 (LLM-mediated) vs. FAISS (raw vector store) at |M| = 1,000. Attack
FAISS ASR-R
Mem0 ASR-R
Reduction
1.00 0.14 0.07
0.00 0.00 0.05
−1.00 −0.14 −0.02
AGENT P OISON MINJA I NJEC MEM
Mem0’s LLM reformulation strips trigger-optimized structure, providing implicit defense.
Table 22: LLM sanitization baseline (GPT-4o-mini, zero-shot JSON classifier, threshold τ =0.5). Evaluated on 20 poison + 50 benign entries per attack. Attack
TPR
FPR
AUROC
Latency (s/entry)
AGENT P OISON MINJA I NJEC MEM
1.000 1.000 1.000
0.000 0.000 0.000
1.000 1.000 1.000
1.16 1.20 1.27
27
density
µ̂ + κσ̂ P0 (benign) P1 (poison)
certified detection
cos(E(c), E(q ∗ ))
sadv
s̄
κσ̂ + η ∆s = sadv − s̄
Figure 10: Certified detection radius (Lemma 7). When ∆s > κσ̂ + η, the adversarial distribution P1 falls entirely within the certified region, guaranteeing TPR = 1. Corpus Scaling: ASR-R at |M| = 200 vs. 1,000 1.000
|M| = 200
|M| = 1,000
1.000
1.0
0.8
ASR-R
0.650
0.6
0.550
0.4
0.2
0.142 0.066
0.0 AgentPoison
Minja
InjecMem
Figure 11: Corpus scaling: ASR-R at |M| = 200 vs. |M| = 1,000. Trigger-optimized AGENT P OI SON is robust to dilution; MINJA and I NJEC MEM degrade 4–7×. Measured vs. Modelled ASR-A Modelled GPT-2 (lower bound) GPT-4o-mini
1.0
ASR-A
0.8
0.6
0.4
0.2
0.0 AgentPoison
Minja
InjecMem
Figure 12: Measured vs. modelled ASR-A. GPT-2 (no safety alignment) provides an upper bound under maximal compliance; GPT-4o-mini reflects production safety alignment.
28