PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhiyuan Zeng, Qinyuan Cheng, Zhangyue Yin, Bo Wang, Shimin Li, Yunhua Zhou, Qipeng Guo, Xuanjing Huang, Xipeng Qiu

arXiv:2412.14135v1cs.AIcs.LG

TL;DR

The paper frames o1’s reasoning capability as a motivation for examining reinforcement learning as an alternative to approaches centered on imitation. It proposes a four-part roadmap and describes search-guided learning, while noting that learned reward models can become misaligned with a changing policy.

  • Problem

    The paper focuses on how reinforcement learning can support o1-like reasoning through policy initialization, reward design, search, and learning.

    Source: §1 · p. 3

  • Method

    The paper surveys a roadmap combining policy initialization, reward design, search, and learning, with search-generated interaction data used to improve the policy.

    Source: §1 · pp. 3–4

  • Results

    The roadmap describes search as generating higher-quality solutions for training and testing and learning as using search-generated data to improve the policy.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors conclude that existing open-source o1-reproduction projects can be viewed as components or variants of the roadmap.

    Source: §9 · p. 30

    A reward model trained on interactions with an older policy may fail to adapt as the policy changes, so it must be updated alongside policy improvements.

    Source: §4.2.1 · p. 11

Abstract

from arXiv · show

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. 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.

1 Introduction

The paper frames o1 as a reasoning milestone and proposes a reinforcement-learning roadmap with policy initialization, reward design, search, and learning. It describes how these components support search-guided policy improvement while noting a distribution-shift risk during test-time search.

1 Introduction

  • o1’s reported performance improves with increased reinforcement-learning and inference computation, motivating a shift toward scaling both training and inference compute.The paper cites OpenAI (2024a;b) for the reported trend.Source: §1 · p. 3
  • The roadmap combines policy initialization, reward design, search, and learning, with search generating solutions for training and testing and learning using search-generated data to improve the policy.The authors state that this interaction data is not manually curated and may avoid costly annotation.Source: §1 · p. 3
  • Pretraining, instruction fine-tuning, and prompts or supervised fine-tuning can establish human-like reasoning behaviors that help models explore solution spaces.The paper describes behaviors such as task composition, self-evaluation, and self-correction.Source: §1 · p. 3
  • Reward shaping can densify sparse outcome rewards, while preference- or expert-data reward models can provide signals when environmental rewards are unavailable.The paper also notes that reward-model construction can extend toward world models.Source: §1 · pp. 3–4
  • Search can produce higher-quality training data than simple sampling and improve sub-optimal policies at inference, but test-time scaling may cause inverse scaling under distribution shift.The policy, reward, and value models may be trained on a different distribution from the one encountered during evaluation.Source: §1 · p. 4
  • Reinforcement learning can use search-generated data through policy gradients or behavior cloning, which differ in data use, simplicity, and memory efficiency.The paper cites AlphaGo Zero as an example combining MCTS with behavior cloning.Source: §1 · p. 4

2 Background

The background describes reinforcement learning as an agent interacting with an environment and learning from rewards. For LLMs, actions and states can correspond to generated tokens, steps, or complete responses and their preceding context.

2 Background

  • Reinforcement learning differs from static-dataset learning by having the agent interact with an environment and receive rewards as it explores.Figure 3 visualizes the interaction for LLM reinforcement learning.Source: §2 · p. 4
  • An agent selects actions according to a policy, often represented as a probability distribution over actions given a state.The environment responds with a next state and reward.Source: §2 · pp. 4–5
  • For LLMs, the agent is the language model, and its state includes the user input and the model’s earlier outputs.Actions may be a token, a step, or a full solution.Source: §2 · p. 5
  • Environmental feedback may be stochastic, with next states and rewards drawn from a transition distribution, or deterministic, with fixed outcomes for a state-action pair.The paper gives dialogue as a stochastic example and mathematical problem solving as deterministic.Source: §2 · p. 5

3 Policy Initialization

