Auto-Regressive Next-Token Predictors are Universal Learners

Eran Malach

RECORD

Auto-Regressive Next-Token Predictors are Universal Learners

Eran Malach

Machine Learning · Submitted 13 Sep 2023

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim 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.

how it is stated · asserted 0.92 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,610 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.12 · human participants 0.03 · controlled comparison 0.06 · randomized assignment 0.01 · states quantitative result 0.12 · compares with prior results 0.16 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v3. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Large language models display remarkable capabilities in logical and mathematical reasoning, allowing them to solve complex tasks.	background 1.00	0.09	0.03	asserted 1.00
s1	Interestingly, these abilities emerge in networks trained on the simple task of next-token prediction.	background 0.97	0.09	0.05	asserted 1.00
s2	In this work, we present a theoretical framework for studying auto-regressive next-token predictors.	contribution 0.96	0.91	0.03	asserted 0.89
s3	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.	result 0.94	0.94	0.62	asserted 1.00
s4	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.	contribution 0.95	0.95	0.05	asserted 0.99
s5	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.	result 0.97	0.95	0.07	asserted 1.00
s6	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.	interpretation 1.00	0.84	0.86	asserted 0.92

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.85.

What was examined, and what was not

sources read

arXiv listing abstract v3

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

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

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 13 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
cs.LG 2026-10 accept novelty 8.0 of 10

A single autoregressive neuron can simulate any feedforward circuit or Turing machine using a number of parameters and generation steps polynomial in the circuit size, independent of circuit depth.
When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning
cs.AI 2026-07 conditional novelty 7.0 of 10

When reflections localize early errors, in-context search solves exp-small pass-rate problems with poly sequential attempts; otherwise it offers no asymptotic gain over parallel sampling, and the update is learnable a...
The Power of Random Features and the Limits of Distribution-Free Gradient Descent
cs.LG 2025-05 reject novelty 7.0 of 10

Distribution-free learnability by bounded-precision mini-batch SGD implies approximability by a polynomial number of random features, up to a new complexity measure called average probabilistic dimension complexity.
Self-Improvement in Language Models: The Sharpening Mechanism
cs.AI 2024-12 conditional novelty 7.0 of 10

Self-improvement in language models can be understood as amortizing best-of-N inference-time selection, with minimax-optimal guarantees for SFT and provable coverage-free benefits for RL with exploration.
Information-Theoretic Analysis of Next-Token Prediction under Markovian Data
stat.ML 2026-09 conditional novelty 6.0 of 10

Generalization bounds for next-token prediction under Markovian data, with explicit scaling in context, mixing, model complexity, and margin, plus experiments showing longer contexts widen the train-test gap.

Show 8 more citing papers

Hierarchical Domain Generalization
cs.LG 2026-07 conditional novelty 6.0 of 10

Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
cs.LG 2026-01 conditional novelty 6.0 of 10

A GNN with an ensemble of MLPs can exactly execute any LOCAL-model graph algorithm after learning a polynomial-size set of local template instructions.
From Reasoning to Super-Intelligence: A Search-Theoretic Perspective
cs.AI 2025-07 conditional novelty 6.0 of 10

The Diligent Learner, a reverse-curriculum algorithm with explicit backtracking and a validator, is proven to learn chain-of-thought reasoning efficiently under two learnability assumptions, while standard methods fai...
Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction
cs.LG 2025-04 conditional novelty 6.0 of 10

On four minimal graph-construction tasks, multi-token training (teacherless or diffusion) produces more diverse and original outputs than next-token training, and random seed prefixes can replace temperature as a dive...
Learning Model Successors
cs.LG 2025-01 conditional novelty 6.0 of 10

A meta-learner that transforms a model for difficulty level k into a model for level k+1 can generalize far beyond its training range, demonstrated on a bracket-matching task.
Position: We Need An Algorithmic Understanding of Generative AI
cs.AI 2025-07 conditional novelty 5.0 of 10

The paper argues for a systematic algorithmic understanding of LLMs and presents a case study suggesting that Llama models do not implement BFS or DFS on graph navigation tasks.
Unraveling Arithmetic in Large Language Models: The Role of Algebraic Structures
cs.LG 2024-11 conditional novelty 5.0 of 10

LLMs can learn commutativity and identity properties of operations from input-output examples alone, generalizing to unseen permutations and identity insertions.
Position: A Theory of Deep Learning Must Include Compositional Sparsity
cs.LG 2025-07 conditional novelty 4.0 of 10

All polynomial-time computable functions are compositionally sparse, and this property is the proposed reason deep networks avoid the curse of dimensionality and achieve practical success.

