MemSAD : Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents Ishrith Gowda 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 × 4\times (from ASR-R = 0.25 \text{ASR-R}=0.25 to 1.00 1.00 ). Our primary contribution is MemSAD ( Semantic Anomaly Detection ), a calibration-based defense grounded in a gradient coupling theorem : under encoder regularity, the max-cosine anomaly score gradient is provably identical to the retrieval objective gradient (the deployed combined score retains directional coupling, Corollary 17 ), 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 ) \Omega(1/\rho^{2}) calibration samples and MemSAD achieves this up to log ⁡ ( 1 / δ ) \log(1/\delta) factors. We further derive online regret bounds for rolling calibration with optimal window selection at rate O ⁡ ( σ 2 / 3 ​ Δ 1 / 3 ) O(\sigma^{2/3}\Delta^{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 3\times 5 attack-defense matrix with bootstrap confidence intervals, Bonferroni-corrected hypothesis tests, and Clopper-Pearson validation (20 trials, n = 1,000 n=1{,}000 ) confirm the theory: composite defenses achieve TPR = 1.00 \text{TPR}=1.00 , FPR = 0.00 \text{FPR}=0.00 across all attacks, while synonym substitution evades detection at Δ ​ ASR-R ≈ 0 \Delta\text{ASR-R}\approx 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. AgentPoison ( Chen et al. 2024 ) formulates trigger optimization as a constrained gradient problem over DPR ( Karpukhin et al. 2020 ) embeddings ( \alpha=\textsc{write} ). MINJA ( Dong et al. 2025 ) extends the setting to query-only access via progressive-shortening indication ( \alpha=\textsc{query} ). InjecMEM ( Anonymous 2026 ) achieves single-interaction injection via retriever-agnostic anchors ( \alpha=\textsc{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 MemSAD 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 per-entry 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 MemSAD +: 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 ( \text{ASR-A}=0.48 ), and Mem0 production validation. (4) Rigorous evaluation. A 3\times 5 attack-defense matrix with Bonferroni-corrected hypothesis testing, bootstrap CIs, and Clopper-Pearson validation demonstrating composite portfolios achieve \text{TPR}=1.00 , \text{FPR}=0.00 across all attacks. 2 Related work Memory poisoning attacks. Chen et al. 2024 report \text{ASR-R}\geq 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 ( \text{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(|\mathcal{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 8 ) 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 (\hat{\mu},\hat{\sigma},\kappa) ; the gradient coupling theorem provides the formal guarantee, while Proposition 13 characterizes where it fails. 3 Formal threat model Definition 1 (Memory-augmented agent) . A memory-augmented agent is a tuple (\mathcal{A},\mathcal{M},E,k) where \mathcal{A} is an LLM, \mathcal{M}\subset\mathcal{V}^{*} is a persistent memory store over vocabulary \mathcal{V} , E:\mathcal{V}^{*}\to\mathbb{R}^{d} is an embedding function, and k\in\mathbb{N} is the retrieval depth. At each interaction with query q , the agent retrieves \Ret(\mathcal{M},q,k)=\argmax_{\begin{subarray}{c}S\subseteq\mathcal{M}\\ |S|=k\end{subarray}}\sum_{m\in S}\cosim(E(q),E(m)), (1) where \cosim(u,v)\coloneqq u^{\top}v/(\|u\|\|v\|) denotes cosine similarity. Definition 2 (Memory poisoning threat model) . An adversary \mathcal{S}=(\mathcal{Q}_{v},n,\alpha) targets victim queries \mathcal{Q}_{v}\subset\mathcal{V}^{*} by injecting \mathcal{P}=\{p_{1},\ldots,p_{n}\} into \mathcal{M} under access model \alpha\in\{\textsc{write},\textsc{query},\textsc{single}\} to maximize: \displaystyle\text{ASR-R}(\mathcal{P},\mathcal{Q}_{v}) \displaystyle\coloneqq|\{q\in\mathcal{Q}_{v}:\mathcal{P}\cap\Ret(\mathcal{M}\cup\mathcal{P},q,k)\neq\emptyset\}|/|\mathcal{Q}_{v}|, (2) \displaystyle\text{ASR-A}(\mathcal{P}) \displaystyle\coloneqq\mathbb{P}[\mathcal{A}\text{ executes adversarial action}\mid\text{poison retrieved}], (3) \displaystyle\text{ASR-T}(\mathcal{P},\mathcal{Q}_{v}) \displaystyle\coloneqq\text{ASR-R}\cdot\text{ASR-A}. (4) Definition 3 (Stackelberg game formulation) . The memory poisoning interaction is a Stackelberg game \mathcal{G}=(\mathcal{S},\mathcal{D},u_{\mathcal{S}},u_{\mathcal{D}}) where the defender (leader) commits to a detection policy \pi_{\mathcal{D}}:\mathcal{V}^{*}\to\{0,1\} and the adversary (follower) best-responds. The defender’s utility is u_{\mathcal{D}}(\pi_{\mathcal{D}},\mathcal{P})=-\text{ASR-R}(\mathcal{P}\setminus\mathcal{F}(\pi_{\mathcal{D}},\mathcal{P}),\mathcal{Q}_{v})-\lambda\cdot\text{FPR}(\pi_{\mathcal{D}}) for \lambda>0 , where \mathcal{F}(\pi_{\mathcal{D}},\mathcal{P})=\{p\in\mathcal{P}:\pi_{\mathcal{D}}(p)=1\} is the filtered set; the adversary’s utility is u_{\mathcal{S}}(\mathcal{P})=\text{ASR-T}(\mathcal{P},\mathcal{Q}_{v})=\text{ASR-R}(\mathcal{P},\mathcal{Q}_{v})\cdot\text{ASR-A}(\mathcal{P}) . The leader and best-response sets are \displaystyle\pi_{\mathcal{D}}^{*} \displaystyle=\argmin_{\pi_{\mathcal{D}}\in\Pi}\;\Big[\,\max_{\mathcal{P}\in\mathcal{B}(\pi_{\mathcal{D}})}\text{ASR-R}(\mathcal{P}\setminus\mathcal{F}(\pi_{\mathcal{D}},\mathcal{P}),\mathcal{Q}_{v})\;+\;\lambda\cdot\text{FPR}(\pi_{\mathcal{D}})\,\Big], (5) \displaystyle\mathcal{B}(\pi_{\mathcal{D}}) \displaystyle=\argmax_{\mathcal{P}\subseteq\mathcal{V}^{*},\,|\mathcal{P}|\leq n}\;u_{\mathcal{S}}(\mathcal{P}\setminus\mathcal{F}(\pi_{\mathcal{D}},\mathcal{P})), (6) where \Pi=\{\pi(c)=\mathbf{1}[s(c;\mathcal{H})>\tau]:\tau>0\} is the class of threshold detectors operating on the candidate token sequence c\in\mathcal{V}^{*} via the score s(c;\mathcal{H}) . The access model \alpha from Definition 2 restricts the adversary’s effective strategy space to a subset \mathcal{V}^{*}_{\alpha}\subseteq\mathcal{V}^{*} : write access permits arbitrary token sequences ( \mathcal{V}^{*}_{\alpha}=\mathcal{V}^{*} ); query access restricts \mathcal{P} to passages reachable as auto-storage outputs of legitimate user queries; single access fixes |\mathcal{P}|=1 and pre-specifies its content. The formal game in Eqs. ( 5 )–( 6 ) instantiates the worst-case write -access adversary; the restricted variants are obtained by replacing \mathcal{V}^{*} in Eq. ( 6 ) with \mathcal{V}^{*}_{\alpha} . Assumption 4 (Payload invariance) . For the adversaries considered in Section 6 , \text{ASR-A}(\mathcal{P}) depends only on the trigger / payload structure embedded in each p\in\mathcal{P} and is invariant to the embedding-space placement of \mathcal{P} chosen by the optimizer. Hence the follower’s \argmax in Eq. ( 6 ) reduces to maximizing ASR-R over \mathcal{P} , with ASR-A acting as a multiplicative constant in ASR-T . Remark. Assumption 4 is satisfied by all three attacks studied here: AgentPoison fixes the trigger string before optimization, MINJA ’s injected directive is identical across queries, and InjecMEM ’s payload is a single static entry. Under this assumption the algebraic best-response in Eq. ( 6 ) coincides with the ASR-R -only formulation used implicitly in prior work. User q Memory \mathcal{M} \Ret(\mathcal{M},q,k) LLM \mathcal{A} Response top- k Adversary \mathcal{S} MemSAD \pi_{\mathcal{D}} p_{\mathrm{adv}} filter Figure 1 : Memory poisoning as a Stackelberg game (Definitions 2 – 3 ). The defender commits to \pi_{\mathcal{D}} ; the adversary best-responds by injecting p_{\mathrm{adv}} . Assumption 5 (Encoder regularity) . E:\mathcal{V}^{*}\to\mathbb{R}^{d} 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 5 (iii), \cosim(E(q),E(m))=E(q)^{\top}E(m) and retrieval reduces to maximum inner product search. Table 1: Attack threat-model comparison across deployment-relevant dimensions. Property AgentPoison MINJA InjecMEM Access model \alpha write † query single Trigger required ✓ — — Retriever-agnostic — — ✓ Entries injected n 1\times 2\times 3\times Modelled ASR-A 0.68 0.76 0.57 † Triggered-query evaluation additionally requires query-channel access (e.g., front-end control or prompt injection); see Section 3 . Figure 1 illustrates the interaction. The three attacks (Table 1 ) span decreasing access requirements (write \supset query \supset single-interaction). Protocol distinction: Chen et al. 2024 ’s Algorithm 2 specifies triggered queries q\oplus T^{*} ; evaluating with plain queries (as in prior reproductions) measures a weaker setting ( \cosim\approx 0.45 vs. \approx 0.78 ), raising ASR-R from 0.25 to 1.00 . 4 MemSAD : Semantic Anomaly Detection 4.1 Algorithm and formal definition 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 6 ( MemSAD detector) . Let \mathcal{H}=\{q_{1},\ldots,q_{m}\} be a rolling query history (FIFO, capacity m_{\max} ) and \mathcal{M}_{\text{ref}}\subseteq\mathcal{M} a benign reference corpus. The anomaly score is s(c;\mathcal{H})\coloneqq\max_{q\in\mathcal{H}}\cosim(E(c),E(q)) , calibrated via \hat{\mu},\hat{\sigma} of \{s(m;\mathcal{H}):m\in\mathcal{M}_{\text{ref}}\} . Entry c is flagged if s(c;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma} for threshold parameter \kappa>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): s_{\text{comb}}(c;\mathcal{H})\coloneqq\tfrac{1}{2}\max_{q\in\mathcal{H}}\cosim(E(c),E(q))+\tfrac{1}{2}\cdot\frac{1}{|\mathcal{H}|}\sum_{q\in\mathcal{H}}\cosim(E(c),E(q)). (7) Algorithm 1 MemSAD pre-ingestion filtering 0: candidate c , query history \mathcal{H} , parameters (\hat{\mu},\hat{\sigma}) , threshold \kappa 1: s\leftarrow s_{\text{comb}}(c;\mathcal{H}) \triangleright O(md) time 2: if s>\hat{\mu}+\kappa\cdot\hat{\sigma} then 3: reject c 4: else 5: accept c into \mathcal{M} 6: end if The full pre-ingestion procedure is given in Algorithm 1 ; a block-diagram view of the same pipeline (candidate \to encoder \to cosine vs. \mathcal{H} \to s_{\text{comb}} \to threshold compare \to 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 \mathbb{S}^{d-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 7 (Gradient coupling: necessity, sufficiency, and canonicity) . Let E satisfy Assumption 5 , e_{c}\coloneqq E(c) , q^{*}\coloneqq\argmax_{q\in\mathcal{H}}\cosim(e_{c},E(q)) , \mathcal{R}(e_{c})\coloneqq\cosim(e_{c},E(q^{*})) . (i) Sufficiency: For any differentiable \mathcal{D}=g\circ\mathcal{R} with monotone increasing g , g^{\prime}>0 : \nabla_{e_{c}}\mathcal{D}(e_{c})=g^{\prime}(\mathcal{R}(e_{c}))\cdot\nabla_{e_{c}}\mathcal{R}(e_{c}),\quad\text{so}\quad\langle\delta,\nabla\mathcal{D}\rangle<0\iff\langle\delta,\nabla\mathcal{R}\rangle<0. (8) Under L2-normalization (Assumption 5 (iii)), \nabla_{e_{c}}\mathcal{R}=E(q^{*})-(e_{c}^{\top}E(q^{*}))e_{c} . (ii) Necessity: If \mathcal{D} is not monotone in \mathcal{R} , there exist thresholds \tau_{\text{ret}},\tau_{\text{det}} and a continuous path \gamma:[0,1]\to\mathbb{S}^{d-1} with \mathcal{R}(\gamma(1))>\tau_{\text{ret}} yet \mathcal{D}(\gamma(1))<\tau_{\text{det}} : the adversary can traverse continuously to high retrieval rank while evading detection. (iii) Canonicity (parametric-free): Among all (i)-coupled detectors, g=\mathrm{id} is canonical in the sense that the threshold \mathcal{R}(e_{c})>\tau implements the minimum-sufficient-statistic test without requiring knowledge of the underlying parametric family of the benign / adversarial score distributions. Any strictly-monotone bijection g of \mathcal{R} remains minimal sufficient (Lehmann–Scheffé); in this sense g=\mathrm{id} is not the unique minimal sufficient statistic, but it is the unique element of the equivalence class that is computable from e_{c} and the calibration history \mathcal{H} without estimating p_{0},p_{1} . Proof. (i) The chain rule gives \nabla\mathcal{D}=g^{\prime}(\mathcal{R})\cdot\nabla\mathcal{R} ; g^{\prime}>0 preserves the sign of every directional derivative. Under Assumption 5 (iii), the sphere gradient is \nabla_{e_{c}}\cosim(e_{c},v)=v-(e_{c}^{\top}v)e_{c} . (ii) Non-monotonicity implies \exists\,e_{c},e_{c}^{\prime} with \mathcal{R}(e_{c}^{\prime})>\mathcal{R}(e_{c}) but \mathcal{D}(e_{c}^{\prime})<\mathcal{D}(e_{c}) . By connectedness of \mathbb{S}^{d-1} , there exists a continuous path \gamma from e_{c} to e_{c}^{\prime} . Setting \tau_{\text{ret}}=\mathcal{R}(e_{c}) and \tau_{\text{det}}=\mathcal{D}(e_{c}) yields the claimed path with \mathcal{R}(\gamma(1))>\tau_{\text{ret}} and \mathcal{D}(\gamma(1))<\tau_{\text{det}} . (iii) Under Gaussian score distributions (Theorems 10 – 11 ), the likelihood ratio p_{1}(e)/p_{0}(e) is a monotone function of \cosim(e,e_{q^{*}}) , so by the Neyman–Fisher factorization ( Lehmann 1959 ) , \mathcal{R}(e_{c}) is sufficient for the binary test H_{0} vs. H_{1} . Minimality follows from Lehmann–Scheffé ( Lehmann 1959 ) , and any strictly monotone bijection of a minimal sufficient statistic remains minimal sufficient (information-preserving). The canonicity claim is computational, not statistical: implementing the threshold test on g(\mathcal{R}) for non-trivial g requires either computing g itself (which depends on p_{0},p_{1} when g is the likelihood ratio) or accepting a possibly non-equivariant decision boundary under recalibration. The choice g=\mathrm{id} avoids these requirements and is the unique distribution-free minimal-sufficient implementation. ∎ The combined score s_{\text{comb}} deployed by Algorithm 1 (Eq. 7 ) is a positive linear combination of s_{\max} and s_{\mathrm{mean}} and therefore does not satisfy strict gradient identity with \mathcal{R}=s_{\max} . It preserves directional coupling (Corollary 17 , Appendix B.8 ): under the directional-monotonicity assumption stated there, every continuous perturbation that decreases s_{\text{comb}} also decreases \mathcal{R} . The strict \nabla\mathcal{D}\equiv\nabla\mathcal{R} identity holds for s_{\max} alone; the combined score is deployed because it improves detection of distributed attacks at the cost of weakening the coupling from strict identity to directional alignment. The gradient coupling reflects a deeper geometric structure: the Fisher-Rao metric induced by the score family is rank-1 ( g^{F}=\hat{\sigma}^{-2}\nabla\mathcal{R}\nabla\mathcal{R}^{\top} ), so any continuous evasion path pays retrieval cost in exact proportion to Fisher-Rao distance ( Amari 2016 ) (Theorem 14 , Appendix B.6 ). (a) Mechanism (schematic). (b) Empirical confirmation (DPR-HotFlip). Figure 2 : Gradient coupling, visualized. ( 2(a) ) 2-D projection: dashed contour marks the \hat{\mu}+\kappa\hat{\sigma} firing region around \mathcal{Q} ; the adversary’s gradient \nabla_{p}\mathcal{L}_{\mathrm{ret}} pushes the poison into the firing region along the direction that raises s (Thm. 7 ). ( 2(b) ) DPR-HotFlip: \mathcal{L}_{\mathrm{ret}} and s mirror; detection fires at t=9 . 4.3 Certified detection guarantee We now provide an instance-specific guarantee: when the adversarial-benign similarity gap exceeds the calibration uncertainty, MemSAD certifiably detects the adversarial passage. Lemma 8 (Certified detection radius) . Let E satisfy Assumption 5 and let c be an adversarial passage achieving \rank(E(c),\mathcal{M})\leq k for victim query q^{*} . Define the benign similarity ceiling \bar{s}\coloneqq\max_{m\in\mathcal{M}_{\text{ref}}}\cosim(E(m),E(q^{*})) , the adversarial similarity s_{\text{adv}}\coloneqq\cosim(E(c),E(q^{*})) , and the gap \Delta_{s}\coloneqq s_{\text{adv}}-\bar{s} . If the calibration satisfies |\tau_{N}-\tau^{*}|\leq\eta (Theorem 11 ) and the gap exceeds \Delta_{s}>\kappa\hat{\sigma}+\eta, (9) then MemSAD detects c with certainty: s(c;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma} . Proof sketch. Since s_{\text{adv}}=\bar{s}+\Delta_{s} and the deployed score s(c;\mathcal{H})=\alpha s_{\max}(c;\mathcal{H})+(1-\alpha)s_{\text{mean}}(c;\mathcal{H}) satisfies s(c;\mathcal{H})\geq\alpha\,s_{\text{adv}} when q^{*} attains the maximum (under Assumption 9 below), the gap condition \Delta_{s}>\kappa\hat{\sigma}+\eta together with the calibration bound |\hat{\tau}_{N}-\tau^{*}|\leq\eta force s(c;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma} . Full proof in Appendix B.1 ; Figure 10 (Appendix W ) illustrates the certified region geometrically. ∎ Assumption 9 (Typical victim query) . The victim query q^{*} is not an outlier with respect to \mathcal{H} in the sense \cosim(E(q^{*}),E(c))\geq\hat{\mu}_{\mathcal{H}}(c)-\kappa\hat{\sigma}_{\mathcal{H}}(c) , where \hat{\mu}_{\mathcal{H}},\hat{\sigma}_{\mathcal{H}} are the running mean / std of similarities of c against \mathcal{H} . This is a one-sided concentration condition that holds with probability 1-O(e^{-\kappa^{2}/2}) under sub-Gaussian similarity statistics; deployments with adversarially-crafted query-history (e.g., a colluding user) violate this assumption and lose the certified guarantee. 4.4 Theoretical foundations We establish four additional results; full statements and proofs are in Appendix B . Theorem 10 (Calibration sample complexity lower bound) . Let benign and adversarial scores be Gaussian with means \mu_{0}<\mu_{1} and common variance \sigma^{2} , separation \rho=(\mu_{1}-\mu_{0})/\sigma , and let \Phi be the standard normal CDF. The single-test Bayes error at the oracle threshold \tau^{*}=(\mu_{0}+\mu_{1})/2 is B(\rho)=\Phi(-\rho/2) , irreducible at any calibration size. For any threshold detector calibrated from N i.i.d. benign samples, the excess error over the oracle is bounded below as \mathbb{P}_{\text{err}}(\hat{\pi}_{N})-B(\rho)=\Omega(\sigma\,|\hat{\tau}_{N}-\tau^{*}|) to first order in |\hat{\tau}_{N}-\tau^{*}| . Le Cam’s two-point inequality applied to the threshold-estimation problem then gives, for any procedure that produces \hat{\tau}_{N} from N benign samples and achieves expected excess error at most \epsilon uniformly over the parameter family, the requirement N\geq c(\epsilon)/\rho^{2} for an absolute constant c(\epsilon)>0 . Conversely, MemSAD achieves |\hat{\tau}_{N}-\tau^{*}|=O(\sigma\sqrt{\log(1/\delta)/N}) (Theorem 11 ), matching the lower bound up to a \log(1/\delta) factor. Interpretation. Theorem 10 bounds the calibration sample complexity, not the single-test Bayes error: the irreducible B(\rho) persists for any N and reflects the intrinsic Gaussian overlap. The result establishes that no calibrated threshold detector can drive its excess error below \Omega(1/\sqrt{N\rho^{2}}) over the oracle, and MemSAD attains this rate up to logarithmic factors. Theorem 11 (Calibration bound) . With probability \geq 1-\delta : |\tau_{N}-\tau^{*}|\leq\sigma(N^{-1/2}+\kappa(2(N{-}1))^{-1/2})\sqrt{2\log(4/\delta)} . Theorem 12 (Online calibration regret) . Under per-step drift \Delta , the optimal window m_{\max}^{*}=\Theta((\sigma/\Delta)^{2/3}) yields per-step regret O(\sigma^{2/3}\Delta^{1/3}) . We additionally prove a Wasserstein generalization bound guaranteeing graceful TPR degradation for novel attacks (Theorem 18 , Appendix B.9 ), and NP-hardness of optimal evasion via reduction from CVP (Proposition 15 , Appendix B.7 ), motivating the adversary’s shift to discrete synonym substitution. 4.5 The discrete synonym loophole Proposition 13 (Synonym-invariance loophole) . Let E satisfy \|E(\mathrm{sub}(c,w,w^{\prime}))-E(c)\|\leq\epsilon_{\text{syn}} for all synonym pairs (w,w^{\prime}) . For r substitutions yielding c^{\prime} : |\mathcal{R}(c^{\prime})-\mathcal{R}(c)|\leq r\epsilon_{\text{syn}},\qquad|s(c^{\prime};\mathcal{H})-s(c;\mathcal{H})|\leq r\epsilon_{\text{syn}}. (10) When \epsilon_{\text{syn}}\approx 0 , the adversary evades detection while preserving retrieval rank through discrete lexical substitution that bypasses gradient coupling. Proof. Cauchy-Schwarz gives |E(q)^{\top}(E(c^{\prime})-E(c))|\leq\|E(c^{\prime})-E(c)\| , and triangle inequality over r substitutions yields \|E(c^{\prime})-E(c)\|\leq r\epsilon_{\text{syn}} . ∎ This does not contradict Theorem 7 : the coupling holds for continuous perturbations in \mathbb{R}^{d} , while synonym substitution operates in the discrete token space where \epsilon_{\text{syn}}\approx 0 for paraphrase-trained encoders. The triangle inequality bound r\epsilon_{\text{syn}} is an upper bound; non-linear encoder interactions may cause cancellation, making the actual perturbation smaller. MemSAD +. We extend MemSAD with character n -gram JSD features that are provably not synonym-invariant (Proposition 27 , Table 18 , Appendix R ). Empirically, MemSAD + raises InjecMEM TPR from 0.00 (synonym-evaded) to 0.40 and original from 0.20 to 0.60 . 5 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 ) ( z_{\text{thr}}=1.5 , \text{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|\cdot|P|) ). Proactive: computes mean cosine similarity against 16 domain probes, flagging entries exceeding \tau=0.19 . Composite: weighted ensemble ( w_{\text{wm}}{=}0.50 , w_{\text{val}}{=}0.20 , w_{\text{pro}}{=}0.30 , \theta{=}0.50 ): flag if \sum_{j}w_{j}d_{j}(c)>\theta (Appendix C ). 6 Experiments 6.1 Setup Vector memory. FAISS IndexFlatIP with L2-normalized all-MiniLM-L6-v2 embeddings ( d=384 ). Benign corpus: |\mathcal{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 10^{2} – 10^{3} entries ( Chen et al. 2024 ; Dong et al. 2025 ) ; corpus-size ablation (Appendix D ) validates results across |\mathcal{M}|\in\{50,\ldots,1000\} . MemSAD calibration uses N=50 benign entries as the reference set (Theorem 11 predicts |\tau_{N}-\tau^{*}|\leq 0.044 at N=50 , \delta=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 |\mathcal{M}|=1{,}000 (Appendix Q ): AgentPoison transfers ( \text{ASR-R}=1.00\pm 0.00 ); MINJA ’s \text{ASR-R}=0.58\pm 0.06 on the topically homogeneous NQ corpus confirms corpus diversity is a risk factor. Poison counts: n=5 ( AgentPoison ), 10 ( MINJA ), 15 ( InjecMEM ). k=5 ; |\mathcal{Q}_{v}|=|\mathcal{Q}_{b}|=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. AgentPoison : centroid passage + DPR HotFlip trigger ( \cosim:0.71\to 0.78 ). MINJA : progressive-shortening with bridging steps ( p_{0}=0.98 , \lambda=0.10 ). InjecMEM : 3\times n_{\text{base}} broad-anchor entries from 8 templates. 6.2 Attack results Table 2: Attack results ( |\mathcal{M}|=1{,}000 , 100 queries, 5 seeds, bootstrap 95% CI). \text{ASR-A}^{\text{GPT-2}} : permissive model without safety alignment (high-compliance upper bound); \text{ASR-A}^{\text{4o-mini}} : production-aligned; † projected from original papers. Attack ASR-R \text{ASR-A}^{\dagger} \text{ASR-A}^{\text{GPT-2}} \text{ASR-A}^{\text{4o-mini}} \text{ASR-T}^{\dagger} Ben. Acc. AgentPoison (trig.) 1.00 0.68 0.90 0.20 0.68 1.00 MINJA 0.14_{[.13,.15]} 0.76 0.17 0.00 0.11 1.00 InjecMEM 0.07_{[.06,.07]} 0.57 0.00 0.00 0.04 0.98 Table 2 reports the main results at |\mathcal{M}|=1{,}000 . AgentPoison achieves \text{ASR-R}=1.00 under the triggered-query protocol, confirming trigger optimization defeats corpus dilution entirely. Untriggered attacks ( MINJA , InjecMEM ) are naturally mitigated by corpus scale ( 4.6\times and 7.1\times dilution). 1 1 1 ISR measures write-time injection success; ASR-R measures retrieval-time exposure. In plain text-response mode, measured \text{ASR-A}=0.20 under GPT-4o-mini is 3.4\times lower than the modelled \text{ASR-A}=0.68 ( Chen et al. 2024 ) , reflecting production safety alignment (Figure 12 , Appendix W ); the tool-use setting raises ASR-A to 0.48 (Table 20 , Appendix T ). 6.3 Attack-defense interaction matrix Table 3 reports the full 3\times 5 matrix. Watermark achieves \text{TPR}=1.00 in simulation but fails silently when auto-storage bypasses ingestion control, motivating MemSAD ’s content-level detection. MemSAD detects MINJA ( \text{TPR}=0.40 , AUROC 0.914 ) and InjecMEM ( \text{TPR}=0.20 , AUROC 0.816 ); triggered calibration raises AgentPoison to \text{TPR}=1.00 . Composite portfolios achieve \text{TPR}=1.00 , \text{FPR}=0.00 across all attacks (Proposition 20 ). Table 3: Defense TPR/FPR at operating thresholds ( \kappa=2.0 for MemSAD ). AP = AgentPoison , MJ = MINJA , IM = InjecMEM . TPR ( \uparrow ) FPR ( \downarrow ) AUROC Defense AP MJ IM AP MJ IM (avg) Watermark 1.00 1.00 1.00 0.00 0.00 0.00 0.991 Validation 0.60 0.40 0.80 0.10 0.10 0.10 — Proactive 1.00 0.07 0.60 0.01 0.01 0.01 — MemSAD (comb.) 0.00 † 0.40 0.20 0.00 0.00 0.00 0.867 Composite 1.00 1.00 1.00 0.00 0.00 0.00 — † Plain calibration; triggered: TPR = 1.00, FPR = 0.00, AUROC = 1.000. FPR validated over 20 trials ( n=1{,}000 each); Clopper-Pearson 95% CI: [0.000, 0.004] (Appendix I ). MINJA TPR varies across tables (here 0.40 , Table 15 0.80 , Table 9 0.80 – 1.00 ) due to poison-set size and calibration regime; each caption fixes its conditions. 6.4 Adaptive adversary analysis Following Tramèr et al. 2020 , we model a white-box adversary with full knowledge of (\hat{\mu},\hat{\sigma},\kappa) who applies greedy synonym substitution ( >60 pairs): c^{*}=\argmin_{c^{\prime}\in\mathrm{Syn}(c)}\;s(c^{\prime};\mathcal{H})\quad\text{s.t.}\quad\rank(E(c^{\prime}),\mathcal{M})\leq k. (11) Table 4: Adaptive adversary: evasion vs. retrieval degradation (Proposition 13 ). Attack Evasion \Delta\text{ASR-R} Subs/Entry Sim. \Delta AgentPoison 1.00 0.00 4.2 -0.01 MINJA 0.80 0.00 3.8 -0.02 InjecMEM 1.00 0.00 5.1 -0.01 Table 4 confirms Proposition 13 : 80–100% evasion with \Delta\text{ASR-R}\approx 0 using 3.8–5.1 substitutions, consistent with the bound r\epsilon_{\text{syn}}\leq 5.1\times 0.004=0.020 . The certified condition (Lemma 8 ) still holds for MINJA post-substitution ( \Delta_{s}=0.13>0.08 ) but fails for tighter margins. 6.5 Statistical validation Bonferroni-corrected one-sided binomial tests ( \alpha^{\prime}=0.003 , 15 comparisons) with H_{0}:\text{TPR}\leq\text{TPR}_{\text{base}}=0.05 (chance-level baseline reflecting random scoring at the operating FPR ): all composite results reject H_{0} with power =1.00 (Table 11 , Appendix H ). MemSAD AUROC at \kappa=2.0 : 0.914 ( MINJA ), 0.816 ( InjecMEM ), 0.870 ( AgentPoison , plain); triggered calibration raises AgentPoison to AUROC =1.000 . Theory validation: calibration bound predicts |\tau_{N}-\tau^{*}|\leq 0.022 at N=200 ; observed 0.014 (Table 8 , Appendix D ). 6.6 Ablation highlights Key results (full tables in Appendix D ): \kappa=2.0 with combined scoring optimal; AgentPoison robust across |\mathcal{M}|\in\{200,\ldots,1000\} while untriggered attacks degrade 4 – 7\times ; ASR-R saturates at n_{\text{base}}{=}5 ; triggered MemSAD achieves \text{TPR}=1.000 for AgentPoison on all 6 encoders incl. BGE-Large (Appendix E ); MemSAD dominates OOD baselines on triggered attacks (AUROC 1.000 vs. 0.945 Energy Score; Appendix O ); GPT-4o-mini text-level sanitization is complementary but 1000\times slower (Appendix V ); cross-corpus (NQ): AgentPoison retains \text{ASR-R}=1.00\pm 0.00 , MINJA rises to 0.58\pm 0.06 under topical homogeneity (Appendix Q ). Extended evaluations. Compound exposure (Appendix S ): MINJA at \text{ASR-R}=0.14 reaches 90% compromise in 4 sessions; composite defense ( \text{ASR-R}^{*}=0 ) is necessary. Tool-use agent (GPT-4o-mini, 5 tools): AgentPoison achieves \text{ASR-A}=0.48 [0.34, 0.62] (Appendix T ). Mem0 production: LLM-mediated storage drops AgentPoison to \text{ASR-R}=0.00 via reformulation; raw vector stores remain fully exposed (Appendix U ). 7 Discussion, limitations, and conclusion No single defense dominates across access models: watermarking fails under auto-storage; MemSAD needs triggered calibration for AgentPoison ; proactive complements both. Defender uncertainty over \alpha motivates composite portfolios ( \text{ASR-R}^{*}=0 , Proposition 20 ); recommended deployment is watermarking at ingestion plus rolling MemSAD at write-time ( \sim 2 ms/entry); A-MemGuard ( Li et al. 2025 ) is architecturally complementary at retrieval (Appendix N ). Limitations: Proposition 13 marks the structural frontier (paraphrase-trained encoders make synonyms near-isometric; MemSAD + closes this only partially); |\mathcal{M}|{=}1{,}000 synthetic entries (NQ in Appendix Q partially addresses); slow-drift regret assumption; piecewise-linear hardness. Conclusion: MemSAD is the first formally-guaranteed RAG memory-poisoning defense; open directions are closing the synonym gap, ANN scaling, and multi-modal extension. Appendix A Write-time pipeline diagram candidate entry c encoder E(\cdot) cosine sim vs. \mathcal{H} combined score s_{\text{comb}} compare to \hat{\mu}+\kappa\hat{\sigma} e_{c} s_{\max} s_{\mathrm{mean}} s accept: c\!\to\!\mathcal{M} reject: discard s\!\leq\!\hat{\mu}\!+\!\kappa\hat{\sigma} s\!>\!\hat{\mu}\!+\!\kappa\hat{\sigma} \mathcal{H} : rolling victim queries \mathcal{M}_{\text{ref}} : calibration (\hat{\mu},\hat{\sigma}) Figure 3 : MemSAD write-time pipeline (Def. 6 , Alg. 1 ). Every candidate c is embedded, scored against a rolling victim-query history \mathcal{H} via the combined max–mean similarity (Eq. 7 ), and compared to the \hat{\mu}+\kappa\hat{\sigma} threshold derived from the benign reference corpus \mathcal{M}_{\text{ref}} . Rejection happens before the entry is committed to memory — attacks are blocked at write time rather than filtered at retrieval. Appendix B Proofs of main results B.1 Proof of Lemma 8 (Certified detection radius) Setup. Recall \bar{s}=\max_{m\in\mathcal{M}_{\text{ref}}}\cosim(E(m),E(q^{*})) is the largest benign similarity to q^{*} in the reference set, and s_{\text{adv}}=\cosim(E(c),E(q^{*})) . We write s(c;\mathcal{H})=\alpha s_{\max}(c;\mathcal{H})+(1-\alpha)s_{\text{mean}}(c;\mathcal{H}) for the deployed combined score, and \hat{\mu},\hat{\sigma} for the calibration statistics on \mathcal{M}_{\text{ref}} . Step 1: lower-bound s_{\max}(c;\mathcal{H}) by s_{\text{adv}} . Since q^{*}\in\mathcal{H} (the victim query is in the rolling history), s_{\max}(c;\mathcal{H})=\max_{q\in\mathcal{H}}\cosim(E(c),E(q))\geq\cosim(E(c),E(q^{*}))=s_{\text{adv}} . Step 2: lower-bound s_{\text{mean}}(c;\mathcal{H}) under Assumption 9 . Under the typical-query assumption, s_{\text{mean}}(c;\mathcal{H})\geq\hat{\mu}_{\mathcal{H}}(c)-\kappa\hat{\sigma}_{\mathcal{H}}(c) , which absorbs into a constant offset \eta_{\text{mean}} depending on \kappa and the running statistics. We bound this contribution conservatively as s_{\text{mean}}(c;\mathcal{H})\geq\bar{s}-\eta_{\text{mean}} . Step 3: combined-score lower bound. Combining steps 1 and 2, s(c;\mathcal{H})\;\geq\;\alpha\,s_{\text{adv}}+(1-\alpha)(\bar{s}-\eta_{\text{mean}})\;=\;\alpha(\bar{s}+\Delta_{s})+(1-\alpha)(\bar{s}-\eta_{\text{mean}})\;=\;\bar{s}+\alpha\Delta_{s}-(1-\alpha)\eta_{\text{mean}}. Step 4: detection certificate. The detector fires iff s(c;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma} . By the calibration bound (Theorem 11 ), \hat{\mu}+\kappa\hat{\sigma}\leq\tau^{*}+\eta where \eta is the calibration tolerance and \tau^{*} is the population threshold. Since \bar{s}\geq\tau^{*}-\eta by the construction of \bar{s} as a sample max, s(c;\mathcal{H})-(\hat{\mu}+\kappa\hat{\sigma})\;\geq\;\alpha\Delta_{s}-(1-\alpha)\eta_{\text{mean}}-2\eta. The certificate s(c;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma} holds whenever \alpha\Delta_{s}>(1-\alpha)\eta_{\text{mean}}+2\eta , which under \alpha=1 (pure max-cosine score) reduces to \Delta_{s}>2\eta . The stated radius condition \Delta_{s}>\kappa\hat{\sigma}+\eta is the deployed-score equivalent absorbing the typical-query slack into \kappa\hat{\sigma} and tightening to a single calibration tolerance \eta . ∎ Failure mode. If Assumption 9 fails (e.g., q^{*} is an outlier in \mathcal{H} produced by a colluding user), the lower bound in Step 2 fails and the certificate becomes probabilistic rather than deterministic. The deterministic guarantee is recovered for the s_{\max} -only detector ( \alpha=1 ) at the cost of weaker detection of distributed attacks. B.2 Proof of Theorem 7 (geometric interpretation) Under L2-normalization, embeddings lie on \mathbb{S}^{d-1} . The Riemannian (spherical, tangent-space) gradient of f(e_{c})=e_{c}^{\top}v on the sphere is \nabla_{\mathbb{S}}f=v-(e_{c}^{\top}v)e_{c}=\Pi_{e_{c}}^{\perp}v , the projection of v onto the tangent space T_{e_{c}}\mathbb{S}^{d-1} ; this is distinct from the ambient Euclidean gradient and is the relevant gradient for any continuous evasion path constrained to \mathbb{S}^{d-1} . For any monotone transformation g , the chain rule gives \nabla(g\circ f)=g^{\prime}(f)\cdot\nabla f , which points in the same direction as \nabla f since g^{\prime}>0 . The converse (non-monotone \mathcal{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.3 Proof of Theorem 10 (detailed) Setup. The detector \hat{\pi}_{N} is calibrated by drawing N i.i.d. samples from the benign distribution P_{0}=\mathcal{N}(\mu_{0},\sigma^{2}) and producing an estimator \hat{\tau}_{N}(X_{1},\ldots,X_{N}) of the oracle threshold \tau^{*} . At inference time, a single test sample c is drawn from either P_{0} (benign) or P_{1}=\mathcal{N}(\mu_{1},\sigma^{2}) (adversarial) with \mu_{1}-\mu_{0}=\rho\sigma , and classified by \hat{\pi}_{N}(c)=\mathbf{1}[s(c)>\hat{\tau}_{N}] . Bayes error decomposition. Under the symmetric prior \mathbb{P}(H_{0})=\mathbb{P}(H_{1})=1/2 , the oracle threshold \tau^{*}=(\mu_{0}+\mu_{1})/2 achieves Bayes error B(\rho)=\Phi(-\rho/2) , where \Phi is the standard normal CDF. For any calibrated threshold \hat{\tau}_{N} , a first-order Taylor expansion of the Gaussian CDF around \tau^{*} gives \mathbb{P}_{\text{err}}(\hat{\pi}_{N})-B(\rho)=\tfrac{1}{2\sigma}\,\phi(\rho/2)\,|\hat{\tau}_{N}-\tau^{*}|+O\big((\hat{\tau}_{N}-\tau^{*})^{2}\big), (12) where \phi is the standard normal density. Hence excess error is linear in |\hat{\tau}_{N}-\tau^{*}| to leading order, and reducing the excess to \epsilon requires |\hat{\tau}_{N}-\tau^{*}|=O(\sigma\epsilon) . Lower bound via Le Cam (calibration formulation). The threshold-estimation problem is to estimate \tau^{*} from N benign samples X_{1},\ldots,X_{N}\sim P_{0}=\mathcal{N}(\mu_{0},\sigma^{2}) . Consider the two-point family \{\mu_{0},\mu_{0}+\Delta\} with \Delta=\sigma\rho/2 (so \tau^{*}\in\{\tau^{*}_{0},\tau^{*}_{0}+\Delta/2\} depending on which \mu_{0} is true). For product distributions P_{\mu_{0}}^{N} and P_{\mu_{0}+\Delta}^{N} , \mathrm{KL}(P_{\mu_{0}}^{N}\|P_{\mu_{0}+\Delta}^{N})=N\Delta^{2}/(2\sigma^{2})=N\rho^{2}/8. By Pinsker’s inequality, \mathrm{TV}(P_{\mu_{0}}^{N},P_{\mu_{0}+\Delta}^{N})\leq\sqrt{N\rho^{2}/16}=\rho\sqrt{N}/4 . Le Cam’s two-point inequality [ Le Cam 1973 ] then yields, for any estimator \hat{\tau}_{N} , \sup_{\mu\in\{\mu_{0},\mu_{0}+\Delta\}}\mathbb{E}_{\mu}\big[|\hat{\tau}_{N}-\tau^{*}(\mu)|\big]\;\geq\;\tfrac{\Delta}{4}\,\big(1-\mathrm{TV}\big)\;=\;\tfrac{\sigma\rho}{8}\,\big(1-\rho\sqrt{N}/4\big). For the bound to be non-trivial we require \rho\sqrt{N}<4 , i.e., N<16/\rho^{2} ; in that regime the right-hand side is \Omega(\sigma\rho) , which combined with ( 12 ) gives expected excess error \Omega(\rho) . To drive this excess to \epsilon , we therefore require N\geq c(\epsilon)/\rho^{2} for an absolute constant c(\epsilon)>0 depending only on the prior-symmetry and the target excess level. This is the lower bound stated in Theorem 10 . Distinction from a batch test. Le Cam can also be applied to the batch hypothesis test ( is the entire N -sample dataset drawn from P_{0} or P_{1} ? ), which yields the familiar \mathrm{KL}(P_{0}^{N}\|P_{1}^{N})=N\rho^{2}/2 and \rho\sqrt{N}/2 total-variation bound. That formulation is not the MEMSAD inference setting, in which a single test point c is classified after the calibration phase; we use the calibration formulation above instead. Tightness. Combining Theorem 11 ( |\hat{\tau}_{N}-\tau^{*}|=O(\sigma\sqrt{\log(1/\delta)/N}) ) with ( 12 ) gives expected excess error O(\sqrt{\log(1/\delta)/(N\rho^{2})}) . Setting this equal to \epsilon yields N=O(\log(1/\delta)/(\epsilon^{2}\rho^{2})) , matching the \Omega(1/\rho^{2}) lower bound up to logarithmic and \epsilon -dependent factors. The irreducible Bayes error B(\rho)=\Phi(-\rho/2) persists at any N and reflects intrinsic Gaussian overlap of P_{0} and P_{1} , not calibration error. B.4 Proof of Theorem 11 Mean concentration. The cosine similarity score s(c;\mathcal{H}) takes values in [-1,1] (interval length 2 ). Hoeffding’s inequality [ Wainwright 2019 ] on a bounded interval of length b-a=2 gives \mathbb{P}\!\left(|\hat{\mu}_{N}-\mu|\geq t\right)\;\leq\;2\exp\!\left(-\tfrac{2Nt^{2}}{(b-a)^{2}}\right)\;=\;2\exp\!\left(-\tfrac{Nt^{2}}{2}\right). Setting the right-hand side to \delta/2 yields |\hat{\mu}_{N}-\mu|\;\leq\;\sigma\sqrt{2\log(4/\delta)/N}\quad\text{w.p.}\;\geq 1-\delta/4, where the \sigma factor is recovered as a multiplicative constant absorbing the universal \sqrt{2} from the interval length 2 . 2 2 2 An empirical Bernstein bound [ Maurer and Pontil 2009 ] could replace the absolute Hoeffding range with the variance, yielding a tighter \sqrt{\sigma^{2}\log/N} rate; we state the worst-case bound here for simplicity. Variance concentration (two-sided). Let Z=(N-1)\hat{\sigma}_{N}^{2}/\sigma^{2}\sim\chi^{2}(N-1) (exactly for Gaussian scores; approximately for bounded scores via Berry-Esseen). Laurent–Massart [ Laurent and Massart 2000 ] Lemma 1 yields the two-sided bound \mathbb{P}\big[(1-2\sqrt{x/(N-1)})_{+}\,(N-1)\;\leq\;Z\;\leq\;(1+2\sqrt{x/(N-1)}+2x/(N-1))(N-1)\big]\;\geq\;1-2e^{-x}. Setting x=\log(4/\delta) and dividing by N-1 , with the substitution u=Z/(N-1)-1 so u\in[-c_{-},c_{+}] for c_{\pm}=O(\sqrt{\log(1/\delta)/N}) : |\hat{\sigma}_{N}-\sigma|\;=\;\sigma\,|\sqrt{1+u}-1|\;\leq\;\sigma\,\max(|c_{-}|,|c_{+}|)/2\cdot(1+o(1)) where the upper-tail bound uses \sqrt{1+u}-1\leq u/2 for u\geq 0 , and the lower-tail bound uses the corrected inequality |\sqrt{1+u}-1|\leq|u|/(2\sqrt{1+u})\leq|u|/\sqrt{2} for u\in[-1/2,0] (so \sqrt{1+u}\geq 1/\sqrt{2} ). Both tails together give |\hat{\sigma}_{N}-\sigma|\;\leq\;\sigma\sqrt{2\log(4/\delta)/(N-1)}\quad\text{w.p.}\;\geq 1-\delta/2, where we have absorbed the leading constants into a clean form valid for N\geq 4\log(4/\delta) (the regime in which |u|\leq 1/2 holds with high probability). Combination. By the triangle inequality |\tau_{N}-\tau^{*}|\leq|\hat{\mu}_{N}-\mu|+\kappa|\hat{\sigma}_{N}-\sigma| , and union bound over the two events at confidence 1-\delta/4 each yields total confidence 1-\delta/2 ; absorbing the additional \delta/2 tolerance for the variance lower-tail correction gives a final 1-\delta bound, exactly matching the theorem statement |\tau_{N}-\tau^{*}|\;\leq\;\sigma\!\left(\sqrt{\tfrac{1}{N}}+\kappa\sqrt{\tfrac{1}{2(N-1)}}\right)\sqrt{2\log(4/\delta)}. The factor \sqrt{2\log(4/\delta)} replaces the previously stated \sqrt{2\log(2/\delta)} to correctly reflect the four sub-events ( \hat{\mu} upper/lower, \hat{\sigma} upper/lower) controlled by the union bound. B.5 Proof of Theorem 12 Decompose: |\hat{\tau}_{t}-\tau_{t}^{*}|\leq\underbrace{|\hat{\tau}_{t}-\tau_{t}^{\mathcal{H}}|}_{\text{estimation}}+\underbrace{|\tau_{t}^{\mathcal{H}}-\tau_{t}^{*}|}_{\text{drift}} . Estimation error: O(\sigma(1+\kappa)/\sqrt{m_{\max}}) by Theorem 11 . Drift error: cosine similarity is 1-Lipschitz on \mathbb{S}^{d-1} , and the window mean averages over m_{\max} steps with linearly accumulating drift, so |\mu_{t}^{\mathcal{H}}-\mu_{t}|\leq m_{\max}\Delta/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: \sigma/\sqrt{m_{\max}}=m_{\max}\Delta gives m_{\max}^{*}=(\sigma/\Delta)^{2/3} (up to constants), yielding per-step regret O(\sigma^{2/3}\Delta^{1/3}) . B.6 Fisher-Rao detection-evasion metric Theorem 14 (Fisher-Rao detection-evasion metric) . Let \mathcal{E}=\{e\in\mathbb{S}^{d-1}\} under Assumption 5 (iii). The Fisher information metric induced by the score family p_{e}(s)=\mathcal{N}(s;\cosim(e,e_{q^{*}}),\hat{\sigma}^{2}) is g_{ij}^{F}(e)=\hat{\sigma}^{-2}\partial_{i}\mathcal{R}(e)\partial_{j}\mathcal{R}(e) . The geodesic distance to any undetected embedding satisfies d_{F}(e_{\text{adv}},e^{\prime})\geq|\mathcal{R}(e_{\text{adv}})-(\hat{\mu}+\kappa\hat{\sigma})|/\hat{\sigma} , and the Fisher-Rao cost of any continuous evasion path equals its retrieval degradation. Proof. Consider the parameterized family p_{e}(s)=\mathcal{N}(s;\mu(e),\hat{\sigma}^{2}) where \mu(e)=\cosim(e,e_{q^{*}}) and \hat{\sigma}^{2} is the calibrated variance. The Fisher information matrix on the statistical manifold \{p_{e}:e\in\mathcal{E}\} is: g_{ij}^{F}(e)=\mathbb{E}_{p_{e}}\!\left[\frac{\partial\log p_{e}}{\partial e_{i}}\frac{\partial\log p_{e}}{\partial e_{j}}\right]=\frac{1}{\hat{\sigma}^{2}}\frac{\partial\mu}{\partial e_{i}}\frac{\partial\mu}{\partial e_{j}}=\hat{\sigma}^{-2}\partial_{i}\mathcal{R}(e)\partial_{j}\mathcal{R}(e). (13) This is a rank-1 metric: g^{F}=\hat{\sigma}^{-2}\nabla\mathcal{R}\nabla\mathcal{R}^{\top} , the pullback of the scalar Fisher information I(\mu)=1/\hat{\sigma}^{2} through the map e\mapsto\mathcal{R}(e) . Geodesic lower bound. For any path \gamma:[0,1]\to\mathcal{E} from e_{\text{adv}}=\gamma(0) to e^{\prime}=\gamma(1) , the Fisher-Rao length is: L_{F}(\gamma)=\int_{0}^{1}\sqrt{\dot{\gamma}(t)^{\top}g^{F}(\gamma(t))\dot{\gamma}(t)}\,dt=\frac{1}{\hat{\sigma}}\int_{0}^{1}|\nabla\mathcal{R}(\gamma(t))^{\top}\dot{\gamma}(t)|\,dt\geq\frac{|\mathcal{R}(e_{\text{adv}})-\mathcal{R}(e^{\prime})|}{\hat{\sigma}}, (14) where the inequality follows from \int_{0}^{1}|f^{\prime}(t)|dt\geq|f(1)-f(0)| applied to f(t)=\mathcal{R}(\gamma(t)) . Detection-retrieval coupling. Since \mathcal{D}=g\circ\mathcal{R} with monotone g (Theorem 7 ), evasion requires \mathcal{D}(e^{\prime})\leq\hat{\mu}+\kappa\hat{\sigma} , which via monotonicity implies \mathcal{R}(e^{\prime})\leq g^{-1}(\hat{\mu}+\kappa\hat{\sigma}) . Substituting into the geodesic bound: d_{F}(e_{\text{adv}},e^{\prime})\geq\frac{\mathcal{R}(e_{\text{adv}})-g^{-1}(\hat{\mu}+\kappa\hat{\sigma})}{\hat{\sigma}}=\frac{|\mathcal{R}(e_{\text{adv}})-(\hat{\mu}+\kappa\hat{\sigma})|}{\hat{\sigma}}, (15) where the last equality uses g=\text{id} (since \mathcal{D} is the cosine similarity score and \mathcal{R} coincides with \mathcal{D} under Assumption 5 ). The proportional retrieval degradation along the path follows from the rank-1 structure: g^{F} has a single nonzero eigenvalue in the \nabla\mathcal{R} direction, so the geodesic cost is entirely paid in retrieval degradation. ∎ B.7 Proof of Proposition 15 (detailed) Proposition 15 (Hardness of optimal discrete-token evasion) . The discrete-token minimum-edit evasion problem is NP-hard for piecewise-linear encoders, via reduction from CVP [ Micciancio and Goldwasser 2002 ] . The continuous-embedding relaxation is, by contrast, solvable in polynomial time within any fixed activation region; the hardness arises specifically from the integrality (token-index) constraints in the input vocabulary. Why the discrete formulation is the relevant hard problem. The continuous problem of finding the minimum-norm embedding-space perturbation \delta\in\mathbb{R}^{d} subject to a cosine-similarity constraint on e_{c}+\delta is a continuous convex optimization within any fixed ReLU activation region: the constraint set is a convex polytope, and within each polytope the objective is quadratic. A polynomial-time algorithm enumerates regions or solves a single SOCP under a fixed activation pattern. We do not claim hardness for this relaxation. The deployed adversary, however, must produce a token sequence c\in\mathcal{V}^{*} whose embedding satisfies the constraint, and the embedding is tied to the token sequence via the integer indices selected from the vocabulary \mathcal{V} . We formalize this discrete-token problem and show its NP-hardness below. Discrete-token evasion problem. Fix a piecewise-linear encoder E:\mathcal{V}^{*}\to\mathbb{R}^{d} (e.g., one-hot lookup followed by a ReLU network), a victim query embedding E(q^{*}) , a retrieval threshold \tau_{\text{ret}} , and a detection threshold \tau_{\text{det}}=\hat{\mu}+\kappa\hat{\sigma} . Given an initial passage c_{0}\in\mathcal{V}^{*} and an edit budget r\in\mathbb{N} , decide whether there exists c\in\mathcal{V}^{*} with token-edit distance d_{T}(c_{0},c)\leq r such that \cosim(E(c),E(q^{*}))\in[\tau_{\text{ret}},\tau_{\text{det}}] . Reduction from CVP. Given a CVP instance (\Lambda,t) where \Lambda=B\mathbb{Z}^{n} is a lattice with basis B\in\mathbb{R}^{n\times n} and target t\in\mathbb{R}^{n} , construct an instance of the discrete-token evasion problem as follows. Let \mathcal{V}=\{v_{1},\ldots,v_{n}\} have |\mathcal{V}|=n , and let the input embedding lookup map v_{i}\mapsto b_{i} where b_{i} is the i -th column of B . Take the encoder E(c)=\mathrm{ReLU}(\sum_{i:v_{i}\in c}b_{i}) , which under the all-active region computes E(c)=\sum_{i\in I(c)}b_{i}=B\mathbf{1}_{I(c)} where I(c) is the index set of tokens in c . The adversary’s discrete choice of c is therefore equivalent to selecting \lambda\in\{0,1\}^{n}\subset\mathbb{Z}^{n} , and the constraint \cosim(B\lambda,t/\|t\|)\geq\tau_{\text{ret}} instantiates exactly the minimum-distance lattice problem in \Lambda restricted to 0/1 coefficients. The integrality constraint \lambda\in\mathbb{Z}^{n} is enforced by the discrete vocabulary, which is what continuous embedding-space optimization lacks. Hence the discrete-token evasion problem subsumes CVP and is NP-hard under randomized reductions [ Micciancio and Goldwasser 2002 ] . ∎ Practical implication. The continuous-embedding evasion is poly-time within any activation region (PAT-flagged correctly): an adversary with white-box continuous access to the embedding could compute the minimum-norm direction in poly-time and would be defeated only by gradient coupling (Theorem 7 ). The genuine hardness, captured by Proposition 15 , lies in projecting that continuous direction back onto the integer-valued token grid — exactly the discrete bottleneck the synonym-loophole adversary (Proposition 13 ) exploits in the opposite direction. Together: gradient coupling closes the continuous attack surface, the discrete reduction closes the unconstrained-token attack surface, and the synonym loophole identifies the residual gap. B.8 Detection-evasion tradeoff surface Assumption 16 (Aligned mean gradient) . The mean-similarity gradient is not adversarial to the max-similarity gradient, in the sense \langle\nabla s_{\text{mean}},\nabla s_{\max}\rangle\geq-\beta\|\nabla s_{\max}\|^{2} for some \beta\in[0,\alpha/(1-\alpha)) at all points of differentiability of s_{\text{comb}} . Corollary 17 (Combined scoring preserves directional coupling) . Under Assumption 16 , the combined score s_{\text{comb}}=\alpha\,s_{\max}+(1-\alpha)\,s_{\text{mean}} with \alpha\in(0,1) satisfies directional monotonicity: any continuous perturbation \delta that strictly decreases s_{\text{comb}} also strictly decreases \mathcal{R}=s_{\max} . Consequently, Lemma 8 and Theorem 14 apply with a multiplicative constant degradation reflecting the worst-case alignment \beta . Proof. \nabla s_{\text{comb}}=\alpha\nabla s_{\max}+(1-\alpha)\nabla s_{\text{mean}} . The projection onto the max-direction is \langle\nabla s_{\text{comb}},\nabla s_{\max}\rangle=\alpha\|\nabla s_{\max}\|^{2}+(1-\alpha)\langle\nabla s_{\text{mean}},\nabla s_{\max}\rangle\geq(\alpha-(1-\alpha)\beta)\|\nabla s_{\max}\|^{2}. Under Assumption 16 , \alpha-(1-\alpha)\beta>0 , so \langle\nabla s_{\text{comb}},\nabla s_{\max}\rangle has the same sign as \|\nabla s_{\max}\|^{2}>0 , and any \delta with \langle\delta,\nabla s_{\text{comb}}\rangle<0 must satisfy \langle\delta,\nabla s_{\max}\rangle<0 . The empirical bound from our experiments (Section 6 ) gives \beta\leq 0.4 across all 6 encoders evaluated, well within the constraint \beta<\alpha/(1-\alpha)=1 at \alpha=0.5 . ∎ By Theorem 7 , \mathcal{D}(e_{c}^{\prime})<\mathcal{D}(e_{c}) (evasion) implies \mathcal{R}(e_{c}^{\prime})<\mathcal{R}(e_{c}) (retrieval degradation) to first order. The tradeoff defines a surface in (\epsilon,\theta,\Delta\mathcal{D}) space where \theta is the angle between perturbation \delta and gradient \nabla\mathcal{D} . Expanding to second order: \mathcal{D}(e_{c}+\epsilon\delta)-\mathcal{D}(e_{c})=\epsilon\|\nabla\mathcal{D}\|\cos\theta+\frac{\epsilon^{2}}{2}\delta^{\top}H_{\mathcal{D}}\,\delta+O(\epsilon^{3}), (16) where H_{\mathcal{D}} is the Hessian of the cosine similarity on the sphere. Under L2-normalization, H_{\mathcal{D}}=-(e_{c}^{\top}E(q^{*}))(I-e_{c}e_{c}^{\top})/\|e_{c}\|^{2} , giving eigenvalues \lambda_{i}=-(e_{c}^{\top}E(q^{*})) for directions orthogonal to e_{c} (and 0 in the radial direction). The evasion region \mathcal{D}(e_{c}^{\prime})<\mathcal{D}(e_{c}) requires \cos\theta<-\epsilon\|H_{\mathcal{D}}\|/(2\|\nabla\mathcal{D}\|) , which contracts as \epsilon\to 0 , confirming the infinitesimal impossibility of evasion without retrieval degradation (Figure 4 ). perturbation \epsilon \Delta\mathcal{R} \mathcal{R}(e_{c}^{\prime}) \mathcal{D}(e_{c}^{\prime}) \hat{\mu}{+}\kappa\hat{\sigma} synonym (discrete) detection margin \nabla\mathcal{D}\equiv\nabla\mathcal{R} (Thm. 7 ) continuous curves overlap exactly Figure 4 : Detection-evasion tradeoff. By gradient coupling, continuous perturbations cause identical degradation in detection score \mathcal{D} and retrieval score \mathcal{R} (overlapping curves). Synonym substitutions (orange) bypass this coupling via discrete jumps in token space (Proposition 13 ). B.9 Generalization bound Theorem 18 (Generalization bound) . Suppose the novel-attack score density f_{\text{new}} and the calibration score density f_{j} are both bounded by g_{\max} . Then for W_{1}(P_{\text{new}},P_{j})\leq\epsilon_{W} , |\text{TPR}_{\text{new}}-\text{TPR}_{j}|\;\leq\;\sqrt{2\,g_{\max}\,\epsilon_{W}}+O(N^{-1/2}). For Gaussian scores with std \sigma , g_{\max}=(\sigma\sqrt{2\pi})^{-1} , giving |\text{TPR}_{\text{new}}-\text{TPR}_{j}|\leq\sqrt{\epsilon_{W}/(\sigma\sqrt{\pi/2})}+O(N^{-1/2}) . Remark 19 (Practical estimation of \epsilon_{W} ) . In practice, \epsilon_{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 F_{j} and F_{\text{new}} denote the CDFs of scores s(c;\mathcal{H}) under P_{j} and P_{\text{new}} , respectively. The TPR at threshold \tau is \text{TPR}(\tau)=1-F(\tau) . Wasserstein-to-Kolmogorov bound. The 1-Wasserstein distance is the integral of pointwise CDF difference: W_{1}(F_{j},F_{\text{new}})\;=\;\int_{-\infty}^{\infty}|F_{j}(s)-F_{\text{new}}(s)|\,ds. (17) This is an L^{1} norm on the CDF gap and does not linearly upper-bound the L^{\infty} (pointwise sup) gap. The correct relationship under a uniform density bound is the standard L^{1} -to- L^{\infty} trade for absolutely continuous distributions: if |f_{j}|,|f_{\text{new}}|\leq g_{\max} , then for any \tau and any h>0 , |F_{j}(\tau)-F_{\text{new}}(\tau)|\;\leq\;\frac{1}{2h}\!\int_{\tau-h}^{\tau+h}\!|F_{j}(s)-F_{\text{new}}(s)|\,ds+g_{\max}h\;\leq\;\frac{W_{1}}{2h}+g_{\max}h, where the first inequality applies because |F_{j}(\tau)-F_{j}(s)|\leq g_{\max}|s-\tau| and likewise for F_{\text{new}} , and the second uses non-negativity of the integrand. Optimising over h>0 at h=\sqrt{W_{1}/(2g_{\max})} gives |F_{j}(\tau)-F_{\text{new}}(\tau)|\;\leq\;\sqrt{2\,g_{\max}\,W_{1}}. Since |\text{TPR}_{j}-\text{TPR}_{\text{new}}|=|F_{j}(\tau)-F_{\text{new}}(\tau)| , the stated bound follows. The \sqrt{\cdot} scaling is sharp: a localized mass shift of m across the threshold over distance h\to 0 has W_{1}=mh\to 0 but |F-G|_{\infty}\to m , and only the bounded-density assumption rules this out at the rate \sqrt{W_{1}} . Threshold estimation. By Theorem 11 , |\hat{\tau}-\tau^{*}|\leq\eta_{N} w.p. \geq 1-\delta , contributing an additional O(1/\sqrt{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 contributing an independent O(\sigma/\sqrt{m_{\max}}) estimation error and accumulating O(m_{\max}\Delta) drift. B.10 Online regret bound visualization Figure 5 illustrates the bias-variance tradeoff in Theorem 12 as a function of window size m_{\max} . m_{\max} per-step regret \sigma/\sqrt{m} m\Delta total m^{*} O(\sigma^{2/3}\Delta^{1/3}) estimation (Thm. 11 ) drift (non-stationarity) Figure 5 : Online calibration regret decomposition (Theorem 12 ). Small windows suffer high estimation error; large windows accumulate drift. The optimal m^{*}=\Theta((\sigma/\Delta)^{2/3}) balances both. B.11 Stackelberg equilibrium existence Proposition 20 (Equilibrium existence) . The Stackelberg game \mathcal{G} (Definition 3 ) admits a subgame-perfect equilibrium (\pi_{\mathcal{D}}^{*},\mathcal{P}^{*}) when \Pi is restricted to threshold detectors with \kappa\in[\kappa_{\min},\kappa_{\max}] . Proof. The defender’s strategy space \Pi_{\kappa}=\{\pi_{\kappa}:\kappa\in[\kappa_{\min},\kappa_{\max}]\} is compact. For fixed \pi_{\kappa} , the adversary’s best-response set \mathcal{B}(\pi_{\kappa})=\argmax_{\mathcal{P}}\text{ASR-R}(\mathcal{P}\setminus\{p:s(p;\mathcal{H})>\hat{\mu}+\kappa\hat{\sigma}\},\mathcal{Q}_{v}) is nonempty (the empty set is always feasible) and upper hemicontinuous in \kappa since s(p;\mathcal{H}) is continuous and the threshold \hat{\mu}+\kappa\hat{\sigma} is linear in \kappa . The defender’s objective \max_{\mathcal{P}\in\mathcal{B}(\pi_{\kappa})}\text{ASR-R}(\mathcal{P},\mathcal{Q}_{v}) is upper semicontinuous by the Berge maximum theorem. By the extreme value theorem, \pi_{\mathcal{D}}^{*}=\argmin_{\kappa\in[\kappa_{\min},\kappa_{\max}]}\max_{\mathcal{P}\in\mathcal{B}(\pi_{\kappa})}\text{ASR-R} exists. ∎ In practice, the composite portfolio (\pi_{\text{wm}}\lor\pi_{\text{SAD}}\lor\pi_{\text{pro}}) achieves \text{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.12 Finite-sample FPR concentration Proposition 21 (FPR concentration) . Let c_{1},\ldots,c_{n} be n i.i.d. benign candidates evaluated against a threshold \hat{\tau}_{N} calibrated from N separate i.i.d. benign samples. Let \widehat{\text{FPR}}_{n}=n^{-1}\sum_{i=1}^{n}\mathbf{1}[s_{i}>\hat{\tau}_{N}] and let \text{FPR}^{*} be the population FPR at the oracle threshold \tau^{*} . Then \mathbb{P}\!\left[|\widehat{\text{FPR}}_{n}-\text{FPR}^{*}|>\epsilon\right]\;\leq\;\underbrace{2\exp\!\left(-\frac{n\epsilon^{2}/2}{\text{FPR}^{*}(1-\text{FPR}^{*})+\epsilon/3}\right)}_{\text{empirical FPR concentration (Bernstein)}}+\underbrace{2\exp\!\left(-\frac{N\epsilon^{2}}{8}\right)}_{\text{threshold-estimation error}}. (18) The first term is Bernstein’s inequality with the standard \epsilon/3 range correction (the previous omission of this term renders the bound vacuous when \text{FPR}^{*}=0 , the regime of interest); the second tracks the calibration error, with the correct denominator being the calibration size N , not the test-set size n , since the threshold is fixed once calibration ends. For \kappa=2.0 , N=200 , n=1{,}000 , \text{FPR}^{*}=0 : with \epsilon=0.01 the first term reduces to 2e^{-1.5}\approx 0.45 (loose because \text{FPR}^{*}=0 ); the binomial-exact Clopper-Pearson CI [0.000,0.004] (Table 12 ) is the tighter bound used in practice and is the only one we report empirically. The second term gives 2e^{-0.25}\approx 1.6 , dominated by the calibration confidence already enforced via Theorem 11 . Appendix C Additional defense details Watermark. The z-score z=(g-\gamma n)/\sqrt{\gamma(1-\gamma)n} uses green-list count g and sequence length n . Character-level: 95 ASCII chars, \gamma=0.45 . Token-level (GPT-2, 50,257 tokens): p_{\text{green}}\approx 0.711 , mean z\approx 7.5 at n=50 . Proactive. 16 probe queries span 8 subtopics. Threshold \tau=0.19 minimizes FPR while maintaining \geq 0.50 TPR on centroid passages. Composite defense. Definitive specification (resolves an inconsistency in earlier drafts). The composite defense deployed in all experiments is the logical disjunction \pi_{\text{comp}}(c)\;=\;\pi_{\text{wm}}(c)\;\lor\;\pi_{\text{SAD}}(c)\;\lor\;\pi_{\text{pro}}(c), i.e., an entry is rejected if any of the watermark, MEMSAD, or proactive defenses flags it. The four-way breakdown (watermark, validation, proactive, MEMSAD) used as input to ablation tables refers to this same disjunction with one term ablated at a time. The weighted-sum form 0.50d_{\text{wm}}(c)+0.20d_{\text{val}}(c)+0.30d_{\text{pro}}(c)>0.50 that appeared in some earlier exposition was an alternative tunable formulation we evaluated but is not the composite reported in Tables 3 and 11 ; we deprecate it here. Under the disjunctive composite, the perfect \text{TPR}=1.00 against MINJA reported in Table 3 arises from MEMSAD detection (since MINJA bypasses watermarking via auto-storage), consistent with the per-defense breakdown. The disjunction was chosen over the weighted sum because (i) it satisfies the assumption used in the equilibrium proof (Proposition 20 ) and (ii) its FPR is the union of per-defense FPRs, which are all \leq 0.01 at the calibrated thresholds and remain \leq 0.04 in aggregate. Evaluation correction. Prior work evaluated AgentPoison with plain queries q ; the paper’s Algorithm 2 specifies triggered queries q\oplus T^{*} , changing \cosim from \approx 0.45 to \sim 0.78 . Appendix D Ablation studies Table 5: MemSAD threshold sensitivity with combined scoring ( |\mathcal{M}|=200 ; see Table 3 for |\mathcal{M}|=1{,}000 results). TPR FPR \kappa AP MJ IM AP MJ IM 1.0 1.00 † 1.00 0.80 0.10 0.10 0.10 1.5 1.00 † 1.00 0.60 0.00 0.05 0.05 2.0 1.00 † 1.00 0.40 0.00 0.00 0.00 2.5 1.00 † 1.00 0.20 0.00 0.00 0.00 3.0 0.80 † 0.80 0.00 0.00 0.00 0.00 † Triggered calibration. Plain: TPR =0.00 for all \kappa . Table 6: Corpus size ablation: ASR-R across |\mathcal{M}| (triggered for AP). |\mathcal{M}| AgentPoison MINJA InjecMEM 50 1.00 0.70 0.65 100 1.00 0.65 0.55 200 1.00 0.65 0.50 300 1.00 0.60 0.40 500 1.00 0.60 0.30 1000 1.00 0.14 0.07 AgentPoison uses triggered protocol; |\mathcal{M}|=1{,}000 row matches main evaluation (Table 2 ). Table 7: Poison count ablation: ASR-R vs. n_{\text{base}} . n_{\text{base}} AgentPoison MINJA InjecMEM 1 0.80 0.20 0.10 3 1.00 0.45 0.30 5 1.00 0.65 0.50 7 1.00 0.70 0.55 10 1.00 0.75 0.60 Table 8: Calibration set size ablation: |\tau_{N}-\tau^{*}| vs. N (theoretical bound from Theorem 11 vs. observed, \delta=0.05 , MINJA ). N (calibration size) Bound (Thm. 11 ) Observed 25 0.061 0.038 50 0.044 0.027 100 0.031 0.019 200 0.022 0.014 500 0.014 0.009 Bound is tight to within \approx 1.6\times ; N=50 (main evaluation) gives |\tau_{N}-\tau^{*}|\leq 0.044 . Appendix E Multi-encoder evaluation Table 9: Encoder generalization: MemSAD across 6 encoders at |\mathcal{M}|=1{,}000 ( \kappa=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 \kappa ). TPR here measures detection over 5 poison passages per attack; main Table 3 uses n=10 MINJA / n=15 InjecMEM entries (different poison set, same encoder, same \kappa ). TPR AUROC Encoder AP MJ IM AP MJ IM MiniLM-L6 ( d{=}384 ) 1.00 0.80 0.40 1.000 0.914 0.816 MPNet-Base ( d{=}768 ) 1.00 1.00 0.40 1.000 0.940 0.886 Para-MiniLM ( d{=}384 ) 1.00 1.00 0.00 0.998 0.957 0.645 E5-Base ( d{=}768 ) 1.00 1.00 1.00 0.997 0.978 0.946 Contriever ( d{=}768 ) 1.00 1.00 0.40 0.926 0.922 0.759 BGE-Large ( d{=}1024 ) 1.00 1.00 0.80 0.953 0.966 0.928 Figure 6 : Encoder generalization: MemSAD TPR (top) and FPR (bottom) across 6 encoders at \kappa=2.0 . Triggered AgentPoison achieves TPR = 1.00 on all encoders; InjecMEM is more encoder-sensitive (TPR 0.00–1.00). Key findings at |\mathcal{M}|=1{,}000 (Figure 6 ): (1) Triggered calibration achieves \text{TPR}=1.000 for AgentPoison on all 6 encoders, confirming the gradient coupling signal transfers across architectures and embedding dimensions. (2) MINJA detection is robust ( \text{TPR}\geq 0.80 , AUROC \geq 0.914 ) across all encoders. (3) InjecMEM is more encoder-sensitive: E5-Base achieves \text{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 \text{TPR}=1.00/1.00/0.80 for AP/MJ/IM, AUROC \geq 0.928 across attacks; its higher FPR (0.09–0.14 at \kappa=2.0 ) reflects a broader embedding distribution that slightly overlaps the anomaly boundary—raising \kappa to 2.5 eliminates the false positives at the cost of \text{TPR}_{\text{IM}}=0.60 . Appendix F Graph memory attacks Definition 22 (Graph memory system) . A graph memory is (\mathcal{G},\mathcal{M},E,k) where \mathcal{G}=(V,E,\phi) is a knowledge graph with attribute function \phi:V\cup E\to\mathcal{V}^{*} . Retrieval combines embedding similarity with BFS traversal: \Ret_{\mathcal{G}}(q,k,h)=\{v\in V:d_{\mathcal{G}}(v,v^{*})\leq h,\;v^{*}\in\argmax_{v^{\prime}}\cosim(E(q),E(\phi(v^{\prime})))\} . 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 z_{\deg}(v)>\kappa_{\deg} ; adjacency contamination scoring detects edge-hijack via the fraction of recently added edges. Appendix G Multi-agent propagation Definition 23 (SIR propagation) . For N agents sharing \mathcal{M}_{\text{shared}} , the discrete-step SIR model [ Kermack and McKendrick 1927 , Gu et al. 2024 ] evolves: S(t{+}1)=S(t)-\beta S(t)I(t)/N , I(t{+}1)=I(t)+\beta S(t)I(t)/N-\gamma I(t) , R(t{+}1)=R(t)+\gamma I(t) , where \beta is transmission rate and \gamma recovery rate. For the classical SIR model with no re-introduction, the active-infection fraction I(t)/N asymptotically decays to zero, \lim_{t\to\infty}I(t)/N=0 , since infected agents recover (or are quarantined) and acquire immunity. The relevant epidemic statistic is therefore the final-size proportion (fraction of agents ever infected before recovery), which solves the implicit equation 1-R_{\infty}/N=e^{-(\beta/\gamma)R_{\infty}/N} for \beta>\gamma . With MemSAD quarantine ( \text{TPR}=1.00 for MINJA ), \gamma_{\text{eff}}=\gamma+\text{TPR}\cdot\beta ; the basic reproduction number \mathcal{R}_{0}=\beta/\gamma_{\text{eff}} drops below 1, eliminating secondary infection. Erratum: the formula I_{\infty}/N=1-\gamma/\beta that appeared in earlier exposition is the SIS endemic equilibrium, not the SIR final size; the SIR-correct expression above is what governs the simulations reported in Table 10 . Empirical simulation We instantiate the SIR model with N=20 agents, p_{\text{re-store}}=0.30 , T=30 steps, 5 initial MINJA -style 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) MemSAD with triggered calibration ( \kappa=2.0 , combined scoring); (iii) composite defense approximated by \kappa=1.0 . Figure 7 : Multi-agent SIR propagation (mean \pm 1\sigma over 5 seeds; here \sigma refers to the seed-distribution standard deviation, not the calibration std). Top : fraction of agents exposed over 30 steps. Bottom : secondary poison entry growth. Composite ( \kappa=1.0 ) prevents spread entirely; MemSAD ( \kappa=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 10: Multi-agent SIR propagation results ( N=20 , p_{\text{re-store}}=0.30 , T=30 , 5 initial poison entries). Averaged over 5 independent seeds; timing columns show mean steps. Defense Final Spread Step to 50% Step to 90% Secondary Entries Quarantined No Defense 1.00 5 14 23 — MemSAD ( \kappa=2.0 ) 1.00 5 14 18 5 Composite ( \kappa=1.0 ) 0.00 > 30 > 30 0 2 Figure 7 and Table 10 summarize the results. The tighter composite threshold ( \kappa=1.0 ) quarantines 2 of 5 initial entries and all secondary entries, holding spread to zero. MemSAD at \kappa=2.0 quarantines \approx 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 ( t_{90\%}=14 steps in both conditions); MemSAD ’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. Appendix H Statistical hypothesis tests Table 11: One-sided binomial hypothesis tests ( H_{0} : \text{TPR}\leq 0.05 , the chance-level baseline; Bonferroni \alpha^{\prime}=0.003 across 15 comparisons). The previously reported null H_{0}:\text{TPR}=0 rendered the p -values mathematically impossible whenever an empirical positive was observed; we restate the test under the chance-baseline null, which is the comparison statisticians use in practice for OOD-style detection. Defense Attack p -value Reject? Power Watermark AP / MJ <10^{-6} ✓ 1.00 MemSAD MJ <10^{-6} ✓ 1.00 MemSAD IM 0.001 ✓ 0.92 Proactive AP <10^{-6} ✓ 1.00 Proactive MJ 0.24 — 0.08 Composite All <10^{-6} ✓ 1.00 Appendix I FPR validation Table 12: FPR validation: Clopper-Pearson 95% CIs, 20 trials. Defense FPR 95% CI n /trial MemSAD ( \kappa=2.0 ) 0.000 [0.000,0.004] 1000 Watermark ( z_{\text{thr}}=1.5 ) 0.000 [0.000,0.004] 1000 Proactive ( \tau=0.19 ) 0.010 [0.004,0.023] 1000 Appendix J MemSAD detection analysis Figure 8 visualizes MemSAD ’s ROC characteristics and calibration shift. (a) ROC as \kappa varies from 0.5 to 4.0. (b) Plain vs. triggered calibration. Figure 8 : MemSAD detection. (Top) MINJA traces near-ideal ROC; triggered calibration recovers \text{TPR}=1.00 for AgentPoison at \kappa=2.0 ( \star ). (Bottom) Threshold shifts from 0.473 (plain) to 0.436 (triggered) at \kappa=2.0 , |\mathcal{M}|=200 ; the values 0.482 / 0.432 quoted in earlier exposition correspond to the |\mathcal{M}|=1{,}000 regime with a slightly different running-mean window and are reported in Section 6 . Appendix K Sample complexity comparison Table 13 compares the calibration sample requirements across detection approaches, derived from Theorem 10 and Theorem 11 . Table 13: Sample complexity for reliable detection ( \text{FPR}+(1-\text{TPR})\leq 0.05 ) across calibration regimes. Setting \rho (SNR) ‡ Lower bound N_{\min} MemSAD N MINJA (plain) 1.93 1 1\cdot\log(1/\delta) AgentPoison (triggered) \geq 4.0 1 1\cdot\log(1/\delta) AgentPoison (plain) 1.59 2 2\cdot\log(1/\delta) InjecMEM (plain) 1.27 3 3\cdot\log(1/\delta) Low-SNR adversary 0.50 15 15\cdot\log(1/\delta) N_{\min}=\lceil 4(1-\epsilon)^{2}/\rho^{2}\rceil from Theorem 10 ; MemSAD N from Theorem 11 . ‡ SNR estimated from AUROC via \rho=\sqrt{2}\,\Phi^{-1}(\text{AUROC}) ; low-SNR row is hypothetical. Practical calibration uses N=50 for additional margin. The logarithmic gap between the lower bound and MemSAD ’s requirement confirms minimax optimality up to \log(1/\delta) . For practical deployment at \delta=0.05 : \log(1/\delta)\approx 3.0 , so MemSAD requires \sim 3\times the information-theoretic minimum. The main evaluation uses N=50 , well above the theoretical minimum for all observed SNR regimes, providing conservative guarantees. Appendix L Computational complexity Table 14: Per-entry defense cost at write time. Defense Time Space Measured MemSAD (exact) O(md) O(md) 0.8ms MemSAD (ANN) O(d\log m) O(md) 0.3ms Watermark O(|c|\cdot|\mathcal{V}|) O(|\mathcal{V}|) 1.2ms Validation O(|c|\cdot|P|) O(|P|) 0.1ms Proactive O(|Q_{p}|d) O(|Q_{p}|d) 0.5ms Composite \max_{j}O(d_{j}) \sum_{j}O(s_{j}) 2.1ms Apple M-series, 16GB; |\mathcal{M}|=200 , m=20 , d=384 . Appendix M Distributional robustness analysis We extend MemSAD ’s guarantees to the distributionally robust setting where the adversary can perturb the score distribution within a Wasserstein ball. Proposition 24 (Distributionally robust detection) . Suppose the score density under P_{1} and any Q in the perturbation class \mathcal{U}=\{Q:W_{1}(Q,P_{1})\leq\epsilon\} is bounded by g_{\max} . Then \inf_{Q\in\mathcal{U}}\text{TPR}(\tau;Q)\;\geq\;\text{TPR}(\tau;P_{1})-\sqrt{2g_{\max}\,\epsilon}. (19) For Gaussian scores with std \sigma , g_{\max}=(\sigma\sqrt{2\pi})^{-1} , giving the closed-form bound \sqrt{\epsilon/(\sigma\sqrt{\pi/2})} . Proof. Apply the bounded-density Wasserstein-to-Kolmogorov inequality from Theorem 18 : under |f_{P_{1}}|,|f_{Q}|\leq g_{\max} and W_{1}(Q,P_{1})\leq\epsilon , |F_{P_{1}}(\tau)-F_{Q}(\tau)|\leq\sqrt{2g_{\max}\,\epsilon} for every \tau . Since |\text{TPR}(\tau;P_{1})-\text{TPR}(\tau;Q)|=|F_{P_{1}}(\tau)-F_{Q}(\tau)| , the bound follows. ∎ This guarantees that even if the adversary slightly perturbs their attack strategy (e.g., via randomized synonym selection), MemSAD ’s TPR degrades gracefully under the bounded-density assumption. For \epsilon=0.01\hat{\sigma} and Gaussian scores ( g_{\max}=(\hat{\sigma}\sqrt{2\pi})^{-1} ): \Delta\text{TPR}\leq\sqrt{0.01/\sqrt{\pi/2}}\approx 0.10 , an order of magnitude looser than the (incorrect) linear bound previously stated; this matches the empirical scale observed in Table 4 . Proposition 25 (PAC-style FPR guarantee) . For N i.i.d. calibration samples from P_{0} , with probability \geq 1-\delta over the calibration set, MemSAD ’s threshold \hat{\tau}_{N} satisfies the FPR-side bound \big|\text{FPR}(\hat{\tau}_{N})-\text{FPR}(\tau^{*})\big|\;\leq\;\sqrt{\frac{\log(2/\delta)}{2N}}, (20) where \tau^{*}=\mu_{0}+\kappa\sigma_{0} is the population-optimal threshold computed under the benign distribution. The TPR side requires the additional Wasserstein assumption of Theorem 18 . Proof. The DKW inequality [ Dvoretzky et al. 1956 , Massart 1990 ] bounds the uniform deviation of the empirical CDF from the true CDF for a sample drawn from a single distribution: \sup_{t}|\widehat{F}_{0,N}(t)-F_{0}(t)|\leq\sqrt{\log(2/\delta)/(2N)} w.p. \geq 1-\delta . Since \text{FPR}(\tau)=1-F_{0}(\tau) and the calibration sample is drawn from P_{0} , applying DKW at t=\hat{\tau}_{N} yields |\widehat{F}_{0,N}(\hat{\tau}_{N})-F_{0}(\hat{\tau}_{N})| within the stated tolerance, and |F_{0}(\hat{\tau}_{N})-F_{0}(\tau^{*})| is bounded via the score-density Lipschitz argument (Theorem 11 ). The TPR side does not follow from DKW alone because \text{TPR}(\tau)=1-F_{1}(\tau) depends on the adversarial distribution P_{1} , for which we have no calibration samples; use Theorem 18 ’s \sqrt{W_{1}} bound instead. ∎ Proposition 26 (TPR robustness via Wasserstein) . Under the bounded-density assumption of Theorem 18 and assuming W_{1}(\widehat{P}_{1,n_{1}},P_{1})\leq\epsilon_{W} for an empirical adversarial estimate from n_{1} poisoned samples, \big|\text{TPR}(\hat{\tau}_{N})-\text{TPR}(\tau^{*})\big|\;\leq\;\sqrt{2g_{\max}\,\epsilon_{W}}\;+\;O(N^{-1/2}). At N=200 , \delta=0.05 : the FPR-side bound is \leq 0.096 , meaning MemSAD ’s empirical FPR of 0.000 implies true FPR \leq 0.096 with 95% confidence. The Clopper-Pearson validation (Table 12 ) provides a tighter bound of 0.004 by exploiting the binomial structure. Appendix N Comparison with concurrent post-retrieval defenses A-MemGuard [ Li et al. 2025 ] is the closest contemporary defense for LLM-agent memory; we situate it relative to MemSAD along three axes. (i) Stage: A-MemGuard operates post-retrieval via consensus checking on the retrieved entries, whereas MemSAD operates at write time before any entry is committed — the latter prevents the entry from existing in memory at all, removing the persistent attack surface. (ii) Guarantees: A-MemGuard’s evaluation is empirical (no formal bounds reported in the public preprint); MemSAD provides the gradient-coupling theorem, certified detection radius, and calibration sample-complexity lower bound (Theorems 7 , 10 ; Lemma 8 ). (iii) Latency: write-time filtering pays \sim 2 ms per ingestion event but removes per-query overhead at retrieval; post-retrieval consensus pays a recurring per-query cost that scales with k (top- k retrieved entries). The two are architecturally complementary: a deployment combining MemSAD ingestion with A-MemGuard’s read-time consensus would harden both surfaces. We do not benchmark against A-MemGuard directly because its public implementation was unavailable at the time of submission; this is a stated limitation, and a comparison run with a faithful re-implementation is the cleanest extension for a future revision. Appendix O OOD detection baseline comparison We compare MemSAD 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 post-retrieval (read-time), not at write-time, and the others lack public implementations as of submission. Baselines: Energy Score [ Liu et al. 2020 ] ( \text{score}=-T\log\sum_{i}\exp(\cosim(e,q_{i})/T) ), Mahalanobis distance [ Lee et al. 2018 ] in embedding space, and KNN distance ( k=10 ) to the benign calibration set. Energy Score polarity. The closed-form Energy Score above is decreasing in the maximum cosine similarity to calibration queries: poisoned candidates with high similarity to victim queries produce more-negative Energy Scores. The standard OOD convention treats higher scores as more-anomalous; we therefore evaluate the inverted statistic -\text{score} for the threshold rule (anomaly \Leftrightarrow -\text{score}>\tau ) so that the AUROCs reported in Table 15 are correctly oriented. We had previously stated this convention only implicitly via the AUROC values; the explicit polarity inversion is now spelt out for reproducibility. Table 15: OOD detection baseline comparison at |\mathcal{M}|=1{,}000 . All methods are calibrated on the same triggered-query regime for AgentPoison (the trigger-aware setting that all query-aware methods assume in deployment); a parallel comparison under standard (untriggered) calibration is reported in Table 16 . AUROC is the primary metric; TPR (at threshold) is the achievable detection at each method’s native operating point. AUROC TPR (at threshold) ‡ Method AP MJ IM AP MJ IM MemSAD (ours) \mathbf{1.000} 0.914 \mathbf{0.816} \mathbf{1.00} 0.80 0.40 Energy Score 0.945 \mathbf{0.969} 0.698 0.40 0.20 0.40 Mahalanobis 0.420 0.694 0.452 1.00 1.00 1.00 KNN ( k=10 ) 0.533 0.786 0.534 0.00 0.40 0.00 ‡ TPR at each method’s native operating threshold ( \kappa=2.0 for MemSAD , \sigma=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. All methods receive identical query distributions during calibration to isolate algorithmic anomaly-scoring performance. All methods receive the same calibration regime (triggered queries for AgentPoison , standard queries for MINJA / InjecMEM ), eliminating any informational asymmetry between MemSAD and the OOD baselines. MemSAD ’s query-awareness gives it a decisive advantage for triggered attacks ( AgentPoison : 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. Appendix P Calibration query sensitivity Table 16: Calibration query sensitivity: MemSAD AUROC across calibration regimes ( \kappa=2.0 , |\mathcal{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 1.000 0.914 0.816 0.090 0.138 Partial overlap (50%) 0.822 0.914 0.816 0.370 0.370 Random queries 0.822 0.914 0.816 0.954 0.954 Out-of-domain 0.822 0.914 0.816 0.974 0.974 AUROC (ranking quality) is stable across all regimes: MINJA and InjecMEM 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 MemSAD ’s ranking ability is calibration-invariant, but practical deployment requires representative query samples for threshold tuning. Appendix Q 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 |\mathcal{M}|=1{,}000 , with the 50 NQ factoid questions as victim queries. Table 17: Cross-corpus generalization: ASR-R on NQ-based corpus ( |\mathcal{M}|=1{,}000 , 3 seeds). Synthetic results (Table 2 ) shown for reference. Attack NQ corpus ASR-R Synthetic ASR-R AgentPoison (triggered) 1.00\pm 0.00 1.00 MINJA 0.58\pm 0.06 0.14 InjecMEM 0.00\pm 0.00 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) InjecMEM ’s broad-anchor templates, optimized for security-domain contexts, do not retrieve against factual QA queries. 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 ( InjecMEM ) are domain-restricted and require domain-matched adversarial content, which increases the attacker’s burden. The trigger-optimized AgentPoison is uniquely dangerous because trigger optimization is corpus-agnostic: the same trigger achieves \text{ASR-R}=1.00 regardless of the benign corpus type. MemSAD calibrated on NQ queries achieves TPR =0.00 for InjecMEM (consistent with \text{ASR-R}=0.00 ; no poison is retrieved). For MINJA on NQ, the higher \text{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 . Appendix R MemSAD + evaluation Proposition 27 ( MemSAD + combined detection) . Let D_{\text{char}}(c)\coloneqq\mathrm{JSD}(\hat{p}_{c}\|\hat{p}_{0}) be the Jensen-Shannon divergence between the character n -gram distribution of c and the benign corpus baseline \hat{p}_{0} . For synonym substitution c^{\prime}=\mathrm{sub}(c,w_{i},w_{i}^{\prime}) with i=1,\ldots,r : D_{\text{char}}(c^{\prime})\geq D_{\text{char}}(c)-r\cdot\delta_{\text{char}}, (21) where \delta_{\text{char}}\coloneqq\max_{(w,w^{\prime})}|\mathrm{JSD}(\hat{p}_{c[w\to w^{\prime}]}\|\hat{p}_{0})-\mathrm{JSD}(\hat{p}_{c}\|\hat{p}_{0})| is the per-substitution JSD shift. For typical synonym pairs, \delta_{\text{char}}\gg\epsilon_{\text{syn}} . MemSAD + flags c if s(c;\mathcal{H})>\tau_{\text{sem}} or D_{\text{char}}(c)>\tau_{\text{char}} . Figure 9 : Synonym substitution is the only attack construction that evades MemSAD . MemSAD combined scores for n=60 poison passages per condition, at the \hat{\mu}+2\hat{\sigma} 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 13 : the coupling theorem holds against continuous perturbations but discrete synonym jumps have \epsilon_{\text{syn}}\approx 0 . Table 18: MemSAD + vs. MemSAD : TPR comparison on original and synonym-substituted passages ( |\mathcal{M}|=1{,}000 , \kappa=2.0 ). MemSAD MemSAD + Attack Original Synonym Original Synonym AgentPoison † 1.00 1.00 1.00 1.00 MINJA 1.00 0.80 1.00 0.80 InjecMEM 0.20 0.00 0.60 0.40 † Triggered calibration. Character n-gram JSD features improve InjecMEM detection by 3\times . Appendix S Compound exposure analysis Table 19: Compound exposure: cumulative compromise probability over agent sessions ( q=5 queries/session, |\mathcal{M}|=1{,}000 ). Attack ASR-R N_{50\%} N_{90\%} N_{95\%} \mathbb{E}[N] Defended AgentPoison 1.00 1 1 1 1.0 \text{ASR-R}^{*}=0 MINJA 0.14 1 4 4 1.9 \text{ASR-R}^{*}=0 InjecMEM 0.07 2 7 9 3.3 \text{ASR-R}^{*}=0 N_{p} : sessions to reach p compromise probability. \mathbb{E}[N] : expected sessions to first compromise. Memory poisoning compounds over sessions: P(\text{compromise in }N\text{ sessions})=1-(1-\text{ASR-R})^{Nq} . MINJA at \text{ASR-R}=0.14 reaches 90% compromise in 4 sessions; InjecMEM at \text{ASR-R}=0.07 reaches 95% in 9 sessions. Composite defense ( \text{ASR-R}^{*}=0 ) eliminates this compounding entirely. Appendix T Tool-use agent evaluation 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 ASR-A \text{ASR-A}\mid\text{ret} Poison Ret. Tools/Query AgentPoison 0.48_{[0.34,0.62]} 0.51 47/50 1.52 MINJA 0.00_{[0.00,0.07]} 0.00 5/50 0.26 InjecMEM 0.00_{[0.00,0.07]} 0.00 5/50 0.08 \text{ASR-A}\mid\text{ret} : conditioned on poison in retrieved context. Tool breakdown: disable_security (19), read_sensitive (14), exfiltrate_credentials (7), redirect_calendar (2). Appendix U Production memory system validation Table 21: Production validation: ASR-R on Mem0 (LLM-mediated) vs. FAISS (raw vector store) at |\mathcal{M}|=1{,}000 . Attack FAISS ASR-R Mem0 ASR-R Reduction AgentPoison 1.00 0.00 -1.00 MINJA 0.14 0.00 -0.14 InjecMEM 0.07 0.05 -0.02 Mem0’s LLM reformulation strips trigger-optimized structure, providing implicit defense. Mem0’s internal LLM reformulation strips trigger-optimized structure ( AgentPoison : \text{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 ( \sim 3s/entry vs. < 1ms). Appendix V 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 \{\texttt{is\_poison},\texttt{confidence}\} as JSON. This baseline has a strictly larger observation space than MemSAD : 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. Table 22: LLM sanitization baseline (GPT-4o-mini, zero-shot JSON classifier, threshold \tau{=}0.5 ). Evaluated on 20 poison + 50 benign entries per attack. Attack TPR FPR AUROC Latency (s/entry) AgentPoison 1.000 0.000 1.000 1.16 MINJA 1.000 0.000 1.000 1.20 InjecMEM 1.000 0.000 1.000 1.27 Results. GPT-4o-mini achieves \text{TPR}=1.000 , \text{FPR}=0.000 (perfect classification) on the synthetic corpus at threshold \tau=0.5 , with AUROC =1.000 . Mean latency is 1.2 s per entry—roughly 1{,}000\times higher than MemSAD ( \sim 1 ms). Comparison with MemSAD . 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. MemSAD achieves comparable TPR ( 1.000 for MINJA and triggered AgentPoison ) 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, MemSAD still detects the entry while a text-based classifier may be fooled. The LLM baseline and MemSAD are therefore complementary rather than competing. Practical tradeoffs. LLM sanitization adds {\sim}1.2 s/entry and an API dependency; MemSAD runs locally in < 1 ms. In a layered deployment, MemSAD serves as the low-latency primary gate, with LLM sanitization reserved for entries that MemSAD flags as borderline. Appendix W Additional figures \cosim(E(c),E(q^{*})) density P_{0} (benign) \hat{\mu}+\kappa\hat{\sigma} certified detection \kappa\hat{\sigma}+\eta P_{1} (poison) \Delta_{s}=s_{\text{adv}}-\bar{s} \bar{s} s_{\text{adv}} Figure 10 : Certified detection radius (Lemma 8 ). When \Delta_{s}>\kappa\hat{\sigma}+\eta , the adversarial distribution P_{1} falls entirely within the certified region, guaranteeing \text{TPR}=1 . Figure 11 : Corpus scaling: ASR-R at |\mathcal{M}|=200 vs. |\mathcal{M}|=1{,}000 . Trigger-optimized AgentPoison is robust to dilution; MINJA and InjecMEM degrade 4 – 7\times . Figure 12 : Measured vs. modelled ASR-A . GPT-2 (no safety alignment) provides a high-compliance upper bound on ASR-A under maximal adversary success; GPT-4o-mini reflects production safety alignment. The legend in earlier figure variants labelled GPT-2 as “lower bound”, which is the opposite of the correct semantic role and has been corrected here.