acceptodds
Under review as a conference paper at ICLR 2027

CATOS: Compute–Accuracy Tradeoff Scalarization for Multiobjective Optimization in Neural architecture Search

Abstract

Neural architecture search (NAS) increasingly targets deployment on resource-constrained hardware such as mobile devices or edge accelerators, where accuracy must be weighed against efficiency metrics such as latency or FLOPs, motivating multiobjective optimization (MOO). Existing MOO methods for NAS rest on Pareto dominance, which induces only a partial ordering: whenever one architecture is more accurate and another more efficient, the two are incomparable, preventing a consistent ranking of tradeoffs across the search space. As a result, existing multiobjective NAS methods rely on heuristic ranking strategies built on Pareto-based indicators, which provide only indirect signals of tradeoffs and are sensitive to the sampled set of architectures. To address these limitations, we introduce CATOS (Compute-Accuracy Tradeoff Scalarization), a scalarization function built on novel mathematical constructs that ranks architectures under bi-objective tradeoffs and remains effective in low-sample regimes by leveraging a compute-accuracy scaling prior. Integrated into an evolutionary algorithm (CATOS-EA), our method outperforms state-of-the-art MOO algorithms as well as constrained approaches on NATS-Bench in nearly all settings. Notably, the constructs underlying CATOS transfer unchanged to the markedly different NLP benchmark HW-GPT-Bench, where the augmented CATOS outperforms the strongest baseline.

Primary area:
optimization
Keywords:
neural architecture search, multi-objective optimization, scalarization, efficiency

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_ErkmOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the trade-off between accuracy and computational cost in neural architecture search. Since Pareto dominance alone cannot rank architectures with different trade-offs, the authors propose CATOS, which constructs reference boundaries from observed architectures and fits curves to score each architecture by its relative distance to them. The score is used for parent and survival selection. The paper reports results on NATS-Bench and evaluates a version on HW-GPT-Bench.

Critical strengths

Many conventional multi-objective methods select solutions based on dominance relations and the distribution of the current solution set. CATOS instead tries to infer a structural relationship between the objectives from observed solutions and uses it to guide the search. I think this idea is meaningful.

Critical weaknesses
  1. The novelty of some geometric constructs is unclear. Local ideal points, for example, have been used in earlier studies. The paper could clarify which parts of CATOS are new.
  2. The paper does not sufficiently discuss the robustness of its power-law fit.
  3. Selecting by a single score may reduce population diversity. The use of additional coverage terms on HW-GPT-Bench raises the question of whether this is also a concern on NATS-Bench.
  4. The wall-clock analysis is limited to a comparison with NSGA-II.
Questions for authors
  1. CATOS uses a single score for parent and survival selection, which may concentrate the population in a narrow region and reduce diversity. On HW-GPT-Bench, the authors add coverage terms to Linear CATOS. Is this intended to address a diversity issue? Could the original CATOS face the same issue on NATS-Bench? Why is a coverage term not needed on NATS-Bench?
  2. The fitted curves assume a power-law cost–accuracy relationship. If this assumption does not hold, errors in the curves could change how architectures are ranked. How would this affect the final search results?
  3. Appendix B reports wall-clock time only for CATOS-EA and NSGA-II, with CATOS-EA taking longer. How does it compare with the other baselines? Apart from the implementation differences noted in the paper, what accounts for the additional runtime?
2 comments

We thank the reviewer for finding CATOS’s corridor-based ranking meaningful for its structural relationship between the objectives.

[W1] The paper could clarify which parts of CATOS are new, since local ideal points have been used in earlier studies.

To the best of our knowledge, local ideal points, the ideal front, the negative Pareto front and the Pareto corridor are all novel in multiobjective optimization (lines 79-80). We assume the reviewer refers to local upper bounds [1]. Local ideal points share a similar construction but are the opposite point for consecutive Pareto points: For consecutive Pareto points yi,yi+1y^i, y^{i+1} with y1i<y1i+1y^i_1 < y^{i+1}_1 (minimization setting):

Local upper bound: ui:=(y1i+1,y2i)=max⁡{yi,yi+1}\quad \quad \quad \quad u^i := (y^{i+1}_1, y^{i}_2) = \max\{y^i, y^{i+1}\}

Local positive ideal point: ℓi+:=(y1i,y2i+1)=min⁡{yi,yi+1}\quad \ell^{i+} := (y^{i}_1, y^{i+1}_2) = \min\{y^i, y^{i+1}\}

(with max⁡/min⁡\max / \min taken componentwise)

Since each uiu^i is dominated by both yiy^i and yi+1y^{i+1} and each ℓi+\ell^i+ dominates both, the local positive ideal points form a best-case envelope of the positive front.

