mlsanityData to 14 Oct 2026

Next-token prediction capacity: general upper bounds and a lower bound for transformers

arXiv 2405.13718 ↗First posted 22 May 2024cs.LG math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

Given a sequence of tokens, such as words, the task of next-token prediction is to predict the next-token conditional probability distribution. Decoder-only transformers have become effective models for this task, but their properties are still not fully understood. In particular, the largest number of distinct context sequences that a decoder-only transformer can interpolate next-token distributions for has not been established. To fill this gap, we prove upper and lower bounds on this number, which are equal up to a multiplicative constant. We prove these bounds in the general setting where next-token distributions can be arbitrary as well as the empirical setting where they are calculated from a finite number of document sequences. Our lower bounds are for one-layer multi-head decoder-only transformers and our proofs highlight an important injectivity property satisfied by self-attention. Furthermore, we provide numerical evidence that the minimal number of parameters for memorization is sufficient for being able to train the model to the entropy lower bound.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 22 of its 59 references that are in the map. First posted on arXiv 22 May 2024.

Builds on

22 of 59 references.

References · 22

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  4. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  5. 2023TinyStories: How Small Can Language Models Be and Still Speak Coherent English?cited by 449
  6. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  7. 2016Long Short-Term Memory-Networks for Machine Readingcited by 161
  8. 2023Representational Strengths and Limitations of Transformerscited by 133
  9. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  10. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  11. 2023Transformers as Support Vector Machinescited by 74
  12. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
10 more
  1. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  2. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  3. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
  4. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 40
  5. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  6. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  7. 2024Mechanics of Next Token Prediction with Self-Attentioncited by 34
  8. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 33
  9. 2024Provably learning a multi-head attention layercited by 21
  10. 2023Memory capacity of two layer neural networks with smooth activationscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 4.

11 papers.

  1. 2024Understanding Factual Recall in Transformers via Associative Memoriescited by 51
  2. 2024Implicit Geometry of Next-token Prediction: From Language Sparsity Patterns to Model Representationscited by 24
  3. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  4. 2025Reasoning Bias of Next Token Prediction Trainingcited by 3
  5. 2025Exact Sequence Interpolation with Transformerscited by 2
  6. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  7. 2026Can Unified Generation and Understanding Models Maintain Semantic Equivalence Across Different Output Modalities?cited by 1
  8. 2026Beyond the Prompt in Large Language Models: Comprehension, In-Context Learning, and Chain-of-Thoughtcited by 1
  9. 2024Memorization Capacity for Additive Fine-Tuning with Small ReLU Networkscited by 0
  10. 2026TULIP: Targeted LLM Unlearning at Layers Identified Per-Inputcited by 0
  11. 2026Information-Theoretic Analysis of Next-Token Prediction under Markovian Datacited by 0