# Variational Nearest Neighbor Gaussian Process

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 3 Feb 2022.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Hierarchical Nearest-Neighbor Gaussian Process Models for Large Geostatistical Datasets](https://mlsanity.com/paper/1406.7343/) (2014)
- [Understanding Probabilistic Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1606.04820/) (2016)
- [A general framework for Vecchia approximations of Gaussian processes](https://mlsanity.com/paper/1708.06302/) (2017)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Local Gaussian process approximation for large computer experiments](https://mlsanity.com/paper/1303.0383/) (2013)
- [A Framework for Interdomain and Multioutput Gaussian Processes](https://mlsanity.com/paper/2003.01115/) (2020)
- [MCMC for Variationally Sparse Gaussian Processes](https://mlsanity.com/paper/1506.04000/) (2015)
- [Natural Gradients in Practice: Non-Conjugate Variational Inference in Gaussian Process Models](https://mlsanity.com/paper/1803.09151/) (2018)
- [Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization](https://mlsanity.com/paper/2006.11267/) (2020)
- [Permutation and Grouping Methods for Sharpening Gaussian Process Approximations](https://mlsanity.com/paper/1609.05372/) (2016)
- [Variational Inference for Gaussian Process Models with Linear Complexity](https://mlsanity.com/paper/1711.10127/) (2017)
- [Sparse within Sparse Gaussian Processes using Neighbor Information](https://mlsanity.com/paper/2011.05041/) (2020)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Correlation-based sparse inverse Cholesky factorization for fast Gaussian-process inference](https://mlsanity.com/paper/2112.14591/) (2021)
- [Patchwork Kriging for Large-scale Gaussian Process Regression](https://mlsanity.com/paper/1701.06655/) (2017)
- [Large-Scale Cox Process Inference using Variational Fourier Features](https://mlsanity.com/paper/1804.01016/) (2018)
- [Hierarchical Inducing Point Gaussian Process for Inter-domain Observations](https://mlsanity.com/paper/2103.00393/) (2021)
- [Scalable Cross Validation Losses for Gaussian Process Models](https://mlsanity.com/paper/2105.11535/) (2021)
- [Input Dependent Sparse Gaussian Processes](https://mlsanity.com/paper/2107.07281/) (2021)

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

- [Scalable Bayesian Optimization Using Vecchia Approximations of Gaussian Processes](https://mlsanity.com/paper/2203.01459/) (2022)
- [Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization](https://mlsanity.com/paper/2301.13303/) (2023)
- [Actually Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2304.05091/) (2023)
- [B'ezier Gaussian Processes for Tall and Wide Data](https://mlsanity.com/paper/2209.00343/) (2022)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Beyond Intuition, a Framework for Applying GPs to Real-World Data](https://mlsanity.com/paper/2307.03093/) (2023)
- [A Hierarchical Variational Graph Fused Lasso for Recovering Relative Rates in Spatial Compositional Data](https://mlsanity.com/paper/2509.20636/) (2025)
- [Adaptive multi-resolution Gaussian processes: Scalable exact inference with naturally data-sparse covariance matrices](https://mlsanity.com/paper/2609.30348/) (2026)

## Abstract (arXiv)

Variational approximations to Gaussian processes (GPs) typically use a small set of inducing points to form a low-rank approximation to the covariance matrix. In this work, we instead exploit a sparse approximation of the precision matrix. We propose variational nearest neighbor Gaussian process (VNNGP), which introduces a prior that only retains correlations within K nearest-neighboring observations, thereby inducing sparse precision structure. Using the variational framework, VNNGP's objective can be factorized over both observations and inducing points, enabling stochastic optimization with a time complexity of O(K3). Hence, we can arbitrarily scale the inducing point size, even to the point of putting inducing points at every observed location. We compare VNNGP to other scalable GPs through various experiments, and demonstrate that VNNGP (1) can dramatically outperform low-rank methods, and (2) is less prone to overfitting than other nearest neighbor methods.