# Transformers are Inherently Succinct

arXiv: https://arxiv.org/abs/2510.19315 · HTML: https://mlsanity.com/paper/2510.19315/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 45 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [The Fifth International Verification of Neural Networks Competition (VNN-COMP 2024): Summary and Results](https://mlsanity.com/paper/2412.19985/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (2025)
- [Analyzing limits for in-context learning](https://mlsanity.com/paper/2502.03503/) (2025)
- [Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning](https://mlsanity.com/paper/2405.18548/) (2024)

## Built on by (most cited first, 4 of 4)

- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [Grounded Continuation: A Linear-Time Runtime Verifier for LLM Conversations](https://mlsanity.com/paper/2605.14175/) (2026)
- [Score Approximation for Diffusion Models on Arbitrary Low-Dimensional Structures](https://mlsanity.com/paper/2606.19894/) (2026)
- [Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2604.01228/) (2026)

## Abstract (arXiv)

We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a classical notion in logic and automata theory. We prove that fixed-precision transformers are remarkably succinct: they can be exponentially more succinct than both linear temporal logic (LTL) and recurrent neural networks, and, by extension, state-space models, and doubly exponentially more succinct than finite automata. In other words, there exist families of languages describable by polynomial-size transformers whose smallest equivalent LTL formula or recurrent neural network is exponentially large, and whose smallest equivalent automaton is doubly exponentially large. We also establish matching upper bounds, showing that any fixed-precision transformer can be converted to an LTL formula with at most an exponential blow-up -- improving a prior doubly exponential translation. As a consequence of this succinctness, we show that basic verification problems for transformers, such as emptiness and equivalence, are provably intractable: specifically, EXPSPACE-complete.