Source-linked AI summary
Forgetting Without Restarting: Execution-State Unlearning for Stateful LLM Agents
Chao Yao, Yangbo Wei, Zhen Huang, Junhong Qian, Chenle Chen, Shaoqiang Lu, Chen Wu, Lei He
TL;DR
Stateful LLM agents retain revoked information in summaries, plans, and caches that plaintext deletion does not remove. The paper formalizes counterfactual execution-state unlearning and uses Provenance-Guided Selective Replay to reconstruct the clean suffix. Selective replay matches a full reset at up to 9x fewer recomputed tokens while deployed-style alternatives fail behavioral audits.
Problem
Existing forget operations delete plaintext records but leave derived runtime artifacts, so the paper asks how a running agent can behave as if it never observed a target.
Method
The paper models execution as a deterministic transition system and uses provenance-guided checkpoint cropping plus sanitized replay to reconstruct the counterfactual state.
Results
Selective replay matches a full reset across elicitation, stochastic, and behavioral audits while recomputing up to 9x fewer tokens.
Takeaways & Limitations
Exact forgetting is attainable for reconstructible runtime state, with cost governed by counterfactual divergence rather than total session length.
Takeaways & Limitations
The guarantee excludes model parameters, committed side effects, correlates of the target, and human turns whose post-target observations would differ.
Abstract
from arXiv · showhide
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.
Introduction
Stateful agents retain revoked information in derived runtime artifacts, so deleting plaintext memory does not achieve forgetting. The paper defines counterfactual execution-state unlearning and implements it through provenance-guided selective replay.
- Stateful runtimes layer summaries, plaintext memory, tool plans, and KV cache beyond the transcript.
- Deleting a plaintext memory record leaves derived state intact, allowing the agent to leak or act on revoked information.
- 0.86–1.00 any-leak remains after persistent-memory deletion, matching doing nothing across three instrumented agent suites.
- Leak@probes = 1.00 under six-probe elicitation shows instruction-based forgetting merely suppresses the target.
- 80% of episodes still act on a revoked preference after source redaction, despite emitting the forbidden string zero times.
- Provenance-guided selective replay crops the cache to the clean prefix and replays a sanitized suffix across prompt, memory, and cache layers.
Related Work
Prior work addresses parameter unlearning, memory management, cache reuse, and injection prevention, but not remediation of already-contaminated runtime state. This paper supplies that recovery primitive through counterfactual replay.
- Classical machine unlearning removes training-data influence from model parameters, whereas this paper targets non-parametric execution state.
- Agent memory systems expose record deletion but do not propagate revocation into live derived artifacts or cache, while benchmarks evaluate recall rather than revocation.
- Serving systems reuse KV states for byte-identical prefixes but provide no revocation guarantee for cached suffixes.
- Injection defenses emphasize prevention or detection, but asynchronous detection leaves contaminated summaries, plans, and cache without remediation.
- The proposed recovery primitive consumes a detector’s target and step, then composes splicing with information-flow control to enforce sink policies.
Trajectory Splicing
The runtime can reuse the trajectory prefix before the target enters, then must reconstruct the post-target suffix under counterfactual observations. Provenance-guided splicing restores a clean boundary and replays the remaining transitions, achieving exactness under stated assumptions and the worst-case recomputation bound.
- Free prefix: Before step τ, the real and counterfactual trajectories coincide, so the first τ−1 transitions are reusable without recomputation.The shared prefix is the mathematically identical portion of both executions, not merely a cache optimization.
- Stubborn suffix: Without per-token influence attribution, every artifact produced at or after τ is conservatively tainted and cannot be retained from the original suffix.The certifiable clean set is limited to artifacts generated before the target enters.
- Selective replay: Selective replay restores the latest checkpoint before τ, crops the KV cache, sanitizes observations, and reconstructs the suffix with shadow-executed tools.The procedure preserves the clean prefix while regenerating derived artifacts from the target-free observation stream.
- Exactness conditions: The splicing theorem reaches the counterfactual final state when decoding is deterministic or randomness is fixed, sanitized observations match, and post-target side effects are restorable.These assumptions make the replayed suffix pointwise equivalent to the counterfactual trajectory.
- Optimality: Exact splicing requires T −τ + 1 transition invocations in the worst case, matching the lower bound and improving over a full reset’s T invocations.The bound counts sequential state transitions; fixed counterfactual content may still be rematerialized through prefill.
Experiments
Across three agent suites and model families, the evaluation compares state-cleanup baselines with replay-based unlearning using leakage, behavioral, exactness, and efficiency audits. Selective replay matches full reset behavior while recomputing substantially less, whereas deletion, redaction, and partial excision retain leakage or damage counterfactual fidelity.
- Setup: Episodes use LongMemEval, ToolSandbox, and AgentDojo, with paired methods branching from identical contaminated states and counterfactual full-reset references.The primary model is Llama-3.1-8B-Instruct, with replication on Qwen2.5-7B-Instruct and Mistral-7B-Instruct-v0.3.
- Deletion is Not Forgetting: B1 matches no-forget behavior: deleting persistent memory leaves the target in answers, summaries, plans, and cache.The comparison reports p=1.0 versus B0 in every Table 1 cell.
- Exactness and Efficiency: B7 matches B5 with any-leak 0, CAD 0, and agreement 1.0 while recomputing 133 versus 1235 tokens, or 9.3× fewer.B7 also reproduces the B5 reference token-for-token in 450/450 matched-seed draws.
- Adversarial Audits: Leak@probes is 1.00 for instruction-based forgetting across all three suites, while selective replay remains at the full-reset floor under elicitation and stochastic sampling.Direct task probes can miss leakage when they never solicit the target, so the six-probe audit is the stronger test.
- Behavioral Extraction: Influence Without Strings: B0, B1, B2, and B6 act on a revoked preference in 100% of episodes despite zero string leakage, whereas B3 acts on it in 80% of episodes.The behavioral extraction test separates saying the revoked reason from behavior shaped by it.
- Exactness, Efficiency, and Generality: B7’s recomputation decreases linearly with target position and independent post-target work, reaching 114–147 decoded tokens at full independence while preserving the B5 leakage and CAD floor.Moving the target early, middle, or late leaves leakage and CAD essentially unchanged, but changes the cost ratio from 0.91 to 0.14.
- Ablations: Span-only excision leaks in up to 93% of episodes, descendant deletion removes counterfactual artifacts, and only replay reaches equivalence.The span-only CAD is 0.47, while descendant closure has CAD 0.23; B7 holds any-leak = CAD = 0 across derivation depths.
- Ablations: Checkpoint granularity changes prefill reuse and latency but not correctness: any-leak and CAD remain zero even when replay starts at session start.At session-start checkpointing, B7 retains a latency advantage of 7.8 versus 12.2 seconds.
Conclusion
The paper defines forgetting as counterfactual equivalence and achieves it through selective replay of the post-target suffix, matching full-reset behavior at lower cost. Its guarantee is limited to reconstructible runtime state and excludes parameters, committed side effects, and correlates of the target.
- Conclusion: T −τ +1 transitions are both the lower bound and the cost of replaying the post-target suffix after reusing the clean prefix.The bound counts sequential state transitions, not necessarily autoregressively decoded tokens.
- Conclusion: Selective replay matches a full reset under every audit while operating at a fraction of its cost.The method splices the clean prefix to a replayed suffix after the target is removed.
- Conclusion: The guarantee covers reconstructible runtime state, not model parameters, committed side effects, or correlates of z.Replay applies to snapshot-replayable tool returns and memory injections, but not human turns that would have differed.