Transformers Learn Shortcuts to Automata

2022/10/19 by Bingbin Liu, Jordan T. Ash, Liu, Bingbin +7 · 3 voices · 39 citations
Computer Science · #Algorithms and Data Compression #Machine Learning and Algorithms #Topic Modeling #cs.FL #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2210.10749

openalex publication_date 2022/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Pretraining Recurrent Networks without Recurrence
• When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
• An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars
• T²MLR: Transformer with Temporal Middle-Layer Recurrence
• Do Language Models Need Sleep? Offline Recurrence for Improved Online Inference
• Is In-Context Learning Learning?
• Position: We Need An Algorithmic Understanding of Generative AI
• Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought
• Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction
• From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers
• In-Context Algebra
• Sequential Enumeration in Large Language Models
• Rectifying LLM Thought from Lens of Optimization
• Language-conditioned world model improves policy generalization by reading environmental descriptions
• Exact Learning of Arithmetic with Differentiable Agents
• Selective Rotary Position Embedding
• Next-Latent Prediction Transformers Learn Compact World Models
• Probability Distributions Computed by Hard-Attention Transformers
• The Scaling Properties of Implicit Deductive Reasoning in Transformers
• Can Language Models Compose Skills In-Context?
• On the Reasoning Abilities of Masked Diffusion Language Models
• Benefits and Limitations of Communication in Multi-Agent Reasoning
• Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
• Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
• Internal Planning in Language Models: Characterizing Horizon and Branch Awareness
• Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thought
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
• Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
• The Topological Trouble With Transformers
• Fast attention mechanisms: a tale of parallelism
• What do language models model? Transformers, automata, and the format of thought
• Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
• Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria
• Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice
• Rethinking Memorization Measures and their Implications in Large Language Models
• Learning State-Tracking from Code Using Linear RNNs
• The Serial Scaling Hypothesis

Discussions

• Transformers Learn Shortcuts to Automata [hn, 37 points, 2 comments]
• Hands down my favorite paper of 2023 arxiv.org/abs/2210.10749 🤖 [bsky, 10 points, 1 comments]
• Algebraic theory of automata (take your pick: Hartmanis-Stearns, Eilenberg, Schützenberger, Krohn-Rhodes) became more relevant in control theory, e.g., through the fundamental work of Michel Fliess. H [bsky, 5 points, 3 comments]

Related

• Constant Bit-size Transformers Are Turing Complete
• The Expressive Power of Transformers with Chain of Thought
• Learning Linear Attention in Polynomial Time
• On the Existence of Universal Simulators of Attention
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers