Transformers Are Inherently Succinct
Published: (May 4, 2026 at 04:03 PM EDT)
1 min read
Source: Hacker News
Source: Hacker News
Resources
Abstract
We propose succinctness as a measure of the expressive power of a transformer in describing a concept. To this end, we prove that transformers are highly expressive in that they can represent formal languages substantially more succinctly than standard representations of formal languages like finite automata and Linear Temporal Logic (LTL) formulas. As a by‑product of this expressivity, we show that verifying properties of transformers is provably intractable (i.e. EXPSPACE‑complete).
Subjects
- Formal Languages and Automata Theory (cs.FL)
- Machine Learning (cs.LG)
- Logic in Computer Science (cs.LO)
Citation
arXiv:2510.19315 (cs.FL)
or arXiv:2510.19315v2 (cs.FL) for this version.
DOI
https://doi.org/10.48550/arXiv.2510.19315 (arXiv‑issued DOI via DataCite)
Submission history
- v1 – Wed, 22 Oct 2025 07:25:54 UTC (28 KB) – by Pascal Bergsträßer (view email)
- v2 – Thu, 23 Oct 2025 08:09:19 UTC (28 KB)