# Formal Algorithms for Transformers

arXiv: https://arxiv.org/abs/2207.09238 · HTML: https://mlsanity.com/paper/2207.09238/

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 19 Jul 2022.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [A Generalist Agent](https://mlsanity.com/paper/2205.06175/) (2022)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [A Survey of Data Augmentation Approaches for NLP](https://mlsanity.com/paper/2105.03075/) (2021)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)

## Built on by (most cited first, 30 of 72)

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024)
- [The Hydra Effect: Emergent Self-repair in Language Model Computations](https://mlsanity.com/paper/2307.15771/) (2023)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [White-Box Transformers via Sparse Rate Reduction](https://mlsanity.com/paper/2306.01129/) (2023)
- [Exposing Attention Glitches with Flip-Flop Language Modeling](https://mlsanity.com/paper/2306.00946/) (2023)
- [Evolving Code with A Large Language Model](https://mlsanity.com/paper/2401.07102/) (2024)
- [Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods](https://mlsanity.com/paper/2408.14511/) (2024)
- [Completed Hyperparameter Transfer across Modules, Width, Depth, Batch and Duration](https://mlsanity.com/paper/2512.22382/) (2025)
- [Materials science in the era of large language models: a perspective](https://mlsanity.com/paper/2403.06949/) (2024)
- [Can a Transformer Represent a Kalman Filter?](https://mlsanity.com/paper/2312.06937/) (2023)
- [Scaling Embedding Layers in Language Models](https://mlsanity.com/paper/2502.01637/) (2025)
- [Can Transformers Learn to Solve Problems Recursively?](https://mlsanity.com/paper/2305.14699/) (2023)
- [Attention layers provably solve single-location regression](https://mlsanity.com/paper/2410.01537/) (2024)
- [Merging Decision Transformers: Weight Averaging for Forming Multi-Task Policies](https://mlsanity.com/paper/2303.07551/) (2023)
- [Improving accuracy of GPT-3/4 results on biomedical data using a retrieval-augmented language model](https://mlsanity.com/paper/2305.17116/) (2023)
- [RankFormer: Listwise Learning-to-Rank Using Listwide Labels](https://mlsanity.com/paper/2306.05808/) (2023)
- [Hierarchical Neural Simulation-Based Inference Over Event Ensembles](https://mlsanity.com/paper/2306.12584/) (2023)
- [Large Language Models Vote: Prompting for Rare Disease Identification](https://mlsanity.com/paper/2308.12890/) (2023)
- [Wavelets Are All You Need for Autoregressive Image Generation](https://mlsanity.com/paper/2406.19997/) (2024)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Neural Circuit Diagrams: Robust Diagrams for the Communication, Implementation, and Analysis of Deep Learning Architectures](https://mlsanity.com/paper/2402.05424/) (2024)
- [Explainability Techniques for Chemical Language Models](https://mlsanity.com/paper/2305.16192/) (2023)
- [Variational Search Distributions](https://mlsanity.com/paper/2409.06142/) (2024)
- [HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing](https://mlsanity.com/paper/2412.16187/) (2024)
- [Evaluating self-attention interpretability through human-grounded experimental protocol](https://mlsanity.com/paper/2303.15190/) (2023)
- [Mechanistic interpretability of large language models with applications to the financial services industry](https://mlsanity.com/paper/2407.11215/) (2024)
- [Training Dynamics of Softmax Self-Attention: Fast Global Convergence via Preconditioning](https://mlsanity.com/paper/2603.01514/) (2026)
- [Pipeline MoE: A Flexible MoE Implementation with Pipeline Parallelism](https://mlsanity.com/paper/2304.11414/) (2023)
- [Kraken: Inherently Parallel Transformers For Efficient Multi-Device Inference](https://mlsanity.com/paper/2408.07802/) (2024)

## Abstract (arXiv)

This document aims to be a self-contained, mathematically precise overview of transformer architectures and algorithms (*not* results). It covers what transformers are, how they are trained, what they are used for, their key architectural components, and a preview of the most prominent models. The reader is assumed to be familiar with basic ML terminology and simpler neural network architectures such as MLPs.