Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation

Thank you for your time and effort in reviewing our paper! These are very helpful suggestions and we address your questions here:

W1: The sections detailing the approach are somewhat brief, which leaves me wanting a deeper understanding of the full method, especially since the study focuses on employing a divide-and-conquer approach for code generation.

Apologies for any confusion. Due to page constraints, we couldn't describe the complete divide-and-conquer process in detail in the main text. However, we supplemented the Implementation Details in Appendix A.1 and have respective prompts in Appendix C to help understand the model's operation. As described in Algorithm 1, FunCoder is a recursive process following a DFS pattern. We use square brackets [L1] below to denote the line number in Algorithm 1.

• FunCoder [L1], when solving each function $f$, first performs the Divide stage [L3-L9], where the LLM initially writes the function and identifies some potential sub-problems, represented as sub-function stubs (e.g., def f(xs: list[int]) -> int) [L3]. In this process, we identify the sub-problems of the current problem, thereby understanding the dependency relationship between functions.
• For each decomposed sub-problem $g_1, g_2, \ldots$, we recursively use FunCoder to obtain the final implementation $G_i$ for that sub-problem [L5-L8]. This $G_i$ shall replace the previously incomplete subfunction stub signature in the final program.
  • FunCoder [L1], when solving each function $g_1$, …
  • FunCoder [L1], when solving each function $g_2$, …
• Now that all sub-problems of $f$ are implemented, we move on to the Conquer stage [L11-13] to complete the larger problem. By combining the signature $f$ and the final implementations $G_i$ of sub-problems, we generate the complete implementation $F$ [L11] and return it [L13].

Let's describe how this algorithm works in detail by combining it with the example given in the lower half of Figure 1.

[a.1] FunCoder(a)
│  [a.3] LLM(a) -> A, {b, c}       # divide
├──[b.1] FunCoder(b)
│  │  [b.3] LLM(b) -> B, {d, e}    # divide
│  ├──[d.1] FunCoder(d)
│  │  │  [d.3] LLM(d) -> D, {}     # divide
│  │  └──[d.13] return D           # nothing to conquer
│  ├──[e.1] FunCoder(e)
│  │  │  [e.3] LLM(e) -> E, {}     # divide
│  │  └──[e.13] return E           # nothing to conquer
│  │  [b.11] LLM(B, {D, E}) -> B*  # conquer
│  └──[b.13] return B*
├──[c.1] FunCoder(c)
│  │  [c.3] LLM(c) -> C, {}        # divide
│  └──[c.13] return C              # nothing to conquer
│  [a.11] LLM(A, {B, C}) -> A*     # conquer
└──[a.13] return A*                # final result

We will add this content to the Appendix to provide a more detailed explanation of our method. Hope this addresses your concerns about our approach.

Q1: How the model decide the functions to be further divided or too simple? Any experiment?

We rely on the knowledge of code and instruction following capabilities acquired by the LLM during its training. This enables the LLM to make approximate decisions on whether a function should be further decomposed. As stated in Appendix A.1, the LLM is prompted in the divide phase to implement the current function and simultaneously introduce new sub-functions if necessary.

As shown in Appendix C.2, we designed the Divide prompt with a 2-shot example. One example demonstrates that complex problems should be decomposed, while the other example shows that simple problems can be implemented without new sub-functions.

Furthermore, in Table 5, we observed that functions produced in the Divide stages are highly domain-specific. These sub-functions are likely to be generated based on knowledge from pre-training data, supporting how LLM can decompose tasks based on pretrained knowledge.

Q2: How the conquer works? Does the model aware of the dependency among those sub functions?

Regarding the complete process of divide-and-conquer, why Conquer works, and whether the model is aware of function dependencies, we have briefly discussed this in response to Weakness 1. Here, we elaborate further:

During the Divide phase, we extract the hierarchical relationships between functions to construct a dependency tree. Conquer merges finished sub-problems, and this is entirely consistent with the principles of divide-and-conquer. In our task, Conquer provides the finalized sub-functions in the context and rewrites the parent function based on them. We will make this point clear in future versions.

Conquer is indispensable. In the Divide phase, the function is generated before the sub-problem definitions, so the details of the sub-problems are not clear at this point. And the invocation of sub-functions or positions from where they are invoked by the parent function might be incorrect. It is therefore necessary to regenerate the function after all sub-functions are finished. In Table 3, we conducted an ablation study on the Conquer stage (Two-pass vs. One-pass) and empirically found that enabling Conquer significantly improves the code generation performance.

