Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes using context free grammars to define a search space. This grammar is very flexible and one can use it to define all kinds of search spaces. The production rules can be formed to imposed constraints as well. Their search algorithm, BANAT is a bayesian optimization based one, where the surrogate model is a hierarchical Weisfeiler-Lehman kernel (adapted Weisfeiler-Lehman kernel used by NASBOWL to make it work for their search space) and the acquisition function is expected improvement. They used a hierarchical NASBENCH 201 search space. 
strength_and_weaknesses: Strength:
1. This paper defines a language for defining search spaces. Their grammar can be used for all the search spaces.
2. Their search algorithm is able to find better architectures faster than others in hierarchical NAS-Bench 201 search space (as they are using a surrogate model).
3. In their empirical evaluations, it was highlighted that while cell-based search space works well for cifar-10, cifar-100 and imagenet-16-120, it does not perform well on CIFARTile or AddNIST. 

** Comments / Questions **
It is a bit hard to understand why we need a special grammar to design the search space. The authors claim it is more flexible and can discover new architectures. But one still needs to design the primitives and how they are connected together. So how can we really discover completely new architectures?
1. Hierarchical search space is much larger than cell spaced search space and is used for scenarios where one is interested in finding architectures with low latency, number of flops etc. So it is not surprising that BANAT was able to discover architectures with lesser number of parameters. It would have been better if they had actually demonstrated how it fared in multi-objective optimization problems and compared against other hierarchical baselines such as MNASNet. 
3. The authors claim that their search space design is more flexible than other baselines and is especially beneficial for object detection setting. But they never ran BANAT to find architectures for object detection.
4. For figure4, Kendall Tau is the most commonly metric. Please use that.
5. Please use a diagram to elucidate how the hierarchical search space looks like
6. Please specify the details about bayesian optimization such as the acquisition function used in the main paper rather than in the appendix.
7. The time taken for Imagenet-16-120 is 1.8 * 8 GPU days. Please specify that explicitly. 
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly. (I have prior knowledge of CFGs, otherwise would have been harder to follow). The novelty is limited. 
summary_of_the_review:  The main novelty is the ability to define a context free grammar for a given search space. It is not evident if this is actually useful in practice. The surrogate model used by BANAT is a minor adaptation of NASBOWL paper which used Weisfeiler-Lehman for a regular NASBENCH search space to make it work for hierarchical setting. They also need to compare their algorithm against other hierarchical search space based algorithms.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes to represent neural architectures as algebraic terms and the design space (i.e. neural architecture search space) as context-free grammars (CFGs).  The authors then develop a Bayesian optimization algorithm building on top of the work by Ru et al., 2021 called BANAT, that exploits the CFG representation to define a hierarchical kernel. Results show BANAT benefits from the hierarchical kernel and outperforms common NAS baselines like random search and evolutionary search on NASBench-201 style search spaces.
strength_and_weaknesses: Pros:
- The CFG formulation of NAS search spaces is natural and flexible. 

Cons:
- The experiments are only conducted on NASBench201 style search spaces, which are small and do not achieve SOTA accuracy.
- BANAT is only evaluated against simple baselines like random search and evolutionary search and not more adaptive competitors, in particular, other Bayesian NAS methods like HNAS (Ru et al., 2021), BANANAS, NASBOT, etc.
- No evidence that the additional expressivity of the search space offered by BANAT results in interesting novel architectures. 
clarity,_quality,_novelty_and_reproducibility: ## Clarity
- The writing could be improved, especially in the introduction, which focuses a lot on discovering novel architectures although this is not shown in the experiments.
- It is unclear how we go from algebraic representation to graph for the hierarchical Weisfeller-Lehman kernel (hWL). 
## Quality
- Quality of the experimental section is low due to missing comparison to other BO NAS methods and just one studied search space of limited size.
## Reproducibility
- Aside from the point of how we go from algebraic representation to graph for hWL, the experimental description is thorough and appears reproducible.