How the literature uses it

35 arXiv papers cite this in 69 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 42 sentences without a confident label

Contests it 1 paper

We were directly inspired by the work of [ref] , and address what we view as its major deficiency, namely time dependence.

A Theory of Learning with Autoregressive Chain of Thought · Discussion and Future Directions · contest 0.79

Compares with it 1 paper

Combining the VC-dimension and cardinality-based sample complexities: $T$ is $$ and $$ learnable using [ref] and [ref] with sample complexities [equation] While we do not know if the $d^2$ vs. $d logT$ gap in the sample complexity (when $logT ≪d$) between $$ and $$ learning is real, it is clear that there remains a statistical advantage over learning the time-dependent $T$ [ref] , which requires $Ω(d ·T)$ samples.

A Theory of Learning with Autoregressive Chain of Thought · Autoregressive Linear Thresholds · 1.00

Cites it as support 4 papers

The advantage here, as pointed out by [ref] , is that we can consider Chain-of-Thought training as essentially providing us a peek into the inner working of the computation, and thus allowing computationally tractable learning.

A Theory of Learning with Autoregressive Chain of Thought · Expressivity and Universality · 1.00
But the good news is that for base generator classes that are tractable, learning to solve problems through autoregressive CoT is computationally tractable if, during training, we are given not only the final answer but the entire Chain-of-Thought leading to it [ref] ; see precise definitions in <Ref>.

Learning to Think from Multiple Thinkers · Introduction · 0.96
First, the next-word prediction objective provides a major benefit by virtue of its generality [ref] : almost any task can be cast in terms of next-word prediction, such that training a model on this task will also give it training on a wide range of other tasks [ref] .

Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve · Beneficial embers of autoregression · 1.00

Cites it as background 16 papers

This process was recently formalized by [ref] and [ref] , who studied both the expressive power and the learnability of such autoregressive systems.

Learning to Think from Multiple Thinkers · Introduction · 0.88
Theoretical results on composition: Previous works on multi-step function composition and subtask decomposition in language models primarily focus on expressing and learning a deterministic function that solves well defined mathematical tasks [ref] , such as solving the bit parity problem [ref] , expressing and learning Turing machines [ref] , composing a mathematical function arbitrary numbers of times [ref] , or simple mathematical operations on text [ref] .

Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective · Related Works · 0.99
The recent works of [ref] study the effect of CoT on the computational and statistical tractability of learning.

A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning · Related Work · 0.91

What it cites · 17 sentences without a confident label

Uses the method or tool of 1 paper

Similarly to [ref] , we use GPT-4 to grade 50 output examples based on grammar, creativity, consistency with the story’s beginning and whether the plot makes sense (see Appendix [ref] for further details).

TinyStories: How Small Can Language Models Be and Still Speak Coherent English? · Tiny Stories · 0.97

Uses data or values from 1 paper

We train a linear next-token prediction network on the TinyStories dataset [ref] , a collection of short stories composed of simple words.

TinyStories: How Small Can Language Models Be and Still Speak Coherent English? · Introduction · 0.98

Compares with 2 papers

In our study, we further substantiate this claim by demonstrating that a small MLP, devoid of any attention mechanism, can match the performance of the transformer in [ref] in 4-digit multiplication, provided that it receives appropriate intermediate supervision.

Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks · Related Work · 0.92
In addition, our results offer improved length complexity bounds for learning parities, indicating that parities can be learned using $O(logn)$ intermediate tokens, a marked reduction from the $O(n)$ intermediate tokens in [ref] .

Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks · Related Work · 0.96

Cites as support 1 paper

While this objective seems extremely simplistic, auto-regressive next-token predictors trained on rich enough data are able to solve strikingly complex tasks [ref] .

Sparks of Artificial General Intelligence: Early experiments with GPT-4 · Introduction · 1.00

Cites as background 11 papers

Recently, a paper by [ref] instrodced Goat, a relatively small transformer fine-tuned from the LLaMA model that was able to outperform GPT-4 in various arithmetic tasks, when trained on data with intermediate calculations.

Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks · Multiplication · 0.81
This idea became very popular with the introduction of the Chain-of-Thought (CoT) approach, where models are prompted to elucidate their thought process prior to yielding a final outcome [ref] .

Let's Verify Step by Step · Related Work · 0.92
These models, like GPT-3, GPT-4 and LaMDA [ref] , are trained on massive amounts of text data and learn to generate coherent and contextually relevant responses to input prompts.

LaMDA: Language Models for Dialog Applications · Introduction · 0.99

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.