CATTS: Confidence-Aware Test-Time Scaling for Multi-Step Web Agents

Paper: 2602.12276 Authors: Nicholas Lee, Lutfi Eren Erdogan, Chris Joseph John, Surya Krishnapillai, Michael W. Mahoney, Kurt Keutzer, Amir Gholami Categories: cs.AI, cs.CL

Abstract

Test-time scaling has emerged as a powerful paradigm for enhancing neural network performance, but its application to agentic, multi-step tasks presents unique challenges. This paper introduces CATTS (Confidence-Aware Test-Time Scaling), a technique that dynamically allocates computational resources based on decision uncertainty in web agents. Through empirical analysis on WebArena-Lite and GoBrowse benchmarks, the authors demonstrate that naive uniform scaling strategies quickly saturate in long-horizon environments due to error compounding. CATTS addresses this by using vote distribution statistics—specifically entropy and top-1/top-2 margin—to identify contentious decisions requiring additional compute. The method achieves up to 9.1% performance improvement over baseline React agents while consuming 2.3x fewer tokens than uniform scaling approaches.

Key Contributions

• Empirical characterization of test-time scaling behavior for multi-step web agents, revealing diminishing returns from uniform per-step compute increases
• Analysis of aggregation strategies including LLM-based Arbiters, showing they can outperform naive voting but may overrule high-consensus decisions
• Identification of vote-derived uncertainty metrics (entropy, top-1/top-2 margin) as reliable predictors of downstream task success
• Introduction of CATTS, a practical dynamic compute allocation policy that achieves superior efficiency-performance tradeoffs

The Problem with Uniform Scaling

Traditional test-time scaling approaches apply uniform compute increases across all decision points. For single-step tasks, this strategy works well—more samples generally yield better results through improved coverage of the solution space. However, multi-step agentic tasks exhibit fundamentally different dynamics.

The authors identify two critical issues. First, errors compound over long horizons: a single misstep early in a task trajectory can render subsequent actions irrelevant, wasting computational resources on doomed paths. Second, not all decisions carry equal uncertainty—some steps have clear optimal actions while others involve genuine ambiguity requiring careful deliberation.

Through experiments on web navigation benchmarks, the paper demonstrates that uniformly increasing sampling from $k=1$ to $k=5$ per step yields diminishing returns. Performance improvements plateau while token consumption grows linearly, creating an unfavorable efficiency frontier. This motivates the need for smarter, adaptive allocation strategies.

Methodology: Vote-Derived Uncertainty Signals

CATTS operates on a simple but powerful insight: the agent’s own vote distribution reveals decision confidence. When multiple sampled trajectories converge on the same action, the decision is likely straightforward. When votes fragment across options, additional compute can help resolve genuine ambiguity.

The paper evaluates two uncertainty metrics derived from vote distributions:

Entropy: Measures the spread of votes across actions. For a distribution $p$ over actions, entropy is computed as:

$H(p) = -\sum_{i} p_i \log p_i$

High entropy indicates dispersed votes and high uncertainty.

Top-1/Top-2 Margin: Captures the gap between the most popular and second-most popular actions:

$\text{margin} = p_{\text{top-1}} - p_{\text{top-2}}$

Small margins suggest competitive alternatives requiring disambiguation.

Empirical analysis shows both metrics correlate with downstream success rates. Steps with high entropy or low margins benefit significantly from additional sampling, while confident decisions (low entropy, high margin) show minimal gains from extra compute.

The CATTS Algorithm

CATTS implements a threshold-based policy for dynamic compute allocation. At each step:

1. Sample $k_{\text{base}}$ trajectories (typically $k_{\text{base}} = 3$)
2. Compute uncertainty metric (entropy or margin) from vote distribution
3. If uncertainty exceeds threshold $\tau$, allocate additional samples up to $k_{\text{max}}$
4. Aggregate votes and select action

