Transformer通用性综述

Transformer架构已成为深度学习的核心范式，从大型语言模型到计算机视觉均取得了突破性进展。这一成功部分源于其被广泛认可的通用性（Universality）和可扩展性（Scalability）。¹ 本综述系统梳理Transformer表达能力的理论基础，涵盖通用逼近定理、形式语言理论视角、架构最小化、近似速率以及提示调优等前沿进展，旨在厘清当前对Transformer表达能力理解的边界，区分稳健的理论保证与脆弱的假设，并指出未来研究的关键方向。

1. 表达能力定义

1.1 基本概念

表达能力（Expressivity）指模型类别能够表示的函数集合大小。在Transformer语境下，表达能力刻画了架构在给定约束条件下能够实现的序列到序列行为（sequence-to-sequence behaviors）范围，独立于训练过程或参数效率。¹²

形式化地，给定输入序列 $X=(x_1,x_2,\dots ,x_n)$，其中 $x_i\in {\mathbb{R}}^d$，Transformer定义了一个从输入序列到输出序列的映射：

$${\mathcal{T}}_{\theta }:{\mathbb{R}}^{n\times d}\to {\mathbb{R}}^{n\times d^{\prime }}$$

其中 $\theta$ 表示模型参数。表达能力研究的核心问题是：这个映射族 $\{{\mathcal{T}}_{\theta }{\}}_{\theta \in \Theta }$ 能够以何种精度逼近任意目标函数类？

1.2 序列到序列映射的数学框架

Transformer处理的是序列到序列（Seq2Seq）的映射问题。设输入序列为 $X=(x_1,\dots ,x_n)\in {\mathcal{X}}^n$，输出序列为 $Y=(y_1,\dots ,y_m)\in {\mathcal{Y}}^m$，则Transformer建模的目标函数类为：

$$\mathcal{F}=\{f:{\mathcal{X}}^n\to {\mathcal{Y}}^m\}$$

关键挑战在于：

• 输入长度 $n$ 可能变化
• 需要捕获token之间的长程依赖关系
• 参数共享机制（同一权重处理所有token）

1.3 排列等变性

Transformer的核心归纳偏置之一是排列等变性（Permutation Equivariance）：输入序列中token的顺序不应影响其语义关系。

定义：函数 $f:{\mathcal{X}}^n\to {\mathcal{Y}}^n$ 称为排列等变的，当且仅当对任意排列 $\sigma \in S_n$：

$$f(\sigma \cdot X)=\sigma \cdot f(X)$$

其中 $\sigma \cdot X=(x_{\sigma (1)},x_{\sigma (2)},\dots ,x_{\sigma (n)})$。

这一性质源于Self-Attention的无序性：注意力权重仅依赖于token内容的点积相似度，而非其位置。

1.4 注意力机制的数学表示

标准缩放点积注意力机制定义为：

$$\text{Attention}(Q,K,V)=\text{softmax}\left(\frac{Q{K}^T}{\sqrt{d}}\right)V$$

其中：

• $Q=X{W}_Q$，$K=X{W}_K$，$V=X{W}_V$ 是Query、Key、Value的线性投影
• $W_Q,W_K,W_V\in {\mathbb{R}}^{d\times d_k}$
• 缩放因子 $\sqrt{d}$ 用于稳定梯度

多头注意力（Multi-Head Attention）扩展为：

$$\text{MultiHead}(X)=\text{Concat}({\text{head}}_1,\dots ,{\text{head}}_h)W_O$$

其中 ${\text{head}}_i=\text{Attention}(X{Q}_i,X{K}_i,X{V}_i)$。

---

2. 通用函数逼近：早期结果

2.1 Yun等人的开创性工作

Yun等人（ICLR 2020）³首次建立了Transformer的通用逼近定理，证明了标准Transformer是连续排列等变序列到序列函数的通用逼近器。

定理（Yun et al., 2020）：³

