rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking — part 1/4

Cleaned-text code points [0, 15428). Bibliography omitted here; source.md includes it.

# rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking

###### Abstract

We present rStar-Math to demonstrate that small language models (SLMs) can rival or even surpass the math reasoning capability of OpenAI o1, without distillation from superior models. rStar-Math achieves this by exercising “deep thinking” through Monte Carlo Tree Search (MCTS), where a math policy SLM performs test-time search guided by an SLM-based process reward model . rStar-Math introduces three innovations to tackle the challenges in training the two SLMs: (1) a novel code-augmented CoT data sythesis method, which performs extensive MCTS rollouts to generate step-by-step verified reasoning trajectories used to train the policy SLM; (2) a novel process reward model training method that avoids naïve step-level score annotation, yielding a more effective process preference model (PPM) ; (3) a self-evolution recipe in which the policy SLM and PPM are built from scratch and iteratively evolved to improve reasoning capabilities. Through 4 rounds of self-evolution with millions of synthesized solutions for 747k math problems, rStar-Math boosts SLMs’ math reasoning to state-of-the-art levels. On the MATH benchmark, it improves Qwen2.5-Math-7B from 58.8% to 90.0% and Phi3-mini-3.8B from 41.4% to 86.4%, surpassing o1-preview by +4.5% and +0.9%. On the USA Math Olympiad (AIME), rStar-Math solves an average of 53.3% (8/15) of problems, ranking among the top 20% the brightest high school math students. Code and data will be available at https://github.com/microsoft/rStar .

## 1 Introduction

Recent studies have demonstrated that large language models (LLMs) are capable of tackling mathematical problems ( Team, 2024a ; Yang et al., 2024 ; OpenAI, 2024 ; Liu et al., 2024 ) . However, the conventional approach of having LLMs generate complete solutions in a single inference – akin to System 1 thinking ( Daniel, 2011 ) – often yields fast but error-prone results ( Valmeekam et al., 2023 ; OpenAI, 2023 ) . In response, test-time compute scaling ( Snell et al., 2024 ; Qi et al., 2024 ) suggests a paradigm shift toward a System 2-style thinking, which emulates human reasoning through a slower and deeper thought process. In this paradigm, an LLM serves as a policy model to generate multiple math reasoning steps, which are then evaluated by another LLM acting as a reward model ( OpenAI, 2024 ) . The steps and solutions deemed more likely to be correct are selected. The process repeats iteratively and ultimately derives the final answer.

In the test-time compute paradigm, the key is to train a powerful policy model that generates promising solution steps and a reliable reward model that accurately evaluates them, both of which depend on high-quality training data. Unfortunately, it is well-known that off-the-shelf high-quality math reasoning data is scarce, and synthesizing high-quality math data faces fundamental challenges. For the policy model, it is challenging to distinguish erroneous reasoning steps from the correct ones, complicating the elimination of low-quality data. It is worth noting that in math reasoning, a correct final answer does not ensure the correctness of the entire reasoning trace ( Lanham et al., 2023 ) . Incorrect intermediate steps significantly decrease data quality. As for the reward model, process reward modeling (PRM) shows a great potential by providing fine-grained feedback on intermediate steps ( Lightman et al., 2023 ) . However, the training data is even scarcer in this regard: accurate step-by-step feedback requires intense human labeling efforts and is impractical to scale, while those automatic annotation attempts show limited gains due to noisy reward scores ( Luo et al., 2024 ; Wang et al., 2024c ; Chen et al., 2024 ) . Due to the above challenges, existing distill-based data synthesis approaches to training policy models, e.g., scaling up GPT4-distilled CoT data ( Tang et al., 2024 ; Huang et al., 2024 ) , have shown diminishing returns and cannot exceed the capability of their teacher model; meanwhile, as of today, training reliable PRMs for math reasoning remains an open question.

In this work, we introduce rStar-Math , a self-evolvable System 2-style reasoning approach that achieves the state-of-the-art math reasoning, rivaling and sometimes even surpassing OpenAI o1 on challenging math competition benchmarks with a model size as small as 7 billion. Unlike solutions relying on superior LLMs for data synthesis, rStar-Math leverages smaller language models (SLMs) with Monte Carlo Tree Search (MCTS) to establish a self-evolutionary process, iteratively generating higher-quality training data. To achieve self-evolution, rStar-Math introduces three key innovations.

First, a novel code-augmented CoT data synthesis method, which performs extensive MCTS rollouts to generate step-by-step verified reasoning trajectories with self-annotated MCTS Q-values . Specifically, math problem-solving is decomposed into multi-step generation within MCTS. At each step, the SLM serving as the policy model samples candidate nodes, each generating a one-step CoT and the corresponding Python code. To verify the generation quality, only nodes with successful Python code execution are retained, thus mitigating errors in intermediate steps. Moreover, extensive MCTS rollouts automatically assign a Q-value to each intermediate step based on its contribution: steps contributing to more trajectories that lead to the correct answer are given higher Q-values and considered higher quality. This ensures that the reasoning trajectories generated by SLMs consist of correct, high-quality intermediate steps.

