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× the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.
Figures & tables
Figure 1: Budget-Aware Value Tree (BAVT) versus parallel sampling. Left: Parallel sampling explores many trajectories in parallel but may waste budget on redundant or dead-end paths. Right: BAVT performs tree-structured search with step-level value estimation and budget-aware expansion to adaptively shift from broad exploration (high remaining budget) to deep exploitation (low remaining budget), improving the performance–efficiency trade-off under strict resource constraints.
Figure 2: Overview of the Budget-Aware Value Tree (BAVT) framework. a) Budget-Aware Expansion dynamically adjusts the node selection distribution, shifting from exploration to exploitation as resources deplete. b) The Test-Time Scaling Tree models the reasoning process, allowing the agent to explore multiple paths. c) Step-Level Value Estimation utilizes a dual-role Actor-Critic setup within a single backbone to evaluate intermediate progress at the step level.
Figure 3: Average performance-efficiency trade-off across the four evaluated multi-hop QA benchmarks for OSS-20B and Qwen3-30B. BAVT operating under strict Low budget constraints (5 calls) consistently rivals or surpasses the baseline’s High budget performance (20 calls), demonstrating that intelligent resource management fundamentally outperforms 4× brute-force compute scaling.
Figure 4: Performance of the OSS-20B reasoning model on multi-hop QA benchmarks. BAVT achieves strictly superior performance and resource efficiency compared to the baseline across all datasets and budget constraints.
Figure 5: Performance of the Qwen3-30B instruct model across multi-hop QA benchmarks. BAVT achieves strictly superior performance, effectively raising the baseline’s ceiling.
Components
HotpotQA
2Wiki
MuSiQue
Bamboogle
AVG
Tree
Value
Budget
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
×
×
×
0.344
0.469
0.205
0.261
0.142
0.203
0.381
0.517
0.268
0.363
✓
×
×
0.243
0.340
0.124
0.163
0.100
0.140
0.392
0.478
0.215
0.280
✓
✓
×
0.356
0.481
0.265
0.332
0.158
0.224
0.456
0.575
0.309
0.403
✓
✓
✓
0.402
0.552
0.413
0.517
0.186
0.272
0.552
0.666
0.388
0.502
Table 1: Ablation study isolating the impact of the Tree Structure, Step-Level Value, and Budget-Aware Node Selection using the OSS-20B model at the Middle budget tier. Checkmarks (✓) indicate an active component, while crosses ( × ) indicate an inactive component.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Parameter
Value
Raw Critic Value Scale
[1,10]
Residual Delta Bounds ( Δt )
[−4,+4]
Normalized State Value Range V(n)
[0.1,1.0]
Terminal Confidence Threshold ( τ )
0.8
Budget Backstop Threshold ( η )
0.2
Max Output Tokens per Call
512
Appendix
Table 2: Core hyperparameters for the BAVT framework and LLM generation.
Budget
Max Tool
Search
Reasoning Model (GPT-OSS)
Instruct Model (Qwen)
Tier
Calls
Cost ($)
Token Cost ($)
Total Cost ($)
Token Cost ($)
Total Cost ($)
Low
5
0.025
0.00088
0.02588
0.00108
0.02608
Middle
10
0.050
0.00176
0.05176
0.00216
0.05216
High
20
0.100
0.00352
0.10352
0.00432
0.10432
Appendix
Table 3: Estimated maximum cost per sample (in USD) across budget tiers. Token costs assume an input-to-output token ratio of 10:1. Search operations constitute the vast majority of the total cost.
While agents are increasingly spending more resources, today agent cost is mostly measured only after execution. A Budget-Aware Agent (BAGEN) should treat budget as an active control signal, rather than a passive cost metric. We first systematically define budget estimation as internal budgets (from agent computation) and external budgets (from agent actions). We then formalize budget-awareness as progressive interval estimation: at each step of a plan, an agent should predict an upper and lower bound on remaining budget, and alert when completion is unlikely. Scoring with a rollout-replay protocol, we find consistent failure patterns on four environments and five frontier agents: (1) strong agents do not necessarily have strong budget-awareness, with correlation r=0.35. (2) frontier models are consistently over-optimistic, continue spending on tasks that are unlikely to succeed, instead of alerting the user early. (3) budget-aware signal is actionable and trainable. Early stop saves 28-64% tokens on failed trajectories, and SFT+RL strengthens early stop and alert behavior. (4) precise interval calibration remains challenging, with interval coverage capping at 47% after SFT+RL. Project page: https://ragen-ai.github.io/bagen/
Yuxiang Lin, Zihan Wang, Mengyang Liu +9
1Northwestern University · 2O2 Lab · 3Independent +5
LLM search agents increasingly rely on tools at inference time, but their trajectories are often constrained by hard limits on both tool calls and generated tokens. Under such dual budgets, better answers require not only stronger models, but also explicit control over which search action should receive the next budget unit and when the accumulated evidence is sufficient to commit a final answer. We study this problem in multi-hop question answering (QA) and formulate it as two-stage inference-time budget control. At search time, our controller assigns each feasible action a task-level Value-of-Information (VOI) score, defined as an operational estimate of marginal task value per unit budget under the current search state and remaining dual budget, and uses this score to choose among retrieval, decomposition, and answer commitment. After search, a selective evidence-grounded finalizer compares the trajectory answer with a refined candidate and rewrites only when the residual error appears to be a low-risk answer-form error. Across four multi-hop QA benchmarks, three LLM backbones, and four budget levels, the method yields positive aggregate gains over four audited baselines under the same hard dual-budget protocol. Ablations show that search-time budget control, especially budget-dependent penalty, provides the main performance gain, while answer-time control helps mainly when the retrieval path is already adequate. These results suggest that inference-time budget control for LLM search agents should govern both how budget is spent during search and how the final answer is committed.
Scaling test-time compute via extended reasoning has become a key paradigm for improving the capabilities of large language models (LLMs). However, existing approaches optimize reasoning under fixed or uniformly sampled token budgets, ignoring the fundamental mismatch between problem difficulty and allocated compute. This leads to overthinking on easy problems and underthinking on hard ones, resulting in suboptimal token efficiency across diverse reasoning scenarios. In this paper, we propose Budget-Adaptive Curriculum Reasoning (BCAE), a unified framework that jointly optimizes reasoning quality and token efficiency through three synergistic components: (1) a budget-conditioned unified policy that embeds the token budget as a continuous conditioning signal, eliminating the need for decoupled thinking and summarization strategies; (2) a curriculum-aware budget scheduler that adaptively shifts the training budget distribution from easy to hard problems based on real-time learning progress; and (3) a truncation-aware dense reward mechanism that provides fine-grained credit assignment at intermediate reasoning steps via process-level verification. We further introduce Budget-Conditioned Advantage Estimation (BCAE), a novel variance reduction technique that conditions the advantage baseline on the sampled budget, yielding more stable policy gradients. Experiments on mathematical reasoning benchmarks (MATH, GSM8K, AIME, and Minerva Math) demonstrate that BACR consistently outperforms other strong baselines across all token budgets, achieving up to 8.3% accuracy improvement under tight budgets while reducing average token consumption by 34% compared to unconstrained reasoning.