Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars
Authors: Simon Schrodi
Danny Stoll
Binxin Ru
Rhea Sanjay Sukthanker
Thomas Brox
Frank Hutter
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Architecture Search
Hierarchical Search Space
Context-free Grammars
Bayesian Optimization
TL;DR: We take a functional view of neural architecture search that allows us to construct highly expressive search spaces based on context-free grammars, and show that we can efficiently find well-performing architectures.

Abstract: The discovery of neural architectures from simple building blocks is a long-standing goal of Neural Architecture Search (NAS). Hierarchical search spaces are a promising step towards this goal but lack a unifying search space design framework and typically only search over some limited aspect of architectures. In this work, we introduce a unifying search space design framework based on context-free grammars that can naturally and compactly generate expressive hierarchical search spaces that are 100s of orders of magnitude larger than common spaces from the literature. By enhancing and using their properties, we effectively enable search over the complete architecture and can foster regularity. Further, we propose an efficient hierarchical kernel design for a Bayesian Optimization search strategy to efficiently search over such huge spaces. We demonstrate the versatility of our search space design framework and show that our search strategy can be superior to existing NAS approaches. Code is available at https://github.com/automl/hierarchical_nas_construction.

Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars
Simon Schrodi
Danny Stoll
Binxin Ru²
Rhea Sanjay Sukthanker
Thomas Brox
Frank Hutter!
University Freiburg
Unnivrsity of Oxford
lachrodi,stolld, sukthan brox, w @cs uni uni-freiburg.ee
robingrobots.om ox. ac.uk
Abstract
The discovery of neural architectures from simple building blocks is long- standing goal of Neural Architecture Search (NAS). Hierarchical search spaces are a promising step towards this goal but lack unifying search space design framework and typically only search over some limited aspect of architectures. In this work, we introduce a unifying search space design framework based on context-free grammars that can naturally and compactly generate expressive erarchical search spaces that are 100s of orders of magnitude larger than com- mon spaces from the literature. By enhancing and using their properties, we effectively enable search over the complete architecture and can foster regular- ity. Further, we propose an efficient hicrarchical kernel design for a Bayesian Optimization search strategy to efficiently search over such huge spaces. We demonstrate the versatility of our search space design framework and show that search strategy can be superior existing NAS approaches. Code is available at https:://// / / gigggut.bb...... com/ automm/hierarchiiei nas___n________ nas_construction.
Introduction
Neural Architecture Search (NAS) aims to automatically discover neural architectures with state-of- the-art performance. While numerous NAS papers have already demonstrated finding state-of-the-an architectures (prominently, e.g., Tan and Le [1]. Liu et al. [2]), relatively little attention has been paid to understanding the impact architectural design decisions on performance, such as the repetition of the same building blocks. Moreover, despite the fact that NAS is heavily-researched field with over 000 papers the last two years [3, 4], NAS has primarily been applied to over-engineered, restrictive search spaces (c.g., cell-based ones) that did not give rise to truly novel architectural patterns. In fact, Yang et al. [5] showed that in the prominent DARTS search space [6] the manually- defined macro architecture is more important than the searched cells, while Xie et al. [7] and Ru et al. [8] achieved competitive performance with randomly wired neural architectures that do not adhere to common search space limitations.
Hierarchical search spaces are promising step towards overcoming these limitations, while keeping the search space of architectures more controllable compared to global, unrestricted search spaces. However, previous works limited themselves to search only for hierarchical cell [9], linear maero topologies [1, 2, 10], required post-hoc checking and adjustment of architectures [8, 11]. This limited their applicability understanding the impact of architectural design choices on performance well search over all (abstraction) levels of neural architectures.
In this work, we propose a functional view of neural architectures and unifying search space design framework for the efficient construction of (hierarchical) search spaces based on Context-Free Gram- mars (CFGs). We compose architectures from simple multivariate functions in hierarchical manner
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

S
S Sequential (S, S, S)
Level
S
(equenttial(Rosiduualffff S, S), Residual(S, S, S), linear)
inea
Level 2
id, conv), Residual(conv, id, conv), linear)
Cony
conv
Cony
conv
Lnnar
Level
Derivation of the function composition of the neural architecture from Equation I (left). Note that the derivations correspond to edge replacements [14-16] the computational graph repre- sentation (right). The intermediate derivations provide various granularities of neural architecture. Appendix A provides the vocabulary of primitive computations and topological operators.
Figure I:
using the recursive nature of CFGs and consequently obtain function composition representing the architecture. Further, we enhance CFGs with mechanisms to efficiently define search spaces over the complete architecture with non-linear macro topology (e.g., see Figure 4 or Figure 10 in Appendix J for examples), foster regularity by exploiting that context-free frrex languages are closed under substitution, and demonstrate how to integrate user-defined search space constraints.
However, since the number of architectures scales exponentially in the number of hierarchical levels leading search spaces 100s of orders of magnitude larger than commonly used ones NAS for many prior approaches search becomes either infcasible (e.g.. DARTS [6]) or challenging (e.g.. regularized evolution [12]). As a remedy, propose Bayesian Optimization for Hierarchical Neural Architecture Search (BOHNAS), which constructs a hierarchical kernel upon various granularities of the architectures, and show its efficiency through extensive experimental evaluation.
Our contributions We summarize our key contributions below:
1. We propose a unifying search space design framework for (hierarchical) NAS based on CFGs that enables us to search across the complete architecture, i.e., from micro to macro, foster regularity, i.e., repetition of architectural patterns, and incorporate user-defined constraints (Section 3). We demonstrate its versatility in Sections 4 and 6.
2. We propose hierarchical extension of WAS-Bench-200 (as well as derivatives) to allow to study search over various aspects of the architecture, c.g., the macro architecture (Section 4).
3. We propose BOHNAS to efficiently search over large hierarchical search spaces (Section 5).
4. We thoroughly show how our search space design framework can be used to study the impact of architectural design principles on performance across granularities.
5. We show the superiority BOHNAS over common baselines on 6/8 (others on par) datasets above ttate-of-the-art methods, using the same training protocol, including, e.g., a 4.99 % improvement on ImageNet- 16- 120 using the MAS--ench-200 training protocol. Further, show that networks, transformers, or both) (Section 6).
effectively search on different types of search spaces (convolutional
6. We adhere to the NAS best practice checklist [13] and provide code at com/ altaaaulml//// /hi erarchchhi chwcalllcaaccccccccccccccccccc _tt__aanssss_cceeeee construction to foster reproducible NAS research (Appendix N).
2
Related work
We discuss related works in Neural Architecture Search (NAS) below and discuss works beyond NAS in Appendix B. Table 4 in Appendix B summarizes the differences between our proposed search space design based CFGs and previous works.
Most previous works focused on global [17, 18), hyperparameter-based [1], chain-structured [19-22], or cell-based [23] search space designs. Hierarchical search spaces subsume the aforementioned spaces while being more expressive and effective in reducing search complexity. Prior works considered n-level hierarchical assembly [2, 9, 24], parameterization of a hicrarchy of random

---

graph generators [8], or evolution of topologies and repetitive blocks [[1]. In contrast to these prior works, we search over all (abstraction) levels of neural architectures and do not require any post-generation testing and/or adaptation of the architecture [8, 11]. Further, we can incorporate user-defined constraints and foster regularity in the search space design.
Other works used formal "systems"; string rewriting systems [25, 26]. cellular (or tree-structured) encoding schemes [27-30], hyperedge replacement graph grammars [31, 32], attribute grammars [33], CFGs [10, 34-0J, And-Or-grammars [41], or a search space design language [42]. Different to these prior works, we search over the complete architecture with non- non-linear macro topologies, can incorporate user-defined constraints, and explicitly foster regularity.
For search, previous works, e.g., used reinforcement learning [17, 43], evolution [44], gradient descent [6, 45, 46], or Bayesian Optimization (BO) [18, 47, 48). To enable the effective use of BO on graph-like inputs for NAS, previous works have proposed
GP with specialized kernels [18, 48, 49), encoding schemes [47, 50), or graph neural networks as surrogate model [51-53]. In contrast these previous works, we explicitly leverage the hierarchical nature of architectures in the performance modeling of the surrogate model.
3 Unifying search space design framework
To efficiently construct expressive (hierarchical) NAS spaces, review two common neural archi- tecture representations and describe how they are connected (Section 3.1). In Sections 3.2 and 3.3 we propose CFGs and enhance them (or exploit their properties) efficiently construct expressive (hierarchical) search spaces.
3.1 Neural architecture representations
Representation as computational graphs A neural architecture can be represented an edge- attributed (or equivalently node-attributed) directed acyelic (computational) graph G(V, E, Oes m.). where o₂ is primitive computation (e.g., convolution) block) applied at edge e E E, and m, is merging operation for incident edges node e E V. Below is an example of an architecture with two residual blocks followed by linear layer:
computational graph itself (e.g., residual
id
id
linear
where the edge attributes conv, id, and linear correspond convolutional blocks, skip connections, or linear layer, respectively. This architecture can be decomposed into coomponnnts//raphhee across multiple hierarchical levels (see Figure the previous page): the operations convolutional blocks and skip connection construct the residual blocks, which construct with the linear layer the entire architecture.
Representation as function compositions composition of multivariate functions:
The example above can also naturally be represented as
id, conv), Residual id, conv), linear) (I) where the functions conv, id, linear, well Sequential and Resi dual are defined with an arity zero or three, respectively. We refer to functions with arity of zero as primitive computations and functions with non-zero arity topological operators that define the (functional/graph) structure. Note the close resemblance to the way architectures are typically implemented in code. To construct the associated computational graph representation (or executable neural architecture program), define a bijection & between function symbols and the corresponding computational graph (or function implemented in code, e.g., in Python), using predefined vocabulary. Appendix 1) shows exemplary how a functional representation is mapped to its computational graph representation.
Finally, we introduce intermediate variables I; that share architectural patterns across an architecture, e.g., residual blocks Fres = Residual(conv, id, conv). Thus, we can rewrite the architecture from Equation as follows:
Sequential (Fres: Fress linear)
3

---

3.2 Construction based on context-free grammars
To construct neural architectures as compositions of (multivariate) functions, we propose to use Context-Free Grammars (CFGs) [54] since they naturally and in a formally grounded way generate (expressive) languages that are (hierarchically) composed from an alphabet, i.e., the set of (multivari- ate) functions. CFGs also provide simple and formally grounded mechanism to evolve architectures that ensure that evolved architectures stay within the defined search space (see Section for details). With our enhancements of CFGs (Section 3.3), we provide a unifying search space design framework that is able to represent all search spaces we are aware of from the literature. Appendix provides examples for NAS-Bench
[50], DARTS [6], Auto-DeepLait [2], hierarchical cell space [9], Mobile-net space [55], and hierarchical random graph generator space [8].
Formally, CFG G (N, Σ, S) consists of a finite set of nonterminals N and terminals E (i.e., the alphabet of functions) with Nn 0, finite set of production rules = {A + 3| E N, E (N U }) where the asterisk denotes the Kleene star [56], and a start symbol S E N. To generate a string (i.e., the function composition), starting from the start symbol S, we recursively replace nonterminals with the right-hand side of production rule, until the resulting string does not contain any nonterminals. For example, consider the following CFG in extended Backus-Naur form [57] (refer to Appendix C for background on the extended Backus-Naur form):
S Sequential(S, S, S) Residual S, S) conv id linear
Figure! I shows how we can derive the function composition of the neural architecture from Equation I from this CFG and makes the connection to its computational graph representation explicit. The set of all (potentially infinite) function compositions generated by a CFG is the language L(9), which naturally forms our search space. Thus, the NAS problem can be formulated as follows:
arg min L(((W), D) wEL(G)
where is an error measure that we seek to minimize for some data D, e.g., final validation error of a fixed training protocol.
3.3 Enhancements
Below, we enhance CFGs or utilize their properties to efficiently model changes in the spatial resolution, foster regularity, and incorporate constraints.
Flexible spatial resolution flow Neural architectures commonly build a hierarchy of features that are gradually downsampled, e.g., by pooling operations. However, many NAS works do not search over the macro topology of architectures (e.g.. Zoph et al. [23]). only consider linear macro topologies testing for resolution mismatches with an adjustment
(e.g., Liu et al. [2], or require scheme (e.g., Ru et al. [8], Mükkullinen et al. [11]).
To overcome these limitations, we propose a simple mechanism search over the macro topology with flexible spatial resolution flow by overloading nonterminals: We assign to each nonterminal the number of downsampling operations required in its subsequent derivations. This effectively distributes the downsampling operations recursively across the architecture.
For example, the nonterminals D1, D2 of the production rule D2 Residual(DI, D2, D1) indicate that or downsampling operations must be applied in their subsequent derivations, respec- tively. Thus, the input features of the residual topological operator Residual will be downsampled twice in both of its paths and, consequently, the merging paths will have the same spatial resolution. Appendix D provides an example that also makes the connection to the computational graph explicit.
Fostering regularity through substitution To foster regularity, i.e., reuse of architectural patterns, we implement intermediate variables (Section 3.1) by exploiting the property that context- -ree languages are closed under substitution. More specifically, we can substitute an intermediate variable J;; E with a string wa of another language L', e.g., constructing cell topologies. By substituting the same intermediate variable multiple times, we reuse the same architectural pattern (w) and, thereby, effectively foster regularity. Note that the language T,' may turn have its own intermediate variables that map to languages constructing other architectural patterns, c.g., activation functions.

---

For example, consider the languages m( and ((G.) constructing the macro or cell topology of a neural architecture, respectively. Further, we add single intermediate variable 21 to the terminals Eg... that map to the string wi E T(Ge), e.g., the searchable cell. Thus, after substituting all 21 with w1, we effectively share the same cell topology across the macro topology of the architecture.
Constraints When designing a search space, we often want to adhere to constraints. For example, we may only want to have two incident edges per node as in the DARTS search space [6]- or ensure that for every neural architecture the input is associated with its output. Note that such constraints implicate -eatex---ennsttivityy but CFGs by design are context-free free. Thus, to still allow for constraints, we extend the sampling and evolution procedures of CFGs by using a (one-step) lookahead to ensure that the next step(s) in sampling procedure (or evolution) does not violate the constraint. We provide more details and comprehensive example in Appendix E.
4 Example: Hierarchical NAS-Bench-201 and its derivatives
In this section, propose hierarchical extension to JAS-Bench-201 [58]: hierarchical NAS- AaS-Becch- 20/ that subsumes (cell-based) NAS-Bench-201 [58] and additionally includes a search over the macro topology well as the parameterization of the convolutional blocks, i.e., type of convolution, activation, and normalization. Below, is the definition of our proposed hierarchical NAS-Bench-201:
D2 Sequentia13(DI, D1, D0) Sequemtial33DO, D1, D1) Sequentiaa4(D1, D1, DO, DO)
D1 == Sequential3(C, C, D]
Sequential4(C; C, C, D)
Reaidual3(C, C, D, D)
DO == Sequential3(C, C, CT.)
Sequentia14(C, C, C, CT.) Residual3(C, C, CL, CT))
D Sequential2(CL, down) Sequential3(CI, CL, down) Residual2[CL, down, down)
C == Sequentia12(II, CL)
Sequential3(CI, CL, CI.)
Reeidual2(CI, CL, CI)
CL Cell(OP, OP, OP, OP, OP, OP)
OP == 2ero | id | CONVBLOCK avg_pool
CONVBLOCK == Sequential3(ACT, CONV, NORM)
ACT relu hardswish mish
CONV =- convix1 conv3x3 dconv3x3
NORM = batch instance
1ayer
(5)
The blue productions of the nonterminals {D2, D1, DO, D, C} construct the (non-linear) macro topology with flexible spatial resolution flow, possibly containing multiple branches. The red and yellow productions of the nonterminals {CL, OP} construct the MAS-Bench-201 cell and [CONYBLOCK, ACT, CONV, NORM) parameterize the convolutional block. Note that the red productions correspond to the original NAS-Bench-22 201 cell- (sub)space [58]. Appendix A provides the vocabulary of topological operators and primitive computations and Appendix D provides comprehensive example on the construction of the macro topology.
We omit the stem (i.e., 3x3 convolution followed by batch normalization) and classifier head (i.e., batch normalization followed by ReLU, global average pooling, and linear layer) for simplicity. We used element-wise summation as merge operation. For the number of channels, we adopted the common design to double the number of channels whenever we halve the spatial resolution. Alternatively, we could handle a varying number of channels by using, e.g., depthwise concatenation as merge operation; thereby also subsuming NATS Bench [59]. Finally, we added constraint to ensure that the input is associated with the output since zero could disassociate the input from the output.
Search space capacity The search space consists of ca. 10446 architectures (Appendix G describes how to compute the search space size), which is hundreds of orders of magnitude larger than other popular (finite) search spaces from the literature, e.g., the NAS-Bench-201 or DARTS search spaces only entail ca. 1.5 10a and 1 architectures, respectively.
Derivatives We can derive several variants of our hierarchical NAS-Bench-201 search space (hierarchical). This allows us to investigate search space as well as architectural design principles in Section 6. We briefly sketch them below and refer for their formal definitions to Appendix J.2:
fixed+shared (cell-based): Fixed macro topology (only leftmost blue productions) with the single, shared NB-201 cell (red productions); equivalent to NAS-Bench-201 [58].
5

---

hierarchical +shared: Hierarchical macro search (blue productions) with a single, shared cell (red & yellow productions).
hierarchical caaeecaaanooonnnn tnon-linear:
Hierarchical macro search with more non-linear macro topologies (i.e., some Sequential are replaced by Di Diamond topological operators), allow- ing for more branching at the macro-level of architectures.
hierarchical cal wwwearhhhhahthhhheeeraaaaaaaaaae +shared linear: Hierarchical macro search with more non-linear macro topologies (more branching at the macro-level) with single, shared cell.
5 Bayesian Optimization for hierarchical NAS
Expressive (hierarchical) search spaces present challenges for NAS search strategies due to their huge size. In particular, gradient-based methods (without any yet unknown novel adoption) do not scale to expressive hierarchical search spaces since the supernet would yield an exponential number of weights (Appendix G provides an extensive discussion). Reinforcement learning approaches would also necessitate a different controller network. Further, we found that evolutionary and zero- cost methods did not perform particularly well on these search spaces (Section 6). Most Bayesian Optimization (BO) methods also did not work well [18. 52] or were not applicable (adjacency [50] or path encoding [47]), except for NASBOWL [48] with its Weisfeiler-Lehman (WL) graph kernel design in the surrogate model.
Thus, we propose the novel BO strategy Bayesian Optimization for Hierarchical Neural Architecture Search (BOHNAS), which (i) uses a novel hierarchical kernel that constructs a kernel upon different improve performance modeling, and (ii) adopts ideas from
granularities of the architectures grammar-guided genetic programming [60, 61] for acquisition function optimization of the discrete space of architectures. Below, we describe these components and provide more details in Appendix H.
Hierarchical Weisfeiler-L.hhman kernel (hWL. We adopt the WI graph kernel design [48, 62] for performance modeling. However, modeling solely based on the final computational graph of the architecture, similar to Ru et al. [48], ignores the useful hierarchical information inherent in our construction (Section 3). Moreover, the large size of the architectures also makes it difficult to use single WL kernel to capture the more global topological patterns.
As remedy, we propose the hierarchical WL kernel (hWL) that hierarchically constructs kernel upon various granularities of the architectures. efficiently captures the information in all hierarchical levels, which substantially improves search and surrogate regression performance (Section 6). To compute the kernel, we introduce fold operators Fi that remove all substrings (i.c., inner functions) beyond the I-th hierarchical level, yielding partial function compositions (i.e., granularities of the architecture). E.g., the folds F,, F2 and F3 for the function composition w from Equation are:
F3 (w) Sequential (Reiiuuuial id, conv), Residual(cony, id, conv), linear). F2 (w) = Sequential (ReuentialRResidullll (Residual, Residual, linear)
Fi (w) Sequential
Note that Fa(w) = w and observe the similarity to the derivations in Figure I. We define hWL for two function compositions wi, Wj constructed over L hierarchical levels, as follows:
kiww (wi, wi)
Σ kwr. (TT(())))))))
where & bijectively maps the function compositions to their computational graphs. The weights A govern the importance of the learned graph information different hierarchical levels (granularities of the architecture) and can be optimized (along with other GP hyperparameters) by maximizing the marginal likelihood. We omit the fold F1 (w) since it does not contain any edge features. Appendix H.2 provides more details our proposed hWL.
Grammar-guided acquisition function optimization Due the discrete nature of the function compositions, we adopt ideas from grammar-based genetic programming [60, 61] for acquisition function optimization. For mutation, we randomly replace substring (i.e., part of the function composition) with new, randomly generated string with the same nonterminal as start symbol. For

---

