# Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspective

###### Abstract

OpenAI o1 represents a significant milestone in Artificial Inteiligence, which achieves expert-level performances on many challanging tasks that require strong reasoning ability. OpenAI has claimed that the main techinique behinds o1 is the reinforcement learining ( OpenAI, 2024a ; OpenAI, 2024b ) . Recent works use alternative approaches like knowledge distillation to imitate o1’s reasoning style, but their effectiveness is limited by the capability ceiling of the teacher model. Therefore, this paper analyzes the roadmap to achieving o1 from the perspective of reinforcement learning, focusing on four key components: policy initialization, reward design, search, and learning. Policy initialization enables models to develop human-like reasoning behaviors, equipping them with the ability to effectively explore solution spaces for complex problems. Reward design provides dense and effective signals via reward shaping or reward modeling, which is the guidance for both search and learning. Search plays a crucial role in generating high-quality solutions during both training and testing phases, which can produce better solutions with more computation. Learning utilizes the data generated by search for improving policy, which can achieve the better performance with more parameters and more searched data. Existing open-source projects that attempt to reproduce o1 can be seem as a part or a variant of our roadmap. Collectively, these components underscore how learning and search drive o1’s advancement, making meaningful contributions to the development of LLM.

One thing that should be learned from the bitter lesson is the great power of general purpose methods, of methods that continue to scale with increased computation even as the available computation becomes very great. The two methods that seem to scale arbitrarily in this way are search and learning . — Richard Sutton, 2019

## 1 Introduction

The field of Artificial Intelligence (AI) has witnessed unprecedented exploration and advancement of Large Language Models (LLMs) over the past two years. LLMs have progressively evolved to handle increasingly sophisticated tasks such as programming and solving advanced mathematical problems. OpenAI o1 represents a significant milestone in AI, which can generate very long reasoning process and conduct human-like reasoning actions like clarifying and decomposing questions, reflecting and correcting previous mistakes, exploring new solutions when encountering failure modes. The o1 model dramatically transcended the reasoning capabilities of preceding LLMs, achieving performance comparable to PhD-level proficiency. Its remarkable reasoning achievements signify OpenAI’s progression to the second stage (“Reasoner”) in their five-stage roadmap to Artificial General Intelligence (AGI).

The blog and system card of o1 demonstrate that the performance of o1 consistently improves with increasing the computation of reinforcement learning and inference ( OpenAI, 2024a ; OpenAI, 2024b ) . This suggests that o1 could drive two paradigm shifts in AI: from (self-)supervised learning toward reinforcement learning, and from scaling solely training computation to scaling both training and inference computation.

o1 scales up the train-time compute with reinforcement learning and the test-time compute with more thinking. We take search as a way to implement the thinking process of o1, since search is scalable ( Sutton, 2019 ) and there are many successful researches that use search for training and decision in reinforcement learning, like AlphaGo ( Silver et al., 2016 ) and AlphaGo Zero ( Silver et al., 2017 ) . In this paper, we take reinforcement learning as the core in the roadmap to o1. Our roadmap is illustrated in Figure 1 and consists of four components: policy initialization, reward design, search, and learning. We believe these four parts are the keys to constructing LLM with strong reasoning abilities like o1.

As depicted in Figure 2 , our roadmap starts with policy initialization. In the context of LLMs, the policy ( π ⁡ ( a | s ) \pi(a|s) ) typically refers to the probability distribution for generating the next token/step/response (action) based on a given context (state). Policy initialization brings human-like reasoning behaviors to LLMs, like task composition, self-evaluation and self-correction. Next, we enter the reward design, which aims to provide guiding signals for search and learning. The reward design can take or reshape the reward signal from the environment or learn a reward model from preference data. Both policy initialization and reward designs are preparations for search and learning. Search plays an important role in generating high-quality solutions at both training and testing phases, which can produce better solutions with more computation. Learning utilizes the data generated by search for improving the policy. The data used for learning is derived from the interaction of the LLM with the environment, rather than being manually curated by human experts, therefore eliminating the need for costly data annotation and enabling the potential for achieving superhuman performance.

##### Policy Initialization

Training an LLM from scratch using reinforcement learning is exceptionally challenging due to its vast action space. Fortunately, we can leverage extensive internet data to pre-train a language model, establishing a potent initial policy model capable of generating fluent language outputs. Moreover, prompt engineering and supervised fine-tuning help models acquire human-like reasoning behaviors, enabling them to think systematically and validate their own results. These approaches enable models to thoroughly explore their solution spaces, leading to more comprehensive problem-solving capabilities.

##### Reward Design

Both search and learning require guidance from reward signals to improve the policy. There are different levels of action granularity, each corresponding to varing levels of reward signals granularity, which can be explored further. Additionally, these signals are often sparse or even nonexistent in many environments. To transform sparse outcome reward to dense process reward, there are some reward shaping methods ( Ng et al., 1999 ) . For the environment where the reward signal is unavailable, like the task of story writing, we can learn a reward model from preference data ( Bai et al., 2022a ) or expert data ( Ng & Russell, 2000 ) .The construction of reward model can further evolve into building a world model ( Dawid & LeCun, 2023 ) .

##### Search

Search plays a crucial role during both the training and testing phases. The training time search refers to generating training data from search process. The advantage of using search to generate training data, as opposed to simple sampling, is that search yields better actions or solutions—i.e., higher-quality training data—thereby enhancing learning effectiveness. During inference, search continues to play a vital role in improving the model’s sub-optimal policies. For instance, AlphaGo ( Wan et al., 2024 ) employs Monte Carlo Tree Search (MCTS) during testing to enhance its performance. However, scaling test-time search may lead to inverse scaling due to distribution shift: the policy, reward, and value models are trained on one distribution but evaluated on a different one ( Gao et al., 2023 ) .

##### Learning

Learning from human-expert data requires costly data annotation. In contrast, reinforcement learning learns through interactions with the environment, eliminating the need for expensive data annotation and offering the potential for superhuman performance. In this roadmap, reinforcement learning utilizes data generated by search for learning via policy gradient or behavior cloning. Policy gradient methods have high data utilization, as they leverage both positive and negative solutions, whereas behavior cloning is advantageous in terms of simplicity and memory efficiency. A prominent example of the iterative interaction between search and learning is AlphaGo Zero ( Silver et al., 2017 ) , which combines Monte Carlo Tree Search (MCTS) ( Metropolis & Ulam, 1949 ) as the search algorithm with behavior cloning as the learning method, ultimately achieving superhuman performance in the game of Go.

We provide a detailed exploration of the potential implementations of Policy Initialization (Section 3 ), Reward Design (Section 4 ), Search (Section 5 ), and Learning (Section 6 ). Additionally, we review existing open-source o1 projects, illustrating how they may either serve as components of our framework or as specific instances within it (Section 7 ). Finally, we discuss the future development trends of o1 and the associated challenges (Section 8 ).

## 2 Background

Since this roadmap is designed from perspective of reinforcement learning, we introduce some background of reinforcement learning and its connection to LLM in this section. Unlike other learning paradigms, reinforcement learning learns through interaction with the environment, rather than learning from a static training dataset. In reinforcement learning, an agent learns by receiving rewards from the environment as it explores. Figure 3 illustrates the interaction between agent and environment in reinforcement learning for LLM.

##### Agent

Agent is the entity that interacts with environment, which makes decision according to its policy. Formally, a policy π \pi is a mapping from states to actions. It is often represented as a probability distribution ( π ⁡ ( a | s ) \pi(a|s) ) over actions given a state s s , where the agent selects actions based on these probabilities.

In the context of LLMs, an agent refers to LLM itself, its policy specify the probability distribution of either token-, step-, or solution-level actions based on the current state. The state s t s_{t} consists of the input provided to the model at time t t , including both user inputs and the model’s earlier outputs. The action taken by the model can vary depending on the problem setting; it involves generating a single token, completing a step, or providing a solution.

##### Environment

Environment refers to the system or world outside the agent. It responds to agent’s actions and provide feedback in terms of next state s t + 1 s_{t+1} and rewards r ⁡ ( s t , a t ) r(s_{t},a_{t}) .

Environmental feedback can be categorized as either deterministic or stochastic. Stochastic feedback is characterized by a transition distribution p ( s t + 1 , r t + 1 | s t , a t ) p(s_{t+1},r_{t+1}|s_{t},a_{t}) , as seen in systems like dialogue models, where user responses are inherently unpredictable. On the other hand, deterministic feedback involves no randomness, yielding a fixed next state s t + 1 s_{t+1} and reward r ⁡ ( s t , a t ) r(s_{t},a_{t}) . For instance, when a LLM solves a mathematical problem, the transition is deterministic, where the current state s t s_{t} and action a t a_{t} are combined to produce the next state s t + 1 s_{t+1} .

## 3 Policy Initialization

In reinforcement learning, a policy defines how an agent selects actions in response to environmental states. As discussed in Section 2 , LLMs operate with actions at three granularity levels: solution-level, step-level, and token-level. Solution-level actions represent the coarsest granularity, treating the entire solution as a single action. Step-level actions operate at an intermediate granularity, where individual steps serve as discrete actions. Token-level actions provide the finest granularity, treating each individual token as an action. Taking token-level actions as an example, the action space contains thousands of tokens from the vocabulary, establishing a well-initialized policy becomes essential for effective model performance ( Brown et al., 2020 ) .

As illustrated in Figure 4 , the initialization process of LLMs consists of two primary phases: pre-training and instruction fine-tuning. During pre-training, models develop fundamental language understanding through self-supervised learning on large-scale web corpora ( Sun et al., 2024d ; Weber et al., 2024 ; Liu et al., 2024f ) , following established power-law relationships between computational resources and performance ( Kaplan et al., 2020 ; Hoffmann et al., 2022 ) . Instruction fine-tuning then transforms LLMs from simple next-token prediction to generating human-aligned responses ( Wei et al., 2022a ; Chung et al., 2024 ) . For models like o1, incorporating human-like reasoning behaviors is crucial to enable more sophisticated exploration of solution spaces. We summarize six key behaviors that can be activated through prompts or learned through expert trajectories distillation from LLMs.

### 3.1 Pre-Training

Pre-training establishes basic language understanding and reasoning capabilities in LLMs through exposure to massive text corpora ( Radford & Narasimhan, 2018 ; Lee et al., 2024 ) . For o1-like models, these core competencies serve as the basis for advanced behaviors developed through subsequent learning and search.

#### 3.1.1 Language Understanding and Generation

Pre-training cultivates diverse language capabilities through extensive exposure to natural language ( Radford & Narasimhan, 2018 ) . At the syntactic level, models learn grammatical structures ranging from basic word order patterns to complex dependencies ( Manning, 2022 ) . This syntactic foundation enables pragmatic understanding, including discourse markers and contextual language use, allowing models to adapt different styles across tasks ( Dam et al., 2024 ) . Generation capabilities progress from basic grammatical coherence to sophisticated features like long-range consistency and complex narrative structures ( Tian et al., 2024b ) . Through multilingual training data, models develop cross-lingual abilities, enabling zero-shot transfer and cultural understanding across languages ( Scao et al., 2022 ; Alves et al., 2024 ) . Research shows language understanding emerges hierarchically: syntactic patterns appear early, while logical consistency and abstract reasoning develop later, suggesting the importance of training duration and data composition beyond model scaling ( He et al., 2024 ; Ahuja et al., 2024 ) .

#### 3.1.2 World Knowledge Acquisition and Storage

Pre-training enables comprehensive knowledge acquisition across factual, procedural, and conceptual domains through diverse corpora processing ( Radford et al., 2019 ; Brown et al., 2020 ) . Models develop rich semantic networks of factual knowledge from encyclopedic sources and academic literature, enabling cross-domain reasoning and novel insights ( Chang et al., 2024 ) . Domain expertise emerges from specialized technical content, manifesting in advanced capabilities like mathematical proofs and scientific analysis ( Shao et al., 2024 ; Yang et al., 2024 ) . Procedural knowledge develops through exposure to instructional content and programming languages, enhancing systematic problem-solving abilities ( Ruis et al., 2024 ; Brahman et al., 2023 ; Haluptzok et al., 2023 ) . Mathematical and logical foundations form through formal mathematical texts, establishing logical reasoning capabilities ( Sun et al., 2023 ; Ahn et al., 2024 ) . Recent studies demonstrate that knowledge storage exhibits efficient compression and generalization properties ( An et al., 2024 ) , with abstract concepts requiring more extensive training compared to factual knowledge ( Allen-Zhu & Li, 2024 ) .

