RNN, LSTM & GRU: Attempts to Fix Long Context

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](/02-llm-modeling/00-fundamentals/01-attention/06-complexity-&-cost/)
  position-blind        → see [05 Position Information](/02-llm-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](/02-llm-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 — 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 — the O(n²) price attention pays for recurrence's failures
• 08 Interpretability — direct token access shown in attention weights