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 exponen-
tially 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 for-
mula or recurrent neural network is exponentially large, and whose smallest equiv-
alent 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 expo-
nential 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.

Read in full here:

https://openreview.net/pdf?id=Yxz92UuPLQ