mlsanityData to 7 Oct 2026

Transformers Learn Shortcuts to Automata

arXiv 2210.10749 ↗First posted 19 Oct 2022cs.LG cs.FL stat.MLcited by 260

Not on the map. Why?

Cited by 49 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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.

Key facts. Cited by 260 papers in the map (data through 7 Oct 2026). Builds on 63 of its 107 references that are in the map. First posted on arXiv 19 Oct 2022.

Builds on

63 of 107 references.

References · 63

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  4. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  6. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  7. 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,243
  8. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,201
  9. 2020Shortcut Learning in Deep Neural Networkscited by 1,928
  10. 2016WaveNet: A Generative Model for Raw Audiocited by 1,710
  11. 2019Dream to Control: Learning Behaviors by Latent Imaginationcited by 1,598
  12. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
38 more
  1. 2016Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translationcited by 1,471
  2. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  3. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  4. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
  5. 2019BERT Rediscovers the Classical NLP Pipelinecited by 1,046
  6. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 994
  7. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  8. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 636
  9. 2014Neural Turing Machinescited by 630
  10. 2018Universal Transformerscited by 613
  11. 2016Adaptive Computation Time for Recurrent Neural Networkscited by 479
  12. 2021Conditional Positional Encodings for Vision Transformerscited by 402
  13. 2020Generative Language Modeling for Automated Theorem Provingcited by 379
  14. 2022Transformers are Sample-Efficient World Modelscited by 317
  15. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  16. 2019Deep Learning for Symbolic Mathematicscited by 266
  17. 2016Benefits of depth in neural networkscited by 248
  18. 2021Mastering Atari Games with Limited Datacited by 235
  19. 2021Scaling Local Self-Attention for Parameter Efficient Visual Backbonescited by 220
  20. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  21. 2016FractalNet: Ultra-Deep Neural Networks without Residualscited by 216
  22. 2022Neural Networks and the Chomsky Hierarchycited by 214
  23. 2022Exploring Length Generalization in Large Language Modelscited by 204
  24. 2020Rethinking Positional Encoding in Language Pre-trainingcited by 197
  25. 2020How Does Mixup Help With Robustness and Generalization?cited by 193
  26. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  27. 2021Thinking Like Transformerscited by 182
  28. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  29. 2022Transformer Language Models without Positional Encodings Still Learn Positional Informationcited by 148
  30. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  31. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 136
  32. 2021Can contrastive learning avoid shortcut solutions?cited by 114
  33. 2021Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networkscited by 108
  34. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  35. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  36. 2021A Neural Network Solves, Explains, and Generates University Math Problems by Program Synthesis and Few-Shot Learning at Human Levelcited by 96
  37. 2021Finetuning Pretrained Transformers into RNNscited by 94
  38. 2020Learning Parities with Neural Networkscited by 77

50 most cited of 63 All 63 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 47; 2024: 81; 2025: 72; 2026: 58.

260 papers.

Sort:

By area:

  1. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  2. 2023Large Language Modelscited by 774
  3. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  4. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  6. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  7. 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoningcited by 257
  8. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  9. 2023Looped Transformers as Programmable Computerscited by 224
  10. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  11. 2024The Illusion of State in State-Space Modelscited by 181
  12. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 168
38 more
  1. 2024The pitfalls of next-token predictioncited by 156
  2. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  3. 2025Scaling Latent Reasoning via Looped Language Modelscited by 145
  4. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 135
  5. 2023Representational Strengths and Limitations of Transformerscited by 132
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  7. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 110
  8. 2024Evaluating the World Model Implicit in a Generative Modelcited by 107
  9. 2024Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Taskscited by 104
  10. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  11. 2023Uncovering mesa-optimization algorithms in Transformerscited by 94
  12. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  13. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  14. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  15. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalizationcited by 78
  16. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  17. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 74
  18. 2024Transformers represent belief state geometry in their residual streamcited by 73
  19. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  20. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  21. 2022LAMBADA: Backward Chaining for Automated Reasoning in Natural Languagecited by 66
  22. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  23. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  24. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  25. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 62
  26. 2024Can Language Models Learn to Skip Steps?cited by 59
  27. 2024How to think step-by-step: A mechanistic understanding of chain-of-thought reasoningcited by 53
  28. 2024ICLR: In-Context Learning of Representationscited by 49
  29. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  30. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  31. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  32. 2025What Has a Foundation Model Found? Using Inductive Bias to Probe for World Modelscited by 46
  33. 2023An Over-parameterized Exponential Regressioncited by 45
  34. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  35. 2024Theoretical limitations of multi-layer Transformercited by 43
  36. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  37. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
  38. 2024An Information-Theoretic Analysis of In-Context Learningcited by 39

50 most cited of 260 All 260 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  2. 2025Constant Bit-size Transformers Are Turing Complete
  3. 2026Adaptive Loops and Memory in Transformers: Think Harder or Know More?
  4. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
  5. 2026Protoreasoning in Tiny Transformers
  6. 2025Transformers are Inherently Succinct
  7. 2025Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
  8. 2026Transformers Linearly Represent Highly Structured World Models