Title: EXECUTION-GUIDED NEURAL PROGRAM SYNTHESIS

Abstract: Neural program synthesis from input-output examples has attracted an increasing interest from both the machine learning and the programming language community. Most existing neural program synthesis approaches employ an encoder-decoder architecture, which uses an encoder to compute the embedding of the given inputoutput examples, as well as a decoder to generate the program from the embedding following a given syntax. Although such approaches achieve a reasonable performance on simple tasks such as FlashFill, on more complex tasks such as Karel, the state-of-the-art approach can only achieve an accuracy of around 77%. We observe that the main drawback of existing approaches is that the semantic information is greatly under-utilized. In this work, we propose two simple yet principled techniques to better leverage the semantic information, which are execution-guided synthesis and synthesizer ensemble. These techniques are general enough to be combined with any existing encoder-decoder-style neural program synthesizer. Applying our techniques to the Karel dataset, we can boost the accuracy from around 77% to more than 90%.

1. INTRODUCTION:

Program synthesis is a traditional challenging problem. Such a problem typically takes a specification as the input, and the goal is to generate a program within a target domain-specific language (DSL). One of the most interesting forms of the specifications is input-output examples, and there have been several applications, such as FlashFill (Gulwani, 2011; Gulwani et al., 2012) .

Recently, there is an increasing interest of applying neural network approaches to tackle the program synthesis problem. For example, Devlin et al. have demonstrated that using an encoder-decoderstyle neural network, their neural program synthesis algorithm called RobustFill can outperform the performance of the traditional non-neural program synthesis approach by a large margin on the FlashFill task (Devlin et al., 2017b) .

Despite their promising performance, we identify several inefficiencies of such encoder-decoder-style neural program synthesis approaches. In particular, such a neural network considers program synthesis as a sequence generation problem; although some recent work take the syntactical information into consideration during program generation (Bunel et al., 2018; Rabinovich et al., 2017; Yin & Neubig, 2017; Parisotto et al., 2017; Xu et al., 2017) , the semantic information, which is typically well-defined in the target DSL, is not effectively leveraged by existing work.

In light of this observation, in this work, we develop simple yet principled techniques that can be combined with any existing encoder-decoder-style neural program synthesizers. The main novel technique is called execution-guided synthesis. The basic idea is to view the program execution as a sequence of manipulations to transform each input state into the corresponding output state. In such a view, executing a partial program can result in intermediate states; thus, synthesizing the rest of the program can be conditioned on these intermediate states, so that the synthesizer can take the state changes into account in the followup program generation process. Therefore, we can leverage this idea to combine with any existing encoder-decoder-style neural synthesizer, and we observe that it can significantly improve the performance of the underlying synthesizers.

In addition, we also propose a simple yet effective technique called synthesizer ensemble, which leverages the semantic information to ensemble multiple neural program synthesizers. In particular, for the input-output program synthesis problem, we can easily verify if a synthesized program satisfies the input-output specification, which allows us to remove invalid predictions from the ensemble during inference time. Albeit its simplicity, to the best of our knowledge, we are not aware of any previous neural program synthesis work applying this approach. We observe that this technique further boosts the performance substantially.

We evaluate our techniques on the Karel task (Bunel et al., 2018; Devlin et al., 2017a) , the largest publicly available benchmark for input-output program synthesis, on which the most performant model in the past can achieve only an accuracy of around 77% (Bunel et al., 2018) . We observe that our proposed techniques can gain better performance than the previous state-of-the-art results. In particular, by combining both of our techniques, we can achieve an accuracy of 92%, which is around 15 percentage points better than the state-of-the-art results. This shows that our approach is effective in boosting the performance of algorithms for neural program synthesis from input-output examples.

2. NEURAL PROGRAM SYNTHESIS FROM INPUT-OUPUT EXAMPLES:

In this section, we first introduce the input-output program synthesis problem and existing encoderdecoder-style neural program synthesis approaches, then present an overview of our approaches.

2.1. PROBLEM DEFINITION:

We follow the literature (Devlin et al., 2017b; Bunel et al., 2018; Chen et al., 2018) to formally define the input-output program synthesis problem below.

Problem Definition 1 (Program emulation) Let L be the space of all valid programs in the domainspecific language (DSL). Given a set of input-output pairs

{(I k , O k )} K k=1 (or {IO K } in short)

, where there exists a program P ∈ L, such that

P (I k ) = O k , ∀k ∈ {1, ..., K}. Our goal is to compute the output O test for a new test input I test , so that O test = P (I test ).

Although the problem definition only requires to compute the output for a test input, a typical method is to synthesize a program P ∈ L such that P is consistent with all input-output pairs {IO K }, and then use P to compute the output. In this case, we say program P emulates the program P corresponding to {IO K }.

In particular, in this work, we are mainly interested in the following formulation of the problem.

Problem Definition 2 (Program synthesis) Let L be the space of all valid programs in the domainspecific language (DSL). Given a training dataset of {IO K } i for i = 1, ..., N , where N is the size of the training data, compute a synthesizer Γ, so that given a test input-output example set {IO K } test , the synthesizer Γ({IO K } test ) = P produces a program P , which emulates the program corresponding to {IO K } test .

