mlsanityData to 14 Oct 2026

Can Transformers Learn n-gram Language Models?

arXiv 2410.03001 ↗First posted 3 Oct 2024cs.CLcited by 11

Not on the map. Why?

Abstract (arXiv)

Much theoretical work has described the ability of transformers to represent formal languages. However, linking theoretical results to empirical performance is not straightforward due to the complex interplay between the architecture, the learning algorithm, and training data. To test whether theoretical lower bounds imply learnability of formal languages, we turn to recent work relating transformers to n-gram language models (LMs). We study transformers' ability to learn random n-gram LMs of two kinds: ones with arbitrary next-symbol probabilities and ones where those are defined with shared parameters. We find that classic estimation techniques for n-gram LMs such as add-λ smoothing outperform transformers on the former, while transformers perform better on the latter, outperforming methods specifically designed to learn n-gram LMs.

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

Builds on

18 of 36 references.

References · 18

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  4. 2017Decoupled Weight Decay Regularizationcited by 1,831
  5. 2022In-context Learning and Induction Headscited by 964
  6. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 341
  7. 2022Neural Networks and the Chomsky Hierarchycited by 217
  8. 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 153
  9. 2023Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMscited by 124
  10. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 118
  11. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  12. 2023Neurons in Large Language Models: Dead, N-gram, Positionalcited by 88
6 more
  1. 2024Transformers Can Represent n-gram Language Modelscited by 32
  2. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  3. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  4. 2020Efficient Computation of Expectations under Spanning Tree Distributionscited by 11
  5. 2021Revisiting Simple Neural Probabilistic Language Modelscited by 10
  6. 2024The Role of n-gram Smoothing in the Age of Neural Networkscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 7; 2026: 3.

11 papers.

  1. 2025Learning curves theory for hierarchically compositional data with power-law distributed featurescited by 17
  2. 2025Better Estimation of the Kullback--Leibler Divergence Between Language Modelscited by 11
  3. 2025Mechanistic Indicators of Understanding in Large Language Modelscited by 8
  4. 2025Bigram Subnetworks: Mapping to Next Tokens in Transformer Language Modelscited by 5
  5. 2025Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architecturescited by 5
  6. 2024An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chainscited by 3
  7. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  8. 2025From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modelingcited by 1
  9. 2026Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don'tcited by 1
  10. 2026Disentangling the Expressivity of RoPEcited by 1
  11. 2026Causally Evaluating the Learnability of Formal Language Taskscited by 0