Transformers Learn Shortcuts to Automata
This addresses the fundamental question of how non-recurrent models achieve efficient reasoning, with implications for understanding and improving AI systems, though it is incremental in extending theoretical insights to Transformers.
The paper tackled the problem of how shallow Transformer models can perform algorithmic reasoning without recurrence, finding that they can represent finite-state automata computations with fewer layers than steps, specifically showing polynomial-sized O(log T)-depth solutions exist and O(1)-depth simulators are common.
Algorithmic reasoning requires capabilities which are most naturally understood through recurrent models of computation, like the Turing machine. However, Transformer models, while lacking recurrence, are able to perform such reasoning using far fewer layers than the number of reasoning steps. This raises the question: what solutions are learned by these shallow and non-recurrent models? We find that a low-depth Transformer can represent the computations of any finite-state automaton (thus, any bounded-memory algorithm), by hierarchically reparameterizing its recurrent dynamics. Our theoretical results characterize shortcut solutions, whereby a Transformer with $o(T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We find that polynomial-sized $O(\log T)$-depth solutions always exist; furthermore, $O(1)$-depth simulators are surprisingly common, and can be understood using tools from Krohn-Rhodes theory and circuit complexity. Empirically, we perform synthetic experiments by training Transformers to simulate a wide variety of automata, and show that shortcut solutions can be learned via standard training. We further investigate the brittleness of these solutions and propose potential mitigations.