Research map / Architectures and efficiency / RNNs and normalization
Separations in the Representational Capabilities of Transformers and Recurrent Architectures
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 via communication complexity that RNNs and one-layer Transformers need linear size for several tasks where small (log-width) two-layer Transformers or small-width models suffice, establishing size-based separations between Transformers and recurrent models.
Problem
Whether tasks exist that are representable by one architecture with poly-logarithmic size but require linear size for the other, comparing Transformers and recurrent architectures (RNNs, SSMs, linear attention) under finite precision.
Approach
Uses nearly orthogonal vectors (JL-based, O(log N) dimensions) for attention-based lookup constructions, and lower-bounds recurrent models and one-layer Transformers via one-way and arbitrary-partition communication protocols reducing from Index, Disjointness, Equality.
Key results
- One-layer Transformer with width 64 reaches near-perfect accuracy on index lookup within a few thousand steps, while LSTM, DSS, Mamba, linear Transformer and RetNet of width/state 256 degrade beyond length 100.
- On Dyck-2, one-layer Transformers achieve near-perfect accuracy only up to length 100, while LSTMs and two-layer Transformers of width 64 stay near-perfect up to length 400.
- Theory: one-layer Transformers and RNNs need width Omega(N) for Equality and Disjointness, while two-layer Transformers of O(log N) width express them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a 1-layer Transformer rather than a recurrent model | Index Lookup · Index Lookup | required width: O(log N) vs m≥N/p | Helped |
| use a recurrent model rather than a 1-layer Transformer | bounded Dyck recognition · Dyck-(2, 2) | required model size: constant width vs mH ≥ \frac{N-1}{3(p+\log N)} | Helped |
| add a second Transformer layer | String Equality · String Equality | required width: Ω(N) to O(log N) | Helped |
| use a 2-layer Transformer rather than a recurrent model | Nearest Neighbor · Nearest Neighbor | required width: O(log N) vs m ≥ N/2p | Helped |
| use a 1-layer Transformer rather than recurrent models | Index Lookup · Index Lookup, lengths 20–400 | accuracy | Helped |
| increase sequence length for a 1-layer Transformer | Index Lookup · Index Lookup, lengths over 100 | accuracy | Hurt |
| use a small LSTM or 2-layer Transformer rather than a 1-layer Transformer | bounded Dyck recognition · Dyck-2, depth at most 2, lengths up to 400 | accuracy | Helped |
| increase sequence length for a 1-layer Transformer | bounded Dyck recognition · Dyck-2, depth at most 2 | accuracy | Hurt |
Surprising findings
- On Dyck-2, one-layer Transformers learn more slowly than LSTMs and two-layer Transformers even at lengths where they reach near-perfect accuracy.
Limitations
- Positive expressivity results do not imply learnability.
- Lower bounds only apply when sequence length is large relative to model size (e.g., beyond 8k for 128-dim double-precision-scale states), not at experimental lengths.
- No lower bounds for two-layer Transformers; communication-based techniques cannot yield them.
Experimental setup
Datasets: synthetic index lookup sequences synthetic Dyck-2 sequences
Benchmarks: index lookup (synthetic) Dyck-2 (synthetic)
Metrics: accuracy
Baselines: LSTM DSS Mamba linear Transformer RetNet
Builds on: Sanford et al. communication complexity for Transformers and RNNs Johnson-Lindenstrauss lemma Multi-Query Associative Recall
Closest papers by meaning
- When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective (NeurIPS 2025 · similarity 0.89)
- Beyond Attention: Breaking the Limits of Transformer Context Length with Recurrent Memory (AAAI 2024 · similarity 0.89)
- Bigram Subnetworks: Mapping to Next Tokens in Transformer Language Models (NeurIPS 2025 · similarity 0.89)
- Transformers need glasses! Information over-squashing in language tasks (NeurIPS 2024 · similarity 0.89)
- Relaxed Recursive Transformers: Effective Parameter Sharing with Layer-wise LoRA (ICLR 2025 · similarity 0.89)
- How Transformers Learn Structured Data: Insights From Hierarchical Filtering (ICML 2025 · 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.