PaperlayerView exact revision on arXiv

Source-linked AI summary

Reasoning Language Models: A Blueprint

Maciej Besta, Julia Barth, Eric Schreiber, Ales Kubicek, Afonso Catarino, Robert Gerstenberger, Piotr Nyczyk, Patrick Iff, Yueling Li, Sam Houliston, Tomasz Sternal, Marcin Copik, Grzegorz Kwaśniewski, Jürgen Müller, Łukasz Flis, Hannes Eberhard, Zixuan Chen, Hubert Niewiadomski, Torsten Hoefler

arXiv:2501.11223v4cs.AIcs.CL

TL;DR

RLM architectures remain costly, proprietary, and difficult to understand, with their component interactions poorly understood. The paper organizes RLM designs in a modular blueprint and provides x1 for experimentation; it also identifies Trace-Based Supervision as a possible direction for training implicit RLMs.

  • Problem

    High costs, proprietary systems, and opaque, complex architectures leave the detailed design of effective, low-cost, scalable RLMs poorly understood.

    Source: §1 · pp. 1–2

  • Method

    The paper presents a modular RLM blueprint, with architectural, mathematical, and algorithmic descriptions, and introduces x1 for experimentation.

    Source: §1 · p. 2

  • Results

    The blueprint maps diverse reasoning approaches into a shared framework, and the authors present x1 as a platform for prototyping RLM architectures.

    Source: §11 · p. 24

  • Takeaways & Limitations

    The authors identify Trace-Based Supervision as a future direction that may train more powerful implicit RLMs and improve generalization.

    Source: §11 · p. 24

    Prompting alone to elicit self-critique and refinement often fails to produce consistently improved results, motivating structured training and careful operator design.

    Source: §8 · p. 21

Abstract

from arXiv · show

Reasoning language models (RLMs), also known as Large Reasoning Models (LRMs), such as OpenAI's o1 and o3, DeepSeek-R1, and Alibaba's QwQ, have redefined AI's problem-solving capabilities by extending LLMs with advanced reasoning mechanisms. Yet, their high costs, proprietary nature, and complex architectures - uniquely combining reinforcement learning (RL), search heuristics, and LLMs - present accessibility and scalability challenges. To address these, we propose a comprehensive blueprint that organizes RLM components into a modular framework, based on a survey and analysis of all RLM works. This blueprint incorporates diverse reasoning structures (chains, trees, graphs, and nested forms), reasoning strategies (e.g., Monte Carlo Tree Search, Beam Search), RL concepts (policy, value models and others), supervision schemes (Outcome-Based and Process-Based Supervision), and other related concepts (e.g., Test-Time Compute, Retrieval-Augmented Generation, agent tools). We also provide detailed mathematical formulations and algorithmic specifications to simplify RLM implementation. By showing how schemes like LLaMA-Berry, QwQ, Journey Learning, and Graph of Thoughts fit as special cases, we demonstrate the blueprint's versatility and unifying potential. To illustrate its utility, we introduce x1, a modular implementation for rapid RLM prototyping and experimentation. Using x1 and a literature review, we provide key insights, such as multi-phase training for policy and value models, and the importance of familiar training distributions. Finally, we discuss scalable RLM cloud deployments and we outline how RLMs can integrate with a broader LLM ecosystem. Our work demystifies RLM construction, democratizes advanced reasoning capabilities, and fosters innovation, aiming to mitigate the gap between "rich AI" and "poor AI" by lowering barriers to RLM design and experimentation.

1 INTRODUCTION

The introduction frames RLM design as an opaque, costly challenge and proposes a modular blueprint plus x1 to support constructing and experimenting with diverse RLMs.

