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 2024 oral (2024)
Keywords: programming
language model
code generation
reasoning
Primary area: natural_language_processing

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.

Divide-and-Conquee Meets Consensus: Unleashing the Power of Functions in Code Generation
Jingchang Chen'
Hongxuan Tang"
Zheng Chu
Harbin Institute of Technology jechendir hitt edu.
Harbin Institute of Technology
Harbin Institute of Technology zchu@ir hit. edu.
jeffswttouttlokk.ccm
Qianglong Chen
Zekun Wang
Zhejiang University chenqianglong. ai ai@gmail.com
Harbin Institute of Technology zkwangiir hit. edu, cn
Ming Liu
Bing Qin Harbin Institute of Technology qbin@ir .hit. edu. thit.ddu.eee.e cn
Harbin Institute Technology ml iutir. hit. edu. cn
Abstract
Despite recent progress made by large language models in code generation, they still struggle with programs that meet complex requirements. Recent work uti- lizes 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 accomplish self- eel--improvement. To this end, we propose FUNCODER, a code generation frame- work incorporating the divide-and-conquer strategy with functional consensus. Specifically, FUNCODER recursively branches off sub-functions smaller goals during code generation, represented by tree hierarchy. These sub-functions are then composited to attain more complex objectives. Additionally, designate functions via a consensus formed by identifying similarities program behavior, mitigating error propagation. FUNCODER outperforms state-of-the-a methods by +9.8% on average HumanEval, MBPP, xCodeEval and MATH with GPT-3.5 and GPT-4. Moreover, method demonstrates superiority smaller models: With FUNCODER, StableCodeg, surpasses GPT-3.5 by +18.6% 8.6% and achieves 97.7% GPT-4's performance 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.
Introduction
Over the past few years, large language models have been observed to attain significant advancements coding capabilities (OpenAl 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
al.) 2024). Although LLMs can proficiently generate simple code snippets, they suffer from decline in performance as code requirements become complicated.
Numerous efforts have been made to tackle this complexity. The two-stage methods (Tiang al. 2023 Zelikman et al. 2023) employ the plan-and-solyy strategy, which first generates a draft outline
'Equal contribution.
Conresponding Authors: Ming Liu, Qianglong Chen.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

FUNCODER (16)
Sampled Implementations
Functional Consensus
('x)
f(o)=
divide
conquer
fi
:
Se
FUNCODER
g
g" (O)
(v)
FUNCODER
h(2)
h' (2)
Kyn
ht (x)
Possible Inputs
Legends
Example
DMdeld, e) Conquer(D. F)
Divide(c) Conquar(C)
Divide(h)
Conquer(R)
Conquer(4)
Problem
Dividela)
('x)
Inrtallymplementte
((++)
Reached Consensus
Figure A flowgraph illustrates FUNCODER. FUNCODER branches off new functions to have sub-goals tackled iteratively (left), re-composites sub-functions, and selects the best using functional consensus (right). Bottom-right figure shows how FUNCODER writes functions at hierarchy-level.
for the complex task and uses it as guidance for implementing the code in the second stage. Multi- agent development frameworks (Hong et al. [2024] Qian al., 2023) mimic real-worle software development workflows, assign different roles to LLMs and collaborate to solve complex goal. Self-impprovement (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 sub- optimal decomposition. (2) Multi-agent collaboration frameworks are cumbersome and rely heavily on LLM capabilities, making them difficult to generalize smaller open-source models. (3) Code refinement through self-tests depends on the correctness of generated unit-tests. Our preliminary study (33.13) 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-and- conquer 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 nottom-up to achieve increasingly complicated objectives. By dividing-and and-cunug 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.
We conduct extensive experiments on code generation benchmarks (Chen et al.) 1021 Austin iet al., [222]] Khan et al. (023) with GPT-3.5 (Ouyang et al., 2022) and GPT-4 (OpenAl 2023).
outperforming -ta art methods by +9.8% on average. Experiments are further carred out on the mathematical competition benchmark, MATH (Hendrycks et al. 2021b). achieving a 6.00 improvement with GPT-4, indicating that FUNCODER can also generalize to complex reasoning. Our method is observed to be equally effective on open-source models (Meta AI 2024 Mistral All 2024, Pinnaparaju et al. 2024 Rozière et al. 2023 Lozhkov et al., 2024), with an average gain over baseline of +31.5% on HumanEval and +47.77 7 on MATH. Additional analysis also shows the
advantage of both at athttps: /i thub. com/ comm//eeeeeme//nnoeerr
and functional consensus. Our code is made openly available

---

Algorithm FUNCODER procedure
(a) Planning- Decomposition
Require: Entry func, from {hront: dyooe }}
Create function...
Require: Large language model, LLM
Generate sequence
1: function FUNCODER((ar)
Cherk if then
2: -Divide-
Return... plan
code
3: Slur {fi} < EXTRACT(LLM((OU))
(b) Decompose Through Coding (ours)
4:
for fi E. {ffi) do
5:
b; is NOTIMPLEMENTED then
Writing function
6:
ft + +FUNCODER(f) & recursion end
def sum common factore(s, bjjt the factors" te (actors(a)
7:
3. Extract
to tree
8:
ADDCHILD(fann ff) end for
fb find factors(b) return commontia.
9:
10:
Conquer-
Introduce new functions
11: Feur + SAMPLE(LLM Jour: CHILD(feur))
det find foctoracc fintthooccr
int) list:
s*frotum factors
12:
Jeur f- FUNCONSENSUS) FFur)
NotimplemmeneeeErooo
13: return für
sum wtarm_ooommnt common list)
14:
end function
aruu of common elements""
15:
return FUNCODER(FoO)
> starts from root
raise NotlmnglemmeeeedErr00
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 solcly with code, achieving a more natural way of requirement decomposition.
2 FUNCODER: Divide-and-Conque Meets Consensus
2.1 Hlvide-and-Conquee for Iterative Programming
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 by with its body by. and is commonly accompanied by a documentation dy 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 decompose tasks into clearly defined sub-functions and then implement them recursively. making functions eligible for re-usage, taking advantage of the andee--edd-onquer 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 froe. We instruct the model to introduce new functions fi E CHILD(feu. that solve certain sub-goals while writing the current feur- To reduce the complexity involved in each generation, we only require the headers h,, and documentation d,, of new functions to be generated, while their implementations by, can be postponed. After completing the current function, the model starts to address those unimplemented sub-functions and complete by. into f. This process stops when the model deems functions too simple to be further divided, finally forming dependency tree 7 TREE CHroa()rrer)) The divide process is similar to 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-fire fepth-first search.
Conquer a process achieving complex objectives through aggregating smaller functions. We notice that child functions 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, misuse them at worst. FUNCODER deals with this issue by re- re-generating functions in inverse topological order on the dependency tree T starting from leaves, complex goals are handled by compositing solved children as f F fī }) f E CHILD(Jaur)
Divide and conquer naturally achieve both decomposition and composition during code generation. Unlike two-stage and agent-based methods, approach dynamically introduces new functions
3

---

along the process, making it less burdensome than producing 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.
2.2 Functionality Similarity as a Consensus
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.
1 1ff(x) 9(x) [D()
(((=) [X
sim JxED(F)
#E XEX(X~D(I)
The similarity becomes 1 if and only if two functions output consistent values for all inputs: Vo 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, approximate it by sampling subset of possible inputs X ~ D(f) with an LLM.
Consensus is reached by selecting the candidate holding maximal similarity with others after sampling multiple function implementations
(f()) for the same requirements.
FUNCONSENSUS(F) arg max
Σ
sim(f() f()
(2)
EF JujEFUfot
By 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-ster thorough verification from the most fundamental functions the way up to the whole program.
2.3 FUNCODER a Function Coder
We design FUNCODER procedure that takes problem in the form of function signature fxx and produces a final solution (x). as exemplified in Figure [ Given a problem f(x), FUNCODER partially implements the function f((x) referring to unimplemented sub-functions ( and h(2). These sub-functions are then fed into FUNCODER to be recursively coped with. We then sample k implementations f/a) (x) based on solved children (3) and h (z). Functional consensus is calculated by evaluating candidates possible inputs. The function sharing maximal behavioral similarity is combined with solved children to formulate the final solution.
3 Experiments
We conduct experiments on competition-level code generation and mathematical reasoning bench- marks with offt---f-the-rtt LLMs, which are covered in section |3.1 and $3.2 respectively. In addition to GPT models (Ouyang al.) 2022, OpenAl 2023). we also conduct experiments with community models like Llama3s, (Meta 2024). StableCodeg, (Pinnaparaju et al. 2024). and CadeLlaamaas (Rozière et al. 2023). We use the instruct variant these models and inference on single A100-80G under BF16 precision with vLLM (Kwon et al. 2023).

---

Table 1: Experiment results code generation benchmarks. We report Pass @ evaluate metric. Results from the original paper are underlined, and the best results are bold.
HumanEval
MBPP
XCodeEval
Model
Method
Pass@1
A
Pass@
At
Easy
Mid
Hard
Expert
All
Standard
68.3
72.0
44,4
15.2
4.6
0.0
20.2
CodeT
+1288
76.0
+4.0
50.6
8.0
0.0
23.2
GPT-3.5
Reflexion
69.5
+1.2
72.5
+0.5
44.4
17.0
5.7
0.0
20.6
LDB
82.9
+14.6
76.0
+4.00
FUNCODER
85.4
+17.1
78.5
+6.5
62.4
29.5
11.6
0.0
31.4
Standard
82.9
73.5
68.5
39.3
19.5
1.7
37.4
Parsel
85.0
+2.1
CodeT
90.9
+8.0
77.0
+3.5
76.4
51.8
21.8
3.4
44.0
GPT-4
Reflexion
91.0
+8.1
77.1
+3.6
71.3
41.1
19.5
2.5
38.6
MetaGPT
85.9
+3.0
FUNCODER
94.5
+11.6
79.5
+6.0
83.1
58.0
26.4
3.4
48.6
Standard
61.6
60.5
9.0
1.8
0.0
0.0
Llama3gs
CodeT
68.9
+7.3
61.5
+1.0
12.4
0.0
0.0
0.0
4.4
FUNCODER
79.7
+18.1
62.5
+2.0
22.0
0.9
0.0
0.0
8.0
Standard
61.0
51.5
7.3
0.9
0.0
0.0
2.8
StablcCodegh
CodeT
75.0
+14.0
57.5
+6.0
11.2
1.8
0.0
0.0
4.6
FUNCODER
81.0
+20.0
63.5
+12.0
13.5
4.5
1.1
0.0
6.2
Standard
43.9
53.5
2.3
0.0
0.0
0.8
CodeLlamagus
CodcT
55,5
+11.6
56.5
+3.0
10.1
0.0
0.0
0.0
3.6
FUNCODER
66.5
+22.6
58.5
+5.0
10.2
0.0
0.0
0.0
3.6
3.1
Code Generation
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.
3.1.1 Experiment Setup
Benchmarks We adopt the full test set (164 problems) for HumanEval, and sample 200 for MBPP and 500 for xCodeEvvll, respectively. Following EbTech (024), split the xCodeBval into subsets based on problem difficulty: Easy (S 1200), Mid (1200-1599), Hard (1600-1999) and Expert (2 2000). The evaluation metric for code generation is Pass@ unless specified.
Baselines We compare FUNCODER with standard prompting (Brown et al.] 2020). two-stage decomposition method Parsel (Zelikman al. 2023), self-testing method CodeT CChen et al. 2023a), self-improvemmen methods Reflexion and LDB (Shinn et al. 2023] Zhong et al. 2024). and mulu- agent developing framework MetaGPT (Hong et al.) 2024). We implement Standard prompting with a 1-shot demonstration. CodeT samples solutions with standard prompting and evaluates them on model-generated tests. The results for Reflexion 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 for code generation tasks. For further implementation details, please refer to Appendix A.I
3.1.2 Results
Table I shows the code generation performance on advanced proprietary models, GPT-3.5 (Ouyang al. 2022) and GPT-4 (OpenAT 2023). For basic programming questions, HumanEval and MBPP, FUNCODER surpass previous SOTA methods by +3.3% in Pass@ and reduce the error rate by 18.6%. Furthermore, FUNCODER demonstrates a substantial improvement on competition-leww problems, outperforming others by 10.4% in GPT-4 and 35.3% with GPT-3.5, We observe that FUNCODER can
5

---

Preliminary Study Self-testing
(b) Effectiveness of Ranking Strategy
final 43.9%
44.5%
M4
final falled
4.1%
19.5%
85
program wrong
Strategy
woong
25,0%
16.5%
Self-Test Resalt
passed
consensus
self-test
75
both incorrec!
14.0%
14,055
failed
random
20
10
40
50
10
GPT-335
StubleCodess
Selected Programs
Figure 3: (a) Preliminary study on self-testing, the programs are evaluated using unit-tests generated by LLMs. (b) The effectiveness of different ranking strategies. We compute the Pass over top-k programs ranked by functional consensus, self-test, and random on 11 candidates. (higher is better)
enhance LLM's capability of solving more complex programming tasks, with average accuracy improvement of 82.3% over the baseline on the Mid and Hard subsets of xCodeEval. Expert level programs, however, still remain colossal challenge for even the most cutting-edge LLMs.
Evaluation also performed over community LLMs, Llama3 (Meta AI, 2024), StableCode (Pin- naparaju et al. 2024) and CodeLlama (Rozière et al. 2023) with results in Table [ FUNCODER consistently boosts the performance of smaller models in code generation, demonstrating notable improvements compared to standard prompting on HumanEval, which gained +29.4% .4% Llama3, +32.8% on StableCode, and even +51.5% on CodeLlama, outperforming that from the previous best method Code'T. We also supplement results GPT-4o mini, Codestral and StarCoder2 in Table [1 Experiment results demonstrate that our method archives state-of-the ofte-offthheart performance on various models, ranging from basic programming to competition contests.
3.1.3 Analysis
FUnCODER Democratize to Smaller LLMs Limited by the LLM capabilities, the application self- improvement multi-agent methods smaller models is without case. By kceping decomposition and composition within the code generation process, our approach exhibits better generalization. As shown in Table with FUNCODER, StableCodeg, 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 with further details in Appendix [A.5 We first verify whether model-generated programs can also pass model-generatee passes self-tests, most from GPT-3.5 would also work on system tests, as much as 19.5%/o64% A 30.5% programs from StableCode rejected, indicating that smaller models like StableCode may not effectively self-test and detect program errors on its own. (b) In the event failed self-tests, large portion of failures attributed to issues in self-tests instead of the programs, and StableCode. These phenomena indicate that self-testing methods have limitations in generating correct and reliable unit tests. As result, we design functional consensus to not require any assertion, but perform mutual verification between solutions instead, as opposed to self-testing.
self-tests: (a) If a program
both GPT-3.5
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 measured via Pass @k,, @, i.c. if any of the top-k ranked programs pass the system test. Figure 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 FUNCODER, we carry out an ablation study with different settings. Studies that replace consensus with self-testing, or with AlphaCode-like (Li et al. (022) clustering, are also included. The ablation constructed on HumanEval with GPT-3.5, as shown Table [ Note that to generate every program FUNCODER costs only OkkN) tokens, where & is the number of sampled candidates,

---

Table 2: Ablation study of FUNCODER HumanEval with GPT-3.5. The setting in main experiment is highlighted in bold. Tokens are calculated as the sum of prompts and completions.
Setting
Standard Avg. Tokens
Divide
Conquer
Ranking
Pass@1
x
X
X
68.3
886.7
One-pass
X
72.6 (+4.3)
1233.7
Two-pass
/
X
78.7 (+10.4)
3343.2
Two-pass + ST@11
/
Self-Test
80.5 (+12.2)
5408.3
Two-pass + CI.@11 CI.@1
/
Clustering @ 11
75.0 (+6.7)
5070.7
FUNCODER @5
/ / Consensus@
Consensus @5
83.5 (+15.2)
4040.9
FUNCODER
85.4 (+17.1)
5402.0
and N is the token length of the final program. This further exemplified and explained in |A.7 We observe that function decomposition and re-composition deliver cumulative performance improvements. Functional consistency is also shown to prevail over self-testing, Putting them all together, FUNCODER received +17.1 improvement with just 5.09x more tokens over baseline. Compared to previous SOTA LDB (= 23K tokens), we are able to gain +2.5 in performance with 76.5% token usage reduction.
3.2 Mathematical Reasoning
Code can be viewed as tool for augmenting the reasoning capabilities of L.MMs (Chen et al. 2023b). Alternative to text-based reasoning like Mhain-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 al. 2021b), competition-level mathematical reasoning benchmark.
3.2.1 Experiment Setup
Benchmark The experiment 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. can be noticed that labels in MATH are formatted in 18T,,, 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 Chain- of-Thought (Wei et al.) 2022), and program-aided baselines: Program-of-Thooe 2023b). Self-Refine (Madaan et al.) 2023). Cumulative Reasoning (Zhang et al.) 2024). The results of Cumulative reasoning are reported the original paper. Standard prompting and chain-of-thouge reasoning use 7-shot demonstrations constructed from the train set. Program-of-Thoon Thought and Self- Refine prompt the model with 1-shot demonstration generate 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.
(Chen al.
Implementation Details FUNCODER adopts 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 set to to match baseline methods.
3.2.2 Results
The experimental results on MATH are shown in Table 3 It shows that program-aided reasoning generally outperforms text-based reasoning. With GPT-4 the backbone, FUNCODER outperforms the strongest baseline Cumulative Reasoning (Zhang et al. 2024) by (6.0 8.3%) and surpasses the vanilla program-aides aided baseline PoT (Chen et al.) 2023b by (10.0 14.7%). When using GPT-3.5- turbo as the backbone, FUNCODER exceeds the strongest baseline by (6.2/ 11.19 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.
7

---

Table 3: Experimental results MATH, competition-level mathematical reasoning benchmark. Best results are in bold. Text-based reasoning methods are denoted with T, while others use program- aided reasoning. We report both overall results and results in seven subjects: Prealgebra, Algebra, Number Theory, Counting & Probability, Geometry, Intermediate Algebra, and Precalculus.
Model
Method
Prealg.
Alg.
Prob.
Geo.
InterAlg.
Precale.
Overall
Standard
62.2
37.4
20.0
29.8
24.4
21.8
34.6
CoT
59.8
51.1
28.9
29.8
28.6
26.7
30.9
40.0
GPT-3.5
PoT
68.3
50.4
33.3
48.9
21.4
18.2
29.1
41.0
Self-Refine
74.4
49.6
48.9
57.4
28.6
35.6
36.4
48.6
FUNCODER
76.8
61.2
55.6
59.6
34.1
36.0
41.8
54.0
Standard
81.7
82.7
71.1
72.3
59.5
46.7
47.3
68.2
CoTt
84.1
87.1
62.2
68.1
45.2
48.9
54.5
68.6
GPT-4
PoT
79.3
80.6
75.6
72.3
50.0
47.8
58.2
68.2
Self-Refine
82.9
82.0
77.8
76.6
55.6
63.6
72.2
CR
86.6
86.3
88.7
71.1
53.7
51.5
51.8
72.2
FUNCODER
89.0
92.8
82.2
83.0
59.5
63.3
56.4
78.2
CoTt
56.1
47.5
31.1
34.0
40.5
14.4
38.2
38.6
Llama3ae
PoT
67.1
32.4
24.4
34.0
16.7
21.1
18.2
32.6
FUNCODER
67.9
45.7
51.1
53.2
19.0
37.8
30.9
45.0
PoT
20.7
14.4
17.8
25.5
4.8
8.9
9.1
14.4
StableCodegs
FUNCODER
46.3
30.2
20.0
29.8
20.0
18.2
26.6
PoT
35.5
26.1
15.0
16.7
0.0
5.5
33.3
15.2
CodeLlamag4h
FUNCODER
44.8
46.1
37.8
34.1
24.6
37.5
24.4
On open-source models, FUNCODER with Llama3 outperforms PoT by (12.4/8..0% It has even reached competitive performance against the state-of -fee----thhh-- the-art method based on GPT-3.5 (45.0 v.s. 48.6). When employing StableCode and CodeLLaMA significant improvements by (12.2 / 84.7%) and (9.2 60.5%), respectively. This improvement demonstrates that approach significantly boost smaller LLMs, democratizing the complex reasoning capabilities of open-source LLMs through programming.
the backbone,
approach achieves
3.2.3 Analysis
GPT-3.5
StableCodego
FUNCODER Can Handle Harder Questions
4igure4comparr compares between CoT, PoT, and FUN-
Ours
50
PoT
CODER across varying difficulty levels. It illus- trates that CoT performs comparatively well on the casiest questions, but suffers from a steep decline in performance difficulty increases. This suggests that text-based reasoning is inad- equate for tackling challenging mathematical reasoning problems. The same situation is also observed POT. In contrast, our method consis- tently demonstrates high performance even challenging problems, particularly excelling on level 5 difficulty with nearly double the perfor- mance compared to PoT and COT. This reflects that our method, with divide-and-comm and-conquer applied, effectively cope with complex problems.
60
CoT
30
20
10
Level
Level Leve3 2
Level
Lend
Lan
Levell
Level.
Level
Figure Average accuracy in each level with the chat model (GPT-3.5) and the code model (StableCodeg,, on the MATH benchmark.
Decomposed Functions are Domain-Specifie 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 fo-ffutntionss of FUNCODER in each MATH subject, as shown in Table 4 It is apparent that different subjects require different abilities, each with own set of sub-functions closely associated with 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.

---

Table 4: Top-3 most commonly used functions in each subject of MATH, listed in descending order.
Subject
Functions
Prealgebra
is is_prime / factorial / ged find _ootsooss / is Ltt__peeeeersppeeee get divisors mod inverse ged
Algebra
/ find _omain
Number Theory
Counting & Probability
factorial / combinations / binomial coefficient couplify_fraction / calculate_triangkee
Geometry
distance find mootsoots / evaluate pealuatt_polyoomaall / inntrpgginntooooattonnn
Intermediate Algebra
Precalculus
cross_ pros__product / fraction certiiionfrom___ from_angle/ dot
4
Related Work
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 el 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., [021] Nijkamp et al. 2023
Li al. 2022 Rozière et al., 2023 Li et al. 2023b Guo et al. (024). Tasks between code and natural language (NL) can be generally divided into three major categories: NL2Code tasks such as
code generation (Austin et al.
202T Chen al. 202T] Hendryyks et al., 202 Khan et al.
2023
and code search (Husain et al.
2019); Code2Code tasks including code completion (Lu et al.
202 1
Zhang et al. 2023; Liu et al., et al. (022)). and test generation (Siddiq et al., 2023) [Schäfer et al. 2024)); Code2NL tasks like code
2024), ) code translation (Ahmad et al. [023] Zhu et al.) [022] Yan
summarization (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 't always run 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. Self-
improvement methods (Madaan et al. 2023 Shinn et al. 2023; Chen et al., 2024 Zhong al. 2024) design closed-loop procedures that repeatedly refine the code based on the feedback. Like
real- real-Tife life software development processes, multi-agent frameworks (Hong et al. 2024] Qian 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 shorteomings 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 tool that augments LLM to solve complex reasoning questions or interact with external environ- ments. Pfogram-of-Thorr
(Chen et al., 20236) and PAL (Gao et al. 2023) prompt the model to generate a program that solves mathematical or symbolic problems. MathPrompper (Imani al. 2023) and Chain-or Chain-of-Conn of-Code (Li et al.] 2023a) fuse the text-based chain-of thain-of-thought with code- based program-of-thougee prompting to complement each other in mathematical reasoning. Cumulative Reasoning (Zhang et al. 2024) conducts bottom-up reasoning to derive the final answer progres- sively. Numerous work (Sun et al. 2023] Wang al., 2024 Yang et al. 2024) also use code as an intermediate component to bridge
LLM agents with external environments.
Decompose for Complex Problems Several recent works employ dccomposition reduce the complexity of hard problems. Least-to-Most (Zhou et al. (2023) adopts two-stage approach, which first decomposes complex problems, and then solves each sub-problem individually tackle complex reasoning tasks. Successive Prompting (Dua et al. 2022) adopts dynamic decomposition, iteratively breaking down problems and addressing sub- nub-problems. Tree-of-Thoughe (Yao al., 2023) breaks down complex problems into state spaces and uses tree search to solve them. Parsel (Zelikman jet 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. 2023) performs retrieval in repositories to complete unfinished code one by one. Unlike these methods, FUNCODER recursively decomposes problems into 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-augmmeted 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-come sub-modular consensus utilized by FUNCODER can be extended to a wider range of problems, and we consider this as future exploration.
and
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.
6 Conclusion
In this paper, we presented FUNCODER, a novel code generation framework that integrates the divide- and-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.
Acknowledgments
We would like to acknowledge the reviewers and chairs for their inspiring and constructive feedback. The research in this article is supported by the National Key Research and Development Project 200IIFF09010022 the National Science Foundation of China (U22B2059, 62276083). Ming Liu and Qianglong Chen are the corresponding authors.
References
Wasi Uddin Ahmad, Md Golam Rahman Tushar, Saikat Chakraborty, and Kai- Wei Chang. AVATAR: A parallel corpus for Java-python program translation. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.). Findings of the Association for Computational Linguistics: ACL. 2023, pp. 2268-2281, Toronto, Canada, 2023. Association for Computational Linguisties. doi: 10. 0066:3/1/2023..mmiinn----- http::///claannhoooy..ooom org
URI.
or2/2023.. 2023. findings-ach acc.ingg-acc.143 143
Jacob Austin, Augustus Odena. Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry. Quoc Le, and Charles Sutton. Program synthesis with large language models. ArXiv preprint,
2021. URL http::tts:///trtt org/ aba/ 077332
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florins Balcan, and Hsuan-Ties Lin (eds.). Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, hash/
December 6-12, 2020, virtual, 2020. URL https://prooeeednngs www.ere....pppppeeeoeoee wtw.afffeeee671111aaaaaaaCe22 Att.re/ettAAADAttattttttttt
Federico Cassano, John Gouwar, Daniel Nguyen, Sydney Nguyen, Luna Phipps-Costin, Donald Pinckney, Ming-Ho Yee, Yangtian Zi, Carolyn Jane Anderson, Molly Feldman, Arjun Guha. Michael Greenberg. and Abhinav Jangda. Multipl-e: A scalable and polyglot approach benchmarking neural code generation. IEEE Trans. Software Eng., 49(7):3675-33)
2023. doi: 10.
URL https
//doi. org. 10. 1109/ TSE. 2023. 3267446
Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian liannGuang Lou, and Weizhu Chen. Codet: Code generation with generated tests. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023a. URL htt.ttts::///// https:///openreview.nr forum Pidd Xtr66Cmmu9c
10

---

Mark Chen, Jerry Tworek. Heewoo Jun, Qiming Yuan. Henrique Pondé de Oliveira Pinto, Jared Kaplan. Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder. Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang. Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wajeiech Zaremba. Evaluating large language models trained on code. ArXiv preprint, abs/2107 03374, 2021. URL https
//arxiv org/ 2107 03374
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research, 2023b. ISSN 2835-8856. http::ttt:////eeeee
net//oorumii--y72471553
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net, 2024. URL httpppp///opeeeeeeeew.eeeeeeeees wttp://wwww.eeeeoooooooo/aaaaaaa
Ole-Johan Dahl, Edsger W. Dijkstra, and Charles Antony Richard Hoare. Structured programming, volume of A.I.I.C. Studies in data processing. Academic Press, 1972. ISBN 978-0-12 12-00--2-000550-3
Dheeru Dua, Shivanshu Gupta, Sameer Singh, and Matt Gardner. Successive prompting for decomposing complex questions. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 1251-1265, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguistics. doi: 10. 1tt.6663111122222mmmmmmmmm.
URL
https://accanthooogyy .rgpey...g///o/ 202g/202..o0 emnlp-main.9 81
EbTech. How to Interpret Contest Ratings Codeforces, 2024, URL https://coaeforces.comm comblog// entry/68288
Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng. Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, and Ming Zhou. CodeBERT: A pre-trained model for programming and natural languages. In Trevor Cohn, Yulan He, and Yang Liu (eds.). Findings of the Association for Computational Linguisties: EMNLP 2020, pp. 1536-1547, Online, 2020. Association for Computational Linguistics. doi: 10. 18.3/v13vv/ 1020.findings. emnlp.133 139.. TtRLhttps:// / acl anthology...ooooooooo org/2020
2020. f findings emnlp. 139
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. PAL: program-aides -iddd language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (cds.), International Conference on Machine Learning, ICML 202., 23-29 July 2023, Honoludu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 10764-10799. PMLR, 2023. URL httph:tttppppeeee httttp::/pproceedingss mlr. ppwps//222/ v2tp///2222////.2.2.// .html
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang. Deepseek-coder When the large language model meets programming the rise of code intelligenee. ArXiv preprint, abs/2401. 14196, 2024. URL https wwwrxi.org//bs////. 14196
P.R. Halmos. Naive Set Theory. Undergraduate Texts in Mathematics. Springer New York, 1998. ISBN 9780387900926. URI. https://books.. wow.le...o...oooe..eeeoeoeooo... com. htt.//ookkssddxxx2222gegeee
Dan Hendrycks. Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He. Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. In Joaquin Vanschoren and Sai-Kit Yeung (eds.). Proceedings of the Neural Information Processing Systems Track on Datasers and Benchmarks 1, NewrlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021a. URL StRL/httss:///ee hattpp:://ataasets-eennii Mash/c24cd766e wow.c244e666611113444444228322
wwtpppppp////../..// proceedings.neus ce4 3aaee136eeebbbbbbbbbb022222 htw.://aaaaaaab.aaaaaaaaaaaaaeee Abstract-rounde html
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song. and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Joaquin Vanschoren and Sii-Kit Yeung (eds.). Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, vir- tual, 2021b. URL https: wew.iess-ennbcacnnbeeeeaaa sancchmarks-proccedding.. proceedings wwwpeediinnnnnnuiiiieee htcc/paper/2221/hhaee bes5aa5ecco0007/332222cccooo.o.3 -wtrsaat-sbstttttteeeeeeeee round2, html

---

Sirui Hong, Mingchen Zhuge, Jonathan Chen. Xiawu Zheng, Yuheng Cheng. Jinlin Wang. Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin. Liyang Zhou, Chenyu Ran. Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. MetaGPT: Meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net, 2024, URL http:ttt////peeeeee//
Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Mare Brockschmidt. Codesearchnet challenge: Evaluating the state of semantic code search. ArXiv preprint, abs/1909.09436, 2019. URL https: org/ abs/ 1909. .9436
Shima Imani, Liang Du, and Harsh Shrivastava. MathPrompter: Mathematical reasoning using large language models. In Sunayana Sitaram, Beata Beigman Klebanov, and Jason D Williams (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), pp. 37-42, Toronto, Canada, 2023, Association for Computational Linguistics. doi: 10. 201118653/112222 acl-:suusttti.yy........ URL httpp::/aaclattbeee
org/ 202g/2023.rrmm acl- cellinnuutrry.c .4
Xue Jiang, Yihong Dong, Lecheng Wang, Qiwei Shang, and Ge Li. Self-planning code generation with large language model. ArXiv preprint, abs/2303.06688 0.6399 2023. URL htttp:://axxii www./ogg///ooo.... 22033 06689
Xin Jin, Jonathan Larson, Weiwei Yang, and Zhiqiang Lin. Binary code summarization: Benchmarking chatgpt/gpt-4 and other large language models. ArXiv preprint, abs/2312.09601, 2023. URL. https wwwpii/.rrg/abbbaaaaaeea
Mohammad Abdullah Matin Khan, M. Saiful Bari, Xuan Long Do, Weishi Wang. Md. Rizwan Parvez, and Shafiq R. Joty. xcodeeval: A large scale multilingual multitask benchmark for code understanding, generation. translation and retrieval. ArXiv preprint, abs/2303.03004, 2023. httpss::: wwwpsiiii.oora/eeooo.oe www.://///aaaaee/e..e/... 2b303 2303 03004
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gon- zalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Chengshu Li. Jacky Liang, Andy Zeng. Xinyun Chen, Karol Hausman. Dorsa Sadigh, Sergey Levine, Li Fei-Fei, Fei Xia, and Brian lchter. Chain of code: Reasoning with language model-augmented code emulator. ArXiv preprint, abs/23 12.02444 2023a. URL httl:htttt://aaee orge atrgg//bb/2331 04474
Raymond Li, Loubna Ben Allal, Yangtian Zi. Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Mare Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltomozhskii, Terry Yue Zhuo Thomas Wang. Olivier Dehaene, Mishig Davaadorj. Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade. Armel Zebaze, Ming-Ho Ho Yee. Logesh Kumar Umapathi. Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang. Rudra Murthy V. Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Moustafa-
Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ehert, Tri Dao. Mayank Mishra, Alex Gu. Jemnifer Robinson, Carolyn Jane Anderson. Brendan Dolan- Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau. Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. Starcoder: may the source be with you! Arxiv preprint, abs/2305 06161, 2023b. https: htap::///araaa /ttp:///axxxvv//ii wwtp:///.rrrgaaaa////aa////// 22010000110010001111111111101161 06161
Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Lehlond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' A'Attmee Igor Babuschkin, Xinyun Chen. Po-Sen Huang. Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Mol- loy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition- code generation with alphacode. ArXiv preprint, abs/2203.0781 2022. URL /tttps:///a/x/// org/ abs/ 2200..22233..2 22///2223222222 07814
Tianyang Liu, Canwen Xu, and Julian McAuley. Repohench: Benchmarking repository-level code auto- completion systems. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net. 2024. URL httL:httt::///og https:///oenrrviee.neet/ wwt.riiwwwweeetonnniiiiiiiee PPjZIOuQuFF]
Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Nouamane Tazi, Ao Tang. Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, Tianyang Liu, Max Tian, Denis Kocetkov, Arthur Zucker, Younes Belkada, Zijian Wang. Qian Liu, Dmitry Abulkhanov, Indraneil Paul, Zhuang Li, Wen-Ding Li. Megan Risdal, Jia Li, Jian Zhu, Terry Yue Zhuo, Evgenii Zheltonozhskii, Nii Osae Osae Dade, Wenhao Yu, Lucas Krauß, Naman Jain, Yixuan Su, Xuanli He, Manan Dey, Edoardo Abati, Yekun Chai, Niklas Muennighoff, Xiangru Tang, Muhtasham Oblokulov, Christopher Akiki, Marc Marone, Chenghao Mou, Mayank Mishra, Alex
12

---

Gu, Binyuan Hui, Tri Dao, Armel Zebaze, Olivier Dehaene, Nicolas Patry. Canwen Xu, Julian J. McAuley. Han Hu, Torsten Scholak, Sébastien Paquet, Jennifer Robinson, Carolyn Jane Anderson, Nicolas Chapados, and et al. Starcoder and the stack v2: The next generation. ArXiv preprint, abs/2402.19173, 2024, URL https://arxiv.c org/ www.////././.......////////// 2402. 19173
Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin B. Clement, Dawn Drain, Daxin Jiang, Duyu Tang. Ge Li, Lidong Zhou, Linjun Shou, Long Zhou, Michele Tu- fano, Ming Gong, Ming Zhou, Nan Duan, Neel Sundaresan, Shao Kun Deng, Shengyu Fu, and Shujie machine learning benchmark dataset for code understanding and generation. In Joaquin Vanschoren and Sai-Kit Yeung (eds.). Proceedings of the Neural Information Processing Sys- tems Track on Datasets and Benchmarks 1. NeurIPS Datasets and Benchmarks 2021, December 2021. virtual, 2021. URL httptttt/t//ttaateet http///ttaattta--bbbbmaaaaree www.beancchhheeeeeee wttpraaaaammaaeeeooeeeeiieeeeeee
Liu. Codexglue:
wwwpadiinnnnnnuiisinee www.neeurripcccoooo hwwpppps..c/ppppe//2////aaaaaa html
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self- feedhack. In Thiirty-sevemth Conference on Neural Information Processing Systems, NeurIPS 2023, 2023. URLL/sttp://ppeenevvveee.et www.://www.eeeooooeeeeeeee S37
Meta Al. Introducing Meta Llama 3: The most capable openly available 1lm to date, 2024. URL https
//ai //a..meta.com www................. matitaaccoo/blooommtallllllee 3/
Mistral Al. Codestral: Hello, world!, 2024, httttp::/aasstrallaa/nesssss///s
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingho Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali. Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https:
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama. Is self-repair silver bullet for code generation? The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net, 2024. URL https:// openreview aett/torummid=y0OXXRR....
OpenAL. GPT-4 technical report. ArXiv preprint, abs/2303.08774, 2023. URL. https://arxiv.or 2303. 08774
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddic Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feed- back. In NeurlPS. 2022. URL httt::/ppapera wwwpppppprr..aaapppppppppp.apa. www.ppppccpppppppppeeee httpppppprr..aseppppep/pe//epeee wtt.r//e----ttttaate--ooeeeeeeee httmeerrrnneeeemmlll
hash/
Nikhil Pinnaparaju, Reshinth Adithyan, Duy Phung. Jonathan Tow, James Baicoianu, Ashish Datta, Maksym Zhuravinskyi, Dakota Mahan, Marco Bellagente, Carlos Riquelme, and Nathan Cooper. Stable code technical report. ArXiv preprint, abs/2404.01 226, 2024. URL lattps///axxxx herg/abs/200 01226
Chen Qian, Xin Cong, Cheng Yang, Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun. Communicative agents for software development. ArXiv preprint, abs/2307.07924, 2023. URL
httpp://arxxa htap::///aaaio.or/abb////// httgg//b///// 2207 00223377772220 .7924
Baptiste Rozière, Jonas Gehring. Fabian Gloeckle. Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Fanton-Ferrer. Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar. Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code Ilama: Open foundation models for code. ArXiv preprint, abs/2308. 12950, 2023. httlhhtts://aaa org/ aba/ 2308 12950
Max Schäfer, Sarah Nadi, Aryaz Eghbali, and Frank Tip. An empirical evaluation of using large language models for automated unit test generation. IEEE Trans. Software Eng., 50(1):85-105, 2024. doi: 109/ SSE.2023.3333955.
//do:::://doi..o 1ttp:/.../1/011................1
2023. .334955
Kensen Shi, Jacob Steinhardt, and Percy Liang. Frangel: component- based synthesis with control structures. Proc. ACM Program. Lang., 3(POPL), 2019. doi: 10.1145/3290386. URL //doi. org/ 1145/32945330
13

---

Noah Shian, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao, Reflexion: language agents with verbal reinforcement learning. In Teirth Conference on Neural Information Processing Systems, NewrlPS 2023, 2023. URL https::/ httpaarwwwwww.eeefrrrrreeeeeeeee het/fooumiiddvAEA
Mohammed Latif Siddiq. Joanna C. S. Santos. Ridwanul Hasan Tanvir. Noshin Ulfat, Fahmid Al Rifat. and Vinicius Carvalho Lopes. Exploring the effectiveness of large language models in generating unit tests. ArXiv preprint, abs/2305.0044 00418, 2023. /tttls/s:://arat
org/
00418
Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models. In Thirth-seventh Conference on Neural Information Processing Systems, NewrIPS 2023. 2023. URL https:://pppereeiiii net/ wwr.mooddddooaaooeeooooo wnn.mminede
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen. Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu. Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Authony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux. Thibaut I. Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nic, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu. Zheng Yan, Iliyan Zarov, Yuchen Zhang. Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. ArXiv preprint, abs/2307.09 0.9288, 2023. URL https://arxiv, http://xxxxv.../aabb// abs/ 2307. 09288
Xingyao Wang. Yangyi Chen, Lifan Yuan. Yizhe Zhang. Yunzhu Li, Hao Peng, and Heng Ji. Executable code actions elicit better LLM agents. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, 2024.
URL/htttp::/ggenrrviiee http:///pnrerrieeeeeeffrrrrrrr wtt.rreeee..eeooooooooooooooeaea ?id-8oJyuKfrFy
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe Ve, Fd H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL /ttps://////
Yue Wang. Weishi Wang. Shatiq Joty, and Steven C.H. Hoi. CodeT5: Identifier-awar unified pre-trained encoder-decoder models for code understanding and generation.
Marie-Francins Moens, Xuanjing Huang. Lucia Specia, and Scott Wen-tau Yih (eds.). Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8696-8708, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics. doi: 10. 1es118663/vl 1/653/v1/2021.000 222022.emmnppnnn aomlp-main.688. URLhttpps: //aclanthology- orooo/g//00 hrgg/2021.22 2021.emmmppp......mmmmmmmmmmml.m www.eemnaaaa.e.eeeee main. 685
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian lchter, Fei Xia, Ed H. Chi, Quoe V. Le. and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http:://ppppppe nips. cc/ sappaper html
files/ https/ppprr////// 2022// 2022/ http:/ahhhhhhaaaaaa 0odd5699613544cccio 15af Of 7 731773331abbbba www.bbatttttttttaeeeeeeeeeeeeeee
Thomas Wolf, I ysandre Dehut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Mai, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's 's transformers: State-of-the-art natural language processing. ArXiv preprint, abs/1910.03771, 2019. URL hRt htttp:://axxi......//// www./iiiwww.o..eooooooooo abs/1910 03771
Weixiang Yan, Yuchen Tian, Yunzhe Li, Qian Chen, and Wen Wang. CodeTransOcean: A comprehensive multilingual benchmark for code translation. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023. pp. 5067-5089. Singapore. 2023. Association for Computational Linguistics. doi: 10. 10.18633/112023..0 wwindiinnnnennllep org/2023, findings----ii - emnlp.337
/tLt:ttts:///at acttolloog
Ke Yang. Jiateng Liu, John Wu, Chaoqi Yang, Yi Fung, Sha Li, Zixuan Huang, Xu Cao, Xingyao Wang, Heng Ji, and ChengXiang Zhai. If LLM the wizard, then code the wand: survey on how code empowers large language models to serve as intelligent agents. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, 2024. URL http::tt/peesreeeeee//
nwt/ waw.ammmmdddlmmlliiimi 8dmNOD9hbg
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran. Thomas Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty seventh Conference on Neural Information Processing Systems, NewrIPS 2023, 2023. https:// wwt id=5Xclecx01h
14

