Neural Rankers for Code Generation via Inter-Cluster Modeling

Dear Reviewer 53rB,

We appreciate the time and effort you have invested in reviewing our manuscript. We try to address your concerns below.

Q1. “It is easy to come up with counterexamples to invalidate the method”

A1:

To ensure the efficacy of our method, we operated under the assumption that incorrect solutions exhibited diversity with a low probability of functional agreement among them. This functional assumption also aligned with the practices of AlphaCode [1] and CodeT [2]. However, in certain cases, this assumption may be untenable as LLMs virtually generate incorrect solutions and erroneous test cases. The scarcity of correct solutions may be scarce compared to incorrect ones introduces vulnerability to criteria based on sizes of clusters [1,2], especially when incorrect solutions may surpass correct ones in magnitude. In addition, the prevalence of erroneous test cases undermines the reliability of execution-based criteria [2]. These occurences hinder the effective re-ranking of clusters, causing both SRank and CodeT to falter in their re-ranking capabilities.

Q2. “The significance of the results are not very clear without a significance test.”

A2:

Given a predetermined set of test cases and corresponding solutions, CodeT and our proposed method, SRank, are deterministic, signifying an absence of randomness that could impact their return values. In order to establish our method’s superiority over CodeT, a comprehensive evaluation was undertaken.

Initially, we assessed 6 models across 2 standard benchmarks, including HumanEval and MBPP, which indicated that SRank always obtained better results than CodeT. The extent of performance disparity between SRank’s performance and that of CodeT varied depending on the model and the dataset. For instance, SRank could achieve 6.37% more than CodeT in pass@1 on CodeGen16 and HumanEval, marking a substantial 17.36% improvement while the improvement on WizardCoder34B and HumanEval was 2.95% in pass@1 (~4.08%). Therefore, the evaluation spanned multiple models and benchmarks, underscoring the robustness and effectiveness of our proposed method.

Subsequently, we conducted an ablation study to analyze the impact of the number of test cases on the performance. Results in Figure 3 showed that when the number of test cases varied, SRank consistently performed better than CodeT.

Q3. “CodeT is even worse than Greedy”

A3:

Please allow us to explain that CodeT is worse than Greedy, an observation rooted in the distinct prompts employed for each. In the case of Greedy, our prompting instruction fed to LLMs includes test cases sourced from the datasets, functioning as soft constraints that guide LLMs behavior. Furthermore, the instruction-tuned models, like the WizardCoder family, exhibit a profound comprehension of natural language prompts. Consequently, they generate solutions cognizant of the test cases in the prompts, thereby enhancing the likelihood of satisfying the test cases. Conversely, when generating solutions for CodeT and SRank, the prompts do not contain test cases, rendering their outputs more susceptible to errors. To sustantiate this assertion, we present experimental results where prompts do not include test cases.

The above results illustrate that when employing identical prompts devoid of explicit test case consideration, CodeT surpasses Greedy in performance.

References:

1. Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., ... & Vinyals, O. Competition-level code generation with alphacode. In Science, 378(6624), 1092-1097. 2022.
2. Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J. G., & Chen, W. Codet: Code generation with generated tests. In ICLR. 2023.

Dear Reviewer BPa9,

Thank you for your thoughtful review and invaluable feedback. Your comments are instrumental in refining our work. We appreciate your positive recognition of the paper presentation, our results, and effectiveness of our method. We fixed the typos in the revised manuscript according to your suggestion. We address your questions below.

Q1. Reproducibility

A1:

Please refer to our response in the authors’ Overall Response comment.

Q2. “Evaluation metric is limited in this paper since there is only pass@1 score”

A2:

In the context of real-world usage, it is plausible that end-users typically opt for a singular suggested solution when soliciting the system to generate code. In alignment with this practical scenario, our evaluation protocol centers exclusively around the pass@1 score. This adherence to reporting pass@1 aligns with established conventions observed in numerous works employing HumanEval and MBPP methodologies. Exemplary instances include foundational code language models such as WizardCoder [1], StarCoder [2], and GPT-4 [3], alongside reranking algorithms like Coder-Reviewer [4], LEVER [5], MBR-exec [6], among others.

