PaperlayerView exact revision on arXiv

Source-linked AI summary

HiPPO: Recurrent Memory with Optimal Polynomial Projections

Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, Christopher Re

arXiv:2008.07669v2cs.LGstat.ML

TL;DR

Sequential models must compress cumulative history online despite bounded storage and limited memory horizons. HiPPO formulates this as optimal polynomial projection, yielding HiPPO-LegS, whose recurrent integration achieves strong long-range performance and timescale robustness.

  • Problem

    Sequential learning requires representing cumulative history with bounded, online-updated storage, while existing recurrent methods have limited memory horizons and often require timescale priors.

  • Method

    HiPPO compresses cumulative histories by projecting them onto bounded-dimensional polynomial bases under time-varying measures, producing memory updates including the full-history HiPPO-LegS mechanism.

  • Results

    HiPPO-LegS achieves 98.3% accuracy on permuted MNIST and outperforms RNN and neural ODE baselines on trajectory classification with unseen timescales and missing data.

  • Takeaways & Limitations

    HiPPO-LegS provides a memory mechanism designed for timescale robustness, efficient long-range dependencies, and handling missing or irregularly sampled data.

  • Takeaways & Limitations

    Sequence models can depend on timescale hyperparameters, such as LSTM forget bias or discretization step size, and sliding-window methods may require correctly setting the window length.

Abstract

from arXiv · show

A central problem in learning from sequential data is representing cumulative history in an incremental fashion as more data is processed. We introduce a general framework (HiPPO) for the online compression of continuous signals and discrete time series by projection onto polynomial bases. Given a measure that specifies the importance of each time step in the past, HiPPO produces an optimal solution to a natural online function approximation problem. As special cases, our framework yields a short derivation of the recent Legendre Memory Unit (LMU) from first principles, and generalizes the ubiquitous gating mechanism of recurrent neural networks such as GRUs. This formal framework yields a new memory update mechanism (HiPPO-LegS) that scales through time to remember all history, avoiding priors on the timescale. HiPPO-LegS enjoys the theoretical benefits of timescale robustness, fast updates, and bounded gradients. By incorporating the memory dynamics into recurrent neural networks, HiPPO RNNs can empirically capture complex temporal dependencies. On the benchmark permuted MNIST dataset, HiPPO-LegS sets a new state-of-the-art accuracy of 98.3%. Finally, on a novel trajectory classification task testing robustness to out-of-distribution timescales and missing data, HiPPO-LegS outperforms RNN and neural ODE baselines by 25-40% accuracy.

1 Introduction

HiPPO frames recurrent memory as online compression of cumulative history through optimal polynomial projections, unifying prior mechanisms and introducing a timescale-robust update. Integrated into RNNs, HiPPO-LegS achieves strong benchmark and robustness results.

  • Motivation and framework: HiPPO represents cumulative history with bounded storage by solving an online function-approximation problem using polynomial-basis coefficients.The approximation weights past time steps through a measure, enabling incremental updates as data arrives.
  • Unification: HiPPO unifies recurrent memory methods, exactly recovers LMU updates, and interprets LSTM and GRU gating as a low-order approximation case.The framework derives these mechanisms from a common formal optimization problem.
  • HiPPO-LegS: HiPPO-LegS uses a scaled measure that incorporates the full history, avoiding priors on sequence length or timescale.Its theoretical benefits include input-timescale invariance, efficient updates, and bounds on gradient flow and approximation error.
  • Empirical evaluation: 98.3% accuracy on permuted MNIST establishes a new state of the art for hyperparameter-free HiPPO-LegS.The method beats the previous RNN state of the art by over 1 point and outperforms models with global context such as transformers.

2 The HiPPO Framework: High-order Polynomial Projection Operators

HiPPO defines memory as maintaining an optimal polynomial projection of a function’s history under a time-varying measure. Differentiating the projection yields tractable continuous dynamics and discrete recurrences, recovering existing and new memory mechanisms.

  • Problem setup: HiPPO compresses cumulative history by projecting it onto a bounded-dimensional polynomial subspace and retaining its basis coefficients online.The subspace dimension N determines the compression size and approximation order.
  • Problem setup: A time-varying measure µ(t) determines the importance assigned to each part of the history, while orthogonal polynomials provide the natural basis.The projection minimizes the L2(µ(t)) approximation error at every time.
  • General framework: Differentiating projection coefficients produces an ODE d/dtc(t) = A(t)c(t) + B(t)f(t), which can be solved online or discretized into an N-dimensional recurrence.This converts an intractable naive projection into an incremental update driven by the current input.
  • Measure families: LegT and LagT instantiate HiPPO with sliding-window and exponentially decaying measures, respectively, and yield linear time-invariant ODEs.LegT summarizes a recent fixed-length window, whereas LagT emphasizes recent history exponentially.
  • Measure families: The framework derives the LMU update and exposes its limitation: the sliding-window rule requires the unavailable value f(t − θ), which must be reconstructed from current coefficients.This introduces an additional approximation beyond the projection itself.
  • Discretization: Standard discretization converts continuous-time HiPPO ODEs into practical discrete-time linear recurrences for sequences and time series.The resulting updates operate on discrete inputs while preserving the online compression formulation.

3 HiPPO-LegS: Scaled Measures for Timescale Robustness

HiPPO-LegS scales a uniform measure across all history, replacing fixed timescale choices with a timescale-equivariant memory update. The resulting recurrence has favorable theoretical efficiency, gradient, and approximation properties.

  • Scaled measure: HiPPO-LegS assigns uniform weight to the complete history [0, t], rather than using a fixed sliding window.This adaptive window is designed to avoid forgetting as time grows.
  • Theoretical properties: The paper establishes bounded gradients and approximation error for HiPPO-LegS, with approximation error decreasing as input smoothness increases.These properties complement its timescale invariance and fast computation.
  • Timescale robustness: HiPPO-LegS is timescale-equivariant: dilating the input f by α scales the output coefficients in the same way.Formally, for h(t) = f(αt), hippo(h)(t) = hippo(f)(αt).
  • Timescale robustness: HiPPO-LegS has no timescale hyperparameters, and its discrete recurrence is invariant to the discretization step size.LegT instead uses a window-size parameter θ, while LegT and LagT use a discrete step-size parameter ∆t.
  • Computational efficiency: Each generalized-bilinear-transform step of the HiPPO-LegS recurrence can be computed in O(N) operations.The special structure of its fixed matrix A enables fast multiplication beyond the generic O(N^2) cost.
  • Computational efficiency: Unrolling discretized HiPPO layers is 10x faster than standard matrix multiplication used in standard RNNs.This practical result validates the computational-efficiency analysis in experiments.

4 Empirical Validation

HiPPO memory mechanisms are integrated into recurrent architectures and evaluated on long-range dependency, timescale-shift, function-reconstruction, and efficiency tasks. HiPPO-LegS generally outperforms recurrent baselines while providing robust and efficient long-range memory.

  • Model Architectures: HiPPO memory updates replace an RNN’s previous hidden state with a projection of the entire feature history.The architecture can use a basic gated RNN update, with HiPPO inserted as an intermediate memory layer.
  • Long-range Memory Benchmark Tasks: 98.3% test accuracy makes HiPPO-LegS state of the art on permuted MNIST.The result exceeds previous recurrent-model performance and also surpasses models with global receptive fields.
  • Long-range Memory Benchmark Tasks: LegS solves the copying task almost perfectly, whereas LegT is highly sensitive to its window-length hyperparameter and most baselines make little progress.The task uses sequences with length L = 200 and directly tests memorization.
  • Timescale Robustness of HiPPO-LegS: HiPPO-LegS generalizes to unseen timescales, while other methods fail under timescale distribution shift despite achieving at least 95% accuracy without that shift.Its continuous-function formulation also supports missing or irregularly sampled data through the discretization step sizes.
  • Theoretical Validation and Scalability: HiPPO-LegS reconstructs functions accurately across 1 million time steps and processes 470,000 updates per second on one CPU core.The update is reported as 10x faster than LSTM and LMU, while both LMU and LegS accurately reconstruct the long input function.
  • Additional Experiments: HiPPO-based RNNs match LSTM performance on IMDB sentiment classification and reduce normalized MSE by 30% on Mackey spin glass prediction.The latter result compares HiPPO-LegS with LSTM, LMU, and a hybrid LSTM+LMU model.

5 Conclusion

HiPPO frames online memory as optimal function approximation under time-varying measures, unifying prior memory mechanisms and introducing scaled measures for growing history. Its scaled Legendre method provides timescale-robust theoretical and empirical properties.

  • 5 Conclusion: HiPPO compresses cumulative signal history by projecting it onto a bounded-dimensional subspace using time-varying measures.The framework supports continuous and discrete signals and permits approximation quality to vary across past time steps.
  • 5 Conclusion: HiPPO-LegS is designed to handle dependencies across millions of time steps without requiring a fixed sequence-length prior.The paper identifies timescale robustness, efficient updates, bounded gradient flow, and approximation-error bounds as theoretical benefits.
  • 5 Conclusion: The framework differs from fixed-length sliding transforms by allowing scaled measures whose window size increases over time.This scaled setting produces qualitatively different theoretical and empirical properties and was not addressed by the cited prior works.
  • 5 Conclusion: HiPPO provides a unified account of recurrent memory methods, including the LMU, gating mechanisms, and orthogonal-polynomial approaches.Its measure-based formulation also distinguishes the method from standard discrete transforms and derives dynamics from an underlying continuous-time problem.
  • 5 Conclusion: The paper positions online processing and memorization as a foundational problem relevant to sequence models across language, reinforcement learning, and continual learning.Attention and dilated convolutions are described as finite-window approaches that avoid explicit memory representation.

A.3 Directly related methods

The paper relates HiPPO to recurrent memory units, orthogonal-polynomial transforms, and dynamical-system approaches. It emphasizes that HiPPO derives memory updates from time-domain online approximation rather than importing a fixed transform or frequency-domain construction.

  • A.3 Directly related methods: The LMU is recovered as a direct HiPPO instantiation using the LegT measure, while HiPPO gives a principled projection-based derivation.The paper contrasts this time-domain optimization view with the LMU’s neurobiological and frequency-domain motivation.
  • A.3 Directly related methods: Unlike standard sliding transforms, HiPPO derives continuous-time dynamics for online approximation before discretizing them.The paper presents this time-domain derivation as a distinct interpretation from discrete transforms and frequency-space approaches.
  • A.3 Directly related methods: HiPPO is a model-independent projection operator that can be integrated into RNNs or used as a layer in other model types.This distinguishes the operator from the complete LMU recurrent architecture.
  • A.3 Directly related methods: HiPPO-LegS strengthens timescale robustness beyond sliding-window methods by using scaling and retaining bounded gradients without a specified timescale hyperparameter.The paper contrasts this with FRU’s bounded-gradient condition, which depends on choosing a timescale appropriately when the horizon is known.
  • A.3 Directly related methods: Orthogonal polynomials provide the approximation bases used across the framework, including Legendre, Laguerre, Hermite, Chebyshev, and related families.Their orthogonality makes optimal polynomial approximation coefficients available through projection.

B.3 ODE Discretization

This section describes how continuous-time HiPPO dynamics are discretized into sequence updates. It compares endpoint-based numerical schemes and highlights a discretization for HiPPO-LegS that is invariant to the step size.

  • B.3 ODE Discretization: ODE discretization converts continuous-time HiPPO dynamics into updates for sequence data by approximating the right-hand-side integral.The framework discusses Euler, backward Euler, bilinear, generalized bilinear, and zero-order-hold methods.
  • B.3 ODE Discretization: Forward Euler uses the left endpoint, backward Euler uses the right endpoint, and bilinear averages the two endpoints.Generalized bilinear transformation extends these choices through a weighted endpoint average parameterized by α.
  • B.3 ODE Discretization: HiPPO-LegS has a discretized system whose recurrence is invariant to the discretization step size Δt.The resulting recurrence does not depend on Δt.
  • B.3 ODE Discretization: Bilinear provides a more accurate approximation than forward or backward Euler for the HiPPO-LegS function-approximation experiment.The experiments therefore use bilinear discretization for LegS updates.
  • B.3 ODE Discretization: Each HiPPO-LegS recurrence step can be computed in O(N) operations under generalized bilinear discretization.The framework defines coefficient dynamics through linear ODEs whose matrices depend on the chosen measure and basis.

