多层Transformer表达能力极限

引言

尽管Transformer已成为大语言模型的主导架构，我们对其表达能力极限的理解仍然有限。之前的工作已经建立了单层Transformer的表达式下界，但对于多层Transformer，直到最近才有了首个无条件下界证明。¹

ICLR 2025的工作揭示了一个令人惊讶的结论：执行顺序组合任务时，多层Transformer需要多项式规模的模型维度——这是首个不依赖未证明复杂度猜想的无条件下界。

问题设定

顺序组合任务

考虑一个自然的组合任务：顺序组合（Sequential Composition）。

设 $f_1,f_2,\dots ,f_L$ 为 $L$ 个函数，每个函数将 $n$ 维输入映射到 $n$ 维输出。顺序组合定义为：

$$f_L\circ f_{L-1}\circ \cdots \circ f_1(\mathbf{x})$$

任务是：给定 $L$ 个函数描述和输入 $\mathbf{x}$，预测组合后的输出。

形式化模型

我们考虑一个 $L$-层Decoder-only Transformer：

• 输入格式：$[f_1,f_2,\dots ,f_L,\mathbf{x}]$
• 位置编码：绝对位置编码
• 精度：$O(\log n)$ 比特

无条件下界

主要定理

定理（顺序组合的深度限制）：对于任意常数 $L$，任意 $L$-层Decoder-only Transformer在执行 $L$-步顺序组合时，需要模型维度 $d=\Omega (n^{1/L})$ 才能达到常数误差。

换言之：

$$d\cdot L\ge \Omega (\log n)\text{或}d\ge \Omega (n^{1/L})$$

关键点：这是无条件下界——不依赖于任何未证明的复杂度猜想。

证明思路

证明基于多方通信复杂性（Multiparty Communication Complexity）框架：

1. 多方模型：将输入划分为 $L+1$ 个不相交的集合，每方持有部分函数描述
2. 通信协议：分析各方需要交换多少信息才能正确计算输出
3. 下界推导：证明任何正确算法都需要大量通信，从而需要大模型容量

与先前工作的区别

方面	之前工作	本工作
下界类型	条件性（依赖猜想）	无条件
深度	单层	多层（常数 $L$）
任务	基本任务	顺序组合
技术	直接构造	通信复杂性

深度-宽度权衡

权衡形式化

定理暗示了一个精确的深度-宽度权衡：

$$\text{组合深度}\approx \frac{\log n}{\log d}$$

即：

• 增加深度：可以减少所需宽度
• 减少宽度：需要增加深度来补偿
• 固定参数：深度和宽度存在最优平衡

权衡曲线

            顺序组合的深度-宽度权衡
            
宽度 d ↑
       │
2^16   │                                           *
       │                                       * *
2^12   │                                   * *
       │                               * *
2^8    │                          * *
       │                     * *
2^4    │                * *
       │           * *
       │      * *
  2    │ * * * * * * * * * * * * * * * * * * * * * *
       └────────────────────────────────────────────→
        1    2    3    4    5    6    7    8    L (层数)
        
图例：每条曲线代表固定的组合深度需求

最优配置

对于 $n$ 个token和 $L$ 层，理论上最优的配置满足：

$$d=\Theta (n^{1/L}),\text{总参数}=\Theta (L\cdot n^{2/L})$$

解码器与编码器的分离

编码器-解码器不对等性

一个重要发现是：编码器和解码器在表达能力上存在可证明的分离。

定理（编码器-解码器分离）：存在一个任务 $T$ 使得：

1. 一个 $O(1)$-层编码器（深度为 $L_1$）可以在维度 $d_1=O(1)$ 下解决 $T$
2. 任何 $O(1)$-层解码器（深度为 $L_2$）需要维度 $d_2=\Omega (\log n)$ 才能解决 $T$

任务构造

该分离任务基于顺序依赖的性质：

编码器友好任务：并行处理所有输入位置
- 位置间无依赖
- 每层可独立处理

解码器困难任务：顺序读取并累积信息
- 当前输出依赖于所有前序输入
- 需要维持"工作记忆"

实践启示

这一分离对模型设计有重要启示：

场景	推荐架构	理由
序列标注	Encoder	并行处理，无需解码
序列生成	Decoder	自回归生成
序列到序列	Encoder-Decoder	各尽其用

链式思维的指数优势

从计算角度理解链式思维

一个深刻发现是：链式思维（Chain-of-Thought）提供了指数级的计算优势。

定理（链式思维优势）：对于某些硬任务 $T$，存在：

