# RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 53 references that are in the map.
- First posted on arXiv 28 Feb 2024.

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (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)
- [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)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Using Fast Weights to Attend to the Recent Past](https://mlsanity.com/paper/1610.06258/) (2016)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [Retrieval as Attention: End-to-end Learning of Retrieval and Reading within a Single Transformer](https://mlsanity.com/paper/2212.02027/) (2022)
- [In Search of Needles in a 11M Haystack: Recurrent Memory Finds What LLMs Miss](https://mlsanity.com/paper/2402.10790/) (2024)
- [On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis](https://mlsanity.com/paper/2009.07799/) (2020)
- [Modeling Recurrence for Transformer](https://mlsanity.com/paper/1904.03092/) (2019)
- [Do Efficient Transformers Really Save Computation?](https://mlsanity.com/paper/2402.13934/) (2024)

## Built on by (most cited first, 30 of 64)

- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling](https://mlsanity.com/paper/2406.07522/) (2024)
- [Gated Slot Attention for Efficient Linear-Time Sequence Modeling](https://mlsanity.com/paper/2409.07146/) (2024)
- [ATLAS: Learning to Optimally Memorize the Context at Test Time](https://mlsanity.com/paper/2505.23735/) (2025)
- [Massive Values in Self-Attention Modules are the Key to Contextual Knowledge Understanding](https://mlsanity.com/paper/2502.01563/) (2025)
- [Falcon Mamba: The First Competitive Attention-free 7B Language Model](https://mlsanity.com/paper/2410.05355/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Llamba: Scaling Distilled Recurrent Models for Efficient Language Processing](https://mlsanity.com/paper/2502.14458/) (2025)
- [Gated DeltaNet-2: Decoupling Erase and Write in Linear Attention](https://mlsanity.com/paper/2605.22791/) (2026)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2410.13857/) (2024)
- [Distilling to Hybrid Attention Models via KL-Guided Layer Selection](https://mlsanity.com/paper/2512.20569/) (2025)
- [Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanism](https://mlsanity.com/paper/2504.18574/) (2025)
- [Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis](https://mlsanity.com/paper/2410.02167/) (2024)
- [ReMamba: Equip Mamba with Effective Long-Sequence Modeling](https://mlsanity.com/paper/2408.15496/) (2024)
- [Decoder-Hybrid-Decoder Architecture for Efficient Reasoning with Long Generation](https://mlsanity.com/paper/2507.06607/) (2025)
- [Artificial Hippocampus Networks for Efficient Long-Context Modeling](https://mlsanity.com/paper/2510.07318/) (2025)
- [A Little Goes a Long Way: Efficient Long Context Training and Inference with Partial Contexts](https://mlsanity.com/paper/2410.01485/) (2024)
- [Mechanistic evaluation of Transformers and state space models](https://mlsanity.com/paper/2505.15105/) (2025)
- [Stuffed Mamba: Oversized States Lead to the Inability to Forget](https://mlsanity.com/paper/2410.07145/) (2024)
- [Shaking Up VLMs: Comparing Transformers and Structured State Space Models for Vision & Language Modeling](https://mlsanity.com/paper/2409.05395/) (2024)
- [Exploring the Limitations of Mamba in COPY and CoT Reasoning](https://mlsanity.com/paper/2410.03810/) (2024)
- [MaTVLM: Hybrid Mamba-Transformer for Efficient Vision-Language Modeling](https://mlsanity.com/paper/2503.13440/) (2025)
- [Strong Memory, Weak Control: An Empirical Study of Executive Functioning in LLMs](https://mlsanity.com/paper/2504.02789/) (2025)
- [Transformers Meet In-Context Learning: A Universal Approximation Theory](https://mlsanity.com/paper/2506.05200/) (2025)
- [Retrieval-Aware Distillation for Transformer-SSM Hybrids](https://mlsanity.com/paper/2602.11374/) (2026)
- [Raven: High-Recall Sequence Modeling with Sparse Memory Routing](https://mlsanity.com/paper/2607.25357/) (2026)
- [Approximation Bounds for Recurrent Neural Networks with Application to Regression](https://mlsanity.com/paper/2409.05577/) (2024)
- [Taipan: Efficient and Expressive State Space Language Models with Selective Attention](https://mlsanity.com/paper/2410.18572/) (2024)

## Abstract (arXiv)

This paper investigates the gap in representation powers of Recurrent Neural Networks (RNNs) and Transformers in the context of solving algorithmic problems. We focus on understanding whether RNNs, known for their memory efficiency in handling long sequences, can match the performance of Transformers, particularly when enhanced with Chain-of-Thought (CoT) prompting. Our theoretical analysis reveals that CoT improves RNNs but is insufficient to close the gap with Transformers. A key bottleneck lies in the inability of RNNs to perfectly retrieve information from the context, even with CoT: for several tasks that explicitly or implicitly require this capability, such as associative recall and determining if a graph is a tree, we prove that RNNs are not expressive enough to solve the tasks while Transformers can solve them with ease. Conversely, we prove that adopting techniques to enhance the in-context retrieval capability of RNNs, including Retrieval-Augmented Generation (RAG) and adding a single Transformer layer, can elevate RNNs to be capable of solving all polynomial-time solvable problems with CoT, hence closing the representation gap with Transformers.