Source-linked AI summary
Learning to Execute
Wojciech Zaremba, Ilya Sutskever
TL;DR
The paper asks whether LSTMs can learn to evaluate short computer programs from character sequences, a demanding sequence-to-sequence task. It trains LSTMs on a restricted linear-time, constant-memory program class and develops curriculum strategies. The combined curriculum enables 99% accuracy on adding two 9-digit numbers, while the study leaves generalization and broader program evaluation unresolved.
Problem
The paper investigates whether LSTMs can learn sequence-to-sequence evaluation of short computer programs, which require numerical operations, assignments, conditionals, and compositionality.
Method
The study trains character-level LSTMs on programs evaluable in linear time and constant memory, comparing curriculum strategies and input transformations.
Results
99% accuracy was achieved when adding two 9-digit numbers with the combined curriculum strategy.
Takeaways & Limitations
LSTMs can learn to evaluate restricted programs, and curriculum learning is crucial for difficult tasks; input doubling reliably improves sequence-to-sequence performance.
Takeaways & Limitations
The models’ reliance on memorization and their learned algorithm remain unclear because training and test distributions were the same.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper tests whether character-level sequence-to-sequence LSTMs can evaluate short computer programs, despite the programs’ nontrivial operations and dependencies. It introduces curriculum learning and input transformations to improve training.
- Core contribution: LSTMs accurately evaluate short simple programs from character-level representations in a sequence-to-sequence framework.The model reads each program character-by-character and computes its integer output.
- Core contribution: The evaluated programs are constrained to computations feasible in linear time and constant memory, matching the LSTM’s single-pass limited-memory structure.The restriction reflects the model’s one-pass reading process and limited memory capacity.
- Training strategy: Training LSTMs to execute programs was difficult, motivating a curriculum procedure that outperformed both no curriculum and naive curriculum learning.The paper also offers a plausible explanation for the new procedure’s advantage over naive curriculum learning.
- Input transformations: Reversing and replicating input sequences improved LSTM performance on a memorization task in many experimental settings.These transformations were studied as ways to simplify sequence-to-sequence learning.
3 PROGRAM SUBCLASS
The study defines a restricted program subclass that LSTMs can process in one pass, then examines its complexity, representation, and related addition and memorization tasks.
- Program subclass: The program subclass uses Python syntax, arithmetic, assignments, conditionals, and for-loops, while forbidding double loops.Each program ends with one print statement producing an integer.
- Program subclass: Programs are generated by varying integer length and nesting, with higher nesting producing deeper compositions that are harder for LSTMs.The programs do not receive external input.
- Program subclass: Multiplication operands and loop ranges are restricted because generic multiplication and nested loops can require more than the model’s linear-time computation.One operand and loop ranges are sampled from a smaller range tied to program length.
- Representation: The LSTM reads and writes character sequences without predefined semantic knowledge, and scrambling input characters does not affect its ability to solve the task.A scrambled input-output example illustrates the task’s difficulty.
- Auxiliary tasks: The addition task uses two uniformly sampled numbers of equal length, while memorization requires reproducing an input sequence character-by-character.Input reversing creates shorter-term dependencies, and input doubling presents the input twice before output.
4 CURRICULUM LEARNING
The curriculum section compares training distributions that vary program difficulty by length and nesting. Its proposed combined strategy mixes easy-to-hard progression with difficult examples throughout training.
- Curriculum motivation: Program length and nesting control complexity, and sufficiently large values make learning nearly intractable.The setup therefore motivates first learning easier programs with smaller length and nesting.
- Strategies: The baseline trains only on examples with the target length and nesting, matching the test distribution without curriculum learning.This is described as statistically sound because training and test distributions coincide.
- Strategies: The naive curriculum begins at length = 1 and nesting = 1, increasing length after validation progress stops before increasing nesting.The experiments consistently increase length first.
- Strategies: The mixed strategy independently samples length and nesting across their full ranges, maintaining a balanced mixture of easy and difficult examples.This keeps some examples at an appropriate difficulty throughout training.
- Strategies: The combined strategy merges naive progression with mixed sampling, ensuring that training includes difficult examples and generally outperforming the mixed strategy.It always outperformed the naive strategy, while its advantage over the mixed strategy was not universal.
5 LSTM
The paper uses a deep LSTM with additive memory cells to process sequences with long-term dependencies. Its top-layer activations predict the output at each timestep.
- At timestep t, each layer receives the preceding layer’s hidden state and its own previous memory state to compute updated hidden and memory states.The mapping T_n,m is a biased linear transformation, and ⊙ denotes element-wise multiplication.
- The model uses activations from the top layer L to predict y_t, where L denotes the network depth.
- Additive memory cells make it easier for LSTM architectures to learn storage of information across long time intervals.
- The deep LSTM represents each layer’s hidden state and uses a separate memory-cell vector to retain information over long periods.All vectors are n-dimensional, and the memory cells are updated additively through gated operations.
6 EXPERIMENTS
The experiments evaluate curriculum strategies and input transformations across program evaluation, addition, and memorization tasks. The combined curriculum generally performs best, including 99% accuracy for adding two 9-digit numbers, while memorization favors jointly doubling and reversing inputs.
- Experimental setup: The experiments use the same two-layer LSTM architecture across program evaluation and memorization tasks.The network has 400 cells per layer, is unrolled for 50 steps, and contains approximately 2.5M parameters.
- Experimental setup: Teacher forcing supplies the first i −1 target digits when predicting digit i, so reported accuracies do not measure fully autonomous generation.
- Experimental setup: The four training strategies are baseline, naive curriculum, mixed, and combined curriculum learning.
- Program evaluation: The combined strategy outperformed the baseline in every program-evaluation setting, despite deeper nesting and longer integers increasing difficulty.
- Addition: 99% accuracy was achieved when adding two 9-digit numbers with the combined curriculum, a substantial improvement over the naive curriculum.
- Memorization: On memorization, simultaneously doubling and reversing the input achieved the best results across the evaluated input-modification settings.The task varied input lengths from 5 to 65 digits and evaluated four modification schemes at convergence.
7 HIDDEN STATE ALLOCATION HYPOTHESIS
The authors hypothesize that curriculum effectiveness depends on how examples allocate the LSTM’s limited hidden-state memory. The combined strategy pairs intermediate mappings from naive curriculum with mixed-difficulty examples that reduce memory restructuring.
- The results suggest that proper curriculum learning is critical on hard problems where conventional stochastic gradient descent performs poorly.
- Across both evaluated problems, the combined strategy outperformed naive curriculum learning and training directly on the target distribution.
- Naive curricula may encourage distributed representations that use much of the hidden state for easier examples requiring less memorization.Adding longer numbers requires retaining more digits before producing output, increasing the memorization demand.
- The combined strategy reduces memory-pattern restructuring by combining naive-curriculum examples with a mixture of examples at all difficulties.The naive component supplies intermediate input-output mappings, while mixed examples discourage allocating all memory to easy cases.
8 CRITIQUE
High prediction accuracy does not establish that an LSTM learned the correct program algorithm, because memorization and shortcut strategies can produce plausible outputs. The authors therefore leave the model’s reliance on memorization unresolved.
- Perfect program-output prediction requires understanding all operands, concepts, and their precise composition.
- Addition is especially demanding because the model must preserve number order and compute carries correctly.
- Element-wise addition can achieve perfect outputs when no carry occurs, without implementing full addition.
- Memorizing two-digit addition results can yield reasonably high accuracy while remaining far from correct.
- The authors do not know how much the model relies on memorization because training and test distributions are identical.
9 DISCUSSION
The study shows that sequence-to-sequence LSTMs can learn to evaluate programs with limited prior knowledge, while curriculum learning and input doubling support performance. However, the results remain bounded by runtime and curriculum uncertainties.
- The authors show that LSTMs can learn program evaluation with limited prior knowledge.
- Correct curriculum learning is crucial for difficult tasks that standard SGD cannot optimize.
- Doubling the input reliably improves sequence-to-sequence LSTM performance.
- The method cannot evaluate arbitrary programs, including programs requiring more than O(n) time, because conventional RNNs and LSTMs have runtime restrictions.
- The optimal curriculum strategy remains unknown and may require identifying the training samples most beneficial to the model.
SUPPLEMENTARY MATERIAL
The supplementary algorithm generates Python programs by composing randomly selected operations over nested structures, evaluating them, and assigning resulting examples to dataset splits.
- Programs are generated across a requested length and nesting depth using a nesting stack.
- The operation set includes addition, subtraction, multiplication, if-statements, for-loops, and variable assignment.
- Each operation samples parameter values, evaluates them, generates code, and pushes the resulting value-code pair onto the stack.
- Random integer values are converted to strings, appended to the values and code lists, and then used to construct new operations.
- Completed examples are assigned to training, validation, or testing by hashing the final code modulo three.
11 ADDITIONAL RESULTS ON THE MEMORIZATION PROBLEM
The authors additionally evaluate the kinds of predictions produced by trained LSTMs on a memorization task. Because teacher forcing supplies correct previous output digits, samples with early errors require careful interpretation.
- The study presents the training-case generation algorithm and an extensive qualitative evaluation of trained LSTM predictions.
- Teacher forcing provides the correct output digit at step i when predicting digit i + 1, even after an earlier error.
- A prediction that errs early but produces later correct digits should not be interpreted as fully autonomous success.
12 QUALITATIVE EVALUATION OF THE CURRICULUM STRATEGIES
The qualitative evaluation compares baseline, naive, mix, and combined curriculum strategies across program-execution examples and memorization settings. Figure 8 varies input length, input transformations, and curriculum strategy under a 20-epoch limit.
- Memorization-task comparison: Figure 8 evaluates four curriculum strategies on memorization inputs ranging from 5 to 65 digits under four input-modification schemes.The schemes are no modification, inversion, doubling, and doubling plus inversion; training is limited to 20 epochs.
- Program-evaluation examples: For one displayed example, the baseline, naive, and combined strategies produce predictions of -2320, -2201, and -2317, respectively.
- Program-evaluation examples: On another example, the baseline and combined strategies both predict 5196, whereas the naive strategy predicts 5104.