一种已有数十年历史的衡量算法复杂度的方法，可能为更好地理解 AI 系统如何进行计算提供一扇窗口。
20 世纪中叶，随着可计算性理论和图灵机等模型的发展，计算机算法研究实现了重大飞跃。图灵机由 Alan Turing 发明，用于形式化定义一个问题可计算的含义，它是一种简单的抽象计算模型，使用算法——用于解决问题的逐步指令——来处理信息。一个算法可以像按照食谱烤蛋糕一样简单，也可以像 Dijkstra 算法一样复杂，后者用于寻找图中节点之间的最短路径。这些理论突破为今天我们所看到的算法系统性研究奠定了基础。
这些进展促成了计算复杂度理论的诞生；这是一个专注于量化实现算法所需资源（如时间和内存）的子领域。计算复杂度理论为根据问题固有难度来研究问题提供了基础，引入了一种将问题分类为复杂度类的结构化方法。科学家随后可以确定哪些问题能够用特定的计算模型求解。
然而，随着我们进入以大语言模型（LLM（大语言模型））为代表的现代 AI 时代，一个新的悖论出现了：现代 AI 模型无疑是强大的计算模型，但我们目前缺乏一个系统性的理论框架来理解其计算复杂度。与传统算法不同——传统算法的行为可以在定义良好的计算复杂度层级中精确分析——AI 模型从非结构化数据中学习复杂函数，而这些函数往往难以用形式化和有原则的术语来刻画。
将算法作为洞察 AI 能力的窗口
在今天发表于 Nature Machine Intelligence 的一项新研究中，我们从理论计算机科学的基础中汲取灵感，以将现代 AI 计算与数十年来研究算法复杂度的传统连接起来。通过算法研究现代 AI 能够计算什么，提供了一种清晰、系统的方式来评估其能力，包括其问题求解策略的正确性和效率。
在计算复杂度中，将算法形式化为计算模型的一种主流方法是使用电路。在电路复杂度理论中，算法被表示为可计算电路模型，其中逐步算法通过遍历该电路来实现。可计算电路模型的一个常见领域是计算算术表达式。这些表达式可以表示为一个电路（或有向无环图），其中当人们遍历各种运算（如加法和乘法）时，算术运算会被计算出来。
重要的是，在这些电路计算模型中，可以通过研究其结构来明确量化算法复杂度，例如电路深度——这是由 IBM Research 的 Charles Bennett 提出的概念。通过逐步测试 AI 模型计算不同复杂度电路问题的能力，我们可以探测并量化 AI 系统的算法局限性。
在一个具有涌现推理能力的前沿 AI 模型层出不穷的时代，系统性地理解这些 AI 模型的能力变得愈发重要。近期工作表明，大型推理模型（LRM）——它们在得出答案之前会生成逐步的思维链——已在基准研究中带来整体改进。尽管基准性能有所提升，但这些模型展示出的实际“推理步骤”往好了说是难以验证，往坏了说则常常是错误的且毫无意义。的确，如果 LRM 通过错误的思维过程得出基准任务的正确答案，这表明它们可能存在一种潜在危险的“理解错觉”，从而掩盖其能力中的严重缺陷。
一种解决方案是在算法上评估这些前沿 AI 系统的性能——这些问题是已知复杂度的，且具有可验证的输出和中间步骤。这将有助于阐明其计算能力，同时使它们与帮助塑造现代计算的其他基础计算模型处于同等地位。引入电路复杂度理论中的工具和概念，使得对原本不透明的现代 AI 系统进行系统性和算法化分析成为可能。这种方法不仅有助于揭开其内部推理的神秘面纱，还能为指导未来架构创新的基准提供严格框架。
理论计算机科学与前沿 AI 的融合形成了一个强大的交汇点，其中复杂度理论的工具通过精确的算法语言，为分析和解释 AI 系统提供了一种结构化方式。这种日益增强的协同作用不仅有可能加深我们对当前模型的理解，还为未来构建更强大、更高效且更可信的 AI 系统提供了有原则的基础和蓝图。
转载声明：本文为转载整理，原文版权归原作者及原站点所有。
原文来源：IBM Research Blog
原文作者：Takuya Ito；如有侵权，请联系管理员删除。
