{'fraction_non_alphanumeric': 0.030680292236611513, 'fraction_numerical': 0.013678676286501127, 'mean_word_length': 4.875635196576625, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Where To Look -- Generative NAS is Surprisingly Efficient

The efficient, automated search for well-performing neural architectures (NAS) has drawn increasing attention in the recent past. Thereby, the predominant research objective is to reduce the necessity of costly evaluations of neural architectures while efficiently exploring large search spaces. To this aim, surrogate models embed architectures in a latent space and predict their performance, while generative models for neural architectures enable optimization-based search within the latent space the generator draws from. Both, surrogate and generative models, have the aim of facilitating query-efficient search in a well-structured latent space. In this paper, we further improve the trade-off between query-efficiency and promising architecture generation by leveraging advantages from both, efficient surrogate models and generative design. To this end, we propose a generative model, paired with a surrogate predictor, that iteratively learns to generate samples from increasingly promising latent subspaces. This approach leads to very effective and efficient architecture search, while keeping the query amount low. In addition, our approach allows in a straightforward manner to jointly optimize for multiple objectives such as accuracy and hardware latency. We show the benefit of this approach not only w.r.t. the optimization of architectures for highest classification accuracy but also in the context of hardware constraints and outperform state-of-the-art methods on several NAS benchmarks for single and multiple objectives. We also achieve state-of-the-art performance on ImageNet. The code is available at http://github.com/jovitalukasik/AG-Net .


Introduction
The first image classification network [29] applied to the large-scale visual recognition challenge ImageNet [15] achieved unprecedented results. Since then, the main driver of improvement on this challenge are new architecture designs [49,51], [52,22] that, ultimately, lead to architectures surpassing human performance [21]. Since manual architecture design requires good intuition and a huge amount of  17,34,27]. However, these methods are inefficient because they require to evaluate thousands of architectures, resulting in impracticable search times. Recent approaches avoid this problem of immense computation costs by either training surrogate models to approximate the performance of an architecture [34,9] or by generating architectures based on learned architecture representation spaces [68,35]. Both methods aim to improve the query efficiency, which is crucial in NAS, since every query implies a full training and evaluation of the neural architecture on the underlying target dataset.
This trade-off between query efficiency and resulting high-scoring architectures is an active research field. Yet, no attempts were made so far to leverage the advantages of both search paradigms. Therefore, we propose a model that incorporates the focus of promising architectures already in the architecture generation process by optimizing the latent space directly: We let the generator learn in which areas of the data distribution to look for promising architectures. This way, we reduce the query amount even further, resulting in a query efficient and very effective NAS method. Our proposed method is inspired by a latent space optimization (LSO) technique [53], originally used in the context of variational autoencoders [26] to optimize generated images or arithmetic expressions using BO. We adapt this concept to NAS and pair it with an architecture performance predictor in an end-to-end learning setting, so that it allows us to iteratively reshape the architecture representation space. Thereby, we promote desired properties of generated architectures in a highly query-efficient way, i.e. by learning expert generators for promising architectures. Since we couple the generation process with a surrogate model to predict desired properties such as high accuracy or low latency of generated architectures, there is no need in our method for BO in the generated latent space, making our method even more efficient.
In practice, we pretrain, on a target space of neural architectures, a GNNbased generator network, which does not rely on any architecture evaluation and is therefore fast and query-free. The generator is trained in a novel generative setting that directly compares generated architectures to randomly sampled architectures using a reconstruction loss without the need of a discriminator network as in generative adversarial networks (GANs) [20] or an encoder as in variational autoencoders (VAEs) [26]. We use an MLP as a surrogate to rank performances and hardware properties of generated architectures. In contrast, previous generative methods either rely on training and evaluating supernets [23], which are expensive to train and dataset specific, or pretrain a latent space and search within this space directly using BO [68,65,35], reinforcement learning (RL) [44] or gradient based methods [36]. These methods incorporate either GANs, which can be hard to train or VAEs, which are biased by the regularization, whereas our plain generative model is easy to train. In addition we enable backpropagation from the performance predictor to the generator. Thereby, the generator can efficiently learn which part of the architecture search space is promising with only few evaluated architectures.
By extensive experiments on common NAS benchmarks [66,17,48,27,30] as well as ImageNet [15], we show that our method is effective and sample-efficient. It reinforces the generator network to produce architectures with improving validation accuracy (see Figure 1), as well as in improving on hardware-dependent latency constraints (see Figure 4) while keeping the number of architecture evaluations small. In summary, we make the following contributions: -We propose a simple model that learns to focus on promising regions of the architecture space. It can thus learn to generate high-scoring architectures from only a few queries. -We learn architecture representation spaces via a novel generative design that is able to generate architectures stochastically while being trained with a simple reconstruction loss. Unlike VAEs [26] or GANs [20], no encoder network nor discriminator network is necessary. -Our model allows sample-efficient search and achieves state-of-the-art results on several NAS benchmarks as well as on ImageNet. It allows joint optimization w.r.t. hardware properties in a straightforward way.

Related Work
Neural Architecture Search Intrinsically, Neural Architecture Search (NAS) is a discrete optimization problem seeking the optimal configuration of operations (such as convolutions, poolings and skip connections) in a constrained search space of computational graphs. . In this paper, we also learn continuous architecture representation spaces. However, in contrast to former works, we propose to optimize the representation space, instead of performing point optimization within a fixed space such as e.g. [36]. A survey of different strategies can be found in [18].
All NAS approaches are dependent on performance estimation of intermediate architectures. To avoid the computation heavy training and evaluation of queries on the target dataset, methods to approximate the performance have been explored [58].  [20] setting, where the backpropagation issue is circumvented using reinforcement learning. In contrast, our proposed GNN generator circumvents the intermediate architecture discretization and can therefore be trained by a single reconstruction loss using backpropagation. Its iterative optimization is inspired by [53], who proposes to use a VAE with weighted retraining w.r.t. a target function to adapt the latent space for the optimization of images and arithmetic functions using BO. Our The input is a randomly sampled latent vector z ∈ R d . First, the input node is generated, initialized and input to a GNN to generate a partial graph representation. The learning process iteratively generates node scores and edge scores using z and the partial graph representation until the output node is generated. The target for this generated graph is a randomly sampled architecture.
model transfers the idea of weighted retraining to NAS. It uses our plain generator and improves sample efficiency by employing a differentiable surrogate model on the target function such that, in contrast to [53], no further black-box optimization step is needed. Next, we describe the proposed generator network.

