acceptodds
Under review as a conference paper at ICLR 2027

Trading Adaptive Depth for Parallel Width in Prior-Guided Search

Abstract

Automated machine-learning (AutoML) search consumes both evaluations and feedback rounds. When evaluations can run in parallel, waiting for feedback between batches can dominate elapsed time even when the total number of evaluations is unchanged. We study how much adaptive depth is needed to reach a target regret when each round can evaluate candidates in parallel. We characterize this tradeoff through the iso-regret frontier , which under regularity, coverage, and calibration conditions satisfies . Here describes how rapidly near-optimal mass vanishes under a fixed reference prior, while summarizes losses in useful within-round coverage. The result gives a sufficient regime in which increasing parallel width can reduce the number of feedback rounds. Motivated by this characterization, we propose Prior-Weighted Bayesian Optimization (PWBO), which combines prior-weighted proposals, diversity-aware batch selection, and confidence-based elimination. In controlled synthetic experiments that vary prior quality and within-round coverage, the observed round counts follow the predicted reciprocal-log frontier, and the fitted difficulty parameter increases across priors as the theory predicts. We then study PWBO on a fully enumerated Avazu click-through-rate (CTR) pipeline testbed, where enumeration provides an exact reachable comparator while each search evaluation still requires model training. On this testbed, PWBO reaches the target in fewer feedback rounds than competing BO baselines.

Primary area:
optimization
Keywords:
LLM-guided AutoML, Round complexity, Prior-weighted Bayesian optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_HkM3OpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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.

  3. 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.

  4. 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
  1. 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?

  2. 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.

  3. 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?

1 comment

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.

Reviewer_THUcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors study expensive search when parallel evaluation is available but feedback remains sequential, asking how many feedback rounds are needed to reach a target regret when each round can evaluate multiple candidates. They characterize this tradeoff via an iso-regret frontier and prove an upper bound on the required number of rounds. Observations around this bound motivate their proposed approach, PWBO, which combines prior-weighted proposals, diversity-aware batch selection, and confidence-based elimination. They extensively evaluate PWBO, where it reaches the target in fewer rounds than the baselines and random search.

Critical strengths
  1. I find the the paper to be well organized and easy to follow, and the figures help a lot in understanding the abstract quantities like deffd_{eff} and νeffν_{eff} (e.g. Figure 1 and Figures 5–8). The appendix is also very detailed with supporting explanation/experiments.

  2. The key idea is decomposing the depth–width tradeoff into two separate bottlenecks i.e how much mass the prior places near the optimum (deffd_{eff}), and how much non-redundant coverage each batch actually provides (νeffν_{eff}). I find this a useful way to explain when wider batches reduce the number of feedback rounds and when they don’t, which, to my knowledge, existing prior-guided BO methods do not explicitly model.

  3. The theory states explicitly the conditions under which the tradeoff holds and gives a case where it breaks down. Lemma 1 shows that repeating evaluations reduces noise but leaves fewer distinct designs per batch. Proposition 1 shows that on flat objectives only the total number of evaluations matters, and the synthetic negative control confirms this. The Avazu experiments then test each bottleneck separately.

Critical weaknesses
  1. The paper says deffd_{eff} measures how much mass the prior puts near the optimum, but from what I can see the proof of Lemma 1 never actually uses the prior mass. deffd_{eff} only comes in through assumption A5, which is about covering numbers, so in practice it behaves like the dimension of the space rather than something about the prior. in the 2-D example in A.2.3 the authors themselves say A5 only holds when α ≥ 2, which means the prior is no better than uniform. so as far as I understand, Theorem 1 doesn’t show that a better prior leads to fewer rounds, which is the main message of the paper.

  2. For the Avazu results, PWBO and LLAMBO show no variation across the 10 seeds, so it’s hard to tell how robust the advantage is. Table 1 only shows b∈{4,8}b \in \{4, 8\}, and the space is small and fully enumerable, while the paper is motivated by open-ended program search. I think the results would be more convincing with seeds that actually change the outcome, the full six-width table, and a larger, non-enumerable search space with larger batch sizes closer to practical settings.

  3. The paper doesn’t position its bound against closely related prior results. I think the near-optimality dimension used in X-armed bandits and optimistic optimization is very similar in spirit to deffd_{eff}. There are also works on batched and limited-adaptivity GP optimization that study how many rounds are needed when evaluations come in batches. Without discussing these, it’s hard to tell what is new in the theory beyond the standard covering argument.