summary_of_the_review: The authors present a simple, flexible formulation of neural architectures as algebraic terms and search spaces as CFGs. Along with this flexible search specification, the authors introduce BANAT, a BO-based NAS search method, that uses a hierarchical representation of architectures to learn and transfer across different granularities of representation in architecture space.  Although results look promising on a suite of experiments based on the NASBench201 benchmark, they do not
sufficiently validate NASBAT relative to other baselines, nor do they provide enough coverage of different search spaces, in particular those that reach SOTA on CIFAR-10/ImageNet.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a CFG-based approach for specifying architecture search spaces. They demonstrate the expressivity of their approach, propose a BO-based schemes for searching it while handling the massive hierarchical search space, and evaluate by searching for architectures on several vision datasets.
strength_and_weaknesses: ### Strengths:
1. The CFG-based approach for specifying large search spaces seems fairly novel and interesting, in-particular allowing for very large search spaces while dealing with issues of dimensionality and other constraints.
2. The authors provide code and furthermore make an effort to ensure impact via both PyTorch and Tensorflow APIs.
3. The presentation of the experimental section is very clear and directly lays out what questions are being answered. Empirically, the results show that the larger search space can be fruitfully searched for stronger architectures than are contained in the NB201 search space, at least on ImageNet-16-120 and the two recently introduced tasks.

### Weaknesses:
1. The “from Scratch” nature of the work may be somewhat overstated, as the user must still specify primitives such as convolutions being used. The authors motivate the work by noting the Transformer was not discovered by NAS, but is there any hope that a search space generated along these lines would encode its crucial attention mechanism while not being so vast as to be unsearchable? Notably, there has been recent work on “from Scratch” AutoML (Real et al., 2020) and NAS (Roberts et al., 2021) that do aim for such generality.
2. It is not entirely clear that the CFG formalism is crucial for defining and constraining search spaces. It could be useful to compare to other AutoML search space definitions, e.g. the domain-specific language for optimizer search of Bello et al. (2017).
3. The related work noted in the two points above is missing.
4. The methods sections of the paper are difficult to follow without either familiarity with CFGs (not safe to assume for ICLR). There is a lot of relegation of detail to the appendix, both for the search space design and for the search methods.
5. The experimental section could benefit from demonstrations with search spaces beyond NB201, and on tasks beyond computer vision, especially since as the authors note the algorithms for vision have already been highly optimized. Some important comparisons/ablations are missing, such as whether FLOPs are also comparable to NB201, and whether it is important to have multiple kinds of activation function in the search space, or if performance is the same if only the one used by NB201 is allowed?

### Questions:
- Is “any neural architecture can be represented algebraically” a formal claim? If yes where is the definition of a neural architecture and proof of the result? Does this fact hold e.g. for recurrent nets?
- Equation 4: presumably f also includes some fixed training procedure for all networks?
- Why is “our grammar-based mechanism does not (generally) support simple scalability of discovered neural architectures (e.g., repetition of building blocks)” true given the use of the CL to capture NB-201? 

### References:
- Bello, Zoph, Vasudevan, Le. *Neural optimizer search with reinforcement learning*. ICML 2017.
- Real, Liang, So, Le. *AutoML-Zero: Evolving machine learning algorithms from scratch*. ICML 2020.
- Roberts, Khodak, Dao, Li, Re, Talwalkar. *Rethinking neural operations for diverse tasks*. NeurIPS 2021.
clarity,_quality,_novelty_and_reproducibility: Clarity: difficult to follow, apart from the experimental section.  
Quality: the work is methodologically interesting, but some experimental justifications are missing.  
Novelty: the work is novel but missing comparisons on related work on from-scratch AutoML, as listed above.  
Reproducibility: good.
summary_of_the_review: I believe the work to be an interesting approach to discovering neural architectures from scratch, and there are some interesting experimental results, so I would be in favor of the paper appearing at the conference. The fairly limited nature of the empirical evaluation, missing discussion of recent work on from-scratch AutoML, and opaque presentation of the method prevent me from giving a stronger endorsement.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes to use context free grammars (CFGs) to represent hierarchical search spaces for neural architecture search, towards the goal of discovering new architectures, rather than refining existing ones (an example of designing Transformers over CNNs is given in the introduction).
Architectures are represented using algebraic terms, and search are then defined by the means of related sets of production rules, terminals and nonterminals, constituting a CFG.
Further, a Bayesian optimization (BO) algorithm, utilizing hierarchical Weisfeiler-Lehman kernel (hWL), is proposed to efficiently search within large search spaces, produced with CFGs.
Experiments are conducted on the NAS-Bench-201 (NB201) search space and its hierarchical variant, using CIFAR-10, CIFAR-100, ImageNet-16-120, CIFARTile and AddNIST datasets.
strength_and_weaknesses: 
**Strengths:**

 - representing neural networks and related search spaces through formal grammars is an interesting research direction with a potential to deliver a convenient tool to work with complex hierarchical search spaces
 - the paper does a good job at explaining the idea and how different search spaces can be represented using this new approach (although this is presented mainly in the Appendix)
 - limitations of the work seem adequately mentioned (although I would still have some questions, see below)
 
