当前位置：首页 > article >正文

一文总览OpenAI o1相关的技术：从CoT、Quiet-STaR、Self-Correct、Self-play RL、MCTS等到类o1模型rStar-Math

article 2025/2/4 0:59:11

前言

注意，本文自10.12日起，正在每周2次更新的过程中，包括已写的部分也在不断修改(以增加更多技术细节、更加通俗易懂)
预计11月下旬完成第一版，25年1月底修订到第二版——具体修订记录详见本文文末..

可能是去年写或讲的关于ChatGPT原理的文章和课程，影响力太大了

导致自从OpenAI o1出来后，每过两天，就有朋友问，“校长 o1啥时候出解读或课程”，实在是各个大模型项目上的事情太多，加之近期一直在抠机器人(比如本博客内连发了五篇机器人相关的文章，再不刻意强插一下比如o1，真的很难停下来)

但，今天又有朋友来问，故，准备并行开写o1了

一开始，我主要是看的这几个资料

OpenAI o1的技术blog
张俊林老师的Reverse-o1:OpenAI o1原理逆向工程图解
GitHub上的o1论文列表，以及我自己挖掘到的一系列paper，以下是逐一出现在本文中的其中几篇
1) 22年1月，Google，思维链的开山之作
Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
2) 23年4月，Google deepmind等机构，代码层面上让模型学会自我调试
《Teaching Large Language Models to Self-Debug》
3) 24年2月，斯坦福、Google等，如何通过CoT让模型学会解决复杂的数学问题
《Chain of Thought Empowers Transformers to Solve Inherently Serial Problems》，

4) 23年5月，让模型学会拆解问题
《Tree of Thoughts (ToT): Deliberate Problem Solving with Large Language Models》
5) 23年5月，OpenAI，《Let's Verify Step by Step》
6) 24年5月，通过结果监督的手段达到过程监督的效果
《Training Large Language Models for Reasoning through Reverse Curriculum Reinforcement Learning》

7) 22年3月，斯坦福、Google，可以迭代利用少量的推理示例和一个没有推理过程的大型数据集，以逐步增强执行更复杂推理的能力
《STaR: Self-Taught Reasoner Bootstrapping Reasoning With Reasoning》
8) 24年3月，斯坦福，语言模型可以教会自己在说话前先思考，即先想好再回答
《Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking》

9) 24年7月，来自Carnegie Mellon University、UC Berkeley、3MultiOn的研究者们提出了一种名为递归自省的方法——RISE
《Recursive introspection: Teaching language model agents how to self-improve》
10) 24年9月下旬，Google开发了一种不需要这些要求的有效自我纠正方法，称为通过强化学习进行自我纠正(Self-Correction via Reinforcement Learning，简称SCoRe)
《Training Language Models to Self-Correct via Reinforcement Learning》

11) 24年8月份，来自UC Berkeley、Google DeepMind的研究者证明在加强模型的推理能力方面，延长思考时间比单纯增加模型参数更有效
《Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters》

12) 24年9月初，《Planning In Natural Language Improves LLM Search For Code Generation》
13) 24年5月，《Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning》
公号或某乎上的一些o1文章
上交团队的一个o1复现

但随着本文越写越深，挖出来的相关资料也越来越多，我会竭尽所能，确保本文具备以下两大特征

尽可能在本文中把o1的所有重要细节都一次性说清楚
如果实在有些细节因为篇幅而没法面面俱到的，我也会尽可能提供相关的论文供相关的读者进一步深入
在行文过程中，对每一个结论都不做随意的主观猜测
由于OpenAI实在是不够开放，一个技术报告完全是啥都没说，所以很容易引发各种猜测、推测，虽然我没法完全百分百知晓o1的所有技术细节，但本文会尽可能做到一切结论都有科学而严谨的权威论文做佐证

且在实在必须做一定的推测时，也可能确保是合理、有信服力的猜测，而非主观想象

至于，为何要写OpenAI o1呢，简言之，就是能力强大

其在物理、化学和生物学的具有挑战性的基准任务上的表现与博士生相似
且它在数学和编码方面表现出色。在国际数学奥林匹克 (IMO) 资格考试中，GPT-4o 仅正确解决了 13% 的问题，而推理模型得分为 83%，并在 Codeforces 比赛中达到了第 89 个百分位

第一部分如何让模型学会思考并分解问题

1.1 如何让模型学会自我调试、解决复杂数学问题

说到o1的原理，根据OpenAI o1的技术报告显示

在于大规模强化学习算法教会o1如何在高质量高效数据(data-efficient)的训练过程中利用其CoT(chain of thought)的能力进行有效思考。且他们发现，随着强化学习的更多赋能(训练时间计算)和思考时间的增加（测试时间计算），o1 的性能会持续提高
进一步，类似于人类在回答困难问题之前可能会思考很长时间，o1 在尝试解决问题时使用了“思维链”（chain of thought）策略
Similar to how a human may think for a long time before responding to a difficult question, o1 uses a chain of thought when attempting to solve a problem.
相当于在面对一个不是很轻松的问题时，模型会像人类一样，尽可能思考全面，以想出一个万全之策
那如何思考出来万全之策呢，OpenAI的策略是通过强化学习，让o1 学会优化其思维链并改进所使用的策略
Through reinforcement learning, o1 learns to hone its chain of thought and refine the strategies it uses.

接下来关键点来了
1) 它学会了识别并纠正自己的错误，即It learns to recognize and correct its mistakes.
2) 将复杂的步骤分解成更简单的步骤，即It learns to break down tricky steps into simpler ones.
3) 并在当前方法无效时尝试不同的解决方式，即It learns to try a different approach when the current one isn’t working.

每一点都是职场精英人士的优秀特征啊，总之，整个过程显著提升了模型的推理能力

至于什么是CoT，特援引此文《ChatGPT技术原理解析：从RL之PPO算法、RLHF到GPT4、instructGPT》中“2.4.3 基于思维链(Chain-of-thought)技术下的prompt，是后来OpenAI o1的关键技术之一的”这段内容

为让大语言模型进一步具备解决数学推理问题的能力，22年1月，谷歌大脑团队的Jason Wei、Xuezhi Wang等人提出了最新的Prompting机制——Chain of Thought(简称CoT)

简言之就是给模型推理步骤的prompt，让其学习人类如何一步步思考/推理，从而让模型具备基本的推理能力，最终可以求解一些简单甚至相对复杂的数学推理能力
其对应的论文为，通过此篇论文《Chain-of-Thought Prompting Elicits Reasoning in Large Language Models》
该论文全部作者包括Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, Denny Zhou
PS，上面的最后一位作者Denny zhou是Google deepmind推理团队的首席科学家

以下是一个示例(下图左侧为standard prompting，下图右侧为基于Cot的prompt，高亮部分为chain-of-thought)，模型在引入基于Cot技术的prompt的引导下，一步一步算出了正确答案，有没有一种眼前一亮的感觉？相当于模型具备了逻辑推理能力

1.1.1 代码层面上让模型学会自我调试：Teaching LLM to Self-Debug by23年4月