对于任意连续函数 $f:[0,1{]}^{n\times d}\to [0,1{]}^{n\times d^{\prime }}$ 和任意 $ϵ>0$，若 $f$ 是排列等变的（即 $f(\sigma \cdot X)=\sigma \cdot f(X)$），则存在一个Transformer网络 ${\mathcal{T}}_{\theta }$，使得：

$$\Vert {\mathcal{T}}_{\theta }(X)-f(X){\Vert }_{\infty }<ϵ$$

对所有 $X\in [0,1{]}^{n\times d}$ 成立。

这一结果的核心洞察在于：

1. Self-Attention层可以计算上下文映射（contextual mapping）
2. Feed-Forward层提供非线性变换能力
3. 两者的组合足以逼近任意连续等变函数

2.2 关键证明思想

证明的核心思想将Transformer视为分区机制（partitioning mechanism）：

1. Token区分性（Token Distinguishability）：通过线性变换和注意力权重，模型可以将输入序列划分为语义相关的组

2. 分区构造：Self-Attention通过加权求和实现类似分段线性插值的功能

3. FFN的非线性增强：Feed-Forward网络在每个位置独立应用非线性变换

形式上，单层Self-Attention可以视为计算：

$$z_i=\sum _{j=1}^n{\alpha }_{ij}{v}_j$$

其中注意力权重 ${\alpha }_{ij}=\text{softmax}(q_i^T{k}_j/\sqrt{d})$ 提供了一种软性选择机制。

2.3 位置编码与通用逼近

原始Transformer的排列等变性意味着模型不能区分输入序列中token的绝对位置。Yun等人的工作进一步证明，通过引入位置编码（Positional Encoding），Transformer可以逼近任意连续序列到序列函数，突破排列等变性的限制。³

定理：³

设有位置编码函数 $p:\{1,\dots ,n\}\to {\mathbb{R}}^d$，则对于任意连续函数 $f:[0,1{]}^{n\times d}\to [0,1{]}^{n\times d^{\prime }}$，存在Transformer ${\mathcal{T}}_{\theta }$ 使得：

$$\Vert {\mathcal{T}}_{\theta }(X\oplus P)-f(X){\Vert }_{\infty }<ϵ$$

其中 $P=(p(1),\dots ,p(n))$ 是位置编码序列。

2.4 FFN的关键作用

Yun等人的分析清晰揭示了Self-Attention与Feed-Forward层在逼近理论中的互补角色：

组件	作用
Self-Attention	实现token间的上下文聚合，计算token间的依赖关系
Feed-Forward	提供位置-wise非线性变换，增强局部表达能力
LayerNorm	稳定数值计算，保证函数连续性
残差连接	构造深层组合，增强整体表达能力

---

3. 形式语言理论视角

形式语言理论提供了另一种理解Transformer表达能力的框架，将Transformer视为形式语言识别器或序列变换器，研究其在离散符号序列上的计算能力。⁴⁵

3.1 复杂性类层次

Transformer的计算能力与电路复杂性类密切相关：

核心对应关系：

注意力变体	表达能力	复杂性类
Leftmost-hard Attention	${\mathsf{AC}}^0$	常数深度多项式电路（无计数）
Average-hard Attention	${\mathsf{TC}}^0$	常数深度多项式电路（含计数）
Softmax Attention	${\mathsf{TC}}^0$（上界）	含计数项的常数深度电路
Decoder + 中间步骤	图灵完备	无限计算能力

3.2 固定精度Transformer的上界

Merrill和Sabharwal的研究⁶建立了固定精度Transformer与${\mathsf{TC}}^0$电路类的精确对应：

定理（Merrill & Sabharwal）：⁶

固定精度Transformer编码器恰好与一阶逻辑加计数量化器（$\mathsf{FO}(\mathsf{Count})$）的表达能力相同。

形式化地，设Transformer编码器为 $\mathcal{E}:{\Sigma }^{\ast }\to {\mathbb{R}}^d$，则：

$$\mathcal{L}(\mathcal{E})=\{w\in {\Sigma }^{\ast }:\mathcal{E}(w{)}_1>\tau \}$$

