Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:
I thank the authors for their update and clarifications.  They have addressed my concerns, and I will keep my score as it is.

-----------------------------------------------------------------------
The authors present a system that parses DSL expressions into syntax trees when trained using input-output examples. Their approach is based around LSTMs predicting a sequence of program-like instructions/arguments, and they argue that their work is an illustration of how we should approach synthesis of complex algorithms using neural techniques.

Overall I liked this paper: 
The authors provide a frank view on the current state of neural program synthesis, which I am inclined to agree with: (1) existing neural program synthesis has only ever worked on ‘trivial’ problems, and (2) training program synthesizers is hard, but providing execution traces in the training data is not a practical solution. I am somewhat convinced that the task considered in this paper is not trivial (so the authors do not obviously fall into trap (1) ), and I am convinced that the authors’ two-phase reinforcement learning solution to (2) is an interesting approach.
My score reflects the fact that this paper seems like a solid piece of work: The task is difficult, the solution interesting and the results are favourable.

However, I would like the authors to clarify the following points:
1.	In the inner loop of Algorithm 1, it looks like Net_in is updated M1 times, and a candidate trace is only stored if arguments that generate an exact match with the ground truth tree are found. Since M1 = 20, I am surprised that an exact match can be generated with so few samples/updates. Similarly, I am surprised that the appendix mentions that only 1000 samples in the outer loop are required to find an exact match with the instruction trace. Could you clarify that I am reading this correctly and perhaps suggest intuition for why this method is so efficient. What is the size of the search space of programs that your LL machine can run? Should I conclude that the parsing task is actually not as difficult as it seems, or am I missing something?
2.	The example traces in the appendix (fig 3, 6) only require 9 instructions. I’m guessing that these short programs are just for illustration – could you provide an example execution trace for one of the programs in the larger test sets? I assume that these require many more instructions & justify your claims of difficulty.
3.	As a technique for solving the parsing problem, this method seems impressive. However, the authors present the technique as a general approach to synthesizing complex programs. I feel that the authors need to either justify this bold assertion with least one additional example task or tone down their claims. In particular, I would like to see performance on a standard benchmarking task e.g. the RobustFill tasks. I want to know whether (1) the method works across different tasks and (2) the baselines reproduce the expected performance on these benchmark tasks. 
4.	Related to the point above, the method seems to perform almost too well on the task it was designed for – we miss out on a chance to discuss where the model fails to work.

The paper is reasonably clear. It took a couple of considered passes to get to my current understanding of Algorithm 1, and I found it essential to refer to the appendix to understand LL machines and the proposed method. In places, the paper is somewhat verbose, but since many ideas are presented, I did not feel too annoyed by the fact that it (significantly) overshoots the recommended 8 page limit.


review_title: good paper – some clarifications would help

final_score: rating: 7: Good paper, accept
review_content: This paper presents a reinforcement learning based approach to learn context-free
parsers from pairs of input programs and their corresponding parse trees. The main
idea of the approach is to learn a neural controller that operates over a discrete
space of programmatic actions such that the controller is able to produce the
desired parse trees for the input programs. The neural controller is trained using 
a two-phase reinforcement learning approach where the first phase is used to find
a set of candidate traces for each input-output example and the second phase is 
used to find a satisfiable specification comprising of 1 unique trace per example
such that there exists a program that is consistent with all the traces. The 
approach is evaluated on two datasets comprising of learning parsers for an 
imperative WHILE language and a functional LAMBDA language. The results show that
the proposed approach is able to achieve 100% generalization on test sets with 
programs upto 100x longer than the training programs, while baseline approaches 
such as seq2seq and stack LSTM do not generalize at all.

The idea to decompose the synthesis task into two sub-tasks of first learning
a set of individual traces for each example, and then learning a program consistent
with a satisfiable subset of traces is quite interesting and novel. The use of 
reinforcement learning in the two phases of finding candidate trace sets with 
different reward functions for different operators and searching for a satisfiable 
subset of traces is also interesting. Finally, the results leading to perfect 
generalization on parsing 100x longer input programs is also quite impressive.

While the presented results are impressive, a lot of design decisions such as 
designing specific operators (Call, Reduce,..) and their specific semantics seem
to be quite domain-specific for the parsing task. The comparison with general 
approaches such as seq2seq and stack LSTM might not be that fair as they are 
not restricted to only those operators and this possibly also explains the low 
generalization accuracies. Can the authors comment on the generality of the 
presented approach to some other program synthesis tasks?

For comparison with the baseline networks such as seq2seq and stack-LSTM, what 
happens if the number of training examples is 1M (say programs upto size 100)? 
10k might be too small a number of training examples and these networks can 
easily overfit such a small dataset.

The paper mentions that developing a parser can take upto 2x/3x more time than 
developing the training set. How large were the 150 examples that were used for
training the models and were they hand-designed or automatically generated by a
parsing algorithm? Hand generating parse trees for complex expressions seems to
be more tedious and error-prone that writing a modular parser.

The reason there are only 3 to 5 candidate traces per example is because the training
examples are small? For longer programs, I can imagine there can be thousands of bad
traces as it only needs one small mistake to propagate to full traces. Related to this
question, what happens to the proposed approach if it is trained with 1000 length programs?

What is the intuition behind keeping M1, M2 and M3 constants? Shouldn’t they be adaptive
values with respect to the number of candidate traces found so far? 

For phase-1 of learning candidate traces, what happens if the algorithm was only using the 
outside loop (M2) and performing REINFORCE without the inside loop?

The current paper presentation is a bit too dense to clearly understand the LL machine 
model and the two-phase algorithm. A lot of important details are currently in the
appendix section with several forward references. I would suggest moving Figure 3 
from appendix to the main paper, and also add a concrete example in section 4 to 
better explain the two-phase strategy.


review_title: Intriguing two phase RL approach for learning neural controllers for discrete programs

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a method for learning parsers for context-free languages. They demonstrate that this achieves perfect accuracy on training and held-out examples of input/output pairs for two synthetic grammars. In comparison, existing approaches appear to achieve little to no generalization, especially when tested on longer examples than seen during training.

The approach is presented very thoroughly. Details about the grammars, the architecture, the learning algorithm, and the hyperparameters are clearly discussed, which is much appreciated. Despite the thoroughness of the task and model descriptions, the proposed method is not well motivated. The description of the relatively complex two-phase reinforcement learning algorithm is largely procedural, and it is not obvious how necessary the individual pieces of the algorithm are. This is particularly problematic because the only empirical result reported is that it achieves 100% accuracy. Quite a few natural questions left unanswered, limiting what readers can learn from this paper, e.g.
- How quickly does the model learn? Is there a smooth progression that leads to perfect generalization?
- Presumably the policy learned in Phase 1 is a decent model by itself, since it can reliably find candidate traces. How accurate is it? What are the drawbacks of using that instead of the model from the second phase? Are there systematic problems, such as overfitting, that necessitate a second phase?
- How robust is the method to hyperparameters and multiple initializations? Why choose F = 10 and K = 3? Presumably, there exists some hyperparameters where the model does not achieve 100% test accuracy, in which case, what are the failure modes?

Other misc. points:
- The paper mentions that "the training curriculum is very important to regularize the reinforcement learning process." Unless I am misunderstanding the experimental setup, this is not supported by the result, correct? The proposed method achieves perfect accuracy in every condition.
- The reimplementations of the methods from Grefenstette et al. 2015 have surprisingly low training accuracy (in some cases 0% for Stack LSTM and 2.23% for DeQueue LSTM). Have you evaluated these reimplementations on their reported tasks to tease apart differences due to varying tasks and differences due to varying implementations?
review_title: Interesting work with strong results, but lacks empirical analysis

Meta-review: This paper proposes a method for training an neural network to operate stack-based mechanism in order to act as a CFG parser in order to, eventually, improve program synthesis and program induction systems. The reviewers agreed that the paper was compelling and well supported empirically, although one reviewer suggested that analysis of empirical results could stand some improvement. The reviewers were not able to achieve a clear consensus on the paper, but given that the most negative reviewer has also declared themselves the least confident in their assessment, I am happy to recommend acceptance on the basis of the median rather than mean score.
Decision: Accept (Poster)