Recurrent Neural Networks

Chapter Overview

Recurrent Neural Networks (RNNs) process sequential data by maintaining hidden states that capture information from previous time steps. This chapter develops RNNs from basic recurrence to modern architectures like LSTMs and GRUs, establishing foundations for understanding transformers.

Learning Objectives

1. Understand recurrent architectures for sequential data
2. Implement vanilla RNNs, LSTMs, and GRUs
3. Understand vanishing/exploding gradient problems
4. Apply RNNs to sequence modeling tasks
5. Understand bidirectional and multi-layer RNNs

Vanilla RNNs

Backpropagation Through Time (BPTT)

Vanishing and Exploding Gradients

The fundamental challenge in training RNNs on long sequences arises from the multiplicative nature of gradient backpropagation through time. When computing gradients with respect to early hidden states, the chain rule requires multiplying Jacobian matrices across all intermediate time steps, leading to exponential growth or decay of gradient magnitudes.

The gradient of the loss with respect to an early hidden state $\vh_0$ involves the product of Jacobians across all time steps:

For a sequence of length $T = 100$, if $\norm{\mW_{hh}} = 0.95$ (slightly less than 1), the gradient magnitude decays as $0.95^{100} \approx 0.006$, reducing gradients by a factor of 167. If $\norm{\mW_{hh}} = 0.9$, the decay is $0.9^{100} \approx 2.7 \times 10^{-5}$, reducing gradients by a factor of 37,000. This exponential decay makes it nearly impossible for the network to learn long-range dependencies: the gradient signal from time step 100 is effectively zero by the time it reaches time step 0. In practice, vanilla RNNs struggle to learn dependencies longer than 10-20 time steps due to vanishing gradients.

Conversely, if $\norm{\mW_{hh}} = 1.05$, the gradient magnitude grows as $1.05^{100} \approx 131.5$, amplifying gradients by a factor of 131. If $\norm{\mW_{hh}} = 1.1$, the growth is $1.1^{100} \approx 13{,}781$, causing gradients to explode. Exploding gradients lead to numerical overflow (NaN values) and training instability, where loss suddenly spikes to infinity. While gradient clipping (capping gradient norms at a threshold like 1.0) provides a practical solution for exploding gradients, it does not address the fundamental problem of vanishing gradients.

The vanishing gradient problem is particularly severe because the spectral norm of $\mW_{hh}$ must be precisely 1.0 to avoid both vanishing and exploding gradients, and maintaining this property during training is extremely difficult. Initialization schemes like orthogonal initialization set $\mW_{hh}$ to have spectral norm 1.0 initially, but gradient descent updates quickly perturb this property. Even with careful initialization, vanilla RNNs rarely learn dependencies beyond 20-30 time steps in practice.

Quantitative Analysis of Gradient Decay

