ICLR 2026: Transformers Proven Exponentially More Succinct Than LTL, RNNs
Get the Tech newsletter
Daily tech — startups, AI labs, chips, the launches that shape the next decade. Free.
- Pascal Bergstraßer, Anthony W. Lin, and Ryan Cotterell authored "Transformers are Inherently Succinct" (ICLR 2026), proposing succinctness — not just expressive power — as a new lens for comparing neural architectures.
- The paper proves fixed-precision transformers are exponentially more succinct than linear temporal logic (LTL) and recurrent neural networks (RNNs), and by extension state-space models (SSMs), meaning polynomial-size transformers can describe languages that force exponentially larger LTL formulas or RNNs.
- Transformers are also doubly exponentially more succinct than finite automata, with polynomial-size transformers capturing languages whose smallest equivalent automaton is doubly exponentially large.
- The key technical ingredient is that transformers can count from 1 to 2^(2^N) — implementing doubly exponentially large counters via a subtle encoding through attention.
- Matching upper bounds show any fixed-precision transformer can be converted to an LTL formula with at most an exponential blow-up, improving a prior doubly exponential translation by Yang et al. (2024).
- As a consequence, basic verification problems for transformers — checking whether a given transformer recognizes a trivial language, or whether two transformers are equivalent — are EXPSPACE-complete, meaning no algorithm can solve them in less than double exponential time under standard complexity assumptions.
- The analysis targets the unique-hard attention transformer (UHAT), with expressivity bounds extending to softmax transformers under fixed precision per Jerad et al. (2025).
Why it matters: The paper reframes the transformer-vs-RNN debate away from raw expressive capacity (where RNNs win) and toward compactness of description — and the practical fallout is that formally verifying transformer behavior hits an EXPSPACE-complete wall. Anyone building tools to certify or debug transformer models inherits a double-exponential-time lower bound on even the simplest questions, like whether a model recognizes the empty language.
Ask SkimNews
