Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a method for differentiable synthesis of program architectures. A program derivation graph is encoded as a differentiable program whose output is a weighted output of all the programs in the graph. The method learns a probability distribution over all possible program derivations induced by a context-free grammar. The grammar rule selection weights and the program parameters are co-optimized iteratively with respect to a loss function over program outputs. The approach is evaluated on four sequence classification tasks. The discovered architectures have better F1 scores as compared to the state-of-the-art program synthesis methods (A*-NEAR and IDS-BB-NEAR).

main_review: **Originality**

The idea of differentiable network architecture search by relaxing the search space to be continuous has already been explored in DART. However, applying this technique to architecture search is not straightforward; the space of program architectures in this setting is huge. This work introduces two techniques, "node sharing" and "iterative unfolding" to address the challenges associated with program synthesis of differentiable programs. If the expansion of nonterminals in two programs are expanded with the same grammar production rule then the resulting subterms can be clubbed together in one node. This converts the program expansion tree into a graph reducing the search space to a great extent.
The Iterative Graph Unfolding approach unfolds the program derivation graph iteratively and prunes away unlikely candidates architectures at the end of each iteration. As the rule selection probabilities and program parameters are co-optimized, iterative graph unfolding ensures that only relevant nodes are kept in the program derivation tree. In my view, these two techniques are the main contributions of this work.

**Significance**

Program Architecture Search is a challenging problem due to the exponential search space. The enumeration-based strategies just do scale to the real world tasks. Differentiable synthesis is an important research direction for effective search. The two techniques introduced in the papers, "node sharing" and "iterative graph unfolding" enables the use of differentiable search methods for synthesizing programmatic models from a context free grammar.

**Quality**

* The problem formulation and the method presentation is technically sound. The iterative parameter update rules are presented clearly.
* The proposed method has been implemented as a tool called dPads. dPads is evaluated on four sequence classification tasks. The proposed method outperforms the state-of-the-art program synthesis methods on the F1 score metric and time.
* I think the evaluation is a bit inadequate. Although the datasets are from diverse domains, I would have liked some variety in the tasks. Currently all the tasks are sequence classification tasks. (Maybe include regression and other data types in addition to sequences). Some comparison with the enumerative approaches would have emphasized the benefit of the proposed approach.
* Naive application of DART like differentiable search does not work in the program synthesis domain. Including the results on dPads without using node sharing and/or iterative folding would bolster the paper's claim.
* The authors might consider reporting ROC-AUC to report the results across thresholds (if the dataset is not imbalanced.)

**Clarity**
* The paper is well written and easy to follow. I would have liked some light introduction to the Program Derivation Graph before diving into the notation heavy exposition. You may think of presenting a simple program derivation tree and the corresponding graph with collapsed nodes.
* I do not get the sentence on line 200. Is it that each node has at most N subterms?  However, there are 3 subterms in node 4 in Figure 4 (step 5).
* Minor: Line 85 uses $\sigma$ for grammar vocabulary. Immediately after that $\sigma$ is used for sigmoid function.
* Minor: Figure 5. Swap figures b and c to keep the same sequence as in Table 1.

limitations_and_societal_impact: * The paper doesn’t spend much time discussing the limitations or possible pain points. This is, in one way, a byproduct of the inadequate evaluations. The proposed approach is only compared with NEAR. I believe more diverse tasks of varying complexity will reveal the strong and weak points of the method.
* The paper already acknowledges that the results achieved with dPads do not match the RNN baseline result. This may be due to limitations in expressivity imposed by the DSL. I would like the authors to comment on this.

There does not seem to be any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the task of synthesizing differentiable programs for sequence classification tasks. It introduces a novel method, dPads, that first constructs a program derivation graph representing a subset of the highest probability possible architectures under a CFG, and subsequently uses an A*-like search to find a program in the graph that balances minimizing complexity with maximizing accuracy. Central to the derivation graph construction method are the ideas of (1) iterative training of architecture weights and neural approximations of subexpressions, (2) node sharing, and (3) iterative graph unfolding. The method is evaluated on four sequence classification tasks, where it is found to have better performance than the program synthesis baselines considered, and worse performance than an RNN baseline, with the key advantage over the RNN being the interpretability of the resultant programs from dPads.
main_review: Program synthesis is an important area because it yields results that are more interpretable, manipulable, and potentially generalize more robustly than neural models. So, it is promising that this method produces results beginning to approach those obtained by an RNN on sequence classification tasks. Still, the results are far enough behind the RNN's to make the accuracy / interpretability trade-off significant.

