# Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning

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

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 38 of its 52 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 38)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [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)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023)
- [WizardCoder: Empowering Code Large Language Models with Evol-Instruct](https://mlsanity.com/paper/2306.08568/) (2023)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning](https://mlsanity.com/paper/2309.05653/) (2023)
- [Fine-Grained Human Feedback Gives Better Rewards for Language Model Training](https://mlsanity.com/paper/2306.01693/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [Complexity-Based Prompting for Multi-Step Reasoning](https://mlsanity.com/paper/2210.00720/) (2022)
- [Llemma: An Open Language Model For Mathematics](https://mlsanity.com/paper/2310.10631/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)

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

- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking](https://mlsanity.com/paper/2501.04519/) (2025)
- [AI Agents vs. Agentic AI: A Conceptual Taxonomy, Applications and Challenges](https://mlsanity.com/paper/2505.10468/) (2025)
- [O1 Replication Journey: A Strategic Progress Report -- Part 1](https://mlsanity.com/paper/2410.18982/) (2024)
- [LLM Post-Training: A Deep Dive into Reasoning Large Language Models](https://mlsanity.com/paper/2502.21321/) (2025)
- [Interactive Post-Training for Vision-Language-Action Models](https://mlsanity.com/paper/2505.17016/) (2025)
- [LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning](https://mlsanity.com/paper/2410.02884/) (2024)
- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Dynamic Parallel Tree Search for Efficient LLM Reasoning](https://mlsanity.com/paper/2502.16235/) (2025)
- [UProp: Investigating the Uncertainty Propagation of LLMs in Multi-Step Agentic Decision-Making](https://mlsanity.com/paper/2506.17419/) (2025)
- [RAG-Star: Enhancing Deliberative Reasoning with Retrieval Augmented Verification and Refinement](https://mlsanity.com/paper/2412.12881/) (2024)
- [A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoning](https://mlsanity.com/paper/2501.02497/) (2025)
- [S2R: Teaching LLMs to Self-verify and Self-correct via Reinforcement Learning](https://mlsanity.com/paper/2502.12853/) (2025)
- [Benchmarking Agentic Workflow Generation](https://mlsanity.com/paper/2410.07869/) (2024)
- [Enhancing LLM Reasoning with Iterative DPO: A Comprehensive Empirical Investigation](https://mlsanity.com/paper/2503.12854/) (2025)
- [HunyuanProver: A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving](https://mlsanity.com/paper/2412.20735/) (2024)
- [LiteSearch: Efficacious Tree Search for LLM](https://mlsanity.com/paper/2407.00320/) (2024)
- [Think More, Hallucinate Less: Mitigating Hallucinations via Dual Process of Fast and Slow Thinking](https://mlsanity.com/paper/2501.01306/) (2025)
- [CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models](https://mlsanity.com/paper/2509.09675/) (2025)
- [AgentRM: Enhancing Agent Generalization with Reward Modeling](https://mlsanity.com/paper/2502.18407/) (2025)
- [Step-wise Adaptive Integration of Supervised Fine-tuning and Reinforcement Learning for Task-Specific LLMs](https://mlsanity.com/paper/2505.13026/) (2025)
- [On the Emergence of Thinking in LLMs I: Searching for the Right Intuition](https://mlsanity.com/paper/2502.06773/) (2025)
- [A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks](https://mlsanity.com/paper/2501.10069/) (2025)
- [Reason4Rec: Deliberative User Preference Alignment of Large Language Models for Recommendation](https://mlsanity.com/paper/2502.02061/) (2025)
- [A Technical Survey of Reinforcement Learning Techniques for Large Language Models](https://mlsanity.com/paper/2507.04136/) (2025)
- [QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search](https://mlsanity.com/paper/2502.02584/) (2025)
- [Quantifying Generalization Complexity for Large Language Models](https://mlsanity.com/paper/2410.01769/) (2024)
- [Improving Multi-Step Reasoning Abilities of Large Language Models with Direct Advantage Policy Optimization](https://mlsanity.com/paper/2412.18279/) (2024)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. However, the auto-regressive generation process makes LLMs prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. In this paper, by casting multi-step reasoning of LLMs as a heuristic search problem, we aim to alleviate the pathology by introducing Q*, a general, versatile and agile framework for guiding LLMs decoding process with deliberative planning. By learning a plug-and-play Q-value model as heuristic function for estimating expected future rewards, our Q* can effectively guide LLMs to select the most promising next reasoning step without fine-tuning LLMs for the current task, which avoids the significant computational overhead and potential risk of performance degeneration on other tasks. Extensive experiments on GSM8K, MATH and MBPP demonstrate the superiority of our method, contributing to improving the reasoning performance of existing open-source LLMs.