acceptodds
Under review as a conference paper at ICLR 2027

Bayesian Optimization with Early Trial Termination for Speeding Up Parallel Neural Network Training

Abstract

Training of large neural networks (NNs) is often done in parallel on multiple GPUs. While existing parallel training frameworks easily allow NN training using multi-dimensional parallelism, the challenge remains in finding the optimal hyperparameters, such as the best balance between the sizes of various parallelism dimensions, which would result in the highest training throughput. Due to the large number of possible parallelism configurations (PCs) for a given training scenario, an exhaustive search over them is prohibitively costly. Existing PC optimization methods either require running NN training trials on a large number of PCs, each of which is costly, or approximate the throughput using only (incomplete) domain knowledge, which may be inaccurate and hardware-specific. To overcome these issues, this paper presents OPPA that can boost the efficiency of Bayesian optimization for optimizing the PC by novelly exploiting (a) the domain knowledge of parallel NN training via parallelism-informed prior beliefs that are general in catering to a variety of parallel NN training scenarios, and (b) early termination of trials involving suboptimal PCs. Despite incorporating these nontrivial efficiency tricks, OPPA is still theoretically guaranteed to achieve sublinear regret. We empirically show that OPPA finds optimal PCs more efficiently than existing methods for parallel training of NNs with varying architectures, training frameworks, and multi-GPU hardware setups.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
bayesian optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_oaC6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents an application of Bayesian optimization (BO) to optimize the parallel training throughput. Since the parallel training is not completely black-box, we can exploit the problem structure to improve the sample efficiency of BO specifically for this application. The authors proposed to exploit the domain knowledge for GP modeling. The experiments showed that the proposed method successfully identifies good configurations.

Critical strengths
  • the paper tries to address an important application
  • the experiments seem to be executed in large scale
Critical weaknesses

The authors should first enhance the presentation quality. The current manuscript is not ready for novelty discussion. The paper maybe presents something novel, but it is hard for me to know how the method is different from existing approaches. Essentially, it is very common to insert the mean and model the residual part only by GP and to use early termination. Therefore, the proposed pipeline looks to me an assemblance of well known promising techniques. If the authors, on the contrary, argue this, please report how experts would usually combine existing techniques and how such combinations fail. I understood that the authors are proposing something, but it is not presented in a way that people know why naively applying existing methods does not work well and how the proposed method circumvents these problems.

The manuscript needs significant revision

The paper is not ready for publication. Please do NOT assume that reviewers will read appendices. They should be supplementary, and we cannot judge the paper correctness if the manuscript heavily depends on appendices given the limited review period. Such paper organization is the authors' responsibility, so defending your manuscript by saying "Look at Appendix X" would not be constructive. I will list the reasons.

First, the design choice is not meaningfully discussed. For example, informed GP prior belief and early trial termination are already known to perform nicely in practice, so my impression on Fig. 7 saying the combination works better than only either of them is no surprise to me. The real question is what people would not come up with easily and why or how it contributes to the performance. Maybe, the way the authors apply GP prior belief or the early trial termination is novel, but no experiments against naive applications are found and I am not sure how exactly the proposed combination is different from a simple combination.

Furthermore, the space is not used well. It is nice to have many figures, but they are mostly very small because some parts are redundant. The background should concisely explain dp, tp, pp. I don't think we need an almost full page for this basic concept considering the tightly packed method and experiment sections. Plus, Fig. 2 is not effectively used. dp, tp, pp could be compacted significantly if Fig. 2 is organized more visually. With the saved space, the relationship to multi-fidelity BO should also be discussed in the main paper. For example, BOHB [1] is likely a good baseline method in this application.

Additionally, there are so many italic and bold characters, making it hard for me to focus which ones are really important. Although it is fine to use italic and bold, their usage should be more focused for readability.

The theoretical analysis assumes i.i.d. Gaussian observations and derives a particular τ\tau. However, the authors set the variable as fixed. Why? Doesn't this invalidate the theoretical guarantee for the claimed method?

References

  • [1] Falkner, Stefan, Aaron Klein, and Frank Hutter. "BOHB: Robust and efficient hyperparameter optimization at scale." International conference on machine learning. PMLR, 2018.
Questions for authors

Questions

  • Please see Critical Weaknesses.

