Research map / Architectures and efficiency / Attention and transformers
Do Efficient Transformers Really Save Computation?
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 Sparse and Linear Transformers can express general dynamic-programming chain-of-thought reasoning but need hidden dimension growing with problem size (Ω̃(√L)), while locality in reasoning steps restores efficiency; validated on Arithmetic, LIS, and Edit Distance experiments.
Problem
Whether efficient Transformers (Sparse and Linear) truly reduce computation relative to standard Transformers when performing chain-of-thought reasoning modeled as dynamic programming.
Approach
Theoretically shows that efficient Transformers need hidden dimension growing with output length for general DP problems (via an information-bottleneck argument under log-precision), and identifies an m-locality condition under which Sparse Transformers achieve Õ(mL) complexity with constant hidden dimension, validated empirically on Arithmetic, LIS, and ED.
Key results
- Sparse and Linear Transformers need hidden dimension Ω̃(√L) for regular general DP problems with L=Θ(n), giving complexity Ω̃(L²), matching standard Transformers asymptotically.
- For the Arithmetic task, a constant-dimension log-precision Sparse Transformer can solve the task, yielding O(L√L) complexity; Linear Transformer lower bound is Ω̃(L√L).
- Experiments show efficient Transformers need larger embedding dimensions as problem size grows, while standard Transformers handle all sizes with dimension 128 or 256; in Table, Standard requires 0.027-0.605 GFLOPs vs Sparse 0.106-2.399 and Linear 0.422-9.584 on Arithmetic.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Linear Transformer instead of Standard Transformer | Arithmetic task · Arithmetic, Length 87, 221, 355, and 505 | GFLOPs: 0.027 vs 0.422; 0.266 vs 4.220; 0.426 vs 6.756; 0.605 vs 9.584 | Hurt |
| Use Sparse Transformer instead of Linear Transformer | Arithmetic task · Arithmetic, Length 87, 221, 355, and 505 | GFLOPs: 0.422 vs 0.106; 4.220 vs 1.055; 6.756 vs 1.690; 9.584 vs 2.399 | Helped |
| Increase problem size | Sparse Transformer and Linear Transformer · Arithmetic, ED, and LIS | required embedding dimension | Hurt |
| Use fixed embedding dimensions of 128 or 256 | Standard Transformer · Arithmetic, ED, and LIS | accuracy | Helped |
| Increase locality by modifying ED to ED_Local | Sparse Transformer and Linear Transformer · ED_Local | required embedding dimension | Helped |
Surprising findings
- Efficient Transformers, despite lower asymptotic complexity, need hidden dimensions growing with problem size on general DP tasks, so their efficiency advantage largely disappears.
- Standard Transformers required the fewest FLOPs across all Arithmetic lengths, even though Sparse and Linear have lower asymptotic complexity.
Limitations
- Results only cover representative Sparse and Linear Transformer designs and may not transfer to other efficient architectures.
- Linear Transformer complexity lower bound Ω̃(mL) is not shown to be tight; open question.
- Experiments use small synthetic DP tasks with 3-5 layer models trained from scratch.
Experimental setup
Datasets: Arithmetic expression evaluation (synthetic) Longest Increasing Subsequence (synthetic) Edit Distance (synthetic) ED_Local (synthetic, higher locality)
Benchmarks: Arithmetic LIS ED
Metrics: final answer accuracy minimum GFLOPs to reach 90% accuracy
Baselines: Standard Transformer Linear Transformer Sparse Transformer
Builds on: Feng et al. chain-of-thought dynamic programming theory Sparse Transformer Linear Transformer
Closest papers by meaning
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.89)
- Trainable Transformer in Transformer (ICML 2024 · similarity 0.89)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.88)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.88)
- Understanding Transformers via N-Gram Statistics (NeurIPS 2024 · similarity 0.88)
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · 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.