The threshold $\tau$ controls the aggressiveness of compute allocation. Lower thresholds trigger more frequent scaling, trading tokens for performance. Higher thresholds prioritize efficiency, scaling only for highly contentious decisions.

This approach provides an interpretable decision rule: compute is allocated precisely when the agent exhibits genuine uncertainty, rather than uniformly across all steps. The policy adapts naturally to task difficulty—complex environments with more ambiguous decisions automatically receive more resources.

Experimental Results

The authors evaluate CATTS on two web agent benchmarks:

WebArena-Lite: A simplified web navigation environment with 100 tasks spanning e-commerce, content management, and information retrieval scenarios.

GoBrowse: A more challenging benchmark requiring multi-step reasoning and interaction with real websites.

Key findings include:

• CATTS with entropy-based allocation achieves 9.1% relative improvement over React baseline on WebArena-Lite
• Token efficiency gains of 2.3x compared to uniform $k=5$ scaling while maintaining comparable performance
• Margin-based allocation shows similar trends with slightly different efficiency-performance tradeoffs
• Performance improvements are most pronounced on longer-horizon tasks where error compounding is severe

The paper also analyzes the distribution of compute allocation across task trajectories. CATTS concentrates resources on genuinely difficult decision points—typically 20-30% of steps—while using minimal compute for straightforward actions. This adaptive behavior explains the superior efficiency compared to uniform strategies.

Aggregation Strategies and the Arbiter

Beyond uncertainty-based allocation, the paper investigates aggregation methods for combining multiple sampled trajectories. Naive majority voting serves as the baseline, but the authors explore more sophisticated approaches.

An LLM-based Arbiter receives all sampled actions and their reasoning traces, then selects the best option. This meta-reasoning can outperform voting by considering action quality beyond mere frequency. However, the Arbiter introduces a critical failure mode: it may overrule high-consensus decisions, injecting errors even when the agent exhibits strong agreement.

The paper finds that Arbiters provide modest gains on average but increase variance. For production systems prioritizing reliability, vote-based aggregation with uncertainty-aware scaling offers a better risk-reward profile. The Arbiter remains valuable for research settings exploring the limits of test-time scaling.

Implications for Agentic Systems

CATTS demonstrates that test-time scaling for agents requires fundamentally different strategies than single-step tasks. The key insight—allocate compute based on decision uncertainty—generalizes beyond web navigation to any multi-step agentic system.

Several broader implications emerge:

Efficiency-Performance Tradeoffs: Dynamic allocation enables new operating points on the efficiency frontier, achieving strong performance with constrained budgets or maximizing performance with flexible resources.

Interpretability: Uncertainty metrics provide transparency into agent decision-making. High-uncertainty steps flag potential failure points for human review or intervention.

Scalability: As models and tasks grow more complex, intelligent compute allocation becomes increasingly critical. CATTS provides a practical framework that scales naturally with task difficulty.

Future Directions: The paper opens questions about optimal uncertainty metrics, learned allocation policies, and integration with other test-time techniques like self-consistency and chain-of-thought prompting.

Takeaways

1. Uniform test-time scaling shows diminishing returns for multi-step agents due to error compounding and heterogeneous decision difficulty across trajectories.

2. Vote-derived uncertainty metrics (entropy and top-1/top-2 margin) reliably predict which decisions benefit from additional compute, enabling dynamic allocation.

3. CATTS achieves up to 9.1% performance improvement over baseline agents while using 2.3x fewer tokens than uniform scaling, demonstrating superior efficiency-performance tradeoffs.

4. LLM-based Arbiters can outperform naive voting but introduce variance by potentially overruling high-consensus decisions, making them less suitable for reliability-critical applications.

5. Adaptive compute allocation provides interpretability benefits by flagging uncertain decisions, enabling human oversight and debugging of agentic systems.

6. The principles of confidence-aware scaling generalize beyond web agents to any multi-step decision-making system, suggesting broad applicability across agentic AI domains.