# Log-Linear-Time Gaussian Processes Using Binary Tree Kernels

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (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)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Double descent in the condition number](https://mlsanity.com/paper/1912.06190/) (2019)
- [SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes](https://mlsanity.com/paper/2106.06695/) (2021)
- [Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization](https://mlsanity.com/paper/2006.11771/) (2020)
- [Random Forest (RF) Kernel for Regression, Classification and Survival](https://mlsanity.com/paper/2009.00089/) (2020)

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

- [Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processes](https://mlsanity.com/paper/2308.14142/) (2023)
- [Data-Driven Abstractions via Binary-Tree Gaussian Processes for Formal Verification](https://mlsanity.com/paper/2407.21029/) (2024)
- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [Domain Invariant Learning for Gaussian Processes and Bayesian Exploration](https://mlsanity.com/paper/2312.11318/) (2023)

## Abstract (arXiv)

Gaussian processes (GPs) produce good probabilistic models of functions, but most GP kernels require O((n+m)n2) time, where n is the number of data points and m the number of predictive locations. We present a new kernel that allows for Gaussian process regression in O((n+m)log(n+m)) time. Our "binary tree" kernel places all data points on the leaves of a binary tree, with the kernel depending only on the depth of the deepest common ancestor. We can store the resulting kernel matrix in O(n) space in O(n log n) time, as a sum of sparse rank-one matrices, and approximately invert the kernel matrix in O(n) time. Sparse GP methods also offer linear run time, but they predict less well than higher dimensional kernels. On a classic suite of regression tasks, we compare our kernel against Mat'ern, sparse, and sparse variational kernels. The binary tree GP assigns the highest likelihood to the test data on a plurality of datasets, usually achieves lower mean squared error than the sparse methods, and often ties or beats the Mat'ern GP. On large datasets, the binary tree GP is fastest, and much faster than a Mat'ern GP.