Suggestions

  • Please see Critical Weaknesses.
4 comments
AuthorsOpenReview ↗

Response (Part 1/3)

We thank the reviewer for their review, and their comments regarding how we study a problem that is practically relevant, and how our experiments are executed at large scale. Below, we provide a response to the comments raised by the reviewer.


Essentially, it is very common to insert the mean and model the residual part only by GP and to use early termination...

We note that one of the contributions in our work is adapting BO to parallelism configuration (PC) optimization which, as noted by the reviewer, is an important problem in itself and is worth studying. In this regard, we are able to introduce several modifications to vanilla BO which are specific to the problem of optimizing PCs (e.g., parallelism-informed prior belief, early termination), which together improve the performance of OPPA beyond vanilla BO. We note that the points below are already discussed in the paper, and we indicate where for each of them.

First, while inserting a prior mean is a known idea, realizing it for PC optimization is not straightforward, since it is not obvious what form of the prior belief is suitable for PC optimization. In OPPA, we presented a prior belief function which is able to sufficiently capture the trends within the parallelized training process, while also being general enough to work across a wide range of NNs and hardware setups (see Sec. 4.1). This demonstrates how combining appropriate domain knowledge with real measurements is useful for PC optimization.

Second, the early termination mechanism is novel in that it is able to exploit characteristics of PC optimization in a way that has not been previously considered in other BO works. Existing BO works which use repeated measurements of the same input [1,2,3] fix the number of repetitions up front. This is unsuitable for PC optimization since initializing NN training is costly and rather that it is more efficient to decide the number of training steps on-the-fly during the training loop rather than restarting trials. Meanwhile, stopping criteria for BO [4,5] decide when to terminate the BO loop itself, which is a different stage of the optimization, and are too expensive to run repeatedly during NN training. In contrast, the early termination mechanism exploits the sequential nature of NN training and incurs little overhead. We note that this discussion was already included in App. H. However, an abridged version of this discussion has also been moved to the main text in the last paragraph of Sec. 4.3.

AuthorsOpenReview ↗

Response (Part 2/3)

First, the design choice is not meaningfully discussed. For example, informed GP prior belief and early trial termination are already known to perform nicely in practice, so my impression on Fig. 7 saying the combination works better than only either of them is no surprise to me...

We note that Fig. 7 shows results from our ablation studies to isolate the effect of each proposed efficiency trick on OPPA's performance (Sec. 5), rather than to claim that their combination is surprising. As discussed in our response to the first comment, while inserting a prior mean is a known idea, the form of the prior belief suitable in the case of PC optimization is not clear (Sec. 4.1). Similarly, while techniques similar to our early termination mechanism have previously been studied in other BO contexts, they cannot be naively applied for PC optimization as they are either inefficient or ill-suited for our problem setting, as we have elaborated in App. H. Here, we specifically can note the following:

  1. The measurements that are made are repeated noisy measurements of the same quantity. Therefore, the measured throughput is still used when a trial terminates early, with the variance of the measured throughput being higher due to fewer training steps. This is unlike a multi-fidelity setting where the observations are not repeated noisy measurements of the same quantity, but instead only correlated across different fidelity values.

  2. Our method performs termination during the NN training trial, and proposes a cheap method to determine when this can be done, as the indicator in Eq. 2 only compares the throughput estimate of the current trial with that of the best PC found so far. That is, the early termination mechanism is designed while taking into consideration the characteristics of training trials, which consist of sequential training steps and can be reduced during the actual training run via a quick decision process.

  3. To save time, a trial should be terminated as early as possible once we know the PC is unlikely to be optimal. In practice, we see that the first few training steps are insufficient to decide this due to warm-up effects, and so OPPA always runs at least qminq_{min} steps before deciding whether to terminate the trial (as seen in the condition in Eq. 2). We show that even when we adaptively terminate the training trial early, we are still able to guarantee a regret bound which is sublinear and dependent on qminq_{min} (Theorem 4.1).


Please do NOT assume that reviewers will read appendices. They should be supplementary, and we cannot judge the paper correctness if the manuscript heavily depends on appendices given the limited review period...

