Recurrent Models for NLP

A recurrent neural network processes a sequence of tokens $x_1, x_2, \dots, x_T$ by maintaining a hidden state $h_t \in \mathbb{R}^d$ that is updated at every time step according to a shared transition function:

The same parameters are reused at every step — this parameter sharing across time is what lets an RNN handle sequences of any length with a fixed-size model. Each $x_t$ is typically a word embedding (see Word Embeddings and Dense Vectors), and $h_t$ is meant to summarize the entire prefix $x_1, \dots, x_t$. Because $h_t$ depends on $h_{t-1}$ which depends on $h_{t-2}$, and so on, information from arbitrarily far back can in principle influence the current prediction — this is the defining advantage over fixed-window models. The core difficulty is long-range dependency learning. Training an RNN uses backpropagation through time (BPTT): the recurrence is "unrolled" into a deep computational graph with one layer per time step, and gradients are propagated backward through this unrolled graph. Because the same weight matrix $W_{hh}$ is applied repeatedly, the gradient of the loss at step $T$ with respect to the hidden state at step $t$ involves a product of $T-t$ Jacobians. If the dominant eigenvalues of these Jacobians are consistently below 1, the product shrinks toward zero (vanishing gradients); if consistently above 1, it blows up (exploding gradients). Either failure prevents the network from learning dependencies that span many steps.

Gated recurrent architectures — the LSTM and the GRU — solve this by introducing a separate, more slowly changing memory pathway and learned gates: small neural networks (typically sigmoid layers) that output values in $[0,1]$ controlling how much information flows through, is overwritten, or is forgotten at each step. The key structural trick is an additive update to memory, rather than a purely multiplicative one, which creates a path along which gradients can flow with a multiplier close to 1 across many time steps.

Vanilla RNN cell. At each step $t$, given input $x_t$ and previous hidden state $h_{t-1}$:

For language modeling, $\hat{y}_t$ is a distribution over the vocabulary predicting $x_{t+1}$, and the loss is the sum of per-step cross-entropies.

LSTM cell. The LSTM maintains two vectors per time step: a hidden state $h_t$ (used for output) and a cell state $c_t$ (the long-term memory highway). Three gates and one candidate value are computed from $x_t$ and $h_{t-1}$:

Here $[h_{t-1}, x_t]$ denotes concatenation, $\sigma$ is the sigmoid function, and $\odot$ is elementwise multiplication. The forget gate decides how much old memory to keep; the input gate decides how much new candidate content to add; the output gate decides how much of the cell state to expose as the hidden state.

GRU cell. The GRU merges the cell and hidden state into one vector and uses two gates:

The update gate $z_t$ directly interpolates between the old state and the new candidate — structurally similar to the LSTM's forget/input pairing but with one gate instead of two, and no separate cell state. Below is language-agnostic pseudocode for a full forward pass of a single-layer LSTM language model over a batch of sequences, followed by the BPTT gradient computation sketch. ```

# Forward pass: LSTM language model over a sequence of length T

# x[1..T] : input token embeddings, each in R^d_in

# h0, c0 : initial hidden and cell state, each in R^d_hidden (usually zero)

# Parameters : W_f, W_i, W_o, W_c (each R^(d_hidden x (d_hidden+d_in)))

# b_f, b_i, b_o, b_c (each R^d_hidden)

# W_hy, b_y (output projection to vocabulary) function LSTM_FORWARD(x[1..T], h0, c0): h[0] = h0 c[0] = c0 for t = 1 to T: z = concat(h[t-1], x[t]) # (d_hidden + d_in)-dim vector f_t = sigmoid(W_f @ z + b_f) # forget gate i_t = sigmoid(W_i @ z + b_i) # input gate o_t = sigmoid(W_o @ z + b_o) # output gate c_tilde = tanh(W_c @ z + b_c) # candidate cell content c[t] = f_t c[t-1] + i_t c_tilde # elementwise; update cell memory h[t] = o_t * tanh(c[t]) # elementwise; expose hidden state logits[t] = W_hy @ h[t] + b_y yhat[t] = softmax(logits[t]) # predicted distribution over vocab return h[1..T], c[1..T], yhat[1..T]

