Algebraic Decomposition Theory for Transformer Length Generalization
Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs, Charles Paperman, Howard Straubing, Michael Hahn
cs.FL, cs.AI
2026-08-14
给出正则语言是否属 C-RASP 的多项式判定算法。125 个语言上 GPT-2 类内近乎完美外推到 10 倍训练长度，类外迅速崩溃。
Transformer 有时能处理比训练更长的序列，有时不能。即便把问题缩到正则语言，有限自动机就能识别的那一类，也没有完整答案。Huang 等人 2025 年的 C-RASP 给出过经验对应：落在这个带计数的受限程序语言里的任务，Transformer 往往会长度泛化；落在外面的不会。缺的是判定手续。给定一门正则语言，能不能机械判断它属不属于 C-RASP。
开篇那对语言很刺眼。(ab+bbaa) 和 (ab+aabb) 两个 DFA 结构几乎一样，训练长度都卡在 50 以内，测到 150。一个能外推，一个不能。星无关、R-平凡、可解群这些现成分类都解释不了这对反差。
Krohn-Rhodes 分解是有限幺半群的经典工具，基本积木是翻转触发器 U2 和单群。两边都不对。C-RASP 写不出 U2；C-RASP 的基本积木是无界计数，对应整数加法群 Z，有限半群表达不了。长度泛化卡在一道对经典有限分解理论不可见的代数性质上。
论文把分解从有限半群扩到 Z。直接拿经典圈积会过强：Z 圈上 Z 几乎能识别任意语言。解决办法是 typed monoid，给无限幺半群加上有限布尔代数当「类型」，只允许类型能区分的接受集。在这个约束下，一条语言属于 C-RASP，当且仅当它的句法幺半群落在 Z 的有类型圈积闭包里。正则语言这一侧，这等价于有界深度 Dyck 语言的圈积。
判定算法的直觉是「除以 Z」。用 Tilson 的派生范畴把关系态射的核提出来，按 R-类从左往右迭代，每一步找一个在当前类上有界、且线性无关的关系到 Z 的态射。成功则构造出到 Z 圈积的除法；失败则证明更短的圈积也不存在。时间对幺半群大小是多项式的。
还有一条更便宜的必要条件，不是充分条件：幺半群满足方程 (xy^ω)^ω x = (xy^ω)^ω，等价于无周期且每个 R-类至多一个幂等元。层级是 R ⊂ C-RASP ∩ REG ⊂ R^ω ⊂ A ⊂ REG，每一级都是真包含。
实验用 125 个正则语言，部分来自前人，部分用概率上下文无关文法采样。任务是状态预测：读前缀，报当前 DFA 状态。模型是 GPT-2，每语言 1 万条训练串，长度从最短合法串到 50，测到 [451, 500] 共 9 个长度桶，每桶 1000 条。位置编码换成全零（NoPE），符号之间插入分隔符，强迫模型走注意力，堵住「只看最后一个字符」的捷径。
成功标准是分布内准确率先打到 100%，并且在超过 2 倍最大训练长度时仍接近分布内表现。每个配置最多试 1000 个随机种子，凑齐 5 个分布内满分的 run。C-RASP 内的语言在远超训练长度时仍接近满分；类外语言刚过训练长度就垮。训练数据加到 10 万条，趋势不变。另做 50 个嵌套更深的语言、训练长度提到 200，结论一样。
相对 Li 与 Cotterell 2025 年更悲观的结论（他们只测了 3 个落在 C-RASP 但不在 R 里的语言，从 N 测到 12N），这篇在同一细类上从 N 测到 10N 仍然能外推。C-RASP 成员资格比 R-平凡、R∘G 这些现成分类更能分开能外推和不能外推的语言。
想知道某个有限状态跟踪任务，例如固定深度的括号匹配、受限 JSON、工作流状态机，Transformer 能不能长度外推，现在有了可跑的判定：算出句法幺半群，看它能不能拆成 Z 的圈积。这跟「Transformer 表达力」不是同一件事。常数深度、多项式精度的 Transformer 大约落在 TC0，可解正则语言都能表达；长度泛化卡的是更窄的一类。COLM 2026 给出的是可跑的判定。
从业者侧，这是一条硬边界，不是多堆层、多喂数据就能跨过去的。10 万条训练样本也救不回类外语言。位置编码还没纳入这套判定。带绝对位置编码的对应物是 C-RASP[periodic, local]，代数侧的决策手续要另做。
实验全是去掉位置编码的小 GPT-2，不是带 RoPE 的真实预训练模型。任务是人造状态预测，并且故意挡住对最后一个 token 的残差捷径；真实解码并不这样。主图报的是最好的成功种子，附录给了 5 个成功种子的平均，类外同样垮，但类内方差只画在图上、没有表。R^ω 减去 C-RASP 的样本很少，那条必要非充分方程 empirically 不太好用。整套理论只管正则语言，上下文无关的括号匹配和自然语言都不在范围内。