2.2. ENCODER-DECODER-STYLE NEURAL PROGRAM SYNTHESIS APPROACHES:

There have been many approaches proposed for different neural program synthesis tasks, and most of them follow an encoder-decoder-style neural network architecture (Bunel et al., 2018; Devlin et al., 2017b; Parisotto et al., 2017) . Figure 1 shows a general neural network architecture for input-output program synthesis. First, an encoder converts input-output examples {IO K } into an embedding. For example, RobustFill (Devlin et al., 2017b) deals with the string transformation tasks, thus it uses LSTMs as the encoder. For the Karel task, both inputs and outputs are 2D grids (see Figure 2 ); therefore, Bunel et al. (2018) employ a CNN as the encoder.

Once the IO embeddings are computed, these approaches employ an LSTM decoder to generate the programs conditioned on the embeddings. For program synthesis, one unique property is that the generated program should satisfy the synthax of L. Therefore, a commonly used refinement is to filter syntactically invalid program prefixes during generation (Parisotto et al., 2017; Devlin et al., 2017b; Bunel et al., 2018) .

In the above approaches, only the syntax information is leveraged; the semantics of L is not utilized. In particular, standard supervised training procedure could suffer from program aliasing: for the same input-output examples, there are multiple semantically equivalent programs, but all except the one provided in the training data will be penalized as wrong programs. To mitigate this issue, Bunel et Figure 1 : A neural network architecture for input-output program synthesis (e.g., (Bunel et al., 2018) ). At each timestep t, the decoder LSTM generates a program token g t conditioned on both the input-output pairs {IO K } and the previous program token g t-1 . Each IO pair is fed into the LSTM individually, and a max-pooling operation is performed over the hidden states {h k t } K k=1 of the last layer of LSTM for all IO pairs. The resulted vector is fed into a softmax layer to obtain a prediction probability distribution over all the possible program tokens in the vocabulary. More details can be found in Appendix C. al. propose to train with reinforcement learning, so that it rewards all semantically correct programs once they are fully generated (Bunel et al., 2018) . In our work, we demonstrate that we can leverage the semantic information in an effective way that provides a better performance.

2.3. AN OVERVIEW OF OUR APPROACHES:

In this work, we propose two general and principled techniques that can improve the performance over existing work, which are execution-guided synthesis (Section 3) and synthesizer ensemble (Section 4). The main idea of our techniques is to better leverage the semantics of the language L during synthesis. Meanwhile, our techniques are compatible with any existing encoder-decoder-style neural program synthesis architecture. We will describe these techniques in detail in the following sections.

3. EXECUTION-GUIDED SYNTHESIS:

Existing approaches generate the entire program only based on the input-output examples before execution. However, this is an inefficient use of the semantics of L. For example, when a program consists of a sequence of statements, we can view the output to be a result by continuously executing each statement in the sequence to convert the input state into a sequence of intermediate states.

Figure 2 illustrates such an example. From this perspective, instead of generating the whole program at once, we can generate one statement at a time based on the intermediate/output state pairs. However, most interesting programs are not just sequential. In this work, we explore this idea using a general control-flow framework. In particular, given any language L, we extend it with three classical types of control-flow: sequential, branching, and looping. The extended language is call L ext . Then, we develop our above idea based on L ext , called execution-guided synthesis. In the following, to make our discussion concise, we first formalize L ext (Section 3.1), and then present the idea of execution-guided synthesis (Section 3.2).

S-Stmt:

S, s ⇓ s S, s → ⊥, s S-Seq B 1 , s → B 1 , s B 1 ; B 2 , s → B 1 ; B 2 , s S-Seq-Bot ⊥; B 2 , s → B 2 , s S-If C, s ⇓ b i = 1 b is true 2 b is false if C then B 1 else B 2 fi, s → B i , s S-While while C do B end, s → if C then B; while C do B end else ⊥ fi, s Table 2: Semantic rules B, s → B , s for L ext . 3.1 THE FORMAL SPECIFICATION OF THE EXTENDED LANGUAGE L ext P := B; ⊥ B := ⊥ | S | B; B | if C then B else B fi | while C do B end S, C ∈ L Table 1: Syntax of L ext .

In this work, we assume some additional control-flow syntax on top of L. We define the extended language L ext in Table 1 . In particular, we assume that a code block B can be composed by a sequence of statements S ∈ L or sub code blocks, and each code block can also be an if-statement or a while-statement. We use C to indicate a condition expression in L, and ⊥ to indicate the termination of a program execution.

The semantics of L ext is specified in Table 2 . These rules are largely standard following the convention in programming language literature. In particular, each rule's name starts with S-indicating that they are semantics rules; the suffixes indicate the constructors each rule specifies, (e.g., Stmt for statements, Seq for sequences, etc. 

s 0 = I; (2) B 0 = P ; (3) B i , s i → B i+1 , s i+1 for i = 0, ..., T -1; and (4) B T = ⊥. The output of the program is O = s T .

