acceptodds
Under review as a conference paper at ICLR 2027

Beyond Recall: Compiling Experience into Executable Memory for LLM Agents

Abstract

Long-horizon LLM agents must turn noisy, sparse-reward trajectories into reusable experience, yet complete trajectories retain incidental actions and summaries can omit execution conditions. We introduce Trace, which compiles executable Walk-through Memory with a fixed Actor: delayed credit identifies candidate preparation, cross-episode outcomes yield candidate prerequisites, and backward slicing links target facts to observed producers. Entry conditions, expected effects, and termination predicates support state-conditioned scheduling, monitoring, and resumption. Across WebShop, J-TTL, and ScienceWorld with three LLM backbones under episode resets, Trace outperforms eight baselines in AUC and Final-3. Relative gains over the strongest baseline in benchmark-averaged AUC and Final-3 average 30.9% and 41.6% across backbones. Ablations show complementary gains from dependency-grounded construction, executable representation, and prerequisite-aware scheduling.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
agents

Reviews

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

This paper proposes Trace, a framework that converts noisy, sparse-reward agent trajectories into executable, reusable memories for long-horizon LLM agents. Trace combines three key components: (1) progress anchoring and delayed credit assignment to identify useful actions, (2) prerequisite estimation to infer dependencies between actions and environmental states, and (3) backward dependency slicing to compile relevant actions into structured walkthroughs. A state-aware scheduler then selects and executes these walkthroughs across episodes using a frozen LLM actor. Experiments on WebShop, J-TTL, and ScienceWorld with three LLM backbones report average relative improvements of 30.9% in AUC and 41.6% in Final-3 performance over the strongest baselines. Ablation and robustness studies further examine the contributions of individual components and their resilience to noisy trajectories and execution perturbations.

Critical strengths

The overall research problem is the online learning ability of the agent, which is very important. The experiments have been done are very sufficient.

Critical weaknesses
  1. There is a little concern about the effect, which is written in the question.
  2. The baseline methods, or the cited paper, is not officially implemented on the three benchmarks used in this paper. That is to say, the author himself re-adapted the methods of other papers on the benchmark they chose. There is no evidence that they reproduce successfully, and each paper is targeted on the benchmark of their choice, which means that the results are not very credible.
  3. The description of the paper, including the drawing of the chart. It seems that llm participates too much, which is not a problem, but the table and chart contain too many numbers or information, which is easy to make human readers lack focus.
Questions for authors

I need the following results to consider improving my score.

  1. On the benchmark used in the baseline paper, the fair comparison under the same model and setting
  2. The result of trace when the number of episodes is k, compared with the results of best-of-k and pass@k
Reviewer_bfBEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Trace, a test-time memory-construction method for long-horizon LLM agents that keeps the Actor (LLM) frozen and updates an external "Walkthrough Memory" with a deterministic, non-LLM Evolver across repeated episodes of the same task. Construction has three stages: (1) progress anchoring plus delayed credit, which parses observations into canonical facts, marks hard/discovery anchors, and propagates discounted credit backward to score unrewarded preparatory actions; (2) prerequisite estimation, which scores each (fact, action) pair by a smoothed cross-episode success gap Nec(f,a)=P(success|a,f=1)−P(success|a,f=0) and admits facts above a threshold with minimum support; and (3) backward dependency slicing, which traces anchor completion facts to their nearest observed producers and compiles ordered precondition–action–effect steps with completion/failure predicates. A state-conditioned scheduler checks Walkthrough eligibility after resets, values preparation via local plus DAG-discounted downstream progress with Thompson-style selection, and monitors/resumes execution. Evaluation covers WebShop, J-TTL, and ScienceWorld with three open backbones (Qwen3-32B, Mistral-Small-3.2-24B, GPT-OSS-20B) against eight baselines over 50 episodes. The headline claims are benchmark-averaged relative gains over the strongest per-block baseline of 30.9% (AUC) and 41.6% (Final-3) averaged across backbones, at lower token cost, supported by a nested construction ablation, a representation/scheduling case study, and offline/online robustness studies.

Critical strengths
  1. Deterministic construction with a genuine efficiency result. The Evolver uses parsing, state differencing, prerequisite scoring, and slicing with no backbone calls, so memory construction adds no LLM-token cost. Table 7 and Figure 2 show Trace matching or beating the best baseline on performance while consuming fewer tokens than Memory, Summary, Reflexion, EvoTest, ACE, and APEX on all three benchmarks. This is the most compelling part of the paper: it decouples "better memory" from "more inference spend," which is a real and useful property and is not the usual free lunch in this literature.

  2. Breadth of evaluation and candor about scope. Three benchmarks × three backbones × eight baselines, plus nested ablation, a representation/scheduling decomposition (Fig. 3), progress-signal masking, sample-efficiency, trajectory-noise, and single-source online-perturbation studies, is above the norm for this subfield. The paper is also unusually honest that prerequisites are observational rather than causal and that slicing guarantees neither minimality nor completeness. This candor makes the empirical story easier to trust where it does hold.

