MLNLP 社区是国内外知名的机器学习与自然语言处理社区，受众覆盖国内外NLP硕博生、高校老师以及企业研究人员。

社区的愿景 是促进国内外自然语言处理，机器学习学术界、产业界和广大爱好者之间的交流和进步，特别是初学者同学们的进步。

转载自 | 机器之心

编辑 | Panda

今天是个好日子，DeepSeek 与 Kimi 都更新了最新版的推理模型，吸引了广泛关注。与此同时，谷歌 DeepMind、加州大学圣地亚哥分校、阿尔伯塔大学的一篇新的研究论文也吸引了不少眼球，并直接冲上了 Hugging Face 每日论文榜第一（1 月 20 日）。

这篇论文题为《Evolving Deeper LLM Thinking》，可译为「进化式更深度 LLM 思维」，其中提出了一种进化搜索策略，可用于 scaling LLM 的推理时计算（inference time compute）。该方法被命名为 Mind Evolution，即心智进化。实验表明，在同等推理成本下，新方法的自然语言规划任务表现会显著优于 Best-of-N 和 Sequential Revision 等其它推理策略。

论文地址：https://arxiv.org/pdf/2501.09891

如何实现心智进化

Mind Evolution 采用了遗传搜索策略，并结合了一个 LLM 和定制的提示集，从而可以有效地搜索自然语言规划任务的解。为了理解 Mind Evolution，我们首先需要简单了解基于语言的遗传算法。

基于语言的遗传算法

遗传算法是一种受自然选择启发的元启发式算法。在遗传算法中，候选解种群会朝着包含更多高质量个体的种群方向演化，这里的质量是相对于目标优化目标而言的。这个目标通常也被称为「适应度」函数。每个候选个体都有一个可以突变并与其他个体重组的遗传表示。

演化搜索通常始于独立生成的候选解种群。在每一代中，都会根据目标评估每个个体的适应度。然后基于适应度对候选个体进行随机选择（「选择」）。在繁殖过程中，被选择的父代的遗传表示会进行组合（「杂交」）并可能发生改变（「突变」）以产生新的子代解。这个过程创造了下一代的子代，它们随后进入种群。由于适应度更高的父代更有可能被选择进行重组，种群适应度通常会随着连续几代而提高。

岛屿模型。为了维持演化种群的多样性，还可引入岛屿模型。在该模型中，不同的子种群（「岛屿」）会独立演化，直到按照特定频率发生「迁移」和「岛屿重置」事件。对于迁移操作，一个岛屿上的解会基于适应度被随机选择迁移到相邻岛屿。对于岛屿重置操作，整体适应度较低的岛屿上的种群会被全局种群中的强解替换，这也具有选择效应。最近已经有一些研究成功采用了岛屿模型，如 FunSearch。

基于语言的遗传表示。基于语言的遗传算法中的个体候选解由自然语言表示。这允许通过提示词来利用 LLM 强大的语言理解和生成能力来实现强大的重组（杂交和突变）和岛屿重置操作。

Mind Evolution

Mind Evolution 的设计见图 1，其超参数则见表 1。

Mind Evolution 的核心组件包括：

1. 选择和迁移操作的具体选择；
2. 一个提示集，可使用 LLM 实现初始化、重组（杂交和突变）以及岛屿重置操作；
3. 一个适应度函数，用于评估给定解的质量并可选择性地反馈检测到的问题。

整个演化过程会重复进行，直到找到有效解，或者直到完成 N_gens 代演化，之后返回得分最高的候选解。

适应度评估。该团队为每个问题域实现了一个适应度函数，其中候选解会被解析并以编程方式进行评估。原则上，任何可以评估解质量的函数都可以使用，包括 LLM 评估。

在 Mind Evolution 中，评估函数有三个关键作用：

• 通过衡量优化目标为解评分（如果有的话）；
• 验证解是否满足给定约束；
• 提供相应的文本反馈。

