Quantitative Bounds for Length Generalization in Transformers

• ArXiv URL: http://arxiv.org/abs/2510.27015v1

• 作者: Zachary Izzo; Eshaan Nichani; Jason D. Lee

• 发布机构: NEC Labs America; Princeton University; University of California, Berkeley

---

TL;DR

本文首次为Transformer的长度泛化（length generalization）能力提供了定量的边界，通过引入一种“模拟论证”方法，证明了当训练序列足够长，能够“模拟”更长序列上的内部行为时，模型便能实现长度泛化，并给出了所需训练长度与模型参数、任务复杂度之间关系的具体数学刻画。

关键定义

本文沿用了已有研究中的核心概念，并在此基础上进行了扩展和分析，关键定义如下：

1. 极限Transformer (Limit Transformer)：这是一个理论上的Transformer模型，拥有无限的上下文长度和泛化的位置编码。它作为分析任意长度序列泛化能力的理想化对象，是本文理论推导的基础。
2. 有限精度注意力 (Finite-Precision Attention)：该假设认为Transformer内部所有计算（特别是Softmax）都以有限的 \(p\) 位精度进行。一个关键推论是，当序列长度 \(N\) 超过某个由“logit边距”决定的阈值时，Softmax注意力机制会退化为一种“硬性最大化 (hardmax)”机制，即注意力权重只会分配给得分最高的 token。
3. logit边距 (logit margin, $\gamma(f)$)：在有限精度设定下，本文定义了 \(logit margin\)，它表示对于任何可能的输入，注意力得分中最大值与次大值之间的最小非零差值。这个值决定了Softmax退化为hardmax所需的序列长度阈值。
4. 无限精度注意力 (Infinite-Precision Attention)：作为对比，本文也分析了无限精度下的情况。为了避免长距离信息的衰减，本文提出了一种新颖的注意力计算方式：仅将位置相关的注意力得分（即\(τ\)-后缀内的部分）乘以一个对数因子 \(log(i)\)，从而能够统一分析局部信息和全局信息在注意力计算中的不同相对重要性。

相关工作

当前，关于Transformer长度泛化（LG）能力的研究主要分为经验和理论两个方面。经验研究发现，Transformer在不同任务上的LG表现差异巨大，从简单的形式语言任务到复杂的推理任务，其成功与否依赖于任务本身、位置编码方案、甚至是“草稿纸”等提示技巧。

理论方面，最近的研究（如RASP-L猜想）试图从任务的可表达性来解释LG现象。特别是，Huang等人（2025）证明了，对于一类可用“极限Transformer”表达的任务，LG在某个有限的训练长度上是可达的。然而，这些工作本质上是“渐进式”的，它们只证明了存在这样一个长度阈值，但并未回答这个阈值具体是多少，即为了实现长度泛化，训练序列到底需要多长？

本文旨在填补这一空白，直接解决上述问题：为极限Transformer实现长度泛化所需的最小训练序列长度提供定量的数学界定（quantitative bounds）。

本文方法

本文的核心创新在于提出并运用了一种“模拟论证” (simulation argument) 的证明框架，来推导长度泛化所需的定量边界。该方法的基本思想是：如果对于任意一个长序列 \(x\)，我们都能构建一个短序列 \(z\) (长度不超过 \(N\))，使得模型在 \(x\) 和 \(z\) 上的行为（即输出）近似相等（$f(x) \approx f(z)$ ），那么，只要两个模型 \(f\) 和 \(g\) 在所有长度不超过\(N\)的序列上表现一致，它们在任意更长的序列 \(x\) 上也必然表现一致 ($f(x) \approx f(z) \approx g(z) \approx g(x)$)。

关键在于如何构建这个短的“模拟”序列 \(z\)。本文证明，只要 \(z\) 能够近似保持计算模型前向传播所需的“充分统计量”，模拟就能成功。基于这一核心思想，本文在两种不同的设定下进行了分析。

有限精度下的单层Transformer分析