Q3: What is the cost of each part? What about overall efficiency and resource utilization.

In Appendix A.6, Table 11, we listed the token usage of gpt-3.5-turbo for both our method and the baselines. We have also provided further statistics on token usage in our General Response. Upon your request, we have further broken down the token usage for each stage of FunCoder in the following table. Hope this answers your questions.

Our algorithm itself is very lightweight and does not consume much CPU or RAM resources. Resource consumption comes from calling the LLMs. For an overall analysis of token efficiency, please refer to the general response. We will include these in our next revision.

We thank you for your time and effort in reviewing our paper! We find your suggestions very helpful and we hereby address your questions:

W1: The equivalence-modulo-inputs idea requires knowing the accurate input domain and designing corresponding input samplers, which are oversimplified in this paper.

It is indeed challenging to ensure that LLMs generate reliable and valid inputs. However, in order to verify code correctness using LLMs, there are typically only three major methods:

1. Predict bugs by just reading the code (e.g. self-refine).
2. Generate unit tests for self-testing (e.g. CodeT).
3. (Ours) Generate inputs and select the best program based on outputs of sampled programs.

In our comparisons, we focused more on the widely used unit-test method, which not only has to generate reliable inputs but also provide correct case outputs. If the generated output is incorrect, program verdicts will be deeply impacted. Experiment results in Table 3 empirically show a clear advantage of our method over unit tests.

W2: Functionality consensus selects the most common functor candidate, but commonality may not necessarily correlate with correctness in code generation. Correct samples can even be exceptional in sampling when the task is challenging to the LLM.

Improving performance beyond pre-trained capabilities is hard. While it's quite challenging to prove it formally, our consensus still works better than clustering and other methods, as is shown in Table 3. We look forward to future work substantiating this finding.

Admittedly, commonality is less likely to boost performance on problems beyond the LLMs' knowledge, but it isn't necessarily outperformed by the Standard baseline. However, commonality empirically reduces incidental errors, as we exemplified in general response.

Refer to xCodeEval results in Table 1. Although our method yields little improvements on Expert-level problems where LLMs can almost never get right, it happened to perform quite well on Hard-level and easier problems. This can be similarly observed on MATH dataset.

W3: The diversity of studied models is a bit limited. It would be helpful to run on more open models such as StarCoder2.

Thanks for your suggestion. We adapted our approach and found that FunCoder can also achieve good results with StarCoder2-15b, bringing its pass@1 of 59.8 on Standard to 78.7 with our method. More promising results can be found in our General Response.

W4: "A program specifies its functionality (or behavior) through the control flow..." is not accurate.

Thank you for pointing out this mistake. Indeed, considering only the control flow of a program is incomplete when it comes to behavior. This was an oversight during our writing process. We'll correct this in our next revision as "the program's control flow and logic".

Q1: Can you exemplify "cascading errors" and explain why sampling multiple functions helps mitigate such errors?

In this context, "cascading errors" refer to where an error in the sub-function causes the parent function to also fail. For example, a badly implemented 'cosine' function will cause everything depending on it to malfunction.

As discussed in W2, sampling implementations on a single function can reduce its incidental errors, so in decomposition it would also reduce overall (cascading) errors in the whole program.

Q2: Can the selection of benchmarks really exercise the core part of solving complicated coding tasks?

Following AlphaCode and CodeLLAMA's definition of 'complex' competition-level datasets, we used xCodeEval and MATH in our evaluations. Table 1, 4, 10 show that our method achieves significant improvements on these more difficult problems.

However, we fully agree with your concerns regarding complex problems. Due to the scope of our work, we haven't yet been able to test our performance on software development tasks, which often involve engineering details like changing requirements, code retrieval, and real-time debugging. Nevertheless, we believe that the idea of divide-and-conquer and consensus can be equally applied to such complex problems and represents a promising area for future research.

Q3a: When computing the token usage, did you include tokens of unused samples when computing "functionality similarity"?

Yes, we included the token count for unused sampled functions, and we obtained token cost directly from OpenAI API's statistics. Hence the token count reported in our paper is the total token expenditure from all API calls throughout the process of solving a problem.

Q3b: Can you also provide more statistics such as the medium token consumption in case the average number is biased by simple tasks?