Questions for authors
  1. In Table 1, PWBO-Unif never reaches the target and ends with higher regret than random search at both b=4 and b=8. Could the authors explain why, and clarify whether the random search baseline samples uniformly or from the Qwen prior?

  2. The paper is motivated by reducing elapsed time, but no wall-clock results are reported. How does the time saved by fewer rounds compare to the cost of prompting the LLM each round with the full candidate list?

  3. The authors defines an adaptivity-beneficial regime (Section 3) and gives the number of prior samples needed without feedback (Corollary 2). I am not sure where do the Avazu experiments sit relative to this threshold? given the Qwen prior’s near-optimal mass in Fig. 3a, plain prior sampling would already be expected to succeed fairly often at T=16, which seems consistent with Table 2.

Reviewer_Y2sMOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a new search method called Prior Weighted Bayesian Optimisation (PWBO) for AutoML pipeline optimisation. Unlike existing AutoML algorithms that are typically optimised to find a good pipeline configuration with the fewest training/evaluations runs, PWBO assumes that parallel pipeline evaluations are available and therefore optimizes the number of rounds executed (I.e, depth) to find a good configuration. Specifically, the tradeoff between width (number of parallel evaluations) and depth (number of rounds) is characterised by a iso-regret frontier that combines the prior quality (d_eff) and coverage (v_eff). The algorithm also select sthe next batch to evaluate in parallel in such a way that the corresponding pipeline configurations are diverse and also prunes unpromising candidate pipeline configurations based on an upper confidence bound. The proposed method is evaluated empirically on synthetic as well as realistic benchmarks. The results demonstrate clearly that PWBO is competitive and often outperforms existing prior-based AutoML methods.

Critical strengths
  • The paper considers the problem of automated ML pipeline optimisation and develops a new method to solve it more efficiently in practice.

  • The proposed width vs depth tradeoff and candidate pipelines selection when parallel evaluations are available appear to be a novel approach to AutoML.

Critical weaknesses
  • Quality of the presentation. First, I wouldn't include mathematical formulas in the Abstract and Introduction. They require formal definitions of all the variables/quantities involved. Rather, it would be better to just give a more intuitive description of those concepts. Furthermore, I think introducing a simple illustrative example of the depth-width tradeoff versus what typical machine learning algorithms are optimised for would help the reader to better understand the contribution. Perhaps as a minor comment, I would stick to the established terminology in AutoML rather than defining/introducing new concepts: for example, a signature is a pipeline configuration, etc.

  • Experimental evaluation. The main paper presents results only on two use-cases: the synthetic power-cusp benchmark and the CTR benchmark (with a brief mention of the NAS benchmark). Although it is good from a pedagogical point of view and illustrates clearly the benefits of the proposed method, I believe that the evaluation is fairly limited. The AutoML literature includes a wide range of benchmarks and datasets.

  • State-of-the-art methods. Along the same line, the experiments include only BO-based methods and random search (the latter is known to be pretty bad). There are many more AutoML search methods in the literature. I think a more comprehensive evaluation against other search methods is warranted.

Questions for authors
  • In Table 1, I'm not sure I read the numbers correctly. If I look at the first line, PWBO needs 2 rounds of 8 parallel evaluations each to find the best configuration. So, basically, it searched 16 configurations. BO and Random Search evaluate pipeline configuration sequentially, so that means they only look at roughly 8 configurations? What is the purpose of the "batch" for these methods?
2 comments

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.

Thank you for the clarification.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their comments. Reviewers found the separation of feedback rounds from evaluation count useful (HkM3) and the presentation clear (THUc). Reviewer THUc confirmed that Q1–Q3 are resolved and appreciated our responses on W2 and W3. Reviewers Y2sM and HkM3 have not yet replied. We summarize the main concerns and our responses below.

1. Theory and PWBO (THUc, HkM3). Theorem 1 is a conditional bound: prior mass affects it through A5. PWBO is designed from the conditions of the bound (Section 5). Relaxing A5 and calibrating the theoretical quantities are left for future work.

2. Wall-clock cost (THUc, HkM3). We added a wall-clock comparison. PWBO takes about 16 and 32 minutes at b=8b=8 and b=4b=4, versus 23 and 50 minutes for πBO. LLM calls take seconds, far less than training. The saving grows when evaluations take longer.

3. Benchmarks and baselines (Y2sM, THUc). Our goal is fewer feedback rounds, not the top rank on AutoML benchmarks. Enumerated spaces let us vary the prior and batch coverage and measure regret exactly. We will add the full six-width table and list larger spaces as future work.

4. Presentation (Y2sM, HkM3). We will describe the main result in words in the Abstract, add a legend to Figure 1, and state the shared batch protocol in the Table 1 caption.

We are happy to answer any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.