23年4月份，来自Google deepmind、UC Berkeley的研究者们Xinyun Chen, Maxwell Lin, Nathanael Schärli, Denny Zhou(此人是Founder and lead of the Reasoning Team in Google DeepMind，这是其个人主页：Denny Zhou's Home Page )，发布了此篇论文：Teaching Large Language Models to Self-Debug

在这项工作中，他们提出了自我调试方法，教大模型通过少样本提示来调试其预测的代码。且无需额外的模型训练，自我调试指导模型执行代码，然后根据代码及其执行结果生成反馈信息。与之前利用人为反馈进行代码修复的工作不同(那些工作中的反馈信息解释了代码错误及其修复方法)
具体如下图所示
在每个调试步骤中，模型首先生成新代码，然后执行代码并解释代码。代码解释与执行结果共同构成反馈信息，模型根据此信息推断代码的正确性，然后将此信息添加到反馈中。然后将反馈信息发送回模型以执行更多调试步骤。当单元测试不可用时，反馈可以仅基于代码解释
最终，在没有为任务指定单元测试的文本到SQL生成中，利用代码解释进行SELF-DEBUGGING能持续提高基线2-3%，并在最困难的问题上提供9%的性能提升
在有单元测试可用的代码翻译和文本到Python生成任务中，SELF-DEBUGGING显著提高了基线准确率，最高可达12%

总之，一次自我调试包含3个步骤：生成、解释和反馈

在生成步骤中，给定问题描述，模型预测候选程序
在解释步骤中，模型被提示以语义上有用的方式处理预测结果，例如用自然语言解释预测，或为预测的代码创建一个示例输入的执行跟踪
最后，在反馈步骤中，会生成一条关于预测代码正确性的反馈信息。这可以通过询问模型本身来确定，也可以通过单元测试外部生成

当然，调试过程在反馈信息表明预测正确时终止，或者达到允许的最大调试次数时终止

接下来，再讨论下可以自动获取和生成的不同类型的自我调试反馈

简单反馈
最简单的自动反馈形式是一个仅仅指示代码正确性的句子，而不提供更多详细信息，这省略了完整自我调试过程中的解释步骤
例如，在文本到SQL的生成中，少样本提示为所有正确的SQL查询提供反馈信息“上面的SQL预测是正确的！”，而对于错误的预测则是“上面的SQL预测是错误的。请修正SQL。”
单元测试反馈（UT）
对于问题描述中包含单元测试的代码生成任务，除了利用代码执行来检查代码的正确性之外，我们还可以将执行结果纳入反馈中，这为调试提供了更丰富的信息

下图展示了一个示例单元测试反馈信息(左对齐的块是模型预测，右对齐的块包含输入的C++代码和基于代码执行的反馈信息) 直观地查看运行时错误和失败单元测试的执行结果也有助于人类程序员更有效地调试。说明了只要有单元测试可用，利用它们可以持续提升自我调试性能
代码解释反馈（Expl）
尽管最近有令人鼓舞的进展表明，大型语言模型可以生成批评以避免产生有害的模型输出，并在一些自然语言任务上提高其性能，但先前的工作尚未展示模型生成反馈在代码生成中的有效性
另一方面，大型语言模型已被证明能够以文本和代码格式描述其生成的问题解决方案
执行跟踪反馈（Trace）
除了解释代码本身，人类程序员通常还通过模拟执行过程来理解代码的语义意义。之前关于代码修复的研究表明，在执行跟踪上训练修复模型可以提高调试性能
因此，当单元测试可用时，作者会检查另一种解释反馈格式，其中LLM被指示逐行解释中间执行步骤。请注意，执行跟踪和逐行解释都来自模型生成，而不是代码执行，因此跟踪反馈不需要比纯代码解释反馈更多的信息；即，不需要访问中间执行状态

以下是一个用于文本到 SQL 生成的自我调试提示示例，其中SQL 查询、解释和反馈均由模型预测(当返回的表格有超过 2 行时，提示中仅包含前 2 行)

1.1.2 如何通过CoT让模型学会解决复杂的数学问题 by24年2月

24年2月，当时来自斯坦福大学、芝加哥丰田技术研究所、谷歌的研究者们Zhiyuan Li, Hong Liu, Denny Zhou, Tengyu Ma，发布了这篇论文《Chain of Thought Empowers Transformers to Solve Inherently Serial Problems》

在该论文中，作者展示了配备CoT的Transformer——允许Transformer在回答问题之前自回归地生成一系列中间token——可以解决固有需要串行计算的复杂问题（假设复杂性理论中的一些知名猜想）
We then show that transformers equipped withCoT—allowing the transformer to auto-regressively generate a sequence of intermediate tokens before answering the questions—can solve complex prob-lems that inherently require serial computations (assuming well-known conjectures in complexity theory).
直观地说，没有CoT，Transformer进行的串行计算数量受限于深度(在此工作中被视为一个固定常数），而有了T个中间步骤，可能的串行计算数量增加到T
Intuitively, without CoT, the number of serial computations conducted by the transformeris bounded by the depth (which is considered as a fixed constant for this work), whereas with T in termediate steps, the number of serial computations possible is boosted to T.

注意，随着序列长度的增加，T可以轻松增加，而深度是依赖于架构的一个固定数值
Note that T caneasily increase as the sequence length increases where the depth is a fixed number that depends onthe architecture

// 待更

1.2 如何让模型学会分解问题

1.2.1 Decomposed Prompting: A Modular Approach for Solving Complex Tasks

22年10月，Decomposed Prompting: A Modular Approach for Solving Complex Tasks
概述：提出了一种名为Decomposed Prompting的方法，通过将复杂任务分解为更简单的子任务，并将这些子任务委托给专门处理这些子任务的LLMs。该方法的模块化结构允许每个提示针对其特定的子任务进行优化，并在必要时进一步分解

// 待更

1.2.2 Tree of Thoughts (ToT): Deliberate Problem Solving with Large Language Models

23年5月，Tree of Thoughts (ToT): Deliberate Problem Solving with Large Language Models

// 待更

1.3 如何让模型学会一步一步的自我验证：结合结果监督与过程监督

1.3.1 Let's Verify Step by Step(含ORM、PRM的介绍)

首先，我们来回顾下语言生成的整个过程

在每个时间步 $t$ ，策略语言模型 $\pi_{\theta}^{R L}$ 由参数 $\theta$ 参数化的策略接收一个状态 $s_t$ ，该状态由输入prompt和到目前为止生成的文本组成

然后，策略的行动 $a_{t+1}$ 是在该状态 $s_t$ 的条件下生成下一个token，其概率为 $\pi_{\theta}\left(a_{t+1} \mid s_{t}\right)$
之后，环境返回一个奖励 $r(s_t, a_{t+1})$ ，状态以转移概率 $p(s_{t+1}|s_t, a_{t+1})$ 转移到 $s_{t+1}$
强化学习的目标是找到一个最优策略，以最大化轨迹 $\tau=\left\{s_{0}, a_{1}, \ldots, s_{T}, a_{T}\right\}$ 上的累积奖励（即回报），其中 $s_0$ 是初始状态（即提示）， $T$ 是动作的长度

策略梯度的一般形式给出如下
$\mathbb{E}_{\tau \sim \pi_{\theta}^{\mathrm{RL}}}\left[\sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}^{\mathrm{RL}}\left(a_{t} \mid s_{t-1}\right) R\left(s_{t-1}, a_{t}\right)\right]$
其中 $E_{\tau \sim \pi^{RL}_\theta}$ 表示在从策略 $\pi^{RL}_\theta$ 采样的轨迹分布下的期望

且其中回报 $R\left(s_{t-1}, a_{t}\right)=\sum_{t^{\prime}=t}^{T} \gamma^{t^{\prime}-t+1} r\left(s_{t^{\prime}-1}, a_{t^{\prime}}\right)$ 是从时间步骤 $t$ 开始的奖励的折现和，折现因子为 $\gamma \in[0,1)$
通过这个梯度，可以进行梯度上升来优化模型。如果回报是有利的，动作的选择概率会通过增加来“增强”
如果给定一个数据集 $\mathcal{D}=\left\{\left(s_{0}^{i}, \mathbf{a}^{i}\right)\right\}_{i=1}^{N}$ ，其中包含 $N$ 对输入 $s_0$ 和人类生成的输出序列 $a$ ，其中 $a= (a_1, a_2, ..., a_T)$ ，整个轨迹为 $\tau=\left\{s_{0}, a_{1}, \ldots, s_{T-1}, a_{T}\right\}$

策略梯度则变为
$\begin{array}{l} \mathbb{E}_{s_{0} \sim \mathcal{D}}\left[\mathbb{E}_{\tau \sim \pi_{\theta}^{\mathrm{RL}}\left(\cdot \mid s_{0}\right)}[ \right. \\ \left.\left.\sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}^{\mathrm{RL}}\left(a_{t} \mid s_{t-1}\right) R\left(s_{t-1}, a_{t}\right)\right]\right] \end{array}$

当然，如果你对上面的这些还不太明白，则可以看下此文《强化学习极简入门：通俗理解MDP、DP MC TC和Q学习、策略梯度、PPO》

其次，近年来，大型语言模型在执行复杂的多步推理方面有了很大提升。然而，即使是最先进的模型仍然经常会产生逻辑错误，很容易出现一步错、则步步错的情况

所以，为了训练更可靠的模型，可以

选择：结果监督的奖励模型ORMs
它仅为采样序列的最终结果提供反馈

