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.

Write the discretized SSM recurrence $h_t = \bar{A}h_{t-1} + \bar{B}x_t$ and derive the continuous-to-discrete step ($\bar{A} = e^{A\Delta}$, ZOH); what is the role of $\Delta$?

Training parallelism: why is a time-invariant SSM equivalent to a global convolution $y = \bar{K} * x$? After adding selectivity, how does the parallel scan (associative scan) restore parallel training?

What is the selective mechanism: why must $\Delta_t, B_t, C_t$ depend on the input $x_t$? How does it compare with LSTM gating (content-adaptive vs fixed parameters)?

Complexity comparison: self-attention is $O(L^2)$ in time and memory vs Mamba's $O(L)$; what does this mean concretely for $L = 100k$ long context?

Why are hybrid Transformer + Mamba architectures popular (Mamba blocks every few layers)? What are the potential weaknesses of pure Mamba?