PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought

Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, Louis Castricato, Jan-Philipp Franken, Nick Haber, Chelsea Finn

arXiv:2501.04682v1cs.AIcs.CL

TL;DR

Complex reasoning may require latent exploration, verification, and search that ordinary CoT does not explicitly represent. The paper proposes Meta-CoT, develops search-based and supervised routes to train it, and reports evidence consistent with internalized search in advanced models. It concludes that the framework and training pipeline provide a promising roadmap, while validation and broader scaling studies remain open.

  • Problem

    Complex reasoning often involves latent exploration and verification, while available reasoning traces may not represent that underlying process.

  • Method

    Meta-CoT explicitly models latent reasoning through search, process supervision, synthetic data generation, linearized search traces, and reinforcement-learning post-training.

  • Results

    Experiments and analyses provide evidence consistent with internalized search, including improved performance with additional training data and model size and a widening advantage for search-augmented models as maze complexity increases.

  • Takeaways & Limitations

    Meta-CoT offers a theoretical and practical roadmap for developing more robust and generalizable reasoning in LLMs.

  • Takeaways & Limitations

    Current value-function training is fundamentally limited to problems with verifiable solutions, excluding proof problems and scientific derivations without suitable verification.

Abstract

from arXiv · show

We propose a novel framework, Meta Chain-of-Thought (Meta-CoT), which extends traditional Chain-of-Thought (CoT) by explicitly modeling the underlying reasoning required to arrive at a particular CoT. We present empirical evidence from state-of-the-art models exhibiting behaviors consistent with in-context search, and explore methods for producing Meta-CoT via process supervision, synthetic data generation, and search algorithms. Finally, we outline a concrete pipeline for training a model to produce Meta-CoTs, incorporating instruction tuning with linearized search traces and reinforcement learning post-training. Finally, we discuss open research questions, including scaling laws, verifier roles, and the potential for discovering novel reasoning algorithms. This work provides a theoretical and practical roadmap to enable Meta-CoT in LLMs, paving the way for more powerful and human-like reasoning in artificial intelligence.

1. Introduction

The paper argues that next-token prediction can encode implicit reasoning, yet complex mathematical tasks expose limits of ordinary Chain-of-Thought. Meta-CoT addresses this gap by explicitly modeling latent search and reasoning processes.

  • Next-token prediction trains language models to approximate data distributions and perform implicit reasoning in their activations.
  • Complexity in the underlying data-generating process can challenge models even when the task is deterministic.The paper uses mathematical reasoning to study this relationship.
  • GPT-4o and Claude fail on a mathematically simple expression, whereas step-by-step prompting substantially improves performance.The expression is canonically equal to 1, but the cited models do not answer it correctly even once without explicit reasoning.
  • Meta-CoT extends CoT by explicitly modeling the underlying reasoning required to produce a particular chain of thought.The framework treats latent exploration, verification, and iterative reasoning as part of the solution process.
  • The proposed roadmap combines theoretical foundations, empirical analysis of advanced models, process supervision, synthetic search data, and reinforcement-learning post-training.The paper also identifies scaling laws, verifier roles, and novel reasoning algorithms as open questions.

2. Meta Chain-Of-Thought

Meta-CoT represents complex reasoning as a latent, non-linear process of exploration that can be formalized through search and internalized by autoregressive models. Evidence from difficult mathematics benchmarks and model behavior suggests that explicit or internal search becomes increasingly valuable as task complexity rises.

  • 2. Meta Chain-Of-Thought: Traditional CoT may fail on advanced problems because complex solution generation is non-linear, iterative, and latent rather than purely left-to-right.The paper contrasts this with simpler tasks whose textbook solutions more closely reflect their data-generating process.
  • 2. Meta Chain-Of-Thought: The windmill problem illustrates how a short final proof can conceal extensive exploration because its highly non-linear solution structure makes standard approaches difficult.The problem was among the competition’s most difficult despite a solution fitting within a few sentences.
  • 2. Meta Chain-Of-Thought: Figure 1 compares frontier-model performance by HARP difficulty and topic with generated-token counts grouped by difficulty and human-solution lengths.Its top and bottom panels respectively describe performance and token behavior.
  • 2. Meta Chain-Of-Thought: Meta-CoT models a latent process q → z1 → . . . → zK that generates the answer and CoT jointly.The latent variables represent omitted thoughts underlying the visible solution steps.
  • 2. Meta Chain-Of-Thought: On harder HARP problems, o1 generates substantially more tokens and widens its performance gap over classical reasoning models.The paper hypothesizes that these longer traces better approximate the extensive Meta-CoT process needed for challenging problems.
  • 2. Meta Chain-Of-Thought: The paper notes that constant-depth models may internalize part of Meta-CoT, as reflected by graded CoT lengths across difficulty Levels 2–6.This qualifies the distinction between internalized reasoning and explicit search.

