# Success Leaves Detours: Learning Executable Walkthroughs for Long-Horizon Agents arXiv: https://arxiv.org/abs/2609.22120 ยท HTML: https://mlsanity.com/paper/2609.22120/ ## Key facts - No citing papers in the map yet (data through 14 Oct 2026). - Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use. - Builds on 34 of its 40 references that are in the map. - First posted on arXiv 20 Aug 2026. ## Placed in - LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/) ## Builds on (most cited first, 30 of 34) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023) - [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022) - [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023) - [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024) - [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025) - [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022) - [WebRL: Training LLM Web Agents via Self-Evolving Online Curriculum Reinforcement Learning](https://mlsanity.com/paper/2411.02337/) (2024) - [Agent S: An Open Agentic Framework that Uses Computers Like a Human](https://mlsanity.com/paper/2410.08164/) (2024) - [Interactive Fiction Games: A Colossal Adventure](https://mlsanity.com/paper/1909.05398/) (2019) - [G-Memory: Tracing Hierarchical Memory for Multi-Agent Systems](https://mlsanity.com/paper/2506.07398/) (2025) - [Cradle: Empowering Foundation Agents Towards General Computer Control](https://mlsanity.com/paper/2403.03186/) (2024) - [Remember Me, Refine Me: A Dynamic Procedural Memory Framework for Experience-Driven Agent Evolution](https://mlsanity.com/paper/2512.10696/) (2025) - [WebEvolver: Enhancing Web Agent Self-Improvement with Coevolving World Model](https://mlsanity.com/paper/2504.21024/) (2025) - [Self-Challenging Language Model Agents](https://mlsanity.com/paper/2506.01716/) (2025) - [EvoTest: Evolutionary Test-Time Learning for Self-Improving Agentic Systems](https://mlsanity.com/paper/2510.13220/) (2025) - [UI-Genie: A Self-Improving Approach for Iteratively Boosting MLLM-based Mobile GUI Agents](https://mlsanity.com/paper/2505.21496/) (2025) - [MaestroMotif: Skill Design from Artificial Intelligence Feedback](https://mlsanity.com/paper/2412.08542/) (2024) - [Learning to Orchestrate Agents in Natural Language with the Conductor](https://mlsanity.com/paper/2512.04388/) (2025) - [ExpSeek: Self-Triggered Experience Seeking for Web Agents](https://mlsanity.com/paper/2601.08605/) (2026) - [Meta-RL Induces Exploration in Language Agents](https://mlsanity.com/paper/2512.16848/) (2025) - [Iterative Tool Usage Exploration for Multimodal Agents via Step-wise Preference Tuning](https://mlsanity.com/paper/2504.21561/) (2025) - [Exploratory Memory-Augmented LLM Agent via Hybrid On- and Off-Policy Optimization](https://mlsanity.com/paper/2602.23008/) (2026) - [ToolTree: Efficient LLM Agent Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning](https://mlsanity.com/paper/2603.12740/) (2026) - [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025) - [SAMULE: Self-Learning Agents Enhanced by Multi-level Reflection](https://mlsanity.com/paper/2509.20562/) (2025) - [R2D2: Remembering, Replaying and Dynamic Decision Making with a Reflective Agentic Memory](https://mlsanity.com/paper/2501.12485/) (2025) - [Learn the Ropes, Then Trust the Wins: Self-imitation with Progressive Exploration for Agentic Reinforcement Learning](https://mlsanity.com/paper/2509.22601/) (2025) - [Learning How to Remember: A Meta-Cognitive Management Method for Structured and Transferable Agent Memory](https://mlsanity.com/paper/2601.07470/) (2026) - [MAGNET: Towards Adaptive GUI Agents with Memory-Driven Knowledge Evolution](https://mlsanity.com/paper/2601.19199/) (2026) ## Abstract (arXiv) 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.