Show Your Work: Scratchpads for Intermediate Computation with Language Models
Authors: Maxwell Nye
Anders Johan Andreassen
Guy Gur-Ari
Henryk Michalewski
Jacob Austin
David Bieber
David Dohan
Aitor Lewkowycz
Maarten Bosma
David Luan
Charles Sutton
Augustus Odena
Venue: ICLR 2022 Submitted (2022)
Keywords: program synthesis
transformers
language models
pre-training
program induction

Abstract: Large pre-trained language models perform remarkably well on tasks that can be done "in one pass", such as generating realistic text or synthesizing computer programs. However, they struggle with tasks that require unbounded multi-step computation, such as adding integers  or executing programs. Surprisingly, we find that these same models are able to perform complex multi-step computations --- even in the few-shot regime --- when asked to perform the operation "step by step", showing the results of intermediate computations. In particular, we train transformers to perform multi-step computations by asking them to emit intermediate computation steps into a "scratchpad". On a series of increasingly complex tasks ranging from long addition to the execution of arbitrary programs, we show that scratchpads dramatically improve the ability of language models to perform multi-step computations. 

Under review as a conference paper at ICLR 2022
SHOW YOUR WORK: SCRATCHPADS FOR INTERMEDI- ATE COMPUTATION WITH LANGUAGE MODELS
An Anonymous authors
Paper under double-blind review
ABSTRACT
Large pre-trained language models perform remarkably well on tasks that can be done "in one pass", such as generating realistic text (Brown et al. 2020) or syn- thesizing computer programs (Chen et al., 2021 Austin et al. (021). However, they struggle with tasks that require unbounded multi-step computation, such adding integers (Brown et al. 2020) or executing programs (Austin et al. 202T). Surprisingly, find that these same models are able perform complex multi- step computations even the few-shot regime- when asked to perform the op- eration "step by step". showing the results of intermediate computations. In par- ticular, we train Transformers to perform multi-step computations by asking them emit intermediate computation steps into "scratchpad". On a series of in- creasingly complex tasks ranging from long addition to the execution of arbitrary programs, we show that scratchpads dramatically improve the ability of language models to perform multi-step computations.
INTRODUCTION
Large Transformer- -basefdmmer---eddddddded language models exhibit surprisingly impressive capabilities (Devlin et al. 2019 Brown et al.) 2020), including the ability to generate code that solves simple programming problems (Chen et al., 2021 Austin et al. (002). However, these models struggle to perform multi- step algorithmic calculations, especially those that require precise reasoning and unbounded com- putation. For example, GPT-3 struggles to perform few-shot addition on numbers with greater than three digits (Brown et al., 2020). Similarly, large-scale language models struggle to predict the re- sult of executing Python code, even code which is solution to programming task the model is able to solve (Austin et al., 2021). Likewise, standard recurrent and graph neural networks fail to systematically generalize when predicting the output of simple programs with loops (Bieber et al.) 2020). So language models can to some extent write code, but do not seem to accurately represent the semantics of the code they write, because they cannot predict its execution. This has moti- vated research on networks that can perform algorithmic reasoning (Graves et al.) 2014 Zaremba & Sutskever 2014 Bieber et al., 2020). Neural networks that accurately represent the semantics of programs could enable a variety of downstream tasks, including program synthesis (Devlin et al.] 2017), program analysis (Allaaanis et al. 2018), and other algorithmic reasoning tasks (Velickovic & Blundeell 2021).
Why do large language models struggle with algorithmic reasoning tasks? We suggest that this is least partly due to a limitation of the way the Transformer architecture is applied to these tasks: the model is asked to perform these tasks in one forward pass. Given a fixed number of layers and fixed amount of computation time, the model cannot adapt the amount of compute spent on a problem to its difficulty before producing an output"" Prior work (Graves) 2016 Banino et al., 2021 has explored neural architectures that explicitly allow for dynamically chosen amounts of computation time to be dedicated to different sub-tasks. this work, we propose a different approach- that
'Transformers perform computation which is quadratic in length of the input sequence, so are theoret- ically unable to perfectly simulate algorithms which have greater time complexity than O(n²). However, it is unclear how relevant this theoretical bound is in practice; neural sequence prediction is approximate, and Trans- formers may be large enough in practice to effectively memorize the correct solutions for relevant subspace of the possible inputs (e.g., all inputs up certain size).

---