Q3. “Benchmarks are limited.”*

A3:

Please refer to our response in the authors' Overall Response comment.

References:

1. Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, Daxin Jiang. Wizardlm: Empowering large language models to follow complex instructions. 2023.
2. Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, … StarCoder: May the source be with you! 2023.
3. OpenAI. GPT-4 Technical Report. 2023.
4. Zhang, T., Yu, T., Hashimoto, T., Lewis, M., Yih, W. T., Fried, D., & Wang, S Coder reviewer reranking for code generation. In ICML. 2023.
5. Ni, A., Iyer, S., Radev, D., Stoyanov, V., Yih, W. T., Wang, S., & Lin, X. V. Lever: Learning to verify language-to-code generation with execution. In ICML. 2023.
6. Shi, F., Fried, D., Ghazvininejad, M., Zettlemoyer, L., & Wang, S. I. Natural language to code translation with execution. In EMNLP. 2022.

Dear Reviewer 6Abb,

Thank you for your helpful comments and valuable suggestions. Below we answer your concerns.

Q1. “...why not just execute the test cases of the dataset instead of going to generate new test cases?...”

A1:

Please refer to our response in the authors' Overall Response comment.

Q2. “...the process for generating suitable test cases is inadequately discussed…”

A2:

For generating test cases, we followed the CodeT’s pipeline to produce 100 sequences. At each time of sampling, we feed the context (function) and an instruction to LLMs to get a sequence that can contains multiple test cases. We further post-process generated test cases to filter out those with syntactic errors. Below is the template of our designed prompt.

Below is an instruction that describes a task. Write a response that appropriately completes the request.

### Instruction:
    I have this function stub, please generate 50 test cases for this function. The function stub is as follow:
    ```python
    {input}    
    pass
    ```
    - Each test case is in the form of assertion statement, for example: assert {entry_point}(...) == ...
    - Each test case is in a single line
    - The length of each test case should be too long, ideally less than or equal to 150 letters
    - The test input should not be too long
    - The inputs of test cases should be diverse and cover corner cases of the function
    - Test cases should not be repeated

### Response:
   Here are 50 test cases for function `{entry_point}`:\nassert {entry_point}("

where input is the function header and entry_point is the function name.

Q3. “...it is suggested the authors validate SRank's effectiveness with more challenging datasets…”

A3:

Please refer to the overall response for more details.

Q4. “Table 2 results indicate Cluster sizes are a more effective feature than Pass rates, which seems counterintuitive as Pass rates more closely resemble the Pass@K metric”

A4:

We welcome the opportunity to clarify that results in Table 2 demonstrate that Cluster sizes appear to have a bigger impact than Pass rates, which seemingly looks counterintuitive first as Pass rates closely correlates with Pass@K metric. This problem is primarily attributed to the nature of generated test cases. We prompt LLMs to produce test cases and employ some simple heuristics to assess their syntactic validity. However, they may be prone to errors in which their expected outputs may be incorrect, thereby diminishing the Pass Rates. In contrast, the Cluster sizes are not dependent on expected outputs of the test cases. We operate under the assumption that there are many ways for solutions to be incorrect, whereas correct solutions share the same functionality. This assumption results in correct solutions forming larger clusters, with smaller clusters potentially containing incorrect solutions. Therefore, the Cluster sizes are likely to be more robust than Pass rates.

Q5. “Cluster sizes feature—ascending or descending”

A5:

Please allow us to elucidate that we re-rank cluster sizes feature in the descending order since we assume that there are many ways for solutions to be incorrect while correct solutions share the same functionality. Therefore, correct solutions tend to form larger clusters, and smaller clusters may contain incorrect solutions.

References:

1. Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J. G., & Chen, W. Codet: Code generation with generated tests. In ICLR. 2023
2. Ni, A., Iyer, S., Radev, D., Stoyanov, V., Yih, W. T., Wang, S., & Lin, X. V. Lever: Learning to verify language-to-code generation with execution. In ICML. 2023

Q3. “Why should we rely on the test cases generated by the model?”

A3:

For clarification, we remind that in the context of our work, a test case can be decomposed into a test input and a test output. For example, a full test case assert f(i) == o has the test input i and test output o.

Our reliance on the test cases generated by pre-trained language models stems from their capacity to produce syntactically and semantically accurate test cases. These expansive models are trained on extensive code datasets, thereby imbuing them with the capability to generate test cases that are, to a certain extent, syntactically and semantically sound. Syntactic correctness entails adherence to the format assert function_name(*args, **kwargs) == output or in specific cases, assert function_name(*args, **kwargs) is None/True/False. Semantically, correctness implies that the test input *args and **kwargs conform to valid argument types, order, and value ranges, while the test output aligns functionally with the input.

We measure the percentage of test cases with valid syntax and semantically correct test inputs. This is done by checking the 1) format or structure of the test case by regular expression, 2) test input and 3) test output by compiling them.

