OpenIAo1原理解读：Q*强化学习与启发式搜索推理框架[Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning]-AI论文

1. 引言 (Introduction)

大型语言模型（LLMs）在许多自然语言任务中展现了令人印象深刻的能力。然而，LLMs的自回归生成过程使得它们在进行多步骤推理时容易产生错误、幻觉以及不一致的陈述。在本文中，我们将LLMs的多步骤推理问题转化为一个启发式搜索问题，并提出了一种名为Q的通用、灵活且敏捷的框架，通过审慎的规划来引导LLMs的解码过程。我们通过学习一个即插即用的Q值模型作为启发函数，估计预期的未来奖励，Q能够有效地指导LLMs选择最具前景的下一步推理步骤，而无需针对当前任务对LLMs进行微调，从而避免了巨大的计算开销以及在其他任务中性能下降的潜在风险。在GSM8K、MATH和MBPP数据集上的大量实验表明，我们的方法在现有开源LLMs的基础上显著提高了推理性能。

鉴于此,我们提出了Q*,一个用于通过深思熟虑规划来提高LLMs多步推理能力的通用、多功能和敏捷的框架。与现有的深思熟虑方法不同, 我们的方法不依赖领域知识来设计启发式函数。此外,通过利用即插即用的Q值模型作为启发式函数,我们的Q可以有效地解决各种任务,引导LLMs选择最有前途的下一步,而无需预先对LLMs进行微调,从而避免了显著的计算开销和在其他任务上可能出现性能下降的风险。最后,Q在执行深思熟虑时只考虑单个步骤,这比MCTS中完成模拟的成本要低得多。

---

2. 相关工作 (Related Works)

LLMs的对齐已成为防止模型输出偏离人类期望的重要技术。监督微调（SFT）可能是最基本的对齐方法，直接通过最小化输出与真实标签之间的交叉熵损失来进行模型调整。另一方面，通过人类反馈的强化学习（RLHF）首先通过人类偏好学习奖励模型（RM），然后使用强化学习算法优化SFT模型，以最大化从RM中获得的累积奖励。直接偏好优化（DPO）通过人类反馈中的排序信息直接对齐LLMs，而无需显式学习RM。最近，Aligner作为一种模型无关的对齐方法提出，通过学习重写LLMs的输出。与这些方法相比，Q具有不同的优点。与SFT和Aligner不同，Q不依赖于大规模的人工标注偏好对，这些对非常昂贵；与RLHF和DPO不同，Q*不修改LLMs的参数，避免了在其他任务中性能下降的风险。

通过规划增强LLMs的能力。Tree-of-thoughts（ToT）通过基本的树搜索算法（如宽度优先搜索或深度优先搜索）探索问题解决的中间步骤，以提高LLMs的推理能力。同样，A搜索和蒙特卡洛树搜索（MCTS）被应用于作为一种规划技术，帮助LLMs在解决复杂的推理问题时提高性能。不幸的是，这些方法中使用的效用函数通常需要为每个具体任务进行复杂的设计，难以推广到新的场景中。此外，使用MCTS进行规划通常需要大量的回合来找到高质量的答案，这大大降低了整体解码过程的速度。为了解决这些问题，我们提出了Q框架，它使用即插即用的Q值模型作为启发函数，通过不修改LLMs参数的方式有效地引导它们选择最有前途的推理步骤，适用于各种推理任务。

LLMs用于数学推理和代码生成:

数学推理和代码生成要求LLMs对关系、数量和逻辑进行多步推理,这本质上具有挑战性。当前的技术包括:

1)提示工程,通过复杂的提示触发LLMs的潜在能力。然而,构建这样的提示需要广泛的专业知识和逐案调整,难以推广到不同的任务;

2)使用大量数学/代码语料库对LLMs进行微调,这通常以巨大的计算负担为代价,并可能损害其他任务的性能;

3)训练RM/验证器来对候选解决方案进行排名,而不提供中间步骤的任何指导。

与之不同,我们的Q*利用即插即用的Q值模型来指导LLMs的深思熟虑过程,有效地为每个中间步骤提供指导,而无需修改LLMs的参数。此外,通过将LLMs的多步推理建模为启发式搜索问题,我们的方法可以推广到各种推理任务,而无需繁琐的提示工程。

---

3. 预备知识 (Preliminary)

将LLMs的多步骤推理形式化为马尔可夫决策过程 (Formulate the Multi-step Reasoning of LLMs as an MDP)

将问题q作为输入，LLMs的答案生成过程可以分解为多个推理步骤，其中最终答案序列a可以看作是这些T个单步推理步骤的连接，公式为a = [a1; a2; …; aT]。每个步骤可以是LLMs输出的单行或固定数量的token。在此视角下，我们可以将LLMs的多步骤推理过程概念化为一个马尔可夫决策过程（MDP）⟨S,A,T,R,γ⟩，其中状态st ∈ S表示输入问题和前面生成的推理步骤的连接，动作at ∈ A表示LLMs生成的下一个推理步骤，状态转移T通过简单的连接操作将当前状态st转换为下一个状态st+1，奖励函数R用于衡量问题解决得有多好，γ是折扣因子。奖励函数通常基于结果给出。也就是说，它通过将最终结果与真实值进行比较来给予奖励：

