Length Generalization for Transformers via Compression¶

会议: NeurIPS 2026
arXiv: 2609.08851
OpenReview: https://openreview.net/forum?id=gx6QOo6yY5
代码: https://github.com/lacoco-lab/length_generalization
领域: 学习理论
关键词: 长度泛化, 幂词压缩, C-RASP, 计数自动机, 样本复杂度

一句话总结¶

本文基于幂词（power words）压缩机制为 Transformer 的逻辑形式化语言 C-RASP+ 与 C-RASP1 建立了多项式级的压缩长度复杂度界，从而证明了样本复杂度仅随公式大小呈单重指数增长，成功消解了此前双重指数上界与 PARITY 变体实验相悖的理论困境。

研究背景与动机¶

大语言模型与 Transformer 架构在超出训练分布的序列长度上的泛化能力（Length Generalization）是近年理论与实证研究的核心热点。此前被广泛认可的理论支柱为 C-RASP 假说（即 RASP-l 猜想的形式化版本）：该理论指出，一个形式任务能够被有限精度的 Transformer 实现长度泛化，当且仅当该任务在 C-RASP 形式化规约语言中可表达。然而，现有 C-RASP 框架存在两项严重的理论阻碍：其一，通用的 C-RASP 语言已被证明不存在可计算的长度泛化界；其二，针对有限精度子集 C-RASP+ 与一阶计数深度子集 C-RASP1，已有研究虽给出了指数级的长度界，但推导出的样本复杂度上界却高达双重指数级别（doubly exponential），且理论界是否紧致悬而未决。

这种理论上的松弛直接引发了实验与理论预测的尖锐矛盾。典型代表是奇偶校验限制任务 $\text{PARITY}_k$（即包含至多 $2k$ 个字符 $a$ 且 $a$ 的数量为偶数的字符串识别任务）：由于对任意固定的 $k$，$\text{PARITY}_k$ 均可在 C-RASP 中定义，现有假说断言 Transformer 应能在此任务上实现长度泛化；但在实际经验中，哪怕对于极小的 $k$（例如 $k=50$），标准 Transformer 的长度外推依然严重失效。若缺乏一个关于公式复杂度与样本规模之间精确、紧致的函数界，理论便无法解释这一经验性反例究竟源自优化困境，还是需要天文数字级的超大训练样本才能触发泛化。

本文的切入角度是打破以常规无压缩字符串为基准的复杂性度量视角，引入计算群论中成熟的幂词（power words）游程压缩机制，在压缩字符串的度量下重新刻画 Transformer 假说类。核心 idea：将 C-RASP+ / C-RASP1 规约编译为反转受限计数自动机（RBCA）与整型向量加法系统（$\mathbb{Z}$-VASS），利用整数锥 Carathéodory 界证明满足条件的接受运行仅需多项式长度的幂词表达，进而将样本复杂度从双重指数下界压至单重指数，为细粒度预测任务泛化难度提供了坚实的理论工具。

方法详解¶

整体框架¶

本文的核心理论构造致力于证明：对于任意 C-RASP+ 或 C-RASP1 公式，存在一个多项式长度的压缩幂词（power word）能够区分不同的假设。整个证明管线自顶向下划分为三个严密的离散阶段：首先将规范化后的时态逻辑公式转化为反转受限带扩展守卫计数自动机（RBCAG），随后消解扩展守卫并编译为整型向量加法系统（$\mathbb{Z}$-VASS），最后在代数层面对 $\mathbb{Z}$-VASS 的接受运行进行圈消除，并通过离散线性方程极值解的界限控制重构出紧凑幂词。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入逻辑公式<br/>C-RASP+ / C-RASP1"] --> B["阶段1：逻辑编译为反转受限计数自动机<br/>Normal Form → RBCAG"]
    B --> C["阶段2：自动机等价消解与降阶<br/>消除守卫 → Z-VASS 归约"]
    C --> D["阶段3：代数环分解与多项式幂词压缩<br/>Carathéodory 支撑界 + 极值解上界"]
    D --> E["输出理论界：多项式压缩长度<br/>单重指数样本复杂度与细粒度分离"]