3. Towards Deliberate Reasoning With Language Models - Search

The section examines inference-time search as a way to improve reasoning efficiency and performance, while asking whether search is a learnable capability or a fundamental capability shift. Evidence spans verifier-guided sampling, tree search, MCTS, and preliminary LLM scaling studies.

  • Motivation: Inference-time search is motivated by the unresolved question of what the true data-generating process for advanced reasoning looks like.The section frames search as a response to limitations in training data and reasoning processes for complex tasks.
  • Inference-Time Search: Pass@k and majority voting expose a persistent verifier-generator gap even as supervised fine-tuning data increases.For the Llama 3.1 8B study, pass@64 approaches 85%, while majority voting improves continuously with more training and samples.
  • Verification: Verifier models improve in best-of-N settings as N increases, and explicitly trained verifiers outperform self-consistency or majority voting.The verifier formulation scores candidate solutions generated by a fixed policy and ranks them by evaluation quality.
  • General Search: Tree search formulates reasoning as an MDP in which states contain the prompt and generated steps, actions add reasoning steps, and rewards assess solutions.This structure supports truncating low-value branches, backtracking to promising nodes, and avoiding repeated sampling of identical steps.
  • General Search: Tree-structured search can improve inference efficiency, with nearly 4 times greater efficiency than parallel sampling on the Game of 24.The cited work also describes tree search as scalable to realistic agentic applications.
  • Learnability and Scaling: Evidence from classical RLHF and MCTS suggests that search-related gains can be learned and can scale with both training-time and inference-time compute.However, LLM evidence remains limited, and existing studies have not systematically ablated model size, data scaling, or inference-time search scaling.

4. Towards Meta-CoT Reasoning

The section proposes training autoregressive models to internalize search-based Meta-CoT, extending CoT with explicit exploration and verification. Evidence from maze tasks and related studies suggests search benefits grow with problem complexity, while practical training remains constrained by data and post-training choices.

  • Motivation and implications: The approach aims to optimize over reasoning algorithms rather than specific outputs, potentially enabling novel problem-solving modes through reinforcement learning.The text presents this as a potential consequence if models learn to implement search algorithms in context.
  • Training Meta-CoT: Meta-CoT training linearizes search traces so autoregressive models learn to execute search sequentially in context.The approach combines a base policy, a search procedure, verification, synthetic traces, and supervised training.
  • Training Meta-CoT: A* traces explicitly represent node states, actions, costs, heuristic values, and queue state for next-token training.The “Trace” corresponds to Meta-CoT Z, while the “Plan” corresponds to the CoT output S.
  • Empirical evidence: Search-augmented models improve consistently with additional training data and model size, while their advantage widens as maze complexity increases.At smaller maze sizes, direct plan generation can perform comparably to smaller search-augmented models; larger mazes produce a wider gap.
  • Empirical evidence: These results are consistent with the view that models can internalize reasoning for low-complexity problems but struggle to reproduce explicit search as complexity grows.The discussion contrasts linear plan length with potentially exponential search cost in the branching factor, while noting that inference scaling laws were not published.
  • Empirical evidence: Autoregressive generation shows better scaling than independent parallel sampling, and observed gains suggest some in-context exploration.The supplied result passage reports nearly 6–7% gains from zero-shot to saturation across episodes.
  • Limitations: A reported best run improved 2% over the initialized LLaMA 3.1 8B Instruct model, but the authors attribute results to post-training mismatch and limited MATH data.Regular supervised fine-tuning on the RL-post-trained model worsened performance in their experiments.

4.3. Synthetic Meta-CoT Via Search

This section constructs synthetic Meta-CoT by applying search algorithms to difficult math problems and recording verified search traces. It compares MCTS with a more efficient best-first strategy, highlighting the cost and backtracking trade-offs of search-based data generation.

  • Search-based data generation: Synthetic Meta-CoT data are generated by running MCTS or A*-style search over partial solution trajectories until a ground-truth verifier finds a correct solution.Both search methods use Monte-Carlo rollouts to estimate the value of partial solutions.
  • Experimental setup: The benchmark is an OpenAI math problem where Gemini 1.5 Pro achieved Pass@128 of 6.25% (8/128 correct).The passage describes this as non-zero performance among frontier models without advanced reasoning at the time of the experiments.
  • Monte-Carlo Tree Search: MCTS search traces record every action and value estimate, but the initial tree contained excessive backtracks and repetitions, including from high-value states.The authors associate these effects with the exploration bonus in MCTS.
  • Monte-Carlo Tree Search: Pure Monte-Carlo rollouts made one MCTS tree cost up to 20 million inference tokens, approximately $100, and take up to half an hour.The authors therefore also evaluate a more efficient best-first exploration strategy.
  • A* search: The best-first method maintains a max-priority frontier, expands candidate next steps, evaluates them, and continues until a ground-truth verifier identifies a correct solution.Search is limited by a maximum depth, and the resulting tree shows more consistent reasoning flow with less backtracking around key steps.

