Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks

By David Bieber, Charles Sutton, Hugo Larochelle, Daniel Tarlow. 2020

49 citations recorded by the source corpus.

Graph neural networks (GNNs) have emerged as a powerful tool for learning software engineering tasks including code completion, bug finding, and program repair. They benefit from leveraging program structure like control flow graphs, but they are not well-suited to tasks like program execution that require far more sequential reasoning steps than number of GNN propagation steps. Recurrent neural networks (RNNs), on the other hand, are well-suited to long sequential chains of reasoning, but they do not naturally incorporate program structure and generally perform worse on the above tasks. Our aim is to achieve the best of both worlds, and we do so by introducing a novel GNN architecture, the Instruction Pointer Attention Graph Neural Networks (IPA-GNN), which achieves improved systematic generalization on the task of learning to execute programs using control flow graphs. The model arises by considering RNNs operating on program traces with branch decisions as latent variables. The IPA-GNN can be seen either as a continuous relaxation of the RNN model or as a GNN variant more tailored to execution. To test the models, we propose evaluating systematic generalization on learning to execute using control flow graphs, which tests sequential reasoning and use of program structure. More practically, we evaluate these models on the task of learning to execute partial programs, as might arise if using the model as a heuristic function in program synthesis. Results show that the IPA-GNN outperforms a variety of RNN and GNN baselines on both tasks.

Subfields: Electrical and Electronic Engineering, Information Systems, Materials Chemistry, Graph Learning

How researchers see this paper

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

In Electrical and Electronic Engineering

  1. Hongseok Yang
  2. Gwonsoo Che
  3. Charles Sutton
  4. Augustus Odena
  5. Quoc V. Le
  6. Anders Andreassen
  7. Maxwell Nye

In Information Systems

  1. David Bieber
  2. Carrie J. Cai
  3. Augustus Odena
  4. Hongseok Yang
  5. Charles Sutton
  6. Jacob Austin
  7. Maarten Bosma
  8. David Dohan

In Materials Chemistry

  1. Gwonsoo Che
  2. Hongseok Yang
  3. Quoc V. Le
  4. Charles Sutton

In Graph Learning

  1. Gwonsoo Che
  2. Hongseok Yang
  3. Augustus Odena
  4. Quoc V. Le
  5. David Bieber
  6. Charles Sutton

Citations in the corpus