acceptodds
Under review as a conference paper at ICLR 2027

TRACE: Recall as Execution for Accountable Memory

Abstract

Agents that work across sessions must remember what matters, apply updates, and honor deletion and access requests; retrieved text cannot say whether a fact is still valid or permitted. We introduce TRACE, which implements Recall-as-Execution: each write records an operation (add, replace, delete), and each recall executes them to decide which facts hold at the requested time for the requesting principal. Every structured answer carries a certificate: the instructions it rests on and why each withheld fact was excluded. Temporal queries, forgetting and counterfactual replay are one call with a different time or ledger. We prove execution deterministic and grouping-independent, and check it against the deployed executor. On fixed ledgers all 659 recalls are admissible with no misuse, against 0.238–0.826 for a dense reader, and all 435 evaluated certificates verify, against 0.000 for baselines reporting no exclusions. On AutoMemoryBench, TRACE satisfies task success, safety and temporal validity together on 4.0% of cases, against at most 0.1% for any full-lifecycle vendor. A matched control locates the margin: folding the same operations into present state matches our admissibility, so the gain is in executing updates, not our format; but present state alone caps time-indexed queries at 0.333, where executing the ledger answers 1.000. Ablating supersession or governance collapses safety to 0.253 and 0.000 while task accuracy holds near 0.92: the result is in the execution semantics, not the backbone.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
agent memory, large language models, state transitions, memory admissibility, verifiable certificates

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_DVCSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the core challenges of long-term large-scale model agents in recognizing stale facts and failing to fully comply with deletion and access control in cross-session memory. However, key experiments revealed issues such as low task success rates and inconsistencies in some comparison protocols.

Critical strengths
  1. The paper points out the fundamental flaw of traditional RAGs in conflating relevance with admissibility and proposes a new paradigm of recall-as-execution.
  2. The paper proposes a relatively complete and unified memory execution framework, integrating memory writing, state updating, time querying into a single execution framework.
Critical weaknesses
  1. Section 4.2, Table 3, and Figure 3 show that TRACE performs exceptionally well in systems with an observable complete memory lifecycle, but the 4.0% task success rate indicates that its capabilities remain limited. Meanwhile, non-memory agent controls such as claude code and codex achieved higher absolute results in task success rate and StrictCore. Although the authors note that these systems are not direct controls with the same memory lifecycle, these results still limit TRACE's claims to practical applicability.
  2. The overall accuracy and compliance of the system described in the paper are highly vulnerable to the absolute precision of the front-end LLM compiler in parsing natural language semantics. In complex real-world dialogues, if the compiler misjudges operation types, misplaces entity relationships, or misses sensitive attributes, even if the execution engine runs perfectly, it will fall into the predicament of "garbage in, deterministic garbage out." The paper, however, merely simulates missing propositions by randomly discarding them, thus avoiding the fatal damage that such errors in understanding complex semantics can cause to the discrete state machine.
  3. The paper uses the “DELETE” instruction to perform logical deletion and designs the entire ledger as append-only. However, sensitive data after deletion remains in the original ledger, and other components can still potentially access this data as long as they can bypass the execution engine to access the underlying ledger.
  4. The paper points out that TRACE's main advantage over traditional RAG lies in its ability to handle memory updates, deletions, and temporal state changes. However, traditional similarity retrieval does not inherently perform these operations. Therefore, TRACE's superiority over Dense-RAG or Lexical-RAG only indicates that explicit state parsing is better suited for handling state update tasks than simple text retrieval; it does not sufficiently prove that TRACE's specific execution framework is superior to other structured state management schemes.
Questions for authors
  1. Despite TRACE's excellent lifecycle compliance, its absolute task success rate on AUTO MEMORY BENCH is only 4.0%. How do the authors explain the contradiction between this extremely low task completion rate and the actual effectiveness claimed by the proposed memory framework? Could the authors provide a detailed failure attribution analysis to clearly distinguish between memory compilation errors, recall failures, and downstream task execution failures?
  2. The current experiments primarily compare TRACE with retrieval methods or materialized state baselines that only store the latest state. Since the lack of historical versions itself leads to failed history queries, could the authors add versioned state management or event sourcing methods that also support time-based queries and access control? Compared to traditional state replay mechanisms, what are the unique advantages of TRACE?
  3. The paper mentions that TRACE uses logical deletion markers to achieve forgetting, but the original data remains in the immutable ledger. Furthermore, history replay could potentially recover subsequently deleted information. How do the authors prevent sensitive information from being re-exposed through historical or counterfactual queries? Can a deletion strategy that enforces deletion at all query times be evaluated, and the trade-off between this strategy and historical auditability analyzed?
Reviewer_udthOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes TRACE, which turns memory updates into typed operations and executes them to determine what information is valid and accessible at query time. It also returns supporting instructions and explanations for excluded information. I think the problem is important, but I’m not yet convinced that the experiments establish the benefit over existing stateful memory systems, or that the broader end-to-end claims follow from the executor-level results.

Critical strengths
  1. I really like the separation between retrieving relevant information and determining whether that information is still valid and permitted. Returning explanations for exclusions is a useful direction, particularly for deletion and changing permissions.

  2. There is substantial implementation checking, including tests against exhaustive slicing and deliberately corrupted certificates. The matched LongMemEval result, 78.2% versus 66.0% for dense RAG, is also encouraging. I appreciate that the appendices disclose several limitations and negative results.

Critical weaknesses
  1. The contribution beyond existing stateful memory is unclear. Table 1 already describes StateFuse as performing query-time state resolution, and §6 describes TRACE’s addition as the packaging of semantics, time/scope selection, and evidence into one interface. However, there is no quantitative comparison with StateFuse or MemTX. More importantly, the stateful reader in Table 19 matches TRACE’s present-time correctness and safety. Its historical-query deficit comes from retaining only the current state. Table 16 also shows identical results for eager and lazy execution. I think these results establish the value of resolving updates, but not the advantage of TRACE over a history-preserving stateful system. A comparison with the same compiled operations, historical information, and access rules would help isolate the contribution.

  2. The main results are difficult to interpret as evidence of superiority. Table 3 mixes LongMemEval configurations and vendor reports, while bolding TRACE’s 78.2% despite several higher numbers. Those numbers are not comparable, and even the displayed RAG baseline, 44.6%, is not the matched 66.0% baseline identified in Appendix A.2. I’d separate these results and put the matched comparison in the main table. The AutoMemoryBench “40×” gain also needs more diagnosis: TRACE reaches 4.0%, while the compared memory systems already fail almost all cases on task success alone. Appendix B.1 acknowledges that adapter, tool-call, and memory failures have not been separated. Without that breakdown, I can’t tell how much of the gap is due to memory semantics.

  3. The perfect scores establish narrower properties than the framing suggests. Fixed-ledger tests bypass natural-language compilation, and retrieval baselines receive zero certificate completeness because they do not emit exclusion reports. These are useful correctness and interface checks, but they don’t establish end-to-end reliability or superiority over a baseline implementing the same interface. This matters because the narrative fallback reintroduces unstructured content. Appendix E.4 reports that redaction fixes the tested literal-secret leakage, but also states that later deletions or permission changes do not retroactively scrub attached narratives. I’d like the safety claims evaluated through the complete answering pipeline, including this path.

also this is a side ppint but I believe almost all the paper's text is written by an LLM.

Questions for authors

What benefit remains over a stateful reader that retains historical versions and uses the same access rules? Can you isolate the contribution of the certificate mechanism against such a reader or StateFuse?

Can you provide a matched version of Table 3 and decompose AutoMemoryBench failures into tool/adapter failures, failed writes, failed retrieval, and incorrect state resolution? This would materially affect how I interpret the reported gains.

What happens when information already present in a narrative fallback is subsequently deleted or restricted? Can you report end-to-end leakage and task success for these cases, including compiler mistakes and final generated answers?

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

TRACE stores agent memory as an append-only log of typed updates written by an LLM compiler and stamped with event and recording times. Recall replays the log up to the query time, applies expiry and access rules, and returns a certificate.