**Weaknesses:**

 - the paper does not clearly present what the benefits of adopting the proposed approach exactly are -- specifically, there are two main questions that are not sufficiently answered: 1) are there any qualitative gains from adopting grammar-based approach over traditional ways of representing search spaces (e.g., just writing PyTorch code specific to what we want to search)? By qualitative gains I mean that something becomes possible, which otherwise would not be; 2) what are the quantitative gains? That is, is it faster/easier/more flexible to use these grammars compared to using custom PyTorch code? Some important related questions:
    - in Appendix E we can see how DARTS search space can be achieved - however, a common problem with DARTS is that even though when a supernet is created each consecutive node takes all previous outputs as its input (as in Figure 6), when deriving a final architecture we only keep two inputs, meaning that some of these connections have to be removed. Is it possible to efficiently represent this kind of constraints using CFGs?
    - Is it possible to easily obtain supernets from a search space description (if it makes sense for the search space)?
    - It seems that every time a searchable graph-based structure is included in a search space (NB201 cell, DARTS cell, etc.), it is represented a custom, purpose-built terminal - does it mean that CFGs are, broadly speaking, not the best choice when searching for arbitrary connectivity between operations? Or could these structures be expressed with additional production rules and simpler terminals?
 - Related to the above, but focused more on the high-level direction of this research: considering that we have to define all terminals, nonterminals and production rules (which I imagine would involve providing implementation for each element), is the overall effort and process of designing a search space fundamentally different when using CFGs compared to just doing hierarchical NAS? Specifically, I do not see how using CFGs brings us closer to the goal of automatically discovering novel architectures (like Transfomers) - in the end it seems we are still primarily limited by the primitives (operations, architectural patterns, etc.) that we decide to include in our search space, just like it is the case for the most (all?) of the existing methods.
 - evaluation of the proposed method is rather limited - I felt a bit disappointed by its scope and the choice of baselines, specifically:
    - only one, very simple search space is considered; although the fact that NB201 search space is extended does help, still the evaluation does not really match what can be usually found in NAS papers
    - selected baselines are all very simple methods - there are many very efficient NAS methods out there, e.g., the entire research field of zero-cost NAS ("Zero-Cost Proxies for Lightweight NAS", "Neural Architecture Search without Training", "Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective", to name just a few papers) seems like a good fit to "search efficiently in the huge search spaces spanned by our algebraic architecture terms", but the authors only include random, evolutionary and BO search, which are one of the most basic approaches
    - similarly, applicability of some efficient one-shot NAS methods, which constitute an important subfield in NAS, is not explored at all (related to one of my questions above)
    
