Transformer计数能力与半代数属性

1. 引言

Transformer的表达能力一直是理论研究的热点问题。传统观点认为，Transformer的表达能力受限于线性组合或简单的非线性变换。但最近的研究揭示了一个令人惊讶的结果：Transformer可以表达任意半代数计数属性，这涉及任意次数的多项式不等式的布尔组合。¹

这意味着Transformer在计数任务上的表达能力远超之前理论框架（如C-RASP）所描述的线性限制。

2. 计数属性的形式化

2.1 计数属性的定义

定义（计数属性）：设字母表 $\Sigma =\{a_1,a_2,\dots ,a_m\}$。一个计数属性是满足以下条件的语言 $L\subseteq {\Sigma }^{\ast }$：

$$w\in L⟺\pi (w)\in L\text{对所有排列 }\pi$$

也就是说，字符串是否属于 $L$ 仅取决于各符号出现的次数，而非它们的位置。

2.2 Parikh向量

每个字符串 $w\in {\Sigma }^{\ast }$ 对应一个 $m$ 维Parikh向量：

$$\Psi (w)=(|w{|}_{a_1},|w{|}_{a_2},\dots ,|w{|}_{a_m})\in {\mathbb{N}}^m$$

其中 $|w{|}_{a_i}$ 表示符号 $a_i$ 在 $w$ 中出现的次数。

2.3 示例

属性	Parikh向量条件	分类
MAJ	$\Vert w{\Vert }_a>\Vert w{\Vert }_b$	线性
PARITY	$\Vert w{\Vert }_a\equiv 0(\mathrm{mod}2)$	模运算
$SQRT$	$\Vert w{\Vert }_b\le \Vert w{\Vert }_a^2$	非线性
$\text{PRIME}$	$\Vert w{\Vert }_a$ 是素数	复杂

3. 半代数集合

3.1 代数集合的定义

定义（半代数集合）：集合 $S\subseteq {\mathbb{N}}^m$ 是半代数的，如果它可以表示为有限个多项式不等式布尔组合的形式：

$$S=\{x\in {\mathbb{N}}^m:p_1(x)>0\}\cup \{x\in {\mathbb{N}}^m:p_2(x)=0\}$$

其中 $p_i\in \mathbb{Z}[X_1,\dots ,X_m]$ 是整系数多项式。

3.2 半代数集合的例子

• 线性不等式：$\{x:x_1+x_2>x_3\}$
• 二次不等式：$\{x:x_1^2<x_2\cdot x_3\}$
• 布尔组合：$\{x:(x_1>0)\wedge (x_2=0\vee x_3>1)\}$

3.3 半代数计数属性

定义：语言 $L$ 是半代数计数属性，如果存在半代数集合 $S$ 使得：

$$L=\{w\in {\Sigma }^{\ast }:\Psi (w)\in S\}$$

4. Transformer的表达能力

4.1 模型设置

考虑无位置编码的Transformer（NoPE）和齐次Softmax注意力（AHAT）：

$$\text{Attn}(Q,K,V{)}_i=\frac{1}{n}\sum _{j=1}^n\text{softmax}\left(\frac{Q_i{K}_j^{\top }}{\sqrt{d}}\right)V_j$$

定理 1.1（半代数表达性）：NoPE-AHAT可以捕获所有半代数计数属性。¹

这意味着对于任何半代数集合 $S$，存在一个Transformer $T$ 使得：

$$T(w)=1⟺\Psi (w)\in S$$

4.2 关键引理：多项式构造

引理 3.1（多项式构造）：对于任何多项式 $p\in \mathbb{Z}[X_1,\dots ,X_m]$，存在一个NoPE-AHAT网络计算 $p(\Psi (w))$。

证明概要：

1. 频率计算：使用均匀注意力计算每个token的比例：

$${\hat{x}}_i=\frac{\text{index}(w_i)}{n+1}$$

2. 乘法Gadget：利用ReLU和均匀注意力构造乘积：

$$x_{i_1}\cdot x_{i_2}\approx \frac{1}{n}\sum _j\text{ReLU}(x_j-x_{i_1})\cdot \text{ReLU}(x_{i_2}-x_j)$$

3. 多项式求值：通过有限次加法和乘法组合得到 $p(\Psi (w))$。

4.3 实现细节

算法 1（多项式计算）：

def polynomial_attention(x, coefficients, degrees):
    """
    使用注意力机制计算多项式
    x: 输入token特征 (n, d)
    coefficients: 多项式系数
    degrees: 每个变量的指数
    """
    n, d = x.shape
    
    # 步骤1: 计算频率（归一化位置）
    positions = torch.arange(n).float() / (n + 1)
    freq = positions.unsqueeze(0).expand(n, -1)  # (n, n)
    
    # 步骤2: 使用均匀注意力提取频率
    uniform_attn = torch.ones(n, n) / n
    extracted_freq = uniform_attn @ positions  # 近似均匀采样
    
    # 步骤3: 计算单个token的"值"
    token_value = extracted_freq  # 近似 x_i/(n+1)
    
    # 步骤4: 构造乘积（利用ReLU的线性分段特性）
    def multiply_gadget(a, b):
        # 近似 a * b
        return (a + b - torch.abs(a - b)) / 2
    
    # 步骤5: 组合单项式
    monomials = []
    for coef, deg in zip(coefficients, degrees):
        term = coef * token_value ** deg[0]
        for d in deg[1:]:
            term = multiply_gadget(term, token_value ** d)
        monomials.append(term)
    
    # 步骤6: 求和得到多项式
    polynomial = sum(monomials)
    
    return polynomial
 
def check_semialgebraic(x, inequality_type='>'):
    """检查半代数条件"""
    return x > 0 if inequality_type == '>' else x == 0
 
def transformer_semialgebraic_classifier(x, polynomials, operators):
    """
    Transformer半代数属性分类器
    x: 输入序列
    polynomials: 多项式列表
    operators: 布尔操作符列表 ('>', '=', '&', '|')
    """
    values = [polynomial_attention(x, *p) for p in polynomials]
    
    results = [check_semialgebraic(v, op) for v, op in zip(values, operators)]
    
    # 组合布尔结果
    final_result = results[0]
    current_op = None
    for i, (r, op) in enumerate(zip(results[1:], operators[1:])):
        if op == '&':
            final_result = final_result & r
        elif op == '|':
            final_result = final_result | r
    
    return final_result

5. 表达能力对比

5.1 C-RASP的局限性

C-RASP框架证明了Transformer可以捕获线性时间逻辑（LTL）：

$$\varphi ::=◯\varphi \mid {\varphi }_1\mathcal{U}{\varphi }_2\mid {\varphi }_1\wedge {\varphi }_2$$

但C-RASP的表达能力被限制为线性计数：

$$\{\Psi (w):\ell (\Psi (w))>c\}\text{其中 }\ell \text{ 是线性的}$$

5.2 表达能力边界

关键发现：存在Transformer可表达但C-RASP无法表达的计数属性。

例 5.1：对于 $k\ge 2$，语言

$$L_k=\{w\in \{a,b{\}}^{\ast }:|w{|}_b\le (|w{|}_a{)}^k\}$$

是半代数的（多项式不等式 $(|w{|}_a{)}^k-|w{|}_b\ge 0$），但不是线性时间逻辑可表达的。

5.3 对比表

属性	C-RASP	Transformer	说明
MAJ	✓	✓	线性不等式
PARITY	✗	✓	模运算（有限状态机）
$SQRT$	✗	✓	二次不等式
PRIME	✗	✓	任意复杂多项式

6. 通用性与不可判定性

6.1 通用性定理

定理 1.2（捕获精确类）：NoPE-AHAT[U]捕获的语言类恰好是所有半代数计数属性。

定理 1.3（两层通用性）：任何递归可枚举的计数属性都可以用仅有两层注意力的NoPE-AHAT[U]识别。

这意味着简单的两层Transformer已经具有极强的表达能力。

6.2 不可判定性

定理 1.4（不可判定性）：给定一个两层NoPE-AHAT或SMAT，判断其语言是否为空是不可判定的。

这建立了Transformer表达能力与停机问题的联系——过强的表达能力带来了计算复杂性挑战。

7. 表达能力的新分类

基于计数能力，Transformer的表达能力可以重新分类：

7.1 表达能力层次

Level 0: 仅位置信息（无表达能力）
Level 1: 线性计数（C-RASP上限）
Level 2: 半代数计数（Transformer实际能力）
Level 3: 递归可枚举（两层Transformer）
Level 4: 不可判定（停机问题等价）

7.2 电路复杂度视角

Transformer的表达能力与电路复杂度有关：

• 常数深度注意力 ⊆ AC⁰（有界AND/OR/NOT）
• O(log n)深度注意力 ⊆ TC⁰（阈值电路）
• 多项式深度注意力 = P（多项式时间）

注意：计数属性主要与TC⁰（阈值电路）相关。

8. 与其他理论的关系

8.1 与热带几何的联系

Transformer的表达能力可以通过热带代数来刻画：

• 注意力操作对应热带矩阵乘法
• Softmax对应热带Softmax
• 整体网络对应热带电路

这与现有的Transformer热带几何理论一致。²

8.2 与WL测试的关系

半代数计数属性的表达能力：

• 弱于1-WL测试（图同构测试）
• 强于颜色细化算法（仅限于有限状态）
• 不包含图属性

8.3 与电路复杂度的联系

Transformer变体	电路复杂度	表达能力
恒定深度+宽度	AC⁰	有限状态
对数深度	TC⁰	半代数计数
多项式深度	P	递归可枚举

9. 实践意义

9.1 算法任务

计数能力对于以下算法任务至关重要：

1. 图算法：计数三角形、路径、子图
2. 集合运算：交集、并集、包含关系
3. 约束满足：SAT、伪布尔约束
4. 程序分析：循环计数、资源分析

9.2 训练建议

理解Transformer的计数能力可以帮助设计更好的训练策略：

• 对于计数任务，足够的宽度比深度更重要
• 位置编码可能削弱计数能力（引入位置偏差）
• 无位置编码（NoPE）在纯计数任务上表现更好

9.3 架构设计

计数能力理论指导架构选择：

任务类型	推荐架构
精确计数	NoPE + 足够宽度
近似计数	线性注意力
位置相关计数	相对位置编码
层次计数	分层注意力

10. 开放问题

1. Softmax的作用：Softmax注意力是否比均匀注意力表达能力更强？
2. 深度需求：表达能力如何随深度增长？
3. 训练动力学：为什么Transformer能学习到理论保证的计数能力？
4. 泛化边界：理论与实践之间的差距来源是什么？

11. 总结

Transformer的计数能力研究揭示了几个重要发现：

1. 表达能力远超预期：Transformer可以表达任意半代数计数属性
2. 多项式是关键：表达能力来源于对多项式运算的隐式实现
3. 通用性惊人：仅两层注意力就具有通用表达能力
4. 不可判定性：过强的表达能力带来了计算复杂性挑战

这些发现为理解和设计Transformer架构提供了新的理论基础。

---

Footnotes

1. Sälzer, M., et al. “The Counting Power of Transformers.” arXiv 2025. https://arxiv.org/abs/2505.11199 ↩ ↩²

2. 本理论与Transformer热带几何表达能力密切相关。 ↩