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

Authors: jingchang  chen
hongxuan  tang
zheng  chu
qianglong  chen
zekun  wang
ming  liu
bing  qin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 15:18:18

Abstract: Despite recent progress made by large language models in code generation, they still struggle with programs that meet complex requirements. Recent work utilizes plan-and-solve decomposition to decrease the complexity and leverage self-tests to refine the generated program. Yet, planning deep-inside requirements in advance can be challenging, and the tests need to be accurate to accomplish self-improvement. To this end, we propose FunCoder, a code generation framework incorporating the divide-and-conquer strategy with functional consensus. Specifically, FunCoder recursively branches off sub-functions as smaller goals during code generation, represented by a tree hierarchy. These sub-functions are then composited to attain more complex objectives. Additionally, we designate functions via a consensus formed by identifying similarities in program behavior, mitigating error propagation. FunCoder outperforms state-of-the-art methods by +9.8% on average in HumanEval, MBPP, xCodeEval and MATH with GPT-3.5 and GPT-4. Moreover, our method demonstrates superiority on smaller models: With FunCoder, StableCode-3b surpasses GPT-3.5 by +18.6% and achieves 97.7% of GPT-4's performance on HumanEval. Further analysis reveals that our proposed dynamic function decomposition is capable of handling complex requirements, and the functional consensus prevails over self-testing in correctness evaluation.

Main paper: 
 introduction: 
 Over the past few years, large language models have been observed to attain significant advancements in coding capabilities (OpenAI, 2023; Touvron et al., 2023) . Meanwhile, models designed specifically for coding tasks have also been introduced (Rozière et al., 2023; Lozhkov et al., 2024; Pinnaparaju et al., 2024) . Although LLMs can proficiently generate simple code snippets, they suffer from a decline in performance as code requirements become complicated.Numerous efforts have been made to tackle this complexity. The two-stage methods (Jiang et al., 2023; Zelikman et al., 2023) employ the plan-and-solve strategy, which first generates a draft outline for the complex task and uses it as guidance for implementing the code in the second stage. Multiagent development frameworks (Hong et al., 2024; Qian et al., 2023) mimic real-world software development workflows, assign different roles to LLMs and collaborate to solve a complex goal. Self-improvement (Shinn et al., 2023; Chen et al., 2024) , on the other hand, refines the program in accordance with execution feedback from self-generated unit tests.Despite fruitful efforts made by the previous methods in dealing with complex problems, certain challenges still remain unsolved: (1) Two-stage approaches need to design a complete plan at the beginning and lack the ability to adjust the top-level design during implementation, leading to suboptimal decomposition. (2) Multi-agent collaboration frameworks are cumbersome and rely heavily on LLM capabilities, making them difficult to generalize to smaller open-source models. (3) Code refinement through self-tests depends on the correctness of generated unit-tests. Our preliminary study ( §3.1.3) finds that models generate unreliable self-tests in abundance. These incorrect tests may mislead self-improvement and, at worse, exacerbate program errors.To address these issues, we propose FUNCODER, a code generation framework utilizing a divide-andconquer strategy and a novel functional consensus mechanism on functions to decompose complex problems. Starting from the main problem, FUNCODER introduces new functions to cope with certain sub-problems. The new functions will be decomposed recursively, eventually forming a tree of functions. FUNCODER then combines functions bottom-up to achieve increasingly complicated objectives. By dividing-and-conquering tasks into simpler sub-functions, complexity can be gradually reduced. However, errors in sub-functions may propagate to the whole program, thereby damaging overall reliability. We propose functional consensus that samples multiple functions and selects the one demonstrating consensus, measured by the aggregated similarity among candidates. By reaching a consensus, we reduce the discrepancies in code behavior and thus alleviate cascading errors.Algorithm 1 FUNCODER procedure Require: Entry func, f root = {h root , d root , ϕ} Require: Large language model, LLM 1: function FUNCODER(f cur )2:-Divide -3:f ′ cur , {f i } ← EXTRACT(LLM(f cur ))4:for f i ∈ {f i } do 5:if b i is NOTIMPLEMENTED then 6:f * i ← FUNCODER(f i ) ▷ recursion 7:end if 8:ADDCHILD(f cur , f * i )9:end for 10:-Conquer - """return factors of x""" raise NotImplementedError() def sum_common_factors(a, b): """sum the common factors""" fa = find_factors(a) fb = find_factors(b) return sum_common(fa, fb)def sum_common(a: list, b: list) -> int:"""sum of common elements""" raise NotImplementedError() 
introduce new functions: 
 Figure 2 : Left: Algorithm for FUNCODER, explained in detail in Appendix A.6. Right: Comparison between decomposition by planning and our approach. FUNCODER introduces new functions to describe sub-goals solely with code, achieving a more natural way of requirement decomposition.2 FUNCODER: Divide-and-Conquer Meets ConsensusA function is defined as a relation between a set of inputs and outputs where each input is assigned exactly one output (Halmos, 1998) , denoted as y = f (x). In computer programming, a function is identified by its header h f with its body b f , and is commonly accompanied by a documentation d f to improve readability. Functions can be invoked from other procedures, allowing for the decomposition of large and complicated requirements into smaller structures that exhibit high comprehensibility and quality (Dahl et al., 1972) . Generally, human programmers tend to decompose tasks into clearly defined sub-functions and then implement them recursively, making functions eligible for re-usage, taking advantage of the divide-and-conquer principle. Inspired by this, FUNCODER recursively divides the requirement and conquers functions to formulate a sophisticated solution, unleashing the potential of LLMs in code generation.Divide is a top-down process that iteratively breaks down problems. Given a code generation problem, the process begins from the entry function f root . We instruct the model to introduce new functions f i ∈ CHILD(f cur ) that solve certain sub-goals while writing the current f cur . To reduce the complexity involved in each generation, we only require the headers h fi and documentation d fi of new functions to be generated, while their implementations b fi can be postponed. After completing the current function, the model starts to address those unimplemented sub-functions and complete b fi into f ′ i . This process stops when the model deems functions too simple to be further divided, finally forming a dependency tree T = TREE(f root , CHILD(f root )). The divide process is similar to a search starting from the entry function, gradually involving new sub-functions while writing the current, and implementing them recursively. We guide the entire process through a depth-first search.Conquer is a process of achieving complex objectives through aggregating smaller functions. We notice that child functions are not yet implemented during the top-down process of writing parent functions. As a result, these parent functions may not be able to effectively utilize the child functions, or misuse them at worst. FUNCODER deals with this issue by re-generating functions in inverse topological order on the dependency tree T -starting from leaves, complex goals are handled by compositing solved children asf * cur ← F(f ′ cur , {f * 1 , f * 2 , . . . }) | f * i ∈ CHILD(f cur). Divide and conquer naturally achieve both decomposition and composition during code generation. Unlike two-stage and agent-based methods, our approach dynamically introduces new functions along the process, making it less burdensome than producing a complete plan at the very beginning. Moreover, while planning or agents require chat capabilities, FUNCODER represents sub-tasks through functions (Figure 2 ), making it more applicable to specialized code generation models.The decomposition of complex tasks benefits from solving easier sub-goals, but might introduce the risks of cascading errors, which refers to errors in sub-functions that lead to errors in ancestral functions. To mitigate this, we introduce Functional Consensus which aims at reducing inconsistencies in program behavior. This is achieved by sampling multiple functions and selecting the one that exhibits consensus, as measured by the aggregated similarity of functionality between candidates, thus abating outlier functionalities.Functionality Similarity A program specifies its functionality (or behavior) through the control flow and logic defined by its code semantics. However, comparing the functionalities between two programs based on their semantics is somewhat challenging. By decomposing the requirement into functions, FUNCODER is able to view the function behavior as a black box that maps arguments into return values. Considering two functions f and g with the same input domain D(f ) = D(g), we define the similarity between them sim(f, g) as the identicalness of outputs when given the same input values.EQUATIONThe similarity becomes 1 if and only if two functions output consistent values for all inputs: ∀x ∈ D(f) : f (x) = g(x) ⇔ sim(f, g) = 1.We notice that the input domain D(f ) is unbounded in most cases, making its measurement barely feasible in practice. Thus, we approximate it by sampling a subset of possible inputs X ∼ D(f ) with an LLM.Consensus is reached by selecting the candidate f * holding maximal similarity with others after sampling multiple function implementations F = {f (i) } for the same requirements.EQUATIONBy introducing functional consensus, FUNCODER produces functions that are more consistent and common in functionality, while omitting abnormal samples. The process is applied to not just the final program, but also to every sub-tree during the bottom-up conquering stage, resulting in step-by-step, thorough verification from the most fundamental functions all the way up to the whole program.We design FUNCODER as a procedure that takes a problem in the form of a function signature f (x), and produces a final solution f * (x), as exemplified in Figure 1 . Given a problem f (x), FUNCODER partially implements the function as f ′ (x) referring to unimplemented sub-functions g(y) and h(z). These sub-functions are then fed into FUNCODER to be recursively coped with. We then sample k implementations f ′ (i) (x) based on solved children g * (y) and h * (z). Functional consensus is calculated by evaluating candidates on possible inputs. The function sharing maximal behavioral similarity is combined with solved children to formulate the final solution. 
experiments: 
 We conduct experiments on competition-level code generation and mathematical reasoning benchmarks with state-of-the-art LLMs, which are covered in section §3.1 and §3.2, respectively. In addition to GPT models (Ouyang et al., 2022; OpenAI, 2023) , we also conduct experiments with community models like Llama3 8b (Meta AI, 2024) , StableCode 3b (Pinnaparaju et al., 2024) , and CodeLlama 34b (Rozière et al., 2023) . We use the instruct variant of these models and inference on a single A100-80G under BF16 precision with vLLM (Kwon et al., 2023) . We choose three benchmarks for code generation evaluation: (a) HumanEval (Chen et al., 2021) includes entry-level coding questions; (b) MBPP (Austin et al., 2021) contains questions of standard library invocation and programming basics; and (c) xCodeEval (Khan et al., 2023) consists of algorithmic challenges sourced from the competitive programming platform CodeForces.Benchmarks We adopt the full test set (164 problems) for HumanEval, and sample 200 for MBPP and 500 for xCodeEval, respectively. Following EbTech (2024), we split the xCodeEval into 4 subsets based on problem difficulty: Easy (≤ 1200), Mid (1200-1599), Hard (1600 Hard ( -1999) ) and Expert (≥ 2000) . The evaluation metric for code generation is Pass@1 unless specified.Baselines We compare FUNCODER with standard prompting (Brown et al., 2020) , two-stage decomposition method Parsel (Zelikman et al., 2023) , self-testing method CodeT (Chen et al., 2023a) , self-improvement methods Reflexion and LDB (Shinn et al., 2023; Zhong et al., 2024) , and multiagent developing framework MetaGPT (Hong et al., 2024) . We implement Standard prompting with a 1-shot demonstration. CodeT samples 11 solutions with standard prompting and evaluates them on model-generated tests. The results for Reflexion are reproduced from the original code.Implementation Details FUNCODER uses a 2-shot prompt in the divide stage and 1-shot for conquering sub-functions. The number of sampled implementations in the functional consensus is set to 11 for code generation tasks. For further implementation details, please refer to Appendix A.1.Table 1 shows the code generation performance on advanced proprietary models, GPT-3.5 (Ouyang et al., 2022) and GPT-4 (OpenAI, 2023) . For basic programming questions, HumanEval and MBPP, FUNCODER surpass previous SOTA methods by +3.3% in Pass@1 and reduce the error rate by 18.6%. Furthermore, FUNCODER demonstrates a substantial improvement on competition-level problems, outperforming others by 10.4% in GPT-4 and 35.3% with GPT-3.5. We observe that FUNCODER can 11 .Experiment results demonstrate that our method archives state-of-the-art performance on various models, ranging from basic programming to competition contests.FUNCODER Democratize to Smaller LLMs Limited by the LLM capabilities, the application of selfimprovement or multi-agent methods on smaller models is without ease. By keeping decomposition and composition within the code generation process, our approach exhibits better generalization. As shown in Table 1 , with FUNCODER, StableCode 3b achieves around 118.6% relative performance to standard GPT-3.5, and also aligns closely with GPT-4 by about 97.7% on HumanEval.Preliminary Study on Self-Testing Method We conduct a preliminary study targeting the self-testing method on HumanEval, results are shown in Figure 3 .a with further details in Appendix A.5. We first verify whether model-generated programs can also pass model-generated self-tests: (a) If a program passes self-tests, most from GPT-3.5 would also work on system tests, as much as 19.5% /64% ≈ 30.5% programs from StableCode are rejected, indicating that smaller models like StableCode may not effectively self-test and detect program errors on its own. (b) In the event of failed self-tests, a large portion of failures are attributed to issues in self-tests instead of the programs, on both GPT-3.5 and StableCode. These phenomena indicate that self-testing methods have limitations in generating correct and reliable unit tests. As a result, we design functional consensus to not require any assertion, but perform mutual verification between solutions instead, as opposed to self-testing.Effectiveness of Functional Consensus Functional consensus or self-testing may be viewed as ranking algorithms for selecting functions. To measure ranking effectiveness, we conduct an analysis on HumanEval with GPT-3.5. For each problem, 11 candidates are ranked with 3 strategies: consensus, self-test, and random shuffle (as a baseline). Effectiveness is measured via Pass@k, i.e. if any of the top-k ranked programs pass the system test. Figure 3 .b shows that functional consensus achieves 94.7% upper bound (Pass@11) performance by selecting a single function (Pass@1), and is close to that of self-test on Pass@4. This clearly demonstrates that functional consensus can effectively evaluate correctness and pick the most promising implementation on the first attempt.Ablation and Token Usage To analyze the impact of dividing, conquering, and functional consensus in FUNCODER, we carry out an ablation study with different settings. Studies that replace consensus with self-testing, or with AlphaCode-like (Li et al., 2022) clustering, are also included. The ablation is constructed on HumanEval with GPT-3.5, as shown in Code can be viewed as a tool for augmenting the reasoning capabilities of LLMs (Chen et al., 2023b) .Alternative to text-based reasoning like Chain-of-Thought (Wei et al., 2022) , programs can offer unique advantages in terms of iteration and calculations. To test the generalizability of FUNCODER beyond algorithm challenges, we conduct an experiment on MATH (Hendrycks et al., 2021b) , a competition-level mathematical reasoning benchmark.Benchmark The experiment is conducted on a subset of the MATH test set, including 500 randomly sampled problems that can be classified into 7 disjoint subjects or 5 difficulty levels. It can be noticed that labels in MATH are formatted in L A T E X, rendering exact-match verdicts impractical. We, therefore, follow previous work (Zhang et al., 2024) and adopt GPT-4 to determine the correspondence between predictions and labels, with further details provided in Appendix A.4.Baselines We compare FUNCODER with the text-based baselines: Standard Prompting and Chainof-Thought (Wei et al., 2022) , and program-aided baselines: Program-of-Thought (Chen et al., 2023b) , Self-Refine (Madaan et al., 2023) , Cumulative Reasoning (Zhang et al., 2024) . The results of Cumulative reasoning are reported in the original paper. Standard prompting and chain-of-thought reasoning use 7-shot demonstrations constructed from the train set. Program-of-Thought and Self-Refine prompt the model with 1-shot demonstration to generate a solution() function that solves the problem. Additionally, self-refine iteratively refines programs based on runtime feedback. All baseline methods are run with self-consistency (Wang et al., 2023) at 5.Implementation Details FUNCODER adopts a program-aided reasoning setting that writes a solution() function and obtains the final prediction by running this program. The number of sampled implementations |F | in functional consensus is set to 5 to match baseline methods.The experimental results on MATH are shown in Table 3 . It shows that program-aided reasoning generally outperforms text-based reasoning. With GPT-4 as the backbone, FUNCODER outperforms the strongest baseline Cumulative Reasoning (Zhang et al., 2024 ) by (6.0 / 8.3%) and surpasses the vanilla program-aided baseline PoT (Chen et al., 2023b ) by (10.0 / 14.7%). When using GPT-3.5turbo as the backbone, FUNCODER exceeds the strongest baseline by (6.2 / 11.1%) and outperforms PoT by as much as (13.0 / 31.7%), which indicates that our approach has a strong advantage over both text-based reasoning and other program-aided reasoning methods. On open-source models, FUNCODER with Llama3 outperforms PoT by (12.4 / 38.0%). It has even reached competitive performance against the state-of-the-art method based on GPT-3.5 (45.0 v.s. 48.6). When employing StableCode and CodeLLaMA as the backbone, our approach achieves significant improvements by (12.2 / 84.7%) and (9.2 / 60.5%), respectively. This improvement demonstrates that our approach can significantly boost smaller LLMs, democratizing the complex reasoning capabilities of open-source LLMs through programming. This suggests that text-based reasoning is inadequate for tackling challenging mathematical reasoning problems. The same situation is also observed in PoT. In contrast, our method consistently demonstrates high performance even on challenging problems, particularly excelling on level 5 difficulty with nearly double the performance compared to PoT and CoT. This reflects that our method, with divide-and-conquer applied, can effectively cope with complex problems.Decomposed Functions are Domain-Specific We hypothesize that questions from the same subject require similar knowledge reserves, which should be reflected in the functionality of the sub-functions.To verify this hypothesis, we statisticize the common sub-functions of FUNCODER in each MATH subject, as shown in Table 4 . It is apparent that different subjects require different abilities, each with its own set of sub-functions closely associated with the domain knowledge. In addition, these common sub-functions are fundamentally basic and straightforward. As exemplified in Appendix B.2, our method is able to leverage and combine these basic sub-functions to achieve more complex goals, thereby reducing the complexity of reasoning and enhancing performance. Large Language Model for Code Code pre-training has received widespread attention, with early models based on small language models (SLM) (Feng et al., 2020; Lu et al., 2021; Wang et al., 2021) .In recent years, with the development of large-scale pre-training techniques, code LLM has emerged, showing remarkable performance in downstream code tasks (Chen et al., 2021; Nijkamp et al., 2023; Li et al., 2022; Rozière et al., 2023; Li et al., 2023b; Guo et al., 2024) . Tasks between code and natural language (NL) can be generally divided into three major categories: NL2Code tasks such as code generation (Austin et al., 2021; Chen et al., 2021; Hendrycks et al., 2021a; Khan et al., 2023) and code search (Husain et al., 2019a) ; Code2Code tasks including code completion (Lu et al., 2021; Zhang et al., 2023a; Liu et al., 2024) , code translation (Ahmad et al., 2023; Zhu et al., 2022; Yan et al., 2023) , and test generation (Siddiq et al., 2023; Schäfer et al., 2024) ; Code2NL tasks like code summarization (Husain et al., 2019b; Jin et al., 2023) . This paper focuses on code generation tasks, ranging from basic to competition level.Code Refinement and Self-Testing Code doesn't always run as expected; it could contain syntax errors, dead loops, or bugs. It's essential to debug and refine the code to ensure better quality.CodeT (Chen et al., 2023a) generates unit-tests to score the implementation. AlphaCode (Li et al., 2022) clusters programs based on whether generated program outputs were identical or not. Selfimprovement methods (Madaan et al., 2023; Shinn et al., 2023; Chen et al., 2024; Zhong et al., 2024) design closed-loop procedures that repeatedly refine the code based on the feedback. Like real-life software development processes, multi-agent frameworks (Hong et al., 2024; Qian et al., 2023) construct specific LLM roles, Tester or QA to generate tests. These studies adopt a shared paradigm wherein self-tests are generated through LLMs. However, Olausson et al. (2024) points out the challenge that LLMs have certain shortcomings in self-repairing their code. This paper avoids these shortcomings by proposing functional consensus as a reliable method of evaluation.Program-Aided Reasoning and Agents Aside from code generation tasks, the program can be a tool that augments LLM to solve complex reasoning questions or interact with external environments. Program-of-Thought (Chen et al., 2023b) and PAL (Gao et al., 2023) Decompose for Complex Problems Several recent works employ decomposition to reduce the complexity of hard problems. Least-to-Most (Zhou et al., 2023) adopts a two-stage approach, which first decomposes complex problems, and then solves each sub-problem individually to tackle complex reasoning tasks. Successive Prompting (Dua et al., 2022) adopts a dynamic decomposition, iteratively breaking down problems and addressing sub-problems. Tree-of-Thought (Yao et al., 2023) breaks down complex problems into state spaces and uses tree search to solve them. Parsel (Zelikman et al., 2023) introduces decomposition to code generation tasks, taking a three-stage to break down requirements into draft and intermediate parsel programs. RepoCoder (Zhang et al., 2023b ) performs a retrieval in repositories to complete unfinished code one by one. Unlike these methods, FUNCODER recursively decomposes problems into a tree structure, hence gradually reduces its complexity. 
discussion: 
 Limitations Our approach unleashes the potential power of functions in programming, which is advantageous on well-defined problems such as competitive programming, or program-augmented reasoning tasks. These scenarios do not however represent all use cases, such as open-ended problems or casual software development. Nevertheless, we believe that the idea of divide-and-conquer and sub-modular consensus utilized by FUNCODER can be extended to a wider range of problems, and we consider this as a future exploration.Broader Impact While code generation is increasingly utilized in software development, Large Language Models (LLMs) are still prone to generating toxic, vulnerable, or malicious code. Such programs pose risks and should be used or executed with extra caution. 
conclusion: 
 In this paper, we presented FUNCODER, a novel code generation framework that integrates the divideand-conquer strategy with functional consensus to address complex requirements. FUNCODER had demonstrated superior performance compared to state-of-the-art methods on various benchmarks and models. Our findings highlighted the effectiveness of dynamic decomposition and functional consensus in writing complex code, which suggests that FUNCODER may have the potential to empower further improvements in code generation and other fields. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not release new data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We reference the code ( §A.2), data ( §A.3) and models ( §A.1) in the Appendix.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: In the supplementary materials, we provide the details of implementation (A.1), baseline information and settings (A.2), benchmarks (A.3), metrics (A.4), settings in the analysis (A.5), and additional experiments (A.9). We also demonstrate the example solutions of our method and baseline in Appendix B, and include all the prompts in Appendix C. Models We access the OpenAI models GPT-3.5 (gpt-3.5-turbo-0613), GPT-4 (gpt-4-1106-preview) and GPT-4o mini (gpt-4o-mini-2024-07-18) through Azure OpenAI. Weights of community models Llama3 (Meta-Llama-3-8B-Instruct), Codestral (Codestral-22B-v0.1), StableCode (stable-codeinstruct-3b), CodeLlama (CodeLlama-34b-Instruct-hf) and StarCoder2 (starcoder2-15b-instruct-v0.1) are downloaded from HuggingFace (Wolf et al., 2019) and served over an OpenAI-like API on a single A100-80G GPU under BF16 precision with vLLM (Kwon et al., 2023) .Divide We instruct the model to write the current function and introduce new functions with clearly defined sub-goals. The prompt C.2 for the divide process includes two examples: one example needs to involve new functions that are left unimplemented; and another where the sub-goal is simple enough that no further decomposition is necessary. The model generates a Python code block with a temperature of 0.2, and the code block will be extracted to represent a tree of functions with new functions as the children of the current. We require that any new sub-function do not refer to existing functions, to avoid circular references. This generation process will be attempted at most 3 times until any valid code with a proper signature is found in the output. FUNCODER then traverses the function tree via depth-first search and restricts the max depth of the tree to 6.Conquer We apply the composition of sub-functions to rewrite the parent function after all subfunctions have been fully decomposed. Code for sub-functions is made visible to the LLM, which is requested to rewrite the current function with a 1-shot demonstration (C.3). With functional consensus applied, the model samples multiple implementations with a temperature of 0.8, and the one that reaches consensus will be kept for further bottom-up processing.The functional consensus is applied in the conquer stage. Formally, Consensus@k samples k-1 implementations in the conquer stage, and reuses the one produced in the divide stage, resulting in a set F of k candidate programs. Then we prompt the model with 1-shot (C.4) to generate potential inputs X for the given function and use them to feed and execute the program.As described in Eq 2, when two functions output the same value in a given input, they will both add 1 point to the overall similarity. A thrown exception or timeout during execution assigns -100 points to the candidate as it indicates potentially problematic code. Similar to self-testing methods, we also leverage the example input/output at the root node to filter out candidates that have wrong functionality. Finally, the one candidate with maximum scores over all inputs is selected, as it reaches consensus with other implementations.Hierarchical Code Interpreter Divide-and-conquer represents the problem hierarchy through structured code. To gain insights of this information, we design an interpreter that syntactically parses the generated output and organizes them into a graph of functions. We are thus able to decompose complex tasks by representing sub-goals through the connections of multiple functions. LLMs may produce vulnerable code even if prompted by trusted inputs, making direct execution or eval() on generated code especially hazardous. Our framework addresses this with the use of a sandboxed environment to contain untrusted code execution, preventing the LLM from hanging up or even breaking the system.Standard Prompting conducts one-time generation and directly output the entire code or final results. In code generation tasks, we use a 1-shot prompting setting with 0.3 temperature. For MATH, we sample 1 question-answer pair per subject in the train set, resulting in a 7-shot prompt, and run self-consistency (Wang et al., 2023) with consistency@5 and temperature 0.7.CodeT (Chen et al., 2023a) samples multiple code solutions X and unit-tests Y . A unit test is an assertion consisting of given input and expected output, whereas in Python it takes the form of "assert func(x) == y", CodeT then checks the programs over self-tests and divides the functions into sets; the score of such a set is defined as the number of functions within multiplied by the number of succeeded tests. Finally, CodeT selects the function with the most agreement (in the biggest set). Similar to the setting of FUNCODER, we sample 11 candidate solutions with 0.8 temperature.AlphaCode-like Clustering is introduced with the model AlphaCode (Li et al., 2022) Reflexion (Shinn et al., 2023 ) is a closed-loop agent system that generates unit tests and iteratively refines the program based on the self-test feedback. The results for GPT-4 on HumanEval and MBPP are reported in the original paper. Based on officially released code3 , we test results with GPT-3.5 and community models under the reflexion strategy with max_iters=2 and Pass@1. For the xCodeEval benchmark, as it is judged through standard input/output, we wrap the standard input into function arguments and obtain the return value as the output in the form of "def main(input_str: str) -> str", and the sample input/output are also transformed to visible tests for reflexion process.MetaGPT (Hong et al., 2024) employs a multi-agent strategy that assigns roles and encodes humanlike software development procedures. The scripts for reproducing the results were not made public as of this paper was completed. Therefore, we include the original result for GPT-4 on the HumanEval dataset under the with feedback setting.LDB (Zhong et al., 2024) segments programs into basic blocks and tracks the values of intermediate variables after each block throughout runtime execution, allowing large language models to verify the correctness of smaller code units. We adopt the results as-is reported in the paper.Chain-of-Thought Prompting (Wei et al., 2022) generates step-by-step reasoning leading to the final output answer. The solution is formatted in L A T E X, and use \boxed to mark the final answer. We sample 1 shot per subject in the MATH train set, resulting in a 7-shot demonstration, and running with consistency@5 and a temperature of 0.7.Program-of-Thought (Chen et al., 2023b) utilizes the coding ability in LLMs to generate programs rather than text-based solutions for reasoning tasks. In MATH, we hint the model with 1-shot prompting to generate a solution() function that returns the final answer to the problem. The program is then executed in a Python environment and obtains the return value. If an exception is thrown during execution, the model will try to regenerate a new program until it succeeds or reaches 3 attempts. Similar to CoT, Program-of-Thought samples 5 programs at a temperature of 0.7 and votes the final result.Self-Refine (Madaan et al., 2023) iteratively prompts the model to give feedback and refine the generated code based on it. Self-refine does not incorporate self-tests, and the refinement is conducted solely on model feedback. In our preliminary study on HumanEval, this feedback is weak and cannot improve performance. However, in MATH, the solution program can be executed without the need for generated assertions. Thus, we extend the self-refine to capture the runtime error trace as feedback and refine the code until it can run or exceed 3 retries.Cumulative Reasoning (Zhang et al., 2024) starts from decomposing the input problem into propositions and conducts bottom-up reasoning until the final answer can be concluded. The results for Cumulative Reasoning are reported in the original paper under with code setting. Pass@k When a program is passed (or accepted), it means that the program must pass all system tests without errors and within the time limit. In our experiments, we set the time limit to 2.5 seconds. Pass@k judges k independent programs, and if any of them can pass, the result will be 1.In most of our experiments, we use Pass@1 as the metric, as it reflects the accuracy of the method framework achieved without feedback from humans. Pass@k, on the other hand, is equivalent to filtering programs through hidden, human-annotated test labels.The ground truth label in MATH is written in L A T E X, and the accuracy between labels and model predictions cannot be directly calculated through exact-match (EM). MATH provides a judge program5 that preprocesses LaTeX syntax and check whether two disambiguated strings are equal. However, this is insufficient for evaluating LaTeX-formatted labels with variant program outputs. We follow the evaluation criteria from previous work (Zhang et al., 2024) , using GPT-4 to assess the consistency between predictions and ground truths, with prompt shown in C.6.Details of Preliminary Analysis on Self-testing (Figure 3 .a) The preliminary study is conducted on the HumanEval dataset, which includes system tests S to evaluate the accuracy of the program, as well as one human-annotated canonical solution c. 3 and detailed explanations about these conditions can be found in Table 8 . -¬(p, T ) ∧ (p, S) ∧ (c, T )In the event of self-test failure, there must have been at least one error in either program or tests, so this condition should never occur.Details of Ranking Strategy Comparison (Figure 3 .b) We obtain 11 candidate programs from FUNCODER on HumanEval with GPT-3.5 and rank them through three strategies. This ensures that the same candidate set is used for a fair comparison. An effective ranking strategy should prioritize placing correct programs at the forefront and filter out those with errors. Thus, we measure the effectiveness by computing Pass@k results on the top-k-ranked programs selected by each strategy. The Pass@11 result serves as an upper bound as it uses all programs to compute the pass rate.How We Count Frequently Used Functions in MATH (Table 4 ) In the mathematical reasoning experiments, we used a subset of 500 items from the MATH test set, with an average of 71.4 questions per subject. However, it is not very confident to represent common functions from only 71.4 programs. Therefore, we sample 3000 problems from the MATH test set for this experiment and run the divideonly setting of FUNCODER on them. Then, the occurrence of sub-functions is counted based on their names after extracting the function nodes of code trees for each category.We hereby provide a detailed explanation of FUNCODER algorithm works, with respect to Algorithm 1 from Figure 2 (a copy is included below for simple reading). As mentioned, FUNCODER is a recursive process following a DFS pattern. We use square brackets (e.g. [L1]) below to denote line numbers in the pseudocode.Algorithm 1 FUNCODER procedure Require: Entry func, f root = {h root , d root , ϕ} Require: Large language model, LLM 1: function FUNCODER(f cur )2:-Divide -3: f ′ cur , {f i } ← EXTRACT(LLM(f cur )) 4: for f i ∈ {f i } do 5: if b i is NOTIMPLEMENTED then 6: f * i ← FUNCODER(f i ) ▷ recursion 7: end if 8: ADDCHILD(f cur , f * i ) 9:end for 10:-Conquer -11:F cur ← SAMPLE(LLM(f ′ cur , CHILD(f cur )) 12:f * cur ← FUNCONSENSUS(F cur ) We hierarchically describe how this algorithm works in detail by combining it with the example given in the right half of Figure 5 . • FunCoder goes through the Divide stage and the Conquer stage for each of the functions.• Based on the current function, Divide generates an implementation of itself and stubs for subfunctions. Within this stage, each function would appear at most once in input and twice in output. All Divide stages consume no more than 3N tokens.• Conquer regenerates the parent function based on its stub and all finalized sub-functions. Herein each function will appear at most twice in input, and sampled k times in output. If k = 1, consensus is implicitly disabled. All Conquer stages shall consume at most (k + 2)N tokens.So FunCoder requires no more than (k + 5)N tokens in input-output, making its token consumption O(kN ) even at worst-case, aligning with other sampling-based methods such as CodeT and AlphaCode-like clustering. Furthermore, when sampling is disabled (k = 1), our method has a token consumption of O(N ), which also aligns with the vanilla Standard method.This section focuses on why functional consensus might enhance the correctness of programs and how it differs from other consistency-based methods. Self-consistency (Wang et al., 2023) is widely employed in the realm of LLM reasoning. It samples multiple sets of answers and uses voting to select the most consistent result, where the answers typically consist of named entities, choice options, or numbers. However, this approach faces challenges when voting on sampled programs, as programs describe executable logic instead of data, making it unobvious to determine whether two programs are equivalent just from the looks.When it comes to picking programs, functional consensus in FUNCODER looked beyond the literal symbols and used a different approach. It uses inputs and execution results to compare behavioral differences among programs. There have been similar methods, such as the strict clustering approach in AlphaCode (Li et al., 2022) , which samples a set of program inputs and then clustering programs with identical outputs into the same group. The final program is then selected from the largest cluster.However, the idea of grouping programs by the 'identicalness' of outputs is not without fallacies, since programs rarely specialize in solving one single irreducible problem -they deal with a variety of inputs, conditions and mysterious cases. The result of this, where different solutions could have many common behaviors and some distinct behaviors, is referred to as the term 'special-case similarity' in the FrAngel paper (Shi et al., 2019) . We consider a correct program solution which has multiple 'special-case similar' programs that are partially correct in different ways, for example:• One program behaving correctly on the general case (almost all) but missed a few edge cases• Another program got one edge case correct but didn't manage to deal with the general case• Yet another program got all edge cases correct but crashed on the general case• A buggy program that behaves correctly on all available test cases but none of these tests trigger the bug (literally test coverage problem)• And many programs that turn out to be frenzy mixtures of all the above If we had a pool of programs that contained the fully-correct program and an assortment of other programs that respected certain cases of the problem as aforementioned, it'd be obvious that the fullycorrect would be decently 'special-case similar' to the rest of the programs, for their similar behavior on inputs. These execution outputs are programmatically obtained and automatically compared against each other without any human intervention or LLM calling required, the process of which sits at the core of our functional consensus algorithm.Therefore, with functional consensus, where the solutions with common behaviors are promoted, we could intuitively expect the result to be a higher likelihood of a fully-correct program. Provided below is a hypothetical example demonstrating why functional consensus prevails:Example Consider the problem of finding all square roots in the complex domain of a non-zero real number (stored in float32).To get the answer right for all inputs, the function must consider 2 cases: A) non-zero numbers have 2 square roots; B) square roots of negative numbers are imaginary. 10 candidate functions are sampled as below:• 5 results (a 1 , a 2 , a 3 , a 4 , a 5 ) only considered case A and got just positive inputs right. For negative numbers, they literally gave up and crashed.• 3 results (b 6 , b 7 , b 8 ) remembered to consider case B, gave 2 imaginary results for negative numbers, but forgot to do the same for positive numbers, returning only 1 square root therein.• Only 2 results (c 9 , c 10 ) considered all cases and returned correct results for all inputs.If we pick the program through 'clustering', the final result would be one of the 5 results (a 1 , a 2 , . . . , a 5 ) that only considered case A, which is evidently not the correct solution. But with functional consensus, the final result is vastly different, since we consider the similarity between the functions based on their behavior on different inputs. Without loss of generality, suppose that there are 2 test inputs 4.0, -9.0, one for each of the 2 cases. We calculate the similarity as follows:• Programs a i got only √ 4.0 = [2.0, -2.0] right so each program here are similar with programs (a 1 , a 2 , a 3 , a 4 , a 5 , c 9 , c 10 ), scoring 7 points.• Since b j only went well with √ -9.0 = [3.0i, -3.0i], programs here only score 5 points for case B with the ones (b 6 , b 7 , b 8 , c 9 , c 10 ).• Each program in c k gets 7 points for √ 4.0 with (a 1 , a 2 , a 3 , a 4 , a 5 , c 9 , c 10 ), and gets 5 points for √ -9.0 with (b 6 , b 7 , b 8 , c 9 , c 10 ). Totals to 12 points.The final result apparently leaned towards c k as the correct solution, even if their outputs as a whole weren't even half as much as a i is. Through this example, we illustrate that functional consensus has the potential to identify the correct samples even at their minority, outperforming other methods such as self-consistency or clustering.Token Usage We provide token usage results in Table 9 for FUNCODER and baseline methods on the HumanEval dataset with the GPT-3.5 model, whereas usage results on other datasets are provided in Table 10 . We report the average token usage per problem. The token usage is computed through the sum of prompt tokens and completion tokens returned by OpenAI API chat completion call6 . For LDB, we report their token usage in the original paper (Zhong et al., 2024) .Table 9 : Token usage for different settings of FUNCODER and baseline methods on HumanEval, all evaluated on GPT-3.5-turbo. The LDB results are reported in the original paper. The main setting for LDB and FUNCODER is bolded. Full Results for Code Generation We provide results for all conducted experiments on code generation benchmarks in Table 11 . Our method consistently improves the baseline on community models by averaging 11% on MBPP and 150% on xCodeEval. It is worth noting that small models have a tendency to have low pass rates on competition problems, leading to a relatively higher randomness, therefore we run 3 experiments and report the median result.Full Results for MATH The MATH dataset divides the problems into five levels of difficulty.The difficulty distribution of our test set can be found in Table 7 . We report the average accuracy of FUNCODER and other methods for each math subject in Table 12 and results for each level in Table 13 . The results of Cumulative Reasoning are obtained from the original paper (Zhang et al., 2024) . Experiment results demonstrate that our method consistently enhances the model's reasoning ability across all levels of MATH. We provide example solutions for the baseline and FUNCODER on code generation and mathematical reasoning. All results are generated with GPT-3.5.B The only line contains four positive integers cnt1 , cnt2 , x , y (1 <= cnt1 , cnt2 <109; cnt1 + cnt2 <=109; 2 <=x <y <=3*104) -the numbers that are described in the statement . It is guaranteed that numbers x , y are prime .Print a single integer -the answer to the problem . ## Sample Input 1 ``3 1 2 3 ``# # Sample Output 1 ``5 ``# # Sample Input 2 ``1 3 2 3 ``# # SampleWe can solve for $a$ by multiplying both sides of the congruence by the modular inverse of $27$ modulo $40$ . Since $27$ and $40$ are relatively prime , we know that $27$ has a modular inverse modulo $40$ . We can find this inverse using the Euclidean algorithm : \ begin { align *} \ text { gcd }(40 ,27) &= \ text { gcd }(27 ,13) &= \ text { gcd }(13 ,1) &= 1. \ end { align *} Therefore , the modular inverse of $27$ modulo $40$ exists . We can find it using the Euclidean algorithm backwards : \ begin { align *} 1 &= 13 -3 \ cdot 4 &= 13 -3(40 -27) &= 4 \ cdot 27 -3 \ cdot 40. \ end { align *} Thus , the modular inverse of $27$ modulo $40$ is $4$ . Multiplying both sides of the congruence $27a \ equiv 17 \ pmod {40} $ by $4$ gives $108a \ equiv 68 \ pmod {40} $ . Simplifying the left -hand side gives $8a \ equiv 28 \ pmod {40} $ . Dividing both sides by $4$ gives $2a \ equiv 7 \ pmod {10} $ . The smallest positive integer $a$ satisfying this congruence is $a =9 $ , and the second -smallest is $a =19 $ . Therefore , the sum of the smallest and second -smallest positive integers $a$ satisfying the congruence $27a \ equiv 17 \ pmod {40} $ is $9 +19=\ boxed {28} $ . """ get common element in two list $a$ and $b$ """ """ Return the sum of all common prime factors of $a$ and $b$ """ raise NotImplementedError () ``L et ' s think step by step and implement the following method sum_common_factors `using existing functions to solve : " Return the sum of all common prime factors of $a$ and $b$ " < Assistant >: You are a mathematical teacher , your task is to :-Judge whether the prediction is matching the answer -Output " Judge : Correct ." or " Judge : Wrong ." , please do not output redundant words -Numerical errors should be ignored ( $1$ is equal to $0 .99999998 $ ) -Some answer might be represent in latex format , and some might be float number , this should be consider as correct ( $ \ frac {1}{2} $ is equal to $0 .5 $ , $3$ $ \ sqrt {66} $ is equal to $24 .37211 $ )-Unit in answer should be ignored , and should be consider as correct ( $13 cm ^2 $ is equal to $13 .0 $ , $ \ $13$ is equal to $13$ )Now , the answer and prediction is : Answer : { ground_truth } Prediction : { model_output } Please output " Judge : Correct ." if two answers are literally the same , or " Judge : Wrong ." for not same , please do not output redundant words .• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Yes, please refer to the Broader Impacts paragraph in Discussion ( §5). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).GitHub: noahshinn/reflexionOriginal MBPP prompt: https://github.com/google-research/google-research/tree/master/mbppmath_equivalence: https://github.com/hendrycks/math/blob/main/modeling/math_equivalence.pyhttps://platform.openai.com/docs/guides/text-generation/managing-tokens 