#### 3.1.3 Basic Reasoning Abilities

Pre-training develops foundational reasoning capabilities through diverse reasoning patterns, emerging hierarchically from simple inference to complex reasoning. Pattern matching and analogical reasoning emerge as primary mechanisms, enabling generalization across domains ( Webb et al., 2022 ; Yasunaga et al., 2024 ; Yu et al., 2024b ) . Logical inference abilities develop through exposure to massive code and mathematical proofs ( Hui et al., 2024 ; Yang et al., 2024 ) , while sequential processing capabilities emerge from procedural texts and mathematical derivations ( Lewkowycz et al., 2022 ) . These abilities enable complex problem decomposition and logical coherence.

### 3.2 Instruction Fine-Tuning

Instruction fine-tuning transforms pre-trained language models into task-oriented agents through specialized training on instruction-response pairs across diverse domains ( Zhang et al., 2023a ; Cheng et al., 2024a ) . This process alters the model’s behavior from pure next-token prediction to purposeful behavior ( Wu et al., 2024b ; Zhao et al., 2024b ) . The effectiveness of instruction fine-tuning depends primarily on two key factors: the diversity of the instruction dataset ( Sanh et al., 2022 ) and the quality of instruction-response pairs ( Li et al., 2024a ; Liu et al., 2024g ) . Research efforts have expanded both dimensions significantly, with Wang et al. (2022b) developing a comprehensive dataset encompassing over 1,600 distinct NLP tasks. FLAN ( Wei et al., 2022a ) demonstrated that models fine-tuned on high-quality instruction data can effectively generalize to novel tasks. Chung et al. (2024) enhanced this capability through scaling across task count, model size, and incorporation of step-by-step reasoning protocols. Smaller-scale models like Alpaca ( Taori et al., 2023 ) achieved remarkable instruction-following capabilities through carefully curated high-quality training data. Self-Instruct ( Wang et al., 2023b ) introduced methods for automated generation of instruction-response pairs using LLMs themselves. Hayati et al. (2024) further established that fine-tuning on complex, multi-step instructions significantly enhances model capabilities and generalization.

### 3.3 Human-like Reasoning Behaviours

While instruction-tuned models demonstrate general task competency and user intent understanding, models like o1 require a more sophisticated repertoire of human-like reasoning capabilities to fully leverage their potential. As shown in Table 1 , similar to Zhang (2024) , our analysis of o1’s behavior patterns identified six human-like reasoning behaviors that help o1 better explore the solution space. We examine the implementation of these reasoning behaviors through two complementary perspectives: supervised fine-tuning and prompt engineering ( richards, 2024 ) .

##### Problem Analysis

Problem analysis serves as a crucial initialization process where the model reformulates and analyzes the problem before solving it ( Kondrakunta et al., 2018 ) . This process involves multiple steps: explicit problem restatement to verify understanding, identification of implicit constraints, and transformation of abstract requirements into concrete, actionable specifications. Deng et al. (2023) advance this concept through Proactive Chain-of-Thought, where models actively analyze potential ambiguities before proceeding with problem-solving. In o1’s blog on cipher solving, this manifests as careful observation of ciphertext patterns and explicit problem reformulation. As shown in Table 1 , in coding tasks, it restructures inputs into matrices and precisely generates expected outputs. Problem analysis reduces ambiguity in problem interpretation, constructing a more advantageous initial state for the subsequent phase ( Lee et al., 2023 ) .

##### Task Decomposition

When encountering complex problems, humans typically decompose them into several manageable subtasks ( Zhou et al., 2023a ) . As shown in Table 1 , in coding tasks, o1 decomposes the problem into several subtasks, including capturing input strings, removing spaces, and parsing input strings. Bursztyn et al. (2022) introduce Compositional Fine-Tuning (CFT), a technique that explicitly divides a target task into its constituent components. Recent studies show that models can effectively perform such decompositions when guided by carefully structured prompts ( Khot et al., 2023 ; Dua et al., 2022 ) . Importantly, the decomposition process is adaptive and context-aware, with the model dynamically adjusting the granularity and structure of subtasks based on the problem’s complexity and uncertainty levels ( Prasad et al., 2024 ; Zhou et al., 2023b ) .

##### Task Completion

Following problem analysis and task decomposition, the model generates solutions through step-by-step reasoning based on clarified problems and decomposed subtasks ( Plaat et al., 2024 ; Sun et al., 2023 ) . This behavior forms the foundation for all other reasoning processes, where successful solutions lead to subsequent subtask processing, while problematic solutions trigger the generation of alternatives or self-correction behaviors. Step-by-step generation significantly enhances models’ complex reasoning capabilities ( Wei et al., 2022b ; Zhang et al., 2023c ) . For LLMs, this ability can be activated through prompts containing reasoning processes ( Wei et al., 2022c ) , or even through simple instructions like “Let’s think step by step” ( Kojima et al., 2022 ) . Smaller models can acquire this capability through distillation on extensive step-by-step reasoning data Shridhar et al. (2023) ; Hsieh et al. (2023) . Recent research indicates that sampling multiple solutions substantially increases the probability of generating correct answers ( Brown et al., 2024 ) , while selecting final answers based on marginal probabilities effectively improves overall accuracy ( Wang et al., 2023a ) .

##### Alternative Proposal

When faced with reasoning obstacles or dead ends, the ability to generate diverse alternative solutions becomes crucial ( Gerwig et al., 2021 ; Liang et al., 2024 ) . As shown in Table 1 , o1 demonstrates this capability in cipher solving by systematically proposing several options. Divergent CoT ( Puerto et al., 2024 ) fine-tunes models to generate multiple solutions in a single inference, significantly improving performance on complex reasoning tasks. The generation of alternative proposals can be activated through prompting strategies. Progressive-Hint Prompting ( Zheng et al., 2023a ) leverages historical solution attempts to guide current reasoning, while Exchange-of-Thought ( Yin et al., 2023a ) enriches the solution space by incorporating insights from other models. This systematic exploration of alternatives not only expands the search space but also enables iterative refinement through solution comparison, leading to more well-reasoned outputs.

##### Self-Evaluation

Following task completion, self-evaluation serves as a critical verification mechanism to validate the correctness of proposed solutions ( Weng et al., 2023 ) . As shown in Table 1 , in o1’s cipher example, the model compares plaintext and ciphertext letter by letter, expressing self-evaluation through explicit feedback such as “Let’s check” or “Let’s test”. This evaluation capability can be enhanced through two primary approaches: implementing detailed evaluation criteria to instill self-evaluation abilities ( Bai et al., 2022b ; Yin et al., 2024b ) , or utilizing self-debate for cross-validation ( Du et al., 2024 ; Sun et al., 2024c ) . Zhang et al. (2024f) introduces Self-Knowledge Tuning to strengthen models’ self-evaluation capabilities, enabling more reliable assessment of their own reasoning processes. Liu et al. (2024d) demonstrates that distilling self-evaluation abilities into smaller models significantly improves their reasoning performance.

##### Self-Correction

When encountering manageable errors in the reasoning process, models employ self-correction behaviors to address them ( Pan et al., 2023 ) . In o1’s demonstration, encountering signals like “No” or “Wait” triggers the correction process. As shown in Table 1 , in o1’s science example, the model identifies errors in formula generation and produces the correct formula through self-correction. Huang et al. (2024a) highlights the challenges of self-correction without external feedback, while Liu et al. (2024a) demonstrates that unbiased prompts and zero temperature settings can unlock intrinsic correction capabilities. Zhang et al. (2024a) introduces step-level analysis that significantly improves self-correction performance across multiple datasets.

While the behaviors described above provide insights into o1’s human-like reasoning capabilities, they represent only a subset of its comprehensive reasoning framework. The model demonstrates sophisticated adaptive behaviors that extend beyond these fundamental patterns, dynamically adjusting its problem-solving strategies based on task-specific requirements and constraints. Through systematic analysis of these behaviors, we gain valuable insights into how o1 navigates complex textual domains and modulates its reasoning behaviors across diverse contextual environments.

### 3.4 Speculation About the Policy Initialization of o1

During the progression from pre-training to instruction following, the model gradually constrains its action space. Policy initialization plays a critical role in developing o1-like models, as it establishes foundational capabilities that influence subsequent learning and search processes. The policy initialization phase encompasses three essential components: pre-training, instruction fine-tuning, and the development of human-like reasoning behaviors. While these reasoning behaviors are implicitly present in LLMs after instruction fine-tuning, their effective deployment requires activation through either supervised fine-tuning or carefully crafted prompts. Below, we outline several foundations for effectively utilizing these human-like reasoning behaviors.

##### Long-Text Generation Capabilities

During inference, LLMs need to generate a large number of tokens to encompass complex and diverse reasoning behaviors, which requires sophisticated long-context modeling capabilities. While current LLMs have significantly improved in processing long texts ( Wang et al., 2024e ) , their capacity for generating lengthy content remains limited. Bai et al. (2024) introduces AgentWrite, an agent-based automated data construction pipeline. By fine-tuning on the constructed LongWriter-6k dataset, the approach substantially enhances LLMs’ long-text generation capabilities. Similarly, Quan et al. (2024) proposes Self-Lengthen, which iteratively fine-tunes on data constructed by the Extender, continuously improving LLMs’ long-form text generation performance.

##### Shaping Human-like Reasoning Behaviors Logically

Beyond generating extensive outputs, models must develop the capability to orchestrate human-like reasoning behaviors in a logically coherent manner. This orchestration requires sophisticated decision-making; for instance, when self-evaluation identifies an error, the model must strategically determine whether to engage in self-correction or explore alternative solutions. While these human-like reasoning behaviors enable comprehensive exploration of solution spaces, they simultaneously introduce computational complexity and demand enhanced logical reasoning capabilities. Current research demonstrates that exposure to programming code and structured logical data significantly strengthens a model’s reasoning capabilities ( Sun et al., 2024b ; Aryabumi et al., 2024 ) . However, the systematic organization and sequencing of these human-like reasoning behaviors remains an open research challenge, particularly in determining optimal decision points for deploying specific reasoning behaviors.

##### Self-Reflection

We identify behaviors such as self-evaluation, self-correction, and alternative proposal as manifestations of the model’s self-reflection capability. Self-reflection addresses a fundamental limitation of autoregressive models: the inability to revise previously generated content ( Madaan et al., 2023 ) . Additionally, self-reflection demonstrates the model’s self-knowledge ( Cheng et al., 2024b ; Yin et al., 2023b ) , enabling it to spontaneously recognize flaws in its generated content. Current research indicates that this capability is not easily acquired and cannot be effectively learned through parameter-efficient fine-tuning methods ( Ye et al., 2024 ) .

### 3.5 Challenges of Policy Initialization for Reproducing o1

While policy initialization establishes crucial foundations for o1-like models, several significant challenges emerge in implementing this approach effectively.

##### How to balance sampling-efficiency and sampling-diversity?

Policy initialization faces a critical trade-off between sharping the action probability distributions for efficient sampling and maintaining sufficient diversity for exploration. While learning from human demonstrations helps constrain the action space, excessive convergence to fixed strategies can limit the discovery of superior approaches during search phases ( Li et al., 2024b ) . This challenge is evident in comparing AlphaGo and AlphaGo Zero, initialization from human data provides a strong starting point but may inadvertently restrict exploration of potentially better strategies.

##### How to ensure domain generalization of reasoning behaviors?

Current research focuses on replicating o1’s behaviors in specific domains such as mathematics ( Chen et al., 2024a ) and coding ( Zhang et al., 2024g ) . However, o1’s behaviors are not limited to domain-specific reasoning behaviors. For instance, in safety tasks, models need to perform behaviors that verify whether generated content complies with safety guidelines. Therefore, during the policy initialization process, models should not be restricted to domain-specific reasoning behaviors. Since it is impractical to specify corresponding reasoning behaviors for all tasks, designing reasoning behaviors with strong domain generalization capabilities becomes crucial.

