LiteSearch: Efficacious Tree Search for LLM
Authors: name: Ante Wang; name: Linfeng Song; name: Ye Tian; name: Baolin Peng; name: Dian Yu; name: Haitao Mi; name: Jinsong Su; name: Dong Yu
Published: 2024-06-29 05:14:04

Abstract: 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 dynamic node selection 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 and TabMWP datasets
demonstrate that our approach not only offers competitive performance but also
enjoys significantly lower computational costs compared to baseline methods.