Sequence Models & RNNs

A feedforward network (MLP) maps a fixed-size input vector to an output. If you want to classify a sentence of length T, the naive approach is to pad everything to a maximum length and feed the whole thing as a flat vector. This fails for three reasons.

Variable length. Real sequences have different lengths. Padding wastes capacity and does not scale.

No positional weight sharing. If the word "not" negates the next word, a feedforward network must learn that independently for every possible position. With 512 positions and a vocabulary of 50,000, that is 25.6 million separate rules to learn — for just one grammatical phenomenon.

No compositionality through time. Meaning is built incrementally. The phrase "not only … but also" is a construction spread across potentially many tokens. A flat vector loses the sequential structure that makes language compositional.

The right inductive bias for sequential data is recurrence: the output at step t should depend on the input at step t and a compressed summary of all previous inputs. Recurrent networks encode exactly this bias, using the same weight matrix at every step — a form of weight sharing across time analogous to how convolutional networks share weights across space.

# Naive feedforward on sequences: broken
import torch
import torch.nn as nn

# Fails: assumes all sequences have the same length L
class BadSequenceModel(nn.Module):
    def __init__(self, vocab_size, L, hidden):
        super().__init__()
        self.embed = nn.Embedding(vocab_size, 16)
        self.fc = nn.Linear(L * 16, hidden)   # hard-coded length L

    def forward(self, x):  # x: (batch, L)
        e = self.embed(x).view(x.size(0), -1)  # flatten
        return self.fc(e)  # no order awareness, no weight sharing

An RNN processes a sequence $x_1, x_2, \ldots, x_T$ one step at a time. At each step $t$ it maintains a hidden state $h_t \in \mathbb{R}^H$ that summarizes what the network has seen so far.

The recurrence equation is: $$h_t = \tanh(W_{hh}, h_{t-1} + W_{xh}, x_t + b_h)$$

And an optional output at each step: $$y_t = W_{hy}, h_t + b_y$$

Here $W_{hh} \in \mathbb{R}^{H \times H}$ is the recurrent weight matrix (the memory), $W_{xh} \in \mathbb{R}^{H \times D}$ maps the input, and $W_{hy}$ projects to output space. Crucially, all time steps share the same weights — there is only one set of $W_{hh}, W_{xh}, b_h$.

Think of $h_t$ as a whiteboard. At each step you (1) erase part of the whiteboard using new information and (2) write a new summary. The tanh nonlinearity squashes the hidden state to $(-1, 1)$, providing a soft normalization.

Three usage patterns:

• Many-to-one: Read the whole sequence, use $h_T$ as input to a classifier (e.g., sentiment classification).
• Many-to-many (same length): Produce one output per input (e.g., part-of-speech tagging).
• Many-to-many (different length): Encoder reads input, decoder generates output — this is the sequence-to-sequence architecture (e.g., translation).

The initial hidden state $h_0$ is typically the zero vector, though it can be learned.

import torch
import torch.nn as nn

class VanillaRNN(nn.Module):
    def __init__(self, input_size, hidden_size, output_size):
        super().__init__()
        self.hidden_size = hidden_size
        # Combined weight matrix for efficiency: [h_{t-1}, x_t] -> h_t
        self.i2h = nn.Linear(input_size + hidden_size, hidden_size)
        self.h2o = nn.Linear(hidden_size, output_size)

    def forward(self, x_seq):  # x_seq: (T, batch, input_size)
        T, B, _ = x_seq.shape
        h = torch.zeros(B, self.hidden_size)  # h_0
        outputs = []
        for t in range(T):
            combined = torch.cat([h, x_seq[t]], dim=1)
            h = torch.tanh(self.i2h(combined))  # h_t
            outputs.append(self.h2o(h))          # y_t
        return torch.stack(outputs), h  # (T, B, output_size), final h

To train an RNN we need gradients of the loss with respect to every weight. The trick is to unroll the RNN across time: think of the T recurrence steps as T copies of the same function, chained together into a very deep (but weight-tied) feedforward network. Then apply standard backpropagation on this unrolled graph.

Let the total loss be $\mathcal{L} = \sum_{t=1}^T \ell_t$ where $\ell_t$ depends on $h_t$. The gradient of $\mathcal{L}$ with respect to $W_{hh}$ accumulates contributions from every time step:

