RNN, LSTM & GRU

Overview

Before attention, the entire field wrestled with one question: how does a model use information from far back in a sequence? Recurrent models (RNN → LSTM → GRU) were a long series of attempts to answer it. Each generation fixed one failure mode— vanishing gradients, memory capacity, direction— but all of them left two fundamental problems unsolved: sequential computation and compressed memory. Attention succeeded precisely where these attempts failed.

Timeline of attempts:
 1986 RNN → can in principle, fails in practice (gradients)
 1997 LSTM → fixes vanishing gradients with gates
 2014 GRU → simpler LSTM, same limits
 2014 Bi-RNN → fixes direction (for understanding tasks)
 2015 Bahdanau attention → first "look back directly" fix (inside RNN!)
 2017 Transformer → removes recurrence entirely → this chapter's subject

• The problem being fixed: Attention Mechanisms → The Problem: Why RNNs Fail at Long Context
• The two unsolved failures: no parallelism + fixed-capacity memory
• Key idea to remember: LSTMs made long-range memory possible; attention made it direct, parallel, and lossless

-

The Baseline: Plain RNN

How it works

h_t = tanh(W_x · x_t + W_h · h_{t-1} + b)

 ┌────────────────────────────────────┐
 x₁ → [h₁] → x₂ → [h₂] → x₃ → [h₃] →... → [h_T]
 │ │ │ │
 └── h₁ feeds ─┘── h₂ feeds ─┘──... └── final h_T = "summary"

Each step: take the new input x_t, mix it with the previous
hidden state h_{t-1}, squash through tanh, pass it on.

The strengths (why recurrence was attractive)

Variable length: one formula for any sequence length
Parameter sharing: same W_x, W_h for every position (few params)
Sequential structure: order is built into the computation
Cheap: O(T) time, O(1) extra state per step

The fatal weaknesses

Failure 1 — Vanishing (or exploding) gradients:
 ∂L/∂W ∝ Π_{k} J(h_k) ← product of many Jacobians
 each step scales the gradient by ~‖J‖ (often < 1)
 10 steps back → ×0.9¹⁰ ≈ 0.35
 50 steps back → ×0.9⁵⁰ ≈ 0.005
 100 steps back → ×0.9¹⁰⁰ ≈ 0.00003
 The network CANNOT learn long-range dependencies:
 the gradient signal is dead before it reaches the distant past.

Failure 2 — No parallelism:
 h_t needs h_{t-1}; h_{t-1} needs h_{t-2}...
 T steps = T serial GPU operations (a 1,000-token sentence is
 1,000 sequential matmuls — the GPU sits idle between steps)

Failure 3 — One-vector memory:
 everything seen so far must fit in ONE fixed-size vector h_t
 → old information gets overwritten by new information
 → capacity is the bottleneck even when gradients survive