Critical weaknesses
  1. The headline gains are reported without any variance and in a framing that inflates them. The main tables (Table 1) give point estimates over three seeds with no standard deviations, confidence intervals, or significance tests, yet the abstract's central numbers (30.9%/41.6%, and 80.9%/178.5% on J-TTL) are relative gains computed against the strongest baseline selected per backbone×benchmark cell. Selecting the per-cell max baseline and then dividing by it introduces selection bias, and several denominators are tiny or unstable (e.g., ScienceWorld/Qwen3 Memory AUC is −0.0273; J-TTL baselines are small), so the relative figures are dominated by a few favorable cells. Concretely, some of the "wins" are within plausible seed noise: WebShop/Qwen3 AUC is 0.5421 (Trace) vs 0.5403 (Memory), and J-TTL/Qwen3 AUC is 0.2410 vs Reflexion 0.2380 — a 1.3% gain, while the much-advertised "most pronounced on J-TTL" effect is carried almost entirely by GPT-OSS-20B, where the best baseline is weak (0.1375). Without variance and with absolute-difference reporting as the primary comparison, I cannot presently distinguish a robust improvement from favorable aggregation. This is consequential because it bears directly on whether the main claim is supported.

  2. The central novelty — "dependency-grounded" construction — is never validated against ground truth. Nec(f,a) is a purely correlational success gap, admitted at τpre=0.25 with nmin=2 present and 2 absent observations and α=0.5 smoothing; with only two samples per group, the Jeffreys prior dominates the estimate, so a "prerequisite" can be asserted on very thin evidence (coverage is only 27.7%/31.9%/33.8% of candidate pairs, App. C.1). The paper's own PV metric is explicitly an execution-consistency diagnostic, "not a precision estimate against ground-truth prerequisite relations." ScienceWorld and WebShop have known task structure, so a gold-prerequisite precision/recall evaluation is feasible and would directly test the claim that Trace recovers real dependencies rather than a well-tuned heuristic that correlates with success. Its absence leaves the paper's distinguishing contribution unsubstantiated, and makes it impossible to attribute the gains to the specific Nec estimator versus any reasonable dependency signal (there is no ablation comparing Nec against, e.g., plain temporal precedence or an LLM-judged prerequisite).

Questions for authors
  1. Can you report per-seed means with standard deviations (or CIs) for every cell of Table 1, and provide the raw absolute-difference comparisons against the single best overall baseline rather than per-cell max? For the near-ties (WebShop/Qwen3; J-TTL/Qwen3 AUC), are the differences significant across seeds? (Clarification — materially affects whether the main claim holds.)

  2. For ScienceWorld and WebShop, where structured state is available, what is the precision/recall of the inferred prerequisite set against ground-truth prerequisites? (Clarification — directly tests the core "dependency-grounded" claim.)

  3. How sensitive are the results to τpre and nmin? Given nmin=2 and α=0.5, a sweep over nmin∈{2,5,10} and τpre∈{0.1,…,0.4} would show whether the prerequisite estimator is stable or operating in a high-variance regime. (Clarification.)

  4. Were any hyperparameters (progress weights, γ, γW, τpre, nmin) selected on a held-out split? "Fixed before evaluation" is stated, but no validation procedure is described. (Clarification.)

  5. Appendix C.1 and C.2 are written prospectively ("the final reproducibility package should report…", "the final experimental report should quantify…") while also giving concrete numbers. Are the coverage, parser-accuracy, and field-masking numbers measured results from this submission, or planned? (Clarification — affects how much weight the diagnostics carry.)

  6. The deterministic Evolver depends on benchmark-specific parsers, regexes, and object lexicons (parser EM 0.87–0.91). Does the token-cost comparison implicitly shift bespoke, per-benchmark engineering cost off-budget relative to LLM-based baselines, and how would the method behave in an environment without reliable state fields? (Clarification — bears on the generality and the fairness of the efficiency claim.)

  7. Robustness and online-perturbation studies are restricted to GPT-OSS-20B and often two benchmarks. Do the construction-noise and recovery results hold on the larger backbones? (Clarification.)

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

This paper proposes a method for turning unstructured experience into executable memory that guides a frozen actor. The pipeline uses benchmark-specific parsers (without LLMs) to convert observations into typed facts. They show gains on three benchmarks and three LLM backbones.

Critical strengths

The idea of an executable memory is interesting and likely useful in many domains.

Critical weaknesses

My main concern is that it's hard to attribute the reported gains to the method because only Trace gets a hand-engineered parser layer. The ablation in Table 2 is troubling because even the weakest ablation, with all three stages off, already beats every J-TTL baseline.

Questions for authors
  • Do any baselines condition on the shaped signals that Trace uses? If not, what supports attributing the gains to the construction stages rather than the hand-designed state information?
  • How much per-environment engineering does porting this method to a new benchmark require? Are there environments that wouldn't admit such a clean, structured state?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.