# GraphGP: Scalable Gaussian Processes with Vecchia's Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 9 Jun 2026.

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

- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Permutation and Grouping Methods for Sharpening Gaussian Process Approximations](https://mlsanity.com/paper/1609.05372/) (2016)
- [Vecchia approximations of Gaussian-process predictions](https://mlsanity.com/paper/1805.03309/) (2018)
- [Metric Gaussian Variational Inference](https://mlsanity.com/paper/1901.11033/) (2019)
- [Geometric variational inference](https://mlsanity.com/paper/2105.10470/) (2021)
- [The Galactic 3D large-scale dust distribution via Gaussian process regression on spherical coordinates](https://mlsanity.com/paper/2204.11715/) (2022)
- [Sparse Kernel Gaussian Processes through Iterative Charted Refinement (ICR)](https://mlsanity.com/paper/2206.10634/) (2022)
- [A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees](https://mlsanity.com/paper/2210.12859/) (2022)
- [GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees](https://mlsanity.com/paper/2211.00120/) (2022)
- [Implementation and Analysis of GPU Algorithms for Vecchia Approximation](https://mlsanity.com/paper/2407.02740/) (2024)

## Abstract (arXiv)

Gaussian processes are a powerful tool for modeling continuous fields, but their naive O(N3) computational cost and O(N2) memory requirement often limit their practical use. Vecchia's approximation is a sparse precision matrix approximation for stationary, decaying kernels that conditions each point only on its k nearest neighbors. We present GraphGP, a GPU algorithm for Vecchia's approximation that scales to nearly a billion parameters with linear time and memory requirements, handling arbitrary point distributions over a large dynamic range. Our key contributions are (1) a bit-reversed k-d tree ordering that allows efficient neighbor searches while also maximizing batch parallelism, and (2) a differentiable CUDA implementation, which is substantially faster and more memory efficient than our pure JAX baseline. GraphGP provides the building blocks for inference, including forward generation, inverse application, log-determinant, and kernel parameter derivatives.