恰好是一类可被 $\mathsf{FO}(\mathsf{Count})$ 公式定义的语言。

3.3 计数能力的局限

计数能力（Counting Power）是Transformer表达能力的核心限制因素：

定理：⁵

Softmax注意力的Transformer编码器位于 ${\mathsf{TC}}^0$ 类，意味着它们可以：

• 判断输入中字符”a”的出现次数是否为奇数（奇偶性）
• 比较不同字符的出现次数

但不能：

• 精确计数到任意大的数字
• 处理需要嵌套递归的问题

C-RASP（Counting-Restricted Access Sequence Processing）⁷提供了一个Transformer表达能力的可组合上界：

$${\text{Transformer}}_{\text{softmax}}\subseteq \text{C-RASP}$$

C-RASP的表达能力恰好涵盖半线性计数性质（semi-linear counting properties）。

3.4 电路复杂性的视角

定义（电路复杂性类）：

• ${\mathsf{AC}}^0$：常数深度、恒定元数、无计数项的多项式大小电路族
• ${\mathsf{TC}}^0$：常数深度、多项式大小、包含MAJORITY门（即计数门）的电路族

定理：⁴

Leftmost-hard Attention Transformer编码器恰好在 ${\mathsf{AC}}^0$ 类；
Average-hard Attention Transformer编码器恰好在 ${\mathsf{TC}}^0$ 类。

3.5 图灵完备性

当允许Transformer解码器多步推理（multi-step reasoning）时，其计算能力可达到图灵完备：

定理：⁸

允许中间步骤输出的Transformer解码器可以模拟任意图灵机。

这意味着在无限精度和无限深度/步数假设下，Transformer具有通用计算能力。

3.6 半代数计数性质

最近的工作⁹进一步拓展了Transformer计数能力的边界：

定理：⁹

Transformer可以表达半代数计数性质（semi-algebraic counting properties），即可以用布尔组合的多元多项式（任意次数）表达的计数性质。

形式化地，给定输入序列 $w\in {\Sigma }^{\ast }$，设 $c_a(w),c_b(w),\dots$ 为各字符的计数，则Transformer可以判断：

$$P(c_a(w),c_b(w),\dots )>0$$

其中 $P$ 是任意多元多项式。

这通过与Hilbert第十问题的联系，还导出了一个重要的不可判定性结果：分析某些极简Transformer模型的行为是停机问题不可判定的。

---

4. 近似速率：架构效率改进

4.1 最小化问题

实际应用中，模型的计算效率和参数效率至关重要。最小化（Minimality）研究关注如何使用最少的架构资源（深度、宽度、注意力头数）实现目标表达能力。¹

定义：模型的最小化程度定义为在保持目标表达能力（如通用逼近）的前提下，各项资源指标的最小值：

• 深度最小化：达到通用逼近所需的最少层数
• 宽度最小化：每层所需最小隐藏维度
• 头数最小化：所需最少的注意力头数

4.2 单层单头Transformer

一个重要发现是：通用逼近不需要多层堆叠或多个注意力头。¹⁰

定理（Universal Approximation - Single Layer, Single Head）：¹⁰

单层、单头Self-Attention配合线性变换和前置的求和线性变换层，即可在 $L^{\infty }$ 范数下逼近任意紧支撑域上的连续函数。

核心洞察：将单头注意力理解为输入域分区机制（input domain-partitioning mechanism），该机制为子区域分配不同的值。通过工程化注意力权重，可以使这种分配模仿目标函数的行为。

4.3 无FFN的Transformer

一个更强的最小化结果是无需Feed-Forward网络的Transformer也能实现通用逼近¹¹：

定理：¹¹

两层Self-Attention（无FFN）即可作为通用逼近器。在此构造中，插值依赖于注意力权重，因此FFN并非严格必需。

这一发现凸显了注意力在Transformer中的核心作用——它可以：

• 逼近分段线性函数
• 模拟插值方法
• 实现上下文感知的token变换

