Transformer可表达高度非线性的计数问题，突破了传统线性限制。
The Counting Power of Transformers
- 构建形式化框架，揭示Transformer在计数上的表达能力边界。
- 证明Transformer能捕捉任意多元多项式组合的半代数计数属性。
- 首次发现无位置编码的极简Transformer也具不可判定性，适合理论研究者。
计数性质（如判断输入文本中某些词元是否比其他词元出现更多）在研究Transformer表达能力中具有重要意义。本文提出一个形式化框架，用于分析Transformer的计数能力。我们指出，现有所有结果仅表明Transformer对（半）线性计数性质具有表达能力，即可通过布尔组合的线性不等式表达。我们的核心结论是：Transformer可表达高度非线性的计数性质。具体而言，我们证明其可捕捉所有半代数计数性质，即可表示为任意多元多项式（任意次数）的布尔组合。这广义化了此前仅能捕捉线性计数性质的C-RASP softmax Transformer。为进一步补充，我们给出一个自然的（softmax）Transformer子类，恰好刻画半代数计数性质。通过与希尔伯特第十问题的关联，该表达能力还导出了一个关于极其简单Transformer模型的新不可判定性结果——令人惊讶的是，该模型既无位置编码（NoPE-transformer），也无掩码机制。我们还通过实验验证了此类计数属性的可训练性。
原文摘要 · Abstract (English)
Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of transformers. In this paper, we provide a formal framework for investigating the counting power of transformers. We argue that all existing results demonstrate transformers' expressivity only for (semi-)linear counting properties, i.e., which are expressible as a boolean combination of linear inequalities. Our main result is that transformers can express counting properties that are highly nonlinear. More precisely, we prove that transformers can capture all semialgebraic counting properties, i.e., expressible as a boolean combination of arbitrary multivariate polynomials (of any degree). Among others, these generalize the counting properties that can be captured by C-RASP softmax transformers, which capture only linear counting properties. To complement this result, we exhibit a natural subclass of (softmax) transformers that completely characterizes semialgebraic counting properties. Through connections with the Hilbert's tenth problem, this expressivity of transformers also yields a new undecidability result for analyzing an extremely simple transformer model -- surprisingly with neither positional encodings (i.e. NoPE-transformers) nor masking. We also experimentally validate trainability of such counting properties.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。