---

Eric Zelikman. Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. Parsel: Algorithmic reasoning with language models by composing decompositions. In Thirty-seventh Conference Neural Information Processing Systems, NeurlPS 2023, 2023. URL http:////pppeeeeeeeeeeeeer/re/ae
Fengji Zhang. Bei Chen, Yue Zhang. Jacky Keung, Jin Liu, Daoguang Zan, Yi Mao, Jian-Guang Lou, and Weizhu Chen. RepoCoder: Repository-lece code completion through iterative retrieval and generation. Houda Bouamor, Juan Pino, and Kalika Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 2471-2484 Singapore, 2023. Association for Computational Linguistics. doi: 10. 10053//1/2023..oo wetp:...mmmmppmmpe main. 151. URL httppttt///aaaaathooollo
org/2023 emnlp main. 151
Yifan Zhang. Jinggin Yang. Yang Yuan, and Andrew Chi Chi-Chih Yao. Cumulative reasoning with large language models. In ICLR 2024 Workshop Bridging the Gap Between Practice and Theory in Deep Learning, 2024.
Lily Zhong, Zilong Wang, and Jingbo Shang. LDB: A large language model debugger via verifying runtime exccution step-by-step. ArXiv preprint, abs/2402. 169066 2024. URL https://arxiv.... org/ abs/2402 16906
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Lc, and Ed H. Chi. Least-to-most prompting enables complex rcasoning in large language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL id=WZH7099tgfM
wtt.:eeeweeieeeeeooouuueu nst/forum?
Ming Zhu, Karthik Suresh, and Chandan K. Reddy. Multilingual code snippets training for program translation. In Shirty-Sixth AAAI Conference Artificial Intelligence, AA22 Fhurth Conference Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Sympexium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22- March 1, 2022, pp. 11783-11790. AAAI Press, 2022. URL httph:tps/// //ojs aaai. org/ orw.oordr..///////.oooooooo.m.ee inde/xndxxx////. monde..ppp/uuee
15

---

