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 guided by step-level value estimation within a single LLM backbone. BAVT uses a budget-conditioned node selection mechanism and a residual value predictor to combat overconfidence in LLM self-evaluation, enabling reliable pruning of uninformative tool calls. Empirical results on multi-hop QA benchmarks show that BAVT outperforms parallel sampling baselines, achieving superior performance under low-budget constraints compared to baselines with 4x the resource allocation.
Intelligent budget management in LLM agents can outperform brute-force compute scaling by 4x, thanks to a new search algorithm that prunes redundant steps and focuses on promising trajectories.
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 4times the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.
