Cheng Tan

万事皆搜索

系列「太阳底下无新事」第二篇——计算机科学的那几个老想法

· systemsaiphilosophy

这个系列的第一篇，讲的是同一份工绝不付两次全价。这一篇要讲的，是藏在最多论文里、却最少被点名的那个想法。把一篇系统论文剥到只剩骨架，你多半会看见同一个两件套：一个候选答案的空间，和一套在空间里行走的办法。搜索。

这两件东西值得分开握着，因为一份贡献只可能落在这两处。空间，是哪些答案压根可以被表达——你能排出的每一张调度表，你能执行的每一个方案，你能施加的每一种次序。行者，是你如何在其间移动：贪心地，穷举地，随机地，聪明地。我所知最干净的一次校准，是 AlphaGo。围棋的空间由规则定死——每一手约 250 种合法着法，一局约 150 手深，合法棋局约 2×10^170 个。造出来的，是一个更好的行者：一棵搜索树，宽度由策略网络收窄，深度由价值网络截断。对阵樊麾时，AlphaGo 评估的局面数，比当年深蓝对卡斯帕罗夫时少了数千倍。胜利不在于搜得更多。在于搜得更少、更准。

把「空间」与「行者」这样掰开，相当一部分系统研究便自动归了位：贡献空间，贡献行者，或两者兼有。

调度：永不谢幕的搜索问题

从这个领域的常青题说起。调度与资源分配，自 1975 年一般形式被证明 NP 完全起，就正式无望了——偏偏又完全绕不开，所以每一代系统研究者都会再遇见它，只是换了新衣。细看「新衣」究竟指什么，答案总是同一件事：空间变了。新负载铸出新空间：云计算让候选摆放弹性起来，无服务器让它们朝生暮死，大模型推理把它们焊在 GPU 显存上。新硬件重塑空间，开出从前没有的取舍。新目标为空间重新配重：把优化对象从单纯的延迟换成功耗或碳排——机器没变，作业没变，「更好」换了定义——旧日的走法便纷纷落在了不同的地方。

一个鲜活的例子是我自己的一件工作，围绕 NVIDIA 的 Multi-Instance GPU（MIG）。MIG 允许把一块物理 GPU 切分成大小不一的实例，这悄悄打破了调度的一条立国假设：机器不再是固定的容器。它的形状，成了你要选择的东西之一。我们把抽象出的版本命名为可重构机器调度问题——自然是 NP 难的——然后用一串行者去走它：贪心搜索，遗传算法，以及，恰如其分地，蒙特卡洛树搜索。后续两篇也可以用同一副眼镜读：一篇理论文章，钉死任何行者在这个空间里至多能走多好；一个实际系统，按效用优先去搜，并在不停机的情况下重构集群。三篇论文，各一句话：这是新空间；这是任何行者的上界；这是一个在实践里活得下来的行者。

校验也是搜索

验证看起来像这一切的反面——没有候选，没有探索，只有一纸裁决。把量词一翻，相似性立刻咬合。我手头最清楚的例子还是自己的：Cobra 检查一个黑盒数据库的行为是否可串行化，而「可串行化」的定义是存在性的——一段历史通过检查，当且仅当存在一个与观测到的每次读写相容的事务串行顺序。校验，就是在一个 NP 完全的空间里搜索那个证人。我们没有手工打造行者；我们把空间交给了一个擅长图问题的 SMT 求解器，自己的力气花在求解器看到空间之前，先把它缩小。早先的一篇论证过，AI 的正确性也是这个存在性的形状：一个输出是正确的，当某次合法运行能解释它。又是同一个对象。要接受，找到一个证人即可；要拒绝，得走遍全空间。验证，是赌注反转了的搜索。

从洞见到求解器

再看行者们这三十年的变迁，因为这个领域改了习惯，却几乎没有声张。

经典的系统论文靠手走空间：盯住问题，找到洞见，把洞见冻进一条启发式，再由评测加冕。新派的论文做的是另一件事：把问题写成一个有原则的形式化——集群调度写成最小费用流，时空摆放写成混合整数规划，Google 闪存缓存背后那个已在生产环境跑了多年的背包问题——然后花钱雇一个通用行者来代步。这之所以变得可行，是因为行者工业化了：SAT 求解器在九十年代末变得实用，SMT 求解器把整套理论收进一个接口，「NP 难」悄悄不再意味着「写一条启发式」，而开始意味着「调一个求解器」。难度从未挪动半分。挪动的是：最坏情形的指数，在观测到的情形里变得可以过日子——只要那个行者，是别人替你攒了十年的工程。

我不想把这道分野说过头——形式化本身仍然吃洞见，许多出色的系统也仍是手作。但趋势清楚：我们不再雕刻行者，改为租用行者。

搜索「搜索者」的机器

于是轮到 AI，以及那个领域最古老的主张。这不是民间传说，而是 Newell 与 Simon 摆在图灵奖演讲正中央的假设：「物理符号系统在解决问题时施展其智能的方式是搜索——即，不断生成并逐步修改符号结构，直至产出一个解结构。」照这个看法，智能不是被搜索点缀的；智能以搜索运转。五十年后，这个领域最锋利的自我批评从另一头说出了同一句话：七十年 AI 研究的苦涩教训是，唯二随算力扩展的方法，是搜索与学习。

所以当 AI 终于大举进入系统研究时，它注定不是天外来客；这是搜索与搜索的会师。有意思的是它进入的位置。它没有加入解空间里的行走。它上移了一层。FunSearch——名字是字面意思，「在函数空间里搜索」——把语言模型和一个校验器配成对，用其作者的话说，「搜索的是描述如何解决问题的程序，而不是解本身」。它的工业后裔 AlphaEvolve，演化出了那条已在生产环境为 Google 打包机群一年多的调度启发式。模型交出的不是一张调度表，是一个调度器。给这个模式起个名字，叫元求解器：搜索不再返回一个用一次就耗尽的答案，而是返回一个可以永远摊销的行者。读过第一篇的读者会认出这笔账——答案是花掉的，求解器是留下的，第二遍更便宜。

你敢在哪一层搜索

退后一步，这三十年的弧线是同一个动作的重复。起初我们亲手搜索答案。后来我们搜索形式化，把行走外包。如今我们搜索「搜索者」本身。空间在变，行者在变，层级在变——动作从未变过。如果 Newell 与 Simon 说得对，智能就是这个动作，那么计算的历史，便是沿着它一层层向上爬的历史——每爬一层，就把下面那层交给机器。

所以老话依然成立：太阳底下，并无新事。但让我把口号说准。「万事皆搜索」不是说万事皆蛮力——AlphaGo 赢，靠的是比深蓝评估得更少。这场游戏，在每一层，从头到尾都是同一件事：知道哪里不必看。

参考文献