04 — Sequence Models

Phase 2 · Months 5–6 | Estimated time: 12–16 hours across 2 weeks

Sequence modeling is the problem of building representations that depend on order. A bag-of-words model treats “dog bites man” and “man bites dog” identically — which is fine until you need to care about the difference. RNNs, LSTMs, and GRUs are the 30-year lineage of solutions to this problem before transformers arrived. They are not obsolete. They are the foundation on which transformer attention makes sense.

---

1. The RNN: Unrolled in Time

A vanilla RNN maintains a single hidden state vector h_t that is updated at each timestep by combining the previous hidden state with the current input:

h_t = tanh(W_hh · h_{t-1} + W_xh · x_t + b_h)
y_t = W_hy · h_t + b_y

Parameter count: W_hh is (H × H), W_xh is (H × D) where H = hidden size, D = input size. Crucially, these weights are shared across all timesteps — the same transformation is applied at t=1, t=2, …, t=T. This is the RNN’s inductive bias: whatever transformation is useful at one timestep is useful at all timesteps.

Theoretically, this means an RNN can process sequences of arbitrary length. In practice, as you’ll see below, “arbitrary” is doing a lot of optimistic work.

---

2. BPTT and the Vanishing/Exploding Gradient Problem

Backpropagation Through Time (BPTT) unfolds the RNN across timesteps and computes gradients by the chain rule across that unrolled graph.

The gradient of the loss with respect to the hidden state at time t=1 involves a product of Jacobians across all timesteps from T back to 1:

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

Each factor ∂h_t/∂h_{t-1} is approximately W_hh^T · diag(1 - h_{t-1}²) for tanh activations. The critical quantity is the spectral radius of this product — the largest singular value of the chain of Jacobians.

If spectral radius < 1: Gradients shrink exponentially with T. At T=100, you’re multiplying by 0.9^100 ≈ 0.00003. Early timesteps receive essentially zero gradient. The network can’t learn long-range dependencies.

If spectral radius > 1: Gradients explode exponentially. At T=100, 1.1^100 ≈ 13,781. Weights diverge; training diverges.

The mathematical root cause: Both problems are consequences of the same structure — a repeated matrix multiplication. The eigenvalues of W_hh either dominate (>1) or disappear (<1) as you raise the matrix to the power of T. There is no stable middle ground at depth.

---

3. LSTM: Gating the Gradient Highway

The LSTM (Hochreiter & Schmidhuber, 1997) solves the vanishing gradient problem for medium-length sequences with a structural redesign: it maintains a separate cell state c_t that accumulates information additively, not multiplicatively. Additions don’t vanish.

The LSTM has four gates. Each is a learned function of the current input x_t and previous hidden state h_{t-1}.

Gate Equations

Forget gate f_t — decides what fraction of the previous cell state to keep:

f_t = σ(W_f · [h_{t-1}, x_t] + b_f)

Output ∈ (0, 1) per element. Value near 0: forget. Value near 1: remember. This is the gate that decides “this sentence just ended, discard the subject I was tracking.”

Input gate i_t — decides which new information to write into the cell:

i_t = σ(W_i · [h_{t-1}, x_t] + b_i)

Controls the magnitude of the update. Gate near 0: ignore the new information entirely.

Candidate cell g_t — the content of the proposed update:

g_t = tanh(W_g · [h_{t-1}, x_t] + b_g)

The tanh bounds values in (−1, 1). This is what the input gate modulates.

Output gate o_t — decides what part of the cell state to expose as the hidden state:

o_t = σ(W_o · [h_{t-1}, x_t] + b_o)

The cell state stores information; the hidden state is the filtered output.

State Update Equations

c_t = f_t ⊙ c_{t-1}  +  i_t ⊙ g_t
h_t = o_t ⊙ tanh(c_t)

where ⊙ denotes element-wise multiplication.

Why c_t solves vanishing gradients: The cell state update is additive — c_t = f_t ⊙ c_{t-1} + i_t ⊙ g_t. The gradient flowing back through c_t is:

∂c_t/∂c_{t-1} = f_t