Second, a novel method that trains an SLM acting as a process preference model , i.e., a PPM to implement the desired PRM, that reliably predicts a reward label for each math reasoning step. The PPM leverages the fact that, although Q-values are still not precise enough to score each reasoning step despite using extensive MCTS rollouts, the Q-values can reliably distinguish positive (correct) steps from negative (irrelevant/incorrect) ones. Thus the training method constructs preference pairs for each step based on Q-values and uses a pairwise ranking loss ( Ouyang et al., 2022 ) to optimize PPM’s score prediction for each reasoning step, achieving reliable labeling. This approach avoids conventional methods that directly use Q-values as reward labels ( Luo et al., 2024 ; Chen et al., 2024 ) , which are inherently noisy and imprecise in stepwise reward assignment.

Finally, a four-round self-evolution recipe that progressively builds both a frontier policy model and PPM from scratch. We begin by curating a dataset of 747k math word problems from publicly available sources. In each round, we use the latest policy model and PPM to perform MCTS, generating increasingly high-quality training data using the above two methods to train a stronger policy model and PPM for next round. Each round achieves progressive refinement: (1) a stronger policy SLM, (2) a more reliable PPM, (3) generating better reasoning trajectories via PPM-augmented MCTS, and (4) improving training data coverage to tackle more challenging and even competition-level math problems.

Extensive experiments across four SLMs (1.5B-7B) and seven math reasoning tasks demonstrate the effectiveness of rStar-Math. Remarkably, rStar-Math improves all four SLMs, matching or even surpassing OpenAI o1 on challenging math benchmarks. On MATH benchmark, with 8 search trajectories, rStar-Math boosts Qwen2.5-Math-7B from 58.8% to 89.4% and Qwen2.5-Math-1.5B from 51.2% to 87.8%. With 64 trajectories, the scores rise to 90% and 88.4%, outperforming o1-preview by 4.5% and 2.6% and matching o1-mini’s 90%. On the Olympiad-level AIME 2024, rStar-Math solves on average 53.3% (8/15) of the problems, exceeding o1-preview by 8.7% and all other open-sourced LLMs. We further conduct comprehensive experiments to verify the superiority of step-by-step verified reasoning trajectories over state-of-the-art data synthesis baselines, as well as the PPM’s effectiveness compared to outcome reward models and Q value-based PRMs. Finally, we present key findings from rStar-Math deep thinking, including the intrinsic self-reflection capability and PPM’s preference for theorem-applications intermediate steps.

## 2 Related Works

Math Data Synthesis . Advancements in LLM math reasoning have largely relied on curating high-quality CoT data, with most leading approaches being GPT-distilled, using frontier models like GPT-4 for synthesis ( Wang et al., 2024b ; Gou et al., 2023 ; Luo et al., 2023 ) . Notable works include NuminaMath ( Jia LI and Polu, 2024a ) and MetaMath ( Yu et al., 2023b ) . While effective, this limits reasoning to the capabilities of the teacher LLM. Hard problems that the teacher LLM cannot solve are excluded in the training set. Even solvable problems may contain error-prone intermediate steps, which are hard to detect. Although rejection sampling methods ( Yuan et al., 2023 ; Brown et al., 2024 ) can improve data quality, they do not guarantee correct intermediate steps. As a result, scaling up CoT data has diminishing returns, with gains nearing saturation—e.g., OpenMathInstruct-2 ( Toshniwal et al., 2024 ) only sees a 3.9% boost on MATH despite an 8× increase in dataset size.

Scaling Test-time Compute has introduced new scaling laws, allowing LLMs to improve performance across by generating multiple samples and using reward models for best-solution selection ( Snell et al., 2024 ; Wu et al., 2024 ; Brown et al., 2024 ) . Various test-time search methods have been proposed ( Kang et al., 2024 ; Wang et al., 2024a ) , including random sampling ( Wang et al., 2023 ) and tree-search methods ( Yao et al., 2024 ; Hao et al., 2023 ; Zhang et al., 2024b ; Qi et al., 2024 ) like MCTS. However, open-source methods for scaling test-time computation have shown limited gains in math reasoning, often due to policy LLM or reward model limitations. rStar-Math addresses this by iteratively evolving the policy LLM and reward model, achieving System 2 mathematical reasoning performance comparable to OpenAI o1 ( OpenAI, 2024 ) .

