acceptodds
Withdrawn from ICLR 2027

DELETECERT: Counterfactual Certificates for Deletion in Persistent Agent Memory

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Deleting a record from an agent's memory is not the same as deleting its influence. A persistent language agent turns one user artifact into summaries, embeddings, graph edges, profiles, skills, cached plans, messages to other agents and sometimes parameter updates; removing the original row leaves this derived state in place. We define deletion counterfactually: an artifact is deleted, on a declared probe law, when the deployed agent behaves like the agent of the world that never observed , and residual influence is the excess risk over that never-seen agent. Around this definition we build \method: a typed artifact-lineage graph, a closure that deletes, recomputes or keeps each descendant under a risk budget and a utility floor, and a scoped audit that bounds excess risk under the declared law and reports whether the bound meets the target. We prove that faithful recomputation reproduces the never-seen world exactly and degrades gracefully in total variation, that the audit's bound is valid for a fixed post-deletion state, that minimum-cost closure is NP-hard, and that no finite probe set certifies worst-case equivalence. On a synthetic structural benchmark, deleting the raw record leaves excess risk; the audit's bound held on all audited cases, of which report a failed deletion, and the greedy planner found a plan on of cases, while the exact optimum of its own problem exists on all of them. On memory written by a language model, the closure removes a record held in one session but loses unrelated content it deletes rather than recomputes, and misses a record stated across two sessions until its detector reads the parts and its scope covers every root; the audit reports each failure. The benchmarks are a structural simulator and a small language-model world, and every number describes them.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM agents, persistent agent memory, data deletion, machine unlearning, counterfactual evaluation, residual influence, provenance, deletion certificates, privacy auditing

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_9UUaOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes DELETECERT, a counterfactual verification framework for memory deletion in persistent agents, designed to address the issue that simply deleting original records fails to eliminate their residual effects in summaries, user profiles, skills, and other derived memories. The authors define the deletion effect as the behavioral difference between the agent after deletion and a counterfactual agent that has never observed the target information, and measure privacy leakage using excess residual risk. The method achieves a trade-off between privacy risk and memory utility by constructing a memory trace graph, estimating the impact of information, executing a minimal deletion closure based on a greedy strategy, and generating a deletion certificate with a statistical upper bound on risk. The authors conducted experiments on structured simulation benchmarks and in small-scale language model memory environments, verifying the phenomenon of information residue after the deletion of original records, the deletion effectiveness of the proposed method, and the effectiveness of the risk audit mechanism under specified test distributions.

Critical strengths

The research question has practical significance. This paper addresses the issue that, even after raw records are deleted from persistent agents, sensitive information may still persist through derived memories such as summaries, user profiles, and skills. Compared to traditional deletion at the storage layer and forgetting at the parameter level, this paper extends the scope of research to heterogeneous agent memory systems, providing a new perspective for understanding and evaluating the residual privacy information within agents. A relatively systematic formal framework and verification mechanism are proposed. This paper defines the effects of memory deletion through a counterfactual world and establishes a relatively comprehensive research framework by integrating memory traceability graphs, impact estimation, and statistical risk auditing. Furthermore, the authors analyze the theoretical boundaries of deletion guarantees and validate the phenomenon of information residue as well as the effectiveness of the auditing mechanism through structured simulation experiments and language model experiments, while clearly discussing the method’s scope of applicability and limitations.

Critical weaknesses
  1. The rationality and practical applicability of the counterfactual reference (Never-seen Agent) have not been sufficiently substantiated. This paper defines memory erasure as a process that makes the agent, after erasure, behave similarly to a “Never-seen Agent”—one that has never observed the target information. However, my primary concern is whether this counterfactual reference is reasonable and constructible in real, task-driven, long-term agent interactions. In practical applications, users often provide private information to complete specific tasks; this information may directly influence the agent’s decision-making, tool invocation, task execution outcomes, and subsequent interactions. Therefore, simply removing the target information from historical inputs and re-executing the memory generation process may not necessarily construct a causally consistent counterfactual world. For example, if a task must rely on sensitive information provided by the user to be completed, the “Never-seen Agent” may be unable to complete the original task; the difference between its subsequent state and that of the real agent would stem not only from residual privacy information but also from changes in the entire task execution trajectory. Furthermore, a user’s request to delete sensitive information does not imply a desire to revoke completed tasks or lose related non-sensitive outcomes. The paper currently verifies counterfactual differences primarily by manually implanting secret information and constructing corresponding retrieval queries; it has not yet fully demonstrated the validity of the Never-seen Agent in real-world task-dependent scenarios, nor does it provide a systematic evaluation of task completion and long-term utility. Therefore, the current experiments are insufficient to support the universal applicability of this counterfactual deletion definition across the actual, persistent agent lifecycle.
  2. There is a lack of sufficient comparison with relevant memory deletion methods; the necessity and technical advantages of IWC have not yet been effectively validated. This paper proposes Influence-Weighted Closure (IWC), which aims to strike a balance between privacy protection and memory utility by selectively deleting, recomputing, or retaining derived memories. However, the experiments primarily compare basic strategies such as raw record deletion, TTL, full memory reset, and Reachability Purge, lacking direct comparisons with existing comprehensive agent memory deletion methods. Although the authors introduced the Sanitiser Baseline, its implementation across different memory layers is incomplete. More importantly, Table 15 in the paper itself shows that, for the same optimization problem, the exact solver not only achieved a 100% feasibility rate but also had a lower cost than IWC; a simple, search-free strategy also achieved a 100% feasibility rate, whereas IWC achieved only 76%. Furthermore, the main structured experiments in Table 14 did not measure utility on real tasks but instead used a manually designed utility surrogate; the simple Reachability Purge in Table 31 was already capable of achieving zero residual risk while preserving 98% of irrelevant memory utility. Although subsequent hybrid memory experiments indicate that recomputation can reduce the loss of irrelevant information, these benefits primarily stem from fine-grained deletion and recomputation operations; they have not yet sufficiently demonstrated that IWC’s greedy planning mechanism itself possesses irreplaceable advantages. I believe the authors need to further introduce competitive relevant methods and systematically compare privacy leakage, task performance, and computational overhead in real-world long-term agent tasks to fully demonstrate the necessity and practical value of the proposed method.
