# LiteSearch: Efficacious Tree Search for LLM

arXiv: https://arxiv.org/abs/2407.00320 · HTML: https://mlsanity.com/paper/2407.00320/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 40 references that are in the map.
- First posted on arXiv 29 Jun 2024.

## Builds on (most cited first, 26 of 26)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [MathQA: Towards Interpretable Math Word Problem Solving with Operation-Based Formalisms](https://mlsanity.com/paper/1905.13319/) (2019)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models](https://mlsanity.com/paper/2401.01335/) (2024)
- [Dynamic Prompt Learning via Policy Gradient for Semi-structured Mathematical Reasoning](https://mlsanity.com/paper/2209.14610/) (2022)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [OpenMathInstruct-1: A 1.8 Million Math Instruction Tuning Dataset](https://mlsanity.com/paper/2402.10176/) (2024)
- [Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing](https://mlsanity.com/paper/2404.12253/) (2024)
- [Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffolding](https://mlsanity.com/paper/2401.12954/) (2024)
- [Self-Discover: Large Language Models Self-Compose Reasoning Structures](https://mlsanity.com/paper/2402.03620/) (2024)
- [Let's reward step by step: Step-Level reward model as the Navigators for Reasoning](https://mlsanity.com/paper/2310.10080/) (2023)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [MindStar: Enhancing Math Reasoning in Pre-trained LLMs at Inference Time](https://mlsanity.com/paper/2405.16265/) (2024)
- [Neural-Symbolic Solver for Math Word Problems with Auxiliary Tasks](https://mlsanity.com/paper/2107.01431/) (2021)
- [GRACE: Discriminator-Guided Chain-of-Thought Reasoning](https://mlsanity.com/paper/2305.14934/) (2023)
- [FlowMind: Automatic Workflow Generation with LLMs](https://mlsanity.com/paper/2404.13050/) (2024)
- [Deductive Beam Search: Decoding Deducible Rationale for Chain-of-Thought Reasoning](https://mlsanity.com/paper/2401.17686/) (2024)
- [Self-Consistency Boosts Calibration for Math Reasoning](https://mlsanity.com/paper/2403.09849/) (2024)

## Built on by (most cited first, 30 of 31)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [Beyond Examples: High-level Automated Reasoning Paradigm in In-Context Learning via MCTS](https://mlsanity.com/paper/2411.18478/) (2024)
- [HunyuanProver: A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving](https://mlsanity.com/paper/2412.20735/) (2024)
- [Towards Self-Improvement of LLMs via MCTS: Leveraging Stepwise Knowledge with Curriculum Preference Learning](https://mlsanity.com/paper/2410.06508/) (2024)
- [CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models](https://mlsanity.com/paper/2509.09675/) (2025)
- [RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation](https://mlsanity.com/paper/2409.09584/) (2024)
- [Non-myopic Generation of Language Models for Reasoning and Planning](https://mlsanity.com/paper/2410.17195/) (2024)
- [Scaling Inference-Time Search with Vision Value Model for Improved Visual Comprehension](https://mlsanity.com/paper/2412.03704/) (2024)
- [Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation](https://mlsanity.com/paper/2412.15118/) (2024)
- [Plan Then Action:High-Level Planning Guidance Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2510.01833/) (2025)
- [RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning](https://mlsanity.com/paper/2505.14140/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [BEATS: Optimizing LLM Mathematical Capabilities with BackVerify and Adaptive Disambiguate based Efficient Tree Search](https://mlsanity.com/paper/2409.17972/) (2024)
- [Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls](https://mlsanity.com/paper/2502.11183/) (2025)
- [ScalingNoise: Scaling Inference-Time Search for Generating Infinite Videos](https://mlsanity.com/paper/2503.16400/) (2025)
- [Investigating Inference-time Scaling for Chain of Multi-modal Thought: A Preliminary Study](https://mlsanity.com/paper/2502.11514/) (2025)
- [LongDPO: Unlock Better Long-form Generation Abilities for LLMs via Critique-augmented Stepwise Information](https://mlsanity.com/paper/2502.02095/) (2025)
- [C2: Scalable Auto-Feedback for LLM-based Chart Generation](https://mlsanity.com/paper/2410.18652/) (2024)
- [PATS: Process-Level Adaptive Thinking Mode Switching](https://mlsanity.com/paper/2505.19250/) (2025)
- [Enhancing Test-Time Scaling of Large Language Models with Hierarchical Retrieval-Augmented MCTS](https://mlsanity.com/paper/2507.05557/) (2025)
- [LLMPC: Large Language Model Predictive Control](https://mlsanity.com/paper/2501.02486/) (2025)
- [How Far are LLMs from Real Search? A Comprehensive Study on Efficiency, Completeness, and Inherent Capabilities](https://mlsanity.com/paper/2502.18387/) (2025)
- [Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs](https://mlsanity.com/paper/2602.09574/) (2026)
- [Multi-Programming Language Ensemble for Code Generation in Large Language Model](https://mlsanity.com/paper/2409.04114/) (2024)
- [Streaming Looking Ahead with Token-level Self-reward](https://mlsanity.com/paper/2503.00029/) (2025)
- [Dual-Stage Value-Guided Inference with Margin-Based Reward Adjustment for Fast and Faithful VLM Captioning](https://mlsanity.com/paper/2506.15649/) (2025)
- [Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search](https://mlsanity.com/paper/2509.25420/) (2025)
- [Reward Model Generalization for Compute-Aware Test-Time Reasoning](https://mlsanity.com/paper/2505.18065/) (2025)

## Abstract (arXiv)

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.