Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a method for neural synthesis of straight-line programs from I/O examples that works by learning
candidate solutions for individual examples and then combining their instructions into an overall solution using a
separate model. They build upon prior work on the DeepCoder dataset (PCCoder) that remains SOTA for neural-guided search
on these programs, and extend it with a second search procedure to assemble lines from per-example candidate solutions
into an overall solution. The resulting search significantly outperforms the PCCoder baseline with roughly the same loss
of generalization to longer programs.
main_review: 
Strengths:
- An original idea for straight-line synthesis – use programs satisfying individual examples as a vocabulary of
  possibly-useful instructions, and learn to aggregate them into a global solution.
- Strong empirical results with investigation of attention and limited generalization.
- Well-described and rigorous evaluation setup.
- Decent overview of related work.

Weaknesses:
- Some choices in the architecture could be better motivated or investigated. The authors already compare to several
  ablations, but they come too late in Section 4. The paper lacks a high-level description of the current encoding
  process and its explored alternatives somewhere around page 5. Currently, the brief "Motivation" paragraph sets up
  _why_ PEPS looks at per-example program states and lines as clues, but then stops just short of explaining _what_ PEPS
  could do with those states/lines at an equally high level.
- Generalization experiments are lacking. The only one presented is length generalization from 12 to 14 lines, which is
  not even particularly ambitious (of course, that still drops every model's performance by ~26%). In contrast, prior
  work on by-example synthesis such as PCCoder, Flash*, RobustFill is also concerned with example overfitting in
  addition to length or compositional overfitting. Specifically:
  - The best model of PCCoder is trained to embed 10 examples but only presented with 5 examples at test time. How would
    an equivalent version of PEPS's cross-aggregator model perform? As presented, it should be able to aggregate any
    variable number of programs that was found in the first phase, but it learns its cues based on the set of available
    keys (program states/lines), which at training time is induced by available I/O examples. Would a bigger set of keys
    yield a stronger cross-aggregator (thanks to a richer sample of state features) or a weaker one (thanks to reliance
    on the higher chance of better-matching PE program being there)?
  - Flash*, RobustFill, Karel, and many other program synthesis settings value _intent generalization_: whether the
    found program satisfies not only the given examples but also a hidden one (in assumption that the given 5
    sufficiently define the intent). DeepCoder and PCCoder do not measure it, presumably because their search methods
    are not amenable to that objective (the trained models optimize correctness w.r.t. the given 5 examples). But PEPS
    is much more powerful! In a sense, it already optimizes example generalization – the whole point of
    cross-aggregation is to use programs that satisfy _some_ examples as building blocks or cues to the program that
    satisfies _more_ examples. We might discover that this method learns to synthesize a _more generalizable_ program,
    even for examples not shown to the aggregator model. That would be a very significant finding for the field.


## Opportunities for improvement

Related work might discuss connections to learning of decision trees and older set-cover driven techniques to synthesize
if-else chains in programming by examples. They also take programs that satisfy a subset of examples, and delegate
satisfaction of the remaining ones recursively to the program in the "alternative" branch. In contrast to PEPS, they use
all learned programs as independent branches at test time - not an option for this DSL.
1. Alur, R., Radhakrishna, A., & Udupa, A. (2017, April). Scaling enumerative program synthesis via divide and conquer.
   In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (pp. 319-336).
   Springer, Berlin, Heidelberg.
2. FlashFill and FlashMeta: algorithms for learning If/ElseIf/Else chains.

The current matching process is based on similarity of _the current program state_ with _the state of each candidate
program right before the line of interest_. Counter-intuitively, it does not consider whether relying on that line would
bring the program state "closer" to desired output. In fact, the "final output" part of the state seems underutilized
and might even be superfluous. As such, the aggregator network does not rely on instruction _semantics_, only on its
syntax and its proximity to the current state.  
Possible concrete suggestions: split Equations 1-3 into two attention blocks, one against keys={states before each line} and one
against keys={states after each line}. Or concatenate them before embedding the key matrix. Or max-pool from each
(before, after) pair to form the key matrix – there are many architectural options.

How often is the synthesized line has the same operator, or even identical to the lines the aggregator attends to? It
seems to be the case for most of the examples. Would a copy mechanism for $o_t$, or even $s_t$ perform just as well?
Even if it makes occasional mistakes, it might cut down inference time a little, which would free up search budget.

## Clarity

Most parts of the paper are clear, and include much-appreciated diagrams for the search process and model pipeline. Some
enhancements:
- High-level description of cross-aggregation and its ablations (see Weaknesses above).
- Usage of the term "GPS" as a substitute for "baseline PCCoder" is confusing, especially in Section 4 when they are
  used interchangeably and inconsistently. There seems to be no need to introduce a new, more general term, if the paper
  explores exactly one baseline instantiation of it.
- Equation 4 does not type-check (at least in my brain).  
  First, the predicted statement $\hat{s}^t$ is multiplied by a
  real scalar. Previously, $s^t$ was defined as a one-hot vector (L97), and $\hat{s}^t$ as its estimate (L214). I
  suppose in practice $\hat{s}^t$ likely means predicted logits and thus Equation 4 is meant to be interpreted
  literally, but that was never properly defined in the paper 🙂  
  Second, using real-valued subscripts $\alpha$ and $1-\alpha$ to obscurely denote "from cross-aggregation" and "from
  program search" respectively does not make much notational sense.

limitations_and_societal_impact: 
A brief note on impact is included in Section 6, likely sufficient for the paper's topic area.
I did not find any explicit discussion of limitations anywhere.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new approach for neural program synthesis by first searching for per-example solutions and then learn to combine them into a global solution. The paper uses PCCoder for synthesizing the per-example solutions, and uses an aggregation model based on cross-attention mechanisms. The aggregation model attends to the partially executed program states by the per-example programs in order to choose the next program token. The proposed technique is evaluated on a DSL involving computation on integers and list of integers, and is shown to achieve better performance than PCCoder. 
main_review: Overall, the idea of first synthesizing per-example programs and then combining them in neural program synthesis is interesting and worth exploring. The paper considers and evaluates many different design choices in their approach, which is a plus. The writing of the paper is clear and easy to follow (except too many abbreviations). However, I have some concerns on how generally applicable the proposed approach is, therefore its significance. Please see the following questions for more details.

Questions for authors:
- It seems that the way the proposed aggregation model operates is by choosing one of the next operators from the per-example programs as the next operator in the global program. This can only generate global programs that are stitches of the per-example programs. For a lot of domains this is not likely to work, and more complex ways to join the per-example solutions might be necessary (e.g. adding conditionals). How often does the proposed method generate mere stitches of the PE programs, and how often does it generate programs that contains new operators? 

- Is there any examples of non-trivial combination of PE solutions performed by the proposed approach? It's not clear whether the current approach is going to be helpful for other domains where non-trivial combination is required. So experiment on another domain would also be helpful.

- With alpha being a hyperparameter, the proposed approach is using global program search (GPS) as part of itself. If we fix alpha=1, what are the results over all evaluation settings? This way, the comparison will be cleaner. 

- What is the takeaway from the N-PEPS variants? They all seems to have a similar performance. Which option does the author recommend?

- The authors might want to include a discussion on the literature on version space algebra used in program synthesis in the related work, since that approach is on combining per-example solutions to a global solution.


limitations_and_societal_impact: The limitations and potential societal impacts are addressed in the conclusions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper addresses the problem of learning to synthesize a program that describes a sequence of array operations to realize the transformation between given input/output (I/O) examples. While most existing learning frameworks are designed to find a program that satisfies all I/O examples at once, sometimes it can be inefficient to consider all the examples at every iteration. This paper aims to improve the efficiency of a synthesizing program by aggregating multiple programs that are separately synthesized considering only one example. Specifically, the paper proposes a framework that first (1) finds N per-example programs where each of them satisfies only one of the N examples, and then (2) yields a program that satisfies all examples by combining all per-example programs using a proposed neural network with a multi-head cross-attention mechanism. The experiments show that the proposed framework outperforms a baseline (PCCoder) that considers all examples at once when given a tight time budget. Ablation studies verify the effectiveness of the proposed cross attention scheme. I believe this work studies a promising problem -- building a more efficient neural program synthesis framework and proposes an effective framework to address the problem with sufficient evaluation. Yet, I still have some concerns such as the limited scope and design choices (see below). Currently, I am slightly leaning toward accepting this paper and look forward to the authors' rebuttal.
main_review: ## Paper strengths and contributions

**Motivation and intuition**
The motivation for devising a more efficient neural program synthesis framework is convincing.

**Novelty**
To the best of my knowledge, synthesizing per-example programs first and then learning to aggregate them to form a global solution is novel in the field of neural program synthesis.

**Technical contribution**
- The proposed multi-head cross-attention mechanism for aggregating per-example programs seems effective.
- This work provides insights on neural program synthesis methods working under a limited time budget.

**Parallel execution**
While the proposed framework considers the total time consumed as $\sum_{i}\  the\ time\ of\ finding\ a\ program\ for\ the\ i\text{-}th\ I/O\ pair + the\ time\ of\ aggregating\ them\ programs$, I believe the proposed framework can potentially be extended to even reduce the running time via parallel execution. If I understand correctly, the process of finding per-example programs can run in parallel (while some per-example programs can be applied to more than one I/O pair) so that the execution time could be the summation of $\max_{i}\ the\ time\ of\ finding\ a\ program\ for\ the\ i\text{-}th\ I/O\ pair + the\ time\ of\ aggregating\ all\ programs$. 

**Clarity**
The overall writing is clear. The authors utilize figures well to illustrate the ideas.

**Initial experiment**
The goal of the initial experiment is to analyze how per-example programs perform compared to a solution found by a global program synthesis baseline. I like the concept of this experiment, which aims to motivate the proposed framework, while I am not fully convinced by the way how results are interpreted (see below).

**Ablation study**
- Different variations of aggregating per-example programs such as taking summation or mean are evaluated (the table in Figure 3), suggesting the effectiveness of the proposed cross attention mechanism.
- The trade-off analysis on dividing the total timeout into the time given to find PE solutions and the time given to the CA module is informative. This result seems to suggest that the CA module does not need much time. It seems that 5-0.8*5=1 sec for the CA module yields the best performance, which is surprisingly low.
- Different variations of composing the keys by varying the set S in the execution tuple against which per-example programs are executed are evaluated, verifying the effectiveness of the proposed method.

**Experimental results**
- The presentation of the experimental results is clear and easy to follow.
- The experimental results in the tables in Figure 3 and Figure 4demonstrate that the proposed framework outperforms a global program synthesis baseline (PCCoder) in terms of success ratio on test samples with varying lengths when the timeout is set to 5 seconds.
- The success ratio vs. time taken result shown in Figure 3 shows that the proposed framework consistently outperforms PCCoder when taking more than 1 second of computation.
- The attention visualization provides some insights into what the CA module learns.

**Reproducibility**
The code is provided, which helps understand the details of the proposed framework.

## Paper weaknesses & questions

**Limited scope**
While the proposed framework is interesting and inspiring, the evaluations are only limited to array transformation programs. I believe this paper would be much stronger and more convincing if the proposed framework was also evaluated in other popular program synthesis domains such as Karel and string transformation.

**Clarity**
The writing of the method section is not easy to follow. I feel the authors try too hard to be precise by explaining all the details including the dimensions of all the representations and introduce too many notations, which actually stops the flow and makes it hard to read. Revising the section by balancing between giving high-level intuitions and important details would make it easier to follow.

**Pairwise aggregation**
This work proposes to aggregate all the per-example programs at once. I wonder if it is possible to instead perform a sequence of pairwise aggregation to recursively produce the final global solution. It is also possible that the pairwise aggregation can run in parallel to save time. This also aligns well with the high-level idea of this work -- conquering sub-problems first for better efficiency.

**Multiple blocks of CA**
The proposed framework work employs only one block of CA. As models with stacked attention modules have achieved exciting results in a wide range of domains, it would be interesting to see if stacking multiple blocks of CA would yield superior performance even it needs to take some extra time to compute, especially since CA does not need much time it seems (from Figure 4).

**Programs with branching conditions and loops**
It seems to me that both PCCoder and the proposed framework can only synthesize programs consisting of a seq of operations. Yet, programs for many real-world applications often include branching conditions (e.g. if-else) and loops (e.g. while, for). I would like to hear the authors' opinion on how it can be extended to deal with those.

**Combing the predicted statements of GPS and PEPS**
I wonder what the intuition is for combining the predicted statements from both GPS and PEPS. It seems that, from Figure 4 bottom right curve, setting $\alpha=1$ yields the best result, meaning that completely using the predicted statements from PEPS is enough.

**Longer timeout**
While there are definitely some applications that require methods with a tight time budget, there are still other applications that value accuracy more than efficiency. I would like to know how the proposed framework performs with a much longer timeout such as 1000 seconds compared to PCCoder.

**Initial experiment**
While I like the idea of employing this initial experiment to motivate the proposed framework, I am not entirely convinced by the way the result is interpreted. I believe tot(5) and GPS are not directly comparable. Imagine we are solving a hard optimization problem with many constraints. Saying tot(5) (i.e. solve the optimization with some constraints removed) can solve the optimization problem in more cases compared to GPS (i.e. actually solve the problem) does not make much sense because solutions found by tot(5) might not even be meaningful at all. That being said, tot(5) does not tell anything how possible the PE solutions can be combined.

**Supervision of PE**
The paper states "we use $p_g$ as a proxy for ground-truth PE solution".
Isn't this actually "wrong" supervision since $p_g$ might contain some redundant operations that do not need to be applied to some "simpler" I/O pairs?

**Missing related works**
I believe some prior works can be incorporated to make the related work section more comprehensive:
- Synthetic Datasets for Neural Program Synthesis
- Improving Neural Program Synthesis with Inferred Execution Traces
- Neural Program Synthesis from Diverse Demonstration Videos 
- Neural Scene De-rendering 
- Learning to Describe Scenes with Programs
- Learning to Infer and Execute 3D Shape Programs

**Minor bugs in code**
It is great to include the code so that reviewers can understand the paper better even by just tracing the code. However, it is also encouraged to make sure the code is runnable so that the results can be reproduced, The provided code has several bugs and it took me a long while to make it runnable. These are just some of the minor bugs that I ran into when trying to reproduce the results (I lost track in the middle because there are many): 
- missing dependencies: numpy
- Code/scripts/solve_problems.py line 24: a line break is missing
- Code/scripts/solve_problems.py line 269: duplicated `help`
- Code/scripts/gen_train_programs does not run with line 264 `range(min_len, args.max_train_len + 1)` and only works when setting it to start from `min_len+1`. It can't generate program with length equal to zero.
- Code/scripts/gen_train_programs.py line 294: should also `mkdir` when the dir does not exist
- Code/scripts/gen_agg_instances.py: inconsistent use of tabs and spaces in indentation


## Other metrics

### Relevance and significance
- Reasonable contribution to a minor problem

### Novelty
- One idea that surprised me by its originality, solid contributions otherwise

### Technical quality
- Technically adequate for its area, solid results

### Experimental evaluation
- Sufficient evaluation w.r.t. most criteria

### Clarity
- It is mostly clear, but improvements are needed, as recommended in the detailed comments.
limitations_and_societal_impact: Described in the main review section.
review_title: null

Meta-review: The paper presents a new technique for synthesizing straight-line programs from input-output examples. The core novelty in the technique is that rather than trying to synthesize a program that works correctly for all available examples, the algorithm first finds separate programs that work for each individual example and then uses a cross aggregator to merge the individually working programs into a program that works correctly on all inputs. 

As the authors point out in their related work section, there is precedent for this idea in the program synthesis community, but this has never been done before in a neural setting. 

The authors addressed many of the questions and concerns raised in the reviews and provided a very thorough rebuttal. I think the main open question is the generality of the technique, since it is only evaluated on an important but limited domain, and it is not clear how to generalize it to more complex settings. 

That said, this paper presents an interesting and novel contribution and should be accepted.


Decision: Accept (Poster)