1. 无链式思维：需要 $d=\Omega (n)$ 维度的单次前向传播
2. 有链式思维：$d=O(1)$ 维度的 $O(\log n)$ 步推理即可解决

优势比：

$$\frac{\text{无CoT所需维度}}{\text{有CoT所需维度}}=\Omega (n)$$

即链式思维提供了指数级的效率提升。

机制解释

链式思维为何如此有效？从表达能力角度：

1. 虚拟深度增加：每生成一个中间token，相当于增加一层计算
2. 状态外部化：中间结果存储在token中，而非仅在隐藏状态中
3. 计算共享：相同参数可在不同步骤重复使用

数学形式化

设 $f$ 是需要执行的函数，$k$ 是链式思维中的推理步数。则有：

$$f(\mathbf{x})=g_k\circ g_{k-1}\circ \cdots \circ g_1(\mathbf{x})$$

其中每个 $g_i$ 可以由一层Transformer实现。关键在于：

$$\underset{\text{链式思维}}{\underbrace{\text{单次深度}\approx k}}\text{vs}\underset{\text{无链式思维}}{\underbrace{\text{所需等效深度}\approx \log n}}$$

多方通信模型

模型定义

为了证明下界，研究者引入了多方自回归通信模型。

设 $L+1$ 方，每方 $P_i$ 持有部分输入：

• $P_0$：持有输入 $\mathbf{x}$
• $P_i$（$1\le i\le L$）：持有函数 $f_i$ 的描述

各方可以按顺序通信，目标是计算 $f_L\circ \cdots \circ f_1(\mathbf{x})$。

通信协议复杂度

引理（通信下界）：任意正确协议需要至少 $\Omega (n\log n)$ 比特的通信。

证明思路：

1. 将输入空间划分为 $\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)$ 个区域
2. 每个区域需要不同的通信模式
3. 信息论下界给出通信量要求

协议-Transformer对应

该通信模型与Transformer存在精确对应：

通信模型	Transformer
每方信息	每层参数
通信轮数	Transformer层数
通信量	模型维度
协议长度	计算深度

技术细节

区分性分解技术

证明的关键创新是区分性分解（Indistinguishable Decomposition）技术：

对于任意可能的输入集合 $\{x_1,x_2,\dots ,x_m\}$，递归构造一个分解：

1. 基础分解：将输入划分为不可区分的组
2. 迭代细化：对每个组继续分解
3. 深度控制：分解深度精确控制维度需求

迭代不可区分分解算法

def iterative_indistinguishable_decomposition(inputs, depth):
    """
    递归分解输入空间
    """
    if depth == 0 or len(inputs) <= 1:
        return [inputs]
    
    # 划分输入为近似不可区分的组
    groups = partition_indistinguishable(inputs)
    
    # 对每个组递归分解
    result = []
    for group in groups:
        result.extend(
            iterative_indistinguishable_decomposition(group, depth-1)
        )
    
    return result

局限性与开放问题

当前局限性

1. 常数深度假设：只分析了 $L=O(1)$ 的情况
2. 精度限制：假设 $O(\log n)$ 精度
3. 任务特殊性：结论针对特定顺序组合任务

开放问题

1. 非恒定深度：$L=\omega (1)$ 时的表达能力？
2. 其他任务：更一般任务的下界是什么？
3. 上界：能否构造更紧的上界？

与实践的联系

模型设计启示

理论下界对实践有重要启示：

1. 深度有限：对于非常深的组合，纯靠增加层数不是解决方案
2. 链式思维必要：复杂推理任务需要链式思维或类似机制
3. 维度重要性：在深度受限时，增加宽度是有效策略

计算预算分配

给定总计算预算 $C$，如何分配深度和宽度？

$$C\approx \underset{\text{深度}}{\underbrace{L}}\times \underset{\text{每层计算}}{\underbrace{d^2}}$$

最优策略：根据任务组合深度选择：

任务复杂度	推荐策略
浅组合（<5步）	较多层、较小宽度
中等组合（5-10步）	适中深度和宽度
深组合（>10步）	链式思维 + 适度深度

总结

多层Transformer表达能力的研究揭示了以下关键发现：

1. 无条件下界：顺序组合任务需要多项式维度（首个无条件证明）
2. 深度-宽度权衡：$d=\Omega (n^{1/L})$ 的精确权衡关系
3. 编码器-解码器分离：存在只编码器可高效处理的任务
4. 链式思维指数优势：链式思维提供 $\Omega (n)$ 的维度节省

这些结果为理解Transformer的计算极限和指导架构设计提供了理论基础。

参考

Footnotes

1. Theoretical limitations of multi-layer Transformer. ICLR 2025. arXiv:2412.02975 ↩