A new theoretical paper from researchers at arXiv demonstrates that transformer models are inherently more succinct than traditional representations of formal languages, such as finite automata and Linear Temporal Logic (LTL) formulas. The work, titled "Transformers Are Inherently Succinct," provides a formal proof that transformers can represent certain concepts using exponentially fewer parameters than standard automata or logic-based descriptions.
Overview
The paper proposes "succinctness" as a formal measure of expressive power: how compactly a transformer can describe a concept compared to other representations. The authors prove that transformers are highly expressive in this sense, showing they can represent formal languages substantially more succinctly than finite automata or LTL formulas. This is a theoretical result, not an empirical one—it establishes a provable lower bound on the compression advantage of transformers.
What the proof shows
The key finding is that transformers can encode certain languages with exponentially fewer parameters than the equivalent finite automaton or LTL formula. For example, a language that requires a finite automaton with exponentially many states can be represented by a transformer with a polynomial number of parameters. This succinctness stems from the self-attention mechanism and autoregressive decoding process, which allow the model to reuse computations across positions in the input sequence.
Tradeoffs
The paper also reveals a significant downside to this expressivity: verifying properties of transformers is provably intractable. Specifically, the problem of checking whether a transformer satisfies a given specification is EXPSPACE-complete—meaning it requires exponential space in the worst case. This is a direct consequence of the model's succinctness: the more compact the representation, the harder it is to reason about its behavior.
Practical implications
For practitioners, the result has several implications:
- Compression: Transformers can be used as lossless compressors for certain formal languages, potentially outperforming traditional automata-based methods.
- Verification: The EXPSPACE-completeness result means that automated verification of transformer behavior (e.g., for safety-critical applications) is fundamentally hard, even for small models.
- Architecture design: The proof suggests that the self-attention mechanism is not just a practical convenience but a theoretically optimal way to achieve succinct representations.
When to use it
This paper is primarily of interest to researchers working on formal verification of neural networks, theoretical computer science, or language model interpretability. For everyday users of transformer-based tools (like ChatGPT or Claude), the practical impact is indirect: it explains why these models can generate concise outputs, but also why debugging their behavior is difficult.
Bottom line
The paper provides a rigorous theoretical foundation for a property many practitioners have observed anecdotally: transformers are