mlsanityData to 14 Oct 2026

Auto-Regressive Next-Token Predictors are Universal Learners

arXiv 2309.06979 ↗First posted 13 Sep 2023cs.LG cs.CLcited by 67

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Large language models display remarkable capabilities in logical and mathematical reasoning, allowing them to solve complex tasks. Interestingly, these abilities emerge in networks trained on the simple task of next-token prediction. In this work, we present a theoretical framework for studying auto-regressive next-token predictors. We demonstrate that even simple models such as linear next-token predictors, trained on Chain-of-Thought (CoT) data, can approximate any function efficiently computed by a Turing machine. We introduce a new complexity measure -- length complexity -- which measures the number of intermediate tokens in a CoT sequence required to approximate some target function, and analyze the interplay between length complexity and other notions of complexity. Finally, we show experimentally that simple next-token predictors, such as linear networks and shallow Multi-Layer Perceptrons (MLPs), display non-trivial performance on text generation and arithmetic tasks. Our results demonstrate that the power of today's LLMs can be attributed, to a great extent, to the auto-regressive next-token training scheme, and not necessarily to a particular choice of architecture.

Key facts. Cited by 67 papers in the map (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 39 of its 53 references that are in the map. First posted on arXiv 13 Sep 2023.

Builds on

39 of 53 references.

References · 39

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2023GPT-4 Technical Reportcited by 18,396
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  6. 2023Let's Verify Step by Stepcited by 3,789
  7. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  8. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  9. 2021MLP-Mixer: An all-MLP Architecture for Visioncited by 1,446
  10. 2022LaMDA: Language Models for Dialog Applicationscited by 1,220
  11. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  12. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 827
27 more
  1. 2016Language Modeling with Gated Convolutional Networkscited by 702
  2. 2023TinyStories: How Small Can Language Models Be and Still Speak Coherent English?cited by 449
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2021Pay Attention to MLPscited by 368
  5. 2016Solving General Arithmetic Word Problemscited by 360
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  7. 2022Teaching Small Language Models to Reasoncited by 284
  8. 2022Transformers Learn Shortcuts to Automatacited by 268
  9. 2023Looped Transformers as Programmable Computerscited by 237
  10. 2023Symbolic Chain-of-Thought Distillation: Small Models Can Also "Think" Step-by-Stepcited by 148
  11. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  12. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 139
  13. 2022Explanations from Large Language Models Make Small Reasoners Bettercited by 124
  14. 2022A Survey of Deep Learning for Mathematical Reasoningcited by 124
  15. 2023Teaching Arithmetic to Small Transformerscited by 123
  16. 2021An Attention Free Transformercited by 112
  17. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  18. 2023Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Taskscited by 84
  19. 2017Failures of Gradient-Based Deep Learningcited by 80
  20. 2020Learning Parities with Neural Networkscited by 78
  21. 2022Limitations of Language Models in Arithmetic and Symbolic Inductioncited by 71
  22. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  23. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 33
  24. 2023Evaluating Transformer Language Models on Arithmetic Operations Using Number Decompositioncited by 15
  25. 2020When Hardness of Approximation Meets Hardness of Learningcited by 7
  26. 2015A Linear Dynamical System Model for Textcited by 6
  27. 2018Provable limitations of deep learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 23; 2025: 21; 2026: 18.

67 papers.

Sort:

By area:

  1. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  2. 2023Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solvecited by 178
  3. 2024The pitfalls of next-token predictioncited by 160
  4. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
  5. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 104
  6. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  7. 2024Can large language models explore in-context?cited by 76
  8. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  9. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 40
  10. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 36
  11. 2025Roll the dice & look before you leap: Going beyond the creative limits of next-token predictioncited by 29
  12. 2024Universal Length Generalization with Turing Programscited by 25
38 more
  1. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 23
  2. 2024Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregationcited by 22
  3. 2024Mixture of Parrots: Experts improve memorization more than reasoningcited by 21
  4. 2024Truth-Aware Context Selection: Mitigating Hallucinations of Large Language Models Being Misled by Untruthful Contextscited by 15
  5. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  6. 2025Position: A Theory of Deep Learning Must Include Compositional Sparsitycited by 14
  7. 2026Continuous Latent Diffusion Language Modelcited by 14
  8. 2023Improving Length-Generalization in Transformers via Task Hintingcited by 13
  9. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 13
  10. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  11. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  12. 2024Semformer: Transformer Language Models with Semantic Planningcited by 9
  13. 2025Learning Algorithms in the Limitcited by 9
  14. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspectivecited by 9
  15. 2023Conditions for Length Generalization in Learning Reasoning Skillscited by 7
  16. 2024Models That Prove Their Own Correctnesscited by 7
  17. 2025Sequential keypoint density estimator: an overlooked baseline of skeleton-based video anomaly detectioncited by 7
  18. 2025CoT Information: Improved Sample Complexity under Chain-of-Thought Supervisioncited by 6
  19. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  20. 2025Position: We Need An Algorithmic Understanding of Generative AIcited by 5
  21. 2025Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNetscited by 5
  22. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-Endcited by 5
  23. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  24. 2024Unraveling Arithmetic in Large Language Models: The Role of Algebraic Structurescited by 4
  25. 2025Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networkscited by 4
  26. 2025To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Modelscited by 4
  27. 2024Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspectivecited by 3
  28. 2025Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regressioncited by 3
  29. 2025On efficiently computable functions, deep networks and sparse compositionalitycited by 3
  30. 2026Learning to Think from Multiple Thinkerscited by 3
  31. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoningcited by 3
  32. 2024Spin glass model of in-context learningcited by 2
  33. 2024Next-Token Prediction Task Assumes Optimal Data Ordering for LLM Training in Proof Generationcited by 2
  34. 2025Correlation Dimension of Auto-Regressive Large Language Modelscited by 2
  35. 2026Knowledge without Wisdom: Measuring Misalignment between LLMs and Intended Impactcited by 2
  36. 2026Resource Consumption Threats in Large Language Modelscited by 2
  37. 2026Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformerscited by 2
  38. 2024On the Power of Decision Trees in Auto-Regressive Language Modelingcited by 1

50 most cited of 67 All 67 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study
  2. 2026Understanding the Emergence of Seemingly Useless Features in Next-Token Predictors
  3. 2026Modeling Next-Token Prediction as Left-Nested Intuitionistic Implication
  4. 2025Measuring In-Context Computation Complexity via Hidden State Prediction
  5. 2025The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner
  6. 2025Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits
  7. 2025Beyond Next-Token Prediction: A Performance Characterization of Diffusion versus Autoregressive Language Models
  8. 2026Beyond Token-Level Policy Gradients for Complex Reasoning with Large Language Models