FunSearch 在公开数学问题上给出新结果

背景

2023年12月14日，《自然》（Nature）发表了 FunSearch，并同时给出了它在两个问题上的结果^[1]。第一个是 cap set 问题，这是极值组合学（extremal combinatorics）中的一个核心问题^[1]。极值组合学关心的是：在避开某些禁止结构的条件下，一个集合或结构最多能有多大；cap set 问题正是这一领域的核心问题之一^[1]。第二个是在线装箱（online bin packing），它是一个有实际调度用途的算法问题^[1]。在线问题要求算法在输入逐步到来时做决定，不能预知后面的输入；装箱则涉及在容量限制下把物品放进箱子^[1]。这两个问题性质不同：一个是关于极值结构的数学问题，另一个是调度中的算法问题^[1]。

发生了什么

最核心的结果是比较性的：在这两个问题上，搜索得到的结果都优于此前已知的最好结果^[1]。FunSearch 并不是直接输出一个答案就结束的求解器。与多数计算机搜索方法不同，它不直接搜索候选解^[1]。论文标题把这种方法描述为结合大语言模型（large language model, LLM）的程序搜索（program search）^[1]。也就是说，被搜索的对象是程序或过程，而不是单个候选答案^[1]。作者由此得出结论：用大语言模型在已经确立的公开问题上做出发现是可能的^[1]。

关键细节

搜索解和搜索程序的区别，是理解 FunSearch 的关键^[1]。如果直接搜索候选解，每个候选就是一个针对问题的答案^[1]。如果搜索程序，每个候选则是一段可以生成或检验答案的过程^[1]。论文明确指出的差异是否定性的：FunSearch 不直接搜索候选解^[1]。论文标题给出了肯定的一面：它是程序搜索，并与大语言模型结合^[1]。程序可以被反复运行、检查和修改，答案则只是一个单独的对象；因此搜索空间的单位从答案变成了可复用的过程^[1]。这也是为什么可以把这种方法理解为对程序的搜索，而不是对答案列表的搜索^[1]。

为什么重要

这些结果之所以重要，首先是因为它们在此前最好结果之上取得了更好的结果^[1]。其次是因为作者的结论：用大语言模型在已经确立的公开问题上做出发现是可能的^[1]。这个结论并没有说大语言模型可以解决一般意义上的数学问题^[1]。它绑定的是论文报告的这两个问题^[1]。但它仍然提供了一个具体案例：围绕大语言模型构建的计算机搜索，被用在了已经作为公开问题存在的研究问题上^[1]。因此，它的意义既是具体的，也是方法上的：具体之处在于比较对象是 cap set 和在线装箱此前已知的最好结果，方法之处在于搜索作用于程序，而不是直接作用于解^[1]。