Test errors [%]] of the best found architectures BOHNAS (ours) compared with the respective best methods from the literature using the same training protocol. Table 6 (Appendix J.3), Table 2, and Tables 9 and (Appendix L..3) provide the full tables the NAS-Bench-201 activation function search, or DARTS training protocols, respectively.
Table 1:
Dataset
C10
C100
IM16-120
CTile
AddNIST NB201
C10
C10 DARTS
IM
Training prot.
NB201
NB201
NB201
NB201
Act. func.
DARTS (transfer)
Previous best
26.51
53.15
35.75
8.32
2.65
24.63*
BOHNAS
5.02
25.41
48.16
30.33
4.57
8.31
2.68
24.48
Difference
+0.51
+1.1
+4.99
+5.42
+2.83
+0.01
-0.03
+0.15
includes hicrarchical search space variants. reproduced results using reported genotype.
CIFAR-10
CIEAR-100
ImageNeet-66112
CIFARTHlc
AddXIST
Via grron 18
58
50
56
20
54
27
52
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
BOTINAS
NASBOWL
RS
NASBOT
RE
AREA
Figure 2: Mean + standard error the hierarchical NAS- -AS-Bench-201 search space. Appendix J.3
provides further results and extensive analyses.
crossover, we randomly swap two substrings produced by the same nonterminal as start symbol. We consider two crossover operators: a novel self-crossover operation swaps two substrings of the same string, and the common crossover operation swaps substrings of two different strings. Importantly, all evolutionary operations by design only result in valid function compositions (architectures) of the generated language. We provide visual examples for the evolutionary operations in Appendix H.
In our experiments, we used expected improvement acquisition function and the Kriging Believer [63] to make use of parallel compute resources to reduce wallclock time. The Kriging Believer hallu- cinates function evaluations of pending evaluations at each iteration to avoid redundant evaluations.
6 Experiments
In the section, we show the versatility of our search space design framework, show how we can study the impact of architectural design choices on performance, and show the search efficiency of our search strategy BOHNAS by answering the following research questions:
RQ1 How does our search strategy BOHNAS compare to other search strategies?
RQ2 How important is the incorporation of hierarchical information in the kernel design?
RQ3 How well do zero-cost proxies perform in large hierarchical search spaces?
RQ4 Can we find well-performing transformer architectures for, e.g., language modeling?
RQS Can we discover novel architectural patterns (e.g., activation functions) from scratch?
RQ6 Can find better-performing architectures in huge hierarchical search spaces with limited
number of evaluations, despite search being more complex than, e.g., in cell-based spaces?
RQ7 How does the popular uniformity architecture design principle, i.c., repetition of similar architectural patterns, affect performance?
RQ8 Can we improve performance further by allowing for more non-linear macro architectures while still employing the uniformity architecture design principle?
To answer these questions, we conducted extensive experiments on the hierarchical (Section 4), activation function [64], DARTS [6], and newly designed transformer-based search spaces (Appendix M.2). The activation function search shows the versatility of our search space design framework, where we search not for architectures, but for the composition of simple mathematical
7

---

CIFAR-10
CIFAR-100
IruageNet-166 16-120
CIFARTile
AddNIST
Val enron 198)
10
54
50
30
0 20 60 100
0 25 do
70
100
0 20 5o 76
100
20 50 To
100
25 60 75 150
Evaluations
Evaluations
Evaluations
Evalnations
Evaluations
hierarchical
fixed I shared (cell-based)
hierarchical shared
hicrarchical + non-linear
hierarchical- -hae---sdared-d-d-iieeeeeee
Figure 3: Mean 11 standard enror for several architecture search space designs (see Section 4 and Appendix J.2 for their CFGs) using BOHNAS for search.
functions. The search on the DARTS search space shows that BOHNAS is also backwards-compattible with cell-based spaces and achieves on-par or even superior performance to state-of-the-ar gradient- based methods; even though these methods are over-optimized for the DARTS search space due to successive works targeting the same space. Search on the transformer space further shows that our search space design framework is also capable to cover the ubiquitous transformer architecture. To promote reproducibility, we discuss adherence to the NAS research checklist in Appendix N. We provide supplementary results (and ablations) in Appendices J.3, K.3, L.3 and M.3.
6.1 Evaluation details
We search for a total of 100 or 1000 evaluations with random initial design of 10 or 50 architectures on three seeds [777, 888, 999) or one seed (777) on the hierarchical function search space, respectively. We followed the training protocols and experimental setups of Dong and Yang [58] or Ramachandran et [64]. For search on the DARTS space, we search for one day with a random initial design of 10 on four seeds (666, 777, 888, 999) and followed the training protocol and experimental setup Liu et al. [6]. Chen al. [45]. For searches on transformer-bant based spaces, we ran experiments each for one day with random initial design of 10 on one seed (777), ) In each evaluation, we fully trained the architectures or activation functions (using ResNet-20) and recorded the final validation error. We provide full training details and the experimental setups for each space in Appendices J. 1, K.2, L.2 and M.I. We picked the best architecture, activation function, DARTS cells, transformer architectures based on the final validation error (for NAS- NAS-Bench-22 Bench-2201 activation function, and transformer- bassed search experiments) or on the average of the five last validation errors (for DARTS). All search experiments used 8 asynchronous workers, each with single NVIDIA RTX 2080 Ti GPU.
or activation
We chose the search strategies Random Search (RS), Regularized Evolution (RE) [12], AREA [65], NASBOT [18], and NASBOWL [48] as baselines. Note that we could not use gradient- based approaches for experiments the hierarchical NAS-Bench-201 search space since they do not scale to large hierarchical search spaces without any novel adoption (see Appendix for a discussion). Also note that we could not apply AREA to the activation function search since it uses binary activation codes of ReLU as zero-cost proxy. Appendix provides the implementation details of the search strategies.
6.2 Results
In the following we answer all of the questions RQI-RQ8. Figure shows that BOHNAS finds supe- rior architectures on the hierarchical NAS-Bench-201 search space compared to common baselines (answering RQ1); including NASBOWL, which does not use hierarchical information in its kernel design (partly answering RQ2). and cost-oos- search strategy AREA (partly answering RQ3). We further investigated the hierarchical kernel design in Figure 12 in Appendix J.3 and found that substantially improves regression performance of the surrogate model, especially smaller amounts of training data (further answering RQ2). We also investigated other zero-cost proxies but they mostly inferior to the simple baselines 12- n-rrrm [66] or flops [67] (Table in Appendix J.3, further answering RQ3). We also found that BOHNAS is backwards compatible with cell-basee search spaces. Table I shows that we found DARTS cells that are on-par on CIFAR-I0 and (slightly) superior on ImageNet (with search on CIFAR- 10) to state-of-the-art gradient- methods; even though those are optiiozde due successive works targeting this particular space.

---

Our searches on the transformer-bast search spaces show that we can indeed find performing transformer architec- tures for, e.g., language modeling or sentiment analysis (RQ4). Specifically, we found a transformer for generative language modeling that achieved best validation loss of 1,4386 with only 3.33 M parameters. For comparison, Karpathy [68] re- ported a best validation loss of 1. 1.4697 with transformer with 10.65 M parameters. Note that as we also searched for the embedding dimensionality. that acts globally the architec- ture, we combined our hierarchical graph kernel (hWL) with Hamming kernel. This demonstrates that our search space design framework and search strategy. BOHNAS, are applica- ble not only NAS but also to joint NAS and Hyperparameter Optimization (HPO). The found classifier head for sentiment analysis achieved a test accuracy of 92.26 %. We depict the found transformer and classifier head in Appendix M.3.
Table 2: Results of the activation function search on CIFAR- 10 with ResNet-20.
Search strategy
Test error [%]
ReLU
8.93
Swish
8.61
RS
8.91
RE
8.47
NASBOWL
8.32
BOHNAS
8.31
The experiments on activation function search (see Table 2) show that our search space design framework as well as BOHNAS can be effectively used to search for architectural patterns from even more primitive, mathematical operations (answering RQ1 RQ5). Unsurprisingly, in this case, NASBOWL is par with BOHNAS, since the computational graphs of the activation functions small. This result motivates further steps in searching in expressive search spaces from even more atomic primitive computations.
To study the impact of the search space design and, thus, the ar- chitectural design choices on performance various derivatives of our proposed hierarchical NAS-Bench-201 search space (see Section 4 and Appendix J.2 for the formal defi- nitions of these search spaces). Figure 3 shows that we can indeed find better-performing architectures in hierarchical search spaces compared to simpler bel--based spaces, even though search is more complex due to the substantially larger search space (answering RQ6). Further, we find that the popular architectural uniformity design principle of reusing the same shared building block across the architecture (search spaces with keyword shared in Figure 3) improves performance (answering RQ7). This aligns well with the research in (manual and automated) architecture engineering over the last decade. However, also found that adding more non- linear macro topologies (search spaces with keyword non-linenn in Figure 3), thereby allowing for more branching at the macro- level of architectures, surprisingly further improves performance (answering RQ8). This is in contrast the common linear macro architectural design without higher degree of branching at the macro-level; except for few notable exceptions [69, 70].
we used
While most previous works in NAS focused on cell-based search spaces, Table reveals that our found architectures are superior in 6/8 cases (others are on par) to the architectures found by previous works. On the NAS-Bench-201 training protocol, our best found architectures on CIFAR-10, CIFAR-100, and ImageNet- 16-120 (depicted in Figure 4) reduce the test error by 0.51 %. 1.1 %, and 4.99 % to the best reported numbers from the literature, respectively. Notably, this is even better than the optimal cells in the cell-based -AS-Bench--01 search space (further answering RQ6). This clearly emphasizes the potential of NAS going beyond cell-based search spaces (RQ6) and prompts us to rethink macro architectural design choices (RQ7, RQ8).
Figure 4: Best architecture found by BOHNAS for ImageNet-16-120 in the hierar- chical NAS-Bench-201 search space. Best viewed with zoom. Figure 10 in Appendix J.3 provides the abbreviations of the operations and the architectures for the other datasets.

---