Under review as a conference paper at ICLR 2022
DIRECT EXECUTION PREDICTION
Consider the following Python function:
def' renove_ Decvee.Dcc(s, ch):
for in (len))))::)):
if [al1] =s ch):
= 4EO <[1
1:3
break for (e))) 1,-1,11)
Large Language Model
remove_Oct( (mooveOOc((PPP",, "P") "H"
[sE1]
sli
return
fill in the below:
assert renove_ Occ( "P") (p')==== ???
SCRATCHPAD TRACING
state: []
line: def resove Occ(s,ch):
state: ("raxove "ome"e__0c""" "scallable_chjee _bbje_ebjjcctt rexove_Occ=")
lime: ouiput
Consider the Following Python Function:
state: ("ch": *p" "s": "PHP')
line: for i. ranse()
def range(len(s)):
("ch": *p* *s": "PHP "1"
if (s[i] ch):
(a(i) ch):
state: ("ch": "p" "s":
== i] "1"
5[0 break for i range(len(s) 1,4,-1:
state: ("ch": "P", "s" "HP", "1"
Large Language
line:
break
(+[1) = ch):
Model
state: ("ch": ept. "s" "P* 41"
5 = sEA 10 alt 1:1 break
line: For i range(len(s) 1,c1,, 1,1,,
state: ("ch": *p" *e* "HP" "1"
recurn
line:
if (s[i] - ch):
state: ("ch": "p" "s". "H" "1";
Ooot "PHPP"
line:
s in sEi
state: ("ch": "P" "s": "H² "1 1)
Mhat che execution trace?
line:
break
state: ("ch": *P", "s" 'H", "1"
return
state: ("remove_Occ "scallable_co objjettteeoeeeteeeeeeeeee resove_Occ"*
"output": "H*)
Figure 1: Overview of our scratchpad approach applied to predicting code execution and comparison to direct execution prediction. Top: Previous work has shown that large pre-trained models achieve poor performance when asked to directly predict the result of executing given computer code (Austin) et al., 202T). Bottom: this work, we show that training models to use a scratchpad and predict the program execution trace line-by-ling can lead to large improvements in execution prediction performance. N.B. Although the example above only has one loop iteration for each loop, all loops unrolled across time.
can exploit existing Transformer architectures and large few-shot-capable language models modify the task design rather than the model or training procedure.
Our proposal is simple: Allow the model to produce arbitrary sequence of intermediate tokens, which we call a scratchpad, before producing the final answer. For example, on addition problems, the scratchpad contains the intermediate results from standard long addition algorithm (see Figure 2}. To train the model, we encode the intermediate steps of the algorithm as text and use standard supervised training.
This paper makes the following contributions:
We introduce (Section 2 the notion of a "scratchpad" for Transformers, in order to make them better at performing complex discrete computations without modifying the underlying architec- ture.
We show (Section 3) that scratchpads help Transformers learn to perform long addition in the fine-tuning regime, and in particular that they improve out-of-distributtin generalization to larger problem instances.
We also find (Section 4 that scratchpads help Transformers perform a somewhat higher level task: polynomial evaluation. This is true in both the few-shot and fine-tuning regimes.
Finally, we move much more general context and show (Section that training Transformers to emit full program traces line by line annotated with local variables dramatically improves their ability to predict the result of executing a given computer program on a particular input. This application in some sense subsumes the others.
2

---

Under review as a conference paper at ICLR 2022
2
METHOD
In this work we consider two related problems: algorithm induction (Graves et al., 2014 2016
Kurach al., 2016, Kaiser & Sutskever 2016) and learning to execute (Zaremba Sutskever 2014 Bieber et al. 2020). The goal of both problems is for the neural network to learn to emulate a function f, which is "algorithmic" in the sense that it can be represented by a short program, such as addition or polynomial evaluation, from input-output behavior. In neural algorithm induction, the goal is to learn single algorithm, and each training example gives single input and desired output represented as strings. Therefore, the training data is D {æ,, f (z;) } For learning to execute, we want the model produce the result of program. represented as source code, on some input. If each is the source code of a program ft. then the training data is D = {(T; Bi, f(x)))) (it is common for each fa have multiple input-output examples, but we omit this to lighten notation).
The main idea of this paper is that to solve a given algorithmic task, we simply encode the inter- mediate steps of the algorithm as text and train the model to emit them to a buffer that we call a "scratchpad." For example, let us consider the algorithmic induction task of learning long addition. To teach a model to add 29 to 57, a training example may look like the text in Figure 2 where the steps of the sradelschool long addition algorithm written out explicitly.
Learning to execute tasks can be encoded similar way, except now we add the source code Ty before the input, scratchpad, and desired out- put. An example of training example for learning to execute task is shown in Figure
Input: 9 + 5
Target:
At training time, the model will be given the input plus target for standard likelihood-based training. At test time, the model will be given only the input and will be required to predict the target, e-g., by beam search or temperature sam- pling. In principle, any sequence model could be used for this. In this work, we choose to use decoder-only Transformer language mod- els, but other sequence models could be effec- tive, such as encoder-decoder models (Raffel ct al. 2019), or recurrent networks.
<scratch>
2 + 5 7
C:
2 5 6 C: 1 # added 9 + 7 = carry 1
8 6 c:
# added 2 5 + 1 = carry 0
0 8
</scratch>
8
Figure 2: Example of input and target for addition with scratchpad. The carry is recorded in the digit following "C:". Comments (marked by #) added for clarity and
part of the target.
Adding a scratchpad has several potential ad- vantages: First, the model has adaptive compu- tation time, that is, it can now process the information for as long needed, depending the complexity of the task given the input. Second, the model can store the intermediate state of its computation in the seratch buffer and refer back to it by attending its context. This removes the need to store all intermediate state in activations. Third, by forcing the model to output con- crete intermediate states by sampling from the generative model, we aim reduce the propagation and compounding of small errors, because states are quantized to token embeddings. Compounded errors can show up in methods like Neural Turing Machines (Graves et al., (2014)- -that use recur- rence to support extended computations. Finally, examining model''s 's scratchpad output can help us identify common errors and correct them by revising the scratchpad format. We found this ability to interpret enrors to be useful in this work.
For all experiments, we used pre-trained dense decoder-only Transformer language models, ranging in size from 2 million to around 100 billion parameters (with the largest denoted 100B+). These models were pre-trained on web documents and dialog data. We omit some details here- pere--icluuding exact model sizes for double-blind review, but will include specific details in the published version.
3 ADDITION
As first task, we consider integer addition. The baseline addition task presents two numbers as the input, and the target is their sum. For example
We introduce spaces between the digits to ensure that each digit is mapped to separate token.
3

---

Under review as a conference paper at ICLR 2022
Addition: In-Distribution Accuracy
Addition: OOD Accuracy 19 digits)
Addition: 00D Accuracy (10 digits)
100
100
100
baseline scratchpad
baseline
baseling
80
scratchpad
scr pratchppd
Accunsy
6.0
60
60
20
20
20
Parameter Count
Parameter Count
Farameter Count
Figure 3: Using scratchpad significantly improves the performance of pre-trained Transformer- based models on addition, including their ability to generalize out of the training distribution to numbers with more digits. Models were trained on 1-8 digit addition. The baseline models were trained without intermediate scratchpad steps.
Input: Target: 8 6
We implement the scratchpad by including the intermediate steps of the long addition algorithm in the target, as Figure We train several models on integer addition problems with inputs that have 1-8 digits. We then test performance on in in-distribution addition problems (with up to 8 digit inputs), and on
problems with 9 and 10 digit inputs. The models were fine-tuned on 100k examples for 5k steps with batch size 32. There are 10k in-distribution test examples, and 1k test examples for each out-of-distribution task. We examine the performance as function of model size, ranging from 2M to IB parameters. We compare performance to baseline which includes the input and target numbers, but no intermediate scratchpad steps.
Results Figure 3 compares the performance of the scratchpad algorithm with the baseline. We that beyond critical model size, models are able to solve the addition task using the scratchpad, while models trained without scratchpad fail to do even at the largest tested scale. On the out-of- distribution tasks (9-10 digit addition), we find that models trained without scratchpad completely fail, while models trained with scratchpad show consistent improvement as function of model size.
POLYNOMIAL EVALUATION
Next we focus on a slightly higher-level task: evaluating polynomials. Inspired by the "polynomial evaluation" subproblem in Saxton et al. (2019), we generate dataset of polynomials of degree less than or equal to three, with integer coefficients and inputs constrained to the range [-10, 10). We also restrict outputs to the range [- 1000,, 1000]. We generate training dataset of 10,000 polynomials and a test dataset size 2.000. An example scratchpad target for this task shown in Figure 4 with each term of the polynomial evaluated separately. As in the previous section, we compare the results of direct execution with the results of using the scratchpad. In this experiment, we evaluate in the few-shot regime using a 100B+ parameter pre-train treitriined decoder-only model, previous work indicates that very large models may be able to perform additions and multiplications with 3 or fewer digits few-shot (Brown al. 2020). We use n 4 example problems in the few-shot prompt. We also evaluate in the fine-tuning regime with an 8B parameter model fine-tuned for 2000 steps on the training set. The results of both evaluations are shown in Table We find that scratchpad execution outperforms direct execution significantly in both the few-shot and fine-tuning regimes.
5 EXECUTING PYTHON PROGRAMS
We have shown that scratchpads can help algorithm induction, that is, they can help models learn to implement a particular algorithm with direct algorithm-specific supervision. But needing to hand- design the intermediate states for every new task is sub-optimal. In this section, we evaluate whether a model can learn to implement a new algorithm by executing arbitrary code. To test this capability, follow the problem setup from Austin al. 2222)) in which language models asked predict the result of executing a given Python program on a particular input. Language models performed poorly at this task, even programs which are solutions a programming tasks the model is able
4

---

Under review as a conference paper at ICLR 2022
Input:
Evaluate -7ax=02 Tex 5
Table 1: Results for polynomial evaluation task. Scratchpad outperforms direct predic- tion whether using fine-tuning or few-shot.
Target:
<scratch>
-7Axt=2: -7
7ex:
5: 5
</scratch>
Few-shot
Fine- Fine-tuning
total:
Direct prediction 8.8%
31.8%
Scratchpad
20.1 %
50.7% %
Figure 4: Example of polynomial evaluation with scratchpad. Each term in the polyno- mial is computed separately and then added.
solve, Here we show that the scratchpad technique can dramatically improve the ability of language models to execute programs.
Direct execution prediction Our main baseline the direct execution prediction procedure ex- plored in Austin et al. (202I). Models are shown the source code for a function, and asked predict the output of running the function on specific inputs. For example, the function in Figure [ takes as input string s and a character ch, and removes the first and last instances of the character ch from the string s. The direct execution prompt and target for this task are shown in the "Direct Execution Prediction" box in Figure T A task considered solved under this regime if the model correctly outputs the target string.
Execution prediction via seratchpad tracing As discussed above, direct execution prediction requires the model to correctly output the result of executing the entire function in single pass. Direct execution prediction has been shown to perform poorly on Python programs in Austin et al. (202T) We therefore design a scratchpad formulation of the execution task, in which models predict the output of program by first predicting the sequence of intermediate states computed during the program's 's execution. Formally, we train models to predict an alternating sequence of 1) the ordered sequence of source code lines executed, and 2) the state of the local variables after each line is executed. We call this object the program's 'ss trace, and it allows us track both the control flow the sequence of operations executed-and how the state changes represent the trace as a string, with the line of code reproduced directly, and the state information represented as JSON dictionary{ For example, the "Scratchpad Tracing" box in Figure contains the tracing prompt and trace target for the function discussed above.
result of each operation. We
Concretely, for each function to be traced, the prompt is formed by printing the function definition, followed by a line which calls the function on a particular input: output fn fn_name (input. .aauue..aaee where fn_name and input value are replaced with the corresponding function name and input value. In Figure [1] note how the correct output of remove Occ(""HPP "P") is shown the last line of the trace, assigned the variable "output". A tracing example is considered to have the correct execution output if the encoding of the value assigned to the variable output in the last line semantic match with the target output value (here. "output": "P"). We consider task to be executed correctly if all given input-output examples are correctly executed. We can also test whether there is "trace exact match" between the model prediction and the ground truth trace, by a) semantically comparing each state in the trace to the corresponding state in the ground truth trace, and b) comparing the sequence of source code lines predicted with the ground truth sequence.
Experimental setup
As prroff-ff-concep.. we first show that scratchpad tracing greatly improves execution performance on synthetic Python data. Then, we compare scratchpad tracing and execu- tion on the human-written Python problems from Austin al. (2021). We find that novel data augmentation technique that uses programs generated by the model as additional training data can significantly increase tracing performance on real data, whereas this augmentation technique hurts
'Some objects cannot be represented using this JSON representation. Some objects (such as tuples) are represented by the closest JSON data type (in this case, lists). Other objects, such as user-constructed objects, are represented by placcholder string, e.g., "cobject myObject>". Functions are also represented as strings, e.g, "scallable object f>".
5

---

Under review as a conference paper at ICLR 2022
Table 2: Synthetic tracing and execution re- sults. Scratchpad outperforms direct predic- tion both for few-shot and fine-tuned. *The accuracy criterion for the few-shot scratch- pad condition was slightly modified, the text Section 5.1 for more details.
def r(v8): +*
while v4
v4 -= 1
return ve
output F(B)
shot Fine-tuned
Direct prediction Scratchpad
11%
20%
Figure 5: Example synthetic Python program
26.5%
41.5%
performance for direct execution. Finally, we show that incorporating tracing data from additional sources further improves tracing performance, indicating that the scratchpad tracing technique plored here may scale well with more data.
For all experiments on Python code, we use a Transformer model with around 100 billion parameters (100B+), a context window of 1024 tokens and a limit of 512 generation tokens. Unless otherwise stated, all fine-ture ane-tuning runs used a batch size of 8192 tokens and a learning rate of 3e-5, and model inference was performed with decoding temperature set to T = 0, equivalent to greedy decoding.
5.1 SCRATCHPAD BEATS DIRECT EXECUTION FOR SYNTHETIC PYTHON PROGRAMS
In our first experiment, we test the few-shot and fine-tuned execution capabilities of our models on simple synthetic Python programs. This provides proof-of-concept for our tracing technique.
We use a dataset of synthetic Python programs modified from Bieber et al. (2020). These programs include small integers (0, and 2), simple while loops, and if statements. We construct corpus of synthetic programs to mimic the size of the MBPP dataset in Austin et al. (2021), with 400 training programs, 100 validation programs, and 200 test programs. For each program, three random integer inputs are sampled from the range 0 to 9.
We test execution and scratchpad tracing under both few-shot and fine-tuning conditions. For few- shot experiments, the prompt contains three examples of previous tracing problems, as shown in Appendix C For fine-tuned experiments, we fine-tune models to convergence on the training split, as judged by validation perplexity.
For the few-shot scratchpad experiment, we noticed that models would not assign the variable name output to the final value in the trace, and would instead continue using vθ (the name of the variable returned in the function f) as the variable name for the final output line. We therefore modified the accuracy criterion from checking whether the value of output in the last line of the trace is correct, to checking whether the value of vθ is correct. (Under naive scoring, the few-shot tracing accuracy is roughly zero.) An example of this behavior is shown in Appendix D
Results Table 2 shows our results on synthetic Python problems. In both few-shot and fine-tuned settings, the scratchpad tracing technique leads to higher overall execution accuracy on the 200 test problems. Fine-tuning also improves performance more for the scratchpad tracing technique than it does for direct execution.
5.2 SCRATCHPAD BEATS DIRECT EXECUTION FOR REAL PROGRAMS
In our second set of experiments, we explore how well the scratchpad performs compared exe- cution on real data. Our main evaluation dataset is the MBPP dataset, introduced in Austin et al. (0221. MBPP consists of 1000 programming problems, each of which contains natural language specification, ground-truti -ruth Python program, and three input-output test cases. These programs involve computation using a large variety of types, including ints, strings, floats, dictionaries, tuples, and more, and include many language features and control-flow structures, such as loops, com- prehensions, library imports, API calls and recursion. The evaluation split of the MBPP dataset contains 500 tasks. In order to separate out effects of the generation window size, report all eval- uation metrics on the subset of these tasks for which the ground- truth trace fits within the generation window of the model for all three of the input-output examples. This leaves subset of 212 test

---

Under review as a conference paper at ICLR 2022
Table 3: Comparison of models fine-tuned on different data sets and evaluated on MBPP programs. We report "per-task" execution and tracing accuracies, which require all examples be correctly executed/traced. We additionally report "per-example" accuracies. which correspond to the total fraction of test examples which are exccuted/traced correctly across the dataset. We find that training scratchpad models on dataset augmented with samples from the model significantly improves performance for the scratchpad model, while it harms the direct execution model. Combining tracing training data from several sources further improves scratchpad model performance.
Direct execution
Scratchpad
MBPP MBPP-aug
MBPP
MBPP-aug MBPP-aug MBPP-aug MBPP-aug +CodeNet +single line
+CodeNet
+single line
(55.2.1
($5.2.2)
(.5.2.1
5.2.22
($5.3)
($5.3)
($5.3)
per-task execution acc: per-task trace acc:
10.3
5.1
5.1
17.3
26.6
25.2
23.4
p/a
n/a
0.9
13.1
24.6
22.0
21.5
per-example execution per-example trace acc:
22.0
12.3
24.6
35.5
46.0
45.3
43.5
n/a
n/a
6.7
26.8
41.9
42.1
40.2
tasks. Increasing generation and context window length an important issue for Transformer-based models, but we view it orthogonal and leave for future work.
5.2.1 PERFORMANCE IS POOR THE VERY-LOW-DAYE REGIME
In our first experiment with the MBPP data, we train scratchpad tracing model on the 374 training tasks (3 examples per task, so 1 1122 overall examples). We discard all training examples which ex- ceed the context window. We compare overall execution results against a model trained on the same 374 training tasks to perform direct execution. The columns labeled "MBPP" for Direct Execution and Scratchpad in Table 3 show the results of this experiment. Neither the scratchpad model or the direct execution model achieve good performance (5% and 10% output accuracy, respectively), and direct execution outperforms the scratchpad model.
5.2.2 SAMPLED PROGRAMS MAKE GOOD SCRATCHPAD TRAINING DATA
Next, we employ a data augmentation technique to increase the size of the training dataset: We first run few-shot synthesis on the 374 MBPP training tasks using the pre-trained 100B+ model, as described in (Asttin et al. (202T). For each task, we sample and record 80 candidate programs {Pa} from the model at temperature T = 0.5. We can then create a new execution datapoint using the candidate program P.. the original three inputs for the task {=:)i=1.2.3. and the three new outputs which result from running the candidate program on original three inputs: (Vhoow ) 1 where Vew = (x.). We discard any candidate programs for which execution results in error. Note that the outputs of Vinew may or may not be equal to the original outputs, depending on the computation performed by the generated program P.. Therefore, this augmented direct execution dataset has both additional new programs and new outputs compared to the original dataset. We can analogously create tracing dataset for our scratchpad model by tracing the execution of each candidate program Pa on each I;, This process produces much larger tracing and execution datasets with 17k new programs, which we refer to as MBPP-aug.
Conceptually, we have augmented the dataset using a combination of tools already available to us, namely a) the neural model, and b) program execution via a Python interpreter. We fine-tune direct execution and scratchpad models on this new augmented dataset MBPP-aug, using the same process as above.
The "MBPP-aus columns in Table Bable3shore show the results of this experiment. While the direct execution approach suffers a decrease in accuracy when trained on this additional data, the performance of the scratchpad model is greatly improved; the model trained on the augmented data solves more than three times the number of tasks as the model trained on only the original MBPP programs. We also note that if we measure the raw correctness across samples, the model already achieves 26.8% exact trace match, which is surprisingly high.
5.3 SCRATCHPAD TRAINING MAKES GOOD USE OF LARGE DATASETS

---

Under review as a conference paper at ICLR 2022
state:
codee: // output:
state: g 168;
[126, 168, 8, -100, -1803;
code: I[i]; output: g 200; i = 1; 1 [109, 188, 8, -180, -1803;
state: "asbbed";
code: set(s); output: f'a', 'b', 'e", "d "sabbed";
state:
code: f output: f 62; 11; 53;
a. b, x nap(int, input().split)) split() if
if 1090 == print(ar(w/1180)
else:
if (x x 1888) / 500
print(min((n(xx/1800 a*(x//1000) b-2))
else:
print(nin(ar(x//188 1), an(x//1060) b))
else:
x 500 8: print(bexxx/5000)
else:
print(b=(x//500
Figure 6: Top: examples of single line data. Bottom: example CodeNet submission.
In this section, we examine whether collecting additional tracing data from human-written pro- grams further improves tracing performance. This will allow us to understand whether the tracing procedure here is likely scale well when slightly out-of-distribution tracing data is added the fine-tuning set. We experiment using two datasets:
Single-line programs This dataset consists of roughly 9 million examples of single-line Python transformations. Figure 6 (Top) shows examples of these transformations. Each transformation consists of an initial set variables and corresponding values, a single line of Python (together these form the input), and the new set of variables and values which results from running the line (the target). When training on single-line data, we do not introduce intermediate scratchpad steps. While this dataset does not provide examples of the high-level, multi-line control flow of trace, the data provides good supervision for modeling the execution of individual lines of code, which is key component of tracing. This data was collected by Fraser Greenlee, and can be accessed here
CodeNet The Project CodeNet dataset (Puri et al. 2021) consists of millions of user submissions to approximately 4,000 coding problems. These submission include both correct and incorrect so- lutions to programming problems. However, from the experiment with MBPP-aug above, we know that incorrect or broken programs can still provide useful training signal. We additionally improved our tracing technique to allow tracing programs with errors; when error is reached, the error mes- sage is added to the end of the trace text and tracing is stopped. We extracted a total 670,904 traces from the CodeNet data. For each dataset, first fine-tune the model on these datasets, and then perform a second fine-tuning on MBPP-aug until convergence.
Results Results are shown Table As above, report execution accuracy across tasks. We additionally report trace accuracy across tasks, to understand the extent to which the entire trace is accurately predicted. We also report the raw execution and trace accuracy across all test examples, as an additional metric to compare models.
Training on either the single-line dataset the CodeNet dataset alone seem to both provide gains over MBPP-aug (23.4% and 25.2% tasks executed correctly. respectively). However, combining both CodeNet and the single-line dataset seems lead to the highest performance; tracing produces the correct final output for 26.6% of the tasks, and nearly quarter of the tasks (24.6%) are traced perfectly for all three examples. These results seem promising: the neural network can often exactly trace programs. In particular, greedily decoding from the best model produces the exact correct trace for almost 42% all traces.
6 RELATED WORK
The tasks in this paper can be viewed as exploring one criticism large language models, namely, to what extent do they simply rely on surface-level statistical correlations text, without learn-
8

---

Under review as a conference paper at ICLR 2022
ing semantics world knowledge (Bender & Koller 2020)? ? In response, Li et al. (2021) provide evidence that pre-trained language models do indeed construct approximate representations of the semantics of the situations they describe in text. In the context of programs, [Austin et al. (2021) approach this question by exploring the learning to execute task on MBPP, which we consider in Section [5.2] The idea behind this task to explore whether neural models for synthesis that gen- crate code could also execute it. While that work finds existing models perform poorly at predicting execution, we show that adding scratchpad allows these models perform better.
Work in learning to execute has considered whether off-the-shelf recurrent neural networks (Zaremba & Sutskever, (2014) or more specialized architectures (Dehghami al., 2 Bieber al. 2020 Wang et 2020) have an inductive bias that is sufficiently well suited for executing and reasoning about arbitrary code. The related problem of neural algorithm induction has attracted considerable interest (Graves et al., 2014, Kurach et al.
2016 Kaiser & Sutskever, 2016 Graves)
jet al., 2016; Reed & de Freitas| 2016] Veličković et al. 2020a b). This work proposes new neural architectures, inspired by theoretical models of computation, whose inductive bias allows them to more easily learn algorithm induction tasks. Several methods for algorithm induction specifically add adaptive computation time to sequence models (Graves) 2016; Dehghani al., 2018 Banino jet al., 2021). In particular, universal transformers include adaptive computation time, and are eval- uated both on algorithm induction and on learning execute tasks (Dehghani al. 2018). In contrast, a scratchpad is a simple way both to provide a transformer model with adaptive compu- tation time, and also to provide supervision about how use that additional computation, without requiring modification to the underlying architecture.
Algorithm induction has also been connected to pre-trained models. Lu et al. (2021) show that Transformers can be used to some extent as universal computation engines, by pre-training on natu- ral language, and fine-tuning a small fraction of the weights on non-language tasks, including simple algorithm induction tasks. Finally, supervised approaches to semantic parsing (Zelle & Mooney, 1996 Zettleoyyr Collins, 2005) Kwiatkowksi et al., 2010, WWong & Mooney] (006) predict the text of database query, which can then be executed to answer natural language question.
7 LIMITATIONS AND FUTURE WORK
Context window size In this work, we limit our experiments to problems where the scratchpad text fits within the model generation window (512 tokens). However, many problems require very long scratchpad generations. Therefore, fully realizing the potential of the scratchpad technique may require further improvements in transformer generation window size. This is an active area of research in NLP (Tay et al. 2020), and improvements would be beneficial for the scratchpad technique.
Learning use the seratchpad without supervision A clear next step to try to learn to use the scratchpad without direct supervision. A simple method would be to use reinforcement learn- ing (RL) techniques: models would be rewarded for correctly answering questions, with reward inversely proportional to the number of scratchpad tokens used. We would hope that learning to use the seratchpad would be a transferable skill; for example, a model could potentially use the algorithm it learned to perform long addition to succeed at polynomial evaluation.
CONCLUSION
In this work we showed-througe experiments on long addition, polynomial evaluation, and Python code exccution- that allowing models to read from and write to a simple scratchpad can improve their performance algorithmic tasks. Such models may be a first step toward combining the comppeeseooooosiooonnnnoooo capabilities of large language models with reasoning capabilities, in order to build models that understand code well as write it. This could be useful for a variety of ap- plications that require both working with natural language and reasoning about program semantics, such program synthesis, neural-guided program analysis, and interactive programming assistants. The scratchpad technique presented here might not take us all the way toward that goal, but we hope is an important step.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY
All fine-tuning and evaluation datasets used in this work are either open source or synthetic and easily reproducible (this excludes MBPP-Aug. which depends generations from the pre-trained transformer model used in this work). Examples of exact prompts are shown in the Appendix, so that they can be exactly reproduced. Although the pre-training details are not open-source, they correspond to the details in Austin et al. (2021).
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations (ICLR), February 2018.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry. Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108. 107.072.. 2021.
Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning to ponder. In 8th ICML Workshop on Automated Machine Learning (AutoMI.), 2021.
Emily M. Bender and Alexander Koller. Climbing towards NLU: On meaning. form, and under- standing in the age of data. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 5185-5198, Online, July 2020. Association for Computational URL
Linguistics. doi: 10. 10.18653//1/2200.aall mll-main.463. maa..mm.......mmm.............
acl -maim.annn4. 463
David Bieber, Charles Sutton, Hugo Larochelle, and Daniel Tarlow. Learning execute programs with instruction pointer attention graph neural networks. In H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 6626-8637. Curran Associates, Inc., 2020. httphttts///ccceeeeheieeo neurips. 1ba0000003344444669PPPPP Paper
cc/
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Kerbert-Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess. Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, abs/2005. 14165, 2020. URL / https//////xxiiooo/aa///////
14165
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Ed- wards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Win- ter, Philippe Tillet, Felipe Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Eliza- beth Barnes, Ariel Herbert- Voss, Will Guss, Alex Nichol, Igor Babuschkin, Suchir Balaji, Shan- tanu Jain, Andrew Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, 1lya Sutskever, and Wojeiech Zaremba. Evaluating large lan- guage models trained on code, July 2021. HtRLLhttt///axxttoe org/ abs/ wtwp////...... 03374
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. July 2018
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. CoRR, abs/1 770.00746, 2017. URL htttp://aaxxi.org//bbb..st
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Associ- ation Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), 2019.
10

---

Under review as a conference paper at ICLR 2022
Alex Graves. Adaptive computation time for recurrent neural networks. arXiv:1603.08983 2016.
arXiv preprint
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, abs/1410.5401, 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomenech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626): 471-476, 2016.
Lukasz Kaiser and Nya Sutskever. Neural gpus learn algorithms. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. In International Conference Learning Representations, (ICLR), 2016.
Tom Kwiatkowksi, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. Inducing probabilis- tic CCG grammars from logical form with higher-order unification. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pp. 022--1333, October 2010.
Belinda Z. Li, Maxwell Nye, and Jacob Andreas. Implicit representations of meaning in neural language models. ArXiv, abs/2106.00737, 2021.
Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Pretrained transformers universal computation engines. March 2021.
Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladmir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, Veronika Thost, Luca Buratti, Saurabh Pujar, and Ulrich Finkler. Project CodeNet: A Large-Scale AI for code dataset for learning diversity of coding tasks. May 2021. URL http:://aaaxiv.rg/aabb//////////
12655
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. CoRR, abs/1910.10683. 2019. httllltpp://xiiiorrr/aaaaas//
http///bs/199... 10683
Scott Reed and Nando de Freitas. Neural programimer-inteepreten... International Conference on Learning Representations (ICLR), 2016. URL http:://////xii wwt.or//pppp////11///////
/ 06279v3
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical rea- soning abilities of neural models. CoRR, abs/1904.01557, 2019. URL/nttp://arsiv.orr///
0155.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. CORR, abs/201 1. 1,04006, 2020. URL httttss//aaxxiv.orrr//////////// 1.040
Petar Velickovic and Charles Blundell. Neural algorithmic reasoning, CoRR, 2bB2222221100.02 2011. 02761
Petar Veličković, Lars Buesing, Matthew C. Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks, 2020a.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execu- tion of graph algorithms, 2020b.
Yu Wang, Fengjuan Gao, Linzhang Wang, and Ke Wang. Learning semantic program embeddings with graph interval neural network, 2020.

---

Under review as a conference paper at ICLR 2022
Yuk Wah Wong and Raymond J Mooney. Learning for semantic parsing with statistical machine translation. In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics Morristown, NJ, USA, 2006. Association for Computational Linguistics.
Wojciech Zaremba and Ilya Sutskever. Learning to execute. ArXiv, 0bss/14104461,, 2014.
J Zelle and R Mooney. Learning parse database queries using inductive logic programming. In National Conference on Artificial Intelligence (AAAI), 1996.
Luke S Zettlemoyer and Michael Collins. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Uncertainty Artificial Intelligence, July 2005.
A EFFECTS OF SCRATCHPAD EXECUTION TRAINING ON SYNTHESIS PERFORMANCE
To measure the extent which fine-tuning on the tracing task described above affects the model's ability to perform program synthesis, we ran few-shot synthesis experiment using the "MBPP- aug + CodeNet + single line" model. Specifically, we performed few-shot synthesis on the MBPP dataset, as described in Austin et al. (2021). For each MBPP synthesis task, 80 candidate programs are sampled from the model (T 0.5), and the task is considered solved if any of the candidate programs satisfy all three test cases. For more details, see Austin et al. (202T). The "MBPP-aug CodeNet single line" model achieved an overall synthesis accuracy of 54%, compared to the 62% accuracy of the original few-shot model in Austin et al. (2021). This indicates that the scratchpad execution training does not completely disrup the model's 's ability to perform other few-shot tasks.
B LONG ADDITION ABLATION STUDY
In our long addition experiments in Section 3 we compared a model that was trained to perform "direct execution" (the baseline) model trained to use scratchpad. Since the model trained to use the scratchpad gets an additional signal from all the intermediate steps shown, we also study what happens if the scratchpad model is subsequently trained to perform direct execution (i.e., di- rectly output the target without using the scratchpad). The result is shown in Figure 7 where we followed the same training procedure as for the original direct execution baseline and scratchpad models. We see no significant benefits from doing any intermediate training using a scratchpad. This indicates that the extra training-tin maining-time information seen by the scratchpad model does not seem solely responsible for the scratchpad model's 's improved performance.
C EXAMPLE FEW-SHOT PROMPT FOR SYNTHETIC PYTHON EXPERIMENTS
Below is an example of prompt for few-shot synthetic Python synthesis problems:
Consider the following Python function:
def f(v8):
vθ += 8
while v4 8: v4
vê
return va
output f(6)
What is the execution trace?
[BEGIN]
state:
line: def f(vē):
state: (*f": "ccallable_object f>*)
12

---

Under review as a conference paper at ICLR 2022
line: output
state: (*ve": 6)
line:
state: (*y8": 6)
line:
state: ("vo": 6, "v4":
line: while v4 > 8:
("ve": "v4":
line: v4 -
state: (*ve": 6, "v4";
line: v0 t=
state: ("ve": 12, "v4": 1)
line: while
state: (*ve": 12, "v4"; 1)
state: (*ve": 12, "v4":
line: ve
state: ("ve": 24, "v4":
line: while
8:
("ve": "v4":
line: return v
("f": "scallsble_obff"
"outout": 24)
[DONE]
Consider der the Following Python function:
def [(v0):
vê += 2
va 8
return
f(4)
execution
[BEGIN]
state: Q
line: def f(v8):
state: (" "scallable_ajjed f>")
line: output f(4)
state: ("v0": 4)
line: -=
state: ("ve":
line: v0 =
state: ("ve":
line: v8 -
state: ("ve": 6)
line: return
state: (*f": "<callable_object f>", "output": 8)
[DONE]
Consider the following Python function:
def f(v0):
while v8 8: vê A=
return
output f(4)
What is the execution trace?
[EEGIN]
state:
line: def f(v8):
<*t": "scallsble_objer (>))
line: output f(4)
state: ("vo": 4)
line: -
state: ("vo": 4)
line: =
state: (*ve": 4, "v8": 2)
line:
13

---

Under review as a conference paper at ICLR 2022
state: ("v8": "v8":
line: vê -
state: (*ve": 4, "v8":
line: vB A=
state: ("ve": 4, "v8"; 1}
line: while
8:
state: (*ve": 4, "v8": 1)
line:
state: (*ve": 4, "v8": 6)
line: ve
state: (*ve": 4, "v8":
line: while
8:
state: ("ve": "v8":
line: return v
(*f"; "<callable_ojjett "output"s
[DONE]
Consider the Following Python function:
def f(v8):
vê ==
ve
return
f(8)
execution
[BEGIN]
D INCORRECT OUTPUT FOR SYNTHETIC PYTHON PROBLEMS
Below is an example of the failure of the few-shot synthetic experiments discussed in Section 5.1 Given problem such as:
Consider the follewing Python Function:
def f(v8):
v0
va *= 1
return
output f(8)
What is the execution trace?
The model produces the following trace:
state: (*ve": 8)
line: def f(v0):
state: ("v8": 8, "F": "<Function at ex888FCIce=")
line:
state: (*v0": 18)
line: ==
state: (*ve": 28)
line: +=
state: ("v8": 20)
line: return vθ
(*f"; "<function at 0x009FC100>" "ve": 20)
Note that this trace is exactly correct, except for the last line: where the model predicted "ve": 20. the correct output is "output": 20. Because this type of error consistently occurs in the few-shot synthetic Python experiments, modified the evaluation script slightly to consider this output to be correct.
14

---

Under review as a conference paper at ICLR 2022
Addition: In-Distribution Accuracy
100
baseline
80
scratchpad
Accuracy (%)
scratchpad model
fine-tuned for
60
direct execution
40
20
0
107
10s Parameter Count
10
Figure 7: Long addition ablation results. Here, we comparing the baseline and scratchpad results to model that is first fine-tuned the scratchpad and then subsequently fine-tuned to perform direct execution (the baseline). The intermediate scratchpad training seem to not have any significant effect the overall performance, indicating that the extra training-time information seen by the scratchpad model does not seem solely responsible for the scratchpad model's performance.
15


Reviews:
[{"review_id": "cHFCmuF3nEU", "reviewer": "Reviewer_uxzZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths:\n\n1. The main scratchpad idea presented here is new and interesting, not only to people who care about executing programs with LMs but also to the language modeling community at large. If we can figure out how to make language models better understand python, that might lead us in a direction that will enable us to build LMs that can better understand natural language. Intermediate computations are not only a property of programming languages, but have lots of relevance to natural language as well, see for example the wide range of research on multi-hop question answering. \n2. I’m very happy to see language modeling research that improves results without actually changing the language model itself! I think this opens up a lot of possibilities that were not available before. With LMs growing in size, it is becoming less practical for researchers to train them from scratch for each project. I hope that this paper motivates the community to further explore research directions which don’t require model modifications at all. \n3. The ideas presented in this paper are simple and easy to reproduce. \n4. The paper is written in a very straightforward and comprehensible way. \n\n\n\nWeaknesses:\n1. Table 3: I’m guessing that you didn’t train the direct execution model on the following datasets:  MBPP-aug +single line, and MBPP-aug +CodeNet +single line, because you saw that MBPP-aug didn’t help? But why are there no results for the direct execution model trained on MBPP + CodeNet or MBPP + single line? If these datasets help the scratchpad model so much, it would be very relevant and interesting to see how much they help the baseline. \n2. This isn’t a major issue but it seems like in the MBPP dataset the authors had to prune more than 50% of the tasks since they were too long to fit entirely within one inference pass of the transformer model used. So the results are biased towards shorter programs. This is totally fine but I felt like the authors should explain that a bit more in the paper and specify exactly how long the context window of their model is so the reader understands how long these programs are. \n\n\nOther notes/questions:\n1. “we aim to reduce the propagation and compounding of small errors, because states are quantized to token embeddings”\nIt's not clear to me that quantizing would help reduce the compounding of errors. What happens if you output a wrong token? Isn’t that even worse than having a small “error” in some continuous representation space? \n2. Table 2 has an asterisk at the bottom left which is not explained in its caption. It would be helpful if you would add that note about the accuracy criterion to that table’s caption as well (if that’s what you mean by that asterisk). \n3. There aren’t many details given about the model used. For example, what position embedding method did you use? I wonder if using a relative position method would have improved the model’s OOD abilities on the addition task. \n", "summary_of_the_paper": "Transformers LMs are getting better and better at generating programs given a description, but do they actually “understand” what they’re generating? Can transformers execute code? The current state of the art in this domain is weak, and the authors show an incredibly simple method here that leads to big performance gains. Instead of modifying the model or the training data, the authors show that by simply training the transformer to output the result of intermediate computation steps, its performance when executing code significantly goes up. \nThe authors show strong results on addition and a few other artificial tasks, before moving on to a codebase of python programs. Their scratchpad method improves over the baseline and benefits from a simple data augmentation method that they introduce. \n", "summary_of_the_review": "This paper presents a new, simple idea, is well written, and has strong empirical results. The research methodology here, of improving LM performance without actually changing the architecture, is super interesting, and I hope that this paper leads to more work that pushes the state of the art forward without modifying the model. The paper presents results on artificial tasks and python code but I believe that conclusions from it are relevant to the entire natural language modeling field. I am strongly in favor of accepting this work!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "YBzUjMIqbqB", "reviewer": "Reviewer_WdDB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Pros: \n* Training models using a scratchpad provides significant empirical improvements in learning to execute\n\n## Cons: \n* The explanation of the contribution of the scratchpad seems incorrect to me. I believe that the explanations that the authors present as to why training with scratchpad supervision helps are only partial, and the actual explanation is different (see below). No ablation study was conducted to separate different sources of contribution and explanations.\n* The motivation for the task is unclear to me. What use do we have in a far-from-perfect learned python interpreter? Can improvements in this task generalize to other tasks? (see below)\n* A direct cost of using a scratchpad is that the output sequence is much longer, making some of the examples in the dataset not fit within the Transformer's context window. At first, I didn't think that this is a practical limitation, but if I understand correctly, this leaves only 212 of the 500 test tasks? This limits the evaluation mostly to short programs and poses scaling limitations on the approach itself.\n\n# Why scratchpads help\nThe paper provides two possible explanations as to why scratchpads help models perform better, but in my opinion, the paper ignores the main factor.\n\nStarting from the Abstract, the paper lists the challenges in learning to execute programs and arithmetic calculations:\n\n## 1. unbounded computation?\nIn previous approaches:\n>\"The model is asked to perform these tasks in one forward pass. Given a fixed number of layers and a fixed amount of computation time, the model cannot adapt the amount of compute spent on a problem to its difficulty before producing an output\"\n\nIn contrast, scratchpads:\n> \"Allow the model to produce an arbitrary sequence of intermediate tokens, which we call a scratchpad, before producing the final answer\".\n> ... \"The model has adaptive computation time, that is, it can now process the information for as long as needed\"\n\nThis gives the impression that the ability to emit tokens that are not included in the final prediction, using a scratchpad, allows unbounded computation. \nHowever, although training with scratchpads *allows* unbounded computation, the models do not perform unbounded computation in practice.\n\nIt is theoretically true that the model has an \"adaptive computation time\" and \"can process the information as long as needed\", because the model can theoretically do that at test time. But this is also not-true, because the output length is about the same length as the \"clean\" output. The model is not _trained_ to process the information for as long as needed, and it thus is not likely to do that at test time.  As shown in Figure 1, even \"for\" loops are not unrolled at training time, but instead, only read once. That is, the total output length is in the order of the original target length, and is not expected to be longer at test time.\n\n## 2. The ability to write to and read from the scratchpad?\n\nThe authors hint that the **main** contributing factor to the improved empirical results of using a scratchpad is allowing to emit intermediate computations and reading from them later. \n\nThe Conclusion section concludes that:\n> \"allowing models to read from and write to a simple scratchpad can improve their performance on algorithmic tasks\".\n\nThis may be one contributing factor and an interesting idea, but the paper did not convince me that it is the main contributing factor.\nTo empirically prove that this is the most important factor, I would expect experiments that ablate (a) the ability to write to a scratchpad, (b) the ability to perform longer computations, and (c) the additional supervision that is provided at training time.\n\n## The most important factor\nWhile each of (1) (unbounded computation) and (2) (the ability to write to the scratchpad) is a potentially useful ability, I believe that none of them is the main factor that contributes to the improved accuracy of the models that were trained with a scratchpad. \nThe paper ignores a third factor: the additional supervision signal. The models with scratchpads are trained with the full program execution trace, while the baselines are not. Is it a fair comparison? I am not sure that comparing models that were trained using only the \"static\" source code and models that were trained with additional \"dynamic\" execution trace supervision is a fair comparison. \n\nThe explanation and presentation of why scratchpads help seem incorrect to me. The authors claim that it's the unbounded computation and the ability to write to a scratchpad, while ignoring the additional supervision. No ablation experiments in the paper have attempted to tease apart these factors and understand the most important sources of contribution.\n\nIs the dependence on this additional supervision information realistic? If this additional supervision source (the step-by-step execution trace) was a new source of supervision that could be utilized in other models of programming languages, then maybe it was useful to use it at training time (if the paper explained it as such!). However, I don't see how this is a source of supervision that can be generalized to other tasks, because it is specific to this task of learning to execute short, standalone, functions. \nIn most scenarios and tasks, a model cannot execute long programs, partial programs, incomplete programs, programs without test cases, or programs that require complex objects as inputs.\n\n# Unclear task motivation\nThe motivation of why to learn to execute python programs and arithmetic addition is unclear to me. While it may be intellectually pleasing to experiment with tasks that are too difficult for neural networks to perform and try to see what components are needed to make the neural networks be more and more accurate, I don't see how this transfers to anything practical. \n\nAt best, the model just learns to mimic the python interpreter (or the \"addition\" algorithm). \nWhat benefit do we have in having a neural network that simulates (a very specific kind of short functions on) the python interpreter, which we already have and can execute programs perfectly? What use do we have in a model that has learned to partially simulate the python \ninterpreter? if we have a python interpreter to provide the execution trace, why do we need a model to learn to execute?\n\nAs the authors write in Section 5.2.2:\n> \"we have augmented the dataset using a combination of tools already available to us, namely ... program execution via a Python interpreter\". \n\nThis is the point - if we consider the python interpreter as a tool that is already available to us, why do we need to learn it? Is this a proxy task to other tasks? Can improvements in this task generalize to other tasks?\n\n## Additional Questions:\n1. As shown in Figure 3, the difference between the scratchpad model and the baseline model starts to affect the performance only starting from sufficiently large models. In smaller models (<50M?), there seems to be no difference, even for the task of arithmetic addition. This is not discussed in the paper. Can the authors explain this phenomenon? I would expect that even a small model (and even other architectures such as LSTMs) would benefit a lot from the additional scratchpad supervision.\n\n2. \"direct execution prediction requires the model to correctly output the result of executing the entire function in a *single pass*\" (section 5, page 5). But then: \"we train models to predict an alternating sequence of 1) the ordered sequence of source code lines executed, and 2) the state of the local variables after each line is executed\". Isn't this also a *single pass*?\n\n3. I do not understand the message of the \"single-line programs\" discussed in Section 5. As shown in Table 3, further training on this additional dataset improves the results even more. But what is the message here? that training on more data improves accuracy? \n\n4. \"neural networks that **understand** code\" is an incorrect, confusing, and harmful terminology: \n\n>\"So language models can to some extend _write_ code, but do not seem to **_understand_** the code they write ...\"\n\n>\"Neural networks that **understand** programs could enable...\"\n\n> \"Such models may be a first step toward ... in order to build models that **_understand_** code\"\n\nThis terminology contributes to the hype over neural networks but confuses the audience that might be given the wrong impression and an imprecise understanding of neural networks and how they work.\n\n5. The paper states that:\n>\"Why do large language models struggle with algorithmic reasoning tasks? We suggest that this is at least partly due to a limitation of the Transformer architecture\"\n\nBut later, the paper does \"exploit existing Transformer architectures\" ... \"without modifying the underlying architecture\". So, do the authors argue that the Transformer architecture inherently limited or not?\n\n# Missing related work: \nThe recognition that providing step-by-step supervision improves execution prediction was demonstrated in some previous work as well. The following recent papers were not discussed nor compared to:\n* Veličković et al, \"Neural Execution of Graph Algorithms\", ICLR 2020\n* Veličković et al, \"Pointer Graph Networks\", NeurIPS 2020\n* Yan et al., \"Neural Execution Engines: Learning to Execute Subroutines\", NeurIPS 2020\n* Wang et al., \"Dynamic Neural Program Embedding for Program Repair\", ICLR 2018\n* Wang et al., \"Blended, Precise Semantic Program Embeddings\", PLDI 2020\n* Wang et al., \"Learning Semantic Program Embeddings with Graph Interval Neural Network”, OOPSLA 2020\n\nI agree that these papers did not use a scratchpad, but I was not convinced that the scratchpad itself is the most contributing factor in this work, and no ablation study showed that.\nI also agree that some of these address learning graph algorithms (and not python programs), but I would also expect a conceptual comparison and discussion.\n\n", "summary_of_the_paper": "This paper addresses the \"learning to execute\" task, of predicting the output of a given python program or arithmetic calculation. The main novelty is to train Transformers with \"scratchpads\": At training time, the model is provided with the intermediate states of all variables after executing every statement; at test time, the model predicts these intermediate states but is allowed to mark them as part of its \"scratchpad\". These intermediate states are not included in the final prediction, but only serve as a temporary output buffer.\n", "summary_of_the_review": "Although training a model using a scratchpad provides significant empirical improvements in learning to execute, and I appreciate the extensive empirical evaluation conducted by the authors, I believe that the explanation of why scratchpad helps is incorrect and confusing the readers. Further, the motivation of this task and settings of learning the python interpreter given a python interpreter at training time, is unclear to me. \n\nThus, I recommend rejection at this time, but I am open to changing my mind if convinced that the main weaknesses listed above are mistaken.  \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LQoU0EnSy3L", "reviewer": "Reviewer_PHbv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The idea is straightforward and leads to clear improvement in the empirical results.\n- The work serves as a nice complement to others which outsource the algorithmic reasoning to outside the machine learning model (e.g. execution-guided program synthesis), and may catalyze further research on the right balance between the work done by the ML model, and by program interpreters or other discrete reasoning engines.\n\nWeaknesses\n- For an entirely empirical paper, the tasks considered are not directly useful to solve with a learned model, since there already exist simple and straightforward ways to perform addition, polynomial evaluation, and Python evaluation with computers. It would be nice to see improvements on a more \"useful\" task.\n- There could be more systematic analyses of the settings where the idea works well and where it does not, beyond the ones already in the paper. For example, we can vary the size of the underlying model, the amount of training data, complexity of the task, etc.\n\nQuestions\n- For the few-shot setting, it was unclear exactly how the few-shot examples were chosen. Were they chosen separately for each test example (e.g. to include the training examples most similar to the test example)? If so, what was the method? If not, what was the methodology used to select the fixed set of examples? How robust are the results to changing the set used?\n- The CodeNet paragraph says: \"We additionally improved our tracing technique to allow tracing programs with errors; when an error is reached, the error message is added to the end of the trace text and tracing is stopped\". Which columns in Table 3 was this improvement applied to? Do we know how much this affects the results, independent of the extra data from CodeNet?\n", "summary_of_the_paper": "The paper evaluates the ability of large pre-trained language models to perform addition, polynomial evaluation, and execution of Python programs, with few-shot in-context learning or with fine-tuning. Instead of having the model directly predict the output of the task, the authors propose to have the model generate all of the intermediate steps involved: for addition, the results of adding every column and the carry; for polynomial evaluation, the value for each term; for Python evaluation, the value of all variables after each line. The authors demonstrate improvements compared to direct execution for all of these settings.\n\nThe authors propose several reasons that would enable such an improvement:\n- Adaptive computation time, as the model runs longer for more complicated tasks\n- Intermediate state can be stored in the past tokens rather than only in the activations\n- Reduced propagation of errors as states are quantized to specific tokens\n- Debugging and interpretability\n", "summary_of_the_review": "I think the paper presents an elegant idea with extensive experiments and would provide useful insights to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1jZGqT4-eQP", "reviewer": "Reviewer_UqLx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Pros:*\n\n- Overall the paper is easy to follow and the idea of augmenting the output with scratchpads is simple and interesting and is shown to perform better than outputting the values of direct execution of the input. \n\n- The scratchpad method shows promises to benefit better from synthetic data augmentation, than direct execution.  \n\n\n*Concerns & Areas of enhancement:*\n\n- *Limitations of the Fine-tuning scenario:* Majority of the results shown in the paper are on the finetuning setup not the few-shot ICL one. The power of large language models is that they are general in context learners.  Finetuning a large LM of that size will completely destroy this capacity. After all, there's no need of having a 100B parameter model that just adds numbers, solves polynomial equations, or Execute python code of fixed length from an application-wise. If authors see that this finetuning is not as destructive to the model, extra evaluation on language modeling or general zero-shot/few-shot in context learning should have been reported. \n\n\n- *Comparison against Meaningful baselines* If we accept that the focus of the study here is to learn neural networks that can ONLY perform complex multi-step computations and \"scratchpads\" are a good method for this. In this case, the authors should have compared meaningful baselines for compositional generalization [1,2,3,4] and aligned with those lines of work. \n\n  * 1- https://arxiv.org/pdf/1711.00350.pdf\n  * 2- https://arxiv.org/pdf/2109.12243v1.pdf \n  * 3- https://proceedings.neurips.cc//paper/2020/file/83adc9225e4deb67d7ce42d58fe5157c-Paper.pdf \n  * 4- https://arxiv.org/pdf/2003.05562.pdf \n\n\n- *Reproducibility & Transparency in reporting methods and experiments*\n\nThe paper lacks lots of reproducibility details on the used models (their pretraining method), finetuning details, few shot examples selections. There's no way to verify the correctness of the result in the paper or to reproduce any of the results if the paper is accepted.  \nTo complete this authors don't provide any reproducibility statement. I advise the authors to read the reproducibility section in the ICLR2022 authors guide https://iclr.cc/Conferences/2022/AuthorGuide\n\n", "summary_of_the_paper": "This paper proposes an output augmentation method for enhancing the capacity of Transformers language models in performing multi-step symbolic computations such as adding integers or executing programs. \nThe idea in brief is instead of finetuning/ICL the model to directly output the result of the execution of the program, the expected output becomes a \"scratchpad\" of the execution steps terminated by the execution prediction. \nThe intuition here is enforcing the output signal has the following advantages 1) allowing adaptive computations time with respect to the input (i.e. the length of the generated scratchpad increases with more complicated inputs) 2) Acting as an intermediate memory 3) Allowing for interpretability. \n\nAuthors evaluate the proposed through finetuning or In context Learning of Decoder only transformers (2M->100B params), on three tasks: \n- Long integer Addition (finetuning only)\n- Polynomial evaluation (Finetuning and ICL)\n- Python program execution both on synthetic and real programs (Finetuning only)\n\nOverall, the results show that:\n- Transformers trained to output scratchpad in addition to the final prediction, perform better than direct prediction only. \n- They could benefit better from synthetic data generation and data augmentation.   \n", "summary_of_the_review": "Overall the scratchpad idea sounds simple and interesting, however, the current evaluation in the fine-tuning setup has it's practical limitations (see above). I advise the authors to either position this paper in one of the two directions discussed above. Overall the reproducibility and transparency in experiment reporting would benefit from major enhancements. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main remaining criticism of the paper is reproducibility, i.e., "it is nearly impossible to verify the correctness of the result in the paper or to reproduce any of these results" (AC). We generally agree with this statement. While the authors do provide some details in the paper, reviewers, AC, SAC, and PCs agree that this is insufficient. Further points that came up in our discussions were the simplicity of the baselines and the choice of testing to demonstrate that the approach really works. Our impression is that the work lacks a rigorous experimental evaluation. These considerations led to the decision in the end.
Decision: Reject