Fixed Universal Transformers¶
会议: NeurIPS 2026
arXiv: 2605.31423
论文: https://arxiv.org/abs/2605.31423 https://openreview.net/forum?id=oLOTrZMfSu
领域: 学习理论
关键词: 通用Transformer, 计算通用性, 随机网络, 表达能力, 嵌入编码
一句话总结¶
类比通用图灵机，本文证明了固定权重（稀疏确定性或随机初始化）的Transformer仅需调整输入嵌入层，即可精确模拟给定族内的任意目标Transformer，同时揭示出多头机制下嵌入维度对网络深度呈固有指数下界的理论界限。
研究背景与动机¶
在深度学习理论与模型重编程（Model Reprogramming）领域，一个长期悬而未决的核心问题是：Transformer模型的强大表达能力究竟源自其训练优化后精细调整的内部注意力与前馈权重，还是其架构本身所具有的固有表征几何结构？近期实验工作（如 Zhong & Andreas, 2024）观察到一个引人瞩目的反直觉现象：在完全随机初始化的Transformer中，仅仅通过训练输入嵌入层（Embedding）和输出投影层（Unembedding），就能赋予模型解决多种算法推理与语言建模任务的能力。然而，这一现象背后缺乏严谨的理论解释与严密的数学刻画。
如果试图从经典计算理论中寻找解释，通用的经典类比通常是通用图灵机（Universal Turing Machine, UTM）或通用电路（Universal Circuit）。在经典理论中，单台通用的机器或固定电路能够通过读取输入带上编码的目标程序，来执行任意目标算法。但既有的神经网络通用近似定理（Universal Approximation）仅保证存在某种权重的网络能够逼近目标函数，每次逼近都需要彻底重置或训练全部网络内部参数；而早先基于循环架构图灵完备性的分析，也无法为现代标准Transformer架构提供定量、紧凑且保真的模拟表征保证。
针对这一根本理论盲区，本文正式提出了通用Transformer（Universal Transformer）的理论框架：保持Transformer主干网络中所有内部注意力（Query/Key）与投影（Value）参数永久固定，将输入嵌入矩阵当作“程序描述载体”。核心 idea：证明固定结构的Transformer能够仅凭线性输入嵌入编码目标网络参数来精确模拟任意目标Transformer，并给出仅含 \(\{0,1\}\) 权重的稀疏树状确定性构造以及连续随机初始化几乎必然（almost surely）通用的充要条件，确立了 \(H^{\Omega(L)}\) 嵌入维度的不可避免性。
方法详解¶
整体框架¶
本文构建的通用Transformer针对目标Transformer族 \(\text{TF}_{H,L,d_{\text{in}},d}\)，其中 \(H\) 为注意力头数，\(L\) 为网络深度，\(d_{\text{in}}\) 为输入输出特征维度，\(d\) 为单头内部维度。通用模型 \(\text{UTF}_{H,L,d_{\text{in}},d}^{m}\) 拥有扩展的嵌入维度 \(m\)，其内部参数集合 \(\{R_Q^{l,h}, R_K^{l,h}, R_V^{l,h}\}_{l\in[L],h\in[H]}\) 与输出解嵌入矩阵 \(U \in \mathbb{R}^{m \times d_{\text{in}}}\) 完全固定且与输入序列长度 \(n\) 无关。
整体模拟过程分为三个阶段： 1. 输入嵌入编码：对任意输入序列 \(X^0 \in \mathbb{R}^{n \times d_{\text{in}}}\)，通过目标模型特异性的嵌入矩阵 \(E \in \mathbb{R}^{d_{\text{in}} \times m}\) 映射为 \(\tilde{X}^0 = X^0 E \in \mathbb{R}^{n \times m}\)。矩阵 \(E\) 承担了将目标网络各层全部权重算子编码到高维正交/非退化子空间中的任务； 2. 固定骨干前向传播：在每一层 \(l\)，通用模型利用固定的注意力投影与掩码算子，计算多头注意力矩阵 \(\tilde{A}^{l,h}\) 与层间状态更新 \(\tilde{X}^l\)。由于参数构造的精确正交对齐，每一层、每个头的注意力矩阵与中间值变换精确复制了目标模型的行为； 3. 固定解嵌入输出：最后一层状态 \(\tilde{X}^L\) 经由固定的解嵌入矩阵 \(U\) 投影回原始维度，实现 \(\tilde{X}^L U = T(X^0)\)。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入序列 X0 ∈ ℝ^(n × d_in)"] --> B["输入嵌入编码: X~0 = X0 · E<br/>将目标网络权重编码到高维空间"]
B --> C["层级注意力匹配<br/>A~^(l,h) = A^(l,h)"]
C --> D["树状路径路由与值变换<br/>沿 H^L 条计算路径执行线性变换"]
D --> E["解嵌入投影: 输出 = X~L · U<br/>投影回原始特征空间 ℝ^(n × d_in)"]关键设计¶
1. 树状路径路由与注意力匹配机制：实现精确计算流对齐
要使通用Transformer能够模拟任意目标Transformer，核心挑战在于多头多层注意力产生的分支计算流。对于 \(L\) 层 \(H\) 头模型，任意输入经过展开后实际上是 \(H^L\) 条注意力传播路径的叠加： $\(T(X^0) = \sum_{(h_1,\dots,h_L) \in [H]^L} A^{L,h_L} \cdots A^{1,h_1} X^0 W_V^{1,h_1} W_O^{1,h_1} \cdots W_V^{L,h_L} W_O^{L,h_L}\)$ 本文将嵌入空间几何化为一个高度为 \(L\) 的 \(H\) 叉树（\(H\)-ary tree）。根节点对应第一层各头的 Query/Key 算子，各内部节点存储后续层所需的值投影乘积，叶节点存储完整的端到端值变换算子 \(M^{1:L,p} = \prod_{s=1}^L W_V^{s,h_s} W_O^{s,h_s}\)。通过将值变换矩阵 \(R_V^{l,h}\) 构造为对角 \(\{0,1\}\) 掩码，每一层选择第 \(h\) 个头时，掩码会精确保留第 \(l\) 个分支为 \(h\) 的子树坐标块，并将其他非相关分支清零。这一设计使得通用模型的各层 Query 和 Key 投影能够无失真地提取目标模型在前序路径调制下的等效表征，从而逐层严格归纳证明 \(\tilde{A}^{l,h} = A^{l,h}\) 对所有层与头恒成立。
2. 稀疏与循环（Looped）确定性构造：紧致维度边界与参数复用
在显式构造中，作者给出了紧致的最小嵌入维度上界 \(\bar{m}\)： $\(\bar{m} := \begin{cases} (L+1)\max\{2d, d_{\text{in}}\}, & \text{if } H=1, \\ \frac{2H(H^L - 1)}{H-1}d + H^L d_{\text{in}}, & \text{if } H > 1. \end{cases}\)$ 在单头情形下，路径退化为单一直链，利用位移矩阵（Shift Matrix）\(R = \sum_{i=1}^L S_{i+1} S_i^\top\) 可以在层间顺次滚动坐标块，使嵌入维度仅需随深度 \(L\) 呈线性增长 \(\mathcal{O}(Ld)\)。在多头情形下，构造扩展到循环网络（Looped Transformer，即层间权重共享），所有层的参数矩阵完全相同。在这一构造中，固定参数矩阵仅取值于 \(\{0,1\}\)，每行至多一个非零元，内部矩阵乘法无需任何复杂的数值缩放，在浮点计算中具备完全零额外舍入误差的优异数值稳定性。
3. 随机初始化的几乎必然通用性：代数超曲面与测度论论证
为了探究通用性是否仅仅依赖于高度人工设计的精巧稀疏结构，作者将通用模拟条件重构为一个巨型线性方程组：\(E R_{\text{all}} = W_{\text{all}}\)，其中 \(R_{\text{all}} \in \mathbb{R}^{m \times N}\) 是完全由通用模型随机参数构成的基矩阵，\(W_{\text{all}} \in \mathbb{R}^{d_{\text{in}} \times N}\) 是目标网络全部参数构成的目标矩阵。只要 \(R_{\text{all}}\) 具有满列秩（Full Column Rank），即可通过伪逆求得适定的嵌入矩阵 \(E = W_{\text{all}} R_{\text{all}}^\dagger\)。定义多项式 \(p(\omega) := \det(\bar{R}_{\text{all}})\)（其中 \(\bar{R}_{\text{all}}\) 为前 \(N\) 行方阵），由于前面的显式稀疏构造构成了一个满足 \(p(\omega) = \pm 1\) 的非退化特解，证明了多项式 \(p(\omega)\) 并非恒零多项式。根据代数几何与测度论，非零实多项式的根集（零点集）在绝对连续分布下的勒贝格测度恒为零。因此，从任意绝对连续分布（如高斯分布、均匀分布）独立采样的Transformer，以概率 1 必然是通用Transformer。
4. 扩展至非线性组件与指数下界证明：边界界定与内禀复杂度
作者进一步探讨了该机制在实际架构组件上的边界： - 门控 MLP 与残差连接：将残差连接视为携带单位变换的恒等注意力头（将 \(H\) 替换为 \(H+1\)），针对 SwiGLU 等门控前馈网络，通过在反向探测基（Backward Linear Probes）中引入线性分支编码，证明了通用性可扩展至含 Gated MLP 的网络，此时维度尺度为 \(\mathcal{O}((2Hr)^L (d_{\text{in}} + d))\)； - LayerNorm 的不可行性：由于 LayerNorm 会除以特征维度方差并引入平移偏置，改变嵌入维度 \(m\) 会破坏线代表征不变量，在 \(X=0\) 时输入嵌入必为 0，固定 LayerNorm 无法生成目标模型任意可学习的偏置 \(\beta\)； - 注意力匹配下界：定理 4.1 证明，对于任何基于“注意力匹配”（Attention-Matching）的通用模型，即便输入维度 \(d_{\text{in}} = 1\)，为了能够独立覆盖 \(H^L\) 种注意力历史路径，必须满足 \(m \ge H^{L/2}\)。这在数学上确立了多头架构中深度与嵌入维度的指数依赖是内禀不可避免的。
实验关键数据¶
主实验¶
论文在两类典型的算法推理基准上进行了验证：括号平衡判定（Parenthesis Balancing / Dyck-1，上下文无关语言）和 \(k\)-跳归纳头（\(k\)-hop Induction Heads，评估多层递归检索与组合推理能力）。对比了三类模型：(1) 定理 3.1 的稀疏通用Transformer（Sparse）；(2) 默认 PyTorch 均匀分布初始化的随机通用Transformer（Random）；(3) 内部参数完全训练的基准Transformer（Fully-trained）。在稀疏与随机通用Transformer中，内部权重均完全冻结，仅通过梯度下降（AdamW）训练输入嵌入矩阵 \(E\) 与解嵌入矩阵 \(U\)。
| 任务 | 架构设置 (\(H, L, d, m\)) | 稀疏通用 (Sparse) | 随机通用 (Random) | 全参数训练 (Fully-trained) |
|---|---|---|---|---|
| Parenthesis Balancing (Dyck-1) [Attention-only] | \(H=4, L=2, d=24, m=1024\) | 100.0% | 94.4% | 100.0% |
| 1-hop Induction Head [Attention-only] | \(H=2, L=2, d=28, m=456\) | 30.2% | 29.4% | 8.4% |
| 2-hop Induction Head [Attention-only] | \(H=2, L=3, d=28, m=1024\) | 33.2% | 30.5% | 51.8% |
| 3-hop Induction Head [Attention-only] | \(H=2, L=4, d=30, m=2280\) | 39.2% | 32.6% | 99.5% |
| 4-hop Induction Head [Attention-only] | \(H=2, L=4, d=30, m=2280\) | 39.4% | 35.2% | 95.6% |
| Parenthesis Balancing [+ Res & LN] | \(H=4, L=2, d=24, m=1024\) | 100.0% | 100.0% | 93.0% |
| 1-hop Induction Head [+ Res & LN] | \(H=2, L=2, d=28, m=456\) | 100.0% | 96.1% | 100.0% |
| 2-hop Induction Head [+ Res & LN] | \(H=2, L=3, d=28, m=1024\) | 100.0% | 85.7% | 100.0% |
| 3-hop Induction Head [+ Res & LN] | \(H=2, L=4, d=30, m=2280\) | 100.0% | 92.6% | 100.0% |
| 4-hop Induction Head [+ Res & LN] | \(H=2, L=4, d=30, m=2280\) | 100.0% | 89.2% | 100.0% |
消融实验¶
为了剖析常见架构组件对冻结主干优化难度的影响，论文在括号平衡与 2-hop 归纳头任务上进行了逐项组件消融（其中额外引入的 MLP 层同样保持随机初始化且完全冻结）：
| 架构变体配置 | Parenthesis (Sparse) | Parenthesis (Random) | 2-hop Ind. (Sparse) | 2-hop Ind. (Random) | 2-hop Ind. (Fully-trained) |
|---|---|---|---|---|---|
| Attention-only | 100.0% | 94.4% | 33.2% | 30.5% | 51.8% |
| + residual | 100.0% | 95.4% | 53.8% | 54.3% | 58.4% |
| + residual & LayerNorm | 100.0% | 100.0% | 100.0% | 85.7% | 100.0% |
| + MLP (frozen random) | 100.0% | 100.0% | 54.6% | 54.1% | 100.0% |
| + MLP & LayerNorm | 100.0% | 100.0% | 100.0% | 66.2% | 100.0% |
关键发现¶
- 表达能力与优化可解性的鸿沟：在 Attention-only 的深层归纳头任务中，稀疏与随机通用Transformer虽然在理论上完全具备表达目标解的容量，但单纯基于一阶梯度更新输入嵌入 \(E\) 极其容易陷入局部极小（准确率在 30%~39% 之间停滞）。
- LayerNorm 与残差的优化使能效应：加入残差连接与 LayerNorm 后，稀疏通用Transformer在全部 1~4 跳归纳头任务上直接跃升至 100% 完美准确率，随机通用Transformer也达到 85.7%~96.1%。这表明归一化算子极大平滑了固定随机基底上的损失曲面。
- 稀疏结构蕴含强归纳偏置：在所有任务中，显式设计的稀疏通用Transformer表现均稳定优于随机初始化的通用Transformer，表明将坐标严格对齐到正交分支树上的结构性先验对反向传播具有显著的正向引导作用。
亮点与洞察¶
- 将嵌入层概念化为“目标程序描述符”：文章跳出了传统“通过微调网络权重适配新任务”的思维定势，从可计算性视角严谨确立了固定Transformer作为类似通用图灵机“硬件底座”的理论地位，指出参数重编程可达到完全无损模拟的理论上限。
- 代数几何多项式非退化技巧：利用显式设计的 \(\{0,1\}\) 特解作为代数行列式多项式非零的“见证者（Witness）”，极其优雅地通过测度论证明了随机连续权重的通用性以概率 1 几乎必然成立。
- 可复用的结构化表征启示：这一机制为模型重编程（Model Reprogramming）以及提示词调优（Prompt Tuning / Soft Prompting）提供了坚实的理论依据，揭示出通过增大嵌入维度，固定大模型的输入层能够具备承载整网重配置的充足自由度。
局限与展望¶
- 指数级嵌入维度的扩展瓶颈：下界定理证明了在严格注意力匹配框架下，多头架构的嵌入维度必须随深度呈 \(H^{\Omega(L)}\) 指数爆炸。这使得通用Transformer在大深度、多头语言模型上的实际物理开销受到限制。
- 理论构造与 LayerNorm 存在代数张力：理论分析无法直接闭合具有任意可学习仿射变换的 LayerNorm，而实验却显示 LayerNorm 对梯度优化求解嵌入至关重要。如何从理论上松弛注意力匹配条件以容纳非线性归一化是关键的开放问题。
相关工作与启发¶
- vs Universal Approximation (Cybenko, 1989; Yun et al., 2020)：传统通用近似探讨的是参数随目标函数变动时函数族的逼近能力；本文讨论的是参数完全固定、仅改变输入嵌入时的无损精确模拟。
- vs Universal Transformer (Dehghani et al., 2019)：Dehghani 等人修改了架构，引入沿深度循环迭代的显式动态停机；本文完全不修改标准Transformer架构，专注于固定参数的计算通用性。
- vs Random Transformers (Zhong & Andreas, 2024)：Zhong 等人观察到了随机Transformer训练嵌入解决任务的经验现象；本文不仅给出了该现象的首个严格理论证明，更指出了随机性并非必需——确定性稀疏骨干能够提供更优越的优化归纳偏置。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 建立了固定权重Transformer通用模拟的理论范式，填补了表示理论关键空白。
- 实验充分度: ⭐⭐⭐⭐ 覆盖了上下文无关文法与多跳归纳头任务，但受限于理论维度，实验集中在小型算法任务。
- 写作质量: ⭐⭐⭐⭐⭐ 证明结构极其严密清晰，附录推导详实自洽。
- 价值: ⭐⭐⭐⭐⭐ 为模型重编程、软提示表征极限以及随机神经网络基础理论提供了基石级的理论支撑。