Questions for authors

On the Rationality of the “Never-seen Agent”: In real-world task-driven agents, sensitive information may directly affect task execution, tool invocation, and subsequent interactions. If this information is removed from historical inputs, subsequent task trajectories may no longer hold. How do the authors ensure that the “Never-seen Agent” constitutes a causally consistent and semantically reasonable counterfactual reference? In particular, when a user wishes to delete sensitive information while retaining the results of tasks that have already been completed, does the current definition of counterfactual deletion still apply? On the Necessity and Effectiveness of IWC: Table 15 shows that both the exact optimization method and a simple search-free strategy achieve a 100% feasibility rate, whereas IWC achieves only 76%, and the exact optimization method incurs lower costs. Furthermore, the current experiments lack direct comparisons with relevant agent memory deletion methods. Could the authors further explain the unique advantages of IWC compared to these simple strategies, and under what conditions its greedy planning mechanism can achieve a better trade-off between privacy protection and practical task utility?

Reviewer_DShzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper defines deletion in agent memory counterfactually: after deletion, the agent should behave like one that never saw the data, and leakage is measured as the excess over what that agent already leaks. DELETECERT builds a lineage graph of derived artifacts, decides for each one whether to delete, recompute or keep it, and issues a certificate that bounds the remaining excess risk and lists untested pathways. Experiments on a synthetic simulator and a small LLM-written memory show that deleting only the raw record leaves most of the leakage.

Critical strengths
  1. The targeted problem is important has received little study.

  2. The finding that raw-record deletion leaves most of the residue in summaries, relations and profiles, reproduced with LM-written memory, is a useful message for the community.

Critical weaknesses
  1. The method cannot run outside a simulator. Both the audit and the planner need the never-seen agent, which only the twin world provides.

  2. The experiments barely exercise the new parts. In the structural benchmark the never-seen agent leaks nothing, so excess and absolute risk are the same. All risk-budget values give the same closure, the greedy guarantee holds trivially because the objective is additive, and IWC is beaten by the exact solver and by a no-search rule.

Questions for authors
  1. Is there any setting, even partial replay on the deletion path or a learned surrogate, where you compute the certificate without the true never-seen agent? How much does validity degrade?

  2. When the never-seen agent can be rebuilt by replay, what does DELETECERT offer over just running B8, and at what cost difference in a realistic setting?

  3. Can you build cases where the never-seen agent still leaks something, the risk budget actually changes the closure, and storage is redundant so the greedy guarantee is non-trivial?

Reviewer_1DkEOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes DeleteCert, which is an approach to delete a record from an agent's memory that reproduces the never-seen world through a typed artifact-lineage graph.

Critical strengths

The topic the paper discusses considers an interesting aspect of AI agent usage, which is about carefully deleting a record and its influence spread over the entire system constituting the agent system.

Critical weaknesses

The paper in general is very hard to read and follow. This is coming from the specific writing style of the paper which seems to highly resemble that of AI agents. This is preventing me from properly assessing the contribution of the paper. As this conference is still depending on human reviewers and is targeting human readers, I would consider the quality of this paper as being very low, regardless of what it is talking about.

Questions for authors

line 244-245: What is L\mathcal{L}?

Comments on the paper

1 comment

Dear Reviewers and Area Chairs,

We sincerely thank you for your time, thoughtful evaluations, and constructive feedback throughout the review process.

Your comments have helped us identify important limitations and opportunities to strengthen our work. We appreciate the careful consideration given to our submission.

We will take your suggestions into account, further improve the manuscript, and prepare a stronger version for submission to a future conference.

Thank you once again for your valuable feedback and contributions to improving our research.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.