A Unified Framework for Establishing the Universal Approximation of Transformer-Type Architectures¶

会议: NeurIPS 2025
arXiv: 2506.23551
代码: 无
领域: Transformer理论 / 逼近论
关键词: 万能逼近性, Token可区分性, 注意力机制, 置换等变性, 控制论

一句话总结¶

建立了统一的理论框架证明各类Transformer架构的万能逼近性(UAP)，核心条件仅两个——前馈层的非线性仿射不变性和注意力层的token可区分性——并利用解析性假设将后者简化为仅需检验两样本情况，成功覆盖softmax、RBF kernel、Performer、BigBird、Linformer等多种实用架构。

研究背景与动机¶

Transformer在NLP、CV等领域取得了巨大成功，但对其表达能力的理论理解一直依赖于针对特定架构的构造性证明。Yun等人(2019)证明了softmax attention Transformer的UAP，Zaheer等人(2020)证明了BigBird的UAP，但每种新发明的注意力变体（kernel-based、稀疏、低秩等）都需要从头设计构造性证明，工作量大且技术路线不可复用。

这与ResNet的UAP理论形成对比：借鉴控制论视角，Li等人(2024)和Cheng等人(2025)已证明具有Lipschitz非线性激活的深层ResNet具有UAP，该结果与具体网络结构无关。然而将此方法直接迁移到Transformer面临本质困难——Transformer的前馈层是token-wise的（对每个token独立施加相同变换），无法直接建模token间交互，这意味着注意力机制必须额外承担"产生不同输入的不同上下文表示"的职责。

本文的核心目标是：给出一组与具体注意力机制无关的充分条件，使得任何满足这些条件的Transformer变体都自动具有UAP，并且这些条件可以被高效验证。

方法详解¶

整体框架¶

将Transformer抽象为两个交替组件的深度组合：(1) token-mixing层 $g \in \mathcal{G}$（抽象注意力），将 $\mathbb{R}^{d \times n}$ 映射到自身，捕获token间依赖；(2) token-wise前馈层 $h \in \mathcal{H}^{\otimes n}$，对每个token独立施加同一函数 $\bar{h}: \mathbb{R}^d \to \mathbb{R}^d$。一个Transformer块为 $(Id + h) \circ (Id + g)$，完整模型为此类块的任意深度组合 $\mathcal{T}_{\mathcal{G},\mathcal{H}}$。在此抽象上定义了支持一般置换子群 $G \leq S_n$ 的 $G$-UAP概念。

关键设计¶

前馈层条件——非线性仿射不变性（Definition 2）:
- 功能：确保深层前馈组合能逼近任意单token上的连续函数
- 核心思路：要求 $\mathcal{H}$ 对仿射变换封闭（$\forall h \in \mathcal{H}, W,A \in \mathbb{R}^{d \times d}, b \in \mathbb{R}^d$，$Wh(A \cdot - b) \in \mathcal{H}$），且包含至少一个非仿射Lipschitz函数
- 设计动机：这是一个极其温和的条件——几乎所有实用前馈网络（任意激活函数、任意宽度）都满足。条件由先行工作(Cheng et al., 2025)证明等价于深层ResNet的UAP
注意力层条件——Token可区分性（Definition 3）:
- 功能：确保注意力机制能为不同输入的所有token产生互不相同的上下文表示
- 核心思路：对任意有限数据集 $D = \{X_i\}_{i=1}^N$（元素在一般位置），存在有限层组合 $g \in (Id + \mathcal{G})^m$ 使得来自不同 $G$-轨道的样本 $X_i, X_j$ 经映射后所有token互不相同
- 设计动机：如果注意力机制无法区分token，则某个正测集上的输出是常数（因为前馈层是token-wise的），UAP必然失败。这是一个必要条件的弱化版本，同时也是实验中容易验证的充分条件
解析性简化（Theorem 2，核心技术贡献）:
- 功能：将token可区分性的验证从"对任意有限集"简化为"对两个样本"
- 核心思路：如果 $\mathcal{G}$ 关于参数 $\theta$ 是解析的，则"对某个 $|D| > 2$ 的有限集token可区分性失败"意味着某个解析函数在参数空间上恒为零。利用非平凡解析函数零集测度为零的性质，可将检验降维至 $|D| = 2$
- 设计动机：直接验证token可区分性需要对"所有有限集"逐个检查（无穷），解析性假设将复杂度降至检查一对样本，极大降低了验证难度

损失函数 / 训练策略¶

纯理论工作，无训练过程。核心定理（Theorem 1）：若 $\mathcal{H}$ 满足非线性仿射不变性且 $\mathcal{G}$ 满足token可区分性，则 $\mathcal{T}_{\mathcal{G},\mathcal{H}}$ 具有 $G$-UAP。附加推论：当token可区分性在固定 $m$ 层注意力中即可满足时，$m$ 层注意力 + 任意多前馈层就足够实现UAP。

实验关键数据¶

主实验¶

纯理论论文，核心贡献在于将统一条件应用到多种实际架构，验证其满足UAP：

