§ 12 RNN / LSTM / GRU & Pre-Transformer Sequence Models

1. Overview

Before the transformer, recurrent architectures were the dominant paradigm for sequence data. An RNN maintains a hidden state that is updated at every time step, giving it theoretically unlimited context. In practice, vanilla RNNs suffer from vanishing gradients that prevent learning long-range dependencies. LSTM (1997) and GRU (2014) solved this with gating mechanisms that create a controlled gradient highway through time. By 2017, seq2seq models with attention (encoder-decoder architectures) achieved state-of-the-art machine translation — and that attention mechanism directly inspired the transformer's self-attention.

2. Vanilla RNN & Backpropagation Through Time

The vanilla RNN update equation at time step t:

h_t = tanh(W_h · h_{t-1} + W_x · x_t + b)     # shared W_h, W_x across all t
y_t = W_y · h_t + b_y                          # output at step t (optional)

Parameters:  W_h ∈ R[d_h × d_h],  W_x ∈ R[d_h × d_in],  b ∈ R[d_h]
All time steps share the same W_h and W_x — that is what makes it recurrent.

Training uses backpropagation through time (BPTT): unroll the RNN for T steps, then run standard backprop on the resulting computation graph. The gradient of the loss with respect to h_1 requires multiplying T Jacobian matrices of the tanh together:

∂L/∂h_1 = ∂L/∂h_T · (∏_{t=2}^{T} ∂h_t/∂h_{t-1})
         = ∂L/∂h_T · (∏_{t=2}^{T}  diag(1 - tanh²(z_t)) · W_h )

If ||W_h|| < 1  →  product shrinks exponentially  →  VANISHING GRADIENT
If ||W_h|| > 1  →  product grows exponentially    →  EXPLODING GRADIENT

Practical Fixes for Vanilla RNNs

3. LSTM — Core Mechanism

Background: Hochreiter & Schmidhuber (1997) identified the vanishing gradient problem precisely and proposed LSTM as a solution. The key observation: a vanilla RNN must route all information through a tanh nonlinearity at every step. The gradient is multiplicatively gated, so it either vanishes or explodes. The fix is to add an explicit cell state whose update is additive — controlled by learnable gates — so the gradient can flow backward with multiplication by only one number (the forget gate value) per step, rather than a full Jacobian.

Plan:

1. Introduce a separate cell state c_t that carries long-range memory — it lives alongside the hidden state h_t.
2. Add a forget gate f_t: how much of the previous cell state to retain (0 = erase, 1 = keep).
3. Add an input gate i_t and cell candidate g_t: how much new information to write.
4. Add an output gate o_t: how much of the cell state to expose as the hidden state h_t.
5. Cell state update: c_t = f_t ⊙ c_{t-1} + i_t ⊙ g_t — this is additive, so ∂c_t/∂c_{t-1} = f_t ≈ 1, providing a gradient highway.

LSTM Math — Full Equations

Combined input: z = [h_{t-1} ; x_t]      # concat prev hidden + current input

Forget gate:    f_t = σ(W_f · z + b_f)   # what fraction of c_{t-1} to erase
Input gate:     i_t = σ(W_i · z + b_i)   # how much new info to admit
Cell candidate: g_t = tanh(W_g · z + b_g) # proposed new memory content
Output gate:    o_t = σ(W_o · z + b_o)   # what fraction of c_t to expose

Cell state:     c_t = f_t ⊙ c_{t-1} + i_t ⊙ g_t   # additive update!
Hidden state:   h_t = o_t ⊙ tanh(c_t)

Gradient highway: ∂c_t/∂c_{t-1} = f_t
  When f_t ≈ 1 the gradient flows back across many steps without decay.
  The network LEARNS when to remember (f→1) and when to reset (f→0).

Walkthrough: LSTM remembering subject across a long clause

Initial conditions: Sequence is "The cat, which had been sitting on the mat for hours, <verb>". We want the model to remember "cat" (singular) by the time it predicts the verb.

4. GRU — Simplified Gating

Cho et al. (2014) introduced the Gated Recurrent Unit (GRU) while working on seq2seq translation. GRU merges the cell state and hidden state into a single vector and uses only two gates, making it faster and simpler than LSTM without a significant accuracy drop on most tasks.

Reset gate:   r_t = σ(W_r · [h_{t-1} ; x_t])     # 0 = ignore previous hidden
Update gate:  z_t = σ(W_z · [h_{t-1} ; x_t])     # 0 = use new, 1 = keep old

Candidate:    h̃_t = tanh(W · [r_t ⊙ h_{t-1} ; x_t])  # new proposal
Output:       h_t = (1 - z_t) ⊙ h̃_t + z_t ⊙ h_{t-1}  # interpolate

GRU vs LSTM:
  - One hidden vector (no separate cell state)
  - Two gates instead of three
  - ~33% fewer parameters
  - Roughly same quality; prefer LSTM when absolute accuracy matters,
    GRU when speed or simplicity is the priority

5. seq2seq Encoder-Decoder & Attention

The encoder-decoder (seq2seq) architecture for machine translation was introduced by Sutskever, Vinyals & Le (2014). The encoder LSTM reads the source sentence and compresses it into a single context vector (the final hidden state h_S). The decoder LSTM generates one target token at a time, conditioned on that context vector.

ENCODER:  for x_1,...,x_S:  h_t = LSTM(x_t, h_{t-1})  → context = h_S

DECODER:  s_0 = h_S
          for each output position t:
            y_t, s_t = LSTM(y_{t-1}, s_{t-1}, context)   # teacher forcing during training
            output   = softmax(W_out · s_t)