This is the forget gate value — which is learned. Contrast this with the RNN’s W_hh^T · diag(tanh'(·)), which is a fixed matrix multiplication with no learned mechanism to prevent decay. The LSTM can learn to set f_t ≈ 1 (keep everything) over long stretches, giving gradients a near-lossless pathway. The cell state is, architecturally, a gradient highway.

---

4. GRU: The Simplified Alternative

The GRU (Cho et al., 2014) collapses the LSTM’s four gates into two and merges the cell state and hidden state into a single vector.

z_t = σ(W_z · [h_{t-1}, x_t])       # update gate (like LSTM's forget + input combined)
r_t = σ(W_r · [h_{t-1}, x_t])       # reset gate
h̃_t = tanh(W · [r_t ⊙ h_{t-1}, x_t])  # candidate hidden state
h_t = (1 - z_t) ⊙ h_{t-1}  +  z_t ⊙ h̃_t

Update gate z_t controls the interpolation between previous and new state: when z_t ≈ 0, keep the old state; when z_t ≈ 1, replace it.

Reset gate r_t controls how much of the previous hidden state influences the candidate.

Criterion	LSTM	GRU
Parameters	~4× hidden size²	~3× hidden size² (25% fewer)
Training speed	Slower	~20–30% faster
Performance	Marginally better on long sequences	Competitive; often equal on standard benchmarks
Memory	Higher	Lower
Use when	You have long sequences (>300 steps), asymmetric forget/output behavior matters	Standard sequence tasks, speed matters, lower memory budget

Practical rule: Start with GRU. Switch to LSTM if the task has evidence of very long-range dependencies and GRU plateaus first.

---

5. Where RNNs/LSTMs Are Still Used in 2025

Transformers did not uniformly replace recurrent models. The replacement was domain-specific, and several high-value use cases remain firmly in LSTM/GRU territory.

The common thread in LSTM survival cases: either the input is inherently streaming (no full-sequence attention is possible), or the device budget rules out transformer quadratic attention costs.

Domain	Model / Context	Why Not Transformer
Time-series forecasting	N-BEATS, PatchTST, LSTNet	Temporal locality; short context windows where LSTM is competitive and faster
Streaming audio / speech	Online ASR systems, keyword spotting	Must process token-by-token with bounded latency; full-sequence attention is incompatible
Edge / embedded devices	TensorFlow Lite LSTM, CoreML	Transformers are parameter-heavy; LSTM at H=256 is deployable on MCUs
RL environments	LSTM policy networks in PPO/DRQN	Partial observability; hidden state as working memory; transformers add too much overhead
Online anomaly detection	Streaming LSTM autoencoders	Real-time constraint; can’t wait for full sequence before making a decision

---

6. Where Transformers Won

For NLP tasks with sequences longer than ~64 tokens, transformers strictly dominate. The attention mechanism’s O(n²) cost is a limitation, but the parallel training and global receptive field are decisive.

• Language modeling (GPT-*): attention sees all previous tokens simultaneously; LSTM processes them serially and forgets early ones

• Machine translation (>~50 token sequences): alignment across long-range dependencies (subject–verb agreement across clauses) requires global attention

• Named entity recognition, classification: BERT-style bidirectional transformers with fine-tuning

• Any task where you have a full sequence at inference time and model size is not a constraint

---

7. Code: LSTM Character-Level Language Model

This trains on a text corpus and generates new text. The generated output demonstrates whether the model has actually learned statistical structure. A purely random character model would produce something like xt#qpw!. A trained LSTM produces something resembling the source domain.

import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np
import random

# ── Data Preparation ────────────────────────────────────────────────────────
# Use a small Shakespeare excerpt. Download or replace with any UTF-8 text.
# wget https://raw.githubusercontent.com/karpathy/char-rnn/master/data/tinyshakespeare/input.txt

with open("input.txt", "r") as f:
    text = f.read()

print(f"Corpus length: {len(text):,} characters")

chars    = sorted(set(text))
vocab_sz = len(chars)
char2idx = {c: i for i, c in enumerate(chars)}
idx2char = {i: c for c, i in char2idx.items()}

print(f"Vocabulary size: {vocab_sz}")

def encode(s): return [char2idx[c] for c in s]
def decode(lst): return "".join(idx2char[i] for i in lst)

data     = torch.tensor(encode(text), dtype=torch.long)
n        = len(data)
train_d  = data[:int(0.9 * n)]
val_d    = data[int(0.9 * n):]

# ── Dataset: Sliding Window Sequences ─────────────────────────────────────
SEQ_LEN    = 100
BATCH_SIZE = 128

def get_batch(split):
    d   = train_d if split == "train" else val_d
    ix  = torch.randint(len(d) - SEQ_LEN, (BATCH_SIZE,))
    x   = torch.stack([d[i    : i + SEQ_LEN    ] for i in ix])
    y   = torch.stack([d[i + 1: i + SEQ_LEN + 1] for i in ix])
    return x, y

# ── Model ──────────────────────────────────────────────────────────────────
class CharLSTM(nn.Module):
    def __init__(self, vocab_size, embed_dim, hidden_size, num_layers, dropout=0.3):
        super().__init__()
        self.embed       = nn.Embedding(vocab_size, embed_dim)
        self.lstm        = nn.LSTM(embed_dim, hidden_size, num_layers,
                                   batch_first=True, dropout=dropout)
        self.dropout     = nn.Dropout(dropout)
        self.fc          = nn.Linear(hidden_size, vocab_size)
        self.hidden_size = hidden_size
        self.num_layers  = num_layers

    def forward(self, x, hidden=None):
        embed  = self.dropout(self.embed(x))              # (B, T, E)
        out, hidden = self.lstm(embed, hidden)             # out: (B, T, H)
        logits = self.fc(self.dropout(out))                # (B, T, V)
        return logits, hidden

    def init_hidden(self, batch_size, device):
        h = torch.zeros(self.num_layers, batch_size, self.hidden_size).to(device)
        c = torch.zeros(self.num_layers, batch_size, self.hidden_size).to(device)
        return (h, c)


DEVICE     = torch.device("cuda" if torch.cuda.is_available() else "cpu")
EMBED_DIM  = 128
HIDDEN     = 512
N_LAYERS   = 2
EPOCHS     = 20
LR         = 3e-3

model     = CharLSTM(vocab_sz, EMBED_DIM, HIDDEN, N_LAYERS).to(DEVICE)
optimizer = optim.Adam(model.parameters(), lr=LR)
scheduler = optim.lr_scheduler.CosineAnnealingLR(optimizer, T_max=EPOCHS)
criterion = nn.CrossEntropyLoss()

print(f"Model parameters: {sum(p.numel() for p in model.parameters()):,}")

# ── Training ────────────────────────────────────────────────────────────────
STEPS_PER_EPOCH = 200

for epoch in range(EPOCHS):
    model.train()
    total_loss = 0.0

    for step in range(STEPS_PER_EPOCH):
        x, y    = get_batch("train")
        x, y    = x.to(DEVICE), y.to(DEVICE)
        hidden  = model.init_hidden(BATCH_SIZE, DEVICE)

        logits, _ = model(x, hidden)                             # (B, T, V)
        loss      = criterion(logits.view(-1, vocab_sz), y.view(-1))

        optimizer.zero_grad()
        loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)  # gradient clipping
        optimizer.step()

        total_loss += loss.item()

    scheduler.step()

    # Perplexity = exp(cross-entropy loss)
    avg_loss   = total_loss / STEPS_PER_EPOCH
    perplexity = np.exp(avg_loss)
    print(f"Epoch {epoch+1:02d} | loss={avg_loss:.4f} | perplexity={perplexity:.1f}")

