Budget-Aware Tool Use Enables Effective Agent Scaling

Tool-augmented agents scale along two dimensions: internal reasoning tokens and external tool calls. This paper shows that simply increasing tool-call budgets can hit a performance ceiling because agents do not adapt their behavior to remaining resources. It introduces Budget Tracker for explicit resource awareness and BATS (Budget-Aware Test-time Scaling) for adaptive planning and verification, using a unified cost metric that combines token and tool costs.

Test-time scaling has improved language-model reasoning, but tool-using agents incur a second resource cost: interaction with the external environment. Search-heavy agents may spend resources on repeated or low-yield paths, so a larger interaction budget does not guarantee better answers. The paper studies how agents should allocate a fixed resource budget between exploration, verification, and additional reasoning.

The central problem is budget-blind tool use. A conventional agent may continue a weak search path, terminate before exploiting useful budget, or incur tool costs without proportional accuracy gains. The paper formulates agent scaling under explicit per-tool budgets and asks how an agent can use remaining resources strategically instead of treating the budget as a passive limit.

Agent test-time scaling extends ordinary inference-time reasoning into environments where models can act through tools. In this setting, resource consumption is heterogeneous: tokens represent internal computation, while tool calls consume external services and interaction opportunities. The paper focuses on web-search agents and studies scaling as a cost-performance problem rather than measuring accuracy alone.

Two methods are introduced. Budget Tracker is a lightweight plug-in that exposes policy guidance and current/remaining resource usage inside the agent context. BATS builds on this state with a persistent tree-structured plan, explicit exploration-versus-verification decomposition, trajectory summarization, and self-verification. The verifier classifies a candidate path as SUCCESS, CONTINUE, or PIVOT, allowing the agent to deepen a promising lead or abandon an unproductive one.

The reported system is a ReAct-style search agent with Search and Browse tools. Budget Tracker inserts resource state into the reasoning loop. BATS wraps that loop with planning, execution, self-verification, summarization, and candidate selection. The architecture is training-free in the reported BATS experiments: the main change is how inference-time resources and trajectories are managed.

The evaluation covers search-intensive and agent benchmarks: BrowseComp (1,266 questions), BrowseComp-ZH (289), HLE-Search (200), and a 114-task retail subset of tau2-bench. The repository identifies a 200-question BrowseComp subset used in the paper’s controlled comparisons.

BATS does not introduce a new model-training objective in the reported experiments. The approach operates at test time by changing the agent’s planning, resource awareness, verification, and candidate-selection behavior. This makes the method applicable as an inference-time control layer around an existing tool-using model.

The experiments vary available tool budgets and compare standard ReAct behavior, Budget Tracker, and BATS. Budget Tracker is evaluated across models under matched budgets. BATS is evaluated at 100 calls per tool and through ablations of planning and verification. The experiments measure both answer accuracy and resource consumption rather than accuracy in isolation.

The comparisons include ReAct as the principal budget-unaware agent baseline, together with SLIM and training-based agent approaches in the broader BATS experiments. The study also compares against different tool-allocation strategies to separate the value of explicit budget awareness from simply increasing the number of available interactions.

The framework focuses on explicit tool-call budgets and does not fully solve multidimensional resource allocation. Token cost, latency, concurrency, and tool reliability can interact with the call budget. The method also depends on the quality of the underlying model, search environment, verifier, and retrieved evidence. Benchmark improvements therefore do not by themselves establish production reliability across arbitrary agent workloads.

The paper’s central finding is that effective agent scaling requires resource awareness, not merely a larger tool-call allowance. Budget Tracker makes resource state visible; BATS uses that state to change exploration, verification, and stopping decisions. Together they improve the cost-performance frontier in the evaluated search-agent settings.

Tengxiao Liu et al., “Budget-Aware Tool-Use Enables Effective Agent Scaling,” arXiv:2511.17006, subsequently published at COLM 2026. Primary project repository: google-research/budget-aware-agent.