即奖励模型只给最后一个结果分配奖励分数，而其他token的分数为0
$r_{o}\left(s_{t-1}, a_{t}\right)=\left\{\begin{array}{ll} r f_{o}\left(s_{t-1}, a_{t}\right), & t=T \\ 0, & t \neq T \end{array}\right.$
所以其可以在没有人类参与的情况下进行，针对所有待解决的问题自动得到答案
或选择：过程监督的奖励模型PRMs
它为每个中间推理步骤提供反馈，即奖励模型 $r_{mp}(·)$ 被训练用于为每个中间推理步骤分配一个奖励分数
$r_{p}\left(s_{t-1}, a_{t}\right)=\left\{\begin{array}{ll} r m_{p}\left(s_{t-1}, a_{t}\right), & t \in \mathcal{T}^{\text {Delimiter }} \\ 0, & t \notin \mathcal{T}^{\text {Delimiter }} \end{array}\right.$
如此则能够准确指出错误发生的位置
但该PRM则需要依赖于人工标注以提供过程监督，比如告诉模型每一步的正确与否，比如下图

ORM 在最后一个标记上的预测作为解决方案的整体得分，这点大家可能并不陌生了，因为instructGPT便是这么做的(详见这篇ChatGPT原理笔记)

而PRM好像很少见，有人可能会说，在这篇ChatGPT原理笔记中，在讲到DSC的实现时，不讲到了虽然奖励模型RM的输出结果reward侧重结果监督奖励，但critic输出的价值估计value则侧重衡量过程么

举个例⼦，假定在经验数据池里，有seq=[ i am learning machine learning with julyedu ]，其

KL系数，即β
kl_ctl: 0.02
旧策略下生成句子中不同词的对数概率
log_probs: [-12.0938, -20.1250, -1.3477, -1.8945, -0.9966, -0.5142, -1.4902]
SFT策略下生成句子中不同词的对数概率
ref_log_probs: [-12.1172, -20.1406, -1.3447, -2.1699, -1.2002, -0.7905, -1.6611]
KL = - kl_ctl * (log_probs - ref_log_probs)
kl_divergence_estimate: [-4.6873e-04, -3.1257e-04, 5.8591e-05, -5.5084e-03, -4.0741e-03, -5.5275e-03, -3.4180e-03]
rewards = [0, 0, 0, 0, 0, 0, reward_score]
token_id为7的token作为该对话的最后1个有效token，其对应的实际经验奖励reward_score将被⽤于表示整个对话的reward
即其奖励reward_score只会是1个标量
reward_clip(reward_score)
reward_clip: -0.0826
KL[最末有效token的idx] + reward_clip → KL_rewards
$r_{KL} = r(x,y) - \beta \log \frac{\pi_{old}^{RL}(y|x)}{\pi^{SFT}(y|x)}$
KL_rewards = [-4.6873e-04, -3.1257e-04, 5.8591e-05, -5.5084e-03, -4.0741e-03, -5.5275e-03, -8.5999e-02]

然后才有后来的优势值计算结果

$\begin{array}{c} \hat{A}_{t}=\delta_{t}+(\gamma \lambda) \delta_{t+1}+(\gamma \lambda)^{2} \delta_{t+2}+\cdots+(\gamma \lambda)^{T-t+1} \delta_{T-1} \\ \text { where } \delta_{t}=r_{K L, t}+\gamma \cdot V_{\text {old }}\left(s_{t+1}\right)-V_{\text {old }}\left(s_{t}\right) \end{array}$

以及

$R_{t}=\hat{A}_{t}+V_{t}$

最后，再有critic输出的价值估计Value对returns的拟合

$V_{clip} = clip(V_{new}, V_{old}-\phi, V_{old}+\phi)$

$vf\_loss = \frac{1}{2} \cdot E_{\tau \sim \pi_{old}^{RL}} E_{s_t \sim {\tau}} [\max((V_{new}(s_t)-R_t)^2, (V_{clip}(s_t)-R_t)^2)]$

其实不然，原因在于

prm orm本质都是奖励模型给出实际得分评判，他们本身如果需要都可以引入“critic”
prm更倾向于表达“走到这一步是好还是坏”，只看这时候如何
critic本质还是价值估计给出的都是价值预测
而且更多时候critic会更倾向于表达“给定状态和动作，最后的奖励可能是多少”，侧重关注对未来的影响

进一步，23年5月，OpenAI的这篇论文《Let's Verify Step by Step》发现过程监督在训练模型解决具有挑战性的MATH数据集的问题时，明显优于结果监督，比如过程监督模型解决了MATH测试集代表性子集中的78%问题

那如何训练PRM呢，训练模型的第一步当然是收集数据了

为了收集过程监督数据，首先向人工数据标注员提供由模型回答数学问题的逐步解决方案

在每次迭代中，他们为每个问题生成N个解决方案，，且尝试在问题级别（每个问题K个解决方案）或在整个数据集上（总共K个解决方案，不均匀分布在各个问题中）应用这种前K过滤
最终，将收集的步骤级标签的整个数据集称为PRM800K。PRM800K训练集包含针对12K个问题的75K个解决方案的800K个步骤级标签

他们的任务是为解决方案中的每一步分配一个正面、负面或中性的标签，如下图所示

正面标签表示该步骤是正确且合理的
负面标签表示该步骤不正确或不合理
中性标签表示存在歧义。在实践中，如果某个步骤存在微妙的误导性，或者是一个技术上仍然有效但不佳的建议，它可能会被标记为中性

1.3.2 R3：通过结果监督的手段达到过程监督的效果 by24年5月

考虑到结果监督为最终结果提供稀疏的奖励，但不识别错误位置(没法明确哪些动作导致了成功或失败)，而过程监督则提供逐步的奖励，但需要大量的人工标注

24年5月，来自复旦的研究者们(黄萱菁团队)，通过此篇论文《Training Large Language Models for Reasoning through Reverse Curriculum Reinforcement Learning》提出了一种名为R3的创新方法：通过Curriculum RL进行逆向推理学习

该方法仅使用结果监督来实现大型语言模型的过程监督优势。在将RL应用于复杂推理时，核心挑战在于识别出能够获得正向奖励的动作序列，并提供适当的监督以进行优化

对于一个多跳推理问题，可以通过不同的推理路径得出一个标准答案

假设可以访问至少一个示例，即一个通往标准答案的正确推理路径，就像在监督微调中一样。当模型从初始状态 $s_0$ 开始探索时，可能会遇到难以获得正奖励的问题

受以往在带示范的强化学习领域研究的启发，R3作者将给定示范的中间状态集定义为 $S_{\text{Inter}}\subset S$ ，并让策略 $\pi_{\theta}$ 从接近目标状态的中间状态 $s_k \in S_{\text{Inter}}$ 开始探索： $\pi_{\theta}(a_{k+1:T}|s_k)$ ，其中 $a_{k+1:T} = (a_{k+1}, ..., a_T)$
基于结果的奖励函数为最终结果提供反馈，作为在 $s_k$ 之后采取的动作的监督信号

在这种策略中，示范中 $s_k$ 之前的轨迹（即 $\{s_0, a_1, s_1, ..., a_k\}$ 可以作为一种指导，帮助模型更容易获得正向奖励，并避免陷入无方向、低效的探索过程，如下图所示
一旦策略学会了从接近目标的选定状态开始实现目标，它就可以将训练扩展到更远的状态（例如， $s_{k-1}$ ），从而利用已经获得的知识

在每个阶段，模型面临一个容易的探索问题，因为它已经学会解决大部分剩余的部分，因此很可能成功。通过这种方式，可以形成一个逐步增加探索难度的curriculum

这使得能够为模型提供大致的逐步监督信号，现在，策略梯度可以表示为：
$\begin{array}{l} \mathbb{E}_{s_{k} \sim \mathcal{S}^{\text {Inter }}} {\left[\mathbb{E}_{\tau \sim \pi_{\theta}^{\mathrm{RL}}\left(\cdot \mid s_{k}\right)}[ \right.} \\ \left.\left.\sum_{t=k+1}^{T} \nabla_{\theta} \log \pi_{\theta}^{\mathrm{RL}}\left(a_{t} \mid s_{t-1}\right) R_{o}\left(s_{t-1}, a_{t}\right)\right]\right] \end{array}$
其中， $S_{\text{Inter}}$ 指的是从数据集 $D$ 中采样的一个演示的中间状态集； $k$ 从 $T-1$ 开始并逐步回退到 $0$ 。在最后一步，模型开始从初始状态 $s_0$ 展开，这相当于原始的结果监督强化学习
接下来，便可以通过PPO算法迭代策略，且设计奖励函数
$\begin{array}{l} r_{\text {final }}\left(s_{t-1}, a_{t}\right)=r_{o}\left(s_{t-1}, a_{t}\right) \\ \quad-\beta \mathrm{KL}\left(\pi_{\theta}^{R L}\left(\cdot \mid s_{t-1}\right), \pi_{\theta}^{I n i t}\left(\cdot \mid s_{t-1}\right)\right) \end{array}$
且和此文《ChatGPT原理》中3.2节介绍的DSC一样，通过广义优势估计GAE来计算优势

第二部分自我推理验证出问题之后，如何让模型学会自我纠正

2.1 自我推理之Self-Taught Reasoner及其变体Quiet-STaR

2.1.1 STaR: Self-Taught Reasoner Bootstrapping Reasoning With Reasoning

22年3月，来自斯坦福、Google的研究者们(Eric Zelikman, Yuhuai Wu, Jesse Mu, Noah D. Goodman)，提出了《STaR: Self-Taught Reasoner Bootstrapping Reasoning With Reasoning》

具体而言，作者使用少量示例提示大型语言模型自我生成推理过程，并通过对那些导致正确答案的推理进行微调，进一步提升模型的能力，然后重复这一过程，每次使用改进后的模型生成下一组训练集。这是一个协同过程，其中推理生成的改进提升了训练数据，而训练数据的改进又进一步提升了推理生成
但作者发现上面这个循环最终无法解决训练集中任何新的问题，因为它没有收到针对未能解决的问题的直接训练信号
为了解决这个问题，作者提出了合理化方法：对于每个模型未能正确回答的问题，他们通过提供正确答案来生成新的推理过程
这让模型能够逆向推理——给定正确答案，模型可以更容易地生成有用的推理过程
这些推理过程随后被收集为训练数据的一部分，通常可以提高整体准确性

总之，作者开发了自学推理者(Self-Taught Reasoner，简称STaR)方法，如下图所示

这是一种可扩展的自举方法，允许模型学习生成自己的推理，同时也学习解决日益复杂的问题
在该的方法中，重复以下过程：

在每次迭代中，首先利用当前模型的推理生成能力尝试解决数据集，从而构建微调数据集的种子集数据
然后，想办法增强该数据集，即为模型未能解决的问题的真实答案提供合理解释
最后，在组合后的数据集上微调大型语言模型

具体实现过程如下

先有一个预训练的LLM和一个包含问题 $x$ 及其答案 $y$ 的初始数据集： $\mathcal{D}=\left\{\left(x_{i}, y_{i}\right)\right\}_{i=1}^{D}$
STaR的方法从一个包含中间推理过程 $r$ 的小提示集P开始： $\mathcal{P}=\left\{\left(x_{i}^{p}, r_{i}^{p}, y_{i}^{p}\right)\right\}_{i=1}^{P}$
其中P≪D（例如P= 10）

类似于标准的少样本提示，然后将这个提示集合与D中的每个示例连接起来，即 $x_{i}=\left(x_{1}^{p}, r_{1}^{p}, y_{1}^{p}, \ldots, x_{P}^{p}, r_{P}^{p}, y_{P}^{p}, x_{i}\right)$ ，这鼓励模型为 $x_i$ 生成一个理由 $\hat{r}_{i}$ ，然后是一个答案 $\hat{y}_{i}$

假设导致正确答案的理由比导致错误答案的理由质量更高。因此，过滤生成的理由，仅保留那些导致正确答案的理由——即 $\hat{y}_{i}=y_{i}$
然后，在这个过滤后的数据集上微调基础模型 $M$
通过使用新微调的模型生成新的理由来重新开始这个过程
不断重复这个过程，直到性能达到预期
注意，在这个过程中，一旦收集到一个新的数据集，便会从原始的预训练模型M开始训练，而不是持续训练一个模型，以避免过拟合

下图是算法概要/流程

总之，STaR可以被视为RL风格策略梯度目标的近似。要理解这一点，请注意，M可以被视为一个离散潜变量模型 $p_{M}(y \mid x)=\sum_{r} p(r \mid x) p(y \mid x, r)$ ——换句话说， $M$ 首先采样一个潜在的理性 $r$ 然后预测 $y$

现在，给定指示器奖励函数，整个数据集上的总期望奖励为

$\begin{aligned} J(M, X, Y) & =\sum_{i} \mathbb{E}_{\hat{r}_{i}, \hat{y}_{i} \sim p_{M}\left(\cdot \mid x_{i}\right)} \mathbb{1}\left(\hat{y}_{i}=y_{i}\right), \\ \nabla J(M, X, Y) & =\sum_{i} \mathbb{E}_{\hat{r}_{i}, \hat{y}_{i} \sim p_{M}\left(\cdot \mid x_{i}\right)}\left[\mathbb{1}\left(\hat{y}_{i}=y_{i}\right) \cdot \nabla \log p_{M}\left(\hat{y}_{i}, \hat{r}_{i} \mid x_{i}\right)\right] \end{aligned}$

梯度是通过策略梯度的标准对数导数技巧获得的。注意，指示函数会丢弃所有未能导致正确答案 $y_i$ 的采样理由的梯度：这是 STaR 中的过滤过程(如上面Algorithm 1 STaR第 5 行所示）。因此，STaR 通过以下方式近似 $J$

贪婪地解码 $(\hat{r}_i, \hat{y}_i)$ 的样本，以减少此估计的方差(以可能导致对理由的偏见性探索为代价，即at the cost of potentially biasedexploration of rationales)
以及在同一批数据上进行多次梯度步骤「类似于一些策略梯度算法 [25]，即Proximal policy optimization algorithms——简称PPO」

2.1.2 Quiet-STaR: 语言模型可以教会自己在说话前思考

24年3月，来自斯坦福的研究者(Eric Zelikman, Georges Raif Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, Noah Goodman)，提出此篇论文《Language Models Can Teach Themselves to Think Before Speaking》

在上一节的《自学推理者》（STaR, Zelikman et al. 2022）中，有用的思考是通过「从问答中的几个例子中推断基本原理，并从那些导致正确答案的例子中学习」来学习的
In the Self-Taught Reasoner (STaR, Zelikman et al. 2022),useful thinking is learned by inferring rationales from few-shot examplesin question-answering and learning from those that lead to a correc tanswer.

这是一个高度受限的设置——理想情况下，语言模型可以学会在任意文本中推断未陈述的基本原理
This is a highly constrained setting – ideally, a language modelcould instead learn to infer unstated rationales in arbitrary text.
故作者提出Quiet-STaR，这是STaR的一个推广版本，其中语言模型学习在每个token上生成理由(相当于在生成每个token时，都能生成一个为何生成当下token的“内心独白”或“理由”)以解释未来文本，从而改善其预测
We present Quiet-STaR, a generalization of STaR in which LMs learn to generate rationales at each token to explain future text, improving theirpredictions.

具体而言，Quiet-STaR的操作包括三个主要步骤，如下图所示

并行推理生成，即Parallel rationale generation
在输入序列 $x_{0: n}$ 中并行处理每个标记 $x_i$ ，生成长度为 $t$ 的推理： $t: c_{i}=\left(c_{i 1}, \ldots, c_{i t}\right)$ ，从而产生 $n\times r$ 个推理候选
插入学习到的<|startofthought|>和<|endofthought|>token来标记每个推理的开始和结束
In parallel across n tokens xi in an input sequence x0:n, we generate r rationales of length t: ci = (ci1, . . . , cit),resulting in n × r rationale candidates.
We insert learned <|startofthought|> and<|endofthought|> tokens to mark each rationale’s start and end.
混合：后推理和基础预测，即Mixing post-rationale and base predictions
从每个推理后的隐藏状态输出中，作者训练一个“混合头”——一个浅层的多层感知机（MLP），生成一个权重，用于确定在多大程度上应该将基于推理后的下一个词预测的 logits 与基础语言模型预测的 logits 结合起来
由于引入了推理，这种方法在微调的早期阶段缓解了分布偏移
From the hiddenstate output after each rationale, we train a ”mixing head” – a shallow MLP produc-ing a weight determining how much the post-rationale next-token predicted logits should be incorporated compared to the base language model predicted logits. Thisapproach eases distribution shift early in finetuning, due to introducing rationales.
优化理由生成，即Optimizing rationale generation
作者优化理由生成参数（开始/结束标记和语言模型权重），以增加使未来文本更可能出现的理由的概率
We optimize the rationale generation parameters (start/end tokens and LM weights) to increase the likelihoodof rationales that make future text more probable.

且使用REINFORCE为理由提供学习信号，基于它们对未来token预测的影响
为了减少方差，作者采用了一种教师强迫技巧，在损失中不仅包括预测思考之后的token的可能性，还包括预测后来的token的可能性
We use REINFORCE to providea learning signal to rationales based on their impact on future-token prediction.
To reduce variance, we apply a teacher-forcing trick to include in the loss thelikelihood of predicting not only the token after the thought but also later tokens

理论清楚了，咱们来看下代码实现

我觉得可能不少读者已经懵了，为方便大家一目了然，我给上面的代码逐行解读下(没有下面这个解读，你会觉得好难，有了这个解读，你会觉得原来这么好理解！)

准备阶段：需要一个初始的模型，一些训练数据，以及一些参数来控制训练的过程，比如学习的速度（学习率）和每次训练处理的数据量（批次大小）
训练过程：反复进行训练，直到达到预定的训练步数。每一轮训练，都会取出一批数据
# 训练过程，重复num_steps次
for i=0 to num_steps do
# 从输入序列 X 中抽取一个长度为 l 的批次
Sample batch of sequences X of length l
# 初始化隐藏状态
$h^{\text{init}}\leftarrow\text{ hidden states }{}_{\theta_{i}}(X)$
对于这批数据中的每个位置，都会做以下事情：
# 对于序列中的每个位置 $j$ 的token(使用并行和注意力掩码)，都会生成推理并进行预测
for j=1 to l in parallel using attention mask do

  首先，让模型预测接下来应该出现什么词
# 使用语言模型的头部预测下一个 $n_{true}$ 个token的概率，并计算初始的对数概率 log p_init
   $\log p_{j: j+n_{\text {true }}}^{\mathrm{init}} \leftarrow \operatorname{lm} \text { head }_{\theta_{i}}\left(h_{j: j+n_{\text {true }}}^{\text {init }}\right)$

然后，让模型生成一些“思考”的内容，这些内容就像是模型在做出预测之前的“内心独白”
# 为序列X当前位置 $j$ 的token生成内在推理/思维 $T_j$ ，思维用 `<start_thought>` 和 `<end_thought>` 包裹，并生成 n_thoughts 个潜在思维

# 用 `<end_thought>` 标记生成思维的结束

接下来，把模型生成的“内心独白”和原始数据结合起来，再次让模型预测接下来的词
# 将生成的推理Tj与原始序列X结合，并更新隐藏状态

# 使用更新后的隐藏状态预测下一个 $n_{true}$ 个token的概率，并计算计算带有思维的对数概率 log p_thought
   $\log p_{j: j+n_{\text {true }}}^{\text {thought }} \leftarrow \operatorname{lm} \text { head }_{\theta_{i}}\left(h_{j: j+n_{\text {true }}}^{\text {thought }}\right)$
混合预测：结合模型的原始预测和带有“内心独白”的预测，得到一个综合的结果
# 使用混合头部计算一个权重，这个权重决定了原始预测和带有推理的预测在最终预测中所占的比例
$w_{j: j+n_{\text{true}}}\leftarrow\text{ mixing head}_{\theta_i}(\left[h_{j: j+n_{\text{true}}}^{\text{thought}}, h_{j: j+n_{\text{true}}}^{\text{init}}\right)$
计算损失：我们会计算模型的预测和实际数据之间的差异，这个差异就是模型需要改进的地方
# 计算混合后的对数概率，得到最终预测 $\log p_{j}^{\text {talk }}$
$\log p_j^{\text{talk}}\leftarrow w_{j: j+n_{\text{true}}}\cdot\log p_{j: j+n_{\text{true}}}^{\text{init}}+\left(1-w_{j: j+n_{\text{true}}}\right)\cdot\log p_{j: j+n_{\text{true}}}^{\text{thought}}$
# 使用负对数似然计算损失函数，基于真实标签 $X_{j+1: j+ n_{ true}+1}$ ，与最终的预测 $\log p_{j: j+ n_{ true}}^{ talk}$ ——代表在位置 j 到 j+n_true 的预测
$\mathcal{L}_j^{ NLL}\leftarrow-\log p_{j: j+ n_{ true}}^{ talk}(X_{j+1: j+ n_{ true}+1})$
奖励机制：如果模型的预测因为加入了“内心独白”而变得更好，就会给它一些“奖励”，让它知道这样做是对的
# 计算REINFORCE奖励，这是带有推理的预测和原始预测之间的对数概率差异，我大胆估计一下，估计可能有朋友在这里不明白了，咋就 $\log\overline{p}_{j: j+ n_{\text{true}}}^{\text{talk}}$ 代表了模型初始状态下(没有使用思维推理推理部分)生成的对数概率，其实伪代码么，加之 $\bar{p}$ 通常表示某种“基线”或“平均”值，故 $\log\overline{p}_{j: j+ n_{\text{true}}}^{\text{talk}}$ 则用来代表模型在没有进行推理之前的基础预测概率了
$r_j=\log p_{j: j+ n_{\text{true}}}^{\text{talk}}\left(X_{j+1: j+ n_{\text{true}}+1}\right)-\log\overline{p}_{j: j+ n_{\text{true}}}^{\text{talk}}\left(X_{j+1: j+ n_{\text{true}}+1}\right)$

# 如果rj大于0——相当于引入思维后的预测结果比基础预测好「即 $\log p_{j: j+n_{\text {true }}^{\text {talk }}}\left(X_{j+1: j+n_{\text {true }}+1}\right)$ 更高」，那么奖励 r_j 将是正值，表示模型得到了改进；否则，奖励为负值，表示没有改进或表现更差，使用REINFORCE奖励更新模型参数
$\nabla_\theta\mathcal{L}_j^{REINFORCE}\leftarrow-r_j 1[r_j>0]\cdot\nabla_\theta\log p_{\theta_i}(T_j|[X_{:j};<\text{start\_thought}>])$

# 将NLL损失和REINFORCE损失相加，得到总损失
$\nabla_\theta\mathcal{L}_j\leftarrow\nabla_\theta\mathcal{L}_j^{NLL}+\nabla_\theta\mathcal{L}_j^{REINFORCE}$
更新模型：根据损失和奖励，会调整模型的参数，让模型在下一次预测时做得更好
# 使用梯度下降法更新模型参数
$\theta_{i+1}\leftarrow\theta_{i}-\alpha\sum_{j=1}^{l}\nabla_{\theta}\mathcal{L}_{j}\qquad//\text{ Update model parameters}$
# 返回训练后的模型参数
$return \theta_{\text{num\_steps}}$

最后，重复以上步骤，直到模型训练完成

补充一下关于Quiet-STaR的三个主要步骤

首先是并行生成

Quiet-STaR的一个关键挑战是在输入序列的每个token位置高效地生成理由，简单地说，这需要对每个token进行单独的前向传递，这对于长序列来说在计算上是不可行的「A key challenge in Quiet-STaR is efficiently generating rationales at each token position in the input sequence. Naively, this would require a separate forward pass for each token,which becomes computationally intractable for long sequences」

作者首先观察到，语言模型的推理过程会为所有输入token生成下一个token的概率分布，这样就可以实现高度并行的生成
We allow for highly parallel generation by first observing that an inference pass of a languagemodel produces a probability distribution over the next tokens for all input tokens.
自然地，这使咱们可以从输入中的每个token中采样一个下一个token。如果已经从每个token生成了一个后继token，就无法简单地继续原来的序列
Naturally,this allows us to sample one next token from each token in the input. If one has generated asuccessor from each token, it is not possible to simply continue with the original sequence.

例如，想象一下在“the cat sat”的每个token后预测下一个token，可能会生成“yes orange saw down”——每个后继token本身都是一个合理的下一个token
For example, imagine predicting the next token after each token of “< bos > the cat sat” onemight generate “yes orange saw down” – each successor by itself is a reasonable next token

如下图所示，通过构建一种注意力掩码，使得所有思维token能够关注自身、同一思维中的所有前面思维token以及前面的文本(说白了，就是每个thought token只能看到它之前的thought token以及对应的token文本，这跟GPT在注意力掩码下的解码策略是一致的)，从而可以并行生成所有思维的续写。每次推理调用用于为所有文本token生成一个额外的思维token「By constructing an attention mask that allows all thought tokens to pay attention to themselves, all preceding thought tokens with in the same thought,and the preceding text, we can generate continuations of all of the thoughts in parallel. Eachinference call is used to generate one additional thought token for all text tokens.」

对于序列的前缀，但这些token的列表是一组这些前缀的“反事实”延续「to a prefix of the sequence, but the list of tokens is a set of “counterfactual” continuations ofthese prefixes」，然而，可以利用这些延续为每个观察到的token生成隐藏的想法
为了高效地实现这一点，作者缓存每次前向传递，并将一个对角注意力掩码与之前的注意力掩码连接起来：每个生成的token现在不仅关注用于生成它的所有token，还关注它自身（但不关注其他“反事实”路径上的token）
此外，这种并行化的下一个采样token过程可以任意重复多次(或者至少，直到内存耗尽为止)

// 待更

2.2(选读) 如何让模型学会自我纠错——Recursive Introspection(简称RISE，类似STaR)

注，该篇论文的可读性不太高，仅做选读，不影响整体理解

一直以来，让大模型在回答时意识到自己的错误并修正这一点上，并不容易，之前的尝试包括且不限于

prompt模型，要求他们回答时如果错了要及时自我纠正，或者要求模型尝试多次回答，或者在特定领域的问答数据上对模型进行微调
但效果都不太好，除非你给模型证明它确实出错了详细证据
生成展示多轮连续改进的数据(可能来自高性能模型），但发现仅仅模仿这些数据并不足以实现这种自我纠错的能力
原因在于：首先，来自不同模型的多轮数据不会展示学习者可能犯的错误类型的改进，因此与学习者无关[24]
First, multi-turn data from a different model would not show improvements in the kinds of errors the learner would make, thereby being irrelevant to the learner [24].

其次，通常从专有模型收集的多轮连续数据质量也不高，因为这些模型通常不擅长对自己的错误提出有意义的改进[21]，尽管它们仍然可以对手头的问题提供有用的回答

24年7月，来自Carnegie Mellon University、UC Berkeley、3MultiOn的研究者们(Yuxiao Qu, Tianjun Zhang, Naman Garg, Aviral Kumar)提出了一种名为递归自省的方法——RISE 「其对应的论文为Recursive introspection: Teaching language model agents how to self-improve」，类似的工作不少，比如这三个：GLoRE、Generating Sequences by Learning to Self-Correct (该工作发表的比较早，其发表于22年10月底，来自Allen Institute for Artificial Intelligence等机构)，以及下一节的SCoRe

RISE的目标是提高大型语言模型在给定问题的连续尝试/回合中的表现

具体来说，给定一个问题 $x_i$ 和其标准答案 $\boldsymbol{y}_{i}^{*}$ 的数据集 $\mathcal{D}=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{y}_{i}^{*}\right)\right\}_{i=1}^{N}$ ，他们的目标是获得一个 $\operatorname{LLM} \pi_{\theta}\left(\cdot \mid\left[\boldsymbol{x}, \hat{\boldsymbol{y}}_{1: t}, p_{1: t}\right]\right)$ ，该模型在给定问题 $x$ 、之前模型对问题的尝试 $\hat{\boldsymbol{y}}_{1: t}$ ，以及辅助指令 $p_{1: t}$ 「例如，查找错误并改进回答的指令；或来自环境的额外编译器反馈」时，尽可能正确地解决给定问题

为此，将这一目标编码为以下希望优化的学习目标

$\max _{\pi_{\theta}} \sum_{i=1}^{L} \mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}^{*} \sim \mathcal{D}, \hat{\boldsymbol{y}}_{i} \sim \pi_{\theta}\left(\cdot \mid\left[\boldsymbol{x}, \hat{\boldsymbol{y}}_{1: i-1}, p_{1: i-1}\right]\right)}\left[\mathbb{I}\left(\hat{\boldsymbol{y}}_{i}==\boldsymbol{y}^{*}\right)\right]$

与标准的监督微调不同，标准的监督微调训练模型 $\pi$ 在给定 $x$ 的情况下生成单一的响应 $\hat{y}$ ，而上述方程则训练 $\pi$ 在给定其之前尝试的响应历史 $\hat{\boldsymbol{y}}_{1: i-1}$ 的情况下做出适当反应
Unlike standard supervised fine-tuning that trains the model 𝜋to produce a single response ˆ𝑦given 𝑥,Equation 3.1 trains 𝜋to also appropriately react to a given history of responses from its own previousattempts ˆ𝑦1:𝑖−1

如下图所示

左图：问题表述
将单轮问题转换为多轮马尔可夫决策过程（MDP）
状态由提示prompt、先前尝试的历史记录和来自环境的可选反馈构成
动作是由大型语言模型在当前多轮交互状态下生成的响应
右图：数据收集
通过展开当前模型 $k-1$ 次来收集数据，随后进行响应改进，这种改进通过以下方式获得：
（1）自蒸馏：从当前模型中采样多个响应，并使用最佳响应
（2）蒸馏：通过查询更强大的模型获得理想响应
在任一情况下，RISE随后在生成的数据上进行训练

对于上面数据改进的第一种方式——自蒸馏，具体怎么理解呢

具体而言，对于数据集中每个状态 $\boldsymbol{s}_{t}^{i} \in \mathcal{D}_{\text {on-policy }}$ ，从策略中采样 $N$ 个响应 $\tilde{\boldsymbol{y}}_{t}^{i}[0], \tilde{\boldsymbol{y}}_{t}^{i}[1], \cdots, \tilde{\boldsymbol{y}}_{t}^{i}[N] \sim \pi_{\theta}\left(\cdot \mid \boldsymbol{s}_{t}^{i}\right)$
Concretely, for each state in the dataset, 𝑠𝑖𝑡∈𝒟on-policy, we sample 𝑁 responses˜𝑦𝑖𝑡[0], ˜𝑦𝑖𝑡[1], · · · , ˜𝑦𝑖𝑡[𝑁] ∼𝜋𝜃(·|𝑠𝑖𝑡),

并使用这些 $N$ 个候选响应中最好的一个(通过关联的奖励值 $\tilde{r}_{t}^{i}[0], \cdots, \tilde{r}_{t}^{i}[N]$ 进行衡量)来重新标记下一步 $t + 1$ 的模型响应，以形成一个改进轨迹
and use the best response from these 𝑁candidates (as measured bythe associated reward values ˜𝑟𝑖𝑡[0], · · · , ˜𝑟𝑖𝑡[𝑁]) to relabel the model response at the next step 𝑡+ 1 in animprovement trajectory.
形式上，假设 $\tilde{\boldsymbol{y}}_{t}^{i}[m]=\arg \max _{j \in[N]} r\left(\boldsymbol{s}_{i}, \tilde{\boldsymbol{y}}_{t}^{i}[j]\right)$ ，那么在步骤 $t + 1$ 时用改进的响应及其关联的奖励值 $\tilde{r}_{t}^{i}[m]$ 来标记数据集 $\mathcal{D}_{\text {on-policy }}$ 中的响应
Formally, say ˜𝑦𝑖𝑡[𝑚] = arg max𝑗∈[𝑁] 𝑟(𝑠𝑖, ˜𝑦𝑖𝑡[𝑗]), then we label the responses in the dataset 𝒟on-policy at step 𝑡+ 1 with the improved response and its associated reward value ˜𝑟𝑖𝑡[𝑚]:
$\tilde{\mathcal{D}}_{\text {on-policy }+ \text { self-distillation }}:=\left\{\left\{\left(\boldsymbol{s}_{t+1}^{i}, \tilde{\boldsymbol{y}}_{t}^{i}[m], f_{t+1}^{i}, \tilde{r}_{t}^{i}[m]\right)\right\}_{t=0}^{T-1}\right\}_{i=1}^{|\mathcal{D}|}$

// 待更

2.3 Self-Correct之SCoRe：通过多轮强化学习进行自我纠正

2.3.1 什么是Self-Correct之SCoRe：对大模型通过RL进行自我纠正 by24年9月

1.1节开头说过，OpenAI o1学会了识别并纠正自己的错误，那它怎么做到的呢

之前对自我纠正LLM的尝试要么依赖于提示工程，要么依赖于专门为自我纠正而微调模型

前者通常无法进行有意义的内在自我纠正
而微调方法在推理时需要运行多个模型，例如一个独立的改进模型，或依赖“教师”监督来指导自我纠正的过程
使用独立的教师监督模型时，自我纠正不一定优于并行的独立尝试

24年9月下旬，Google开发了一种不需要这些要求的有效自我纠正方法，称为通过强化学习进行自我纠正(Self-Correction via Reinforcement Learning，简称SCoRe），其对应的论文为：《Training Language Models to Self-Correct via Reinforcement Learning》

其仅训练一个模型，该模型既可以对问题产生响应，也可以在没有任何预测反馈的情况下纠正错误简言之，SCoRe是一种多轮次强化学习方法，用于教大型语言模型如何纠正自己的错误
且与其最接近的便是上一节介绍的递归自省——Recursive Introspection(简称RISE，类似STaR)，他们利用一种类似STaR的迭代方法进行自我纠正。尽管该研究主要使用了预言式教师监督，但其仅通过五轮自我纠正训练获得的初步结果显示出微小的改进，这与在STaR中看到的结果一致
Perhaps the closest tous from this set is Qu et al. (2024), which utilizes an iterative STaR-like approach self-correction. Whilethis work largely uses oracle teacher supervision, their preliminary results from training for self-correctiononly show minor improvements over five turns, consistent with the results we see for STaR.

SCoRe采用两阶段训练：

在第一阶段，通过训练纠正第二次尝试的响应，同时将第一次尝试的分布约束在接近基础模型，以产生不易行为崩溃的初始化
in the first stage, it produces aninitialization that is less susceptible to behavior collapse by training to correct second-attempt responses while constraining the first-turn distribution to be close to the base model;
然后在第二阶段对两次尝试进行训练以最大化奖励「followed by training on both attempts to maximize reward in the second stage」
关键是，多轮RL的第二阶段采用了一种奖励塑形项，该项奖励的是“朝向自我纠正的进展”，而不是最终响应的正确性
the second stage of multi-turn RL employs are ward shaping term that rewards “progress” towards self-correction as opposed to the correctness of the final response

在效果上，相对于基础的Gemini模型，SCoRe的方法在MATH（Hendrycks等人，2021）的推理问题上实现了绝对15.6%的自我纠正提升，并且实现了绝对9.1%的提升

具体来说，如下图所示，表示的是自我纠正的问题设定「SCoRe不仅训练模型生成最佳可能的响应，还旨在训练模型在最后一次尝试中生成最佳最终响应。在第二轮中，可能会以指令的形式提供额外输入，要求模型自我纠正或由模型生成」

给定一个包含问题 $\boldsymbol{x}_{i}$ 和响应 $y_{i}^{*}$ 的数据集 $\mathcal{D}=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{y}_{i}^{*}\right)\right\}_{i=1}^{N}$
然后训练一个LLM策略 $\pi_{\theta}\left(\cdot \mid\left[x, \hat{y}_{1: l}, p_{1: l}\right]\right)$ ，该策略在给定问题 $x$ 、之前模型对该问题的 $l$ 次尝试 $\hat{\boldsymbol{y}}_{1: l}$ 以及辅助指令 $p_{1: l}$ 「例如，寻找错误并改进响应的指令」的情况下，尽可能正确地解决问题 $x$
这种形式化类似于Qu等人「即上面提过的RISE，详见Recursive introspection: Teaching language model agents how to self-improve」中的多轮MDP
作者还假设可以访问一个oracle奖励̂ $\hat{r}\left(y, y^{*}\right)$ ，例如一个答案检查器「即answer checker，详见此论文：Solving math word problems with process-and outcome-based feedback，即要求语言模型生成推理步骤可以提高许多推理任务的性能，且对于正确的推理步骤，发现有必要使用基于过程的监督或来自模拟基于过程的反馈的学习奖励模型的监督」，通过将响应 $y$ 与oracle响应 $y^{*}$ 进行比较来评估其正确性
We also assumeaccess to an oracle reward ̂𝑟(𝒚, 𝒚∗), such as an answer checker (Uesato et al., 2022), that evaluates the correctness of response 𝒚 by comparing it with the oracle response 𝒚∗. C

