AuPair: Golden Example Pairs for Code Repair

The title is confusing. The paper tries to solve text-to-code problems, where the model is given a task description and some test cases. The paper did not solve code repair problems.

The paper does attempt to solve the code repair problem (see lines 101-105) as we describe at the beginning of the Approach section: given a problem and its initial guess (i.e. broken program), the task is to generate a fix (i.e. repaired solution), which is scored by the percentage of test cases it passes. The exact repair prompt is shown in the Appendix (section A.2). We will update the text to clarify this point.

The evaluation is questionable. The paper did not report results using standard metrics (e.g., pass@k for varies k). How does your approach perform in standard pass@k metrics?

We cannot provide fair results for the pass@k metric because the pass@k metric makes an assumption that all $k$ responses from the LLM are i.i.d. generated, whereas our approach produces fixes in a specific order: the first AuPair is more useful than the second, which is more useful than the third, etc; so their success probabilities monotonically decrease as a function of $k$. We will explain this in Section 3.

We report the test case average, or test pass rate, which has also been used in prior work for evaluating LLMs for coding [1, 2, 3].

[1] Measuring Coding Challenge Competence With APPS. Hendrycks et al, 2021.

[2] An Empirical Study of the Non-determinism of ChatGPT in Code Generation. Ouyang et al, 2023.

[3] Benchmarking the Communication Competence of Code Generation for LLMs and LLM Agent. Wu and Fard, 2024.

How does your approach compare with other RAG-based techniques?

This paper is not related to RAG techniques: we propose an algorithm that devises a fixed set of AuPairs which are used at inference time, as opposed to RAG methods that retrieve relevant documents / knowledge bases at inference time to generate responses. It could be potentially used in conjunction with RAG techniques but then that is orthogonal to the contribution of the paper and is more suitable for future work. In contrast, our set of AuPairs and inference prompts are fixed before any test cases are seen, nothing is retrieved at test time.

The evaluation only shows the results for Gemini variants and missing results for other models.

We have provided results on 4 models, 2 Gemini models and 2 Gemma models, spanning distinct architectures and meaningfully different levels of capability. But, absolutely, more models are better (as pointed out by Reviewer Yjae as well) so we intend to run more experiments and provide results in a week.

The approach may not be practical. In Section 2.2, for each problem in D_{val}, we need to make |C| calls for all the pairs in the candidate list C. This is extremely expensive. Can we use other ways to rank the candidates (e.g., sequence similarity)?

Our proposed algorithm discovers AuPairs, which once discovered, can be used to boost performance on several different datasets, as our out-of-distribution generalisation results in Figure 6 indicate. It is important to note that this is a one-time cost that our algorithm has to incur, in return for significant boosts in performance across 6 other datasets using the same fixed set of AuPairs.

Indeed, there could be ways of ranking candidates in less expensive ways such as sequence similarity, distance to closest pair embedding, clustering, etc. In this paper, we chose to rank the candidate pairs by the problems they solved, thereby partitioning the space of pairs in terms of their effect on performance, not the features of the pairs themselves. We did some initial investigations in the direction of clustering pairs by similarity, but the results were not promising enough at the time so we did not pursue it further. This is a good suggestion for future work and we will include it in Section 5.

I don’t understand the reasons behind picking best-of-N as the baseline.

Our setup involves an inference compute budget of N LLM calls, so we use best-of-N as the baseline since sampling-based methods such as best-of-N and self-consistency have been the most commonly used methods in this setting. As we have also conveyed to reviewer yYRs, we are working on adding an additional self-repair baseline [1] that first gets verbal feedback from the LLM based on the buggy code and then uses that verbal feedback to generate a repaired response.

[1] Is Self-Repair a Silver Bullet for Code Generation? Olausson et al, 2023.

The paper lacks comparisons with alternative baseline methods…such as Self-Repair[1]

We intend to provide a comparison with self-repair[1] with the same number of LLM calls at inference in a week.

[1] Is Self-Repair a Silver Bullet for Code Generation? Olausson et al, 2023.

The presentation of the experimental datasets appears overstated. While the authors mention the use of seven datasets, six of these are extracted from CodeContest[2]... all experiments focus on code generation benchmarks, lacking evaluations on code repair benchmarks like the self-repair section in Livecodebench[3] or the APR section in xCodeEval[4].

Yes, since CodeContests is a collection of several different datasets, 5 of our datasets are borrowed from there (LiveCodeBench and CodeJam used in this paper are not from CodeContests). However, the problems in these individual datasets differ along other axes such as topic coverage, granularity and distribution across difficulty levels, implementation vs mathematically oriented problems, problem description format, to name a few.

Hence, we believe these datasets are still meaningful to assess out-of-distribution generalisation capability of AuPairs since LLMs have been shown to be sensitive to problem formatting [1]. Nonetheless, based on the reviewer's suggestion, we intend to run additional experiments on Livecodebench for repair and report back with results by the end of the discussion period.

[1] Does In-Context Learning Really Learn? Rethinking How Large Language Models Respond and Solve Tasks via In-Context Learning. Long*, Wu* et al, COLM 2024.

The conclusions regarding diversity are not sufficiently substantiated. The authors claim that AuPairs provide diversity without a trade-off in performance. However, in Figure 7(b), while diversity scores increase from Gemini-1.5-flash to Gemma-9B to Gemma-27B, performance scores of AuPairs show a decline, suggesting that the improvement in diversity may indeed come at a performance cost too.

Figure 7(b) shows the relation between performance and diversity of the generated fixes, with one colour per model. Best-of-N generates diverse but low scoring fixes (except on Flash), while AuPair always generates higher-scoring responses (the star is higher than the square for each model), which can be highly diverse (e.g., when using Gemini-1.5-Pro, top right), or less diverse with Gemma models. In other words, AuPairs never trade off performance, but they also don’t automatically increase diversity. We apologise that our caption and original description was not very clear about this, and the plot itself is easy to misread, but the revised version should be much clearer.

Why did you choose not to include the execution results of guesses directly within the prompts? Including these results could potentially provide more context and improve the model's performance by refining subsequent guesses.

Yes, absolutely, including execution results could potentially improve the model's performance, but as we have described in our setup, we do not expose the model to the actual test cases (we only provide the score), and giving it execution feedback in the context would leak test case information to the model, making this out of scope for this paper. However, this is a great suggestion for future work, so we thank the reviewer for their comment.

Could you clarify the setup of your baseline method, "best of N"?

The best-of-N baseline consists of the following formatted according to the repair prompt (see Appendix A.2):

test problem text
test problem guess

The same prompt is then used to generate N responses, out of which the highest-scoring response is selected. Note that here, highest-scoring means the solution that passes the most test cases.

On the other hand, the AuPair method consists of the following formatted according to the repair prompt:

<aupair problem text
aupair guess
aupair fix>

test problem text
test problem guess

This leads to N different prompts for N AuPairs, leading to N responses, out of which, again, the highest-scoring response is selected. Note that due to each AuPair being included as a 1-shot example, we get N different prompts as input to the LLM, compared to the best-of-N setup, where the same prompt is used N times.

The inference compute for best-of-N baseline and AuPair is exactly the same, since both of them make N LLM calls.

The experimented setting somewhat already “reveals the answer”: as described in the paper “given a coding problem, its test cases, and …” … test cases should be assumed unknown at any point during the generation.

The test cases are not provided to the model as part of the prompt. The part "given a coding problem, its test cases, and …" is used to refer to the full setup where the test cases are not provided during response generation, they are only used for evaluation. We will update the text to clarify this.

this paper experiments with Gemma and Gemini models in various sizes…better alternatives should be considered

We intend to provide additional results for GPT-3.5/4o next week (and will follow up on this as we get results).

It is unclear (from section 3) what evaluation metric is used in this paper… A program should pass all test cases to prove its correctness…

We report the test case average, or test pass rate, which has also been used in prior work for evaluating LLMs for coding [1, 2, 3]. We will highlight the metric for easier understanding.

We will also report the number of problems with all test cases passed: this is less granular but addresses the potential risk of bias pointed out.

[1] Measuring Coding Challenge Competence With APPS. Hendrycks et al, 2021.
[2] An Empirical Study of the Non-determinism of ChatGPT in Code Generation. Ouyang et al, 2023.
[3] Benchmarking the Communication Competence of Code Generation for LLMs and LLM Agent. Wu and Fard, 2024.

Sampling baseline sample only N responses; but for the proposed method, it involves N AuPairs and then N fixes, so that would cause the compute to be 2N?

Both baseline and our proposed approach use N LLM calls. The only difference between baseline and our approach is in the prompt that is passed to the LLM. In baseline, all the N LLM calls use the same prompt containing the problem text and guess code:

test problem text
test problem guess

In AuPair, each of the N LLM calls contains an AuPair as the 1-shot example, formatted according to the repair prompt (Appendix A.2):

<aupair problem text
aupair guess
aupair fix>

test problem text
test problem guess

To be extra clear: AuPair uses N calls, not 2N, just like the baselines we compare to.

It is unclear what the green and blue blocks mean in Figure 1; similarly, what the purple block mean in Figure 3.

The blue blocks in Figures 1 and 3 refer to "guesses" from the train dataset and the green blocks are "fixes". Note that the train dataset contains blue guesses, and the LLM after repair generates green fixes. Pairs consist of guesses and fixes both, so they are represented as the combination of the blue and green.

The purple blocks in Figure 3 refer to guesses from the validation dataset. In both Figures 1 and 3, the pairs have blue and green blocks, indicating that pairs are collected and AuPairs are extracted only on the training dataset.

I am curious on the types of fixes model learn to perform, have you observed any major categories, e.g., “fixing variable name copy errors”, “fixing logical computing errors”, etc.

Section A.5 in the Appendix contains examples of 10 types of fixes, along with a short description of each type of fix. We have observed categories such as adding extra if conditions for edge cases, fixing input parsing, adding loop exit condition, fixing logical bugs, to name a few.

As mentioned in the paper, AuPair is created on a held-out validation set. How would the proposed method apply when no held-out validations are available?

