Turing complete computation and reasoning are often regarded as necessary precursors to general intelligence. There has been a significant body of work studying neural networks that mimic general computation, but these networks fail to generalize to data distributions that are outside of their training set. We study this problem through the lens of fundamental computer science problems: sorting and graph processing. We modify the masking mechanism of a transformer in order to allow them to implement rudimentary functions with strong generalization. We call this model the Neural Execution Engine, and show that it learns, through supervision, to numerically compute the basic subroutines comprising these algorithms with near perfect accuracy. Moreover, it retains this level of accuracy while generalizing to unseen data and long sequences outside of the training distribution.
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