The approach builds upon the ideas of NEAR [1] and Euphony [2]. It uses a similar strategy to NEAR of (1) using neural models to approximate unexpanded subexpressions and (2) using an A*-like search for the optimal program. The contributions of this paper over those of [1] and [2] come from the methods of making the search space smaller. Performing iterative graph unfolding retaining only the top-N programs per node, combined with node sharing, allows for this. The other core aspect of this paper's method is it constructs a continuous relaxation of the otherwise discrete search space, iteratively training the architecture weight selection parameters and the neural subexpression parameters; this is most similar to the approach of the DARTS line of work [3], with which I acknowledge limited familiarity.

To demonstrate the value of this reduced search space, the experiments compare against two methods from [1], making the claim that other methods perform even worse and need not be compared against in the paper. Overall, the evaluation is done well, on four datasets with sequence classification tasks. These tasks are quite similar to one another in number of examples, frames, and number of features, and also share the similarity that they all come from visual recordings over time, despite the approach being more general than this one modality. It is interesting to note that the variance in run time can be quite high. Consider providing an explanation of this observation.

Consider also making the description of T clearer. Line 240 states the intention of T, but making it precise or explicitly stating its type or outputs would improve clarity. Other than this, the paper is written precisely. The appendix provides adequate details to understand the experiments fully.

Consider also including empirical information about the reduction in search space provided by node sharing and top-N retention. While the run times are informative, quantifying the search space reduction would be more useful for understanding the source of the relative performance of dPads and baselines more precisely.

From the results in Appendix A, it is interesting that performance already begins to drop off when N=3. The increase in time is understandable, but the drop in f1 score and accuracy is surprising. Do you have an explanation for this? Much of Appendix B already appears in the paper and is duplicated precisely; this is not necessary.

---

[1] Learning Differentiable Programs with Admissible Neural Heuristics https://arxiv.org/abs/2007.12101

[2] Accelerating Search-Based Program Synthesis using Learned Probabilistic Models https://www.seas.upenn.edu/~mhnaik/papers/pldi18b.pdf

[3] DARTS: Differentiable Architecture Search https://arxiv.org/abs/1806.09055

---

Line 21: s/achieves/achieving

Line 204: "noterminals" should be "nonterminals".

Line 223: "depcited" should be "depicted"

Line 234: $q[u/f^u_k]$ denotes the graph with $u$ modified, not the $f$-score; reword to make this clear.

Line 535: s/shows/show

Line 553: I'm not familiar with the term "sortness".
limitations_and_societal_impact: The authors acknowledge the main technical limitation of the work, the relative performance compared with RNN methods. The authors also mention in Section 6 that there is potential for attacks on security and fairness on models derived via the paper's method.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper introduces dPads, an approach to learning interpretable programs to perform sequence classification tasks, as an alternative to using RNNs which are less interpretable and possibly less robust. The programs are generated using a context-free grammar (adapted from prior work) of differentiable operations applied to sequences. The ultimate objective is to find a program that obtains high classification accuracy on a dataset, while having low architectural cost. This is done by using a continuous relaxation of the discrete choices in the grammar, using a softmax over all possible grammar production rules instead of a categorical choice, with learnable weights. Further optimizations include “node sharing” (where two nodes in the program derivation graph are shared if they represent the same nonterminal and thus can be expanded the same way) and “iterative graph unfolding” which is somewhat like a beam search over the program derivation process, narrowing down the earlier choices using a guess for their quality, resulting in less combinatorial explosion (higher efficiency) at the cost of a fully complete search. As a final step, an A* search is used to choose a single complete program with high accuracy and low cost. Experiments on 4 sequence classification datasets show that dPads performs better than prior work NEAR, but worse than plain RNNs (which are not interpretable programs).
main_review: **Positives**
* dPads performs better than prior work NEAR
* The diagrams are quite helpful for understanding the approach
* The iterative graph unfolding idea is quite interesting. Even though it’s similar to a beam search, I haven’t seen such an idea presented for a tree-shaped program derivation before.

