Learning programs with neural networks is a challenging task, addressed by a long line of existing work. It is difficult to learn neural networks which will generalize to problem instances that are much larger than those used during training. Furthermore, even when the learned neural program empirically works on all test inputs, we cannot verify that it will work on every possible input. Recent work has shown that it is possible to address these issues by using recursion in the Neural Programmer-Interpreter, but this technique requires a verification set which is difficult to construct without knowledge of the internals of the oracle used to generate training data. In this work, we show how to automatically build such a verification set, which can also be directly used for training. By interactively querying an oracle, we can construct this set with minimal additional knowledge about the oracle. We empirically demonstrate that our method allows automated learning and verification of a recursive NPI program with provably perfect generalization.
Previous work by Cai et al. (2017) shows how to use Neural Programmer-Interpreter (NPI) framework to prove correctness of a learned neural network program by introducing recursion. It requires generation of a diverse training set consisting of execution traces which describe in detail the role of each function in solving a given input problem. Moreover, the traces need to be recursive: each function only takes a finite, bounded number of actions. In this paper, the authors show how training set can be generated automatically satisfying the conditions of Cai et al.'s paper. They iteratively explore all
possible behaviors of the oracle in a breadth-first manner, and the bounded nature of the recursive
oracle ensures that the procedure converges. As a running example, they show how this can be be done for bubblesort. The training set generated in this process may have a lot of duplicates, and the authors show how these duplicates can possibly be removed. It indeeds shows a dramatic reduction in the number of training samples for the three experiments that have been shown in the paper. 
I am not an expert in this area, so it is difficult for me to judge the technical merit of the work. My feeling from reading the paper is that it is rather incremental over Cai et al. I am impressed by the results of the three experiments that have been shown here, specifically, the reduction in the training samples once they have been generated is significant. But these are also the same set of experiments performed by Cai et al. 
Given the original number of traces generated is huge, I do not understand, why this method is at all practical. This also explains why the authors have just tested the performance on extremely small sized data. It will not scale. So, I am hesitant accepting the paper. I would have been more enthusiastic if the authors had proposed a way to combine the training space exploration as well as removing redundant traces together to make the whole process more scalable and done experiments on reasonably sized data.