3.2. EXECUTION-GUIDED SYNTHESIS ALGORITHM:

In Definition 1, we can observe that the initial and final states are simply two special states provided as the input-output examples of the synthesis problem. Thus, a synthesizer Γ for input-output pairs should also be able to take any state-pairs as inputs. Our execution-guided synthesis algorithm takes advantage of this fact to improve the performance of the synthesizer. In the following, we discuss three cases from the easiest to the hardest to present our approach.

Sequential programs. We now consider the simplest case, where the program is in the form of S 1 ; ...; S T , to illustrate the basic idea of execution-guided synthesis algorithm. We present the algorithm in Algorithm 1. Assuming the input-output examples are {IO K }, we can treat them as

K state-pairs {(s k i , s k o )} K k=1 , where s k i = I k , s k o = O k .

The Exec algorithm takes the synthesizer Γ and the input-output pairs {IO K } as its input. It also takes an additional input ∆, which is the ending token to be synthesized. For the top-level program, ∆ will be the ⊥ token. Later we will see that when synthesizing the sub-program for If-and While-blocks, different ending tokens will be used.

The synthesized program is initially empty (line 3). Then the algorithm iteratively generates one statement S at a time (line 4-10 and 17), and appends it to the end of P (line 16). Importantly, if S is not an if-statement or a while-statement, for which we handle separately, the algorithm executes the newly generated statement S to transit s k i into s k new (line 11-14). Therefore, in the subsequent iteration, the synthesizer can start from the new states s k new after executing the partial program P Algorithm 1 Execution-guided synthesis (sequential case)

1: function EXEC(Γ, {(s k i , s k o )} K k=1 , ∆) 2:

// The main algorithm is called using Exec (Γ, {IO K }, ⊥)

3: P ← ⊥ 4: S ← Γ({(s k i , s k o )} K k=1 ) 5: while S = ∆ do 6: if S = if -token then // If-statement synthesis 7: S, {(s k i , s k o )} K k=1 ← ExecIf(Γ, {(s k i , s k o )} K k=1 ) 8:

else 9:

if S = while-token then // While-statement synthesis 10: C ← Γ(I) 3:

S, {(s k i , s k o )} K k=1 ← ExecWhile(Γ, {(s k i , s k o )} K k=1 ) 11: else // Execution of S 12: S, s k i → ⊥, s k new for k = 1, ..., K 13: s k i ← s k new for k = 1, ...,

I t ← {(s i , s o ) ∈ I| C, s i ⇓ true} 4: I f ← {(s i , s o ) ∈ I| C, s i ⇓ false} 5: B t ← Exec(Γ, I t , else-token) 6: B f ← Exec(Γ, I f , fi-token) 7: I t ← {(s new , s o )|(s i , s o ) ∈ I t ∧ B t , s i ⇓ s new } 8: I f ← {(s new , s o )|(s i , s o ) ∈ I f ∧ B f , s i ⇓ s new } 9: I ← I t ∪ I f 10: S ← if C then B t else B f fi 11:

return S, I 12: end function generated so far. In doing so, the synthesizer can see all intermediate states to better adjust the followup synthesis strategies to improve the overall synthesis performance.

Branching programs. Dealing with if-statements is slightly more complicated than sequential programs, since in an if-statement, not all statements will be executed on all inputs. Following the execution in Algorithm 1 naively, we have to use Γ to synthesize the entire if-statement before being able to execute the partially generated program to derive intermediate states.

Therefore, in Algorithm 2, we extend the above idea to handle if-statements. When the next predicted token is an if -token, our execution-guided synthesizer first predicts the condition of the if-statement C (line 2). Then, we evaluate C over all state-pairs. Based on the evaluation results, we can divide the IO pairs into two sets I t and I f (line 3-4), so that all states in the former meet the branching condition to go to the true branch, and all states in the latter go to the false branch. Therefore, in the followup synthesis, we do not need to consider I f (or I t ) when synthesizing the true branch (or the false branch) (line 5-6). Note that in line 5-6, synthesizing both true-branch and false-branch employ execution-guided synthesis algorithm to leverage intermediate states, and different ending tokens (i.e., else and fi) are supplied respectively. Once we have done the synthesis of both branches, we can execute the generated branches to get the new states I (line 7-9), and return the newly generated if-statement and updated states to the caller of this algorithm.

In Algorithm 2, we use B, s ⇓ s to indicate a big-step execution of code block B over state s to get s . In particular, this means that B, s → B 1 , s 1 → ... → ⊥, s .

Looping programs. The remaining problem is to handle while-statements. Due to the rule S-While (see Table 2 ), a while-statement while

C do B end (1) is equivalent to if C then (B; while C do B end) else ⊥ fi (2)

Therefore, we can employ a procedure similar to Algorithm 2 once a while-token is predicted. However, there are two differences. First, in (2), the false-branch is empty, thus we do not need to deal with the false-branch. Second, although the true-branch is B; while C do B end, once we have generated B, we do not need to generate the rest of the true-branch, since both C and B have been generated. The detailed algorithm can be found in Appendix B.

