Paper proves transformers represent formal languages far more succinctly than finite automata or LTL formulas, making transformer verification EXPSPACE-complete.
Key Takeaways
Preprint (arXiv:2510.19315) introduces succinctness as a formal measure of transformer expressive power over concepts and languages.
Transformers can encode formal languages with exponentially more compact representations than equivalent finite automata or Linear Temporal Logic formulas.
The expressivity gain has a hard cost: verifying transformer properties is provably intractable at EXPSPACE-complete complexity.
Result has direct implications for formal safety verification and any tooling that tries to guarantee transformer behavior on formal language tasks.
