State-space models (Mamba, S4): Foundations — AI-ML deep dive

Before you can read the parent note, you must own every piece of notation it throws at you. This page builds each one from nothing, in the order they depend on each other. Nothing here assumes you have seen a matrix, an ODE, or a convolution before.

1. A sequence, its index $k$ , and its length $L$

Why start at $1$ and not $0$ ? It is purely a bookkeeping choice — nothing mathematical hinges on it. Starting at $k = 1$ lets us say " $x_{1}$ is the first real input" and, later, reserve a separate label for the memory before any input has arrived (that memory is $h_{0}$ , built in §5). If you preferred $k = 0$ for the first input, you would just shift every subscript down by one; the formulas are identical.

The picture: imagine words on a page read left to right, or beads threaded on a string. Each bead sits at a position $k = 1, 2, 3, \dots, L$

Why the topic needs it: the whole point of these models is processing sequences — sentences, audio, DNA — where order matters. The counter $k$ lets us talk about "the past" (steps before $k$ ) and "the future" (steps after).

2. A vector — the state as a list of numbers

The picture: an arrow in space, or more simply, a set of $N$ dials each holding a value. If $N = 2$ you can draw it as a point on a flat plane; if $N = 1000$ you can't draw it, but it's still "just a list".

Why the topic needs it: the model's memory — the hidden state $h$ — is a vector. Each of its $N$ slots stores one running summary of the past. Bigger $N$ = more memory capacity.

3. The hidden state $h$ and its dimension $N$

The picture: a small whiteboard the model scribbles notes on. At each step it erases a bit, adds the new input's contribution, and keeps the board for next time.

Why the topic needs it: this single vector is the entire summary of everything the model has seen so far. That is what makes the model fast — it never re-reads the past; it only reads the whiskered-down summary $h$ .

4. A matrix and matrix–vector multiplication

The picture: feed an arrow in, get a rotated/stretched arrow out. See the figure below — the left dial-panel is $h$ , the grid is $A$ , the right panel is $A h$ .

Why the topic needs it. The three letters $A, B, C$ are all matrices, and they do three different jobs:

$A \in R^{N \times N}$ — mixes the old memory into the new memory (state → state).
$B \in R^{N \times 1}$ — injects the current input into the memory (input → state).
$C \in R^{1 \times N}$ — reads the memory out into an answer (state → output).

5. The recurrence, its initial state $h_{0}$ , and the output $y_{k}$

Reading the bar. The overline marks the discrete (per-step) version of a matrix. So $\overset{ˉ}{A}$ ("A-bar") is the discrete version of $A$ , and likewise $\overset{ˉ}{B}$ ("B-bar") is the discrete version of $B$ . The un-barred $A, B$ are the continuous versions (§7 explains why they differ). $C$ needs no bar — it reads the state out the same way in both worlds.

The picture: a bucket of water starting empty ( $h_{0} = 0$ ). Each step the bucket drains a fraction (that's $\overset{ˉ}{A}$ , which keeps a portion of the old level) and you pour in a splash proportional to the input (that's $\overset{ˉ}{B} x_{k}$ ). The water level is the state; the reading on a gauge attached to it is $y_{k}$ .

Why the topic needs it: this pair of lines is the model at inference time. It runs in $O (L)$ — one cheap update per token — which is exactly the linear-time promise state-space models (SSMs) make over the $O (L^{2})$ Transformer. Compare this to RNNs and LSTMs, which also carry a state forward step by step; SSMs are that idea with a cleaner, controllable update rule.