关键设计¶

1. 逻辑规范化与反转受限计数自动机编译：将时序计数约束映射为单调状态机 针对逻辑表达与自动机状态转换之间的结构鸿沟，该设计首先将 C-RASP+ 公式在多项式时间内规约为标准形式（Normal Form）：将公式解耦为当前符号验证（present formulas）与纯粹的历史时序验证（past formulas）。在此基础上构建计数自动机（RBCAG），设计两类专用计数器：第一类针对每个历史子公式 $\psi$ 设置单比特指示计数器，跟踪其在当前输入前缀下的真值；第二类针对时序计数加权和 $\sum \alpha_t t$ 设置线性累加计数器。由于 C-RASP+ 严格限制使用正系数且不含 $\mathbf{until}$ 算子，各时序约束条件的真值在序列滑动过程中仅经历常数次真值切换，从而使得计数器的反转次数受多项式严格约束，成功建立了从 Transformer 时态逻辑到可判定反转受限计数自动机（RBCA）的对数空间编译映射。

2. 整型向量加法系统归约：消除扩展守卫并实现代数效应抽象 为将包含丰富不等式测试的 RBCA 转化为纯代数计算模型，本文第二项关键设计是将守卫条件通过区间划分进行静态展开。通过提取所有比较常数边界 $\{k_1, \dots, k_m\}$，将原始计数器值改写为相对偏移量 $x - k_i$，并以辅助单比特计数器表征所属区间，从而将任意复杂的不等式守卫条件规约为对计数器的零测试。进一步地，利用已有判定性结论将无扩展守卫的 RBCA 线性规约为 $d$ 维整型向量加法系统（$\mathbb{Z}$-VASS）。在 $\mathbb{Z}$-VASS 体系中，自动机的每一次转移被完全抽象为在欧几里得网格 $\mathbb{Z}^d$ 上的整型更新向量，使得序列接受条件等价于寻找一条始于初态、止于终态且总效应向量代数和严格为零 $\mathbf{0} \in \mathbb{Z}^d$ 的路径。

3. 环分解与基于 Carathéodory 界的多项式幂词重构：利用代数压缩消解指数级样本爆炸 为证明任何可满足公式均能被紧凑压缩字符串表征，该设计提出了基于图论环消除与仿射整型规划极值界的压缩方案。对于 $\mathbb{Z}$-VASS 上的任意有效接受路径 $\rho$，算法首先标记首次访问各状态的关键转移，进而剥离所有不包含标记边的简单圈，得到长度至多为 $|Q|(|Q|+1)$ 的基础无圈骨架路径 $\sigma$。此时被剥离的简单圈集合 $\{\pi_1, \dots, \pi_k\}$ 的累积效应与骨架路径效应 $\Delta(\sigma)$ 构成线性丢番图方程 $\mathbf{A}\mathbf{x} = -\Delta(\sigma)$，其中 $\mathbf{x} \in \mathbb{N}^k$ 为非负整数解。

本文关键突破在于利用 Eisenbrand & Shmonin 的整数锥 Carathéodory 定理：证明该方程必然存在一个稀疏支撑解 $\mathbf{x}'$，其非零分量个数至多为： $$|\mathsf{supp}(\mathbf{x}')| \leq 2d \log(4d \|\mathbf{A}\|_\infty)$$ 结合 von zur Gathen 与 Sieveking 针对整型线性方程解范数的极值分析，确定各非零系数的上界为 $\|\mathbf{x}'\|_\infty \leq (d+1)d^{d/2}\max(\|\mathbf{A}'\|_\infty, \|\mathbf{b}\|_\infty)^d$。由于选出的简单圈数量为多项式阶，且每个圈的重复倍数以二进制编码后长度仅为多项式阶，重新将这些圈以幂词形式 $u_0 \langle v_1 | \mu_1 \rangle \dots \langle v_\ell | \mu_\ell \rangle u_\ell$ 插入骨架路径中，所得幂词的字符长度关于原公式大小仅为多项式阶。由此直接推论，假设空间中由多项式幂词覆盖的样本集大小仅呈单重指数增长 $\mathcal{O}(2^{\mathsf{poly}(|\phi|)})$，正式推翻了此前双重指数的粗糙上界。

损失函数 / 训练策略¶

实验验证严格遵循 Huang et al. (2025) 的标准化协议以确保可比性： - 模型配置：采用标准的 4 层、2 头的 Transformer 编码器结构，词嵌入维度设置为 256。 - 优化器与学习率：采用 Adam 优化器，学习率设为 $1 \times 10^{-3}$，批量大小（batch size）为 64。 - 训练收敛与早停准则：在包含长度 $[0, M]$ 的分布内数据集上训练，当连续三次评估的分布内准确率均达到 100% 时触发早停（Early Stopping），或直至跑满最大上限 60,000 步。对于 $k \leq 32$ 采用基准窗口 $M=50$；对于 $k=64$ 扩展至 $M=256$ 以确保阈值在训练期可达。 - 监督机制：输入序列采用标准化格式 $\langle\textsc{bos}\rangle, w, \langle\textsc{sep}\rangle, y, \langle\textsc{eos}\rangle$，交叉熵损失函数严格仅在回答标记（answer token）位置进行梯度计算与回传。

实验关键数据¶

主实验¶

实验旨在检验具有对数规约大小的任务与多项式规约大小的任务在外推测试集上的长度泛化表现差异。测试设置划分为分布内区间 $t_0 = \mathcal{C}[0, M]$，外推第一区间 $t_1 = \mathcal{C}[M+1, 2M]$ 以及外推第二区间 $t_2 = \mathcal{C}[2M+1, 3M]$。

任务	目标谓词公式复杂度	$t_0$ 表现 (In-dist)	$t_1$ 表现 (OOD-1)	$t_2$ 表现 (OOD-2)	理论预测与泛化表现
$\text{COUNT}_{k}$ ($k=2 \dots 64$)	$\mathcal{O}(\log k)$ (C-RASP+)	100.0%	$\geq 96.5\%$	$\geq 93.8\%$ (最低点 $k=32$)	极小样本即可实现稳健长度泛化
$\text{MAJ}_{k}$ ($k=2 \dots 64$)	$\mathcal{O}(\log k)$ (C-RASP1)	100.0%	$\geq 97.2\%$	$\geq 96.0\%$ (最高达 99.8% @ $k=64$)	对数级规范完美外推至超长序列
$\text{PARITY}_{k}$ ($k=2$)	$\mathcal{O}(k)$ (C-RASP+)	100.0%	99.2%	98.5%	极小阈值下公式规模极小，拟合优异
$\text{PARITY}_{k}$ ($k=4$)	$\mathcal{O}(k)$ (C-RASP+)	100.0%	95.4%	93.1%	样本需求温和增长，外推开始轻微衰退
$\text{PARITY}_{k}$ ($k=8$)	$\mathcal{O}(k)$ (C-RASP+)	100.0%	86.8%	84.2%	样本空间快速膨胀，外推显著掉点
$\text{PARITY}_{k}$ ($k=16$)	$\mathcal{O}(k)$ (C-RASP+)	98.7%	84.0%	82.5%	分布内拟合出现波动，外推阻滞
$\text{PARITY}_{k}$ ($k=32$)	$\mathcal{O}(k)$ (C-RASP+)	93.4%	86.1%	85.6%	分布内退化至 93.4%，进入样本饥渴区
$\text{PARITY}_{k}$ ($k=64$)	$\mathcal{O}(k)$ (C-RASP+)	91.2%	77.6%	74.2%	外推严重衰减，样本复杂度过大导致失效

消融实验¶

针对理论预测的核心驱动力——公式表达复杂度 $|\phi|$ 与语言识别难度之间的因果关联，论文在 Appendix D 中给出下界理论消融，并在控制变量下对比了不同规模 $k$ 下 $\text{PARITY}_k$ 与纯计数任务的渐近难度。

