Reasoning2024~115 minarXiv:2408.06195

MUTUAL REASONING MAKES SMALLER LLMS STRONGER PROBLEM-SOLVERS

Reasoning via RL Self-improvement & synthetic data

Zhenting Qi, Mingyuan Ma, Jiahang Xu +3Aug 12, 2024cs.CL

🎯 Pitch

Small language models can solve math problems nearly as well as fine-tuned ones without any training—just by having a weaker model fact-check their reasoning. rStar boosts a tiny LLaMA2-7B from 12% to 64% on GSM8K by having the model generate diverse solution paths via MCTS and then asking a peer to verify each path’s self-consistency.

1. Executive Summary

This paper introduces rStar, a self-play mutual reasoning approach that significantly improves the reasoning capabilities of small language models (SLMs) at inference time without fine-tuning or distillation from superior models. The method decouples reasoning into a self-play mutual generation-discrimination process: a target SLM augmented with Monte Carlo Tree Search (MCTS) uses a rich set of five human-like reasoning actions (e.g., proposing a one-step thought, decomposing into sub-questions, rephrasing the question) to generate candidate reasoning trajectories, while a second SLM of similar capability acts as a discriminator to verify each trajectory through mutual reasoning consistency (masking part of a trajectory and checking whether the discriminator completes it to the same answer). Across five SLMs and five reasoning benchmarks, rStar boosts GSM8K accuracy from 12.51% to 63.91% for LLaMA2-7B, from 36.46% to 81.88% for Mistral-7B, and from 74.53% to 91.13% for LLaMA3-8B-Instruct — improvements that match or surpass the accuracy achieved after domain-specialized supervised fine-tuning — establishing that SLMs already possess strong reasoning capabilities that can be unlocked through structured generation and peer verification, even when self-rewarding and self-verification prove unreliable in these smaller models.

2. Context and Motivation

The Core Problem: Small Language Models Are Fundamentally Weak Reasoners — But Why?

This paper confronts a puzzle that has become increasingly urgent as language models proliferate across deployment contexts. Small language models (SLMs) — models in the 3–8 billion parameter range like LLaMA2-7B, Mistral-7B, and Phi3-mini — consistently underperform on complex reasoning tasks despite possessing substantial world knowledge acquired during pretraining. For example, LLaMA2-7B achieves only 12.51% accuracy on the GSM8K math word problem benchmark even with few-shot chain-of-thought prompting (Table 2). Mistral-7B, a stronger and more recent model, reaches only 36.46%. These numbers are far below what would be practically useful in any application requiring reliable multi-step deduction.

The standard remedy for weak reasoning has been supervised fine-tuning (SFT) on reasoning data — but this creates a dependency. High-quality SFT data for reasoning is typically synthesized by more capable, often proprietary models like GPT-4 (Wang et al., 2024a; Gou et al., 2023). The paper's Figure 1 makes this concrete: fine-tuning LLaMA2-7B on MetaMath (which is distilled from GPT-4 outputs) raises GSM8K accuracy from 12.51% to roughly 66%. But what if you don't have access to a superior teacher model? What if the model is deployed in an environment where only local, relatively weak models are available? This is the setting the paper targets — reasoning improvement without any superior model, relying purely on the knowledge already inside the SLM itself.

The theoretical significance is that it forces a re-examination of why SLMs fail at reasoning. Is their pretrained knowledge insufficient? Or do they possess the necessary knowledge but lack the capacity to deploy it reliably through standard generation strategies? If the latter, then the bottleneck is not a knowledge deficit but a generation and verification problem — the model cannot reliably sample correct reasoning paths from its own distribution and cannot reliably recognize correctness when it stumbles upon it. This is the hypothesis rStar sets out to test, and it has direct implications: if true, then reasoning improvement becomes an inference-time problem rather than a training-time problem, which fundamentally changes how one allocates compute resources.

Why This Problem Matters Now

The paper's framing in Section 1 highlights several practical drivers:

Proliferation of SLMs in constrained environments. Models like Phi3-mini (3.8B parameters) are explicitly designed for on-device or edge deployment (Abdin et al., 2024) — running on phones, laptops, or private servers where neither cloud connectivity nor GPT-4-level models are available. If these models remain incapable of reliable multi-step reasoning, their practical utility in domains like tutoring, personal assistance, or automated decision support is severely limited. Unlocking their latent reasoning capability at inference time would dramatically expand their deployable scope.

Self-improvement without teacher dependency. The dominant paradigm for improving SLM reasoning — distilling from larger models — creates a bottleneck. It requires that a superior model already exists and that its outputs are accessible (financially, legally, and technically). For many organizations, especially those operating in regulated industries or with proprietary data that cannot be sent to external APIs, this is not viable. The paper explicitly positions itself as pursuing "a complimentary and yet more challenging approach: Reasoning improvements without a superior teacher LLM" (Section 1). If successful, this opens a path to reasoning improvement that is self-contained — the model improves using only its own knowledge and peer models of comparable capability.

The robustness-capability gap in smaller models. Recent work has shown that while large models like GPT-4 can benefit from self-refinement and self-verification techniques (Madaan et al., 2024; Wu et al., 2024; Zhou et al., 2024), these same techniques often fail or even degrade performance when applied to smaller models (Forsman, 2024). The paper explicitly cites this finding: "the approaches are less effective in SLMs and may even lead to worse performance." This suggests that the self-improvement toolbox developed for frontier models does not directly transfer downward, and a new approach tailored to SLM limitations is needed.

Where Prior Approaches Fall Short

The paper positions itself against three families of prior work, each of which addresses part of the problem but falls short for SLMs. Understanding these gaps is essential to seeing why rStar's design choices are what they are.

1. Self-Exploration via Tree Search (e.g., RAP, ToT)

The most directly comparable prior work is RAP (Reasoning via Planning; Hao et al., 2023), which uses Monte Carlo Tree Search to let an LLM iteratively decompose problems into sub-questions and self-explore the solution space. This is the paradigm the paper builds on most heavily. However, the paper identifies two specific, empirically grounded limitations:

Ineffective space exploration from narrow action spaces. RAP uses a single action type — proposing the next sub-question — at every node of the search tree. The paper argues (Section 3.1) that this severely limits diversity in the generated reasoning trajectories. Different problems require different reasoning strategies: some benefit from direct step-by-step solving, others need decomposition, still others require re-reading and rephrasing the problem when the model misunderstands key conditions. A single-action MCTS cannot adapt its exploration strategy to the problem's characteristics. The paper quantifies this: "after 32 rounds of self-exploration with RAP, only 24% of the trajectories generated by LLaMA2-7B on GSM8K are correct" (Section 1). This means 76% of the generated trajectories are incorrect — a high-noise environment where answer selection becomes critical but difficult.

Near-random self-rewarding in SLMs. RAP's MCTS relies on a self-evaluated reward function to guide tree expansion: the model scores each intermediate node on how "helpful" it is. The paper's Appendix A.1 presents a devastating ablation: replacing RAP's self-evaluated reward component r1 (the model's own estimation of a sub-question's usefulness) with random values has "minimal impact on RAP's performance across different SLMs and datasets" (Table 6). On LLaMA2-7B with GSM8K, RAP achieves 24.34% accuracy; RAP with random r1 achieves 22.90% — a statistically negligible drop. This means SLMs are essentially incapable of reliable self-evaluation during tree search: their internal confidence estimates are no better than random, so the MCTS guidance signal is effectively noise. This is the central empirical finding that motivates rStar's decision to abandon self-rewarding entirely in favor of an external discriminator.

ToT (Tree of Thoughts; Yao et al., 2024) suffers from similar limitations. It uses a single "propose one thought" action and relies on BFS rather than MCTS for traversal. The paper's results (Table 2) show ToT consistently underperforms even few-shot CoT on several benchmarks — for example, 12.96% vs. 12.51% on LLaMA2-7B GSM8K, and 36.01% vs. 47.23% on LLaMA3-8B GSM8K — suggesting that its exploration strategy is actively counterproductive for weaker models.

2. Self-Consistency and Majority Voting

Self-consistency (SC; Wang et al., 2023) is the dominant answer selection method in multi-round reasoning: sample $N$ complete reasoning chains independently, then select the most frequent final answer via majority voting. For strong models where most samples are correct, this works well — it's essentially an error-correction mechanism that cancels out occasional mistakes. But SC has an implicit assumption that breaks down for SLMs: the correct answer must be the mode of the output distribution. If the model produces incorrect answers more often than correct ones (which is the case when pass@1 is low, as for LLaMA2-7B at 12.51%), majority voting cannot recover the correct answer — the majority is wrong by construction.

The paper's results bear this out. Table 2 shows that scaling SC from 8 to 128 samples on LLaMA2-7B for GSM8K improves accuracy from 15.31% to only 23.05% — a gain of less than 8 percentage points from a 16× increase in compute. On StrategyQA, SC@128 actually lowers accuracy compared to SC@8 for several models (e.g., LLaMA3-8B drops from 63.76% to 63.31%), and for LLaMA2-7B, SC@128 underperforms few-shot CoT (58.37% vs. 58.82%). The paper notes this explicitly: "SC with more sampling can even lower the score on StrategyQA" (Section 4.2). This happens because sampling more chains adds noise faster than it adds correct answers when the base pass@1 is low.

More subtly, majority voting treats all reasoning chains as equally trustworthy — it has no mechanism to distinguish a logically sound but minority reasoning path from an incorrect majority path. On problems where the correct reasoning is subtle and most attempts go wrong, SC is fundamentally limited regardless of the number of samples.

3. Self-Verification and Self-Evaluation

A more recent family of methods attempts to have the LLM verify its own outputs: self-verification (Weng et al., 2023) prompts the model to check whether a generated reasoning chain is correct, while self-refine (Madaan et al., 2024) iteratively critiques and revises outputs. These techniques have shown promise on large models like GPT-4, but the paper and cited prior work (Huang et al., 2023; Feng et al., 2023) demonstrate they are unreliable for SLMs.

The paper's Table 5 (left) provides direct evidence: for LLaMA3-8B's MCTS-generated trajectories, self-verification achieves 75.52% accuracy compared to 85.52% for rStar's discriminator. Similarly, Table 4 shows that adding self-evaluation to rStar's generator reduces accuracy on LLaMA3-8B GSM8K from 74.38% to 70.28%. The paper's explanation is that SLMs "struggle to evaluate themselves and rectify their initial responses without any external feedbacks" (Section 2). This is consistent with the random self-rewarding finding in Appendix A.1 — the fundamental problem is that the model's internal confidence signal is decoupled from actual correctness for smaller models.

Trained reward models (e.g., Wang et al., 2024b; Chen et al., 2024a) avoid the self-evaluation problem by training a separate verifier, but introduce two new problems: they require additional training data with correctness annotations (which reintroduces the teacher dependency problem — where do the labels come from?), and they can overfit to specific tasks (a reward model trained on GSM8K-style problems may not transfer to StrategyQA or MATH). The paper explicitly notes these as risks (Section 2) and positions rStar as avoiding both by using an untrained discriminator with a novel consistency mechanism.

How This Paper Positions Itself

rStar synthesizes insights from these three families of prior work while addressing their specific failure modes for SLMs:

From tree search (RAP, ToT): It inherits the MCTS framework for structured exploration but replaces the single-action paradigm with a 5-action space that enables human-like adaptive reasoning. This is not an incremental change — it fundamentally broadens what kinds of reasoning paths the tree can generate, and the ablation in Table 1 shows each action contributes measurably to accuracy.
From self-consistency: It inherits the idea of sampling multiple solutions and aggregating, but replaces majority voting with mutual reasoning consistency — a verification mechanism that works even when the correct answer is not the mode. Instead of counting votes, it checks whether a different model, given partial reasoning as a hint, independently arrives at the same conclusion. This decouples verification from the generating model's internal confidence, which the paper has shown is unreliable.
For self-verification: It inherits the goal of answer verification without ground-truth labels but replaces self-verification with peer-verification — using a second SLM as discriminator rather than having the generating model judge itself. The key insight is that while one SLM's self-evaluation is unreliable, two SLMs independently agreeing on an answer is a stronger signal. This is explicitly analogized to human practice: "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" (Section 3.3).
Against trained reward models: rStar avoids training entirely — the discriminator is used zero-shot with a prompting strategy that leverages partial reasoning traces as hints. This makes the approach task-general (no per-task training data or labels needed) and eliminates the overfitting risk.

The paper's core wager is that the reasoning knowledge is already in the SLM's weights — acquired during pretraining on internet-scale text, code, and math data — and that the bottleneck is purely one of generation reliability and answer verification. If this is correct, then a sufficiently powerful search strategy (rich-action MCTS) coupled with a noise-resistant verification mechanism (mutual consistency) should unlock performance commensurate with what fine-tuning achieves — without any new knowledge injection. The paper's results, particularly the comparison to MetaMath fine-tuning in Figure 1, are designed to test exactly this hypothesis: rStar on LLaMA2-7B reaches 63.91% GSM8K accuracy, nearly matching the ~66% achieved by MetaMath fine-tuning. On Mistral-7B, rStar's 81.88% exceeds MetaMath fine-tuning's 77.7% — suggesting that the model's pretrained reasoning capability was actually underutilized during standard fine-tuning, or that the fine-tuning data introduced distributional biases that rStar's self-contained search avoids.

The Underlying Empirical Premise: SLM Self-Evaluation Is Broken

