mlsanityData to 7 Oct 2026

Induction Heads Interpolate N-Grams

arXiv 2607.02800 ↗First posted 2 Jul 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Induction heads are attention circuits believed to underlie in-context learning in transformers, yet a precise characterization of the estimators they implement remains elusive. We study transformers trained on order-k Markov chains and identify two complementary smoothing mechanisms. First, at finite attention-weight scale, the circuit implements a soft context-matching estimator: it aggregates contributions from exact and partial context matches, weighted exponentially by their overlap, and induces a data-dependent interpolation across context orders analogous to Jelinek-Mercer smoothing. Second, a beginning-of-sequence (BOS) token induces additive pseudo-counts, recovering Dirichlet-style smoothing. We construct a disentangled transformer implementing both mechanisms and show that trained transformers recover the predicted attention patterns. Across settings where pseudo-count smoothing is optimal or lower-order contexts provide structured evidence, trained transformers match or outperform classical count-based baselines. Our results bridge mechanistic interpretability of induction heads with classical statistical smoothing, revealing that transformers learn to regularize in-context estimation rather than simply count.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 42 of its 52 references that are in the map. First posted on arXiv 2 Jul 2026.

Builds on

42 of 52 references.

References · 42

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  3. 2022Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?cited by 1,413
  4. 2022In-context Learning and Induction Headscited by 930
  5. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 915
  6. 2022Transformers learn in-context by gradient descentcited by 714
  7. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  8. 2023Towards Automated Circuit Discovery for Mechanistic Interpretabilitycited by 700
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  10. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  11. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  12. 2022Data Distributional Properties Drive Emergent In-Context Learning in Transformerscited by 303
30 more
  1. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  2. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
  3. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  4. 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 148
  5. 2023Pretraining task diversity and the emergence of non-Bayesian in-context learning for regressioncited by 138
  6. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 115
  7. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 114
  8. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 112
  9. 2023Uncovering mesa-optimization algorithms in Transformerscited by 94
  10. 2024What needs to go right for an induction head? A mechanistic study of in-context learning circuits and their formationcited by 86
  11. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  12. 2024Transformers represent belief state geometry in their residual streamcited by 73
  13. 2024Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cited by 60
  14. 2024Asymptotic theory of in-context learning by linear attentioncited by 54
  15. 2023Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regressioncited by 47
  16. 2024Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformerscited by 46
  17. 2023Pretraining Data Mixtures Enable Narrow Model Selection Capabilities in Transformer Modelscited by 45
  18. 2023Learning Transformer Programscited by 40
  19. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 39
  20. 2024Transformers Can Represent n-gram Language Modelscited by 31
  21. 2024Transformers on Markov Data: Constant Depth Sufficescited by 26
  22. 2025The emergence of sparse attention: impact of data distribution and benefits of repetitioncited by 25
  23. 2024Understanding Transformers via N-gram Statisticscited by 23
  24. 2024How do Transformers perform In-Context Autoregressive Learning?cited by 16
  25. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 15
  26. 2024On Limitation of Transformer for Learning HMMscited by 9
  27. 2025Selective Induction Heads: How Transformers Select Causal Structures In Contextcited by 7
  28. 2024Long-Context Linear System Identificationcited by 3
  29. 2025What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chainscited by 3
  30. 2026Transformers Learn Latent Mixture Models In-Context via Mirror Descentcited by 1

Built on by

Not cited yet.