LiteSearch: Efficacious Tree Search for LLM
This addresses the computational inefficiency problem for deploying tree search in practical LLM applications, representing an incremental improvement over existing methods.
The paper tackles the high computational cost of tree search algorithms for LLMs in mathematical reasoning by introducing a guided tree search with dynamic node selection and budget calculation, achieving competitive performance on GSM8K and TabMWP datasets with significantly lower computational costs.
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.