A Appendix
In the supplementary materials, we provide the details of implementation (A.I) baseline information and settings (.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 and include all the prompts in Appendix
Table 5: Symbols and Glossary.
Alias
Description
(i) Symbols f(x)
Function
In the programming language, a function consists of header, documentation, and its body {h,, dr. by A func- tion can also be viewed as mapping f D
lf
Function Header
Declares the function name, arguments. and return type, and is used as signature to identify the function in program.
dy
Function Docstring (or Decumentation)
Provides additional usage details for this function, but is optional. We encourage the model to generate docstrings to describe sub-goals precisely.
by
Function Body (or Implementation)
The function hody contains a subroutine that describes its control flow and behavior. Functions may he invoked from within.
((())
Partially Implemented
A provisional function structure generated by the LLM where sub-procedures are not yet implemented.
(*)
Solved Function
A final implementation that is no longer changed and represents FUNCODER'S 's final comprehension and solution the original problem.
F= (fe)
Sampled Implementation
Functions that re-implement (ax based solved sub- functions, generated by models using the same input prompt.
CHIL(((()) T
Dependency Dependency Tree
Functions that are used in f()). (exclude [(x) itself)
Defined by TREE(f, CHILD(f)), where is the root node the current sub-task. Circular references are ignored. implement a certain function f respecting sub- procedures as potentially reusable components.
F
Function Composition
(ii) Glossary
System Test
Hidden Test
System testing is phase where set of previously invis- ible cases run against the submitted program to validate if code correct and produces the expected output for different categories of inputs.
Unit Test
Assertion
A test an assertion consisting given input and expected output, whereas in Python, takes the form of assert func (x) ==
Self-testing
Self-testing is an evaluation process that prompts the model to generate unit tests (assertions) to assess the rectness the generated program.
AlphaCode- Clustering
AlphaCode proposed clustering process that elects didate program from number of samples, recognizing programs that produce exactly identical outputs as equiva- lent, and picks one program from the largest cluster.
A.1 Implementation Details
Models We access the OpenAl models GPT-3.5 (gpt-3.5-urbo-06133 GPT-4 110--------0
and GPT--4o mini (got-40-mini-2024--77 through Azure OpenAI. Weights of community models Llama3 Matta--lamaa3------nneet Codestral (Codestral-22B-vv.)), StableCode (stable-code-
instruct-3b), CodeLlama (CodeLlama-344) Insttuuucctt and StarCoder2 (stareoder2-15b-inete 15b-instruct-v0.1
16

---

are downloaded from HuggingFace (Wolf et al., 2019) and served over an OpenAI-like API on 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 functions with new functions as the children of the current. We require that any new cub-function do not refer to existing functions, to avoid circular references. This generation process will be attempted at most times until any valid code with proper signature is found in the output. FUNCODER then traverses the function tree via depth-first -irst 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 sub- functions have been fully decomposed. Code for sub-functions made visible the LLM, which is requested to rewrite the current function with a I-shot demonstration (C.3) With functional consensus applied, the model samples multiple implementations with temperature of 0.8, and the one that reaches consensus will be kept for further bottom-up processing.
Functional Consensus The functional consensus is applied in the conquer stage. Formally, Consen- sus@k samples k-1 implementations
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 [ when two functions output the same value in given input, they will both add point to the overall similarity. A thrown exception or timeout during execution assigns -10 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 candidate with maximum scores over all inputs is selected, it reaches consensus with other implementations.
Hierarchical Code Interpreter Divide-and-con anrid--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- 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.
A.2 Baseline Details
Standard Prompting conducts one-time generation and directly output the entire code or final results. In code generation tasks, use 1-shot prompting setting with 0.3 temperature. For MATH, we sample question-answer pair per subject in the train set, resulting in a 7-shot prompt, and run self-consistency (Wang 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 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.
"assert func (x)
AlphaCode-like Clustering introduced with the model AlphaCode (Li et al. 2022), and samples multiple code solutions X. A fine-tuned model is used to generate test inputs upon which programs are evaluated. Programs are then clustered by whether the outputs are (exactly) identical, in which the largest group was selected. The final result comes from this largest group, where any result within would suffice. In our ablation study, we use similar settings to FUNCODER, sampling 11 candidate solutions with 0.8 temperature and generate sample inputs likewise.
17

---

consists of three generation stages: high-level sketch, Parsel program, and final program. The Parsel program is an intermediate representation of code that describes and organizes program structure. We report the result of HumanEval with GPT-4 from the original paper.
Parsel Zelikman et al.
2023
Reflexion (Shinn et al. (023) is 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 code test results with GPT-3.5 and community models under the reflexion strategy with max mexx_iterse iiter=t2e222 and Pass@) I. 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 visible tests for reflexion process.
MetaGPT (Hong et al., 2024) employs a multi-agent strategy that assigns roles and encodes human- like 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 the paper.
Chain-of-Thoughee Prompting (Wei et al. 2022) generates step-by-step reasoning leading to the final output answer. The solution formatted in Islie, and use vboxed to mark the final answer. We sample shot per subject in the MATH train set, resulting in 7-shot demonstration, and running with consistency @ and temperature of 0.7.
Trogram-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 solution() () function that returns the final answer to the problem. The program then executed 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 attempts. Similar to COT, Program-of of-onn-o--huhhhhh samples 5 programs at a temperature of 0.7 and votes the final result.
Self-Refine (Madaan al. 2023) iteratively prompts the model 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 al. 2024) starts from decomposing the input problem into propo- sitions and conducts bottom-up reasoning until the final answer can concluded. The results for Cumulative Reasoning reported in the original paper under with code setting.
A.3
Benchmark Details
Table 6: Overview and details of HumanEval, MBPP, xCodeEval, and MATH dataset.
HumanEval
MBPP
xCodeEval
MATH
Task Attribute
Code Generation
Code Generation
Programming Contest tags, difficulty
Mathematical Reasoning subject, level
Metric
Pass@1
Pass
Pass@1 7,635
EM-gpt
# Sample (original)
164
427
5,000 500
# Sample (ours)
164
200
500
Entry func
variant arguments return -2.8
variant arguments
main() standard input standard oulput
solution() n/a return
Input
Output
# Examples Tests
-2.1
n/a
System Tests
-8.1
-3.1
51.1
n/a
GitHub: noabshiin/rrftexion
18

---

HumanEval (Chen et al., 2021 is hand- crafted programmiig dataset designed to evaluate model's code generation capability. It consists of 164 instances involving programming skills in language comprehension, reasoning, algorithms, and simple mathematics. The problem contains 2.8 sample inputs and outputs on average in the function document, which can be leveraged provide additional guidance for the LLM to select or self-improve the programs. We conduct experiments on all 164 instances using accuracy (Pass@) 1) as the evaluation metric. The details of the Pass@ metric are described in Appendix A.4
MBPP (Austin et al. 2021) consists fundamental Python programming problems, with a total of 974 examples covering Python programming basics, standard library usage, and related assessment. Following Shinn et al. 2023), we adopt the mbpp-typed split from MultiPL-E (Cassano et al., 2023) and sample 200 instances, using Pass @ I as the metric. The original promp from MBPP includes all hidden tests in the input problem, which may cause label leakage when using these tests to refine or select programs. To ensure a fair comparison, MultiPL-E removes the test information in the prompt.
XCodeEval (Khan et al. 2023) is a competition-leeel multilingual and multitask benchmark con- sisting of 17 programming languages. xCodeEval collects 25 million openly available samples from codeforces.com comm a platform for competitive programming. The data we use include problem descriptions in problem wem_dddssrpiioon json and system tests from unittest_du db__ d..jjjnn which consists of 7,635 competition problems and averaged 51.1 tests per problem. Note that the tests in XCodeEval are crawled, some of them are incomplete due to the website context limit (they end with an ellipsis and the further content is missing); we filter out problems having invalid test cases. Based on the CodeForces Rating (EbTech 2024), we categorize the problems by their difficulty: Easy and Expert (2 2000). We sample 500 problems
(S 1200). Mid (1200-1599), Hard (1600-199)) from the full split with the basic filter rule mentioned above, resulting Table 7 The CodeForces problem has a different input/output style compared to HumanEval and MBPP: it scans input from Standard Input and prints the answer to Standard Output. Therefore, we judge the program on system tests using CodeForces-style judger and use Pass @ 1 (the program must pass all system tests) as the evaluation metric.
MATH (Hendrycks et al. 202 is a challenging competition-level mathematical reasoning dataset, with problems and solutions formatted ITTEX. covers seven categories: Prealgebra, Algebra, Number Theory, Counting & Probability, Geometry, Intermediate Algebra, and Precalculus. The original test set of MATH consists 5000 samples, and we randomly sampled 500 problems as shown in Table 7 In addition to text-based reasoning, writing programs is another promising way to solve mathematical problems. These methods involve writing a main () or solution () function, and executing the program obtain the final answer. Through experiments on MATH, aim to demonstrate that FUnCoDES can enhance LLM's ability to address complex mathematical problems through programming.
Table 7: Number of test samples in (a) xCodeEvall difficulty, (b) MATH level, (c) MATH subject.
Difficulty
Ours
Original
Level
Ours
Original
Subject
Ours Original
Prealgebra
82
871
Easy
178
1428
Level 1
39
437
Algebra
139
1187
Mid
112
1319
Level 2
90
894
Number Theory
45
540
Hard
87
1453
Level 3
108
1131
Counting & Probability
47
474
Expert
118
3289
Level 4
116
1214
Geometry
42
479
n/a
5
146
Level 5
147
1324
Intermediate Algebra
90
903
Precalculus
55
546
Total
500
7635
Total
500
5000
Total
500
5000
A.4 Metries
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.
@k
'Original MBPP prompt: htwp://hhccccoooooecoo//ooooeoee
19

---

In most of our experiments, we use @ass@ I as the metric, as it reflects the accuracy of the method framework achieved without feedback from humans. @ass@k, on the other hand, equivalent to filtering programs through hidden, human-annotann
test labels.
The ground truth label in MATH is written in LSTE, and the accuracy between labels and model predictions cannot be directly calculated through exact-match (EM). MATH provides judge program that preprocesses LaTeX syntax and check whether two disambiguated strings are equal. However, this is insufficient for evaluating X-fomaafre labels with variant program outputs. We follow the evaluation criteria from previous work (Zhang et al.) (024). using GPT-4 to assess the consistency between predictions and ground truths, with prompt shown in C.6
EM-GPT
A.5 Details of Analysis
Details of Preliminary Analysis on Self-testing (Figure a) The preliminary study is conducted on the HumanEval dataset, which includes system tests S evaluate the accuracy of the program, as well as one numan-annotated canonical solution c. For each question, we: (1) Obtain one solution program p from Standard Prompting. (2) Prompt the model to generate 7 self-tests T based on the question and entry function. The self-test is in the form of the unit test assert (x) == We then judge the generated program p and canonical solution c over the self-tests and system tests Formally, pair (x, Y) is used to identify whether program passes test Y. Where (p, S) indicates that the program can pass the system tests, demonstrating its correctness. And -(c, T)) means the canonical solution can not pass self-tests, suggesting that the tests generated by model could be wrong. The self-test results on generated programs are first evaluated and divided into two classes: self-test passed or failed. If the self-test passes, the self- celf-improvement methods will stop iteration and pick this program as final result. The next step is to determine whether the program can pass system tests. If the self-test fails, it indicates that there could be error in the program test itself. In this case, the correctness of the program is checked using final tests (p. S) and the correctness of the unit test by canonical program (c, T). The results GPT-3355 and StableCode are shown in Figure 3 and detailed explanations about these conditions can be found in Table
Table 8: Explanation on how we classify cases in self-testing preliminary study.
Class
Subelass
Condition
Explanation
The self-test result is consistent with the final judge. How- ever, self-testing methods cannot improve performance in this case, as the program from the bascline (Standard Prompt) already correct.
final passed
A A (p.
self-test passed
final failed
Self-test is toe weak to detect errors in the program, there could be edge cases that not been considered.
(p, ( ^ A(p,
This is good example that self-testing detects errors the program. Feedback from the test will used to select or refine the solution.
program wrong
A)) (c,
Bad case, the self-test produced an error result fil- tered out a correct solution. Continuously revising the code for this test will lead to performance downgrade.
unit-test wrong
(p, T) (b, (c,
self-test failed
The model is unable to generate a correct solution or test cases. Refining the program over faulty test samples will not lead the correct answer.
both
A(2, (c,
wrong
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.
(c.T)
Details Ranking Strategy Comparison (Figure We obtain 11 candidate programs from FUNCODER on HvmanEval 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
math httpa//wwww....aooooooooooooo/oe
20

---

placing correct programs at the forefront and filter out those with errors. Thus, we measure the effectiveness by computing Pass @ass@k results on the top-k-ranked programs selected by each strategy. The Pass@1 result serves as upper bound as it uses all programs to compute the pass rate.
4 the mathematical reasoning experiments, we used a subset of 500 items from the MATH test set, with average of 71.4 questions per subject. However, is not very confident represent common functions from only 71.4 programs. Therefore, sample 3000 problems from the MATH test set for this experiment and run the divide- only 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 cach category.
How We Count Frequently Used Functions MATH
A.6 Detailed Explanation of Algorithm
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 recursive process following a DFS pattern. We use square brackets (c.g. [L1]) below to denote line numbers in the pscudocode.
Algorithm FUNCODER procedure
Example
Divide(e)
Require: Entry func, froot (hronts droos {
Divide(a)
Require: Large language model, LLM
function FUNCODER(fcu)
2:
Divide
3: Seur [ft] EXTRACT(LLM(((u))
Divideld, e) Conquer(D, E)
4: for E {ffi) do
Conquer(8)
5:
bf NOTIMPLEMENTED then
6:
f2 + FUNCODEE((A)
D recursion
7:
end ADDCIILD(faar/ fi)
8:
D
D
9:
end for
10:
Conquer-
Divide(c) Conquer(C)
11: Feur + SAMPLE cur? CHILD(ffur)
Conquer(A)
12: faur + FUNCONSENSUS
13: return für
14:
end function
15:
return FUNCODER (frOD))((
> starts from root
D
E
D
E
Figure 5: Left: Algorithm for FUNCODER. Right: Decomposition example of A [B [DE] C].
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-problent represented as sub-function stubs (e.g., def (xs: list[int]) sub-problems of the current problem, thereby understanding the dependency between functions.
int) [L3]. In this process, we identify the
For each decomposed sub-problem 9 .2:.... we recursively FUNCODER obtain the final implementation G; for that sub- nub-problem [L5-L8]. This G3 shall replace the previously incomplete subfunction stub signature the final program.
Now that all sub-problema 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 G1, G2,... of sub- problems we generate the complete implementation F [L11] and return it [L13].
We hierarchically describe how this algorithm works in detail by combining with the example given the right half F
[a. 1] FunCoder (a)
[a.3] (LM(a) -> A, {b, c}
divide
[b.1] FunCoder (b)
[b.3] LLM(b) -> B, {d, e}
divide
21

---

-- [d. 1] FunCoder (d)
[d.3] (dM D,
divide
+-- [d]13] return D
nothing to conquer
--- [e. 1] FunCoder (e)
[e.3] (LM -> E, 0
divide
+- ---[e.13) return E
nothing to conquer
1b] LLM(B, {D, E}) -> B*
conquer
+- [b.13] 13] return B*
---[c_ [c.1] FunCoder (c)
[c.3] LLM(c) -> C, 0
divide
+-- [c.13] return C
nothing to conquer
[a.11] LLM(A, {B, c}) -> A=
conquer
[3.13] return A*
final result
A.7 Token-cost Complexity
Example We use the example from Figure where the final program consists of functions A[B [D, D,E,, cC, and A serves as the entry to the program. Here we respect the aforementioned notations, and further use the lower-case letter a to represent the number of stub tokens, upper-case A to represent the number of result tokens, for the function A, and other functions likewise. Let E the token-cost complexity of the final result.
N + B
In Standard, the code is only generated once to complete the given stub. We use parentheses to represent the order of LLM calls in full process.
(1)
a -> B D input tokens = output tokens overall
B ++ O(N)
In each step the FUNCODER/Divide stage, the bo-eeiimpleeeteed function will serve as the context. The function (stub) will be implemented and sub-function stubs are to be declared.
(1)
-> b
(2)
b -> d
(3)
d ->
(5)
e ->
(8)
c input tokens = + b output tokens overall = ONN)
+
d
+
+
2N
In every FUNCODER/Conquer, the context shall include the current function's 's definition and finalized implementations of sub- functionss. The output is the re-implemented current function.
(4)
d -> kD
(6)
e -> kE
(7)
b E -> kB
(9)
C -> kC
(10)
B C -> kA
input tokens
b B c +
d
D
0 +
< 2N
output tokens kA
kB + kC
kD
KE
kN
overall
(kN)
These stages in all bring FUNCODER's 's total token consumption to strictly O(kN) for every problem.
Token Complexity of FUNCODER is O(kN) Define N as the token length of the final program, which is correlated the inherent complexity the problem, and define k as the number of sampled candidates. We first explain in detail that the worst-case token cost of FUNCODER is O(kN):
22

---

The naive Standard method should naturally generate O(N) tokens. Sampling- based baselines like CodeT cost OKkN) tokens.
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 sub- functions. Within this stage, each function would appear at most once in input and twice in output. All Divide stages consume no more than 3NV 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 & times in output. If k = 1, consensus is implicitly disabled. All Conquer stages shall consume most (k + 2) tokens.
So FunCoder requires no more than (k + N) tokens in input-output, making its token consump- tion O(kN) even at worst-case, aligning with other sampling-based methods such as CodeTT 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.
A.8 Discussion About Functional Consensus
This section focuses on why functional consensus might enhance the correctness of programs and how it differs from other consistency-bant based methods. Self-consistency (Wang et al. 2023) is widely employed 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 symbols and used different approach. uses inputs and exccution results compare behavioral differences among programs. There have been similar methods, such as the strict clustering approach in AlphaCode (Li et al., 2022), which samples 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.
programs,funnctioall consensus in FUNCODER looked beyond the literal
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 al. 2019). We consider correct program solution which has multiple speccil--cse 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 '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 pool of programs that contained the fully-correct program and an assortment of other programs that respected certain cases the problem as aforementioned, it'd be obvious that the fully- correct 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 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 fully-correct program. Provided below is 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 fl float32). To get the answer right for all inputs, the function must consider 2
23

---

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 (#1. d2, d3, ag (5)) only considered case A and got just positive inputs right. For negative numbers, they literally gave up and crashed.
results (bg, by, by) remembered to consider case B, gave imaginary results for negative numbers, but forgot to do the same for positive numbers, returning only square root therein.
Only 2 results (cg, C1o) considered all cases and returned correct results for all inputs.
we pick the program through 'clustering'. the final result would be one of the results (41, 02......0. (s) 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 imputs. Without loss of generality, suppose that there are 2 test inputs 4.0, -900, one for each the 2 cases. We calculate the similarity as follows:
Programs a; got only v40 = |2.0, 22.0] right so each program here are similar with programs (01, 022 0g d4, 05, cg, C10), scoring 7 points.
Since by only went well with /-9.0 [3.0i, 3.00,,, programs here only score points for case B with the ones (bg, b7, by, Cg, C1u).
Each program in cı gets 7 points for 440 with (a1, 02, as, as as Co, C10), and gets 5 points for V-90 with (bs, b7, bg, Cq. C1o). Totals to 12 points.
The final result apparently leaned towards Cj as the correct solution, even if their outputs as a whole weren't even half much a; is. Through this example, illustrate that functional consensus has the potential to identify the correct samples even at their minority, outperforming other methods such self-consistens clustering.
A.9
Supplementary Results
Token Usage We provide token usage results in T FUNCODER and baseline methods on the HumanEval dataset with the GPT--3.5 model, whereas usage results other datasets provided in Table TO We report the average token usage per problem. The token usage is computed through the sum prompt tokens and completion tokens returned by OpenAl API chat completion cal 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.
Tokens
Method
Setting
Pass
Min.
Max.
Avg.
Med.
Standard CodeT Reflexion
One-time
68.3
648
1477
886.7
861
One-time + Self-Test
81.1 (+12.8)
2298
9645
4479.
4166
maxiter=2
69.5 (+1.2)
416
4906
1416.1
754
line-level
80.5 (+12.2)
24K
LDB (reported)
block-level
82.9 (+14.6)
23K
function-level
79.9 (+11.6)
27K
One-pass Two-pass
72.6 (+4.3)
826
3489
1233.7
1132
78.7 (+10.4)
2197
8406
3343.2
3078
FUNCODER
Two-pass @onsensus@5
83.5 (+15.2)
2455
9432
4040.9
3800
Two-pass + Consensus @ 11
85,4 (+17.1)
3015
13850
5402.0
5166
FUNCODER (ablation)
Two- poo-pass-oo + Self-TTsst@ 11
80.5 (+12.2)
2967
13758
5408.3
5184
Two-pass + Clustering@
75.0 (+6.7)
3044
9958
5070.7
4888

---

Table 10: Token usage of FUNCODER and baseline methods other datasets, i.e. MBPP, xCodeBval and MATH. Results are evaluated on GPT-3.5-turbo.
Tokens
Dataset
Method
Pass@1 1
Min.
Max.
Avg.
Med.
Standard
72.0
577
2102
744.9
717.0
CodeT
76.0 (+4.0)
2232
8172
2945.3
2866.0
MBPP
Reflexion
72.5 (+0.5)
391
3379
1205
569.5
FUNCODER
78.5 (+6.5)
3462
13229
5049.9
4644.0
Standard
20.2
1051
3343
1599.5
1530.0
CodeT
23.2 (+3.0)
2264
9245
3937.4
3733.0
XCodeEval
Reflexion
20.6 (40.4)
2977
1003222
401767.3
328591.5
FUNCODER
31.4 (+11.2)
4883
53225
10559.7
8927.0
PoT
41.0
551
5867
953.0
835.0
MATH
FUNCODER
54.0 (+13.0)
2622
30139
7075.5
5666.5
Full Results for Code Generation We provide results for conducted experiments on code generation benchmarks in Table Our method consistently improves the baseline community models by averaging 1 11% on MBPP and 150% on xCodeEval. is worth noting that small models have tendency have low pass rates competition problems, leading relatively higher randomness, therefore we run experiments and report the median result.
Full Results for MATH The MATH dataset divides the problems into five levels of diffieulty. 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 T2 and results for each level in
Table T3 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.
25

---

Table 11: Results for Code Generation. We report Pass @ evaluate metric. Results from the original paper are underlined, and the best results are bold.
HumanEval
MBPP
xCodeEval
Model
Method
Pass@1
A
Pass@
A
Easy
Mid
Hard
Expert
All
Standard
68.3
72.0
44.4
15.2
4.6
0.0
20.2
CodeT
81.1
+1288
76.0
+4.0
50.6
16.1
8.0
0.0
23.2
GPT-3.5
Reflexion
69.5
+1.2
72.5
+0.5
44.4
17.0
5.7
0.0
20.6
LDB
82.9
+14.6
76.0
+4.0
FUNCODER
85.4
+17.1
78.5
+6.5
62.4
29.5
11.6
0.0
31.4
Standard
82.9
73.5
68.5
39.3
19.5
1.7
37.4
Parsel
85.0
+2.1
CodeT
90.9
+8.0
77.0
+3.5
76.4
51.8
21.8
3.4
44.0
GPT-4
Reflexion
91.0
+8.1
77.1
+3.6
71.3
41.1
19.5
2.5
38.6
MetaGPT
85.9
FUNCODER
94.5
+11.6
79.5
+6.0
83.1
58.0
26.4
3.4
48.6
Standard
87.3
76.0
65.7
9.2
0.0
35.4
GPT-4o mini
CodeT
90.9
+3.6
75.5
-0.5
71.9
49.1
16.1
0.0
39.6
FUNCODER
91.5
+4.2
77.5
+1.5
72.5
52.3
11.5
0.0
39.8
Standard
61.6
60.5
9.0
1.8
0.0
0.0
3.6
Llama3gs
CodeT
68.9
+7.3
61.5
+1.0
12.4
0.0
0.0
0.0
4.4
FUnCODER
79.7
+18.1
62.5
+2.0
22.0
0.0
0.0
Standard
79.3
68.5
27.5
2.3
0.0
11.4
Codestralg2s
CodeT
86.0
+7.3
74.0
+5.5
34.8
7.1
3.4
0.0
14.8
FUnCOdER
89.0
+9.7
74.5
+6.0
49.4
15.2
3.4
0.0
22.0
Standard
61.0
51.5
7.3
0.9
0.0
0.0
2.8
StableCodege
CodeT
75.0
+14.0
57.5
+6.0
11.2
1.8
0.0
0.0
4.6
FUNCODER
81.0
+20.00
63.5
+12.0
13.5
1.1
0.0
Standard
43.9
53.5
2.3
0.0
0.0
0.0
0.8
CodeLlamay4h
CodeT
55.5
+11.6
56.5
+3.0
10.1
0.0
0.0
0.0
3.6
FUNCODER
66.5
+22.6
58.5
+5.0
10.2
0.0
0.0
0.0
3.6
Standard
59.8
64.5
18.0
0.9
2.3
0.0
7.2
StarCoder216a
CodeT
70.7
+10.9
66.0
+1.5
13.5
0.9
0.0
0.0
5.0
FUNCODER
78.7
+18.9
70.0
+5.5
29.2
4.5
0.0
0.0
11.6
26

---

Table 12: Experimental results on MATH, a competition-leww mathematical reasoning benchmark. Best results are in bold. Text-based reasoning methods are denoted with 1, while others use program- aided reasoning. We report both overall results and results seven subjects: Prealgebra, Algebra, Number Theory, Counting & Probability, Geometry, Intermediate Algebra, and Precalculus.
Model
Method
Prealg.
Alg.
NT
Prob.
Geo.
InterAlg.
Precalc.
Overall
Standard
62.2
37.4
20.0
29.8
31.0
24.4
21.8
34,6
CoTt
59.8
51.1
28.9
29.8
28.6
26.7
30.9
40.0
GPT-3.5
PoT
68.3
50.4
33.3
48.9
21.4
18.2
29.1
41.0
Self-Refine
74.4
49.6
48.9
57.4
28.6
35.6
36.4
48.6
FUNCODER
76.8
61.2
55.6
59.6
34.1
36.0
41.8
54.0
Standard
81.7
82.7
71.1
72.3
59.5
46.7
47.3
68.2
CoTt
87.1
68.1
45.2
48.9
68.6
PoT
79.3
80.6
75.6
72.3
50.0
47.8
58.2
68.2
GPT-4
Self-Refine
82.9
82.0
77.8
76.6
54.8
55.6
63.6
72.2
CR
86.6
86.3
88.7
71.1
53.7
51.5
51.8
72.2
FUNCODER
89.0
92.8
83.0
59.5
63.3
56.4
78.2
Standard
83.5
87.2
47.6
57.8
56.4
71.8
CoTt
90.2
95.7
82.2
68.1
50.0
61.1
61.8
77.2
GPT-4o mini
PoT
80.5
84.2
77.8
72.3
50.0
60.0
50.9
71.0
Self-Refine
79.3
83.5
75.6
87.2
47.6
57.8
56.4
71.8
FUNCODER
81.7
83.5
80.0
80.9
59.5
60.0
54.5
73.2
CoTt
56.1
47.5
31.1
34.0
14.4
38.2
38.6
Llama3s6
PoT
67.1
32.4
24.4
34.0
16.7
21.1
18.2
32,6
FUNCODER
67.9
45.7
51.1
53.2
19.0
37.8
30.9
45,0
PoT
70.7
56,1
46.7
44.7
21.4
26.7
30.9
45.6
Codestralyza
FUNCODER
81.7
61.9
46.7
55.3
28.6
45.6
38.2
54.8
PoT
20.7
14.4
17.8
25.5
4.8
8.9
9.1
14.4
StableCodo
FUNCODER
46.3
30.2
20.0
29.8
4.8
20.0
18.2
26.6
PoT
35.5
26.1
15.0
16.7
0.0
5.5
33.3
15.2
CodeLlamaçab
FUNCODER
44.8
46.1
37.8
34.1
13.6
24.6
37.5
24.4
PoT
46.3
29.5
28.9
25.5
21.4
27.8
23.6
30.2
StarCoder21se
FUNCODER
72.0
39.6
40.9
46.8
23.8
28.1
27.3
40.8
27

---

Table 13: Full results of each method different levels of MATH. The best results in bold. Text-based reasoning methods are denoted with while others use program-aides -ided reasoning.
Model
Method
Level 1
Level 2
Level
Level
Level 5
Overall
Standard
61.5
51.1
43.5
25.9
17.7
34.6
CoTT
76.9
48.9
50.9
33.6
21.8
40.0
GPT-3.5
PoT
61.5
51.1
56.5
33.6
24.1
41.0
Self-Refine
84.6
61.1
65.7
32.8
31.3
48.6
FUNCODER
84.6
65.9
68.5
43.1
37.4
54.0
Standard
89.7
85.6
83.3
55.2
51.0
68.2
CoT*
94.9
81.1
77.8
64.7
50.3
68.6
PoT
94.9
80.0
74.1
63.8
53.1
68.2
GPT-4
Self-Refine
94.9
81.1
83.3
62.1
60.5
72.2
CR
90.7
90.0
81.9
66.4
52.2
72.2
FUNCODER
94.9
90.0
81.5
75.9
66.0
78.2
Standard
87.2
82.2
80.6
62.9
61.9
71.8
CoT
97.4
90.0
87.0
71.6
61.2
77.2
GPT-4o mini
PoT
89.7
81.1
76.9
63.8
61.2
71.0
Self-Refine
87.2
82.2
80.6
62.9
61.9
71.8
FUNCODER
94.9
82.2
81.5
62.9
63.9
73.2
COT
76.9
46.7
46.3
25.9
27.9
38.6
Llama3ga 8t
PoT
64.1
43.3
41.7
25.0
17.0
32.6
FUNCODER
79.5
60.0
52.3
37.4
27.9
45.0
PoT
79.5
56.7
57.4
34.5
29.9
45.6
Codestralgzb
FUNCODER
84.6
66.7
67.6
43.1
39.5
54.8
PoT
35.9
22.2
19.4
7.8
5.4
14.4
StableCodeg,
FUNCODER
53.8
37.8
35.2
21.6
10.2
26.6
PoT
36.1
30.7
28.0
13.0
8.8
15.2
CodeLlamaças
FUNCODER
60.6
52.1
44.3
28.8
16.3
24.4
PoT
43.6
44.4
45.4
20.7
14.3
30.2
StarCoder2150
FUNCODER
71.8
57.8
55.1
26.7
23.3
40.8
28

---

B Examples
We provide example solutions for the baseline and FUNCODER on code generation and mathematical reasoning. All results are generated with GPT-3.5.
B.1
Code Generation
Info: xccettaas/Eccc077550000000006660 (binary search, difficulty 1800)
Problem
time limit per test: second
memory limit per test: 256 megabytes
input: standard input
output: standard output
Description
You have two friends. You want to present each of them several positive integers. You want present ent1 numbers the first friend and ent2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means that no number should be presented to both friends. In addition, the first friend does not like the numbers that remainder by prime number x. The second one does not like the numbers that are divisible without remainder by prime number y. Of course, you' 're not going to present your friends numbers they don 't like. Your task is to find such minimum number v, that you can form presents using numbers from may choose not to present some numbers at all.A positive integer number greater than 1 is called prime if it has no positive divisors other than 1 and itself.
divisible without
1,2,..., Of course you
Input
The only line contains four positive integers enti, ent2, x, (1<= entl, cnt2 cnt2<109; cnt1+cnt2<=109; 2<=x<y<=3+104)- the numbers that described in the statement. It is guaranteed that numbers x, y are prime.
# Output
Print single integer the answer to the problem.
## Sample Input
*# Sample Output
## Sample Input
2
= Sample Output
29

---

## Notes
In the first sample you give the of numbers (1,3,5) the first friend and the aet of numbers {2} the second friend. Note that you give set {1, 3, 5} to the first friend, then we cannot give any of the numbera 1, 3, 5 to the second friend. In the second sample you give the set of numbers (3) to the first friend, and the set of numbers (1, 2, 4} to the second friend. Thus, the ansver the problem is 4.
B.1.1 Standard
def main None:
entl, ent2, x, y list (map (mnt input () .pplit )))
# binary search
1, r 1, 2 (cnt1 + cnt2) upper bound
while
mid (1 r)
# number of numbers that can be given to the first friend cnt_x = mid //
# number of numbers that can be given to the second friend ent_y mid y
# number numbers that can be given to both friend ent_xy mid // (x y)
# number of numbers that can't be given to any friend ent_none mid ent_x ent_y ent_xy
if ent_x entl and ent_y >= ent2 and ent_none entl ent2
r = mid else:
1 mid print (1)
Result: Wrong answer on sample test 1: expected: '5', found: '8' [Ith token] X
B.1.2 FUNCODER
def main() -> None:
entl, ent2, x, y = map (int, input O O) split ())
left right int (2e9)
while left < right:
mid (left + right) // 2
if is_valid (mid,
y, entl, ent2):
right mid
else:
left mid
print (left)
def is_valid enti, cnt2):
check if there entl numbers not divisible by non_x_numbers v (v x)
if non_x_numben < entl:
return False
check if there non_y_numbers v (v y)
ent2 numbers divisible by y
if numbbrrs < cnt2:
return False
30

---

check if there cntl+ent2 numbers divisible by both and 1cm (x y) // (x, y)
common_numbers
(v // lcm)
1f common_numbers cnt1 cnt2: return False
return True
def (ed int, b: int) -> int:
#n" get the greatest common divisor of two numbers $a$ and $b$ ""*
while b: a, = b, % b
return
Result: Accepted /
B.2
Mathematical Reasoning
Info: htth//nmbee_thhoryyee
(level
Problem What is the sum of the smallest and second-smallest positive integers a satisfying the congruence 27a 17 (mod 40)
Ground Truth: 62
B.2.1 CoT
We solve for $a$ multiplying both sides of the congruence by the modular inverse of $278 modulo $40$. Since $27$ and $40$ relatively prime, we know that $27$ has a modular inverse modulo $408. We can find this inverse using the Euclidean algorithm: Abegin(align
(40 ,2)) &= (text(ged)(21 k= (text(ge))
<end(align*)
Therefore, the modular inverse of $278 modulo $40$ exists. We can find it using the Euclidean algorithm backwards:
Abegin(aligns)
&= 13 \odot 4
k= 13 3(40 27)
t- 4 /edot 27 Nedot 40.
(andggg
Thus, the modular inverse $27$ modulo $40$ is $4$. Multiplying both
sides of the congruence $27a\equiv 17 \pmod (40}$ by $4$ gives squialequiv 68 (400 Simplifying the left-hand side gives $8alequiv 28 \400. Dividing both sides by $4$ gives $2a! equiv (100S The smallest positive integer $a$ satisfying this congruence is $a=9$, and the recond-smallest is $a=19$. Therefore, the sum of the smallest and integers $a$ satisfying the congruence $27a 927avequiv 17 \pmod(40) is $9+19= {28)
positive
Result: 28 X
31

---

40 B.2.2 PoT
def ()
rha is the of the smallest and second smallest positive integers $a$ satisfying the congruence $$27a\equiv 17 Apmod {40)
$$
== candidates []
while len (en(cadidates)) < 2:
a (40
17) // 81
if 0 and (40
17) % 81 0: candidates. append (a)
k +
return sum (candidates)
Result: x
B.2.3 FUNCODER
from typing import Tuple
def solution() ()
q"""What is the sum of the smallest and integers $a$ satisfying the congruence $$27alequiv 17 spmod<40>"> $$***
positive
27
17
inverse sind_inverseee m)
x (b inverse) m
Find the smallest and second-smalles positive integers satisfying the congruence equation
// ged m)) ged, - extended m)
using the formula: x
si = s2 (m // ged)
return s1
def find_ innd_inveese (a: int, int) -> int: "#"find the inverse of $a$ modulo Sm$"""
x, axtended_euclidde m)
return % > else (x m) %
def extended_euclideeee euclid int, b: int) -> Tuplelint, int, int]: : """Extended Euclidean Algorith if b == 0: return a, 1,
ged, x1, y1 extended a b) x = y1
= x1 (a // b) y1
return ged, y
Result: 62 /
32

---

C Prompts
C.1 Prompt for Standard
You programming copilot, you can solve problem by writing Python functions. Your task is to:
You need to write Python function that returns the answer
You can import libraries to better solve the problem.
Do not write any code outside the function (importing is accepted)
<seer>:
Let 's think step by step and complete the following Python function sun_factor" that solves:
python
def sum sum_ factor (a: int, b: int) -> int
"""Return the sum all common prime factors $a$ and $b$""" """
raise HotlaplenenteeErtor))
<Assistant>:
First, I need to get the prime factors of $a$ and $b$.
Second, I
for" loop to find common element in two factors
list.
Here the "sum factor" function:
python
def sum_factor (a: int, b: int) -> int:
"**Return the factors_a prime_factor (a)
all common prime factors $a$ and "*@
factors_b prime_factor (b)
common_factors = get_ common (factors_a, factors_b)
return sum (actor)_
def prime_factor(x int) >> list:
"*"get list of prime factors of number $x$*"" ret -
while
i += 1 x:
if % == 0 and is_prime (i);
ret. append
return ret
def is is-prime(x: int) -> bool:
"*"dteeminee $x$ is prime number not
if 2:
return False
for i in range (2, (x**0.)) 1): if % == 0:
return False
return True
def get_common(e (a: list, b: list) -> list:
*** "*get common element in two list Sa$ and Sb$"""
=
item in a:
if item in b: ret. append (item)
return ret
33

---

<User>:
Let's 's think step by step and complete the following Python function "(
cur_func_name) that solves:
python
(cur_funcl
C.2
Prompt for Divide
You are programming copilot, you can solve problem by writing Python functions. Your task is to:
For every turn, you need to write a Python function that returns the answer based on Current Code (not code in chat history).
Do not modify function name, arg names, docstring in given functions.
You can import libraries to better solve the problem.
If a single function is too hard to solve, you can decompose it into multiple smaller functions.
You leave function unimplemented for now, but write the function at end of code and comment what the function does
<User>:
Current Code:
python
def sum con__commo_facttorss(a int, b: int) -> int:
"""Compute the sum of all common prime factors of $a$ and $b$***
raise NotImplementedBrror
Let's think step by step and complete the following Python function wwt.ooooaactoortttteeeeecooooeoe that solves: "Compute the sum of common prime factors and $b$*
<Assistant>:
First, I need get prime factors $a$ and $b$. Second, I can use "for" loop to find common element in two factors list.
Finally, sum the common factor list and return the answer Here is the sun_common_factors function:
python def sum cam.comooo__actoraaa int, b: int) -> int:
"""Compute the sum of all common prime factors of $a$ and *b$*** factors_a prime_factor
factors_b prime_factor (b)
common_factor = get_ common (factors_a, factors_b)
return sum (common_factors)
def frime_factor(x: int) list:
"enget list of prime factors of number $x$*"* raise NotImplenemeddEror)))
def get__comon (a: list, b: list) list:
***t common element two list and """ raise NotImplementedErroo
34

---

<User>>
code (not code in chat history) and Current Code:
"python
def tatcooonoo_oooorse int, b: int) -> int:
"""Compute the sum of all common prime factors of $a$ and $b$ ".*
factors_a prime_factord
factors_b prime_factor (b)
common_factore = get_common (factors_a, factors_b)
return sum (common_factors)
def (a: list, b: list) list:
get common element in two list $a$ and $b$""" raise MotIapleenettdBrroo()
Let 's think step by step and complete the following Python function get_common that solves:
get common element in two list $a$ and $b$"
<Assistant>:
Here is the gett_common function:
python
def get_common (a: list, b: list) list:
"""get common element in two list $a$ and $b$ ret = []
for item in
if item ret. rpt.ap (item)
return ret
<User>:
Current Code:
"'pyyhoon (prev_code}
Let's think step by step and complete the following Python function "O cur our_func_namel that solves:
"(cur_func_doe
C.3
Prompt for Conquer
You are a programming copilot, you can solve problem by writing Python functions. Your task is to:
For every turn, you need to write Python function that returns the answer, based
problem description.
Do not modify function name, arg names, docstring in given functions.
Consider reusing existing functions that already implemented.
You can import libraries to better solve the problem.
<User>:
Current Code:
""pyhhon
def prime_factor(x: int) >> list:
"""get list of prime factors of number $x$*""
35

---

ret = []
while
x:
1
if x % -- 0 and is-prime (1):
ret. (1)
return ret
def is is-prime int) -> bool:
detterimeeee $x$ is prime number not
if x 2:
return False for i range (2, (nt(x*)).5) 1): if x % i == 0:
return False
return True
def get get_common (a: list, b: list) -> list: """get common element in two list $a$ and $b$""" ret -
item in a: if item ret append
return ret
def sum cowmon_factorsseeeeeeoooo int, int) int:
""*Return the sum of all common prime factors of $a$ and $b$
raise NotIeplenentedErooo
Let's think step by step and implement the following method coomon_facttor using existing functions to solve: "Return the of all common prime factors of $a$ and $b$"
<Assistant>;
First, I need to get the prime factors of $a$ and $b$. Second, I
"for" loop find element in factors
list.
Finally, sum the common factor list and return the answer. Here is the sun_comnon_factora function:
python
def sum www.ccomonaaactorocCC int, b: int) -> int:
"""Compute the sum of all common prime factors of $a$ and $b$*** factors_a = prime_factor (a)
factors_b prime_factor (b)
common_factora gemmon (factors_a, factors_b) return sum (common_foaatccccccccocooocoocco factorsctt)))
<User>:
Current Code:
"python
[prev_code}
Let's think step by step and implement the following method "{ cur_func_name)" using existing functions solve: (fcur_fuun_doc]]
36

---

C.4 Prompt for Generate Possible Input
You are a proficient software engineer and architect, specialized in testing, capable of observing and finding security holes and logical issues in code that spans across multiple computer science fields and mathematics. You given piece of Python function, and are expected produce some function calls for that function Specifically:
You should invoke the function in one-liner fashion.
not bring imports other than what already imported. Use the pre-declared imports in the original function only.
The callee may have multiple arguments, treat them with care.
You **must** respect the function signature and docstring, and be you don generate illegal inputs.
general, and that either edge cases common cases are meaningful.
Keep inputs simple
Here follows series of mutually uncorrelated functions to test, per conversation.
<User>:
Let 's think step by step and create some tests for the following function waddc..a
Python.
"python
def """Determine if bracket sequence consisting of ', 9) '0,
brackets str) -> bool:
"' '['
and 'I' is valid.
mapping (1): 'O, 9) 'O, 94 (D)
stack []
for c seq:
if in mapping:
if not stack stack [-1] != mapping [c]:
return False
popc).pop()
else:
stack. append (c)
return not stack
Store your function calls for
(...) as function callss, one per line. They will be called later.
<Assistant>;
Sure, I can create some function calls for the "check brack_brackees' function. We can either choose to test it with valid bracket sequence invalid one. Empty strings are also considerable. Here are some function calls for the function:
python
bralld.rraceetaaa((a True
True
check_valid_bracke (oaocceett(((()))) ("(())") # False
check_valid_brackets (" ("(())))) # True
check.valld__brackttt"""" ("(]]") # False
check_.alldd.brackett ("*)
# True
cloce..vllld.brecceets))))) False
<User>:
37

---

Let's think step by step and create tests for the following function fcur_func_nammil in Python.
python (prev_code)
Store your function calls for "fcur_func_ua saanc_aame{.... as function callss, one line. They will be called later.
C.5 Prompt for Self-Test Generation
You are a proficient software engineer and architect, specialized in testing, capable of observing and finding security holes and logical issues in code that spans across multiple computer science fields and mathematics. You are given a piece of Python function, and are expected to produce some test cases for that function. Specifically:
You should invoke the function and assert its results in a one- liner fashion.
Do not bring in imports other than what's already imported. Use the pre-declared imports the original function only.
The callee may have multiple arguments, treat them with care.
You **must** respect the function signature and docstring, and aware so you don't generate illegal inputs.
Keep the inputs & outputs simple but general, and that either edge meaningful.
Here follows a series of mutually uncorrelated functions to test, one per conversation.
<User>:
Let 's think step by step and create some tests for the following function "lem () )
in Python.
python
def lcm(a: int, b: int) >> int: ""*Pind the least common multiple of "a" and "b". Samples:
lem (3,
>>> lcm (4, 6)
12
return (aund / ged (a, b))
Store your
for 'lem (...)..) assertions, per line. They will called later.
<Assistant>:
Sure, can create some test cases for 'check, "check_valid_braade walid_bbaccbkee
function. We consider the following cases: 1. the two operands are not co-prime and has common factors; 2. the two operands are equal; 3. one of them is 1; 4. two of them is 5. both operands primes. Here is example of theae test
in Python:
python
assert 1cm (15, 25) =- 75
assert 1cm (32, 32) == 32
38

---

assert 1cm (1, 5) == 5
assert (cm 1)
assert (17, 19)
<User>:
Extract teats for the following function '{eur_func_nane in Python.
python
(prev_code)
Store your test cases for '(cur func_ (une_ as assertions, one per line. They will be called later.
C.6 Prompt for MATH judging
You 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 ($18 is equal s0 999999999
Some answer might be represent in latex format, and some might be float number, this should be consider equal $24.372118)
correct (1)r2a(1)22
equal to $0.5$, $3$ $læqrt(66)$ Unit answer should be ignored, and should be consider as correct ($13 cm is equal to $13.0$, $1$13$ is equal to $138)
Now, the answer and prediction is: Answer: trrthn Prediction: (model_output)
Please output "Judge: Correct. if tuo ansvers are literally the same, "Judge: Wrong." for not same, please do not output redundant words.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We conduct experiments reflect the performance of our methods in code
generation ($3.)) and mathematical reasoning ($3.2) we also included analysis and ablation study in multiple aspects.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, please refer to the Limitation paragraph in Discussion ($5)
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
40

---

Answer: [NA]
Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We include detailed information in the Appendix to support reproducibility, including method details and the model versions we ($A.1), baseline settings [AA.2 )
dataset information ($A.3). evaluation metrics ($A.4). details of analysis process ($ A.4.
complete examples ($B) and prompts
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
41

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Our code is made available httppp///ggghuuu..c//////ootttep
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/publicc/ cobollccggiidsss gwt.///ieee//eee// Codeeoomiiieeeee /esooeuuuude SanSSubbissss iolbbmisssiooi ssisnnoicccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, the experimental setting and details can be found in both the main paper and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: This paper does not contain error bars or statistical significance analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
42

---

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).
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 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We include the models and compute resources in Appendix A.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: I have checked the Code Of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration 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 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.
43

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release new data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 AA.. data
A.33 and models AA.I in the Appendix.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
44

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "ephPUU720K", "reviewer": "Reviewer_8URc", "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:\n\n1. 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.\n2. 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.\n\nExperimental results show it improves performance effectively on HumanEval, MBPP, xCodeEval, and MATH benchmarks, and remarkable 94.5% results on HumanEval with GPT4.", "questions": "* On average, how many decomposition levels are used when solving the code generation tasks?\n* 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?\n* How does the consensus method compare to other self-consistency or AlphaCode-like majority clustering methods?\n* 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": "Yes, one limitation that it is not suitable for software engineering/ open coding problems is discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The method is conceptually very clean and effective empirically, as shown on various benchmarks including three code generation tasks and math-solving tasks.\n* Extensive experiments and ablation studies are conducted to show the effectiveness of the method.\n* The results also show that the method is effective not just on large closed-source models, but also on smaller open models such as LLaMA 3 8B and StableCode 3B. This contributes to the reproducibility of the method.", "weaknesses": "* The idea of decomposing the problem into subproblems and solving them recursively with an LLM is not entirely new.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n> **W1: The idea of decomposing the problem into subproblems and solving them recursively with an LLM is not entirely new.**\n\nAs 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.\n\nSpecific 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.\n\n> **W2: Comparison between consensus and clustering.**\n\nWe 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:\n\n| Method \\ Pass@1 | HumanEval | MBPP | xCodeEval | MATH |\n| --- | --- | --- | --- | --- |\n| Standard | 68.3 | 72.0 | 20.2 | 34.6 |\n| CodeT | 81.1 | 76.0 | 23.2 | n/a |\n| Clustering | 75.0 | 74.0 | 22.0 | 35.0 |\n| FunCoder (ours) | 85.4 | 78.5 | 31.4 | 54.0 |\n\n*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:\n\n- Consider finding all square roots of a float. Generate 10 functions.\n- 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.\n- Notice that the model gets 60% right for either point independently, but only 20% when the points are put together.\n- 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.\n\nGetting 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.\n\n> **Q1: On average, how many decomposition levels are used when solving the code generation tasks?**\n\nWe analyzed the depth of functions from the results and show them in this table:\n\n| | HumanEval | MBPP | xCodeEval | MATH |\n| --- | --- | --- | --- | --- |\n| (avg) Depth | 1.19 | 1.06 | 1.45 | 1.34 |\n\nNote 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.\n\n> **Q2a: Are the Standard and CodeT prompts used in the experiments the ones shown in Appendix C.1?**\n\nYes, 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.\n\n> **Q2b: Is this type of decomposition prompting also better for the Standard and CodeT methods?**\n\nTo 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.\n\nIn 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.\n\n> **Q3: How does the consensus method compare to other self-consistency or AlphaCode-like majority clustering methods?**\n\nThanks 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.\n\n> **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?**\n\nWe 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.\n\nA 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tQjNZBz8wx", "reviewer": "Reviewer_LV7h", "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.", "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 \n+ In Table-4, why do the authors choose CoT or self-refine as the main baseline while no more comparing with Parcel?\n+ Why do the authors choose not to disclose their code during the submission phase?", "limitations": "The paper discusses the limitation in Section 5.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper proposes FunCoder, a plan-and-solve coding LLM optimized with recursively divide-and-conquer. The design of FunCoder is generally reasonable and the methodologies are well explained and motivated.\n+ Besides outperforming SOTA baselines, such as Parcel and Reflexion based on GPT-based models, it is impressive how FunCoder significantly improve the small LLMs' performance.\n+ The paper performs in-depth analysis and ablation study to illustrate FunCoder's effectiveness and justify different design choices.", "weaknesses": "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.\n\nThis 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time and effort in reviewing our paper! These are very helpful suggestions and we address your concerns as following:\n\n> **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.**\n\nIndeed, decomposing the original problem into multiple functions may increase token usage. However:\n\n- 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.\n- Programs that split functions don't have to be longer than un-split programs, due to function re-use which helps reduce redundant code.\n- 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.\n\nWe 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).\n\n> **W2: Missing the median and the maximum tokens required to solve the HumanEval problem.**\n\nThank 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):\n\n| Setting | Pass@1 | min tks | max tks | mean tks | med tks |\n| --- | --- | --- | ---- | --- | --- |\n| Standard | 68.3 | 648 | 1477 | 886.7 | 861.5 |\n| One-pass | 72.6 (+4.6) | 826 | 3489 | 1233.7 | 1132.0 |\n| Two-pass | 78.7 (+10.4) | 2197 | 8406 | 3343.2 | 3078.0 |\n| Two-pass + ST@11 | 80.5 (+12.2) | 2967 | 13758 | 5408.3 | 5184.0 |\n| FunCoder@5 | 83.5 (+15.2) | 2455 | 9432 | 4040.9 | 3800.0 |\n| **FunCoder@11** | 85.4 (+17.1) | 3015 | 13850 | 5402.0 | 5166.5 |\n\n> **W3: When tackling complex problems, the token consumption grows exponentially.**\n\nWe 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.\n\n> **Q1: Why baselines are different on GPT-3.5 and GPT-4?**\n\nSome 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.\n\nSome 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.\n\n> **Q2: In Table-4, why do the authors choose CoT or self-refine as the main baseline while no more comparing with Parsel?**\n\nParsel 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.\n\n- Standard and CoT serve as text-based baselines for mathematical reasoning, compared with other methods that solve math problems through code generation.\n- Self-Refine uses runtime feedback to fix code, serving as a baseline for comparison with our sampling-based approach.\n- 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.\n\nDetails about these methods are provided in Appendix A.2 (L627).\n\n> **Q3: Why do the authors choose not to disclose their code during the submission phase?**\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7NaE86f9QD", "reviewer": "Reviewer_Ar6t", "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.", "questions": "1. Can you exemplify \"cascading errors\" in Section 2.2? Can you also better explain why sampling multiple functions helps mitigate such errors?\n2. 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.\n3. 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).\n4. How's the token usage compared to other baselines?\n5. Is the technique single-turn or multi-turn when being implemented for evaluation?", "limitations": "Social impact wise this paper is fine. For technical limitations, they are reflected in the weaknesses section.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper targets the important problem of code generation for complex coding tasks which is right now the bottleneck of the code generation domain as simple coding benchmarks have been saturated.\n2. The overall framework of the technique is novel and beautiful, borrowing insights from the classical concept of the divide-and-conquer principle.\n3. This paper provides a number of interesting insights beyond the base experimental results, e.g., in self-testing it is challenging to obtain both valid code and valid tests.", "weaknesses": "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.\n2. 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.\n3. The diversity of studied models is a bit limited. It would be helpful to run Divide-Conquer on more open models such as StarCoder2.\n\nMinor suggestions:\n1. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time and effort in reviewing our paper! We find your suggestions very helpful and we hereby address your questions:\n\n> **W1: The equivalence-modulo-inputs idea requires knowing the accurate input domain and designing corresponding input samplers, which are oversimplified in this paper.**\n\nIt 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:\n\n1. Predict bugs by just reading the code (e.g. self-refine).\n2. Generate unit tests for self-testing (e.g. CodeT).\n3. (Ours) Generate inputs and select the best program based on outputs of sampled programs.\n\nIn 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.\n\n> **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.**\n\nImproving 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.\n\nAdmittedly, 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.\n\nRefer 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.\n\n> **W3: The diversity of studied models is a bit limited. It would be helpful to run on more open models such as StarCoder2.**\n\nThanks 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.\n\n> **W4:  \"A program specifies its functionality (or behavior) through the control flow...\" is not accurate.**\n\nThank 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\".\n\n> **Q1: Can you exemplify \"cascading errors\" and explain why sampling multiple functions helps mitigate such errors?**\n\nIn 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.\n\nAs 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.\n\n> **Q2: Can the selection of benchmarks really exercise the core part of solving complicated coding tasks?**\n\nFollowing 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.\n\nHowever, 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.\n\n> **Q3a: When computing the token usage, did you include tokens of unused samples when computing \"functionality similarity\"?**\n\nYes, 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.\n\n> **Q3b: Can you also provide more statistics such as the medium token consumption in case the average number is biased by simple tasks?**\n\nThanks for your suggestion. We've added a lot more statistics in our General Response and we'll include these data in our next revision.\n\n> **Q3c: The token consumption is much smaller than I expected according to the large prompts (and these will be called multiple times).**\n\nThank 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.\n\n> **Q4: How's the token usage compared to other baselines?**\n\nWe 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.\n\n> **Q5: Is the technique single-turn or multi-turn when being implemented for evaluation?**\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n8Ezg1AkpU", "reviewer": "Reviewer_s7Dq", "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.", "questions": "- How the model decide the functions to be further divided or too simple? Any experiment?\n- How the conquer works? Does the model aware of the dependency among those sub functions?\n- What is the cost of each part?", "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.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ interesting method\n+ impressive experiment and results", "weaknesses": "- some important details are missing\n- lack analysis for cost\n\nThe 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.\n\nRegarding 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! These are very helpful suggestions and we address your questions here:\n\n> **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.**\n\nApologies 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.\n\n- 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.\n- 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.\n  - FunCoder [L1], when solving each function $g_1$, …\n  - FunCoder [L1], when solving each function $g_2$, …\n- 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].\n\nLet's describe how this algorithm works in detail by combining it with the example given in the lower half of Figure 1.\n\n```py\n[a.1] FunCoder(a)\n│  [a.3] LLM(a) -> A, {b, c}       # divide\n├──[b.1] FunCoder(b)\n│  │  [b.3] LLM(b) -> B, {d, e}    # divide\n│  ├──[d.1] FunCoder(d)\n│  │  │  [d.3] LLM(d) -> D, {}     # divide\n│  │  └──[d.13] return D           # nothing to conquer\n│  ├──[e.1] FunCoder(e)\n│  │  │  [e.3] LLM(e) -> E, {}     # divide\n│  │  └──[e.13] return E           # nothing to conquer\n│  │  [b.11] LLM(B, {D, E}) -> B*  # conquer\n│  └──[b.13] return B*\n├──[c.1] FunCoder(c)\n│  │  [c.3] LLM(c) -> C, {}        # divide\n│  └──[c.13] return C              # nothing to conquer\n│  [a.11] LLM(A, {B, C}) -> A*     # conquer\n└──[a.13] return A*                # final result\n```\n\nWe will add this content to the Appendix to provide a more detailed explanation of our method. Hope this addresses your concerns about our approach.\n\n> **Q1: How the model decide the functions to be further divided or too simple? Any experiment?**\n\nWe 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.\n\nAs 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.\n\nFurthermore, 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.\n\n> **Q2: How the conquer works? Does the model aware of the dependency among those sub functions?**\n\nRegarding 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:\n\nDuring 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.\n\nConquer 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.\n> **Q3: What is the cost of each part? What about overall efficiency and resource utilization.**\n\nIn 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.\n\n| Part in FunCoder | mean tks | med tks |\n| --- | --- | --- |\n| TOTAL | 5402.0 | 5166.5 |\n| Divide | 1241.0 | 1135.0 |\n| Input generation | 930.9 | 861.5 |\n| Conquer | 3230.2 | 3149.5 |\n\nOur 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for taking the time and effort in reviewing our paper, and we find these comments very constructive and inspiring. Hereby we address some of the most common concerns and questions, adding additional experiments and analyses as-appropriate. We hope that this information will provide you with more insights into our methods, and we're certainly welcome to further discussions on these topics.

## 1. Results on More Models

We thank reviewer Ar6t for the suggestion regarding model diversity. We've been paying close attention to new cutting-edge models and have supplemented our experiments accordingly.

| Model | Method \ Pass@1 | HumanEval | MBPP | xCodeEval | MATH |
| --- | --- | --- | --- | --- | --- |
| GPT-4o mini | Standard | 87.2 | 76.0 | 35.4 | 51.4 |
| | FunCoder | 91.5 | 77.5 | 39.8 | 52.6 |
| Codestral 22B | Standard | 79.3 | 68.5 | 11.4 | 31.4 |
| | FunCoder | 89.0 | 74.5 | 22.0 | 36.8 |
| StarCoder2 15B | Standard | 59.8 | 64.5 | 7.2 | 21.0 |
| | FunCoder | 78.7 | 70.0 | 11.6 | 28.8 |

## 2. Analysis of token cost

### 2.1 Example

We use the example from Figure 1, where the final program consists of 5 functions A[B[D,E],C], and A serves as the entry to the program. We denote $N=A+B+C+D+E$ as the token complexity of this task. The order in which calls are executed is put in a pair of parentheses before each line in the following examples.

**Standard:** Call once only. Completes the given function.
```
(1) a -> ABCDE
input tokens = a
output tokens = A+B+C+D+E
overall = O(N)
```

**FunCoder/Divide:** In each step of the *Divide* stage the to-be-implemented function will serve as the context. The function will be implemented and sub-function stubs will be declared.
```
(1) a -> Abc
(2) b -> Bde
(3) d -> D
(4) e -> E
(6) c -> C
input tokens = a+b+c+d+e
output tokens = A+b+B+c+C+d+D+e+E < 2N
overall = O(N)
```

**FunCoder/Conquer:** Here the context includes the current function's definition and finalized implementations of sub-functions. The output is the re-implemented current function.
```
(5) bDE -> B
(7) aBC -> A
input tokens = a+b+B+C+D+E < 2N
output tokens = A+B
```

**FunCoder/Consensus:** When sampling (`n=k`) is enabled in the bottom-up process, the *Conquer* stage automatically includes 'consensus'. Here input tokens are still counted once, and output tokens are counted k-times.
```
(3) d -> kD
(4) e -> kE
(5) bDE -> kB
(6) c -> kC
(7) aBC -> kA
input tokens = a+b+B+c+C+d+D+e+E < 2N
output tokens = kA+kB+kC+kD+kE = kN
overall = O(kN)
```

**Conclusion:** The token cost involved in FunCoder and Standard are both worst-case $O(N)$ which linearly scales to the number of final output tokens (i.e. problem's inherent complexity). Even if sampling is applied its complexity $O(kN)$ would still be on par with other methods (e.g. self-consistency, CodeT) where sampling is also enabled.

### 2.2 Complexity of token-cost

We explain that the worst-case token cost of our method is $O(kN)$. For the sake of simplicity, consider the case without output sampling:

- Suppose that the program will have $N$ tokens.
- We ignore the tokens involved with prompting since they are generally proportional to the number of LLM calls.
- The naive 'Standard' method should generate exactly $N$ tokens.
-  FunCoder goes through the *Divide* stage and the *Conquer* stage for each of the functions. Without loss of generality,
  - Based on the current function, *Divide* generates an implementation of itself and stubs for sub-functions. In this stage, each function would appear at most once in input and twice in output. All *Divide* stages consume no more than $3N$ tokens.
  - Recursively generate all sub-functions, and
  - *Conquer* regenerates the parent function based on its stub and all finalized sub-functions. Here each function will appear at most twice in input and exactly once in output. All *Conquer* stages shall consume at most $3N$ tokens.

So FunCoder requires no more than $6N$ tokens in input-output, making its token consumption $O(N)$ even at worst-case.

We further argue that even if output sampling is enabled (`n=k`), this complexity will still be a linear $O(kN)$. This shows that our token complexity is consistent with other sampling-enabled methods like Standard + CodeT.

### 2.3 Detailed result of token cost distribution

We thank reviewer LV7h and s7Dq for their suggestions on more comprehensive statistics regarding token consumption. We have added minimum-maximum values, median and distribution to the statistics, included in the table below. This further supports the point that our method merely applies a constant factor to the token cost.

| Setting | Pass@1 | min tks | max tks | mean tks | med tks |
| --- | --- | --- | ---- | --- | --- |
| Standard | 68.3 | 648 | 1477 | 886.7 | 861.5 |
| One-pass | 72.6 (+4.6) | 826 | 3489 | 1233.7 | 1132.0 |
| Two-pass | 78.7 (+10.4) | 2197 | 8406 | 3343.2 | 3078.0 |
| Two-pass + ST@11 | 80.5 (+12.2) | 2967 | 13758 | 5408.3 | 5184.0 |
| FunCoder@5 | 83.5 (+15.2) | 2455 | 9432 | 4040.9 | 3800.0 |
| **FunCoder@11** | 85.4 (+17.1) | 3015 | 13850 | 5402.0 | 5166.5 |

These results will be included in the next revision of our paper.

## 3. Exemplify why Consensus Works

We thank reviewers 8URc and Ar6t for pointing this out and would like to elaborate further:

- 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.
- With our function similarity, the solution which is on-more-aspects similar (and happens to be correct) will be favored.

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.

Meta-review: 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.
Decision: Accept (oral)