PaperlayerView exact revision on arXiv

Source-linked AI summary

Budget-Aware Tool Use Enables Effective Agent Scaling

Tengxiao Liu, Zifeng Wang, Jin Miao, I-Hung Hsu, Jun Yan, Jiefeng Chen, Rujun Han, Fangyuan Xu, Yanfei Chen, Ke Jiang, Samira Daruki, Yi Liang, William Yang Wang, Tomas Pfister, Chen-Yu Lee

arXiv:2511.17006v2cs.AI

TL;DR

Tool-augmented agents do not reliably improve when given more tool-call budget because they lack budget awareness. This paper introduces Budget Tracker and BATS, formalizes unified token-and-tool cost, and finds that budget-aware methods produce stronger scaling and better cost-performance trade-offs.

  • Problem

    Simply increasing tool-call budgets can leave agents at a performance ceiling because standard agents lack explicit budget awareness.

  • Method

    The paper introduces Budget Tracker and BATS, which use continuous resource tracking to adapt agent planning, verification, and tool use under explicit budgets.

  • Results

    Budget-aware methods produce more favorable scaling curves and better cost-performance trade-offs, with BATS achieving higher performance using fewer tool calls and lower overall cost.

  • Takeaways & Limitations

    Explicitly accounting for tool-call budgets and unified token-tool costs supports more effective and efficient scaling of tool-augmented agents.

  • Takeaways & Limitations

    The study prioritizes tool-call budgets over token-based budgets, while token usage remains part of the unified cost metric.

Abstract

from arXiv · show

Scaling test-time computation has been extended from language model reasoning to tool-augmented agents, where scaling involves not only thinking in tokens but also acting via tool calls that directly constrain environmental interaction. However, we found that simply increasing the tool-call budget fails to improve performance, as agents lack "budget awareness" and quickly hit a performance ceiling. We study how to scale such agents effectively under explicit tool-call budgets, focusing on web search agents. We first introduce the Budget Tracker, a lightweight plug-in that provides the agent with continuous budget awareness, enabling simple yet effective scaling. We further develop BATS (Budget-Aware Test-time Scaling), an advanced framework that leverages this awareness to dynamically adapt its planning and verification strategy. To analyze cost-performance scaling in a controlled manner, we formalize a unified cost metric that jointly accounts for token and tool consumption. We provide the first systematic study on budget-constrained agents, showing that budget-aware methods produce more favorable scaling curves and push the cost-performance Pareto frontier. Our work offers empirical insights toward a more transparent and principled understanding of scaling in tool-augmented agents. Our code is available at https://github.com/google-research/budget-aware-agent.

1. Introduction

Tool-augmented agents scale through both tokens and tool calls, but extra tool-call budget alone can fail because standard agents lack budget awareness. The paper introduces Budget Tracker and BATS to adapt agent behavior to available resources and improve cost-effective scaling.

  • Tool-augmented test-time scaling expands both thinking in tokens and acting through tool calls that determine external exploration depth and breadth.The paper focuses on search agents because collecting external information inherently requires extensive tool calls.
  • Standard agents often hit a performance ceiling because they perform shallow searches and fail to use additional tool-call resources effectively.The paper identifies budget awareness, rather than simply increasing spending, as the central challenge.
  • The study formalizes a unified cost metric that jointly accounts for internal token consumption and external tool interactions.This metric is used to trace cost-performance scaling trends in budget-constrained search agents.
  • Budget Tracker provides continuous resource signals to ReAct agents and improves performance across varied budget constraints.It is presented as a lightweight, plug-and-play module that supports more effective scaling and pushes the cost-performance Pareto frontier.
  • BATS dynamically adapts planning and verification to remaining resources, choosing between deepening a lead and branching to alternatives.Its planning module adjusts stepwise effort, while verification selects whether to pursue promising or alternative paths.
  • BATS achieves higher performance with fewer tool calls and lower overall cost than competing methods, yielding more favorable scaling curves and cost-performance trade-offs.Systematic experiments under varying budgets support this overall comparison.

2. Problem Formulation

