Transformer模型比传统逻辑和网络更简洁，能用更小规模描述复杂语言。
Transformers are Inherently Succinct
- 用压缩能力衡量Transformer表达力，证明其在固定精度下极高效
- 多项式大小的Transformer可等价替代指数级的LTL公式或递归网络
- 揭示验证问题本质困难，适合关注模型效率与形式验证的研究者
我们以简洁性作为衡量Transformer表达能力的指标。简洁性——即一种形式系统相对于其他系统描述语言的紧凑程度——是逻辑与自动机理论中的经典概念。我们证明，固定精度的Transformer具有惊人的简洁性：其可比线性时序逻辑（LTL）和循环神经网络（RNN）指数级更简洁，且比有限自动机双指数级更简洁。换言之，存在一类语言可用多项式大小的Transformer描述，而其最小等价的LTL公式或RNN需指数级规模，最小等价自动机则需双指数级规模。我们还建立了匹配的上界，表明任何固定精度Transformer可转换为至多指数级膨胀的LTL公式（优于先前的双指数级转换）。由此推得，Transformer的基本验证问题（如空性、等价性）本质上不可解：具体为EXPSPACE完全。
原文摘要 · Abstract (English)
We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a classical notion in logic and automata theory. We prove that fixed-precision transformers are remarkably succinct: they can be exponentially more succinct than both linear temporal logic (LTL) and recurrent neural networks, and, by extension, state-space models, and doubly exponentially more succinct than finite automata. In other words, there exist families of languages describable by polynomial-size transformers whose smallest equivalent LTL formula or recurrent neural network is exponentially large, and whose smallest equivalent automaton is doubly exponentially large. We also establish matching upper bounds, showing that any fixed-precision transformer can be converted to an LTL formula with at most an exponential blow-up -- improving a prior doubly exponential translation. As a consequence of this succinctness, we show that basic verification problems for transformers, such as emptiness and equivalence, are provably intractable: specifically, EXPSPACE-complete.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。