🤖 machine learning

Parity, Sensitivity, and Transformers

本文通过证明单层 Transformer 因敏感性约束而无法计算奇偶性任务，从而解决了该任务能否由单层 Transformer 计算的开放性问题，同时提出了一种实用的四层 Transformer 构造，该构造在求解奇偶性任务时无需依赖先前所必需的诸如长度相关位置编码或硬最大函数等不切实际的假设。

原作者： Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图教一个非常聪明但略显僵硬的机器人玩一个名为“奇偶游戏”的简单游戏。

在这个游戏中，机器人会看到一串长长的灯光，其中一些是红色的（0），一些是蓝色的（1）。机器人唯一的工作就是回答一个问题：“蓝色灯光的总数是偶数还是奇数？”

如果有 3 盏蓝色灯光，答案就是“奇数”。如果有 4 盏，答案就是“偶数”。

这对我们来说听起来很简单，但对于一种被称为“Transformer"（驱动许多现代聊天机器人和翻译器的架构）的特定人工智能架构而言，这个游戏一直是个谜。科学家们一直在争论：这个机器人需要多少层“思考层”才能解决这个游戏？

以下是本文发现的简单解释：

1. “单层”机器人太笨了

作者首先问道：仅凭一层思考的 Transformer 能解决这个问题吗？

他们证明答案是不能。

类比：想象机器人是一个站在房间里的人，房间里挤满了举着红色或蓝色卡片的人。这个人只能同时看向所有人，并快速扫视一下“平均值”。

“奇偶”游戏极其敏感。如果你将一个人的卡片从红色改为蓝色，答案就会完全翻转（从偶数变为奇数）。
作者表明，单层机器人太“平滑”且太“懒惰”。它无法对单一变化做出足够敏锐的反应。这就像试图通过只听平均风速来检测飓风中的单根针掉落声。机器人的“敏感度”增长得太慢，无法捕捉到解决游戏所需的微小而关键的变化。

结论：你至少需要两层思考来解决这个问题。

2. “旧方案”使用了太多“作弊”手段

在这篇论文之前，其他科学家已经想出了如何构建一个能够解决该游戏的 Transformer，但他们不得不使用一些“作弊”手段或不切实际的设置：

“魔法尺子”：他们给机器人一把尺子，让它在开始阅读之前就知道字符串的确切长度（例如：“这个字符串正好是 1,000 个字符长”）。真实的机器人通常直到读完句子才知道其长度。
“完美开关”：他们使用了一种“硬开关”，可以瞬间做出二元决策，而不是真实机器人使用的“柔和、模糊”的概率开关。
“零误差”过滤器：他们移除了一个安全过滤器（称为 LayerNorm），该过滤器通常用于防止机器人的数值爆炸到无穷大。

这些方案在纸面上有效，但在现实世界中行不通，因为它们依赖于实际 AI 训练中并不存在的假设。

3. 新的、现实世界的解决方案

本文的作者构建了一个新机器人，它在没有任何上述作弊手段的情况下解决了奇偶游戏。

没有魔法尺子：它使用“与长度无关”的位置编码。它不需要预先知道字符串的总长度；它只需观察事物彼此之间的相对位置。
柔和开关：它使用标准的“柔和”注意力机制（即真实聊天机器人中使用的那种）。
安全过滤器：它无需移除安全过滤器即可工作。
代价：为了在不作弊的情况下做到这一点，机器人需要四层思考，而不是两层。

类比：
把旧的“作弊”解决方案想象成一位魔术师，他通过偷看藏在桌子底下的答案键来解决谜题。
新的解决方案则像一位侦探大师，他通过仔细检查每一个线索、交叉比对它们并多做一点工作（四层而不是两层）来解决同样的谜题。它稍微慢一些，需要更多的“脑力”（深度），但它能在真实的法庭上奏效，而不仅仅是在魔术舞台上。

突破总结

下界：仅含一层的 Transformer 在数学上无法解决奇偶游戏。这不是训练问题；机器人本质上缺乏完成此任务的架构。
上界：你可以用 Transformer 解决这个游戏，但要以一种现实的方式（不依赖与长度相关的技巧作弊，也不移除安全过滤器），你需要四层。

这篇论文本质上在沙地上划出了一条清晰的界线：“如果你想要一个现实的人工智能来计数奇数和偶数，请给它至少四层的深度。任何少于四层的架构，在数学上都是不可能的。”

基于所提供的文本，以下是论文《奇偶性、敏感性与 Transformer》的详细技术总结。

问题陈述

本文探讨了 Transformer 架构表达能力的根本问题，特别是关于**奇偶性（PARITY）**任务。奇偶性是一个布尔函数，当二进制输入序列中 1 的个数为奇数时输出 1，否则输出 0。它是理论计算机科学中的一个典型问题，以其高敏感性（翻转任意单个比特都会改变输出）而闻名。

虽然先前的研究已经证实，具有硬注意力机制（特别是唯一硬注意力或 UHAT）的 Transformer 无法在常数深度内计算奇偶性，但具有软（softmax）注意力机制的 Transformer 的能力仍不太明确。现有的能够计算奇偶性的软注意力 Transformer 构造依赖于“不切实际”的假设，例如：

