ICLR 2026 学习理论 Transformer 表达力 Transformer 自回归语言模型加权自动机线性时序逻辑形式语言

Probability Distributions Computed by Autoregressive Transformers¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=gZIcyx1tQY
代码: 待确认
领域: 学习理论 / Transformer 表达力
关键词: Transformer 表达力, 自回归语言模型, 加权自动机, 线性时序逻辑, 形式语言

一句话总结¶

这篇论文把 Transformer 表达力研究从"分类器"（接受/拒绝整串）的传统设定，扩展到它实际被使用的"自回归概率语言模型"设定，证明了「自回归」与「实数权重（概率）」这两个改动会改变甚至打破已有的等价结论——有时让 Transformer 变强，有时让分类器与自回归彼此不可比。

研究背景与动机¶

领域现状：绝大多数关于 Transformer 表达力的理论工作（Yang et al. 2024、Jerad et al. 2025、Li & Cotterell 2025 等）都把 Transformer 当作语言识别器（language recognizer）来分析：输入一整串，输出一个布尔判定（接受还是拒绝）。在这个设定下已经积累了一批漂亮结论，例如唯一硬注意力 Transformer（UHAT）作为分类器，恰好等价于线性时序逻辑（LTL）和无计数器有限自动机（counter-free DFA / cfDFA）。

现有痛点：可是 Transformer 在实践中根本不是这么用的。真实的语言模型有两点本质不同：第一，输入是一个前缀而不是整串，输出是对下一个 token 的预测；第二，输出是一个概率分布而不是布尔判定。也就是说，理论研究的对象（布尔权重的分类器）和实际使用的对象（实数权重的自回归器）之间，隔着两道没人系统跨越过的鸿沟。

核心矛盾：没人验证过那些"识别器时代"的等价结论，在搬到"语言模型"设定后还成不成立。如果成立，那现有理论就能直接复用；如果不成立，就说明把识别器的结论当成语言模型的结论是有风险的——而这种默认搬运恰恰是文献里常见的做法。

本文目标：把表达力问题沿两个独立维度拆开——(1) 未加权（布尔权重）vs 实数权重，(2) 分类器（整串→标量）vs 自回归器（每个前缀→下一符号分布），构成一个 2×2 的四象限，然后逐格回答"已有等价性在这一格还成不成立"。

切入角度：作者引入一个统一抽象——状态编码器（state encoder），把 Transformer、DFA、LTL 都看成"把串映射成状态序列、且第 i 个状态只依赖前缀 \(w_{\le i}\)"的同一类对象，再给它配不同的输出函数，就能在同一框架下同时谈分类器和自回归器。

核心 idea：用"状态编码器 + 输出函数"这一对组件，把表达力问题统一参数化为「分类器输出函数 vs 自回归输出函数」「布尔半环 vs 实半环」，从而精确刻画出哪些等价性会被自回归化 / 概率化打破。

方法详解¶

整体框架¶

本文不是提一个新模型，而是建一套形式化框架来回答"Transformer 作为概率语言模型到底能表达哪些分布"。整体思路分三步走：先用状态编码器这个抽象把 Transformer、DFA、LTL 统一到同一层（它们都是"前缀→状态"的函数）；再给状态编码器配两种输出函数，分别得到分类器与自回归器两种"用法"；最后在布尔半环和实半环两种权重下，逐一比较这四种组合（见原文 Fig. 1 的四象限）的表达力，得出一串"等价 / 严格包含 / 不可比"的分离结论。

整篇论文的逻辑骨架是：把"加权语言"\(S:\Sigma^*\to K\) 当作研究对象（\(K\) 是半环），分类器和自回归器只是把同一个状态编码器变成加权语言的两种不同方式，于是表达力比较就归结为"哪种输出函数能写出哪些加权语言"。

关键设计¶

1. 状态编码器：把 Transformer / DFA / LTL 统一成同一类对象

传统研究里 Transformer、有限自动机、时序逻辑是三套各说各话的形式系统，难以在同一标尺下比较"作为语言模型"的能力。本文用状态编码器统一它们：一个状态编码器是把串 \(w_1\cdots w_n\) 映射成状态序列 \(q_0,\dots,q_n\in Q\) 的函数，且关键约束是 \(q_i\) 只依赖前缀 \(w_{\le i}\)（因果性）。Transformer 读到 \(w_i\) 后的隐状态 \(h^{(i)}\)、DFA 的转移结果 \(\delta^*(\iota,w_1\cdots w_i)\)、LTL 公式元组在位置 \(i\) 的真值向量 \(\Phi(w)_i=(\mathbb{I}\{w,i\models\phi_1\},\dots)\)，全都是合法的状态编码器。作者随即证明（Thm. 5.1）UHAT、LTL、cfDFA 定义的是等价的状态编码器（存在状态集之间的双射使三者状态序列一一对应），这是后续一切比较的地基——既然底层状态编码器等价，表达力差异就只可能来自"配什么输出函数 + 在什么半环里"。

2. 分类器 vs 自回归器：同一状态编码器的两种"读出"方式

