Self-Attention vs Recurrence
How transformers replaced RNNs as the dominant sequence architecture
Attention parallelizes training and reaches long-range dependencies in one hop, which is why transformers displaced RNNs for nearly all sequence modeling.
Self-Attention (Transformer)
Glossary →Self-attention computes pairwise compatibility scores between all positions in a sequence simultaneously, enabling O(1) path length for long range dependencies and full parallelism during training.
Best for: Parallel training and long-range dependencies.
Recurrence (RNN/LSTM)
Glossary →Recurrent architectures (RNN, LSTM, GRU) process sequences one token at a time, maintaining a hidden state that carries information forward. Sequential by nature, limiting parallelism.
Best for: Streaming or memory-constrained edge settings.
At a glance
| Dimension | Self-Attention (Transformer) | Recurrence (RNN/LSTM) |
|---|---|---|
| Training parallelism | Full (all positions at once) | None (sequential) |
| Long range dependencies | Direct (O(1) path length) | Indirect (must relay through states) |
| Memory (training) | O(n^2) for attention matrices | O(n) for hidden states |
| Inference | Autoregressive with KV cache | Naturally streaming |
| Dominant era | 2017-present | 2013-2017 |
| Best for | Language models, vision, multimodal | Legacy systems, streaming, edge |
Key differences
- 1Attention is parallel; recurrence is sequential
- 2Attention has O(n^2) memory for sequence length n; recurrence is O(n) but with vanishing gradient risk
- 3Transformers scale to massive models via parallelism; RNNs hit hardware bottlenecks earlier
- 4Attention captures long range dependencies directly; RNNs must relay through every intermediate step
- 5RNNs have constant memory per step; transformers need KV cache that grows linearly with sequence length
In the interview
- Saying RNNs are dead without naming streaming or edge use cases
- Confusing O(n^2) attention memory with O(n) inference memory
- Forgetting that KV cache still grows linearly at inference
- Handwaving 'parallelism' without saying what parallelizes
How to choose
Attention parallelizes and reaches globally; recurrence stays cheap and streams. Hybrids target both.
Common misconceptions
Myth: RNNs are obsolete.
Reality: Linear-time recurrent-flavored models (Mamba, RWKV, RetNet) are back on the research frontier because they scale to very long contexts more cheaply than attention.
Myth: Attention is always O(n^2).
Reality: Only vanilla self-attention. FlashAttention keeps it O(n^2) compute but linear memory; sparse and linear-attention variants trade quality for asymptotics.
Memory aid
Recurrence is a game of telephone; attention is a group chat where everyone sees everyone.
Can you combine them?
Hybrid architectures exist (e.g., Mamba, RWKV, RetNet) that blend attention-like quality with linear-time recurrence. These are an active research area targeting the best of both worlds.