Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Fast Bayesian Optimization of Function Networks with Partial Evaluations

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read A single global candidate replaces nested per-node search, giving up to a 16x speedup in Bayesian optimization of function networks while keeping query choices nearly unchanged.

desk verdict A pragmatic speedup of p-KGFN with real empirical gains, but the two approximations that make it fast are under-analyzed and one subroutine is under-specified. read the letter →

arxiv 2506.11456 v2 pith:BXCZ7TDM submitted 2025-06-13 stat.ML cs.LG

classification stat.MLcs.LG
keywords BayesianoptimizationfunctionnetworkspartialevaluationsknowledgegradientacquisitionGaussianprocesscomputationalspeedupexpectedimprovement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the expensive nested acquisition optimization of p-KGFN can be replaced by a much cheaper procedure without losing much query efficiency. It proposes Fast p-KGFN, which generates one candidate network input via a modified expected-improvement problem, propagates it through sampled surrogate functions to form node-specific candidates, and then evaluates p-KGFN on a small discrete set rather than solving a nested continuous optimization problem for every node. Numerical experiments on three function-network problems report objective values close to p-KGFN per unit evaluation cost while cutting acquisition runtime by up to about 16x. If true, this widens the applicability of cost-aware partial evaluations to problems where the original acquisition cost dominated the savings.

What carries the argument

The load-bearing mechanism is a three-step shortcut: (1) a modified EIFN acquisition function $\mathbb{E}[(y_K(x) - \nu_n^*)^+ \mid D_n]$ is optimized once to obtain a network-level candidate $\hat{x}_n$; (2) one posterior sample of every node function is propagated through the DAG to simulate intermediate outputs $\hat{y}_k(\hat{x}_n)$, which are concatenated with the relevant external inputs to assemble node-specific candidates $\hat{z}_{n,k}$; (3) the p-KGFN acquisition $\alpha_{n,k}(\hat{z}_{n,k})$ is evaluated over the small discretization $A = S_T \cup S_L \cup \{x_n^*\}$ instead of over $X$, where $S_T$ comes from a batch Thompson sampling scheme that selects $N_T$ points maximizing average performance across $M$ sampled networks and $S_L$ are random points near $x_n^*$. The nested optimization of the original method is thereby replaced by one continuous solve plus finite enumeration.

What would settle it

For one of the paper's test networks, evaluate a node candidate $z_k$ at a point whose hypothetical observation shifts the updated posterior mean maximizer far from $A$ (for example, into a region not covered by local points and not sampled by batch Thompson draws), then compute $\alpha_{n,k}(\hat{z}_{n,k})$ using $A$ and using a dense global optimization of $\nu_{n+1}$; if the rankings of nodes change and Fast p-KGFN selects a node that a correct p-KGFN value would not, the central speedup claim is refuted.

Watch

Extended reading notes

Core claim

The central claim is that the computational bottleneck of p-KGFN, namely optimizing a nested Monte Carlo acquisition function separately for every node, is avoidable. Fast p-KGFN replaces this with one optimization of EIFN modified to use the current posterior-mean maximum $\nu_n^*$ as the baseline, then uses one shared GP sample path through the network to produce a candidate input for each node, and finally approximates the p-KGFN value of each candidate by maximizing the updated posterior mean over a discrete set $A$ containing batch-Thompson points, local points, and the current maximizer $x_n^*$. The paper reports that this variant achieves optimization performance close to p-KGFN and consistently beats full-evaluation baselines, while speeding up acquisition computation up to 16x.

Load-bearing premise

Everything rests on the heuristic that the small discrete set $A$ contains a point close to the true maximizer of each updated posterior mean $\max_{x \in X} \nu_{n+1}(x; z_k)$; when that fails the p-KGFN estimate is wrong and the algorithm may pick the wrong node or input, and the paper provides no error bound for this approximation.

Editorial extensions

