Question bank — State-space models (Mamba, S4)

False. At inference they run as a recurrence like an RNN, but at training the linear (input-independent) SSM unrolls into a convolution, which parallelises across the whole sequence — RNNs cannot do this because their nonlinearity blocks unrolling into a fixed kernel.

False. The GPU runs the discretised recurrence $h_k=\bar{\mathbf{A}}{h}_{k-1}+\bar{\mathbf{B}}{x}_k$. The continuous form is a design language that lets us borrow control-theory tools; discretisation converts it to something computable on tokens.

False for S4/Mamba. A dense $\mathbf{A}$ would cost $O(N^2)$, but S4's diagonal-plus-low-rank and Mamba's diagonal $\mathbf{A}$ make the per-step cost effectively $O(N)$, which is why large $N$ (long memory) stays affordable.

False. Naively the kernel is length $L$, so direct convolution is $O(L^2)$ — but because it is a fixed kernel it goes through FFT at $O(L\log L)$. Attention builds an $L\times L$ score matrix that has no such shortcut, staying $O(L^2)$.

False. They must lie inside the unit circle (magnitude $<1$) for stable, decaying memory. Since $\mathbf{A}$'s eigenvalues typically have negative real parts, $e^{\mathbf{A}\Delta }$ produces magnitudes below 1 — the sign of the exponent's real part, not the entry, is what matters.

False. $\bar{\mathbf{A}}=e^{\mathbf{A}\Delta (x)}$: the base $\mathbf{A}$ is a fixed learned parameter, but the effective transition changes per token because $\Delta$ is computed from the input. Selection lives in $\Delta$ (and in $\bar{\mathbf{B}},\mathbf{C}$), not in a table.

False. It is still a recurrence — every step $h_k=\bar{\mathbf{A}}(x_k)h_{k-1}+\bar{\mathbf{B}}(x_k)x_k$ runs one after another. What it loses is the convolutional form, because a convolution needs a single time-invariant kernel.

The formula is a limit-safe expression: as $\mathbf{A}\to 0$, ${\mathbf{A}}^{-1}(e^{\mathbf{A}\Delta }-\mathbf{I})\to \Delta \mathbf{I}$ (Taylor expand $e^{\mathbf{A}\Delta }\approx \mathbf{I}+\mathbf{A}\Delta$). So $\bar{\mathbf{B}}\to \Delta \mathbf{B}$ — no blow-up, the input is simply written proportional to the step size.

Wrong to call it a fatal loss but the mechanism is right: with $\mathbf{D}=0$ the direct $x\to y$ path is gone, so any input echo must route through the state. In practice $\mathbf{D}$ is a cheap residual and is often kept precisely so the model needn't waste state capacity on a copy.

Missing the read-out. Each entry must be pre-multiplied by $\mathbf{C}$: $\bar{\mathbf{K}}=(\mathbf{C}\bar{\mathbf{B}},\mathbf{C}\bar{\mathbf{A}}\bar{\mathbf{B}},\dots )$. Without $\mathbf{C}$ you'd have the state's impulse response, not the output's.

Backwards. Mamba cannot use the FFT at all — its input-dependent parameters destroy the fixed kernel. It wins on modelling quality via selection, and stays fast through a hardware-aware scan (fused kernels, work in SRAM), not through FFT.

In S4 it is a learned scalar per channel; in Mamba it is computed from each token. It is never a hand-set constant during the forward pass — it is exactly the knob the model turns to decide memory length.

It's only the first-order approximation of $e^{\mathbf{A}\Delta }$. Over 100K-token sequences the small per-step error compounds, and stability can be lost when eigenvalues drift outside the unit circle. The matrix exponential is the exact zero-order-hold solution, which is why it's preferred.

The continuous form lets us set $\mathbf{A}$ using well-understood signal-processing theory (e.g. HiPPO for optimal memory) and gives a principled, error-controlled discretisation via $e^{\mathbf{A}\Delta }$ — advantages a purely discrete recurrence design lacks.

$\bar{\mathbf{A}}=e^{\mathbf{A}\Delta }$, so a large $\Delta$ pushes eigenvalue magnitudes near 1 (state barely decays → long memory) while a small $\Delta$ pushes them toward 0 (state decays fast → short memory). One number smoothly interpolates the whole memory range.

Unrolling the recurrence shows each output is a weighted sum of all past inputs with weights $\mathbf{C}{\bar{\mathbf{A}}}^k\bar{\mathbf{B}}$. That is a convolution whose receptive field is the entire sequence — unlike a CNN's short fixed window, giving unbounded (but decaying) context.

Both avoid the $O(n^2)$ attention matrix by keeping a fixed-size running summary of the past that is updated additively per token. The state $h_k$ plays the role of linear attention's accumulated key–value memory; both trade an explicit token-pair matrix for a recurrent state.

Negative read-out weights let state dimensions cancel or oppose each other, so the model can express conditions like "fire when dimension 1 is high and dimension 2 is low" — richer than a purely additive read-out could.

Its decay rate is the same for every token, so it must pick one global compromise: long memory keeps the name but also clutters with filler words; short memory drops the filler but forgets the name. Mamba escapes this by choosing per-token.

The state never decays — it becomes a running accumulator of $\bar{\mathbf{B}}{x}_k$. This is a perfect but lossless memory; useful for counting/integrating, but risky since it never forgets and can grow unbounded.

$\bar{\mathbf{A}}\to \mathbf{I}$ and $\bar{\mathbf{B}}\to 0$ (since $\bar{\mathbf{B}}\approx \Delta \mathbf{B}$), so the state is frozen and the input ignored — the token is effectively skipped. This is exactly how Mamba "forgets" or bypasses filler.

If $\mathbf{A}$'s eigenvalues have negative real part, $\bar{\mathbf{A}}=e^{\mathbf{A}\Delta }\to 0$: the old state is wiped and the step is dominated by the fresh input — a sharp "reset and pay full attention here" behaviour.

No. $h_1=\bar{\mathbf{B}}{x}_1$ so $y_1=\mathbf{C}\bar{\mathbf{B}}{x}_1$ — the first input immediately writes into the state and reads out, so $y_1$ is nonzero whenever $x_1$ and the kernel head $\mathbf{C}\bar{\mathbf{B}}$ are nonzero.

Old contributions get amplified each step, so ${\bar{\mathbf{A}}}^k$ explodes and the state overflows — the SSM's version of an RNN's exploding gradient/activation. Stable training keeps magnitudes strictly below 1.

No — both reduce to the single computation $y_1=\mathbf{C}\bar{\mathbf{B}}{x}_1$. The parallel-training advantage of the convolution only appears once $L>1$; the two views are two lenses on the same underlying map.

They decay at the identical rate, so their memories become linearly redundant unless $\bar{\mathbf{B}}$/$\mathbf{C}$ separate them — effectively wasting capacity. Diverse eigenvalues (fast + slow channels) are what give the model a spectrum of memory timescales.