NAS-Bench-301 and the Case for Surrogate Benchmarks for Neural Architecture Search

Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, Frank Hutter

Abstract

The most significant barrier to the advancement of Neural Architecture Search (NAS) is its demand for large computational resources, which hinders scientifically sound empirical evaluations of NAS methods. Tabular NAS benchmarks have alleviated this problem substantially, making it possible to properly evaluate NAS methods in seconds on commodity machines. However, an unintended consequence of tabular NAS benchmarks has been a focus on extremely small architectural search spaces since their construction relies on exhaustive evaluations of the space. This leads to unrealistic results that do not transfer to larger spaces. To overcome this fundamental limitation, we propose a methodology to create cheap NAS surrogate benchmarks for arbitrary search spaces. We exemplify this approach by creating surrogate NAS benchmarks on the existing tabular NAS-Bench-101 and on two widely used NAS search spaces with up to $10^{21}$ architectures ($10^{13}$ times larger than any previous tabular NAS benchmark). We show that surrogate NAS benchmarks can model the true performance of architectures better than tabular benchmarks (at a small fraction of the cost), that they lead to faithful estimates of how well different NAS methods work on the original non-surrogate benchmark, and that they can generate new scientific insight. We open-source all our code and believe that surrogate NAS benchmarks are an indispensable tool to extend scientifically sound work on NAS to large and exciting search spaces.

Introduction: The Scalability Crisis in NAS

Neural Architecture Search (NAS) has the potential to automate the design of optimal neural networks, but its progress is severely hampered by computational costs. Evaluating a single architecture often requires thousands of GPU hours. To address this, the community developed tabular benchmarks like NAS-Bench-101, which provide pre-computed performance metrics for every architecture in a fixed search space.

However, tabular benchmarks suffer from a fundamental limitation: they require exhaustive evaluation. This restricts them to "toy" search spaces (typically <423,000 architectures). In contrast, real-world search spaces, such as those used in DARTS or FBNet, contain between $10^{18}$ and $10^{21}$ architectures. NAS methods optimized on small tabular spaces often fail to generalize to these massive, realistic environments.

Methodology: From Tables to Surrogates

To bridge this gap, we propose surrogate NAS benchmarks. Instead of exhaustive evaluation, we evaluate a representative subset of the search space and train a regression model to predict the performance of the remaining architectures.

Surrogate Modeling and Data Collection

We evaluated several model architectures, including Graph Isomorphism Networks (GIN)—which treat neural architectures as graphs—and tree-based ensembles like XGBoost. To ensure the surrogates are accurate in high-performance regions where NAS optimizers spend most of their time, we used a mixed sampling strategy:

  1. Random Sampling: For broad coverage of the search space.
  2. Optimizer-Guided Sampling: Architectures discovered by various NAS algorithms to densely sample the "good" regions.

Noise and Multi-Objective Modeling

Neural network training is inherently stochastic. To account for this, we use ensembles of surrogate models to provide both a mean performance estimate and a measure of uncertainty (aleatoric noise). Furthermore, our surrogates predict multiple objectives, including accuracy and runtime, enabling the evaluation of multi-objective NAS algorithms.

Key Insights: Why Surrogates Outperform Tables

A surprising finding is that surrogate models can actually be more reliable than tabular benchmarks. Because individual training runs are noisy, a single entry in a table is just one random realization. A surrogate model, trained on thousands of related architectures, learns the underlying performance manifold and effectively smooths out the noise.

Surrogate vs. Tabular Error: As training data increases, surrogates can achieve lower mean absolute error than tabular benchmarks by smoothing out stochastic training noise.

Results and Benchmarks

We introduced several new benchmarks under the NAS-Bench-301 umbrella:

  • SNB-DARTS: A surrogate for the DARTS space ($10^{18}$ architectures) on CIFAR-10.
  • SNB-FBNet: A surrogate for the FBNet space ($10^{21}$ architectures) on CIFAR-100.

High Fidelity and Efficiency

Our surrogates achieve high ranking correlation (Sparse Kendall Tau of ~0.8) and faithfully reproduce the search trajectories of real NAS optimizers. Most importantly, these evaluations take only seconds on a CPU, simulating months of GPU time.

Fidelity of Search Trajectories: Comparison of NAS optimizer performance on the true benchmark versus GIN and XGB surrogates, showing that surrogates faithfully reproduce search dynamics.

Correcting Scientific Narratives

The efficiency of NAS-Bench-301 allowed us to revisit previous assumptions. For instance, Local Search (LS) was previously thought to perform poorly on the DARTS space. By running LS for much longer than previously feasible (simulating 115 GPU days), we discovered it eventually achieves state-of-the-art performance.

Conclusion and Future Work

Surrogate benchmarks provide a scalable, reproducible, and scientifically sound way to evaluate NAS methods on realistic search spaces. While they face challenges like extrapolation risks in unsampled regions, they represent a significant step forward from limited tabular benchmarks. Future work will extend these surrogates to diverse domains like NLP and ASR and utilize active learning to further refine prediction accuracy in high-interest regions.

Summary updated

Abstract

The most significant barrier to the advancement of Neural Architecture Search (NAS) is its demand for large computational resources, which hinders scientifically sound empirical evaluations of NAS methods. Tabular NAS benchmarks have alleviated this problem substantially, making it possible to properly evaluate NAS methods in seconds on commodity machines. However, an unintended consequence of tabular NAS benchmarks has been a focus on extremely small architectural search spaces since their construction relies on exhaustive evaluations of the space. This leads to unrealistic results that do not transfer to larger spaces. To overcome this fundamental limitation, we propose a methodology to create cheap NAS surrogate benchmarks for arbitrary search spaces. We exemplify this approach by creating surrogate NAS benchmarks on the existing tabular NAS-Bench-101 and on two widely used NAS search spaces with up to $10^{21}$ architectures ($10^{13}$ times larger than any previous tabular NAS benchmark). We show that surrogate NAS benchmarks can model the true performance of architectures better than tabular benchmarks (at a small fraction of the cost), that they lead to faithful estimates of how well different NAS methods work on the original non-surrogate benchmark, and that they can generate new scientific insight. We open-source all our code and believe that surrogate NAS benchmarks are an indispensable tool to extend scientifically sound work on NAS to large and exciting search spaces.
BibTeX
@inproceedings{siems2022nas,
  author = {Julien Siems and Lucas Zimmer and Arber Zela and Jovita Lukasik and Margret Keuper and Frank Hutter},
  title = {{NAS-Bench-301 and the Case for Surrogate Benchmarks for Neural Architecture Search}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=523TDHuiAHX},
}
Figure