Handout — Recurrent Neural Language Models

Every model so far has looked at a fixed number of previous tokens: $n-1$ for an n-gram, whatever the window is for a fixed-window neural LM. Both are the same admission — that $p(x_t \mid x_{<t})$ has been replaced by $p(x_t \mid x_{t-k}, \dots, x_{t-1})$ because the real conditional has an argument of unbounded size. A recurrent network is the first architecture in this course that does not make that concession.

1What a fixed window cannot do

Handout #3's fixed-window model concatenates the embeddings of the previous $k$ tokens and pushes them through an MLP. It fixed the n-gram model's sparsity problem — similar contexts now share parameters — but it inherited the Markov assumption unchanged, and with it three separate defects.

Information older than $k$ is gone. Not down-weighted, not approximated — structurally unavailable. In "The keys that I left on the kitchen counter yesterday afternoon, next to the mail, are …", the number of the verb is determined by keys, thirteen tokens back. Any $k \le 13$ cannot get this right for the right reason.

Every position gets its own parameters. The input layer is $W \in \mathbb{R}^{d \times kd}$, so the weights that read the token at distance 1 are entirely separate from those that read distance 2. Nothing forces the model to learn "a noun three back" as the same kind of thing as "a noun two back"; it must learn each $k$ times over.

$k$ is a hyperparameter, and the cost of raising it is linear in parameters. Doubling the window doubles the first layer. Handling a document means a window of thousands.

2The recurrence

2.1  Three equations

