"For years the field told me I had to choose. Be a recurrence and carry a state forward one step at a time, cheap to run but slow to train and forgetful past a horizon; or be an attention layer and connect everything to everything, faithful to the past but paying a quadratic toll for the privilege. I refused the choice. I am a linear recurrence with a structured matrix, so I unroll as a single global convolution at training time and fold back into a constant-memory scan at inference. I read a sequence a million tokens long without my cost exploding, I hold a signal across a length that would have drowned an LSTM, and when the clock between my observations stutters, I do not blink, because underneath I was always a differential equation pretending to be discrete. The Kalman filter recognized me first. It said: you are what I always was, only now you learned your own matrices."
A Linear Recurrence Quietly Outscaling Attention
Chapter Overview
Part III has spent four chapters circling a single tension. The gated recurrent network of Chapter 10 cured the vanishing gradient but computes step by step, slow to train and still forgetful across very long horizons. The Transformer of Chapter 12 connected any two timesteps directly and trained in parallel, but its attention matrix costs quadratic time and memory in the sequence length, which makes truly long sequences ruinously expensive. For most of the deep-learning era these felt like opposite ends of a trade-off you simply had to pick a side of. This chapter is about the family of models, built largely between 2022 and 2026, that refuses the trade-off and answers both problems at once: linear recurrences whose structure lets them train like a convolution and run like a filter, scaling to sequences of a million steps without quadratic cost and without the gradient dying.
The chapter is organized around four answers to that goal, plus a unification. It opens with structured state-space models, the S4 line that began when the HiPPO theory of optimal memory gave a principled initialization for a linear state-space layer, and its diagonal and parallel-scan descendants such as S5, which made the idea fast and practical. It then turns to selective state-space models, the Mamba architecture, whose central insight is to let the state-space parameters depend on the input so the model can choose what to remember and what to ignore, recovering the content-addressing that fixed linear recurrences lacked, all implemented with a hardware-aware parallel scan that keeps it fast on modern accelerators. Next it surveys the linear-attention family, the closely related lineage of RWKV and RetNet and their kin, which reach the same place from the Transformer side by replacing softmax attention with a kernel that admits a recurrent form, so a single architecture has both a parallel training mode and a constant-memory inference mode. Finally it crosses into continuous time with the Neural ODE family, where the residual network becomes a differential equation solved by a numerical integrator, the Latent ODE and ODE-RNN that carry this into latent sequence modeling, and the Neural CDE that drives the dynamics with the data path itself, the model built precisely for irregularly sampled and partially observed series like clinical vitals.
Section 13.6 is the intellectual climax of the entire temporal thread this book has carried since Part II. There it shows that the Kalman filter of Chapter 7, the structured state-space model of Section 13.1, the selective Mamba of Section 13.2, and the linear-attention recurrence of Section 13.3 are not four separate inventions but four instances of one template: a linear recurrence in a hidden state, $h_t = A h_{t-1} + B x_t$ with a readout $y_t = C h_t$, differing only in whether the matrices are hand-specified, learned and fixed, learned and input-dependent, or kernel-induced. The thread that began with the Kalman filter in Section 7.6, returned as the learned recurrent cell in Section 10.5, and now lands here, closes into a single equation. The classical filter and the frontier sequence model are the same object viewed at different times, and seeing that is the deepest payoff this part offers.
The chapter keeps its claims measurable. Following the Part III convention, the worked examples and the lab lean on tasks where the right answer is known exactly, a long-range copy task where recurrent networks provably fail and a synthetic irregularly-sampled series whose generating dynamics are known, so that a model's long memory and its handling of ragged time are demonstrated rather than asserted. The reward for the work is large: by the end you will understand why a 2024-era state-space layer can read a sequence longer than any LSTM could hold and longer than any Transformer could afford, and why, underneath, it is the oldest idea in the book.
Prerequisites
This chapter sits at the confluence of three earlier threads and needs all three. From Chapter 10: Recurrent Neural Networks you need the recurrence as a state carried forward and updated, the vanishing and exploding gradient problem it was built to fix, and especially the closing bridge that read the gated cell as a learned filter, because the structured and selective state-space layers here are recurrences too and inherit that whole picture. From Chapter 12: Attention and Transformers you need self-attention and its quadratic cost in sequence length, since the linear-attention family of Section 13.3 is defined by removing exactly that cost, and the entire motivation for structured state-space models is to beat the quadratic toll attention pays. From Chapter 7: State-Space Models and Filtering you need the linear state-space form, the transition and observation matrices, and the Kalman predict-correct cycle, because Section 13.6 maps every model in this chapter back onto that exact algebra. A working command of PyTorch at the level Part III has assumed throughout, defining modules and trusting autograd, is taken for granted; the continuous-time sections additionally assume comfort with ordinary differential equations and numerical integration at the level of a first course. Readers wanting refreshers on the state-space machinery, on optimization and deep learning, or on the calculus of differential equations will find every referenced chapter and the appendices indexed in the Table of Contents.
If you keep one idea from this chapter, keep this: a structured linear recurrence $h_t = A h_{t-1} + B x_t$, $y_t = C h_t$ can be unrolled as a parallel convolution for fast training and folded into a constant-memory scan for cheap inference, which answers the RNN gradient problem and the Transformer quadratic problem at once, and which is exactly the Kalman filter with its matrices learned. Structured state-space models (S4, S5) learn fixed matrices initialized by HiPPO theory for long memory; selective models (Mamba) make the matrices input-dependent so the model chooses what to remember, run by a hardware-aware scan; linear attention (RWKV, RetNet) reaches the same recurrent form by replacing softmax with a kernel; and Neural ODEs and CDEs push the recurrence into continuous time for irregularly sampled data. Section 13.6 proves these are one template seen four ways, the equation the Kalman filter of Chapter 7 has been all along.
Chapter Roadmap
- 13.1 From HiPPO to Structured State-Space Models The S4 line in full: the HiPPO theory that gives a linear state-space layer a principled long-memory initialization, the dual recurrent and global-convolution views that let the same layer train in parallel and run as a scan, and the diagonal and parallel-scan descendant S5 that made the idea fast and practical.
- 13.2 Selective State-Space Models (Mamba) and Hardware-Aware Scans Mamba and the selective state-space layer: why making the state-space parameters depend on the input restores the content-addressing that fixed linear recurrences lack, how the selection mechanism chooses what to keep and what to forget, and the hardware-aware parallel scan that keeps the model fast on modern accelerators.
- 13.3 Linear Attention, RWKV, and RetNet The same destination reached from the Transformer side: replacing softmax attention with a kernel that factorizes, so attention admits a linear recurrent form, and the architectures that exploit it, RWKV and RetNet and their kin, each with a parallel training mode and a constant-memory recurrent inference mode.
- 13.4 Neural ODEs, Latent ODEs, and ODE-RNNs Crossing into continuous time: the residual network reread as a differential equation solved by an integrator, the adjoint method that backpropagates through the solver at constant memory, and the Latent ODE and ODE-RNN that carry continuous dynamics into latent sequence modeling.
- 13.5 Neural CDEs and Irregularly-Sampled Data The continuous analogue of the RNN built for ragged time: the Neural Controlled Differential Equation, whose dynamics are driven by an interpolated path through the observed data, handling irregular sampling, missing channels, and partial observation natively, the model of choice for clinical and sensor series with no clock.
- 13.6 Bridge: Unifying RNNs, SSMs, and Linear Attention The climax of the temporal thread: the proof that the Kalman filter, the structured state-space model, the selective Mamba, and the linear-attention recurrence are four instances of one linear-recurrence template, differing only in how the matrices are obtained, the single equation toward which Sections 7.6 and 10.5 have been building.
Once you have worked through the six sections, the Hands-On Lab below chains them into a single experiment. Each lab step maps to a section, so the lab doubles as a review: by the time you finish you will have built the diagonal state-space layer of Section 13.1 in both its views, broken a recurrent baseline on the long-range copy task it cannot solve, swapped in the selective Mamba block of Section 13.2, related it to the linear-attention recurrence of Section 13.3, fit the continuous-time models of Section 13.4 and Section 13.5 on irregular data, and seen all of it collapse onto the one template of Section 13.6.
Hands-On Lab: Long Memory, Linear Time
Objective
Build the central object of this chapter with your own hands, watch it succeed where a recurrent network provably fails, then carry it into selective and continuous-time form. You will first implement a single diagonal state-space layer of Section 13.1 in both of its equivalent views, the step-by-step recurrence and the unrolled global convolution, and verify on a short input that the two produce the same output, which is the dual nature that lets the layer train in parallel and run as a scan. You will then build the long-range copy task, in which a short token to be copied appears at the very start of a long sequence and must be reproduced at the very end, with pure noise in between, the task on which an LSTM or GRU from Chapter 10 collapses as the gap grows. Training your state-space layer and a recurrent baseline head to head across increasing sequence lengths, you will produce the chapter's headline result: the state-space layer holds the copied token across a length several times longer than the recurrence can manage, in linear time. Next you will swap your fixed layer for a selective Mamba block of Section 13.2 and watch input-dependent selection improve on a variant of the task that requires ignoring distractor tokens, the content-addressing a fixed recurrence cannot do, and connect its recurrent form to the linear-attention view of Section 13.3. Finally you will leave the regular grid entirely: you will generate an irregularly-sampled series with known dynamics and fit a Neural CDE of Section 13.5 (with a Neural ODE of Section 13.4 as a baseline), confirming it handles ragged timestamps and missing channels that the discrete models cannot ingest without imputation. Throughout, you will keep one eye on Section 13.6 and watch every model you build reveal itself as the same linear recurrence.
What You'll Practice
- Implementing a diagonal state-space layer in both its recurrent and global-convolution views and verifying their equivalence, following Section 13.1.
- Constructing the long-range copy task and racing a state-space layer against a recurrent baseline across sequence lengths to measure long memory in linear time, following Section 13.1 and Chapter 10.
- Swapping in a selective Mamba block and demonstrating input-dependent selection on a distractor task, following Section 13.2.
- Relating the selective recurrence to the linear-attention form of RWKV and RetNet, following Section 13.3.
- Fitting a Neural CDE and a Neural ODE on an irregularly-sampled series with known dynamics, following Section 13.4 and Section 13.5.
- Recognizing each model as one instance of the unified linear-recurrence template, following Section 13.6.
Setup
You need PyTorch for the state-space layer, the Mamba block, and the continuous-time models, NumPy to generate the synthetic copy task and the irregularly-sampled series, and Matplotlib to plot accuracy and runtime against sequence length. The continuous-time steps use torchdiffeq for the differential-equation solver and its adjoint backward pass, and the selective step can use the reference mamba-ssm package once you have built the diagonal layer yourself so you know what it computes. No dataset download is required; both the copy task and the irregular series are generated in a few lines so the lab runs out of the box, and the irregular series respects the temporal split discipline of Chapter 2 so a strong score reflects genuine extrapolation rather than a leak. The recurrent baseline is PyTorch's nn.GRU, the same drop-in cell the Chapter 10 lab used, so the head-to-head comparison reuses identical training code and differs only in the sequence layer.
import torch, torch.nn as nn
class DiagonalSSM(nn.Module):
"""A single diagonal state-space layer: h_t = A h_{t-1} + B x_t, y_t = C h_t."""
def __init__(self, state=64, channels=1):
super().__init__()
# diagonal A parameterized so |a| < 1 keeps the recurrence stable and trainable
self.log_neg_a = nn.Parameter(torch.rand(state) * 0.5 - 4.0) # a = -exp(log_neg_a)
self.B = nn.Parameter(torch.randn(state, channels) * 0.1)
self.C = nn.Parameter(torch.randn(channels, state) * 0.1)
def forward(self, x): # x: (batch, length, channels)
a = torch.exp(self.log_neg_a) # stable diagonal transition, 0 < a < 1
h = x.new_zeros(x.size(0), a.size(0)) # hidden state per batch element
ys = []
for t in range(x.size(1)): # recurrent view; the conv view runs in parallel
h = a * h + (self.B @ x[:, t].T).T # h_t = A h_{t-1} + B x_t (diagonal A)
ys.append((self.C @ h.T).T) # y_t = C h_t
return torch.stack(ys, dim=1)
Steps
Step 1: Build the diagonal SSM in both views and verify equivalence
Take the recurrent layer above and derive its global-convolution form: unrolling the linear recurrence shows that $y_t$ is a convolution of the input with the kernel $C A^k B$, which for a diagonal $A$ is a geometric sequence you can compute in closed form and apply with an FFT. Implement that convolution view and confirm on a short random input that it produces the same output as the step-by-step loop, the equivalence of Section 13.1 that lets the layer train in parallel as a convolution and run at inference as a constant-memory scan.
Step 2: Break a recurrent baseline on the long-range copy task
Generate the copy task: a short token at the start of a sequence, a long stretch of noise, then a marker that asks the model to reproduce the start token at the end. Train a nn.GRU baseline across growing sequence lengths and watch its copy accuracy fall toward chance as the gap grows, the same long-horizon failure Chapter 10 measured, now pushed to lengths where even a gated cell gives out.
Step 3: Race the state-space layer and measure linear-time long memory
Train your diagonal state-space layer on the identical task and lengths. It should hold high copy accuracy across sequences several times longer than the GRU could, and because the layer trains via the convolution view, plot its wall-clock training time against length and confirm it grows roughly linearly, not quadratically, the headline claim of Section 13.1 made concrete.
Step 4: Swap in a selective Mamba block and add distractors
Replace the fixed layer with a selective Mamba block of Section 13.2 and modify the task so distractor tokens that must be ignored appear in the noise stretch. Because the selective layer's parameters depend on the input, it can learn to admit the real token and reject the distractors, the content-addressing a fixed linear recurrence cannot perform, and it should beat the fixed layer on this variant while keeping the linear-time scaling.
from mamba_ssm import Mamba # reference selective state-space block (Section 13.2)
# drop-in replacement for the sequence layer: input-dependent A, B, C give selection
mamba = Mamba(d_model=64, d_state=16, d_conv=4, expand=2) # hardware-aware parallel scan inside
y = mamba(x) # x: (batch, length, 64); same shape out, linear in length
Step 5: Relate the recurrence to the linear-attention view
Write the selective recurrence's state update as the running sum a linear-attention model of Section 13.3 maintains, and confirm numerically that the RWKV or RetNet style recurrent state and the state-space hidden state evolve the same way on a short input. This is the bridge of Section 13.6 in miniature: two architectures from opposite origins keeping the same linear recurrence.
Step 6: Fit a Neural CDE on an irregularly-sampled series
Generate a series with known continuous dynamics, then drop and jitter timestamps and mask some channels so it is genuinely irregular and partially observed. Fit a Neural ODE of Section 13.4 as a baseline and a Neural CDE of Section 13.5, whose dynamics are driven by an interpolation of the data path, and confirm the CDE ingests the ragged timestamps and missing channels natively and recovers the dynamics where a discrete model would need imputation first.
Expected Output
The lab produces a layered result. Step 1 yields two implementations of one layer that agree to numerical precision, the concrete proof of the recurrent and convolution duality. The copy-task plot of Steps 2 and 3 is the chapter's headline figure: the GRU's accuracy collapses toward chance as the gap grows while the state-space layer holds high accuracy across far longer sequences, and its training time grows linearly rather than quadratically with length, long memory in linear time as promised. Step 4 shows the selective Mamba block beating the fixed layer on the distractor variant, demonstrating that input-dependent selection recovers content-addressing without giving up the scaling. Step 5 shows the selective recurrence and a linear-attention recurrence evolving the same hidden state, the unification of Section 13.6 verified on a toy input. Step 6 closes on irregular time: the Neural CDE fits the ragged, partially-observed series natively and recovers its dynamics, where the discrete models could only have run after imputation. The reader finishes having built, broken, and unified the frontier sequence models with their own hands, and having seen, line by line, that the 2024-era state-space layer and the classical Kalman filter are the same recurrence.
Every model in this lab has a maintained reference implementation, and the line-count savings are dramatic. A correct diagonal state-space layer with the FFT-based convolution view, numerically careful kernel construction, and a stable parameterization runs to well over a hundred lines from scratch; the mamba-ssm package supplies a complete selective block, hardware-aware scan and all, in a single constructor call, and handles the custom CUDA kernel internally. The torchdiffeq library supplies the differential-equation solvers and, crucially, the adjoint backward pass that backpropagates through the integrator at constant memory, turning a Neural ODE or Neural CDE into a few lines where a hand-rolled solver with manual gradients would be hundreds and easy to get wrong. The discipline of the chapter still holds: build the diagonal layer yourself once, as Section 13.1 does, so you know exactly what kernel the recurrence computes, then let these libraries carry every experiment. They handle the FFT convolution, the fused scan, and the adjoint integration that you would otherwise spend the whole lab debugging.
Stretch Goals
- Push the copy-task length until the state-space layer also begins to fail, and report the length at which it does, locating the practical ceiling of the fixed diagonal layer of Section 13.1.
- Stack several selective blocks into a small Mamba language or forecasting model and compare its throughput against a Transformer of matched parameter count on a long sequence, quantifying the quadratic-versus-linear gap of Section 13.2 and Section 13.3.
- Replace the Neural CDE's interpolation scheme with a different one (linear, cubic Hermite) and measure the effect on the irregular-series fit, probing the data-path control of Section 13.5.
What's Next?
This chapter assembled the linear-recurrence and continuous-time toolkit and proved it is one idea wearing four faces. Chapter 14: Deep Forecasting Architectures puts that toolkit, together with the convolutions of Chapter 11 and the attention of Chapter 12, to work on the concrete problem this book opened with: forecasting. It surveys the architectures that now dominate the forecasting benchmarks, the patched and channel-independent Transformers, the frequency-domain forecasters that pick up the spectral thread from Chapter 4, the state-space and linear models that descend directly from this chapter, and the careful, sometimes deflating, lesson that a well-tuned linear baseline can rival a deep model on many series. Where this chapter built the sequence layers, the next chapter assembles them into full forecasting systems and asks which one you should actually reach for, with the running finance and energy series as the proving ground. The linear recurrence you built here does not retire; it shows up in Chapter 14 as one of the strongest forecasters in the lineup.
Bibliography & Further Reading
Structured State-Space Models
Gu, A., Goel, K., Re, C. "Efficiently Modeling Long Sequences with Structured State Spaces." ICLR, 2022. arXiv:2111.00396. arxiv.org/abs/2111.00396
The S4 paper that launched the structured state-space line, with the dual recurrent and convolution views and the long-range memory that anchors Section 13.1.
Gu, A., Dao, T., Ermon, S., Rudra, A., Re, C. "HiPPO: Recurrent Memory with Optimal Polynomial Projections." NeurIPS, 2020. arXiv:2008.07669. arxiv.org/abs/2008.07669
The theory of optimal memory by polynomial projection that gives the state-space layer its principled long-memory initialization, the foundation under S4 in Section 13.1.
Smith, J. T. H., Warrington, A., Linderman, S. W. "Simplified State Space Layers for Sequence Modeling." ICLR, 2023. arXiv:2208.04933. arxiv.org/abs/2208.04933
The S5 paper that simplified S4 to a diagonal multi-input layer run by a parallel scan, the fast and practical descendant featured in Section 13.1.
Selective State-Space Models
Gu, A., Dao, T. "Mamba: Linear-Time Sequence Modeling with Selective State Spaces." 2023. arXiv:2312.00752. arxiv.org/abs/2312.00752
The Mamba paper introducing input-dependent selection and the hardware-aware parallel scan, the entire subject of Section 13.2.
Dao, T., Gu, A. "Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality." ICML, 2024. arXiv:2405.21060. arxiv.org/abs/2405.21060
The Mamba-2 and state-space duality paper that formally ties structured state-space models to attention, the theoretical heart of the unification in Section 13.6.
Linear Attention and Its Kin
Peng, B., et al. "RWKV: Reinventing RNNs for the Transformer Era." Findings of EMNLP, 2023. arXiv:2305.13048. arxiv.org/abs/2305.13048
The RWKV architecture with a parallel training mode and a constant-memory recurrent inference mode, a central example of the linear-attention family of Section 13.3.
Sun, Y., Dong, L., Huang, S., Ma, S., Xia, Y., Xue, J., Wang, J., Wei, F. "Retentive Network: A Successor to Transformer for Large Language Models." 2023. arXiv:2307.08621. arxiv.org/abs/2307.08621
RetNet and its retention mechanism, which admits parallel, recurrent, and chunked forms, the other anchor of the linear-attention lineage in Section 13.3.
Continuous-Time Models
Chen, R. T. Q., Rubanova, Y., Bettencourt, J., Duvenaud, D. "Neural Ordinary Differential Equations." NeurIPS, 2018. arXiv:1806.07366. arxiv.org/abs/1806.07366
The paper that recast the residual network as a differential equation and introduced the constant-memory adjoint backward pass, the foundation of Section 13.4.
Rubanova, Y., Chen, R. T. Q., Duvenaud, D. "Latent ODEs for Irregularly-Sampled Time Series." NeurIPS, 2019. arXiv:1907.03907. arxiv.org/abs/1907.03907
The Latent ODE and ODE-RNN built for irregular sampling, the continuous-time latent sequence models of Section 13.4 and the setup for Neural CDEs.
Kidger, P., Morrill, J., Foster, J., Lyons, T. "Neural Controlled Differential Equations for Irregular Time Series." NeurIPS, 2020. arXiv:2005.08926. arxiv.org/abs/2005.08926
The Neural CDE, the continuous analogue of the RNN whose dynamics are driven by the data path itself, the central model of Section 13.5 for irregularly-sampled series.
Tools & Libraries
Chen, R. T. Q., et al. "torchdiffeq: Differentiable ODE solvers with full GPU support and adjoint backpropagation." GitHub. github.com/rtqichen/torchdiffeq
The reference PyTorch library of differentiable ODE solvers with the adjoint backward pass, the engine behind the Neural ODE and Neural CDE steps of the lab.
Datasets & Benchmarks
Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., Metzler, D. "Long Range Arena: A Benchmark for Efficient Transformers." ICLR, 2021. arXiv:2011.04006. arxiv.org/abs/2011.04006
The Long Range Arena benchmark of long-sequence tasks on which structured state-space models first demonstrated their decisive long-memory advantage, the field test behind Sections 13.1 and 13.2.