Remarks. The final algorithm is called by Exec (Γ, {IO K }, ⊥). Note that our execution-guided synthesis algorithm can be applied to any neural synthesizer Γ, and we can train the synthesizer Γ using any supervised or reinforcement learning algorithms that have been proposed before (Devlin et al., 2017b; Bunel et al., 2018) . In our evaluation, we demonstrate that our execution-guided synthesis technique helps boost the performance of both supervised and reinforcement learning algorithms proposed in existing work (Bunel et al., 2018) .

4. SYNTHESIZER ENSEMBLE:

In our experiments, we observe that when we use different random initializations of the synthesizer during training, even if the synthesizer architectures are the same, they will be effective on different subsets of the dataset, although the overall prediction accuracy is similar to each other. Thus, a natural idea is to train multiple synthesizers, and ensemble them to build a more performant synthesizer.

Different from other deep learning tasks, for program synthesis task, without knowing the ground truth, we can already filter out those wrong predictions that cannot satisfy the input-output specification. Thus, we ensemble multiple synthesizers as follows: we run all synthesizers to obtain multiple programs, and select from programs that are consistent with all input-output examples. This provides us with a better chance to select the correct final prediction that generalizes to held-out IO pairs.

The main subtlety of such an approach is to deal with the case when multiple generated programs satisfy the input-output examples. In this work, we consider several alternatives as follows:

• Majority vote. We can choose the most frequently predicted program as the final prediction.

• Shortest. Following the Occam's razor principle, we can choose the shortest program as the final prediction.

5. EVALUATION:

In this section, we demonstrate the effectiveness of our approaches on the Karel dataset (Pattis, 1981; Bunel et al., 2018) . We first introduce the task, discuss the experimental details, and present the results.

5.1. THE KAREL TASK:

Karel is an educational programming language proposed in the 1980s (Pattis, 1981) . Using this language, we can control a robot to move inside a 2D grid world and modify the world state, and our goal is to synthesize a program given a small number of input and output grids as the specification. Such tasks have been used in Stanford CS introductory courses (CS106A, 2018) and the Hour of Code (HoC, 2018), and have been studied recently in several neural program synthesis works (Devlin et al., 2017a; Bunel et al., 2018; Shin et al., 2018) . Figure 2 shows an example in the Karel domain.

We provide the grammar specification and the state representation in Appendix A. In particular, the (Bunel et al., 2018) and this work, "SL" and "RL" to indicate supervised learning and reinforcement learning respectively. In the "Ensemble" column, dash indicates that no ensemble is used, "S" and "MV" indicate the shortest and majority vote principles respectively. For the single model accuracy, we report the results of the model with the best generalization accuracy. We include 15 models in each ensemble.

Karel DSL includes control flow constructs such as conditionals and loops, which is more challenging than problems well-studied before, such as FlashFill (Gulwani, 2011; Devlin et al., 2017b) .

Our evaluation follows the setup in (Bunel et al., 2018) . We train and evaluate our approaches on their dataset, which is built by randomly sampling programs from the DSL. For each program, 5 IO pairs serve as the specification, and the sixth one is the held-out test sample. In total, there are 1,116,854 programs for training, 2,500 in the validation set, and 2,500 in the test set. We evaluate the following two metrics, which are the same as in (Bunel et al., 2018) :

• Exact Match. The predicted program is an exact match if it is the same as the ground truth.

• Generalization. The predicted program is a generalization if it satisfies the input-output examples in both the specification and the held-out examples.

Training dataset construction for the Exec algorithm. Note that the original Karel dataset only provides the input-output examples and the ground truth programs. To train the synthesizer Γ with our Exec algorithm in the supervised learning setting, we need the supervision on intermediate states as well, which can be obtained easily by executing the ground truth programs following the semantics (Table 2 ). In particular, for each sample {IO K }, P in the original training set, we construct a sequence of training samples {(s k i-1 , O k )} Ki k=1 , S i (i = 1, 2, ..., T ), with each sample containing K i ≤ K state pairs and a program S i ∈ P . The algorithm to construct this set is largely analogous to the semantics specification, and we defer the details to Appendix B.

Training algorithms. Once the training set is constructed, the neural synthesizer Γ can be trained on this new dataset using the same algorithm as the one for training Γ on the original dataset. Therefore, our Exec algorithm can be applied to both supervised learning and reinforcement learning algorithms proposed in (Bunel et al., 2018) for evaluation.

Model details. We employ the same neural network architecture as in (Bunel et al., 2018) to synthesize the programs, which is briefly discussed in Section 2.2. During the inference time, we set the beam size B = 64, and select the one with the highest prediction probability from the remaining programs. More details can be found in Appendix C.

5.2. RESULTS:

We present our main results in Table 3 . We report the results of ensembling 15 models for our ensemble techniques. For reference, we include MLE and RL results in (Bunel et al., 2018) , which were the state-of-the-art on the Karel task for the exact match and generalization metrics respectively. We first apply our ensemble techniques to these approaches, and observe that the performance could be significantly boosted by around 7%.

