Research map / Architectures and efficiency / Attention and transformers
Local to Global: Learning Dynamics and Effect of Initialization for Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically shows that 2-layer transformers (with RoPE or relative position encodings) can represent k-th order Markov chain in-context counting (k-gram estimators), and that transformers without position encodings cannot match Bayes-optimal k-th order predictions.
Problem
How transformers learn Markov chains in-context: what architectures can represent k-th order Markov (k-gram) predictors, and how position encodings affect this capability.
Approach
Constructs explicit transformer weights that implement k-gram counting via attention with large-scale (kappa to infinity) induction-head-like attention patterns, using RoPE or relative position encodings; shows that without position encodings the attention is permutation invariant and cannot reach Bayes-optimal k-th order prediction.
Key results
- Bigram counting and trigram counting are representable by 2-layer, 1-head transformers via attention with kappa-to-infinity induction-head patterns.
- k-th order counting is representable by a 2-layer transformer with RoPE; relative position encodings achieve it with ceil(log(k+1))+2 layers and 2 heads per layer.
- Transformers without position encodings cannot represent the Bayes-optimal k-th order chain predictor for any k>1 (permutation invariance argument).
Limitations
- Constructions rely on the limit kappa to infinity, so attention becomes hard and approximations are only asymptotic.
- The shown proof of the main theorem is incomplete (e.g., trailing unfinished derivations in the excerpt).
- The no-position-encoding impossibility lemma is only sketched in the excerpt.
Experimental setup
Builds on: induction head RoPE
Closest papers by meaning
- Transformers on Markov data: Constant depth suffices (NeurIPS 2024 · similarity 0.89)
- What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains (NeurIPS 2025 · similarity 0.89)
- Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions (NeurIPS 2025 · similarity 0.89)
- Non-asymptotic Convergence of Training Transformers for Next-token Prediction (NeurIPS 2024 · similarity 0.88)
- How do Transformers Perform In-Context Autoregressive Learning ? (ICML 2024 · similarity 0.88)
- Dynamical Properties of Tokens in Self-Attention and Effects of Positional Encoding (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.