Routing Is Least Learnable Where It Is Most Valuable: Bounds on Representation Routing for Web Agents

AI summary

Overview

Research area: Web agents and GUI grounding — specifically, how the observation representation (accessibility tree text, screenshot pixels, or set-of-marks fusion) affects agent success, and whether a system can learn to choose a representation per task.

Technical level: Advanced. The paper assumes familiarity with agent benchmarks, oracle/union ceilings, AUROC, nested cross-validation, and multiplicity correction.

Scope: A measurement study across six observation modes, eight site–model cells, and 7,686 scored episodes on VisualWebArena and WebArena, establishing an upper bound (a rerun-corrected cost ceiling) and a lower bound (five routing policies that fail) on per-task representation routing.

What This Paper Is About

A web agent must be shown the page before it can act, and today that choice — accessibility tree text, a screenshot, or a set-of-marks fusion — is fixed once at build time for every task. The authors ask what a per-task choice would actually buy, by measuring six observation modes under one fixed scaffold and one fixed prompt budget across eight (site × backbone) cells. The surprising answer is that the apparent prize is largely an artefact of run-to-run noise, and that the benchmarks the field measures on cannot produce the supervision a router would need to learn.

Key Contributions

1. Demonstrating genuine complementarity of representations. 44 of the 48 mode–cell pairs solve at least one task no other mode in that cell solved, every mode does so in some cell, the failures of losing channels are structurally different, and which mode wins reverses between the two task sets.

2. Separating representation diversity from rerun variance in the oracle ceiling. The six-mode union ceiling of 7.1–51.9% against a best single mode of 2.2–35.6% is compared against the measured cost of simply rerunning an arm already in hand; only the cost ceiling (9.5–30.6% cheaper at unchanged success in 8 of 8 cells) survives, because it adds no arm.

3. Establishing a lower bound from five routing constructions. Choosing which mode, a learned triage of spend, a zero-token regex rule read off the task text, a confidence cascade, and pooled cost tiers all land at or below trivial fixed policies, and they fail for three separate reasons — supply, estimand, and value — rather than one weak router.

4. Naming the obstruction as a property of today's agents, not of routing. Routing supervision is produced at the agent's success rate, so routing is least learnable exactly where it would be most valuable; label supply and routing opportunity correlate at ρ = 0.952 across cells, which makes the result falsifiable by a stronger agent.

Main Findings

• Representations are complementary but not portable. Every mode wins somewhere and loses elsewhere; on classifieds, the hybrid (SoM) class leads by 8.04–9.82pp at one arm per class, while on WebArena the no-image class leads by +4.81pp. The five remaining cells sit at 0.49–2.96pp, inside the noise band, and are read only as directions.

• Failure happens at the first decision, not through drift. On tasks two modes disagree about, 72–100% of VisualWebArena trajectories have already diverged by step 3 and at most 3% diverge at step 10 or later; the effect is weaker on WebArena (50–90% early, up to 22% late).

• Behavioural signatures are legible and large. On the replicated cell, 22 of 25 live behavioural metrics separate the modes by more than a rerun moves them, several by 5–22×. On red·B2, Vision scrolls 8× as often as SoM and clicks half as often. Per-step decision quality moves more than macro action frequency in 7 of 8 cells, at 1.34–4.07× on the six VisualWebArena cells, with WA·B0 the exception at 0.97×.

• The noise floor is large enough to be the headline. Rerunning one condition changes 12.1–14.3% of task outcomes on cls·B0, and 49 of 224 tasks flip in at least one of three replicated arms. Flips concentrate in multi-solver rows: 48–52% of those flip, against 2.9% of the rest. The resolution threshold is 2.32–2.53pp, so an effect must reach roughly 3.8–4.2pp to clear it under the exchangeability null.

• Most of the oracle headroom is not representation diversity. Adding the best distinct arm buys +1.97 to +7.14pp, while rerunning an arm already in hand buys 4.91–7.59pp wherever a replicate exists. A second run of a mode already in hand gains about as much as adding a new one.

• Only the cost ceiling survives. Keeping the best mode everywhere and sending only never-solved tasks to the cheapest arm leaves success unchanged by construction and cuts cost 9.5–30.6% in 8 of 8 cells. It survives because it adds no arm — it is the same arms spent differently, reachable in principle with one bit per task rather than a mode identity.

