Bidirectional and Stacked Recurrence: Cost and Causality

A single recurrent layer at position $t$ has access to the prefix. Its state was built by reading $x_1 \dots x_t$ in order and contains nothing that was not in those inputs. For tagging tasks where the decision at a position depends on what comes after it, such as deciding the part of speech of a word whose disambiguating context follows, that restriction is a property of the architecture rather than of the data, and two standard constructions remove it: run a second recurrence over the reversed sequence and combine the two, or stack more layers so that each position is transformed repeatedly.

Reading the suffix as well as the prefix

A bidirectional layer holds two independent recurrent cells. The forward cell processes the sequence left to right, producing states $h^{\rightarrow}_t$; the backward cell processes the same sequence right to left, producing $h^{\leftarrow}_t$ from inputs $x_T \dots x_t$; the layer’s output at each position is the concatenation of the two states, of width $2d$. Neither cell sees the other, so the parameter count doubles exactly and the arithmetic per step doubles, but the two passes are independent and the recurrence depth along time stays $T$: the critical path is one recurrence, not two.

The output at position $t$ then depends on the entire sequence rather than on its prefix, which is the whole gain. It is not the same as having a state that summarizes both sides in one vector: the two states are separate, and any combination of the two depends on what the downstream layers do with the concatenation. A projection after the concatenation, or the first layer above it, is where the prefix and suffix information is actually mixed.

Counting the cost of a bidirectional stack follows from separating the two axes. A layer of width $d$ with both directions emits $2d$ values per position, so the layer above it sees an input of width $2d$ and its own cells cost on the order of $2d(2d + d)$ per step rather than $2d(n + d)$; in practice the width of a bidirectional layer is halved relative to a single-direction layer of the same capacity, which brings the parameter counts back into line and keeps the memory footprint identical.

Segment boundaries are the other decision. States should be reset at boundaries the data actually has, such as separate documents or utterances, because a state carried across unrelated inputs encodes content with no bearing on the current one and the model has no signal telling it to forget. Where such boundaries are absent, the choice is between carrying the state, which lets the model see further back at the cost of a position-dependent distribution over states that training may not have covered, and resetting periodically, which makes the states at the start of each segment behave like the start of a sequence. Short sequences are the case where the two differ least, since the state has had little opportunity to accumulate.

Where the reverse pass is not allowed

The reverse cell cannot produce its first output until it has read the final input, so a bidirectional layer cannot be used in a streaming decoder or in any model whose output at position $t$ feeds the input at position $t+1$. For a left-to-right language model the reverse pass is not merely inconvenient but invalid: it would condition the prediction of $x_{t+1}$ on the symbols that are supposed to be unknown. The same applies to any layer inside a decoder, which is why encoder-decoder systems of the kind described in encoder-decoder models and teacher forcing use a bidirectional encoder and a strictly forward decoder.

For offline tasks the constraint disappears, and the whole sequence is available at once. Part-of-speech tagging, named entity recognition, phoneme recognition over a complete utterance, and per-token classification of a stored document all permit it. The cost that remains is memory: the backward pass needs the full input before it starts, so a streaming implementation has to buffer the sequence, and the layer’s useful latency is bounded below by the length of the input.

Depth inside the recurrence

Stacking adds a second axis of composition. In a stack of $L$ layers, layer $\ell$ runs its own recurrence over the sequence of outputs produced by layer $\ell - 1$, so the model computes a grid of $L \times T$ cell applications and the per-step transformation at each position becomes the composition of $L$ learned maps. The recurrence still handles time; depth handles the complexity of the transform applied at each time step, in the same way that adding hidden layers to a feedforward network increases the class of functions computable from a fixed input vector.

The arithmetic is $O(L \cdot T \cdot d^{2})$ per sequence, linear in both axes, and the activation memory for backpropagation grows the same way: $O(L \cdot T \cdot d)$ values must be held unless activations are recomputed. Gradient flow along the depth axis has its own product of matrices, one factor per layer, so a deep stack can lose the gradient before it reaches the input side of the network even when the time axis is well conditioned. Residual connections from the input of a layer to its output place an identity in that product and are the usual mitigation; the same argument appears in the time axis in backpropagation through time.

Wavefront parallelism in a stack

A stack does not have to be evaluated layer after layer over the whole sequence. Layer $\ell$ at step $t$ depends only on layer $\ell$ at step $t-1$ and layer $\ell-1$ at step $t$, so the dependencies form a wavefront: layer 2 can be working on step $t$ while layer 1 works on step $t+1$. Scheduling by wavefront turns a dependency chain of $L \cdot T$ sequential cell applications into one of $T + L - 1$, which matters because each cell application is a small matrix product that does not fill a device on its own. The total work is unchanged; only the number of steps that must be executed serially shrinks.

The bidirectional case composes with this. Two passes plus a stack of $L$ layers gives a grid of $2L \times T$ cells whose critical path is still on the order of $T + L$, provided enough independent work is available to fill the pipeline at each wavefront step. The reason to state this explicitly is that it determines whether extra depth is paid for in latency or only in throughput: depth that can be pipelined costs compute, depth that cannot costs wall-clock time.

Regularization and state resets in a stack

Each layer owns its own initial state, so a two-layer model has two parameters of width $d$ (or two sets, for a bidirectional stack) that are learned if the first state is learnable. Whether the state is carried across batched subsequences has to be decided per layer, and the layers need not agree: a common arrangement feeds whole sequences to the lowest layer and lets each layer see the same boundaries.

Dropout in a stack is applied to the connections between layers rather than to the recurrent connections within a layer. Dropping state coordinates inside the recurrence corrupts the memory that the layer is accumulating, and the noise applied at each step accumulates along the sequence in a way that training never sees at inference. Applying the same dropout mask at every time step to the inter-layer connections, which is the standard variational formulation, keeps the repeated path noise-free while still regularizing the feedforward part of the computation. Inter-layer dropout is also the cheapest regularizer here, since it costs no extra arithmetic.

Normalization is the other lever. Layer normalization applied to the cell’s pre-activations controls their scale at every step, which limits the drift into saturated regions described in gates in LSTM and GRU cells, and it does not depend on a batch dimension, so it behaves identically at training and inference and across variable sequence lengths.

Choosing between two directions and more depth

The two mechanisms buy different things, and the choice follows from the task. If the label at a position depends on both sides and the whole sequence is available, the reverse pass is the direct answer and costs a factor of two in parameters and per-step arithmetic. If the per-position transformation is the hard part, depth is the answer, and a single direction with $L$ layers is cheaper than a bidirectional layer of the same total width, since the bidirectional layer pays twice for the same depth.

Where the sequence must be consumed incrementally, neither helps on the output side. A strictly causal model has one direction and a bounded state, and reaching further back then requires attention over stored positions, as described in attention as content-based alignment, or a longer-horizon state, which is a different trade with its own memory cost.