新论文证明单层注意力模型：k个头能算k位奇偶校验，无条件无法算k+1位
arXiv预印本给出单层注意力头复杂度的精确分层，并证明嵌入维度和数值精度在无限时也无法替代注意力头。
AI解读：这篇论文回答了注意力机制的一个基础问题：单层自注意力到底能算什么？作者给出一个干净的分层结论——k个注意力头能计算k位奇偶校验，但算不了k+1位，而且这个限制在嵌入维度和数值精度无限大时依然成立，说明加宽模型或提高精度都不能替代增加注意力头。证明的关键是一个交替和障碍，他们用同一方法还给出了多跳归纳头任务的下界。对关注Transformer可表达性的研究者，这提供了精确的容量边界，但要注意这是理论结果，尚未考虑训练动态和实际优化，不直接预测模型在真实任务上的表现。
东北大学和加州大学圣塔克鲁兹分校的研究者Rajmohan Rajaraman、Ravi Sundaram、Amanuel Tesfaye在arXiv预印本中提出“注意力头复杂度”概念，证明在单层仅有注意力的模型中，k个头可计算k位奇偶校验函数，但无法计算 (k+1) 位版本，该下界在嵌入维度和数值精度不受限时依然成立。
下界的对抗性证明方法
论文证明基于交替和障碍：清除softmax分母后，得到的决策多项式中每个单项式至少省略k+1个输入位中的一个，导致其与奇偶校验相关性消失。同一方法也推广到多跳归纳头任务的下界。
- 论文收到日期 2026 年 9 月 3 日，共 32 页 0 图，发表于计算复杂性子领域。
无需无限资源的紧凑性定理
研究者提出紧凑性定理：任何可计算的函数都能在嵌入维度和数值精度上界限制下实现，该上界仅取决于任务离散数据（头数、字母表大小、长度）。这意味着无限精度或维度不能替代头的数量，为下界的无条件性提供补充。
- 该定理说明，即使理论上允许无界资源，实际计算也不依赖它们，突显头数的核心作用。
通用二元函数的头数上界与下界
论文给出通用二元函数的结果：2^n个头足以计算任何n位二元函数，每个头对应其多线性展开中的一个单项式。同时，通过计数论证，几乎所有此类函数至少需要 Ω(2^n/n^2) 个头，该下界与上界在多项式因子内匹配，适用于维度与精度无界情况。
- 这些结果联合刻画了该模型中布尔计算的头需求，上界与下界接近匹配。