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