Research map / Architectures and efficiency / Attention and transformers
Transformers, parallel computation, and logarithmic depth
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 constant-depth self-attention transformers and constant-round Massively Parallel Computation protocols can simulate each other, implying log-depth transformers solve graph connectivity and k-hop induction heads, which recurrent, GNN, sub-quadratic and shallow CoT models cannot solve efficiently.
Problem
Understanding what transformers can efficiently compute in the regime where context length grows while depth and width grow sublinearly, and what distinguishes them from other sequence and graph architectures.
Approach
Establishes a bidirectional simulation between transformers and Massively Parallel Computation (MPC): R-round MPC protocols are implemented by depth O(R) transformers, and depth-L transformers are simulated by O(L)-round MPC protocols, identifying parallelism as the key property distinguishing transformers.
Key results
- Transformers with 500K to 5M parameters and depths 2 to 6 trained on k-hop induction heads (context 100, alphabet 4) show the largest learnable k roughly doubling per added layer; a six-layer model performs well for all k <= 16.
- Theory: k-hop induction heads solvable by a causally-masked transformer with constant width m=O(1), H=1, and depth floor(log2 k)+2.
- Theory: R-round MPC protocols are simulated by O(R)-layer transformers with m=O(s^4 log N); conversely depth-L transformers are simulated by O(L)-round MPC, giving conditional Omega(log D) depth lower bound for connectivity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase transformer depth | Transformers trained on k-hop induction heads · k-hop induction heads | largest learnable k: Incrementing depth approximately doubles the largest k | Helped |
| Use a deeper model | Transformers trained on k-hop induction heads · Finite-sample k-hop induction heads | generalization | Helped |
Surprising findings
- Multi-layer RNNs of width O(N^{1/7}) need depth k for k-hop induction heads, and Mamba and other recurrent models inherit this limit.
- Single-layer chain-of-thought transformers need linear chain-of-thought length in k to solve k-hop, unlike log-depth transformers.
Limitations
- Lower bounds are conditional on the one-versus-two cycle conjecture for MPC.
- Embedding dimension m=O(N^{4 delta} log N) in the MPC-to-transformer simulation only non-trivial for strongly sublinear local memory; constructions may be inefficient in size.
- Assumes fixed-precision p=Theta(log N) bits and arbitrary element-wise MLPs, which abstracts away practical training.
Experimental setup
Datasets: synthetic k-hop induction heads sequences
Benchmarks: k-hop induction heads
Metrics: accuracy on k-hop prediction largest learnable k by depth
Baselines: Mamba Performer Longformer multi-layer RNNs GNN message passing (Congest-based bounds) shallow chain-of-thought transformers
Builds on: Massively Parallel Computation induction heads Performer Longformer Mamba
Closest papers by meaning
- Fast attention mechanisms: a tale of parallelism (NeurIPS 2025 · similarity 0.87)
- Two Heads are Better than One: Simulating Large Transformers with Small Ones (NeurIPS 2025 · similarity 0.86)
- Positional Attention: Expressivity and Learnability of Algorithmic Computation (ICML 2025 · similarity 0.86)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.86)
- What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks (ICML 2024 · similarity 0.86)
- Transformer Layers as Painters (AAAI 2025 · similarity 0.85)
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.