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_cc_2024_Conference
Published: 2024-05-09 14:35:58

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.

Main paper: 
 introduction: 
 The goal of neural architecture search (NAS) [14, 42] is to automatically find a network architecture for a given task, removing the need for expensive human expertise. NAS uses (i) a defined search space of all possible architectures that can be chosen, and (ii) a search algorithm e.g. [68, 58, 40] 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 [56] , or perhaps a (manually designed) MLP-Mixer [53] , or even a (manually designed) ResNet [19] . Why isn't NAS being used instead?ViT MLP-Mixer Derivation tree Derivation tree Derivation treeFigure 1 : Three state-of-the-art 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 on other node colouring. Best viewed with digital zoom.Part of the problem is that most NAS search spaces are not expressive enough, relying heavily on high-level operations and rigid structures. For example in the DARTS [30] search space, each architecture consists of repeating cells; each cell is a 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] -making it impossible to discover anything beyond ConvNet characteristics. Indeed, random search [63, 27] is often a 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 ex nihilo approach to search space construction. In AutoML-Zero [41] 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] or 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: a search space that is both highly expressive, and in which we can straightforwardly use existing tried-and-tested architectures as powerful priors for search. To this end, we propose einspace: a 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 as well as macro and micro structures. With its expressivity, the space contains disparate state-of-the-art architectures such as ResNets [19] , transformers [56, 13] and the MLP-Mixer [53] , as shown in Figure 1 . 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 a broad class of fundamental network operations and further describe how such elements can be 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 [16] -eight diverse classification tasks including vision, language, audio, and chess problems-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 human-designed architectures to initialise the search, we consistently find both large performance gains and significant architectural changes. Code to reproduce our experiments is available at https://github.com/linusericsson/einspace.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 spaces-focusing on expressiveness and incorporating the priors of existing state-of-the-art architectures-has the potential to drive NAS research towards a new paradigm.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer:[Yes] Justification: The main contribution is our search spaceeinspace-which is described in detail in the paper, and can be 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 Table 1 . We have included aspirational goals as motivation, and made it clear that we believe this work is a step towards achieving them. 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 to 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. 
background: 
 Neural architecture search The search space used in NAS has a significant impact on results [63, 65] . This has facilitated the need to investigate search space design alongside the actual search algorithms [37] . Early macro design spaces [24, 68] made use of naive building blocks while accounting for skip connections and branching layers. Further design strategies have looked at chain-structured [3, 4, 6, 43] , cell-based [69, 66, 30, 15] 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 [45] and topological evolutionary strategies [35] . Additional work on search spaces have proposed new candidate operations and module designs such as hand-crafted multi-branch cells [51] , tree-structures [3] , shuffle operations [32] , dynamic modules [22] , activation functions [38] and evolutionary operators [10] . In AutoML-Zero [41] , the authors try to remove human bias from search space construction by defining a space of basic mathematical operations as building blocks.The pioneering work of [47] 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 a balance between the level of complexity in the search space and incorporating components from diverse state-of-the-art architectures. Crucially, our space enables flexibility in both macro structure and at the individual operation level. While previous search spaces can be instantiated for specific architecture classes [30, 12] , our single space incorporates multiple classes in one, ConvNets, transformers and MLP-only 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 [34, 58] , reinforcement learning [66, 68, 69] and genetic algorithms [5, 39, 40] . A popular thread of work, towards improving computational efficiency via amortising training cost, involves the sharing of weights between different architectures via a supernet [1, 3, 9, 18, 30, 31] . Efficiency has been further improved by sampling only a subset of supernet channels [60] , thus reducing both space exploration redundancies and memory consumption. Alternative routes to mitigating space requirements have considered both architecture and operation-choice pruning [7, 15] . We however highlight that random search often proves to be a very strong baseline [27, 63] ; a consequence of searching within narrow spaces. This is commonly the case for highly engineered search spaces that contain a high fraction of strong architectures [59] . Contrasting this, in our einspace we observe that random search across many tasks performs poorly, underpinning the value of a good search strategy for large, diverse search spaces [2, 41] .A context-free grammar (CFG; [20] ) is a tuple (N,Σ,R,S), where N is a finite set of non-terminal symbols, Σ is a finite set of terminal symbols, R is the set of production rules-where each rule maps a non-terminal A ∈ N to a string of non-terminal or terminals A → (N ∪Σ) + -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 a production, starting with the rules containing the starting symbol, we can generate strings within the grammar. CFGs can be parameterised: each non-terminal, in each rule in R, is annotated with parameters p 1 ,...,p n that influence the production. These parameters can condition production, based on an external state or contextual information, thus extending the power of the grammar.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We have a dedicated Limitations section in our paper. Please see Section 5 for more details. Guidelines:• The answer NA means that the paper has no 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 a 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, e.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 on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best 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 to not penalize honesty concerning limitations. 
