Neural Program Synthesis with Query
Authors: Di Huang
Rui Zhang
Xing Hu
Xishan Zhang
Pengwei Jin
Nan Li
Zidong Du
Qi Guo
Yunji Chen
Venue: ICLR 2022 Poster (2022)

Abstract: Aiming to find a program satisfying the user intent given input-output examples, program synthesis has attracted increasing interest in the area of machine learning. Despite the promising performance of existing methods, most of their success comes from the privileged information of well-designed input-output examples. However, providing such input-output examples is unrealistic because it requires the users to have the ability to describe the underlying program with a few input-output examples under the training distribution. In this work, we propose a query-based framework that trains a query neural network to generate informative input-output examples automatically and interactively from a large query space. The quality of the query depends on the amount of the mutual information between the query and the corresponding program, which can guide the optimization of the query framework. To estimate the mutual information more accurately, we introduce the functional space (F-space) which models the relevance between the input-output examples and the programs in a differentiable way. We evaluate the effectiveness and generalization of the proposed query-based framework on the Karel task and the list processing task. Experimental results show that the query-based framework can generate informative input-output examples which achieve
and even outperform well-designed input-output examples.

Published as a conference paper at ICLR 2022
NEURAL PROGRAM SYNTHESIS WITH QUERY
Di Huangl24 1.2., Rui Zhang 1,4; Xing Hu! 14, Xishan Zhang 14, Pengwei Jin 1:24,
Nan Li Zidong Dul Qi Guo' & Yunji Chen 1.2
SKL of Computer Architecture, Institute of Computing Technology. CAS
University of Chinese Academy of Sciences
*University of Science and Technology of China
*Cambricon Technologies
ABSTRACT
Aiming to find a program satisfying the user intent given input-ouiput examples, program synthesis has attracted increasing interest in the area of machine learning. Despite the promising performance of existing methods, most of their success comes from the privileged information of well-designed input-output examples. However, providing such input-output examples is unrealistic because it requires the users to have the ability to describe the underlying program with a few input- output examples under the training distribution. In this work, we propose a query- based framework that trains a query neural network to generate informative input- output examples automatically and interactively from a large query space. The quality of the query depends on the amount of the mutual information between the query and the corresponding program, which can guide the optimization of the query framework. To estimate the mutual information more accurately, we introduce the functional space (F-space) which models the relevance between the input-output examples and the programs in differentiable way. We evaluate the effectiveness and generalization of the proposed query-baser framework on the Karel task and the list processing task. Experimental results show that the query- based framework can generate informative input-output examples which achieve and even outperform desl-des input-output examples.
INTRODUCTION
Program synthesis is the task of automatically finding program that satisfies the user intent ex- pressed in the form of some specifications like input-output examples (Gulwani et al., 2017). Re- cently, there has been an increasing interest in tackling it using neural networks in various domains, including string manipulation (Gulwani 201T Gulwani et al.] 2012] Devlin al. 2017b), list pro- cessing (Balog et al. 2017 Zohar& & Wolf 2018) and graphic applications (Ellis et al. 2018 2019).
Despite their promising performance, most of their success relies on the well-designed input-output examples, without which the performance of the program synthesis model drops heavily. For exam- ple, in Karel (Devlin et al., [0176] Bunel et al., 2018). the given input-output examples are required to have high branch coverage ratio the test program: In list processing, the given input-output examples are guided by constraint propagation (Balog et al., (017)) to ensure their effectiveness on the test program. However, providing such input-output examples is unrealistic because it requires the users to be experienced in programming to describe the underlying program with several input- output examples. Worse, the users must be familiar with the distribution of the training dataset to prevent themselves from providing out-of-distribution examples (Shin et al. 2019). In summary, how to generate informative input-output examples without expert experience is still an important problem that remains a challenge.
In this paper, we propose a query-based framework to automatically and efficiently generate infor- mative input-output examples from large space, which means that the underlying program can be easily distinguished with these examples. This framework consists of two parts: the query network
"Corresponding author. Contact: (huangdi20b, zhangrui) @ict.ac.en.

---

Published as a conference paper at ICLR 2022
def move D)
Interact
Generate
Embed
Synthesize
puttazker ()
Lus susatight move D)
User intent (program)
Query network
Input
Output
Synthesis network
Predicted program
Figure I:
The query-based framework. The query network generates informative input-output exam- ples by interacting with the user, and then the generated examples are sent to the synthesis network synthesize the underlying program.
and the synthesis network, and each part is trained separately. The query network trained to gen- erate the input-output examples in an iterative manner, and then the synthesis network is trained to synthesize the program with the input-output examples generated by the query network. It has three advantages: (1) There is no demand for well-designed input-output examples in both training and testing, which leads to a good generalization. (2) The query network works in an efficiently gener- ative manner, which can essentially reduce the computation cost while facing problems with large input-output space. (3) The query network serves as a plug-and module with high scalability, for it is separated from the program synthesis process entirely.
To train the query network, the key idea is to model the query process as decision tree and find out that the informativeness of the input-output examples associated with the amount of mutual information (i.e.the information gain in the decision tree) between the input-output examples and the programs, and thus the query network can be optimized by maximizing the mutual informa- tion. The mutual information can be approximated by the InfoNCE loss (van den Oord et al.) 2018), which depends on the relevance between the samples. However, due to the many-to toayy-to-manny many relation- ship between the input-output examples and the programs, the relevance is difficult to be measured straightforwardly. To this end, we introduce the functional space (F-space). In F-space, each pro- gram can be projected into vector, and each input-output example corresponds programs, which can be represented by a normal distribution (Sun & Nielsen 2019). Whenever a new example is queried, the new set of candidate programs produced by the intersection of the two original sets of programs, and the new distribution is produced by the product of the two origi- nal distributions. The more the queried examples, the smaller the size of the program set, the lower the entropy of the distribution. With the InfoNCE loss and F-space, the query network is trained to generate the input-output examples whose F-space distribution can maximize the probability of the corresponding program and minimize the probability of the others. Once the query network is trained, the training of the synthesis network is no different from what other researchers have done before, except that the input-output examples are generated by the query network.
set of candidate
We evaluate our method on the Karel task and the list processing task which have large input spaces. Without utilizing the well-designed input-output examples both in training and testing, we achieve and even outperform the rate-of-the--a performance on the Karel task and list processing task, which shows the effectiveness and generalization of our query- based framework.
2 PROBLEM STATEMENT
Intuitively, consider an oracle that contains some kind of symbolic rules programs), our goal to discover these symbolic rules inside this oracle. To do this, the traditional program synthesis assumes that the oracle can provide some informative signals (e.g.input-outpe) ically, based on which the synthesizer can find the rules. However, this is a strong assumption with high requirements problem where the informative signals are gained actively by querying the oracle under a much weaker assumption that the behavior of the oracle is deterministic (i.e.the same input always results in the same output).
examples) automat-
the oracle that is impractical in many cases. In this work, consider query
Following the intuition, a reasonable solution for the query problem would be "making the programs distinguishable with as few queries as possible". To make this statement concrete and practical, we introduce the following formulations.
2

---

Published as a conference paper at ICLR 2022
First, define the functional equivalence, which is consistent with the definition of the equivalence of functions in mathematics.
Definition 2.1 (Functional equivalence). Let Il be the input example domain containing all valid input examples, be the output example domain containing all possible oulput examples, and be the program domain containing all valid programs under the domain specific language (DSL), each program p E IP can be seen as a function p : O. For two programs pj E P and Pj E P, p; and Pj are functional equivalent if and only if Va: E p4(x) = (x))
Using the concept of functional equivalence, we can formulate the program synthesis task:
Definition 2.2 (Program synthesis). Suppose there is underlying program E I and K input- output examples [e] = { yk (T Vs)) E 1 x O, 1...K K} generated by it, the program synthesis task aims to find program ý which is functional equivalent to p using [el.
Following the definitions above, we can define the task of the query.
Definition 2.3 (Query). Given a program E IP and set of history K input-outple examples [e]] the query process firstly generates query by the query network fgi IK+1 f[el]] corresponding response is given by the program UK+1 = p(rk+1) E O. The query and response are added to the history input-ouiput examples: [e]] t [e] U (2K+1.8K+1)) and this process repeats.
Then,
The query process aims distinguish the underlying program with as few queries as possible, based on which we can define the optimal query strategy.
Definition 2.4 (The optimal query strategy). Given set of programs and a target program p", the optimal query strategy Q aims to distinguish the p* by generating as few input-output examples [e]] as possible.
When the query space is large, is impractical to find the optimal query strategy by direct search. Thus, we take the query process as the expansion of a decision tree where the leaves are the pro- grams, the nodes are the queries, and the edges are the responses, and then the generation of queries can be guided by the information gain, which is also known as the mutual information:
[e]
arg max / (P; [[]]).
(1)
[c]
METHODS
The mutual information is hard to calculate due to the large spaces of queries and programs. To this end, we resort to the InfoNCE loss (van den Oord et al. 2018) which estimates the lower bound of the mutual information:
LNCE [loog exp(S([e]] Pw)) }}
N
exp( (ep([((ee,pp) (()).
and
I(IP; [e]]) 2 (og(N) LNCE,
(3)
where ((:,)) denotes a relevance function. Maximizing the mutual information is equivalent to min-
imizing LNCE. Intuitively, InfoNCE maximizes the relevance between the positive pairs and mini- mizes the relevance between the negative pairs. Specifically, for a batch data {[[e] Pn); pn) JN, construct positive pairs as ([e)s.P:)) and negative pairs as ([[e]s.P))) + j}. Traditionally, the relevance defined as the dot product of the samples, which may be inaccurate for the many- to-many relationship between the input-output examples and the programs. Thus next, will introduce functional space (F-space) to model the relationship properly.
3.1 F-SPACE
Definition 3.1 (F-space and functional distance). F-space is [I] dimensional space which consists of all valid programs that can be implemented by program domain P.. Each program is represented by [I] different output examples (y1, V2.-.. ..n)) The distance F-space can be measured by the number of different output examples: d(v;, Dú |di [(v,, (())
3

---

Published as a conference paper at ICLR 2022
Espe
[c]] E [el,
[e]
Lel.Ulel
F-SEEcE
[e]]
The illustration of F-space. Left: The projection of the input-output examples [[e] and program Middle: The subset relationship between [e]; and [ell;- Note that this relation is opposite in F-space; Right: The union operation of [[e]] and [[e]]- This operation is also opposite in F-space where union operation correspond to an intersection operation in F-space.
Figure 2:
Intuitively, F-space (P,, d) measures the functional differences between programs. Each program can be represented by a vector in F-space, and if different programs are represented by the same vector e (y1, //,,.... ym), ). indicates that these two programs get the same results for all inputs, and they are considered to be functionally equivalent. This is also consistent with Definition 2.1 In practice, a space with dimension [II is too large to compute, and thus we utilize the sparsity of F-space and learn approximate space with dimension reduction by neural networks.
Regarding onput- examples, representing them by vectors is not appropriate. Consider a set of input-output examples [e] { (2x, 3*k} {*, cannot find vector that represents it when K < [I] because there are more than one programs that satisfies these K input-output examples.
Formally, summarize the properties of the representation of input-output examples in F-space as follows:
Each of input-output examples [e] {(r yb)) should be represented by set of
F-space vectors [r] = =
For two sets of input-output examples [e]; and [e],, if [ell S [eli- then their F-space representations [r]; and [rr1, have the relationship [r]. [r]
For two sets of input-output examples [e]]: and [e]]]- suppose [e]' = [c], [el then in
F-space, their corresponding representations have the relationship ]rl' - [r]; [r]:Urb
Similarly, if [e]' [c]] L [e] then in F-space, their corresponding representations have the relationship [r]]' = [r] n [r];
Additionally, this representation should be differentiable and thus can be optimized by neural net-
works. To this end, we model the representation of [e] as a Normal distribution (Ren & Leskovec Sun & Nielsen 2019). where the probability of the distribution indicates the possibility that it is the underlying program to be synthesized given input-output examples [[e]. We illustrate the
2020
projection, the subset relationship, and the union/intersection operation distributions Figure Under this representation, the query process becomes the process of reducing the uncertainty of the distribution. To train the query network, we define several neural operators for the ncural network training follows.
Program projection. To project a program to a vector v in F-space, we traditionally use a sequence model as encoder:
(4) Note that the program synthesis model differs largely on different datasets, so we choose vary our program encoder according to the specific program synthesis models different datasets. In practice, our program encoder is the reverse of the program synthesis decoder.
v (p)
Input-output example projection. Given a single input-output example [e] (2, v)}. we can project it into Normal distribution using the same architecture of the corresponding program syn- thesis model, except that add MLP output the two parameters of the Normal distribution: and 2)).
(o, MLP (Encoder, ([el)),
(5)
where MLP means multi-layer perceptron.
4

---

Published as a conference paper at ICLR 2022
Xt
x++1
xt+2
Query
Query
Query
Program
Program
Program
X1.
X1
11
.....*
....
....
1r-1r
1--11
1 Yt-1
InfoNCE loss
Xt. Yt
Xx. Yt
Xt+1.Y1+1
InfoNCE loss
InfoNCE loss
Figure 3: The recurrent training process.
Input-output examples intersection. Given K onputt examples [e] = {( }K)} each example (Tr, }a)} is represented by Normal distribution Pr. - (Jus: Tx) using the projector above. The purpose of the intersection is to aggregate these Normal distributions into a new one, which represents [e]] in F-space. Under the assumption of independence, the probability of the intersection distribution should be:
K
Pri
II Pre. k=1
(6)
Fortunately, the product of independent Normal distributions is still a Normal distribution, which means that can represent it [μ', log(o"))), practice we utilize the attention mechanism with another MLP to let the neural network learn the new Normal distribution (Ren & Leskovec 2020
ln',log(o") (0og(o2))=
Σ W/ log log(o?))
eepp M M.Paaetnttin attention (1e,, log (o?
U/s Σj= crp(MMPP Pattentioon (145, log(o
(8)
This formulation not only keeps the form of distributions closed but also approximates the mode of the effective support of Normal distributions, which satisfies requirement the intersection of
distribution (Sun & Nielsen 2019). Appendix C.1
We give detailed proof on the reasonability of doing this in
Inverse projection to query. Finally, we need to generate new query from the representation of input-output examples in F-space. Using the projection and the intersection operation mentioned above, we can project the K onput-output examples into the representation [μ', log(o"))) To gener- ate query Tnew from this representation, we introduce decoder which has similar architecture to Encoder, but reversed:
Enew Decoder([x', (ollpl",oog(""" loo(o"))))
With these operators, we can model the relevance between input-output examples and programs as the probability in the distributions in F-space, and rewrite the loss in Equation as
exp(N((pn (p ('))'))))
LNCE -Ellog(
(10)
EN cpp(N(pp
Next, will introduce how to train the neural network.
5

---

Published as a conference paper at ICLR 2022
3.2 TRAINING
As mentioned above, the query network is optimized by maximizing the mutual information. We observe that taking previous query examples as the condition and only optimizing the query strat- egy at the current query step is a greedy optimization, which may fail into the local minima more easily. An example is shown in Appendix C.2 Thus, a recurrent training process adopted grep the global mutual information on every step instead of the mutual information conditioned on the previous examples. See Figure and Algorithm
Additionally, like the task of sequence generation, we need an input-output example to act as the start signal < sos 2. However, different datasets differ largely in program synthesis, which makes the design of universal start signal difficult. Thus, we design specific start signals for each dataset separately. For example, in Karel, the signal is designed to be an empty map with the robot at the center of the map; In list processing, the signal is just three lists full of NULL. More training details such as the network architectures, the processing of datasets, training tricks, can be seen in Appendix A
4 EXPERIMENTS
We studied three problems in our experiments, (1) The metric that is reasonable in our query-based framework. (2) The performance of the query-based framework. (3) The generalization ability on different tasks of the query- based framework. To do this, first, we demonstrate comparison among several program synthesis metrics. Then, we present our results of the query on the Karel dataset and the list processing dataset to show our methods' performance and generalization ability.
4.1 METRICS
There are three metrics in neural program synthesis.
Semantics:
Given 5 input-output examples, if the predicted program satisfies all these examples, then it is semantically correct.
Generalization: Given 5 input-output examples and a held-out input-output example, if the predicted program satisfies all 6 examples, then it is generally correct.
Exact match: If the predicted program is the same as the ground-trute program, then it matches the ground-truth exactly.
Among them, the exact match is the most strict metric and generalization is the second one. In practice, the exact match has its drawback in that the predicted program may be different from the ground-truth program, but they are functionally equivalent. Thus, the performance is measured by generalization on Karel and semantics on list processing traditionally. However, generalization is not appropriate here for two reasons: (1) It can only measure the performance of the program synthesis process instead of the query process. In the query process, the network chooses input- output examples independently, and judging them by the held-out example is meaningless. (2) Even for the program synthesis process without query, generalization is not strict enough. The program that satisfies small set of input-output examples may fail on a larger set of input-output examples. Thus, the best choice is to use functional equivalence as our metric. Unfortunately, the judgment of functional equivalent is notoriously difficult problem which makes it hard be applied in evaluation. To alleviate this problem, we generate 95 held-out input-output examples randomly to achieve a higher branch coverage than 1 held-out example, and make the generalization on these examples a proxy of the functional equivalence:
Functional equivalence (proxy): Given 5 input-output examples and 95 held-out input- output examples, if the predicted program satisfies all 100 examples, then it is functional equivalent to the ground-truth program.
To illustrate the difference between functional equivalence and generalization further, we measured the average branch coverage of these two metries on Karel's validation set. Given set of input- output examples, branch coverage evaluates the percentage of program branches that are covered by the examples.

---

Published as a conference paper at ICLR 2022
Table The performance of the program synthesis model trained on input-output examples gener- ated by different methods on the Karel task.
Bunel et al. (2018)
Chen et al. 2019
Metric
Random Well-designed
Query
Random
Well-designed
Query
Exact match Functional equivalence
29.44% 33.08%
41.16% 48.52%
41.12% 46.64%
26.08% 32.28%
37.36% 47.60%
38.68%
48.48%
The result is shown in Table Functional equivalence outperforms generalization by nearly 10%, which indicates that functional equivalence can represent the correctness of the predicted program much better than gen- eralization.
Semanties
Generalization
FE
Branch coverage
86.57%
87.99%
97.58%
Table I: The branch coverage of semantics, general- ization and functional equivalence (FE).
4.2 KAREL TASK
Karel is an educational programming lan- guage used control robot living in 2D grid world (Pattis al. 1981.. The domain-specific language (DSL) and other details are included in Appendix B.1
Settings. Following Section 3 we split the training process into the training of the query network and the training of the synthesis network. For the query network, set Encoder, the same the one of Bunel et al. (2018) except for the output layer, and Encoder, a two-layer LSTM (see details in Appendix A.2)). For the synthesis network, all settings stay unchanged in the original program synthesis method. We report the top-1 results with beam size 100 for Bunel et al. (2018) and 64 for Chen (0199) which the default setting for validation the original code. As in Section 4.1 exact match and functional equivalence are more appropriate than other metrics in the query task, so we save the checkpoints based on the best exact match instead of the best generalization (for the computation inefficiency of functional equivalence), which may cause differences in our baseline reproduction.
We generate the dataset with 5 input-output examples using three different methods: randomly selected (random), baseline models (well-designed), and our method (query). Then, we train the synthesis network these datasets with two state-of-the-aat methods: Bunel et al. (2018) and Chen jet al. (2019). Note that there is a slight difference between the program simulators used by them which will give different responses during the query process, and choose the one in Bunel al. 20188) as ours.
Dataset Performance. Table 2 presents the performance of the trained synthesis networks, from which we conclude that The The queried dataset performs well both two training methods, indicating that the query process is totally decoupled with the synthesis process and has high generality. (2) Our query method gets comparable results with both baseline methods and largely outperforms the random selection method with more than 10%, which shows its effectiveness.
Comparison query. We also compared our method with query by committee (QBC) Seung et (1992) as another baseline, shown in Figure In QBC, we sample queries based on their diversity. That is, we generate program candidates by beam search, and then select the query that can re- sult in the most diverse outputs on these program candidates. The diver- sity is measured by the output equiv- alence. Algorithm details can be seen
45%
3556
Frnectioan loneettnlllll aqueealanee
355
25%
Quary
Randam
Query
20%6
Well designed
25%
Rundom
15%
QBC-cmah
Woll-designal
10%
QDC cash unzware
15%
QBC-cmahh aware
OBC-enshb-anowane
Number of queries
Number of quesies
Figure 4: The query performance of different methods.
7

---

Published as a conference paper at ICLR 2022
Bunel et.al
Chen ct.al
40%-
Fumetional equivalence
50%
40%
Fumctional equivalence
50%
40%k
30%6
30%
Well-designed
30%
Well-designed
20%
Well-designed
Well-designed
20%
Query
20%
Query
Query
10%
Query
Random
Random
Random
Random
10%
0%
20
10
10
Number of spochs
Number epochs
Number of spochs
Number epochs
Figure The training curve of the program synthesis model on Karel.
Table 3: The performance of the program synthesis model trained on input-output examples gener- ated by different methods on the list processing task.
Searching for semantics
Searching for exact match
Dataset
Metric
Random Well-designed
Query
Random
Well-designed
Query
Exact match
20.07%
32.81% 80.26%
22.26%
50.65%
81.21%
81.56%
Di
Functional equivalence
52.03%
68.20%
50.65%
81.21% %
81.56%
Exact match Functional equivalence
9.25%
15.72% 39.88%
10.44%
22.61% %
38.51% 38.51%
38.63%
D2
24.49%
32.94%
22.61% %
38.63%
in Appendix B.4 There are two strategies based on QBC: Crash-aware, which repeats the algorithm sample another one if the query crashes; And crash-unaware, which samples queries regardless of the crash problem (see Appendix [or a detailed explanation of crashes). QBC-crash-unawarc performs worse than Random because Random is chosen by filtering crashed IOs while QBC-crash- unaware may contain crashes. QBC-crash-await performs much better than QBC-crash-ue unaware because queries the underlying program multiple times to make sure that the query will result in a crash, which is unfair. Even though, out method still outperforms QBC-eeash-aware, which shows its advantage.
crash-unaware
Training process. To do further study, plot the training curve in Figure 5 It is shown that the Query dataset always has quick start, which indicates that the query method can extract the features of the distinguishable programs effectively and makes them easier be synthesized.
4.3 LIST PROCESSING TASK
To show the generalization ability of the query method, conduct another experiment on the list processing task. The list processing task takes 1-3 lists or integers as the input example, and then produces list or an integer as the output example. More details can be seen Appendix B.2
Settings. Following PCCoder Zoharr & Wolf 2018), we generate two datasets with program length 4 as dataset D2 and program length up to 12 as dataset D2. We set the Encoder, of the query network similar PCCoder except for an MLP, and use single layer LSTM as the Encoder, (see Appendix A.2 The synthesis network and the parameters of complete anytime beam search (CAB) (Zhang 1998) stay the same as PCCoder, except that the maximum time is set seconds instead of 5,000 seconds for reality.
Similar to the Karel task, we generate the dataset with 5 input-output examples with three different methods. Furthermore, we use two end conditions of CAB: The searching ends when all input- output examples satisfied (searching for semantics), and the searching ends when all statements are true (searching for exact match).
The results are presented Table 3 from which we can conclude that: (1) Our query method results higher than well-designed input-output examples in searching for the exact match and consistently outperforms the random. (2) When the length of programs increases. the performance decreases largely. This results from the original algorithm of PCCoder that the inter-
Performance.
8

---

Published as a conference paper at ICLR 2022
mediate variables difficult to be saved when the ground program is long. However, the query method decreases slower than others, and the gap between the well-designed and the query is closed largely.
RELATED WORK
Programming by examples. Synthesizing a program that satisfies the user intent using the pro- vided input-output examples is a challenging problem that has been studied for years (Manna & Waldinger 1971: Liebermam| Solar-oaaam et al. 2006)Gulwwani 201 Gulwani et al. 2012).
Recently, with the development of Deep Learning, more researchers tend tackle this problem with neural networks a variety of tasks, including string transformation (Devlin et al. 2017b),
list processing (Balog al. 2017: Zohar & Wolf, 2018), graphic generation (Ellis et al. [2015 Tian
ct al. 2219)) Karel (Devlin et al. 2017a| |unell et al.) 2018), policy abstraction (Sun et al.
2018
Verma et al.
2018) and so on. Additionally, techniques like program debugger (Balog al.
2020
Gupta ct al.
2020). traces (Chen et al., 2019 Shin et al. 2018 Ellis et al. 2019), property sig- natures (Odena & Sutton 2020; Odena et al., 2021) are also used improve the performance of
program synthesis. However, their promising performance relies on the well-designed input-output examples which a high requirement for users. If the examples provided are of poor quality, the performance will be affected severely. Worse, if out-of-distribution examples are provided, the pro- gram synthesis model cannot finish the task as expected (Shin et al. 2019).
Interactive program synthesis. Considering the high requirement of input-output examples, Le et al. (2017) build an abstract framework in which the program synthesis system can interact with users to guide the process of synthesis. Following this framework, multiple interactive synthesis systems are studied. Among them, Mayer et al. ()015). |Wang et al. (2017), and Laich et al. (2020) tend to find counter-examples as queries to the users in a random manner. Although they get rid of the restrictions on the users, the quantity of the onput- examples is not guaranteed, which may get the synthesis process into trouble. Padhi et al. 2018) select more than one query each time and let the users choose which one to answer. This brings additional burden the users, and the users are unaware of which query will improve the program synthesized most. Most recently, Ji al. (2020) utilizes the minimax branch select the question where the worst answer gives the best reduction of the program domain. Theoretically, the performance of the selection is guaranteed. However, this method is based on search and hardly be applied to tasks with large input-output space. Worse, the query process and the synthesis process are bound, which results in its poor scalability. In contrast, our method can be applied to problems with large spaces, and the query process is decoupled with the synthesis process, which makes its application more flexible.
Learning to acquire information. Similar to our work, Pu et al. study the query problem from an cntrmmation-thhoredee perspective. They show that maximizing the mutual information between the input-ouiput examples and the corresponding program greedily is 1-1 as good as the optimal solution that considers all examples globally. However, they assume that the space of queries can be enumerated, which limits the application of their query algorithm on complex datasets like Karel. By comparison, our work proposes a more general algorithm that can generate queries in nearly infinite space. Other related work including active learning and black-box testing can be seen Appendix
2018) and Pu et al. (2017) also
6 CONCLUSION
In this work, we propose query-based framework to finish the program synthesis task more re- alistically. To optimize this framework, we show the correlation between the query strategy and the mutual information. Moreover, we model the relevance between the input-output examples and programs by introducing the F-space, where we represent the input-output examples as the distri- bution of the programs. Using these techniques, we conduct a series of experiments that shows the effectiveness, generalization, and scalability of our query-based framework. We believe that our methods work not only the program synthesis tasks, but also any task that aims to simulate an underlying oracle, including reverse engineering, symbolic regression, scientific discovery, and so

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work partially supported by the National Key Research and Development Program of China (under Grant 2020AAA0103802), the NSF of China (under Grants 61925208, 62102399, 62002338, 61906179, 61732020, U19B2019), Strategic Priority Research Program of Chinese Academy of Beijing Academy of Artificial Intelligence (BAAI) and Beijing Nova Pro- gram of Science and Technology (Z191 100001 I 19093), CAS Project for Young Scientists in Basic Research (YSBR-029), Youth Innovation Promotion Association CAS and Xplore Prize.
Science
REFERENCES
D. Angluin. Queries and concept learning. Machine Learning, 2:319-342, 1988.
Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, S. Nowozin, and Daniel Tarlow. Deepcoder: Learning write programs. In ICLR (Poster). OpenReview.net, 2017.
Matej Balog, Rishabh Singh, Petros Maniatis, and Charles Sutton. Neural program synthesis with differentiable fixer. ArXiv, abs/2006. 10924, 2020.
Rudy Bunel, M. Hausknecht, Devlin, Rishabh Singh, and Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In ICLR (Poster). OpenReview.net, 2018.
Xi Chen, Yan Duan, Rein Houthooft, J. Schulman, Ilya Sutskever, and P. Abbeel. Infogan: Inter- pretable representation learning by information maximizing generative adversarial nets. In NIPS, 2016.
Xinyun Chen, Chang Liu, and D. Song. Execution-guided neural program synthesis. In ICLR, 2019.
Ido Dagan and S. Argamon. Committee-based sampling for training probabilistic classifiers. In ICML, 1995.
Devlin, Rudy Bunel, Rishabh Singh, M. Hausknecht, and P. Kohli. Neural program meta- induction. In NIPS, 2017a.
J. Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and P. Kohli. Robustfill: Neural program learning under noisy i/o. In ICMI, 2017b.
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and J. Tenenbaum. Learning infer graphics programs from hand-drawn images. In NeurlPS, 2018.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with repl. In NeurIPS, 2019.
S. Gulwani. Automating string processing in spreadsheets using input-output examples. In POPL 2011.
Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using exam- ples. Commun. ACM, 55:97-105, 2012.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Found. Trends Program. Lang., 4:1-119, 2017.
Kavi Gupta, P. E. Christensen, Xinyun Chen, and D. Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. In NewrIPS, 2020.
Eric Jang, Shixiang Shane Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In ICLR (Poster). OpenReview.nett 2017.
Ruyi Ji, Jingjing Liang, Yingfei Xiong. Lu Zhang, and Zhenjiang Hu. Question selection for inter- active program synthesis. Proceedings of the 41 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2020.
R. King, Ken E. Whelan, F. M. Jones, Philip G. K. Reiser, Christopher H. Bryant, S. Muggleton, D. Kell, and S. Oliver. Functional genomic hypothesis generation and experimentation by a robot scientist. Nature, 427:247-252, 2004.
10

---

Published as a conference paper at ICLR 2022
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6990, 2014.
V. Krishnamurthy. Algorithms for optimal scheduling and management of hidden markov model sensors. IEEE Trans. Signal Process., 50:1382-1397, 2002.
Larissa Laich, Pavol Biclik, and Martin T. Vechev. Guiding program synthesis by learning to gener- ate examples. In ICLR, 2020.
Vu Le. Daniel Perelman, Oleksandr Polozov, Mohammad Raza, A. Udupa, and S. Gulwani. Inter- active program synthesis. ArXiv, abs/1703.03539, 2017.
D. Lewis and W. Gale. A sequential algorithm for training text classifiers. In SIGIR '94, 1994.
H. Lieberman. Your wish is my command: Programming by example. 2001.
Chris Maddison, Andryy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In ICLR (Poster). OpenReview.net, 2017.
Z. Manna and R. Waldinger. Toward automatic program synthesis. Commun. ACM, 14:151-165, 1971.
Mikaël Mayer, Gustavo Soares, Maxim Grechkin, Vu Le, Mark Marron, Oleksandr Polozov, Rishabh Singh, B. Zorn, and S. Gulwani. User interaction models for disambiguation in program- ming by example. Proceedings of the 28th Annual ACM Symposium on User Interface Software & Technology, 2015.
Karl Meinke. Automated black-box testing of functional correctness using function approximation. In ISSTA, pp. 143-153, ACM, 2004.
Karl Meinke and Fei Niu. A learning-base approach to unit testing of numerical software. In ICTSS, volume 6435 Lecture Notes in Computer Science, pp. 221-235. Springer, 2010.
Karl Meinke and Muddassar A. Sindhu. Incremental learning- based testing for reactive systems. In TAP@ TOOLS, volume 6706 of Lecture Notes in Computer Science, pp. 134-151. Springer, 201 1.
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In ICLR. OpenReview.net, 2020.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, and Charles Sutton. Bustle: Bottom-up learning-guided guided exploration. In ICLR. OpenReview.net, 2021.
program program-synthenn synthesis through learning
Saswat Padhi, Prateek Jain, Daniel Perelman, Oleksandr Polozov, Gulwani, and Millstein. Flashprofile: a framework for synthesizing data profiles. Proceedings of the ACM on Program- ming Languages, 2:1 28, 2018.
Richard Pattis, Roberts, and M Stehlik. Karel the robot. A gentele introduction to the Art of Programming, 1981.
Yewen Pu, Leslie Pack Kaelbling, and Armando Solar-Lezama. Learning acquire information. In Gal Elidan, Kristian Kersting, and Alexander T. Ihler (eds.), Proceedings of the Thirly-Third Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, AUAI Press, 2017.
Yewen Pu, Zachery Miranda, Armando Solar-Lezama, and L. Kaelbling. Selecting representative examples for program synthesis. In JCML, 2018.
Hongyu Ren and Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In NeurIPS, 2020.
H. Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In COLT, pp. 287-294, ACM, 1992.
Richard Shin, Illia Polosukhin, and D. Song. Improving neural program synthesis with inferred execution traces. In NeurlPS, 2018.
11

---

Published as a conference paper at ICLR 2022
Richard Shin, Neel Kant, Kavi Gupta, Christopher M. Bender, Brandon Trabucco, Rishabh Singh, and D. Song. Synthetic datasets for neural program synthesis. In ICLR (Poster). OpenReview.net, 2019.
Changjian Shui, Fan Zhou, Christian Gagn'e, e, and B. Wang. Deep active learning: Unified and principled method for query and training. In AISTATS, 2020.
Armando Solar-Lezama, Liviu Tancau, R. Bodík, S. Seshia, and V. Saraswat. Combinatorial sketch- ing for finite programs. In ASPLOS XII, 2006.
Ke Sun and Nielsen. Information-geommetii set embeddings (igse): From sets to probability distributions. ArXiv, abs/1911.11240) 2019.
Shao-Hua Sun, Hyeonwoo Noh, S. Somasundaram, and Joseph J. Lim. Neural program synthesis from diverse demonstration videos. In ICML, 2018
Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, W. Freeman, J. Tenenbaum, and Jiajun Wu. Learning to infer and execute shape programs. ICLR (Poster). OpenReview.net, 2019.
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. ArXiv, abs/1807..dm .07448, 2018.
Abhinav Verma, V. Murali, Rishabh Singh, P. Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 5052-5061. PMLR, 2018.
Chenglong Wang, Alvin Cheung, and R. Bodík. Interactive query synthesis from input-output ex- amples. Proceedings of the 2017 ACM International Conference on Management of Data, 2017.
Weixiong Zhang. Complete anytime beam search. In AAAI/IAA, 1998.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In NewrIPS, 2018.
12

---

Published as a conference paper at ICLR 2022
A TRAINING DETAILS
A.1 TRAINING ALGORITIIM
Algorithm Training process
1:
function TRAIN()
2: Initialize max iterations and max query times
3: for i NJ do
4:
p + Underlying programs
5:
(0o. Vo) &-
6:
[el + {(00. yo)}
7:
L+0
8:
for 1 E
do
9:
- Encoderp(p)
Encode program, Equation (4)
10:
n1, logg(oo? IO-ENCODER([]]) Tt -- Decoder(1, log(o)))
Encode input-output examples
11:
D Query next input Get next output from the oracle
Y1 p(xz)
13:
[e] - [e]l (1t,, ve)
"' log(o ([C)
15:
L + Loss(u, u. (og(o"") +
> InfoNCE loss, Equation
end for
17: Update parameters w.r.t. L
end for
19: end function
1: function 10 10-ENCODER((ZA }&3*)
2: for ioriE (1... K} do
(og +- MLP (Encoder, (( (x1, (:]) 4: end for
3:
Encode single example, Equation
5: for i E (1... K} do
Wi f expl MLP, tientiion (lp,, Jog(a
6:
Calculate attentions, Equation (8)
E L. Puctiattion (1a
log(
7: end for
8: [n, log( o "²=]] Ek w; w,; [og(
Intersection, Equation
9: return la, log(
10: end function
A.2 MODEL DETAILS HYPER PARAMETERS
Karel. The query encoder is the same the one used by [unel et al. (2018) composed of Convolutional Neural Network (CNN) with the residual link. After the query encoder, there is an MLP to project the embedding into μe, log(o²). The dimension of f and is the hidden size of MLP is 512. The query decoder is similar to the query encoder except that the number of channels is reversed, and additional batch normalization is added to keep the generation more stable. The program encoder is two-layer LSTM with hidden size of 256.
256, and thus
Note that in the well-designed dataset, the size of the grid world can be changed from to However, for the convenience of training, we set the size of the query world fixed to 16. Moreover, to guarantee that all queries can recognized by program simulator, we split the query into three parts: boundaries (the map size, set to 16x 16), agent position (where the agent is and towards), and map state (the placement of markers and obstacles), and generate them as follows:
Boundaries: The boundaries indicate the map size, fixed 16 x 16.
Agent position: generate 4 x 16 16 one-hot vector where 4 indicates four facing directions and 16 x 16 indicates the position.
Map state: generate 12 one-hot vector on the 16 x 16 map including obstacle, 1-10 markers, and empty grid.
13

---

Published as a conference paper at ICLR 2022
Conv
Conv BN LReLU
Conv LReLU
Activation-
Conv
ReLU
Conv ReLU
Conv
ReLU
Iayers
Activation
BN LReLU
layers
(a) ResBlock
(b) ResBNBBlok
Input-examples
Conv
Linear
Hedilado
Linear
10 embeddings
10 embeddinggs
ML.P
Ousput-examples+
Cony
Lineur
+ Iug(a*)
(c) 10 Encoder
Distribution encoder (MLP.)
Input-output examples
10 Enooder
MILP
(o) latent code
RoBN- Blocks
Representation
log(d?)
(e) Enzoder
(i) Decoder
16x16
boundaries
N
Input-ouiput examples
Internect
Linear
Reshupe
Decoder
Lincur
Agent position
Concel
+ +Query
Latent code
Conv
Gumbel
Softums
Map
(g) The query network for Karel
Figure 6: The architecture of the query network for Karel (zoom in for better view).
Activation-
Linear
Linear
Linear
Next layers
Input-output examples
Embed
Donse Blocks
10 emboddings
(a) DenseBBlock
(b) IO Encoder
10 embeldings+
MLP
Lineur
Input-output
examples
10 Enceder
#
Lineur
+ log(a")
log(o*)
(e) Distribution Encoder (MLP)
(d) Enceder
Iaput types
examples
Input-output
Intersect
Cencat
Linear
Gumbel
Seltuxx
Gumbel
Int proposition
proposition /
+nn/Lis//Nulll
Padding
+uury
1 atent code
Softmas
Null
(e) The query network for list processing
Figure 7: The architecture of the query network for list processing (zoom in for better view). Type filter chooses query between the list proposition and int proposition depends on the input types.
The architecture details are shown in figure 6
For training, the learning rate query network is set to 10-4 with the Adam optimizer Kingma & Ba (2014) while the learning rate of the synthesis network stays the same with the original methods. The batch size is 128, and the random seed set to 100.
List processing. The query encoder is the same as the one in PCCoder. The dimension of and set to 256 for dataset D) and 128 for dataset D2 without much tuning. The query decoder is lingle-layer linear network with dimension 256 for dataset D; and 128 for dataset D2. The program encoder a single layer LSTT with hidden size 256 for dataset D and 128 for dataset Dz.
The inputs of list processing consist of three types: INT, LIST, and NULL, Thus, each query is NULL or an integer or a list consisting integers the range of [-256, 255]. Each integer is represented by 512 one-hot vector. For the well-designed input-output examples, the length of a LIST is sampled stochastically with the maximum length of 20. However, to make the query network simpler, fix the length of queries to 20. The query network generates all three types
14

---

Published as a conference paper at ICLR 2022
Prog p = def run()
Stmt while(b) : repeat(r) | $1;
if(b): ifelse(b) 81 else
Cond frontIsClear() leftIsClear() righttIeeer))))))) markersPresent(( noMarkersPresent()) not Action move() turnRight() turnLeft()
pickMarker() putMarker()
Cste 0 19
Figure 8: The DSL of Karel
separately by different networks and chooses among them according to the type of inputs using type filter.
The details of the query network for list processing are shown in figure
For training, the learning rate of the query network is set 10 with 0.1 decay every 40 epochs and the Adam optimizer Kingma & Ba (2014). The learning rate of the synthesis network is 10-3 which stays the same with the original methods with 0.1 decay every epochs. The batch size of the query process is 64, the batch size of synthesis is 32 for Dj and 100 for D2. The random seed is set to 100.
A.3 OTHER TRAINING TECHNIQUES
Latent code. The subsequent queries easy fail into the mode collapse, generating simi- lar queries repetitively. To tackle this problem, we introduce a latent code, like the one in Info- GAN (Chen et al., 2016), another input, which indicates the current query step, and ask the encoder in the next query step to decode it accurately. Specifically, given latent code which indicates the current query step, the query network supposed to maximize the mutual information between and the output query x to alleviate the mode collapse problem. To generate under the condition of c, we concatenate with the encoded representation μ and log(a²), and then send it to the decoder (Equation (9). shown in Figure and Figure 7c). To maximize the mutual informa- tion I (c; Ir), we design a network aiming to classify from T, which models the distribution Q(c(z) (details can be seen in Chen et al. (2016)). This network shares its parameters with the Encoder, (Equation (5) except for the last layer, and is optimized with the cross-entropy loss.
Gumbel-Softmax, Note that the queries are discrete, which makes the query network cannot be optimized by pack-propagation. Thus, we take advantage of the fumbel-Softmax distribution (Mad-) dison et al. 2017 Jang et al. 2017) and make the query process differentiable.
Curriculum learning. The query network is trained progressively. At the beginning of the train- ing, the query network generates one query only. As the training goes on, the limit of the number of queries increases until it achieves five. Specifically, this limit increases every epochs. Curricu- lum learning helps to make the training process more stable.
Kullback-Leibler (KL) divergence. A failed attempt. Similar to the latent code, we tried to add the reciprocal of the KL divergence between different queries on the same program as another loss to make the queries more diverse. However, this loss does not have significant impact training most of the time and makes the training process unstable, and thus it is abandoned our final version.
15

---

Published as a conference paper at ICLR 2022
Hero facing North
Hero facing South
Hero facing West
Hero facing East
Obstacle
Grid boundary
marker
marker
marker
marker
marker
marker
marker
marker
marker
10 marker
Table 4: Representation cell grid world
Input
Output
Program
def run ()
move ()
putMarker ()
turnRight ()
move ()
Figure 9: An example of Karel.
B EXPERIMENT DETAILS
B.1 THE KAREL TASK
Karel is an educational programming language, which can be used to control robot to move in
2D grid world (Pattis et al. 1981). Figure 8 presents the domain language specification (DSL) of Karel. Figure shows Karel program example. Each cell of the grid world is represented 16-dimensional vector corresponding to the features described in Table (Bunel et al. 2018).
Handling of crashes. agent:
The executor of Karel will get a "CRASH" result and then terminates if the
Picks marker while marker is presented.
Puts a marker down while the number of the markers in the cell exceeds the limit (the limit is set to 10).
Walks up an obstacle or of boundaries.
Falls into an infinite loop (the loop with more than 10. API calls).
In the early stage of training, the query network generates the queries randomly, and thus the pro- grams into these crashed states easily, making the queries cannot be applied to training. To avoid these situations, we modify the executor so that when crashes happen, the state stays still without change and the program keeps executing.
16

---

Published as a conference paper at ICLR 2022
Basic Function
+1
-1
X2
+ x ((-1)
*
*
X3
+3
X4 :4
> 0
<
%2
%2 == 1
First-order Function
HEAD
LAST TAKE DROP ACCESS
MINIMUM MAXIMUN REVERSE SORT SUM
Higher-order Function
MAP FILTER COUNT ZIPWITH SCANL1
Figure 10: The DSL of list processing
Input
Program
[-17, 4,4, 11, 0, -5, 9,, 13, 6, 6, -8 11]
FILTER (<0)
Output
MAP (x4)
SORT
1-12,-20,
REVERSE
Figure 11: An example of list processing.
B.2 THE LIST PROCESSING TASK
The list processing task takes 1-3 lists or integers as input examples and produces a list or an integer as the output example. An example is shown in Figure [1] Figure T0]shows the DSL of list process- ing. Following Zohar & Wolf (2018), we generate two datasets: Dj with program length 4 and D2 with program length up to 12.
Handling of the out of range problem. Constraint propagation guarantees that the execution of programs never obtains intermediate values that out of range [-256, 255]. However, when query randomly in the early stage of training, the out-of-range problem can easily occur. To handle this problem, truncate the intermediate values to [-256, 255] while querying ensure that all queries can yield legal responses.
B.3 THE EVOLUTION OF DISTRIBUTION ENTROPY
To make sanity check of the F-space formulation, study how the entropy of the distribution changes over the step of the query.
The entropy of multivariate Normal distribution N(x; μ, Σ)) is given by
H(x) マ in + (1+1n(27))
(11)
where E denotes the covariance matrix and D denotes the dimension of x. In our case, have assumed the independence of each dimension of x which means that a diagonal matrix. Hence
In (n( In II of - - In(o?))
(12)
where of the diagonal element of Σ, indicating the variance of each dimension. D a constant during querying, so we calculate the mean of log (²²) as equivalent substitute to show the change of the entropy. Results are shown in Figure 12 In our experiments, Karel performs best and this is also revealed by the entropy that Karel decreases much faster than list processing. On the contrary, the entropy of list processing decreases slowly and has worse performance in our experiment. This performance may be increased by tuning the query network more carefully.
17

---

Published as a conference paper at ICLR 2022
1e-3
3v-33
1e-3
3.7
4-
Karel
9.5
List-D1
List-D2
3.6
log 01
3-
9.0
3.5
2-
8.5
3.4
8.0
3.3
1
5
2
Query step
Query step
Query step
Figure 12:
The entropy of the distribution decays when query goes
Table 5: The statistics on the query times of each crash-aware QBC query step.
1
2
3
4
5
avg
5.72
2.47
2.96
4.27
4.86
214
200
224
357
226
min
0
B.4 QUERY COMMITTER
In this section, present the details of our baseline algorithm: query by committee (Seung al. 1992]. Algorithm 2 shows the crash-aware version of the QBC algorithm, which selects the query that result in the most diverse outputs. The crash-unaware version can be obtained simply by removing all CRASH judgments. Note that, compared with the crash-unaware version, the crash- aware version queries the underlying program more times for CRASH judgment (see Table 5). and thus results in a much better performance.
C THEOREMS AND PROOFS
C.1 THE PRODUCT OF TWO NORMAL DISTRIBUTIONS
In this section, will show that the product of two normal distributions is scaled normal distri- bution.
Theorem C.1 (The product of two normal distributions). Given two normal distributions that sat- isfies p(x)
(
the product of them is scaled normal "distribution" in the form of 20
V2n0
(3-
where the scale factor.
"2na
Proof.
Suppose we have two normal distributions Pa and Ps:
Ea Mg :2
Pa(x) = V2TTa
20
(13)
(a (p=
po(x)
20
V2TTbb
The product of p. and Ps:
(emRn 20
pa(x)p((x)
20
V2T0a
1mab
(14)
1
(x-u2
20
2
2TT.
18

---

Published as a conference paper at ICLR 2022
Algorithm 2 Query by committee (QBC): crash-aware
1: function QUERY()
2: Initialize trained model M, query pool Q and max query times
3: 4- Underlying program (oracle)
4: repeat
5: 21 sample
6:
511 <- p(x1)
7:
until y1 not CRASH
8:
[e]] + (21,
9:
for E (2...... {3 do
10:
program candidates [ø] + M(ee]) 21 t SELECT- QUEECT-QUERY(Q.22 [p]) V/ - p(x))
D Get top K predictions by beam search
12:
[e] - [e] ((1),)))
14: end for
15: return [e]
16: end function
1: function SELECT-QUERY(CE [p]
2:
repeat
queries +- sample 100 times from Q 4: score_list +
3:
Acquisition scores of queries
5: for q E queries do
6:
Sq 4- 0
7:
for p [p] do
8:
ÿ + p(g)
9:
if y unique then
10:
+
D> The more diversity the output, the better the query
end if end for
12:
wwwpeliist.ppppdddccc sq))
14:
end for Sort score list in a descending order with 8q for a E score_list do Select the query with the highest score and without CRASH y + p(q)
16:
17:
18:
if' y not CRASH then return end if end for
19:
20:
21:
22:
until query is found
If all 100 queries result in CRASH, repeat this process.
23:
end function
Consider the index part
22)2 (r
(x 2
(02 + 0,)22 - 2(H100 + u00 a (HE0z + 13022
+
20
20
20
x² 2 Us m
13 +12
a2top
20200²
(15)
Hao tn 2
Hso 2 +
o3 +o
22t0
2n
20
02+03
=7+ X
19

---

Published as a conference paper at ICLR 2022
where
of 4
7
0z 4.4%%
(16)
1 +12
(Ubo + )²
02 22+0
0. +
À =
2
22t0
Simplify A:
Hi +
[Bo 3 tua )
22top
0 22
A
20 ahtof
(m300 + 1o 2 + 03²)) (aan + kaa
20 20 (0 + +06)
(17)
(0 + m 2paab)
20 (0 tof))
(Ma- mb)²
2(0 + of)
Finally, we get
pa(x))p(1))
2 x
(18)
(r-d/12
a V2Ta0
where
11 1 2 + M
0 of
0 =
(19)
00 + 0b
21
1
(a-m4)) 2
V 12m + +o²)
Next, we will show that approximating the new jı' and log(o"2) with the weighted sum of the [Pa. mbb
and [log(o2), ( is reasonable.
For p', it is obvious that it can be seen as
1003
Pa
0 of
(20)
o
Pa +
02 + of
d
+
which is a weighted sum. For log(o"? we can rewrite as follows
o.
log(o²2) log( 0² + o
log(a?) + log(a?) - log(oo + +o
1
1
log(oz) log( (hlog(o²) + klog(o?) + log(
2(h-1) +
2(k-1) ))
oft 0a
2h 0
= (1 -))) + (1 k))) log(
ob 0a
2k 2(h-1)
t 0
2(k
(21)
20

---

Published as a conference paper at ICLR 2022
program
4A
QB
QC
QD
Po
X
P1
VVA
V
X
P2
X
p3
V
X
Ps
P6
P7
X
Figure 13: An example: 8 candidate programs Po-7 and 4 queries QA-D each with possible responses {v, x).
where and l are two coefficients. With suitable h and & learned, the last term can be ignored af Rih-17 a2hop 25 1) and thus log(o??) can be approximate by the weighted sum of (1og(o2), log(os)).
C.2 THE RECURRENT TRAINING PROCESS
We adopt a recurrent training process model the mutual information between the onput-output examples and the programs more accurately. Traditionally, the next query is gained by selecting the query with the maximum mutual information conditioned on the former ones:
4 = arg max / (IP; (I, 3)][=))
(22)
However, this greedy strategy fails in that after a series of queries, and finally there are only candidate programs distributed uniformly and 4 queries Q {qA,...:90) {D} each with 2 possible responses {v- x) left, our goal is to find out the underlying program with as few queries as possible (conditioned on the former queries which are omitted). According to the definition of the mutual information [(X; Y)
cases. An example is shown in Figure 13 Suppose
(po....,P
P(z,y) Σzex Eyer P(x, y)log P(m) we can calculate the mutual information between the queries and the programs as follows (we QA-D = v/x x to represent (= v/x for simplicity):
P(p.qA) P(p. p(poga)log P(p)
1
((P: = Σ Σ
8 log
8
(23)
PEr RAE(V.x)
Samilarly, (B) = [(P: = I(P:qD))
qD) 1. Thus, Equation 22 suggests that 4 queries share the same priority. When the query process continues, however, this not the case. For the second query (let (B)):
[(P:g)= Σ Σ
P(p. log
P(p.4) P())
6 log(
1
2* * log( 8
1.81,
PEr 2
(24)
where (v.x}² (V,x) {v, x}. Similarly, T(P: (ДΛ, (c) T(P; (qΛ, T(P; (1c, (D)) = 2,
(25)
I(P: (yn, 4))) [IP; (qn, qn)) = 1.81.
Equation 24 and Equation 25 show that considering the longer horizon, (B is the worst choice as the first query because it gets the minimum mutual information whichever the second query is. This conclusion is also straightforward without calculation: we choose CA,C.D as the first query, then only need query for more times; And if we choose qB as the first query, then need 3.25 queries on average with queries in the worst case.
To this end, we adopt recurrent training process shown in Figure In the recurrent training process, the gradient can be propagated through multiple query steps and thus the current query selection can be affected by future queries.
21

---

Published as a conference paper at ICLR 2022
D ADDITIONAL RELATED WORK
D.1 ACTIVE LEARNING
Active learning a research domain that aims to reduce the cost of labeling by selecting the most representative samples iteratively from the unlabeled dataset and then asking them to an oracle for labeling while training. According to Shui et al. (2020), active learning can be divided into pool-based sampling (Angluin, 1988; King et al., 2004), which judges whether sample should be selected for query-based on the evaluation the entire dataset; steam-based sampling (Dagan & Argamon 1995: Krishnamurthy 2002). which judges each sample independently compared to pool-based sampling: and membership query synthesis (Lewis Gale 1994). which means that the unlabeled sample be generated by the learner instead of selecting from the dataset only. Al- though active learning involves querying an oracle iteratively, which similar to our framework, there still two main differences between them. (1) For the final purpose, active learning aims finish the training stage at low cost, and the inference stage remains the same as other machine learning tasks without the query process, while our framework aims to find the oracle (i.e.the un- derlying program) in symbolic form, and the query process is retained during inference. (2) For the query process, active learning assumes only one oracle (i.e.the same query always gets the same label). In contrast, our framework assumes multiple oracles (i.e.the same query will get different responses if the underlying programs are different).
D.2 AUTOMATED BLACK-BOX TESTING
Black-box testing is method of software testing aiming examine the functionality of black- box (such as a piece of a program) by a large number of test cases without perceiving its inter- nal structures. The most famous automated test cases generation method is learning-based based testing (LBT) 2204
& Niu 2010, Meinke & Sindhu, 2011). LBT is an iterative approach generate test cases by interacting with the black-box, which sounds similar the query problem mentioned in this paper. However, the settings and the purpose of the black-box testing are totally different from ours. In detail, the black- testing assumes the existence of a target requirement (or target function) and a black-box implementation of this requirement (such as a piece of program which unknown). The purpose to check the black-box implementation to ensure that there is no bug or difference between the target requirement and the black-box by generating test cases (i.e inp..uuuuto examples). In a contrast, in our settings, the target function does not exist, and all have is a black-box (or called oracle underlying program in paper). Our goal is to query this black box and guess which program is hidden inside based on the experience learned from the training set.
E TWO QUERY EXAMPLES
In this section, we show two query examples that cover all branches of the program while the well- designed dataset fails to do this. Each example consists of the underlying program and the corre- sponding important queries that improve the branch coverage. See Figure 14]and Figure
22

---

Published as a conference paper at ICLR 2022
Program
def run ()
if markersPresent:
putMarker
if not rightIsClear:
putMarker
pickMarker
turnRight
repeat R=2:
turnLeft putMarker
putMarker
move putMarker
10
10
Figure 14: An query example of Karel. The number the cell denotes the amount of markers.
23

---

Published as a conference paper at ICLR 2022
Program
def run ()
10
10
10
10
10
repeat R=2:
putMarker
turnRight
if frontIsClear:
putMarker
putMarker
turnRight
putMarker
while rightIsClear:
move
move
pickMarker
turnRight
turnleft
turnLeft
move
putMarker
turnLeft
10
Figure 15: Another query example of Karel. The number in the cell denotes the amount of markers.
24


Reviews:
[{"review_id": "OZJIKa4Dx5c", "reviewer": "Reviewer_KXs9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "The problem of generating appropriate unit tests in an interactive manner and has the potential to be a key ingredient in future programming workflows. However I think the paper as written needs improvement before it can be accepted. In particular, I think the following points need attention :-\n\n(1) They say that the Product of normal distributions is a normal distribution but that's not necessarily the case in general - for example see https://math.stackexchange.com/questions/101062/is-the-product-of-two-gaussian-random-variables-also-a-gaussian/101120#101120\n\n(2) Sanity checks :-\n  (a) I would expect the merged unit test distribution to be lower entropy than the distribution of the individual unit tests (as more unit tests mean the functions satisfying them are fewer). This is something that should be examined.\n  (b) They don't test whether the program they synthesize in the end has a high probability under the merged unit test normal distribution vs a  program that doesn't satisfy those unit tests\n\n(3) Interactive unit test generation has been looked at in the past and it's unclear the different ways in which their setup differs. It's also unclear what assumptions they are making that guide their design choices (along with theoretical or empirical validation for those assumptions). Some illustrating examples would help develop their intuition here.\n\n(4) They should compare against more baseline methods. For example they mention Padhi et al. which present multiple queries to the user and let the user pick which one to label. This they claim puts additional burden on the user. But they could still compare against Padhi et al. in a way that's fair to them by selecting for example a query at random for the user to label out of the ones that Padhi et al. suggest.\n\n(5) The empirical results with the baselines they compare against aren't very compelling. For example they are much worse in the Searching for Semantics metric for list processing task compared to the baseline methods and only very marginally better in the searching for exact match metric. They also don't give error bars for their results.", "summary_of_the_paper": "The authors propose a framework to generate unit tests by generating candidate inputs for which labels are queried from an oracle. The idea is to have a vector space where each point represents a function (different programs that are functionally equivalent map to the same point) and a unit test is represented as a set of points that correspond to functions that would pass that unit test. \n\nThey project a unit test onto a normal distribution on the function space where the probability of the distribution is whether a point is the underlying function to be synthesized given the unit test. \n\nThey merge multiple unit tests using an attention mechanism into a single point in the function space and then train the unit test generator such that the mutual information between the probability distribution on the merged unit test and the probability distribution on the programs is maximized using InfoNCE loss.\n\nA synthesizer network is used to synthesize the program from generated unit tests. They test on Karel and list processing task.", "summary_of_the_review": "The problem is interesting but the paper suffers from some incorrect claims, insufficient motivation and justification, and underwhelming empirical results. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "N9FxYCrUt9O", "reviewer": "Reviewer_WAY8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "## what I like about this paper\n\nI really liked the F-space formulation, it is very clever and intuitive to map single functions p to points, and sets of examples e to distribution of points, it is a \"by definition\" representation that captures the relationships between examples and programs in a learned embedding. the operations over this space is also well-justified, with algebraic manipulations of the example embedding such as union and intersections very cleanly explained.\n\nAlgorithm 1. is cleanly written, I was able to follow it well other than line 11 and 12 (see question below)\n\nI personally liked the choice of functionally equivalent proxy for evaluation. \"if the predicted program satisfies all 100 examples, then it is functional equivalent to the ground-truth program\". It is a very practical choice and and also a fairly thorough one.\n\nThe results seem convincing to me, implementing a query generator for the space of Karel and list-manipulation is very impressive, as these are fairly high-dimension spaces, and much work must have been put into making it all work out.\n\nOverall this is a solid work that (appears to me) is written by a group who understands the landscapes of neuro-guided program synthesis well.\n\n## what this paper needs work on\nThis paper would be much stronger if the following points can be addressed.\n\n### the exposition\nwhile the technical aspect of the paper (F-space, its learning objective, evaluation) are sound, the problem statement can be cleaner. the current paper does not draw a clean distinction between \"the problem statement\" and \"the proposed algorithm\". as a result, the paper reads like a long todo list of \"we need to do this, then did that, oh by the way we need to make this differentiable because neural networks\" and as a reader I'm left confused as to what the actual problem is that we're solving. for instance, in definition 2.3, it tells me what a querying algorithm is doing, but it doesn't tell me at all _why_ we need to query or _what_ are we querying for.\n\nto be constructive, I would add a \"problem statement\" subsection before \"problem formulation\" that formally define what exactly is the problem we're solving. specifically, one might borrow the terminologies of active diagnostics / bayesian optimization, that of the \"acquisition function\": given a set of possible query points X, the acquisition function a(x) scores all possible query points x \\in X, and the querying algorithm picks the x with the highest score. in this particular work, the acquisition function is that of mutual information I([[e]], p), which is to say, given a set of (potentially empty) observed examples so-far {(x1,y1)...(xt-1,yt-1)}, we wish to have the query network pick a next query point x_t such that the acquisition function of mutual information I([[e + (xt, yt)]], p) is maximized. _only then_ can one jump into the explanation of F-space and related techniques of solving this querying problem. \n\ncurrently, the relationship to mutual information (the objective that the query network is optimizing for) is only mentioned in equation (7), almost as an after-thought. this is incredibly confusing because I am left clueless what problem the paper is actually solving while reading the answers to this mysterious problem (think hitchhiker's guide, where the answer is 42 but the question is unstated).\n\nSince we use the same acquisition function both in training the synthesizer and at inference time to query, the synthesizer receives the examples from the same distribution, thus, we do not run into the problem of out-of-distribution examples at inference time. The paper definitely makes an attempt to make this claim, but it is unclear in the current version. I believe once the problem statement is cleanly defined, this contribution can be stated cleaner as well.\n\n### other baselines\nCurrent approach only compares against a weak random baseline, while there is merits to it (one can argue random examples is the standard for synthesis benchmarks), the paper can be much stronger with these additional baselines:\n\n1) query by committee. this is a standard approach in active diagnostics where one keeps a sampled distribution of valid hypothesis, then select the query point that maximizes disagreement. specifically, given current set of examples e = {(x1,y1)...(xk,yk)}, we can sample the a program synthesizer to obtain multiple programs that are consistent with e: p1, p2, ... pn, then, use 100 randomly sampled inputs (same as your testing procedure) to discover if there is an input x that maximizes disagreement between these programs. Terminate early of the synthesizer can only propose functionally equivalent programs over the 100 sampled inputs. See https://dl.acm.org/doi/pdf/10.1145/130385.130417 for a similar set up, albeit over a simpler domain.\n\n2) end-to-end RL. one can train a query proposer jointly with a synthesizer in an end-to-end communication setting, where one jointly optimizes (over both the query NN and the synthesizer NN) the probability of the synthesizer recovering the ground-truth program p, given the observation sampled by the querying NN (x, p(x))\nSee https://arxiv.org/pdf/2006.00418.pdf for an end-to-end communication game set up, albeit over a simpler domain. I believe the same gumbel trick would work here as well.\n\nI would expect a replication of 1), as it is by far the most standard approach in active diagnostics, and is incredibly easy to implement and used widely in practice. 2) might be more difficult to replicate, I am okay not seeing it. I believe 1) and 2) serve as strong, yet standard baselines that this work should compare itself to, and I am fairly confident the proposed method of this work would out-perform both 1) and 2), seeing the proposed approach demonstratively out-performs 1) and 2) will make me much more confident in this work.\n\n### related works\n\nThere are very relevant prior works that studies the relationships between optimally querying examples for program synthesis from an information theoretic perspective:\n[1] https://arxiv.org/pdf/1704.06131.pdf\n[2] https://arxiv.org/pdf/1711.03243.pdf\n\nSpecifically, these works formally justify the strategy of greedily picking the next query (i.e. picking x_t that greedily \"maximize the mutual information between the input-output examples [[e]] and the corresponding program p\", same as this work) as more than a heuristic, but is in fact (1-1/e) as good as the globally optimal solution that picks (globally) a set of k examples that maximize the mutual information between [[e]] and p. The proof involves showing that adding examples is monotonic and sub-modular in reducing the set of satisfiable programs.\n\nFurther, [1] studies the exact same problem as this work: How do you optimally query a set of observations for program synthesis? And also propose a similar querying NN that selects which next point to add, however, unlike this work, they assume the space of query points can be enumerated. Thus, one can view this work as solving a much needed algorithmic improvement to [1], by making a querying NN that can _generate_ new query points. Explaining the relationship between this work and [1,2] would help contextualizing this work better.\n\n## questions:\n\n- line 11 and 12 of algorithm 1 is bit unclear to me. The decoder makes a choice for the next query point x_t, but since the rest of the loss requires one to query the oracle p(x_t), the gradient cannot \"go through\" this sample step. typically this is learned using policy gradient or some RL objective, because presumably we cannot teacher force the correct x_t, because it amounts to sampling, from the space of all possible query points X, the best one that helps the identification of p. how is this done? (edit: ah gumbel trick. very nice!)\n\n- how do you obtain negative samples? i.e. \" we construct positive pairs {([[e]], p_i)} and negative pairs {([[e]], p_j )|i != j}. \" how does this work? presumably you want to sample p_j in such a way that p_i and p_j are functionally equivalent over [[e]] yet distinct over some other query points (i.e. exactly the x your query network should produce). however sampling this p_j that is consistent to p_i sofar over [[e]] yet still distinct to some unseen x is a challenge of its own, so you adopted to just sample a \"random p_j\" if I understand correctly. is this the case? if so it probably should be justified, at least with a few words why this particular form of contrastive learning is a good choice here.\n\n- is the synthesizer trained completely de-coupled from the latent representations of the querying NN? I'd imagine the embedding [[e]] be quite helpful, you just have to decode from it to obtain the correct program. but it is good either way, I would personally find the paper stronger if the synthesizer is completely decoupled, i.e. does not rely on [[e]] in any way just to prove a point that one could use any \"back-end\" synthesizer they want.\n\nminor:\n\n- in abstract, what does the phrase \"actual distribution\" mean? the distribution that end-user would use to communicate their intent? a distribution of input that would allow the program to be uniquely identified from all the space of programs unambiguously? or is it just \"the training distribution\", which is what I believe it to be after reading the intro.\n\n\n\n", "summary_of_the_paper": "This paper considers an active diagnostic setup for program synthesis as follows: There is an oracle function/program p* belonging to a space of functions, and at inference time, one would like to uncover p*. To do so, a querying algorithm iteratively/adaptively query the oracle with inputs x1, x2, ... xk, receiving outcomes y1, y2, ... yk in return. A synthesizer (or any inverse model capable mapping observations to hypothesis, doesn't really matter) then proposes a guess p' based on the collected query-observation pairs (called examples) {(x1,y1)...(xk,yk)}. One \"wins the game\" if p* and p` behave the same way (functional equivalent) on all inputs, using as few queries (i.e. small k) as possible.\n\nTo do this, the paper introduce a learned F-space, which both functions f and sets of examples e can map into. While functions map (using a learned embedding) to single points in F-space (each point in F-space represent a unique function), examples map (using yet another learned embedding) to distributions in F-space (each example set represent a _distribution of_ functions that are consistent with it). The querying network is trained to generate the next observation x conditioned on the existing observations {(x1,y1)...(xk,yk)} in such a way that maximally reduce the uncertainty of the F-space once the new example, (x, p*(x)) is augmented to the existing observations.\n\nResults are convincing to me.", "summary_of_the_review": "Overall I liked the paper, as it solves 2 key challenges of program synthesis:\n1. The training distribution of the synthesizer does not match the testing distribution\n2. One would like to recover the target program with as few examples as possible\n\nIt solves both problem by \"mocking\" the active diagnostic process of (2) in training time, having a trained querying network to propose the most informative queries. To build a querying network, the proposed method embed both programs and examples in a joint F-space, and use contrastive learning to train the querying NN to propose query points that maximally distinguish the target program p from distractor programs p'. The construction of F-space is both intuitive and algebraically elegant.\n\nResults give good evidence of the proposed method as well.\n\nThis paper would be stronger if the 3 points mentioned: exposition, other baselines, and related works can be addressed, I am willing to raise the score accordingly.\n\nThe author addressed the 3 points mentioned, so I am raising the score as I said I would. Although there is no score of 7, I meant a 7 instead of an 8 as the baseline (QBC) is still fairly close to the proposed method, and is derived in much less time (a week).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CybYCpN_DgS", "reviewer": "Reviewer_Ytee", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "Strengths: \n- The interactive framing of the problem is useful to explore. For program synthesis from input-output examples, there often is an implicit oracle for the unknown program that the user can use, even if it is not cheap to compute. If the user has to decide the input-output examples without guidance, then the set may not end up being very informative at distinguishing between possible programs. By having the synthesizer query the user for inputs interactively, it can obtain the specification most useful for generating the right program.\n- The F-space formalism is a nice way of thinking about the space of programs and functional equivalence, although it is not practical (as it requires enumerating all possible inputs to the programs) and the definition seems unlikely to be novel in the literature.\n\nWeaknesses:\n- The modeling of F-space and sets of input-output examples as normal distributions seemed inappropriate. In particular, equation 3 states that we want to model the intersection of two sets by intersecting the distributions (taking a product of the pdfs?) but then equation 4 goes onto take a weighted sum of the mean and log of the variance parameters. Equations 4 and 5 cite Ren & Leskovec 2020, but that paper took weighted sums of Beta distribution parameters, not normal distribution parameters.\n- The paper does not provide all details necessary to reproduce the results (see suggestions for more details).\n- The paper doesn't describe what happens for invalid inputs to programs (i.e. inputs which cause the programs to crash). For example, in Karel, it is not allowed to take a marker from a cell containing no markers.\n\nSuggestions:\n- Provide greater details necessarily for reproducibility of the paper. Various details that were necessary to obtain the results are obscure in the appendix and not described elsewhere. Examples:\n  - Query decoder for Karel: if it is similar to the query encoder, how does it generate a grid world state as the output?\n  - Query decoder for list processing: since input examples \n  - \"additional batch normalization is added to keep the generation more stable\": how was this done?\n  - \"we introduce a latent code like InfoGAN\": this can be described more precisely, including with equations\n  - \"we add the reciprocal of the KL divergence [...] this loss does not have a significant impact on training most of the time and makes the \ntraining process unstable\": If the loss was not useful, then was it still kept?\n  - \"At the beginning of the training, the query network generates one query only. As the training goes on, the number of query times increases until it achieves the query time limit.\": How was the number of generated queries increased over time? Why is the curriculum necessary?\n  - \"to guarantee that every query can be recognized by the program simulator, we design the output layer of the query network elaborately.\": it is not clear what was done in the output layer to guarantee this.\n- Add a prior to F-space and use it to generate the best queries. The set of all possible programs is very large or infinite, but the set of useful programs that the user might want is smaller. It should be possible to learn the prior distribution (or assume one like Occam's razor) and use it to inform the next query.", "summary_of_the_paper": "In neural program synthesis from input-output examples, the goal is to generate a program which, when executed on the inputs, produces the corresponding outouts. Typically, the set of input-output examples is taken as given by the program synthesis method. In this work, the authors propose to instead have the program synthesizer interact with an oracle to determine the set of input-output examples. The synthesizer proposes a potential input for the program, the oracle produces the output, and the process repeats. Under this paradigm, the program synthesizer can query the oracle for the inputs which would be most helpful in determining the correct program. This direction has been explored in prior work as \"interactive program synthesis\", but largely with constraint-based methods.\n\nThe paper represents each input-output example pair as a normal distribution (with a mean and variance parameter). A set of input-output example pairs is also represented as a normal distribution, with its parameters a weighted sum of each pair's parameters. A neural decoder module takes the mean/variance of this combined distribution as input to produce a new input; we can query the oracle with the input to get the output, resulting in a new input-output example pair.\n", "summary_of_the_review": "The paper has a useful motivation and explores interesting idea, but the aspects of the execution and the missing details in the work make it difficult to recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses an important problem of selecting inputs to drive an inductive program synthesis process. This is an important problem because inductive synthesis relies on carefully chosen inputs to ensure that the chosen inputs can provide sufficient information about what the desired program is. This paper proposes an approach where instead of simply asking the user to provide a set of input/output examples to the synthesizer, the user interacts with a query network that queries the user on the output of specific inputs and these input/output examples are then fed into an existing program synthesis engine.  

I think the ideas in the paper are very original and I agree with reviewer WAY8 that this paper should be accepted. I think the original version of this paper had several issues that led to the low scores from the other reviewers, but the paper improved significantly with the review process. 

That said, I do think that some of the concerns of the other two reviewers are valid, and some additional steps could be taken to address them. For example, the paper follows a long tradition in ML of making assumptions that are questionable but that make the math work nicely (e.g. choosing to represent things as gaussian distributions, or assuming independence for things that are clearly not independent). We are usually ok with such shortcuts if they are properly acknowledged and the resulting method proves to work well empirically, but the original set of experiments in the paper was extremely minimal. That said, the experiments added through the rebuttal process give me more confidence that even with the mathematical shortcuts, the method still works well.
Decision: Accept (Poster)