Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: # Summary

This paper trains a network to mimic simple known algorithms in a way that guarantees that they generalize to
out-of-distribution test instances. The network mimics the algorithms by running repeatedly in a loop where each
iteration of the loop runs a Transformer and outputs a mask that tells the next iteration the inputs to process. The
setup is tested on sorting, adding, and graph algorithms, and found to learn regular number representations that
supposedly aid generalization.

# Review

This paper has an admirable and useful goal, but the way it is currently implemented and presented is not ready for
publication at ICLR.

My main issue is with the training/testing setup and its presentation. The authors assume a certain structure of an
algorithm (for instance, the iterative structure of recursive selection sort), delegate one or more modules inside this
structure to be implemented by neural networks, and train them only.
Most of the "strong generalization" is coming from the fact that the iterative structure is fixed. The work abstracts
out the most complex parts of each algorithm. In Figure 3, for instance, the NN must learn to find the smallest element
among the non-masked-out ones on the input, return it, and mask it out. This is a much simpler task than the whole
sorting algorithm. Training the network to solve "find_min" != claiming that the network solves and strongly generalizes
on "sort".

Important training details are left unspecified. How is the data for training NEEs generated? For instance, for training
the network in Figure 3, do you trace the whole selection sort on a randomly generated list, and collect the
intermediate input/output pairs for "find_min"? If so, it's absolutely unsurprising that the process also works for
longer lists -- see above. Are composable NEEs, like the three networks in Figure 7, trained jointly or separately? Do
they observe their own outputs that are fed into subsequent NEE networks, or are the previous outputs teacher-forced,
or are they pre-trained? Many of these details need to be clarified precisely to make the experimental setup
verifiable.
Some important details are presented factually without any motivation. For example, why does Figure 5 use
SHIFT and XOR? Why, in general, the next mask produced by a NEE is XORed with a previous one instead of replacing it?

I liked the embedding visualizations, which clearly demonstrate structure in the latent space driven by (a) the
binary number representations, and (b) the addition task objective. In addition to regular ordering structure (needed to
implement addition), the latent space also clearly exhibits regularities inherent to the binary representation, such as
the shift by 64 in Figure 8a. While interesting, this only confirms the findings of Shi et al., albeit in a more pure
experimental setting.

In summary, the scope of experiments and presentation of results would need to be significantly improved in order for
this work to reach the quality bar of ICLR.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: his paper deals with the problem of designing neural network architectures that can learn and implement general programs.  The authors are motivated by problems in such works, mainly generalization to testing distributions that do not necessarily correspond to the training distribution.  It should be made clear that the latter is a general problem in machine learning (with phenomena such as covariate shift being commonplace), the authors particularly relate this work to predicting new values and longer sequences (i.e. strong generalization).

The authors further motivate their work by assuming that these phenomena are due to lack of prior structure that can be alleviated by further supervision during training.  The goal is for complex behaviour to emerge via composition of simple functions (which clearly follows the deep learning paradigm).Specifically, the authors propose a modification to the transformer architecture, that does not use positional encodings (the authors mention that this was detrimental to their work - it would be good to provide some more insight into that) and single-headed attention.  The main contribution seems to be adding the self-attention mask that is learned, along with execution traces that have been used in previous work.  An relatively small increase in performance is observed due to this, but it seems that the experiment is limited (no standard deviation in results, so I presume one run with one initialization).  Therefore it seems to me that the contribution of this paper is limited in terms of technical contribution.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper investigates an interesting problem of building a program execution engine with neural networks. The authors proposed a transformer-based model to learn basic subroutines, such as comparison, find min, and addition, and apply them in several standard algorithms, such as sorting and Dijkstra’s.

Pros:
1. The method achieves generalization towards longer sequences than the sequences in the training set in several algorithms.
2. The method represents numbers in binary form and the visualization shows that it learns embeddings from fixed-range integer numbers in a well-structured manner.
3. The learned NEE subroutines are tested in a variety of standard algorithms, such as multiple sorting algorithms and Dijkstra’s shortest path algorithm. The experiments further demonstrate that several NEE subroutines can be composed together in complex algorithms.

Cons:
1. NEE mostly focuses on learning low-level subroutines such as number comparison or addition. Therefore, it has to be used along with conventional subroutines, and cannot completely replace the full execution in complex algorithms, which have sophisticated control logic, such as if/else and for-loops. When the transformer model is used alone in the sorting task (Sec. 4.1), the performance degrades substantially as the sequence length gets longer.
2. Although the method achieved some degree of strong generalization, it lacks a formal way to verify the correctness of the learned subroutines, as opposed to prior work on program synthesis (Cai et al. 2017) that can prove the generalization of their model with recursion. 
3. The method relies on detailed execution traces for supervised learning which can be costly to obtain.

Questions:
1. Confusing sentence: “Can we retain high attention resolution by restricting the model to only observe the first scenario repeatedly?” Can you elaborate on what you meant here?
2. From Figure 1, it seems that the model with dot product attention generalizes better in longer sequences than the one with all modifications. What’s the reason?
3. I would like to better understand the limitation of these learned NEE subroutines in long sequences. For instance, in Figure 8 and Figure 9, how would the model perform beyond the lengths of the sequences tested here? Would the performance maintain at 100% or decrease gradually as the sequences get even longer?
4. I am curious to know how this method could be extended to support more complex number systems, such as float numbers, and more complex data structures beyond sequences, such as binary trees and priority queues. I’d love to hear what the authors have to say about this.
5. I'd also like to know if the number embeddings learn in different algorithms would exhibit different structures (by examining the visualization of number embeddings learned in different tasks).
6. As NEE focuses on learning the basic subroutines while NPI aims to learn the high-level program executions, I think that it’d be very interesting to see how these two can combine their complementary strengths to build a complete neural-based execution engine.

Typos:
Select he node --> Select the node

review_title: Official Blind Review #1

Meta-review: This paper investigates the problem of building a program execution engine with neural networks. While the reviewers find this paper to contain interesting ideas, the technical contributions, scope of experiments, and the presentation of results would need to be significantly improved in order for this work to reach the quality bar of ICLR.
Decision: Reject