Before diving into rStar's architecture, it is worth emphasizing the empirical foundation on which the entire approach rests, because it justifies every design decision. The paper's Appendix A.1 presents a controlled experiment that, in just a few sentences, dismantles the premise of SLM self-rewarding. RAP's reward function uses two components: r1 (the model's self-evaluated helpfulness of a new sub-question, obtained by prompting "Is the new question useful?") and r2 (the confidence from self-consistency majority voting on the sub-question's answer). The final reward is r = r1 × r2. When r1 is replaced with random values, accuracy drops negligibly (24.34% → 22.90% on LLaMA2-7B GSM8K; 56.25% → 55.50% on Mistral-7B). When r2 is replaced with random values, the drop is larger (24.34% → 22.67% on LLaMA2-7B; 56.25% → 49.66% on Mistral-7B), showing that r2 carries some signal while r1 carries essentially none. The implication is stark: the model's own assessment of whether a reasoning step is "helpful" is no better than a coin flip. Any method that relies on an SLM to score its own intermediate reasoning steps — including RAP, self-verification, and self-refine — is building on sand.

This is why rStar's architecture has no self-evaluation component for intermediate nodes (Section 3.2's reward function scores nodes purely based on their contribution to reaching correct final answers, determined retrospectively through back-propagation from terminal nodes), and why the verification step is farmed out to a separate model (Section 3.3's discriminator) rather than done by the generating model. The paper does not claim this insight as novel — it is consistent with Huang et al. (2023) and Feng et al. (2023) — but it uses it as the organizing principle for the entire system design, making "don't trust the model's self-assessment" a constraint that shapes every component.

3. Technical Approach

3.1 Reader Orientation

rStar is a self-play mutual reasoning system that enables small language models to solve complex reasoning problems by having two comparable SLMs work together — one generates multiple candidate reasoning paths through a structured search process, while the other verifies those paths by checking whether it would independently arrive at the same answer given partial hints. The system solves the fundamental problem that SLMs can occasionally produce correct reasoning but cannot reliably recognize when they have done so (their self-evaluation is near-random, as demonstrated in Appendix A.1), so it replaces self-assessment with peer assessment: a second model's agreement serves as an unsupervised correctness signal that is substantially more reliable than any single model's internal confidence estimate.

3.2 Big-Picture Architecture (Diagram in Words)

The rStar system has four major components operating in sequence:

The Target SLM (Generator): The model whose reasoning capability we want to improve (e.g., LLaMA2-7B, Mistral-7B). It is augmented with a Monte Carlo Tree Search (MCTS) engine that systematically explores the space of possible reasoning paths using five distinct action types. The generator produces a set of candidate solution trajectories — complete reasoning chains from question to final answer.
The MCTS Engine with Rich Action Space: A search controller that wraps the generator and manages the tree-building process. At each step, it selects an action type (e.g., "propose next thought step," "break into sub-question," "rephrase the question"), prompts the generator with that action template, adds the resulting reasoning step as a new node, scores the node using a tailored reward function based on contribution to correct answers (not self-evaluation), and back-propagates scores up the tree. After a fixed number of rollouts (typically 32), it extracts all complete trajectories from root to terminal nodes as candidate solutions.
The Discriminator SLM (Verifier): A second SLM of comparable capability (typically Phi3-mini-4k, a 3.8B parameter model) that evaluates each candidate trajectory from the generator. For a given trajectory, the discriminator receives the first portion of the reasoning steps (randomly split at 20–80% of the path) as a prompt and is asked to complete the remaining steps to reach a final answer. If the discriminator's independently generated answer matches the original trajectory's answer, the trajectory is deemed "mutually consistent" and enters the validated pool.
Final Trajectory Selector: After the discriminator has filtered candidate trajectories, the generator selects the final answer from the validated set. Each validated trajectory receives a final score computed as the product of its MCTS reward value and the terminal node's confidence score (from the self-consistency majority voting used during rollout). The trajectory with the highest product is selected as the system's output.

Information flows sequentially: a question enters → the MCTS engine builds a search tree using the generator, producing candidate trajectories → the discriminator checks each trajectory for mutual consistency → the generator selects the highest-scoring validated trajectory as the final answer.

3.3 Roadmap for the Deep Dive

First, the MCTS formulation and problem setup, including how reasoning is formalized as tree search, the definition of nodes, edges, actions, and trajectories. This establishes the mathematical scaffolding on which everything else depends.
Second, the rich action space (the five A1–A5 actions), because the choice of what actions the model can take at each node fundamentally determines the diversity and quality of trajectories the tree can generate. Understanding each action's purpose and the ablation evidence for their contributions is essential before seeing how they fit into the search algorithm.
Third, the reward function and back-propagation mechanism, which is the critical departure from prior work: rStar abandons self-evaluation for intermediate nodes entirely and instead uses retrospective scoring based on terminal node correctness. This is the solution to the "SLMs cannot self-reward" problem established in Appendix A.1.
Fourth, the MCTS rollout procedure itself, explaining how the four standard MCTS operations (selection, expansion, simulation, back-propagation) are adapted to the language model setting with the UCT formula, the exploration-exploitation tradeoff, and the collection of candidate trajectories.
Fifth, the mutual reasoning consistency mechanism, which is rStar's core innovation for answer verification. This includes how the discriminator is prompted (the masking strategy, why partial hints are provided), the statistical rationale for why two-model agreement is informative when both models are weak, and how the validated set is constructed.
Sixth, the final trajectory selection procedure, which explains how MCTS rewards and terminal confidence scores are combined to pick the best answer from validated trajectories.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a systems-and-methods paper whose core idea is that SLM reasoning can be substantially improved by (a) giving the model a diverse set of reasoning strategies to explore via MCTS, (b) avoiding any reliance on the model's own assessment of intermediate step quality (which is empirically near-random), and (c) using a second, independent SLM's agreement as a proxy for correctness — a mechanism called mutual reasoning consistency.

Problem Formalization: Multi-Step Reasoning as MCTS Tree Search

The paper formalizes reasoning as a multi-step generation problem rather than a single-pass completion problem (Section 3.1). This is a deliberate design choice: the authors argue that "it is much easier for SLMs to correctly generate one step than complete reasoning steps in a single inference," which motivates the tree-search approach over standard chain-of-thought.

Formal setup. Let $x$ be the input question (e.g., "Jason had 20 lollipops. He gave Denny some lollipops. Now Jason has 12 lollipops. How many lollipops did Jason give to Denny?"), and let $M$ denote the target SLM — the model whose reasoning performance we want to improve. The MCTS framework uses $M$ to incrementally build a search tree $\mathcal{T}$ .

Tree structure. The root node of $\mathcal{T}$ represents the original question $x$ . Each edge in the tree corresponds to a reasoning action $a$ selected from the action space $\{A_1, A_2, A_3, A_4, A_5\}$ (detailed in the next subsection). Each child node is an intermediate reasoning step $s$ generated by $M$ when prompted with the current reasoning state and the selected action. Concretely, if the current node represents the partial reasoning $x \oplus s_1 \oplus s_2 \oplus \dots \oplus s_{i-1}$ , then applying action $a_i$ prompts $M$ to produce the next reasoning step $s_i$ , creating a new child node.

Trajectory definition. A path from the root to a terminal node (also called a leaf node, denoted $s_d$ , representing the final answer) constitutes a candidate solution trajectory:

$t = x \oplus s_1 \oplus s_2 \oplus \dots \oplus s_d$

where $\oplus$ denotes string concatenation. The set of all trajectories extracted from the completed search tree is $\mathbb{T} = \{t_1, t_2, \dots, t_n\}$ , where $n \geq 1$ .

Goal. From the set $\mathbb{T}$ of candidate trajectories, identify the trajectory (or trajectories) whose final answer matches the ground-truth correct answer for question $x$ . Crucially, ground-truth labels are not available during inference — the system must determine correctness through unsupervised means (the mutual consistency mechanism).

Why tree search instead of sequential generation. The paper explicitly contrasts this MCTS approach with chain-of-thought prompting. In CoT, the model produces the entire reasoning chain $s_1, s_2, \dots, s_d$ in a single forward pass (autoregressively, but without backtracking or branching). This means that an error at step $s_3$ condemns the entire trajectory — there is no mechanism to explore alternative step-3 options while keeping the correct $s_1$ and $s_2$ . MCTS addresses this by allowing the search to branch at any step, exploring multiple candidate $s_i$ values for each prefix. When the model occasionally produces a correct intermediate step (which happens with non-trivial probability even for weak models), the tree structure preserves that step and continues exploring from it, rather than discarding it because a later step in the same trajectory was wrong.

Why MCTS specifically (not BFS, DFS, or random sampling). Prior tree-search methods for LLMs have used BFS (ToT) or random sampling (self-consistency). BFS explores nodes level-by-level, which requires scoring all nodes at a given depth before moving deeper — making it dependent on a reliable intermediate scoring function, which the paper has shown SLMs lack. Random sampling (self-consistency) has no structured exploration at all — each trajectory is generated independently, so the system cannot learn from partial successes. MCTS offers a middle ground: it uses selective expansion guided by a reward signal that is back-propagated from terminal nodes, focusing computational resources on promising branches while still maintaining exploration of alternatives. The UCT formula (detailed below) provides the mathematical mechanism for this balance.

The Rich Action Space: Five Human-Like Reasoning Actions (A1–A5)

The core of rStar's MCTS generator is a set of five distinct action types that determine how the model produces the next reasoning step at each node (Section 3.2). This is the paper's primary departure from prior MCTS-based methods like RAP (which uses only one action: "propose next sub-question") and AlphaMath/MindStar (which use only "generate next reasoning step").

Motivation: the human reasoning analogy. The paper justifies the multi-action design by drawing an analogy to how humans approach problems: "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" (Section 3.2). The implication is that a single action type constrains the search tree to a particular structural pattern (e.g., always a sequence of sub-questions with answers), whereas a diverse action space allows the tree to adapt its exploration strategy to the problem's characteristics — some sub-trees might proceed via direct step-by-step reasoning, others via decomposition, others via reformulation.

The five actions, with their implementation details:

A1: Propose a one-step thought. This action prompts the SLM to generate exactly one next reasoning step, conditioned on the current reasoning prefix. Unlike chain-of-thought (which produces all steps at once), A1 generates a single atomic thought. The prompt template (reproduced in Appendix A.3) provides few-shot examples demonstrating step-by-step decomposition: for a problem about trees being planted, it shows "Step 1: Identify the initial number of trees... Step 2: Identify the final number of trees..." etc. The prompt explicitly instructs the model with "Let's think step by step" and demonstrates that each call produces exactly one logical step.

This action is suited for problems where the reasoning is best expressed as a linear sequence of deductive steps, and where generating one step at a time with re-evaluation at each stage produces higher-quality intermediate steps than generating the entire chain at once. The paper cites the decision-making literature (Yao et al., 2024; Besta et al., 2024) to support this claim: LLMs produce better decisions when they focus on one step rather than generating complete thoughts end-to-end.

A2: Propose the remaining thought steps. This action aligns with standard chain-of-thought: given the reasoning prefix generated so far, the model produces all remaining steps through to the final answer in one forward pass. The paper describes this as enabling "'fast thinking' to solve simple questions in fewer steps" (Section 3.2). The prompt template provides examples where the model directly produces a complete solution — e.g., for the lollipop problem, it generates "Jason started with 20 lollipops. Then he had 12 after giving some to Denny. So he gave Denny 20 - 12 = 8. The answer is: 8." — in a single response.

This action is efficient for problems where the model can reliably produce correct reasoning without step-by-step guidance. It reduces tree depth (fewer node expansions needed) and avoids the accumulation of errors that can occur when each step is generated independently (each independent generation introduces a chance for the model to go off-track). However, it provides less granularity for the search: if the "remaining thoughts" contain an error, the tree cannot branch at intermediate points within that multi-step block.

A3: Propose next sub-question along with its answer. This action implements the least-to-most prompting strategy (Zhou et al., 2022): instead of solving the problem directly, the model decomposes it by identifying the next sub-question that needs to be answered and then answering that sub-question. The prompt template (Appendix A.3) shows examples like: for the problem about Ali's money, the first sub-question is "How much money does Ali have after giving half of his total money to his sister?" with answer "Ali initially has four $10 bills and six$ 20 bills, totaling 4 * 10 + 6 * 20 = 160 dollars. Giving half of this to his sister leaves him with 160 / 2 = 80 dollars. The answer is 80." Then a second sub-question follows, and so on until the original question is answered directly.

This action is specifically designed for complex multi-step problems where direct end-to-end reasoning is unreliable for SLMs. By forcing the model to explicitly identify and solve sub-problems, it breaks the overall task into smaller pieces that are individually easier. The prompt template is explicit about answer formatting: "please answer it in a complete sentence, ending with 'The answer is <a numeric answer>'" — this standardization is critical for the downstream reward computation, which needs to extract final numeric answers from terminal nodes.

A4: Answer the sub-question again. This action can only be used after A3 has been applied at the current node — it re-answers the sub-question that A3 proposed. The key difference from A3 is that A4 uses a few-shot chain-of-thought prompting template (Appendix A.3, the same template as A2) rather than the least-to-most decomposition template. The paper notes that "the original answer generated by A3 did not use a CoT-like prompt but instead followed the least-to-most problem decomposition prompt" (Section 3.2), implying that A4 provides an alternative reasoning pathway for the same sub-question using a different prompting strategy. This introduces diversity: the same sub-question can now have multiple candidate answers generated via different prompting styles, and the search can explore which approach leads to correct downstream results.

This action addresses a specific failure mode: when A3 answers a sub-question incorrectly, the error propagates to all subsequent reasoning. By allowing A4 to re-answer the same sub-question (potentially correctly), the search tree creates a branch point where alternative answers to the same sub-question can be pursued. The paper's case analysis notes that "a sub-question might not be answered correctly by A3," motivating A4 as an error-recovery mechanism.

A5: Rephrase the question/sub-question. This action reformulates the original question (or a sub-question) by extracting and explicitly listing all conditions. The prompt template (Appendix A.3) provides a pattern: "Given a list of conditions, please answer the question. Condition 1: ... Condition 2: ... Question: ..." For example, the lollipop problem is rephrased as "Condition 1: Jason starts with 20 lollipops. Condition 2: After giving some lollipops to Denny, Jason has 12 lollipops left. Question: How many lollipops did Jason give to Denny?"

This action is motivated by the paper's error analysis: "many [incorrect cases] are due the LLM misunderstanding the question. For example, it might miss a specific condition provided in the question" (Section 3.2). By forcing the model to explicitly restructure the problem statement into enumerated conditions, A5 reduces the chance that critical information is overlooked during subsequent reasoning steps. The instruction to "clearly list all conditions given in the problem statement" acts as a form of attention redirection — the model must re-read and re-express all constraints rather than relying on its initial (potentially lossy) encoding of the problem.

Ordering constraints. The paper specifies that certain actions have ordering dependencies: "A4 can only happen after A3, and A5 can only happen after the root question" (Section 3.2). This makes semantic sense: you cannot re-answer a sub-question that hasn't been asked yet, and rephrasing is most naturally applied to the original problem statement (or to a sub-question, presumably also after it has been posed). These constraints are enforced during MCTS node expansion: the set of available actions at a given node depends on the action history of the path leading to that node.

Ablation evidence for the action space (Table 1). The paper evaluates the contribution of each action by measuring accuracy on 200 sampled GSM8K questions with LLaMA3-8B. Starting from A3 alone (which corresponds to RAP's action space): 70.5% accuracy. Adding A5: 72.5% (+2.0%). Adding A4: 73.5% (+1.0%). Adding A2: 74.0% (+0.5%). Adding A1 (all five): 75.0% (+1.0%). The cumulative gain from the full action space over the RAP baseline is +4.5 percentage points, and each addition produces a monotonic improvement. The table demonstrates that each action type contributes independently — they are not redundant — and that the diversity they provide translates to measurable accuracy gains.

Practical implications of the action space. On any given problem, the MCTS exploration will naturally favor certain actions over others based on the reward signal: actions that consistently lead to correct terminal nodes will receive higher Q-values (see next subsection) and be selected more frequently. This means the tree adaptively allocates its exploration budget across action types depending on what works for the specific problem, without requiring a pre-programmed strategy. On a simple arithmetic problem, A2 ("propose remaining thought steps") might dominate because it efficiently produces correct answers; on a complex multi-constraint problem, A3 (decomposition into sub-questions) and A5 (rephrasing) might be preferentially explored because they handle complexity better; on problems where initial answers are often slightly wrong, A4 (re-answering) provides a correction mechanism.

The Reward Function: Contribution-Based Scoring Without Self-Evaluation

The second critical component of the MCTS generator is the reward function, which assigns a scalar value to each node in the search tree to guide future expansions. This is where rStar makes its most decisive break from prior work (Section 3.2).

Design principle: exclude self-rewarding. The paper states this explicitly: "First, we exclude self-rewarding techniques for any intermediate nodes due to the limited capabilities of SLMs" (Section 3.2). This is the direct operationalization of the finding in Appendix A.1 that SLMs perform near-random self-evaluation. Any reward function that asks the model to judge the quality of its own intermediate steps would inject noise into the search process, potentially steering it toward arbitrary branches that happen to receive high (but meaningless) self-scores.

Design principle: avoid external supervision. The second constraint is: "to ensure generalization across different reasoning tasks, we avoid introducing external supervision (e.g., tools or trained value models)" (Section 3.2). This means no trained reward models (which would require per-task labeled data and risk overfitting) and no external tools like calculators or code executors (which would limit applicability to tasks where such tools exist). The reward signal must be derived purely from the MCTS process itself using only the base SLM.

The contribution-based reward scheme. The paper draws an analogy to AlphaGo (Silver et al., 2017): "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." This is a retrospective reward — nodes are not scored when they are created (forward-looking self-evaluation) but rather when their downstream consequences become known (backward-looking contribution measurement).

Reward definition. For each node $s$ generated under action $a$ , define $Q(s, a)$ as the cumulative reward value that will guide future selection. Initially, for all unexplored nodes, $Q(s_i, a_i) = 0$ . This initial zero value means that unexplored nodes have no inherent preference — the search is driven purely by the exploration term in the UCT formula (see below) until terminal feedback arrives.

When the search reaches a terminal node $s_d$ (either because a final answer has been produced or because the maximum tree depth $d$ has been reached), the system computes the terminal node's reward $Q(s_d, a_d)$ . The paper specifies: "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" (Section 3.2).

What does "likelihood (confidence) of self-consistency majority voting" mean? During the simulation phase of MCTS (described in the next subsection), the system performs multiple rollouts from each node. For a terminal node, these rollouts involve sampling independent completions (or answer extractions) and checking what final answer is produced. The confidence score is the fraction of rollouts that produce the majority answer — essentially, how consistently the model arrives at the same final answer when sampling from the terminal state. If all rollouts agree (confidence = 1.0), the terminal node's answer is considered highly reliable; if rollouts disagree (confidence near 0.5), the answer is considered uncertain. Formally, if the majority answer appears in $k$ out of $n$ rollouts, then:

$Q(s_d, a_d) = \frac{k}{n}$

where $k$ is the count of rollouts producing the majority-vote answer and $n$ is the total number of rollouts performed at the terminal node.

Back-propagation. Once the terminal reward is computed, it is propagated backward along the trajectory $t = x \oplus s_1 \oplus s_2 \oplus \dots \oplus s_d$ from the terminal node to the root. For each intermediate node $s_i$ (for $i = 1, 2, \dots, d-1$ ), the update rule is:

$Q(s_i, a_i) \leftarrow Q(s_i, a_i) + Q(s_d, a_d)$

where $Q(s_d, a_d)$ is the terminal node's reward computed as above.

What this update means operationally. Each intermediate node accumulates the rewards of all terminal nodes that are reachable from it through subsequent MCTS rollouts. If a node $s_i$ is on the path to many terminal nodes that achieve high confidence scores, its $Q(s_i, a_i)$ grows large. If it only leads to low-confidence terminal nodes, its $Q$ value stays small. The absolute magnitude of $Q(s_i, a_i)$ reflects both the frequency with which paths through $s_i$ are explored and the quality (confidence) of the terminal nodes those paths reach.

Why this form works for SLMs where self-rewarding fails. The critical property is that $Q(s_d, a_d)$ is computed without asking the SLM to judge its own reasoning steps. Instead, it measures an observable, behavioral signal: when the model samples repeatedly from this terminal state, does it consistently produce the same answer? High consistency suggests the model has reached a stable conclusion; low consistency suggests uncertainty or contradictory reasoning. This signal correlates imperfectly but usefully with actual correctness — it leverages the fact that correct mathematical reasoning tends to be more deterministic (once you have the right setup, the answer follows) while incorrect reasoning tends to produce inconsistent outputs across samples.

Moreover, the back-propagation mechanism means that intermediate steps are judged by their consequences rather than their face plausibility. A step that seems odd but consistently leads to correct, high-confidence answers will accumulate high $Q$ value; a step that appears reasonable but leads to low-confidence or inconsistent answers will not. This is analogous to credit assignment in reinforcement learning: actions are valued based on the long-term outcomes they enable, not on immediate appearance.

Contrast with RAP's self-rewarding. RAP's reward for intermediate nodes is $r = r_1 \times r_2$ , where $r_1$ is the model's self-evaluated helpfulness of the proposed sub-question ("Is the new question useful?") and $r_2$ is the self-consistency confidence of the sub-question's answer. The paper showed that $r_1$ is effectively random (Table 6), meaning RAP's reward is dominated by noise. rStar eliminates the $r_1$ term entirely and uses only the behavioral consistency signal $r_2$ , but applies it at terminal nodes rather than intermediate nodes. The back-propagation mechanism then distributes this signal backward, so intermediate nodes still receive reward information — but the information comes from measured outcomes rather than self-assessed quality.

Why terminal-only reward with back-propagation works. A potential concern is that back-propagating from terminal nodes provides a sparse and delayed reward signal — intermediate nodes may be explored many times before any terminal feedback arrives. The MCTS framework handles this naturally through the exploration term in UCT (discussed next), which ensures that unvisited nodes are explored regardless of their initially zero $Q$ values. As more rollouts are performed, the accumulated $Q$ values for nodes on successful paths become large enough to dominate the exploration term, shifting the search from exploration to exploitation. This is exactly the standard MCTS dynamic, and it works as long as the terminal reward signal is informative (which the self-consistency confidence partially provides, as shown by the Table 6 result that replacing $r_2$ with random values does cause accuracy drops).

MCTS Rollout: Selection, Expansion, Simulation, and Back-Propagation

With the action space and reward function defined, the MCTS search procedure follows the standard four-phase loop adapted to the language model setting (Section 3.2). The paper provides a high-level description; here we reconstruct the detailed mechanics.

Initialization. The search tree root is the question node $s_0 = x$ . The tree initially contains only this node. The action space is the set $\{A_1, A_2, A_3, A_4, A_5\}$ , with ordering constraints enforced at each node.

Multiple rollouts. The paper specifies "we perform multiple searches consisting of selection, expansion, simulations and back-propagation" and "to achieve more accurate reward estimation, we perform multiple rollouts" (Section 3.2). The total number of rollouts is a hyperparameter: the paper uses 32 rollouts for most experiments (Section 4.1), meaning the four-phase cycle repeats 32 times per question, each time adding new nodes or updating existing ones. The ablation in Figure 5 shows that performance improves with more rollouts, from 2 up to 32, with diminishing returns at higher counts for some models.

Phase 1: Selection (traversing the tree to find a node to expand). Starting from the root, the algorithm recursively selects child nodes using the Upper Confidence Bound applied to Trees (UCT) formula until it reaches a node that has unexplored children (i.e., not all actions have been attempted at that node) or a terminal node.

The UCT formula is given as:

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

where:

$N(s, a)$ is the number of times node $s$ (generated under action $a$ ) has been visited in previous iterations (including the current selection pass).
$N_{\text{parent}}(s)$ is the total number of times the parent node of $s$ has been visited.
$Q(s, a)$ is the cumulative reward value for node $s$ under action $a$ , updated via back-propagation as described in the previous subsection.
$c$ is a constant that balances exploration and exploitation. The paper does not specify the exact value of $c$ ; this is typically tuned as a hyperparameter or set to a standard default (e.g., $\sqrt{2}$ in the original UCT formulation).

What UCT computes. The first term $\frac{Q(s, a)}{N(s, a)}$ is the average reward per visit for node $s$ — a measure of how "good" this node has been historically (exploitation). The second term $c \sqrt{\frac{\ln N_{\text{parent}}(s)}{N(s, a)}}$ is the exploration bonus — it is large when $s$ has been visited few times relative to its parent, encouraging the search to try less-visited branches. The sum balances these two forces: at each decision point, the algorithm selects the child that maximizes the UCT value.

Why this formulation. The UCT formula is the standard approach in MCTS (Kocsis & Szepesvári, 2006) because it provably balances exploration and exploitation in the limit (the regret grows logarithmically with the number of trials). The exploration term has the specific form $c\sqrt{\ln(N_{\text{parent}})/N}$ because this arises from the Hoeffding inequality bound on the uncertainty of the estimated average reward — nodes visited fewer times have higher uncertainty, so the optimistic upper bound is higher. This is what makes MCTS systematically explore the tree rather than repeatedly exploiting the first moderately good path it finds. For rStar, this is critical because the initial zero $Q$ values provide no exploitation signal — the first several rollouts are driven almost entirely by the exploration term, ensuring broad coverage of the action space before the search narrows to high-reward regions.

Phase 2: Expansion (adding new nodes). When the selection phase reaches a node that has not been fully expanded (i.e., there are actions in the available action set that have not yet been tried at this node), the algorithm selects one such untried action $a$ , prompts the SLM with the current reasoning state and the prompt template for $a$ , and generates the next reasoning step $s_{\text{new}}$ . This creates a new child node, which is added to the tree. The new node's $Q$ value is initialized to $0$ and its visit count $N$ to $0$ (or $1$ if counting the current visit).

The maximum tree depth $d$ is a hyperparameter: $d = 5$ for most tasks, $d = 8$ for MATH (Section 4.1). The paper also specifies: "Actions A1 and A3 have a maximum of 5 nodes per depth, while the other actions have a default node count of 1" (Section 4.1). This means that at any given depth, A1 and A3 can be branched up to 5 times (generating up to 5 alternative steps at that point), while A2, A4, and A5 produce only a single child per node — which makes sense since A2 generates all remaining steps at once (so further branching at that depth is unnecessary) and A4/A5 are corrective actions that typically need only one alternative.

Phase 3: Simulation (rollout to estimate value). From the newly expanded node $s_{\text{new}}$ , the algorithm performs a rollout to reach a terminal node and obtain a reward estimate. The paper states that "the simulation is performed using the default rollout policy" (Section 3.2). The "default rollout policy" refers to a fast, computationally cheap strategy for completing the reasoning from the current state to a final answer — likely using the same SLM with a standard prompting approach (perhaps the A2 "propose remaining thought steps" action, which produces a complete solution in one generation) rather than recursively applying the full tree search at deeper levels. The paper uses "multiple rollouts" to get a more accurate reward estimate — instead of a single completion from $s_{\text{new}}$ , the system samples multiple independent completions, each reaching a terminal node with its own answer.

At the terminal node (reached via the rollout policy), the reward $Q(s_d, a_d)$ is computed as the self-consistency confidence:

$Q(s_d, a_d) = \frac{\text{count of rollouts producing the majority answer}}{\text{total number of rollouts}}$

Phase 4: Back-propagation (updating ancestor nodes). The terminal reward is propagated backward along the path taken during selection and expansion. For each node $s_i$ on that path, including the newly expanded node:

$Q(s_i, a_i) \leftarrow Q(s_i, a_i) + Q(s_d, a_d)$

$N(s_i, a_i) \leftarrow N(s_i, a_i) + 1$

The $N$ increments track the number of times each node has been part of a completed trajectory, which feeds into the UCT formula's exploration term for future selection phases.

Candidate trajectory collection. After all 32 rollouts are complete, the search tree contains multiple complete paths from root to terminal nodes, as well as many partial paths. The paper states: "We collect all trajectories from the rollout iterations as candidate solutions" (Section 3.2). Specifically, any path that reaches a terminal node (final answer produced, or maximum depth reached) during any of the 32 rollouts is extracted as a candidate trajectory $t_i$ . The set of all such trajectories is $\mathbb{T} = \{t_1, t_2, \dots, t_n\}$ .

Why not select a single "best" trajectory from MCTS. The paper notes: "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" (Section 3.3). This is an important empirical observation: the reward signal from MCTS, while useful for guiding search, is not reliable enough to directly pick the correct trajectory from the candidate set. This motivates the second stage of rStar — the discriminator — which provides an independent verification signal.

Mutual Reasoning Consistency: The Discriminator Mechanism

The discriminator is the second SLM, denoted $\hat{M}$ , which provides unsupervised external feedback on each candidate trajectory generated by the MCTS (Section 3.3). The paper's default discriminator is Phi3-mini-4k (3.8B parameters), chosen for its light weight. The discriminator is used zero-shot — it receives no task-specific training or fine-tuning, and operates purely through the prompting mechanism described below.

The core insight: partial hint + independent completion. The key idea is that if two independent models arrive at the same answer when one is given the other's reasoning prefix as a hint, then the answer is more likely to be correct. This is not because either model is particularly reliable on its own (they are both weak SLMs), but because their errors are likely to be uncorrelated — they make different mistakes for different reasons, so agreement is informative.

Discrimination procedure for a single trajectory. For a candidate trajectory $t = x \oplus s_1 \oplus s_2 \oplus \dots \oplus s_d$ produced by the generator $M$ :

Random split point. The system randomly samples a split index $i$ such that $i < d$ (the split comes before the final step). The paper specifies: "we randomly split it between 20% and 80% of its steps" (Section 4.1). This means the split point is chosen uniformly from the range $[\lceil 0.2d \rceil, \lfloor 0.8d \rfloor]$ , ensuring that the discriminator receives a substantial prefix (at least 20% of the reasoning) but must still complete a meaningful portion of the remaining reasoning (at least 20% of the steps are masked).
Prefix extraction. The system extracts the prefix $\hat{t} = x \oplus s_1 \oplus s_2 \oplus \dots \oplus s_{i-1}$ — the original question plus the first $i-1$ reasoning steps.
Discriminator completion. The prefix $\hat{t}$ is provided as a prompt to the discriminator SLM $\hat{M}$ , which is asked to complete the remaining reasoning steps and produce a final answer. The paper's Figure 4 shows an example prompt: the discriminator receives "the earlier reasoning trajectory" (the prefix of steps) and is asked to answer the question. By providing the initial reasoning steps as context, the system reduces the difficulty of the problem for the discriminator: it doesn't have to start from scratch, but can build on the already-established reasoning structure.
Answer comparison. The discriminator's completed answer is compared to the original trajectory $t$ 's final answer (from $s_d$ ). If they match, the trajectory $t$ is considered validated (mutually consistent). If they differ, $t$ is rejected.

Why partial hints work. The paper explains this with a human analogy: "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" (Section 3.3).

The statistical rationale is more subtle. If the generating model's trajectory is correct, then providing the correct initial steps as a hint makes it easier for the discriminator to reach the correct final answer — the discriminator has lower probability of error because part of the reasoning is already done. If the trajectory is incorrect (the initial steps contain reasoning errors), the discriminator may still reach a different answer, either because it follows the flawed reasoning to a different (incorrect) conclusion, or because it recognizes an error and corrects it (producing the right answer, which will differ from the wrong answer in the original trajectory). In either case, disagreement flags the trajectory as suspect.

The crucial property is that the discriminator is not asked to judge the trajectory (which would require self-evaluation capabilities that SLMs lack). Instead, it is asked to produce its own answer given partial context. The judgment (consistent or not) emerges from comparing two independently generated answers, not from a direct assessment of reasoning quality.

Why random split points (20–80%). The choice of random split points serves two purposes: (1) it prevents the discriminator from exploiting the same hint structure across all trajectories (which could create systematic biases), and (2) it ensures that the discriminator is tested across varying levels of hint completeness, from minimal hints (20% of steps revealed) to substantial hints (80% revealed). If the mutual consistency signal were systematically weaker for certain split ranges (e.g., when very little context is provided, the discriminator may struggle regardless), the randomization averages over these effects rather than conditioning on a fixed, potentially suboptimal split.

The discriminator model choice (Table 5, right). The paper experiments with different discriminator models: using LLaMA3-8B-Instruct as both generator and discriminator achieves 88.70% accuracy (baseline with majority voting), while using LLaMA3.1-8B-Instruct as discriminator yields 89.52%, Phi3-Mini-Instruct yields 91.13%, and GPT-4 yields 92.57%. The key finding is that the choice of discriminator model "generally does not affect the effectiveness" (Section 4.2) — even the 3.8B Phi3 model (the smallest tested) works effectively, and scaling up to GPT-4 provides only a small incremental gain (91.13% → 92.57%). This is important because it means the mutual consistency mechanism does not depend on the discriminator being strong, only on it being different from the generator (having uncorrelated errors). When Phi3 is the target SLM (meaning generator = discriminator), the system performs "self-discrimination" — the same model serves both roles, but presumably its errors across independently generated completions are sufficiently uncorrelated for the mechanism to still provide a useful signal (the paper does not explicitly analyze this case, but Table 2 shows Phi3-mini achieves strong results with rStar).

Why mutual consistency outperforms self-verification (Table 5, left). The paper directly compares discriminators: for LLaMA3-8B's MCTS-generated trajectories, mutual consistency (rStar discriminator) achieves 85.52% accuracy versus 75.52% for self-verification (where the generator model checks its own trajectories). This 10-percentage-point gap demonstrates that having an independent model verify is substantially more effective than having the same model introspect — consistent with the paper's thesis that SLM self-assessment is unreliable.

Parallelized verification. The paper notes that "the discriminator performs inference in a parallelized manner, making the verification process highly efficient" (Section 4.1). Since each candidate trajectory's verification is independent of the others, all discriminator calls can be batched or run concurrently, meaning the wall-clock time for discrimination scales sub-linearly with the number of candidate trajectories.

Final Trajectory Selection

After the discriminator has produced a set of validated trajectories (those deemed mutually consistent), the system must select a single final answer. The paper specifies a scoring mechanism (Section 3.3):

Score computation. For each validated trajectory, the system computes:

$\text{final\_score}(t) = Q_{\text{trajectory}}(t) \times \text{confidence}_{\text{terminal}}(t)$

where:

$Q_{\text{trajectory}}(t)$ is the reward value associated with the trajectory from the MCTS process. The paper states: "We compute each trajectory's final score by multiplying its reward with the terminal node's confidence score achieved from rollouts." The trajectory's reward is the cumulative $Q$ value of the terminal node $s_d$ — specifically, the sum of all terminal rewards back-propagated to $s_d$ across all rollouts where $s_d$ was reached (or perhaps the average reward $\frac{Q(s_d, a_d)}{N(s_d, a_d)}$ , though the paper's wording suggests the raw $Q$ value).
$\text{confidence}_{\text{terminal}}(t)$ is the self-consistency confidence at the terminal node — the fraction of rollouts that produced the majority answer, as used in the reward computation.

Why multiply reward and confidence. The reward $Q$ reflects how frequently the trajectory's terminal node was reached and how high-quality those arrivals were (in aggregate, since $Q$ accumulates rewards from multiple rollouts). The confidence reflects how consistent the model is when sampling from that terminal state. Multiplying them combines two signals: a trajectory that is frequently reached with high confidence is preferred over one that is rarely reached or has low confidence. If either signal is zero (zero reward or zero confidence), the product is zero, effectively filtering out trajectories that the MCTS process judged unpromising.

Selection. "The trajectory with the highest final score is chosen as the solution" (Section 3.3). The generator SLM $M$ makes this final selection — it iterates through validated trajectories, computes the score for each, and picks the maximum.

Why the generator makes the final choice, not the discriminator. The discriminator's role is to filter — it eliminates trajectories where an independent model disagrees with the proposed answer. But the discriminator does not rank the surviving trajectories; it only provides a binary validation signal. The final selection among validated trajectories falls back to the generator's MCTS-derived scores, which encode information about search reliability (how consistently certain reasoning paths lead to high-confidence answers) that the discriminator does not capture. This division of labor — discriminator for filtering, generator for ranking — ensures that each component contributes its comparative advantage.

Summary of Design Choices and Their Justifications

Five-action MCTS over single-action MCTS (RAP): The ablations in Table 1 show that each action contributes to accuracy, and a diverse action space allows the search to adapt its strategy to problem characteristics rather than being constrained to a single decomposition pattern. This is the primary driver of the generator's improved trajectory quality over RAP (Table 4: rStar generator achieves 74.38% vs. RAP's 56.56% on LLaMA3-8B GSM8K, using majority voting for both).
Contribution-based retrospective reward over self-evaluated reward: SLM self-evaluation is near-random (Appendix A.1, Table 6), so any reward function that asks the model to assess its own intermediate steps is inherently noisy. The retrospective reward uses an observable behavioral signal (self-consistency confidence at terminal nodes) and back-propagates it — the signal comes from actual outcomes, not from the model's (unreliable) introspection. Table 4 shows that adding self-evaluation to rStar's generator reduces accuracy (70.28% vs. 74.38% on LLaMA3-8B GSM8K), confirming that even with a strong generator, self-evaluation hurts rather than helps.
Mutual consistency over self-verification or majority voting: Self-verification requires the model to judge its own outputs — which SLMs cannot do reliably (Table 5: self-verification achieves 75.52% vs. rStar discriminator's 85.52% on LLaMA3-8B GSM8K). Majority voting requires the correct answer to be the mode of the output distribution — which fails for weak models where most outputs are incorrect (Table 2: SC@128 achieves only 23.05% on LLaMA2-7B GSM8K). Mutual consistency avoids both pitfalls: it uses a second independent model (so errors are uncorrelated) and it checks for agreement rather than counting votes (so a minority-correct answer can still be selected if the discriminator independently arrives at it).
Discriminator as untrained peer rather than trained reward model: Trained reward models require labeled training data (reintroducing the teacher dependency) and risk overfitting to specific tasks. The discriminator is used zero-shot, requires no training, and the experiments show it transfers across tasks (it works on GSM8K, GSM-Hard, MATH, SVAMP, and StrategyQA without task-specific adaptation). Table 5 (right) shows the discriminator is effective across different model choices, confirming robustness.
Parallelized discriminator for efficiency: By verifying each trajectory independently, the discriminator calls can be batched, keeping inference overhead manageable despite the two-model architecture. The paper reports that solving a GSM8K question averages 166 model calls for LLaMA2-7B and 148 for Mistral-7B (Table 7), taking about 4.5 days on a single A100 GPU for the full test set — costly but not prohibitive, and amenable to parallelization across GPUs.

4. Key Insights and Innovations

Innovation 1: SLM Reasoning Failure Is a Verification Problem, Not (Primarily) a Knowledge Problem

The paper's most fundamental intellectual move is reframing why small language models fail at reasoning. The dominant assumption in the field — implicit in the widespread reliance on GPT-4-distilled fine-tuning data (Wang et al., 2024a; Gou et al., 2023) — is that SLMs lack the knowledge to reason correctly, and that this knowledge must be injected through supervised training on high-quality reasoning traces. rStar challenges this assumption directly, proposing instead that the bottleneck is generation reliability and answer verification: SLMs already possess sufficient knowledge from pretraining to solve many reasoning problems, but they cannot reliably access that knowledge through standard generation (most sampled trajectories are wrong) and cannot reliably recognize correctness when they stumble upon it (self-evaluation is near-random).

This reframing has profound implications. If SLM reasoning weakness is a knowledge deficit, the only solution is more or better training — scaling pretraining, fine-tuning on distilled data, or waiting for larger models. But if it is a generation-and-verification bottleneck, then inference-time techniques — better search strategies, better answer selection mechanisms — can unlock latent capabilities without any new knowledge injection. The paper's results provide compelling evidence for the latter view: rStar on LLaMA2-7B achieves 63.91% GSM8K accuracy (Table 2), nearly matching the ~66% achieved by MetaMath fine-tuning (Figure 1), despite adding no new training data. On Mistral-7B, rStar's 81.88% exceeds fine-tuned MetaMath's 77.7%, suggesting the fine-tuned model actually underutilized some of the base model's pretrained reasoning capacity.

What makes this framing distinctive is not the claim itself — the idea that LLMs "know more than they can say" is familiar from prompting research — but the empirical operationalization through negative results. The paper doesn't merely assert that self-evaluation is unreliable; it demonstrates that SLM self-assessment of reasoning step helpfulness is statistically indistinguishable from random (Appendix A.1, Table 6: replacing RAP's self-evaluated r1 with random values changes GSM8K accuracy for LLaMA2-7B from 24.34% to 22.90%). This is not "SLMs are somewhat unreliable at self-assessment" — it is "SLM self-assessment provides no usable signal whatsoever." The corollary — that any method relying on an SLM to score its own intermediate reasoning steps is building on sand — is the organizing principle behind every design choice in rStar, from the elimination of self-evaluation in the reward function to the use of a separate discriminator model. This negative result is arguably the paper's most important single contribution, because it identifies a bright-line constraint that any future SLM reasoning method must respect: do not ask small models to judge their own intermediate outputs.

