Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes PG-TD, which integrates Transformer with MCTS for code generation. PG-TD works by generating a tree of possible programs, first generating high likelihood sequences and then evaluating them on test problems. It then selects the best and searches for more sequences until it completes the program. The authors also propose to cache completed queries as many are repeated during search. The authors demonstrate results of pass rate and computation time on an established coding challenge, demonstrating PG-TD outperforms GPT-3 baselines.

strength_and_weaknesses: Strengths:
* The paper is clearly written and described.
* The website has a useful visualization and providing the code is appreciated (though there is a lot of code provided and maybe a subset would be preferred).
* The paper approaches an important research area, improving generation for LLMs and proposes a reasonable approach for it that does not require any additional training and minimal code complexity.
* The results demonstrate it outperforms baselines in performance.
* The results showing varied rewards is interesting and useful and a nice benefit of the approach.

Weaknesses
* The results are all performed with GPT-2 and seem to be a relatively weak LLM for coding. For coding in particular, where any small mistake may be catastrophic (in that it doesn't compile or run), I am unable to fully contextualize the benefits with a weak model (and one not trained on code). Codex for example would be a much stronger approach a minimize issues like the second sentence in the abstract “ Although the programs they generate achieve high token-matching-based scores, they often fail to compile or generate incorrect outputs.” Indeed, I ran two of the proposed tasks (Figure 1) and the circle problem on the website and *zero shot* Codex solved both. Furthermore it solved both with much more reasonable code than the PG-TD code and did it in under 5 seconds. 
* The authors should report cost of running the algorithm.
* The overall success rate, particularly based on the examples shown in the paper, seems quite low for all methods.
* I believe all the results in this paper are zero-shot (or else I missed this), but presumably much of the issues would be solved with simple prompting with a few examples. The authors should compare to this.
* The examples of code shown are odd, in that it tends to generate unnecessarily complicated code for quite simple problems, stating `print(2*(r**2)-r**2)` instead of `print(r**2)`.
* Please discuss the failure modes, for both PG-TD and baselines, are they not compiling or failing test cases?
* I find pass rate an odd metric. These problems are simple and the input is constrained, so if the code doesn't solve them 100% then is it not incorrect code? If nothing else, the authors should report the number of tasks solved 100%. 
* The computation times are quite slow and somewhat prohibitive, perhaps an improved LLM would help with this or a smaller one to search more quickly. Can you early terminate? What if a beam achieves 100% pass rate during search, do you stop?
* The caching I do not see as a major contribution. Writing a dictionary for cache[query or partial] should suffice unless I misunderstood. 
* Though mostly clearly written, the statement of contributions, introduction, and abstract can be more clear what actually is done. What planning algorithm, what computationally efficient design mechanisms? These should be presented early and clearly for the reader.
* The method itself is reasonable interesting, integrating MCTS to the search, and it might be useful to show the approach on more varied problems, perhaps other coding challenges or BigBench benchmarks.

clarity,_quality,_novelty_and_reproducibility: Clarity: good
Quality: unclear based on results
Novelty: reasonable to my knowledge
Reproducibility: good
summary_of_the_review: The authors propose a novel approach that is interesting and potentially useful, and the paper is clearly written. However, they only compare and leverage GPT-2 for coding problems, which leads to low performance across the board and making it unclear if they are solving a real problem -- they should run the examples with Codex and also with prompting. The algorithm is also quite slow, the code produced is overly complicated, and the metric of pass rate only is lacking (they should also report whether the code was correct). I do not believe caching to be a major contribution, but is presented as such and takes up a page. The paper may be improved by further demonstrating performance on other problems (perhaps not code) that have a reward structure.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: A new decoding strategy for language models for code is presented, based on the intuition of selecting tokens that lookahead search deems to be more likely to lead to correct sequence outputs. Additional ideas on managing the performance overhead of this strategy are presented. Finally, experimental results indicate that this new decoding strategy can outperform baselines by some margin.
strength_and_weaknesses: * (+) This is an interesting direction, focusing on a core part of neural code generation that often receives little attention.
* (+) The empirical results indicate a significant improvement over baselines for the evaluated models.
* (~) I found the discussion of related work unsatisfactory - it's presented as a list of related papers, with little discussion of commonalities and differences to the presented work
clarity,_quality,_novelty_and_reproducibility: The paper is largely clearly written and easy to follow. I found App. C.1 was very valuable to better understand some of the choices made and would urge the authors to include more of it in the main text of the paper.

As far as I am aware, this is a novel contribution (though I'm not familiar with the planning literature); the experiments are sound and support the claims made in the paper well. (I'd have appreciated more details on the timings of different models though).
summary_of_the_review: Novel decoding algorithm, good experimental results, no major concerns: this paper should be accepted, as it will be of substantial interest to the ICLR subcommunity of researchers interested in code generation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes using a (MCTS-inspired) heuristic planning algorithm to guide the decoding process of a pre-trained code-generation transformer, for the specific task of test-case-guided competitive programming. At a high level, the proposed decoding strategy maintains a tree of prefixes, conducts beam-search-based "rollouts" and evaluates them on test cases to assess quality of these prefixes, then uses this information to determine which tree nodes to continue exploring. (I believe that the proposed method is deterministic, in contrast to MCTS which is stochastic by design.)

Since beam search and greedy decoding already involve expanding a tree of tokens, the authors introduce caching mechanisms to make their proposed planner more efficient: they cache the tree structure generated during beam search and re-use it when expanding nodes for MCTS, and (when using greedy rollouts) they cache the greedy decoding output for any given prefix and re-use it when expanding the nodes along an already-explored trajectory.

The authors compare their approach to beam search, sample-and-filter approaches (such as the one used by AlphaCode), and the SMCG-TD decoding strategy proposed by Ellis et al. (2019). They argue that their decoding strategy outperforms these other strategies, although some of this may be due to the particular hyperparameters they used; for a fixed number of generated programs or fixed computation time their approach seems to perform fairly similarly to SMCG-TD.
strength_and_weaknesses: Strengths:

- Integrating LM generation with MCTS is a good idea, allowing the search process to focus on prefixes with a higher chance of producing good programs.
- The ability of their approach to cache and reuse outputs from the beam-search rollouts means the proposed strategy can be implemented fairly efficiently.
- Their method seems to slightly outperform baseline methods given a fixed runtime budget, without needing to retrain the transformer model.

Weaknesses:

- **(mostly resolved in new revision)** Although the authors refer to their planning algorithm as MCTS, the "Monte Carlo" aspect appears to be missing. The proposed approach is deterministic: it selects actions based on the most-likely tokens following a prefix, and computes "rollouts" using either beam search or greedy decoding.
  - The algorithm thus seems more like a heuristic best-first search than MCTS. Since a lot of the value of MCTS comes from aggregating over randomized rollouts, I would imagine randomization might lead to better performance. (On the other hand, the proposed "sequence caching" wouldn't work for random rollouts.)
  - This choice is also confusing from a clarity standpoint; I expected the rollouts to be sample-based given that the method was based on MCTS.
  - *The authors have rephrased this to not say their method is exactly MCTS, although I do have some remaining suggestions for how to make this clearer; see discussion.*
- The main evaluation results are based on a seemingly arbitrary set of hyperparameters for each decoding strategy, and it's not clear to me that the comparisons (e.g. in Table 1) are fair.
  - **(resolved in new revision)** As one example, their method explores only the top 3 tokens at each state, but their sample-and-filter baseline explores the top 5, and SMCG-TD doesn't have any top-k restriction (at least not stated in the paper).
  - **(resolved in comments)** Additionally, the plots in Figure 4 show much smaller differences between their method and SMCG-TD than the differences in Table 1. This suggests that the differences in Table 1 are partially explained by generating different numbers of programs, or running for different amounts of time, due to the arbitrary hyperparameters selected for comparison.
    - *The authors have included updated results in the comments below. Indeed their approach generates more programs by default. For a small budget, their approach is slightly worse than the SMCG-TD baseline, whereas for a large budget their approach is better. Their approach is also faster relative to the number of unique programs it generates.*
- The novelty of the approach seems fairly small relative to ordinary MCTS and to existing applications of it to LLMs (e.g. the PPL-MCTS approach of Chaffin et al. (2022)).
clarity,_quality,_novelty_and_reproducibility: ### Clarity
The paper is fairly clearly written. However, the fact that the authors refer to the method as "MCTS" despite not having any sampling steps is a bit misleading.

One minor comment: on page 2, I'm not sure what the authors mean by "by treating programming languages as particular languages." What is a "particular language" in this context?

### Quality
As mentioned in the weaknesses section, I think that the proposed algorithm is not really MCTS due to not having any stochastic (Monte Carlo) sample evaluation procedure. Using truly random rollouts would yield a more faithful version of MCTS, and give a better signal of whether MCTS is useful for LLM program generation. (At the very least, it would be good to discuss this difference more explicitly in the paper, and perhaps only refer to the proposed method as being inspired by MCTS.)

I also have a number of concerns with the quality of the experimental results. It's not clear to me how the hyperparameters for their approach or for the baselines were selected, and some choices seem unfair. For instance, their method only considers the top 3 tokens at each step, whereas sample-and-filter uses top 5 sampling, and SMCG-TD may not use any top-k sampling. This means that their method is exploring a significantly smaller search space than all of the baselines! So if good programs exist under a top-3 restriction, their method has a much higher chance of finding them. It seems important to use the same search space for all of the baselines (i.e. use the same top-k restriction) in order to fairly compare the node-expansion strategies.

It's also hard for me to reconcile the results in Table 1 with those in Figure 4. In Table 1, PG-TD appears to often outperform SMCG-TD by a large margin. However, in Figure 4, the two methods have very similar performance at a fixed number of generated programs or at a fixed runtime. Since the hyperparameters directly affect both the number of generated programs and the accuracy of each method, it seems critical that the comparisons in Table 1 be conducted for some fixed value of these. For instance, one could select the number of generated programs for sample-and-filter and for SMCG-TD to match the number of generated programs explored by their method.

### Novelty
I have not seen any other works that uses both MCTS and large language models to do program generation. However, there are previous works that do pairwise combinations of these (e.g. MCTS with a language model, MCTS for program generation, language models for program generation), so the combination of all three is only marginally novel technically speaking.

The two caching methods proposed by the authors seem interesting and useful, although they appear to be fairly straightforward applications of memo-ization techniques rather than being totally novel ideas.

Regardless of the technical novelty, there is value in providing new empirical evidence that these techniques work well in the problem synthesis setting. However, given my concerns about the experimental results, I'm not sure the evidence is strong enough to be significant.

### Reproducibility
The paper describes their approach clearly enough that I think it could be reimplemented, although it is fairly complex so this might require a bit of effort. I think the experiments could be reimplemented as well based on the information  provided, but I'm not particularly confident the findings would be robust to slightly different hyperparameter choices or implementations.
summary_of_the_review: Although combining MCTS with a LLM for program generation is a good idea, there is not much technical novelty, and I have concerns about the validity of the empirical claims and whether it is appropriate to call the proposed approach MCTS given that it removes the stochastic part. I don't think this paper currently meets the bar for acceptance.

I think this paper could be strengthened by
- investigating the behavior of the planning algorithm when rollouts are actually drawn randomly rather than via greedy search or beam search (in other words, when the planning algorithm is actually MCTS)
- being more careful about hyperparameter choices for the baselines to ensure any differences are due to the differences in action selection / exploration / planning, rather than being due to differences in search space size or generated program budgets.

**Updated review:** The authors have addressed my concerns: they have clarified the relationship to MCTS, adjusted baselines to use more similar hyperparameters, and ran a comparison of beam search to sampling-based MCTS (for which their beam search method does better). In the discussion thread below, they have also included additional comparisons for Table 1 (labeled Table F in the comments below) that give a better sense of the performance of their approach; it consistently outperforms sampling-and-filtering, and given either a fixed computation time or a large enough budget, it also seems to outperform the SMCG-TD baseline (although only by a small margin). I have updated my score from 3 to 8, with the understanding that the updated results will be included in the final version of the paper if accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an approach for improving pretrained models of source code for generating better code, if the input includes test cases. Given a pretrained model of code, a natural language (NL) description of the problem, and a few input-output examples, the authors use a Monte-Carlo tree search (MCTS)-based algorithm to generate code that satisfies the input-output examples, instead of just sampling / using beam search and "hoping" that the generated code will satisfy the input-output examples (="pass the tests").
The idea is demonstrated on the APPS dataset, across GPT-2-1.5B and GPT-Neo-2.7B models, where the model passes more tests than the standard approaches of beam search or sampling + post-filtering.
strength_and_weaknesses: ### Strengths
+ The problem is important and has a broad interest.
+ The idea is interesting conceptually and shows improved results.
+ The idea of treating code generation as an RL problem, where input-output pairs provide the reward, is novel and related to much work in program synthesis.

### Weaknesses
- **Usability** - I am finding it hard to see how the approach can be usable in realistic settings. This severe limitation is not explicitly mentioned, and is clear only to readers who are very familiar with the field and its datasets: while the paper places itself besides general models of code such as Codex,  CodeBERT, CodeT5 etc., the proposed approach is actually much more limited than them, and does not "play the same game". While Codex (for example) is only **tested** on executable test-cases to measure its execution accuracy, the proposed approach **requires training** on the input-output pairs. Further, not only that it requires input-output pairs at training time, at test time it can only be applied to examples that have input-output pairs as well.

In contrast, all other models (Codex,  CodeBERT, CodeT5 etc.) can be applied (at test time) to inputs that do not have input-output pairs, and this way they can serve as general code-completion / code-generation / bug-detection assistants.
The proposed approach kind of "overfits" on the existing benchmarks, while losing usability on the realistic tasks that these benchmarks are meant to be a proxy of.
How do the authors see the proposed model to be useful in real life? In which settings and tasks do we expect the user to provide both a natural language intent *and* test cases?

- **Clarity** - discussed in the next section.

clarity,_quality,_novelty_and_reproducibility: ### Clarity
* The main parts of the paper are unclear and not explained: 
    * I did not understand most of Section 3. 
    * The main Figure 2 and Algorithm1 are barely explained, assuming that the reader is not only familiar but also proficient with Monte-Carlo Tree Search (MCTS). 
    * For example, the procedure `UCB_SELECT` appears in the algorithm but not explained. I know that there are some additional details in the Appendix, but: 
        1. `UCB_SELECT` is still not explicitly explained, and 
        2.  in this case the appendices do not only provide "extra details", but are a crucial part of understanding the paper, and this makes the paper be not self-contained without reading the appendices.
* I did not understand Figures 2+3 (both because they were not explained, and because some of the text is tiny) and Algorithms 1+2.

### Questions to authors:
1. How do the authors see the proposed model to be useful in real life? In which settings and tasks?
2. "We assume that the agent has access to a set of test cases" - while this is the assumption of traditional "[programming by example](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/pbe16.pdf)" approaches, in which modern realistic settings is this a reasonable assumption?
3. Figure 1 is not very motivating, because it shows an example that is quite degenerated (replacing a string `S` with `'x' * len(S)`), and claiming that standard beam search could not solve it.
Giving the same problem to Codex (in the OpenAI playground), using the same test input:
```
# Given a string, replace every character with 'x' and print the result.
# Example: 
# replace_char('sardine')
# output: xxxxxxx

def replace_char(
```
which returned:
```
string):
    return 'x' * len(string)
```
Isn't this solution even better than PG-TD's solution in Figure 1? (except that PG-TD's solution makes an in-place modification while Codex's prediction returns a new string, but returning a new string is the more common, simpler, and more realistic solution anyways). I would like to see more motivating cases that show examples that the standard transformer could not solve at all, and were only solved thanks to PG-TD.

4. The paper claims that the standard approach of sampling many examples is not sample-efficient. However, isn't the exhaustive expansion in Figure 3 also not sample-efficient?

### Related work:
* How is the proposed approach different from Ellis et al. (2019) and Le et al. (2022)? 
These works are mentioned in the related work, but I did not understand how do they differ from the proposed approach.
summary_of_the_review: While the idea is interesting conceptually, I think that the settings and assumptions are overly unrealistic, and I do not understand how can the proposed approach be ever useful in real life.

It would have improved the paper if the authors could show that a model that was **only trained** with test cases - works better at test time **without test cases at test time**. Otherwise, if the user of the model needs to provide both a NL intent *and* test cases for every test-example, isn't it a bit too much of a burden for the user of such a model?

I thus currently vote for rejection, but I am open to changing my mind if the authors convinced me otherwise.

=========================
## Post-discussion

The authors have resolved most of my concerns.
I think that the main weakness of the paper remains its limited usability, i.e., the setting it addresses is overall unrealistic.

I increased my score to 6, and I hope that the authors will complete the experiments where they generate the test cases as well, which will significantly strengthen the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Strengths: This is an interesting direction, focusing on a core part of neural code generation that often receives little attention.
The empirical results indicate a significant improvement over baselines for the evaluated models.  The idea of treating code generation as an RL problem, where input-output pairs provide the reward, is novel and relevant to much work in program synthesis. The authors response was strong and addressed many of the weaknesses.

Weaknesses: The main weakness was seen to be the use of both an English description of the task to be solved as well as a set of unit tests (input/output pairs).  Writing code with both a natural language language description and provided unit tests seems a poor match to actual coding, or at least a less challenging problem that working from English alone.

In the end it was decided that this paper is working in an established paradigm and within that paradigm it is a fairly complete paper and would not benefit greatly from another revision.  One reviewer would still like to see a demonstration of generating unit tests from natural language descriptions as was claimed to be possible in an author response.
justification_for_why_not_higher_score: The methodology in which this paper is working was judged to be of limited interest.
justification_for_why_not_lower_score: The methodology does have an established published tradition and the paper is unlikely to benefit from revision.
Decision: Accept: poster