Technical Summary: Are Online Skill and Memory Modules Always Worth Their Tokens?

Problem Statement

Online web agents frequently augment a base "actor" model with modules for memory, workflow induction, or skill synthesis (e.g., Agent Workflow Memory, Agent Skill Induction, ReasoningBank). While these modules aim to improve task success by reusing knowledge from prior trajectories, they incur a significant test-time token cost. This cost is rarely reported alongside the actor's inference cost, creating a "simple allocation problem": tokens spent on inducing, retrieving, or injecting reusable knowledge are tokens unavailable for direct task execution (observing, reasoning, acting).

The central question addressed is whether, under a fixed total inference budget, it is more effective to allocate tokens to online augmentation modules or to a vanilla actor that uses the same budget for additional interaction steps. This is particularly relevant as frontier models (e.g., Gemini 3, GPT-5.4) have improved in multi-step reasoning, potentially reducing the need for external scaffolding.

Methodology

The study conducts a budget-constrained evaluation across three WebArena domains (Shopping, Reddit, Admin) and one WorkArena-L1 domain (enterprise knowledge work).

Systems Compared

The authors compare three online augmentation methods against a budget-matched vanilla baseline:

1. AWM (Agent Workflow Memory): Induces natural-language workflows from successful trajectories.
2. ASI (Agent Skill Induction): Synthesizes and reuses executable Python skill functions.
3. ReasoningBank: Distills reasoning strategies from successes and failures into a memory bank.
4. Vanilla-IB (Vanilla-Increased-Budget): A vanilla actor without auxiliary modules. To ensure a fair budget comparison, its interaction horizon is extended from the standard 10 steps to 15 steps. It also employs a rule-based accessibility-tree pruning mechanism to reduce context length without LLM calls.

Experimental Setup

• Models: Gemini 3 Flash, GPT-5.4-mini, and Qwen 3.6-27B.
• Budget Accounting: Total token usage is aggregated across all system components (actor + auxiliary modules).
• Evaluation Rigor: Unlike prior work that often reports single-run metrics, this study reports results over three independent runs to capture run-to-run variance. Metrics include aggregate success rate (SR), total tokens per task, and bounds on task-level stability (Any-of-3 and All-of-3 success rates).
• Domains: WebArena (Shopping, Reddit, Admin) and WorkArena-L1 (ServiceNow tasks).

Key Results

1. Vanilla Baseline Superiority in Aggregate Performance

Across all three WebArena domains and all three models, the Vanilla-IB baseline consistently matched or surpassed the aggregate success rate of the augmented methods (AWM, ASI, ReasoningBank).

• Token Efficiency: Vanilla-IB often achieved these results using fewer total tokens than the augmented methods.
• Model Dependency: The performance gap was most pronounced with GPT-5.4-mini, suggesting that weaker models may generate noisy workflows or skills that degrade performance. Even with stronger models, the augmented methods failed to outperform the budget-matched vanilla actor.
• WorkArena-L1: The trend held in enterprise settings, where Vanilla-IB remained competitive with the best augmented methods while using fewer tokens.

2. The "Budget Asymmetry" Illusion

The study reveals that apparent gains from augmentation often stem from budget asymmetry. For instance, on the Reddit domain with Gemini 3 Flash, AWM and Vanilla-IB had identical success rates at 10 steps. However, AWM consumed significantly more tokens. When Vanilla-IB's horizon was extended (up to 25 steps), it surpassed AWM in success rate while still using fewer tokens than AWM's standard 10-step configuration. This indicates that the "benefit" of the module was largely an artifact of the augmented method having a higher token budget, not a superior architectural advantage.

3. Sources of Token Overhead

Token decomposition analysis (Table 3) identifies two sources of overhead for augmented methods:

1. Explicit Module Costs: Tokens consumed by induction, retrieval, and verification calls.
2. Implicit Context Inflation: Retrieved workflows, memories, or skills are injected into the actor's prompt at every step, increasing the prompt size and thus the cost of every subsequent actor call.

4. Run-to-Run Variance and Stability

Single-run success rates were found to be unstable. The study reports Any-of-3 (success in at least one run) and All-of-3 (success in all three runs) metrics. The gaps between these bounds were significant, indicating that single-run evaluations hide substantial task-level noise. This variance is exacerbated by environmental factors (timeouts, page loads) and the stochastic nature of LLM sampling.

5. Structural Fragility of Augmentation

• Programmatic Skills (ASI): Synthesized skills rely on dynamic accessibility-tree IDs (BIDs). If the page state changes (e.g., reload), these IDs become invalid, causing silent failures or errors. Vanilla agents, which query the LLM at every step, adapt naturally to state changes.
• Verification Confounds: In ASI, functions are often stored even if they fail initially but the agent recovers via primitive actions, leading to a library of "broken" skills.
• Contamination: AWM and ReasoningBank often induce knowledge from failed trajectories because the "judge" (evaluator) only sees the final outcome, not the intermediate steps. This leads to the injection of incorrect strategies into the agent's context.

Significance and Claims

The paper argues for a shift in evaluation hygiene for online web agents:

1. Total Cost Reporting: Comparisons must report total token usage across all modules, not just the actor.
2. Budget-Matched Baselines: Augmented methods should be compared against vanilla actors that utilize the same total inference budget (e.g., via extended horizons) rather than fixed step counts.
3. Multi-Run Reporting: Evaluations must report multi-run variance (e.g., Any-of-3/All-of-3) as a core criterion, as single-run metrics are insufficient to capture the reliability of online agents.

The authors conclude that while skills and workflow memory may offer gains in specific, highly repetitive domains, their apparent benefits often vanish when the overhead is accounted for against a budget-matched actor. The rapid improvement of base models suggests that external scaffolding may no longer be necessary for many tasks, and that "more interaction steps" is often a more efficient use of tokens than "more complex scaffolding."

Limitations

The authors acknowledge that their conclusions are restricted to the specific domains (Shopping, Reddit, Admin) and models tested. They note that environments with highly homogeneous task distributions or stable, high-level APIs (where offline skill discovery is amortized) might yield different tradeoffs favoring augmentation. Furthermore, the budget matching is an approximation based on step counts, as exact token matching is difficult in dynamic web environments.