- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the trade-off between parallel evaluations and adaptive feedback rounds in prior-guided search. It introduces a conditional upper bound on the rounds needed to reach a target regret, using a prior-relative difficulty parameter and an effective coverage factor. The proposed PWBO method combines prior-weighted proposals, batch diversity, and confidence-based elimination. Synthetic experiments examine the predicted scaling, while Avazu and NAS-Bench-201 experiments compare search performance with several BO baselines.
Critical strengths
-
Separating feedback rounds from evaluation count is useful. When evaluations can run in parallel, the number of times the search must wait for feedback is a meaningful resource. The distinction between distinct locations and repeated evaluations in Section 3 is also helpful.
-
The experiments include relevant controls. The prior-quality intervention, diversity ablations, and fixed-prior GP-update comparison help explain where the gains come from. The NAS-Bench-201 result also provides some evidence beyond the CTR setting.
Critical weaknesses
-
The connection between the theorem and the implemented PWBO algorithm is not established well enough. Appendix A.2 requires attainable covering, sharp growth, mass–geometry alignment, and globally calibrated spatial confidence bounds. It also explicitly leaves certification for the chosen surrogate as an implementation obligation. The practical GP and repulsive selection rule are not shown to satisfy these conditions, so the theorem provides conditional motivation rather than a guarantee for PWBO. This gap limits the main theoretical contribution.
-
The fitted parameters do not independently validate the theoretical quantities. Section 6 and Appendix D fit difficulty and coverage parameters to the observed frontier, while Appendix D.2 calls the reported difficulty values phenomenological. Matching the expected ordering is interesting, but is weaker than showing that independently measured prior mass and coverage predict the round counts. Also, an upper bound alone does not establish that the reciprocal-log curve is a tight frontier. The paper should keep these distinctions clearer.
-
The practical efficiency evidence is incomplete. Appendix C reports round counts and evaluations, and explicitly excludes scheduling and proposal-generation overhead from its latency interpretation. This is reasonable accounting, but the motivation is reduced waiting time. With LLM proposal calls and potentially unequal pipeline durations, fewer rounds do not yet establish an end-to-end time saving. The current evidence leaves that practical benefit unresolved.
-
The presentation needs more work. The abstract puts a fairly dense bound and several symbols before giving enough intuition. Figure 1 is also too schematic: the points, diamonds, shaded regions, and boundaries are not clearly defined, and their relation to the coverage factor is mostly asserted in the caption. An explicit small example would communicate the mechanism much better. These are fixable issues, but they make the central argument harder to assess.
Questions for authors
-
Which assumptions in Appendix A.2 are certified for the actual PWBO implementation? In particular, do the implemented confidence intervals meet the spatial-envelope requirement, or should the theorem be read solely as motivation?
-
Can the theoretical difficulty and coverage quantities be estimated independently of the frontier fit from the existing enumerated data? Please distinguish those estimates from the fitted parameters already reported.
-
Do the existing execution logs include proposal-generation and batch-duration measurements? If so, do they support the practical time-saving motivation after these costs are included?
Thank you again for your comments on our submission. As the discussion period ends soon, we would be grateful if you could take a look and let us know whether it addresses your concerns. We are happy to answer any further questions.