acceptodds
Under review as a conference paper at ICLR 2027

WitRepair: Certifiable Minimum Repair of Persistent Agent Memory via Retrieval Equivalence

Abstract

Deleting a memory record that caused an agent failure can expose a replacement with the same effect. We study minimum-cardinality deletion over a declared actionable memory set, with a certificate excluding every smaller repair. We introduce WitRepair, which groups deletions by their ordered retrieved contexts. Under deterministic replay and deletion-stable rankings, each single-read class has a unique minimum representative; one replay labels the whole class. For read-only multi-turn agents, deletion and retention conditions across all reads characterize complete trace classes. We derive tight worst-case search bounds and a separate label count for certifying a given minimum repair. On ReAct–StrategyQA, the complete search policy certifies 93.33–97.44% of incidents across three models. An order-by-cache ablation attributes fresh-response differences to search order and execution savings to trace reuse. Across 12 controlled SQLite configurations, trace reuse reduces mean fresh executions from 42.42 to 9.58 under repair-first search and from 74.25 to 11.75 under direct search, relative to exact-candidate caching. Certificates establish minimum cardinality for the specified task, actionable set, and deterministic replay oracle.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM agents, persistent memory, post-incident repair, retrieval equivalence, trace reuse, minimum repair certification

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_dv9POpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes WitRepair, a framework for finding minimum-cardinality memory deletions to repair failures in persistent-memory agents. The key idea is to exploit retrieval equivalence: different deletion sets may lead to the same retrieved context or execution trace, allowing their outcomes to be reused without redundant agent executions. The authors introduce canonical representatives for retrieval-equivalence classes and extend the approach to multi-turn agents through complete-trace guards. They also provide theoretical bounds on search complexity and guarantees for minimum-cardinality repair under deterministic replay assumptions.

Critical strengths

The paper provides a well-structured theoretical analysis with rigorous proofs. In particular, it establishes conditions for safely reusing equivalent execution traces and guarantees minimum-cardinality repair under the stated assumptions.

Critical weaknesses
  1. Limited conceptual novelty. The proposed method appears incremental, as its core idea is to exploit equivalence between memory-deletion candidates to avoid redundant executions. Similar ideas have been explored in prior program-repair research. For example, Mechtaev et al. [1] introduce test-equivalence classes to group repair candidates and reduce redundant test executions. The paper does not sufficiently clarify what distinguishes these contributions from existing equivalence-based repair techniques. Moreover, the theoretical guarantees rely on restrictive assumptions, such as deterministic replay and deletion-stable retrieval. The paper introduces numerous mathematical definitions, symbols, and theoretical bounds without sufficiently explaining the intuition behind each construction or its practical significance. While the overall idea is relatively straightforward, the extensive formalization makes the method unnecessarily difficult to follow.

  2. The experimental results do not clearly isolate the improvements attributable to the proposed equivalence mechanism. In particular, Table 19 shows that, with matched candidate ordering and request caching, canonical search requires the same number of LLM calls as general exact search (8.03 on average), although it reduces candidate evaluations from 10.61 to 8.03. This raises questions about the additional model-call savings provided by the proposed mechanism beyond standard request caching. Furthermore, the main comparison in Table 2 uses different candidate ordering strategies for WitRepair and Exact+cache, making it difficult to determine how much of the improvement comes from retrieval equivalence rather than the search heuristic. Although the controlled SQLite experiments demonstrate meaningful execution savings, they mainly rely on scripted deterministic controllers. Stronger evidence from realistic LLM-controlled multi-turn agents would help establish the practical benefits of the proposed method.

Reference

[1] Sergey Mechtaev, Xiang Gao, Shin Hwei Tan, and Abhik Roychoudhury. 2018. Test-Equivalence Analysis for Automatic Patch Generation. ACM Trans. Softw. Eng. Methodol. 27, 4, Article 15 (October 2018), 37 pages. https://doi.org/10.1145/3241980

Questions for authors
  1. What are the key technical contributions of retrieval equivalence and complete-trace guards beyond existing equivalence-based repair methods?

  2. Could the authors compare WitRepair and Exact+cache using the same candidate ordering and caching settings on ReAct–StrategyQA to isolate the efficiency gains from the proposed equivalence mechanism?

  3. How is the actionable memory set selected in practice, and how sensitive are the results to its size and composition?

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