## 4 Reward Design

In reinforcement learning, the agent receives feedback from the environment in the form of a reward signal and seeks to maximize its long-term reward by improving its policy. The reward function, denoted as r ⁡ ( s t , a t ) r(s_{t},a_{t}) , represents the reward associated with the agent’s action a t a_{t} in state s t s_{t} at time step t t . The reward signal is crucial in guiding both the training and inference processes, as it defines the desired behavior of the agent through numerical scoring. While the same optimal policy can be learned from various reward designs ( Ng et al., 1999 ) , a well-designed reward signal can accelerate both the convergence of learning and the efficiency of the search process.

This section provides an overview of the current reward design methods for large language models (LLMs). We begin by comparing the outcome reward and the process reward . Next, we introduce reward design methods that have been specifically proposed for LLMs. We also review reward design techniques that are widely used in reinforcement learning but have not yet been applied to LLMs. Finally, based on our comparison of these different methods, we offer a speculative discussion on the reward design for o1.

### 4.1 Outcome Reward vs Process Reward

The outcome reward involves assigning a score based on whether the outputs of a large language model (LLM) meet predefined expectations ( Cobbe et al., 2021 ; Shao et al., 2024 ) . For instance, Cobbe et al. (2021) uses outcome reward to assess whether the solution provided by the LLM to a mathematical problem is correct. Since ground truth is generally available for tasks such as solving mathematical problems, outcome reward is often straightforward.

Although the outcome reward is relatively easy to construct, it lacks supervision for intermediate steps. For instance, a solution to a mathematical problem that leads to the correct answer may still contain errors in the intermediate steps ( Lightman et al., 2024 ) . As a result, using the outcome reward may cause the LLM to generate incorrect solution steps, which could negatively affect performance. Moreover, outcome reward is sparse, as it does not reward intermediate steps, making it challenging to learn step-level policies. Despite these limitations, it remains widely used in reinforcement learning for LLMs due to its simplicity.

In contrast to the outcome reward, the process reward provides a reward signal not only for the final step but also for intermediate steps ( Lightman et al., 2024 ; Yin et al., 2024a ) . For example, Lightman et al. (2024) involves human annotators rewarding the intermediate steps in a mathematical solution generated by an LLM. The outcome reward can be seen as a special case of the process reward, where the rewards for intermediate steps are all set to zero.

Depending on the granularity of the actions, the process can be classified into token-level ( Rafailov et al., 2024 ) and step-level ( Lightman et al., 2024 ) . The step-level segmentation is flexible. Kuhn et al. (2023) uses information entropy to guide step segmentation while methods in mathematical problem-solving typically use newline characters as the split symbol ( Lightman et al., 2024 ) .

Although process rewards show promise, they are more challenging to learn than outcome rewards. For instance, the reward design in Lightman et al. (2024) depends on human annotators, making it costly and difficult to scale. There are some automatic ways to transform outcome rewards to process rewards, which is called reward shaping in traditional reinforcement learning. We introduce the methods of reward shaping in Section 4.2.3 .

### 4.2 Reward Design Methods

Since outcome reward can be seen as a special case of process reward, many reward design methods can be applied to the modeling of both outcome reward and process reward. The resulting models are typically referred to as the Outcome Reward Model(ORM) and the Process Reward Model(PRM). We review these reward design methods for LLMs, categorizing them based on whether or not they have direct access to the reward signal from the environment.

#### 4.2.1 Reward from Environment

The most straightforward approach to designing a reward is to directly utilize the reward signal from the environment, or learn a model to simulate the reward signal from the environment.

##### From Realistic Environment

Many environments can provide effective reward signals, for example, code generation can receive reward signals from a compiler or interpreter. Dou et al. (2024) ; Shojaee et al. (2023) ; Dong et al. (2024) have shown that the quality of code generation is improved with compiler feedback. Zhang et al. (2024e) generates test cases for input questions and uses the testing outcomes as the reward signal. ( Shi et al., 2022 ) measures the similarity of different programs based on their execution results. Zheng et al. (2024) uses the execution results of a program as guidance for refining a code generation model. For some real-world tasks, the environment is just a sandbox. In web shopping ( Liu et al., 2024e ) , the environment is represented by a real HTML page, and the reward is calculated based on the score the LLM obtains through clicks and searches. In more general scenarios, sandboxes are created to allow the policy model to interact directly with, such as in environments like MineDojo ( Fan et al., 2022 ) or Alfworld ( Shridhar et al., 2021 ) .

##### From Simulating Environment

While some environments can provide valid feedback, interacting with them to obtain the reward signal can be costly, or the feedback may not be available at test time. For example, during testing, we might not have test cases to validate whether the program generated by the LLM is correct. In such cases, a reward model is required to simulate the reward signal from the environment. For instance, Lightman et al. (2024) trains a verifier to predict whether the model’s solution to a mathematical problem is correct at test time.

Simulating the reward signal enables the LLM to obtain feedback at any time. However, using such a reward model during learning or search can lead to the problem of distribution shift. As the policy is updated during learning and search, the reward model, which is trained on data from interactions between the old policy and the environment, may fail to adapt to the new policy. This issue, known as reward optimization, has been discussed in Gao et al. (2023) ; Stroebl et al. (2024) . Thus, the reward model must be updated in tandem with the policy improvements. In more general domains, simulating the environment aligns with the concept of a world model, where the transition probabilities of states must be further simulated, allowing for a more accurate reward model. We discuss the world model in Section 4.5.2 .

##### From AI Judgment

AI Judgment involves using general AI assistants to provide the reward signal, serving as an alternative to relying on realistic environments, thereby avoiding the high costs associated with environment construction and interaction. For instance, it is common to use a powerful LLM, such as GPT-4, to assess the performance of an AI assistant ( Zheng et al., 2023b ) . While AI judgment can be viewed as a form of reward model, it does not face the issue of reward optimization, as it is not dependent on the policy model. As a result, AI judgment remains effective even when the policy model undergoes updates. The LLM is an implementation of the world model, which also highlights the effectiveness of building a world model to provide reward signals.

#### 4.2.2 Reward Modeling from Data

For some environment, the reward signal from environment is unavailable, which can not be simulated. For example, it is difficult to judge whether the response from an AI assistant is good or not. Fortunately, it is easier to collect the expert data or the preference data than giving a reward. With the expert data or preference data, we can also learn a model to provide effective rewards.

Learning rewards from preference data is widely recognized in the LLM community, particularly due to the success of RLHF ( Bai et al., 2022a ) . However, learning rewards from expert data, also known as Inverse Reinforcement Learning, has not been widely used for LLMs, which may represent a promising technique for o1.

##### Learning Rewards from Preference Data

Preference data is collected by ranking multiple responses from LLMs to the same question. Using the Bradley-Terry model, an outcome reward can be derived based on the pair-wise comparison ( Bradley & Terry, 1952 ) . Learning rewards from preference data for LLM is first proposed in Christiano et al. (2017) , which introduced the preference signal to tackle complex reinforcement tasks without access to a reward function, achieving significant success in Atari games and robotics. They further developed this approach for text summarization ( Stiennon et al., 2020 ) . This technique is then used for the development of ChatGPT, where preference signals are used for aligning policy behavior with human values ( Bai et al., 2022b ) .

Learning from preference data has been widely used in alignment of LLMs. However, it is crucial to construct the preference data that accurately reflects the actual performance of downstream tasks. For example, Wen et al. (2024) show that using human preferences as supervision may degrade the true performance of the model.

##### Learning Rewards from Expert Data

Inverse Reinforcement Learning (IRL) is a method for learning rewards from expert data, with the goal of recovering the reward function that the expert is optimizing. This is achieved by fitting the reward function to the trajectories generated by the expert and maximizing the recovered reward ( Abbeel & Ng, 2004 ; Ng & Russell, 2000 ) . Many IRL approaches integrate adversarial learning techniques. Garg et al. (2021) introduces the convex conjugate function to avoid the need for adversarial training. Compared with learning reward from preferences, the data for IRL is easier to be collected. However, IRL typically involve adversarial training, which makes the learning more complicated than learning rewards from preferences. Despite that IRL is well-known in reinforcement learning, there is no empirical evidence that it has been used for large-scale reinforcement learning for LLM.

#### 4.2.3 Reward Shaping

The reward signal from some environments may not be effective; for example, it could be an outcome reward rather than a process reward. In such cases, the reward can be reshaped to make it denser and more informative, a process known as reward shaping. For instance, Kumar et al. (2024) attempts to train an LLM to self-correct via reinforcement learning and discovers that proper reward shaping can prevent learning collapse. Wang et al. (2024c) reshaped the outcome reward by estimating the value function using Monte Carlo sampling, employing the Q-value Q π ​ ( s t , a t ) Q_{\pi}(s_{t},a_{t}) as the reward during intermediate steps. However, since the value function depends on the policy π \pi , the value function estimate from one policy may not be a valid reward function for another policy. This is empirically validated by Xiong et al. (2024) , who found that using a value function from another policy for reward shaping is harmful.

Ng et al. (1999) defines potential-based reward shaping and proves that two reward functions can lead to the same optimal policy if and only if they satisfy the following equation: F ⁡ ( s t , a t ) = r ⁡ ( s t , a t ) + γ ​ ϕ ​ ( s t + 1 ) − ϕ ⁡ ( s t ) , F(s_{t},a_{t})=r(s_{t},a_{t})+\gamma\phi(s_{t+1})-\phi(s_{t}), (1) where F ⁡ ( s t , a t ) F(s_{t},a_{t}) and r ⁡ ( s t , a t ) r(s_{t},a_{t}) are two reward functions that yield the same optimal policy, γ \gamma is the discount factor, and ϕ \phi is a potential function. Potential-based reward shaping suggests that the reward function r ⁡ ( s t , a t ) r(s_{t},a_{t}) can be reshaped without altering the optimal policy, as long as the shaping satisfies Equation 1 . Setlur et al. (2024) uses the theory of potential-based reward shaping to transform outcome rewards into process rewards.

The reward learned from preference data can also be reshaped. For example, Rafailov et al. (2023) , Rafailov et al. (2024) and Zhong et al. (2024) demonstrate that DPO implicitly makes potential-based reward shaping ( Ng et al., 1999 ) on the reward learned from preference data.

While reward shaping can be advantageous, it may also be harmful. Improper reward shaping can negatively affect both learning and search processes. As a result, reward shaping requires careful design and often entails incorporating inductive bias.

### 4.3 Speculation About the Reward Design of o1

We now turn to discuss our assumptions regarding the reward design for o1. Given that o1 could handle multi-task reasoning, its reward model is likely to incorporate multiple reward design methods. For complex reasoning tasks, such as mathematics and code, where responses typically involve long chains of reasoning, a process-reward model is more likely to be employed to supervise the intermediate process, rather than ORM. Techniques like reward shaping can help derive process rewards from outcome rewards.

When no reward signal is available from the environment, we suspect that o1 will need to rely on learning from preference data ( Christiano et al., 2017 ) or expert data ( Garg et al., 2021 ) .

Given that o1 can be fine-tuned using few-shot examples, we suspect that it has a robust reward model trained on a large and diverse dataset spanning a wide range of domains. It can be adapted to a new domain easily through ground truth and solution pairs. Moreover, it is more likely to predict rewards by generating with LLM rather than through value heads.

### 4.4 Challenges of Reward Design for Reproducing o1

##### How to overcome distribution shift?

The reward model learns from an existing dataset distribution and the out-of-distribution problem still remains significant today ( Gao et al., 2023 ) , especially as the LLM continues to explore and learn from feedback. The reward provided by the proxy model deviates from the golden reward when the distribution of the policy model changes, as the trajectory becomes unseen during the training of the reward model and heavily depends on its generalization. Scaling the parameters of the reward model and increasing the amount of data can mitigate this issue but does not completely solve it. Iteratively training the reward model provides a more direct solution, but it still requires human involvement in the loop.

##### How to design fine-grained reward for language model?

