While the Transformer architecture dominates modern foundation models, it is burdened by a severe computational barrier: the Quadratic Context Bottleneck. Standard self-attention requires evaluating the full $N times N$ attention matrix, scaling computation and memory as $O(N^2)$ with sequence length $N$. Processing million-token documents or long-range video becomes computationally prohibitive. In 2023, Albert Gu and Tri Dao introduced Mamba, rooted in continuous Structured State-Space Models (SSMs), matching Transformer performance while processing sequences in linear $O(N)$ time and constant inference memory.
1. The Continuous-Time State-Space Representation
A State-Space Model maps a 1D continuous input signal $x(t) in mathbb{R}$ through an $N$-dimensional latent state $h(t) in mathbb{R}^N$ to an output $y(t) in mathbb{R}$ via linear differential equations:
$$h'(t) = A h(t) + B x(t)$$
$$y(t) = C h(t) + D x(t)$$
where $A in mathbb{R}^{N times N}$ is the state transition matrix governing internal memory evolution, $B in mathbb{R}^{N times 1}$ is the input projection vector, and $C in mathbb{R}^{1 times N}$ is the observation projection.
2. The HiPPO Framework: Optimal Orthogonal History Projection
If state transition matrix $A$ is randomly initialized, internal memory suffers catastrophic forgetting. In 2020, Albert Gu et al. established the HiPPO (High-order Polynomial Projection Operators) framework: proving that to maintain an optimal online approximation of continuous historical signal $x(t)$ under a exponentially decayed memory measure $mu(t) = e^{t – t_{max}}$, the state vector must track the coefficients of Legendre orthogonal polynomials.
The resulting closed-form HiPPO matrix $A in mathbb{R}^{N times N}$ is:
$$A_{nk} = begin{cases} -sqrt{(2n+1)(2k+1)} & text{if } n > k \ -(n+1) & text{if } n = k \ 0 & text{if } n < k end{cases}$$
The HiPPO operator endows the linear dynamical system with mathematically provable memory retention across millions of time steps.
3. Discretization and Dual Dualities: Recurrence vs Convolution
To process digital discrete tokens $(x_0, x_1, dots)$, continuous SSMs are discretized using the bilinear (Tustin) or zero-order hold (ZOH) transformation with step size $Delta$:
$$bar{A} = exp(Delta A), quad bar{B} = (Delta A)^{-1}(exp(Delta A) – I) cdot Delta B$$
The discretized system exhibits a remarkable mathematical duality:
- Linear Recurrent View ($O(1)$ Inference): $h_t = bar{A} h_{t-1} + bar{B} x_t, quad y_t = C h_t$. During autoregressive token generation, the model maintains a constant-size hidden state $h_t$, achieving $O(1)$ time complexity and avoiding the massive KV cache memory footprint of Transformers.
- Global Convolutional View ($O(N log N)$ Training): Unrolling the recurrence reveals a global 1D convolution: $y = x * bar{K}$ where $bar{K} = (Cbar{B}, Cbar{A}bar{B}, dots, Cbar{A}^{N-1}bar{B})$. Training is executed non-autoregressively across the entire sequence simultaneously in parallel via the Fast Fourier Transform (FFT).
4. Mamba: The Selective State Space (S6) Architecture
Classical SSMs (S4, H3) are linear time-invariant (LTI): matrices $A, B, C, Delta$ remain constant across all tokens regardless of input content. LTI systems cannot perform content-based reasoning: they cannot selectively filter out irrelevant noise or remember specific crucial tokens.
Gu and Dao (2023) broke the LTI constraint by introducing Selective State Spaces (S6): making parameters input-dependent functions of the current token $x_t$:
$$B_t = W_B x_t, quad C_t = W_C x_t, quad Delta_t = text{softplus}(W_Delta x_t + text{Parameter})$$
Because parameters vary across time, the global convolution duality is lost. To preserve training speed, Gu and Dao designed a Hardware-Aware Parallel Scan: rather than materializing the intermediate expanded states in slow GPU HBM memory, the parallel scan executes entirely inside ultra-fast on-chip SRAM memory, achieving $O(N)$ linear-time processing faster than optimized FlashAttention.
