Travel Back To Move Forward: Retrospective Exploration and Evolving for Long Horizon Agents

Ziang Ye; Wentao Shi; Lei Chen; Zhengzhou Cai; Yu Wang; Zhiyuan Yao; Zihan Wang; Xierui Song

cs.AIOct 9, 2026

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,

Organizations: University of Science and Technology of China · Shanghai Innovation Institute · Meituan · Facebook ·

Abstract

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 $s_{0}$ 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 $A^{\mathrm{cont}}$ for execution tokens including rewind. Right: the verified-progress difference between a matched abandoned/resumed pair produces $A^{\mathrm{ref}}$ for the reflection tokens that generate $e_{m}$ . The separate masked objectives jointly update one shared policy.

Prompting Methods
Method	MineSweeper			Sokoban			ALFWorld			ScienceWorld
Method	P@1	T@1	T@3	P@1	T@1	T@3	P@1	T@1	T@3	P@1	T@1	T@3
Zero-shot	3.5	3.1 $\downarrow$ 0.4	5.2 $\uparrow$ 1.7	6.0	5.5 $\downarrow$ 0.5	9.0 $\uparrow$ 3.0	35.0	34.2 $\downarrow$ 0.8	40.1 $\uparrow$ 5.1	8.0	7.2 $\downarrow$ 0.8	11.0 $\uparrow$ 3.0
ReAct	6.0	6.5 $\uparrow$ 0.5	10.2 $\uparrow$ 4.2	7.0	6.8 $\downarrow$ 0.2	11.8 $\uparrow$ 4.8	40.0	41.0 $\uparrow$ 1.0	47.5 $\uparrow$ 7.5	10.2	9.4 $\downarrow$ 0.8	15.1 $\uparrow$ 4.9
Reflexion	5.5	7.0 $\uparrow$ 1.5	9.8 $\uparrow$ 4.3	6.5	6.2 $\downarrow$ 0.3	12.0 $\uparrow$ 5.5	38.0	42.1 $\uparrow$ 4.1	45.3 $\uparrow$ 7.3	9.0	13.0 $\uparrow$ 4.0	16.2 $\uparrow$ 7.2
Rollback	6.7	6.5 $\downarrow$ 0.2	13.2 $\uparrow$ 6.5	9.7	10.3 $\uparrow$ 0.6	15.0 $\uparrow$ 5.3	35.0	34.2 $\downarrow$ 0.8	43.1 $\uparrow$ 8.1	13.2	12.3 $\downarrow$ 0.9	20.0 $\uparrow$ 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

\Delta_{\mathrm{ref}}=\mathrm{T@3}-\mathrm{T@1}

; the lower row shows proactive gain

\Delta_{\mathrm{pro}}=\mathrm{T@1}-\mathrm{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 ${\pm}1.6$	12.5 ${\pm}1.7$	16.3 ${\pm}2.7$
ReAct	15.8 ${\pm}2.9$	15.9 ${\pm}1.2$	21.2 ${\pm}3.2$
Reflexion	14.8 ${\pm}2.5$	17.1 ${\pm}2.6$	20.8 ${\pm}1.4$
Rollback	16.2 ${\pm}2.7$	15.8 ${\pm}1.7$	22.8 ${\pm}3.1$
GRPO	66.3 ${\pm}1.2$	64.7 ${\pm}1.4$	72.3 ${\pm}2.0$
RLOO	65.2 ${\pm}2.3$	63.7 ${\pm}2.3$	70.9 ${\pm}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.

\pm

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\times 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.

	$\delta_{t}$ (per step)	$S$ (segment endpoint)	$V(\xi\mid s)$ (branch)
MineSweeper	native board reward: $+0.5$ safe reveal, $+2.0$ blank-region expansion, $+10.0$ board cleared, $-0.1$ mine revealed, $-1.0$ invalid or no-change action	cumulative $\delta$ on the retained path from $s_{0}$	cumulative $\delta$ along the branch
Sokoban	environment-returned transition reward	$d_{0}-d(\text{endpoint})$ by breadth-first search	$d_{0}-d_{\mathrm{end}}$ , with $d_{\mathrm{end}}=0$ if solved and $d_{\mathrm{end}}=d_{0}$ 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.

\delta_{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.

Policy and optimization
Setting	Value
Learning rate	$1\times 10^{-6}$
LR Scheduler	Constant
Optimizer updates	300
Batch size	16
Advantage-normalization $\epsilon$	$1\times 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

C_{3}

, 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

C_{10}

C_{4}

, 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.

Long-Horizon LLM Agents

Long-horizon large language model agents plan, use tools, and preserve task state across extended, multi-step interactions.

See all 429 papers

AgentRewind: Recoverable Execution for Long-Horizon LLM Agents
Aug 14, 2026Yu Zhuang, Kefei Chen, Yitong Duan +3Long-Horizon LLM Agents Long-Horizon Agent Tasks
University of Chinese Academy of Sciences · Zhongguancun Academy, Beijing, China · Institute of Automation, Chinese Academy of Sciences +1
Rollback the World, Keep the Reflection: Rollback-Induced Reflection for Long-Horizon LLM Agents
Sep 16, 2026Yi Yu, Liuyi Yao, Yaliang Li +2Long-Horizon LLM Agents LLM Agent Reliability
Wuhan University · Alibaba Group
Failure Recovery via Belief Updates and World Modeling for Long-Horizon Agents
Oct 13, 2026Xiyang Wu, Zhichao Liu, Shengxin zhang +4Long-Horizon LLM Agents Long-Horizon Reasoning
University of Maryland · Google · MBZUAI

Aug 14, 2026J/K move · Enter open · S save

AgentRewind: Recoverable Execution for Long-Horizon LLM Agents

Yu Zhuang, Kefei Chen, Yitong Duan, Shuxin Zheng+2

University of Chinese Academy of Sciences · Zhongguancun Academy, Beijing, China · Institute of Automation, Chinese Academy of Sciences+1

Long-Horizon LLM Agents Long-Horizon Agent Tasks LLM Agent Reliability Long-Horizon Agent Evaluation

Open paper AskPDF arXiv

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.

Abstract

Long-Horizon LLM Agents

Explore similar work

AgentRewind: Recoverable Execution for Long-Horizon LLM Agents

Rollback the World, Keep the Reflection: Rollback-Induced Reflection for Long-Horizon LLM Agents

Failure Recovery via Belief Updates and World Modeling for Long-Horizon Agents