acceptodds
Under review as a conference paper at ICLR 2027

ReTrace: Fast Adaptation via Slow Contextual Meta-Learning for Web Traversal Agents

Abstract

Humans rarely solve search problems by persisting along a single path. When progress stalls, they adjust their search, reflect on what failed, and recover from unsuccessful attempts. They also retain what successful recovery teaches them and reuse it later. Web traversal agents often struggle to adapt when search progress stalls, while lessons from failure and recovery are rarely consolidated into reusable guidance. We introduce ReTrace, a two-timescale contextual meta-learning framework for web traversal agents that couples fast metacognitive adaptation with slow experience consolidation. At the fast timescale, ReTrace treats how to adapt search behavior as a meta-decision: the agent coordinates traversal, recovery, and reflection to navigate the web, recover from unsuccessful attempts, and reflect on failures to adapt within a task. These adaptations yield informative traces of search, recovery, and reflection. At the slow timescale, a meta-learning harness uses these traces together with task-level ground-truth feedback to attribute successful behavioral changes, consolidate them into three reusable skills—Traversal Skill, Recovery Skill, and Reflection Skill—and organize these skills into a contextual scaffold for future tasks. In ReTrace, the fast agent produces adaptive traces, the slow harness turns these traces into context, and the evolved context improves subsequent fast adaptation. On WebWalkerQA with matched search budgets, fast adaptation raises pass@4 from 47.17% to 65.09%. Adding slow contextual meta-learning further improves V-GEMS QA pass@1 from 47.14% to 55.00% and WebWalkerQA pass@4 from 65.09% to 66.98%, suggesting that learned experience improves both the initial search policy and subsequent fast adaptation.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
Web Traversal Agents, Contextual Meta-Learning, Fast Adaptation, Recovery Traces, Metacognitive Adaptation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_wHjhOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Summary

This paper proposes ReTrace, a two-timescale framework for web traversal agents that combines task-internal recovery with cross-task consolidation of recovery experience. The method aims to improve web navigation by enabling agents to backtrack, explore alternative branches, reflect on failed attempts, and reuse successful recovery strategies in subsequent tasks. The paper evaluates the framework on WebWalkerQA and V-GEMS and includes ablations of its fast adaptation and slow learning components.

Critical strengths

Strengths

  1. A well-motivated framework that addresses both local recovery and cross-task learning. The paper identifies two complementary limitations of existing web agents: their tendency to persist along unproductive trajectories and their inability to systematically reuse lessons from previous failures. The two-timescale design provides a coherent framework for studying these issues, rather than treating reflection, backtracking, and memory as isolated heuristics.

  2. Comprehensive empirical evaluation with systematic component analysis. The experiments compare the full framework with task-internal fast adaptation and slow-learned skills separately, examine different recovery budgets, and report both task success and computational costs. The reported results show that Full ReTrace improves WebWalkerQA pass@4 to 66.98%, compared with 47.17% for WebWalker and 65.09% for Fast alone. The additional transfer evaluation and failure analysis strengthen the empirical characterization of the method.

  3. Useful analysis beyond aggregate success rates. The paper examines recovery behavior, the efficiency trade-off between additional reasoning and fewer environment actions, and the types of failures that remain after applying ReTrace. This analysis helps clarify when recovery is useful and why some tasks remain unsolved, making the work more informative than a method paper supported only by an overall benchmark score.

Critical weaknesses

