mlsanityData to 7 Oct 2026

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

arXiv 2402.18510 ↗First posted 28 Feb 2024cs.LG cs.CL stat.MLcited by 62

Not on the map. Why?

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.

Key facts. Cited by 62 papers in the map (data through 7 Oct 2026). Builds on 28 of its 53 references that are in the map. First posted on arXiv 28 Feb 2024.

Builds on

28 of 53 references.

References · 28

  1. 2017Attention Is All You Needcited by 59,932
  2. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  4. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  5. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  6. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  7. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  8. 2021Improving language models by retrieving from trillions of tokenscited by 1,278
  9. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  10. 2014Neural Turing Machinescited by 630
  11. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 594
  12. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
16 more
  1. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  2. 2022Transformers Learn Shortcuts to Automatacited by 260
  3. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  4. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  5. 2023Zoology: Measuring and Improving Recall in Efficient Language Modelscited by 188
  6. 2016Using Fast Weights to Attend to the Recent Pastcited by 161
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  8. 2023Representational Strengths and Limitations of Transformerscited by 132
  9. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  10. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  11. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 50
  12. 2022Retrieval as Attention: End-to-end Learning of Retrieval and Reading within a Single Transformercited by 45
  13. 2024In Search of Needles in a 11M Haystack: Recurrent Memory Finds What LLMs Misscited by 36
  14. 2019Modeling Recurrence for Transformercited by 26
  15. 2020On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysiscited by 26
  16. 2024Do Efficient Transformers Really Save Computation?cited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 18; 2025: 24; 2026: 20.

62 papers.

Sort:

By area:

  1. 2024Gated Delta Networks: Improving Mamba2 with Delta Rulecited by 483
  2. 2025Kimi Linear: An Expressive, Efficient Attention Architecturecited by 169
  3. 2024Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modelingcited by 167
  4. 2024Gated Slot Attention for Efficient Linear-Time Sequence Modelingcited by 73
  5. 2025ATLAS: Learning to Optimally Memorize the Context at Test Timecited by 57
  6. 2025Massive Values in Self-Attention Modules are the Key to Contextual Knowledge Understandingcited by 44
  7. 2024Falcon Mamba: The First Competitive Attention-free 7B Language Modelcited by 43
  8. 2024Theoretical limitations of multi-layer Transformercited by 43
  9. 2025Llamba: Scaling Distilled Recurrent Models for Efficient Language Processingcited by 35
  10. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  11. 2024How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMscited by 24
  12. 2026Gated DeltaNet-2: Decoupling Erase and Write in Linear Attentioncited by 24
38 more
  1. 2025Distilling to Hybrid Attention Models via KL-Guided Layer Selectioncited by 17
  2. 2025Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanismcited by 15
  3. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysiscited by 14
  4. 2024ReMamba: Equip Mamba with Effective Long-Sequence Modelingcited by 12
  5. 2025Decoder-Hybrid-Decoder Architecture for Efficient Reasoning with Long Generationcited by 10
  6. 2024A Little Goes a Long Way: Efficient Long Context Training and Inference with Partial Contextscited by 9
  7. 2025Artificial Hippocampus Networks for Efficient Long-Context Modelingcited by 9
  8. 2025Mechanistic evaluation of Transformers and state space modelscited by 8
  9. 2024Stuffed Mamba: Oversized States Lead to the Inability to Forgetcited by 7
  10. 2024Shaking Up VLMs: Comparing Transformers and Structured State Space Models for Vision & Language Modelingcited by 6
  11. 2024Exploring the Limitations of Mamba in COPY and CoT Reasoningcited by 6
  12. 2025MaTVLM: Hybrid Mamba-Transformer for Efficient Vision-Language Modelingcited by 6
  13. 2025Strong Memory, Weak Control: An Empirical Study of Executive Functioning in LLMscited by 6
  14. 2026Retrieval-Aware Distillation for Transformer-SSM Hybridscited by 5
  15. 2024Taipan: Efficient and Expressive State Space Language Models with Selective Attentioncited by 4
  16. 2025Transformers Meet In-Context Learning: A Universal Approximation Theorycited by 4
  17. 2026What to Keep, What to Forget: A Rate--Distortion View of Memory Compaction in LLMs and Agentscited by 4
  18. 2026Raven: High-Recall Sequence Modeling with Sparse Memory Routingcited by 4
  19. 2024CLIP-Mamba: CLIP Pretrained Mamba Models with OOD and Hessian Evaluationcited by 3
  20. 2025VideoMAP: Toward Scalable Mamba-based Video Autoregressive Pretrainingcited by 3
  21. 2025The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architecturescited by 3
  22. 2025Alleviating Forgetfulness of Linear Attention by Hybrid Sparse Attention and Contextualized Learnable Token Evictioncited by 3
  23. 2026MDN: Parallelizing Stepwise Momentum for Delta Linear Attentioncited by 3
  24. 2024Approximation Bounds for Recurrent Neural Networks with Application to Regressioncited by 2
  25. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 2
  26. 2025SportMamba: Adaptive Non-Linear Multi-Object Tracking with State Space Models for Team Sportscited by 2
  27. 2025Fast attention mechanisms: a tale of parallelismcited by 2
  28. 2025Controllably Efficient Language Modelscited by 2
  29. 2026On the "Induction Bias" in Sequence Modelscited by 2
  30. 2026Morphing into Hybrid Attention Modelscited by 2
  31. 2024Birdie: Advancing State Space Models with Reward-Driven Objectives and Curriculacited by 1
  32. 2025HAD: Hybrid Architecture Distillation Outperforms Teacher in Genomic Sequence Modelingcited by 1
  33. 2025Two Heads Are Better than One: Simulating Large Transformers with Small Onescited by 1
  34. 2025FlashEVA: Accelerating LLM inference via Efficient Attentioncited by 1
  35. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  36. 2026Bayesian Optimality of In-Context Learning with Selective State Spacescited by 1
  37. 2026Retrievit: In-context Retrieval Capabilities of Transformers, State Space Models, and Hybrid Architecturescited by 1
  38. 2026On the Expressive Power and Limitations of Multi-Layer SSMscited by 1

50 most cited of 62 All 62 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025How Transformers Learn In-Context Recall Tasks? Optimality, Training Dynamics and Generalization
  2. 2025StateX: Enhancing RNN Recall via Post-training State Expansion
  3. 2026Adaptive Loops and Memory in Transformers: Think Harder or Know More?
  4. 2025Rethinking Reasoning in LLMs: Neuro-Symbolic Local RetoMaton Beyond ICL and CoT
  5. 2026DreamingGoose: Staged Distillation from Autoregressive Transformers to Bidirectional Recurrent Diffusion Language Models
  6. 2022Re2G: Retrieve, Rerank, Generate
  7. 2025Beyond Semantics: How Temporal Biases Shape Retrieval in Transformer and State-Space Models
  8. 2025Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention