acceptodds
Under review as a conference paper at ICLR 2027

When Does a Memory Descendant Need Repair? Structural Lineage vs. Stale State in Persistent Agent Memory

Abstract

Persistent LLM agents store conclusions that can remain active after their sources are corrected. We show that structural provenance fidelity and repair adequacy are different quantities. We distinguish structural descendants, descendants whose task value changes under an update, and descendants whose stored value is wrong afterward. In a controlled persistent-memory testbed with two LLM readers, material-support provenance covers about two-thirds of structural descendants at shallow depth and one-half at greater depth, while reaching at least 95% of stale stored state. Repair remains near oracle with fewer re-derivations. Matched-random provenance with the same edge budget and structural precision/recall reaches only about two-thirds of stale state. A second attributor improves structural fidelity while reaching the same stale state with more work. A symbolic value-agreement graph, retaining parents aligned with the stored conclusion, reproduces the LLM graph's selectivity. For unate rules and correct stored values, we prove that current-state value-agreement support reaches every update-sensitive descendant. Public multi-hop memory experiments show that persistent intermediates sharply lower post-update accuracy when they become invalid, with little change when they remain valid. These results establish stale-state coverage, repair work, and post-repair behavior as essential measures of provenance quality alongside structural fidelity.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
large language model agents, persistent memory, provenance, memory repair, stale state, agent evaluation

Reviews

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

This paper studies repair of derived memories after source corrections, distinguishing structural descendants, update-sensitive descendants, and stale stored states. In controlled experiments, LLM provenance reaches nearly all stale memories despite incomplete structural coverage, outperforming matched-random graphs. Value-agreement support reproduces this behavior and admits a reachability guarantee under stated assumptions. MemoryAgentBench experiments further show that stale intermediates harm subsequent answers.

Critical strengths
  1. The paper makes a useful distinction between provenance fidelity and repair adequacy. Equations (1)–(3) separate historical lineage, update sensitivity, and actual stored-state error. Accounting for reader errors is particularly valuable: a sensitive descendant may already contain the updated answer, while an insensitive descendant may remain incorrect. This provides a more precise evaluation framework than measuring structural edge recovery alone.
  2. Several complementary controls strengthen the interpretation. The value-agreement baseline offers a concrete explanation for the observed selectivity. The second attributor improves structural precision and recall while increasing recomputation without improving stale coverage. The content-removal and length-matched replacement experiments also help attribute behavioral degradation to stale content rather than merely additional context.
Critical weaknesses
  1. The controlled environment is narrow in ways that favor the proposed support criterion. All rules are unate, answers are binary, task rules are explicitly supplied, retrieval prioritizes required parents, and the depth sweep uses small chains. This is an effective diagnostic environment, but it does not reveal how robust the result is to ambiguous support, imperfect retrieval, larger branching graphs, or memories containing multiple claims. In particular, agreement of the final Boolean answer can conceal obsolete reasoning or supporting details, as the limitations section recognizes.
  2. Reduced re-derivation work is not yet evidence of reduced total cost. The reduction from roughly 8.2 to 5.9–6.0 re-derivations per episode is meaningful under the fixed operator, but the LLM provenance approach also requires attribution calls. Reporting attribution and repair tokens, latency, and total calls would clarify the practical tradeoff. The current results support savings in repair work specifically.
Questions for authors
  1. Does the value-agreement baseline retain near-oracle post-repair accuracy when run end to end with fresh generation and refreshed attribution?
  2. Can the authors establish sufficient conditions under which formation-time value-agreement edges remain adequate across sequential corrections?
  3. Can LLM attribution be evaluated on the public multi-hop setting, including stale coverage, structural coverage, and repair work?
  4. How were public evaluation units selected, and why do original and reversed orderings yield different unit counts? Are confidence intervals clustered sufficiently to account for any shared source streams?
1 comment
AuthorsOpenReview ↗

Response to Reviewer oR6d

We thank Reviewer oR6d for the thoughtful review of our three-set formulation and controls, and have added closed-loop runs, sequential-update theory, public LLM attribution, unit accounting, and cost analyses.

1. Value-agreement provenance under live regeneration and re-attribution