We thank the reviewer for this comment. We would like to clarify that the main paper already carefully explains the important points of our work, including the problem formulation (Sec. 3), the design of each component of OPPA (Sec. 4), our main theoretical result (Thm. 4.1) and the experimental results (Sec. 5), and only defers to the appendix for further details (e.g., full proofs and additional experimental results), with appropriate signposts to the relevant sections. This is necessary given the space limitations for the submission (9 pages for the main text), and we hope the reviewer understands. Nonetheless, in the updated paper, we have used the additional page to move more of the important discussion points from the appendix to the main paper, including the comparison of the early termination mechanism with existing methods (from App. H), the choice of the hyperparameters of OPPA (e.g., τq\tau_q and qminq_{min}, from App. G), and the rationale for our choice of baselines and how the best PC is reported (from App. I).


The background should concisely explain dp, tp, pp...

We note that in our paper, we provide a more extensive description (with diagrams) for different types of parallelism as we do not assume the readers are necessarily practitioners who work with parallel NN training already. As we discuss in Sec. 2 (around Line 158), PC optimization differs from typical BO applications since the hyperparameters in a PC affecting the training throughput have better-defined mechanics (even if not completely known) that can be partially described based on domain knowledge, which OPPA exploits through its prior belief (Sec. 4.1). Hence, our paper also aims to be a starting point for BO researchers who may want to consider PC optimization as a novel setting, and to develop techniques that exploit its specific problem structure. Since this requires more knowledge of how each type of parallelism affects the training throughput and memory usage, we have decided to provide more extensive background information in the main paper, while keeping further details in App. A.

AuthorsOpenReview ↗

Response (Part 3/3)

The theoretical analysis assumes i.i.d. Gaussian observations and derives a particular τ\tau. However, the authors set the variable as fixed. Why?

The theoretical choice of τq\tau_q in Thm. F.2 (Eq. 51) depends on the noise standard deviation ss, which is unknown in practice. We therefore fix τq\tau_q to a constant (as stated in Sec. 4.3 of the updated paper). Setting τq\tau_q to a small enough number (in our case, 10−310^{-3}) is sufficient to distinguish between suboptimal PCs. We note that this is in line with other existing BO works [6,7] which typically use fixed constants in place of theoretically optimal values which are difficult to compute in practice, while still maintaining good empirical results. We also see that the choice of τq\tau_q does not affect the sublinear regret in Thm. F.1, meaning the algorithm will still recover the optimum in theory.


We again sincerely thank the reviewer for their efforts during the review process, and hope our clarifications are able to address your concerns and improve your evaluation of our paper.


[1] Picheny et al. Quantile-Based Optimization of Noisy Computer Experiments With Tunable Precision. Technometrics 2013.

[2] Binois et al. Replication or Exploration? Sequential Design for Stochastic Simulation Experiments. Technometrics 2019.

[3] Dai et al. Batch Bayesian Optimization for Replicable Experimental Design. NeurIPS 2023.

[4] Ishibashi et al. A Stopping Criterion for Bayesian Optimization by the Gap of Expected Minimum Simple Regrets. AISTATS 2023.

[5] Wilson. Stopping Bayesian Optimization with Probabilistic Regret Bounds. NeurIPS 2024.

[6] Bogunovic et al. Adversarially Robust Optimization with Gaussian Processes. NeurIPS 2018.

[7] Li & Scarlett. Gaussian Process Bandit Optimization with Few Batches. AISTATS 2022.

Thank you for the comments. Please also check the original review.

it is not obvious what form of the prior belief is suitable for PC optimization the main paper already carefully explains the important points of our work we provide a more extensive description (with diagrams) for different types of parallelism as we do not assume the readers are necessarily practitioners who work with parallel NN training already

Probably, the authors explain important points carefully, but the amount isn't correctly assigned. Importantly, the main body has only 9 pages (& 10 pages during the rebuttal period), so more important points should be more carefully discussed.

About Sec. 4.1, although describes the design (prior decomposition, GP for deviation, R and M forms), and it gives a generic reason for the overall structure, it does not discuss why the specific prior forms were chosen or what alternatives were rejected. If the choice is not obvious, please do explain the rationale in the main body with more space. That is what I said more important.

the early termination mechanism is novel in that it is able to exploit characteristics of PC optimization in a way that has not been previously considered in other BO works.

