Limitations of RNNs motivating transformers: Exercises

This page tests everything from the parent note by making you do the reasoning. Each problem is graded from L1 (just recognise the idea) up to L5 (put everything together). Every solution is hidden inside a collapsible callout — try the problem first, then reveal.

Before we start, one reminder about the symbols we use everywhere below, so nothing appears un-earned:

The two decay quantities we lean on:

Level 1 — Recognition

L1-Q1

An RNN reads a sentence of $T = 6$ tokens. How many hidden states $h_{1}, h_{2}, \dots$ must be computed one after another before $h_{6}$ is available, and what is this sequential cost in big-O notation?

Recall Solution

To compute $h_{6}$ we need $h_{5}$ , which needs $h_{4}$ , … down to $h_{1}$ . That is 6 hidden states computed in strict order. Because the number of ordered steps equals $T$ , the sequential cost is $O (T)$ . Each individual step is $O (1)$ work, but they cannot overlap.

Answer: 6 sequential steps, cost $O (T)$ .

L1-Q2

State in one line why a transformer's per-position work does not force sequential computation the way an RNN's does. Name the mechanism.

Recall Solution

Because in self-attention every position looks at every other position directly and simultaneously; position 6 does not wait for positions 2–5 to finish. The mechanism is self-attention, giving $O (1)$ sequential depth.

Level 2 — Application

L2-Q1

The per-step shrink factor is $k = 0.9$ . By what fraction is the gradient multiplied after flowing back 20 steps? Is the far-back token's signal strengthened or weakened?

Recall Solution

Over 20 steps the gradient is multiplied by $k^{20} = 0. 9^{20}$ . $0. 9^{20} \approx 0.1216$ The signal is weakened to about $12.2%$ of its starting strength. See the decay curve below — 20 steps sits where the plum curve has already dropped well under a fifth.

Figure — Limitations of RNNs motivating transformers

L2-Q2

An RNN encoder squeezes $T = 800$ tokens drawn from a vocabulary of size $V = 32000$ into one hidden vector. Using $bits = T lo g_{2} V$ , how many bits of information does the input carry?

Recall Solution

$bits = 800 \times lo g_{2} (32000)$ $lo g_{2} (32000) \approx 14.966$ , so $800 \times 14.966 \approx 11, 973 bits.$ Answer: about 11,973 bits of information must be packed into a single fixed-size vector.

L2-Q3

Same setup, hidden size $d = 512$ . Using the note's capacity estimate $O (d lo g_{2} d)$ , roughly how many bits can the vector hold, and does it fit the 11,973 bits from L2-Q2?

Recall Solution

$d lo g_{2} d = 512 \times lo g_{2} 512 = 512 \times 9 = 4, 608 bits.$ The vector holds about 4,608 bits but must store 11,973 bits — it holds only $4608/11973 \approx 38.5%$ of what is needed. It does not fit; the encoder is forced to forget most of the sequence. This is the compression bottleneck the encoder-decoder suffers.

Level 3 — Analysis

L3-Q1

A vanilla RNN and an LSTM are compared. For the vanilla RNN the per-step factor is $k = 0.90$ ; the LSTM's cell-state highway keeps a forget-gate value $f_{t} = 0.99$ each step so its effective factor is $0.99$ . Over a 300-token review, compute each surviving fraction and the ratio between them.

Recall Solution

Vanilla: $0.9 0^{300}$ . Taking logs, $300 ln 0.90 = 300 (- 0.10536) = - 31.6$ , so $0.9 0^{300} \approx e^{- 31.6} \approx 1.9 \times 1 0^{- 14}$ — effectively zero. LSTM: $0.9 9^{300}$ . $300 ln 0.99 = 300 (- 0.01005) = - 3.015$ , so $0.9 9^{300} \approx e^{- 3.015} \approx 0.049$ , about 4.9% surviving. Ratio $= 0.049/ (1.9 \times 1 0^{- 14}) \approx 2.6 \times 1 0^{12}$ . The LSTM keeps a usable $\sim 5%$ of the signal where the vanilla RNN keeps essentially nothing — a trillion-fold improvement in reach. See how the two curves separate:

L3-Q2

Find the number of steps $n$ at which a gradient with $k = 0.95$ has decayed to exactly $1%$ of its original strength. Solve $0.9 5^{n} = 0.01$ .

Recall Solution

Take logs of both sides: $n = \frac{l n 0.01}{l n 0.95} = \frac{- 4.60517}{- 0.051293} \approx 89.8.$ So after roughly 90 steps the signal is down to $1%$ . Any dependency longer than ~90 tokens is essentially unlearnable at this $k$ . This is why the BPTT gradient cannot connect "not" near the start to a word 295 positions later.

Level 4 — Synthesis

L4-Q1

