Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solver

## Abstract

Abstract This paper introduces rStar, a self-play mutual reasoning approach that significantly improves reasoning capabilities of small language models (SLMs) without fine-tuning or superior models. rStar decouples reasoning into a self-play mutual generation-discrimination process. First, a target SLM augments the Monte Carlo Tree Search (MCTS) with a rich set of human-like reasoning actions to construct higher quality reasoning trajectories. Next, another SLM, with capabilities similar to the target SLM, acts as a discriminator to verify each trajectory generated by the target SLM. The mutually agreed reasoning trajectories are considered mutual consistent , thus are more likely to be correct. Extensive experiments across five SLMs demonstrate rStar can effectively solve diverse reasoning problems, including GSM8K, GSM-Hard, MATH, SVAMP, and StrategyQA. Remarkably, rStar boosts GSM8K accuracy from 12.51% to 63.91% for LLaMA2-7B, from 36.46% to 81.88% for Mistral-7B, from 74.53% to 91.13% for LLaMA3-8B-Instruct. Code will be available at here .

## 1 Introduction

Despite their success, large language models (LLMs) face significant challenges in complex reasoning (Valmeekam et al., ; Weng et al., ). For example, state of the art models like Mistral-7B (Jiang et al., ) can only achieve 36.5% accuracy on the GSM8K dataset, even with techniques like Chain-of-Throught (CoT) (Wei et al., ). Although fine-tuning is shown to be an effective way to improve reasoning capability, most LLMs rely on fine-tuning data distilled or synthesized by *superior* models like GPT-4 (Wang et al., ; Gou et al., ). Meanwhile, the community has been actively working on a complimentary and yet more challenging approach: Reasoning improvements *without* a superior teacher LLM.

Figure: Figure 1: With 32 rounds of inference, rStar makes SLMs highly capable problem-solvers, matching or even surpassing the reasoning performance achieved after domain-specialized SFT.
Refer to caption: extracted/5786663/teaser.png

A promising paradigm to improve reasoning without superior models is to leverage the knowledge within LLMs themselves (Wang et al., ; Hao et al., ; Madaan et al., ). For example, RAP (Hao et al., ) adopts a self-exploration solution to iteratively improve LLM’s reasoning performance through self-rewarded feedback. Unfortunately, study suggests that this paradigm often suffers from two fundamental issues.

First, LLMs often struggle to effectively explore the solution space during reasoning. The self-exploration often traps in a solution space with low-quality reasoning steps even after many attempts. For example, our experiments reveal that after 32 rounds of self-exploration with RAP (Hao et al., ), only 24% of the trajectories generated by LLaMA2-7B on GSM8K are correct.
Second, even the self-exploration can find high quality reasoning steps, it is difficult for SLMs to tell which reasoning steps are of higher quality or determine which final answers are correct, thus it is hard to effectively guide the self-exploration. Our study shows that a naïve reward-based self-exploration guidance can lead to results no better than random guesses (see Appendix A.1).

A more troublesome fact is that the above two issues are more pronounced in the smaller version of LLMs, i.e., SLMs, due to their weaker capabilities. For instance, while GPT-4 can improve by self-refining its output (Madaan et al., ; Wu et al., ; Zhou et al., ), the approaches are less effective in SLMs and may even lead to worse performance (Forsman, ). This significantly hinders the adoption of neural language models.

This paper introduces Self-play muTuAl Reasoning (rStar), a novel approach that boosts SLMs’ reasoning capability during inference without fine-tuning or superior models. To address the aforementioned challenges, rStar decouples reasoning into a self-play mutual generation-discrimination process as illustrated in Fig. 2.
Specifically, rStar is unique in the following approaches. First, although relying on a conventional Monte Carlo Tree Search (MCTS) for SLMs to self-generate reasoning steps, rStar advocates *a richer set of reasoning actions* in the self-exploration. The new proposed actions simulate human reasoning behaviors given the current reasoning state, such as decomposing and searching for a specific reasoning step, proposing a new sub-question, or rephrasing the given question. This enables SLMs to generate high-quality candidate reasoning trajectories during self-exploration.
Second, to effectively guide the exploration among the generated reasoning trajectories, rStar augments the MCTS process with a new discrimination process called *mutual consistency*. In particular, rStar employs a second SLM with the similar capability, acting as a discriminator to provide unsupervised feedback on each candidate reasoning trajectory generated by MCTS. To improve the accuracy of the feedback, rStar hints the second SLM with sampled partial reasoning trajectories, asking it to complete the remaining reasoning steps. And rStar deems the mutually agreed reasoning trajectories of higher quality. Mutual consistency mirrors the common human practice in the absence of supervision, where agreement among peers (i.e., two SLMs) on derived answers suggests a higher likelihood of correctness.
As a result, mutual consistency offers more effective reasoning across diverse tasks than other approaches like self-consistency (Wang et al., ) and avoids the risk of overfitting when training a reward model (Chen et al., ; Wang et al., ).

Figure: Figure 2: Our self-play mutual reasoning is a generation-discrimination process: (1) a self-generator augments the target SLM to generate candidate reasoning trajectories using MCTS; (2) the discriminator uses another SLM to provide unsupervised feedback on each trajectory based on partial hints; (3) based on this feedback, the target SLM decides a final reasoning trajectory as the solution.
Refer to caption: extracted/5786663/overview.png

Extensive experiments across five SLMs and five diverse reasoning tasks demonstrate the effectiveness of rStar. With just 32 rounds of MCTS inference, rStar significantly enhances SLMs’ reasoning capabilities, matching or even surpassing the accuracy achieved after fine-tuning. For example, rStar boosts GSM8K accuracy from 12.51% to 63.91% for LLaMA2-7B, from 36.46% to 81.88% for Mistral, and from 47.23% to 85.52% for LLaMA3-8B. Furthermore, we conduct comprehensive experiments to verify rStar’s superiority over state-of-the-art baselines, including single-round inference techniques like few-shot CoT, multi-round prompting approaches such as self-consistency, and self-improvement techniques such as RAP, ToT, self-evaluation and self-verification.

