Title: NEURAL PROGRAM SYNTHESIS BY SELF-LEARNING

Abstract: Neural inductive program synthesis is a task generating instructions that can produce desired outputs from given inputs. In this paper, we focus on the generation of a chunk of assembly code that can be executed to match a state change inside the CPU and RAM. We develop a neural program synthesis algorithm, AutoAssemblet, learned via self-learning reinforcement learning that explores the large code space efficiently. Policy networks and value networks are learned to reduce the breadth and depth of the Monte Carlo Tree Search, resulting in better synthesis performance. We also propose an effective multi-entropy policy sampling technique to alleviate online update correlations. We apply AutoAssemblet to basic programming tasks and show significant higher success rates compared to several competing baselines.

1. INTRODUCTION:

Program synthesis is an emerging task with various potential applications such as data wrangling, code refactoring, and code optimization (Gulwani et al., 2017) . Much progress has been made in the field with the development of methods along the vein of neural program synthesis (Parisotto et al., 2016; Balog et al., 2017; Bunel et al., 2018; Hayati et al., 2018; Desai et al., 2016; Yin & Neubig, 2017; Kant, 2018) . Neural program synthesis models build on the top of neural network architectures to synthesize human-readable programs that match desired executions. Notice that neural program synthesis is different from neural program induction approaches in which neural architectures are learned to replicate the behavior of the desired program (Graves et al., 2014; Joulin & Mikolov, 2015; Kurach et al., 2015; Graves et al., 2016; Reed & De Freitas, 2015; Kaiser & Sutskever, 2015) .

The program synthesis task consists of two main challenges: 1). intractability of the program space and 2). diversity of the user intent (Gulwani et al., 2017) . Additional difficulties arise from generalpurpose program synthesis including data scalability and language suitability. We will briefly describe these challenges below.

Program Space. The program synthesis process consists of sequences of code with combinatorial possibilities. The number of possible programs can grow exponentially with the increase of the depth of the search and the breath of hypothesis space.

User Intent. To interpret and encode user's intention precisely is essential to the success of program synthesis. While writing formal logical definition is usually as hard as defining the program itself, natural language descriptions nevertheless introduce human bias and ambiguity into the process. Our work here focuses on Inductive Program Synthesis approach where input-output pairs are demonstrated as a program task specification.

Scale of Data. The success of recent neural-network-based methods is often built on the top of largescale-labeled data. Collecting non-trivial human-written programs/code with task specifications can be expensive, especially a large degree of diversity in the code is demanded. An alternative is to exhaust the entire program space, but it is difficult to scale up without taking exploration priority. We instead show an efficient data collection procedure to explore the program space.

Choice of Language. The choice of the programming language is also very important. High-level languages like Python and C are powerful but they can be very abstract. Methods like abstract syntax tree (AST) (Hayati et al., 2018) exist but a general solution is still absent. The query language has also been chosen as a topic of study (Balog et al., 2017; Desai et al., 2016) , but it has a limited domain of application. Here, we focus on a subset of x86 assembly language, which is executed on CPU with RAM access.

Our Work. We develop a neural program synthesis algorithm, AutoAssemblet, to explore the largescale code space efficiently via self-learning under the reinforcement learning (RL) framework. During the RL data collection period, we re-weight the sampling probability of tasks based on the model's past performance. The re-weighting sampling distribution encourages the networks to explore challenging and novel tasks. During the network training period, the deep neural networks learn policy function to reduce the breath of the search and the value function to reduce the depth of the search. The networks are integrated with Monte Carlo Tree Search (MCTS), resulting in better performance (Coulom, 2006; Browne et al., 2012) . This allows our model to solve more complex problems with over 22 3 hypothesis space done in 10 steps, while the previous related works considered searching 34 output choices finished in 5 steps (Balog et al., 2017) .