Weaknesses

  1. The contribution of slow cross-task learning is less convincing than that of fast recovery. On WebWalkerQA, the full method improves pass@4 by only 1.89 percentage points over Fast alone (66.98% versus 65.09%). Although the gain on V-GEMS is larger, the current results suggest that much of the improvement on the main benchmark may come from task-local recovery rather than the proposed cross-task meta-learning mechanism. A stronger analysis of when the slow-learned scaffold provides benefits beyond retaining or retrieving successful recovery episodes would make the central methodological contribution more convincing.

  2. The evaluation provides limited evidence of generalization across agent configurations and task distributions. The experiments primarily use one model family and two web-traversal QA benchmarks. Moreover, the WebWalkerQA evaluation retains tasks that pass an annotated-path reachability audit. While this audit helps separate interface accessibility from reasoning ability, the resulting task distribution may not fully represent the broader range of real-world web navigation problems. Evaluation with additional backbones, more diverse task types, and less structured environments would better establish the generality of the approach.

  3. The practical availability and cost of the slow-learning feedback signal require further clarification. The slow-learning process uses task-level ground-truth feedback to determine which behavioral changes should be consolidated. Such feedback is convenient in controlled benchmarks but may not be readily available in real deployments. The paper would be stronger with a clearer account of the supervision and evaluation costs required for scaffold updates, and with experiments establishing whether reliable cross-task improvement persists when task-level ground truth is replaced by weaker or delayed feedback.

Questions for authors
  1. Clarification The paper compares ReTrace with a structured Experience Bank under the same executor, fast-recovery mechanism, model, budget, and evaluator. Could the authors clarify whether the two methods are also matched in terms of update frequency, context/token budget, and the amount of historical information available at each decision? This clarification is important for determining whether the reported gains come from the proposed slow-learning and consolidation mechanism rather than differences in information access or computational resources.

  2. Assessment-critical evidence The WebWalkerQA evaluation retains tasks that pass an annotated-path reachability audit. How many tasks are excluded by this filtering, and how sensitive are the reported improvements to the audit criteria? In particular, does the relative advantage of ReTrace remain similar when evaluated on the full original task set, with interface-inaccessible tasks reported separately? This would help assess whether the measured gains reflect general recovery capability or are partly influenced by the selected task distribution.

4 comments

We thank the reviewer for recognizing our clear presentation, two-timescale design, and computational cost analysis.

Weaknesses

W1. Slow Learning's independent contribution and complementarity with Fast Recovery. Fast detects stagnation, rolls back, and reflects within tasks; Slow consolidates search and recovery into reusable guidance. With Fast disabled, Slow achieves 49.06% WebWalkerQA pass@1 versus Fast's 48.11%. On frozen V-GEMS, Slow reaches 49.29% versus Fast's 47.14%, demonstrating an independent search prior.

Slow also advances success and improves Fast's efficiency. On WebWalkerQA, Full ReTrace raises pass@1 from 48.11% (Fast) to 50.00%, while reducing total actions by ~8.3%, navigation actions by 9.76%, LLM calls by 8.3%, and total tokens by 14.0% relative to Fast. At pass@4, Full reaches 66.98% versus Fast's 65.09%, using ~7.9% fewer total tokens. Fast recovers; Slow guides branch selection, evidence use, and post-recovery search.

We added frozen V-GEMS pass@2–pass@4 to assess retry budgets (%, WW=WebWalkerQA; VG=V-GEMS):

MethodWW@1WW@2WW@3WW@4VG@1VG@2VG@3VG@4
Baseline44.3445.2847.1747.1745.7147.1450.0053.57
Fast48.1158.4964.1565.0947.1449.2852.8657.14
Slow49.0660.3860.3861.3249.2955.7156.4356.43
Fast + Slow50.0061.3265.0966.9855.0056.4359.2960.71

On V-GEMS, Full exceeds Fast by 7.86 points at pass@1 (55.00% vs. 47.14%) and 3.57 at pass@4 (60.71% vs. 57.14%). The larger first-run gain reflects improved initial search; benefits vary with task distribution and retry budget.

Why learn a scaffold rather than retrieve successful traces? We added Agent Workflow Memory (AWM) and ReasoningBank comparisons alongside Experience Bank:

MethodWW@1WW@2WW@3WW@4VG@1
Full ReTrace50.0061.3265.0966.9855.00
AWM31.1334.9136.7938.6852.86
ReasoningBank33.0233.0235.8536.7953.57
Experience Bank40.5750.9455.6661.3237.86

AWM and ReasoningBank retrieve past knowledge. Experience Bank shares the Executor, Fast Recovery, backbone, budget, and Evaluator, retrieving evaluated episodes and task/subtask procedural skills. ReTrace uses Evidence Analysis, Synthesis, and Review to compare failed and corrected searches and consolidate recurring lessons into persistent strategies with observable triggers, actions, and stopping conditions, excluding task-specific URLs, answers, and details. Thus, retrieval differs from consolidation. Full exceeds Experience Bank by 5.66 points on WebWalkerQA pass@4 (66.98% vs. 61.32%) and 17.14 on frozen V-GEMS pass@1 (55.00% vs. 37.86%). Fast supplies recovery traces; Slow guides later Fast adaptation.

W2. Generalization across backbones and task distributions. With DeepSeek-v4.1-flash, we evolved on WebWalkerQA and froze the scaffold for 140 V-GEMS tasks:

MethodWW@1WW@2WW@3WW@4VG@1
Baseline53.7758.4962.2664.1542.14
Fast54.7262.2666.0467.9242.85
Slow55.6663.2166.9867.9244.28
Fast + Slow58.4964.1566.9868.8745.71

Full improves WebWalkerQA pass@1 by 4.72 points over Baseline and 3.77 over Fast; frozen V-GEMS pass@1 reaches 45.71% versus 42.14%, 42.85%, and 44.28% for Baseline, Fast, and Slow.

We also reversed transfer, evolving on V-GEMS and freezing the scaffold for WebWalkerQA:

MethodVG@1VG@2VG@3VG@4WW@1 frozen
Baseline45.7147.1450.0053.5744.34
Fast47.1449.2852.8657.1448.11
Slow47.1447.8650.7154.2946.23
Fast + Slow47.8650.7153.5758.5749.06

Full reaches 58.57% V-GEMS pass@4 (Baseline 53.57%; Fast 57.14%) and 49.06% frozen WebWalkerQA pass@1 (Baseline 44.34%; Fast 48.11%; Slow 46.23%). These tests show transfer across backbones and both dataset directions.

W3. Feedback granularity, availability, and update cost. Slow uses delayed task-level outcomes, not step-level labels. The Evaluator provides no correct paths or branch, rollback, or scaffold-edit instructions. Fast judges stagnation and selects rollback/reflection during execution; Slow analyzes completed trajectories and outcomes afterward. Both benchmarks allow factual answers to be checked against references without expert step annotations. Ground truth never guides live navigation. WebWalkerQA updates affect only later tasks; V-GEMS transfer freezes the Scaffold. Costs include task evaluation and Evidence Analysis, Synthesis, and Review calls per window. A fixed Scaffold budget bounds injected context as history grows; costs appear in the paper.

Questions

Q1. Experience Bank: update frequency, context budget, and historical information availability. Experience Bank and ReTrace use the same Executor, Fast Recovery mechanism, backbone, interaction budget, and Evaluator. Both use completed-task experience without future outcomes; they differ in how they organize it.

Experience Bank stores evaluator-validated historical episodes plus task-level and subtask-level Procedural Skills, retrieving relevant entries for each new task. It attempts cross-task memory consolidation after each evaluated task. ReTrace instead runs Evidence Analysis, Synthesis, and Review after each batch of completed WebWalkerQA tasks, extracting recurring decision principles into a versioned Scaffold. Only an approved Scaffold is published for later tasks. The Executor sees this version, not the analysis ledger or historical trajectories.

