acceptodds
Under review as a conference paper at ICLR 2027

Trajectories as Programs: Verified Replay and State Recovery for LLM Agents

Abstract

Large language model (LLM) agents are typically given multiple attempts at the same task. A failed attempt has often already completed part of the task. To reuse past attempts, existing methods turn them into text and ask the model to regenerate the actions from the initial state. The regenerated actions may be different from the original ones, so text cannot bring the task exactly back to a state the previous attempt reached, and the completed part cannot be kept. To address this problem, we propose Trajectories as Programs (TaP), a training-free framework that stores each attempt as an executable program, so a new attempt can start exactly where the completed part ends instead of regenerating everything from text. To decide where a new attempt should start, we introduce Verified State Localization: it replays the program of a failed attempt and keeps the states that have verifiably completed part of the task as recovery points. But recovery points are not equally useful, and attempts are limited. To spend the limited attempts on the recovery points most likely to solve the task, we introduce Probe-Guided Attempt Allocation: cheap probes first judge which recovery points can leave the old failed path and make new progress, and full attempts go to the most promising recovery points. Once a task is solved, TaP replays its verified program directly instead of calling the model, so the task stays solved and every new attempt goes to the tasks that are still unsolved. Across AppWorld and BFCL-V3 and across model sizes, Tap sets a new state of the art on both metrics: it solves more tasks per attempt on average, and solves more tasks at least once over all attempts, than all baselines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, experience reuse, test-time search, agent memory, AppWorld, BFCL

Reviews

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

This paper proposes Trajectories as Programs (TaP), a framework for reusing LLM agent experience in resettable, deterministic environments. For failed trajectories, TaP replays recorded action prefixes and evaluates task progress to identify recovery points, then uses short probes and adaptive attempt allocation to generate continuations. For successful trajectories, it produces verified, pruned programs that can be replayed directly, avoiding regressions caused by regenerating actions. The paper evaluates the framework on AppWorld and BFCL-V3 using multiple models, component ablations, and budget-matched comparisons.

Critical strengths
  1. The method addresses a clear problem and offers a practically useful design.

    The paper distinguishes two needs in experience reuse: preserving successful behavior and retaining useful progress from failed attempts. Executable trajectory records reduce reliance on the model to regenerate previous actions faithfully. Restoring both the environment state and the corresponding context also provides a well-defined starting point for continuation. Recovery-point selection, probe-guided allocation, and verified replay form a coherent framework.

  2. The experiments support the effectiveness of the overall framework under the studied conditions.

    Table 1 reports improvements in both Avg@4 and Pass@4 across two benchmarks and multiple model configurations. For example, with Qwen3-8B on AppWorld, TaP improves Avg@4 from 24.70 to 34.47 and Pass@4 from 42.06 to 48.02 over dynamic ReMe. Improvements in both metrics indicate that the gains include solving more tasks, beyond preserving previously achieved success. The budget-matched comparisons further suggest that the advantage over the tested baselines cannot be explained simply by additional model calls.

  3. The component analyses help explain where the gains come from.

    Figure 4 compares textual summaries, verbatim transcripts, and executable replay of the same successful experience, directly demonstrating that regeneration can lose previously verified behavior. Table 2 examines replay, recovery-point localization, probing, and attempt allocation separately. Removing state localization reduces Avg@4 by 2.43 and 3.55 percentage points on the two benchmarks. Section 4.5 further examines how the benefits of probing and allocation vary with the search budget, helping clarify when these components are most useful.

Critical weaknesses
  1. The budget-matched comparison does not fully separate the benefits of state recovery from those of budget reallocation.

    In Table A4, the baselines continue attempting already-solved tasks, whereas TaP concentrates additional search on unsolved tasks. The observed gap may therefore reflect both intermediate-state recovery and differences in budget allocation. Would TaP retain its advantage if the baselines also preserved successful solutions and redirected the remaining budget to unsolved tasks? Alternatively, do existing control experiments show that intermediate-state recovery provides additional benefits beyond budget reallocation?

  2. It is unclear whether the text-only control changes only how trajectories are reused.

    Table 2 compares TaP with text-only experience, but it is not clear whether this variant retains the same recovery-point selection, probing, and attempt-allocation rules, replacing only program replay with re-execution based on textual records. If these search rules also change, the performance gap cannot be attributed specifically to accurate restoration of previous states rather than differences in search strategy.

  3. The distinction from prior recovery methods should be made more explicit.

    RePoT: Recoverable Program-of-Thought via Checkpoint Repair already preserves valid prefixes through verified replay and repairs suffixes from verified states. The paper should clarify its additional contributions in recovery-point selection, probe-guided allocation, and reuse of successful programs across evaluation passes. This is primarily a related-work positioning issue and does not independently justify rejection.

