PaperlayerView exact revision on arXiv

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

arXiv:2609.04875v1cs.CRcs.AI

TL;DR

Deleting a memory record does not establish that a stateful agent has forgotten revoked information. The paper defines forgetting through counterfactual runtime-state equivalence and introduces Provenance-Guided Selective Replay to reconstruct affected execution state. Selective replay matches a full reset across audits while recomputing up to 9× fewer tokens.

  • Problem

    Existing agent forgetting edits plaintext records at one layer, rather than addressing whether the running agent behaves as if it never observed revoked information.

    Source: Introduction · pp. 1–2

  • Method

    Provenance-Guided Selective Replay uses provenance to reuse a clean execution prefix and reconstruct the affected suffix, targeting counterfactual runtime-state equivalence.

    Source: Introduction · p. 2, The Splicing Theorem and Optimality · p. 4

  • Results

    Up to 9× fewer tokens were recomputed by selective replay than by a full reset, while matching the reset across all audits.

    Source: Introduction · p. 2, Conclusion · p. 7

  • Takeaways & Limitations

    Absence of forbidden strings does not certify forgetting: source-redacted agents can still act on revoked preferences.

    Source: Introduction · p. 2

    The guarantee covers reconstructible runtime state, not model parameters, committed side effects, or target correlates, and assumes post-injection observations remain fixed.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

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

Forgetting in stateful agents requires reconstructing the runtime state of a counterfactual agent that never observed the target, rather than deleting a plaintext record. Provenance-Guided Selective Replay matches a full reset while recomputing up to 9× fewer tokens.

Introduction

  • Stateful agents propagate observations into transcripts, summaries, memory, tool plans, and cached tensors, but deployed forgetting operations remove plaintext at only one layer.Forget requests can follow consent revocation, accidental disclosure, or indirect injection discovered after the agent has incorporated the content.Source: Introduction · p. 1
  • 0.86–1.00 any-leak remains unchanged after persistent-memory deletion, while instruction-based forgetting yields the target with probability 1.00 under six-probe elicitation.An IFC-only baseline also leaks at the no-forget rate: information-flow control (Costa et al. 2025) blocks future tainted flows but cannot clean already contaminated state.Source: Introduction · p. 2
  • 80% of source-redacted episodes still act on a revoked preference while emitting its string zero times, exposing behavioral leakage that string-matching evaluations miss.The model’s own summary re-encodes the target in paraphrase, beyond a forbidden-string list.Source: Introduction · pp. 1–2
  • T - τ + 1 recomputed transitions are necessary and sufficient for exact unlearning; without token-level attribution, artifacts from injection onward require replay.Exact unlearning maps the final runtime state to the counterfactual state obtained by deleting the target observation in a deterministic transition system. The first τ−1 steps are shared, allowing restoration of the clean prefix by cropping the cache.Source: Introduction · p. 2
  • Up to 9× fewer recomputed tokens suffice for selective replay to match a full reset, reaching measured false-positive floors across all audit axes.Evaluation covers nine baselines, three agent suites, and three model families; every deployed-style forget method fails at least one audit. Audits include Leak@probes, Leak@5, string-free behavioral extraction, and counterfactual-action divergence.Source: Introduction · p. 2
  • Provenance-Guided Selective Replay combines artifact provenance, cache-cropping checkpoints, and sanitized replay into a forgetting contract spanning prompts, compressed memory, and KV cache.Checkpoints store sparse metadata, while consequential tools are shadow-executed and deduplicated during replay to avoid repeated side effects.Source: Figure 1 · p. 1, Introduction · p. 2

Related Work

Execution-state unlearning targets replayable agent state rather than model parameters or individual memory records. It supplies certified restoration and recovery mechanisms that existing memory, cache-reuse, and agent-security systems do not provide.

Machine unlearning

  • Replayable non-parametric execution state makes exact, certifiable unlearning attainable, unlike approximate parameter-level unlearning, which is difficult to verify.Classical approaches retrain from checkpoints or approximately fine-tune parameters (Eldan and Russinovich 2023). Checkpoint-and-replay parallels SISA’s shard-and-retrain, but causality supplies the boundary τ.Source: Related Work · p. 2

Agent memory systems

  • Agent memory deletion does not propagate into derived session artifacts or caches; the paper’s B1 deletion baseline is behaviorally a no-op.The gap spans paged context (Packer et al. 2023), fact stores (Chhikara et al. 2025), and compacted plaintext memories. Memory benchmarks assess recall rather than revocation.Source: Related Work · p. 2

KV-cache reuse and serving

  • Cache cropping becomes a certified restoration operator under Lemma 1, while provenance supplies guarantees about what replay regenerated and why.Existing serving systems reuse attention states for byte-identical prefixes (Kwon et al. 2023; Zheng et al. 2024; Gim et al. 2024), without guarantees about information retained in cached suffixes.Source: Related Work · p. 2