The paper formulates agent test-time scaling as maximizing expected accuracy under per-tool call budgets, then evaluates search agents using a unified measure of realized token and tool costs. This framework distinguishes available budget from actual spending and traces performance-cost scaling curves.

  • 2.1. Agent Test-time Scaling: Agent test-time scaling maximizes expected accuracy while ensuring realized calls to every tool remain within its allocated budget.Performance is evaluated across budget levels to characterize how effectively an agent leverages resources.
  • 2.1. Agent Test-time Scaling: The preset budget is a hard upper limit, whereas realized cost depends on the agent’s execution strategy.The paper uses a post-hoc unified cost metric for consistent comparisons.
  • 2.1. Agent Test-time Scaling: Tool-call budgets are prioritized because tool calls directly constrain external knowledge acquisition, while accurate token budgets are difficult to determine for multi-step agents.Token usage is still incorporated into the unified cost metric.
  • 2.2. Problem Instantiation with Search Agent: Search agents instantiate the framework by reasoning over retrieved evidence and alternating ReAct-style reasoning with search and browse actions.Search returns result lists with snippets and URLs, while browse retrieves fuller webpage content.
  • 2.2. Problem Instantiation with Search Agent: Unified cost sums token costs from internal reasoning with economic costs for actual invocations of each tool.Tool calls have provider-dependent prices, while token costs distinguish input, output, and cache-hit tokens.
  • 2.2. Problem Instantiation with Search Agent: Additional tool calls generally increase token consumption because agents must process and reason over retrieved external information.Measuring unified cost under varying budgets enables comparisons across policies using actual incurred costs.

3. Budget Awareness

Budget Tracker makes tool-use scaling budget-aware by exposing resource status during agent reasoning. This improves accuracy and cost efficiency under fixed budgets and helps agents continue scaling beyond ReAct’s performance ceiling.

  • 3. Budget Awareness: The tracker appends used and remaining per-tool budgets during the reasoning loop so agents can condition subsequent actions on resource availability.It also supplies initial guidance about budget regimes and tool-use recommendations.
  • 3.3. Results and Analysis: Budget Tracker improves accuracy across models and benchmarks under identical budget limits.The tracker provides explicit budget signals that encourage more strategic tool use.
  • 3.3. Results and Analysis: With 10× less budget, Budget Tracker matches ReAct’s accuracy while reducing search calls by 40.4% and overall cost by 31.3%.The reported comparison is 12.8% versus 12.6% accuracy for budgets 10 and 100, respectively.
  • Budget Tracker consistently pushes the Pareto: ReAct saturates as tool budgets increase, whereas Budget Tracker continues scaling by surfacing unused resources.ReAct reaches a performance ceiling at a budget of 100 on BrowseComp, while the tracker enables further budget utilization.
  • Budget Tracker consistently pushes the Pareto: Sequential scaling with Budget Tracker extends the cost–performance frontier beyond ReAct’s plateau through more effective tool utilization.The comparison reports that Budget Tracker sustains gains after sequential scaling of ReAct eventually hits a ceiling.
  • Budget Tracker consistently pushes the Pareto: In parallel scaling, Budget Tracker produces a superior cost–performance curve while accuracy is evaluated across increasing parallel runs.The figure separates accuracy scaling from the corresponding cost–performance trend.

4. BATS: Budget-Aware Test-time Scaling

BATS extends budget awareness into dynamic planning and verification for search agents. It maintains a structured plan, evaluates candidate answers against constraints, and uses remaining resources to continue, pivot, or terminate exploration.

  • 4. BATS: Budget-Aware Test-time Scaling: BATS combines budget-aware planning with verification to maximize search-agent performance under per-tool budgets.The framework iterates over new information and updated budgets until a budget is exhausted.
  • 4. BATS: Budget-Aware Test-time Scaling: BATS decomposes question clues into exploration and verification categories to choose search actions and conserve budget.Exploration expands the candidate space, whereas verification checks specific properties.
  • 4. BATS: Budget-Aware Test-time Scaling: A persistent tree-structured checklist retains completed, failed, and partial steps while adapting exploration breadth and verification depth to remaining budget.This retention is intended to prevent redundant tool calls as the plan is refined.
  • 4. BATS: Budget-Aware Test-time Scaling: After a candidate answer, self-verification checks each constraint and chooses SUCCESS, CONTINUE, or PIVOT based on evidence and remaining budget.Promising but incomplete trajectories can continue, while contradictions or insufficient resources trigger termination or a pivot.
  • 4. BATS: Budget-Aware Test-time Scaling: When continuing or pivoting, BATS compresses the trajectory into a summary containing findings, failures, and optimization suggestions for subsequent reasoning.The summary reduces context length while preserving grounding in prior exploration.

