揭示固定精度Transformer的语言表达能力边界
Characterizing the Expressivity of Fixed-Precision Transformer Language Models
- 用理想化模型分析Transformer的表达能力
- 理论证明其等价于带过去算子的线性时序逻辑
- 实验证明表达力不足时泛化失败
基于Transformer的语言模型虽在实践中表现优异，但其理论表达能力仍不清晰。本文研究了一类理想化的固定精度Transformer，其具有严格的未来掩码、软注意力且无位置编码。我们证明这类模型的表达能力恰好等同于仅包含一个时间算子——过去算子的线性时序逻辑片段。该结果与形式语言理论、自动机理论及代数中的经典分类相联系，建立了统一的理论框架。此外，实验表明：当训练语言在其理论表达能力范围内时，模型能可靠跨序列长度泛化；而超出此范围时，泛化则持续失败。
原文摘要 · Abstract (English)
Transformer-based language models (LMs) have achieved widespread empirical success, but their theoretical expressive power remains only partially understood. In this work, we analyze a restricted idealization of fixed-precision transformers with strict future masking, soft attention, and no positional encodings. We establish that this class of models is exactly as expressive as a specific fragment of linear temporal logic that contains only a single temporal operator: the past operator. We further connect this fragment to established classes in formal language theory, automata theory, and algebra, yielding a unified framework for understanding transformer expressivity under this idealization. Finally, we present empirical results that align closely with our theory: transformers trained on languages within their characterized expressive capacity generalize reliably across sequence lengths, while they consistently fail to generalize on languages beyond it.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。