Unlike in Atari games or robotic environments, language presents a unique challenge because the definition of a step or action can vary in granularity: token-level, step-level or solution-level. In many situations, such as fitting the model to human preferences, it is more natural to judge the entire solution rather than each token individually, as higher-order semantics in language emerge from the combination of tokens. However, using token combinations as actions results in an action space that is too large to define or learn a reward function for. The potential action space grows exponentially, leading to a long tail of actions. Meanwhile, the sparsity of the reward signal increases with the length of each step as we mentioned before.

##### How to choose data when modeling reward for complex tasks?

As the complexity of tasks increases, choosing the appropriate type of feedback becomes increasingly challenging. Recent studies have shown that using preference-based feedback for tasks like code generation or mathematical reasoning may actually degrade the performance of the policy model ( Wen et al., 2024 ) . Additionally, the question of how much data is necessary to accurately capture the intended behavior remains underexplored. The difficulty of evaluating whether a reward is effective also grows as the complexity of the task increases.

### 4.5 Generalization

The previous section primarily focused on reward design for specific tasks, such as math and coding. When addressing more general tasks, we need to create a broader environment. Practically, according to OpenAI’s 5-stages plan for AGI, o1 has been a strong reasoner, the next stage is to train an agent that can interact with the world and address real-world problems. To achieve this goal, we need a reward model to provide the reward signal for the agent taking actions in a realistic environment. In this section, we focus on how to construct a general reward signal, which can be divided into two components: the reward ensemble and the world model.

#### 4.5.1 Reward Ensemble

An intuitive way to build a reward signal for a general task is through an ensemble rewards in specfic domains. Quan (2024) trains the reward model as a form of MoE ( Jiang et al., 2024a ; Zeng et al., 2024a ) , where each expert is trained on a different task to provide the corresponding reward signal, and the outputs are aggregated finally. Nguyen et al. (2024) frames this problem as a multi-armed bandit question, learning to select the most suitable reward model. In short, the crucial question is for these methods is how to combine the reward signals effectively.

#### 4.5.2 One for all: World Model

The world model can not only provide the reward signal but also predict the next state ( Ha & Schmidhuber, 2018 ; Bar et al., 2024 ) . Some works claim that a video generator is a world model since the video generator can predict the images in the future time steps ( Liu et al., 2024b ; Bar et al., 2024 ; Wang et al., 2024d ; Brooks et al., 2024 ) . Dawid & LeCun (2023) also proposes a framework where world model do not need to predict the next state, instead they predict the representation of the next state, which is easier and more efficient than predicting a image. This is inline with Muzero ( Schrittwieser et al., 2020 ) , which also let the environment simulator to predict the representation of the next state in the game of go. The current works of world model focus on modeling of the next state prediction, but we believe modeling the reward signal is also critical and challenging for an agent to accomplish real-environment tasks.

## 5 Search

For LLMs, performing random sampling during generation has become a mainstream method to improve output quality, with techniques such as nucleus sampling being prominent examples ( Holtzman et al., 2020 ) . Furthermore, many studies ( Kulal et al., 2019 ; Chen et al., 2021 ) have observed that the pass@k metric improves consistently as the number of model samples increases. Brown et al. (2024) show that even small models can outperform large models leveraging search. This suggests that language models have the potential to explore the correct solution by more sampling during inference, which requires consuming more inference-time computations. Search refers to the process of finding the correct solution through multiple attempts or strategic exploration based on certain guidance, such as rewards or heuristic rules. Well-known inference strategies like self-consistency ( Wang et al., 2023a ) and Best-of-N (BoN) ( Cobbe et al., 2021 ) both can be seen as search methods. For model like o1, which are designed to solve complex reasoning tasks, search may play an important role in both training and inference processes. In this section, we first analyze the possible role of search in o1, and then introduce the details of various promising search methods which have the potential to be used in the construction of o1-like models.

### 5.1 The role of Search in o1

Search often relies on guiding signals thus can be viewed as a process of strategy iteration, we call it search policy. Compared to naive sampling, search policies are usually more likely to find better solutions. Solutions generated by search policies can either be directly used as the final output or incorporated into training algorithms, like Expert Iteration ( Anthony et al., 2017 ) , to iteratively improve the policy. We believe that search plays a crucial role in both the training and inference processes of o1 . We will refer to the search during these two stages as training-time search and test-time search , respectively.

In the training phase, the trial-and-error process in online reinforcement learning can also be seen as a search process ( Sutton & Barto, 1998 ) , where the agent performs naive sampling based on its own policy and learns solution that yield high rewards. However, since o1 involves longer inference lengths and includes human-like reasoning behaviors, the search space becomes large, and naive sampling may become inefficient. Therefore, some advanced search strategies are needed to more efficiently explore better solutions and use them as training data to update the policy model. This process can be iteratively conducted during training. In the inference phase, o1 demonstrates that increasing compute during inference with more time spent thinking can continuously improve model performance ( OpenAI, 2024a ) . We argue that o1’s way to think more can be seen as a kind of search, using more inference-time computation to find better answers.

The two key aspects of search are the guiding signals for the search and the search strategies to get candidate solutions. Search strategies are used to obtain candidate solutions or actions, while guiding signals are used to make selections. We first discuss the guiding signals for the search process, dividing them into internal and external guidance. Inspired by Snell et al. (2024) , we categorize the search strategies into tree search and sequential revisions. It is worth noting that these two classification dimensions are orthogonal, for example, tree search methods can utilize either internal or external guiding signals. We present a schematic diagram of these categories in Figure 6 .

### 5.2 Search Guidance

In the following sections, we will discuss methods for providing guiding signals to the search process. Search based on internal guidance does not rely on real-world feedback from the external environment or proxy models, but instead uses certain states or evaluation capabilities of the model itself to guide the search process. Classic text generation decoding algorithms, such as greedy decoding and beam search, typically use the probability of tokens or sequences as internal guidance for the search process. External guidance is generally independent of specific policies and relies solely on environment- or task-related signals to guide the search process.

#### 5.2.1 Internal Guidance

##### Model Uncertainty

Model uncertainty ( Malinin & Gales, 2018 ) is a common form of internal guidance. Many studies leverage it to select high-quality responses from candidates, with self-consistency ( Wang et al., 2023a ) being a notable example. Self-consistency uses majority voting or weighted sums to choose the answer with the lowest uncertainty. Universal self-consistency ( Chen et al., 2023 ) extends this approach to free-form responses, enabling large language models to select the most consistent answer without task-specific constraints, thus broadening its applicability. Building on the idea that different sentences can express the same meaning, Kuhn et al. (2023) shift the focus to semantic rather than syntactic uncertainty. They use NLI models ( Williams et al., 2018 ) for semantic clustering, treating two sentences as equivalent if they exhibit bi-directional entailment. The entropy of the semantic distribution is then used to measure uncertainty. This semantic entropy has also been applied to detect hallucinations ( Farquhar et al., 2024 ) , showing strong performance. Model uncertainty is often derived through unsupervised methods, making it easy to be obtained. However, its reliability depends heavily on the model’s calibration ( Guo et al., 2017 ) . A well-calibrated model is essential for effectively utilizing model uncertainty.

##### Self-evaluation

Model uncertainty is a useful guide but does not directly reflect response accuracy. For example, high-uncertainty answers can still be correct. To improve model performance, self-evaluation aims to let models assess their own outputs, leveraging the assumption that evaluation is easier than generation, known as the generator-discriminator gap (DG-gap) ( Leike, 2022 ; Davis et al., 2024 ) . A key application of the DG-gap is reinforcement learning from human feedback (RLHF) ( Stiennon et al., 2020 ) . Compared to directly annotating the correct model output, researchers have found that human annotators’ preferences for different candidate outputs can serve as effective and scalable supervisions. This approach helps align the model’s behavior with human intentions and values. For instruction-following language models, LLM-as-a-Judge ( Gu et al., 2024 ) is an efficient self-evaluation method, achieving high agreement with human evaluators on MT-Bench ( Zheng et al., 2023b ) . Using this approach, Yuan et al. (2024) demonstrate that models can improve self-rewarding through iterative DPO training. Similarly, Wu et al. (2024a) introduce LLM-as-a-Meta-Judge to enhance self-evaluation. The main challenge in task-specific self-evaluation is determining whether a DG-gap exists and how to fully exploit it for greater accuracy. It is important to note that some studies ( Huang et al., 2024a ) suggest that models cannot accurately evaluate answers without feedback. To address this, we may need to scale up the model size, train it for self-evaluation, specify more detailed evaluation criteria.

#### 5.2.2 External Guidance

##### Environmental Feedback

Using environmental feedback corresponding to downstream tasks is one of the most commonly used forms of external guidance and is typically directly related to the evaluation metrics of downstream tasks. Reward is a typical form of environmental feedback and is often used to guide the search process, directly corresponding to the final performance. We have discussed details of reward design in Section 4.2 . During the search process, we may need multi-scale rewards for guidance, such as outcome rewards and process rewards. Using rewards as guiding signals often requires constructing the environment or utilizing proxy feedback, which can improve search effectiveness but may also introduce additional computational overhead. Moreover, when using proxy feedback such as a reward model for search, if the sampled solutions deviate significantly from the distribution of the reward model’s training data, the search may actually lead to a decrease in performance. Besides, environmental feedback that is indirectly related to the final performance can also be used to guide the search process, such as code compilation outcomes, correctness of intermediate steps in solving mathematical problems, unit tests, and more. This type of feedback often serves as an alternative to feedback on the final task outcomes.

##### Heuristic Rules

Many search algorithms use heuristics as guiding signals alongside environmental feedback. Traditional informed search methods, such as greedy search and A ∗ A^{*} search, require the use of heuristic rules developed based on the specific information of the task to guide the search process ( Russell & Norvig, 2020 ) . Additionally, studies for enhancing LLMs’ reasoning abilities ( Hao et al., 2023 ; Koh et al., 2024 ) also apply task-specific heuristics to guide search. When we want to reduce the cost of environmental feedback or when environmental feedback is unavailable, using heuristic rules is a good alternative.

#### 5.2.3 Comparison of Internal and External Guidance

This section compares internal and external guidance. Internal guidance relies solely on the model, avoiding the need for external environments or ground truth, and is generally task-agnostic. Thus, internal guidance is highly transferable and useful when specific evaluation criteria for downstream tasks are unavailable . External guidance relies on specific downstream task information, such as rewards from interactive environments or ground truth, making it more aligned with model performance and better at guiding search strategies. However, it introduces construction costs and computational overhead. During inference, the ground truth is often unavailable, and interacting with the environment or simulator is costly. Additionally, external guidance from surrogate models (like a fixed reward model) can face out-of-distribution (OOD) issues ( 4.4 ). Therefore, external guidance during inference requires careful consideration.

#### 5.2.4 Combination of Internal and External Guidance

Internal and external guidance can be combined to direct the search process, with typical approaches integrating the model’s own uncertainty and proxy feedback from reward models. For example, Wang et al. (2024c) and Snell et al. (2024) combine self-consistency with feedback from a process reward model to select the highest-quality responses.

The value function is another type of signal that combines both internal and external guidance. In reinforcement learning, the value function estimates expected cumulative rewards from a state (V function) or state-action pair (Q function), guiding agents to select actions that maximize long-term rewards. It typically relies on environmental reward signals and uses a separate neural network ( Yu et al., 2024a ; Liu et al., 2024c ; Wang et al., 2024c ) . The calculation formula for the value function is as follows (refer to Sutton & Barto (1998) ): v π ​ ( s ) ≐ 𝔼 π ​ [ G t ∣ S t = s ] = 𝔼 π ​ [ ∑ k = 0 ∞ γ k ​ R t + k + 1 ∣ S t = s ] , for all ​ s ∈ 𝒮 , v_{\pi}(s)\doteq\mathbb{E}_{\pi}[G_{t}\mid S_{t}=s]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}\mid S_{t}=s\right],\,\text{for all }s\in\mathcal{S}, (2)

In this equation, v π ​ ( s ) v_{\pi}(s) denotes the value of state s s under policy π \pi , while 𝔼 π \mathbb{E}_{\pi} represents the expectation taken over all possible trajectories following the policy π \pi . The term G t G_{t} is the return, which is defined as the cumulative sum of future rewards discounted by the factor γ \gamma , where γ ∈ [ 0 , 1 ] \gamma\in[0,1] determines the importance of future rewards relative to immediate rewards. Specifically, R t + k + 1 R_{t+k+1} is the reward received at time step t + k + 1 t+k+1 , conditioned on the state at time t t being s s . Finally, 𝒮 \mathcal{S} refers to the set of all possible states in the environment.