## 2 Related Work

Prompting Language Models to Reason.
Prompting-based methods, such as Chain-of-Thought (Wei et al., ), focus on designing instructions and pipelines to enhance LLMs’ reasoning performance during inference. Recent advances include planning (Hao et al., ; Ding et al., ), problem decomposition (Zhou et al., ; Khot et al., ; Hao et al., ), abstraction (Zheng et al., ), programming (Chen et al., ; Zhou et al., ).
These methods aim to improve single-round inference performance and are orthogonal to ours.

LLM Self-improvement. Recently, research on the self-improvement of LLMs has rapidly increased.
Fine-tuning based methods (Chen et al., ; ) leverage the capabilities of a well-pretrained LLM to synthesize data and progressively enhance its performance. Advanced prompting techniques, such as self-verification (Gero et al., ; Zhou et al., ), and RAP (Hao et al., ), improve performance through iterative self-exploring based on self-diagnosed feedback at inference time.
However, as illustrated in previous section, the achieved performance often depend on the LLM’s inherent capabilities, and for SLMs, their weaker instruction-following ability and unreliable self-rewarding can mislead self-improvement.

Sampling Reasoning Paths. Recent works (Brown et al., ; Li et al., ; Snell et al., ) on mathematical reasoning have shown that sampling diverse reasoning paths can significantly enhance performance compared to greedy one-time decoding. Self-Consistency (Wang et al., ) sample a complete CoT path each time. Tree-search approaches (Yao et al., ; Hao et al., ; Zhang et al., ), like MCTS, further improve the performance by breaking down tasks and sampling simpler, individual intermediate reasoning steps. However, most approaches have limited action spaces. For example, RAP (Hao et al., ) decomposes only subproblems, while AlphaMath (Chen et al., ) searches only for one CoT step, limiting effectiveness in generating better trajectories.

Answer Verification. To select correct reasoning trajectories, majority voting (Wang et al., ) is a widely-used approach. To improve accuracy, some works train value or rewards model for verification (Wang et al., ; Chen et al., ), but these require additional annotations and have risks in overfitting to specific tasks. Self-verification (Weng et al., ) leverages LLM capabilities for backward self-verification. Nevertheless, its effectiveness hinges on its inherent ability to reason effectively. Recent studies have shown that LLM struggles to evaluate itself and rectify its initial responses without any external feedbacks (Huang et al., ; Feng et al., ).

## 3 Methodology

### 3.1 Overview

Problem Formulation. To solve a reasoning problem by SLMs, we formulate it as a multi-step reasoning generation task, which breaks
the problem into simpler sub-tasks. This is more effective than traditional CoT-based reasoning (Wei et al., ; Wang et al., ), as it is much easier for SLMs to correctly generate one step than complete reasoning steps in a single inference. We leverage the Monte-Carlo Tree Search (MCTS) algorithm (Kocsis & Szepesvári, ) to augment the target SLM for self-generating multi-step reasoning solutions.

Formally, for a given problem $x$ and a target SLM $M$, the MCTS augments $M$ to incrementally build a search tree $\mathcal{T}$. As illustrated in Fig. 3, the root node represents the question $x$, an edge represents an action $a$, each child node is an intermediate step $s$ generated by $M$ under the corresponding action. A path from the root node to a leaf node (denoted as $s_{d}$, also called a terminal node) constitutes a candidate solution trajectory $\mathbf{t}=x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{d}$. From the search tree $\mathcal{T}$, we can extract a set of solution trajectories $\mathbb{T}=\{\mathbf{t}^{1},\mathbf{t}^{2},...,\mathbf{t}^{n}\}(n\geq 1)$. Our goal is to find the trajectories that can achieve the correct answer for the given question.

Challenges in SLM Self-Improvement. MCTS allows an SLM to explore and evaluate multiple potential solutions. Ideally, by balancing exploration of new possibilities with the exploitation of high-reward actions, the SLM can gradually refine its reasoning steps to generate a final correct reasoning trajectory. However, due to the limited capabilities in SLMs, traditional MCTS yields minimal improvement. First, the vast solution space makes it challenging for SLMs to generate effective solutions. Existing MCTS-based methods (Hao et al., ; Kang et al., ) that use single actions limit diversity and struggle to generalize across tasks. Approaches like self-consistency (Wang et al., ) use random sampling ensure diversity, SLMs often produce poor-quality solutions, requiring many attempts to find a correct solution, thereby increasing inference costs.

Second, it’s challenging to accurately reward each action. Without ground truth labels, it’s difficult to verify the correctness for each intermediate step $s_{i}$ and the final answer in $s_{d}$. Majority voting in self-consistency requires most traces to be correct, which is often not the case for SLMs. Methods like RAP (Hao et al., ) use self-rewarding, but our study shows SLMs perform near-random self-rewarding (Appendix A.1). Training a reward model, as in M^∗ (Kang et al., ), can address this challenge but faces difficulties in collecting training data and generalizing across various tasks.

Overview.
To address these challenges, this section introduces our methodology, rStar, which decomposes reasoning into solution generation and mutual verification in Fig. 2. To tackle the first challenge, we introduce a richer set of human-like reasoning actions that allows for thorough space exploration across diverse reasoning tasks. To address the second challenge, we design an SLM-tailored reward function to evaluate intermediate steps, avoiding reliance on their often unreliable self-evaluations. Moreover, we use another SLM as a discriminator to augment the MCTS process, mutually verifying the correctness of each trajectory with the generator SLM.

### 3.2 Self-generating Reasoning Trajectory with MCTS Rollout

Figure: Figure 3: An example to illustrate the process of self-generator. Highlighted nodes from top to bottom constitute a complete reasoning trace. Given a question, MCTS augments the target SLM to explore a rich, human-like reasoning action space and generate the next steps based on the current state.
Refer to caption: x1.png

A Rich Set of Human-like Reasoning Actions. At the core of MCTS generation lies the action space, which defines the scope of tree exploration. Most MCTS-based methods use a single action type to build the tree. For instance, in RAP, the action is to propose the next sub-question, whereas in AlphaMath (Chen et al., ) and MindStar (Kang et al., ), the action is to generate the next reasoning step.
However, relying on a single action type can easily lead to ineffective space exploration.