Yes. Paired values below are reported as Luna/DeepSeek. In closed-loop runs across D∈{1,3,5}D\in\{1,3,5\} (50 episodes/reader) regenerating answers and refreshing provenance at every repair, value-agreement provenance reached 0.97/1.00 stale coverage and 0.05/0.00 final probe errors (oracle: 0.02/0.00) while cutting re-derivations from 10.8/10.8 to 5.7/5.8. Its selectivity holds when repairs alter subsequent memory state (§5.5, Fig. 3, Table 16).

2. Sufficient conditions for formation-time edges across sequential updates

Proposition 2 (§3.4) proves this on a fixed structural DAG and fixed deterministic local rules over finite parent domains: (i) at formation, each node computes its value accurately from current parents; (ii) recorded edges contain a certificate forcing that stored value; and (iii) at each correction, reachable active nodes are invalidated, re-derived in topological order from the latest values of all required structural parents, and given a fresh certificate.

While certificate parents remain uninvalidated, they keep their formation values and force the stored output regardless of omitted parents; if any certificate parent changes, the node is reached, re-derived, and given a new certificate. By induction, across arbitrary sequential or simultaneous updates, all active memories match the task values of the current root assignment. On unate rules, formation-time value-agreement parents form a certificate (proof and 20,000-system checks/family: App. C, Table 8).

3. LLM attribution coverage and repair work on public multi-hop data

Replacing oracle path provenance on MemoryAgentBench with frozen deepseek-flash (§5.7), final accuracy over all evaluated units matched oracle repair in 7 of 8 conditions and was +0.015 higher (95% CI [0.000, 0.040]) in 1 (0.42–0.56 re-derivations/unit vs. 0.46–0.61 for oracle). Because 94–100% of structurally linked intermediates on these lookup paths change value after an upstream update, structural and stale coverage nearly coincided (0.75–0.98), showing the boundary case without redundant support (Fig. 5, Table 11).

4. Evaluation-unit selection, ordering denominators, and shared-fact dependence

A unit is a multi-hop question with a unique relation path whose pre-correction path is complete at the intermediate query step and differs from the post-correction path on at least one hop. Input order changes which questions have a complete pre-correction window before the update: in mh_6k, 4 questions lack a resolved path in both orders, while 29 (original) vs. 34 (reversed) lack a pre-correction window, giving 67 vs. 62 units (65 vs. 52 in mh_32k; App. D Table 10).

To handle shared facts within a stream, we group questions sharing any subject–relation key into connected components (30–46/split) and report component-clustered bootstrap 95% CIs alongside unit CIs (Table 10). Under component clustering, the write-back × validity interaction upper bound is < 0 in 7 of 8 conditions (primary mh_6k reversed: Luna [-0.62, -0.21], DeepSeek [-0.38, -0.09]); only mh_32k reversed DeepSeek (with a small point effect) touches zero at [-0.19, 0.00], noted in App. D.

5. Do fewer re-derivations mean lower total cost?

App. H (Table 20, pooled over D=1,…,5D=1,\dots,5) separates attribution and repair calls, tokens, and latency. Separate thinking-enabled deepseek-flash attribution uses around 102k/101k tokens/ep. (~12.5k for low-effort Luna), exceeding tokens saved on short Boolean repairs (2,104/2,537). Thus §§5.5 and 6 scope efficiency claims strictly to re-derivation work reduction (44–57%). Meanwhile, value-agreement and minimal-certificate provenance cut re-derivations without LLM attribution calls: minimal certificates lowered repair time/ep. from 20s to 9s (Luna) and 15s to 7s (DeepSeek), while edge logging added 1.8 ms CPU time and 384 bytes/ep.

6. Incomplete retrieval, wider graphs, and multi-claim memories

We added closed-loop runs on retrieval misses and wide branching graphs, and explained multi-claim handling in App. C. Dropping required parents at 25% degraded all methods including oracle repair (1.76/1.48 errors) and lowered LLM stale coverage to 0.80, confirming complete parent retrieval is needed (Table 17). On non-unate rules, value agreement dropped to 0.42/0.41 while minimal certificates and LLM provenance reached 0.99/1.00; on wide branching graphs (max fan-out 10), LLM provenance kept 1.00/1.00 stale coverage (Table 19). For multi-claim memories, App. C outlines per-claim certificates or retaining the union of component-claim certificates.