Same for this part. It's clear where the decision is made and what is measured, but I don't think the delta is informatively discussed in the manuscript. The closest prior works are successive halving and Hyperband, median stopping, and confidence-bound elimination but the authors seem to define Repeated-measurement BO and BO stopping criteria as the closest related work. Essentially, benchmarking is not performed against strong existing baselines such as BOHB or learning-curve extrapolation or freeze-thaw BO. The design choices inside the rule again get little justification.

We note that Fig. 7 shows results from our ablation studies to isolate the effect of each proposed efficiency trick on OPPA's performance (Sec. 5)

The ablation is not meaningful without alternative approaches if the authors really believe that the proposed choices are novel. As mentioned, we already know that each component such as GP mean insertion does work in practice. The whole point is how to build the pipeline. I don't think the pipeline design rationale is fully explained in the main body; hence, the current ablation study is also not self-contained in my eyes.


Overall, my assessment does not change. I strongly recommend major revision.

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

The paper proposed a BO-based optimisation method to find high-throughput parallel configurations under a memory constraint. By introducing the early trial termination mechanism, the proposed method can efficiently improve training efficiency.

Critical strengths
  1. accelerating training within limited memory capbility is a practical and valuable resarch problem.
  2. experiments demonstrate that OPPO, utilising an early-exit mechanism, was still able to identify superior parallel configurations and improve overall throughput in training compared to other solutions.
Critical weaknesses
  1. Increasing the TP, PP and DP degrees linearly/exponentially increases communication costs, whilst linearly/exponentially reducing the computational overhead and memory cost per node; conversely, increasing the batch size linearly increases communication, computational and memory costs. Based on these facts, it is intuitively possible to identify an optimal parallel configuration through empirical modelling. If the relationship between existing parallel configurations, throughput and memory overhead can be modelled empirically, it would challenge the rationale of treating the search space as a complex and intricate black-box and using BO-base method. Therefore, I would kindly ask the author to provide convincing evidences to demonstrate that empirical modelling is unreliable.
Questions for authors
  1. Please clarify what is meant by "estimated" in Figure 9. And explain why it is reasonable to use estimates.
  2. Figure 6 suddenly introduces R(s−1)R(s^{-1}), where other figures use R(P)(s−1)R(P)(s^{-1}). Do they refer to the same thing?
  3. Please list detailed hyperparameters involved in the optimisation of parallel configurations. Although Figure 2 illustrates some of the parallel configurations involved in the optimisation, this is not sufficient to convince the reader that the search space is complex and intricate black-box.
  4. Please carefully establish statement on the novelty and contribution "we are the first to formulate the problem of finding the optimal PC as a black-box optimisation problem with black-box constraints". And clarify the novelty and contribution of this work compared with previous research (e.g. ‘Optimising Distributed Training of Large Language Models on Frontier’ (ISC High Performance 2024)).
3 comments
AuthorsOpenReview ↗

Response (Part 1/2)

We thank the reviewer for their review, and their comments regarding how we study a problem that is practically relevant. Below, we provide a response to the comments raised by the reviewer.


...it is intuitively possible to identify an optimal parallel configuration through empirical modelling. If the relationship between existing parallel configurations, throughput and memory overhead can be modelled empirically, it would challenge the rationale of treating the search space as a complex and intricate black-box and using BO-base method...

We refer to the discussion we have provided in the Related Works section of our paper (particularly around Line 128), where we note that one of the key observations in our paper is that the true throughput of a parallelism configuration (PC) cannot be specified exactly since it is affected by various factors that may not be exactly known. This means that existing cost models or simulations can only provide approximations of the true throughput. In this regard, BO is well suited for this problem since it uses the throughput measurements directly for the optimization process and adaptively selects which configuration should be trialed next. OPPA does model this relationship via the parallelism-informed prior belief (Sec. 4.1), while still using real measurements to correct for the intricacies that the model cannot capture.

This is reflected in our results, where OPPA is able to consistently outperform the other methods. Additionally, we note two other points. First, in practice, there is no one-size-fits-all heuristic that works on all possible hardware. For example, the optimization traces from experiments for Fig. 8b show little difference whether communication overlap is used or not. Meanwhile, as seen in Table 5, while communication overlap may be helpful in some scenarios (e.g., experiments for Fig. 22), it is not helpful in others (e.g., experiments for Fig. 19). Second, using a cost model alone is suboptimal in general since it is unable to capture the NN training on real hardware, as shown by the R&M-Hat baseline (which performs non-adaptive PC optimization via a cost model) and by the comparison in Fig. 9 with [1,2], which both optimize the PC non-adaptively and are outperformed by OPPA.