If this is right

  • Per-iteration acquisition runtime drops by 4.24x to 16.03x across the reported problems, with the largest speedup when p-KGFN is most expensive.
  • Optimization quality stays close to p-KGFN and, in the reported comparisons, consistently beats EIFN, showing that partial evaluations still earn their keep.
  • The benefits of partial evaluations grow as the evaluation cost of downstream nodes increases, in both p-KGFN and Fast p-KGFN.
  • The current posterior-mean maximizer $x_n^*$ in the discrete set is essential: ablations show that removing it degrades performance sharply.
  • The method applies whenever intermediate node outputs can be queried at arbitrary feasible inputs without first evaluating parents.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same 'one global solve plus discrete enumeration' template could accelerate other acquisition functions whose nested expectation requires solving an inner continuous optimization for each sampled outcome.
  • The speedup should grow roughly linearly in the number of nodes, since the original method solves one nested acquisition problem per node while the fast method solves one EIFN problem regardless of the network size; this is a testable scaling prediction.
  • The batch-Thompson representative subset idea, choosing a small set that performs well on average across many sampled networks, may be useful beyond p-KGFN as a cheap construction of promising sets in multi-fidelity or multi-objective settings.
  • A possible failure mode the paper leaves open is that on strongly multimodal function networks, the single EIFN candidate plus local neighborhood may systematically miss promising nodes whose inputs are far from the current maximizer, so the method may degrade where many separated optima exist.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper proposes Fast p-KGFN, an accelerated variant of the p-KGFN acquisition function for Bayesian optimization of function networks with partial evaluations. Instead of solving a nested optimization problem for each node, the method generates one candidate input per node by optimizing a modified EIFN acquisition, draws a single realization from each GP posterior to compute intermediate outputs, and then evaluates the p-KGFN acquisition on a small discrete set A built from batch Thompson sampling, local points, and the current posterior mean maximizer. Experiments on AckMat, FreeSolv, and Manu report objective values close to p-KGFN with up to a 16x reduction in per-iteration runtime, along with ablations on the discrete set composition and its parameters.

Significance. If the claims hold, the paper is practically valuable because it substantially reduces the computational overhead of p-KGFN, making partial-evaluation BOFN applicable to problems where objective evaluations are only moderately expensive. The paper's strengths include reproducible code, results averaged over 30 trials with confidence intervals, runtime comparisons, and parameter ablations that show robustness. However, the central approximation, replacing the continuous inner maximization in p-KGFN with a small discrete set A, is heuristic and unquantified, and the paper does not describe how the batch Thompson subset-selection problem is solved. These issues temper the strength of the central empirical claim.