# ── Text Generation ─────────────────────────────────────────────────────────
def generate(model, seed_text, length=500, temperature=0.8):
    """
    temperature < 1.0 → more conservative (picks high-prob chars)
    temperature > 1.0 → more creative / random
    """
    model.eval()
    chars_in = encode(seed_text)
    hidden   = model.init_hidden(1, DEVICE)

    # Warm up hidden state on seed
    with torch.no_grad():
        for ch in chars_in[:-1]:
            x = torch.tensor([[ch]], dtype=torch.long).to(DEVICE)
            _, hidden = model(x, hidden)

    result = list(seed_text)
    x      = torch.tensor([[chars_in[-1]]], dtype=torch.long).to(DEVICE)

    with torch.no_grad():
        for _ in range(length):
            logits, hidden = model(x, hidden)         # (1, 1, V)
            logits  = logits[0, 0] / temperature
            probs   = torch.softmax(logits, dim=-1)
            next_ch = torch.multinomial(probs, 1).item()
            result.append(idx2char[next_ch])
            x = torch.tensor([[next_ch]], dtype=torch.long).to(DEVICE)

    return "".join(result)


print("\n=== Generated Text (temperature=0.8) ===")
sample = generate(model, seed_text="ROMEO:\n", length=400, temperature=0.8)
print(sample)

# Expected output after 20 epochs on tinyshakespeare (~1M chars):
# Perplexity starts ~60–65 (epoch 1), converges to ~12–18 (epoch 20)
# Bigram baseline perplexity: ~25–30 → LSTM beats it by epoch 5
#
# Sample output (trained):
# "ROMEO:
# Why, then, the world's mine oyster, which I with sword will open.
# JULIET: What satisfaction canst thou have to-night?
# ROMEO: The exchange of thy love's faithful vow for mine."
# (Not exact, but structure, capitalization, and dialogue format will emerge)

Perplexity as a metric: Perplexity = exp(cross-entropy loss). A value of 1.0 means perfect prediction. A uniform distribution over 65 characters gives perplexity = 65. An LSTM trained on Shakespeare should converge to ~12–18, meaning the model is as uncertain as if it had ~15 equally likely choices at each step — far better than random.

---

What Most People Get Wrong

LSTMs don’t “solve” the vanishing gradient problem. They mitigate it for medium-length sequences.

The cell state’s additive update c_t = f_t ⊙ c_{t-1} + i_t ⊙ g_t is not a guaranteed gradient highway. It is a learned highway. The forget gate f_t is a learned sigmoid. Nothing forces the network to keep it near 1.0 for very long sequences — in practice, LSTMs still struggle when sequence length exceeds ~300–500 steps on tasks that require non-trivial long-range reasoning.

The Transformer’s self-attention has O(1) path length between any two tokens — a direct connection, not a chain of recurrent updates. That is why transformers structurally dominate LSTMs on tasks requiring long-range dependencies. The LSTM mitigated the problem with gates. The transformer eliminated it with attention. Understanding this distinction is what separates an engineer who knows when to reach for which tool.

---

Return to README.md · Next: 05_training_dynamics.md