Interference Search: Reachability-Preserving State Merging and Learned Pruning for Parallel Reasoning Search
本文介绍了干扰搜索（Interference Search），这是一种通过同步扩展前沿并合并等价状态来通过实现指数级的表示节省，同时在证明保持目标可达性的同时，在 Countdown 和 MBPP 等任务上展示出相比传统线性搜索方法显著的性能提升的并行推理框架。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在人工智能领域，大型语言模型常被想象成孤独的思考者，生成一条单一且连续的文本流来解决问题。这种被称为“推理迹线”（reasoning trace）的方法在处理简单任务时表现良好，但在面对需要探索多种不同可能性的问题时却显得力不从心。想象一下，你正试图寻找走出复杂迷宫的方法，并记录下你走的每一步；如果你撞到了死胡同，你必须回到起点重新开始，并带着所有失败尝试的历史记录继续前进。这种方法效率低下，因为它将每一次尝试都视为独特的，即便两条不同的路径最终都通向了迷宫中的同一个位置。研究人员现在正在探索如何让这些人工智能系统变得更聪明，通过识别出不同的思考路径何时收敛到了相同的境况，从而让系统能够停止重复劳动，并将精力集中在接下来的步骤上。
一组研究人员开发了一种名为“干扰搜索”（Interference Search）的新方法来解决这一特定的低效问题。该方法不再让人工智能在单条路径或互不沟通的独立分支树中徘理，而是将问题视为一系列截然不同的状态或情境。当人工智能探索不同的行动时，系统会检查两条不同的推理线路是否落在了完全相同的状态上。一旦发生这种情况，系统就会将它们合并为一个具有代表性的单一状态，并丢弃重复的历史记录。这个过程并非基于猜测，而是一种严谨的检查，旨在确认当前的情况是否与之前访问过的某个状态完全一致。通过这种方式，人工智能可以极大地扩展其搜索范围，而不会耗尽内存或时间，因为它不再浪费精力在多个相同的未来可能性副本上。
研究人员使用一个被称为“倒数”（Countdown）的经典数学谜题测试了这一想法，其目标是利用一组起始数字和基础算术运算达到一个目标数字。在这个环境中，所谓的“状态”就是当前可用的数字集合。团队发现，不同的运算序列经常会导致完全相同的数字组合。例如，以不同的顺序对两个数字进行加法运算，可能会得到相同的中间总数。在针对六个数字问题的实验中，系统生成了超过 831,000 条不同的路径，但这些路径最终坍缩成了仅 13,229 个不同的状态。这意味着，平均而言，有超过 62 条不同的路径指向同一个单一情境。通过合并这些重复项，系统能够比那些保持每条路径独立的传统方法更有效地探索问题空间。
为了确保这种合并不会意外地丢弃解法，研究人员通过数学证明：只要我们对“相同性”的定义能够保留到达目标的能力，那么任何有效的解都不会丢失。他们表明，只要合并后的状态允许进行与原路径相同的后续动作，搜索过程就是完整的。然而，他们还引入了第二层控制机制：一个经过学习的“裁判”。这是一个专门训练用于预测哪些状态可能是死胡同的独立人工智能。研究人员非常谨慎地将“精确合并相同状态（这是安全的）”与“剪枝掉不太可能的状态（这带有风险）”区分开来。如果裁判过于激进，它可能会切断一条原本可以通向解法的路径。研究结果显示，虽然这种剪枝可以大幅减少系统的计算量，但需要维持一种精细的平衡，以避免失去解决困难问题的能力。
当研究人员将这种合并方法与遵循单一推理线的标准方法进行对比时，差异显而易见。在一组包含 30 个困难四数字问题的测试中，单线方法在特定的努力限度内仅解决了 30 个问题中的 21 个。而使用“干扰搜索”方法的系统，在投入同样程度的努力下，解决了全部 30 个问题。此外，它达到解法所需的步骤也更少，这表明如果系统在并行硬件上运行，其解决问题的速度会更快。在另一项包含 100 个六数字问题的大规模测试中，合并后的方法解决了 77%，而未合并的版本仅解决了 50%。这些数据表明，推理路径中的冗余不仅是一个小问题，更是一个严重的瓶颈，而这种新方法成功地消除了这一瓶颈。
这项研究还探讨了该方法是否能应用于代码生成——这是一个比数学谜题复杂得多的任务。在一项涉及编程挑战的初步测试中，该方法展现出了潜力，它能够识别出许多生成的程序在功能上是相同的并将其合并。然而，研究人员对此结论持谨慎态度。由于样本量过小，其方法与其他方法之间的成功率差异并不显著，因此无法得出定论。他们强调，虽然在数学这种“状态定义精确”的领域中合并状态的概念行之有效，但在处理像编写代码这样开放式的任务时，情况会变得困难得多，因为两个程序可能在某些测试中表现一致，但在其他测试中表现却大相径庭。
最终，这项工作证明了人工智能组织其搜索方式的方式与其利用智能生成想法的能力同样重要。通过将关注点从“如何到达一个状态的历史”转向“状态本身”，并通过严格合并重复项，研究人员展示了人工智能可以实现更高效的推理。研究结果表明，未来的系统可以受益于将“提出想法的行为”与“管理搜索空间的行为”相分离，从而让人工智能在不被自身冗余思绪困扰的情况下，探索更广泛的可能性。虽然该方法并非适用于所有类型的“万灵药”，但它为使推理系统在不同路径往往指向同一终点的领域中变得更加强大，提供了一种具体且经过验证的方法。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。