Neural Execution Engines: Learning to Execute Subroutines

By Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, Milad Hashemi. 2020

45 citations recorded by the source corpus.

A significant effort has been made to train neural networks that replicate algorithmic reasoning, but they often fail to learn the abstract concepts underlying these algorithms. This is evidenced by their inability to generalize to data distributions that are outside of their restricted training sets, namely larger inputs and unseen data. We study these generalization issues at the level of numerical subroutines that comprise common algorithms like sorting, shortest paths, and minimum spanning trees. First, we observe that transformer-based sequence-to-sequence models can learn subroutines like sorting a list of numbers, but their performance rapidly degrades as the length of lists grows beyond those found in the training set. We demonstrate that this is due to attention weights that lose fidelity with longer sequences, particularly when the input numbers are numerically similar. To address the issue, we propose a learned conditional masking mechanism, which enables the model to strongly generalize far outside of its training range with near-perfect accuracy on a variety of algorithms. Second, to generalize to unseen data, we show that encoding numbers with a binary representation leads to embeddings with rich structure once trained on downstream tasks like addition or multiplication. This allows the embedding to handle missing data by faithfully interpolating numbers not seen during training.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

Chain of Thought Prompting Elicits Reasoning in Large Language Models (2022, neutral): “Recent work along in this direction has included a number of architectural innovations (Cai et al., 2017; Dong et al., 2019; Yan et al., 2020), as well as the use of large language models (Chen et al.”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[34] Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi.”
Teaching Algorithmic Reasoning via In-context Learning (2022, methodology): “…the architecture align to the algorithms under consideration (Kaiser and Sutskever, 2015; Chiang and Chen, 2018; Xu et al., 2019; Gordon et al., 2019; Yan et al., 2020; Chen et al., 2020; Xhonneux et al., 2021; Veliˇckovi´c and Blundell, 2021) or to the input format (Thawani et al., 2021).”
Meta-Learning an Inference Algorithm for Probabilistic Programs (2021, methodology): “8a. Limitations and future work Currently, a learnt inference algorithm in our work does not generalise to programs with different sizes (Yan et al., 2020), e.g., from clustering models with two clusters to those with ten clusters.”
Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks (2021, background): “, 2019), algorithmic tasks (Veličković et al., 2020; Yan et al., 2020), and inductive classification Hamilton et al.”