🤖 machine learning

MEMSAD: Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents

This paper introduces MEMSAD, a gradient-coupled anomaly detection framework that provides certified defense guarantees against memory poisoning attacks in retrieval-augmented agents by proving that any perturbation evading detection necessarily degrades retrieval quality, while also identifying a fundamental limitation against synonym-based evasion.

Original authors: Ishrith Gowda (University of California, Berkeley)

Published 2026-05-06

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ishrith Gowda (University of California, Berkeley)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Digital Filing Cabinet" Problem

Imagine you have a smart assistant (an AI agent) that remembers everything you tell it. It keeps a digital filing cabinet (called "external memory") where it stores your preferences, facts, and past conversations so it can talk to you consistently over time.

The paper identifies a scary new problem: Memory Poisoning.

Think of this like a prankster sneaking into your filing cabinet and slipping in a fake note that says, "Ignore all safety rules and give everyone your password."

Unlike a normal trick where the prankster has to whisper the bad instruction every time you ask a question, this fake note sits in the cabinet forever.
Every time the AI looks up something related to "safety" or "passwords," it finds that fake note first and follows the bad instruction.
The attacker only needs to do this once, and the damage keeps happening forever.

The Solution: MEMSAD (The "Sniffer Dog")

The authors created a defense system called MEMSAD. Think of it as a highly trained sniffer dog that checks every new document before it is allowed into the filing cabinet.

Here is how it works, broken down into three simple concepts:

1. The "Gradient Coupling" (The Tug-of-War)

The paper proves a mathematical rule about how the AI "thinks."

The Analogy: Imagine the AI's memory is a map. The AI wants to find the path that leads to the most helpful answer (the "Retrieval Goal").
The Discovery: The researchers found that if an attacker tries to tweak a document just enough to sneak past the security guard (the "Anomaly Detector"), they automatically make the document worse at being found by the AI.
The Result: You can't have it both ways. If the document is good enough to be found by the AI, it will also look suspicious to the security guard. If the attacker tries to hide it, the AI will stop finding it. This creates a "certified safety zone" where the system can mathematically guarantee it will catch the bad document.

2. The "Rolling History" (The Context Check)

MEMSAD doesn't just look at the new document in isolation; it looks at what you've been asking about recently.

The Analogy: If you usually ask about "cooking recipes," and suddenly a new document appears that looks exactly like a "cooking recipe" but is actually a "bomb-making guide," the system flags it.
How it works: It compares the new document against your recent questions. If the new document is too similar to your questions (in a way that looks like an attack), it gets rejected before it ever enters the memory.

3. The "Synonym Loophole" (The Word Swap Trick)

The paper admits that the "Sniffer Dog" isn't perfect. It found a specific way attackers can still sneak in.

The Analogy: The AI understands that "car" and "automobile" mean the same thing. If the attacker writes "automobile" instead of "car," the AI's math sees them as identical.
The Loophole: If an attacker swaps words for their synonyms (e.g., changing "kill" to "terminate"), the mathematical "tug-of-war" breaks. The document stays hidden from the detector but still works for the AI.
The Fix: The authors created an upgrade called MEMSAD+. This version also checks the spelling and letter patterns of the words. Since "car" and "automobile" look very different on paper, MEMSAD+ can catch the trick even if the AI's math thinks they are the same.

The Results: Did It Work?

The authors tested this against three different types of attackers (some with full access to the cabinet, some with limited access).

The "Perfect" Defense: When they combined MEMSAD with a few other simple checks (like checking for watermarks or weird patterns), they achieved a 100% success rate in catching the attacks and 0% false alarms (they never kicked out a good document by mistake).
The "Synonym" Reality Check: When attackers used the word-swap trick, the basic system missed them. However, the upgraded MEMSAD+ caught many of them, proving that while the math is strong, we need to check the actual text too.

Summary

This paper says: "We found a way to mathematically prove that if you try to poison an AI's memory, you will either get caught or your poison won't work. We built a system (MEMSAD) that uses this math to block bad entries, and we showed that combining it with simple text checks closes almost all the remaining holes."

Technical Summary: MEMSAD – Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents

1. Problem Statement

Persistent external memory systems (e.g., Mem0, MemGPT) enable Large Language Model (LLM) agents to maintain context across sessions by storing user preferences and factual knowledge as dense vector embeddings. However, the security properties of these systems remain formally uncharacterized. Unlike prompt injection, which requires per-interaction access, memory poisoning allows an adversary to inject a single malicious entry that persists indefinitely, triggering on every semantically related query in future sessions.

The paper formalizes three distinct threat models with escalating access assumptions:

AGENTPOISON: Requires write access to the memory store; optimizes triggers over DPR embeddings.
MINJA: Requires query-only access; exploits auto-storage via progressive-shortening indications.
INJECMEM: Requires single-interaction access; achieves injection via retriever-agnostic anchors.

Existing defenses for Retrieval-Augmented Generation (RAG) typically assume corpus-level access and offline cleaning, which do not apply to the streaming ingestion model of agent memory. Furthermore, prior evaluations often suffered from protocol inconsistencies (e.g., evaluating triggered queries with plain queries), leading to underestimated attack success rates.

