Research map / Architectures and efficiency / Attention and transformers
Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
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.
Studies in-context learning of binary Markov chain dynamics with linear self-attention, deriving global minimizers in a reparameterized space, proving NP-hardness of recovering 1-layer LSA parameters, and interpreting multilayer LSA forward passes as preconditioned multi-objective optimization.
Problem
Understanding how transformers perform in-context learning when the in-context examples are Markov chain trajectories governed by a shared transition kernel, a setting beyond i.i.d. linear regression ICL.
Approach
Reparameterize the single-layer linear self-attention objective into a strictly convex problem over an enlarged parameter space with closed-form minimizer, show mapping back to actual transformer parameters is NP-hard via reduction from bilinear separability, and interpret multilayer LSA forward passes as preconditioned gradient descent on multiple objectives.
Key results
- For a 3-state-space setting, mean accuracy of a 1-layer LSA was 0.55 versus 0.98 for a 3-layer LSA.
- Accuracy gap between the reparameterized least-squares model and 1-layer LSA grows as dimension d increases from 1 to 10.
- Trained GPT-2 transformers of small/standard size perform comparably to SVM and logistic regression on Markov ICL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase LSA depth from 1 layer to 3 layers | LSA · Markovian prompts, |S|=3 | mean accuracy: 0.55 -> 0.98 | Helped |
| Use dense rather than sparse P,Q parameter matrices (ablation) | single-layer LSA · Length-2 Markov chains | training loss | No clear effect |
| Increase depth from 1 to 3 layers | LSA · Markovian prompts with state-space sizes 2, 3, and 4 | accuracy | Helped |
| Increase depth beyond the initial layers | 10-layer LSA in the restricted parameter space · 100 in-context Markov chains of length 5 | objective values | Mixed |
| Use the reparameterized model instead of 1-layer LSA | Markovian dynamics prediction · Binary Markov chains as dimension d increases | accuracy | Helped |
| Increase Markov-chain dimension | 1-layer LSA relative to the reparameterized model · Binary Markov chains | accuracy gap | Hurt |
| Use small or standard GPT-2 configurations instead of the tiny configuration | GPT-2-based transformers · Markovian prompts with independent and correlated initial states | test accuracy | Helped |
| Use trained small or standard transformers instead of 3-NN | Markovian next-token prediction · Markovian prompts with independent and correlated initial states | test accuracy | Helped |
Surprising findings
- Dense (non-sparse) optimal parameters for Markov ICL contrast with the sparse optimum found for i.i.d. linear regression ICL.
- Multilayer LSA training shows that beyond a certain depth, all objective values increase together rather than improving.
Limitations
- Theory restricted to single-layer linear attention (no softmax) and first-order binary Markov chains.
- Real-world dynamics may involve higher-order dependencies beyond Markov assumptions.
- Results on deeper and nonlinear transformers are only empirical.
Experimental setup
Datasets: synthetic binary Markov chains
Benchmarks: synthetic Markov chain ICL prompts
Metrics: accuracy mean squared error generational distance
Baselines: logistic regression linear regression 3-nearest neighbors support vector machine reparameterized least-squares model
Builds on: linear self-attention ICL theory (preconditioned gradient descent) reparameterization of LSA objective for linear regression
Closest papers by meaning
- Pretrained Transformer Efficiently Learns Low-Dimensional Target Functions In-Context (NeurIPS 2024 · similarity 0.90)
- In-context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation (NeurIPS 2025 · similarity 0.90)
- In-context Convergence of Transformers (ICML 2024 · similarity 0.89)
- Technical Debt in In-Context Learning: Diminishing Efficiency in Long Context (NeurIPS 2025 · similarity 0.89)
- Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions (ICLR 2024 · similarity 0.89)
- How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations (ICLR 2024 · similarity 0.89)
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.