Paper deep dive
Work While They Sleep: Exploiting Evaluation Latency for Fully Bayesian Optimization
Gustavo Sutter, Alejandro Comas-Leon, David Holzmüller, Hao Wang, Luis Ricardez-Sandoval, Pascal Poupart, Agustinus Kristiadi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/12/2026, 5:51:25 AM
Summary
The paper introduces ELF-BO (Evaluation Latency Fully Bayesian Optimization), an algorithm that reduces decision latency in fully Bayesian optimization by performing MCMC sampling of hyperparameter posteriors during the expensive objective function evaluation phase. This approach allows for accurate uncertainty quantification without the typical computational overhead associated with fully Bayesian methods, making them practical for real-world applications with high evaluation costs.
Entities (7)
Relation Signals (6)
ELF-BO → isa → Fully Bayesian Optimization
confidence 95% · In this work, we propose ELF-BO... allowing for fully Bayesian optimization
Gaussian Processes → isusedin → Bayesian optimization
confidence 95% · Standard BO methods utilize Gaussian processes (Rasmussen and Williams, 2006, GP;) as surrogate models
ELF-BO → reduces → Decision Latency
confidence 92% · ELF-BO makes fully Bayesian optimization practical... while only incurring decision latency on par with or better than standard BO.
Gustavo Sutter → affiliatedwith → Vector Institute
confidence 90% · Gustavo Sutter ... Affiliation: Vector Institute, Toronto, ON, Canada
Agustinus Kristiadi → affiliatedwith → Vector Institute
confidence 90% · Agustinus Kristiadi ... Affiliation: Vector Institute, Toronto, ON, Canada
ELF-BO → uses → MCMC
confidence 90% · This is done by sampling from the hyperparameter posterior... using Markov chain Monte Carlo (MCMC) methods
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Black-box optimization problems are ubiquitous across science and engineering, often dealing with expensive objective functions. This objective latency has two consequences during optimization: (i) the objective evaluation dominates execution time, and (ii) sample-efficient algorithms are crucial to accelerate development and avoid wasting resources. Bayesian optimization (BO) methods are the \textit{de facto} choice of planners for suggesting the next point to try. Standard BO fits the surrogate model's hyperparameters with a point estimate. Alternatively, a fully Bayesian approach uses model averaging to account for uncertainty over the hyperparameters, leading to better uncertainty estimates---useful in the low-data regime that is pervasive in BO. However, it is often prohibitively expensive and thus rarely used. In this work, we propose ELF-BO, an algorithm that uses the objective evaluation latency to headstart the computation of the next suggestion, allowing for fully Bayesian optimization without incurring substantial decision-time costs. This is done by sampling from the hyperparameter posterior \emph{while} the objective is being evaluated, only requiring reweighting of the samples once the objective value is observed. Across synthetic functions and real-world applications, we show that ELF-BO matches the performance of fully Bayesian methods while only incurring decision latency on par with or better than standard BO. Thus, ELF-BO makes fully Bayesian optimization practical in real-world use cases.
Tags
Links
- Source: https://arxiv.org/abs/2610.08969v2
- Canonical: https://arxiv.org/abs/2610.08969v2
Trouble viewing inline? Open PDF directly →
Full Text
50,904 characters extracted from source content.
Expand or collapse full text
Work While They Sleep: Exploiting Evaluation Latency for Fully Bayesian Optimization Gustavo Sutter †thanks: Equal contribution. Affiliation: Vector Institute, Toronto, ON, Canada Alejandro Comas-Leon11footnotemark: 1 Affiliation: Vector Institute, Toronto, ON, Canada David Holzmüller Affiliation: SODA Team, INRIA Saclay, Palaiseau, France Hao Wang Affiliation: Department of Chemical Engineering, University of Waterloo, Waterloo, ON, Canada Luis Ricardez-Sandoval Affiliation: Department of Chemical Engineering, University of Waterloo, Waterloo, ON, Canada Affiliation: Waterloo Institute for Nanotechnology, University of Waterloo, Waterloo, ON, Canada Pascal Poupart Affiliation: Vector Institute, Toronto, ON, Canada Agustinus Kristiadi Affiliation: Vector Institute, Toronto, ON, Canada Affiliation: Department of Computer Science, Western University, London, ON, Canada [4pt] Cheriton School of Computer Science University of Waterloo Waterloo ON Canada Abstract Black-box optimization problems are ubiquitous across science and engineering, often dealing with expensive objective functions. This objective latency has two consequences during optimization: (i) the objective evaluation dominates execution time, and (i) sample-efficient algorithms are crucial to accelerate development and avoid wasting resources. Bayesian optimization (BO) methods are the de facto choice of planners for suggesting the next point to try. Standard BO fits the surrogate model’s hyperparameters with a point estimate. Alternatively, a fully Bayesian approach uses model averaging to account for uncertainty over the hyperparameters, leading to better uncertainty estimates—useful in the low-data regime that is pervasive in BO. However, it is often prohibitively expensive and thus rarely used. In this work, we propose ELF-BO, an algorithm that uses the objective evaluation latency to headstart the computation of the next suggestion, allowing for fully Bayesian optimization without incurring substantial decision-time costs. This is done by sampling from the hyperparameter posterior while the objective is being evaluated, only requiring reweighting of the samples once the objective value is observed. Across synthetic functions and real-world applications, we show that ELF-BO matches the performance of fully Bayesian methods while only incurring decision latency on par with or better than standard BO. Thus, ELF-BO makes fully Bayesian optimization practical in real-world use cases. 1 Introduction Bayesian optimization (Močkus, 1975, BO;) often acts as a planner (suggesting the next query point to evaluate) for optimizing black-box functions commonly encountered in science (Greenaway et al., 2023; Muthyala et al., 2026) and engineering (Lam et al., 2018; Ament et al., 2023b). Across domains, most applications of BO deal with expensive objective functions, a property that motivates the development of sample-efficient methods. The inherent high evaluation latency makes it the main bottleneck in the optimization run. Meanwhile, after suggesting a query location, the planner waits idly for the evaluation results before continuing. Crucially, expensive function evaluations also limit applications to cases with restricted data availability, both in initial dataset size and in the number of evaluations allowed in the optimization loop (Jones et al., 1998). The former increases the difficulty of achieving the latter, as a misspecified model can lead to suboptimal queries that waste precious evaluation budget. Standard BO methods utilize Gaussian processes (Rasmussen and Williams, 2006, GP;) as surrogate models and use a point estimate approach—either maximum likelihood estimation (MLE) or maximum a posteriori (MAP)—to find the GP’s hyperparameters (e.g., lengthscale, output scale, deep-kernel parameters, and noise variance). However, relying on a single estimate of the hyperparameters can drastically underestimate the uncertainty over the true hyperparameters, and therefore the uncertainty over the objective values (De Ath et al., 2021b). Importantly, this is a bigger problem in the low-data regimes where well-calibrated models are required for sample-efficient decision-making. The same trade-off arises beyond GPs: the high computational overhead of Bayesian neural networks (Li et al., 2024; Kristiadi et al., 2024, BNNs;) makes them similarly expensive at decision time. ⋯·s⋯·sWorker⋯·s⋯·sPlannerTimeStandard MCMC-Based BO⋯·s⋯·sWorker⋯·s⋯·sPlannerTimeELF-BO (Ours)Function evaluationMCMC samplingAcquisition optimizationSample reweighting Figure 1: Where the time goes in a sequential BO campaign. Each timeline shows the worker (the experiment or simulator evaluating f) and the planner (the BO algorithm); thick segments denote busy time. Left: In standard fully Bayesian BO, the two alternate: the planner waits while f is evaluated, and the worker waits while the planner runs MCMC and optimizes the acquisition function. Right: ELF-BO runs MCMC while f is being evaluated, so once yty_t arrives, only a cheap importance reweighting and the acquisition optimization remain, greatly reducing decision latency. An alternative to point estimates is the use of a fully Bayesian optimization (Osborne et al., 2009; Benassi et al., 2011), in which the hyperparameters are averaged out according to their posterior distribution. In practice, this is done by using Markov chain Monte Carlo (Neal, 2011, MCMC;) methods to obtain samples from the posterior distribution and computing the average of the acquisition function over the samples. As usual in Bayesian inference, the price is paid with more computation and time, mostly due to the expensive MCMC sampling, rendering fully Bayesian methods prohibitively expensive for many practitioners. This expensive decision-making step between objective function evaluations is undesirable in various applications; e.g., in automated materials discovery, machine time is valuable, so minimal downtime is desired (MacLeod et al., 2020). In this work, we show that most of the expensive steps needed in a fully Bayesian approach can be performed while the expensive objective function is being evaluated. We propose Evaluation Latency Fully Bayesian Optimization (ELF-BO), which uses the BO planner’s otherwise idle time to reduce the footprint of fully Bayesian optimization after the evaluation result becomes available—see Fig. 1. This is accomplished by showing that an expectation over the next hyperparameter posterior can be computed using a weighted expectation with the posterior of the hyperparameters at the current step. These weights are proportional to the posterior predictive density of the pending evaluation results—thus only the weights are computed once the evaluation is done. Since this identity relies only on Bayes’ rule, ELF-BO is not tied to GPs and can be applied to BNNs. In this work, however, we focus on GPs due to their prevalence and simplicity in BO. We evaluate ELF-BO on 15 standard benchmarks ranging from 2 to 10 dimensions and on three real-world experimental datasets. Across these problems, ELF-BO matches the optimization performance of naïve MCMC-based fully Bayesian BO after every observation, while its decision latency—the time the experiment sits idle waiting for the next query—stays close to that of point-estimate BO. The latter amounts to a decision latency roughly 10× lower than standard fully Bayesian BO with a Matérn kernel, 70–110× lower with a deep kernel, and more than two orders of magnitude lower as the dataset grows. We further use the effective sample size of the importance weights to diagnose when reweighting is reliable, and characterize the regimes in which ELF-BO yields the largest gains. Altogether, ELF-BO makes MCMC-based fully Bayesian BO practical in real-world scenarios—the more expensive the function evaluation, the more calibrated the planner will be, without high compute overhead. 2 Preliminaries We consider the maximization problem ∗∈argmax∈f() x_*∈ _ x f( x) where f:→ℝf:X is an expensive black-box objective function that can only be accessed via noisy observations yi=f(i)+ϵiy_i=f( x_i)+ _i, with ϵi∼(0,σn2) _i (0, _n^2). Bayesian optimization (BO) provides a principled solution to this problem grounded in Bayesian decision theory. The key components of BO are: a surrogate model p(f∣t)p(f _t) and an acquisition function α(,t)α( x;D_t), where t=(i,yi)i=1tD_t=\( x_i,y_i)\_i=1^t is the set of observations of the objective function up to the current time step t∈1,…,Tt∈\1,…,T\. The surrogate models the current belief over the objective function given the data observed so far, which the acquisition function then uses to score the value of querying each point next. The next query is chosen as t+1∈argmax∈α(,t) x_t+1∈ _ x α( x;D_t), the objective is evaluated at t+1 x_t+1, and the procedure repeats until the evaluation budget is exhausted. 2.1 Gaussian Processes The standard surrogate choice for BO is the Gaussian process. A Gaussian process (μ(),k())GP(μ^( θ),k^( θ)) is a distribution over functions fully characterized by its prior mean function μ():→ℝμ^( θ):X and its covariance function k():×→ℝk^( θ):X×X , where θ collects all hyperparameters of the mean and covariance functions, together with the observation noise variance σn2 _n^2. Conditioned on an observation dataset t=(i,yi)i=1tD_t=\( x_i,y_i)\_i=1^t and on the hyperparameters θ, the posterior distribution over function values is also a GP, with posterior mean and covariance given by μt()() μ^( θ)_t( x) =μ()()+κ()()⊤(()+σn2)−1(t−μ()(t)) =μ^( θ)( x)+κ^( θ)( x) ( K^( θ)+ _n^2 I)^-1( y_t-μ^( θ)( X_t)) (1) kt()(,′) k^( θ)_t( x, x ) =k()(,′)−κ()()⊤(()+σn2)−1κ()(′), =k^( θ)( x, x )-κ^( θ)( x) ( K^( θ)+ _n^2 I)^-1κ^( θ)( x ), (2) where ()=[k()(i,j)]i=1,j=1t,t∈ℝt×t K^( θ)=[k^( θ)( x_i, x_j)]_i=1,j=1^t,t ^t× t is the observation covariance matrix, κ()()=[k()(,i)]i=1t∈ℝtκ^( θ)( x)=[k^( θ)( x, x_i)]_i=1^t ^t is the vector of cross-covariances, t=[y1,…,yt]∈ℝt y_t=[y_1,…,y_t] ^t collects the observed objective values, and t X_t collects all observed points. Defining σt2()():=kt()(,)σ^2( θ)_t( x):=k^( θ)_t( x, x)\ , the marginal posterior at any point x is p(f()∣t,)=(f()∣μt()(),σt2()())p(f( x) _t, θ)=N(f( x) μ^( θ)_t( x), _t^2( θ)( x)). We emphasize that these expressions are conditional on θ; recovering the surrogate p(f∣t)p(f _t) introduced above requires marginalizing the hyperparameters out, which we discuss in Section 2.2. 2.2 Model Averaging The posterior in Section 2.1 is conditional on a particular setting of hyperparameters θ; thus, following the prescription of Bayesian inference, we should marginalize out our uncertainty over it, calculating p(f∣t)=∫p(f∣t,)p(∣t)p(f _t)= p(f _t, θ)p( θ _t)d θ. The problem, however, is that such an integral is intractable. The hyperparameter posterior p(∣t)∝p(t∣)p()p( θ _t) p(D_t θ)\,p( θ), given a prior p()p( θ) and the GP marginal likelihood, is not Gaussian, since θ enters the likelihood nonlinearly through the kernel matrix, its inverse, and its determinant; moreover, its normalizing constant has no closed form. As a consequence, practitioners rely on a point estimate θ obtained via maximum likelihood or maximum a posteriori. Such practice is the standard in BO, and is equivalent to approximating p(∣t)p( θ _t) with δ(−^)δ( θ- θ). Unfortunately, this discards all uncertainty about θ, which is especially bad in low-data regimes prevalent in BO. Monte Carlo (MC) methods offer a solution to this problem, allowing us to approximate the intractable integral as p(f∣t)≈1/M∑m=1M(f∣μt(m),kt(m))p(f _t)≈ 1/M _m=1^MGP(f _t^( θ_m),k_t^( θ_m)), where (m)m=1M∼p(∣t)\ θ^(m)\_m=1^M p( θ _t). Different Markov chain Monte Carlo (MCMC) algorithms can be used to generate the samples, such as slice sampling (Neal, 2003; Murray and Adams, 2010) or Hamiltonian Monte Carlo (Duane et al., 1987; Neal, 2011) and its adaptive variant NUTS (Hoffman and Gelman, 2014). Under this mixture surrogate, the marginal acquisition function becomes the corresponding mixture of per-sample acquisitions, α(,t)=p(∣t)[α(,t,)]≈1M∑m=1Mα(,t,(m)),α( x;D_t)=E_p( θ _t)[α( x;D_t, θ)]≈ 1M _m=1^Mα( x;D_t, θ^(m)), (3) provided α is linear in the predictive distribution, so that the marginalization over θ and the expectation over function values commute. This holds for expected improvement (Jones et al., 1998, EI;); for its numerically stable variant Log-EI (Ament et al., 2023a), which we use in this work, we average in EI space and take the logarithm of the result. Other acquisition functions can also be applied but may not reduce to a mixture of per-sample acquisitions; for instance, upper confidence bound (Auer, 2002; Srinivas et al., 2010) is instead computed from the mean and variance of the mixture. Figure 2: Overview of ELF-BO. Fully Bayesian BO marginalizes the acquisition function over the GP hyperparameters θ, which requires MCMC after every new observation. We instead run it while the objective is still being evaluated. Left: (I) with the candidate t x_t dispatched and its value yty_t still pending, we sample (m)\ θ^(m)\ from the posterior given the data collected so far, p(∣t−1)p( θ _t-1), which is already available. Each sample gives a different GP fit, and hence a different posterior at t x_t. Right: (I) when yty_t arrives, each sample is reweighted by how well it predicted it, w(m)∝p(yt∣t−1,t,(m))w^(m) p(y_t _t-1, x_t, θ^(m)), and (I) the per-sample acquisition functions α(,t,(m))α( x;D_t, θ^(m)) are combined into the marginal acquisition α(,t)α( x;D_t) used to pick the next candidate. 3 Evaluation Latency Fully Bayesian Optimization Consider a dataset t−1D_t-1 has been observed, a point t x_t was just dispatched for evaluation, and yty_t is pending. Our goal is to start the computations to generate the suggestion as follows: t+1=argmax∈∼p(∣t)[α(,t,)], x_t+1= _ x∈XE_ θ p( θ _t)[α( x;D_t, θ)], (4) where t=t−1∪(t,yt)D_t=D_t-1∪\( x_t,y_t)\ and θ are the GP hyperparameters. The obvious challenge is that yty_t, and consequently tD_t, are not known yet, so we would have to wait for it to run MCMC to obtain samples (m)m=1M\ θ^(m)\_m=1^M needed to compute the acquisition. The central idea of ELF-BO is that we can use the objective evaluation time to obtain samples (m)m=1M\ θ^(m)\_m=1^M from the posterior of the previous step p(∣t−1)p( θ _t-1) and use a reweighted average to compute (4), as illustrated in Fig. 2. The following proposition justifies this (proof in Appendix A): Proposition 1. Let φ be a function of θ and p(∣t)p( θ _t) be the posterior of hyperparameters at step t∈1,…,Tt∈\1,…,T\. Suppose that, for each t≥1t≥ 1, p(∣t)p( θ _t) is absolutely continuous w.r.t. p(∣t−1)p( θ _t-1). Then, for all t=1,…,Tt=1,…,T, ∼p(∣t)[φ()]=∼p(∣t−1)[w()φ()],wherew()=p(yt∣t−1,t,)p(yt∣t−1,t).E_ θ p( θ _t)[ ( θ)]=E_ θ p( θ _t-1)[w( θ)\, ( θ)], w( θ)= p(y_t _t-1, x_t, θ)p(y_t _t-1, x_t). Proof sketch. We use the importance sampling argument with the previous posterior as the proposal, so the importance weight is the ratio of the new posterior to the old one. By Bayes’ rule, this ratio is proportional to the likelihood of the new observation under the predictive distribution. ∎ The preceding result implies that we can start computing the expectation w.r.t. the posterior p(∣t)p( θ D_t) at the time step t before we receive the actual result for yty_t. In particular, we can already start sampling θ from p(∣t−1)p( θ D_t-1) of the previous time step t−1t-1. This is the expensive part of this expectation computation due to expensive MCMC. Indeed, once yty_t is obtained, only simple computation of w()w( θ), φ() ( θ), and averaging are required. Notice that Proposition 1 casts the expectation as importance sampling. We can thus use self-normalized importance sampling (Owen, 2013) to approximate ∼p(∣t)[α(,t,)]E_ θ p( θ _t)[α( x;D_t, θ)] using MCMC samples (m)m=1M\ θ^(m)\_m=1^M from p(∣t−1)p( θ _t-1) obtained before the evaluation is ready and reweighted after yty_t is observed: α(,t)≈∑m=1Mw(m)α(,t,(m)),w(m)=p(yt|t−1,t,(m))∑m′p(yt|t−1,t,(m′)).α( x;D_t)≈ _m=1^Mw^(m)\,α( x;D_t, θ^(m)), w^(m)= p(y_t|D_t-1, x_t, θ^(m)) _m p(y_t|D_t-1, x_t, θ^(m )). (5) This moves all MCMC computations to objective evaluation time. Once the objective value is observed, the acquisition function can be computed by reweighting the sampled hyperparameters based on how well each explains the observed value. Algorithm 1 summarizes the complete procedure. The reweighting strategy in ELF-BO may resemble sequential Monte Carlo (Chopin, 2002, SMC;), but in ELF-BO, a fresh set of samples is generated at each function evaluation, whereas SMC propagates a single population across all steps. Importantly, as in all importance sampling algorithms, the approximation is only reliable when the proposal p(∣t−1)p( θ _t-1) adequately covers the target p(∣t)p( θ _t). This can be monitored through the effective sample size of the self-normalizing weights: Meff=1/∑m=1M(w(m))2M_eff=1/ _m=1^M(w^(m))^2, which is available immediately after yty_t is observed. Values of MeffM_eff near M indicate that the value of yty_t had high probability under a variety of sampled hyperparameters, so the reweighted samples are representative, while low values indicate that yty_t was poorly explained by most of the samples, meaning a few samples dominate and the estimate will collapse to a single point. In Section 6 we analyze the effective sample size of the method across optimization steps. Algorithm 1 ELF-BO Initial dataset 0D_0, acquisition α, number of samples M, evaluation budget T Final dataset TD_T (m)m=1M←MCMC(p(∣0))\ θ^(m)\_m=1^M← MCMC(p( θ _0)) w(m)←1/Mw^(m)← 1/M for t=1,…,Tt=1,…,T do t=argmax∈∑mw(m)α(;t−1,(m)) x_t= _ x∈X _mw^(m)\,α( x;D_t-1, θ^(m)) h←(f,t)h← async 5.24994ptcompute(f, x_t) ⊳ evaluation of f(t)f( x_t) starts (m)m=1M←MCMC(p(∣t−1))\ θ^(m)\_m=1^M← MCMC(p( θ _t-1)) ⊳ Computed in parallel yt←_(h)y_t← await 5.24994ptget\_result(h) ⊳ evaluation of f(t)f( x_t) ends; obtain yty_t t=t−1∪(t,yt)D_t=D_t-1∪\( x_t,y_t)\ Compute w(m)\w^(m)\ as in (5) end for 3.1 Decision Latency Reduction We now analyze the decision latency, the wall-clock time elapsed between an observation arriving and the next query being proposed. This is relevant whenever idle equipment is costly, samples degrade while waiting, or an operator must dispatch the next experiment immediately, prevalent in automated scientific discovery (MacLeod et al., 2020). Let TfT_f denote the evaluation latency of the objective, TMCT_MC the time to draw M posterior samples, TαT_α the time to optimize the expected acquisition function, and TwT_w the time to compute the weights in (5). The decision latencies of standard fully Bayesian optimization and ELF-BO are given by LFBO=TMC+TαandLELF-BO=max(0,TMC−Tf)+Tw+Tα,L_FBO=T_MC+T_α L_ELF-BO= (0,\,T_MC-T_f)+T_w+T_α, respectively. Therefore, ELF-BO reduces decision latency by ΔL=LFBO−LELF-BO=min(TMC,Tf)−Tw. L=L_FBO-L_ELF-BO= (T_MC,T_f)-T_w. Note that in many real-world applications, Tf≥TMCT_f≥ T_MC, so the entire MCMC sampling procedure runs behind the objective evaluation. In such cases, the reweighting overhead is negligible in practice. We validate this analysis in Section 6. 4 Related Work Fully Bayesian Optimization Early work on GPs for global optimization considered a fully Bayesian approach to model hyperparameters (Osborne et al., 2009; Benassi et al., 2011). For instance, the seminal work of Snoek et al. (2012) demonstrated that an MCMC approach using slice sampling (Neal, 2003; Murray and Adams, 2010) outperforms point estimate-based methods. More recently, De Ath et al. (2021b) analyzed the benefits of fully Bayesian methods in BO, demonstrating that the MCMC approach is superior to MAP and variational inference methods when using EI and automatic relevance determination kernels. In the high-dimensional setting, SAASBO (Eriksson and Jankowiak, 2021) demonstrated the effectiveness of a fully Bayesian method with NUTS (Hoffman and Gelman, 2014) and priors that capture sparseness. Marginalizing out hyperparameters also provides a textbook solution to overfitting and is beneficial in the overparameterized regime of deep kernels (Ober et al., 2021). Beyond GP surrogates, fully Bayesian BO has also been performed with Bayesian neural networks (Li et al., 2024; Kristiadi et al., 2023; Kristiadi et al., 2024), which could equally benefit from ELF-BO. Asynchronous Batch Bayesian Optimization In this setting, multiple function evaluations run in parallel, and, as soon as one of the function evaluations finishes, a new query is launched without waiting for the pending results. Ginsbourger et al. (2011) was the first to work on this problem, using samples from the predictive posterior at the pending location to calculate the expected EI under different objective realizations. Alvi et al. (2019) proposed the use of local penalization around the pending point to reduce redundant selections, while De Ath et al. (2021a) used an ε -greedy algorithm to achieve the same goal. Alternatively, Kandasamy et al. (2018) proposed the use of Thompson Sampling (Thompson, 1933) in which a new sample of the posterior is taken after including only the newly revealed observation. More recently, Riegler et al. (2026) also demonstrated good results across acquisition functions without explicitly modelling the pending evaluations. On the related problem of stochastically delayed feedback, Verma et al. (2022) considered substituting the minimum function value for observations not yet revealed, a pessimistic version of the Kriging Believer method (Ginsbourger et al., 2010). ELF-BO complements this line of work by operating in settings with a single function evaluation at a time, a scenario often found in real-world applications. Figure 3: Standard benchmarks. Optimization performance of 15 synthetic functions. ELF-BO consistently follows Standard FBO on most functions, in many of which the fully Bayesian approaches achieve earlier convergence than MAP. Figure 4: Real-world tasks. Results on three experimental datasets from the Olympus suite. Top: best GAP found versus iteration, with standard error shaded. ELF-BO converges as quickly and reliably as Standard FBO, while MAP lags and varies more across seeds. Bottom: mean decision latency versus area under GAP curve, with error bars showing the standard error over all steps. By sampling while the objective is evaluated, ELF-BO has area under GAP close to Standard FBO’s at a latency similar to MAP’s, more than 10× lower than Standard FBO. 5 Experiments We now evaluate the empirical performance of ELF-BO. Our experiments aim to answer two questions: (i) Does reweighting hyperparameter samples drawn while the oracle is busy match the performance of running MCMC after each observation? (i) What is the wall-clock time effect of moving sampling under the objective evaluation? Baselines. We compare ELF-BO against random search and two baselines sharing the surrogate and acquisition function, so that differences between methods reflect only how the GP hyperparameters are handled and when the compute is spent. Random search samples uniformly from the domain. MAP fits the hyperparameters by maximizing the marginal likelihood plus log prior at every step, which is the default practice. Standard fully Bayesian optimization (Standard FBO) runs NUTS on the full dataset after each observation arrives; it is the fully Bayesian gold standard and pays the entire sampling cost between evaluations. ELF-BO runs the same NUTS sampler on the data available when a query is dispatched, while the oracle is evaluating, and when the observation arrives, it corrects the draws with a single importance reweighting. Setup. All methods use a GP with a constant mean, homoskedastic Gaussian likelihood, and ARD Matérn-5/2 kernel with output scale. The lengthscale prior is scaled by dimension as proposed by Hvarfner et al. (2024). For the sampling methods, we shift the distribution so that the MAP prior’s mode becomes the sampled prior’s median, and we reduce the scale from 3 3 to 1. Unless stated otherwise, Standard FBO and ELF-BO use NUTS (Hoffman and Gelman, 2014) with 4 vectorized chains, 512 warmup steps per chain, keeping a total of M samples after thinning by 16 (total of 16M16M samples generated after warmup). We use a dense mass matrix and a max tree depth of 6. Log-EI (Ament et al., 2023a) is used for all methods. For all experiments, we report the results across 10 trials, with standard errors indicated. All methods are implemented in BoTorch (Balandat et al., 2020). Further details on the experimental setup are presented in Appendix B. Metrics. As different objective functions have different scales, GAP (Barton, 1984) is used to evaluate performance: GAP=(yimax−y0max)/(y∗−y0max)GAP=(y_i^max-y_0^max)/(y_*-y_0^max), where yimaxy_i^max is the best observed value at the i-th iteration, y0maxy_0^max is the highest initial value, and y∗y_* is the optimal value. To evaluate the benefits of leveraging objective evaluation time, we also measure the decision latency of each algorithm. 5.1 Standard Benchmark Functions Following De Ath et al. (2021a), we use the 15 benchmark functions11 1 https://w.sfu.ca/~ssurjano/optimization.html ranging from d=2d=2 to d=10d=10: Branin, Eggholder, Goldstein–Price and Six-Hump Camel (d=2d=2); Hartmann (d=3,6d=3,6); Ackley and Michalewicz (d=5,10d=5,10); Styblinski–Tang (d=5,7,10d=5,7,10); and Rosenbrock (d=7,10d=7,10). Each run starts from 2d2d Sobol points and uses a total budget of 100 optimization steps. The methods that use MCMC take M=64M=64 hyperparameter samples per BO step. We consider noiseless observations. The results presented in Fig. 3 demonstrate that ELF-BO tracks Standard FBO closely on most of the 15 functions, with curves largely overlapping within standard error. This agreement holds across input dimensions and a range of landscape characteristics, including smooth functions such as Branin and more rugged, highly multimodal functions such as Eggholder. There are, however, functions for which ELF-BO and Standard FBO diverge, such as Michalewicz (d=5d=5). In Section 6 we analyze this failure through the lens of effective sample size. Finally, we observe that ELF-BO follows Standard FBO both when it outperforms MAP and when they are equivalent, showing no clear preference for cases where point estimates are “good enough”. This matches the goal of the work, which is to provide a small-latency alternative to fully Bayesian optimization. Figure 5: Deep kernel on real-world tasks. Results of the deep kernel on Olympus datasets. As in experiments with Matérn kernel, ELF-BO achieves Pareto optimality over Standard FBO and MAP, with an even more pronounced reduction in decision latency. See Appendix C for GAP curves. 5.2 Real-World Applications In addition, we evaluate ELF-BO on three experimental datasets curated in the Olympus benchmark suite (Häse et al., 2021). Rather than using learned emulators, we directly treat the datasets as a virtual library—thus, querying a point returns its recorded experimental measure. HPLC (d=6d=6 and ||=1,386|X|=1,386) tunes the sampling sequence of a robotic direct-inject HPLC system to maximize peak area (Roch et al., 2020). Photo-PCE10 and Photo-WF3 (d=4d=4 and ||=1,040|X|=1,040 each) optimize the composition of polymer blends to minimize22 2 We negate the objective and consider it a maximization problem. photodegradation (Langner et al., 2020). We choose the three Olympus datasets with more than 1000 data points to provide a large enough library for BO. GAP is computed with y∗y_* set to the best measurement in each dataset. All three datasets were collected through physical experiments. In a live campaign where Standard FBO chooses each experiment before it is run, every evaluation would take far longer than sampling the hyperparameter posterior, leaving the planner idle for most of the campaign—precisely the setting ELF-BO is designed for. Although the photodegradation data was collected in a high-throughput setting, we optimize all three tasks sequentially. We use an initial dataset of 2d2d Sobol points and a total budget of 50 steps for all tasks. Standard FBO and ELF-BO use M=128M=128 hyperparameter samples per BO step. More details on the tasks and datasets are provided in Appendix B. The optimization curves presented in Fig. 4 (top) demonstrate that, across all tasks, ELF-BO closely tracks Standard FBO in performance. The results also highlight that in real-world applications with limited evaluation budget, a fully Bayesian approach can improve sample efficiency, achieving better results in earlier optimization steps. We analyze the sample efficiency using the area under the GAP curve, which is presented in Fig. 4 (bottom) alongside average decision latency. This demonstrates the Pareto dominance of ELF-BO over Standard FBO and MAP, displaying optimization performance on par with Standard FBO while providing suggestions more than 10×10× faster. Deep kernel. A natural use case for a fully Bayesian approach is with deep kernels (Wilson et al., 2016), as marginalizing out the network weights can mitigate the overfitting of point estimates in the overparameterized regime (Ober et al., 2021). In addition, they offer a challenging setting for ELF-BO, as the sampled parameters include neural-network weights, a step toward BNN surrogates. We repeat the real-world benchmarks, replacing the Matérn kernel with a deep kernel (two-layer neural network; see Appendix B). As shown in Fig. 5, the decision latency of Standard FBO grows 5–9× relative to Matérn, whereas ELF-BO remains under 1 s, a 70–110× reduction, while remaining competitive in sample efficiency. 6 Analysis We now analyze ELF-BO under different settings, improving our understanding of the method. To this end, we study the scalability with respect to dataset size and the impact of effective sample size. Scaling with the number of observations. The cost of fully Bayesian optimization grows with the number of observations n. However, ELF-BO is unaffected by this growth as long as sampling fits within the evaluation time. Figure 7 shows the decision latency as a function of the number of observations on Photo-WF3 (d=4d=4) for the deep kernel model in Section 5.2. While Standard FBO latency grows up to 24 minutes, ELF-BO remains nearly constant at under 3 seconds. This highlights the large gains that can be obtained by ELF-BO when optimization campaigns are long and use more complex models. The same figure indicates the evaluation time required to fully hide sampling at each step, providing a practical guide for when ELF-BO is applicable. Impact of effective sample size. As noted in Section 3, ELF-BO depends on how representative the samples collected during the objective evaluation are. We analyze MeffM_eff of Michalewicz (d=5d=5), a function for which ELF-BO has difficulties tracking Standard FBO performance, and Hartmann (d=6d=6), a function close in dimensionality for which ELF-BO performs well. Figure 7 presents the step-wise fraction of effective samples, defined as Meff/M_eff/M. The effective sample size for Michalewicz (d=5d=5) is lower for most of the optimization steps, although it remains far from collapse for both functions. The lower values of MeffM_eff for Michalewicz (d=5d=5) help explain why ELF-BO performs worse on that function. Since MeffM_eff is available as soon as yty_t is observed, it provides a cheap diagnostic for flagging steps where the reweighted estimate may be less reliable. Figure 6: Deep kernel on larger datasets. Decision latency on Photo-WF3 (d=4d=4) as observation set grows. Standard FBO increases with dataset size while ELF-BO remains constant. Figure 7: Normalized effective sample size per iteration. Michalewicz (d=5d=5) exhibits a lower effective sample size than Hartmann (d=6d=6) for most of the optimization steps. 7 Conclusion We introduced ELF-BO, a fully Bayesian optimization algorithm that leverages the objective’s execution latency to alleviate the time taken to make a decision on the next point to query. By drawing samples from the posterior given the data available at dispatch time and reweighting them once the observation is revealed, ELF-BO removes MCMC from the time between function evaluations. Across 15 synthetic functions and three real-world experimental datasets, ELF-BO matches the optimization performance of MCMC-based fully Bayesian optimization on most tasks while keeping decision latency close to point estimate BO times. Limitations and Future Work ELF-BO’s latency gains are observed in applications for which objective function evaluations take more time than MCMC, but are absent in applications where evaluations are near-instant. Moreover, we only consider GP surrogates in the sequential setting. Natural extensions include BNN surrogates and asynchronous batch BO with multiple pending evaluations. More broadly, ELF-BO shows that the planner’s idle time, which is inherent to expensive black-box optimization, can be spent on better decisions. References Alvi et al. (2019) A. S. Alvi, B. Ru, J. Calliess, S. J. Roberts, and M. A. Osborne Asynchronous Batch Bayesian Optimisation with Improved Local Penalisation. In ICML, Cited by: §4. Ament et al. (2023a) S. Ament, S. Daulton, D. Eriksson, M. Balandat, and E. Bakshy Unexpected improvements to expected improvement for Bayesian optimization. In NeurIPS, Cited by: §2.2, §5. Ament et al. (2023b) S. Ament, A. Witte, N. Garg, and J. Kusuma Sustainable Concrete via Bayesian Optimization. arXiv preprint arXiv:2310.18288. Cited by: §1. Auer (2002) P. Auer Using Confidence Bounds for Exploitation-Exploration Trade-offs. JMLR 3 (Nov). Cited by: §2.2. Balandat et al. (2020) M. Balandat, B. Karrer, D. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In NeurIPS, Cited by: §B.3, §5. Barton (1984) R. R. Barton Minimization Algorithms for Functions with Random Noise. American Journal of Mathematical and Management Sciences 4 (1-2). Cited by: §5. Benassi et al. (2011) R. Benassi, J. Bect, and E. Vazquez Robust Gaussian Process-Based Global Optimization Using a Fully Bayesian Expected Improvement Criterion. In International Conference on Learning and Intelligent Optimization, Cited by: §1, §4. Chopin (2002) N. Chopin A Sequential Particle Filter Method for Static Models. Biometrika 89 (3). Cited by: §3. De Ath et al. (2021a) G. De Ath, R. M. Everson, and J. E. Fieldsend Asynchronous ε -Greedy Bayesian Optimisation. In UAI, Cited by: §4, §5.1. De Ath et al. (2021b) G. De Ath, R. M. Everson, and J. E. Fieldsend How Bayesian Should Bayesian Optimisation Be?. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, Cited by: §1, §4. Duane et al. (1987) S. Duane, A.D. Kennedy, B. J. Pendleton, and D. Roweth Hybrid Monte Carlo. Physics Letters B 195 (2). Cited by: §2.2. Eriksson and Jankowiak (2021) D. Eriksson and M. Jankowiak High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces. In UAI, Cited by: §4. Ginsbourger et al. (2011) D. Ginsbourger, J. Janusevskis, and R. Le Riche Dealing with asynchronicity in parallel Gaussian Process based global optimization. Research Report Mines Saint-Etienne. Cited by: §4. Ginsbourger et al. (2010) D. Ginsbourger, R. Le Riche, and L. Carraro Kriging is well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems, Cited by: §4. Greenaway et al. (2023) R. L. Greenaway, K. E. Jelfs, A. C. Spivey, and S. N. Yaliraki From Alchemist to AI Chemist. Nature Reviews Chemistry 7 (8). Cited by: §1. Häse et al. (2021) F. Häse, M. Aldeghi, R. J. Hickman, L. M. Roch, M. Christensen, E. Liles, J. E. Hein, and A. Aspuru-Guzik Olympus: a benchmarking framework for noisy optimization and experiment planning. Machine Learning: Science and Technology 2 (3). Cited by: §5.2. Hoffman and Gelman (2014) M. D. Hoffman and A. Gelman The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo.. JMLR 15 (1). Cited by: §2.2, §4, §5. Hvarfner et al. (2024) C. Hvarfner, E. O. Hellsten, and L. Nardi Vanilla Bayesian Optimization Performs Great in High Dimensions. In ICML, Cited by: §5. Jones et al. (1998) D. R. Jones, M. Schonlau, and W. J. Welch Efficient global optimization of expensive black-box functions. Journal of Global Optimization 13. Cited by: §1, §2.2. Kandasamy et al. (2018) K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Póczos Parallelised Bayesian Optimisation via Thompson Sampling. In AISTATS, Cited by: §4. Kingma and Ba (2015) D. P. Kingma and J. Ba Adam: A Method for Stochastic Optimization. In ICLR, Cited by: §B.2. Kristiadi et al. (2023) A. Kristiadi, A. Immer, R. Eschenhagen, and V. Fortuin Promises and pitfalls of the linearized Laplace in Bayesian optimization. In Fifth Symposium on Advances in Approximate Bayesian Inference, Cited by: §4. Kristiadi et al. (2024) A. Kristiadi, F. Strieth-Kalthoff, M. Skreta, P. Poupart, A. Aspuru-Guzik, and G. Pleiss A sober look at LLMs for material discovery: Are they actually good for Bayesian optimization over molecules?. In ICML, Cited by: §1, §4. Lam et al. (2018) R. Lam, M. Poloczek, P. Frazier, and K. E. Willcox Advances in Bayesian Optimization with Applications in Aerospace Engineering. In 2018 AIAA Non-Deterministic Approaches Conference, Cited by: §1. Langner et al. (2020) S. Langner, F. Häse, J. D. Perea, T. Stubhan, J. Hauch, L. M. Roch, T. Heumueller, A. Aspuru-Guzik, and C. J. Brabec Beyond Ternary OPV: High-Throughput Experimentation and Self-Driving Laboratories Optimize Multicomponent Systems. Advanced Materials 32 (14). Cited by: §B.1, §5.2. Li et al. (2024) Y. Li, T. G. Rudner, and A. G. Wilson A Study of Bayesian Neural Network Surrogates for Bayesian Optimization. In ICLR, Cited by: §1, §4. MacLeod et al. (2020) B. P. MacLeod, F. G. L. Parlane, T. D. Morrissey, F. Häse, L. M. Roch, K. E. Dettelbach, R. Moreira, L. P. E. Yunker, M. B. Rooney, J. R. Deeth, V. Lai, G. J. Ng, H. Situ, R. H. Zhang, M. S. Elliott, T. H. Haley, D. J. Dvorak, A. Aspuru-Guzik, J. E. Hein, and C. P. Berlinguette Self-Driving Laboratory for Accelerated Discovery of Thin-Film Materials. Science Advances 6 (20). Cited by: §1, §3.1. Močkus (1975) J. Močkus On Bayesian Methods for Seeking the Extremum. In Optimization Techniques IFIP Technical Conference, Cited by: §1. Murray and Adams (2010) I. Murray and R. P. Adams Slice Sampling Covariance Hyperparameters of Latent Gaussian Models. In NIPS, Cited by: §2.2, §4. Muthyala et al. (2026) M. R. Muthyala, F. Sorourifar, T. Tan, Y. Peng, and J. A. Paulson Generative Multiobjective Bayesian Optimization with Scalable Batch Evaluations for Sample-Efficient De Novo Molecular Design. Industrial & Engineering Chemistry Research 65 (1). Cited by: §1. Neal (2003) R. M. Neal Slice sampling. The Annals of Statistics 31 (3). Cited by: §2.2, §4. Neal (2011) R. Neal Handbook of Markov Chain Monte Carlo. Cited by: §1, §2.2. Ober et al. (2021) S. W. Ober, C. E. Rasmussen, and M. van der Wilk The Promises and Pitfalls of Deep Kernel Learning. In UAI, Cited by: §4, §5.2. Osborne et al. (2009) M. A. Osborne, R. Garnett, and S. J. Roberts Gaussian Processes for Global Optimization. In International Conference on Learning and Intelligent Optimization, Cited by: §1, §4. Owen (2013) A. B. Owen Monte Carlo Theory, Methods and Examples. https://artowen.su.domains/mc/. Cited by: §3. Rasmussen and Williams (2006) C. E. Rasmussen and C. K. I. Williams Gaussian Processes for Machine Learning. The MIT Press. Cited by: §1. Riegler et al. (2026) B. Riegler, J. Odgers, and V. Fortuin Standard Acquisition Is Sufficient for Asynchronous Bayesian Optimization. In AISTATS, Cited by: §4. Roch et al. (2020) L. M. Roch, F. Häse, C. Kreisbeck, T. Tamayo-Mendoza, L. P. E. Yunker, J. E. Hein, and A. Aspuru-Guzik ChemOS: An Orchestration Software to Democratize Autonomous Discovery. PLOS ONE 15 (4). Cited by: §B.1, §5.2. Snoek et al. (2012) J. Snoek, H. Larochelle, and R. P. Adams Practical Bayesian optimization of machine learning algorithms. In NeurIPS, Cited by: §4. Srinivas et al. (2010) N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In ICML, Cited by: §2.2. Thompson (1933) W. R. Thompson On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3-4). Cited by: §4. Verma et al. (2022) A. Verma, Z. Dai, and B. K. H. Low Bayesian Optimization Under Stochastic Delayed Feedback. In ICML, Cited by: §4. Wilson et al. (2016) A. G. Wilson, Z. Hu, R. Salakhutdinov, and E. P. Xing Deep Kernel Learning. In AISTATS, Cited by: §5.2. Appendix A Proofs See 1 Proof. Let t∈1,…,Tt∈\1,…,T\ be arbitrary. By the importance sampling argument: ∼p(∣t)[φ()]=∫φ()p(∣t)=∫φ()p(∣t)p(∣t−1)⏟=:w()p(∣t−1)d=∼p(∣t−1)[w()φ()]. splitE_ θ p( θ _t)[ ( θ)]&= ( θ)\,p( θ _t)\,d θ\\ &= ( θ) p( θ _t)p( θ _t-1)_=:w( θ)p( θ _t-1)\,d θ\\ &=E_ θ p( θ _t-1)[w( θ)\, ( θ)]\,. split In particular, the importance weight is w()=p(∣t)p(∣t−1)w( θ)= p( θ D_t)p( θ D_t-1). Recall that t=t−1∪(t,yt)D_t=D_t-1∪\( x_t,y_t)\. Thus p(∣t)=p(∣t−1,t,yt)p( θ D_t)=p( θ D_t-1, x_t,y_t). Therefore, by Bayes’ rule we have that: p(∣t)=p(∣t−1,t,yt)=p(yt∣t−1,t,)p(∣t−1,t)p(yt∣t−1,t)=p(yt∣t−1,t,)p(∣t−1)p(yt∣t−1,t). splitp( θ _t)&=p( θ _t-1, x_t,y_t)\\ &= p(y_t _t-1, x_t, θ)\,p( θ _t-1, x_t)p(y_t _t-1, x_t)\\ &= p(y_t _t-1, x_t, θ)\,p( θ _t-1)p(y_t _t-1, x_t)\,. split Therefore, plugging this into w()w( θ) we get: w()=p(∣t)p(∣t−1)=p(yt∣t−1,t,)p(∣t−1)p(yt∣t−1,t)1p(∣t−1)=p(yt∣t−1,t,)p(yt∣t−1,t)∝p(yt∣t−1,t,), splitw( θ)&= p( θ _t)p( θ _t-1)\\ &= p(y_t _t-1, x_t, θ)\,p( θ _t-1)p(y_t _t-1, x_t) 1p( θ _t-1)\\ &= p(y_t _t-1, x_t, θ)p(y_t _t-1, x_t)\\ & p(y_t _t-1, x_t, θ), split where the last proportionality is because the denominator is constant w.r.t. θ. ∎ Appendix B Experimental Details B.1 Real-World Applications HPLC. The dataset originates from the autonomous calibration of a robotic sampling sequence for direct-inject HPLC analysis (Roch et al., 2020). The authors report sessions of 100 autonomous experiments over approximately seven hours, corresponding to roughly four minutes per evaluation. Photo-PCE10 and Photo-WF3. These datasets report the photostability of photovoltaic blends (Langner et al., 2020). The experimental time reported by the authors is 18 hours for a batch of samples. As mentioned in the main text, we consider the problem in the sequential (non-batch) optimization setting. B.2 Deep Kernel Details The deep kernel is implemented as σf⋅k(ℰ(),ℰ(′)) _f· k(E( x),E( x )), where k is a Matérn kernel with lengthscales fixed at 1, σf _f is a kernel outputscale, and ℰ:ℝd→ℝ8E:R^d ^8 is a neural network with a single hidden layer of dimension 16 and tanh activations. Taking into consideration the observation noise and constant mean, the deep kernel has a total of 16d+15516d+155 hyperparameters. To give NUTS a proper posterior to sample and prevent overfitting in MAP, we impose a zero-mean normal prior with variance 0.25 for all the neural network’s biases and 4/Lin4/L_in for its weights, where LinL_in is the dimension of the layer’s input. For the experiments in Section 5.2, the MAP deep kernel is optimized using 500 iterations of Adam (Kingma and Ba, 2015) per restart, with 4 restarts and a learning rate of 0.01. For Standard FBO and ELF-BO, samples are obtained using NUTS with a diagonal mass matrix, performing 512 warmup steps and 4096 samples, resulting in M=256M=256 after thinning by 16, with a max tree depth of 10. For the scaling experiments in Section 6 we use M=128M=128 and the Log-EI is evaluated on batches of 32 candidates at a time. B.3 Computational Resources Experiments are implemented in Python using the BoTorch (Balandat et al., 2020) library version 0.18.1. All synthetic benchmarks are executed on a single NVIDIA L40S, while real-world experiments make use of an NVIDIA H100. B.4 Further Experimental Details A throwaway NUTS run happens before the first BO step, so that device start-up is not considered in latency results. Acquisition function optimization For the continuous synthetic functions, we use 10 restarts, with 512 raw samples. For the discrete real-world problems, every unused row is scored, 512 rows at a time. Appendix C Additional Results Figure 8: Deep kernel on real-world tasks. Optimization curves of the deep kernel methods on Olympus datasets. Deep Kernel Figure 8 presents the complete GAP curves for the deep kernel experiments described in Section 5.2.