Policy initialization builds on pretraining and instruction fine-tuning, then activates human-like reasoning behaviors that support exploration. The section reviews capability foundations and implementation approaches while identifying unresolved challenges in behavior orchestration and generalization.

3.1.1 Language Understanding and Generation

  • Pretraining on large text corpora establishes language understanding and generation capabilities, with syntactic patterns emerging before logical consistency and abstract reasoning.The passage emphasizes training duration and data composition alongside model scaling.Source: §3.1.1 · p. 5, §3.1 · p. 5

3.1.2 World Knowledge Acquisition and Storage

  • Pretraining supports world-knowledge acquisition and storage across factual, procedural, and conceptual domains, while abstract concepts require more extensive training than factual knowledge.The cited discussion describes knowledge compression and generalization as well.Source: §3.1.2 · p. 6

3.1.3 Basic Reasoning Abilities

  • Pretraining develops reasoning from simple inference toward complex reasoning through pattern matching, analogy, logical inference, and sequential processing.The passage links code, mathematical proofs, and procedural texts to these capabilities.Source: §3.1.3 · p. 6

3.2 Instruction Fine-Tuning

  • Instruction fine-tuning turns pretrained models into task-oriented agents, with effectiveness depending on the diversity of instruction data and the quality of instruction-response pairs.The cited examples include FLAN’s generalization to novel tasks and Alpaca’s curated high-quality data.Source: §3.2 · p. 6

3.3 Human-like Reasoning Behaviours

  • The section identifies six human-like reasoning behaviors and discusses prompt engineering and supervised fine-tuning as complementary ways to elicit or teach them.Examples include problem analysis, decomposition, task completion, alternative proposals, self-evaluation, and self-correction.Source: §3.3 · pp. 7–8

3 Policy Initialization

  • Policy initialization constrains an initially broad action space through pretraining and instruction fine-tuning, while reasoning behaviors can be activated through prompts or supervised fine-tuning.The paper frames these stages as preparation for subsequent learning and search.Source: §3 · p. 5, Figure 4 · p. 6, §3.4 · p. 8

3.4 Speculation About the Policy Initialization of o1

  • Long-form generation remains limited, and logically sequencing reasoning behaviors is challenging because orchestration requires decision-making, computation, and stronger logical reasoning.The systematic choice of when to deploy particular behaviors remains an open challenge.Source: §3.4 · pp. 8–9

3.5 Challenges of Policy Initialization for Reproducing o1

  • Initialization faces a trade-off between efficient sampling from concentrated action distributions and preserving diversity for exploration; human demonstrations can constrain discovery of better strategies.The section also identifies domain generalization as a challenge because reasoning behaviors must extend beyond mathematics and coding to tasks such as safety.Source: §3.5 · p. 9

4 Reward Design

Reward design supplies guidance for search and learning through environment signals, learned reward models, or reward shaping. The section compares reward granularities, reviews methods, and discusses challenges and possible designs for o1.

4 Reward Design

  • The section treats reward as numerical guidance for both training and inference, with well-designed signals potentially accelerating learning convergence and search.Source: §4 · p. 9

4.1 Outcome Reward vs Process Reward

  • Outcome rewards assess final-answer correctness but omit intermediate supervision, while process rewards score intermediate steps and can be token- or step-level.Outcome reward is a special case of process reward with intermediate-step rewards set to zero; the corresponding models are ORM and PRM.Source: §4.1 · p. 10, §4.2 · p. 10

4.2.1 Reward from Environment

  • Environment rewards can be used directly or simulated by a model, but simulated rewards may become misaligned as the policy changes.AI judgment avoids this distribution-shift issue because it does not depend on the policy model; simulated reward models should be updated alongside policy improvements.Source: §4.2.1 · p. 11

4.2.2 Reward Modeling from Data

  • Preference data supports reward learning, while inverse reinforcement learning recovers rewards from expert trajectories but lacks evidence of large-scale LLM use.Preference data should reflect downstream-task performance; human-preference supervision may degrade true performance.Source: §4.2.2 · pp. 11–12

