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

arXiv:2605.03482v1 Announce Type: cross 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 with a unified evaluation framework spanning three attack classes with escalating access assumptions. Correcting an evaluation protocol inconsistency in the triggered-query specification of Chen et al. (2024), we show faithful evaluation increases measured attack success by 4imes (ASR-R: 0.25 o 1.00). Our primary contribution is MEMSAD (Semantic Anomaly Detection), a calibration-based defense grounded in a gradient coupling theorem: under encoder regularity, the anomaly score gradient and the retrieval objective gradient are provably identical, so any continuous perturbation that reduces detection risk necessarily degrades retrieval rank. This coupling yields a certified detection radius guaranteeing correct classification regardless of adversary strategy. We prove minimax optimality via Le Cam's method, showing any threshold detector requires Omega(1/rho^2) calibration samples and MEMSAD achieves this up to log(1/elta) factors. We further derive online regret bounds for rolling calibration at rate 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 imes 5 attack-defense matrix with bootstrap confidence intervals, Bonferroni-corrected hypothesis tests, and Clopper-Pearson validation (n=1{,}000) confirm: composite defenses achieve TPR = 1.00, FPR = 0.00 across all attacks, while synonym substitution evades detection at Delta ASR-R approx 0, exposing a gap existing embedding-based defenses cannot close.

Source: arXiv cs.LG | 2026-05-06