The reward for the program synthesis task in RL is very sparse, where usually only very few trajectories reach the target output. Empirically, we find that RL policy network training unsatisfactory by receiving low rewards. This is the result of strong correlations of online RL updates, which lead to non-stationary distribution of observed data (Mnih et al., 2016; Volodymyr et al., 2013) . In this paper, we propose a conceptually simple multi-entropy policy sampling technique that reduces the updating correlations.

Since our algorithm can learn from its trails without human knowledge, it avoids the data scalability problem. We test its performance on human-designed programming challenges and observe higher success rates comparing to several baselines. This paper makes the following contributions:

1. Adapt self-learning reinforcement learning into the neural inductive program synthesis process to perform assembly program synthesis. 2. Devise a simple multi-entropy policy sampling strategy to reduce the update correlations. 3. Develop AutoAssemblet for generating assembly code for 32-bit x86 processors and RAM.

2. RELATED WORK:

We first provide a brief overview of the Inductive Program Synthesis (IPS) literature. Then, we discuss related works along several directions.

Inductive Program Synthesis (IPS) views the program synthesis task as a searching process to produce a program matching the behavior with the demonstrated input-output example pairs (Balog et al., 2017) . Given enough training examples, a typical IPS model first searches for potential matching programs, followed by picking the best solution using a ranking mechanism. (Balog et al., 2017) focuses mainly on the search part of the algorithm.

Neural IPS Recent progress has been made for neural inductive program synthesis (Menon et al., 2013; Parisotto et al., 2016; Balog et al., 2017; Kalyan et al., 2018) . When performing the task in this way, a network learns a probability distribution over the code space to guide the search for matching the given input-output pairs. Despite the observation of promising results, challenges remain in neural program synthesis for e.g. effectively exploring the code space. Usually, such a space exploration is carried out by collecting human-labeled data or performing an enumerate search over program space. Our main difference to the existing method is in the data generation procedures. Menon et al. (2013) learns from a small dataset collected by humans, which is hard to scale in practice. While query language in Balog et al. (2017) can potentially yield millions of programs to train deep networks, the data generation process is done by enumerating search strategies without learning a priority. Our model instead efficiently explores a considerably large space by using a self-learning reinforcement learning strategy. Balog et al. (2017) ; Kalyan et al. (2018) focuses on query languages with high-level functions like FILTER and MAP. Gulwani (2011) is a practically working application used in a string programming setting. Hayati et al. (2018) synthesizes high-level source code from natural language. Recently, Graph Neural Networks are seen as a potential solution to encoding complex data structure for high-level languages (Allamanis et al., 2018) we provide a different paradigm for Neural IPS by using a subset of x86 instruction set, which generates a program in low-level assembly language. x86 instruction set is widely used in modern computers (Shanley, 2010) . Ensemble language sythesis is also studied in Chen et al. (2018) . A direct advantage is that the algorithm can synthesize program and receive the reward in the x86 simulator environment. Another advantage is x86 operations directly operate in CPU and RAM in a prescribed format, which is suitable for neural networks to observe the correlation.

Representations of Program State:



3. AUTOASSEMBLET:

In this section, we first reformulate program synthesis task as an RL problem and introduce necessary notations. Then, we describe the task sampling and multi-entropy policy sampling strategies in the data collection process. Following that, we explain the training procedure of policy and value networks. Finally, we illustrate how Monte Carlo Tree Search utilizes policy networks and value networks during search stage. The full procedure is illustrated in Algorithm 1.

3.1. TASK SAMPLING:

We train our model following a pipeline consisting of several stages. Initially, we create millions of pilot programs λ p by executing some initial policies π p . We then construct input-output IO pairs by running λ p on x86 simulator as our initial task pool. In our setting, input I and output O represent the actual value stored in the CPU registers and the RAM.

During the training process, we assume N programming tasks are sampled from the task pool; each consists of a set of K input-output pairs. Our goal is to learn a neural network θ that can produce a program λ θ with a consistent behavior given one set of input-output pairs:

λ θ (I k i ) = O k i ∀i ∈ 1..N, ∀k ∈ 1..K.

