Research map / Architectures and efficiency / Attention and transformers
When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective
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.
Proves a statistical (sample complexity) separation showing single-layer Transformers learn q-sparse token regression with N-independent sample complexity when heads H≥q, while RNNs need N^Ω(1) samples for general qSTR and FFNs need Ω(N) even for simple-qSTR.
Problem
Which function classes can Transformers learn with fewer samples than feedforward and recurrent networks, even with infinite compute, and how does sample complexity scale with sequence length N?
Approach
Introduces the q-sparse token regression (qSTR) model where each output depends on q input tokens whose positions are given in the prompt (dynamic sparsity); shows attention adapts to this via retrieval, while FFNs and RNNs lack this adaptivity, giving a sample complexity hierarchy, using covering-number bounds for Transformers and metric-entropy/norm-based lower bounds for RNNs and FFNs.
Key results
- Single-layer Transformer with H ≥ q heads achieves sample complexity almost independent of N (up to polylog factors) for qSTR, and cannot learn qSTR with H < q even with infinite samples.
- RNNs learn simple-qSTR with polylog(N) samples but require N^Ω(1) samples for general qSTR; min-norm ERM RNNs fail when n ≤ N^c1.
- FFNs require Ω(Nd) samples to learn even simple-1STR regardless of width; experiments show FFN and RNN sample complexity grows with N on 1STR while Transformers remain milder.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use an FFN or RNN instead of a Transformer | 1STR · 1STR; varying sequence length N | sample complexity | Hurt |
| use an RNN instead of an FFN | simple-1STR · simple-1STR; varying sequence length N | sample complexity | Helped |
Surprising findings
- Even for simple-qSTR, feedforward networks need sample complexity linear in N regardless of width, while RNNs do not.
Limitations
- Optimization dynamics of Transformers learning qSTR are not analyzed; the sample complexity bound is not shown to be achieved by gradient descent.
- Upper bounds use norm-constrained ERM and a single-layer Transformer; depth-based separations are left for future work.
- Lower bounds for RNNs rely on a subexponential weight-norm restriction and n ≤ N^c1.
Experimental setup
Datasets: synthetic qSTR / simple-1STR data
Benchmarks: synthetic 1STR and simple-1STR tasks
Metrics: test MSE sample complexity to reach loss threshold
Baselines: feedforward networks recurrent neural networks
Builds on: Sanford et al. 2023 sparse averaging separation covering number bounds for Transformers Maurey sparsification
Closest papers by meaning
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.89)
- On the Optimal Memorization Capacity of Transformers (ICLR 2025 · similarity 0.88)
- Approximation Rate of the Transformer Architecture for Sequence Modeling (NeurIPS 2024 · similarity 0.88)
- Beyond Attention: Breaking the Limits of Transformer Context Length with Recurrent Memory (AAAI 2024 · similarity 0.88)
- Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling (NeurIPS 2024 · similarity 0.87)
- Two Heads are Better than One: Simulating Large Transformers with Small Ones (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.