# ProTo: Program-Guided Transformer
for Program-Guided Tasks

Zelin Zhao111Work was done when Zelin was a visiting student at Gatech.
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
Karan Samel
Georgia Institute of Technology
<EMAIL_ADDRESS>
Binghong Chen
Georgia Institute of Technology
<EMAIL_ADDRESS>
Le Song
Biomap and MBZUAI
<EMAIL_ADDRESS>

###### Abstract

Programs, consisting of semantic and structural information, play an important
role in the communication between humans and agents. Towards learning general
program executors to unify perception, reasoning, and decision making, we
formulate program-guided tasks which require learning to execute a given
program on the observed task specification. Furthermore, we propose Program-
Guided Transformer (ProTo), which integrates both semantic and structural
guidance of a program by leveraging cross-attention and masked self-attention
to pass messages between the specification and routines in the program. ProTo
executes a program in a learned latent space and enjoys stronger
representation ability than previous neural-symbolic approaches. We
demonstrate that ProTo significantly outperforms the previous state-of-the-art
methods on GQA visual reasoning and 2D Minecraft policy learning datasets.
Additionally, ProTo demonstrates better generalization to unseen, complex, and
human-written programs.

##  1 Introduction

Programs are the natural interface for the communication between machines and
humans [11]. In comparison to instructing machines via demonstrations [41, 52,
71, 6] or via natural language [14, 32, 3], guiding agents by programs has
multiple benefits. First, programs are explicit and much cleaner than other
instructions such as languages [79]. Second, programs are structured with
loops and branches [1] so they can express complex reasoning processes [95].
Finally, programs are compositional, promoting the generalization and
scalability of neural models [15, 64, 20]. However, while program synthesis
and program induction have been deeply explored [12, 17, 18, 22, 39, 49], very
few works focuses on learning to follow program guidance [79, 70].
Furthermore, previous work designs ad-hoc program executors for different
functions in different tasks [79, 29, 23], which hinders the generalization
and scalability of developed models.

To pursue general program executors to unify perception, reasoning, and
decision making, we formulate program-guided tasks, which require the agent to
follow the given program to perform tasks conditioned on task specifications.
The programs may come from a program synthesis model [95] or be written by
human [79]. Two exemplar tasks are shown in Figure 1. Program-guided tasks are
challenging because the agent needs to jointly follow the complex structure of
the program [1], perceive the specification, and ground the program semantics
on the specification [40].

Inspired by the recent significant advance of transformers in diverse domains
[24, 25, 59], we present the Program-guided Transformer (ProTo) for general
program-guided tasks. ProTo combines the strong representation ability of
transformers with symbolic program control flow. We propose to separately
leverage the program semantics and the explicit structure of the given program
via efficient attention mechanisms. ProTo enjoys strong representation ability
by executing the program in a learned latent space. In addition, ProTo can
either learn from reward signals [64, 79] or from dense execution supervision
[15].

We evaluate ProTo on two tasks, program-guided visual reasoning and program-
guided policy learning (corresponding to Figure 1 left and Figure 1 right).
The former task requires the model to learn to reason over a given image
following program guidance. We experiment on the GQA dataset [47] where the
programs are translated from natural language questions via a trained program
synthesis model. The evaluation on the public test server shows that we
outperform the previous state-of-the-art program-based method by 4.31% in
terms of accuracy. Our generalization experiments show that ProTo is capable
of following human program guidance. The latter task asks the agent to learn a
multi-task policy to interact with the environment according to the program.
We experiment on a 2D Minecraft environment [79] where the programs are
randomly sampled from the domain-specific language (DSL). We find that ProTo
has a stronger ability to scale to long and complex programs than previous
methods. ProTo significantly outperforms the vanilla transformer [85] which
does not explicitly leverage the structural guidance of the program. We will
release the code and pre-trained models after publishing.

In summary, our contributions are threefold. First, we formulate and highlight
program-guided tasks, which are generalized from program-guided visual
reasoning [95, 64] and program-guided policy learning [79]. Second, we propose
the program-guided transformer for program-guided tasks. Third, we conduct
extensive experiments on two domains and show promising results towards
solving program-guided tasks.

##  2 Related Work

Figure 1: Illustration of two exemplar program-guided tasks. The first task is
program-guided visual reasoning [47], where the model needs to learn to
execute a visual program on the specification (image) to get a predicted
answer. The second task is program-guided policy learning [79], where the
agent learns a policy to perform tasks based on the observed specification
following the program guidance.

##### Program Induction, Synthesis and Interpretation

Program induction methods learn an underlying input-output mapping from given
examples [54, 22, 50], and no programs are explicitly predicted. Differently,
program synthesis targets at predicting symbolic programs from task
specifications [23, 12, 18, 17, 31, 27, 91, 83, 16, 78, 58, 84]. However,
these approaches do not learn to execute programs. In the domain of digit and
string operation (adding, copying, sorting, etc.), Neural Program Interpreter
(NPI) [70, 92, 73] learn to compose lower-level programs to express higher-
level programs [37] while Neural Turing Machines [38, 55] use attentional
processes with external memory to infer simple algorithms. Recently, [79]
proposes to guide the agent in 2D Minecraft via programs. [65] detects
repeated entries in the image and uses programs to guide image manipulation.
They neither attempt to formulate general program-guided tasks nor propose a
unified model for different tasks.

##### Visual Reasoning

Visual reasoning requires joint modeling of natural language and vision. A
typical visual reasoning task is the visual question answering (VQA) [5].
Attention mechanisms have been widely used in the state-of-the-art VQA models
[60, 2, 72, 99, 46]. Neural module networks and the neural-symbolic approaches
[95, 64] propose to infer programs from natural languages and execute programs
on visual contents to get the answer. A large-scale dataset GQA [47], which
addresses the low diversity problem in the synthetic CLEVR dataset [48], is
proposed to evaluate the state-of-the-art visual reasoning models. Neural
state machine [45] is proposed by leveraging modular reasoning over a
probabilistic graph, which does not leverage the symbolic program. Our model
is similar to the concurrent work, meta module network [15] in that we use
shared parameters for different function executors. Nevertheless, we propose a
novel attention-based architecture and extend our model to the policy learning
domain.

##### Transformer

Transformer was firstly proposed in machine translation [85]. After that,
transformers demonstrate their power on many different domains, such as cross-
modal reasoning [81], large-scale unsupervised pretraining [24, 77, 94], and
multi-task representation learning [69, 66]. Recently, transformers appear to
be competitive models in many fundamental vision tasks, such as image
classification [25, 97], object detection [13] and segmentation [59, 33].
While we share the same belief that transformers are strong, unified, elegant
models for various deep learning tasks, we propose novel transformer
architecture for program-guided tasks. We discuss a few similar unpublished
works in Appendix A.

##### Policy Learning With Programs

Previous policy learning literature explored the benefits of programs in
different aspects. First, some pre-defined routines containing human prior
knowledge could help reinforcement learning, and planning [30, 67, 4, 98].
Second, programs enable interpretable and verifiable reinforcement learning
[87, 8]. Our approach follows a recent line of work that learns to interpret
program guidance [79, 4]. However, we adopt a novel, simple and uniform
architecture that demonstrates superior performance, thus conceptually related
to multitask reinforcement learning [82, 90] and hierarchical reinforcement
learning [7].

##  3 Program-guided Tasks

Unlike natural language that is flexible, complex, and noisy, programs are
structured, clean and formal [79]. Therefore, programs can serve as a powerful
intermediate representation for human-computer interactions [11]. Different
from previous work that learns to synthesis programs from data [95, 83, 27],
we study learning to execute given programs [79] based on three motivations.
First, instructing machines via explicit programs instead of noisy natural
languages enjoys better efficiency, and accuracy [79]. Second, learned program
executors have stronger representation ability than hard-coded ones [95, 15].
Third, we attempt to develop a unified model to integrate perception,
reasoning, and decision by learning to execute, which heads towards a core
direction in the neural-symbolic AI [36, 35].

A program-guided task is specified by a tuple
$(\mathcal{S},\Gamma,\mathcal{O},\mathcal{G})$ where $\mathcal{S}$ is the
space of specifications, $\Gamma$ denotes the program space formed by a
domain-specific language (DSL) for a task, $\mathcal{O}$ is the space for
execution results, and $\mathcal{G}$ is the goal function for the task. For
each instance of the program-guided task, a program $P\in\Gamma$ is given. An
executor $\mathcal{E}_{\Phi}$ is required by the task to execute the program
on the observed specification. Note that different from hard-coded non-
parametric executors used in some previous work [95, 23], the executor
$\mathcal{E}_{\Phi}$ is parametrized by $\Phi$. For convenience, we define a
routine to be the minimum execution unit of a program (e.g. Filter(girl) in
Figure 1 is a routine). We denote $P_{k}$ to be the $k$-th routine in $P$ and
$|P|$ to be the number of routines in $P$. According to the DSL, the program
should begin at the entrance routine and finish at one of the exiting routines
(e.g. Filter(girl) in Figure 1 is an entrance routine and Query_color() is an
exiting routine). At each execution step $\tau$, the executor executes the
current routine $P_{p}\in P$ on the specification $s^{(\tau)}\in\mathcal{S}$
and produces an output $o^{(\tau)}\in\mathcal{O}$. The execution of $P$
finishes if one of the exiting routines finishes execution. The goal of a
program-guided task is to produce desired execution results to achieve the
goal $\mathcal{G}$.

