Success Leaves Detours: Learning Executable Walkthroughs for Long-Horizon Agents

# Success Leaves Detours: Learning Executable Walkthroughs for Long-Horizon Agents
Source: [https://arxiv.org/html/2609.22120](https://arxiv.org/html/2609.22120)
Chenyu FangAffiliation:Shanghai AI LaboratoryAffiliation:Corresponding authorsLiang YanAffiliation:Fudan UniversityAffiliation:\[3pt\] Equal contributionBo LiAffiliation:Fudan UniversityBo ZhangAffiliation:Shanghai AI LaboratoryPeng YeAffiliation:Shanghai AI LaboratoryAffiliation:Corresponding authors

###### Abstract

Test\-time self\-evolving agents improve by reusing experience across episodes, but sparse\-reward trajectories contain failed attempts, loops, and detours that hinder direct reuse, while trajectory summaries often discard the state conditions and action dependencies required for execution\. We study*executable Walkthrough induction from sparse\-reward trajectories*, aiming to extract compact, state\-conditioned, and verifiable procedures\. Our key observation is that delayed credit measures an action’s association with downstream progress but does not establish whether the action produces a state fact required for subsequent execution\. We therefore proposeTrace, a credit\-guided and dependency\-grounded framework that compiles noisy interaction histories into executable Walkthrough Memory\. It first detects progress anchors from reward and persistent state changes and propagates credit backward to identify high\-value transitions\. It then estimates the prerequisites of each action from cross\-episode success and failure evidence\. Finally, backward dependency slicing traces anchor facts to their observed producers and extracts compact, dependency\-consistent action chains, while filtering loops and detours that are not linked to the resolved dependencies\. The resulting Walkthroughs explicitly encode entry conditions, ordered state–action–effect steps, completion and failure predicates, and prerequisite dependencies, enabling cross\-episode reuse, intermediate\-state resumption, and programmatic verification\. Experiments on J\-TTL, WebShop, and ScienceWorld with three open\-source LLM backbones show thatTraceconsistently outperforms eight test\-time learning and memory baselines\. Compared with the strongest baseline, it improves average AUC and Final\-33by30\.0%30\.0\\%and40\.5%40\.5\\%, respectively, while using fewer inference tokens\. Ablations and controlled studies validate the contributions of credit propagation, prerequisite estimation, dependency slicing, executable representation, and dependency\-aware selection\. These results suggest that long\-horizon interaction is better supported by state\-conditioned executable procedures than by complete trajectories or abstract summaries\.

## 1Introduction

Large Language Model \(LLM\) agents have demonstrated substantial progress on long\-horizon interactive tasks, including web navigation, software operation, text\-based games, and tool\-augmented problem solving\([42](https://arxiv.org/html/2609.22120#bib.bib1);[32](https://arxiv.org/html/2609.22120#bib.bib2);[28](https://arxiv.org/html/2609.22120#bib.bib3)\)\. Despite this progress, long\-horizon environments remain difficult because they are often partially observable, governed by sparse or delayed feedback, and structured around prerequisite chains whose consequences emerge only many steps after an action is taken\. Test\-time self\-evolving agents seek to overcome these limitations by accumulating interaction experience across episodes and updating external memories, prompts, or agent configurations without repeatedly modifying the underlying model\([25](https://arxiv.org/html/2609.22120#bib.bib6);[40](https://arxiv.org/html/2609.22120#bib.bib7);[10](https://arxiv.org/html/2609.22120#bib.bib19)\)\. The resulting improvement, however, depends critically on whether noisy interaction trajectories can be transformed into memories that later Actors can reliably select, execute, and verify\.

Consider a broad class of long\-horizon environments in which meaningful progress is distributed across many steps, explicit reward is sparse or delayed, and successful execution depends on latent prerequisites\. A trajectory that ultimately opens a gate may containGO SOUTH,GO NORTH,ASK TECHNICIAN,SEARCH DESK,TAKE CODE, andOPEN GATE\. Only the final action may receive reward, even though asking the technician, searching the desk, and taking the code establish indispensable conditions, while the back\-and\-forth navigation may be incidental\. Memory construction in this setting must therefore recover unrewarded preparation, distinguish necessary steps from coincidental detours, identify coherent procedure boundaries, and preserve the state conditions under which each step remains valid\. We formulate this problem as*executable Walkthrough induction from sparse\-reward trajectories*: recovering minimal, state\-conditioned, executable, and verifiable procedures that can reproduce progress in subsequent episodes\.

Existing agent memory systems approach experience reuse through four broad representational paradigms, each preserving a different aspect of interaction history while omitting part of the execution structure required in this setting\.\(1\) Episodic replay and retrieval methodspreserve or recall concrete past experience\([11](https://arxiv.org/html/2609.22120#bib.bib4);[29](https://arxiv.org/html/2609.22120#bib.bib5)\); although such memories improve behavioral fidelity and state alignment, retrieval alone does not identify a minimally sufficient procedure, determine which recorded steps remain necessary, or specify where execution should resume and terminate\.\(2\) Semantic distillation and reflective memorycompress trajectories into reflections, insights, rules, or evolving playbooks\([25](https://arxiv.org/html/2609.22120#bib.bib6);[40](https://arxiv.org/html/2609.22120#bib.bib7);[36](https://arxiv.org/html/2609.22120#bib.bib8)\); these representations are compact and transferable, but they often abstract away explicit preconditions, intermediate state effects, resource\-acquisition paths, and programmatic completion or failure criteria\.\(3\) Procedural and workflow\-oriented memoriesextract reusable routines or structured abstractions\([3](https://arxiv.org/html/2609.22120#bib.bib9);[19](https://arxiv.org/html/2609.22120#bib.bib10);[26](https://arxiv.org/html/2609.22120#bib.bib11)\); however, their induction objectives do not explicitly test whether every retained transition establishes a fact required by a later action, so successful trajectories may still yield procedures that contain incidental steps or fail under altered intermediate states\.\(4\) Graph\-structured memoriesorganize experience through temporal, semantic, hierarchical, or quasi\-symbolic relations\([34](https://arxiv.org/html/2609.22120#bib.bib12);[24](https://arxiv.org/html/2609.22120#bib.bib13)\); such connectivity supports structured retrieval and abstraction, but an edge is not an executable dependency unless the state produced upstream satisfies a precondition downstream\. The common missing element is therefore a fact\-grounded criterion that separates historical association with success from procedural necessity\.

The central technical problem is*grounded procedure induction*: identifying the smallest action chain that establishes a target state together with all prerequisites required to reach it\. We address this problem withTrace, a credit\-guided and dependency\-grounded framework for inducing executable Walkthroughs from noisy, sparse\-reward trajectories\. Its key insight is that delayed credit and procedural necessity provide complementary but non\-equivalent evidence\. Delayed credit can recover early actions that may contribute to later progress, including preparation with no immediate reward, but high credit only indicates historical relevance and does not prove that an action is required\. Procedural necessity instead depends on whether an action establishes the target state or a prerequisite fact consumed by a later step\. Accordingly,Traceuses progress\-aware credit propagation to obtain high\-recall candidate actions, then applies fact\-grounded prerequisite analysis to retain only the transitions needed to reproduce the target progress\. Credit identifies potentially useful evidence, while dependency recovers the minimally sufficient execution chain\.

Traceconverts raw interaction trajectories into executable Walkthroughs through a three\-stage programmatic pipeline\. First, it canonicalizes observations into structured states, detects progress anchors from rewards and persistent state changes, and propagates credit backward to recover potentially useful preparatory transitions\. Second, it estimates prerequisite facts from observed action outcomes and cross\-episode evidence, then performs required\-fact\-driven backward slicing to retain only transitions that establish the target state or an unresolved prerequisite\. This removes loops, failed branches, redundant detours, and high\-credit actions that are not procedurally necessary\. Third, the retained dependency chain is compiled into a structured Walkthrough with explicit entry conditions, ordered precondition\-action\-effect steps, prerequisite relations, and completion and failure predicates\. The resulting memory supports applicability checking, intermediate\-state resumption, effect verification, and reliable termination\. Across episodes, only the external Walkthrough Memory evolves, while the Actor remains fixed\.

Empirically,Tracedelivers stronger and more consistent test\-time improvement than memory, retrieval, reflection, and automated prompt\-optimization baselines\. Across WebShop, J\-TTL, and ScienceWorld benchmarks withQwen3\-32B,Mistral\-Small\-3\.2\-24B, andGPT\-OSS\-20B,Traceachieves the strongest AUC and Final\-33performance in every evaluated benchmark\-backbone block\. Relative to the strongest competing baseline in each setting, it improves average AUC by 30\.0% and Final\-33by 40\.5%, with average gains of 65\.4% in AUC and 135\.6% in Final\-33on the prerequisite\-intensive J\-TTL benchmark\. Diagnostic ablations further establish a coherent mechanism\-to\-outcome chain: delayed credit increases preparatory\-action recall, prerequisite estimation improves dependency recovery and necessary\-step recall, and backward slicing raises necessary\-step precision, reduces residual redundancy, and improves replay success\. Robustness studies show gradual degradation under masked progress signals and injected exploration, loops, and backtracking, while increasing the history budget from three to nine episodes improves endpoint performance, despite non\-monotonic intermediate results\. These results support the central claim that effective long\-horizon experience reuse requires both recovery of necessary state dependencies and an executable representation of the resulting procedure\.

Our main contributions are as follows:

- •Credit\-Guided, Dependency\-Grounded Induction\.We introduceTracefor test\-time self\-evolution in long\-horizon environments with sparse feedback, delayed consequences, hidden prerequisites, and noisy trajectories\. By combining progress anchoring and delayed credit propagation with experience\-grounded prerequisite estimation and required\-fact\-driven backward slicing,Tracerecovers unrewarded preparation while removing actions that are historically correlated with success but procedurally unnecessary\.
- •Executable Self\-Evolving Walkthrough Memory\.We propose a structured procedural memory that represents experience through entry conditions, prerequisite dependencies, ordered precondition\-action\-effect steps, and programmatic completion and failure predicates\. This representation supports applicability checking, intermediate\-state resumption, effect verification, reliable termination, and continual cross\-episode refinement without updating the Actor parameters\.
- •Cross\-Benchmark Gains and Mechanistic Validation\.Traceattains the strongest AUC and Final\-33results in every evaluated benchmark\-backbone block, improving the strongest competing baselines by 30\.0% and 40\.5% on average and achieving particularly large gains on J\-TTL\. Fine\-grained ablations, trajectory\-quality diagnostics, progress\-signal masking, noise injection, and history\-efficiency studies consistently validate the distinct roles of credit propagation, prerequisite estimation, and dependency slicing\.

## 2Related Work

#### Test\-Time Learning and Self\-Improving LLM Agents\.

Existing work improves agents through reflection, online training, or system\-level search\. SAMULE\([7](https://arxiv.org/html/2609.22120#bib.bib21)\)generates reflections from individual interactions, within\-task experience, and cross\-task experience\. WebEvolver\([6](https://arxiv.org/html/2609.22120#bib.bib22)\), WebRL\([22](https://arxiv.org/html/2609.22120#bib.bib23)\), UI\-Genie\([30](https://arxiv.org/html/2609.22120#bib.bib24)\), and Self\-Challenging Agents\([43](https://arxiv.org/html/2609.22120#bib.bib25)\)convert interaction trajectories, generated data, or self\-constructed tasks into training signals\. Gödel Agent\([33](https://arxiv.org/html/2609.22120#bib.bib26)\)and AFlow\([35](https://arxiv.org/html/2609.22120#bib.bib27)\)optimize agents through self\-modification or workflow search\. These methods typically require parameter updates, reflection, or costly search\. In contrast, we freeze both the model and agent framework and update only a cross\-episode Walkthrough Memory through programmatic trajectory processing, enabling lightweight test\-time improvement\.

#### Procedural Memory and Workflow Induction from Agent Trajectories\.

Evolving Generalist Virtual Agents\([39](https://arxiv.org/html/2609.22120#bib.bib28)\), G\-Memory\([34](https://arxiv.org/html/2609.22120#bib.bib12)\), and Evolving Agents\([24](https://arxiv.org/html/2609.22120#bib.bib13)\)organize interaction experience into subtask graphs, hierarchical memories, or symbolic abstractions\. ReMe\([4](https://arxiv.org/html/2609.22120#bib.bib15)\), Learning How to Remember\([18](https://arxiv.org/html/2609.22120#bib.bib16)\), and MAGNET\([26](https://arxiv.org/html/2609.22120#bib.bib11)\)study the maintenance and transfer of procedural knowledge, while SAMem\([29](https://arxiv.org/html/2609.22120#bib.bib5)\), R2D2\([11](https://arxiv.org/html/2609.22120#bib.bib4)\), Stepwise Experience Recall\([5](https://arxiv.org/html/2609.22120#bib.bib29)\), and ExpSeek\([38](https://arxiv.org/html/2609.22120#bib.bib30)\)improve state\- or step\-level retrieval\. These methods mainly reuse summaries, rules, or local trajectory fragments without explicitly representing step\-level dependencies and execution conditions\. Our method instead analyzes state transitions directly: progress anchors identify local goals, delayed credit recovers potentially useful preceding actions, and backward dependency slicing extracts compact, dependency\-consistent action chains by retaining transitions linked to target facts and their candidate prerequisites\. The resulting Walkthroughs contain entry conditions, ordered actions, expected effects, and completion and failure criteria, while a prerequisite DAG represents dependencies among them\.

#### Exploration and Prerequisite\-Aware Walkthrough Scheduling\.

Existing exploration methods mainly optimize action, policy, or tool selection\. Toward Efficient Exploration\([2](https://arxiv.org/html/2609.22120#bib.bib31)\)and Meta\-RL\([12](https://arxiv.org/html/2609.22120#bib.bib32)\)study posterior sampling and learned exploration strategies\. Progressive Exploration\([23](https://arxiv.org/html/2609.22120#bib.bib33)\), Exploratory Memory\-Augmented Agent\([20](https://arxiv.org/html/2609.22120#bib.bib34)\), Dual\-Scale World Memory\([13](https://arxiv.org/html/2609.22120#bib.bib35)\), DreamPhase\([8](https://arxiv.org/html/2609.22120#bib.bib36)\), and SPORT\([15](https://arxiv.org/html/2609.22120#bib.bib37)\)improve exploration through self\-imitation, memory, world models, offline imagination, or preference learning\. MaestroMotif\([14](https://arxiv.org/html/2609.22120#bib.bib38)\), Agent S\([1](https://arxiv.org/html/2609.22120#bib.bib39)\), Cradle\([27](https://arxiv.org/html/2609.22120#bib.bib20)\), ToolTree\([31](https://arxiv.org/html/2609.22120#bib.bib40)\), and Conductor\([21](https://arxiv.org/html/2609.22120#bib.bib41)\)search over predefined skills, tools, or agent sets, while COLA\([41](https://arxiv.org/html/2609.22120#bib.bib42)\)and Cook and Clean Together\([17](https://arxiv.org/html/2609.22120#bib.bib43)\)study subtask scheduling\. These approaches typically explore primitive actions or predefined skills and therefore cannot directly exploit prerequisite structures induced from prior trajectories\. We schedule only Walkthroughs whose execution conditions are currently satisfied and propagate downstream returns through the prerequisite DAG, reducing ineffective exploration while capturing the long\-term value of prerequisite procedures\.

![Refer to caption](https://arxiv.org/html/2609.22120v1/main.png)Figure 1:Overview ofTrace\.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\.

## 3Credit\-Guided Walkthrough Memory Construction and Scheduling

We consider a long\-horizon interactive setting in which a frozen LLM Actor repeatedly attempts the same task across episodes\. After each episode, the Evolver deterministically transforms the interaction trajectory into executable*Walkthrough Memory*, where each Walkthrough encodes a reusable subgoal with its prerequisites, ordered steps, expected effects, and termination conditions\. The Evolver detects progress anchors through state differencing, propagates delayed credit to earlier contributing actions, infers prerequisites from action effects and cross\-episode evidence, and applies backward dependency slicing to extract compact, dependency\-consistent action chains from the observed trajectories\.

### 3\.1Progress Anchoring and Delayed Credit Propagation

#### Canonical state representation\.

After an episode ofTTactions, the Evolver receives

τ=\(ot,at,rt,inv​t\)​t=1T,\\tau=\{\(o\_\{t\},a\_\{t\},r\_\{t\},\\mathrm\{inv\}t\)\}\{t=1\}^\{T\},\(1\)whereoto\_\{t\},ata\_\{t\},rtr\_\{t\}, andinvt\\mathrm\{inv\}\_\{t\}denote the observation, action, cumulative reward, and inventory at steptt, respectively\. Each observation is deterministically parsed into

st=\(ℓt,ℐt,𝒪t,𝒵t,ℰt,𝒜t\),s\_\{t\}=\(\\ell\_\{t\},\\mathcal\{I\}\_\{t\},\\mathcal\{O\}\_\{t\},\\mathcal\{Z\}\_\{t\},\\mathcal\{E\}\_\{t\},\\mathcal\{A\}\_\{t\}\),\(2\)whereℓt\\ell\_\{t\}is the current location,ℐt\\mathcal\{I\}\_\{t\}is the inventory,𝒪t\\mathcal\{O\}\_\{t\}is the visible\-object set,𝒵t\\mathcal\{Z\}\_\{t\}contains object states,ℰt\\mathcal\{E\}\_\{t\}contains exits, and𝒜t\\mathcal\{A\}\_\{t\}contains admissible actions\.

The canonical state is assigned a stable keyκt=Hash⁡\(st\)\\kappa\_\{t\}=\\operatorname\{Hash\}\(s\_\{t\}\)\. We define the reward and state changes asΔ​rt=rt\+1−rt\\Delta r\_\{t\}=r\_\{t\+1\}\-r\_\{t\}andΔ​st=Diff⁡\(st,st\+1\)\\Delta s\_\{t\}=\\operatorname\{Diff\}\(s\_\{t\},s\_\{t\+1\}\), respectively\. The trajectory then induces the following state–action transition:

et:κt→,at,κt\+1\.e\_\{t\}:\\quad\\kappa\_\{t\}\\xrightarrow\{,a\_\{t\},\}\\kappa\_\{t\+1\}\.\(3\)Each transition is associated with the reward changeΔ​rt\\Delta r\_\{t\}and state changeΔ​st\\Delta s\_\{t\}\. This representation exposes the persistent state changes and repeated transitions required by the subsequent credit and dependency analyses\.

#### Progress anchors and delayed credit\.

A*hard progress anchor*is created when a transition changes reward, inventory, a persistent object state, an unlocked region or exit, a persistent flag, or the terminal status\. For example, adding an access code to the inventory yields an ‘obtain access code” anchor, while changing a gate from locked to open yields an ‘open gate” anchor\. A*discovery anchor*is created when the Actor first reaches a room, observes an object or exit, discovers a new admissible action, or encounters an available but untried opportunity\. Anchor labels are instantiated from fixed templates rather than generated by an LLM\.

To assign credit to preceding zero\-reward actions, the Evolver defines

gt=Δ​rt\+λI​It\+λO​Ot\+λE​Et−λF​Ft,g\_\{t\}=\\Delta r\_\{t\}\+\\lambda\_\{I\}I\_\{t\}\+\\lambda\_\{O\}O\_\{t\}\+\\lambda\_\{E\}E\_\{t\}\-\\lambda\_\{F\}F\_\{t\},\(4\)whereItI\_\{t\},OtO\_\{t\}, andEtE\_\{t\}indicate task\-relevant inventory, object\-state, and exploration progress, whileFtF\_\{t\}indicates invalid actions, death, loops, or no progress\. For a candidate segment ending at anchor steptat\_\{a\}, credit is propagated backward along the observed trajectory:

Cta=gta,Ct=gt\+γ​Ct\+1,t<ta,C\_\{t\_\{a\}\}=g\_\{t\_\{a\}\},\\qquad C\_\{t\}=g\_\{t\}\+\\gamma C\_\{t\+1\},\\quad t<t\_\{a\},\(5\)
whereγ∈\(0,1\)\\gamma\\in\(0,1\)is a step\-level discount factor\.

#### Experience\-grounded prerequisite estimation\.

Delayed credit identifies temporally useful transitions but does not reveal the conditions under which their actions are likely to succeed\. The Evolver therefore aggregates action attempts across episodes to identify facts that are empirically associated with action success\.

For each attemptiiof actionaa, letyi∈\{0,1\}y\_\{i\}\\in\\\{0,1\\\}denote whether the action succeeds, and letxif∈\{0,1\}x\_\{i\}^\{f\}\\in\\\{0,1\\\}indicate whether factffhas been observed before the action is executed\. We define the support of the two groups as

Nb\(f,a\)=∑i∈𝒟a𝕀\[xif=b\],b∈\{0,1\},N\_\{b\}\(f,a\)=\\sum\_\{i\\in\\mathcal\{D\}\_\{a\}\}\\mathbb\{I\}\[x\_\{i\}^\{f\}=b\],\\qquad b\\in\\\{0,1\\\},\(6\)where𝒟a\\mathcal\{D\}\_\{a\}contains all observed attempts of actionaaacross episodes\. The empirical prerequisite score is then

Nec⁡\(f,a\)=Pr^​\(y=1∣a,xf=1\)−Pr^​\(y=1∣a,xf=0\)\.\\operatorname\{Nec\}\(f,a\)=\\widehat\{\\Pr\}\(y=1\\mid a,x^\{f\}=1\)\-\\widehat\{\\Pr\}\(y=1\\mid a,x^\{f\}=0\)\.\(7\)A fact is included in the candidate prerequisite set only if

f∈Pre^​\(a\)⇔Nec⁡\(f,a\)\>τpre∧N1​\(f,a\)≥nmin∧N0​\(f,a\)≥nmin\.f\\in\\widehat\{\\operatorname\{Pre\}\}\(a\)\\iff\\operatorname\{Nec\}\(f,a\)\>\\tau\_\{\\mathrm\{pre\}\}\\;\\land\\;N\_\{1\}\(f,a\)\\geq n\_\{\\min\}\\;\\land\\;N\_\{0\}\(f,a\)\\geq n\_\{\\min\}\.\(8\)Action–fact pairs that do not satisfy both support requirements, including actions that have not been sufficiently attempted, remain unspecified rather than being assigned a prerequisite relation\. We consider only facts observed before the action attempt, thereby excluding facts produced by the action itself\. Prerequisite candidates can additionally be supported by changes in admissible actions, environment\-provided failure reasons, and differences in action availability across states\.

Because this score is estimated from observational trajectories, it represents an empirical association rather than a causal or logically necessary condition\. We therefore use it only to identify candidate prerequisites for subsequent Strategy Map refinement\.

### 3\.2Fact\-Grounded Dependency Linking and Walkthrough Extraction

Prerequisite estimation determines which facts an action requires but does not identify which concrete transitions in the current trajectory produced those facts\. Backward dependency slicing therefore starts from the anchor’s completion facts and recursively searches the trajectory for the actions that produced them, yielding a compact, dependency\-consistent action chain\.

The positive effect set of transitionttis

Efft=Diff\+⁡\(st,st\+1\)\.\\operatorname\{Eff\}\_\{t\}=\\operatorname\{Diff\}^\{\+\}\(s\_\{t\},s\_\{t\+1\}\)\.\(9\)A transition withκt=κt\+1\\kappa\_\{t\}=\\kappa\_\{t\+1\}hasEfft=∅\\operatorname\{Eff\}\_\{t\}=\\varnothingand is treated as a no\-progress self\-loop\.

For an anchor, the unresolved fact set is initialized as

R←CompleteFacts⁡\(anchor\)\.R\\leftarrow\\operatorname\{CompleteFacts\}\(\\mathrm\{anchor\}\)\.\(10\)The trajectory is scanned backward, and transitionttis retained when

Efft∩R≠∅\.\\operatorname\{Eff\}\_\{t\}\\cap R\\neq\\varnothing\.\(11\)After retention, the unresolved set is updated by

R←\(R∖Efft\)∪Pre⁡\(at\)\.R\\leftarrow\\left\(R\\setminus\\operatorname\{Eff\}\_\{t\}\\right\)\\cup\\operatorname\{Pre\}\(a\_\{t\}\)\.\(12\)
When evidence is sparse, the Evolver conservatively removes only exact self\-loops and explicit back\-and\-forth cycles, postponing further pruning until more episodes are available\.

For instance, slicing backward from an open\-gate anchor may retain*unlock gate*,*move to gate*,*take code*,*search desk*, and*ask technician*, while removing unrelated observations and detours\.

Each Walkthrough is represented compactly as

Wi=\(gi,Di,ei,Πi,ci,fi,zi,ηi\),W\_\{i\}=\(g\_\{i\},D\_\{i\},e\_\{i\},\\Pi\_\{i\},c\_\{i\},f\_\{i\},z\_\{i\},\\eta\_\{i\}\),\(13\)wheregig\_\{i\}is the local goal,DiD\_\{i\}is the prerequisite set,eie\_\{i\}is the entry predicate,Πi\\Pi\_\{i\}is the ordered procedure,cic\_\{i\}andfif\_\{i\}are the completion and failure predicates,ziz\_\{i\}is the verification status, andηi\\eta\_\{i\}stores scheduling statistics\. The procedure is

Πi=\(pi,1,…,pi,Li\),pi,j=\(Pi,j,ai,j,Ei,j\),\\Pi\_\{i\}=\(p\_\{i,1\},\\ldots,p\_\{i,L\_\{i\}\}\),\\qquad p\_\{i,j\}=\(P\_\{i,j\},a\_\{i,j\},E\_\{i,j\}\),\(14\)
wherePi,jP\_\{i,j\}is the step precondition,ai,ja\_\{i,j\}is the action, andEi,jE\_\{i,j\}is the expected effect\. Thus, a step can be represented simply as “technician visible→\\rightarrowask about gate→\\rightarrowdesk search enabled,” rather than as a free\-form textual memory\.

The completion predicate is generated directly from the corresponding progress anchor, while the failure predicate captures terminal failure, irreversible loss of a required fact, or an unrecoverable prerequisite state\. These explicit conditions make the induced procedure executable, resumable, and programmatically verifiable rather than merely descriptive\.

Table 1:\(RQ1\-A\)Overall performance comparison across three benchmarks\.All methods are evaluated with the same backbone model within each block\. We highlight thebestandsecond\-bestresults\.†: No\-learning Baseline\.⋆: Memory\-based & Reflection\-based Methods\.⋄: Automated Prompt Optimization Methods\.WebShopJ\-TTLScienceWorldAvg\.BackboneMethodAUC↑\\uparrowFinal\-3↑\\uparrowAUC↑\\uparrowFinal\-3↑\\uparrowAUC↑\\uparrowFinal\-3↑\\uparrowAUC↑\\uparrowFinal\-3↑\\uparrowQwen3\-32BStatic†0\.4823↑0\.000\.4706↑0\.000\.0290↑0\.000\.0191↑0\.000\.1397↑0\.000\.1150↑0\.000\.2170↑0\.000\.2016↑0\.00Memory⋆0\.5403↑0\.060\.5578↑0\.090\.1327↑0\.100\.0583↑0\.04\-0\.0273↓0\.17\-0\.0020↓0\.120\.2152↓0\.000\.2047↑0\.00RAG⋆0\.4510↓0\.030\.4321↓0\.040\.0263↓0\.000\.0180↓0\.000\.1200↓0\.020\.1170↑0\.000\.1991↓0\.020\.1890↓0\.01Summary⋆0\.4680↓0\.010\.4943↑0\.020\.1461↑0\.120\.0654↑0\.050\.0759↓0\.060\.0624↓0\.050\.2300↑0\.010\.2074↑0\.01Reflexion⋆0\.4859↑0\.000\.4728↑0\.000\.2380↑0\.210\.1870↑0\.170\.1388↓0\.000\.1513↑0\.040\.2876↑0\.070\.2704↑0\.07EvoTest⋄0\.4889↑0\.010\.5094↑0\.040\.1562↑0\.130\.0718↑0\.050\.1507↑0\.010\.1446↑0\.030\.2653↑0\.050\.2419↑0\.04ACE⋄0\.2128↓0\.270\.2317↓0\.240\.1855↑0\.160\.0768↑0\.060\.1530↑0\.010\.1602↑0\.050\.1838↓0\.030\.1563↓0\.05APEX⋄0\.5034↑0\.020\.5412↑0\.070\.1668↑0\.140\.1870↑0\.170\.0336↓0\.110\.0028↓0\.110\.2346↑0\.020\.2437↑0\.04Trace0\.5421↑0\.060\.6047↑0\.130\.2410↑0\.210\.2833↑0\.260\.1884↑0\.050\.2186↑0\.100\.3238↑0\.110\.3689↑0\.17Mistral\-Small\-3\.2\-24BStatic†0\.3974↑0\.000\.3867↑0\.000\.0398↑0\.000\.0309↑0\.000\.1626↑0\.000\.1333↑0\.000\.1999↑0\.000\.1836↑0\.00Memory⋆0\.4512↑0\.050\.5549↑0\.170\.1212↑0\.080\.0847↑0\.050\.1479↓0\.010\.1378↑0\.000\.2401↑0\.040\.2591↑0\.08RAG⋆0\.3386↓0\.060\.3524↓0\.030\.0544↑0\.010\.0740↑0\.040\.1215↓0\.040\.1511↑0\.020\.1715↓0\.030\.1925↑0\.01Summary⋆0\.4149↑0\.020\.5118↑0\.130\.1610↑0\.120\.1053↑0\.070\.1658↑0\.000\.1767↑0\.040\.2472↑0\.050\.2646↑0\.08Reflexion⋆0\.4461↑0\.050\.4295↑0\.040\.2078↑0\.170\.1624↑0\.130\.1628↑0\.000\.2396↑0\.110\.2722↑0\.070\.2772↑0\.09EvoTest⋄0\.4627↑0\.070\.5268↑0\.140\.2073↑0\.170\.1608↑0\.130\.1630↑0\.000\.1914↑0\.060\.2777↑0\.080\.2930↑0\.11ACE⋄0\.2875↓0\.110\.2913↓0\.100\.1847↑0\.140\.1470↑0\.120\.1889↑0\.030\.2188↑0\.090\.2204↑0\.020\.2190↑0\.04APEX⋄0\.4318↑0\.030\.5682↑0\.180\.2250↑0\.190\.1808↑0\.150\.1927↑0\.030\.2055↑0\.070\.2832↑0\.080\.3182↑0\.13Trace0\.4896↑0\.090\.5726↑0\.190\.3742↑0\.330\.3195↑0\.290\.2243↑0\.060\.2476↑0\.110\.3627↑0\.160\.3799↑0\.20GPT\-OSS\-20BStatic†0\.4523↑0\.000\.4189↑0\.000\.0253↑0\.000\.0130↑0\.000\.1731↑0\.000\.1949↑0\.000\.2169↑0\.000\.2089↑0\.00Memory⋆0\.5123↑0\.060\.5567↑0\.140\.0567↑0\.030\.0548↑0\.040\.1530↓0\.020\.1661↓0\.030\.2407↑0\.020\.2592↑0\.05RAG⋆0\.4210↓0\.030\.3812↓0\.040\.0076↓0\.020\.0220↑0\.010\.1058↓0\.070\.0996↓0\.100\.1781↓0\.040\.1676↓0\.04Summary⋆0\.4380↓0\.010\.4915↑0\.070\.1155↑0\.090\.0622↑0\.050\.1497↓0\.020\.1486↓0\.050\.2344↑0\.020\.2341↑0\.03Reflexion⋆0\.4529↑0\.000\.4263↑0\.010\.1105↑0\.090\.0687↑0\.060\.1732↑0\.000\.1877↓0\.010\.2455↑0\.030\.2276↑0\.02EvoTest⋄0\.4529↑0\.000\.5778↑0\.160\.1375↑0\.110\.0971↑0\.080\.1287↓0\.040\.1544↓0\.040\.2397↑0\.020\.2764↑0\.07ACE⋄0\.1728↓0\.280\.1632↓0\.260\.0913↑0\.070\.0413↑0\.030\.1401↓0\.030\.1394↓0\.060\.1347↓0\.080\.1146↓0\.09APEX⋄0\.4654↑0\.010\.5441↑0\.130\.0906↑0\.070\.0613↑0\.050\.1972↑0\.02\-0\.0833↓0\.280\.2511↑0\.030\.1740↓0\.03Trace0\.5143↑0\.060\.5960↑0\.180\.3783↑0\.350\.4927↑0\.480\.2527↑0\.080\.3113↑0\.120\.3818↑0\.160\.4667↑0\.26

## 4Experiments

Figure 2:\(RQ1\-B\)Performance–cost comparison usingGPT\-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 thebestandsecond\-bestperformance\.In this section, we conduct extensive experiments to answer the following research questions:\(RQ1\): How doesTracecompare with strong test\-time learning and memory baselines?\(RQ2\): Does each construction mechanism correctly perform its intended function?\(RQ3\)How do Walkthrough representation and dependency\-aware scheduling affect cross\-episode experience reuse?\(RQ4\): How robust isTrace, and under what conditions does its advantage diminish?

### 4\.1Experimental Setup

#### Datasets and Benchmarks\.

To thoroughly evaluate the effectiveness ofTrace, we adopt three widely\-adopted benchmarks across three domains:\(1\) Interactive Fiction, including J\-TTL\([9](https://arxiv.org/html/2609.22120#bib.bib14);[10](https://arxiv.org/html/2609.22120#bib.bib19)\)\.\(2\) E\-commerce, including WebShop\([32](https://arxiv.org/html/2609.22120#bib.bib2)\)\.\(3\) Scientific Reasoning, including ScienceWorld\([28](https://arxiv.org/html/2609.22120#bib.bib3)\)\. Further experimental details appear in the Appendix\.

#### Baselines\.

We evaluate eight baselines: \(1\)Static; \(2\)Memory\([10](https://arxiv.org/html/2609.22120#bib.bib19)\); \(3\)RAG\([10](https://arxiv.org/html/2609.22120#bib.bib19)\); \(4\)Summary\([10](https://arxiv.org/html/2609.22120#bib.bib19)\); \(5\)Reflexion\([25](https://arxiv.org/html/2609.22120#bib.bib6)\); \(6\)EvoTest\([10](https://arxiv.org/html/2609.22120#bib.bib19)\); \(7\)ACE\([37](https://arxiv.org/html/2609.22120#bib.bib18)\); and \(8\)APEX\([16](https://arxiv.org/html/2609.22120#bib.bib17)\)\.

#### LLM Backbones\.

For instantiating these frameworks, we adopt three open\-source LLMs,Qwen3\-32B,Mistral\-Small\-3\.2\-24B, andGPT\-OSS\-20B\.

#### Metrics\.

We run each game forE=10E=10episodes and report: \(1\)Final\-33, the average normalized score over the last three episodes; \(2\)AUC, following[10](https://arxiv.org/html/2609.22120#bib.bib19), defined asAUC=1E​∑e=1ER⁡\(e\)Rmax\\mathrm\{AUC\}=\\frac\{1\}\{E\}\\sum\_\{e=1\}^\{E\}\\frac\{R\(e\)\}\{R\_\{\\max\}\}, whereR⁡\(e\)R\(e\)is the score obtained in episodeeeandRmaxR\_\{\\max\}is the maximum score achievable in a single episode; \(3\)Replay Success\(RS\), the fraction of attempted Walkthrough executions that reach their specified completion conditions, defined asRS=1Nrep∑i=1Nrep𝕀\[ci=1\]\\mathrm\{RS\}=\\frac\{1\}\{N\_\{\\mathrm\{rep\}\}\}\\sum\_\{i=1\}^\{N\_\{\\mathrm\{rep\}\}\}\\mathbb\{I\}\[c\_\{i\}=1\], whereNrepN\_\{\\mathrm\{rep\}\}is the total number of Walkthrough replay attempts andci=1c\_\{i\}=1if theii\-th replay reaches its completion condition before triggering a failure condition or exhausting its execution budget, andci=0c\_\{i\}=0otherwise; and \(4\)Token Cost, the total number of input and output tokens consumed across all episodes, defined asCost=∑e=1E\(Tein\+Teout\)\\mathrm\{Cost\}=\\sum\_\{e=1\}^\{E\}\\left\(T^\{\\mathrm\{in\}\}\_\{e\}\+T^\{\\mathrm\{out\}\}\_\{e\}\\right\)\.

#### Parameter Configurations\.

For all experiments, we set the LLM temperature to0\.80\.8\. Each task is run for1010episodes, with each episode limited to at most150150environment steps\.

### 4\.2Main Results \(RQ1\)

#### Takeaway11:Traceachieves the best performance across tasks and backbone models\.

As shown in Table[1](https://arxiv.org/html/2609.22120#S3.T1), compared with the strongest baseline in the Avg\. column for each backbone and metric,Traceimproves the average AUC and Final\-3 by30\.0%30\.0\\%and40\.5%40\.5\\%, respectively\. OnQwen3\-32B,Mistral\-Small\-3\.2\-24B, andGPT\-OSS\-20B, the AUC gains are12\.6%12\.6\\%,28\.1%28\.1\\%, and52\.1%52\.1\\%, while the Final\-3 gains are36\.4%36\.4\\%,19\.4%19\.4\\%, and68\.8%68\.8\\%, respectively\. The improvements are most pronounced on J\-TTL, whereTraceincreases AUC and Final\-33by65\.4%65\.4\\%and135\.6%135\.6\\%on average\.

#### Takeaway22:Traceachieves its performance gains without incurring excessive inference cost\.

As shown in Figure[2](https://arxiv.org/html/2609.22120#S4.F2),Traceconsumes only0\.35640\.3564M,2\.32312\.3231M, and1\.08961\.0896M tokens on WebShop, J\-TTL, and ScienceWorld, respectively\. Its token consumption is consistently lower than that of Memory, Summary, Reflexion, EvoTest, ACE, and APEX across all three benchmarks\. More importantly,Traceis also more efficient than the AUC\-best baseline in each setting: it uses23\.6%23\.6\\%fewer tokens than Memory on WebShop,33\.1%33\.1\\%fewer than EvoTest on J\-TTL, and37\.8%37\.8\\%fewer than APEX on ScienceWorld\. These results show that the improvements ofTracearise from more effective cross\-episode experience reuse rather than increased inference expenditure\.

### 4\.3Ablation Study \(RQ2\)

#### Takeaway33: All three construction stages provide complementary and cumulative gains in end\-to\-end performance\.

As shown in Table[2](https://arxiv.org/html/2609.22120#S4.T2), adding Delayed Credit to Immediate Progress Only improves AUC by0\.03810\.0381and Final\-33by0\.04690\.0469on ScienceWorld, while improving AUC by0\.07340\.0734and Final\-33by0\.09750\.0975on J\-TTL\. Prerequisite Estimation provides AUC and Final\-33gains of0\.03880\.0388and0\.04690\.0469on ScienceWorld, and0\.07180\.0718and0\.09140\.0914on J\-TTL\. Backward Dependency Slicing further increases AUC by0\.06860\.0686and Final\-33by0\.08290\.0829on ScienceWorld, and increases AUC by0\.06670\.0667and Final\-33by0\.08550\.0855on J\-TTL\. Overall, the full method exceeds Immediate Progress Only by0\.14550\.1455in AUC and0\.17670\.1767in Final\-33on ScienceWorld, and by0\.21190\.2119in AUC and0\.27440\.2744in Final\-33on J\-TTL\. These cumulative gains show that candidate recovery, prerequisite induction, and dependency\-based pruning jointly improve performance\.

ScienceWorldJ\-TTLDel\.Cred\.Prereq\.Est\.Back\.Slic\.AUC↑\\uparrowFinal\-33↑\\uparrowAUC↑\\uparrowFinal\-33↑\\uparrow✓\\checkmark✓\\checkmark✓\\checkmark0\.2527↑0\.000\.3113↑0\.000\.3783↑0\.000\.4927↑0\.00✓\\checkmark✓\\checkmark×\\times0\.1841↓0\.070\.2284↓0\.080\.3116↓0\.070\.4072↓0\.09✓\\checkmark×\\times×\\times0\.1453↓0\.040\.1815↓0\.050\.2398↓0\.070\.3158↓0\.09×\\times×\\times×\\times0\.1072↓0\.040\.1346↓0\.050\.1664↓0\.070\.2183↓0\.10

Table 2:\(RQ2\)Nested ablation of the three Walkthrough construction stages illustrated in Figure[1](https://arxiv.org/html/2609.22120#S2.F1), evaluated on ScienceWorld and J\-TTL usingGPT\-OSS\-20B\.
![Refer to caption](https://arxiv.org/html/2609.22120v1/rq2_b_executable_scheduling_study.png)Figure 3:\(RQ3\)Effects of executable Walkthrough representation and dependency\-aware scheduling on cross\-episode experience reuse\.All variants use the same nodes, action sequences, prerequisite annotations, dependency edges, memory snapshots, and interaction budgets\.

### 4\.4Case Study\(RQ3\)

#### Takeaway44: Executable representation and dependency\-aware scheduling improve execution efficiency and dependency consistency, respectively, and provide complementary benefits\.

As shown in Figure[3](https://arxiv.org/html/2609.22120#S4.F3), enabling either mechanism alone improves every metric on both ScienceWorld and J\-TTL\. Executable representation primarily reduces execution cost, lowering Actions per Success from29\.429\.4to17\.817\.8on ScienceWorld and from42\.742\.7to21\.921\.9on J\-TTL\. Dependency\-aware scheduling more strongly improves reuse validity: it increases Replay Success by0\.1250\.125and0\.1420\.142, while reducing Prerequisite Violation by0\.1450\.145and0\.2120\.212, on ScienceWorld and J\-TTL, respectively\. Each mechanism provides further gains when added on top of the other, and the full method achieves the best results across all metrics\.

Figure 4:\(RQ4\-A\)Robustness to progress\-signal masking on ScienceWorld and J\-TTL usingGPT\-OSS\-20B\.

### 4\.5Robustness and Sensitivity Study \(RQ4\)

#### Takeaway55: Delayed Credit remains effective under partial masking of non\-terminal progress signals, but relying only on terminal rewards substantially degrades Walkthrough executability and downstream performance\.

As shown in Figure[4](https://arxiv.org/html/2609.22120#S4.F4), masking25%25\\%of the non\-terminal progress signals reduces Replay Success by only0\.0540\.054–0\.0610\.061, while AUC and Final\-33decrease by0\.03330\.0333–0\.05780\.0578and0\.04300\.0430–0\.07310\.0731, respectively\. All three metrics decline consistently as more intermediate signals are removed\. When only terminal rewards are retained, Replay Success decreases by0\.1780\.178–0\.2400\.240, accompanied by substantially larger reductions in AUC and Final\-33\. These results show that Delayed Credit tolerates partially missing progress evidence, whereas intermediate state changes remain essential for constructing executable Walkthroughs and improving subsequent episodes\.

![Refer to caption](https://arxiv.org/html/2609.22120v1/rq4_c_sample_efficiency.png)Figure 5:\(RQ4\-B\)Cross\-episode evidence sample efficiency on ScienceWorld and J\-TTL usingGPT\-OSS\-20B\.
#### Takeaway66: Additional cross\-episode evidence improves endpoint performance within the ten\-episode interaction budget\.

As shown in Figure[5](https://arxiv.org/html/2609.22120#S4.F5), increasing the available history from33to99episodes improves Replay Success, AUC, and Final\-3 by0\.0100\.010,0\.0360\.036, and0\.1100\.110on ScienceWorld, and by0\.1070\.107,0\.1160\.116, and0\.1060\.106on J\-TTL, respectively\. The intermediate results are not strictly monotonic, but the nine\-episode setting outperforms the three\-episode setting on every metric and both benchmarks\. These results show that Prerequisite Estimation can benefit from additional success and failure observations within the practical ten\-episode interaction budget\.

![Refer to caption](https://arxiv.org/html/2609.22120v1/rq4_b_trajectory_noise.png)Figure 6:\(RQ4\-C\)Robustness to trajectory noise on ScienceWorld and J\-TTL usingGPT\-OSS\-20B\.
#### Takeaway77:Traceis robust to trajectory noise, retaining most of its clean\-trajectory performance even under substantial structured redundancy\.

As shown in Figure[6](https://arxiv.org/html/2609.22120#S4.F6), with20%20\\%isolated exploratory actions, the metrics that decrease retain96\.3%96\.3\\%–97\.6%97\.6\\%of their original performance across both benchmarks, while Replay Success on J\-TTL increases from0\.3080\.308to0\.3460\.346\. Under the more challenging setting with20%20\\%loops and backtracking, the method preserves84\.4%84\.4\\%–95\.9%95\.9\\%of its clean\-trajectory performance\. Even when mixed redundancy reaches40%40\\%, it retains83\.2%83\.2\\%–92\.9%92\.9\\%of the corresponding clean values\. These results demonstrate that the Walkthrough construction pipeline effectively suppresses interference from exploration, loops, and backtracking while maintaining stable executability and downstream gains\.

## 5Conclusion

We introduceTraceto learn executable Walkthroughs from noisy, sparse\-reward trajectories for reliable experience reuse\.Tracecombines delayed\-credit propagation, fact\-grounded prerequisite estimation, and backward dependency slicing to extract progress\-enabling action chains\. Empirically, it outperforms the strongest baselines by30\.0%30\.0\\%in AUC and40\.5%40\.5\\%in Final\-33with lower token cost\. Ablations and robustness studies confirm complementary gains from all stages and resilience to trajectory noise\. These results establish state\-conditioned executable procedures as a practical memory unit for efficient, verifiable, and resumable long\-horizon agents\.

## References

- Agasheet al\.\(2025\)S\. Agashe, J\. Han, S\. Gan, J\. Yang, A\. Li, and X\. WangAgent s: an open agentic framework that uses computers like a human\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 22924–22946\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Arumugam and Griffiths \(2026\)D\. Arumugam and T\. L\. GriffithsToward efficient exploration by large language model agents\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=M3vwnscpL2)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Caoet al\.\(2026a\)Z\. Cao, J\. Deng, L\. Yu, W\. Zhou, Z\. Liu, B\. Ding, and H\. ZhaoRemember me, refine me: a dynamic procedural memory framework for experience\-driven agent evolution\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 16803–16822\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1)\.
- Caoet al\.\(2026b\)Z\. Cao, J\. Deng, L\. Yu, W\. Zhou, Z\. Liu, B\. Ding, and H\. ZhaoRemember me, refine me: a dynamic procedural memory framework for experience\-driven agent evolution\.InFindings of the Association for Computational Linguistics: ACL 2026,San Diego, California, United States,pp\. 16803–16822\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.829),[Link](https://aclanthology.org/2026.findings-acl.829/)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Cuiet al\.\(2025\)S\. Cui, A\. He, S\. Xu, H\. Zhang, Y\. Wang, Q\. Zhang, Y\. Wang, and B\. XuSelf\-guided function calling in large language models via stepwise experience recall\.InFindings of the Association for Computational Linguistics: EMNLP 2025,pp\. 10842–10854\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.findings-emnlp.574)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Fanget al\.\(2025\)T\. Fang, H\. Zhang, Z\. Zhang, K\. Ma, W\. Yu, H\. Mi, and D\. YuWebEvolver: enhancing web agent self\-improvement with co\-evolving world model\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 8970–8986\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Geet al\.\(2025\)Y\. Ge, S\. Romeo, J\. Cai, M\. Sunkara, and Y\. ZhangSamule: self\-learning agents enhanced by multi\-level reflection\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 16602–16621\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Hamidiet al\.\(2026\)S\. M\. Hamidi, L\. Ye, and K\. N\. PlataniotisDreamPhase: offline imagination and uncertainty\-guided planning for large\-language\-model agents\.InThe Fourteenth International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Hausknechtet al\.\(2020\)M\. Hausknecht, P\. Ammanabrolu, M\. Côté, and X\. YuanInteractive fiction games: a colossal adventure\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 7903–7910\.Cited by:[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px1.p1.1)\.
- Heet al\.\(2026\)Y\. He, J\. Liu, Y\. Liu, Y\. Li, T\. Cao, Z\. Hu, X\. Xu, and B\. HooiEvoTest: evolutionary test\-time learning for self\-improving agentic systems\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=JFnnajbkvP)Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px4.p1.1)\.
- Huanget al\.\(2025\)T\. Huang, K\. Basu, I\. Abdelaziz, P\. Kapanipathi, J\. May, and M\. ChenR2d2: remembering, replaying and dynamic decision making with a reflective agentic memory\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 30318–30330\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Jianget al\.\(2026\)Y\. Jiang, L\. Jiang, D\. Teney, M\. Moor, and M\. BrbicMeta\-RL induces exploration in language agents\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=4GiBscHW1k)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Kimet al\.\(2026\)M\. Kimet al\.Dual\-scale world memory for llm agents towards hard\-exploration problems\.InThe Fourteenth International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Klissarovet al\.\(2025\)M\. Klissarov, M\. Henaff, R\. Raileanu, S\. Sodhani, P\. Vincent, A\. Zhang, P\. Bacon, D\. Precup, M\. C Machado, and P\. D’OroMaestromotif: skill design from artificial intelligence feedback\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 18029–18057\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Liet al\.\(2026a\)P\. Li, Z\. Gao, B\. Zhang, Y\. Mi, X\. S\. Ma, C\. Shi, T\. Yuan, Y\. Wu, Y\. Jia, S\. Zhu,et al\.Iterative tool usage exploration for multimodal agents via step\-wise preference tuning\.Advances in Neural Information Processing Systems38,pp\. 59496–59528\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Liet al\.\(2026b\)Y\. Li, J\. Yang, Z\. Zheng, Z\. Hu, Y\. Sui, S\. Wang, Y\. He, and B\. HooiAPEX: autonomous policy exploration for self\-evolving llm agents\.arXiv preprint arXiv:2605\.21240\.Cited by:[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px2.p1.1)\.
- Lianget al\.\(2026a\)D\. Liang, C\. Zhang, X\. Xu, J\. Ju, Z\. Luo, and X\. BaiCook and clean together: teaching embodied agents for parallel task execution\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 18415–18424\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Lianget al\.\(2026b\)S\. Liang, P\. Cao, J\. Zhao, W\. Teng, X\. Liao, J\. Zhao, and K\. LiuLearning how to remember: a meta\-cognitive management method for structured and transferable agent memory\.InFindings of the Association for Computational Linguistics: ACL 2026,San Diego, California, United States,pp\. 30733–30753\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1535),[Link](https://aclanthology.org/2026.findings-acl.1535/)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Lianget al\.\(2026c\)S\. Liang, P\. Cao, J\. Zhao, W\. Teng, X\. Liao, J\. Zhao, and K\. LiuLearning how to remember: a meta\-cognitive management method for structured and transferable agent memory\.arXiv preprint arXiv:2601\.07470\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1)\.
- Liuet al\.\(2026\)Z\. Liu, J\. Kim, X\. Luo, D\. Li, and Y\. YangExploratory memory\-augmented LLM agent via hybrid on\- and off\-policy optimization\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=UOzxviKVFO)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Nielsenet al\.\(2026\)S\. Nielsen, E\. Cetin, P\. Schwendeman, Q\. Sun, J\. Xu, and Y\. TangLearning to orchestrate agents in natural language with the conductor\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=U23A2BUKYt)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Qiet al\.\(2025\)Z\. Qi, X\. Liu, I\. L\. Iong, H\. Lai, X\. Sun, J\. Sun, X\. Yang, Y\. Yang, S\. Yao, W\. Xu,et al\.Webrl: training llm web agents via self\-evolving online curriculum reinforcement learning\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 79791–79821\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Qinet al\.\(2026\)Y\. Qin, X\. Tan, Z\. He, G\. Li, H\. Lin, Z\. Li, Z\. Xu, Y\. Shi, S\. Cai, R\. Rui, S\. Cai, Y\. Cai, X\. Zhang, S\. Ye, K\. Li, and X\. SunLearn the ropes, then trust the wins: self\-imitation with progressive exploration for agentic reinforcement learning\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Kssko33Ekq)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Ranaldi \(2026\)L\. RanaldiEvolving agents\.InProceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 16561–16569\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.acl-long.754)Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Shinnet al\.\(2023\)N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. YaoReflexion: language agents with verbal reinforcement learning\.Advances in Neural Information Processing Systems36,pp\. 8634–8652\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1),[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px2.p1.1)\.
- Sunet al\.\(2026\)L\. Sun, J\. Zhang, S\. Wang, and Z\. WeiMAGNET: towards adaptive GUI agents with memory\-driven knowledge evolution\.InProceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 28181–28206\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.acl-long.1299)Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Tanet al\.\(2025\)W\. Tan, W\. Zhang, X\. Xu, H\. Xia, Z\. Ding, B\. Li, B\. Zhou, J\. Yue, J\. Jiang, Y\. Li, R\. An, M\. Qin, C\. Zong, L\. Zheng, Y\. Wu, X\. Chai, Y\. Bi, T\. Xie, P\. Gu, X\. Li, C\. Zhang, L\. Tian, C\. Wang, X\. Wang, B\. F\. Karlsson, B\. An, S\. Yan, and Z\. LuCradle: empowering foundation agents towards general computer control\.InProceedings of the 42nd International Conference on Machine Learning,External Links:[Link](https://proceedings.mlr.press/v267/tan25h.html)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Wanget al\.\(2022\)R\. Wang, P\. Jansen, M\. Côté, and P\. AmmanabroluScienceworld: is your agent smarter than a 5th grader?\.InProceedings of the 2022 Conference on Empirical Methods in Natural Language Processing,pp\. 11279–11298\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px1.p1.1)\.
- Wanget al\.\(2026\)T\. Wang, P\. Xu, S\. Cao, L\. Yang, D\. Li, J\. Jiao, and K\. HuangSAMem: state\-aware memory as a fine\-grained memory for llm agents in decision\-making\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 14691–14710\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Xiaoet al\.\(2026\)H\. Xiao, G\. Wang, Y\. Chai, Z\. Lu, W\. Lin, H\. He, L\. Fan, L\. Bian, R\. Hu, L\. Liu,et al\.Ui\-genie: a self\-improving approach for iteratively boosting mllm\-based mobile gui agents\.Advances in Neural Information Processing Systems38,pp\. 150376–150411\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Yanget al\.\(2026\)S\. Yang, C\. Han, Y\. Ding, S\. Wang, and E\. HovyTooltree: efficient llm tool planning via dual\-feedback monte carlo tree search and bidirectional pruning\.InThe Fourteenth International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Yaoet al\.\(2022\)S\. Yao, H\. Chen, J\. Yang, and K\. NarasimhanWebshop: towards scalable real\-world web interaction with grounded language agents\.Advances in Neural Information Processing Systems35,pp\. 20744–20757\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px1.p1.1)\.
- Yinet al\.\(2025\)X\. Yin, X\. Wang, L\. Pan, L\. Lin, X\. Wan, and W\. Y\. WangGödel agent: a self\-referential agent framework for recursively self\-improvement\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 27890–27913\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Zhanget al\.\(2026a\)G\. Zhang, M\. Fu, K\. Wang, F\. Wan, M\. Yu, and S\. YanG\-memory: tracing hierarchical memory for multi\-agent systems\.Advances in Neural Information Processing Systems38,pp\. 12988–13018\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1),[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2025a\)J\. Zhang, J\. Xiang, Z\. Yu, F\. Teng, X\. Chen, J\. Chen, M\. Zhuge, X\. Cheng, S\. Hong, J\. Wang,et al\.Aflow: automating agentic workflow generation\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 34040–34077\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.
- Zhanget al\.\(2025b\)Q\. Zhang, C\. Hu, S\. Upasani, B\. Ma, F\. Hong, V\. Kamanuru, J\. Rainton, C\. Wu, M\. Ji, H\. Li,et al\.Agentic context engineering: evolving contexts for self\-improving language models\.arXiv preprint arXiv:2510\.04618\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p3.1)\.
- Zhanget al\.\(2026b\)Q\. Zhang, C\. Hu, S\. Upasani, B\. Ma, F\. Hong, V\. Kamanuru, J\. Rainton, C\. Wu, M\. Ji, H\. Li, U\. Thakker, J\. Zou, and K\. OlukotunAgentic context engineering: evolving contexts for self\-improving language models\.InInternational Conference on Learning Representations,Cited by:[§4\.1](https://arxiv.org/html/2609.22120#S4.SS1.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2026c\)W\. Zhang, X\. Zhang, H\. Yu, S\. Nie, B\. Wu, J\. Yue, T\. Liu, and Y\. LiExpSeek: self\-triggered experience seeking for web agents\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 29255–29283\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1462)Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2026d\)Z\. Zhang, W\. Bu, K\. Pan, B\. Miao, W\. Zhang, G\. Wang, W\. Ji, R\. Tang, J\. Li, and S\. TangEvolving generalist virtual agents with generative and associative memory\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 13006–13014\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px2.p1.1)\.
- Zhaoet al\.\(2024\)A\. Zhao, D\. Huang, Q\. Xu, M\. Lin, Y\. Liu, and G\. HuangExpeL: llm agents are experiential learners\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 19632–19642\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v38i17.29936)Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1),[§1](https://arxiv.org/html/2609.22120#S1.p3.1)\.
- Zhaoet al\.\(2025\)D\. Zhao, L\. Ma, S\. Wang, M\. Wang, and Z\. LvCOLA: collaborative multi\-agent framework with dynamic task scheduling for gui automation\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 4570–4593\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px3.p1.1)\.
- Zhouet al\.\(2024\)S\. Zhou, F\. F\. Xu, H\. Zhu, X\. Zhou, R\. Lo, A\. Sridhar, X\. Cheng, T\. Ou, Y\. Bisk, D\. Fried,et al\.Webarena: a realistic web environment for building autonomous agents\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 15585–15606\.Cited by:[§1](https://arxiv.org/html/2609.22120#S1.p1.1)\.
- Zhouet al\.\(2026\)Y\. Zhou, S\. Levine, J\. Weston, X\. Li, and S\. SukhbaatarSelf\-challenging language model agents\.Advances in Neural Information Processing Systems38,pp\. 113959–113991\.Cited by:[§2](https://arxiv.org/html/2609.22120#S2.SS0.SSS0.Px1.p1.1)\.