24年11月来自复旦大学、上海AI实验室、UC Merced、香港理工、新南威尔士大学、上海交大和斯坦福大学的论文“LLaMA-Berry: Pairwise Optimization for Olympiad-level Mathematical Reasoning via O1-like Monte Carlo Tree Search”。
本文提出一个数学推理框架 LLaMA-Berry，用于增强大语言模型 (LLM) 的问题求解能力。该框架将
蒙特卡洛树搜索与自我细化 (SR-MCTS)
相结合以优化推理路径，并利用成对奖励模型对全局的不同路径进行评估。通过利用 LLM 的自我批评和重写功能，SR-MCTS 通过促进更有效地探索解决方案空间来克服传统逐步推理和贪婪搜索算法的低效和局限性。为了指导搜索过程，提出
成对偏好奖励模型 (PPRM)
，通过强化学习从人类反馈 (RLHF) 训练的指令遵循能力来预测解决方案之间的成对偏好。最后，采用
增强型 Borda 计数 (EBC)
方法将成对偏好合成为全局分位数分数以进行评估。该方法解决数学推理任务中评分变异性和非独立分布的挑战。该框架已在通用和高级基准上进行了测试，与现有的开源和闭源方法相比，显示出不错的搜索效率和性能，特别是在复杂的奥林匹克级基准测试中，包括 AIME24 和 AMC23。
数学推理
是人工智能领域的一大挑战，广泛应用于自动定理证明、数学问题解决和科学发现（Ahn，2024）。最近，GPT-4 等大语言模型 (LLM)（Achiam，2023）在涉及算术和几何问题解决的一般数学任务方面取得重大进展（Cobbe，2021；Sun，2024；Ying，2024）。然而，复杂的数学推理仍然具有挑战性，尤其是在奥林匹克级别的基准测试中，例如 AIME（MAA，2024）。
提高问题解决能力的一种直观方法是将解决方案分解为
逐步推理
路径（Lightman，2023；Luo，2024a），如 Chain-of-Thought（CoT Wei，2022）所示。虽然基于提示的方法可以有效地促进这种推理路径的构建，但由于生成过程中缺乏全面的反馈，它们仍可能遇到挑战，从而影响效率（Paul，2023）。与逐步生成方法相比，另一个有前途的研究方向将整个解决方案视为一个独立的状态，使用
重写功能
来改进解决方案，例如 Self-Refine（Madaan，2023a）和 Reflexion（Shinn，2024）。然而，这些方法虽然具有创新性，但有时也会面临一些挑战，比如容易陷入局部最优或由于反馈缺陷而可能偏向次优解，这可能会影响它们的最大潜在性能。
除了生成推理路径之外，有效的解决方案评估也至关重要，
结果奖励模型 (ORM)
和
过程奖励模型 (PRM)
(Uesato，2022) 等模型就是很有价值的例子。ORM 关注推理路径中最终答案的正确性，而 PRM 则强调流程中每个步骤的正确性。虽然这两种方法都使奖励模型能够分配标量分数，但获得可靠的标记数据来训练这些奖励模型仍然是一项重大挑战。此外，数学推理任务的评分标准可能有很大差异，因为每个问题都有独特的特点。这种变化使奖励模型的扩展变得复杂，并阻碍它们捕捉解决方案之间局部偏好关系的能力。尽管使用语言模型进行训练，这些奖励模型尚未充分利用指令遵循能力，这可能会限制它们处理更复杂的推理任务的有效性（Zhang，2024a）。
推理的奖励模型
。可靠的奖励模型（Kang，2024；Wang，2023；Havrilla，2024；Lightman，2023；Ma，2023）可以有效区分期望反应和不期望反应，这在复杂推理中尤其重要。结果奖励模型 (ORM) 是用推理路径的最终结果进行训练的。由于奖励由最终答案决定，ORM 可能会受到粗略监督和错位问题的影响。相比之下，过程奖励模型 (PRM) 提供更易于解释的分步奖励信号，并引导模型遵循 CoT。因此，PRM 通常被认为更有效（Lightman 等人，2023）。然而，PRM 的成功依赖于大量手动注释的数据（Luo，2024a；Havrilla，2024），这非常耗时，并且仍然面临绝对奖励分数波动性的挑战。
树搜索推理
。对不同的推理路径进行采样（Brown，2024）已证明其在提高找到正确答案概率方面的有效性。自洽性 (Wang et al., 2022) 每次都会采样一条完整路径，而诸如思维树 (ToT) (Yao et al., 2023) 和蒙特卡洛树搜索 (MCTS) (Chen et al., 2024a,b; Luo et al., 2024b; Feng et al., 2023; Xie et al., 2024; Xu, 2023; Liu et al., 2023; Tian et al., 2024; Ding et al., 2023) 之类的树搜索方法会扩展多个步骤以优化步骤答案并最终获得最优解。此外，自优化 (Madaan et al., 2023a) 方法已成为最近的焦点。自我验证（Gero，2023；Weng，2022）和 rStar（Qi，2024）利用模型的固有能力来迭代探索和细化答案。然而，自我细化的性能通常受到模型固有能力的限制，尤其是对于自我细化能力明显较弱的小型语言模型 (SLM)（Madaan，2023b）。Zhang（2024b）提出，通过多智体协作将细化过程视为有向无环图 (DAG)，可以增强 LLM 的数学推理能力。
如图所示，SR-MCTS 将蒙特卡洛树搜索 (MCTS) 与自优化机制相结合，以不断评估和优化解决方案搜索。这种集成利用 MCTS 的迭代特性和 LLM 的自我改进能力，从而改善搜索结果。
蒙特卡洛树搜索 (MCTS) 是马尔可夫决策过程 (MDP) 框架内的一种有效方法，通过采样应用状态、动作和价值函数。该算法遵循四个关键步骤：
选择、扩展、评估和反向传播
。在选择阶段，使用树置信上限 (UCT) 算法扩展根节点，该算法通过平衡探索和利用来选择节点。在扩展阶段，节点 s 生成后续状态 s′，作为新节点添加到树 T 中。评估阶段，通常使用模拟或启发式方法来估计这些节点的 Q 值。最后，在反向传播期间，估计的 Q 值会从叶节点追溯更新到根节点。这个迭代过程允许 MCTS 通过平衡新路径的探索和已知高价值路径的利用来改进决策。
选择阶段
。选择阶段从搜索树 T 中确定一个节点 s_i 以进行扩展，其中每个节点代表一个完整的解决方案状态。采用树置信上限 (UCT) 算法来选择最优节点，并使用动态修剪来避免局部最优。当节点 s_i 的子节点达到预定义的限制，并且至少一个子节点的 Q 值超过 s_i 的 Q 值时，即认为该节点 s_i 已被充分探索。
扩展阶段
。在扩展阶段，如上图所示，选定答案 s_i 通过自我完善过程生成后继答案进行扩展，自我完善过程包括批评和重写过程。批评过程生成批评 c_i = C(s_i)，指出当前选定答案 S_i 中的缺点（如数学错误或逻辑故障）；重写过程生成新答案 s_i+1 = R(s_i, c_i)。实践中，为了简化问题，假设此过程是确定性的，确保相同的原始状态解 s_i 始终产生相同的后继状态解 s_i+1。然后将新状态解 s′ 作为新节点添加到搜索树 T 中。
评估阶段
。评估阶段使用成对偏好奖励模型（PPRM）计算新生成的节点 s′ 的值 Q（s′）。评估包括两个步骤：全局价值评估和局部价值评估。全局价值 Q_g(s′) 由胜负偏好矩阵 M 中 s′ 的分位数决定，反映节点之间的胜负关系。局部价值 Q_l(s′) 通过与搜索树 T 中的相邻节点比较得出。然后，总价值 Q(s′) 计算为全局价值和局部价值的加权组合：Q(s′) = αQ_g(s′) + (1 − α)Q_l(s′)，其中 α 控制每个成分的相对影响力。
反向传播阶段
。在反向传播阶段，新节点的价值 Q(s′) 传播回其父节点 s_i，将 s_i 的 Q 值更新为其子节点 Q 值的折扣和：Q(s_i) = (1 − γ)Q(s_i) + γQ(s′)。折扣因子 γ 表示未来奖励的重要性。这种迭代更新机制确保父节点的价值不断优化，从而增强对未来选择的指导。
此外，为了控制搜索树的增长，SR-MCTS 方法限制最大展开次数 N_max。当达到限制时，搜索过程终止，从而限制了树的无限制扩展。SR-MCTS 的总体目标是最大化所有现有节点 S 的预期最高 Q 值，引导走向最理想的结果 s∗，确保搜索过程高效地收敛到高质量的解决方案。
对不同解决方案进行可靠的评估，在数学问题解决任务中起着至关重要的作用，因为它可以更好地估计 Q 值，从而提供更好的指导。现有的奖励模型通常通过给出绝对分数来评估解决方案，例如过程奖励模型（PRM Lightman，2023）和结果奖励模型（ORM Yu，2023）。然而，基于分数的奖励模型可能无法充分利用 LLM 的指令遵循能力或有效处理评分标准的变化，尤其是当解决方案之间的差异非常微妙。为了解决这个问题，提出成对偏好奖励模型 (PPRM)，它利用一个全面的偏好数据集，其中包含来自 PRM 和 ORM 方法的大量样本（Toshniwal，2024；Lightman，2023）来学习数学解决方案之间的偏好关系。
对于给定数学问题的两个解决方案（a1 和 a2），用 a1 ≻ a2 来表示 a1 优于 a2 的情况。PPRM 使用成对偏序预测它们的相对质量。在该方法中，a1 ≻ a2 由 LLM 的tokens表示，并且使用 LLM 计算的token logits 值来估计 P(a1 ≻ a2 | φ)。
然后，受到语言界面微调（LIFT Dinh，2022）进步的启发，将 PPRM 的训练过程构建为问答任务，以利用 LLM 的指令遵循能力。该模型的任务是回答以下问题：“对于问题 Q，解决方案 a1 是否比解决方案 a2 更好？” 如图所示。为了形成一个稳健的训练目标，使用指示函数 I 将预测的token标签 yˆ（“是”或“否”）与基本事实标签 y 一起进行评估。
最后，将包含数百万个数学问题解决方案对的成对偏好数据集 D 转换为适合问答任务的数据集 D′。采用 RLHF 技术来训练模型，以提高其在偏序预测问答任务中的表现。随后，利用直接偏好优化（DPO Rafailov，2024）方法最大化目标 argmax_φ E_P[I（yˆ，y）] 来找到最佳 P_φ。
尽管 PPRM 允许直接比较两个解决方案的质量，但仍然需要将这些局部偏好转换为一个有凝聚力的全局排名，以获得对答案的全面评估。这个转换过程可以形式化为与学习排名 (LtR) 方法相关的全局最优排名聚合 (GORA) 问题。此外，提出基于数学问题解传递性假设的增强 Borda 计数 (EBC) 方法，它将朴素 Borda 计数算法与 Floyd-Warshall (Warshall, 1962) 算法计算的偏好传递闭包相结合。
局部偏好计算
。首先，PPRM 为所有 n 个问题解生成一个偏好矩阵 M，其中 M_i,j = 1 表示解决方案 a_i 优于解决方案 a_j，否则 M_i,j = 0。如上图所示，该矩阵可看作是有向图 G = (V, E)的邻接矩阵，其中每个解 a_i 对应一个顶点 v_i，如果 M_i,j = 1，则存在一条边 e = (v_i, v_j)，表明解 a_i 优于 a_j。
转换闭环
。为简化问题，采用数学解的传递性假设，即如果 v_i ≻ v_k 且 v_k ≻ v_j，则v_i ≻ v_j。在此假设下，偏好矩阵的转换闭环 C 可通过 Floyd-Warshall 算法计算，例如，如果 M_i,k = 1 且 M_k,j = 1，则 M_i,j = 1。
基于Borda计数的全局排序
。接下来，基于转换闭环矩阵 C，应用增强型 Borda 计数法进行全局排名。增强型 Borda 计数法通过计算每个节点的出度（out-degree）来确定其排名，出度对应于它击败的节点数。对于每个节点 v_i，Borda(v_i) 定义为 (C_i,j) 和，如图中列出的排名节点一样。
Borda 计数越高，排名越高。然而，在实践中，循环偏好可能会导致朴素的 Borda 计数方法出现效率问题。为了进一步完善排名，设计一个重排名阶段，其中 PPRM 生成的对数用于在 Borda 计数相等节点之间进行软比较。具体来说，对于两个 Borda 计数相等的节点 v_i 和 v_j，软比较规则可以表示为 v_i ≻v_j ⇐⇒ P(a_i ≻a_j) > P(a_j ≻_ai)。此过程可确保即使存在循环或局部歧义，排名仍保持一致和合理。
解决方案的全局分位数得分
。最后，将排名转换为每个解决方案 v 的全局分位数得分 Q_g，即 Q_g (v) = 1 − (rank(v)−1)/( |V|−1)，其中 rank(v) 是基于 Borda 计数排名中 v 的位置，|V| 是节点总数。为了反映搜索树结构中的局部优势，在 C 中计算节点 v 的局部胜率 Q_l(v) 及其子节点 Children_v。
