24年11月来自清华和加州理工的论文“ReST-MCTS∗: LLM Self-Training via Process Reward Guided Tree Search”。
LLM 自训练的最新方法，主要依赖于 LLM 生成响应并过滤那些具有正确输出答案的响应作为训练数据。这种方法通常会产生低质量的微调训练集（例如，错误的规划或中间推理）。本文开发一种强化自训练方法，称为
ReST-MCTS∗
，该方法基于将过程奖励指导与树搜索 MCTS∗ 相结合，以收集更高质量的推理轨迹以及每步价值来训练策略和奖励模型。ReST-MCTS∗ 绕过通常基于树搜索强化学习训练过程奖励的每步手动注释：给定 oracle 最终正确答案，ReST-MCTS∗ 能够通过估计此步有助于得出正确答案的概率来推断正确的
过程奖励
。这些推断的奖励有双重目的：它们充当进一步完善过程奖励模型的价值目标，也有助于为策略模型自训练选择高质量的轨迹。在相同的搜索预算内，ReST-MCTS∗ 中的树搜索策略与之前的 LLM 推理基线（例如 N 中最佳和思维树）相比实现了更高的准确率。然后，通过此树搜索策略搜索的轨迹作为训练数据，可以不断增强这三种语言模型进行多次迭代，并超越其他自训练算法（例如 ReST-EM 和 自奖励语言模型）。
大语言模型 (LLM) 主要在人工生成的数据上进行训练。但随着网络上大多数可用高质量人工生成的文本已被抓取并用于 LLM 训练 [1] ，研究重点已转向使用 LLM 生成的内容进行自我训练 [2; 3; 4; 5; 6; 7]。与大多数强化学习 (RL) 问题类似，LLM 自我训练需要奖励信号。大多数现有的强化自我改进方法（例如 STaR [4]、RFT [5]、ReST-EM [6]、V-STaR [7]）假设可以访问真实奖励模型（来自监督数据集的标签或预训练的奖励模型）。这些方法使用 LLM 为每个问题生成多个样本，并假设导致高奖励（正确解决方案）的样本是高质量样本，然后在这些样本上进行训练（因此称为自我训练）。此类程序可有效提高 LLM 性能，在某些情况下可解决基础 LLM 无法解决的推理任务 [8; 9; 10]。
大语言模型训练
。大语言模型 (LLM) [36; 37; 38] 在各种自然语言任务中取得显著的成功。最近的研究重点是提高 LLM 的推理能力，包括收集高质量或更大的领域特定数据 [39; 40; 41; 42; 10; 43]、设计精心设计的提示 [22; 44; 45; 46]，或训练监督学习 [10; 31; 32; 47] 或强化学习 (RL) [48; 49; 50; 16]。当使用 RL 算法训练 LLM 时，LLM 的生成可以自然地表示为马尔可夫决策过程 (MDP)，并针对特定目标进行优化。根据此公式，InstructGPT [51] 通过利用来自人类反馈的 RL (RLHF) [52] 优化 LLM 以符合人类偏好，取得了显著成功。然后，RLAIF 使用 AI 反馈从人类反馈扩展 RL [53]。
大语言模型推理
。LLM 推理算法包括基于提示的思维链 (CoT) [22]、基于规划的思维树 (ToT) [24]。科学推理有几个类别来挖掘现有大型语言模型的潜力，这些类别源于解决问题的不同表现。先前的研究试图超越直接生成。例如，在论文 [54] 中，提出一种逐步生成解决方案的方法，使用另一个模型或函数来选择排名靠前的答案，并通过将输出限制在更窄的集合来避免幻觉。[55] 提出一种引导提示推理方法，它可以对递归解释的各种假设生成溯因解释，消除矛盾的候选，并实现逻辑一致的推理。思维链 (CoT) [22] 模仿人类的思维过程，针对问题提供逐步解决方案。自洽性 CoT [23] 通过从 LM 中抽取多种解释，然后选择出现频率最高的最终答案，提高了答案的可靠性和自洽性。思维树 (ToT) [24] 通过考虑树中的多种不同推理路径并探索连贯的思维单元来执行深思熟虑的决策，进一步概括了 CoT 方法。
然而，上述程序的一个关键限制是，即使推理轨迹得出正确的解决方案，也不一定意味着整个轨迹都是准确的。LLM 通常会生成错误或无用的中间推理步骤，但仍然会偶然找到正确的解决方案 [17]。因此，自训练数据集通常可能包含许多误报 - 中间推理轨迹或规划不正确，但最终输出是正确的 - 这限制 LLM 微调复杂推理任务的最终性能 [18; 19]。解决此问题的一种方法是使用价值函数或奖励模型来验证推理轨迹的正确性（然后将其作为自训练的学习信号）[1; 12]。然而，训练可靠的奖励模型来验证推理轨迹中的每一步通常依赖于密集的人工生成注释（每个推理步骤）[1]，这不能很好地扩展。本研究旨在通过开发一种新方法来解决这一差距，该方法可以自动获取可靠的推理轨迹，同时有效地利用奖励信号进行验证。主要研究问题是：
如何自动获取高质量的推理轨迹，并有效地处理奖励信号以进行验证和 LLM 自我训练？
ReST-MCTS∗
是一个使用基于模型 RL 来训练 LLM 的框架。如表所示给出其和以往方法的比较：进行可靠自我训练的主要挑战是构建有用的学习信号。理想情况下，人们希望每个中间推理步骤的正确性都有一个密集的学习信号，这由 PRM 给出。否则，使用稀疏的学习信号，人们会遭受与强化学习类似的信用分配。从历史上看，学习过程奖励模型（PRM） 的主要挑战是每个推理步骤缺乏监督注释。这是 ReST-MCTS∗ 方法试图克服的主要挑战。
使用推理方法可以显著提高 LLM 解决问题的能力 [10]。给定一个策略模型 π（一个自回归预训练语言模型）和一个输入问题 Q，π 可以通过预测下一个 token 自回归生成输出序列 s = (s_1 , s_2 , · · · , s_K )。
给定一个输入问题 Q，在最简单的情况下，π 可以通过自回归预测下一个token来生成输出序列或推理步骤 (s_1, s_2, · · · , s_K ) ∼ π(·|Q) 的轨迹。为简单起见，假设一个推理步骤包含一个句子（句子本身包含多个 tokens）。还假设最后的输出 s_K 是最后一步。LLM 也可以被提示或调节以沿着某些轨迹偏向生成。对于提示 c，可以将策略写为 π(·|Q, c)。这个想法最著名的应用是思维链 (CoT) [22]。
任何问题都可以通过零样本提示、少样本提示[57]、思维链（CoT）[22]、自洽 CoT [23] 或最佳 N（BoN）选择[1]、思维树（ToT）[24]、蒙特卡洛树搜索（MCTS）[14]、思维图（GoT）[58] 等方法来推理。
在 LLM 的背景下，假设推理轨迹来自策略模型 π 采样。自训练方法的常见第一步是在原始数据集 D_S_0 上微调基础模型 π 并获得新的生成器 π_S_0。此外，还考虑奖励 r 来评估历史轨迹的价值。
最近的研究 [1; 12] 通过 PRM 和 ORM，将推理的目标建模为搜索问题 Q 的最高累积奖励轨迹 s 并推断出最终答案 A。
本文方法
ReST-MCTS∗
如图所示，由四个主要组件开发而成：
• MCTS∗ 在 PRM 的指导下，以足够的部署时间执行树搜索。
• PRM 评估任何部分解决方案的质量并指导 MCTS∗。
• 策略模型为每个问题生成多个中间推理步骤。
• LLM 自训练，使用 MCTS∗ 收集推理轨迹，在正样本上训练策略模型，并在所有生成的轨迹上训练PRM。
像 [24] 和 [26] 这样的树搜索方法需要一个价值函数和结果奖励模型 r_φ 来修剪分支、评估最终解决方案和备份价值。然而，使用 ORM 来评估最终解决方案并反向传播意味着必须完全生成每个搜索轨迹，这既昂贵又低效。最近的研究 [14] 建议在 MCTS 中使用学习的 LLM 价值函数，这样备份过程就可以在中间步骤中进行，而不需要完整的生成。他们的工作大大提高搜索效率，但仍然依赖
输出奖励模型（ORM）
来选择最终答案。从这些工作中汲取灵感，本文提出一种 MCTS 变型，即
MCTS
∗，它使用质量价值 v_k 作为训练的基于 LLM
过程奖励模型（PRM）
价值目标，并为 MCTS 提供指导。
鉴于上述属性，可以直接使用
过程奖励模型
V_θ 来评估任何部分解决方案的质量，并在中间节点中进行选择和反向传播。除了使用质量价值之外，还结合特殊的
蒙特卡洛展开
方法和
自我批评
机制来提高效率和精度。MCTS∗ 表示为一种算法，该算法在每次迭代中包含四个主要阶段，即
节点选择、思维扩展、贪婪 MC 展开和价值反向传播
。
与常见的 MCTS 设置类似，该算法在每个单个科学推理问题 q 的搜索树 T_q 上运行。每个树节点 C 代表一系列想法或步骤，其中记录部分解决方案 p_C 、访问次数 n_C 和相应的质量价值 v_C 。为简单起见，将每个节点表示为一个元组 C = (p_C , n_C , v_C )。
给定一个新的训练数据集 D_G，自训练方法使用生成器 π_S_0 为每个问题 Q 生成推理步骤 s 和最终答案 A。在每次迭代 i（i ≥ 1）中，STaR、RFT 和 ReST-EM 使用二进制正确性标签 z 检查生成的解 D_G_i，并将正确的解（A_j = a∗）保留为 D_G_i (A_j=a∗)。V-STaR 和 Self-Rewarding 在正样本上不断迭代的基础上，保留每个问题 Q 正确和错误的生成解，并使用所有数据 D_G_i 在构造的验证器数据 D_VER 上训练偏好数据对，因此 π_V 可以学习生成器在每次迭代 i 中产生的错误模式。然后，生成器 π_S_i−1 ，这里是 π_S_0 ，在新生成的数据集 D_G_i (A_j = a∗) 上进行微调，过程在后续迭代中不断运行。
节点选择
。与 [14] 类似，从初始根节点开始每个选择过程，因为这样可以进行回溯。在每次迭代中，首先执行节点选择阶段，其中从初始根节点开始分层选择叶节点C_select。为了纳入节点的质量价值，使用
UCB（可信度上限）
作为选择子节点的标准，而不是
树可信度上限（UCT）
[26]。对于每个中间节点，选择具有最大 UCB 的子节点。此标准同时考虑质量价值和访问次数，因此它鼓励探索高质量节点，同时为未充分探索的节点留下一些机会。
思维扩展
。其次，将选定节点 C_select 的值与阈值 l 进行比较（在实验中，l 设置为 0.9）。如果 v_C_select >= l，则节点记录的部分解决方案 p_C_select = [s_1 , s_2 , · · · , s_k ] 被视为可以接受的最终解决方案（因为只有当 C 接近正确的最终答案时，v_C 才会接近 1），然后直接将其作为输出返回，终止算法。这与 [60] 采用的方法不同，因为不需要奖励模型估计。否则，启动扩展阶段，其中通过提示策略 π_S_0 来采样新的解决方案步骤 s_k+1,i（i = 1, 2, · · · , b），即 s_k+1,i ∼ π_S_0 (s_1,2,··· ,k|q)，b 是样本或分支的数量。随后，将新节点 C_i = ([s_1, s_2, · · · , s_k, sk+1,i], 0, v_C_i ) 添加到 T_q 中，其中 v_C_i 由价值模型分配，v_C_i ← V_θ(p_C_i |q)。请注意，还将自我批评机制纳入此扩展过程。
贪婪 MC 展开
。[60] 和 [14] 使用简化的三阶段迭代，其中不包括叶节点上的模拟过程。相反，尽管生成和时间成本增加，但模拟过程仍会带来有用的信息以进行价值估计。在此阶段，在具有最大预测值的新节点 C_i 上模拟几个步骤。从此节点开始的推理步骤将逐步采样并进行评估，同时仅进一步探索最有价值的路径，直到达到步骤限制 m。记录在采样过程中获得的最高质量值 v_max 并用于基于权重参数 α 的 v_C_i 更新。
价值反向传播
。最后，从 C_select 开始进行价值备份。使用加权平均方法更新 C_select 每个父节点的价值。对于从根到 C_select 轨迹上的每个节点 C，更新其 n_C 和 v_C。
通过自我批评确定终止
。尽管价值模型为部分解决方案提供了准确的评估，但它无法始终如一地发出逻辑终止信号，尤其是当推理模型得出错误结论时。因此，即使生成了错误的最终答案，仍可能在此节点下进行进一步探索，从而降低搜索效率。因此，使用自我批评来提供额外的及时逻辑终止信号，以避免不明智的探索以及对更深入搜索的洞察。具体而言，提示推理模型在每个扩展阶段之前根据现有的部分解决方案 p 生成推理结束 (EoI) 信号或提供有关后续探索步骤的建议 o。如果收到 EoI 信号，则将跳过扩展和 MC 展开阶段。否则，将在下一扩展阶段作为推理提示的一部分使用，因此 π_S_0 根据 o 和 p 生成新步骤。
如下算法 2 总结该价值引导的搜索算法 ReST-MCTS∗ 为伪代码形式：
基于所提出的树搜索算法 MCTS∗，对推理策略和过程奖励模型进行自我改进。在初始化策略 π 和过程奖励模型 V_θ 之后，迭代地使用它们，并利用在此过程中生成的搜索树 T_q 为特定的科学或数学问题生成高质量的解决方案并进行自我改进过程，称为
ReST-MCTS∗
。该工作从 MuZero [20] 框架中汲取灵感，并将其应用于 LLM 的训练，称之为“MuZero 式 LLM 学习”。
自训练方法的数据生成过程主要包括四个阶段，即搜索、修剪、验证和奖励推理，如图所示：
故此，搜索过程会产生一个搜索树 T_q，由多条推理轨迹组成。首先剪枝掉所有未完成的分支（未得出最终答案的分支）。然后通过简单的字符串匹配或 LLM 判断，根据树搜索中其他轨迹最终答案的正确性进行验证，选出正确的解。这些验证过的推理轨迹，即第 i 次迭代中的 D_G_i（A_j = a∗，N 为采样解数，A_j 为第 j 个解，a∗ 为最终正确答案），用于提取新的训练数据进行策略自改进，这个过程就是执行策略自训练。