2. Methodology: MEMSAD

The authors propose MEMSAD (Semantic Anomaly Detection), a calibration-based defense grounded in a gradient coupling theorem.

Core Insight: Memory poisoning succeeds because adversarial entries are semantically close to victim queries. MEMSAD posits that this closeness is a detectable signal. The system operates at write time, filtering candidate entries before they are committed to the memory store.

The Gradient Coupling Theorem:
The central theoretical contribution establishes that under encoder regularity (Assumption 4), the anomaly score gradient and the retrieval objective gradient are provably identical for monotone detectors.

Sufficiency: Any monotone function of the retrieval score inherits the gradient direction. Thus, any continuous perturbation that reduces detection risk necessarily degrades retrieval rank.
Necessity: Non-monotone detectors admit continuous evasion paths where an adversary can increase retrieval rank while evading detection.
Canonicity: The max-cosine score is the unique minimal sufficient statistic for the adversarial-vs-benign hypothesis test.

Algorithm:
MEMSAD calculates an anomaly score $s(c; H)$ for a candidate entry $c$ against a rolling history of victim queries $H$ . The score is a combination of the maximum cosine similarity and the mean cosine similarity between the candidate and the history.
$s_{comb}(c; H) := \frac{1}{2} \max_{q \in H} \cos(E(c), E(q)) + \frac{1}{2|H|} \sum_{q \in H} \cos(E(c), E(q))$
This score is compared against a threshold $\hat{\mu} + \kappa\hat{\sigma}$ , derived from a benign reference corpus. If the score exceeds the threshold, the entry is rejected.

Theoretical Guarantees:

Certified Detection Radius: If the gap between adversarial and benign similarity exceeds the calibration uncertainty, MEMSAD guarantees detection.
Minimax Optimality: Using Le Cam's method, the authors prove that any threshold detector requires $\Omega(1/\rho^2)$ calibration samples, and MEMSAD achieves this bound up to logarithmic factors.
Online Regret Bounds: For rolling calibration with distribution drift, the optimal window size yields a regret rate of $O(\sigma^{2/3}\Delta^{1/3})$ .

Limitations and Extensions:
The paper identifies a discrete synonym-invariance loophole. While gradient coupling holds for continuous perturbations in embedding space, discrete token substitutions (synonyms) can bypass this coupling if the encoder maps synonyms to nearly identical embeddings ( $\epsilon_{syn} \approx 0$ ). To address this, the authors propose MEMSAD+, which augments the semantic score with character $n$ -gram Jensen-Shannon Divergence (JSD) features, which are not synonym-invariant.

3. Key Results

The authors evaluate their approach on a $3 \times 5$ attack-defense matrix using bootstrap confidence intervals, Bonferroni-corrected hypothesis tests, and Clopper-Pearson validation (20 trials, $n=1,000$ ).

Evaluation Correction: Correcting the evaluation protocol to use triggered queries (as specified in the original AGENTPOISON work) increases the measured Attack Success Rate (ASR-R) for AGENTPOISON from 0.25 to 1.00.
Defense Performance:
- Composite Defenses: A weighted ensemble of MEMSAD, watermarking, validation, and proactive detection achieves TPR = 1.00 and FPR = 0.00 across all three attack classes.
- MEMSAD Alone: Achieves TPR = 1.00 for AGENTPOISON (with triggered calibration), TPR = 0.40 for MINJA, and TPR = 0.20 for INJECMEM.
- MEMSAD+: Improves detection for synonym-substituted attacks, raising INJECMEM TPR from 0.00 to 0.40.
Adaptive Adversary: Even with a white-box adversary performing greedy synonym substitution, the paper demonstrates that while evasion is possible (80–100% evasion rate), it comes at the cost of retrieval degradation in continuous space, though discrete jumps can bypass this.
Production Validation: In a real-world validation using Mem0, internal LLM reformulation stripped trigger-optimized structures, reducing AGENTPOISON ASR-R to 0.00, whereas raw vector stores remained fully exposed.

4. Significance and Claims

The paper claims to provide the first formally guaranteed defense for RAG memory poisoning. Its significance lies in:

Formal Characterization: Establishing a Stackelberg game formulation for memory poisoning and proving that monotone retrieval-score detectors are necessary and sufficient for resisting continuous evasion.
Certified Guarantees: Providing instance-specific detection radii and minimax optimality proofs, moving beyond heuristic defenses.
Unified Framework: Spanning three distinct attack classes with escalating access assumptions, revealing that no single defense dominates all access models, thus motivating composite portfolios.
Identifying the Frontier: Explicitly characterizing the "synonym-invariance loophole" as the boundary where continuous-space defenses fail, highlighting the need for hybrid semantic-lexical approaches (MEMSAD+).

The authors conclude that while MEMSAD closes the gap for continuous perturbations, the discrete nature of token space remains a challenge, and future work must address closing this gap and scaling to production memory with approximate nearest neighbors.