Reviewer_PkxgOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper analyzes the problem of stale agent memory. The problem is when the premise of conclusions in agent memory is changed, only the update-sensitive conclusions need to be changed but not all structurally descendent conclusions need to be updated. This paper classified all descendants to whether their value needs to be changed (update-sensitive) and whether the stored value is stale. The paper introduced a symbolic “value-agreement support” graph and proved the proposition that for unary boolean rules without error in stored values, the value-agreement edges are guaranteed to reach all update-sensitive descendants. The paper also runs experiments with ChatGPT Luna and DeepSeek Flash to verify with the graph, the agents can find most of the update-sensitive values and observe increase in accuracy after fact changed.

Critical strengths

The proved reachability of all update-sensitive descendants provides soundness of the proposed method

The problem identified that not all descendants need update is correctly identified

Critical weaknesses

Lack of distinction and empirical comparison with prior agent memory repair work

The related work section mentioned various important and closely-related prior work in agent memory repair (e.g., MEMOREPAIR, REVISE), but no comparison to describe what these prior work lacks and what this paper distinguishes from previous work. Lack of justifications of why not comparing with them makes it questionable whether this paper’s proposed solution is better than other methods.

Furthermore, in the evaluation section, this paper does not compare with existing work, making it unclear how good this paper can do compared with existing work.

Lack of attribution ablations

For critical hyperparameters used in this paper like retrieval budget K, district count, and false-positive rate of attribution edges, the paper lacks ablation study and sensitivity test. It is unclear how these parameters will influence the system’s performance and what are the assumptions and guarantee a real deployment of the system needs to support.

Gap between testbed scenario and real-world agent memory lacks discussion

The primary testbed is rather simple: binary attributes, deterministic boolean formulas, and clear YES/NO outputs. Real-world persistent agents usually face text descriptions, summaries, and high dimensional data which can’t be described as simple boolean and may include error. The proved proposition is also for boolean propositions without error. This presents a substantial gap between the test scenario and reality.

Questions for authors

How does the concept of “value-agreement support” behave when derived memory is not binary? Like if the fact to be changed is numeric value, text descriptions, or a set of values? Furthermore, when an upstream update partially update the memories’ value like add to a set or remove from a set, how should the method proposed to proceed?

Can you compare the reachability with existing agent memory repair systems? E.g., MEMOREPAIR. What are their performance on the same test scenario as yours?

Can you quantify the breakdown and root cause of failure modes for the cases that you do not achieve 100% reachability in empirical evaluations? Will change to a more powerful LLM model solve this discrepancy between experiment and theory (where the proposition claims 100% coverage)?

2 comments
AuthorsOpenReview ↗

Response to Reviewer Pkxg

We thank Reviewer Pkxg for the constructive feedback on prior repair policies, non-binary extensions, theory-vs-empirical gaps, and readability. The revision separates value sensitivity from stored-answer error in Fig. 1 and Eqs. (1)–(3), adds all requested comparisons and failure analyses, and reorganizes the paper.

1. Numeric, set, and text memories and partial updates

Beyond sign-based value agreement, Proposition 2 generalizes our condition to certificates—parent subsets forcing the stored output—for any deterministic function on finite parent domains. Across 20,000 simulated random systems per family including 3-valued numeric rules (maximum, sum-threshold; App. C, Table 8), certificate edges left 0/20,000 stale systems under single and simultaneous updates while cutting re-derivations (11.26 → 5.42 under single-root numeric updates). For functions like an exact sum where all parents are needed, zero edges are omissible and correctness holds.

App. C also outlines principles for set and multi-claim text memories: storing atomic claims separately lets per-claim certificates repair only claims tied to changed parents, whereas keeping multiple claims in one item requires retaining the union of their certificates (free-form summaries: future work, §7).

2. Comparison with MEMOREPAIR and prior repair policies

App. F (Tables 15–16) compares adapted prior policies in closed loop on identical episodes, readers, correction schedules, and re-derivation operators. Paired values below are reported as Luna/DeepSeek.

  • MEMOREPAIR and REVISE: Reachable-closure withdrawal/reposting (MEMOREPAIR, keeping 2,659/2,659 candidates at default λ=0.3\lambda=0.3) and read-dependency recomputation (REVISE) match oracle closure given full structural provenance (10.8 re-derivations, 0.02/0.00 probe errors). Under MEMOREPAIR's Leak% (1−Cstruct1-C_{\text{struct}}), our LLM graph appears to miss 44–45% of structural propagation, yet it repairs 97–100% of stale states with 0.05/0.00 error in 6.0 re-derivations.
  • Lenient Support check (dependency-rollback adaptation): Keeping a node whenever any parent is unaffected skips all nodes under single-root updates on conjunctive/threshold rules, giving 0.0 re-derivations and no-repair error (0.53/0.47).
  • Early-cutoff: Halting propagation on the full structural graph when a re-derived value is unchanged gives 0.04/0.00 error in 6.8/6.8 re-derivations—more work than minimal certificates (4.6/4.7) or value agreement (5.7/5.8), since all direct children of a changed node must still be re-evaluated first.