7 Limitations
Our versatile search space design framework based on CFGs (Section 3) unifies all search spaces we are aware of from literature in single framework; see Appendix F for several exemplar search spaces, and allows search over all (abstraction) levels of neural architectures. However, we cannot construct any architecture search space since we are limited to context-free free languages (although our enhancements in Section 3.3 overcome some limitations), c.g., architecture search spaces of the type {a"b"c" cm E N cannot be generated by CFGs (this can be proven using Ogden's 's lemma [71]).
While more expressive search spaces facilitate the search over wider spectrum of architectures, there is an inherent rrade-off between the expressiveness and the search complexity. The mere existence of potentially eetter-performing architectures does not imply that we can actually find them with a limited search budget (Appendix J.3); although our experiments suggest that this may be more feasible than previously expected (Section 6). In addition, these potentially may not work well with current training protocols and hyperparameters due to interaction effects between them and over-optimization for specific types of architectures. A joint optimization of neural architectures, training protocols, and hyperparameters could overcome this limitation, but further fuels the trade-off between expressiveness and search complexity.
performing architectures
Finally, our search strategy, BOHNAS, is sample-based and therefore computationally intensive (search costs for up to 40 GPU days for our longest search runs). While it would benefit from weight sharing, current weight sharing approaches are not directly applicable due to the exponential increase of architectures and the consequent memory requirements. We discuss this issue further in Appendix G.
8 Conclusion
We introduced a unifying search space design framework for hierarchical search spaces based on CFGs that allows us to search over all (abstraction) levels of neural architectures, foster regularity, and incorporate user-defined constraints. To efficiently search over the resulting huge search spaces, we proposed BOHNAS, an efficient BO strategy with a kernel leveraging the available hierarchical information. Our experiments show the versatility of our search space design framework and how it can be used to study the performance impact of architectural design choices beyond the micro- level. We also show that BOHNAS can be superior to existing NAS approaches. Our empirical findings motivate further steps into investigating the impact of other architectural design choices on performance as well as search on search spaces with even more atomic primitive computations. Next steps could include the improvement of search efficiency by means of multi-fidelity optimization or meta-learning, or simultaneously search for architectures and the search spaces themselves.
Acknowledgments and Disclosure of Funding
This research was funded by the Deutsche Forsehungssermeinscaatt (DFG, German Research Founda- tion) under grant number 41 7969288,, and the Bundesministerium für Umwelt, Naturschutz, nukleare Sicherheit und Verbraucherschutz (BMUV, German Federal Ministry for the Environment, Nature Conservation, Nuclear Safety and Consumer Protection) based on resolution of the German Bun- destag (67KI2029A). Robert Bosch GmbH is acknowledged for financial support. We gratefully acknowledge support by the European Research Council (ERC) Consolidator Grant "Deep Learning 2.0" (grant no. 101045765). Funded by the European Union This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the ERC. Neither the European Union nor the ERC can be held responsible for them.
Funded by
the European Union
10

---

References
[1] Mingxing Tan and Quoe V. Le. EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. International Conference on Machine Learning. 2019.
[2] Chenxi Liu, Liang-Chien Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L. Yuille, and Li Fei- Fei. Laeppae Hicrarchical Neural Architecture Search for Semantic Image Segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
[3] Difan Deng and Marius Lindauer. https: //wp::///wwwwwe automl. www.o//ggggg//////ooooooo// automl/literatune nerrraall-nneura-----e www.errraa-aratttttr-eeeaaaaea [Online; accessed 4- Mayy33
Literature on Neural Architecture Search. 2022.
[4] Colin White, Mahmoud Safari, Rhea Sukthanker, Binxin Ru, Thomas Elsken, Arber Zela, Debadeepta Dey, and Frank Hutter. Neural Architecture Search: Insights from 1000 Papers. arXiv, 2023.
[5] Antoine Yang, Pedro M. Esperança, and Fabio M. Carlueci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations, 2020.
[6] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable Architecture Search. In International Conference on Learning Representations, 2019.
[7] Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring Randomly Wired Neural Networks for Image Recognition. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2019.
[8] Robin Ru, Pedro Esperança, and Fabio Maria Carlucci. Neural architecture generator optimization. In Advances in Neural Information Processing Systems, 2020.
[9] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hier- archical Representations for Efficient Architecture Search. In International Conference on Learning Representations, 2018.
[10] Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro. DENSER: deep evolution- ary network structured representation. Genetic Programming and Evolvable Machines, 2019.
[11] Risto Miikkulainen, Jason Liang, Elliot Meyerson, Aditya Rawal. Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, et al. Evolving Deep Neural Networks. In Artificial Intelligence in the Age of Neural Networks and Bruin Computing. Elsevier, 2019.
[12) Esteban Real, Alok Aggarwal, Yanping Huang. and Quoe V. Le. Regularized Evolution for Image Classifier Architecture Search. In Proceedings of the National Conference on Artificial Intelligence, 2019.
[13] Marius Lindauer and Frank Hutter. Best practices for scientific research neural architecture search. Journal of Machine Learning Research, 2020.
[14] Annegret Habel and Järs-Jörg Kreowski. On context- free graph languages generated by edge replacement. Graph-Grammnn Grammars and Their Application Computer Science, 1983.
[15] Annegret Habel and Hans-Jörg Kreowski. Characteristics of graph languages generated by edge replace- ment. Theoretical Computer Science, 1987.
[16] Frank Drewes, Hans-Jörg Kreowski, and Annegret Habel. Hyperedge replacement graph grammars. In Handbook Of Graph Granmars And Computing By Graph Transformation: Volume I: Foundations. World Scientific, 1997.
[17] Barret Zoph and Quoe V. Le. Neural Architecture Search with Reinforcement Learning. In International Conference Learning Representations, 2017.
[18] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnahás Póczos, and Eric Xing. Neu- ral Architecture Search with Bayesian Optimisation and Optimal Transport. Advances in Neural Information Processing Systems, 2018.
[19] Nicholas Roberts, Mikhail Khodak, Tri Dao, Liam Li, Christopher Ré, and Ameet Talwalkar. Rethinking Neural Operations for Diverse Tasks, Advances in Neural Information Processing Systems, 2021.
[20] Han Cai, Ligeng Zhu, and Song Han. ProxylesNNAS: Direct Neural Architecture Search on Target Task and Hardware. International Conference Learning Representations, 2019.

---

[21] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-All: Train One Network and Specialize it for Efficient Deployment. In International Conference Learning Represenlations. 2019.
[22] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. AutoFormer: Searching Transformers for Visual Recognition. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, 2021.
[23] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning Transferable Architectures for Scalable Image Recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2018.
[24] David So, Wojeiech Manke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Qune V. Le. Searching for Efficient Transformers for Language Modeling. In Advances Neural Information Processing Systems, 2021.
[25] Hiroaki Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex Systems, 1990.
[26] Egbert J. W. Boers, Herman Kuiper, Bart L. M. Happel, and Ida G. Sprinkhuizen- Biological Metaphors In Designing Modular Artificial Neural Networks. In International Conference on Artificial Neural Networks, 1993.
[27] Frederic Gruau. Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm. PhD thesis, Laboratoire de I'Informatique du Parallilisme, Ecole Normale Supirieure de Lyon, 1994.
[28] Sean Luke and Lee Spector. Evolving Graphs and Networks with Edge Encoding: Preliminary Report. In Late-breaking Papers of the Genetic Programming 96 conference, 1996.
[29] Edwin D. De Jong and Jordan B. Pollack. Utilizing Bias Evolve Recurrent Neural Networks. In International Joint Conference on Neural Networks, 2001.
[30] Han Cai, Jiacheng Yang. Weinan Zhang, Song Han, and Yong Yu. Path-Level Network Transformation for Efficient Architecture Search. In International Conference on Machine Learning, 2018.
[31] Martin Luerssen and David University of New South Wales, 2003.
Powers. On the Artificial Evolution of Neural Graph Grammars.
[32] Martin H. Luerssen. Graph Grammar Encoding and Evolution of Automata Networks. In Australasian Conference on Computer Science, 2005.
[33] Lean-Baptiste Mouret and Stéphane Doncieux. MENNAG: a modular, regular and hierarchical encoding for neural-network, based on attribute grammars. Evolutionary Intelligence, 2008.
[34] Christian Jacob and Jan Rehder. Evolution of neural net architectures by hierarchical grammar grasd genetic system. In Artificial Neural Nets and Genetic Algorithmss 1993.
[35] Jorge Couchet, Daniel Manrique, and Luis Porras. Grammar-Guided Neural Architecture Evolution. In International Work- Cork-Cooferrecce the Interplay Between Natural and Artificial Computation, 2007.
[36] Fardin Ahmadizar, Khabat Soltanian, Fardin AkhlaghianTTab, and Ioannis Tsoulos. Artificial neural network development by means of novel combination grammatical evolution and genetic algorithm. Engineering Applications of Artificial Intelligence, 2015.
[37] Qadeer Ahmad, Atif Ratiq, Muhammad Adil Raja, and Noman Javed. Evolving MIMO multi-layered artificial neural networks using grammatical evolution. In Proceedings of the ACM Symposium on Applied Computing, 2019.
[38] Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro. Automatic generation of neural networks with structured grammatical evolution. In IEEE Congress on Evolutionary Computation, 2017.
[39] Ricardo H. R. Lima, Aurora T. R. Pozo, and Roberto Santana. Automatic Design of Convolutional Neural Networks using Grammatical Evolution. Brazilian Conference on Intelligent Systems, 2019.
[40] Víctor de la Fuente Castillo, Alberto Diaz-Álvarez Miguel- Ángel Manso Manso-Callejo. and Francisco Ser- radilla Garcia. Grammar Guided Genetic Programming for Network Architecture Search and Road Detection on Aerial Orthophotography, Applied Sciences, 2020.
12

---

[41] Xilai Li. Xi Song. and Tianfu Wu. AOGNets: Compositional grammatical architectures for deep learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2019.
[42] Renato Negrinho, Matthew Gormley, Geoffrey J. Gordon, Darshan Patil, Nghia Le, and Daniel Ferreira. Towards modular and programmable architecture search. Advances in Neural Information Processing Systems, 2019.
[43] Hicu Pham, Melody Guan, Barret Zoph, Quoe V. Le, and Jeff Dean. Efficient Neural Architecture Search via Parameters Sharing. In International Conference on Machine Learning, 2018
[44] Esteban Real. Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu. Jie Tan, Quoc V. Lc, and Alexcy Kurakin. Large-Scale Evolution of Image Classifiers. In International Conference on Machine Learning, 2017.
[45] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, Cho-Jui Hsich. DrNAS: Dirichlet Neural Architecture Search. In International Conference on Learning Representations, 2021.
[46] Xuanyi Dong and Yang. Scarching for Robust Neural Architecture in Four GPU Hours. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2019.
[47] Colin White, Willie Neiswanger, and Yash Savani. BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search. In Proceedings of the National Conference on Artificial Intelligence, 2021.
[48] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Oshorne. Interpretable Neural Architecture Search via Bayesian Optimisation with ccisfeiler--ehmar Kernels. In International Conference on Learning Representations, 2021.
[49] Kevin Swersky, David Duvenaud, Jasper Snoek, Frank Hutter, and Michael A. Osborne. Raiders of the Lost Architecture: Kernels for Bayesian Optimization in Conditional Parameter Spaces. In NeurlPS Workshop Bayesian Optimization in Theory and Practice, 2013.
[50] Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. NAS- Bench-101: Towards Reproducible Neural Architecture Search. In International Conference on Machine Learning, 2019.
[51] Lizheng Ma. Jiaxu Cui, and Bo Yang. Deep Neural Architecture Search with Deep Graph Bayesian Optimization. In IEEE/WIC/ACM International Conference Web Intelligence. IEEE Computer Snciety Press, 2019.
[52) Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the Gap between Sample-based and One-shot Neural Architecture Search with BONAS. In Advances Neural Information Processing Systems, 2020.
[53] Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph HyperNetworks for Neural Architecture Scarch. In International Conference on Learning Representations, 2019.
[54] Noam Chomsky. Three models for the description of language. IRE Transactions on information theory, 1956.
[55] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc Le. MnasNet: Platform-Aware Neural Architecture Search for Mobile. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2019.
[56] Stephen C. Kleene et al. Representation of events in nerve nets and finite automata. Automata studies, 1956.
[57] John Warner Backus. The syntax and semantics of the proposed international algebraic language of the zurich acm com-gamm conference. In International Conference on Information Processing. 1959.
[58] Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. In International Conference on Learning Representations, 2020.
[59] Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. NATS- BenchBench: Benchmarking NAS Algorithms for Architecture Topology and Size. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021.
[60] Robert McKay, Nguyen Xuan Hoai, Peter A. Whigham. Yin Shan, and Michael O' neill. Grammar- based genetic programming: survey, Genetic Programming and Evolvable Machines, 2010.
13

---

[61] Henry Moss, David Leslie, Daniel Beck, Javier González, and Paul Rayson. BOSS: Bayesian Optimization over String Spaces. In Advances in Neural Information Processing Systems, 2020.
[62] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-I.chmal Graph Kemness. Journal of Machine Learning Research, 2011.
[63] David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. Kriging is well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems. Springer, 2010.
[64] Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for Activation Functions. arXiv, 2017.
[65] Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural Architecture Search without Training. In International Conference on Machine Learning, 2021.
[66] Mohamed S. Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D. Lane. Zero-Cost Proxies for Lightweight NAS. In International Conference on Learning Representations, 2021.
[67] Xuefei Ning. Changeheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Yu Wang. Evaluating Efficient Performance Estimators of Neural Architectures. Advances in Neural Information Processing Systems, 2021.
[68] Andrej Karpathy. nanoGPT. httppa//ggthubb.mm//aaaaaaattttt hash: eba36e8).
2023. [Online; Commit
[69] Ankit Goyal, Alexey Bochkovskiy, Jia Deng, and Vladien Koltun. Non-deep Networks. Advances in Neural Information Processing Systems, 2022.
[70] Hugo Touvron, Matthieu Cord, Alaacldin El-Nouby, Jakob Verbeck, and Hervé Jégou. Three things everyone should know about Vision Transformers. In Proceedings of the European Conference on Computer Vision, 2022.
[71] William Ogden. A helpful result for proving inherent ambiguity. Mathematical Systems Theory, 1968.
[72] Marcin Andrychowicz. Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances in Neural Information Processing Systems, 2016.
[73] Ke Li and Jitendra Malik. Learning to Optimize. International Conference Learning Representations, 2017.
[74] Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P. Lillicrap. Matt Botvinick, and Nando Freitas. Learning to Learn without Gradient Descent by Gradient Descent. In International Conference on Machine Learning, 2017.
[75] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning Optimize: A Primer and A Benchmark. Journal of Machine Learning Research, 2022.
[76] Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoe Le. Neural Optimizer Search with Reinforcement Learning, In International Conference on Machine Learning, 2017.
[77] Ruochen Wang, Yuanhao Xiong, Minhao Cheng, and Cho-Jui Hsieh. Efficient Non-Parametti Optimizer Search for Diverse Tasks. Advances in Neural Information P Processing Systems, 2022.
[78] Esteban Real, Chen Liang, David So, and Quoe V. Le. AutoML-Zero: Evolving Machine Learning Algorithms From Scratch. In International Conference on Machine Learning, 2020.
[79] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Yao Liu, Kaiyuan Wang, Cho-Jui Hsieh, Yifeng Lu, and Quoe V. Le. Evolved Optimizer for Vision. In First Conference on Automated Machine Learning (late-Breaking Workshop), 2022.
[80] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In International Conference on Learning Representations, 2021.
[81] Alexander L Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow, Differentiable programs with neural libraries. In International Conference on Machine Learning, 2017.
[82] Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong Learning Program Synthesis. Advances in Neural Information Processing Systems, 2018
14

---

[83] Ameesh Shah, Eric Zhan. Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. Learning Differentiable Programs with Admissible Neural Heuristics. Advances in Neural Information Processing Systems, 2020.
[84] Guofeng Cui and He Zhu. Differentiable Synthesis of Program Architectures. In Advances in Neural Information Processing Systems, 2021.
[85] Jie Hu, Li Shen, and Gang Sun. Squeeze-ane and- Exdiititttion Networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2018.
[86] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bileNetV2: Inverted Residuals and Linear Bottlenecks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018.
[87] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of "small-world' networks. Nature, 1998.
[88] Paul Erdös, Alfréd Rényi, et On the evolution random graphs. Publ. Math. Inst. Hung. Acad. Sci, 1960.
[89] Han Xiao, Ziwei Wang, Zheng Zhu, Jic Zhou, and Jiwen Lu. Shapley-NASt Discovering Operation Contribution for Neural Architecture Search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
[90] Eric Brochu, Vlad M. Cora, and Nando De Freitas. A Tutorial on Bayesian Optimization Expensive Cost Functions, with Application to Active User Modeling and Hicrarchical Reinforcement Learning. arXiv, 2010.
[91] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proceedings of the JEEE, 2015.
[92] Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The Application of Bayesian Methods for Seeking the Extremum. Towards Global Optimization, 1978.
[93] Alex Krizhevsky, Geoffrey Hinton, al. Learning Multiple Layers of Features from Tiny Images, 2009.
[94] Patryk Chrabaszc7, Ilya Loshchilov, and Frank Hutter. A Downsampled Variant of ImageNet as an Alternative to the CIFAR Datasets. arXiv, 2017.
[95] Rob Geada, Stephen McGough, Amir A. Abarghouei. Isabelle Guyon, and Sébastien Treguer. CVPR-NAS- cttp:////croooooaatttttss..... https://github. http://bbGeaaa//vp---aeeee datasatsassss 2021.
(codebase for the "CVPR-NAS 2021 Unseen Data Track").
[96] Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization, In International Conference Learning Representations, 2019.
1971 Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009.
[98] Andrej Karpathy. The Unreasonable Effectiveness of Recurrent Neural Networks. github.
http:////eeeeeeeiieeeeeeeeeeee effectivensss/ 2015.
[99] Andrew Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Ng, and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, 2011.
[100) Kaiming Hc, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recog- nition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2016.
[101] Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-NAS: A Zero-Shot NAS for High-Performance Image Recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
[102] Jack Turner, Elliot Crowley, Michael O' O'Boyle, Amos Storkey, and Gavin Gray. BlockSwap: Fisher- guided Block Substitution for Network Compression Budget. International Conference on Learning Representations, 2020.
[103] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking Winning Tickets Before Training by Preserving Gradient Flow. International Conference on Learning Representations, 2020.
15

---

[104] Namhoon Lee. Thalaiyasingam Ajanthan, and Philip HS Torr. SNIP: Single-shot Network Pruning based Connection Sensitivity. International Conference Learning Representations, 2019.
[105] Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems. 2020.
[106] Vasco Lopes, Saeid Alirezazadeh, and Luis Alexandre. EPE-NAS: Efficient Performance Estimation Without Training for Neural Architecture Search. International Conference on Artificial Neural Networks, 2021.
[107] Lennart Schneider, Florian Pfisterer. Martin Binder, and Bernd Bischl. Mutation is all you need. ICML Workshop on Automated Machine Learning, 2021.
[108] Arber Zela, Julien N. Siems, Lucas Zimmer, Jovita Lukasik, Margret Keuper, Frank Hutter. Sur- rogate NAS Benchmarks: Going Beyond the Limited Search Spaces of Tabular NAS Benchmarks. In International Conference on Learning Representations, 2022.
[109] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, 2020.
[110] Zhihang Li, Teng Xi. Jiankang Deng, Gang Zhang, Shengzhao Wen, and Ran He. GP-NAS: Gaussian Process based Neural Architecture Search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2020.
[111] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going Deeper with Convolutions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2015.
[112] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications. Xrviv, 2017.
[113] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet: An Extremely Efficient Convolu- tional Neural Network for Mobile Devices. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018.
[114] Ningning Ma, Xiangyu Zhang, Hai-Tar Zheng, and Jian Sun. ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design. In Proceedings of the European Conference on Computer Vision, 2018.
[115] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive Neural Architecture Search. In Proceedings of the European Conference Computer Vision, 2018
[116] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial Channel Connections for Memory-Efficien Architecture Scarch. In International Conference on Learning Representations, 2020.
[117] Jacob Devlin, Ming- Mei Chang. Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of Conference of the North American Chapter of the Association for Computational Linguistics, 2019.
[118] Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. NAS evaluation is frustratingly hard, Interna- tional Conference on Learning Representations, 2020.
16

---

A Vocabulary for primitive computations and topological operators
Table 3 and Figure 5 describe the primitive computations and topological operators used throughout our experiments, respectively. We defined the order of arguments of the topological operator as follows: we order arguments first by their sink nodes and then by the source node (following Dong and Yang [58]). Note that by adding more primitive computations and/or topological operators we could construct even more expressive search spaces.
Table 3: Primitive computations. "Name" corresponds to the string function symbols in our CFGs and "Function" is the associated implementation of the primitive computation in pseudocode. The subscripts g. k. 8, and p are abbreviations for groups, kernel size, strides, and padding, respectively. During assembly of neural architectures ((w), we replace string function symbols with the associated primitive computation.
Name
Function
avg-pool
AvgPoolkm3.. 3.0.,m11.pmmm (x)
batch
(x)
convix1
Conv==1,==1,p=000
conv3x3
Conv
dconv3x3
Nonv==CA==,;==1===1
down
+ Conv (A7gPo01(=2..==6xx)
hardswish
Hardswish(x)
id
Identitiy(x)
instance
(x)
layer
(x)
mish
Mish (x)
relu
(eLU(x)
Zeros (x)
(a) Sequentialle ial((a, b).
(b) Sequenti a13(a, h,
(c) Sequential4(a, c,
d
(d) Residual2(a, b, c).
(e) Residual3((, c, d).
( Cell(a. e.
a
a
b
d
b
d
(g) Diamond2(a, b, c, d).
(h) Diamond3(a, b, c, d, e. f).
Figure 5: Topological operators. Each subfigure makes the connection between the topogolocial operator and associated computational graph explicit, i.e., the arguments of the topological operators (a, b, ...) are mapped to the respective edges of the corresponding the computational graph.
B Extended related work
Complementary to Section 2, we provide comparison of our proposed search space design to others from the literature Table Our search space design framework allows us to search over all aspects of the architecture and incorporate user-defined constraints well as foster regularity.
17

---

Table 4: Comparison of search space designs.
Search over/from
Design approach
Example
Micro structure
Macro structure
Primutives
Constraints
Regularity
Global
Kandasamy et al. (18)
Hyperarameter-an
Tan and [I]
Chain-structured
Roberts et al. [19]
Cell-based
Zoph al. [23)
D-level hierarchical assembly
Liu
41
Graph generator hicrarchy
Ru et al [8]
CuDeepNEAT
Miikkulainen [11]
Formal systems
Negriaho al. [42]
Enhanced CFGs
Ours
1 search only linear confined macro topologies; "requires post-hoc validation scheme; "do not share architectural patterns hierarchically
While our work focuses exclusively on NAS, we will discuss below how it relates to the areas of optimizer search (as well automated machine learning from scratch), and neural-symbolic programming.
Optimizer search is closely related field to NAS, where we automatically search for optimizer (i.e., an update function for the weights) instead of an architecture. Initial works used learnable parametric non-pann parameetiiiic optimizers. While the former approaches [72-75] have poor scalability and generality, the latter works overcome those limitations. More specifically, Bello et al. [76] searched for instantiation of crafted patterns via reinforcement learning, while Wang et al. [77] proposed a tree-structured search space' and searched for optimizers via a modified Monte Carlo sampling approach. AutoML-Za -Zero [78] took entire machine learning algorithms, including optimizers, from a generic search space built from basic mathematical operations with an evolutionary algorithm. Chen al. [79] used RE to search for optimizers from a generic search space (inspired by AutoML-Zero) for the training of vision transformers [80].
more general approach by searching
Complementary to the above, there is also recent interest in automatically synthesizing programs from domain-specne sppciffc languages. Gaunt et al. [81] proposed hand-crafted program template and simultancously optimized the parameters of the differentiable program with gradient descent. Valkov al. [82] proposed a type-directed (top-down) enumeration and evolution approaches over differentiable functional programs. Shah et al. [83] hierarchically assembled differentiable programs and used neural networks for the approximation of missing expression in partial programs. Cui and Zhu [84] treated CFGs stochastically with trainable production rule sampling weights, which were optimized with gradient descent [6]. However, naively (directly) applying gradient-based approaches (without any novel adaption) does not scale to hierarchical search spaces due to the exponential explosion of supernet weights, but still renders interesting direction for future work.
Compared to these lines of work, we enhance CFGs to handle changes in spatial resolution, explicitly promote regularity in the search space design, and (compared to most of them) incorporate constraints. Note that the latter two could also be applied in those domains. We also proposed a BO search strategy to search efficiently with tailored kernel design handle the hierarchical nature of the architectural search space.
C Details on extended Backus-Naur form
The (extended) Backus-Naur form [57] is a meta-language to describe the syntax of CFGs. We use meta-rules of the form S ::= where S E N is a nonterminal and a e (N U E)* is string of nonterminals and/or terminals. We denote nonterminals in UPPER CASE, terminals corresponding to topological operators in Initial upper case/teletype, and terminals corre- sponding to primitive computations lower case/teletype, e.g.. S ::= Residual(S, id, S). To compactly express production rules with the same left-hand side nonterminal, use the
Note that the tree- structured search space can equivalently be described with CFG (with a constraint on the number of maximum depth of the syntax trees).
18

---

DI
D1
(a) Computational graph representation of current derivation in Equation 8.
D
D
D
C
CL
(b) Computational graph representation of current derivation in Equation 9.
CL
down
&t
down down
down
CL
CL
CL
CL
CL
CL down
O CL CL CL CL down CL
CL
CL
CL
CL
down
(c) Computational graph representation of current derivation in Equation 10.
Figure 6: Comprehensive example for the construction of the macro topology in the hierarchical NAS-Bench-200 search space. We visualize the computational graphs of the derivation steps from Equations 8 to 10. Note that CLs (representing spatial resolution preserving cells) do not change the spatial resolution and the primitive computation down downsamples the features by factor of two. Our proposed mechanism to overload the nonterminals (Section 3.3) effectively distributes the downsampling operations across the macro topology so that all incoming features each node will have the same spatial resolution.
vertical bar to indicate a choice of production rules with the same left-hand side, e.g., ::= Sequential(S. S, S) Residual(S, id, S) conv.
D Comprehensive example for the construction of the macro topology
Consider the following derivation of the macro topology of an architecture in the hierarchical NAS-Bench-201 (see Section 4 for the search space definition):
D2 + S3(D1, D1, DO)
(8)
S3(R3(C, C, D, D), R3(C, C, D, D), S3(C, C, CL))
(9)
(22, CT.), C2 CL, CL), S2(CL, down), R2(CT., down, down)), R3(,2(CL, CL, CL), S2(CL, CL), R2(CL, down, down), R2(CL, down, down)
(10)
S3(S2(CL, CL), R2 CL, CL), CL)
where abbreviate Sequential ill and Residual with S or R for sake of brevity. Figure 6 visualizes the corresponding computational graphs at each step and shows how our proposed mechanism of overloading nonterminals (Section 3.3) effectively distributes downsampling operations (down) across the macro topology of an architecture so that incoming features at each node will have the same spatial resolution.
E
Comprehensive example for the implementation of constraints
In the design of a search space, one often wants to adhere to one or more constraints. For example, one wants have exactly two incident edges per node [6] or wants ensure that every architecture in the search space is valid, i.e., there needs to exist at least one path from the input to the output. CFGs (by design) cannot handle such constraints since it requires comtext-sensitivvlyy Thus, we extend CFGs with a n-step lookahead to guarantee compliance with the constraints. The n-step lookahead considers all n-step scenarios (e.g., possible n-step derivations) and filters out all scenarios that would result in violation with at least one constraint. In practice, leverage the recursive
19

---

nature of CFGs and find that one-step lookaheads are sufficient for the constraints considered in our work. the following, we consider how the lookahead effectively ensures compliance for an exemplary constraint.
We consider the constraint "the input is associated with the output". To guarantee this constraint, it is sufficient to ensure that for each topological operator during sampling (or evolution) there is at least one path from the input the output (due to the recursive nature of CFGs). To this end, lest whether the removal of an edge would result in a disassociation of the input from the output of the computational graph the current topological operator (no path from input to output) with an one-step lookahead. More specifically, consider the following topological operator Cell(a, b, c, d.e, f):
and the primitive computations zero and non-zero, where the former disassociates two nodes, i.e., removes their edge. The topological operator Cell has the following four paths from the input (1) to output (4): 1-2-3-4, 1-2-4, 1-3-4, and 1-4. Note that to not violate the constraint at least one of these paths needs to exist after sampling (or evolution). Below, describe potential sampling of primitive computations for the topological operator:
Substitute a with non-zero: valid since non-zero does not disassociate the input from the output.
2. Substitute b with zero: valid since the paths 1-2-3-4, 1-2-4, and 1-4 are still possible. Remove 1-3-4 from the paths.
3. Substitute e with
valid since the paths 1-2-4 and 1-4 are still possible. Remove 1-2-3-4 from the paths.
4. Substitute d with zero: valid since the path 1-2-4 still possible. Remove 1-4 from the paths.
5. Substitute with
zero: invalid since it would remove the last remaining possible path 1-2-4.
non-zero: valid since non-zero does not disassociate the input from the output.
6. Substitute with zero: valid since the path 1-2-4 is still possible. Note that we also could substitute with non-zero but this operation would be pruned away since the node 3 is not connected to the input.
Consequently, the sampling generates the following computational graph that adheres to the constraint:
non - zero
2
4
non-zero
Note that this procedure only samples architectures which comply with the constraint. Further, note that all architectures will be valid, i.e., there are no spatial resolution or channel mismatches due our enhancements of CFGs (Section 3.3). We can similarly implement this procedure for evolution as well as for other constraints.
Common search spaces from the literature
In Section 4, we demonstrated how to construct the hierarchical VAS-Bench-200 search space, that subsumes the cell-based
search space [58], with our search space design framework. Below, we first provide a best practice guide to design search spaces and then show how to also define the following popular search spaces from the literature: TAS-Bench-1ee 101 search space [50], DARTS
20

---

c_ (k-1)
[k-2)
Node3
Node4
Node5
Node6
c_1
Figure 7: Visualization of the Darts topological operator.
search space [6]. Auto- Laee-DeeLLab search space [2]. hierarchical cell search space [9], Mobile-net search space [55], and hierarchical random graph generator search space [8]. For more details on the search spaces, please refer to the respective works.
Best practice to construct search space with context-free grammars
We first note that the design largely depends on the target task. That is, an image-based task may require different design than text-based task. In general, when looking for high-performing architectures for given task, we recommend reviewing the relevant literature and consulting domain experts if one is not particularly familiar with the application domain. In particular, distilling commonalities and differences among architectures that form the basis of the design for the CFG. Starting from this basis, we recommend expanding the search space by adding more and more production rules to the CFG to allow for the exploration of interesting novel architectures. This procedure ensures search efficiently find well- performing architectures by exploiting prior knowledge in the search space design. We leave the integration of prior knowledge into BOHNAS for future work. If computational resources are virtually unlimited, one could also search for for architectures from scratch, similar to the AutoML-Zero [78].
recommend
NAS-Bench-101 search space
The NAS-Bench-10h search space [50] consists fixed macro architecture and searchable cell, ie.. directed acyclic graph with maximally 7 nodes and 9 edges. We adopted the API of NAS- Bench- 101 our search space design and, thus, we can define the NAS-Bench- search space as follows
NB101 :: ModelSpec OPS)
MATRIX Matrix BINARY, BINARY
(II)
BINARY
OPS List(OP, OP, OP, OP, OP) OP : conv_1xt conv_3x3 max_pool
and add constraint ensure that BINARY - 1 9.
DARTS search space
The DARTS search space [6] consists of a fixed macro architecture and a cell, i.e., a seven node directed acyclic graph (Darts; see Figure for the topological operator). We omit the fixed maero architecture from our search space design for simplicity. Each cell receives the feature maps from the two preceding cells as input and outputs a single feature map. Fach intermediate node (i.e., Node3, Node4, Node5, and Node6) is computed based on two of its predecessors. Thus, define the
21

---

DARTS search space as follows:
DARTS : DNrta(NODE3, NODEI, NODE5, NODE6)
NODE3 Node3(OP, OP)
NODE4 = OO,, OP, OP)
NODE5 :: NOP OP, OP, OP)
(12)
NODE6 =: (OP OP, OP, OP, OP)
OP = sep_conv_3x2 sep_conv_bxx dil_conv___e dil_coov__aa
max_pool avg-pool id zero
where the topological operator Node3 receives two inputs, applies the operations separately on them, and sums them up. Similarly, Node4, Node5, and Node6 apply their operations separately to the given inputs and sum them up. The topological operator Darts feeds the corresponding feature maps into each of those topological operators and finally concatenates all intermediate feature maps. Since the final discrete architecture each intermediate node only receives two non-zero inputs, we need to add constraint to ensure that each intermediate node only has two incident edges. More specifically, we enforce that for each intermediate node only two OP primitive computations are non-zero and the others are zero. For example, one of the primitive computations of the topological operator Node4 is enforced to be zero.
To avoid adding an explicit constraint, we can utilize that the topological operators can be an arbitrary (Python) function (with an associated computational graph which is only required for search strategies using the graph information in their performance modeling). Thus, we can equivalently express the DARTS search space as follows:
DARTS GENOTYPE(OP, IN1, OP, IN1, OP, IN2, OP, IN2, OP, IN3, OP, IN3, OP, IN4, OP, IN4) OP sep_ 3x3 sep_conv_5al dil__onv_3x3 dil_conv__i
max_pont pax_pool avg_pool id
IN1 := 0
IN2 ==
2
IN3 ==
IN4
(13)
where GENOTYPE resembles the Python object (namedtuple), which can plugged (almost) directly into standard DARTS implementations.
Auto-Deepl.an search space
Auto-DeepLab [2] combines a cell-level with a network-level search space to search for segmentation networks, where the cell is shared across the searched macro architecture, i.c., twelve step (linear) path across different spatial resolutional levels. The cell-level design is similar to the one of Liu et al. [6] and, thus, we can use a similar search space design in Equation 12. For the network-level, we introduce constraint that ensures that the path is of length twelve, i.e., we ensure exactly twelve derivations in our CFG at the network-level. Further, we overload the nonterminals so that they correspond to the respective spatial resolutional level, e.g., D4 indicates that the original input is downsampled by a factor of four (see Section 3.3 for details). For the sake of simplicity, we omit the first two layers and atrous spatial pyramid poolings they are fixed, and hence define the network- search space as follows:
D4 := Same SameLCELL, D4)
Down(CELL, D8)
D8 == Up(CELL, D4)
Same(CELL, D8) DouL( D16)
(14)
D16 == Up(CELL, D8)
Same D16) Dosn(CELL, D32)
D32 Up(CELL, D16) Same Same(CELL, D32)
where the topological operators Up. Same, and Down upsample/halve, do not change/do not change, or downsample/double the spatial resolution/chamnels, respectively. The intermediate variable CELL maps to the shared cell.
Hierarchical cell search space
The hierarchical cell search space [9] consists of a fixed (linear) maero architecture and a hierarchically assembled cell with three levels which is shared across the macro architecture. Thus, can omit
22

---

the fixed macro architecture from our search space design for simplicity. The first, second, and third hierarchical levels correspond to the primitive computations (i.e.. id, max_pool, avg-pool. sep_comy depth_ conv, conv, zero), six densely connected four node directed acyclic graphs (DAG4), and densely connected five node directed acyelic graph (DAG5), respectively. The zero operation could lead to directed acyclic graphs which have fewer nodes. Therefore, we introduce a constraint enforcing that there are always four (level 2) or five (level 3) nodes for every directed acyclic graph. More specifically, outgoing edge. Alternatively, we could write out all all variants explicitly. Further, since a densely connected five node directed acyclic graph graph can have (at most) ten edges, need to introduce the intermediate variables (i.e., M1, M6) to enforce that only six (possibly) different four node directed acyclic graphs are used. Consequently, define CFG for the third hierarchical level
only need to ensure each node has least incident and
LEVEL3 = DAG5 LEVVLL2 LEVEL2)
(15)
LEVEL2
M1
M2
M3
X4
M5
M6
zero
where we substitute the intermediate variables M1, .. M6 with the six lower-level motifs constructed by the first and second hierarchical level
LEVEL2 :: (LEVEL, LEVELI)
(16)
LEVEL1 = id max_pool avg_pool sep_conv depphh_covv
conv
zero
Mobile-net search space
Factorized hierarchical search spaces, e.g.. the Mobile-net search space [55], factorize a (fixed) macro architecture often based on an already well-performing reference architecture into separate blocks (e.g.. cells). For the sake of simplicity, we assume a three sequential blocks (Block) reference architecture (Sequenti al). In each of those blocks, we search for the convolution operations (CONV), kernel sizes (KSIZE), squeeze-and-exciee and-excitation ratio (SERATIO) [85], skip connections (SKIP), number of output channels (FSIZE), and number of layers per block (ALERRS), where the latter two are discretized using the reference architecture, Consequently, we can express this search space as follows:
MACRO (COVEBCC CONVBLOCK, CONVBLLOCK)
CONVBLOCK Block(CONV, KSIZE, SERATIO, SKIP, FSIZE, #LAYERS)
CONV :: conv dconv mbconv
KSIZE ::= 3 5
(17)
SERATIO :: 0 0.25
SKIP pooling id_residual no_skip
FSIZE 0.75 1.0 1.25
#LAYERS 0
where conv, donv and mbconv correspond to convolution, depthwise convolution, and mobile inverted bottleneck convolution [86]. respectively.
Hierarchical random graph generator search space
The hierarchical random graph generator search space [8] consists of three hierarchical levels of random graph generators (i.e., Watts StrtosSttr [87] and Erdös Réngi [88]). We denote with Watts-Strogatz.3 the random graph generated by the Watts-Strogatt model with nodes. Thus,
23

---

we can represent the search space as follows:
TOP
Watts-Strogatz_3(KK Pt)(MII, MID, MID)
Watts-Strogatz_ (t) MID)
MID =
Brdbs-Reeny__1(en((BTT
Erdōs-Rényi_10(Pm) (BOT. BOT
(18)
x10
BOT ==
Watts-Strogatz__3[1 (NODE, NODE, NODE)
Natts--ttrogazz_10KK (b)DE NODE
K 2 3
where each terminal Pt, Pm, and Pb map to continuous number in [0.1, 0.9]² and the placeholder variable NODE maps to primitive computation, e.g., separable convolution. Note that we omit other hyperparameters, such stage ratio, channel ratio etc., for simplicity.
Computation of search space and supernet size G
In this section, we show how efficiently compute the size of search spaces and the size of (hypothetical) supernet.
Search space size There are two cases to consider: (i) a CFG contains cycles (i.e., part of the derivation be repeated infinitely many times), yielding open-ended, infinite search space; and (ii) a CFG contains no cycles, yielding in a finite search space whose size we can compute.
Consider production A + Residual(B, B, B) where Residual is a terminal, and A and are nonterminals with - conv | id. Consequently, there are 2 = 8 possible in- stances of the residual block. If we add another production rule for the nonterminal A, e.g., + Sequential(B, B, B), we would have 2 + 2 = 16 possible instances. Further, adding a production rule C Sequential(A, A, A) would yield search space size of (23 + 2 = 4096.
More generally, we introduce the function PA that returns the set of productions for nonterminal A E N, and the function μ P -> N that returns all the nonterminals for production p E P. We can then recursively, starting from the start symbol A E N, compute the size of the search space as follows:
('' II f(A') PEPA NEM(P)
(u() 0, otherwise
S(A) = Σ
(19)
When a CFG contains some constraint, we ensure only account for valid architectures (i.e., compliant with the constraints) by ignoring productions which would lead to invalid architectures.
Supernet size Stochastic supernets are a key component of recently popular fast search strategies, e.g., gradient-based methods. A supernet is composed of all possible architectures of search space. We outline how one could naïvely adopt these gradient-basse methods to hierarchical search spaces and discuss why these supernets (without any novel adaption) do not scale to large hierarchical search spaces.
DARTS [6] and its variants (e.g., Chen et al. [45], Dong and Yang [58], Xiao et al. [89]) relax the categorical (discrete) choice of primitive computations O, e.g., o(5.) (x) Σ m())((x), where
AEO
ml-) is mixing function, e.g., DARTS uses the softmax over all possible primitive computations exp(a (t.2))
m(x)= Eneo exp(o G215: and o(-) is primitive computation, e.g., convolution.
'While CFGs do not support continuous production choices, we extend the notion of substitution by substituting string representation of Python (float) variable for the intermediate variables Pt, Pm, and Pb.

---

For hierarchical search spaces, we could extend DARTS by also relaxing the categorical choices of the topological operators & Ti (e.g., Liu et al. [2], i.e. 1 (6.2) (x) Σ ET
m(())((2)) with, e.g.,
explat) )
mi(a (x) Enjery " where indicates the hierarchical level, i, denote the edge = (i,j) of
the topological operator ft. and Ti = O..oo Note that this corresponds to stochastic treatment of CFGs with learnable sampling probabilities at, for their productions. Further, note that we (implicitly) assume independence of the current derivation step from the previous ones, even though it actually is conditionally dependent on the previous derivation steps.
O.
To search with gradient descent, we need to create a supernet that contains all (exponentially many) discrete architectures. To this end, we define densely connected n-node directed acyclic graphs G1 that entails all possible topological operators at each hierarchical level / E [I, LJ, in which each topological operator 4 E Ti can be identified by the indication vector 2t, E {0, 1)m(m-1)/2 where nnn 1)/2 = EG is the number of edges. Consequently, we can recursively compute the number of possible architectures represented by the supernet as follows
s(1) : -{
{Ca,
CG.
,1=1 1,
II eE(L....|Ea.II
g(l - , otherwise
(20)
where G1 corresponds directed acyelic graph for the cell-level search space of size Ca e.g., 10 for the DARTS cell. We can similarly compute the number of searchable cells follows
|EGa
1= 2,
g'(1) eE Ea,I)
-1(1-1)
otherwise
(21)
Consequently, the supernet is of size of (L) Sc, where Sc, is the size of a searchable cell. is apparent that the supernet size scales linearly in the number of cells g gL)., which, however, scales exponentially the number of hierarchical levels. This makes the application of methods using supernets, e.g., gradient-based ones, (generally) challenging in hierarchical search spaces with many hierarchical levels.
H
More details on the proposed search strategy
In this section, provide more details and comprehensive examples for search strategy Bayesian Optimization for Hierarchical Neural Architecture Search (BOHNAS) presented in Section 5.
H.1 Bayesian Optimization
Bayesian Optimization (BO) is powerful family of search techniques for finding the global optimum of black-box objective problem. It is particularly suited when the objective expensive to evaluate and, thus, sample efficiency is highly important [90].
To minimize a black-box objective problem with BO, we first need to build a probabilistic surrogate to model the objective based on the observed data so far. Based on the surrogate model, we design an acquisition function to evaluate the utility of potential candidate points by trading off exploitation (where the posterior mean of the surrogate model is low) and exploration (where the posterior variance of the surrogate model is high). The next candidate points to evaluate is then selected by maximizing the acquisition function [91]. The general procedure of BO is summarized in Algorithm 1.
We used the widely used acquisition function, expected improvement (EI) [92], our BO strategy. EI evaluates the expected amount of improvement of a candidate point x over the minimal value f' observed so far. Specifically, denote the improvement function as [(x) max(0, f f(x)), the EI acquisition function has the form
(xI()((.) = E[((x) [.) = 1'd (f- ( df
(f' - g)
25

---

Algorithm Bayesian Optimization algorithm [90].
Input:
Initial observed data D,, black-box objective function f. total number of BO iterations T The best recommendation about the global optimizer x"
Output:
fort= .,..... do
Select the next X by maximizing acquisition function (x([D;)
Evaluate the objective function at f 1xx+11)
Dr+1 < Dr U (x++1, ft+1)
Update the surrogate model with Dz+1
end for
Algorithm 2 Kriging Believer algorithm to select one batch of points.
Input: Observation data Dr, batch size
Output: The batch points B,+1 (x D. D.U.D
(1)
1411
for : do
( Select the next Xi+1 by maximizing acquisition function (x)
Compute the predictive posterior mean p(x(4) (D:)
D. < De U (x+41, (xx41, (D))) (D)))
end for
where (x) and o² (x are the mean and variance of the predictive posterior distribution at a candidate point and (6-) and (.) denote the PDF and CDF of the standard normal distribution, respectively.
To make use of ample distributed computing resource, we adopted Kriging Believer [63] which uses the predictive posterior of the surrogate model to assign hallucinated function values {Sp)pe pe P} to the /' candidate points with pending evaluations {pp .... P) and perform next BO recommen- dation in the batch by pseudo-augmenting the observation data with DD {(xp> pE(), P}+ namely D.- = D, D. The algorithm of Kriging Believer at one BO iteration to select a batch of recommended candidate points is summarized in Algorithm
H.2 Hierarchical Weisfeiler-Lehmal kernel
Inspired by Ru et al. [48], we adopted the Weisfeiler-Lehmar (WL) graph kernel [62] in the GP surrogate model to handle the graph nature of neural architectures. The basic idea of the WL kernel is to first compare node labels, and then iteratively aggregate labels of neighboring nodes, compress label and compare them. Algorithm summarizes the WL kernel procedure.
them into
al. [48] identified three reasons for using the WL. kernel: (1) able to compare labeled and directed graphs of different sizes, (2) it is expressive, and (3) it is relatively efficient and scalable. Hicrarchical search spaces can express a diverse spectrum neural architectures with very heterogencous topological structure. Therefore, reason (1) is very important property of the WL kernel to account for the diversity of neural architectures and makes other kernels (e.g., adjacency [50] or path encoding [47]) not applicable. Moreover, if we allow for many hierarchical levels, can construct very large neural architectures. Therefore, reasons (2) and (3) are essential for accurate and fast modeling.
However, modeling solely based on the (standard) WL graph kernel neglects the useful hierarchical information from our construction process. Moreover, the large size of neural architectures makes still challenging to capture the more global topological patterns. We therefore propose to use hierarchical information through hicrarchy of WL graph kernels that take into account the different granularities of the architectures and combine them in a weighted sum. To obtain the different granularities, use the fold operators F; that removes parts beyond the 1-th hierarchical level. Thereby, we obtain the folds
Fs(w) = Sequential (Brreintiialliiiuuuulallaaaaaaaa (Besidual id, conv), Residual (conv, id, conv), linear), F2(w) = Sequent (Residdaal,, Residual, linear). Fi(w)) = Sequential
26

---

Algorithm 3 Weisfeiler-Lchman subtree kernel computation [62].
Input: Graphs G1, G2, maximum iterations H Output: Kernel function value between the graphs
Initialize the feature vectors ((G1) @u(G1), ((G:) = @G2) with the respective counts of original node labels (i.e., the h = 0 WL features) for h ..... do
Assign multiset Mr (v) f (u)lu E (N()) to each node v E G, where 4-11 is the node label function of the h 1-th WL. iteration and N is the node neighbor function
Sort elements in multiset M, (v) and concatenate them to string Sn (v)
Compress each string sn (v) using the hash function f s.t. f(s((v) f(sn(w)) + sh(v) (n)
Add 1-1 as prefix for (v)
Concatenate the WL features on (G1). (G2) with the counts of the new labels: ((G1)
( ((G2 (o(G2). on (G2)]
Set (v) = (c) Ve E G
end for
Compute inner product k (dn(Gi), (n between WI. features th (G1), db (G2) in RKHS H
id
id
conv
conv
conv
conv
linear
(a) Pa(w) (Rquential(eesiduual) (conv, id, conv), Residual(conv, id, conv), linear).
Residual
Residual
linear
(b) Fa (w)
Sequential Sequential (Residual, Residual, linear).
Figure 8: Labeled computational graphs (F22 and ((Fs) of the folds F3 and F3, respectively.
for the string w from Equation 1. Figure 8 visualizes the labeled computational graphs o ((F2) and (FF) of the folds F2 or F3. respectively, Note that we ignore the first fold since it does not represent a labeled DAG. Also, note that we additionally add the previous nonterminals to provide additional information about the construction history. These graphs can be fed into (standard) WL graph kernels. Therefore, we can construct a hierarchy of WL graph kernels KW as follows:
kawI(wn, = Σ N k ((F(ww))) 1=2
(22)
where wy and W/ are two strings. Note that A governs the importance of the learned graph information across the hicrarchical levels and can be optimized through the marginal likelihood. Note that while the hicrarchical kernel structure seems superfluous for this example, for search spaces with many hierarchical levels it greatly improves the ability of the kernel to capture the more topological patterns (Section 6).
H.3 Examples for the evolutionary operations
For the evolutionary operations, we adopted ideas from grammar-based genetic programming [60, 61]. In the following, we will show how these evolutionary operations manipulate the function composition of architecture, e.g..
Sequential al (Residual id, conv), Residual(conv, id, conv), linear) from the scarch space
(23)
S Sequential(S, S, S) Residual(S, S, S) conv id
linear
(24)
Figure shows how we can derive the function composition in Equation 23 from the search space in Equation 24, For mutation operations, we first randomly piek a substring (i.e., part of the composition), c.g., (esiduallcoon, id, conv). Then, we randomly sample function composition with the
27

---

same nonterminal symbol S as start symbol, e.g., Sequential(cony, id, linear), and replace the previous substring, yielding
SequentiallSqquuriiaaaaac..
id, linear), Residual(conv, id, conv), linear)
(25)
For (sross-err we swap the two substrings, e.g., Residual (conv, id, conv) and Residual(conv, id, conv) with the same nonterminal S as start symbol, yielding
id, conv), Residual(conv, id, conv), linear)
(26)
Note that unlike the commonly used crossover operation, which uses two parents, self-crossover has only one parent. Future works could also consider self-copy operation that copies a part of
the function composition to another part of the (total) function composition of an architecture to explicitly regularizing diversity.
I Implementation details of the search strategies and dataset details
BOHNAS, NASBOWL, and NASBOT We used the same hyperparameters for the three BO strategies. We ran the BO approaches asynchronously in parallel throughout our experiments with a batch size of B 1, i.e., at each BO iteration single architecture is proposed for evaluation. We used 10 or 50 random samples to initialize the BO strategies for the architecture (hierarchical NAS-Bench- 201, DARTS, transformer) or activation function search spaces. respectively. For the acquisition function optimization, we used pool size of P 200, where the initial population consisted of the current ten pers-rerformng architectures and the remainder were randomly sampled architectures to encourage exploration in the huge search spaces. During evolution, the mutation probability was set to Pmout = 0.5 and crossover probability was set to Peross = 0.5. From the crossovers, half of them were self-crossovers of one parent and the other half were common crossovers between two parents. The tournament selection probability was set to Ptour 0.2. We evolved the population at least for ten iterations and maximum of 50 iterations using early stopping criterion based on the fitness value improvements over the last five iterations.
Regularized Evolution (RE) and AREA RE [9, 12] and AREA [65] iteratively mutate the best architectures out of a sample of the population. We reduced the population size from 50 to 30 to account for fewer evaluations in the architecture search experiments, and used a sample size of 10. For AREA, we randomly sampled 60 candidates and selected the initial population (30) based on its zero-cost proxy score (nwot). We also ran RE and AREA asynchronously for better comparability.
J Searching the hierarchical NAS-Bench-201 search space
In this section, we provide training and dataset details (Appendix J.1), provide search space def- initions of variants of the hierarchical CAS-Bench-201 search space (Appendix J.2) and provide supplementary results Section 6 and conduct extensive analyses (Appendix J.3).
J.1 Training details
Training protocol We evaluated all search strategies on CIFAR- [93]. ImageNet- 16- 12- [94), CIFARTile, and AddNIST [95]. Note that CIFARTile and AddNIST are novel datasets and therefore have not yet been optimized by the research community. We provide further dataset details below. For training of architectures on CIFAR-IO/II
and ImageNet-16-122 120, we followed the training protocol of Dong and Yang [58]. We trained architectures with SGD with learning rate of 0.1, Nesterov momentum of 0.9, weight decay of 0.0005 with cosine annealing [96], and batch size of 256 for 200 epochs. The initial channels were set to 16. For both CIFAR-I0 and CIFAR-100, we used random flip with probability 0.5 followed by random crop (32x32 with pixel padding) and normalization. For ImageNet- 6-200, used 16x 16 random crop with 2 pixel padding instead.
For training of architectures on AddNIST and CIFARTile, we followed the training protocol from the CVPR-NAS 2021 competition [95]: We trained architectures with SGD with learning rate of 0.01, momentum of 0.9, and weight decay of 0.0003 with cosine annealing, and batch size of 64 for 64 epochs. We set the initial channels to 16 and did not apply any further data augmentation.
28

---

Table Licenses for the datasets we used in our experiments.
Dataset
License
URL
CIFAR-I0 [93]
MIT
html
CIFAR-100 [93]
MIT torp:://aww.cc..ooottoooooo
html
ImageNeet16-- 12-120 [94]
MIT
CIFARTile [95]
GNU http:///gghhin.cooo///ooaaaroaee
AddNIST [95]
GNU
ImageNet [97]
Custom
Tiny Shakespeare [98]
MIT
https://github. hwwpp///.o....aapaa////aaaaaaaaa
IMDb [99]
Custom
https://ai. edwe htt.:///w......mmmmaaa//aaaaa/aa
Dataset details In Table 5, provide the licenses for the datasets used in experiments. For training of architectures on CIFAR-10, CIFAR-100 100 [93], and ImageNet-16- 1--10 [94], we followed the dataset splits and training protocol of NAS-Bench-200 [58]. For CIFAR-IO, we split the original training set into a new training set with 25k images and validation set with 25k images for search following [58]. The test set remained unchanged. For evaluation, trained architectures training and validation set. For CIFAR- 100, the training set remained unchanged, but the test set was partitioned in a validation set and new test set each with 5K images. For ImageNet- 16- 120, all splits remained unchanged. For AddNIST and CIFARTile, we used the training, validation, and test splits as defined the CVPR-NAS 2021 competition [95].
both the
J.2 Derivatives of the hierarchical NAS-Bench-208 search space
We derive several derivatives of the hierarchical AAS-Bench-201 search space (Section 4). This derivative let study the impact of different parts of the architecture (c.g.. branching of the macro architecture or repetition of the same architectural blocks) in Section 6. Below, we provide their formal definitions.
Derivative: fixed+shared (cell-based)
This derivative uses fixed macro topology with a single, shared cell. Formally, we first define the fixed macro search space:
D2 Sequentia13(D1, D1, DO)
= Sequentiaa3(C, C, D)
DO : Sequentia13(C, C, SHARED)
(27)
D :== Soquantial2(SHARRD, down)
Sequential2(SHAARD. SHARED)
where the intermediate variable SHARED shares the cell across the fixed macro architecture and maps to a single instance of the cell-level space:
CL. ::= CeP, OP, OP, OP, OP, OP)
OP : zero | id CONVBLOCK avg_pool
CONVBLOCK Sequentia13AACI, CONV, NORM) ACT relu
(28)
CONV convix1
conv3x3
NORM ::= batch
Note that the cell-level space equivalent to the original NAS-Bench-20 search space [58], and since the macro level search space is fixed to the same macro architecture used in the original NAS- Bench-201 search space, this derivative consequently equivalent to the original NAS-Bench-200 search space.
29

---

Derivative: biorarchical+sharedd
For this derivative, we searched over the macro search space but limited the cell-Ievel part to a single instance (a shared cell). Formally, we define macro-level of this derivative as follows:
D2 = Sequentia13(D1, DI, DO) Sequent:ia13(DO, D1, D1) Sequentia14(D1, DI, DO, DO)
D1 = Sequential3(C, C, D) Sequential4(C, C, C, D) Residual3(C, C, D, D)
DO = Sequentia13(C, C, SHARED) Sequentia14(C, C, C, SHARED)
Residual3(C, C, SHARED, SHARED)
D Sequentiaa12(SHAAREDD down) Sequential3(SHARRED, SHARED, down]
Residual22(SHHARRD, down, down)
C Sequentiaa2/SHHARRDD, SHARED) Sequential3(SHARED, SHARED, SHARED)
Residbal12/SHARRDD SHARED, SHARED)
(29)
where the intermediate variable SHARED shares the cell across the macro architecture and maps to a single instance of the cell-level space:
CL Ce1 OP, OP, OP, OP, OP)
OP
id CONVBLOCK avg-pool
CONVBLOCK Sequentia13(ACI, CONV, NORM)
(30)
ACT :: relu hardawish mish
CONV ::= convix1 conv3x3 dconv3x3
NORM batch instance layer
Derivative:
For this derivative, we replaced some of the linear macro topologies (Sequential) with non-linear topologies (Di (miamond); Figure 5 for the topological operator Diamond. This results in architectures with more branching at the macro-level. Formally, we define this derivative as follows:
D2 Sequentia13(D1, D1, D0) Sequential3(D0, D1, D1) Sequential4(D1, D1, DO, DO)
DI := Sequential3(C, C, D) Residnal3(C, C, D, D)
Diamond3(C, C, C, C, D, D)
DO Sequential3(C, C, CT.) Residua13(C, C, CL, CL)
Diamond3(C, C, C, C, CL, CL)
SeQ down)
Res down, down)
Diamend2(CL, CL, down, down)
== (CQ CL) Residua12(CL, CL, CL)
Diamond2(CL, CL, CL, CL)
CL : Cell(OP, OP, OP, OP, OP, OP)
zero id CONVBLOCK avg_pool CONVBLOCK Sequentia13(ACT, CONV, NORM)
ACT == relu hardswish mish
CONV convix1 conv3x3 dconv3x3
NORM = batch instance layer
(31)
Derivative: hierarchhica--ghareehtoo---
For this derivative, we replaced some of the línear macro topologies (Sequential) with non-linear macro topologies (Diamond). This results in architectures with more branching at the macro-level. Different to the derivative iierarchicaltnon.
used single, shared cell. Formally,
30

---

define this derivative as follows:
D2 : Sequentia13(DI, D1, DO) Sequent:aa3(DO, D1, DI) Sequentia14(D1, D1, DO, DO)
D1 == Sequentia13(C, C, D) Residual3(C, C, D, D) Diamond3(C, C, C, C, D, D)
DO == Sequentia13(C, C, SHARED) Residual3(C, C, SHARED, SHARED)
Diamond3(C, C, C, C, SHARED, SHARED)
D == Sequential2(SHARRDD down) ResiduaJ2(SHARED down, down)
Diamond2(SHARRED, SHARED, down, down)
C Sequent:a11((SIAARRD, SHARED) Residua12(SHHARED, SHARED, SHARED)
Diamond((SHARED, SHARED, SHARED, SHARED)
(32)
where the intermediate variable SHARED shares the cell across the macro architecture and maps to a single instance of the cell-level space:
CL Ce11(OP, OP, OP, OP, OP, OP)
OP : zero id CONVBLOCK avg_pool
CONVBLOCK Sequentia13(ACT, CONV, NORM)
(33)
ACT ::= relu hardswish mish
CONV convix1 conv3x3 dconv323
NORM ::= batch instance
layer
J.3 Supplementary results and analyses
Search costs Search time varied across datasets from 0.5 days (CIFAR-10) to ca. 1.8 days (ImageNet-16-122 using eight asynchronous workers, each with an NVIDIA RTX 2080 GPU, for ca. 4 to ca. 14.4 GPU days in total.
Test errors We report the test errors of our best found architectures Table 6. observe that search strategy BOHNAS finds the strongest performing architectures across all dataset on the hierarchical as well as cell-based search space. Note that we found, c.g., on ImageNet- 16-1 an architecture which is par with the optimal architecture of the cell-based NAS-Bench-22 search space (52.78 % vs. 52.69 %). When using BOHNAS in the hierarchical search space with more non-linear macro topologies and single, shared cell eiierarhicall shared -oot+ooon-lli linear) we can even better architectures, which improved the test error by 0.51 %, 1.1 %, and 4.99 % on CIFAR-10, CIFAR-100, ImageNet-16-120, respectively.
Figure shows the test error vs. number of parameters or FLOPs. Our best found architectures on hierarchical NAS-Bench-201 (hierarchical) fall well within the parameter and FLOPPs ranges of the cell-based NAS MAS-Bench-201 search space across all datasets, except for the parameters on CIFAR- 10. Note that our best found architecture on ImageNet- 1ir--66115 6-120 hierarchical NAS-Bench-200 is Pareto-optimal for test error vs. number of parameters and test error vs. number of FLOPs.
Best architectures Below we report the best found architecture dataset on the hierarchical NAS- Be--BBench211 search space (Section 4) for each dataset. Figure 10 visualizes the novel and diverse design of the architectures (including stem and classifier head).
CIFAR-10 (mean test error 5.65 %, #params 2.204 MB, FLOPs 127.673 M):
Sequential4 Sgggeniie-eeesddlllRRssaanaCCild convix1, layer)), (Seuueaaiaa
zero, SequentialI (Squuentaaaaaaaaaassssiia conv3x3, layer)), zero, Sequen- iisheeehneniiil conv3x3, instance))), [
dconv3x3, dconv3x3, layer)), id, zero), Cell(zero, cx layer)), id, 1xl, instance)). Sequential (eguuettalllSqqueet (Sequueniall conv3x3, layer)), Sequen- tial (SSequenniall(harasiiss dconv3x3, layer)))). Residual2(Cellldd, zero, Sequen- tial (Seluuentttiall cxlv layer)), (SqqenniallSSqqueeniaaaaaai
layer)), id, avg_pool, (Squuental
(Squuettal
(Squunttaall layer))))) conv3x3, layer)), zero), Cell(id, zero, id, Sequen- tial (reuuenaaaaaa,,,,,,,,, conv3x3, batch)), id, id),
convix1, layer)),
conv3x3, layer)). tiall (Seluenttttll,,,,,,l cony 1x1, layer)). Sequeental conv3x3, layer)).
convixl, layer)). Sequen-
31