Result: Execution results $\\{o^{(\tau)}\\}_{\tau=1}^{T}$

1 Initialize $\tau=0$ and the pointer $p$;

2 Build $\mathbf{P}^{s}$ according to Eq. 1;

3 while  _not reach an exiting routine_ do

4 Observe $s^{(\tau)}$ and set $\tau$ = $\tau+1$ ;

5 Build $\mathbf{P}^{t(\tau)}$ according to Eq. 2;

6
$o^{(\tau)}=\mbox{ProToInfer}(s^{(\tau)},\mathbf{P}^{s},\mathbf{P}^{t(\tau)},p)$;

7 Output $o^{(\tau)}$ ;

8 if  _$P_{p}$ finishes execution_ then

9 UpdatePointer($p$, $o^{(\tau)}$, $P_{p}$) ;

10

11 end while

Algorithm 1 ProTo Execution

1 if  _$P_{p}$ is an If-routine_ then

2 Point $p$ to the first routine in the $T/F$ branch if $o^{(\tau)}$ is
$T$/$F$;

3

4 else if  _$P_{p}$ is a While-routine_ then

5 Point $p$ to the first routine inside/outside the loop if $o^{(\tau)}$ is
$T$/$F$;

6

7 else if  _$P_{p}$ ends a loop_ then

8 Point $p$ to the loop condition routine.

9 else

10 Point $p$ to the subsequent routine;

11

12 end if

Algorithm 2 UpdatePointer($p$, $o^{(\tau)}$, $P_{p}$)

##  4 Program-guided Transformer

A good model for a program-guided task should fulfill the following merits.
First of all, it should leverage both the semantics and structures provided by
the program (refer to Figure 2). Second, it would better be a multi-task
architecture with shared parameters for different routines to ensure
efficiency and generalization [15, 88, 69]. Third, it would be better if the
model does not leverage external memory for the efficiency of batched training
[64]. To these ends, we present the Program-guided Transformer (ProTo). ProTo
treats routines as objects and leverages attention mechanisms to model
interactions among routines and specifications. The execution process of ProTo
is presented in Algorithm 1. In each execution timestep, ProTo leverages the
semantic guidance $\mathbf{P}^{s}$ and the current structure guidance
$\mathbf{P}^{t(\tau)}$ (Line 2&5 in Algorithm 1, detailed in Sec 4.1) and
infers for one step (Line 6 in Algorithm 1, detailed in Sec 4.2). When a
routine finishes execution, a pointer $p\in\\{1,2,...,|P|\\}$ indicating the
current routine $P_{p}$ ($P_{p}$ is the $p$th routine in $P$) would be updated
(Line 8&9 in Algorithm 1, detailed in Algorithm 2 and Sec 4.3). The results of
ProTo are denoted as $\\{o^{(\tau)}\\}_{\tau=1}^{T}$ where $T$ is the total
number of execution timesteps. ProTo supports several training schemes, which
are listed in Sec 4.4.

###  4.1 Disentangled Program Representation

As shown in the left of Figure 2, we leverage both the semantics and structure
of the program in ProTo. The semantic part of the program
$\mathbf{P}^{s}\in\mathbb{R}^{|P|\times d}$ is an embedding matrix for all
routines where $\mathbb{R}$ is the real coordinate space and $d$ is a
hyperparameter specifying the feature dimension. Note $\mathbf{P}^{s}$ remains
the same for all execution timesteps. Denote
$\\{\mathbf{w}^{k}_{i}\\}_{i=0}^{L}$ to be the words in $P_{k}$ where $L$ is
the maximum number of words in one routine (padding words are added if $P_{k}$
does not have $L$ words), we construct the $k$-th row of $\mathbf{P}^{s}$
corresponding to $P_{k}$ via a concatenation of all token embeddings:

$\mathbf{P}^{s}_{k}=\bigparallel_{i}\mbox{WordEmbed}(\mathbf{w}^{k}_{i})$ (1)

where $\bigparallel\cdot$ represents the concatenation function and WordEmbed
maps a token to an embedding with dimension $d_{m}$ where we set $d=L\times
d_{m}$.

The structure part of the program
$\mathbf{P}^{t(\tau)}\in\mathbb{R}^{|P|\times|P|}$ is a transition mask
calculated at each execution timestep $\tau$ to pass messages from the
previous execution timestep to the current execution timestep. Although most
types of the routines only need to get information from the previously
executed routines, some logical routines such as Compare_Color() rely on more
than one routines’ results. We denote $\mbox{Parents}(P_{p})$ to be the set of
routines whose results would be taken as input by the current routine $P_{p}$.
We can easily derive $\mbox{Parents}(P_{p})$ from the program $P$, which is
detailed in the Appendix C.1. The transition mask $\mathbf{P}^{t(\tau)}$ is
defined by the following equation:

$\mathbf{P}^{t(\tau)}[i][j]=\begin{cases}0&\mbox{if
($P_{j}\in\mbox{Parents}(P_{p})$ and $P_{i}=P_{p}$) or ($i=j$)},\\\
-\infty&\mbox{else},\\\ \end{cases}$ (2)

where we set diagonal elements of $\mathbf{P}^{t(\tau)}$ to zeros to preserve
each routine’s self information to the next timestep. Positional encoding is
added following the standard transformer [85].

###  4.2 ProTo Inference

Given the disentangled program guidance $\mathbf{P}^{s}$,
$\mathbf{P}^{t(\tau)}$ and the current observed specification
$s^{(\tau)}\in\mathbb{R}^{N_{S}\times d}$ where $N_{s}$ is the number of
objects in the specification, ProTo infers the execution result $o^{(\tau)}$
via stacked attention blocks as shown on the right of Figure 2, which is
presented in detail in this subsection. Note we assume the specification is
represented in an object-centric manner, which might be obtained via a pre-
trained object detector [2] or an image patch encoder [25].

Figure 2: Main components of Program-guided Transformer (ProTo). Left: we
propose a disentangled program representation to leverage both semantics and
structures of the program. The shown program selects the bag and the wine from
the image and verifies whether the bag is on the left to the wine. Right:
given structure and semantic guidance offered by a program, ProTo updates the
result matrix leveraging the program guidance and the specification.

ProTo maintains a result embedding matrix $\mathbf{Z}\in\mathbb{R}^{|P|\times
d}$ which stores latent execution results for all routines. The result
embedding matrix is initialized as a zero matrix and is updated at each
timestep. We show the architecture of transformer executors in the right of
Figure 2. During ProTo inference, we first conduct cross-attention to inject
semantic information of routines to the hidden results via

$\mathbf{H_{1}}=\mbox{CrossAtt}_{1}(\mathbf{Z},\mathbf{P}^{s})=\mbox{softmax}(\frac{\mathbf{Z}\mathbf{P}^{s\top}}{\sqrt{d}})\mathbf{P}^{s}$
(3)

where $\mathbf{H_{1}}\in\mathbb{R}^{|P|\times d}$ is the first intermediate
latent results.

We propose to adopt masked self-attention [85] to propagate the information of
the previous results to the current routine. The masked self-attention
leverages the transition mask to restrict the product of queries and keys
before softmax (queries, keys and values are the same in the self-attention).
Formally, we acquire the second intermediate results
$\mathbf{H_{2}}\in\mathbb{R}^{|P|\times d}$ by

$\mathbf{H_{2}}=\mbox{MaskedSelfAtt}(\mathbf{H_{1}},\mathbf{P}^{t(\tau)})=\mbox{softmax}(\frac{\mathbf{H_{1}}\mathbf{H_{1}}^{\top}}{\sqrt{d}}+\mathbf{P}^{t(\tau)})\mathbf{H_{1}}.$
(4)

After that, we apply cross-attention again to update results based on the
specification $s^{(\tau)}$:

$\mathbf{Z}=\mbox{CrossAtt}_{2}(\mathbf{H_{2}},s^{(\tau)})=\mbox{softmax}(\frac{\mathbf{H_{2}}s^{(\tau)\top}}{\sqrt{d}})s^{(\tau)}.$
(5)

The above equations for self-attention and cross-attention show only one head
of self-attention and cross-attention for simplicity. However, in experiments,
we use multi-head attention with eight heads [85]. The resulting embedding
corresponding to the pointed routine $\mathbf{Z}_{p}$ would be decoded via an
MLP to produce an explicit output $o^{(\tau)}=\mbox{MLP}(\mathbf{Z}_{p})$.

###  4.3 Pointer Update

After each execution timestep, we would update the pointer $p$ if $P_{p}$
finishes execution. Note that some routines cannot be finished in one
execution timestep (e.g., the routine Mine(gold) requires the agent to
navigate to the gold and then take Mine action). We know the execution of
$P_{p}$ is finished if the execution result $o^{(\tau)}$ meets the ending
condition of $P_{p}$ (e.g. when $o^{(\tau)}$ is the Mine action and the agent
successfully mines a gold, we judge that Mine(gold) is finished). A full list
of ending conditions for all routines is in the Appendix B.

The pointer $p$ is updated according to the control flow [1, 18, 79] of the
program. The pointer’s movement is determined by the execution result
$o^{(\tau)}$, the type of $P_{p}$, and the location of $P_{p}$. We outline the
detailed procedure of pointer update in Algorithm 2.

##### Parallel Execution

