A Gaussian process (GP) is a regression model that returns a prediction together with a calibrated error bar. Its exact form needs time that grows with the cube of the number of training points. For about a decade the standard response has been to spread the work over many machines. That can mean splitting the data among independent "experts" whose predictions are then merged, running variational training through a parameter server, or running iterative linear solvers across several GPUs. Distributed computing charges a tax, though: startup cost, synchronization, and moving results between machines. Outside the GP literature this tax is well documented. Hadoop jobs have a fixed scheduling floor that makes them slower than serial code on small and medium inputs (Performance Comparison Between Hama and Hadoop, The application of the Hadoop software framework in Bioinformatics programs). Retrieval and ant-colony solvers show a measurable crossover problem size below which serial code wins (The Relationship between Architectures and Example-Retrieval Times, Solving Traveling Salesman Problems with Ant Colony Optimization Algorithms in Sequential and Parallel Computing Environments: A Normalized Comparison). The GP literature has never located this crossover. Recent evidence also suggests it may sit much further out than people assume: a nearest-neighbor GP trains on 1.6 million points in about 30 seconds on a laptop and beats distributed GPs in accuracy (Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression).
This note proposes to measure and predict the parallelization efficiency threshold for GP regression. The threshold is defined as the dataset size, input dimension, and network latency at which a distributed GP reaches a given test accuracy faster than the best single-machine method. The central claim is that the threshold must be accuracy-matched: distributed GP methods change the model, not only the runtime. We further claim that a three-parameter hardware cost model, fitted from microbenchmarks, can predict both the crossover and the best partitioning, including the aggregation-tree depth that Distributed Gaussian Processes explicitly leaves open.
Core Claim
Every distributed GP paper in the file reports speedup against its own centralized version. A Distributed Variational Inference Framework for Unifying Parallel Sparse Gaussian Process Regression Models reports 116 versus 836 seconds for dPIC on AIMPEAK. Asynchronous Distributed Variational Gaussian Process for Regression shows nearly constant per-iteration time as cores are added. Neither comparison answers the practitioner's question, which is whether to distribute at all given the strongest single-node alternative.
We hypothesize the following. On low-dimensional data such as flight delays or household power, nearest-neighbor GP prediction dominates committee and variational methods on accuracy-matched wall-clock time up to the largest sizes in the file. In that regime the threshold may not exist at all. Distribution starts to pay only in two cases. The first is high input dimension, where nearest-neighbor search degrades. The second is the high-accuracy end of the curve, where exact inference (Exact Gaussian Processes on a Million Data Points) keeps improving while approximations stop. Finding where these regions begin, and predicting them without running every method, is the contribution.
Cost Model
For a method run on $P$ workers arranged in an aggregation tree of depth $h$, we model the time to reach target accuracy as
$$T(n, d, P, h) = T_0 + I \left( h\,\alpha + \frac{s(P,h)}{\beta} \right) + \frac{C(n/P, d)}{\gamma},$$
The symbols are defined as follows:
- $T_0$ is fixed startup cost.
- $I$ is the number of synchronization rounds needed to reach the accuracy target.
- $\alpha$ is per-hop network latency.
- $s(P,h)$ is the number of bytes moved per round.
- $\beta$ is bandwidth.
- $C(n/P, d)$ is the local floating-point work for $n/P$ points in dimension $d$.
- $\gamma$ is the sustained compute rate.
The form of $C$ follows from each method's known complexity: cubic in local size for expert-committee methods, $nm^2$ for inducing-point methods, and squared in $n$ per iteration for conjugate gradients. We fit $\alpha$, $\beta$ and $\gamma$ once per hardware setup from ping, all-reduce and matrix-multiply microbenchmarks. $I$ is the only quantity tied to the accuracy target, so we estimate it from a short run on a subsample.
The threshold $n^*$ is the smallest $n$ at which $\min_{P,h} T$ for a distributed method falls below the single-node time $T_{\text{local}}(n,d)$ at equal test error. The model predicts a finite optimal tree depth for committee methods, because the latency term grows with $h$ while the load on the central aggregator falls. This is exactly the trade-off Distributed Gaussian Processes describes but does not resolve.
Research Program
We will re-implement or run, under one harness, the main methods in the file.
- Nearest-neighbor GP: GPnn as the local-prediction reference (Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression).
- Sparse variational GP: a single-node inducing-point model.
- Exact inference: multi-GPU conjugate gradients (Exact Gaussian Processes on a Million Data Points).
- Expert committee: the robust Bayesian committee machine (rBCM), which combines independent experts weighted by how much each reduces uncertainty relative to the prior (Distributed Gaussian Processes), run with both star and tree topologies.
- Synchronous variational: dPIC/dLMA, which aggregates local gradient summaries at a master node (A Distributed Variational Inference Framework for Unifying Parallel Sparse Gaussian Process Regression Models).
- Asynchronous variational: ADVGP, which pushes stale gradients to a parameter server under a delay bound $\tau$ (Asynchronous Distributed Variational Gaussian Process for Regression).
We deliberately exclude gp2Scale (gp2Scale: A Class of Compactly Supported Non-Stationary Kernels and Distributed Computing for Exact Gaussian Processes on 10 Million Data Points) from the main sweep. Its block-MCMC pipeline answers a different question, full hyperparameter posteriors, so we treat it as a qualitative reference point.
Each method is run on three hardware tiers:
- a single CPU laptop-class machine;
- a single 8-GPU box;
- a small multi-node CPU/GPU cluster in which we inject controlled latency between nodes.
The injected latency lets us sweep $\alpha$ independently of everything else. For each dataset we subsample $n$ over roughly two orders of magnitude and record full curves of test error against wall-clock time, including startup. Crossovers are then read off at fixed targets for root mean squared error (RMSE) and negative log likelihood (NLL). NLL is reported after the additive-noise recalibration step GPnn recommends, applied to all methods so that calibration tricks do not decide the comparison.
We then validate the cost model. It is fitted on some datasets and hardware tiers, and we check whether it predicts $n^*$, the optimal $P$, and the optimal rBCM depth on the ones held out.
Baselines
The do-nothing reference is subset-of-data: fit an exact GP on as many random points as fit in a fixed single-machine time budget. Distributed Gaussian Processes shows rBCM beats it on Kin40K but reports no numeric value. We run it at matched wall-clock time, and any distributed method that fails to beat it at equal time has no case at all.
The strongest single-node competitor is GPnn. It is the method most likely to make distribution pointless: the file reports it trains on 1.6 million HouseElectric points in "approximately 30 seconds on a basic laptop" and beats distributed GPs in MSE and NLL on UCI data (Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression). The file gives no absolute GPnn RMSE, so we must reproduce one. GPnn gets the same neighbor count and hyperparameter-subset tuning budget, a grid over the number of neighbors and the subset size, as the distributed methods get over $P$ and inducing-point count. Beating it means reaching its converged RMSE and calibrated NLL in less total wall-clock time, or reaching an error it cannot reach at all.
The strongest accuracy baseline is exact conjugate-gradient inference. On Kin40K it reports RMSE 0.099 against 0.273 for an inducing-point model, and it trains on 1.3 million HouseElectric points in "less than 2 hours" on 8 V100 GPUs (Exact Gaussian Processes on a Million Data Points). We run it with its published 10,000-point pretraining warm start. That start time is counted, not hidden.
For the distributed methods, the reference numbers are:
- rBCM: RMSE 35.5 on the roughly 5-million-point flight subset (Distributed Gaussian Processes).
- ADVGP: RMSE 309.7 on NYC Taxi, against 556.3 for mean prediction (Asynchronous Distributed Variational Gaussian Process for Regression).
We reproduce these first to confirm our implementations before any sweep.
The key ablation isolates the cost model's contribution. The model-chosen $(P, h)$ is compared with two alternatives: the default settings in each paper, and an oracle found by exhaustive grid search. The model is useful only if it lands within 10–20% of the oracle's time at a small fraction of the search cost.
Why not just…?
Why not just always use GPnn on one machine? This is the real threat, and the study is built so it can win. If GPnn is faster at matched accuracy on every dataset and every $n$ we test, that is a publishable negative result. It would tell practitioners to stop distributing low-dimensional GP regression. The file gives a reason to expect it breaks somewhere: nearest-neighbor indexing degrades with dimension. PUMADYN32NM (32 inputs) and Song (90 inputs) are included to test exactly this. Exact inference also keeps improving where approximations stall, as shown on Song in Exact Gaussian Processes on a Million Data Points, so very tight accuracy targets are a second place where distribution could win.
Why not just use a single-node sparse inducing-point model? It is cheap, but the file shows it plateaus: 0.273 against 0.099 RMSE on Kin40K. Approximation-Aware Bayesian Optimization adds that such models smooth away sharp local structure. It stays in the sweep, so its accuracy-matched curve will show directly whether it ever sets the frontier.
Why not just grid-search worker count empirically for each job? That works if one can afford it, but each grid point is a full distributed run, which is precisely the expense in question. The ablation above measures how much of the oracle's advantage the cheap microbenchmark model recovers. If a two- or three-point empirical search matches it, we will report that and treat the cost model as explanatory rather than practical.
Decisive Checks
The benchmarks are Kin40K, SARCOS, PUMADYN32NM, Protein, Song, HouseElectric, the US flight dataset, and a NYC Taxi subsample. The study succeeds if three things hold.
First, it produces a reproducible map of $n^*$ against input dimension and injected latency for each distributed method, measured against GPnn and exact inference at matched RMSE and NLL.
Second, the fitted cost model predicts held-out crossovers within a factor of two in $n$.
Third, the predicted optimal rBCM tree depth matches the empirically fastest depth on the cluster tier as latency is swept.
The central hypothesis is falsified in either of two ways. It fails if distributed methods beat GPnn at matched accuracy on the low-dimensional flight and HouseElectric data at moderate $n$. It also fails if crossovers turn out to depend on factors the three-parameter model cannot capture, such as straggler variance, in which case the model needs a straggler term, as coded-computing work like Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers suggests.
References
- Performance Comparison Between Hama and Hadoop
- The application of the Hadoop software framework in Bioinformatics programs
- The Relationship between Architectures and Example-Retrieval Times
- Solving Traveling Salesman Problems with Ant Colony Optimization Algorithms in Sequential and Parallel Computing Environments: A Normalized Comparison
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Distributed Gaussian Processes
- A Distributed Variational Inference Framework for Unifying Parallel Sparse Gaussian Process Regression Models
- Asynchronous Distributed Variational Gaussian Process for Regression
- Exact Gaussian Processes on a Million Data Points
- gp2Scale: A Class of Compactly Supported Non-Stationary Kernels and Distributed Computing for Exact Gaussian Processes on 10 Million Data Points
- Approximation-Aware Bayesian Optimization
- Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers