Forgetting Points Without Forgetting Information in Nearest-Neighbor Gaussian Processes

A Gaussian process (GP) is a Bayesian regression model that returns a prediction together with a calibrated error bar. Exact GPs cost cubic time in the number of data points, so the most accurate scalable variants replace the full model with a sparse graph. Each point "listens" only to its $K$ nearest earlier neighbors. Variational nearest neighbor Gaussian process (VNNGP) builds this graph once, offline, and then trains at a cost of $O(K^3)$ per step. Real deployments are streaming: sensors, spatial surveys and optimization loops keep adding points, and memory budgets force old points out. Today the only principled options are to rebuild the graph and retrain, or to switch to low-rank streaming GPs, which blur fine spatial detail.

We propose a bounded-memory streaming nearest-neighbor GP built on one observation. Removing a point from a GP's sparse graph is marginalization: the point is integrated out, not merely erased. Marginalizing a Gaussian is a Schur complement on its precision (inverse covariance) matrix, which is exactly the "star-mesh" transform that the vector-search community uses heuristically to patch deleted nodes in search graphs. In a GP this operation is exact, so the removed point's information survives in its neighbors. What is left to design is a principled rule for trimming the dense patch back to $K$ neighbors. We choose the rule that loses the least probability mass, measured by Kullback–Leibler (KL) divergence, a standard measure of how far one distribution is from another. The result keeps memory constant, keeps VNNGP's local sharpness, and retains what pruned points taught the model.

Core Claim

