Neural Program Synthesis By Self-Learning
Authors: Yifan Xu
Lu Dai
Udaikaran Singh
Kening Zhang
Zhuowen Tu
Venue:  (2020)
Keywords: Neural Program Synthesis
Reinforcement Learning
Deep learning
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. 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.

Under review as a conference paper at ICLR 2020
NEURAL PROGRAM SYNTHESIS BY SELF-LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Neural inductive program synthesis is a task generating instructions that can pro- duce desired outputs from given inputs. In this paper, 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 neural program synthesis algorithm, AutoAssem- blet, 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 tech- nique to alleviate online update correlations. We apply AutoAssemblet to basic programming tasks and show significant higher success rates compared to several competing baselines.
INTRODUCTION
Program synthesis an emerging task with various potential applications such as data wrangling, code refactoring, and code optimization (Gulwani et al.) (017). Much progress has been made in the field with the development of methods along the vein of neural progrum 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 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 Katser & 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 general- purpose program synthesis including data scalability and language suitability. We will briefly de- scribe 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 the success of pro- gram 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 pro- cess. 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 scale-labeled data. Collecting non-trivial human- human-written programs/code with task specifications can be expensive, especially 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 efficient data collection procedure explore the program space.
methods is often built on the top of large-
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 topic of study (Balog et al. 2017
Desai al. 2016), but it has limited

---

Under review as a conference paper at ICLR 2020
domain of application. Here, focus subset of x86 assembly language, which is executed on CPU with RAM access.
Our Work. We develop neural program synthesis algorithm, AntoAssemblet, to explore the large- scale code space efficiently via self-learning under the reinforcement learning (RL) framework. During the RL data collection period, re-weight the sampling probability of tasks based on the model's '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) BBrowne et al.) 2012). This allows our model to solve more complex problems with over 22d 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 trajec- tories reach the target output. Empirically, we find that RL policy network training unsatisfactory by receiving low rewards. This the result strong correlations of online RL updates, which lead to non-stationary distribution of observed data (Mnih et al. 2016) Volodymyr et al. (013). 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 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 pro- cess perform assembly program synthesis.
2. Devise simple multi-entropy policy sampling strategy reduce the update correlations.
3. Develop AutoAssemblet for generating assembly code for 32-bit x86 processors and RAM.
2 RELATED WORK
We first provide 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 a searching process to produce program matching the behavior with the demonstrated input-output example pairs (Ba- log et al. 2017). Given enough training examples, typical IPS model first searches for potential matching programs, followed by picking the best solution using ranking mechanism. (Balog et al., 2017) focuses mainly the search part of the algorithm.
Neural IPS Recent progress has been made for neural inductive program synthesis (Menon et al. 2013 Parisotto al. 2016 [allg 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 space exploration 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. (0133) learns from small dataset collected by humans, which hard to scale in practice. While query language in [Balog et al. (0017) can potentially yield millions of programs to train deep networks, the data generation process done by enumerating search strategies without learning a priority. Our model instead efficiently explores considerably large space by using self-learning reinforcement learning strategy.
;) Kalyan et al. (2018) focuses query languages with high-level functions like FILTER and MAP. Gulwani (201 is practically working application used in string programming setting. Hayati 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 al. 2018). In this paper,
Representations of Program State Balog et al. (017));
2

---

Under review as a conference paper at ICLR 2020
Training Pipeline
Update
Policy Nettockk
Vale
Networka
a: lTc
V:
CPU
Input
Task Pool
Sampling
Output
R
Self-Learning
b. MCTS Process
1. Selection
2. Espansion
3. Evaluation
4. Backup
V. Regiowr
Regitar
Vv
Iur
Regitai
Tepineer
Fam
Regidwrr
Ran
Th
Negiserr Iumn
Rain
V+
Fagooer tam
Regirter
Regiotrr
Fart
Fam
Figure 1: Self-Learning Reinforcement Learning AutoAssemblet: a. Training Pipeline composed of self-Learning and with re-adjustment of sampling strategy b. Monte Carlo Tree Scarch(MCTS) searches for best policy by utilizing policy networks and value networks.
we provide a different paradigm for Neural IPS by using a subset of x86 instruction set, which generates 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 prescribed format, which suitable for neural networks observe the correlation.
AUTOASSEMBLET
In this section, first reformulate program synthesis task RL problem and introduce neces- sary 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 illustrated in Algorithm
3.1 TASK SAMPLING
We train our model following pipeline consisting of several stages. Initially, we create millions of pilot programs X, by executing some initial policies Tp. We then construct input-output 10 pairs by running Ap x86 simulator the actual value stored in the CPU registers and the RAM.
initial task pool. In our setting, input I and output O represent
During the training process, 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 f that can produce a program Ag with consistent behavior given one set of input-output pairs:
xo(1)) - WE Vk I..K.
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. record the success rate for
To motivate networks to learn more diverse program distribution. each task sampled from the pool, which is used to maintain a multinomial distribution. The network gets sample from the tasks fails complete more often, and the easy tasks will not be prioritized.
3

---

Under review as a conference paper at ICLR 2020
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 based on a state representation S(,,0), St in short, each time step t. During the process, 4++1 is generated by x86 simulator by executing based on previous state I, Program terminates at time step T when either output O is reached (Ir O) or maximum steps have been proceeded. The terminal step will receive reward r(sr) such that r(sT) = if the output O is reached, and r(ST) 0 otherwise. All previous states will receive a decayed reward r = -=""""-((8 accordingly. collect (r, pairs for all N sampled task.
During training, we observe that on- on-policy updates have a high correlation, which converge to non-stationary process. Various off--olliy methods proposed to alleviate this problem, including storing previous data in a replay buffer and asynchronously executing multiple agents (Riedmiller) 2003 Schulman et al. 2015 Mnih al. 2016). However, program synthesis can be regarded as a meta-task where a new task is proposed to solved at each time. Storing previous experience done in other tasks updating asynchronously doesn't 't show clear advantage. We take alternative approach where temperature r 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 by default. A higher leads to softer probability distribution, and lower т shifts the distribution towards ooee like distribution (Hinton al., (015). The change of temperature reduces the correlation among samples by flexibly altering sampling distribution, which conceptually similar off- off-policy sampling techniques discussed above.
3.3 POLICY NETWORKS TRAINING
Imitation Learning
We first train our model to imitate programs A generated by pilot policy Tp which is used to construct input-output /0 task pairs. Different from imitation learning that collects human behavior, Ap is not necessary as good as expert demonstrations. For examples, sub 3 following odd 4 can be optimized add 1. Therefore, we expect the quality of X, decreases for longer programs. However, pilot policy Tp is useful to guide policy training and provide Ty 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 Tp(s) conditioned on given inputs:
(i) - EST. log mo(a (8())))8)))
Policy Gradient
While imitation learning duplicates predictions faithful the target output from Ap. 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 supervised model with the policy gradient technique to optimize outcome directly:
(m) -IE -.L..
Σ T-
(((T))))
log mo(a,(s))
t=1
t=
To take advantage of both side, we combine Lim and Cyt as a hybrid objective, where À decays with the training process:
Lhybria (0) L.r(()) + XLim (0)
4

---

Under review as a conference paper at ICLR 2020
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), usually cannot reach the terminal state when looking head due to poor policy performance and the depth limitation. To estimate the expected value under given policy иæ. we train a value function & directly predict discounted outcomes would be received for given state:
T
(()) = -E -Es
((T)) (s()))
(5)
3.5 SEARCHING WITH POLICY AND VALUE NETWORKS
Once trained, we combine policy networks and value networks with a Monte Carlo Tree Search (MCTS) provide a look-ahead search. Policy network is used 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
general steps: 1) Selection. MCTS starts from root state S, (also as current state Sc) and searches for the first available non-expanded leaf state St unless the terminal state S. is found. If the leaf node is found, MCTS will proceed expansion step. Otherwise, it picks current node S. from lists of based four factors: state reward R., its visit time No. its parent visit time Pa and exploration factor
St = arg max Re/No + EV 2.)g(P.)/N. S.c(S.)
(6)
2) Expansion. After MCTS decides which state S. to be expanded, it applies policy network (o(als))) to sample one action from hypothesis distribution, and proceeds to Sc+1. A good pol- icy network can significantly boost search tree efficiency by reducing the necessary breadth of the expansion. 3) Evaluation. We use the same policy
our rollout policy to search terminal state S, from node S.+1 under & maximum step. target state not reached due to code error or maxi- mum step is reached, we use value function V (s;) to estimate terminal state's 's future outcome. 4) Backup. The result of the rollout process used to update reward for the nodes on the path from S. to Sp.
Algorithm AutoAssemblet Training Process
1: Require: policy network कe; value network Va; task pool S = 81, 8x where s& is constructed by input state I, and output state O at time step I; list of policy temperature Ti.....
2: Initialize the task weighting coefficients (wv) setting ws 0 for k 1,...
3: while AutoAssemblet has not converged do
4: PA= Softmar (wr) // Multi- Enttriy Policy Sampling
5: Sample a batch of tasks Sg = $1, ..., from task pool S based on {
6: for à in M do
7: Collect (st, at, r+) pairs based on policy network
=
8:
We +- we + (-1) (=}((1))0) Update weighting coefficients
9:
end for
10:
Update by Eq.
// Policy Networks Training
11: Update V4 by Eq.
Value Networks Training
12:
end while
4 EXPERIMENTS
In this section, we describe the results from two categories experiments. the first set of exper- iments, demonstrate how AutoAssemblet may improve upon the performance achieved through only imitation learning or REINFORCE. In the second set of experiments, we demonstrate the per- formance of AutoAssemblet on human-designed program benchmarks comparing other baselines.
5

---

Under review as a conference paper at ICLR 2020
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 (heaz, %ebr, %ecr, %edx ) and 4 main data transfer / in- leger instructions (addl, subl, movl, imull), 10 digit numbers, and optionally 4 RAM positions (-0(%rbp)) -7(rrbp), -8(6rbp)) 12(66rb)) )
Observation Space The observation space the networks look at is the current values in CPU register and RAM well 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 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 task. Since the code length is fixed, the unrolled RNN can significantly increase the training speed. Our value networks mainly consist of two parts: task encoder and 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 dyper-parameter of using 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.
eitdon
Intuzon Dun
0.355
0.6
2.5
0053
Vood Addieee
22
3) NNNutber Tasks
Number Registers
0) Difficult
d) Number
Figure 2: Performance comparison under four experiments setting
Increase of search difficulty. In our first experiment shown in Figure 24), 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 AutoAssembler model shows more robust improvements with high data efficiency.
Additionally, Figure (D), 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 2 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.
6

---

Under review as a conference paper at ICLR 2020
Figure 2 demonstrates that neural network's performance decreases when adding more input- output 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 single inputouutuu 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 seems to remove this ambiguity for more instances within the training data.
4.3 HUMAN-DESIGNE PROGRAMMING CHALLENGES
Previously, we trained the neural network on self-explored tasks generated by the pilot policy. In this experiment, we designed a of human-designed tasks to test potentials solve meaningful programming tasks. As 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 their level of abstraction. Within the easy task set, we have the tasks addition, subtraction, multiplication of registers, and finding the minimum and maximum values. Within the medium task set, have the tasks of moving the value of register to another register location, adding and subtracting a value larger than 10, and adding a constant to all registers. Adding subtracting value greater than ten may be difficult because this a state that neural network rarely experienced during training. Lastly, the hard task set includes high-level abstraction, such 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.
Model
Imitation
REINFORCE
MCTS(PV)
AutoAssemblet (Ours)
EASY
SUCCESS RATE
60%
64%
63%
59%
AVE STEPS
2.7
3.1
2.5
2.9
MEDIUM
SUCCESS RATE
25%
29%
35%
37%
AVE STEPS
4.5
7.5
9.2
6.9
HARD
SUCCESS RATE
2%
5%
5%
10%
AVE STEPS
13.1
12.4
13
12.5
TOTAL
SUCCESS RATE
34.4%
38.2%
40.2%
40.4% %
Table 1: Results Hlman--Designed Programming Challenges. Details tasks designed each difficulty
level is explained at A.I
The similar performance between the model learned from imitation learning and REINFORCE flects the limitations of only using a policy network for code generation, and thus suggests that improvement come from the use of value function.
Our model performs better than all baseline models with an over 20% overall improvement over the nearest models. As seen in table]] I our model achieved a higher accuracy for test set within different difficulty level.
DISCUSSION
5.1 WHAT AUTOASSEMBLET LEARNED FROM NETWORKS
In this section, we highlight set of programs generated by AutoAssemblet to solve the human- designed tasks we created. These examples illustrate the model's ability to create low-level code that is interpretable by human and to find shorteuts of the problems.
First, the model can leam a continuous representation of number system, so can learn simple algebra to switch sequence of number to another sequence. Second, for those digits not frequently seen training data (which only appears sparsely), the model learns to approach the value with more efficient operation (such multiplication). and to finetune the value by add subtract small

---

Under review as a conference paper at ICLR 2020
value get the exact target. Third, the mapping between register and value is also learned by the model. 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 imput is originally stored in RAM, and the target is only about transforming the values in RAM. As simple problem, the network learns 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:
Description:
Algebra: imull $eax, $ecx addl $2, tecx
Input:
The task is add 30 to the third register. It tests the model's abil- ity to perform simple arithmetic. Instead of addition, the model utilizes multiplication.
[5, 1, 7, 8]
[4, 3, 7,
Output:
[5, 1, 37,
[4, 3, 30, 0]
MAP:
Input-output example:
Description:
addl $1, 8ebx
Input:
The goal is to add 1 to each register, which would show up in a human-made program of iteration.
addl $1, Sedx
[8, 1, 0,
addl $1, teax
[2, 4, 5, 7]
addl $2, tecx
Output:
subl $0, $ecx
19, 2, 1, 8]
subl $1, $ecx
[3, 5, 6, 8]
Filter: subl $1, Secx
Input-output example:
Description:
Input:
Filters out the values less than and sets them to -1.
subl $2, $eax
[1,5, 0, 2] [1, 8, 0,
addl $4, $edx
subl $4, 8edx
Ouipuf:
addl $4, Sedx
[-1, 5, 11,1,, -1]
[-1 -1,-11
Sort:
Input-output example:
Description:
addl $4, $ebx
Ippu::
Sort the variables in the list and return. Sorting is highly dependent on the input, therefore we only sort single list of inputs.
subl $4, $eax
[5, 1, 7, 8]
Outpul:
[1, 5, 7, 81
8

---

Under review as a conference paper at ICLR 2020
Load/Store Memory: movl -8 (&rbp), subl $3, movl $ebx, -4 ($rbp)
Input-output example:
Description:
tebx tebx
Input:
Load variable from RAM, add it with number, and store it to RAM again.
CPU: [0, 0, 0, 0]
RAM: [2, 8, 0, 1]
CPU: [0, 0, 0, 0]
RAM: [6, 5, 4, 9]
Ouiput:
CPU: [0, -3, 0, 0]
RAM: [2, -3, 0, 1]
CPU: [0, 1, 0, 0]
RAM: [6, 1, 4, 9]
Input-output exampee::
Summation:
Input: [e, 1,
addl $3, $edx
addl $4, $ebx
Description:
[7, 4, 3, 1,,4,3,31
subl $4, 8ebx addl 8ebx, Redx addl 8eax, 8edx
Find the summation of the regis- ters and set the value as the final register in the input.
Ouiput: [0, 10,1,,66 61
[7, 4, 7,4,3,14, 4,14,3,14]
5.2 LIMITATIONS AND FUTURE DIRECTIONS
However, limitations still remain. One major issue is that we prohibit the model to use control- flow instructions. Many challenging tasks can be easily solved with loop and if statement. Our network decides next instruction only by observing current and target machine states. There is no sufficient mechanism 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 control- flow instructions into our setting. Besides,the abuse of if-else clauses can also hampers extraction of general methods to solve task, because agent can be cheated in 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 bounded certain stack or heap positions in assembly language. The agent needs to know which position accessible avoid stack-overflow and segmentation fault, and which variable is available in current scope to avoid getting out-dated value of This problem is especially important in solving tasks with variables needs long-term usage. variable management mechanism should also be introduced to apply accurate operations on variables and to protect the prohibited area in RAM and registers.
CONCLUSION
We have presented a neural program synthesis algorithm. AutoAssemblet, for generating a segment of assembly code to execute state change 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, points to a promising direction for program synthesis, if properly formulated, to learn to code scale.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018.
M Balog, AL Gaunt, M Brockschmidt, S Nowozin, and D Tarlow. Deepcoder: Learning write programs, In International Conference on Learning Representations (ICLR 2017). OpenReview.
net, 2017.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. International Conference on Learning Representutions, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guider neural program synthesis. 2018.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Subhajit Roy, et al. Program symthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering, pp. 345-356. ACM, 2016.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint urXiv:1400.544 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using neural network with dynamic external memory. Nature, 538 (,66)):411,201..
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In ACM Sigplan Notices, volume 46, pp. 317-330. ACM, 2011.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, al. Program synthesis. Foundations and Trends in Programming Languages, 4(1-2):1-119, 2017.
Shirley Anugrah Hayati, Raphael Olivier, Pravalika Avvaru, Pengcheng Yin, Anthony Tomasic, and Graham Neubig. Retrieval-baat neural code generation. In Proceedings of the 2018 Conference on Empiricul Methods Natural Language Processing, pp. 925-930, 2018
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint trXiv:1503.02533 2015.
Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in newral information processing systems, pp. 190-198, 2015.
Eukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv: 2015.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gul- wani. Neural-guided deductive search for real-time program synthesis from examples. In Inter- national Conference on Learning Representations, 2018.
Neel Kant. Recent advances in neural program synthesis. arXiv preprint arXiv: 10X::.180..02333, 2018
Karol Kurach, Marcin Andrychowicz. and Ilya Sutskever. Neural random random-access access machines. arXiv preprint arXiv: 10.111/11...39 2015.
10

---

Under review as a conference paper at ICLR 2020
Aditya Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Kalai. A machine learn- ing framework for programming by example. In International Conference on Machine Learning, pp. 187-195, 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. 2016.
Scott Reed and Nando De Freitas. arXiv:1511.06279, 2015.
Neural programmer-imeeppeter.. arXiv preprint
Martin Riedmiller. Neural fitted q iteration-first experiences with data efficient neural reinforce- ment learning method. In European Conference on Machine Learning, pp. 317-328. Springer, 2005.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
Tom Shanley, x86 Instruction Set Architecture. MindShare press, 2010.
Mnih Volodymyr, Koray Kavukcuoglu, David Silver, Alex Graves, and loannis Antonoglou. Playing atari with deep reinforcement learning. In NIPS Deep Learning Workshop. 2013.
Pengcheng Yin and Graham Neubig. syntactic neural model for general-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 440-450, 2017.
A APPENDIX
A.1 TASK DESCRIPTION
Description of human-designed programming tasks:
Easy:
1) Summing 2 registers (setting sum value @ first register) (10 tasks)
2) Summing 4 registers (setting sum value @ first register) (10 tasks)
3) mapping: adding to all registers (10 tasks)
4) subtract 15 from second index (10 tasks)
5) add 10 first index (10 tasks)
6) 51-100 50 generated examples of I-line code (10 tasks)
Medium:
1) Adding prior registers (add to register value from register i-1) (10 tasks)
2) subtracting prior registers (10 tasks)
3) maximum value (to first register) (10 tasks)
4) minimum value (to first register) (10 tasks)
5) switching 1st and 4th register (10 tasks)
6) 51-100: generated examples of 1-line code
Hard:
1) Filtering (keep value above 5, set others to 0) (10 tasks)
2) sorting (4 registers)(10 tasks)
3) reversing registers (10 tasks)
4) mapping: register value for rest of registers (10 tasks)
5) mapping: adding +i for ith register (10 tasks)

---

Under review as a conference paper at ICLR 2020
A.2 DATASET DISCRIPTION
We designed experiment settings of different variable:
1. Number of tasks. We use 4 dataset, with 10000, 100000, 200000, 300000 tasks respectively.
Default other parameters are registers, operations, 10 numbers, 3 lines of program.
Lines of program. We use 4 dataset, with 2, 3, 4. 5 lines of program respectively. Default other parameters are 4 registers, 4 operations, 10 numbers, 300000 tasks.
Number of examples per task. We use dataset, with 1, 2, 3, 4, 5 pairs of examples per task
respectively. Default other parameters are 4 registers, 4 operations, 10 numbers, 300000 tasks.
Number of registers. We use dataset, with 1, 2, 3, registers respectively. Default other parameters are 300000 tasks, 4 operations, 10 numbers.
12


Reviews:
[{"review_id": "rylmwZrCFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary] \nThis 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.\n\nSignificance: are the results significant? 2/5\nNovelty: are the problems or approaches novel? 2/5\nEvaluation: are claims well-supported by theoretical analysis or experimental results? 4/5\nClarity: is the paper well-organized and clearly written? 4/5\n\n[Strengths]\n\n*clarity*\nThe 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. \n\n*technical contribution*\n- Optimizing both the imitation learning loss and the reinforcement learning loss yields better performance when more tasks are available and tasks are more difficult.\n- Leveraging a learned policy network and value network for improving the efficiency of the MCTS seems effective.\n\n*ablation study*\nAblation 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.\n\n*experimental results*\n- All the descriptions of the experiments and the presentations of the results are fairly clear. \n- The results demonstrate the effectiveness of the proposed RL guided MCTS.\n\n[Weaknesses]\n\n*novelty*\nOverall, I do not find enough novelty from any aspects while the overall effort of this paper is appreciated. The reasons are as follows.\n- 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). \n- 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.\n- 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. \n- Program synthesis on assembly languages: RISC-V [6], etc.\n\n*related work*\nThe 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. \n\n*baselines*\nIn my opinion, the baselines (imitation, REINFORCE, MCTS) presented in the paper are far from comprehensive. I believe the following baselines should also be considered:\n- 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.\n- Search-based program synthesis baseline (i.e. learning guided search vs heuristic search)\n- 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].\n\n*testing set*\nThe 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\".\n\n*number of given I/O pairs*\nIt 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). \n- 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.\n- 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.\n\n[1] \"RobustFill: Neural Program Learning under Noisy I/O\" in ICML 2017\n[2] \"Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis\" in ICLR 2018\n[3] \"Reinforcement and Imitation Learning for Diverse Visuomotor Skills\" in RSS 2018\n[4] \"DeepMimic: Example-Guided Deep Reinforcement Learning of Physics-Based Character Skills\" in SIGGRAPH 2018\n[5] \"Learning to Infer Graphics Programs from Hand-Drawn Images\" in NeurIPS 2018\n[6] \"Program Synthesis Through Reinforcement Learning Guided Tree Search\" arXiv 2018\n[7] \"Neural Program Synthesis from Diverse Demonstration Videos\" in ICML 2019\n[8] \"Execution-Guided Neural Program Synthesis\" in ICLR 2019\n[9] \"Learning to Describe Scenes with Programs\" in ICLR 2019\n[10] \"Learning to Infer and Execute 3D Shape Programs\" in ICLR 2019\n\n===== After rebuttal =====\n\nI appreciate the authors for the revision and for clarifying some points. I am still not entirely convinced by the response and the revision.\n\nFirst, I mentioned several papers that are related to this work, the authors failed to discuss the difference between this submission and these works. \n- 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.\n- While the proposed hybrid objective is very similar to the one proposed in [2, 3, 4], the revision does not mention this.\n- 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.\n- 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.\nI 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.\n\nSecond, 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?\n\nThe 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.\n\nFrom 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.\n\nOverall, I believe this submission requires a serious revision and I firmly recommend this paper to be rejected.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HkldANPAYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to tackle the problem of neural inductive program synthesis using a combination of REINFORCE, imitation learning, and MCTS. Furthermore, they propose a method for sampling tasks that aims at minimising task correlation when optimizing the policy parameters. They test their method on a set of input-output sequences provided by automatically generated x86 programs, and a small set of manually designed programs.\n\n\nGiven the current state of the manuscript, this is a clear reject. Some of the main issues I notice are:\n\n1. The novelty of the proposed (combined) method is unclear, given that it is a relatively straightforward combination of relatively simple and battle-tested techniques; I don't consider this in general to be a problem, but previous work has explored the problem way more significantly both algorithmically and in modeling terms.\n\n2. The experimental section is entirely composed of non-standard datasets, and - in general - the manuscript lacks almost entirely in critical details regarding how the datasets are generated; e.g. What is the pilot policy? Is there a finite set of IO tasks defined for all the experiments? How were the manual tasks designed? What are the qualitative differences in task dynamics between the two experiment settings?\n\n3. The baselines are extremely basic, especially considering that there are a multitude of papers - some of which are mentioned in sections 1 and 2 - that would provide for some excellent comparison. Furthermore, there's a lack of details about the model setup, hyperparameters, state featurization, and so on.\n\n4. Across the manuscript there seems to be some apparent confusion on whether they are tackling the problem as a multi-task setting, where each IO set is considered to be a separate task, or whether all of these tasks are just instances of a single MDP. Given that the program space is well defined, I would think that modelling the problem as a single task is more appropriate, however the authors seem to have chosen a multi-task approach. However, in such case there's also a lot of previous work on multi-task RL and meta-learning that should have been mentioned and potentially used / compared against. This also affects how sensible their proposed sampling method is (and whether the assumption wrt on-policyness actually is reasonable).\n\nI would encourage the authors to improve the work in the following ways:\n- Please include the nitty gritty details about the setup, including dataset, simulator, training and algorithmic hyperparameters, state featurization, etc. - try to make experimental reproduction as easy as possible exclusively based on the manuscript.\n- Clarify the setup wrt. point 4 above; ideally formalize the problem statement using MDPs, such that it can be properly reasoned upon.\n- Review more closely previous work, and choose a suitable (and possibly recent and as close to SOTA as reasonably possible) baseline, such that the proposed methods can be quantitatively and qualitatively compared.\n- Similarly, please attempt to test your method on existing environments and datasets, such that any analysis against previous baselines can be fairly assessed.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkg42vUycH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tackles the problem of program synthesis in a subset of x86 machine code from input-output examples. First, the paper uses a random code generation policy to generate many programs and executes them with random inputs to obtain I/O and program pairs. Then, the paper trains a model using imitation learning on this dataset, and then transitions to to using policy gradient and Monte Carlo Tree Search methods to train the network.\n\nI thought it was quite cool that the paper generates assembly code, but the set of instructions allowed is quite limited. While the paper seems a bit dismissive about prior work such as Balog et al 2017 that use \"query languages\", the higher-level primitives found in such languages (like \"filter\") could also mean that the models involved have to learn higher-level semantics than what this model needs.\n\nFurthermore, the paper only uses two input-output examples to specify the desired behavior, and the accuracy of the model's output is only evaluated on that pair of examples. While the paper discusses in Section 5.2 that it is important to learn general methods to solve a provided task, this evaluation setting prevents . Similar to previous work like Bunel et al 2018, I would encourage the authors to measure how well the generated programs can do on held-out example input-output pairs, to see whether the model could successfully recover the \"intended\" program; to assist with this, we can also increase the number of input-output pairs used to specify the task. Of course, this would make it probably impossible to recover the \"hard\" problems from section 4.3, since those require conditional execution.\n\nI think the paper should have cited works such as\n- https://arxiv.org/abs/1906.04604\n- https://openreview.net/forum?id=H1gfOiAqYm\n- https://papers.nips.cc/paper/8107-improving-neural-program-synthesis-with-inferred-execution-traces\nwhich also make use of execution information in order to predict the code. In particular, the first paper in this list also uses tree search methods to generate programs as a sequence of loop and branch-free instructions, so I believe it should be quite similar to this paper at a high level.\n\nConsidering the above limitations with the evaluation methodology, and the limited novelty of this work in light of these citations, I vote for weak reject.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider the problem of program induction from input-output pairs.                                                     
They propose an approach based on a combination of imitation learning from                                                         
an auto-curriculum for policy and value functions and alpha-go style tree search.                                                   
It is a applied to inducing assembly programs and compared to ablation                                                             
baselines.                                                                                                                         
                                                                                                                                   
This paper is below acceptance threshold, based on the reviews and my own                                                          
reading.                                                                                                                           
The main points of concern are a lack of novelty (the proposed approach is                                                         
similar to previously published approaches in program synthesis), missing                                                          
references to prior work and a lack of baselines for the experiments.
Decision: Reject