依赖于总输入长度（ $n$ ）的位置编码。
硬注意力机制。
带有正则化参数 $\epsilon = 0$ 的层归一化。
与因果掩码不兼容。

此外，单层 Transformer 是否能够计算奇偶性仍是一个未解决的问题。

方法论

作者采用两种不同的方法论途径来解决 Transformer 对奇偶性表达能力的下界和上界（构造）问题。

1. 基于平均敏感性的下界
为了证明单层 Transformer 无法计算奇偶性，作者利用了平均敏感性的概念。

定义：函数 $f$ 的平均敏感性是指翻转输入比特位置从而改变函数输出的期望比特位置数量。对于奇偶性，该值恰好为 $n$ （线性增长）。
逻辑：作者将单层 Transformer 的计算建模为实数一阶逻辑 $(\mathbb{R}, <, +, \cdot)$ 中可表达的函数。通过应用塔斯基 - 塞登伯格定理（量词消去），他们证明了任何由单层 Transformer 计算的函数都可以表示为固定数量的低次多项式阈值函数（PTF）的布尔组合。
界定：引用 Kane 的结果，作者确立了低次 PTF 的平均敏感性以 $O(\sqrt{n} \cdot (\log n)^{O(1)})$ 的速率增长。由于奇偶性的平均敏感性呈线性增长（ $n$ ），单层 Transformer 无法计算它。

2. 基于新构造的上界
为了证明奇偶性可以由 Transformer 在不依赖不切实际假设的情况下计算，作者提出了一种新的四层构造。

机制：该构造使用softmax 注意力和与长度无关、多项式有界的位置编码。它避免了层归一化，并在完全注意力和因果掩码下均有效。
算法策略：
1. 第 1 层：计算输入比特的加权和，以推导出与 1 的计数（ $\Sigma$ ）相关的值 $\gamma$ 。
2. 第 2 层：利用位置编码（ $i \mapsto (\ln i, i^{10})$ ）和值 $\gamma$ 计算加权平均值 $\Gamma$ 。该值近似于一个编码 $\Sigma$ 信息的函数 $f(\rho)$ 。
3. 第 3 层：构建注意力权重 $L_{i,n}$ ，使其高度集中在位置 $i = \Sigma$ 。这是通过使用第 2 层计算的值 $\Gamma$ 来近似一个在 $i = \Sigma$ 处达到峰值的特定二次型来实现的。作者证明，对于正确的位置，其注意力权重显著大于（超出 $\Omega(n^6)$ 的幅度）任何其他位置。
4. 第 4 层：利用集中的注意力权重计算 $(-1)^i$ 的加权和。结果是一个接近 $(-1)^\Sigma$ 的值 $z$ ，使得最终层能够区分偶数和奇数奇偶性。
处理大输入：为了处理 1 的个数（ $\Sigma$ ）较大的情况，该构造将输入划分为 $M$ 个子序列（其中 $M$ 为偶数常数），并行计算每个子序列的奇偶性，并聚合结果。

主要贡献与结果

解决单层开放问题：本文明确回答了单层 Transformer 是否能计算奇偶性这一开放问题。结果为否定。作者证明，任何由单层 Transformer 计算的函数的平均敏感性被 $O(\sqrt{n} \cdot (\log n)^{O(1)})$ 所界定，这不足以应对奇偶性的线性敏感性。
改进的奇偶性构造：作者提出了一种新的四层 Transformer 构造来计算奇偶性。该构造通过去除若干限制性假设，改进了先前的工作（例如 Chiang 和 Cholak, 2022; Yang 等人，2025）：
- 它使用软注意力（softmax）而非硬注意力。
- 它采用与长度无关的位置编码。
- 它不需要层归一化（或者具体而言，不依赖 $\epsilon=0$ ）。
- 它与因果掩码兼容。
- 位置编码是多项式有界的，使其在实际输入长度下可行。
深度要求：本文确立了虽然一层是不够的，但在现实的设计约束下，四层是足够的。这细化了对计算高敏感性函数所需深度的理解。

意义

本文通过精确刻画 Transformer 架构在奇偶性任务上的深度要求，推进了对 Transformer 架构的理论理解。通过将 Transformer 表达能力与布尔函数的平均敏感性联系起来，作者提供了一个严格的下界，排除了单层模型的可能性。同时，通过提供一种遵循标准架构实践（软注意力、因果掩码、有界编码）的四层构造，本文证明了奇偶性可以由 Transformer 计算，而无需诉诸理论上的虚构。

作者指出，这些结果有助于解释为什么 Transformer 在训练过程中可能难以泛化到像奇偶性这样的任务：该函数需要特定的深度和架构配置，如果模型过浅或受限，可能无法通过标准的梯度下降方法轻易学习。这项工作补充了关于硬注意力模型表达能力的现有文献，并为软注意力 Transformer 的能力提供了更现实的基准。