5. Experiments and Results

Across web-search benchmarks and budgets, BATS improves accuracy and cost–performance trade-offs over baselines, while ablations show verification and continued budget use are important.

  • Experimental Setup: The evaluation covers BrowseComp, BrowseComp-ZH, and HLE-Search, with comparisons against general-purpose and agent-specialized baselines.Parallel scaling provides a resource-equivalent comparison by matching total tool consumption.
  • 5.2. Results: 24.6% on BrowseComp, 46.0% on BrowseComp-ZH, and 27.0% on HLE-Search under 100 tool uses, with BATS outperforming baselines without training.These results use Gemini-2.5-Pro in a budget-constrained setting.
  • 5.2. Results: Across all budget levels, BATS outperforms parallel majority voting in accuracy and achieves better accuracy at comparable or lower unified costs.Figure 7 evaluates tool-call and unified-cost scaling on a 200-example BrowseComp subset.
  • Ablations: Continuing new attempts after an initially verified answer produces substantially higher accuracy than early stopping with the remaining budget unused.The comparison is reported for the BATS orchestration framework.
  • Ablations: Removing verification lowers BrowseComp performance from 18.7% to 15.4%, while removing both planning and verification lowers it to 14.6%.The ablation uses a 100-tool-use budget per tool.

6. Related Work

The paper extends test-time scaling from text-only reasoning to tool-augmented agents and focuses on dynamic, cost-effective scaling for web search under explicit budgets.

  • 6.1. Test-Time Scaling: Prior test-time scaling uses sequential refinement, parallel sampling, aggregation, and hybrid strategies primarily for text-only reasoning.This work extends the scaling setting to include both tokens and tool calls.
  • 6.2. Web Search Agents: Web-search research includes task-specific training and inference-time strategies, but existing approaches can produce redundant calls or use static configurations.The paper instead studies dynamic performance under explicit budget constraints.
  • 6.2. Web Search Agents: Web-search agents use search and browse tools to solve complex, multi-hop queries requiring external information gathering.These agents form the paper’s main tool-augmented setting.

7. Conclusion

The paper presents a systematic study of budget-constrained tool-use scaling and introduces budget awareness to improve agent efficiency across resource limits.

  • Conclusion: Budget awareness enables stronger scaling and consistently pushes the cost–performance Pareto frontier across information-seeking tasks.The conclusion frames tool-call budgets as a critical scaling dimension.
  • Conclusion: The Budget Tracker provides lightweight budget awareness, while BATS dynamically adapts planning and verification to real-time resource status.The paper presents these as complementary approaches to overcoming standard agents’ performance ceiling.
  • Conclusion: The unified cost metric accounts for tool-call and token consumption, with tool calls standardized at $0.001 per invocation and tokens billed separately.The invocation rate is an average derived from post hoc experiment statistics.

A.2. Implementation Details

The implementation combines real-time budget tracking, iterative planning, verification, and trajectory compression, then evaluates generalization across conversational and coding agents.

  • Model Configuration: The experiments use Gemini-2.5-Flash, Gemini-2.5-Pro, and Claude-Sonnet-4 with specified thinking budgets, generation limits, and temperature 0.7.Gemini-2.5-Flash disables thinking, while Gemini-2.5-Pro uses a thinking budget of 1024.
  • Context Management: Context management truncates browsed pages, retains only the latest tool response, and periodically summarizes older verification trajectories.These strategies limit context growth during long agent interactions.
  • BATS Implementation: BATS iteratively reasons, plans, invokes tools, and uses verification to CONTINUE, PIVOT, or declare SUCCESS under per-tool budgets.Pivoting compresses the trajectory and starts a new attempt with the remaining budget.
  • Conversational Tasks: On τ2-bench, Budget Tracker improves Avg@4 from 47.8% to 55.5% and Pass^4 from 21.9% to 27.2% at budget 10.It also surpasses the baseline’s budget-50 Pass^4 while using approximately 18.4% fewer tool calls.
  • Coding Tasks: On SWE-bench Verified at budget 50, Budget Tracker raises resolve rate by 18.6 percentage points while using similar tool calls and token cost.The reported resolve rates are 55.4% versus 36.8%, with 45.7 versus 46.0 tool calls.
  • Coding Tasks: Budget Tracker also improves over a budget-60 baseline by using 9.9% fewer tool calls, reducing token cost by 7.5%, and increasing resolve rate by 2.2 points.The comparison is 45.7 versus 50.7 calls, 18.88¢ versus 20.40¢, and 55.4% versus 53.2%.