A搜索 (A Search)

A是一种重要的启发式搜索算法，广泛应用于审慎规划、多智能体路径规划和约束推理。最初，A是为在路径规划问题中从源点s到目标点g寻找最短路径而提出的。它为每个前沿顶点n关联一个值f(n) = g(n) + h(n)，其中g(n)是从源点s累积的路径成本，h(n)是估算从n到目标g的最短路径成本的启发值。该算法采用最优优先搜索策略，即每次迭代总是选择f值最小的顶点进行扩展，直到到达目标。当启发式h(·)是可接受的时，A*保证找到最优路径。

---

4. Q*：一种通用、灵活的审慎规划框架 (Q*: A General, Versatile and Agile Deliberation Framework for LLMs)

现代LLMs以自回归方式生成自然语言，即在给定先前生成的token序列的情况下预测下一个token。因此，当LLMs应用于多步骤推理问题时，任何先前步骤中的错误都可能导致后续推理路径中引入错误、幻觉和不一致，最终未能解决当前问题。鉴于LLMs生成每个token的计算资源有限，无法在解决难题时投入更多的计算资源。简而言之，LLMs无法执行深入的审慎思考，这是解决复杂多步骤推理问题所必需的。

我们提出了Q框架，这是一种通用、灵活且敏捷的框架，基于A启发式搜索算法，在不对LLMs进行任务特定微调的前提下，有效地引导LLMs选择最具前景的下一步推理步骤。更具体地说，我们将为给定问题找到最优推理序列的过程转化为启发式搜索问题，其中每个状态st都关联一个f值，用以估计如果我们扩展st所能获得的效用值：

[ f(st) = g(st) + λh(st), ]

其中g(st)表示从初始状态s1到当前状态st的累积效用，h(st)是从st推导出正确答案的可能性估计的启发值，λ是平衡g(st)和h(st)重要性的系数。

我们提出使用基于过程的奖励函数RP，该函数编码了推理任务的先验知识或偏好来计算累积效用g(st)：

[ g(st) = Agg(RP(s1), …, RP(si), …, RP(st)), ]

其中Agg ∈ {min,max,∑,[−1]}表示聚合函数，用于总结从s1到st路径中的奖励。我们使用状态st的最优Q值作为启发值h(st)，即：

[ f(st) = g(st) + λmax_{at ∈ A} Q∗(st, at). ]

在实际操作中，由于枚举所有可能的下一步推理步骤是不可行的，我们限制备选步骤为LLM返回的top-K候选，并将公式表示为：

[ f(st) = g(st) + λmax_{at ∈ top-K(πθ(·|st))} Q∗(st, at). ]

---

5. 实验 (Experiments)

实验设置 (Experimental Settings)

我们在两个数学推理任务和一个代码生成任务上验证了Q*框架的有效性，数据集的

统计如表所示。

1) GSM8K是一个包含小学数学问题的数据集，解决方案以逐步格式给出，最后一行是精确的数值答案；

2) MATH是一个包含高中数学竞赛问题的数据集，解决方案以LaTeX代码和自然语言混合格式给出；

3) MBPP是一个入门级的Python编程数据集，其中问题是编码挑战，每个问题都有一个测试用例。

实验结果 (Experimental Results)

在GSM8K、MATH和MBPP数据集上的实验结果表明，Q框架能够显著提升现有LLMs的多步骤推理能力，尤其是在无需微调模型参数的情况下，取得了更好的推理效果。具体实验结果如表所示，Q方法与其他验证方法相比，表现出更好的性能，特别是在规划方法的比较中，Q*框架在累积效用的帮助下表现优于其他方法。

---

6. 结论 (Conclusion)

解决具有挑战性的多步骤推理问题需要LLMs超越自回归的token生成方式，进行更深入的审慎推理。本文提出了Q*，一种通用、灵活且敏捷的审慎推理框架。与现有的审慎推理方法不同，Q不需要为每个具体任务设计复杂的效用函数，它仅依赖于真实值来训练Q值模型，能够轻松应用于各种推理任务。此外，通过使用即插即用的Q值模型作为启发函数，Q可以有效地指导LLMs解决不同任务，而无需提前对LLMs进行微调，这避免了在其他任务中性能下降的风险。最后，我们的Q*框架具有敏捷性，因为它每次仅考虑一个步骤，而不是像蒙特卡洛树搜索（MCTS）那样需要完整的回合推理。在数学推理和代码生成任务上的广泛实验验证了我们方法的优越性。