State-space models (SSMs) and Gaussian Processes (GPs) are highly effective for processing sequential data. By framing temporal evolution as a Markov chain, algorithms like the Kalman filter achieve a computational complexity that scales linearly ($O(T)$) with the number of time steps.
However, this linear temporal scaling hides a severe bottleneck: the computational cost scales cubically ($O(d^3)$) with the dimensionality $d$ of the latent state space. When the state dimension grows—whether representing pixels in a video, nodes in a massive traffic network, or spatial compartments in a biological simulation—this cubic scaling quickly renders exact probabilistic inference intractable.
Why the Math Demands Cubic Time
To understand why this bottleneck occurs, we must look at how uncertainty propagates through a dynamical system. To capture the full dependencies between $d$ distinct state variables, a model must maintain a $d \times d$ covariance matrix $\Sigma$.
Standard State-Space Inference:
State Vector (d) ──► Covariance Matrix (d x d) ──► Matrix Inversion/Multiplication ──► O(d³) Cost
When a new observation arrives, or when we compute a second-order optimization step, we must evaluate how information flows across all dimensions. This requires solving a linear system or inverting a matrix of size $d \times d$. As noted by Hamidreza Hashempoor et al. in Gated Inference Network: Inference and Learning State-Space Models, traditional Bayesian inference requires matrix inversions that scale cubically with the size of the state space.
If $d$ represents a few tracking coordinates, an $O(d^3)$ cost is trivial. But the bottleneck becomes prohibitive in large-scale applications:
- Spatio-temporal Networks: Tracking city-wide traffic networks or massive neural populations requires operations that scale cubically with the number of nodes, preventing real-time tracking (Soumyasundar Pal et al. in RNN with Particle Flow for Probabilistic Spatio-temporal Forecasting).
- Biophysical Modeling: Reconstructing high-fidelity voltage signals across complex dendritic trees scales cubically with the number of spatial compartments (Ruoxi Sun et al. in Scalable Bayesian inference of dendritic voltage via spatiotemporal recurrent state space models).
Where the Bottleneck Manifests
This cubic scaling constraint appears across several distinct domains within machine learning and numerical analysis.
Probabilistic Differential Equation Solvers
Modern probabilistic numerics treat ordinary differential equations (ODEs) and boundary value problems (BVPs) as state-space inference tasks to quantify numerical uncertainty. As Nicholas Krämer et al. demonstrate in Linear-Time Probabilistic Solution of Boundary Value Problems, the computational complexity of state-space inference is cubic with respect to both the system dimension and the solver order. This $O(d^3)$ time and $O(d^2)$ memory requirement limits their use to small-scale problems, preventing uncertainty-aware optimization in high-dimensional neural ODEs (Jonas Beck et al. in Diffusion Tempering Improves Parameter Estimation with Probabilistic Integrators for Ordinary Differential Equations).
State-Space Gaussian Processes
Converting a temporal Gaussian Process into a state-space representation successfully reduces temporal complexity to $O(T)$. However, as Hannes Nickisch et al. show in State Space Gaussian Processes with Non-Gaussian Likelihood, it introduces a cubic cost relative to the state dimension. This trade-off implies that the computational efficiency of these models is highly sensitive to the complexity of the chosen covariance functions; using complex or composite kernels necessitates larger state vectors, making the approach prohibitively expensive (William J. Wilkinson et al. in Unifying Probabilistic Models for Time-frequency Analysis).
Algorithmic Escape Hatches
To scale these models to millions of dimensions, researchers exploit structural properties of the dynamics, the priors, or the observations to bypass full matrix operations.
Exploiting Kronecker Structures
When a high-dimensional system can be factored into independent or grid-like components, the dense $d \times d$ covariance matrix can be structured as a Kronecker product ($A \otimes B$).
The key algebraic insight is that the inverse of a Kronecker product is the Kronecker product of the individual component inverses:
$$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}$$
If a state space of dimension $d = 1,000,000$ can be factored into two components of size $1,000$, inverting the full matrix directly requires $O((10^6)^3) = O(10^{18})$ operations. Inverting the Kronecker factors requires only $O(1000^3 + 1000^3) = O(10^9)$ operations.
Nicholas Krämer et al. leverage this property in Probabilistic ODE Solutions in Millions of Dimensions, achieving linear $O(d)$ scaling by combining independence assumptions with Kronecker structures in the prior models.
Low-Rank Updates
In many systems, even though the hidden state space is high-dimensional, the observations or updates at any given time step are sparse or low-dimensional. This means the change to the covariance matrix has a low rank.
Using the Woodbury matrix identity, the inverse of a matrix modified by a low-rank update can be computed by inverting a much smaller matrix:
$$(A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}$$
If $A$ is a diagonal or easily invertible matrix of size $d \times d$, and $U, V$ represent a low-rank update of rank $k$ (where $k \ll d$), the inversion cost depends on $O(k^3)$ rather than $O(d^3)$.
Eftychios A. Pnevmatikakis et al. exploit this in Fast interior-point inference in high-dimensional sparse, penalized state-space models to reduce the computational complexity of Newton's method from cubic to linear relative to the state dimension. Similarly, Matthew Dowling et al. introduce XFADS in eXponential FAmily Dynamical Systems (XFADS): Large-scale nonlinear Gaussian state-space modeling, utilizing low-rank structured posterior updates to achieve linear time complexity without sacrificing dense covariance structures.
Sample-Based and Ensemble Messages
Instead of explicitly tracking and updating a dense $d \times d$ covariance matrix, uncertainty can be represented implicitly using an ensemble of samples.
Dan MacKinlay et al. demonstrate this in Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional, Black-box Systems. By representing beliefs as samples and passing low-rank messages between nodes in a graphical model, they avoid the cubic scaling typical of exact belief propagation, enabling accurate posterior estimation in large-scale physical simulations like fluid dynamics and weather patterns.
Uniformization for Continuous-Time Chains
In continuous-time Markov jump processes, calculating exact transition probabilities traditionally requires computing a matrix exponential, which scales as $O(d^3)$ relative to the state space size.
Vinayak A. Rao et al. bypass this in Fast MCMC sampling for Markov jump processes and continuous time Bayesian networks via a technique called uniformization. This method transforms the continuous-time inference problem into a discrete-time Hidden Markov Model dominated by a sparse transition matrix, reducing the computational complexity from $O(d^3)$ to $O(d^2)$.
Key Foundational Work
Combining discriminative features to infer complex trajectories (2006) — contributed 1 concept elements to this direction.
Gaussian Processes in Reinforcement Learning (2003) — contributed 1 concept elements to this direction.