---

Table 6: Test errors (and #: standard error) of popular baseline architectures (e.g.. ResNet [100) and EfficientNet [1] variants), and our best found architectures on the bell- and hierarchical B-----Be--2000 search space, Note that we picked the ResNet and EfficientNer et variant based on the test error, consequently giving an overestimate of their test performance. We also compared gradient- based approachess which cannot be applied to hierarchical search spaces without any novel adoption.
(best) test crror (and =:1 standard error) across three seeds {777, 888, 999} of the best architecture of the three search runs with lowest validation eтror. test errors on the hierarchical search space variant with more non- linelr macro topologies and single, shared cell (hierarchi cal wwwechhicaassshhheeeeeeeeaaaeeee +ssssah---oon linear, refer to Appendix J.2 for its definition).
AddNIST hieruchiccal
8.05 + 0.29
0.69
7.4 1 0.23
1.55
1.4
1.89
14.82 0 0.66
7.45 4 0.23
8.2 + 0.37
6.33 # 0.50
7.78 0.05 (34)
13:24 1. 0.58 (BI)
7.56
14.47
13.77
6.09 1:
0.23
4.57 4.57 0.38
0.38
cell bll.based
73.21 0.13
10.18 + 0.74
9.92 0.63
7.82 + 0.36
0.35 7.69
10.11 0.69
10.75 + 0.23
10.68 - 0.27
10.72 0.53
7.86 0.41
7.86 0.41
8.04 0.45
4.27
10.11
hierucchical
40.93 0.81
40.99 = 2.89
2.39
2.95
2.0
1.29
0.67
2.25
35.75 1.58
32.28 2.39
30.33 = 0.77
57.8 0.57 (18) 61 61.01 1 0.62 (BO)
CIFARTIle
38
49
43.31
45.66
42.45
36
37 1 1.62
39.2 2:24
cell Illbbased
76.1 + 0.07
54.77 + 0.68
55.15 + 2.3
52.72 + 0.45
52.79 # 0.59
1 2.29
41.63 + 1.02
+ 1.12
1 1.2
52.81 + 0.27
52.81 + 0.27
53.18 4 0.91
39.61
399
hierrchiicl
54.7 + 0.82
55,39 = 0.54
24.24 = 0666
0.29
58 47 2.74
0.91
57.58 = 153
54.61 = 0.28
53.47 0.86
0.61
52.78 = 0.23
ImageNer: 16 120
53.67 + 0.18 (56) 77.73 0.29 (BO)
53.43
58
49.47 1.73
1.116
cell .l--boeed
81.59 0.000
53.66 + 0.000
54.33 = 0.78
53.92 = 0.6
1.3
58.93 = 2.2
54.2 0.49
53.67 0,39
53.67 0.39
53.54 = 0.43
$2.69
55.99
56.8
bierarchical
29.49 + 0.57
30.0 = 0.32
29.35 + 0.79
31.73 + 0,96
31665 4 1.05
31.66 + 0.72
32.09 1: 1.61
29.25 4: 0.35
28.7 0.64
2 0.46
27.63 4 0.2
27.1 + 0.66 (110)
35.17 1 0.42 (B6)
27.57
CIFAR- 100
25.28 1 0.19
23.41 0.28
61.03 +: 0.000
26.49 = 0.001
28.75 = 0.57
27.68 # 0.55
0.3
28.91 + 0.25
29.37 : 0.17
29.95 1. 0.42
27.66 + 0.18
27.66 1 0.18
27.03 - 0.23
cell blssededd
26.49
29.35
optimal numbers as reported in Dong and Yang [58].
hierarchical
177000 0.1
6.88 0.24
0.03
8.56 0.87
8,26 + 0.38
8.4 1 0.52
6.68 4: 0.15
6.98 + 0.5
1: 0.16
5.65 = 0.09
6.49 + 0.24 (32) 11.73 = 0.1 (BO)
6.77
6.37
8.18
6.0
5.37 0.12
5.02 1 0.1
CIFAR-
cell bused
43.7 1: 0.00"
3.64 = 0.00
6.39 = 0.18
5,76 = 0.17
6.55 0.1
6.59 0.17
6.68 0.12
68 - 0.43
5.68 0.11
5.68 0.11
5.64 = 0.14
5.63
DANAS (progressive) [45]
NASWOT (N= 100) [65]
NASWOT (N= 10000 [65]
NASWOT (N= 10000) [65]
reported numbers.
NASWOT (N- 165]
Best EffcceenNett [1]
Best ResNar [100]
BOHNAS (best)
NAS Bench- 201
NASBOWL [48)
BOHNAS (beat)
NASBOT [18) [18]
DARIS [6]
DrNAS [45]
RE [9 12]
AREA 1651
BOHNAS
BOHNAS
Method
RS
32

---

CIFAR 10
CIFAR 100
ImageNet 16 120
Test. error [%]
100
50
75
80
70
25
50
0.2
1.2
2.2
0.2
0.9
1.6
0.2
0.9
1.0
# parrams [MB]
# params [MB]
#araams [MB]
all cells
best cell
(a) Test enror vs. number of parameters (#params (MB)).
CIFAR 10
CIFAR 100
ImageNet 16 120
Test error [%]
100
75
50
80
70
25
100
200
100
200
0
20
40
80
# #LOPss [M]
# FLOPs [M]
# FLOPs [M]
all cells
best cell
(b) Test error vs. number FLOPs (#FLOPs (M)).
Figure 9: Test enror number of parameters (a) and FLOPs (b) for each architecture candidate in the cell-based search space (blue dots), the best cell (orange cross), and our best found architecture in the hicrarchical HAS-Bench-200 search space (green star).
zero,
convix1, instance)), dconv3x3, batch)), (Squentaal
dconv3x3, instance)), Sequential (Sequenttial3rellu, convixl, batch)), id. id), down, down), Searraall@@@@eeemnaaalaaaaisisi dconv3x3, batch)), conv layer)), Se- convlx/ 1x1, batch)). (Squueaiill(SSquennaaaaaaaaaaa
conv3x3, layer)), id, avg pool),
down, down)). Residuull3(ResiduuaD(CCCCIC zero, Sequential conv convlx1, layer)). tial (Scquential3(miss, conv3x3, instance))), ( layer)), id, avg_pool, (Sequentta3n dconv3x3, layer)), id, zero), Cell(zero, (Squuetaal cx1, layer)), id, Sequential (Squuaataaannnaaaaaassiiii convlxl, layer)). Sequen- dconv3x3, layer)))). Residual2(Cell(dd, zero, Sequen- conv3x3, layer)),
(hardssiih, conv3x3, layer)), id, Sequen-
dconv3x3,
convix1, instance)). (Sequettall tial tial (Sequentiaa (mish, conv 1x1, layer)), (Sqquentiaa dconv3x3, batch)), zero), Cell(id, id, Sequen- tiall (Squeentnnnii, conv3x3, batch)), id. id), conv3x3. layer)), Sequentiall (Serentiall quential (Sequentiall3 conv3x3, instance)), zero, id)), Residual2(CCel((qqqente convixl, batch)), id, Sequentiall (SquenttaA Residual2(Celll) (Sequentaal
conv 1x1, layer)). Se- convix1. 1x1, batch)), Sequential I (Sequenttial (Sequential3(relu, dconv3x3, batch)), convlx1, batch)). id. id). down, down),
conv lx1. layer)). Sequen- (aaagueenntaa333asvvviiiiii dconv3x3, batch)). Sequentiall (Squuetial(Sequuntiaal (Seluentialaer,,,, conv Ixl, batch)), Sequential "Scpuential3(hardsishhh conv3x3, layer)), id, avg_pool), down, down)),
(eedie/enniieCe/leeeeeaaaaaaaaaa (harrwe conv3x3, batch)), (Squenttall convixt Ix1, instance)), Sequentiall (Squentiaal((ree conv 1x1, layer)), Sequential (Sequeetialleee cxlvlx1, layer)). Sequential Inquenttiall(Seen (Sequential convix1, layer)), id), tiall (Sequential3reelu, convixl, layer)), id, id), Cell(id, ( (qquentaalSSqqueniaalall
(Sequentiall conv batch)), id, id, Sequen-
conv 1xl, instance)). tiall (Sequentiall(relu, cxl, layer)). zero, convixl. instance)). Sequen- conv3x3, batch)))). Residual2(Cell(Sqqueee)) (Sequentiall Sequential Sequential (Sequentiall conv3x3, instance)). Sequential (Sequential convlx1.
conv3x3, layer)),
33

