Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

Yushu Li; Wenlong Deng; Jiajin Li; Xiaoxiao Li

Source-linked AI summary

Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

Yushu Li, Wenlong Deng, Jiajin Li, Xiaoxiao Li

arXiv:2603.12634v1Mar 13, 2026cs.LGcs.AI

TL;DR

LLM agents often waste constrained inference resources on redundant or dead-end reasoning, while existing budget-aware approaches may require fine-tuning or lack mid-execution control. BAVT is a training-free dynamic tree-search framework using residual step-level values and budget-conditioned node selection. Across four multi-hop QA benchmarks, it consistently outperforms parallel sampling, including under low budgets where it exceeds baseline performance at 4× the resource allocation.

Problem
Current agents can exhaust token and tool budgets on redundant or low-yield steps, while existing budget-aware methods may require expensive fine-tuning or provide limited control.
Method
BAVT combines dynamic tree-structured search, residual step-level value estimation, and budget-conditioned node selection within a single LLM backbone.
Results
Across four multi-hop QA benchmarks, two model families, and three budget tiers, BAVT consistently outperforms parallel sampling baselines and under low budgets surpasses baseline performance at 4× the resource allocation.
Takeaways & Limitations
The results support intelligent budget management as a more effective performance-efficiency strategy than brute-force compute scaling under the evaluated constraints.
Takeaways & Limitations
The current formulation and evaluations primarily focus on a single external tool, web search, with a uniform discrete cost.

Abstract

from arXiv · show

Test-time scaling has become a dominant paradigm for improving LLM agent reliability, yet current approaches treat compute as an abundant resource, allowing agents to exhaust token and tool budgets on redundant steps or dead-end trajectories. Existing budget-aware methods either require expensive fine-tuning or rely on coarse, trajectory-level heuristics that cannot intervene mid-execution. We propose the Budget-Aware Value Tree (BAVT), a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree guided by step-level value estimation within a single LLM backbone. Another key innovation is a budget-conditioned node selection mechanism that uses the remaining resource ratio as a natural scaling exponent over node values, providing a principled, parameter-free transition from broad exploration to greedy exploitation as the budget depletes. To combat the well-known overconfidence of LLM self-evaluation, BAVT employs a residual value predictor that scores relative progress rather than absolute state quality, enabling reliable pruning of uninformative or redundant tool calls. We further provide a theoretical convergence guarantee, proving that BAVT reaches a terminal answer with probability at least $1-ε$ under an explicit finite budget bound. Extensive evaluations on four multi-hop QA benchmarks across two model families demonstrate that BAVT consistently outperforms parallel sampling baselines. Most notably, BAVT under strict low-budget constraints surpasses baseline performance at $4\times$ the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.

1 Introduction

Test-time scaling improves agent reliability but can waste constrained resources on redundant or low-yield reasoning. BAVT addresses this with training-free, budget-aware tree search that shifts from exploration to exploitation and outperforms parallel sampling under strict budgets.

Motivation: Unrestricted test-time scaling can exhaust token and tool-call budgets on redundant or low-yield steps, while additional spending may yield diminishing accuracy gains.Existing budget-aware approaches also face transfer or granularity limitations.
Approach: BAVT models multi-hop reasoning as a dynamic search tree with step-level value estimation and adaptive resource allocation within a single LLM backbone.Nodes represent intermediate states, while edges correspond to actions or tool invocations.
Approach: BAVT’s residual value critic scores marginal progress rather than absolute state quality, enabling pruning of uninformative branches while mitigating LLM self-evaluation overconfidence.The critic evaluates relative progress at each reasoning step.
Approach: Budget-conditioned node selection provides a parameter-free transition from broad exploration with abundant resources to concentrated exploitation as the budget depletes.The mechanism transforms node values using a power-based scaling function whose exponent is the inverse of the remaining budget ratio.
Results: Across four multi-hop QA benchmarks, two model families, and three budget tiers, BAVT consistently outperforms parallel sampling baselines.The evaluations compare performance across multiple resource levels.
Results: BAVT under strict low-budget constraints surpasses baseline performance at 4× the resource allocation, indicating that intelligent allocation can outperform brute-force scaling.The paper presents this as a performance-efficiency advantage under constrained resources.