至关重要的是，不假设在测试时能访问这个oracle；相反，模型必须推断是否存在错误，并在必要时进行纠正，这在——例如数学推理问题中经常发生

接下来，需要找到一个LLM策略 $\pi(\square \mid \circ)$ ，将输入token $\circ$ 映射到输出标记□，以最大化在 $l + 1$ 轮（ $l = 1$ ）结束时从验证器verifier获得的正确性奖励

$\max _{\pi_{\theta}} \mathcal{E}_{\boldsymbol{x}, \boldsymbol{y}^{*} \sim \mathcal{D}, \hat{\boldsymbol{y}}_{l+1} \sim \pi_{\theta}\left(\cdot \mid\left[x, \hat{y}_{1: l}, p_{1: l}\right]\right)}\left[\sum_{i=1}^{l+1} \hat{r}\left(\hat{\boldsymbol{y}}_{i}, \boldsymbol{y}^{*}\right)\right]$

请注意，与标准的监督微调或常见的强化学习微调流程不同——这些流程训练策略 $\pi$ 直接生成 $y^{*}$ 「或任何其他 $y$ 使得 $\hat{r}\left(y, y^{*}\right)=1$ 」

而SCoRe下的上述方程则是同时在多次尝试中训练 $\pi$ ，其中中间步骤是间接监督的，以最大化总和「Equation 1 trains 𝜋 over multiple attempts simultaneously, where intermediate turns are supervised indirectly to maximize the sum」

