State-space models (Mamba, S4)

The State-Space Foundation

WHY continuous? Even though we process discrete tokens, the continuous formulation gives us powerful tools from control theory and signal processing. We'll discretize it carefully.

From Continuous to Discrete: The Key Step

For neural networks processing discrete sequences, we need to discretize the continuous dynamics. Using the zero-order hold assumption (input is constant between timesteps), the exact solution is:

WHY this specific discretization? The matrix exponential $e^{\mathbf{A}\Delta}$ is the exact solution to the ODE for constant input. Using simpler methods (like Euler) would accumulate errors over long sequences.

HOW to compute $e^{\mathbf{A}\Delta}$ ? For general matrices this is expensive, but S4 uses structured matrices (next section) where it becomes efficient.

S4: Structured State Spaces

The original SSM approach hit a wall: the state dimension $N$ needs to be large (thousands) to have sufficient memory capacity, but this makes the $\mathbf{A}$ matrix huge and expensive.

The Convolution View

Here's the crucial dual perspective: the SSM can be viewed as either:

Recurrent: $h_k = \bar{\mathbf{A}} h_{k-1} + \bar{\mathbf{B}} x_k$ (for generation)
Convolutional: $y = \bar{\mathbf{K}} \ast x$ (for training)

The SSM convolution kernel is:

Formula SSM Kernel

$\bar{\mathbf{K}} = (\mathbf{C}\bar{\mathbf{B}}, \mathbf{C}\bar{\mathbf{A}}\bar{\mathbf{B}}, \mathbf{C}\bar{\mathbf{A}}^2\bar{\mathbf{B}}, \ldots, \mathbf{C}\bar{\mathbf{A}}^{L-1}\bar{\mathbf{B}})$

Where $L$ is the sequence length. This is the impulse response of the system.

Derivation: Unroll the recurrence starting from $h_0 = 0$ :

\begin{aligned} h_1 &= \bar{\mathbf{B}} x_1 \\ h_2 &= \bar{\mathbf{A}}\bar{\mathbf{B}} x_1 + \bar{\mathbf{B}} x_2 \\ h_3 &= \bar{\mathbf{A}}^2\bar{\mathbf{B}} x_1 + \bar{\mathbf{A}}\bar{\mathbf{B}} x_2 + \bar{\mathbf{B}} x_3 \\ y_k &= \mathbf{C}h_k = \sum_{i=1}^k \mathbf{C}\bar{\mathbf{A}}^{k-i}\bar{\mathbf{B}} x_i \end{aligned}

This is a convolution with kernel $\bar{\mathbf{K}}$ .

WHY convolutional view? Convolutions can be computed in $O(n \log n)$ using FFT, and they parallelize perfectly across the sequence (unlike the recurrent form). Training uses convolution, inference uses recurrence.

HOW does DPLR structure help? With diagonal-plus-low-rank $\mathbf{A}$ , the powers $\bar{\mathbf{A}}^k$ and kernel $\bar{\mathbf{K}}$ can be computed efficiently using the Cauchy kernel trick and FFT. The details involve complex analysis, but the result is $O(N \log N)$ computation per layer.

Worked example Worked Example:2D SSM Step

Let's trace one timestep with a tiny2D state for intuition.

Given:

State dimension $N = 2$
Discrete matrices: $\bar{\mathbf{A}} = \begin{bmatrix} 0.9 & 0 \\ 0 & 0.5 \end{bmatrix}$ , $\bar{\mathbf{B}} = \begin{bmatrix} 0.1 \ 0.2 \end{bmatrix}$ , $\mathbf{C} = \begin{bmatrix} 1 & -0.5 \end{bmatrix}$
Previous state: $h_0 = \begin{bmatrix} 0.3 \\ 0.1 \end{bmatrix}$
Current input: $x_1 =2.0$ Step 1: Update state $h_1 = \bar{\mathbf{A}} h_0 + \bar{\mathbf{B}} x_1 = \begin{bmatrix} 0.9 & 0 \\ 0 & 0.5 \end{bmatrix} \begin{bmatrix} 0.3 \\ 0.1 \end{bmatrix} + \begin{bmatrix} 0.1 \\ 0.2 \end{bmatrix} \cdot 2.0$ WHY multiply by $\bar{\mathbf{A}}$ ? We're decaying the old state—the 0.9 means the first dimension has long memory (decays slowly), while 0.5 means the second dimension forgets faster.

$= \begin{bmatrix} 0.27 \ 0.05 \end{bmatrix} + \begin{bmatrix} 0.2 \\ 0.4 \end{bmatrix} = \begin{bmatrix} 0.47 \\ 0.45 \end{bmatrix}$

