Research map / Large language models / Reasoning and chain of thought
Auto-Regressive Next-Token Predictors are Universal Learners
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically that linear auto-regressive next-token predictors trained on chain-of-thought data can approximate any Turing-computable function, introduces length complexity, and experimentally trains a linear model on TinyStories and a 775M-parameter attention-free MLP on 4-digit multiplication.
Problem
Understanding why next-token prediction with chain-of-thought yields powerful reasoning, and how much of this power comes from the auto-regressive training scheme versus the architecture; classical supervised learning cannot efficiently learn many complex functions without intermediate supervision.
Approach
Auto-regressive learning turns intermediate CoT tokens into supervised labels, and the argmax sampling step acts as a non-linearity, so linear next-token predictors can compute linear threshold circuits and hence any efficiently Turing-computable function. The paper also defines length complexity, the number of intermediate CoT tokens needed, and shows it trades off against sample and computationa
Key results
- A 775M-parameter attention-free MLP trained on CoT data matches the per-digit/exact-match performance of the fine-tuned 7B Goat model on 4-digit multiplication and outperforms GPT-3.5 and GPT-4 on that task.
- A small 70M transformer trained with the same tokenization and CoT scheme reached only 72% per-digit accuracy, below the MLP.
- Linear AR models can compute any linear threshold circuit, and so any efficiently Turing-computable function with polynomial blow-up; parities are computable with O(log n) length complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train a next-token MLP with CoT multiplication examples | MLP · 4-digit multiplication validation | exact-match accuracy | Helped |
| Train a next-token MLP with CoT multiplication examples | MLP · 4-digit multiplication validation | per-digit accuracy | No clear effect |
| Use a 70M transformer instead of the MLP, retaining the tokenization and CoT scheme | 4-digit multiplication · 4-digit multiplication validation | per-digit accuracy | Hurt |
| Train a linear next-token predictor on TinyStories | Linear model · TinyStories | story generation quality | Helped |
Surprising findings
- A small transformer (70M) trained with the same scheme performs worse than the attention-free MLP on multiplication.
- The linear TinyStories model still produces often grammatical stories despite having no nonlinearity beyond argmax-based sampling.
Limitations
- Linear TinyStories model is not exactly the idealized linear AR model; it shares embedding parameters across positions.
- Theoretical results require long CoT sequences, which may be impractical to obtain; the length complexity can be large.
- Experiments are limited to a single arithmetic task and a small synthetic story dataset; GPT-4 grading is a rough proxy for quality.
Experimental setup
Datasets: TinyStories 4-digit multiplication CoT data
Benchmarks: TinyStories 4-digit multiplication
Metrics: GPT-4 grades (grammar, creativity, consistency, plot) LanguageTool grammar error-free rate exact match accuracy per-digit accuracy
Baselines: GPT-3.5 GPT-4 Goat-7B small transformer (70M)
Builds on: PAC learning chain-of-thought scratchpad Goat
Closest papers by meaning
- Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction (ICML 2025 · similarity 0.88)
- The Pitfalls of Next-Token Prediction (ICML 2024 · similarity 0.88)
- On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study (NeurIPS 2025 · similarity 0.88)
- How reinforcement learning after next-token prediction facilitates learning (ICLR 2026 · similarity 0.88)
- Measuring In-Context Computation Complexity via Hidden State Prediction (ICML 2025 · similarity 0.88)
- On the Generalization Ability of Next-Token-Prediction Pretraining (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.