The value function plays a fundamental role in reinforcement learning, as it quantifies the long-term expected reward for starting in a specific state and taking actions according to the given policy. By evaluating the value of states, the value function enables agents to compare and make informed decisions about which states or actions are more favorable under a particular policy.

Rafailov et al. (2024) show that DPO is an inverse Q-learning algorithm, where DPO model logits act as the Q function, enabling search processes guided by the value function. They also demonstrate performance gains from applying beam search to the DPO model. Additionally, some work ( Silver et al., 2017 ; Wan et al., 2024 ; Chen et al., 2024a ) incorporates a value head into the policy model, sharing a large-scale backbone. The main challenge in using value functions lies in accurately estimating them , especially in tasks with sparse rewards or high-dimensional outputs, such as large language model generation, where inaccuracies can significantly impact performance.

### 5.3 Search Strategies

We categorize search strategies into two types: tree search and sequential revisions . Tree search generates multiple answers simultaneously, acting as a global search that explores a broader range of solutions. In contrast, sequential revisions refine each attempt based on previous ones, functioning as a local search that may offer higher efficiency ( Snell et al., 2024 ) .

#### 5.3.1 Tree Search

This section introduces tree search algorithms like Best-of-N (BoN), beam search, and MCTS. BoN generates multiple independent candidate solutions but lacks dynamic adjustment of the model’s probability distribution, leading to inefficiencies, such as over-sampling high-probability options. BoN can be seen as a special case of tree search with depth-1 nodes. In contrast, other tree search strategies dynamically adjust at each step, balancing exploration and exploitation with heuristics, and can use lookahead search, backtracking, and pruning to improve efficiency and reduce sampling costs. An important question in using tree search algorithms on LLMs is defining the granularity of the tree node. As shown in Figure 7 , common granularities of tree nodes include: token level, step level, and solution level. The token level represents the finest granularity, while the solution level represents the coarsest granularity. Generally, the smaller the granularity of the search tree nodes, the deeper the search tree becomes.

##### Best-of-n Sampling

Best-of-N sampling (BoN) is a simple yet effective search method, which can be seen as a solution-level tree search. It first generates multiple candidate solutions from the model, then selects the best solution via a reward model while discarding the rest ( Cobbe et al., 2021 ) . When BoN uses oracle rewards (e.g., comparing with ground truth), its accuracy improves with more samples, as coverage increases ( Brown et al., 2024 ) . However, in most cases, oracle rewards are unavailable, making that learning a reward model becomes the primary bottleneck. Additionally, increasing the number of samples raises computational costs, further limiting BoN’s scalability.

To reduce BoN’s cost, Sun et al. (2024a) propose speculative rejection, leveraging the correlation between partial and complete sequence scores. By scoring partial sequences and discarding low-scoring solutions early, it reduces computation while achieving BoN-like performance. An alternative to multiple sampling is fine-tuning the policy model to mimic BoN’s distribution. Gui et al. (2024) theoretically prove that BoN is optimal under specific constraints and fine-tune the model using best-of-n and worst-of-n data with preference-based IPO loss and SFT loss. Similarly, Amini et al. (2024) introduce variational BoN (vBoN), which uses PPO to minimize the gap between the policy model and BoN’s distribution, achieving superior performance without repeated sampling. Sessa et al. (2024) propose BOND, which fine-tunes the model to approximate BoN’s distribution by minimizing Jeffreys divergence (a combination of forward and backward KL divergences). Through iterative distillation, BOND reduces inference to a single sample while maintaining BoN-level performance.

##### Beam Search

Beam search is a classic tree search algorithm that traditionally expands and prunes branches based on partial sequence probabilities. Beam search is typically conducted at the token level. Recent advancements in large language models have led to modifications of beam search by integrating additional guidance signals. TreeBoN ( Qiu et al., 2024 ) iteratively expands branches and prunes low-quality responses using token-level rewards from DPO ( Rafailov et al., 2024 ) , maintaining high-quality sequences while reducing computation in a manner similar to beam search, on step level. Similarly, Yu et al. (2024a) train a value model from outcome supervision to score partial sequences, replacing token probabilities. Xie et al. (2023) improve stochastic beam search ( Kool et al., 2019 ) , balancing exploitation and exploration by using a policy model for self-evaluation for sampling instead of token probabilities. Ma et al. (2023) propose a process reward model to guide greedy search, introducing backtracking when child nodes have negative rewards. Snell et al. (2024) implement lookahead search via k-step rollouts for evaluating partial sequences, which can be seen as a specia case of MCTS. Reward-guided beam search, compared to token-probability-based approaches, better aligns with downstream task performance. By incorporating value models, rollouts, or backtracking, it also balances exploitation and exploration, enhancing sampling coverage.

##### Monte Carlo Tree Search

Incontrast to BoN and traditional beam search, Monte Carlo Tree Search (MCTS) is a lookahead search algorithm used for making optimal decisions in large search spaces ( Browne et al., 2012 ) , which can choose actions based on their expected returns. Traditional MCTS use Monte Carlo estimations to estimate state values in a search tree. As simulations increase, the search tree grows, values become more accurate, and the action-selection policy improves by prioritizing higher-value children. MCTS is suitable for large-scale search spaces. Compared to traditional algorithms, it efficiently explores complex search trees using estimated action values (expected rewards). Moreover, MCTS balances exploration and exploitation, allowing the search to not only focus on the most promising areas but also explore unknown regions, thereby avoiding getting stuck in local optimal solutions. As a result, it has shown strong performance on complex reasoning tasks with large search spaces, such as Go ( Silver et al., 2016 ) .

In MCTS, the nodes of the tree represent states, and the edges represent actions. MCTS constructs a search tree through multiple MCTS simulations to estimate the value (expected reward) of candidate actions in the current state. A typical MCTS simulation consists of four stages:

• Selection : Starting from the root, the algorithm selects edges (actions) recursively based on the action values. To encourage exploration, MCTS adds an exploration term to the action values, which promotes actions that have been visited less frequently. This term is typically calculated using a variant of PUCT ( Rosin, 2011 ) . As a result, MCTS is able to explore more actions and make more accurate estimates of their values. After selecting an action, a new state is reached, which corresponds to a node in the tree. The selection process is repeated continuously until a leaf node is reached.

• Expansion : If the leaf node reached by the selection process is not a terminal node, such as not being the <eos> token in the text, MCTS will expand this node. It selects the possible actions for the leaf node’s state and the resulting states after executing those actions as the child nodes of the current node, using the probabilities of these actions as the initial action values. Typically, MCTS expands the same number of actions each time.

• Evaluation : For the node reached by the selection process, MCTS evaluates the value of the node’s state to refine the current action values. Traditional MCTS uses a more efficient policy for Monte Carlo estimation (e.g., using a smaller model), a process known as rollout, and the policy used for estimation is called the rollout policy ( Sutton & Barto, 1998 ) . Another approach is to use an additional value model to predict the value of the current state without requiring extra sampling. In practice, rollout and the value model can be used together. The advantage of this state value estimation is that MCTS, compared to traditional lookahead search algorithms, can more efficiently estimate the expected reward of the current state in the future without traversing the entire search tree, making it more suitable for problems with large search spaces.

• Backpropagation : After evaluating the value of the node’s state, MCTS performs backpropagation to update the values of the actions along the path as well as the visit counts of the actions. Through backpropagation, MCTS refines its estimates of the action values, making the estimates more accurate.

The MCTS algorithm iteratively executes four stages until reaching a predefined simulation limit, selecting the most visited action from the root node.

MCTS algorithms based on LLMs mainly differ in action granularity and reward selection. Wan et al. (2024) analyze the impact of token-level and step-level actions on the search space. Step-level actions simplify the search process by reducing tree width but face challenges with large action spaces due to sentence diversity. In contrast, token-level actions narrow the action space but increase tree depth. Some approaches also adopt solution-level actions, where nodes represent entire solutions, and actions modify these solutions.

• Token-level actions: Liu et al. (2024c) use a token-level action space, where the LLM predicts the next token as the MCTS action, with the PPO value model evaluating states. Choi et al. (2023) employ token-level MCTS to ground generation in reference knowledge, reducing hallucinations. Zhang et al. (2023b) use token-level MCTS to guide Transformers in generating better programs, evaluating node values via rollouts. Accurately assessing token values is critical, but sparse reward signals pose challenges in deriving token-level value or reward models. Additionally, the deep search tree leads to efficiency issues, making the design of an efficient inference framework essential for token-level MCTS.

• Step-level actions: For multi-step reasoning tasks, step-level actions are a natural choice. Hao et al. (2023) propose RAP, an MCTS-based planning algorithm, which defines actions based on task-specific steps, such as posing sub-questions in math problems or moving blocks in Blocksworld ( Valmeekam et al., 2023 ) . RAP uses an LLM to predict future states instead of observing state transitions. Chen et al. (2024a) treat partial solutions as states and reasoning steps as actions for mathematical problems. Putta et al. (2024) ; Zhou et al. (2024) use browser interaction commands as actions in WebShop, a simulated e-commerce platform. Unlike task-specific steps, Qi et al. (2024) design five human-like reasoning actions for MCTS. To achieve o1-style reasoning, we may need to manually design actions like reflection and error correction, which should be incorporated during policy initialization.

• Solution-level actions: Solution-level MCTS treats the complete solution as a node state and modifications as actions. Zhang et al. (2024c) propose MCTSr, where nodes represent different answer versions, actions involve self-refinement, and rewards come from self-evaluation. Starting with a naive model-generated answer, MCTSr combines self-refinement with MCTS to achieve GPT-4-level performance on math problems. Building on MCTSr, Zhang et al. (2024d) use a pairwise preference reward model to evaluate whether a modified answer improves, estimating the new node’s value. Yan et al. (2024) use self-improvement as actions and design a consistency-based method to ensure factual correctness.

##### Other Tree Search Algorithms.

In addition to MCTS and Beam Search, traditional graph search algorithms like DFS, BFS, and A ∗ A^{*} are also used. The Tree-of-Thought (ToT) framework ( Yao et al., 2023a ) models reasoning as a tree, where nodes represent reasoning steps and branches represent continuations. By expanding and evaluating multiple reasoning solutions, ToT explores a broader solution space, introducing mechanisms like search, reflection, and backtracking to reconsider steps and explore alternatives. ToT employs DFS and BFS for its search process. Koh et al. (2024) propose an A ∗ A^{*} -inspired best-first search, using a multimodal LLM to evaluate nodes and a heuristic to select or backtrack. Lehnert et al. (2024) use A ∗ A^{*} to collect execution traces, training an encoder-decoder model to imitate these traces.

#### 5.3.2 Sequential Revisions

Compared to tree search, sequential revisions primarily conducts the search by iteratively refining the previous answer. The key feature of sequential revisions is that it generates improved answers based on reflections on previous answers or changes in the environment. Sequential revisions requires the model to have basic abilities for self-reflection and error correction, which can be introduced during the poicy initialization through SFT or Prompting, as discussed in Section 3 .

Sequential revisions can directly rely on the internal guidance such as self-evaluation. Madaan et al. (2023) propose to SELF-REFINE. It first generates an initial answer using a LLM, and then utilize the same LLM to iteratively provide feedback for its output and refine its output based on the self feedback. The iteration process stops when the maximum number of iterations is reached or when the model determines that it can stop. Snell et al. (2024) also uses a model with revision capabilities to perform revisions during inference, demonstrating that the accuracy of the answer improves as the number of revisions increases. Other work rely on observation or feedback from external environment. Both Yao et al. (2023b) and Shinn et al. (2023) are based on the model reflecting on or improving the next action based on external feedback observed after taking an action. Chen et al. (2024c) and Gou et al. (2024) use feedback based on the execution of generated code to allow the model to modify the generated code or debug.