To address this, we revisit how humans approach reasoning.
Different people solve problems using diverse actions: some break into sub-questions, others solve it directly, and some might rephrase the problem to focus on key conditions. Moreover, people adjust their approach based on current states, choosing different actions as needed. Inspired by this human reasoning process, we introduce a richer set of 5 actions to maximize the SLM’s potential for correctly solving complex reasoning problems.

$\diamond$ A1: Propose an one-step thought. This action prompts the LLM to generate the next one-step thought for a given question, by considering the existing reasoning steps. Unlike the CoT, which generates complete thoughts, this approach simplifies the reasoning process and allows the LLM to perform better decision making (Yao et al., ; Besta et al., ).

$\diamond$ A2: Propose the remaining thought steps. Instead of generating only one step thought per state, this action aligns with standard CoT, enabling “fast thinking” to solve simple question in fewer steps. Given the already generated reasoning steps, it prompts the LLM to directly produce the remaining steps until reaching the final answer.

$\diamond$ A3: Propose next sub-question along with its answer. This action is inspired by least-to-most prompting (Zhou et al., ), which breaks down a complex problem into a series of simpler sub-questions and solves them sequentially. Following RAP’s implementation, we prompt the LLM to ask and then answer the next sub-question.

$\diamond$ A4: Answer the sub-question again. Considering that a sub-question might not be answered correctly by A3, we propose this action to re-answer it. To improve accuracy, this action prompts the LLM to use few-shot CoT. Note that the original answer generated by A3 did not use a CoT-like prompt but instead followed the least-to-most problem decomposition prompt (Zhou et al., ).

$\diamond$ A5: Rephrase the question/sub-question. When analyzing incorrect cases, we found that many of them are due the LLM misunderstanding the question. For example, it might miss a specific condition provided in the question. Therefore, we propose a new action to rephrase the question more simply. Specifically, we prompt the LLM to clearly list all conditions given in the problem statement.

**Table 1: Ablation study on the effectiveness of our rich action space: we evaluate LLaMA3-8B on 200 sampled GSM8K questions.**
| Action Space | Accuracy |
| --- | --- |
| $A_{3}$ (i.e., RAP) | 70.5 |
| $A_{3}$ + $A_{5}$ | 72.5 |
| $A_{3}$ +$A_{4}$ + $A_{5}$ | 73.5 |
| $A_{2}$ + $A_{3}$+$A_{4}$ + $A_{5}$ | 74.0 |
| All ( $A_{1}$ + $A_{2}$ + $A_{3}$+$A_{4}$ + $A_{5}$) | 75.0 |

The above 5 actions define a highly diverse action space $\{A_{1},A_{2},A_{3},A_{4},A_{5}\}$.
At each step $i$, MCTS selects an action $a_{i}$ from this space. We then use this action $a_{i}$ to prompt the LLM to generate the next reasoning step $s_{i}$, based on the current state, which is the previous generated trajectory $x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{i-1}$. Note that certain actions require orders. For example, A4 can only happen after A3, and A5 can only happen after the root question. As shown in Table 1, each action plays a crucial role in improving the final reasoning accuracy.

Reward Function. Another critical component in MCTS is the reward function, which evaluates the value of each action and directs the tree expansion.
We design a simple yet effective reward function for SLMs. First, we exclude self-rewarding techniques for any intermediate nodes due to the limited capabilities of SLMs. Second, to ensure generalization across different reasoning tasks, we avoid introducing external supervision (e.g., tools or trained value models). Our approach draws inspiration from AlphaGo (Silver et al., ), where we score each intermediate node based on its contribution to the final correct answer. Consequently, actions that frequently lead to correct answers receive higher rewards, making them more likely to be selected in future MCTS tree expansions.

We define $Q(s,a)$ as the reward value for node $s$ generated under action $a$.
Initially, all unexplored nodes are assigned $Q(s_{i},a_{i})=0$, leading to random tree expansions. Upon reaching the first terminal node $n_{d}$, we compute a reward score $Q(s_{d},a_{d})$ based on whether it reaches the correct answer.
This score is then back-propagated to each intermediate node along the trajectory $\mathbf{t}=x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{d}$. Specifically, for each $s_{i}$ (for $i=1,2,...,d-1$), its $Q$ value is updated as follows: $Q(s_{i},a_{i})=Q(s_{i},a_{i})+Q(s_{d},a_{d})$. To compute the $Q(s_{d},a_{d})$ for the terminal node, we use the likelihood (confidence) of self-consistency majority voting as the reward value.

Figure: Figure 4: The prompt example for mutual reasoning consistency.
Refer to caption: extracted/5786663/discriminator.png

Solution Generation with MCTS Rollout. We now describe how our MCTS generates candidate reasoning trajectories. Starting from the initial root node $s_{0}$, we perform multiple searches consisting of selection, expansion, simulations and back-propagation. Specifically, the simulation is performed using the default rollout policy, and to achieve more accurate reward estimation, we perform multiple rollouts. To balance the exploration and exploitation, we use the well-known Upper Confidence Bounds applied to Trees (UCT) (Kocsis & Szepesvári, ) to select each node. This selection process is mathematically represented as:

$$ $\text{UCT}(s,a)=\frac{Q(s,a)}{N(s,a)}+c\sqrt{\frac{\ln N_{parent}(s)}{N(s,a)}}.$ $$

where $N(s,a)$ is the number of times node $s$ has been visited in previous iterations, and $N_{parent}(s)$ represents the visiting count of the parent node of $s$. $Q(s,a)$ is the estimated reward value and will be updated through back-propagation. $c$ is a constant that balances exploitation and exploration.

Once the search reaches a terminal node, either a terminal state or a predetermined maximum tree depth $d$, we obtain a trajectory from the root to terminal node. We collect all trajectories from the rollout iterations as candidate solutions. The next section explains how we verify each of them.

### 3.3 Reasoning Trajectory Selection with Mutual Consistency