major comments (2)
  1. [§4.2, Eq. (4), Algorithm 1 step 10] The replacement of max_{x∈X} ν_{n+1}(x; z_k) with max_{x∈A} ν_{n+1}(x; z_k) is load-bearing for node selection, but the paper provides no analysis or empirical validation of this approximation. The ablation in Appendix B only compares different compositions of A; it never checks whether A contains points near the true continuous maximizer, nor how the selected action would change with a much richer discrete set. Because the central claim of maintaining competitive query efficiency depends on this approximation, please add an experiment or analysis that quantifies its error, for example by comparing the objective values obtained against a variant that uses a much larger discrete set or continuous inner optimization on at least one problem, such as AckMat.
  2. [§4.2, batch Thompson sampling subset selection] The method requires solving ST ∈ arg max_{S⊂X, |S|=N_T} (1/M) Σ_{j=1}^M max_{x∈S} f̂^A_j(x), but the paper does not specify how this combinatorial optimization over a continuous space is performed, what candidate pool is searched, or whether the solution is exact or approximate. This missing algorithmic detail is necessary for reproducibility and also affects the quality of A; please state the algorithm used (e.g., greedy selection from the set of sampled realizations' maximizers) and, if it is approximate, discuss the impact on the discrete set quality.
minor comments (5)
  1. [Table 1 and Appendix A.1] The label "ActMat" should be "AckMat" in the table header and the appendix section heading.
  2. [Algorithm 1, step 4] The phrase "with replacing y*_{n,K} by ν*_n" should be "by replacing y*_{n,K} with ν*_n".
  3. [§2] The statement that "a set containing Y_{J(k)} is known" is vague; the main text should give a concrete example of how such a set is obtained (as the appendix does for the test problems) or explicitly refer to the appendix.
  4. [Appendix D, caption] The caption says "comparing Fast p-KGFN against 8 baselines," but only seven baselines are listed alongside Fast p-KGFN; this should be corrected to "7 baselines" or the list should be adjusted.
  5. [Appendix B, Figure 5] The ablation would be more informative if it reported the discrete set sizes for each configuration (for example, the default has |A|=21 while Thompson+Local has |A|=20), since the performance differences could be confounded with the size of A.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the speedup and query-efficiency claims are empirical and the heuristic discrete-set approximation is a risk, not a circular reduction.

full rationale

The paper's central claims are empirical: Fast p-KGFN is compared on three benchmark problems against p-KGFN, EIFN, KGFN, TSFN, EI, KG, and Random, and the reported speedup is measured wall-clock runtime while query efficiency is measured by ground-truth objective value at the posterior-mean maximizer. The acquisition function values used for node selection are not fitted to the target outcomes; they are computed from the GP posterior via the p-KGFN formula and a finite-set approximation of max_x ν_{n+1}(x; z_k). The use of the discrete set A = S_T ∪ S_L ∪ {x*_n} is an unquantified approximation, and the ablation studies assess which heuristic components of A matter, but this is a correctness/robustness concern rather than a circularity: the method does not define its prediction in terms of the quantity it claims to predict, and no fitted parameter is renamed as a prediction. Self-citations to Buathong et al. (2024) and Astudillo and Frazier (2021a) supply the definitions of p-KGFN and EIFN which the paper extends and accelerates; this is standard building on prior work, not a load-bearing chain that forces the claimed results. No equation in the paper reduces by construction to its inputs, and no uniqueness theorem or self-citation is invoked to forbid alternatives. Thus the honest finding is no significant circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The method relies on a handful of hand-chosen hyperparameters (M, N_T, N_L, r) and several assumptions about the problem structure (independent node evaluation, GP surrogates) and the quality of the discrete set. No new physical or conceptual entities are introduced.

free parameters (4)
  • M (number of network realizations for batch TS) = 10 (default)
    Chosen by hand in Section 5; ablation in Appendix C shows robustness across values 5 to 15.
  • N_T (number of batch Thompson points) = 10 (default)
    Chosen by hand; ablation in Appendix C shows robustness across values 5 to 15.
  • N_L (number of local points) = 10 (default)
    Chosen by hand; ablation in Appendix C shows robustness across values 5 to 15.
  • r (local point radius) = 0.1 (default)
    Chosen by hand; ablation in Appendix C shows robustness across 0.01 to 0.5.
assumptions (4)
  • domain assumption A set containing the feasible outputs of parent nodes is known, and each node can be evaluated at any input in that set without evaluating its parents.
    Section 2 states this assumption explicitly; it is what makes partial evaluations possible and is a known limitation acknowledged in the conclusion.
  • domain assumption Each node function is modeled as an independent GP, leading to conditionally independent posteriors.
    Section 3 adopts the inference scheme of Astudillo and Frazier (2021a); the correctness of the acquisition values depends on this statistical model.
  • ad hoc to paper The discrete set A is a good surrogate for the full continuous search space in the inner maximization of p-KGFN.
    Section 4.2 replaces max over X with max over A without an error bound; the entire speedup relies on this approximation.
  • ad hoc to paper Thompson sampling realizations from the GP posteriors provide a representative set of function draws for subset selection.
    The batch TS selection in Section 4.2 assumes these samples are sufficient to identify high-potential points.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Bayesian Optimization of Function Networks with Partial Evaluations." pith.science (2026). https://pith.science/paper/BXCZ7TDM

@misc{pith2026250611456,
  author       = {Pith},
  title        = {Pith review of: Fast Bayesian Optimization of Function Networks with Partial Evaluations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BXCZ7TDM}},
  note         = {Machine review of arXiv:2506.11456}
}
read the original abstract