(1) Empirically, we find that sampling from the task pool uniformly leads RL policy networks to overfit easy tasks by giving up difficult tasks with no positive reward, resulting in performance decreasing. To motivate networks to learn a more diverse program distribution, we record the success rate for each task sampled from the pool, which is used to maintain a multinomial distribution. The network gets to sample from the tasks it fails to complete more often, and the easy tasks will not be prioritized.

3.2. MULTI-ENTROPY POLICY SAMPLING:

The first stage of RL training is the data collection process. For each sampling task, the policy networks θ recursively synthesize next line of code a t based on a state representation s (It,O) , s t in short, at each time step t. During the process, I t+1 is generated by x86 simulator by executing a t based on previous state I t . Program terminates at time step T when either output O is reached (I T = O) or maximum steps have been proceeded. The terminal step will receive a reward r(s T ) such that r(s T ) = 1 if the output O is reached, and r(s T ) = 0 otherwise. All previous states will receive a decayed reward r t = γ T -t r(s T ) accordingly. We collect (s t , a t , r t ) pairs for all N sampled task.

During training, we observe that on-policy updates have a high correlation, which converge to a non-stationary process. Various off-policy methods are proposed to alleviate this problem, including storing previous data in a replay buffer and asynchronously executing multiple agents (Riedmiller, 2005; Schulman et al., 2015; Mnih et al., 2016) . However, program synthesis can be regarded as a meta-task where a new task is proposed to be solved at each time. Storing previous experience done in other tasks or updating asynchronously doesn't show clear advantage. We take an alternative approach where temperature τ in the softmax distribution is alternated. It allows us to synchronously execute multiple agents with different entropy distribution in parallel. In the softmax function, temperature τ is set to 1 by default. A higher τ leads to a softer probability distribution, and a lower τ shifts the distribution towards a one-hot-encoded like distribution (Hinton et al., 2015) . The change of temperature reduces the correlation among samples by flexibly altering sampling distribution, which is conceptually similar to off-policy sampling techniques discussed above.

3.3. POLICY NETWORKS TRAINING:



Imitation Learning:

We first train our model to imitate programs λ p generated by pilot policy π p , which is used to construct input-output IO task pairs. Different from imitation learning that collects human behavior, λ p is not necessary as good as expert demonstrations. For examples, sub 3 following add 4 can be optimized to add 1. Therefore, we expect the quality of λ p decreases for longer programs. However, pilot policy π p is useful to guide policy training and provide π θ with a stable initialization.

The imitation learning objective is simply obtained from cross-entropy. The networks is trained to make predictions that can maximize the likelihood of actions a from π p (s) conditioned on given inputs:

EQUATION

Policy Gradient While imitation learning duplicates predictions as faithful to the target output from λ p , it falls into the problem of program aliasing: maximizing the likelihood of a single program would penalize many equivalent correct programs, which hurts long-term program synthesis performance (Bunel et al., 2018) . Thus, we perform reinforcement learning on top of a supervised model with the policy gradient technique to optimize outcome directly:

EQUATION

To take advantage of both side, we combine L im and L rl as a hybrid objective, where λ decays with the training process:

EQUATION

3.4. VALUE NETWORKS TRAINING:

The final stage of the training pipeline is the state-value prediction. When performing long-term program synthesis with Monte Carlo Tree Search (MCTS), we usually cannot reach the terminal state when looking head due to poor policy performance and the depth limitation. To estimate the expected state value under given policy π θ , we train a value function φ to directly predict discounted outcomes would be received for given state: 

EQUATION

4. EXPERIMENTS:

In this section, we describe the results from two categories of experiments. In the first set of experiments, we demonstrate how AutoAssemblet may improve upon the performance achieved through only imitation learning or REINFORCE. In the second set of experiments, we demonstrate the performance of AutoAssemblet on human-designed program benchmarks comparing to other baselines.

4.1. EXPERIMENT SETUP:

Action Space The action space the network searches on is a reduced syntax of the x86 assembly language. We use 4 CPU registers (%eax, %ebx, %ecx, %edx ), and 4 main data transfer / integer instructions (addl, subl, movl, imull) , 10 digit numbers, and optionally 4 RAM positions (-0(%rbp), -4(%rbp), -8(%rbp), -12(%rbp) ).

Observation Space The observation space the networks look at is the current values in CPU register and RAM as well as target values. The network takes in the observation as input and generates the next line of code. During the training and searching process, the instruction is then compiled and executed by CPU (or a simulator of CPU) to get subsequent state.

Model Our policy networks mainly consist of two parts: a task encoder and a program decoder. The task encoder consists of an embedding layer and five fully-connected (FC) layers followed by tanh. The start state and target state pairs are concatenated and feed into the embedding layer. We implemented an unrolled RNN as the code generator. The generator receives a context vector from the previous FC network, which extracts information about a task. Since the code length is fixed, the unrolled RNN can significantly increase the training speed. Our value networks mainly consist of two parts: a task encoder and a value prediction layer. The task encoder shares the same architecture with the policy networks, and the value prediction layer is an additional FC layer followed by a sigmoid function. Potentially, the task encoder between policy networks and value networks can be shared.

4.2. PERFORMANCE COMPARISON:

We trained neural networks on different augmentations of the training process to demonstrate the success of our method in different settings. The hyper-parameters we tested were the size of the task pool, the lines of code in the training code, the size of the input-output set, and the number of registers. For all our experiments in this category, we used the default hyper-parameters of using a pair of instances in the input-output set, 3 lines of code, 4 registers, and 300,000 coding tasks. We compare our results with ones learned from imitation learning and REINFORCE. The prediction accuracy is evaluated on a hold-out validation set. Increase of search difficulty. In our first experiment shown in Figure 2a ), we evaluated our models on increasing task pool sizes and tested for the accuracy of the generated program. Notice, both results from imitation learning and REINFORCE drop after task pool scales larger. This is largely due to the policy learned by networks overfits to simple and redundant tasks. Our AutoAssemblet model shows more robust improvements with high data efficiency.

Additionally, in Figure 2b ), the search space is largely increased by the number of registers used, which leads to the sharp decrease in accuracy, but our model has the most gentle slope.

Increase of task difficulty. As our third experiment shown in Figure 2c ), we increase the task difficulty by increasing the number of steps pilot program used to generate input-outputs. For single step task, our model shows worse performance comparing to another two baselines, but it indicates significant higher accuracy when task challenge increases. We hypothesize that because the MCTS is unnecessary searching for a multi-line solution, thus not recognizing the simple single-line solution.

For tasks that generate from 5 steps, it boosts accuracy from 2% to 12% compare to imitation learning. This is because our model does not suffer from overfitting the memorization of the exact data pattern.

Figure 2d ) demonstrates that neural network's performance decreases when adding more inputoutput pairs to the training data. The results are more consistent after increasing to more than two input-output pairs. We hypothesize the reason for this is that having a single input-output pair makes the task of finding the mapping between the input and output ambiguous. For a single input-output pair, multiple high-level abstraction could solve such mapping. However, increasing the number of pairings to at least 2 seems to remove this ambiguity for more instances within the training data.

4.3. HUMAN-DESIGNED PROGRAMMING CHALLENGES:

Previously, we trained the neural network on self-explored tasks generated by the pilot policy. In this experiment, we designed a set of human-designed tasks to test its potentials to solve meaningful programming tasks. As a note, we create two input-output pairs per task to ensure that the network produces the desired program.

We divided the tasks into three categories based on their level of abstraction. Within the easy task set, we have the tasks of addition, subtraction, multiplication of registers, and finding the minimum and maximum values. Within the medium task set, we have the tasks of moving the value of a register to another register location, adding and subtracting a value larger than 10, and adding a constant to all registers. Adding or subtracting a value greater than ten may be difficult because this is a state that neural network rarely experienced during training. Lastly, the hard task set includes high-level abstraction, such as filtering, sorting, switching registers, and finding the two maximum or minimum values. Respectively, there are fifty, forty, forty human-designed tasks within the easy, medium, and hard test sets. The similar performance between the model learned from imitation learning and REINFORCE reflects the limitations of only using a policy network for code generation, and thus suggests that improvement can come from the use of a value function.

