RNNs and LSTMs

The feedforward neural language model fixed the sparsity of n-grams by embedding words as vectors, but it kept one limitation from them: a fixed window. It reads the last $N-1$ words, concatenates their embeddings, and predicts the next word — and a word $N$ positions back is simply invisible. Widen the window and the input layer grows with it; the model still cannot condition on a subject that appeared twenty words ago. Linguistic dependencies span arbitrary distances: the verb in the keys to the cabinet are on the table agrees with keys, five words back, across a singular noun that would mislead any fixed-window guess.

The recurrent neural network removes the window entirely. Instead of reading a fixed window of recent words, it processes the sequence one token at a time and carries a hidden state forward from step to step. That state is a running summary of everything read so far, with no built-in limit on how far back it can reach.¹ This lesson builds the RNN from its one recurrent equation, turns it into a language model, trains it, finds the gradient problem that undermines it, and repairs that problem with the LSTM.

The recurrent equation

A recurrent network is any network with a cycle in its connections: the value of some unit depends, directly or indirectly, on its own earlier output. The constrained, well-behaved version used throughout language processing is the Elman network, or simple recurrent network. At each time step $t$ it takes the current input vector ${\mathbf{x}}_t$ and the hidden state ${\mathbf{h}}_{t-1}$ from the previous step, and produces a new hidden state:

where $g$ is a non-linearity (typically $\tanh$), $\mathbf{W}$ maps the input into the hidden layer, and $\mathbf{U}$ maps the previous hidden state into the current one. The recurrent matrix $\mathbf{U}$ is the whole difference from a feedforward network: it is how past context flows into the present. From the hidden state we read an output in the usual way, a softmax over classes for soft classification:

Three weight matrices define the network — $\mathbf{W}\in {\mathbb{R}}^{d_h\times d_{in}}$, $\mathbf{U}\in {\mathbb{R}}^{d_h\times d_h}$, $\mathbf{V}\in {\mathbb{R}}^{d_{out}\times d_h}$ — and, decisively, they are shared across every time step. The same $\mathbf{U}$ that carries step $1$'s context into step $2$ carries step $99$'s into step $100$. There is no per-position parameter and therefore no window; a sequence of any length is processed by the same small set of weights.

Written this way the recurrence looks like new machinery, but it is not. If we unroll the network in time — copy the cell once per time step and connect each copy's hidden state to the next — the cycle disappears and what remains is an ordinary feedforward computation, just a very deep one whose depth equals the sequence length. The copies are distinct in their values (each ${\mathbf{h}}_t$ differs) but identical in their weights ($\mathbf{U}$, $\mathbf{V}$, $\mathbf{W}$ are the same everywhere).

Forward inference

Because ${\mathbf{h}}_t$ needs ${\mathbf{h}}_{t-1}$, inference is inherently sequential: we sweep left to right, and at each step compute the hidden state from the previous one and read off the output. The whole forward pass is four lines.

The sequential dependence is both the strength (unbounded context) and the weakness (no parallelism across time) of the architecture, and that lack of parallelism is what later motivates the transformer.

Worked example: a two-step forward pass

Run the recurrence with tiny numbers. Take one-dimensional hidden and input states, $g=\tanh$, and weights $\mathbf{W}=0.8$, $\mathbf{U}=0.5$, with $h_0=0$. Feed the inputs $x_1=1.0$ then $x_2=-0.5$.

Step 1. The pre-activation is $\mathbf{U}{h}_0+\mathbf{W}{x}_1=0.5(0)+0.8(1.0)=0.8$, so $h_1=\tanh (0.8)=0.664$. The state now carries a trace of $x_1$.

Step 2. The pre-activation is $\mathbf{U}{h}_1+\mathbf{W}{x}_2=0.5(0.664)+0.8(-0.5)=0.332-0.400=-0.068$, so $h_2=\tanh (-0.068)=-0.068$. Notice that $h_2$ depends on $x_1$ only through $h_1$ — the recurrent term $\mathbf{U}{h}_1$ is the single channel by which step 1's information reaches step 2. This is the whole mechanism: everything the past contributes to the present flows through the one hidden wire, which is also why a weak recurrent weight (here $0.5$) attenuates old context, foreshadowing the vanishing gradient.

RNNs as language models

To use an RNN as a language model, run it over a corpus and, at each step, have it predict the next word from the current word and the hidden state.² Unlike the fixed-window neural model, the RNN has no context limit: ${\mathbf{h}}_t$ can in principle carry information from the very first word of the sequence.

At step $t$ the current word is looked up in the embedding matrix $\mathbf{E}$, combined with the previous hidden state, and turned into a distribution over the whole vocabulary:

The output ${\mathbf{y}}_t$ is a probability vector over the vocabulary; its $i$-th component is the model's estimate that word $i$ comes next, $P(w_{t+1}=i\mid w_1,\dots ,w_t)={\mathbf{y}}_t[i]$. The probability of a whole sequence is the product across positions,

where ${\mathbf{y}}_i[w_i]$ denotes the probability the model placed on the true word $w_i$ at step $i$.

Training and teacher forcing

The RNN is trained to minimize the cross-entropy of the true next word. Because the target distribution is a one-hot vector on the correct word $w_{t+1}$, the cross-entropy at step $t$ collapses to a single term, the negative log probability the model assigned to that word:

The loss for a training sequence is the average of these over all positions. One subtlety governs training: at each step we feed the model the correct history $w_{1:t}$, not the words it actually predicted. If the model guesses wrong at step $t$, we ignore that guess and still hand it the true $w_{1:t+1}$ for the next step. Always supplying the gold prefix is called teacher forcing, and it keeps training stable by preventing early mistakes from cascading.

The same trained model can generate text: seed it with a start symbol, sample a word from ${\mathbf{y}}_1$, feed that word back in as the next input, and repeat until an end symbol appears. Because each generated word is fed back as the next step's input, this is called autoregressive generation — the model conditions on its own choices, one word at a time.

RNNs slot into other tasks with only the output layer changed. For sequence labeling — the part-of-speech and named-entity tagging of the previous lesson — a softmax over the tagset at each step emits one label per token. For sequence classification, the final hidden state ${\mathbf{h}}_n$ serves as a compressed summary of the whole text and is fed to a feedforward classifier; the classification loss then backpropagates all the way through the RNN, an instance of end-to-end training.

Backpropagation through time

Training an unrolled RNN is ordinary backpropagation applied to the unrolled graph, with one new complication: a hidden state ${\mathbf{h}}_t$ influences the loss at every later step, because it feeds ${\mathbf{h}}_{t+1}$, which feeds ${\mathbf{h}}_{t+2}$, and so on. To find the gradient reaching ${\mathbf{h}}_t$ we must sum the error flowing back from all of those futures. The resulting two-pass algorithm — forward to compute and save every hidden state and loss, then backward through time to accumulate gradients — is backpropagation through time (BPTT).³

Because the weights are shared, each of $\mathbf{U}$, $\mathbf{V}$, $\mathbf{W}$ receives a gradient contribution from every time step; the per-step gradients are summed before the update. The mechanics are standard, but the shape of the backward pass has a consequence that governs whether the network can actually learn long-range structure.

Worked example: unrolling the backward chain

Unroll three steps and follow one gradient path. The loss at step $3$, call it $L_3$, depends on ${\mathbf{h}}_3$, which depends on ${\mathbf{h}}_2$, which depends on ${\mathbf{h}}_1$. The chain rule for the gradient of $L_3$ with respect to the earliest hidden state ${\mathbf{h}}_1$ is a product of per-step Jacobians:

where ${\mathbf{z}}_t=\mathbf{U}{\mathbf{h}}_{t-1}+\mathbf{W}{\mathbf{x}}_t$. Each hop back multiplies by the same factor $\mathrm{diag}(g^{\prime })\mathbf{U}$, so crossing $k$ steps multiplies by that factor $k$ times. For example, suppose the recurrent weight and the local derivative combine to a factor of $0.6$ per step. Then a gradient crossing $1$ step is scaled by $0.6$, across $5$ steps by $0.6^5=0.078$, across $10$ steps by $0.6^{10}=0.006$, and across $20$ steps by $0.6^{20}=0.00004$. The signal reaching a state twenty words back is four orders of magnitude weaker than the one reaching the immediately previous state.

The same product governs $\partial L/\partial \mathbf{U}$ and the other weight gradients, so a plain RNN cannot learn to connect a decision to context more than a handful of steps back — precisely the failure the next section names.

The vanishing-gradient problem

Consider how an error at step $t$ reaches a hidden state many steps earlier, at step $t-k$. The gradient must flow backward through the recurrence once per intervening step, and each such hop multiplies by the recurrent weight $\mathbf{U}$ and by the derivative of the non-linearity $g$. Over $k$ steps the signal is multiplied by roughly the same factor $k$ times — a geometric progression.

If that repeated factor is less than one, the product shrinks toward zero: the gradient vanishes, and the far-past hidden states receive essentially no learning signal. If the factor exceeds one, the product blows up and the gradient explodes. In practice, plain RNNs vanish far more often than they explode, and the effect is that the network cannot tie a decision to context more than a handful of steps back.⁴

The deeper diagnosis is that a plain RNN requires one hidden layer to do two conflicting jobs at once: supply the information the current step needs, and preserve information that some future step will need. Every write for the present overwrites part of the past. Consider the flights the airline was cancelling were full: the number of were depends on flights, but the intervening singular airline dominates the local context and the plural signal is written over long before it is needed. A network with a single, always-updated state has no way to hold a value aside untouched.

The LSTM

The long short-term memory network solves this by giving the unit a second state — a cell state ${\mathbf{c}}_t$ that runs alongside the hidden state and is engineered so that information can pass along it nearly unchanged.⁵ The network then learns, through small sub-networks called gates, which information to erase from the cell, which to add, and which to expose as output. Context management is learned rather than fixed.

Every gate shares one design: a feedforward layer, a sigmoid $\sigma$ squashing its output into $[0,1]$, and a pointwise (Hadamard) multiplication $\odot$ with the vector being gated. Because the sigmoid pushes toward $0$ or $1$, the gate acts as a soft binary mask — coordinates near $1$ pass through, coordinates near $0$ are erased.

The forget gate decides what to delete from the previous cell state. It reads the previous hidden state and current input, and its mask ${\mathbf{f}}_t$ multiplies ${\mathbf{c}}_{t-1}$ element-wise, zeroing out whatever is no longer relevant:

The candidate is the new information proposed for the cell — the same $\tanh$ computation a plain RNN would perform:

The input gate selects which of that candidate to actually add, then the surviving old context and the selected new context are summed into the updated cell state:

The output gate decides what of the cell to expose as the hidden state used for the current output and passed to the next step:

The gate that matters most for the gradient is the forget gate on the cell state. The cell update ${\mathbf{c}}_t={\mathbf{c}}_{t-1}\odot {\mathbf{f}}_t+\dots$ is (nearly) additive: when the forget gate stays open (${\mathbf{f}}_t\approx 1$), backpropagating through the cell multiplies the gradient by roughly $1$ at each step instead of by a shrinking factor. Context can sit in the cell across dozens of steps with its gradient intact — the additive path is what plain RNNs lacked, and the reason the LSTM can hold flights until were needs it.

Worked example: the forget gate holds a value

Take a single cell coordinate storing the subject is plural bit as $c=1.0$, and watch it survive intervening words. Suppose the network has learned, for this coordinate, a forget gate that stays near open ($f=0.95$) while it should keep the value, and near closed only when a new subject arrives.

A word that should not overwrite (say the distractor airline). The forget gate computes $f=0.95$, and the input gate computes $i=0.05$ with candidate $g=-0.8$ (a competing singular signal). The cell update is

The plural bit dropped only from $1.0$ to $0.91$ — the distractor barely dented it, because the input gate admitted little of the new candidate. Repeat this across five intervening words with the same gates and the value decays as $0.95^5\approx 0.77$, still clearly positive when the verb finally needs it. Contrast a plain RNN, whose single state would be overwritten by each word: with the tanh update of the earlier example, the plural signal is gone within two or three steps. The forget gate near $1$ is what turns the multiplicative decay into near-preservation.

The gradient view. Because $c_t=f_t\odot c_{t-1}+\dots$, the backward derivative $\partial c_t/\partial c_{t-1}=f_t$. When $f_t\approx 1$ the gradient crossing the cell is multiplied by $\approx 1$ per step instead of by the $\approx 0.6$ of the plain-RNN example — so $1^{20}=1$ where $0.6^{20}=0.00004$. The cell is a gradient-preserving path, and the forget gate controls it.

The full derivation of the gates, their gradients, and the additive cell-state path is in the deep-learning course's LSTM & GRU lesson; the RNN recurrence and BPTT are treated in recurrent networks.

The GRU