Transformer has one powerful ability that it can conduct sequential prediction
in parallel [85]. In our case, we can execute routines that do not have result
dependency in parallel. We only need to modify the masked self-attention in
Eq. 4 to support passing multiple routines’ messages in parallel. Furthermore,
multiple pointers would be adopted and updated in parallel, while multiple
results would be output in parallel in one execution timestep. We detail the
paralleled version of Algorithm 1 and Algorithm 2 in the Appendix C.2.

###  4.4 ProTo Training Targets

After deriving the execution results of all routines denoted via
$\\{o^{(\tau)}\\}_{\tau=1}^{T}$, ProTo can be trained via the following three
types of training targets. (1) Dense Supervision $\mathcal{L}_{D}$. When the
ground truth of all execution results of all routines
$\\{\widetilde{o}^{(\tau)}\\}_{\tau=1}^{T}$ is known, we can use a dense loss
$\mathcal{L}_{D}$, which is the $L_{2}$ distance between
$\\{o^{(\tau)}\\}_{\tau=1}^{T}$ and
$\\{\widetilde{o}^{(\tau)}\\}_{\tau=1}^{T}$. (2) Partial Supervision
$\mathcal{L}_{P}$. Knowing the final execution result of the whole program
$\widetilde{o}^{(T)}$, ProTo can be learned through partial supervision
$\mathcal{L}_{P}$ which measures the $L_{2}$ distance between $o_{T}$ and
$\widetilde{o}^{(T)}$. (3) RL Target $\mathcal{L}_{R}$. When a program is
successfully executed, the environment gives the agent a sparse reward of
$+1$. Otherwise, the agent gets a zero reward. In this case, ProTo can be
optimized via a reinforcement learning loss $\mathcal{L}_{R}$ [51, 79]. In
experiments, we follow the same type of supervision as the corresponding
baselines, which varies from task to task.

##  5 Experiments

###  5.1 Program-guided Visual Reasoning

Table 1: Comparison of ProTo with previous models on the test2019 split of the
GQA dataset. In the collum of training Signal, we use QA, SG, Prog to denote
question-answer pairs, scene graphs, and programs. As for the metrics, Cons.,
Plaus., Valid., Distr., Acc. represent consistency, plausibility, validity,
distribution, and accuracy correspondingly.

Model | Signal | Binary | Open | Cons. | Plaus. | Valid. | Distr. | Acc.
---|---|---|---|---|---|---|---|---
Human [47] | - | 91.20 | 87.40 | 98.40 | 97.20 | 98.90 | - | 89.30
BottomUp [2] | QA | 66.64 | 34.83 | 78.71 | 84.57 | 96.18 | 5.98 | 49.74
MAC [46] | QA | 71.23 | 38.91 | 81.59 | 84.48 | 96.16 | 5.34 | 54.06
LXMERT [81] | QA | 77.16 | 45.47 | 89.59 | 84.53 | 96.35 | 5.69 | 60.33
NSM [45] | SG | 78.94 | 49.25 | 93.25 | 84.28 | 96.41 | 3.71 | 63.17
PVR [56] | Prog | 78.02 | 43.75 | 91.43 | 84.77 | 96.50 | 6.00 | 59.81
SNMN [42] | Prog | 73.40 | 40.82 | 85.11 | 84.79 | 96.37 | 5.14 | 56.09
MMN [15] | Prog | 78.90 | 44.89 | 92.49 | 84.55 | 96.19 | 5.54 | 60.83
ProTo | Prog | 79.12 | 51.45 | 93.45 | 86.12 | 96.52 | 3.66 | 65.14

Table 2: Accuracy of the ablation study on the validation split of the GQA
dataset.

Model | Acc.
---|---
ProTo Full Model | 64.47
No Structure Guidance | 55.16
No Semantic Guidance | 33.82
GAT Encoding | 58.58
Partial Supervision | 60.28
NS-VQA [93] | 29.57
IPA-GNN [10] | 47.10
MMN [15] | 60.40

Table 3: Results of the generalization experiments on the validation split of
GQA dataset.

Generalization | Model | Acc.
---|---|---
Human Program Guidance | MMN [15] | 59.47
ProTo | 70.33
Unseen Programs | MMN [15] | 61.88
ProTo | 65.34
Restricted Data Regime | MMN [15] | 52.39
ProTo | 58.31

##### Task Description

Program-guided visual reasoning requires the agent to follow program guidance
to reason about an image. It is formed by a tuple
$(\mathcal{S}^{v},\Gamma^{v},\mathcal{O}^{v},\mathcal{G}^{v})$ where $v$
denotes the visual reasoning task. One specification $s\in\mathcal{S}^{v}$ is
the object-centric representation of an image formed via a pre-trained object
detector [2], which is not updated from time to time. In other words,
$s^{(\tau)}$ = $s^{(\tau+1)}$ holds for each timestep $\tau$. The design of
the program space $\Gamma^{v}$ follows the previous work [47]. The output set
$\mathcal{O}^{v}$ is the possible results for all routines for all the
programs (all types of results are encoded to fixed-length vectors as
explained in Appendix D.1). We define an answer to a program $P$ to be the
final execution result of the program $P$, and the goal of program-guided
visual reasoning $\mathcal{G}^{v}$ is to predict the correct answer to the
program. As for the training target, we adopt the dense supervision
$\mathcal{L}_{D}$ as described in Sec 4.4 to train ProTo following previous
approaches [15, 42, 56].

##### Dataset Setup

We conduct experiments of program-guided visual reasoning based on the public
GQA dataset [47] consisting of 22 million questions over 140 thousand images.
It is divided into training, validation, and testing splits. The ground true
answers, programs, and scene graphs are provided in the training and
validation split but not in the test split. We use the provided balanced
training split to control data bias. On the training split, we train a
transformer-based seq2seq model [85] to parse a question into a program. For
validation and testing, we use this trained seq2seq model to acquire a program
from a question 222In the GQA dataset [47], we found that a simple seq2seq
model can achieve 98.1% validation accuracy to convert a natural language
question into a program. The concurrent work [15] also found a similar fact..
Besides answer accuracy, the GQA dataset [47] offers three more metrics
evaluating the consistency, validity, and plausibility of learned models.

##### Experiment Details

We take $N=50$ object features (provided by the GQA dataset) with $d=2048$
dimension. The optimizer is BERT Adam optimizer [24] with a base learning rate
$1\times 10^{-4}$, which is decayed by a factor of $0.5$ every epoch. To
alleviate over-fitting, we adopt an L2 weight decay of $0.01$. The model is
trained for $20$ epochs on the training split, and the best model evaluated on
the validation split is submitted to the public evaluation server to get
testing results. The testing results of baselines are taken from the
corresponding published literature [81, 45, 15] or the leaderboard. Following
[15, 45], we do not list unpublished methods or methods leveraging external
datasets.

##### Testing Results

We present the results on the testing split of GQA comparing to previous
baselines in Table 5.1. ProTo surpasses all previous baselines by a
considerable margin, successfully demonstrating the effectiveness of leverage
program guidance in reasoning. The superior performance of ours over the
concurrent work meta module network (MMN) [15] reveals ProTo’s strong modeling
ability. More visualizations are in Appendix D.1.

##### Ablation Study

We ablate our full model to the following variants to study the importance of
different components. Despite the described changes, other parts remain the
same with the full model. (1) No Structure Guidance. Only the semantic
guidance is used, and $\mathbf{P}^{t(\tau)}$ is set to the all-zeros matrix in
Eq 4. (2) No Semantic Guidance. The semantic guidance $\mathbf{P}^{s}$ is set
to the all-zeros matrix to disable semantics guidance. (3) GAT Encoding. We
use graph attention networks [86] to encode the program and fuse the program
feature with result embedding matrix and specification feature via two
consecutive cross attention modules (refer to Appendix D.1 for details). (4)
Partial Supervision. We only supervise the predicted answer to the program but
do not give dense intermediate supervision (refer to Sec 4.4).

Table 2 shows the results, and the validation accuracy of two program-based
baselines is listed for reference. The results demonstrate that both structure
guidance and semantic guidance contribute significantly to the overall
performance. ProTo is also better than the GNN baseline because of the strong
cross-modal representation learning ability of the transformer [43]. And the
extremely low validation accuracy of NS-VQA [95], which is reported by its
authors in [93], reveals that the hard-coded program executors are not as
powerful as the learned transformer executors.

##### Generalization Experiments

We conduct systematical experiments to evaluate whether humans can guide the
reasoning process via programs. More details are in the Appendix D.1. (1)
Human Program Guidance. We test whether humans can guide the reasoning process
via programs on a collected GQA-Human-Program dataset. We ask volunteers to
write 500 programs and corresponding answers on 500 random pictures taken from
the GQA validation split. No natural language questions are collected. All the
models are trained on the training split of GQA and tested on the GQA-Human-
Program dataset. (2) Unseen Programs. Following [15], we remove from the
training split all the programs containing the function verify_shape, and we
evaluate the models on the instances containing verify_shape on the validation
split. (3) Restricted Data Regime. We restrict the models only to use $10\%$
uniformly sampled training data to test the data efficiency of models.

Results are presented on Table 3. We found that ProTo can successfully
generalize its learned program execution ability to human written programs,
surpassing the previous state-of-the-art neural module network approach by
over 10 points. ProTo can also generalize to unseen programs, again verifying
the compositional generalization ability of our neural-symbolic transformer
model [24, 20]. Besides, ProTo is more data-efficient than MMN [15]. We also
found that ProTo is much more effective than the recent learning-to-execute
approach IPA-GNN [10].

###  5.2 Program-guided Policy Learning

Figure 3: Training curves on the 2D Minecraft environments in comparison to
several baselines. Both mean and standard errors over ten random agents are
shown in the figure.

##### Task Description

Program-guided policy learning requires the agent to learn a policy perform
tasks following a given program [79]. We denote this task as a tuple
$(\mathcal{S}^{p},\Gamma^{p},\mathcal{O}^{p},\mathcal{G}^{p})$ where $p$
stands for the policy learning task. Since we are experimenting on a grid-
world environment, the specification $s\in\mathcal{S}^{p}$ is the feature
embeddings of $N_{g}$ objects placed in $N_{g}$ grids. Unlike the visual
reasoning task, the specification is updated by the environment at each
timestep $\tau$ after the agent takes an action. The design of the program
space $\Gamma^{p}$ follows [79]. The output space $\mathcal{O}^{p}$ consisting
of several types: (1) Boolean results (True or False); (2) Motor Actions (e.g.
Up); (3) Interactive Actions (e.g. Mine and Build). Note the agent can only
interact with the grid it stands on. In this task, the agent should learn from
a reward signal $\mathcal{L}_{R}$ (described in Sec 4.4) while we also
experiment applying the dense supervision. The goal $\mathcal{G}^{p}$ is to
maximize the task completion rates [79].

##### Experiment Details

Following [75, 79], we conduct experiments on a 2D Minecraft Environment333The
implementation of the environment, the dataset, and the baselines are provided
by the authors of [79].. Programs are sampled from the DSL and divided into
training and testing splits ($4000$ for training and $500$ for testing). For
each instance, the agent must follow a given program to navigate the grid
world, mine resources, sell mined resources from its inventory, or place
marks. The baselines include Program-guided Agent (PGA) [79], the naïve
Transformer [85], and TreeRNN [80]. PGA separately learns perception and
policy modules. Transformer and TreeRNN encode the input program in a token by
token manner and output an action distribution. We ensure that the number of
parameters for different methods is comparable. We use the same manner of
encoding the objects in the grid into features as [79], which are projected to
$d$-dimension features via an MLP. The policy is optimized via the actor-
critic (A2C) algorithm [51], and we use the same policy learning
hyperparameters with PGA [79], which are detailed in the Appendix D.2 for
reference. When using dense supervision, the ground-true execution traces come
from a hard-coded planner. More details are in the Appendix D.2.

Table 4: Task completion rates on 2D MineCraft under different test settings. We repeat each experiments on 10 different random seeds and we show both averaged rates and their standard deviations. Baseline numbers are slightly different from [79] due to random noises. Supervision | RL Target | Dense Supervision
---|---|---
Model | Transformer [85] | PGA [79] | ProTo | PGA[79] | ProTo
Standard Testing | 50.1$\pm$3.2 | 94.2$\pm$0.8 | 97.3$\pm$2.1 | 96.9$\pm$0.9 | 99.1$\pm$0.5
Longer Programs | 41.2$\pm$3.5 | 86.1$\pm$0.9 | 91.2$\pm$3.3 | 92.1$\pm$0.7 | 94.4$\pm$0.8
Complex Programs | 40.8$\pm$1.8 | 89.7$\pm$0.3 | 95.0$\pm$2.5 | 91.2$\pm$0.5 | 96.3$\pm$1.0
Figure 4: An example of result on the 2D Minecraft environment. The given
program is shown in (a). Each timestep’s execution results and specifications
are shown in (b) top and (b) bottom, respectively. Due to space limitations,
we only show some specifications along the timeline, and the arrows in (b)
denote the places of the specifications in the timeline.

##### Training Curves, Testing Results and Visualization

We first show the training curves under the RL target in Figure 3. We observe
that ProTo surpasses Program-guided Agent (PGA) [79], which demonstrates the
power of leveraging disentangled program guidance in transformers. The fact
that ProTo outperforms the vanilla end-to-end transformer by a large margin
demonstrates the effectiveness of explicitly leveraging program structure
guidance.

We test the trained agent in different settings. Despite the Standard Testing
split offered by [79], we sample two more splits from the DSL while ensuring
the testing cases are not seen in the training split: Longer Programs and
Complex Programs. All programs in Longer Programs contain more than eighty
tokens, while all programs in Complex Programs include more than four If or
While tokens. Furthermore, we add execution losses on the training split and
test the baseline method PGA and our method. The results on the test splits
are shown in Table 4. We find that ProTo performs better than PGA [79] on all
testing settings. ProTo scales better than PGA to longer and complex programs,
demonstrating the strong ability of ProTo to leverage the program structure.
We also observe that ProTo has superior performance when dense execution
supervision is provided. A demonstration of the test split is provided in
Figure 4, where we observe ProTo successfully learns to execute the program
and develops a good policy to follow the program guidance.

##  6 Conclusion and Future Work

In this paper, we formulated program-guided tasks, which asked the agent to
learn to interpret and execute the given program on observed specifications.
We presented the Program-guided Transformer (ProTo), which addressed program-
guided tasks by executing the program in a hidden space. ProTo provides new
state-of-the-art performance versus previous dataset-specific methods in
program-guided visual reasoning and program-guided policy learning.

Our work suggests multiple research directions. First, it’s intriguing to
explore more advanced and challenging program-guided tasks, such as program-
guided embodied reasoning [21] and program-guided robotic applications [68].
Second, we are learning separate parameters for different tasks, while
building general and powerful program executors across tasks with shared
parameters is very promising [44, 90, 88]. Additionally, improving transformer
executors with more hierarchy [59] and better efficiency [96] is a meaningful
future direction.

##  7 Acknowledgement

We thank Shao-Hua Sun for sharing his codes to us. This work is supported in
part by the DARPA LwLL Program (contract FA8750-19-2-0201).

Figure 1: Visualization of validation results on the GQA dataset (Part 1). We
use the green tick and the red cross to denote right and wrong reasoning
result respectively. The MMN approach fails both examples while ProTo
successfully addresses them. Figure 2: Visualization of validation results on
the GQA dataset (Part 2). We use the green tick and the red cross to denote
right and wrong reasoning results, respectively. Both models predict the
correct answer in the first example, and the reasoning traces are the same.
For the second example, our model gets the correct answer, but the MMN
baseline fails. Figure 3: Visualization of test results on the Minecraft
environment in comparison to program-guided agent [79] (Part 1). Due to space
limitations, we omit the middle steps for executing routines and directly show
the execution results of routines. We use the green tick and the red cross to
denote right and wrong reasoning results, respectively. Additionally, we use a
red circle to indicate that the agent has failed some routine (therefore, the
program execution is failed). We observe that the ProTo agent can build a
bridge to cross a river to place a circle on the other side of the river, but
PGA fails to do so. Figure 4: Visualization of test results on the Minecraft
environment in comparison to program-guided agent [79] (Part 2). Due to space
limitations, we omit the middle steps for executing routines and directly show
the execution results of routines. We use the green tick and the red cross to
denote right and wrong reasoning results, respectively. We observe that the
ProTo agent can mine the gold in the corner, but PGA fails to do so within the
time constraint.

##  Appendix A Extended Related Work

##### Transformers with Masked Attention

We notice a few transformer-based architectures adopt masked attention to
achieve different goals. First, the masked self-attention [85] is adopted to
restrict the model from seeing subsequent positions of tokens for machine
translation. Second, mask attention networks [28] uses mask matrices to
enforce the localness modeling ability of transformers. Third, in the vision
domain, attention masks are used to highlight specific classes of visual
content (e.g., foreground objects) [76, 89]. One concurrent unpublished work
[34] uses masked attention to model data flow relationship for source code
summarization.

##### Neural Symbolic Learning

The goal of neural symbolic learning is to pursue a coherent, unified view of
symbolic logic-based computation and neural computation [9, 35, 36]. Previous
neural symbolic systems involve visual reasoning [95, 64], logic induction
[63], and reading comprehension [19]. We propose to leverage transformer
architecture to integrate perception, reasoning, and decision. We believe
transformer architecture would advance neural-symbolic systems because of its
ability of compositional representation learning.

##  Appendix B Program Details

In this section, we provide more details of the programs on two experimented
tasks.

###  B.1 Program-guided Visual Reasoning

All types of routines on the GQA dataset [47] are provided in Table 8. No loop
or branching routines exist in the GQA datasets. In the GQA dataset, the
entrance routine is the first routine in the program, and the exiting routine
is the last routine of the program, which would produce the final answer to
the program. Some types of routines may use more than one inputs.

There are three types of program inputs and outputs (execution results). The
first type is Objects, which is a probabilistic distribution over detected
objects [64]. The second type is Boolean that is either True or False.
Finally, the Answer type is a distribution over all answer candidates. We
acquire the ground true execution results by executing ground true programs on
the ground true scene graphs. Since the dimensions of results for different
types of routines are different, we use MLPs with different output dimensions
to decode the result embeddings of different routines. Note that ProTo
executes the program in a latent space, so no explicit inputs are directly
sent to ProTo. Only latent embeddings are sent into ProTo. The latent result
embeddings are grounded to the explicit results via execution losses.

All the routines on the GQA datasets are single-step routines, which are
finished via only a single forward step. In other words, we always update the
pointer at each execution step.

