arXiv:2605.30523cs.LGcs.AI2026-05被引 3

揭示填充Transformer表达能力的关键因素,发现精度和深度决定上限。

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

  • 通过填充输入符号构建并行计算空间,分析不同注意力机制的表达能力。
  • 常数精度下等价于L-一致AC⁰,渐进精度下可达L-一致TC⁰,与宽度无关。
  • 循环结构实现类似电路的序列处理,适合研究模型复杂度与逻辑计算关系的人。

近期工作通过布尔电路关联揭示了Transformer的计算能力边界,但现有结果缺乏精确刻画且对建模假设敏感。填充Transformer——在输入末尾添加如'...'等填充符号——因其提供多项式空间用于自适应并行计算,成为建立与电路类等价关系的有效工具。然而,仅有限的填充Transformer理想化形式被研究,其等价性在注意力类型、模型宽度和一致性方面的鲁棒性尚不明确。我们发现,在合理假设下,填充Transformer对这些变化具有出乎意料的鲁棒性,且数值精度和模型深度是影响表达能力的主要因素。具体而言,证明了多项式填充的常数精度L-一致Transformer等价于L-一致AC⁰,而渐进精度版本则达到L-一致TC⁰,且不受宽度影响。此外,循环结构可实现类电路的序列处理:logᵈN次循环的常数精度模型达到FO-一致ACᵈ,渐进精度版本则达FO-一致TCᵈ。有趣的是,宽度或精度超过对数级别不会提升表达能力,所有结论对softmax和平均硬注意力均成立。

原文摘要 · Abstract (English)

Recent work describes what transformers can and cannot compute through connections to boolean circuits, but existing results lack exact characterizations and are sensitive to modeling choices. Padded transformers -- to whose input filler symbols such as ``...'' are appended -- emerge as a useful gadget for establishing equivalences to circuit classes by providing polynomial space for adaptive parallel computation. However, only a limited set of padded transformer idealizations has been studied, leaving open how robustly these equivalences hold under changes to attention type, model width, and uniformity. We find that, under practical assumptions, padded transformers are surprisingly robust to all of these, and identify numeric precision and model depth as the main factors affecting expressivity. Concretely, we prove that polynomially padded $\text{L-uniform}$ constant-precision transformers are equivalent to $\text{L-uniform AC}^0$, while growing-precision ones achieve $\text{L-uniform TC}^0$ regardless of width. Furthermore, looping enables sequential processing analogous to circuits: $\log^d N$-looped constant-precision transformers reach $\text{FO-uniform AC}^d$, and growing-precision ones reach $\text{FO-uniform TC}^d$. Interestingly, growing width or precision beyond logarithmic does not increase expressivity, and all our results hold for both softmax and average hard attention transformers.

Transformer表达能力电路理论注意力

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。