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

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.