In traditional MCTS, typically only one trajectory is selected as the final solution based on a specific metric, such as choosing the path with the highest reward from the rollout iterations. Unfortunately, after trying various existing methods, we found it challenging to define a single metric that reliably selects the trajectory containing the correct answer.
Therefore, we collect all trajectories and propose mutual reasoning consistency for answer selection.

Mutual Reasoning Consistency by Discriminator SLM2. As shown in Fig. 2, in addition to the target SLM $M$, we introduce another SLM $\hat{M}$ to serve as a discriminator, providing external unsupervised feedback for each candidate trajectory.
Specifically, for $\mathbf{t}=x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{d}$, we mask the reasoning steps starting from a randomly sampled step $i$ ($i<d$). We then provide the earlier reasoning trajectory $\mathbf{t}=x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{i-1}$ as a prompt to $\hat{M}$ to complete the remaining steps for the question. Due to the provision of the earlier $i-1$ reasoning steps as a hint, we reduce the difficulty, thereby increasing the likelihood that SLM $\hat{M}$ can provide the correct answer.
As shown in Fig. 4, we compare whether the answer completed by $\hat{M}$ matches the original trajectory $\mathbf{t}$. If they are consistent, we consider $t$ as an validate trajectory for final selection.

We provide an intuitive explanation to illustrate the rational behind our approach. Consider students solving a problem without a teacher’s feedback. A student (SLM1) unsure of their solution might ask a peer (SLM2) to review their reasoning. If the peer, given the same initial steps, arrives at the same answer, the student gains confidence in their solution. This peer verification process reflects the mutual reasoning consistency we aim to achieve.

Final Trajectory Selection by SLM1. After applying mutual reasoning consistency to all candidate trajectories, we return to the target SLM $M$
to select the final trajectory from the validated ones. We compute each trajectory’s final score by multiplying its reward with the terminal node’s confidence score achieved from rollouts. The trajectory with the highest final score is chosen as the solution.

**Table 2: rStar greatly improves reasoning accuracy across various SLMs and tasks. rStar (generator@maj): uses majority voting for answer verification to show the MCTS generator’s effectiveness.**
| Method | LLaMA2-7B | Mistral-7B | LLaMA3-8B | LLaMA3-8B-Instruct | Phi3-mini-4k |
| --- | --- | --- | --- | --- | --- |
| GSM8K |  |  |  |  |  |
| Zero-shot CoT | 1.44 | 17.89 | 22.66 | 68.38 | 20.17 |
| Few-shot CoT | 12.51 | 36.46 | 47.23 | 74.53 | 83.45 |
| SC@maj8 | 15.31 | 42.91 | 54.21 | 78.39 | 86.35 |
| SC@maj64 | 20.77 | 52.84 | 64.37 | 83.24 | 88.02 |
| SC@maj128 | 23.05 | 57.25 | 67.55 | 84.69 | 88.68 |
| ToT | 12.96 | 38.89 | 36.01 | 69.07 | 79.68 |
| RAP | 24.34 | 56.25 | 57.99 | 80.59 | 81.88 |
| rStar (generator @maj) | 27.22 | 64.59 | 74.38 | 88.70 | 90.44 |
| rStar | 63.91 | 81.88 | 85.52 | 91.13 | 90.67 |
| GSM-Hard |  |  |  |  |  |
| Zero-shot CoT | 0.83 | 5.16 | 6.44 | 14.94 | 33.73 |
| Few-shot CoT | 3.71 | 13.57 | 13.80 | 25.63 | 40.63 |
| SC@maj8 | 4.39 | 17.36 | 18.20 | 28.51 | 42.00 |
| SC@maj64 | 6.52 | 22.59 | 23.73 | 30.33 | 44.80 |
| SC@maj128 | 6.89 | 25.01 | 25.47 | 31.16 | 45.56 |
| ToT | 2.35 | 11.47 | 10.61 | 19.64 | 32.68 |
| RAP | 7.28 | 22.52 | 18.95 | 29.64 | 40.94 |
| rStar (generator @maj) | 8.64 | 29.26 | 26.76 | 33.35 | 46.55 |
| rStar | 18.57 | 37.91 | 32.97 | 37.53 | 46.55 |
| SVAMP |  |  |  |  |  |
| Zero-shot CoT | 8.90 | 26.10 | 40.20 | 70.90 | 84.70 |
| Few-shot CoT | 48.10 | 72.80 | 76.90 | 89.20 | 92.80 |
| SC@maj8 | 49.90 | 74.60 | 79.10 | 89.20 | 93.50 |
| SC@maj64 | 54.10 | 76.70 | 80.70 | 90.50 | 93.30 |
| SC@maj128 | 54.50 | 76.60 | 80.80 | 90.60 | 93.70 |
| ToT | 33.40 | 56.30 | 62.20 | 79.80 | 84.90 |
| RAP | 41.00 | 71.80 | 73.10 | 85.70 | 91.50 |
| rStar (generator @maj) | 60.30 | 83.10 | 86.20 | 91.89 | 93.80 |
| rStar | 74.90 | 86.40 | 90.00 | 94.29 | 94.10 |
| StrategyQA |  |  |  |  |  |
| Zero-shot CoT | 52.67 | 57.20 | 41.48 | 57.21 | 54.68 |
| Few-shot CoT | 58.82 | 65.65 | 64.05 | 68.41 | 63.61 |
| SC@maj8 | 59.10 | 65.50 | 63.76 | 68.26 | 64.34 |
| SC@maj64 | 58.51 | 63.61 | 63.46 | 67.39 | 62.74 |
| SC@maj128 | 58.37 | 62.01 | 63.31 | 66.67 | 59.53 |
| ToT | 45.27 | 55.75 | 57.64 | 60.41 | 40.47 |
| RAP | 59.68 | 64.48 | 63.32 | 68.71 | 60.26 |
| rStar (generator @maj) | 61.57 | 69.43 | 65.50 | 71.47 | 65.50 |
| rStar | 67.25 | 70.31 | 67.69 | 71.57 | 67.25 |

## 4 Experiments

### 4.1 Setup

