S4

The paper made structured state-space models a practical long-sequence architecture family.

Metadata

Field	Value
Paper	Efficiently Modeling Long Sequences with Structured State Spaces
Authors	Albert Gu, Karan Goel, Christopher Ré
Year	2021 preprint; ICLR 2022
Venue	ICLR 2022
arXiv	2111.00396
OpenReview PDF	uYLFoz1vlAC
Hazy Research	Structured State Spaces for Sequence Modeling
Status	verified

Question

Transformers use pairwise attention and scale quadratically in sequence length. RNNs scan sequences linearly but often struggle with very long-range dependencies and parallel training. CNNs can be efficient but need large receptive fields or dilation to cover long context.

S4 asks:

$$\text{Can a state-space model handle very long sequences efficiently and accurately?}$$

The target regime is not just a few hundred tokens. The paper is motivated by sequences with thousands or tens of thousands of steps.

Main Claim

S4 proposes a structured parameterization of state-space sequence models that preserves long-range modeling ability while making the computation practical.

The core architecture claim is:

$$\text{continuous-time state-space model}\to \text{structured parameterization}\to \text{efficient convolution/scan sequence layer}.$$

The durable contribution is not a new task objective. It is a sequence-mixing layer that becomes a serious alternative to attention for long-range modeling.

Architecture Contract

Item	Contract
Input	sequence $u_0,\dots ,u_{L-1}$
Output	sequence $y_0,\dots ,y_{L-1}$ or pooled task representation
Core model	linear state-space system
Main state	latent state $x(t)$
Continuous dynamics	$x^{\prime }(t)=Ax(t)+Bu(t)$
Observation	$y(t)=Cx(t)+Du(t)$
Efficient view	sequence convolution with a structured kernel
Main goal	long-range dependency modeling with practical compute
Later lineage	S4 variants, S5/DSS, Mamba-style selective SSMs

State-Space Model Form

A continuous-time linear state-space model is:

$$x^{\prime }(t)=Ax(t)+Bu(t),$$ $$y(t)=Cx(t)+Du(t).$$

Here:

Symbol	Meaning
$u(t)$	input signal
$x(t)$	hidden state
$y(t)$	output signal
$A$	state transition matrix
$B$	input projection into state
$C$	readout from state
$D$	skip/direct input-output term

After discretization, a simple recurrent form is:

$$x_k=\bar{A}{x}_{k-1}+\bar{B}{u}_k,$$ $$y_k=\bar{C}{x}_k+\bar{D}{u}_k.$$

This looks RNN-like, but S4 uses a carefully structured linear dynamical system rather than arbitrary recurrent cells.

Recurrent View and Convolution View

The recurrent update is:

$$x_k=\bar{A}{x}_{k-1}+\bar{B}{u}_k.$$

Unrolling gives:

$$y_k=\bar{C}{\bar{A}}^k\bar{B}{u}_0+\bar{C}{\bar{A}}^{k-1}\bar{B}{u}_1+\cdots +\bar{C}\bar{B}{u}_k.$$

This can be written as a convolution:

$$y_k=\sum _{i=0}^k{K}_i{u}_{k-i},$$

where the convolution kernel is:

$$K_i=\bar{C}{\bar{A}}^i\bar{B}.$$

So the same layer has two useful views:

View	Use
recurrent scan	streaming inference and stateful processing
convolution	parallel training over full sequences

This duality is one reason SSMs became attractive as sequence architectures.

Why Structure Is Needed

A generic state matrix $A$ is hard to use efficiently and stably for long sequences. Computing:

$$K_i=\bar{C}{\bar{A}}^i\bar{B}$$

for many $i$ can be expensive or unstable.

S4’s architecture contribution is to choose a structured parameterization that makes the kernel computation efficient while preserving long-memory behavior.

The paper uses a structured state matrix based on a normal-plus-low-rank form:

$$A\approx \Lambda -P{Q}^{\top }$$

where $\Lambda$ is diagonal or normal-like after transformation, and $P{Q}^{\top }$ is a low-rank correction.

The exact implementation details are mathematical, but the architecture reading point is:

$$\text{state matrix structure}\Rightarrow \text{stable long-range kernel}\Rightarrow \text{fast sequence layer}.$$

Cauchy Kernel Computation

S4 reduces part of the computation to a Cauchy kernel form. Abstractly, terms look like:

$$\sum _i\frac{a_i}{z-{\lambda }_i}.$$

This matters because the layer is not “just an RNN.” The speed comes from turning a structured dynamical system into efficient numerical operations for the convolution kernel.

For architecture reading, this should be remembered as:

$$\text{SSM dynamics}\to \text{structured kernel}\to \text{parallel convolution implementation}.$$

Relation to RNNs

S4 and RNNs both carry state:

$$x_k=f(x_{k-1},u_k).$$

But a standard RNN learns a nonlinear transition directly:

$$h_k=\sigma (W_h{h}_{k-1}+W_u{u}_k+b).$$

S4 starts from a linear dynamical system with structured matrices and usually places nonlinearities around SSM layers in a deep network.

Axis	RNN / LSTM	S4
state update	learned recurrent cell	structured state-space dynamics
long memory	controlled by gates or recurrence	controlled by state matrix spectrum and HiPPO-inspired structure
training parallelism	often sequential bottleneck	convolution view enables parallel training
inference	scan/recurrent	scan/recurrent
inductive bias	learned hidden-state recurrence	continuous-time sequence dynamics

S4 is therefore a return to recurrence, but with different mathematics and implementation.

Relation to Transformers

Transformers mix tokens with attention:

$$Y=\mathrm{softmax}\left(\frac{Q{K}^{\top }}{\sqrt{d}}\right)V.$$

This gives direct pairwise token interaction but costs:

$$O(L^2).$$

S4 uses state-space sequence mixing:

$$y=K\ast u$$

with a structured kernel $K$. It does not build a token-token attention matrix.

Axis	Transformer	S4
mixing primitive	pairwise attention	structured sequence convolution / scan
long sequence cost	quadratic in length for dense attention	near-linear or efficient convolution depending implementation
memory	attention matrix and activations	state/kernel representation
pairwise content routing	explicit through $Q{K}^{\top }$	implicit through state dynamics
streaming	needs caching design	natural recurrent state view

S4 is an architecture answer to the same long-context pressure that also motivated Performer and later Mamba.

Relation to Mamba

S4 is a key predecessor of modern state-space sequence architectures. Mamba keeps the long-sequence SSM motivation but makes the dynamics selective and input-dependent.

Axis	S4	Mamba
SSM parameters	largely time-invariant after input projection	input-dependent selective parameters
core issue	efficient long-range SSM layer	content-aware selection without attention
implementation view	convolution/scan	hardware-aware selective scan
role in lineage	makes SSMs practical	makes SSMs competitive for dense token modalities

The reading path is:

$$\text{RNN/LSTM}\to \text{S4}\to \text{Mamba}.$$

Relation to CNNs

Because S4 can be computed as a convolution, it also relates to CNNs:

$$y_k=\sum _i{K}_i{u}_{k-i}.$$

But the kernel $K_i$ is generated from state-space dynamics rather than learned as an unconstrained finite convolution filter. This gives S4 a long-range structured kernel:

| Axis | CNN | S4 | | --- | --- | | kernel | learned finite local kernel | generated long sequence kernel | | receptive field | grows with depth, dilation, or large kernels | can cover long contexts through state dynamics | | structure | locality and translation sharing | continuous-time dynamical prior | | training | convolution | convolution view |

This is why S4 is often described as combining recurrent, convolutional, and continuous-time views.

Evidence to Read

The paper’s evidence should be read around long-range dependency modeling:

Evidence	What It Supports
Long Range Arena	ability to handle long sequences and difficult long-context tasks
Path-X	stress test for length around $16k$
sequential image tasks	whether sequence models can process flattened visual inputs
language/audio experiments	cross-modality sequence modeling
generation speed	recurrent/scan view can make autoregressive inference efficient

The important claim is:

$$\text{S4 is not only asymptotically attractive; it works on long-range benchmarks}.$$

What to Watch in the Ablations

S4 has a dense mathematical core. When reading, separate:

Question	Why It Matters
What structure is imposed on $A$?	controls stability and efficient computation
Is the task truly long-range?	otherwise attention/CNN baselines may be enough
Is training parallel or recurrent?	affects throughput and memory
How is discretization handled?	continuous-to-discrete conversion changes dynamics
What nonlinear wrapper is used?	SSM kernel alone is usually part of a deep block
Are baselines equally tuned?	long-sequence benchmarks are sensitive to recipes

Failure Modes and Caveats

• S4 is mathematically heavier than standard attention or convolution.
• Implementation details matter: kernel computation, discretization, numerical stability, and parameterization affect results.
• The original S4 layer is not as simple to implement as later diagonal or selective variants.
• Strong long-range benchmark performance does not automatically imply better language-model scaling.
• S4 is mostly time-invariant within a layer; later models such as Mamba emphasize input-dependent selection.

Why This Matters for Architecture Reading

S4 changes the architecture question from:

$$\text{Which tokens should attend to which tokens?}$$

to:

$$\text{What dynamical system should summarize the sequence?}$$

That makes it a different kind of sequence model from attention. It is especially important for AI architecture notes because it explains why Mamba is not an isolated trick but part of a longer SSM line.

Links

• State-space model
• RNN
• LSTM
• CNN
• Attention
• Transformer
• Computational complexity
• Long Short-Term Memory
• Attention Is All You Need
• Performer
• Mamba

One-Line Memory

S4 is the structured state-space paper that made long-range sequence modeling practical by turning continuous-time SSM dynamics into an efficient convolution/scan layer.