Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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. 

They 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. 

They 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.

A synthesizer network is used to synthesize the program from generated unit tests. They test on Karel and list processing task.
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 :-

(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

(2) Sanity checks :-
  (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.
  (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

(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.

(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.

(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_review: The problem is interesting but the paper suffers from some incorrect claims, insufficient motivation and justification, and underwhelming empirical results.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

The 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.

main_review: Strengths: 
- 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.
- 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.

Weaknesses:
- 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.
- The paper does not provide all details necessary to reproduce the results (see suggestions for more details).
- 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.

Suggestions:
- 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:
  - Query decoder for Karel: if it is similar to the query encoder, how does it generate a grid world state as the output?
  - Query decoder for list processing: since input examples 
  - "additional batch normalization is added to keep the generation more stable": how was this done?
  - "we introduce a latent code like InfoGAN": this can be described more precisely, including with equations
  - "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 
training process unstable": If the loss was not useful, then was it still kept?
  - "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?
  - "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.
- 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

To 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.

Results are convincing to me.
main_review: ## what I like about this paper

I 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.

Algorithm 1. is cleanly written, I was able to follow it well other than line 11 and 12 (see question below)

I 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.

The 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.

Overall this is a solid work that (appears to me) is written by a group who understands the landscapes of neuro-guided program synthesis well.

## what this paper needs work on
This paper would be much stronger if the following points can be addressed.

### the exposition
while 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.

to 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. 

currently, 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).

Since 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.

### other baselines
Current 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:

1) 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.

2) 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))
See 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.

I 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.

### related works

There are very relevant prior works that studies the relationships between optimally querying examples for program synthesis from an information theoretic perspective:
[1] https://arxiv.org/pdf/1704.06131.pdf
[2] https://arxiv.org/pdf/1711.03243.pdf

Specifically, 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.

Further, [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.

## questions:

- 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!)

- 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.

- 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.

minor:

- 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.




summary_of_the_review: Overall I liked the paper, as it solves 2 key challenges of program synthesis:
1. The training distribution of the synthesizer does not match the testing distribution
2. One would like to recover the target program with as few examples as possible

It 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.

Results give good evidence of the proposed method as well.

This 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.

The 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).
review_title: null

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)