Why does an RNN's hidden-state chain block parallel training across time steps?

## The dependency, stated precisely A recurrent layer is defined by a single equation applied over and over with the same weights: `h_t = f(W_h h_(t-1) + W_x x_t + b)`. Here `x_t` is the input at position t, `h_t` is the hidden state after position t, `W_h` and `W_x` are weight matrices shared across all positions, and `f` is an elementwise nonlinearity. Gated cells such as LSTM and GRU add more terms, but the shape is identical: the output at position t is a function of the state at position t-1. That is a *data dependency*, not a code-organisation problem. You cannot compute `h_5` without `h_4`, and you cannot compute `h_4` without `h_3`. For a sequence of length T, the forward pass therefore contains T operations that must execute one after another. Backpropagation through time (BPTT) unrolls the same chain and walks it backwards, so the backward pass is another T serial operations. The *critical path* through the computation grows linearly with sequence length. ## What is still parallel, and why it is not enough Three things do parallelize inside a recurrent trainer: - **The batch.** Independent sequences share no hidden state, so B sequences can advance through step t together. This is the only large source of parallelism available. - **Within a step.** The matrix multiply `W_h h_(t-1)` is itself parallel across rows and columns. - **Across stacked layers,** partially: layer 2 at position t needs layer 1 at position t, so a wavefront can overlap layers, but the depth of a stack is small compared with T. The problem is that these are small. At each step you multiply a `B x d` activation matrix by a `d x d` weight matrix, where d is the hidden size — a few hundred to a couple of thousand. Modern accelerators are built for very large matrix multiplies; a stack of small ones is dominated by fixed per-operation overhead and by moving weights and activations through memory rather than by arithmetic. Utilisation is low, and the standard fix — enlarge the batch — has limits: memory holds the saved activations for *all* T steps for the backward pass, so batch size and sequence length trade against each other, and very large batches change optimisation behaviour. The decisive point is the critical path. Adding accelerators shortens the time to process a batch, but it cannot make step 4 start before step 3 ends. A multi-day translation run on eight accelerators is slow not because the arithmetic is large but because the arithmetic is *strung out*: the machine spends most of its time waiting on the previous step. ## What dropping recurrence buys Replace the recurrent layer with one that computes every position's output directly from the layer's inputs — every position's result depends on the inputs, never on another position's *output*. Now the whole sequence is one operation. A batch of B sequences of length T becomes a `(B*T) x d` matrix, multiplied once. The critical path per layer no longer depends on T at all; it depends only on the depth of the network. Sequence length turns from a serial dimension into another parallel dimension, alongside the batch. The consequence is wall-clock, and it is large. On the same corpus with the same number of training tokens, a trainer that is parallel over positions saturates the matrix units and finishes an epoch in a small fraction of the time a recurrent unroll takes on the same hardware. That single fact — not a claim about better modelling — is what motivated moving away from recurrence for large-scale sequence training. ## The distinction candidates get wrong Removing recurrence does not necessarily reduce total arithmetic. A parallel-over-positions layer often performs *more* floating-point work than a recurrent unroll on the same sequence, because each position is computed against many others rather than against a single carried state. What changes is that the work is issued all at once instead of in a chain, so it maps onto hardware that is designed for exactly that shape. Wall-clock time and total FLOPs are different quantities, and this whole trade is about the first. ## How to talk about it in an interview Say the equation, name the dependency, name the critical path, and name what stays parallel (the batch). Then give the consequence: low utilisation, wall-clock scaling with T, and no rescue from more hardware. Finish with the trade — the parallel replacement pays in arithmetic and in what it loses (ordering has to be supplied, and per-step cost stops being bounded), which shows you understand it as an engineering exchange rather than a strict upgrade.