Density-Aware Calibration for Nearest-Neighbor Gaussian Processes

The fastest Gaussian process (GP) regressors predict each test point from only its few nearest training points. A GP is a Bayesian regression model that returns a prediction together with an error bar. These methods use the same "how many neighbors, how smooth, how noisy" settings everywhere. Real spatial data is rarely spread evenly. House sales crowd into cities, rain gauges into populated valleys, air-quality monitors into capitals. Fifty neighbors in London may cover a few streets, while fifty neighbors in rural Wales may span tens of kilometres. A single global setting is then tuned mostly to the dense regions, because that is where most of the data sits. Clustering has long known this problem as the failure of global density thresholds. We propose to carry that lesson into scalable GP regression. The neighbor search these methods already run gives a free estimate of local data density. We would use that estimate, together with external context variables such as property type, season, or weather, to set the GP's smoothness and noise point by point instead of globally. External context variables are usually called exogenous variables.

The claim is specific and testable. The known robustness of nearest-neighbor GPs to wrong settings is a dense-data property. It should fail in exactly the sparse regions where users most need honest error bars. A cheap correction keyed to local neighbor distance and exogenous context should close most of the sparse-region gap in accuracy and calibration at almost no extra cost. It should do so without harming dense regions and without adding exogenous variables to the neighbor search space.

Core Claim

Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression introduces GPnn. GPnn estimates kernel hyperparameters on a small random subset. It then predicts each query from its $m$ nearest neighbors and applies one global post-hoc fix to the noise variance. The paper proves that mean squared error becomes insensitive to a misspecified kernel as $n \to \infty$. That limit is a local infill limit: it requires neighbors to crowd ever closer to the query. Where data is sparse, the limit is never reached. There the distance to the $m$-th neighbor, $r_m(x)$, is comparable to the kernel lengthscale $\ell$, and prediction error depends strongly on whether $\ell$ is right. Standard GP error bounds scale with the ratio of fill distance to lengthscale, which is where this dependence comes from.

A random estimation subset compounds the problem. It is drawn mostly from dense regions, so the global $\ell$ and noise variance $\sigma^2$ describe those regions. The single calibration step then averages over very different regimes. This motivation follows Gap 1 and Gap 4 of the research file. In the clustering setting, Clustering by Exceptions and Nearest-Neighbour-Induced Isolation Similarity and Its Impact on Density-Based Clustering show that absolute distance misrepresents affinity when density varies. We transfer that observation from cluster boundaries to regression calibration.

The mechanism replaces GPnn's global hyperparameters $\theta = (\ell, s^2, \sigma^2)$, meaning lengthscale, signal variance, and noise variance, with a low-dimensional function:

$$ \log \theta(x) = g_\phi\big(\log r_m(x),\ \rho(x),\ z(x)\big). $$

Here $r_m(x)$ is the distance to the $m$-th neighbor, which GPnn already computes. $\rho(x)$ is the ratio of $r_m(x)$ to the average $r_m$ of $x$'s neighbors, which is the normalized relative-density score from Clustering by Exceptions. $z(x)$ is the exogenous context. $g_\phi$ is a small monotone spline or two-layer network with parameters $\phi$. Each prediction in GPnn is an independent small GP on $m$ points, so letting $\theta$ vary with the query creates no positive-definiteness problem. That problem makes nonstationary kernels hard in global GPs, but GPnn's decoupled design removes it, and we exploit that property. Exogenous variables enter only through $g_\phi$, or optionally an additive mean term. They change how smooth and how noisy the field is believed to be near $x$. They never enter the neighbor search, so retrieval keeps the low dimension of the physical coordinates.

Research Program

The estimation step changes in two ways.

First, the hyperparameter subset is drawn stratified by density quantile, so sparse regions are represented in proportion to area rather than to point count. This is a sampling analogue of the density equalization in CDF Transform-and-Shift. CDF-TS reshapes coordinates so that fixed-threshold clustering works under uneven densities. We leave the coordinates alone and equalize only which points inform the hyperparameters, because warping inputs would distort the spatial distances the kernel is meant to model.

Second, within each stratum we fit local hyperparameters by maximizing the marginal likelihood of many small neighborhood GPs. Each costs $O(m^3)$ with $m$ around 32 to 400. We then fit $g_\phi$ across strata and exogenous values. Noise calibration is fitted the same way: leave-one-out standardized residuals are regressed on the inputs of $g_\phi$, replacing GPnn's single scalar correction.

Three analyses accompany the method. The first measures how GPnn's error and calibration change with the density decile of the query on real data. This tests whether the robustness theorem in fact degrades in sparse regions; if it does not, the project's premise fails early and cheaply. The second compares a variance-only correction against full local hyperparameters. That separates "only the error bars were wrong" from "the predictions were also wrong." The third checks whether exogenous context explains residual nonstationarity beyond what density explains. Weather-driven noise in air-quality monitors is the natural example, in the spirit of the heteroscedastic regime shifts described in Aura. Aura handles such shifts with a large neural router. We use a few scalars.

As an extension, the same $g_\phi$ can define a Gibbs-style nonstationary kernel inside Variational nearest neighbor Gaussian process. VNNGP conditions each latent value on its $K$ nearest neighbors through a sparse precision matrix. Its authors note that static Euclidean neighbor graphs fail under anisotropy. The extension is secondary because VNNGP requires a valid joint covariance, which constrains the form of $g_\phi$.

Baselines

The naive reference is GPnn exactly as published in Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression. It uses global hyperparameters from a random subset and its global noise correction. Plain $k$-nearest-neighbor regression serves as a floor for the mean. GPnn is also the strongest competitor on speed. The paper reports about 30 seconds on a laptop for $1.6\times10^6$ HouseElectric points, roughly a 100x speedup over other methods, and better MSE and NLL than SVGP and distributed GPs on most UCI datasets. The file gives no numerical MSE or NLL for any of these datasets, so: no reported result found on Lacuna for GPnn RMSE/NLL on UKHousing, Precipitation, 3DRoad or HouseElectric. We will rerun it ourselves.

The strongest accuracy competitor is VNNGP from Variational nearest neighbor Gaussian process. It trains hyperparameters on all data by minibatching and reportedly beats SVGP with 1024 inducing points at $K=32$ on UKHousing, with the lowest NLL on almost all spatial datasets. No numerical values are reported in the file. Because it fits hyperparameters on everything, it is the right test of whether our gains come merely from GPnn's cheap subset fit. We will also run SVGP, a sparse variational GP that summarizes the data through 1024 learned "inducing" points, for context.

All methods will use the same train/test splits, the same physical-coordinate neighbor index, and the same neighbor count $m$ or $K$. Each gets the same budget of 20 hyperparameter-tuning trials on a validation split and the same single-GPU or laptop hardware, with wall-clock time reported. Beating the baselines means two things. The method must lower NLL and improve 90% interval coverage in the sparsest density quintile by a margin larger than across-seed variation, against both GPnn and VNNGP. And it must stay within noise of them on the densest quintile, at less than twice GPnn's runtime.

Four ablations isolate the key ingredient. The first is density-only, with no $z$. The second is exogenous-only, with no density inputs. The third is variance-only correction, where $g_\phi$ rescales the predictive variance but leaves $\ell$ and $s^2$ global. The fourth is stratified sampling with global hyperparameters, which tests whether the subset change alone does the work.

Why not just…?

Why not just append the exogenous variables to the inputs with per-dimension lengthscales and run GPnn or VNNGP unchanged? This is a real threat when exogenous variables are few and smooth, and it will be run directly as a baseline. Its expected weakness is that it puts context into the neighbor search. Two houses sold a decade apart, or two monitors under different weather, stop being neighbors even when they are adjacent. Search dimension also grows, and the file notes that neighbor retrieval degrades as dimension grows. It also does nothing for density-driven miscalibration. If concatenation matches our exogenous-only ablation, we will drop the exogenous gating claim and keep only the density claim.

Why not just recalibrate predictive variances post hoc, per density bin or with a residual regression? This is the most serious alternative, because GPnn already shows that cheap calibration fixes much of the NLL. Our variance-only ablation is exactly this method. If it matches the full method on both RMSE and NLL in sparse regions, then local lengthscales add nothing and the contribution reduces to stratified recalibration. We would report that honestly. Our hypothesis is that sparse-region RMSE also improves, because the mean depends on $\ell$ when $r_m/\ell$ is not small. Recalibrating variances cannot change the mean.

Why not just density-equalize the inputs with CDF Transform-and-Shift and then run Euclidean GPnn? CDF-TS works for clustering because it only needs cluster membership preserved. For regression it would change the distances over which the kernel measures correlation, stretching dense cities and compressing countryside in ways unrelated to how the target varies. It also carries the iterative cost the file flags. We will include it as a baseline on UKHousing and Precipitation. We expect it to help sparse calibration but hurt dense-region RMSE.

Why not just use more neighbors, or VNNGP's full-data hyperparameter fit? Larger $m$ widens the receptive field everywhere and costs $O(m^3)$ per query. Full-data fitting still yields one global $\theta$ dominated by dense regions. Sweeping $m$ from 32 to 400 for both GPnn and VNNGP will show whether the sparse-quintile gap shrinks with $m$ alone.

Proposed Experiments

The main experiments use UKHousing, Precipitation and 3DRoad, the spatial suites used by VNNGP and GPnn, plus the UCI suite from GPnn (Poletele, Bike, Protein, Ctslice, Road3D, Song, HouseElectric) as a check on non-spatial inputs. Exogenous variables are property type and sale date for UKHousing and time and season for Precipitation. The exogenous-only arm is skipped where no meaningful $z$ exists.

For a harder, policy-relevant test we use Air Quality Arena. Its 14,000+ monitors across seven countries have strongly uneven station density. The task is spatial interpolation of held-out stations at each hour. Inputs are station coordinates. Context is hour, day of week, and co-measured pollutants, with meteorology added if it is available in the release. Hold-outs are stratified so that rural stations are well represented. The AQA paper reports that supervised models in India's CPCB network struggle to beat Seasonal Naive, which makes CPCB a stress test for calibration under volatility.

Metrics are RMSE, NLL, and the coverage of 50% and 90% predictive intervals, each reported overall and by density quintile defined from $r_m$. Runtime is also reported.

The decisive check is the per-quintile plot for GPnn in the first analysis. If GPnn's sparse-quintile NLL and coverage are not clearly worse than its dense-quintile values, the premise is wrong and the project stops. If they are worse, the second decisive check is whether full local hyperparameters beat the variance-only ablation on sparse-quintile RMSE. That result determines whether the contribution is a better calibration rule or a better local model.