Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspective — part 2/8

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

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