Learning to Execute

By Wojciech Zaremba, Ilya Sutskever. 2014

591 citations recorded by the source corpus.

Recurrent Neural Networks (RNNs) with Long Short-Term Memory units (LSTM) are widely used because they are expressive and are easy to train. Our interest lies in empirically evaluating the expressiveness and the learnability of LSTMs in the sequence-to-sequence regime by training them to evaluate short computer programs, a domain that has traditionally been seen as too complex for neural networks. We consider a simple class of programs that can be evaluated with a single left-to-right pass using constant memory. Our main result is that LSTMs can learn to map the character-level representations of such programs to their correct outputs. Notably, it was necessary to use curriculum learning, and while conventional curriculum learning proved ineffective, we developed a new variant of curriculum learning that improved our networks' performance in all experimental conditions. The improved curriculum had a dramatic impact on an addition problem, making it possible to train an LSTM to add two 9-digit numbers with 99% accuracy.

Subfields: Artificial Intelligence, Natural Language Processing

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 Natural Language Processing

Citations in the corpus

Long Short-Term Memory-Networks for Machine Reading (2016, background): “, 2014): since the inputs are recursively combined into a single memory representation which is typically too small in terms of parameters, it becomes difficult to accurately memorize sequences (Zaremba and Sutskever, 2014).”
Neural GPUs Learn Algorithms (2015, methodology): “Neural Turing Machines (Graves et al., 2014) were shown to learn a number of basic sequence transformations and memory access patterns, and their reinforcement learning variant (Zaremba & Sutskever, 2015b) has reasonable performance on a number of tasks as well.”
Grammar as a Foreign Language (2014, methodology): “This was ﬁrst demonstrated on the English-to-French translation task (Sutskever et al., 2014), but the same approach also works for evaluating short python programs (Zaremba & Sutskever, 2014).”
Chain of Thought Prompting Elicits Reasoning in Large Language Models (2022, neutral): “Using intermediate reasoning steps has a long history in program synthesis and execution (Zaremba and Sutskever, 2014, inter alia ).”
Universal Transformers (2018, methodology): “Unlike (Zaremba & Sutskever, 2015), we do not use any curriculum learning strategy during training and we make no use of target sequences at test time.”
Show Your Work: Scratchpads for Intermediate Computation with Language Models (2021, neutral): “Work in learning to execute has considered whether off-the-shelf recurrent neural networks (Zaremba & Sutskever, 2014) or more specialized architectures (Dehghani et al., 2018; Bieber et al., 2020; Wang et al., 2020) have an inductive bias that is sufﬁciently well suited for executing and reasoning…”
Program Synthesis with Large Language Models (2021, methodology): “We suspect that training on more detailed execution data [Zaremba and Sutskever, 2014, Bieber et al., 2020] may further improve performance.”
Evaluating Large Language Models Trained on Code (2021, background): “Learning to Execute (Zaremba & Sutskever, 2014) demonstrated that models could execute simple tasks like addition and memo-rization.”
A Survey of Machine Learning for Big Code and Naturalness (2017, background): “Zaremba and Sutskever [197] Characters Execution Trace Distributed —”
Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets (2015, methodology): “While this model was orginally developed to address the vanishing and exploding gradient problems, LSTM is also able to learn simple context-free and context-sensitive grammars [16, 36].”
Memory Networks (2014, neutral): “A I] 1 6 O ct 2 01 4”
ShapeWorld - A new test methodology for multimodal language understanding (2017, background): “Recent work in the context of deep learning has investigated sequence patterns (Joulin and Mikolov, 2015), combinatorial problems (Vinyals et al., 2015), or executing programming language code (Zaremba and Sutskever, 2014), amongst others.”
Order Matters: Sequence to sequence for sets (2015, neutral): “…(Vinyals et al., 2015b), and models for computation map from problem statements (e.g. a python program or a set of points on the plane) to their solutions (the answer to the program (Zaremba & Sutskever, 2014), or the traveling salesman problem tour for the set of points (Vinyals et al., 2015a)).”
Programmable Agents (2017, background): “Different approaches to this problem focus on networks that infer programs [3, 10, 22], on networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13]; although there is much overlap between many of these approaches.”
Analysing Mathematical Reasoning Abilities of Neural Models (2019, background): “Zaremba & Sutskever (2014) analyze the ability of LSTMs to map short Python programs (addition or for-loops) to their output.”
Deep Speech 2 : End-to-End Speech Recognition in English and Mandarin (2015, background): “Other works have found that presenting examples in order of difficulty can accelerate online learning [6, 70].”
Long-term recurrent convolutional networks for visual recognition and description (2014, methodology): “We use the LSTM unit as described in [46] (Figure 2, right), which is a slight simplification of the one described in [10].”
Pointer Networks (2015, methodology): “Nonetheless, these methods still require the size of the output dictionary to be fixed a priori.”
Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks (2015, background): “Additionally, instead of a single forget gate, the Tree-LSTM unit contains one forget gate f jk for each child k .”
Neural Programmer-Interpreters (2015, background): “However, we are aware that others have gotten multi-digit addition of the above form to work to some extent with curriculum learning (Zaremba & Sutskever, 2014).”