AspectExperience BankReTrace Slow
WebWalkerQA updateAttempts memory consolidation after each scored taskOne evolution process after each batch of completed tasks; publish after approval
V-GEMSDatabase frozen; retrieval only, no writesScaffold frozen; no evolution
Knowledge injectedTop-5 experience skills and related lessons, entry-limitedOnly published Scaffold
Context limitPer-entry limitsFixed 1,115-token publication target; 1,239-token reference metadata
Actual Scaffold length—WebWalkerQA nonempty versions ~322–445 tokens; frozen V-GEMS 584 tokens
Executor limits≤30 steps; max_tokens=4096 per generation≤30 steps; max_tokens=4096 per generation

The 1,115-token publication ceiling is fixed across WebWalkerQA evolution; 1,239 tokens is reference metadata. The Bank retrieves up to five skills and related lessons under entry-level limits; Slow publishes a compact consolidated policy.

Slow compares unsuccessful search and corrected behavior through Evidence Analysis, Synthesis, and Review. It translates reusable patterns into conditional strategies with observable triggers, specific actions, and stopping conditions, excluding task-specific URLs, answers, and examples. The Bank retains and retrieves relevant historical episodes and procedural skills. Results reflect this distinction: Full ReTrace's WebWalkerQA pass@4 of 66.98% versus Experience Bank's 61.32%, and frozen V-GEMS pass@1 of 55.00% versus 37.86%. Both use the shared runtime and freeze persistent experience during V-GEMS transfer.

Q2. WebWalkerQA reachability filtering and its impact. The reachability audit separates failures caused by agent search decisions from non-executable paths under the current WebWalker interface. Live sites change: pages move, links expire, access becomes restricted, button mappings change, and fetching may fail. Thus an annotated path may no longer be reproducible.

The criterion is whether an annotated path can be executed through the current interface, not whether an agent answers its question correctly. The audit does not run an answering agent, use model accuracy to select questions, or consult Baseline/ReTrace outcomes when deciding which tasks to retain. Every method is evaluated on the same retained task set. Retention is determined before model evaluation. The audit replays the annotated reference route, not an agent-generated trajectory. A failed path replay records an interface or access obstacle; it does not constitute an incorrect predicted answer. This separates environmental executability from the search policy being measured, while keeping the evaluated task subset identical across methods.

The audit checks starting-page availability, replays annotated navigation actions, and records missing links/buttons and fetch failures. WebWalker fetches pages, converts content to text, and exposes navigable links as buttons. Changing sites or interface-level mapping and access restrictions can therefore prevent execution of particular annotated steps. It checks execution, not branch quality or alternative solving routes.

We additionally conducted experiments beyond the original filtered WebWalkerQA task distribution. First, with the WebWalkerQA-learned Scaffold frozen on V-GEMS, we evaluated pass@1–pass@4: Full ReTrace achieves 55.00/56.43/59.29/60.71%, versus Fast's 47.14/49.28/52.86/57.14%. The +7.86-point pass@1 and +3.57-point pass@4 gains show transfer under distinct retry budgets. Second, replacing the backbone with DeepSeek-v4.1-flash gives 45.71% frozen V-GEMS pass@1 for Full versus 42.14% for Baseline, 42.85% for Fast, and 44.28% for Slow. Third, we reversed the transfer direction: evolving on V-GEMS and freezing the Scaffold for WebWalkerQA gives Full 49.06% pass@1 versus 44.34% (Baseline), 48.11% (Fast), and 46.23% (Slow). These complementary tests examine whether the learned prior remains useful across backbone choices, experience sources, target distributions, and retry budgets, beyond the original filtered tasks.

Thank you again for your constructive feedback. In our rebuttal, we added analyses on Slow’s independent contribution, comparisons with AWM, ReasoningBank, and Experience Bank, cross-backbone and reverse cross-dataset transfer, and further clarification of feedback, context budget, and evolution costs.

We would greatly appreciate your thoughts on whether these results adequately address your concerns and resolve the remaining uncertainty. If so, we hope the additional evidence can help strengthen your confidence in the soundness and generality of our approach.

Reviewer wHjh

