Reproduce “Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents” on OpenResearch

About this paper

Yushu Li, Wenlong Deng, Jiajin Li, Xiaoxiao Li

The Budget-Aware Value Tree (BAVT) framework, developed by researchers at the University of British Columbia and Vector Institute, enables Large Language Model (LLM) agents to perform multi-hop reasoning with high efficiency and reliability under strict computational budgets. It consistently surpasses parallel sampling baselines, often achieving better task performance with 75% less resource allocation, by integrating a dynamic search tree with step-level value estimation and an adaptive exploration-exploitation strategy.

Key insights

• Intelligent, fine-grained budget management at inference time fundamentally outperforms brute-force compute scaling in LLM agent performance and efficiency.
• Step-level value estimation, particularly predicting residual information gain, effectively mitigates LLM overconfidence and provides crucial guidance for efficient search.
• Dynamically adjusting the exploration-exploitation balance based on remaining budget is critical for maximizing performance under tight resource constraints, preventing early budget exhaustion.
• The BAVT framework effectively addresses issues like compounding errors in reasoning models and 'mode collapse' in instruction-tuned models by guiding diverse and relevant search trajectories.

Summary by alphaXiv.