Transformer 本质上简洁

Source: Hacker News

资源

• 查看 PDF
• HTML（实验性）

摘要

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

主题

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

引用

arXiv:2510.19315 (cs.FL)
或 arXiv:2510.19315v2 (cs.FL)（此版本）。

DOI

https://doi.org/10.48550/arXiv.2510.19315 (arXiv‑issued DOI via DataCite)

提交历史

• v1 – 2025年10月22日 星期三 07:25:54 UTC (28 KB) – 作者 Pascal Bergsträßer (查看电子邮件)
• v2 – 2025年10月23日 星期四 08:09:19 UTC (28 KB)