然后使用基础强化学习微调方法，采用了一种带有固定模型KL散度惩罚的REINFORCE策略梯度训练方法「Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs」，这种方法广泛应用于大语言模型的强化学习微调中，主要用于单轮RLHF的场景
形式上，这些方法训练策略 $\pi_{\theta}(\cdot \mid x)$ 以优化以下内容，其中 $\pi_{\mathrm{ref}}$ 是一个参考策略

$\max _{\theta} \mathbb{E}_{\boldsymbol{x}_{t}, \boldsymbol{y}_{t} \sim \pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{t}\right)}\left[\hat{r}\left(\boldsymbol{y}_{t}, \boldsymbol{y}^{*}\right)-\beta_{1} D_{K L}\left(\pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{t}\right)| | \pi_{\mathrm{ref}}\left(\cdot \mid \boldsymbol{x}_{t}\right)\right)\right]$

2.3.2 SCoRe：通过多轮强化学习进行自我纠正 by24年9月

为了衡量自我纠正性能（本文中考虑 $l = 2$ ），然后报告并分析以下指标：

Accuracy@t1：模型在第一次尝试时的准确率
Accuracy@t2：模型在第二次尝试时的准确率
$\Delta(\mathrm{t} 1, \mathrm{t} 2)$ ：第一次和第二次尝试之间模型准确率的净提升，衡量自我纠正的效果
$\Delta^{\mathrm{i} \rightarrow \mathrm{C}}(\mathbf{t} 1, \mathbf{t} 2)$ ：在第一次尝试中错误但在第二次尝试中变为正确的问题的比例，衡量自我纠正能解决多少新问题
$\Delta^{\mathrm{c} \rightarrow \mathrm{i}}(\mathbf{t} 1, \mathbf{t} \mathbf{2})$ ：在第一次尝试中正确但在第二次尝试中变为错误的问题的比例，衡量模型对正确答案理解的程度