Decision: This paper introduces FunCoder, an elegant divide-and-conquer strategy for code generation which uses an LLM to recursively decompose a complex programming task into a tree of functions calling helper functions. Because the units of decomposition are individual code functions, FunCoder also uses the notion of functional consensus to select good helper function implementations before completing the implementation of the parent function. These techniques lead to significant improvements in multiple code generation and math reasoning benchmarks.

I recommend to **accept** this paper because, in my opinion, this is a great paper with many strengths:
* The topic of LLM-based code generation for complex tasks is clearly important.
* Reviewers agreed that FunCoder is "conceptually very clean", "novel and beautiful", and "well explained and motivated".
* Reviewers also praised the "extensive experiments" and their "striking" results: "Besides outperforming SOTA baselines, ... it is impressive how FunCoder significantly improve the small LLMs' performance."
* Beyond the impressive end-to-end results, the authors dive deeper to better understand the method and explain its benefits compared to prior approaches. In this way, the paper "justif[ies] different design choices" and "provides a number of interesting insights beyond the base experimental results".
* The paper's writing is "commendably clear". In fact, I think a reader can understand the main divide-and-conquer idea from only Figure 1 and Figure 2.
* The authors provided detailed rebuttals containing clarifications, further analyses, and new experimental results. These rebuttals strengthened the paper's conclusions and improved the reviewers' opinions of the work.
* After discussions, all reviewers are supportive of accepting this paper.