• Fusion does not clear the bar either. Against a workload-matched single channel, the fused mode's premium clears the rerun threshold in 0 of 8 cells.

• Routing dies of label supply. The natural label — the cheapest mode that solved the task — exists only where something succeeded, yielding 15–97 labels per cell over six classes; under a minimum-of-ten-rows-per-class filter, four of six cells admit no classifier at all. The question is scarce too: tasks where more than one mode succeeds are 1.5–34.6% of a cell, and on two cells they number 3 and 4.

• Routing that has plenty of labels still buys nothing. The triage label is defined everywhere and predictable in five of six cells (AUROC 0.651–0.717; red·B2 is below chance at 0.483), yet under fully nested cross-validation no cell's learned triage Pareto-dominates always taking the cheapest mode.

• A free signal exists and routing on it still loses. A regex over the task intent flags tasks where the screenshot is worth +22.54pp against +0.65pp elsewhere (flagging 71 of 224 classifieds tasks and 63 of 203 reddit tasks), but the policy built on it still loses to always-Vision, because the screenshot does not hurt on the unflagged tasks either.

• The cascade ranks usefully and still buys nothing. Escalating on low self-reported confidence beats always-rich at no operating point in any comparable cell, though against a random-escalation control the ranking is informative.

• Pooling backbones restores supply but makes labels ambiguous. Different backbones disagree about the same task, and the single surviving cell is the one whose verdict a leakage correction flips; its triage signal is below chance.

• Two practitioner-intuitive features fail outright. The benchmark's own difficulty annotation adds ΔAUROC +0.0024, and whether the task supplies a reference image does not help.

• The obstruction is one wall, not several. Label supply and routing opportunity both track the best single mode's success rate at ρ = 0.952 (mean gap 1.65pp). The routable share grows roughly linearly in the per-mode rate, where mutually independent modes would grow near-quadratically at these success levels — so the negative result is a statement about routing at 2–36% success, not about routing.

• Instrument caveats are themselves results. An audit on 2026-08-03 found five conclusions hardcoded in the producers that generate the tables stating the same quantities, across four scripts: four stale denominators (an annotation column reading 6/6 beside a count column reading 8/8) and one factual error (a claim that Vision is the cheapest mode in every cell, false on WA·B0 where DOM is). Every number is now read from a product JSON at render time.

Methodology in Plain English

The authors hold everything except the observation mode constant: one scaffold, one prompt budget, one action space, one model call per step emitting a thought, a confidence, and an action, with the last eight action outcomes as context. No planner, memory, reflection or retry policy sits above the step. That fixed scaffold is what licenses reading a difference between conditions as a difference of representation.

They then vary the representation across six modes. Four carry no screenshot and differ only in which text payload the agent receives (the full accessibility tree versus the flattened mark list) and which prompt family tells it what to expect; the corners add or remove the image. Six modes are evaluated across eight cell types — three sites crossed with three backbones, minus one cell that was never run — giving 36 conditions in total.

The critical methodological move is the rerun control. Before crediting any gain to adding a representation, they re-run conditions that are already in hand and measure how much the outcome moves. They report two distinct quantities and are careful never to confuse them: an observed band (how much the mean actually moved across replicated pairs, 0.89–2.23pp) and a resolution threshold (how large an effect must be before a single rerun would be unlikely to produce it unaided, 2.32–2.53pp under an exchangeability null). They also keep mean differences and set differences strictly separate, since a union ceiling moves by the set functional, not the mean.

On the routing side, they construct five policies spanning different hypothesis classes and evaluate them against the trivial baselines — always the best single mode, always the cheapest — using fully nested cross-validation. Because the table set is not one inferential family, they explicitly classify each table as confirmatory, descriptive, or selection-derived, and correct only within the confirmatory family.

Why This Matters

Impact on research. The paper reframes a widely held assumption — that a better representation choice per task is low-hanging fruit — as a measurement artefact. It introduces a reporting discipline (price a rerun before pricing a representation) that applies well beyond this setting, and it demonstrates that at these success rates the resolution of the benchmark instrument is comparable to the effects being reported. Its most consequential claim is falsifiable by construction: because label supply and routing opportunity both scale with the agent's success rate, a sufficiently stronger agent should overturn the negative result, and the authors say so explicitly.