Full closure over-repairs and single-parent retention fails on logical rules, while certificate provenance captures stale states with fewer re-derivations.

3. Sensitivity to retrieval budget, distractors, and noisy edges

In closed-loop sweeps (App. G, Fig. 12, Tables 17–18), LLM and value-agreement stale coverage stayed at 0.97–1.00 across L2 budgets K∈{2,4,8,16}K\in\{2,4,8,16\} and {0,4,8,12}\{0,4,8,12\} distractors. Dropping required parents at 25% (pmiss=0.25p_{\text{miss}}=0.25) caused even oracle repair to incur 1.76/1.48 errors and lowered LLM stale coverage to 0.80, confirming complete parent retrieval is needed during re-derivation. Adding false-positive edges kept coverage at 1.00 while raising re-derivations (10.0 → 13.5–18.1); randomly dropping true edges lowered certificate containment and reduced coverage accordingly (Fig. 3C).

4. Causes of <100% empirical coverage and stronger-model checks

App. I (Table 21) separates Assumption (i) (local calculation correctness) from Assumption (ii) (conditional certificate containment among correct local calculations). On unate rules, value-agreement and minimal certificates reach 100% conditional certificate containment on both readers. Under LLM provenance on Luna, all 16 missed stale pairs (11 written wrong at formation, 5 inherited from a wrong ancestor) and all 9 residual stale states (4 + 5) come from low-effort Luna's 21 local calculation errors (2,070/2,091 = 99.00%). Among correct local calculations, LLM attribution omitted a certificate once on Luna (99.95%) and 4 times on DeepSeek (99.81%), causing 0 missed stale pairs in the observed update sequences.

Re-querying the 10 unique failing reader prompts with high-effort Luna or gpt-5.6-terra gave 10/10 correct answers in both cases (26/30 over 3 low-effort resamples), and re-attributing the 3 certificate-omitting replay states with gpt-5.6-terra recovered valid certificates in 3/3 cases—pinpointing the source of the small gap to 100%.

5. Readability and organization

We added a notation table (Table 2) and experiment roadmap (Table 3) linked in §§3–4, replaced codes (OFF, S0, S4) with descriptive names (no write-back, keep-stale, closure invalidation), and reordered §5 so controlled runs (§§5.1–5.5) precede the public benchmark (§§5.6–5.7).

Reviewer_PkxgOpenReview ↗

Prior-policy comparisons and failure analysis address my main concerns

I’m raising my score to weak accept. The authors now compare adapted MEMOREPAIR and REVISE policies on the same episodes and show that selective repair reaches 97–100% of stale states with 6.0 re-derivations per episode, compared with 10.8 for full dependency repair. The retrieval and edge-error ablations clarify when that benefit holds. I also found the failure analysis persuasive: the authors traced all 16 missed stale pairs on Luna to errors in the stored calculations, including errors inherited from earlier memories.

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

This paper proposes a causal auditing framework for persistent agent memory in order to address the divergence between structural derivation lineage and actual repair necessity when upstream source facts are modified in evolving LLM memories. The key ideas include (1) formally decoupling historical structural descendants from audit-time update-sensitive descendants and genuinely stale stored states, (2) demonstrating that material-support attribution mirrors a symbolic value-agreement graph that provably reaches stale descendants while pruning redundant re-derivations, and (3) adopting stale-state coverage, computational repair cost, and post-repair task behavior as primary metrics for provenance quality with structural fidelity. Evaluation on controlled persistent-memory lifecycles and public multi-hop memory benchmarks shows promising stale-state repair coverage, reduced re-derivation overhead, and substantial recovery of post-update downstream behavioral accuracy.

Critical strengths

The paper separates historical derivation lineage from genuine state staleness in persistent agent memory architectures, and provides a scheme that prevents wasteful re-computation cascades.

The paper bridges empirical agent attribution with truth-maintenance theory through value-agreement support graphs that capture decisive causal dependencies.

Critical weaknesses

