Venue: ICLR 2022 Conference

Reviews:

final_score: rating: null
review_content: Dear authors,

The public discussion period is about to end and the authors did not respond to any of the reviews.

Although my initial score is low, I did hope to discuss the paper with you during this discussion period and give the authors the opportunity to convince me that I was wrong in my initial assessment. 






review_title: Discussion with authors?

final_score: rating: 3: reject, not good enough
review_content: 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. 
The 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. 
The 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. 

Authors evaluate the proposed through finetuning or In context Learning of Decoder only transformers (2M->100B params), on three tasks: 
- Long integer Addition (finetuning only)
- Polynomial evaluation (Finetuning and ICL)
- Python program execution both on synthetic and real programs (Finetuning only)

Overall, the results show that:
- Transformers trained to output scratchpad in addition to the final prediction, perform better than direct prediction only. 
- They could benefit better from synthetic data generation and data augmentation.   

main_review: *Pros:*

- 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. 

- The scratchpad method shows promises to benefit better from synthetic data augmentation, than direct execution.  


*Concerns & Areas of enhancement:*

- *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. 


- *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. 

  * 1- https://arxiv.org/pdf/1711.00350.pdf
  * 2- https://arxiv.org/pdf/2109.12243v1.pdf 
  * 3- https://proceedings.neurips.cc//paper/2020/file/83adc9225e4deb67d7ce42d58fe5157c-Paper.pdf 
  * 4- https://arxiv.org/pdf/2003.05562.pdf 


- *Reproducibility & Transparency in reporting methods and experiments*

The 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.  
To 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


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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

The authors propose several reasons that would enable such an improvement:
- Adaptive computation time, as the model runs longer for more complicated tasks
- Intermediate state can be stored in the past tokens rather than only in the activations
- Reduced propagation of errors as states are quantized to specific tokens
- Debugging and interpretability

main_review: Strengths
- The idea is straightforward and leads to clear improvement in the empirical results.
- 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.

Weaknesses
- 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.
- 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.

Questions
- 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?
- 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?

summary_of_the_review: I think the paper presents an elegant idea with extensive experiments and would provide useful insights to the community.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
The 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. 

main_review: 
Strengths:

1. 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. 
2. 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. 
3. The ideas presented in this paper are simple and easy to reproduce. 
4. The paper is written in a very straightforward and comprehensible way. 



Weaknesses:
1. 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. 
2. 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. 


Other notes/questions:
1. “we aim to reduce the propagation and compounding of small errors, because states are quantized to token embeddings”
It'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? 
2. 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). 
3. 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. 

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!
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

main_review: ## Pros: 
* Training models using a scratchpad provides significant empirical improvements in learning to execute

## Cons: 
* 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.
* 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)
* 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.

# Why scratchpads help
The paper provides two possible explanations as to why scratchpads help models perform better, but in my opinion, the paper ignores the main factor.

Starting from the Abstract, the paper lists the challenges in learning to execute programs and arithmetic calculations:

## 1. unbounded computation?
In previous approaches:
>"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"

In contrast, scratchpads:
> "Allow the model to produce an arbitrary sequence of intermediate tokens, which we call a scratchpad, before producing the final answer".
> ... "The model has adaptive computation time, that is, it can now process the information for as long as needed"

This gives the impression that the ability to emit tokens that are not included in the final prediction, using a scratchpad, allows unbounded computation. 
However, although training with scratchpads *allows* unbounded computation, the models do not perform unbounded computation in practice.

It 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.

## 2. The ability to write to and read from the scratchpad?

The 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. 

The Conclusion section concludes that:
> "allowing models to read from and write to a simple scratchpad can improve their performance on algorithmic tasks".

This may be one contributing factor and an interesting idea, but the paper did not convince me that it is the main contributing factor.
To 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.

## The most important factor
While 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. 
The 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. 

The 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.

Is 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. 
In 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.

# Unclear task motivation
The 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. 

At best, the model just learns to mimic the python interpreter (or the "addition" algorithm). 
What 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 
interpreter? if we have a python interpreter to provide the execution trace, why do we need a model to learn to execute?

As the authors write in Section 5.2.2:
> "we have augmented the dataset using a combination of tools already available to us, namely ... program execution via a Python interpreter". 

This 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?

## Additional Questions:
1. 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.

2. "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*?

3. 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? 

4. "neural networks that **understand** code" is an incorrect, confusing, and harmful terminology: 

>"So language models can to some extend _write_ code, but do not seem to **_understand_** the code they write ..."

>"Neural networks that **understand** programs could enable..."

> "Such models may be a first step toward ... in order to build models that **_understand_** code"

This 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.

5. The paper states that:
>"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"

But 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?

# Missing related work: 
The 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:
* Veličković et al, "Neural Execution of Graph Algorithms", ICLR 2020
* Veličković et al, "Pointer Graph Networks", NeurIPS 2020
* Yan et al., "Neural Execution Engines: Learning to Execute Subroutines", NeurIPS 2020
* Wang et al., "Dynamic Neural Program Embedding for Program Repair", ICLR 2018
* Wang et al., "Blended, Precise Semantic Program Embeddings", PLDI 2020
* Wang et al., "Learning Semantic Program Embeddings with Graph Interval Neural Network”, OOPSLA 2020

I 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.
I also agree that some of these address learning graph algorithms (and not python programs), but I would also expect a conceptual comparison and discussion.


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. 

Thus, I recommend rejection at this time, but I am open to changing my mind if convinced that the main weaknesses listed above are mistaken.
review_title: null

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