Travel Back To Move Forward: Retrospective Exploration and Evolving for Long Horizon Agents
Authors: Ziang Ye, Wentao Shi, Lei Chen, Zhengzhou Cai, Yu Wang, Zhiyuan Yao, Zihan Wang, Xierui Song, Fuli Feng, Yixin Cao
Organizations: University of Science and Technology of China · Shanghai Innovation Institute · Meituan · Facebook · Zhejiang University · Tsinghua University · Fudan University
Large language model agents increasingly operate in long-horizon environments where early mistakes can trigger cascading failures and trap agents in dead-end trajectories. Agents must therefore be able to proactively recover from such states and turn their exploratory experience into guidance for subsequent decisions. We introduce ReTRAIL, a framework that enables agents to rewind the environment to earlier states while preserving valid progress and carrying forward knowledge learned from abandoned exploration. The environment state moves backward while the agent's knowledge continues to move forward. ReTRAIL trains a shared policy with two complementary signals: State-Anchored GRPO compares alternative continuations from revisited states to improve execution, while a branch-advancement reward guides reflection through the progress of subsequent exploration. Experiments across four interactive benchmark MineSweeper, Sokoban, ALFWorld and ScienceWorld show that simply adding a rewind primitive provides limited benefit and can even degrade performance. In contrast, ReTRAIL enables agents to rewind from unproductive states and use insights from abandoned branches to guide subsequent exploration. These results demonstrate the value of coupling environment rewinding with experience reuse within an ongoing task for long-horizon task solving. The code is available at https://github.com/whi497/ReTRAIL.
Figures & tables
Figure 1: Retrospective exploration with retained experience. Multi-episode adaptation (top) restarts the task from s0 after an unsuccessful attempt, carrying retained experience into a new episode. In contrast, ReTRAIL (bottom) proactively abandons an unproductive branch, distills its experience, rewinds to an earlier state, and resumes with the retained execution prefix and accumulated experience. Recovery can occur before terminal failure.
Figure 2: Learning from retrospective exploration. The top panel collects retrospective trials for one task. Left: State-Anchored GRPO combines task-wide endpoint progress with return comparisons among continuations sharing an environment state and retained prefix, producing Acont for execution tokens including rewind. Right: the verified-progress difference between a matched abandoned/resumed pair produces Aref for the reflection tokens that generate em . The separate masked objectives jointly update one shared policy.
Method
MineSweeper
Sokoban
ALFWorld
ScienceWorld
P@1
T@1
T@3
P@1
T@1
T@3
P@1
T@1
T@3
P@1
T@1
T@3
Prompting Methods
Zero-shot
3.5
3.1 ↓ 0.4
5.2 ↑ 1.7
6.0
5.5 ↓ 0.5
9.0 ↑ 3.0
35.0
34.2 ↓ 0.8
40.1 ↑ 5.1
8.0
7.2 ↓ 0.8
11.0 ↑ 3.0
ReAct
6.0
6.5 ↑ 0.5
10.2 ↑ 4.2
7.0
6.8 ↓ 0.2
11.8 ↑ 4.8
40.0
41.0 ↑ 1.0
47.5 ↑ 7.5
10.2
9.4 ↓ 0.8
15.1 ↑ 4.9
Reflexion
5.5
7.0 ↑ 1.5
9.8 ↑ 4.3
6.5
6.2 ↓ 0.3
12.0 ↑ 5.5
38.0
42.1 ↑ 4.1
45.3 ↑ 7.3
9.0
13.0 ↑ 4.0
16.2 ↑ 7.2
Rollback
6.7
6.5 ↓ 0.2
13.2 ↑ 6.5
9.7
10.3 ↑ 0.6
15.0 ↑ 5.3
35.0
34.2 ↓ 0.8
43.1 ↑ 8.1
13.2
12.3 ↓ 0.9
20.0 ↑ 6.8
Table 1: Performance comparison on four long-horizon interactive benchmarks. P@1 evaluates forward execution without rewind, T@1 enables proactive rewind within one trial, and T@3 permits up to three macro attempts with reflection-guided recovery. Every setting shares a 60-call budget per trial, including execution and reflection. Colored annotations show absolute changes relative to P@1; bold values indicate the best result in each column. All values are success rates (%).
Figure 3: Exploration diversity and efficiency of LaMer and ReTRAIL on MineSweeper and Sokoban. (a) States visited, where higher values indicate broader exploration; (b) Actions to success, where lower values indicate more efficient solving. ReTRAIL visits more states while requiring fewer actions.
Figure 4: Scaling instance difficulty and recovery attempts. (a) T@3 success with additional mines or boxes; these settings vary instance difficulty. (b) Success with one to four permitted macro-attempts. ReTRAIL’s endpoint value is annotated in each panel. Y-axis ranges differ by subplot and are explicitly labeled. Higher is better.
Table 6
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Recovery gains by reference-solution length. The upper row shows reflection-guided retry gain Δref=T@3−T@1 ; the lower row shows proactive gain Δpro=T@1−P@1 . Values are equal-weight averages across the four environments, in percentage points. Short, Medium, and Long use the environment-specific grouping rules above.
Method
P@1
T@1
T@3
Zero-shot
13.1 ±1.6
12.5 ±1.7
16.3 ±2.7
ReAct
15.8 ±2.9
15.9 ±1.2
21.2 ±3.2
Reflexion
14.8 ±2.5
17.1 ±2.6
20.8 ±1.4
Rollback
16.2 ±2.7
15.8 ±1.7
22.8 ±3.1
GRPO
66.3 ±1.2
64.7 ±1.4
72.3 ±2.0
RLOO
65.2 ±2.3
63.7 ±2.3
70.9 ±2.1
Appendix
Table 4: Equal-weight averages across the four benchmarks, computed from the reported benchmark means in Table 1 and rounded to one decimal place. ± is the standard deviation across the three evaluation seeds. These are aggregate point estimates, not additional runs.
Environment
Train
Test
Partition information
MineSweeper
256
128
6×6 boards, 3 mines
Sokoban
256
128
registered room variants share these sizes
ALFWorld
3,553
140
train / valid_seen
ScienceWorld
3,322
1,661
L0 task/variation pairs
Appendix
Table 5: Registered task-instance partitions loaded by the training entrypoints. Counts describe distinct dataset entries, not generated continuations or repeated evaluations. ALFWorld’s selected test partition is valid_seen ; its separately registered valid_unseen partition contains 134 entries. ScienceWorld uses the L0 partition.
d0−dend , with dend=0 if solved and dend=d0 if deadlocked
ALFWorld
environment-returned transition reward
fraction of satisfied goal conditions at the endpoint
maximum fraction of satisfied goal conditions along the branch
ScienceWorld
environment-returned transition reward
native completion score at the endpoint
maximum native completion score along the branch
Policy visibility
environment-dependent native feedback
ScienceWorld score is visible
the branch comparison is not a prompt input
Appendix
Table 6: Training signals by environment. δt supplies the execution return, S the task-wide endpoint score, and V the branch score for reflection. Derived advantages and branch-score differences are not policy inputs.
Setting
Value
Policy and optimization
Learning rate
1×10−6
LR Scheduler
Constant
Optimizer updates
300
Batch size
16
Advantage-normalization ϵ
1×10−6
Appendix
Table 7: Training and evaluation configuration of ReTRAIL. Optimizer settings are shared with the trained baselines. The retrospective-exploration and objective blocks describe ReTRAIL; a trial can contain several forward segments and should not be equated with one baseline trajectory.
Unit
Meaning
Trial
The full run under one global model-call budget.
Macro-attempt
One attempt until success, irreversible failure, or budget exhaustion; proactive rewinds stay within it.
Forward segment
Execution between recovery boundaries, or until success, failure, or budget exhaustion.
Model call
One execution or reflection generation; a rewind request is an execution call.
Primitive action
One environment action; a Sokoban execution call can contain several moves.
Appendix
Table 8: Units used for rollout and budget accounting.
Model-initiated recovery
Forced recovery
Trigger
execution output requests an earlier checkpoint
controller observes a configured failure condition
Target
requested by the policy; validated before restoration
selected through the checkpoint-choice reflection interface
Reflection
a separate generation returning <remark>
a separate generation returning <remark> and a target
Call accounting
one execution call for the request, plus one reflection call
one reflection call in addition to preceding execution calls
Main-text metric
available under T@1 and T@3
failure-triggered retries available under T@3
Appendix
Table 9: Recovery triggers and model calls. Restoration follows reflection, so the abandoned branch remains available when its memory is generated. Checkpoint selection and fallback parsing follow the environment-specific prompt implementation.
Figure 6: MineSweeper: restoring the board while retaining the failed reveal’s outcome. Revealing (6,2) ends the branch. The policy selects C3 , preserving all three preceding safe reveals, and carries the mine location into the resumed execution. It then reveals (5,2) , completing the board. Coordinates are one-indexed.
Figure 7: Sokoban: replacing an unproductive continuation while preserving a solved subgoal. The policy returns from C10 to C4 , retaining the first box on its target. The final reflection identifies how to reach the right side of the remaining box; the next two action turns execute that route and complete the task. Coordinates follow the zero-indexed environment rendering.
Many real-world tasks require LLM agents to interact with their environments over long execution horizons. Errors that occur early in execution may propagate through both the agent context and environment state, and their effects may be difficult to reverse through subsequent actions. Existing methods mainly seek to reduce such errors through plan refinement and safety checks but provide little support after errors occur. To enable recovery during long-horizon execution, we present AgentRewind, a runtime recovery framework that records aligned checkpoints of the agent context and controlled environment, allowing agents to return to an earlier state and resume execution with information from previous attempts. We also construct MettleBench, a benchmark for evaluating task completion and partial progress on long-horizon engineering assignments containing a series of related requirements. Experiments across tasks, multiple models, execution strategies, and agent harnesses show that AgentRewind improves task success rate and average checklist progress over the compared baselines.
Yu Zhuang, Kefei Chen, Yitong Duan +3
University of Chinese Academy of Sciences · Zhongguancun Academy, Beijing, China · Institute of Automation, Chinese Academy of Sciences +1
Large language model (LLM) agents increasingly tackle long-horizon tasks through multi-step environment interaction, yet a single erroneous action can alter subsequent states and observations, causing errors to compound over time. Existing methods either correct the context without repairing altered environment states or restore earlier states while discarding useful experience, making it difficult to both eliminate failure conditions and avoid repeating past mistakes. We argue that reliable recovery should instead be treated as a rollback-boundary control problem that jointly determines when to intervene, where to resume, and what information should survive recovery. Based on this view, we propose Rollback-Induced Reflection (RIR), a unified recovery framework that restores execution to a selected prior state while carrying forward reusable knowledge distilled from the abandoned trajectory to guide subsequent decisions. We further characterize recovery through a unified operator over rollback depth and retained memory, providing a general view of state restoration and knowledge retention. Experiments on three long-horizon benchmarks show that RIR consistently improves average task performance across multiple LLM backbones, with structured reflection memory preserving useful experience and selective rollback enabling efficient recovery.
Long-horizon agents often struggle to recover from failures whose causes lie several steps earlier, beyond what local reflection or backtracking can resolve. We introduce BELIEFWEAVER, a framework that combines persistent evidence across attempts with prospective reasoning over repair directions. It maintains a relational belief state over frontiers, attempts, observations, and checkpoints. Execution evidence updates related frontier priorities across attempts and rollback, while diagnostic evidence gates execution. An implicit world model (IWM) evaluates repair hypotheses, predicts progress, and identifies relations among frontiers to guide exploration. We further distill these recurring IWM reasoning components into a 9B student through supervised fine-tuning and on-policy distillation (OPD). Across three terminal-based benchmarks, BELIEFWEAVER improves aggregate final score by 5.1 percentage points over native Terminus-2 continuation, with positive trends in exploration efficiency. The distilled 9B student improves final score by 9.8 percentage points over the reported native baseline while reducing estimated teacher API cost by 54.8% relative to the matched teacher. These results show that persistent evidence and prospective reasoning can improve recovery in long-horizon agent tasks while substantially reducing reliance on teacher-model inference.