D Derivations of HiPPO Projection Operators

HiPPO derives fast memory updates by projecting histories onto orthogonal-polynomial bases under time-varying measures. The framework recovers LMU and Fourier Recurrent Unit updates while introducing measure choices such as LegS.

  • General derivation: HiPPO derives translated Legendre, translated Laguerre, and scaled Legendre memory updates from a shared projection framework.The derivations follow a common sequence: choose a measure and basis, differentiate them, derive coefficient dynamics, and reconstruct the approximation.
  • Scaled Legendre: The scaled Legendre measure uniformly weights the entire history [0, t], producing dynamics dilated by the time-varying factor t−1.Unlike fixed-width measures, it uses a varying-width support.
  • General derivation: Orthogonal-polynomial coefficients provide an incrementally updated representation of the optimal projection under the selected measure and basis.The framework expresses coefficient dynamics as a closed-form ODE or linear recurrence.
  • Translated Legendre: The translated Legendre measure uses a fixed sliding window of length θ, and its update exactly recovers the LMU equation.Because the window requires f(t−θ), reconstruction supplies an approximation when that input is no longer available.
  • Translated Laguerre: The translated Laguerre construction uses generalized Laguerre polynomials and an exponentially weighted history, with the basic result corresponding to α = 0 and β = 1.The derivation flips and translates the Laguerre weight from [0, ∞) to (−∞, t].
  • Other bases: HiPPO also derives the Fourier Recurrent Unit using a sliding Fourier measure and analyzes additional Fourier- and Chebyshev-based constructions.The Fourier basis is treated as an orthogonal-polynomial basis after a change of variables.

E.4 Function Approximation Error

The approximation error analysis bounds the discarded high-order Legendre coefficients using smoothness assumptions on the input function. The resulting decay connects HiPPO error to classical Fourier approximation results.

  • Error decomposition: HiPPO approximation error is controlled by the squared sum of high-order Legendre coefficients beyond approximation order N.Parseval’s identity reduces the projection-error bound to bounding coefficients with indices n ≥ N.
  • Smoothness bounds: For an L-Lipschitz input, integration by parts provides coefficient bounds that yield an explicit truncation-error estimate.The proof uses the derivative bound |f′| ≤ L and vanishing boundary terms.
  • Smoothness bounds: For inputs with k bounded derivatives, repeated integration by parts gives a tail bound scaling as O(1)t^2k N^(−2k+1).The derivative smoothness assumption determines how rapidly the Legendre coefficients decay.
  • Interpretation: The Legendre coefficient-decay result is analogous to the Fourier result that order-k bounded derivatives imply n-th coefficients decay as O(n^−k).Both bounds are proved through integration by parts.

F.1 Model Architecture Details

HiPPO RNNs replace the usual recurrent hidden-state history with a projected HiPPO memory, then apply a gated recurrent update. The memory dynamics use fixed measure-dependent matrices.

  • Architecture: HiPPO memorizes feature histories through discretized linear recurrent dynamics and integrates those dynamics into RNN models.The continuous operator consumes an input function and produces coefficient functions that are discretized into recurrent updates.
  • Architecture: The model replaces the previous hidden state with a projected representation of its entire history before applying the RNN update function.The experiments use a basic gated update with sigmoid gating and a tanh-transformed parametrized linear function.
  • Variants: HiPPO-LegT, LagT, and LegS instantiate the architecture with translated Legendre, tilted Laguerre, and scaled Legendre measures.LegT requires a timescale parameter θ, whereas LegS is hyperparameter-free with respect to sequence length.
  • Variants: HiPPO-Rand tests whether the architecture alone suffices by replacing framework-derived dynamics with a random linear time-invariant system.The paper contrasts this baseline with dynamics derived from the HiPPO framework.
  • Architecture: The HiPPO memory operator orthogonalizes feature histories, while fixed matrices A_t and B_t depend on the selected measure.N and d denote approximation order and hidden-state size.

F.2 Permuted MNIST