Reward Models are crucial for effective System 2 reasoning but are challenging to obtain. Recent works include LLM-as-a-Judge for verification ( Zheng et al., 2023 ; Qi et al., 2024 ) and specialized reward models like Outcome Reward Model ( Yang et al., 2024 ; Yu et al., 2023a ) and Process Reward Model (PRM) ( Lightman et al., 2024 ) . While PRMs offer promising dense, step-level reward signals for complex reasoning ( Luo et al., 2024 ; Wang et al., 2024c ) , collecting step-level annotations remains an obstacle. While Kang et al. (2024) ; Wang et al. (2024a) rely on costly human-annotated datasets like PRM800k ( Lightman et al., 2024 ) , recent approaches ( Wang et al., 2024c ; Luo et al., 2024 ) explore automated annotation via Monte Carlo Sampling or MCTS. However, they struggle to generate precise reward scores, which limits performance gains. rStar-Math introduces a novel process preference reward (PPM) that eliminates the need for accurate step-level reward score annotation.

## 3 Methodology

### 3.1 Design Choices

MCTS for Effective System 2 Reasoning . We aim to train a math policy SLM and a process reward model (PRM), and integrating both within Monte Carlo Tree Search (MCTS) for System 2 deep thinking. MCTS is chosen for two key reasons. First, it breaks down complex math problems into simpler single-step generation tasks, reducing the difficulty for the policy SLM compared to other System 2 methods like Best-of-N ( Brown et al., 2024 ) or self-consistency ( Wang et al., 2023 ) , which require generating full solutions in one inference. Second, the step-by-step generation in MCTS naturally yields step-level training data for both models. Standard MCTS rollout automatically assign Q-value to each step based on its contribution to the final correct answer, obviating the need for human-generated step-level annotations for process reward model training.

Ideally, advanced LLMs such as GPT-4 could be integrated within MCTS to generate training data. However, this approach faces two key challenges. First, even these powerful models struggle to consistently solve difficult problems, such as Olympiad-level mathematics. Consequently, the resulting training data would primarily consist of simpler solvable problems, limiting its diversity and quality. Second, annotating per-step Q-values demands extensive MCTS rollouts; insufficient tree exploration can lead to spurious Q-value assignments, such as overestimating suboptimal steps. Given that each rollout involves multiple single-step generations and these models are computationally expensive, increasing rollouts significantly raises inference costs.

Overview . To this end, we explore using two 7B SLMs (a policy SLM and a PRM) to generate higher-quality training data, with their smaller size allowing for extensive MCTS rollouts on accessible hardware (e.g., 4 × \times 40GB A100 GPUs). However, self-generating data presents greater challenges for SLMs, due to their weaker capabilities. SLMs frequently fail to generate correct solutions, and even when the final answer is correct, the intermediate steps are often flawed or of poor quality. Moreover, SLMs solve fewer challenging problems compared to advanced models like GPT-4.

This section introduces our methodology, as illustrated in Fig. 1 . To mitigate errors and low-quality intermediate steps, we introduce a code-augmented CoT synthetic method, which performs extensive MCTS rollouts to generate step-by-step verified reasoning trajectories, annotated with Q-values. To further improve SLM performance on challenging problems, we introduce a four-round self-evolution recipe. In each round, both the policy SLM and the reward model are updated to stronger versions, progressively tackling more difficult problems and generating higher-quality training data. Finally, we present a novel process reward model training approach that eliminates the need for precise per-step reward annotations, yielding the more effective process preference model (PPM).

### 3.2 Step-by-Step Verified Reasoning Trajectory

We start by introducing our method for generating step-by-step verified reasoning trajectories with per-step Q-value annotations. Given a problem x x and a policy model M M , we run the standard MCTS to incrementally construct a search tree for step-by-step solution exploration. As shown in Fig. 1 (a), the root node represents question x x , while child nodes correspond to intermediate steps s s generated by M M . A root-to-leaf path ending at terminal node s d s_{d} forms a trajectory 𝐭 = x ⊕ s 1 ⊕ s 2 ⊕ … ⊕ s d \mathbf{t}=x\oplus s_{1}\oplus s_{2}\oplus...\oplus s_{d} , with each step s i s_{i} assigned a Q-value Q ⁡ ( s i ) Q(s_{i}) . From the search tree 𝒯 \mathcal{T} , we extract solution trajectories 𝕋 = { 𝐭 1 , 𝐭 2 , … , 𝐭 n } ​ ( n ≥ 1 ) \mathbb{T}=\{\mathbf{t}^{1},\mathbf{t}^{2},...,\mathbf{t}^{n}\}(n\geq 1) . Our goal is to select high-quality trajectories from 𝒯 \mathcal{T} to construct the training set. For this purpose, we introduce code-augmented CoT synthesis method to filter out low-quality generations and perform extensive rollouts to improve the reliability of Q-value accuracy.