Forgetting Without Restarting: Execution-State Unlearning for Stateful LLM Agents
Researchers propose provenance-guided selective replay letting LLM agents forget revoked information without restarts, matching full reset behavior.
The paper formalizes execution-state unlearning for stateful LLM agents, requiring that agents behave as if a revoked memory record was never observed across transcripts, compressed memory, tool plans, and KV caches. It proves exact unlearning requires at least T-τ+1 recomputed transitions and that Provenance-Guided Selective Replay attains this bound via a provenance graph, KV cache cropping, and sanitized replay. In audits across three agent suites, nine baselines, and three model families, memory deletion left leakage unchanged, instruction-based forgetting collapsed under elicitation (Leak@probes = 1.00), and selective replay matched full resets at up to 9x fewer recomputed tokens.
- Formalizes execution-state unlearning across prompt, memory, and KV cache
- Proves exact unlearning needs at least T-τ+1 recomputed transitions
- Selective replay indistinguishable from full reset at 9x fewer tokens
- Instruction-based forgetting leaks revoked data in 100% of probes
- Source redaction still leaked revoked preferences in 80% of episodes
Full article213 words · extracted from arxiv.org · click to collapse
Long-running LLM agents are stateful: beyond the transcript they accrete compressed summaries, plaintext memory, pending tool plans, and, under every serving API, a KV cache. Yet today's "forget" operations delete a plaintext memory record and stop, leaving every artifact derived from the revoked information intact. We formalize execution-state unlearning: after a forget request, the agent must behave as if it had never observed the target. Modeling the runtime as a deterministic transition system, we prove that the pre-target trajectory prefix is shared with this counterfactual world for free, that the post-target suffix is irreducibly tainted without token-level attribution, and that exact unlearning requires at least $T-τ+1$ recomputed transitions, where $τ$ is the target's injection step. Provenance-Guided Selective Replay attains this bound as a cross-layer contract spanning prompt, compressed memory, and cache: a provenance graph locates the injection point, checkpoint restoration reduces to cropping the KV cache, and sanitized replay regenerates the counterfactual suffix. Audited with elicitation, stochastic, and string-free behavioral tests across three agent suites, nine baselines, and three model families, memory deletion leaves leakage unchanged, instruction-based forgetting collapses under elicitation (Leak@probes = 1.00), and source redaction still acts on a revoked preference in 80% of episodes, while selective replay is indistinguishable from a full reset at up to 9x fewer recomputed tokens.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.04875