**Negatives**
* The prose is a bit dense which makes it hard to follow some parts (but the diagrams are quite helpful)
* The work is quite similar to NEAR, with the similarities and differences not adequately explained, which can make many parts of dPads appear more novel than they are
* There is not enough experimental analysis about the impact of the differences between dPads and NEAR

---

Overall the approach in this paper makes sense. It did take me multiple passes through the paper to actually understand the approach, so perhaps the writing could be made more clear, maybe with a higher emphasis on conveying the broader intuitions before diving into details. I found that the diagrams were quite helpful in understanding the approach.

My main concern is that the paper is not clear enough on how dPads differs from NEAR. The two works use very similar DSLs (by design), both view program search as a graph search problem where the graph nodes are partially expanded programs and edges represent grammar production rules, both use A* with admissible heuristics to perform the search within this graph, and both use neural networks to approximate missing (unexpanded) expressions. It appears that dPads implements some engineering optimizations to make the search process faster, but it is not clear whether NEAR uses similar optimizations (since NEAR is faster than dPads on one dataset), what the impact of these optimizations are, nor how novel they are (when viewed at a high level, sharing nodes when nodes represent the same thing is a common technique, and iterative graph unfolding is similar to beam search). Given how similar dPads and NEAR are, I think the paper should have space dedicated to explaining how NEAR works, what its drawbacks are in more detail (maybe with examples), and then demonstrating how dPads’ modifications help address those drawbacks.

As it is, I feel that this paper is a bit misleading because the high similarity to NEAR is swept under the rug, and would only be noticed by a reader already familiar with NEAR. Thus, in my opinion, the paper needs a significant change to present the approach in a way that adequately explains its relationship (similarities and differences and _why_) to prior work. Doing so would also strengthen the paper's significance, if readers can come away with stronger intuitive understandings of why certain approaches are better than others.

**Questions**
* 105: where to do the costs $c(r)$ come from?
* 289: “all tools search over the same DSL” - have you extended NEAR to use the extra DSL elements, or limited dPads to use NEAR’s DSL?
* 307: Why is the F1 score of 0.475 different from the value in Table 1, 0.458? Is it because Figure 6 contains the best program over 5 runs, and the other runs produce programs with much lower F1 score? What are those other programs?
* Table 2: Is there a copy/paste error here? The F1, Acc, and Time columns are exactly the same between Crim13 and Sk152.
* What are the main differences between dPads and NEAR? Intuitively speaking, why are dPads’ approach better than NEAR’s approach? I understand the argument of being more efficient in an enormous search space, but why is NEAR faster than dPads on Fly-vs-fly, and similar in speed on Crim13 and Sk152? From the timing results, I infer that NEAR must have other kinds of optimizations, and a deeper dive into the pros and cons of each approach is needed.
* Each dataset has a training, validation, and test set. Furthermore, the training set is split into $D_{val}$ and $D_{train}$ (line 279), so now we have 4 splits. Where is each split used?

**Minor suggestions**
* 21: achieves -> achieving
* 32: inefficient in natural -> inefficient in nature? Or just inefficient
* 138: still not sure what “inefficient in natural” means
* 223: depcited -> depicted
* I would give an example task in the introduction or problem formulation to help clarify what is meant by “sequence classification,” which I initially interpreted to mean classification of text. This also helps the reader think about the correct datatypes when reading about the approach
* I would make a connection between iterative graph unfolding and beam search -- when I realized the similarities, the iterative graph unfolding step suddenly made much more sense.