Models and Datasets. rStar is a general approach applicable to various LLMs and reasoning tasks. We evaluate 5 SLMs: Phi3-mini (3.8B) (Abdin et al., ), LLaMA2-7B, Mistral-7B (Jiang et al., ), LLaMA3-8B, and LLaMA3-8B-Instruct (Meta, ). We test across 5 reasoning tasks, including 4 mathematical tasks (GSM8K (Cobbe et al., ), GSM-Hard (Gao et al., ), MATH (Hendrycks et al., ), SVAMP (Patel et al., )) and one commonsense reasoning task (StrategyQA (Geva et al., )).

Implementation Details. In the trajectory self-generation stage, we augment each target SLM with our MCTS, performing 32 rollouts. Except for MATH, where we set the depth $d$ to 8, all other tasks have a $d$=5. Actions $A_{1}$ and $A_{3}$ have a maximum of 5 nodes per depth, while the other actions have a default node count of 1. In the trajectory discrimination stage, we use Phi3-mini-4k as the discriminator, which has only 3.8B parameters, for effective inference. Moreover, the discriminator performs inference in a parallelized manner, making the verification process highly efficient.
Notably, when Phi3 is the target SLM, it performs self-discrimination. For a given trajectory, we randomly split it between 20% and 80% of its steps, providing the first half of the steps as input to the discriminator SLM, which then completes the remaining steps.
Detailed prompts are available in appendix A.3.

### 4.2 Main Results

Baselines. We compare rStar against three strong baseline types: (i) single-round CoT prompting, including zero-shot CoT (Kojima et al., ) and few-shot CoT (Wei et al., ); (ii) multi-round CoT prompting using the widely adopted self-consistency (SC) method (Wang et al., ). We sample answers 8, 64, and 128 times, employing majority voting for answer selection; and (iii) multi-round self-improving approaches. For this, we select ToT (Yao et al., ) and RAP (Hao et al., ) as baselines, using BFS and MCTS for tree search, respectively. Note that the action in ToT corresponds to our action $A_{1}$, while RAP corresponds to our action $A_{3}$. For the answer selection, we follow their original implementations.

Results on diverse reasoning benchmarks. We start by evaluating the effectiveness of rStar on general reasoning benchmarks. Table 2 compares its accuracy with state-of-the-art baselines on diverse SLMs and reasoning datasets. To demonstrate the effectiveness of our generator, we also provide the accuracy of rStar (gen. @maj), which do not apply our discriminator and use majority voting for answer verification. We highlight three key observations:
(1) SLMs empowered with rStar demonstrate highly capable problem-solving abilities. For example, LLaMA2-7B originally had an accuracy of only 12.51% on GSM8K using few-shot CoT. However, with improvements from rStar, its accuracy increased to 63.91%, nearly matching the accuracy achieved with fine-tuning as shown in Fig. 1. Similarly, Mistral with rStar can even outperform fine-tuned MetaMath by +4.18%. This improvement shows that SLMs already have strong reasoning capabilities but need guidance to generate and select the correct solutions.
(2)
rStar consistently improves the reasoning accuracy of various evaluated SLMs across different tasks to a state-of-the-art level. In contrast, none of the baseline approaches consistently perform well across all four benchmarks. For example, while SC excels in three mathematical tasks, it is less effective on the logical reasoning task of StrategyQA. Specifically, SC with more sampling can even lower the score on StrategyQA. RAP performs better than SC on StrategyQA but falls short compared to SC on most mathematical reasoning tasks.
(3) Even without our proposed discriminator for reasoning trajectory verification, our MCTS generator demonstrates greater effectiveness in improving reasoning accuracy for SLMs compared to existing multi-round inference baselines. For example, rStar (generator @maj) achieves up to 2.88%-16.39% higher accuracy than RAP, 10.60%- 38.37% higher accuracy than ToT, and 1.69% - 7.34% higher accuracy than SC on the GSM8K dataset.

**Table 3: Reasoning performance comparison on the challenging MATH-500 dataset. Due to the extensive LaTeX syntax in the dataset, which is challenging for pre-trained LLMs in instruction following, we evaluate only on LLaMA3-8B-instruct and Phi3-Mini-4k-Instruct.**
| Method | LLaMA3-8b-Instruct | Phi3-mini-4k |
| --- | --- | --- |
| Zeroshot CoT | 5.80 | 3.60 |
| Fewshot CoT | 17.80 | 32.20 |
| SC@maj8 | 30.00 | 40.40 |
| SC@maj64 | 33.00 | 45.20 |
| SC@maj128 | 33.80 | 45.60 |
| ToT | 13.60 | 18.20 |
| RAP | 18.80 | 27.80 |
| rStar (generator @maj) | 38.30 | 48.40 |
| rStar | 42.94 | 48.60 |

Figure: Figure 5: Performance comparison on the GSM8K dataset under different number of rollouts. rStar can significantly improve reasoning accuracy with just 2 rollouts.
Refer to caption: extracted/5786663/rollout.png

Results on challenging mathematical dataset. We also evaluate the effectiveness of rStar on more challenging mathematical datasets. In particular, we select the GSM-Hard and MATH datasets. Following (Wang et al., ; Lightman et al., ), we use MATH-500, a subset of representative problems from the MATH dataset, to speedup the evaluation. As shown in Table 2 and Table 3, rStar
is capable of significantly improve the reasoning accuracy of SLMs on these challenging mathematical datasets.
Remarkably, when compared to SOTA baselines, we observe a significant improvements of up to +12.9% and +9.14% on GSM-Hard and MATH-500, respectively.

### 4.3 Ablation Study