4.4 低秩权重矩阵

另一项关键发现是低秩权重矩阵同样可以实现通用逼近¹²：

定理：¹²

使用低秩权重矩阵（而非满秩 $Q,K,V,O$ 矩阵）的单层Self-Attention仍能保持通用逼近性质。

这意味着可以将高维token表示投影到更小的子空间，在减少参数量的同时保持足够的表达能力。

4.5 Softmax的特殊作用

添加softmax操作可以进一步简化通用逼近构造：

定理：¹

在特定构造下，softmax可以通过模拟插值实现单层注意力下的通用逼近。Softmax注意力可以逼近分段线性函数。

这揭示了softmax的数学本质：它是一种软性最大值操作，本质上是在进行加权插值。

4.6 近似速率分析

给定目标精度 $ϵ$，逼近所需资源（层数、宽度）与 $ϵ$ 的关系是重要的理论问题。

速率定义：设 $f$ 属于某函数类 $\mathcal{F}$（如Hölder连续函数类），Transformer ${\mathcal{T}}_L$ 使用 $L$ 层，定义：

$$E(L,ϵ)=\underset{f\in \mathcal{F}}{\sup }\underset{\theta }{\inf }\Vert f-{\mathcal{T}}_{\theta }{\Vert }_{\infty }$$

已知结果：对于光滑函数类，Transformer的近似速率与深度 $L$ 的关系为：

$$E(L,ϵ)\lesssim O(L^{-\alpha })\text{（某些指数 }\alpha \text{）}$$

这与神经网络深度-表达能力的关系类似，但Transformer的并行计算特性提供了额外的实践优势。

4.7 高维输入域

最近的工作¹将分析扩展到高维输入域：

定理：¹

在高维输入域下，Transformer的通用逼近能力取决于：

1. 全局信息路由是否保留
2. 位置编码策略
3. 注意力头的组织方式

关键是保持全局信息传递——即使采用稀疏注意力，只要信息可以间接路由到所有token，表达能力就不会丧失。

---

5. 表达能力的局限性

5.1 近似理论极限

尽管Transformer具有强大的表达能力，但仍存在fundamental limitations。¹⁴

5.1.1 长序列上的层级结构

定理：⁴

Self-Attention不能建模周期性的有限状态语言，也不能处理层级结构（hierarchical structure），除非层数或头数随输入长度增加。

这对于形式语言中典型的上下文无关文法（CFG）尤其相关——CFG需要递归嵌套结构，而Transformer的固定深度限制了这种递归深度。

5.1.2 周期性语言

定理：⁴

Self-Attention无法识别正则语言中的周期性（periodicity）性质，例如语言 $L=\{w:w\text{ 中 ’a’ 的个数是 }3\text{ 的倍数}\}$，除非模型深度随输入长度增长。

5.2 计数精度的限制

定理：⁵⁷

虽然Softmax注意力赋予了Transformer计数能力，但这种能力被限制在 ${\mathsf{TC}}^0$ 类的范围内：

• 可以判断奇偶性
• 可以比较不同字符的出现次数
• 不能精确计数到非常大的数字
• 不能处理需要 $O(n)$ 精度的计数

形式化地，设输入长度为 $n$，则可表达的计数性质复杂度为 $O(\text{poly}(\log n))$ 而非 $O(n)$。

5.3 布尔公式封闭性

定理：⁵

Transformer（固定精度、softmax注意力）不能判断封闭布尔公式（closed Boolean formulas）的真值。

这一限制源于布尔公式的递归性质，与上下文无关文法相关联。

5.4 与实际能力的差距

理论极限与实际能力之间存在有趣的张力：

理论极限                          实践表现
     │                              │
     │  ✗ 无法精确处理嵌套递归       │
     │  ✗ 无法精确计数到O(n)         │  ✓ 在许多递归任务上表现良好
     │  ✗ TC^0上界                   │  ✓ 捕获长程依赖
     │                              │  ✓ 上下文学习能力
     ▼                              ▼

