# Probability Distributions Computed by Autoregressive Transformers

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

## 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 (most cited first, 24 of 24)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)
- [Aperiodic Weighted Automata and Weighted First-Order Logic](https://mlsanity.com/paper/1902.08149/) (2019)

## Built on by (most cited first, 2 of 2)

- [Encoder-Decoder Transformers: Logical Characterizations and Periodicity](https://mlsanity.com/paper/2605.07705/) (2026)
- [Surprisal Theory is Tautological (without Rational Grounding)](https://mlsanity.com/paper/2607.21574/) (2026)

## 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.