We appreciate your positive assessment, particularly your recognition of our two-timescale design, the complementary roles of Fast and Slow, and our empirical analyses. Your questions have also helped us identify aspects warranting further investigation.

In response, we added experiments on Slow's independent contribution, cross-model and cross-dataset generalisation, and comparison fairness. We sincerely hope these results further clarify the distinct value of Slow beyond task-level recovery and address your remaining concerns. As the discussion period draws to a close, we would be most grateful for any further thoughts you might wish to share.
Reviewer_qJM1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a framework that combines fast and slow adaptation to improve search trajectories in web agents. During execution, Fast assesses whether the current path is worth pursuing. When necessary, it returns to an earlier node, removes context from the failed branch, and uses reflection to redirect the search. After multiple tasks have been completed, Slow draws on execution traces and outcome feedback to update reusable skills for subsequent tasks. The framework does not update model parameters.

Critical strengths
  1. The approach is intuitive: it stops unproductive exploration and reuses lessons from recovery to guide subsequent searches. It shows improvements with the model and environment evaluated in the paper.
  2. Section 3 and the appendix describe the method in detail, particularly state rollback, context restoration, and budget management. These components are reasonably well specified.
  3. The Fast/Slow ablations and cross-dataset evaluation with frozen skills provide evidence that the gains extend beyond reflection within the current task.
Critical weaknesses
  1. The evaluation is small, covering only 106 WebWalkerQA tasks and 140 V-GEMS tasks after filtering. On WebWalkerQA, adding Slow to Fast improves pass@4 by only 1.89 percentage points, equivalent to two additional solved tasks. Without repeated experiments or confidence intervals, the stability of this gain remains unclear.

  2. The experiments use only qwen3.5-plus. It is unclear whether the approach yields similar gains across models with different capabilities, particularly those that already have strong recovery capabilities.

  3. Additional controls would help establish the contribution of the proposed mechanisms. These could include manually written skills of comparable length, skills derived solely from complete trajectories, and simpler rollback mechanisms.

  4. The cost claims require further clarification. At WebWalkerQA pass@4, the full method consumes more total tokens per successful task than the baseline. The cost of Slow’s experience consolidation is also not clearly accounted for. Fewer actions do not necessarily imply lower overall cost.

Questions for authors
  1. Could the authors provide results with additional models?
  2. How does the method compare with manually written, broadly applicable static skills and with skills derived solely from complete trajectories?
  3. Would evolving skills on V-GEMS and then freezing them for evaluation on WebWalkerQA also yield gains?
  4. Do the reported costs include Slow’s analysis, synthesis, and review stages? Does the method retain an advantage under the same total computational budget?
3 comments

We thank the reviewers for recognizing ReTrace's design, implementation, and Fast/Slow complementarity. We add cross-model results, five controls, reverse frozen transfer, and equal-total-cost analysis including Slow evolution.

W1&Q1. Additional models

Beyond the original Qwen3.5-Plus, we evaluate ReTrace on DeepSeek-v4.1-flash, evolving skills online on WebWalkerQA and transferring the frozen skills to V-GEMS.

MethodWebWalkerQA p@1/2/3/4V-GEMS p@1
Baseline53.77/58.49/62.26/64.1542.14
Fast54.72/62.26/66.04/67.9242.85
Slow55.66/63.21/66.98/67.9244.28
Fast+Slow58.49/64.15/66.98/68.8745.71

Full ReTrace improves WebWalkerQA pass@4 from 64.15% to 68.87% (+4.72 pp) and frozen V-GEMS pass@1 from 42.14% to 45.71% (+3.57 pp); Fast and Slow individually also exceed baseline on both datasets.

W2&Q2. Human-written skills and full-trajectory comparisons