There is still debate over whether Sequential Revisions is truly effective. For example, Huang et al. (2024a) argue that large models cannot self-correct properly without external feedback. However, the opposing viewpoint suggests that due to the existence of the DG-gap ( Leike, 2022 ) , large models may have a stronger ability to discern and improve the answers they have already generated, allowing for further refinement. Chen et al. (2024d) conduct empirical studies across a range of tasks and found that Sequential Revisions only achieves performance improvements over simpler methods like BoN when the accuracy of the discriminator (guidance) ≥ \geq 90%.

Paper Search Guidance Search Strategies Internal Guidance External Guidance Tree Search Sequential Revisions Math Verifier ( Cobbe et al., 2021 ) ✗ Env Feedback Best-of-N ✗ Self-consistency ( Wang et al., 2023a ) Model Uncertainty ✗ Best-of-N ✗ Speculative Rejection ( Sun et al., 2024a ) ✗ Env Feedback Best-of-N ✗ BoN ( Gui et al., 2024 ) ,vBoN ( Amini et al., 2024 ) ,BOND ( Sessa et al., 2024 ) ✗ Env Feedback Best-of-N † ✗ TreeBoN ( Qiu et al., 2024 ) ✗ Env Feedback Beam Search ✗ OVM ( Yu et al., 2024a ) Value Function Value Function Beam Search ✗ Xie et al. (2023) Self-evaluation ✗ Beam Search ✗ Ma et al. (2023) ✗ Env Feedback Beam Search ‡ ✗ Snell et al. (2024) ✗ Env Feedback Beam Search ✗ TS-LLM ( Wan et al., 2024 ) ✗ Env Feedback MCTS ✗ PPO-MCTS ( Liu et al., 2024c ) Value Function Value Function MCTS ✗ KCTS ( Choi et al., 2023 ) ✗ Env Feedback MCTS ✗ Zhang et al. (2023b) ✗ Env Feedback MCTS ✗ RAP ( Hao et al., 2023 ) Self-evaluation Heuristic Rules MCTS ✗ AlphaMath ( Chen et al., 2024a ) Value Function Value Function MCTS, Beam Search ✗ AgentQ ( Putta et al., 2024 ) Self-evaluation ✗ MCTS ✗ LATS ( Zhou et al., 2024 ) Self-evaluation, Model Uncertainty ✗ MCTS ✗ rStar ( Qi et al., 2024 ) Model Uncertainty ✗ MCTS ✗ MCTSr ( Zhang et al., 2024c ) Self-evaluation ✗ MCTS ✓ LLaMA-Berry ( Zhang et al., 2024d ) ✗ Env Feedback MCTS ✗ Mirror ( Yan et al., 2024 ) ✗ Heuristic Rules MCTS ✓ ToT ( Yao et al., 2023a ) ✗ Env Feedback, Heuristic Rules DFS,BFS ✗ Koh et al. (2024) ✗ Env Feedback A ∗ A^{*} ✗ Beyond A ∗ A^{*} ( Lehnert et al., 2024 ) ‡ ✗ Heuristic Rules A ∗ A^{*} ✗ Self-refine ( Madaan et al., 2023 ) Self-evaluation ✗ ✗ ✓ Snell et al. (2024) Self-evaluation ✗ ✗ ✓ ReACT ( Yao et al., 2023b ) ✗ Env Feedback ✗ ✓ Reflexion ( Shinn et al., 2023 ) ✗ Env Feedback ✗ ✓ Self-debug ( Chen et al., 2024c ) ✗ Env Feedback ✗ ✓ Critic ( Gou et al., 2024 ) ✗ Env Feedback ✗ ✓

As a summary, we list the research work in Table 2 , along with the specific categories of guiding signals and search strategies used, for the reader’s reference.

#### 5.3.3 Comparison of Tree Search and Sequential Revisions

As we mentioned in Section 5.3.1 , tree search typically samples multiple candidate solutions simultaneously, which allows some tree search algorithms, such as BoN, to be accelerated using parallel strategies. At the same time, the candidate solutions in tree search are relatively independent of each other, and the search process can encourage exploration during sampling, such as in MCTS. This broadens the coverage of candidate solutions. On the other hand, sequential revisions generally continue to search around a previously sampled solution, allowing for, incremental improvements, which may lead to better solutions in some cases. For example, Snell et al. (2024) show that sequential revisions with internal guidance outperform majority voting (a tree search strategy with internal guidance). However, since sequential revisions rely on previous attempts, the computational cost increases with the number of revisions made.

#### 5.3.4 Combination of Tree Search and Sequential Revisions

Tree search and sequential revisions can be used together. In tree search, using solution-level search nodes can be seen as a combination of tree search and sequential revisions ( Zhang et al., 2024c ; Zhang et al., 2024d ) . Additionally, Snell et al. (2024) combines BoN with sequential revisions by first randomly sampling N candidate solutions, then applying sequential revisions to these N solutions, and finally using a verifier to select the best solution from all of them. This combined approach achieves performance that surpasses BoN. Such results may demonstrate the potential of combining these two search strategies.

### 5.4 Speculation About the Search of o1.

In this section, we discuss the guiding signals and search strategies used during both the training-time search and inference-time search in o1.

##### Train-time search.

During training, o1 is more likely to employ tree search techniques, such as BoN or tree search algorithms, and primarily relies on external guidance. This is because the model needs to gradually enhance its reasoning capabilities during training, and tree can sample a large number of candidate solutions in parallel, efficiently providing the model with abundant high-quality training data. Furthermore, since real-time interaction is not required during training, various external environments can be accessed to validate the sampled solutions, such as executing code or verifying the accuracy of mathematical computations. This external guidance helps more accurately direct the model’s search process.

##### Test-time search.

For test-time search, o1 is more likely to use sequential revisions, combining internal guidance to continuously refine and correct its search through reflection. Through the example in the o1 blog ( OpenAI, 2024a ) , we can observe that o1’s reasoning style is closer to sequential revisions. Besides, using Tree Search for long reasoning processes can result in significant overhead. And during inference, it is difficult to rely on real-world environments for guidance, and ( Gao et al., 2023 ; Stroebl et al., 2024 ) point out that performing extensive searches based on proxy feedback, like reward models, can lead to overoptimization problem. While increasing the computations during inference, it can actually degrade performance. However, observations from o1’s blog suggest that the model’s performance continues to improve as the computational effort during inference increases. This leads us to believe that o1 primarily uses internal guidance during the inference stage. The computations during inference is mainly reflected in the length of the inference chain.

### 5.5 Scaling Law of Search

Prior to OpenAI’s release of o1, several studies explored inference-time scaling laws. Brown et al. (2024) studied BoN, dividing BoN into two stages: sampling solutions and selecting the best one via a verifier. They found that increasing the number of samples improved "coverage" (pass@1 accuracy) following a power law. Small models could achieve near 100% pass@1 accuracy on MATH with sufficient scaling. However, they noted a gap between best-of-n accuracy and pass@1, attributing it to the verifier’s limitations in identifying correct solutions.

Snell et al. (2024) analyzed the scaling of tree search and sequential revisions, showing both approaches scaled well with more computational resources. They found that, for a given computational budget, increasing model size was more effective for complex tasks, while sampling more tokens sufficed for simpler tasks. Lightman et al. (2024) examined reward signals in scaling and observed that outcome-reward-based best-of-n search plateaued as samples increased, while PRM-based best-of-n search avoided this issue.

While these studies showed performance gains with increased search computation, Gao et al. (2023) found the inverse scaling law where scaling best-of-n search could degrade performance due to distribution shift. The reward model, trained on original policy data, struggles to generalize to new policy. Stroebl et al. (2024) noted similar issues and suggested that other search algorithms, like MCTS, may also face inverse scaling challenges.

### 5.6 Challenges of Search for Reproducing o1

##### How to overcome Inverse Scaling

One approach is to reduce test-time search, as the inverse scaling phenomenon occurs primarily during large-scale search. However, this limits the scale of search. Alternatively, improving the reward model’s generalization to handle unseen states is another solution. Inspired by LLM development, this can be achieved by increasing the model’s size and training data, as validated in Gao et al. (2023) .

##### How to avoid over-thinking on simple tasks?

Not all problems require complex reasoning or search. For straightforward queries like “1+1=?”, engaging in elaborate analysis wastes computational resources and potentially introduces errors. Forcing reasoning on such problems wastes resources and causes delays. To address this, we could constrain the length of the chain of thought (CoT) using reward shaping with a length penalty. This reshaped reward balances minimizing superfluous search and solving problems effectively.

##### How to trade off tree search and sequential revisions?

Search scales across two dimensions: tree search and sequential revision. Combining both improves performance ( Zhao et al., 2024a ) , but with a fixed computational budget, the optimal allocation of resources remains unclear. This challenge is similar to balancing model size and data size under a fixed budget. Empirical scaling laws can provide guidance for resource allocation.

##### How to improve efficiency of Search?

A key challenge in scaling search is efficiency, as LLMs’ auto-regressive generation is limited by memory read-write speeds, restricting GPU utilization ( Dao et al., 2022 ) . Additionally, some tree search algorithms, like MCTS, lack inherent parallelism. Improving efficiency requires both engineering and algorithmic solutions. For example, engineering optimizations involves implementing KV-cache sharing, while algorithmic improvements can perform KV-cache compression ( Xiao et al., 2024 ; Zeng et al., 2024b ) and speculative sampling ( Yi et al., 2024 ) .

## 6 Learning

We have introduced policy initialization, which learns from human-expert data 1 1 1 policy initialization can also learn from a stronger model, which we ignores here for simplicity. , why do we still need reinforcement learning? What makes reinforcement learning essential is that the training data of reinforcement learning is unlimited which comes from the interaction with an environment. In contrast, the human-expert data is limited and expensive. Furthermore, reinforcement learning has the potential to achieve superhuman performance, since it learns from trial and error instead of human-expert data. While human-expert data captures human behavior and knowledge, reinforcement learning can lead to the discovery of strategies that humans may not be capable of. AlphaGo ( Silver et al., 2016 ) which utilized reinforcement learning, was able to defeat world-class human players in the game of Go by discovering novel strategies that were previously unknown to experts, for example the famout “37 move” of AlphaGo ( Silver et al., 2016 )

The reinforcement learning typically samples the trajectory using a policy and improves the policy based on the received rewards. In the context of o1, we hypothesize that the reinforcement learning process generates trajectories through a search algorithm rather than relying solely on sampling. One advantage of search methods is their ability to explore superior states or solutions compared to random sampling. For example, beam search prioritizes actions with the highest expected action values. Thus, search techniques can provide higher-quality training data than simple sampling. Under this assumption, the reinforcement learning of o1 could involve an iterative process of search and learning. In each iteration, the learning phase utilizes the search-generated outputs as training data to enhance the policy, while the improved policy is then applied to the search process in the next iteration. A prominent example of this search-and-learn iteration is AlphaGo Zero ( Silver et al., 2017 ) , which uses trajectory data obtained via Monte Carlo Tree Search (MCTS) for policy learning.

The train-time search is different from the test-time search. The test-time search outputs a solution with the maximum rewards or confidence in all candidate solutions. But at the training, all candidate solutions generated from search may be utilized by learning. We denote the set of state-action pairs output from search as D search D_{\text{search}} , and the set of state-action pairs in the optimal solutions from search as D expert D_{\text{expert}} . Therefore, D expert D_{\text{expert}} is a subset of D search D_{\text{search}} . We visualize the difference between D search D_{\text{search}} and D expert D_{\text{expert}} in Figure 8 .

### 6.1 Learning Methods

Given D search D_{\text{search}} , the policy can be improved using either policy gradient methods ( Sutton et al., 1999 ) or behavior cloning. This section provides a detailed overview of several key policy gradient methods. Among these, Proximal Policy Optimization (PPO) ( Sutton et al., 1999 ) and Direct Policy Optimization (DPO) ( Rafailov et al., 2023 ) are the most widely used reinforcement learning techniques for LLMs. It is also common to preform behavior cloning or supervised learning on the searched data ( Zelikman et al., 2022 ; Touvron et al., 2023 ) . The behavior cloning here differs from that in policy initialization discussed in Section 3 in that it learns the behavior derived from the search process, rather than from human expert.