The paper formalises post-incident repair of a poisoned agent memory as minimum-cardinality deletion over a declared actionable set A, subject to a replay predicate Φ. Its central observation is genuinely nice: under deletion-stable top-q retrieval, every deletion set that returns the same ordered context shares a unique minimum representative — the records skipped before the retrieval frontier — and evaluating that representative labels the whole class. Search in increasing cardinality; once the union of failed classes covers every set of size below k, a size-k success is a certified minimum. The single-read count Qcan(q,k) = C(q+k, k) and the certificate label count 1 + C(q+k−1, k−1) both check out arithmetically on every value in Table 5, and the canonical-representative argument (C_x(R) ⊆ R, |C_x(R)| = ℓ − q, hence every minimum repair is canonical) is correct and cleanly proved. The complete-trace extension with guards D_τ ⊆ R′, R′ ∩ S_τ = ∅ is also correct, and the opening-only counterexample in A.3 is a genuinely useful negative control.

Critical strengths

S1: The core combinatorial result is correct, and it is the right result. S2: The counting is right, and the paper checks it in two independent ways. S3: The accounting is honest, and the negative controls are real. S4: The internal arithmetic is consistent.

Critical weaknesses

The difficulty is that the paper's theory and its evaluation are about different things. The theory bounds the number of class-label queries needed; the experiments measure model calls, scripted executions, and wall-clock milliseconds. Once a full-request cache is present — which it is in every experiment — the cache already collapses two deletion sets that induce the same prompt into one entry. The paper says so itself: Proposition 2 concludes that with matched caches "both procedures incur the same sequence of full-request cache misses", and Table 19 shows 8.03 model calls for both general exact search and canonical search under matched order. So the mechanism the paper is built around contributes exactly zero model-call savings under matched conditions, and 10.61 → 8.03 candidate evaluations, a 1.3× reduction in local bookkeeping. The headline "19.0 → 13.5 fresh responses" (Table 2) therefore has to come from the candidate ordering heuristic, which is not part of the contribution and is never ablated.

Two further design choices remove the hard parts of the problem. The actionable set A is a pre-declared 12-record pool containing all six planted poisons — a 50% poison density, so localisation, which is the actual difficulty of memory repair, is assumed rather than solved. And each of the 200 tasks gets its own independent store copy, so deleting records to fix task i can never damage task j; collateral damage, the principal risk of deletion-based repair, is structurally unmeasurable in this design.

Questions for authors
  1. Given Proposition 2 (trace reuse does not change cache misses) and Table 19 (canonicalisation does not change model calls under matched order), what accounts for 19.0 → 13.5 responses in Table 2? Please report the ordering-only arm.
  2. If two deletion sets induce the same ordered context, do they not produce the same prompt and therefore the same full-request cache entry? If so, what does the equivalence class buy beyond avoiding the local rebuild-and-retrieve work?
  3. How is the 12-record actionable pool constructed in deployment, and what are the certified k and the cost when A = M at n = 1K and 100K?
  4. Since each task owns its store copy, how would you measure the collateral damage of a deletion that repairs incident i but removes a record task j depends on?
  5. Why does WITREPAIR leave 5.56% residual target output when deleting the entire store leaves 45.00%? What is the mechanism by which retaining 62 records suppresses the target below the no-memory floor?
  6. Can a third party verify a certificate without re-executing? What bytes does one contain, and how large is it?
  7. In the T-sweep, the trace bound exceeds the finite-store bound at every tested point (1,351 vs 1,351 at T = 10). Under what parameters is Theorem 3 non-vacuous, and do the observed savings follow from guard hits rather than the bound?
  8. Is the adversarial labelling in Theorem 2 realisable by any ranking-plus-predicate Φ? If not, is "tight" meant only inside the black-box relaxation?
Reviewer_a1dwOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes WitRepair, a mechanism for finding the smallest possible set of memory record deletions that avoids agent failure. Sometimes, deleting one memory surfaces another memory into the query results, which can lead to another failure.

The key idea is to group candidate repairs into equivalence classes for efficiency, and finding the smallest edit that allows the task to pass.

Critical strengths

The paper identifies what may be an important problem: simply deleting bad memories does not guarantee success, as each deletion risks bringing in another bad memory. Minimizing the size of the edit, and sharing work between sets both reduces complexity and minimizes the risk of further disruptions.

Critical weaknesses

While the paper is written up nicely by the LLM, the fundamental idea appears to be trivial. The gains over MemAudit (an apparent predecessor) are also small.

Questions for authors

Your approach targets poisoned memories, the fix to which is simply deleting them. It appears that you are doing this simply by enumerating the set of minimal edits until you have a successful result.

But what happens if deleting a good record can itself cause a failure? Does your algorithm work in this case? It seems like it would aggressively remove the entire memory once that happens, since the removal of one (good) element causes a failure, which would be blamed on the newly introduced element.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.