You must process a batch of $B = 64$ sequences, each of length $T = 256$ , on a GPU with $C = 6000$ cores. (a) For the RNN, how many sequential timesteps are forced, and how many cores are busy at each timestep if one core handles one sequence? (b) For the transformer, how many positions can be computed at once, and are all cores used?

Recall Solution

(a) RNN. All 64 sequences march through time together, so the forced sequential depth is $T = 256$ timesteps. At each timestep only the 64 sequences advance, so 64 cores busy, leaving $6000 - 64 = 5936$ cores idle each step. (b) Transformer. Every position of every sequence is independent in the forward pass: $B \times T = 64 \times 256 = 16, 384$ positions ready at once. That exceeds the 6000 cores, so all 6000 cores are saturated and the work is done in $⌈ 16384/6000 ⌉ = 3$ waves instead of 256 sequential steps. The RNN wastes hardware; the transformer's parallel structure fills it.

L4-Q2

Combine two limitations. For $k = 0.95$ over $T = 256$ , what surviving gradient fraction reaches the first token, and separately, what compression ratio applies if $d = 256$ , $V = 10000$ ? State which limitation would bite first for learning long-range negation.

Recall Solution

Gradient reach: $0.9 5^{255}$ . $255 ln 0.95 = 255 (- 0.051293) = - 13.08$ , so $0.9 5^{255} \approx e^{- 13.08} \approx 2.1 \times 1 0^{- 6}$ — about two-millionths survives. Compression: available $\approx d lo g_{2} d = 256 \times 8 = 2048$ bits; required $= 256 lo g_{2} 10000 = 256 \times 13.288 \approx 3402$ bits; ratio $2048/3402 \approx 0.602$ , i.e. 60% fits. For learning a long-range negation, the vanishing gradient bites first: even if the vector could store the info ( $60%$ is generous), the training signal ( $2 \times 1 0^{- 6}$ ) is far too weak to teach the network which token mattered. Storage and learning are different failures; here learning fails harder.

Level 5 — Mastery

L5-Q1

Design argument. Suppose someone proposes "just raise $k$ to exactly $1$ so gradients never vanish." Explain quantitatively what breaks, using the fact that if $k > 1$ the factor becomes $k^{n}$ with $k > 1$ . Compute the gradient blow-up for $k = 1.05$ over $n = 200$ and name the failure.

Recall Solution

Setting $k = 1$ removes vanishing but sits on a knife-edge: any drift above $1$ triggers exploding gradients. For $k = 1.05$ , $n = 200$ : $1.0 5^{200} = e^{200 l n 1.05} = e^{200 (0.04879)} = e^{9.758} \approx 1.73 \times 1 0^{4} .$ The gradient is amplified ~17,000×, causing numerical overflow / NaN updates — the exploding gradient failure. So $k = 1$ is unstable: below it you vanish, above it you explode, and $tanh$ saturation makes staying exactly at $1$ impossible across all inputs. This dilemma is why transformers abandon the recurrence rather than tune $k$ .

L5-Q2

Full synthesis. A researcher claims: "LSTMs with $f_{t} = 0.99$ solve everything up to 300 tokens, so we never needed transformers." Refute this using: (i) the L3-Q1 surviving fraction, (ii) the L4 parallelism result, and (iii) the compression ratio for $d = 512, T = 1000, V = 50000$ .

Recall Solution

(i) Reach. From L3-Q1, $0.9 9^{300} \approx 0.049$ : only $\sim 5%$ of the gradient survives even at the friendly $f_{t} = 0.99$ . LSTMs stretch memory (~10 → ~100 steps) but never remove the multiplicative decay — for 1000+ tokens the $\sim 5%$ becomes $0.9 9^{1000} \approx e^{- 10.05} \approx 4.3 \times 1 0^{- 5}$ , again near-useless. (ii) Parallelism. Even a perfect LSTM keeps the recurrence $h_{t} = f (h_{t - 1}, x_{t})$ , so its sequential depth stays $O (T)$ ; it cannot fill a GPU. Transformers stay $O (1)$ deep. (iii) Compression. $d lo g_{2} d = 512 \times 9 = 4608$ bits available; required $= 1000 lo g_{2} 50000 = 1000 \times 15.61 \approx 15, 610$ bits; ratio $4608/15610 \approx 0.295$ — only 29.5% fits, exactly the parent note's failure case. Verdict: the LSTM improves one axis (reach) partially, but leaves parallelism and compression broken. Self-attention plus positional encoding repairs all three: one-hop gradients, full parallelism, and re-reading every source token instead of one squeezed vector. The claim fails.

Recall Quick self-check (reveal after attempting all)

RNN forced sequential depth ::: $O (T)$ Transformer sequential depth ::: $O (1)$ , via self-attention Per-step gradient factor symbol ::: $k = σ_{m a x} (W_{hh}) \cdot γ$ Why $k = 1$ is not a fix ::: knife-edge — below it vanishes, above it explodes What actually removes the multiplicative chain ::: direct one-hop self-attention