HiPPO: Recurrent Memory with Optimal Polynomial Projections
- Publication
- NeurIPS 2020Conference
- First submitted to arXiv
- arXiv:2008.07669
Cite this paper · BibTeX
The citation identifies the linked source version. It cites the original paper and its authors.
@misc{mambahippo2020,
title = {{HiPPO: Recurrent Memory with Optimal Polynomial Projections}},
author = {Albert Gu and Tri Dao and Stefano Ermon and Atri Rudra and Christopher Re},
year = {2020},
eprint = {2008.07669},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2008.07669}
}
We have already read S4 to better understand the research context, so let's revisit this paper.
I have to say that the author's papers are very mathematical, and you need to muster some courage before opening them.
Problem Definition
Most people are familiar with the issue of vanishing and exploding gradients in RNNs.
Although this is a characteristic inherent in the architecture, there are always some ways to mitigate it, such as adding gates like LSTM or GRU, or using special bases like Fourier Recurrent Unit or Legendre Memory Unit (LMU).
However, this only treats the symptoms, not the root cause!
The authors do not agree with these approaches. They believe these methods share some common problems:
- There is no unified theoretical framework to explain the memory mechanism.
- They often require prior knowledge about the input sequence's length or time scale.
Can we find a method that does not require prior knowledge of the time scale, has a theoretical foundation, and can address the long-term dependency issue?
Problem Solution
First, let’s reconsider the scenario of an RNN.
Compressed Representation of Sequences
Given an input function that changes over time, at each time , we want to make decisions, predictions, or representations based on all past information (i.e., the entire sequence or signal segment from the start time 0 to time , , ).
However, directly storing the entire history is impractical, because as time progresses, the amount of data increases indefinitely, making storage computationally difficult.
Therefore, we need a "compressed representation with bounded dimensions"!
That is, we hope to use a finite number of parameters (values) at each moment to approximate the entire historical information.
Next, we must choose a function subspace with bounded dimensions in which to find the best approximation.
The authors choose a natural and commonly used option: polynomial spaces.
Suppose we take as the space spanned by polynomials:
In this subspace, we can write the approximate function as
where are basis polynomials for the measure chosen at current time , and are the coefficients we need to maintain and update. Since is fixed, we only need coefficients to represent a compressed approximation of the history observed by time .
The Advantages and Disadvantages of Approximation
This brings up the next core question:
- What method should we use to define "approximation" and quantify the "quality of the approximation"?
The quality of the approximation, or "the quality of the approximation," can be measured by the "concept of distance."
Generally, we know that there is a length on the number line, a distance in the plane, and also a distance in higher-dimensional spaces. The function space (where each function is treated as a point) can also define a "distance," but the way to define this distance requires the use of integrals.
The author's idea here is:
If two functions are very close in value at every time point, we say they are "close in distance"; on the other hand, if they are inconsistent in many places, they are "far apart".
Mathematically, we define the distance between functions by introducing a "measure" and a corresponding "weighted inner product":
-
Measure
Here, we can think of the measure as a kind of "weighting system" used to indicate which time points on the time axis are more important.
If we care more about the most recent data, we assign a larger weight to the "latest time intervals" and a smaller weight to the more distant past time points. Or, we could treat all time points equally.
-
Weighted Inner Product
We define the "inner product" between two functions and as follows:
The inner product itself is not a distance. To measure the difference between and , calculate ; the measure gives more weight to errors at the times it emphasizes.
Similar to the length of a vector in two-dimensional space, which is , in function space, we use the inner product to define the "length" or "norm" of a function:
If the value of function is large, the norm will be large; if is close to 0, the norm will be small.
Finally, we try to approximate a simpler function to approach (representing the historical data from 0 to ), and then, within this metric structure, we can calculate the difference between the two:
This integral squares the difference where the measure has weight and then integrates it. If is supported only on , later times are not included. The term tells us:
- If it is small for most of the time points, the integral result will be small, indicating that and are very close.
- If it is large for many time points, the integral result will be large, indicating that and differ greatly.
HiPPO Framework
By this point, we have defined the "memory" problem as an "online function approximation problem," where, at any given time , we approximate the accumulated history of the input function over the interval using an -dimensional subspace (usually spanned by polynomials).
To achieve this goal, the next task is to solve the following problem:
As new data keeps arriving, how do we update the approximation coefficients online, so that the polynomial stays close to ?
Orthogonal Polynomials and Coefficient Projection
-
Choosing an appropriate basis :
To ensure good mathematical properties, we choose normalized orthogonal polynomials for the measure as the basis for . Their orthonormality gives the optimal approximation coefficients directly as inner products and makes the updates more concise.
-
Solving for the "best approximation projection":
If is the best polynomial approximation to , then it can be written as:
where is the best approximation coefficient at time . By definition, can be obtained through the inner product:
Due to orthogonality, obtaining becomes a straightforward and feasible task.
Transforming into a Differential Equation
The key problem now is:
How do we update as time progresses?
Since and the measure change over time, we consider taking the derivative of with respect to .
After detailed mathematical derivation, we find:
where is an matrix, and is an vector, both determined by the measure and the properties of the orthogonal polynomials.
This means that the "evolution of the best approximation coefficients over time" can be described by an ordinary differential equation (ODE).
Theoretically, by solving this ODE, we can update online.
However, in practice, we cannot solve the ODE exactly in continuous time, but we can discretize it (using methods like Euler's method or other numerical techniques) to convert it into a linear recurrence form.
Thus, each time a new value arrives, we can update
similar to an RNN. The barred coefficients come from discretization; a generic matrix-vector update takes time per step, with lower costs possible for specific structures.
HiPPO Abstraction
In the previous sections, we have defined the "memory representation" problem as a "function approximation problem":
- At any given time , we wish to represent the entire historical signal in a finite-dimensional way, ensuring that this approximation is optimal under a selected metric.
The author introduces several key operators here:
-
Projection Operator :
- Input: The historical function segment , which is the portion of the function over the time interval .
- Output: A polynomial , where is an -dimensional polynomial subspace.
This is the polynomial that best approximates under the metric.
In simple terms, finds the "best polynomial approximation" to represent over the interval .
-
Coefficient Extraction Operator :
- Input: A polynomial .
- Output: A vector , which is the coefficient vector of the polynomial in terms of an orthogonal polynomial basis.
Since is an element in an -dimensional subspace, we can uniquely express as
where the are the orthogonal basis functions (determined by the measure ).
By combining these two operators, we have , which maps the original function directly to its best polynomial approximation coefficient vector :
Thus, we only need to maintain to dynamically update and obtain a bounded-dimensional representation of historical memory.
While the definition is simple, directly computing is not easy.
The author derives the update rule for from theory, which can be described by an ODE:
where and are matrices and vectors determined by the measure and the choice of the basis.
Finally, the author includes a cute hippopotamus and a chart to illustrate the process:
The process of simplifying the approximate function is broken down into four steps:
-
Arbitrary Function : The upper left shows a function curve , defined for . This represents the time-varying signal input.
-
For each time , compute the best projection :
The second box in the diagram shows that at any time , we want to find a polynomial to approximate .
In the diagram, is drawn as a function curve approximating , but only considering the current time range , and determining the best approximation according to the inner product space defined by the selected measure .
-
Coefficient Representation and Dynamics (ODE):
The third box shows that is written as a linear combination of orthogonal polynomial bases, yielding the coefficient vector .
At this point, the author's theoretical result shows that will follow a set of linear differential equations (ODE):
This simplifies the problem into a computable dynamic system.
We no longer need to repeatedly minimize an error function, but instead update over time.
-
Discretization and Online Update:
Finally, since the actual data is a discrete sequence (e.g., ), we discretize the ODE, leading to the state shown in the far-right diagram:
This is a simple recurrence relation, similar to a special "RNN-like" structure. Given the previous time step's state and the current input , we can update the state .
HiPPO Application Examples
To help us better understand how HiPPO can be applied in practice, the author provides two common "memory types" as examples: Sliding Window (LegT) Measure and Exponential Decay (LagT) Measure.
-
1. Sliding Window (LegT) Measure
The sliding window is an intuitive memory mechanism, commonly used in scenarios such as monitoring real-time video streams in a control room.
We are generally only concerned with events that occurred in the last few seconds, and older frames are no longer important. Therefore, we set a "window length" , storing only the most recent seconds of video and constantly discarding older fragments. This is like sliding a fixed-length window along the timeline, only looking at the "latest" history inside this window.
Mathematically, this idea of "uniform weighting over the interval [ ]" can be expressed using a measure:
where is the indicator function, indicating that only time points within the interval are considered.
For this measure, the HiPPO projection yields the time-invariant linear ODE used by LMU, with the signal leaving the left edge of the sliding window approximated from the current coefficients:
where and have a clear closed-form solution. This update rule is the one used by the Legendre Memory Unit (LMU).
LMU was originally motivated as a memory mechanism for spiking neural networks. HiPPO derives its update from sliding-window projection and clarifies the approximation required at the window's departing boundary. The finite-state update is not an exact sliding projection for every possible signal.
-
2. Exponential Decay (LagT) Measure
Another common scenario is when we want to consider the infinite past history, but the more distant information becomes less important.
Mathematically, this can be modeled by applying exponential decay to the weights of the history:
which gives the most weight to recent time points, and gradually less weight to older ones, but never completely disappearing.
Similarly, using HiPPO, we can derive the corresponding ODE and linear recurrence update rules for this measure:
This set of formulas describes a "long-term memory" that "gradually fades," which is very useful for many practical applications, such as finance, signal filtering, and weighted averaging.
The author uses these two examples to demonstrate the versatility of the HiPPO framework. By simply changing the measure, we can generate different memory update rules with varying characteristics.
Sliding windows and exponential decay are just two typical examples of measures. Through the same derivation process, we can generate corresponding formulas for other special measures (such as Fourier or Chebyshev) or specific task requirements.
HiPPO Discretization
In the original definition, HiPPO starts with continuous time and describes the evolution of the memory state over time through a set of ODEs. However, in practice, we often deal with discrete sequential data, such as daily stock prices, temperature readings every second, or image signals at each time step.
Therefore, we need to discretize the continuous-time ODE, which means dividing time into small steps and converting the continuous evolution equation into a discrete update formula, making it applicable to real sequential data.
In continuous time, we have
where is the input function, is the state vector, and describes how the state is updated.
By dividing time into small steps , at each time point (where is an integer), we update the state. Forward Euler below illustrates the idea; the paper's experiments use more stable bilinear or zero-order-hold discretization.
The basic Forward Euler discretization is:
If we have a sequence of inputs , we can assume that , and then use the above formula to update step by step.
With this discretization step, we can compute it in a "single loop" on a computer:
- Starting from the initial state ,
- Each time a new data point arrives, we update .
This results in a discrete-time recurrence relation, eliminating the need to deal with continuous differential equations.
If observations are irregular or missing, the difference between successive timestamps can set each , followed by the chosen discretization update. This accounts for elapsed time but cannot automatically recover an unobserved value; the input between observations still needs an interpretation.
HiPPO Low-Degree Projection
HiPPO approximates historical memory with polynomials. is the coefficient dimension, so the highest polynomial degree is . A larger supplies more basis functions for complex histories.
But what happens if , meaning that we use only a constant, degree-zero basis?
Taking HiPPO-LagT (the exponential decay example) as an example, when , the corresponding ODE becomes very simple, with , and upon discretization, we get:
This formula can be interpreted as:
- When , acts like the proportion of old memory retained.
- Under the same condition, acts like the proportion of new information injected.
If we additionally make the input depend on the state and allow to adapt to the input and state, we find that:
- Hey! This update rule is exactly the familiar Gated RNN!
This lowest-order projection plus those input and step-size designs produces a gated-RNN-style update. A GRU still needs parallel units and its particular update functions; it is not merely the equation by itself.
It turns out that Gated RNNs can also be derived from the "function approximation" perspective, rather than being solely an empirically designed architecture.
Timescale Robustness of HiPPO
In the previous sections, we learned that HiPPO determines the characteristics of the memory mechanism by selecting an appropriate measure. The measures we explored earlier, such as Sliding Window (LegT) or Exponential Decay (LagT), rely on certain hyperparameters to represent time range or time intervals (for example, the window size in LegT or in LagT when discretized).
However, in practice, we often cannot determine the optimal timescale in advance, and fixed timescales may not be applicable when the data distribution changes over time.
To address this issue, the author introduces a new measure in this section:
- Scaled Legendre (LegS)
This measure aims to establish a memory mechanism that is robust to timescales, without requiring specific time hyperparameters.
Definition of the LegS Measure
This measure assigns uniform weights to the entire historical interval , unlike the sliding window, which only focuses on the recent -length time interval, or exponential decay, which heavily weights the recent history and exponentially reduces the weight of distant history.
LegS essentially dynamically expands the "window" over time, always including all history from to .
Based on the author's proofs, HiPPO-LegS has dynamic equations for both continuous and discrete time:
-
Continuous-time differential equation:
-
Discrete-time recurrence relation:
Here, and , with specific structures for and as follows:
Here is the identity matrix. The discrete example is valid only for ; initialization must handle the singularity at rather than divide by zero. These formulas avoid a fixed window-length hyperparameter, though state size and discretization still need choices.
Theoretical Properties and Advantages
The LegS (Scaled Legendre) measure proposed by HiPPO exhibits several advantages.
Its key feature is assigning uniform weights to the entire historical interval , which leads to "timescale robustness," "computational efficiency," "stable gradient flow," and "controlled approximation error."
-
Timescale Robustness
Since LegS does not rely on fixed time window sizes or step-size parameters, it naturally adapts to time stretching or compression. The author provides the following mathematical expression:
For any , define , then
In other words, for any time scaling function , we have:
This means constant compression or stretching of the input time axis produces the same coefficient trajectory at a rescaled time. The coefficient values are not multiplied by , and this statement does not cover arbitrary time warping.
In contrast, other measures (such as LegT or LagT) require additional window lengths or step sizes as hyperparameters, which are easily affected by changes in timescale and must be carefully adjusted in practice.
-
Computational Efficiency
After discretizing the continuous ODE, we face the issue of performing matrix-vector multiplications at each time step. Typically, this requires computations.
However, for LegS, through a specific generalized bilinear transformation discretization method, each update step can be computed in time:
For the HiPPO-LegS discrete recurrence update
under appropriate discretization conditions, each calculation can be completed in time.
Due to the structure of , the generalized bilinear discretizations analyzed in the paper permit memory updates. The measured speed table below concerns the memory updater on one CPU core; it does not show a tenfold acceleration for an entire RNN or for every choice of .
-
Gradient Flow
RNNs often suffer from the "vanishing gradient" problem, which makes it difficult to capture long-term dependencies. For LegS, the author provides an analysis of the gradient flow, showing that it avoids exponential gradient decay:
For any ,
The analyzed continuous memory path decays like rather than exponentially. The gradient still decreases.
-
Approximation Error Bounds
Finally, the author discusses the theoretical accuracy of LegS in function approximation.
If is L-Lipschitz, then
and if has -th bounded derivatives, then
Under the stated smoothness and derivative bounds, increasing the coefficient dimension lowers these error bounds. A fixed-dimensional state cannot exactly reconstruct every signal.
Discussion
In the experiments, the author used different HiPPO methods, including the previously introduced LegT, LagT, and LegS.
-
LegT: Requires a hyperparameter to represent the sliding window length.
If the timescale of the data is known and set to an ideal value, LegT performs well. However, if is not suitable (too large or too small), performance will significantly degrade.
-
LagT: Requires setting a step size hyperparameter , and its performance also depends on this choice.
-
LegS: Does not require such time-scale parameters and is theoretically more robust to different timescales.
In addition, the author designed a control group Rand, where random and matrices (properly normalized) are used in the update rule. By comparing Rand with other rigorously derived HiPPO dynamics, the importance of "specific dynamic design" is confirmed, as opposed to the effect of purely random matrices.
The HiPPO methods were also combined with MGU (Minimal Gated Unit, a simplified GRU) as the basic architecture. Additionally, various RNN variants designed for long-term dependencies, such as LSTM, GRU, expRNN, and LMU, were also compared.
The compared methods use the same hidden-state dimension; HiPPO variants additionally set memory dimension . This makes their scales roughly comparable.
Long-Term Memory Benchmark Task
The pMNIST task involves shuffling the pixel order of MNIST handwritten digits and then inputting the model pixel by pixel. Since the spatial adjacency of pixels is shuffled, the model must use long-term memory to retain and integrate information from the entire image for classification, making this task a true test of long-term dependency capability.
The left side of the table reports validation accuracy averaged over three random seeds; the right side lists test accuracy reported by this paper and earlier studies.
- HiPPO-LegS reaches the highest validation accuracy in the left-side comparison, 98.34%; its reported test accuracy on the right is 98.3%.
- LegT performed well when the window length was set to the ideal value but suffered a significant performance drop when was set incorrectly.
- LagT also performed well with an appropriate .
LMU had been the state-of-the-art (SOTA) for this task in RNN-based models, but LegS surpassed LMU and other sequence models, achieving a test accuracy of 98.3% on pMNIST, setting the "strict sequence model" true SOTA.
Timescale Robustness
Sequence models generally benefit from appropriate timescale priors, but these priors are often presented as additional hyperparameters and are not automatic solutions. For example:
- In LSTM, the "forget bias" parameter requires adjustment to handle long-term dependency issues.
- HiPPO-LagT and HiPPO-LegT require choosing an appropriate step size or window length during discretization.
In the previous section, ablation experiments were conducted, showing that if a sliding window mechanism like LegT does not have the correct , its performance drastically drops.
In the paper, the author used the Character Trajectories dataset as an experimental target.
The task of this dataset is to classify characters drawn by handwriting strokes (coordinates collected at a fixed sampling rate). To simulate "timescale shifts," the author considered two standard time series generation processes:
-
Sampling Rate Change: The training model's sampling rate is different from the testing sampling rate, resulting in different timescales between training and testing. Since the sequence length can vary, the model cannot directly infer the change in sampling rate from the sequence length.
-
Irregular Sampling or Missing Data: In this case, the time stamps of the sequence are not at fixed intervals. A simple transformation is performed: the time stamps in the testing phase are scaled. If the model can naturally handle multiple timescales, it will automatically adapt to the time expansion or compression of the test data.
HiPPO treats input data as continuous functions and processes observed samples through discretization. Supplying the elapsed time and an input interpretation between observations lets its update handle irregular sampling; missing values are not reconstructed automatically. Together with LegS's timescale equivariance, this motivates testing whether it adapts under those settings.
In this experiment, the author compared HiPPO-LegS with other models designed for irregular sampling and missing data, including:
- GRU-D: Models the time intervals between observations using a decay mechanism.
- Neural ODE Models: Use ODEs to simulate state evolution between observation points, naturally handling irregular sampling.
The results are shown in the table below:
Without the timescale shift, all listed models exceed 95% accuracy. Under the tested shifts, several baselines fall sharply.
HiPPO-LegS scores 88.8%–94.9% across the four shifted test settings in this table, above each corresponding baseline. That supports greater robustness in these particular evaluations; the shifts do still lower its accuracy.
Scalability Verification
In this function-reconstruction experiment, the paper reports about 0.25 error for LSTM even at sequence length 1,000. This is not a universal upper limit on the sequence lengths LSTMs can process.
To test very long sequences, the authors sample a continuous-time, band-limited white-noise process and reconstruct a sequence of length , allowing each method up to 256 memory units.
After one million steps, LMU and HiPPO-LegS obtain reconstruction MSEs of 0.05 and 0.02, respectively, below the LSTM result of 0.25. This is lossy reconstruction, not exact recovery of every input value.
The next figure shows HiPPO-LegS tracking the input curve more closely in this setting, with larger LSTM reconstruction deviations:
The authors also measure the memory updater's practical speed, in addition to its per-step complexity under the analyzed discretization:
With a C++ updater and PyTorch bindings on one CPU core, HiPPO-LegS processes 470,000 elements per second in this function-reconstruction benchmark; the LSTM and LMU updater rows show 35,000 and 41,000. These are memory-update throughput measurements, not speed for full classification models.
Conclusion
The HiPPO framework treats memory representation as an ongoing optimal function approximation problem over time, and by introducing a measure of time variation, it unifies and explains existing memory mechanisms.
HiPPO-LegS, as an instance of the HiPPO framework, not only theorizes towards "timescale robustness," but also practically demonstrates its effectiveness in handling long-term dependency problems with sequences up to millions of time steps and with high computational efficiency.