1 INTRODUCTION

  • High costs, proprietary systems, and poorly understood component interactions make it difficult to design RLMs that are effective, low-cost, and scalable.The question spans specialized components such as policy, value, and reward models, search, and supervision.Source: §1 · pp. 1–2
  • The blueprint organizes RLM building blocks into a framework described through architecture, mathematical formulations, and algorithmic specifications.It includes chains, trees, graphs, nested structures, reasoning operations, and outcome- and process-based supervision.Source: §1 · p. 2
  • The analysis maps approaches including LLaMA-Berry, QwQ, Journey Learning [123], Beam Search, CoT, ToT, and Graph of Thoughts into the blueprint.It also considers RAG, data stores, and tools.Source: §1 · p. 2
  • The authors introduce x1 as a modular implementation for developing and experimenting with RLM architectures, including training, inference, and synthetic-data generation.They describe it as supporting optimizations and scalability, including batch processing.Source: §1 · p. 2
  • The work presents the blueprint and x1 as ways to lower barriers to RLM design and experimentation and to address the “rich AI”–“poor AI” divide.The authors state this as an aim of the work.Source: §1 · p. 2

2 EVOLUTION & FOUNDATIONS OF RLMS

The section traces RLMs to the convergence of LLMs, reinforcement learning, and high-performance computing, then distinguishes their reasoning styles and architectures.

2.1 Basic Pillars of Reasoning LMs

  • RLMs emerged from advances in LLMs, reinforcement-learning systems, and computing capacity, including HPC.The section uses GPT-4o [119] and AlphaZero [138] as examples of the first two threads.Source: §2.1 · pp. 2–3, Figure 2 · p. 3

2.1.1 Large Language Models: A Reservoir of Knowledge

  • LLMs such as GPT-4o and LLaMA [55] encode broad world knowledge but often rely on next-token prediction rather than explicit, iterative problem-solving.The section contrasts this with the need for structured reasoning mechanisms.Source: §2.1.1 · p. 3

2.1.2 Reinforcement Learning: Exploring and Innovating

  • Reinforcement learning enables exploration of large search spaces, while its traditional systems lacked real-world knowledge and capacity for complex, multifaceted reasoning tasks.The section presents integrating RL with LLMs as combining exploration and optimization with language-model knowledge.Source: §2.1.2 · p. 3

2.1.3 HPC: Scalability & Efficiency

  • HPC scaling now relies on heterogeneous processors and distributed parallelism, while sparsity, quantization, and pruning help mitigate energy demands.The section notes that rising miniaturization costs prompted alternatives such as parallelism and heterogeneous computing.Source: §2.1.3 · p. 4

2.2 The Convergence: System 2 Thinking in AI

  • The combination of LLM knowledge, RL exploration and optimization, and HPC support is described as enabling System 2 Thinking and explicit, deliberate reasoning.The section says RL and HPC together let models navigate large decision spaces, evaluate strategies, and iteratively refine solutions.Source: §2.2 · p. 4

2.3 Interpolation (LLMs) vs. Extrapolation (RLMs)

  • Where standard LLMs interpolate within training-distribution patterns, RLMs use structured exploration to extrapolate beyond those boundaries.The section characterizes this as a shift from pattern completion to active problem-solving.Source: §2.3 · p. 4

2.4.1 Implicit Reasoning Models

  • The hierarchy distinguishes implicit RLMs such as QwQ, whose reasoning is embedded in model weights, from models with explicit reasoning mechanisms.Implicit reasoning is described as opaque and not explicitly disentangled or manipulated.Source: §2.4.1 · p. 4, §2.4 · p. 4

2.4.2 Explicit Reasoning Models

  • Explicit designs such as LLaMA-Berry and Marco-o1 [187] use external mechanisms, including MCTS with RL, to simulate, evaluate, and refine solutions iteratively.Separating reasoning from static model knowledge supports greater flexibility and interpretability, though explicit reasoning can later be internalized through training.Source: §2.4.2 · p. 5

3 ESSENCE OF REASONING LMS

The section presents RLMs as coordinated inference, training, and data-generation pipelines, then extends the blueprint across architectural variants and integration with broader LLM agent ecosystems.

3.1 Basic Architecture, Pipelines, & Concepts

  • RLMs comprise inference, training, and data-generation pipelines; inference serves user requests, while independent data generation mirrors inference and supplies data for model retraining.Training and data generation together can provide self-learning capabilities.Source: §3.1 · p. 5

3.1.1 Inference

  • Prompts root a usually tree-structured search whose nodes are coherent reasoning steps; policy models generate steps, value models score paths, and search ends at a terminal answer.The value model evaluates a path from a node, while a reward model can assess an individual reasoning step.Source: §3.1.1 · p. 5, §3.1.2 · p. 5

3.1.2 Training

  • Training uses supervised data and continual self-learning on generated data; collected labels may be outcome-based, process-based, or trace-based, with trace labels recording applied operators.Generated data is stored in a replay buffer for unsupervised training.Source: §3.1.2 · p. 5

3.2 Encompassing Diverse RLM Architectures

  • Nesting lets an MCTS node contain an entire reasoning structure, while Journey Learning [123] rewires and consolidates paths for subsequent reasoning; the blueprint also covers variants beyond these cases.The blueprint is presented as a general framework for existing designs and future RLM innovations.Source: §3.2 · p. 7

3.3 Integration with Broader LLM Agent Ecosystems

  • RLMs can use retrieval, web queries, databases, and computational tools during inference or data generation, with policy or value models extending reasoning through these resources.A value or reward model could query a database to verify intermediate steps or retrieve context.Source: §3.3 · p. 7

4 BLUEPRINT FOR REASONING LMS

The blueprint decomposes RLMs into reasoning schemes, operators, models, and pipelines, providing a modular vocabulary for designing and analyzing systems. It covers alternative reasoning structures and strategies, operator types, training approaches, test-time compute, and pipeline objectives.

4.1 Overview & Main Components

  • An RLM is a composition of a reasoning scheme, operators and associated models, and pipelines that orchestrate them for training, inference, or data generation.Figure 5 places the reasoning scheme, operators, and models in separate toolboxes, with pipelines in the center.Source: §4.1 · p. 7, Figure 5 · p. 8

4.2 Reasoning Scheme

  • Reasoning steps range from tokens to full text segments, while structures connect them as chains, trees, graphs, or nested forms.Step granularity is a design choice; nested structures can place a chain inside a tree node.Source: §4.2.1 · p. 7, §4.2.2 · p. 9

4.2.3 Reasoning Strategy

  • Reasoning strategies govern how structures evolve, with examples including MCTS, Beam Search, and ensembles; these differ from token-level decoding strategies.MCTS balances exploration and exploitation, while Beam Search retains a fixed number of highly ranked continuations.Source: §4.2.3 · p. 9

4.3.1 Structure Operators

  • Structure operators generate, aggregate, prune, or restructure reasoning steps and paths to change the search structure.Journey Learning [123] converts a tree into a chain, while diversity can be steered through temperature or search trade-offs.Source: §4.3 · p. 9, §4.3.1 · p. 9

4.3.2 Traversal Operators

  • Traversal, update, and evaluation operators select or revisit steps, improve content or scores, and assess terminal or intermediate reasoning.Value estimators judge a step by its expected contribution to a correct final outcome.Source: §4.3.2 · p. 10, §4.3.3 · p. 10, §4.3.4 · p. 10

4.3.5 Discussion: Test-Time Compute

  • Test-time compute allocates more inference resources to difficult tasks, which the blueprint can implement through more generation, refinement, path exploration, and aggregation.These mechanisms expand possibilities for harder problems while aggregation can retain promising paths.Source: §4.3.5 · pp. 10–11

4.4 Models

  • Models implement operators, commonly with policy models for generation and value models for evaluation, and use training paradigms and supervision schemes such as OBS or PBS.OBS uses input and outcome labels; PBS also labels intermediate steps and is harder to gather, while proposed TBS adds operator-sequence traces.Source: §4.4 · p. 11, §4.4.1 · p. 11, §4.4.2 · p. 11

4.5 Pipelines

  • Pipelines specify how schemes, operators, and models interact for objectives including inference, model training, and synthetic data generation.The paper provides algorithmic specifications for inference, training, and data generation pipelines.Source: §4.5 · pp. 11–12, Table 1 · p. 12

5 EXPRESSING EXISTING SCHEMES

The blueprint represents existing RLMs and related approaches as combinations of reasoning structures, strategies, operators, models, and pipelines. Its examples range from explicit search systems to implicit reasoning models and structured prompting.

5 EXPRESSING EXISTING SCHEMES

  • The blueprint accounts for common MCTS-based explicit RLMs as well as generalized designs, implicit RLMs, and structured prompting schemes.The analysis covers reasoning operators and pipelines as well as structures and strategies.Source: §5 · p. 12

5.1 Explicit RLMs

  • Typical explicit RLMs use MCTS over reasoning-step trees, while Journey Learning restructures selected tree branches into a long chain for internalization.Typical systems use generation, evaluation, and value updates; Journey Learning [123] trains weights to generate long reasoning chains directly.Source: §5.1 · pp. 12–13

5.2 Implicit RLMs

  • QwQ generates implicit reasoning autoregressively, while CoT, Self-Consistency, ToT, and GoT exemplify structured prompting designs.CoT uses a chain, ToT a tree with branch evaluation, and GoT a graph guided by an external controller.Source: §5.2 · p. 13, §5.3 · p. 13

6 HOW TO USE THE BLUEPRINT

The tutorial presents a sequence for applying the blueprint: choose the reasoning scheme, specify its operators, then determine models and training details. Design choices are framed around the application domain and practical trade-offs.

6.1 Part 1: Define the Reasoning Scheme

  • Choose a reasoning structure, step granularity, and strategy to fit the application, balancing token cost, exploration, implementation complexity, and compute.Chains are described as affordable, trees as costly but exploratory, and token-level steps as potentially more precise but computationally demanding.Source: §6.1 · p. 13

6.2 Part 2: Define the Operators

  • For MCTS, start with generate, select, and backpropagate, then consider operators such as backtrack and decide which operations use neural models.Operator implementation choices affect computational complexity and system flexibility.Source: §6.2 · p. 13

6.3 Part 3: Determine the Training Details

  • Set training details by defining the domain, model architectures, and base models in light of the target tasks and reasoning design.The tutorial identifies policy models for generation and value models for evaluation as a typical MCTS pairing.Source: §6.3 · p. 14
  • Prepare policy and value data, initialize models with supervised fine-tuning, collect further MCTS data, then continue training with SFT or reinforcement learning.Policy data may come from the paper’s pipeline or CoT prompting; value data may come from full MCTS simulations.Source: §6.3 · p. 14

7 FRAMEWORK X1: DESIGN & IMPLEMENTATION

This section presents x1 as an extensible framework for prototyping RLMs, covering its MCTS-based reasoning, model training, scaling architecture, and analysis of token-probability distributions. It describes how uncertainty patterns and metrics can inform reasoning strategies while noting that reliable benchmarking requires sufficiently large samples and that metric usefulness varies by task.

7.1 Reasoning Scheme

  • x1 is an extensible, minimalist framework for designing and experimenting with RLMs, combining tree-structured reasoning with MCTS and value-guided exploration.Its operators generate and evaluate nodes, select paths, and update the tree; generation can use Diverse Beam Search or high-temperature sampling.Source: §7 · p. 14, §7.1 · p. 14, §7.2 · p. 14

7.3.1 Training the Policy Model

  • The policy model generates one reasoning step at a time, using an eois token to mark intermediate steps and eos to mark completion of the reasoning chain.This dual-token scheme explicitly distinguishes ongoing reasoning from a completed solution, supporting stepwise decomposition and interpretability.Source: §7.3.1 · pp. 14–15

7.3.2 Training the Value Model

  • The value model estimates a node’s q-value as the expected cumulative reward discounted by the steps to reach it, with sparse rewards assigned only at the terminal step.Because most reasoning tasks can be evaluated only at the final answer, the reward signal is available when the chain reaches its terminal state.Source: §7.3.2 · p. 15

7.4 Enabling Scalability and Efficiency

  • x1 separates policy and value servers to support independent scaling, parallel MCTS instances, batching, and tailored resource allocation, and describes deployment across HPC systems and clouds.The scaling blueprint also covers storage, high-performance communication, parallelism, and resource-saving options such as shared base models with task-specific adapters.Source: §7.4 · p. 15, §7.5 · p. 16

