Cache-Sized Subdomains for Exact Gaussian Processes

Exact Gaussian processes are Bayesian regression models that give calibrated uncertainty along with their predictions. They are expensive because training has to solve a linear system with, and estimate the log-determinant of, an $n \times n$ covariance matrix. The best current systems split that work evenly across GPUs and report "almost linear" speedup: eight GPUs are roughly eight times faster (Exact Gaussian Processes on a Million Data Points). In scientific computing, the same kind of solver sometimes does better than linear. When a fixed problem is cut into enough pieces that each piece fits in a processor's fast on-chip memory (its cache), each processor stops waiting on slow main memory, and $N$ processors can run more than $N$ times faster. This has been reported for turbulence solvers (Offermans et al.) and, closest to our setting, for conjugate-gradient solves inside domain-decomposed optimization (Lueg et al.).

We propose to bring this effect to Gaussian processes where it can actually occur. That is not the dense case. It is covariance matrices made genuinely sparse by compactly supported kernels, which are kernels whose correlation drops exactly to zero beyond a cutoff distance (gp2Scale). The method partitions the data spatially into subdomains sized to fit in cache. It eliminates each subdomain's interior points exactly with local Cholesky factorizations, and solves only the much smaller system on subdomain boundaries iteratively. This yields exact solves, a log-determinant that is mostly computed exactly rather than estimated, and hyperparameter gradients. The work also measures, and honestly attributes, where any super-linear speedup comes from.

Core Claim

We make three claims. First, for compactly supported kernels on low-dimensional inputs, a Schur-complement domain decomposition of the covariance matrix gives exact Gaussian process training whose strong scaling has a predictable super-linear window. The window opens when each worker's stored sparse block fits in its last-level cache. It closes when the global reductions in conjugate gradients dominate, the same "breaking point" Offermans et al. mapped for spectral-element codes.

Second, the decomposition changes the log-determinant problem. Write $K_\theta$ for the kernel-plus-noise matrix with hyperparameters $\theta$, $K_{II}^{(s)}$ for the interior block of subdomain $s$, and $S$ for the Schur complement on the interface (boundary) points. Block elimination then gives the identity

$$\log|K_\theta| = \sum_{s=1}^{S_{\text{sub}}} \log|K_{II}^{(s)}| + \log|S|.$$

The first term is exact and embarrassingly parallel, computed from local Cholesky factors. Only $\log|S|$ needs stochastic estimation, and $S$ is far smaller than $K_\theta$. We precondition that estimate with the diagonally-assembled additive Schwarz (ASd) preconditioner from Lueg et al. This extends the single-device preconditioned log-determinant estimator of Preconditioning for Scalable Gaussian Process Hyperparameter Optimization to distributed training. It should also shrink estimator variance enough to keep that paper's L-BFGS (a quasi-Newton optimizer) usable at the 10-million-point scale.

Third, and most important for credibility, we separate two sources of super-linearity. One is the hardware effect: data now fits in cache. The other is algorithmic: local factorizations cost $O((n/S_{\text{sub}})^3)$ each, so their total cost falls faster than the number of subdomains grows. The algorithmic gain would also appear on a single device running the same many-block solver. We decouple the number of subdomains $S_{\text{sub}}$ from the number of workers $P$ so the two effects can be measured separately.

Why This Is Not Already Done

Several close pieces of work each stop short of this. Wang et al. partition dense kernel matrix-vector products across GPUs, computing kernel blocks on the fly. That work is compute-bound, so cache residency has little to gain there, which is consistent with the near-linear scaling they report. gp2Scale makes the matrix sparse and distributes kernel assembly, but trains by block-MCMC with host-node assembly. It uses no iterative decomposition, and the file reports no speedup measurements for it. Lueg et al. show super-linear PCG scaling between 64 and 256 ranks, but for interior-point optimization, with no kernel matrices or log-determinants. GPyTorch and the preconditioning paper stay on a single device.

We supply the combination and the attribution study. We do not claim that dense exact Gaussian processes become super-linear. We expect they do not, and we will show it.

Research Program

The first component is the solver. Points are ordered with a k-d tree so that each leaf is a subdomain and points within the kernel cutoff of another leaf become interface points. Each worker stores its sparse interior block, its Cholesky factor, and its coupling rows. Leaf size is chosen from a simple capacity model: bytes of stored nonzeros, plus the factor, plus halo buffers, must stay below the measured cache capacity of the target device. That capacity will be measured, not assumed.

The interface system is solved with PCG under ASd, with full additive Schwarz and block Jacobi as comparison preconditioners. Stochastic trace estimation of $\log|S|$ uses Lanczos quadrature on the ASd-preconditioned operator. Hyperparameter gradients are obtained by differentiating the block elimination, using the same probe vectors.

The second component is a performance model. It predicts time per training iteration as a function of $P$ and $S_{\text{sub}}$ from three quantities: memory traffic under the measured bandwidth of each memory level, local factorization flops, and allreduce latency. This makes the predicted super-linear window a falsifiable statement rather than an after-the-fact story.

The third component is a statistical check, because the kernel is being changed. Compact support buys sparsity at the cost of modelling assumptions. We will report accuracy against dense exact Gaussian processes wherever the dense version is feasible.

Baselines