In a nearest-neighbor GP whose variational posterior (the model's learned belief over function values) is stored as a sparse precision on the neighbor graph, there are two steps to maintenance. Deletions are handled by exact Schur-complement marginalization of that posterior, followed by KL-guided projection back onto a $K$-neighbor sparsity pattern. Insertions are handled by appending points to the conditioning order and linking them to neighbors through a dynamically maintained proximity index.

Under a fixed memory budget, this should match periodic full retraining in accuracy at a small fraction of the update cost. It should also clearly beat "drop the point and re-pick neighbors" on regions the stream has already left.

The novelty is not "use a dynamic nearest-neighbor index inside a GP." Any off-the-shelf dynamic index can answer neighbor queries. What is new is that the GP's own algebra tells the graph maintainer which patch edges to keep and what numerical values they should carry.

Where This Sits

The problem is motivated by the static assumption shared by the two locality-based GP methods. VNNGP places an inducing variable at every training point and conditions each point on its $K$ Euclidean nearest neighbors in a fixed ordering. It reports that $K=32$ beats a sparse variational GP with 1024 inducing points on UKHousing. It gives no mechanism for inserting or removing points. GPnn separates cheap hyperparameter fitting from prediction over the $m$ nearest neighbors of each test point. It reports training on $1.6\times10^6$ points in about 30 seconds, roughly a 100x speedup. However, it treats its approximate-nearest-neighbor index as a static database and has no posterior state to maintain at all.

The streaming GP line solves online updating but constrains the design space in a way we avoid. Streaming Sparse Gaussian Process Approximations (SSGP) turns the previous posterior into a likelihood for old data and projects onto $M$ moving pseudo-points. We borrow that "old posterior as prior" logic. We do not borrow its global low-rank bottleneck, which Approximation-Aware Bayesian Optimization shows smooths over sharp local structure. Recurrent Memory for Online Interdomain Gaussian Processes (OHSVGP) compresses one-dimensional streams through recurrent polynomial-basis memories. On multi-dimensional spatial data it needs artificial sorting heuristics, which is precisely the regime we target.

The maintenance mechanism comes from vector search. Graph-based Nearest Neighbors with Dynamic Updates via Random Walks (SPatch) replaces a deleted search-graph node with a weighted clique among its neighbors, justified through random-walk hitting times. It then keeps the top-$t$ edges with a tuned threshold. Proximity Graph Maintenance for Fast Online Nearest Neighbor Search (IPGM) instead re-inserts orphaned neighbors by global search. The DiskANN library keeps deleted nodes as temporary waypoints until a batch consolidation step.

Both SPatch and IPGM justify their patches by search recall, and SPatch's edge-selection threshold is admittedly heuristic. In our setting the Schur complement is not a surrogate for anything: it is the exact marginal. The trimming criterion can therefore be derived rather than tuned. Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs studies the same algebra purely as a graph-sparsification problem, which supports treating these as one operation.

Research Program

The model keeps three things: a Vecchia prior (each point's GP conditional given its parent set, computed with local $K\times K$ solves); a variational posterior whose precision is stored as a sparse inverse-Cholesky factor on the same parent pattern; and a dynamic proximity graph over point locations, used only to find candidate neighbors.

Insertion. A new observation is appended at the end of the conditioning order. Its parents are its $K$ nearest existing points, returned by the proximity graph. Because earlier points condition only on their predecessors, no existing conditional changes. The new point's variational parameters are initialized from the GP conditional plus its likelihood term, then refined by a few minibatch steps of the online objective.

Deletion. Deletion is triggered when the memory budget $B$ is exceeded; pruning policies such as oldest-first or lowest-leverage are compared. We marginalize the point $x$ out of the variational posterior. Let $\Lambda$ be the posterior precision, $x$ the removed point, $R$ its Markov blanket (the parents and children that share a nonzero precision entry with $x$), and $\Lambda_{AB}$ the block of $\Lambda$ between index sets $A$ and $B$. The exact marginal precision over the blanket is

$$\Lambda'_{RR} = \Lambda_{RR} - \Lambda_{Rx}\,\Lambda_{xx}^{-1}\,\Lambda_{xR}.$$

The subtracted term creates new dependencies among members of $R$. This is the "mesh" in star-mesh, now with Gaussian weights. Each child that lost $x$ as a parent then chooses a new parent set of size $K$. Candidates are its surviving parents, the fill-in partners created above, and a few proximity-graph neighbors. We pick greedily by the largest reduction in the child's conditional variance under the marginal. This greedy rule is the local step that minimizes the KL divergence from the dense marginal to the sparse factor.

The same parent selection is applied to the prior, so prior and posterior keep the same pattern. The ordering stays valid because every replacement parent precedes the child. The deleted point's likelihood contribution is not discarded; it lives on in $\Lambda'$, much as SSGP retains old data through its projected posterior.

The analysis has two parts. We bound the KL divergence lost per deletion in terms of how much of the child's conditional variance the discarded fill-in edges would have explained. We also show that positive-definiteness is preserved by construction, since each factor is a valid inverse Cholesky. The per-deletion cost is $O(|R|\,K^3)$, independent of the number of points $N$. As a secondary, low-cost check, we swap our variance-reduction rule into SPatch's top-$t$ step on SIFT to see whether the GP-derived criterion transfers back to search.

Baselines

The naive reference is periodic full retraining: static VNNGP rebuilt from scratch on the current buffer every $T$ updates. This is the "ReBuild" strategy that IPGM beat by up to 18.8% in efficiency for search indices, and that dynamic coarsening beat by 10–20x in Adapting to Evolving Graphs. We run it with the same $K$, the same hyperparameters, and several values of $T$, and report the full accuracy-versus-compute curve. Beating it means matching its negative log likelihood (NLL, the standard measure of how well predicted error bars fit the data) within noise, at a lower cumulative update cost.

The strongest existing competitor for prediction is GPnn over a dynamic index. We run GPnn's local predictor on a FreshVamana-style index kept under the same memory budget, with the same neighbor count and hyperparameters fitted on the same subsample. For the index itself, the DiskANN paper reports that FreshVamana maintains above 95% recall over 50 churn cycles. We found no result on Lacuna for GPnn under streaming insertions and deletions. Its static result is the ~30-second, 100x-speedup figure quoted above. Beating it means lower NLL and RMSE on regions whose points have been pruned, where GPnn has no information left.

The strongest streaming GP competitor is SSGP with $M$ chosen to use the same memory as our budget $B$, under the same wall-clock allowance. On one-dimensional or time-ordered streams we also include OHSVGP, which reports being about 350x faster than an earlier online sparse GP on Solar (0.4 s versus 140 s). We found no result on Lacuna for either method on the spatial streams we use.

Two ablations isolate the key ingredient:

  • Drop and re-select. Delete the point, re-pick each orphaned child's parents through the proximity graph, and reinitialize the affected variational entries from the prior. This is the GP analog of IPGM's Global Reconnect.
  • Tombstoning. Keep deleted points in the graph as masked parents, as in DiskANN's lazy policy. For search, SPatch reports that removing and patching nodes gives 2.5x–3x faster queries than tombstones.

Every method gets the same hyperparameter tuning budget on a held-out prefix of the stream.

Why not just…?

Why not just rebuild VNNGP periodically? Rebuilding is simple and exactly correct at rebuild time. However, it discards pruned points' information unless the buffer grows without bound, and it goes stale between rebuilds. If its accuracy-versus-compute curve dominates ours at every value of $T$, the proposal fails. That is a direct, measurable outcome.

Why not just run GPnn on an existing dynamic nearest-neighbor index? This is the real threat, because it needs no new algorithm. Its weakness under a memory budget is structural: GPnn predicts only from stored points, so a pruned region becomes empty. It also has no training-time posterior that could carry forward what was learned there. The old-region NLL measurement below settles the question. If GPnn matches us there, the marginalization step adds nothing.

Why not just use a streaming sparse GP like SSGP? SSGP retains old information by design but through a global low-rank representation. The VNNGP comparison on UKHousing, and the "blurriness" findings in Approximation-Aware Bayesian Optimization, suggest this loses short-lengthscale structure. SSGP will be run at equal memory. If it wins on smooth data, that result is expected and will be reported.

Why not just drop the point and warm-restart a few gradient steps? Minibatch training might recover the lost information on its own, which would make exact marginalization unnecessary. The drop-and-re-select ablation with matched extra gradient steps tests exactly this. Marginalization must win by a margin that exceeds seed variance to justify itself.

Proposed Experiments

We create streams from the benchmarks in the file:

  • Spatial sweeps. Points arrive in a sweep across space, so the budget forces pruning of regions the stream has left. We use UKHousing, Precipitation and 3DRoad, from the VNNGP and GPnn evaluations, and OS Terrain 50, from the SSGP evaluation.
  • Spatio-temporal window. ERA5 climate data, from the OHSVGP evaluation, with a sliding time window.
  • Random-order streams. UCI Protein, Song and HouseElectric, from GPnn's suite, streamed in random order to test the non-spatial case.

Metrics are RMSE and NLL on three held-out sets: the current region, previously visited (now pruned) regions, and the whole domain. We also report per-update wall-clock time and peak memory, and we compare against an unbudgeted static VNNGP as an upper reference.

The decisive check is old-region NLL at a budget of 10% of the stream length. Marginalization must beat both drop-and-re-select and GPnn-on-a-dynamic-index. It must also stay within a small gap of full retraining, while per-update cost stays flat as $N$ grows.

The second check is whether the KL bound predicts the observed per-deletion accuracy loss. If it does, the bound can be used to adapt $K$ online.

The third check is the transfer test on SIFT. Recall-versus-queries-per-second under SPatch's 80% mass-deletion protocol tells us whether the GP-derived trimming rule can replace SPatch's tuned threshold. A negative result there would not undermine the GP contribution.