6. The derivative $h^{'} (t)$ and the continuous law

The picture: the slope of the tangent line on a curve. Steep upward slope = growing fast; flat = holding steady; downward = shrinking.

Why the tool, and why not just differences? The parent's continuous law is the ordinary differential equation (ODE)

$h'(t) = \mathbf{A}\,h(t) + \mathbf{B}\,x(t) \tag{$\star$}$

— an equation that says "the change in $h$ is determined by where $h$ is now ( $A h$ ) plus the current input ( $B x$ )". We give it the label $(⋆)$ so we can point back to it. Physics and control theory have centuries of exact tools for such laws. Working continuously first, then converting to steps, gives an exact update rule instead of the crude approximation you'd get by naively subtracting neighbouring samples.

7. The step size $Δ$ and the matrix exponential $e^{A Δ}$

Why this specific tool? The solution of the ODE $(⋆)$ (with input held constant over a step) over one full step of width $Δ$ is exactly multiply-by- $e^{A Δ}$ . So the discrete decay matrix is $\overset{ˉ}{A} = e^{A Δ}$ : it is the honest, exact answer to "if the state obeys this law, where is it one tick later?" A crude method (Euler's $\overset{ˉ}{A} \approx I + A Δ$ ) drops all the higher terms and drifts off over long sequences.

The picture — why decay: in the scalar case $e^{a Δ}$ with $a < 0$ is a number between $0$ and $1$ . Multiplying the state by it each step shrinks it — that is forgetting. The figure shows how the size of that number sets memory length: near $1$ ⇒ long memory, near $0$ ⇒ fast forgetting. This is exactly the worked example's $0.9$ (slow) vs. $0.5$ (fast).

8. Convolution and the kernel $\overset{ˉ}{K}$

The picture: a stencil dragged along the sequence; at every stop it multiplies-and-adds the values under it. This is the same operation at the heart of Convolutional Neural Networks — only there the stencil slides over an image, here over a time axis.

Formula Where the kernel comes from — unroll the recurrence

Start from $h_{0} = 0$ and apply §5's rule step by step:

h_1 &= \bar{\mathbf{B}} x_1 & &\Rightarrow\ y_1 = \mathbf{C}\bar{\mathbf{B}}\,x_1 \\ h_2 &= \bar{\mathbf{A}}\bar{\mathbf{B}} x_1 + \bar{\mathbf{B}} x_2 & &\Rightarrow\ y_2 = \mathbf{C}\bar{\mathbf{A}}\bar{\mathbf{B}}\,x_1 + \mathbf{C}\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 & &\Rightarrow\ y_3 = \mathbf{C}\bar{\mathbf{A}}^2\bar{\mathbf{B}}\,x_1 + \cdots \end{aligned}$$ Notice the pattern: the input $x_i$ from $k-i$ steps ago always arrives multiplied by $\mathbf{C}\bar{\mathbf{A}}^{\,k-i}\bar{\mathbf{B}}$ — it got injected by $\bar{\mathbf{B}}$, then aged $(k-i)$ times by $\bar{\mathbf{A}}$, then read out by $\mathbf{C}$. Collecting these weights gives $$y_k = \sum_{i=1}^{k} \big(\mathbf{C}\bar{\mathbf{A}}^{\,k-i}\bar{\mathbf{B}}\big)\,x_i,$$ which is exactly a convolution with 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}},\dots)$. So the $j$-th kernel entry is $\mathbf{C}\bar{\mathbf{A}}^{\,j}\bar{\mathbf{B}}$ — the ==impulse response==, i.e. what comes out $j$ steps after a single spike.

Why the topic needs it: unlike the step-by-step recurrence, a convolution can be computed for all positions in parallel, which is why the S4 model trains as a convolution but generates as a recurrence.

Recall Why two views of the same model?

Recurrence :::: cheap $O (L)$ generation, one token at a time, no parallelism. Convolution :::: parallel over the whole sequence, ideal for training on GPUs.

9. Complex numbers and the diagonal $Λ$ (a light touch)

You do not need complex analysis to read D1; just hold onto these plain-word meanings.

10. Big-O notation — counting cost

Why the topic needs it: this is the scoreboard of the whole chapter. Transformers are $O (L^{2})$ ; SSMs are $O (L)$ recurrent / $O (L lo g L)$ convolutional. Linear Attention is another route to $O (L)$ — SSMs are a cousin, reaching the same linear budget through a state recurrence instead of a reweighted attention sum.

How the foundations feed the topic

Equipment checklist

Read each cue, answer aloud, then reveal.

What does the subscript

k

x_{k}

mean, and what is

L

k

is the position/index in the sequence;

L

is the sequence length (last step). We count

k = 1, \dots, L

What is the initial state

h_{0}

and why do we need it?

The memory before any input — defined as the zero vector — so the recurrence has something to feed step

k = 1

; it makes

h_{1} = \overset{ˉ}{B} x_{1}

What is a vector

h \in R^{N}

An ordered list of

N

real numbers — the model's memory, one summary value per slot.

What are the three jobs of

A

B

C

A ages/mixes old state into new; B injects the current input into the state; C reads the state out into the output

y_{k}

What does the overline in

\overset{ˉ}{A}

and

\overset{ˉ}{B}

signal?

The discretized (per-step) versions of the continuous matrices

A

and

B

What does

h^{'} (t)

measure, and what is equation

(⋆)

The instantaneous rate of change of the state;

(⋆)

is the ODE

h^{'} (t) = A h (t) + B x (t)

Why use the matrix exponential

e^{A Δ}

for

\overset{ˉ}{A}

It is the exact solution of the ODE over one step of width

Δ

; simpler methods drift over long sequences.

What stability condition makes the kernel decay?

Eigenvalues of

A

must have negative real part, so each

e^{λ Δ}

has size below 1.

In the scalar case, what does

\overset{ˉ}{A}

near

1

vs. near

0

mean?

Near 1 = long memory (slow forgetting); near 0 = fast forgetting.

What does

Δ

control?

The gap between clock ticks / discretization step — effectively how fast the state forgets.

Why is the

k

-th kernel entry

C \overset{ˉ}{A}^{k} \overset{ˉ}{B}

An input injected by

\overset{ˉ}{B}

, aged

k

times by

\overset{ˉ}{A}

, then read by

C

— the impulse response.

What are the entries of the diagonal matrix

Λ

in S4?

Its eigenvalues

λ_{1}, \dots, λ_{N}

— the per-direction scaling numbers; powers are cheap because you power each entry.

What does

*

mean in

p q^{*}

Conjugate transpose: turn the column into a row and flip the sign of each imaginary part.

What do

O (L)

and

O (L^{2})

compare?

How compute grows with sequence length; SSMs are linear

O (L)

, Transformers quadratic

O (L^{2})

Ready? Head back to State-space models (Mamba, S4) and the symbols will read like plain sentences.