① 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?
With a fixed A=0.8, the state h_t accumulates contributions from every token with the same decay rate. Large x_t bumps do lift the state, but the state also retains non-zero contributions from prior tokens indefinitely — blurring the history into a smoothed version. Small x_t values near zero barely change the state, but they also do not suppress the leftover from prior large inputs. The result is a low-pass-filtered signal that loses the sharp distinctions between important and unimportant tokens.
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
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?
When x_t is large, sigmoid(2 * x_t) is close to 1, so A_t approaches 0.95 — the past hidden state h_(t-1) is retained at high fidelity (low forgetting). Simultaneously B_t is also large, so x_t is written in with strong weight. In other words: at an important token the model both preserves previous context AND absorbs the new input. Conversely when x_t is near zero, A_t drops, softening the past memory, and B_t also decreases, so the irrelevant token barely leaves a trace. This is the selectivity: the gate strength is tied directly to the content of the input.
Retrieval check
Answer all 2 correctly to mark this stage mastered.
② Math
Mamba starts from the continuous-time state space model:
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:
This gives the discrete recurrence used at every time step:
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:
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.
Show next line
Show next line
Retrieval check
Answer all 2 correctly to mark this stage mastered.
③ Pseudo code
Arrange the five steps of Mamba’s selective scan in the correct order:
- Scan hidden state: h_t = Ā_t * h_{t-1} + B̄_t * x_t
- Discretize A and B using Delta_t: Ā_t = exp(Delta_t * A), B̄_t = Delta_t * B_t
- Project input x_t to get per-token parameters: Delta_t, B_t, C_t via linear layers
- Compute output: y_t = C_t * h_t
- 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 ysRetrieval check
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
Answer all 1 correctly to mark this stage mastered.
⑤ Original paper
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).