einspace: Searching for Neural Architectures from Fundamental Operations

We thank the reviewer for their valuable feedback, and respond to each point below.

Contribution: There are three key differences between einspace and the CFG-based spaces of Schrodi et al [1].

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

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.

Table A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])

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.

PCFG extension: See previous answer above.

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.

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.

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.

Table B: Finetuning pretrained models

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.

Parameter counts and FLOPs: Thank you for this suggestion, parameter counts are now presented in Table C.

Table C: Parameter counts

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.

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

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 valuable feedback, and respond to each point below.

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.

Table D: Time-consumption (in hours)

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.

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

Table A: Additional datasets from NAS-Bench-360 (one-dimensional)

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

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.

Table A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])

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

Questions:

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.

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.

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

We hope we have addressed all fundamental questions raised and, in light of our clarifications, we invite the reviewer to consider increasing their score.

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

We thank the reviewer for their valuable feedback, and respond to each point below.

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.

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

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.

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.

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.

Table D: Time-consumption (in hours)

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.

Table A: Comparing einspace to hNASBench201 (from Schrodi et al. [1])

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.

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

In light of our responses and improved evaluation, we invite the reviewer to consider increasing their score.

[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.
[2] Insights from the Use of Previously Unseen Neural Architecture Search Datasets, Geada et al, CVPR 2024.

We thank the reviewer for their valuable feedback, and respond to each point below.

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

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.

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.

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.

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

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

Table A: Additional datasets from NAS-Bench-360 (one-dimensional)

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

We thank the reviewer for their valuable feedback, and respond to each point below.

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.

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.

Table A: DenseNet121 results

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.

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

Table B: CIFAR10 results

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.

Table C: Comparing einspace to hNASBench201 (from Schrodi et al. [1])

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.

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.

[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.
[2] Insights from the Use of Previously Unseen Neural Architecture Search Datasets, Geada et al, CVPR 2024.

Table D: Time-consumption (in hours)

We thank the reviewer for their valuable feedback, and respond to each point below.

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.

[1] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars, Schrodi et al, NeurIPS 2023.
[2] ZARTS: On Zero-order Optimization for Neural Architecture Search, Wang et al, NeurIPS 2022.
[3] PASHA: Efficient HPO and NAS with Progressive Resource Allocation, Bohdal et al, ICLR 2023.

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.

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.

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

Table A: Comparing einspace to hNASBench201 (from Schrodi et al [1])

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.