On the Expressive Power of Transformers

大脑的蓝图：为什么有些谜题更难解？

想象一下，你正在试图教一个机器人如何阅读。你可能会认为机器人只需要像人类扫描页面一样，一个接一个地看字母就行了。但现代超智能机器人（被称为大语言模型，LLMs）并不这样工作。它们不是从左到右阅读，而是使用一种被称为“Transformer”的特殊技巧。把 Transformer 想象成一个在房间里工作的庞大侦探团队。当他们看到一个句子时，每个侦探都可以瞬间向其他所有侦探喊话：“嘿，我正在看这个词，它和那边那个词有关联！”这使得他们能够瞬间理解上下文和关系，而不是仅仅死记硬背规则列表。

但这里有一个让科学家们彻夜难眠的大问题：这些侦探到底有多聪明？他们能解决任何谜题吗，还是说有些谜题注定会让他们束手无策？为了找到答案，研究人员不仅进行测试，还通过计算机科学数学的角度来观察机器人的“大脑”。他们将 Transformer 与被称为“电路”的一类数学机器进行比较。把这些电路想象成拥有装配线的工厂。有些工厂非常简单，只有短长的生产线和很少的工人（这些被称为 AC0）。另一些则有更长的生产线和更强大的工具，可以计数和比较巨大的数字（这些是 TC0）。通过弄清楚 Transformer 更像哪种工厂，科学家可以准确预测它能解决哪些类型的问题，以及在哪里撞到天花板。这很重要，因为如果我们知道了这些模型的极限，我们就能停止期望它们展现魔法，转而开始构建那些真正擅长做事的模型。

论文的大发现：Transformer 的动力开关

在他们的论文《论 Transformer 的表达能力》（On the Expressive Power of Transformers）中，研究人员 Phokion G. Kolaitis 和 Rik Sengupta 扮演着检查一座新型高科技建筑的建筑师角色。他们不仅仅是在观察建筑有多漂亮，还在测量其承重能力，以精确了解它能承载什么。他们的主要发现是，Transformer 的力量并不是固定的；它会根据几个“旋钮”或设置发生剧烈变化，具体来说是精度（它可以使用多少位小数进行数学运算）以及是否允许它**“大声思考”**（一种被称为“思维链”，Chain-of-Thought 的技术）。

首先，让我们看看没有任何额外思考时间的 Transformer。作者解释说，如果你给 Transformer 一个简单的、“硬性”注意力设置（即它只选择一个词来关注），或者如果你限制它的数学精度（例如仅使用极少量的比特信息），它会表现得异常脆弱。事实上，在这些条件下，Transformer 在数学上等同于最简单的电路工厂 AC0。这意味着它可以处理基础逻辑，比如检查一个句子是否有偶数个单词，但它在处理需要计数或比较大数字的任务时会感到吃力。这就像一个能发现红帽子的侦探，却数不出房间里有多少顶红帽子。

然而，当你调高精度时，故事变得有趣得多。如果允许 Transformer 使用更精确的数学（具体来说是随着文本长度增长的比特数，如 $\Theta(\log n)$），它就会升级。它变得像 TC0 电路工厂一样强大。这是一个显著的飞跃！现在，Transformer 可以处理“多数问题”和更复杂的计数任务。这就像是给了侦探一台计算器；突然之间，他们就能解决以前无法解决的谜题。但即便有了这次升级，论文也暗示仍然存在一个天花板。如果没有额外的帮助，这些模型很可能被困在 TC0 领域，无法轻易解决在更复杂的计算机类别（如 PTIME，多项式时间）中发现的深层、循序渐进的逻辑推理问题。

根据论文，真正的游戏规则改变者是思维链（CoT）。想象一下，Transformer 不再仅仅是一个观察犯罪现场的侦探；现在，它被允许在给出最终答案之前写下自己的思想日记。它可以生成中间“标记”（即小笔记），并将其反馈给自己以帮助解决问题。作者展示了这一简单的改变打破了之前的限制：

• 如果允许 Transformer 写一篇短日记（与文本长度成比例，即 $O(n)$），它可以解决需要平方时间（如 $n^2$）的问题。
• 如果它可以写一篇很长的日记（与文本长度的多项式成比例，即 $poly(n)$），它就变得足够强大，可以模拟任何标准的计算机算法，达到 PTIME 类。
• 如果它拥有无限的思考空间和精度，它可以模拟一台图灵机，这是能够解决任何可计算问题的通用计算机的理论定义。

论文非常明确地说明了这意味着什么：Transformer 本身既不是“全能的”，也不是“无用的”。它解决难题的能力完全取决于你给它多少“草稿纸”（思维链）和多少“数学精度”。如果没有这些资源，它就局限于简单、浅层的逻辑。有了它们，它可以沿着复杂性的阶梯攀爬，一直达到模拟完整计算机的高度。

作者还指出了一些具体的局限性。他们认为，“硬”注意力模型（即机器人只选一个词的模型）严格弱于“软”注意力模型（即它会权衡许多词的模型），在某些情况下甚至无法达到最简单电路类的完整力量。此外，他们强调，虽然 Transformer 在理论上有足够的思维链来模拟图灵机，但这只是一个理论极限。在现实世界中，我们没有无限的内存或无限的时间来生成无限的中间想法，因此现实世界的模型总会有一个低于理论最大值的实际天花板。

简而言之，Kolaitis 和 Sengupta 绘制出了 Transformer 的“电网图”。他们向我们展示了这些模型不是神奇的黑匣子，而是受资源限制的机器。如果你想让它们解决难题，你不能只是要求它们“更努力地尝试”；你必须给它们正确的工具：更多的精度、更多的层级，以及最重要的——循序渐进思考的能力。论文总结道，理解这些极限至关重要。这有助于我们停止期望它们去做不可能的事，转而开始设计它们，使它们成为它们所能达到的最佳版本：极其强大、但终究是有界的模式识别器。