需要注意的是，对于许多经典搜索问题（如 NP 完全问题），验证解比解决问题要容易得多。同样，该该团队观察到，对于所考虑的自然语言规划任务，编写评估函数是可能的。能够检查候选解的正确性并不意味着能在这个任务找到有效解。也就是说，实现评估函数并不等同于解决任务。

种群初始化。给定目标问题，通过向 LLM 提供问题描述、解决问题所需的任何信息以及相关指令，独立采样 N_convs 个初始解。如果 N_seq > 1，则每个初始解都会通过「通过批评性对话进行优化（Refinement through Critical Conversation）」过程的 N_seq - 1 个额外轮次进行评估和改进，该过程将在下文解释。

这个初始化过程一共会生成 N_convs × N_seq 个候选解，它们构成了第一代第一个岛屿上的初始种群。

通过批评性对话进行优化（RCC）。给定一个候选解（或用于重组过程的一组候选解），该团队利用 LLM 通过组织「批评者」角色和「作者」角色之间的批评性对话来生成改进的解，如图 2 所示。

分离这两个角色的目标是提高 LLM 的批判性思维能力。每轮对话都会被构建为一个由提示词驱动的过程，其中解会根据批评性反馈进行改进，类似于 Reflexion。

具体来说，批评者首先会分析输入的候选解，解读文本评估反馈，并建议纠正反馈中提到的问题的方法。然后，作者基于输入候选解、后续评估和批评者的分析提出一个改进的解。

选择。为了产生岛屿的下一代，该团队遵循玻尔兹曼锦标赛选择（Boltzmann tournament selection）方法，其中根据从适应度分数的 softmax 变换得到的概率分布，从种群中随机采样 0 到 N_parent 个父代。通过这种方式，表现更好的解更有可能被选择用于繁殖，而其他候选解仍然可以偶尔被选择以保持多样性。

杂交和突变。该团队将杂交和突变操作实现为单个重组步骤，即指示 LLM 使用上述 RCC 过程来改进给定的一组父代（图 2）。具体来说，对于重组，采样 1 到 N_parent 个父代，并修改图 2 中的步骤（b）以首先纳入父代的评估结果，然后对所有父代应用批评者并将修改后的解作为下一代的「初始解」提出。然后，如果 N_seq > 1，继续遵循步骤（c）（d）（e）顺序生成 N_seq - 1 个子代解，通过使用 RCC 过程改进每个先前的子代。

对于每个岛屿上的每一代，都会将 N_convs × N_seq 个子代解添加到岛屿种群中，并移除重复的解。对于选择，该团队遵循玻尔兹曼锦标赛而不是显式地淘汰候选解，除非执行如下的岛屿重置。

岛屿间迁移。在迁移事件之间，每个岛屿种群独立演化。在迁移期间，在完成当前岛屿上的这一代后，顶部的 N_emigrate 个解从当前岛屿 i 克隆到下一个岛屿 i + 1（该团队按从 1 到 N_island 的顺序顺序更新岛屿上的种群）。迁移在岛屿之间循环进行，所以从岛屿 N_island 的移民会到达岛屿 1。该团队发现这种形式的循环迁移可加速整体演化过程。

岛屿重置。岛屿重置每隔 N_reset 代就发生一次。在岛屿重置事件期间，首先从全局种群中选择表现最好的个体，平均得分最低的 N_reset 个岛屿上的种群被淘汰，选定的表现最好的个体被克隆到重置的岛屿上。为了选择表现最好的个体，该团队探索了两种方法：

• 根据适应度直接选择排名前 N_top 的候选解；
• 首先根据适应度选择排名前 N_candidate 的候选解，然后提示 LLM 从这个池中选择 N_top 个彼此有实质性差异的好候选解。消融研究表明，后一种策略的效果更好。

心智进化的实验表现

任务。该团队在三个基准自然语言规划领域上评估了 Mind Evolution，其中包括来自 Natural Plan 的两个任务（Trip Planning 和 Meeting Planning ），以及 TravelPlanner 基准。

