Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents a branch-and-bound approach to learn good programs
(consistent with data, expected to generalise well), where an LSTM is
used to predict which branches in the search tree should lead to good
programs (at the leaves of the search tree). The LSTM learns from
inputs of program spec + candidate branch (given by a grammar
production rule) and ouputs of quality scores for programms. The issue
of how greedy to be in this search is addressed.

In the authors' set up we simply assume we are given a 'ranking
function' h as an input (which we treat as black-box). In practice
this will simply be a guess (perhaps a good educated one) on which
programs will perform correctly on future data. As the authors
indicate, a more ambitious paper would consider learning h, rather
than assuming it as a given.

The paper has a number of positive features. It is clearly written
(without typo or grammatical problems). The empirical evaluation
against PROSE is properly done and shows the presented method working
as hoped. This was a competent approach to an interesting (real)
problem. However, the 'deep learning' aspect of the paper is not
prominent: an LSTM is used as a plug-in and that is about it. Also,
although the search method chosen was reasonable, the only real
innovation here is to use the LSTM to learn a search heuristic.


The authors do not explain what "without attention" means.


I think the authors should mention the existence of (logic) program
synthesis using inductive logic programming. There are also (closely
related) methods developed by the LOPSTR (logic-based program
synthesis and transformation) community. Many of the ideas here are
reminiscent of methods existing in those communities (e.g. top-down search
with heuristics). The use of a grammar to define the space of programs
is similar to the "DLAB" formalism developed by researchers at KU
Leuven.

ADDED AFTER REVISIONS/DISCUSSIONS

The revised paper has a number of improvements which had led me to give it slightly higher rating.


review_title: Although the search method chosen was reasonable, the only real innovation here is to use the LSTM to learn a search heuristic.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper extends and speeds up PROSE, a programming by example system, by posing the selection of the next production rule in the grammar as a supervised learning problem.

This paper requires a large amount of background knowledge as it depends on understanding program synthesis as it is done in the programming languages community. Moreover the work mentions a neurally-guided search, but little time is spent on that portion of their contribution. I am not even clear how their system is trained.

The experimental results do show the programs can be faster but only if the user is willing to suffer a loss in accuracy. It is difficult to conclude overall if the technique helps in synthesis.
review_title: Incremental paper but well-written

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This is a strong paper. It focuses on an important problem (speeding up program synthesis), it’s generally very well-written, and it features thorough evaluation. The results are impressive: the proposed system synthesizes programs from a single example that generalize better than prior state-of-the-art, and it does so ~50% faster on average.

In Appendix C, for over half of the tasks, NGDS is slower than PROSE (by up to a factor of 20, in the worst case). What types of tasks are these? In the results, you highlight a couple of specific cases where NGDS is significantly *faster* than PROSE—I would like to see some analysis of the cases were it is slower, as well. I do recognize that in all of these cases, PROSE is already quite fast (less than 1 second, often much less) so these large relative slowdowns likely don’t lead to a noticeable absolute difference in speed. Still, it would be nice to know what is going on here.

Overall, this is a strong paper, and I would advocate for accepting it.


A few more specific comments:


Page 2, “Neural-Guided Deductive Search” paragraph: use of the word “imbibes” - while technically accurate, this use doesn’t reflect the most common usage of the word (“to drink”). I found it very jarring.

The paper is very well-written overall, but I found the introduction to be unsatisfyingly vague—it was hard for me to evaluate your “key observations” when I couldn’t quite yet tell what the system you’re proposing actually does. The paragraph about “key observation III” finally reveals some of these details—I would suggest moving this much earlier in the introduction.

Page 4, “Appendix A shows the resulting search DAG” - As this is a figure accompanying a specific illustrative example, it belongs in this section, rather than forcing the reader to hunt for it in the Appendix.


review_title: Strong paper; accept

Meta-review: The pros and cons of this paper cited by the reviewers can be summarized below:

Pros:
* The method proposed here is highly technically sophisticated and appropriate for the problem of program synthesis from examples
* The results are convincing, demonstrating that the proposed method is able to greatly speed up search in an existing synthesis system

Cons:
* The contribution in terms of machine learning or representation learning is minimal (mainly adding an LSTM to an existing system)
* The overall system itself is quite complicated, which might raise the barrier of entry to other researchers who might want to follow the work, limiting impact

In our decision, the fact that the paper significantly moves forward the state of the art in this area outweighs the concerns about lack of machine learning contribution or barrier of entry.
Decision: Accept (Poster)