Probability Distributions Computed by Autoregressive Transformers
Not on the map. Why?
Abstract (arXiv)
Most expressivity results for transformers treat them as language recognizers -- devices that accept or reject strings -- rather than as they are used in practice: as language models that generate strings autoregressively and probabilistically. We characterize the probability distributions that transformer language models can express. We show that making transformer language recognizers autoregressive can sometimes increase their expressivity, and that making them probabilistic can break equivalences that hold in the non-probabilistic case. Our overall contribution is to tease apart what functions transformers are capable of expressing in their most common use case as language models.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 24 of its 45 references that are in the map. First posted on arXiv 31 Oct 2025.
Builds on
24 of 45 references.
References · 24
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
- 2022Transformers Learn Shortcuts to Automatacited by 268
- 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
- 2022Neural Networks and the Chomsky Hierarchycited by 217
- 2023What Formal Languages Can Transformers Express? A Surveycited by 124
- 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
- 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
- 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
- 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
- 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
- 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
12 more
- 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
- 2024Transformers Can Represent n-gram Language Modelscited by 32
- 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
- 2024Universal Length Generalization with Turing Programscited by 25
- 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
- 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
- 2025Constant Bit-size Transformers Are Turing Completecited by 19
- 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
- 2025Unique Hard Attention: A Tale of Two Sidescited by 10
- 2023MLRegTest: A Benchmark for the Machine Learning of Regular Languagescited by 7
- 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
- 2019Aperiodic Weighted Automata and Weighted First-Order Logiccited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.