Our model performs better than all baseline models with an over 20% overall improvement over the nearest models. As seen in table 1, our model achieved a higher accuracy for test set within different difficulty level.

5. DISCUSSION:



5.1. WHAT AUTOASSEMBLET LEARNED FROM NETWORKS:

In this section, we highlight a set of programs generated by AutoAssemblet to solve the humandesigned tasks we created. These examples illustrate the model's ability to create low-level code that is interpretable by human and to find shortcuts of the problems.

First, the model can learn a continuous representation of number system, so it can learn simple algebra to switch a sequence of number to another sequence. Second, for those digits not frequently seen in training data (which only appears sparsely), the model learns to approach the value with more efficient operation (such as multiplication), and to finetune the value by add or subtract small value to get to the exact target. Third, the mapping between register name and value is also learned by the model. It knows which position should be changed and put the corresponding register name to generated instruction to achieve its goal, rather than changing digits randomly.

We also try the setting including RAM. The input is originally stored in RAM, and the target is only about transforming the values in RAM. As a simple problem, the network learns to first load the value to register, apply operations on it, and store it back to memory after the task is done. We present several demo programs below: Input-output example: Input: CPU:[0, 0, 0, 0] RAM: [2, 8, 0, 1] CPU:[0, 0, 0, 0] RAM: [6, 5, 4, 9] Output: CPU:[0, -3, 0, 0] RAM:[2, -3, 0, 1] CPU:[0, 1, 0, 0] RAM: [6, 1, 4, 9] Description: Load a variable from RAM, add it with a number, and store it to RAM again.

Algebra: imull %eax,

Summation::

addl $3, %edx addl $4, %ebx subl $4, %ebx addl %ebx, %edx addl %eax, %edx

Input-output example::

Input: [0,1, 3,2] [7,4,3,0] [4,4,3,3] Output: [0,1, 3,6] [7,4,3,14] [4,4,3,14] Description: Find the summation of the registers and set the value as the final register in the input.

5.2. LIMITATIONS AND FUTURE DIRECTIONS:

However, limitations still remain. One major issue is that we prohibit the model to use controlflow instructions. Many challenging tasks can be easily solved with a loop and if statement. Our network decides next instruction only by observing current and target machine states. There is no sufficient mechanism to step back to certain historical states to re-insert a branching clause into instruction flow. Thus an advanced global planning mechanism is necessary to introduce controlflow instructions into our setting. Besides,the abuse of if-else clauses can also hampers extraction of general methods to solve a task, because an agent can be cheated in a simple adversarial example: reduce any multi-instance based problem to one-instance problem by if-else clause and take trivial steps to solve each instance separately. Such limitation contradicts the original purpose of finding the universal method to solve all instances in the same task.

Another challenge is variable management. Variables in high-level language are bounded to certain stack or heap positions in assembly language. The agent needs to know which position is accessible to avoid stack-overflow and segmentation fault, and which variable is available in current scope to avoid getting out-dated value of it. This problem is especially important in solving tasks with variables needs long-term usage. A variable management mechanism should also be introduced to apply accurate operations on variables and to protect the prohibited area in RAM and registers.

6. CONCLUSION:

We have presented a neural program synthesis algorithm, AutoAssemblet, for generating a segment of assembly code to execute state change in the CPU and RAM. We overcome the limitations in the previous program synthesis literature by designing a self-learning strategy suitable for code generation learned via reinforcement learning. We adapt policy networks and value networks to reduce the breadth and depth of the Monte Carlo Tree Search. Applicability for AutoAssemblet using an effective reinforcement learning approach has been observed in our experiments, where a sequence of assembly codes can be successfully generated to execute the stage changes within the CPU. It points to a promising direction for program synthesis, if properly formulated, to learn to code at scale.