Key Insight: RNNs in principle can remember arbitrarily long (they're Turing-complete), but gradient math and fixed-size memory make it impractical. The LSTM was the first serious engineering fix.

---

Attempt 1: LSTM (1997)— Fix the Vanishing Gradient

Long Short-Term Memory (Hochreiter & Schmidhuber, 1997) attacked failure #1 head-on with a gated, additive memory path.

The cell state: a "constant error carousel"

The central trick is a separate memory, the cell state C_t, updated by addition instead of multiplication:

Gate formulas (⊙ = element-wise multiply, σ = sigmoid):

 f_t = σ(W_f · [h_{t-1}; x_t] + b_f) forget gate → what to DROP from memory
 i_t = σ(W_i · [h_{t-1}; x_t] + b_i) input gate → what to WRITE to memory
 C̃_t = tanh(W_c · [h_{t-1}; x_t] + b_c) candidate → proposed new content
 C_t = f_t ⊙ C_{t-1} + i_t ⊙ C̃_t cell update → additive!
 o_t = σ(W_o · [h_{t-1}; x_t] + b_o) output gate → what to REVEAL
 h_t = o_t ⊙ tanh(C_t) hidden state

 ┌──────────────────────── C_t-1 ─────────────────────────┐
 │ ▼
x_t ───┼──► σ (forget f) ─────┐ ┌─ multiply ─► C_t
h_t-1 ─┼──► σ (input i) ──────┼──► candidate C̃ ──► multiply
 └──► tanh (candidate) ─┘ ▲ │
 └──► σ (output o) ─────────┴──► tanh ──► multiply ─► h_t

Why this fixes vanishing gradients

Plain RNN path: h_t = tanh(W·[...]) → every step is a tanh multiply
 gradient × (tanh' ≤ 1) each step → decays

LSTM path: C_t = f_t ⊙ C_{t-1} + i_t ⊙ C̃_t
 gradient flows through C_{t-1} with multiplier ≈ f_t
 if f_t ≈ 1 (gate OPEN) → gradient passes ~unchanged

This is the "Constant Error Carousel": the cell can carry a signal
back hundreds of steps because the path is ADDITIVE, not a chain of
squashing functions. Training a 100-step dependency becomes feasible.

Worked gate example (toy numbers)

Given: h_{t-1} = 0.2, x_t = 0.8, C_{t-1} = 1.0
Pre-activations (already computed by the weights):

 forget: z_f = 0.5 → f = σ(0.5) = 0.62 (keep 62% of old memory)
 input: z_i = 1.0 → i = σ(1.0) = 0.73 (write 73% of candidate)
 candidate: z_c = −0.3 → C̃ = tanh(−0.3) = −0.29
 output: z_o = 0.2 → o = σ(0.2) = 0.55

Cell update:
 C_t = f·C_{t-1} + i·C̃
 = 0.62·1.0 + 0.73·(−0.29)
 = 0.62 − 0.21 = 0.41

Hidden state:
 h_t = o·tanh(C_t) = 0.55·tanh(0.41) = 0.55·0.39 ≈ 0.21

Interpretation: the LSTM kept most of its old memory (0.62 factor),
wrote a little negative candidate, and output a bounded view of it.

What LSTMs still couldn't fix

Sequential computation remains: C_t still depends on C_{t-1}
 → training is T serial steps (slow, GPU-starved)

Fixed-capacity memory remains: one cell vector per position;
 keeping "cat" for 16 steps means it still shares the cell with
 everything else — information is mixed, not addressable

Long-range is *possible* but *fragile*:
 - forget gate is rarely fully open: f ≈ 0.6–0.9 in practice
 - old content decays: 0.9¹⁶ ≈ 0.19, 0.8¹⁶ ≈ 0.03 of the signal
 - gates are a *learned* trade-off: keeping everything hurts
 (the LSTM learns to forget to fit new material)

No direct "pointer" to a distant token — to use token #5's content
 at token #100, it must survive 95 compressions intact

---

Attempt 2: GRU (2014)— Simplify the LSTM

Gated Recurrent Unit (Cho et al., 2014) merged the forget and input gates into one update gate and dropped the separate cell state.

 z_t = σ(W_z·[h_{t-1}; x_t]) update gate (how much to change)
 r_t = σ(W_r·[h_{t-1}; x_t]) reset gate (how much old info to use)
 h̃_t = tanh(W_h·[r_t ⊙ h_{t-1}; x_t]) candidate
 h_t = (1 − z_t) ⊙ h_{t-1} + z_t ⊙ h̃_t blend old and new

2 gates, 3 weight matrices (vs LSTM's 3 gates, 4 matrices)

LSTM: 3 gates (f, i, o) + cell state C → 4 matrices
GRU: 2 gates (z, r), no separate cell → 3 matrices

Same core idea, fewer parameters:
 - trains faster, needs less data
 - performance ≈ LSTM on most tasks (sometimes better, sometimes worse)
 - still sequential, still fixed-memory, still decay-prone

-

Attempt 3: Bidirectional & Stacked RNNs— Fix Direction and Depth

Bidirectional RNNs (Schuster & Paliwal, 1997)

Forward pass: h₁ → h₂ →... → h_T (left-to-right context)
Backward pass: h₁ ← h₂ ←... ← h_T (right-to-left context)
Concatenate: [h_forward; h_backward] (both directions available)

Fixed: understanding tasks benefit from FUTURE context
 ("bank" needs the word AFTER it to be disambiguated)
Still broken: sequential in both passes (2× slower), still compressed

Stacked (deep) RNNs

h¹_t → h²_t → h³_t →... (hierarchical abstractions per layer)

Fixed: more expressive features per position
Worsened: depth multiplies the vanishing-gradient problem;
 needs skip-connections/gating to even train deep stacks

---

Attempt 4: Attention Inside RNNs (Bahdanau, 2015)— the patch that worked

The first attention mechanism was not a transformer— it was added to an LSTM encoder–decoder to fix one specific problem: the decoder had to squeeze the whole source sentence into a single final vector.

The fix: let the decoder "look back" at every encoder state

Instead of: context = ONE vector (the last encoder state)
Now: c_t = Σⱼ α_tj · h_j ← weighted sum of ALL encoder states

 e_tj = vᵀ tanh(W_a·[s_{t-1}; h_j]) (alignment score)
 α_tj = softmax(e_tj) (attention weight over source)
 c_t = Σⱼ α_tj · h_j (context vector — direct lookup!)
 s_t = RNN(s_{t-1}, [y_{t-1}; c_t]) (decoder update)

Decoder generating "The cat":
 step 1 ("The") → attends to: "Die"(0.55) "Katze"(0.10)...
 step 2 ("cat") → attends to: "Katze"(0.70)...

The decoder READS the relevant source words directly —
no 95-step compression survival required.

Why this matters for the story

This is the exact mechanism this chapter studies — but inside an RNN
It proved "direct connection to the past" is the right fix
The RNN core still serialized everything: attention fixed MEMORY,
 not PARALLELISM — T steps were still T serial computations

The Transformer (Vaswani 2017) took the next and final step:
remove the RNN entirely → attention is the ONLY token-to-token
mechanism → everything is parallel.

-

Attempt 5: The Transformer (2017)— Remove Recurrence

Recurrent: h_t = f(h_{t-1}, x_t) (must finish t−1 first)
Transformer: out = softmax(Q·Kᵀ/√d)·V (all positions at once)

Fixes the two remaining failures in one stroke:
 Parallelism: one big matmul, not T serial steps
 Memory: every token is addressable at ANY distance with O(1) steps
 — "its" reaches "cat" directly, no compression in between

New costs introduced:
 O(n²) compute/memory → see [06 Complexity & Cost](/01-modeling/00-fundamentals/01-attention/(06-complexity-cost/)
 position-blind → see [05 Position Information](/01-modeling/00-fundamentals/01-attention/05-position-information/)

---

The Scoreboard

Attempt	Year	Fixed	Left broken
Plain RNN	1986	—	gradients, parallelism, memory capacity
LSTM	1997	vanishing gradients (gated additive cell)	parallelism, capacity, fragile long-range
GRU	2014	simpler/faster training	same as LSTM
Bi-RNN	1997/2014	direction (both contexts)	sequential ×2, capacity
Bahdanau attention	2015	last-vector bottleneck (direct lookup)	sequential core remains
Transformer	2017	parallelism + direct memory	O(n²) cost, position-blind

The pattern: every recurrent attempt fixed ONE symptom.
Attention was the first fix that addressed the ROOT:
"stop compressing — give every token a direct wire to every other token."

-

Concrete Failure: The "its" Problem Through an LSTM

Sentence: "The cat, which was adopted from the shelter last winter,
 finally settled into its new home."

Distance from "cat" to "its" ≈ 16 tokens.

LSTM path:
 - "cat" is stored in the cell at position 2
 - every step, the forget gate multiplies the cell (f ≈ 0.6–0.9)
 - signal remaining after 16 steps: 0.9¹⁶ ≈ 0.19 (best case)
 0.8¹⁶ ≈ 0.03 (typical)
 - AND the cell also holds "shelter", "winter", "settled", "home"...
 → "cat" must survive as one component among many, compressed

Attention path:
 - at "its", the query matches the key of "cat" directly
 - score → softmax weight → value flows in ONE step
 - distance is irrelevant: 16 steps or 16,000, same mechanism

LSTM result: confused pronoun reference (shelter/home steal attention)
Transformer: "its" → "cat" with high weight (see [08 Interpretability](/01-modeling/00-fundamentals/01-attention/08-interpretability/))

-

Why Attention Ultimately Won (Three Reasons)

1. DIRECT ACCESS — every token can read any other token with O(1)
 steps; no information has to "survive" compression or decay
2. PARALLELISM — the whole sequence is processed as one matmul;
 GPUs (which are massive parallel machines) finally get fed
3. SCALABILITY — training data ×1000 (the LLM era) is only usable
 because transformers train fast enough to exploit it;
 LSTMs at GPT-3 scale would take decades of wall-clock time

LSTM/GRU are not obsolete — they still power:
 - speech processing, some time-series models
 - hybrid architectures, state-space models (Mamba) revisit their ideas
But for text, attention won outright.

-

Key Takeaways

RNN → LSTM → GRU: a history of patching one failure at a time LSTM's gift: the gated additive cell (constant error carousel) tamed vanishing gradients The wall they all hit: sequential computation + fixed-capacity memory Bahdanau (2015): attention was first an RNN patch— "look back directly" Transformer (2017): removed recurrence → parallel + addressable memory Trade-off: attention pays O(n²) for what recurrence gave away for free (order, linear cost) Not useless today: LSTM ideas live on in Mamba/state-space models and sequence audio models

-

Related Notes

• 00 Attention Mechanisms— the chapter this note motivates
• [01 Query, Key & Value](/01-modeling/00-fundamentals/01-attention/(01-query-key-value/)— where the "look back directly" idea matured
• 02 Scaled Dot Product Attention— the modern form of Bahdanau's context vector
• 03 Types Of Attention— why causal masking matters for generation (unlike bidirectional LSTM)
• [06 Complexity & Cost](/01-modeling/00-fundamentals/01-attention/(06-complexity-cost/)— the O(n²) price attention pays for recurrence's failures
• 08 Interpretability— direct token access shown in attention weights