To understand the severity of vanishing gradients, consider a concrete example with BERT-base dimensions. Suppose we have a vanilla RNN with hidden dimension $h = 768$ (matching BERT-base) and sequence length $n = 512$ (BERT's maximum sequence length). The recurrence matrix $\mW_{hh} \in \R^{768 \times 768}$ has 589,824 parameters. If we initialize $\mW_{hh}$ orthogonally (spectral norm exactly 1.0) and the $\tanh$ derivatives average 0.5 (typical for non-saturated activations), the effective Jacobian norm per time step is approximately $1.0 \times 0.5 = 0.5$.

Over 512 time steps, the gradient magnitude decays as $0.5^{512} \approx 10^{-154}$, which is far below machine precision for FP32 (approximately $10^{-38}$) or even FP64 (approximately $10^{-308}$). The gradient effectively becomes exactly zero after about 130 time steps in FP32 or 1,000 time steps in FP64. This means a vanilla RNN cannot learn any dependencies spanning more than 130 tokens when using FP32 arithmetic, regardless of optimization algorithm or learning rate. The mathematical structure of the recurrence fundamentally limits the learnable dependency length.

For comparison, consider the gradient flow in a transformer with the same dimensions. The self-attention mechanism computes attention scores $\mA = \text{softmax}(\frac{\mQ\mK\transpose}{\sqrt{d_k}})$ and outputs $\mO = \mA\mV$. The gradient $\frac{\partial L}{\partial \mV}$ flows directly from the output through the attention weights, without any multiplicative accumulation across time steps. The gradient magnitude remains approximately constant regardless of sequence length, enabling transformers to learn dependencies spanning thousands of tokens. This fundamental difference in gradient flow explains why transformers replaced RNNs for nearly all sequence modeling tasks: they solve the vanishing gradient problem by design.

The LSTM architecture addresses vanishing gradients through its cell state mechanism, which provides an additive path for gradient flow. The cell state update $\mathbf{c}_t = \vf_t \odot \mathbf{c}_{t-1} + \vi_t \odot \tilde{\mathbf{c}}_t$ includes an additive term rather than purely multiplicative updates. The gradient with respect to $\mathbf{c}_{t-1}$ is:

Long Short-Term Memory (LSTM)

Key components:

• Cell state $\mathbf{c}_t$: Long-term memory, flows with minimal modification
• Forget gate $\vf_t$: What to remove from cell state
• Input gate $\vi_t$: What new information to store
• Output gate $\vo_t$: What to output from cell state

LSTM Computational Analysis

Understanding the computational cost of LSTMs is essential for comparing them to transformers and explaining why transformers have become dominant despite LSTMs' theoretical advantages for sequential processing. The LSTM's gating mechanisms provide powerful modeling capabilities but come with significant computational overhead that limits their efficiency on modern hardware.

For an LSTM with input dimension $d$ and hidden dimension $h$, each time step requires computing four gates (forget, input, candidate, output), each involving a matrix multiplication with the concatenated input $[\vh_{t-1}, \vx_t] \in \R^{h+d}$. The computational cost per time step is:

This computational cost is deceptively modest compared to transformers. A single transformer layer with the same dimensions requires approximately 12.9 GFLOPs for self-attention (with $n = 512$) plus 9.4 GFLOPs for the feed-forward network, totaling 22.3 GFLOPs—about 4.6× more than the LSTM. However, this comparison is misleading because it ignores the critical difference in parallelization: the transformer can process all 512 positions simultaneously, while the LSTM must process them sequentially.

The sequential nature of LSTMs means that the 4.8 GFLOPs cannot be parallelized across time steps. On an NVIDIA A100 GPU with peak throughput of 312 TFLOPS (FP16), the theoretical minimum time to process a sequence of length 512 is $\frac{4.8 \times 10^9}{312 \times 10^{12}} = 15.4$ microseconds if we could achieve perfect parallelization. However, the sequential dependency forces us to process one time step at a time, with each step taking approximately $\frac{9.4 \times 10^6}{312 \times 10^{12}} = 0.03$ microseconds at peak throughput. In practice, small matrix multiplications achieve only 1-5\% of peak throughput due to insufficient parallelism, so each time step actually takes approximately 1-3 microseconds, giving a total sequence processing time of 512-1,536 microseconds (0.5-1.5 milliseconds).

For comparison, a transformer layer can process the entire sequence in parallel. The self-attention computation requires three matrix multiplications ($\mQ = \mX\mW_Q$, $\mK = \mX\mW_K$, $\mV = \mX\mW_V$) with dimensions $512 \times 768 \times 768$, followed by the attention score computation $\mA = \text{softmax}(\frac{\mQ\mK\transpose}{\sqrt{d_k}})$ and output computation $\mO = \mA\mV$. These operations can be batched into large matrix multiplications that achieve 40-60\% of peak GPU throughput, completing in approximately 50-100 microseconds total. The transformer is 5-30× faster than the LSTM despite having more FLOPs, purely due to better parallelization.

The memory requirements for LSTM hidden states are modest compared to transformer attention matrices. For batch size $B$ and sequence length $n$, the LSTM must store hidden states $\vh_t \in \R^{B \times h}$ and cell states $\mathbf{c}_t \in \R^{B \times h}$ for each time step, requiring $2Bnh \times 4 = 8Bnh$ bytes in FP32. For BERT-base dimensions with $B = 32$, $n = 512$, $h = 768$, this totals $8 \times 32 \times 512 \times 768 = 100{,}663{,}296$ bytes, or approximately 96 MB. This is substantially less than the 384 MB required for transformer attention scores in a single layer, making LSTMs more memory-efficient for long sequences.

However, this memory advantage is offset by the sequential processing requirement. While transformers can trade memory for speed by using gradient checkpointing (recomputing activations during the backward pass rather than storing them), LSTMs cannot benefit from this technique as effectively because the sequential dependency prevents parallelization of the recomputation. Gradient checkpointing reduces transformer memory by 3-5× with only 20-30\% slowdown, but for LSTMs, the slowdown is 2-3× because the recomputation cannot be parallelized. This makes gradient checkpointing less attractive for LSTMs, limiting their ability to scale to very long sequences.

Gated Recurrent Unit (GRU)

Advantages over LSTM:

• Fewer parameters (3 gates vs 4)
• Simpler architecture
• Often similar performance
• Faster training

Bidirectional RNNs

Bidirectional RNNs capture context from both past and future, useful when entire sequence is available (not for online/causal tasks).

Example: BERT uses bidirectional transformers (attention, not RNN), capturing full context.

RNN Applications

Sequence-to-Sequence:

• Machine translation: Encoder RNN $\to$ Decoder RNN
• Text summarization
• Speech recognition

Sequence Labeling:

• Part-of-speech tagging
• Named entity recognition
• Output at each time step

Sequence Generation:

• Language modeling
• Music generation
• Sample from output distribution

RNNs vs Transformers: A Computational Comparison

The transition from RNNs to transformers represents one of the most significant architectural shifts in deep learning. The following table summarizes the key computational differences:

The fundamental bottleneck of RNNs is sequential processing: each hidden state $\vh_t$ depends on $\vh_{t-1}$, preventing parallelization across time steps. On an A100 GPU with 6,912 CUDA cores, an LSTM processing batch size 32 utilizes only $\sim$0.5\% of parallel capacity. Transformers eliminate this bottleneck by computing all positions simultaneously via matrix multiplication, achieving 15$\times$ or greater speedup despite having more total FLOPs.

The parallelization advantage compounds with hardware efficiency: transformers achieve high arithmetic intensity through data reuse in matrix multiplications ($\sim$256 FLOPs/byte), while RNNs perform small matrix-vector products with low data reuse ($\sim$1--10 FLOPs/byte). The combined effect is 100--500$\times$ faster training for equivalent model capacity.

Exercises

Solutions

Full solutions for all exercises are available at \url{https://deeplearning.hofkensvermeulen.be}.