有了状态编码器，本文把它的两种用法形式化。分类器只在最后一个位置读出一个标量权重：\(C(w)=c(T(w)_n)\)，整串对应一个值（布尔半环里就是接受/拒绝）。自回归器则在每个位置读出一个对下一符号（含 EOS）的权重分布 \(\Pr_A(\sigma\mid w_{\le i})=r(T(w)_i)(\sigma)\)，再把这些条件分布连乘成整串的权重：

\[\Pr_A(v\mid u)=\Big(\bigotimes_{i=1}^{|v|}\Pr_A(v_i\mid u v_{<i})\Big)\otimes\Pr_A(\mathrm{EOS}\mid uv)\]

并强制施加归一化条件：对任意前缀 \(u\)，\(\bigoplus_{v\in\Sigma^*}\Pr_A(v\mid u)=1\)。这个看似技术性的约束其实是分类器与自回归器表达力分歧的根源——它意味着自回归器定义的必须是归一化加权语言，并且"不能有死路也不能无限循环"（任何被采样到的前缀都能续成合法串）。正是这个归一化要求，让某些分类器能写、自回归器写不出（反之亦然）。

3. 实半环下的分离：分类器与自回归器不可比，且 UHAT 只等价 cfDFA

进入实数权重（概率）后，作者刻画出实分类器恰好能表达非周期阶梯函数（aperiodic step function）：\(S(w)=\bigoplus_{i=1}^m k_i\otimes\mathbb{I}\{w\in L_i\}\)，其中 \(k_i\) 是常数、\(L_i\) 是无计数器（非周期）正则语言。由此立刻得到一个反直觉结论（Cor. 5.4）：分类器与自回归器互不包含。例如加权语言 \((\tfrac12 a)^*\) 能被 LTL 自回归器表达（它有无穷多种串权重），却无法被任何 LTL 分类器表达（阶梯函数只能输出有限多种不同权重）；反过来 \((1a)^*\) 能被分类器表达，却不能被任何自回归器表达（因为它不是归一化加权语言）。更微妙的是：实半环下 UHAT/LTL 作为自回归器只等价于确定型 cfDFA，而加权无计数器 NFA 严格更强（Prop. 5.5，原文 Fig. 2c 给了一个不可确定化的反例），也就是说在布尔设定下等价的 cfDFA 与 cfNFA，到了实数权重下被拉开了差距，UHAT 只够到较弱的那一档。

4. 布尔半环下的分离：片段化 LTL 让自回归严格强于分类

