LiteSearch: Efficient Tree Search with Dynamic Exploration Budget for Math Reasoning

Recent research suggests that tree search algorithms (e.g. Monte Carlo Tree Search) can dramatically boost LLM performance on complex mathematical reasoning tasks. However, they often require more than 10 times the computational resources of greedy decoding due to wasteful search strategies, making them difficult to be deployed in practical applications. This study introduces a novel guided tree search algorithm with a goal-directed heuristic function and node-level exploration budget (maximum number of children) calculation to tackle this issue. By considering the search progress towards the final answer (history) and the guidance from a value network (future) trained without any step-wise annotations, our algorithm iteratively selects the most promising tree node before expanding it within the boundaries of the allocated computational budget. Experiments conducted on the GSM8K, TabMWP, and MATH datasets demonstrate that our method not only offers competitive performance but also enjoys significantly lower computational costs compared to baseline methods.

Authors

• Ante Wang School of Informatics, Xiamen University, China Shanghai Artificial Intelligence Laboratory, China
• Linfeng Song Tencent AI Lab, Bellevue, WA
• Ye Tian Tencent AI Lab, Bellevue, WA
• Baolin Peng Tencent AI Lab, Bellevue, WA
• Dian Yu Tencent AI Lab, Bellevue, WA
• Haitao Mi Tencent AI Lab, Bellevue, WA
• Jinsong Su School of Informatics, Xiamen University, China Shanghai Artificial Intelligence Laboratory, China Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, China
• Dong Yu Tencent AI Lab, Bellevue, WA

Keywords

No keywords are indexed for this paper.