Step 2: Compute output $y_1 = \mathbf{C} h_1 = \begin{bmatrix} 1 & -0.5 \end{bmatrix} \begin{bmatrix} 0.47 \\ 0.45 \end{bmatrix} = 0.47 - 0.225 = 0.245$

WHY the negative weight? The two state dimensions can have opposing effects, allowing the model to learn complex patterns (e.g., "output high when first dimension is high BUT second is low").

Mamba: Selective State Spaces

S4 was a breakthrough but had a key limitation: the matrices $\bar{\mathbf{A}}, \bar{\mathbf{B}}, \mathbf{C}$ are input-independent. The same filter is applied to every token.

WHY selective? Consider processing a document: the model might want to remember a name mentioned in the first sentence for the entire sequence, but forget filler words immediately. Fixed SSMs can't make this choice—Mamba can.

HOW is this computed efficiently? This breaks the convolution view (kernel is now input-dependent), so we can't use FFT. Mamba uses specialized hardware-aware kernels that fuse the recurrent computation with careful memory management, achieving speed comparable to FFT-based S4 despite being recurrent.

Worked example Mamba Selection Example

Scenario: Processing the sentence "John went to the store and bought milk."

Traditional S4: Each word gets the same decay rate. If we set long memory, we remember "went" and "and" as much as "John" (wasteful). If short memory, we forget "John" too quickly.

Mamba:

Token "John": model learns large $\Delta$ → slow decay → $\bar{\mathbf{A}} \approx 0.98$
Token "and": model learns small $\Delta$ → fast decay → $\bar{\mathbf{A}} \approx 0.3$
Token "milk": model learns large $\Delta$ → remember for next sentence

HOW the selection happens: The $\text{Linear}_\Delta$ network looks at the token embedding and outputs a scalar. If the token has high "semantic importance" features, it outputs large $\Delta$ . This is learned end-to-end from the task loss.

The Mamba Architecture Block

A full Mamba block combines the selective SSM with gating and projections:

Formula Mamba Block

Input x (B, L, D)
 ↓
LayerNorm
 ↓
Project to 2*E dimensions
 ↓ (split)
 ↓           ↓
SSM path   Gate path
(selective  (Conv1D 
 SSM)       + SiLU)
 ↓           ↓
 └── ⊙ ────┘  (element-wise multiply)
      ↓
  Project back to D
      ↓
  Residual + Input

WHY the gating? Similar to GLU (Gated Linear Units), this lets the model control information flow. The gate decides "how much" of the SSM-processed information to pass through.

Training vs Inference Modes

Worked example Dual Computation Modes

Training (parallel):

Input: full sequence $x_1, \ldots, x_L$
For S4: Compute kernel $\bar{\mathbf{K}}$ once, FFT convolution
For Mamba: Parallel scan algorithm (computes all $h_k$ in $O(\log L)$ depth)
Gradients flow through entire sequence at once

Inference (sequential):

Maintain state $h_{k-1}$ in memory
Receive new token $x_k$
Update: $h_k = \bar{\mathbf{A}} h_{k-1} + \bar{\mathbf{B}}(x_k) x_k$
Output: $y_k = \mathbf{C}(x_k) h_k$
$O(1)$ time per token (constant state size!)

WHY this matters: Transformers must attend to all previous tokens ( $O(n)$ per new token). SSMs just update a fixed-size state ( $O(1)$ per token). At100K context, this is a 100,000× difference in operations.

Common mistake Common Misconception: "SSMs can't model long-range dependencies"

Wrong idea: "Recurrent models like RNNs failed because they can't remember far back. SSMs are recurrent, so they'll fail too."

Why it feels right: Vanilla RNNs do suffer from vanishing gradients over long sequences.

The truth: SSMs avoid this through:

Careful initialization: The $\mathbf{A}$ matrix is initialized with specific eigenvalues (HiPPO initialization) that create stable, long-term memory channels
Large state dimension: $N = 16\text{-}64$ for RNNs, $N = 1000\text{-}8000$ for SSMs
Structured parameterization: DPLR structure keeps gradients stable
Selection mechanism (Mamba): Can dynamically choose what to remember In practice, Mamba matches or exceeds Transformers on long-range tasks like copying strings separated by 100K tokens.

Connections to Other Models

Transformers: SSMs are an alternative to attention, trading off flexibility for efficiency
RNNs and LSTMs: SSMs are the "spiritual successor" with better long-term memory and paralelization
Convolutional Neural Networks: The convolution view links SSMs to time-series convolutions
Linear Attention: Some linear attention variants are mathematically equivalent to certain SSM configurations
Mixture of Experts: Mamba can be combined with MoE for even greater efficiency

Recall Explain to a 12-year-old