在该设定下，模型计算具有有限精度，导致注意力机制在长序列上表现为hardmax行为。

• 核心机制：当序列长度 $$

  x

  \(足够长（例如，\)

  x

  ≥ 2^(p/γ(f))\(，其中\)p\(是精度位数，\)γ(f)$$ 是logit边距）时，注意力将完全集中在具有最大attention logit的token上。此时，模型的输出主要依赖于这些被“选中”的token的经验频率（即各类token在被选中的集合里出现的比例）。

• 模拟方法：构造一个短序列 \(z\)，使其能够近似复现长序列 \(x\) 中被hardmax机制选中的token的经验频率分布。
• 主要结论 (定理 4.1 & 4.2)：本文证明，对于单层极限Transformer，要实现长度泛化，所需的最小训练长度 \(N\) 与以下因素相关：

  • 最差情况误差 ($l_∞$ error): \(N\) 的上界与模型参数的范数 \(L\)、位置编码周期 \(Δ\)、词汇表大小 $$

    Σ

    \(、局部性参数\)τ\(以及目标误差的倒数\)ε⁻¹$$ 呈多项式关系。

  • 平均情况误差 (Average error): 在一定的序列分布假设下（如从狄利克雷分布中采样），同样可以得到关于 \(N\) 的定量边界，其与 \(ε⁻¹\) 的关系更复杂。

这些结果首次定量地揭示了，要泛化到更长序列，所需的训练数据长度如何随着模型和任务的复杂度（由上述参数体现）而增加。

无限精度下的双层Transformer分析

为了更贴近多层Transformer中高层输入的连续特性，本文还分析了无限精度下的情况。

• 核心机制：本文对标准的无限精度注意力进行了修正，通过对局部上下文（\(τ\)-后缀）的注意力得分进行对数缩放 (\(log i\))，使得模型可以灵活地权衡全局信息（整个序列前缀的token统计）和局部信息（结尾附近的几个token）。此时，模型的输出可以被看作是一个依赖于 “\((τ-后缀, 全局token直方图)\)”这一对联合分布 的连续函数。
• 模拟方法：构造一个短序列 \(z\)，使得在 \(z\) 上 “\((τ-后缀, 全局token直方图)\)” 的经验联合分布能够近似长序列 \(x\) 上的对应分布。

• 主要结论 (定理 5.2)：对于双层无限精度极限Transformer，所需的最小训练长度 \(N\) 由新定义的复杂度度量 \(C(f)\) 和 位置边距 \(γ(f)\) 共同决定。其上界形式为：

  \[N = \tilde{O}\left( \max\left\{ C(f)^2, \frac{\log(1/\varepsilon)}{\gamma(f)} \right\} \cdot \varepsilon^{-2} \right)\]

  其中 \(C(f)\) 是一个与模型各层权重范数、\(τ\)、$$

  Σ

  \(等呈指数和多项式关系的复杂项。这再次表明，模型越复杂（\)C(f)\(越大）或位置编码的区分度越小（\)γ(f)$$ 越小），实现泛化所需的训练数据就越多。

实验结论

尽管论文正文未详细展示实验部分，但作者在文中明确指出，他们通过经验性实验验证了理论分析得出的见解。

• 理论验证：实验结果与理论发现相符，证实了从“模拟论证”中推导出的关于所需训练数据长度与模型/任务参数之间关系的定性估计是正确的。

• 实际意义：实验还支持了一个观点，即在实际中，注意力机制退化为hardmax所需的序列长度可能远小于理论上的最坏情况界限（\(2^(p/γ)\)），这意味着理论界限中的多项式部分（$$poly(τ, Δ, L, ε⁻¹,

  Σ

  )$$）可能在实践中起主导作用。

• 最终结论：本文的理论结果成功地将“更复杂的任务需要更丰富的训练数据才能实现长度泛化”这一直觉形式化、定量化，为理解Transformer的外推机制提供了更深刻的理论洞察，并对如何为大型语言模型扩展训练上下文长度提供了实践指导。