function LSTM_LOSS(yhat[1..T], targets[1..T]): loss = 0 for t = 1 to T: loss += cross_entropy(yhat[t], targets[t]) # -log P(target_t) return loss / T

# Training step: unroll T steps, compute loss, backpropagate through time function TRAIN_STEP(x[1..T], targets[1..T], params, h0, c0): h[], c[], yhat[] = LSTM_FORWARD(x, h0, c0) loss = LSTM_LOSS(yhat, targets) grads = BACKPROP(loss, params) # reverse-mode autodiff through the

# unrolled T-step computation graph;

# gradients w.r.t. shared params are

# SUMMED across all T time steps CLIP_GRADIENT_NORM(grads, max_norm) # guard against exploding gradients params = OPTIMIZER_UPDATE(params, grads) return params, loss ``` The essential correctness property to notice: because $W_f, W_i, W_o, W_c$ (and the vanilla RNN's $W_{hh}$) are shared across all time steps, backpropagation must accumulate their gradients by summing the contribution from every step $t$ — this is what "backpropagation through time" specifically means, as opposed to ordinary backpropagation in a feedforward net where each layer has distinct parameters.

Time complexity. For a sequence of length $T$, hidden size $d$, and input embedding size $e$, each vanilla RNN step costs $O(d(d+e))$ for the matrix-vector products, so a full forward pass costs $O(T \cdot d(d+e))$. An LSTM computes four such affine transforms per step (three gates plus the candidate), so its cost is $O(4 \cdot T \cdot d(d+e)) = O(T d(d+e))$ up to a constant factor; a GRU uses three transforms, landing between the two. Backpropagation through time has the same asymptotic cost as the forward pass, since each step's backward computation mirrors its forward computation (standard for reverse-mode autodiff).

Space complexity. Naively, BPTT must store every intermediate activation ($h_t$, gate values, candidate values) for all $T$ steps to compute gradients on the backward pass, costing $O(T \cdot d)$ memory. This is the key sequential bottleneck: unlike a Transformer's attention layer, which computes all positions in parallel, an RNN's step $t$ depends on the output of step $t-1$, so steps cannot be parallelized across time — only across the batch dimension. Truncated BPTT (backpropagating only $k \ll T$ steps at a time, carrying $h_t$ forward without gradient) trades correctness of the gradient (it becomes a biased estimate of the true gradient) for a memory bound of $O(k \cdot d)$ and enables training on arbitrarily long streams.

Why gradients vanish or explode (proof sketch). Consider a simplified vanilla RNN recurrence $h_t = \tanh(W_{hh} h_{t-1} + \cdots)$. By the chain rule,

