# Limitations of Autoregressive Models and Their Alternatives

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

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

- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [Imitating Human Behaviour with Diffusion Models](https://mlsanity.com/paper/2301.10677/) (2023)
- [Challenges and Applications of Large Language Models](https://mlsanity.com/paper/2307.10169/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Likelihood-Based Diffusion Language Models](https://mlsanity.com/paper/2305.18619/) (2023)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Language Models as Agent Models](https://mlsanity.com/paper/2212.01681/) (2022)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [HYPRO: A Hybridly Normalized Probabilistic Model for Long-Horizon Prediction of Event Sequences](https://mlsanity.com/paper/2210.01753/) (2022)
- [Diffusion Language Models Can Perform Many Tasks with Scaling and Instruction-Finetuning](https://mlsanity.com/paper/2308.12219/) (2023)
- [Unveiling Causal Reasoning in Large Language Models: Reality or Mirage?](https://mlsanity.com/paper/2506.21215/) (2025)
- [Towards Efficient Exact Optimization of Language Model Alignment](https://mlsanity.com/paper/2402.00856/) (2024)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Pangu-Agent: A Fine-Tunable Generalist Agent with Structured Reasoning](https://mlsanity.com/paper/2312.14878/) (2023)
- [TESS 2: A Large-Scale Generalist Diffusion Language Model](https://mlsanity.com/paper/2502.13917/) (2025)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Parallel Vertex Diffusion for Unified Visual Grounding](https://mlsanity.com/paper/2303.07216/) (2023)
- [A Tutorial on LLM Reasoning: Relevant Methods behind ChatGPT o1](https://mlsanity.com/paper/2502.10867/) (2025)
- [DLM-One: Diffusion Language Models for One-Step Sequence Generation](https://mlsanity.com/paper/2506.00290/) (2025)
- [Language modeling via stochastic processes](https://mlsanity.com/paper/2203.11370/) (2022)
- [CordViP: Correspondence-based Visuomotor Policy for Dexterous Manipulation in Real-World](https://mlsanity.com/paper/2502.08449/) (2025)
- [animal2vec and MeerKAT: A self-supervised transformer for rare-event raw audio input and a large-scale reference dataset for bioacoustics](https://mlsanity.com/paper/2406.01253/) (2024)
- [OCEAN: Offline Chain-of-thought Evaluation and Alignment in Large Language Models](https://mlsanity.com/paper/2410.23703/) (2024)
- [Language Model Decoding as Direct Metrics Optimization](https://mlsanity.com/paper/2310.01041/) (2023)
- [Reflection-Window Decoding: Text Generation with Selective Refinement](https://mlsanity.com/paper/2502.03678/) (2025)
- [AI Must Embrace Specialization via Superhuman Adaptable Intelligence](https://mlsanity.com/paper/2602.23643/) (2026)

## Abstract (arXiv)

Standard autoregressive language models perform only polynomial-time computation to compute the probability of the next symbol. While this is attractive, it means they cannot model distributions whose next-symbol probability is hard to compute. Indeed, they cannot even model them well enough to solve associated easy decision problems for which an engineer might want to consult a language model. These limitations apply no matter how much computation and data are used to train the model, unless the model is given access to oracle parameters that grow superpolynomially in sequence length. Thus, simply training larger autoregressive language models is not a panacea for NLP. Alternatives include energy-based models (which give up efficient sampling) and latent-variable autoregressive models (which give up efficient scoring of a given string). Both are powerful enough to escape the above limitations.