mlsanityData to 14 Oct 2026

An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains

arXiv 2410.05493 ↗First posted 7 Oct 2024cs.LG cs.IT math.ITcited by 3

Not on the map. Why?

Abstract (arXiv)

We study transformers' in-context learning of variable-length Markov chains (VOMCs), focusing on the finite-sample accuracy as the number of in-context examples increases. Compared to fixed-order Markov chains (FOMCs), learning VOMCs is substantially more challenging due to the additional structural learning component. The problem is naturally suited to a Bayesian formulation, where the context-tree weighting (CTW) algorithm, originally developed in the information theory community for universal data compression, provides an optimal solution. Empirically, we find that single-layer transformers fail to learn VOMCs in context, whereas transformers with two or more layers can succeed, with additional layers yielding modest but noticeable improvements. In contrast to prior results on FOMCs, attention-only networks appear insufficient for VOMCs. To explain these findings, we provide explicit transformer constructions: one with D+2 layers that can exactly implement CTW for VOMCs of maximum order D, and a simplified two-layer construction that uses partial information for approximate blending, shedding light on why two-layer transformers can perform well.

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

Builds on

21 of 52 references.

References · 21

  1. 2017Attention Is All You Needcited by 60,361
  2. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 938
  3. 2022Transformers learn in-context by gradient descentcited by 732
  4. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  5. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  6. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 298
  7. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 279
  8. 2023Language Modeling Is Compressioncited by 225
  9. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 222
  10. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  11. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 118
  12. 2023The mechanistic basis of data dependence and abrupt learning in an in-context classification taskcited by 118
9 more
  1. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 118
  2. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  3. 2022General-Purpose In-Context Learning by Meta-Learning Transformerscited by 105
  4. 2024In-Context Language Learning: Architectures and Algorithmscited by 89
  5. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 40
  6. 2024Transformers on Markov Data: Constant Depth Sufficescited by 27
  7. 2020Bayesian Context Trees: Modelling and exact inference for discrete time seriescited by 13
  8. 2024Can Transformers Learn n-gram Language Models?cited by 11
  9. 2024On Limitation of Transformer for Learning HMMscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Informationcited by 2
  2. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 2
  3. 2026Learning Source Structure: Bayesian Prediction with Transformerscited by 0