Test-time self-evolving agents improve by reusing past experience, yet sparse-reward trajectories contain failures, loops, and detours, while summaries often omit the state conditions and action dependencies needed for execution. We study executable Walkthrough induction from sparse-reward trajectories: extracting compact, state-conditioned, and verifiable procedures. Our key observation is that delayed credit identifies actions associated with progress but cannot determine whether they produce facts required by later actions. We propose Trace, a credit-guided, dependency-grounded framework that compiles noisy trajectories into executable Walkthrough Memory. It detects progress anchors from rewards and persistent state changes, propagates credit to identify valuable transitions, and estimates action prerequisites from cross-episode success and failure evidence. Backward dependency slicing then traces required facts to their producers, extracting dependency-consistent action chains while removing irrelevant loops and detours. The resulting Walkthroughs encode entry conditions, ordered state--action--effect steps, and completion and failure predicates, supporting reuse, intermediate-state resumption, and programmatic verification. Experiments on J-TTL, WebShop, and ScienceWorld with three open-source LLMs show that Trace consistently outperforms eight test-time learning and memory baselines. Compared with the strongest baseline, it improves average AUC and Final-3 by 30.0 and 40.5, respectively, while using fewer inference tokens. These results show that long-horizon interaction benefits more from state-conditioned executable procedures than from complete trajectories or abstract summaries.
Figures & tables
Figure 1: Overview of Trace . The upper pipeline scores progress-linked candidates, estimates action prerequisites from cross-episode evidence, and slices trajectories backward from anchor facts. The lower panel shows the resulting executable Walkthrough, including state-conditioned steps, verification status, and scheduling statistics used by the next episode.
WebShop
J-TTL
ScienceWorld
Avg.
Backbone
Method
AUC ↑
Final-3 ↑
AUC ↑
Final-3 ↑
AUC ↑
Final-3 ↑
AUC ↑
Final-3 ↑
Qwen3-32B
Static †
0.4823 ↑0.00
0.4706 ↑0.00
0.0290 ↑0.00
0.0191 ↑0.00
0.1397 ↑0.00
0.1150 ↑0.00
0.2170 ↑0.00
0.2016 ↑0.00
Memory ⋆
0.5403 ↑0.06
0.5578 ↑0.09
0.1327 ↑0.10
0.0583 ↑0.04
-0.0273 ↓0.17
-0.0020 ↓0.12
0.2152 ↓0.00
0.2047 ↑0.00
RAG ⋆
0.4510 ↓0.03
0.4321 ↓0.04
0.0263 ↓0.00
0.0180 ↓0.00
0.1200 ↓0.02
0.1170 ↑0.00
0.1991 ↓0.02
0.1890 ↓0.01
Summary ⋆
0.4680 ↓0.01
0.4943 ↑0.02
0.1461 ↑0.12
0.0654 ↑0.05
0.0759 ↓0.06
0.0624 ↓0.05
0.2300 ↑0.01
0.2074 ↑0.01
Reflexion ⋆
0.4859 ↑0.00
0.4728 ↑0.00
0.2380 ↑0.21
0.1870 ↑0.17
0.1388 ↓0.00
0.1513 ↑0.04
0.2876 ↑0.07
0.2704 ↑0.07
Table 1: (RQ1-A) Overall performance comparison across three benchmarks. All methods are evaluated with the same backbone model within each block. We highlight the best and second-best results. † : No-learning Baseline. ⋆ : Memory-based & Reflection-based Methods. ⋄ : Automated Prompt Optimization Methods.
Figure 2: (RQ1-B) Performance–cost comparison using GPT-OSS-20B . All methods use the same backbone and are evaluated under the same ten-episode interaction budget. Total Tokens include both input and output tokens consumed over all episodes and are reported in millions (M). We highlight the best and second-best performance.
Figure 4
Figure 4: (RQ4-A) Robustness to progress-signal masking on ScienceWorld and J-TTL using GPT-OSS-20B .
Figure 5: (RQ4-B) Cross-episode evidence sample efficiency on ScienceWorld and J-TTL using GPT-OSS-20B .
Figure 6: (RQ4-C) Robustness to trajectory noise on ScienceWorld and J-TTL using GPT-OSS-20B .
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.
Ziang Ye, Wentao Shi, Lei Chen +7
University of Science and Technology of China · Shanghai Innovation Institute · Meituan +4
Long-horizon agents learn from failure, but the value of a failure record can change as execution progresses. We study when retaining, compressing, or removing the same history block improves subsequent execution relative to full-history KEEP. We introduce RECAP, a framework that combines matched context interventions, execution-relational prediction, and independent policy certification. Matched environment states and rollout seeds measure success and continuation prompt-cost differences; prefix-only relations between a failure block and the current execution propose promising edits. Independent task bundles then select a policy subject to harmful-intervention and non-positive-benefit risk constraints under a fixed measurement protocol. A five-seed longitudinal case holds both the failure block and its summary fixed: compression fails at an early state and becomes a cost-saving intervention at a later state. Across five backbones, RECAP produces positive paired-success saving estimates with backbone-specific reliability-efficiency tradeoffs. On Hunyuan-A13B, it edits 43.24% of retained checkpoints while matching KEEP's observed 91.89% continuation success and reducing unconditional mean continuation prompt cost by 4,619.8 tokens (2.13%). The framework provides an execution-level reference for deciding when to forget: retain history by its value to what comes next.
Chenle Chen, Yangbo Wei, Zhijie Zheng +6
University of California, Los Angeles · Shanghai Jiao Tong University · Arizona State University +1
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