Innovation 2: Mutual Consistency as an Unsupervised Correctness Signal for Weak Models

The field has converged on two dominant paradigms for answer verification in multi-sample reasoning: majority voting (self-consistency; Wang et al., 2023) and trained reward models (Cobbe et al., 2021; Lightman et al., 2023; Wang et al., 2024b). Both have known failure modes for weak models. Majority voting requires the correct answer to be the mode of the output distribution — it fails when pass@1 is low because the majority is wrong by construction (as seen in Table 2: SC@128 on LLaMA2-7B GSM8K reaches only 23.05% accuracy, barely above the 12.51% few-shot CoT baseline). Trained reward models require labeled training data, reintroducing the teacher dependency that rStar is designed to avoid, and risk overfitting to specific tasks and data distributions.

rStar introduces a third paradigm: mutual reasoning consistency, where a second, independent SLM verifies candidate trajectories not by judging them directly but by completing a partially-masked version of the same reasoning path and checking whether it arrives at the same answer (Section 3.3). This is conceptually distinct from both majority voting and trained verifiers. It is not voting — a single dissenting opinion from the discriminator can invalidate a trajectory, even if every other sample agrees. And it requires no training — the discriminator operates zero-shot through prompting.

The intellectual innovation is the recognition that two weak models with uncorrelated errors can provide a stronger verification signal than either model alone, even though neither model is reliable individually. This is a form of weak supervision through independence: if the generator's trajectory is incorrect, the discriminator — given the same (potentially flawed) reasoning prefix — is unlikely to independently reproduce exactly the same wrong answer, because the two models make different kinds of mistakes. Conversely, if the trajectory is correct, providing the correct prefix makes the discriminator's completion task easier, increasing the probability it reaches the same answer. Agreement thus carries information about correctness, despite both models being weak.