4.4. Do Advanced Reasoning Systems Implement In-Context Search?

Advanced reasoning traces display search-like behaviors, including backtracking, repetition, and self-evaluation, but these observations do not establish that models execute tree search at test time.

  • Advanced-model traces show inconsistent logical flow, semantic backtracking, and repetition across reasoning steps.
  • A* produces a more best-first trace with fewer backtracks concentrated around key steps than the MCTS trace.
  • o1’s qualitative behavior resembles synthetic MCTS-like traces, although the authors do not claim it implements tree search during inference.
  • DeepSeek R1 performs substantial self-evaluation, with smoother reasoning and less abrupt backtracking than o1.
  • Gemini 2.0 Flash Thinking Mode appears smoother, backtracks less often, and can regenerate a solution from the final state to the initial state.

5. Process Supervision

Process supervision uses learned value functions to evaluate intermediate reasoning states and guide search, while experiments show improving PRM quality with more data but important limits on verifiability and efficiency.

  • Process Reward Models score intermediate reasoning states, allowing search to backtrack toward promising states when paths become suboptimal.
  • Outcome-based verification with MCTS requires ground-truth answers and can consume up to 20 million inference tokens per training example, costing up to hundreds of dollars.
  • Parameterized PRMs take a question and partial solution as input and output a scalar value in [0, 1].
  • Predicted-value error decreases as PRM training data increases, while small datasets converge early at around 30% of an epoch.
  • Monte Carlo-trained value functions are limited to problems with verifiable solutions, excluding proof problems and scientific derivations from this supervision approach.

6. Meta Reinforcement Learning - Learning How To Think

The section frames reasoning as meta-reinforcement learning, where models adapt to unknown task rewards through in-context exploration, and examines whether RL improves search efficiency or discovers new reasoning algorithms.

  • Meta-RL formulation: Meta-RL treats reasoning as adaptation to an initially unknown reward function, turning the deterministic search problem into a partially observable task.The model infers accepted and rejected solutions from experience gathered under a new prompt.
  • Learning from feedback: SFT alone does not induce in-context exploration or improve performance, whereas RL can train models to use feedback across multiple solution episodes.RLEF models explore through compiler feedback before producing an evaluation solution, while the cited SFT analysis reports no exploration benefit.
  • Learning from feedback: RL-trained models can refine solutions over multiple turns even with unreliable feedback, although ground-truth feedback retains an advantage.Performance continues improving with additional test-time revisions under random feedback, but a gap remains relative to ground-truth feedback.
  • Efficiency gains: RL post-training improves exploration performance and search efficiency, but often does not exceed the success rate of symbolic or ground-truth approaches.Countdown success rates improve with smaller search budgets, while the RL-tuned SoS model remains below the symbolic approach and STaR reaches up to 4% versus about 1% for base SFT.
  • Efficiency versus super-intelligence: Current evidence supports improved search efficiency more strongly than the discovery of novel reasoning algorithms or previously unsolved problem classes.The paper reports clear efficiency benefits but only weak evidence for emergent super-reasoning beyond increased search budgets.
  • Inducing meta-reasoning: Explicit meta-cognitive prompting increases regret expression, but self-verification and backtracking do not consistently improve accuracy and may correlate with incorrect answers.Llama 3.1 70B reaches 25.67% regret expression under Think & Verify, while GPT-4o and Claude 3.5 Sonnet remain at 1–4%.

7. Putting It All Together - A Pipeline for System 2 Reasoning

The proposed training pipeline combines instruction tuning on synthetic search traces with reinforcement learning to internalize Meta-CoT reasoning. It also considers verifier-free self-training, while emphasizing stability, regularization, and unresolved training-design questions.

  • Training pipeline: The pipeline follows modern post-training by combining instruction tuning and reinforcement learning.Instruction tuning uses synthetic in-context search data, followed by RL training.
  • Training pipeline: Synthetic search traces are proposed because advanced models rarely exhibit meta-reasoning behaviors such as regret or backtracking through prompting alone.
  • RL post-training: The RL formulation uses verifiable solution rewards and a reference-policy constraint to stabilize and preserve interpretability over long horizons.The authors identify robust credit assignment and long-horizon stability as significant challenges.
  • Latent reasoning objectives: Alternative objectives amortize latent reasoning and solution generation within one autoregressive model, including a variational formulation requiring RL because the model samples discrete tokens.The latent reasoner and decoder can be combined into a single model under the proposed objective.
  • Verifier-free training: Verifier-free RL removes the need to verify final solutions, but bootstrapping high-quality latent reasoning still requires verifiable outcomes for synthetic data.
  • Training challenges: The verifier and reward pipeline requires explicit regularization because sampling-related biases can make reward models favor longer answers.
  • Inference control: Conditioning on search parameters can trade inference compute against accuracy and reproduce qualitatively different reasoning behaviors at inference time.

8. Going Forward

The paper identifies data, infrastructure, verification, and algorithmic gaps that constrain open research on reasoning models. It proposes Big MATH and highlights unresolved questions about search scaling, verifiers, faithfulness, and external-tool reasoning.

  • Open-research bottlenecks: Open reasoning research is bottlenecked by limited data and compute, weak open-source infrastructure, and insufficient resources for algorithmic exploration.
  • Data resources: Big MATH aims to aggregate over 1,000,000 high-quality, diverse, verifiable mathematics problems to address shortages in challenging reasoning data.The project combines existing datasets with post-processing and additional data from novel sources.
  • Verification constraints: Automated verification is constrained because many tasks lack unique canonical answers, resist deterministic grading, or risk measuring factual retrieval instead of reasoning.
  • Data criteria: The proposed data criteria require uniquely verifiable solutions, open-ended formulations, and closed-form answers suitable for automated evaluation.
  • Data quality: Existing datasets contain substantial quality problems: NuminaMath has roughly 860,000 entries, including more than 42,500 duplicates and varied boxed-solution formats.89.7% contain exactly one boxed solution, while 2.6% contain none and 7.7% contain multiple boxed solutions.
  • Faithfulness: Faithful process supervision remains unresolved because models can produce inconsistent or unfaithful CoTs despite reaching correct final answers.The paper identifies rewarding full CoTs and open-ended proofs as an open question.
  • Verifier gaps: Pre-trained process reward models lag behind Monte Carlo search in efficiency, while verifier-driven best-of-N performance remains below oracle pass@N.
  • Open questions: Future work must evaluate search scaling on realistic reasoning tasks, clarify joint policy-verifier scaling, and compare internal reasoning with external tools.The paper notes that sequential in-context search can be slow, whereas classical search methods such as MCTS can be parallelized.

9. Conclusion

The paper presents Meta-CoT as a framework that augments Chain-of-Thought with search, verification, and iterative refinement. It reports supporting evidence from model behaviors and proposes a training roadmap, while leaving key validation and scaling questions open.

  • Conclusion: Meta-CoT models advanced problem solving by incorporating search, verification, and iterative refinement beyond traditional Chain-of-Thought.
  • Conclusion: Observed state-of-the-art model behaviors and experiments on in-context exploration and backtracking support the hypothesis that internal search processes matter for complex-task performance.
  • Conclusion: The proposed training pipeline offers a concrete approach for developing models with enhanced Meta-CoT capabilities, but its efficacy remains to be validated.
  • Future work: Open questions concern reasoning and search scaling laws, process supervision, verification, and the interaction between instruction tuning and reinforcement learning.The Big MATH dataset is intended to support further research on reasoning models.

A. Prompting

The prompting study evaluates five increasingly sophisticated instruction sets for reasoning-like behaviors and their relationship to mathematical performance. Complex prompting strategies consume substantially more input tokens because of demonstrations and explicit capability requirements.

  • Prompting evaluation: The evaluation compares five increasingly sophisticated instruction sets using token patterns, reasoning-like behaviors, and math problem-solving performance.
  • Prompting cost: Complex instructions such as Think (3-shot) use substantially more input tokens than simpler prompting strategies.The extra tokens primarily come from in-context demonstrations and explicit thinking, reflection, and verification requirements.

B. Regret Analysis

Table 5 compares regret expression across models and prompting strategies, focusing on self-correction and error acknowledgment.

  • Regret expression varies across model scales and prompting strategies.The table reports differences in self-correction and error acknowledgment behaviors.

C. Different Instruction Tuning Objectives

