Auto-Regressive Next-Token Predictors are Universal Learners

2023/09/13 by Eran Malach, Malach, Eran · 2 voices · 12 citations
Computer Science · #Machine Learning and Data Classification #Natural Language Processing Techniques #Topic Modeling #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2309.06979

openalex publication_date 2023/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Planning with Transformers: Chain of Computation and Structured Context Windows
• Position: We Need An Algorithmic Understanding of Generative AI
• Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction
• Knowledge without Wisdom: Measuring Misalignment between LLMs and Intended Impact
• Artificial or Just Artful? Do LLMs Bend the Rules in Programming?
• Provable Long-Range Benefits of Next-Token Prediction
• Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
• Can Language Models Compose Skills In-Context?
• Correlation Dimension of Auto-Regressive Large Language Models
• To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
• On efficiently computable functions, deep networks and sparse compositionality
• Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression

Discussions

• Auto-Regressive Next-Token Predictors Are Universal Learners [hn, 93 points, 13 comments]
• 📝 Auto-Regressive Next-Token Predictors Are Universal Learners 🧠📚 "Presents a theoretical framework for studying auto-regressive next-token predictors and show theoretically that even simple models [mastodon, 0 points, 0 comments]

Related

• Provable Long-Range Benefits of Next-Token Prediction
• How Reinforcement Learning After Next-Token Prediction Facilitates Learning
• On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study
• I Predict Therefore I Am: Is Next Token Prediction Enough to Learn Human-Interpretable Concepts from Data?
• Your LLM Knows the Future: Uncovering Its Multi-Token Prediction Potential