The experiments evaluate HiPPO on long-range pixel classification and memory tasks, with particular attention to timescale hyperparameters. HiPPO variants are competitive on permuted MNIST, while LegS is robust on long-copying settings.

  • Permuted MNIST: Permuted MNIST applies a fixed pixel permutation to a 784-step image sequence, increasing the demand for long-term dependency modeling.The task uses 60,000 training examples and 10,000 test examples with a held-out validation split.
  • Permuted MNIST: All HiPPO variants achieve state-of-the-art performance among previous recurrent sequence models on permuted MNIST.The comparison includes HiPPO-LegT, HiPPO-LagT, HiPPO-LegS, and a reproduced LMU.
  • Timescale ablations: Timescale hyperparameters substantially affect LegT and LagT performance, while LegT’s θ should match the data timescale for best behavior.The ablations vary discretization step size for LagT and θ for LegT.
  • Copying: HiPPO-LegS solves the Copying task fastest, whereas LegT slows drastically when θ is mis-specified as 20 or 2000 instead of 200.The Copying task requires reproducing ten initial digits after a long sequence of zeros.
  • Copying: The HiPPO-Rand baseline performs much worse than framework-derived updates, while standard RNN and LSTM models remain nearly at baseline.This comparison emphasizes the role of the precise derived dynamics rather than only the surrounding architecture.

F.5 Online Function Approximation and Speed Benchmark

This section evaluates HiPPO-LegS, LMU, and LSTM for reconstructing long discrete signals and compares their inference speed.

  • The reconstruction task uses a length-10^6 discrete sequence sampled at Δt = 10^-4 from a band-limited white-noise process.The input signal has a 1Hz band limit.
  • HiPPO-LegS and LMU perform memory updates without additional RNN architecture, while LSTM uses trained linear decoding from hidden and cell states.All models use N = 256 hidden units; LSTM is trained on 100 sequences with L2 loss.
  • Inference speed is benchmarked for HiPPO-LegS, LMU, and LSTM in single-threaded mode on an Intel Xeon CPU.The benchmark uses an Intel Xeon E5-2690 v4 at 2.60GHz.
  • Table 6 is identified as an IMDB test-accuracy comparison averaged over three seeds, with separate rows for proposed methods and recurrent baselines.

F.6 Sentiment Classification on the IMDB Movie Review Dataset

This section evaluates HiPPO-based recurrent models on IMDB sentiment classification and reports performance comparable to or better than LSTM, while expRNN performs worse.

  • The IMDB dataset contains 25,000 train and test sequences ranging from hundreds to thousands of steps for binary sentiment classification.Ten percent of the standard training set is used for validation.
  • The recurrent baselines are LSTM, vanilla RNN, LMU, and expRNN, each implemented with 256 hidden units.
  • HiPPO-RNNs achieve similar and consistent performance, on par or better than LSTM, on the IMDB task.
  • Other long-range-memory recurrent approaches that constrain network expressivity, such as expRNN, perform worse on this more generic task.
  • The Mackey-Glass experiment models chaotic dynamical systems by predicting 15 future time steps with four-layer recurrent networks trained using mean squared error.The cited passage notes that a hybrid LSTM+LMU approach improved on either model alone, but was not combined with HiPPO-LegS.
  • HiPPO-LegS reduces normalized MSE by over 30% relative to LSTM, LMU, and the best hybrid LSTM+LMU model.

F.8 Additional Analysis and Ablations of HiPPO

The additional analyses compare online function-approximation behavior across HiPPO variants, emphasizing LegS’s lower error and LegT’s sensitivity to its window-length hyperparameter.

  • Function approximation: LegS has the lowest absolute approximation error among LegT, LagT, and LegS on the test function.LegT and LagT have similar, slightly higher errors than LegS.
  • LegT Window Length: A LegT window that is only 0.5% too small relative to the total sequence length causes huge approximation errors.The passage attributes this to the final measure not being supported everywhere, leaving inaccuracies near x = 0 unconstrained by the projection problem.
  • Generalized LagT Family: LagT is governed by parameters α and β, with small α generally performing better and larger β producing unstable reconstruction.Small β values work well, while a fuller theoretical explanation of these tradeoffs remains open.
  • LegS vs. LegT: LegS requires no timescale hyperparameters, whereas LegT uses a sliding window whose update includes an additional approximation term for f(t − θ).When θ = T, both methods use the same final measure and specify the same function at time T.
Loading 2008.07669v2…