Search papers, labs, and topics across Lattice.
The paper introduces Budget-Aware Value Tree (BAVT), a training-free inference-time framework that optimizes LLM agent reasoning by modeling it as a dynamic search tree with step-level value estimation. BAVT uses a budget-conditioned node selection mechanism and a residual value predictor to intelligently allocate resources and prune uninformative tool calls. Empirical results on multi-hop QA benchmarks show that BAVT achieves superior performance compared to parallel sampling baselines, even with significantly lower budget constraints.
Intelligent budget management in LLM agents can outperform brute-force compute scaling by 4x, thanks to a novel search tree algorithm that prunes redundant steps.
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-\epsilon$ 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.
