K-文化的一切——从回归到 K-美妆，发送到您的邮箱订阅邮件

METAL MEDIA

On the Expressive Power of Transformers

arXiv:2608.126712026-08-14

用电路复杂度这把尺子,精确测量Transformer到底有多强

这篇论文是一篇综述,梳理了当今几乎所有大语言模型核心结构Transformer在计算能力上的边界,使用电路复杂度理论作为衡量标准。文章把Transformer形式化为语言识别器,展示了注意力类型和数值精度等设置如何决定它们落入哪个电路复杂度等级。文章还指出,加入思维链推理可以让Transformer的能力远超这些限制,甚至能模拟任意图灵机。

METAL MEDIA 解读图

用电路复杂度这把尺子,精确测量Transformer到底有多强

  1. 01论文将Transformer正式定义为语言识别器,区分编码器(输出接受或拒绝的判断)和解码器(自回归地逐个生成词元)。
  2. 02论文没有用经典的自动机理论或乔姆斯基谱系,而是采用电路复杂度,因为Transformer是并行的、层数固定的计算过程,更适合与布尔电路或阈值电路做类比。
  3. 03论文汇总了已有结果:注意力机制是硬注意力还是softmax注意力、内部计算用多少位精度,决定了Transformer的能力落在AC0还是更大的TC0这一电路等级。
  4. 04在没有思维链的情况下,Transformer的表达能力大体被限制在TC0之内;但配合长度递增的思维链,Transformer可以达到LOGSPACE、PTIME,若思维链长度不受限,甚至能模拟任意图灵机。
  5. 05这篇论文本身不提出新定理,而是把该领域已有的多项研究成果整合成一个统一的综述框架。
这是 METAL MEDIA 制作的解读图，并非论文作者提供的原图。

他们做了什么

  1. 论文将Transformer正式定义为语言识别器,区分编码器(输出接受或拒绝的判断)和解码器(自回归地逐个生成词元)。
  2. 论文没有用经典的自动机理论或乔姆斯基谱系,而是采用电路复杂度,因为Transformer是并行的、层数固定的计算过程,更适合与布尔电路或阈值电路做类比。
  3. 论文汇总了已有结果:注意力机制是硬注意力还是softmax注意力、内部计算用多少位精度,决定了Transformer的能力落在AC0还是更大的TC0这一电路等级。
  4. 在没有思维链的情况下,Transformer的表达能力大体被限制在TC0之内;但配合长度递增的思维链,Transformer可以达到LOGSPACE、PTIME,若思维链长度不受限,甚至能模拟任意图灵机。
  5. 这篇论文本身不提出新定理,而是把该领域已有的多项研究成果整合成一个统一的综述框架。
Figure 1: A high-level view of the encoder architecture.
Figure 1: A high-level view of the encoder architecture.
𝐲i=𝐖(O)​(∑j=1nαi,j​𝐯j),𝐯j=𝐖(V)​𝐱j,αi,∗=𝒮⁡(si,∗),(1)
si,j=𝐪i⊤​𝐤jdkey,𝐪i=𝐖(Q)​𝐱i,𝐤j=𝐖(K)​𝐱j.(2)
Figure 2: An encoder (left) and a decoder (right).
Figure 2: An encoder (left) and a decoder (right).
(𝐲1(ℓ),…,𝐲n(ℓ)):=∑h=1H𝗌𝖺(h,ℓ)​(𝐱1(ℓ−1),…,𝐱n(ℓ−1))+(𝐱1(ℓ−1),…,𝐱n(ℓ−1)),
(𝐱1(ℓ),…,𝐱n(ℓ)):=(𝖿𝖿(ℓ)​(𝐲1(ℓ)),…,𝖿𝖿(ℓ)​(𝐲n(ℓ)))+(𝐲1(ℓ),…,𝐲n(ℓ)).
F𝒯0​(w):=w
F𝒯i​(w):=F𝒯i−1​(w)⋅F𝒯​(F𝒯i−1​(w))​ for ​i≥1,

为什么重要

理解这些计算能力的边界,有助于说明为什么大语言模型在某些任务上表现出色而在另一些任务上存在根本性局限,这对合理设定模型能力预期很有实用价值。同时也表明思维链不只是一种提示技巧,而是能在形式意义上真正扩展模型的计算能力。

本文术语

  • 电路复杂度(circuit complexity) · 研究由AND/OR/NOT等逻辑门组成的电路能多高效地解决计算问题的理论分支
  • AC0 / TC0 · 由深度固定的逻辑电路能解决的问题集合;TC0额外允许多数表决门,因此能力比AC0更强
  • 硬注意力 / softmax注意力 · 硬注意力只关注得分最高的位置,而softmax注意力(实际大语言模型使用的方式)会对所有位置分配加权概率
  • 精度(precision) · 模型内部计算所用的比特数;精度过低会限制表达能力,对数级精度则足以支持加法等运算
  • 思维链(Chain-of-Thought, CoT) · 模型在给出最终答案前先生成一系列中间推理词元,并将其重新输入以继续计算的方法

论文原文摘要（英文）

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

作者 · Phokion Kolaitis, Rik Sengupta

在 arXiv 阅读

最新论文

全部论文 →

METAL MEDIA 最新报道

图片来源： Phokion Kolaitis et al., arXiv:2608.12671, CC BY 4.0