Research

MachinoAI Research

IMPORTANTAI Agents

Budget-Aware Tool Use Enables Effective Agent Scaling

Agent scaling is not just more tokens or tool calls; agents must know and strategically allocate their remaining budget.

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 LeeAug 17, 2026arXiv; cs.AI12 min read
AI Agentstest-time scalingagent coststool usebudget awarenessweb search agentsBATSbudget-constrained optimizationunified costadaptive planning

TL;DR

Budget Tracker adds explicit resource state to the agent loop, while BATS adds adaptive planning and verification; under a 100-call-per-tool budget, Gemini-2.5-Pro with BATS reaches 24.6% BrowseComp, 46.0% BrowseComp-ZH, and 27.0% HLE-Search.

Why It Matters

Production agents pay for both reasoning tokens and external calls. Budget awareness turns a fixed tool allowance into a controllable resource-allocation problem, enabling better cost-performance trade-offs and clearer stopping behavior.

Research Brief

The shortest useful explanation.

Budget Tracker adds explicit resource state to the agent loop, while BATS adds adaptive planning and verification; under a 100-call-per-tool budget, Gemini-2.5-Pro with BATS reaches 24.6% BrowseComp, 46.0% BrowseComp-ZH, and 27.0% HLE-Search.

budget-constrained optimizationunified costadaptive planningself-verificationearly stoppingcost-performance Pareto frontiertest-time scalingagent costs

Core Explanation

The paper studies test-time scaling for tool-augmented agents under explicit tool-call budgets. It introduces Budget Tracker for continuous budget awareness and BATS for budget-aware planning and self-verification, together with a unified cost metric covering token and tool-call costs.

Why It Matters

Production agents pay for both reasoning tokens and external calls. Budget awareness turns a fixed tool allowance into a controllable resource-allocation problem, enabling better cost-performance trade-offs and clearer stopping behavior.

Budget Tracker exposes query and URL budgets to the agent before tool calls.

Budget Tracker in the agent loop

Original arXiv HTML figure showing budget state supplied before the next reasoning and tool call.

Accuracy versus tool budget for ReAct and ReAct plus Budget Tracker.

Budget-aware scaling curve

Original arXiv HTML plot showing ReAct saturating while Budget Tracker continues to scale with more tool budget.

BATS iterative planning and verification loop under per-tool budgets.

BATS framework

Original arXiv HTML figure showing budget-aware planning, tool execution, verification, pivoting, and answer selection.

Section 01

Problem

01. Problem

Tool-augmented agents have two coupled scaling resources: internal reasoning tokens and external tool calls. Giving an agent a larger tool-call budget does not automatically improve performance because standard agents may keep using a rigid search strategy and stop before exploiting the available budget. The paper formulates agent scaling as maximizing accuracy under explicit per-tool budgets.

1More tool calls can increase cost without proportional accuracy gains.2Agents can terminate early or repeatedly pursue low-yield paths.3Production systems need a unified view of token and tool costs.

Section 02

How It Works

03. How It Works

Budget Tracker appends policy guidance and real-time remaining/used budgets after tool interactions. BATS adds a persistent tree-structured plan, exploration and verification decomposition, and a backward constraint check over candidate answers. Verification returns SUCCESS, CONTINUE, or PIVOT; failed paths can be summarized before another attempt.

1Budget Tracker: budget state after tool calls.2Planning: maintain a tree of completed, failed, and partial subtasks.3Verification: check each question constraint as satisfied, contradicted, or unverifiable.4Decision: SUCCESS, CONTINUE, or PIVOT.

Section 03

Architecture

05. Architecture

The system is a ReAct-style search agent with Search and Browse tools. Budget Tracker can be inserted as a plug-in. BATS wraps the loop with planning, tool execution, self-verification, retry/pivot behavior, trajectory summarization, and final answer selection. The architecture is training-free in the reported BATS experiments.

1LLM reasoning and planning.2Search/Browse tool layer.3Budget tracking and resource state.4BATS planning tree.5Self-verification and answer selection.

Section 04

Experiments

06. Experiments

The paper evaluates on BrowseComp (1,266 questions), BrowseComp-ZH (289), HLE-Search (200), and a 114-task retail subset of tau2-bench. Budget Tracker improves accuracy across models under identical budgets. BATS is evaluated under 100 tool uses per tool and compared with ReAct, SLIM, and training-based agents.

1Budget Tracker with Gemini-2.5-Pro: ReAct 12.6±1.2/31.5±1.5/20.5±0.5 vs Budget Tracker 14.6±1.2/32.9±0.5/21.8±1.0 on BrowseComp/BrowseComp-ZH/HLE-Search.2At budget 10, Budget Tracker reaches 12.8% vs ReAct 12.6% at budget 100, with 40.4% fewer search calls, 19.9% fewer browse calls, and 31.3% lower cost.3BATS with Gemini-2.5-Pro at 100 calls per tool: BrowseComp 24.6%, BrowseComp-ZH 46.0%, HLE-Search 27.0%.4BATS ablation: full 18.7/39.1/23.0 vs without planning 17.0/34.6/20.0, without verification 15.4/37.7/22.0, without both 14.6/32.9/21.5.

Formulas

Budget-constrained accuracy

\\max_{\\pi} \\mathrm{Acc}_{\\mathbf b}(\\pi)=\\mathbb{E}_x[\\mathbf{1}\\{\\hat y_\\pi(x)=y(x)\\}]\\quad\\mathrm{s.t.}\\quad c_i(x;\\pi)\\le b_i

The agent maximizes expected accuracy while never exceeding the allocated call budget for any tool.

yground-truth answer
piagent policy
b_imaximum calls for tool i
c_irealized calls for tool i
yhatagent answer

Unified agent cost

Cmathrmunified(x;pi)=cmathrmtoken(x;pi)+sumi=1Kci(x;pi)PiC_{\\mathrm{unified}}(x;\\pi)=c_{\\mathrm{token}}(x;\\pi)+\\sum_{i=1}^{K}c_i(x;\\pi)P_i

Total economic cost combines token consumption with the cost of each realized tool invocation.

Knumber of tools
P_ieconomic price per call
c_inumber of calls to tool i
c_tokentoken cost

Related Research

AI Agents

Generative Agents

An agent architecture combining memory, retrieval, reflection, and planning to simulate believable long-horizon behavior.

AI Agents

MIRA

MIRA is an autonomous medical agent evaluated in a sandboxed EHR workflow with tools for diagnosis, testing, treatment, and admission decisions.

AI Agents

Agentic Reasoning

A tool-using agent framework that extends LLM reasoning with web search, coding, and structured reasoning memory for deep research tasks.

References

ReAct: Synergizing Reasoning and Acting in Language Models

Base reasoning/action loop used by the search-agent experiments.

BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents

Primary browsing benchmark used in the experiments.

Lost in the Maze: Overcoming Context Limitations in Long-Horizon Agentic Search

SLIM baseline for context-efficient long-horizon search.

arXiv v2arXiv HTML v2Official GitHub repository