Architecture Generative Model
Preliminaries We aim to generate neural networks represented as directed acyclic graphs (DAG). This representation is in line with the cell-based architecture search spaces commonly used as tabular benchmarks [66,17]. Each cell is a DAG G = (V, E), with nodes v ∈ V and edges e ∈ E. The graph representations differ between the various benchmarks in terms of their labeling of operations. For example in NAS-Bench-101 [66] each node is associated with an operation, whereas in NAS-Bench-201 [17] each edge is associated with an operation. Generative Network Commonly used graph generative networks are based on variational autoencoders (VAE) [26]. In contrast, our proposed network is a purely generative network, p G (see Figure 2). To generate valid graphs, we build our model similar to the graph decoder from the VAE approach SVGe [35]. The generator takes a randomly sampled variable z ∼ N (0, 1) as input and reconstructs a randomly sampled graph from the cell-based search space. The model iteratively builds the graph: it starts with generating the input node v 0 , followed by adding subsequent nodes v i and their labels and connecting them with edges e (j,i) , j < i, until the end node v T with the label output is generated. Additionally, we want to learn a surrogate for performance prediction on the generated data and allow for end-to-end training of both. To allow for backpropagation, we need to adapt several details of the generator model. We initialize the nodeattributes for each node by one-hot encoded vectors, which are initialized during training using a 2-layer MLP to replace the learnable look-up table proposed in SVGe. The output of our generator is a vector graph representation consisting of a concatenation of generated node scores and edge scores. It is important to note that the iterative generation process is independent of the ground truth data, which are only used as a target for the reconstruction loss. Note that the end-to-end trainability of the proposed generator is a prerequisite for our model: It allows to pair the generator with a learnable performance predictor such that information on the expected architectures' accuracy can be learned by the generator. This enables a stronger coupling with the predictor's target for the generation process and higher query efficiency (see subsection 4.4). In contrast, previous models such as [23,35,65] are not fully differentiable and do not allow such optimization. Our generative model is pretrained on the task of reconstructing neural architectures, where for each randomly drawn latent space sample, we evaluate the reconstruction loss to a randomly drawn architecture. This simple procedure is facilitated by the heavily constrained search spaces of neural architectures, making it easy for the model to learn to generate valid architectures without being supported by a discriminator model as in generative adversarial networks (GANs) [20]. An evaluation of the generation ability of our model and implementation details are provided in the supp. mat. section D.
Performance Predictor This generative model is coupled with a simple surrogate model, a 4-layer MLP with ReLU non-linearities, for target predictions C. These targets can be validation or test accuracy of the generated graph, or the latency with respect to a certain hardware. For comparison, we also include a tree-based method, XGBoost (XGB) [10] as an alternative prediction model. XGB [10] is used as a surrogate model in NAS-Bench-301 [48] and shows high prediction abilities. The input to XGB is the vector representation of the architectures. Since this method is non-differentiable, we additionally include a gradient estimation for rank-based metrics [45]. This way, we are able to include gradient information to the generator. Yet, it is important to note, that this approach is not fully differentiable. This comparison will allow us to measure the trade-off between using supposedly stronger predictors over the capability to allow for full end-to-end learning.
Training Objectives The generative model p G learns to reconstruct a randomly sampled architecture G from search space p D given a randomly sampled latent vector z ∼ N (0, 1). The objective function for this generation process can be formulated as the sum of node-level loss L V and edge-level loss L E : where L V is the Cross-Entropy loss between the predicted and the ground truth nodes and L E is the Binary-Cross Entropy loss between the predicted and ground truth edges of the generated graphG. This training step is completely unsupervised. Figure 2 presents an overview of the training process. To include the training of the surrogate model, the objective function is reformulated to: where α is a hyperparameter to trade-off generator loss L G and prediction loss L C for the prediction targets C of graph G. We set the predictor loss as an MSE. Furthermore, each loss is optimized using mini-batch gradient descent.
Generative Latent Space Optimization (LSO) To facilitate the generation process, we optimize the architecture representation space via weighted retraining [53], resulting in a sample efficient search algorithm. The intuition of this approach is to place more probability mass on high-scoring latent points, (e.g. high performing or low latency architectures) and less mass on low-scoring points. Thus, this strategy does not discard low-scoring architectures completely, which would be inadequate for proper learning. The generative model is therefore trained on a data distribution that systematically increases the probability of high-scoring latent points. This can be done by simply assigning a weight w i to each data point G i ∼ p D , indicating its likelihood to occur during batch-wise training. In addition, the training objective is weighted via a weighted empirical mean Gi∼p D w i L for each data point. As for the weights itself, [53] proposed a rank-based weight function where f (·) is the evaluation function of the architecture G i ; for NAS-Bench-101 [66] and NAS-Bench-201 [17] it is the tabular benchmark entry, for NAS-Bench

