# Fast convolution algorithm for state space models

arXiv: https://arxiv.org/abs/2411.17729 · HTML: https://mlsanity.com/paper/2411.17729/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 22 Nov 2024.

## Builds on (most cited first, 6 of 6)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections](https://mlsanity.com/paper/2206.12037/) (2022)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Robustifying State-space Models for Long Sequences via Approximate Diagonalization](https://mlsanity.com/paper/2310.01698/) (2023)

## Built on by (most cited first, 1 of 1)

- [Block-Biased Mamba for Long-Range Sequence Processing](https://mlsanity.com/paper/2505.09022/) (2025)

## Abstract (arXiv)

We present an unconditionally stable algorithm for applying matrix transfer function of a linear time invariant system (LTI) in time domain. The state matrix of an LTI system used for modeling long range dependencies in state space models (SSMs) has eigenvalues close to 1. The standard recursion defining LTI system becomes unstable if the m× m state matrix has just one eigenvalue with absolute value even slightly greater than 1. This may occur when approximating a state matrix by a structured matrix to reduce the cost of matrix-vector multiplication from Oleft(m2right) to Oleft(mright) or Oleft(mlog mright). We introduce an unconditionally stable algorithm that uses an approximation of the rational transfer function in the z-domain by a matrix polynomial of degree 2N+1-1, where N is chosen to achieve any user-selected accuracy. Using a cascade implementation in time domain, applying such transfer function to compute L states requires no more than 2L matrix-vector multiplications (whereas the standard recursion requires L matrix-vector multiplications). However, using unconditionally stable algorithm, it is not necessary to assure that an approximate state matrix has all eigenvalues with absolute values strictly less than 1 i.e., within the desired accuracy, the absolute value of some eigenvalues may possibly exceed 1. Consequently, this algorithm allows one to use a wider variety of structured approximations to reduce the cost of matrix-vector multiplication and we briefly describe several of them to be used for this purpose.