Cost-Aware Test-Time Scaling for Tool-Using LLM Agents

Contents

An AI agent can achieve 12.8% accuracy while spending 31.3% less per question than a conventional baseline, according to experiments published on Arxiv. In a BrowseComp experiment, Gemini 2.5 Pro with a budget tracker achieved that accuracy at a reported cost of 6.8 cents per question, compared with 12.6% accuracy and 9.9 cents for the baseline.

The result exposes a fundamental problem in agentic AI: giving a model more computation and tool access does not guarantee better answers. An agent might execute more searches, inspect additional pages and generate longer reasoning traces without resolving the question any further.

Cost-aware test-time scaling tackles this problem by asking how an agent should allocate its limited resources across reasoning, external actions, exploration and verification.

Why test-time scaling needs a cost model

Test-time scaling allocates additional computation to a model while it solves a task. Traditional approaches increase reasoning tokens, generate alternative answers or run multiple trajectories before selecting a result.

Tool-using agents introduce a second dimension: interaction with external systems. A research agent can search the web, open documents, execute code and query APIs. Each action may provide new evidence, but it also adds cost and latency.

Imagine an agent investigating a software vulnerability. After finding the original advisory, it could inspect the vendor’s security bulletin and check the affected versions. Alternatively, it could make another six searches that return articles repeating the same announcement.

Both approaches consume resources. Only one is likely to resolve an important uncertainty.

The technical objective is to maximize task performance under explicit resource constraints:

Maximize expected task utility

Subject to:
  Monetary cost ≤ budget
  Tool calls ≤ call limit
  Output tokens ≤ token limit
  Completion time ≤ latency target

This formulation makes a useful distinction between spending less and accomplishing more per unit of expenditure. It also recognizes that monetary cost, latency and compute consumption are separate measures that should not automatically be combined.

Budget Tracker and BATS: making resource allocation explicit

The 2025 paper Budget-Aware Tool-Use Enables Effective Agent Scaling introduces two related approaches: Budget Tracker and BATS, short for Budget-Aware Test-time Scaling.

Budget Tracker is a lightweight, prompt-level mechanism. It informs the agent about its consumed and remaining tool-call budget after interactions. This allows a ReAct-style agent to account for its resource state without requiring additional model training.

BATS extends this idea through structured planning, intermediate summaries and self-verification. Rather than following the same investigation strategy regardless of remaining resources, it can decide whether to pursue a promising lead or explore another direction.

The framework combines three decisions:

Plan: break the question into constraints and unresolved subtasks.
Investigate: allocate search and browsing actions to evidence that could resolve those subtasks.
Verify: assess whether the candidate answer satisfies the question before continuing or stopping.

The researchers evaluated Budget Tracker on BrowseComp, BrowseComp-ZH and HLE-Search. With Gemini 2.5 Pro, adding the tracker raised accuracy from 12.6% to 14.6% on BrowseComp, from 31.5% to 32.9% on BrowseComp-ZH, and from 20.5% to 21.8% on HLE-Search.

The reported savings are equally interesting. In the BrowseComp cost experiment, Budget Tracker used a tool budget of 10, compared with 100 for the ReAct baseline. It achieved comparable accuracy while reducing the unified cost by 31.3%.

a two-panel chart comparing the BrowseComp configurations — AI Budget Tracker Result

Value of Information: choosing the next action

Knowing the remaining budget does not tell an agent which action deserves it. That requires an estimate of the likely benefit of each available action.

The May 2026 paper Inference-Time Budget Control for LLM Search Agents addresses this problem using a task-level Value of Information (VOI) controller.

The controller scores three broad choices: retrieve more evidence, decompose the question further or commit to an answer. It considers task progress, remaining resources and penalties associated with consuming the budget.

Conceptually, the decision resembles this comparison:

Action value =
  expected task improvement
  / estimated resource cost

This is a simplified explanation, not the paper’s exact scoring function. Its VOI method uses operational heuristics rather than a direct Bayesian calculation of information gain.

Consider an agent comparing two vendors’ security capabilities. It has found their product pages, but one vendor’s certification status remains unclear. Another general search may return repeated marketing summaries; checking the certification registry could resolve the issue directly.

A sensible controller should prioritize the registry lookup when its expected benefit justifies the cost. The value of an action depends on the current evidence, not simply on how many calls remain.

The VOI study evaluates four multi-hop question-answering benchmarks with three model backbones under separate tool-call and output-token limits. Its results report positive aggregate gains over several baselines, although performance varies across settings.

Why more trajectories can still produce weaker results

Parallel scaling runs several agent trajectories and selects an answer. Sequential scaling extends a single investigation. Both can improve performance, but both introduce failure modes.

A long sequential trajectory can accumulate irrelevant context or remain trapped in an unproductive approach. Parallel execution can generate a correct answer without reliably selecting it.

The 2026 study Benchmark Test-Time Scaling of General LLM Agents identifies these problems as a context ceiling and a verification gap. Its General AgentBench framework evaluates search, coding, reasoning and tool use, finding that additional scaling does not consistently improve performance in general-agent settings.

This distinction is central to cost-aware design. Generating a correct answer somewhere among ten candidates is useful only if the selection mechanism can identify it. Otherwise, parallel sampling increases expenditure without ensuring a better final response.

diagram showing several agent trajectories producing different answers

What diverse agents contribute

TUMIX: Multi-Agent Test-Time Scaling with Tool-Use Mixture explores another approach: running agents with different tool-use strategies and allowing them to refine their responses.

One agent might rely on textual reasoning, another on web search, and another on code execution. Their value comes from finding different evidence, not merely repeating similar reasoning paths.

The authors report accuracy improvements of up to 3.55 percentage points over their best baseline in selected experiments at near-equal inference cost. They also report that adaptive early termination preserved performance at approximately 49% of the cost of the fixed-round and majority-consistency alternatives they evaluated.

These figures are specific to the paper’s benchmarks and configurations. They do not establish that every multi-agent architecture will be cheaper or more accurate.

Evaluating real cost efficiency

Accuracy alone cannot establish whether a scaling strategy is efficient. A meaningful evaluation must measure realized resource consumption alongside task quality.

At minimum, record the following:

Task success: whether the final answer satisfies the evaluation criteria.
Monetary cost: actual model and tool charges per task.
Resource usage: input and output tokens, tool calls, retries and failed operations.
Latency: median completion time and slowest-tail performance.
Verification quality: how often the agent accepts incorrect answers or rejects correct ones.

Researchers should compare methods under matched models, datasets, tool backends and resource limits. They should also test difficult cases where the first plausible answer is wrong. Otherwise, a controller that stops prematurely can appear economical simply because the evaluation fails to expose its mistakes.

The most useful summary is a cost-performance frontier: the accuracy each method achieves at different levels of actual expenditure.

Plot realized cost on the horizontal axis and task accuracy on the vertical axis

What remains unresolved

Current research demonstrates that explicit budget awareness can improve search-agent performance, but it does not establish a universally optimal controller.

Estimating an action’s future value remains difficult because the agent cannot know in advance whether a tool call will return decisive evidence. Self-verification can also repeat the same errors made during answer generation. In production, infrastructure costs, concurrency and latency introduce further trade-offs.

There is also a generalization problem. Search agents, software engineering agents and systems that modify external applications have different costs and failure consequences. Results from question-answering benchmarks need independent validation before they can guide every deployment.

Balancing AI Reasoning Quality, Verification, and Compute Budgets

Cost-aware test-time scaling treats inference as a resource-allocation problem. Budget Tracker makes constraints visible, BATS combines budget awareness with planning and verification, and VOI-based control attempts to prioritize actions according to their expected contribution.

The next advance will require better estimates of marginal task value, stronger verification and evaluations based on actual cost rather than nominal budgets alone.

The objective is precise: spend additional computation when it is likely to improve the result, stop when further work has little expected value, and retain enough evidence to distinguish a verified answer from an incomplete investigation.