Why Transformers — The Problems with RNNs

A recurrent neural network (RNN) reads a sequence one token at a time, folding each token into a hidden state that it carries forward to the next step. Before 2017, that was the architecture behind the leading models for language, translation, and speech. LSTMs and GRUs led translation benchmarks for roughly half a decade, and nothing else seriously competed.

They had three weaknesses, and each one hurt.

Sequential computation meant you could not parallelize along the time axis: token t+1 needs the hidden state from token t. A 1,024-token sequence meant 1,024 serial steps on a GPU that can do 1,000,000 floating-point ops per cycle. Training wall-clock time grew linearly with sequence length, on hardware built for parallelism.

Vanishing gradients meant information 50 tokens back had already passed through 50 non-linearities. Gated recurrent units (LSTM, GRU) softened the crush but did not remove it. Long-range dependencies, like "the book I read last summer on a plane to Kyoto was…", routinely failed.

Fixed-width hidden states meant the encoder squeezed the whole source sequence into a single vector before the decoder saw anything. Whether the source is 5 tokens or 500, the bottleneck has the same shape.

The 2017 paper "Attention Is All You Need" dropped recurrence entirely. All positions attend to all other positions in parallel, and training becomes one big matrix multiplication instead of 1,024 sequential ones.

By 2026 the same block runs across modalities: language (GPT-5, Claude 4, Llama 4), vision (ViT, DINOv2, SAM 3), audio (Whisper), biology (AlphaFold 3), robotics (RT-2). Same block, different inputs.

Recurrence is computation where step t depends on step t-1. An RNN computes h_t = f(h_{t-1}, x_t), so you cannot compute h_5 before h_4. On a modern GPU with 10,000+ parallel cores, that wastes 99% of the silicon on a long sequence.

Self-attention is a weighted sum over the whole sequence: output_i = sum_j(a_ij * v_j), computed for all pairs (i, j) at once. The full N×N attention matrix fills in one batched matmul, and no step waits on another. That is the shape GPUs are built for.

The speedup is not a constant. It is the difference between O(N) serial depth and O(log N) serial depth, since a tree reduction combines N values in log N rounds. In practice, transformers train 5–10× faster per epoch on matched hardware at N=512, and the gap widens with sequence length until you hit the O(N²) memory wall of attention (Flash Attention later attacked that wall, see Lesson 12).

What transformers cost. Attention memory scales as O(N²). At 2K context that is fine. At 128K you need sliding windows, RoPE extrapolation, Flash Attention tiling, or linear attention variants. Recurrence was O(N) in both time and memory. Attention does O(N²) work and holds O(N²) memory, and parallelism wins the wall-clock time back.

The inductive bias shift. RNNs assume locality and recency. Transformers build in no such assumption: all pairs are candidates for attention. That is why transformers need more data to train well but scale further once they have it. Chinchilla (2022) formalized this: given enough tokens, a transformer beats an RNN of equal parameter count.

This build has no neural network. We simulate the core bottleneck numerically so you can feel the gap on your laptop.

Step 1: measure serial depth

See code/main.py. It defines two functions. One is a decayed recurrence (serial, like an RNN): each step multiplies the previous state by 0.9 and adds the new element. The other is a plain mean over the sequence (order-independent, like the reduction inside attention). Same input, different dependency graph.

def rnn_style(xs):
    h = 0.0
    for x in xs:
        h = 0.9 * h + x   # can't parallelize: h depends on previous h
    return h
 
def attention_style(xs):
    return sum(xs) / len(xs)  # every x is independent

We time both at N = 1,000, 10,000, 100,000, and 1,000,000. The RNN version is O(N) and runs down a single CPU pipeline. Even in pure Python, the attention-style reduction beats it at every one of those lengths, because Python's sum() is implemented in C and iterates without interpreter overhead per step.

Step 2: count theoretical operations

Both functions touch each of the N elements once. What differs is dependency depth: how many operations must happen sequentially before the next can start. RNN depth = N. Attention-style depth = ceil(log2 N) with a tree reduction, which is what depth() in main.py computes. The script's parallel_scan (a Hillis-Steele prefix sum) has the same O(log N) depth, and the script checks it against serial_scan on a length-16 sequence (zero mismatches, last value 120.0). Depth, not op count, decides GPU time.

Step 3: empirical scaling on long sequences

The script prints two tables. The depth table runs N from 64 to 262,144: RNN depth grows from 64 to 262,144 while attention-style depth grows from 6 to 18. The wall-clock table is the noisier one. On one run, the RNN loop took about 0.03 ms at N = 1,000 and about 31 ms at N = 1,000,000, with the attention-style reduction 4 to 7 times faster at each length. Your numbers will differ. That gap is mostly interpreter overhead, so read the depth table for the architectural claim.

When to still pick an RNN in 2026:

State-space models (SSMs) like Mamba are essentially RNNs with a structured parameterization that gives them the best of both: O(N) scan memory and parallel training via selective scan. They recover 90% of transformer quality with better long-context scaling. In 2026 most frontier labs train hybrid SSM+transformer models (Jamba, Samba), so recurrence has become a component rather than a rival.

See outputs/skill-architecture-picker.md. The skill picks an architecture for a new sequence problem given length, throughput, and training-budget constraints. It refuses to recommend a pure RNN for a training run above 1B tokens until it has stated the trade-off. It also refuses to recommend full attention above 64K context without stating the O(N²) memory cost, and refuses to recommend an architecture published less than 12 months ago for production without a named fallback.

1. Easy. Take rnn_style from code/main.py and replace the scalar hidden state with a length-64 vector of hidden states. Re-measure. How much does the serial overhead grow with hidden-state dimension?
2. Medium. Extend the parallel_scan and serial_scan equivalence check in code/main.py, which only runs at length 16. Verify the two produce the same output on length 1024, then instrument parallel_scan to count its rounds and confirm the depth is log2(N).
3. Hard. Port the attention-style reduction to PyTorch on GPU. Time both as you sweep sequence length from 64 to 65,536. Plot the result and explain the curve shape.

• Vaswani et al. (2017). Attention Is All You Need: the paper that displaced recurrence in mainstream NLP.
• Bahdanau, Cho, Bengio (2014). Neural MT by Jointly Learning to Align and Translate: where attention was born, bolted onto an RNN.
• Hochreiter, Schmidhuber (1997). Long Short-Term Memory: the original LSTM paper, for the record.
• Gu, Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces: a modern recurrent answer to transformers.