评估维度 / 任务设定	逻辑表征长度下界	样本复杂度需求界	$k=64$ 时的 $t_2$ 实测准确率	实验结论说明
$\text{COUNT}_{64}$ 计数阈值	$\Theta(\log k)$ 紧凑界	多项式级 $\mathcal{O}(\mathsf{poly}(k))$	98.4%	阈值二进制编码使得状态表示极紧凑
$\text{MAJ}_{64}$ 双向计数对比	$\Theta(\log k)$ 紧凑界	多项式级 $\mathcal{O}(\mathsf{poly}(k))$	99.8%	两个一阶计数变量比较，无状态爆炸
$\text{PARITY}_{64}$ 奇偶限制	$\Omega(k)$ 严格线性下界	指数级 $\mathcal{O}(2^{\Omega(k)})$	74.2%	无法对数紧凑化，必须显式析取各偶数态
理论边界对比：前人界 (Yang et al., 2026a)	未区分幂词拓扑	双重指数级 $2^{2^{\mathcal{O}(\\|\phi\\|)}}$	-	理论界极度松弛，完全无法解释实验趋势
理论边界对比：本文压缩界 (Ours)	多项式幂词压缩	单重指数级 $2^{\mathcal{O}(\\|\phi\\|)}$	74.2% 对齐	证明样本需求随 $k$ 指数暴增，完美预测失效点

关键发现¶

对数表达任务 vs 线性表达任务的断崖式分流：只要任务能够用二进制编码在对数符号级 $\mathcal{O}(\log k)$ 内书写（如 $\text{COUNT}_k$ 与 $\text{MAJ}_k$），所需的样本量随 $k$ 呈多项式增长，Transformer 展现出惊人的长度外推稳健性（即便序列达到训练长度的 3 倍，准确率仍稳定在 96%~99% 以上）。
奇偶性限制任务的样本饥渴困境：证明了 $\text{PARITY}_k$ 无论在 C-RASP+ 还是 C-RASP1 中，其逻辑公式大小的严格下界均为 $\Omega(k)$（无法压缩为 $\log k$）。结合本文推导的指数样本复杂度界，其所需样本量随 $k$ 呈指数暴涨，直接导致有限训练步数下外推准确率跌落至 74.2%。这表明此前的实验“反例”并非由于 C-RASP 假说崩溃，而是由于未达到所必需的理论样本阈值。

亮点与洞察¶

跨学科工具迁移的范式创新：首次将计算群论与字词压缩领域的“幂词（power words）”与整型向量加法系统理论桥接至深度学习长度泛化领域，利用代数丢番图稀疏解巧妙绕过了传统自动机字符串组合爆炸问题。
平息关于 C-RASP 假说的理论争议：此前实验观察到 $\text{PARITY}_k$ 无法外推，被广泛当作质疑“可定义即能泛化”猜想的有力反例；本文通过细粒度样本复杂度分析证明该反例本质是样本规模指数壁垒的表象，维护了逻辑可表达性理论的完整性。
可复用的分析框架：将神经网络泛化分析转化为“逻辑规约大小 $\to$ 计数自动机 $\to$ 线性系统稀疏解 $\to$ 压缩样本界”的标准分析范式，具备向更高阶时态逻辑扩展的方法论价值。

局限与展望¶

适用逻辑片段的局限性：作者承认当前成果主要限定在 C-RASP+（无否定时序前缀的有限精度逻辑）与 C-RASP1（一阶计数深度）两个子集，尚未能涵盖具备多层计数嵌套与双向时序操作的完整 C-RASP 语言。
非 C-RASP+ 任务的外推特例未覆盖：自然语言与程序语言中存在部分超出上述片段却同样具备良好泛化能力的任务（例如正则语言 $(ab)^*$）；如何界定一个既包含这些模式又具备可计算样本界的更宏观逻辑子集仍是未解难题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将幂词与整数锥 Carathéodory 理论引入 Transformer 泛化理论，构思极具原创性。
实验充分度: ⭐⭐⭐⭐☆ 理论证明极其严密，配套受控实验精准验证了理论预测的转折点。
写作质量: ⭐⭐⭐⭐⭐ 逻辑结构层层递进，从高阶动机、形式化建模到代数证明推导一气呵成。
价值: ⭐⭐⭐⭐⭐ 彻底解决了关于 Transformer 长度泛化假说的关键悬案，确立了样本复杂度细粒度分析新标杆。