einspace: a search space of fundamental operations: 
 Our neural architecture search space, einspace2 , is introduced here. Based on a parameterised PCFG, it provides an expressive space containing many state-of-the-art 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 a running example we will be constructing a simple convolutional block with a skip connection within einspace, explaining at each stage how it relates to the architecture. The block will consist of a convolution, a normalisation and an activation, wrapped inside a skip connection.Each fundamental operation within einspace takes as input a tensor, either passed as input to the whole network or an intermediate tensor from a previous operation, and operates on 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 in a network architecture. The terms one-to-one, one-to-many and many-to-one below refer to the number of input and output tensors of the functions within that group. For full details of the operations, see Appendix A.2Branching. 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.Routing. One-to-one functions that change the shape or the order of the content in a tensor without altering its information. Examples include axis permutations as well as the im2col and col2im operations. In our visualisations, these are coloured green. From top to bottom; sequential, branching, routing and computation modules.[ S [ M [ C norm]][ M [ C relu]]] [ S [ B clone][ M1 [ C linear]][ M2 [ C identity]][ A add]] [ S [ P im2col][ M [ C linear]][ R col2im]] [ S [ M [ C softmax]]] identity clone cloneIn our example, the skip connection will be handled by a combination of branching and aggregation functions, the convolution is decomposed into the routing functions im2col and col2im, with a linear layer from the computation group between them. The normalisation and activation come from the computation group. In the next subsection, we discuss the larger structures of the architecture.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.A module is defined as a composition of functions from above that 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 be paired with a subsequent aggregation operation. Thus, the whole network can be seen as a module that takes a single tensor as input and outputs a single prediction. A 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 2 .Sequential module. A pair of modules and/or functions that are applied to the input tensor sequentially. Using our grammar, defined in Section3.3, this can be produced using the rule ( M → M M ), 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 in an aggregation function. In the grammar below this can be produced by the rule ( M → B M A ).Routing module. A routing function is applied, followed by a module and/or function. A final routing function then processes the output tensor. In the grammar below this is produced by the rule ( M → P M R ). For more details on the role of the routing module, see Appendix A.3.Computation module. This module only contains a 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 ( M → C ).To construct our example, we will be using all four modules. The branching module combines the clone and add functions from before to create a 2-branch structure. One branch is a simple skip connection by using the identity function inside a computation module. The other branch is the more complex sequence. The convolutional layer is created by combining im2col, linear and col2im in a routing module. The norm and activation are each wrapped in a computation module and these are all composed in sequential modules. Figure 2 shows similar module instantiations in action.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 M R | C, B → clone | group, A → matmul | add | concat, P → identity | im2col | permute, R → 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 is a predefined module that takes an output feature from the backbone and processes it into a 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 in the CFG in Figure 3 . When designing a search space, we must balance the need for flexibility-which 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 is 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 2 , to construct a convolution, we start from the rule ( M → P M R ) and derive the following( P → im2col ), ( M → C → linear ) and ( R → 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 a branching factor of 2 we have ( BM 1 M 2 A ) but with a branching factor of 4 we have (BM 1 M 1 M 1 M 1 A ).Examples of components instantiated by a branching factor of 2 include skip connections, and for 4, or 8, multi-head attention.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 mode3 that affects the shape of our features and which operations are available at 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 a 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 a 2D tensor of shape (S, 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 col2im. 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 Im 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.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 an 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:EQUATIONGiven this, we 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 no available valid options, it will backtrack and change the latest decision until a 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 P was previouslyEQUATIONEnhanced with parameters, this now becomes two rulesEQUATIONEQUATIONThis signifies that an im2col operation is not available in the Col mode. Similarly, the available aggregation options depend on the branching factor of the current branching moduleEQUATIONEQUATIONEQUATIONWhen sampling an architecture, we construct a decision tree where non-leaf nodes represent decision points and leaf nodes represent architecture operations. In each iteration, we either select a 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 a deeper, more complex network, whereas selecting functions leads to a shallower, simpler network. We can balance this complexity by assigning probabilities to our production rules, thereby making a PCFG. Recall our CFG ruleEQUATIONIf we choose one of the first three options we are delving deeper in the search tree since there is yet another M to be expanded, but if we choose ( M → C ), the computation-module, then we will reach a terminal function. Thus, to balance the depth of our traversal and therefore expected architecture complexities, we can set probabilities for each of these rules:EQUATIONsuper-critical sub-critical 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.We could set these probabilities to match what we wish the expected depth of architectures to be (for empirical results 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 setting the probabilities such that the branching rate of the CFG is less than one [8] . For details of how, see Appendix A.4. So, as shown in Figure 4 , we set the computation module probability to p(M → C | M) = 0.32 and the probabilities of the other modules to 1-0.32. For simplicity, all other rule probabilities are uniform.For a thorough example of how sampling is performed in einspace, please see Appendix A.1.As our search space strives for expressivity and diverse architectures, we adopt a diverse benchmark suite from the recent paper on Unseen NAS [16] , containing datasets at different difficulties across 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 B.2 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 we beat competing NAS methods on CIFAR100, FSD50K and Darcy Flow, and to the best of our knowledge set a new state-of-the-art on NinaPro.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, we start by constructing an 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-first-out 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 a whole subtree if a non-leaf node is chosen.Validate Architecture: Check if the new architecture can produce a valid output in the forward pass, given an input of the expected shape, and that it fits within resource constraints, e.g. GPU memory. If it does, accept it; otherwise, discard and retry the mutation.Note that these are 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 [11] . In this work, we focus on the properties of our search space and investigate whether simple search strategies are able to find good architectures, and leave investigations on more complex search strategies for future work.We compare these search strategies to PC-DARTS [60] , DrNAS [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.1 In previous NAS search spaces e.g. [30, 62, 12] , complex search methods often perform very similarly to random search [27, 63] . Indeed, we can see this in Table 1 comparing the PC-DARTS strategy to DARTS random search.way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
random sampling and 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 performance of a ResNet18. The random search baseline is also far behind, but intriguingly outperforms baseline NAS approaches on Chesseract.We now turn to a more sophisticated search strategy. We perform regularised evolution in einspace for 1000 iterations across all datasets, initialising the population with 100 random samples. In Table 1 the results are shown in 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 to DARTS. Compared to the top performing NAS methods, however, it is significantly behind on some datasets. We evaluate performance across multiple datasets and modalities from Unseen NAS [16] . Results transcribed from [16] are denoted *, where DARTS [30] and Bonsai [15] 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. To fully utilise the powerful priors of existing human-designed structures, we now invoke search where the initial population of our evolutionary search is seeded with a collection of existing state-of-the-art architectures.We first seed the entire population with the ResNet18 architecture. The search applies mutations to these networks for 500 iterations. In Table 1 , these results can be found in the RE(RN18) 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 cases we can beat the existing state-of-the-art, 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 6 has a direct improvement over the ResNet18 by 5.76%. See also the architecture in Figure 5 and the collection in Figure 8 in the Appendix for the breadth of structures that are found in einspace.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 our search results on einspace are competitive, even with far weaker search space priors.One dataset where our searches struggle is CIFARTile, a more complex version of the CIFAR10 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 is highly successful for traditional computer vision style tasks that have been common in the literature. 
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] or 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.6. 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 architecture, primarily due to the multiple ways of stacking sequential modules. Moreover, we 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 no options for recurrent computation, as found in RNNs and the new wave of state-space models like Mamba [17] . We believe this can 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. We also chose to keep the options for activations and normalisation layers as small as possible since in practice the benefit from changing these is minor.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We submit our codebase together with the paper for reviewers to check our results. The codebase includes all configuration files to reproduce our results on Unseen NAS (Tab. 1) and NASBench360 (Tab. 6). It also includes detailed instructions on how to set up the environment and datasets. We will make our codebase publicly available on acceptance. 
conclusion: 
 We have introduced einspace: an expressive NAS search space based on a parameterised PCFG. We show that our work enables the construction of a comprehensive and diverse range of existing state-ofthe-art architectures and can further facilitate discovery of novel architectures directly from fundamental operations. With only simple search strategies, we report competitive resulting architectures across a 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We provide a detailed description of the experimental settings in Appendix B. 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 of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Unfortunately, the computational expense for running multiple runs of each experiment was too large. We focused on breadth of tasks instead of repeated runs on the same task.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if 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 to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is 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 a 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 are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on 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 on 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, or 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is foundational research which is application agnostic. Guidelines:• The answer NA means that there is 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 to particular applications, let alone deployments. However, if there is a 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 of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 a 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer:[Yes] Justification: This work uses existing datasets and the work corresponding to 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 is used and, if possible, include a URL.• 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 NeurIPS 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. 
 
 Appendix: A.1 SamplingIn this section, we explain the process of sampling an architecture from our parameterised PCFG through an example. We specifically focus on how the running example from the main paper, a simple convolutional block with a 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 ( M M ), ( B M A ), or ( P M R ). Since our block includes a skip connection, the macro structure of our architecture is best represented by a branching module ( B M A ).Within this module, we expand the string from left to right, thereby starting with ( B ). The specific branching operation that fits our goal is ( B → clone ) as we wish to later combine a transformed version of the tensor with itself. Since we have two branches, they are produced separately (see branching prior) and our module becomes( B M 1 M 2 A ).For the first branch, ( M 1 ), we need a set of components that constitute a convolution followed by batch normalisation and an activation. Since this involves several composed operations we first expand into a sequential module ( M 1 → M 3 M 4 ). The first of these operations represents the convolution. Within einspace, a convolution, conv(x), is decomposed into the three operations, col2im(linear(im2col(x))). Thus, in our grammar we unfold it as a routing module, ( M 3 → P M 5 R ) which further produces ( P → im2col ), ( M 5 → C → linear ) and ( R → col2im ). The normalisation and activation are then generated under ( M 4 ), defined as another sequential module (M 4 → M 6 M 7 ) with ( M 6 → C → norm ) and ( M 7 → C → relu ).The second branch, M 2 , acts as a skip connection and is thus derived as ( M 2 → C → identity ).To finalise the architecture, the aggregation symbol ( A ) merges the tensors back into one unit. To complete the residual connection, we use the rule ( A → add ).The full derivation tree in this example is shown in Figure 3 of the main paper. This general sampling process allows the creation of complex neural network architectures from a structured and interpretable set of rules.Our grammar in the main paper is somewhat simplified. There are some fundamental operations that have hyperparameters that allow multiple versions to be chosen. They are detailed here.Branching functions. For the production rule ( B → clone | group ), the full set of options is:EQUATIONwhere b refers to the branching factor and dim is the dimension we group over.Aggregation functions. Similarly, for the production rule ( A → matmul | add | concat ), the full set of options is:EQUATIONwhere 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 functionality 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 col2im only takes the predicted output shape as a parameter so we can include only a single version of this operation.im2col(k=1,s=1,p=0), im2col(k=1,s=2,p=0), (18) im2col(k=3,s=1,p=1), im2col(k=3,s=2,p=1), (19) im2col(k=4,s=4,p=0), im2col(k=8,s=8,p=0), im2col(k=16,s=16,p=0), (20) where k is the kernel size, s 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: (EQUATIONEQUATIONFor completeness, the identity operation can also be included, making two versions in the Col mode (with identity=permute(o=(1,2))) and six in the Im mode (with identity=permute(o=(1,2,3))).Computation functions. For linear layers, we vary the output dimension d across powers of two:EQUATIONlinear(d=128), linear(d=256), linear(d=512), (25) linear(d=1024), linear(d=2048).(EQUATIONThe norm operation takes on the batch-norm functionality in the Im mode and layer-norm in Col mode. The softmax is just a 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.In this section we provide some more information about how the routing module can represent common components.The routing module, ( M → P M R ), puts a prior on certain types of operations inside our architectures.A patch embedding, such as those found in many transformers, is achieved by the following derivation: ( M → im2col linear identity ), while a convolution can be obtained by ( M → im2col linear col2im ). In terms of the process required to sample such combinations, the first is easy since there are no dependencies between the operations. The second, however, is more complicated and requires some discussion.Let x be a tensor in R 3×32×32 and let us consider a routing module containing the functions: im2col, linear, col2im. The functions will be applied in order to the input tensor, giving usEQUATIONEQUATIONEQUATION)The shapes of the intermediate and final tensors {x ′ ,x ′′ ,y} depend on several function hyperparameters. These are listed below.Table 2 : Hyperparameters for the three functions involved in a convolution component. The input tensor has height dimension h in and width w in . The im2col operation will extract column vectors from this space a number of times depending on the kernel size k in , stride s in and padding p in values in the table above. The number of column vectors equalsEQUATIONwhich in our case gives l = 256. The shapes of all intermediate tensors can therefore be written as in Table 3 .Table 3 : Tensor shapes in the forward pass of our convolution component; c in = 3,h in = 32,w in = 32 in this example.Tensor Shapex [c in ,h in ,w in ] x ′ [l, c in ×k in ×k in ] x ′′ [l, c out ] y [c out , h out , w out ]Therefore, to successfully apply the col2im function, the constraint l = h out ×w out must be satisfied.From Equation 30we can see that the output height and width can be predicted by the im2col parametersEQUATIONEQUATIONSo, 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 the col2im only rearranges the tensor back into its correct 3D form. This is trivial in the case where h in = w in since h out = w out = √ l. However, if h in ̸ = w in , 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 l must not change in the connecting branch as it would break the constraint l = h out ×w out .If a PCFG is consistent, the probabilities of all finite derivations sum to one, or equivalently, it has a zero probability of generating infinite strings or derivations [8] . For us, that means a sampled architecture can not be infinitely large, and that the sampling algorithm will halt with probability one. In order to check if a CFG is consistent, we can inspect the spectral radius ρ of its non-terminal expectation matrix [8] . If ρ < 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-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 an architecture string, ℓ, as a function of the rule probabilities. More specifically, denote by E[A] the expected length of string generated by a nonterminal in the grammar A. Then ℓ = E[S], where:EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONIn the above, α is the right hand side of a rule and α i varies over the nonterminals in that right hand side.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), i.e. two spatial dimensions and one channel dimension. In order to search for architectures on 1D datasets-with input tensors of shape (S, D), i.e. one sequence dimension and one token dimension-we need to adjust the einspace CFG to make it compatible.We replace the routing functions im2col and col2im with operations that perform the full 1D convolution directly-without decomposing the operation-and place them into the computation function group. Below are the new conv1d functions in the 1D variant of einspace conv1d(k=1,s=1,p=0,d=32), conv1d(k=1,s=1,p=0,d=64) (40) conv1d(k=1,s=1,p=0,d=128), conv1d(k=1,s=1,p=0,d=256) (41) conv1d(k=3,s=1,p=1,d=32), conv1d(k=3,s=1,p=1,d=64) (42) conv1d(k=3,s=1,p=1,d=128), conv1d(k=3,s=1,p=1,d=256) (43) conv1d(k=5,s=1,p=2,d=32), conv1d(k=5,s=1,p=2,d=64) (44) conv1d(k=5,s=1,p=2,d=128), conv1d(k=5,s=1,p=2,d=256) (45) conv1d(k=8,s=1,p=3,d=32), conv1d(k=8,s=1,p=3,d=64) (46) conv1d(k=8,s=1,p=3,d=128), conv1d(k=8,s=1,p=3,d=256).(EQUATIONSome versions of the group, concat and permute operations are also removed as they operate on a dimension that now doesn't exist. Below is the adjusted grammar for this variant.S → M M | B M A | R M R, M → M M | B M A | R M R | C, B → clone | group, A → matmul | add | concat, R → identity | permute, C → identity | conv1d | linear | norm | relu | softmax | pos-enc.In the NASBench360 results presented in Table C .1, this 1D variant of einspace is used for the datasets ECG, Satellite and Deepsea. The baseline WideResNet-16-4 architecture is also adjusted to handle the 1D data, as described in [55] .In this section we will discuss the size of the introduced search space.Our einspace grammar contains recursive rules, e.g. ( M → M M ). Due to this recursion the grammar generates a language with an infinite number of strings. We know from Section A.4 that since our grammar is consistent, the architecture sampling process always terminates. This means every architecture derivation tree is finite in size. So, while einspace covers an infinite number of architectures, each such architecture is finite. Let the architecture string denote the left-to-right sequence of leaves of a derivation tree. We define S n to be the set of all architecture strings of length n. As we will show next, the size of S n grows exponentially with n. To do this, we first introduce a few new concepts.A Dyck language [25] is a formal language consisting of strings that represent balanced and properly nested sequences of pairs of symbols, typically parentheses, where each opening symbol must have a corresponding closing symbol, and at no point in the string can the number of closing symbols exceed the number of opening symbols. A Dyck language can be generated by a context-free grammar defined over a set of terminal symbols Σ = {(,)}. Generalising this, Dyck-k denotes a Dyck language with k distinct pairs of matching symbols, e.g. Dyck-2 has Σ = {(,),[,]}. The growth of a Dyck-1 language is described by the Catalan numbers, reflecting the exponential increase in valid strings as the length of the input increases, i.e. the number of strings with m matching pairs of symbols is the mth Catalan numberC m = 1 m+1 2m m .Asymptotically, the number of such strings grows as O(4 m ). Dyck-2 languages do not follow the Catalan numbers but still grow as O(4 m ).We can rewrite (and somewhat simplify) our einspace CFG from Section 3.3 in order to generate a Dyck languageS → M M | ( M ) | [ M ], M → M M | ( M ) | [ M ] | C, C → 1 | 2 | 3 | ...The set of non-terminal symbols {B, A, P, R} has been replaced with the terminal set of parentheses and square brackets {(, ), [, ]} and, for simplicity, the terminal symbols of C have been replaced by integers. This makes it a Dyck-2 language with the addition of the C symbol that can be expanded into several terminal options.While a normal Dyck-2 language grows as O(4 m ), ours is more complex. Firstly, each non-terminal symbol M will eventually produce a C which leads to a terminal. Let the number of terminals derivable from C be χ, and the number of occurrences of the symbol C in the derivation of an architecture be c. The number of possible strings we can obtain from just the C symbols thus grows as O(χ c ). 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 be β. We already know that the number of balanced brackets is m, meaning the total number of terminals coming from these is 2m. Therefore, the number of architecture strings in S n grows asEQUATION)where m is the combined number of branching and routing modules, c is the number of computation functions, and n = 2m + c. Some architectures will contain many nested branching or 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.In Table 4 we compare einspace to other popular search spaces in the literature along several axes. We highlight some of the most important differences here:• einspace uniquely unifies multiple architectural families (ConvNets, Transformers, MLPonly) into one single expressive space while the CFG-based framework of Schrodi et al. [46] has variations of spaces centred around ConvNets only, and a separate instantiation focusing only on Transformers.• einspace extends to probabilistic CFGs. This enables 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 → 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, [46] instead focuses on fixed hierarchical levels that limits the macro structure to a predefined-though very large-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. We use convolutional baselines of ResNet18 [19] and WideResNet-16-4 [64] . Both stems use a 3×3 convolution instead of the standard 7×7 as most input shapes in the datasets we use are small. The former contains a 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 × 3 convolution with stride 2. This has been shown to be equally powerful [49] and in our experiments we find that it performs similarly. Our ViT model is a small 4-layer network with a patch size of 4, model width of 512, and 4 heads. The MLP-Mixer shares the same patch embedding stem with a patch size of 4. It has 8 layers and, similarly, a model width of 512. The channel mixer expands the dimension by 4 and the token mixer cuts it in half. The models have the following number of parameters (given an input image of shape [3, 64, 64] ): Resnet18: 11.2M, WRN16-4: 2.8M, ViT: 4.4M and MLP-Mixer: 6.5M.Every network that is instantiated contains a few common operations. For classification tasks, the network head takes the following form: the output features of the sampled backbone are reduced to their channel dimension via reduce(x, 'B C H W -> B C', 'mean') 4 or reduce(x, 'B C H -> B C', 'mean'), depending on if the input 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 backbone 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.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, we retrain on train+val splits and evaluate on test. To speed up our experiments, 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 in Table 5 .Our experimental evaluation covers 19 different datasets, with sizes ranging from thousands of data points, to a million (Satellite from NASBench360), and spatial resolutions of up to 256×256 (Cosmic from NASBench360). In this section we briefly describe these parts in detail.We followed the official instructions of Unseen NAS [16] to setup the datasets. Descriptions of each dataset follow:Table 5 : Hyperparameters for each dataset, taken from Geada et al. [16] for Unseen NAS and Tu et al. [55] for NASBench360. We set the number of search epochs to 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 CIFAR10 (bottom), the metrics differ and we report the 0-1 error instead of accuracy to align with the other metrics focused on error minimisation. Cosmic contains images from the F435W filter collected from the Hubble Space Telescope. It aims to identify cosmic rays (corrupted pixels) in the images. Inputs are images of 1×256×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.The ECG task concerns predicting irregularities in electrocardiograms. ECG recordings of 9-60 seconds are sampled at 300 Hz and labeled using four classes: normal, disease, other, or noisy rhythms. We process each recording with a fixed sliding window of 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 F1-score.The goal of the Satellite task is to classify land cover maps for geo-surveying, for one million data points across 24 categories. Each data point is a single-channel satellite time-series of shape 1×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.This dataset focuses on predicting the behaviour of chromatin proteins to aid in understanding genetic diseases. Each data point is a genome sequence of 1,000-base pairs (A, C, T or G), represented as a binary matrix of shape 1000 × 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 CIFAR10 dataset: CIFAR10 CIFAR10 is a widely known image classification dataset with 10 classes. Each image is of size 3×32×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.All our experiments ran on our two internal clusters with the following infrastructure:Table 6 : Lower is better. Our results on NASBench360 [55] , 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 is used, along with a human-designed expert architecture per dataset (Expert). RE(WRN) refers to initialising the regularised evolution search algorithm with the WideResNet16-4 (WRN) architecture. Note that we could not reproduce some baseline WRN performances in our code.We have therefore reported both the WRN from NB360 and our own WRN results. We use our own results for computing average ranks. We test einspace on the diverse NASBench360 [55] to further showcase its potential. These results can be found in Table 6 . In this setting the baseline network is a WideResNet16-4 (WRN)-which is For our experiments we set the computation module probability to p(M → C | 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 we can see that the complexity, as measured by the count of terminals and non-terminals in the derivation trees, grows as the probability decreases.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 to 1 billion, and from as few as two operations up to as many as 3,000. The frequency of all functions in einspace that appear in these networks can be found in Figure 7 . NeurIPS Paper Checklistsequential_module• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).The name is inspired by the generality of Einstein summation and the related Python library einops[44] as many of our operations can be implemented by it.Note that this is similar but not the same as the mode of a general tensor, which determines the number of dimensions of that tensor. We use the term mode to refer to the state that a particular part of the architecture is in.The notation used here comes from the Python package einops[44], which implements a reduce function. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Below I list my major concerns about this submission:

- *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.
- *Limitations of the search space*: As the authors mention, there are various important architectures that cannot be encoded in einspace.
- *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. 
- *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.
questions: 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]?


-- References --

[1] https://proceedings.neurips.cc/paper_files/paper/2023/file/4869f3f967dfe954439408dd92c50ee1-Paper-Conference.pdf

[2] https://proceedings.neurips.cc/paper/2020/file/ea4eb49329550caaa1d2044105223721-Paper.pdf
limitations: limitations: The authors have addressed the limitations adequately.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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. 

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

Moreover, 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.
questions: 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.

Does 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]?

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

[1] Hierarchical Representations For Efficient Architecture Search (Simonyan et.al 2018)
[2] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars (Schrodi et.al 2023)
limitations: limitations: The limitations are adequately discussed in the final section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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

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

4. 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.
questions: questions: NA
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: Despite the strengths of this paper, I still have some concerns that prevent me from confidently recommending acceptance:
1. 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.
2. 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. 
3. 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.
questions: questions: See weaknesses.
limitations: limitations: The authors have discussed the limitations in their paper. Besides, there are no potential negative societal impacts of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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. 
- 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. 

If the authors adequately address these concerns, I will gladly raise my score.
questions: 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). 
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. **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. 

[1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch.
questions: questions: Questions:

1, 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?

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

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

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

5. Could you present parameter and FLOPs counts in Table 1?

6. How is the branching rate hyperparameter set for a newer search space?





[1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch.

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

Comments: title: Message to reviewer ZVSn
Response to Reviewer duvy
Response to Reviewer wLBZ
Response to Reviewer s1qw
Response to Authors
Response to reviewer
Response to rebuttal
Thanks for the response
Thanks for the rebuttal.
Read the rebuttal and discuss with the authors
comment: Thank you again for taking the time to review our paper. We hope our response has addressed your concerns, and would be very grateful if you would reconsider your scores. If there are further questions we are happy to continue discussing until the deadline tomorrow.
We thank the reviewer for their response and their updated scores, and we are encouraged that they think our work has strong potential. We will integrate all feedback from this review process into our paper and for a potential camera-ready version we are also working towards evaluating a BO search strategy on our search space. Thank you for a great discussion.
I thank the authors for their response and the additional experiments comparing einspace to the hierarchical NB201 space from Schrodi et al. I will increase my score, however, I think this paper has the potential to become a really strong publication by incorporating the feedback from the reviewers, and one more iteration might be beneficial in the long run.
We thank the reviewer for their response and updated scores. If there are any outstanding concerns regarding the time complexity or representations of architectural components, we are happy to discuss further during the discussion period.
We thank the reviewer for their response and updated scores. If there are any outstanding concerns, we are happy to clarify further during the discussion period.
I thank the Authors for their detailed response. Based on the additional results I would like to raise my score to 5.
Thanks to the authors for the detailed rebuttal. Although there are some issues of einspace, such as high time complexity and complex representation of skip connections, I think it is a valuable exploration of the search space with atomic operations. Therefore, I would like to raise my score to Weak Accept.
We thank the reviewer for their response and updated scores. We appreciate that there may be concern that at times our method finds architectures of higher parameter counts. However, we argue that this shows the flexibility of the search space in adapting to the difficulty of the given task. On three datasets (AddNIST, MultNIST and Chesseract) the parameter count is significantly increased, but in other cases it is significantly reduced (Language and Gutenberg). The increases could be easily controlled by either rejecting architecture candidates that are too big, or by including an efficiency component to the optimisation objective.
I appreciate the efforts of the authors in addressing my questions I am increasing my score to 4. That said, I am still concerned about the parameter sizes of architectures discovered by einspace in most cases being much larger than architectures being compared with.
We thank the reviewer for their response and for updating their scores. Let us know if there is anything we can clarify further to clear up the misconceptions, and we'll be happy to do so in the remaining discussion period.
After reading the rebuttal, I raise my score to 4 and lower my confidence. There is something I have misunderstood but I fail to figure it out.
Hi Reviewers, 

The authors have submitted their rebuttal responses addressing the concerns and feedback you provided. We kindly request that you review their responses and assess whether the issues you raised have been satisfactorily addressed.

If there are any areas where you believe additional clarification is needed, please do not hesitate to engage in further discussion with the authors. Your insights are invaluable to ensuring a thorough and constructive review process.

Best
AC