Softmax Transformers Are Doubly Exponentially Succinct

We prove that fixed-precision softmax transformers can be doubly exponentially more succinct than finite automata, resolving an open question. Over a fixed alphabet, we construct constant-depth transformers with causal masking, one head per layer, no positional encodings, width and precision $O(n)$, and description length $O(n^3)$. The smallest equivalent NFAs and DFAs each have $2^{\Theta (2^n)}$ states, although every accepted word has length $\Theta (n{2}^n)$. The state lower bound comes from the $2^{2^n}$ Boolean tables encoded by prefixes. The separation also holds for fixed-precision average-hard attention. The same language requires description size $2^{\Theta (n)}$ in C-RASP+, a counting-based formalism expressively equivalent to $(1,1)$-precision transformers. This resolves a second open question by ruling out a polynomial-size translation into C-RASP+. A direct finite-state simulation yields a doubly exponential DFA upper bound and singly exponential bounds on shortest accepted and distinguishing words. Finally, we show that nonemptiness is NEXP-complete under the same architectural restrictions.