Recurrent Neural Networks

Imagine reading a sentence one word at a time and trying to predict the next word. A feedforward network sees each word in isolation. It cannot remember what came before it. To predict correctly you need memory. You need a compact summary of everything read so far. This summary updates as each new word arrives. This is exactly the problem Recurrent Neural Networks (RNNs) solve. They do this by carrying a hidden state forward through time. The same weights are reused at every step. RNNs matter because sequential data is everywhere. Language, speech, sensor streams, stock prices, genomic sequences, and user click histories all qualify. Each has an inherent order. A plain feedforward network cannot exploit that order. Convolutional layers exploit spatial locality with shared filters. RNNs exploit temporal locality with a shared transition function instead. The same small set of weights applies at every time step. This holds regardless of sequence length. This mirrors the parameter-sharing idea behind Convolutional Layers and Parameter Sharing. But sharing happens across time instead of across space. The big picture: an RNN is a dynamical system. At each step it reads an input. It combines this input with its previous hidden state. It then produces a new hidden state. This state is a running, learned summary of the past. The same weight matrices are reused at every time step. Because of this, the network can process sequences of arbitrary length. It does so with a fixed number of parameters. No fixed-size feedforward network can do this. It would need to unroll into an impractically large architecture per sequence length. This article builds the RNN from first principles. It covers the recurrence equation and the computational graph when unrolled in time. It also covers the forward pass in pseudocode. The complexity of training is explained next. Then comes the vanishing/exploding gradient problem. This problem motivates later architectures. The article closes with a worked numerical trace. It also covers common pitfalls. Finally, it traces the historical path from associative memories to modern sequence models. These models are used throughout deep learning. This foreshadows Backpropagation Through Time and LSTMs and GRUs.

Key takeaways

An RNN maintains a hidden state updated at every time step by a function with shared weights, letting one small model process sequences of any length.
The core recurrence is $h_t = f(W_{hh} h_{t-1} + W_{xh} x_t + b_h)$ , with an output $y_t = g(W_{hy} h_t + b_y)$ .
"Unrolling" the recurrence in time turns it into a deep feedforward computational graph, which is trained with Backpropagation Through Time (BPTT).
Training cost is $O(T)$ per sequence in both time and memory (for storing activations), where $T$ is sequence length.
Long sequences cause vanishing or exploding gradients because gradients are products of many Jacobians across time — the central weakness motivating gated architectures.
RNNs underlie early machine translation, speech recognition, and language modeling, and remain the conceptual foundation for LSTMs, GRUs, and even attention-based sequence models.

The core insight

An RNN turns a variable-length sequence into a fixed-size computation by applying the same learned update rule to a hidden state at every time step.

The idea

A Recurrent Neural Network is a neural network whose computational graph contains a cycle: the network's output at time $t$ depends on an internal hidden state $h_t$ , which is itself a function of the current input $x_t$ and the previous hidden state $h_{t-1}$ . Formally, an RNN defines a state-transition function

h_t = f_\theta(x_t, h_{t-1})

parameterized by a fixed set of weights $\theta$ that do not change with $t$ . This is the temporal analogue of a convolution kernel sliding over space: instead of one filter reused at every spatial position, an RNN reuses one transition function at every time position. The hidden state acts as a compressed memory of the entire prefix $x_1, \dots, x_t$ , and because $\theta$ is shared, the number of parameters is independent of sequence length $T$ . The most common ("vanilla" or Elman) RNN instantiates $f_\theta$ as an affine map followed by a nonlinearity:

h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h)

and, when a per-step prediction is needed,

y_t = \operatorname{softmax}(W_{hy} h_t + b_y).

Here $x_t \in \mathbb{R}^{d}$ , $h_t \in \mathbb{R}^{n}$ , $W_{xh} \in \mathbb{R}^{n \times d}$ , $W_{hh} \in \mathbb{R}^{n \times n}$ , and $W_{hy} \in \mathbb{R}^{k \times n}$ . The state $h_0$ is typically initialized to zero (or learned). Because the same three weight matrices are applied at every step, training an RNN on a length-1000 sequence uses the same parameter count as training on a length-10 sequence — the crucial efficiency gain over naively concatenating all time steps into one giant feedforward input. RNNs are used in three canonical modes: sequence-to-sequence (one output per input, e.g. part-of-speech tagging), sequence-to-one (a single output after reading the whole sequence, e.g. sentiment classification), and one-to-sequence (generating a sequence from a single input, e.g. image captioning). All three reuse the identical recurrence; only where outputs are read out and losses are attached differs.

