Research map / Architectures and efficiency / Attention and transformers
RNNs are not Transformers (Yet): The Key Bottleneck on In-Context Retrieval
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 theoretically that chain-of-thought does not let constant-size RNNs match Transformers on in-context retrieval tasks (associative recall, IsTree), and that in-context RAG via regex or appending one Transformer layer closes the gap; validated on IsTree and HotpotQA with Mamba/Transformer/hybrid models.
Problem
Whether RNNs, even with chain-of-thought, can match Transformers on algorithmic problems, given that RNNs have limited memory for in-context retrieval.
Approach
Uses communication-complexity/streaming lower bounds to show o(n)-bit-memory RNNs fail at in-context retrieval (Index, AR, c-gram, Counting, IsTree) even with CoT, then shows that adding regex-based retrieval (in-context RAG) or a single Transformer layer on top of the RNN restores full polynomial-time expressivity.
Key results
- On IsTree, CoT improves RNN and Transformer accuracy but RNN accuracy degrades sharply as graph size grows, while Transformers consistently outperform RNNs.
- In-context RAG lets all models reach near-perfect IsTree accuracy, and the hybrid Mamba with one Transformer layer performs on par with the Transformer.
- On HotpotQA with random paragraph order, RNN performance drops more sharply as the number of paragraphs n increases from 2 to 8 than Transformer or hybrid models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CoT | RNNs and Transformers · IsTree | accuracy | Helped |
| Add CoT to RNNs | RNNs · IsTree as graph size increases | accuracy | Hurt |
| Add CoT to RNNs rather than use a Transformer | IsTree · IsTree | accuracy | Hurt |
| Add In-Context RAG with regular-expression retrieval | All tested models · IsTree | accuracy | Helped |
| Append one Transformer layer to Mamba | Mamba · IsTree | accuracy | Helped |
| Increase the number of randomly ordered paragraphs | RNNs, Transformers, and hybrid models · Hotpot-QA, random paragraph order | accuracy | Hurt |
| Increase retrieval difficulty by adding randomly ordered paragraphs | RNNs compared with Transformers and hybrid models · Hotpot-QA, random paragraph order | accuracy | Mixed |
| Use a hybrid model with 4 attention layers instead of an RNN | RNN · Hotpot-QA, random paragraph order | accuracy | Helped |
| Place the required paragraphs at the end instead of randomizing paragraph order | Transformer, RNN, and hybrid models · Hotpot-QA | accuracy | Helped |
Surprising findings
- Without CoT, neither Transformers nor RNNs learn to solve IsTree in the experiments.
Limitations
- In-context RAG via regular expressions has no existing training data and is not a practical method beyond the theoretical setting.
- Only representation power is studied; training dynamics and generalization are not analyzed.
- Hybrid architecture result considers only appending a single Transformer layer; other architectural changes are unexplored.
Experimental setup
Datasets: HotpotQA synthetic IsTree graphs
Benchmarks: IsTree (synthetic) HotpotQA with controlled retrieval difficulty
Metrics: accuracy
Baselines: Mamba Transformer (LLaMA architecture) Mamba with one Transformer layer (hybrid) Phi-1.5 teacher
Builds on: chain-of-thought Mamba Linear Transformers Phi-1.5
Closest papers by meaning
- Beyond Attention: Breaking the Limits of Transformer Context Length with Recurrent Memory (AAAI 2024 · similarity 0.88)
- Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanism (ICML 2025 · similarity 0.88)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.87)
- RAT: Bridging RNN Efficiency and Attention Accuracy via Chunk-based Sequence Modeling (NeurIPS 2025 · similarity 0.86)
- In-Context Learning with Representations: Contextual Generalization of Trained Transformers (NeurIPS 2024 · similarity 0.86)
- In-Context Learning as Conditioned Associative Memory Retrieval (ICML 2025 · similarity 0.86)
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.