If the reviewer meant something else, could a reference be shared?

[1] Klamroth et al. "On the representation of the search region in multi-objective optimization." European Journal of Operational Research 245.3 (2015): 767-778.

[Q3 and W4, part 1] How does CATOS compare in wall-clock time with other baselines except NSGA-II (Appendix B)?

We agree a computationally heavier baseline than NSGA-II would strengthen the comparison, and add NSGA-III with its heavier reference-point selection. We also optimized CATOS, vectorizing the scoring, and reran the wall-clock comparison against both baselines at a much larger scale (~1M architectures). The search runs in the OFA MobileNetV3 space, which we found has the smallest framework overhead, optimizing predicted ImageNet accuracy against Note10 latency (population 300, 80 children per generation), repeated 5 times. All algorithms share every component except parent selection and survival, isolating the optimizer itself.

MethodRuntime (s)
CATOS-EA267.3 ± 1.7
NSGA-II (pymoo)239.0 ± 4.3
NSGA-III (pymoo)272.5 ± 1.3

CATOS-EA is only ~12% slower than NSGA-II and slightly faster than NSGA-III, with negligible overhead per generation. This replaces the original runtime experiment (unoptimized CATOS) in Appendix B of the revised manuscript.

~0.27 ms (new) vs. ~0.6 s per architecture (old), from batching, fast objective retrieval and vectorized scoring.

[Q3 and W4, part 2] Apart from the implementation differences noted in the paper, what accounts for the additional runtime?

The dominating costs in CATOS are curve-fitting and distance calculation (scoring), the latter especially depending on an efficient implementation.

[W3 and Q1] Selecting by a single score may reduce population diversity. For HW-GPT-Bench additional coverage terms are used. Why is a coverage term not needed on NATS-Bench?

We thank the reviewer for pointing this out! We didn't observe improvements in coverage-sensitive metrics (hypervolume regret and ε-indicator) for CATOS-EA on NATS-Bench, when augmenting it with coverage signals. If the scaling prior fits the Pareto front well, each model is scored similarly to its tradeoff, thus selection is not biased towards any region. On HW-GPT-Bench, the denser front and larger budget (Section 4.4) produce many candidates with near-identical scores, so explicit coverage signals are needed to maintain spread.

[Q2] If power-law cost–accuracy does not hold, how would this affect the final search results?

If the power law does not fit the fronts well, closeness to the front is no longer scored uniformly, which can concentrate the search on a subregion of the objective space or flatten scores across models and slow convergence. This is avoided by the linear interpolation fallback, which is assumption-free and adapts to the shape of the Pareto fronts. This is shown by the new result in Figure 2 of the revised document, where linear CATOS outperforms CATOS with scal. prior, both without coverage.

[W2] The paper does not sufficiently discuss the robustness of its power-law fit.

We fully agree robustness deserves a clear treatment, and note the submission provides evidence along three lines. First, in the low-sample regime the scaling prior outperforms general interpolators (RBF, linear) (Table 4). Second, a warm-start analysis (Tables 9 and 10; 7 and 8 in the original submission) tests sensitivity to poor initialization: runs with the worst initialization (low initial hypervolume) show the largest hypervolume gains, indicating robustness. Third, Section A.2 discusses curve-fitting rare failure cases that resolve as more models are sampled. If a particular aspect is not covered here, we would gladly investigate further.

Thank you for the response. I will maintain my original score.

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

The paper proposes CATOS, a scalarisation function that enables NAS methods to rank architectures across two objectives. This ranking provides search algorithms more information than Pareto dominance, under which architectures are often mutually incomparable and is less sensitive to the particular set of sampled Pareto-optimal solutions. To compute a score that captures the compute-accuracy trade-off, the authors introduce concepts such as negative Pareto dominance and the Pareto corridor. When integrated into an evolutionary algorithm, CATOS outperforms both evolutionary and differentiable NAS methods under given compute constraints.

Critical strengths

[S1]: The paper proposes an interesting technique to rank Pareto-optimal architectures. It builds on new constructs for this purpose, such as the negative Pareto front, local ideal points and the Pareto corridor, which gives an interesting perspective on the ranking problem.

[S2]: The proposed technique remains competitive at lower computing budgets. This makes the technique particularly interesting for computationally constrained deployment settings.

[S3]: The papers is clearly written and easy to understand.

[S4]: The author is extensively transparent about their use of AI throughout the entire research proces, which is very appreciated by the reviewer.

Critical weaknesses

[W1] The graph-fitting procedure for the upper front seems to be computationally expensive and its overhead is not clearly characterised. Although the authors provide a wall-clock comparison against NSGA-II, the actual cost of the fitting operation remains unclear. It would be interesting to see whether this operation is a constant overhead or grows as function of the number of architectures during search for example.

[W2] The HW-GPT-Bench comparison is under-described. The paper gives little detail on the experimental setup. The authors presumably wanted to show general applicability, but the experiment feels out of place in the paper. Moreover, a different prior is used for the curve fitting, which weakens general applicability of the technique.

[W3]: As briefly discussed by the authors in Section A.1, extending the technique beyond two objectives would have substantially strengthened the submission. Also, this makes the comparison in Table 1 less fair, as all of the techniques do support more than 2 objectives.

[W4] The authors have not released their code, nor do they mention that it will be made publicly available, making it more difficult to verify their claims.

Questions for authors

[Q1] Were all SOTA baselines in Table 1 also repeated 100 times or were different numbers of runs used? Several baselines report a standard deviation of 0.00.

[Q2] ConNAS and TF-NAS appear to do better under the peak-memory constraint in the size space. Do the authors know why CATOS-EA does not outperform them in all cases?

[Q3] Some SOTA algorithms used in Table 1 are highly sensitive to hyperparameters. How were the hyperparameters of the baselines chosen?

[Q4] Section 4.3 uses the 25th/75th-quantile restriction, while Section 4.2 does not. What's the reason behind that? It seems a little bit weird to me to evaluate it that way. Also, I assume the filtering is only done for evaluation purpose and not something that you would do in real deployment (as this requires the knowledge of the entire search space).

[Q5] How were the budgets in Table 2 and 3 defined?

[Q6] In Section 4.4, the authors state that the power-law fit is most beneficial in low-sample regimes. Could they demonstrate this (with a dummy problem)?

5 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

We thank the reviewer for finding our approach and constructs novel and interesting, our technique relevant for computationally constrained deployment, our paper well written and easy to follow, and our AI-usage disclosure transparent.

[W1, part 1] Although the authors provide a wall-clock comparison against NSGA-II, the actual cost of the fitting operation remains unclear.

We agree that the previous experiment was not optimal to isolate that cost. To characterize the fitting and scoring overhead at scale, we vectorized the scoring and reran the wall-clock comparison over ~1 million architectures, against NSGA-II and NSGA-III (pymoo), a heavier baseline, since its reference-point selection costs more per generation than NSGA-II’s crowding distance.

Setting: The search runs in the OFA MobileNetV3 space, which we found has the smallest framework overhead, optimizing predicted ImageNet accuracy against Note10 latency (population 300, 80 children per generation), repeated 5 times. All algorithms share every component except parent selection and survival, isolating the optimizer itself.

MethodRuntime (s)
CATOS-EA267.3 ± 1.7
NSGA-II239.0 ± 4.3
NSGA-III272.5 ± 1.3

CATOS-EA is only ~12% slower than NSGA-II and slightly faster than NSGA-III, with a negligible overhead per generation. This replaces the original runtime experiment (unoptimized CATOS) in Appendix B of the revised document.

~0.27 ms (new) vs. ~0.6 s per architecture (old), from batching, fast objective retrieval and vectorized scoring.

[W1, part 2] The graph-fitting procedure for the upper front seems to be computationally expensive and its overhead is not clearly characterised. It would be interesting to see whether this operation is a constant overhead or grows as function of the number of architectures during search for example.

The least-squares curve-fitting procedure only scales with the amount of models on the Pareto front. The full NATS-Bench topology benchmark with 15,625 models has 13-35 Pareto front models, depending on the cost objective and dataset, making the curve-fitting computationally inexpensive.

[Q6] In Section 4.4, the authors state that the power-law fit is most beneficial in low-sample regimes. Could they demonstrate this (with a dummy problem)?

We agree a demonstration is valuable! Rather than a synthetic problem, we extend the original ablation (Table 4) to high budget (Table 5, revised document), as we felt it would be more convincing. For low budget, the scaling prior outperforms linear and RBF fits, while for high budget we expect the linear fit to close the gap, as a purely data-driven fit. We follow the same setup and evaluation of the original ablation, but with an initial population of 50 and 500 total evaluations.

Setting: NATS-Bench topology; Δacc and Δlat are regrets (lower is better); GT-PF is the share of the ground-truth Pareto front found on the filtered set (higher is better).

MetricMethodC-10C-100IN
Δacc (pp) ↓RBF0.22 ± 0.310.30 ± 0.321.11 ± 0.40
Linear0.07 ± 0.080.21 ± 0.260.99 ± 0.50
CATOS0.15 ± 0.250.22 ± 0.221.04 ± 0.50
Δlat (ms) ↓RBF1.4 ± 1.10.5 ± 0.40.6 ± 0.6
Linear0.5 ± 0.70.3 ± 0.30.5 ± 0.5
CATOS0.5 ± 0.60.4 ± 0.30.5 ± 0.5
GT-PF (%) ↑RBF13.42 ± 9.9716.31 ± 11.5819.14 ± 8.38
Linear25.42 ± 8.3221.69 ± 15.2420.62 ± 8.44
CATOS25.21 ± 9.3920.38 ± 13.0719.67 ± 8.69