:



Figures and Tables:

a) Number of Tasks b) Number of Registers c) Difficulty of Tasks d) Number of I/O Pairs

Figure 2: Performance comparison under four experiments setting

. In this paper,

Table content: <table><tr><td>a. Training Pipeline</td><td/><td/><td colspan="2">Update</td><td/><td/><td/><td/><td/><td>0. 8</td></tr><tr><td/><td>Weighting Coefficients</td><td/><td>Input Input Input</td><td/><td>Policy Networks</td><td colspan="2">Value Networks</td><td>τ</td><td>ãτ</td><td>πτ τ</td><td>vτ τ</td><td>CPU</td></tr><tr><td>Task Pool</td><td>Sampling</td><td/><td colspan="2">Output Output Output</td><td/><td/><td/><td/><td/><td>RAM Simulator</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Sτ τ</td><td>Rτ τ</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">Self-Learning</td></tr><tr><td>b. MCTS Process</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">1. Selection</td><td colspan="3">2. Expansion</td><td colspan="3">3. Evaluation</td><td/><td colspan="2">4. Backup</td></tr><tr><td>Register Ram</td><td/><td/><td>Register Ram</td><td/><td/><td>Register Ram</td><td/><td/><td/><td>Vφ</td><td>Register Ram</td></tr><tr><td>Register Ram</td><td>Register Ram</td><td colspan="2">Register Ram</td><td>Register Ram</td><td colspan="2">Register Ram</td><td>Register Ram</td><td>Vφ</td><td/><td>Register Ram</td><td>Register Ram</td></tr><tr><td>Register Ram</td><td/><td>Register Ram</td><td>Register Ram</td><td>πθ π</td><td>Register Ram</td><td>Register Ram</td><td>Vφ</td><td colspan="2">Register Ram</td><td>Register Ram</td><td>Vφ</td></tr><tr><td/><td/><td/><td/><td/><td>πθ π</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>Register Ram</td><td>r</td><td/><td/><td>Register Ram</td><td>r</td></tr></table>

5)3.5 SEARCHING WITH POLICY AND VALUE NETWORKSOnce trained, we combine policy networks and value networks with a Monte Carlo Tree Search (MCTS) to provide a look-ahead search. Policy network is used to narrow down the breadth of the search to high-probability actions, while the value network is used to reduce the depth of the search with state value estimation.The MCTS method is composed of 4 general steps: 1) Selection. MCTS starts from root state S r (also as current state S c ) and searches for the first available non-expanded leaf state S l unless the terminal state S t is found. If the leaf node is found, MCTS will proceed expansion step. Otherwise, it picks new current node S c from lists of S l based on four factors: state reward R c , its visit time N c , its parent visit time P c and exploration factor . Initialize the task weighting coefficients {w k } by setting w k = 0 for k = 1, ..., K 3: while AutoAssemblet has not converged do

Table content: <table><tr><td/><td>S  *  c = arg max</td></tr><tr><td>4:</td><td>p k = Softmax (w k ) // Multi-Entropy Policy Sampling</td></tr><tr><td>5:</td><td>Sample a batch of tasks SB = s1, ..., sN from task pool S based on {p k }</td></tr><tr><td>6:</td><td>for i in M do</td></tr><tr><td>7: 8:</td><td>Collect (st, at, rt) pairs based on policy network π i θ w k ← w k + (-1) 1{π i θ (I k ) =O} // Update weighting coefficients</td></tr><tr><td>9:</td><td>end for</td></tr><tr><td>10:</td><td>Update π θ by Eq. (4) // Policy Networks Training</td></tr><tr><td>11:</td><td>Update V φ by Eq. (5) // Value Networks Training</td></tr><tr><td colspan="2">12: end while</td></tr></table>

Results of Human-Designed Programming Challenges. Details for tasks designed in each difficulty level is explained at A.1