2 Related Work

Related work spans tool-using agents, test-time scaling, and budget-aware inference. These approaches improve agent capability or reduce inference cost, but deployed systems can still rely on resource-intensive loops that become trapped in costly dead ends.

Tool-Using Agents: External-tool frameworks interleave reasoning traces with tool actions, enabling LLM agents to interact with dynamic environments and solve complex queries.Examples include ReAct, Toolformer, and WebGPT.
Tool-Using Agents: RL-based tool-use approaches can suffer from severe instability and high computational overhead, limiting their practicality for agent training.The cited related work identifies these as recurring concerns.
Open Challenge: Deployed agents often rely on naive autonomous loops that assume unlimited resources and can become trapped in costly dead ends.This motivates more structured resource management for autonomous inference.
Test-Time Scaling: Test-time scaling allocates additional inference computation to improve reasoning robustness, including for multi-step tool interactions.Self-Consistency and related methods exemplify this direction.
Budget-Aware Inference: Budget-aware inference includes model cascading, routing systems, and dynamic resource allocation for general LLM reasoning.These methods seek to reduce deployment costs or direct computation more selectively.

3 Methodology

BAVT formulates tool-augmented inference as resource-constrained search over a dynamic reasoning tree, combining step-level value estimation with adaptive budget control. Its budget-conditioned expansion policy shifts from exploration toward exploitation, while residual evaluation and a finite-budget convergence guarantee support efficient and reliable termination.

3.1 Problem Formulation: Budget-Aware Agent Inference: BAVT models tool-augmented inference as a resource-constrained deterministic decision process with states, actions, transitions, budgets, and action costs.States include the query, prior actions, reasoning traces, and observations; actions include internal generations and external tool calls, while budgets track remaining tools and tokens.
3.2 Overview of Budget-Aware Value Tree (BAVT): The test-time scaling tree represents intermediate reasoning states as nodes and generated actions as edges, enabling exploration of multiple competing trajectories.The search policy explores branches rather than committing directly to one linear trajectory, reducing exposure to dead-end paths.
3.3 Step-Level Value Estimation: BAVT uses the same LLM backbone as a Generator and Critic to propose actions and evaluate intermediate progress after environmental feedback.The critic provides step-level estimates that guide expansion instead of relying only on delayed trajectory-level evaluation.
3.3 Step-Level Value Estimation: Residual value prediction scores each action’s information delta relative to its parent state, with a bounding function normalizing the updated child value.This relative-progress formulation is designed to reduce overconfidence and penalize redundant or uninformative tool executions.
3.4 Budget-Aware Node Expansion: As the remaining budget falls, BAVT increases its scaling exponent, concentrating node-selection probability on higher-valued candidates and shifting from exploration to exploitation.With abundant resources, selection is roughly proportional to raw node values; as resources deplete, the distribution approaches near-deterministic selection of the highest-valued node.
3.6 Theoretical Analysis: Convergence to Termination: Under three structural assumptions, BAVT has a finite-budget probabilistic convergence guarantee: for any ε > 0, some finite budget bound yields termination probability at least 1 − ε.The proof uses bounded progress toward a value threshold and a finite number of valid expansion steps; completing K steps triggers termination deterministically.

4 Experiments

Experiments compare BAVT with budget-matched parallel sampling across four multi-hop QA benchmarks, two model families, and three resource tiers. BAVT maintains stronger performance-efficiency trade-offs, while ablations show that step-level value and budget-aware selection are central to its gains.