To compare structured recovery with prompting, aggregation, and retrieval, we add five controls:

  1. Human-written Skill: Web traversal guidance covering question understanding, navigation, evidence acquisition/verification, path adjustment, and stopping.
  2. Merged Trajectories: merge all runs per task into one task-level record before skill extraction.
  3. Success-only: extract skills only from successful trajectories.
  4. Failure-only: extract skills only from failed trajectories.
  5. RAG: index chunks of visited webpages; upon backtracking, retrieve the top three BM25 passages using question keywords and inject them with source URLs into subsequent context.
MethodWebWalkerQA p@1/2/3/4V-GEMS p@1
ReTrace50.00/61.32/65.09/66.9855
Human-written Skill36.79/41.51/43.40/45.2832.14
Merged Trajectories37.74/47.17/55.66/56.6037.14
Success-only39.62/50.00/56.60/57.5537.14
Failure-only35.85/48.11/54.72/58.4936.43
RAG43.40/50.94/55.66/59.4347.86

ReTrace beats all controls. Versus best control RAG, WebWalkerQA pass@4 rises 59.43%→66.98% (+7.55 pp), and V-GEMS pass@1 47.86%→55.00% (+7.14 pp).

Three findings support structured learning. (1) Recovery events provide finer evidence than merged task trajectories: the failed branch, task-local reflection, and post-recovery search let Slow compare strategy changes rather than summarize final execution; ReTrace exceeds Merged Trajectories by 10.38 pp on WebWalkerQA pass@4. (2) Combining successful and failed cases with task feedback and before/after-recovery comparisons identifies strategies to retain, discard, or adjust; gains over Success-only and Failure-only are 9.43 and 8.49 pp. (3) Reusable decision rules outperform direct retrieval here: ReTrace distills recurrent cross-task patterns into contextual scaffolds with triggers, actions, and stopping conditions guiding later searches. Section 4.5 also compares structured vs. Raw-branch Recovery: with Outer Reflection under 30 steps, first-run success is 50.00% vs. 38.68% (+11.32 pp).

W3&Q3. Reverse frozen transfer: V-GEMS→WebWalkerQA

Beyond WebWalkerQA-to-V-GEMS transfer, we evolve skills online on V-GEMS using the same pass@4 protocol, then freeze and test them on WebWalkerQA without target updates.

MethodV-GEMS p@1/2/3/4WebWalkerQA frozen p@1
Baseline45.71/47.14/50.00/53.5744.34
Fast47.14/49.28/52.86/57.1448.11
Slow47.14/47.86/50.71/54.2946.23
Fast+Slow47.86/50.71/53.57/58.5749.06

Full ReTrace reaches 58.57% V-GEMS pass@4 vs. baseline 53.57%. Frozen WebWalkerQA pass@1 is 49.06%, +4.72 pp over baseline and above Fast-only (48.11%) and Slow-only (46.23%). Thus both transfer directions show gains.

W4&Q4. Slow evolution cost and equal total budgets

Section 4.6 reports solving-time LLM calls, tokens, and environment interactions. We now count Slow's Analysis, Synthesis, and Review alongside Solving. Across WebWalkerQA tasks, one-time evolution costs 8.154M tokens for Slow-only (7.483M Analysis, 0.365M Synthesis, 0.306M Review) vs. 6.497M for Full ReTrace (5.147M, 0.729M, 0.621M), all included in total cost. V-GEMS uses frozen WebWalkerQA skills: target evaluation adds no Analysis/Synthesis/Review, while source evolution is counted above.

Using observed pass@1–pass@4, we compare maximal cumulative success under identical total-cost caps, including Solving and evolution. On WebWalkerQA, Full ReTrace achieves 65.09% at pass@3 for 51.251M tokens; Fast needs 59.808M at pass@4 for the same success, so Full ReTrace costs 14.31% less including all Slow stages. At a 51.251M cap, Full ReTrace reaches 65.09% vs. Fast 64.15% and Slow-only 61.32%; at 61.551M, 66.98% vs. 65.09% and 61.32%. Full ReTrace therefore retains a better performance-cost tradeoff in these budget ranges after full Slow overhead.