HumanEval

MBPP

From the table, since the percentage of invalid test cases is very minor, we can confirm the ability of code language models in generating test cases with correct syntax and correct semantics to a certain extent. Note that the reported numbers above are not deduplicated. Although the total number of test cases seem to be large, for each sequence of test cases, we only choose the first 5 valid test cases. With 100 sequences of test cases, the possibly maximum number of test cases for SRank in our experiments is 500 test cases.

Q4. “Why the evaluation is confined to Python language only? There are many multilingual benchmarks available now.”

A4:

We agree that there are multilingual benchmarks available and our method can be generalized to most of the programming languages. In this work, we choose Python as a demonstration language as it was also employed in previous work with the same research scope, e.g., CodeT [1], Coder-Reviewer [2], LEVER [3], MBR-exec [4], CodeRanker [5], and AlphaCode [6]. We leave the experiments for other programming languages for future work.

Q5. “In a real setting (say in an industry setting), is this a good assumption that 100 solutions will be sampled? …, why an LLM that has billions of parameters need to generate 100s of solutions?”

A5:

As we indicated in the introduction, maximum likelihood-based decoding often suffers from a degeneration problem, while the correct solutions of the problem may exist within the sampled solutions from the model distribution. Empirically, numbers in Table 1 (with updated greedy decoding results) showed that greedy decoding results can be much worse than SRank. This supports the argument that sampling a sufficiently enough number of solutions can lead to higher chances that those sampled solutions would contain the correct one. Reranking algorithms such as SRank are specifically devised to discern and prioritize the correct solutions among the sampled set. Again, the ultimate goal of this work and many other works e.g CodeT, Coder-Reviewer, LEVER, MBR-exec, CodeRanker, AlphaCode, etc., is to improve performance for real world tasks, in this case, code generation, through reranking sampled solutions with the minimal trade-off for time and resources.

Besides, the number 100 solutions is employed in the paper and can be seen as a hyperparameter. In application, a specific number can be adopted to balance the trade-off between accuracy for time and resources since performance tends to improve as more solutions are sampled.

Dear Reviewer c5Kt,

We are sincerely grateful for your insightful reviews. Your professional feedback not only guides us in crafting a more comprehensive and competitive paper but also reinforces our enthusiasm, especially regarding your positive acknowledgment of our results on code benchmarks, rigorous evaluation and ablation study. Below we address your questions.

Q1. “... Can you explain - how grouping solutions that pass the same subset of test cases potentially”

A1:

In addressing your query, we provide a specific illustration. Consider a scenario utilizing the CodeT reranking method, where a cluster encompasses two solutions, denoted as f_1 and f_2, both passing all prescribed test cases with the exception of one particular assertion, assert f(i) == o. In such instances, our assurance extends only to the divergence of f_1(i) and f_2(i) from o; yet, it remains plausible that f_1(i) != f_2(i). This observation underscores the distinct functionality of f_1 and f_2, despite their classification within the same cluster.