在对训练数据进行强化学习策略优化时，至少有两种同样好的解决方案：

(i) 学习如何从第一次尝试到第二次尝试进行改进
或 (ii)学习如何在第一次尝试时就产生最佳响应，然后在第二次尝试中不进行修正

虽然一个好的自我纠正策略应该最大化 accuracy@t1 和 accuracy@t2，但作者发现标准的强化学习会导致行为不再纠正——言外之意，就是标准的RL不符合作者的预期

因此，作者在 SCoRe 中的关键见解是必须更明确地鼓励自我纠正行为，这通过一个两阶段的方法来实现

第一阶段（Stage I）起到初始化的作用，在这一阶段，我们通过优化第二次尝试的准确率，同时明确地将第一次尝试的分布限制在基础模型上，来训练模型以实现两次尝试行为的解耦
The first stage (Stage I) serves the role of initialization where we train the model to decouple its behavior across the two attempts by attempting to optimize second-attemptaccuracy while explicitly constraining the distribution of first attempts to the base model.
接下来，阶段 II 共同优化两次尝试的奖励。为了确保阶段 II 不会退化为“直接”解决方案，作者对奖励进行偏向，以加强自我纠正的进展
From here,Stage II then jointly optimizes the reward of both attempts. To ensure that Stage II does not collapse to the “direct” solution, we bias the reward to reinforce self-correction progress

具体而言，如下图所示

阶段 I：训练解耦尝试的初始化，相当于第一轮贴近初始模型的结果
SCoRe的第一阶段目标是通过改进基础模型在第二次尝试上的覆盖率来获得一个初始化，而这种改进是基于第一次尝试的结果，以减少后续的自我纠错训练中出现行为坍塌的可能性
The goal of Stage I of SCoRe is to obtain an initialization by improving the base model’s coverage over second attempts given the first attempt, so that subsequent training for self-correction is less prone tobehavior collapse.

$\rightarrow$ 虽然这通常通过SFT来完成，但由于SFT本身也存在崩溃。因此，作者在这一阶段使用强化学习来解耦两次尝试
为此，作者明确地微调基础模型，使其在第二次尝试时产生高奖励的响应，同时通过使用KL散度约束模型，使其第一次尝试保持接近基础模型，从而不改变第一次尝试
To do so,we explicitly fine-tune the base model to produce high-reward responses at the second attempt, whileforcing the model to not change its first attempt by constraining it to be close to the base model usinga KL-divergence

$\rightarrow$ 且尽管这看起来可能次优——减少第一次尝试中的错误本应带来更好的第二次尝试——但正如作者将展示的，这个阶段在减少基础模型仅仅将第一次和第二次尝试的分布简单地耦合在一起的偏见方面是至关重要的，从而在实际进行多轮RL时避免行为坍塌
While this may appear sub-optimal – a first attempt with fewer mistakes should leadto a better second attempt – but as we will show, this stage is critical in reducing the base model’s biastowards simply coupling the first and second-attempt distributions, thus avoiding behavior collapse when actual multi-turn RL is run

其目标为
其中 $\beta_{2}$ 是一个超参数，旨在仅在第一次尝试时强制执行严格的KL惩罚，以避免第一次对话的response发生偏移(如上标蓝的部分所示)

有两个小问题需要注意一下

1) 首先是为何用KL惩罚，其实很好理解，就是让迭代中的策略 $\pi_{\theta}$ 不要跟最初的策略 $\pi_{\mathrm{ref}}$ 相差太远，类似ChatGPT的迭代——详见此文ChatGPT原理的「3.1.3 InstructGPT训练阶段3：如何通过PPO算法进一步优化模型的策略」

2) 此处仍然使用来自上节最后的默认KL散度惩罚——即如下所示
$\max _{\theta} \mathbb{E}_{\boldsymbol{x}_{t}, \boldsymbol{y}_{t} \sim \pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{t}\right)}\left[\hat{r}\left(\boldsymbol{y}_{t}, \boldsymbol{y}^{*}\right)-\beta_{1} D_{K L}\left(\pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{t}\right)| | \pi_{\mathrm{ref}}\left(\cdot \mid \boldsymbol{x}_{t}\right)\right)\right]$
但权重相对较小，并且为了清晰起见在上述方程中省略
且实验证明与标准多轮强化学习相比，本阶段I在分离两个响应方面更为有效，并且导致了更好的阶段II性能
阶段二：带奖励塑造的多轮次强化学习，相当于第二轮鼓励大胆尝试，并试图纠正
SCoRe的第二阶段从第一阶段初始化，现在共同优化两次尝试的性能
第二阶段通过以下目标来训练策略 $\pi_{\theta}(\cdot \mid \cdot)$ ，定义为方程4

$\max _{\theta} \mathbb{E}_{\boldsymbol{x}_{1}, \boldsymbol{y}_{1} \sim \pi_{\theta}(\cdot \mid \boldsymbol{x}), \boldsymbol{y}_{2} \sim \pi_{\theta}\left(\cdot \mid\left[\boldsymbol{x}_{1}, p_{1}\right]\right)}\left[\sum_{i=1}^{2} \hat{r}\left(\boldsymbol{y}_{i}, \boldsymbol{y}^{*}\right)-\beta_{1} D_{K L}\left(\pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{i}\right)| | \pi_{\mathrm{ref}}\left(\cdot \mid \boldsymbol{x}_{i}\right)\right)\right]$

其中 $\boldsymbol{x}_{i}, i \in\{1,2\}$ 对应于作为上下文传递给模型的输入token集

   $\rightarrow$ 为了防止学习过程在阶段II中崩溃为非自我纠正的解决方案，需要将学习问题偏向于自我纠正
  To prevent the learning process from collapsing to a non self-correcting solution in Stage II,we need to bias the learning problem towards self-correction」
   $\rightarrow$ 作者通过奖励塑造来实现这一点：通过奖励那些在学习期望的自我纠正行为上取得“进展”的转换
We implement this via reward shaping:by rewarding transitions that make “progress” towards learning the desired self-correction behavior.

具体来说，给定从策略中采样的一个两轮回合
$\tau=\left\{\boldsymbol{x}_{1}, \hat{\boldsymbol{y}}_{1}, \hat{r}\left(\boldsymbol{y}_{1}, \boldsymbol{y}^{*}\right), \boldsymbol{x}_{2}, \hat{\boldsymbol{y}}_{2}, \hat{r}\left(\boldsymbol{y}_{2}, \boldsymbol{y}^{*}\right)\right\}$

作者在方程4中
$\max _{\theta} \mathbb{E}_{\boldsymbol{x}_{1}, \boldsymbol{y}_{1} \sim \pi_{\theta}(\cdot \mid \boldsymbol{x}), \boldsymbol{y}_{2} \sim \pi_{\theta}\left(\cdot \mid\left[\boldsymbol{x}_{1}, p_{1}\right]\right)}\left[\sum_{i=1}^{2} \hat{r}\left(\boldsymbol{y}_{i}, \boldsymbol{y}^{*}\right)-\beta_{1} D_{K L}\left(\pi_{\theta}\left(\cdot \mid \boldsymbol{x}_{i}\right)| | \pi_{\mathrm{ref}}\left(\cdot \mid \boldsymbol{x}_{i}\right)\right)\right]$
的第二次尝试中修改奖励̂ $\hat{r}\left(\boldsymbol{y}_{2}, \boldsymbol{y}^{*}\right)$ ，加入一个奖励
$\widehat{b}\left(\boldsymbol{y}_{2} \mid \boldsymbol{y}_{1}, \boldsymbol{y}^{*}\right):=\alpha \cdot\left(\hat{r}\left(y_{2}, y^{*}\right)-\widehat{r}\left(y_{1}, y^{*}\right)\right)$
其中 $\alpha$ 是一个理想情况下大于1.0的正常数乘数

在第二次尝试中加入这个额外奖励，通过仅强调那些改变响应正确性的转换来衡量进步的概念，并在第二次尝试中将正确响应变为不正确的转换上施加重负的惩罚
Adding thisbonus to the second attempt measures a notion of progress by only emphasizing transitions that flip thecorrectness of the response and assigns a heavy negative penalty to transitions that change a correctresponse to incorrect in the second attempt.
相当于如果第二次尝试与第一次尝试相比提高了正确性，则会在第二次尝试的奖励中添加奖励，而如果响应降低，则会施加惩罚

因此，加入这个额外奖励应该能够规范训练过程，使其不会崩溃到那个在训练集上看起来也是最优的“直接”解决方案上，而是学习自我纠正
Thus, the addition of this bonus should regularize thetraining process from collapsing on to the “direct” solution that also appears optimal on the training setbut does not learn self-correction.

这意味着模型被鼓励去探索和尝试不同的响应，即使这些尝试可能不是立即正确的，但它们有助于模型学习如何在后续的尝试中进行自我纠正和改进
且可以避免模型过早地收敛到一个固定的、可能无法适应新情况的解决方案上，而是鼓励模型发展出更加灵活和适应性强的策略

事实上，这篇论文的可读性也一般，我在Reddit看到了关于这篇论文的讨论：谷歌发布新论文：通过强化学习训练语言模型进行自我纠正，有兴趣的可以看看

第三部分对AlphaZero技术的借鉴：Self-play RL、MCTS

3.1 如何进一步加强推理能力：延长思考时间而非单纯增加模型参数

24年8月份，来自UC Berkeley、Google DeepMind的研究者发布的此篇论文《Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters》证明在加强模型的推理能力方面，延长思考时间比单纯增加模型参数更有效》

毕竟人类在面对相对复杂的问题时，也会花更长时间思考，以从长计议