How it works

Unrolling. Although the recurrence is naturally described as a loop, training requires viewing it as a computational graph. "Unrolling" the RNN for $T$ steps produces a deep feedforward network with $T$ layers, where every layer shares the same weights $W_{hh}, W_{xh}, W_{hy}$ . This unrolled graph is what backpropagation actually runs on — an algorithm specialized to it is called Backpropagation Through Time, covered in depth in its own article, but the forward pass and the shape of the gradient computation are already visible here.

Forward pass. At each step, compute the new hidden state from the old one and the current input, then optionally produce an output and a loss. ```pseudocode function RNN_FORWARD(x[1..T], h0, W_xh, W_hh, b_h, W_hy, b_y): h ← h0 # h has shape (hidden_size,) H ← empty list # store all hidden states for BPTT Y ← empty list # store all outputs for t ← 1 to T: a_t ← W_xh · x[t] + W_hh · h + b_h h ← tanh(a_t) y_t ← softmax(W_hy · h + b_y) append h to H append y_t to Y return H, Y # H[t], Y[t] for t = 1..T ```

Loss over a sequence. If each step has a target $\hat y_t$ (e.g. the next token), the total loss is the sum (or mean) of per-step losses:

L = \sum_{t=1}^{T} L_t(y_t, \hat y_t).

Backward pass (sketch). Gradients flow backward through the unrolled graph. Each hidden state $h_t$ influences the loss both directly (through $y_t$ ) and indirectly through every later hidden state $h_{t+1}, \dots, h_T$ . Define $\delta_t = \partial L / \partial h_t$ (accumulated from both paths); then: ```pseudocode function BPTT(x[1..T], H[1..T], Y[1..T], targets[1..T], W_xh, W_hh, W_hy, b_h, b_y): grad_Whh ← 0; grad_Wxh ← 0; grad_Why ← 0 grad_bh ← 0; grad_by ← 0 dh_next ← 0 # gradient flowing in from t+1 for t ← T downto 1: dy_t ← Y[t] - targets[t] # softmax + cross-entropy grad grad_Why += dy_t ⊗ H[t] grad_by += dy_t dh ← W_hy^T · dy_t + dh_next # total gradient into h_t da ← dh ⊙ (1 - H[t]^2) # backprop through tanh grad_bh += da grad_Wxh += da ⊗ x[t] h_prev ← H[t-1] (or h0 if t == 1) grad_Whh += da ⊗ h_prev dh_next ← W_hh^T · da # pass gradient to t-1 return grad_Wxh, grad_Whh, grad_Why, grad_bh, grad_by ``` Every step reuses the same weight matrices, so the gradient with respect to, say, $W_{hh}$ , is a sum over all time steps of the local contribution — this sum is the direct consequence of parameter sharing and is what makes shared weights trainable at all.

Figure

An RNN unrolled across three time steps: one shared weight set applied repeatedly

Complexity & correctness

Time complexity. Let $T$ be sequence length, $n$ the hidden size, and $d$ the input dimension. Each time step performs matrix–vector products $W_{hh}h_{t-1}$ ( $O(n^2)$ ), $W_{xh}x_t$ ( $O(nd)$ ), and (if predicting) $W_{hy}h_t$ ( $O(nk)$ for $k$ output classes). Summed over $T$ steps, the forward pass costs

O\big(T(n^2 + nd + nk)\big),

which is $O(Tn^2)$ when $n$ dominates $d,k$ . The backward pass (BPTT) touches every edge of the unrolled graph exactly once, so it costs the same $O(Tn^2)$ — a direct consequence of the fact that reverse-mode automatic differentiation costs a constant factor (≈2–3×) times the forward pass, regardless of graph shape.

Space complexity. Naively, BPTT must store every intermediate hidden state $h_1, \dots, h_T$ (and pre-activations) from the forward pass to reuse in the backward pass, costing $O(Tn)$ memory. This is the classical time–space tradeoff of backprop through deep graphs: truncated BPTT trades correctness of the gradient (it only backpropagates $k \ll T$ steps) for $O(kn)$ memory, and gradient checkpointing trades extra recomputation time for reduced memory by storing only a subset of states and recomputing the rest during the backward pass.

