mlsanityData to 14 Oct 2026

Thinking Like Transformers

arXiv 2106.06981 ↗First posted 13 Jun 2021cs.LG cs.CLcited by 184

Not on the map. Why?

Abstract (arXiv)

What is the computational model behind a Transformer? Where recurrent neural networks have direct parallels in finite state machines, allowing clear discussion and thought around architecture variants or trained models, Transformers have no such familiar parallel. In this paper we aim to change that, proposing a computational model for the transformer-encoder in the form of a programming language. We map the basic components of a transformer-encoder -- attention and feed-forward computation -- into simple primitives, around which we form a programming language: the Restricted Access Sequence Processing Language (RASP). We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer, and how a Transformer can be trained to mimic a RASP solution. In particular, we provide RASP programs for histograms, sorting, and Dyck-languages. We further use our model to relate their difficulty in terms of the number of required layers and attention heads: analyzing a RASP program implies a maximum number of heads and layers necessary to encode a task in a transformer. Finally, we see how insights gained from our abstraction might be used to explain phenomena seen in recent works.

Key facts. Cited by 184 papers in the map (data through 14 Oct 2026). Builds on 29 of its 43 references that are in the map. First posted on arXiv 13 Jun 2021.

Builds on

29 of 43 references.

References · 29

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  4. 2020Longformer: The Long-Document Transformercited by 3,413
  5. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  6. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  7. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,026
  8. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  9. 2020Efficient Transformers: A Surveycited by 790
  10. 2018Universal Transformerscited by 647
  11. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  12. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
17 more
  1. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  2. 2020Transformers as Soft Reasoners over Languagecited by 270
  3. 2019Analyzing the Structure of Attention in a Transformer Language Modelcited by 243
  4. 2017Interpretable Convolutional Neural Networkscited by 162
  5. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  6. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  7. 2015Inferring Algorithmic Patterns with Stack-Augmented Recurrent Netscited by 76
  8. 2017Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamplescited by 66
  9. 2020A Formal Hierarchy of RNN Architecturescited by 62
  10. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  11. 2019Sequential Neural Networks as Automatacited by 54
  12. 2019Improving Transformer Models by Reordering their Sublayerscited by 52
  13. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  14. 2020ETC: Encoding Long and Structured Inputs in Transformerscited by 34
  15. 2018Evaluating the Ability of LSTMs to Learn Context-Free Grammarscited by 16
  16. 2018Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learningcited by 15
  17. 2018Explaining Black Boxes on Sequential Data using Weighted Automatacited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 27; 2024: 69; 2025: 44; 2026: 35.

184 papers.

Sort:

By area:

  1. 2023Towards Automated Circuit Discovery for Mechanistic Interpretabilitycited by 724
  2. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  3. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 550
  4. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  6. 2022Transformers Learn Shortcuts to Automatacited by 268
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  8. 2023Looped Transformers as Programmable Computerscited by 237
  9. 2022Neural Networks and the Chomsky Hierarchycited by 217
  10. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  11. 2023A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operationscited by 144
  12. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
38 more
  1. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  2. 2024A Practical Review of Mechanistic Interpretability for Transformer-Based Language Modelscited by 118
  3. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 115
  4. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  5. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  6. 2024Transformers need glasses! Information over-squashing in language taskscited by 91
  7. 2024A Primer on the Inner Workings of Transformer-based Language Modelscited by 85
  8. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  9. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  10. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  11. 2025The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMscited by 64
  12. 2021The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalizationcited by 62
  13. 2024Finding Transformer Circuits with Edge Pruningcited by 60
  14. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  15. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  16. 2025Weight-sparse transformers have interpretable circuitscited by 44
  17. 2023When Do Prompting and Prefix-Tuning Work? A Theory of Capabilities and Limitationscited by 43
  18. 2023Learning Transformer Programscited by 41
  19. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  20. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 40
  21. 2024Memory3: Language Modeling with Explicit Memorycited by 40
  22. 2024Differentiation and Specialization of Attention Heads via the Refined Local Learning Coefficientcited by 40
  23. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  24. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  25. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 37
  26. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 36
  27. 2024Transformers Can Represent n-gram Language Modelscited by 32
  28. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  29. 2024A phase transition between positional and semantic learning in a solvable model of dot-product attentioncited by 30
  30. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  31. 2024Hypothesis Testing the Circuit Hypothesis in LLMscited by 29
  32. 2024Transformers on Markov Data: Constant Depth Sufficescited by 27
  33. 2023Interpretability Illusions in the Generalization of Simplified Modelscited by 25
  34. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  35. 2024Universal Length Generalization with Turing Programscited by 25
  36. 2024InterpBench: Semi-Synthetic Transformers for Evaluating Mechanistic Interpretability Techniquescited by 25
  37. 2024Mechanistic?cited by 25
  38. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 23

50 most cited of 184 All 184 (JSON)