Let $e_t = E\,x_t$ be the embedding of token $t$ (a row lookup, as in Handout #3 §1). The hidden state $h_t \in \mathbb{R}^{d_h}$ evolves as

and the prediction at each step reads off that state:

and the training objective is the same one it has been since Handout #2:

The parameters are $E, W_{hh}, W_{eh}, W_{ho}, b_h, b_o$ — and that is the entire model, for any sequence length. Compare the fixed-window model, whose first layer grows with $k$.

The last row is the one that bites, and Handout #6 §2 already explained why: reverse-mode differentiation must keep every intermediate activation until the backward pass reaches it. Parameters are constant in $T$; memory is not.

2.2  What "recurrent" buys, stated carefully

Two distinct wins, often run together, and they are worth separating because only one of them survives into the Transformer.

1. Unbounded context, in principle. $h_t$ is a function of every token up to $t$. There is no $k$. "In principle" is load-bearing — §3 is about how much of that reach is real.
2. Weight sharing across time. One $W_{hh}$ applies at every step, so whatever the model learns about "how to update a summary given a new word" is learned once and used everywhere. This is the same argument as convolutional weight sharing across space, and it is the part the Transformer keeps: its per-position feed-forward and attention parameters are also shared across all positions.

2.3  An RNN is a deep net with tied weights

There is nothing new to learn about training it. Write out the recurrence for $T$ steps:

h1 = tanh(W_hh @ h0 + W_eh @ e1 + b)
h2 = tanh(W_hh @ h1 + W_eh @ e2 + b)      # same W_hh
h3 = tanh(W_hh @ h2 + W_eh @ e3 + b)      # same W_hh
...

That is a $T$-layer feed-forward network in which every layer uses the same weight matrix. Unrolling is the name for taking that view, and it means backpropagation applies with zero modification: it is Handout #6 §1's computation graph, just a very deep and narrow one. The special name — backpropagation through time — describes no new algorithm. It describes reverse-mode autodiff over the unrolled graph.

One consequence follows immediately from Handout #6 §4.2's gradient accumulation: $W_{hh}$ appears at every one of the $T$ steps, so its gradient is a sum of $T$ contributions. That single fact is the source of everything in §3.

3Why training them is hard

3.1  Vanishing and exploding gradients

Trace one gradient path back through $T$ steps. By the chain rule, the contribution of $h_1$ to a loss at step $T$ is a product of $T-1$ Jacobians:

The same matrix appears in every factor. A repeated product of one matrix is governed by its largest singular value $\sigma$: the norm behaves like $\sigma^{T}$, and there are only three regimes. Strip it to a scalar and the numbers are unignorable:

for w in (0.9, 1.0, 1.1):
    W = torch.tensor(w, requires_grad=True)
    h = torch.tensor(1.0)
    for _ in range(50):
        h = h * W                 # a 50-step linear "RNN"
    h.backward()
    print(f"w={w}: h_50={h.item():.6g}  dh/dW={W.grad.item():.6g}")

# w=0.9: h_50=0.00515377  dh/dW=0.28632
# w=1.0: h_50=1           dh/dW=50
# w=1.1: h_50=117.391     dh/dW=5335.95

A 10% change in one number moves the gradient by four orders of magnitude over 50 steps. $0.9^{50} \approx 0.005$; $1.1^{50} \approx 117$. Only $\sigma$ exactly $1$ is stable, and nothing keeps it there during training.

Now note the $\operatorname{diag}(1 - h_t^2)$ factor, which is $\tanh'$. Handout #6 §5 Q2 made the point in the abstract: $\tanh' \le 1$, with equality only at $h = 0$, so the nonlinearity multiplies the gradient by at most one at every step and typically by much less. The architecture is biased toward vanishing.

3.2  Truncation: BPTT is never actually run to $t=1$

Even setting gradients aside, full BPTT over a corpus is impossible: the unrolled graph would be as deep as the dataset is long, and §2.1's last table row says you would have to hold every activation. So implementations chop the stream into segments of some fixed length (in the code we will read, the flag is called bptt, typically 35), and backpropagate only within a segment.

The trick that makes this more than a crude approximation: carry the hidden state forward across segments, but not the gradient. The next segment starts from the state the previous one ended in, so the model's forward context is still unbounded; only the credit assignment is truncated at 35 steps. §7.3 shows the four lines that do this, and they are the ones students most often misread.

3.3  Gates: LSTM and GRU in one idea

The architectural fix for vanishing gradients is to give the state a path through time that is additive rather than multiplicative. An LSTM keeps a cell state $c_t$ updated as

where $f_t, i_t \in (0,1)^{d}$ are learned, input-dependent gates. Compare $\partial c_t / \partial c_{t-1} = \operatorname{diag}(f_t)$ with the vanilla RNN's $\operatorname{diag}(1-h_t^2)W_{hh}$. If the forget gate stays near 1, the product of Jacobians is near the identity for as long as it does — the gradient can travel a long way without being repeatedly multiplied by a learned matrix. The gate can also close, which is the point: the network learns per-dimension, per-timestep how long to preserve information.

A GRU merges the input and forget gates into one and drops the separate cell state — fewer parameters, usually comparable quality. The details of which gate is which matter far less than the shared idea: an additive path through time, with learned control over it. That same idea is the residual connection you will meet in the Transformer, and it is not a coincidence.

4Generating text

Scoring runs the whole sequence at once. Generation cannot: token $t+1$ depends on token $t$, which you just sampled. The loop is

1. feed the current token, get $p(\cdot)$ and the new state;
2. sample a token from $p$;
3. make it the current token, and repeat.

The important structural point — and it is the reason RNNs look so good next to Transformers at inference time — is that step 1 costs the same at position 10,000 as at position 3. The entire past is in $h_t$, a fixed-size vector, so generation is $O(1)$ per token and $O(T)$ overall, with $O(1)$ memory. §7.4 puts this side by side with the Transformer branch of the very same file, which is $O(T^2)$.

Temperature. Sampling is usually done from a rescaled distribution $p_\tau(i) \propto \exp(z_i / \tau)$. As $\tau \to 0$ this concentrates on the argmax (greedy, repetitive); $\tau = 1$ is the model's actual distribution; $\tau > 1$ flattens it (more diverse, more incoherent). Because it is applied in the exponent, it is a one-parameter knob on the entropy of the next-token distribution and costs nothing.

5What RNNs cannot fix

Two costs are structural — no gate solves them — and together they are why the field moved.

1. No parallelism over time. $h_t$ requires $h_{t-1}$. On a training sequence of length 1000, an RNN must perform 1000 dependent steps, each too small to fill a GPU. A Transformer computes all positions simultaneously, because attention looks at the whole prefix at once instead of threading a state through it. This is not a constant-factor difference; it changes what is trainable at all at scale, which — per Handout #1 §4 — is the currency that matters.

2. A fixed-size bottleneck. Everything about the past must fit in $h_t$, a $d_h$-vector, regardless of how long the past is. Attention removes exactly this constraint by keeping every past position addressable.

Neither is a claim that RNNs do not work — they worked well enough to run production translation systems. Both are claims about how they scale, and scaling was the thing. The Transformer handout starts from exactly these two complaints.

6Reading real code: PyTorch's word-level LM

The example we will read is not a teaching toy — it is the official pytorch/examples word-level language model, which has been the reference implementation people copy for years. It is worth reading precisely because it is ordinary production-adjacent code: terse, slightly dated in places, with a couple of decisions that will look wrong until you work out why they are not.

What to assess as you read. Whether you can follow the hidden state as it is threaded through time and across batches; whether you can name every tensor shape in forward; whether you can explain the weight tying; and whether you notice what the sampling loop does differently in its two branches.

7Four things to find in that code

7.1  forward, one line at a time

model.py · RNNModel.forward (verbatim)

def forward(self, input, hidden):
    emb = self.drop(self.encoder(input))
    output, hidden = self.rnn(emb, hidden)
    output = self.drop(output)
    decoded = self.decoder(output)
    decoded = decoded.view(-1, self.ntoken)
    return F.log_softmax(decoded, dim=1), hidden

Six lines, and all of §2 is in the second one. Note first what is not here: no loop over time. self.rnn is nn.LSTM (or nn.GRU, nn.RNN), and PyTorch runs the recurrence internally in optimized code. The $T$-step loop from §2.3 exists — it is simply not written in Python.

The shapes, which the file does not document and which you should verify yourself:

(T, B) rather than (B, T) is the single most common source of confusion in this file. nn.RNN and friends default to batch_first=False, a historical choice that persists because changing it would break everyone. If your tensor is batch-first you must transpose or pass batch_first=True; getting this wrong does not crash, it silently treats your batch dimension as time.

The view(-1, ntoken) flattens $(T, B)$ into $T \cdot B$ rows in row-major order — all $B$ positions of timestep 0, then all of timestep 1, and so on. That ordering has to match the targets, which is §7.3's business.

a = nn.NLLLoss()(F.log_softmax(logits, dim=1), targets)
b = F.cross_entropy(logits, targets)
assert torch.allclose(a, b)     # 2.309767 == 2.309767

7.2  Weight tying, and the constraint it imposes

model.py · RNNModel.__init__ (verbatim; a second paper citation elided)

        # Optionally tie weights as in:
        # "Using the Output Embedding to Improve Language Models" (Press & Wolf 2016)
        # https://arxiv.org/abs/1608.05859
        if tie_weights:
            if nhid != ninp:
                raise ValueError('When using the tied flag, nhid must be equal to emsize')
            self.decoder.weight = self.encoder.weight

One assignment, and it is worth pausing on how much it does. self.encoder is the $|\Sigma| \times d$ input embedding; self.decoder is the $d \to |\Sigma|$ output layer, whose weight is also $|\Sigma| \times d$. Making them the same tensor object means:

• Parameters drop by $|\Sigma| \cdot d$ — on a realistic vocabulary this is often the largest single matrix in the model, so this is not a marginal saving.
• Gradients from both uses accumulate into one .grad, by exactly the mechanism of Handout #6 §4.2. One tensor, two consumers, contributions summed. Nothing special was needed to make this work — it is why += is the right default.
• The two spaces are forced to coincide, which is the actual modeling claim: the vector that represents a word and the vector that predicts it should be the same vector. Empirically this helps, especially on smaller datasets.

And the raise explains itself now: the shapes only match if $d_h = d_e$. A capability constrains an unrelated-looking hyperparameter — the kind of coupling you only see by reading the code.

7.3  The hidden state across batches — the subtle part

This is where most readers of this example go wrong, and the three functions live in main.py. Start with the data layout:

main.py · batchify (verbatim)

def batchify(data, bsz):
    # Work out how cleanly we can divide the dataset into bsz parts.
    nbatch = data.size(0) // bsz
    # Trim off any extra elements that wouldn't cleanly fit (remainders).
    data = data.narrow(0, 0, nbatch * bsz)
    # Evenly divide the data across the bsz batches.
    data = data.view(bsz, -1).t().contiguous()
    return data.to(device)

Run it on the integers 1–24 with bsz=4 and the layout becomes obvious:

batchify(torch.arange(1, 25), 4)
# tensor([[ 1,  7, 13, 19],
#         [ 2,  8, 14, 20],
#         [ 3,  9, 15, 21],
#         [ 4, 10, 16, 22],
#         [ 5, 11, 17, 23],
#         [ 6, 12, 18, 24]])

Each column is a contiguous stream: 1–6, then 7–12, and so on. The corpus was cut into $B$ long strips laid side by side. So reading down the rows walks forward in time in all $B$ streams at once — which is exactly the (T, B) convention from §7.1, and now it is clear that convention is not arbitrary.

Consequently consecutive batches are continuations of each other, not independent samples:

def get_batch(source, i):
    seq_len = min(args.bptt, len(source) - 1 - i)
    data = source[i:i+seq_len]
    target = source[i+1:i+1+seq_len].view(-1)
    return data, target

# with bptt=3, on the tensor above:
# get_batch(source, 0) -> data rows [1,7,13,19], [2,8,14,20], [3,9,15,21]
#                         target    [2,8,14,20, 3,9,15,21, 4,10,16,22]
# get_batch(source, 3) -> data rows [4,10,16,22], [5,11,17,23]   <- continues

Two things to see. First, target is the input shifted by one and flattened row-major, which is precisely the alignment Handout #7 §9.2 spent a subsection on — here it is a slice offset instead of a slice-off-the-ends, and it must match decoded.view(-1, ntoken)'s row-major flattening. Second, batch $i{+}1$ picks up where batch $i$ stopped, so throwing away the hidden state between batches would discard real context. It is kept. And that creates the problem:

main.py · repackage_hidden (verbatim)

def repackage_hidden(h):
    """Wraps hidden states in new Tensors, to detach them from their history."""

    if isinstance(h, torch.Tensor):
        return h.detach()
    else:
        return tuple(repackage_hidden(v) for v in h)

This function is §3.2's truncation, and it is four lines. The hidden state carried into the next batch is a tensor with a grad_fn pointing back through the previous batch's graph. If you call .backward() on the next batch's loss without detaching, autograd tries to walk back into a graph that was already freed:

RuntimeError: Trying to backward through the graph a second time (or directly access
saved tensors after they have already been freed)

— the exact error from Handout #6 §4.5 Q3, arising here for a structural reason rather than a mistake. .detach() returns the same numbers with the history cut, so the values flow forward forever while gradients stop at the segment boundary. The recursion into a tuple is there because an LSTM's state is (h, c), not a single tensor.

One more line from the same file, whose presence you can now predict:

# `clip_grad_norm` helps prevent the exploding gradient problem in RNNs / LSTMs.
torch.nn.utils.clip_grad_norm_(model.parameters(), args.clip)

§3.1's fix, in the training loop, with a comment that names the problem. Note where it sits: after loss.backward() and before optimizer.step() — it has to operate on gradients that exist and have not yet been applied. Feed-forward examples rarely include this line; this one does, because it must.

7.4  The sampling loop, and a free lesson about Transformers

generate.py · the generation loop (verbatim)

with torch.no_grad():  # no tracking history
    for i in range(args.words):
        if is_transformer_model:
            output = model(input, False)
            word_weights = output[-1].squeeze().div(args.temperature).exp().cpu()
            word_idx = torch.multinomial(word_weights, 1)[0]
            word_tensor = torch.Tensor([[word_idx]]).long().to(device)
            input = torch.cat([input, word_tensor], 0)
        else:
            output, hidden = model(input, hidden)
            word_weights = output.squeeze().div(args.temperature).exp().cpu()
            word_idx = torch.multinomial(word_weights, 1)[0]
            input.fill_(word_idx)

Four things, in order of how much they are worth.

1. The two branches have different complexity, and you can see it. The RNN branch ends with input.fill_(word_idx): the input stays a single (1,1) tensor and the entire past lives in hidden. The Transformer branch ends with input = torch.cat([input, word_tensor], 0): the input grows, and the next call re-runs the model over the whole prefix from scratch. Generating $T$ tokens is $O(T)$ work in the first branch and $O(T^2)$ (with quadratic attention inside, worse still) in the second. This snippet is the clearest statement of the RNN/Transformer trade-off in this handout — the architecture that won training lost inference, and the KV cache exists to buy this back.

2. .div(temperature).exp() on log-probabilities. §7.1 established that forward returns log_softmax. So .div(τ).exp() computes $\exp(\log p_i / \tau) = p_i^{1/\tau}$ — which is the temperature-rescaled distribution up to a constant. No renormalization is performed, and none is needed: torch.multinomial accepts unnormalized non-negative weights and normalizes internally. At $\tau = 0.5$ the weights above sum to 0.879, not 1, and the sampling is still correct.

3. torch.no_grad(). Handout #6 §3's warning, applied correctly. Without it, this loop would build a graph 1000 tokens deep and hold every activation, for gradients no one will ever use.

4. The safe_globals list at the top of the file. Skim it. It is there because torch.load of a pickled model is arbitrary code execution unless you restrict what may be unpickled, and PyTorch tightened this default. It has nothing to do with language modeling and everything to do with reading real code: production files carry scars from problems outside the subject matter, and recognizing that a block is not about your topic is part of reading fluently.

7.5  Now do something to it

Show all answers

8Check yourself

Show all answers

9Optional further reading

Strictly optional — nothing here is assumed in class or on a quiz.

• Karpathy, The Unreasonable Effectiveness of Recurrent Neural Networks (2015) — the post that convinced a lot of people this worked. Historically valuable: read it knowing what came two years later.
• Olah, Understanding LSTM Networks — the diagrams everyone uses. If §3.3 was too compressed, this is the expansion.
• Pascanu, Mikolov & Bengio, On the difficulty of training recurrent neural networks (2013) — where the clipping-and-spectral-radius analysis of §3.1 is done properly.
• Sutskever, Vinyals & Le, Sequence to Sequence Learning with Neural Networks (2014) — the fixed-size-bottleneck architecture whose failure mode motivated attention. Read it before the attention material and the next step will feel inevitable.