Transformers Can Represent Formal Languages More Succinctly Than Finite Automata, But Verification Is Intractable
By
[Submitted on 22 Oct 2025 (v1), last revised 23 Oct 2025 (this version, v2)]
27d ago· 1 min readenInsight
70/100
Toasty
Bagelometer↗
A good honest bake. Not flashy, but you'll finish the whole bagel.
Score70TypeanalysisSentimentneutral
Summary
This paper introduces "succinctness" as a metric for measuring the expressive power of transformers. The authors prove that transformers can represent formal languages much more succinctly than traditional representations like finite automata and Linear Temporal Logic (LTL) formulas. A key finding is that this high expressivity comes with a trade-off: verifying properties of transformers is provably intractable (EXPSPACE-complete).
Key quotes
· 3 pulledWe propose succinctness as a measure of the expressive power of a transformer in describing a concept.
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).
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 re