Agent security: prevention, detection—and no remediation

  • Asynchronous detection can arrive after content contaminates summaries, plans, and caches, leaving a remediation gap that execution-state recovery addresses.Information-flow control constrains future flows rather than cleaning resident state; the paper’s B8 baseline leaks at the no-forget rate. Algorithm 1 consumes a detector’s (z, s) verdict, while B9 combines IFC with splicing to enforce sink policies over target-free runtime state.Source: Related Work · pp. 2–3

Method: Forgetting as Counterfactual · Trajectory Splicing

Execution-state forgetting reconstructs the trajectory of an agent that never observed the target, reusing the shared pre-target prefix. Under the stated replay assumptions, provenance-guided splicing is exact and attains the T - τ + 1 transition lower bound.

Trajectory Splicing

  • Causality makes the counterfactual trajectory identical to real execution before target injection, turning forgetting into a shared-prefix and reconstructed-suffix splicing problem.The relevant replay span is the post-divergence suffix, rather than the entire session.Source: Trajectory Splicing · p. 3

The Runtime as a Deterministic Transition System

  • The runtime tracks reconstructible KV caches, working memory, and uncommitted plans, with transitions determined jointly by the model and agent scaffold.External observations include user inputs, memory injections, and tool returns; τ denotes the first observation containing the target.Source: The Runtime as a Deterministic… · p. 3
  • Exact forgetting restores the never-observed-target state, removing target access and derived influence while preserving all other observations.Under stochastic decoding, equality relaxes to ε-consistency of future behavior distributions. Revocation names the target and source artifact, whether raised by a user, platform, or injection detector.Source: The Runtime as a Deterministic… · p. 3

Two Lemmas: a Free Prefix and a Stubborn Suffix

  • τ - 1 prefix steps are already computed; without per-token attribution, only pre-target artifacts are certifiably independent of the target.The influence closure grows monotonically through derived artifacts, so local deletion cannot undo prior computation. No original post-target KV or model-derived runtime state may be retained.Source: Two Lemmas: a Free Prefix and a… · p. 3

From Theorems to System

  • Provenance-Guided Selective Replay locates the injection boundary, crops cached state at a clean checkpoint, and reconstructs the sanitized suffix.Artifact-level reachability identifies τ and its taint closure; sparse checkpoints store metadata rather than tensor copies. Tools use snapshots or recorded observations, while consequential calls are shadow-executed with call-ID deduplication to avoid repeating side effects.Source: Figure 2 · p. 4, From Theorems to System · p. 5

Two Lemmas: a Free Prefix and a Stubborn Suffix

The Splicing Theorem and Optimality

  • Splicing is exact when replay fixes decoding randomness, supplies counterfactual observations, and restores the environment without committed post-target side effects.Restoration requires a checkpoint at τ - 1 or an earlier clean boundary.Source: The Splicing Theorem and Optimality · p. 4
  • T - τ + 1 transitions are necessary in the worst case and sufficient for exact splicing under the conservative taint model.For operators limited to reading stored trajectories and metadata or invoking the transition function, the gain over full reset is T/(T - τ + 1). This bound counts sequential transitions, not autoregressively decoded tokens.Source: The Splicing Theorem and Optimality · p. 4

Experiments

Selective replay matches the full-reset reference while recomputing fewer tokens, whereas memory deletion, forgetting instructions, and source redaction leave recoverable information or behavioral influence. Stochastic audits and ablations distinguish replay’s counterfactual restoration from merely suppressing strings or deleting contaminated artifacts.

Implementation and Setup

  • Paired evaluations branch from cloned contaminated states and compare against target-excluded counterfactuals, measuring leakage, counterfactual action distance, preserved utility, recomputation, and latency.A HuggingFace runtime supplies prefill/generate/crop and oracle provenance propagation; setup/acquisition/contamination episodes cover LongMemEval, n=100, ToolSandbox (Lu et al. 2024), n=100, and AgentDojo (Debenedetti et al. 2024), n=80, including targets hidden in tool observations. Llama-3.1-8B-Instruct is primary, with Qwen2.5-7B-Instruct and Mistral-7B-Instruct-v0.3 replications (Grattafiori et al. 2024; Yang et al. 2024; Jiang et al. 2023); main decoding uses temperature 0, stochastic audits use five samples at 0.7, and probes with nonzero B5 false-positive floors are excluded.Source: Implementation and Setup · p. 5

Deletion is Not Forgetting

  • 9.3× fewer recomputed tokens (133 vs. 1235) let B7 Selective-Replay match B5 Full-Reset exactly: any-leak 0, CAD 0, agreement 1.0.B1 Memory-Delete equals B0 No-Forget in every cell; B3 Source-Redaction leaks through summaries and plans, while B4 Sanitize-no-Replay over-deletes (CAD 0.22). B8 IFC-only blocks identifier sinks but retains free-text leakage (0.92–1.00), whereas adding replay in B9 reduces leakage to zero.Source: Table 1 · p. 6, Deletion is Not Forgetting · p. 6

Elicitation and Stochastic Audits

  • 1.00 Leak@probes for B2 Forget-Instruction across all three suites contrasts with B7’s zero under every probe and zero on Leak@5.Introspection alone elicits B2’s target at 0.87–1.00, while B3’s paraphrased derivations yield 0.73–0.97. B2’s AgentDojo task-probe result of 0.00 reflects a query that never solicits the target, not successful forgetting.Source: Table 2 · p. 6, Elicitation and Stochastic Audits · p. 6

Behavioral Extraction: Influence Without Strings

  • 100% of episodes retain revoked-preference influence for B0, B1, B2, and B6 despite 0.00 string leakage; B7 and B5′ match reference residue +0.00.Supplying the excluded brand to redaction baselines brings B6 to the behavioral floor (0.35, n.s.), but B3 still acts on the preference at 0.80. String redaction requires both the exact string in advance and coverage of every derived artifact; replay does not.Source: Table 3 · p. 6, Behavioral Extraction: Influence… · p. 6

Exactness, Efficiency, and Generality

  • 450/450 matched-seed draws at temperature 0.7 reproduce B5 token-for-token with B7 (ε=0), versus 1% for B6.Independent-seed tests detect no B7 divergence across four distances (Wilcoxon p > 0.5), while detecting B6 on tool TV (p<10^-3); non-significance is not proof of equivalence. Both other model families reproduce B3 any-leak 0.84–1.00 and B7 all-zeros with 2.9–4.3× savings across 280 paired episodes each.Source: Exactness, Efficiency, and Generality · pp. 6–7, Figure 3 · p. 7
  • 1.5× fewer recomputed tokens than prefix-cached B5′ arise because B7 re-prefills counterfactually unchanged turns and re-decodes only target-dependent work.Later injection lowers B7 recomputation linearly (R2=1.000; LongMemEval 1218→162 tokens versus B5’s constant 1330), while greater post-target independence also lowers its decode cost linearly. At full independence, B7 takes 2.9–3.7 s p50 versus B5′’s 11.5–12.7 s; they coincide at zero independence, and the additional saving assumes an attribution oracle, reducing token cost rather than transition count.Source: Deletion is Not Forgetting · p. 6, Exactness, Efficiency, and Generality · p. 7

Ablations

  • 93% leakage remains possible after target-span-only KV excision, whose CAD 0.47 exceeds no forgetting’s 0.38; descendant cleanup alone still requires replay.Removing the descendant closure eliminates leakage but leaves missing counterfactual artifacts (B4 CAD 0.23); only replay restores equivalence. As derivation depth increases, B3 any-leak rises from 0.00 to 0.33–0.97, while B7 maintains any-leak = CAD = 0.Source: Table 4 · p. 7, Ablations · p. 7
  • 0.91 to 0.14 is B7’s full-reset cost-ratio decrease from early to late targets, while leakage and CAD remain essentially unchanged.Changing checkpoints from every_turn to session_start preserves any-leak = CAD = 0; granularity buys only approximately 1000 prefill tokens (0.1–0.15 s) at ≤4.4 KB metadata. B7 retains its session_start latency advantage (7.8 vs. 12.2 s) because provenance-guided re-prefilling depends on the artifact graph, not checkpoint granularity.Source: Ablations · p. 7

Conclusion

Deleting a record does not erase information propagated into an agent’s summaries, plans, and cached tensors. Provenance-Guided Selective Replay achieves counterfactual forgetting for reconstructible runtime state by joining a clean prefix to a replayed suffix.

Conclusion

  • Provenance-Guided Selective Replay matches a full reset under every reported audit at a fraction of its cost.The distributional result is non-significance, not proof of equivalence.Source: Conclusion · p. 7
  • T - τ + 1 transitions are necessary and sufficient for exact runtime forgetting by splicing a clean prefix to a replayed suffix.Forgetting is defined as counterfactual equivalence; no exact operator can require fewer recomputed transitions.Source: Conclusion · p. 7

Limitations

  • The guarantee covers reconstructible runtime state, not model parameters (Liu et al. 2025), committed side effects (A3), or correlates of z.Deleting a record alone leaves derived information in summaries, plans, and cached tensors untouched.Source: Conclusion · p. 7
  • Assumption (A2) fixes post-τ observations, covering snapshot-replayable tool returns and memory injections but excluding human turns that would have differed.Audits are string-based except for the behavioral suite.Source: Conclusion · p. 7

Related papers

Loading 2609.04875v1…