However, a few concerns that I have with the paper including:

First, the theoretical guarantees relies on the assumtion of unate update functions, which actually rarely holds in practical ML workflows. Real agent interactions involve defeasible reasoning and non-monotonic updates where new evidence can cancel or modify existing beliefs arbitrarily. As a result, the paper seems to provide limited insight on realistic agentic systems.

Second, the evaluation relies on created micro-benchmarks with shallow dependency chains rather than representative behaviors of domain workloads. Real-world tasks such as software development and enterprise customer service typically have intricate multi-hop dependancies and cross-agent sharing that are not studied in the paper. As a result, the reported efficiency gains in descendant repair may not generalize to realistic, large-scale graph lineages.

Third, the methodology assumes an idealized external oracle, which detects corrupted roots and supplies perfect corrections at fixed intervals. In production agent architectures these days, identifying faulty memory items is an endogenous, noisy process plagued by hallucination and partial observability. Without tested under imperfect, agent-driven error discovery, how practical ability of the proposed lineage tracking remains unclear.

Finally, the paper performs offline graph analysis on frozen execution episodes instead of using a dynamic runtime maintenance protocol. Deploying such fine-grained dependency tracking inside a running multi-agent platform can introduce significant synchronization delays, metadata bloat, and memory overhead that are not considered in the paper. Without an end-to-end systems characterization under continuous execution, it is hard to determine the actual operational cost of the approach.

Questions for authors
  1. Could you clarify whether root memory corruptions and corrections in the evaluation are identified by an automated omniscient oracle or through manual human annotation?
  2. In the evaluated benchmarks, what are the maximum path depth and branching factor observed across the recorded memory dependency graphs?
  3. How frequently do non-unate update rules occur in the natural language experiments, and what proportion of structurally reachable descendants remain semantically unaffected under them?
  4. What is the runtime latency and storage overhead incurred by logging fine-grained dependency edges compared to uninstrumented agent execution?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 8e4G

We thank Reviewer 8e4G for raising important questions on practical generalization and operational cost. In the revision, we clarify how corrections arrive, report observed graph scale statistics, and add closed-loop experiments on non-unate rules, wide branching graphs, and runtime/token costs.

1. How are wrong root memories and corrections identified?

In the controlled testbed, the episode generator holds ground-truth root facts, injects opposite values into 6 of 24 roots per episode, and programmatically audits each corrupted root 20 steps after arrival to replace it with its true value. On MemoryAgentBench, a later fact in the stream with the same subject–relation key serves programmatically as an update to the earlier value. Neither setting uses manual human adjudication; our study focuses on how to propagate and repair downstream derived memories once a correction arrives (§4.1, §7, Apps. A & D).

2. What are the depths and branching scales of the evaluated graphs?

Appendix E (Table 14) summarizes the observed graph dimensions (public multi-hop paths have max depth 3 and max fan-in 3):

Controlled settingMax depthMax parents (mean)Max children (mean)
Depth sweep (D=1D=1–55)54 (3.24)6 (1.83)
Non-unate rules24 (3.20)4 (1.78)
Wide branching graphs44 (3.30)10 (2.35)

Paired values below are reported as Luna/DeepSeek. In new closed-loop runs on wide branching graphs (depth 4, shared parents, max fan-out 10), LLM provenance reached 1.00 stale-state coverage on both readers while visiting only 0.49 of structural descendants and cutting re-derivations in half vs. oracle closure (25.8 → 12.5/12.6). Matched random reached 0.60/0.59 stale coverage (0.64/0.60 probe errors vs. 0.08/0.00 for LLM), maintaining the advantage of selective provenance on wide branching graphs (App. G, Fig. 13, Table 19; multi-agent shared memory is noted as future work in §7).

3. Do the results hold when unateness fails, and how often does that arise in natural language?

The revision separates Proposition 1 (for value agreement) from Proposition 2 (for general rules). Proposition 2 applies to a fixed dependency graph and fixed deterministic local rules over finite parent domains without requiring unateness: when local calculations at formation are exact and incoming edges contain a certificate forcing the stored value, topological re-derivation using all required structural parents with fresh certificate refresh preserves consistency across sequential and simultaneous corrections.

In closed-loop experiments on non-unate rules (parity, exactly-two-of-four, XOR), value-agreement stale coverage dropped to 0.42/0.41 (1.46/1.38 probe errors) as predicted, whereas minimal-certificate and LLM provenance retained broader parent sets (LLM structural coverage 0.84/0.85 vs. 0.40/0.39 for value agreement) and both achieved 0.99/1.00 stale coverage with near-oracle probe error (0.08/0.00 and 0.14/0.02 vs. oracle 0.12/0.00).

We did not tabulate the frequency of non-unate rules in natural language. What the public experiments measured is the fraction of structurally connected intermediates whose ground-truth value changed after an upstream correction (94–100%). Repair performance on non-unate rules was evaluated via controlled experiments with parity and XOR (§3.4, Apps. C & G, Tables 8 & 19).

4. What are the latency and storage overheads of provenance tracking in continuous execution?

Appendix H (Table 20) reports attribution and repair calls, tokens, and latency pooled across D=1,…,5D=1,\dots,5 (10.6 oracle re-derivations/ep. over all five depths vs. 10.8 on D∈{1,3,5}D\in\{1,3,5\} in Table 16).

Calling a separate external LLM attributor at each formation uses 13.9/14.0 calls/ep. (~102k/101k tokens, 321/315s for thinking-enabled deepseek-flash; ~12.5k tokens, 58s for low-effort gpt-5.6-luna), exceeding the tokens saved in repairing short Boolean prompts (2,104/2,537 tokens; repair time 20/15s → 12/8s). We therefore separate re-derivation work reduction (44–57%) from external attribution token cost. Meanwhile, value-agreement and minimal-certificate provenance reduced re-derivations without LLM attribution calls: minimal certificates lowered per-episode repair time from 20s to 9s on Luna and from 15s to 7s on DeepSeek, while recording edges added 1.8 ms of CPU time and 384 bytes of storage per episode.

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

This paper distinguishes structural dependency, update sensitivity, and actual staleness in persistent agent memory. In controlled experiments, LLM-generated provenance reaches at least 95% of stale states despite recovering substantially fewer structural descendants. Matched graph controls and a symbolic support rule help explain this selectivity, while public memory experiments show the behavioral harm of retaining invalid intermediates. I recommend weak acceptance: the evaluation distinction is useful and supported by informative controls, although validation of automatically generated provenance remains concentrated in the synthetic setting.

Critical strengths

The distinction between changed task values and incorrect stored answers is important. It accounts for reader errors that ordinary dependency tracking overlooks, including stored answers that remain wrong despite an update leaving the task value unchanged. This provides a clearer basis for evaluating what repair actually accomplishes.

The controlled comparisons convincingly show why edge-level scores alone are insufficient. Matched-random graphs preserve edge counts, precision, and recall yet reach substantially less stale state. The second attributor and value-agreement control further explain the result: recovering additional dependencies can increase recomputation without improving repair coverage.

Critical weaknesses

The public benchmark validates the harm of stale intermediates, but not the effectiveness of LLM-generated provenance. Its repair conditions use oracle path support. Consequently, the central finding about selective, near-oracle repair still rests on 50 synthetic episodes with explicit Boolean rules. Evaluating the same attributor on the public tasks would substantially strengthen the practical case.

The graph-only controls replay logged formations without regenerating reader answers. This cleanly isolates reachability on a shared history, but does not establish how the competing graphs behave when their repairs change subsequent answers, stored values, and dependencies. A smaller end-to-end comparison of matched-random, value-agreement, and LLM provenance would help establish whether their ordering survives this feedback.

Questions for authors

How does the material-support attributor perform on MemoryAgentBench when it replaces oracle path support, measured by post-repair accuracy and repair work?

Which reported repair comparisons regenerate answers and dependencies after each intervention? Do the main differences between graph representations persist in those end-to-end runs?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 6jrD

We thank Reviewer 6jrD for the positive assessment of our distinction between structural dependency and actual repair need and of our controlled comparisons. We have added the requested LLM attribution evaluation on public data and end-to-end closed-loop comparisons with live regeneration.

1. Can LLM provenance replace oracle path provenance on MemoryAgentBench?

Across all eight MemoryAgentBench conditions—combining two context lengths (6k, 32k), original vs. reversed ordering, and two readers—we replaced oracle path provenance with our frozen deepseek-flash attributor, which sees only the stored intermediate conclusion, the question, and candidate memories available at formation.