###  B.2 Program-guided Policy Learning

We list different types of routines on the 2D Minecraft datasets in Table 5.
In this dataset, the entrance routine is the first routine in the program, and
the exiting routines are routines that might be executed at the end of the
program execution 444In branching cases, the last routines of both branches
are possibly executed, so they are all exiting routines..

All routines in 2D Minecraft datasets take the specification as input and
output either actions or Boolean results. The actions can either be motor
actions or interactive actions as described in Sec 5.2 of the main text. Like
the GQA experiments, we also use MLPs with different output dimensions to
decode the results embeddings.

The list of ending conditions is also provided in Table 5. Note that the PGA
baseline [79] uses the same set of end conditions.

We visualize the distribution of program lengths on both GQA and Minecraft in
Figure D6.

##  Appendix C Algorithm Details

###  C.1 Derive Parents of Routines

For the GQA dataset, the parents of routines are provided in the ground
truths. For example, in the Figure 2 of main text, the parents of the third
routine (Verify_relation(left)) are the first routine (Select(bag)) and the
second routine (Select(wine)).

For the Minecraft dataset, the parent of one routine is the previously
executed routine. Each routine only depends on the previous routine, and no
routines rely on more than one routine.

###  C.2 Parallel Execution

Since ProTo is a transformer-like [85] architecture, it has a promising
ability to execute many routines in parallel when they have no result
dependency. A typical example is shown in Figure C5. The parallel version of
algorithms is shown in Algorithm 3 and Algorithm 4. We adopt a vector of
pointers $\mathbf{p}$ to point to different routines executed in parallel.

The semantic guidance remains the same as Eq. 1. We revise the structure
guidance $\mathbf{P}$ to support executing many routines in one time as the
following equation:

$\mathbf{P}^{t(\tau)}[i][j]=\begin{cases}0&\mbox{if ($\exists p\in\mathbf{p}$,
s.t. $P_{j}\in\mbox{Parents}(P_{p})$ and $P_{i}=P_{p}$) or ($i=j$)},\\\
-\infty&\mbox{else}.\\\ \end{cases}$ (6)

Parallel execution is only enabled in the GQA experiments. On the Minecraft
datasets, there is only one agent who needs to perform all the required tasks.
So the routines in the Minecraft experiments can not be executed in parallel.
We expect this parallel execution feature can be tested on a multi-agent
environment [57] in the future.

Note that in the main text, we explain our approach sequentially for ease of
understanding.

Result: Execution results $\\{o^{(\tau)}\\}_{\tau=1}^{T}$

1 Initialize $\tau=0$ and a pointer;

2 Build $\mathbf{P}^{s}$ according to Eq. 1;

3 while  _not reach an exiting routine_ do

4 Observe $s^{(\tau)}$ and set $\tau$ = $\tau+1$ ;

5 if  _there are routines that can be executed in parallel_ then

6 Spawn a vector of pointers $\mathbf{p}$ to point to those routines;

7 Build $\mathbf{P}^{t(\tau)}$ according to Eq. 6;

8
$o^{(\tau)}=\mbox{ProToInfer}(s^{(\tau)},\mathbf{P}^{s},\mathbf{P}^{t(\tau)},\mathbf{p})$;

9 Output $o^{(\tau)}$ ;

10 ParaUpdatePointer($\mathbf{p}$, $o^{(\tau)}$) ;

11

12 end while

Algorithm 3 ProTo Execution in Parallel

1 if  _parallel routines finishes execution_ then

2 Merge pointers $\mathbf{p}$.

3 for  _one pointer $p$ in $\mathbf{p}$_ do

4 if  _$P_{p}$ does not finish execution_ then

5 return

6 if  _$P_{p}$ is an If-routine_ then

7 Point $p$ to the first routine in the $T/F$ branch if the result of $P_{p}$
is $T$/$F$;

8

9 else if  _$P_{p}$ is a While-routine_ then

10 Point $p$ to the first routine inside/outside the loop if the result of
$P_{p}$ is $T$/$F$;

11

12 else if  _$P_{p}$ ends a loop_ then

13 Point $p$ to the loop condition routine.

14 else

15 Point $p$ to the subsequent routine;

16

17 end if

18

19 end for

Algorithm 4 ParaUpdatePointer($\mathbf{p}$, $o^{(\tau)}$) Figure C5: An
example of ProTo parallel execution. We show the program and its semantics in
(a) and (b). The specification is shown in (c). We show the execution flow in
(d) where we can see we execute two routines at $\tau=2$. In (e), we show the
semantic guidance and the structure guidance of ProTo execution process.

##  Appendix D Experimental Details and Further Results

In this section, we provide more details and further results on two
experimented tasks.

###  D.1 Program-guided Visual Reasoning

####  D.1.1 Program Synthesis Model

We adopt a simple transformer-based seq2seq model [85] to translate a natural
language question into a program. Both the encoder and the decoder of the
seq2seq model are composed of six identical self-attention layers with hidden
feature dimensions $d_{h}=512$. The head number is eight.

The input question is encoded in a token-by-token manner via a learnable
dictionary $\phi_{q}$. We turn the ground true program into a sequence by
traversing the program tree via pre-order traverse. Segment tokens [SEG] are
added between two routines. The predicted sequential program can be recovered
via a reverse way. We used beam search with a beam size of $4$ and length
penalty $\alpha=0.6$ [85]. The validation accuracy of this model is $98.1\%$.

####  D.1.2 Program Representation

In the semantic part of the program, we set $d_{m}=256$, $L=8$ and $d=2048$.
In the implementation of the structure part, we use $-1\times 10^{9}$ as the
negative infinity, which is the same as the standard implementation of masked
attention in transformers [85].

####  D.1.3 Visualizations

We provide more visualization of ProTo on the validation datasets in
comparison to the concurrent work meta module networks (MMN) [15]. The
implementation and hyperparameters of meta module networks follow their
official code. Specifically, for the Objects types of results, we visualize
the predicted object with a probability $p>0.5$. For the results with type
Boolean or Answer, we present the choice with maximum probability. The
visualizations are shown in Figure 1 and Figure 2.

####  D.1.4 Details of the GAT Encoding

During the ablation study, we compare our model to graph attention networks
(GAT) [86]. The node features are semantic embeddings of routines, and the
edges represent message passing relationships. Specifically, the node features
are constructed via a concatenation of word embeddings, which is the same as
Eq. 1. The embedding dimension is the same as ProTo. One edge exists between a
routine and its parents as in Eq. 2. Note that since the GQA programs do not
have conditional routines such as While and If, the edges are determined
before execution. The routine embeddings are fed to two cross-attention
modules to fuse information of result embeddings and specifications following
Eq 3 and Eq 5. We also use an MLP to decode the latent results to get explicit
routine results.

The GAT model consists of three layers, where each layer has eight attention
heads with 256 features, following by an ELU nonlinearity.

####  D.1.5 Details of Generalization Experiments

##### Purpose of Collecting Additional Human-written Programs

