MapCoder: Multi-Agent Code Generation for Competitive Problem Solving

1 Introduction

• Competitive programming requires deep understanding of natural-language problems, multi-step reasoning, algorithm and data-structure expertise, and code that passes comprehensive tests.Source: §1 · p. 1
• Prior direct-prompting, planning, and retrieval approaches often yielded limited gains and lacked bug-fixing, while generation and debugging commonly used only the problem description in zero-shot form.Source: §1 · pp. 1–2
• MapCoder uses retrieval, planning, coding, and debugging agents in a structured cascade with dynamic iteration, and its retrieval agent finds relevant problems autonomously.The pipeline is inspired by how human programmers recall past solutions, plan, write code, and debug.Source: §1 · p. 2, Figure 1 · p. 2
• MapCoder’s debugging agent tests and fixes code using sample input/output rather than generated or external test cases.The introduction notes that generated tests can be incorrect; it cites a 3% HumanEval-to-MBPP performance drop for self-reflection and a 26.3% drop when replacing GPT-4 with ChatGPT on HumanEval.Source: §1 · p. 2
• Across seven programming-synthesis benchmarks, MapCoder consistently achieved new state-of-the-art performance, outperforming Reflexion (Shinn et al., 2023) and AlphaCodium (Ridnik et al., 2024).The authors also report superior performance across programming languages and problem difficulties.Source: §1 · p. 2

2 Related Work

• Program synthesis has a long history in AI, with prior approaches using search and data flow and pre-LLM neural models fine-tuned for code generation (Li et al., 2022a).Other pre-LLM approaches used conversational intents or data-flow features (Andreas et al., 2020; Yu et al., 2019).Source: §2 · p. 3
• Code-synthesis LLMs include recent open-source models such as Llama-2, CodeLlama-2, Mistral, Deepseek Coder, and MoTCoder, which can solve many basic programming tasks (Touvron et al., 2023; Roziere et al., 2023; Guo et al., 2024; Li et al., 2023).The related work also cites code-synthesis LLMs including Li et al. (2022b), Fried et al. (2022), Chen et al. (2021b), Austin et al. (2021), Nijkamp et al. (2022), and Allal et al. (2023).Source: §2 · p. 3
• LLM prompting includes retrieval, planning, and debugging; MapCoder combines these paradigms and mirrors the human programming cycle, using complete solutions rather than tree-traversal substeps (Yasunaga et al., 2023; Wei et al., 2022b; Ridnik et al., 2024; Yao et al., 2023).Tree-of-thoughts and cumulative reasoning use tree traversal to explore solution substeps, whereas MapCoder's agents work with different forms of complete solutions (Zhang et al., 2023).Source: §2 · p. 3

3.1 Retrieval Agent

• The Retrieval Agent uses the LLM itself to generate k user-defined similar problems, solutions, plans, code, and algorithm tutorials as auxiliary examples for later agents.Its prompt proceeds from generating problems and solutions, to step-by-step code that can be post-processed into plans, and then relevant algorithms and tutorials.Source: §3.1 · p. 3

3.2 Planning Agent

• The Planning Agent creates a separate target plan for each retrieved example and provides confidence scores, preserving diverse pathways and indicating each plan’s utility to later agents.Its prompt uses retrieved examples and their plans rather than combining all examples into one target plan.Source: §3.2 · pp. 3–4

3.3 Coding Agent

• The Coding Agent translates the original problem and one selected plan into code, tests it on sample I/O, and sends failing code to the Debugging Agent.If the initial code passes the sample tests, the agent predicts it is the final solution.Source: §3.3 · p. 4

3.4 Debugging Agent

• The Debugging Agent uses sample I/O and the Planning Agent’s plan to fix generated code, repeating the process up to t times without generating additional test cases.The paper states that plan-derived debugging significantly enhances bug fixing in MapCoder.Source: §3.4 · p. 4

3.5 Dynamic Agent Traversal