---

layer)), ( convixi, layer)), (Sequettal conv3x3. layer)), id). (SSpeettaaiallssSeeeeeaaaaaaaa
1x1. batch)), id. id, Sequen- tiall (Sequenttaler, conv3x3, batch)), id, id), Cell(id.
conv Ixl, instance)), (qquentiallsqueeniaBrrelll convixl, instance)), Sequen- tial (Scquentiaal dconv3x3, layer)), zero, (SguuttttiilllsSSuuuutaaaEEee dconv3x3, instance)), zero, zero, id,
dconv3x3, layer)))), zero, id)), Beaaraaiiieeeeidaaaaeelleeeeeeee (Sequential conv3x3, layer),, cxnvIx1, layer)). Sequential (Sequentiall(relu, 1x1, layer)), Sequential I (Sequential3rell, conv3x3, layer)), id), Cell(Sequntiall(SSqg) (Sequential33relu, convixl, batch)), id, id, Sequen- tiall (Sequenttnil conv3x3, batch)), id, id), Cell(id, (Squential(Sequeniaal conv instance)), Sequentiall (equentilell,, convlx1, instance)). Sequen- tial [Sequenntiaallrrrll, cxnvixl, layer),, zero, conv3x3, batch)))), Residual2/Cell(Scqunnaaalll (Sequenttial (Sequtttiiilit (SqpeentallsqquuenttaaaaaC conv3x3, layer)), layer)). (Sseeeniial(Squuenaaaaaaae convix1. 1x1, layer)), Sequential conv3x3, layer)), id), Cell(eqquntiall tial (Sequentiall(relu, conv3x3, batch)), id, id), Cell(id, Sequential (Seluential(rellu, convlxl, instance)), Sequen-
(Squentiall conv3x3, layer)),
conv3x3, layer)), convlxl,
1xl, batch)), id, id, Sequen-
convlxl, lx1, instance)), tial (Sequeential((reuu convix1, layer)), zero, (esuuettiill/sguuenaaaahhhra conv3x3, layer)))). (eeeuaaDDCCeelleeqeeeillquluuure
conv3x3, layer),, (Sequentaal conv3x3, layer)), Sequential (Sequentiall(relu, convlx1 1x1, layer)), Scquentiall (Sequenttaal(relu, cxnvix1, layer)), Sequential I( (Sequentiall conv3x3, layer)), id), tiall (Sequentiall((elu,, conv3x3, batch)), id. id), Cell(id, (eqqential conv 1xl, instance)). (Squentaal convixl, instance)). Sequen- tial (Sequential3(relu, convixi, layer).. zero, (Squeatial(Sequenaaaaaaaaaaar conv3x3, layer)))), Cell(id, (Sqqueniall convix1, batch)), id, zero, id)))
convix1, batch)), id, id, Sequen-
convix1, layer)),
CIFAR-100 (mean test error 27.63 %, #params 0.962 MB, FLOPs 115.243
conv3x3, layer), pvg_ Se- (hartial sonvlx1. instance), zero, Sequentiall(mish, conv3x3, batch), zero), CellSeqqueniial3(aandwwis dconv3x3, batch), zero, Sequential3harrdsiis 3xonv3x3, hatch), Sequential3(relu ((reu,, deonv3x3, hatch), id, id), CellSequentiial(mmik) conv3x3, batch), zero, id, zero, SequentialB(hardssshhl dconv3x3, batch). id)). Sequential2(Cellidd. zero, Se- (mint conv3x3, batch), zero, zero, Sequential3mmish, convix1, batch)). Cell(zero, zero, zero, id. zero, avg pool)), Cell(SequeniallSreel, conv3x3, batch), zero, Sequen- rial3(hadssiish, conv3x3, instance), id, id, avg_pool), Cell(id, id, zero, zero, id, id)), Residdua Scco:ittandcceeSSSSuuuuaaaaaaiii dconv3x3, layer), Scquential3 dconv3x3, batch), Sequential conv3x3, instance). Sequential3 (mish, conv3x3, batch)). Cell(Sequential3 (hardwssssh conv Ix1, layer), id, ( id. id). Cell(Sequental(rellu conv3x3, instance). zero, id, zero, Sequential3mmish, conv3x3, batch), avg pool)), Scquential3iCCell2zooo. id, Scquential3(harddwsshh convixl, layer), Sequential3(issh conv3x3, instance), Sequentiall(mish, conv3x3, instance), zero), ( convix1, layer), id, SequentialBhhardswssh, dconv3x3, batch), Sequential3(relu, conv3x3, batch), id, id), Cell(Sequential(rrell conv3x3, instance), zero id, zero, Sequential3(mish, conv3x3, layer), poo_) Sequential3(mish, conv3x3, layer), avg_pool, Scquential3(mish, conv3x3, layer)), down, down), Resiidual((eellzzroo. id, zero. Sequentiallmmish, conv3x3. batch), avg pool. Sequen- tial3 conv3x3, layer)). down, down)), conv3x3, layer). id, Sequeeniallhhardssishh dconv3x3. layer), Sequential3/aardsissh, dconv3x3, batch), SequentialB(mish, conv3x3, instance), Scquentiall(mish, conv3x3, batch)), Cell[SequentiiaSShaarssssss convix1, layer), id, Sequeettaa dconv3x3, batch), Sequential3(relu, conv3x3, layer), id, id), Cal((Scquenttaa3rrelu,, conv3x3, instance), zero, id, zero (mish, conv3x3, batch), avg_ wrg_)))l)). Sequen- LLLLCCell(equentill(iiiii conv3x3, batch), id. Sequential3hharddsist. conv batch), Sequential3 conv3x3, instance), Sequential3(mmssh, conv3x3, instance), zero), Cell BallSSeuueniaalhhadswiii conv Ixl, layer), id, SequentialB(hardswish, dconv3x3, batch), ( dconv3x3, batch), id, id), Cell(Sequential3(eelu conv3x3, instance), zero, id. zero, (mmu,, conv3x3, layer), mog_)ool)), Residual2(Cell(een id, zero, Sequential3miish, conv3x3, layer), pool, SequentialBmmish, conv3x3, layer)).
conv3x3, layer), id, Scquential&
dconv3x3, batch), Sequential3(rllu, conv3x3, layer),
id, zero,
34

---