limitations_and_societal_impact: One point that should be mentioned is that, IIUC, dPads requires more time and resources (i.e., higher carbon footprint) to produce a program, compared to simpler approaches like plain RNNs.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A method for synthesising programs using gradient descent is presented, alternating between optimisation of operator parameters (constants) and of the program structure (nested expressions). The submission focuses on reducing the complexity of the search for correct structures, using the idea of sharing different nodes in the search tree (i.e., allow them to appear in different contexts) as well as initially approximating subexpressions by neural networks and only starting to learn to represent them by programs when the subtree appears to be a promising candidate.
Experiments on four small datasets show that the method compares favourably to a baseline in synthesizing programs that explain observed behaviour.
main_review: Originality
---
I'm not an expert in this area, and hence cannot comment much on this dimension. However, the idea of re-using parts of the synthesized programs in several places was already present in the TerpreT work of Gaunt et al, which considered a number of formalisms (e.g., assembly programs) in which operand choices were shared in a similar way as in the proposed "Node Sharing" method in this submission.

Quality
---
The only claims in the paper are related to the effectiveness of the proposed method. Claims regarding the overall method seem well-supported by the experiments (but again, not an expert and hence no idea if these datasets/baselines are appropriate), but the individual contribution of the different methods remain unclear:
1. The experiments do not break out the effect of the node sharing technique at all. For example, what would happen if every potential function would have its own child nodes? Clearly, the runtime would explode, but would the quality of the generated programs improve as well? You could even imagine faster convergence, as the number of constraints on each parameter is reduced.
2. The effect of the iterative search tree deepening technique is not studied in detail. In particular, I'm not sure if N=3 means that all children are always preserved (that somewhat depends on how the $c$ parameter of fold is treated); and many other pruning approaches (e.g., considering the top N candidates across the entire search tree, rather than per node) are not considered at all.

Clarity
---
I found the paper very hard to follow, in particular because some core concepts are not illustrated in a helpful way. For example, it would have been helpful to explain the meaning of $w$ - I first thought this is simply the probability distribution over potential choices in a node; however this seems to be wrong when considering Fig. 3 and Eq. (3), and instead it turns out that this is conditional on where it is used. Providing a full example would have made following the text much easier.

There are a number of imprecisions (or maybe missed opportunities):
* l162-l165: What about the first parameter of ITE and Add? Are these not shared (because this wouldn't be well-typed), or is there some special-casing happening here? More generally, are types used at all to direct the search?
* how are variables picked by the system? does the grammar contain a fixed pool of variables, or is this somehow special-cased?
* Sect. 3.3: the choice of the name $f$ to compute a cost in Alg. 1 is extremely unfortunate, as it has no relationship to the $f_u^k$ also appearing here.

Significance
---
The present submission does not seem to be a breakthrough in applicability of neural program search to complex problems. The idea of iterative deepening of the search is interesting, though somewhat underexplored in this submission, and just aims to bound the base of the exponential blowup of the search method. 


Minor details
---
- Fig. 1: I found this DSL extremely strange (without knowing the datasets), as it mixes non-standard, apparently task-focused primitives such as mapprefix and SlideWindowAvg into a basic functional language. It would be helpful to comment on the choice of functions in the text.
- l105: "sum of the multiset of rules" -> "sum of the costs of the rules in the multiset of rules" (or something slightly less ungainly, but correct)
- l135: "are inefficient in natural" -> "... in general"
- l204: "noterminals"
- l223: "depcited"
- Fig. 6: left half of table for "Sk152-10 actions" is a copy of the Crim13-sniff results

Update after Author Response
---
Given the additional example on a different DSL, I'm happy to believe that this submission is more significant as it is applicable to a wider range of examples; hence I'm upgrading my original rating.
limitations_and_societal_impact: In the checklist, the authors claim that they discussed the limitations of their work, but I could find no such discussion in the paper. No negative societal impact is apparent.
review_title: null

Meta-review: The reviewers appreciated the novel idea presented in the paper to use gradient-based search in a continuous relaxation of context-free grammar rules for synthesis of program architectures. The additional experiments with comparison to enumerative approaches and ablation experiments, as well as more information about empirical savings in search space and relationship with NEAR were also greatly appreciated. There was still a concern about improving the writing and presentation in the paper, which hopefully the authors can improve in the final version taking feedback from the detailed reviews. It would also be great to incorporate the new experiments and discussions from the responses in the final version.
Decision: Accept (Poster)