模型。在实验中，该团队使用的默认 LLM 是 Gemini 1.5 Flash（gemini-1.5-flash001）。表 1 给出了将 Mind Evolution 应用于 Flash 时使用的超参数。除了评估使用 Flash 模型的 Mind Evolution 外，该团队还研究了一种两阶段方法，其中对于在 N_gens 代限制内未解决的问题使用 Gemini 1.5 Pro 模型（gemini-1.5-pro-exp-0827）。这种两阶段方法比在每个问题实例上都使用 Pro 模型更具成本效益。

对比基线。对于每个任务，Mind Evolution 都与三种基线搜索策略进行了比较，这些策略使用了相同的解评估器和特定任务的提示词：

1. 1-Pass，其中使用 LLM 的单次前向传递得到解。
2. Best-of-N，独立生成最多 800 个候选解，直到找到成功的解（与 Mind Evolution 上限相同）。
3. Sequential-Revision+，其中独立提出 10 个候选解，然后使用 RCC 过程分别修改 80 轮。注意使用 10 个独立的 80 轮改进线程而不是单个 800 轮改进，因为该团队表示很少能观察到 80 轮后的改进。这个基准方法类似于运行 10 次多轮 Reflexion。

此外，作为参考，该团队还在对比中加入了使用 OpenAI o1-preview 的 1-Pass 基准。

TravelPlanner

TravelPlanner 是一个自然语言规划基准，它模拟的问题是：根据用户给出的偏好和约束条件，为用户组织旅行计划。

表 2 比较了 Mind Evolution 与基线策略的总体成功率和计算成本。

可以看到，在成功率方面，Mind Evolution 明显优于基线策略，超过 95%。相比之下，Sequential-Revision+ 的表现也还行，接近 83%，而 Best-of-N 逊色多了，仅有 55.6%。总的来说，进化策略的优势得到了明显体现。

再来看看上面的两阶段方法，即使用 Gemini 1.5 Pro 处理未被解决的问题，该团队发现几乎整个数据集都可以被解决 —— 在验证和测试问题上分别达到 100% 和 99.9% 的成功率。

该团队表示，唯一接近这个成功率的研究成果是《Large language models can plan your travels rigorously with formal verification tools》（arXiv:2404.11891）—— 该方法使用 GPT-4 进行自动形式化，然后利用形式求解器分别在验证和测试集上达到 98.9% 和 97.0% 的成功率。相较之下，Mind Evolution 完全无需形式求解器。

最后需要注意的是，TravelPlanner 数据集包含三个难度级别（简单、中等、困难）和三个旅行时长（3 天、5 天、7 天），这就形成了 9 个不同的问题类别。图 3 展示了在这些不同类别上的成功率的细分情况。

可以看到 1-Pass 和 Best-of-N 的成功率会在规划更多旅行天数时下降，但对于 Mind Evolution 和 Sequential-Revision+ 这种迭代改进方法，这种趋势不太明显。

Natural Plan – Trip Planning

Trip Planning 任务的目标是找到一个行程安排，其中包含要访问的城市序列以及在每个城市停留的天数，需要满足航班连接性和日程安排约束。表 3 给出了一些问题实例。该团队将基准数据集分为了 320 个验证和 1280 个测试实例。

同样，从表 2 可以看到，Mind Evolution 在这个任务上明显优于基线方法，其成功率在验证集上达到 96.2%，在测试实例上达到 94.1%。

值得注意的是，Best-of-N（77.2%）在这个任务上超过了 Sequential-Revision+（74.4%）。

该团队发现，对于两阶段方法，Mind Evolution 在验证集上的成功率达到了 100%，在测试集上也达到 99.6%。这些发现再次突出了进化搜索相对于简单采样和顺序改进的优势。

最后需要指出，这个任务的难度会随要访问的城市数量而变化，范围从 3 到 10 个城市。图 4 显示了按城市数量划分的成功率细分情况，看起来 Mind Evolution 的相对优势随着城市数量的增加而增加。