Bayesian optimization of function networks (BOFN) is a framework for optimizing expensive-to-evaluate objective functions structured as networks, where some nodes' outputs serve as inputs for others. Many real-world applications, such as manufacturing and drug discovery, involve function networks with additional properties - nodes that can be evaluated independently and incur varying costs. A recent BOFN variant, p-KGFN, leverages this structure and enables cost-aware partial evaluations, selectively querying only a subset of nodes at each iteration. p-KGFN reduces the number of expensive objective function evaluations needed but has a large computational overhead: choosing where to evaluate requires optimizing a nested Monte Carlo-based acquisition function for each node in the network. To address this, we propose an accelerated p-KGFN algorithm that reduces computational overhead with only a modest loss in query efficiency. Key to our approach is generation of node-specific candidate inputs for each node in the network via one inexpensive global Monte Carlo simulation. Numerical experiments show that our method maintains competitive query efficiency while achieving up to a 16x speedup over the original p-KGFN algorithm.

Figures

Figures reproduced from arXiv: 2506.11456 by the authors.

Figure 1
Figure 1. Such compositions are called function networks and are described with a directed acyclic graph (DAG) where arXiv:2506.11456v2 [stat.ML] 23 Jun 2025 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 1
Figure 1. An example of an objective function modeled as a function network. The objective function’s input is the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Function networks in the numerical experiments: (a) AckMat (b) FreeSolv and (c) Manu [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figures from the paper (6 more)
Figure 3
Figure 3. Figure 3: Optimization performance comparing between our proposed Fast p-KGFN algorithm and benchmarks [PITH_FULL_IMAGE:figures/full_fig_p006_3.png]
Figure 4
Figure 4. Figure 4: Cost sensitivity analysis for AckMat (top row) and FreeSolv (bottom row) problems with different costs (a) [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Ablation study focused on the discrete set generation method. Fast p-KGFN average performance over 30 [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Ablation study focused on the discrete set generation parameters [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Ablation study focused on the discrete set generation parameter [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: Pareto front comparison (acquisition optimization runtime vs. final objective value) averaged over 30 trials [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 22 canonical work pages

  1. [1]

    Ackley, D. (2012). A connectionist machine for genetic hillclimbing , volume 28. Springer science & business media

  2. [2]

    and Frazier, P

    Astudillo, R. and Frazier, P. (2019). Bayesian optimization of composite functions. In International Conference on Machine Learning , pages 354--363. PMLR

  3. [3]

    and Frazier, P

    Astudillo, R. and Frazier, P. (2021a). Bayesian optimization of function networks. Advances in neural information processing systems , 34:14463--14475

  4. [4]

    and Frazier, P

    Astudillo, R. and Frazier, P. I. (2021b). Thinking inside the box: A tutorial on grey-box bayesian optimization. In 2021 Winter Simulation Conference (WSC) , pages 1--15. IEEE

  5. [5]

    G., and Bakshy, E

    Balandat, M., Karrer, B., Jiang, D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. (2020). Botorch: A framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems , 33:21524--21538

  6. [6]

    Buathong, P., Wan, J., Astudillo, R., Daulton, S., Balandat, M., and Frazier, P. I. (2024). Bayesian optimization of function networks with partial evaluations. In Proceedings of the 41st International Conference on Machine Learning , pages 4752--4784

  7. [7]

    I., Baar, K., and Block, D

    Cosenza, Z., Astudillo, R., Frazier, P. I., Baar, K., and Block, D. E. (2022). Multi-information source bayesian optimization of culture media for cellular agriculture. Biotechnology and bioengineering , 119(9):2447--2458

  8. [8]

    R., Chang, J., Myung, J., Hooper, D., Armstrong, A., Pitt, M., and Maruyama, B

    Deneault, J. R., Chang, J., Myung, J., Hooper, D., Armstrong, A., Pitt, M., and Maruyama, B. (2021). Toward autonomous additive manufacturing: Bayesian optimization on a 3d printer. MRS Bulletin , 46:566--575

Show all 26 references
  1. [9]

    Frazier, P. I. (2018). A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811

  2. [10]

    I., Powell, W

    Frazier, P. I., Powell, W. B., and Dayanik, S. (2008). A knowledge-gradient policy for sequential information collection. SIAM Journal on Control and Optimization , 47(5):2410--2439

  3. [11]

    Frazier, P. I. and Wang, J. (2016). Bayesian optimization for materials design. Information science for materials discovery and design , pages 45--75

  4. [12]

    Garnett, G. P. (2002). An introduction to mathematical models in sexually transmitted disease epidemiology. Sexually transmitted infections , 78(1):7--12

  5. [13]

    N., Duvenaud, D., Hern \'a ndez-Lobato, J

    G \'o mez-Bombarelli, R., Wei, J. N., Duvenaud, D., Hern \'a ndez-Lobato, J. M., S \'a nchez-Lengeling, B., Sheberla, D., Aguilera-Iparraguirre, J., Hirzel, T. D., Adams, R. P., and Aspuru-Guzik, A. (2018). Automatic chemical design using a data-driven continuous representatio...

  6. [14]

    and Yang, X.-S

    Jamil, M. and Yang, X.-S. (2013). A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Optimisation , 4(2):150--194

  7. [15]

    R., Schonlau, M., and Welch, W

    Jones, D. R., Schonlau, M., and Welch, W. J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global optimization , 13:455--492

  8. [16]

    Khongkomolsakul, W., Buathong, P., Yang, E., Dadmohammadi, Y., Zhou, Y., Li, P., Yang, L., Frazier, P., and Abbaspourrad, A. (2025). Improving thermal and gastric stability of phytase via ph shifting and coacervation: A demonstration of bayesian optimization for rapid process ...

  9. [17]

    Kusakawa, S., Takeno, S., Inatsu, Y., Kutsukake, K., Iwazaki, S., Nakano, T., Ujihara, T., Karasuyama, M., and Takeuchi, I. (2022). Bayesian optimization for cascade-type multistage processes. Neural Computation , 34(12):2408--2431

  10. [18]

    Mobley, D. L. and Guthrie, J. P. (2014). Freesolv: a database of experimental and calculated hydration free energies, with input files. Journal of computer-aided molecular design , 28:711--720

  11. [19]

    Mo c kus, J. (1975). On bayesian methods for seeking the extremum. In Optimization techniques IFIP technical conference: Novosibirsk, July 1--7, 1974 , pages 400--404. Springer

  12. [20]

    Plappert, M., Andrychowicz, M., Ray, A., McGrew, B., Baker, B., Powell, G., Schneider, J., Tobin, J., Chociej, M., Welinder, P., et al. (2018). Multi-goal reinforcement learning: Challenging robotics environments and request for research. arXiv preprint arXiv:1802.09464

  13. [21]

    Scott, W., Frazier, P., and Powell, W. (2011). The correlated knowledge gradient for simulation optimization of continuous parameters using gaussian process regression. SIAM Journal on Optimization , 21(3):996--1026

  14. [22]

    Sha, D., Ozbay, K., and Ding, Y. (2020). Applying bayesian optimization for calibration of transportation simulation models. Transportation Research Record , 2674(10):215--228

  15. [23]

    Snoek, J., Larochelle, H., and Adams, R. P. (2012). Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems , 25

  16. [24]

    Ungredda, J., Pearce, M., and Branke, J. (2022). Efficient computation of the knowledge gradient for bayesian optimization. arXiv preprint arXiv:2209.15367

  17. [25]

    Williams, C. K. and Rasmussen, C. E. (2006). Gaussian processes for machine learning , volume 2. MIT press Cambridge, MA

  18. [26]

    and Frazier, P

    Wu, J. and Frazier, P. (2016). The parallel knowledge gradient method for batch bayesian optimization. Advances in neural information processing systems , 29

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.