#### 6.1.1 Policy Gradient

The policy gradient parameterizes the policy with θ \theta , which can be defined as π θ ​ ( a | s ) \pi_{\theta}(a|s) . θ \theta is updated with the following gradient:

∇ θ J ​ ( θ ) = 𝔼 π θ ​ [ Q ⁡ ( s t , a t ) ​ ∇ θ ​ log ⁡ π θ ​ ( a t | s t ) ] \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[Q(s_{t},a_{t})\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\right] (3) Q-value Q ⁡ ( s t , a t ) Q(s_{t},a_{t}) is often approximated with Monte Carlo sampling ( Sutton et al., 1999 ) or Temporal-Difference estimation ( Konda & Tsitsiklis, 1999 ) .

##### REINFORCE

REINFORCE algorithm ( Sutton et al., 1999 ) uses Monte Carlo to approximate action value: ∇ θ J ​ ( θ ) = 1 | D search | ​ ∑ ( s t , a t ) ∈ D search [ G t ​ ∇ θ ​ log ⁡ π θ ​ ( a t | s t ) ] , \nabla_{\theta}J(\theta)=\frac{1}{|D_{\text{search}}|}\sum_{(s_{t},a_{t})\in D_{\text{search}}}\left[G_{t}\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\right], (4) where the return G t G_{t} is the discounted cumulated rewards, D search D_{\text{search}} denotes all state-action pairs in the searched data.

##### Actor-Critic

The return G t G_{t} may bring high variance for the gradient estimation. Therefore, Actor Critic ( Konda & Tsitsiklis, 1999 ) replace G t G_{t} with the advantage function or Temporal-difference error, which defined A ⁡ ( s t , a t ) = R t + 1 + γ ​ V π θ ​ ( s t + 1 ) − V ⁡ ( s t ) A(s_{t},a_{t})=R_{t+1}+\gamma V_{\pi_{\theta}}(s_{t+1})-V(s_{t}) .

The advantage function in Actor-Critic algorithm involves the estimation of value function V ⁡ ( S ) V(S) , therefore it learns a value model to approximate the value function. Another benefit of using Temporal-difference error A ⁡ ( s t , a t ) A(s_{t},a_{t}) instead of G t G_{t} is that the estimation of G t G_{t} may require more computation for sampling. For example, some trajectories in beam-search are pruned before reaching the terminal state. We need to make additional sampling to estimate G t G_{t} for these intermediate states.

##### PPO

In policy gradient methods, the policy is updated using gradient ascent. However, when the policy update is too large, it can cause drastic changes in the policy, leading to poor performance or even divergence. TRPO ( Schulman et al., 2015 ) and PPO ( Schulman et al., 2017 ) address this problem with KL divergence constraint and clipping, which ensuring that policy updates are not too large.

Another benefit of TRPO and PPO is that it improves data utilization. It is more data-efficient to update the parameters θ \theta multiple times on the same example, like the multi-epoch training in machine learning. Repeatably learning on the same data is called Replaying buffer in reinforcement learning. Replaying buffer improves the data utilization, but making the learning off-policy, where the behavior policy ( π search \pi_{\text{search}} ) that generates D search D_{\text{search}} is not the same as the target policy ( π θ \pi_{\theta} ) that is to be optimized. TRPO ( Schulman et al., 2015 ) and PPO ( Schulman et al., 2017 ) alleviates this problem with KL divergence constraint and clipping.

PPO is a variant of Actor-Critic algorithm, which has been widely used for reinforcement learning for large language model, especially the RLHF ( Ouyang et al., 2022 ; Bai et al., 2022a ) . But the training of PPO typically involves 4 models for function approximation of π θ \pi_{\theta} , π search \pi_{\text{search}} , reward, value, which is expensive. GRPO ( Shao et al., 2024 ) alleviate this issue by estimating value function with Monte Carlo estimation instead of function approximation. Remax ( Li et al., 2024c ) is also proposed to simplify the training of PPO, which use the return of greedy decoding as the baseline of reduce the variance of reinforce algorithm.

It is not trivial to reimplement the performance of PPO, Huang et al. (2022) highlight 13 core implementation details of PPO, for example, using two distinct networks to predict policy and value respectively is better than sharing their parameters. Zheng et al. (2023c) ; Wang et al. (2024a) also empirically validate the influence of some implementation details on the performance of RLHF, for example, they found that it is helpful to normalize and clip reward.

##### DPO

DPO eliminate the cost of modeling value model and reference policy, meanwhile having low variance in reward/value estimation. The idea of DPO is to reparameterize reward function with the optimal policy π ∗ \pi^{*} , and transform the optimization of Bradley-Terry reward modeling to the optimization of the policy. The loss function of DPO is: ℒ DPO ​ ( π θ , π ref ) = − 𝔼 ( x , y w , y l ) ∼ 𝒟 search ​ [ log ⁡ σ ⁡ ( β ​ log ⁡ π θ ​ ( y w | x ) π ref ​ ( y w | x ) − β ​ log ⁡ π θ ​ ( y l | x ) π ref ​ ( y l | x ) ) ] \mathcal{L}_{\text{DPO}}(\pi_{\theta};\pi_{\text{ref}})=-\mathbb{E}_{(x,y_{w},y_{l})\sim\mathcal{D_{\text{search}}}}\left[\log\sigma\left(\beta\log\frac{\pi_{\theta}(y_{w}|x)}{\pi_{\text{ref}}(y_{w}|x)}-\beta\log\frac{\pi_{\theta}(y_{l}|x)}{\pi_{\text{ref}}(y_{l}|x)}\right)\right] (5)

where x x denotes the question, y w y_{w} denotes the positive solution and y l y_{l} denotes the negative solution. The parametrization of DPO can derive a kind of reward shaping: f ⁡ ( r , π ref , β ) ​ ( x , y ) = r ⁡ ( x , y ) − β ​ log ​ ∑ y π ref ​ ( y | x ) ​ exp ⁡ ( − r ⁡ ( x , y ) β ) f(r,\pi_{\text{ref}},\beta)(x,y)=r(x,y)-\beta\log\sum_{y}\pi_{\text{ref}}(y|x)\exp\left(-\frac{r(x,y)}{\beta}\right) (6) Here, the term β ​ log ​ ∑ y π ref ​ ( y | x ) ​ exp ⁡ ( − r ⁡ ( x , y ) β ) \beta\log\sum_{y}\pi_{\text{ref}}(y|x)\exp\left(-\frac{r(x,y)}{\beta}\right) serves as the baseline for r ⁡ ( x , y ) r(x,y) , which explains why DPO does not encounter the high variance issue associated with the REINFORCE algorithm. Estimating this baseline is computationally expensive due to the large action space, but DPO eliminates this estimation by leveraging the Bradley-Terry model.

DPO has been widely used as the alternative for PPO in RLHF ( Dubey et al., 2024 ) . Even though the search does not provide the preference data directly, we can still construct preference pairs from D search D_{\text{search}} . LLama-3 ( Dubey et al., 2024 ) uses the positive and negative examples from rejected sampling as the preference data for DPO. MCTS-DPO ( Xie et al., 2024 ) and SVPO ( Chen et al., 2024b ) collect a number of step-level preference pairs from state-action pairs from MCTS, and use the preference data for DPO.

#### 6.1.2 Behavior Cloning

Behavior cloning, or supervised learning, employs the expert policy as the target and seeks to reduce the discrepancy between the policy π θ \pi_{\theta} and the expert policy π expert \pi_{\text{expert}} . While π expert \pi_{\text{expert}} may not represent a true expert policy, it is generally more effective than π θ \pi_{\theta} . Furthermore, π expert \pi_{\text{expert}} improves with increased computational effort, indicating that, with sufficient resources, π expert \pi_{\text{expert}} could approach the performance of a true expert policy. For LLM, the loss function of behavior cloning is cross-entropy loss. min θ − 𝔼 ( s , a ) ∼ π expert ​ [ log ⁡ π θ ​ ( a | s ) ] \text{min}_{\theta}-\mathbb{E}_{(s,a)\sim\pi_{\text{expert}}}\left[\log\pi_{\theta}(a|s)\right]

D search D_{\text{search}} contains all state-action pairs from search, including the negative solution, therefore it can not be taken as the expert data. In contrast, the state-action pairs in D expert D_{\text{expert}} receive the highest rewards compared with other pairs. Therefore, D expert D_{\text{expert}} can be taken as the expert data. The expert data from search may not really have a high quality, but it is better than the data sampled from the current policy. And as we scale the compuation of search, the expert data generated from search becomes more optimal. For example, Gao et al. (2023) found scaling best-of-n search enlarges the distance between policy of the best-of-n solution and the current policy.

min θ − 1 | D expert | ​ ∑ ( s , a ) ∈ D expert [ log ⁡ π θ ​ ( a | s ) ] , \text{min}_{\theta}-\frac{1}{|D_{\text{expert}}|}\sum_{(s,a)\in D_{\text{expert}}}\left[\log\pi_{\theta}(a|s)\right], (7)

The approach of iterating search and behavior cloning is called Expert Iteration in Anthony et al. (2017) . AlphaGo Zero ( Silver et al., 2017 ) is a well-known example of expert iteration, which uses the policy of MCTS for behavior cloning.

Although Expert iteration uses behavior cloning which can be seen as the supervised learning, it is different from policy initialization introduced in Section 3 , where the expert data comes from human expert or a stronger model. The expert data of expert initialization comes from the interaction with the environment, i.e., search.

A well-known example of expert iteration for large language model is STaR ( Zelikman et al., 2022 ) that uses reject sampling as the search algorithm to filter the examples generated by LLM with incorrect answers and finetune LLM on the remaining examples. LLama-2 ( Touvron et al., 2023 ) utilizes the method of STaR for RLHF and found it achieve the comparable performance with PPO. V-Star ( Hosseini et al., 2024 ) follows Star to use reject sampling to filter high-quality examples, but they train a verifier using DPO to provide reward for reject sampling rather than relying on the ground-truth answer. Their verifier also works at the test-time, by applying on best-of-n search. Wan et al. (2024) ; Tian et al. (2024a) ; Chen et al. (2024a) ; Zhang et al. (2024b) follows AlphaGo Zero to use MCTS as the search algorithm and finetune LLM on the solutions with the highest or the top-k highest reward in the tree. The main difference of their work between STaR is that they used different search algorithm.

#### 6.1.3 Speculation about the learning of o1

We make some comparison on the PPO, DPO and behavior cloning to see which one is more likely to be used for o1. The differences between the three methods in terms of memory cost and data utilization are summarized in Table 3 .

##### Memory Cost

PPO requires storing reward function, value function and reference policy in memory, which is expensive. While DPO eliminates the reward model and value model, which is simpler and more memory-efficient than PPO. But DPO is based on Bradley-Terry model and requires the preference data. For some environment, where the ground truth is available, it would be better to learn a policy with PPO using the reward signal, instead of learning from preference data. Behavior cloning even does not need reference policy, thus is the most memory-effient among three learning methods.

##### Data Utilization

The difference among the 3 learning methods is not only on the learning algorithm, but also on the training data. PPO and DPO use all state-action pairs from search ( D search D_{\text{search}} ), even those with negative rewards. While behavior cloning adopts the subset of state-action pairs from search with high rewards ( D expert D_{\text{expert}} ). Therefore, PPO and DPO have better data utilization than behavior cloning, since the negative action or solution can also provide useful signal for improving policy.

Havrilla et al. (2024) empirically compare the performance between PPO ( Schulman et al., 2017 ) and behavior cloning on GSM8K and MATH, and they find the behavior cloning (expert iteration) consistently outperforms policy gradient. It requires more empirical comparison on these methods.

It is likely that the learning of o1 results from the combination of multiple learning methods. In this framework, we hypothesize that the learning process for o1 begins with a warm-up phase using behavior cloning, followed by a transition to PPO or DPO once the improvements from behavior cloning plateau. This approach is grounded in the idea that behavior cloning is more efficient than PPO or DPO, thereby accelerating the warm-up phase. However, behavior cloning is limited in that it only learns from the highest-reward solutions and disregards negative solutions. Consequently, further optimization may require the use of PPO or DPO, which provide better data utilization. This pipeline is consistent with the post-training strategies employed in LLama2 ( Touvron et al., 2023 ) and LLama3 ( Dubey et al., 2024 ) .

