HiPPO: Optimal Polynomial Memory for Sequence Models
State space models such as S4 and Mamba read a sequence one step at a time and carry
only a small state of fixed size, yet they recall structure from thousands of steps
earlier. The theory behind this is HiPPO:
high-order polynomial projection operators. The construction follows,
and the demo below runs it on preset or hand-drawn signals.
A recurrent model consumes its input step by step and carries everything it knows
forward in a state vector of fixed size. The past keeps growing; the state does not.
Classical RNNs manage this tension with gates, leaks, and initialization schemes, yet
still struggle to retain information over long horizons. Attention avoids the problem by
keeping every past token and paying a quadratic cost to do so.
Given a budget of only \(N\) numbers about the past, HiPPO determines in closed form
which \(N\) they should be.
2 · Memory as function approximation
Treat the input seen so far as a function \(f\) on \([0, t]\) rather than a
list of values. Remembering the past then means keeping a compressed description of
that function, and compressing a function reduces to approximating \(f\) by a
polynomial.
Two choices define the scheme. A measure \(\omega(t, x)\) sets how
much weight each past moment \(x\) receives; it can emphasize recent history or weight
all of it equally. An orthonormal polynomial basis
\(g_0, g_1, \dots, g_{N-1}\) is then fixed with respect to that measure. The memory is
the coefficient vector \(c(t) \in \mathbb{R}^N\) of the least-squares polynomial
approximation of the history:
The left equation writes memory, projecting the history onto basis function
\(n\). The right equation reads memory: the basis functions mixed with weights
\(c_n\) reconstruct the history. The approximation is optimal in the least-squares
sense. Under the measure \(\omega\), no other \(N\) numbers formed from linear
projections give a smaller error.
3 · Updating without recomputing
The projection integral runs over the whole history, and the history grows at every
instant, so recomputing \(c(t)\) from scratch at each step would defeat the purpose.
The main result of the HiPPO paper is that no recomputation is required. For natural
choices of measure the coefficient vector satisfies a
linear ordinary differential equation driven by the incoming signal,
where \(A(t) \in \mathbb{R}^{N \times N}\) and \(B(t) \in \mathbb{R}^{N}\) have closed
forms. Updating the projected memory of the entire past requires only the current
memory and the newest sample. The proof differentiates the projection integral in
\(t\), uses the fact that the derivative of a Legendre polynomial is a combination of
lower-order Legendre polynomials, and collects the boundary terms. The calculus is
routine; the resulting update is linear, online, and exact.
For the uniform measure over the whole history, called HiPPO-LegS
(for scaled Legendre), the operators are:
\[
\frac{d}{dt}\, c(t) = -\tfrac{1}{t} A\, c(t) + \tfrac{1}{t} B\, f(t),
\qquad
A_{nk} =
\begin{cases}
\sqrt{(2n+1)(2k+1)} & n > k \\[2pt]
n + 1 & n = k \\[2pt]
0 & n < k ,
\end{cases}
\qquad
B_n = \sqrt{2n+1}.
\]
Note the factor \(1/t\): as the history grows, the dynamics slow in proportion. This
makes LegS timescale-equivariant. Stretching the input in time stretches the
memory with it, with no timescale hyperparameter to tune.
4 · The demo
A signal \(f\) streams in from left to right. The model keeps only the \(N\) numbers of
\(c(t)\). At each instant the
green curve is the reconstruction \(\hat f\) decoded
from those numbers, drawn over the interval that the measure weights (the
shaded band). The three lower panels show the state
itself, the basis functions it weights, and the operators \(A\) and \(B\) that drive
it.
Switch the measure to change what “remembering the past” means: whole history, sliding window, or exponential decay.
Drag the \(N\) slider to change the memory budget and watch resolution appear and disappear.
Draw your own signal with the pencil button, or scrub time by dragging on the chart.
Hover any panel for exact values.
Measure — how the past is weighted
Input signal
Memory budget — N = 16
Window length
signal \(f\)reconstruction \(\hat f\) from \(c(t)\)measure \(\omega\)
t = 0.00 serror —
Drawing mode — drag across the chart to reshape the signal
The state \(c(t)\)
These 16 numbers are everything the model remembers.
Weighted basis functions
Each coefficient scales one polynomial; their sum is the green reconstruction.
The operators \(A\), \(B\)
Fixed matrices, determined by the measure alone. Blue positive, red negative.
5 · Things to try
The budget is the resolution
With \(N=4\), only the coarse trend survives. Raise \(N\) and each added
coefficient resolves one more oscillation of the signal.
Graceful forgetting
LegS never abandons the past; it spreads a fixed budget over a growing
interval. Early bumps blur while recent ones stay sharp.
Hard forgetting
LegT is all-or-nothing: near-perfect recall inside the window, and a bump that
slides past its edge is gone rather than blurred.
Smooth recency bias
LagT fades the past exponentially. The square wave’s last edge stays
crisp while older transitions dissolve. Lower the decay rate to remember longer.
Too fast to catch
A chirp accelerates without bound. LegS spreads its budget over all of history
and eventually cannot track it; switch to LegT and it locks on inside the
window.
Break it yourself
Draw a signal with something hidden in it, a sharp spike or a long silence,
and see what each memory keeps and what it discards.
6 · The three measures
The measure determines the character of the memory. The paper derives operators for
several measures; the demo implements the three standard ones.
Measure \(\omega\)
Dynamics
Character
LegS scaled Legendre
uniform on \([0, t]\)
\(\dot c = -\tfrac{1}{t}A c + \tfrac{1}{t}B f\)
Never forgets; resolution stretches thinner as history grows. Timescale-robust, parameter-free.
LegT translated Legendre
uniform on \([t-\theta,\, t]\)
\(\dot c = -\tfrac{1}{\theta}A c + \tfrac{1}{\theta}B f\)
Sharp inside a sliding window, amnesia beyond it. Requires choosing \(\theta\). Recovers the Legendre Memory Unit.
LagT Laguerre
\(e^{-r(t-x)}\) decay
\(\dot c = r(-A c + B f)\)
Smooth recency bias with constant dynamics; the “leaky” memory of classical RNNs, done optimally.
For LegT the matrix takes the form \(A_{nk} = \sqrt{(2n+1)(2k+1)}\) below the diagonal
and \(\sqrt{(2n+1)(2k+1)}\,(-1)^{n-k}\) above it; the alternating upper triangle is
visible in the operator panel of the demo. For LagT, \(A\) is the lower-triangular
matrix of ones. None of these matrices is learned; each follows from the choice of
measure alone.
7 · From ODE to RNN
Real data is discrete, so the ODE is discretized with a step \(\Delta t\). The demo
fixes \(\Delta t = 0.01\) and uses the bilinear (Tustin) method, the same one used
throughout the S4 line of work:
where \(A'\) and \(B'\) denote the continuous operators with their \(1/t\),
\(1/\theta\), or \(r\) scaling folded in. The result is a linear recurrence
\(c_{k+1} = \bar A c_k + \bar B f_k\), a recurrent network whose weights are fixed and
structured rather than learned. The demo runs this recurrence one sample at a time.
8 · From HiPPO to S4 and Mamba
HiPPO connects two lines of work. The
Legendre Memory Unit,
whose update rule is exactly HiPPO-LegT, came first; the modern state space models
came after. S4 uses the
HiPPO-LegS matrix as the initialization of a learned state space layer, and
its ablations show the choice is not cosmetic: replacing the HiPPO initialization with
a random matrix collapses performance on long-range benchmarks. A later paper,
How to Train Your HiPPO,
generalized the theory and explained why even the diagonal approximations in S4
inherit the memory properties.
Mamba keeps the state
space structure and makes the dynamics input-dependent, so the model learns when to
write to memory and when to forget, on top of the construction shown here.