• MapCoder ranks plans by confidence, tests code from the highest-ranked plan, debugs failures up to t times, then tries the next plan for up to k iterations; its complexity is O(kt).The process returns code when it passes sample I/O tests or when debugging succeeds.Source: §3.5 · p. 4

4.1 Datasets

• The evaluation covers five basic-programming datasets and three competitive-programming datasets.The basic datasets are HumanEval, HumanEvalET, EvalPlus, MBPP, and MBPP-ET; the competitive datasets are APPS (150 problems), xCodeEval (106), and CodeContest (156). HumanEval and its extensions contain 164 problems, while MBPP and its extensions contain 397; for MBPP-ET, one test case per problem is randomly provided as sample I/O and excluded from hidden tests.Source: §4.1 · pp. 4–5

4.2 Baselines

• Comparisons include direct prompting, CoT (Wei et al., 2022b), self-planning (Jiang et al., 2023b), analogical reasoning (Yasunaga et al., 2023), Reflexion (Shinn et al., 2023), self-collaboration (Dong et al., 2023b), and AlphaCodium (Ridnik et al., 2024).The baselines span unguided generation, stepwise reasoning, planning, recalling analogous problems, feedback from unit tests, collaboration among LLM roles, and iterative refinement.Source: §4.2 · p. 5

4.3 Foundation Models, Evaluation Metric, k, and t

• The evaluated foundation models are ChatGPT (gpt-3.5-turbo-1106), GPT-4 (gpt-4-1106-preview), and Gemini Pro, alongside Mistral-7B-instruct.Success is measured with Pass@k, where at least one of k generated solutions must be correct; k = t = 5 for HumanEval and k = t = 3 for the other datasets.Source: §4.3 · pp. 5–6

5 Results

• MapCoder significantly outperforms all baselines and achieves new state-of-the-art results across all benchmarks; GPT-4 generally scores higher than ChatGPT.Source: §5 · p. 6

5.1 Performance on basic code generation

• MapCoder’s Pass@1 surpasses Reflexion by ∼3% on GPT-4 HumanEval and improves Direct prompting by up to 88% on ChatGPT HumanEvalET.AI-generated test cases cause 8% of HumanEval failures and 15% of MBPP failures; MapCoder does not depend on AI-generated test cases.Source: §5.1 · p. 6

5.2 Performance on competitive problem solving

• Against Direct prompting, MapCoder improves ChatGPT by 41.3% (APPS), 52.6% (xCodeEval), and 132.8% (CodeContests), and GPT-4 by 73.7%, 41.2%, and 135.1%, respectively.On CodeContest, its Pass@1 of 28.5% matches AlphaCodium’s Pass@5 of 29%; MapCoder’s Pass@5 adds a further 12.8% improvement. On APPS, MapCoder exceeds all baseline prompts’ Pass@1 scores for ChatGPT and GPT-4.Source: §5.2 · pp. 6–7, Table 3 · p. 7

5.3 Performance with Varying Difficulty Levels

• MapCoder excels in APPS Introductory, Interview, and Competition categories, with its highest gain in Competition; on xCodeEval it beats Direct across algorithm types and higher difficulties, but gains remain limited beyond mid-level (>1000).Source: §5.3 · p. 7, Figure 6 · p. 7, Figure 5 · p. 7

5.4 Performance Across Different LLMs

• With Gemini Pro and Mistral-7B-instruct, MapCoder shows gains over baseline approaches on both HumanEval and CodeContest.Source: §5.4 · p. 7, Table 4 · p. 8, Table 5 · p. 8

5.5 Performance Across Different Programming Languages

• On xCodeEval, MapCoder demonstrates consistent proficiency across programming languages relative to baselines.Source: §5.5 · p. 8, Figure 7 · p. 8

6 Ablations Studies and Analyses

• The ablation study uses HumanEval because its simpler problems are easier for humans to diagnose.Source: §6 · p. 8

6.1 Impact of Different Agents

