# Can Transformers Learn n-gram Language Models?

arXiv: https://arxiv.org/abs/2410.03001 · HTML: https://mlsanity.com/paper/2410.03001/

## 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 (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens](https://mlsanity.com/paper/2401.17377/) (2024)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Neurons in Large Language Models: Dead, N-gram, Positional](https://mlsanity.com/paper/2309.04827/) (2023)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Efficient Computation of Expectations under Spanning Tree Distributions](https://mlsanity.com/paper/2008.12988/) (2020)
- [Revisiting Simple Neural Probabilistic Language Models](https://mlsanity.com/paper/2104.03474/) (2021)
- [The Role of n-gram Smoothing in the Age of Neural Networks](https://mlsanity.com/paper/2403.17240/) (2024)

## Built on by (most cited first, 11 of 11)

- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Better Estimation of the Kullback--Leibler Divergence Between Language Models](https://mlsanity.com/paper/2504.10637/) (2025)
- [Mechanistic Indicators of Understanding in Large Language Models](https://mlsanity.com/paper/2507.08017/) (2025)
- [Bigram Subnetworks: Mapping to Next Tokens in Transformer Language Models](https://mlsanity.com/paper/2504.15471/) (2025)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains](https://mlsanity.com/paper/2410.05493/) (2024)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modeling](https://mlsanity.com/paper/2505.12381/) (2025)
- [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026)
- [Disentangling the Expressivity of RoPE](https://mlsanity.com/paper/2608.11909/) (2026)
- [Causally Evaluating the Learnability of Formal Language Tasks](https://mlsanity.com/paper/2606.09822/) (2026)

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