Experiments on Tabular Benchmarks
NAS-Bench-101 For our experiments on NAS-Bench-101, we first pretrain our generator for generating valid graphs on the NAS-Bench-101 search space. This step does not require information about the performance of architectures and is therefore inexpensive. The pretrained generator is then used for all experiments on NAS-Bench-101. Our NAS algorithm is initialized by randomly sampling 16 architectures from the search space, which are then weighted by the weighting function W = w(G) G∼p D . Then, latent space optimized architecture search is performed by iteratively retraining the generator coupled with the MLP surrogate model for 15 epochs and generating 100 architectures of which the top 16 (according to their accuracy prediction) are evaluated and added to the training data. This step is repeated until the desired number of queries is reached. When generating architectures, we sample from a grid, containing the 99%-quantiles from N (0, 1) uniformly distributed. This way, we sample more distributed latent variables for better latent space coverage. We compare our method to the VAE-based search method Arch2vec  Table 1. Here, we report the mean over 10 runs. Results including the standard deviation can be found in the supp. mat. Note, we search for the architecture with the best validation accuracy and report the corresponding test accuracy. Furthermore, we plot the search progress in Figure 3 (bottom left). As we can see, our model AG-Net improves over all state-of-the-art methods, not only at the last query of 300 data points, reaching a top 1 test accuracy of 94.2%, but is also almost any time better during the search process.
A direct comparison to the recently proposed GANAS [44] on NAS-Bench-101 is difficult, since GANAS searches on NAS-Bench-101 until they find the best architecture in terms of validation accuracy, whereas we limit our search to a maximal amount of 192 queries and are able to find high-performing architectures already in this small query setting. The comparison of AG-Net to the generator paired with an XGBoost [10] predictor shows that our end-to-end learnable approach is favorable even over potentially stronger predictors. NAS-Bench-201 This benchmark contains three different image classification tasks: CIFAR-10, CIFAR-100 [28] and ImageNet16-120 [14]. For the experiments on NAS-Bench-201 [17] we retrain AG-Net in the weighted manner for 30 epochs. In this setting, we also compare AG-Net to two recent generative models [44,23]. SGNAS [23] trains a supernet by uniform sampling, following SETN [16]. Additionally a CNN based architecture generator is trained to search architectures on the supernet. When comparing with [65], we also adopt their evaluation scheme of adding only the best-performing architecture (top-1) to the training data instead of top-16 as in our other experiments.
We report the search results for different numbers of queries for the NAS-Bench-201 dataset in Table 2. In addition, we plot the search progress in terms of queries in Figure 3 (top). Our method provides state-of-the-art results on all datasets for a varying number of queries. Most importantly, AG-Net shows strong performance in the few-query regime compared to [65] with the exception of CIFAR-100, proving its high query efficiency. ‡ We reran this experiment using the implementation from [58].
† We reran these experiments using the official implementation from [55,56,57], with the same initial training data and amount of top k architectures as for AG-Net.  Table 3 (right) and visualized in Figure 3 (bottom right). Our AG-Net improves over all stateof-the-art methods by a substantial margin and using XGB as a predictor even improves the search further. ImageNet Experiments The previous experiment on NAS-Bench-301 [48] shows the ability of our generator to generate valid architectures and to perform well in the DARTS [34] search space. This allows for searching a well-performing architecture on ImageNet [15]. Yet evaluating up to 300 different found archi-  tectures on ImageNet is extremely expensive. Our first approach is to retrain the best found architectures on the CIFAR-10 [28] image classification task from the previous experiment on NAS-Bench-301 (AG-Net and the XGBoost adaptions) on ImageNet [15]. Our second approach is based on a training-free neural architecture search approach. The recently proposed TE-NAS [11] provides a training-free neural architecture search approach, by ranking architectures by analysing the neural tangent kernel (NTK) and the number of linear regions (NLR) of each architecture. These two measurements are training free and do not need any labels. The intuition between those two measurements is their implication towards trainability and expressivity of a neural architecture and also their correlation with the neural architecture's accuracy; NTK is negatively correlated and NLR positively correlated with the architecture's test accuracy. We adapt this idea for our search on ImageNet and search architectures in terms of their NTK value and their number of linear regions instead of their validation accuracy. We describe the detailed search process in the supp. mat. subsection C.5.    Table 4 shows the results. Note that our latter described search method on ImageNet is training-free (as TE-NAS [11]) and the amount of queries displays the amount of data we evaluated for the zero cost measurements. Other query information include the amount of (partly) trained architectures. Furthermore, the displayed differentiable methods are based on training supernets which can lead to expensive training times. The best found architectures on NAS-Bench-301 [48] (CIFAR-10) result in comparable error rates on ImageNet to former approaches. As a result, our search method approach is highly efficient and outperforms previous methods in terms of needed GPU days. The result in terms of top-1 and top-5 error rates are even improving over the one from previous approaches when using the training free approach.