The proposed instruction-tuning stage considers multiple objectives for training models to produce reasoning traces. These choices include procedural cloning, Meta-CoT-only optimization, joint solution supervision, and masking decisions for incorrect branches.

  • The section frames these alternatives as potential fine-tuning objectives for the reasoning pipeline.
  • The pipeline considers standard procedural cloning through traditional supervised fine-tuning.
  • An alternative objective optimizes only over Meta-CoT tokens rather than directly training solution generation.This requires a separate step to summarize the search process into a final solution.
  • Joint sequences containing the solution may provide additional supervision for maintaining internal state.
  • Training may mask sub-optimal or incorrect branches and retain only branches on the correct path to the final answer.Prior work reported no performance degradation without masking when the data distribution remained reasonable, while another approach masked unsafe-generation tokens.

D. MCTS Details

The MCTS procedure alternates selection, expansion, and backup to search over logical solution steps. It uses UCT-based selection, policy sampling for expansion, value evaluation, and ancestor-statistic updates.

  • MCTS proceeds through selection, backup, and expansion.
  • Selection: Selection follows the highest UCT score from the root until reaching a leaf, representing the current partial solution as S_t.
  • Selection: UCT combines a value function, visit counts, and an exploration constant to choose the next logical step.The procedure uses UCT rather than PUCT because logical-step likelihoods can be highly skewed.
  • Expansion: Expansion samples b actions from policy π_θ for a nonterminal leaf, adds them as children, and initializes their values with a value function.This value evaluation replaces the simulation step commonly used in game settings.
  • Backup: Backup propagates the expanded-node statistics along the path to the root while incrementing ancestor visit counts.

E. Chains-Of-Thought

The section presents synthetic chain-of-thought traces for jury-seating planning problems and compares reasoning through alternative counting strategies. The traces include model-generated solutions using A* and MCTS, alongside other model traces and a reported total of 1024 arrangements.

  • Chains-Of-Thought: Complete Gemini-1.5 traces use A* and MCTS on planning problems, alongside parallel traces from DeepSeek-R1, DeepSeek-O1, and Gemini-2.The section also includes a tool-augmented dynamic-programming example from an SFT-tuned Llama3.1-8B model.
  • Problem setup: The jury problem fixes Nikolai Nikolaevich in the next clockwise seat and lets later members sit in designated or next available seats.
  • Counting strategies: Several traces count sequential choices, with options depending on whether the preceding jury member moved.These traces distinguish cases where later members have two options from cases where only one option remains.
  • Counting strategies: The traces explore corrections for overcounting through decision points, cycle arrangements, last-person constraints, and rotational symmetry.
  • Circular arrangement: Alternative traces simplify the circular arrangement by fixing Nikolai's position and arranging the remaining 11 people relative to him.One passage states that this gives 11! arrangements before accounting for movement patterns.
  • Reported result: 1024 is reported as the total number of different jury seating arrangements.Other traces explicitly mark several intermediate calculations as incorrect before presenting this result.

Trace - Reasoning with External Tools

The trace repeatedly revises its approach to count jury seating arrangements, moving from informal choice counting to corrected initialization and iterative or dynamic-programming formulations. It concludes that the stated rules yield 1024 arrangements.

  • Computational formulation: A dynamic-programming formulation represents states using available seats and Nikolai’s current seat, with recursive or iterative implementations proposed.
  • Approach revisions: An initial dynamic-programming approach is identified as flawed because it overlooks the actual sequence of members and mishandles the initial state.
  • Approach revisions: The revised reasoning counts directly from Nikolai’s initial placement and tracks subsequent designated-seat or next-available-seat choices.
  • Result: 1024 arrangements result for 12 jury members under the specified seating rules.
  • Problem setup: The problem fixes Nikolai Nikolaevich in the next clockwise seat, after which each member sits in a designated or next available seat.

O1 official math CoT

The trace solves a polynomial interpolation problem by converting the reciprocal condition into a polynomial root problem and factoring out the known integer roots. Evenness then fixes the remaining quadratic and gives the additional solutions ±1/n!.

  • Problem: The problem asks for all other real x when a monic real polynomial of degree 2n satisfies p(1/k)=k^2 for 1≤|k|≤n, with n even.
  • Factorization: The associated polynomial has degree 2n+2 and factors into the known terms (x^2−1)…(x^2−n^2) multiplied by a monic quadratic.
  • Coefficient determination: Evenness forces the quadratic’s linear coefficient to vanish, while evaluation at zero determines its constant term as -1/(n!)^2.
  • Conclusion: The additional real solutions are x=±1/n!.
  • Construction: Defining q(x)=p(1/x)-x^2 converts the given conditions into roots at k=±1,±2,…,±n for an associated polynomial.
Loading 2501.04682v1…