Main Results: BAVT achieves 0.338 average EM at Low budget with OSS-20B, exceeding the baseline’s 0.334 High-budget peak while using one-quarter of the resources.The Low tier uses 5 tool calls, compared with 20 at High.
Reasoning Model: BAVT elevates OSS-20B average EM from the baseline’s 0.194 to 0.338 at Low budget and consistently outperforms the baseline across all three tiers.The baseline rises from 0.194 to 0.334 as its budget increases, whereas BAVT’s advantage is strongest under tight constraints.
Instruct Model: BAVT reaches 0.386 average EM for Qwen3-30B at Low budget, overcoming the baseline’s plateau from 0.289 EM at Low to 0.293 EM at High.The reported mechanism is value-guided search widening, which induces divergent tool calls when trajectories yield zero information gain.
Dataset-Specific Results: On MuSiQue, BAVT raises Qwen3-30B EM from the baseline’s 0.12 plateau to 0.21, while on 2Wiki OSS-20B reaches 0.37 EM at Low versus 0.38 for the baseline at High.On Bamboogle, OSS-20B improves from 0.31 to 0.49 EM at Low and plateaus at 0.55 EM at Middle.
Ablation Studies: Ablations yield 0.215 average EM for random tree expansion, 0.309 with step-level value, and 0.388 with full budget-aware node selection.Unguided tree search fragments computation, while the budget-aware exponent shifts selection toward exploitation as resources deplete.

5 Conclusion

BAVT addresses inefficiencies in unconstrained test-time scaling by using dynamic search, step-level criticism, and budget-aware node selection. Across four multi-hop QA benchmarks, it improves the performance-efficiency trade-off under strict resource constraints.

BAVT models multi-hop reasoning as a dynamic search tree guided by an LLM-driven step-level critic.Its node-selection mechanism transitions from broad exploration to greedy exploitation as computational budgets deplete.
BAVT is training-free and consistently outperforms robust parallel sampling baselines across four multi-hop QA benchmarks.The evaluation reports a superior performance-efficiency trade-off across the benchmark suite.
Under strict low-budget constraints, BAVT frequently surpasses the high-budget performance of standard methods.The conclusion attributes this result to mitigating compounding reasoning errors and the mode-collapse plateau in instruction-tuned architectures.

6 Limitations and Future Work

The paper identifies limitations involving critic overhead, simplified tool-cost modeling, and evaluation confined to knowledge-intensive multi-hop question answering. Future work targets lightweight critics, multidimensional tool pricing, and long-horizon interactive tasks.

Inference Overhead of the Critic: Evaluating every intermediate step with the main LLM backbone consumes part of the overall token budget.The authors report this overhead as empirically net-positive on complex multi-hop tasks but propose lightweight PRMs or value heads as alternatives.
Heterogeneous Tools and Asymmetric Costs: The current formulation and evaluation focus on a single web-search tool with uniform discrete cost C_tool = 1.Real deployments may require handling tools with asymmetric financial costs, latencies, and rate limits.
Extension to Long-Horizon Agent Tasks: The evaluation is centered on knowledge-intensive multi-hop question answering rather than open-ended, long-horizon interactive environments.Extending BAVT to such environments requires handling irreversible actions, partial observability, delayed rewards, and more nuanced temporal credit assignment.

A BAVT Algorithm

Algorithm 1 initializes BAVT with a query, resource budgets, a search tree, and a candidate set, then repeatedly selects, expands, evaluates, and backpropagates through nodes. After budget consumption, it returns an answer from the highest-valued available leaf.

1. Budget-Aware Node Selection: The remaining-resource ratio r_t sets α_t = 1/r_t, making node sampling increasingly value-focused as resources deplete.Expansion nodes are sampled from the candidate pool proportionally to V(n_i)^α_t.
Initialization: BAVT initializes a root query, tool and token budgets, a tree, a candidate set, and an empty answer set.The initial root state is the query, with budget b_0 = (B_tool, B_token).
2. Action Generation and Transition: After node selection, BAVT issues a structural instruction based on node value to widen, deepen, or answer.This step generates and transitions candidate actions within the tree.
3. Value Critic and Backpropagation: The critic predicts residual progress for a successor node, updates its value, and backpropagates values through the tree when answers are available.A skipped candidate inherits the parent value, while evaluated successors receive an update based on the predicted residual.
4. Backstop Answer Generation: BAVT returns the answer extracted from the available leaf with maximum value.The backstop answer-generation step selects n* = arg max over available nodes of V(n).

B.1 Hyperparameter Configurations

The framework keeps dynamic search parameters constant across datasets for reproducibility and generalization analysis. State values are normalized to [0.1, 1.0], while residual deltas are clipped before updating parent scores.

BAVT holds dynamic search parameters constant across all datasets to demonstrate framework generalization.The hyperparameters are documented in Table 2 for reproducibility.
Value Scaling and Normalization: Raw critic scores from 1 to 10 are normalized by 10, constraining operational state values V(n) to [0.1, 1.0].The normalization stabilizes exponentiation during budget-annealed node sampling.
Value Scaling and Normalization: Residual information deltas Δ_t are clipped to [−4, +4] before being applied to the parent node’s score.

B.2 Cost Estimation Analysis

The cost analysis estimates maximum per-sample costs across three budget configurations using a 10:1 input-to-output token assumption. External search operations account for over 90% of expenditure, making redundant-tool-call pruning central to budget efficiency.

Scope: The analysis estimates maximum theoretical deployment cost per sample across three predefined budget configurations.This contextualizes BAVT's economic efficiency during deployment.
Pricing assumptions: Input token volume is conservatively estimated at 10× output token volume for multi-hop tasks with retrieved contexts.The token budget represents maximum output tokens, while retrieved-context prompts are assumed to be substantially longer.
Cost drivers: Over 90% of cost per sample comes from external search queries across budget tiers and model architectures.The analysis characterizes search operations as vastly dominating inference expenditure.
Cost drivers: Table 3 estimates maximum per-sample costs in USD across budget tiers, with search operations constituting most total cost.The table uses an input-to-output token ratio of 10:1.

C System Prompt Templates

The system prompts specify separate generator, critic, planner, and dynamic-control roles for BAVT. Together, they enforce one-action generation, conservative step-level value assessment, abstract planning, and budget-responsive expansion or answering.

C.1 Generator (Actor) System Prompt: The generator handles multi-hop question answering with one action per turn and a one-line final answer in an answer tag.It may call tools across multiple rounds but must submit exactly one final answer.
C.2 Step-Level Critic Prompt: The critic judges the quality of the agent's latest action rather than solving the question itself.Its output is constrained to a JSON object containing only a delta field.
C.2 Step-Level Critic Prompt: The critic represents absolute value on a 1–10 scale, with node 0 starting at 1 and higher values indicating greater likelihood of a correct final answer.The critic receives prior value and step history, then outputs only the relative delta as an integer in [-4, +4].
C.2 Step-Level Critic Prompt: Critic scoring is conservative: weak or ambiguous evidence should avoid positive deltas, while no meaningful gain should receive a nonpositive delta.The implied new value must remain within [1, 10].
C.2 Step-Level Critic Prompt: The critic uses five calibrated tiers ranging from no basis or impossibility to near-certain or certain correctness.A score of 10 is intended to be rare, and the criteria also penalize speculation, repetition, unjustified leaps, and low information gain.
C.3 High-Level Planner Prompt: The planner produces an abstract 2–5-step outline that states which fact or relationship must be established at each hop.It must not answer the question, invent facts, or specify concrete searches, tools, websites, queries, or data sources.
C.4 Dynamic Structural Instructions: During tree expansion, dynamic instructions are selected from critic value estimates to control whether the generator answers, widens, or deepens.The generator prompt replaces a dynamic placeholder with deterministic commands.
C.4 Dynamic Structural Instructions: Widening follows a nonpositive value gain by requiring a different query or reasoning path, while deepening directs one next action unless evidence already suffices.A budget backstop forces an immediate answer without further tool calls when resources are exhausted.