The fundamental objective of clustering is to assemble solutions with identical functionality into sets, subsequently ranking these solution sets as opposed to directly assessing an extensive array of individual solutions. CodeT, unfortunately, deviates from this foundational principle. Notably, its inadequacy becomes pronounced, particularly when the quantity of test cases is limited. This leads to the aggregation of functionally disparate solutions into a shared cluster, resulting in suboptimal performance, as elucidated in Figure 3 within our submitted paper.

Our proposed method systematically addresses the issue of functional inconsistency within clusters. If two solutions, f_1 and f_2, coexist in the same cluster, and given the identical test case as described earlier, it is guaranteed that f_1(i) == f_2(i), irrespective of the output value o. Essentially, our clustering algorithm yields finer-grained clusters than CodeT concerning functionality. Please refer to section 5.2 Case Study which shows some examples regarding functional inconsistency of CodeT. Consequently, our algorithm enhances the efficacy of the cluster ranking step. This distinction is illustrated in Figure 3, where we compare the CodeT line with the Cluster size + Pass rate line. Both lines utilize cluster size and pass rate as cluster features, with the disparity lying solely in the method of cluster formation.

Q2. “How does modeling inter-cluster interactions better indicate cluster correctness?”

A2:

As articulated in the paper, "The intuition is that clusters with high overlap exhibit greater shared functionality". We elucidate why modeling inter-cluster interactions enhances the indication of cluster correctness through a concrete example. Consider solving a competitive programming problem where individuals propose solutions, which may be correct or incorrect. Here, clusters 1, 2, and 3 represent distinct solutions by three programmers addressing the same problem, respectively. In practice, incorrect solutions fail because they cover most cases but fail in specific instances. For two people with two incorrect solutions, each may fail for different reasons. In Figure 2, person 2, i.e cluster 2, may overlook the special case with input as 0, while person 3 forgets to cover input as 3. Consequently, when calculating the overlap in functionality, i.e., the match in outputs when executing the solutions on numerous test inputs, the solutions sharing the maximum output overlap are likely optimal.

To further validate that modeling inter-cluster interactions aids in ranking clusters, we present the results of reranking solely by matrix I without any cluster features V. In this scenario, V is a column vector with 1 at every entry. Consequently, the ith entry in R is the sum of functional overlap between the ith cluster and all other clusters.

HumanEval

MBPP

The results demonstrate that incorporating interaction modeling consistently elevated performance beyond random. Furthermore, reranking with interaction alone significantly outperforms the performance of greedy decoding in some cases, such as 51.13 vs 28.49 for CodeGen2.5, 50.01 vs 39.63 for StarCoder, 62.75 vs 47.00 for CodeX002 in HumanEval.

3. Concern on the assumption that incorrect solutions are diverse and there is a low probability of functional overlap among incorrect solutions.

Answer:

Our proposed method operates under the assumption that incorrect solutions are diverse and there is a low probability of functional overlap among incorrect solutions, so it is crucial to validate this assumption. Detailed results addressing this are presented in Section A of the Appendix. Quantitative findings indicate that the probability of lower functional overlap between incorrect solutions surpasses that of higher functional overlap, consistent with our assumption. In addition, we provide some qualitative examples through interaction matrices, revealing substantial functional overlap among correct solutions and low functional overlap among incorrect solutions.

4. Reproducibility

Answer:

Regarding reproducing our results, we provide the anonymous repository at https://anonymous.4open.science/r/SRank---ICLR-2024-BC32

References:

1. Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J. G., & Chen, W. Codet: Code generation with generated tests. In ICLR. 2023

2. Ni, A., Iyer, S., Radev, D., Stoyanov, V., Yih, W. T., Wang, S., & Lin, X. V. Lever: Learning to verify language-to-code generation with execution. In ICML. 2023