The scaling prior stays clearly ahead of RBF on all metrics. In the higher budget, the linear fit however catches up and is marginally ahead, which shows that the prior helps most when data is scarce and converges to the purely data-driven fit as the budget grows.

[Q4] Why does Section 4.3 use the 25th/75th-quantile restriction, while Section 4.2 does not? It seems a little bit weird to me to evaluate it that way. I assume the filtering is only done for evaluation purpose and not something that you would do in real deployment (as this requires the knowledge of the entire search space).

Yes, the filtering is purely for evaluation purposes and only applies to the set-based metrics (hypervolume regret, ε-indicator, GT pareto points), not the constrained regret evaluations in Tables 1 and 3. Our reasoning is that set-based metrics reward coverage over the whole objective space, including regions where a small accuracy gain comes at a large latency cost. Q25/Q75 restricts them to the deployment-relevant band, where the accuracy–latency tradeoff is reasonable, and it works as a set-wise counterpart of pure constrained evaluation.

[Q5] How were the budgets in Table 2 and 3 defined?

Budgets in Tables 2 and 3 count models evaluated for both accuracy and cost. Low/mid/high budgets are 60/300/500 evaluated models (lines 317–319), and are consistent across the paper and appendix.

AuthorsOpenReview ↗

Rebuttal (2/2)

[W3]: As briefly discussed by the authors in Section A.1, extending the technique beyond two objectives would have substantially strengthened the submission. Also, this makes the comparison in Table 1 less fair, as all of the techniques do support more than 2 objectives.

We agree an extension beyond two objectives would strengthen the submission, but the biobjective scope was deliberate for CATOS’s target setting, namely efficient deep learning, where cost and accuracy are the dominant objectives [1]. The constructs are not inherently limited to two objectives: negative Pareto dominance and the negative Pareto front are already defined for general dimension, and extending local ideal points and the Pareto corridor is concrete future work (Section A.1). While the constr. diff. methods handle several constraints at the same time, each search is fixed to one constraint configuration and re-run per configuration. CATOS-EA searches once, constraint-agnostic, serving all constraints in Table 1 simultaneously from that single run and recovering each result post-hoc from the same front.

[1] Tan, Mingxing, and Quoc Le. "Efficientnet: Rethinking model scaling for convolutional neural networks." ICML 2019.

[Q2] ConNAS and TF-NAS appear to do better under the peak-memory constraint in the size space. Do the authors know why CATOS-EA does not outperform them in all cases?

Good question! The gap comes from our evaluation protocol. For fairness, CATOS-EA is run once per dataset/search-space, and each constraint’s result is read off that single run post-hoc rather than re-optimized per constraint (Section 4.2). The constrained differentiable approaches instead optimize directly for peak memory, where they often reach the highest accuracy, so edging out CATOS-EA there is expected. Even so, CATOS-EA stays very close to the optimal model under this objective.

[Q1+Q3] Were all SOTA baselines in Table 1 also repeated 100 times or were different numbers of runs used? Several baselines report a standard deviation of 0.00. Also, some SOTA algorithms used in Table 1 are highly sensitive to hyperparameters. How were the hyperparameters of the baselines chosen?

We thank the reviewer for raising this point. The constrained differentiable results in Table 1 originate from the ConNAS [2] paper and were repeated 5 times. Using their exact configuration felt like the fairest comparison. We added this information to Section 4.2 in the revised paper.

[2] Ruyter et al. Constraint-guided hardware-aware nas through gradient modification. ICLR 2026.

[W2, part 1] The HW-GPT-Bench comparison is under-described. The paper gives little detail on the experimental setup.

We agree that some settings of the HW-GPT-Bench experiment deserve a more detailed description and have updated the revised version accordingly (Section 4.1 in HW-GPT-Bench protocol and Section 4.4). In summary: We search the GPT-S space of HW-GPT-Bench. For mutation each architectural choice is resampled with probability 0.10.1. Hypervolume is computed every 100 evaluations on each run's cumulative non-dominated set, with objectives min–max normalized to [0,1][0,1] across runs and reference point (1.1,−0.1)(1.1, -0.1). The rank-sum replaces the CATOS score, meaning everything else about the algorithm is unchanged, including the tournament selection described in Section 3.3.

[W2, part 2] The authors presumably wanted to show general applicability, but the experiment [HW-GPT] feels out of place in the paper. Moreover, a different prior is used for the curve fitting, which weakens general applicability of the technique.