In that case, we split any given dataset for which we want to generate AuPairs, into training, validation, and test datasets. So if the validation dataset is not provided separately, we construct this split from our side to get a validation dataset.

In line 079, the authors claim that they propose a general-purpose, domain-independent algorithm for self-repairing LLMs. However, later, in line 082, the authors state that they focus on code repairing.

We wanted to emphasise that our algorithm is domain-independent but in this paper, we focus on the code-repair task as an evaluation for our proposed algorithm. We got carried away by our enthusiasm while writing but we'll tone down this sentence, thanks for pointing this out!

The unit tests are an essential part of the pipeline…I do not see how the proposed framework can be applied to other domains. Can the authors please clarify?

Intuitively, the unit tests act as grounded feedback for our algorithm which is used to drive the selection of AuPair in the right direction. However, it is not the only way of feedback. As mentioned in the Conclusion section (line 538), we have talked about using feedback from a reward model or a critic [1, 2]. In this case, the scores that we currently obtain from evaluation on unit tests can be replaced by the scores produced by the critic without having to change the AuPair algorithm.

[1] CRITIC: Large language models can self-correct with tool-interactive critiquing. Gou et al, 2024
[2] CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning. Le*, Wang* et al, 2022.

Please provide a clear list of all inputs required by the algorithm, including the validation set, and explain how each input is used in the process.

In this work, we have two phases: (1) Candidate pair dataset generation consisting of guess-fix pairs (2) AuPair selection algorithm. AuPair selection algorithm is concretely expressed in Algorithms 1 and 2 with exact inputs and outputs, which is our core contribution.

Candidate pair dataset generation is explained in detail below and we'll include it in the Appendix. However, note that if a pair dataset is given with guess-fix samples, this stage is not required.

Full pipeline with input-output listed in brackets:
Given: coding dataset consisting of problem description and unit tests

Phase 1:

• Construct guess dataset: generate initial guess (using guess generation prompt in Appendix A.2) for each problem in the input coding dataset, and the score for this initial guess as the percentage of unit tests passed by the initial guess (input: coding dataset containing problem descriptions and unit tests, output: guess dataset containing problem descriptions, unit tests, initial LLM-generated guesses, scores for guesses)

• Train / val / test split from guess dataset (input: guess dataset, output: train dataset, val dataset, test dataset)

• Generate large set of candidate pairs using the train dataset (input: train dataset, output: candidate pairs, see Figure 1)

Phase 2:

• Extract AuPairs from the candidate pairs by evaluating on the validation dataset (input: candidate pairs, val dataset, output: AuPairs, see Figure 3, Algorithms 1 and 2)

Inference:

• Evaluate the impact of using AuPairs on the test dataset (input: AuPairs, test dataset, output: final score)

Figure 1 is high-level, giving no concrete details. Can the authors please be more specific of how the extraction algorithm works?

We give the details of how to generate pairs in the caption for Figure 1, but we can flesh this out in the main text to make it easier to understand. The pair generation phase proceeds as follows:

1. We begin with the curated dataset that consists of the problem, its initial guess generated by the LLM, and the score of this initial guess. This score is computed as the percentage of passed unit tests for that problem by the guess.

2. Next, a problem and its guess are sampled from this dataset and the repair prompt is composed (the exact prompt is given in the Appendix (Section A.2).

3. This repair prompt is then passed as input to the LLM which generates a repaired solution, or a fix.

4. Next, the score of that fix is calculated in the same way as the score of the guess. If the fix score is higher than a guess score, this pair of (guess, fix) along with their scores, and the problem and unit tests is stored in the set of candidate pairs.

5. Furthermore, if this fix does not solve all unit tests, it is added back into the dataset as a new guess, since there is further scope for improvement.

We thank the reviewer for their feedback and would like to highlight the key results and takeaways from the discussion period:

• Additional baseline: We have now added an extra baseline – self-repair [1]. It is clear from the results, AuPair outperforms self-repair across all datasets and models (has matching performance for only AtCoder Gemma-9B and AtCoder Gemini-1.5-Flash).

• Additional model: We now have results using GPT-4o-mini on AtCoder:

As is evident from these results, all our trends from the other models hold: AuPair outperforms all baselines even on GPT-4o-mini.

• Additional dataset: We have added results for repair on LiveCodeBench in the appendix of the updated draft (Section A.1.4); the results clearly indicate that all the trends we have observed in the original set of experiments hold: AuPair exhibits superior performance to the baselines across all models.

• Additional metric: We have also reported the percentage of fully solved problems as an additional metric in Fig. 11 in the appendix. All the trends that we observed for the earlier metric, test pass rate, hold for this stricter metric as well.

• Text revisions: We have updated the figure captions to clarify the approach and added an extra pair generation algorithm) in the appendix; we hope this gives a clear idea of the steps involved in the AuPair algorithm.

Given that the extended discussion period is drawing to an end, we would like to request the reviewer to reconsider their score, especially in light of all the additional results and clarifications we have provided that clearly show that our proposed approach outperforms all baselines across a large number of models and datasets.

[1] Is Self-Repair a Silver Bullet for Code Generation? Olausson et al, 2023.