可能的解释：

1. 自然语言的实际递归深度通常是有界的
2. 近似计数对于大多数任务已足够
3. 大规模训练可能隐式地”压缩”了这些限制

---

6. 提示与PEFT的表达能力

6.1 提示调优的通用逼近

提示调优（Prompt Tuning）是一种高效的微调范式，通过学习一小段”软提示”向量来调整预训练模型的行为。

核心问题：¹

能否通过提示调优，使较小的模型作为通用函数逼近器？

定理：¹

即使较小的、经过适当提示调优的模型也可以作为通用函数逼近器。

具体而言，Prefix Transformer只需要一个注意力头就能逼近任意连续函数，且所需网络深度与序列长度呈线性关系。

6.2 Prefix Transformer的数学框架

Prefix Transformer引入可学习的前缀向量 $\mathcal{P}=(p_1,\dots ,p_k)$ 作为提示：

$${\mathcal{T}}_{\theta ,\mathcal{P}}(X)={\text{Transformer}}_{\theta }(\mathcal{P}\oplus X)$$

其中 $\oplus$ 表示序列拼接。

定理：¹

存在仅使用单个注意力头的Prefix Transformer ${\mathcal{T}}_{\theta ,\mathcal{P}}$，使得对任意连续函数 $f$：

$$\Vert {\mathcal{T}}_{\theta ,\mathcal{P}}(X)-f(X){\Vert }_{\infty }<ϵ$$

6.3 参数高效微调的表达能力

参数高效微调（Parameter-Efficient Fine-Tuning, PEFT）通过更新少量参数实现大模型的高效适配。

定理：¹

Prefix Tuning、LoRA等PEFT方法在理论上可以保持Transformer的完整表达能力上界：

$$\text{Expressivity}(\text{Full Fine-tune})\approx \text{Expressivity}(\text{PEFT})$$

这为”少参数更新等于全参数更新”提供了理论依据，尽管实际优化景观可能存在差异。

6.4 提示作为隐式计算

从计算理论角度，提示可以视为隐式计算（implicit computation）的一种形式：

定理：¹

提示向量 $\mathcal{P}$ 可以编码：

1. 条件信息（如任务描述）
2. 隐式的计算状态
3. 函数参数的编码

这使得Prefix Tuning成为一种元学习（meta-learning）机制，其中提示编码了”如何学习”的信息。

6.5 开放问题

尽管提示调优展现了强大的表达能力，仍有重要问题未解决：

问题	现状
提示长度与表达能力	理论上线性关系，具体界未知
离散/自然语言提示	表达能力尚未在理论上刻画
多任务提示	组合泛化能力缺乏理论保证

---

7. 统一视图：理论与实践的综合

7.1 表达能力层次结构

综合以上分析，Transformer表达能力呈现清晰的层次结构：

┌─────────────────────────────────────────────────────────────────┐
│                        通用连续函数                               │
│                    (需要位置编码 + 足够深度)                       │
├─────────────────────────────────────────────────────────────────┤
│                      排列等变连续函数                             │
│                  (标准Transformer + FFN)                          │
├─────────────────────────────────────────────────────────────────┤
│                     半代数计数性质                                │
│                   (Softmax Attention)                            │
├─────────────────────────────────────────────────────────────────┤
│                       TC^0 类语言                                │
│              (Average-hard Attention + Softmax)                   │
├─────────────────────────────────────────────────────────────────┤
│                       AC^0 类语言                                │
│                  (Leftmost-hard Attention)                       │
└─────────────────────────────────────────────────────────────────┘

7.2 架构约束与表达能力的关系

不同架构选择对表达能力的影响如下表所示：

架构选择	表达能力	效率	备注
完整注意力	${\mathsf{TC}}^0$	$O(n^2)$	理论最强
稀疏注意力	$\subseteq {\mathsf{TC}}^0$	$O(nk)$	保持全局路由
低秩投影	$\approx$ 完整	降低参数	可达通用逼近
单头注意力	通用逼近	高效	需要前置线性层
无FFN两层	通用逼近	高效	注意力主导
无位置编码	排列等变	-	失去序列顺序感知