Real-world applications:

• Cost control for deployed web agents. The surviving result is directly operational: routing never-solved tasks to a cheaper representation cuts cost 9.5–30.6% with no success loss, and needs only one bit per task rather than a mode identity.
• Model selection and grounding configuration for GUI agents. Practitioners choosing between accessibility-tree grounding, screenshot grounding, and set-of-marks fusion can use the class-level comparisons — with the caveat that the winner is a property of the specific site, model, and task set, not of the modality.
• Benchmark design and reporting standards. The finding that the evaluators emit only binary scores, and that this blocks routing supervision, points directly at graded evaluators as an infrastructure fix.
• Cascade and escalation systems for agent pipelines. The confidence cascade's failure — a usable ranking that still buys nothing because the expensive arm does not hurt on the excluded tasks — is a cautionary case for anyone building escalation logic on self-reported confidence.

Industry relevance. Teams shipping browser agents today make a fixed grounding choice at build time. This paper tells them that choice is not universally transferable, that a two-point difference between modes is what a single repetition delivers on its own, and that an API bill and an electricity estimate cannot be pooled into one efficiency number — the denominator silently reorders which mode is cheapest in four of the six cells with enough successes to divide by.

Future Directions

• Graded evaluators. The benchmarks emit exactly two values across 7,686 scored episodes, with no missing or non-numeric entries. A graded per-task score would make every episode a training signal regardless of success, attacking the supply obstruction directly.

• Replicates as a reporting norm. Single-run reporting remains standard; at the measured flip rates, a mode-to-mode difference below roughly 4pp is not resolvable by one run against another. Rerun floors should be reported alongside mode deltas.

• A third workload and cross-family coverage on the second benchmark. Both WA cells are Qwen, and the two benchmarks share one application (WA reddit is the vwa-reddit container — same image, same port, same account). Modality, task set, and benchmark all change together at the VWA/WA boundary, so with two levels no design identifies what moderates the winner-reversal.

• Richer hypothesis classes and online cascade infrastructure. Only five simple constructions were tested; no LLM-based router, reinforcement learning, contextual bandit, or online policy was evaluated. The supply obstruction is argued to be estimator-independent, but the value of richer hypothesis classes on this data is unmeasured, and every escalation number here is an offline splice that never observes what a real cascade does after the cheap arm has acted on a stateful site.

Target Audience

Researchers and engineers working on web agents, GUI grounding, and computer-use agents who need to make or defend a representation choice — and who are willing to read their own results against a measured noise floor rather than against zero. It is also valuable to benchmark designers (the binary scoring critique is actionable) and to practitioners building cost-aware agent deployments, who can adopt the cost ceiling without adopting the paper's negative conclusion. The paper is written for readers comfortable with oracle bounds, cross-validation, and multiplicity correction; the central idea is accessible, but the evidence is dense.

Authors’ abstract

Web agents observe a browser through text, pixels, or both, and the choice is usually fixed once for all tasks. We measure six observation modes across eight site-model combinations (cells) on VisualWebArena and WebArena and ask what choosing per task would buy. The modes are complementary: each solves tasks the others miss, they fail in structurally different ways, and the best choice reverses between task sets. The obvious prize, an oracle that picks a winning mode for every task, looks large but is inflated by run-to-run noise: rerunning the same mode on the same tasks changes 12-14% of outcomes, so a second run of a mode already in hand gains about as much as adding a new one. What survives is a cost bound: sending only the tasks no mode solves to the cheapest mode cuts cost by 9.5-30.6% in 8 of 8 cells at unchanged success. We then test five routing policies (picking the mode, deciding when to spend on the strong mode, a zero-cost rule read off the task text, a confidence cascade, and pooled cost tiers), and none robustly beats simply fixing one well-chosen mode; the one exception is a fragile result in our sparsest cell. The central obstruction is that routing supervision is produced at the agent's success rate: the weaker the agent, the fewer labels a router gets, exactly where routing would be most valuable. This limit belongs to today's agents rather than to routing itself. Label supply and routing opportunity rise together (correlation 0.95 across cells), so a stronger agent can overturn the result, and we report the rerun noise bands and the full measurement protocol.