**Table 4: Ablation study on the effectiveness of our MCTS generator. Ours+self-eval: we apply self-evaluation to prompt model for self-rewarding each intermediate action in our generator.**
| Generator | LLaMA3-8B | LLaMA3-8B-Instruct |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GSM8K | StrategyQA | GSM8K | StrategyQA |  |  |  |  |  |
| Answer verification | Answer verification | Answer verification | Answer verification |  |  |  |  |  |
| Maj | Ours | Maj | Ours | Maj | Ours | Maj | Ours |  |
| RAP | 56.56 | 57.31 | 62.30 | 64.63 | 81.35 | 84.69 | 69.43 | 70.60 |
| SC (@128) | 67.55 | 85.06 | 63.31 | 65.65 | 84.69 | 89.99 | 66.67 | 68.56 |
| Ours+Self-eval | 70.28 | 82.18 | 65.07 | 66.22 | 88.07 | 89.92 | 69.28 | 69.43 |
| Ours | 74.38 | 85.52 | 65.50 | 67.69 | 88.70 | 91.13 | 71.47 | 71.57 |

**Table 5: Ablation study on discriminator effectiveness. We evaluate accuracy on GSM8K. Left: Our discriminator consistently outperforms others in verifying solution trajectories generated by different generators. Right: The ablation study on the choice of discriminator model.**
| Discriminator | LLaMA3-8B | LLaMA3-8B-Instruct |  |  |
| --- | --- | --- | --- | --- |
| Generator | Generator |  |  |  |
| SC | Ours | SC | Ours |  |
| Maj | 67.55 | 74.38 | 84.69 | 88.70 |
| Self-verification | 74.00 | 75.52 | 83.02 | 86.63 |
| Ours | 85.06 | 85.52 | 89.99 | 91.13 |

Effectiveness under different rollouts. rStar uses a rollout policy for MCTS tree expansion. More rollouts generate more candidate solution trajectories but increase inference cost. In Fig. 5, we compare the accuracy of SC, RAP, and our rStar across different rollouts on GSM8K. For SC, we sample solutions based on each number of rollouts and use majority voting to select the answer. We highlight two key observations: (1)
Even with just 2 rollouts, rStar significantly improves reasoning accuracy for SLMs, demonstrating its effectiveness; (2) Both rStar and SC benefit from more rollouts, whereas RAP tends to saturate and even decline after 4 rollouts on LLaMA3-8B-Instruct. One reason is that the single-type action space in RAP limits the effective MCTS exploration.

The effectiveness of MCTS generator. We compare our MCTS generator with three baselines: (i) the MCTS generator used in RAP; (ii) SC with 128 randomly sampled solutions; and (iii) our generator with Self-evaluation, a popular technique that self-evaluates the reward score for each action. Baseline (iii) specifically evaluates the effectiveness of our reward function.
To isolate the impact of answer verification methods, each generator is evaluated under both majority voting and our discriminator for trajectory selection. As shown in Table 4, our generator consistently outperforms the baseline generators across different answer verification methods. More, we demonstrate the effectiveness of our SLM-tailored reward function, as self-evaluation reduces our generator’s accuracy.

The effectiveness of discriminator. We setup two experiments for evaluation. First, we compare our discrimination approach with two baselines: the majority voting and self-verification (Weng et al., ). Specifically, we follow the key idea in  Weng et al. () to prompt the SLM (i.e., generator SLM) to self-verify the correctness of each trajectory. To demonstrate the generalization ability of our discriminator, we used candidate solutions from different generators for evaluation.
As shown in Table 5 (Left), our discriminator significantly improves reasoning accuracy when performing answer verification on trajectories generated by different generators. Similar to the previous self-evaluation experiment, self-verification on SLMs is ineffective.

Second, we study the impact of discriminator model selection. Our current discriminator models are all Phi3-Mini-Instruct. We tested various LLMs, both stronger and weaker, as discriminators for LLaMA3-8B-Instruct. As shown in Table 5 (Right), the choice of discriminator model generally does not affect the effectiveness of our mutual reasoning consistency for answer verification. Notably, using the powerful GPT-4 as the discriminator only slightly improves performance (91.13% to 92.57%), demonstrating that mutual reasoning consistency can effectively verify answers using SLMs.

## 5 Conclusion

In this work, we present rStar, a generator-discriminator self-play approach that significantly grow the reasoning capabilities for SLMs at the inference time. Our approach reveals that SLMs, such as LLaMA2-7B, already exhibit strong reasoning capabilities prior to domain specialized supervised fine-tuning. rStar achieves state-of-the-art performance across five SLMs and five diverse reasoning tasks, substantially outperforming existing multi-round prompting and self-improvement approaches. Furthermore, we conduct extensive ablation studies and analysis, contributing to the development of more advanced SLM self-improved reasoning.

## Appendix A Appendix

### A.1 Experiments to evaluate the self-rewarding in SLMs

**Table 6: Analysis on the effectiveness of SLMs’ self-rewarding. The original $r_{1}$ is a self-evaluation of the helpfulness of the new proposed subquestion, while $r_{2}$ measures the confidence in answering the subquestion through self-consistency majority voting. Results show that replacing the self-evaluated $r_{1}$ to random values does not significantly impact the final reasoning performance.**
| Method | LLaMA2-7B | Mistral |
| --- | --- | --- |
| GSM8K |  |  |
| RAP | 24.34 | 56.25 |
| RAP + random $r_{1}$ | 22.90 | 55.50 |
| RAP + random $r_{2}$ | 22.67 | 49.66 |
| Multiarith |  |  |
| RAP | 57.22 | 91.11 |
| RAP + random $r_{1}$ | 52.78 | 90.56 |
| RAP + random $r_{2}$ | 47.22 | 81.11 |

Ablation study on self-rewarding in RAP. RAP rewards both intermediate and terminal nodes. For each node generated by its action, it combines two scores, $r_{1}$ and $r_{2}$, to determine the final reward score. Formally, $r=r_{1}\times r_{2}$. $r_{1}$ is a self-evaluation score that evaluates the LLM’s own estimation of the helpfulness of the current node. Specifically, it prompts the LLM with the question "Is the new question useful?". $r_{2}$ is the confidence of correctly answering the proposed new question, measured by self-consistency majority voting.

To evaluate the effectiveness of self-rewarding in RAP, we replace $r_{1}$ and $r_{2}$ with random values sampled from (0,1)and re-run RAP on LLaMA2-7B and Mistral-7B. We select a challenging dataset, GSM8K and an easy mathematical reasoning dataset, Multiarith (Roy & Roth, ), for evaluation.