Experiments on Hardware-Aware Benchmark
Next, we apply AG-Net to the Hardware-Aware NAS-Benchmark [30]. We demonstrate in two settings that AG-Net can be used for multi-objective learning. The first setting (Joint=1 ) is formulated as constrained joint optimization: where f (·) evaluates architecture G for accuracy and g h (·) evaluates for latency given a hardware h ∈ H and a user-defined latency constraint L. The second setting (Joint=0 ) is formulated as constraint objective: max where we drop the optimization on latency and only optimize accuracy given the latency constraint. The loss function to train our generator in these settings is updated from Equation 2 to: where α is a hyperparameter trading off generation and prediction loss, and λ is a hyperparameter trading off both prediction targets C 1 (accuracy) and C 2 (latency).
To perform LSO in the joint objective setting from Equation 4, we rank the training data D for both accuracy and latency jointly by summing both with varying devices and latency (Lat.) constraints in two multi-objective settings: Joint=0 optimizes accuracy under latency constraint, while Joint=1 optimizes for accuracy and latency jointly. We report the best found architecture out of 10 runs with their corresponding latency, as well as the mean of these runs. We compare to random search as a strong baseline [31]. Feasibility (Feas.) is the proportion of evaluated architectures during the search that satisfy the latency constraint (larger is better). The optimal architecture (*) is the architecture with the highest accuracy satisfying the latency constraint.  Figure 4 depicts searches with our model in both optimization settings on Pixel 3 with different latency conditions. More results on different hardware and latency constraints are shown in Table 5. We observe that either optimization setting outperforms the random search baseline in almost all tasks. Additionally, our method is able to find the optimal architecture for a task regularly (in 15 out of 20 tasks), which random search was not able to provide. When considering mean accuracy and feasibility of the best architectures of all runs, we see that Joint=1 is able to improve the ratio of feasible architectures found during the search substantially. This is to be expected given that the latent space is explicitly optimized for latency in this setting. Consequently, Joint=1 is able to find better-performing architectures compared to Joint=0 if the constraint restricts the space of feasible architectures strongly (see results on Raspi 4). The feasibility ratio of random search is an indicator on how restricted the space is. In most cases, the latency penalization seems to be sufficient to find enough well-performing and feasible architectures, as can be seen by the feasibility of Joint=0 which is greatly improved compared to random search. We show the development of feasibility over time from Table 5 in Figure 4.

Ablation Studies
In this section we analyse the impact of the LSO technique and the backpropagation ability to the search efficiency. Therefore, we compare our AG-Net with the latter named adaptions on the tabular benchmarks NAS-Bench-101 [66] and NAS-Bench-201 [17]. The results of our ablation study are reported in Table 6.
As we can see, the lack of weighted retraining decreases the search substantially.
In addition the results without backpropagation support that the coupling of the predictor's target and the generation process enables a more efficient architecture search over different search spaces. Thus, the combination of LSO and a fully differentiable approach improves the effectiveness of the search.

Conclusion
We propose a simple architecture generative network (AG-Net), which allows us to directly generate architectures without any additional encoder or discriminator. AG-Net is fully differentiable, allowing to couple it with surrogate models for different target predictions. In contrast to former works, it enables to backpropagate the target information from the surrogate predictor into the generator. By iteratively optimizing the latent space of the generator, our model learns to focus on promising regions of the architecture space, so that it can generate high-scoring architectures directly in a query and sample-efficient manner. Extensive experiments on common NAS benchmarks demonstrate that our model outperforms state-of-the-art methods at almost any time during architecture search and achieves state-of-the-art performance on ImageNet. It also allows for multi-objective optimization on the Hardware-Aware NAS-Benchmark.

Appendices
Section A provides an overview about the graph representations for each search space, we consider in the main paper. In section B we show additional ablation studies. In section C, we provide more details about the experimental settings. In subsection C.5 we provide additional details for our search method on the DARTS search space. In section D we describe details about the generator network, and in section E we list all hyperparameter settings of our experiments. Lastly, we include a visual intuition of the latent space optimization technique in section F.

A Search Space Representations
In this section we give more details about the search spaces we consider in the main paper.
A.1 NAS-Bench-101 For visualization purposes, we present in Figure 5 exemplary a DAG from the NAS-Bench-101 search space, with its corresponding node attribute matrix and its adjacency matrix. Note, a concatenation of the flatted node attribute matrix and the flatted upper triangular adjacency matrix is the representation our generator model is trained to learn; this holds for all search spaces. , and ImageNet16-120 [14]. This benchmark provides validation and test accuracy information for each of the three datasets. The cell structure is different compared to NAS-Bench-101: Each cell has |V | = 4 nodes and |E| = 6 edges, where the former represent feature maps and the latter denote operations chosen from the set O = {1 × 1 conv., 3 × 3 conv., 3 × 3 avg pooling, skip, zero}. Each intermediate edge is connected to two predecessor nodes. Each cell also contains two input nodes, which are the output nodes from the previous two cells. The overall network is created by stacking the normal and reduction cell.
In order to train our generative model to generate valid cells, we additionally randomly sample 500k architectures from the DARTS search space. We train our generative model to learn to generate valid cells independently of being a normal or reduction cell. In Figure 7 we visualize the adapted node attribute matrix and the adapted adjacency matrix to an exemplary DAG in the DARTS search space [34]. This is similar to the representation in [65]. . Note, for the NAS-Bench-X11 evaluations, each architecture from the NAS-Bench-NLP search space must be trained for three epochs to use the surrogate model, whereas NAS-Bench-Suite provides the surrogate model for NAS-Bench-NLP without learning curve information, but also accompanying a lower Kendall Tau rank correlation. For fast evaluations we use the latter surrogate for our experiments. In order to use the surrogate benchmark, the architecture representation is the same used in [64] with the modification that each hidden node is connected to the output node. An exemplary architecture representation is visualized in Figure 8. A next step is to analyse the 14, 332 provided architectures on uniqueness, which leads to 12, 107 unique architectures. Furthermore, since [64] and [37] only provide a surrogate model, which only considers architectures with up to 12 nodes, we also restrict our training data to this subset leading to a total of 7, 258 architectures.

