Transformer 本质上简洁 (2025)

Source: Hacker News

摘要

我们提出将简洁性作为衡量 transformer 在描述概念时表达能力的指标。为此，我们证明 transformer 具有高度表达力，能够比有限自动机和线性时序逻辑（LTL）公式等标准形式语言表示方式更为简洁地表示形式语言。作为这种表达力的副产品，我们展示了验证 transformer 的属性在理论上是不可解的（即 EXPSPACE‑complete）。

主题

• 正式语言与自动机理论 (cs.FL)
• 机器学习 (cs.LG)
• 计算机科学中的逻辑 (cs.LO)

引用

• arXiv: arXiv:2510.19315 (cs.FL)
• 版本: arXiv:2510.19315v2 (cs.FL)
• DOI: 10.48550/arXiv.2510.19315 (arXiv‑issued DOI via DataCite)

提交历史

• v1: Wed, 22 Oct 2025 07:25:54 UTC (28 KB) – submitted by Pascal Bergsträßer
• v2: Thu, 23 Oct 2025 08:09:19 UTC (28 KB)

View PDF | HTML (experimental)