This framing is novel because it inverts the usual approach to verification. Rather than trying to make a single verifier strong enough to judge outputs directly (which, for SLMs, the paper has shown is infeasible through self-evaluation), rStar makes verification an emergent property of a two-model system. The key evidence that this works comes from Table 5 (right): when Phi3-mini (3.8B parameters) serves as discriminator for LLaMA3-8B-Instruct, accuracy reaches 91.13%; replacing it with GPT-4 (a vastly stronger model) improves accuracy only marginally to 92.57%. The discriminator doesn't need to be strong — it needs to be different. This is a fundamentally different design philosophy from the "train a better verifier" approach, and it suggests a research direction where verification emerges from model ensembles with uncorrelated error patterns rather than from increasingly sophisticated individual verifiers.

Innovation 3: Action-Space Diversity as the Driver of MCTS Effectiveness (Not the Search Algorithm Itself)

Prior MCTS-based reasoning methods for LLMs (RAP by Hao et al., 2023; AlphaMath by Chen et al., 2024a; MindStar by Kang et al., 2024) share a common architecture: MCTS search over a single action type — either "propose next sub-question" or "generate next reasoning step." The implicit assumption is that the search algorithm's exploration-exploitation dynamics are the primary source of improvement, with the action space being merely the atomic operation that the search orchestrates. The paper challenges this assumption by showing that the action space itself — not the search algorithm wrapped around it — may be the dominant factor in trajectory quality.

The evidence is in Table 1: starting from the RAP baseline (A3 only, 70.5% accuracy on 200 sampled GSM8K questions with LLaMA3-8B), each new action type added to the space produces a monotonic improvement — +2.0% for A5 (rephrasing), +1.0% for A4 (re-answering sub-questions), +0.5% for A2 (propose remaining thoughts), +1.0% for A1 (one-step thought) — for a total gain of +4.5 percentage points. These gains come from enriching the action space, not from improving the search algorithm (the MCTS procedure is held constant across all conditions). The paper's framing — that humans use diverse reasoning actions adaptively, and that a single-action MCTS constrains the system to "a solution space with low-quality reasoning steps even after many attempts" (Section 1) — positions action-space diversity as a first-class design dimension, not an afterthought.

What makes this more than an incremental engineering improvement is the conceptual implication: the search algorithm matters less than what the model is allowed to do at each step. This suggests that future work on LLM reasoning tree search should focus on action-space design (what reasoning primitives to include, how they interact, whether they should be learned rather than hand-specified) rather than on increasingly sophisticated search algorithms. The paper's negative result with lookahead-style search (implicit in the contrast between rStar's rich-action MCTS and RAP's single-action MCTS, where RAP saturates or degrades after 4 rollouts in Figure 5) further supports this: more compute-intensive search over a narrow action space is less effective than simpler search over a rich action space.

This is a subtle but important shift in how to think about LLM reasoning architectures. The field has largely treated the search algorithm as the "intelligent" component and the action space as a fixed, low-level primitive. rStar inverts this: the diversity and quality of reasoning primitives is the primary lever for capability improvement, with the search algorithm serving as a resource-allocation mechanism that directs compute toward the most promising primitives per problem.

Innovation 4: The Generator-Discriminator Self-Play Framework as an Alternative to Self-Training

The paper's highest-level architectural contribution is the self-play mutual reasoning framework — a generator that produces candidate solutions via MCTS, and a discriminator that filters those solutions via mutual consistency, with the generator then selecting the final answer from validated candidates. This is not self-play in the game-theoretic sense (the models are not iteratively improving each other through competition), but rather a division of labor between generation and verification where both components are weak models working cooperatively.

The significance of this framework lies in what it replaces. The dominant paradigm for improving LLM reasoning without human labels has been self-training — the model generates solutions, some selection mechanism identifies high-quality ones (via heuristics, verifier scores, or ground-truth checks on a subset), and the model is fine-tuned on those solutions (STaR by Zelikman et al., 2022; ReST $^{\text{EM}}$ by Singh et al., 2024; self-play fine-tuning by Chen et al., 2024b). Self-training requires multiple rounds of generation and fine-tuning, making it computationally expensive and introducing risks of distributional collapse (the model amplifies its own biases over successive rounds).

rStar demonstrates that a single inference-time pass through a generator-discriminator pipeline can achieve accuracy gains comparable to fine-tuning — without any parameter updates. Table 2 shows rStar boosting LLaMA2-7B GSM8K from 12.51% (few-shot CoT) to 63.91%; Figure 1 shows MetaMath fine-tuning reaches ~66%. The generator-discriminator approach achieves this in one inference cycle per question (32 rollouts of MCTS plus parallel discriminator calls), avoiding the iterative training overhead and the distributional shift risks of self-training. The paper's Appendix K (implicitly referenced via the ReST $^{\text{EM}}$ discussion in the prior analysis) suggests that self-training can actually degrade SLM reasoning performance, further strengthening the case for inference-time solutions over training-time ones when working with weak models.

Conceptually, this framework separates two problems that self-training conflates: trajectory generation (exploring the solution space) and trajectory selection (identifying which solutions are correct). By assigning these to different models with different mechanisms (MCTS with diverse actions for generation; mutual consistency for verification), rStar allows each component to be optimized independently. The generator's design choices (action space, reward function, tree depth) are driven purely by what maximizes the probability of producing at least one correct trajectory somewhere in the candidate set. The discriminator's design choices (split point, model choice, prompting strategy) are driven purely by what maximizes the signal-to-noise ratio of the verification signal. This modularity is a practical engineering advantage, but it also represents a conceptual advance: it suggests that generation quality and verification quality are separable axes of improvement for SLM reasoning, and that pursuing them independently (rather than trying to optimize a single model to do both well, as self-training does) is both more effective and more tractable for weak models.

The framework also has a pragmatic implication that the paper doesn't fully articulate but that emerges from the results: it suggests a deployment architecture where any available small model can serve as discriminator for any other. Table 5 (right) shows that Phi3-mini (3.8B) works effectively as discriminator for LLaMA3-8B-Instruct, and GPT-4 provides only marginal improvement. This means the discriminator can be the cheapest available model that is architecturally different from the generator — enabling reasoning improvement even in highly resource-constrained settings where only small models are available. The mutual consistency mechanism effectively converts model diversity (the fact that different SLMs make different errors) into a verification signal, which is a genuinely new way to think about the value of model ensembles for reasoning tasks.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on five reasoning benchmarks: GSM8K (Cobbe et al., 2021), a grade-school math word problem dataset with approximately 1,319 test questions; GSM-Hard (Gao et al., 2022), a harder variant of GSM8K; MATH-500 (Hendrycks et al., 2021; Lightman et al., 2023), a 500-question subset of competition-level math problems from the MATH benchmark; SVAMP (Patel et al., 2021), a set of elementary math word problems with structural variations; and StrategyQA (Geva et al., 2021), a commonsense reasoning benchmark requiring implicit multi-step inference with boolean (yes/no) answers. The paper does not explicitly state the test-set sizes for GSM-Hard, SVAMP, and StrategyQA.
Base model(s). Five small language models are evaluated: Phi3-mini (3.8B) (Abdin et al., 2024), LLaMA2-7B (the least capable, serving as the primary stress test), Mistral-7B (Jiang et al., 2023), LLaMA3-8B, and LLaMA3-8B-Instruct (Meta, 2024). These span a range of base capabilities — from LLaMA2-7B's 12.51% few-shot CoT on GSM8K to Phi3-mini's 83.45% — and represent the class of models deployable on-device or in resource-constrained environments. The key criterion for inclusion is that all are models for which standard self-improvement techniques (self-refinement, self-verification) are known to be unreliable, making them appropriate testbeds for rStar's approach.
Metrics. The sole evaluation metric across all experiments is accuracy — the fraction of test questions for which the system's selected final answer matches the ground-truth answer exactly. For mathematical datasets (GSM8K, GSM-Hard, MATH, SVAMP), accuracy is computed via exact numeric answer matching. For StrategyQA, it is boolean yes/no matching. The paper reports no other metrics (e.g., calibration, confidence scores, inference cost as FLOPs, or latency).
Baselines. Three categories of baselines are compared:
- Single-round CoT prompting: zero-shot CoT (Kojima et al., 2022) and few-shot CoT (Wei et al., 2022). These establish the floor for each model's raw reasoning capability.
- Multi-round self-consistency (SC): SC@maj8, SC@maj64, and SC@maj128 (Wang et al., 2023), which sample 8, 64, or 128 independent CoT solutions and select the most common final answer via majority voting. These test whether simple repeated sampling can recover correct answers when single-round accuracy is low.
- Multi-round self-improvement methods: ToT (Tree of Thoughts; Yao et al., 2024), using BFS tree search with an action space corresponding to A1 ("propose one-step thought"); and RAP (Reasoning via Planning; Hao et al., 2023), using MCTS with an action space corresponding to A3 ("propose next sub-question"). Both follow their original implementations for answer selection.
Additionally, the paper reports an intermediate variant rStar (generator @maj) — trajectories from rStar's MCTS generator selected via majority voting rather than the mutual consistency discriminator — to isolate the generator's contribution from the discriminator's.
Generation budget / compute accounting. The primary compute budget measurement for rStar is number of MCTS rollouts, with 32 rollouts used as the default for all main experiments (Section 4.1). Each rollout involves one full MCTS cycle (selection, expansion, simulation, back-propagation), which may trigger multiple SLM calls for node expansion and terminal reward estimation. The paper does not standardize compute accounting across baselines in a budget-equivalent manner: self-consistency baselines are evaluated at fixed sample counts (8, 64, 128) rather than matched to rStar's total generation count, and tree-search baselines (RAP, ToT) also use their own MCTS/BFS configurations without a unified FLOPs budget comparison. The paper reports average inference counts: 166 model calls per question for LLaMA2-7B and 149 for Mistral-7B on GSM8K (Table 7), with approximately 367k and 349k generated tokens per question respectively. These numbers are provided for transparency but are not used to calibrate baseline comparisons. For the discriminator, inference is parallelized across trajectories, but the paper does not report discriminator call counts or token budgets.
Cross-validation / statistical protocol. The paper does not employ cross-validation or report statistical significance measures (confidence intervals, standard deviations, or hypothesis tests) for any main results. Accuracy is reported as a point estimate on the full test set. Ablation studies (Tables 1, 4, 5 left) use the full test sets of the respective benchmarks (or 200 sampled questions for Table 1's GSM8K ablation) without held-out validation folds. The tree depth and maximum nodes per depth (d = 5 for most tasks, d = 8 for MATH; max 5 nodes per depth for A1 and A3, max 1 for A2, A4, A5) are stated as fixed hyperparameters in Section 4.1 without indicating whether they were tuned on a validation set or set a priori.

Main Quantitative Results

Aggregate Performance Across Five Models and Five Benchmarks (Table 2)

The headline result is that rStar substantially and consistently improves reasoning accuracy across all five SLMs and all five benchmarks, with the largest absolute gains occurring for the weakest models. Table 2 presents the complete matrix.

GSM8K results. rStar raises LLaMA2-7B from 12.51% (few-shot CoT) to 63.91% — a 51.4 percentage point absolute gain, representing more than a 5× relative improvement. For Mistral-7B, accuracy increases from 36.46% to 81.88%. For LLaMA3-8B, from 47.23% to 85.52%. For LLaMA3-8B-Instruct, from 74.53% to 91.13%. For Phi3-mini, from 83.45% to 90.67%. The most dramatic gains are on the weakest models, consistent with the paper's thesis that these models already possess reasoning capability but cannot reliably access it through standard generation.

Compared to the strongest single-approach baseline, SC@maj128, rStar outperforms it on every model: LLaMA2-7B (63.91% vs. 23.05%), Mistral-7B (81.88% vs. 57.25%), LLaMA3-8B (85.52% vs. 67.55%), LLaMA3-8B-Instruct (91.13% vs. 84.69%), and Phi3-mini (90.67% vs. 88.68%). The absolute gaps are largest for the weakest models (40.86 points for LLaMA2-7B, 24.63 points for Mistral-7B) and narrow for the already-strong models (6.44 points for LLaMA3-8B-Instruct, 1.99 points for Phi3-mini) — a pattern consistent with diminishing returns when base accuracy is already high.

GSM-Hard results. On this more challenging variant, rStar achieves accuracies of 18.57% (LLaMA2-7B), 37.91% (Mistral-7B), 32.97% (LLaMA3-8B), 37.53% (LLaMA3-8B-Instruct), and 46.55% (Phi3-mini). The improvement over SC@maj128 ranges from +11.68 points (LLaMA2-7B: 18.57% vs. 6.89%) to +12.90 points (Mistral-7B: 37.91% vs. 25.01%). On LLaMA3-8B-Instruct, the gain is +6.37 points (37.53% vs. 31.16%). These results demonstrate that rStar's gains are not limited to easy problems but extend to harder ones where the base pass@1 is lower — though the absolute accuracies remain modest, reflecting the dataset's difficulty.

SVAMP results. This is the easiest mathematical dataset, and base model performance is already fairly high. rStar achieves 74.90% (LLaMA2-7B, up from 48.10% few-shot CoT), 86.40% (Mistral-7B, up from 72.80%), 90.00% (LLaMA3-8B, up from 76.90%), 94.29% (LLaMA3-8B-Instruct, up from 89.20%), and 94.10% (Phi3-mini, up from 92.80%). The gains over SC@maj128 are +20.40, +9.80, +9.20, +3.69, and +0.40 points respectively — again largest for the weakest models.

StrategyQA results. This commonsense reasoning task differs from the mathematical benchmarks in that answers are boolean and reasoning involves implicit world knowledge rather than computation. rStar achieves 67.25% (LLaMA2-7B, up from 58.82% few-shot CoT), 70.31% (Mistral-7B, up from 65.65%), 67.69% (LLaMA3-8B, up from 64.05%), 71.57% (LLaMA3-8B-Instruct, up from 68.41%), and 67.25% (Phi3-mini, up from 63.61%). Critically, self-consistency degrades performance on StrategyQA for several models: SC@maj128 underperforms few-shot CoT on LLaMA2-7B (58.37% vs. 58.82%), LLaMA3-8B (63.31% vs. 64.05%), LLaMA3-8B-Instruct (66.67% vs. 68.41%), and Phi3-mini (59.53% vs. 63.61%). This is the key evidence that majority voting fails catastrophically when the model's output distribution is not concentrated on the correct answer — sampling more only adds noise. rStar avoids this failure mode because mutual consistency does not rely on the correct answer being the mode; it verifies individual trajectories through independent peer agreement. The paper explicitly highlights this: "SC with more sampling can even lower the score on StrategyQA" (Section 4.2).

Comparison to RAP and ToT baselines. Across all model-benchmark pairs, rStar outperforms RAP, and RAP generally outperforms ToT (which is often worse than single-round few-shot CoT). For example, on LLaMA2-7B GSM8K: rStar 63.91%, RAP 24.34%, ToT 12.96%. On Mistral-7B GSM8K: rStar 81.88%, RAP 56.25%, ToT 38.89%. The RAP-to-rStar gap is attributable to both the richer action space (rStar's generator alone, with majority voting, achieves 27.22% on LLaMA2-7B vs. RAP's 24.34% — Table 2, rStar (generator @maj) line) and the mutual consistency discriminator (which then lifts 27.22% to 63.91%). The ToT results are particularly weak, with ToT underperforming few-shot CoT on LLaMA3-8B GSM8K (36.01% vs. 47.23%) and LLaMA2-7B GSM8K (12.96% vs. 12.51% — essentially tied). This suggests BFS with a single action type is an actively harmful exploration strategy for weak models, likely because it expands many unpromising branches without a reliable scoring function to guide pruning.

MATH-500 Results (Table 3)

For the most challenging mathematical dataset, evaluations are limited to the instruction-tuned models (LLaMA3-8B-Instruct and Phi3-mini-4k) due to the extensive LaTeX formatting in MATH questions, which the paper notes is "challenging for pre-trained LLMs in instruction following" (Table 3 caption). rStar achieves 42.94% on LLaMA3-8B-Instruct (up from 17.80% few-shot CoT) and 48.60% on Phi3-mini (up from 32.20%). The gains over SC@maj128 are +9.14 points for LLaMA3-8B-Instruct (42.94% vs. 33.80%) and +3.00 points for Phi3-mini (48.60% vs. 45.60%).

The absolute accuracies remain far below GSM8K levels, consistent with MATH being a substantially harder benchmark requiring college-level mathematical knowledge. Notably, rStar (generator @maj) already outperforms all baselines: 38.30% for LLaMA3-8B-Instruct vs. SC@maj128's 33.80%, and 48.40% for Phi3-mini vs. SC@maj128's 45.60%. The discriminator adds +4.64 and +0.20 points respectively for the two models, indicating that on harder problems, the generator's trajectory quality is the binding constraint and discrimination yields smaller marginal gains. This is consistent with the intuition that when problems are difficult, the primary bottleneck is producing any correct trajectory, not selecting among candidates.

The Generator vs. Discriminator Contribution (Table 2, rStar line vs. rStar (generator @maj) line)

By comparing the full rStar accuracy to the generator-only (majority voting) accuracy, we can decompose the system's gains into generation quality and verification quality. The results are highly model-dependent:

LLaMA2-7B GSM8K: Generator contributes +14.71 points over few-shot CoT (12.51% → 27.22%), while discriminator adds +36.69 additional points (27.22% → 63.91%). The discriminator is the dominant component for this weakest model — the generator produces mostly wrong trajectories, but the discriminator reliably identifies the rare correct ones that majority voting would miss.
Mistral-7B GSM8K: Generator adds +28.13 points (36.46% → 64.59%), discriminator adds +17.29 points (64.59% → 81.88%). Both components contribute substantially, with the generator now providing a stronger base since Mistral produces a higher proportion of correct trajectories.
LLaMA3-8B-Instruct GSM8K: Generator adds +14.17 points (74.53% → 88.70%), discriminator adds +2.43 points (88.70% → 91.13%). For this stronger model, the generator is the primary driver — trajectory quality is already high, and verification provides only a small further boost.

This pattern — discriminator gains are inversely proportional to base model strength — is a natural consequence of the mutual consistency mechanism: when the generator already produces mostly correct trajectories, discrimination has less room to improve over majority voting (which also works well when correctness is the mode). When the generator's output is mostly incorrect, majority voting fails and the discriminator's ability to identify minority-correct trajectories becomes crucial. The paper acknowledges this directly in Appendix A.2: "The importance of the generator and discriminator varies based on the SLM's solution generation effectiveness."

Scaling with Number of Rollouts (Figure 5)

Figure 5 compares rStar, RAP, and self-consistency across rollout counts from 2 to 32 on two models (LLaMA3-8B and LLaMA3-8B-Instruct) for GSM8K. rStar achieves strong performance even at 2 rollouts — for LLaMA3-8B, rStar reaches approximately 75% at 2 rollouts compared to SC's roughly 57% and RAP's roughly 56%. As rollouts increase, rStar continues to improve: at 32 rollouts, rStar reaches approximately 87–88% on both models. In contrast, RAP saturates and declines after 4 rollouts on LLaMA3-8B-Instruct — dropping from its peak at 4 rollouts to a lower level at 32 rollouts, consistent with the paper's claim that "the single-type action space in RAP limits the effective MCTS exploration" (Figure 5 caption). SC scales more slowly than rStar, and at 32 rollouts it reaches approximately 67% for LLaMA3-8B and 84% for LLaMA3-8B-Instruct — well below rStar.

The RAP degradation with more rollouts is noteworthy: it suggests that increasing compute with a narrow action space can actually hurt performance, presumably because the MCTS over-exploits limited exploration patterns and converges to suboptimal reasoning strategies that the unreliable self-rewarding signal reinforces. rStar's continued improvement across the full rollout range supports the claim that action-space diversity and the contribution-based reward function enable more effective long-run exploration.

Ablation Studies and Robustness Checks

Action space diversity (Table 1): Ablating action types on 200 sampled GSM8K questions with LLaMA3-8B shows monotonic improvement from each addition: A3 alone (equivalent to RAP's action space) achieves 70.5% accuracy; adding A5 (rephrase) yields 72.5%; adding A4 (re-answer sub-question) yields 73.5%; adding A2 (propose remaining thoughts) yields 74.0%; adding A1 (one-step thought) for the full space yields 75.0%. Each action contributes positively, with cumulative gain of +4.5 points. This ablation validates the paper's core claim that action-space diversity is a primary driver of generator effectiveness, independent of the MCTS algorithm or discriminator (majority voting is used for answer selection here). A missing ablation is whether any single additional action beyond A3 dominates the gain, or whether the ordering of additions matters — the paper adds actions cumulatively in one fixed order, so interaction effects between actions are not isolated.

Generator comparison against baselines (Table 4): Four generator configurations are compared under two answer verification methods (majority voting and the rStar discriminator). For LLaMA3-8B on GSM8K: the rStar generator achieves 74.38% (majority) and 85.52% (rStar discriminator), outperforming RAP's generator (56.56% / 57.31%), SC@128 (67.55% / 85.06%), and rStar with self-evaluation (70.28% / 82.18%). For LLaMA3-8B-Instruct on GSM8K: rStar generator achieves 88.70% (majority) and 91.13% (rStar discriminator), versus RAP generator (81.35% / 84.69%), SC@128 (84.69% / 89.99%), and rStar+self-eval (88.07% / 89.92%).

The key finding is that adding self-evaluation to rStar's generator reduces performance despite the generator being otherwise identical: on LLaMA3-8B GSM8K, self-evaluation drops accuracy from 74.38% to 70.28% with majority voting, and from 85.52% to 82.18% with the rStar discriminator. This mirrors the Appendix A.1 finding that SLM self-assessment is counterproductive, even when combined with an otherwise well-designed generator. The paper highlights this as validating the decision to exclude self-rewarding from the reward function design.

On StrategyQA (Table 4, right columns), the pattern is consistent but with smaller absolute differences. For LLaMA3-8B-Instruct: rStar generator achieves 71.47% (majority) and 71.57% (rStar discriminator), versus RAP generator (69.43% / 70.60%), SC@128 (66.67% / 68.56%), and rStar+self-eval (69.28% / 69.43%). The discriminator adds little on StrategyQA for the stronger models — likely because the generator's trajectory quality is already high enough that majority voting is near-optimal.

Discriminator comparison against verification baselines (Table 5, left): For LLaMA3-8B and LLaMA3-8B-Instruct on GSM8K, three verification methods are compared on trajectories from two different generators (SC and rStar generator). The rStar discriminator consistently achieves the highest accuracy regardless of which generator produced the trajectories. For LLaMA3-8B with SC-generated trajectories: majority voting 67.55%, self-verification 74.00%, rStar discriminator 85.06%. With rStar-generated trajectories: majority voting 74.38%, self-verification 75.52%, rStar discriminator 85.52%. Self-verification provides a modest improvement over majority voting (+6.45 and +1.14 points respectively), but the rStar discriminator provides substantially larger gains (+17.51 and +10.14 points). This demonstrates that mutual consistency — using an independent model — is far more effective than having the same model verify its own outputs, consistent with the paper's thesis about SLM self-assessment unreliability.

Discriminator model choice (Table 5, right): Using LLaMA3-8B-Instruct as generator on GSM8K (baseline majority voting: 88.70%), the discriminator model is varied: LLaMA3-8B-Instruct (self-discrimination) achieves 88.78%, LLaMA3.1-8B-Instruct achieves 89.52%, Phi3-Mini-Instruct achieves 91.13%, and GPT-4 achieves 92.57%. The finding is that "the choice of discriminator model generally does not affect the effectiveness" — even the smallest model (Phi3-mini, 3.8B) works effectively, and scaling to GPT-4 yields only +1.44 points improvement over Phi3-mini. This robustness is important because it means the discriminator can be a lightweight model, keeping inference costs manageable. Notably, self-discrimination (LLaMA3-8B-Instruct as both generator and discriminator) still provides a small gain over majority voting (88.78% vs. 88.70%), suggesting that even a single model's completions given partial hints carry some verification signal — though the gain is minimal compared to using a different model.

Self-rewarding ablation in RAP (Table 6, Appendix A.1): For RAP on LLaMA2-7B and Mistral-7B across GSM8K and Multiarith, replacing the self-evaluated reward component r1 with random values causes minimal accuracy change. On LLaMA2-7B GSM8K: RAP 24.34% vs. RAP+random r1 22.90% (difference: −1.44 points). On Mistral-7B GSM8K: 56.25% vs. 55.50% (difference: −0.75 points). In contrast, replacing the self-consistency confidence component r2 with random values causes larger drops: LLaMA2-7B GSM8K drops to 22.67% (−1.67 points vs. original), Mistral-7B GSM8K drops to 49.66% (−6.59 points). On Multiarith (an easier dataset), RAP+random r2 drops more sharply: LLaMA2-7B 57.22% → 47.22%, Mistral-7B 91.11% → 81.11%. This establishes that the self-consistency confidence signal (r2) carries genuine information about trajectory quality, while the self-evaluated "helpfulness" signal (r1) is near-random — exactly the finding that motivates rStar's design to use terminal-node self-consistency confidence for rewards while excluding all self-evaluation terms.

Critical Assessment

Does rStar Demonstrate That SLMs Possess Latent Reasoning Capability Unlocked by Inference-Time Techniques?

The paper's central claim — that SLMs "already exhibit strong reasoning capabilities prior to domain specialized supervised fine-tuning" (Section 5) and that these capabilities can be unlocked through structured generation and peer verification — is strongly supported by the evidence, but with important qualification about what "strong reasoning capabilities" means operationally.

The evidence is compelling for the within-distribution case. On GSM8K, a dataset whose problem types and difficulty range are well-represented in the pretraining corpus of these models, rStar elevates LLaMA2-7B from 12.51% to 63.91% — a gain that genuinely represents unlocking latent knowledge, since the model was not fine-tuned on math reasoning data. The comparison to MetaMath fine-tuning (Figure 1: rStar's 63.91% vs. MetaMath's ~66%) supports the claim that the pretrained model's reasoning capacity is comparable to what fine-tuning on distilled GPT-4 data achieves. For Mistral-7B, rStar's 81.88% exceeding MetaMath's 77.7% actually suggests the inference-time approach better utilizes the pretrained knowledge than fine-tuning does.

However, what the experiments do not demonstrate is that this latent knowledge extends to problems far outside the pretraining distribution. The MATH-500 results (Table 3) show rStar achieving 42.94% on LLaMA3-8B-Instruct, which, while substantially higher than the 17.80% few-shot CoT baseline, is still below 50%. This suggests that for harder, more diverse mathematical reasoning requiring specialized knowledge (calculus, number theory, formal proof techniques), the pretrained model's knowledge base is genuinely incomplete — search and verification can amplify what's present but cannot create new mathematical understanding. The paper is appropriately measured in its claims, stating that rStar improves performance without claiming it matches supervised fine-tuning on all datasets. But the framing of "already possess strong reasoning capabilities" should be understood as conditional on the capability being somewhere in the model's output distribution at non-zero probability — which breaks down for sufficiently hard or out-of-distribution problems.

A related missing analysis: the paper does not report what fraction of rStar's successful trajectories on GSM8K correspond to solutions that the base model could produce with standard few-shot CoT but at low probability, versus solutions requiring the combinatorial exploration of the 5-action MCTS to construct (i.e., solutions that are novel compositions of reasoning primitives that never appear together in a single CoT sample). This distinction matters for the "latent knowledge" claim — if most correct trajectories are simply rare CoT samples that majority voting would eventually find with enough samples, then rStar's contribution is primarily efficient verification, not generation. If many correct trajectories require the action-space diversity to construct, then the generation component is genuinely unlocking new combinatorial reasoning capabilities. The paper provides no decomposition.

Does the Generator-Discriminator Architecture Genuinely Solve the Verification Problem?

The evidence that mutual consistency outperforms self-verification and majority voting is clear and consistent across experiments. Table 5 (left) shows 10+ point gains over self-verification. Table 2 shows massive gains over SC@maj128 for weak models (40.86 points for LLaMA2-7B). The discriminator model ablation (Table 5, right) shows robustness to model choice. These are strong results.

However, there are two unaddressed concerns:

Discriminator-generator error correlation. The mutual consistency mechanism's statistical power depends on the discriminator's errors being uncorrelated with the generator's errors. The paper provides no analysis of error correlation between generator and discriminator. Intuitively, two models from different families (e.g., LLaMA and Phi) likely have different error patterns. But when Phi3-mini serves as discriminator for LLaMA3-8B-Instruct, the paper achieves 91.13% accuracy; when LLaMA3-8B-Instruct serves as its own discriminator (self-discrimination in Table 5, right), accuracy is 88.78% — a smaller gain over the 88.70% majority voting baseline. This suggests that self-discrimination provides minimal signal beyond majority voting, which is consistent with positively correlated errors (the same model makes similar mistakes in both roles). The paper does not systematically vary the generator-discriminator pairing to measure how error correlation affects discrimination effectiveness — a gap that leaves open the question of how to optimally select discriminator models in practice.

No verification of the verification mechanism on incorrect trajectories. The discriminator is evaluated only by its contribution to final accuracy. The paper does not report the discriminator's precision (what fraction of validated trajectories are actually correct) or recall (what fraction of actually correct trajectories are validated). Without these metrics, it is unclear whether the discriminator is genuinely identifying correctness or whether it is merely filtering out trajectories that happen to disagree with the discriminator while keeping some incorrect ones and discarding some correct ones. A precision-recall analysis over the mutual consistency threshold would significantly strengthen the verification claims.

Does the Rich Action Space Actually Matter, or Is It Just Increasing Compute?

The action space ablation (Table 1) shows monotonic improvement from adding actions, but the experiment conflates action-space breadth with total compute: adding more action types means the MCTS tree can explore more branches at each node (since A1 and A3 each allow up to 5 nodes per depth, while the others allow 1). With all five actions, the branching factor is larger, meaning more total trajectories are generated and explored within the 32-rollout budget. The paper does not ablate whether the improvement comes from the semantic diversity of the actions or simply from the increased number of nodes explored. A controlled experiment that equalizes the total number of node expansions — e.g., comparing the 5-action space to a single-action space that generates more alternatives per depth — would be needed to isolate the diversity effect from the compute effect.

The marginal gains from individual actions in Table 1 are relatively small (0.5–2.0 points each) compared to the gap between rStar's generator and RAP's generator in the full experiments (Table 4: 74.38% vs. 56.56% on LLaMA3-8B, a 17.82-point gap). This suggests that additional factors beyond the action space contribute to the generator's superiority — possibly the reward function (contribution-based vs. self-evaluated) or the terminal confidence computation. The paper's Table 4 comparison (rStar generator vs. RAP generator, both with majority voting) does not isolate these factors: the two generators differ in action space, reward function, and potentially rollout policy, so the attribution to any single design choice is confounded.

Are the Baseline Comparisons Fair?

Several aspects of the baseline comparisons warrant scrutiny:

No compute-matched comparisons. rStar uses 32 MCTS rollouts, which requires approximately 166 model calls for LLaMA2-7B and 149 for Mistral-7B per question (Table 7). Self-consistency baselines are evaluated at 8, 64, and 128 samples — SC@128 uses fewer model calls (128 vs. 149–166) but generates complete trajectories each time (higher token count per call) rather than the step-by-step partial generations of MCTS. RAP and ToT have their own internal compute budgets that are not calibrated to rStar's. Without FLOPs-matched or token-matched comparisons, it is impossible to determine whether rStar's improvements reflect algorithmic superiority or simply more computation. A fair comparison would sweep all methods across a range of total inference FLOPs or token budgets and compare the Pareto frontiers.

RAP baseline configuration. The paper uses RAP's "original implementation" but does not specify the number of MCTS rollouts used for RAP in Tables 2 and 3. If RAP was run with fewer rollouts than rStar (as suggested by Figure 5, where RAP degrades after 4 rollouts while rStar scales to 32), then the comparison is biased in rStar's favor — RAP might simply be under-provisioned. The Figure 5 comparison does show rStar outperforming RAP at matched rollout counts (2–32), which partially addresses this, but Figure 5 covers only two models on GSM8K, not the full matrix of results in Table 2.

ToT performance is suspiciously low. ToT achieves accuracies below few-shot CoT on several benchmarks (e.g., LLaMA3-8B GSM8K: ToT 36.01% vs. few-shot CoT 47.23%). This is not a natural baseline — it suggests that the ToT implementation used may be substantially suboptimal (perhaps due to the BFS exploration strategy, the specific prompting, or the evaluation function used for pruning). Using a ToT baseline that underperforms single-round prompting makes rStar's improvements over ToT less informative than they appear.

Self-consistency ceiling for strong models. For Phi3-mini on GSM8K (Table 2), SC@maj128 already achieves 88.68%, and rStar reaches 90.67% — a gain of only 1.99 points. This suggests that as base model capability increases, the marginal benefit of rStar over simple repeated sampling shrinks. The paper does not discuss this saturation effect or characterize the conditions under which rStar provides diminishing returns. For LLaMA3-8B-Instruct, the gap is similarly narrow (91.13% vs. 84.69% SC@128, a 6.44-point gain), and on SVAMP, the gap is 3.69 points. This is not a weakness of rStar per se — methods that solve the hard-tail are inherently most valuable — but it means the dramatic headline numbers (4×, 5× improvements) apply primarily to the weakest models and are not representative of expected gains across the board.

Statistical Rigor and Reproducibility Concerns

No confidence intervals, standard deviations, or significance tests. Every accuracy number in Tables 2 and 3 is reported as a point estimate. With test sets of varying sizes (GSM8K is approximately 1,319 questions; MATH-500 is exactly 500; the others are unspecified), differences of a few percentage points may or may not be statistically significant. For the narrower gaps — e.g., rStar 90.67% vs. SC@128 88.68% on Phi3-mini GSM8K, or rStar 94.10% vs. SC@128 93.70% on Phi3-mini SVAMP — we cannot determine whether these represent genuine improvements or sampling noise. The paper's claims of "state-of-the-art" performance would be strengthened by basic statistical reporting.

Fixed hyperparameters with no sensitivity analysis. The tree depth (d = 5 or 8), maximum nodes per depth (5 for A1/A3, 1 for others), and number of rollouts (32) are stated as fixed values without justification or sensitivity analysis. The paper does not show how performance varies with different depth settings, different branching limits, or how the optimal configuration changes across model sizes and task difficulties. The single rollout scaling curve (Figure 5) is the only hyperparameter sensitivity analysis provided, and it covers only one axis (number of rollouts) for two models on one benchmark.

Single test-set evaluation. With the exception of the 200-question sample ablation in Table 1, all results are reported on the full test sets without cross-validation splits. The "compute-optimal" allocation strategy that the paper implicitly advocates (more rollouts for harder problems, varying the generator-discriminator tradeoff) is based on a single evaluation pass — there is no held-out data used to tune hyperparameters, raising the risk that the reported numbers overfit to the specific test questions.

Missing baseline: standard MCTS with richer action space but without discriminator. The paper compares rStar against RAP (single-action MCTS) but does not report a baseline that uses the 5-action MCTS with standard MCTS answer selection (highest-reward path) instead of the mutual consistency discriminator. The rStar (generator @maj) results use majority voting, not MCTS's internal selection mechanism — which means we cannot determine whether the discriminator's contribution is primarily fixing weaknesses in majority voting or weaknesses in MCTS reward-based selection. A direct ablation comparing: (a) 5-action MCTS with MCTS reward-based selection, (b) 5-action MCTS with majority voting, and (c) 5-action MCTS with mutual consistency would clarify this.

Robustness to Task Diversity

The paper evaluates on five benchmarks spanning math and commonsense reasoning. The results on StrategyQA (Table 2) are particularly illuminating because this task differs fundamentally from mathematical reasoning — answers are boolean, reasoning involves world knowledge rather than computation, and the "steps" in a reasoning trajectory look qualitatively different (commonsense inferences rather than arithmetic operations). rStar's consistent improvement on StrategyQA (e.g., LLaMA2-7B from 58.82% to 67.25%, LLaMA3-8B-Instruct from 68.41% to 71.57%) demonstrates that the approach is not math-specific. However, StrategyQA also reveals the clearest failure mode of self-consistency (performance degrades with more samples for most models), which rStar avoids. This cross-task robustness supports the paper's claim that the generator-discriminator framework is general-purpose.

That said, all five benchmarks are closed-form answer tasks with exact-match evaluation. The paper does not evaluate on open-ended generation tasks, dialogue, summarization, or any task where correctness cannot be reduced to string matching. The mutual consistency mechanism fundamentally requires that the discriminator's answer can be compared to the generator's answer — "do they agree?" — which is straightforward for numeric or boolean answers but ambiguous for free-text answers. Extending rStar to open-ended tasks would require a different consistency metric (semantic similarity, entailment, etc.), which the paper does not explore or discuss.

6. Limitations and Trade-offs

Limitation 1: rStar Does Not Help on Problems Where the Base Model Cannot Produce Any Correct Trajectory — The "Capability Ceiling" Problem

The assumption or constraint. rStar's fundamental operating assumption is that the base SLM can produce at least some correct reasoning trajectories at a non-zero rate — the search and verification mechanisms amplify and identify existing capabilities, but they do not create new ones. The paper acknowledges this indirectly in its framing: "SLMs already have strong reasoning capabilities but need guidance to generate and select the correct solutions" (Section 4.2). However, this assumption has a sharp boundary: when the base model's pass@1 is effectively zero on a problem, no amount of search or verification can produce a correct answer, because there are no correct trajectories in the search tree to find.

The consequence. The approach fails catastrophically on problems outside the model's capability range. This is not a gradual degradation — it is a hard ceiling. Evidence for this appears in the MATH-500 results (Table 3): even with rStar, LLaMA3-8B-Instruct achieves only 42.94% accuracy, meaning the majority of college-level math problems remain unsolved despite the 32-rollout MCTS and mutual consistency verification. The generator-only accuracy (rStar (generator @maj): 38.30%) is already close to the full rStar accuracy (42.94%), indicating that the binding constraint is trajectory generation, not verification — the search simply cannot find correct solutions for most problems because they are not in the model's output distribution at any non-trivial probability.

This limitation is more than an empirical observation; it defines the scope of rStar's applicability. The paper's results show that rStar's gains are largest on easier benchmarks where base pass@1 is moderate (GSM8K, SVAMP) and shrink on harder ones (GSM-Hard: 18.57–46.55% across models; MATH: 42.94–48.60%). For a practitioner, this means rStar is valuable for problems within the model's rough capability range — where the model occasionally gets the answer right through standard prompting — but provides minimal benefit for novel, highly complex, or out-of-distribution reasoning where the model simply does not possess the necessary knowledge or reasoning patterns.

What evidence exists in the paper. The MATH-500 results in Table 3 provide the clearest signal. The gap between rStar (generator @maj) and full rStar shrinks relative to easier benchmarks: on GSM8K for LLaMA3-8B-Instruct, the discriminator adds +2.43 points (88.70% → 91.13%); on MATH-500, it adds +4.64 points (38.30% → 42.94%). The larger relative gain on MATH-500 still leaves absolute accuracy below 50%, indicating that even with perfect verification, the ceiling imposed by generation quality is low. The paper does not report per-difficulty breakdowns (analogous to the difficulty-bin analysis in Snell et al., 2024), which would directly quantify how rStar's effectiveness varies with problem hardness and identify the capability ceiling more precisely.

Mitigation status. The paper does not attempt to address this limitation — it is inherent to the inference-time-only approach. The solution would necessarily require training-time intervention (fine-tuning on harder problems, scaling to larger models, or retrieval-augmented generation). The paper's stated goal is explicitly "reasoning improvements without a superior teacher LLM" (Section 1), which rules out the standard remedies. The authors do not suggest future work on extending the capability ceiling, though the implication is that rStar should be combined with iterative self-improvement (using rStar-generated correct solutions as fine-tuning data) to gradually expand the model's capability range — an approach the paper does not explore but that would naturally follow from the framework.

Limitation 2: The Inference Cost Is Substantial and Not Accounted for in the Headline Accuracy Numbers

The assumption or constraint. rStar's accuracy gains come at a large computational cost that is reported but not amortized in the headline comparisons. The paper states that solving a single GSM8K question requires an average of 166 model calls for LLaMA2-7B and 149 for Mistral-7B, generating approximately 367k and 349k tokens respectively (Table 7, Appendix A.2). The full GSM8K test set of ~1,319 questions takes "about 4.5 days on a single A100 GPU per model" (Appendix A.2). The comparison baselines — self-consistency at 8, 64, and 128 samples — require 8, 64, or 128 model calls respectively (each generating a complete CoT solution), which is fewer calls but longer individual generations.

The paper treats number of rollouts as the compute budget (Figure 5) but does not normalize across methods in a unified cost metric (FLOPs, total generated tokens, or wall-clock time at matched hardware). This makes the accuracy comparisons in Table 2 potentially misleading: rStar achieves 81.88% on Mistral-7B GSM8K versus SC@maj128's 57.25%, but rStar uses more total compute (149 calls with partial-step generations) than SC@128 (128 calls with full-trajectory generations), and the token costs are not directly comparable because MCTS steps are shorter than full CoT trajectories.

The consequence. The headline accuracy gains conflate algorithmic improvement with increased compute expenditure. A practitioner deciding whether to deploy rStar needs to know: if I equalize the inference budget (in FLOPs or GPU-hours) between rStar and a baseline like self-consistency, does rStar still win? If I scale self-consistency to 256 or 512 samples (which would match or exceed rStar's token budget), does the gap close? The paper provides no evidence on this question. The Figure 5 rollout scaling curves partially address it — at matched rollout counts (2–32), rStar outperforms SC — but rollouts are not directly comparable units across methods (one rStar rollout involves multiple model calls for selection, expansion, and simulation; one SC rollout is a single complete generation). Without a FLOPs-matched or token-matched comparison, the efficiency gains are unquantified.

Additionally, the 4.5 days per model on a single A100 for GSM8K is a substantial practical cost. For a production system processing thousands of queries per day, rStar's inference cost would require significant GPU provisioning or batching infrastructure. The paper notes that costs "can be significantly reduced by distributing tasks across multiple GPUs or batching model calls within each rollout" (Appendix A.2), but provides no empirical measurements of parallelization efficiency or latency-vs-throughput tradeoffs.

What evidence exists in the paper. Table 7 in Appendix A.2 provides average model calls and token counts per question. Figure 5 compares rStar to SC and RAP at matched rollout counts (not matched cost). The paper does not report any FLOPs-matched or token-normalized comparison, any measurement of end-to-end wall-clock latency, or any analysis of how rStar's performance varies when SC baselines are scaled to equal total token budgets. This is a gap in the experimental methodology that prevents a rigorous efficiency assessment.

Mitigation status. The paper partially acknowledges the cost concern (Appendix A.2) and gestures at parallelization as mitigation, but does not quantify the achievable speedup or demonstrate practical deployment feasibility. The suggestion to batch model calls is plausible — MCTS at a given depth can expand multiple nodes in parallel, and discriminator calls across trajectories are independent — but the MCTS selection phase is inherently sequential (each level's expansion depends on the UCT scores computed from previous rollouts), limiting parallelization potential. The paper does not propose or evaluate a budget-adaptive version of rStar that dynamically allocates rollouts based on estimated problem difficulty (cf. Snell et al., 2024, which implements exactly this for LLM test-time compute scaling), which would be the natural mitigation for the cost concern.

Limitation 3: Verification Through Mutual Consistency Has Unknown Precision and Recall — We Don't Know How Often the Discriminator Is Wrong

The assumption or constraint. The mutual consistency mechanism operates as a binary filter: if the discriminator completes a partially-masked trajectory and arrives at the same answer, the trajectory is validated; otherwise, it is discarded. The paper assumes that agreement between generator and discriminator is informative about correctness — that validated trajectories are more likely to be correct than non-validated ones, and that the discriminator does not systematically validate wrong answers or reject correct ones at high rates.

However, the paper provides no direct measurement of the discriminator's verification quality. It does not report precision (what fraction of validated trajectories are actually correct), recall (what fraction of actually correct trajectories are validated), false positive rate (how often an incorrect trajectory is validated), or false negative rate (how often a correct trajectory is rejected). The only evaluation metric is final accuracy after trajectory selection, which conflates verification quality with generation quality and the final selection mechanism.

The consequence. Without precision and recall measurements, a practitioner cannot assess the discriminator's reliability in isolation or diagnose failure modes. Several concerning scenarios are possible:

The discriminator could be validating incorrect trajectories that happen to share the same wrong answer. If both generator and discriminator make similar systematic errors (e.g., both models misread a problem condition in the same way), they will agree on an incorrect answer. The paper provides no analysis of error correlation between generator and discriminator, and the self-discrimination result in Table 5 (right) — where LLaMA3-8B-Instruct serves as its own discriminator and achieves only 88.78% vs. the 88.70% majority voting baseline — suggests that when the same model plays both roles, the verification signal is minimal, consistent with correlated errors. Different-model pairs may have lower but still non-zero error correlation.
The discriminator could be rejecting correct trajectories that use unconventional but valid reasoning. The split-point randomization (20–80% of steps revealed) means the discriminator sometimes sees only a small prefix. If the discriminator cannot reconstruct the correct answer from a minimal hint (even though the generator's full trajectory is correct), it will reject a valid solution — a false negative. The paper does not report how accuracy would change if correct-but-rejected trajectories were retained.
The discriminator's effectiveness may vary with split point position. Trajectories split at 20% (minimal hint) are harder for the discriminator to complete correctly than those split at 80% (nearly complete). The randomization averages over this variation, but a practitioner might want to use a fixed optimal split point rather than randomizing, or might want to ensemble multiple split points for higher verification confidence. The paper provides no analysis of how verification accuracy varies with split point.

What evidence exists in the paper. The only evidence for discriminator quality is the improvement in final accuracy when it is added to the generator (Table 2: rStar vs. rStar (generator @maj), and Table 5: rStar discriminator vs. majority voting baseline). For LLaMA2-7B on GSM8K, the discriminator adds +36.69 points; for Mistral-7B, +17.29 points; for LLaMA3-8B-Instruct, +2.43 points. These gains demonstrate that the discriminator provides genuine value, but do not decompose how much of the gain comes from filtering out incorrect trajectories versus from the final scoring mechanism versus from the discriminator's ability to validate the single best trajectory. The paper does not report any direct verification metrics (precision, recall, error correlation, per-split-point analysis).

Mitigation status. Not addressed. The paper provides no verification quality diagnostics, no error correlation analysis, and no sensitivity study of the mutual consistency mechanism. Future work would need to measure verification precision/recall directly (by comparing discriminator validation decisions against ground-truth correctness labels for individual trajectories) and analyze failure modes (when does a correct trajectory get rejected? when does an incorrect one get validated?). The paper also does not explore calibration of the verification signal — e.g., whether trajectories validated under more stringent conditions (multiple discriminator completions, multiple split points) are more likely to be correct, which could enable a confidence-graded verification rather than binary filtering.

Limitation 4: The Action Space Is Hand-Designed and Fixed — It May Not Transfer to New Domains or Model Families

The assumption or constraint. The five action types (A1–A5) were designed based on the authors' analysis of human reasoning strategies and error patterns observed on mathematical word problems: step-by-step deduction (A1), direct CoT completion (A2), problem decomposition (A3), sub-question re-answering (A4), and problem rephrasing (A5). Each action has a custom prompt template with few-shot examples tailored to arithmetic word problems (Appendix A.3). The action space is fixed across all five benchmarks and all five model families — there is no adaptation of actions or prompts based on the task or model.

The paper asserts that these actions "define a highly diverse action space" (Section 3.2) and shows via ablation (Table 1) that each contributes to accuracy on GSM8K. However, the design is fundamentally manual and domain-informed: the actions reflect the authors' understanding of what reasoning primitives are useful for math word problems, and the prompt templates encode specific reasoning patterns (e.g., the A3 template demonstrates decomposition of arithmetic word problems into sub-questions with numeric answers).

The consequence. The action space may not transfer effectively to qualitatively different reasoning domains. StrategyQA (commonsense reasoning) is the most different benchmark tested, and rStar does improve over baselines there (Table 2: LLaMA2-7B from 58.82% to 67.25%), suggesting some cross-domain transfer. But StrategyQA still involves step-by-step inference with a boolean answer — the reasoning structure is not radically different from math word problems. The paper does not evaluate on domains where the reasoning structure is fundamentally different: code generation (where "steps" are lines of code), multi-hop question answering over documents (where steps involve retrieval and synthesis), dialogue state tracking (where steps are slot-value updates), or open-ended planning (where steps are actions in a world model and the "answer" is a plan rather than a single token).

Even within mathematical reasoning, the fixed action space may be suboptimal for certain problem types. Geometry problems require spatial reasoning; probability problems require enumeration of outcomes; algebra problems require symbolic manipulation. The current actions (decompose, rephrase, step-by-step, complete, re-answer) are generic reasoning strategies that may not capture domain-specific reasoning patterns. The paper provides no evidence about whether the action space is sufficient for the full diversity of MATH problems (which span algebra, geometry, number theory, probability, and precalculus) or whether certain MATH subdomains account for disproportionate shares of the remaining errors.

Additionally, the prompt templates are model-agnostic but were likely developed and tested with specific models (LLaMA-family models are prominent in the paper). Smaller or differently-trained models might respond differently to the same prompts — e.g., Phi3-mini might benefit from different few-shot examples or a different action structure than LLaMA2-7B. The paper provides no analysis of per-action effectiveness across models.

What evidence exists in the paper. The action space ablation in Table 1 shows cumulative contributions on LLaMA3-8B for GSM8K. The cross-benchmark results in Table 2 show rStar improving accuracy on all five benchmarks, providing indirect evidence of cross-domain transfer. However, the paper provides no per-action breakdown by benchmark (does A5's rephrasing help more on StrategyQA than on GSM8K? does A3's decomposition help on MATH but not on SVAMP?), no per-action breakdown by model (do weaker models benefit more from certain actions?), and no analysis of whether the action space saturates — i.e., whether adding a sixth action would continue to improve performance or whether five is sufficient for the tested domains.

Mitigation status. The paper does not address action space transfer or adaptation. The fixed, hand-designed action space is a pragmatic choice that works well for the evaluated benchmarks, but it represents a form of domain knowledge injection (the action designers understood what reasoning strategies help for math problems) that subtly violates the paper's "no superior model" premise — the action space is effectively a human-provided prior on useful reasoning strategies. A fully self-contained system would need to learn or discover useful actions from the model's own behavior, perhaps through meta-reasoning or automatic prompt optimization. The paper does not discuss this direction.

Limitation 5: Performance Saturates on Stronger Models — rStar Provides Diminishing Returns as Base Capability Increases

The assumption or constraint. rStar is motivated by and designed for small language models with weak base reasoning capabilities. The paper's central narrative — that SLMs possess latent reasoning knowledge that rStar unlocks — is best supported when the base model's few-shot CoT accuracy is low and rStar achieves dramatic gains (e.g., LLaMA2-7B on GSM8K: 12.51% → 63.91%). However, the method's marginal benefit shrinks substantially as base model capability increases, a pattern that is visible in the results but not discussed as a limitation.

The consequence. For practitioners using stronger SLMs or larger models, rStar may not justify its computational cost. The data tells the story:

Phi3-mini on GSM8K (Table 2): few-shot CoT already achieves 83.45%. SC@maj128 reaches 88.68%. rStar reaches 90.67% — a gain of only +1.99 points over SC@128 and +7.22 over few-shot CoT. At 32 MCTS rollouts generating hundreds of model calls, this marginal improvement must be weighed against the compute budget. If inference cost scales linearly with model size and rollout count, deploying rStar on a model that already achieves 88.68% with simple repeated sampling may not be cost-effective.
LLaMA3-8B-Instruct on GSM8K (Table 2): rStar achieves 91.13% vs. SC@128's 84.69% (+6.44 points). This is a more meaningful gain but still modest compared to the 4×–5× relative improvements on weaker models.
LLaMA3-8B-Instruct on SVAMP (Table 2): rStar achieves 94.29% vs. SC@128's 90.60% (+3.69 points) and few-shot CoT's 89.20% (+5.09 points).
Phi3-mini on SVAMP (Table 2): rStar achieves 94.10% vs. SC@128's 93.70% (+0.40 points) — within statistical noise.

The pattern is clear: rStar's absolute gains over strong baselines are small when the base model is already capable. This is not a failure of rStar per se — any method that approaches the 100% ceiling will show diminishing returns — but it means that rStar's value proposition is highly model-dependent. The paper's framing emphasizes the dramatic gains on weak models but does not foreground the saturation effect.

Furthermore, the discriminator's contribution shrinks on stronger models: for LLaMA3-8B-Instruct on GSM8K, the discriminator adds +2.43 points over the generator with majority voting (88.70% → 91.13%); for Phi3-mini, it adds +0.23 points (90.44% → 90.67%). This suggests that when the generator already produces mostly correct trajectories, mutual consistency provides minimal additional signal — the verification problem is largely solved by the generator's inherent quality, and majority voting suffices. The expensive discriminator infrastructure adds little value in this regime.

What evidence exists in the paper. The data is in Table 2 and discussed in Appendix A.2, which notes: "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" — implying that the discriminator's role diminishes. The paper does not analyze the cost-effectiveness tradeoff for strong models, provide a recommendation for when rStar is worth deploying vs. when simpler methods suffice, or characterize the base accuracy threshold below which rStar provides substantial gains.

Mitigation status. The paper does not address this saturation effect as a limitation, though it does implicitly acknowledge it in Appendix A.2. A practical mitigation would be a difficulty-estimation or model-capability-estimation module that decides per-problem whether to deploy rStar or fall back to a cheaper method (e.g., few-shot CoT for easy problems, SC@8 for medium, rStar only for hard problems). This would parallel the compute-optimal test-time scaling approach in Snell et al. (2024), where the inference strategy is chosen adaptively based on estimated prompt difficulty. The paper does not propose or evaluate such adaptive allocation.

Limitation 6: rStar Has Not Been Demonstrated on Open-Ended Generation Tasks — The Mutual Consistency Mechanism Requires Exact Answer Matching

The assumption or constraint. rStar's mutual consistency mechanism depends on comparing the discriminator's completed answer to the generator's original answer and checking for exact match. For mathematical benchmarks (GSM8K, MATH, SVAMP, GSM-Hard), answers are numeric and matching is strict equality after extraction (the paper uses standard numeric answer extraction, presumably following the dataset conventions). For StrategyQA, answers are boolean (yes/no), and matching is again exact. The paper provides no mechanism for handling tasks where answers are free-form text, structured outputs, or multi-sentence explanations — domains where "same answer" is an ambiguous concept.

The paper does not explicitly state this as a scope limitation, but it is implicit in the benchmark selection: all five benchmarks are closed-form answer tasks with well-defined, extractable final answers. Section 1 frames rStar as solving "diverse reasoning problems" and lists the five benchmarks, but does not discuss what types of reasoning problems fall outside this scope.

The consequence. A substantial fraction of real-world LLM applications involve open-ended generation: summarization (where "correctness" is multi-dimensional — factual accuracy, coherence, conciseness), translation (where multiple valid translations exist), creative writing, dialogue response generation, code generation with complex correctness criteria beyond unit tests, or explanation tasks where the quality of reasoning matters as much as the final conclusion. For such tasks, the mutual consistency mechanism cannot be applied directly because:

There is no unique correct answer to compare. If the generator produces a summary and the discriminator produces a different summary, they may both be perfectly valid. Exact matching would reject most correct trajectories, making the discriminator a false-negative generator.
"Agreement" is a matter of degree, not a binary. Two summaries may share the same key information but differ in wording, level of detail, or ordering. Defining a consistency threshold requires semantic similarity metrics, which introduce their own reliability issues (especially for SLMs that the paper has already shown are unreliable at self-evaluation).
The "answer" may not be extractable as a single short string. If the task is to explain a solution step-by-step, the final answer is the entire explanation, not a single token or number. Masking part of the explanation and asking the discriminator to complete it would require the discriminator to produce a multi-step reasoning trace, and comparing two traces for consistency would require evaluating whether they reach the same conclusion through equivalent reasoning — a much harder verification problem than comparing "42" to "42".

The paper's evaluation suite is limited to tasks with extractable, unique correct answers, which means the claimed generality ("diverse reasoning problems") is narrower than it might appear. A practitioner working on open-ended reasoning tasks cannot assume rStar will transfer without substantial modification to the verification mechanism.

What evidence exists in the paper. The paper evaluates on five benchmarks, all of which are exact-match tasks with extractable answers. There is no ablation or discussion of how mutual consistency would extend to open-ended generation, no experiment replacing exact match with a soft similarity metric (e.g., BLEU, ROUGE, or LLM-as-judge agreement), and no analysis of how the discriminator's effectiveness changes if the "consistency" criterion is relaxed from exact match to approximate match. The paper does not acknowledge this scope limitation explicitly.

Mitigation status. Not addressed. Extending rStar to open-ended tasks would require a fundamentally different consistency criterion — perhaps using the discriminator not as a binary verifier but as a scorer that rates how well its own completion aligns with the generator's trajectory along dimensions like factual consistency, logical coherence, or stylistic similarity. This would move rStar closer to trained reward model territory (which the paper explicitly avoids) or require natural language inference techniques to check whether the discriminator's completion entails the generator's conclusion. The paper does not discuss future work in this direction.

7. Implications and Future Directions

How This Work Changes the Landscape

rStar shifts the conversation around small language model reasoning from a training-centric to an inference-centric framing, but — critically — it does so not by proposing a more sophisticated search algorithm or a better prompt, but by demonstrating that the primary bottleneck for SLM reasoning is verification, not generation capability. This is a reframing of the problem rather than a paradigm shift: the field already had MCTS-based reasoning (RAP, ToT), multiple-solution sampling (self-consistency), and verification mechanisms (trained reward models, self-verification). What rStar contributes is the empirical demonstration that these pieces, when assembled correctly for the SLM regime, can unlock performance comparable to fine-tuning — and that the correct assembly requires abandoning any reliance on the model's own quality judgments in favor of peer verification through independent completion.

The paper's most significant conceptual move is its negative result made constructive: Appendix A.1's finding that SLM self-evaluation is near-random (r1 replacement with random values causes a negligible accuracy drop: 24.34% → 22.90% on LLaMA2-7B GSM8K) is not merely a critique of prior work but the organizing principle for a new architecture. This finding resolves a contradiction that has been accumulating in the literature. On one side, self-refinement and self-verification techniques show promise on large models (Madaan et al., 2024; Weng et al., 2023); on the other, studies like Huang et al. (2023) and Feng et al. (2023) show these techniques fail or degrade for smaller models. rStar's framework explains this: SLMs cannot evaluate their own outputs, so any method that asks them to do so — whether through explicit self-evaluation prompts, self-rewarding in MCTS, or self-verification of complete trajectories — is injecting noise into the system. The resolution is not that self-improvement is impossible for SLMs, but that it requires an external verifier — and rStar demonstrates that this verifier can be another equally weak model, used through a prompting strategy that converts independent completion into a verification signal rather than through direct quality assessment.

This reframing redirects research attention in several ways. First, it makes verifier design for SLMs a first-class research problem, distinct from verifier design for large models. The finding that trained reward models risk overfitting and require labeled data (Section 2), while self-verification is unreliable (Table 5), and mutual consistency works with minimal model requirements (Table 5, right: Phi3-mini as discriminator for LLaMA3-8B-Instruct achieves 91.13%, only 1.44 points below GPT-4), suggests that the productive direction for SLM verification is architectural diversity (ensembles of different models with uncorrelated errors) rather than individual verifier quality (training increasingly sophisticated single-model verifiers). This is a genuinely different design philosophy from the "train a better reward model" approach dominant in the field (Lightman et al., 2023; Wang et al., 2024b).

Second, the paper makes action-space design a first-class dimension of MCTS-based reasoning. Prior work treated the action space as a fixed, low-level primitive (RAP's single "propose next sub-question" action; ToT's single "propose one thought" action). rStar's Table 1 shows that each additional action type yields a measurable accuracy gain (cumulative +4.5 points from five actions), establishing that the diversity of reasoning primitives available to the search algorithm is a primary lever for capability improvement. This suggests future MCTS-based methods should treat action-space engineering with the same care currently given to search algorithm design — and potentially learn actions from data rather than hand-specifying them.

Third, rStar demonstrates that inference-time compute can substitute for training-time data in the SLM regime, but with a sharp boundary. The comparison to MetaMath fine-tuning in Figure 1 shows rStar on LLaMA2-7B reaching 63.91% GSM8K accuracy, nearly matching fine-tuning's ~66% — without any new training data. On Mistral-7B, rStar's 81.88% exceeds MetaMath fine-tuning's 77.7%. These results establish that, at least for within-distribution math reasoning, the pretrained model's knowledge is competitive with what fine-tuning on GPT-4-distilled data provides. However, the MATH-500 results (Table 3: 42.94% for LLaMA3-8B-Instruct) and the implicit difficulty gradient across benchmarks (GSM8K rStar 91.13% → GSM-Hard 37.53% → MATH 42.94%) show that this substitution breaks down for harder problems — inference-time search cannot create knowledge the model does not possess. This reframes the training-vs-inference tradeoff for SLMs as difficulty-dependent: for problems within the model's rough capability range (where pass@1 is non-trivially above zero), inference-time techniques can match or exceed fine-tuning; for problems beyond that range, training remains necessary. This is an important practical guideline that prior work had not quantified.

Finally, rStar provides a partial reconciliation with the Snell et al. (2024) compute-optimal test-time scaling framework (discussed extensively in the reference example). Snell et al. showed that adaptive allocation of inference compute based on difficulty can yield 4× efficiency gains over best-of-N, and that test-time compute with a small model can outperform a ~14× larger model on easy problems. rStar operates in a complementary regime: it applies to models where even the best-of-N baseline (self-consistency with majority voting) is fundamentally broken because the correct answer is rarely the mode of the output distribution — a failure mode Snell et al. did not study because their base models (PaLM 2-S*) had much higher pass@1 (~10–19% on MATH, far above LLaMA2-7B's near-zero on harder problems). rStar's mutual consistency mechanism is a solution to a harder verification problem than Snell et al.'s PRM-based approach addresses: how to select correct answers when they are a minority of the candidate set. Combining rStar's verification with Snell et al.'s difficulty-conditioned compute allocation would be a natural integration of the two frameworks.

Follow-Up Research This Work Enables

Measuring discriminative precision and recall of mutual consistency. The paper demonstrates that mutual consistency improves final accuracy but provides no direct measurement of the discriminator's verification quality: what fraction of validated trajectories are actually correct (precision), and what fraction of actually correct trajectories are validated (recall)? A follow-up study would label individual candidate trajectories from rStar's MCTS generator with ground-truth correctness (by comparing their final answers to known labels) and then measure precision and recall for the mutual consistency discriminator across different split-point ranges (20%, 40%, 60%, 80% of steps revealed). This would reveal failure modes: does the discriminator systematically validate trajectories with a particular wrong answer (indicating correlated errors between generator and discriminator)? Does it reject correct trajectories with unconventional reasoning (false negatives at low split percentages)? Does precision improve when multiple discriminator completions are required per trajectory rather than a single one? The study would also compare discrimination quality when the generator and discriminator are from the same versus different model families, quantifying error correlation directly. This would transform mutual consistency from an empirically-validated heuristic into a calibrated verification mechanism with known operating characteristics.

Difficulty-conditioned adaptive allocation of rStar's compute budget. rStar uses a fixed 32 rollouts for all problems regardless of difficulty, but the paper's results show that rStar's marginal benefit varies dramatically with base model capability: for strong models on easy problems, 2 rollouts already achieve near-peak performance (Figure 5); for weak models on hard problems, additional rollouts continue to help but the absolute ceiling remains low. A natural extension would borrow the compute-optimal test-time scaling framework from Snell et al. (2024) and apply it to rStar's specific search architecture: estimate problem difficulty (perhaps by running a small number of initial rollouts and measuring the self-consistency confidence of the resulting terminal nodes), then adaptively allocate the remaining rollout budget based on estimated difficulty, and choose between simple majority voting (for high-confidence cases) and mutual consistency (for low-confidence cases) as the verification mechanism. The key experiment would measure, on a fixed total compute budget (in FLOPs or generated tokens), whether adaptive allocation outperforms uniform 32-rollout rStar. This would also address the paper's unexamined cost-effectiveness problem by demonstrating whether the discriminator can be deployed selectively rather than for every trajectory.

Learning the action space from model behavior instead of hand-designing it. The five-action space (A1–A5) is hand-designed based on human analysis of math reasoning strategies and common SLM error patterns. Table 1 shows each action contributes positively, but there is no evidence that five actions are sufficient or optimal, and the prompts are fixed across all tasks and models. A meta-reasoning extension would train the SLM itself to propose useful actions: given a set of problems and their correct solutions, the model could be prompted to analyze which reasoning strategies would have helped, and new action types could be extracted and added to the space. Alternatively, the MCTS could treat action selection as a learned policy optimized via reinforcement learning from terminal-node correctness, rather than using the undirected UCT formula. The experiment would compare learned action spaces against the hand-designed one on MATH (where the diversity of subdomains — algebra, geometry, probability — may require domain-specific actions that the current generic space misses). A negative result (learned actions do not outperform hand-designed ones on in-distribution math problems, but do transfer better to out-of-distribution benchmarks like ARC or FOLIO) would characterize the limits of domain-specific action engineering versus learned meta-reasoning.

Stress-testing mutual consistency on models where the generator and discriminator share pretraining. The paper's discriminator ablation (Table 5, right) shows that using LLaMA3-8B-Instruct as its own discriminator yields 88.78%, only marginally above the 88.70% majority voting baseline — suggesting that self-discrimination provides almost no signal. But what about models that share pretraining data and architecture but differ in scale or fine-tuning, such as using LLaMA3-8B discriminator for LLaMA3-70B generator, or Mistral-7B discriminator for LLaMA2-7B generator? Do models from the same family have sufficiently uncorrelated errors for mutual consistency to work? A systematic study would pair models with varying degrees of relatedness: same checkpoint (self-discrimination), same family different sizes, same family with different fine-tuning, different families, different architectures entirely (dense vs. mixture-of-experts), and measure how verification precision varies with model relatedness. This would establish the conditions under which mutual consistency is reliable and inform deployment decisions (given a specific generator model, which available model should serve as discriminator?).

Combining rStar's generator-discriminator self-play with iterative self-training. The paper demonstrates that rStar's inference-time pipeline can achieve accuracy competitive with fine-tuning on GSM8K, but it does not close the self-improvement loop: use rStar to generate high-quality reasoning trajectories, then fine-tune the generator on those trajectories, then re-run rStar with the improved generator. This is the natural extension of the self-play concept from single-round inference to multi-round improvement. The experiment would measure GSM8K and MATH accuracy after 1, 2, and 3 rounds of this self-training loop, comparing against: (a) fine-tuning on the same number of GPT-4-distilled trajectories (the upper bound from teacher distillation), (b) fine-tuning on trajectories selected by majority voting rather than mutual consistency (isolating the discriminator's contribution to training data quality), and (c) no fine-tuning (the current rStar baseline). A key diagnostic would be whether the discriminator's verification quality degrades as the generator improves — does the generator start producing errors that the discriminator cannot detect because both models converge on the same incorrect reasoning patterns? This would test whether mutual consistency remains a useful signal through multiple rounds of self-improvement or whether it saturates once the generator becomes strong enough to need a stronger verifier.

Replacing the fixed action prompts with model-specific prompt optimization. The Appendix A.3 prompts for A1–A5 are fixed across all five evaluated models — the same few-shot examples and instruction templates are used for LLaMA2-7B, Mistral-7B, and Phi3-mini alike. But different models may respond differently to the same prompts, and the paper provides no evidence that the prompts are optimal for any specific model. A follow-up study would apply automatic prompt optimization (e.g., DSPy-style prompt compilation or evolutionary search over prompt templates) to each action type, optimizing per-model to maximize the pass@1 of individual action-generated steps on a validation set. The experiment would then measure whether model-specific optimized prompts improve rStar's final accuracy over the paper's fixed prompts, and whether the gain varies with model size (do weaker models benefit more from prompt optimization, or do they lack the instruction-following capability to exploit optimized prompts?). This would also test a broader question: how much of rStar's effectiveness comes from the action-space structure (the concept of five diverse reasoning primitives) versus the specific prompt engineering of the few-shot examples?

Practical Applications and Downstream Use Cases

On-device mathematical reasoning assistants using Phi3-mini-class models. The paper shows Phi3-mini (3.8B parameters) with rStar achieves 90.67% on GSM8K and 94.10% on SVAMP — accuracies that make it practically useful as a math tutor or homework assistant. A deployment on a phone or laptop would run the generator-discriminator pair entirely locally (using Phi3-mini as the generator and either a second Phi3-mini instance or a differently-initialized checkpoint as discriminator), providing high-accuracy math reasoning without cloud connectivity. Based on Table 7's cost estimates for larger models (~150 model calls per question, ~350k tokens generated), a 3.8B model on modern mobile hardware could plausibly solve a GSM8K problem in seconds to tens of seconds, making interactive tutoring feasible. The key deployment advantage is that this requires no training data, no fine-tuning, and no distillation from GPT-4 — the system runs entirely from the pretrained weights that already ship with the device.

Batch verification of training data for self-improvement pipelines. When using SLMs to generate training data for themselves (e.g., for domain-specific fine-tuning via rejection sampling), the quality of the generated data depends critically on answer verification. Standard approaches use majority voting (requiring many samples per question and failing when the model is weak) or GPT-4-as-judge (reintroducing teacher dependency). rStar's mutual consistency offers a teacher-free alternative: for each training question, run the 32-rollout MCTS to generate candidate answers, apply the discriminator to filter, and include only mutually-consistent trajectories in the training set. Based on Table 2's results, this would dramatically increase the yield of correct training examples compared to majority voting: for LLaMA2-7B on GSM8K, majority voting achieves 27.22% accuracy on generated trajectories, while rStar selects 63.91% correct answers. This 2.3× increase in training data quality would directly improve downstream fine-tuning results, without requiring access to any superior model.

Deploying the cheapest viable model per query through adaptive model selection. The paper shows rStar's gains vary dramatically with base model strength: LLaMA2-7B improves by +51.4 points on GSM8K, while Phi3-mini improves by only +7.2 points. A cost-aware deployment system could maintain a portfolio of models (e.g., a very cheap LLaMA2-7B, a mid-range Mistral-7B, and a capable Phi3-mini), use a lightweight difficulty estimator (perhaps the self-consistency confidence from 2–4 preliminary CoT samples) to gauge how hard each incoming query is, and route it to the cheapest model that can achieve acceptable accuracy with rStar's inference-time augmentation. Easy questions (high initial confidence) go to LLaMA2-7B with many rollouts; medium questions go to Mistral-7B; only genuinely hard questions use Phi3-mini or escalate to a cloud API. This mirrors the compute-optimal scaling philosophy from Snell et al. (2024) but applied to model selection rather than inference-strategy selection, and rStar's results provide the per-model accuracy curves needed to optimize such a system.

Dependency tree

Papers this one builds on, walking backwards through the same domain and shared topics.

Understanding and Mitigating Tokenization Bias in Language Models2024· reasoning← in-domain predecessor
- DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data2024· reasoning← in-domain predecessor
Scaling Synthetic Data Creation with 1,000,000,000 Personas2024· data← topic thread
- The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale2024· data← in-domain predecessor
- MOSEL: 950,000 Hours of Speech Data for Open-Source Speech Foundation Model Training on EU Languages2024· data← similar topic
Why Does Self-Distillation (Sometimes) Degrade the Reasoning Capability of LLMs?2026· reasoning← similar topic
- SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training2025· alignment← LLM-judged similar
- LongCat-Flash-Prover: Advancing Native Formal Reasoning via Agentic Tool-Integrated Reinforcement Learning2026· reasoning← in-domain predecessor
- jina-embeddings-v5-text: Task-Targeted Embedding Distillation2026· training-methods← topic thread
rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking2025· reasoning← similar topic
- OpenAI o1 System Card2024· safety← topic thread
- Multiplex Thinking: Reasoning via Token-wise Branch-and-Merge2026· reasoning← similar topic
- R-Horizon: How Far Can Your Large Reasoning Model Really Go in Breadth and Depth?2025· reasoning← similar topic

What it influenced

Later papers in the same chain. Direction reversed.

DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search2024· reasoning→ in-domain predecessor
- DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search2025· training-methods→ LLM-judged similar
- Attention Heads of Large Language Models: A Survey2024· reasoning→ in-domain predecessor
- Exponential Speedups by Rerooting Levin Tree Search2024· reasoning→ similar topic
- Offline Reinforcement Learning for LLM Multi-Step Reasoning2024· reasoning→ similar topic
- HunyuanProver: A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving2024· reasoning→ similar topic
Source2Synth: Synthetic Data Generation and Curation Grounded in Real Data Sources2024· data→ topic thread
A Case Study of Web App Coding with OpenAI Reasoning Models2024· code→ topic thread
- Not All LLM Reasoners Are Created Equal2024· reasoning→ LLM-judged similar
- OPENCODER: THE OPEN COOKBOOK FOR TOP-TIER CODE LARGE LANGUAGE MODELS2024· code→ in-domain predecessor
- A Comparative Study on Reasoning Patterns of OpenAI's o1 Model2024· reasoning→ topic thread
STaR: Bootstrapping Reasoning With Reasoning2022· reasoning→ similar topic
- Large Language Models are Zero-Shot Reasoners2022· reasoning→ in-domain predecessor
- REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewards2025· reasoning→ similar topic
- Fantastic Reasoning Behaviors and Where to Find Them: Unsupervised Discovery of the Reasoning Process2025· reasoning→ similar topic
rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking2025· reasoning→ similar topic
- Kimi k1.5: Scaling Reinforcement Learning with LLMs2025· reasoning→ in-domain predecessor
- DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning2025· rl-training→ topic thread