论Transformer的表达能力

# 论Transformer的表达能力

来源：https://arxiv.org/html/2608.12671

Phokion G. Kolaitis
单位：加州大学圣克鲁兹分校
单位：圣克鲁兹，加州
邮箱：[[email protected]](mailto:)

2026年8月

###### 摘要

多层Transformer本质上构成了当今几乎所有大语言模型（LLM）的关键组成部分。由于其普遍性和计算能力，越来越多的研究工作致力于通过将Transformer与理论计算机科学界数十年来研究的标准计算模型进行比较，来精确校准Transformer作为语言识别器的表达能力。在这一努力中，电路复杂性在很大程度上已成为分析Transformer表达能力的“正确”计算复杂性分支；其原因在于，通过Transformer所使用的各种资源（如注意力和精度）对其进行参数化，可以直接与按资源（如门类型、大小和深度）参数化的不同电路类别进行比较。在此，我们使用电路复杂性的概念和方法，对界定Transformer表达能力的部分成果进行了概述。

关键词：Transformer；计算模型；电路复杂性。

###### 目录
1. [引言](#S1)
2. [架构](#S2)
    1. [Transformer作为语言识别器](#S2.SS1)
    2. [Transformer的特征与参数](#S2.SS2)
    3. [编码器计算](#S2.SS3)
    4. [解码器计算](#S2.SS4)
3. [经典复杂性与电路复杂性](#S3)
    1. [“正确”的层级结构](#S3.SS1)
    2. [定义](#S3.SS2)
    3. [描述复杂性](#S3.SS3)
4. [表达性结果](#S4)
    1. [无思维链](#S4.SS1)
    2. [有思维链](#S4.SS2)
5. [结论](#S5)
6. [参考文献](#bib)

## 1 引言

Transformer已成为现代大语言模型（LLM）的默认计算基底，然而其形式化能力至今仍最多只能算是部分被理解。对于逻辑学和计算复杂性的研究者而言，这既是挑战也是机遇：将这一取得非凡经验成功的架构形式化，以便将其作为一族受资源约束的计算模型来研究，并将其能力与标准计算模型背后的经典层级结构进行比较。事实上，近期大量文献正是致力于这一方向。通过将序列长度、深度、注意力头数、数值精度、位置编码等视为显式资源，可以得到Transformer的各种变体，其表达能力可与自动机和电路类别的表达能力相关联。本简评聚焦于将Transformer作为语言识别器，以及它们与电路复杂性之间的联系。其基本原理是，注意力层的行为类似于结构化的并行计算阶段，这使得它们可以与具有门类型、扇入、大小和一致性限制的有界深度电路进行比较。这一视角既阐明了Transformer能模拟什么，也揭示了其局限性所在。它还揭示了在架构设置中的微小选择——硬注意力与软注意力、固定精度与无限精度等等——如何显著影响表达能力。我们的目标是仔细建立形式化架构，着重介绍迄今为止已确立的部分成果，并让读者领略一些证明技术的风格。如需更详细的综述，我们建议读者参阅该领域的其他几本综合调查，包括关于神经网络与形式语言[1](https://arxiv.org/html/2608.12671#bib.bib6)、RNN与Transformer[21](https://arxiv.org/html/2608.12671#bib.bib7)、Transformer表达性[24](https://arxiv.org/html/2608.12671#bib.bib8)以及Transformer手册[29](https://arxiv.org/html/2608.12671#bib.bib9)的综述。

## 2 架构

### 2.1 Transformer作为语言识别器

在正式描述其每个组成部分之前，我们先非正式地描述Transformer架构，以便确立Transformer如何充当语言识别器。Transformer可以被视为一种特定的神经网络，由一个输入层、一个或多个隐藏层以及一个输出层组成。Transformer的输入是某个字母表Σ上的非空输入字符串，其长度n称为*上下文长度*。输入字母表的每个字符称为一个*词元*（在实践中，词元通常是子字符串而非单个字符；输入文本通过一个非常重要的过程——称为*词元化*——被分解为词元，这超出了本综述的范围）。Transformer的输入层通过将每个词元映射为一个d维实向量，将其嵌入到向量空间中，其中d是Transformer的一个参数。此后，每个隐藏层将长度为n的d维实向量序列作为输入，并对该序列应用一个*长度保持*的函数，得到长度为n的d维实向量序列作为该层的输出。输出层根据所考虑的Transformer类型而有所不同。

- 在Transformer*编码器*（将Transformer视为*分类器*时所采用的模型）中，输出层将最终的d维向量序列转换为单个概率p_out∈[0,1]，并且当且仅当p_out≥1/2时*接受*输入字符串。
- 在Transformer*解码器*（将Transformer视为*语言模型*时所采用的模型）中，输出层输出一个新词元[^1]，将其附加到原始输入之后，然后以*自回归*的方式继续这一过程，即在预先指定的时间步数内，通过消费先前时间步生成的所有词元来顺序生成新词元。这是用于文本生成的Transformer版本。此外，解码器也很容易转变为语言识别器：在最终时间步，它的行为类似于编码器，输出一个概率p_out（而不是一个新词元），并且当且仅当p_out≥1/2时*接受*原始输入字符串。

[^1]: 新词元可以被视为从Σ上的一个隐式概率分布中抽取。该分布在训练过程中被有效学习，并编码在模型的架构中，因此模型的输出过程是完全确定性的。然而，在实践中，最终词元通常使用诸如Top-K采样或Top-p采样[11](https://arxiv.org/html/2608.12671#bib.bib28)之类的解码过程来选择，这些过程在采样之前限制候选集；因此前向计算是确定性的，而实际输出可能是随机的，除非使用贪心解码或固定的随机种子。

### 2.2 Transformer的特征与参数

我们现在准备正式描述Transformer架构。首先，每个Transformer都有几个特征。

#### 硬/软注意力。
Transformer语言的丰富性来自隐藏层内部的一种称为*注意力*的机制[26](https://arxiv.org/html/2608.12671#bib.bib23)，它本质上是一种缩放的点积，用于组合序列中不同向量的信息。定义注意力的突破性想法在于认识到，模型不需要仅以固定顺序处理语言，也不必将所有内容压缩到单一隐藏状态中。相反，每个词元可以直接“查看”一个足够长序列中的其他词元，并决定哪些词元最相关。这使得模型在捕捉长距离关系方面表现更好，更容易并行训练，并且可以扩展到更大的系统——这基本上为现代Transformer和大语言模型奠定了基础。对注意力机制的假设构成了Transformer行为的一个核心区分特征。注意力可以是*硬*的或*软*的，其中后者往往比前者具有更强的表达能力[9](https://arxiv.org/html/2608.12671#bib.bib24)、[10](https://arxiv.org/html/2608.12671#bib.bib12)、[22](https://arxiv.org/html/2608.12671#bib.bib16)、[17](https://arxiv.org/html/2608.12671#bib.bib14)、[16](https://arxiv.org/html/2608.12671#bib.bib25)。注意力的标准选择包括UHAT（“唯一硬注意力”）、AHAT（“平均硬注意力”）和SMAT（“softmax注意力”），其中只有最后一种在实践中被广泛使用。

#### 掩码/无掩码。
在编码器中，我们通常假设一个无*掩码*的模型，这意味着每个位置可以*先验地*关注所有其他位置。相比之下，在解码器中，我们通常假设一个使用*未来掩码*的自回归模型，其中位置只能关注其之前的位置。LLM的演进已看到从编码器模型（如BERT）向解码器模型（如GPT、Claude、Gemini、LLaMA）的转变，这是因为后者的自回归特性可用于文本生成。此外，理论上可以证明，编码器模型在语言识别方面严格强于解码器模型[^2]；同时，如[5](https://arxiv.org/html/2608.12671#bib.bib5)所示，编码器模型的下界意味着恒定深度对称电路的下界；这将是一个技术上的突破，因为电路下界技术（如随机限制方法）不适用于对称函数。

[^2]: 应当指出，这些“较弱”的解码器没有*思维链*，这是我们接下来要描述的一项附加能力。

#### 思维链。
在自回归解码器模型中，架构可以在计算过程中输出中间词元，然后通过将这些词元附加到输入来将其反馈给架构。这个过程称为*思维链*（CoT）；已知具有这种能力的Transformer严格强于没有这种能力的Transformer[5](https://arxiv.org/html/2608.12671#bib.bib5)、[20](https://arxiv.org/html/2608.12671#bib.bib2)、[14](https://arxiv.org/html/2608.12671#bib.bib4)。大多数现代LLM都利用了CoT式的中间推理。

#### 参数。
除上述特征外，Transformer还具有以下参数。

- *层数*：Transformer中隐藏层的数量，记为L。我们总是假设L是常数，并将层索引为ℓ∈[L]。
- *注意力头数*：注意力头的数量，通常记为H。我们同样假设H是常数，并将头索引为h∈[H]。
- *嵌入维度*：嵌入向量的长度，记为d。通常还有两个附加维度，即*键宽度*d_key和*隐藏宽度*d_hidden。这些参数中的每一个都可以依赖于上下文长度n，尽管在实践中通常为固定常数。
- *精度级别*：允许在架构内执行所有计算的比特数，记为p。该参数通常也是输入长度n的函数；事实上，我们经常假设p=Θ(log n)（参见第[4](https://arxiv.org/html/2608.12671#S4)节开头的讨论）。
- *思维链数量*：对于具有思维链的Transformer，允许生成的中间词元数量，作为输入长度n的函数f(n)。在第[4.2](https://arxiv.org/html/2608.12671#S4.SS2)节中，我们将看到函数f(n)的不同渐近选择所导致的表达性差异。

有时，层数L被称为Transformer的*深度*，而嵌入维度、注意力头数和所用精度位数的乘积Hdp被称为其*宽度*。需要强调的是，上下文长度n（即输入的长度n）*不是*Transformer的参数。原因在于，Transformer可以处理任意长的输入，正如有限自动机可以处理任意长的字符串一样。这一有用的抽象使我们能够将Transformer视为语言识别器。在现实世界的Transformer中，上下文长度（也称为*上下文窗口*）受到某个较大但固定的值（如256k）的限制。

### 2.3 编码器计算

（参见图1：编码器架构的高级视图）

如果X是一个集合，我们将用X*表示所有由X中元素组成的有限序列的集合，而用X+表示所有非空此类序列的集合。所有实数的集合将用ℝ表示。此外，如果m是自然数，我们将用[m]表示集合{1,...,m}。

#### 输入层。
在输入层中，长度为n的字符串通过一个长度保持的函数embed: Σ*→(ℝ^d)*映射为n个ℝ^d向量的序列。为了得到将函数embed应用于字符串w∈Σ*的结果，我们依次取每个输入字符w_i，并取两个函数之和：应用于字符w_i的*词嵌入*函数WE: Σ→ℝ^d，以及应用于索引i的*位置编码*函数PE: [n]→ℝ^d。输入层的输出是所得序列(x_1^(0),...,x_n^(0))∈(ℝ^d)^n。换言之，我们有：
x_i^(0) = WE(w_i) + PE(i)，对所有i∈[n]。

#### 隐藏层。
Transformer的每个隐藏层ℓ∈[L]都是一个长度保持的函数L^(ℓ): (ℝ^d)*→(ℝ^d)*，它接受一个序列(x_1^(ℓ−1),...,x_n^(ℓ−1))∈(ℝ^d)^n作为输入，并输出一个序列(x_1^(ℓ),...,x_n^(ℓ))∈(ℝ^d)^n。为了描述隐藏层，我们需要*自注意力*子层和*逐位置前馈*子层的概念。

一个宽度为d、键宽度为d_key的*自注意力子层*是一个长度保持的函数sa: (ℝ^d)+→(ℝ^d)+，本质上是对所有n个位置上的*值*向量进行加权求和，其中权重是*查询*向量和*键*向量的函数。换言之，我们有三个矩阵W^(Q)，W^(K)，W^(V)∈ℝ^(d_key×d)，加上一个长度保持的*加权函数*S: ℝ+→ℝ+，以及一个输出矩阵W^(O)∈ℝ^(d×d_key