The LSTM's three gates and separate cell state are effective but heavy — four feedforward layers per unit. The gated recurrent unit (GRU) is a lighter design that keeps the same gradient-preserving idea with fewer parts: it drops the separate cell state and uses just two gates, a reset gate that controls how much past state enters the candidate and an update gate that interpolates between the old state and the candidate. It trains faster and often matches the LSTM's accuracy, so it is a common default when the LSTM's full capacity is not needed.

The LSTM lineage and the rise of attention

The recurrent architectures of this lesson have a precise public history, and the last step in it is the one that made them obsolete for translation.

The LSTM (Hochreiter and Schmidhuber, 1997).⁶ The long short-term memory unit was introduced two decades before it became standard, specifically to solve the vanishing-gradient problem this lesson diagnoses. Their analysis showed that a plain recurrent unit's error signal decays or explodes exponentially in the time lag, and their fix — the constant error carousel, an internal cell whose self-connection has weight $1$ so the gradient neither grows nor shrinks — coincides with the additive cell path above. The forget gate was added later (Gers, Schmidhuber, and Cummins, 2000) and is now part of the standard cell.

Sequence-to-sequence and the GRU (Sutskever, Vinyals, and Le, 2014; Cho et al., 2014).⁷ Two 2014 papers turned stacked LSTMs into machine-translation systems. Sutskever and colleagues trained a deep LSTM encoder-decoder end to end on English-French and reached a BLEU score competitive with phrase-based statistical systems; one trick carried much of the gain — reversing the source sentence so early source words sat near the decoder. Cho and colleagues introduced the GRU in the same encoder-decoder setting. Both hit the single-context-vector bottleneck this lesson closes on.

Attention (Bahdanau, Cho, and Bengio, 2015).⁸ The fix for the bottleneck was to let the decoder read a weighted combination of all encoder hidden states at each step, with the weights computed from how well each source position matches the current decoder state. Bahdanau and colleagues showed this align and translate mechanism removed the sharp quality drop on long sentences that the fixed-vector encoder-decoder suffered. Attention was first an add-on to an RNN; the transformer (Vaswani et al., 2017) then kept the attention and discarded the recurrence entirely, regaining the parallelism across time that the sequential RNN gave up — the exact weakness noted after the forward-inference algorithm above.

Stacked and bidirectional RNNs

The RNN cell is a module — vectors in, vectors out — so it composes in two useful ways.

A stacked RNN feeds the entire output sequence of one RNN as the input sequence of another, piling several layers deep. Lower layers induce local, concrete features; higher layers build more abstract representations on top, the same layered-abstraction argument that motivates depth elsewhere. Stacked RNNs generally outperform single-layer ones, though training cost rises with depth.

A bidirectional RNN addresses a different limitation: a left-to-right RNN's state at step $t$ knows only the words up to $t$, nothing to the right. For tasks where the whole input is available — labeling a token given its full sentence, classifying a complete document — the words after $t$ are informative too. A bidirectional RNN runs two independent RNNs, one forward and one backward over the reversed sequence, and concatenates their states at each position:

The combined ${\mathbf{h}}_t$ sees both the left and right context of position $t$ — the view a local labeling decision wants.

The encoder-decoder model

The tasks so far map an input sequence to an output of the same length — one tag per word, one label per document. Machine translation, summarization, and question answering are different: the output is a new sequence whose length and word order need not match the input at all. The architecture built for this is the encoder-decoder, or sequence-to-sequence, model.⁹

It is two RNNs joined at a single vector. The encoder reads the entire source sequence and compresses it into a fixed-length context vector — typically its final hidden state. The decoder is an autoregressive RNN language model whose initial state is that context vector; it generates the target sequence one token at a time, each step conditioned on the context and the words produced so far, until it emits an end symbol.

This design trains end-to-end on paired sequences and produced the first strong neural machine translation systems. But it has a structural flaw visible in the figure: everything the decoder learns about the source must squeeze through the single context vector $\mathbf{c}$. For a short sentence that is fine; for a long paragraph, one fixed-length vector cannot hold every detail, and translation quality falls as the source grows. The information bottleneck is inherent to compressing an arbitrarily long input into one vector.

The fix is to let the decoder look back at all of the encoder's hidden states, not just the final one, weighting them by relevance at each decoding step — the mechanism called attention. Attention removes the bottleneck, and once a model is built entirely out of attention with the recurrence removed, it becomes the transformer, the subject of the next module.