einspace: Searching for Neural Architectures from Fundamental Operations
Authors: Linus Ericsson
Miguel Espinosa
Chenhongyi Yang
Antreas Antoniou
Amos Storkey
Shay B Cohen
Steven McDonagh
Elliot J. Crowley
Venue: NeurIPS 2024 poster (2024)
Keywords: neural architecture search
nas
deep learning architectures
context-free grammars
cfg
pcfg
neural networks
search space
Primary area: deep_learning_architectures
TL;DR: We introduce an expressive NAS search space, containing diverse SOTA architectures. When searching in this space we find new SOTA and improvements on existing architectures.

Abstract: Neural architecture search (NAS) finds high performing networks for a given task. Yet the results of NAS are fairly prosaic; they did not e.g. create a shift from convolutional structures to transformers. This is not least because the search spaces in NAS often aren’t diverse enough to include such transformations *a priori*. Instead, for NAS to provide greater potential for fundamental design shifts, we need a novel expressive search space design which is built from more fundamental operations. To this end, we introduce `einspace`, a search space based on a parameterised probabilistic context-free grammar. Our space is versatile, supporting architectures of various sizes and complexities, while also containing diverse network operations which allow it to model convolutions, attention components and more. It contains many existing competitive architectures, and provides flexibility for discovering new ones. Using this search space, we perform experiments to find novel architectures as well as improvements on existing ones on the diverse Unseen NAS datasets. We show that competitive architectures can be obtained by searching from scratch, and we consistently find large improvements when initialising the search with strong baselines. We believe that this work is an important advancement towards a transformative NAS paradigm where search space expressivity and strategic search initialisation play key roles.