**Minor shortcoming and suggestions:**

 - consider changing "Linear" to, for example, "Sequential" - the word "linear" is commonly associated with linear operations, not with a chain of sequential operations
 - "However, there is of course no single search space that can construct any neural architecture" I assume the authors meant that it is impossible to define a single search space _using CFGs_, that would include any neural architecture? I would argue that an implicitly defined search space obtained by considering basic graph operations (such as add a node, add an edge, assign operation, etc.) together with a starting graph (e.g., empty graph) would include any neural network realizable in practice. How big such a search space would be, or if it would be easy to use some searching algorithms within it is a different question - although please note that there exist NAS papers that defined search spaces in such way.
 - Equations 4 and 8 are somewhat redundant, Equation 8 does not seem to add much on top of Equation 4, just minor details - in general, in my opinion, Sections 2 and 3 could be combined and made shorter, and the saved space could be used to include some of the things I mentioned are currently missing from the paper.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written but it misses some important discussion regarding comparing CFGs with conventional way of defining search spaces. The idea of using formal grammars is novel, so is the introduction of hierarchical Weisfeiler-Lehman kernel (although the latter is a minor modification). The authors provide code which helps with reproducibility.
summary_of_the_review: While I like the motivation presented in the paper and the idea of using formal grammars seems somewhat compelling to me, in my opinion the paper currently does not contain convincing argumentation for using CFGs, neither does it provide sufficiently strong/interesting experimental results to consider it for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a novel symbolic search space for NAS that allows generating architectures without predefined connection patterns.

The search space is derived from contextual-free gramma where the networks are presented as algebraic terms formed from neural operators.

To navigate through this search space, the author leverages Bayesian Optimization with a hierarchical WL kernel.

Experiments are conducted on NAS-Bench-201, where the author shows that architectures derived from this search space surpass those generated by prior cell-based search spaces.
strength_and_weaknesses: Strength:

- The presented search space is novel and different from existing architectural spaces. By itself, it counts as a solid contribution to the community.
- The authors demonstrated the effectiveness of this search space over hand-engineered cell-based ones, leveraging the BO-hWL algorithm.

Weakness:

- [Minor] The search space itself still relies on existing patterns designed by human priors, e.g. the Cell(OP, OP, OP) operators, residual, and convolutions. Moreover, considering the sheer size of the search space, the search cost could be prohibitive beyond small-scale experiments. However, I don’t think it diminishes the contributions of this work. These issues could be left for future works to explore.
- [Minor] Related work: The authors did a throughout survey of relevant NAS works in Section 5. Though it might also be worthwhile to also mention the topics of program synthesis or Neural-Symbolic Programming. The NSP community also has several existing works on adopting contextual-free grammar for discovering programs [1, 2]. Some also mentioned NAS since architectures can be viewed as a subset of differentiable programs [1, 2]. This work also inspires some recent AutoML methods, such as [3] where an algebraic search space is also proposed, but for a different task.

[1] Shah et al, Learning Differentiable Programs with Admissible Neural Heuristics. NeurIPS 2020
[2] Cui and Zhu, Differentiable Synthesis of Program Architectures. NeurIPS 2021
[3] Wang et al. Efficient Non-Parametric Optimizer Search for Diverse Tasks. NeurIPS 2022
clarity,_quality,_novelty_and_reproducibility: The paper is clear and well-written. The search space is novel for the NAS community.

I don't seem to find the code in this submission, but the author mentioned in the abstract that they open source in PyTorch and Tensorflow.
summary_of_the_review: The search space that this paper presents is valuable to the NAS community, and I vote for acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a new approach to representing neural architectures as algebraic terms and the design space as context-free grammars (CFGs). While the formulation is novel, natural and flexible, the experimental results are limited to small search spaces that do not achieve state-of-the-art accuracy. BANAT is only compared to simple baselines, and there is no evidence that the additional expressivity of the search space leads to novel architectures.

To strengthen the case for the usefulness of method, it would be beneficial to conduct experiments on other search spaces that allow for state-of-the-art results. This would provide a more comprehensive evaluation of effectiveness and allow for a more convincing comparison to other NAS methods, such as HNAS, BANANAS, and NASBOT.

Overall, the CFG representation of NAS search spaces is a promising approach, but additional experimentation is needed to fully demonstrate its potential. We encourage the authors to address these limitations and believe that the paper can be made a valuable contribution to the field.
Decision: Reject