Source-linked AI summary
MapCoder: Multi-Agent Code Generation for Competitive Problem Solving
Md. Ashraful Islam, Mohammed Eunus Ali, Md Rizwan Parvez
TL;DR
Complex code synthesis remains difficult for LLMs because competitive problems require deep problem understanding, sophisticated algorithms, substantial code, and reliable testing. MapCoder addresses this with four interacting agents for retrieval, planning, coding, and debugging, and reports consistent outperformance across major benchmarks and settings. Its main practical boundaries are high token and API usage and reliance on limited sample I/O for bug fixing.
Problem
LLMs remain limited on complex code-generation tasks, especially competitive programming problems requiring deep understanding, multi-step reasoning, algorithms, data structures, substantial code, and comprehensive testing.
Method
MapCoder uses retrieval, planning, coding, and debugging agents in a structured pipeline with adaptive traversal and plan-guided code generation.
Results
MapCoder consistently outperforms established baselines and state-of-the-art approaches across basic and competitive programming benchmarks, languages, and problem difficulties.
Takeaways & Limitations
MapCoder provides a multi-agent framework for code generation in complex problem-solving tasks, with demonstrated performance across major programming benchmarks.
Takeaways & Limitations
MapCoder generates many tokens and API calls, and its debugging currently relies on limited sample I/O that may not cover all possible test cases.
Abstract
from arXiv · showhide
Code synthesis, which requires a deep understanding of complex natural language problem descriptions, generation of code instructions for complex algorithms and data structures, and the successful execution of comprehensive unit tests, presents a significant challenge. While large language models (LLMs) demonstrate impressive proficiency in natural language processing, their performance in code generation tasks remains limited. In this paper, we introduce a new approach to code generation tasks leveraging multi-agent prompting that uniquely replicates the full cycle of program synthesis as observed in human developers. Our framework, MapCoder, consists of four LLM agents specifically designed to emulate the stages of this cycle: recalling relevant examples, planning, code generation, and debugging. After conducting thorough experiments, with multiple LLM ablations and analyses across eight challenging competitive problem-solving and program synthesis benchmarks, MapCoder showcases remarkable code generation capabilities, achieving new state-of-the-art results (pass@1) on HumanEval (93.9%), MBPP (83.1%), APPS (22.0%), CodeContests (28.5%), and xCodeEval (45.3%). Moreover, our method consistently delivers superior performance across various programming languages and varying problem difficulties. We open-source our framework at https://github.com/Md-Ashraful-Pramanik/MapCoder.
1 Introduction
MapCoder addresses the difficulty of competitive code generation by combining retrieval, planning, coding, and debugging agents in a structured multi-agent pipeline. Across programming benchmarks and models, it reports consistently strong performance against established prompting baselines.
- Competitive programming requires understanding natural-language descriptions, complex reasoning, algorithms, data structures, substantial code, and comprehensive test cases.
- Existing direct-prompting, planning, retrieval, and self-reflection approaches provide limited gains for complex code generation.
- MapCoder imitates the human programming cycle through retrieval, planning, coding, and debugging agents, while autonomously generating relevant examples and dynamically cascading agent interactions.
- MapCoder debugs generated code using sample input-output pairs rather than requiring additional test-case generation or external tools.
- MapCoder consistently achieves new state-of-the-art performance across basic and competitive programming benchmarks, models, programming languages, and problem difficulties.
2 Related Work
Prior program-synthesis research spans search, data-flow methods, neural code generation, and prompting strategies. MapCoder combines retrieval, planning, and debugging paradigms rather than treating them as separate approaches.
- Program Synthesis: Program synthesis has longstanding roots in AI, including search- and data-flow-based approaches.
- Program Synthesis: Earlier language-model approaches generated code through fine-tuning, conversational intents, or data-flow features.
- Prompting LLMs: LLM prompting includes retrieval, planning, and debugging approaches alongside direct code generation.
- Prompting LLMs: MapCoder combines these prompting paradigms and bridges their gaps.
3 MapCoder
MapCoder reproduces a human programming workflow with retrieval, planning, coding, and debugging agents connected by an adaptive traversal protocol. Plans receive confidence scores that determine coding order, while failed solutions are debugged and then revisited with alternate plans.
- MapCoder structures four LLM agents—retrieval, planning, coding, and debugging—to reproduce the human programming cycle.
- Retrieval Agent: The Retrieval Agent autonomously generates k similar problems, solutions, and metadata for downstream agents.
- Planning Agent: The Planning Agent uses retrieved examples and plans to produce step-by-step plans with confidence scores.
- Coding Agent: The Coding Agent translates one plan into code, tests it on sample I/Os, and forwards failing code to debugging.
- Debugging Agent: The Debugging Agent fixes bugs using sample I/O and planning information, repeating the process up to t times without additional test-case generation.
- Dynamic Traversal: Dynamic traversal sorts plans by confidence, tries the highest-scoring plan first, and returns to the Planning Agent after unsuccessful coding and debugging.
4 Experimental Setup
The experiments cover eight programming-synthesis benchmarks, compare MapCoder with several prompting baselines, and evaluate it across multiple foundation models using Pass@k.
- Datasets: Eight benchmark datasets span basic programming and complex competitive programming domains.The basic-programming set includes HumanEval, HumanEvalET, EvalPlus, MBPP, and MBPP-ET; the remaining benchmarks are competitive-programming datasets.
- Baselines: MapCoder is compared with Direct, Chain of Thought, Self-Planning, Analogical Reasoning, and Reflexion prompting approaches.The baselines differ in whether they use direct generation, stepwise reasoning, planning, retrieved analogies, or reflection.
- Foundation Models and Metric: Experiments use ChatGPT, GPT-4, Gemini Pro, and Mistral-7B-instruct as foundation models.The evaluated models include both proprietary and open-source LLMs.
- Evaluation Presentation: Table 2 reports Pass@1 results, marking state-of-the-art cells and gains over Direct Prompting.Some comparison results are collected from prior studies, including Jiang et al. (2023b), Shinn et al. (2023), and Dong et al. (2023b).
- Foundation Models and Metric: Pass@k counts a dataset evaluation as successful when at least one of k generated solutions is correct.The reported setup uses k = t = 5 for HumanEval and k = t = 3 for the other datasets.
5 Results
MapCoder achieves strong results across basic and competitive programming benchmarks, with gains over Direct prompting across models, languages, and difficulty levels. Its advantages are especially pronounced on challenging competitive-programming tasks, although gains diminish beyond mid-level xCodeEval difficulty.
- Overall Results: MapCoder achieves new state-of-the-art results across the evaluated competitive-programming benchmarks and substantially outperforms baselines.GPT-4 generally produces higher scales of performance than ChatGPT.
- Basic Code Generation: MapCoder improves Direct prompting on all four simple-programming datasets, with a maximum 88% gain on HumanEvalET by ChatGPT.On HumanEval with GPT-4, MapCoder’s Pass@1 surpasses Reflexion by approximately 3%.
- Competitive Problem Solving: 41.3%, 52.6%, and 132.8% improvements over Direct prompting occur on APPS, xCodeEval, and CodeContests for ChatGPT.For GPT-4, the corresponding improvements are 73.7%, 41.2%, and 135.1%.
- Competitive Problem Solving: 28.5% Pass@1 on CodeContest matches AlphaCodium’s 29% Pass@5 result, while MapCoder’s Pass@5 adds 12.8% improvement.The comparison is reported against a concurrent state-of-the-art model.
- Difficulty Levels: MapCoder excels across APPS introductory, interview, and competition categories, with the highest gain in competitive problem solving.The APPS results cover all three stated difficulty levels.
- Difficulty Levels: MapCoder performs across algorithm types and higher xCodeEval difficulty levels, but gains remain limited beyond mid-level difficulties greater than 1000.The xCodeEval tags represent algorithm types, while difficulty is an integer whose higher values indicate harder problems.
- Across Foundation Models: MapCoder shows performance gains over baselines with both Gemini Pro and Mistral-7B-instruct on simple and contest-level problems.The reported trend is consistent across HumanEval and CodeContest.
- Programming Languages: MapCoder maintains consistent proficiency across multiple programming languages on xCodeEval relative to baselines.The language comparison is presented in Figure 7.
6 Ablations Studies and Analyses
Ablations identify debugging and planning as the most influential MapCoder agents, while additional retrieval and debugging effort improves performance at a time cost. Error analysis shows reduced performance on difficult algorithmic domains.
- Impact of Different Agents: Removing any MapCoder agent decreases performance, with the Debugging Agent having the largest measured impact.Excluding debugging causes a 17.5% performance drop, and debugging ablations average a 24.83% drop across cases.
- Impact of Different Agents: The Planning Agent is the second most important component, producing a 16.7% average performance drop when excluded across cases.The ablation evaluates each agent’s contribution within the full pipeline.
- Qualitative Analysis: Plan-derived debugging fixes bugs by using the Planning Agent’s plan as guidance for the Debugging Agent.The qualitative example attributes the observed debugging behavior to the interaction between these two agents.
- Hyperparameter Analysis: Increasing the numbers of self-retrieved exemplars k and debugging attempts t improves performance at the expense of time.MapCoder’s two hyperparameters are k, the number of retrieved exemplars, and t, the number of debugging attempts.
- Input Analysis: Adding five HumanEval-ET sample I/Os yields a 1.5% performance gain on HumanEval.The augmentation addresses HumanEval’s average of 2.82 sample I/Os per problem.
- Error Analysis and Challenges: MapCoder has reduced performance on difficult xCodeEval problems in areas including Combinatorics, Constructive, Number Theory, Divide and Conquer, and Dynamic Programming.Manual inspection finds problem misinterpretation, inappropriate greedy or brute-force attempts, and inaccurate DP-table construction.
7 Conclusion and Future Work
MapCoder is presented as a multi-agent framework that captures the complete problem-solving cycle for complex code generation. Evaluation shows consistent outperformance of established baselines and state-of-the-art approaches, while future work targets broader domains.
- MapCoder employs retrieval, planning, coding, and debugging agents that dynamically interact to generate high-quality outputs.
- MapCoder is evaluated on major benchmarks spanning basic and competitive programming datasets.
- MapCoder consistently outperforms well-established baselines and state-of-the-art approaches across various metrics.
- Future work aims to extend MapCoder to question answering and mathematical reasoning.
8 Limitations
The paper identifies high token usage as a resource constraint and notes reliance on limited sample I/O pairs for bug fixing. It leaves token/API-call minimization and improved test-case generation for future work.
- MapCoder generates many tokens, which may challenge deployment in resource-constrained environments.The paper leaves minimizing tokens and API calls for future work.
- MapCoder relies on sample input-output pairs for bug fixing, but their limited number may not cover the full range of possible test cases.Improving additional test-case generation could reduce this reliance and improve robustness.
A Algorithm of MapCoder
The algorithm retrieves exemplars, generates and confidence-sorts plans, then codes and tests candidates, applying iterative debugging when sample tests fail. Prompt details for the four agents are provided in Figures 8–10.
- The algorithm retrieves k self-generated exemplars and creates one plan for each exemplar.
- Plans are sorted by confidence before the coding agent generates candidate code for each plan.
- Each candidate is tested on sample I/O, and failed candidates receive up to t debugging attempts using the test log.
- Detailed prompts for the Retrieval, Planning, Coding, and Debugging Agents are shown in Figures 8, 9, and 10.The Retrieval Agent prompt uses a specific instruction sequence described as a crucial design choice.
C Example Problem
The example materials document MapCoder’s four-agent interaction through prompts and responses. They include self-retrieval, confidence assessment, planning, coding, and debugging prompt components.
- Two complete examples show the prompts and responses for all four MapCoder agents.
- The self-retrieval agent is illustrated in Figure 8.
- The confidence-generation prompt asks whether a plan correctly solves a competitive programming problem in a specified language.
- The planning-generation prompt asks for a concrete plan using an example problem, its planning, and a relevant algorithm.
- The planning prompt for the original problem includes the problem description and the plan produced in the previous step.
- The planning agent is illustrated in Figure 9, while coding and debugging prompts are illustrated in Figure 10.