Source-linked AI summary
Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers
Zhenting Qi, Mingyuan Ma, Jiahang Xu, Li Lyna Zhang, Fan Yang, Mao Yang
TL;DR
Small language models often struggle with complex reasoning and typically benefit from superior-model supervision or fine-tuning. rStar uses MCTS-based generation with human-like reasoning actions and mutual verification by a second SLM. Across five SLMs and five diverse tasks, it substantially improves reasoning accuracy, including large GSM8K gains.
Problem
Small language models struggle with complex reasoning, while common improvements rely on fine-tuning data distilled or synthesized by superior models.
Method
rStar combines MCTS with richer human-like reasoning actions and a second, similarly capable SLM that provides unsupervised mutual-consistency verification.
Results
Across five SLMs and five diverse reasoning tasks, rStar significantly improves reasoning accuracy; LLaMA2-7B GSM8K rises from 12.51% to 63.91%.
Takeaways & Limitations
rStar shows that SLMs can achieve highly capable problem-solving during inference without fine-tuning or superior models.
Abstract
from arXiv · showhide
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 https://github.com/zhentingqi/rStar.
1 INTRODUCTION
rStar addresses the difficulty of improving SLM reasoning without fine-tuning or superior teacher models by combining richer MCTS exploration with mutual generation and discrimination. Across diverse tasks, it substantially improves accuracy and can match or surpass domain-specialized fine-tuning.
- SLMs struggle with complex reasoning, while common improvements rely on fine-tuning data distilled or synthesized by superior models.
- Self-exploration can remain trapped in low-quality reasoning, and SLMs struggle to identify better intermediate steps or correct final answers.After 32 rounds of RAP self-exploration, only 24% of LLaMA2-7B GSM8K trajectories were correct; naïve reward guidance performed no better than random guesses.
- rStar uses MCTS with human-like reasoning actions to generate candidate trajectories and a second SLM to discriminate among them through mutual consistency.The actions include decomposing or searching for steps, proposing sub-questions, and rephrasing the question.
- 32 rounds of MCTS inference significantly improve SLM reasoning across five models and five diverse tasks, matching or surpassing fine-tuned accuracy.
- 12.51% to 63.91% is LLaMA2-7B’s GSM8K accuracy improvement with rStar, while Mistral rises from 36.46% to 81.88%.
2 RELATED WORK
Related work improves language-model reasoning through prompting, self-improvement, path sampling, and answer verification. rStar combines these concerns through richer search and mutual verification without relying on superior teachers or task-specific reward models.
- Prompting Language Models to Reason: Prompting methods improve single-round inference through instructions and techniques such as chain-of-thought, planning, decomposition, abstraction, and programming.
- LLM Self-improvement: Self-improvement methods use fine-tuning or iterative prompting, but fine-tuning commonly relies on data synthesized by stronger models and self-feedback can be unreliable.
- Sampling Reasoning Paths: Sampling diverse reasoning paths, including self-consistency and tree search, improves over greedy decoding but still depends on obtaining sufficiently good trajectories.
- Answer Verification: Answer verification methods use voting, trained reward models, or self-verification, each facing requirements for correct traces, annotations, generalization, or reliable self-evaluation.
3 METHODOLOGY
rStar addresses SLM self-improvement challenges by combining richer human-like reasoning actions with MCTS generation, reward propagation, and mutual verification. Its methodology decomposes reasoning into candidate trajectory generation and discriminator-based evaluation without external supervision.
- Overview: rStar formulates reasoning as multi-step trajectory generation, where MCTS incrementally builds a search tree of intermediate steps and candidate solutions.Each root-to-leaf path forms a candidate trajectory for the original question.
- Mutual Reasoning Consistency: A second SLM discriminates candidate trajectories by completing masked reasoning steps from an earlier partial trajectory, enabling mutual verification.This discriminator augments the target SLM with external unsupervised feedback during MCTS.
- A Rich Set of Human-like Reasoning Actions: rStar expands MCTS with five human-like actions: one-step thoughts, remaining thoughts, sub-question answering, re-answering, and question rephrasing.Actions are selected according to the current state, with ordering constraints such as re-answering after sub-question generation.
- A Rich Set of Human-like Reasoning Actions: The five actions define a diverse action space that MCTS uses to generate reasoning steps from the preceding trajectory.The method restricts certain actions to appropriate states, such as allowing question rephrasing only at the root and re-answering after sub-question answering.
- Reward Function: rStar avoids intermediate self-rewarding and external supervision by rewarding actions according to whether their trajectories lead to correct final answers.Terminal rewards are propagated backward through intermediate nodes, while UCT balances exploration and exploitation during tree selection.
4 EXPERIMENTS
Experiments across five SLMs and five reasoning tasks evaluate rStar’s setup, benchmark performance, rollout efficiency, and generator, discriminator, and self-rewarding components. rStar improves reasoning accuracy across challenging mathematical datasets and diverse tasks, while mutual reasoning verification remains effective with SLM discriminators.
- 4.1 SETUP: rStar is evaluated on five SLMs across five reasoning tasks, including four mathematical benchmarks and StrategyQA.
- 4.1 SETUP: The evaluation uses 32 MCTS rollouts, with Phi3-mini-4k serving as the discriminator for efficient parallelized trajectory verification.
- 4.2 MAIN RESULTS: rStar improves reasoning accuracy across diverse SLMs and tasks, with LLaMA2-7B rising from 12.51% to 63.91% on GSM8K.
- 4.3 ABLATION STUDY: The discriminator consistently outperforms majority voting and self-verification, while changing the discriminator model generally does not affect mutual reasoning consistency.GPT-4 only raises LLaMA3-8B-Instruct accuracy from 91.13% to 92.57%.
- 4.2 MAIN RESULTS: Up to +12.9% and +9.14% improvements are observed on GSM-Hard and MATH-500, respectively, compared with state-of-the-art baselines.
- 4.2 MAIN RESULTS: With just 2 rollouts, rStar significantly improves GSM8K reasoning accuracy, while additional rollouts benefit both rStar and self-consistency.
- 4.3 ABLATION STUDY: The MCTS generator is evaluated against RAP, randomly sampled self-consistency, and self-evaluation variants under majority voting and discriminator verification.
5 CONCLUSION
The conclusion presents rStar as a generator-discriminator self-play approach that strengthens SLM reasoning at inference time. Across five SLMs and five diverse reasoning tasks, it achieves state-of-the-art performance and outperforms existing multi-round prompting and self-improvement approaches.
- rStar significantly grows SLM reasoning capabilities at inference time through generator-discriminator self-play.
- Across five SLMs and five diverse reasoning tasks, rStar achieves state-of-the-art performance and substantially outperforms existing multi-round approaches.
A.1 EXPERIMENTS TO EVALUATE THE SELF-REWARDING IN SLMS
This ablation examines whether RAP’s self-rewarding signals improve SLM reasoning. Replacing self-evaluation with random values has little effect, whereas randomizing answer-confidence scores can reduce accuracy.
- RAP combines self-evaluation of a node’s helpfulness with self-consistency confidence to compute its reward as r = r1 × r2.
- Replacing r1 with random values has minimal impact on RAP performance across the evaluated SLMs and datasets.
- Replacing r2 with random values causes a noticeable accuracy drop on Mistral and Multiarith.
- The results suggest LLaMA2-7B and Mistral perform near-random self-evaluations for r1.
A.2 DISCUSSIONS
The generator and discriminator contribute differently depending on the SLM’s solution-generation effectiveness, while both remain necessary for rStar’s final performance. The approach also incurs substantial inference costs from MCTS self-generation.
- On LLaMA2-7B, rStar’s generator improves GSM8K accuracy by +4.17%, while the discriminator adds a further +36.69%.
- Both components are crucial because the generator must first produce a correct solution for the discriminator to identify.
- The discriminator is especially important for weaker solution generation, whereas improving the generator matters more when the model already produces many correct solutions.
- rStar’s primary inference cost comes from the MCTS self-generator, which requires many model inferences and generated tokens.
- After 32 rollouts, solving a GSM8K question averages 166 model calls on LLaMA2-7B and 148 on Mistral.
- Completing 32 rollouts for the GSM8K test set takes about 4.5 days on one A100 GPU per model, though distribution and batching can reduce this cost.
A.3 PROMPT EXAMPLES IN MTCS
The MCTS prompt examples instantiate rStar’s reasoning actions through stepwise thought generation, sub-question decomposition, answer proposal, and question rephrasing. The examples apply these actions to arithmetic and multi-step word problems.
- Reasoning actions: The prompt begins by asking the model to propose an one-step thought while framing the response as step-by-step reasoning.
- Reasoning actions: A later action asks the model to propose the remaining thought steps or answer the sub-question again.
- Worked examples: The examples demonstrate direct arithmetic reasoning for addition, subtraction, multiplication, and combined operations in short word problems.
- Prompt templates: The prompt templates include placeholders for the user question and response, alongside worked examples showing explicit numbered reasoning steps.
- Reasoning actions: One prompt action asks the model to propose the next sub-question together with its answer.
- Sub-question decomposition: The decomposition prompt requires complete-sentence answers to sub-questions and an explicit final-answer format for answerable original questions.
- Sub-question decomposition: Longer examples decompose age, firefly-count, money, and tunnel problems into intermediate questions before reaching the original answer.
- Question rephrasing: Another action rephrases the question or sub-question by splitting its context into conditions while preserving the original information.