Are Online Skill and Memory Modules Always Worth Their Tokens? A Budget-Constrained Study of Web Agents

arXiv:2606.15017 · cs.CL · Submitted 2026-06-12 · Read on arXiv

cs.CL

Submitted: 2026-06-12

Updated: 2026-08-30

Comments: Accepted to EMNLP 2026

Project page: https://sinahmr.github.io/budget-constrained-web-agents

License: http://creativecommons.org/licenses/by/4.0/

The gist: Online web agents often augment a base actor with memory, workflow, or skill modules.

Terminology

Abstract

Online web agents often augment a base actor with memory, workflow, or skill modules. These modules can improve performance, but they also consume test-time tokens, a cost rarely reported alongside the actor's inference cost. We study online augmentation, where this overhead is paid on every task, and re-evaluate its benefits under a fixed total inference budget. We compare AWM, ASI, and ReasoningBank with a token-matched vanilla baseline that uses the same budget for additional actor steps. Across four WebArena domains and three models, Gemini 3 Flash, GPT-5.4-mini, and Qwen 3.6-27B, the vanilla baseline matches or surpasses all three augmentation methods in aggregate success rate while often using fewer total tokens. We observe a similar trend on WorkArena-L1 with Qwen 3.6-27B, indicating that the effect extends to enterprise knowledge-work tasks. Our results suggest that skills and workflow memory can be useful in specific domains, but their apparent gains often vanish against a budget-matched actor. We further show that run-to-run variance materially affects outcomes and should be reported as a core evaluation criterion for online web agents.

Sources

Related papers