Thank you again for your constructive feedback. In our rebuttal, we added evaluations on DeepSeek-v4.1-flash, comparisons with human-written skills, trajectory-based learning, and RAG, as well as reverse cross-dataset transfer experiments.

We also accounted for all Slow-loop evolution costs and provided equal-total-token-budget comparisons. We would greatly appreciate your thoughts on whether these additional results adequately address your concerns.

Dear Reviewer qJM1:

As the discussion period draws to a close, we very much appreciate the opportunity for this constructive exchange, which we believe is valuable in fostering a collaborative research community. We sincerely hope that our additional experiments, including evaluations with another model, comparisons with alternative skill construction and retrieval strategies, reverse cross-dataset transfer, and further cost analyses under matched budgets, have helped to address the concerns raised and provide a clearer understanding of our approach.

We are sincerely grateful for the opportunity to engage in this constructive exchange, which we have found most valuable. Should you have any further thoughts or observations, we would very much welcome hearing them. Likewise, should any aspects of our responses warrant further clarification, we would be more than pleased to elaborate while the discussion remains open.
Reviewer_iZWMOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

ReTrace designs a combination of a fast loop and a slow loop for improving web traversal agents. The fast loop is a harness loop where a model judge detects stagnation, rolls back to before the stagnation and then retries with a reflection. The slow loop is a skill-file evolution where the skill file gets updated during training and then injected during test time. The paper shows that both designs improve search performance and reinforce each other.

Critical strengths
  • The proposed method is sensible and the paper is easy to follow
  • The method tests transfer to another benchmark (beyond WebWalker the training dataset).
  • Cost reporting in LLM calls.
Critical weaknesses

The paper does not provide sufficient baselines to compare against and does not have a equal-token-budget comparison for the Fast component. Specifically, for the Fast component, there is only 1 baseline WebWalker. For the Slow component, there are also many closely related methods such as ACE, GEPA, AWM, ReasoningBank and none are directly compared against.

Questions for authors
  • Does the WebWalker baseline include the critic agent or just the explorer agent?
  • How accurate is the stagnation judge?
  • Could the stagnation judge model be replaced by rules?
3 comments

We thank the reviewer for the constructive feedback. We add experiments on baseline coverage, compute fairness, and the need for the LLM-based Stagnation Judge.

W1. Equal-token-budget comparison and related methods

Figure 8 reports recorded LLM token usage normalized per task and per successful task, accumulated through pass@k. We also include every online LLM call, including control overhead, for matched-budget and matched-success comparisons.

Equal token cap. On V-GEMS pass@1, all methods have the same 200k-token cap per task. Fast+Slow reaches 50.00%, above Baseline (39.29%–45.00%), Fast (45.00%–46.43%), and Slow (48.57%). Thus, Fast+Slow performs best under the identical per-task cap: the improvement cannot be attributed simply to a larger inference budget.

Tokens at the same target success rate. For WebWalkerQA pass@4, we set 50% task success as the reference target and compare token consumption (k) for the executor alone, executor plus control, and all online LLM calls:

MethodExecutorExecutor + controlAll online LLM
Baseline*>588.27>588.27>616.25
Fast45.74118.56135.28
Slow77.3677.3696.89
Fast+Slow44.02116.36128.36

Baseline never reaches 50% (final pass@4: 47.17%); reported costs are observed lower bounds. Fast+Slow reaches 50% with 44.02k executor tokens or 128.36k including all online LLM calls; Baseline remains below 50% after 616.25k. This contrast shows that ReTrace's gain is driven by better exploration and recovery rather than simply more inference tokens.

To address coverage of related experience-based baselines, we further directly compare ReTrace with AWM and ReasoningBank:

MethodWebWalkerQA p@1WebWalkerQA p@4V-GEMS p@1
ReTrace5066.9855
AWM31.1338.6852.86
ReasoningBank33.0236.7953.57

On WebWalkerQA pass@1, ReTrace exceeds AWM and ReasoningBank by 18.87 and 16.98 percentage points, respectively; it also achieves higher V-GEMS pass@1 than both methods. In some failed cases, AWM and ReasoningBank continue exploring despite having potentially sufficient information to answer, eventually exhausting the step budget without a timely final answer. Thus, complex web traversal requires both experience reuse and timely detection of unproductive exploration to adjust execution. ReTrace combines Fast Loop online recovery with Slow Loop experience accumulation to coordinate exploration, recovery, and completion.

Q1. WebWalker baseline clarification

Our WebWalker baseline implements the complete Explorer + Critic architecture, rather than evaluating only the Explorer Agent, matching the original WebWalker setup.

Q2. Stagnation Judge accuracy

We evaluate the Judge at the recovery-event level using annotated Golden Paths (info.golden_path) as the reference. A branch is positive when its action sequence is not a prefix of any Golden Path; predicted positive means REROUTE (continuation score < 5).

DatasetMethodTPFPFNPrecisionRecall
V-GEMS p@1Fast58110898.31%34.94%
V-GEMS p@1Fast+Slow84216597.67%33.73%
WebWalkerQA p@1Fast82439495.35%17.23%
WebWalkerQA p@1Fast+Slow89234397.80%20.60%

The Judge attains 95%–98% precision against Golden Paths, with only 1–4 false-positive recoveries per setting. Its lower recall reflects a conservative decision policy: deviating from an annotated path does not automatically trigger immediate recovery. Combined with ReTrace's higher task success than rule-based alternatives, these results support our design principle: recovery should occur only when enough evidence warrants it, not at every annotated-path deviation.

Q3. Can simple rules replace the Stagnation Judge?

To test whether the LLM-based Judge is necessary, we compare it with two non-LLM stagnation-detection rules and a retrieval-based RAG alternative:

  • Keyword Heuristic: Track question–page keyword relevance; recover after three consecutive steps without exceeding the previous best relevance.
  • Fixed Steps: Recover at steps 5 and 15.
  • RAG: Index visited webpage chunks; after Re3 rollback, retrieve the three most question-relevant chunks via BM25 and inject them with source URLs into subsequent context.
MethodWebWalkerQA p@1WebWalkerQA p@4V-GEMS p@1
ReTrace5066.9855
Keyword Heuristic37.7448.1135.71
Fixed Steps43.4053.7735.71
RAG43.4059.4347.86

ReTrace outperforms both rules across settings: +12.26 and +6.60 points on WebWalkerQA pass@1, and 55.00% versus 35.71% for both on V-GEMS. These results show that recovery effectiveness depends not only on performing rollback, but also on selecting the right time to recover. By considering broader exploration context, the LLM Judge detects stagnation more effectively than fixed steps or local keyword relevance.

Thank you again for your constructive feedback. In our rebuttal, we added equal-token-budget and matched-success cost comparisons, direct evaluations against AWM and ReasoningBank, and clarified that the WebWalker baseline includes both Explorer and Critic.

We also report stagnation-judge precision and recall, alongside comparisons with keyword-based, fixed-step, and RAG alternatives. We would greatly appreciate your thoughts on whether these additional results adequately address your concerns.

Dear Reviewer iZWM:

As the discussion period draws to a close, we very much appreciate the opportunity for this constructive exchange, which we believe is valuable in fostering a collaborative research community. We hope that the additional experiments and clarifications, including comparisons with related methods, equal-token-budget evaluations, and analyses of the Stagnation Judge, have helped provide further insight into our approach and address the points raised.

Should you happen to have any further thoughts or questions regarding our responses, we would of course be delighted to continue the discussion and provide any further clarification that might be helpful. Thank you again for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.