Each factor's operator norm is bounded by $\|W_{hh}\| \cdot \max|\tanh'| \le \|W_{hh}\|$ (since $\tanh' \le 1$). If the largest singular value of $W_{hh}$ is consistently less than 1, this product shrinks geometrically in $T-t$, so $\partial h_T / \partial h_t \to 0$ — the gradient signal from a distant time step vanishes before it can update earlier weights, explaining why vanilla RNNs struggle to learn dependencies beyond roughly 5-10 tokens in practice. If the largest singular value exceeds 1, the product can grow geometrically instead, causing exploding gradients (visible as sudden loss spikes or NaNs during training), which is why gradient clipping is standard practice.

Why LSTMs fix this. The cell-state recurrence $c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t$ gives

directly (with no matrix multiplication and no squashing nonlinearity in this particular path). If the network learns to keep $f_t \approx 1$ for the time steps spanning a long-range dependency, this Jacobian is close to the identity, so gradients can flow across many steps with no multiplicative decay — this is the celebrated "constant error carousel" argument that motivated the LSTM's design. The gates themselves are learned, so the network adaptively decides which information deserves this near-lossless path, rather than every path having this property indiscriminately (which would make forgetting impossible).

Correctness of BPTT itself. BPTT is not an approximation of backpropagation; it is exact reverse-mode automatic differentiation applied to the unrolled computational graph, which is a finite, well-defined directed acyclic graph once weight-sharing is accounted for (the same weight tensor appears as a node reused at $T$ positions, and its gradient is the sum of the partials from each occurrence — a direct consequence of the multivariate chain rule for a variable used in multiple places). This is why RNNs train with the exact same guarantees as any feedforward network with tied weights.

Honest tradeoffs. LSTMs/GRUs mitigate but do not eliminate the vanishing gradient problem — extremely long sequences (thousands of tokens) still degrade performance. Their fundamentally sequential computation makes them harder to parallelize on GPUs than Transformers, which is a major reason attention-based architectures displaced them for large-scale training, even though RNNs remain attractive for streaming/online inference where output must be produced token-by-token with $O(d^2)$ per-step cost rather than attending over a growing context.

Consider language modeling on the tiny sentence "the cat sat" with a toy vocabulary and a hidden size of 2, to make the LSTM cell-state update mechanics fully concrete. Suppose (after training) the forget gate for the third word ("sat") has learned to be close to 1 in the dimension that tracks "subject established," while other gates modulate the rest.

Reading the second hidden dimension across steps: the forget gate stays high ($0.5 \to 0.9 \to 0.95$) once "cat" establishes the subject, so the candidate contributions from "sat" ($\tilde c_3[1] = 0.9$) get blended with, rather than overwrite, the memory of "cat" ($c_2[1]=0.14$), giving $c_3[1] = 0.95 \times 0.14 + 0.3 \times 0.9 = 0.40$. This is exactly the mechanism that lets the model retain "the subject is a cat" long enough to correctly predict a subject-agreeing verb form, even if several more words intervened before "sat." Contrast with a vanilla RNN on the same input: its single hidden state at each step is entirely recomputed as $\tanh(W_{xh}x_t + W_{hh}h_{t-1} + b)$, with no gated, additive channel — so the influence of "the" at step 1 on $h_3$ is attenuated by two full multiplications through $W_{hh}$ and two $\tanh$ squashings, illustrating concretely why the vanilla model's memory decays faster than the LSTM's gated cell state.

Recurrent architectures for sequence modeling emerged from a lineage connecting theoretical neuroscience-inspired networks to a rigorous fix for a gradient pathology.

Gated recurrent networks powered the first generation of production neural NLP systems: Google's early Neural Machine Translation system (GNMT, 2016) used stacked LSTM encoder-decoders, and LSTMs were standard in speech recognition acoustic and language models, autocomplete systems, and named-entity recognition pipelines throughout the mid-2010s. Bidirectional LSTMs (processing a sequence forward and backward and concatenating both hidden states) became a default building block for sequence-labeling tasks like part-of-speech tagging and named-entity recognition, and formed the backbone of early Contextual Embeddings such as ELMo, which stacked bidirectional LSTMs to produce context-sensitive word representations — a direct conceptual predecessor to Transformer-based contextual models. RNN encoder-decoder pairs also established the Sequence-to-Sequence Models paradigm (encode a source sequence into a fixed vector or set of hidden states, then decode a target sequence), which persists conceptually even as the encoder and decoder internals shifted to attention and self-attention. Today, pure RNNs are less common at the frontier of large language models, but their gating principles persist in modern efficient-attention alternatives (state-space models, linear attention variants), and LSTMs/GRUs remain practical choices for low-latency streaming applications, resource-constrained on-device inference, and time-series or sensor-fusion tasks adjacent to NLP where strict sequential processing and small model footprints are valued over maximal parallelism.

Ask the tutor: Can you walk through, step by step, how the gradient of the loss at time step 5 flows back to the input at time step 1 in an LSTM versus a vanilla RNN?