Transformer 长度泛化的代数分解理论

已知基于 Transformer 的语言模型有时能够泛化到比训练期间见过的序列更长的序列，但我们仍缺乏对哪些任务允许长度泛化的精确刻画。甚至还不知道 Transformer 会在哪些正则语言上进行长度泛化——而这是一类基础性的语言。我们的贡献在于首次建立了对 Transformer 会在哪些正则语言上进行长度泛化的完整刻画，并提供了一种决策算法，其运行时间相对于该语言的句法幺半群大小为多项式时间。这些结果依赖于对 C-RASP 中正则语言的有效刻画；C-RASP 是一种近期建立的形式体系，用于表达 Transformer 会在哪些语言上进行长度泛化。这一刻画具有挑战性，因为有限半群的 Krohn-Rhodes 分解理论等经典工具不足以用于 C-RASP。首先，Krohn-Rhodes 理论的基本构件——flip-flop 和 simple groups——无法在 C-RASP 中表达。其次，C-RASP 的基本构件（无界计数）无法由 Krohn-Rhodes 理论中的有限半群表达。因此，正则语言上的长度泛化受一种代数性质控制，而这种性质在经典有限分解理论中是不可见的。我们将经典分解理论从有限半群推广到整数上的无限加法群，使我们能够用整数的迭代 wreath products 来刻画 C-RASP，并推导出一个可证明的、用于判定正则语言成员资格的多项式时间算法。在广泛的正则语言测试套件上进行的实验表明，我们的理论比现有分类更准确地捕捉了 Transformer 的长度泛化行为。