SSM & Mamba

State-space models (SSMs, e.g. S4/Mamba) frame sequence modeling as a linear time-invariant system: continuous form $\dot{h}(t) = Ah(t) + Bx(t)$, $y(t) = Ch(t)$; ZOH (zero-order hold) discretization gives $\bar{A} = e^{A\Delta}$, $\bar{B} = (e^{A\Delta} - I)A^{-1}B$, so inference is the linear recurrence $h_t = \bar{A}h_{t-1} + \bar{B}x_t$, $y_t = Ch_t$ — an $O(1)$ state update per step with no KV cache. When time-invariant ($\bar{A}, \bar{B}, C$ independent of the input) it unrolls into a global convolution $y = \bar{K} * x$ with $\bar{K} = (C\bar{B}, C\bar{A}\bar{B}, \ldots)$, enabling fully parallel training. The key of Mamba is the selective mechanism: $\Delta_t, B_t, C_t$ depend on the input $x_t$ (e.g. $\Delta_t = \mathrm{softplus}(W_\Delta x_t)$), acting like gating to decide per-token whether to remember or ignore — the cost is losing the convolution form, replaced by parallel scanning (associative scan) in training. Complexity: self-attention is $O(L^2)$ in time and memory, Mamba is $O(L)$ in sequence length, giving a clear edge on long sequences.

long-context modeling (50k+ tokens) and linear-time inference on edge devices; staple interview comparisons include Mamba vs Transformer (complexity, parallelism, long-range dependencies), Mamba vs LSTM (selectivity vs gating), and the SSM discretization derivation.

Transformer attention grows quadratically ($O(L^2)$), making long-context training/inference expensive; RNNs (LSTM) are $O(L)$ but sequential and cannot be trained in parallel. Mamba keeps $O(L)$ complexity via a linear recurrence, restores training parallelism via the parallel scan, and uses the selective mechanism to overcome the limited expressivity of fixed-parameter recurrences — reaching near-Transformer quality while greatly improving inference throughput and long-sequence memory.

Test Your Knowledge: Practice Questions for "SSM & Mamba"

Single choice pitfall questions with instant feedback and mistake tracking.