7.6.1 Relevance of Token Probability Distribution

  • Token distributions can guide reasoning choices: flat distributions suggest exploration or delaying a step, one dominant token can support a faster choice, and several likely tokens favor comparing alternatives.A dominant token can still be misleading, while flat distributions may require extra evaluation; the framework uses distribution patterns to inform efficiency, confidence, and balanced exploration.Source: §7.6.1 · p. 17

7.6.2 Analyzing Token Probability Distribution

  • Variance, entropy, VarEntropy, and Gini characterize distribution shape and uncertainty, helping distinguish flat, dominant-token, and multiple-high-probability patterns.VarEntropy captures changes in entropy, while Gini reflects probability concentration; together, the metrics provide complementary views for reasoning and model-development decisions.Source: §7.6.2 · pp. 17–18

7.6.3 Example Results

  • Example outputs show that close top-two probabilities with much smaller alternatives can motivate forking, whereas one dominant probability favors more deterministic reasoning.A relatively large sum of remaining probabilities indicates a flatter, more uncertain distribution where clarification, added context, or revisiting earlier steps may help.Source: §7.6.3 · p. 18
  • Zero-shot prompting shows lower overall uncertainty, but high-probability tokens may signal data leakage, and <thought> tokens have high prediction uncertainty.The passage cautions that token granularity can make next-token probabilities roughly even across the vocabulary in some contexts.Source: §7.6.3 · p. 18
  • High VarEntropy with low entropy can favor tree search, while low VarEntropy with high entropy may call for clarification or intermediate-step refinement.The section links these uncertainty patterns to balancing exploration and exploitation during reasoning.Source: §7.6.3 · pp. 18, 21
  • The Gini coefficient can better highlight task-critical reasoning tokens than entropy or VarEntropy, which may also flag formatting or stylistic tokens.It captures inequality in token probabilities in vital reasoning areas.Source: §7.6.3 · p. 18

7.7 Benchmarking RLMs

  • At least 500 evaluated samples are needed for single-digit-percentage error variability; benchmarks should include at least 200 samples per category and 500 across all categories.These recommendations aim to mitigate variability-driven bias and support statistically robust comparisons.Source: §7.7 · p. 21, Figure 10 · p. 21

8 EXAMPLE INSIGHTS FOR EFFECTIVE RLMS

The section offers practical RLM design insights drawn from the literature and analyses using x1: assess reasoning processes, stage training, use familiar distributions, and avoid prompt-only self-critique.

Use Process-Based Evaluation

  • Process-based evaluation is described as more reliable than ORMs and provides richer feedback by assessing reasoning steps and their relationships.The authors say this helps refine reasoning paths and improve accuracy and generalization.Source: §8 · p. 21

Use Two Phases for Training

  • A dedicated SFT phase before RL can maintain standard-benchmark performance while improving reasoning, as reported for process reinforcement through implicit rewards [41].Source: §8 · p. 21

Train on Familiar Distributions

  • PRIME [41], [176] reports curated sequences such as eois avoid performance degradation, while familiar distributions in rStar-Math [57] stabilize training faster and improve reasoning quality.Source: §8 · p. 21

Be Careful with Prompting LLMs to Critique and Evaluate

  • Prompting alone to elicit self-critique often leads to instability; explicitly training iterative refinement outperforms simple prompting.The section also cites a study reporting that prompting to refine reasoning does not consistently improve results.Source: §8 · p. 21

9 BENCHMARKS FOR RLMS

The section surveys benchmarks for mathematical, logical, coding, causal, commonsense, and reasoning-utility tasks, including agent and retrieval-augmented generation capabilities.

9.1 Mathematical Reasoning

  • Mathematical benchmarks range from fixed datasets to templates, while FrontierMath’s expert-crafted modern problems are solved by current state-of-the-art models at less than 2%.The authors recommend templated versions where available to reduce contamination risk and provide a more accurate performance measure.Source: §9.1 · pp. 21–22

9.2 Logical Reasoning

  • Logical benchmarks span formal logic and theorem proving; PrOntoQA’s artificial ontology graphs emphasize step-by-step reasoning, while BIG-Bench covers over 200 tasks.Source: §9.2 · pp. 22–23

9.3 Coding

  • Coding benchmarks include ODEX, SWE-bench, DS-1000, APPS, MBPP, and HumanEval.Source: §9.3 · p. 23

9.4 Causal Reasoning

  • Causal benchmarks cover cause-effect and counterfactual tasks, but many are solved or weakly applicable to real-world language-model tasks, limiting current RLM evaluation.Source: §9.4 · p. 23

9.5 Commonsense Reasoning

  • Commonsense benchmarks span everyday knowledge and specialized expertise; GPQA Diamond tests questions answerable by relevant PhDs but challenging to experts in unrelated fields.Source: §9.5 · p. 23

9.6 Reasoning Utilities

  • Reasoning-utility benchmarks assess agent capabilities through environments such as GAIA and WebArena, alongside benchmarks for retrieval-augmented generation.Source: §9.6 · p. 23

10 RELATED ANALYSES

Prior analyses cover reasoning improvements to standard LLMs and explicit reasoning models, but the paper identifies gaps in systematic blueprints and open implementations. It positions its modular framework and x1 implementation as practical complements to those analyses.

10.1 Reasoning with Standard LLMs

  • Standard-LLM work covers training, prompting, and in-context reasoning, but reviews often lack code, formal language, and explicit reasoning models; the blueprint integrates techniques modularly.Source: §10.1 · pp. 23–24

10.2 Explicit Reasoning Models

  • Explicit-reasoning analyses include inference-time refinement and verifier or reinforcement-learning roadmaps, while the paper adds a foundational framework and modular, scalable implementation.Source: §10.2 · p. 24

11 CONCLUSION

The paper presents a modular RLM blueprint and x1 for prototyping, alongside formal MDP/MCTS foundations and distinctions among reward and value models. It also identifies future directions including trace-based supervision and scalable cloud deployment.

11 CONCLUSION

  • The blueprint organizes RLM structures, operations, and training schemes, while x1 provides a modular platform for prototyping novel architectures.The conclusion describes the blueprint as a flexible toolbox and x1 as a minimalist, user-friendly experimentation platform.Source: §11 · p. 24
  • Trace-Based Supervision extends process supervision with labeled traversal traces and may support implicit RLMs that internalize structures and improve generalization.The paper presents TBS as a future research direction, not an evaluated result.Source: §11 · p. 24
  • The blueprint proposes nested tree and graph architectures for multilayered tasks, and modular cloud deployments for distributing compute-intensive work.The conclusion frames these as future directions for expanding applications and scalability.Source: §11 · p. 24

SION PROCESSES FOR REASONING TASKS

  • The mathematical framework models reasoning chains with MDPs and uses MCTS to search the space of possible chains.An MDP represents processes; MCTS explores the resulting state space.Source: Appendix A · p. 25, §A.2 · p. 26

A.1.2 MDPs in the RLM Setting

  • In the RLM setting, states are partial reasoning sequences, and actions append reasoning steps; common sparse rewards arrive only at terminal answers.The discount factor controls the weight of future rewards, with higher values emphasizing long-term reasoning success.Source: §A.1.2 · p. 25

A.2 Monte Carlo Tree Search

  • MCTS iteratively selects and expands tree nodes, simulates paths to terminal states for rewards, and backpropagates estimates and visit counts.The search stops at a specified iteration count, computational budget, or convergence criterion.Source: §A.2 · p. 26

B.1 Outcome- vs. Process-Based Reward Models

  • Outcome-based reward models score final outcomes, whereas process-based models score individual steps and provide denser feedback but require extensive, costly annotations.Outcome-based models can misjudge intermediate steps; process-based annotations may come from people, LLMs, or automated methods.Source: §B.1 · pp. 26–27

B.2 Outcome-Driven Process-Based Reward Models

  • Outcome-Driven Process-Based Reward Models aggregate simulated path outcomes into step-wise labels, while value models estimate future returns and Q-value models guide action-specific MCTS choices.O-PRMs avoid extensive human annotation but retain outcome-related failure modes; the paper favors process-based value models for sparse rewards and Q-VMs for MCTS.Source: §B.2 · p. 27, §B.3.2 · p. 28, §B.3.4 · p. 28