..."estimated" in Figure 9. And explain why it is reasonable to use estimates.

In the paper, we refer to the estimated throughput as the throughput we obtain based on the training trials we conducted, i.e., the number of training steps divided by their total time over a trial that has been run for all qmax⁡q_{\max} steps (after the outlier removal in App. F.2). We report the estimated value as it is the closest we are able to get to the true throughput, which does not have an analytical form we can use as the ground truth. We also see that this is sufficient since the time per training step stabilizes quickly (Fig. 16), and since the throughputs of all methods are estimated in the same way, the comparison between them remains fair. We thank the reviewer for this comment, and have added an explanation of the estimated throughput to Sec. 5 in the updated paper.


Figure 6 suddenly introduces R(s−1)R(s^{-1}), where other figures use R(P)(s−1)R(P)(s^{-1}). Do they refer to the same thing?

Yes, they refer to the same thing, and RR is used as a shorthand for the throughput R(P)R(P). We have updated the axis labels of Fig. 6 to R(P)R(P) so that the notation is consistent with elsewhere.


Please list detailed hyperparameters involved in the optimisation of parallel configurations. Although Figure 2 illustrates some of the parallel configurations involved in the optimisation, this is not sufficient to convince the reader that the search space is complex and intricate black-box.

We emphasize that we have already included this information in Table 1 in Appendix C.1. We placed it in the appendix due to space constraints, but in the updated paper, we have expanded the description of these hyperparameters in Sec. 3.

From the table, we note that the parallelism configuration does not consist only of the size of each parallelism dimension, but also includes other hyperparameters affecting the throughput as well such as the ZeRO stage used, the virtual pipeline sizes, or even additional parallelism dimensions. Given the feasible values of these hyperparameters, the size of the search space can be in the order of up to 10410^4, already infeasible by exhaustive search.

AuthorsOpenReview ↗

Response (Part 2/2)

Please carefully establish statement on the novelty and contribution "we are the first to formulate the problem of finding the optimal PC as a black-box optimisation problem with black-box constraints". And clarify the novelty and contribution of this work compared with previous research (e.g. 'Optimising Distributed Training of Large Language Models on Frontier' (ISC High Performance 2024)).

We clarify that we do not claim to be the first to formulate PC optimization as a black-box optimization problem. The sentence in Line 89 ("In Sec. 3, we first formulate the problem... Then, we develop surrogate models...") describes the order in which our method is presented, and we have rephrased it ("We begin by formulating...") in the updated paper to avoid this confusion. Indeed, we acknowledge that black-box optimization techniques have already been used for PC optimization (e.g., XGBoost-based autotuning used in DeepSpeed which we compare with in Sec. 5, the BO-based hyperparameter search using DeepHyper in the work raised by the reviewer). However, naively using these methods remains inefficient, as demonstrated by the XGBoost and Vanilla-BO baselines in Sec. 5, the latter of which is similar in spirit to the BO-based search in the work raised by the reviewer.

Instead, the novelty of our work lies in how BO is adapted to PC optimization. As discussed in Sec. 4 and throughout the rest of the paper, we introduce several modifications to vanilla BO which are specific to the problem of optimizing PCs, namely the parallelism-informed prior belief and the early trial termination mechanism, both techniques being novel in PC optimization space. These novel components are constructed specifically with the characteristics of PC optimization problem in mind, and as a result, significantly improve the efficiency of BO in practice (Sec. 5) while maintaining sublinear regret in theory. From this, we would also encourage future methods to follow similar blueprints and incorporate similar considerations.


We again sincerely thank the reviewer for their efforts during the review process, and hope our clarifications are able to address your concerns and improve your evaluation of our paper.


[1] Li et al. AMP: Automatically Finding Model Parallel Strategies with Heterogeneity Awareness. NeurIPS 2022.

[2] Lin et al. nnScaler: Constraint-Guided Parallelization Plan Generation for Deep Learning Training. OSDI 2024.