Most weaknesses raised by reviewers were addressed by the rebuttals, but a minor weakness remains: the method is not evaluated on realistic complex programming tasks, despite being designed for complex tasks. A full experiment is a lot to ask for given the paper's broad scope already, but I think it would be very enlightening to include a small case study on 1-3 carefully-chosen realistic complex tasks (chosen based on the needs/strengths of FunCoder and simplifying assumptions like being contained in one file, not cherrypicked post-hoc based on results).

I also think this paper should be highlighted (more than a poster) because its ideas are intuitive, elegant, and broadly applicable. Decomposition in program synthesis is not a new subject, but the divide-and-conquer strategy proposed in this paper is a novel and conceptually simple approach that seems generally applicable to more languages and programming domains than explored by the paper. The concept of functional consensus is also a refreshing alternative to clustering of function behavior (majority voting) or self-testing (like CodeT). I anticipate that the core ideas in this paper could be easily communicated to and appreciated by a broader audience without requiring much prerequisite knowledge, another reason for this paper being well-suited for an oral presentation.

---

I also want to share some thoughts with the authors, in case it helps improve a future version of the paper. Your rebuttal includes an example illustrating why functional consensus works. Here is an additional explanation which may be more intuitive.

Functional consensus reminds me of "special-case similarity" from the FrAngel paper (Section 4.1 of https://arxiv.org/pdf/1811.05175). In short, this is a common property where a fully-correct program is similar to other (simpler) programs that only solve a subset of the desired functionality (a "special case"). The FrAngel paper found success in program synthesis search by remembering the simplest program generated so far which solves each different subset of tests, and biasing generation of future programs toward the set of remembered programs. This works if enough remembered programs contain sufficient similarity to a fully-correct solution to increase the chances of progress.

Bringing this back to functional consensus, a possible explanation for its effectiveness is as follows. Consider a correct solution program which has multiple "special-case programs" which are partially correct in different ways, for example:

* a program that behaves correctly in the general case but misses an edge case
* a program that handles the edge case correctly but messes up the general case
* a buggy program that behaves correctly for all tests that don't trigger the bug
* a program which replaces an if/else block with just the body of the else, which still behaves correctly for the subset of tests where the condition evaluates to false
* a program with a mix of the above properties

If we had a pool of programs containing the fully-correct program along with multiple special-case programs such as those listed above, then we would expect:

* the fully-correct program would be similar (in behavior on tests) to every other special-case program
* each special-case program would be similar to other special-case programs only to the extent that the special cases themselves overlap, which is less than the amount of overlap with the fully-correct program

So, intuitively we would expect that the fully-correct program is selected by functional consensus.

It may also be interesting to weight each test by how much it's able to distinguish between different sampled programs, considering the other tests as well. For example, the first test that exercises some edge case is really helpful in identifying programs that handle that edge case correctly. But further tests for the same edge case may not provide any additional "distinguishing power". Should an edge case have more impact on functional similarity simply because it has more tests? A correct program must handle the edge case correctly, no matter how many tests illustrate that edge case. But, perhaps failing a rare edge case is more acceptable than failing a common edge case. The right decision might depend on how exactly the tests are generated.

Reviews: review: paper_summary: paper_summary: The author applies divide-and-conquer methods to code generation problems with Large Language Models (LLMs). A problem is divided into subproblems recursively; that is, the function that solves the problem is generated in a top-down manner. Given the parent function, the LLM is prompted to implement it using child functions, which are yet to be implemented. Then, it recursively implements the child functions. There are two key components that make this method work well:

1. A two-pass generation approach: When generating a function f, the first pass generates the function/plans without child functions being implemented yet. The second pass occurs when the children functions are implemented, conditioning on the children functions and regenerating the parent functions again. This is to overcome potential problems that may arise when parent functions are generated before child functions are concretely implemented.
2. Consensus via multiple sampling: Each time a function is regenerated in the second pass, multiple programs are sampled, and a consensus of the samples is used to generate the final program. The consensus is determined by selecting the program that exhibits the most similar input-output behavior to other functions.

Experimental results show it improves performance effectively on HumanEval, MBPP, xCodeEval, and MATH benchmarks, and remarkable 94.5% results on HumanEval with GPT4.
strength_weakness: strength_weakness: * The idea of decomposing the problem into subproblems and solving them recursively with an LLM is not entirely new.
* The consensus method, which aims to select top programs from a set of samples using similarity, is different but similar to the AlphaCode approach. It would be interesting to see a comparison of selecting the top programs using majority voting on the input/output as in AlphaCode instead of calculating the similarity.
questions: questions: * On average, how many decomposition levels are used when solving the code generation tasks?
* Are the Standard and CodeT prompts used in the experiments the ones shown in Appendix C.1? Is this type of decomposition prompting also better for the Standard and CodeT methods?
* How does the consensus method compare to other self-consistency or AlphaCode-like majority clustering methods?
* 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 else where?
limitations: limitations: Yes, one limitation that it is not suitable for software engineering/ open coding problems is discussed.
paper_summary: paper_summary: The paper presents FuncCoder, a novel coding framework designed to enhance code generation by incorporating a divide-and-conquer strategy with functional consensus. FuncCoder addresses the limitations of existing methods that struggle with complex programming tasks by recursively breaking down problems into smaller sub-functions, which are then hierarchically organized and recomposed to achieve more complex goals. The functional consensus mechanism mitigates error propagation by selecting functions that exhibit similar behaviors. Experimental results show that FuncCoder outperforms state-of-the-art methods, such as Parcel and Reflexion, on various benchmarks, including HumanEval, MBPP, and xCodeEval, and demonstrates its effectiveness across different language models like GPT-3.5, GPT-4, as well as smaller models such as StableCode3b. The framework's ability to dynamically decompose and compose functions enables superior performance in handling complex coding requirements and mathematical reasoning tasks.
strength_weakness: strength_weakness: While FunCoder demonstrates impressive performance in handling well-defined programming challenges, there is a practical concern regarding the token length of the trajectory. 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. As reported by Table-3, the average token length is ~5.5k, and I am curious about the median and the maximum tokens required to solve HumanEval problem.

This becomes concerning when dealing with more intricate and interconnected coding requirements. As each layer of decomposition adds to the overall length, the token usage can escalate rapidly, leading to inefficiencies and increased computational costs. The empirical data shows that while FunCoder performs well on self-contained coding benchmarks, the token length could become a limiting factor for more complex problems, potentially offsetting the advantages gained through the divide-and-conquer approach. This exponential growth in token length necessitates careful consideration and optimization to ensure that FunCoder remains scalable and efficient for a broader range of coding tasks.
questions: questions: + Why do the authors report different methods for GPT-3.5 and GPT-4 in Table-1? Aren't these approaches generalizable to all GPT-based models through API? I would suggest the authors to add back missing baselines for both models. A similar question presents in Table-4 
+ In Table-4, why do the authors choose CoT or self-refine as the main baseline while no more comparing with Parcel?
+ Why do the authors choose not to disclose their code during the submission phase?
limitations: limitations: The paper discusses the limitation in Section 5.
paper_summary: paper_summary: This paper presents Divide-and-Conquer Meets Consensus -- a prompting scheme for generating complex functional code. In contrast to planning ahead of time, the proposed technique performs planning in smaller steps by decomposing a coding task into smaller sub-tasks recursively and solving them when they are simple enough. The evaluation shows that the technique can significantly outperform prior arts and works for both proprietary models and smaller open models.
strength_weakness: strength_weakness: 1. There is a flaw in the design of functionality similarity. Authors claim in L104 that they sample inputs from the input domain of the function, namely D(f). First, it is non-trivial to infer D(f). While simple type analysis is applicable, oftentimes the pre-conditions of the function can go beyond type constraints. For example, the pre-condition asserts the input sequence is sorted when doing code generation for binary search. Second, it is challenging to accurately infer such pre-conditions, and inputs violating such pre-conditions often manifest undefined behaviors of function candidates, falsifying functionality-similarly candidates. For example, in the EvalPlus paper, these conditions are manually specified to ensure the soundness of test input generation. In summary, the equivalence-modulo-inputs idea requires knowing the accurate input domain and designing corresponding input samplers, which are oversimplified in this paper.
2. Back to the high-level framework, it is unclear why functionality consensus would work in the first place. 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.
3. The diversity of studied models is a bit limited. It would be helpful to run Divide-Conquer on more open models such as StarCoder2.

Minor suggestions:
1. L97 "A program specifies its functionality (or behavior) through the control flow...": This is not accurate as control flow is just a partial representation of code semantics. For example, `a + b` and `a - b` share the same control flow (i.e., no control flow) but stand for completely different semantics.
questions: questions: 1. Can you exemplify "cascading errors" in Section 2.2? Can you also better explain why sampling multiple functions helps mitigate such errors?
2. The technique is motivated to solve complicated coding tasks. I wonder if the selection of benchmarks can really exercise the core part of the technique, i.e., resolving complex code generation tasks.
3. When computing the token usage, did you include tokens of unused samples when computing "functionality similarity"? Can you also provide more statistics such as the medium token consumption in case the average number is biased by simple tasks? Overall the presented token consumption in Table 3 is much smaller than I expected according to the large prompts shown in the Appendix (and these will be called multiple times).
4. How's the token usage compared to other baselines?
5. Is the technique single-turn or multi-turn when being implemented for evaluation?
limitations: limitations: Social impact wise this paper is fine. For technical limitations, they are reflected in the weaknesses section.
paper_summary: paper_summary: The paper proposes FunCoder, a code generation framework incorporating the divide-and-conquer strategy with functional consensus. FunCoder recursively branches off sub-functions as smaller goals during code generation, represented by a tree hierarchy. These sub-functions are then composited to attain more complex objectives. Additionally, they use a consensus formed by identifying similarities in program behavior, mitigating error propagation. FunCoder shows great perormance compared to baselines by +9.8% on average in HumanEval, MBPP, xCodeEval and MATH with GPT-3.5 and GPT-4.
strength_weakness: strength_weakness: - some important details are missing
- lack analysis for cost

The paper is commendably clear and the results of the experiments are striking. However, I find that 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. It would be greatly beneficial if the authors could expand on this strategy. For instance, how does the model determine which functions require further division or are enough simplistic? Are there specific experiments that illustrate this process? Additionally, it would be insightful to know whether the model is designed to recognize dependencies among the subdivided functions and how it integrates these components effectively.

Regarding the implementation costs, the approach involves segmenting the program generation into multiple stages using a depth-first search for each sub-program. This intricate process prompts a question about the overall efficiency and resource utilization. I would appreciate if the authors could provide more detailed information on the costs associated with these procedures.
questions: questions: - How the model decide the functions to be further divided or too simple? Any experiment?
- How the conquer works? Does the model aware of the dependency among those sub functions?
- What is the cost of each part?
limitations: limitations: Some limitations have been discussed but it would be better to discuss more on the cost of the FUNCODER and the limitation of divide-and-conquer for hard problems.

Comments: title: Thanks for the reply!
comment: We thank you for your response and again apologize for causing confusion regarding our code.

To put it honestly, we were quite busy with other things on our hands, so didn't have enough time to polish our code. But we reassure you that the method **and the implementation** are still straightforward, and that replicating this work from scratch needn't two months time (far less than that).

As is also discussed in the *Limitations and Social Impact* section that directly running code generated by LLMs can be risky. Although our current version of Code Interpreter Sandbox works and could prevent the machine from many known attacks, we are actively looking for more promising means of protection, lest our code causes problems when it goes public.

Comments and suggestions on how the code should be open-sourced are also super welcomed.
Thanks for the authors response. It mostly makes sense, though I have concerns why the minimum working code for replication requires **months** to release while the authors acknowledge the methods are relatively straightforward. I would like to see some brief explanations of what are the most time-consuming part for code release and the main difficulty of implementing the current agentic system.
We sincerely thank you for the follow-up discussion and the rating update.

For accuracy on simple sub-problems, we hypothesize that well-trained LLMs can solve them well (compared to complex sub-problems). But since this needs human labeling for all LLM outputs, which is beyond our available man-power, we might not include statistics for this issue. With that said, we hope that future research may look into this and investigate further.

While there may be a slight possibility of losing accuracy forcing the LLM to decompose a simple problem (when the LLM is not trained to decompose such problems), or vice versa, conducting experiments that enforce program depth during generation is actually a very interesting idea. Such experiments may provide more insights to how complexity correlates with functional decomposition, and may lead to more promising ways to reliable code generation. So we welcome future work that proposes new, faithful methods to control this function decomposition depth.
We sincerely thank you for your response and your rating update.

We fully agree with you that weakness 1 & 2 should be at least discussed in the limitations section, and we will add them in our next revision. We look forward to future research that investigates these weaknesses and, better yet, be accompanied with theoretical analysis.
Overall I am satisfied with the authors' responses. Weaknesses 3 and 4 should be easily addressable and I look forward to seeing more models being compared. While weaknesses 1&2 are not resolved due to their challenges, I suggest at least discussing them as limitations of the technique in the revision and calling for further research. Specifically, I feel the concern of W1 is a bit outstanding. Probably the only way to address it right now is to add program contracts via human experts (for example, contracts are added manually in the EvalPlus paper for test-case reliability) or LLMs; some weak pre-condition is also better than nothing even if they cannot be strictly verified.

I'm happy to increase by rating to 6.
Thank you for your detailed response.
I am generally satisfied with the clarifications provided; however, I have reservations regarding point 3. 
Traditional LLMs just generate the whole code.
Your techniques are generated in a divide-conquer way, which means the LLM needs to understand the code dependency and generate multiple times for each sub-problem considering the context.
The sub-problems may be easier than the origin problems, which means the overall success rate (94.5) and the success rate for sub-problems (97.2) would be different.
More complex problems require higher accuracy on sub-problems (~100%).
Does that mean that in your experiment, for simple sub-problems, the LLM can reach almost 100% accuracy?

Additional experiments could be highly beneficial to solidify the claims of your technique’s effectiveness. Specifically, experiments that vary the depth of sub-problem generation (e.g., restricting the LLM to generate a depth of 2 or 3 programs) could provide valuable insights into how the structure and depth of problem decomposition affect the overall pass rate.

I've adjusted my score to reflect my appreciation of the responses you have provided.
We thank you again for taking your time to read our responses and provide suggestions.

> **1. The analysis of token cost appears to assume an ideal scenario where no failures occur.**

Indeed, in the analysis of general response, we simplified the situations and ignored the the situations where the LLMs make a mistake. However, in token cost results (Table 3, 11 and in our response) we have **always included** token usage for retries to ensure fair comparison, and we argue that this situation may be trivial to consider.

Failures that cause retries can rarely happen in FunCoder -- they happen if and only if no code can be extracted from the responses' Markdown blocks, or that the code was syntactically incorrect. We provide additional statistic results in the table below, which shows a relatively low failure rate even in complex questions (MATH or xCodeEval).

| Dataset | Pass@1 | failed to parse / all LLM calls |
|---|---|---|
| HumanEval | 85.4 | 0.10% |
| MBPP | 78.5 | 0.31% |
| xCodeEval | 31.4 | 1.68% |
| MATH | 54.0 | 2.10% |

> **2. We would like to see the analysis results of Table 1 or 2 (compared to the SOTA).**

We report token consumption data for some of the fields in Table 1 and Table 4, regarding GPT-3.5 and SOTA methods, in the table below. Some of the cells are missing data since some methods were not open-source and did not report detailed token usage.

| Dataset | Method | Pass@1 | min tks | max tks | mean tks | med tks |
|---|---|---|---|---|---|---|
| HumanEval | Standard | 68.3 | 648 | 1477 | 886.7 | 861 |
| | CodeT | 81.1 | 2298 | 9645 | 4479.1 | 4166 |
| | Reflexion | 69.5 | 416 | 4906 | 1416.1 | 754 |
| | LDB (Reported prev SOTA) | 82.9 | - | - | ~23000 | - |
| | FUNCODER | 85.4 | 3015 | 13850 | 5402.0 | 5166 |
| xCodeEval | Standard | 20.2 | 1051 | 3343 | 1599.5 | 1530 |
| | CodeT (prev SOTA) | 23.2 | 2264 | 9245 | 3937.4 | 3733 |
| | Reflexion | 20.6 | 2977 | 1003222 | 401767.3 | 328591 |
| | FUNCODER | 31.4 | 4883 | 53225 | 10559.7 | 8927 |
| MATH | Standard | 62.2 | 551 | 5867 | 953.0 | 835 |
| | FUNCODER | 76.8 | 2622 | 30139 | 7075.5 | 5666.5 |

> **3. Then, your success rate to derive b->B and c->C should be increased to the square root of 0.945, which means 0.972. When the program becomes much more complex, the requirement of success rate for each divided subprogram is further increased.**

**Accumulated errors in FunCoder also occur in Standard**, where generating all functions (ABC) all at once would have a higher error rate than generating one at a time (A, B, C).

Note that this metaphor may not be exact since 94.5% acc is an average of all problems, where different problems are decomposed into different depths. However, we follow this metaphor and continue to show why FunCoder works better than other methods. Here success rate of *Standard* on a single function is $\sqrt{82.9}=91.0$. On a harder dataset where problems are decomposed to 10 levels of functions on average, *Standard*'s overall accuracy will be $91.0^{10}=38.9$, while FunCoder still keeps $97.2^{10}=79.3$.

Results on xCodeEval dataset shows that FunCoder gets greater improvements on harder problems compared to simple problems. But of course, the analysis we just made was based on a simple assumption and does not reflect reality.

> **4. I think there should be some design and cost to increase the performance, even if the divided programs are simpler than the original ones.**

We designed FunCoder under the consideration of complex problem performance, and have made visible progress. Particularly, our method:

 1. **Divide** dynamically decomposes problems into simpler subproblems, making them easier to solve. The Divide stage always considers just one layer of problem at a time, thus can keep the model in context, reducing ambiguity and complexity caused by extra-long code. For instance, the problem A-B-C-D requires all these functions to be in context in *Standard*, while ours only need 2 for each of the 4 calls.
 2. **Conquer** enables bottom-up generation through re-composing simple functions into a complex solution to a complex problem. This mitigates the issue where Divide cannot see the subfunctions while generating parent functions, making function dependencies more robust. (Note that LLMs are autoregressive models, so while *Standard* generates ABC, when A is being generated B,C aren't there yet. This could cause *Standard* to mis-invoke B or C from A in this implementation.)
 3. **Functional consensus** verifies every function starting from the leaves. Through sampling and voting, incidental errors and cascading errors may be reduced and thus the accuracy could be improved. Before our method, self-test was widely used for verifying programs, and now FunCoder manages to achieve higher performance with the same level of token complexity.

We further note that Divide, Conquer and Consensus may be used together, and that using them in conjunction will further raise the accuracy on complex problems.
Thank you for the detailed rebuttal and the efforts made to clarify the cost analysis in your paper. However, I still have some concerns regarding the logic and assumptions underlying this analysis.

The analysis of token cost appears to assume an ideal scenario where no failures occur. Additionally, the new data presented in the rebuttal seems to mirror Table 3 of the paper(ablation study). We would like to see the analysis results of Table 1 or 2(compared to the SOTA).

In a naive program, the standard is a -> BC, and yours is A, [B, C] (follow your notations). 
We assume the divide and conquer is perfectly gained, and the pass rate is just the success rate.
The best performance of FUNCODER is 94.5. 
Then, your success rate to derive b->B and c->C should be increased to the square root of 0.945, which means 0.972.

When the program becomes much more complex, the requirement of success rate for each divided subprogram is further increased.

I think there should be some design and cost to increase the performance, even if the divided programs are simpler than the original ones.
However, from the rebuttal, it seems most parts depend on the LLM for program generation and divide-conquer, which means the error will increase when the program becomes more complex.

I am willing to consider increasing my score if we could address these questions.