4.2.3 Reward Shaping

  • Reward shaping can densify outcome signals, but policy-dependent value estimates may fail across policies and improper shaping can harm learning and search.Potential-based shaping preserves the optimal policy when its equation is satisfied; DPO is described as implicitly applying this form of shaping to preference rewards.Source: §4.2.3 · p. 12

4.3 Speculation About the Reward Design of o1

  • The authors speculate that o1 combines reward methods, favors process rewards for long reasoning tasks, and uses preference or expert data when environmental rewards are unavailable.They also conjecture a broad reward model adaptable through ground-truth and solution pairs, with rewards more likely generated by an LLM than value heads.Source: §4.3 · pp. 12–13

4.4 Challenges of Reward Design for Reproducing o1

  • Reward design challenges include policy-induced distribution shift, choosing reward granularity for language, and selecting feedback and data amounts for complex tasks.Preference feedback may degrade performance on code or math tasks, and evaluating reward effectiveness becomes harder as task complexity increases.Source: §4.4 · p. 13

4.5 Generalization

  • For general tasks, the section frames reward construction around ensembles of domain-specific rewards and world models.Ensembles require combining reward signals effectively; world models can predict rewards and next states or their representations.Source: §4.5 · p. 13, §4.5.1 · p. 13, §4.5.2 · p. 14

5 Search

Search uses guidance to select among candidate solutions generated by search strategies. The paper presents it as relevant to both training and inference, where additional computation can support finding better answers.

5 Search

  • Search includes repeated attempts or strategic exploration guided by rewards or heuristics; self-consistency and Best-of-N are cited as inference search methods.The passage notes that pass@k improves with more samples and that search can let small models outperform larger ones, at additional inference-time computation.Source: §5 · p. 14

5.1 The role of Search in o1

  • Search policies can produce better solutions than naive sampling, either as final outputs or as training data for iterative policy improvement.The paper distinguishes training-time search from test-time search.Source: §5.1 · p. 14
  • Longer reasoning expands the search space, making naive sampling potentially inefficient; advanced strategies can generate training data to update the policy iteratively.At inference, the paper interprets spending more time thinking as search using additional computation to find better answers.Source: §5.1 · p. 15
  • Search separates candidate-generation strategies from selection guidance, with tree search and sequential revision orthogonal to internal and external guidance.Either guidance type can be paired with either strategy type.Source: §5.1 · p. 15

5.2 Search Guidance

Search guidance directs candidate generation using model-internal signals, external task feedback, or both. The section compares their transferability and costs, then describes value functions as a combined signal.

5.2.1 Internal Guidance

  • Model uncertainty supports candidate selection, but it does not directly measure answer accuracy; self-evaluation can help, though its usefulness depends on evaluation ability and calibration.The section notes that models may fail to evaluate answers accurately without feedback.Source: §5.2.1 · pp. 15–16

5.2.2 External Guidance

  • External guidance uses task-related feedback, including rewards and heuristic rules, but constructing environments or proxy feedback can add costs and introduce distribution-shift risks.Feedback can include outcome or process rewards, compilation results, intermediate-step correctness, and unit tests.Source: §5.2.2 · p. 16

5.2.3 Comparison of Internal and External Guidance

  • Internal guidance is task-agnostic and transferable, whereas external guidance better aligns search with task performance but may require costly environments and face out-of-distribution issues.At inference, ground truth is often unavailable and environment interaction can be costly.Source: §5.2.3 · p. 16

5.2.4 Combination of Internal and External Guidance

  • Combining internal signals with proxy feedback can guide selection, while value functions estimate expected cumulative reward from states or state-action pairs.Value estimates can be inaccurate, especially with sparse rewards or high-dimensional outputs.Source: §5.2.4 · pp. 16–17, Figure 7 · p. 17

5.3 Search Strategies

The section surveys tree search and sequential revisions as complementary ways to search for better solutions. Their effectiveness depends on guidance quality, search design, and computational cost.