Thank you to the authors for their response. The authors have addressed most of my concerns, and I have raised my rating to Weak Accept. However, I suggest that the authors should further clarify the fundamental differences between their approach and prior work to better highlight its methodological novelty. Given that the challenges discussed in this paper have already been addressed in previous research, simply expanding the search space or changing the optimisation algorithm can only be regarded as an incremental improvement, rather than a substantive methodological contribution.

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

The authors propose OPPA to novelly exploit parallelism informed prior beliefs and an early trial termination criteria to find configurations with the highest training throughput. The idea is that existing methods largely brute force search through configurations or trials, but OPPA boosts the efficiency of Bayesian optimization. Empirical results aim to establish that OPPA finds configurations more efficiently than existing methods.

Critical strengths
  • The goal is to combine analytical models of computation, communication and memory with a GP that learns their residual errors via training trials. It may be a useful design for parallelism configuration search. The approach aims to address some practical limitations of either a fixed performance model of a general block box optimizer alone.

  • The experiments cover a wide range of models spanning LLMs, VLMs, MoEs, and a wide range of hardware. The hardware variance is particularly meaningful as evidence of practical application. The breath of these experiments is the strongest attribution of this work.

  • The evaluation seeks to be transparent in stating optimization overhead, training initialization, configuration switching, etc. The four way ablation of Fig 7 is helpful.

Critical weaknesses
  • The regret proof is invalid. This is a serious weakness, given for a single round with (q^1=qmin⁡\hat q_1=q_{\min}), it requires $ u\leq \log(1+u),\qquad u>0 $ , hence this step directly produces the claimed 1/qmin⁡1/\sqrt{q_{\min}} dependence in Theorem F.1, so it crucially affects a central guarantee.

  • The theoretical guarantee does not establish recovery by the algorithm. Algorithm 4 selects only previously untried configurations and returns only configurations whose trials complete all steps. Consequently, early termination can permanently exclude a genuinely better configuration from the final recommendation. Algorithm 3, which is analyzed, does not impose the same restriction against revisiting configurations, and its regret concerns all queried points. This distinction significantly weakens the claim that OPPA can recover the optimal configuration.

  • The throughput estimator does not equal the written wall-clock objective. Equation (23) estimates throughput as $ \bar r_q=\frac{1}{q}\sum_{j=1}^{q}\frac{1}{t_j}, $ whereas the number of completed training steps per unit elapsed time is $ r_{\mathrm{wall}}=\frac{q}{\sum_{j=1}^{q}t_j}. $ These quantities can rank configurations differently when step-time variability differs.

Questions for authors
  • Validity under adaptive stopping in Corollary F.1 states unbiasedness and variance s2/qs^2/q for a fixed sample count, but Lemma F.1 applies these results to data-dependent stopping counts q^i\hat q_i. What argument establishes the required confidence bounds under this adaptive stopping rule?

  • Are the plotted throughputs computed using Equation (23), or using completed steps divided by total elapsed time? Do the improvements persist when final configurations are independently evaluated over longer runs using aggregate throughput? Is Figure 5b based on independently measured downstream training trajectories or extrapolation from the short estimates?

  • Does the implementation follow Algorithm 4 in permanently excluding previous configurations and returning only full-length trials? If so, what prevents an optimal configuration from being discarded due to early noise or an improvement smaller than τq\tau_q? How often does this happen in the reported experiments?

  • Why were FlexParallel, Mist, Galvatron, or Shockwave omitted when they are arguably frontier methods in this space?

4 comments
AuthorsOpenReview ↗

Response (Part 1/3)

We thank the reviewer for their review, and their comments regarding our wide range of expriments. Below, we provide a response to the comments raised by the reviewer.


The regret proof is invalid. This is a serious weakness, given for a single round with (q^1=qmin⁡\hat q_1 = q_{\min}), it requires u≤log⁡(1+u)u \le \log(1 + u), u>0u > 0, hence this step directly produces the claimed 1/qmin⁡1/\sqrt{q_{\min}} dependence in Theorem F.1...