Natural Plan – Meeting Planning

Meeting Planning 的任务目标是安排一系列会议以最大化个人之间的会议数量，所涉及的限制条件包括可用性、位置和交通时间。这个任务与 TravelPlanner 和  Trip Planning  的不同之处在于，并非每个问题实例的每个会议都可安排，这意味着无法知道是否已达到最优解。因此，该团队允许搜索继续进行直到达到迭代次数的上限，最终得到了表 2 中的结果。对于这个任务，该团队将实例集分为了 500 个验证和 500 个测试实例。

从表 2 可以看到，Mind Evolution 在验证集上达到 85.0% 的成功率，在测试集上达到 83.8%。值得注意的是，使用 Gemini 1.5 Pro 的两阶段方法在验证和测试上的成功率分别为 98.4% 和 98.2%。

最后，图 5 显示了按需要安排会议的人数划分的成功率细分情况。该团队发现，随着人数增加，Mind Evolution 可保持显著的成功率优势。

实验结果分析

为了理解 Mind Evolution 的 scaling 性能，该团队还进行了更多研究。

scaling 性能。图 6 报告了 Mind Evolution 在规划任务中随着代数增加的成功率变化情况。这些结果清楚地表明， Mind Evolution 会随着代数增加而稳步提升。

为了比较 Mind Evolution 与基线搜索方法的 scaling 性能，该团队还做了每种策略生成的候选解数量与成功率和平均任务评估分数的关系图（图 7-9）。任务评估分数通过对未满足的约束和目标值的次优性进行惩罚来计算，因此在任何问题实例中可以达到的最高分数是零。

图 7-9 分别显示了在 TravelPlanner、Trip Planning 和 Meeting Planning 任务上的结果。在每种情况下，都可以看到所有搜索方法的整体成功率和平均任务评估分数都会随着提出的解数量的增加而单调改善。这些图还表明，就达到指定成功率水平（或平均任务性能）所需的候选解数量而言，Mind Evolution 始终比基线策略更有效。

该团队注意到 Best-of-N 在 TravelPlanner 上的表现明显不佳。该团队认为这是因为该任务涉及隐含的常识约束（例如，旅行计划应该返回出发城市，不能两次访问同一餐厅等），这些约束不在问题实例中给出，而是从评估反馈中学习得到，而 Best-of-N 没有利用这些反馈。

该团队还进行了一系列消融研究，以研究 Mind Evolution 不同组件的效果，具体详情请参阅原论文。

一个高难度新任务：StegPoet

最后，在这篇论文中，该团队还提出了一个具有挑战性的新任务 StegPoet，其中需要将隐藏消息通过隐写术编码到一篇创意写作文章中。

即使这个问题难以形式化，它仍然适合程序化验证，这使得本文考虑的方法可以处理它。

在这个任务中，由数字序列表示的隐藏消息（M）应该被编码在关于特定主题的创意文本中，以散文、故事或诗歌的形式表达。目标是既提供一个数字到单词的替换密码，又生成使用该密码编码消息的文本。

图 10 给出了一个例子。该团队额外施加了一个约束，即在生成的文本中，连续密码词之间必须平均有 B 个单词，这确保当 B > 0 时，简单地将密码词作为文本部分列出不符合作为解的资格。

这个问题的难度在四个维度上变化：

1. 随着隐藏消息 M 的长度增加，难度增加。该团队设定 10 ≤ |M| ≤ 30。
2. M 中数字的重复性。重复越多，约束越严格。
3. 重复数字彼此之间的「接近程度」。每种写作形式都规定了同一个词的重复和出现接近程度的可接受性。LLM 必须在遵守形式和正确编码消息的需求之间取得平衡。
4. 根据经验，随着 B（密码词之间的平均距离）增加，问题变得更加困难。测试中，3 ≤ B ≤ 7。