Characterizing the Expressivity of Fixed-Precision Transformer Language Models¶

会议: NeurIPS 2025
arXiv: 2505.23623
代码: GitHub
领域: LLM理论
关键词: transformer expressivity, formal language theory, linear temporal logic, fixed precision, length generalization

一句话总结¶

精确刻画了固定精度、严格未来掩码、软注意力、无位置编码的 Transformer 的表达能力——恰好等价于仅含过去算子的线性时态逻辑 LTL[P]，并将其与偏序确定有限自动机 (PODFA)、$\mathcal{R}$-trivial 幺半群统一起来。

研究背景与动机¶

领域现状：Transformer 的理论表达能力是重要开放问题。现有工作通过将 Transformer 与形式语言、逻辑、电路复杂度关联来分析。Yang et al. (2024) 证明固定精度+唯一硬注意力 (UHA) 的 Transformer 等价于完整的 LTL[P,F,S,U]（含四个时态算子）。Yang & Chiang (2024) 分析了软注意力版本，证明其上界是 C-RASP，但精确刻画是开放问题。
现有痛点：
很多理论假设任意精度或与长度相关的精度，高估了实际 Transformer 的能力
UHA（唯一硬注意力）与实际使用的 softmax 注意力差距大
软注意力+固定精度 Transformer 的精确表达力刻画仍缺失
核心矛盾：实际部署的 Transformer 使用固定精度（16/32 位）和软注意力，但理论结果要么假设更强的模型（任意精度），要么用更简单的注意力（硬注意力），无法直接指导对实际模型能力的理解。
本文要解决什么？ 给出固定精度+软注意力+严格掩码+无位置编码的 Transformer 的精确表达力刻画。
切入角度：双向归约——证明这类 Transformer 可以被翻译为 PFO²[<]（两变量过去一阶逻辑），同时 LTL[P] 的每个公式都能被 Transformer 模拟。
核心idea一句话：固定精度软注意力 NoPE Transformer 的表达力恰好是 LTL[P]——只能看过去、只能做有限次计数的逻辑。

方法详解¶

整体框架¶

本文是纯理论工作，核心贡献是建立等价链： $$\text{Fixed-precision Soft-Attn NoPE Transformer} = \text{PFO}^2[<] = \text{LTL}[\text{P}] = \text{PODFA} = \mathcal{R}\text{-trivial monoids}$$ 证明分两步：(1) Transformer → PFO²[<]（上界）；(2) LTL[P] → Transformer（下界）。加上 PFO²[<] = LTL[P]（本文独立证明），得到精确刻画。

关键设计¶

上界：Transformer → PFO²[<]：
做什么：证明任何固定精度 Transformer 识别的语言都可以用 PFO²[<] 公式描述
核心思路：固定精度下注意力权重只能取有限多个值。由于各位置的注意力分布相同（NoPE），注意力模式只依赖于"过去哪些 token 出现过"和出现次数（但被有限精度截断），这恰好是 PFO²[<] 可以表达的
关键洞察：软注意力在固定精度下的"加权平均"实际上只能区分有限多种情况，这使得其能力大幅弱于理论上的任意精度版本
下界：LTL[P] → Transformer：
做什么：证明 LTL[P] 中的任何公式对应的语言都可以被 Transformer 识别
核心思路：LTL[P] 公式可以递归构造。原子公式 $\pi_a$（"当前符号是 a"）trivially 可实现；布尔运算在任何精度下都可实现；过去算子 P（"过去是否存在满足 $\psi$ 的位置"）可以通过注意力机制实现——注意力可以聚焦到满足 $\psi$ 的历史位置
关键洞察：NoPE 条件下没有 F（未来）、U（直到）、S（自此以来）算子的模拟能力，所以表达力严格弱于 LTL[P,F,S,U]
LTL[P] 与 PODFA 和 $\mathcal{R}$-trivial 幺半群的等价：
做什么：将逻辑的刻画连接到自动机理论和代数理论
PODFA：偏序确定有限自动机——状态转移图构成偏序的 DFA
$\mathcal{R}$-trivial 幺半群：句法幺半群的 $\mathcal{R}$-类都是平凡的
语言理论角度：恰好是左确定多项式 (left-deterministic polynomials) 识别的语言类
扩展到 Transformer 语言模型：
做什么：证明 Transformer LM（生成模型而非识别器）具有相同的表达力
核心思路：LM 通过 $p(\text{eos} | \mathbf{w})$ 的阈值隐式定义语言识别，与识别器等价

损失函数 / 训练策略¶

不涉及训练策略改进——纯理论加实验验证

实验关键数据¶

主实验¶

长度泛化实验（训练在短序列上，测试长序列）：

语言	在 LTL[P] 内？	长度泛化准确率
$(ab)^*$	✅	100%
$a^b^$	✅	100%
所有 LTL[P] 内语言	✅	100%
Bounded Dyck-1	❌	< 100%
$(aa)^*$ (需要计数)	❌	失败
所有超出 LTL[P] 的语言	❌	一致失败

消融实验¶

配置	结果	说明
不同学习率/随机种子	结论不变	LTL[P] 内始终成功，外始终失败
增加层数/头数	LTL[P] 外仍失败	架构变化不改变理论极限

关键发现¶

理论与实践高度吻合：LTL[P] 内语言 100% 泛化，外无一例外失败
固定精度+NoPE 严重限制能力：很多看似简单的语言（如 bounded Dyck、偶数长度串）都超出其能力
软注意力 ≠ 硬注意力：软注意力(本文)只能表达 LTL[P]，而 UHA 可以表达完整 LTL[P,F,S,U]——差距巨大

亮点与洞察¶

精确刻画而非上下界：与大多数表达力分析工作不同，本文给出了完整的等价刻画，不留下任何空隙
多个数学框架的统一极为优雅：逻辑（LTL[P]）= 自动机（PODFA）= 代数（$\mathcal{R}$-trivial）= 语言学（左确定多项式）= 计算模型（固定精度 Transformer）
实际启示：NoPE Transformer 的能力远弱于通常认为的——甚至不能可靠地做括号匹配。这解释了为什么位置编码对 Transformer 如此重要

局限性 / 可改进方向¶

仅限 NoPE（无位置编码）：实际 Transformer 使用 RoPE/APE/ALiBi 等位置编码，加入位置编码后的精确刻画是重要开放问题
固定精度 = 理想化：实际训练中梯度和激活的数值行为比理论假设复杂
仅考虑语言识别/生成：未涉及 Transformer 在推理、算术等非语言任务上的表达力
改进方向：(1) 加入 RoPE 后的表达力刻画；(2) 扩展到 Transformer with scratchpad/chain-of-thought

评分¶

新颖性: ⭐⭐⭐⭐⭐ 精确表达力刻画是该领域最难的问题类型，等价证明和多框架统一都是重要贡献
实验充分度: ⭐⭐⭐⭐ 精心设计的语言层次结构+长度泛化实验，理论预测与实验完美吻合
写作质量: ⭐⭐⭐⭐⭐ 结构清晰（Figure 1 路线图极好），数学严谨，对非专家也有可读性
价值: ⭐⭐⭐⭐⭐ 为理解 Transformer 能力边界提供了最精确的理论基础之一

语言	在 LTL[P] 内？	长度泛化准确率
\((ab)^*\)	✅	100%
\(a^b^\)	✅	100%
所有 LTL[P] 内语言	✅	100%
Bounded Dyck-1	❌	< 100%
\((aa)^*\) (需要计数)	❌	失败
所有超出 LTL[P] 的语言	❌	一致失败