down, down). Residual2((eelleero,,, id, zero, Sequential3(mishh conv3x3, batch), _ pool, (enus, conv3x3, layer)), down, down)))
1nageNee-1661200 (mean test error 52.78 %, #params 0.626 MB, FLOPs 23.771 M):
avg_pool, id, id, Sequential 3 layer), zero), Cell(Sequnniial convix1, batch), zero, zero, S (mish, dconv3x3, layer), zero, zero), Cell(Sequetial dconv3x3, layer), Sequential3 doonv3x3, layer), zero, Sequential conv3x3, layer), Sequentiall(relu, dconv3x3, instance), Sequential3(hardssiss tial3(relu, conv3x3, layer), Sequentialßmiish, cx,vix1, batch), Sequentiall(mish, 1xl, batch), avg pool. Sequential(relu. conv3x3, layer)), Cell(id, id, Sequential3mmish, conv3x3, layer), Sequential3(relu, conv3x3, instance), id, id)). Residual2(Cell(zero,, avg pool, Sequen- (mish, conv 1x1, batch), Sequential conv 1x1. layer), zero, zero), Cell(id. Sequen- tial3(relu, 3x3nv3x3, layer), zero, zero, Sequential3rrelu, dconv3x3, instance), zero), Cell(id, Sequential3(relu, conv3x3, layer), id, zero, zero, id)), Cell(zero, Scquential33hardssishh conv3x3, layer), avg_ zero, ScquontiallBhardssssh, convixl, layer), id)), Resid- conv convix1, instance), Sequential3mmish, conv 1x1, layer), (miu, convixl, instance), zero, Bequential dconv3x3, layer), id). Cell(id, avo_pool, avg. avo_. Sequential3(relu, convix1 1x instance), id, zero), Ballavg__pol, Sequential3(mish, conv3x3, instance), Sequential3mmish, convixl, instance), Sequential3 dconv3x3, batch). id, Ssquential3(harddwwai conv3x3, instance))), Se- quential2(Cell(zen Sequential3(rllu, conv3x3, layer), Sequential convlx1, batch), Sequential3 convix1, batch), avg_pool, Sequential ((relu, conv3x3, instance)), Cell(id, zero, Sequential3(mish, conv3x3, layer), Sequential3(relu, conv3x3, instance), id, id), conv3x3, layer), Sequential3(mish, cxnv1x1, batch), id, 3 conv Ix1, layer), zero, id), down, down). (esiiduul2(Cl((SSqqenniaaaa conv3x3, layer), zero, SequentialBírelu, dconv3x3, layer), Sequential conv 1x1, layer), zero, id). down, dowa)). Sequential3 (mish, convlxl, layer), Soquential3(mish, convixl, instance), avg_pool, Se- quantial33hardssishh, dconv3x3, layer), id), Cell(id, pvo_ avg pool, Scquential3(rchu, 1x1, instance), id, zero), Cell(avg_pon) pool, Sequentialß(mish, conv3x3, instance), Se- quential3(mish, convix1, instance), Sequeetiall dconv3x3, batch), id, Sequen- (hardswss,,,, conv3x3, instance))), Sequential2(Celllzero, Sequential3(relu, conv3x3, layer), Sequentiallmmish, conv 1x1, batch), Sequentiall(mish, convix batch), avg_ avg_pool, Sequential3(relu, conv 3x3, layer)). Cell(id, zero, Sequential3 conv3x3, layer), Se- quential3(relu, conv3x3, instance), id, id)). layer), avg pool. id, Sequential3 conv3x3, instance), zero, id), down, down), Resid- ual2(Cell(Scqueenilltrct conv3x3, layer), zero, Sequential3(relu, dconv3x3, instance), Sequentiall(mish, convix1, layer), zero, id), down, down)))
conv3x3, instance))), Sequential2(Celllzze,, Sequen-
convixl, instance).
conv3x3,
CIFARTile (mean test error 30.33 %, #params 2.356 MB, FLOPs 372.114M):
conv3x3, instance), id, zero, Sequential3(relu, dconv3x3, instance), Sequential3 conv Ixl, instance), avg avg_pool). Cell(avg pool, avg wyg_pool, id, zero, avg_pool), Cellseqquential((reuu, dconv3x3, instance), zero, id, SequentialB(rclu, dconv3x3, layer), id, id)) Residual2(Celllzzro. zero. Sequential3mmish convixl, instance), Se- (mint,al3(mish, conv3x3, batch), zero, id), Cell(Sequential(mmsshh conv3x3, instance), zero, eequenntaal3rrluu doonv3x3, batch), id, Sequential conv3x3, batch), id), CellSSequential(haaddviii dconv3x3, batch), Sequential3(relu, conv3x3, batch), Se- (rent,al3rrelu, cx,, hatch), zero, Sequential3(relu, conv3x3, batch), id)). Sequen- (eQuueetllS 3x3n layer). Sequentiall(mish, conv 1x1, layer), id, zero, (Sque conv3x3, batch). Sequential3(relu, dconv3x3. layer)), down). Sequen- (ial2(Cell(id, Sequential conv cxlv layer), id, Sequential3 conv cx.v in- stance), avg_pool, Sequential3rrelu, convixl, layer)), down)), ( avg_pool, avg_pool, Schuennia dconv3x3, instance), Sequential convix1, layer), Sequential dconv3x3, instance)), Cell(id, id, Scquential3 dconv3x33, layer), id, id, zero), Cell(Sequential3(rel.. conv3x3, layer), id, avg pool, Se- (mential3(mish, dconv3x3, instance). Sequential3(rllu. conv convix1, layer), zero)), Resid- MalZ[CellSSqueentialmmmm
conv3x3, batch),
conv3x3, batch), Sequential3(mish, conv3x3, instance), zero, avg_ avg_pool, avg_pool, Sequentiall(mish, couvlxI. batch)), Cell(Sqquential conv Ixl, batch), Sequential3 dconv3x3, layer), zero, id, avg_ poo_ avg poo_), Cell(avg pool, Sequentiaal conv instance). id, avg pool, avg_pool, Sequential conv 1x1, instance))). ResidualZ(CalISeeeeniiaBBBee dconv3x3, batch), avg pool, id,
35

---

avg. pool, id, zero), down, down), Residual2(Celllzero,, zero, SequentialSrell, 3xonv3x3, batch), avg pool, Sequential 1xl, instance), avg pool), down, down)). Se- quential4SSqqueniall3 Sagaaeeeeeaaaaaaleeeeeeuaaaaaaaa Sequential conv3x3, batch), SeguentialShhardsissh, conv3x3, batch), SequentialBrrllu, convixl, instance), id, Sequential3(relu, convixl, layer), Sequentialã(relu conv3x3, layer)), Cell(id, Sequential conv3x3, instance), Scquential conv Ixl, instance), Sequential3(retu, conv3x3, layer), avg_pool Sequential3miisk convix1, layer)) Cell(zero, zero, id, SequentialBrrelu, conv3x3, batch), id, (equential3 convixl, layer))), cony3x3, batch), S conv3x3, batch), Sequential3rrelu, convixl, instance), (rruen dconv3x3, layer). Sequential3(mish conv Ix1, layer), Se- (uential3(relu, conv3x3, batch)). Cell(id, Sequential3rrelu, conv3x3, instance), Sequen- (harswhs,,,sshh, conv convix1, instance). Sequential dconv3x3, instance). avg pool, Se- (mint,al3mmish, convix1, layer)), Cell(zero, zero, id, Scquential3(relu, conv3x3, batch), id, avg_pool)), Sequential3(Celllid, id, avg_pool, Scquential3(miis conv1xl, layer), Sequential(mmish, conv3x3, batch), zero), Cell(id, Scquen convixl, batch), avg pool, Sequential3(relu, conv 1x1, layer), avg p zero), Cell(zero, Sequential3 1x batch), Sequential3mmish dconv3x3, batch), Sequential3 conv Ix1, batch), id, id)), Cell(id, Scquential3 conv 1x layer), zero, id, zero, id)). Sequen- fal3(Sequential2(eeiii zero, Sequential3missh dconv3x3, instance), Scquentialã conv3x3, batch), (mquential3mmish, deonv3x3, instance), Sequential3(relu, conv 1x1, in- stance)). Cell(Sequentiaa(rell,, dconv3x3, instance), avg_pool, Semuential convixl, instance), (equuential(harrssiiitt dconv3x3, instance), id, Sequential conv Ixl, layer))), Scquential2(Celllzen, zero, Sequential dconv3x3, instance), Sequen- tirll, conv3x3, instance), Scquential&(harddswihh conv3x3, hatch), avg_ "poo), Cell(id, id, Sequential3hhardswihh. conv 1x1, instance), avg_pool, zero, Sequential3barrdswikte conv3x3, batch))). Cell(avg pool. Sequential dconv3x3, layer), zero, avg pool, avg pool, zero)))
AddNIST (mean test error 6.33 %, #params 2.853 MB, FLOPS 593.856 M):
Sequential (conv3x3, batch), Se- quential3rrelu, convixl, layer). Sequentiall(mish, conv3x3, batch), avg_pool, zero), Cell(zero, zero, avg_pool, id, avg_pool, Sehusetial convlxl, instance)), CellSSqqueniial(reel, conv3x3, layer), id, zero, Sequential3(mish, conv3x3, instance), id, avg. pooo))))) Sequentiaa2((eel(id,, Sequential(relu,, conv3x3, layer), Sequential3(relu, conv3x3, layer), Sequential conv3x3, batch), id, Sequentiallrrelu, conv3x3, layer)). Cel([eqqueniill3(ishh conv3x3, instance), id, Sequential3(mishh conv3x3, batch), id, oyg_pool, id)). Sequeetial3(Ceell(eee.. id, Sequential3(relu, dconv3x3, instance). Sequential dconv3x3. layer). Sequential3(relu, dconv3x3, instance), Sequen- (mish, conv3x3, batch)), Cell(Sequential conv instance), zero, Sequen- tial3(relu, conv3x3, instance), id, zero, Scquential3(relu, conv3x3, batch)), down), Se- gueltial3(Cell(zroo,, avg_pool, Schuenttal&hhardssissh, dconv3x3, layer), Scquential3rrclu, conv3x3, layer), Scquential& convixl, instance), Sequential (hardswwis conv3x3, batch)), CelisSequeniaal(haarrsssst conv3x3, batch), SequentiallKhardssishh 1xl, layer). Sequentiall conv 1x1, batch), id, ScquentialB(harddwissh conv3x3, batch), zero). down)), avg_ Scquential3(harddwis dconv3x3, batch), Sequential3mmish, dconv3x3, batch), id, Sequential3mmish, conv3x3, layer)). Cell(zero. Sequentiallreluu, dconv3x3, layer), Sequential conv3x3, instance), avg_pool, avg. pvol, zero)), Se- quential((Cell(Sqqunniaa
cxlv layer),
conv3x3, batch), id, Sequentiall3relu, conv3x3, layer), Sequential3(mish, co instance), id, Sequential3rrelu dconv3x3, batch)), Cell(Sqqueniall((ishh, conv3x3, batch), Sequential3 1x,v instance). Sequen- tiilh, conv3x3, instance), zero. (equentiallmmish, dconv3x3, layer). Sequential3 conv3x3. batch)). Cell(avg pool, Sequential conv lx1, instance). Sequentiall(relu, conv3x3, batch), avg. pool, id. Sequentialmmish, dc3nv3x3, batch))). Dequential3(Cell((ee avg avg_pool, SeahentialS dxonv3x3, layer), Scquential3(relu, conv3x3, batch), Schpential&hhardsiishh convixl, batch), Scquueniial&hhardsishh conv3x3, batch)), Cell(avg_pool. Sequeniaal dconv3x3, layer), Seque convixl, batch), id, (Cquential3hhardwiiin conv3x3, batch), zero), down). Residual2(Cell((er.. Sequen- tial3 conv 1x1, instance), "equuential3haardwiiii convixl, instance), wgo_, Se- quential3(relu, conv 1x1, layer). ((aauenwtal 33onv3x3, batch)), down, down)), (eanaaaaeSSSeeeaaaaaaaaalSeeeeee
conv3x3, instance), id, Sequential conv3x3, batch), avg_pool, zero, id), Cell(avg_ pool. Sequential conv3x3, layer), avg_ SequentialBmmish, conv3x3, batch), Sequential3(relu, conv3x3, batch), id)). (eguuential2CCllSSSeennnaal
cxnvlxl, layer), avg ppol, Sequential33hardswsshh
36

---

deonv3x3, batch), Sequential3(mish. dconv3x3, batch), id. Sequential3miish conv3x3, layer)). Cell(zero, Sequential3(relu, dconv3x3, layer), Shauential,hharddiishh,,, conv3x3, instance), avg pool, stance), Sequential conv3x3, layer), ScquentialB deonv3x3, batch), id, Sequential3(relu, conv3x3, layer)), (emiS conv convixl, batch), id, avg_ id, avg_pool, id)), Cell(id, Sequentiall(relu, conv3x3, layer), Semuential convixl, in- stance), SequentiallKhardswishh conv3x3, batch), Sequential3mmish, dconv3x3, instance), Se- SeearaaaaeSeeeeeaiieeeeellaaeeee
aool pool, zero)), Sequential((eellidd, Sequential3rrllu, conv3x3, in-
quential2hhardssishh, conv instance))).
conv3x3, instance), id, SequentialB(relu, conv3x3, hatch), avg_pool, zero, id), Cell(zero, Sequential3rell. conv3x3, batch), avg_ avg_pool, (miu,, conv3x3, batch), Se- conv3x3, batch), id, Sequential3reelu. conv3x3, layer), (miu,n conv 1xl, layer), id, Se- (rent,a dconv3x3, instance)), Cell[Sqquentall(miik conv3x3, batch), Sequen- tial tmal3, convix1, instance), (rguuential(hardswviii dconv3x3, instance), zero, Sequen- tial timi3,,,sh, dconv3x3, layer), Scquential3 conv3x3, batch)), Cell(avg_ pool, Sequen- (mish, convix1, instance). Sequential3(rllu, conv3x3, batch), _ id, Sequen- (mish. dconv3x3, batch))), (equential(Ceelldd. Sequentiallrrelu, conv3x3, layer), SequentialSShardssiia conv3x3, layer), SequentialShhardssshh dconv3x3, batch), id, Se- quentialß(relu, conv3x3, layer)), Cell(Sqquential3(mis))) conv3x3, batch), id, avg_pool, id, avg_pool, id)) Cell(id, Sequential3reluu, conv3x3, layer), Sequentiallmmish, convixl, instance),
(uential3reelu, dconv3x3, instance), id)) (eweeniiillCCelSSSeeeaaaaaa///
conv3x3, batch), Sequentiall(mish dconv3x3, instance), Sequential3 conv3x3, instance))))
Below we also report the best found architecture per dataset on the hierarchical search space with more non-linear macro topologies (instead of linear macro topologies) and single, shared cell wawechiccttshaard-oooo
For sake of readability we report macro topology and cell separately. Different the best architectures found in the hierarchical space (hierarchical), the found architectures on this variant tend to have higher computational complexity (parameters and FLOPs).
search
CIFAR-10 (mean test error 5.02 %, #params 4.82 MB, FLOPs 439.796 M):
Shared, Shared), Diamond2(Shared, Shared, Shared, Shared), (Shadd,l down, down), Residual2(Shared, down, down)), Resid- Mal3(eesiduull(Shared Shared, Shared), (liamon2((Sharee) Shared, Shared, Shared), Di- aShand(Sharedd, Shared, down, down), (Saaond2(Shared,, Shared, down, down)). Dia- mondd(RRsidnall(Saare.. Shared, Shared), Residual2(Shared, Shared, Shared), Resid- uShrreh, Shared, Shared), Residual2(Shared, Shared, Shared), Shared, Shared))
CellSequential3hhardsiis conv3x3, layer), Scquential3(harddsiss conv3x3, layer), Se- (mintial3(mish, conv3x3, layer), ScquentialB(rllu, conv3x3, batch), SequentialBmishh conv3x3, instance), Sequential3(relu, convix1, batch))
CIFAR-100 100 (mean test error 25.41 %, #params 2.68 MB, FLOPs 307.87 M):
Shared, Shared). Residual2(Shared, Shared, Shared), Residuall(Shared, down, down). Sequential2(Share,, down)), ResidualS Shared, Shared), Residual2(Shared, Shared, Shared), Residual2(Sharrcd, down, down), Sequential2(Shared, down)), Residnal((Rssiddu222SShhre Shared, Shared), Soquential2(Shared, Shared), Shared, Shared), Sequen- iial3(Diamon2((Saared, Shared, Shared, Shared), Sequential2(Shared, Shared), Shared))
Cell(Sequential((mms))) conv3x3, batch), Sequential3rrelu, conv3x3, hatch), Sequential3 conv3x3, batch), (equen conv3x3, batch), (equential dconv3x3, instance), id)
ImageNet- 16 16-120 (mean test error 48.16 %, #params 0.852 MB, FLOPs 89.908 M):
Shared, Shared, Shared), Desiduul2((hharee Shared, Shared), Shared), (Ramoond(Resdddu222SSaaa Shared, Shared), (aamond2((Shaed)) Shared, Shared, Shared), Residual2(Shared, Shared, Shared), Diamond2(Shared, Shared, Shared, Shared). Diamond2(Shared, Shared, down, down), Diamond2(Shared, Shared, down, down)), Desiddaa3KResiduul22/Saaaa Shared, Shared), Residual2 Shared, Shared), Residual2(Shared, down, down), Residual2(Shared, down, down)))
37

---

(a) CIFAR- 10.
38

---

6003
(b) CIFAR-
39

---

(c) ImageNet- 16-100.
40

---

(d) CIFARTile.
41

---

CHEEO
(e) AddNIST.
Figure 10: Visualization of the best found architectures in our hierarchical NAS-Bench-201 search space. Abbreviations are defined follows: ap=avg_ pool, ba=batch, cl=convixl, c3=conv3x3, cls=classifier, dc=dconv3x3, ha=hardswish, in=instance, la=layer, mi=mish, re=relu, and stm=stem. Best viewed with zoom.
42

---

CI
CIFAR-100 100
Image Net- Net-1-12111
CIFe
AddNTST
40
70
80
15
80
40
Vol
10
30
BOHNAS
NASHOWL R3
NASROT
RE
AREA
BOHNAR
NASHOW
R3
NASDOT
RE
AREA
ROHNAS NASBOWI
RS
NASBOT
RE
AREA
BOHNAS NASBOWI
NASBOT
RE
AREA
BOHNAS
NASBOW
RS
NASROT
RE
AREA
Figure 11: Density estimates of the validation errors of all architecture candidates proposed by the
search strategies and across all datasets from our experiments in Section 6.
CellSSqquential((missh, conv3x3, batch), Sequential3(mish, convixl, batch), Sequen- tial3(relu, conv3x3, instance), Sequential3(mish, conv3x3, instance), Sequential3(relu, conv3x3, batch), id)
CIFARTile (mean test error 39.2 %6 #params 10.712 FLOPs 1519.944
Shared, Shared), Residual Shared, Shared), Diamond2(Shared, Shared, down, down)), Revidull(Sqqeemta222Saaee Shared), Residual2(Shared, Shared, Shared), Sequential2(Shareed down), Diamond2(Shared, Shared, down, down)), aShard)SSarred. Shared, Shared, Shared). Sequential2(Shared, Shared). Shared, Shared), SramoonS(Sequentaal2SSarr Shared). Sequential2(Shared) Shared), Sequential((hharel Shared), Sequential2(Sharee (Shaaed,, Shared), Shared, Shared))
Shared), Scquential2(Shared, Shared), Di-
Cell(Sqquentialmmmsshh conv3x3, batch), Sequential3rrelu, conv3x3, instance), avg_ syg_poo,, Sequential3miish conv3x3, layer), Sequentiallrellu, dconv3x3, layer). Sequential3 conv3x3, layer))
AddNIST (mean test error 4.57 %, #params 3.345 MB, FLOPs 347.959 M):
DeneenaallDDiamoooon/a/aaaooo (Shared, Shared, Shared. Shared). Diamond2 Shared, Shared, Shared), Diamond2 Shared, Shared, Shared), Diamond2 Shared, Shared, Shared), Residual2(Shared, down, down), Residual2(Shared, down, down)), (isiduai((Dammon2((Saara) Shared, Shared, Shared), Diamond2(Shared, Shared, Shared, Shared), Residual2(Shared, down, down), Residual2(Shared, down, down)), Resid- ual3(Diamond((haardd, Shared, Shared, Shared), Diamond2(Shared,, Shared, Shared, Shared), Shared, Shared), Aequential(SSequenaaa22222 Shared, Shared, Shared), Shared))
Shared), DSaaond2(Shared,
CellSeqquettial((ell,, conv3x3, batch), zero, avg. avg__ool, Sequential conv3x3, instance), SequentialBharddswit, conv3x3, instance), Scquentiall3(arddsiish conv3x3, instance))
Is BOHNAS exploring well-performing architectures during search? To investigate this ques- tion, visualized density estimates of the validation error of proposed candidates for all search strategies across our experiments on the hierarchical NAS-Bench-20 search space from Section 6. Figure 11 shows that BOHNAS explored better architecture candidates across all the datasets, ie.. has smaller median validation errors and the distributions are further shifted towards smaller validation errors than for the other search strategies.
Does incorporating hierarchical information improve performance modeling? To further assess the modeling performance of our surrogate, we compared regression performance of GPs with different kernels, i.e., our hierarchical WL kernel (hWL), WL kernel [48], and NASBOT's kernel [18]. We also tried the GCN encoding [52] but it could not capture the mapping from the complex graph space to performance, resulting in constant performance predictions. Further, note that the adjacency encoding [50] and path encoding [47] cannot be used in our hierarchical search spaces since the former requires fixed number of nodes and the latter scales exponentially in the number of nodes. We re-used the data from the search runs and ran trials over the seeds (O.... 19). In every trial, we sampled training of varying number and test set of 500 architecture and validation
43

---

CIFAR-10
CTFA R-100
ImageNet-16-1
CIFARTile
AddNIST
0.7
0.7
Kendall's
0.6
0.6
0.3
0.5
0.3
0.4
0.4
0.4
0.4
200
400
200
400
200
400
200
400
200
400
#train samples
#train samples
#train samples
#train samples
#train samples
hWL
WL
NASBOT
Figure 12: Mean Kendall's rank correlation with +1 standard enror achieved by a GP with various kernels.
CIFAR-10
CIFAR-100
Manageeet-11e 16-120
CIFARTile
AddNIST
Vaa error 1%6
32
58
60
10
30
50
54
8
28
52
26
50
50
100
0
50
100
25
50
75
100
25
50
75
100
25
75 100
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
hicrarchical
hierarchical without flexible parameterization
Figure 13: Impact of flexible parameterization of convolutional blocks in the hierarchical NAS- Bench-201 search space.
error pairs, respectively. We recorded Kendall's rank correlation between the predicted and true validation еггоr.
Figure 12 clearly shows that the incorporation of the hierarchical information in the kernel de- sign improves performance modeling. This is especially pronounced for smaller amounts of seen architectures.
What is the impact of flexible parameterization of convolutional blocks? To investigate the impact of the flexible parameterization of the convolutional blocks (i.e., activation functions, normal- izations, and type of convolution), we removed the flexible parameterization and allowed only the same primitive computations as the cell-based NAS-Bench-200 search space, while still searching the macro architecture. More explicitly, only allow ReLU non-linearity the activation function, batch normalization as the normalization, and 1 1 or 3 3 convolutions. Figure 13 shows that for all datasets except CIFAR-100 flexible parameterization of the convolutional blocks improves performance of the found architectures. Interestingly, we find an architecture on CIFAR-100, which achieves 26.24 % test error with 1.307 MB and 167.172M.. M number of parameters FLOPs, respec- tively. This architecture is superior to the optimal architecture in the cell-based NAS-Bench-200 search space (26.49 %). Note that this architecture also Pareto-optimal for test error number of parameters and test error vs. number of FLOPs.
zero-cost proxies also work in vast hierarchical search spaces? To assess zero-cost proxies, we re-used the data from the search runs and recorded Kendall's 7 rank correlation. Table 7 shows that nwot is surprisingly the best-performing non-baseline zero-cost proxy, even though it is specifically crafted for architectures with ReLU non lineariitis.s Interestingly, the baseline zero-cost proxies often yield better results than other non-baseline cero-cost proxies. Thus, expressive hierarchical search spaces bring new challenges for the design of zero-cost proxies.
Search space comparisons Supplementary to Figure 3, Figure 14 compares the search space vari- inear
ants hi hierarchical vs. fixed+shared (cell-based) vs. using RS, RE, and NASBOWL. The cell-based search space design shows on par superior perfor- mance on all datasets except for CIFARTile for the three search strategies. This is in stark contrast to the results using BOHNAS (Figure 3). It shows that more expressive search spaces do not necessitate
44