Thanks for your suggestion. We've added a lot more statistics in our General Response and we'll include these data in our next revision.

Q3c: The token consumption is much smaller than I expected according to the large prompts (and these will be called multiple times).

Thank you for pointing out the concern about token costs. This is because the OpenAI Inference API still only charges prompt tokens once per call, when we use n=k sampling. We further discussed token costs in our general response, and concluded that it costs only $O(kN)$ tokens, same as Standard sampling.

Q4: How's the token usage compared to other baselines?

We list in Table 11 (Appendix A.6) the token usage for all other baselines. Note that some baselines are not open-sourced and the token usage details were not reported in the respective papers, so they are not included in the table.

Q5: Is the technique single-turn or multi-turn when being implemented for evaluation?

We used single-turn chat completions. In each call we only include a common prefix (system prompt and few-shot examples) and one assistant question describing the current task. This helps reduce token costs, context lengths and prevents context contamination.

We thank you for your time and effort in reviewing our paper! These are very helpful suggestions and we address your concerns as following:

W1: The recursive decomposition of tasks into sub-functions inherently leads to the generation of numerous function headers, bodies, and documentations, which can significantly inflate the token count.

Indeed, decomposing the original problem into multiple functions may increase token usage. However:

• Function headers and documentation don't occupy much tokens, since they typically just have a few lines, and are way smaller than the function body that might span to dozens of lines.
• Programs that split functions don't have to be longer than un-split programs, due to function re-use which helps reduce redundant code.
• Our method does not force the LLM to decompose overly simple tasks into subfunctions. In fact, the standard method also generates sub-functions, and both methods have similar resulting code lengths. Our approach just regenerates function with fine-grained divide-and-conquer above that.

We might also add that, we showed in Table 11 (L759) that although our token usage was not the best of all, but that it was small enough given its state-of-the-art performance (e.g. LDB took 23K tokens to get 82.9% while ours made 85.4% with 5.4K tokens).

W2: Missing the median and the maximum tokens required to solve the HumanEval problem.

Thank you for pointing out the flaws in our initial statistical method. We reviewed Table 3, the ablation study of FunCoder on HumanEval with gpt-3.5-turbo, re-ran statistics on the original data and obtained the following results (you can find them in our General Response):

W3: When tackling complex problems, the token consumption grows exponentially.

We did not provide a token complexity analysis in the original paper, but our method actually costs only O(N) tokens and it linearly scaled to the size of the generated program. We discussed this proof in detail in general response, and this will be added to the next revision of this paper.

Q1: Why baselines are different on GPT-3.5 and GPT-4?

Some results are directly obtained (and cited) from the original papers, and we've marked them with an underline in Table 1. Some methods only reported results for GPT-4, and upon careful examination, results for other models were not mentioned in these papers. In Appendix A.2, we provided details for which results were derived from the original papers, and specified whichever methods were specifically tailored for code generation or mathematical reasoning tasks.

Some methods compared are not fully open-source or lack detailed instructions. Since we weren't able to reproduce them consistently, we had to cite them verbatim instead. We'd like to add more experiments in the next revision and get more updates on this topic.

Q2: In Table-4, why do the authors choose CoT or self-refine as the main baseline while no more comparing with Parsel?

Parsel did not provide prompts or code for tasks beyond code generation with HumanEval, and it is not designed specifically for mathematical reasoning. Therefore, we did not compare Parsel on the math tasks. Instead, we introduced baselines that were specifically designed for mathematical reasoning, which are more commonly used in that area, such as CoT, self-refine, and CR.

• Standard and CoT serve as text-based baselines for mathematical reasoning, compared with other methods that solve math problems through code generation.
• Self-Refine uses runtime feedback to fix code, serving as a baseline for comparison with our sampling-based approach.
• CR (Cumulative Reasoning) is another baseline for step-by-step problem solving and was the previous SOTA method for the MATH dataset. Unlike our approach, which employs a divide-and-conquer strategy, CR uses a bottom-up technique that progressively derives the final answer.

Details about these methods are provided in Appendix A.2 (L627).

Q3: Why do the authors choose not to disclose their code during the submission phase?

We are still organizing our codebase during the paper submission phase. However, we are confident that we can prepare a minimal working code and accompanying bash scripts for replicating the experiments within the next few months. Meanwhile, as the principles of our method are relatively straightforward, to ensure reproducibility of our work, we have provided complete prompts verbatim so that just calling an API with these prompts would suffice. These prompts should work with most methods and models unless specifically noted.

