Research map / Large language models / Agents, code and math
Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FunCoder, a code generation framework that recursively divides problems into a tree of sub-functions and conquers them bottom-up, selecting each function via a functional consensus based on input-output agreement among sampled candidates.
Problem
LLMs struggle with code generation for complex requirements; plan-and-solve decomposition fixes plans upfront, multi-agent frameworks are heavy, and self-generated tests are often unreliable, so self-refinement can mislead.
Approach
Dynamic divide-and-conquer: the model introduces sub-function stubs during generation, forms a dependency tree, implements children first and composes them bottom-up; at each node, candidates are chosen by maximal pairwise behavioral similarity on LLM-generated inputs (functional consensus) instead of self-written assertions.
Key results
- With GPT-3.5, FunCoder reaches 85.4 Pass@1 on HumanEval (vs. 82.9 LDB, 68.3 standard) and 78.5 on MBPP.
- With GPT-4, FunCoder gets 94.5 on HumanEval and 78.2 on MATH, +6.0 over the strongest baseline Cumulative Reasoning (72.2).
- StableCode-3B with FunCoder reaches 81.0 on HumanEval, up from 61.0 standard prompting, and the paper reports it surpasses GPT-3.5 standard by 18.6%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Funcoder instead of the strongest reported baseline | GPT-3.5 · HumanEval | Pass@1: 82.9 -> 85.4 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-4 · HumanEval | Pass@1: 91.0 -> 94.5 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-3.5 · MBPP | Pass@1: 76.0 -> 78.5 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-4 · MBPP | Pass@1: 77.1 -> 79.5 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-3.5 · xCodeEval All | Pass@1: 23.2 -> 31.4 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-4 · xCodeEval All | Pass@1: 44.0 -> 48.6 | Helped |
| Use Funcoder instead of the strongest reported baseline | GPT-3.5 · MATH Overall | EM-gpt: 48.6 -> 54.0 | Helped |
| Use Funcoder instead of Cumulative Reasoning | GPT-4 · MATH Overall | EM-gpt: 72.2 -> 78.2 | Helped |
| Add divide-only decomposition (ablation) | Funcoder on GPT-3.5 · HumanEval | Pass@1: 68.3 -> 72.6 | Helped |
| Add bottom-up conquer after divide (ablation) | Funcoder on GPT-3.5 · HumanEval | Pass@1: 72.6 -> 78.7 | Helped |
| Replace consensus with Self-Test@11 (ablation) | Two-pass Funcoder on GPT-3.5 · HumanEval | Pass@1: 85.4 -> 80.5 | Hurt |
| Replace consensus with Clustering@11 (ablation) | Two-pass Funcoder on GPT-3.5 · HumanEval | Pass@1: 85.4 -> 75.0 | Hurt |
Surprising findings
- Self-generated unit tests are often wrong: for StableCode, roughly 30% of programs that passed self-tests failed system tests, and many self-test failures stemmed from wrong tests rather than wrong programs.
- Functional consensus picks the top candidate on the first attempt with Pass@1 close to Pass@11 upper bound, outperforming self-testing ranking in several settings.
Limitations
- Advantageous mainly on well-defined problems such as competitive programming and program-aided reasoning; less suited to open-ended software development.
- Token cost grows with the number of sampled candidates (O(kN)), roughly 5x standard prompting.
- Expert-level xCodeEval problems remain unsolved (about 3.4% at best).
Experimental setup
Datasets: HumanEval MBPP xCodeEval MATH
Benchmarks: HumanEval MBPP xCodeEval MATH
Metrics: Pass@1 EM-GPT (GPT-4 judged equivalence)
Baselines: Standard prompting CodeT Reflexion LDB MetaGPT Parsel Chain-of-Thought Program-of-Thought Self-Refine Cumulative Reasoning
Builds on: Parsel CodeT Reflexion Program-of-Thought Self-Refine
Closest papers by meaning
- CodeChain: Towards Modular Code Generation Through Chain of Self-revisions with Representative Sub-modules (ICLR 2024 · similarity 0.88)
- MaintainCoder: Maintainable Code Generation Under Dynamic Requirements (NeurIPS 2025 · similarity 0.87)
- AlphaVerus: Bootstrapping Formally Verified Code Generation through Self-Improving Translation and Treefinement (ICML 2025 · similarity 0.87)
- CodeChemist: Test-Time Scaling for Low-Resource Code Generation via Functional Knowledge Transfer (ICML 2026 · similarity 0.86)
- BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions (ICLR 2025 · similarity 0.86)
- Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.