5.3.1 Tree Search

  • Tree search explores multiple candidates, while BoN selects among independent samples and beam search expands and prunes branches using probabilities or additional guidance.BoN can over-sample high-probability options; reward-model quality and sampling costs constrain its scalability, while speculative rejection and distribution-matching fine-tuning offer alternatives.Source: §5.3.1 · pp. 17–18
  • MCTS estimates action values through repeated simulations, balancing exploration and exploitation before selecting the most-visited root action.Its stages are selection, expansion, evaluation, and backpropagation; evaluation can use rollouts, a value model, or both.Source: §5.3.1 · pp. 18–19
  • Tree-search node granularity ranges from token-level to solution-level, trading narrower action spaces against deeper trees and broader steps against wider trees.The section also surveys token-, step-, and solution-level MCTS, each with distinct action and evaluation choices.Source: §5.3.1 · pp. 17, 19
  • Other tree-search approaches include ToT with DFS or BFS and A*-inspired methods that evaluate nodes and guide selection or backtracking.A* has also been used to collect execution traces for model training.Source: §5.3.1 · pp. 19–20

5.3.2 Sequential Revisions

  • Sequential revisions iteratively refine prior answers using self-feedback or environmental observations, and require reflection and error-correction abilities.Examples include SELF-REFINE and code revision based on execution feedback.Source: §5.3.2 · p. 20
  • Sequential revisions outperform simpler methods like BoN only when discriminator (guidance) accuracy is ≥90%, according to an empirical study across tasks.The effectiveness of sequential revisions remains debated.Source: §5.3.2 · p. 20

5.3.3 Comparison of Tree Search and Sequential Revisions

  • Tree search can parallelize relatively independent candidates and broaden coverage, while revisions make incremental changes around earlier attempts but accumulate cost with each revision.One cited comparison found sequential revisions with internal guidance outperforming majority voting.Source: §5.3.3 · p. 20

5.3.4 Combination of Tree Search and Sequential Revisions

  • Combining tree search with revisions can surpass BoN by revising sampled candidates and then selecting among them with a verifier.Solution-level search nodes can also combine tree search and revisions.Source: §5.3.4 · p. 20

5.4 Speculation About the Search of o1.

The authors speculate that o1 uses external guidance and tree search during training, then internal guidance and sequential revisions at inference. They relate this proposal to reported scaling behavior and practical constraints.

Train-time search

  • During training, o1 may use tree search with external guidance to generate many parallel candidate solutions validated by environments such as code execution or math checks.The authors suggest this can efficiently provide high-quality training data as reasoning capabilities improve.Source: §5.4 · p. 21

Test-time search

  • At inference, o1 may use internal guidance and sequential revisions, since long tree searches are costly and proxy-reward searches can overoptimize despite increasing computation.The authors infer this from o1’s reasoning style and reported performance gains as inference effort increases, particularly through longer reasoning chains.Source: §5.4 · pp. 21–22

5.5 Scaling Law of Search

Prior studies report that additional search computation can improve performance, but scaling outcomes depend on the search method, task, and guidance quality. Distribution shift can also produce inverse scaling.

5.5 Scaling Law of Search

  • More BoN samples improved pass@1 accuracy on MATH following a power law, but verifier limitations left a gap between best-of-n accuracy and pass@1.The cited study reported that small models could approach 100% pass@1 with sufficient scaling.Source: §5.5 · p. 22
  • Tree search and sequential revisions both scaled with computation; larger models helped complex tasks more, while more sampled tokens sufficed for simpler tasks.Outcome-reward BoN plateaued as samples increased, whereas PRM-based BoN avoided that issue.Source: §5.5 · p. 22
  • Scaling BoN can degrade performance when a reward model trained on original-policy data fails to generalize to the shifted policy distribution.The cited work notes that MCTS may also face inverse-scaling challenges.Source: §5.5 · p. 22

5.6 Challenges of Search for Reproducing o1