任务	目标谓词公式复杂度	\(t_0\) 表现 (In-dist)	\(t_1\) 表现 (OOD-1)	\(t_2\) 表现 (OOD-2)	理论预测与泛化表现
\(\text{COUNT}_{k}\) (\(k=2 \dots 64\))	\(\mathcal{O}(\log k)\) (C-RASP+)	100.0%	\(\geq 96.5\%\)	\(\geq 93.8\%\) (最低点 \(k=32\))	极小样本即可实现稳健长度泛化
\(\text{MAJ}_{k}\) (\(k=2 \dots 64\))	\(\mathcal{O}(\log k)\) (C-RASP1)	100.0%	\(\geq 97.2\%\)	\(\geq 96.0\%\) (最高达 99.8% @ \(k=64\))	对数级规范完美外推至超长序列
\(\text{PARITY}_{k}\) (\(k=2\))	\(\mathcal{O}(k)\) (C-RASP+)	100.0%	99.2%	98.5%	极小阈值下公式规模极小，拟合优异
\(\text{PARITY}_{k}\) (\(k=4\))	\(\mathcal{O}(k)\) (C-RASP+)	100.0%	95.4%	93.1%	样本需求温和增长，外推开始轻微衰退
\(\text{PARITY}_{k}\) (\(k=8\))	\(\mathcal{O}(k)\) (C-RASP+)	100.0%	86.8%	84.2%	样本空间快速膨胀，外推显著掉点
\(\text{PARITY}_{k}\) (\(k=16\))	\(\mathcal{O}(k)\) (C-RASP+)	98.7%	84.0%	82.5%	分布内拟合出现波动，外推阻滞
\(\text{PARITY}_{k}\) (\(k=32\))	\(\mathcal{O}(k)\) (C-RASP+)	93.4%	86.1%	85.6%	分布内退化至 93.4%，进入样本饥渴区
\(\text{PARITY}_{k}\) (\(k=64\))	\(\mathcal{O}(k)\) (C-RASP+)	91.2%	77.6%	74.2%	外推严重衰减，样本复杂度过大导致失效

评估维度 / 任务设定	逻辑表征长度下界	样本复杂度需求界	\(k=64\) 时的 \(t_2\) 实测准确率	实验结论说明
\(\text{COUNT}_{64}\) 计数阈值	\(\Theta(\log k)\) 紧凑界	多项式级 \(\mathcal{O}(\mathsf{poly}(k))\)	98.4%	阈值二进制编码使得状态表示极紧凑
\(\text{MAJ}_{64}\) 双向计数对比	\(\Theta(\log k)\) 紧凑界	多项式级 \(\mathcal{O}(\mathsf{poly}(k))\)	99.8%	两个一阶计数变量比较，无状态爆炸
\(\text{PARITY}_{64}\) 奇偶限制	\(\Omega(k)\) 严格线性下界	指数级 \(\mathcal{O}(2^{\Omega(k)})\)	74.2%	无法对数紧凑化，必须显式析取各偶数态
理论边界对比：前人界 (Yang et al., 2026a)	未区分幂词拓扑	双重指数级 \(2^{2^{\mathcal{O}(\\|\phi\\|)}}\)	-	理论界极度松弛，完全无法解释实验趋势
理论边界对比：本文压缩界 (Ours)	多项式幂词压缩	单重指数级 \(2^{\mathcal{O}(\\|\phi\\|)}\)	74.2% 对齐	证明样本需求随 \(k\) 指数暴增，完美预测失效点