C.6. Early Stopping Analysis

Early stopping evaluates whether agents can answer efficiently before exhausting their tool budgets. BATS uses additional budget more effectively, improving accuracy and cost efficiency while ReAct largely plateaus.

  • The early-stopping evaluation measures the first completed answer, stopping when the budget is exhausted or when an answer passes BATS self-verification.This setup tests efficiency and robustness without forcing agents to consume their full budgets.
  • ReAct underuses browse calls and reaches 30.7% accuracy for budgets of 30 and above, showing little benefit from additional resources.Its search usage also remains nearly unchanged across budgets 30 and 100.
  • 37.4% accuracy at budget=200, up from 29.8% at budget=3, while BATS increases its use of search and browse calls as budget grows.BATS surpasses the baseline’s best accuracy with a budget of 5.
  • BATS exceeds 37% accuracy at approximately $0.23 unified cost, whereas parallel majority vote requires more than twice that cost.The comparison uses actual unified cost and early-stopping accuracy.
  • BATS combines budget-conditioned planning with verification decisions that select SUCCESS, CONTINUE, or PIVOT based on answer quality and remaining resources.Its planning module adapts search effort across high, medium, low, and critical budget regimes.

E.2. Behavioral Shift 1: Adaptive Strategy Selection

Budget awareness changes agents from rigid search behavior to adaptive strategy selection. The resulting behavior improves efficiency by tailoring exploration, verification, and tool allocation to available resources.

  • Adaptive Strategy Selection: Under high budgets, budget-aware agents explore broadly; under low budgets, they prioritize precise queries, unlike ReAct’s fixed narrow-first strategy.ReAct is too narrow when resources are plentiful and too wasteful when resources are scarce.
  • Adaptive Strategy Selection: Budget Tracker with budget=10 matches ReAct with budget=100 in accuracy, 12.8% versus 12.6%, while using 40.4% fewer search calls and 31.3% lower cost.The reported comparison attributes the gain to spending resources differently rather than simply spending more.
  • Adaptive Strategy Selection: Budget Tracker allocates a larger share of calls to browsing, with a 12.9% browse-to-search ratio versus ReAct’s 9.6%.Browsing supports deeper webpage reading for verification-heavy questions.
  • Adaptive Strategy Selection: BATS further conditions verification on resource availability, balancing answer confidence against whether to continue, pivot, or stop.Verification-guided retries contribute a 5.9 percentage-point gain between early-stopping and full accuracy.

F.2. Adaptive Verification

BATS adapts verification decisions to both trajectory quality and remaining budget. Its verifier can diagnose failure and redirect the agent toward a more promising strategy.

  • Adaptive Verification: Under high budgets, budget-aware agents expand searches from a specific keyword, whereas ReAct applies narrow conditions immediately and fails.The example contrasts resource-abundant exploration with ReAct’s fixed strategy.
  • Adaptive Verification: Under low budgets, Budget Tracker prioritizes query efficiency and precision, while ReAct exhausts resources through exhaustive search.The budget-aware strategy successfully solves the illustrated task.
  • Adaptive Verification: BATS’s verifier recommends a new strategy after identifying the failure cause, enabling a successful next attempt when budget remains.Figure 17 illustrates verification-guided pivoting rather than blind repetition.

G. Limitations

The study is limited by unexamined multi-dimensional resource constraints, substantial experimentation costs, and unresolved questions about resource allocation and context management.

  • More resource constraints: The study does not examine how agents should jointly manage token limits, inference latency, and tool-call budgets.The authors identify multi-dimensional resource control as an important deployment challenge.
  • Computational cost: Scaling tool-augmented agents incurs substantial API-token and tool-call costs, limiting repeated experiments and hyperparameter search.
  • Resource allocation: The analysis does not explore how agents should allocate available resources, despite evidence that models may underestimate their consumption.The authors leave accurate resource estimation and principled budget allocation for future work.
  • More intelligent context management: Advanced context engineering remains largely unexplored beyond simple response removal and trajectory summarization techniques.Open questions include memory formats and balancing context length against performance.
Loading 2511.17006v2…