A.4 NAS-Bench-NLP
We show experiments in the DARTs search space and on NAS-Bench-NLP in subsection 4.2.
In our experiments in subsection 4.3 we consider the latency information on the NAS-Bench-201 search space.

B Additional Ablation Studies
In this section we give an overview of different ablation studies with respect to the proposed AG-Net. Fig. 9: Architecture search on NAS-Bench-101. Reported is the mean over 10 trials for the search of the best architecture in terms of validation accuracy on the CIFAR-10 image classification task compared to strong predictor models.

B.1 Oracle Ablation
As we have seen in the previous section, our model AG-Net is able to find high-scoring architectures in various search spaces of different sizes and with different objectives. In addition, including the supposedly stronger predictor XGB  [10] leads to improvements for the search on NAS-Bench-NLP [27]. In this section, we include an even stronger architecture accuracy evaluation model, i.e. the benchmark query input itself (oracle). The comparison of the oracle benchmark (also including the ranking metric as for XGB in the main paper) to our AG-Net and XGB modifications are visualized in Figure 9. This figure demonstrates the high performance of our model in the low query area. The more queries are evaluated for the search, the better the oracle becomes, outperforming all other methods after 150 queries.

B.2 Latent Space Ablations
As we have seen in subsection 4.1, AG-Net improves over state-of-the art methods. For additional comparisons, we investigate different search methods in the latent space of the generative model, with samples z from a grid and also include baselines using the LSO approach. For the first experiment we use the generator solely as a data sampler from the generator's latent space without any retraining, for the latter baseline we retrain the generator during the search. For the optimization, we use Bayesian optimization, local search and random search.
Bayesian Optimization We use DNGO[50] as our uncertainty prediction model for the Bayesian optimization search strategy, with the basis regression network being a one-layer MLP with a hidden dimensionality of 128, which is trained for 100 epochs and expected improvement (EI) [39] as our acquisition function, which is mostly used in NAS. We set the best function value for the EI evaluation as the best validation accuracy of the training data. We sample 16 initial random latent space variables z ∼ U[−3, 3] and decode them to graph data using our pretrained generative model. These latent space variables and their corresponding validation architecture performances are then the inputs for the DNGO model for training. Again, the best 16 architectures are selected using EI in each round to be evaluated and added to the training data. This search ends when the total query amount of 300 is reached.

