Skip to content
AI360XpertBeta

State Space Models

A state space model compresses the entire past into a fixed-size hidden state that is updated one input at a time, giving linear-time inference without the quadratic score matrix that attention requires.

A scalar state updated as h equals 0.9 h plus 0.5 x turns inputs 1, 0 and 2 into states 0.5, 0.45 and 1.405, so one fixed number carries the past forward
A scalar state updated as h equals 0.9 h plus 0.5 x turns inputs 1, 0 and 2 into states 0.5, 0.45 and 1.405, so one fixed number carries the past forward

Why Does This Exist?

Full attention compares every token with every other token. That pairwise grid is exact recall at quadratic price. Linear attention keeps the grid and approximates it. State space models drop the grid entirely.

The idea comes from control theory. Keep one fixed size summary h. When a new input x arrives, update the summary with a transition A and an input gain B, then read the output y with an output gain C. Generating the next token costs one update and one read, no scan of history. Memory stays flat as length grows.

One idea underneath it. A hidden state is running memory with fixed shape. Attention memory grows with N. A state of dimension d costs O(d)O(d) to store and O(d2)O(d^2) to update, with no N in either term. That is the hardware win, and the diagram above draws it for a scalar state.

This page covers the recurrence, a hand computed run, and the tradeoff. The gated recurrent cousin lives in long-short-term-memory. The selective modern form lives in mamba.

Think of It Like This

A whiteboard that never gets bigger

You track a long game on one small whiteboard. Each play you erase a little of what is there, write in the new score, and copy one number to the sheet as the official output. The board never grows. Reading the output costs one glance, no matter how many plays came before.

The board is the state h. How fast old marks fade is A. How bold the new marker is counts as B. What you copy to the sheet counts as C.

Where it stops: a small board smears details. It remembers that recent plays were high scoring, not the exact second quarter score. When your task needs one exact far back token, a fixed board can drop it while attention would fetch it directly.

How It Actually Works

The discrete recurrence is two lines. Here hth_t is the state at step t, xtx_t the input, yty_t the output, AA the transition, BB the input gain, CC the output gain:

ht=Aht−1+Bxt,yt=Chth_t = A h_{t-1} + B x_t, \quad y_t = C h_t

In plain words: mix a faded old state with the scaled new input, then read out a scaled state. With learned AA, BB, CC plus a step size for discrete tokens, training can run as a convolution over the whole sequence while inference runs step by step. Same weights, two execution orders.

Worked example with three inputs

Take scalars A=0.9A = 0.9, B=0.5B = 0.5, C=1.0C = 1.0 and inputs 1.01.0, 0.00.0, 2.02.0 from rest h0=0h_0 = 0.

Step 1: h1=0.9×0+0.5×1.0=0.50h_1 = 0.9 \times 0 + 0.5 \times 1.0 = 0.50. Output y1=0.50y_1 = 0.50.

Step 2: h2=0.9×0.50+0.5×0.0=0.45h_2 = 0.9 \times 0.50 + 0.5 \times 0.0 = 0.45. Output y2=0.45y_2 = 0.45. The zero input still fades memory by 0.90.9.

Step 3: h3=0.9×0.45+0.5×2.0=0.405+1.0=1.405h_3 = 0.9 \times 0.45 + 0.5 \times 2.0 = 0.405 + 1.0 = 1.405. Output y3=1.405y_3 = 1.405.

One number carried the past through all three steps. That is the diagram headline: boxes for 1, 0 and 2 feeding states 0.5, 0.45 and 1.405.

Why init matters and what selection adds

A random A often fades too fast or blows up, the same pathology old recurrent nets hit. Structured inits start A as a matrix that preserves long history well, projecting past inputs onto smooth basis functions rather than learning that from scratch. Modern selective forms go further and let B, C and the step depend on the input, so the model can keep a surprising token and skip filler. That input dependence is the step from classic SSMs to mamba.

Code

Run the three step scalar recurrence with plain Python. No library needed.

A = 0.9B = 0.5C = 1.0xs = [1.0, 0.0, 2.0]h = 0.0for t, xv in enumerate(xs, start=1):    h = A * h + B * xv    print(f"t={t} h={h:.4f} y={C*h:.4f}")# -> t=1 h=0.5000 y=0.5000# -> t=2 h=0.4500 y=0.4500# -> t=3 h=1.4050 y=1.4050

The printout matches the hand arithmetic. Change AA to 0.00.0 and rerun: each state equals half the current input, memory vanishes, which shows how A alone controls how far back the state reaches.

Watch Out For

Expecting exact far back recall from a fixed state

A test hides one code early in a long log and asks for it verbatim at the end. Attention can point at it exactly. A small fixed state may have smeared it away several thousand steps earlier.

Symptom: strong average loss with failures on planted exact recall probes that attention passes. Fix: grow state dimension, add selective gating as in mamba, or pair the SSM with retrieval or a few global attention layers. Choose by probe, not by average loss alone.

Mixing up the two execution orders

Training as a convolution and inference as a recurrence are the same model run two ways. Weights AA, BB and CC do not change between them.

Symptom: separate copies drift during edits and outputs disagree by far more than floating error. Fix: keep one weight set and test both paths on the three input example above. They must agree to about 1e−61e-6. If not, the bug is in padding, masking or the step size, not the theory.

The Quick Version

  • A state space model keeps a fixed size state updated by h=Ah+Bxh = A h + B x with output y=Chy = C h.
  • Our scalar run with A 0.9 and B 0.5 turns inputs 1, 0 and 2 into states 0.5, 0.45 and 1.405.
  • Inference costs one update per step with O(d)O(d) memory, no scan of history and no score matrix.
  • Good init preserves long history from the start, and input dependent selection keeps surprising tokens.
  • Fixed states smear exact far back detail, so test planted recall before choosing over attention.