# Separations in the Representational Capabilities of Transformers and Recurrent Architectures

arXiv: https://arxiv.org/abs/2406.09347 · HTML: https://mlsanity.com/paper/2406.09347/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 69 references that are in the map.
- First posted on arXiv 13 Jun 2024.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [Zoology: Measuring and Improving Recall in Efficient Language Models](https://mlsanity.com/paper/2312.04927/) (2023)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Using Fast Weights to Attend to the Recent Past](https://mlsanity.com/paper/1610.06258/) (2016)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Tracr: Compiled Transformers as a Laboratory for Interpretability](https://mlsanity.com/paper/2301.05062/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)

## Built on by (most cited first, 29 of 29)

- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](https://mlsanity.com/paper/2502.10178/) (2025)
- [Sequential Group Composition: A Window into the Mechanics of Deep Learning](https://mlsanity.com/paper/2602.03655/) (2026)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers](https://mlsanity.com/paper/2505.21024/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Lower bounds on transformers with infinite precision](https://mlsanity.com/paper/2412.20195/) (2024)
- [A completely uniform transformer for parity](https://mlsanity.com/paper/2501.02535/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective](https://mlsanity.com/paper/2503.11272/) (2025)
- [Fast attention mechanisms: a tale of parallelism](https://mlsanity.com/paper/2509.09001/) (2025)
- [Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth](https://mlsanity.com/paper/2602.11175/) (2026)
- [Two Heads Are Better than One: Simulating Large Transformers with Small Ones](https://mlsanity.com/paper/2506.12220/) (2025)
- [Hybrid Quantum-Classical Recurrent Neural Networks](https://mlsanity.com/paper/2510.25557/) (2025)
- [Universal computation is intrinsic to language model decoding](https://mlsanity.com/paper/2601.08061/) (2026)
- [A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention](https://mlsanity.com/paper/2602.01763/) (2026)
- [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026)
- [Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalization](https://mlsanity.com/paper/2605.31558/) (2026)
- [On the Role of Depth in the Expressivity of RNNs](https://mlsanity.com/paper/2604.02201/) (2026)
- [Position: Avoid Overstretching LLMs for every Enterprise Task](https://mlsanity.com/paper/2605.09365/) (2026)
- [Inference Time Context Sparsity: Illusion or Opportunity?](https://mlsanity.com/paper/2605.24168/) (2026)
- [From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP](https://mlsanity.com/paper/2607.11760/) (2026)
- [Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention](https://mlsanity.com/paper/2608.11427/) (2026)

## Abstract (arXiv)

Transformer architectures have been widely adopted in foundation models. Due to their high inference costs, there is renewed interest in exploring the potential of efficient recurrent architectures (RNNs). In this paper, we analyze the differences in the representational capabilities of Transformers and RNNs across several tasks of practical relevance, including index lookup, nearest neighbor, recognizing bounded Dyck languages, and string equality. For the tasks considered, our results show separations based on the size of the model required for different architectures. For example, we show that a one-layer Transformer of logarithmic width can perform index lookup, whereas an RNN requires a hidden state of linear size. Conversely, while constant-size RNNs can recognize bounded Dyck languages, we show that one-layer Transformers require a linear size for this task. Furthermore, we show that two-layer Transformers of logarithmic size can perform decision tasks such as string equality or disjointness, whereas both one-layer Transformers and recurrent models require linear size for these tasks. We also show that a log-size two-layer Transformer can implement the nearest neighbor algorithm in its forward pass; on the other hand recurrent models require linear size. Our constructions are based on the existence of N nearly orthogonal vectors in O(log N) dimensional space and our lower bounds are based on reductions from communication complexity problems. We supplement our theoretical results with experiments that highlight the differences in the performance of these architectures on practical-size sequences.