Research map / Architectures and efficiency / Attention and transformers
Approximation Rate of the Transformer Architecture for Sequence Modeling
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.
Derives Jackson-type approximation rates for a single-layer, single-head Transformer on general continuous sequence-to-sequence targets, using POD-based complexity measures of the temporal coupling, and compares Transformers with RNNs on temporal ordering and mixing.
Problem
Theoretical understanding of which sequence-to-sequence relationships a Transformer can approximate efficiently, and how its approximation capacity compares to RNNs under changes in temporal structure.
Approach
Establishes a representation theorem writing any continuous sequence target as a softmax-attention form with pairwise coupling rho and pointwise f, F; defines complexity measures based on POD singular-value decay of rho (plus feed-forward approximation budgets) and proves an explicit Jackson-type rate in which the attention head dimension m_h trades off POD truncation error against feed-forward ap
Key results
- ViT on CIFAR10 with altered (permuted) temporal ordering reaches 0.96 accuracy versus 0.98 for original; Transformer BLEU on WMT14 En-De drops from 26.85 to 25.91 under permutation.
- On a linear temporal-mixing task, RNN MSE rises from 1.02e-7 to 3.57e-2 under temporal ordering change while Transformer MSE is stable at about 2.18e-5 to 2.51e-5.
- Training error of ViT attention decreases with head dimension m_h following an approximate power law O(1/m_h^0.27).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Permute the input dataset while keeping outputs unchanged | Transformer · CIFAR10 | accuracy: 0.98 -> 0.96 | No clear effect |
| Permute the input dataset while keeping outputs unchanged | Transformer · ENG-DE | BLUE: 26.85 -> 25.91 | No clear effect |
| Alter temporal ordering | RNN · Synthetic linear target, temporal ordering | MSE: 1.02e{-7} -> 3.57e{-2} | Hurt |
| Alter temporal ordering | Transformer · Synthetic linear target, temporal ordering | MSE: 2.18e{-5} -> 2.51e{-5} | No clear effect |
| Convolve the input with a randomly generated filter | RNN · Synthetic linear target, temporal mixing | MSE: 1.02e{-7} -> 1.58e{-7} | No clear effect |
| Convolve the input with a randomly generated filter | Transformer · Synthetic linear target, temporal mixing | MSE: 2.18e{-5} -> 2.39e{-4} | Hurt |
Surprising findings
- Transformer performance is essentially unchanged by permuting temporal order of targets, while RNN performance collapses, showing neither architecture dominates.
- Temporal mixing of inputs degrades Transformer performance (MSE 2.18e-5 to 2.39e-4) while RNN is unaffected.
Limitations
- Analysis restricted to single-layer, single-head Transformers without layer normalization or residual connections.
- Sequence length fixed (finite tau); extension to multi-head and deep Transformers left for future work.
- Real-world validation is only indirect (training error as proxy for approximation error).
Experimental setup
Datasets: CIFAR10 WMT2014 English-German synthetic sequence targets
Benchmarks: CIFAR10 WMT2014 English-German synthetic temporal ordering and mixing targets
Metrics: accuracy BLEU MSE training error
Baselines: RNN linear RNN
Builds on: Jackson theorem Eckart-Young theorem Kolmogorov representation theorem
Closest papers by meaning
- Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling (NeurIPS 2024 · similarity 0.92)
- When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective (NeurIPS 2025 · similarity 0.88)
- Prompting a Pretrained Transformer Can Be a Universal Approximator (ICML 2024 · similarity 0.87)
- Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? (ICLR 2024 · similarity 0.87)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.87)
- A unified framework for establishing the universal approximation of transformer-type architectures (NeurIPS 2025 · similarity 0.87)
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.