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

**Authors:** Chaojie Wang, Yanchen Deng, Zhiyi Lv, Shuicheng Yan, An Bo  
**arXiv:** [2406.14283](https://arxiv.org/abs/2406.14283)  
**Date:** 2024-06-20  
**Summary page:** https://www.summarizepaper.com/en/paper/2406.14283v1/

## Key points

- Authors address challenges faced by LLMs in multi-step reasoning tasks
- Auto-regressive generation process of LLMs leads to errors, hallucinations, and inconsistent statements during complex reasoning processes
- Proposed framework, Q*, guides decoding process through deliberative planning using a plug-and-play Q-value model as a heuristic function
- Q* avoids computational overhead and performance degradation on other tasks without fine-tuning for each specific task
- Extensive experiments on datasets like GSM8K, MATH, and MBPP validate the effectiveness of the method
- Q* offers a domain-agnostic solution for improving multi-step reasoning in LLMs by employing Q-value models as heuristic functions
- More computationally efficient compared to complete rollouts in Monte Carlo Tree Search (MCTS) by considering only a single step during deliberation
- Formalizes multi-step reasoning for LLMs as a Markov Decision Process (MDP) with state representing input prompt and reasoning steps taken so far, actions corresponding to subsequent reasoning steps
- Introduces approaches for estimating optimal Q-values of state-action pairs using offline reinforcement learning techniques and stronger LLM completions from rollouts

## Summary

In their paper titled "Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning," Chaojie Wang, Yanchen Deng, Zhiyi Lv, Shuicheng Yan, and An Bo address the challenges faced by  in performing multi-step reasoning tasks. While  have shown impressive capabilities in various natural language tasks, their auto-regressive generation process often leads to errors, hallucinations, and inconsistent statements during complex reasoning processes. To mitigate these issues, the authors propose , a general and agile framework that guides the decoding process of  through deliberative planning. The key innovation of  lies in its ability to leverage a plug-and-play Q-value model as a heuristic function to guide  in selecting the most promising next step without requiring fine-tuning for each specific task. This approach not only avoids significant computational overhead but also mitigates the risk of performance degradation on other tasks. The authors conducted extensive experiments on datasets such as GSM8K, MATH, and MBPP to validate the effectiveness of their method. Unlike traditional approaches that rely on domain knowledge to design heuristic functions,< kd >Q* </ kd > offers a domain-agnostic solution for improving multi-step reasoning in < kd >LLMs.</ kd > By employing Q-value models as heuristic functions,< kd >Q*</ kd > can efficiently tackle various tasks without prior fine-tuning of< kd >LLMs.</ kd >

Furthermore,< kd >Q* </ kd > considers only a single step during deliberation, making it more computationally efficient compared to complete rollouts in Monte Carlo Tree Search (MCTS). The authors formalize multi-step reasoning for < kd >LLMs</ kd > as a Markov Decision Process (MDP), where the state represents the input prompt and reasoning steps taken so far, while actions correspond to subsequent reasoning steps. They introduce several approaches for estimating optimal Q-values of state-action pairs using offline reinforcement learning techniques and stronger LLM completions from rollouts.