Table content: <table><tr><td>Model</td><td colspan="4">Imitation REINFORCE MCTS(PV) AutoAssemblet (Ours)</td></tr><tr><td>EASY</td><td/><td/><td/><td/></tr><tr><td>SUCCESS RATE</td><td>60%</td><td>64%</td><td>63%</td><td>59%</td></tr><tr><td>AVE STEPS</td><td>2.7</td><td>3.1</td><td>2.5</td><td>2.9</td></tr><tr><td>MEDIUM</td><td/><td/><td/><td/></tr><tr><td>SUCCESS RATE</td><td>25%</td><td>29%</td><td>35%</td><td>37%</td></tr><tr><td>AVE STEPS</td><td>4.5</td><td>7.5</td><td>9.2</td><td>6.9</td></tr><tr><td>HARD</td><td/><td/><td/><td/></tr><tr><td>SUCCESS RATE</td><td>2%</td><td>5%</td><td>5%</td><td>10%</td></tr><tr><td>AVE STEPS</td><td>13.1</td><td>12.4</td><td>13</td><td>12.5</td></tr><tr><td>TOTAL</td><td/><td/><td/><td/></tr><tr><td>SUCCESS RATE</td><td>34.4%</td><td>38.2%</td><td>40.2%</td><td>40.4%</td></tr></table>

Peer review (iclr2020):
[Summary] This paper addresses the problem of synthesizing programs (x86 assembly code) from input/output (I/O) pairs. To this end, the paper proposes a framework (AutoAssemblet) that first learns a policy network and a value network using imitation learning (IL) and reinforcement learning (RL) and then leverages Monte Carlo Tree Search (MCTS) to infer programs. The experiments show that AutoAssemblet can synthesize assembly programs from I/O pairs to some extent. Ablation studies suggest the proposed IL and RL guided search is effective. Significance: are the results significant? 2/5 Novelty: are the problems or approaches novel? 2/5 Evaluation: are claims well-supported by theoretical analysis or experimental results? 4/5 Clarity: is the paper well-organized and clearly written? 4/5 [Strengths] *clarity* The overall writing is clear. The authors utilize figures well to illustrate the ideas. Figure 1 clearly shows the proposed pipeline as well as the MCTS process. In general, the notations and formulations are well-explained. *technical contribution* - Optimizing both the imitation learning loss and the reinforcement learning loss yields better performance when more tasks are available and tasks are more difficult. - Leveraging a learned policy network and value network for improving the efficiency of the MCTS seems effective. *ablation study* Ablation studies are comprehensive. The proposed framework first optimizes two losses (IL and RL) and leverages the learned policy network and the value network for improving MCTS. The provided ablation studies help analyze the effectiveness of each of them. *experimental results* - All the descriptions of the experiments and the presentations of the results are fairly clear. - The results demonstrate the effectiveness of the proposed RL guided MCTS. [Weaknesses] *novelty* Overall, I do not find enough novelty from any aspects while the overall effort of this paper is appreciated. The reasons are as follows. - This *self-learning* framework is not entirely novel since it has been proposed in [1], where the model is trained on a large number of programs that were randomly generated and tested on a real-world dataset (FlashFill). - The hybrid objective (IL+RL) has been explored in neural program synthesis [2] (a supervised learning model is fine-tuned using RL), learning robot manipulation [3], character control [4], etc. - Utilizing Monte Carlo Tree Search for program synthesis has been studied in many works. [5] proposes to treat the network outputs as proposals for a sequential Monte Carlo sampling scheme and [6] presents an RL guided Monte Carlo tree search framework. - Program synthesis on assembly languages: RISC-V [6], etc. *related work* The descriptions of the related work are not comprehensive. While many neural synthesis works [1, 5, 7-10] have explored a wide range of settings for learning to perform program synthesis, they are not mentioned in the paper. I suggest the authors conduct a comprehensive survey on this line of works. *baselines* In my opinion, the baselines (imitation, REINFORCE, MCTS) presented in the paper are far from comprehensive. I believe the following baselines should also be considered: - As the proposed model optimizes a combination of the IL loss and the RL loss, it would make sense to also evaluate a model optimizing this hybrid loss. - Search-based program synthesis baseline (i.e. learning guided search vs heuristic search) - Comparing the proposed framework against some neural induction baselines would confirm the importance and effectiveness of explicitly synthesizing programs instead of directly predicting the outcome/output. This has been shown in [1, 7]. *testing set* The testing sets are extremely small (with only 50, 40, 40 programs), which makes the results less convincing. Also, how those testing sets were created is not mentioned anywhere in the paper. It only states *we designed a set of human-designed tasks*. *number of given I/O pairs* It is not mentioned anywhere how the authors split the observed I/O pairs and the assessment I/O pairs such as what has been done in most of the works [1, 2, 7, 8]. While the observed I/O pairs are input to the program synthesis framework, the assessment I/O pairs are used to evaluate the synthesized programs. By doing so, the more observed I/O pairs are given, the more accurate the synthesized programs should be (assuming the model can find programs that fit the observed I/O pairs). - The discovery (Figure 2d) in this paper is contradictory to what is mentioned above: the program synthesis accuracy decreases when more I/O pairs are given. I am assuming the authors do not split observed I/O pairs and assessment I/O pairs. - With the setup where the observed I/O pairs are separated from the assessment I/O pairs, a larger number of K (the number of the observed I/O pairs) should be used so that it is more likely that the program for each task is unique and the evaluation would make more sense. [1] *RobustFill: Neural Program Learning under Noisy I/O* in ICML 2017 [2] *Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis* in ICLR 2018 [3] *Reinforcement and Imitation Learning for Diverse Visuomotor Skills* in RSS 2018 [4] *DeepMimic: Example-Guided Deep Reinforcement Learning of Physics-Based Character Skills* in SIGGRAPH 2018 [5] *Learning to Infer Graphics Programs from Hand-Drawn Images* in NeurIPS 2018 [6] *Program Synthesis Through Reinforcement Learning Guided Tree Search* arXiv 2018 [7] *Neural Program Synthesis from Diverse Demonstration Videos* in ICML 2019 [8] *Execution-Guided Neural Program Synthesis* in ICLR 2019 [9] *Learning to Describe Scenes with Programs* in ICLR 2019 [10] *Learning to Infer and Execute 3D Shape Programs* in ICLR 2019 ===== After rebuttal ===== I appreciate the authors for the revision and for clarifying some points. I am still not entirely convinced by the response and the revision. First, I mentioned several papers that are related to this work, the authors failed to discuss the difference between this submission and these works. - The *self-learning* paradigm is used in [1, 2, 7, 8] but [1, 7] are still not mentioned. If the authors intentionally ignore these works so that they can claim the novelty, it is not acceptable. - While the proposed hybrid objective is very similar to the one proposed in [2, 3, 4], the revision does not mention this. - Why [5, 6] that utilizing Monte Carlo Tree Search for program synthesis are still missing from the revision? I believe these works are very relevant to this submission. - The authors acknowledged that they did not know about [6] that works on program synthesis for an assembly language. Yet, this paper is still missing from the paper. I spent a lot of time conducting a survey in this field to help the authors to improve this submission and trying to identify the novelty of this submission. However, the authors just chose to ignore it, which is very disappointing. Second, many suggestions that I made are just rejected by the authors because they believe it is *not very easy and trivial*. Given this self-learning setting, I believe it would be easy to implement some program induction baselines using supervised learning. Or how about search-based program synthesis baselines? The writing about 50, 40, 40 testing sets is very misleading. I believe all the reviewers just think the testing accuracy was computed using those testing sets. From my point of view, *program aliasing” does not mean there are not sufficient I/O examples to fully describe a task; Instead, it means there are programs written differently can be semantically the same, which means no matter how many input examples are given, their outputs will always match. Overall, I believe this submission requires a serious revision and I firmly recommend this paper to be rejected.