M ap C oder: Multi-Agent Code Generation for Competitive Problem Solving (2024)

Abstract: Code synthesis, which requires a deep understanding of complex natural language (NL) problem descriptions, generation of code instructions for complex algorithms and data structures, and the successful execution of comprehensive unit tests, presents a significant challenge. Thus, while large language models (LLMs) demonstrate impressive proficiency in natural language processing (NLP), their performance in code generation tasks remains limited. In this paper, we introduce a new approach to code generation tasks leveraging the 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 LLMs ablations and analyses across eight challenging competitive problem-solving and program synthesis benchmarks—MapCoder showcases remarkable code generation capabilities, achieving their new state-of-the-art (pass@1) results—(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.

## introduction computer programming has emerged as an ubiquitous problem-solving tool that brings tremendous benefits to every aspects of our life @xcite @xcite . to maximize programmers' productivity, and enhance accessibility, automation in program synthesis is paramount. with the growth of llms, significant advancements have been made in program synthesis-driving us in an era where we can generate fully executable code, requiring no human intervention @xcite . despite llms' initial success and the scaling up of model size and data, many of these models still struggle to perform well on complex problemsolving tasks, especially in competitive programming problems @xcite . to mitigate this gap, in this paper, we introduce mapcoder: a multi-agent prompting based code generation approach that can seamlessly synthesize solutions for competition-level programming problems. competitive programming or competition-level code generation, often regarded as the pinnacle of problem-solving, is an challenging task. it requires a deep comprehension of nl problem descriptions, multi-step complex reasoning beyond mere memorization, excellence in algorithms and data structures, and the capability to generate substantial code that produces desired outputs aligned with comprehensive test cases @xcite . early approaches utilizing llms for code generation employ a direct prompting approach, where llms generate code directly from problem descriptions and sample i/o @xcite . recent methods like chain-of-thought @xcite advocates modular or pseudo code-based generation to enhance planning and reduce errors, while retrieval-based approaches such as @xcite leverage relevant problems and solutions to guide llms' code generations. however, gains in such approaches remains limited in such a complex task like code generation where llms' generated code often fails to pass the test cases and they do not feature bug-fixing schema @xcite . a promising solution to the above challenge is self-reflection @xcite , which iteratively evaluates the generated code against test cases, reflects on mistakes and 1 4912 figure 1 : overview of mapcoder (top). it starts with a retrieval agent that generates relevant examples itself, followed by planning, coding, and iterative debugging agents. our dynamic traversal (bottom) considers the confidence of the generated plans as their reward scores and leverages them to guide the code generation accordingly. modifies accordingly. however, such approaches have limitations too. firstly, while previous studies indicate that superior problem-solving capabilities are attained when using in-context exemplars @xcite @xcite or plans @xcite , these approaches, during both code generation and debugging, only leverage the problem description itself in a zero-shot manner. consequently, their gains can be limited. to confront the above challenge, we develop mapcoder augmenting the generation procedure with possible auxiliary supervision. we draw inspiration from human programmers, and how they use various signals/feedback while programming. the human problem-solving cycle involves recalling past solutions, planning, code writing, and debugging. mapcoder imitates these steps using llm agents -retrieval, planning, coding, and debugging. in contrast to relying on human annotated examples, or external code retrieval models, we empower our retrieval agent to autonomously retrieve relevant problems itself @xcite . moreover, we design a novel structured pipeline schema that intelligently cascades the llm agents and incorporates a dynamic iteration protocol to enhance the generation procedure at every step. figure 1 shows an overview of our approach, mapcoder. additionally, existing iterative self-reflection methods rely on extra test cases generated by llm agents (e.g., agentcoder @xcite , lats @xcite , self-reflection @xcite ) or external tools, compounding the challenges. test case generation is equally challenging as code generation @xcite , and incorrect test cases can lead to erroneous code. blindly editing code based on these test cases can undermine problem-solving capabilities. for instance, while self-reflection boosts gpt-4's performance on the humaneval dataset, it drops by 3% on the mbpp dataset @xcite . upon identification, to validate this, on the humaneval dataset itself, we replace their gpt-4 with chat-gpt, and see that model performance drops by 26.3%. therefore, our debugging agent performs unit tests and bug fixing using only the sample i/o, without any artifact-more plausible for real-world widespread adoption. we evaluate mapcoder on seven popular programming synthesis benchmarks including both basic programming like humaneval, mbpp and challenging competitive program-solving benchmarks like apps, codecontests and xcodeeval. with multiple different llms including chatgpt, gpt-4, and gemini pro, our approach significantly enhances their problem-solving capabilities -consistently achieving new sota performances, outperforming strong baselines like reflexion @xcite , and alphacodium @xcite . moreover, our method consistently delivers superior performance across various programming languages and varying problem difficulties. furthermore, with detailed ablation studies, we analyze mapcoder to provide more insights. 2 4913 2 related work program synthesis: program synthesis has a long standing history in ai systems @xcite . a large number of prior research attempted to address it via search/data flow approaches @xcite @xcite . lms, prior to llms, attempt to generate code by fine-tuning (i.e., training) neural language models @xcite @xcite @xcite @xcite , conversational intents or data flow features @xcite . large language models: various llms have been developed for code synthesis @xcite @xcite @xcite . recent open source llms include llama-2 @xcite , codellama-2 (roziere et al., 2023), mistral @xcite deepseek coder @xcite , motcoder @xcite that are capable of solving many basic programming tasks. prompting llms: as indicated in section 1, llm prompting can be summarized into three categories: retrieval @xcite @xcite ; planning @xcite ; debugging @xcite @xcite apart from the direct code generation approaches. in contrast, we combine all these paradigms and bridge their gaps (see ## mapcoder our goal is to develop a multi-agent code generation approach for competitive problem-solving. in order to do so, our framework, mapcoder, replicates the human programming cycle through four llm agents -retrieval, plan, code, and debug. we devise a pipeline sequence for mapcoder, intelligently cascading the agents in a structured way and enhancing each agent's capability by augmenting in-context learning signals from previous agents in the pipeline. however, not all the agent responses/outputs are equally useful. therefore, additionally, mapcoder features an adaptive agent traversal schema to interact among corresponding agents dynamically, iteratively enhancing the generated code by, for example, fixing bugs, while maximizing the usage of the llm agents. in this section, we first discuss the agents (as per the pipeline), their prompts, and interactions, followed by the dynamic agent traversal protocol in mapcoder towards code generation for competitive problem-solving. ## results in this section, we evaluate the code generation capabilities of our framework, mapcoder, for competitive problem solving. our experimental results are reported in ## ablations studies and analyses we present the ablation study of the mapcoder on humaneval dataset as the problems are simpler and easy to diagnose by us humans. ## conclusion and future work in this paper, we introduce mapcoder, a novel framework for effective code generation in complex problem-solving tasks, leveraging the multi-agent prompting capabilities of llms. mapcoder captures the complete problem-solving cycle by employing four agents -retrieval, planning, coding, and debugging -which dynamically interact to produce high-quality outputs. evaluation across major benchmarks, including basic and competitive programming datasets, demonstrates mapcoder's consistent outperformance of well-established baselines and sota approaches across various metrics. future work aims to extend this approach to other domains like question answering and mathematical reasoning, expanding its scope and impact.