ExeDec: Execution Decomposition for Compositional Generalization in
  Neural Program Synthesis
Kensen Shi Joey Hong Manzil Zaheer Pengcheng Yin Charles Sutton
When writing programs, people have the ability to tackle a new complex task
by decomposing it into smaller and more familiar subtasks. While it is
difficult to measure whether neural program synthesis methods have similar
capabilities, we can measure whether they compositionally generalize, that is,
whether a model that has been trained on the simpler subtasks is subsequently
able to solve more complex tasks. In this paper, we characterize several
different forms of compositional generalization that are desirable in program
synthesis, forming a meta-benchmark which we use to create generalization tasks
for two popular datasets, RobustFill and DeepCoder. We then propose ExeDec, a
novel decomposition-based synthesis strategy that predicts execution subgoals
to solve problems step-by-step informed by program execution at each step.
ExeDec has better synthesis performance and greatly improved compositional
generalization ability compared to baselines.