We next observe that our execution-guided synthesis alone can significantly improve the generalization accuracy over all approaches from (Bunel et al., 2018) , even after we accompany their approaches with our ensemble techniques. In particular, without the ensemble, "Exec+SL" already improves "MLE+RL" by 8 points on generalization accuracy; and when ensemble approaches are applied to "MLE+RL", this gap is shrunk, but still positive. Similar to (Bunel et al., 2018) , we can also train our Exec model using the RL technique, which improves the generalization accuracy by another 1 point, while slightly decreases the exact match accuracy. These results show that utilizing intermediate execution states alone is already an effective approach to boost the performance.

Note that the improvement of Exec on the exact match accuracy is relatively minor, and sometimes negative when applying the ensemble to baseline training algorithms. This is because our Exec algorithm is not designed to optimize for exact match accuracy. In particular, we decouple the full programs in the original training dataset into small pieces, thus our synthesizer Γ is trained with segments of the original training programs instead of the full programs. In doing so, our synthesizer is more capable of generating programs piece-by-piece and thus tends to generate semantically correct programs (i.e., with a better generalization accuracy) rather than the same programs in the training and testing sets (i.e., with a better exact match accuracy). In fact, for real-world applications, the generalization accuracy is more important than the exact match accuracy, because exact match accuracy is more about evaluating how well the synthesizer recovers the language model of the pCFG sampler used to generate the dataset. More discussion can be found in Appendix D.1.

Finally, we apply our ensemble approaches on top of Exec+SL and Exec+RL. We observe that this can further improve the generalization accuracy and exact match accuracy by around 6% on top of the best single model. These results show that our ensemble approaches consistently boost the performance, regardless of the underlying models used for ensembling.

In addition, we investigate the performance of ensembling different number of models. We present the results of ensembling Exec + RL models in Figure 3 , and defer the results of ensembling Exec models to Appendix D.2. We observe that using the shortest principle is generally more effective than using the majority vote principle, especially when fewer number of models are included in the ensemble. However, when there are more models, majority vote may achieve a better generalization accuracy than the shortest principle. This is reasonable, since when there are too few models, there might not be enough effective models to form the majority.

Interestingly, we observe that Exec+RL+Ensemble does not significantly improve the performance over Exec+SL+Ensemble. This may be due to that the improvement from ensemble hides the improvement from RL. More discussion of our evaluation results can be found in Appendix D.

To summarize, we make the following key observations: 1. Our execution-guided synthesis technique can effectively improve previous approaches, which only use the syntactic information, or the final program execution outputs.

2. Our ensemble approaches can effectively improve the performance regardless of the underlying models being used.

3. The different modules of our proposed approaches, i.e., execution-guided synthesis and ensemble techniques, can work independently to improve the performance, and thus they can be applied independently to other tasks as well.

4. By combining all our novel techniques, we improve the state-of-the-art on the Karel task by 14.88 points (generalization) and 7.14 points (exact match).

6. RELATED WORK:

Synthesizing a program from input-output examples is an important challenging problem with many applications (Devlin et al., 2017b; Gulwani et al., 2012; Gulwani, 2011; Bunel et al., 2018; Chen et al., 2018; Cai et al., 2017; Li et al., 2017; Reed & De Freitas, 2016; Zaremba et al., 2016; Zaremba & Sutskever, 2015; Fox et al., 2018; Xiao et al., 2018; Ganin et al., 2018) . There has been an emerging interest in studying neural networks for program synthesis. A line of work studies training a neural network to directly generate the outputs given the inputs (Devlin et al., 2017b; a; Graves et al., 2014; Joulin & Mikolov, 2015; Kaiser & Sutskever, 2015) . In particular, Devlin et al. study the Karel domain (Devlin et al., 2017a) . However, as shown in (Devlin et al., 2017a) , this approach is incapable of handling the case when the number of input-output examples is small, and is hard to generalize to unseen inputs.

Recent work study using neural networks to generate programs in a domain-specific language (DSL) from a few input-output examples (Devlin et al., 2017b; Bunel et al., 2018; Parisotto et al., 2017; Polosukhin & Skidanov, 2018; Zohar & Wolf, 2018) . Several work synthesize programs for FlashFill tasks, which are in the string transformation domain (Devlin et al., 2017b; Parisotto et al., 2017) .

Other work synthesize programs in a LISP-style DSL for array manipulation (Polosukhin & Skidanov, 2018; Zohar & Wolf, 2018) . In particular, Zohar & Wolf (2018) also study the idea of encoding the state of the transformed inputs as it is updated during execution. However, these DSLs only include sequential programs, and do not support more complex control flows such as loops and conditionals in our studied Karel problem. Prior works also consider incorporating syntax constraints and information from program execution to facilitate program synthesis (Devlin et al., 2017b; Wang et al., 2018a; Bunel et al., 2018) . However, all these works generate the whole program, and use its execution results to guide the synthesis process; in contrast, our work leverages more fine-grained yet generic semantic information that can be gathered during executing programs in most imperative languages. As a result, our approach's performance is significantly better than previous work (Bunel et al., 2018) .

Previous work also study program synthesis given intermediate states. For example, Sun et al. (2018) propose to synthesize the program from demonstration videos, which can be viewed as sequences of states. In such a problem, all intermediate states can be extracted from the videos. On the contrary, in the input-output program synthesis problem studied in our work, the input to the program synthesizer provides only the initial state and the final state. Thus, our synthesizer is required to address the challenge of inferring intermediate states, which is mainly tackled by our execution-guided synthesis algorithm.

In contrast to training a neural network to generate the entire program, a recent line of research studies using a neural network to guide the symbolic program search based on the input-output specification, so that the search process prioritizes the operators that have higher domain-specific scores predicted by the neural networks (Balog et al., 2017; Vijayakumar et al., 2018) . Instead of predicting such domain-specific scores to guide the program search, we directly incorporate the domain knowledge by executing partial programs, and utilize the execution results for program generation of the neural network synthesizer. Meanwhile, recent work propose to leverage the full execution traces in the context of program repair (Wang et al., 2018b) . Our work is the first to leverage partial execution traces for the program synthesis task, which is a much harder task than program repair.

7. CONCLUSION:

In this work, we propose two general and principled techniques to better leverage the semantic information for neural program synthesis: (1) execution-guided synthesis; and (2) synthesizer ensemble. On a rich DSL with complex control flows, we achieve a significant performance gain over the existing work, which demonstrates that utilizing the semantic information is crucial in boosting the performance of neural program synthesis approaches. We believe that our techniques are also beneficial to other program generation applications, and we consider extending our techniques to handle programming languages with richer semantics as important future work. At the same time, we have observed that utilizing existing reinforcement learning techniques does not provide much performance gain when combined with our approaches. We believe that there is plenty of room left for further improvement, and we are also interested in exploring this problem in the future.

Algorithm 3 Execution-guided synthesis (while-statement)

1: function EXECWHILE(Γ, I)

2:

C ← Γ(I)

3:

I t ← {(s i , s o ) ∈ I| C, s i ⇓ true} 4: I f ← {(s i , s o ) ∈ I| C, s i ⇓ false} 5:

B t ← Exec(Γ, I t , end-token)

6:

I t ← {(s new , s o )|(s i , s o ) ∈ I t ∧ B t , s i ⇓ s new } 7: I ← I t ∪ I f 8: S ← while C do B t end 9:

return S, I 10: end function

C MODEL DETAILS:

C.1 NEURAL NETWORK ARCHITECTURE Our neural network architecture can be found in Figure 1 , which follows the design in Bunel et al. (2018) . In particular, the IO Encoder is a convolutional neural network to encode the input and output grids, which outputs a 512-dimensional vector for each input-output pair. The decoder is a 2-layer LSTM with a hidden size of 256. The embedding size of the program tokens is 256.

Each program is represented as a sequence of tokens G = [g 1 , g 2 , ..., g L ], where each program token g i belongs to a vocabulary Σ. At each timestep t, the decoder LSTM generates a program token g t conditioned on both the input-output pair and the previous program token g t-1 , thus the input dimension is 768. Each IO pair is fed into the LSTM individually, and we a max-pooling operation is performed over the hidden states {h t } K k=1 of the last layer of LSTM for all IO pairs. The resulted 256-dimensional vector is fed into a softmax layer to obtain a prediction probability distribution over all the 52 possible program tokens in the vocabulary.

Notice that this neural network architecture can also be applied to other program synthesis problems, with modifications of the IO encoder architectures for different formats of input-output pairs. For example, in the domain where input-output examples are text strings, such as FlashFill (Gulwani, 2011) , the IO encoders can be recurrent neural networks (RNNs) (Devlin et al., 2017b) .

C.2 TRAINING OBJECTIVE FUNCTIONS:

To estimate the parameters θ of the neural network, we first perform supervised learning to maximize the conditional log-likelihood of the referenced programs (Parisotto et al., 2017; Devlin et al., 2017b; Bunel et al., 2018) . In particular, we estimate θ * such that

EQUATION

Where π i are the ground truth programs provided in the training set.

When training with reinforcement learning, we leverage the policy gradient algorithm REIN-FORCE (Williams, 1992) to solve the following objective:

EQUATION

Where R i (G) is the reward function to represent the quality of the sampled program G. In our evaluation, we set R i (G) = 1 if G gives the correct outputs for given inputs, and R i (G) = 0 otherwise. In our evaluation, we observe that while our Exec approach significantly boosts the generalization accuracy, the performance gain of the exact match accuracy is much smaller, and sometimes even negative. We attribute this to the fact that the ground truth program in the Karel benchmark is not always the simplest one satisfying the input-output examples; on the other hand, our approach tends to provide short predictions among all programs consistent with the input-output specification. For example, Figure 5 shows a predicted program that is simpler than the ground truth, while also satisfies the input-output pairs. Notice that different from the MLE approach in (Bunel et al., 2018) 5 , it is more common for the ground truth program to be a single "move()" statement than other more complicated ones. Therefore, when training with our approach, the model is less prone to overfitting to the sample distribution of the original dataset, and focuses more on the program semantics captured by the intermediate execution.

