Thinking Like Transformers
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
RASP-L is a human-readable programming language whose programs can be compiled into Transformer weights, with each line compiling into at most one Transformer layer.
“RASP-L is a human-readable programming language which defines programs that can be compiled into Transformer weightsfoot_0 , such that each line of RASP-L compiles into at most one Transformer layer.”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Weiss et al., 2021
Section 3.1 (p. 6) says RASP programs compile to Transformer architectures, but explicitly states that full compilation to concrete Transformer weights is beyond the paper’s scope. The paper calls its language RASP, not RASP-L, and does not establish that each line compiles into at most one layer. (LLM, conf=0.90)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredA decoder-only autoregressive Transformer is likely to length-generalize when trained to completion on an algorithmic task if the task can be solved by a short RASP-L program that works for all input lengths.
“introduce the RASP-Generalization Conjecture: Transformers tend to length generalize on a task if the task can be solved by a short RASP program which works for all input lengths.”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Weiss et al., 2021
The Abstract (p. 1) proposes RASP as a model for transformer encoders, and Experiments (pp. 8–9) show that transformers can learn several tasks with RASP solutions. But the paper does not state the claimed length-generalization conjecture: Appendix A.2 (p. 13) reports training and testing on sequences within the same 0–100 length range. The cited evidence also does not establish the claim for decoder-only autoregressive Transformers or RASP-L. (LLM, conf=0.86)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 29
- Ainslie, J., Ontañón, S., Alberti, C., Pham, P., Ravula, A., and Sanghai, S. ETC: encoding long and structured data in transformers. CoRR , abs/2004.08483, 2020. URL https://arxiv.org/abs/2004.08483 . · arXiv
- Ayache, S., Eyraud, R., and Goudian, N. Explaining black boxes on sequential data using weighted automata. In Proceedings of the 14th International Conference on Grammatical Inference, ICGI , 2018. URL http: //proceedings.mlr.press/v93/ayache19a.html .
- Bahdanau, D., Cho, K., and Bengio, Y. Neural machine translation by jointly learning to align and translate. In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference on Learning Representations, ICLR , 2015. URL http://arxiv.org/abs/1409.0473 . · arXiv
- Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The long-document transformer. CoRR , abs/2004.05150, 2020. URL https://arxiv.org/abs/2004.05150 . · arXiv
- Bernardy, J.-P. Can recurrent neural networks learn nested recursion? In Linguistic Issues in Language Technology, Volume 16 . CSLI Publications, 2018. URL https://www. aclweb.org/anthology/2018.lilt-16.1 .
- Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP , 2020. URL https://doi.org/10.18653/v1/ 2020.emnlp-main.576 . · DOI
- Child, R., Gray, S., Radford, A., and Sutskever, I. Generating long sequences with sparse transformers. CoRR , abs/1904.10509, 2019. URL http://arxiv.org/abs/ 1904.10509 . · arXiv
- Clark, K., Khandelwal, U., Levy, O., and Manning, C. D. What does BERT look at? an analysis of bert's attention. CoRR , abs/1906.04341, 2019. URL http://arxiv.org/ abs/1906.04341 . · arXiv
- Clark, P., Tafjord, O., and Richardson, K. Transformers as soft reasoners over language. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI , 2020. URL https://doi.org/10. 24963/ijcai.2020/537 .
- ICLR , 2019. URL https://openreview.net/forum? id=HyzdRiR9Y7 .
- Hahn, M. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics , 2020. URL https://transacl.org/ojs/index.php/ tacl/article/view/1815 .
- Hewitt, J., Hahn, M., Ganguli, S., Liang, P., and Manning, C. D. Rnns can generate bounded hierarchical languages with optimal memory. In Webber, B., Cohn, T., He, Y., and Liu, Y. (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP , 2020. URL https://doi.org/10.18653/v1/ 2020.emnlp-main.156 . · DOI
- Joulin, A. and Mikolov, T. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems, NeurIPS , 2015. URL https://arxiv.org/abs/1503.01007 . · arXiv
- Merrill, W. Sequential neural networks as automata. CoRR , 2019. URL http://arxiv.org/abs/1906.01615 . · arXiv
- Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., and Smith, N. A. Parameter norm growth during training of transformers. CoRR , 2020a. URL https://arxiv.org/ abs/2010.09697 . · arXiv
- Merrill, W., Weiss, G., Goldberg, Y., Schwartz, R., Smith, N. A., and Yahav, E. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics , 2020b. URL https://www.aclweb.org/anthology/ 2020.acl-main.43 .
- Omlin, C. W. and Giles, C. L. Extraction of rules from discrete-time recurrent neural networks. Neural Networks , 9(1):41-52, 1996. URL https://doi.org/10.1016/ 0893-6080(95)00086-0 .
- Pérez, J., Barceló, P., and Marinkovic, J. Attention is turingcomplete. Journal of Machine Learning Research , 22, 2021. URL http://jmlr.org/papers/v22/20-302. html .
- Press, O., Smith, N. A., and Levy, O. Improving transformer models by reordering their sublayers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL , 2020. URL https://www. aclweb.org/anthology/2020.acl-main.270/ .
- Rabusseau, G., Li, T., and Precup, D. Connecting weighted automata and recurrent neural networks through spectral learning. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS , volume 89 of Proceedings of Machine Learning Research , 2019. URL http://proceedings.mlr.press/v89/ rabusseau19a.html .
- Roy, A., Saffar, M., Vaswani, A., and Grangier, D. Efficient content-based sparse attention with routing transformers. Trans. Assoc. Comput. Linguistics , 9, 2021. URL https://transacl.org/ojs/index.php/tacl/ article/view/2405 .
- Sennhauser, L. and Berwick, R. C. Evaluating the ability of lstms to learn context-free grammars. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, BlackboxNLP@EMNLP , pp. 115-124, 2018. URL https://doi.org/10.18653/v1/ w18-5414 . · DOI
- Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. Efficient transformers: A survey. CoRR , abs/2009.06732, 2020. URL https://arxiv.org/abs/2009.06732 . · arXiv
- Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, NeurIPS , 2017. URL https: //proceedings.neurips.cc/paper/2017/hash/ 3f5ee243547dee91fbd053c1c4a845aa-Abstract. html .
- Weiss, G., Goldberg, Y., and Yahav, E. On the practical computational power of finite precision rnns for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL , 2018a. URL https://aclanthology.info/papers/ P18-2117/p18-2117 .
- Weiss, G., Goldberg, Y., and Yahav, E. Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning, ICML , 2018b. URL http://proceedings.mlr.press/v80/ weiss18a.html .
- Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. Self-attention networks can process bounded hierarchical languages. CoRR , 2021. URL https://arxiv.org/ abs/2105.11115 . · arXiv
- Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are transformers universal approximators of sequence-to-sequence functions? In 8th International Conference on Learning Representations, ICLR , 2020. URL https://openreview.net/forum? id=ByxRM0Ntvr .
- Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontañón, S., Pham, P., Ravula, A., Wang, Q., Yang, L., and Ahmed, A. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020. URL https: //proceedings.neurips.cc/paper/2020/hash/ c8512d142a2d849725f31a9a7a361ab9-Abstract. html .
Cited by
Sorted by citations
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., & Wang, L. (2023) · arXiv · doi:10.48550/arxiv.2305.15408 · Cited by 69 · see citing works
“[57] Gail Weiss, Yoav Goldberg, and Eran Yahav.”
BackgroundResultGSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models
Mirzadeh, I., Alizadeh, K., Shahrokhi, H., Tuzel, O., Bengio, S., & Farajtabar, M. (2024) · arXiv · doi:10.48550/arxiv.2410.05229 · Cited by 57 · see citing works
“For example, parallels have been drawn between components such as attention and feed-forward modules and simple computational primitives (Weiss et al., 2021; Zhou et al., 2024).”
Overcoming a Theoretical Limitation of Self-Attention
Chiang, D., & Cholak, P. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.527 · Cited by 39 · see citing works
What Formal Languages Can Transformers Express? A Survey
Strobl, L., Merrill, W., Weiss, G., Chiang, D., & Angluin, D. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00663 · Cited by 31 · see citing works
Self-citationSaturated Transformers are Constant-Depth Threshold Circuits
Merrill, W., Sabharwal, A., & Smith, N. A. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00493 · Cited by 25 · see citing works
Caution Ahead: Numerical Reasoning and Look‐Ahead Bias in AI Models
LEVY, B. (2026) · Journal of Accounting Research · doi:10.1111/1475-679x.70058 · Cited by 20 · see citing works
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · see citing works
“The original RASP language can be thought of as a domain-specific-language for specifying Trans-former weights, in human-readable form (Weiss et al., 2021).”
BackgroundMethodInfluentialBeyond the Frontier: Predicting Unseen Walls From Occupancy Grids by Learning From Floor Plans
Ericson, L., & Jensfelt, P. (2024) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2024.3410164 · Cited by 10 · see citing works
The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic GeneralizationPreprint
Csordás, R., Irie, K., & Schmidhuber, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.07732 · Cited by 11 · see citing works
Cui, H., Behrens, F., Krząkała, F., & Zdeborová, L. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ade137 · Cited by 5 · see citing works
The ambiguity of BERTology: what do large language models represent?
Gröndahl, T. (2023) · Synthese · doi:10.1007/s11229-023-04435-5 · Cited by 5 · see citing works
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · see citing works
Neural Recognition of Dashed Curves with Gestalt Law of Continuity
Liu, H., Li, C., Liu, X., & Wong, T. (2022) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52688.2022.00143 · Cited by 4 · see citing works
Irie, K., Csordás, R., & Schmidhuber, J. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.588 · Cited by 3 · see citing works
Making sense of transformer success
Angius, N., Perconti, P., Plebe, A., & Acciai, A. (2025) · Frontiers in Artificial Intelligence · doi:10.3389/frai.2025.1509338 · Cited by 2 · see citing works
Strobl, L., Angluin, D., Chiang, D., Rawski, J., & Sabharwal, A. (2025) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00736 · Cited by 4 · see citing works
FloorGenT: Generative Vector Graphic Model of Floor Plans for Robotics
Ericson, L., & Jensfelt, P. (2022) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros47612.2022.9982144 · Cited by 2 · see citing works
The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs
Sinha, A., Arun, A., Goel, S., Staab, S., & Geiping, J. (2025) · arXiv · doi:10.48550/arxiv.2509.09677 · Cited by 1 · see citing works
“This is consistent with prior work showing the necessity of thinking tokens for transformers to perform sequential tasks (Weiss et al., 2021; Merrill & Sabharwal, 2023).”
Uncovering patterns of semantic predictability in sentence processing
Jacobs, C. L., Hubbard, R. J., Grobol, L., & Federmeier, K. D. (2025) · Journal of Memory and Language · doi:10.1016/j.jml.2025.104653 · Cited by 1 · see citing works
Language models need inductive biases to count inductively
Chang, Y., & Bisk, Y. (2024) · arXiv · doi:10.48550/arxiv.2405.20131
“This corresponds to the “selector_width" primitive in RASP.”
BackgroundMethodInfluentialLength Generalization Bounds for Transformers
Yang, A., Bergsträßer, P., Zetzsche, G., Chiang, D., & Lin, A. W. (2026) · Zenodo · doi:10.5281/zenodo.18800699
Implicit Language Models are RNNs: Balancing Parallelization and Expressivity
Schöne, M., Rahmani, B., Kremer, H., Falck, F., Ballani, H., & Gladrow, J. (2025) · arXiv · doi:10.48550/arxiv.2502.07827
“Weiss et al. (2021) observe that programs written in a specific language (RASP) can be mapped to transformer models of sufficient capacity.”
Looped Transformers for Length Generalization
Fan, Y., Du, Y., Ramchandran, K., & Lee, K. (2024) · arXiv · doi:10.48550/arxiv.2409.15647
Constraint satisfaction in large language modelsPreprint
Jacobs, C. L., & MacDonald, M. C. (2024) · doi:10.31234/osf.io/xfnpb
Uncovering patterns of semantic predictability in sentence processingPreprint
Jacobs, C. L., Hubbard, R. J., Federmeier, K. D., & Grobol, L. (2024) · doi:10.31234/osf.io/znkpg
Model Mapping: Can We Turn Transformers Into Programs?Preprint
Upadhyay, S., Keigwin, B., Wu, Y., Samkharadze, L., Hu, J., & Ginsburg, E. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5026576
Model Mapping: Can We Turn Transformers Into Programs?Preprint
Upadhyay, S., Keigwin, B., Bandi, C., Wu, Y., Samkharadze, L., Hu, J., & Ginsberg, E. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5361294
- Authors
- Weiss, G., Goldberg, Y., & Yahav, E.
- Affiliations
- Technion – Israel Institute of Technology (IL)
- Bar-Ilan University (IL)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2021
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2106.06981
- OpenAlex
- W3121462755
- Cited by
- 18
- References
- 0
- Citations by year
- 2026: 1 · 2025: 6 · 2024: 4 · 2023: 2 · 2022: 4 · 2021: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Keywords
- transformer models, Transformer encoder, computational model, programming languages, RASP, attention mechanism, feedforward neural networks, finite automata, recurrent neural networks, histogram computation, sorting, Dyck languages, attention heads, number of layers, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