Questions for authors
  1. Is there a control that separates the benefits of intermediate-state recovery from those of budget reallocation?

    For example, a baseline could preserve successful solutions and spend the remaining budget only on unsolved tasks, allowing a comparison between restarting from the initial state and using TaP. Other existing experiments that distinguish these two effects would also be helpful.

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

TaP reuses LLM-agent trajectories as executable programs. It identifies recovery points where a failed attempt has made verified progress, uses short probes to decide where to continue, and saves successful programs for later replay. The method requires resettable, deterministic environments and a partial-progress checker. Experiments on AppWorld and BFCL-V3 show improvements over the evaluated memory baselines.

Critical strengths
  1. The method addresses a useful problem: repeated attempts often discard work that was already done correctly. TaP offers a practical way to preserve that progress and continue from it without changing model parameters.
  2. The experimental gains are substantial across models and both benchmarks. The budget-matched results are particularly helpful: on AppWorld with Qwen3-8B, TaP reaches 48.02% Pass@4 versus 44.84% for ReMe with roughly the same number of model calls. This is the main reason I favor acceptance.
Critical weaknesses
  1. The relationship to Go-Explore and IGE needs clearer discussion. Returning to earlier states through recorded actions already has precedent, so the contribution should be centered more precisely on verified recovery-point selection and attempt allocation.
  2. TaP uses intermediate checker feedback, while the main memory baselines receive feedback after an attempt. Table A25 partly addresses this difference, but does not give the baselines the same access to intermediate progress.
  3. The cost comparison mainly matches model-call counts. Total token usage and runtime, including search and verification, would make the practical efficiency gains easier to assess.
Questions for authors
  1. Could you compare TaP with an IGE-style baseline under the same model-call budget and intermediate checker access?
  2. Could you report total token usage and runtime, including probes, replay, and verification? Flag For Ethics Review
Reviewer_sLCpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

TaP (Trajectories as Programs) addresses a key bottleneck in LLM agent retry loops: existing methods store failed attempts as text, so when the model regenerates actions from scratch, it deviates from what actually worked and loses already-completed progress. TaP instead stores each attempt as an executable program that can be deterministically replayed to restore exact environment states, then uses Verified State Localization to scan a failed trajectory and keep only states where the task's checker confirms new progress (recovery points), and Probe-Guided Attempt Allocation to spend cheap probes deciding which recovery point can both leave the failed path and make new progress, before committing limited full attempts to the most promising ones. Once a task is solved, TaP prunes and replays the verified program without further model calls, so solved tasks stay solved. Across AppWorld and BFCL-V3 with four open-weight and three closed models, TaP sets a new state of the art on both Avg@4 and Pass@4, improves over strong memory baselines (ReMe dynamic) by up to ~17 Avg points, and transfers zero-shot across model sizes—validating that executable replay of verified states, rather than text regeneration, is what lets retries compound progress.

Critical strengths

The paper designs a concrete, well-engineered pipeline that makes the resettable/deterministic-environment assumption operational, and the most novel piece is Probe-Guided Attempt Allocation. The key insight is that recovery points are heterogeneous and attempts are budgeted, so the paper estimates two orthogonal quantities per recovery point: ρ (probability the probe actually leaves the failed path) and g (probability it makes verified progress after leaving), then combines them into q = ρ·g and uses cheap probes (2 probes × 5 actions per point) as a gating signal before spending expensive full attempts. This is clever because ρ and g trade off against depth in opposite directions, so their product naturally selects an interior recovery depth rather than the trivial earliest or latest point. Empirically, probe score q correlates monotonically with realized full-attempt success (Spearman 0.57–0.66; top decile succeeds 7.7–13.5× more often than bottom), validating that the cheap-probe signal is real. This is a specific, reusable algorithmic contribution that other retry/search frameworks can adopt.

Critical weaknesses

TaP's entire mechanism rests on a resettable, deterministic, side-effect-free environment with a partial-progress checker, a premise the authors admit excludes "live services with side effects" and under which "the recovery search loses its signal." Yet both benchmarks (AppWorld, BFCL-V3) are precisely such sandboxed, resettable API simulations, so the reported gains are measured only in the favorable regime, and no experiment tests non-resettable, stochastic, or success-only-checker settings (the one checker ablation, Table A25, never removes the checker from TaP itself). This matters because in non-resettable environments the recovery machinery collapses to "retention only," whose Pass@4 equals No Memory exactly (Table 2; Fig. A7b), so the headline 7.3 to 24.4 point Pass@4 gain vanishes precisely where the premise fails, leaving the claimed general experience-reuse framework far narrower than presented.

Questions for authors

None.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.