Correctness argument. The forward recurrence is a mathematically well-defined function composition: unrolling for $T$ steps yields an explicit feedforward computational graph (as in the figure) where node $h_t$ has exactly two parents, $h_{t-1}$ and $x_t$ , and the same weight matrices label every corresponding edge. Backpropagation on a DAG is provably correct by the chain rule applied to a topological order; BPTT is nothing more than ordinary backpropagation run on this unrolled DAG in reverse topological order. The one subtlety is parameter tying: since $W_{hh}$ appears at every time step, the total gradient with respect to $W_{hh}$ must sum its local partial derivatives across all $T$ occurrences —

\frac{\partial L}{\partial W_{hh}} = \sum_{t=1}^{T} \frac{\partial L}{\partial h_t}\bigg|_{\text{via step } t} \cdot h_{t-1}^\top,

exactly what the multivariate chain rule prescribes when one scalar-valued parameter feeds into many downstream computations. This sum is precisely what the pseudocode's `grad_Whh += ...` accumulator computes.

The vanishing/exploding gradient problem. Tracing $\partial h_T/\partial h_1$ through the chain rule gives a product of $T-1$ Jacobians:

\frac{\partial h_T}{\partial h_1} = \prod_{t=2}^{T} \frac{\partial h_t}{\partial h_{t-1}} = \prod_{t=2}^{T} \operatorname{diag}(1-h_t^2)\, W_{hh}.

If the largest singular value of $W_{hh}$ (scaled by the tanh derivative, which is $\le 1$ ) is consistently below 1, this product shrinks geometrically in $T$ , causing vanishing gradients — the network cannot learn dependencies spanning many steps. If it is consistently above 1, the product explodes. This is an honest, structural limitation of vanilla RNNs, not a bug: it is why gradient clipping is used in practice and why gated architectures (LSTMs and GRUs) were designed with additive, gated memory paths that keep this product closer to 1.

Worked example

Consider a toy character-level RNN with hidden size $n=2$ , predicting the next character of the string `"ab"` → target `"ba"` (i.e., after `a` predict `b`, after `b` predict `a`), using one-hot inputs over the alphabet $\{a, b\}$ . Fix (small, hand-chosen) parameters:

W_{xh} = \begin{bmatrix} 0.5 & -0.3 \\ 0.2 & 0.4 \end{bmatrix},\quad W_{hh} = \begin{bmatrix} 0.1 & 0.0 \\ 0.0 & 0.1 \end{bmatrix},\quad b_h = \begin{bmatrix}0\\0\end{bmatrix}

W_{hy} = \begin{bmatrix} 1.0 & -1.0 \\ -1.0 & 1.0 \end{bmatrix},\quad b_y = \begin{bmatrix}0\\0\end{bmatrix},\quad h_0 = \begin{bmatrix}0\\0\end{bmatrix}

with rows/columns ordered $(a,b)$ , so $x_1 = (1,0)^\top$ (letter `a`), $x_2 = (0,1)^\top$ (letter `b`).

Step $t=1$ (input `a`):

a_1 = W_{xh}x_1 + W_{hh}h_0 = \begin{bmatrix}0.5\\0.2\end{bmatrix},\qquad h_1 = \tanh(a_1) = \begin{bmatrix}0.4621\\0.1974\end{bmatrix}

z_1 = W_{hy}h_1 = \begin{bmatrix}0.4621 - 0.1974\\ -0.4621+0.1974\end{bmatrix} = \begin{bmatrix}0.2647\\-0.2647\end{bmatrix}

Softmax: $y_1 = \big(\tfrac{e^{0.2647}}{e^{0.2647}+e^{-0.2647}},\ \tfrac{e^{-0.2647}}{e^{0.2647}+e^{-0.2647}}\big) \approx (0.6314,\ 0.3686)$ . Target at $t=1$ is `b`, so $\hat y_1 = (0,1)$ . Loss $L_1 = -\ln(0.3686) \approx 0.998$ .

Step $t=2$ (input `b`), using $h_1$ from above:

a_2 = W_{xh}x_2 + W_{hh}h_1 = \begin{bmatrix}-0.3\\0.4\end{bmatrix} + \begin{bmatrix}0.0462\\0.0197\end{bmatrix} = \begin{bmatrix}-0.2538\\0.4197\end{bmatrix}

h_2 = \tanh(a_2) \approx \begin{bmatrix}-0.2483\\0.3968\end{bmatrix}

z_2 = W_{hy}h_2 \approx \begin{bmatrix}-0.6451\\0.6451\end{bmatrix} \;\Rightarrow\; y_2 \approx (0.1584,\ 0.8416)

Target at $t=2$ is `a`, so $\hat y_2=(1,0)$ . Loss $L_2 = -\ln(0.1584) \approx 1.843$ .

Total sequence loss $L = L_1+L_2 \approx 2.841$ . Notice $h_2$ depended on $h_1$ (through $W_{hh}h_1$ in $a_2$ ), which is exactly the mechanism carrying information about the first character into the second step's prediction — the entire point of the recurrence. In the backward pass, $\partial L/\partial W_{hh}$ receives contributions from both $t=1$ and $t=2$ , summed as derived above, because $W_{hh}$ is the same matrix at every step.

$t$	input	$h_t$	predicted $y_t$	target	$L_t$
1	a	(0.462, 0.197)	(0.631, 0.369)	b	0.998
2	b	(−0.248, 0.397)	(0.158, 0.842)	a	1.843

Common pitfalls & traps

Pitfall	Why it happens	Fix
Forgetting to sum gradients across time for shared weights	Treating $W_{hh}$ as if it only appears once instead of at every step	Accumulate `grad_Whh` across all $t$ , as the chain rule requires
Exploding gradients	Repeated multiplication by $W_{hh}$ with spectral norm $>1$ over many steps	Gradient clipping (clip norm of full gradient vector)
Vanishing gradients on long sequences	Product of $T$ Jacobians, each $\le 1$ in norm, shrinks geometrically	Use gated units (LSTMs and GRUs), shorter truncation windows, or careful initialization
Confusing "hidden size" with "sequence length"	Both are just integers in code, easy to swap when reshaping tensors	Always name tensor axes explicitly (`batch, time, hidden`)
Truncated BPTT bias	Truncating the backward pass at $k$ steps silently drops all gradient from dependencies beyond $k$	Choose $k$ based on the longest dependency length that matters for the task
Using softmax cross-entropy loss with unnormalized/unstable logits	Numerical overflow in `exp()` for large logits	Subtract max logit before exponentiating (log-sum-exp trick)

Pioneers & history

Recurrent computation traces back to early neural models of memory and associative recall, long before "deep learning" existed as a field. The idea of a network with feedback connections — where a unit's state can depend on its own past state — was central to work on associative memories and dynamical neural networks in the 1980s, well before the training methods to make such networks practical were developed.

Origins · 1 minJohn J. Hopfield and how this was discovered

John J. Hopfield

1933– · American physicist and neuroscientist

Hopfield's 1982 model of associative memory using networks with symmetric feedback connections demonstrated that recurrent dynamics could store and retrieve patterns as stable states, directly inspiring later work on trainable recurrent networks and energy-based views of neural computation.

History

1982

— Hopfield networks introduce recurrent, energy-based associative memory.

1986

— Rumelhart, Hinton, and Williams describe backpropagation and its extension to recurrent nets (BPTT) for sequence learning.

1990

— Elman's "Finding Structure in Time" popularizes the simple recurrent network for language and sequence tasks.

1991

— Hochreiter's diploma thesis formally identifies the vanishing gradient problem in deep and recurrent networks.

1997

— Hochreiter and Schmidhuber introduce the LSTM to address vanishing gradients with gated memory cells.

Where this matters

RNNs (and their gated descendants) powered the first generation of deep learning systems for speech recognition (acoustic and language modeling), machine translation (sequence-to-sequence encoder–decoder models before attention-only architectures became dominant), handwriting recognition, and time-series forecasting in finance, energy demand, and healthcare monitoring. Text generation and early chatbot systems relied on character- or word-level RNN language models predicting the next token from hidden state, the same mechanism traced in the worked example above. Even as attention-based architectures have replaced RNNs in many state-of-the-art language systems, the conceptual core — a state updated over time with shared weights — persists in streaming inference systems, reinforcement learning agents with memory, online recommendation systems processing user event streams, and control systems that must summarize an unbounded history with bounded memory. Understanding RNNs is also the direct prerequisite for LSTMs and GRUs and for the training algorithm Backpropagation Through Time, both of which patch the specific weaknesses identified here.