3.1.1 如何最优地扩展测试时的计算

// 待更

3.1.2 训练易于搜索的验证器及针对PRM的搜索方法(Best-of-N、Beam Search、Lookahead Search)

论文中提到，他们首先训练易于搜索的验证器

在PRM训练的问题上，最初，PRM训练[22,42]使用了人类众包工人的标签。虽然Lightman等人[22]发布了他们的PRM训练数据（即PRM800k数据集），但作者发现这些数据在很大程度上对我们无效

他们发现，即使是最简单的策略，例如最佳N取样，也很容易利用在该数据集上训练的PRM。作者假设这可能是由于他们数据集中GPT-4生成样本与作者PaLM 2模型之间的分布偏移所致「We found that it was easy to exploit a PRM trained on this dataset via even naïve strategies such as best-of-N sampling. We hypothesize that this is likely a result of the distribution shift between the GPT-4 generated samples in their dataset and our PaLM 2 models」
总之，最终作者没有进行昂贵的过程来为他们Google的PaLM 2模型收集众包工人的PRM标签，而是采用了Wang等人[45]的的方法，在没有人工标注的情况下监督PRMs，使用通过从解决方案的每一步进行蒙特卡罗展开获得的每步正确性估计(we instead apply the approach of Wang et al. [45] to supervise PRMs without human labels, using estimates of per-step correctness obtained from running Monte Carlo rollouts from each step in the solution)
因此，作者的PRM的每步预测对应于基础模型采样策略的未来奖励的估计(Our PRM’s per-step predictions there fore correspond to value estimates of reward-to-go for the base model’ssampling policy)
其类似于最近的工作[31,45]，且他们还与ORM基线进行了比较，但发现我们的PRM始终优于ORM
因此，本节中的所有搜索实验均使用PRM模型。关于PRM训练的更多细节见附录D

其次在答案聚合问题上，他们在测试时，可以使用基于过程的验证器对从基础模型中采样的一组解决方案中的每个步骤进行评分(At test time, process-based verifiers can be used to score each individual step in aset of solutions sampled from the base model)

为了使用PRM选择最佳N个答案，需要一个函数来聚合每个答案的每个步骤得分，以确定正确答案的最佳候选者

为此，作者首先聚合每个答案的每个步骤得分，以获得完整答案的最终得分（逐步聚合）。然后，在答案之间进行聚合以确定最佳答案（答案间聚合）

具体来说，如下处理逐步和答案间聚合

逐步聚合
与其通过取乘积或最小值[22,45]来聚合每步得分，作者更倾向于使用PRM在最后一步的预测作为完整答案的得分
Rather than aggregating the per-step scores by taking the product orminimum [22, 45], we instead use the PRM’s prediction at the last step as the full-answer score.

因为，作者发现这在他们研究的所有聚合方法中表现最好（见附录E）
答案间聚合
作者遵循Li等人的方法[21]，应用“最佳N加权”选择而非标准的最佳N
最佳N加权选择在所有具有相同最终答案的解决方案中边缘化验证者的正确性分数，选择总和最大的最终答案
Best-of-N weighted selection marginalizes the verifier’s correctness scoresacross all solutions with the same final answer, selecting final answer with the greatest total sum

其次，在测试时通过搜索方法优化PRM

作者研究了三种搜索方法，这些方法从少样本提示的基础LLM中采样输出，下图展示了一个示例

第一，加权最佳-N：Best-of-N，从 N 个样本中选择最佳答案，并根据 PRM 最终得分选择最佳答案，如上图左侧所示

从基础LLM中独立采样N个答案，然后根据PRM的最终答案判断选择最佳答案

第二，束搜索：Beam Search，束搜索在每一步采样 N 个候选项，并根据 PRM 选择前 M 个继续搜索，如上图中部所示

束搜索通过搜索每一步的预测来优化PRM。他们的实现与BFS-V [10,48]相似

具体来说，作者考虑一个固定数量的束 $N$ (比如上图是4)和一个束宽度 $M$ (比如上图是2)，然后运行以下步骤：

为解决方案的第一步采样 $N$ 个初始预测
根据PRM预测的逐步奖励估算对生成的步骤进行评分（在此设置中，由于奖励是稀疏的，这也对应于前缀的总奖励
仅筛选出前 $\frac{N}{M}$ 得分最高的步骤(如上图中间部分所示，筛选出第一行的第2个、第4个)
现在从每个候选者中，从下一步中采样 $M$ 个提案，结果再次得到总计 $N / M \times M$ 个候选前缀(如上图中间部分所示，筛选出第二行的第1个、第4个，相当于在前两行中，有两束候选，一个是2-1，一个是4-4)
然后再次重复步骤2-4(在第三行时，最佳的两束候选是2-1-1,4-4-4，在第四行时，最佳的唯一一束候选是4-4-3-3)

通过运行此算法，直到找到一个解决方案或达到最大光束扩展轮数（在作者的情况下为40）。他们以N个最终答案候选结束搜索，并对其应用上述的最佳N加权选择来进行最终答案预测

第三，前瞻搜索：Lookahead Search，前瞻搜索将束搜索的每一步扩展为利用 k 步前瞻，同时评估要保留和继续搜索的步骤，如下图右侧所示

前瞻搜索修改了束搜索评估单个步骤的方式，它使用前瞻展开来提高每一步搜索过程中的PRM值估计的准确性

具体来说，在束搜索的每一步中，前瞻搜索不是使用当前步骤的PRM得分来选择TOP候选，而是进行模拟，展开到 $k$ 步，若达到解的终点则提前停止
at each step in the beam search, rather than using the PRM score at the current step to select the top candidates, lookahead search performs a simulation, rolling out up to 𝑘steps furtherwhile stopping early if the end of solution is reached.
为了最小化模拟展开中的方差，使用温度0进行展开。在此展开结束时PRM的预测用于为束搜索的当前步骤评分。换句话说，可以将束搜索视为 $k = 0$ 时前瞻搜索的一种特殊情况

给定一个准确的PRM，增加 $k$ 应该能在每步值估计的准确性上有所提升，当然，有得必有失，此举必然需要额外的计算
还需注意，这种版本的前瞻搜索是MCTS [38]的一种特殊情况，其中MCTS中设计用于促进探索的随机元素被移除，因为PRM已经训练完成且被冻结
Also note that this version of lookahead search is a special case of MCTS [38], where in the stochastic elements of MCTS, designed to facilitate exploration, are removed since the PRM is already trained and is frozen.

这些随机元素在学习值函数时非常有用（毕竟已经通过PRM学习了），但在想要利用而非探索的测试时刻则不太有用
These stochastic elements are largely useful for learning the value function (which we’ve already learned with our PRM),but less useful at test-time when we want to exploit rather than explore.

因此，前瞻搜索在很大程度上代表了MCTS风格方法在测试时的应用方式(Therefore, lookahead search islargely representative of how MCTS-style methods would be applied at test-time.)

3.2 如何让模型更高效的搜索可行性方案

2024年9月，《Planning In Natural Language Improves LLM Search For Code Generation》：这篇论文提出了PLANSEARCH算法，用于解决LLMs在推理时缺乏多样性导致搜索效率低下的问题

该算法通过生成多样化的观察，组合观察形成候选计划，并实现代码，从而在想法空间中增加多样性，显著提高了代码生成的性能

// 待更

3.3 AlphaZero与MCTS

《Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning》

《ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search》

AlphaZero论文为《Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm》

《Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training》

// 待更

3.4 阿里改进过程监督奖励PRM：将MC和LLM as a dudge结合

一般而言，基于蒙特卡罗MC估计的数据合成对于PRMs通常表现不佳，较于LLM-as-a-judge（Zheng etal.,2023）和人工注释，泛化能力较弱

MC估计依赖于完成模型来评估当前步骤的正确性，这可能导致基于错误的步骤生成正确答案，或基于正确的步骤生成错误答案，导致步骤验证不准确

此外，作者识别出传统的Best-of-N，即BoN评估策略在PRMs中的潜在偏差：

不可靠的策略模型生成的response虽然得到了正确答案但过程有缺陷，导致BoN的评估标准与PRM的过程验证目标不一致
有限的过程验证能力使得PRM对这些情况表现出容忍，导致BoN表现膨胀
现有PRMs的最低分数显著集中在最终答案步骤上，揭示了BoN优化PRMs中从过程到结果导向评估的转变

为了解决这些挑战，25年1.13日，来自Qwen Team, Alibaba Group的研究者Zhenru Zhang、Chujie Zheng、Yangzhen、Wu Beichen、Zhang Runji Lin、Bowen Yu∗、Dayiheng Liu∗、Jingren Zhou、Junyang Lin∗开发了一种共识过滤机制

其有效地将MC估计与LLM-作为-裁判结合，相当于该策略除了Rollout，还引入其它大模型作为判断者(LLM as a dudge)，两者评判一致才算数(即仅当LLM-as-a-judge和MC估计在解决方案中的错误推理步骤位置达成共识时)，才保留实例

如此，在克服MC的局限性的同时，也极大增强了PRM判断的准确性，并倡导一种更全面的评估框架，结合response级别和步骤级别的指标
基于这些机制，显著提高了BoN评估和逐步错误识别任务中的模型性能和数据效率
总之，他们发布了一种新的最先进的PRM，优于现有的开源替代方案，并为未来在构建过程监督模型方面的研究提供了实用指南
其对应的论文为《The Lessons of Developing Process Reward Models in Mathematical Reasoning》

// 待更

第四部分对OpenAI o1的复现与超越：微软rStar-Math

4.1 整体理解rStar-Math

4.1.1 通过PRM + MCTS实现对o1的高水平复刻

我之前还不知道这个模型，后来从张俊林的解读中看到的

才知道，25年1.8日，来自Microsoft Research Asia的研究者Xinyu Guan∗、Li Lyna Zhang∗、Yifei Liu、Ning Shang、Youran Sun、Yi Zhu、Fan Yang、Mao Yang提出了OpenAI o1的复刻模型rStar-Math，其对应的论文为《rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking》

rStar-Math旨在训练一个数学策略SLM和一个过程偏好模型PPM——来生成更高质量的训练数据，并将两者整合到蒙特卡罗树搜索MCTS中，以实现深度思考

其这两个模型的参数大小均为7B 如此较小的规模允许在可用硬件，例如 4×40GB A100 GPU 上进行广泛的MCTS回溯
其中数学策略模型SLM在测试时通过基于SLM的过程奖励模型进行搜索指导

且rStar-Math引入了三项创新以解决训练的挑战：

一种新颖的代码增强的CoT数据合成方法，通过执行广泛的MCTS展开来生成逐步验证的推理轨迹，用于训练策略SLM(SLM指的是较小的语言模型)

虽然MCST可以将复杂的数学问题分解为更简单的单步生成任务，但如张俊林所说，MCST很难做成功的最大阻碍是PRM不太好做，大家一般会模仿AlphaGo，到了某个推理中间步骤S，然后从S出发rollout出多条之后的推理轨迹，直到产生最终答案，然后看下从S出发的多个后续轨迹中，有多少导向了正确的最终答案，导向越多正确最终答案的则Reward越高

