← Roadmap

Mamba: Linear-Time Sequence Modeling with Selective State Spaces

Gu, Dao · 2023

① Intuition

Transformers dominate sequence modeling, but they carry a fundamental cost: self-attention is O(L²) in sequence length L. Every new token must attend to every previous token. At L = 4096 that is 16 million dot products per layer; at L = 100k it becomes prohibitive. The KV-cache scales linearly with context, but the attention computation itself scales quadratically — making very long-context inference slow and expensive.

State space models (SSMs) offer a linear-time alternative. An SSM maintains a hidden state h_t that summarizes all past inputs, updating it with a simple recurrence: h_t = A h_(t-1) + B x_t. The output is y_t = C h_t. Because each step touches only h_t and x_t, inference is O(L) — no quadratic explosion. The catch: classical SSMs use fixed matrices A, B, C that do not depend on the input. This makes the dynamics input-agnostic — the model integrates every token with the same weights, blurring relevant content into an undifferentiated running average. It cannot selectively remember an important token or forget irrelevant noise.

Mamba’s core insight is to make the SSM parameters input-dependent. The step size Delta, the input projection B, and the output projection C all become functions of x_t. Delta_t controls how much the current token is “written” into the hidden state: a large Delta means absorb strongly, a small Delta near zero means skip this token. This gives the model a selective memory: it can latch onto salient content and discard noise — behavior that classical SSMs simply cannot produce.

Before toggling the widget: if A_t is always 0.8 (plain SSM), what do you expect to happen to h_t as the sequence progresses through both large and small x_t values?

Interact with the widget: toggle “Selective (Mamba)” on and off and step through t=0 to t=15. In plain-SSM mode A_t stays at 0.8 for every step. In Mamba mode A_t = 0.95 * sigmoid(2 * x_t) and B_t = sigmoid(1 + x_t), so both depend on x_t. Watch the h_t bar chart and the A_t readout change as you move the step slider.

h_t across 16 steps

t=0t=15

h at step 0

0.0000

A_t at step 0

0.8000

Mode: Plain SSM

h_t = A_t · h_{t-1} + B_t · x_t  |  x_t = sin(t × 0.8)

After playing with the widget: when x_t is large and positive in selective mode, A_t rises. What does that actually mean for the hidden state — is the model remembering or forgetting the past?

Retrieval check

Why is standard self-attention O(L²) in sequence length?
What is the fundamental limitation of a classical (non-selective) SSM?

Answer all 2 correctly to mark this stage mastered.

② Math

Mamba starts from the continuous-time state space model:

h′(t)=A h(t)+B x(t),y(t)=C h(t)+D x(t)h'(t) = A\,h(t) + B\,x(t), \quad y(t) = C\,h(t) + D\,x(t)

where h(t) is the hidden state vector, x(t) the scalar input, and A, B, C, D are matrices/vectors. To apply this on discrete token sequences, Mamba discretizes via the zero-order hold (ZOH) rule using a learned step size Delta:

Aˉ=exp⁡(ΔA),Bˉ≈ΔB\bar{A} = \exp(\Delta A), \qquad \bar{B} \approx \Delta B

This gives the discrete recurrence used at every time step:

ht=Aˉ ht−1+Bˉ xt,yt=C hth_t = \bar{A}\,h_{t-1} + \bar{B}\,x_t, \qquad y_t = C\,h_t

So far this is a standard discretized SSM. Mamba’s key move: make Delta, B, and C functions of the current input x_t via learned linear projections:

Bt=SB(xt),Ct=SC(xt),Δt=softplus(SΔ(xt))B_t = S_B(x_t),\quad C_t = S_C(x_t),\quad \Delta_t = \text{softplus}(S_\Delta(x_t))

where S_B, S_C, S_Delta are linear layers. Because Delta enters the ZOH formula, a large Delta_t means a large Ā_t and a large B̄_t — the model strongly absorbs x_t into the state. A small Delta_t near zero means Ā_t approaches the identity (perfect memory of the past) and B̄_t approaches zero (ignore the current input). This is content-aware gating built into the scan kernel itself.

What does Delta_t control geometrically in the discretization?
Show next line
Δt→0⇒Aˉ→I,  Bˉ→0  (skip token);Δt≫0⇒absorb strongly\Delta_t \to 0 \Rightarrow \bar{A} \to I,\; \bar{B} \to 0 \;\text{(skip token)};\quad \Delta_t \gg 0 \Rightarrow \text{absorb strongly}
Why is softplus used to parameterize Delta_t rather than, say, a sigmoid or a raw linear layer?
Show next line
Δt=softplus(SΔ(xt))>0  ∀ xt∈R\Delta_t = \text{softplus}(S_\Delta(x_t)) > 0 \;\forall\, x_t \in \mathbb{R}

Retrieval check

In Mamba's selective SSM, which of the following are NOT input-dependent?
What happens to the discrete recurrence h_t = Ā h_{t-1} + B̄ x_t when Delta_t is very small (near zero)?

Answer all 2 correctly to mark this stage mastered.

③ Pseudo code

Arrange the five steps of Mamba’s selective scan in the correct order:

  1. Scan hidden state: h_t = Ā_t * h_{t-1} + B̄_t * x_t
  2. Discretize A and B using Delta_t: Ā_t = exp(Delta_t * A), B̄_t = Delta_t * B_t
  3. Project input x_t to get per-token parameters: Delta_t, B_t, C_t via linear layers
  4. Compute output: y_t = C_t * h_t
  5. Apply residual and output projection to produce the final token embedding

Fill in the blank — the state update inside the scan loop:

def selective_scan(x, A, S_B, S_C, S_delta):
    # x: (L,) input sequence
    h = 0
    ys = []
    for t in range(len(x)):
        delta_t = softplus(S_delta(x[t]))
        B_t     = S_B(x[t])
        C_t     = S_C(x[t])
        A_bar   = exp(delta_t * A)
        B_bar   = delta_t * B_t
        h       = _______________________
        ys.append(C_t * h)
    return ys

Retrieval check

In the selective scan, why must C_t be applied after the state update (h_t = Ā h_{t-1} + B̄ x_t) rather than before?

Answer all 1 correctly to mark this stage mastered.

④ Code (Python)

Implement the selective scan in NumPy. Given an input sequence x of shape (L,) and scalar-valued functions for A_t (decay) and B_t (input gate), compute the hidden state sequence h over all L steps, then return it along with the output y_t = C * h_t using a fixed scalar C=1.0.

Retrieval check

In the selective_scan implementation, what role does sigmoid(x[t]) play for both A_t and B_t?

Answer all 1 correctly to mark this stage mastered.

⑤ Original paper

Your browser can't embed PDFs. Download Mamba: Linear-Time Sequence Modeling with Selective State Spaces (Gu, Dao 2023).

Open in new tab · Download

Suggested reading order: §1 (Introduction — motivation from the O(L²) attention bottleneck and why classical SSMs fall short) → §3.1 (Selective State Space Models — formal definition of input-dependent Delta, B, C and the selectivity mechanism) → §3.2 (Efficient Implementation — the hardware-aware parallel scan algorithm that makes selective SSMs practical on GPUs despite the sequential recurrence).