Surrogate NAS Benchmarks: Going Beyond the Limited Search Spaces of Tabular NAS Benchmarks

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

Abstract

The primary bottleneck in Neural Architecture Search (NAS) research is the immense computational cost required for evaluation, often limiting experiments to small, artificial "tabular" search spaces. We propose Surrogate NAS Benchmarks, a methodology to create efficient, accurate benchmarks for realistically large search spaces (up to $10^{21}$ architectures). By training regression models on a sparse subset of architecture evaluations, we provide a tool that simulates real-world NAS performance in seconds. Our results demonstrate that surrogates not only match the ranking accuracy of tabular benchmarks but can even surpass them by smoothing out evaluation noise. We open-source our surrogates for DARTS and FBNet spaces to enable democratized, large-scale NAS research.

The Challenge: The Generalization Gap in NAS

Neural Architecture Search (NAS) automates the design of neural networks, but its "real-world" application is prohibitively expensive. Evaluating a single NAS algorithm can consume thousands of GPU hours. To mitigate this, the community developed Tabular Benchmarks (e.g., NAS-Bench-101), which provide pre-computed performance tables for every architecture in a search space.

However, tabular benchmarks suffer from a fundamental limitation: they are restricted to tiny "toy" spaces (typically $<10^6$ architectures) because they require exhaustive evaluation. In contrast, practical search spaces are often $10^{18}$ or larger. This creates a "generalization gap" where algorithms optimized for small tabular spaces fail to perform on the massive, complex spaces used in production.

Methodology: Building the Surrogate

Instead of an exhaustive table, we propose using a Surrogate Model to predict architecture performance. We evaluate a strategic subset of the search space and train a machine learning model to interpolate performance across the entire domain.

Model Selection and Data Collection

We explored several surrogate architectures, including XGBoost, Random Forests, and Graph Isomorphism Networks (GIN). GINs are particularly well-suited for NAS as they can directly process the graph-based topology of neural architectures.

To ensure the surrogate is accurate in high-performance regions—where NAS optimizers spend most of their time—we employed a mixed sampling strategy. We combined random architectures with those discovered by running various NAS optimizers (e.g., Regularized Evolution, BOHB). This ensures the model learns both the global landscape and the local "peaks" of the search space.

Why Surrogates?

A common misconception is that a surrogate is merely a "second-best" approximation of a table. In reality, surrogates can be superior. Tabular entries are typically based on a very small number of training runs (1-3), making them susceptible to stochastic noise. A surrogate model, by learning from thousands of related architectures, acts as a regularizer that "smooths out" this noise to find the true underlying performance trend.

Surrogate vs. Tabular Error

As shown in the figure above, once the surrogate is trained on a sufficient number of architectures (approximately 21,500 for NAS-Bench-101), its Mean Absolute Error (MAE) drops below that of the tabular benchmark, providing a more reliable estimate of an architecture's true quality.

Validation and Results

We validated our approach on three benchmarks: NAS-Bench-101 (as a sanity check), and two massive new spaces: SNB-DARTS ($>10^{18}$ architectures) and SNB-FBNet ($\approx 10^{21}$ architectures).

Faithful Optimization Trajectories

The ultimate test for a NAS benchmark is whether it yields the same conclusions as a real-world experiment. We ran several popular NAS optimizers—including Differential Evolution (DE), Regularized Evolution (RE), and TPE—on both the true benchmarks and our surrogates.

Comparison of Optimization Trajectories

The results demonstrate that the "anytime performance" curves on the GIN and XGB surrogates closely mirror the trajectories on the true benchmark. This confirms that researchers can use these surrogates to develop and tune algorithms with high confidence that their findings will transfer to real-world settings.

Extreme Efficiency

The computational savings are transformative. Experiments that would typically require 11.8 GPU days can be simulated on a surrogate in just a few seconds on a standard CPU. This allows for extensive hyperparameter tuning and statistical significance testing that was previously impossible for most research groups.

Correcting Scientific Narratives

The utility of surrogate benchmarks extends beyond mere speed. We used our surrogates to revisit a study claiming that "Local Search" performs poorly on the DARTS space. Because the surrogate is so cheap, we could afford to run Local Search for a much longer simulated duration than the original authors could on real hardware. We discovered that Local Search actually achieves state-of-the-art performance if given a sufficient time budget—a discovery that would have cost over 100 GPU days to verify without surrogates.

Limitations and Future Work

While powerful, surrogates are not without risks. Model bias is a concern; if a NAS algorithm uses a GIN internally, it might "overfit" to a GIN-based surrogate. We mitigate this by providing multiple surrogate versions based on different model architectures. Additionally, surrogates are primarily interpolators; their accuracy may degrade in "unseen" regions of the search space, such as architectures with extreme connectivity patterns.

Conclusion

Surrogate NAS benchmarks bridge the gap between the efficiency of tabular benchmarks and the realism of massive search spaces. By providing a cheap, accurate, and reproducible evaluation framework, we hope to democratize NAS research and enable the community to tackle the challenges of large-scale architecture search.

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{zela2022surrogate,
  author = {Arber Zela and Julien Siems and Lucas Zimmer and Jovita Lukasik and Margret Keuper and Frank Hutter},
  title = {{Surrogate NAS Benchmarks: Going Beyond the Limited Search Spaces of Tabular NAS Benchmarks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=523TDHuiAHX},
}
Figure