Table 6 compares the results with original RAP. We can see that replacing $r_{1}$ with random values has minimal impact on RAP’s performance across different SLMs and datasets. However, replacing $r_{2}$ with random values result in a noticeable drop in accuracy on Mistral and Multiarith. This indicates that self-evaluation $r_{1}$ has minimal effect, suggesting that LLaMA2-7B and Mistral are essentially performing near-random self-evaluations.

### A.2 Discussions

Discussions on the importance of generator and discriminator. In our experiments, we found that on certain SLMs, the discriminator yields more significant improvement than the generator. For instance, on LLaMA2-7B, rStar (generator @maj) can improves accuracy by +4.17% on GSM8K, while our discriminator can further boosts accuracy by +36.69%. However, both the generator and discriminator are crucial to final performance. The generator must effectively produce the correct solution first, and the discriminator then provide reasonable feedback to select the correct solution.

The importance of the generator and discriminator varies based on the SLM’s solution generation effectiveness. For LLaMA2-7B, the proportion of correct solution trajectories is low, leading to a lower majority voting score. In this case, the discriminator is crucial for identifying the correct solution, significantly boosting accuracy. Conversely, for stronger models like LLaMA3-8B-instruct, our generator produces a higher proportion of correct solutions. Therefore, improving the generator results in greater accuracy improvements.

**Table 7: Inference costs of rStar on GSM8K. We show the average number of inferences and generated tokens required to solve a question.**
|  | LLaMA2-7B | Mistral |
| --- | --- | --- |
| Avg. calls | 166.81 | 148.90 |
| Avg. generated tokens | 367.1k | 348.6k |

Inference cost. rStar grows SLMs reasoning capabilities at inference time. The primary inference cost arises from our MCTS self-generator. Table 7 shows the average number of inferences and tokens generated for solving a GSM8K question after 32 rollouts.
On LLaMA2-7B and Mistral, this averages 166 and 148 model calls to solve a question, respectively. Currently, completing the 32 rollouts for the entire GSM8K test set takes about 4.5 days on a single A100 GPU per model. These costs can be significantly reduced by distributing tasks across multiple GPUs or batching model calls within each rollout.

### A.3 Prompt examples in MTCS

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 3
presentation: 3
questions: Answering the questions 1, 2 above would help.

Edit - post rebuttal: questions 1 and 2 were answered by the authors to my satisfaction.
soundness: 2
strengths: The experimental results point to much improved performance of the model under reasoning.
summary: The paper puts forward an approach to improve reasoning capabilities of LLMs. The approach is based on MCTS with a discriminator model selecting the most promising answers. Experiments appear to demonstrate superior reasoning capabilities of the approach compared to fine-tuning and other approaches.

Post-rebuttal: My expertise in the area is limited to the one of an interested observer. I am reassured by the responses of the authors to my questions and having read through the related links and explanations, I am happy to revise my score up and recommend acceptance. I would encourage the authors to add explanations to points such as the ones I have highlighted to increase the reach of the paper to people outside the LLM area.
weaknesses: This is not my area, hence low confidence, however as someone outside the LLM area I struggled to see the arguments put forward in the paper. I recommend the author to put more emphasis into making the key parts of the technical material more accessible by providing more explanations. Here are the key problems I had.

1 I did not understand how the MCTS approach works here both in terms of generation of the next steps. What simulation is performed, how this is tuned and where the MCTS itself results from (is it the model itself). Equally I found no explanation as to why this would/should lead to increased performance in the step generations.

2 I did not understand why a discriminator would have better performance than the original model and why it is the case that these capabilities cannot or should not be employed directly by the reasoning model. 

I think that if I had more explanations on the points above I would have been to understand the technical contribution more.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Reasoning capabilities are often studied in terms of generalizability How would you study generalization capabilities of your method? Could you transfer between tasks/benachmarks?
soundness: 2
strengths: - The paper is relatively well written making it easy to follow..
-  the methodology is clearly explained and differences as well as similarities to competing methods are made explicit.
- In the experimental evaluation it is clearly shown that the proposed method out-competes state-of-the-art approaches. This is substantiated by a couple of informative ablation studies.
summary: The paper describes a method to improve "reasoning capabilities" of small language models. This is done by generating trees of prompt using MCTS and by using a second small language model that "critiques" MCTS rollouts. After introducing the method the paper than show in its experimental section that on a suite of benchmarks the new method, dubbed rStar, outperforms existing methods.
weaknesses: The paper claims to improve reasoning capabilities of small language models. However, by training/augmenting a SML with MCTS on a specific dataset we now end up with a model that is informed by the statistics of the dataset. In the end there is no reasoning happening but the proposed method allows the SML to better exploit statistical patterns in the data-query pairs that it was trained on.

In the end the proposed methods does not allow SMLs to reason but is a method to perform prompt-engineering in an automated fashion using the statistics of the benchmark in question.


One of the problems I have is the anthropomorphism present in the paper. Specifically, with using "rich set of human like reasoning actions" already in the abstract and continuing it throughout the paper.


While I do not see how the paper enables SMLs to reason better, I can see that the introduces techniques have clear experimental advantages over competing methods. This leads me to tend towards arguing towards accepting the paper ever so slightly. .

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1) The authors introduce a set of five human-like reasoning actions as the action types for MCTS. This design requires manual selection and experimental validation, which may not be optimal. Could the authors provide any experiments or analysis comparing their manually selected actions to other potential action sets? Did the authors consider automating the action type design process?


2) A very interesting aspect of OpenAI's o1 model is its self-reflective behavior. Did the authors consider integrating self-reflection as an action type in their framework? What potential benefits or challenges do the authors expect with such an addition?


3) The authors mention that temporal order constraints exist for different action types. Could the authors provide pseudocode or a more detailed explanation of how the temporal order constraints are implemented in their MCTS algorithm?


4) In Section A.3, the authors mention the high token cost associated with this method. For instance, the average number of generated tokens per question on GSM8k is 367.1k, which could limit the method's practical applicability. Have the authors considered optimization strategies to address this issue? While distributed inference can reduce processing time, it does not reduce the overall computational cost.