$$\frac{\partial \mathcal{L}}{\partial W_{hh}} = \sum_{t=1}^T \frac{\partial \ell_t}{\partial W_{hh}}$$

Each term requires computing $\frac{\partial h_t}{\partial h_k}$ for $k < t$, which by the chain rule through the recurrence is:

$$\frac{\partial h_t}{\partial h_k} = \prod_{i=k+1}^{t} \frac{\partial h_i}{\partial h_{i-1}} = \prod_{i=k+1}^{t} \text{diag}(\tanh'(\cdot)), W_{hh}$$

This is a product of $(t-k)$ Jacobian matrices. Gradients from step $t$ back to step $k$ must travel through this product.

Truncated BPTT: Because unrolling all T steps is memory-expensive (storing all intermediate activations), in practice we often truncate the backpropagation to a fixed window of $\tau$ steps. This trades exact gradient computation for feasibility on long sequences.

In code, frameworks like PyTorch handle this automatically by building a dynamic computation graph — loss.backward() unrolls and differentiates everything. The detach() operation cuts the gradient flow at a specific point, implementing truncated BPTT.

# Truncated BPTT in PyTorch
model = VanillaRNN(input_size=10, hidden_size=128, output_size=5)
optimizer = torch.optim.Adam(model.parameters())

def train_truncated_bptt(x_seq, targets, chunk_size=35):
    T = x_seq.size(0)
    h = torch.zeros(x_seq.size(1), 128)  # h_0, not tracked
    total_loss = 0
    for start in range(0, T, chunk_size):
        chunk = x_seq[start:start+chunk_size]
        tgt   = targets[start:start+chunk_size]
        outputs, h = model(chunk)  # forward on this chunk
        h = h.detach()             # CUT gradient flow at chunk boundary
        loss = nn.CrossEntropyLoss()(outputs.view(-1, 5), tgt.view(-1))
        optimizer.zero_grad()
        loss.backward()            # backprop only within this chunk
        optimizer.step()
        total_loss += loss.item()
    return total_loss

The product of Jacobians in BPTT is the root cause of the most notorious failure mode in sequence modeling.

Consider the simplified scalar recurrence $h_t = \tanh(w \cdot h_{t-1} + u \cdot x_t)$. The gradient flowing back $k$ steps is proportional to $w^k \cdot (\tanh'(\cdot))^k$. Since $|\tanh'(z)| \leq 1$ and achieves the maximum only near $z=0$, this product almost always shrinks exponentially with $k$:

$$\left|\frac{\partial h_t}{\partial h_{t-k}}\right| \approx (w \cdot \sigma)^k, \quad \sigma < 1$$

• If $|w \cdot \sigma| < 1$: gradients vanish — the network cannot learn dependencies spanning more than a handful of steps.
• If $|w \cdot \sigma| > 1$: gradients explode — training diverges with NaN losses.

Hochreiter's 1991 diploma thesis (later the 1997 LSTM paper) gave the first rigorous analysis of this phenomenon. The key insight: a standard RNN's hidden state must both (a) remember information (which requires large recurrent weights) and (b) be stable under gradient flow (which requires small recurrent weights). These two requirements are in fundamental tension.

Gradient clipping is a simple and effective patch for the exploding gradient side: if the global gradient norm exceeds a threshold, rescale the gradient vector to have that norm. This is now standard in every sequence model training loop.

torch.nn.utils.clip_grad_norm_(model.parameters(), max_norm=5.0)

But clipping does nothing for vanishing gradients. For that, we need architectural change — gating.

# Demonstrating vanishing gradients empirically
import numpy as np
import matplotlib.pyplot as plt

def simulate_gradient_flow(w, T=100):
    """Track gradient magnitude from step T back to step 1."""
    grad = 1.0  # start at step T
    grads = [grad]
    # tanh'(0) = 1 is the best case; use 0.9 as a realistic saturation factor
    sigma = 0.9
    for _ in range(T - 1):
        grad *= w * sigma
        grads.append(abs(grad))
    return grads

# w=0.9 -> vanishing; w=1.1 -> exploding
for w in [0.9, 1.0, 1.1]:
    g = simulate_gradient_flow(w)
    print(f'w={w}: grad at step 1 = {g[-1]:.2e}')
# w=0.9: grad at step 1 = 2.66e-10  (vanished)
# w=1.0: grad at step 1 = 1.22e-04  (slow decay)
# w=1.1: grad at step 1 = 1.36e+03  (exploded)

The LSTM, introduced by Hochreiter & Schmidhuber (1997), solves vanishing gradients with a clever architectural insight: separate the memory from the hidden state.

An LSTM maintains two vectors at each time step:

• Cell state $c_t \in \mathbb{R}^H$ — the long-term memory highway. Information flows along this highway with only element-wise operations (addition and multiplication), so gradients can travel through it with near-zero attenuation.
• Hidden state $h_t \in \mathbb{R}^H$ — the short-term working memory / output.

Three gates (each a sigmoid applied to a linear combination of $h_{t-1}$ and $x_t$, so values lie in $(0, 1)$) control information flow:

1. Forget gate $f_t = \sigma(W_f [h_{t-1}; x_t] + b_f)$: how much of the old cell state to keep.
2. Input gate $i_t = \sigma(W_i [h_{t-1}; x_t] + b_i)$: how much of the new candidate to write.
3. Output gate $o_t = \sigma(W_o [h_{t-1}; x_t] + b_o)$: how much of the cell to expose as hidden state.

And a candidate cell: $$\tilde{c}t = \tanh(W_c [h{t-1}; x_t] + b_c)$$

The cell update is: $$c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t$$

And the hidden state: $$h_t = o_t \odot \tanh(c_t)$$

The cell update is the key. When the forget gate is near 1 and the input gate near 0, $c_t \approx c_{t-1}$ — the cell state is copied forward unchanged, and the gradient through $\partial c_t / \partial c_{t-1} = f_t \approx 1$. This is the constant error carousel from Hochreiter's original analysis: gradients flow backward through time almost undamped.

Analogy: think of the cell state as a conveyor belt moving through a factory. The gates are workers who can read items off the belt (output gate), throw items on the belt (input gate), or toss old items off (forget gate). The belt itself runs freely without interference — no squashing, just arithmetic.

import torch
import torch.nn as nn

class LSTMCell(nn.Module):
    """Manual LSTM cell to make the equations explicit."""
    def __init__(self, input_size, hidden_size):
        super().__init__()
        H = hidden_size
        # All 4 gates computed in one matrix multiply for efficiency
        self.W = nn.Linear(input_size + H, 4 * H)  # [f, i, o, g]

    def forward(self, x, h_prev, c_prev):
        combined = torch.cat([h_prev, x], dim=1)
        gates = self.W(combined)                   # (B, 4H)
        H = gates.size(1) // 4
        f = torch.sigmoid(gates[:, :H])            # forget gate
        i = torch.sigmoid(gates[:, H:2*H])         # input gate
        o = torch.sigmoid(gates[:, 2*H:3*H])       # output gate
        g = torch.tanh(gates[:, 3*H:])             # candidate cell
        c = f * c_prev + i * g                     # cell state update
        h = o * torch.tanh(c)                      # hidden state
        return h, c

# PyTorch's built-in (faster, cuDNN-backed):
rnn = nn.LSTM(input_size=10, hidden_size=128, num_layers=2,
              batch_first=True, dropout=0.3)

The GRU (Cho et al., 2014) offers a streamlined alternative to the LSTM. It merges the cell state and hidden state into a single $h_t$, and uses only two gates:

1. Reset gate $r_t = \sigma(W_r [h_{t-1}; x_t])$: how much of the past hidden state to use when computing the candidate. When $r_t \approx 0$, the unit forgets the past entirely.
2. Update gate $z_t = \sigma(W_z [h_{t-1}; x_t])$: how much to blend the old hidden state with the new candidate — a convex interpolation.

$$\tilde{h}t = \tanh(W [r_t \odot h{t-1}; x_t])$$ $$h_t = (1 - z_t) \odot h_{t-1} + z_t \odot \tilde{h}_t$$

The update gate plays the combined role of LSTM's forget and input gates. When $z_t \approx 0$, $h_t \approx h_{t-1}$ — the hidden state is copied forward unchanged (same constant-error-carousel property). When $z_t \approx 1$, the new candidate completely replaces the old hidden state.

GRU vs LSTM:

• GRU has fewer parameters (~25% fewer) and often trains faster.
• On small datasets, GRUs often match or slightly outperform LSTMs.
• LSTMs tend to outperform GRUs on tasks requiring very precise memory management (e.g., tracking nested parentheses, long-document understanding).
• In practice, the difference is often small — try both and use validation performance to decide.

The key architectural advance both share: additive cell updates instead of the multiplicative path through tanh, letting gradients flow without shrinkage.

class GRUCell(nn.Module):
    """Manual GRU cell for pedagogical clarity."""
    def __init__(self, input_size, hidden_size):
        super().__init__()
        H = hidden_size
        self.W_r = nn.Linear(input_size + H, H)  # reset gate
        self.W_z = nn.Linear(input_size + H, H)  # update gate
        self.W_h = nn.Linear(input_size + H, H)  # candidate

    def forward(self, x, h_prev):
        combined = torch.cat([h_prev, x], dim=1)
        r = torch.sigmoid(self.W_r(combined))            # reset gate
        z = torch.sigmoid(self.W_z(combined))            # update gate
        candidate_input = torch.cat([r * h_prev, x], dim=1)
        h_cand = torch.tanh(self.W_h(candidate_input))  # candidate
        h = (1 - z) * h_prev + z * h_cand               # interpolate
        return h

# PyTorch's built-in:
gru = nn.GRU(input_size=10, hidden_size=128, num_layers=2, batch_first=True)

Many important tasks require mapping a sequence of one length to a sequence of another length: machine translation ("The cat sat" → "Le chat s'est assis"), speech-to-text, summarization, code generation. A single RNN cannot naturally handle variable-output-length tasks.

The encoder-decoder (also called seq2seq) architecture, introduced by Sutskever, Vinyals & Le (2014) and Cho et al. (2014), solves this:

1. Encoder RNN: Reads the input sequence $x_1, \ldots, x_T$ and compresses it into a fixed-length context vector $c = h_T^{\text{enc}}$ (the final hidden state).
2. Decoder RNN: Conditioned on $c$, generates the output sequence $y_1, \ldots, y_{T'}$ one token at a time, feeding each generated token back as the next input (autoregressive generation).

The encoder and decoder can be LSTMs or GRUs; they do not need to share weights.

The bottleneck problem. Compressing an arbitrarily long input into a single fixed-size vector is fundamentally lossy. For long sentences (>20 words), the context vector becomes a severe bottleneck and translation quality degrades. This motivated the development of the attention mechanism (Bahdanau et al., 2015), which lets the decoder look at all encoder hidden states at each decoding step via a learned weighted sum — not just the final one. Attention solved the bottleneck and later evolved into the multi-head self-attention of transformers.

class Encoder(nn.Module):
    def __init__(self, vocab, embed, hidden):
        super().__init__()
        self.embed = nn.Embedding(vocab, embed)
        self.rnn = nn.LSTM(embed, hidden, batch_first=True)
    def forward(self, src):       # src: (B, T)
        _, (h, c) = self.rnn(self.embed(src))
        return h, c               # context vectors

class Decoder(nn.Module):
    def __init__(self, vocab, embed, hidden):
        super().__init__()
        self.embed = nn.Embedding(vocab, embed)
        self.rnn = nn.LSTM(embed, hidden, batch_first=True)
        self.fc = nn.Linear(hidden, vocab)
    def forward(self, trg_token, h, c):
        # trg_token: (B,) one token at a time
        x = self.embed(trg_token.unsqueeze(1))  # (B, 1, embed)
        out, (h, c) = self.rnn(x, (h, c))
        pred = self.fc(out.squeeze(1))           # (B, vocab)
        return pred, h, c

# Autoregressive decoding loop (teacher forcing during training)
# for t in range(max_len):
#     pred, h, c = decoder(trg[:, t], h, c)

Training RNNs and LSTMs requires attention to several practical details that are less critical for feedforward networks.

Gradient clipping. Even with LSTMs, gradients can occasionally spike. Always clip: clip_grad_norm_(params, max_norm=5) before the optimizer step.

Initialization. The orthogonal initialization of $W_{hh}$ (or the recurrent weight matrix) is particularly effective: it preserves gradient norms at the start of training, giving the network a better chance to learn long-range dependencies before vanishing kicks in.

Dropout in RNNs. Standard dropout applied to recurrent connections disrupts the memory mechanism. Variational dropout (Gal & Ghahramani, 2016) uses the same dropout mask at every time step within an unroll — this respects the recurrent nature of the network. In PyTorch's nn.LSTM, the dropout parameter applies to the output of each layer (not the recurrent connection itself), which is a reasonable approximation.

Layer normalization. Layer norm applied to the hidden state at each step (not batch norm, which does not work well with variable-length sequences) significantly stabilizes training.

Stacked / deep RNNs. Multiple recurrent layers stacked vertically — the output sequence of layer $l$ feeds as the input sequence to layer $l+1$ — reliably improve performance on hard tasks. 2-4 layers is typical; more is rarely beneficial for vanilla LSTMs.

Bidirectional RNNs. For non-generative tasks (classification, named entity recognition), we can process the sequence both forward and backward, concatenating the two hidden states: $h_t^{bi} = [\overrightarrow{h}_t; \overleftarrow{h}_t]$. This doubles the effective receptive field at each position. nn.LSTM(bidirectional=True) handles this.

# Full training loop skeleton with best practices
model = nn.LSTM(input_size=128, hidden_size=256, num_layers=2,
                batch_first=True, dropout=0.3)
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
scheduler = torch.optim.lr_scheduler.ReduceLROnPlateau(optimizer)

# Orthogonal init for recurrent weights
for name, param in model.named_parameters():
    if 'weight_hh' in name:
        nn.init.orthogonal_(param)
    elif 'weight_ih' in name:
        nn.init.xavier_uniform_(param)
    elif 'bias' in name:
        nn.init.zeros_(param)
        # LSTM forget gate bias trick: initialize to 1
        # so the network starts by preferring to remember
        n = param.size(0)
        param.data[n//4 : n//2].fill_(1.0)

# Training step
def step(x, y):
    out, _ = model(x)              # (B, T, hidden)
    loss = criterion(out[:, -1], y)  # many-to-one
    optimizer.zero_grad()
    loss.backward()
    torch.nn.utils.clip_grad_norm_(model.parameters(), 5.0)  # clip!
    optimizer.step()

Understanding where RNNs break down makes the transformer's design immediately legible.

The three limitations of RNNs that attention addresses:

1. Sequential computation. An RNN at step $t$ depends on $h_{t-1}$, so it cannot be parallelized across time. Training on a sequence of length $T$ takes $O(T)$ sequential steps. Transformers compute all positions in parallel: $O(1)$ sequential steps, $O(T^2)$ total work (the attention matrix). For modern GPUs optimized for massive parallelism, the $T^2$ cost is a worthwhile trade.

2. Fixed-size bottleneck. The context vector $c = h_T$ must encode the entire input. The Bahdanau attention mechanism replaces this with a dynamic context vector at each decoding step: $c_t = \sum_i \alpha_{ti} h_i^{\text{enc}}$ where $\alpha_{ti}$ is a learned alignment score. Self-attention (in transformers) applies this idea to every position attending to every other position.

3. Gradient path length. Even with LSTMs, the gradient from $y_T$ back to $x_1$ must travel through $T$ multiplicative gates. With attention, any two positions are connected by a path of length $O(1)$ through the attention matrix — gradients are short-circuited across any distance.

The transformer (Vaswani et al., 2017) took gating all the way: replace recurrence entirely with multi-head self-attention + position encoding + feedforward blocks. Every advance since — BERT, GPT, T5, LLaMA — is a transformer. But the LSTM's gating intuition lives on: in transformers, the feedforward sublayer (with its expansion and contraction) plays an analogous role to the LSTM's cell, and the residual connections are the LSTM's constant-error highway made explicit.

# Bahdanau (additive) attention in a decoder step
class BahdanauAttention(nn.Module):
    def __init__(self, enc_hid, dec_hid):
        super().__init__()
        self.attn = nn.Linear(enc_hid + dec_hid, dec_hid)
        self.v    = nn.Linear(dec_hid, 1, bias=False)

    def forward(self, h_dec, enc_outputs):
        # h_dec: (B, dec_hid), enc_outputs: (B, T, enc_hid)
        T = enc_outputs.size(1)
        h_dec_exp = h_dec.unsqueeze(1).expand(-1, T, -1)  # (B, T, dec_hid)
        energy = torch.tanh(self.attn(
            torch.cat([h_dec_exp, enc_outputs], dim=2)))    # (B, T, dec_hid)
        attention = torch.softmax(self.v(energy).squeeze(2), dim=1)  # (B, T)
        context = (attention.unsqueeze(2) * enc_outputs).sum(dim=1)  # (B, enc_hid)
        return context, attention  # context replaces the fixed c = h_T