The naive reference point is the same compact-kernel Gaussian process trained on one worker with one subdomain. That means sparse PCG with a Jacobi preconditioner and unpreconditioned stochastic trace estimation. Speedups are reported against it and, separately, against the single-device many-subdomain ablation described below. All methods get the same data splits, the same stopping tolerance on the solve, and the same hyperparameter-optimization budget in wall-clock time.

The strongest dense competitor is multi-GPU BBMM from Wang et al. BBMM is conjugate gradients built on batched matrix products, preconditioned by pivoted Cholesky. This is the only exact method in the file shown at a million points. On Kin40k, Wang et al. report test RMSE 0.099 for the exact GP against 0.273 for SGPR. On HouseElectric they report under 2 hours on 8 V100 GPUs. We rerun it in GPyTorch on the same hardware with their pretrain-on-a-subset-then-fine-tune protocol. Beating it means matching its RMSE within noise on spatial benchmarks at lower wall-clock time for the same number of devices. On Kin40k, it means quantifying how much RMSE compact support costs relative to 0.099.

The strongest compact-kernel competitor is gp2Scale's distributed block-MCMC pipeline, run with identical kernels on the 3D temperature data. There is no reported result found on Lacuna for gp2Scale's RMSE or speedup, so we measure both ourselves. Beating it means equal or better CRPS (continuous ranked probability score) at lower time-to-converged-hyperparameters.

The local-approximation competitor is GPnn (Leveraging Locality and Robustness). It reports about 30 seconds on a laptop for 1.6 million points and roughly 100× speedup over other methods. We run it with its recommended neighbor counts and its calibration step. SGPR and SVGP (inducing-point methods) are also run, with inducing budgets tuned under the same time cap.

Three ablations isolate the proposal's ingredients. The central one is the single-device batched variant: identical subdomains and solver, all on one device. It isolates the algorithmic gain from the hardware gain. The second is a uniform row-block partition of the same sparse matrix without cache-aware sizing. The third is Schur-complement training with an unpreconditioned log-determinant estimate. This isolates the benefit of combining ASd with the exact interior log-determinant.

Why not just…?

Why not just use an inducing-point method like SVGP or SGPR? Wang et al. show these methods saturate as data grows. Their Kin40k gap is 0.273 against 0.099. Approximation-Aware Bayesian Optimization shows the fixed inducing budget smooths away sharp local structure. Our topography and temperature experiments test whether that loss appears on strongly non-stationary spatial fields, where compact kernels were designed to help.

Why not just use GPnn? This is a real threat on low-dimensional data, where nearest-neighbor search is cheap. GPnn may simply win on wall-clock time for prediction accuracy alone. Our case rests on three things GPnn lacks: a global exact likelihood for hyperparameters, stronger calibration than its weak-calibration guarantee, and preserved long-range coupling through the interface system. If GPnn matches our RMSE and CRPS at a fraction of the cost on temperature and 3DRoad, we will report that the solver's value is limited to likelihood-based training and model comparison.

Why not just run dense multi-GPU BBMM? Its cost is quadratic per iteration and compute-bound, so partitioning it does not change memory behavior. We include a cache-sized tiling of dense BBMM to confirm that no super-linear window appears there. That result would explain Wang et al.'s near-linear scaling rather than contradict it.

Why not just run the same block-decomposed solver on one large device? This is the most serious alternative, because much of the super-linearity may be algorithmic. The decoupled $S_{\text{sub}}$-versus-$P$ design settles it directly. If the single-device ablation captures most of the gain, the contribution is recast as a single-device algorithm, with distribution needed only for memory capacity, and we will say so.

Why not just use a sparse direct solver? Lueg et al. found that MKL PARDISO scaled poorly with thread count while domain-decomposed PCG scaled to 1,024 ranks. Kernel matrices in three dimensions, however, can have milder fill than their optimization systems. We therefore include a sparse Cholesky baseline up to the largest size that fits in memory.

Proposed Experiments

The primary benchmark is gp2Scale's 10-million-point 3D temperature data. We run strong-scaling sweeps on both a CPU cluster, following Lueg et al.'s Bridges-2-style MPI setting, and a GPU cluster. We report parallel efficiency against $P$ at fixed $S_{\text{sub}}$ and against $S_{\text{sub}}$ at fixed $P$, alongside hardware counters for cache misses. The decisive hardware check is whether efficiency above 1 coincides with the model's predicted cache-fit point. It should appear in the fixed-$S_{\text{sub}}$ sweep, which excludes the algorithmic effect, and it should vanish when leaf sizes are deliberately set just above cache capacity.

The decisive log-determinant check compares the variance of the $\log|K_\theta|$ estimate, and the number of L-BFGS iterations, against the single-device preconditioned estimator on the Elevators through 3DRoad range used by the preconditioning paper. That paper reports up to 12× speedup; its per-dataset figures are not in the file.

Statistical fidelity is measured by RMSE, CRPS, and calibration coverage on topography, California housing, 3DRoad, Kin40k, and HouseElectric. Song (90-dimensional) serves as a negative control, where we expect compact support to become nearly dense and the method to lose to BBMM. The upper edge of the window is mapped by pushing $P$ until the interface PCG's allreduces dominate. We then report the points-per-worker breaking point, the Gaussian process analogue of Offermans et al.'s DOF-per-core thresholds.