5) The authors emphasize that this method is designed for SLMs. Have the authors conducted experiments or analysis comparing rStar's performance on SLMs versus on LLMs? What’s the expectation of the method's effectiveness to change with model size?
soundness: 3
strengths: The idea of introducing human-like reasoning actions and using mutual consistency between SLMs to verify the results during inference time is intriguing. The writing is well-structured and clear. Empirical results with details are given.
summary: The paper introduces rStar, a self-play mutual reasoning approach designed to improve the reasoning capabilities of small language models (SLMs). This method enhances SLMs with prompting engineering. The key mechanism involves a generation-discrimination process where the target SLM creates reasoning trajectories using Monte Carlo Tree Search (MCTS) enriched with human-like reasoning actions. Another SLM, with similar capabilities, acts as a discriminator to verify the generated trajectories, ensuring they are mutually consistent, which increases their likelihood of correctness. Experiments show that rStar effectively boosts performance on challenging reasoning benchmarks.
weaknesses: There are still some design and implementation details related to manual action selection, self-reflection, token cost, scalability to larger models that need further clarification.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: - When does performance improvement drop off with increased roll outs? The paper stops at 32, but performance seems to still be improving linearly.
- How does this approach compare to other MCTS methods recently proposed?
soundness: 4
strengths: The paper's primary originality lies in its novel two-phase approach to improving small language model reasoning. Rather than relying on conventional methods, it creatively combines an enriched Monte Carlo Tree Search with a mutual consistency verification phase using a second SLM. Particularly innovative is the expansion of the MCTS action space to include human-like reasoning operations such as problem decomposition, question rephrasing, and stepwise thinking. The proposed "mutual consistency" verification approach, while used before, is an interesting application that seems very effective.

The authors conduct a comprehensive evauation across a diverse set of benchmarks and models. Additionally, they perform convincing ablation studies that validate their key design choices, particularly the importance of both the expanded action space and mutual consistency verification. The provided baselines are also good.

The majority of the paper is well written and clearly expressed.

The significance of this work is particularly noteworthy. It demonstrates that SLMs possess stronger latent reasoning capabilities than previously believed and provides a practical method for improving SLM reasoning without requiring expensive fine-tuning or supervision from larger models.
summary: This paper tackles the challenge of improving small language models' reasoning abilities without fine-tuning or larger model supervision. The key innovation is a two-phase approach called rStar: first, a generator phase uses Monte Carlo Tree Search with an expanded set of reasoning operations (like decomposing problems, rephrasing questions, and proposing intermediate steps) to create potential solution paths. Then, a discriminator phase uses a second small language model to verify these solutions through "mutual consistency" (checking if the model can arrive at the same conclusion given partial steps). The approach is notable because it improves performance through better inference-time decision making rather than parameter updates or knowledge distillation from larger models. The empirical results demonstrate substantial improvements across multiple reasoning benchmarks and model sizes, suggesting that smaller language models have more latent reasoning capability than previously thought, but need better mechanisms to access it. The authors validate their approach through extensive ablation studies showing the importance of both the expanded MCTS action space and the mutual consistency verification.
weaknesses: The description of rStar in the introduction, starting on line 71, is hard to follow. Perhaps breaking the algorithm down into bullet points would help make the process more explicit and easier to digest than the wall of text. Moving figure 3 to the beginning would also be effective.

On line 255 you say "based on whether it reaches the correct answer" (which would imply you're using the ground truth answer during your search), but it seems like it is simply based on the likelihood of self-consistency majority voting mentioned on line 259.

It seems one potential limitation of mutual reasoning consistency is if an early action makes an incorrect statement that dramatically simplifies the problem. In this case it is likely that $SLM_2$ matches $SLM_1$. Given that this method works so well, this clearly isn't a critial issue, but certainly worth addressing/exploring more (at the very least mention this potential limitation).

Comparisons to other MCTS methods would be nice to have. A quick google search found (on top of the couple cited in the paper) "Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning" and "Improve Mathematical Reasoning in Language Models by Automated Process Supervision". How do these approaches performance compare to yours?

Meta-review: (a) Summary:
The paper introduces rStar, a novel self-play mutual reasoning approach that improves small language models' (SLMs) reasoning capabilities without requiring fine-tuning or supervision from larger models. The key technical contributions include:
1. A generation-discrimination process where the target SLM uses MCTS augmented with human-like reasoning actions to generate solutions
2. A verification mechanism using another SLM as a discriminator to ensure mutual consistency
3. Extensive empirical validation showing significant improvements across multiple reasoning benchmarks (GSM8K, GSM-Hard, MATH, SVAMP, StrategyQA)

(b) Strengths:
1. Novel Technical Approach: The combination of MCTS with diverse reasoning actions and mutual consistency verification is innovative and well-justified
2. Strong Empirical Results: Comprehensive evaluation across multiple benchmarks and model sizes, with significant performance improvements
3. No Fine-tuning Required: Method works with pretrained models, making it widely accessible
4. Thorough Ablation Studies: Clear demonstration of the importance of each component
5. Good Generalization: Shows effectiveness across different reasoning tasks and on unseen problems 

(c) Weaknesses:
1. High Computational Cost: The method requires substantial token generation 
2. Manual Action Selection: The five reasoning actions are manually designed, raising questions about optimality
3. Limited Model Size Exploration: Primary focus on 7B-8B parameter models due to computational constraints
4. Potential Edge Cases: In rare cases, early incorrect statements might lead to consistent but wrong answers

(d) Reasons for Acceptance:
1. Significant Technical Innovation: The paper introduces a novel approach combining MCTS, diverse reasoning actions, and mutual consistency verification
2. Strong Empirical Results: Demonstrates substantial improvements across multiple benchmarks
3. Practical Impact: Method works with pretrained models and doesn't require fine-tuning or larger model supervision
4. Thorough Evaluation: Comprehensive ablation studies and analysis validate the approach
5. Clear Presentation: Well-written with clear methodology explanation

Decision: Accept (Poster)