7.3 稳健保证 vs 脆弱假设

稳健的理论保证（Robust Guarantees）：¹

1. 通用逼近定理在广泛条件下成立
2. ${\mathsf{TC}}^0$ 上界在固定精度假设下稳固
3. 单层单头通用逼近在足够资源下可证

脆弱的假设（Fragile Assumptions）：

1. 无限精度 vs 固定精度——两者表达能力差异巨大
2. 理论构造 vs 可训练性——存在性证明不等于可学习
3. 连续域 vs 离散域——离散设置的理论尚不完善

7.4 实践指南

基于理论分析，架构设计建议如下：

场景	推荐架构	理论依据
通用逼近需求	单层单头 + 前置线性层	Yun et al., Abbott et al.
高效部署	低秩投影 + 稀疏注意力	Merrill et al., Ji et al.
长序列建模	稀疏注意力 + 全局路由	保持TC^0上界
上下文学习	多层堆叠 + 提示调优	深度-表达能力权衡

7.5 开放问题与未来方向

7.5.1 未解决的理论问题

1. 定量近似速率：除光滑函数类外，其他函数类的近似速率尚不完整
2. 离散设置的表达能力：严格资源约束下的表达力尚未充分理解
3. 替代位置编码：不同位置编码方案对表达力的影响缺乏系统分析
4. 优化与表达力的交互：表达能力边界与梯度下降优化景观的关系

7.5.2 实践导向的研究

1. 效率-表达力权衡：在给定计算预算下最大化表达能力
2. 专用Transformer设计：针对特定函数类的专用架构
3. 理论启发的架构搜索：基于表达能力分析的Neural Architecture Search

7.6 与相关工作的联系

本综述与以下工作形成理论上的补充：

相关主题	联系	参考
neural-network-expressivity	共享通用逼近定理传统；Transformer是NN的特殊形式	Hornik et al., Cybenko
transformer-expressivity-tropical-geometry	热带几何提供精确的空间划分分析	Su et al.

---

参考文献

---

相关词条：neural-network-expressivity，transformer-expressivity-tropical-geometry，transformer-and-attention，neural-network-theory

Footnotes

1. Abbasi & Hooshmand, “On the Universality of Transformer Architectures; How Much Attention Is Enough?”, arXiv:2512.18445, 2025 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³

2. Merrill et al., “What Formal Languages Can Transformers Express? A Survey”, Transactions of the Association for Computational Linguistics, 2024 ↩

3. Yun et al., “Are Transformers Universal Approximators of Sequence-to-Sequence Functions?”, ICLR 2020 ↩ ↩² ↩³ ↩⁴

4. Hahn, “Theoretical Limitations of Self-Attention”, TACL 2020 ↩ ↩² ↩³ ↩⁴ ↩⁵

5. Merrill & Sabharwal, “Tighter Bounds on the Expressivity of Transformer Encoders”, arXiv:2301.10743, 2023 ↩ ↩² ↩³ ↩⁴

6. Merrill & Sabharwal, “The Expressive Power of Transformers with Chain of Thought”, ICLR 2024 ↩ ↩²

7. Merrill et al., “C-RASP: Circuits for Accessible Sequence Processing”, NeurIPS 2022 ↩ ↩²

8. Merrill & Sabharwal, “Transformers are Universal Predictors”, arXiv:2307.07843, 2023 ↩

9. Strobl et al., “The Counting Power of Transformers”, ICLR 2026 ↩ ↩²

10. Abbott et al., “Universal Approximation with Neural Attention”, OpenReview, 2024 ↩ ↩²

11. Ji et al., “Two-Layer Attention-Only Transformers are Universal Approximators”, NeurIPS 2024 ↩ ↩²

12. Sanford et al., “Low-Rank Transformers are Universal Approximators”, ICML 2024 ↩ ↩²