einspace: Searching for Neural Architectures from Fundamental Operations
Linus Ericsson
Miguel Espinosa' Shay B. Cohen
Chenhongyi Yang' Steven McDonagh'
Antreas Antoniou? Elliot J. Crowley!
Amos Storkey²
School of Engineering
School of Informatics
University of Edinburgh
Project page: http:://hhuuerrrroooooooooooiiip
Code: http:s//ggttau...omm/mmseeeeeeee
Abstract
Neural architecture search (NAS) finds high performing networks for given task. Yet the results of NAS are fairly prosaic; they did not c.g. create a shift from convolu- tional structures transformers. This is not least because the search spaces NAS often aren't 't diverse enough to include such transformations a priori. Instead, for NAS to provide greater potential for fundamental design shifts, need a novel expressive search space design which is built from more fundamental operations. To this end, we introduce einspace, search space based on parameterised probabilistic context- free grammar. Our space is versatile, supporting architectures of various sizes and complexities, while also containing diverse network operations which allow model convolutions, attention components and more. It contains many existing com- petitive architectures, and provides flexibility for discovering new ones. Using this search space, we perform experiments find novel architectures well as improve- ments on existing ones on the diverse Unseen NAS datasets. We show that competi- tive architectures can be obtained by searching from scratch, and we consistently find large improvements when initialising the search with strong baselines. We believe that this work is an important advancement towards transformative NAS paradigm where search space expressivity and strategic search initialisation play key roles.
1 Introduction
The goal of neural architecture search (NAS) 14
to automatically find network architecture for given task, removing the need for expensive human expertise. NAS uses (i) defined search space of all possible architectures that can chosen, and (ii) a algorithm e.g. [68 58
to navigate through the space, selecting the most suitable architecture with respect to search objectives. Despite significant research investment in NAS, with over 1000 papers released since 2020 [59]. manually designed architectures still dominate the landscape. If someone looks through recent deep learning papers, they will most likely come across a (manually designed) transformer (566,, or perhaps (manually designed) MLP-Mixer (53), or even a (manually designed) ResNet [19]. Why isn 't NAS being used instead?
* coius.cricssoneee ed.ac.uk
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

ResNet1a
VIT
MLP-Mixar
Derivation tree
Derivation
Figure I: Three state-of-the arrt architectures and their associated derivation trees within einspace. Top row shows the architectures where the black node is the input tensor and the red is the output. Bottom row shows derivation trees where the top node represents the starting symbol, the grey internal nodes the non-terminals and the leaf nodes the terminal operations. See Section 3.1 for details other node colouring. Best viewed with digital zoom.
Part of the problem is that most NAS search spaces not expressive enough, relying heavily on high-level operations and rigid structures. For example the DARTS [30] search space, each architecture consists of repeating cells; each cell is directed acyclic graph where nodes are hidden
states, and edges are operations drawn from a fixed set of mostly convolutions. This encodes a very specific prior- architectures contain convolutions with multi-scale, filter-like structures (50) maaking it impossible to discover anything beyond ConvNet characteristics. Indeed, random search [63 27 is
often strong baseline in NAS; networks sampled from unexpressive spaces behave very similarly [57
which makes it hard to justify an (often expensive) search.
One solution is to take the nihilo approach to search space construction. In AutoML-Zero [1] the authors create a very expressive search space that composes basic mathematical operations without any additional priors. However, searching through this space is far too expensive for mainstream use, requiring several thousand CPUs across several days to (re)discover simple operations like linear layers and ReLUs. Recent interest in hierarchical search spaces 47 has enabled the study of search across differing architectural granularities which naturally allows for greater flexibility. However, attempts so far have been limited to single architecture families like ConvNets [47 transformers [67). The hybrid search spaces that do exist have limited options both on the operation-level and macro structure [26 61
For NAS to be widely used we need the best of both worlds: search space that is both highly expressive, and in which we can straightforwardly use existing triet-and-tested architectures as powerful priors for search. To this end, we propose einspace: neural architecture search space based on a parameterised probabilistic context-free grammar (CFG). It is highly expressive, able to represent diverse network widths and depths well as macro and micro structures. With its expressivity, the space contains disparate state-of-the -fet----rr--t-tttt architectures such as ResNets [1), transformers [56 13
and the MLP-Mixer [53). shown in Figure T. Other notable architectures contained in einspace are DenseNet 23 WideResNet (WRN) (64), ResMLP [54) and the Vision Permutator 21
We realise our proposed search space through the creation of function-mapping groups that define broad class of fundamental network operations and further describe how such elements can composed into full architectures under the natural recursive capabilities of our CFG. To guarantee the validity of all architectures generated within the expressive space, we first extend our base CFG with parameters that ensure diverse components can be combined into complex structures. Next, we balance the contention between search space flexibility and search space complexity by introducing mild constraints on our search space via branching and symmetry -based priors. Finally, we integrate probabilities into our production rules to further control the complexity of architectures sampled from our space.
To demonstrate the effectiveness of einspace, we perform experiments on the Unseen NAS datasets
diverse classification tasks including vision, language, audio, and chess problems-use using simple random and evolutionary search strategies. We find that in such an expressive search space, the choice of search strategy is important and random search underperforms. When using the powerful priors of blmann-dsiggaa architectures to initialise the search, we consistently find

---

both large performance gains and sigmificant architectural changes. Code to reproduce our experiments available htttt::/ gitbbgttthuu..... www.tttw....mm...o www.loiommmaiiiee csson cssson/iisspacee
Using only simple search strategies, we can still identify competitive architectures, indicating that further refining these strategies in einspace could lead to significant advancements. We hope that this novel perspective on search focusing on expressiveness and incorporating the priors of existing state-of-the-art architectures--bat the potential drive NAS research towards new paradigm.
2
Background
Neural architecture search
The search space used in NAS has significant impact on results 63
65
This has facilitated the need
Early macro design spaces (24 68 made use of naive building blocks while accounting for skip connections and branching
to investigate search space design alongside the actual search algorithms 37
layers. Further design strategies have looked at chain- structurd [3 6 43] cell-based [69] 66 30 [5]
and hierarchical approaches. Hierarchical search spaces have been shown to be expressive and effective in reducing search complexity and methods include factorised approaches [52]. n-level hierarchical
assembly [28] 29 (48, parameterisation of hierarchical random graph generators 445 and topological
evolutionary strategies [35]. Additional work on search spaces have proposed new candidate operations and module designs such as hand-crafted
cells [51], tree-structures [3], shuffle
operations
[32. dynamic modules [22]. activation functions (38] and evolutionary operators [T0. In
AutoML-Zero 41 the authors try to remove human bias from search space construction by defining space of basic mathematical operations as building blocks.
The pioneering work of [4 constructs search spaces using CFGs. We take this direction further and construct einspace as a probabilistic CFG allowing for unbounded derivations, balanced by careful tuning of the branching rate. We aim to strike balance between the level of complexity the search space and incorporating components from diverse state-of-the -frte-r-----attttt architectures. Crucially, our space enables ficxibility in both macro structure and at the individual operation level. While previous search spaces can be instantiated for specific architecture classes (30] [2]. our single space incorporates multiple classes in onc, ConvNets, transformers and MLP-onll architectures. Such hybrid spaces have been explored before (26), but they have been limited in their flexibility, offering only direct choices between convolution and attention operations and disallowing the construction of novel components.
Prominent search strategies employed for NAS include Bayesian optimisation [4 (4|38, reinforcement
learning [66] 68 69 and genetic algorithms 5
popular thread of work, towards improving computational efficiency via amortising training cost, involves the sharing of weights between different architectures via supernet
39 40
Efficiency has been further improved by sampling only subset of supernet channels (60] thus reducing both space exploration redundancies and memory consumption. Alternative routes to mitigating space requirements have considered both architccture and operation-choice pruning 7 [5]. We however highlight that random search often proves to be a very strong baseline (2 63 a consequence of searching within narrow spaces. This is commonly the case for highly engineered search spaces that contain high fraction of strong architectures [59]. Contrasting this, in our e einspace we observe that random search across many tasks performs poorly, underpinning the value of good search strategy for large, diverse search spaces 2
[ 9 18
30
3T.
Context-free grammars
A context-free grammar (CFG; 20 is tuple (N,E, R,S), where N is finite set of non-terminal symbols, V is a finite set of terminal symbols, iss the set of production rules-whers each rule maps non-terminal A E N string of non-terminal or terminals A - (NU and S is the starting symbol. A CFG describes a context-free language, containing all the strings that the CFG can generate. By recursively selecting production, starting with the rules containing the starting symbol, we can gen- erate strings within the grammar. CFGs can be parameterised: each non-terminal in each rule in R, is annotated with parameters Pr. that influence the production. These parameters can condition pro- duction, based on an external state or contextual information, thus extending the power of the grammar.
A probabilistic context-free free grammar (PCFG) associates each production rule with a probability [33 These define the likelihood of selecting a particular rule given a parent non- non-terminal. The assigned probabilities allow for stochastic string generation.
3

---

3 einspace: A Search Space of Fundamental Operations
Our neural architecture search space, einspace introduced here. Based on a parameterised PCFG, it provides an expressive space containing many state-of- offthh--rt neural architectures. We first describe the groups of operations we include in the space, then how macro structures are represented. We then present the CFG that defines the search space and its parameterised and probabilistic extensions.
As running example we will be constructing simple convolutional block with skip connection within einspace, explaining at each stage how it relates to the architecture. The block will consist of convolution, a normalisation and an activation, wrapped inside skip connection.
3.1 Fundamental Operations
Each fundamental operation within einspace takes as input tensor, either passed as input to the whole network or intermediate tensor from previous operation, and operates it further. An operation can be thought of as a layer in a processing pipeline that defines the overall network. The fundamental operations can be separated into four distinct groups of functions that define their role network architecture. The terms one-to-one, one-lo-many and many-lo-one below refer to the number of input and output tensors of the functions within that group. For full details of the operations,
Appendix A.2
Branching. One-to-many functions that direct the flow of information through the network by cloning or splitting tensors. Examples include the branching within self-attention modules into queries, keys and values. In our visualisations, these are coloured yellow.
Aggregation. Many-to-one functions that merge the information from multiple tensors into one. Examples include matrix multiplication, summation and concatenation. In our visualisations, these are coloured purple.
One-to-one functions that change the shape the order of the content in tensor without altering its information. Examples include axis permutations as well as the im2col and col 2im operations. In our visualisations, these are coloured green.
Routing,
Computation. One-to-one functions that alter the information the tensor, either by parameterised operations, normalisation non-linneee non-aiinssssiees. Examples include linear layers, batch norm and activations like ReLU and softmax. In visualisations, these are coloured blue.
(, C, (,ro)))
In our example, the skip connection will be handled by combination of branching and aggregation functions, the convolution decom- posed into the routing functions im2col 1:2colan and col2im, with linear layer from the computation group between them. The normalisa- tion and activation come from the computation group. In the next subsection, we discuss the larger structures of the architecture.
nOTE
rolu
1.4.
[iter)]] sdenttty]l,
15near
clone
add
3.2
Macro Structure
identity
The groups of functions above describe the fundamental operations that make up an architecture. We now describe how these functions are composed in different ways to form larger components.
[. Sncoo1] ]inear]][ colzi4]]
inzcol
linear
colzin
A module is defined takes one input tensor and produces one output tensor, with potential branching inside. A module may contain multiple computation and routing operations, but each branching must paired with a subse- quent aggregation operation. Thus, the whole network can be seen as a module that takes a single tensor as input and outputs single prediction. network module may itself contain multiple modules, directly pertaining to the hierarchical phrase nature of CFG structures. We divide modules into four types, visualised in Figure
composition of functions from above that
I, setten]]]
Figure 2: Visualisation of ex- ample modules with their CFG derivations in bracket notation. From top to bottom; sequential, branching. routing and compu- tation modules.
"The name is inspired by the generality of Einstein summation and the related Python library einops 44 as many of operations be implemented it.

---

Sequential module. A pair of modules and/or functions that are applied to the input tensor sequentially. Using our grammar, defined in Sectior 3.3 this can be produced using the rule MMMMM, or equivalently from the starting symbol S. This also applies to the rules below.
Branching module. A branching function first splits the input into multiple branches. Each branch is processed by some inner set of modules and/or functions. The outputs of all branches are subsequently merged an aggregation function. In the grammar below this can be produced by the rule [M-BBM
Routing module. A routing function applied, followed by a module and/or function. final routing function then processes the output tensor. In the grammar below this is produced by the rule (M (M-PP MRR. R). For more details on the role of the routing module, see Appendix[A.3]
Computation module. This module only contains single function, selected from the one-to-one computation functions described above. While this module is trivial, we will see later how its inclusion is helpful when designing our CFG and its probabilistic extension. In the grammar below this is produced by the rule ( C)
To construct our example, we will be using all four modules. The branching module combines the clone and add functions from before create 2-branch structure. One branch is simple skip connection by using the identity function inside computation module. The other branch is the more complex sequence. The convolutional layer is created by combining im2col, linear and col2im in routing module. The norm and activation are each wrapped in computation module and these are all composed sequential modules. Figure shows similar module instantiations action.
3.3
Search Space as Context-Free Grammar
The following CFG defines our einspace, where uppercase symbols represent non-terminals and lowercase represent terminals. The colours refer to the function groups.
S
M
M
B
M
A
P
M
R
M
+
M
M
B
M
A
P
MAMRO
C,
B
cl one group; add
+
mat matmul
concat, identity im2col permute,
P
+ identity col2im permute,
C identity
linear
norm
relu
softmax
pos-enc.
Our networks are all constructed according to the high-level blueprint: backbone + head where head a predefined module that takes an output feature from the backbone and processes into prediction (see Appendix B for more details). The backbone is thus the section of the network that is generated by the above CFG. When searching for architectures we search across different backbones.
Completing our running example, we present the full derivation of the architecture the CFG in 3
S
M2
A
clone
Mg
M4
C
add
M5
Mg
identity
im2col
C
col2im
C
linear
norm
relu
Figure 3: Example derivation tree of traditional convolutional block with skip connection.
5

---

3.4 Prior Choices
When designing a search space, we must balance the need for w allows more valid architectures to be included-and constraints which reduce the size of the search space. We can view constraints as imposing priors on which architectures we believe are worth including. As discussed, many previous frameworks are too restrictive; therefore, we aim to impose minimal priors, listed below.
Convolutional prior. We design our routing module to enable convolutions to be easily constructed, while also allowing components like patch embeddings and transpose operations. We thus enforce that a routing function followed by another routing function later in the module. Moreover, im2col only appears in the production rule of the first routing function ( P and col2im in the last R ). As shown in Figure construct a convolution, we start from the rule M MMPMMM and derive the following (P im2col (M C linerr) and + col2im)
Branching prior. We also impose a prior on the types of branching that can occur in a network. The branching functions clone and group can each have a branching factor of 2, 4 or 8. For a factor of 2, we allow each inner function to be unique, processing the two branches in potentially different ways. For branching factors of 4 or 8, the inner function M is repeated as is. processing all branches identically (though all inner functions are always initialised with separate parameters). Symbolically, given branching factor of 2 we have ( [BM, Mg A but with branching factor of 4 we have ( BM M₁ M2 M₁ A ) Examples of components instantiated by a branching factor of 2 include skip connections, and for 4, or 8, multi-head attention.
3.5 Feature Mode
Different neural architectures operate on different feature shapes. ConvNets maintain 3D features throughout most of the network while transformers have 2D features. To enable such different types of computations in the same network, we introduce the concept of a mode that affects the shape of our features and which operations are available that point in the network. Before and after each module, we fix the feature tensor to be of one of two specific shapes, depending on which mode we are in.
Im mode. Maintains 3D tensor of shape (C, H, W). where C is the number of channels, H is the height and W is the width. Most convolutional architectures operate in this mode.
Col mode. Maintains 2D tensor of shape (8, D), where S is the sequence length and D is the token dimensionality. This is the mode in which most transformer architectures operate.
The mode is changed by the routing functions im2col and col 2im. Most image datasets will provide inputs in the Im mode, while most tasks that use a language modality will provide it in Col mode.
Our example architecture maintains the mode at almost all stages, apart from inside the routing modules where the im2col function briefly puts us in the Col mode before col2im brings us back.
3.6 Parameterising the Grammar
Due to the relatively weak priors we impose on the search space, sampling a new architecture naively will often lead to invalid networks. For example, the shape of the output tensor of one operation may not match the expected input shape of the next. Alternatively, the branching factor of a branching function may not match the branching factor of its corresponding aggregation function.
We therefore extend the grammar with parameters. Each rule r now has an associated set of parameters (s,m.b) that defines in which situations this rule can occur. When we sample architecture from the grammar, we start by assigning parameter values based on the expected input to the architecture. For example, they might be the input tensor shape, feature mode and branching factor:
(s [3, [3,224,224] m Im,b= 1).
Given this, can continuously infer the current parameters during each stage of sampling by knowing how each operation changes them. When we expand a production rule, we must choose a rule which has matching parameters. If at some point, the sampling algorithm has available valid options, it
NNoe that this is similar but not the same the mode of general tensor, which determines the number of dimensions of that tensor. We use the term mode refer the state that particular part of the architecture is in.

---

will backtrack and change the latest decision until full valid architecture is found. Hence, we ensure that we can sample architectures without risk of obtaining invalid ones.
As an example of this, the CFG rule for was previously
P
identity im2col
permute.
(2)
Enhanced with parameters, this now becomes two rules
P Pmm= Im)
identity
im2col
permute,
(3)
P ((m=Col)
identity permute.
(4)
This signifies that im2col operation is available in the Col mode. Similarly, the available aggregation options depend on the branching factor of the current branching module
A(b=2) 2)
matmul add
concat,
(5)
A(b=4] 4) add concat, concat.
(6)
A(b=8)
add
(7)
3.7 Balancing Architecture Complexity
When sampling an architecture, we construct a decision tree where non-leaf nodes represent decision points and leaf nodes represent architecture operations. In each iteration, either select non-terminal module to expand the architecture and continue sampling, or choose a terminal function to conclude the search at that depth. Continuously selecting modules results in deeper, whereas selecting functions leads to a shallower, simpler network. We can balance this complexity by assigning probabilities our production rules, thereby making PCFG. Recall our CFG rule
complex network,
M - M M
P C).
(8)
If we choose one of the first three options another M to be expanded, but if we choose ( M + C), ), the computation-module, then we will reach terminal function. Thus, balance the depth of our traversal and therefore expected architecture
delving deeper in the search tree since there is yet
complexities, we can set probabilities for each of these rules:
PM + M M). p(M MMM-+MMAM)
P(M->MM|MM) pMM+CC|M)
The value of p(M + C M) is especially important as it can be interpreted as the probability that we will stop extending the search tree at the current location.
Branching rate
p(M C MM 0.31
We could set these probabilities to match what we wish the expected depth architectures to (for empirical re- sults on the architecture complexity, see Table 10 in the Appendix). However, we can actually ensure that the CFG avoids generating infinitely long architecture strings by set- ting the probabilities such that the branching rate of the CFG is less than one [8). For details of how, see Appendix[A.. A.4 So, as shown in Figure 4 we set the computation module probability to pM the other modules to 0.32
Branching rate
1.0-
Super-crtical
sub critical
0.8
0.6
0.0
0.0
0.2
0.4
0.6
0.8
1.0
p(M -
M 0.32 and the probabilities of
Figure 4: To ensure our CFG is consistent and does not generate infinite architec- tures, we make sure the branching rate is in the sub-critical region by setting pM M) 0.31.
For simplicity, all other rule
3
probabilities are uniform.
For thorough example of how sampling performed in einspace, please see Appendix A.1
4 Experiments
4.1
Experimental Details
Datasets
As our search space strives for expressivity and diverse architectures, we adopt a diverse benchmark suite from the recent paper Unseen NAS [16), containing datasets at different difficulties across
7

---

vision, language, audio and further modalities. We run individual searches on these datasets. that are each split into train, validation and test sets. See Appendix for the detailed dataset descriptions.
While Unseen NAS forms the basis of this section, we run additional experiments on the diverse NAS- Bench360 benchmark [55] in Appendix C.1 where beat competing NAS methods CIFAR1OO, FSD50K and Darcy Flow, and to the best of our knowledge set a new state-of-the-an on NinaPro.
Search strategy
We explore three search strategies within einspace: random sampling, random search, and regularised evolution (RE). Random sampling estimates the average expected test performance from K random architecture samples. Random search samples K architectures and selects the best performer on a validation set. In regularised evolution, start by constructing initial population of 100 individuals, which are either randomly sampled from the search space or seeded with existing architectures. For (K 100) iterations, the algorithm then randomly samples 10 individuals and selects the one with the highest fitness as the parent. This parent is mutated to produce a new child. This child is evaluated and enters the population while the oldest individual in the population is removed, following a first-in-firste first-ouutuu queue structure. An architecture is mutated in three straightforward steps:
1. Sample a Node: Uniformly at random sample a node in the architecture derivation tree.
2. Resample the Subtree: Replace the subtree rooted at the sampled node by regenerating it based on the grammar rules. This step allows the exploration of new configurations, potentially altering whole subtree if a non-leaf node is chosen.
3. Validate Architecture: Check if the architecture
produce valid output in the forward pass, given an input of the expected shape, and that it fits within resource constraints, c.g. GPU memory. it does, accept it; otherwise, discard and retry the mutation.
Note that these very simple search strategies, and that there is huge potential to design more intelligent approaches, e.g. including crossover operations in the evolutionary search, using hierarchical Bayesian optimisation [47] or directly learning the probabilities of the CFG (II). In this work, focus on the properties of our search space and investigate whether simple search strategies are able to find good architectures, and leave investigations more complex search strategies for future work.
Baselines
We compare these search strategies to PC-DARTS 160] DINAS 7 and Bonsai-Net [15] with results transcribed from [16.. We also compare to the performance of a trained ResNet18 (RN18). More details on the baselines, training recipes and network instantiations can be found in Appendix B.]
4.2 Random Sampling and Search
In previous NAS search spaces e.g. 30 62
complex
search methods often perform very similarly to random search (7 633. Indeed, we can see this in Table aableccmpprr
ing the PC-DARTS strategy to DARTS random search.
However for einspace, this is not the case for most datasets. Random sampling improves on pure random guessing (not shown), but is far from the baseline perfor- mance of a ResNet18. 8. The random search baseline is also far behind, but intriguingly outperforms baseline NAS ap- proaches on Chesseract.
4.3 Evolutionary Search from Scratch
Figure 5: The top RE(Mix) architecture on AddNIST, found in einspace.
We now turn to more sophisticated search strategy. We perform regularised evolution in einspace for 1000 itera-
the tions across all datasets, initialising the population with 100 random samples. In Table the results are shown the column named RE(Scratch). The performance of this strategy is significantly higher than random search on several datasets, indicating that the search strategy is more important in an expressive search space like einspace compared DARTS. Compared to the top performing NAS methods, however, it is significantly behind some datasets.

---

Table 1: Accuracies resulting from the combination of einspace with the simple search strategies of random sampling, random search, and regularised evolution (RE). See text for further detail. We evaluate performance across multiple datasets and modalities from Unseen NAS [16]. Results transcribed from [16] are denoted where DARTS 30 and Bonsai [5] search spaces are employed. The expressiveness of einspace enables performance that remains competitive with significantly more elaborate search strategies, as well as outperforming the CFG-based space hNASBench201 [46] when using evolutionary search in both spaces. Best and second best performance per dataset.
Regularised evolution (RE)
Rand.
Baselines
Rand. Search
hNB201
einspace
Sampl.
Dataset
RN18
DARTS'
PC-
NAS'
Dr
Bonsai- Net'
RE (Scratch)
(RN18)
RE
RE (Mix)
RE (Scratch)
DARTS'
Bonsai"
ein apace
space
ein
AdINIST
93.36
96.60
97.06
97.91
93.82
97.54
97.72
83.87
97.07
34.17
67.00
10.13
Language
92.16
90.12
88.55
87.65
92.43
96.84
97.92
88.12
90.12
76.83
87.01
35.26
MultNIST
91.36
96.68
98.10
97.17
93.44
96.37
92.25
93.72
96.55
39.76
66.09
18.87
CIFARTile
47.13
92.28
81.08
91.47
58,31
60.65
62.76
30.89
90.74
24.76
30,90
25.25
Gutenberg
43.32
49.12
46.62
48.57
43.70
54.02
50.16
36.70
47.72
29.00
39.58
19.69
Isabella
63.65
65.77
64.53
64.08
59.79
64.30
62.72
56.33
66.35
58.53
56.90
32.24
GeoClussing
90.08
94.61
96.03
95.66
92.33
95.31
95.13
60.43
95.54
63.56
69.13
24.35
Chesseract
59.35
57,20
58.24
60.76
63.92
60.31
61.86
59.50
59.16
68.83
61,46
44.83
Average acc.
72.55
80.30
78.78
80.41
74.72
78.17
77.56
63.70
80.41
49.43
59.76
26.33
Average rank
7.38
4.69
4.62
3.75
6.00
3.88
4.12
9.00
4.31
9.50
8.88
11.88
4.4 Evolutionary Search from Existing SOTA Architectures
To fully utilise the powerful priors of existing human-designed structures, now invoke search where the initial population of our evolutionary search seeded with collection of existing ofate-of-the-arr architectures.
We first seed the entire population with the ResNet1 8 architecture. The search applies mutations to these networks for 500 iterations. In Table these results can be found in the RE(RNI8) column.
To further highlight the expressivity of einspace, we perform experiments searching from an initial population seeded with mix of ResNet18, WRN16- 4, ViT and MLP architectures. To our knowl- edge, other NAS space is able to represent such diverse set of architectures in a single space. These results shown in the RE(Mix) column.
Overall, we find that on every single task, we can find an improved version of the initial architecture using RE(RN18) and on all but one using RE(Mix). Moreover, in some state-of-thh-aan especially on tasks further from the traditional computer vision setting. In particular, where previous NAS methods fail-i.e. the Language dataset-the architecture in Figure a direct improvement over the ResNet18 by 5.76%. See also the architecture in Figure the collection in Figure in the Appendix for the breadth of structures that are found in einspace.
beat the existing
The best model on the Language dataset, found by RE(Mix) in einspace.
Figure 6:
We further compare einspace to the previous, CFG-based, hNASBench201 from Schrodi et al. [46]. This allows for an initial study on the effects of our search space design choices and, in particular, the increased expressiveness compared to hNASBench201. These results show how einspace compares favourably to a different search space under the same evolutionary search. Overall, we highlight that search results on einspace competitive,
with far weaker search space priors.
One dataset where our searches struggle is CIFARTile, a more complex version of the CIFARI 10 dataset. While large improvements are made to the baseline networks, they still lag behind other NAS methods. This shows how the strong and restricted focus on ConvNets within the DARTS search space highly successful for traditional computer vision style tasks that have been common in the literature.

---

5 Limitations
Our search space, designed for diversity, is extremely large and uniquely unbounded in terms of depth and width. This complexity makes formulating one-shot methods like ENAS [36] DARTS [30] challenging. Instead, developing an algorithm to learn the probabilities of the PCFG may be more feasible. This approach, however, must address the grammar's context-free nature where sampling probabilities do not consider network depth, feature shape, or previous decisions, although this could be mitigated by using the parameters outlined in Section 3.66 Due to the relatively slow nature of our evolutionary search strategy (see Table 9 in Appendix C.5 we believe that finding more efficient
search strategies for expressive spaces like ours is an important and exciting direction for future work.
Another issue is ambiguity arising from the possibility of multiple derivation trees for a single architec- ture, primarily due to the multiple ways of stacking sequential modules. Moreover, have found that through sampling and mutation, some architectures' components reduce to the identity operation, from e.g. stacked identity and permute operations within sequential and routing modules. Finding ways to represent the equivalence classes of derivation trees can thus be powerful for reducing effective search space size.
Finally, we designed einspace to be diverse, but some key structures cannot be represented in its current form. There are options for recurrent computation, found in RNNs and the new wave of state-space models like Mamba [7]. We believe this can be integrated via the inclusion of recurrent module that repeats the computation of the components within it however leave more detailed exploration of this direction to future work. We also chose to keep the options for activations and normalisation layers small possible since in practice the benefit from changing these is minor.
Conclusion
We have introduced einspace: an expressive NAS search space based on a parameterised PCFG. We show that work enables the construction of comprehensive and diverse range of existing state-of- the-art architectures and can further facilitate discovery of novel architectures directly from fundamental operations. With only simple search strategies, report competitive resulting architectures across diverse set of tasks, highlighting the potential value of defining highly expressive search spaces. We further demonstrate the utility of initialising search with existing architectures as priors. We believe that future work on developing intelligent search strategies within einspace can lead to exciting advancements in neural architectures.
Acknowledgements and Disclosure of Funding
The authors are grateful to Joseph Mellor, Henry Gouk, and Thomas L.. Lee for helpful suggestions. This work was supported by the Engineering and Physical Sciences Research Council [EP/X020703/1].
References
[1] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc V Le. Under- standing and simplifying one-shot architecture search. In International Conference on Machine Learning, 2018.
[2] Gabriel Bender, Hanxiao Liu, Bo Chen, Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoe V Le. Can weight sharing outperform random architecture search? An investigation with tunas. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, 2020.
[3] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations, 2019.
[4] 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 on Learning Representations, 2020.
10

---

[5] Angelica Chen, David Dohan, and David So. Evoprompting: Language models for code-level neural architecture search. Advances in Neural Information Processing Systems, 2023.
[6] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching trans- formers for visual recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
[7] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. DrNAS: Dirichlet neural architecture search. In International Conference on Learning Representations. 2020.
[8] Zhiyi Chi. Statistical properties probabilistic context-free grammars. Computational Linguis- lics, 25(1):131-160, 1999.
[9] Xiangxiang Chu, Bo Zhang, and Ruijun Xu. FairNAS: Rethinking evaluation fairness of weight sharing neural architecture search. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
[10] Yuanzheng Ci, Chen Lin, Ming Sun, Boyu Chen, Hongwen Zhang, and Wanli Ouyang. Evolving search space for neural architecture search. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
[11] Shay Cohen. Latent-Variable PCFGs: Background and applications. In Proceedings of the 15th Meeting on the Mathematics of Language, 2017.
[12] Xuanyi Dong and Yi Yang. Nas-bench-201 Extending the scope of reproducible neural architec- ture search. ICLR, 2020.
[13] 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 16x 16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[14] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55): 2019.
[15] Rob Geada, Dennis Prangle, and A Stephen McGough. Bonsai-net: One-shot neural architecture search via differentiable pruners. arXiv preprint arXiv:2006. 09264, 2020.
[16] Rob Geada, David Towers, Matthew Forshaw, Amir -parguu-bbarghuuei.. and Stephen Mc- Gough. Insights from the use of previously unseen neural architecture search datasets. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024.
[17] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint 22x 2023.
[18] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu. Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Proceedings the European Conference on Computer Vision, 2020.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[20] John Hopcroft, Rajeev Motwani, and Jeffrey Ullman. Introduction automata theory, languages, and computation. ACM SigAct News, 32(1):60-65,2000 2001.
[21] Qibin Hou, Zihang Jiang, Li Yuan, Ming-Ming Cheng, Shuicheng Yan, and Jiashi Feng. Vision permutator: permutable MIPPlike architecture for visual recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):1328-1333 2023.
[22] Jie Hu, Shen, and Gang Sun. Squeeze-and-excitaton networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
2018. 2018.
11

---

[23] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[24] Kirthevasan Kandasamy, Willie Neiswanger. Jeff' Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. Advances in Neural Information Processing Systems, 2018.
[25] Jacques Labelle and Yeong-Nan Yeh. Generalized dyck paths. Discrete Mathematics, 82(1): URL
1-6, 1990. ISSN 0012-365X. doi: http://ooooorr//0000000000026200
bsttps://ww... www.ssceeeeeee.......... http://wwwceeeeeeeettttcoooo////
[26] Changlin Li, Tao Tang. Guangrun Wang, Jiefeng Peng, Bing Wang, Xiaodan Liang, and Xiaojun Chang. BossNAS: Exploring hybrid trnntraasformers with biock-wisely self-supervised neural architecture search. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
[27] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Conference on Uncertainty in Artificial Intelligence, 2019.
[28] Chenxi Liu, Liang-Chian Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Prociie Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
[29] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hierarchical representations for efficient architecture search. In International Conference on Learning Representations, 2018.
[30] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
[31] Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf. NSGA-Net: neural architecture search using multi-objective genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, 2019.
[32] Ningning Ma, Xiangyu Zhang, Hai- Hai-Tao Zheng, and Jian Sun. Shufflenet v2: Practical guidelines for efficient enn architecture design. In Proceedings of the European Conference on Computer Vision, 2018
[33] Christopher Manning and Hinrich Schutze. Foundations statistical natural language processing. MIT press, 1999.
[34] Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically- -unned neural networks. In Proceedings of the Workshop on Automatic Machine Learning. PMLR, 2016.
[35] Risto Mikkulainenn Jason I Liang, Elliot Meyerson, Aditya Rawal, Dan 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 Brain Computing, pages 269-287, Elsevier, 2024.
[36] Hicu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning. 2018.
[37] Ilija Radosavovic, Justin Johnson, Saining Xie, Wan-Yen Lo, and Piotr Dollár. On network design spaces for visual recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
[38] Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint arxiv: 2017.
[39] Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference on Machine Learning,2011 2017.
12

---

[40] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence. 2019.
[41] Esteban Real, Chen Liang, David So, and Quoc V Le. AutoML-zero: Evolving machine learning algorithms from scratch. In International Conference on Machine Learning, 2020.
[42] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A comprehensive survey of neural architecture search: Challenges and solutions. ACM Computing Surveys (CSUR), 54(4):1-34 2021.
[43] 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.
[44] Alex Rogozhnikov. Einops:
Clear and reliable tensor manipulations with einstein-like notation. In International Conference on Learning Representations, 2022.
[45] Robin Ru, Pedro Esperanca, and Fabio Maria Carlucci. Neural architecture generator optimization. Advances in Neural Information Processing Systems, 2020.
[46] Simon Schrodi, Danny Stoll, Binxin Ru, Rhea Sukthanker, Thomas Brox, and Frank Hutter. Construction of hierarchical neural architecture search spaces based on context-free grammars. In Advances in neural information processing systems, 2023.
[47] Simon Schrodi, Danny Stoll, Binxin Ru, Rhea Sukthanker, Thomas Brox, and Frank Hutter. Construction of hierarchical neural architecture search spaces based on context-frre grammars. Advances in Neural Information Processing Systems, 2024.
[48] David So, Wojciech Mańke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoe LL. Primer: Searching for efficient transformers for language modeling. In Advances in Neural Information Processing Systems, 2021.
[49] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for Simplicity: The All Convolutional Net. In ICLR Workshops, 2015.
[50] Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015.
[51] Mingxing Tan and Quoe V Le. Mixconv: Mixed depthwise convolutional kernels. In Proceedings of the British Machine Vision Conference, 2019.
[52] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le. MnasNet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
[53] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. MLP-Mixer: An all-MLP Architecture for Vision. In Advances in Neural Information Processing Systems, 2021.
[54] Hugo Touvron, Piotr Bojanowski, Mathilde Caron, Matthieu Cord, Alaaeldin El-Nouby, Edouard Grave, Gautier Izacard, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, and Hervé Jégou. ResMLP: Feedforward Networks for Image Classification With Data-Efficient Training. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):5314-5322 2023.
[55] Renbo Tu, Nicholas Roberts, Mikhail Khodak, Junhong Shen, Frederic Sala, and Ameet Talwalkar. Benchmarking Neural Architecture Search on Diverse Tasks. In Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[56) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
13

---

[57] Xingchen Wan, Binxin Ru, Pedro M Esperança, and Zhenguo Li. On redundancy and diversity in cell-based neural architecture search. In International Conference on Learning Representations. 2022.
[58] Colin White, Willie Neiswanger, and Yash Savani. BANANAS: Bayesian optimization with neural architectures for neural architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[59] 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 preprint arXiv:2301.0872) 2023.
[60] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pc-darts: Partial channel connections for memory-efficient architecture search. In International Conference on Learning Representations, 2020.
[61] Shangshang Yang. Xiaoshan Yu, Ye Tian, Xueming Yan, Haiping Ma, and Xingyi Zhang. Evolutionary neural architecture search for transformer in knowledge tracing. Advances in Neural Information Processing Systems, 2023.
[62] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, 2019.
[63] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evalu- ating the search phase of neural architecture search. In International Conference on Learning Representations, 2020.
[64] Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. In Proceedings of the British Machine Vision Conference, 2016.
[65] Xinbang Zhang, Zehao Huang, Naiyan Wang, Shiming Xiang, and Chunhong Pan. You only search once: Single shot neural architecture search via direct sparse optimization. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, ((()))291129006 2020.
[66] Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng- Liu. Practical block-wise neural network architecture generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2018.
[67] Yuan Zhou, Haiyang Wang, Shuwei Huo, and Boyu Wang. Hierarchical full-attention neural architecture search based on search space compression. Knowledge- Based Systems, 269:110507 2023.
[68] Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations, 2017.
[69] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architec- tures for scalable image recognition. In Proceedings the the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018
14

---

A Search Space Details
A.1 Sampling
In this section, we explain the process of sampling an architecture from our parameterised PCFG through example. We specifically focus how the running example from the main paper, simple convolutional block with skip connection, could be generated.
We begin the process with the starting symbol S, which could produce several forms based on the production rules, including ( (MM), ). M A or (P MR) ). Since our block includes a skip connection, the macro structure of our architecture is best represented by branching module MBM A)
Within this module, expand the string from left to right, thereby starting with ). The specific branching operation that fits our goal is + clone ) as we wish to later combine a transformed version of the tensor with itself. Since we have prior) and our module becomes Mj M2 A)
branches, they are produced separately (see branching
For the first branch, ( [M by batch normalisation and an activation. Since this involves several composed operations we first expand into sequential module ( M₁ + M3 M4 The first of these operations represents the convolution. Within einspace, a convolution, conv (x)). ). is decomposed into the three operations, col2im 20i2mmmienerr( [m2col (z))). Thus, in our grammar unfold it as routing module, (M3 - P Ms R) which further produces P + im2col] ), Mg - linear)) ) and (R col 2im) ). The normalisation and activation then generated under M4 defined another sequential module ( - MMMM with ( (M C norm and ( M, derived as M2 - idd-nnitttt
need set of components that constitute convolution followed
). The second branch, M2, acts as a skip connection and is thus
To finalise the architecture, the aggregation symbol ( (A) merges the tensors back into one unit. To complete the residual connection,
the rule ( A - add). ).
The full derivation tree this example shown in Figure the main paper. This general sampling process allows the creation of complex neural network architectures from a structured and interpretable set of rules.
A.2 Fundamental Operations
Our grammar in the main paper is somewhat simplified. There are some fundamental operations that have hyperparameters that allow multiple versions be chosen. They are detailed here.
Branching functions. For the production rule (B - clone| group ), the full set of options is:
clone (b=2) clone (b=4) clone (b=8)
(10)
group (dupmid=11, |group (dim=1, group (dim=1,
(11)
group(dim=2, group (dim=2, b=4) group (dim=2, b-8)
(12)
group (dim= b=2) |group (dim=3, b=4) group (dim=3, b=8),
(13)
where b refers to the branching factor and dim is the dimension we group Aggregation functions. Similarly, for the production rule (A>> m-tmml add concat the full set options is:
A matmul (scaled=False) (aatuu(sscaleeee
add
(14)
concat (dim=1, b=2) concat (dim=1, (co)cct (dim=1,bbrt
(15)
concat (dim=2,.b=2) concat (dim=2,b=4) concat (dim=2, b=8)
(16)
concat (dim=3, b=2) concat (dim=3, concat (dim=3, b=8),
(17)
where scaled= True makes the matmul operation equivalent to the scaled dot product used in many transformer architectures, dim is the dimension we concatenate over and b is the branching factor.
Routing functions. The im2col and col2im functions are implemented to offer the standard function- ality that enables convolutional operations, including variables that set the kernel sizes, stride, dilation and padding. Below are the full set of options for im2col. The col 20liimm only takes the predicted output
15

---

shape as parameter so we can include only single version of this operation.
im2col
im2col (k=1,==2,p=0),
(18)
im2col (k= im2col s=1 (M2col(k=,ss444
(19)
im2col 8 8 im2col p=0),
(20)
where is the kernel size, is the stride and p the padding.
For the permute operation, there are six versions of the order parameter o. There is one for the Col mode and five for the Im mode:
permute (o- (2,1)),
(21)
permute (o= (o=(1,3, (1,3,2)) (ot,,,e(==2211,3) permute((=(2,3,)) (o= 1)).
(22)
pe
(23)
For completeness, the identity operation can also be included, making two versions in the Col mode (with (eentityperrmttoor(((,)))) and in the Im mode (with identity=permute (o- (1),,
Computation functions. For linear layers, we vary the output dimension d across powers of two:
linear linear(d=16)
linear (d=32),
linear (d=64),
(24)
linear (d=128),
linear (d=256),
linear (d=51))
(25)
linear linear (d=1024),
linear (d=2048))
(26)
The norm operation takes on the batch-norus functionality in the Im mode and layer-norm in Col mode. The sof tmax just softmax operation applied to the final dimension, the relu activation is implemented as the single option leaky-relu and pos-enc is a learnable positional encoding.
A.3 Patch Embeddings and Convolutions
In this section provide some more information about how the routing module represent common components.
The routing module, (M- + P M R.) puts prior certain types of operations inside architectures. patch embedding, such as those found many transformers, achieved by the following derivation: (M + im2col linear identity) while convolution can be obtained by M - im2col 1 linear col2im) ). In terms of the process required to sample such combinations, the first easy since there are no dependencies between the operations. The second, however, is more complicated and requires some discussion.
Let.z be tensor in 32 and let us consider a routing module containing the functions: im2col, 1 linear, col2im. The functions will be applied in order the input tensor, giving us
x' im2coml (w),
(27)
x" linearnnrrrrr (x'),
(28)
y col2im(m' (x"))
(29)
The shapes of the intermediate and final tensors (ed,""")) depend on several function hyperparameters. These listed below.
Table 2: Hyperparameters for the three functions involved in convolution component.
im2col
col
linear
kin (kernel size)
kout 7 (kernel size)
Cout 64 (output channels)
8in 2 (stride)
Sout 2 (stride)
Pin (padding)
Pout 0 (padding)
The input tensor has height dimension han and width Win The im2col operation will extract column vectors from this space number of times depending the kernel size kin, stride Sin and padding Pin.
16

---

values in the table above. The number of column vectors equals
hin + 2x Pin
(hin 1)-1
Win
2x Pip Pin (kin 1]
(30)
8in
8yn
which in our case gives 1 The shapes of all intermediate tensors can therefore be written as in Table
Table 3: Tensor shapes the forward pass of our convolution component; Gin -3,tin = -2, Win = 32
in this example.
Tensor
Shape
x'
[1, Cin x hin x kinn
[2, Cout
[Couts Bouts Wout)
Therefore, to successfully apply the col2im function, the constraint (= hout x Wout must be satisfied. From Equation 30 we can see that the output height and width can be predicted by the im2col
parameters
hin +2 Pin
(kign 1) 1)-1
hout
+1
(31)
Sin
Win +2 x Pin
(kin 1)
Wout
+1
(32)
Sin
So, in practice, the im2col operation fully defines the behaviour of the convolution apart from the number of output channels defined by the linear layer-and and the col2im only rearranges the tensor back into its correct 3D form. This is trivial in the case where hin = Winn since hout Wout = vI. However, hin Win, then the predicted output shapes must be remembered until the col2im operation is applied.
Thus, in our sampling and mutation algorithm, whenever an im2col operation is sampled, we must store the predicted output shape until a corresponding col2im is applied. Additionally, the dimensionality of must not change in the connecting branch as it would break the constraint fout X Wot--
A.4 Branching Rate of the CFG
If PCFG is consistent, the probabilities of all finite derivations sum to one, or equivalently. it has a zero probability of generating infinite strings derivations []. For us, that means sampled architecture can not be infinitely large, and that the sampling algorithm will halt with probability one. In order to check if CFG is consistent, we can inspect the spectral radius p its non-terminal expectation matrix [8). If p<C 1, then the PCFG is consistent. This expectation matrix is indexed by the non-terminals in the grammar (both the columns and the rows), and at each cell it provides the expected number of instances the column non-terminal being generated from the row non-terminal by summing the probabilities of the row non-terne non-terminal multiplied by the count of the column non-terminal in each rule.
We can also solve a (simple, in our case) set of linear equations in order to compute the expected length of architecture string, function of the rule probabilities. More specifically, denote by [[A] the expected length of string generated by a nonterminal in the grammar A. Then l. = =][s], where:
E(s] Σ a 8) ΣE E(aa
(33)
EMM
Σ
PMM + M) E
(34)
E[B
(35)
E[A
(36)
E(P)
(37)
E
(38)
E
(39)
17

---

In the above, a the right hand side of a rule and varies over the nonterminals in that right hand side.
A.5 Adjustments for One-Dimensional Tasks
We have presented our new search space primarily with the application to two-dimensional data in mind-where, confusingly, the input tensor is of the shape (c, H, W), two spatial dimensions and one channel dimension. In order search for architectures on ID datasets -with imput tensors of shape (s, D), i.e. one sequence dimension and one token dimension we need to adjust the einspace CFG make it compatible.
We replace the routing functions im2col and col with operations that perform the full ID convo- lution serretll--ithheee decomposing the operation- place them into the computation function group. Below are the new convid functions in the ID variant of einspace
convid((=1,==1,pF0..cc
(40)
conr1d([st1,=11,p00..111
(41)
con=f((k=3,xx1.p=111--5)
(42)
com=dd(==3_=51,p111--226) )
(43)
convid convid (
con1dd(==__=11,p22,--666
(44)
comvi@(k=5,s=1,,-222-2233
(45)
convld(k=8,s11,p=33.00
convi((ks8,5_1,,333ddd4
(46)
convid s- 1
(47)
Some versions the group, concat and permute operations are also removed they operate on dimension that now doesn't 't exist. Below is the adjusted grammar for this variant.
S
M
M
B
M
A
R
R, M C,
M
M
+
M
M
B
M
A
B
clone group, add concat, R identity permute,
A +
matmul |
C identity convid linear
norm
relu
softmax
pos- enc.
In the NASBench360 results presented in Table C.I this 1D variant of einspace is used for the datasets ECG, Satellite and Deepsea. The baseline WideResNNet-66-4 architecture is also adjusted to handle the ID data, as described in (55)
A.6 Size of the Search Space
In this section we will discuss the size the introduced search space.
Our einspace grammar contains recursive rules, e.g. (M MM) ). Due to this recursion the grammar generates language with an infinite number of strings. We know from Section[A.4] A..4 since our gram- mar is consistent, the architecture sampling process always terminates. This means every architecture derivation tree is finite size. So, while einspace covers an infinite number of architectures, each such architecture is finite. Let the architeclure string denote the left-to-right sequence of leaves of derivation tree. We define S,, to be the set of all architecture strings of length n.. As we will show next, the size of Sn grows exponentially with To do this, we first introduce few new concepts.
Dyck language [25] is formal language consisting of strings that represent balanced and properly nested sequences of pairs of symbols, typically parentheses, where each opening symbol must have corresponding closing symbol, and no point the string can the number closing symbols exceed the number of opening symbols. A Dyck language can be generated by a context- fffee grammar defined over set terminal symbols Σ= {.))). Generalising this, Dyck-k denotes Dyck language with distinct pairs of matching symbols, e.g. Dyck-2 has Σ= (() The growth of Dyck-1 language is described by the Catalan numbers, reflecting the exponential increase valid strings as the length of the input increases, i.c. the number of strings with matching pairs of symbols is the mith Catalan number
18

---

Cm= 1 (.m)) Asymptotically, the number of such strings grows as ((47). Dyck-2 languages do m+1 not follow the Catalan numbers but still grow (
We can rewrite (and somewhat simplify) our einspace CFG from Section 3.3 in order generate Dyck language
s - MM (M) | [M],
M MM ( ( [M] 1 C.
C - 1
The set of non-terminal symbols (B, A, P. R] has been replaced with the terminal set of parentheses and square brackets C. ). [.]] and, for simplicity. the terminal symbols of C have been replaced by integers. This makes it Dyck-2 language with the addition of the C symbol that can be expanded into several terminal options.
While normal Dyck-2 2 language grows O(4"), ours is complex. Firstly, each non-terminal symbol M will eventually produce a C which leads to a terminal. Let the number of terminals derivable from be X. and the number of occurrences of the symbol in the derivation of an architecture be c. The number of possible strings we can obtain from just the C symbols thus grows as Ox")). Secondly, the brackets we introduced can, in our original CFG, themselves be derived into terminal symbols for branching, aggregation and routing functions via (B, A, P. R). Let the maximum number of terminals derivable from any of these 3. We already know that the number of balanced brackets m, meaning the total number of terminals coming from these is 2m. Therefore, the number of architecture strings in S,, grows as
044Th x*),
(48)
where m the combined number of branching and routing modules, cs the number of computation functions, and 2m Some architectures will contain many nested branching routing functions and be dominated by the first two factors, and some will contain many sequential modules and computation functions and be dominated by the third.
A.7 Comparison to Other Search Spaces
In Table we compare einspace to other popular search spaces in the literature along several axes. We highlight some of the most important differences here:
e inspace uniquely unifies multiple architectural families (ConvNets, Transformers, MLP- only) into one single expressive space while the CFG-based framework of Schrodi al. [46) has variations of spaces centred around ConvNet Nets only, and a separate instantiation focusing only on Transformers.
einspace extends to probabilistic CFGs. This enables set of benefits that include (i) allowing experts to define priors on the search space via probabilities, and (ii) enabling broader range of search algorithms that incorporate uncertainty estimates inside the search itself.
e einspace contains recursive production rules (e.g. M + MM), meaning the same rule can be expanded over and over again, providing an infinite space and a very high flexibility in macro structures. In contrast, [66 instead focuses on fixed hierarchical levels that limits the macro structure to predefined though very large-sei set of choices.
einspace encodes architectures in the form of derivation trees. These allow for mutations that can effectively alter both the macro structure and the individual components of an architecture. Modifications of this class are more difficult if using e.g. the more rigid graph encodings.
Overall, we highlight that our experimental search results on einspace are competitive with previous work, even with far weaker priors on the search space.
19

---

Table 4: Comparison of einspace with existing search spaces. RS: random search, RE: regularised evolution, RL: reinforcement learning, BO: Bayesian optimisation and GB: gradient-basee size of e einspace is infinite, but we can bound the number of possible architectures strings of certain length, as discussed in Section & Gradient based search is difficult these spaces due to their size, but other Beiigt-sharring methods may be available. 'The paper introducing hNASBench201 [46] also considers versions of the search space for Transformer language models.
The
Search Space Properties
Available Search Strategies
Type
Size
Focus
RS
RL
BO
GB
einspace
PCFG
Infinite
ConvNets, Transformers, MLP-only
hNASBench201
CFG
10446
ConvNets*
4
/
/
NASBench201
Cell
10
ConvNets
of
/
NASBench101
Cell
105
ConvNets
DARTS
Cell
1018
ConvNets
v
B Implementation and Experimental Details
B.1
Networks
Baseline networks
We use convolutional baselines of ResNet18 [9] and WideResNet-16-4 [64]. Both stems use a x convolution instead of the standard x 7 as most input shapes in the datasets we use are small. The former contains max-pooling layer in the stem, which for simplicity we decide to not represent in our search space. Instead we modify the pooling operation and replace it with a 3 x 3 convolution with stride 2. This has been shown to be equally powerful [49] and in our experiments we find that performs similarly. Our ViT model is small 4-layer network with patch size of 4, model width of 512, and heads. The MLP-Mixc shares the same patch embedding stem with a patch size 8 layers and, similarly, model width of 512. The channel mixer expands the dimension by 4 and the token mixer cuts it half. The models have the following number of parameters (given an input image of shape [3, 64, 64]): Resnet18: 11.2 1.,2M, WRN16-4: 2.8M, VIT: 4.4M and MLP-Mixer: 6.5M.
has
Network head
Every network that is instantiated contains few common operations. For classification tasks, the network head takes the following form: the output features the sampled backbone are reduced to their channel dimension via reduce (x, 'B B C³ 'mean' >, depending on if the imput features x are in Im or Col mode. Second, a final linear layer that maps the channel dimension to the target dimension (i.e., the number of classes) is appended. For dense prediction tasks: the head contains an adaptive average pooling layer that upsamples the two final dimensions of the back features to the target image size. If the features are in the Col mode, we insert a new dimension after the batch size. Then regardless of mode, a linear layer adjusts the number of channels to the target channel number.
-> B C², 'mean 2 > reduce (x, 'B C H ->
Network training
Each network is trained and evaluated separately with no weight sharing. During the search phase we minimise the loss on a train split and compute the validation metric on a validation set. To evaluate the final chosen module, the inner loop optimisation of architectures uses fewer epochs compared to the evaluation phase. All networks are trained using the SGD optimizer with momentum of 0.9. The values for learning rate, weight decay, batch size and more can be found T
retrain vrain+val splits and evaluate on test. To speed up experiments,
B.2 Datasets
Our experimental evaluation covers 19 different datasets, with sizes ranging from thousands of data points, to million (Satellite from NASBench360), and spatial resolutions of up to 256 x 256 (Cosmic from NASBench360), In this section we briefly describe these parts in detail.
We followed the official instructions of Unseen NAS [66 to setup the datasets. Descriptions of each dataset follow:
*The notation used here comes from the Python package einops
44 which implements reduce function.
20

---

Table 5: Hyperparametters for each dataset, taken from Geada et al. [16] for Unseen NAS and Tu et al. 55 for NASBench360. We the number of search epochs be one eighth of the evaluation epochs to speed up the search stage without significantly compromising on signal quality. For the Unseen NAS datasets (top set) we report the accuracy across all datasets. For NASBench360 (second set) and CIFARIO 10 (bottom), the metrics differ and we report the 0-1 error instead of accuracy to align with the other metrics focused on error minimisation.
Dataset
Metric
Baseline
Epochs (search)
Epochs (eval)
Batch
Learning
Weight decay
Mom-
name
type
model
size
rate
entum
AddNIST
Accuracy
ResNet18
64
256
0.04
3 10 4
0.9
Language
Accuracy
ResNet18
64
256
0.04
3 10
0.9
MultNIST
Accuracy
ResNet18
64
256
0.04
3x 10
0.9
CIFARTile
Accuracy
ResNet18
64
256
0.04
3x 10
0.9
Gutenberg
Accuracy
ResNet18
0.04
3x
0.9
Isabella
Accuracy
ResNet18
64
256
0,04
3x 3x
0.9
GeoClassing
Accuracy
ResNet18
64
256
0.04
3x
0.9
Chesseract
Accuracy
ResNet18
64
256
0.04
3x
0.9
CIFAR100
0-1 error
WRN16-4
25
200
128
0.1
5x
0.9
Spherical
0-1 error
WRNI 6-4
25
200
128
0.1
5x10-
0.9
NinaPro
0-1 error
WRN16-4
25
200
5x10
0.9
FSD50K
1 mAP
WRN16-4
25
200
256
0.1
5x10
0.9
Darcy Flow
relative &
WRN16-4
25
200
4
0.001
5x
0.9
PSICOV
MAE
WRN16-4
25
200
8
0.001
5x
0.9
Cosmic
1 AUROC
WRN16-4
25
200
8
0.001
5x10
0.9
ECG
F-
WRN16-4
25
200
256
5x
0.9
Satellite
0-1 error
WRN16-
25
200
4096
0.1
5x
0.9
Deepsea
AUROC
WRN16-4
25
200
256
5x10
0.9
CIFARIO
0-1
WRN16-4
25
200
128
0.1
5
0.9
AddNIST
This dataset derived from the MNIST dataset. Specifically, each RGB image is computed by stacking three MNIST images in the channel dimension. Each image has the shape 3 x 28 x 28. It has a total of 20 categories; the class label is computed by summing the MNIST labels in all three channels. Among the 70,000 images, 45,000 used for training, 15,000 used for validation, and 10,000 images are used for testing.
Language
Language consists of six-letter words extracted from dictionaries of ten Latin alphabet languages: English, Dutch, German, Spanish, French, Portuguese, Swedish, Zulu, Swahili, and Finnish. Words containing diacritics or the letters' 'y" and 'z' are excluded, making an alphabet of 24 letters. Each sample consists of four words encoded into a binary image of shape 1 x 24 x 24. The task is to predict the language of the sample. Along the y-axis are the letter positions the concatenated 24-letter string, and along the x-axis are the letters in the alphabet. As an example, a one in the position (0, 0) indicates that the first letter in the string an 'a'. The dataset split into 50,000 training samples, 10,000 validation samples, and 10,000 test samples.
MulNNIST
MultNIST is dataset designed similarly AddNIST, originating from the same research objective. Each channel of the 3 channel images contains an image from the MNIST dataset. Each image has
the shape 3 x 28 28. The dataset is divided into 50,000 training images, 10,000 validation images, and 10,000 test images. Unlike AddNIST, MultNIST comprises ten classes (0-9), the label for each MultNIST image computed using the formula / = (r x mod 10, where r, and are MNIST labels of the red, green, and blue channels, respectively.
RTile
CIFARTile is dataset where each image is composite of four CIFAR- 10 images arranged in 2 x grid, making each sample an image of shape 3 64 64. The dataset is divided into 45,000
21

---

training images, 15,000 validation images, and 10,000 test images. CIFARTile has four classes (0-3), determined by the number of distinct CIFAR-I0 classes in each grid, minus one.
Gutenberg
Gutenberg a dataset sourced from Project Gutenberg. It includes texts from six authors, with basic text preprocessing applied: punctuation removal, diacritic conversion, and elimination of structural words. The dataset contains consecutive sequences of three words (3-6 letters each), padded to 6 characters and concatenated into 18-character strings. These strings are converted into images with size 1 x 27 x 18, with the x-axis representing character positions and the y-axis representing alphabetical letters spaces. The task is to predict the author of each sequence. The dataset is split into 45,000 training, 15,000 validation, and 6,000 test images.
Isabella
Isabella is a dataset derived from musical recordings of the Isabella Stewart Gardner Museum, Boston. It includes four classes based on the era of composition: Baroque, Classical, Romantic, and 20th Century. The recordings are split into five-second snippets and converted into 64- spectrograms, resulting in images with dimensions 1 x 64 x 128. The dataset is divided into 50,000 training images, 10,000 validation images, and 10,000 test images, ensuring no overlap of recordings across splits. The task is to predict the era of composition from the spectrogram.
GeoClassing
GeoClassing is based on the BigEarthNet dataset. It uses satellite images initially labeled for ground-cover classification but reclassified by the European country they depict. The dataset includes ten classes: Austria, Belgium, Finland, Ireland, Kosovo, Lithuania, Luxembourg, Portugal, Serbia, and Switzerland. Each image is of size 3 x images, 8, 8,758 validation images, and 8,751 test images. The task is to predict the country depicted in each image based on topology and ground coverage.
64 x 64. The dataset is split into 43,821 training
Chesseract
Chesseract is a dataset derived from public chess games of eight grandmasters. The dataset consists of the final 15% of board states from these games. Each position is one-hot encoded by piece type and color, resulting in x8 x images. The dataset is divided into 49, 99,998 training images, 9,999 validation images, and 9,999 test images, ensuring no positions from the same game appear across splits. Each image is classified into one of three classes; White wins, Draw, or Black wins. The task is predict the game's ' result based on the given board position. We pad the input with zero-valued pixels to make 12 x 18 x 18 tensor.
We follow the official instructions of NASBench360 [55] to setup the datasets. Dataset descriptions follow:
CIFAR100
CIFAR 100 is widely known image classification dataset with 100 fine-grained classes. Each image is of size x 32 x 32. The dataset is split into 40,000 training, 10,000 validation and 10,000 testing images. We preprocess the images by applying random crops, horizontal flips, and normalisation.
Spherical
Spherical dataset consists on classifying spherically projected CIFAR images. Specifically, CIFAR images are projected to the northern hemisphere with a random rotation. Each image is of size x 60 x 60. Spherical dataset uses the same split ratios as CIFARI00. In this case, there is no data augmentation nor pre-process pre-processing steps.
NinaPro
NinaPro is dataset for classifying hand gestures given their electromyography signals. EMG data signals are collected with two Myo armbands as wave signals. Wave signals, along with their wavelength and frequency, are processed 2D signals of shape 16 x 52. There are 18 classes, which are heavily imbalanced, with the neutral position amounting for 65% of all gestures. The dataset is split into 2,638 training samples, 659 validation samples, and 659 testing samples. No further data augmentation is applied.
FSD50K
Freesound Dataset 50k (FSD50K) is collection of 51,197 sound clips, categorised into 200
22

---

categories, where each clip can receive multiple labels. The task is to classify the sound event from its log-mel spectrogram. and the performance computed via the mean average precision (mAP). We resample the raw audio files at frequency of 22,050 Hz and convert them into 96-band log-mel spectrograms. From these longer audio files, we extract shorter, overlapping I-second segments, resulting in input size of x 101 x 96. During training, one randomly-selecter segment per clip is used, rather than all segments. Background noise is added to 75% of the training data as part of data augmentation. The validation set consists of 4,170 clips and the test set of 10,231 clips.
Darcy Flow
Darcy Flow is regression task for predicting the solution of 2D PDE at predefined later stage given some 2D initial conditions. The input is a 1 x 85 x 85 image describing the initial state of the fluid. The output should match the same dimensions. The dataset is split into 900 images for training, 100 for validation, and 100 for test. Input data is normalised.
PSICOV
This dataset concerns the use of neural networks in the protein folding prediction pipeline. It uses proteins from one source, DeepCov, for training and validation. DeepCov contains 3,456 proteins each with shape 57 x 128 x 128. The validation set consists of 100 proteins, with the rest used for training. The test set comes from another source, PSICOV, with 150 proteins. These proteins come in features of a different shape, x x512 512. Due to this, the evaluated network takes each non-overlapping
128 128 patch as input. The labels represent pairwise distances between residues. The evaluation metric mean absolute error (MAE) computed on distances below 8A, denoted as MAEs.
Cosmic
Cosmic contains images from the F435W filter collected from the Hubble Space Telescope. It aims identify cosmic rays (corrupted pixels) in the images. Inputs are images of 1 x 256 x 256, and outputs are pixel binary predictions (artifact vs. no-artifact). The dataset is split into 4,347 images for training, 483 for validation, and 420 for test.
ECG
The ECG task concerns predicting irregularities electrocardiograss ECG recordings 9-60 seconds are sampled at 300 Hz. and labeled using four classes: normal, disease, other, or noisy rhythms. We process each recording with fixed sliding window 1,000 ms and stride of 500 ms. This transforms 2,186 single lead recordings into more than 330,000 segments. We use 261,740 of these for training, 33,281 for validation, and 33,494 for test. Each segment has the shape 1 1,000. The evaluation metric is the Fi-score.
Satellite
The goal of the Satellite task is to classify land cover maps for geo-surveying, for million data points across 24 categories. Each data point is a single-channe satellite time-series shape 1 x 46, with standard normalisation augmentation applied. The data is split with 800,000 samples for the training set, 100,000 for validation, and 100,000 for test.
Deepsea
This dataset focuses on predicting the behaviour of chromatin proteins to aid in understanding genetic diseases. Each data point is genome sequence of 1,000-base pairs (A, C, or G), represented as binary matrix of shape 1000 x 4, categorised across 36 classes of chromatin features. The training set contains 71,753 data points, with 2,490 for validation and 149,400 for testing. The evaluation metric is the area under the receiver operating characteristic (AUROC).
Finally, we also report results on the classic CIFARIO dataset:
CIFAR10
CIFARIO a widely known image classification dataset with 10 classes. Each image is of size 3 x 32 x 32, The dataset is split into 40,000 training, 10,000 validation and 10,000 testing images. We preprocess the images by applying random crops, horizontal flips, and normalisation.
B.3 Compute Resources
All our experiments our two internal clusters with the following infrastructure:
23

---

Table 6: Lower is better. Our results on NASBench360 [35 where we report errors across all datasets as described in Table 5 We compare to the results from 55 where the GAEA algorithm on the DARTS search space used, along with a
expert architecture per dataset (Expert). RE(WRN) refers to initialising the regularised evolution search algorithm with the WideResNet 6-4 (WRN) architecture. Note that we could not reproduce some baseline WRN performances in our code. have therefore reported both the WRN from NB360 and our own WRN results. We use our own results for computing average ranks. Best and second best performance per dataset (excluding WRN from NB360).
WRN
WRN ours
GAEA DARTS
RE(WRN) einspace
Expert
NB360
CIFARI00
23.35
25.61
24.02
19.39
21.47
Spherical
85.77
76.32
48.23
67.41
66.37
NinaPro
6.78
10.32
17.67
8.73
6.37
FSD50K
0.92
0.92
0.94
0.62
0.65
Darcy Flow
0.073
0.032
0.026
0.008
0.014
PSICOV
3.84
5.71
2.94
3.35
4.38
Cosmic
0.245
0.245
0.229
0.127
0.730
ECG
0.43
0.59
0.34
0.28
0.46
Satellite
15.49
15.29
12.51
19.80
12.55
DeepSea
0.40
0.45
0.36
0.30
0.36
Average rank L
3.60
2.35
1.70
2.35
Table 7: Higher is better. Accuracies for searches with DenseNet12 21 as well as finetuning pretrained networks the Unseen NAS benchmark. First two column the baseline performances of training ResNet1 and DenseNet12) from scratch. Next two columns are results when initialising our regu- larised evolution with ResNetl and DenseNet121. Final two columns are results when finetuning ResNet18 and EfficientNet-B0 from their pretrained ImageNet weights.
RE
Finetuning RNI8
RN18
DN121
RN18
DN18
ENBO
AddNIST
93.36
94.72
97.54
94.84
94.69
94.77
Language
92.16
91.27
96.84
98.39
90.31
90.62
MultNIST
91.36
92.58
96.37
94.86
91.12
91.90
CIFARTile
47.13
56.37
60.65
66.06
52.26
79.32
Gutenberg
43.32
42.97
54.02
47.23
42.52
42.08
Isabella
63.65
43.65
64.30
42.89
62.35
67.46
GeoClassing
90.08
92.20
95.31
94.33
90.70
95.81
Chesseract
59.35
61.72
60.31
61.64
61.29
62.24
Average acc. t
72.55
71.94
78.17
75.03
73.16
78.02
AMD EPYC 48-Core Processor with 1000GB RAM and 8x NVIDIA RTX A5500 with 24GB of memory
AMD EPYC 7452 32-Core Processor with 400GB RAM and 7x NVIDIA A100 with 40GB of memory
Each experiment used single GPU to train each architecture. Running 1000 iterations of RE (crratc)) on the quickest datasets (Language and Chesseract) took around 2 days, while the slowest (GeoClassing) took days. We had very similar training times for RE(RNI8) and RE(Mix) which ran for 500 iterations.
C Additional Results
C.1 NASBench360
We test einspace on the diverse NASBench360 (55) to further showcase its potential. These results can be found in T In this setting the baseline network is WideResNet16-4 (WRN)-whie is

---

Table 8: Lower is better. Performance on CIFARIO as measured by the 0-1 error.
RNI8
RE(RN18)
RE(Mix)
CIFARIO 5.09
4.69
5.27
Table 9: Runtime of search algorithms, well as the number of model parameters for the found architectures. Numbers for PC-DARTS on two datasets are missing due to missing logs from the authors of [16]. RE on einspace the RE(Mix) variant, while RE on hNASBench201 searches from scratch.
AMINIST
I Language
MuleNIST
CIFARTile
Gutenberg
Isabella
GeoClassing
Chesseract
DrNAS
10
9
11
25
13
59
23
10
runtine
(hours)
PC-DARTS
4
12
30
RE(hNB201)
15
72
21
59
59
37
RE(einspace)
55
71
32
62
42
80
65
42
DINAS
#parans
(x110%)
PC-DARTS
RE(NNB201)
RR(einspace)
adapted for the ID tasks ECG, Satellite and Deepsea as (55). see that our regularised evolution with the baseline the initial seed, RE(WRN), again consistently finds architectural improvements. It matches the performance of the GAEA search strategy on the DARTS search space, achieving the same average rank. On NinaPro, it even beats the Expert architecture, specifically designed for this task and to the best of our knowledge sets a new state-of-the-ar Note that we fail to exactly reproduce the WRN baseline network performance several tasks, so we report both our own WRN values along with those from
C.2 More Baseline Architectures
We explore another baseline architecture, 1e1, and use the initial seed to our evolutionary search in einspace. In Table[7] we can see that the DenseNet 121 on its own performs comparably to the ResNet18 model. When seeding search from the model with RE(DNI21), we observe performance boosts similar to the gaps found between RNI8 and RE(RN18), highlighting the general applicability of initialising search from different architectures within einspace.
C.3 Finetuning
We present further results comparing method against finetuning model from pre-trained weights. In the experiments presented Table a finetuned EfficientNet-Bl matches or beats the ResNet18 18 baseline the Unseen NAS datasets. However, RE(Mix) einspace still often outperforms this method, e.g. on Gutenberg by 12%, although finetuning dominates on the CIFARTile vision task.
C.4 CIFAR10
To complete evaluation common NAS benchmarks, also report results the CIFAR10 dataset in Table
C.5 Runtime and Parameter Count
Table summarises the runtimes and parameter counts of architectures found using DrNAS, PC- DARTS, and RE on hNNASBench201 and einspace. Notably, the gradient-basee DrNAS and PC- DARTS demonstrate significantly shorter runtimes, with DrNAS achieving search times between 10 to 25 hours and PC-DARTS between 4 to 12 hours. In contrast, the black-box evolutionary methods show substantially longer runtimes, ranging from to hours, as they independently train a large number of networks. The search times for einspace are comparable to those for hNASBench201, though due to the potential increased complexity in candidate architectures, they can sometimes be significantly longer. In terms of model parameters, DrNAS and PC- PC-DARTS consistently produce architectures
25

---

Table 10: The distribution of terminal and nonterminal symbols as well as average branching factors in 2000 sampled architectures with varying values for the computation module probability p(M-+C|M). For probability values 0.2 and 0.1 there is no data, as the sampling process is too time-consuming.
Type
p(M -
Min
Mean
Median
Std
Max
0,9
2
3.87
3.00
2.84
28
0.8
2
5.34
4.00
6.32
54
terminals
0.7
2
6.72
4.00
11.22
118
0.6
2
8.65
4.00
16.73
202
0.5
2
40.22
5,00
303.65
4779
0.4
2
100.15
8.00
749.61
12026
0.3
2
6070.77
9.00
64863.45
878122
0.9
2
3.63
3.00
3.45
42
non-terminals
0.8
2
5.04
3.00
6.91
64
0.7
2
6.00
3.00
9.21
81
0,6
2
7.74
4.00
13.61
165
0.5
2
39.03
5.00
325.18
5219
0,4
2
88.58
8,00
649.44
10417
0.3
2
4588.13
8.00
50203.87
734497
0.9
1
1.75
1.00
1.63
7.61
branching factor
0.8
1
2.05
1.00
1.95
7.73
0.7
2.05
1.00
1.91
7.83
0.6
2.17
1.00
1.96
7.73
0.5
2.34
1.00
2.00
7.88
0.4
2.81
1.75
2.14
7.87
0.3
2.80
1.75
2.13
7.96
with parameter counts around 4 million, hNASBench201 is consistently more parameter efficient at around IM, while einspace finds architectures that vary significantly in size from 1M-25M, showing flexibility in adaptation to task difficulty.
C.6 Empirical Architecture Complexity
M) 0.32 using the branching rate method described in A.4 We next report empirical results for the architecture complexities as we vary this value. In Table 10 can see that the complexity, as measured by count of terminals and non-terminals in the derivation trees, grows the probability decreases.
For our experiments we the computation module probability to p(M -
When searching for an architecture on a new unknown task, the flexibility of the search space is key. During our random searching on einspace we found that we sampled networks with parameter counts ranging from zero up billion, and from as few two operations up as many 3,000. The frequency of all functions in einspace that appear in these networks can be found in Figure
26

---

Distribution node types
Frequency
10
10²
sequental module
branch module
routing moddoddss
cone lensor2
cone Tensorr
cione tensor8
gouup 0 dim2510
FoU m2m2222
you cim4s c
FOU cim4820
FOUD (imm53
youup mimmsss 110
group dim8s20
group dim8s3c
0ot product
scaled dol product
add lensors
22
lensors220
304
(ensors, (8)
(ensors 2
tensors.309
idonuty
pemmule2
permulc133 132
permule22
permute25 1
permute3 2
permute32
Im2cc! k130p
im2co! k2800
in2c0 2kc0kk115 111kk111 0
im2cc 3128 1-
Im2ccl4 2422e444400 k4800
im22c/8 (1220o8k8a00 kka00p
16 16g0p
col2mm
ineer 32
inners
linertd
12-
linear2048
leakyrelu
softn ex
positional emcodingg
cal (ensors
lansors
(ensors
Im2col161 16k
computatins
Node type
Figure 7: Frequency of each module/function in 8,000 sampled architectures with C 0.332.
27

---

Figure 8: The top architectures by RE(Mix) in einspace Unseen NAS. From left to right, row by row: AddNIST, Language; MultNIST, CIFARTile; Gutenberg, Isabella; GeoClassing, Chesseract.
28

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer:[Yes]
The main contribution is our search space- einspace-which is described in detail in the paper, and can explored using the code we have provided. We have claimed competitive results on the Unseen NAS datasets with our space using simple search algorithms which can be verified in T We have included aspirational goals as motivation, and made it clear that we believe this work is a step towards achieving them.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have dedicated Limitations section in our paper. Please see Section 5 foor more details.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to treech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable. the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't aeknowledged judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
29

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
Our paper does not present any theoretical proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We provide implementation and experimental details in Appendix B We also submit our codebase together with the paper. The codebase includes all configuration files to reproduce our results Unseen NAS (Tab. [T] and NASBench360 (Tab. 6p. It also includes detailed instructions on how to set the environment and datasets.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., s., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some
30

---

way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
We submit our codebase together with the paper for reviewers to check our results. The codebase includes all configuration files reproduce results on Unseen NAS (Tab. and NASBench360 (Tab.6), (6. also includes detailed instructions on how to set up the
Justification:
environment and datasets. We will make our codebase publicly available acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7 //nips.cc/ wwtpcppcccpcuudeeeeeeeeeepppeeee httpa///guiddes/deeuubbbbiiiii SonddesubmissioPPoliccc
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed description of the experimental settings in Appendix We also submit the codebase, from which readers can find all the settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Unfortunately, the computational expense for rumning multiple runs of each experiment was too large. We focused on breadth of tasks instead of repeated runs on the same task.
Guidelines:
31

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were caleulated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: In Appendix B.3 we give information computer workers, memory and time.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Ethisss
Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://wwwwp...oollaooccccccccaa
Question:
Answer: [Yes]
Justification: We have read the code of ethics, and confirm that the research conducted conforms with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special considera- tion due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
32

---

Justification:
This is foundational research which is application agnostic.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimesss considerations (e.g.. deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer:[NA)
Justification:
This is foundational research which is application agnostic.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:[Yes Yes]
Justification: This work uses existing datasets and the work corresponding these datasets is cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
33

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For commmon datasets, wwwpssswpppeeeeeeeeeeeeeeeeeeeee thoode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Well-documented code is provided. Please see our answer to Question 5 of the checklist.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooee/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country institution) were obtained?
Question:
Answer: [NA]
Justification:
The research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "1mIVrs0HN2", "reviewer": "Reviewer_duvy", "summary": "This paper introduces einspace, a search space that is designed to hierarchically encode architectures using probabilistic context-free grammars (PCFG). It can encode various architectural components, such as convolutions, attention mechanisms, etc. The authors demonstrate the efficacy of simple blackbox optimizers in einspace to discover architectures that perform competitively on various tasks and datasets.", "questions": "- Could you please discuss further in more details on what are the main advantages of using CFG instead of graph-based or other encodings used in NAS [2]?\n\n\n-- References --\n\n[1] https://proceedings.neurips.cc/paper_files/paper/2023/file/4869f3f967dfe954439408dd92c50ee1-Paper-Conference.pdf\n\n[2] https://proceedings.neurips.cc/paper/2020/file/ea4eb49329550caaa1d2044105223721-Paper.pdf", "limitations": "The authors have addressed the limitations adequately.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "In general the motivation to move beyond the conventional NAS spaces is valid and really important in my opinion. The paper is also very well-written, with simple examples followed by a more generic definition of the search space and interesting application to various tasks and datasets.\nDiscovering novel architectures is a very challenging problem for the NAS community and as far as I know, this has not been achieved yet. Having a complex and versatile search space is the first step towards this goal.\n\nSome other positive aspects of this submission:\n\n- Interesting experiments showing the complexity of the search space and the need of guided search methods (e.g. evolutionary strategies as the authors show), instead of random search, which on previous spaces (e.g. the DARTS one) was shown to perform already well.\n- Available code that fosters reproducibility and enables easier future research on this topic.\n- Extending the prior work of [1] to probabilistic CFG. This enables (1) easier expert prior definitions on the search space, (2) a broader range of algorithms applied on einspace, that can as well incorporate uncertainty estimates of their choices inside the search itself.", "weaknesses": "Despite the vast number of architectures that einspace includes, the major problem is how to search on these spaces in an efficient way. The prior work of [1] used BO with a hierarchical graph kernel (a novelty aspect of that paper), however that was still expensive, especially when moving to image classification tasks. I think defining search spaces that are very complex is very useful task, however, the NAS problem is not only solved by defining the search space alone. The search algorithm is a major component of the whole pipeline, and using blackbox methods to search in such search spaces will be computationally demanding and will still require company scale computation.\n\nBelow I list my major concerns about this submission:\n\n- *Novelty*: I think the paper has some novel aspects compared to [1], e.g. the fact that can encode both attention-mechanisms and convolution, or other operators, or the probabilistic extension of the CFG. However, as the authors mention in the limitation section, it would be great if accompanying the search space, there would be a new proposed search method that can efficiently search on this space by exploiting the PCFG.\n- *Limitations of the search space*: As the authors mention, there are various important architectures that cannot be encoded in einspace.\n- *Claims*: I think the claim (for instance in the abstract) that you find \"novel architectures\" can mean many things. Correct me if I am wrong, but in my opinion einspace still encodes most of the known architectures, and searching on it will only re-discover them or improve on top of those architectures, but it won't find a completely novel architectural component, as for instance ResNets introduced the residual connection back then. \n- *Limited experimental evaluation and results*: The empirical evaluations are not enough in my opinion. The used tasks are simple and one function evaluation is cheap enough to allow blackbox methods to run there. Evaluating on more expensive tasks would require the development of more efficient search strategies that are tailored to einspace. Moreover the results shown in Table 1 are not that impressive considering RE is typically a very strong baseline, so I would have expected it to outperform all other methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Novelty:_ We agree that our core contributions relate to the search space. However we respectfully argue that the introduction of a valuable new space forms a meaningful and valid contribution, independently of presenting a completely novel search strategy. We provide an opportunity for the field to develop new search strategies for our space, and encourage interesting new lines of work. While we acknowledge the impressive work of Schrodi et al. [1], who offer both a new search space framework and search strategy, there are also several recent papers whose main contributions consist solely of a search strategy [2, 3], and this is naturally complemented by papers that contain a search space core contribution. As reviewer **duvy** also notes; our search space highlights the importance of search strategy choice, in relation to space complexity. We believe this further helps to encourage follow-up work on search strategies and we will explicitly strengthen this idea in our revision. Finally, our secondary contribution in this paper is that seeding the search with existing SOTA architectures is a powerful approach that has been previously overlooked. Our expressive search space makes this straightforward as it contains such a diverse set of existing architectures.\n\n[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.  \n[2] ZARTS: On Zero-order Optimization for Neural Architecture Search, Wang et al, NeurIPS 2022.  \n[3] PASHA: Efficient HPO and NAS with Progressive Resource Allocation, Bohdal et al, ICLR 2023.\n\n_Limitations of the search space:_ To date, einspace constitutes one of the most expressive search spaces in the NAS field. We evidence that it combines multiple powerful architectural families in a unified space; including ConvNets, transformers and MLP-only architectures. While we account for a large set of important architectures, we are also clear to communicate that this is a non-exhaustive set. We do not view this as a large limitation, rather, it opens the door for interesting follow-up work, such as support for recurrent operations (e.g. via inclusion of a recurrent module that repeats the computation of the components within). We leave such directions for future work.\n\n_Claims on novel architectures:_ We clarify that einspace has an 'increased ability to find novel architectures'. It includes both examples of existing SOTA architectures, like ResNets and ViTs, but importantly it includes a huge amount of architectures anywhere between and around these existing models. As an example, many previous search spaces consider the self-attention module to be a fixed component, while we model the intricacies of each matrix multiplication, activation, linear layer and branching/merging structures. By changing the number of branches, or the operations done in each branch, we are able to build and discover uncommon architectural components that are on a similar order of complexity as existing self-attention or indeed residual connections. That is; we provide a significantly more granular space within which novel components can be discovered. It is of course true that we impose some constraints on the space, as discussed in Sec. 3.4, but these are relatively weak constraints that don’t significantly reduce expressiveness. We are open to refining the specific phrasing of claims on this point, towards aiding understanding, if the reviewer deems this important.\n\n_Limited evaluation and results:_ We appreciate the reviewer's concern regarding limited evaluation and would firstly note that this is a common problem of previous NAS works, which often only consider a small number of datasets e.g. CIFAR10. To alleviate this concern we present an array of additional experimental results in our rebuttal, towards strengthening our submission. Our updated experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360), and spatial resolutions of up to 256x256 (‘Cosmic’, NB360). Our updated experimental work provides further evidence of the efficacy of our proposed space, including more expensive tasks, and the experimental breadth can be considered more diverse than most previous NAS work. We address the issue regarding development of more efficient search strategies above (see previous point) and accordingly defer evaluation of ImageNet scale tasks to future work.\nAs part of our new results, we also present a direct comparison to hNASBench201,  the hierarchical CFG-based search space from Schrodi et al [1]. These results show how einspace compares favourably to a different search space under the same evolutionary search. Overall, we highlight that our search results on einspace are competitive, even with far weaker priors on the search space.\n\nTable A: Comparing einspace to hNASBench201 (from Schrodi et al [1])\n|| RE (hNASBench201) | RE (Mix) (einspace) |\n|-|-|-|\n| AddNIST | 93.82 | 97.72 |\n| Language | 92.43 | 97.92 |\n| MultNIST | 93.44 | 92.25 |\n| CIFARTile | 58.31 | 62.76 |\n\n_Encodings:_ Our CFG formulation encodes architectures in the form of derivation trees. This explicitly differs from a graph encoding; a derivation tree records the set of design choices that define a flexible macro structure for the architecture, while a graph encoding alternatively provides only a rigid macro-structure-blueprint for representable architectures (e.g. via fixed size adjacency matrices). Through the use of derivation trees, einspace allows for mutations that can effectively alter both the macro structure -and- the individual components of an architecture. Modifications of this class are more difficult if using rigid graph encodings. We will update our manuscript to include further discussion on this point and thank the reviewer for the helpful question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HjmeEIVYJo", "reviewer": "Reviewer_s1qw", "summary": "This paper introduces einspace, a hierarchical space of neural architectures based on parametric probabilistic context free grammar, which is expressive enough to accommodate various state-of-the-art architectures including ResNets and Transformers.\n\nThe Authors further perform Regularized Evolution (RE) search over einspace either searching from scratch or seeding the initial population with state-of-the-art architectures. In particular when seeded with ResNet18, RE generates novel architectures that significantly outperform ResNet18 on multiple datasets from Unseen NAS. Furthermore, RE both seeded with ResNet18 and Mix (a mixture of SOTA architectures) significantly outperform RE from scratch as well as random sampling and random search.", "questions": "How does einspace compare with other hierarchical search spaces in the literature [1] and [2] in terms of performance? To support the advantages of einspace, including expressivity at a reasonable search cost, it would be beneficial to conduct comparative evaluations, at least with RE, across a number of tasks.\n\nDoes it make sense to apply black-box search methods other than RS, RE to einspace, for example the bayesian optimization-based methods BOHNAS and NASBOWL used in [2]?\n\nApproximate search times for RE on datasets of Table.1 are reported in appendix B.3. How do these search times compare with those of other NAS methods listed in Table.1? A similar comparison would also be valuable for the experiments in Table 5.\n\n[1] Hierarchical Representations For Efficient Architecture Search (Simonyan et.al 2018)\n[2] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars (Schrodi et.al 2023)", "limitations": "The limitations are adequately discussed in the final section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This study extends previous research on hierarchical architecture spaces by introducing a more expressive framework capable of accommodating diverse structures including convolutional networks and transformers. \n\nNovelties include imposing minimal priors which facilitate successful search within a highly expressive architecture space. Additionally, grammar rules are equipped with parameters to ensure the generation of valid architectures through the combination of various components. Moreover, the complexity / depth of architectures are regulated by tuning the probabilities assigned to production rules.\n\nThe authors demonstrate through a number of experiments involving ResNet and WideResNet architectures that network performance can be significantly enhanced by utilizing einspace in conjunction with RE, when seeding the initial population with these SOTA architectures.", "weaknesses": "The experiments are currently limited. While the paper does not introduce a search strategy tailored to this search space, it is crucial to emphasize experiments demonstrating the potential for RE, possibly seeded with SOTA networks, to enhance model performance. \n\nThe current evaluations focus on ResNet18 on the Unseen NAS datasets as well as WRN on datasets from NASBench360. Extending this analysis to include a broader range of models, e.g. those listed in Table.1 of Unseen NAS, such as AlexNet and DenseNet, would provide useful insights on the effectiveness of einspace. \n\nMoreover, it would be valuable to explore the application of RE on einspace to improve performance on widely used datasets like CIFAR10, e.g with ResNet and in particular ViT,  given that the paper highlights the capability of einspace to support transformer architectures as an advantage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Limited evaluation:_ We present additional experimental evaluation in this rebuttal on multiple axes. Taking into account all new results, our experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points, to a million (Satellite from NB360), and spatial resolutions of up to 256x256 (‘Cosmic’, NB360). The new results further evidence the efficacy of einspace and our seeded RE and we believe our study is now significantly broader and more diverse than most NAS work we are aware of. We will update our manuscript to include the additional experimental work and thank the reviewer for the suggestion.\n\n_Broader range of models:_ Our rebuttal now provides initial results on RE(DenseNet121) using einspace. We see gains here as well, especially on the Language dataset, where it almost matches the performance of RE(RN18)=96.84. We believe the further exploration of additional models constitutes potentially valuable future work.\n\nTable A: DenseNet121 results\n| | DenseNet121 | RE(DenseNet121) |\n|-|-|-|\n| AddNIST | 94.72 | 94.84 |\n| Language | 91.26 | 96.42 |\n\n_More datasets eg. CIFAR10 with ResNet and ViT:_ Our updated experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360). Our updated experimental work includes more expensive tasks and provides further evidence of the efficacy of our proposed space. The experimental breadth has been meaningfully increased and can be considered to constitute a diverse range of tasks.\n\nWe now present results on CIFAR10, using our regularised evolution seeded with Resnet18, and the mix of architectures (including a ViT). We can see that the improvement in this case is not as significant as for other datasets, an effect we attribute to the broad focus of einspace that goes beyond ConvNets, which have long been optimised for datasets like CIFAR10.\n\nTable B: CIFAR10 results\n| | RN18 | RE(RN18) | RE(Mix) |\n|-|-|-|-|\n| CIFAR10 | 94.91 | 95.31 | 94.73 |\n\n_einspace vs other hierarchical spaces:_ We agree that a direct comparison between einspace and previous CFG-based spaces would be beneficial. We are now happy to report new results comparing RE on einspace vs. RE on hNASBench201 (hierarchical+non-linear) from Schrodi et al [1] in the table below. The results show that our searches in einspace tend to outperform those on hNASBench201, and that both improve upon the baseline network. We thank the reviewer for this suggestion. The full set of results will be included in the updated manuscript.\n\nTable C: Comparing einspace to hNASBench201 (from Schrodi et al. [1])\n|| RN18 | RE (hNB201) | RE (Mix) (einspace) |\n|-|-|-|-|\n| AddNIST | 93.36 | 93.82 | 97.72 |\n| Language | 92.16 | 92.43 | 97.92 |\n| MultNIST | 91.36 | 93.44 | 92.25 |\n| CIFARTile | 47.13 | 58.31 | 62.76 |\n\n_BO in einspace:_ Bayesian optimisation methods are certainly applicable to einspace. Similar to how BOHNAS is used in [1], we think a hierarchical kernel can work well with our CFG formulation. Unfortunately, due to resource and time constraints, we were not able to perform this experiment in time for this rebuttal. We conjecture that BO could provide a sample efficient search and be further improved through seeding with SOTA architectures, like we do with RE. We leave more in depth exploration of advanced search strategies to future work.\n\n_Search times:_ In the table below we include search time results for NAS methods DrNAS, PC-DARTS and RE(Mix), that were originally listed in Tab.1. Note that two numbers are missing due to missing logs from the authors of [2]. We see that, as expected, the gradient-based DrNAS and PC-DARTS are significantly faster compared to the black box RE(Mix) which trains 500 networks independently. We update our manuscript to report these results and add some further discussion on the tradeoff between diversity and time complexity in light of these observations, towards providing the reader with additional insight into the related issues. We thank the reviewer for the useful question.\n\n[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.  \n[2] Insights from the Use of Previously Unseen Neural Architecture Search Datasets, Geada et al, CVPR 2024.\n\nTable D: Time-consumption (in hours)\n| AddNIST | Language | MultNIST | CIFARTile | Gutenberg | Isabella | GeoClassing | Chesseract |\n|-|-|-|-|-|-|-|-|\n| DrNAS | 10 | 9 | 11 | 25 | 13 | 59 | 23 | 10 |\n| PC-DARTS | 4 | - | 5 | 12 | 9 | 30 | - | 2 |\n| RE(Mix) | 55 | 71 | 32 | 62 | 42 | 80 | 65 | 42 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NsaPG2YbVX", "reviewer": "Reviewer_sBZH", "summary": "The manuscript presents \"einspace,\" a novel neural architecture search (NAS) space based on a parameterized probabilistic context-free grammar (CFG). The authors aim to address the limitations of current NAS methods by proposing a highly expressive search space that supports diverse network operations and architectures of varying sizes and complexities.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces a unique NAS search space, \"einspace,\" which is designed to be highly expressive, accommodating a wide range of architectures, including those not traditionally found in NAS literature.\n\n2. The work contributes to the ongoing discussion on the role of search space expressivity and strategic search initialization in NAS, potentially paving the way for future research in this direction.", "weaknesses": "1. While the authors claim to introduce a new search space, the manuscript's Method Section appears to describe a set of rules that break down operators into smaller elements, which could be misinterpreted as a mere decomposition rather than a novel search space construct. This raises questions about the actual size and scope of the proposed search space, which would benefit from further clarification.\n\n2. Section 3.7 is not clearly articulated, and the authors are encouraged to provide a simplified explanation of its main content to aid reader comprehension.\n\n3. The primary goal of the proposed method is to design a highly expressive yet constrained search space. To substantiate this claim, it would be beneficial to conduct searches and validating on larger-scale datasets, such as ImageNet, which could more effectively demonstrate the superiority of the proposed search space. The current experiments on smaller datasets may not fully showcase the advantages of the search space.\n\n4. The experimental settings are somewhat unclear. It appears that the authors search within the proposed space and then validate the discovered network structures on other datasets, such as those from NAS-Bench-360. However, NAS-Bench-360 imposes constraints on the design space that may not be compatible with the structures proposed by the authors. Further clarification on how the proposed space's network structures are adapted or validated on NAS-Bench-360 is needed to ensure the experiments are methodologically sound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Size and scope of the search space:_ We thank the reviewer for the comment however believe this point to be largely a matter of semantics. By decomposing coarse grained building blocks into atomic operators we meaningfully increase the size, complexity and flexibility of the search space. We evidence that this allows points in our search space to embody (common) architectures that cannot be represented in previously explored spaces. We note that multiple co-reviewers are impressed by the size and scope of our proposed space (ZVSn, wLBZ) and that our experiments serve to evidence the complexity of the search space (duvy).\n\n_Clarity of Section 3.7:_ We thank the reviewer for the opportunity to provide a simplified explanation. If we consider network architectural design to be a procedural, decision-making process, then the crux of the message in Sec. 3.7 is that: **we can introduce a probabilistic choice at each step in this process, to help us achieve the desirable level of architecture complexity**. At each step, there is a chance to continue building the network (adding more components) or to stop and finalise a part of it. The probability P(M -> C|M) is particularly important for this. Further, guided by previous work on PCFGs, we can carefully adjust these probabilities to provably control the average complexity of the generated architectures. In essence, the probabilistic approach strikes a balance between creating deep, complex networks and shallow, simpler ones. This helps to explore a wider range of architectural possibilities while maintaining control over the overall complexity of the generated models. We refine our phrasing of Sec. 3.7, towards further aiding reader understanding on this point.\n\n_Larger-scale datasets:_ We appreciate the reviewer's concern regarding limited evaluation and would firstly note that this is a common problem of previous NAS works, which often only consider a small number of datasets e.g. CIFAR10. To alleviate this concern we present an array of additional experimental results in our rebuttal, towards strengthening our submission. Our updated experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360). Our updated experimental work provides further evidence of the efficacy of our proposed space, including more expensive tasks, and the experimental breadth can be considered more diverse than most previous NAS work that we are aware of. We address the issue regarding development of more efficient search strategies above (see reply to **duvy**) and accordingly defer evaluation of ImageNet scale tasks to future work.\n\n_Unclear experimental settings:_ We think there may be a misunderstanding on how we performed our experiments on NAS-Bench-360 for Table 5. These results are run independently to those in Table 1, and there is no transfer or adaptation between tasks. Throughout our evaluation, every search is performed on the same dataset that the evaluation is performed on. Thank you for highlighting this, we will revise the manuscript to make it clearer.\n\nSome datasets in NAS-Bench-360 do indeed impose some additional constraints on the search. The 5 tasks we considered for the submitted version were the easiest to use and required no adjustments to the search space. The Cosmic and Darcy Flow datasets simply needed a dense prediction output layer instead of a classifier.\n\nIn our updated results in this rebuttal, we also consider some 1D datasets within the benchmark, and this required us to adjust the einspace CFG to make it compatible. Primarily, these adjustments include replacing our decomposed convolutional operators with 1-dimensional versions. The details of all adjustments will of course be added to the manuscript along with the results on these 1D tasks.\n\nTable A: Additional datasets from NAS-Bench-360 (one-dimensional)\n| | WRN | DARTS (GAEA) | Expert | RE(WRN) einspace |\n|-|-|-|-|-|\n| Satellite | 15.29 | 12.51 | 19.80 | 12.55 |\n| DeepSea | 0.45 | 0.36 | 0.30 | 0.36 |\n\nWe thank the reviewer for the detailed comments and suggestions that enable us to update our manuscript towards further improving clarity. We hope we have addressed all fundamental questions raised and, in light of our clarifications, we invite the reviewer to consider increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5dDXOTj15I", "reviewer": "Reviewer_wLBZ", "summary": "This paper proposes a new search space named einspace based on a parameterized probabilistic context-free grammar for neural architecture search. In contrast to conventional search space composed of high-level operations and modules such as recurrent layer, convolutional layer, and activation layer, einspace consists of more fundamental operations, such as clone, summation, permutation, and activation. This einspace can be defined by a context-free grammar and can represent the neural architecture as the derivation tree. The experiments on Unseen NAS and NAS-Bench-360 demonstrate the advantage of this search space.", "questions": "See weaknesses.", "limitations": "The authors have discussed the limitations in their paper. Besides, there are no potential negative societal impacts of this work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and is easy to follow.\n2. The idea of fundamental operations and context-free grammar for search space is great and interesting.\n3. This search space has the advantage of designing new architectures based on existing SOTA architectures such as ResNet, Wide-ResNet, ViT, and MLP-Mixer.", "weaknesses": "Despite the strengths of this paper, I still have some concerns that prevent me from confidently recommending acceptance:\n1. The first problem is about the novelty. Since einspace is not the first search space based on CFG, and the fundamental operations of einspace are common in the existing search space, the novelty of einspace may not reach my expectations. Although the fundamental operations are different from and more expressive than the high-level operations and rigid structures of existing search space, these fundamental operations are also commonly used in existing search space. Furthermore, it is complicated to represent convolution and skip connection using these operations and it is impossible to represent recurrent computation, as the authors discussed in the Limitation section.\n2. The second problem is about the tradeoff between diversity and time complexity of the search space. It would be better to analyze the time complexity or compare the time consumption between einspace and others, such as the space of DARTS. \n3. From the experimental results, the architectures searched in einspace do not seem to be that competitive compared to other methods, as shown in Table 1. I think the results are also influenced by the search strategy. Is it possible to apply RL or differentiable search strategies to this search space? If possible, the author can give a table listing which search strategies are suitable for einspace and which search strategies are better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Novelty:_ We acknowledge previous CFG-based studies exist, however we would highlight that we are the first work to introduce the concept of pCFGs for search space design, which we show brings advantages in controlling the expected architecture complexities. We are also the first to unify multiple architectural families into one single expressive space. We provide direct experimental evidence, namely that regularised evolution seeded with diverse SOTA architectures performs competitively across a broad range of datasets. We believe that this constitutes a meaningful step forward, beyond previous work on CFG based search space design.\n\nThe fundamental operations in einspace are atomic, and rather than focussing on the fact that they are pre-existing, we highlight that the novelty of our work stems from our thinking around the required expressiveness of the search space. The unique manner in which we organise and leverage such atomic operators results in the emergence of new search spaces that contribute a previously unseen expressiveness for NAS-based tasks.\n\n_Complexity of components:_ We agree with the reviewer that existing hand-designed high-level operators (e.g. convolutions, skips) often require a complicated composition of atomic operators and that this typically necessitates specific human expertise. This observation is actually at the very crux of our argument. Rather than assuming that such coarse operators are optimal, and hiding their inner workings from the model, we instead enable the autonomous construction and discovery of such related operators.\n\n_Recurrence missing:_ While we account for a large set of important architectures, we are also clear to communicate that this is a non-exhaustive set. We do not view this as a large limitation, rather, it opens the door for interesting follow-up work, such as support for recurrent operations (e.g. via inclusion of a recurrent module that repeats the computation of the components within). We leave such directions for future work.\n\n\n_Tradeoff between diversity and time complexity:_ We thank the reviewer for the useful suggestion. In the table below we include search time results for NAS methods DrNAS, PC-DARTS and RE(Mix), that were originally listed in Tab.1. Note that two numbers are missing due to missing logs from the authors of [2]. We see that, as expected, the gradient-based DrNAS and PC-DARTS are significantly faster compared to the black box RE(Mix) which trains 500 networks independently. We update our manuscript to report these results and add some further discussion on the tradeoff between diversity and time complexity in light of these observations, towards providing the reader with additional insight into the related issues.\n\nTable D: Time-consumption (in hours)\n| AddNIST | Language | MultNIST | CIFARTile | Gutenberg | Isabella | GeoClassing | Chesseract |\n|-|-|-|-|-|-|-|-|\n| DrNAS | 10 | 9 | 11 | 25 | 13 | 59 | 23 | 10 |\n| PC-DARTS | 4 | - | 5 | 12 | 9 | 30 | - | 2 |\n| RE(Mix) | 55 | 71 | 32 | 62 | 42 | 80 | 65 | 42 |\n\n_Competitiveness:_ We highlight that, in Table 1, RE(RN18) and RE(Mix) achieve average ranks that are only beaten by BonsaiNet, which shows the high performance of our approach. Additionally, as part of our new results, we also present a direct comparison to hNASBench201, the hierarchical CFG-based search space from Schrodi et al [1]. These results show how einspace compares favourably to a different search space under the same evolutionary search. Overall, we highlight that our search results on einspace are competitive, even with far weaker priors on the search space.\n\nTable A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])\n|| RE (hNASBench201) | RE (Mix) (einspace) |\n|-|-|-|\n| AddNIST | 93.82 | 97.72 |\n| Language | 92.43 | 97.92 |\n| MultNIST | 93.44 | 92.25 |\n| CIFARTile | 58.31 | 62.76 |\n\n_Potential search strategies:_ We thank the reviewer for the idea of a table clarifying the potential search strategies for einspace. Like hNASBench201 from Schrodi et al [1], einspace is too large for one-shot methods that require all architectures to be instantiated into a single supernet. However, there are other weight-sharing methods relating to MCTS and SPOS that may be applicable.\n\nTable A: Comparison of einspace with existing search spaces. † Gradient-based search is difficult in these spaces due to their size, but other weight-sharing methods may be available. *The paper introducing hNASBench201 [1] also considers versions of the search space for Transformer language models.\n\n| | Type | Size | Focus | RS | RE | RL | BO | Gradient-based |\n|-|-|-|-|-|-|-|-|-|\n| einspace | pCFG | Huge | ConvNets, Transformers, MLP-only | ✓ | ✓ | ✓ | ✓ | † |\n| hNASBench201 | CFG | 10^446 | ConvNets* | ✓ | ✓ | ✓ | ✓ | † |\n| NASBench201 | Cell | 10^4 | ConvNets | ✓ | ✓ | ✓ | ✓ | ✓ |\n| NASBench101 | Cell | 10^5 | ConvNets | ✓ | ✓ | ✓ | ✓ | ✓ |\n| DARTS | Cell | 10^18 | ConvNets | ✓ | ✓ | ✓ | ✓ | ✓ |\n\nIn light of our responses and improved evaluation, we invite the reviewer to consider increasing their score.\n\n[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.  \n[2] Insights from the Use of Previously Unseen Neural Architecture Search Datasets, Geada et al, CVPR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OQcRi7lkXr", "reviewer": "Reviewer_ZVSn", "summary": "This paper proposes a new type of neural architecture search (NAS) search space that goes beyond standard, small NAS search spaces. Most popular search spaces in NAS are quite small, and include architectures that include known motifs because they are built around standard architectures. The authors point out that this is why NAS has failed to produce fundamentally new architectures, and instead, that most advancements in neural network architectures are from expert driven hand-design. Their search space, einspace, is a probabilistic context-free grammar (CFG) of fundamental operations.", "questions": "- Out of curiosity, what do the authors view as the key reason for einspace not being able to express RNNs and SSMs? This is a valid design decision, but it also seems as though it should be fairly straightforward to design a version of einspace that supports recurrence (I could be mistaken about this). \n- Why did the authors choose the 5 NAS-Bench-360 tasks that were used in their evaluation? Does the method work on the other tasks?", "limitations": "The authors clearly state the limitations, and even discuss avenues for future work. This includes extending the search space to handle recurrent architectures and state space models.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written, well-motivated, and easy to follow. \n- The paper is clear in that its innovation is related to search space design, with many suggestions for possible search algorithms. The search space itself is quite impressive, and includes both convolutions as well as self-attention operations (built-up from more fundamental building blocks). \n- The results of search seem impressive -- while einspace does not always yield stronger architectures compared to other methods or hand-designed baselines, it does sometimes yield significantly better architectures. Furthermore, the comparison to the random search baseline is appreciated. \n- The search space supports initialization using existing architectures -- this is important for setting priors for problems in which good architectures are already known.", "weaknesses": "- The resulting architectures in Table 1 do not always outperform SOTA architectures, but when they do, the improvement can be significant. On the other hand, there does not seem to be a comparison of the computational costs involved -- this would be helpful to include, especially as the search space is quite large. \n- The authors include results on NAS-Bench-360, which is great, however the results are incomplete and it is unclear why the authors only evaluate on 5 out of the 10 tasks. This seems particularly important as the motivation of einspace is similar to the line of work related to NAS-Bench-360. \n- In order to make search tractable, it seems like many assumptions are made on the priors on the search space. This makes sense, however, it would be interesting to explore variations on these choices more in-depth. \n\nIf the authors adequately address these concerns, I will gladly raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Computational costs:_ We thank the reviewer for the useful suggestion. In the table below we include search time results for NAS methods DrNAS, PC-DARTS and RE(Mix), that were originally listed in Tab.1. Note that two numbers are missing due to missing logs from the authors of [2]. We see that, as expected, the gradient-based DrNAS and PC-DARTS are significantly faster compared to the black box RE(Mix) which trains 500 networks independently. We update our manuscript to report these results and add some further discussion on the tradeoff between diversity and time complexity in light of these observations, towards providing the reader with additional insight into the related issues.\n\nTable D: Time-consumption (in hours)\n| AddNIST | Language | MultNIST | CIFARTile | Gutenberg | Isabella | GeoClassing | Chesseract |\n|-|-|-|-|-|-|-|-|\n| DrNAS | 10 | 9 | 11 | 25 | 13 | 59 | 23 | 10 |\n| PC-DARTS | 4 | - | 5 | 12 | 9 | 30 | - | 2 |\n| RE(Mix) | 55 | 71 | 32 | 62 | 42 | 80 | 65 | 42 |\n\n_NAS-Bench-360 tasks missing:_ We appreciate the reviewer's concern regarding our original NAS-Bench-360 evaluation. Due to resource and time constraints we did not manage to have all NAS-Bench-360 results ready. The five tasks we reported in our original submission were the most amicable to our search space and required no adjustments.\n\nIn this rebuttal, we present further results on 1D datasets within the benchmark, which required us to adjust the einspace CFG to make it compatible. Essentially, these adjustments include replacing our decomposed convolutional operators with 1-dimensional versions. We add the results for these 1D tasks, along with details of these minor adjustments, to our updated manuscript. The remaining three datasets, within the benchmark, are in progress and will also be included for the camera-ready submission.\n\nTable A: Additional datasets from NAS-Bench-360 (one-dimensional)\n| | WRN | DARTS (GAEA) | Expert | RE(WRN) einspace |\n|-|-|-|-|-|\n| Satellite | 15.29 | 12.51 | 19.80 | 12.55 |\n| DeepSea | 0.45 | 0.36 | 0.30 | 0.36 |\n\nIn the rebuttal in general, we present an array of additional experimental results, towards strengthening our submission. Our updated experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360), and spatial resolutions of up to 256x256 (‘Cosmic’, NB360). We provide further evidence of the efficacy of our proposed space, including more expensive tasks, and the experimental breadth can be considered of high diversity. We believe this serves to strengthen our motivation for einspace, that is indeed aligned with works related to NAS-Bench-360 and we thank the reviewer for the suggestion.\n\n_Exploring design priors of einspace:_ We agree with the reviewer that this provides an additional interesting direction for exploration. Towards exploring this aspect further, we present results comparing einspace to the previous, CFG-based, hNASBench201 from Schrodi et al. This allows for an initial study on the effects of our search space design choices and, in particular, the increased expressiveness compared to hNASBench201. These results show how einspace compares favourably to a different search space under the same evolutionary search. Overall, we highlight that our search results on einspace are competitive, even with far weaker priors on the search space.\n\nTable A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])\n|| RE (hNASBench201) | RE (Mix) (einspace) |\n|-|-|-|\n| AddNIST | 93.82 | 97.72 |\n| Language | 92.43 | 97.92 |\n| MultNIST | 93.44 | 92.25 |\n| CIFARTile | 58.31 | 62.76 |\n\nWe update our manuscript with these findings with the aim to further improve reader understanding for choices relating to search space priors and thank the reader for the suggestion.\n\nQuestions:\n\n_Recurrence missing:_ The reviewer raises an interesting question and we agree that recurrence, and related operations, make for an appealing einspace extension. We believe recurrent operations can likely be integrated via the inclusion of a recurrent module that repeats the computation of the components within it; however we leave more detailed exploration of this direction to future work.\n\n_Why not full NAS-Bench-360?:_ As already mentioned, the reasons for only including 5 out of 10 NAS_Bench-360 tasks was due to limited time and compute resources, and that some of the tasks require further adjustments to our CFG codebase. We evidence here that we have been able to successfully extend our experimental work on this axis and further, that the full set of tasks will be included in any camera-ready version.\n\nWe thank the reviewer for detailed comments that (1) thoroughly test the experimental and theoretical underpinnings of our ideas and (2) enable us to update our manuscript towards further improving clarity.\n\nWe hope we have addressed all fundamental questions raised and, in light of our clarifications, we invite the reviewer to consider increasing their score.\n\n\n[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3hfeDX5NIQ", "reviewer": "Reviewer_c4rx", "summary": "Neural Architecture Search (NAS) often produces incremental improvements due to limited diversity in traditional search spaces. To address this, the paper introduces \"einspace,\" a versatile search space built from probabilistic context-free grammar (CFG). Einspace supports a wide range of architectures and operations, enabling the modelling of convolutions and attention mechanisms. Experiments on Unseen NAS datasets show that einspace can discover novel architectures from scratch and with grammars containing different foundation model architectures.", "questions": "Questions:\n\n1, The paper claims that it is the first one to represent foundation model architectures with a NAS search space. However [1] already represented a language model using CFGs. Also [1] can potentially present any architecture (ViT, MLPMixer). Is my understandng correct that this paper introduces a PCFG on [1] to  limit the search space size? I am also currently lacking a CFG which is a union of multiple foundation model architectures in a single grammar. Could the authors provide an example for this?\n\n2. The paper uses random search and evo search, both of which are sample inefficient and do not scale well with the size of the dataset and search space. How do more sample efficient bayesian optimization algorithms perform here?\n\n3. Currently the standard for small unseen datasets is finetuning a pretrained model on the smaller downstream task. Could the authors should ideally compare to for eg: simply finetuning a pretrained vision transformer or efficientnet on the unseen dataset?\n\n4. Evaluation on larger datasets is missing. Architectures which are able to exploit dataset patterns change depending on the scale of datasets available (eg: Vision transformers [2]). Are the architectures discovered significantly different from the existing ones even when the dataset is scaled up. How efficient is the search on this scale?\n\n5. Could you present parameter and FLOPs counts in Table 1?\n\n6. How is the branching rate hyperparameter set for a newer search space?\n\n\n\n\n\n[1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch.\n\n[2] Raghu, M., Unterthiner, T., Kornblith, S., Zhang, C. and Dosovitskiy, A., 2021. Do vision transformers see like convolutional neural networks?. Advances in neural information processing systems, 34, pp.12116-12128.", "limitations": "I do think that the paper opens up newer avenues of research in neural architecture search, however, given the limited evaluation I do have concerns about the applicability of the method. Check weakness and questions for details on the limitations. I am happy to raise my score if each of my concerns are appropriately addressed.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is written very clearly and examples of CFGs aid understanding of the paper. \n2. The authors release code which improves the reproducibility of the work and potential future work \n3. While I do think that this paper opens up new opportunities and challenges for scaling NAS from scratch to larger spaces and datasets, I have questions (check questions) for the authors to improve the quality of their evaluations and make a stronger case for the practical applicability of einspace.", "weaknesses": "1. **Contribution**: Currently I fail to see the main contribution of the paper to the area to \"searching architectures from scratch\" [1]. I find the representation  properties of the search space to be same as [1] (except the use of probabilistic CFGs). Moreover, the search schemes proposed random and evolutionary search are not very sample efficient in such large spaces compared to [1], which uses bayesian optimization with graph kernels. \n2. **Evaluation**: The paper does not compare to natural baselines like [1]. Moreover I find the evaluation to be quite limited in terms of the datasets evaluated and the base models finetuned/evaluated on. \n\n[1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and respond to each point below.\n\n_Contribution:_ There are three key differences between einspace and the CFG-based spaces of Schrodi et al [1].\n- Our space unifies multiple architectural families (ConvNets, Transformers, MLP-only) into one single expressive space while [1] present variations of their spaces centred around ConvNets only, with a separate instantiation focusing only on Transformers.\n- einspace extends to probabilistic CFGs. This constitutes a significant contribution by enabling a set of benefits that include (i) allowing experts to define priors on the search space via probabilities, and (ii) enabling a broader range of search algorithms that incorporate uncertainty estimates inside the search itself.\n- einspace contains recursive production rules (e.g. M -> MM), meaning the same rule can be expanded over and over again, providing a very high flexibility in macro structures. [1] instead focuses on fixed hierarchical levels that limits the macro structure to a predefined (though very large) set of choices.\nWe will ensure that these differences are better highlighted in the manuscript.\n\n_Comparing to baseline search space:_ We appreciate the reviewer’s concern and provide a comparison with the baseline of [1]. Table A presents results comparing einspace to the CFG-based, hNASBench201 from Schrodi et al. This allows for a fairer and more direct comparison of the search spaces. These results show how einspace compares favourably under the same evolutionary search. Overall, we highlight that our search results on einspace are competitive, even with far weaker priors on the search space.\n\nTable A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])\n||RE(hNASBench201)|RE(Mix)(einspace)|\n|-|-|-|\n|AddNIST|93.82|97.72|\n|Language|92.43|97.92|\n|MultNIST|93.44|92.25|\n|CIFARTile|58.31|62.76|\n\n_Foundation model architectures:_ We apologise for any confusion caused, as we do not wish to claim that we are the first to represent foundation models within a NAS search space. We claim that we are the first to represent multiple architectural families (specifically ConvNets, Transformers, MLP-only) in a unified search space. The spaces presented in [1] focus on either ConvNets or Transformers, but not both in a unified space. If there is a particular wording that caused this confusion, we are happy to rephrase it to be more clear.\n\n_PCFG extension:_ See previous answer above.\n\n_Unified grammar:_ We apologise for any confusion here too. We only present one grammar in the paper, and it is shown in section 3.3. This grammar is expressive enough to be the union of multiple foundation model architectures in a single grammar. All experiments and all figures in the paper are from architectures generated by that grammar. Please let us know if any specific wording caused this confusion, and we will be happy to improve it.\n\n_Sample efficiency and BO:_ Due to the large set of experimental requests and queries, suggested by our six reviewers, we unfortunately did not have enough time nor spare compute to explore sample efficient BO during the time limited rebuttal period. We conjecture that such sample efficiency strategies may combine well with our large search space and provides for an exciting future direction.\n\n_Finetuning pretrained models:_ We thank the reviewer for their suggestion, and agree that this is an interesting comparison. Below we present results for the finetuning of the ResNet18 and EfficientNet-B0 architectures on the Unseen NAS datasets. The results show that we can often get a significant boost from finetuning, but for datasets that differ too much from the pretraining task (ImageNet) such as Language and Gutenberg, there is actually a degradation in performance. These are in fact the datasets where we see some of the biggest improvements from using einspace, and it highlights the expressiveness of our new search space.\n\nTable B: Finetuning pretrained models\n\n||RN18|FT(RN18)|FT(EfficientNetB0)|\n|-|-|-|-|\n|AddNIST|93.36|94.69|94.77|\n|Language|92.16|90.31|90.62|\n|MultNIST|91.36|91.12|91.90|\n|CIFARTile|47.13|52.26|79.32|\n|Gutenberg|43.32|42.52|42.08|\n|Isabella|63.65|62.35|67.46|\n|GeoClassing|90.08|90.70|95.81|\n|Chesseract|59.35|61.29|62.24|\n\n_Larger datasets:_ In the rebuttal we present an array of additional experimental results. Our updated evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360), and spatial resolutions of up to 256x256 (‘Cosmic’, NB360). Unfortunately we did not have enough time nor spare compute to explore e.g. ImageNet, but we believe our evaluation is now broad enough to highlight the expressiveness and utility of einspace.\n\n_Parameter counts and FLOPs:_ Thank you for this suggestion, parameter counts are now presented in Table C.\n\nTable C: Parameter counts\n\n||AddNIST|Language|MultNIST|CIFARTile|Gutenberg|Isabella|Geoclassing|Chesseract|\n|-|-|-|-|-|-|-|-|-|\n|DrNAS|4M|4M|5M|3M|3M|4M|4M|4M|\n|PC-DARTS|3M|-|3M|3M|2M|2M|-|2M|\n|RE(Mix)|20M|1M|25M|5M|1M|5M|4M|11M|\n\n_Setting branching rate hyperparameter:_ We assume the reviewer is asking “how is the branching rate hyperparameter set for a new task?”. In this case, we can confirm that the branching rate is set only once, based on the theoretical guidance of Section 3.7. We highlight that this hyperparameter remains constant across -all- of our experiments and tasks. We believe this evidences the generalisability of our search space, and its ease of use. If we have misunderstood the query, we would ask the reviewer to further clarify on this point. Thank you.\n\nWe thank the reviewer for detailed comments that help us improve our manuscript. We have provided additional experiments that significantly extend our evaluation. We hope we have addressed all fundamental questions raised and, in light of our clarifications, we ask that the reviewer considers increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the six (!) reviewers for their time and valuable comments that improve the quality of our work. We are encouraged by the positive feedback, namely:

- Multiple reviewers appreciate the novelty of our core idea, to move beyond conventional NAS spaces (duvy, wLBZ, ZVSn)
- That our experimental results evidence our method efficacy (duvy, s1qw, ZVSn)
- Our work opens up new opportunities and future NAS research directions (sBZH, c4rx)
- A majority of reviewers note that the paper is well-written, well-motivated, and easy to follow (duvy, wLBZ, ZVSn, c4rx)
- Our use of helpful examples and clarity of explanation (duvy, c4rx)
- Multiple reviewers appreciate that we release our source code preemptively during the review period (duvy, c4rx)

We address individual reviewers’ concerns below inline and also offer a communal reply here in order to address several common and important points.

**Novelty**: Our core contribution is a novel search space, which we argue is a meaningful and valid contribution, independently of presenting a completely novel search strategy. This provides an opportunity for the community to develop new search strategies for our space and encourages interesting new lines of work. That said, as a starting point, we have highlighted the effectiveness of seeding search with SOTA architectures, which is straightforward given the flexibility of our space. Our space uses a CFG, as in the excellent work of [1], but is distinct for several key reasons:

- Our space unifies multiple architectural families (ConvNets, Transformers, MLP-only) into **one single expressive space** while [1] present variations of their spaces centred around ConvNets only, with a separate instantiation focusing only on Transformers.
- einspace extends to probabilistic CFGs. This constitutes a significant contribution by enabling a set of benefits that include (i) allowing experts to define priors on the search space via probabilities, and (ii) enabling a broader range of search algorithms that incorporate uncertainty estimates inside the search itself.
- einspace contains recursive production rules (e.g. M &#8594; MM), meaning the same rule can be expanded over and over again, providing a very high flexibility in macro structures. [1] instead focuses on fixed hierarchical levels that limits the macro structure to a predefined (though very large) set of choices. We will ensure that these differences are better highlighted in the manuscript.

Further to this, we present a direct comparison to hNASBench201, the hierarchical CFG-based search space from [1]. These results show how einspace compares favourably to a different search space under the same evolutionary search. Overall, we highlight that our search results on einspace are competitive, even with far weaker priors on the search space.

Table A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])
|| RE (hNASBench201) | RE (Mix) (einspace) |
|-|-|-|
| AddNIST | 93.82 | 97.72 |
| Language | 92.43 | 97.92 |
| MultNIST | 93.44 | 92.25 |
| CIFARTile | 58.31 | 62.76 |


**Experimental results**: We appreciate reviewer concerns regarding experimental evaluation, as this is a common problem in NAS work. To alleviate this concern we present an array of additional experimental results in our rebuttal, towards strengthening our submission. Our updated experimental evaluation now covers 16 different datasets, with sizes ranging from thousands of data points to over a million ('Satellite', NB360), and spatial resolutions of up to 256x256 (‘Cosmic’, NB360). Our updated experimental work provides further evidence of the efficacy of our proposed space, including more expensive tasks, and the experimental breadth can be considered more diverse than most previous NAS work.

Table B: Additional datasets from NAS-Bench-360 (one-dimensional)
| | WRN | DARTS (GAEA) | Expert | RE(WRN) einspace |
|-|-|-|-|-|
| Satellite | 15.29 | 12.51 | 19.80 | 12.55 |
| DeepSea | 0.45 | 0.36 | 0.30 | 0.36 |

[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.

Meta-review: The paper received reviews from six reviewers: three weak accepts, one borderline accept, and two borderline rejects. Most reviewers recognized the significance of expanding the NAS search space, which is a valuable contribution to the NAS field. The main concerns raised were related to the searching strategy and the need for more comprehensive evaluation on larger datasets.

The authors performed exceptionally well in their rebuttal, addressing most concerns by presenting additional evaluation results and explanations. Although two reviewers initially shown strong rejection attitude, they increased their scores after considering the rebuttal.

After reviewing the paper and the rebuttal, AC believes that the overall strengths outweigh the weaknesses and recommends acceptance.  This decision has been discussed with SAC. For the camera-ready version, the authors should incorporate all key results presented in the rebuttal and make significant improvements to the paper’s presentation.
Decision: Accept (poster)