Neural Guided Constraint Logic Programming for Program Synthesis
Synthesizing programs using example input/outputs is a classic problem in artificial intelligence. We present a method for solving Programming By Example (PBE) problems by using a neural model to guide the search of a constraint logic programming system called miniKanren. Crucially, the neural model uses miniKanren's internal representation as input; miniKanren represents a PBE problem as recursive constraints imposed by the provided examples. We explore Recurrent Neural Network and Graph Neural Network models. We contribute a modified miniKanren, drivable by an external agent, available at https://github.com/xuexue/neuralkanren. We show that our neural-guided approach using constraints can synthesize programs faster in many cases, and importantly, can generalize to larger problems.
The paper presents an approach to neural guided search for program synthesis of LISP programs.  A modified miniKanren constraint solver is used to synthesize a program from example IO pairs by "inverting" the EVAL function.  The search for candidate programs in the solver is guided by a neural network (either a GNN or an RNN with other layers on top).  The approach is compared to baselines and three symbolic methods.   Pros: - The paper is very well written and definitely relevant to NIPS - The evaluation against symbolic methods is reasonable - While the idea of scoring evaluation expansions is not novel, applying it to the EVAL function is   Cons: - Novelty is somewhat limited - Links to some recent related work are missing - No comparison to other neural methods   In general, I think that paper is clear and sound enough.  I am not so confortable about originality, but still, I am in favor of acceptance.   Major issues:  - The fact that learners can be used to score candidate rule expansions has already been demonstrated (several times) before, see for instance:      Learning to Search in Branch-and-Bound Algorithms, 2014, He, Daume' III, and Eisner (more distantly related; but note that, unsurprisingly, program synthesis and structure learning in general *can* be framed as a MILP problem)      End-to-End Differentiable Proving, 2017, Rocktäschel and Riedel (in a very related setting)    Essentially this paper "ports" the neural guidance idea from SLD resolution to constraint satisfaction, which in miniKanren is based on the same principle.  The handling of logical operators as aggregators is also similar.    As far as I can see, the novely here is in the choice of "what to guide", namely the expansion of the EVAL function, and in the choice of neural architecture.  This is less novel than the authors seem to claim.    This is good enough, but the authors should definitely better position their contribution w.r.t. the aforementioned works, especially the second one.   - The fact that the proposed system is "deeply integrated" with miniKanren and LISP prevents comparison to existing neural approaches.  This is very unfortunate---but unavoidable, I guess.    More generally, it is difficult to see what the advantages of the proposed approach are with respect to existing neural synthesis alternatives.  Unfortunately there is no ready-made, agreed-upon benchmark or problem setting for neural program synthesis, and I understand that it is difficult to compare against other neural techniques.  However, this is only a partial excuse.    Note that, for instance, since in principle prolog can be used to synthesize programs satisfying a set of examples, the method in the "end-to-end differentiable proving" paper can be used for program synthesis too.  I won't ask the authors to compare against it, as it is a lot of work, but this should be doable.  - The pros and cons of RNN versus GNN are not really studied in depth.  I guess that this is unavoidable, given that these models are quite opaque.   Minor issues:  - missing commas in Figure 2