Routing Is Least Learnable Where It Is Most Valuable: Bounds on Representation Routing for Web Agents
Source: arXiv:2608.06171 · Published 2026-08-06 · By Jiaming Wei, Zekun Wu, Adriano Koshiyama, Maria Perez-Ortiz
TL;DR
This paper tackles the problem of grounding representation choice for web agents that interact with web pages using different observation modes—such as text-only, image-only, or combinations. Unlike prior work that fixes a single representation modality per deployment, the authors ask whether dynamically routing tasks to different modes could improve agent performance or cost efficiency. They extensively evaluate six observation modes across eight site-model pairs ("cells") from two challenging benchmarks, VisualWebArena and WebArena. The key finding is that while the modes are complementary—each solving tasks the others miss—most apparent gains from per-task routing vanish once run-to-run noise is accounted for. In other words, variability when repeating the same mode run accounts for a large fraction of the apparent gains from routing. The only robust benefit surviving this noise correction is a "cost ceiling," where routing unsolved tasks to the cheapest mode reduces cost by 9.5–30.6% across all cells without hurting success rate. However, five routing policies designed and tested fail to outperform simply fixing the best single mode per cell. The central bottleneck is label scarcity for routing supervision: effective routing requires labeled data from contested tasks, but those only appear where an agent is already successful, limiting how well routing can learn. Stronger agents that succeed on more tasks would generate more routing supervision and opportunities to improve. The contribution includes a novel rerun noise analysis, upper and lower bounds on routing gains, and detailed behavior of representation complementarities. This paper provides an in-depth measurement of the fundamental limits of representation routing for today’s web agents and points out that current agent capabilities, rather than routing algorithms, largely determine routing’s value.
Key findings
- Each of the six observation modes solves at least one task no other mode in the same cell solves, confirming complementarity (44 of 48 mode–cell pairs have unique solves).
- Rerunning the same mode on the same tasks changes 12–14% of outcomes; 22% of tasks flip in at least one of three replicated arms, showing high run-to-run noise.
- An oracle picking the best mode per task gains 7.1–51.9% success over the best single mode at 2.2–35.6%, but much of this is explained by rerun noise.
- Sending only never-solved tasks to the cheapest mode reduces cost by 9.5–30.6% in all 8 cells at unchanged success, surviving noise correction.
- Five diverse routing policies (learned triage, confidence cascade, zero-cost text rules, pooled cost tiers, mode picking) fail to robustly outperform fixed single modes.
- Routing supervision labels exist only at the agent’s success rate, resulting in severe label scarcity (only 15–97 labels per cell across 6 classes), preventing routers from learning.
- The set of routable tasks (those solved by more than one mode) tracks agent success rate closely (correlation 0.95), making routing value and supervision tied to agent capability.
- Representation choice reverses between task sets and is deployment-dependent; no universally best mode exists across sites or models.
Threat model
The adversary is essentially the uncertainty and noise in the web task environment and agent behavior, generating stochastic successes and failures. There is no malicious attacker explicitly modeled. Routing must learn from limited labeled successes where multiple candidate modes solve the same task. It cannot rely on unlimited labels or graded per-task signals. The agents cannot adapt during evaluation, and rerun environment variability places a natural upper bound on measurable gains.
Methodology — deep read
Threat model & assumptions: The study assumes a web agent interacting stepwise with browser states via one of six grounding observation modes under fixed scaffolds and no higher-level planning. The adversary is essentially the task distribution and agent stochasticity producing outcome variance, not an explicit attacker. The key assumption is the agent’s success rate governs available routing supervision labels.
Data provenance, size, labels, splits: Evaluations occur on VisualWebArena and WebArena benchmarks, combining classified ads and Reddit site tasks. Eight total (site × backbone) "cells" are evaluated, comprising over 7,600 scored episodes under 36 conditions (six modes per cell). Labels are derived as binary success or failure per episode; no graded scores are available, limiting supervision granularity.
Architecture/algorithm: The core agent is a prompt-driven system issuing a thought, grounding, and action each step, with last eight steps’ outcomes as context. Six modes represent different views of the page: accessibility tree (DOM), set-of-marks (SoM), vision-only screenshot, and hybrids. Modes vary in text payload and grounding method (element ids, coordinates). Routing policies choose among these modes per task, with designs including oracle upper-bound, learned triage, confidence cascades, zero-cost rules, and cost-based tiers. Loss functions and training methods for routing classifiers depend on limited task success signals. No new backbone models are trained—routing policies lie atop fixed agents.
Training regime: Routing policies are trained using scarce labels where multiple modes solve a task, typically 15–97 labels per cell, filtered for minimum examples per class. Cross-validation with nested folds is employed. Some routing policies use simple heuristics or zero-cost rules derived from task text rather than learned classifiers.
Evaluation protocol: Success rate is the primary metric, measured as binary task completion. Cost is measured per episode either in token counts for API-served models or estimated electricity for local backbones. Noise due to reruns (repeat runs of same mode/task) is carefully quantified and serves as a baseline against which routing gain claims are compared. Ablations test labels supply, routing supervision quality, and cascading policies. Rerun noise thresholds determine statistical significance of observed improvements. Evaluation includes eight cells and multiple routing policies.
Reproducibility: The paper reports all numerical results extracted directly from logged JSON artefacts at runtime, ensuring consistency. Code and datasets are partially closed but rely on established benchmarks VisualWebArena and WebArena. Some backbone models (Qwen3-VL-235B API, Gemma-3-4B local) are external and not fully open. Replicates exist only for a subset of cells, limiting some comparisons.
Concrete example: Consider a classifieds site with backbone B0 (cls·B0 cell). The DOM mode solves some tasks uniquely; the Vision mode solves others. Oracle picks the best mode per task and improves success by up to 50%, but rerunning DOM twice also yields a 7% gain due to noise. Routing tries to learn from cases where multiple modes succeed to pick per-task best mode but fails due to only 15–20 such tasks providing labels. Sending unsolved tasks to cheapest mode cuts cost by ~15% without losing success. None of the learned routing policies improves beyond a fixed DOM or Vision mode.
Technical innovations
- Comprehensive rerun noise measurement for web agent task success, showing up to 14% task outcome flips on reruns and controlling upper bound claims accordingly.
- Demonstration that representation choices for web agents are strongly complementary but routing gains are limited by label scarcity correlated with agent success rate.
- Formulation and empirical test of multiple routing policies (learned triage, confidence cascade, zero-cost linguistic rules, pooled cost tiers) for mode selection, benchmarking their failure to exceed fixed-mode baselines robustly.
- Derivation of a cost-efficiency routing bound that reduces cost by 9.5–30.6% by sending never-solved tasks to the cheapest mode without adding arms, surviving noise corrections.
Datasets
- VisualWebArena — ~7,000+ scored episodes across multiple tasks and modes — public benchmark [Koh et al. 2024]
- WebArena — 104 tasks evaluated across modes and backbones — public benchmark [Zhou et al. 2024]
Baselines vs proposed
- Best single fixed mode: success rate = 2.2–35.6% across cells vs Oracle per-task mode selector: success rate = 7.1–51.9%, before noise correction
- Rerun of same mode: success gain = 4.91–7.59pp, comparable to adding a different mode
- Routing policies (learned triage, confidence cascade, zero-cost rule): none achieve success or cost improvements that robustly surpass best fixed mode baseline
- Cost ceiling routing (sending only unsolved tasks to cheapest mode): cost reduction = 9.5–30.6% at unchanged success across all cells
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2608.06171.
Fig 1: What this paper measures. (1) One model call per step emits a thought, a grounding and an action, with the
Fig 2: Success rate of all six modes in all eight
Limitations
- Routing supervision label scarcity caused by limited tasks solved by multiple modes restricts training of routing policies.
- Binary success/fail evaluator yields no graded signal, reducing richness of training labels for routing.
- Rerun noise and environment drift confound attributions to representation diversity versus repetition gains.
- Only a subset of cells have replicated runs, limiting precision of noise floor estimates and generalization.
- Benchmarks used do not cover all web task varieties and domain shifts, so portability of results is uncertain.
- Evaluation excludes adaptive or stateful cascades that react online, relying instead on offline splicing of results.
Open questions / follow-ons
- How would routing policies improve if richer, graded success evaluators replaced binary task scoring?
- Can stronger web agents with higher overall success rates enable practical routing by increasing the number of contested routing labels?
- What gains would an online, stateful cascading architecture produce versus the offline splicing of modes tested here?
- How do representation routing and cost/success tradeoffs behave on other web domains and task families beyond VisualWebArena and WebArena benchmarks?
Why it matters for bot defense
For bot-defense and CAPTCHA practitioners, this paper offers an important cautionary case on the limits of dynamically choosing observation modes for web-interacting agents based on routing techniques. While multi-view representations of web state are complementary and can uniquely solve different tasks, practical gains from per-task representation routing are severely constrained by supervision scarcity tightly coupled to overall agent success. This suggests that efforts to improve bot and CAPTCHA defenses by selectively using or routing different grounding modalities require careful consideration of label availability and agent capabilities. The finding that rerun noise rivals claimed routing gains highlights the necessity to measure stability and noise baselines rigorously in evaluation pipelines. Finally, the demonstrated cost ceiling gains offer a practical lever by offloading unsolved tasks to cheaper modes, which may inform multi-fidelity defenses or detection strategies that balance cost with success detection. However, more powerful, capable agents and richer evaluation signals would be required to unlock robust routing benefits. In short, this work advises practitioners to measure carefully, consider agent success regimes, and manage expectations regarding representation routing's current utility for bot and CAPTCHA interactions.
Cite
@article{arxiv2608_06171,
title={ Routing Is Least Learnable Where It Is Most Valuable: Bounds on Representation Routing for Web Agents },
author={ Jiaming Wei and Zekun Wu and Adriano Koshiyama and Maria Perez-Ortiz },
journal={arXiv preprint arXiv:2608.06171},
year={ 2026 },
url={https://arxiv.org/abs/2608.06171}
}