mlsanityData to 7 Oct 2026

Transformers Can Represent n-gram Language Models

arXiv 2404.14994 ↗First posted 23 Apr 2024cs.CL cs.AI cs.CCcited by 31

Not on the map. Why?

Abstract (arXiv)

Existing work has analyzed the representational capacity of the transformer architecture by means of formal models of computation. However, the focus so far has been on analyzing the architecture in terms of language acceptance. We contend that this is an ill-suited problem in the study of language models (LMs), which are definitionally probability distributions over strings. In this paper, we focus on the relationship between transformer LMs and n-gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any n-gram LM, giving us a concrete lower bound on their probabilistic representational capacity. This provides a first step towards understanding the mechanisms that transformer LMs can use to represent probability distributions over strings.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 22 of its 50 references that are in the map. First posted on arXiv 23 Apr 2024.

Builds on

22 of 50 references.

References · 22

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022In-context Learning and Induction Headscited by 930
  3. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 915
  4. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 337
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  7. 2021Thinking Like Transformerscited by 182
  8. 2017Breaking the Softmax Bottleneck: A High-Rank RNN Language Modelcited by 147
  9. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  10. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  11. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  12. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
10 more
  1. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  2. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  3. 2020A Formal Hierarchy of RNN Architecturescited by 61
  4. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  5. 2019Sequential Neural Networks as Automatacited by 54
  6. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 32
  7. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  8. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  9. 2018Context-Free Transductions with Neural Stackscited by 14
  10. 2017Subregular Complexity and Deep Learningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 10; 2025: 13; 2026: 8.

31 papers.

Sort:

By area:

  1. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  2. 2024Understanding Transformers via N-gram Statisticscited by 23
  3. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  4. 2025Learning curves theory for hierarchically compositional data with power-law distributed featurescited by 17
  5. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  6. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 15
  7. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  8. 2024Beyond Scaling Laws: Understanding Transformer Performance with Associative Memorycited by 12
  9. 2024Can Transformers Learn n-gram Language Models?cited by 11
  10. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  11. 2025Evolution of Concepts in Language Model Pre-Trainingcited by 8
  12. 2025Selective Induction Heads: How Transformers Select Causal Structures In Contextcited by 7
19 more
  1. 2025Bigram Subnetworks: Mapping to Next Tokens in Transformer Language Modelscited by 5
  2. 2025Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architecturescited by 5
  3. 2024Jet Expansions of Residual Computationcited by 4
  4. 2024Neural Networks Generalize on Low Complexity Datacited by 3
  5. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  6. 2024A Transformer with Stack Attentioncited by 2
  7. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  8. 2024Representing Rule-based Chatbots with Transformerscited by 1
  9. 2025Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learningcited by 1
  10. 2025From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modelingcited by 1
  11. 2025Towards Understanding Transformers in Learning Random Walkscited by 1
  12. 2026PixRec: Leveraging Visual Context for Next-Item Prediction in Sequential Recommendationcited by 1
  13. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 1
  14. 2026Transformers Learn Latent Mixture Models In-Context via Mirror Descentcited by 1
  15. 2026An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammarscited by 1
  16. 2026Space-Efficient Language Generation in the Limitcited by 1
  17. 2026A theoretical model for task routing in mixture-of-expert transformerscited by 0
  18. 2026Induction Heads Interpolate N-Gramscited by 0
  19. 2026Disentangling the Expressivity of RoPEcited by 0