Research map / Learning theory and algorithms / Sample complexity
In-context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation
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.
Shows that deep linear transformers with O(log T) depth can in-context approximate least-squares prediction for noisy 1D/d-dim linear dynamical systems with error O(log T / T), while single-layer linear transformers suffer a non-vanishing lower bound, indicating depth separation.
Problem
Approximation power of transformers for in-context learning of noisy linear dynamical systems (non-IID data), including how depth affects the uniform L2 test loss as sequence length T grows.
Approach
Construct a deep linear transformer that unrolls modified Richardson iteration to solve the sample-covariance linear system, yielding the least-squares one-step predictor; and prove a non-vanishing lower bound for single-layer linear attention on 1D systems via limiting loss computation.
Key results
- Theorem: an O(log T)-depth linear transformer achieves uniform test loss O(log(T)/T) for noisy linear dynamical systems.
- Single-layer linear attention on 1D systems has limiting test loss lower bounded by a positive constant C(sigma^2, w_min, w_max) independent of parameter norm bound R.
- Experiments (d=1, T=500) show a clear loss gap between depth L=1 and L>=2 for both softmax and linear transformers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a deep linear transformer with depth O(log(T)) instead of a single-layer transformer | In-context learning of noisy linear dynamical systems · Noisy linear dynamical systems | L² test loss: O\left(\frac{\log(T)}{T} \right) | Helped |
| Use a single-layer linear attention block | In-context learning of 1D noisy linear dynamical systems · 1D noisy linear dynamical systems | L² test loss: C(\sigma^2,w_{\min},w_{\max}) > 0 | Hurt |
| Increase softmax transformer depth beyond L =2 | Softmax transformers learning noisy 1D linear dynamical systems · Noisy 1D linear dynamical systems (T = 500) | test error | Helped |
| Increase linear transformer depth from L = 2 to L = 3, 4, or 5 | Linear transformers learning noisy 1D linear dynamical systems · Noisy 1D linear dynamical systems (T = 500) | test error | No clear effect |
| Use a single-layer linear attention transformer rather than a deeper transformer | Transformers learning noisy 1D linear dynamical systems · Noisy 1D linear dynamical systems (T = 500) | test error | Hurt |
Surprising findings
- Linear transformers' optimal loss is roughly the same at depths 2 through 5, suggesting the O(log T) depth bound may be suboptimal and constant depth might suffice.
Limitations
- Lower bound proved only for single-layer linear attention with fixed MLP identity and 1D systems.
- Upper bound depth O(log T) may be suboptimal; constant-depth existence is open.
- Approximation only; does not show trained transformers learn the system.
Experimental setup
Datasets: synthetic noisy linear dynamical systems
Benchmarks: synthetic 1D linear dynamical systems (T=500, w in [0,0.8])
Metrics: L2 test loss test error vs epochs
Baselines: softmax transformers least-squares estimator
Builds on: mesa-optimization hypothesis linear transformers implement gradient descent Richardson iteration
Closest papers by meaning
- Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions (NeurIPS 2025 · similarity 0.90)
- In-context Learning on Function Classes Unveiled for Transformers (ICML 2024 · similarity 0.89)
- In-context Convergence of Transformers (ICML 2024 · similarity 0.88)
- Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression (NeurIPS 2024 · similarity 0.88)
- In-Context Learning of a Linear Transformer Block: Benefits of the MLP Component and One-Step GD Initialization (NeurIPS 2024 · similarity 0.87)
- Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? (ICML 2024 · similarity 0.86)
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.