We thank the reviewer for spotting this error in bounding ∑i=1Nσi−12(xi)\sum_{i=1}^N \sigma^2_{i-1}(x_i) in the proof of Thm. F.1 (Eqs. 37-40 in the updated paper). This step can be fixed by additionally assuming k(x,x)≤1k(x,x) \le 1, which we have added to Assumption F.1, in line with the other assumptions which follow from other BO works [1,2,3]. With this, the corrected bound is βN8qmax⁡NγN/(qmin⁡log⁡(1+qmax⁡/s2))\beta_N \sqrt{8 q_{\max} N\gamma_N/(q_{\min}\log(1+q_{\max}/s^2))}, which is still sublinear in NN with the same 1/qmin⁡1/\sqrt{q_{\min}} dependence. We have corrected Thm. F.1 (with the full derivation) and Remark F.1 accordingly in the updated paper, while the rate in Thm. 4.1 remains unchanged.


Algorithm 4 selects only previously untried configurations and returns only configurations whose trials complete all steps. Consequently, early termination can permanently exclude a genuinely better configuration from the final recommendation. Algorithm 3, which is analyzed, does not impose the same restriction against revisiting configurations...

We see from the second part of Thm. 4.1 (proven in Thm. F.2 using Lemma F.2) that, with high probability, any PC whose throughput is lower than that of the best PC found so far will have its trial terminated early. Also, if the trial of PiP_i is terminated early then PiP_i is unlikely to be much better than the best PC found so far (by Lemma F.2), and so can be excluded. This is the main intuition behind the early termination mechanism, as it filters out PCs that are unlikely to be much better than the best PC found so far. Note that even when a trial is terminated early, its measured throughput is still informative as it still provides an estimate for the true throughput (albeit with higher variance).

We note that Algorithm 3 is intended as a simplified version of Algorithm 4 to aid the conceptual understanding of the early termination mechanism and its theoretical analysis. Algorithm 4 avoids revisiting previously trialed PCs since the time required for initializing NN training is high (and often larger than the time per training step). In the updated paper, we have clarified this in App. F.3.2 and App. G.

AuthorsOpenReview ↗

Response (Part 2/3)

The throughput estimator does not equal the written wall-clock objective. Equation (23) estimates throughput as rˉq=1q∑j=1q1tj\bar r_q = \frac{1}{q}\sum_{j=1}^q \frac{1}{t_j}, whereas the number of completed training steps per unit elapsed time is rwall=q∑j=1qtjr_{\text{wall}} = \frac{q}{\sum_{j=1}^q t_j}. These quantities can rank configurations differently when step-time variability differs.

We thank the reviewer for this observation. We clarify that our theoretical analysis considers E[1/T]E[1/T] rather than 1/E[T]1/E[T] since it requires each training step to give a noisy measurement of the same quantity, such that the mean estimator is unbiased with variance s2/qs^2/q (Assumption F.1 and Corr. F.1). Computing the mean of 1/ti,j1/t_{i,j} satisfies this, as rˉi,q\bar r_{i,q} can then be viewed as an unbiased estimator of the reciprocal of the time per training step, and so is consistent with the theoretical results. Also, in App. F.1 of the updated paper, we show that the two quantities differ only by a small factor that depends on how much the time per training step fluctuates. As the time per training step fluctuates little (Fig. 16), both quantities would rank the PCs similarly in practice.


Validity under adaptive stopping in Corollary F.1 states unbiasedness and variance s2/qs^2/q for a fixed sample count, but Lemma F.1 applies these results to data-dependent stopping counts q^i\hat q_i. What argument establishes the required confidence bounds under this adaptive stopping rule?

We thank the reviewer for raising this point. We clarify that the confidence bound in Lemma F.1 holds for the data-dependent q^i\hat q_i, even though whether a trial is terminated depends on the measurements observed so far. This is because the same bound can be obtained by applying Lemma 7 in [3] to the individual training steps instead, which give the same GP posterior as in Eqs. 25 and 26. The lemma then only requires the noise of each training step to be sub-Gaussian conditioned on the previous measurements, which holds by Assumption F.1. In light of the comment by the reviewer, we have added a clarification after the proof of Lemma F.1 in the updated paper to explain this point.


Are the plotted throughputs computed using Equation (23), or using completed steps divided by total elapsed time? Do the improvements persist when final configurations are independently evaluated over longer runs using aggregate throughput? Is Figure 5b based on independently measured downstream training trajectories or extrapolation from the short estimates?