B.4 Evaluation Schemes

The section introduces further categorizations and details concerning overall evaluation.

B.4 Evaluation Schemes

  • The section signals additional categorizations and details about overall evaluation.The supplied passage does not specify those categorizations.Source: §B.4 · p. 28

B.4.1 Evaluation Types

Reasoning-step evaluation can use relative comparisons, absolute scores, or text feedback, selected according to the evaluation goal.

B.4.1 Evaluation Types

  • Relative evaluations rank multiple reasoning steps, including through Bradley-Terry pairwise preferences that maximize the reward gap between chosen and rejected steps.The passage cites Bradley-Terry as an example.Source: §B.4.1 · p. 28
  • Absolute evaluations assign scalar scores or binary labels; regression conveys degree of qualities such as coherence, while classification naturally represents correctness.Absolute scores can also be converted into rankings when needed.Source: §B.4.1 · pp. 28–29
  • Text-based evaluations, including LLM-as-a-Judge and self-critique [132], provide detailed rationales useful for structural refinement.The passage distinguishes these from numerical guidance.Source: §B.4.1 · p. 29

B.4.2 Evaluation of Reasoning Steps

The section surveys evaluation options for reasoning steps and describes x1’s MCTS setup, which trains with verifier-provided terminal rewards and uses a value model at inference.

B.4.2 Evaluation of Reasoning Steps

  • Numerical evaluations compare nodes to steer MCTS, while text evaluations better guide structural refinements than search paths.Evaluation approaches include external value models, policy-model scoring, heuristics, simulations, and domain-specific tools.Source: §B.4.2 · p. 29
  • External evaluators include reward, state-value, state-action-value, and pairwise models; internal methods prompt the policy model for scores or use its uncertainty.Tool-based checks can provide objective feedback in well-defined domains, though their applicability is limited to those domains.Source: §B.4.2 · p. 29

C.1.1 Setup and Notation

  • x1 assigns terminal answers rewards of 1 or −1 according to correctness, with value estimates bounded between −1 and 1.Its discount factor is set between 0.95 and 1 to avoid over-penalizing long reasoning sequences.Source: §C.1.1 · p. 29
  • x1 represents intermediate reasoning steps as actions and uses a pre-trained transformer value model to estimate process-based Q-values.The model adds three linear layers and a shifted, rescaled sigmoid; training assumes access to a verifier for final-answer correctness.Source: §C.1.1 · p. 30

C.1.2 MCTS Algorithm

  • During training, an external verifier’s terminal reward is backpropagated through the tree; during inference, x1 relies on its value model.The true reward anchors Q-value estimates, and the selected path with the highest terminal value estimate supplies the answer.Source: §C.1.2 · p. 30
  • x1 uses a node-based PUCT selection variant without a prior, and expands each selected leaf with M children to explore alternative reasoning paths.Its node statistics include visit counts, transition Q-value estimates, and terminality.Source: §C.1.2 · p. 30

C.2 Training Phase 1

Phase 1 prepares policy and q-value models for structured reasoning and later MCTS-based exploration. It uses supervised datasets of reasoning sequences and their corresponding next-step targets or trajectory scores.

C.2 Training Phase 1

  • Phase 1 uses supervised fine-tuning to prepare policy and q-value models to generate and evaluate reasoning trajectories for later MCTS-based exploration.The policy learns semantically coherent reasoning steps, while the q-value model scores intermediate and terminal states.Source: §C.2 · pp. 30–31

C.2.1 Datasets Generation and Preparation

  • The policy dataset pairs prompts and reasoning sequences with the next reasoning step or final answer, while the q-value dataset pairs reasoning sequences with scores.A base LLM and verifier program can generate and label q-value training data.Source: §C.2.1 · p. 31

C.2.2 SFT of the Policy Model

  • Completion-only SFT trains the pretrained policy model to predict the next reasoning step from each prompt using cross-entropy loss.The target completion may be a subsequent reasoning step or the final answer.Source: §C.2.2 · p. 31, §C.2.1 · p. 31

C.2.3 Q-Value Model Training

The q-value model is trained to score reasoning trajectories, then updated alongside the policy during a second, MCTS-driven training phase. Policy refinement can use RL, preference optimization, or SFT, with MCTS-derived values also informing advantage estimates.

C.2.3 Q-Value Model Training

  • The q-value model learns scalar trajectory scores using regression for continuous rewards or classification for binary rewards and preference pairs.Its scores later guide policy refinement and search accuracy.Source: §C.2.3 · pp. 31–32

C.3 Training Phase 2

  • Phase 2 alternates MCTS generation of reasoning sequences with RL-based policy fine-tuning and continual q-value model updates.The first-phase models need sufficient pretraining for stable second-phase training.Source: §C.3 · p. 32

C.3.1 Training Algorithm

  • For each prompt, the training algorithm builds an MCTS tree, prunes paths that did not reach terminal states, and stores retained nodes and values in a replay buffer.Batches from that buffer update both the policy and q-value model.Source: §C.3.1 · pp. 32–33

C.3.2 Policy Update

  • Policy updates can use PPO or REINFORCE for evaluated online trajectories, DPO for preference pairs, or SFT on high-value reasoning sequences.PPO may also use KL regularization or an entropy term.Source: §C.3.2 · pp. 33–34

C.3.3 Advantage Calculation

  • The proposed advantage calculation uses MCTS-backpropagated values together with the q-value model as an alternative to training a PPO critic from scratch on bootstrapped rewards.MCTS values incorporate child estimates and potentially terminal reward signals.Source: §C.3.2 · p. 33, §C.3.3 · p. 34

C.3.4 Q-Value Model Update

  • During Phase 2, the q-value model is updated by squared-error minimization to match MCTS-backpropagated values, keeping it in-distribution with the policy’s new outputs.The authors state this also benefits value-model accuracy.Source: §C.3.4 · p. 34

D.1 Phase 1 Policy Model Training

The appendix specifies training procedures for policy, value, and q-value models, including alternative reward designs and the role of terminal-state scoring. It also describes how q-value models address a terminal-state limitation of value models.

D.1 Phase 1 Policy Model Training

  • Policy training introduces an eois token to delimit reasoning steps and uses self-generated training data produced with greedy decoding.The assistant-token benefit was observed for LLaMA models, but may not generalize to other base models.Source: §D.1 · p. 34

D.2 Phase 1 Value Model Training

  • The process-based value model replaces costly simulations at inference with predictions trained on simulation data rather than true value functions.It takes reasoning-step sequences as input and outputs a scalar value.Source: §D.2 · p. 35

D.2.1 Binary Rewards: Modeling the Likelihood of a Correct Terminal State

  • With binary rewards, MCTS estimates a state’s likelihood of leading to a correct answer from the ratio of correct simulations, and terminal-state predictions estimate terminal reward during inference.A predicted likelihood above a threshold such as 0.5 maps to reward 1; otherwise it maps to 0.Source: §D.2.1 · pp. 35–36

D.2.2 Continuous and Bounded Rewards: Modeling the Expected Future Reward

  • For continuous bounded rewards, simulations average discounted terminal rewards, and the value model uses a scaled, shifted sigmoid with MSE training.The authors report tanh and clipped linear outputs were unstable, and note that the discounted estimator typically underestimates value due to false negatives.Source: §D.2.2 · p. 36, §D.2.2.3 · p. 36

D.3 State Action Value Function Modeling

  • A q-value represents the expected cumulative reward of taking an action in a state under the policy.For sparse rewards, earlier rewards are zero and the q-value simplifies accordingly.Source: §D.3 · p. 37

D.3.1 Process-Based Q-Value Modeling

  • For nonterminal actions, q-value training targets can be estimated with Monte Carlo simulations, while the final action’s q-value is its immediate reward.The q-value model predicts a scalar from the sequence of past reasoning steps and current action.Source: §D.3.1 · p. 37

D.3.2 The Difference Between Value and Q-Value Models

  • Q-value models give the final action a meaningful correctness evaluation, whereas value models assign terminal states zero.This distinction lets q-value models assess whether the final step leads to a correct response during inference.Source: §D.3.2 · p. 38
Loading 2501.11223v4…