知识卡片：Transformer长度泛化的代数分解理论

一句话结论

本文首次完整刻画了Transformer在正则语言上的长度泛化能力，并给出一个以语言句法幺半群大小为参数的多项式时间判定算法。

事件概述或研究问题

Transformer语言模型有时能泛化到比训练时更长的序列，但缺乏对“哪些任务允许长度泛化”的精确刻画。正则语言是语言理论中的基础类别，此前甚至不知道Transformer能在哪些正则语言上实现长度泛化。本文解决这一问题，其核心工具是对C-RASP形式体系的代数刻画。

方法/产品要点

• 研究对象是C-RASP，一个近期建立的形式体系，用于表达Transformer能长度泛化的语言。
• 经典Krohn-Rhodes有限半群分解理论不足以刻画C-RASP：其基本构件（flip-flop和单群）在C-RASP中不可表达；而C-RASP的基本构件（无界计数）无法用有限半群表达。
• 本文将经典分解理论从有限半群推广到整数上的无限加法群，用整数的迭代圈积（iterated wreath products）刻画C-RASP，并由此推导出正则语言成员资格的多项式时间判定算法。
• 实验在广泛的正则语言测试集上进行，验证该理论比现有分类更准确地捕捉Transformer的长度泛化行为。

主要结果或产业意义

• 建立了“哪些正则语言可被Transformer长度泛化”的第一个完整刻画。
• 提供了运行时间关于语言句法幺半群规模呈多项式的决策算法。
• 指出长度泛化受控于一种经典有限分解理论无法看到的代数性质，揭示现有代数工具在该问题上的盲区。

为什么重要

此前对Transformer长度泛化的理解多依赖位置编码或具体训练机制（如RoPE的频率使用），缺乏基于语言结构本身的系统判据。本文从代数分解视角给出了正则语言层面的完整答案，并为后续扩展到更复杂语言提供了理论基础。相对已有关于RoPE数据驱动解释的卡片，本条提供的是形式语言与代数复杂性方向的独立刻画，属于不同维度的互补进展。

局限与不确定性

• 论文摘要未提供实验具体数值和比较基准细节，实验效果的具体程度待核实。
• 刻画仅针对正则语言；对上下文无关语言或更复杂任务的适用性待核实。
• 判定算法基于句法幺半群，实际计算中构造句法幺半群的开销未在摘要中说明，待核实。
• C-RASP与实际Transformer架构（如注意力头数、层数、数值精度）之间的精确对应关系待核实。

可用于图书/PPT/简报的角度

• 用“计数能力”解释Transformer长度泛化的边界：无界计数是C-RASP的核心构件，但经典有限半群理论无法处理它。
• 以“从有限半群到整数群”为线索，展示如何改造经典代数工具以适应深度学习理论问题。
• 对比“数据驱动”（RoPE频率匹配）与“结构驱动”（正则语言代数）两种解释长度泛化的视角。

与既有脉络的关系

已有卡片讨论了RoPE频率使用如何受数据影响，从而影响长度泛化；本卡片补充了一个不依赖具体位置编码的代数刻画：在正则语言层面，长度泛化能力由C-RASP决定，可由句法幺半群的多项式时间算法判定。这是对长度泛化理论基础的重要增量。

原始材料

• 英文标题：Algebraic Decomposition Theory for Transformer Length Generalization
• 英文关键词：Transformer, Length Generalization, Regular Languages, Algebraic Decomposition, C-RASP
• 原始来源：https://arxiv.org/abs/2608.13433v1
• 作者：Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs, Charles Paperman, Howard Straubing, Michael Hahn
• 发布/更新：2026-08-13
• 分类：cs.FL, cs.AI