---

add Table 7: Kendall's rank correlation of zero-cost-proxeee
hierarchical NAS-Bench-200 space. Note that zen and nwot may not be suitable for our hierarchical search space, as they are specifically designed for architectures with batch normalization and ReLU non-linearity, respectively. We report exemplary search results for NASWOT [65] in Table 6.
Zero-cost proxy
Type
CIFAR-10
CIFAR-100
ImageNet-16-120
CIFARTile
AddNIST
plain [66]
Baseline
-0.01
0.0
-0.08
0.02
-0.04
params [67]
Baseline
0.05
0.24
0.37
0.09
0.14
flops [67]
Baseline
0.16
0.38
0.38
0.36
0.33
12-norm [66]
Baseline
0.58
0.42
0.29
0.44
0.63
zen-score [101]
Piece. Lin.
0.54
0.5
0,42
0.27
0,45
fisher [102]
Pruning-a at- init
-0.24
-0.21
-0.13
-0.12
0,01
grad-norm [66]
Pruning-u itii
-0.17
-0.14
-0.08
-0.01
0,06
grasp [103]
Pruming-al at-ggg--t-ii
-0.02
0.07
0,05
-0.01
-0.0
anip [104]
Pruming-ut-Be
-0.1
-0.15
-0.11
0.05
0.13
synflow [105]
Pruning-at-init
0.09
0.35
0.42
-0.21
-0.11
epe-nas [106]
Jacohian
0.11
0.17
0.26
0.15
0.03
jacov [65]
Jacohian
0.3
0.29
0.2
0.21
0.17
nwot [65]
Jacohian
0.36
0.58
0.73
0.46
0.21
Table 8: Vocabulary for the binary and unary operations in the activation function search space. The symbol B indicates per-channel trainable parameter and o(-) is the sigmoid function.
2: +-32
bgaucctan,cc oa
exp 1 B(2 m2)" expl 3pm - Jgl) Sag Bjrg
cubic aquare Foot
coe
DOB.r
UD3x unis
maxfa, 0) min(s. a(s)
xulii 21
bgaussias abs
ainh
sinb
sub
warg sd
aconst aconat log
cosh
cashi 2)
signoid
div
tanh
Tann [
log(( + exp(x))
beax
maax 25)
nag wbs
-
log(1s) ()
asinh
sinh (4)
gaussian
exp(=2?)
bein
[e]
exp(a)
atanh
Tunh (x)
wrr
erf(e)
beignoid
equare
sinn(a)
an improvement in performance since search strategy also needs to be able to such well-performing architectures. It also shows the superiority of BOHNAS over the other NAS approaches (Q1) and provides further evidence that the incorporation of hierarchical information is key contributor for the search efficiency (Q2). Based on this, we believe that future work using, e.g., graph neural networks as surrogate, may benefit from also incorporating hierarchical information.
For the hierarchical search space with more non-linear macro topologies (instead of linear macro topologies) and a single, shared cell (hierarchi cal ssharednno wnnnoonniinn linear), we find similar pattern as Figure We believe that one reason for this is that the architectural regularization (sharing of single cell) reduces search complexity.
K
Searching for activation functions
K.1
Search space
To search for activation functions, we adopted the search space from Ramachandran al. [64]. More specifically, we define the search space as follows:
L2 : BinTopo [L, L1, BINOP) UnTopo(LL)
L1 = BinTopo (UNTOP UNOP, UNOP, BINDP) UnTopo(UNOP)
BINOP = add multi sub div bmax bmin bsigmoid bgaussian_sq
bgaussian_abe wavg UNOP id neg abs square cubic sqqare_roor mconst aconst sinh
(34)
log exp
sin
cosh tanh asinh
atanh
sinc
umax
umin
sigmoid logexp gaussian erf
const
where the vocabulary for the binary operations (BINOP) and unary operations (UNOP) is provided Table and BinTopo and UnTopo define the topological operators of binary or unary operations, respectively. The search space comprises ca. 108.6 potential activation functions. Note that the search space size can be varied by adding more levels or can be made open-ended by using a recursive formulation, i.c., L ::= BinOp(L, L) UnOp(L) lid.
45

---

CIFAR-10
CTFA R-100
ImageeNe Net- 16- 1--
CIFARTile
AddNIST
Vai error [96)
32
58
60
10
30
56
50
28
40
8
26
52
30
50
100
0
50
75
100
25
50
75
100
25
50
75 100
25
75 100
Evalnations
Eva Enations
Evaluations
Evaluations
Evaluations
hierarchical
hierarchical non wenn-lineaa---- -inear-shared cell
cell-based
(a) Random Search (RS).
CIFAR-10
CIFAR-100
IrnageNet- 1-120
CIFARTile
AddNIST
Val orror [96]
32
10
10
30
56
60
51
26
52
40
7
8
26
30
0
25
50
75
100
0
25
50
75
100
25
50
75
100
25
50
75 100
25
50
75 100
Evaluations
Eva Ivatioooons
Evaluations
Evaluations
Evaluations
hicrarchical
hicrarchical+ lincar-shared cell
cell based
(b) Regularized Evolution (RE).
CIFAR-10
CTFAR R-100
TmageNer- 16-120
CIFARTile
AddNIST
Val error 1998
30
56
28
54
40
52
26
50
30
6
0
25
50 100
50
76
100
25
30
75
100
25
50
75
100
25 50
75 100
Evaluations
ivalnations
Evalnations
Exalnations
Evalnations
hierarchical
hierarchical + non-lineat shared cell
cell-based
(c) NASBOWL.
Figure 14: Comparison of mean and +1 validation error of bierarchical, hierarchical with shared cell, and cell-based search space designs using Random Search (RS) (a), Regularized Evolution (RE) (b), and NASBOWL (c) for search.
K.2 Training details
Similar to Ramachandran al. [64], we trained ResNet-20 [100] on CIFAR-I0 [93]. Specifically, we trained the network with SGD with learning rate of 0.1, momentum of 0.9, and weight decay of 0.0001, with a batch size of 128 for 64K steps. The learning rate is divided by 10 after 32K and 48K steps. We used random flip with probability 0.5 followed by random crop (32x32 with 4 pixel padding) and normalization. We split the training data into 45K training or 5K validation samples, respectively, and report the final test error the unseen test set (10K samples).
K.3 Supplementary search results
Choice of search strategies We only ran experiments using BOHNAS, RS, RE, and NASBOWL. We did not ran experiments using AREA since zero-cost proxy specifically uses the binary codes of the ReLU non-linearity. We did not ran NASBOT since it already performed poorly the hierarchical NAS-Bench-201 search space.
Search costs The search cost
5 GPU days using eight asynchronous workers, each with an NVIDIA RTX 2080 Ti GPU, for ca. 40 GPU days in total.
Best found activation function Our best found activation function for ResNet-20 is follows:
3(a(=z) min(z, 0)) + (1 (miim(mmax(, 0), erf x))
(35)
46

---

2.0
ReLU
1.3
Sigmoid
1.0
GHLU
Swish
8 0.5
0.5
1
(a) Best found activation function.
(b) Common activation functions.
Figure 15: Visualization of our best found activation function (see Equation 35) for different values of the trainable parameter (left) and common activation function from the literature (right).
Figure 15 visualizes and compares the found activation function with common activation functions from the literature. The found activation function a weighted mixture of the sigmoid function and ReLU non-linearity.
L Searching for convolutional cells in the DARTS search space
While our main focus is to go beyond cell-based search spaces in this work, we also demonstrate that our proposed search strategy BOHNAS works in popular cell-based search spaces, e.g., cell-based NAS-Bench-22 201 [58] in Section 6. In addition, we also evaluated BOHNAS the popular DARTS search space [6]. The DARTS search space definition provided Equation 13 (Appendix F). Following Ru et al. [48], we used the ENAS-style node-attributed DAG representation to apply the WL graph kernel on the normal or reduction cells, respectively.
L.1 Implementation details
In contrast to all other experiments, we set the crossover probability to Peross = 0.0 (and consequently Pmut = 1.0), Schneider et al. [107] showed the importance of mutation" for the performance of BANANAS [47] on NAS-Bench-301 (surrogate benchmark of the DARTS search space, Zela et al. (108)).
L.2 Training details
Search settings Following Liu al. [6], we split the CIFAR-IO training dataset into train and validation set with 25k samples each. We trained a small network with 8 cells for 50 epochs, with batch size 64 and the initial number of channels 16. We used SGD with learning rate of 0.025 with cosine annealing Loshchilov and Hutter [96], momentum of 0.9, and weight decay of 0.0003. Since the validation performance on CIFAR-10 very volatile, we averaged the final validation errors, following Ru et al. [48]. In contrast to previous works, we picked the best normal and reduction cells based on the validation performance from the different search runs with random seeds (666, 777, 888, 999}. and did not pick the cell-based on its validation performance by training from scratch, e.g., for short period 100 epochs [6].
Retrain settings Following Liu et al. [6], we retrained the a large network with cells for 600 epochs with batch size 96. The initial channels were to 36. Other hyperparameters used during search. We also applied cutout and auxiliary towers with weight 0.4. Following Chen et al. [45], set the path dropout probability to 0.3 (instead of 0.2). We used the entire CIFAR-10 10 training set (50k samples) for training and report the final accuracy on the test set (10k samples). We evaluated the architecture with discovered normal and reduction cells for the same random seeds used for search. We additionally also retrained the reported architectures of NASBOWL [48],
same as
'In their implementation only the incumbent is mutated, whereas we still ran evolution over multiple steps to remain consistent across experiments.
47

---

Skip comnect
dil CoNv 5x.5
cep_coev__333 3K3
c_(k-2)
skip connect
sep_
c_ [k-21
conv__id
sep_couvv_ 3x3
<_(k]
3x3
(k)
skip
_5x
agg. pool 3x3
sep_conv 5x55
(k-1)
skip comnect
sep_conv_St5
and pool 3x3
(a) Normal cell.
(b) Reduction cell.
Figure 16: Normal and reduction cells discovered by BOHNAS the DARTS search space CIFAR-10.
DrNAS [45], and Shapley-NAS [89] to reduce effects of possible confounding factors such as choice of random seeds, software versions, hardware, etc.
To assess the transferability of our found normal and reduction cell on CIFAR- 10, we trained the best cell on ImageNet following the mobile setting by Liu al. [6]. where the input image size 224 x24 and the number of multiply-add operations is restricted to be less than 600 M. For training, we used the same random seeds used for search on CIFAR-10. Due the high training cost, we omitted retraining of reported cells of prior works.
L.3 Search results
Search costs We ran search with eight asynchronous workers, each with an NVIDIA RTX 2080 Ti GPU, for exactly 1 GPU day, resulting total search cost GPU days. Note that by using the extensive parallel computing power available in today's 's computing clusters, the wallclock time for search day) is comparable that of ttate-of-the-ar gradient-based methods. Retraining on 10/aaeet required ca. 1.5/5 GPU days single/eight NVIDIA RTX 2080 Ti GPU(s).
Figure 16 shows the best found normal and reduction cell. Table 9 shows that BOHNAS can find well-performing normal and reduction cells that are on-par or (mostly) superior to other sample-based search strategies. The discovered normal and reduction cells are also competitive with state-of-the-au gradient-based methods, which are (typically) optimized for this particular search space.
CIFAR-10 Results
ImageNet results Table 10 shows that BOHNAS achieves competitive (or superior) results with 24.55 % and 7.4 % average top-1 top-5 test error, respectively. This shows the transferability of the found normal and reduction cells by BOHNAS. The discovered normal and reduction cells are also superior state-of-the-art art gradient- based methods in the transfer setting", which are actually optimized for this particular search space since successive works target the DARTS search space. BOHNAS is only inferior gradient-based methods that searched for the cells ImageNet.
M Searching for transformers for generative language modeling and sentiment analysis
To demonstrate that approach is also applicable to diverse architecture types and tasks, we searched for transformers for language modeling (nanoGPT experiment) as well as sentiment analysis.
Note that for fair comparison, compare only reproduced numbers to avoid confounding factors.
48

---

Table 9: Comparison with state-of-the-arg art image classifiers on CIFAR-10 on the DARTS search
space.
Avg. val error
Avg. test
Best
Params M
Search cost
Search strategy
Type
[%]]
[%]
[%]
GPU days]
RS with early stopping
ASHA [109]
3.03 + 0.13
2.85
4.6
Random-WS WS [7]
RS
2.85 + 0.08
2.71
4.3
ENAS" [43]
RI.
2.89
4.6
AmocbaNet-A [12]
evolution
3.34 = 0.06
3.2
3150
AmocbaNet-B [12]
evolution
2.55 = 0.05
2.8
3150
GP-NAS [1]0]]
BO
3.79
3.9
BANANAS [47]
BO
2.64
2.57
BONAS-C [52]
2.46
3,48
BONAS-D [52]
BO
2.43
3.3
NASBOWL [48]
BO
2.61 0.08
2.50
3.7
NASBOWL [48]
BO
11.84 + 0.15
2.93 + 0.1
2.83
3.7
N/A
DARTS (v2) [6]
gradient
2.76 0.09
3.3
4
GDAS [58]
gradient
2.93
3.4
0.3
DrNAS [45]
gradient
2.46 = 0.03
4.1
0.6
DrNASt [45]
gradient
12.19 + 0.06
2.63 + 0.09
2.51
4.1
N/A
Shapley-NAS [89]
gradient
2.47 - 0.04
2.43
3,4/3.6
0.3
Shapley-NAS' [89]
gradient
12.35 0.22
3.09 0.07
2.97
3.6
N/A
BOHNAS
BО
11.27 + 0.16
2.68 = 0.12
2.55
3.9
expanded search space from DARTS. reproduced results using the reported genotypes. not reported.
M.1 Training details
nanoGPT We followed the training protocol for Shakespearean works [98] of Karpathy [68] to train character-based language model. Specifically, trained the networks for 5000 iterations with batch size 64 with 100 warmup iterations and AdamW optimizer [96] with learning rate of 0,001, weight decay of 0. 31 of 0.9, and 32 of 0.95 with decaying learning rate schedule. We equally split the data into training and validation data. The vocabulary is of size of 65, We set the block size to 256 and used a dropout rate of 0.2.
Sentiment analysis For sentiment analysis on IMDb [99], we used a frozen BERT encoder [117] and searched for classifier head (see Appendix M.2 for details). We trained the classifier head for five epochs with a batch size 128 with the Adam optimizer with learning rate of 0.001, 31 of 0.9, and B2 of 0.999, We used dropout rate of 0.25 and hidden dimensionality of 256.
M.2 Search space definitions
nanoGPT We constructed the search space around the default transformer architecture of Karpathy [68], excluding the embedding layers and the final couple of layers (layer normalization followed by a linear layer) for simplicity. The search space is defindd as follows:
Sequential3(1_ I., I.) Sequential2(1, L. Residual2[[, L., I.)
:: Sequential2(T, T) Sequentia13(T, T, T) Residual2(T, T, T)
: TransfornerrBooc((HHEAAD MLPRATIO, ACT)
(36)
NHEADS = 6
4
MIPRATIO 4
2
ACT gelu
relu
silu
Additionally. we searched for the embedding dimensionality {96, 192, 384]. However, since the embedding dimensionality acts globally on architecture, we treated as a categorical hyperpa- rameter. To this end, we combined our hierarchical graph kernel (hWL.) with Hamming kernel in our search strategy, BOHNAS. This shows that both our search space design framework as well as search strategy, BOHNAS, can also be used for joint NAS and hyperparameter optimization.
49

---

Table 10: Comparison with state-of ofttc----hherrrr art image classifiers on ImageNet in the mobile setting on the DARTS search space. We reproduced results for DrNAS [45] and ShapleyNAS [89] using the reported genotype on one seed (777).
Top-1 test emorr
Top-5 test emor
Params
Search cost
Search strategy
Type
[8]
[%]
[M]
[GPU days]
Inception-v1 [111]
manual
30.1
10.1
N/A
MobileNet [112]
manual
29.4
N/A
ShuffleNet 2x (v1) [113]
manual
26.4
10.2
N/A
ShufficNct (v1) [114]
manual
25.1
N/A
NASNet-A [23]
RI.
26.0
8.4
2000
AmoebalNet-C(11]
evolution
24.3
3150
PNAS [115]
BO
25.8
8.1
255
BONAS-C [52]
BO
24.6
7.5
5.1
7.5
BONAS-D [52]
Bо
25.4
8.0
4.8
10
MnasNet-92 [55]
RI
25.2
8.0
4,4
Random- WS [7]
RS
25.3 1. 0.25
92.2 1 0.15
5.6 1 0.1
DARTS (v2) [6]
gradient
26.7
8.7
4.7
GDAS [58]
gradient
26.0
8.5
5,3
0.3
PC-DARTS [116]
gradieut
25.1
7.8
3.6
0.1
P-DARTS' [116]
gradient
24.6
7,5
4.9
N/A
P-DARTS [1]6]
gradient
24.4
7.4
4.9
0.3
DrNAS [45]
gradient
24.3
7.4
5.7
N/A
DrNAS [45]
gradient
23.7
7.1
5.7
4.6
Shaplcy-NAS' [89]
gradient
24.9
7.6
5.1
N/A
Shapley-NAS [89]
gradient
24.3
7.6
5.1
0.3
Shapley-NAS" [89]
gradient
25.0
7.6
5.4
N/A
Shapley-NAS [89]
gradient
23.9
4.2
BOHNAS
BO
24.55 + 0.03
7.44 + 0.04
5.4
8
BOHNAS (best)
BO
24.48
7.3
5.4
8
search run on ImageNet, otherwise CIFAR-10. reproduced results using reported genolypes. not reported.
r(4.2,relu)
T(4,3,silu)
148,2,relu)
T(8,3,
T(6.2,
T(6,4,relu)
T(4,4,relu)
I(4,3,
T(8.2,gelu)
Figure 17:
Best found transformer architecture (excluding embedding layers and final few layers) with an embedding dimensionality of 192 for the nanoGPT experiment.
Sentiment analysis We searched for classifier head on top of the BERT encoder [117] followed by linear projection. Specifically, we define the search space follows:
CELL : CePS, OPS, OPS, OPS, OPS, OPS)
(37)
OPS : id zero
transformer gru
mlp
where the topological operator (CELL) corresponds to densely four node DAG (similar to the NAS-Bench-201 cell-based search space [58]), and transformer, gru, and mlp are transformer block, GRU unit, or two-layer MLP with GeLU non-linearity, respectively. We feed the output of the searched classifier cell into GRU unit followed by dropout (with rate of 0.25) and final linear layer.
M.3 Search results
Search cost We searched with eight asynchronous workers, each with an NVIDIA RTX 2080 Ti GPU, for exactly 1 GPU day, resulting in a total search cost of 8 GPU days.
Found transformer and classifier head We depict the found transformer for the nanoGPT experi- ment in Figure 17. Figure 18 depicts the found classifier head for sentiment analysis.
50

---

id
1d
transformer
id gru
id
Figure 18: Found classifier head for the sentiment analysis experiment.
Best practices checklist for NAS research
NAS research has faced challenges with reproducibility and fair empirical comparisons for a long time [109, 118]. In order to promote fair and reproducible NAS research, Lindauer and Hutter [13] created best practices checklist for NAS research. Below, we address all points on the checklist.
1. Best Practices for Releasing Code
(a) Did you release code for the training pipeline used to evaluate the final architectures?, Did you release code for the search space?, Did you re- lease code for your NAS method? [Yes] All code can be found at https://github com/ aataaautomlhiiaa /atttmm//ieearccicaal.mmmm wwwerrrcccllaaaas carraal_ans_conssutciiioo
(b) Did you release the hyperparameters used for the final evaluation pipeline, as well as random seeds? [Yes] We provide experimental details (including hyperparameters. as well as random seeds) in Section Appendices 1. K.2, L.2 and M.1.
(c)
Did you release hyperparumeters for your NAS method, as well as random seeds? [Yes] We discuss implementation details (including hyperparameters well as random seeds) of our NAS method in Section 6, Appendices I, L.1 and M.2.
2. Best practices for comparing NAS methods
(a) For all NAS methods you compare, did you use exactly the same NAS benchmark, including the same dataset (with the same training-test split), search space and code for training the architectures and hyperparameters for that code? [Yes] We always used the same training pipelines during search and final evaluation.
(b) Did you control for confounding factors (disferent hardware, versions of deep learning libraries, different runtimes for the different methods)? [Yes] We kept hardware, software versions, and runtimes fixed across our experiments to reduce effects of confounding factors.
(c) Did you ablation studies? [Yes] We compared different kernels (hWL, WL, NASBOT, and GCN) and investigated the surrogate performance in Section 6. We also analyzed the distribution of architectures during search, impact of the flexible parameterization of the convolutional blocks, test error vs. number of parameters and FLOPs Appendix J.3.
(d) Did you use the same evaluation protocol for the methods being compared? [Yes] (c) Did you compare performance over time? [Yes] We plotted results over the number of iterations, typically done for black-box optimizers, and report the total search cost in Appendices J.3, K.3, L.3 and M.3. For the activation function search, DARTS cell search, and transformer-batt this is typically not done for these experiments.
searches, did not compare performance over time, as
(f) Did you compare to random search? [Yes]
(g) Did you perform multiple rums of your experiments and report seeds? [Yes] We ran all search runs on the hierarchical or cell-based NAS-Bench-201 over three seeds, the search run for activation function for one seed, the search on the DARTS search space on four seeds, transformer searches for one seed, and surrogate regression experiments over 20 seeds. All seeds are reported.
(h) Did you tabular surrogate benchmarks for in-depth evaluations? [N/A] At the time of this work, there existed no surrogate benchmark for hierarchical NAS.
51

---

3. Best practices for reporting important details
(a) Did you report how you tuned hyperparumeters, and what time and resources this required? [N/A] We have not tuned any hyperparameter.
(b) Did you report the time for the entire end-to-end NAS method (rather than, e.g., only for the search phase? [Yes]] We report search times in Appendices J.3, K.3, L.3 and M.3. For the hierarchical WAS-Bench-220 experiments, the training protocols are exactly the same for the search and final evaluation (except for CIFAR-IO) 10), and, thus, there are no additional costs for final evaluation. For the activation function search experiment, we used the same training protocol for training and evaluation. For the DARTS experiment, we re-trained the discretized architecture on CIFAR- 10/ImageNet which required ca. 1.5/5 GPU days single/eight NVIDIA RTX 2080 Ti GPU(s). For the nanoGPT experiment, we report the final error on the given validation set. For the sentiment analysis experiment,
used the same training and evaluation protocol.
(c) Did you report all the details of your experimental setup? [Yes] We report all experi- mental details in Section 6, Appendices J.1, K.2, L.I, L.2 and M.1.
52


Reviews:
[{"review_id": "TJ96Jq32Lb", "reviewer": "Reviewer_sktw", "summary": "The authors propose an approach to unify the search space for Neural Architecture Search (NAS) using context-free grammars. They further develop a Bayesian Optimization based search strategy to effectively explore a huge search space. They experiment over (proposed) hierarchical extension of NAS-Bench 201 benchmark to demonstrate sound improvements.\n\n", "questions": "See above", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Hierarchical search space design allows exploration of more controlled and viable architectures. While prior works mostly explored cell-based search, or require post-hoc checking, the authors develop a principled solution for macro to micro search using context-free grammars (CFG).\n\nIn order to demonstrate their search granularity, the authors propose a hierarchical extension to NAS-Bench 201, and subsequently perform most of the experiments in the modified benchmark. The paper would benefit from also highlighting these results on the original NAS-Bench 201 benchmark to understand how the granularity of the search space impacts the different search methods in the traditional benchmark.\n\nIn the modified hierarchical benchmark, the authors demonstrate strong performance improvements against several baseline methods. In Table 1, the authors contrast their search strategy against existing search strategies on multiple dimensions. ", "weaknesses": "1. While BOHNAS in general works well across multiple settings and outperforms several baselines, they do have limited gains when compared against DARTS and NASBOWL.\n2. All the experiments and benchmarks in the paper focus on Conv based search spaces. Given that a lot of recent works, primarily on language models, focus on Transformer search spaces, a related discussion would be useful for the readers.\n3. It will be nice to have results on larger datasets including the full ImageNet.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review. We are happy that the reviewer views our approach as a “principled solution for macro to micro search” and that it “allows exploration of more controlled and viable architectures”. \n\nBy following the reviewer’s suggestion, we additionally conducted experiments on transformer-based search spaces to showcase the general applicability and versatility of our proposed search space design. Please refer to our general response for more details.\n\nBelow, we address the remaining questions and criticisms of the reviewer.\n\n> Comparisons across various search space granularities, including the original cell-based NAS-Bench-201 benchmark\n\nThis is indeed an interesting question that we investigated in Figure 3 of the paper. In this experiment, we compared various search spaces (including the original NAS-Bench-201 benchmark (fixed+shared)) across various datasets using BOHNAS. The results show that we can indeed find better-performing architectures in hierarchical search spaces compared to, e.g., cell-based search spaces (such as the original NAS-Bench-201 search space). Figure 13 in the supplement complements this experiment by using other search methods (RS, RE, & NASBOWL) with similar results. While this experiment is an initial step toward better understanding the effects of search space granularities, we believe that this is a promising direction for future works to explore further.\n\n> Performance gains of BOHNAS beyond cell-based search spaces\n\nWe would like to highlight that our proposed search strategy, BOHNAS, clearly outperforms NASBOWL on hierarchical search spaces (e.g., see Figure 2 of the main paper). DARTS is not (yet?) even applicable to such vast hierarchical search spaces since the expressive hierarchical search spaces would yield an exponential number of weights (please refer to Appendix C for an extensive discussion). However, we acknowledge that in search spaces with fewer or no hierarchical levels (e.g., the DARTS search space), BOHNAS only yields architectures with smaller performance gains, but importantly not inferior ones (see Table 1 of the main paper).\n\n> Results on larger datasets including the full ImageNet\n\nWe acknowledge that we currently do not have ImageNet results besides on the DARTS search space (please refer to Table 10 in the supplement). We would like to note that our approach is independent of the target task or data modality (also please refer to our general response). Given our presented results, we expect similar results on larger datasets but we do not have access to sufficiently large compute resources to train multiple neural networks that are competitive for ImageNet in the non-mobile setting. "}, {"review_id": "gLuJbsOCIl", "reviewer": "Reviewer_gqtA", "summary": "This paper uses context-free grammar to improve the efficiency of neural architecture search. Experiments show that the proposed approach outperforms existing methods. ", "questions": "N/A", "limitations": "The authors have discussed the limitation of this paper: while adopting CFGs may limit the search space to context-free languages, empirical results have demonstrated effectiveness of the proposed approach. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Simple, well-motivated and efficient approach to improve neural architecture search. \n- Clear presentation. ", "weaknesses": "No major weakness found, though the improvement presented in Table 2 seemed marginal. \nIn addition, as the authors discussed in Section 7, the expressiveness of CFGs are limited to context-free languages, which may exclude the optimal architecture. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our work. We are glad that the reviewer finds our approach “simple, well-motivated and efficient”. Below, we address an interesting point raised by the reviewer in more detail.\n\n> Exclusion of the optimal architecture from the search space (as discussed started discussing in Section 7 of the main paper)\n\nThis is indeed a great point, since the search space always defines the upper bound of the best-performing architecture we can find for a certain task. This is true for all types of search spaces, including our hierarchical search spaces based on context-free grammars, except for global search spaces, where we could indeed search over all architectures. However, search costs may be much higher, e.g., there are many architectures with poor performance, while the best-performing architectures may be only found in tiny subsets of the entire search space. Adding to the aforementioned, we would like to note that even if we ensure that the optimal architecture could be found hypothetically, there is no guarantee that any search strategy is able to actually find it with a limited computational budget."}, {"review_id": "rTqA0Tza1T", "reviewer": "Reviewer_Q2bD", "summary": "The authors propose improvements to several parts of the neural architecture search (NAS) pipeline. First, they introduce a methodology for specifying search spaces based on a combinator grammar that is both more flexible than previous structured search spaces and encourages more regularity and hierarchy than previous unstructured ones. They show that this methodology allows them to represent all search spaces they’re aware of from the literature, and extend them in ways that are likely to be helpful. Then they describe a method for searching these spaces using Bayesian optimization with a multiscale graph kernel and evolutionary operations, and show that this method achieves better results on existing search spaces (e.g., NAS-Bench-201 and DARTS) and even better results on hierarchical extensions of these search spaces (hierarchical NAS-Bench-201).", "questions": "How far are we from “architectures from the book”? Was anything surprising about the architectural structures your method discovered? You mention some architecture search spaces that can’t be covered with a CFG (can you give an example?); are any important architecture classes locked out because of these search spaces?", "limitations": "The authors adequately cover the limitations of their techniques. Two that particularly stood out to me are that the work assumes a computer vision/convnet context (e.g. special case handling of downsampling, no non-image-classification benchmarks) and lacks support for weight sharing.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The authors introduce good ideas and report strong results. They explicate and carefully follow NAS best practices, and use relatively little compute (only consumer GPUs!) while fostering reproducibility. Relative to a somewhat crowded field, the paper stands out as both careful and “obvious in retrospect”.", "weaknesses": "The work is somewhat sprawling and can’t go into enough depth on some of the most interesting parts; e.g. the constraints section that explains that the CFG isn’t actually context-free is one paragraph long in the main paper, and all full network examples are in the appendix. Overall I have to put a lot of work in to understand where your advances fit in the big picture, and exactly what parts contribute to improved results. It also feels a bit like the last hurrah of a somewhat fading subfield (both convnet architecture optimization and convnet-focused NAS are perhaps a bit tapped out).\nA notational nit I have is that Residual(a, b, c) is a confusing way to write a structure where b is the residual for a and c. Is there any particular reason for this choice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the thorough review and thoughtful raised questions. We are glad that the reviewer finds that our “paper stands out as both careful and ‘obvious in retrospect’”. We are very happy that the reviewer acknowledges our “strong results”, while using “relatively little compute (only consumer GPUs!)”. We are pleased that the reviewer appreciates our efforts to foster reproducibility by “explicat[ing] and carefully follow[ing] NAS best practices”.\n\nBy following the reviewer’s suggestions, we were able to demonstrate the generality beyond the, arguably “fading subfield” of conv-based NAS as well as vision tasks (“works assumes [...] vision/convnet context”) by conducting experiments on two transformer-based search spaces on text (generative language modeling and sentiment analysis). Please refer to our general response for more details.\n\nBelow, we address the reviewer’s remaining questions and concerns.\n\n> “How far are we from ‘architectures from [scratch]’?”\n\nThis is indeed a very interesting question! We believe that our work is one step closer toward searching for architectures from scratch by opening up search spaces to a broader spectrum of architectures. Nevertheless, there are several challenges for the NAS community working towards this goal. For example, the sheer size makes the search significantly more complex. Thus, we need to improve our search strategies in terms of efficiency or try to incorporate user priors to help kick-start the search process. A fruitful direction for future works could be to incorporate ideas from, e.g., multi-fidelity optimization or meta-learning. Besides the increased search complexity, search space design also is more challenging, e.g., how do we ensure that there are no shape mismatches. While our work proposes some techniques to remedy such difficulties in the search space design, there may be several more such challenges left to be solved in future works.\n\n> “Was anything surprising about the architectural structures your method discovered?”\n\nA surprising observation was that architectures with various branches at the macro-level often performed as well as or better than architectures with the common design of chaining similar layers or blocks (e.g., transformer or residual blocks) one after another. This prompts us (at least the authors of this work) to rethink the macro architectural design choices (for NAS) that we all adopted over the last decade; except for a couple of notable recent exceptions [1,2]. We were also genuinely surprised that different activation functions or normalizations throughout the architecture could work together and not lead to training instabilities or the like.\n\n> “You mention some architecture search spaces that can’t be covered with a CFG (can you give an example?)”\n\nIn principle, all search spaces could be covered by *some* CFG, but there is *not one* CFG that can cover all architectures. To give an example, consider architectures of the form $a^n b^n c^n$, where a, b, and c are some layers (e.g., a is a convolution, b is a transformer block, c is an MLP), each repeated n times. For example, for n=2 we would have aabbcc. However, through the pumping lemma for context-free languages [3], we can show that no single context-free grammar can construct all architectures of the form $a^n b^n c^n$. \n\n> “Lacks support for weight sharing”\n\nYes, we acknowledge that our current implementation does not support weight sharing. The main reason is that current weight-sharing approaches do not scale to large hierarchical search spaces, i.e., their supernet would require an exponential number of weights. Please refer to Appendix C for a more extensive discussion.\n\n> “The work is somewhat sprawling and can’t go into enough depth”\n\nWe make the points raised by the reviewer clearer and more clearly emphasize how our advances fit into the bigger picture in the revised manuscript.\n\nRegarding the notation of topological operators (e.g., Residual(a, b, c)): we associate edges with the arguments and order the arguments first by the sink nodes of each edge and then by the source node (if multiple edges have the same sink node). For Residual, we have the edges (1,2), (1,3), & (2,3), and thus b is the residual connection in our case. However, we are willing to change this scheme if the reviewer thinks there is some other more intuitive scheme.\n\n[1] Goyal, Ankit, et al. \"Non-deep networks.\" NeurIPS 2022.\n\n[2] Touvron, Hugo, et al. \"Three things everyone should know about vision transformers.\" ECCV 2022.\n\n[3] Bar-Hillel, Y.; Micha Perles; Eli Shamir (1961). \"On formal properties of simple phrase-structure grammars\"."}, {"review_id": "xoIGJjVqkF", "reviewer": "Reviewer_mjYa", "summary": "In this paper, the authors focus on the search space issue in neural architecture search and propose a unifying search space design framework that models all candidate neural structures with context-free grammars. This approach enlarges the search space, which is more likely to find high-performance architectures, and meanwhile does not bring much search cost with the proposed Bayesian Optimization for hierarchical NAS. Experimental results show that systems with hierarchical search spaces outperform the previous NAS systems.", "questions": "Context-free grammars can well organize the search space and use clear rules to define a large search space, but what are the advantages of this approach for NAS? Although its search space has enlarged, a larger search space still requires more efficient search strategies to balance the search cost. What are the differences between your method and other previous work to expand the search space? For example, what is the main property of context-free grammars you think can help in NAS?", "limitations": "The authors have adequately addressed the limitations and discussed them in Section 7.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The issue that this article focuses on is precious. The search space is an important issue for NAS, and somewhat determines the upper bound of performance of the resulting system. The limited search space will make the system difficult to find a proper neural structure. The authors notice this problem and propose a new method to enlarge the space without much more search cost, which makes the approach more useful.  \n2. The proposed method is novel. There have already been some studies on NAS trying to introduce larger search space, but most are model specific. However, in this paper, the authors apply context-free grammars to model the search space, which is interesting and new. It’s easy for users to compose a considerable search space by allowing further derivations of the function composition. \n3. The hierarchical search space is compatible with previous NAS methods. \n4. The paper is well-written. The figures and descriptions are clear. It’s easy for readers, even researchers not in this area, to understand the main idea of this paper.\n", "weaknesses": "1. In the proposed hierarchical search space, it’s more complicated to design a search space because the space must be described in context-free grammars, which is a little bit difficult. Does it take a lot of experience to design a search space based on context-free grammars for tasks? If one wants to apply this method in some other tasks, such as natural language processing or speech processing, can this method be easily used? Are there any suggestions for designing grammar? I suggest the authors clarify these issues in the next version. \n\n2. A related problem, which I think is important, is that the authors restrict the discussion to fixed-length problems. It is not obvious how the method is applied to variable-length problems, such as those in NLP. I guess the problem would be much different if we deal with a sequence of variable length, but it is often the case in recent LLMs.\n\n3. The use of CFG often leads to a compact representation of exponentially many structures. In this sense, the method discussed here is similar to methods that make use of compact data structures, such as DARTS. The advantage of using CFGs is that the method is itself well explained and training CFG-based systems has long been studied. On the other hand, this makes the work have overlap with previous work. \n\n4. Pruning is generally used in CFG-based systems. But it is not covered in this work. This is not a concern but a possible improvement to current work.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the encouraging comments and thoughtful questions. We are very happy that the reviewer finds our work “precious” and “easy for readers, even researchers not in this area, to understand the main idea of this paper.”\n\nBy following the reviewer’s suggestion, we were able to demonstrate that our search space design framework can also easily be used also for “variable-length problems, such as those in NLP” by conducting experiments on two transformer-based search spaces on text (generative language modeling & sentiment analysis). Please refer to our general response for more details.\n\nWe address the remaining questions and concerns below.\n\n> Differences to previous works on compact search space representations\n\nWe acknowledge that there is some degree of overlap with previous methods that proposed compact search space representations. Nevertheless, we would like to point out some key differences from our work to previous works. Most importantly, our search space design allows searching over all parts of the architecture, from micro-level choices, such as which activation function to use for each layer, to macro-level choices. Previous works either considered only one of these, searched only for a confined set of macro topologies (e.g., only linear macro topologies), or required post-hoc validation procedures (e.g., checking for shape mismatches and fixing them). In contrast, our approach always generates valid entire architectures (according to the context-free grammar (CFG)). In addition, our approach supports the incorporation of user-defined architectural constraints as well as can effectively foster regularity. We provide a comparison of various search space design techniques in Table 4 in the supplement.\n\n> “What are the advantages of this approach for NAS?”; “What is the main property of context-free grammars you think can help in NAS?”\n\nAdding to the points mentioned above, we believe that CFGs provide a very formal way of treating search spaces and the NAS community could benefit from integrating ideas from the thoroughly studied field of grammars. Since CFGs generate and manipulate architectures in the text space, it also opens avenues of treating architectures not only as graphs but as strings; thereby enabling, e.g., the application of string kernels or potentially even providing an interface to leverage recent generative LLMs for architecture search.\n\n> “Does it take a lot of experience to design a search space based on context-free grammars [...]?”\n\nThere will certainly be some familiarization time. Nevertheless, we are confident that researchers as well as practitioners alike will quickly get used to the search space design based on CFGs. To facilitate adaptation, we additionally provide a \"Python\" interface for designing CFGs without the requirement to get into the notational details of the extended Backus-Naur form [1].\n\n> “Are there any suggestions for designing grammar[s]?”\n\nThe design of a CFG depends on the target task. That is, an image-based task may require a different design than a text-based task. The CFGs shown in our work can be a first step to get a better idea/inspiration for the own design of such a CFG.\n\nIn general, when looking for high-performing architectures for a given task, we would always recommend reviewing the relevant literature and consulting domain experts if one is not particularly familiar with the application domain. In particular, we recommend distilling commonalities and differences among architectures that form the basis of the design for the CFG. Starting from this basis, we recommend expanding the search space by adding more and more production rules to the CFG to allow for the exploration of interesting novel architectures. This process of designing a CFG, especially in the beginning, may take some trial and error to get \"right\" but from our experience, it becomes easier with time. We will add to the revised manuscript a best practice guide for CFG design for NAS search spaces for researchers and practitioners alike.\n\n> “Pruning is generally used in CFG-based systems.”\n\nThanks, this is indeed an interesting idea and could be a fruitful direction for future work!\n\n[1] JW, Backus. \"The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference.\" International Conference on Information Processing 1959."}]

Author rebuttal:
We thank all the reviewers for their thorough review, thoughtful questions, and constructive criticisms. We are very glad to hear that reviewers find that our work is “precious” (mjYa), “principled” (sktw), “simple, well-motivated and efficient” (gqtA), as well as “stands out as both careful and ‘obvious in retrospect’” (Q2bD).

Two shared questions and concerns among reviewers (sktw, Q2bD, mjYa) are whether our search space design can also be applied to (i) transformer-based search spaces and (ii) non-vision tasks. 

To answer these in the affirmative, we conducted two NLP experiments to search for (1.) a GPT-like transformer for generative language modeling and (2.) a classifier head on top of a frozen BERT encoder for sentiment analysis. These experiments further show the generality and versatility of our proposed search space design framework. Additionally, the nanoGPT experiment (1.) shows that both our search space design framework as well as search strategy, BOHNAS, can be used for joint NAS & HPO. We will include these experiments in our revised manuscript.

## 1. Searching for a transformer for generative language modeling

For this experiment, we searched for a transformer (excluding the embedding layers and the final few layers for simplicity) based on Andrej Karpathy’s nanoGPT for Shakespearean works [1]. Similar to our other experiments, we used 8 asynchronous workers (each with an NVIDIA RTX 2080 Ti GPU) for one day. We define the context-free grammar for this search space as follows:

```
S::= Sequential3(L, L, L)  |  Sequential2(L, L)  |  Residual2(L, L, L)
L ::= Sequential2(T, T)  |  Sequential3(T, T, T)  |  Residual2(T, T, T)
T ::= TransformerBlock(NHEADS, MLPRATIO, ACT)
HEADS ::= 6  |  4  |  8
MLPRATIO ::= 4  |  2  |  3
ACT ::= gelu  |  relu  |  silu     ,
```
where the topological operators (Sequential3, Sequential2, Residual2) are similarly defined as in our other experiments from our work. The operator TransformerBlock corresponds to the basic transformer block commonly used in transformers and is parameterized by the number of heads (NHEADS), MLP ratio (MLPRATIO), and activation function (ACT).

We additionally searched for the embedding dimensionality {96, 192, 384}. However, since the embedding dimensionality acts globally on the architecture, we treated it as a categorical hyperparameter. To this end, we combined our hierarchical graph kernel (hWL) with a Hamming kernel in our search strategy, BOHNAS.

Our search yielded a transformer with the best validation loss of 1.4386 with only 3.33M parameters. For comparison, Andrej Karpathy reported a best validation loss of 1.4697 with 10.65M parameters for his transformer. We depict the found transformer in Figure 1 of the attached pdf.

Future work could scale up the search (in terms of the search space, training data, model scale, training compute, and/or search compute) to find even more powerful, general-purpose generative LLMs.

## 2. Searching for the classifier head of a frozen BERT encoder for sentiment analysis

For this experiment, we used a frozen BERT encoder and searched for a classifier head for sentiment analysis of IMDb movie reviews. We ran the search using 8 asynchronous workers (again, each equipped with an NVIDIA RTX 2080 Ti GPU) for one day. We define the context-free grammar for this search space as follows:

```
S ::= Cell(OPS, OPS, OPS, OPS, OPS, OPS)
OPS ::= id  |  zero  |  transformer  |  gru  |  mlp
```

where the topological operator (Cell) corresponds to the NAS-Bench-201 cell topology, `id` is the identity function, `zero` is the zero function, `transformer` is a typical transformer block, `gru` is a gated recurrent unit (GRU), and `mlp` is a 2-layer MLP that increases and decreases dimensionality (we chose a factor of 2) with GELU activation function. For simplicity, we have omitted the linear projection of the BERT embedding and the final few layers (GRU -> Dropout -> Linear).

Our search yielded a classifier head that achieved a test accuracy of 92.26%. We depict the found classifier head in Figure 2 of the attached PDF. Although this does not achieve state-of-the-art numbers, we would like to note that we conducted this experiment only as proof of concept (e.g., not optimal training pipeline, etc.) and expect improved numbers by adopting more recent training techniques, e.g., further pre-training with additional training data, also finetuning the BERT encoder, hyperparameter tuning, etc.

[1] Karpathy, A. “nanoGPT”. GitHub 2023.

Meta-review: This paper presents a novel and promising approach to Neural Architecture Search (NAS) by introducing a unifying search space design framework based on context-free grammars. The authors demonstrate the effectiveness of their approach by efficiently searching over large and expressive hierarchical search spaces and achieving superior results compared to existing NAS approaches. Overall, this paper is well-written and makes a significant contribution to the field of NAS. The reviewers are positive in the rebuttal period. I recommend to accept this paper.
Decision: Accept (poster)