Answers · How models work

Why can a linear recurrence be computed as a convolution?

In shortBecause a linear recurrence adds up past inputs with fixed decaying weights, and that weighted sum is a convolution with the recurrence's impulse response.

A linear recurrence can be computed as a convolution because its state at any step is a fixed weighted sum of all earlier inputs. The weights are the powers of the carry factor, so they are the impulse response of a filter, and convolving the input with that response produces the same state.

h_t = \Lambda h_{t-1} + B x_t

Take one slot first, with carry factor $\lambda$ and input written in with weight $b$ : $h_t = \lambda h_{t-1} + b x_t$ . Unrolling by hand gives $h_0 = b x_0$ , then $h_1 = \lambda b x_0 + b x_1$ , then $h_2 = \lambda^2 b x_0 + \lambda b x_1 + b x_2$ . The coefficient on the input from $k$ steps ago is $\lambda^k b$ , so the state is the causal convolution $h_t = \sum_{k=0}^{t} \lambda^k b\, x_{t-k}$ , plus a term from whatever the slot held before the sequence began.

h_t = \sum_{k=0}^{t} \Lambda^k B\, x_{t-k} + \Lambda^{t+1} h_{-1}

With $\Lambda$ diagonal, that matrix sum splits into one independent sum per slot. Slot $i$ has its own factor $\lambda_i$ , so its contribution from $k$ steps back is $\lambda_i^k (B x_{t-k})_i$ , and the whole layer is a bank of convolutions sharing an input but not a kernel. The kernel for slot $i$ is the sequence $1, \lambda_i, \lambda_i^2, \ldots$ multiplied by the row of $B$ that writes into that slot. A readout above the recurrence may mix the slots again, but that is position-by-position work and does not change the convolution property of the carry.

A general linear carry matrix also gives a convolution, with matrix-valued kernel $\Lambda^k B$ , but diagonal makes it a bank of scalar convolutions. The diagonal choice is a modelling choice for independent timescales, not a condition for convolution to exist. Linearity and a fixed carry are the conditions.

The local filter guess

The natural guess is that convolution means a short local filter, so a recurrence that carries state forever cannot be one. That guess fails because a convolution kernel does not have to be short. For $\lambda = 0.9$ and $b=1$ the kernel is $1, 0.9, 0.81, 0.729, 0.6561, \ldots$ ; it never becomes zero, it only decays. The filter has infinite support. What makes it cheap is that the infinitely many taps are generated by one number and can be applied by a scan or by an FFT, not that the kernel is short.

The impulse response is not hidden far away. Feed a single one at time zero and zeros afterwards. The state at step $k$ is $\lambda^k b$ , because each step multiplies what is left by $\lambda$ . Convolving any input with that response is therefore identical to running the recurrence on that input. The recurrence is the filter, written in the time domain as a loop rather than as a list of taps.

The decay rate is the kernel

Close to one, the kernel decays slowly and the convolution reaches far back. At $\lambda = 0.9$ the tap at lag $k$ is $0.9^k$ , and the slot has lost half of an impulse after $\ln(0.5)/\ln(0.9) \approx 6.6$ steps. At $\lambda = 0.999$ the same calculation gives $\ln(0.5)/\ln(0.999) \approx 693$ steps. The kernel is longer by a factor of about a hundred while the carry factor has moved only from nine tenths to nine hundred and ninety nine thousandths.

Direct convolution would cost $T^2$ for $T$ steps, an FFT would cost $T \log T$ , and running the recurrence costs $T$ . Those are three ways to apply the same kernel. The recurrence is usually preferred in a model because it is causal, streaming and needs only the current state; the convolution form is preferred for analysis and for parallel training over a whole sequence. Either way the numbers produced are the same, up to floating point.

For a bank of slots, the impulse response is not one kernel but a list of kernels, one per slot. That is why a layer can hold a fast summary and a slow summary at the same time: each slot convolves the same input with a different geometric kernel.

Where it stops being a convolution

The equivalence depends on the carry being linear and fixed. If $\Lambda$ changes with $t$ , the state is still a weighted sum of past inputs, but the weight on lag $k$ is a product of different factors and there is no single kernel to convolve with. If a nonlinearity sits inside the recurrence, superposition fails and the state is no longer a convolution of the input at all. The initial state also contributes $\Lambda^{t} h_0$ , which is a decaying term separate from the input convolution.

Worth keeping

The kernel of a linear recurrence is the sequence of powers of its carry factor.
Convolution does not require a short kernel; an exponentially decaying kernel has infinite support.
If the carry changes over time or a nonlinearity sits inside the loop, the fixed-kernel convolution description fails.

Where this goes next

This question is one step of Models That Carry a Memory, a course that works through its subject from the beginning. The page that teaches this part of it is A Linear Recurrence Done Properly, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course