We sincerely thank you for your time and effort in reviewing our paper! We find your suggestions very helpful and we address your questions as follows:

W1: The idea of decomposing the problem into subproblems and solving them recursively with an LLM is not entirely new.

As is discussed in 4. Related work, there is indeed previous work that decomposes problems into subproblems and explores them through search. But many of those focus on mathematical reasoning or multi-hop question answering, and can have difficulties applying to code generation.

Specific to code generation, we innovatively leveraged the inherent advantages of functions, using function signatures to identify sub-problems. We further relate sub-problems via function declaration and invocation, thus decomposing complex tasks in a more natural way. We believe that this form of task decomposition can have a more straightforward advantage in code generation and can better elicit the potential of code models.

W2: Comparison between consensus and clustering.

We find your suggestion to be very constructive. We have made a comparison between these methods on gpt-3.5-turbo and have observed a considerable advantage in functional consensus:

Clustering from AlphaCode strictly classifies programs into mutually independent groups by exactly identical outputs. Our method measures output similarity based on many input cases, which is a more permissive approach. Since inputs to a program may have edge cases, treating two programs distinctly just because one output was different, without considering how similar they are, is sub-optimal. For example:

• Consider finding all square roots of a float. Generate 10 functions.
• 4 results know that a positive number has two square roots. 4 results know that a negative number has imaginary square roots. Only 2 results considered both points.
• Notice that the model gets 60% right for either point independently, but only 20% when the points are put together.
• Clustering would put programs in three categories [4, 4, 2] based on output, and end up choosing who only gets one point right. But with our function similarity, the one who gets both points right that is on-more-aspects similar will be favored.

Getting benefits on Clustering often requires more programs (even up to 1M in AlphaCode paper). Our method does well with just 11 sampled programs. Consensus is also exceptionally good at pass@1 while AlphaCode focused on pass@10 instead.

Q1: On average, how many decomposition levels are used when solving the code generation tasks?

We analyzed the depth of functions from the results and show them in this table:

Note that since we rely on the intrinsic capabilities of the model to determine whether or not to decompose functions during generation, we cannot forcibly control the depth of decomposition. The LLM tends to generate shallow code for simple problems and vice versa, which is why the average depth is just slightly above 1.0. But this method is quite effective on complex problems exhibiting deeper function depths.

Q2a: Are the Standard and CodeT prompts used in the experiments the ones shown in Appendix C.1?

Yes, both Standard and CodeT used the prompts from Appendix C.1. We will clarify this point in a later revision and explicitly specify the prompts used for each method on HumanEval.

Q2b: Is this type of decomposition prompting also better for the Standard and CodeT methods?

To ensure the fairness between the decompose prompt and the standard prompt, we used the same example in all prompts. So the Standard method also breaks down the original problem into multiple functions, but it generates all the functions all at once, whereas our decomposition prompting allows for recursive sub-function generation. However, it's worth noting that the decomposition prompt always requires iterative-decomposition, since it only produces sub-function stubs and would otherwise produce incomplete programs.

In Table 3, we conducted an ablation study on the results of decomposition. "One-pass" refers to just Divide (recursively decomposing) functions above Standard, and "Two-pass" refers to having both Divide and Conquer but without functional consistency applied. The results indicate that applying just recursive decomposition will still yield a considerable improvement.

Q3: How does the consensus method compare to other self-consistency or AlphaCode-like majority clustering methods?

Thanks for your suggestion. Clustering in AlphaCode can be viewed as self-consistency over programs in code generation. So we re-ran the experiments with majority clustering mentioned in AlphaCode, and you can see the results in our response to Weakness 2.

Q4: In the abstract and line 167, it is said that GPT4 performance on HumanEval is about 97% but I can't find that number in Table 1. Is it mentioned elsewhere?

We apologize for any confusion caused by our wording. What we intended to convey is that on the HumanEval dataset, StableCode-3b with FunCoder (81.0% pass@1) achieved 97.7% of the performance of GPT-4 with Standard (82.9% pass@1). This statement in the abstract aims to highlight that FunCoder can significantly enhance the code generation performance of small open-source models, bringing them close to that of advanced models, which to our belief was a very interesting finding.

A similar point is also discussed in section 3.1.3 (L163-167). We apologize again for any misunderstanding caused by any ambiguity in our paper, and we shall clarify this in a future revision.