The search discussion identifies trade-offs in scaling inference: large searches can trigger inverse scaling, simple tasks can be overthought, and tree search competes with sequential revision under fixed compute. It also highlights efficiency bottlenecks in LLM generation and some tree-search algorithms.

How to overcome Inverse Scaling

  • Reducing test-time search may address inverse scaling, but limits search scale; improving reward-model generalization to unseen states is an alternative.The paper points to increasing model size and training data as a possible route to better generalization.Source: §5.6 · p. 22

How to avoid over-thinking on simple tasks?

  • For simple tasks, elaborate reasoning can waste computation and introduce errors; a chain-of-thought length penalty is proposed to discourage unnecessary search.The reshaped reward is intended to balance shorter reasoning with solving the task effectively.Source: §5.6 · p. 22

How to trade off tree search and sequential revisions?

  • With fixed compute, the optimal allocation between tree search and sequential revision remains unclear, although combining both is reported to improve performance.The paper suggests empirical scaling laws could guide resource allocation.Source: §5.6 · p. 22

How to improve efficiency of Search?

  • LLM generation is constrained by memory read-write speeds, and MCTS lacks inherent parallelism; proposed remedies include KV-cache sharing or compression and speculative sampling.Figure 8 distinguishes policy-gradient use of all searched solutions from behavior cloning on highest-reward solutions.Source: §5.6 · p. 22, Figure 8 · p. 23

6 Learning

The section frames reinforcement learning as learning from search-generated data, contrasting policy-gradient methods with behavior cloning and considering their trade-offs. It also identifies open questions in scaling and training efficiency, question generation, and off-policy learning.

6 Learning

  • Search-generated training data can support iterative search and learning: search explores better solutions than random sampling, and each learned policy informs the next search.The paper hypothesizes that o1 may use this cycle; AlphaGo Zero is given as an example of learning from MCTS trajectories.Source: §6 · p. 23

6.1.1 Policy Gradient

  • PPO training typically requires four models for policy, search policy, reward, and value, while GRPO and Remax are described as ways to simplify or reduce this cost.The section also notes that PPO implementation details can materially affect performance.Source: §6.1.1 · p. 24

6.1.2 Behavior Cloning

  • Behavior cloning trains on the highest-reward searched state-action pairs, while policy-gradient methods can use all searched pairs, including negative solutions.Search-derived expert data may improve as search computation scales, though it may not be high quality.Source: §6.1.2 · p. 25, §6.1.3 · p. 26

6.1.3 Speculation about the learning of o1

  • On GSM8K and MATH, behavior cloning (expert iteration) consistently outperformed policy gradient in the cited comparison, but more empirical comparison is needed.The paper speculates that behavior cloning could warm-start learning before PPO or DPO, which use negative solutions more fully.Source: §6.1.3 · p. 26

6.2 Scaling Law of Reinforcement Learning

  • OpenAI’s blog is reported to show a log-linear relationship between reasoning performance and train-time compute, while broader RL scaling laws for LLMs remain little studied.Prior RL scaling work cited here focused on traditional tasks, and small-scale LLM studies had not established predictive scaling laws.Source: §6.2 · pp. 26–27

6.3 Challenges of Learning for Reproducing o1

  • Train-time search is identified as a major efficiency bottleneck; reusing data from earlier search iterations may reduce search scale but can introduce off-policy issues.The section also flags policy-conditioned question generation as challenging because generated questions may be unsuitable or unsolvable.Source: §6.3 · p. 27
  • Search-generated data can be off-policy because it comes from a better policy; behavior cloning before policy-gradient training is proposed to narrow the policy gap.This per-iteration sequence differs from the separate warm-up-then-PPO/DPO speculation.Source: §6.3 · pp. 27–28

7 Open-source o1 Project

The paper treats open-source o1 projects as components or instances of its framework and compares their choices across policy initialization, reward design, search, and learning. The reviewed projects span prompt-based reasoning, search-generated training, reinforcement learning, and distillation.

7 Open-source o1 Project

  • Open-source implementations are presented as components or special cases of the paper’s framework, organized by initialization, reward design, search, and learning.The paper excludes several industry models because their techniques were not open-sourced.Source: §7 · p. 28

Thinking Claude

  • g1 and Thinking Claude prompt self-reflection and fine-grained reasoning actions, but their prompts were not validated on reasoning benchmarks.g1 proposes multiple solutions; Thinking Claude adds actions such as problem analysis and progress tracking.Source: §7 · p. 28, Thinking Claude · p. 28

Open-o1

  • Open-o1 provides long-CoT supervised fine-tuning data of unclear provenance; its reported training improved reasoning-benchmark performance for Llama-3-8B and Qwen-7B.The paper says the data source is unclear and speculates it may come from human experts or a stronger model.Source: Open-o1 · p. 28

o1 Journey

  • The o1 Journey Part 1 uses beam-search tree data refined by GPT-4 for supervised fine-tuning, while Part 2 distills o1-mini’s hidden reasoning traces.Part 1 reports o1-mini PRM outperforming Math-Shepherd; Part 2 reports Qwen-72B outperforming o1-preview on AIME, a comparison the paper cautions does not establish student-over-teacher distillation.Source: o1 Journey · p. 29

Open-Reasoner

  • Open-Reasoner uses MCTS only at test time and trains from current-policy samples, alongside a reward model similar to Math-Shepherd.Source: Open-Reasoner · p. 29

Slow Thinking with LLMs

  • Slow Thinking with LLMs Part 1 combines reinforcement learning and test-time MCTS using DPO; Part 2 combines distillation with DPO or SFT on reject-sampled data.Part 2 reports further improvement from reinforcement learning after distillation.Source: Slow Thinking with LLMs · p. 29

Marco-o1

  • Marco-o1 combines Open-o1 data with model-generated MCTS data for SFT and reports that stepwise self-reflection enhances search effectiveness.Source: Marco-o1 · p. 29

o1-coder

  • o1-coder generates test cases for outcome rewards, uses MCTS solutions for SFT, and updates a process reward model as the policy improves.Source: o1-coder · p. 29

8 Future Directions

The future-directions discussion focuses on adapting o1 to general domains and modalities, extending it to real-world tasks, and enabling learning and search with world models. It identifies reward availability, long multimodal reasoning traces, and environment interaction as central considerations.

How to adapt o1 to general domains?

  • General-domain adaptation depends on general reward models: reasoning tasks may use outcome rewards and shaped process rewards, while other tasks may require feedback or expert-derived rewards.The paper names Bradley-Terry preference modeling and inverse reinforcement learning as possible approaches.Source: §8 · pp. 29–30

How to introduce multiple modality to o1?

  • Multimodal reasoning must maintain fine-grained alignment between long chains of thought and other modalities; including images in CoT can improve these connections but increase inference latency.Continuous representations are proposed as a potential alternative to textual and modality-specific CoT content.Source: §8 · p. 30

How to learn and search with a world model?

  • For real-environment tasks, a world model can support more efficient training interaction and test-time planning before real actions are executed.The paper states that without a world model, search or planning is impossible in a non-time-reversible real environment.Source: §8 · p. 30

9 Conclusion

The paper presents an RL-based roadmap to reproducing o1 and surveys its key components. It relates existing open-source reproduction projects to the roadmap and calls for further research on reproduction challenges.

9 Conclusion

  • The paper presents a roadmap for reproducing o1 from the perspective of reinforcement learning.It emphasizes policy initialization, reward design, search, and learning.Source: §9 · p. 30
  • The paper surveys the roadmap's key components: policy initialization, reward design, search, and learning.Source: §9 · p. 30
  • Existing open-source projects attempting to reproduce o1 are variations of the roadmap.Source: §9 · p. 30
  • The authors hope the roadmap inspires further research on challenges in reproducing o1.Source: §9 · p. 30

Related papers

Loading 2412.14135v1…