架构	注意力类型	核函数/稀疏模式	UAP类型	所需注意力层数	先前结果
原始Transformer	Softmax kernel	$k(x,y) = e^{x^\top y}$	$S_n$-UAP	1层	已知(Yun 2019)
Performer	随机特征kernel	$k(x,y) = \phi(x)^\top\phi(y)$	$S_n$-UAP(a.s.)	1层	已知(Alberti 2023)
RBF注意力	高斯kernel	$k(x,y) = e^{-\gamma\\|x-y\\|^2}$	$S_n$-UAP	1层	新结果
BigBird	稀疏softmax	滑动窗口+全局+随机	$G$-UAP	连通跳数	放宽条件
Longformer	滑动窗口	$\mathcal{N}(i) = {j:	j-i	\leq w}$	反射群-UAP
Linformer	低秩投影	$EF$投影矩阵	UAP(无对称性)	1层	新结果
SkyFormer	Nyström kernel	近似高斯kernel	$S_n$-UAP	1层	新结果

消融实验¶

配置	关键指标	说明
Kernel极限行为	$\lim_{t\to\infty} k(x,tW_Ky_1)/k(x,tW_Ky_2)$	要求发散或趋零，可区分不同token
稀疏注意力连通性	图连通性	只要token能通过有限跳数互相到达即满足UAP
固定注意力层数	$m$ 层	对kernel-based注意力仅需1层，对稀疏注意力需"连通跳数"层

关键发现¶

稀疏注意力的UAP条件可优雅地归结为图的连通性——不需要周期性、Hamiltonian路径或星形子结构等技术条件
Kernel-based注意力中UAP条件归结为kernel在key缩放下的极限行为——一种自然的"硬注意力"近似
1层注意力+任意多前馈层对kernel-based注意力就足够实现UAP，这量化了注意力的"记忆容量"

亮点与洞察¶

理论贡献极为干净：两个独立的可验证条件+一个解析性简化技巧，覆盖了几乎所有主流Transformer变体，避免了逐架构构造的繁琐
非构造性方法的威力：不需要显式构造近似目标函数的网络参数，只需验证条件即可保证UAP存在
"token可区分性"是一个具有设计指导意义的概念：任何新注意力机制只要能通过有限层区分任意两个输入的所有token，就自动拥有UAP保证
稀疏注意力的理论下界：图只需连通（而非完全图），为设计高效稀疏模式提供了理论保证——可以非常稀疏，只要保持连通即可
对称性保持的新架构：提出了保持二面体群 $D_n$ 和循环群 $C_n$ 等变性的注意力设计，对分子和晶体结构预测等应用有价值

局限与展望¶

未考虑LayerNorm等实际中广泛使用的归一化层对UAP的影响
某些注意力机制（如linear attention $k(x,y)=\phi(x)^\top\phi(y)$ 中 $\phi$ 为ReLU时）不满足解析性假设，Theorem 2不适用（但Theorem 1仍可直接验证）
框架不提供量化的逼近速率——知道"可以逼近"但不知道"多快"
仅处理固定长度、紧集上的序列到序列映射，未覆盖变长输入、自回归生成等场景
未分析多头注意力、MoE等复杂组件对逼近效率的各自贡献

评分¶

新颖性: ⭐⭐⭐⭐⭐ 将控制论+解析性技巧引入Transformer UAP分析，建立了优雅的统一框架
实验充分度: ⭐⭐⭐ 纯理论论文，通过多种架构推论充分展示了框架的通用性
写作质量: ⭐⭐⭐⭐⭐ Definition→Theorem→Corollary结构层次分明，直觉解释到位
价值: ⭐⭐⭐⭐ 为Transformer架构设计提供了理论基础和UAP保证设计准则

架构	注意力类型	核函数/稀疏模式	UAP类型	所需注意力层数	先前结果
原始Transformer	Softmax kernel	\(k(x,y) = e^{x^\top y}\)	\(S_n\)-UAP	1层	已知(Yun 2019)
Performer	随机特征kernel	\(k(x,y) = \phi(x)^\top\phi(y)\)	\(S_n\)-UAP(a.s.)	1层	已知(Alberti 2023)
RBF注意力	高斯kernel	\(k(x,y) = e^{-\gamma\\|x-y\\|^2}\)	\(S_n\)-UAP	1层	新结果
BigBird	稀疏softmax	滑动窗口+全局+随机	\(G\)-UAP	连通跳数	放宽条件
Longformer	滑动窗口	$\mathcal{N}(i) = {j:	j-i	\leq w}$	反射群-UAP
Linformer	低秩投影	\(EF\)投影矩阵	UAP(无对称性)	1层	新结果
SkyFormer	Nyström kernel	近似高斯kernel	\(S_n\)-UAP	1层	新结果

配置	关键指标	说明
Kernel极限行为	\(\lim_{t\to\infty} k(x,tW_Ky_1)/k(x,tW_Ky_2)\)	要求发散或趋零，可区分不同token
稀疏注意力连通性	图连通性	只要token能通过有限跳数互相到达即满足UAP
固定注意力层数	\(m\) 层	对kernel-based注意力仅需1层，对稀疏注意力需"连通跳数"层