D.2 MORE DETAILS OF THE ENSEMBLE:

For different training approaches of a single model, we train 15 models with different random initializations. To do the ensemble, we first sort the 15 models according to the descending order of their generalization accuracies on the validation set, then select the first k models to compute the results of the k-model ensemble. When multiple programs satisfy the ensemble criterion, e.g., with the shortest length for the Shortest method, we choose the one from the models with better generalization accuracies on the validation set.

Figure 6 shows the results of the ensemble trained with our Exec approach. Tables 5 and 6 show the numerical results of applying ensemble to our Exec approach and Exec + RL approach. 

:



Figures and Tables:

Figure 2: An example of the execution of partial programs to reach the target state in the Karel domain. The blue dot denotes the marker put by the Karel robot.

). The judgment B, s → B , s indicates a small-step execution of program B over state s to result in a new program B and a new state s . The judgments S, s ⇓ s and C, s ⇓ b capture the big-step execution in L that statement S evaluates to a new state s from s, and condition C evaluates to a boolean value b from s. Following the semantics of L ext , we can formally define a program execution. Definition 1 (Program execution) Given a program P ∈ L ext and an input I, the execution is a sequence s 0 ...s T , such that (1)

Figure 3: Results of the ensemble model trained with Exec + RL approach. Left: generalization accuracy. Right: exact match accuracy. The corresponding figures using models trained with Exec approach can be found in Appendix D.2.

Figure 5: An example of the predicted program that generalizes to all input-output examples, but is different from the ground truth. Here, we only include 2 out of 5 input-output examples for simplicity. Notice that the predicted program is simpler than the ground truth.

Figure 6: Results of the ensemble model trained with our Exec approach. Left: generalization accuracy. Right: exact match accuracy.

K

Table content: <table><tr><td>14:</td><td>end if</td></tr><tr><td>15:</td><td>end if</td></tr><tr><td>16:</td><td>P ← P ; S</td></tr><tr><td>17: 18:</td><td>S ← Γ({(s k i , s k o )} K k=1 ) end while</td></tr><tr><td>19:</td><td>return P</td></tr><tr><td colspan="2">20: end function</td></tr><tr><td colspan="2">Algorithm 2 Execution-guided synthesis (if-statement)</td></tr></table>

Accuracy on the Karel test set. In the "Training"column, we use "MLE" and "Exec" to indicate the training approaches proposed in

Table content: <table><tr><td>Training</td><td colspan="3">Ensemble Generalization Exact Match</td><td>From</td></tr><tr><td/><td>-</td><td>71.91%</td><td>39.94%</td><td>Bunel et al. (2018)</td></tr><tr><td>SL</td><td>S</td><td>78.80%</td><td>46.68%</td><td>This work</td></tr><tr><td>MLE</td><td>MV -</td><td>78.80% 77.12%</td><td>47.08% 32.17%</td><td>This work Bunel et al. (2018)</td></tr><tr><td>RL</td><td>S</td><td>84.84%</td><td>46.04%</td><td>This work</td></tr><tr><td/><td>MV</td><td>84.16%</td><td>46.36%</td><td>This work</td></tr><tr><td/><td>-</td><td>85.08%</td><td>40.88%</td><td/></tr><tr><td>SL</td><td>S</td><td>91.60%</td><td>45.84%</td><td/></tr><tr><td>Exec</td><td>MV -</td><td>91.52% 86.04%</td><td>45.36% 39.40%</td><td>This work</td></tr><tr><td>RL</td><td>S</td><td>91.68%</td><td>46.36%</td><td/></tr><tr><td/><td>MV</td><td>92.00%</td><td>45.64%</td><td/></tr></table>

, our model is not directly optimized for the exact match accuracy, since the training set not only includes the input-output examples in the original training set, but also the intermediate state pairs, which constitute a larger part of our augmented training set. Meanwhile, in our training set, for state pairs resembling {(s k 1 , s k 2 )} K k=1 in Figure

Table content: <table/>

24% 41.36% 41.52% 41.96% 41.76% 42.64% 43.12% 43.48% 43.56% 43.92% 44.44% 44.80% 45.32% 45.36% Exec + RL (S) 39.40% 42.80% 43.56% 43.84% 44.32% 44.96% 45.16% 45.44% 45.52% 46.36% 46.24% 46.04% 46.28% 46.16% 46.04% Exec + RL (MV) 39.40% 40.76% 41.56% 42.92% 42.84% 43.84% 43.68% 44.36% 44.48% 44.60% 45.24% 45.52% 45.48% 45.64% 45.64%

Table content: <table><tr><td>Ensemble</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td></tr><tr><td>Exec (S)</td><td colspan="15">40.88% 42.16% 42.64% 43.12% 43.00% 43.36% 44.32% 44.64% 44.72% 45.64% 45.32% 45.60% 45.52% 45.92% 45.84%</td></tr><tr><td>Exec (MV)</td><td colspan="2">40.88% 41.</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Exact match accuracy of the ensemble.