We have the following reasons for collecting the human-written programs.
First, we are curious whether humans can communicate with machines via
programs, which has not been done by previous work before. Second, the GQA
questions and programs are synthetic, and many of the programs are awkward
(e.g., with many unnecessary modifiers such as "the baked good that is on the
top of the plate that is on the left of the tray"). Third, the GQA test split
programs are not publicly available, and the translated programs from the
questions may be inaccurate. Since the validation split has been used for
parameter tuning, we wish to benchmark program-guided visual reasoning on the
collected independent data points. Forth, this small-scale dataset lays the
ground for the construction of our novel dataset for program-guided tasks.

##### GQA-Humam-Program Dataset Collection Process

For the Human Program Guidance experiments, we create the GQA-Humam-Program
dataset to diagnose whether humans can guide the reasoning process via
programs. We employ five volunteers to write 500 programs and answers on the
GQA validation dataset. The estimated hourly wage is ten dollars, and the
total amount spent on volunteers is two thousand dollars. A parser checks the
written programs to ensure that they follow the domain specification language
of GQA. We encourage the volunteers to write longer and more complex programs.
Two volunteers cross-check the correctness of programs and answers. For
fairness of comparison, we retrain the meta neural module networks [15] on the
training split of GQA while preventing it from seeing the natural language
questions. The screenshot of the data collection tool is provided in Figure
D7.

##### Rationale Behind Unseen Programs Experiments

In the experiments of Unseen Programs, the models are required to learn
combinatorial word-level semantics to execute unseen programs. The training
set contains verify_size and filter_shape, the models may generalize
compositionally to the unseen program verify_shape.

##### Restricted Data Regime Experiments

We repeat for three random seeds and found the standard deviation of the
results is smaller than 2$\%$.

####  D.1.6 Computational Resources

We train our model and the baselines on a 48 core Ubuntu 16.04 Linux server
with eight Nvidia Titan-X GPU. The CPU is Intel Silver 4116 CPU @ 2.10GHz. The
total training time is around 48 hours.

####  D.1.7 License and Permissions

The GQA dataset is built upon Visual Genome [53], which is under Creative
Commons Attribution 4.0 International License. The GQA dataset is publicly
available so that we can use it for research purposes. The GQA dataset is used
in many published literature [47, 45], and we do not found offensive content
in this dataset.

Figure D6: The program length distribution on the GQA and the Minecraft dataset. Figure D7: Screenshot of the UI for the construction of the GQA-Humam-Program dataset. The submitted programs are checked by the parser and the collected answers are cross-checked by two more annotators. Table 5: All types of routines in the domain-specific language of the 2D MineCraft dataset [79]. We use Spec. to denote specification. Some routines require many arguments, which are numbered by integers with brackets (e.g., (1), (2), etc.). Type |  Arguments | Input | Output |  |  Semantics and
---
Ending Conditions
Mine |  Triangle, circle, rectangle, gold, wood, or iron | Spec. | Action |  |  Go to the item and pick it up.
---
Ended when the action "Mine" is predicted and the agent successfully mined a
gold.
BuildBridge |  - | Spec. | Action |  |  Go to the river and build a bridge.
---
Ended when the action "Bridge" is predicted and the agent successfully builds
a bridge.
Goto |  Coordinates | Spec. | Action |  |  Go to the coordinates.
---
Ended when the agent reaches the target.
Place |  |  (1) Triangle, circle
---
or rectangle
(2) Coordinates
Spec. | Action |  |  Place the object on the specified coordinates.
---
Ended when the action "Place" is predicted.
Sell |  Triangle, circle, rectangle, gold, wood, or iron | Spec. | Action |  |  Go to the merchant and sell mined items.
---
Ended when the action "Sell" is predicted.
If / If-Else |  (1) Agent, env, or is_there (2) Gold, wood, iron, bridge, river, merchant, wall, or flat (3) Operators ($>,\geq,=,<,\leq$) (4) Number | Spec. | Boolean |  |  Perform branching based on the condition in the if-clause.
---
Ended in a single execution step.
While |  |  (1) Agent, env, or is_there
---
(2) Gold, wood, iron,
bridge, river, merchant,
wall, or flat
(3) Operators
($>,\geq,=,<,\leq$)
(4) Number
Spec. | Boolean |  |  Perform looping based on the condition in the while-clause.
---
Ended in a single execution step.
Table 6: Architecture details of ProTo and the baselines on the 2D MineCraft dataset. Model | Parameters |  Architecture Details
---|---|---
ProTo | 1.30M |  Eight attention heads with an intermediate size of 64; shared computation between routines; the state map is encoded via a two-layer MLP with hidden size 256 and output size $d=2048$; the inventory is encoded via another two-layer MLP with hidden size 128 and output size $d=2048$; the inventory feature is added to the state map to produce the final specification feature; the output MLP is also a two-layer MLP with hidden size 256.
PGA | 1.21M |  The state map is encoded via a batch of CNNs with channel sizes of 32, 64, 96, and 128. Each convolutional layer has kernel size three and stride 2, which is followed by ReLU nonlinearity. The inventory is encoded via a two-layer MLP with a channel size of 256. The goal is encoded via a two-layer MLP with a channel size of 64. The features are fused via a modulation mechanism proposed by PGA [79].
Vanilla Transformer | 2.63M |  Two attentional layers stacked, with eight attention heads, a hidden size of 128, and an intermediate size of 256.
Tree-RNN | 0.51M |  Program embeddings are of dimension 128. Attention LSTM size of 128. Tree-RNN uses a composition module to aggregate all the children representation of a node, which is of size [128 × 128], and output projection weights of size [128 × 128], with a bias of size 128. The program embeddings are average pooled across one routine so that each routine will be mapped to a fixed dimension. The composition layer is applied when combining pooled embedding from all the children of a node.

###  D.2 Program-guided Policy Learning

####  D.2.1 Environment Details

The major environmental resources that the agent can interact with are gold,
wood, or iron. The environment may contain a river, and the agent cannot go
across unless a bridge is built. The size of the grid world ranges from five
to eight. There could be two to four merchants in the environment. The
environment is randomly initialized, and the agent is also randomly
initialized while ensuring the program can be finished. If the agent fails to
finish the program within 300 timesteps, the execution would be terminated
(timeout).

####  D.2.2 A2C and Hyper-parameters

We use the same implementation of the A2C algorithm as [79] (provided by its
authors). The A2C algorithm uses a learning rate of $1\times 10^{-3}$, $64$
environments running in parallel with $64$ number of workers. The number of
roll-out steps for each update is five. The agent is trained for $10^{7}$
timesteps. The balance of the entropy regularization term is $\beta=0.1$.

####  D.2.3 More Visualizations

We provide more visualizations of the results on the test splits in Figure 3
and Figure 4.

####  D.2.4 Architecture Details and Computational Costs

We list the computational costs and details of ProTo and the baselines in
Table 6.

Table 7: Comparison between the generalization ability of the planner and ProTo on the Minecraft dataset. Removed Routine | Planner Acc | ProTo Acc
---|---|---
Mine(Gold) | 11.4 | 59.3
Is_there(River) | 43.8 | 65.6
Agent[Silver] | 46.2 | 77.1

The server that we used is the same as the GQA experiments, but we only use a
single GPU in the Minecraft experiments following [79]. The total training
time is around 80 hours.

####  D.2.5 Details about the Planner Used in Dense Supervision

We create a planner to generate ground true execution traces to train the
ProTo baselines with full supervision. The planner uses a hard-coded
interpreter to parse the programs. For all the actions that need navigation,
the planner uses an A* search algorithm [26] to find the shortest path. For
the Bridge, Mine and Sell action, we would find the nearest river, the nearest
item or the nearest merchant. For the If and While routines, the planner uses
the symbolic information in the environment (e.g. env[gold]=3) to decide
whether the conditions are satisfied.

####  D.2.6 License and Permissions

The Minecraft dataset is under Creative Commons Attribution 4.0 International
License. We acquire this dataset and its license from the authors of [79].
Since it’s a synthetic dataset, we don’t think it has offensive content.

##  Appendix E Additional Discussions about the Neural-Symbolic Baselines

The comparison between different neural symbolic approaches is a significant
aspect of our work. On the first domain of visual reasoning, our paper shows
that a mixed parametric neural-symbolic model would outperform pure symbolic
non-parametric executors (Table 2). On the second domain of Minecraft, we have
compared neural baselines (Table 4). We also have a pure symbolic (non-
learning) method: the planner. The advantages of the learned executor beyond
the symbolic planner are as follows.

First, the hard-coded planner requires a lot of ad-hoc engineering work to
handle complex cases. But our method can learn from a sparse reward signal.
For example, our method can learn to build a bridge to cross the river to
fetch gold on the other side of the river without explicit supervision (just
given a reward signal). However, a planner needs to handle this case with
special treatment.

Second, we experiment on Minecraft to validate the ability of ProTo to
generalize across unseen routines. Specifically, we remove a routine from the
training split (e.g., Mine(Gold)) and test on programs that contain the
removed routine. This experiment validates the compositional generalization
ability (e.g., generalize to Mine(Gold) after seeing Is_there(gold)and
Mine(Silver)). Only a reward signal is used for training. Other experimental
details are the same as described in Sec 5.2. The planner is set to choose a
random legal action when meeting an unseen routine). The results on the
validation dataset are presented in Tab 7.

Third, the planner cannot scale up to a large number of states. A planner
cannot work well on a large-scale scenario such as the game GO [74].

Forth, the planner can never work on raw image observations. Note our
transformer-based architecture can work on raw image input after dividing the
observation into patches [25] or detecting objects in the raw image. But the
symbolic planner has no way to work on raw image inputs.

##  Appendix F Limitations

Despite our contributions to task formulation and ProTo models, our work has
several limitations. First, since the program-based approaches need to
leverage the program guidance and dense supervision, it cannot easily leverage
large-scale datasets for self-supervised pretraining [61]. We would work on
building large-scale datasets with program annotations to alleviate this
limitation. Second, we hypothesize that one can still improve proTo’s
architecture design since the community has not exploited the power of
transformers. We would incorporate recent advances in transformers [59, 96] to
improve ProTo. Furthermore, we could conduct more ablation studies to reveal
the importance of different components in ProTo.

##  Appendix G Broader Impact

Our findings provide a simple yet effective approach to address program-guided
tasks. Potentially, people may leverage ProTo models to instruct robots via
programs [68]. However, the learned executors may be attacked by adversarial
training [62]. And instructing machines via programs might require humans to
have more advanced knowledge (e.g., knowing the basic concepts of programs and
how to follow program syntax). Therefore, those of a low educational level may
not be able to leverage the benefits of our approach, which might aggravate
social inequalities.

Table 8: All types of routines in the domain-specific language of the GQA dataset [47]. Type |  Arguments | Input | Output |  Semantics
---|---|---|---|---
Select/Filter |  Position, color, material, shape, or activity | Objects | Objects |  Filter out a set of objects by the positions, colors, etc from the input objects.
Choose |  Name, scene, color, shape, position or attributes | Objects | Answer |  Choose one answer (e.g., name, scene, color) from given answer candidates.
Verify |  Color, shape, scene, or relation | Objects | Boolean |  Verify whether the given concepts (e.g., color, shape) holds true for the input objects.
|  Relate
---
InverseRelate
Name, or attributes | Objects | Objects |  Filter out a set of objects that have the relation concept (e.g., names, attributes) with the input objects.
Query |  Name, color, shape, scene or position | Objects | Answer |  Query the concept (e.g., name, color) of the input objects.
Common |  Color, or material | Two objects | Answer |  Query the common concepts (e.g., color, material) of the input objects.
Different |  Name, color, or material | Two objects | Boolean |  Return whether the concepts of the objects (e.g., name, color) are different.
Same |  Name or color | Two objects | Boolean |  Return whether the concepts of the objects (e.g., name, color) are same.
And |  - | Two booleans | Boolean |  Return whether the two input booleans are both True.
Or |  - | Two booleans | Boolean |  Return whether one of the two input conditions is True.
Exist |  - | Objects | Boolean |  Return whether the input object set is not empty.

## References

  * Allen [1970] Frances E Allen.  Control flow analysis.  _ACM Sigplan Notices_ , 5(7):1–19, 1970.
  * Anderson et al. [2018a] Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 6077–6086, 2018a.
  * Anderson et al. [2018b] Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 3674–3683, 2018b.
  * Andre & Russell [2003] David Andre and Stuart J Russell.  _Programmable reinforcement learning agents_.  PhD thesis, University of California, Berkeley, 2003.
  * Antol et al. [2015] Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh.  Vqa: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 2425–2433, 2015.
  * Argall et al. [2009] Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning.  A survey of robot learning from demonstration.  _Robotics and autonomous systems_ , 57(5):469–483, 2009.
  * Barto & Mahadevan [2003] Andrew G Barto and Sridhar Mahadevan.  Recent advances in hierarchical reinforcement learning.  _Discrete event dynamic systems_ , 13(1):41–77, 2003.
  * Bastani et al. [2018] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama.  Verifiable reinforcement learning via policy extraction.  _arXiv preprint arXiv:1805.08328_ , 2018.
  * Besold et al. [2017] Tarek R. Besold, Artur S. d’Avila Garcez, Sebastian Bader, Howard Bowman, Pedro M. Domingos, Pascal Hitzler, Kai-Uwe Kühnberger, Luís C. Lamb, Daniel Lowd, Priscila Machado Vieira Lima, Leo de Penning, Gadi Pinkas, Hoifung Poon, and Gerson Zaverucha.  Neural-symbolic learning and reasoning: A survey and interpretation.  _CoRR_ , abs/1711.03902, 2017.  URL http://arxiv.org/abs/1711.03902.
  * Bieber et al. [2020] David Bieber, Charles Sutton, Hugo Larochelle, and Daniel Tarlow.  Learning to execute programs with instruction pointer attention graph neural networks.  _CoRR_ , abs/2010.12621, 2020.  URL https://arxiv.org/abs/2010.12621.
  * Booth [2014] Paul Booth.  _An introduction to human-computer interaction (psychology revivals)_.  Psychology Press, 2014.
  * Bunel et al. [2018] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli.  Leveraging grammar and reinforcement learning for neural program synthesis.  _arXiv preprint arXiv:1805.04276_ , 2018.
  * Carion et al. [2020] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In _European Conference on Computer Vision_ , pp. 213–229. Springer, 2020.
  * Chen & Mooney [2011] David Chen and Raymond Mooney.  Learning to interpret natural language navigation instructions from observations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 25, 2011.
  * Chen et al. [2021] Wenhu Chen, Zhe Gan, Linjie Li, Yu Cheng, William Wang, and Jingjing Liu.  Meta module network for compositional visual reasoning.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pp. 655–664, 2021.
  * Chen et al. [2016] Xinyun Chen, Chang Liu, Richard Shin, Dawn Song, and Mingcheng Chen.  Latent attention for if-then program synthesis.  _arXiv preprint arXiv:1611.01867_ , 2016.
  * Chen et al. [2017] Xinyun Chen, Chang Liu, and Dawn Song.  Towards synthesizing complex programs from input-output examples.  _arXiv preprint arXiv:1706.01284_ , 2017.
  * Chen et al. [2018] Xinyun Chen, Chang Liu, and Dawn Song.  Execution-guided neural program synthesis.  In _International Conference on Learning Representations_ , 2018.
  * Chen et al. [2019] Xinyun Chen, Chen Liang, Adams Wei Yu, Denny Zhou, Dawn Song, and Quoc V Le.  Neural symbolic reader: Scalable integration of distributed and symbolic representations for reading comprehension.  In _International Conference on Learning Representations_ , 2019.
  * Chen et al. [2020] Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou.  Compositional generalization via neural-symbolic stack machines.  _arXiv preprint arXiv:2008.06662_ , 2020.
  * Das et al. [2018] Abhishek Das, Samyak Datta, Georgia Gkioxari, Stefan Lee, Devi Parikh, and Dhruv Batra.  Embodiedquestionanswering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1–10, 2018.
  * Devlin et al. [2017a] Jacob Devlin, Rudy Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli.  Neural program meta-induction.  _arXiv preprint arXiv:1710.04157_ , 2017a.
  * Devlin et al. [2017b] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli.  Robustfill: Neural program learning under noisy i/o.  In _International conference on machine learning_ , pp. 990–998. PMLR, 2017b.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Duchoň et al. [2014] František Duchoň, Andrej Babinec, Martin Kajan, Peter Beňo, Martin Florek, Tomáš Fico, and Ladislav Jurišica.  Path planning with modified a star algorithm for a mobile robot.  _Procedia Engineering_ , 96:59–69, 2014.
  * Ellis et al. [2017] Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Joshua B Tenenbaum.  Learning to infer graphics programs from hand-drawn images.  _arXiv preprint arXiv:1707.09627_ , 2017.
  * Fan et al. [2021] Zhihao Fan, Yeyun Gong, Dayiheng Liu, Zhongyu Wei, Siyuan Wang, Jian Jiao, Nan Duan, Ruofei Zhang, and Xuanjing Huang.  Mask attention networks: Rethinking and strengthen transformer.  _arXiv preprint arXiv:2103.13597_ , 2021.
  * Feser et al. [2016] John K Feser, Marc Brockschmidt, Alexander L Gaunt, and Daniel Tarlow.  Differentiable functional program interpreters.  _arXiv preprint arXiv:1611.01988_ , 2016.
  * Fikes & Nilsson [1971] Richard E Fikes and Nils J Nilsson.  Strips: A new approach to the application of theorem proving to problem solving.  _Artificial intelligence_ , 2(3-4):189–208, 1971\.
  * Fox et al. [2018] Roy Fox, Richard Shin, Sanjay Krishnan, Ken Goldberg, Dawn Song, and Ion Stoica.  Parametrized hierarchical procedures for neural programming.  _ICLR 2018_ , 2018.
  * Fried et al. [2018] Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Taylor Berg-Kirkpatrick, Kate Saenko, Dan Klein, and Trevor Darrell.  Speaker-follower models for vision-and-language navigation.  _arXiv preprint arXiv:1806.02724_ , 2018.
  * Gao et al. [2021a] Peng Gao, Jiasen Lu, Hongsheng Li, Roozbeh Mottaghi, and Aniruddha Kembhavi.  Container: Context aggregation network.  _CoRR_ , abs/2106.01401, 2021a.  URL https://arxiv.org/abs/2106.01401.
  * Gao et al. [2021b] Shuzheng Gao, Cuiyun Gao, Yulan He, Jichuan Zeng, Lun Yiu Nie, and Xin Xia.  Code structure guided transformer for source code summarization.  _CoRR_ , abs/2104.09340, 2021b.  URL https://arxiv.org/abs/2104.09340.
  * Garcez et al. [2019] Artur d’Avila Garcez, Marco Gori, Luis C Lamb, Luciano Serafini, Michael Spranger, and Son N Tran.  Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning.  _arXiv preprint arXiv:1905.06088_ , 2019.
  * Garcez et al. [2008] Artur SD’Avila Garcez, Luis C Lamb, and Dov M Gabbay.  _Neural-symbolic cognitive reasoning_.  Springer Science & Business Media, 2008.
  * Gers et al. [1999] Felix A Gers, Jürgen Schmidhuber, and Fred Cummins.  Learning to forget: Continual prediction with lstm.  _Neural Computation_ , 1999.
  * Graves et al. [2014] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  _arXiv preprint arXiv:1410.5401_ , 2014.
  * Gulwani [2014] Sumit Gulwani.  Program synthesis.  _Software Systems Safety_ , pp. 43–75, 2014.
  * Harnad [1993] Stevan Harnad.  Grounding symbols in the analog world with neural nets.  _Think_ , 2(1):12–78, 1993.
  * Ho & Ermon [2016] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  _arXiv preprint arXiv:1606.03476_ , 2016.
  * Hu et al. [2018] Ronghang Hu, Jacob Andreas, Trevor Darrell, and Kate Saenko.  Explainable neural computation via stack neural module networks.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 53–69, 2018.
  * Huang et al. [2019] Haoyang Huang, Yaobo Liang, Nan Duan, Ming Gong, Linjun Shou, Daxin Jiang, and Ming Zhou.  Unicoder: A universal language encoder by pre-training with multiple cross-lingual tasks.  _arXiv preprint arXiv:1909.00964_ , 2019.
  * Huang et al. [2020] Wenlong Huang, Igor Mordatch, and Deepak Pathak.  One policy to control them all: Shared modular policies for agent-agnostic control.  In _International Conference on Machine Learning_ , pp. 4455–4464. PMLR, 2020.
  * Hudson & Manning [2019a] Drew Hudson and Christopher D Manning.  Learning by abstraction: The neural state machine.  In _Advances in Neural Information Processing Systems_ , pp. 5903–5916, 2019a.
  * Hudson & Manning [2018] Drew A Hudson and Christopher D Manning.  Compositional attention networks for machine reasoning.  In _International Conference on Learning Representations_ , 2018.
  * Hudson & Manning [2019b] Drew A Hudson and Christopher D Manning.  Gqa: A new dataset for real-world visual reasoning and compositional question answering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 6700–6709, 2019b.
  * Johnson et al. [2017a] Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 2901–2910, 2017a.
  * Johnson et al. [2017b] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Judy Hoffman, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick.  Inferring and executing programs for visual reasoning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 2989–2998, 2017b.
  * Kaiser & Sutskever [2015] Łukasz Kaiser and Ilya Sutskever.  Neural gpus learn algorithms.  _arXiv preprint arXiv:1511.08228_ , 2015.
  * Konda & Tsitsiklis [2000] Vijay R Konda and John N Tsitsiklis.  Actor-critic algorithms.  In _Advances in neural information processing systems_ , pp. 1008–1014. Citeseer, 2000.
  * Konidaris et al. [2012] George Konidaris, Scott Kuindersma, Roderic Grupen, and Andrew Barto.  Robot learning from demonstration by constructing skill trees.  _The International Journal of Robotics Research_ , 31(3):360–375, 2012.
  * Krishna et al. [2017] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ , 123(1):32–73, 2017.
  * Lake et al. [2015] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  _Science_ , 350(6266):1332–1338, 2015.
  * Lake et al. [2017] Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman.  Building machines that learn and think like people.  _Behavioral and brain sciences_ , 40, 2017.
  * Li et al. [2019] Guohao Li, Xin Wang, and Wenwu Zhu.  Perceptual visual reasoning with knowledge propagation.  In _Proceedings of the 27th ACM International Conference on Multimedia_ , MM ’19, pp. 530–538, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450368896.  doi: 10.1145/3343031.3350922.  URL https://doi.org/10.1145/3343031.3350922.
  * Littman [1994] Michael L Littman.  Markov games as a framework for multi-agent reinforcement learning.  In _Machine learning proceedings 1994_ , pp. 157–163. Elsevier, 1994.
  * Liu & Wu [2019] Yunchao Liu and Zheng Wu.  Learning to describe scenes with programs.  In _International Conference on Learning Representations_ , 2019.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  _arXiv preprint arXiv:2103.14030_ , 2021.
  * Lu et al. [2016] Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh.  Hierarchical question-image co-attention for visual question answering.  _arXiv preprint arXiv:1606.00061_ , 2016.
  * Lu et al. [2019] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  _arXiv preprint arXiv:1908.02265_ , 2019.
  * Madry et al. [2017] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Manhaeve et al. [2018] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Deepproblog: Neural probabilistic logic programming.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/dc5d637ed5e62c36ecb73b654b05ba2a-Paper.pdf.
  * Mao et al. [2019a] Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu.  The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision.  In _International Conference on Learning Representations_ , 2019a.  URL https://openreview.net/forum?id=rJgMlhRctm.
  * Mao et al. [2019b] Jiayuan Mao, Xiuming Zhang, Yikai Li, William T. Freeman, Joshua B. Tenenbaum, and Jiajun Wu.  Program-guided image manipulators.  _CoRR_ , abs/1909.02116, 2019b.  URL http://arxiv.org/abs/1909.02116.
  * Mohammad [2016] Saif M Mohammad.  Sentiment analysis: Detecting valence, emotions, and other affectual states from text.  In _Emotion measurement_ , pp. 201–237. Elsevier, 2016.
  * Parr & Russell [1998] Ronald Parr and Stuart Russell.  Reinforcement learning with hierarchies of machines.  _Advances in neural information processing systems_ , pp. 1043–1049, 1998.
  * Pomerleau et al. [1991] Dean A Pomerleau, Jay Gowdy, and Charles E Thorpe.  Combining artificial neural networks and symbolic processing for autonomous robot guidance.  _Engineering Applications of Artificial Intelligence_ , 4(4):279–285, 1991.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Reed & De Freitas [2015] Scott Reed and Nando De Freitas.  Neural programmer-interpreters.  _arXiv preprint arXiv:1511.06279_ , 2015.
  * Schaal et al. [1997] Stefan Schaal et al.  Learning from demonstration.  _Advances in neural information processing systems_ , pp. 1040–1046, 1997.
  * Shih et al. [2016] Kevin J Shih, Saurabh Singh, and Derek Hoiem.  Where to look: Focus regions for visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 4613–4621, 2016.
  * Shin et al. [2018] Richard Shin, Illia Polosukhin, and Dawn Song.  Towards specification-directed program repair, 2018.  URL https://openreview.net/forum?id=B1iZRFkwz.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Sohn et al. [2018] Sungryull Sohn, Junhyuk Oh, and Honglak Lee.  Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies.  _arXiv preprint arXiv:1807.07665_ , 2018.
  * Song et al. [2018] Chunfeng Song, Yan Huang, Wanli Ouyang, and Liang Wang.  Mask-guided contrastive attention model for person re-identification.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Sun et al. [2019a] Chen Sun, Austin Myers, Carl Vondrick, Kevin Murphy, and Cordelia Schmid.  Videobert: A joint model for video and language representation learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 7464–7473, 2019a.
  * Sun et al. [2018] Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim.  Neural program synthesis from diverse demonstration videos.  In _International Conference on Machine Learning_ , pp. 4790–4799. PMLR, 2018.
  * Sun et al. [2019b] Shao-Hua Sun, Te-Lin Wu, and Joseph J Lim.  Program guided agent.  In _International Conference on Learning Representations_ , 2019b.
  * Tai et al. [2015] Kai Sheng Tai, Richard Socher, and Christopher D Manning.  Improved semantic representations from tree-structured long short-term memory networks.  _arXiv preprint arXiv:1503.00075_ , 2015.
  * Tan & Bansal [2019] Hao Tan and Mohit Bansal.  Lxmert: Learning cross-modality encoder representations from transformers.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 5103–5114, 2019.
  * Teh et al. [2017] Yee Whye Teh, Victor Bapst, Wojciech Marian Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu.  Distral: Robust multitask reinforcement learning.  _arXiv preprint arXiv:1707.04175_ , 2017.
  * Tian et al. [2019] Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, William T Freeman, Joshua B Tenenbaum, and Jiajun Wu.  Learning to infer and execute 3d shape programs.  _arXiv preprint arXiv:1901.02875_ , 2019.
  * Trivedi et al. [2021] Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J. Lim.  Learning to synthesize programs as interpretable and generalizable policies, 2021.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _arXiv preprint arXiv:1706.03762_ , 2017.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Verma et al. [2018] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri.  Programmatically interpretable reinforcement learning.  In _International Conference on Machine Learning_ , pp. 5045–5054. PMLR, 2018.
  * Vilalta & Drissi [2002] Ricardo Vilalta and Youssef Drissi.  A perspective view and survey of meta-learning.  _Artificial intelligence review_ , 18(2):77–95, 2002.
  * Wang et al. [2020] Huiyu Wang, Yukun Zhu, Hartwig Adam, Alan L. Yuille, and Liang-Chieh Chen.  Max-deeplab: End-to-end panoptic segmentation with mask transformers.  _CoRR_ , abs/2012.00759, 2020.  URL https://arxiv.org/abs/2012.00759.
  * Wilson et al. [2007] Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli.  Multi-task reinforcement learning: a hierarchical bayesian approach.  In _Proceedings of the 24th international conference on Machine learning_ , pp. 1015–1022, 2007.
  * Wu et al. [2017] Jiajun Wu, Joshua B Tenenbaum, and Pushmeet Kohli.  Neural scene de-rendering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 699–707, 2017.
  * Xiao et al. [2018] Da Xiao, Jo-Yu Liao, and Xingyuan Yuan.  Improving the universality and learnability of neural programmer-interpreters with combinator abstraction.  _arXiv preprint arXiv:1802.02696_ , 2018.
  * Yang et al. [2020] Jianwei Yang, Jiayuan Mao, Jiajun Wu, Devi Parikh, David D Cox, Joshua B Tenenbaum, and Chuang Gan.  Object-centric diagnosis of visual reasoning.  _arXiv preprint arXiv:2012.11587_ , 2020.
  * Yang et al. [2019] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  _arXiv preprint arXiv:1906.08237_ , 2019.
  * Yi et al. [2018] Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Joshua B Tenenbaum.  Neural-symbolic vqa: Disentangling reasoning from vision and language understanding.  _arXiv preprint arXiv:1810.02338_ , 2018.
  * You et al. [2019] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh.  Large batch optimization for deep learning: Training bert in 76 minutes.  _arXiv preprint arXiv:1904.00962_ , 2019.
  * Zhang & Yang [2021] QingLong Zhang and Yubin Yang.  Rest: An efficient transformer for visual recognition.  _CoRR_ , abs/2105.13677, 2021.  URL https://arxiv.org/abs/2105.13677.
  * Zhao et al. [2020] Zelin Zhao, Chuang Gan, Jiajun Wu, Xiaoxiao Guo, and Joshua Tenenbaum.  Augmenting policy learning with routines discovered from a demonstration.  _arXiv preprint arXiv:2012.12469_ , 2020.
  * Zhou et al. [2015] Bolei Zhou, Yuandong Tian, Sainbayar Sukhbaatar, Arthur Szlam, and Rob Fergus.  Simple baseline for visual question answering.  _arXiv preprint arXiv:1512.02167_ , 2015.