# Constant-Time Predictive Distributions for Gaussian Processes

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2018.

## Built on by (most cited first, 30 of 48)

- [Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information](https://mlsanity.com/paper/2104.09460/) (2021)
- [Fast Adaptation with Linearized Neural Networks](https://mlsanity.com/paper/2103.01439/) (2021)
- [Bayesian Optimization with High-Dimensional Outputs](https://mlsanity.com/paper/2106.12997/) (2021)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Conditioning Sparse Variational Gaussian Processes for Online Decision-making](https://mlsanity.com/paper/2110.15172/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Kernel Interpolation for Scalable Online Gaussian Processes](https://mlsanity.com/paper/2103.01454/) (2021)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Trust Your Robots! Predictive Uncertainty Estimation of Neural Networks with Sparse Gaussian Processes](https://mlsanity.com/paper/2109.09690/) (2021)
- [When are Iterative Gaussian Processes Reliably Accurate?](https://mlsanity.com/paper/2112.15246/) (2021)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [Tuning Legged Locomotion Controllers via Safe Bayesian Optimization](https://mlsanity.com/paper/2306.07092/) (2023)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Robust and Conjugate Spatio-Temporal Gaussian Processes](https://mlsanity.com/paper/2502.02450/) (2025)
- [Iterative Methods for Vecchia-Laplace Approximations for Latent Gaussian Process Models](https://mlsanity.com/paper/2310.12000/) (2023)
- [Effective Bayesian Causal Inference via Structural Marginalisation and Autoregressive Orders](https://mlsanity.com/paper/2402.14781/) (2024)
- [Faster Kernel Interpolation for Gaussian Processes](https://mlsanity.com/paper/2101.11751/) (2021)
- [Sensitivity Prewarping for Local Surrogate Modeling](https://mlsanity.com/paper/2101.06296/) (2021)
- [Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data](https://mlsanity.com/paper/2405.14492/) (2024)
- [Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processes](https://mlsanity.com/paper/2308.14142/) (2023)
- [Rate-Informed Discovery via Bayesian Adaptive Multifidelity Sampling](https://mlsanity.com/paper/2411.17826/) (2024)
- [Multi-armed bandits for resource efficient, online optimization of language model pre-training: the use case of dynamic masking](https://mlsanity.com/paper/2203.13151/) (2022)
- [Sparse Kernel Gaussian Processes through Iterative Charted Refinement (ICR)](https://mlsanity.com/paper/2206.10634/) (2022)
- [Scaling up Probabilistic PDE Simulators with Structured Volumetric Information](https://mlsanity.com/paper/2406.05020/) (2024)
- [Contraction rates for conjugate gradient and Lanczos approximate posteriors in Gaussian process regression](https://mlsanity.com/paper/2406.12678/) (2024)
- [AUGUR, A flexible and efficient optimization algorithm for identification of optimal adsorption sites](https://mlsanity.com/paper/2409.16204/) (2024)
- [Batched Energy-Entropy acquisition for Bayesian Optimization](https://mlsanity.com/paper/2410.08804/) (2024)
- [HiGP: A high-performance Python package for Gaussian Process](https://mlsanity.com/paper/2503.02259/) (2025)

## Abstract (arXiv)

One of the most compelling features of Gaussian process (GP) regression is its ability to provide well-calibrated posterior distributions. Recent advances in inducing point methods have sped up GP marginal likelihood and posterior mean computations, leaving posterior covariance estimation and sampling as the remaining computational bottlenecks. In this paper we address these shortcomings by using the Lanczos algorithm to rapidly approximate the predictive covariance matrix. Our approach, which we refer to as LOVE (LanczOs Variance Estimates), substantially improves time and space complexity. In our experiments, LOVE computes covariances up to 2,000 times faster and draws samples 18,000 times faster than existing methods, all without sacrificing accuracy.