# Auto-Regressive Next-Token Predictors are Universal Learners

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

## Key facts

- Cited by 72 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.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 39)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [MLP-Mixer: An all-MLP Architecture for Vision](https://mlsanity.com/paper/2105.01601/) (2021)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Language Modeling with Gated Convolutional Networks](https://mlsanity.com/paper/1612.08083/) (2016)
- [TinyStories: How Small Can Language Models Be and Still Speak Coherent English?](https://mlsanity.com/paper/2305.07759/) (2023)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Pay Attention to MLPs](https://mlsanity.com/paper/2105.08050/) (2021)
- [Solving General Arithmetic Word Problems](https://mlsanity.com/paper/1608.01413/) (2016)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Teaching Small Language Models to Reason](https://mlsanity.com/paper/2212.08410/) (2022)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Symbolic Chain-of-Thought Distillation: Small Models Can Also "Think" Step-by-Step](https://mlsanity.com/paper/2306.14050/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Explanations from Large Language Models Make Small Reasoners Better](https://mlsanity.com/paper/2210.06726/) (2022)
- [A Survey of Deep Learning for Mathematical Reasoning](https://mlsanity.com/paper/2212.10535/) (2022)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [An Attention Free Transformer](https://mlsanity.com/paper/2105.14103/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks](https://mlsanity.com/paper/2305.14201/) (2023)

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

- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve](https://mlsanity.com/paper/2309.13638/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction](https://mlsanity.com/paper/2504.15266/) (2025)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)
- [Mixture of Parrots: Experts improve memorization more than reasoning](https://mlsanity.com/paper/2410.19034/) (2024)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Truth-Aware Context Selection: Mitigating Hallucinations of Large Language Models Being Misled by Untruthful Contexts](https://mlsanity.com/paper/2403.07556/) (2024)
- [Continuous Latent Diffusion Language Model](https://mlsanity.com/paper/2605.06548/) (2026)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [Improving Length-Generalization in Transformers via Task Hinting](https://mlsanity.com/paper/2310.00726/) (2023)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [From Reasoning to Super-Intelligence: A Search-Theoretic Perspective](https://mlsanity.com/paper/2507.15865/) (2025)
- [Deep sequence models tend to memorize geometrically; it is unclear why](https://mlsanity.com/paper/2510.26745/) (2025)
- [Language Generation with Infinite Contamination](https://mlsanity.com/paper/2511.07417/) (2025)
- [Semformer: Transformer Language Models with Semantic Planning](https://mlsanity.com/paper/2409.11143/) (2024)
- [Learning Algorithms in the Limit](https://mlsanity.com/paper/2506.15543/) (2025)
- [Conditions for Length Generalization in Learning Reasoning Skills](https://mlsanity.com/paper/2311.16173/) (2023)
- [Models That Prove Their Own Correctness](https://mlsanity.com/paper/2405.15722/) (2024)

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