Abstract

Long-running LLM agents are stateful: beyond the transcript they accrete compressed summaries, plaintext memory, pending tool plans, andunder every serving APIa KV cache. Yet todays 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 targets 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 stringfree 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 episodeswhile selective replay is indistinguishable from a full reset at up to 9 __ fewer recomputed tokens.