Source-linked AI summary
Evaluating the Search Phase of Neural Architecture Search
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, Mathieu Salzmann
TL;DR
NAS is commonly evaluated by downstream performance, which does not directly reveal whether its search strategy is effective or robust. This paper evaluates the search phase against random architecture selection and finds that state-of-the-art methods are often no better than random, while weight sharing can distort candidate rankings. The findings emphasize search-space structure and weight-sharing effects as central considerations for NAS evaluation and design.
Problem
NAS algorithms are usually compared through downstream results, leaving the effectiveness and robustness of their search strategies insufficiently evaluated.
Method
The paper compares NAS search policies with uniformly random architectures from the same search spaces, using matched training conditions and multiple random seeds.
Results
State-of-the-art NAS algorithms do not significantly outperform random sampling on the evaluated tasks, while weight sharing can make candidate rankings uncorrelated with true performance.
Takeaways & Limitations
Evaluating the search phase reveals the importance of search-space structure and the negative impact of weight sharing on NAS search effectiveness.
Takeaways & Limitations
The analysis uses reduced search spaces with ground-truth architecture performances because standard spaces are too large to evaluate exhaustively.
Abstract
from arXiv · showhide
Neural Architecture Search (NAS) aims to facilitate the design of deep networks for new tasks. Existing techniques rely on two stages: searching over the architecture space and validating the best architecture. NAS algorithms are currently compared solely based on their results on the downstream task. While intuitive, this fails to explicitly evaluate the effectiveness of their search strategies. In this paper, we propose to evaluate the NAS search phase. To this end, we compare the quality of the solutions obtained by NAS search policies with that of random architecture selection. We find that: (i) On average, the state-of-the-art NAS algorithms perform similarly to the random policy; (ii) the widely-used weight sharing strategy degrades the ranking of the NAS candidates to the point of not reflecting their true performance, thus reducing the effectiveness of the search process. We believe that our evaluation framework will be key to designing NAS strategies that consistently discover architectures superior to random ones.
1 INTRODUCTION
NAS is usually judged by downstream performance, leaving the effectiveness and robustness of its search strategies insufficiently examined. This paper compares NAS search policies with random sampling and finds limited advantages, while identifying search-space constraints and weight sharing as important factors.
- NAS evaluation typically focuses on the final architecture’s downstream results, obscuring how sampling strategies and search spaces affect search effectiveness.
- The proposed evaluation compares NAS solutions with uniformly random architectures sampled from the same search space and trained using matching hyper-parameters across multiple seeds.
- On PTB and CIFAR-10, DARTS, NAO, and ENAS do not significantly outperform random sampling; in RNN space, NAO performs worse than random.
- Weight sharing produces candidate rankings that do not reflect true evaluation performance, reducing the effectiveness of the NAS search process.
- The evaluation framework highlights the importance of the search space and the negative impact of weight sharing for developing NAS strategies superior to random search.
2 RELATED WORK
Related work addresses NAS efficiency, search-space characterization, and algorithm evaluation. Prior comparisons with random search often used procedures that did not give the random policy an equivalent evaluation opportunity.
- Vanilla NAS can require thousands of GPU hours, motivating weight sharing methods that reduce computational resources substantially.
- Weight sharing lets sampled models inherit parameters from previously trained models, while later work replaces reinforcement learning with gradient descent, Bayesian optimization, or performance predictors.
- Search-space studies characterize architecture distributions and ground-truth performance, supporting analysis of whether spaces contain meaningful variation in architecture quality.
- NAS algorithms are generally judged by final downstream results, so the mechanisms and robustness of their search phases remain insufficiently studied.
- Earlier random-search comparisons reported one random architecture or selected among eight after limited training, rather than training all alternatives under a fair procedure.
- The paper contrasts its weight-sharing findings with prior work because the training schemes and search settings differ fundamentally.
3 EVALUATING THE NAS SEARCH
The framework evaluates NAS search directly by comparing its best architecture with a uniformly sampled architecture under repeated, matched evaluation conditions. Reduced spaces with ground-truth performance make exhaustive search-quality analysis feasible.
- 3 EVALUATING THE NAS SEARCH: Typical NAS separates search, which seeks an architecture, from evaluation, which retrains the selected model and measures it on test data.
- 3 EVALUATING THE NAS SEARCH: The framework treats random search as a baseline and expects an effective NAS policy to produce a solution that clearly outperforms it.
- 3 EVALUATING THE NAS SEARCH: The random policy assigns uniform probabilities to operations and samples one connection to a previous DAG node for each node.
- 3.1 COMPARING TO RANDOM SEARCH: Best NAS and random architectures are trained from scratch with multiple seeds, reporting means and standard deviations while sharing evaluation-training seeds between policies.
- 3.2 SEARCH IN A REDUCED SPACE: Reduced search spaces are used because standard spaces are too large for exhaustive evaluation; the RNN space contains 32 solutions, each trained 10 times for ground-truth performance.
- 3.2 SEARCH IN A REDUCED SPACE: For CNNs, NASBench-101 provides graph-based spaces with three operations and up to 423,624 architectures in the seven-node case.
4 EXPERIMENTAL RESULTS
Experiments on standard and reduced RNN/CNN search spaces show that the evaluated NAS policies rarely improve over random sampling. Reduced-space analyses further implicate weight sharing as a source of ranking errors that weaken search effectiveness.
- 4.1 NAS COMPARISON IN A STANDARD SEARCH SPACE: Random sampling outperforms DARTS and NAO on average in the RNN space and finds the overall best cell, with perplexity 57.60.Training this cell for 4000 epochs yields perplexity 55.93.
- 4.1 NAS COMPARISON IN A STANDARD SEARCH SPACE: NAS methods marginally exceed random search in the CNN space by less than 0.5% top-1 accuracy; NAO finds the best architecture at 97.10%.The random policy incurs no search cost in this comparison.
- 4.1 NAS COMPARISON IN A STANDARD SEARCH SPACE: Across standard RNN and CNN spaces, the evaluated NAS algorithms do not significantly outperform random search, and some perform worse.The study compares DARTS, NAO, ENAS, and BayesNAS with random search using repeated runs.
- 4.2 SEARCHING A REDUCED SPACE: In the reduced RNN space, no policy finds the truly best architecture; ENAS repeatedly selects the same architecture, while DARTS never finds a top-5 architecture.NAO outperforms random sampling on average but selects an architecture from its uniformly sampled initial pool, making it practically similar to random search.
- 4.2 SEARCHING A REDUCED SPACE: In the reduced CNN space, NAO reaches 93.33% versus the ground-truth best of 95.06, with its best rank among the top 4% and probability 0.62 of surpassing random search.These results are measured on the NASBench-101 7-node space.
- 4.3 IMPACT OF WEIGHT SHARING: Removing weight sharing improves ENAS and NAO performance by about 1% on average and raises their probability of surpassing random search to 0.92 and 0.90, respectively.For the 7-node case, the best cells reach 94.11% for NAO and 94.04% for ENAS without weight sharing.
5 CONCLUSION
The paper finds that state-of-the-art NAS search policies are no better than random and links this outcome to constrained search spaces and weight sharing. These insights motivate developing relaxed weight-sharing strategies.
- State-of-the-art NAS search policies are no better than random search.The comparison evaluates the effectiveness of the search phase rather than only downstream task performance.
- A constrained search space and weight sharing negatively impact NAS search effectiveness.Weight sharing shuffles architecture rankings during search, reducing their correspondence with evaluated performance.
- The overlooked properties of NAS strategies motivate the development of novel NAS algorithms.The paper specifically identifies relaxed weight sharing as a future direction.
A.1 KENDALL TAU METRIC
The section describes Kendall Tau as a ranking-correlation measure and presents NAS search-space representations based on graphs, strings, and vectors. It also outlines candidate architectures, NAS algorithms, and ground-truth ranking procedures.
- KENDALL TAU METRIC: Kendall Tau τ measures correlation between two rankings on a scale from −1 to 1.τ = −1 indicates maximum disagreement, τ = 1 maximum agreement, and values near zero indicate no correlation.
- NAS SEARCH SPACE REPRESENTATION: NAS architectures can be represented as directed acyclic graphs, strings, or vectors of operation and connection probabilities.The vector representation encodes each node ID or operation as probabilities, with softmax parameters α.
- NASBENCH: NASBench contains 423,624 CNN-cell architectures, each trained three times and ranked by average CIFAR-10 test accuracy.The ranking assigns rank 1 to the highest-accuracy architecture and rank 423,624 to the lowest.
- PROBABILITY TO SURPASS RANDOM SEARCH: The probability metric estimates whether the best architecture found after n runs exceeds a randomly searched architecture under the same budget.The paper uses this probability as a new metric for evaluating the search phase.
- SEARCH EVALUATION: The search phase is evaluated by comparing NAS solutions with uniformly random architectures trained under the same hyper-parameters and across multiple seeds.The paper evaluates publicly available DARTS, NAO, and ENAS, alongside BayesNAS in the described algorithm set.
C.5 EXPERIMENTAL SETUP
The experiments use PTB for recurrent-cell search and CIFAR-10 for convolutional-cell search, evaluating candidates with perplexity and top-1 accuracy. The setup standardizes evaluation and adapts algorithms for reduced search spaces.
- DATASETS AND METRICS: PTB evaluates recurrent cells with perplexity, while CIFAR-10 evaluates convolutional cells with top-1 accuracy.The respective tasks are next-word prediction and image classification.
- EVALUATION: All searched architectures use the same evaluation backbone and parameter initialization to ensure fair comparisons.The reported accuracy variation from initialization is less than 0.002.
- REDUCED SEARCH SPACES: Reduced search spaces require modifications to the evaluated NAS algorithms to achieve their best performance.The adaptations change node counts, NAO sampling and embedding settings, and ENAS sampler parameters.
D SUPPLEMENTARY EXPERIMENTS
The supplementary experiments provide additional experiments supporting the paper’s claims.
- The supplementary material includes additional experiments to support the paper’s claims.
D.1 INFLUENCE OF THE AMOUNT OF SHARING
Weight sharing can distort architecture rankings, with architectures sharing fewer weights performing better in the toy RNN experiment. A corresponding CNN experiment also finds decreasing ranking correlation as sharing increases.
- D.1 INFLUENCE OF THE AMOUNT OF SHARING: Different active connections in the DAG expose architectures to different amounts of shared parameters.For node 3, the input can be node 0, node 1, or node 2, changing which parameters affect its output.
- D.1 INFLUENCE OF THE AMOUNT OF SHARING: The toy search space contains 12 architectures formed by 3 possible connections to node 3 and 4 operation choices.The first two nodes are fixed while only node 3 is searched.
- D.1 INFLUENCE OF THE AMOUNT OF SHARING: Top-performing architectures share no weights, while architectures sharing more weight matrices perform worse.Shared matrices are those from nodes 1 and 2 also used when searching for node 3.
- D.1 INFLUENCE OF THE AMOUNT OF SHARING: In the CNN experiment, ranking correlation decreases as weight sharing increases.The experiment evaluates 12 architectures formed by 4 connection choices and 3 operation choices.
D.2 RANDOM SAMPLING COMPARISON
The paper argues that the DARTS random baseline can select architectures using unstable early rankings. Rank trajectories vary substantially during training, motivating a convergence-trained random baseline and repeated random-seed comparisons.
- D.2 RANDOM SAMPLING COMPARISON: Early-training performance can diverge from final performance, so DARTS’s 300-epoch random policy may select a sub-optimal architecture.The DARTS policy samples 8 architectures independently and selects the best after 300 epochs.
- D.2 RANDOM SAMPLING COMPARISON: Models’ ranks show significant training-time variation, with some early strong models falling lower by the end.Figure 7 averages rank trajectories over 10 runs and marks the epochs when random sampling occurs.
- D.2 RANDOM SAMPLING COMPARISON: The paper uses a random baseline that samples one model per seed, trains it to convergence, and compares policies across 10 random seeds.This is presented as a fairer and more reliable comparison than using a single random seed.
D.3 NASBENCH DETAILED RESULTS.
NASBench experiments compare sampling-based and one-shot NAS methods across search spaces with 4–7 nodes. Sampling-based methods have higher mean accuracy, while one-shot methods can find better individual architectures but remain variable and miss the overall best.
- D.3 NASBENCH DETAILED RESULTS.: Sampling-based NAS strategies achieve higher mean accuracy and lower standard deviation than one-shot methods.The results associate this pattern with easier convergence to a local minimum and less exploitation of the full search space.
- D.3 NASBENCH DETAILED RESULTS.: One-shot methods produce more diverse solutions, with lower means and larger standard deviations, but can select better architectures.FairNAS reaches 94.47 accuracy and SPOS 94.24, compared with 93.98 for the best sampler-based FBNet result.
- D.3 NASBENCH DETAILED RESULTS.: ENAS consistently improves as the number of nodes increases, while FBNet consistently outperforms DARTS under the reported similarity comparison.The experiments report mean and best top-1 accuracy for node counts n ∈[4, 7].
- D.3 NASBENCH DETAILED RESULTS.: Algorithm variance is large and sensitive to initialization, and even one-shot methods fail to find the overall-best architecture with accuracy 95.06.All methods are evaluated with 10 random seeds, and top architectures are retrained from scratch for ground-truth performance.