在布尔半环里，完整 LTL 的分类器与自回归器是等价的（Thm. 5.6），但这个等价的证明里藏着关键不对称：从自回归器转回分类器，需要用到 \(\mathsf{Y}\)（Yesterday）和 \(\mathsf{H}\)（Historically）算子。这提示：一旦把算子集 \(O\) 砍掉 \(\mathsf{H}\) 或 \(\mathsf{Y}\)，等价就会崩。作者随即证实（Prop. 5.8）：语言 \((ab)^*\) 能被一个 \(\mathrm{TL}[\varnothing]\) 自回归器定义，却不能被任何 \(\mathrm{TL}[\mathsf{H}]\) 或 \(\mathrm{TL}[\mathsf{Y}]\) 分类器定义（\(\mathrm{TL}[\mathsf{Y}]\) 分不清末尾 \(k\) 个符号以外的差异，\(\mathrm{TL}[\mathsf{H}]\) 只能定义 stutter-invariant 语言而 \((ab)^*\) 不是）。由于 Li & Cotterell (2025) 与 Jerad et al. (2025) 已证明定点精度 SMAT、最左硬注意力 UHAT 恰好等价于 \(\mathrm{TL}[\mathsf{P}]\equiv\mathrm{TL}[\mathsf{H}]\)，这就直接推出：这些 Transformer 变体作为自回归器严格强于作为分类器。不过这种增益有上限——\((aab)^*\) 仍然两种用法都写不出来（Prop. 5.9）。同样的机制也解释了带计数算子的 \(\mathrm{TL}[\overset{\leftharpoonup}{\#}]\) 为何作为自回归器更强，从而解释了 Yang et al. (2025) 实验中"深度 \(k\) 的 SMAT 在符号预测任务上能解 \(L_{k+2}\) 而非只到 \(L_k\)"的现象。

一个例子：\((ab)^*\) 为什么自回归能写、分类写不了¶

取三元组公式 \(\Phi=(\mathrm{BOS},a,b)\) 作状态编码器，状态记录"当前在串首 / 上一个是 a / 上一个是 b"。自回归输出函数定义为：下一符号可出 \(a\) 当且仅当 \(q_{\mathrm{BOS}}\) 或 \(q_b\) 为真（即在串首或刚读完 b）；可出 \(b\) 当且仅当 \(q_a\) 为真（刚读完 a）；可结束（EOS）当且仅当在串首或刚读完 b。顺着走一遍：起点允许 \(a\) 或结束 → 读 \(a\) 后只允许 \(b\) → 读 \(b\) 后又回到允许 \(a\) 或结束，于是恰好生成 \(ab\,ab\,ab\cdots\) 即 \((ab)^*\)。而分类器只能在最后一位读一次状态、没法"每步约束下一符号"，在 \(\mathrm{TL}[\mathsf{Y}]\)/\(\mathrm{TL}[\mathsf{H}]\) 这种缺算子的片段里就无力区分 \((ab)^*\) 与混入 \(aab\) 的串——这把"自回归逐步约束"带来的额外表达力讲得很具体。

实验关键数据¶

本文是纯理论论文，没有训练实验，"结果"以定理/命题的形式给出。下表汇总四象限（原文 Fig. 1）的核心结论，可视作论文的"主结果表"。

主结果：四象限表达力对照¶

设定	分类器	自回归器	关系
布尔 · UHAT (=完整 LTL)	= LTL/cfDFA	= LTL/cfDFA	等价（Thm. 5.6）
布尔 · 最左 UHAT / 定点 SMAT (=TL[P]≡TL[H])	TL[P]	严格更强	自回归 > 分类（Prop. 5.8）
实数 · UHAT (=LTL)	非周期阶梯函数 = cfDFA = cfNFA	= cfDFA	分类与自回归不可比（Cor. 5.4）
实数 · cfNFA vs UHAT 自回归	—	UHAT 只到 cfDFA	cfNFA 严格更强（Prop. 5.5）

关键分离实例¶

加权语言	分类器可表达？	自回归器可表达？	说明
\((\tfrac12 a)^*\)（实半环）	否	是	串权重有无穷多种，阶梯函数只能输出有限种
\((1a)^*\)（实半环）	是	否	非归一化语言，违反自回归归一化约束
\((ab)^*\)（布尔，TL[H]/TL[Y]）	否	是	片段缺算子，自回归靠逐步约束补回
\((aab)^*\)（布尔，TL[H]）	否	否	区分 aab/aaab 需两层嵌套 Y，自回归→分类只补一个 Y

关键发现¶

归一化约束是分歧的总开关：实半环里分类器与自回归器不可比，根源就是自回归器被强制定义归一化加权语言，而分类器没有这个负担。
算子的缺失决定增益是否出现：完整 LTL 下自回归不增表达力；只有当片段缺了 \(\mathsf{Y}\) 或 \(\mathsf{H}\)，自回归"逐步预测下一符号"才会把分类器写不出的语言补回来。
构造代价存在下界：把 \(\mathrm{prefix}(\phi)\) 脱糖成等价 LTL 公式的大小是指数级的；除非 P=PSPACE（或相应 P=NP），否则不存在多项式时间的等价构造（Prop. 5.7），说明自回归→分类的转换本质上昂贵。

亮点与洞察¶

一个抽象统一三套形式系统：状态编码器把"第 i 个状态只看前缀 \(w_{\le i}\)"抽出来当公共接口，使 Transformer、DFA、LTL 能在同一标尺下被赋予"分类器/自回归器"两种用法——这个抽象本身就很可复用，可迁移到 RNN、SSM 等任意因果序列模型的表达力分析。
把"概率"当成一等公民：以往工作把概率分布当成事后归一化的细节，本文用半环把"布尔判定"和"实数概率"放进同一代数框架，于是"加权语言""归一化"这些概念能统一处理，揭示出概率化会打破布尔设定下的等价。
理论解释了别人的实验异常：Yang et al. (2025) 观察到深度 \(k\) 的 SMAT 在符号预测任务上能解到 \(L_{k+2}\)，本文用"\(\mathrm{TL}[\overset{\leftharpoonup}{\#}]\) 缺 Y 算子 → 自回归更强"一句话解释清楚，体现了框架的预测力。
方法论警示：直接把"语言识别器"的表达力结论搬给"语言模型"是有风险的——这条洞察对所有读 Transformer 理论文献的人都有校准意义。

局限与展望¶

模型类偏理想化：分析的是唯一硬注意力（UHAT）、定点精度 SMAT、无位置编码这类高度简化的 Transformer，离实际的对数精度 softmax 注意力 + 位置编码还有距离；作者明确把扩展到这些更现实的类列为未来工作。
缺自回归不可表达性的证明工具：在分类器与自回归器不重合（如实权重）的格子里，作者坦言目前没有好办法证明"某语言不能被自回归器表达"，这块技术留白限制了实半环下分离结论的完整性。
未触及思维链：现实语言模型常带 chain-of-thought（中间多步推理再出答案），本文只覆盖无中间步的自回归；实权重 + 思维链的自回归器能算出哪类概率分布（能否覆盖 BPP/PP）是开放问题。
纯理论、无实证验证：所有分离都是构造性反例，尚未在真实训练的 Transformer 上探查这些理论边界是否在有限精度/优化条件下实际显现。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统刻画 Transformer 作为概率自回归语言模型的表达力，并精确分离它与分类器的差异
实验充分度: ⭐⭐⭐⭐ 纯理论论文，定理体系完整且自洽，但缺少实证验证（作者亦承认）
写作质量: ⭐⭐⭐⭐⭐ 四象限框架清晰，反例选得精当，把抽象分离讲得可理解
价值: ⭐⭐⭐⭐⭐ 校准了"用识别器结论替代语言模型结论"的常见隐患，为后续表达力研究立了通用框架