Skip to main content
ZICQ

Wiki Concepts

Mamba (State Space Model)

Concepts
Aliases: state space model SSM selective SSM Mamba ·2026-10-10

Mamba (State Space Model)

Mamba is a deep sequence modeling architecture founded on Selective State Space Models (Selective SSM / S6). Introduced by Albert Gu and Tri Dao in late 2023, Mamba was engineered to overcome the quadratic computational and memory bottlenecks ($O(L^2)$) inherent to self-attention in the Transformer architecture.

Mamba achieves parity with or surpasses comparably sized Transformers across language, genomic, and audio benchmarks, while reducing sequence training and inference scaling to strictly linear $O(L)$ time complexity and constant $O(1)$ inference memory, completely eliminating the KV cache bottleneck during autoregressive decoding.


Theoretical Foundations: From Continuous State Spaces to Discretization

Classical State Space Models originate in control theory as continuous linear time-invariant (LTI) systems, mapping a 1D continuous signal $x(t) \in \mathbb{R}$ through a hidden state $h(t) \in \mathbb{R}^N$ to an output signal $y(t) \in \mathbb{R}$:

$$h'(t) = A h(t) + B x(t)$$

$$y(t) = C h(t)$$

Where:

  • $A \in \mathbb{R}^{N \times N}$ represents the state transition matrix governing dynamic decay;
  • $B \in \mathbb{R}^{N \times 1}$ denotes the input projection matrix injecting external signals;
  • $C \in \mathbb{R}^{1 \times N}$ is the observation matrix decoding hidden states into outputs.
Continuous Input x(t) ──► [ODE Integration & Transition B, A] ──► Hidden State h(t) ──► [Observation C] ──► Output y(t)
                                      │
                                      ▼ (Zero-Order Hold Discretization)
Discrete Sequence x_t  ──► h_t = A_bar * h_{t-1} + B_bar * x_t ──► y_t = C * h_t

Zero-Order Hold (ZOH) Discretization Formulations

To ingest discrete sequence tokens, the continuous differential system is discretized across step size $\Delta > 0$ using Zero-Order Hold integration:

$$\bar{A} = \exp(\Delta A)$$

$$\bar{B} = (\Delta A)^{-1} \left(\exp(\Delta A) - I\right) \cdot (\Delta B) \approx \Delta B$$

Yielding discrete state recurrence:

$$h_t = \bar{A} h_{t-1} + \bar{B} x_t$$

$$y_t = C h_t$$

This formulation supports dual modes: during inference, it executes as a recurrent state update requiring constant $O(1)$ memory; during training, it expands into a static 1D convolution kernel $\bar{K} = (C\bar{B}, C\bar{A}\bar{B}, \dots, C\bar{A}^k\bar{B})$, trainable via Fast Fourier Transforms (FFT) in parallel.


The Breakthrough: Selective State Spaces (S6)

The primary bottleneck of early structured SSMs (such as S4) was their strict Time-Invariance (LTI): matrices $A, B, C$ remained frozen across all sequence positions, independent of input content. This prevented the model from dynamically filtering irrelevant tokens versus retaining critical semantic anchors ("Content-Blindness").

Mamba introduced the Selective Scan Mechanism (S6), parameterizing the control matrices as dynamic projections of the current token $x_t$:

$$B_t = \text{Linear}_B(x_t) \in \mathbb{R}^{B \times L \times N}$$

$$C_t = \text{Linear}_C(x_t) \in \mathbb{R}^{B \times L \times N}$$

$$\Delta_t = \text{Softplus}\left(\text{Parameter} + \text{Linear}_\Delta(x_t)\right) \in \mathbb{R}^{B \times L \times D}$$

$$\bar{A}_t = \exp(\Delta_t A), \quad \bar{B}_t = \Delta_t B_t$$

              ┌────────────── Input Token x_t ──────────────┐
              │                       │                     │
              ▼                       ▼                     ▼
        Dynamic Input B(x_t)    Dynamic Step Δ(x_t)   Dynamic Readout C(x_t)
              │                       │                     │
              └───────────────► Dynamic Rescaling ◄─────────┘
                                      │
                                      ▼
             Selective Retention: h_t = A_bar_t * h_{t-1} + B_bar_t * x_t
  • Selective Memory: When encountering filler or stop words, the model scales $\Delta_t$ upward, triggering rapid state resets. When critical entities appear, small $\Delta_t$ values preserve memory across thousands of context steps.

Hardware-Aware Associative Parallel Scan

Input-dependent selection breaks the static convolution formulation, precluding FFT convolution. Naively evaluating recurrent loops in standard PyTorch introduces severe GPU memory transfer overhead across High Bandwidth Memory (HBM).

Mamba resolved this via a custom work-efficient associative parallel scan CUDA kernel:

  1. On-Chip SRAM Kernel Fusion: Fuses discretization ($\bar{A}_t, \bar{B}_t$) and state updates into a single unified GPU kernel.
  2. Minimizing High-Bandwidth I/O: High-dimensional hidden states $h \in \mathbb{R}^{B \times L \times D \times N}$ are maintained entirely within fast on-chip SRAM registers during the parallel scan. Only final output activations $y \in \mathbb{R}^{B \times L \times D}$ are written back to global HBM, cutting memory I/O traffic by an order of magnitude.

Mamba vs. Transformer Architectural Profile

Dimension Standard Transformer (Self-Attention) Mamba (Selective SSM)
Training Complexity Scales quadratically with sequence length $O(L^2)$ Strictly linear $O(L)$
Autoregressive Inference Step Re-scans historical keys and values $O(L)$ Constant latency step $O(1)$
Inference VRAM Footprint Massive KV cache expanding with length $O(L)$ Zero KV cache overhead; fixed hidden state $O(1)$
Long-Context Throughput Degrades at ultra-long sequences ($>100\text{K}$) Streams ultra-long contexts ($1\text{M}+$ tokens) at low latency
Exact Associative Recall High (direct pairwise inner-product addressing) Information bottleneck over dense multi-hop associative recall
Few-Shot In-Context Learning Exceptional in-context meta-learning Pure SSMs show slight degradation on complex multi-hop queries

Industrial Evolution: Hybrid SSM-Attention Architectures

To combine Mamba's linear serving economics with Transformer associative precision, modern architectures adopt hybrid configurations:

  • Jamba (AI21 Labs): Interleaves Mamba layers with attention blocks (e.g., 1 attention layer per 7 Mamba layers), yielding an $80%$ reduction in KV cache memory while preserving complex multi-hop retrieval;
  • Mamba-2 (State Space Duality, SSD): Formulates an algebraic duality between structured SSMs and linear attention, allowing state transitions to execute via block-decomposed semi-separable matrix multiplications on native Tensor Core hardware, accelerating training by $2\times$ to $8\times$.

Sources and Key Literature