Teacher forcing: during training, feed the GROUND TRUTH y_{t-1} as decoder input
                 (not the model's own prediction). Speeds up convergence but creates
                 a train/test mismatch — at inference the model must use its own output.

The Information Bottleneck Problem

Compressing an entire variable-length sentence into a single fixed-size vector h_S creates a bottleneck. For long sentences (30+ tokens) the encoder hidden state cannot retain enough information, causing translation quality to degrade sharply — as observed empirically by Bahdanau et al. (2014, arXiv:1409.0473).

Bahdanau Attention — the Fix

Instead of using only h_S, allow the decoder to attend over all encoder hidden states h_1...h_S using a soft weighted average. The weights (attention scores) are computed from the decoder's current query and each encoder state:

Bahdanau (additive) attention:
  e_{ti} = v^T · tanh(W_h · h_i + W_s · s_{t-1})   # one scalar per source position
  α_{ti} = softmax(e_{t1}, ..., e_{tS})              # attention weights, sum = 1
  c_t    = Σ_i α_{ti} · h_i                          # context vector for step t

Luong (multiplicative) attention:
  dot:     score(h_i, s) = h_i · s
  general: score(h_i, s) = h_i^T · W_a · s
  concat:  score(h_i, s) = v^T · tanh(W_a · [h_i ; s])   # ≈ Bahdanau

The attention map α_{ti} can be visualised as a matrix [T_out × S_in] —
it shows which source words the decoder looks at when generating each target word.

6. Why Transformers Replaced RNNs at Scale

By 2017, seq2seq + attention models reached strong BLEU scores on translation, but three systemic limitations prevented them from scaling to the largest datasets and compute budgets:

7. Minimal Demos

Demo A — LSTM Gates Step-by-Step

Feed 5 tokens through an nn.LSTMCell and manually extract the forget, input, and output gate activations at each step. Watch how the cell norm grows as memory accumulates, and how h norm is controlled by the output gate. Change d_in and d_h to see how gate statistics shift with hidden size.

Demo B — Bahdanau vs Luong Attention

Given 6 encoder hidden states and a decoder query, compute attention weights with both Bahdanau (additive) and Luong (dot-product and general) scoring functions. The bar chart shows which source positions each variant focuses on. Try changing S and d to see how attention distributes over longer sequences.

8. Production / Source Pointers

9. References

Papers

• Hochreiter & Schmidhuber 1997 — Long Short-Term Memory (Neural Computation 9(8)). The original LSTM paper.
• Cho et al. 2014 — Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation (GRU; arXiv:1406.1078)
• Sutskever, Vinyals & Le 2014 — Sequence to Sequence Learning with Neural Networks (seq2seq; arXiv:1409.3215)
• Bahdanau, Cho & Bengio 2014 — Neural Machine Translation by Jointly Learning to Align and Translate (additive attention; arXiv:1409.0473)
• Luong, Pham & Manning 2015 — Effective Approaches to Attention-based Neural Machine Translation (dot/general attention; arXiv:1508.04025)
• Graves, Mohamed & Hinton 2013 — Speech Recognition with Deep Recurrent Neural Networks (bidirectional LSTM + CTC; arXiv:1303.5778)
• Pascanu, Mikolov & Bengio 2013 — On the Difficulty of Training Recurrent Neural Networks (vanishing/exploding gradient analysis; arXiv:1211.5063)
• Vaswani et al. 2017 — Attention Is All You Need (Transformer; arXiv:1706.03762) — replaces RNN with self-attention
• Gu & Dao 2023 — Mamba: Linear-Time Sequence Modeling with Selective State Spaces (arXiv:2312.00752)

Lectures

• Stanford CS224n — Lecture 5: RNNs and Language Models and Lecture 7: Machine Translation, Attention, Subword Models (Christopher Manning)
• MIT 6.S191 — Lecture 2: Recurrent Neural Networks (Alexander Amini)
• NYU DS-GA 1008 — Yann LeCun: Recurrent Networks and their Applications
• CMU 11-785 — Deep Learning: Recurrent Neural Networks (Bhiksha Raj)
• fast.ai Practical Deep Learning — Lesson 8: RNNs from scratch (Jeremy Howard)
• Karpathy — The Unreasonable Effectiveness of Recurrent Neural Networks (2015 blog post, accompanying code walk)

Textbooks

• Goodfellow, Bengio & Courville — Deep Learning (MIT Press, free at deeplearningbook.org) — Chapter 10: Sequence Modeling with Recurrent and Recursive Nets
• Zhang et al. — Dive Into Deep Learning (d2l.ai, free) — Chapters 9–10: RNNs, LSTMs, GRUs, seq2seq
• Jurafsky & Martin — Speech and Language Processing (3rd ed., free draft) — Chapter 9: RNNs and LSTMs

Code / Repos

• karpathy/char-rnn — classic character-level LSTM language model
• pytorch/examples/word_language_model — LSTM language model with tied embeddings
• pytorch/fairseq — production seq2seq with Bahdanau/Luong attention (fairseq/models/lstm.py)
• state-spaces/mamba — modern SSM alternative to transformers (2023)

Blog Posts

• Colah — Understanding LSTM Networks (colah.github.io, 2015): the definitive visual walkthrough of LSTM gates
• Karpathy — The Unreasonable Effectiveness of Recurrent Neural Networks (karpathy.github.io, 2015)
• Olah & Carter — Attention and Augmented Recurrent Neural Networks (distill.pub, 2016)
• Lilian Weng — Attention? Attention! (lilianweng.github.io, 2018): comprehensive survey of attention variants

10. Interview Prep