Aggregated over all evaluated units (both valid and invalidated intermediates), final post-repair accuracy under LLM provenance equaled oracle path repair in 7 of 8 conditions and was 0.015 higher in the remaining condition (component-clustered bootstrap 95% CI [0.000, 0.040]). Edge precision was 0.97–1.00, recall was 0.88–0.96, and re-derivations per unit were 0.42–0.56 under LLM provenance vs. 0.46–0.61 under oracle path provenance.

On these public lookup paths, structural coverage and stale-state coverage also nearly coincided at 0.75–0.98 (identical in 6 conditions; differing by 0.01–0.03 in 2). Unlike logical rules with redundant support, every hop along an active single-path lookup is essential. These results confirm both that LLM attribution effectively replaces oracle path provenance and that the work savings of selective repair depend on support redundancy in the task (§5.7, Fig. 5, Table 11).

2. Do differences across provenance representations persist when answers and dependencies are regenerated live?

Whereas §5.4 compared pure graph reachability on fixed formation histories, our new §5.5 runs live closed-loop comparisons across depths D∈{1,3,5}D\in\{1,3,5\} and 50 episodes per reader. At each correction, invalidated nodes are recomputed by the reader LLM and re-attributed live, and the updated memory state feeds into all subsequent corrections and probes. Paired values below are reported as Luna/DeepSeek.

ProvenanceRe-derivations / ep.Stale coverageFinal probe errors / ep.
Oracle structural10.8 / 10.81.00 / 1.000.02 / 0.00
LLM material-support6.0 / 6.00.97 / 1.000.05 / 0.00
Value-agreement5.7 / 5.80.97 / 1.000.05 / 0.00
Minimal certificate4.6 / 4.70.98 / 1.000.04 / 0.00
Rule-based but-for2.8 / 2.70.83 / 0.830.14 / 0.12
Matched random6.6 / 6.70.64 / 0.660.21 / 0.19

LLM, value-agreement, and minimal-certificate provenance retain near-oracle final probe error while cutting re-derivations by 44–57%. Fixed-history replay isolated parent selection under matched edge count, precision, and recall; in closed-loop execution with live regeneration, matched-random stale-state coverage remained at 0.64/0.66, preserving its separation from LLM provenance (§5.5, Fig. 3, Table 16).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and New Experiments

We thank all four reviewers for their careful and constructive feedback. A central question across the reviews was whether the separation between structural lineage and actual repair need holds beyond fixed-history replays and unate binary rules. In the revised manuscript, we address every question through new experiments, a generalized theoretical result, and a reorganized presentation:

  • LLM attribution on the public multi-hop benchmark (§5.7, Fig. 5, Table 11): Across all eight MemoryAgentBench conditions, we replaced oracle path provenance with a frozen LLM attributor (deepseek-flash). LLM-attributed repair matched oracle path repair in final accuracy on 7 of 8 conditions (and was slightly higher on the remaining condition), while structural and stale-state coverage nearly coincided on these single-path lookups where every hop is essential—showing that the work savings of selective repair depend on support redundancy in the task.
  • End-to-end closed-loop execution across all conditions (§5.5, Fig. 3, Table 16): Beyond fixed-history replays, we ran end-to-end closed-loop evaluations where invalidated nodes are regenerated live by the reader LLM and re-attributed at every correction. Even when repairs dynamically alter subsequent memories and dependencies, certificate, value-agreement, and LLM provenance maintain near-oracle post-repair accuracy while substantially reducing re-derivation work.
  • Certificate theory for sequential/simultaneous updates and general rules (§3.4 Proposition 2, Apps. C & G, Tables 8 & 19): Over a fixed dependency graph, we prove that when local calculations are exact and each formation records a certificate, topological re-derivation using all required parents together with certificate refresh keeps active memories consistent across sequential and simultaneous corrections. This guarantee applies to deterministic rules over finite domains beyond unate functions, and is validated via multi-family simulations and closed-loop experiments on non-unate rules (e.g., parity, XOR) and wide branching graphs.
  • Prior-policy comparisons, cost/failure accounting, and readability overhaul (Apps. A, F–I): We adapted MEMOREPAIR, REVISE, a lenient support check, and early-cutoff into the same closed-loop testbed; added sensitivity sweeps over retrieval and edge errors; separated attribution cost from repair cost; and decomposed reader local calculation errors vs. certificate omissions. We also added a notation summary (Table 2) and an experiment roadmap (Table 3), and reorganized the exposition and section structure for readability.

Detailed responses to each reviewer's questions follow in individual replies.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.