We clarify that, in our implementation, the plotted throughputs are computed as the number of training steps divided by their total time (after the outlier removal in App. F.2), as indicated by "best (estimated) measured throughput" in the figure captions. As mentioned above and now stated in App. F.1 of the updated paper, this differs from Eq. 23 by a small factor, especially since the plotted throughputs only come from trials which have been run for all qmax⁡q_{\max} training steps. For example, across all trials in our experiments with Qwen2-1.5B on 8 GPUs, the two quantities differ by at most 1.3% (with a median of 0.004%). We also see that the time per training step stabilizes quickly, as seen in Fig. 16 (App. G), where after a certain point (even before reaching qmax⁡q_{\max}) a larger number of repeats will typically not have large effects on the estimated throughput of a PC. Hence, we expect the estimated throughput to be representative of the true training throughput as well.

Regarding Fig. 5b, the number of training steps in the subsequent parallel NN training (unshaded region) is extrapolated from the estimated throughput of the PC returned by each method, rather than measured from an independent training run. We are able to do so since, as described above, the time per training step does stabilize quickly. We have made this clear in the caption of Fig. 5b in the updated paper.

AuthorsOpenReview ↗

Response (Part 3/3)

Why were FlexParallel, Mist, Galvatron, or Shockwave omitted when they are arguably frontier methods in this space?

As stated in Sec. 5 of the updated paper (moved up from App. I.2), the methods we compare with are those which rely on measurements from short training trials, whereas Galvatron [6] and Mist [7] (using a cost model and a symbolic performance model, respectively), like AMP [4] and NNScaler [5], belong to the class of methods which only rely on constructing an approximation of the training throughput. These methods optimize the PC non-adaptively and tend to also operate on a different representation of PC, making them difficult to compare with OPPA. As discussed in Secs. 1 and 2 (around Lines 53 and 136), they may not capture all the complex intricacies of parallel NN training. Nonetheless, we include AMP and NNScaler as representative methods of this class in Fig. 9, where OPPA outperforms them, as it is able to adaptively select promising PCs using the measured throughputs from real NN training trials. Meanwhile, Shockwave [8] is orthogonal to OPPA since it is a cluster scheduler, which decides how GPUs are allocated across multiple training jobs whose throughput changes over time, while OPPA optimizes the PC of a single training job given the allocated GPUs. Lastly, FlexParallel is, to the best of our knowledge, a concurrent work which does not realize them in the same way as OPPA's parallelism-informed GP prior beliefs (Sec. 4.1) and early trial termination mechanism within the training loop (Sec. 4.3).


We again sincerely thank the reviewer for their efforts during the review process, and hope our clarifications are able to address your concerns and improve your evaluation of our paper.


[1] Srinivas et al. Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting. IEEE Transactions on Information Theory, 2012.

[2] Makarova et al. Risk-averse Heteroscedastic Bayesian Optimization. NeurIPS 2021.

[3] Kirschner & Krause. Information Directed Sampling and Bandits with Heteroscedastic Noise. COLT 2018.

[4] Li et al. AMP: Automatically Finding Model Parallel Strategies with Heterogeneity Awareness. NeurIPS 2022.

[5] Lin et al. nnScaler: Constraint-Guided Parallelization Plan Generation for Deep Learning Training. OSDI 2024.

[6] Miao et al. Galvatron: Efficient Transformer Training over Multiple GPUs Using Automatic Parallelism. VLDB 2023.

[7] Zhu et al. Mist: Efficient Distributed Training of Large Language Models via Memory-Parallelism Co-Optimization. EuroSys 2025.

[8] Zheng et al. Shockwave: Fair and Efficient Cluster Scheduling for Dynamic Adaptation in Machine Learning. NSDI 2023.

I thank the authors for the rebuttal, and apologize for my late response. I have carefully gone over the revised upload.

While this discussion and rebuttal has been valuable, I do agree that the presentation and organization of this paper needs heavy revision. It is very difficult to follow, for example presenting algorithm 3 as a version of algorithm 4 is confusing. It reads as over-claiming on the contributions of the work, which is not explicitly presented in the first place.

The numerous subsections and appendix subsections that follow is also not realistic for a reader. The error on the regret proof is worrisome, in terms of trust and carefulness when approaching the manuscript. Therefore I shall maintain my score, thank the authors for their work, and encourage a clearer revision that can lead to novelty and contribution discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.