Random and Local Search
In addition to Bayesian Optimization as a comparison, we also include a random search [31] and local search investigation. Recently, [57] show that local search is a powerful NAS baseline, resulting in competitive results. Local search [57] evaluates samples and their neighborhood uniformly at random. An option to define the neighborhood is the set of architectures which differ from a sampled architecture by one node or edge. This can be done only in the discrete search space, given for example by the tabular NAS-Benchmarks. We have to adapt the neighborhood definition in our latent space for local search in this space. We sample a latent space variable z ∼ U[−3, 3], decode it and evaluate the generated neural architecture. Here, we define neighborhood as the Euclidean space around the sampled latent variable U ϵ (z) = {y ∼ U[−3, 3]|d(z, y) < ϵ}, with ϵ being sufficiently small. This neighborhood is then investigated until a local optimum in terms of validation accuracy is reached. Furthermore, we include a random search and local search comparison using weighted retraining. Here, we retrain the generative model in each search iteration for 1 epoch with the weighted objective function, ceteris paribus.
To compare with weight-sharing approaches, we also compare to the supernet from [23] for the NAS-Bench-201 search space. To compare our AG-Net with SGNAS, we use the supernet as our surrogate model to predict the architectures performance while retraining the generative model in the weighted manner. The results of our ablation studies are reported in Table 7. AG-Net improves over search methods on the latent space with and without LSO on both benchmarks, demonstrating that our generator in combination with our MLP surrogate model learns to adapt the distribution shift constructed by the weighted retraining best.
For further visualizations we also plot different ablation search methods over different query numbers in Figure 10 for both benchmarks NAS-Bench-101 and NAS-Bench-201. This figure demonstrates the high any-time performance of our method on both search spaces. For any number of available queries, our model is better in finding high-performing architectures from the latent space than other latent space based methods. Our proposed method, consisting of the generative and surrogate model combined with the latent space optimization, makes the architecture search focus on promising regions in the search space. This method could be trapped in local solutions, which we investigate experimentally in the following. First, the previous section already points out that our proposed method AG-Net improves over both local search methods with and without the latent space optimization approach. Thus, we assume that the latent space optimization learns properties of high-scoring architectures without being easily trapped in poor local solutions. The amount of samples drawn in each search iteration also provides a trade-off between diversity versus specificity. To investigate further how easily AG-Net could be trapped in a local solution, we test our method when it only uses in total the best k (predicted) architectures from our test samples and the training data as a new training set for the next search iteration (degenerative) and is thereby encouraged to forget about worse performing architectures. Figure 11 shows the search behaviour of the degenerative model with k = 16 and k = 32. Even in this case, AG-Net is not easily trapped in poor solutions.

C.1 Surrogate Model
In this section, we present details about the surrogate models used in the main paper. The MLP surrogate model used for our AG-Net is a 4-layer MLP with ReLU non-activation functions. The hidden size equals the input size. The input to the MLP surrogate model is the vector representation ∈ R n of our graphs: a concatenation of the flatted node attribute matrix and flatted upper triangular matrix of the adjacency matrix, which presents the edge scores, see section A for visualizations. Note, the vector dimension n differs across the search spaces due to the different maximal amount of nodes. Our AG-Net passes the output of our generator, i.e. a generated vector representation, as the direct input to our MLP surrogate model.
We consider as an alternative surrogate model the XGB [10] prediction model. The input to this prediction model is the vector representation of the architecture.

C.2 Search Algorithm
High-level descriptions of the unconstrained (subsection 4.1) and constrained (subsection 4.3) versions of our search algorithm are depicted in algorithm 1 and algorithm 2 respectively.

C.3 NAS-Bench-101
In this section, we give more information about the NAS-Bench-101 experiments from the main paper. Table 8 is the detailed version of Table 1 including the standard deviation. Table 9 is the detailed version of Table 2 including the standard deviation.

C.5 DARTS Search Space
Additional Results Table 10 is the detailed version of Table 3 including the standard deviation.
Search Process using NAS-Bench-301 For experiments in the DARTS [34] search space, we first train our generative model on generating valid cells, as visualized in Figure 7; here we do not distinguish between generating a normal or a reduction cell. Having a pretrained generative model for generating valid cell representations in the DARTS search space allows for searching well-performing architectures. Here we describe the search process for architectures evaluated on CIFAR-10 using the surrogate benchmark NAS-Bench-301 [48]. Since the DARTS search space is defined by a normal and reduction cell, we have to adapt the search process, compared to the search in the tabular benchmark search spaces, where the architectures differ between the DAG. We begin the search by randomly sampling 16 architectures from NAS-Bench-301. Next, we generate one normal cell. This cell is used to search for the best reduction cell in terms of cell optimizing both KN and NLR measurements. In each search iteration we generate reduction cells and calculate the KN and NLR for each combination of normal cell and reduction cell. The reduction cells are ranked according to their mean KN and their mean NLR (mean in terms of all three normal cells). The 16 best ranked reduction cells are then used for the next iteration of reduction cell search. The reduction cell search stops, when a maximum of 104 queries is reached. After that we use the best found reduction cell in terms of the lowest KN and the highest NLR for the next search for a normal cell. The next steps use this best found reduction cell as a starting point and searches for the best normal cell in the same manner as before. The search stops after a total of 208 queries and outputs an overall normal and reduction cell combination, leading to a DARTS [34] architecture, which we train on ImageNet [15] using the same training pipeline as [11]. . For both settings we need to adapt the surrogate model by including an additional predictor g(·) for latency. We implement g(·) equally to the performance predictor f (·), whereas both predictors  share weights in our experiments. We give a detailed overview of the hyperparameter settings in section E. Since we include an additional predictor, the training objective needs to be updated, as seen in Equation 6 with multiple targets. The risk of including multiple targets to the training objective is an exploding loss leading to reduced valid generation ability of our generative network. In order to overcome this problem, we scale each loss term by the largest one, such that each term is at most 1. This way, we have a more stable training.