Imagine you're listening to a long song and trying to remember it. Your brain doesn't remember every single sound equally—some parts (the chorus, the melody) you remember strongly, while other parts (a quiet drum beat) you forget quickly.

A Transformer is like writing down every single sound on a huge piece of paper and constantly looking back at the whole paper. If the song is really long (like 100,000 notes!), your paper becomes gigantic and it takes forever to check everything.

A State-Space Model (SSM) is like having a small notebook where you keep summary notes. When you hear a new sound, you update your notebook based on the old notes and the new sound. Your notebook stays small no matter how long the song is!

S4 made the notebook super organized (structured) so you can flip through it really fast. Mamba made it even smarter: when an important sound comes (like the singer saying "I love you"), the notebook says "Write this in pen!" so it stays there a long time. When boring sounds come, it says "Write in pencil" so they fade away quickly.

This is why SSMs can handle super duper long sequences (like reading an entire Harry Potter book at once!) while Transformers would get tired halfway through.

Flashcards

#flashcards/ai-ml

What are the two key equations defining a continuous state-space model? :: $h'(t) = \mathbf{A}h(t) + \mathbf{B}x(t)$ (state evolution) and $y(t) = \mathbf{C}h(t) + \mathbf{D}x(t)$ (observation)

What is the time complexity of SSMs compared to Transformers for sequence length

n

SSMs are

O(n)

O(n \log n)

, while Transformers are

O(n^2)

due to the attention matrix

How do we discretize a continuous SSM for neural networks?

Define

\bar{\mathbf{A}} = e^{\mathbf{A}\Delta}

and

\bar{\mathbf{B}} = (\mathbf{A}^{-1}(e^{\mathbf{A}\Delta} - \mathbf{I})) \mathbf{B}

, then use recurrence

h_k = \bar{\mathbf{A}} h_{k-1} + \bar{\mathbf{B}} x_k

What structural constraint does S4 place on the

\mathbf{A}

matrix?

S4 uses diagonal-plus-low-rank (DPLR) structure:

\mathbf{A} = \Lambda - \mathbf{p}\mathbf{q}^*

, enabling efficient computation via FFT

What are the two computational views of an SSM?

Recurrent view (for inference):

h_k = \bar{\mathbf{A}} h_{k-1} + \bar{\mathbf{B}} x_k

, and Convolutional view (for training):

y = \bar{\mathbf{K}} \ast x

What is the SSM convolution kernel

\bar{\mathbf{K}}

\bar{\mathbf{K}} = (\mathbf{C}\bar{\mathbf{B}}, \mathbf{C}\bar{\mathbf{A}}\bar{\mathbf{B}}, \mathbf{C}\bar{\mathbf{A}}^2\bar{\mathbf{B}}, \ldots, \mathbf{C}\bar{\mathbf{A}}^{L-1}\bar{\mathbf{B}})

—the impulse response of the system

What is the key innovation of Mamba over S4?

Mamba makes SSM parameters input-dependent (selective):

\bar{\mathbf{B}}(x), \mathbf{C}(x), \Delta(x)

depend on the input token, allowing the model to choose what to remember

How does Mamba's selectivity mechanism work?

The timestep parameter

\Delta(x)

is computed per-token via a learned linear layer; large

\Delta

gives slow decay (long memory), small

\Delta

gives fast decay (quick forgetting)

Why can't Mamba use the FFT-based convolution trick from S4?

Because the kernel is now input-dependent (different for each sequence), breaking the time-invariance required for FFT convolution

What is the per-token computational cost of SSM inference vs Transformer inference?

SSMs:

O(1)

(just update fixed-size state). Transformers:

O(n)

(attend to all previous tokens)

What initialization strategy helps SSMs maintain long-term memory?

HiPPO initialization, which sets the eigenvalues of

\mathbf{A}

to specific values that create stable memory channels

At what sequence length do SSMs typically become faster than Transformers?

Around 4K-8K tokens, depending on hardware and implementation details; for <2K tokens, optimized Transformers (FlashAttention) are often faster

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

State-space models (SSMs) ek bahut hi powerful alternative hai Transformers ke liye, especially jab sequence bohot lambi ho. Socho aise—Transformer ko puri sequence yad rakhni padti hai har step pe, jaise tum ek bohot badi book ko har page khol ke dekhte raho. Jitni badi book, utna zyada kaam. But SSMek smart notebook rakhta hai jo continuously update hota rehta hai. Sirf ek chhoti si "state" yad rakhni hai, aur har naye token ke sath usko update kar lo. Yeh concept signal processing aur control theory se ata hai—hum ek continuous dynamical system banate hain jo time ke saath evolve hota hai.

S4 (Structured