Critical strengths
  1. The recall contract is precise enough to test. Specification 2 defines complete certificates, and the checker is not meaningful: it catches 500/500 dropped and 500/500 padded entries, and 478/478 removed exclusion reasons (App. D.4).

  2. A fair control shows where the gain actually comes from. A reader applying the same compiled updates to current state ties TRACE on present-time admissibility (only valid, permitted facts) on the 224 AutoMemoryBench probes but not on 100 synthetic past-state cases (0.333 vs. 1.000; Table 19).

Critical weaknesses
  1. The headline numbers mostly hold by construction, and the mechanism is already known. The fixed-log runs execute pre-typed logs without the compiler (App. A.2), so TRACE’s perfect Table 2 scores test only the executor.

  2. End to end, results are mixed and the baselines look unreliable. The clearest gain is LongMemEval. On AutoMemoryBench TRACE completes 4.0% of tasks, below all four memory-free agent controls (6.3-17.8%; Table 3). Its “forty times” lead on the joint task-safety-time criterion (Sec. 4.2) is over vendor systems at 0.1% or less, which App. B.1 also concedes could be adapter faults. On StructMemEval’s matched 49-item set, six systems tie at exactly 0.204 (Table 3), suggesting failed adapters.

Questions for authors
  1. (Clarification) Were the fixed logs of Table 2 and the Fig. 5 data (104 cases, 2184 queries) typed from benchmark annotations or by the compiler? Full TRACE reaches 0.921 task success there, versus 4.0% on AutoMemoryBench.

  2. (Clarification) How many AutoMemoryBench cases underlie the 4.0% (App. B.1 gives only 15,120 queries), and how many failures stem from a wrong resolved state rather than compilation, readout or the harness?

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

TRACE proposes a structured approach to long-term agent memory in which recall is executed over an append-only ledger of typed instructions. Updates, retractions, deletion, validity, and access scope are resolved before an answer is selected. The system also produces evidence identifying the instructions supporting an answer and the reasons other information was excluded. The paper evaluates the resulting recall behavior through fixed-ledger tests, certificate and governance tests, and end-to-end memory benchmarks. I view its main contribution as a coherent, inspectable interface for accountable recall, together with empirical evidence about its behavior, rather than a new underlying state primitive.

Critical strengths
  1. The paper addresses a consequential gap in persistent-agent memory: a relevant retrieved fact may no longer be valid or authorized for the current query. Resolving admissibility before answer selection, and reporting both supporting and excluded evidence, makes the proposed recall behavior substantially more inspectable.

  2. The evaluation includes useful controls beyond headline answer accuracy. In particular, the fixed-ledger setting isolates the reader from compilation errors, while matched comparisons, certificate perturbations, and reported weaker results help readers understand the mechanism’s benefits and limits. This makes the paper informative even where the broader end-to-end claims require qualification.

Critical weaknesses
  1. The described certificate construction is clearest for scalar answer targets. For a set-valued or aggregate answer depending on multiple ACCUMULATE instructions, it is not yet clear from the specification how the constructed slice retains every necessary dependency. Since certification is central to the contribution, the paper should establish the supported operator and projection coverage. I cannot determine from the manuscript alone whether this is an omitted implementation detail or a narrower supported interface.

  2. The narrative fallback path needs a clearer lifecycle guarantee. Redacting sensitive information when a narrative is attached does not, by itself, show what happens after a previously admissible fact is deleted or its access scope changes. This matters if the fallback path contributes to the reported utility while the paper presents governance as a property of the overall answering system. The structured-path evidence remains valuable, but these two scopes should be distinguished.

Questions for authors
  1. Could you show an example from the implemented certificate constructor in which two ACCUMULATE instructions contribute to one set-valued or aggregate answer? Which instructions appear in the slice, does the verifier accept it, and which operators and projections are covered by the reported certificate results?

  2. Which principal end-to-end results use narrative fallback? On that same answering path, what happens if a previously public narrative fact is subsequently deleted or made private? If the current guarantee applies only to structured recall or to a restricted fallback configuration, please state that boundary explicitly.

  3. Could you provide a concise configuration mapping for the principal utility and governance results, so that readers can identify which properties were demonstrated together under the same compiler, fallback, and verification settings?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.