The HW-GPT benchmark was chosen precisely because it differs from NATS-Bench along as many axes as possible: a partitioned search space, perplexity rather than accuracy, a high model budget, and a dense Pareto front. The aim is to show that CATOS’s constructs and corridor-based scoring carry over to such a different setting, and that CATOS, while already guiding search strongly on its own on NATS-Bench, also combines cleanly with coverage signals when the setting requires it. On the prior: The linear interpolation is a deliberate fallback for when no scaling prior fits, serving as a reasonable, unbiased default. This is exactly what the HW-GPT experiment is intended to demonstrate: that CATOS holds up even in the absence of a scaling prior.

[W4] The authors have not released their code, nor do they mention that it will be made publicly available, making it more difficult to verify their claims.

We thank the reviewer for raising this. The inference and evaluation code built on naslib will be made public, which we added to the revised document (lines 72-73). We would like to highlight that the supplementary material contains the code for CATOS, how it is embedded in the EA and how it's augmented with the coverage signals in Figure 2.

If our responses leave any raised concerns unaddressed, we would be glad to take them up during the discussion period.

I would like to thank the authors for their responses to my questions and further clarification. However, I have one point that remains unclear.

What is the overhead of the curve-fitting operation proposed by CATOS itself, i.e. measured in isolation rather than as total wall-clock time compared against state-of-the-art methods? Also, the 13–35 Pareto front models cited correspond to the ground-truth front of the full benchmark. However, the curve is fitted to the front observed during search (which differs from that count) and Section A.1 states that each front update triggers rescoring of all sampled models. Could the authors report fitting and scoring time as a function of the number of evaluated architectures or the current front size?

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

The paper proposes CATOS: it scores each model based on its related distance to fitter upper and lower envelopes in the accuracy-compute space. More precisely, these envelopes are fitter using local ideal points and negative Pareto front, respectively. The resulting scalar score is used to guide evolutionary architecture search.

Critical strengths
  • The paper compares against sufficiently many related methods and benchmarks.

  • the method is motivated by the important, realistic objective of working with a very limited number of observations.

Critical weaknesses
  • The basic idea of ranking solutions according to their distance from reference fronts is not fundamentally new.

  • The first six pages are largely devoted to motivating and formalizing CATOS, although the novelty of the approach seems limited.

  • The ablation in Sec. 4.5 primarily tests how the reference curves are fitted, but not whether the newly introduced geometric constructions are better than simpler alternatives.

  • The power-law used to smooth upper and lower envelopes from few architectures imposes a strong assumption on the shape of these envelopes, potentially introducing bias.

  • The paper lacks direct comparisons with standard multi-objective indicators used to guide evolutionary search, such as hypervolume, under the same evolutionary framework.

Questions for authors

Q1) The paper uses a power-law fit on NATS-Bench, but seems to use piecewise-linear interpolation on HW-GPT-Bench. Doesn't the necessity to make this choice limit the generality of the method, since the shape of the Pareto Front is not known in advance ?

Q2) Is the proposed scalar sufficient to preserve diversity along the Pareto front (which standard methods like NSGA-II will do) ?

Q3) Why is it necessary to combine the proposed score with additional diversity and coverage indicators (hypervolume and nearest-neighbor distance) on HW-GPT-Bench? Could the authors report the performance of CATOS alone on this benchmark ?

Q4) Is the proposed scalar score guaranteed to preserve Pareto dominance? Could a dominated architecture receive a higher score than an architecture that dominates it?

Q5) Are the methods in the benchmarks compared under equivalent computational search budgets ?

4 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

We thank the reviewer for recognizing that our approach is well motivated by low-budget NAS and that we compare against a broad set of related methods and benchmarks.

[Q4] Is the proposed scalar score guaranteed to preserve Pareto dominance? Could a dominated architecture receive a higher score than an architecture that dominates it?

We thank the reviewer for raising this point! Yes, the score preserves Pareto dominance: a dominated point cannot receive a higher score than the point that dominates it. This is because its distance to the positive curve cannot be smaller than that of the dominating point, and its distance to the negative curve cannot be larger.

Distance to positive curve: Since we constrain α\alpha and β\beta to be positive, the scaling prior g(cost)=100−β∗cost−αg(cost) = 100 - \beta * cost^{-\alpha} is strictly monotonically increasing. Given Q is being dominated by P, this means costQ≥costPcost_Q \geq cost_P and accQ≤accPacc_Q \leq acc_P. Since g is increasing, g(costQ)≥g(costP)g(cost_Q) \geq g(cost_P), so g(costQ)−accQ≥g(costP)−accPg(cost_Q) - acc_Q \geq g(cost_P) - acc_P. This means the signed y-distance of P is always smaller than the one of Q.

