LiteSearch: Efficacious Tree Search for LLM

2024/06/29 by Ante Wang, Linfeng Song, Wang, Ante +13 · 7 citations
Computer Science · #Artificial Intelligence (cs.AI) #Computation and Language (cs.CL) #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Natural Language Processing Techniques #Semantic Web and Ontologies

paper · pdf · doi:10.48550/arxiv.2407.00320

openalex publication_date 2024/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Plan Then Action:High-Level Planning Guidance Reinforcement Learning for LLM Reasoning
• Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search
• CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models
• Enhancing Test-Time Scaling of Large Language Models with Hierarchical Retrieval-Augmented MCTS
• Dual-Stage Value-Guided Inference with Margin-Based Reward Adjustment for Fast and Faithful VLM Captioning
• Reward Model Generalization for Compute-Aware Test-Time Reasoning
• RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning

Related

• Enhancing LLM Reasoning with Reward-guided Tree Search
• Policy Guided Tree Search for Enhanced LLM Reasoning
• LLM-First Search: Self-Guided Exploration of the Solution Space
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls
• Limits of PRM-Guided Tree Search for Mathematical Reasoning with LLMs