这种做法从思想上来看是非常合理的，但是问题在于：其实从S出发导向最终正确答案的rollout轨迹里，很多都包含中间推理过程的错误，导致如此评估出的Reward不准确(这个结论请参考上文1.3.2节的阿里改进PRM的工作)

总之，Reward是指导MCST搜索方向的重要信号，Reward不准自然导致搜出来的推理空间轨迹质量就不够高
故rStar-Math把推理轨迹改成代码的形式，这样可以通过程序验证筛掉不靠谱的路径，等于用代码验证的方式对搜索空间进行了剪枝，干掉了大量肯定错误的中间节点
一种新颖的过程奖励模型训练方法，避免了简单的步骤级评分注释，产生了更有效的过程偏好模型PPM
本质上讲，这个类似DPO的思路，引入正负例一起评估，评估的对象其实是从问题根结点出发，到S步骤之前所有推理步骤的质量

说白了，PPM利用了这样一个事实，即尽管critic网络给的Q-values仍然不够精确，无法通过广泛的MCTS回溯对每个推理步骤进行评分，但Q-values可以可靠地区分正面（正确）步骤和负面（无关/错误）步骤
因此，该训练方法基于Q-values为每个步骤构建偏好对，并使用成对排名损失[Ouyang et al., 2022]来优化PPM对每个推理步骤的评分预测，从而实现可靠的标记。该方法避免了直接使用Q-values作为奖励标签的传统方法[Luo et al., 2024, Chen et al., 2024]
4轮进化方案，从头开始逐步构建一个前沿策略模型和PPM，并迭代进化以不断提高推理能力
在每一轮中，我们使用最新的策略模型和PPM来执行MCTS
且过程中，使用上述两种方法生成越来越高质量的训练数据，以训练更强的策略模型和PPM用于下一轮
每一轮都实现渐进的改进：（1）更强的策略SLM，（2）更可靠的PPM，（3）通过PPM增强的MCTS生成更好的推理轨迹，以及（4）提高训练数据覆盖率以应对更具挑战性甚至比赛级别的数学问题

最终通过对747k数学问题进行数百万次合成解决方案的4轮自我进化，rStar-Math将SLMs的数学推理能力提升至最先进水平

在MATH基准测试中，它将Qwen2.5-Math-7B从58.8%提高到90.0%，将Phi3-mini-3.8B从41.4%提高到86.4%，分别超过o1-preview +4.5%和+0.9%
在美国数学奥林匹克（AIME）中，rStar-Math平均解决53.3%（8/15）的题目，跻身于最优秀的高中数学学生的前20%
代码和数据将可在https://github.com/microsoft/rStar 获得

4.1.2 提出背景与现有的挑战

自从o1模型推出以来，国内外便有大量的研究团队想对其复现，而复现的挑战也很明显，即关键是训练一个强大的策略模型来生成有前途的解题步骤和一个可靠的奖励模型来准确评估它们，这两者都依赖于高质量的训练数据

不幸的是，众所周知，现成的高质量数学推理数据稀缺，并且合成高质量数学数据面临基本挑战。对于策略模型来说，区分错误的推理步骤与正确的步骤具有挑战性，这使得消除低质量数据变得复杂
且值得注意的是，在数学推理中，正确的最终答案并不能确保整个推理过程的正确性 [Lanham et al.,2023]。错误的中间步骤会显著降低数据质量
至于奖励模型，虽然最近的工作包括用于验证的LLM-as-a-Judge [Zheng et al.,2023,Qi et al.,2024]和专门的奖励模型，如Outcome Reward Model [Yang et al.,2024,Yu et al.,2023a]，和Process Reward Model (PRM) [Lightmanet al.,2024]

过程奖励建模PRM通过对中间步骤提供细粒度反馈显示出巨大潜力——即PRM为复杂推理提供了有前途的密集、步骤级别的奖励信号[Luo etal.,2024,Wang et al.,2024c]，但收集步骤级别的注释仍然是一个障碍

且尽管Kang et al.[2024],Wang et al.[2024a]依赖于昂贵的人类注释数据集如PRM800k [Lightman etal.,2024]，最近的方法[Wang et al.,2024c,Luo et al.,2024]探索通过蒙特卡洛采样或MCTS进行自动化注释
然而，他们在生成精确的奖励分数方面仍然存在困难，这限制了性能提升

由于上述挑战，现有的基于蒸馏的数据合成方法用于训练策略模型，例如扩大 GPT4 蒸馏的 CoT 数据 [Tang etal.,2024,Huang et al.,2024]，已显示出收益递减，并且不能超过其教师模型的能力

rStar-Math引入了一种新颖的过程偏好奖励（PPM），消除了对准确步骤级别奖励分数注释的需求

总之，在此之前，训练可靠的 PRM 用于数学推理并不是一个很好解决的问题

4.2 rStar-Math的三大关键设计

4.2.1 步骤验证推理轨迹

给定一个问题x 和一个策略模型M，运行标准的MCTS 以逐步构建一个用于逐步解决方案探索的搜索树

如图1(a) 所示

根节点表示问题 $x$ ，而子节点对应于由M 生成的中间步骤 $s$ 。从根到叶节点终止于节点 $s_{d}$ 形成一个轨迹 $\mathbf{t}=x \oplus s_{1} \oplus s_{2} \oplus \ldots \oplus s_{d}$ ，每一步 $s_{i}$ 被分配一个Q 值 $Q\left(s_{i}\right)$
从搜索树T 中，提取解决方案轨迹 $\mathbb{T}=\left\{\mathbf{t}^{1}, \mathbf{t}^{2}, \ldots, \mathbf{t}^{n}\right\}(n \geq 1)$ ，目标是从T 中选择高质量的轨迹以构建训练集
为此，作者引入了代码增强的CoT 合成方法，以过滤掉低质量的生成，并执行广泛的回溯以提高Q 值精度的可靠性

如下图图2所示的一个例子，比尔向南走 $\frac{1}{2}$ 英里，然后向东走 $\frac{3}{4}$ 英里，最后又向南走 $\frac{1}{2}$ 英里。他与起点的直线距离是多少英里？请将你的答案以小数形式表示，保留到最接近的百分位

那怎么解出这个问题的答案呢，无非就是分成如下图所示的4步

策略模型生成一个步骤的NL CoT及其对应的Python代码，其中NLCoT被嵌入为Python注释。只有成功执行Python代码的生成才被保留为有效候选者

// 待更

4.2.2 过程偏好模型PPM

如之前所说，过程奖励模型提供了细粒度的步骤级奖励信号，对于解决复杂的数学问题是非常理想的。然而，获取高质量的步骤级训练数据仍然是一个未解决的挑战

现有方法依赖于人工标注[Lightman et al.,2023]或MCTS生成的分数[Zhang et al.,2024a,Chen etal.,2024]为每个步骤分配分数
这些分数随后作为训练目标，使用如MSE损失[Chen etal.,2024]或点损失[Wang et al.,2024c,Luo et al.,2024,Zhang et al.,2024a]等方法来最小化预测分数与标注分数之间的差异
因此，这些标注的步骤级奖励分数的精确性直接决定了所得过程奖励模型的有效性。不幸的是，精确的逐步评分仍然是一个未解决的挑战。尽管广泛的MCTS展开提高了Q值的可靠性，但精确评估细粒度的步骤质量仍然存在问题

例如，在一组正确的步骤中，很难将它们排名为最佳、次佳或一般，并分配精确的分数。同样，在错误的步骤中，区分最差和中等差的步骤也面临类似的挑战。即使是专家的人类注释在大规模时也难以保持一致性，从而导致训练标签中固有的噪声

如此，作者特地引入了通过“构建步骤级别的正负偏好对”来训练过程偏好模型PPM

如图1(b)所示

不是将Q值直接用作奖励标签，而是利用它们从MCTS树中选择步骤来构建偏好对

对于每个步骤，选择两个Q值最高的候选步骤作为正步骤，两个Q值最低的作为负步骤。关键是，所选的正步骤必须导向正确的最终答案，而负步骤则必须导向错误的答案
对于中间步骤（除最终答案步骤外），正负对共享相同的前导步骤
对于最终答案步骤，由于相同的推理轨迹很少产生不同的最终答案，于是选择两个平均Q值最高的正确轨迹作为正例，两个平均Q值最低的错误轨迹作为负例

根据[Ouyang et al.,2022，即instructGPT，详见此文《ChatGPT技术原理解析：从RL之PPO算法、RLHF到GPT4、instructGPT》的3.1.2 InstructGPT训练阶段2：如何对多个输出排序及如何训练RM模型]，使用标准的Bradley-Terry模型定义了损失函数，采用成对排名损失
$\mathcal{L}_{p p m}(\theta)=-\frac{1}{2 \times 2} E_{\left(x, y_{i}^{\text {pos }}, y_{i}^{n e g} \in \mathbb{D}\right)}\left[\log \left(\sigma\left(r_{\theta}\left(x, y_{i}^{\text {pos }}\right)-r_{\theta}\left(x, y_{i}^{\text {neg }}\right)\right)\right)\right]$

当 $i$ 不是最终答案步骤时， $y_{i}^{p o s}=s_{1} \oplus \ldots \oplus s_{i-1} \oplus s_{i}^{\text {pos }} ; y_{i}^{\text {neg }}=s_{1} \oplus \ldots \oplus s_{i-1} \oplus s_{i}^{\text {neg }}$
这里， $r_{\theta}\left(x, y_{i}\right)$ 表示PPM 的输出，其中 $x$ 是问题， $y$ 是从第一步到第 $i$ 步的轨迹

4.2.3 自我进化的深度思考：4轮迭代

// 待更

此外，超越o1还有另一个路径，即deepseek R1/Kimi K1.5，而这个路径的原理与实现，详见此文《一文速览DeepSeek R1：如何通过纯RL训练大模型的推理能力以比肩甚至超越OpenAI o1(含Kimi K1.5解读)》

当然了，除了rStar-Math和deepseek R1/Kimi K1.5，UCL、上交也对o1做了复刻

本文的修订完善记录

本文自10.12发布以来，一直在不断更新，12 13 14这三天没来得及记录，以下是从10.15日起的修订记录

2024年10.15，反复修订此节——2.1.2 Quiet-STaR: 语言模型可以教会自己在说话前思考
特别是逐行解读其伪代码
10.16，反复修订以下这两节的内容
2.2(选读) 如何让模型学会自我纠错——Recursive Introspection(简称RISE，类似STaR)
2.3 Self-Correct之SCoRe：通过多轮强化学习进行自我纠正
10.19，重新梳理全文结构(全文目录亦有调整)，比如新增一节：1.2 如何让模型学会分解问题
10.22，编写下面这几节
3.1.2 训练易于搜索的验证器及针对PRM的搜索方法(Best-of-N、Beam Search、Lookahead Search)
2025年1.15
因解读deepseek R1的过程中，再次注意到本文，更注意到了微软的rStar-Math

故修订第四部分的标题，如下
第四部分对OpenAI o1的复现与超越：微软rStar-Math
并开始更新第四部分

且新增一节
3.4 阿里改进过程监督奖励PRM：讲MC和LLM as a dudge结合
..