Distance to negative curve: Same argumentation as above, but the signed y-distance of P to the negative curve is bigger than of Q.

Transfer to shortest euclidean distance (as used in CATOS): The same reasoning carries over to the shortest euclidean distance, which is measured along the curve's normal. For an increasing curve, the normal points toward lower cost and higher accuracy, which is the direction in which P improves on Q. Moving from P to Q therefore goes against the normal, so Q's distance to the positive curve is at least P's, and its distance to the negative curve is at most P's.

[W5] The paper lacks direct comparisons with standard multi-objective indicators used to guide evolutionary search, such as hypervolume, under the same evolutionary framework.

In table 9/10 of the submission (Table 11/12 revised version), we compare with hypervolume and crowding distance as scalarization alternatives in the same EA framework. While hypervolume remains a strong baseline, CATOS shows consistent improvements with few exceptions, especially in regret to optimal accuracy/latency.

[W3] The ablation in Sec. 4.5 primarily tests how the reference curves are fitted, but not whether the newly introduced geometric constructions are better than simpler alternatives.

We agree, and target this at the local ideal points in Table 6 (revised document), as the corridor-based scoring does not depend on them. The negative Pareto front, by contrast, supplies the lower reference curve (g−g^-) every CATOS score is computed against. Removing it would leave scores unbounded rather than in [0,1][0,1], replacing the scoring function rather than ablating a component. Following the protocols of Tables 2 and 3, removing the ideal points degrades performance on 35 of 45 cells, with 6 ties and 4 losses, mostly in the near-saturated regime, confirming they are a valuable component of CATOS.

[W1] The basic idea of ranking solutions according to their distance from reference fronts is not fundamentally new.

We agree that distance-based ranking is not new in itself. What sets CATOS apart is its corridor-based scoring, in which the fitted or interpolated fronts themselves determine the ranking. On NATS-Bench, this single scalar replaces dominance-based ranking entirely. Unlike other approaches, the score derives from each candidate's nearest-point distance to the continuous fronts, with the negative Pareto front as the lower reference, not from distances to discrete points, such as non-dominated solutions or reference points [1,2,3], or distances to or along a direction toward a global ideal or nadir point [4,5,6].

[1] Li, Chunlei, et al. "An indicator-based many-objective evolutionary algorithm with adaptive reference points assisted by growing neural gas network." IEEE Transactions on Emerging Topics in Computational Intelligence (2024).

[2] Tian, Ye, et al. "A multi-objective evolutionary algorithm based on an enhanced inverted generational distance metric." 2016 IEEE congress on evolutionary computation (CEC). IEEE, 2016.

[3] Zitzler, Eckart, and Simon Künzli. "Indicator-based selection in multiobjective search." International conference on parallel problem solving from nature. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004.

[4] Tian, Ye, et al. "Guiding evolutionary multiobjective optimization with generic front modeling." IEEE transactions on cybernetics 50.3 (2020): 1106-1119.

[5]Yuan, Yuan, et al. "A new dominance relation-based evolutionary algorithm for many-objective optimization." IEEE Transactions on Evolutionary Computation 20.1 (2016): 16-37.

[6] Hwang, Ching-Lai and Kwangsun Yoon. “Multiple Attribute Decision Making: Methods and Applications - A State-of-the-Art Survey.” Lecture Notes in Economics and Mathematical Systems, vol. 186. Springer, 1981.

AuthorsOpenReview ↗

Rebuttal (2/2)

[Q2 + Q3, part 1] Is the proposed scalar sufficient to preserve diversity along the Pareto front (which standard methods like NSGA-II will do)? Why is it necessary to combine the proposed score with additional diversity and coverage indicators (hypervolume and nearest-neighbor distance) on HW-GPT-Bench?

It depends on front density, and we observe both regimes. In the lower sample regime of NATS-Bench, CATOS maintains coverage on its own: augmenting it with coverage signals did not improve the coverage-based metrics (hypervolume, ε-indicator). On the much denser HW-GPT-Bench front, many candidates receive near-identical scores, so explicit coverage signals become necessary to maintain spread. This is a generic property of dense fronts, not a CATOS-specific limitation: any quality-only scalarization benefits from an added spread signal here.

[Q2 + Q3, part 2] Could the authors report the performance of CATOS alone on this benchmark [HW-GPT]?

Of course! We agree that CATOS (linear and scaling prior) without coverage signals, is an interesting ablation for Figure 2 and added it to the revised document. The results show that each is competitive early and is then overtaken by NSGA-II and MOEA/D after roughly 1500–2000 models, as expected once the score saturates on the dense front. The coverage-only variant (HV + NN-distance, without the CATOS score) performs considerably worse, while Linear CATOS with coverage signals remains ahead of all baselines throughout, indicating that the corridor score provides the decisive quality signal.

[W2, part 1] The first six pages are largely devoted to motivating and formalizing CATOS, although novelty of the approach seems limited.

We want to point out that the formal development of the novel constructs is the paper’s general contribution, not setup for one method: negative Pareto dominance (p. 3), the negative Pareto front (p. 3/4), local ideal points and ideal fronts (p. 4), and the Pareto corridor (p. 4) are defined independently of CATOS and are reusable in other bi-objective settings, while the negative Pareto front extends to general multiobjective settings. CATOS itself follows in 1.5 pages as an application of them. Could the reviewer expand on what is not novel about our formal development and provide a reference?

[Q5] Are the methods in the benchmarks compared under equivalent computational search budgets?

Yes. In Tables 2, 3, 4, 5 and 6 all methods share the same budget, defined as the number of model evaluations. Table 1 compares a different paradigm, where budgets are deliberately not equalized, to CATOS-EA’s disfavor: the constrained methods train one supernet per constraint, whereas CATOS-EA is given no constraint a priori and produces a single Pareto front that we filter post-hoc for every constraint in the table. It solves the harder problem and still matches or beats the per-constraint baselines, surpassing the next-best after 41 evaluations on average on the size space.

[Q1] The paper uses a power-law fit on NATS-Bench, but seems to use piecewise-linear interpolation on HW-GPT-Bench. Doesn't the necessity to make this choice limit the generality of the method, since the shape of the Pareto Front is not known in advance?

We thank the reviewer for raising this. The choice does not depend on knowing the Pareto front in advance. Linear interpolation is an assumption-free fallback that adapts to any front shape, so it is always a safe default. Opting for the scaling prior instead requires two things that are typically known a priori: the metric’s range (e.g. perplexity vs. accuracy) and whether the objective space is partitioned. The latter follows from the structure of the search space, not from evaluating its models. Figure 2 further shows that linear interpolation is itself a strong alternative to the prior, so the method does not hinge on getting this choice right.

[W4] The power-law used to smooth upper and lower envelopes from few architectures imposes a strong assumption on the shape of these envelopes, potentially introducing bias.

The reviewer is right that a prior can introduce bias. Here the only assumption is diminishing returns at higher compute cost. Its strength is not fixed: the degree of curvature is fit to the data (the Pareto front), and when the data call for it the fit flattens to nearly linear. The sole shape the prior rules out is increasing returns with higher cost, which is not expected in this setting.

Concerns about soundness

We thank the reviewer for the detailed and constructive feedback. We believe our responses above resolve the written concerns, including the soundness of the scalar score (Q4), the novelty (W1), and the generality of the method (Q1, W4). Since the overall soundness concerns were not elaborated beyond the summary rating, we would be grateful if the reviewer could point to any specific remaining issue so we can address it during the discussion period.

I thank the authors for their rebuttal. I stand by my initial assessment: the lengthy formalization does not establish novelty. The combination of several ideas, with different components used depending on the task, makes it difficult to identify the source of the method’s advantage. I do not think the contribution currently rises to the level of an ICLR paper.

  1. Concerning novelty, the authors explain “What sets CATOS apart is its corridor-based scoring, in which the fitted or interpolated fronts themselves determine the ranking,” but there is not sufficient evidence such as a direct ablation isolating the benefit of its distinctive two-front corridor construction. Ablation of table 10-11, “V-only and Crowding-only” test for alternative selection scores but does not seem to address specifically the impact of corridor-based scoring. Table 6 isolates the contribution of local ideal points, but does not address two-front corridor construction.

  2. I understand the framing that the approach performs better when the number of iteration is limited, but this puts in question the scalability of the approach to more complex task requiring longer search, and thus the impact of the method (e.g. in Table 12, CATOS does not perform significantly better than baselines at High budget).

  3. About W2 “The first six pages are largely devoted to motivating and formalizing CATOS, although novelty of the approach seems limited”, the authors respond that “formal development of the novel constructs is the paper’s general contribution, not setup for one method”, but defining constructs independently of CATOS and making them reusable does not, by itself, establish substantial novelty. Naming and formalizing a construction (e.g. “negative Pareto dominance (p. 3), the negative Pareto front (p. 3/4), local ideal points and ideal fronts (p. 4), and the Pareto corridor (p. 4)”) does not by itself establish novelty either. Negative Pareto front are related to anti-Pareto front, local ideal points seem closely related to prior work[1].

