ReST-MCTS：通过过程奖励引导的树搜索实现LLM自训练
摘要
最近的大语言模型（LLM）自训练方法大多依赖于LLM生成响应，并过滤那些输出答案正确的样本作为训练数据。这种方法通常会产生低质量的微调训练集（例如，错误的计划或中间推理）。本文提出了一种基于过程奖励引导的树搜索MCTS的强化自训练方法，称为ReST-MCTS，用于收集更高质量的推理轨迹以及每一步的值，以训练策略模型和奖励模型。ReST-MCTS通过基于树搜索的强化学习绕过了通常用于训练过程奖励的每步手动标注：给定最终正确答案，ReST-MCTS能够通过估计该步骤有助于得出正确答案的概率来推断正确的过程奖励。这些推断的奖励具有双重作用：它们既作为进一步优化过程奖励模型的值目标，也用于选择高质量的轨迹进行策略模型的自训练。我们首先展示了ReST-MCTS中的树搜索策略在相同的搜索预算下，相较于之前的LLM推理基线（如Best-of-N和Tree-of-Thought）具有更高的准确性。然后，我们展示了通过使用该树搜索策略搜索到的轨迹作为训练数据，可以持续增强三个语言模型的性能，并在多次迭代中优于其他自训练算法，如 ReST({}^{\text{EM}})和Self-Rewarding LM。我们在https://github.com/THUDM/ReST-MCTS发布了所有代码。
1 引言
大语言模型（LLMs）大多是在人类生成的数据上进行训练的。但随着我们接近一个临界点，即网络上大多数高质量的人类生成文本已被爬取并用于LLM训练[1]，研究重点已转向使用LLM生成的内容进行自训练[2; 3; 4; 5; 6; 7]。与大多数强化学习（RL）问题类似，LLM自训练需要一个奖励信号。大多数现有的强化自改进方法（例如，STaR [4], RFT [5], ReST({}^{\text{EM}})[6], V-STaR [7]）假设可以访问一个真实的奖励模型（来自监督数据集的标签，或预训练的奖励模型）。这些方法使用LLM为每个问题生成多个样本，并假设导致高奖励（正确解决方案）的样本是高质量样本，随后在这些样本上进行训练（因此称为自训练）。这样的过程可以有效提高LLM的性能，在某些情况下可以解决基础LLM无法解决的任务[8; 9; 10]。
然而，上述过程的一个关键限制是，即使推理轨迹得出了正确的解决方案，也不一定意味着整个轨迹都是准确的。LLM经常生成错误或无用的中间推理步骤，但仍然偶然找到正确的解决方案[17]。因此，自训练数据集通常包含许多假阳性——中间推理轨迹或计划是错误的，但最终输出是正确的——这限制了LLM在复杂推理任务中的最终性能[18; 19]。解决这个问题的一种方法是使用值函数或奖励模型来验证推理轨迹的正确性（然后将其作为自训练的学习信号）[1; 12]。然而，训练一个可靠的奖励模型来验证推理轨迹中的每一步通常依赖于密集的人工生成标注（每个推理步骤）[1]，这种方法的扩展性较差。我们的研究旨在通过开发一种新方法来解决这一差距，该方法能够自动获取可靠的推理轨迹，并有效利用奖励信号进行验证。我们的关键研究问题是：如何自动获取高质量的推理轨迹，并有效处理奖励信号以进行验证和LLM自训练？
在本文中，我们提出了ReST-MCTS，这是一个使用基于模型的RL训练框架来训练LLM的方法。我们提出的方法使用改进的蒙特卡洛树搜索（MCTS）算法作为推理策略，记为MCTS，并由训练好的每步过程奖励（值）模型引导。我们方法的一个关键方面是能够通过执行足够多的rollout来自动生成每步的标签，用于训练每步的奖励模型。这个标注过程有效地过滤出具有最高质量的样本子集，而无需额外的人工干预。表1总结了我们的方法与之前方法的关键区别。我们通过实验验证了ReST-MCTS在发现良好推理轨迹方面优于之前的工作，例如在SciBench [20]和MATH [21]基准测试中，在相同的搜索预算下，ReST-MCTS优于Self-Consistency (SC)和Best-of-N (BoN)，从而带来了更好的自训练效果。
总结来说，我们的贡献如下：
- 我们提出了ReST-MCTS，这是一种通过MCTS搜索生成过程奖励的自训练方法。关键步骤是通过MCTS进行足够次数的rollout，自动标注每个中间节点的过程奖励。我们在多个推理基准上进行了验证，发现ReST-MCTS优于现有的自训练方法（例如，ReSTEM和Self-Rewarding），如表2所示，并且在推理策略（例如，CoT和ToT）上也表现更好，如表4所示。
- ReST-MCTS中的奖励生成器相较于之前的过程奖励生成技术（例如，MATH-SHEPHERD）生成了更高质量的过程奖励模型，如表3所示。
- 在相同的搜索预算下，ReST-MCTS中的搜索算法（MCTS）比Self-Consistency和Best-of-N具有更高的准确性，如图2所示。
2 推理与自训练的背景
我们遵循基于LLM的推理的标准设置。我们从策略$\pi$开始，该策略使用基础LLM实例化。给定输入问题$Q$，在最简单的情况下，$\pi$可以通过自回归预测下一个标记来生成输出序列或推理步骤的轨迹$(s_{1},s_{2},\cdots,s_{K})\sim\pi(\cdot|Q)$。为简单起见，我们假设一个推理步骤由单个句子组成（句子本身由多个标记组成）。我们还假设最后一个输出$s_{K}$是最终步骤。LLM也可以通过提示或条件来偏向生成某些轨迹。对于提示$c$，我们可以将策略写为$\pi(\cdot|Q,c)$。这个想法最著名的应用是思维链（CoT）[22]。
自我一致性（SC）。 自我一致性[23]从$\pi$中采样多个推理轨迹，并选择出现频率最高的最终答案。
树搜索与值函数。 另一个想法是使用树结构的推理轨迹[24; 14]，这些轨迹从中间推理步骤分支出来。使用所谓的树搜索推理算法的一个关键问题是需要一个值函数来引导否则组合爆炸的搜索过程[14]。两个常见的值函数包括结果奖励模型（ORMs）[25]，它仅在最终答案的正确性上进行训练，以及过程奖励模型（PRMs）[1]，它在每个推理步骤的正确性上进行训练。我们假设$r_{s_{k}}$是PRM在第$k$步的输出sigmoid分数。我们的ReST-MCTS方法使用树搜索自动学习一个好的PRM。
Best-of-N。 作为自我一致性的替代方案，还可以使用学习到的值函数（PRM或ORM）选择具有最高值的推理轨迹[1]。
自训练。 在高层次上，自训练[6; 12]有两个步骤。第一步是生成，我们使用$\pi$（在我们的例子中是树结构轨迹）采样多个推理轨迹。第二步是改进，在推理轨迹上构建学习信号，然后用于微调$\pi$。这个过程可以重复多次迭代。
先前工作的局限性。 进行可靠自训练的主要挑战是构建有用的学习信号。理想情况下，人们希望在每个中间推理步骤的正确性上有一个密集的学习信号，这由PRM提供。否则，使用稀疏的学习信号，人们会遭受类似于强化学习中的信用分配问题。历史上，学习PRM的主要挑战是缺乏每个推理步骤的监督标注。这是我们的ReST-MCTS方法旨在克服的主要挑战。我们在附录A中详细描述了初步内容。
3 ReST-MCTS方法
我们的方法ReST-MCTS如图1所示，并使用了四个主要组件开发。
- MCTS，它在PRM的指导下执行具有足够rollout次数的树搜索。
- 过程奖励模型（PRM），它评估任何部分解的质量并指导MCTS。
- 策略模型，它为每个问题生成多个中间推理步骤。
- LLM自训练，它使用MCTS收集推理轨迹，在正样本上训练策略模型，并在所有生成的轨迹上训练过程奖励模型。
基于搜索的LLM推理策略
部分解的值$v_{k}$。 部分解$p_{k}=[s_{1},s_{2},\cdots,s_{k}]$的值（过程）奖励$v_{k}$应满足以下基本质量：
- 有限范围：$v_{k}$被限制在特定范围内。此限制确保$v_{k}$的值是有界的，不会超过某个限制。
- 反映正确性的概率：$v_{k}$反映了部分解是完整且正确答案的概率。$v_{k}$的较高值表示质量更好或更接近正确答案的可能性更高。
- 反映解步骤的正确性和贡献：$v_{k}$结合了每个解步骤的正确性和贡献。从部分解开始时，正确的下一步应导致比错误步骤更高的$v_{k}$。此外，朝着最终答案做出更多正确推导的步骤应导致更高的$v_{k}$值。此属性确保$v_{k}$捕捉到朝着正确解决方案的增量进展，并奖励有助于解决方案整体正确性的步骤。
部分解的推理距离$m_{k}$。 为了估计解步骤的进展，我们将$p_{k}$的推理距离$m_{k}$定义为策略模型从$p_{k}$开始达到正确答案所需的最小推理步骤。推理距离反映了进展以及策略基于当前步骤找出正确答案的难度，因此可以进一步用于评估$p_{k}$的质量。然而，我们指出$m_{k}$不能直接计算。它更像是一个可以通过从$p_{k}$开始执行模拟或轨迹采样并找到发现正确答案的实际最小步骤来估计的隐藏变量。
单步的加权奖励$w_{s_{k}}$。 基于评估部分解的期望质量，我们引入了加权奖励的概念，以反映当前步骤$s_{k}$的质量，记为$w_{s_{k}}$。基于常见的PRM奖励$r_{s_{k}}$，$w_{s_{k}}$进一步将推理距离$m_{k}$作为权重因子，反映了$s_{k}$的增量进展。
质量值和加权奖励的表示。 为了确定步骤$k$处部分解的质量值$v_{k}$，我们结合了前一个质量值和当前步骤的加权奖励。通过考虑前一个质量值，我们考虑了到前一步为止的累积进展和正确性。因此，$v_{k}$可以迭代更新为：
$$ v_{k}=\left{\begin{array}{cc}0,&k=0\ max(v_{k-1}+w_{s_{k}},0),&else\end{array}\right. $$
当前步骤$s_{k}$的加权奖励$w_{s_{k}}$提供了该特定步骤对整体解决方案的质量和贡献的度量。基于$m_{k}$（其中$m_{k}=K-k$，$K$是解决方案$s$的总推理步骤数）、前一个质量值$v_{k-1}$和MATH-SHEPHERD [12]中的$r_{s_{k}}$，我们可以迭代更新加权奖励$w_{s_{k}}$的定义如下：
$$ w_{s_{k}}=\frac{1-v_{k-1}}{m_{k}+1}(1-2r_{s_{k}}),;;k=1,2,\cdots $$
随着$k$的增加，$m_{k}$减少，表明达到正确答案所需的推理步骤更少。这导致在当前步骤的加权奖励上放置更高的权重。我们还可以推导出$w_{s_{k}}$和$v_{k}$满足以下定理所示的期望有界性。
定理1（$w_{s_{k}}$和$v_{k}$的有界性）。 如果$r_{s_{k}}$是一个在$[0,1]$范围内的sigmoid分数，则如上定义的$w_{s_{k}}$和$v_{k}$满足以下有界性：$w_{s_{k}}\leq 1-v_{k-1}$，$v_{k}\in[0,1]$。
推导。 请参阅附录B.1中的详细推导。
因此，我们可以得出结论，$w_{s_{k}}$和$v_{k}$具有以下符合我们期望的性质：
观察1。 如果从$p_{k}$开始的推理路径需要更多步骤才能得到正确答案，则单步加权奖励$w_{s_{k}}$较低。
观察2。 $w_{s_{k}}$随着PRM预测的sigmoid分数$r_{s_{k}}$的增加而减少。因此，$w_{s_{k}}$与PRM对步骤正确性的预测呈正相关。
观察3。 $v_{k}\to 1\iff r_{s_{k}}\to 0,\ m_{k}=0$，即$v_{k}$仅在$s_{k}$达到正确答案时收敛到上限$1$。
基于$v_{k}$和$w_{s_{k}}$的特性，一旦我们有了精确的PRM和$m_{k}$的准确预测，就可以直接预测部分解的质量值并引导搜索。在我们的方法中，我们没有分别训练模型来预测$r_{s_{k}}$和$m_{k}$，而是简单地训练一个过程奖励模型$V_{\theta}$来预测$v_{k}$，作为常见PRM的变体。由于奖励已纳入$v_{k}$的计算中，因此无需单独训练奖励模型，从而节省了大量用于答案选择的精力。
过程奖励模型引导的树搜索MCTS。 像[24]和[26]这样的树搜索方法需要一个值函数和结果奖励模型$r_{\phi}$来修剪分支、评估最终解决方案并备份值。然而，使用ORM评估最终解决方案并回传意味着每个搜索轨迹必须完全生成，这既昂贵又低效。最近的工作[14]建议在MCTS中使用学习到的LLM值函数，以便备份过程可以在中间步骤中进行，而无需完全生成。他们的工作大大提高了搜索效率，但仍然依赖于ORM来选择最终答案。受这些工作的启发，我们进一步提出了一种新的MCTS变体，即MCTS，它使用质量值$v_{k}$作为训练好的LLM过程奖励模型的值目标，并指导MCTS。
鉴于上述特性，我们可以直接使用过程奖励模型$V_{\theta}$来评估任何部分解的质量，选择并在中间节点中回传。除了使用质量值外，我们还结合了一种特殊的蒙特卡洛rollout方法和自我批评机制，以提高效率和精度，这些在附录C.1中有详细解释。我们将MCTS表示为一个算法，每次迭代包括四个主要阶段，即节点选择、思维扩展、贪婪MC rollout和值回传。与常见的MCTS设置类似，该算法在每个科学推理问题$q$的搜索树$T_{q}$上运行。每个树节点$C$代表一系列思维或步骤，其中记录了部分解$p_{C}$、访问次数$n_{C}$和相应的质量值$v_{C}$。为简单起见，我们将每个节点表示为元组$C=(p_{C},n_{C},v_{C})$。MCTS的总体伪代码如算法2所示。
自训练管道
如图1所示，基于提出的树搜索算法MCTS，我们对推理策略和过程奖励模型进行自改进。在初始化策略$\pi$和过程奖励模型$V_{\theta}$后，我们迭代地使用它们，并利用过程中生成的搜索树$T_{q}$为特定科学或数学问题生成高质量解决方案，并进行自改进过程，称为ReST-MCTS。我们的工作受到MuZero [20]框架的启发，并将其应用于LLM的训练，我们称之为“MuZero风格的LLM学习”。
指令生成。 在此阶段，初始化从用于训练过程奖励模型$V_{\theta}$的原始数据集$D_{0}$开始。
收集过程奖励模型的过程奖励。 提取新的值数据相对复杂，我们从修剪后的搜索树$T^{\prime}{q}$上推导出每个树节点$C$的部分解的目标质量值，这些节点至少在一个正确的推理轨迹上（包括根节点）。我们首先根据$T^{\prime}$中达到正确答案所需的最小推理步骤计算每个树节点$C$的$m_{k}$。然后，我们使用[12]中的硬估计（HE）来计算$r_{s_{k}}$，即$r_{s_{k}}=1-r_{s_{k}}^{\text{HE}}$，这意味着如果推理步骤可以在$T^{\prime}{q}$中达到正确答案，则认为该步骤是正确的。使用$m$和$r_{s_{k}}$，我们能够推导出每个节点在或接近一个正确推理轨迹上的部分解的值。对于每个节点$C$（部分解$p_{C}=[s_{1},s_{2},\cdots,s_{k-1}]$）和相关的下一步$s_{k}$，我们可以使用公式(1)推导出值$v_{k}$，并使用公式(2)推导出加权奖励$w_{k}$，如果$r_{s_{k}}^{\text{HE}}=0$，则$m_{k}$设置为与$m_{k-1}$相同。图3展示了一个具体的推理过程示例。我们从根节点开始更新所有这些奖励和值，并收集所有$(Q,p,v)$对以形成第$i$次迭代中的$D_{V_{i}}$，用于在下一轮迭代中训练过程奖励模型。
收集策略模型的推理轨迹。 如图4所示，搜索过程生成一个搜索树$T_{q}$，其中包含多个推理轨迹。我们首先修剪所有未完成的分支（未达到最终答案的分支）。然后，我们通过简单的字符串匹配或LLM判断验证树搜索中获取的其他轨迹的最终答案，并选择正确的解决方案。这些经过验证的推理轨迹在第$i$次迭代中作为$D_{G_{i}(A_{j}=a^{})}|!|{N=1}^{N}$（其中$N$是采样解决方案的数量，$A$是第$j$个解决方案，$a^{}$是最终正确答案）用于提取新的训练数据以进行策略自改进。此过程随后通过公式(13)（$i\geq 1$）执行策略自训练。
过程奖励模型和策略模型的相互自训练。 与之前的工作（如ReSTEM [6]）相比，ReSTEM仅关注策略的自训练，并证明策略可以通过迭代生成新轨迹并从自身生成的高奖励轨迹中学习来改进，而我们的工作同时改进了过程奖励模型和策略模型的自训练。在过程奖励模型的训练集$D_{V_{0}}$初始化和新问题集$D_{G}$给定后，我们可以开始对$V_{\theta}$和$\pi$进行迭代自训练过程。我们使用$\pi$执行MCTS并为$D_{G}$生成解决方案，具体实现细节见第3.1节。在第$i$次（$i=1,2,\cdots$）迭代中，我们使用$D_{V_{i-1}}$训练$V_{\theta}$以获得$V_{i}$，并在$D_{G_{i}}$上训练策略模型$\pi_{S_{i-1}}$以生成新的生成器$\pi_{S_{i}}$。同时，$D_{G_{i}}$驱动$V_{i}$更新为$V_{i+1}$。我们在算法1中展示了过程奖励模型和策略模型相互补充的迭代自训练过程。
算法1 值模型和策略模型的相互自训练ReST-MCTS。
输入: 基础LLM $\pi$，策略模型的原始数据集$D_{S_{0}}$，值模型的原始数据集$D_{0}$，新问题集$D_{G}$，解决方案数量$N$，第$j$个解决方案$A_{j}$，正确答案$a^{}$，值模型$V_{\theta}$，加权值函数$w$，质量值函数$v$，迭代次数$T$。
输出: 自训练后的策略模型$\pi_{S_{T}}$和值模型$V_{T}$。
- $\pi_{S_{0}} \leftarrow \text{SFT}(\pi, D_{S_{0}})$ // 微调生成器
- $D_{V_{0}} \leftarrow \text{generate_value_data}(D_{0}, w, v)$ // 初始化值模型的训练集
- $V_{0} \leftarrow \text{train_value_model}(V_{\theta}, D_{V_{0}})$ // 初始化值模型
- for $i = 1$ to $T$ do
$D_{G_{i}} \leftarrow \text{generate\_policy\_data}(\pi_{S_{i-1}}, V_{i-1}\text{ guided MCTS}^{}, D_{G}, N)$ // 为策略模型生成合成数据for $j = 1$ to $N$ do$D_{G_{i}(A_{j}=a^{})} \leftarrow \text{label\_correctness}(D_{G_{i}})$ // 匹配并选择正确的解决方案$\pi_{S_{i}} \leftarrow \text{SFT}(\pi_{S_{i-1}}, D_{G_{i}(A_{j}=a^{})}|\!|_{N=1}^{N})$ // 自训练策略模型$D_{V_{i}} \leftarrow \text{extract\_value\_data}(D_{G_{i}})$ // 收集过程奖励并提取值数据- $V_{i} \leftarrow \text{train_value_model}(V_{i-1}, D_{V_{i}})$ // 自训练值模型
- return $\pi_{S_{T^{}}}, V_{T}$
4 实验
我们从三个角度验证ReST-MCTS：
- 自训练方法：使用生成的样本进行评估，并在多个迭代中进行比较，例如ReSTEM和Self-Rewarding，在三个LLM骨干上的分布内和分布外基准测试中，如表2所示。ReST-MCTS在每次迭代中优于现有方法，并通过其生成的数据持续自我改进。
- 过程奖励模型：与最先进的技术进行比较，例如MATH-SHEPHERD（MS）和SC + MS在GSM8K和MATH500上的表现，如表3所示。结果表明，ReST-MCTS学习到了一个良好的PRM，并且我们的奖励模型实现了更高的准确性。
- 树搜索策略：在大学级科学推理基准测试中与三种LLM进行比较，例如CoT和ToT，如表4所示。我们还在MATH和SciBench上在相同的搜索预算下进行评估，例如SC和Best-of-N，如图2所示。结果表明，尽管预算不足，ReST-MCTS显著优于其他基线。
4.1 值模型的初始化
为了从环境中获得准确的反馈，我们从一组选定的科学或数学问题$D_{0}$中构建值模型的初始训练集$D_{V_{0}}$，无需人工标注过程。然后，我们分别在ChatGLM3-6B [27; 28]和Mistral-7B [29]模型上进行微调，获得初始值模型，作为PRM的变体，指导LLM树搜索以生成更高质量的数学和科学问题解决方案。
科学和数学的细粒度数据集。 为了收集科学问题的值训练数据，我们将SelfInstruct [10]中的精简科学数据集$D_{sci}$整合到$D_{0}$中。该数据集包含11,554个问题，每个问题都配有一个正确的逐步解决方案。对于每个问题$q^{(i)}(i=1,2,\cdots,N)$和相应的解决方案$s^{(i)}=s^{(i)}{1,2,\cdots,K{i}}$，我们提取所有部分解以形成样本$d^{(i)}{k}=q^{(i)},s^{(i)}{1,2,\cdots,k}(p^{(i)})$。为了使值模型能够区分错误步骤，我们还使用了一个基本上无法处理此类难度推理任务的LLM策略（ChatGLM2），在给定$q^{(i)}$和$p^{(i)}$的情况下生成单步$s^{(i)}{k+1}$，获得新的部分解$p^{(i)}=[s^{(i)}{1,2,\cdots,k},s^{(i)}]$和新的样本$d^{(i)}{k,j}=q^{(i)},s^{(i)}{1,2,\cdots,k},s^{(i)}$。为简单起见，生成的步骤被视为错误。总共，我们收集了473.4k个样本用于训练初始值模型。之后，我们推导出所有样本$d^{(i)}$和$d^{(i)}{k}$的目标质量值，并使用它们构建$D{V_{0}}$，如附录B.1所示。我们采用另一种方法生成数学问题的值训练数据，如附录B.1所示。
4.2 评估ReST-MCTS的自改进
为了全面检查ReST-MCTS自训练对不同骨干的影响，我们执行了2次自训练迭代，并比较了两个代表性的自训练方法，ReSTEM（将结果奖励与真实答案进行比较）和Self-Rewarding（由LLM判断结果奖励），在三个基础模型上，即LLaMA-3-8B-Instruct [30]、Mistral-7B: MetaMATH [29; 31]和SciGLM-6B [10]。主要结果如表2所示。关于样本生成的数据集，由于我们主要关注ReST-MCTS在特定领域中的持续改进能力，我们主要在数据集中包含数学问题。为简单起见，我们在每次迭代中使用相同的数据集$D_{G}$。它涉及从MATH、GSM8K和TheoremQA [32]等知名基准的训练集中选择的问题。通过在$D_{G}$生成的样本上同时训练策略和值模型，我们观察到我们的自训练范式能够在分布内和分布外基准上持续增强两个模型的能力，无论使用哪种骨干。
策略模型的迭代性能改进。 之前的LLM自训练方法大多依赖于LLM生成响应，并假设每个问题的正确答案是高质量样本，而中间推理步骤在许多情况下是错误的或无用的。因此，我们通过在不同奖励（值）监督策略下生成新样本来比较ReST-MCTS与最近的自训练范式。对于ReSTEM和Self-Rewarding，默认的采样策略是生成CoT数据，并根据真实答案或策略提供的奖励对生成的数据进行精炼。相比之下，ReST-MCTS通过MCTS生成数据样本，并根据质量值和真实答案对数据进行精炼。表2中的结果表明，所有三个骨干都可以通过使用ReST-MCTS作为范式，通过自身生成的数据持续自我改进。ReST-MCTS在每次迭代中基本上都优于之前的自训练方法ReSTEM和Self-Rewarding。这意味着ReST-MCTS可以筛选出更高质量的自生成数据以进行更好的自我改进。
奖励模型的迭代性能改进。 我们还比较了我们的迭代训练策略和值模型如何在相同的令牌使用下改进MATH [33]测试集上的整体搜索结果。实现细节见附录E.3。我们在图2（a）中展示了结果，其中ReST-MCTS（迭代#1）大大优于大多数基线，但并未完全超越Self-Consistency。相比之下，经过更多次自训练迭代后，基于增强值模型的验证基本上在每个点上优于Self-Consistency，达到了48.5%的最高准确率，显著超过了Self-Consistency的42.5%。这表明了我们的自训练管道的有效性。
4.3 评估ReST-MCTS的奖励引导和推理策略
我们在本文中的主要假设是，获得更高质量轨迹的更好搜索策略可以改进自训练。在本节中，我们主要关注我们的过程奖励引导的MCTS是否能够在不同的推理任务中获得改进，以获得更好的样本。我们首先在表3中评估值模型本身的有效性，然后在表4中评估不同推理策略的性能。
各种验证模型的性能比较。 如[1]所建议的，不同的值模型或奖励模型在准确性和精细度上有所不同。我们使用多个奖励模型和验证方法对GSM8K和MATH500的问题进行了测试。值得注意的是，我们包括了MATH-SHEPHERD（MS）[12]的相同实验设置作为比较，因为它也采用了自动训练数据生成方法用于奖励模型。对于SC+ReST-MCTS，我们使用与MS相同的CoT采样策略，只是SC是根据我们自己的值模型的输出而不是MS的奖励模型执行的，这使得这是一个不同奖励模型训练方法的直接比较。我们记录了Mistral-7B: MetaMATH在选定测试集上的模型准确率，如表3所示。结果表明，与MS和SC+MS相比，SC+ReST-MCTS（值）在GSM8K和MATH上的解决方案准确率表现出更高的提升。这证实了我们值模型的有效性，进一步表明我们对质量值和加权奖励的定义是有效的，甚至可能更好。
相同搜索预算下的性能比较。 尽管基于MCTS的搜索方法在模型性能上表现出显著改进，但它们通常需要大量的令牌输入和完成，这使得在某些情况下成本相当高。因此，我们进行了更多实验，以研究搜索令牌预算与模型性能之间的关系，比较ReST-MCTS和用于MATH的相同基线，这些基线在附录E.3中有详细说明。由于我们的自训练过程主要在数学数据上进行，因此在这种情况下我们不考虑自训练的影响。然而，我们指出，这仍然可以作为自训练范式的迁移学习研究进一步探讨。图2（b）显示了当完成预算变化时，不同方法在SciBench上的准确率。结果表明，尽管预算不足，ReST-MCTS大大优于其他基线。我们注意到，尽管基于CoT的方法可以通过增加样本预算大大提高，但它们往往很快收敛到一个有限的准确率，这不如ReST-MCTS令人满意。
不同推理策略在基准测试中的性能比较。 为了评估ReST-MCTS的有效性，我们在SciBench [34]和SciEval [35]上进行了基准实验。所有基准设置见附录E.2。对于模型骨干，我们包括了大规模模型GLM4和GPT-3.5-turbo（均为API），以及一个小规模模型LLaMA2-13B-Chat。如表4所示，实验重复2次，我们报告了3种方法在10个科目上的平均准确率（%）。关于整体准确率，ReST-MCTS在所有3个模型上优于其他基线，GLM4提高了4.0%，GPT-3.5-turbo提高了3.1%。在特定科目如chemmc、quan和stat上，ReST-MCTS实现了超过5.0%的显著改进，表明其在发现准确解决方案方面的巨大潜力。此外，我们注意到我们的ToT基线在许多科目上也表现良好，有时甚至超过了ReST-MCTS。这反映了我们的值模型可以为基于树搜索的方法提供适当的指导。我们还发现，对于LLaMA2-13B-Chat，改进并不十分显著。这表明小规模策略在采用复杂的树搜索方法时可能面临困难，因为它们的逐步推理能力相对较低。
5 相关工作
5.1 大语言模型训练
大语言模型（LLMs）[36, 37, 38]在各种自然语言任务中取得了显著成功。最近的研究集中在提高LLMs的推理能力，包括收集高质量或更大规模的领域特定数据[39, 40, 41, 42, 10, 43]，设计精细的提示[22, 44, 45, 46]，或训练监督学习[10, 31, 32, 47]或强化学习（RL）[48, 49, 50, 16]。当LLMs使用RL算法进行训练时，LLMs的生成可以自然地表示为马尔可夫决策过程（MDP），并针对特定目标进行优化。根据这一公式，InstructGPT [51]通过利用人类反馈的强化学习（RLHF）[52]在优化LLMs以符合人类偏好方面取得了显著成功。RLAIF随后使用AI反馈扩展了从人类反馈的强化学习[53]。我们的工作旨在提出一种通过过程奖励引导的树搜索进行LLM自训练的方法。
5.2 大语言模型推理
LLM推理算法包括基于提示的思维链（CoT）[22]，基于规划的树思维（ToT）[24]。科学推理有几个类别，以挖掘现有大语言模型的潜力，从而在问题解决中产生不同的表现。以前的研究试图超越直接生成。例如，在本文[54]中，提出了一种逐步生成解决方案的方法，使用另一个模型或函数选择排名靠前的答案，并通过将输出限制在更窄的集合中来避免幻觉。[55]提出了一种启发式提示推理方法，可以生成各种假设的溯因解释，消除矛盾的候选者，并实现逻辑一致的推理。思维链（CoT）[22]模仿人类的思维过程，提供逐步解决方案。自我一致性CoT [23]通过从LM中采样多个解释并选择出现频率最高的最终答案来提高答案的可靠性和自我一致性。树思维（ToT）[24]进一步推广了CoT方法，通过考虑树中的多个不同推理路径并探索连贯的思维单元来执行深思熟虑的决策。在我们的工作中，我们对硬科学推理任务进行了基准测试[22, 24, 34, 35]。
6 结论
在本文中，我们提出了ReST-MCTS，通过奖励引导的树搜索生成高质量样本来自训练策略和过程奖励模型。从前一次迭代中推断出的奖励能够精炼过程奖励模型，并使用高质量轨迹自训练策略模型。实验结果表明，ReST-MCTS优于其他自训练范式，并在相同的搜索预算下实现了比之前推理基线更高的准确性。
局限性： 我们在附录H部分详细讨论了局限性。总结来说，我们需要展示ReST-MCTS可以推广到数学之外的其他推理任务（如编码、代理等）；以及没有真实答案的任务（对话、SWE-Bench [56]等）。我们还需要扩展所提出的值模型，并进一步改进数据过滤技术。一个潜在的想法是结合在线RL算法，以帮助更好地自训练值模型和策略模型。
附录
附录A 预备知识
在本节中，我们简要描述了LLM推理、奖励验证和LLM自训练。符号的定义见表5，模型比较见图6。
A.1 LLM推理
推理方法的使用可以显著提高LLM的解决问题的能力[10]。给定一个策略模型$\pi$（一个自回归预训练语言模型）和一个输入问题$Q$，$\pi$可以通过自回归生成输出序列$s = (s_{1}, s_{2}, \cdots, s_{K})$，通过预测下一个标记。生成完整输出序列的条件概率分布为：
$$ \pi(s|Q) = \prod_{k=1}^{K} \pi(s_{t}|s_{<t}, Q). $$
任何问题都可以通过零样本提示、少样本提示[57]、思维链（CoT）[22]、自我一致性CoT [23]或Best-of-N（BoN）选择[1]、树思维（ToT）[24]、蒙特卡洛树搜索（MCTS）[14]、图思维（GoT）[58]等方法进行推理。通常，最近的研究以CoT [22]为代表，旨在提高整体性能，如下所示：
$$ P_{\pi}(A=a^{}\mid Q)=\mathbb{E}{(s,s_{1},\cdots,s_{K})\sim P_{\pi}(s|Q)} \Big{[}P(A=a^{}\mid s_{0},s_{1},\cdots,s_{K},Q)\Big{]}. $$
我们通常将每个轨迹$(s_{1}, s_{2}, \cdots, s_{K})$称为推理轨迹。$P(A=a^{}\mid s_{0}, s_{1}, \ldots, s_{K}, Q)$是在给定问题$Q$和推理轨迹$s$的情况下获得正确答案$a^{}$的概率。给定原始训练数据集$D={Q_{1}, Q_{2}, \cdots, Q_{M}}$，可以通过使用上述推理策略对每个问题$Q$采样$\pi$ $N$次来生成新的数据集：
$$ D_{S_{0}}={(Q^{j}{1}, s^{j})|{j=1}^{N}, \cdots, (Q^{j}, s^{j}{M})|^{N}}. $$
如表1所示，STaR [4]、RFT [5]、ReSTEM [6]、V-STaR [7]和Self-Rewarding [16]采用了CoT提示。Step-by-step [1]和MATH-SHEPHERD [12]利用Best-of-N选择作为推理评估策略。TS-LLM [14]使用MCTS作为推理策略来完全生成轨迹。我们的工作同样寻求正确的推理路径以最大化期望的累积$P$。
A.2 奖励验证
在LLM的背景下，我们假设推理轨迹来自策略模型$\pi$的采样。自训练方法的常见第一步是在原始数据集$D_{S_{0}}$上微调基础模型$\pi$，并获得新的生成器$\pi_{S_{0}}$。此外，奖励$r$用于评估历史轨迹的价值。具有奖励$r(Q, s)$的强化学习（RL）目标为：
$$ \mathcal{L}{\text{RL}}=\mathbb{E}{Q\in D_{S_{0}}}\big{[}\mathbb{E}_{s\in\pi(s|Q)}[r(Q, s)]\big{]}. $$
最近的工作[1; 12]通过PRM和ORM，将推理的目标建模为搜索以找到问题$Q$的最高累积奖励轨迹$s$，并推断最终答案$A$。
- ORM（$D\times S\rightarrow\mathbb{R}$）使用交叉熵损失进行训练：
$$ \mathcal{L}{\text{ORM}}=A\text{log},r_{s}+(1-A_{s}),\text{log}(1-r_{s}), $$
其中$A_{s}$是正确答案（如果$s$正确则$A_{s}=1$，否则$A_{s}=0$），$r_{s}$是ORM的输出sigmoid分数。STaR [4]、RFT [5]和ReSTEM [6]将结果奖励视为值标签$A_{s}$，与真实答案进行比较。在V-STaR[7]中，其结果奖励由多次迭代的LLM生成，奖励$r$通过验证器$\pi_{V}$和LLM生成器$\pi_{S_{0}}$定义如下：
$$ r(Q, s)=\beta,\text{log},\frac{\pi_{V}(s|Q)}{\pi_{S_{0}}(s|Q)}. $$
$\beta$是控制参考策略$\pi_{S_{0}}$接近度的超参数。与V-STaR不同，Self-Rewarding [16]中的结果奖励$r$是通过LLM-as-a-Judge提示生成的，使用数据集$D_{S_{0}}$和策略模型$\pi_{S_{0}}$。在V-STaR和Self-Rewarding中，收集的$D_{\text{VER}}$用于训练验证器，如下所示：
$$ D_{\text{VER}}={(Q_{j}, s^{+}{j,1}, s^{-}), \cdots, (Q_{j}, s^{+}{j,d}, s^{-})}^{N}_{j=1}, $$
$d$是偏好对的数量。然而，之前的工作[1; 12]表明，PRM在假阳性解决方案中表现出比ORM更好的监督，并提供更可靠的反馈。
- PRM（$D\times S\rightarrow\mathbb{R}^{+}$）使用以下公式进行训练：
$$ \mathcal{L}{\text{PRM}}=\sum^{K} A_{s_{k}}\log r_{s_{k}}+(1-A_{s_{k}}),\log(1-r_{s_{k}}), $$
其中$A_{s_{k}}$是$s_{k}$的正确答案（如果$s_{k}$正确则$A_{s_{k}}=1$，否则$A_{s_{k}}=0$），$r_{s_{k}}$是PRM的输出sigmoid分数。具体来说，[1]将PRM训练视为一个三分类问题，并需要昂贵的人工标注。类似地，MATH-SHEPHERD [12]通过BoN推理策略收集随机rollout轨迹，并自动合成过程奖励以构建PRM训练数据集。MATH-SHEPHERD通过硬估计（HE）和软估计（SE）定义了每个推理步骤$s_{k}$的自动化质量$r_{s_{k}}$，即：
$$ A^{\text{HE}}{s{k}}=\left{\begin{array}{ll}1,&\exists A_{j}\in A^{},A_{j}=a^{}\0,&\text{Otherwise}\end{array}\right., $$
和
$$ A^{\text{SE}}{s{k}}=\frac{\Sigma^{N}{j=1}[(A=a^{*})}{N}. $$
$A^{*}={A_{j}}^{N}_{j=1}$，$N$是解决方案的数量。为了更精确地找到具有最高期望奖励的推理轨迹，RAP [59]使用MCTS通过状态-动作函数（$\mathcal{Q}:S\times\mathcal{A}\longmapsto\mathbb{R}$）估计每个节点的期望未来奖励。然而，将MCTS纳入LLM的解码过程是昂贵的，因为估计和更新状态-动作函数需要递归访问，并且奖励值需要通过LLM计算。并发工作pDPO [13]虽然有效，但没有考虑LLM生成的内部准确性，并忽略了要生成的步骤数量。在本文中，我们将过程奖励引导与树搜索相结合，以探索高效的解决方案空间并合成高质量的轨迹。
A.3 LLM自训练
生成。 给定一个新的训练数据集$D_{G}$，自训练方法使用生成器$\pi_{S_{0}}$为每个问题$Q$生成推理步骤$s$和最终答案$A$。在每次迭代$i$（$i\geq 1$）中，STaR、RFT和ReSTEM检查生成的解决方案$D_{G_{i}}$，并使用二元正确性标签$z$，保留正确的解决方案$(A_{j}=a^{})|^{N}{j=1}$作为$D(A_{j}=a^{})}|^{N}{j=1}$。基于对正样本的连续迭代，V-STaR和Self-Rewarding保留每个问题$Q$的正确和错误生成的解决方案，并在构建的验证器数据$D{\text{VER}}$上训练偏好数据对，使用所有数据$D_{G_{i}}$，以便$\pi_{V}$可以学习生成器在每次迭代$i$中产生的错误模式。然后，生成器$\pi_{S_{i-1}}$（这里是$\pi_{S_{0}}$）在新的生成数据集$D_{G_{i}(A_{j}=a^{*})}|^{N}{j=1}$上进行微调，并再次更新为生成器$\pi{S_{i}}$。这个过程在后续迭代中持续运行。它们的迭代过程和奖励值如下：
$$ D_{S_{0}}\xrightarrow{\pi}\pi_{S_{0}}\xrightarrow{D_{G_{i}}}D_{G_{i}(A_{j}=a^{*})}\xrightarrow{\pi_{S_{i-1}}}\pi_{S_{i}}, $$
其中$i=1$用于RFT，$i\geq 1$用于STaR、ReSTEM、V-STaR和Self-Rewarding。
改进。 在$D_{S_{0}}$上完成推理任务的实际方法是通过监督微调（SFT）训练策略模型，通过在训练数据集上最小化负对数似然损失：
$$ \mathcal{L}{\text{SFT}}(\pi)=-\mathbb{E}{(Q, s)\in D_{S_{0}}}\big{[}\sum_{t=1}^{T}\log\pi(s_{t}|s_{<t}, Q)\big{]}. $$
最近的离线偏好学习方法用DPO [50]替换了LLM验证器（在LLM生成器和二元分类之前训练）。验证器$\pi_{V}$的DPO训练目标如下：
$$ \mathcal{L}{\text{DPO}}(\pi;\pi_{S_{0}})=-\mathbb{E}{(Q, s^{+}, s^{-})\sim D{\text{VER}}}\big{[}\log\sigma(r(Q, s^{+})-r(Q, s^{-}))\big{]}, $$
其中$\sigma$是逻辑函数。
附录B 推导演示
B.1 加权值和质量值的定义
加权值。 回顾加权奖励的定义：
$$ w_{s_{k}}=\frac{1-v_{k-1}}{m_{k}+1}(1-2r_{s_{k}}),;;k=1,2,\cdots $$
我们知道$r_{s_{k}}\in[0,1]$。现在，让我们检查项$(1-2r_{s_{k}})$的最大可能值。由于$r_{s_{k}}\in[0,1]$，$(1-2r_{s_{k}})$的最大值出现在$r_{s_{k}}=0$时。在这种情况下，$(1-2r_{s_{k}})=1$。因此，我们可以得出结论：$-1\leq(1-2r_{s_{k}})\leq1$。
接下来，考虑分母$(m_{k}+1)$。由于$m_{k}=K-k$，且$K\geq k$，我们有$m_{k}\geq0$和$m_{k}+1\geq1$。因此，我们可以得出结论：$(m_{k}+1)\geq1$。
结合这些结果，我们可以将加权奖励重写如下：
$$ w_{s_{k}}=\frac{1-v_{k-1}}{m_{k}+1}(1-2r_{s_{k}})\leq|1-v_{k-1}|\cdot|1-2r_{s_{k}}|\leq|1-v_{k-1}| $$
因此，我们推导出$w_{s_{k}}\leq|1-v_{k-1}|$，这表明加权奖励受1与前一个质量值之差的绝对值限制。
质量值。 回顾质量值$v_{k}$是通过结合前一个质量值$v_{k-1}$和当前步骤的加权奖励$w_{s_{k}}$来确定的。
$$ v_{k}=max(v_{k-1}+w_{s_{k}},0) $$
现在，我们可以归纳得出结论$v_{k}\in[0,1]$，从$v_{0}=0$开始。假设$v_{k-1}\in[0,1]$，那么我们可以使用$w_{s_{k}}$的界限推导出$v_{k}\in[0,1]$。
$$ v_{k}=max(v_{k-1}+w_{s_{k}},0)\leq v_{k-1}+|1-v_{k-1}|=1 $$
因此，基于加权奖励的性质和质量值的定义，我们可以推导出$v_{k}$确实被限制在$[0,1]$范围内，$k=0,1,2,\cdots$。
数学的细粒度数据集。 我们采用另一种方法生成数学问题的值训练数据。对于这种方法，我们只需要每个问题$q$的正确答案$a_{}$，这更容易满足。具体来说，我们将MATH [33]训练集整合到$D_{0}$中。对于每个问题$q^{(i)}$和答案$a_{}^{(i)}$，我们使用Mistral-7B: MetaMATH [31]作为策略，以简单的广度优先搜索（BFS）方式生成解决方案轨迹，获得类似于自训练过程的搜索树$T_{q}^{(i)}$。随后，我们根据$a_{*}^{(i)}$验证$T_{q}^{(i)}$的所有叶节点的答案。验证后的搜索树用于推导$D_{V_{0}}$的数据样本及其目标值。
- 值模型训练集的构建。 之前的方法如[1]使用PRM通常需要人工标注来初始化训练集，这相当昂贵。相比之下，我们的值模型的初始训练集可以以较低的成本构建。
对于数学数据，我们采用与第3.2节中提到的相同方法来推断验证搜索树$T_{q}^{(i)}$中部分解的过程奖励和质量值。而对于科学数据，这个值推断过程略有不同。我们仍然基于公式(1)和公式(2)中的定义推导$p_{k}^{(i)}$的目标值。假设原始解决方案是可靠且简洁的，我们可以简单地将$s^{(i)}$视为$q^{(i)}$的全局最优推理路径。因此，我们推导出：
$$ r_{s_{k}}^{(i)}=0,m_{k}^{(i)}=K_{i}-k,w_{k}^{(i)}=\frac{1}{K_{i}}\text{和}v_{k}^{(i)}=\frac{k}{K_{i}}. $$
推导。 请参阅附录B.2中公式(20)的详细推导。
相反，对于生成的错误样本，我们设置$r_{s_{k+1}}^{(i)}=1$，$m_{k+1}^{(i)}=K_{i}-k$（因为仍然需要$K_{i}-k$个正确的推理步骤才能达到最终答案）。考虑到$v_{k}^{(i)}=\frac{k}{K_{i}}$，我们有：
$$ w_{k+1}^{(i)}=-\frac{K_{i}-k}{K_{i}-k+1}\frac{1}{K_{i}}, $$
$$ v_{k+1}^{(i)^{\prime}}=\max(0,\frac{k-1}{K_{i}}+\frac{1}{K_{i}\cdot(K_{i}-k+1)}). $$
推导。 请参阅附录B.2中公式(21)和公式(22)的详细推导。
收集所有样本及其相应的推导质量值，我们获得了值模型$V_{\theta}$的初始训练集$D_{V_{0}}$，如附录E.1所述。
B.2 加权值和质量值的详细推导
在这里，我们使用公式(2)推导加权奖励，并使用公式(1)推导质量值：
当$k=0$时：
$$ v_{0}=0 $$
当$k=1$时：
$$ w_{1}=\frac{1-0}{K-1+1}(1-2\times0)=\frac{1}{K} $$
$$ v_{1}=\max(0+\frac{1}{K},0)=\frac{1}{K} $$
当$k=2$时：
$$ w_{2}=\frac{1-\frac{1}{K}}{K-2+1}(1-2\times0)=\frac{K-1}{K(K-1)}=\frac{1}{K} $$
$$ v_{2}=\max(\frac{1}{K}+\frac{1}{K},0)=\frac{2}{K} $$
因此，
$$ w_{k}=\frac{1}{K},w_{k-1}=\frac{1}{K},w_{k+1}=\frac{1}{K} $$
$$ v_{k}=\frac{k}{K},v_{k-1}=\frac{k-1}{K},v_{k+1}=\frac{k+1}{K} $$
$$ m_{k}=K-k,m_{k-1}=K-k+1,m_{k+1}=K-k-1. $$
然后，我们推导公式(21)和公式(22)：
$$ w_{k+1} =\frac{1-v_{k}}{m_{k+1}+1}(1-2r_{s_{k+1}}) $$
$$ =\frac{1-\frac{k}{K}}{(K-k)+1}(1-2\times1) $$
$$ =-\frac{K-k}{K(K-k+1)} $$
$$ =-\frac{1}{K}\frac{K-k}{K-k+1} $$
$$ v_{k+1} =\max(v_{k}+w_{k+1},0) $$
$$ =\max(\frac{k}{K}-\frac{1}{K}\frac{K-k}{K-k+1},0) $$
$$ =\max(\frac{k(K-k+1)-(K-k)}{K(K-k+1)},0) $$
$$ =\max(\frac{k(K-k+1)-(K-k+1)+1}{K(K-k+1)},0) $$
$$ =\max(\frac{(K-k+1)(k-1)+1}{K(K-k+1)},0) $$
$$ =\max(\frac{(K-k+1)(k-1)}{K(K-k+1)}+\frac{1}{K(K-k+1)},0) $$
$$ =\max(\frac{k-1}{K}+\frac{1}{K(K-k+1)},0) $$
附录C 算法细节和过程示例
C.1 MCTS*的算法细节
节点选择。 类似于[14]，我们建议从初始根开始每次选择过程，因为这允许回溯。在每次迭代中，首先执行节点选择阶段，从初始根开始分层选择叶节点$C_{select}$。为了结合节点的质量值，我们使用UCB作为选择子节点的标准，而不是UCT [26]，如下所示：
$$ UCB(C)=v_{C}+\epsilon\sqrt{\frac{\ln n_{parent}}{n_{C}}}, $$
其中$n_{parent}$是$C$的父节点的访问次数，$\epsilon$是探索常数。对于每个中间节点，我们选择具有最大UCB的子节点。此标准考虑了质量值和访问次数，因此鼓励探索高质量节点，同时为未充分探索的节点留出机会。
思维扩展。 其次，将所选节点$C_{select}$的值与阈值$l$（在我们的实验中，$l$设置为$0.9$）进行比较。如果$v_{C_{select}}>=l$，则节点的记录部分解$p_{C_{select}}=[s_{1},s_{2},\cdots,s_{k}]$被视为可接受的最终解决方案（因为$v_{C}$仅在$C$接近正确答案时接近$1$），然后直接返回作为输出，终止算法。这与[60]采用的方法不同，因为不需要奖励模型估计。否则，启动扩展阶段，其中通过提示策略$\pi_{S_{0}}$采样新的解决方案步骤$s_{k+1,i}(i=1,2,\cdots,b)$，即$s_{k+1,i}\sim\pi_{S_{0}}(s_{1,2},\ldots,k|q)$，$b$是样本或分支的数量。随后，将新节点$C_{i}=([s_{1},s_{2},\cdots,s_{k},s_{k+1,i}],0,v_{C_{i}})$添加到$T_{q}$中，$v_{C_{i}}$由值模型分配，$v_{C_{i}}\gets V_{\theta}(p_{C_{i}}|q)$。请注意，我们还将自我批评机制纳入此扩展过程，稍后将进行说明。
贪婪MC Rollout。 [60]和[14]使用简化的三阶段迭代，不包括对叶节点的模拟过程。相比之下，我们认为模拟过程仍然为值估计带来有用的信息，尽管生成和时间成本增加。在此阶段，我们建议在新节点$C_{i}$上模拟几步，具有最大预测值。从该节点开始的推理步骤将逐步采样和评估，同时仅进一步探索最有价值的路径，直到达到步骤限制$m$。在采样过程中获得的最高质量值$v_{max}$被记录，并使用权重参数$\alpha$更新$v_{C_{i}}$，如下所示：
$$ v_{C_{i}}\leftarrow\alpha v_{C_{i}}+(1-\alpha)v_{max}. $$
此外，访问计数$n_{C_{i}}$也通过$n_{C_{i}}\gets n_{C_{i}}+1$更新。
值回传。 最后，我们从$C_{select}$开始进行值备份。$C_{select}$的每个父节点的值使用加权平均方法更新。对于从根到$C_{select}$的轨迹上的每个节点$C$，我们更新其$n_{C}$和$v_{C}$如下：
$$ n_{C}\gets n_{C}+1 $$
$$ v_{C}\gets\frac{n_{C}-1}{n_{C}}v_{C}+\frac{1}{n_{C}}v_{C_{select}}. $$
通过自我批评确定终止。 尽管值模型为部分解提供了准确的评估，但它不能始终发出逻辑终止信号，特别是在推理模型得出错误结论时。因此，即使生成了错误的最终答案，仍可能在该节点下进行进一步探索，导致搜索效率降低。因此，我们建议使用自我批评来提供额外的及时逻辑终止信号，以避免不明智的探索，并为更深入的搜索提供洞察。具体来说，我们在每次扩展阶段之前提示推理模型生成推理结束（EoI）信号或根据现有部分解$p$提供后续探索步骤的建议$o$。如果接收到EoI信号，则跳过扩展和MC rollout阶段。否则，建议将在后续扩展阶段中用作推理提示的一部分，因此$\pi_{S_{0}}$基于$o$和$p$生成新步骤。ReST-MCTS*的总体伪代码如算法2所示。
算法2 提出的值引导搜索算法MCTS*。
输入: 问题$q$，推理模型$\pi_{S_{0}}$，值模型$V_{\theta}$，最大迭代次数$T$，阈值$l$，分支$b$，rollout步骤$m$，rollout分支$d$，权重参数$\alpha$。
输出: 最佳解决方案$p_{C}$。
- $T_{q}\leftarrow\text{Initialize_tree}(q)$
- $\pi_{S_{0}},V_{\theta}\leftarrow\text{Initialize_models}(\pi_{S_{0}},V_{\theta})$
- for $i$ in range($T$) do
$C\leftarrow\text{root}(T_{q})$**while** $C$ is not leaf node **do**$C\leftarrow argmax_{C^{\prime}}\epsilon_{\text{children}}(c)\left(v_{C^{\prime}}+\epsilon\sqrt{\frac{\ln n_{C}}{n_{C^{\prime}}}}\right)$ // 基于UCB选择子节点**if** $v_{C}\geq l$ **then****return** $p_{C}$ // 输出解决方案**else**$o\leftarrow\text{Do\_self\_critic}(p_{C}|q,\pi_{S_{0}})$ // 获取$\pi_{S_{0}}$的响应以进一步利用或停止推理**if** $o$ is not **Eol** **then****for** $j$ in range($b$) **do**$C_{j}\leftarrow\text{Get\_new\_child}(o,p_{C}|q,\pi_{S_{0}})$ // 基于前几步和自我批评进行扩展$v_{C_{j}}\gets V_{\theta}(p_{C_{j}}|q)$ // 使用值模型进行评估$C^{\prime}\leftarrow argmax_{C^{\prime}}\epsilon_{\text{children}}(c)\left(v_{C^{\prime}}\right)$$p=p_{C^{\prime}}$$v_{max}=0$**for** $k$ in range($m$) **do**$p,v_{max}\leftarrow\text{Get\_next\_step\_with\_best\_value}(p|\pi_{S_{0}},V_{\theta},d,q)$ // 采样新子节点并记录最佳观察值$v_{C^{\prime}}\leftarrow\alpha v_{C^{\prime}}+(1-\alpha)v_{max}$$n_{C^{\prime}}\gets n_{C^{\prime}}+1$ // 更新rollout节点的值和访问计数Back_propagate($C$) // 使用加权平均更新父节点的值- $C$=Get_best_node($T_{q}$) // 获取搜索树中具有最高值的节点
- return $p_{C}$
C.2 数据生成过程和奖励推断的具体示例
我们的自训练方法的数据生成过程主要包括四个阶段，即搜索、修剪、验证和奖励推断，如图4所示。对于奖励推断，图3展示了一个具体的示例。
附录D 模型比较
ReST-MCTS vs. AlphaLLM。* 作为一种旨在增强LLM推理的方法，AlphaLLM [61]使用定制的MCTS算法和批评模型来提供精确的反馈。尽管AlphaLLM也采用MCTS和批评模型进行自我改进，但他们的方法在多个关键方面与我们的方法不同，如下所述。
(1) MCTS算法的设计。 对于搜索级别，AlphaLLM的$\eta$MCTS将选项视为动作，终止信号由终止函数$\beta$传递。相比之下，我们使用推理步骤作为动作，这是通过定制的提示设计实现的。关于批评模型，我们使用单个值模型为中间节点提供评估。该模型经过训练，可以预测特别设计的质量值，这些质量值反映了部分解的完整性和正确性，而不是估计RL中值函数的传统定义。此外，我们还将自我批评机制纳入树搜索算法中，以提供对策略的洞察（附录C.1），而AlphaLLM没有采用这一点。
(2) 奖励/值的定义。 我们对加权奖励和质量值的定义是新颖的，导致我们的方法与AlphaLLM在批评模型训练、数据合成和数据过滤等各种过程中存在显著差异。由于我们的质量值设计涉及过程奖励和推理距离的信息，因此基于此目标训练的值模型自然可以在搜索过程中提供足够的反馈，而无需实现AlphaLLM提到的其他批评模型。
(3) 自训练算法。 尽管AlphaLLM也包括迭代自训练，但实现方法差异很大。最重要的是，他们的批评模型在整个迭代过程中是静态的，这意味着他们更关注策略的改进。相比之下，我们还考虑了自训练对批评值模型的影响。如算法1所示，我们根据每次迭代中问题的最终搜索树计算过程奖励和质量值，然后将其用作值模型的新训练数据。
附录E 实验细节
E.1 初始值模型的训练和评估
值模型的初始化。 我们将$D_{V_{0}}$拆分，并使用训练集微调ChatGLM3-6B和Mistral-7B，以预测部分解的值。我们简单地向模型添加一个线性层，以直接将概率转换为标量值。此外，我们使用AdamW优化器[62]和公式(37)中的MSE损失进行优化，最终获得一个可以评估逐步解决方案正确性和完整性的初始值模型$V_{\theta}$。请注意，在此过程中学习率设置为1e-6。MSE训练损失如下：
$$ L_{\text{MSE}}=E_{(q,p,v)\sim D_{V_{\theta}}}[V_{\theta}(p|q)-v]^{2}. $$
值模型的评估。 我们使用包含14k数据样本的测试集来评估值模型，绝对容差为$0.1$：
$$ \text{Accuracy}=\frac{1}{t}\Sigma_{i=1}^{t},I(\lvert clip(V_{\theta}(p_{i}|q_{i}),0,1)-v^{*}_{i}\rvert<0.1) $$
其中$t$是测试数据样本的数量，$q_{i}$是样本$i$的问题，$p_{i}$是样本$i$的部分解，$v^{*}_{i}$是样本$i$的目标值。我们的初始值模型达到了69.3%的准确率，这意味着它在大多数情况下是可靠的。我们还进行了一项研究，以衡量值模型在科学基准SciBench [34]上的表现，与结果监督的奖励模型和自我批评方法进行比较，如表7所示。
E.2 基准设置
为了比较不同搜索方法的性能，我们构建了一个标准化的基准测试，可以普遍用于标记的科学或数学数据集，如MATH、SciBench和SciEval。除了ReST-MCTS，我们还纳入了两个其他基线：思维链（CoT）和树思维（ToT）。对于每种方法，设计了专门的提示$P$以执行搜索过程。此外，部署了推理模型$\pi$和值模型$V$以提供推导和反馈。关于CoT基线，我们使用Self-Consistency计算准确率。对于ToT基线，我们使用简单的贪婪深度优先搜索（DFS）算法，节点值由值模型分配。当达到最大深度$10$时，算法停止利用，并在节点值超过阈值$0.9$时结束。对于ReST-MCTS，使用自我批评，结束阈值也设置为$0.9$。rollout步骤限制$m$设置为$2$，$\alpha$设置为$0.5$，默认迭代次数$T$设置为$50$。此外，两种树搜索算法默认使用$b=3$，其中$b$是扩展过程中生成的样本数量，如前所述。搜索过程结束后，策略被提示根据获得的解决方案提取最终答案，然后与真实答案进行比较以确定正确性。这些方法在基准测试中的结果如第4.3节所示。
E.3 搜索验证的基线
相关验证基线的基本设置如下：
- ORM + Best-of-N (BoN) 为简单起见，我们使用[10]中使用的ORM，该ORM在SciInstruct上进行训练。对于每个问题，我们采样$N$个解决方案，并选择具有最高ORM分数的解决方案作为输出。$N$用于控制令牌使用。
- ReST-MCTS* 实现ReST-MCTS，使用值模型$V_{\theta}$作为PRM来引导MCTS。控制令牌使用的变量是迭代次数$T$和分支参数$b$。
- Self-Consistency 使用简单的CoT提示为每个问题生成$N$个解决方案。然后提取并分类它们的最终答案，选择出现频率最高的答案作为最终输出。$N$用于控制令牌使用。
- PRM + Best-of-N (BoN) 使用值模型$V_{\theta}$作为PRM，我们执行基于DFS的树搜索。每个选定的解决方案$s$由PRM分数$r_{\text{PRM}}=\Pi_{i=1}^{K}v_{i}$评估。在所有$N$个解决方案中，具有最高PRM分数的解决方案被视为最终输出。在此设置下，$b$设置为3，而$N$用于控制令牌使用。
如图2所示，我们比较了每种算法在MATH和SciBench上达到一定准确率所消耗的令牌数量。结果表明，要达到一定的预期准确率，MCTS基本上比其他算法（如SC和ORM + BoN）需要更少的令牌。这意味着基于相同的预期标准，MCTS在保持合理计算成本的同时优于其他算法。至于实际运行时间，我们记录了不同算法（在我们的基本实验设置下）在单个问题上的平均运行时间，如表6所示。我们看到MCTS在探索和模拟上花费的时间比其他简单算法更多。然而，由于我们的方法采用了不同的值设计，它不需要大量的蒙特卡洛估计。这减少了我们算法的运行时间，并将时间消耗限制在合理范围内。请注意，MCTS可以达到其他算法即使在无限成本下也无法达到的高准确率，我们认为这额外的时间是相当可接受的。
E.4 ReST-MCTS*在SciBench上的值模型
我们使用[10]获得的奖励模型（用作SciGLM的分类器）作为ORM，并使用我们的细粒度值模型作为PRM，分别提供结果奖励和逐步值。我们还包括Self-Rewarding方法，其中策略模型本身被指示提供逐步值。对于所有方法，每个步骤的样本数量设置为$3$。使用此设置，我们记录了GLM4和GPT-3.5-turbo在选定问题上的模型准确率，如表7所示。结果表明，与ORM和Self-Rewarding相比，基于PRM的方法表现出更高的准确率。这证实了我们值模型的有效性。此外，图5关注了总令牌预算的消耗，包括所有提示令牌和完成令牌。然而，我们仍然需要注意，随着超参数$b$和$T$的增加，ReST-MCTS*的总令牌使用量（尤其是提示令牌）迅速增加。
E.5 ReST-MCTS*在SciEval上的表现
SciEval。 类似于SciBench，我们在SciEval上进行了基准测试。结果如表8所示。对于GLM4和GPT-3.5-turbo，ReST-MCTS*再次在整体准确率上优于其他基线，分别达到了79.87%和62.31%的准确率。然而，我们注意到，尽管基于树搜索的方法在平均表现上表现出优势，但它们在某些部分的SciEval上未能提高CoT基线的性能。我们检查了数据分布，发现这些部分基本上都是单选题。由于它们比其他类型的问题难度较低，Self-Consistency CoT方法可能已经胜任。此外，这些问题通常需要较少的推理步骤，这可能是树搜索方法表现不如预期的主要原因。
附录F 提示和指令示例
我们在本节中展示了ReST-MCTS*和自训练过程中使用的一些指令示例，包括：
- 推理指令 此指令用于树搜索中，策略基于先前的自我批评信息生成新步骤。
- 自我批评指令 用于生成EoI信号或进一步搜索的建议。
- LLM验证指令 此指令用于自训练的数据生成过程中，当需要通过LLM（在我们的案例中为GPT-4）验证答案时。
附录G MCTS和LLM推理的进一步预备知识
G.1 蒙特卡洛树搜索（MCTS）
MCTS [63]是一种用于在大型和复杂组合空间中进行最优决策的搜索算法。该算法将搜索空间表示为搜索树，并基于随机模拟的评估进行最佳优先搜索。该技术已广泛应用于多个游戏场景，并取得了巨大成功，例如AlphaGo和AlphaZero [64]用于计算机围棋游戏。基本的MCTS算法涉及迭代搜索过程，包括四个步骤来构建搜索树：
(1) 选择。代理从空树的根节点开始，遍历搜索树的访问节点，并根据给定的选择策略选择下一个节点，直到到达可扩展节点或叶节点。
(2) 扩展。如果算法到达可扩展节点，则通过选择未访问的子节点扩展搜索树。
(3) 模拟。完成扩展后，如果当前节点处于非终端状态，则算法将从当前节点开始进行一次或多次独立模拟，直到达到终端状态。在此过程中，动作是随机选择的。
(4) 回传。基于搜索结果更新从当前节点到根的路径上的节点统计信息。请注意，评估的分数基于达到的终端状态。
为了在较少测试的路径与迄今为止确定的最佳策略之间进行权衡，MCTS通过最大化树的上置信界（UCT）在选择子节点$k$时保持适当的探索与利用平衡，如下所示，$\text{UCT}=\overline{X}{k}+2C\sqrt{\frac{2\ln n}{n_{k}}}$：其中第一项$\overline{X}{k}$是从臂$k$获得的平均奖励，该术语鼓励利用更高奖励的选择。通常理解$\overline{X}$在$[0,1]$范围内。在第二探索项中，$C_{p}>0$是一个常数，以满足Hoeffding不等式，奖励在$[0,1]$范围内[26]。$n$是当前节点被访问的次数，$n_{k}$是子节点$k$被访问的次数。通常，$n_{k}=0$产生UCT值为$\infty$，因此节点的所有子节点都有非零概率并被考虑。
G.2 使用蒙特卡洛树搜索的LLM推理
LLM已被发明，过去用于自回归文本生成，现在非常擅长推理。推理算法包括基于提示的思维链（CoT）[22]，基于规划的树思维（ToT）[24]，成功实现了LLM推理性能的提升。ToT结合了树搜索（例如深度/广度优先搜索）作为算法和LLM作为启发式来权衡评估和生成的能力。通过蒙特卡洛树搜索（MCTS）进行推理探索并获得奖励推理路径的推理规划（RAP）[59]。
最近的研究[60]表明，蒙特卡洛树搜索（MCTS）代理受益于任务特定的扩展和扩展研究树。具体来说，MCTS代理根据评估结果（例如奖励和节点被访问的次数）为访问状态提供适当的选择策略，以指导即将进行的搜索。其机制协调搜索空间内的探索和思想利用，优于基于树思维（ToT）的传统深度优先搜索（DFS）或广度优先搜索（BFS）算法。基于MCTS，一些研究还探索了推理代理提供搜索指导的能力。在催化剂设计中，[65]提出了蒙特卡洛思维搜索，使用LLM进行复杂的科学推理查询。[59]提出了推理规划（RAP），采用MCTS作为规划算法，并重新利用LLM作为世界模型和推理代理。其他人如[66]实验使用值函数，作为近端策略优化（PPO）过程的副产品，基于MCTS指导令牌级解码。总的来说，这些方法提高了LLM的推理能力，而它们在一些具有挑战性的科学任务上的表现仍然不尽如人意。此外，这一系列方法不同于我们的贡献，我们提出了一种值模型方法作为奖励函数，以优化推理路径并改进模型输出。
附录H 局限性
在本节中，我们讨论了ReST-MCTS*的一些局限性。
推广到其他任务，特别是那些没有标签的任务。 与许多现有的自训练工作类似，ReST-MCTS也依赖于监督数据集中的真实标签来首先过滤响应；在未来，我们需要展示ReST-MCTS可以推广到数学之外的其他推理任务（如编码、代理、对话等）；此外，对于那些需要多步规划和推理的非常复杂的任务（如实现整个软件，如SWE-Agent），这些任务没有真实答案，我们需要提出一种更好的方法来收集奖励反馈（从少量人工标注和符号执行或求解器），并训练一个可推广的奖励模型，该模型可以工作并帮助更广泛的任务。
所提出的值模型的规模和多样性。 尽管我们基于Mistral-7B: MetaMATH训练了一个值模型，其表现优于最先进的值模型MATH-SHEPHERD，但仍需要更大规模的值模型骨干来进行更好的PRM训练。此外，训练提议PRM的初始训练集是由SciGLM生成的，SciGLM是一个专注于数学和科学推理任务的模型，但仍然缺乏通用性。虽然当前的PRM在多个数学和科学推理任务（如MATH和SciBench）上取得了最佳结果，但值得探索更多样化的训练集，以扩展到各个领域，如代码生成和代理规划。
自训练数据过滤技术。 正如我们在第1节中提到的，推理轨迹的质量影响自训练的有效性，生成高质量的训练集起着重要作用。因此，我们训练迭代过程奖励模型以指导树搜索方向，以获得高质量的轨迹。另一方面，由于训练良好的值模型可以帮助过滤出具有最高过程值的top-k生成轨迹，我们还期望更强和更大的LLM模型作为值模型的骨干可能有助于获得更多。
附录I 更广泛的影响
ReST-MCTS旨在引入一种通用的自训练方法，使用MCTS自动标注和生成过程奖励，这将有助于生成高质量的数据集并提高LLM的推理能力。在各种LLM上微调合成的高质量数据集可以直接提高值模型和生成器的性能，并有助于避免在训练过程奖励模型时手动生成过程奖励的成本。缺点是单个奖励模型无法扩展到多个领域，我们可以通过在各种推理领域上训练各种奖励模型来解决这个问题。我们相信，总的来说，优点大于缺点。
附录J 可重复性
我们已尽最大努力确保我们所有实验结果的