Adversarial Synthetic Datasets for Neural Program Synthesis
Authors: Alexander Suh
Yuval Timen
Venue:  (2021)
Keywords: Program Synthesis
Synthetic Data
Evolutionary Algorithm

Abstract: Program synthesis is the task of automatically generating a program consistent with a given specification. A natural way to specify programs is to provide examples of desired input-output behavior, and many current program synthesis approaches have achieved impressive results after training on randomly generated input-output examples. However, recent work has discovered that some of these approaches generalize poorly to data distributions different from that of the randomly generated examples. We show that this problem applies to other state-of-the-art approaches as well and that current methods to counteract this problem are insufficient. We then propose a new, adversarial approach to control the bias of synthetic data distributions and show that it outperforms current approaches.

Under review as a conference paper at ICLR 2021
ADVERSARIAL SYNTHETIC DATASETS FOR NEURAL PROGRAM S SYNTHESIS
Anonymous authors Paper under double-blind review
ABSTRACT
Program synthesis is the task of automatically generating a program consistent with given specification. natural way to specify programs is provide ex- amples of desired input-output behavior, and many current program synthesis ap- proaches have achieved impressive results after training on randomly generated input-ouiput examples. However, recent work has discovered that some of these approaches generalize poorly to data distributions different from that of the ran- domly generated examples. We show that this problem applies to other state-of- the-art approaches as well and that current methods to counteract this problem are insufficient. We then propose new, adversarial approach control the bias of synthetic data distributions and show that it outperforms current approaches.
INTRODUCTION
Program synthesis has long been key goal of Al research. In particular, researchers have become increasingly interested in the task of programming by example (PBE), where the goal is to generate program consistent with a given set of input-output (I/O) pairs. Recent studies have achieved impressive results, capable of solving PBE problems that humans would find difficult (e.g.. Sharma al. ( Zohar Wolf (2018); Ellis et al. (2019)). However these studies have concerning weakmess: since large, naturally occurring datasets of program synthesis problems do not exist, these studies train and test their models on synthetic datasets of randomly generated programs and 1/O pairs. The justification for using these synthetic datasets is that if model can correctly predict programs for arbitrary PBE problems, then it has likely learned the semantics of the programming language and can generalize problems outside the synthetic data distribution (Devlin al. 2017).
While this justification is plausible, model might also perform well because has learned specific aspects of the synthetic data distribution, and recent studies have found this be the for several state-of-the-ane models (Shin et al.) 2019 Clymo et al., (019). These studies find that current PBE models often perform poorly on distributions different from that of the training data, and they pro- pose methods to mitigate this issue by generating synthetic data with more varied distributions. The idea behind these methods is that model trained more varied synthetic data should generalize to wider variety of distributions, hopefully including those of real-world PBE problems.
Nevertheless, we find that these methods are often insufficient. Previous studies differ on what constitutes a "varied distribution" of synthetic data, creating definitions based on problem-speciffic heuristics. While generating training data based on these heuristics does help models generalize to certain distributions, we find that models trained using these methods still fail to generalize to many other distributions, including those resembling distributions real-world problems.
Moreover, different methods fail to generalize to different distributions, raising the question of how one should construct test sets to evaluate these methods. While previous studies have arbitrarily picked test sets that they believe present reasonable challenge for state-of-the-an methods, this approach may lead to overly optimistic evaluations. A study may report that a method performed well because the researchers failed to find those distributions which the method performs poorly.
In this paper, we propose an adversarial method to generate a training set. Our adversarial approach builds a training set iteratively, finding data distributions which given model performs poorly and adding data drawn from those distributions to the training set on each iteration. We test this method by using it generate training data for the PCCoder model from Zohar & Wolf (2018), and

---

Under review as a conference paper at ICLR 2021
show that models trained using method generalize to a variety of distributions better than previously proposed methods. Moreover, we propose using a variation of our adversarial approach to generate test sets to evaluate PBE methods. We create test sets for different versions of PCCoder using this approach and show that these test sets reveal weaknesses in models that are not obvious when using other test sets.
This paper makes the following key contributions:
1. We propose a new, adversarial method to generate desirable distributions on which to train models for PBE.
2. We show that models trained using our method generalize to variety of datasets better than models trained using previously proposed methods.
3. We show that our adversarial approach may also be used to generate test sets that are less likely to overestimate the performance of model.
2 RELATED WORK
Most studies on PBE methods generate 1/O pairs using random sampling schemes, filtering out in- valid I/O pairs for each program by constraining the sample space and rejecting sets of 1/O pairs that do not meet these constraints. Ballo et al. (2016) construct dataset of PBE problems for DeepCoder by enumerating programs up to a given length and removing programs with easily de- tectable issues (e.g., redundant variables). For each program generated, they then create I/O pairs by sampling inputs uniformly from a restricted range of values guaranteed to yield valid outputs for the given program. FFen et al. (2018) and Zohar & Wolf (2018) also create datasets using the DeepCoder DSL (domain-specific language) in a similar manner.
Bunel et al. (2018) generate PBE problems for Karel (Pattis 1981) by randomly sampling programs from the Karel DSL. and removing programs with obvious problems, similar to Balog et al. They then generate I/O pairs for each program by sampling random inputs and running the program to obtain the corresponding outputs. However, Bunel et al. do not specify what sampling distributions are used for the programs and I/O pairs.
Parisotto et al. Parisotto et al. (016) create a dataset for the Flashfill domain (Gulwani et al. 2012) by enumerating programs up
expressions long and then randomly sampling inputs create 1/O pairs. They report that while their model achieves 97% accuracy on their synthetic data, they achieve only 38% accuracy on small dataset of 238 real-world problems. Devlin af. (2017) use a data generation approach similar to Parisotto et al. but with an improved model and are more successful, achieving 92% accuracy on the same real-world dataset used by Parisotto et al.
All of the papers above focus on advancing models for PBE, but they do so largely using synthetic data to train those models. [Shin et al. (2019) report that even minor differences between the synthetic data distributions used for training and evaluation To solve this problem, they propose a data generation method to improve a model's ability to gener- alize other data distributions. They first choose of "salient variables" for the domain, defined as a mapping from IO pairs in the synthetic dataset to a finite, discrete set. They then sample 1/ pairs such that the salient variables will be approximately uniformly distributed in the resulting dataset. Shin et al. find that the model proposed by Bunel et al. (2018) better generalizes to a variety of distributions when trained with data generated with this method. However, this method has two major disadvantages, First, it requires the user to determine the correct salient variables, which may be difficult for complex domains. Second, if the domain of valid I/O pairs is highly dependent on the program, it is often prohibitively complex to enforce uniformity across salient variables.
drastically decrease model's performance.
Recently, Clymo al. (2019) proposed a method to generate PBE problems using SMT solver. They impose constraints on the I/O pairs to ensure that pairs selected for the dataset are not too similar to each other and then select I/O pairs that satisfy these constraints using a SMT solver. However, when testing an implementation of this method on the DeepCoder domain, the reported improvement of the constraint based methods over simpler sampling methods is marginal, with the best constraint-basee based method performing only 2.4% better than the best sampling method. More- over, many of their constraints are highly specific to the DeepCoder domain, and Clymo et al. do not offer way to adapt their method to other problem spaces. Nevertheless, they present method
2

---

Under review as a conference paper at ICLR 2021
that does not require the salient variables of [Shin et al. (2019), and they show that their approach can be applied to domains such as DeepCoder, for which it is difficult to enforce uniformity across salient variables.
Our adversarial method is closely related to the literature on adversarial training. Most similar to our work is that of Volpi et al. (2018), who propose adversarial training procedure learn models resistant to covariate shift. Given a model M trained on data from a given domain X, Volpi et al. generate synthetic training data by sampling data points for which M performs poorly, under the constraint that the sampled data points must be within a certain Wassertein distance p from X. By retraining M on the synthetic data, Volpi al. create a new model resistant to covariate shifts of magnitude p. However, a key difficulty in applying their method is that the user must predict the magnitude of a covariate shift before actually occurs in order to select p. Moreover, our approach differs from that of Volpi et al. in that our goal is to train model to generalize to virtually any distribution of data valid for a given programming problem, where as Volpi et al. try to train a model to be resistant to single, anticipated covariate shift. Our method also does not require the user to predict a hyperparameter such as p to train a model.
Other studies have also proposed adversarial methods to generate synthetic training data (e.g., Good- fellow et al. (2013): ; Sinha et al. (2020). However, these methods try to train a model to be resistant to imperceptible ad adversarial attacks, which make small perturbations to training examples such that the perturbed inputs cause the target model to output incorrect answers with high confidence. Our method tries train model generalize to all valid data distributions, not just the small perturba- tions found in adversarial attacks.
Some studies have proposed iteratively constructing training sets based on the concept of "surprise." In the field of program synthesis, Pu et al. (0177) generate I/O pairs to specify a program by first generating a large set of candidate 1/O pairs and then iteratively selecting the I/O pairs from this set that are most surprising, where surprise is estimated using neural network trained to predict which I/O pairs will be selected (I/O pairs assigned lower probabilities by the neural network are more surprising). Pu et al. use this approach to ensure that their I/O pairs are sufficient to specify desired programs unambiguously. In contrast, our approach tries to find and generalize to out-of- distribution data, and therefore generates I/O pairs to maximize the difficulty of the resulting PBE problems rather than maximizing surprise.
Our adversarial method uses evolutionary algorithm to find desirable training distributions. This approach is similar to that of studies on competitive co-cvolution (c.g.. Rosin & Belew (1997); Arcuri & Yao (2007). For example, Arcuri & Yao (2014) co-evolve populations of programs and populations of unit tests given a formal specification of a desired program. The fitness value of a candidate program depends
how many unit tests it passes, while the fitness value of candidate unit test depends on how many programs it causes to fail. However, the goal Afrrru & Yao (2014) and similar works is simply generate vanilla program synthesis algorithm capable of generating a program given its formal specification. They do not try to ensure that their algorithms generalize to different data distributions as we do (e.g., their algorithm might only work for certain distributions of formal specifications). Furthermore, in order to compute fitness values, co-evolutionary methods require the user to provide a formal specification of the desired program (e.g., using Z notation (pivey & Abrial 1992)). Our approach only requires the user to provide I/O pairs describing the behavior of a desired program, which tend to be easier to provide than a formal specification (Palshikar 2001
3 METHODOLOOGY
We propose an iterative, adversarial approach to build a synthetic dataset of PBE problems. Given a PBE model trained on a given dataset, we use evolutionary algorithm to find data distribution on which this model performs poorly. We then add PBE problems drawn from that distribution to the dataset and train new model on the new, larger dataset. We then repeat the steps above using the new model and new dataset. Appendix A provides pseudocode for this process.
The evolutionary algorithm works as follows. Let & be the space of programs in our DSL, and let I x O be the space of I/ pairs. Suppose we have a model M x O - D. and we select family of data distributions of the form D(17)= + [0, 1), where j are the parameters of the distribution.
3

---

Under review as a conference paper at ICLR 2021
We create population of distributions D(7"), 0 iis n, with randomly selected parameters
IT'. We then draw a set of PBE problems S, c ((0,i,0) E ①b x 0 o(i) = o} for each distribution D by sampling o uniformly from 4, sampling from I according to D and
setting = Φ()). Next, we calculate fitness scores
F(S.) H(0,2,0) E S; M + oH
15:
where Mi, is the program returned by M for (i, We choose the n distributions D( with the highest fitness scores F(S.). We create a new population of distributions by adding the m fittest distributions the new population and then for each D(7") within the fittest distributions, we sample n/m- - 1 new distributions D(7 + t) and add those to the new population (where e random variable of our choosing). We then repeat the steps above with the new population. Appendix B provides pseudocode for the evolutionary algorithm.
One might be concerned that our evolutionary algorithm could return distributions on which a given model performs poorly due to ambiguity rather than overfitting. For example, a model given I/O pairs of all zeros likely will not return the underlying program, since many programs could poten- tially create those I/O pairs. However, it is important to note that in the DeepCoder domain, as well as other program synthesis domains, a model given a problem (ø. i, o), where ((i) o, need not return d. To solve the problem, the model may return any program that maps to making am- biguous I/O pairs, such as those containing only zeros, easy to solve. Therefore, we are confident that distributions returned by our algorithm will be those for which the model performs poorly due to overfitting on synthetic data rather than ambiguity of examples.
An obvious disadvantage explored by the evolutionary algorithm. Nevertheless, we believe the task of choosing a space of distributions be less difficult than the tasks of choosing salient variables (Shin et al. (019)) SMT constraints (Clymo et al.) 2019) necessary for previously proposed methods. Whereas the correct choice of salient variables or SMT constraints may not be intuitive, we argue that the guidelines for choosing a space of distributions for our approach are relatively simple: one should choose the largest space of distributions that can feasibly be searched by the evolutionary algorithm. A larger space of distributions will allow our algorithm to generate more varied training data at the cost of being more difficult to search.
approach is that must choose the space of distributions to be
A second disadvantage to our approach is that its runtime is quadratic in the number of iterations, since each iteration requires us to retrain M on a larger and larger training set (assuming the time it takes to train M is linear in the size of the training set). In the experiments below, our approach increased training time from about 12 hours to several days for PCCoder and from 30 minutes to hours for Karel. However, we argue that this increased runtime is not as bad as it may seem. First, there are multiple ways to adjust the runtime. For example, one could generate more PBE problems per iteration and use fewer iterations, or one could decrease the size of S,, decreasing runtime at the cost of increasing the variance of the fitness scores. Furthermore, our approach only increases training time and does not increase the time it takes to synthesize programs for end users.
4 EXPERIMENTS
The DeepCoder DSL (Balog et al. 2016) is language for manipulating lists of integers, capable of expressing complex behaviors such as branching and looping. To evaluate our approach, we generate synthetic data train PCCoder (Zohar & Wolf, 2018). which solves PBE problems from the DeepCoder domain using beam search guided by neural network. In this section, we first discuss the implementation of our adversarial method for the DeepCoder domain and then test this implementation against previously proposed methods.
4.1 EVOLUTIONARY ALGORITHM
To implement our evolutionary algorithm, we need to define the space of data distributions our al- gorithm will explore. The DeepCoder DSL uses integers between -256 and 255 and lists of integers
4

---

Under review as a conference paper at ICLR 2021
with lengths between 1 and 20. Therefore, can define simple data distribution with four param- eters: lower and upper bound for integers (a. b -256 I a I b I 255) and lower and upper bound for list lengths (c, d 1 c S d I 20). For any integer input. from discrete uniform(a, b). For any list input, we draw a list length from discrete uniform(c. (c, d) and then draw 1 integers from discrete uniform(a, b) to fill the list. Our evolutionary algorithm will explore the space of all such distributions.
then draw an integer
To calculate the fitness function for distribution, we draw 100 problems of program length from the distribution and run our model on each problem with a timeout of 60 seconds. When evaluating models in our experiments, we use test sets with program lengths of 5, 8, 10, 12. and 14, and we use a timeout of 300 seconds. However, running models on programs longer than 5 lines with a timeout of 300 seconds would cause our evolutionary algorithm to take prohibitively long to run, so we use shorter programs and timeouts to estimate fitness of distributions.
Next, we define the random variables we will use to mutate our distributions. We mutate integer bounds by adding values drawn from U U--250/2 250/2"), where i [0,5] is the index of the current iteration of the evolutionary algorithm (starting at 0). We mutate list length bounds by adding values drawn from (-220/2', 20/2*). Since the bounds of these distributions decrease on each iteration, our evolutionary algorithm is able to explore a wide variety of distributions in earlier iterations and then make smaller adjustments during later iterations.
Finally, we describe how we initialize our population of distributions. As observed by Clymo et al. (2019), smaller input values are valid for more programs in the DeepCoder DSL. Therefore, to speed up training, we initialize a and b from N(0, 10) rather than U(- U--2566 255) to make it more likely that initial distributions will generate valid I/O pairs. While one may worry that using (0, 10) will prevent our algorithm from exploring larger values of a and b, recall that we initially mutate our distributions with a random variable uniformly distributed between 250 and 250. This allows our algorithm to explore the entire space of available distributions.
One might wonder why our approach adversarially generates inputs but not programs. While one could adapt our evolutionary algorithm to ad adversarially generate programs as well, we found that manipulating distributions of programs in test sets did not affect the accuracy of PCCoder. Similar to Shin et al.) (2019), we created two test sets in which we changed the distributions of programs but left the distribution of 1/O pairs identical to that of the original PCCoder training data. In one test set, we did not allow any programs using higher-order functions, and in the other, we did not allow any programs using first-order functions. Neither test set produced any drop in accuracy when used to evaluate PCCoder. Since PCCoder seems to generalize well across different distributions of programs but not different distributions of I/O pairs, we limit our evolutionary algorithm to the generation of inputs. This makes evolutionary algorithm more efficient, since its search space is smaller.
4.2 BASELINES
We compare our approach to three previously suggested approaches. First, we use the approach used by |Balog et al. (2016), Feng et al.) (2018), and Zohar & Wolf (2018) to generate data for DeepCoder, which we call Restricted Domain. This approach imposes a set of program-dependent constraints on inputs that ensure the corresponding outputs are valid. While this approach removes all invalid I/O pairs when generating examples, the constraints are overly strict and remove many valid I/O pairs as well.
Second, we use the approach proposed by (Shin et al. (2019), in which we choose set of what they call "salient variables" and then try to ensure a uniform distribution of those variables in our dataset. We describe Shin et al.'s algorithm to ensure uniformity of salient variables Appendix C. For our salient variables, approach: the minimum and maximum integers of the inputs and the minimum and maximum list lengths of the inputs. We call this the Salient Variables approach.
use the same variables that define distributions selected by our evolutionary
Finally, we use an approach called Non-Uniforn Sampling proposed by Clymo et al. 2019). For given program, generate value r from exponential distribution. The input values for I/O pairs are then selected uniformly at random with replacement from the range [-r, r). The intuition behind this approach is that smaller input values are valid for more programs in the DeepCoder DSL.,
5

---

Under review as a conference paper at ICLR 2021
so sampling with bias toward smaller values increases the probability that suitable inputs will be found for all programs, Clymo et al. report that they choose a rate parameter of 0.001 for their exponential distribution. However, exponential distribution with a rate parameter of 0.001 has mean of 1000, well above the maximum valid value in the DeepCoder DSL of 255. Therefore, we pick of rate parameter of 0.01 for our experiments.
Clymo et al. also propose an approach they call Semantic Variation. In this approach they constrain input and output values using constraints that help ensure that I/O pairs selected will be varied. They then use a SMT solver to generate I/O pairs that satisfy these constraints. While we would like to use this approach as a baseline, Clymo et do not specify how they encode the constraints that for input and output o selected for program @, Φ(i) and i * o(i). This missing detail is important, since Clymo et also report that the DeepCoder DSI. is too complex to encode such constraints for certain programs á and therefore resort to unspecified approximation of those constraints. However, Clymo et report that semantic variation performed only 2.4% better than non-Uniform Sampling when comparing area under top-k curves, we believe the inclusion of Non- Non-Uniform Sampling to sufficient for our experiments.
To compare the above approaches with our own, we generate datasets using each approach and then train the PCCoder model using each dataset, creating four differently trained PCCoder models (three trained using the baselines and one trained using approach). Each dataset contains 300,000 PBE problems. To create our adversarial dataset, we first train PCCoder on 140,000 problems generated using Restricted Domain as Zohar & Wolf (2018) did for the original version of PCCoder. Using this model for the first iteration, we then add 160,000 problems generated using 20 iterations of our adversarial algorithm, for a total of 300,000 problems (the same number of problems generated for the baselines).
We test our four models on five test sets: three test sets generated using the baselines and two test sets generated from distributions we believe would be common among human- generrted examples. We generate the test sets have the same size and program lengths Zohar Wolf (2018): each test set contains 2500 programs of lengths 5, 8, 10, 12, and 14 (with 500 programs of each length).
To create the two test sets generated from "human-like" distributions, we first observe that while no large-scale dataset of human-generte generated examples exists for the DeepCoder domain, |Balog et al. (016)) and Zohar& & Wolf (2018) provide several human-created examples of DeepCoder problems in their figures. An immediately noticeable discrepancy between the human-created I/O pairs in the appendices and the synthetic I/O pairs used in those studies is that the comman-created I/O pairs use small, positive integers far more frequently than the synthetic data. Moreover, positive integers more common than negative numbers in the human-created data, regardless of the absolute values of the integers. Based on these observations, create two "human-like" test sets:
1. 1-to-10: We generate synthetic data using the constraints from Balog et al. (0016), but we change the valid range for all integers from [-256, 255] to [1, 10).
2. Small Integers: We generate synthetic data using the constraints that integer variables must be between and 10 but integers within lists may be between and 255. We remove the constraints of Balog et al. (2016), since these constraints limited the variety of examples in these particular test sets.
When running our models, we set PCCoder's memory size to 11 and timeout to 300 seconds. We performed all experiments on Intel Xeon 2.30GHz CPUs.
4.3 RESULTS
Table shows the percentage of problems solved by each approach. While some of the baselines slightly outperform our adversarial approach on certain test sets-in particular, each baseline unsur- prisingly outperforms on its own test sets-the adversarial approach generalizes to all of the baseline test sets reasonably well. Whereas the performance of each baseline approach sometimes drops drastically when evaluated on test sets from other baselines, as shown by the bolded accuracies in Table II the adversarial approach performs decently on test sets from all baselines. Moreover, on the human-like test sets, the adversarial approach outperforms all baseline approaches by a significant margin.

---

Under review as a conference paper at ICLR 2021
Table I: Performance of PCCoder trained using Restricted Domain, Salient Variables, Non-Uniform Sampling, and our adversarial method. The worst accuracy of each training method for each program length is bolded.
LENGTH DATASET
RESTRICTED
SALIENT NON-UNIFOMM
ADVERSARIAL
RESTRICTED DOMAIN
94.6%
95.4%
51.8%
94.0%
NON-UNIFORM SAMPLING
18.8 %
21.8%
97.4%
89.0%
SALIENT VARIABLES
95.8%
97.6%
49.8%
94.0%
1-TO-10
60.4%
62.0%
44.0%
70.0 %
SMALL INTEGERS
60.2%
60.2%
55.8%
75.4%
RESTRICTED DOMAIN
60.4%
72.6%
20.8 %
69.4%
NON-UNIFER SAMPLING
17.2 %
17.8%
82.4%
65.6%
SALIENT VARIABLES
72.4%
69.8%
21.4%
63.4%
1-TO-10
31.4%
37.4%
21.8%
39.8 %
SMALL INTEGERS
47.6%
48.4%
42.6%
64.4%
RESTRICTED DOMAIN
48.8%
57.8%
15.2%
53.0%
NON-UNIFORM SAMPLING
16.4%
16.4%
64.8%
50.0%
10
SALIENT VARIABLES 1-TO-10
54.2%
53.2%
11.6%
49.4%
25.2%
28.0%
15.8%
29.2%
SMALL INTEGERS
40.6%
40.2%
35.2%
49.0%
RESTRICTED DOMAIN
36.8%
40.2%
8.0%
33.2%
NON-UNIFOR SAMPLING
6.8%
8.6 %
48.0%
35.6%
12
SALIENT VARIABLES 1-T0-10
43.8%
40.6%
9.0%
38.8%
17.4%
21.2%
12.8%
25.8 %
SMALL INTEGERS
37.2%
39.6%
34.4%
48.0%
RESTRICTED DOMAIN
25.0%
30.2%
8.6%
28.0%
NON-UNIFORM SAMPLING
8.4%
9.4%
37.0%
26.8%
14
SALIENT VARIABLES
32.8%
32.2%
10.0%
30.0%
1-T0-10
18.6%
17.0%
10.6%
22.4% %
SMALL INTEGERS
32.8%
34.8%
30.2%
45.6%
is promising to see that the adversarial approach outperforms the baselines on the small integers dataset in partieular. The small integers distribution outside the space of distributions available to our evolutionary algorithm, so in theory, training data generated by our adversarial approach might not improve performance on this distribution. However, our results show that our adversarial approach was able to generate data drawn from distributions similar enough to the small integers distribution improve performance.
4.4 USING THE ALGORITHM TO MEASURE PERFORMANCE
Previous PBE studies have often evaluated the performance of their models using test sets drawn from the same distribution as the training However, this approach risks overestimating a model's performance, since a model may perform well on test set because it has learned features of the syn- thetic data distribution rather than the semanties of the programming language. Therefore, we argue that PBE model should be evaluated on test set drawn from different distribution than the train- ing set. Naturally, this raises the question of what distribution we should use for the set. this section, we propose using our adversarial algorithm to generate test data from those distributions on which the model performs worst. The intuition behind this approach is that adversarially generated test data should come from distribution as different as possible from the training data by design. If a model can perform well on adversarially generated test data, it has likely learned the semantics of the DSL and is not relying features specific to the training data.
We use this method to evaluate our four versions of PCCoder. For each version of PCCoder, we Algorithm 2 generate dataset of 100 examples with program length 5. Table 2 shows that our adversarial approach significantly outperforms the baselines. We can also see that there exist distributions which models perform far worse than would be suggested by Table [ For

---

Under review as a conference paper at ICLR 2021
Performance of the four approaches test sets generated using evolutionary algorithm. The last column lists the lower and upper bounds for integers and the lower and upper bounds for list lengths for each test set's distribution.
Table 2:
APPROACHES
% SOLVED
DISTRIBUTION
RESTRICTED
6%
58; 16. 19
CON-UNIFORM
51%
2,55; 18,
SALIENT ADVERSARIAL 81%
9%
-6,
10, 20
2, 12; 4, 17
example, while the Salient Variables method achieves an accuracy of least 20% all test sets of length 5 in our previous experiments, our evolutionary algorithm finds a distribution for which this method has accuracy of just 9%.
This evaluation method is far less likely to overestimate performance than those of other studies, which tend to use test sets drawn from the same distribution as the training set or otherwise drawn from arbitrary distributions that the researchers believe will be sufficiently challenging. By testing on arbitrarily chosen distributions, a study may overestimate a model's performance because it over- looked distributions which the model generalized poorly. However, our approach finds the most difficult distribution for a model within given search space, providing a more systematic way to test model's ability to generalize different distributions.
EXPERIMENTS ON KAREL
an educational programming language that produces instructions for an agent (a robot named Karel) in a rectangular m x n grid world. Karel creates imperative programs capable of using conditionals and loops, which make the agent move around and alter its grid world. [Bunel eet al. (2018) propose an algorithm to solve PBE problems for Karel using beam search guided by neural network, which [Shin et al. (209)) use to test their Salient Variables method. Shin et al. show that changes in the synthetic data distribution severely decrease the accuracy of Bunel et al.'s algorithm; they then use the Salient Variables method to solve this problem, almost completely eliminating the drops in accuracy. In this section, generate training set for Karel using adversarial approach, and we show that our approach climinates the drops in accuracy just as well the Salient Variables approach when used to train Bunel et al.'s model. To the best of our knowl- edge, this makes our approach the first to successfully generalize across multiple program synthesis domains (i.e., DeepCoder and Karel).
Karel (Pattis [98]
5.1 EVOLUTIONARY ALGORITHM
Similar to the implementation of our adversarial approach for the DeepCoder domain, we must define the space of data distributions that our evolutionary algorithm will explore. In the Karel DSL, grids can have heights and widths between 2 and 16, and each grid square may contain one of two objects: marker
wall (or neither). We define a data distribution with four parameters: grid height grid width b, wall ratio e (the fraction of grid squares containing walls), and marker ratio d (the fraction of grid squares containing markers). To generate a grid from this distribution, we create an empty a x grid. For each grid square, we place a wall in that square with probability Then, for each grid square without a wall, we place a random number of markers (chosen from discrete uniform( 1, 9)) in that square with probability d.
Similar to our implementation for DeepCoder, we draw 100 problems of program length 5 to cal- culate the fitness function for distribution. We mutate grid heights and widths by adding values drawn from discrete uniform(- -4, 4), and we mutate wall and marker ratios by adding values drawn from discrete uniform( -0.25, 0.25). Since the space of I/O pairs is far simpler in Karel than in DeepCoder, we find that just two iterations of mutations is sufficient when running our evolutionary algorithm.
8

---

Under review as a conference paper at ICLR 2021
5.2 RESULTS
We compare our approach to those of Bunel et al. (2018) and Shin al. (2019). We do not compare our approach to that ofymo et al. (2019), since there is no clear way to adapt their approach for Karel. We evaluate our three approaches three ways. First, we use the original test set provided by Bunel et al. Second, we evaluate the approaches on 12 test sets proposed by Shin et al. These test sets have varying distributions of markers and walls, the majority of which are outside the search space of our evolutionary algorithm. We describe Shin al.'s 's method to generate these test sets in Appendix D. Finally, we evaluate the three approaches using test sets generated using the adversarial method described in Section 4.4.
On Bunel et al.'s original test set, our method performs marginally better than the Salient Vari- ables method, solving 62.60% of problems compared to Salient Variables' 60.68%. Bunel et al.'s method performs best by a large margin with an accuracy 73.44%. The high accuracy of Bunel et al.'s method is to be expected, since Bunel et al. trained their model data drawn from the test distribution, allowing their model to overfit on this test set.
On the 12 test sets proposed by Shin et al., both our approach and the Salient Variables approach greatly outperform Bunel et al. The average accuracy of Bunel et al.s method is 29.61%, %. while the average accuracy the Salient Variables method is 62.46%, and the average accuracy of our method is 62.53%. Similarly, when using test sets generated using the method from Section 4.4, Bunel et al. achieve an accuracy of 21.51 %, whereas the Salient Variables and adversarial approaches achieve 58.97% and 58.22%% respectively. Accuracies of each approach for each individual test set can be found in Appendix E. Clearly, our adversarial method is able to outperform Bunel et al.'s original training method just well as the Salient Variables method.
However, our method does not outperform the Salient Variables method as it did in the DeepCoder domain. We hypothesize that this is because Karel is much simpler problem space compared to DeepCoder. In particular, the space of valid I/O pairs is highly grogram-dependent in DeepCoder but not in Karel. Any valid Karel grid is valid input to any Karel program ó, and the output d(i) is always guaranteed to be a valid grid as well. In contrast, many potential inputs will be invalid for any given DeepCoder program. For example, if a DeepCoder program takes list of integers as input, removes all odd numbers from the list, and then returns the first number, then any list containing only odd numbers is an invalid input for that program. Because the space of valid I/O pairs varies from program to program in DeepCoder, it is much harder to sample inputs uniformly with respect to salient variables DeepCoder than in Karel. Thus the Salient Variables method is able to perform par with our adversarial method in Karel but struggles in more complex domain such as DoepCoder. Our adversarial method, however, able to handle both domains quite well, making it the first such method to generalize across program synthesis domains.
DISCUSSION
Researchers often train PBE models using randomly generated problems, the idea being that a model that can correctly predict programs for arbitrary inputs has likely learned the semantics of its DSL and can therefore generalize to problems outside the synthetic data distribution. However, recent studies have demonstrated that these models often overfit on their synthetic training sets and often generalize poorly to data from even slightly different distributions. We present a new method to generate synthetic data for program synthesis models that mitigates this issue. We show that a model trained with data generated using this method is able to outperform models trained with previously proposed methods on variety of baselines.
Moreover, we show that our method can be adapted to generate test sets. Previous studies have chosen distributions for synthetic test sets either by reusing the distribution of the training data or by arbitrarily picking distributions believed to provide sufficient challenge for their models. We use an evolutionary algorithm to generate test data from distributions that are intentionally as different as possible from the training distribution. These test sets allow for more conservative evaluation of program synthesis models and allow us to better evaluate a model's 's ability to generalize to different distributions.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andrea Arcuri and Xin Yao. Coevolving programs and unit tests from their specification. In Proceedings of the Twenty-Second IEEE/ACM International Conference on Automated Soft- ware Engineering, ASE '07, pp. 397-400, New York, NY. USA, 2007. Association for Com- puting Machinery. ISBN 9781595938824.
doi: 10.1445/1221611.1322613. URL https:
Andrea Arcuri and Xin Yao. Co-evolutionary automatic programming for software development. Information Sciences, 259:412 - 432, 2014. ISSN 0020-0255. doi: http:///bbi.orr/10..000 1016//
2e.20009.2..199 URL http: www. www. www.:ssceenciieeceo recte com httm://ieenc//ttiicee///o 50220225509055490
Matej Balog, Alexander L.. Gaunt, Mare Brockschmidt, Sehastian Nowozin, and Daniel Tarlow.
Deepcoder: Learning to write programs. CoRR, abs/161 1.009999, 2016.
Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. CoRR, abs/ 1018805.000 805.04276, 2018.
Judith Clymo, Haik Manukian, Nathanael Fijalkow, Adrià Gascón, and Brooks Paige. Data genera- tion for neural programming by example. ArXiv, abs/ 1.122224,,,, 2019.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. CoRR, abs/1 703/0799,,,,,9, 2017.
Kevin Ellis, Maxwell I. Nye, Yewen Pu, Felix Sosa, Joshua B. Tenenbaum, and Armando Solar- Lezama. Write, execute, assess: Program synthesis with repl. ArXiv, abs/1906. 2019.
Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. Program synthesis using conflict-driven learning. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, pp. 420-435, New York, NY, USA, 2018.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, 2015.
Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using exam- ples. Commun. ACM, 55(8)-97-105, August 2012.
Girish Keshav Palshikar. Applying formal specifications to real-world software development. IEEE Software, 18(6):89-97, 2001.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. CoRR, 00s/1611.01855 2016.
Richard E. Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, Inc., 1981.
Yewen Pu, Zachery Miranda, Armando Solar-Lezama, and Leslie Pack Kaelbling. Learning to select examples for program synthesis. CoRR, abs/1711.03243, 2017. URL /attp://axxiv.rrrr
abs 1111. 03243
Christopher D. Rosin and Richard K. Belew. New methods for competitive coevolution. Evolution- ary Computation, 5(1):1 1997. doi: 29,1166/evcc.1997.5.. URL htttps://doi. o
2b.1162/evco.199...
Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. Csgnet: Neural shape parser for constructive solid geometry. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5515-5523, 2017.
Richard Shin, Neel Kant, Kavi Gupta, Christopher Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program synthesis, 2019.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training, 2020.
10

---

Under review as a conference paper at ICLR 2021
J Michael Spivey and JR Abrial. The Z notation. Prentice Hall Hemel Hempstead, 1992.
Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation, 2018.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. CoRR, htts/8809.4466 2018.

---

Under review as a conference paper at ICLR 2021
A ADVERSARIAL ALGORITHM
Input: model M, dataset X, evolutionary algorithm E, iterations N, episodes population size n, elites size m, num probs
for i = 0 to N - do
params = E e,,,e,n,
Randomly generate programs C 4
Draw c imputs C from distribution D(params) outputs [j
j < c)
problems = zip(programs, inputs, outputs)
Add problems to X
Train M on X
end for
Algorithm 1: Adversarial algorithm
B EVOLUTIONARY ALGORITHM
Input: model M, episodes population size n, elites size Randomly initialize params = [7" < n].
for 0 to - do
Randomly generate problems 5 (s
Calculate filnessScores ,
Sort params in descending order of fitnessScores newParams params|: ml
for j 0 to m 1 do
for k: = to n/ n/m do
Append new Params[]]] + Eoo new end for end for params = new Paramss
end for
Algorithm 2: Evolutionary algorithm
C
THE SALIENT VARIABLES METHOD
Here we give a more detailed description of the Salient Variables method of Shin et al. (2019) introduced baseline in Section 4.2. Let be the space of inputs, which is originally sampled from a distribution calculated by > X. We would like to sample a dataset D from such that has uniform distribution throughout D. To do this, we sample i ~ q and calculate x v(i). We then add i to D
+ [0, 1]. Let X be the discrete, finite space of salient variable, which is
with probability g(i), where
s(i) =)) min P,(u(i) x') + xx)++) x'ex
with P,(v(i)), the probabilities induced over v(i) via q. calculated empirically based on counts computed with past samples drawn from g. e E R a hyperparameter that allows the algorithm tolerance for non-uniformity. Increasing increases the algorithm's speed at the cost of allowing the distribution of u(i) to diverge further from the uniform in D. We repeat the above until is of desired size. Note that X can be space of tuples, allowing to ensure that the joint distribution of multiple salient variables is uniform, as we do in Section 4. Algorithm provides pseudocode for this method.
For our implementation in Section 4, we divide our salient variables by 10 and truncate the result. For example, if the minimum integer of an input is -256, we place -26 into dictionary of counts
12

---

Under review as a conference paper at ICLR 2021
in algorithm 3
This way. have far fewer elements in dictionary of counts so that Puiin in algorithm will become greater than after a reasonable amount of time.
Input: distribution q, salient variable tolerance dataset size
Create dictionary of counts = {o 0, E X
D=
t=
while DI do Sample i ~
C(u(i)) Clu(i)) +1
= t +
Pmin minaex
Peurr Clv(t)
te
9 te
Sample h ~ Bernoulligg)
if then
Add i to D end if end while
Algorithm 3: Salient Variables algorithm
D SHIN ET AL.'S TEST SETS
Shin al. (019) do provide the 12 test sets used in their paper, but they describe the process to generate these test sets, and we try to follow their methodology as closely as possible. Each test set contains grids with a wall ratio Twall f0.05, 0.25, 0.65, 0.85), marker ratio Tmarker {.05, 0.25, 0.65, 0.85), and a marker distribution Marker count E {G, U, A), where G, U, and A Geom(0.5) respectively. As described by
stand for Geom(0.5) discrete uniform(1, 9), and Shin et al., we use the following process to generate grids for a test set with wall ratio Twall, marker ratio r morker. and marker distribution D Dmarker comnt
1. For each of the 2,500 programs in the original test set from Bunel et al. (2088) we generate n discrete uniform(1, input grids. was unclear from Shin (2019) whether should generate a random number of input grids or 5 input grids. However, generating random number of grids yielded results closer those described by Shin et al.
2. For each of the grids, we sample grid width and grid height N. discrete uniform( 10, 16) and create an empty x grid.
3. For each grid square, we place a wall in that square with probability Twol-- all squares have walls, we resample.
4. For each grid square without wall, we place markers in that square with probability If Ymarker-
5. For each grid square chosen contain markers, we sample m Dmarker comns and place m markers in that square.
6. We place the agent in a random, non-walled grid square in random orientation.
7. After generating all input grids for a given program, we check whether the input grids exhibit complete branch coverage (i.e., each branch of the program's control flow is exe- cuted by at least one of the inputs). If branch coverage is incomplete, we discard all n grids and repeat the steps above.
is clear that some of Shin et al.'s test sets do not contain all 2,500 programs from the original test set, since they report accuracies such as 69.37% (if their test sets contained all 2,500 programs, then this would imply that their model solved 1734.25 problems, and it is impossible to solve 0.25 of problem). Therefore, Shin et al. must discard programs for which they repeatedly find incomplete branch coverage in step 7. Shin et al. do not specify how many times we may find incomplete branch coverage before discarding program, but choose to discard program after hitting step
13

---

Under review as a conference paper at ICLR 2021
7 1,000 times. This may explain why Shin al. report higher accuracies for the Salient Variables method than we do: if Shin et al. chose to use fewer than 1,000 retries, they may have discarded more difficult programs, increasing their reported accuracies.
However, this potential difference in the number retries does not explain why our accuracies for much higher than the baseline accuracies reported by Shin al. Shin et al. report an average accuracy of 10.68% for the baseline method. On our versions of Shin et al.'s test sets, the baseline method achieves an average accuracy of 29.61% %. We generated several different versions of Shin et al.'s 's test sets by altering the process above, changing parameters such as the number of retries, the number of grids generated, and the distribution of grid sizes. The baseline method achieved approximately 30% accuracy for all versions. Therefore, our best guess for the cause of Shin et al.'s lower accuracies that Shin et al. evaluated the baseline method using neural network that reached a bad local optimum during training. This would explain why Shin et al. observe such inexplicably low accuracies for the baseline method.
the baseline method
E
KAREL RESULTS
Table Performance of the three approaches (Bunel et al.'s original approach, salient variables, and our adversarial approach) on the 12 test sets proposed by Shin et al. We describe these test sets in Appendix D.
Twall; Tmarker
Dmarkercount
BASELINE
SALIENT
ADVERSARIAL
GEOMETRIC
42.52%
58.92%
59.41 %
5
UNIFORM
32.63%
59.32%
60.12%
10 GEOMETRIC
18.77%
57.83%
59.48%
GEOMETRIC
42.64%
58.60%
58.88%
8
UNIFORM
33.56%
57.56%
57.52%
10 GEOMETRIC
24.77%
58.20%
58.56%
GEOMETRIC
30.41 %
61.80%
61.22%
10
UNIFORM
29.31 %
63.05%
62.
10- GEOMETRIC
24.70%
62.62%
62.58%
GEOMETRIC
25.89%
71.26%
71.40%
12
UNIFORM
26.38%
70.13%
70.00%
10 GEOMETRIC
23.71%
70.27%
68.96%
14


Reviews:
[{"review_id": "uHsDtKXQNqE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 paper proposes an approach to develop synthetic datasets aimed at training DeepCoder-alike models. They claim that current approaches to generate synthetic datasets do not help coding algorithms to obtain a good generalization. The reviewed literature and the experiments presented back such claim. The approach consists in an _adversarial_ Evolutionary Computation (EC) methodology.\n\nPros:\n- The paper is, in general, well written. The language is clear, and overall structure of the paper is OK.\n- The method is sounding, as it departs from proven concepts such as using evolutionary methods as adversarial sample generators for deep models.\n\nCons:\n-  Sec. 3 could be improved. Authors rely too much on formal notation to express their main contribution, with almost no explanation in simple words, or the intuition behind it.\n- Although the paper may be solid enough, from a scientific point of view, I consider the scope of the paper too narrow. Authors are proposing a tool to help another tool without too much use other than competitions on synthetic datasets. As the authors state themselves, there are no enough real-life cases for these types of models to perform, and therefore everything is reduced to benchmark tests on toy, artificially generated, datasets.\n- i.e., their contribution is minimal from a wider point of view. This is evidenced in their own list of stated key contributions, where they expand a unique contribution (the proposed approach) into three redundant achievements (experimental evaluation of the approach in two different settings).\n\nOther comments:\nA major problem with the entire field of Program synthesis within the field of deep learning, is that sometimes overlaps alarmingly with the field of Genetic Programming (GP), and it becomes difficult to really put in perspective if a contribution is original enough, or just a re-painted version of an older idea. This paper is a clear example of such problem. The method the authors are proposing, bears some resemblance to the (competitive) Co-Evolutionary approach of subset sampling used in GP [1,2,3]. But these methods are never mentioned in the related work area, becoming impossible to perform a side by side comparison of the proposed approach against what already exists in other areas; in other words, the paper fails by being too focused on the area of deep learning, while being oblivious to very similar developments in parallel areas.\n\n1. Doucette, J. A., Mcintyre, A. R., Lichodzijewski, P., & Heywood, M. I. (2012). Symbiotic coevolutionary genetic programming: a benchmarking study under large attribute spaces. Genetic Programming and Evolvable Machines, 13(1), 71-101.\n2. Chong, S. Y., Tino, P., & Yao, X. (2008). Measuring generalization performance in coevolutionary learning. IEEE Transactions on Evolutionary Computation, 12(4), 479-505.\n3. Pagie, L., & Hogeweg, P. (1997). Evolutionary consequences of coevolving targets. Evolutionary computation, 5(4), 401-418.\n\nRate updated 30 Nov.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RiaABr1vGg7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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:\n\nSynthesis models trained on synthetic datasets of randomly generated programs and corresponding IO pairs often fail to generalize to real-world PBE problems. The models often learn specific aspects of the synthetic data distribution rather than the semantics of the programming language. This work proposes a more principled adversarial approach to generate synthetic data. The training set is built iteratively by finding data distributions on which a given model performs poorly and adding data drawn from these distributions to the training set. The model and the training dataset are built in tandem. The candidate distributions are generated by mutating the current population of distributions. Models trained using this method are shown to generalize to a variety of distributions.\n\n## Positives:\n\n* The problem is this work is addressing an important one and is well situated. \n\n* Novelty: Although the idea of adversarial data augmentation to improve generalization across domains has already been explored in the literature (eg. Volpi et. al.), I haven’t seen this applied in the PBE setting. The current work is agnostic to the architecture of the synthesis model. I would, however, like the authors to contrast their approach with these approaches. \n\n* Clarity: The paper is well written and well motivated. The algorithm is explained well and seems reproducible. \n\n* Results: The experiments are inline with the claim. The proposed method is evaluated on two domains (DeepCoder and Karel) and compared with two state-of-the-art methods. Although the method is not a winner for all the datasets, it generalizes well and has best worst-accuracy across different datasets for various program lengths. \n\n* The work proposes to use adversarially generated test sets for evaluating performance of models. I believe this is an important contribution and will help in avoiding cherry-picking (often unintentional) of test datasets.\n\n## Negatives\n\n* Defining the space of distributions to be explored may be difficult if the DSL involves APIs with the complex semantics. For example, it will be difficult to use the simplistic method of defining distributions for all the literals for the Sygus String PBE domain. Most of the random IO pairs will not have a solution (or a very long solution). I think it will be difficult to adapt the current method to such a highly constrained domain. I would like the authors to comment on this and qualify the results if they agree.\n\n* To bolster the claim, I would have liked additional results on a complex domain (eg. SYGUS String PBE).\n\n* I believe readers will benefit from some discussion on contrasting the current approach to conventional adversarial data augmentation methods (even though the setting is quite different).\n\n## Overall Remark\nI believe the method will be a valuable contribution towards the important problem of generating synthetic datasets to train robust models. Despite my apprehension of the applicability to more complex domains, I believe the method can still be employed in conjunction with the other methods.\n\n## Minor comments\n* Although the paper claims adversarial training data generation as the main contribution, the title of the paper focuses on the “evolution” aspect of the method. \n* As I understand, in section 3, $(\\phi, i, o)$, “i” and “o” are input and output vectors and not a single input output pair. Would like the authors to clarify this.\n* “We sample n/m -1 new distributions”. Shouldn’t it be “n/m”\n\n## References\n* Volpi, Riccardo, et al. \"Generalizing to unseen domains via adversarial data augmentation.\" Advances in neural information processing systems. 2018.\n* Alur, Rajeev, et. al. Syntax-guided synthesis. IEEE, 2013.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lq96NAf8qAH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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 paper is proposing to evolve datasets of (inputs, outputs) in the context of programming by example (PBE), where the goal is to infer a computer program that is consistent with the association of (inputs, outputs). The justification of the approach is to figure out instances that would allow to learn a model with PBE that would generalize better, compared to learning from synthetic datasets that are randomly generated. The approach followed consists to use an evolutionary algorithm to generate this new dataset, using the learn model as a guide, by picking the points where the model at hand performs poorly. Such adversarial approach proceed iteratively, adding extra pairs of (inputs, outputs) to the training set, to get it to perform better in situations where it has trouble.\n\nThe proposal is relatively straightforward, using an adversarial optimization loop to enhance the training set for better (at generalization) PBE approach. Such solution is in line with many other adversarial approaches. The proposal is quite specific to the context of PBE, and has been tested in a rather synthetic setting (toy problems / synthetic problems). Performance shows good general improvement of the performance. However, the overhead of generating the adversarial samples is not provided, nor the overhead caused by adding more samples to the training set. If we have trained the model with more random samples (same size for all approaches), would the results be the same -- I mean is there any correction made to ensure that we are always comparing approaches with the same number of samples?\n\nThe overall proposition is analogous to different proposals made with coevolution in evolutionary algorithms in the years 2000s. Here again, the training set was \"co-evolved\" with the program inference task in a competitive (adversarial) way, with a population of samples vs. a population of programs, trying to obtain the samples that would mislead the most the programs, in order to infer more robust solutions. See for instance\n\nhttps://doi.org/10.1162/evco.1997.5.1.1\nhttps://doi.org/10.1162/106365604773955139\n\nAlthough we are not talking of the same kind of PBE -- evolutionary algorithms vs. PCCoder -- I think linking the current work with this older one would be required, as the idea is not new (but applied to a different PBE approach).\n\nThe quality of writing is not as sharp as we would expect for an ICLR paper. The writing stay somewhat vague at times, we would expect more formal and precise presentation. The algorithms presentation in Appendices A and B are not very clear and not very useful to grasp all the details. The presentation of the methods in Sec. 4.1 and 4.2 are very textual, I am far from being convinced that someone who what to reproduce the approach will be able with the information provided. For instance, how is exactly computed the fitness function is not given explicitly, from what I get I would have a hard time to implement it, or at least valid it in its correctness. It appears strange of proposing an optimization solution as the main contribution without explaining in detail the objective function optimized.\n\nIn brief, the proposal does not pass the threshold in terms of significance of the contribution, overall quality of the paper and how exhaustive the experimental evaluation has been made.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EXDTsT3UN3d", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- quality : good\n- clarity : good\n- originality : okay\n- significance : okay\n\nThis work mainly deal with the issue of I-O selection during training. Typical program synthesis training collects its dataset as follows:\n1) select a random program \\phi\n2) select a set of random inputs I\n3) run \\phi(x) to get a set of outputs O\n4) add the tuple (\\phi, I, O) as training data \n5) train a model M using the training data\n\nGiven a program \\phi, there are infinitely many input-outputs that can be used to specify it. Which one should you pick? This work suggests that instead of picking a random set of I, this set of input should be chosen adversarially, conditioned on the current synthesis model M. Under this scheme, one alternates in generating adversarial training datasets D' and appending it to D, and each time we re-fit a new synthesis model M over this dataset. Experiments show this is good in practice.\n\nI especially liked the passage in this paper that uses the adversarial I-O as test set and measure performance with it. It is a very good lower bound on just how bad your synthesis algorithm is.\n\nSome comments and questions for the authors:\n\n1) why stop at being adversarial w.r.t. input I? why can't we also pick \\phi adversarially? Imagine we have a PCFG (or any language model for that matter) capable of generating programs, we can easily evolve a PCFG that targets more \"tricky\" programs to have them in the grammar. in this sense, this paper title is inaccurate in saying the evolution is evolving how to construct synthetic datasets, as we do not evolve over \\phi, but only over I. maybe a more appropriate title would be something along the line of evolving adversarial inputs for synthesis.\n\n2) how expensive is this algorithm? presumably this algorithm needs to cycle between fitting M and generating D. One can imagine this is costly if too many rounds happen? Understandibly, this cost is only paid in training time, but it should not be too high – for instance, re-training M after every single (\\phi, I, O) addition. If the time takes to fit M linear in the size of D, Is the time complexity quadratic in the number of iterations? Is 20 iterations (for your experiments) chosen for any particular reason?\n\n3) one line of work that is highly relevant is \"selecting representative examples for program synthesis (Pu et.al 2018)\", where they start with a big set of input-output examples, and iteratively select from the big set the most \"surprising\" examples, where surprising is estimated using a neural network trained on the task of I-O infilling. \nThey used representative examples as a pre-process step to program synthesis, but one can imagine adopting it as a baseline in the following sense:\n- first train the neural-network that can measure surprisal using I-O infilling tasks\n- sample a random program \\phi\n- sample a large set of input-outputs I-O_large\n- start with I-O_repr = {}\n- iteratively add i-o from I-O_large that is surprising – conditioned on I-O_repr – to I-O_repr until I-O_repr is of a desired size\n- return (\\phi, I-O_repr) as training data point\n\nI-O_repr is representative in a sense that it maximally disambiguate equivalent programs that satisfies the previous set of I-O. It would be interesting to see the relationship between the adversarial examples (optimized for hardness) and the representative examples (optimized for minimizing ambiguity).\n\n4) A question just out of curiosity, how can this approach be scaled to an interactive setting, where the size of I-O can vary? Imagine in an interactive synthesis setting, after giving 3 I-O to the synthesizer, the synthesizer M returns a program that satisfies these 3 I-Os, but isn't what the user want. The user adds a 4th I-O as a result. Would you evolve different sets of adversarial training data one for each I-O size? Is the user being adversarial here though? Or is the user being cooperative, how would you model that?\n\n\n\nOverall I enjoyed reading this paper. I find the reasoning of using test sets that are off-distribution compelling, and the usage of an adversarially constructed test-set well justified. This work can be made stronger by considering also evolving a good distribution of \\phi (or at least some comments on why this was not attempted), and comparing against the work that selects representative set of I-O.\n\nfinal recommendation:\nafter looking at the other reviewer's scores and exchanging some more information with the authors (thanks for the great exchange btw), I would maintain my score of 6. I feel this line of work is definitely useful for program synthesis, especially in the analytical aspects (using adversarially generated examples as benchmarking tools and as representative explanations). the comparisons against other genetic programming approaches, I feel, is not too necessary once the paper is framed as \"using adversarial examples to instrument / analyze synthesizer behaviours\". ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper uses adversarial data to improve generalization in Programming By Example (PBE). The reviews were somewhat mixed with some people finding this useful and interesting while others finding it straightforward and unsurprsing. The reviewers were not convinced of the ultimate usefulness of the approach since it is evaluated on toy or synthetic datasets. The clarity of the presentation could also be improved.
Decision: Reject