Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents ProTo (Program-Guided Transformer), a modified 
Transformer-based architecture that aims to learn a (fully neurally-parameterized)
 execution model for symbolic programs. The authors propose a parameterization scheme that encodes the program semantics (decomposed along minimal executable components of the symbolic program) and program syntax (using a transition mask defined based on the program tree); and describe multiple training regimes (varying from dense supervision based on ground truth or symbolic executions, to a fully RL-based distant supervision.) 
The authors present empirical evaluations on two domains -- visual question answering (GQA) and policy execution (2D Minecraft) with respect to other comparable neural architectures that leverage symbolic program traces. They find comparable performance with respect to the SOTA, and demonstrate improvements in generalization to longer and novel programs. 

main_review: *Strengths (soundness; theoretical grounding; empirical evaluation; significance and novelty; relevance to NeurIPS community)*:
- Application is interesting and of significant interest to the NeurIPS community. Domains used demonstrate promise for future work. Learning executors that can handle formal programming languages is an area of of interest with important potential applications for generalization and interpretability, and the authors demonstrate their model on two domains -- VQA and policy learning -- that highlight this. Further, while the authors focus on learning execution engines for formal program representations, it seems possible and of interest to test the generalizability of the same architecture (perhaps pre-trained on programs as a form of ‘synthetic data’ to natural language processing -- and indeed, the authors do approach this in their GQA approach (which uses a Seq2Seq model to perform the initial transformation from natural language into the DSL used here.)

The DSLs used are fairly complex -- the planning DSL has looping constructs.

- Architecture proposed is reasonably novel and lays the groundwork for future work. The proposed architecture is based on Transformers -- it uses attention blocks as its primary neural architectural component -- but takes interesting, reasonable seeming, (and I believe, novel) approaches to leverage the inherent semantic and syntactic structure of the program representation. This seems promising as an avenue for future work using similar architectures, and I think if the authors wished they could attempt to describe the most general instantiation of this architecture while signposting particular choices made in their concrete model that could be modified in the future (e.g the authors choose routines as minimal executable units, presumably for supervision purposes. But it seems like changes could be made so that `Filter(girl)` could be decomposed further for greater compositionality in the future.)

- Empirical evaluations show comparable performance to other SOTA architectures (like meta-module networks), and generalization experiments show significant performance improvements. The results from human-specified programs are particularly interesting. The authors compare against a good range of strong baselines and ablations.

For the generalization experiments, it would be nice to see a continuous graph (rather than bucketing the programs into standard testing, longer programs, and complex programs, for instance, in Table 4) that really shows the fall-off in performance between length of training programs vs. generalization performance -- perhaps this would even more clearly highlight the contributions of this model. 

Similarly, the authors also present intriguing data using ‘unseen programs’ on the GQA dataset. I could personally use some clarification on how this worked -- was there additional ‘training’ at test time to learn to use the `verify` instances? Otherwise, how does the model know at all how to execute these primitives -- but it could be interesting and useful to see a similar continuous graph showing the fall-off in generalization performance as additional new primitives are introduced into the dataset, to really showcase compositionality or graceful robustness to new primitives. 

*Weaknesses (soundness; theoretical grounding; empirical evaluation; significance and novelty; relevance to NeurIPS community)*:
- Discussion of generalization performance is promising but could be more rigorous, especially with respect to symbolic / formal baselines when they exist, or mixed neuro-symbolic methods. The authors mention several times that their approach -- learning the program executor entirely -- is based on prior work showing that learned executors often outperform symbolic ones.
This certainly may be the case on many domains of interest, and the authors convincingly show strong improvements over a model (NS-VQA) that uses a symbolic execution model on visual question answering, a domain that does seem to require some learnable component and that seems well-suited for this application.

On the second domain (Minecraft), however, we do in fact have a fully symbolic model -- the symbolic planner used to construct programs (and that provides the dense supervision.) In the strengths section above, I laid out some figures / generalization experiments that would help give a clearer picture of how this model performs relative to a fully-symbolic executor on two axes that seem most important to emulate: (a) modularity compositionality with respect to new program components introduced into the DSL; and (b) generalization to long programs and programs of arbitrary length.
Especially because the authors strongly suggest that a core goal of this model is to replace or outperform symbolic models on important future domains, I think it is important to have a clear picture of how well it can perform on fully symbolic tasks relative to symbolic baselines. 
 
- Empirical performance in comparison to SOTA is comparable and competitive, but in many cases, except on generalization or complex programs, it is not very large. It suggests that a harder dataset would be necessary to really showcase the performance of this model, and on GQA, all models still seem to fall well short of human performance.
- (More minor): discussion of failure cases, especially wrt longer programs and control flow. Discussion of intermediate execution states and disentanglement. The GQA dataset does not have control flow. Loops and other more complex, characteristically programmatic structures are one area where I would have expected to see degraded generalization performance with respect to a symbolic model (e.g. performing more inaccurately with greater numbers of loops). The authors show results specifically on complex programs (with more than four If/While tokens) which are promising -- but again, I see this as an area that could have specifically probed where this model successfully learns to emulate the desired flow and when it may not. Perhaps some metric other than ground-truth accuracy -- such as an analysis of the intermediate execution state accuracy -- would also serve this purpose. 
- Use of dense supervision. This is discussed in the limitations section (Appendix E), but raises questions about the scalability of this model with respect to its ultimate end goal. However, it could be interesting to see other ‘Partial Superivsion’ training regimes other than the one in the paper (knowing the final execution result of the whole program) -- what about supervision on some program components but not others (suggested by the GQA training regime -- which starts with a pre-trained object detector)? This could be an interesting area for testing compositionality and robustness to new program components as well.


limitations_and_societal_impact: The authors provide a reasonable discussion of limitations and broader impact in the appendix (E and F).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new model for learning to execute programs on program-guided tasks. The model is based on transformer and uses cross-attention and self-attention mechanisms. It takes as inputs both the program structure (control flow information) and program semantics (through token embeddings), as well as task specifications. The model is evaluated on a visual reasoning benchmark and a 2D Minecraft RL benchmark. Experiments show that the proposed model achieves better performance than previous ad-hoc approaches for learning to execute programs in these domains. 
main_review: This paper proposes a general approach for learning to execute programs on program-guided tasks. Using programs to guide learning is a promising direction and has received increasing attention, so the paper is targeting an important problem. The paper is well-written and easy to follow. The experimental evaluation is good, covering two distinct domains including visual reasoning and RL, and showed consistent improvement over prior ad-hoc approaches designed for each domain. Overall, this is a well-written paper.

Questions:

- What are the reasons for the performance improvement by ProTo over the prior ad-hoc approaches? Is it utilizing more information from the program, or just due to the better modeling power of a large transformer model? It would be helpful to see some analysis on the difference between ProTo and prior approaches to help understand why ProTo is better. 

- There are some prior work that proposes general techniques for learning to execute programs, which is most closely related to the theme of the paper: Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks, David Bieber et.al. 2020. 
It would be good if the authors can compare with these approaches.

- ProTo model feeds the last result matrix into the current step, therefore inducing a recurrent structure. How is this treated during training? Since for RL tasks with long horizon and only reward signal, back-propagating through the whole episode seems to be a high computation burden.


limitations_and_societal_impact: The limitations and societal impact is discussed in the Appendix.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes Program-Guided Transformer (ProTo) for program execution tasks. Specifically, instead of simply encoding the program as a token sequence, they disentangle the program representation into a semantic representation and a structural representation, and the structural representation takes the program control flows into accounts. They modify the attention mechanisms of the vanilla Transformer architecture to encode the disentangled program representation. They evaluate their approach on two tasks: (1) program-guided visual question answering on GQA; and (2) program-guided policy learning task proposed in [64]. They show that ProTo outperforms other baselines.
main_review: Learning to execute programs is an important topic. In particular, executing programs on visual inputs and understanding routines in programs are challenging problems. For both GQA and policy learning tasks, the authors present good results and comparisons to strong baselines. The proposed Transformer architecture properly utilizes the program structure. Although the programs evaluated in this work are in restricted domain-specific languages, the ProTo architecture might be extended to more complicated programming languages.

I have a couple of questions about the approach design and experiments:

1. From Algorithms 1 and 2, the pointer update depends on the execution results. According to the equation for computing the output o, I suppose the execution output vector should represent a probability distribution over all possible execution results. When you train or evaluate the model, do you take the argmax to determine the execution output for the pointer update, e.g., selecting T/F for conditional statements and selecting actions for executing routines? If this is the case, is the model hard to train since wrong intermediate execution results can mislead the execution of all remaining program statements?

2. Could you present the distribution of program lengths in your experiments? What is the largest program length ProTo can handle? From the attention computation and the structural representation, the transition mask and some intermediate results are |P|x|P|-dimensional, thus the model might not scale to larger programs without modification.

3. A general suggestion on related work and baseline discussion: I feel that the main point of this work is about neural-symbolic reasoning and program understanding, because the modification of the Transformer architecture itself is not extremely novel. Therefore, in the main body of the paper, the authors can include more discussion of existing work on neural-symbolic learning, and the key differences between this work and baseline models that lead to better performance.

4. I am confused about the results of Unseen Programs in GQA experiments. For removing "verify"-type problems, do you mean that you only remove them for training the ProTo model, or do you also remove them for training the program synthesis model? If you completely remove all these problems for training, I don't know why the model can generalize. Specifically, how should the model understand these new functions if they never appear in training?

5. What is the point of collecting additional human-written programs for evaluation? Why not simply evaluate the model performance on ground truth programs in GQA? Could you provide the statistics of the human program dataset you collect, and explain what are the key differences between these new programs and those in GQA?

6. In the policy learning experiment, it says that "Transformer and TreeRNN encode the input program in a token by token manner". However, I suppose the TreeRNN model should encode the program as a tree. Could you explain more about how you use TreeRNN here?

7. In experiments of Longer Programs and Complex Programs, do you only train the models on shorter programs with fewer control flow constructs, or do you still train on programs of all different complexities, but present the test results on harder programs? I wonder whether these results show the generalization of models to programs that are more complex than training samples, or they are more about breakdown results varying the program complexities.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper explores how learning agents can follow program guidance to solve visual reasoning and policy learning tasks. While most prior works are only designed to address one of the two tasks, this paper aims to propose a unified framework that can tackle both two problems. To this end, the paper proposes a Transformer-based framework (ProTo) that learns to interpret and execute programs on observed specifications by learning to execute a program in a latent space with cross attention and masked attention mechanisms. The experiments on the visual reasoning task (GQA dataset) show that ProTo outperforms baselines using different learning signals such as question-answer pairs, scene graphs, and programs. The experiments on the program-guided policy learning in a 2D-Minecraft environment show that ProTo outperforms baselines and generalizes better to long and complex programs. I believe this work studies a promising research direction and proposes a framework that can address program-guided tasks in two domains. Therefore, I am leaning toward accepting this paper yet still have some concerns (see below) which I hope to be addressed in the rebuttal.
main_review: ## Paper strengths and contributions
**Motivation**
- The motivation for using programs as a structured, clean and formal representation to guide learning agents for task-solving is convincing.

**Novelty and technical contributions**
- To the best of my knowledge, the idea of unifying two program-guided task domains, including visual reasoning and policy learning, is novel.
- The idea of separately leveraging the program semantics and the explicit structure of the given program is convincing, and this paper proposes a way to implement this idea.
- Treating routines (sub-tasks in programs) as objects and leverages attention mechanisms to model interactions among routines and specifications using Transformer seems effective.
- Execute programs in a learned latent space for strong representation ability seems to contribute to the performance gain and generalization capability.
- The proposed framework can be trained using different levels of supervisions, including dense execution traces, a goal specification with distance measurement, and sparse rewards. This provides great flexibility.

**Clarity**
The writing of the introduction and the related work is clear. The problem and the proposed framework are well motivated and the contributions are explicitly stated.

**Experimental results**
- The presentation of the experimental results is clear.
- Visual reasoning task on the GQA dataset:
	- ProTo outperforms all baselines using learning signals including question-answer pairs, scene graphs, and programs on all the metrics.
	- The generalization experiments evaluate how well the models can generalize to the programs that are written by humans. The results show that ProTo outperforms the meta module network.
	- The low data regime experiment evaluates if how well the models can perform with only 10% of training data. The result shows that ProTo outperforms the meta module network.
- Policy learning task on the 2D-Minecraft domain:
	- ProTo learns more efficiently compared to the program-guided agent baseline and end-to-end learning models.
	- The experiments on longer and more complex programs show the better generalization performance of ProTo.

**Ablation study**
The ablation studies on the GQA dataset show that:
- Leveraging both the structure guidance and the semantic guidance is the key to the superior performance of ProTo.
- Utilizing a Transformer to encode inputs is better than using a graph neural network.

**Reproducibility**
The code is provided, which helps understand the details of the proposed framework.

## Paper weaknesses & questions

**Clarity: method section**
The writing of the method section is unclear and is not easy to follow. I have read it three times and still am not sure I correctly understand what modules are learned to do what, what input/output representations they use, how they are used for tasks from two domains. With my partial understanding of the proposed method, it is not easy for me to judge it. I believe a significant revision of the method section is required. 

**Walk-through example or flow chart**
Together with the point mentioned above, I believe it would be better to either provide a walk-through example or a flow chart that explicitly shows the learning modules and the input/output representations. It would be even better if walk-through examples from both domains are shown. While Figure 2 is supposed to serve this purpose, it is not still clear to me.

**Table 2 bottom rows**
I do not know how to interpret the bottom two rows of Table 2. Do the numbers indicate the performance of NS-VQA and MMN with partial supervision? If this is the case, I suggest the authors move the midrule a row higher so that three models (ProTo, NS-VQA, and MMN) learning from partial supervision and put them together for comparison. If not, the authors should probably provide a better description at the end of Section 5.1.

**Unseen programs**
I do not understand the unseen program generalization experiment on the GQA dataset. Does it mean that the model has never seen verify type tokens during training and can still work when tested on a program with such tokens without further training? Also, why are the verify type of instances chosen not others? It would be better if the authors offer intuitions for this.

**External memory**
While the authors believe that it would be better if a model does not leverage external memory for program-guided tasks for more efficient training, 
I actually believe incorporating external memories would allow the framework to be applied to a wider scope of program-guided applications. 

**Human-written programs and model-synthesized/GQA programs**
The generalization experiment evaluates how well ProTo and MMN can generalize to human-written programs, which are supposed to be different from model-synthesized programs and the programs in the GQA dataset. However, without some examples of all types of programs (human-written programs, model-synthesized programs, and GQA programs), it is not easy to judge if the distribution gap exists or how large the gap is, making it even harder to judge the generalization ability of ProTo and MMN.

**Missing related works**
While the related work section is fairly sufficient, including the following works would make it more comprehensive:
- Neural Scene De-rendering
- Neural Program Synthesis from Diverse Demonstration Videos
- Learning to Describe Scenes with Programs
- Learning to Infer and Execute 3D Shape Programs

**Minor issues**
- duplicated citations: [57] & [58]
- L155: Note "that"
- Many other grammar errors

## Other metrics

### Relevance and significance
- Reasonable contribution to a minor problem

### Novelty
- One idea that surprised me by its originality, solid contributions otherwise

### Technical quality
- Technically strong, highly general results, advanced techniques

### Experimental evaluation
- Solid, informative evaluation w.r.t all 5 criteria

### Clarity
- This paper is difficult to understand in places because of typos, lack of organization, or other flaws. The paper would need significant/major improvement in writing.
limitations_and_societal_impact: Described in the main review section.
review_title: null

Meta-review: All reviewers appreciated the novel approach for learning to execute symbolic programs using both program syntax and semantics. Adding additional experimental evaluation and comparisons to IPA-GNN and symbolic planner for Minecraft was also greatly appreciated. It would be great to incorporate the feedback, and the experimental and architectural clarifications from the reviews and author responses in the final version.
Decision: Accept (Poster)