[1] Zhang, Yu, et al. "A multi-objective particle swarm optimization based on local ideal points." Applied Soft Computing 161 (2024): 111707.

  1. Concerning the response to Q1), the authors say “Linear interpolation is an assumption-free fallback that adapts to any front shape, so it is always a safe default”, but then it is unclear what practical criterion determines which curve construction to use on a new task (e.g. a power-law fit on NATS-Bench rather than something else), without relying on retrospective benchmark performance.
AuthorsOpenReview ↗

Follow-up Response by Authors

We thank the reviewer for the continued engagement. We believe our earlier rebuttal addressed the generality of our proposed constructs, the curve choice, and scalability. Here we focus on the points not yet discussed: an ablation of the two-front corridor, and constructions in the literature related to our local ideal points and negative Pareto front.

Ablation of the two-front corridor

We thank the reviewer for raising this. The negative Pareto front is what makes corridor based scoring two front: removing it leaves only the upper reference and the scores unnormalized, which is why we treated it as a core component rather than an ablatable option. To nonetheless isolate the benefit of the two front construction, beyond the local ideal points (Table 6) and the scaling prior (Table 5 on NATS-Bench, Figure 2 on HW-GPT-Bench), we compare Linear CATOS with and without the negative Pareto front, so the effect is attributable to the corridor itself rather than the curve fit or the selection score. Without the negative Pareto front, candidates are ranked by their distance to the positive Pareto front alone.

Setting: NATS-Bench topology, same protocol as Table 2, mean ± SD over 100 runs. HV-regret and Epsilon-indicator on the filtered set, lower is better, better value in each pair in bold.

HV-Regret

BudgetMethodcifar10cifar100ImageNet16-120
lowlinear CATOS0.1202 ± 0.04680.2431 ± 0.07210.2680 ± 0.0748
lowlinear CATOS no neg. front0.2276 ± 0.10470.3271 ± 0.09100.3309 ± 0.0878
midlinear CATOS0.0479 ± 0.02280.1215 ± 0.05470.0997 ± 0.0421
midlinear CATOS no neg. front0.0794 ± 0.04850.1459 ± 0.05460.1209 ± 0.0579
highlinear CATOS0.0274 ± 0.01250.0762 ± 0.04930.0655 ± 0.0287
highlinear CATOS no neg. front0.0437 ± 0.02290.1018 ± 0.04440.0752 ± 0.0376

Epsilon-Indicator

BudgetMethodcifar10cifar100ImageNet16-120
lowlinear CATOS0.2010 ± 0.06630.4263 ± 0.14570.3448 ± 0.0804
lowlinear CATOS no neg. front0.3400 ± 0.12980.4765 ± 0.12470.4273 ± 0.1197
midlinear CATOS0.0946 ± 0.03090.2234 ± 0.06720.1794 ± 0.0625
midlinear CATOS no neg. front0.1361 ± 0.06910.2306 ± 0.06650.2126 ± 0.0803
highlinear CATOS0.0642 ± 0.02400.1887 ± 0.05750.1376 ± 0.0402
highlinear CATOS no neg. front0.0896 ± 0.02870.2141 ± 0.05650.1590 ± 0.0546

Removing the negative Pareto front degrades performance across all datasets, budgets, and both metrics, confirming that the two-front corridor is meaningful.

Local ideal points seem closely related to prior work [1].

We thank the reviewer for pointing this out. Our local ideal points share the name with those in [1], but differ in construction and purpose. There, the points are formed on the fly, one per region of objective space spanning several solutions, and used to score how converged each individual solution is during search. Ours are built from consecutive Pareto optimal points and assembled into a connected set that we use as a front in its own right, the ideal front, which serves to fit the reference curve (or a linear interpolation). [1] uses its points individually for selection, and neither creates an ideal front from them nor a negative counterpart.

[1] Zhang, Yu, et al. "A multi-objective particle swarm optimization based on local ideal points." Applied Soft Computing 161 (2024): 111707.

Negative Pareto front and the anti-Pareto front

The anti-Pareto front appears in a line of work in mathematical epidemiology [2], where it is a worst-case value function defined over the full feasible set of vaccine-allocation strategies and characterized analytically where the problem structure permits. There it is the object of study in its own right, quantifying how poorly a vaccine allocation can perform. Our negative Pareto front differs in both nature and purpose: it is a dual-dominance boundary over a finite, sampled set of architectures, an empirical, sample-dependent estimate rather than a provable envelope, and it is not studied for its own sake but used instrumentally, delimiting the Pareto corridor and, once fitted with the scaling prior, providing the lower reference against which architectures are scored. The anti-Pareto front serves neither role: it is not used to guide a search or rank candidates.

[2] Delmas, Jean-François, Dylan Dronnier, and Pierre-André Zitt. "Optimal vaccination: various (counter) intuitive examples: J.-F. Delmas et al." Journal of Mathematical Biology 86.2 (2023): 26.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.