### 6.2 Scaling Law of Reinforcement Learning

The relationship between the loss, computational cost, model parameters, and data size during the pre-training phase of large models follows a power-law scaling law. But does reinforcement learning (RL) in large language models also exhibit a scaling law? The blog of OpenAI ( OpenAI, 2024a ) shows that there is a log-linear scaling law between reasoning performance and train-time compute. However, aside from this, there has been little research on the scaling laws related to reinforcement learning.

OpenAI has also investigated the scaling laws in reinforcement learning ( Hilton et al., 2023 ) , their experiments focused on traditional reinforcement learning tasks, such as Dota 2, and did not involve LLMs. They found that the performance of reinforcement learning is improved with the increase of the number of model parameters and interactions with environment, which follows power law. They were able to derive the optimal number of model parameters and interactions with environment under a fixed computational budget.

Tuyls et al. (2024) studied the scaling laws of imitation learning in traditional reinforcement learning tasks, such as Atari. They also observed a power-law relationship between the imitation-learning loss and scale factors, including model size, data size, and computation budget. However, the data used for imitation learning came from expert annotations, rather than being generated through interactions with environment.

Some studies on reinforcement learning with large models have experimentally explored the relationship between LLM performance and the number of iterations ( Zelikman et al., 2022 ; Xie et al., 2024 ) . However, these studies only conducted small-scale validations, showing that scaling the number of iterations is effective, but they did not establish scaling laws that could be used to predict results for larger-scale experiments. In order to conduct large-scale reinforcement learning like o1, it is crucial to investigate the scaling laws of reinforcement learning on LLMs.

### 6.3 Challenges of Learning for Reproducing o1

##### How to improve Training Efficiency?

The primary bottleneck in training efficiency arises from the train-time search process, as the time required for LLM generation on the same batch exceeds that of training, with search being particularly slow. For instance, in the open-source project MCTS-DPO ( Xie et al., 2024 ) , the majority of the training time is consumed by the MCTS search, leading to training times of up to one week on an A800 GPU using the MATH dataset. There are two potential strategies for accelerating training: 1. Improving the search algorithm and implementation, which has been discussed in the search section and will not be reiterated here. 2. Extending learning beyond the data generated by online search to include data from previous search iterations. While reusing data from previous iterations may introduce issues related to off-policy learning, it increases data utilization and consequently reduces the search scale.

##### How to learn a Strong Question Generator.

We have introduced how the solutions generated by search can be used for learning. But the data for learning includes not only the solution but also question. As the policy of LLM improves, the challenging questions become simple. Therefore, it may be important to update the question or initial states. For example, the new questions can be more challenging or explore the new domains. Wizzrd-LM Xu et al. (2024) proposes to prompt a strong LLM like chatgpt to generate a more challenging question or another question that is related to the given question. But the generation of new question is independent from the performance of the policy to be optimized. The problem of updating questions is also related to Curriculum Learning ( Wang et al., 2022a ) , especially automatic curriculum learning ( Kumar et al., 2010 ) . Generating questions conditioned on the policy for LLM is challenging, since the generated questions may not be suitable or even unsolvable. Learning on these questions are not helpful for improving policy of LLM.

##### How to Narrow the Distribution Shift in off-policy learning?

The solutions generated by search is typically better than the data sampled from the current policy. The result is that the data produced by search can be considered as originating from a better policy. Using search-generated data for policy gradient training constitutes off-policy learning. To mitigate the distribution shift of policy in off-policy learning, one straightforward approach is to limit the scale of the search. The smaller the search scale, the less pronounced the distribution-shift issue becomes. Alternatively, we can implement search with sampling from the current policy, then there is no distribution shift problem.

An alternative approach is to incorporate off-policy learning methods. While techniques such as importance sampling and KL divergence constraints, employed in TRPO ( Schulman et al., 2015 ) and PPO ( Schulman et al., 2017 ) , are effective. However, they require knowledge of the policy probability associated with the search data, denoted as π search \pi_{\text{search}} , which is unavailable.

Another approach to make use of behavior cloning to turn the off-policy learning to on-policy learning. We can first apply behavior cloning on searched data D search D_{\text{search}} to narrow the gap between π θ \pi_{\theta} and π search \pi_{\text{search}} . After completing the behavior cloning, policy gradient training can then be conducted on the searched data. The pipeline of policy gradient following behavior cloning occurs at each iteration, which is different the speculation introduced in 6.1.3 , where we perform behavior cloning at early iterations and PPO at the remaining iterations. Furthermore, this approach can be supplement for our speculation: We perform behavior cloning at the warm-up stage, and then combine behavior cloning and PPO at each iteration.

## 7 Open-source o1 Project

Although o1 has not published a technical report, the academic community has made available several open-source implementations of o1. All of these implementations can be viewed as components or special cases of the o1 framework introduced in this paper. In Table 4 , we summarize the methods adopted by these open-source projects in the areas of policy initialization, reward design, search, and learning.

There are also some o1-like models from industry, for example, k0-math, skywork-o1 ( o1 Team, 2024 ) , Deepseek-R1 ( Shao et al., 2024 ) , QwQ ( Team, 2024 ) and InternThinker ( Cai et al., 2024 ) . We do not discuss about these models, since they have not open sourced their techniques.

### g1

g1 ( bklieger, 2024 ) may be the earliest project that attempts to reimplement o1, they take the approach of prompt engineering. They prompt LLM to self-reflect and propose multiple solutions to clone the behavior of o1.

### Thinking Claude

Thinking Claude ( richards, 2024 ) works similarly to g1, which prompts LLM with more complex and fine-grained actions, like problem analysis and progress tracking. Both g1 and Thinking Claude can reshape the behavior of LLM to be like that of o1, but they have not validated their prompts on reasoning benchmarks.

### Open-o1

Open-o1 ( Open-Source-O1, 2024 ) provides a SFT dataset, where each response contains long cot. But it is not clear where does these data come from. We suspect that these data are coming from human experts or a strong LLM. Open-o1 found that training LLama-3-8B and Qwen-7b on their dataset can not only shape the style of model response to be like o1, but also improve the model performance on reasoning benchmarks.

### o1 Journey

The o1 journey ( Qin et al., 2024 ; Huang et al., 2024b ) is outlined in two technical reports.

##### Part 1

In Part 1 ( Qin et al., 2024 ) , the tree data generated through beam search is traversed, with specific nodes refined by GPT-4 and then used in supervised fine-tuning. The examples presented in the paper highlight the model’s self-reflection capabilities, which comes from the refinement of GPT-4. The approach adopted in Part 1 can be described as expert iteration, where SFT is applied to the data generated via search. Part 1 also compares PRM from o1-mini anotation versus Math-Shepherd ( Wang et al., 2024c ) , they found that o1-mini outperforms Math-Shepherd.

##### Part 2

Part 2 ( Huang et al., 2024b ) of the o1 journey introduces a radically different approach. While Part 1 focuses on reinforcement learning, Part 2 attempts to distill o1-mini. Although o1-mini conceals the chain-of-thought (CoT) and only outputs the summary of CoT, Part 2 tries to recover the hidden CoT by prompt o1-mini to augment the summary. Through distillation, they found that Qwen-72B outperforms o1-preview on AIME. However, it does not mean that distillation enables the student model to outperform the teacher model, since o1-mini also surpasses o1-preview on AIME.

### Open-Reasoner

The framework of Open-Reasoner ( Wang et al., 2024b ) is akin to AlphaGo ( Silver et al., 2016 ) , utilizing reinforcement learning to enhance the model’s performance. During the testing phase, Monte Carlo Tree Search (MCTS) is employed to identify optimal solutions. This search algorithm is applied exclusively during testing, while the training data is derived by sampling with the current policy. Additionally, Open-Reasoner employs a method similar to Math-Shepherd ( Wang et al., 2024c ) for training the reward model.

### Slow Thinking with LLMs

Similarly to the o1 journey, Slow Thinking with LLMs is alos outlined in two technical reports ( Jiang et al., 2024b ; Min et al., 2024 ) .

##### Part 1

The part 1 of Slow Thinking with LLMs ( Jiang et al., 2024b ) is similar to OpenReasoner ( Wang et al., 2024b ) , incorporating both reinforcement learning and test-time search. But unlike Open-Reasoner, it employs the DPO instead of PPO algorithm during training. In the testing phase, it also employs the MCTS algorithm for search.

##### Part 2

The part 2 of Slow Thinking with LLMs ( Min et al., 2024 ) distills from QwQ ( Team, 2024 ) and Deepseek-R1 ( Shao et al., 2024 ) and tries two methods for reinforcement learning: DPO and SFT on data generated from reject sampling. They found that distilling on thousands of examples from QwQ and Deepseek-R1 can significantly bring a substantial improvement on challenging reasoning tasks and reinforcement learning can bring further improvement based on distillation.

### Marco-o1

Marco-o1 ( Zhao et al., 2024a ) integrates the data from Open-o1 with data generated by the model itself through the MCTS algorithm for SFT training. Marco-o1 demonstrates that prompting the model for self-reflection after each step of the MCTS process enhances the effectiveness of the search.

### o1-coder

o1-coder ( Zhang et al., 2024g ) attempts to reimplement o1 on the code generation. They train a generator to generate test case for providing outcome reward. With outcome rewards, they use MCTS algorithm to generate code solutions, which are then used for improving policy model through SFT. Their train a PRM following Wang et al. (2024c) which is updated with the improvement of the policy.

## 8 Future Directions

##### How to adapt o1 to general domains?

The key to adapt o1 to general domains is the availability of a general reward models. How can we learn a general reward model for general domains? For reasoning tasks, there is typically a standard answer, allowing for the training of an outcome reward model. Using the reward shaping techniques introduced in Section 4 , a process reward model can be further trained on top of the outcome reward model. For non-reasoning tasks, such as alignment tasks, obtaining an outcome reward is often challenging. In such cases, methods introduced in Section 4 , such as learning from feedback, become crucial. A Bradley-Terry model ( Leike et al., 2018 ) can be trained from preference data, or a reward model can be developed from expert data using inverse reinforcement learning.

##### How to introduce multiple modality to o1?

The challenge of incorporating multiple modality into o1 primarily lies in the alignment or grounding between text and other modalities. For example, when the image modality is introduced, the model needs to handle the fine-grained relationships between long CoT and images. When CoT becomes lengthy, establishing such connections becomes more difficult. Therefore, Gao et al. (2024) incorporated the image modality into the CoT, so that the CoT generated by the model includes both text and images. This approach enhances the fine-grained connections between the generated text and images, but it also introduces new challenges. Introducing information from the image or other modalities into the COT significantly increases its length, leading to increased inference latency. A potential solution to this issue could be to use continious representations to generate CoT, replacing textual and other modality-specific information.

##### How to learn and search with a world model?

OpenAI has outlined a 5-stage roadmap to AGI, with stage 2 focusing on becoming a strong reasoner, stage 3 centered on becoming an agent.The o1 has already reached stage 2, achieving reasoning capabilities on par with human experts. Consequently, o1’s next goal is to progress to stage 3—being able to take actions in real environment and solving real-environment tasks.

The key to extending o1 to real-world environments lies in reward modeling, more specifically in environment or world modeling. This concept of world models was also introduced in Section 4 . When a simulator of the real environment is established, the agent can interact with the world model rather than directly with the environment. The world model plays a vital role in both training and testing the agent. During training, interacting with the world model is more efficient than direct interaction with the environment. During testing, the agent can leverage the world model for planning or searching, identifying the optimal strategy before executing actions in the real environment. Without a world model, it is impossible for the model to perform search or planning, as the real environment is not time-reversible. For example, in the game of Go, once a move is made, it cannot be undone.

## 9 Conclusion

In this paper, we present a roadmap for reproducing o1 from the perspective of reinforcement learning, emphasizing key components such as policy initialization, reward design, search, and learning. We offer a comprehensive survey of these components and show that existing open-source projects that attempt to reproduce o1 are variations of our roadmap. Finally, we hope this roadmap inspire further research on overcoming the challenges involved in reproducing o1.