---
title: RNNs and LSTMs
module: Sequences
moduleNumber: 4
lessonNumber: 3
order: 403
summary: >
  A feedforward neural language model sees a fixed window of words and can look no
  further back. The recurrent neural network removes that limit: it carries a hidden
  state across time, so each word is read in the context of everything before it. We
  build the RNN from its one recurrent equation, use it as a language model, train it
  by backpropagation through time, and diagnose the vanishing-gradient problem that
  makes plain RNNs forget. The LSTM fixes the forgetting with a cell state and three
  gates, and the encoder-decoder stacks two RNNs into a sequence-to-sequence model —
  and its single-vector bottleneck is the problem attention was invented to remove.
topics: [Sequences]
sources:
  - book: Jurafsky
    ref: "Ch. 9 — Deep Learning Architectures for Sequence Processing; §9.2 Recurrent Neural Networks; §9.3 RNNs as Language Models"
  - book: Jurafsky
    ref: "§9.4 RNNs for other NLP tasks; §9.5 Stacked and Bidirectional RNNs; §9.6 The LSTM; Ch. 10 — The Encoder-Decoder Model"
---

The [feedforward neural language model](/natural-language-processing/semantics/neural-language-models)
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.[^jm-rnn] 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:

$$
\mathbf{h}_t \;=\; g\!\left(\mathbf{U}\mathbf{h}_{t-1} + \mathbf{W}\mathbf{x}_t\right),
$$

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:

$$
\mathbf{y}_t \;=\; \mathrm{softmax}\!\left(\mathbf{V}\mathbf{h}_t\right).
$$

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.

$$
% caption: One RNN cell. The current input $\mathbf{x}_t$ and the previous hidden state
% $\mathbf{h}_{t-1}$ combine through $\mathbf{W}$ and $\mathbf{U}$ into the new hidden state
% $\mathbf{h}_t$, which both feeds the output $\mathbf{y}_t$ and is passed forward in time.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=13mm, minimum height=9mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (x)  at (0,0)   {x(t)};
  \node[box, draw=acc, text=acc, thick] (h) at (0,1.9) {h(t)};
  \node[box] (y)  at (0,3.8) {y(t)};
  \draw[->, acc, thick] (x) -- (h) node[midway, right, font=\scriptsize] {W};
  \draw[->, acc, thick] (h) -- (y) node[midway, right, font=\scriptsize] {V};
  % recurrent self-loop carrying h(t-1) into h(t)
  \draw[->, thick] (h.north west) .. controls (-1.8,3.1) and (-1.8,0.7) .. (h.south west);
  \node[font=\scriptsize, anchor=east] at (-1.85,1.9) {U (from h(t-1))};
\end{tikzpicture}
$$

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).

$$
% caption: The same RNN unrolled across three steps. Layers are recomputed at every step,
% but the weights $\mathbf{U}$, $\mathbf{V}$, $\mathbf{W}$ are shared; the hidden state is
% the one wire that carries context from each step to the next.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=11mm, minimum height=8mm, align=center},
  hbox/.style={draw=acc, text=acc, thick, minimum width=11mm, minimum height=8mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \t/\xx in {1/0, 2/3.3, 3/6.6}{
    \node[box]  (x\t) at (\xx,0)   {x(\t)};
    \node[hbox] (h\t) at (\xx,1.9) {h(\t)};
    \node[box]  (y\t) at (\xx,3.8) {y(\t)};
    \draw[->, acc, thick] (x\t) -- (h\t) node[midway, right, font=\scriptsize] {W};
    \draw[->, acc, thick] (h\t) -- (y\t) node[midway, right, font=\scriptsize] {V};
  }
  \node[left=2mm of h1, font=\scriptsize] {h(0)};
  \draw[->, thick] ($(h1.west)+(-1.3,0)$) -- (h1.west);
  \draw[->, thick] (h1) -- (h2) node[midway, above, font=\scriptsize] {U};
  \draw[->, thick] (h2) -- (h3) node[midway, above, font=\scriptsize] {U};
\end{tikzpicture}
$$

> **Definition (Recurrent neural network).** A network that computes a sequence of hidden
> states $\mathbf{h}_1, \ldots, \mathbf{h}_n$ by the recurrence
> $\mathbf{h}_t = g(\mathbf{U}\mathbf{h}_{t-1} + \mathbf{W}\mathbf{x}_t)$, sharing the
> weights $\mathbf{U}$, $\mathbf{W}$ across all $t$. The state $\mathbf{h}_t$ encodes the
> whole prefix $\mathbf{x}_1, \ldots, \mathbf{x}_t$, so context is not bounded by a fixed
> window.

### 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.

```algorithm
caption: $\textsc{Forward-RNN}(\mathbf{x}, \mathit{network})$ — map an input sequence to outputs
input: sequence $\mathbf{x} = \mathbf{x}_1, \ldots, \mathbf{x}_n$; weights $\mathbf{U}, \mathbf{V}, \mathbf{W}$
$\mathbf{h}_0 \gets \mathbf{0}$
for $t = 1$ to $n$ do
  $\mathbf{h}_t \gets g(\mathbf{U}\mathbf{h}_{t-1} + \mathbf{W}\mathbf{x}_t)$ // carry context forward
  $\mathbf{y}_t \gets f(\mathbf{V}\mathbf{h}_t)$ // read the output
return $\mathbf{y}_1, \ldots, \mathbf{y}_n$
```

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.[^jm-lm] 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:

$$
\mathbf{e}_t \;=\; \mathbf{E}\mathbf{x}_t, \qquad
\mathbf{h}_t \;=\; g\!\left(\mathbf{U}\mathbf{h}_{t-1} + \mathbf{W}\mathbf{e}_t\right), \qquad
\mathbf{y}_t \;=\; \mathrm{softmax}\!\left(\mathbf{V}\mathbf{h}_t\right).
$$

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, \ldots, w_t) =
\mathbf{y}_t[i]$. The probability of a whole sequence is the product across positions,

$$
P(w_{1:n}) \;=\; \prod_{i=1}^{n} P(w_i \mid w_{1:i-1}) \;=\; \prod_{i=1}^{n} \mathbf{y}_i[w_i],
$$

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:

$$
L_{\mathrm{CE}}(\hat{\mathbf{y}}_t, \mathbf{y}_t) \;=\; -\log \hat{\mathbf{y}}_t[w_{t+1}].
$$

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.

$$
% caption: Training an RNN language model. Each step reads its input embedding, updates the
% hidden state, and produces a softmax over the vocabulary; the loss is the negative log
% probability of the true next word, averaged across the sequence.
\begin{tikzpicture}[>=stealth, font=\small,
  emb/.style={draw, minimum width=9mm, minimum height=6mm, align=center, font=\scriptsize},
  rbox/.style={draw=acc, text=acc, thick, minimum width=9mm, minimum height=8mm, align=center},
  sm/.style={draw, minimum width=9mm, minimum height=6mm, align=center, font=\scriptsize},
  ls/.style={draw, minimum width=13mm, minimum height=6mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \def\dx{2.7}
  \foreach \i/\w/\nw in {0/So/long, 1/long/and, 2/and/thanks, 3/thanks/for}{
    \node[emb] (e\i) at (\i*\dx,0)   {\w};
    \node[rbox] (h\i) at (\i*\dx,1.5) {h};
    \node[sm]  (s\i) at (\i*\dx,3.0) {softmax};
    \node[ls]  (l\i) at (\i*\dx,4.4) {-log y(\nw)};
    \draw[->, acc, thick] (e\i) -- (h\i);
    \draw[->, acc, thick] (h\i) -- (s\i);
    \draw[->, thick] (s\i) -- (l\i);
  }
  \foreach \i [evaluate=\i as \j using int(\i+1)] in {0,1,2}{
    \draw[->, thick] (h\i) -- (h\j) node[midway, above, font=\scriptsize] {h};
  }
  \node[font=\scriptsize, anchor=east] at (-0.8,0)   {input};
  \node[font=\scriptsize, anchor=east] at (-0.8,1.5) {RNN};
  \node[font=\scriptsize, anchor=east] at (-0.8,4.4) {loss};
\end{tikzpicture}
$$

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](/natural-language-processing/sequences/sequence-labeling)
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).[^jm-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:

$$
\frac{\partial L_3}{\partial \mathbf{h}_1} = \frac{\partial L_3}{\partial \mathbf{h}_3}\;
\frac{\partial \mathbf{h}_3}{\partial \mathbf{h}_2}\;
\frac{\partial \mathbf{h}_2}{\partial \mathbf{h}_1},
\qquad
\frac{\partial \mathbf{h}_t}{\partial \mathbf{h}_{t-1}} = \mathrm{diag}\!\left(g'(\mathbf{z}_t)\right)\mathbf{U},
$$

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')\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.

$$
% caption: The per-step multiplier compounds geometrically over $k$ steps back. With a
% factor of $0.6$ per hop the gradient scale is $0.6^k$: it falls below $0.01$ by about
% eight steps, so context more than a few words back gets a negligible learning signal.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.4,0) node[right, black, font=\scriptsize] {steps back k};
  \draw[->, black] (0,0) -- (0,3.3) node[above, black, font=\scriptsize] {gradient scale};
  % plot 3*0.6^x for x=0..10 (scaled)
  \draw[acc, very thick, domain=0:10, samples=40, variable=\k]
    plot ({\k*0.68}, {3*pow(0.6,\k)});
  \node[acc, anchor=west] at (5.0,0.55) {0.6 to the k};
  % markers
  \foreach \k/\lab in {0/1, 5/5, 10/10}
    \node[font=\scriptsize, anchor=north] at (\k*0.68,-0.05) {\lab};
  % 0.01 threshold line
  \draw[red, dashed] (0,0.09) -- (7.0,0.09);
  \node[red, anchor=south east, font=\scriptsize] at (7.0,0.1) {below 0.01};
\end{tikzpicture}
$$

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.[^jm-vanish]

$$
% caption: The gradient's magnitude as it is propagated back through time, one recurrent hop
% per step. Multiplying by a factor below one at each hop shrinks it geometrically, so distant
% steps get almost no learning signal — the vanishing-gradient problem.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (8.4,0) node[right, black, font=\scriptsize] {steps back};
  \draw[->, black] (0,0) -- (0,3.4) node[above, black, font=\scriptsize] {gradient size};
  % decaying gradient bars
  \foreach \i/\hh in {1/3.0, 2/1.95, 3/1.27, 4/0.82, 5/0.53, 6/0.35, 7/0.22}{
    \fill[acc!25, draw=acc] (\i-0.28,0) rectangle (\i+0.28,\hh);
  }
  % decay curve just past the bar tops
  \draw[red, very thick]
    (1,3.0) .. controls (2,2.1) and (3,1.3) .. (4,0.82)
    .. controls (5,0.5) and (6,0.3) .. (7,0.22);
  \node[red, anchor=west] at (7.15,0.22) {vanishes};
  % x tick labels
  \foreach \i/\lab in {1/1, 4/4, 7/7}
    \node[font=\scriptsize, anchor=north] at (\i,-0.05) {\lab};
\end{tikzpicture}
$$

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.[^jm-lstm] 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:

$$
\mathbf{f}_t \;=\; \sigma\!\left(\mathbf{U}_f\mathbf{h}_{t-1} + \mathbf{W}_f\mathbf{x}_t\right),
\qquad
\mathbf{k}_t \;=\; \mathbf{c}_{t-1} \odot \mathbf{f}_t.
$$

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

$$
\mathbf{g}_t \;=\; \tanh\!\left(\mathbf{U}_g\mathbf{h}_{t-1} + \mathbf{W}_g\mathbf{x}_t\right).
$$

**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:

$$
\mathbf{i}_t \;=\; \sigma\!\left(\mathbf{U}_i\mathbf{h}_{t-1} + \mathbf{W}_i\mathbf{x}_t\right),
\qquad
\mathbf{c}_t \;=\; \mathbf{k}_t + \mathbf{g}_t \odot \mathbf{i}_t.
$$

**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:

$$
\mathbf{o}_t \;=\; \sigma\!\left(\mathbf{U}_o\mathbf{h}_{t-1} + \mathbf{W}_o\mathbf{x}_t\right),
\qquad
\mathbf{h}_t \;=\; \mathbf{o}_t \odot \tanh(\mathbf{c}_t).
$$

$$
% caption: A single LSTM cell. The previous cell state $\mathbf{c}_{t-1}$ flows along the top,
% multiplied by the forget gate $f$ then added to the gated candidate ($g$ selected by the input
% gate $i$); the output gate $o$ reads $\tanh(\mathbf{c}_t)$ into the new hidden state $\mathbf{h}_t$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  io/.style={draw, minimum width=11mm, minimum height=6mm, align=center, font=\scriptsize},
  gate/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  op/.style={draw, circle, minimum size=6mm, inner sep=0pt, font=\scriptsize},
  tn/.style={draw, minimum width=9mm, minimum height=5mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % inputs on the left
  \node[io] (cprev) at (0,4.2) {c(t-1)};
  \node[io] (hprev) at (0,2.1) {h(t-1)};
  \node[io] (x)     at (0,0.4) {x(t)};
  % cell-state line across the top
  \node[op] (fmul) at (3.2,4.2) {x};
  \node[op] (add)  at (6.4,4.2) {+};
  \node[io, draw=acc, text=acc, thick] (ct) at (9.4,4.2) {c(t)};
  \draw[->, thick] (cprev) -- (fmul);
  \draw[->, thick] (fmul) -- (add);
  \draw[->, acc, thick] (add) -- (ct);
  % gates (well spaced, no overlaps)
  \node[gate] (f) at (3.2,2.4) {f};
  \node[gate] (g) at (5.0,1.0) {g};
  \node[gate] (i) at (5.0,2.5) {i};
  \node[op]   (gi) at (6.4,1.0) {x};
  \node[gate] (o) at (9.4,1.0) {o};
  \node[op]   (omul) at (9.4,2.6) {x};
  \node[tn]   (th)   at (7.9,3.3) {tanh};
  \node[io, draw=acc, text=acc, thick] (ht) at (11.4,1.0) {h(t)};
  % gate feeds from h(t-1) and x(t) into forget gate
  \draw[->, black] (hprev) -- (f);
  \draw[->, black] (x) .. controls (1.4,0.4) and (2.2,1.4) .. (f.south);
  \draw[->, thick] (f) -- (fmul);
  % candidate g gated by i, into the add (i sits off the vertical gi->add line)
  \draw[->, thick] (g) -- (gi);
  \draw[->, thick] (i) .. controls (5.6,2.3) and (6.0,1.6) .. (gi.north west);
  \draw[->, thick] (gi) -- (add);
  % output path: c(t) -> tanh -> omul (gated by o) -> h(t)
  \draw[->, thick] (ct) .. controls (9.4,3.7) and (8.6,3.6) .. (th);
  \draw[->, thick] (th) .. controls (8.8,2.9) and (9.4,3.1) .. (omul);
  \draw[->, thick] (o) -- (omul);
  \draw[->, thick] (omul) .. controls (10.3,2.2) and (11.4,2.0) .. (ht);
  \draw[dashed, black] (-0.9,-0.2) rectangle (12.3,5.1);
  \node[anchor=south east, font=\itshape, black] at (12.2,-0.15) {LSTM};
\end{tikzpicture}
$$

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 + \ldots$ 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.

> **Definition (LSTM gate).** A feedforward layer followed by a sigmoid, whose output in
> $[0,1]^d$ is multiplied element-wise into the vector it controls. The **forget gate** removes
> information from the cell, the **input gate** admits new information, and the **output gate**
> exposes the cell as the hidden state. Sigmoid gates turn context management into learned,
> differentiable masking.

### 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

$$
c_{\text{new}} = f \cdot c_{\text{old}} + i \cdot g = 0.95(1.0) + 0.05(-0.8) = 0.95 - 0.04 = 0.91.
$$

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} + \ldots$, 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](/deep-learning/architectures/lstm-and-gru) lesson; the RNN
recurrence and BPTT are treated in
[recurrent networks](/deep-learning/architectures/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).[^hochreiter] 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).[^seq2seq] 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).[^bahdanau] 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](/natural-language-processing/transformers/transformers-and-attention)
(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:

$$
\mathbf{h}_t^{f} = \mathrm{RNN}_{\text{forward}}(\mathbf{x}_1, \ldots, \mathbf{x}_t), \qquad
\mathbf{h}_t^{b} = \mathrm{RNN}_{\text{backward}}(\mathbf{x}_t, \ldots, \mathbf{x}_n), \qquad
\mathbf{h}_t = [\mathbf{h}_t^{f} \oplus \mathbf{h}_t^{b}].
$$

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

$$
% caption: A bidirectional RNN. A forward RNN and a backward RNN process the sequence in opposite
% directions; their hidden states are concatenated at each position so every output sees both the
% left and the right context.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=8mm, minimum height=7mm, align=center, font=\scriptsize},
  ob/.style={draw, minimum width=8mm, minimum height=6mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \def\dx{2.4}
  \foreach \i in {1,2,3}{
    \node[box] (x\i) at (\i*\dx,0)   {x(\i)};
    \node[box] (f\i) at (\i*\dx,1.5) {f};
    \node[box] (b\i) at (\i*\dx,3.0) {b};
    \node[ob]  (y\i) at (\i*\dx,4.5) {y(\i)};
    \draw[->, thick] (x\i) -- (f\i);
    \draw[->, thick] (f\i) -- (y\i);
    \draw[->, thick] (b\i) -- (y\i);
  }
  % forward chain L->R
  \draw[->, acc, thick] (f1) -- (f2);
  \draw[->, acc, thick] (f2) -- (f3);
  % backward chain R->L
  \draw[->, thick] (b3) -- (b2);
  \draw[->, thick] (b2) -- (b1);
  \node[acc, font=\scriptsize, anchor=west] at (3*\dx+0.35,1.5) {forward pass};
  \node[font=\scriptsize, anchor=west] at (3*\dx+0.35,3.0) {backward pass};
\end{tikzpicture}
$$

## 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.[^jm-seq2seq]

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.

$$
% caption: The encoder-decoder model. The encoder RNN compresses the whole source into a single
% context vector $\mathbf{c}$, which seeds the decoder RNN; the decoder generates the target
% autoregressively. Everything the decoder knows about the source must pass through $\mathbf{c}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=10mm, minimum height=7mm, align=center, font=\scriptsize},
  cb/.style={draw=acc, text=acc, thick, minimum width=11mm, minimum height=7mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \def\dx{2.0}
  % encoder
  \foreach \i/\w in {1/le, 2/chat, 3/dort}{
    \node[box] (e\i) at (\i*\dx,0) {\w};
    \node[box] (E\i) at (\i*\dx,1.5) {enc};
    \draw[->, thick] (e\i) -- (E\i);
  }
  \draw[->, acc, thick] (E1) -- (E2);
  \draw[->, acc, thick] (E2) -- (E3);
  % context vector, set apart from the last encoder box
  \node[cb] (c) at (3*\dx+2.2,1.5) {c};
  \draw[->, acc, thick] (E3) -- (c) node[midway, above, font=\scriptsize] {context};
  % decoder (start symbol as ASCII text, not a bracketed token)
  \foreach \i/\w/\nw in {1/start/the, 2/the/cat, 3/cat/sleeps}{
    \node[box] (D\i) at (3*\dx+2.2+\i*\dx,1.5) {dec};
    \node[box] (d\i) at (3*\dx+2.2+\i*\dx,0)   {\w};
    \node[box] (o\i) at (3*\dx+2.2+\i*\dx,3.0) {\nw};
    \draw[->, thick] (d\i) -- (D\i);
    \draw[->, thick] (D\i) -- (o\i);
  }
  \draw[->, acc, thick] (c) -- (D1);
  \draw[->, thick] (D1) -- (D2);
  \draw[->, thick] (D2) -- (D3);
  \node[font=\scriptsize, anchor=north] at (2*\dx,-0.8) {encoder (source)};
  \node[font=\scriptsize, anchor=north] at (3*\dx+2.2+2*\dx,-0.8) {decoder (target)};
\end{tikzpicture}
$$

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](/natural-language-processing/transformers/transformers-and-attention),
the subject of the next module.

[^jm-rnn]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), §9.2 — Recurrent Neural Networks: the Elman/simple recurrent network, the recurrence $\mathbf{h}_t = g(\mathbf{U}\mathbf{h}_{t-1} + \mathbf{W}\mathbf{x}_t)$, weight sharing across time, and unrolling the cycle into a feedforward graph.
[^jm-lm]: **Jurafsky & Martin**, §9.3 — RNNs as Language Models: next-word prediction with no fixed context window, the embedding-hidden-softmax forward pass, sequence probability as a product of per-step probabilities, and the cross-entropy training objective.
[^jm-bptt]: **Jurafsky & Martin**, §9.2.2 — Training: the two-pass backpropagation-through-time algorithm, saving hidden states forward and accumulating gradients backward through time, with the three weight matrices shared across steps.
[^jm-vanish]: **Jurafsky & Martin**, §9.6 — The LSTM (motivation): the difficulty of carrying distant information, the repeated multiplications during the backward pass that drive gradients to zero, and the vanishing-gradient problem.
[^jm-lstm]: **Jurafsky & Martin**, §9.6 — The LSTM: the explicit cell/context layer, the forget, input (add), and output gates as sigmoid-masked feedforward layers, and the additive cell update that lets gradients flow across many steps.
[^jm-seq2seq]: **Jurafsky & Martin**, Ch. 10 — The Encoder-Decoder Model: two RNNs joined by a context vector, the decoder as a conditioned autoregressive language model, and the fixed-length-context bottleneck that motivates attention.
[^hochreiter]: **Hochreiter and Schmidhuber (1997)**, _Long Short-Term Memory_, Neural Computation — the LSTM and its constant-error-carousel cell that keeps the recurrent gradient from vanishing or exploding; the forget gate was added by **Gers, Schmidhuber, and Cummins (2000)**, _Learning to Forget_, Neural Computation.
[^seq2seq]: **Sutskever, Vinyals, and Le (2014)**, _Sequence to Sequence Learning with Neural Networks_, NeurIPS — a deep LSTM encoder-decoder for machine translation, with source reversal; and **Cho et al. (2014)**, _Learning Phrase Representations using RNN Encoder-Decoder_, EMNLP — the GRU and the RNN encoder-decoder.
[^bahdanau]: **Bahdanau, Cho, and Bengio (2015)**, _Neural Machine Translation by Jointly Learning to Align and Translate_, ICLR — the attention mechanism that lets the decoder attend to all encoder states, removing the fixed-vector bottleneck; the recurrence-free **Vaswani et al. (2017)**, _Attention Is All You Need_, NeurIPS, is the transformer.