C.6 NAS-Bench-NLP
Exemplary Searches for Other Devices In Figure 4 we showed an exemplary search result comparing random search with both of our constrained algorithm settings in the case of different latency constraints on a Pixel3. In the following, we show more examples on different devices in Figure 12. These plots show that both methods Joint=1 and Joint=0 outperform the random search baseline in all different device experiments. The same results as in the main paper holds Search Progress and Baselines Local search [57] is considered a strong baseline in NAS. In the case of constrained searches (as in HW-NAS-Bench), we noticed that it cannot perform well without adaptation. The vanilla local search algorithm expects as input a single randomly drawn architecture from the search space. However, this architecture is not guaranteed to be feasible in this setting, as its latency can be larger than the latency constraint. To circumvent this, we performed local search in the following settings: (a) local search vanilla setting with one randomly drawn architecture, and (b) local search initialized with 16 randomly drawn architectures. In each setting, local search continues to search the neighborhood of the next best architecture in terms of accuracy that satisfies the latency constraint. We noticed that initializing local search with 16 randomly drawn architectures improves its performance substantially, however, it is still not on par with random search [31] in this constrained search space. Consequently, we only show random search as the baseline in Table 5 to improve readability. In Figure 13 we show the progress of our algorithms (Joint=0 and Joint=1 ) compared to random search and local search in settings (a) and (b).

D.1 Generator Evaluation
Based on an investigation of autoencoder abilities from [65] and [35], we can examine the generation ability of our generative model. For that we train our generator on 90% of the overall dataset, and thus have a hold-out dataset of 10% for the tabular benchmarks. The generative model training on the surrogate benchmarks is a priori only on a subset of the overall dataset. Additionally, we sample 10, 000 random variables z ∼ N (0, 1) and decode them to graphs.  We report the results of this investigation in Table 12. Here, validity describes the ratio of valid graphs our generator model generates, uniqueness describes the portion of unique graphs from the valid generated graphs, and novelty is the portion of generated graphs not in the training set. It is not surprising for the NAS-Bench-301 and NAS-Bench-NLP search spaces, that our model is able to generate 100% unique and novel graphs, given the large size of both search spaces. This demonstrates that our simple generator model is able to generate valid graphs with high novelty and consequently is able to cover a substantial part of the search space. Table 12 also reports the training costs of the generative model on the complete dataset as described in section A on a single Tesla V100. We used for the experiments the OMNI cluster from the University of Siegen.

D.2 Generator Implementation Details
In this section we present more details about the generation model SVGe from [35]. The pseudo algorithm is described in algorithm 3. The modules f initNode , f addNode , f addEdges , f Embedding used in this code are two-layer MLPs with ReLU activation functions. Note, in contrast to SVGe, we don't sample within the 16 Table 5 at any time during the search progress in terms of the number of evaluated architectures (up to 320). Optimality is the mean validation accuracy of 10 runs per algorithm, normalized by the optimal value for each parameter setting (hence, optimum is at 1.0). (right) zoomed y-axis generation process, in order to allow for end-to-end learning with the prediction model for AG-Net.

E Hyperparameters
In this section we give a detailed overview about the hyperparameter for our generative network. We use pytorch [40] and pytorch geometric [19] for all our implementations. Table 13 presents all used hyperparameters for the generation training. We train our generator in a ticked manner; after every 5.000 train data, we evaluate our generator for validity ability. The used pretrained state dict for our search is then, the one, which the highest validation measurement, which is defined by randomly sample 10, 000 latent vectors z ∈ R 32 and generate architectures. The training is the same for all different search spaces.    Fig. 14: The latent space is reshaped in a way that promotes desired properties of generated architectures (in this example: accuracy). Consequently, it becomes more likely for the generator to generate architectures satisfying this property.