Ask the tutor: How does the LSTM's gating mechanism concretely prevent the multiplicative gradient decay seen in the vanilla RNN?

Why can't we just use a feedforward network on the concatenated sequence instead of an RNN?

A feedforward network over a concatenated sequence needs a fixed input size, so it cannot handle variable-length sequences without padding or truncation, and it must learn separate weights for each position, meaning a pattern seen at position 3 doesn't automatically transfer to position 30. An RNN's shared weights let the same detected pattern (e.g., negation, subject-verb agreement) be recognized regardless of where in the sequence it occurs, and it naturally supports arbitrary sequence lengths at inference time — properties analogous to how convolutional weight sharing generalizes patterns across spatial position.

Is the hidden state literally "memory" in the way a computer's memory works?

Not exactly. A computer's memory stores exact values at addressable locations; an RNN's hidden state is a fixed-size, dense vector that must compress the entire history into $n$ real numbers via a learned, lossy nonlinear transformation. It behaves more like a running summary statistic than an addressable memory bank. This limited capacity, combined with vanishing gradients, is precisely why long-range dependencies are hard for vanilla RNNs and why architectures with explicit gating and additive memory paths (LSTMs, GRUs) were introduced.

What is the difference between an RNN's parameters and its hidden state?

Parameters ( $W_{hh}, W_{xh}, W_{hy}, b_h, b_y$ ) are learned once during training and fixed at inference time; they define the rule for updating the state. The hidden state $h_t$ is not a parameter — it is a per-sequence, per-time-step intermediate value, recomputed from scratch for every new input sequence starting from $h_0$ . Confusing the two is a common bug: resetting $h_0$ between independent sequences is necessary, but resetting the weights is not (and would erase everything learned).

Why is unrolling in time useful if the loop can just be run directly?

Running the loop directly is how the forward pass is executed, but training requires computing gradients, and gradients are computed by backpropagation on an explicit computational graph. Unrolling makes that graph explicit: it shows that $h_t$ has two parents ( $h_{t-1}$ and $x_t$ ) and that the weight matrices are edge labels repeated identically across all $T$ layers. This view is what justifies applying ordinary reverse-mode differentiation (BPTT) and what makes clear why gradients must be summed across time for shared parameters.

Does a larger hidden size always fix the vanishing gradient problem?

No. Hidden size $n$ controls how much information the state can represent at a single time step, but vanishing gradients arise from repeatedly multiplying Jacobians whose spectral norm is less than 1 across many time steps — a property of the recurrent weight matrix's dynamics, not of its size. Increasing $n$ can help empirically by giving the optimizer more room to find better-conditioned solutions, but it does not structurally fix the multiplicative decay; gating mechanisms that provide additive, near-identity paths for gradient flow are the structural fix.

Can RNNs be trained in parallel across time steps, like convolutional layers can across space?

Not within a single sequence: the forward computation of $h_t$ strictly depends on $h_{t-1}$ , creating a sequential dependency chain that cannot be parallelized across time on a single sequence. Parallelism in practice comes from batching many independent sequences together and processing them simultaneously across the batch dimension, while still stepping through time sequentially. This sequential bottleneck is one practical reason attention-based architectures, which allow more parallel computation across positions, became attractive alternatives for very long sequences.

What exactly does "the same weights at every time step" buy us in terms of parameter count?

Without sharing, a feedforward network processing a length- $T$ sequence with hidden size $n$ and input size $d$ would need a distinct weight matrix at each of the $T$ positions, giving $O(T \cdot n(n+d))$ parameters that grows with sequence length. An RNN uses one $W_{hh}$ , one $W_{xh}$ , and one $W_{hy}$ total, giving $O(n(n+d+k))$ parameters independent of $T$ . This is the same efficiency argument as convolutional parameter sharing, applied along the time axis instead of the spatial axes.