mlsanityData to 7 Oct 2026

Limitations of Autoregressive Models and Their Alternatives

arXiv 2010.11939 ↗First posted 22 Oct 2020cs.LG cs.CL stat.MLcited by 54

Not on the map. Why?

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.

Key facts. Cited by 54 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 16; 2024: 13; 2025: 11; 2026: 7.

54 papers.

Sort:

By area:

  1. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  2. 2024Scaling Diffusion Language Models via Adaptation from Autoregressive Modelscited by 268
  3. 2023Imitating Human Behaviour with Diffusion Modelscited by 260
  4. 2023Challenges and Applications of Large Language Modelscited by 251
  5. 2024The pitfalls of next-token predictioncited by 156
  6. 2023Likelihood-Based Diffusion Language Modelscited by 147
  7. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
  8. 2022Language Models as Agent Modelscited by 131
  9. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  10. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  11. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  12. 2022HYPRO: A Hybridly Normalized Probabilistic Model for Long-Horizon Prediction of Event Sequencescited by 57
38 more
  1. 2023Diffusion Language Models Can Perform Many Tasks with Scaling and Instruction-Finetuningcited by 39
  2. 2024Towards Efficient Exact Optimization of Language Model Alignmentcited by 37
  3. 2025Unveiling Causal Reasoning in Large Language Models: Reality or Mirage?cited by 36
  4. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 32
  5. 2021Sequence-to-Sequence Learning with Latent Neural Grammarscited by 30
  6. 2023Pangu-Agent: A Fine-Tunable Generalist Agent with Structured Reasoningcited by 30
  7. 2025TESS 2: A Large-Scale Generalist Diffusion Language Modelcited by 30
  8. 2023Parallel Vertex Diffusion for Unified Visual Groundingcited by 28
  9. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  10. 2025A Tutorial on LLM Reasoning: Relevant Methods behind ChatGPT o1cited by 24
  11. 2025DLM-One: Diffusion Language Models for One-Step Sequence Generationcited by 19
  12. 2022Language modeling via stochastic processescited by 18
  13. 2025CordViP: Correspondence-based Visuomotor Policy for Dexterous Manipulation in Real-Worldcited by 16
  14. 2024animal2vec and MeerKAT: A self-supervised transformer for rare-event raw audio input and a large-scale reference dataset for bioacousticscited by 14
  15. 2024OCEAN: Offline Chain-of-thought Evaluation and Alignment in Large Language Modelscited by 12
  16. 2023Language Model Decoding as Direct Metrics Optimizationcited by 8
  17. 2023Autoregressive Modeling with Lookahead Attentioncited by 7
  18. 2024Guaranteed Generation from Large Language Modelscited by 7
  19. 2025Reflection-Window Decoding: Text Generation with Selective Refinementcited by 7
  20. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  21. 2024Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelinescited by 6
  22. 2026AI Must Embrace Specialization via Superhuman Adaptable Intelligencecited by 6
  23. 2023Principled Gradient-based Markov Chain Monte Carlo for Text Generationcited by 4
  24. 2023Mini-Giants: "Small" Language Models and Open Source Win-Wincited by 3
  25. 2023LinguaLinked: A Distributed Large Language Model Inference System for Mobile Devicescited by 3
  26. 2025Theoretical Guarantees for Minimum Bayes Risk Decodingcited by 3
  27. 2021Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offscited by 2
  28. 2024Detecting Machine-Generated Long-Form Content with Latent-Space Variablescited by 1
  29. 2024Online Multi-modal Root Cause Identification in Microservice Systemscited by 1
  30. 2025Type-Compliant Adaptation Cascades: Adapting Programmatic LM Workflows to Datacited by 1
  31. 2026Binary Rewards and Reinforcement Learning: Fundamental Challengescited by 1
  32. 2026Leveraging Pretrained Language Models as Energy Functions for Glauber Dynamics Text Diffusioncited by 1
  33. 2022Self-learning locally-optimal hypertuning using maximum entropy, and comparison of machine learning approaches for estimating fatigue life in composite materialscited by 0
  34. 2023Stochastic Code Generationcited by 0
  35. 2024Local Attention Mechanism: Boosting the Transformer Architecture for Long-Sequence Time Series Forecastingcited by 0
  36. 2024SetLexSem Challenge: Using Set Operations to Evaluate the Lexical and Semantic Robustness of Language Modelscited by 0
  37. 2025Learning Model Successorscited by 0
  38. 2025SMCLM: Semantically Meaningful Causal Language Modeling for Autoregressive Paraphrase Generationcited by 0

50 most cited of 54 All 54 (JSON)