• Turning off any agent lowers performance; excluding Debugging alone drops it 17.5% (24.83% average across all cases), while Planning has a 16.7% average drop.The study identifies Debugging as the most impactful agent and Planning as the second most important.Source: Table 6 · p. 8, §6.1 · p. 8

6.2 Qualitative Example

• A qualitative example shows the Debugging Agent fixing bugs by using the Planning Agent’s plan as a guide.The example compares Direct, CoT, Reflexion, and MapCoder prompting and is presented as evidence of the impact of Planning and Debugging.Source: §6.2 · p. 8

6.3 Impact of k and t

• Higher k and t yield higher pass@1 performance at the expense of time.The analysis varies the number of self-retrieved exemplars (k) and debugging attempts (t); Table 8 tracks API calls, tokens, and response time.Source: §6.3 · p. 8, Table 7 · p. 8, Table 8 · p. 9

6.4 Impact of Number of Sample I/Os

• Adding five HumanEval-ET sample I/Os to HumanEval’s average of 2.82 per problem yields a 1.5% performance gain.The augmented sample-I/O set was used because HumanEval provides a limited number of sample inputs and outputs.Source: §6.4 · p. 9

6.5 Error Analysis and Challenges

• On xCodeEval, MapCoder solves few problems in several difficult algorithmic categories, with DP errors including misinterpretation, greedy or brute-force attempts, and inaccurate DP tables.The cited manual inspection covered five DP problems; the analysis attributes these difficulties to gaps in precise problem understanding and concrete planning.Source: §6.5 · p. 9

• MapCoder employs interacting retrieval, planning, coding, and debugging agents to capture the complete problem-solving cycle.Source: §7 · p. 9
• MapCoder consistently outperforms well-established baselines and state-of-the-art approaches across various metrics.Source: §7 · p. 9
• Future work will extend MapCoder to domains such as question answering and mathematical reasoning.Source: §7 · p. 9

8 Limitations

• MapCoder generates many tokens, which may challenge resource-constrained settings; minimizing token and API-call use remains future work.The paper notes that k and t can be adjusted to trade performance gains for time and token consumption.Source: §8 · p. 9
• Bug fixing relies on a limited number of sample I/O pairs, which may not cover all test cases; better additional test generation could improve robustness.Source: §8 · p. 9
• Exploring open-source code-generation models such as CodeL-LaMa, LLaMa3, and Mixtral 8x7B could offer insights and potential improvements.Source: §8 · p. 9
• Machine-generated code should be run in a sandbox to mitigate potential risks.Source: §8 · p. 9

A Algorithm of MapCoder

• The Retrieval Agent first self-retrieves k exemplars for the subsequent workflow.The algorithm takes k as the number of self-retrieved exemplars.Source: A Algorithm of MapCoder · p. 12
• The Planning Agent creates a plan for each exemplar, and the plans are sorted by confidence.Source: A Algorithm of MapCoder · p. 12
• For each plan in confidence order, the Coding Agent generates code that is tested against sample input/output.Source: A Algorithm of MapCoder · p. 12
• If a test fails, the Debugging Agent uses the log to revise the code for up to t attempts, retesting after each attempt.A passing test returns the code immediately.Source: A Algorithm of MapCoder · p. 12
• If a candidate does not pass after debugging, the algorithm proceeds through the remaining plans and returns code after the candidates are exhausted.Source: A Algorithm of MapCoder · p. 12

B Details Promptings of MapCoder

• The appendix presents prompts for the Retrieval, Planning, Coding, and Debugging Agents in Figures 8, 9, and 10.It identifies the Retrieval Agent prompt’s specific instruction sequence as a crucial design choice.Source: B Details Promptings of MapCoder · p. 12

C Example Problem

• Two complete MapCoder examples provide all prompts and responses for the four agents via a link.The figures identify prompts for the self-retrieval, planning, and coding and debugging agents.Source: C Example Problem · p. 12, Figure 8 · p. 13, Figure 9 · p. 13