Table content: <table><tr><td>Ensemble</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td></tr><tr><td>Exec (S)</td><td colspan="15">85.08% 86.44% 87.04% 87.52% 87.76% 88.20% 89.04% 89.72% 90.16% 90.28% 90.68% 91.16% 91.44% 91.40% 91.60%</td></tr><tr><td>Exec (MV)</td><td colspan="15">85.08% 86.08% 86.84% 87.36% 87.72% 87.84% 88.68% 89.36% 89.80% 90.00% 90.44% 91.12% 91.48% 91.40% 91.52%</td></tr><tr><td>Exec + RL (S)</td><td colspan="15">86.04% 87.20% 88.64% 89.40% 89.64% 90.24% 90.32% 90.44% 90.48% 90.60% 90.96% 91.24% 91.32% 91.64% 91.68%</td></tr><tr><td colspan="16">Exec + RL (MV) 86.04% 86.88% 88.24% 89.16% 89.20% 90.04% 90.08% 90.20% 90.56% 90.68% 91.28% 91.48% 91.76% 91.96% 92.00%</td></tr></table>

Generalization accuracy of the ensemble.

Table content: <table/>

Peer review (iclr2019):
 This paper proposes guiding program synthesis with information from partial/incomplete program execution. The idea is that by executing partial programs, synthesizers can obtain the information of the state the (partial) program ended in and can, therefore, condition the next step on that (intermediate) state. The paper also mentions ensembling synthesizers to achieve a higher score, and by doing that it outperforms the current state-of-the-art on the Karel dataset program synthesis task. In general, I like the idea of guiding synthesis with intermediate executions, and the evaluation in the paper shows this does make sense, and it outperforms the SOTA. The idea is original and the evaluation shows it is significant (enough). However, I have two major concerns with the paper, its presented contribution, and the clarity. First, I cannot accept ensembling as a contribution to this paper. There is nothing novel about the ensemble proposed, and ensembling, as a standard method that pushes models that extra few percentage points, is present in a lot of other research. I have nothing against achieving SOTA results with it, while at the same time showing that the best performing model outperforms previous SOTA, which this paper orderly does. However, I cannot accept non-novel ensembling as a contribution of the paper. Second, the clarity of the paper should be substantially improved: - my main issue is that it is not clear how the Exec algorithm (see next point too) is trained. From what I understand Exec is trained on supervised data via MLE. What is the supervised data here? Given the generality claims and the formulation in Algorithm 1/2, and possible ways one could use the execution information, as well as the fact that the model should be end-to-end trainable via MLE, it seems to me that the model is trained on prefixes (defined by Algorithm 1/2) of programs. Whether this is correct or not, please provide full details on how one can train Exec without using RL. - By looking at Table 3, it seems that the generalization boost coming from Exec (I’m ignoring ensembling) is higher enough, and that’s great. However, it’s obvious that the exact match gain by Exec is minute, implying that the proposed algorithm albeit great on the generalization metric, does not improve the exact match at all. Do you have any idea why is that? Is that because Exec is trained via MLE and the Exec algorithm doesn’t add anything new to the training procedure? - how do algorithm 1 and 2 exactly relate? I guess there is a meaning of ellipses in Lines 1 and 13, however, that is not mentioned anywhere. Is the mixture of algorithm 1 and 2 (and a non-presented algorithm for while loops) the Exec algorithm? How exactly are these algorithms joined, i.e what is the final algorithm? - while on one side, I find some formalizations (problem definitions, definition 1, semantic rules in table 2) nicely done, I do not see their necessity nor big gains from them. In my opinion, the understanding of the rest of the paper does not depend on them, and they are well-described in the text. - the paper says that the algorithm “helps boost the performance of different existing training algorithms”, however, it does so only on the Bunel et al model (and the MLE baseline in it), and albeit there’s mention of the generality, it has not been shown on anything other than those two models and the Karel dataset. - do lines 6-7 in Algorithm 2 recurse? Does the model support arbitrarily nested loops/if statements? - The claim that the shortest principle is most effective is supported by 2 data points, without any information on the variance of the prediction/dependence on the seed. Did you observe this for #models > 10 too? Up to what number? - In table 3, is Exec on MLE? Could you please, for completeness, present the results of Exec + RL + ensemble in the table too? - summarization, point 3 - what are the different modules mentioned here? Exec/RL/ensemble? Minor issues, remarks, typos: - table 1 position is very unfortunate - figure 1 is not self-explanatory - it takes quite a lot of space to explain the network architecture, yet it fails to deliver meaning to parts of it (e.g. what is h_t^x, why is it max-pooled, what is g_t, etc) - abstract & introduction - “Reducing error rate around 60%” absolute percentage points seem like a better evaluation measure (that the paper does use). Why is the error rate reduction necessary here? - figure 2 - why is the marker in one of the corners, and not in the cell itself? - Algorithm 1, step 4, is this here just as initialization, so S is non-empty to start with? - Table 2 rule names are unclear (e.g. S-Seq-Bot ?) - Table 3 mentions what Exec indicates twice