Exact Lazy Batch Selection for Gaussian-Process Screening of Million-Candidate Pools

Bayesian optimization picks the next experiments to run by fitting a Gaussian process to past results. A Gaussian process (GP) is a probabilistic regression model that gives both a prediction and an uncertainty for every untested point. In large-library screening, such as choosing which molecules to dock out of millions, the step that limits throughput is often not fitting the model. It is scoring every candidate in the pool. The predicted mean is cheap: one dot product per candidate. The predicted uncertainty is expensive: with $n$ past observations it needs a triangular solve of cost $O(n^2)$ per candidate. A batch for $q$ parallel workers multiplies that cost again, because each chosen point lowers the uncertainty of its neighbours. With $n = 10^4$ observations and two million candidates, exact uncertainty for the whole pool is out of reach. Practitioners therefore approximate the model, subsample the pool, or drop the GP altogether.

We propose to skip most of those uncertainty computations without changing what the algorithm selects. The key fact is that, with hyperparameters held fixed, conditioning on more data never increases GP posterior variance. A stale variance is therefore always a valid upper bound. A cheap geometric bound, the kernel distance from a candidate to its nearest already-observed point, gives a second valid upper bound that survives hyperparameter refits. Put these bounds in a priority queue, compute exact variance only for candidates whose optimistic score could still enter the batch, and the result is the same batch that brute-force greedy selection would produce, at a fraction of the cost. This is the lazy, triangle-inequality-pruned seeding idea of Exact Acceleration of K-Means++ and K-Means||, carried over from Euclidean distances to GP posterior variance.

Core Claim

Many standard batch rules are monotone in the posterior standard deviation $\sigma$ at a fixed posterior mean $\mu$. These include upper confidence bound with pure-exploration filling (UCB-PE) and expected improvement under the "kriging believer" heuristic, which pretends pending batch points returned their predicted mean so that $\mu$ stays put and only $\sigma$ shrinks. For all such rules, exact greedy batch construction over a discrete pool can be done lazily. Two bounds make this possible. The first comes from monotone conditioning:

$$\sigma^2_{t+1}(x) \le \sigma^2_t(x),$$

which holds for any candidate $x$ when the observation set at round $t+1$ contains that of round $t$, whether the new points are real or hallucinated batch members. The second is geometric. Take a stationary kernel with output scale $s^2$, noise variance $\tau^2$, and kernel distance $d_k(x,x')^2 = k(x,x) - 2k(x,x') + k(x',x')$. Conditioning on the single nearest observation $x_j$ already gives

$$\sigma^2(x) \le d_k(x, x_j)^2 + \tau^2.$$

This follows from $s^2 - k^2/(s^2+\tau^2) \le (s^2-k)(s^2+k)/s^2 + \tau^2 \le 2(s^2-k) + \tau^2$.

For an isotropic kernel, $d_k$ is a fixed monotone function of the input-space distance $r(x)$ to the nearest observed point. A nearest-observation index built once with triangle-inequality pivots therefore gives fresh $O(1)$ bounds after every lengthscale refit. Refits are exactly the moment when stale bounds become invalid. For the Tanimoto kernel on molecular fingerprints, the Jaccard distance is a metric and the same construction applies.

What is new here is not lazy evaluation as a general idea. It is three things together: showing that GP batch acquisition has the monotone structure lazy evaluation needs; supplying a refit-proof geometric bound so laziness survives hyperparameter learning; and measuring whether the combination makes exact GP uncertainty affordable at million-candidate scale.

Relation to Prior Work

Three papers motivate the gap. MEMES screens libraries of up to 96 million molecules with expected improvement on molecular embeddings. It reports that acquisition over the full pool is a bottleneck and handles scale with deep GPs, not exact inference. Approximation-Aware Bayesian Optimization shows that sparse variational GPs waste capacity on low-utility regions and moves inducing points toward promising areas. Our approach keeps the exact posterior and saves compute only where the acquisition rule provably does not care. Batched Gaussian Process Bandit Optimization via Determinantal Point Processes shows that UCB-PE equals greedy maximization of a determinantal point process (DPP-MAX), a diversity-favouring selection rule built from the posterior covariance. Our accelerated object is therefore a known, analysed batch rule. That paper argues sampling (DPP-SAMPLE) beats greedy maximization but pays a Markov chain Monte Carlo cost on large pools. We accelerate the greedy variant only and treat DPP-SAMPLE as a quality comparison, not a target.

Three papers supply the method and its limits. Raff's seeding work supplies lazy "dirty" priority-queue updates and triangle-inequality skip tests. It also warns that pruning loosens above roughly 1024 dimensions, which constrains how fingerprints and embeddings are represented. Large scale K-means clustering using GPUs shows that pruning more than 90% of points beat brute-force RAPIDS on GPU by 1.5–2x. This is our evidence that pruning still pays on accelerators. Batch Bayesian Optimization via Local Penalization builds batches greedily with Lipschitz-based exclusion zones and re-optimizes the penalized acquisition each time. It is the batch rule a practitioner would otherwise use, and its penalized values are not monotone bounds of the kind we need.

Two greedy-acceleration papers are the contrast case. Sparse Greedy Gaussian Process Regression cuts the greedy scan by evaluating 59 random candidates, which lands in the top 5% with 95% probability. Efficient Greedy Coordinate Descent for Composite Problems maps greedy selection to approximate maximum inner product search and reports that recall degrades near the optimum. Both are approximate. Ours is exact. Its efficiency should improve, not degrade, as the variance surface flattens and the mean dominates the ranking.

Research Program

We will build a discrete-pool batch selector in three parts.

The first part is the exact mean pass. Each round computes $\mu(x)$ for all $N$ candidates at $O(Nn)$ cost on GPU.

The second part is the bound layer. Each candidate carries an upper bound on its variance: the minimum of its last exact variance (valid until the next hyperparameter refit) and the geometric nearest-observation bound. The geometric bound is maintained with pivot-based triangle-inequality filtering, in the style of Raff and of the joinable-table pivots in Efficient Joinable Table Discovery in Data Lakes, as new observations arrive.

The third part is the lazy queue. Candidates are ordered by their optimistic acquisition value, $\mu + \beta\,\sigma_{\text{ub}}$, or expected improvement evaluated at $\sigma_{\text{ub}}$; expected improvement increases in $\sigma$ at fixed $\mu$, so this is a valid upper bound. The top entry is popped, its exact variance is computed, and it is reinserted. When an exact value sits at the top, it is accepted, hallucinated into the posterior with a rank-one update, and the next slot begins. Earlier exact values stay valid as upper bounds within the batch.

On the analysis side, we will prove that the selector's output matches brute-force greedy selection, ties excepted. We will also characterise the number of exact evaluations in terms of how many candidates have $\mu(x) + \beta\,\sigma_{\text{ub}}(x)$ above the $q$-th best exact score. This quantity is measurable and shows directly when the method helps and when it does not.

The known breaking cases will be stated, not hidden. Automatic-relevance-determination kernels refit per-dimension lengthscales, which invalidates the precomputed geometric bound; we will test an anisotropic fallback that bounds through the smallest lengthscale. Thompson sampling is not monotone in $\sigma$, so it lies outside scope.

Baselines

The naive reference is brute-force greedy batch selection: exact mean and variance for all $N$ candidates at every batch slot, with no subsampling. It produces the same batch as our method, so the comparison is purely about compute. It will run on the same GPU, with the same Cholesky factor and the same batched triangular-solve kernels. We count a win as at least a 10x reduction in exact variance evaluations and a matching wall-clock gain, with byte-identical batches.

The strongest existing system for this regime is the MEMES pipeline MEMES. It reports recovering 90% of the top-1000 docking hits while docking 6% of the 96-million-molecule library; random sampling recovers about 5.5% at the same rate. We will not have the compute to dock 96 million molecules. We will therefore re-run the MEMES-style approximate-GP plus expected-improvement loop on Zinc-250K and Enamine HTS with the same featurization, oracle budget, batch size and acquisition wall-clock cap as our method. We count a win as top-k recovery at least as high under an equal or smaller selection wall-clock. Exact uncertainty should help most on narrow optima, where the file notes sparse models over-smooth.

The subsampling baseline evaluates a uniform random fraction of the pool each round, including the 59-candidate rule from Sparse Greedy Gaussian Process Regression, with the fraction tuned so its selection time equals ours. Local penalization Batch Bayesian Optimization via Local Penalization will run on the discrete pool as the standard batch rule. Asynchronous Thompson sampling in the style of Kandasamy et al., using random-feature posterior samples, will run as the batch-free alternative.

Two ablations isolate the ingredients. "Stale bound only" drops the geometric bound and must cold-start after every refit. "Geometric bound only" drops cross-round reuse. Their gap to the full method shows which ingredient carries the savings. No reported result was found on Lacuna for exact-versus-approximate acquisition cost on these pools, so the brute-force runs establish that reference ourselves.

Why not just…?

Why not just subsample the pool at random each round? For most of the pool this is the real threat, because a top-5% candidate is cheap to find. But on a two-million-molecule library, the top 5% is 100,000 molecules, and screening is scored on recovering the top-1000. Our experiment fixes selection time and compares top-1000 recovery over rounds. If subsampling matches exact greedy selection there, the exactness argument fails for this regime, and we will report that.

Why not just use a sparse or deep GP so each variance costs $O(m^2)$? That is what MEMES and Approximation-Aware Bayesian Optimization do, and it changes the posterior. The two approaches compose: the within-batch monotone bound holds for any fixed inducing set. We will run the lazy queue on top of a sparse variational GP as well, and report both whether the exact posterior improves hit recovery and whether laziness still saves work under the approximation.

Why not just use asynchronous Thompson sampling, which needs no batch construction? With random features, a posterior sample over $N$ candidates costs $O(N\cdot\text{features})$. That may be as cheap as our method, which makes it a genuine competitor. Its weakness, noted by Kathuria et al., is that nothing forces workers apart in synchronous batches. We will measure pairwise duplication within batches and top-k recovery against it at equal wall-clock. If it wins, our contribution narrows to settings that require deterministic, diverse batches.

Why not just brute-force on a GPU? Large scale K-means clustering using GPUs found pruning still beat RAPIDS by 1.5–2x, because memory and transfer, not arithmetic, set the limit. Variance evaluation is a heavier per-candidate cost than a distance, so the margin should be larger. The naive baseline above tests this directly.

Proposed Experiments

Correctness first. On Hartmann-6 and Branin-Hoo, each discretized to $10^6$ points, together with the FastXML tuning tasks from the DPP paper, we verify byte-identical batches against brute force at $q \in \{5, 10, 50, 200\}$. Since quality matches by construction, any regret gap would indicate a bug.

Scale next. On Zinc-250K and Enamine HTS (about 2.1 million compounds), we score candidates with cheap Guacamol objectives such as Osimertinib MPO and Fexofenadine MPO, so the whole pool can be ground-truthed. For each, we report the fraction of exact variance evaluations, selection wall-clock, and top-1000 recovery over 50 rounds, with $n$ growing to $10^4$.

The decisive diagnostic plots the fraction of candidates refreshed per round against $\beta$, round index and representation dimension. Raff's degradation above roughly 1024 dimensions predicts that the geometric bound weakens on 2048-bit fingerprints. We will therefore compare raw fingerprints, Tanimoto distance, and a low-dimensional embedding such as CDDD, as used in MEMES.

The method is worth pursuing if, at $n = 10^4$ and two million candidates, fewer than 5% of candidates need exact variance per batch, and if exact greedy UCB-PE matches or beats both the approximate-GP pipeline and Thompson sampling on top-1000 recovery at equal selection time. If refits erase the savings, or random subsampling matches recovery, the experiments will show that clearly.