MARS: Multi-Specialist LLM Relay System for Competitive Programming

AI summary

Overview

Research area: Multi-agent large language model (LLM) systems for automated code generation, evaluated on competitive programming.

Technical level: Intermediate. The paper assumes familiarity with LLM prompting, retrieval-augmented generation (RAG), pass-rate evaluation, and the structure of competitive programming benchmarks, but the system architecture is described in plain procedural terms.

Scope: The paper introduces MARS, a prompt-only relay of topic-specialized LLM agents grounded by retrieval over an algorithm-theory corpus, and measures it on the CodeContests test split against direct prompting, retrieval baselines, ensemble and relay baselines, CodeSIM, and PairCoder.

What This Paper Is About

Existing multi-agent pipelines for competitive programming split work into generic planner, coder, and debugger roles and expect the backbone model to supply all algorithmic knowledge on its own. The authors argue this leaves the crucial ingredient — knowing which algorithmic technique applies — to chance, and that no prior system ties agent specialization to the topic structure of the problem or grounds each agent in a topical knowledge corpus. MARS addresses this by making each agent a single-topic expert (dynamic programming, graphs, strings, geometry, and so on) whose context is retrieved from an algorithm-theory corpus, then relaying one shared draft through a small, task-matched team with public-test execution as feedback at every step.

Key Contributions

1. A topic-aligned multi-agent relay. MARS replaces the stage-aligned planner-coder-debugger decomposition with agents that are each a single-domain expert, grounded by RAG over an algorithmic theory corpus (cp-algorithms, encoded with Jina Embeddings v2). The paper draws a contrast with retrieval systems such as REDCODER, DocPrompting, and RepoCoder, which retrieve over code, API documentation, or a codebase rather than over distinct algorithmic-theory topics.

2. Self-reported topical team formation. Every specialist in a pool of eleven self-assesses against the shared corpus filtered by its own tags, returning an in-scope flag, a relevance flag, and a confidence score. Up to three matches are shortlisted, and the starter is elected by a separate can-start probe; rarest specialists fire only on tag-matched tasks.

3. In-loop public-test execution at every relay turn. Each turn issues two LLM calls: a code-generation call, then a run of the draft against public examples in ExecEval, then a self-check and handoff call that returns keep-code, repair-code, or no-change with structured handoff fields. A repair is accepted only if it compiles and does not reduce the number of passing public tests relative to that turn's draft — a deterministic gate using observable execution signal rather than self-reported confidence.

4. A bounded, cheap protocol. The relay is budget-bounded to at most three unique specialists and eight steps, stops on an explicit stop signal, exhaustion of unused selected specialists, the step budget, or a no-progress cutoff (reroute at a streak of two, stop at three). A post-relay sanitization pass runs on every candidate, and an infrastructure-fixer is invoked only when boilerplate-level failures (I/O wiring, includes, type widths) are detected.

Main Findings

• Headline result on CodeContests with Gemma 4: MARS reaches 0.624 ± 0.006 pass rate at 2.3 recorded pipeline stages per task, which the paper reports as +14.4 percentage points over direct prompting. Table 1 lists the same run as 0.62 ± 0.01, at 244.3 ± 154.4 seconds, 40.3 ± 8.1 thousand tokens, and 16.6 ± 1.3 calls per task, averaged across 3 runs.
• Gap to CodeSIM: CodeSIM reaches 0.731 ± 0.009 (listed as 0.73 ± 0.01 in Table 1, at 817.5 ± 1358.5 seconds). MARS closes most of that gap at 3.3× lower wall-clock cost and ~7× smaller standard deviation in per-task token spend.
• Baseline ordering: MARS improves over Direct by +0.144, over Single-RAG by +0.095, and over the Parallel ensemble baseline by +0.060. Table 1 pass rates are Direct 0.48 ± 0.02, Single-RAG 0.53 ± 0.01, Parallel ensemble 0.56 ± 0.00, and Base relay 0.55 ± 0.00.
• Where the gains come from: Single-RAG plateaus at 0.529 because a single specialist with no test signal cannot recover from algorithmic missteps, and the Parallel ensemble pays 360.9 s per task on isolated candidates reconciled only at merge time. MARS opens a +0.14 gap on Hard tasks, where prompt-only baselines hover near 0.18–0.26.
• Difficulty tiers (Easy n=56, Medium n=39, Hard n=70): Scores stay near ceiling on Easy (0.80–0.93). MARS beats Direct on Medium (0.72 vs. 0.59) and more than doubles it on Hard (0.40 vs. 0.18). CodeSIM leads on every tier, using up to 45 debug iterations per Hard task.
• Routing concentrates: Team selection clusters on Mathematics, Constructive Algorithms, Data Structures, and Dynamic Programming. Base relay and MARS share a deterministic assessor and coincide in team distributions; the Parallel ensemble's earlier, less selective prompt admits more borderline specialists (Brute Force, Graphs) without improving accuracy.
• Other backbones: MARS has the highest pass rate of the three methods on every backbone — Qwen3.5-27B, C++17: MARS 0.297 ± 0.012, Single-RAG 0.264 ± 0.004, Direct 0.192 ± 0.018; GPT-5.4-mini, C++17: MARS 0.503 ± 0.043, Single-RAG 0.364 ± 0.024, Direct 0.149 ± 0.019. MARS beats Single-RAG by 9.5 points on Gemma 4, 3.3 on Qwen3.5-27B, and 13.9 on GPT-5.4-mini.
• Python transfer: On Python (PyPy 3) with Gemma 4, MARS reaches 0.622 ± 0.015 against Direct's 0.485 ± 0.000 (+13.7 points); both match their C++17 counterparts within uncertainty, though Python is slower (307.6 vs. 244.3 s).
• PairCoder comparison: The adapted Navigator/Driver MAS reaches 0.705 ± 0.009, 8.3 points above MARS at 1.4× the wall-clock cost (426.7 ± 451.7 s). Its plan clustering uses a proprietary embedding model (text-embedding-3-large), and around 11% of the 165 tasks ended in a truncated completion counted as failures.
• Ablations: Removing RAG grounding alone costs 2.0 points (0.604 ± 0.007). Generalists without RAG are 0.9 points below MARS within one standard deviation, but take 31% longer (319.8 ± 245.1 vs. 244.3 ± 154.4 s) and use more calls (17.3 ± 1.3 vs. 16.6 ± 1.3); because retrieval also changes, this row does not isolate specialization. The earlier Base relay (0.552 ± 0.000) and Parallel manager (0.564 ± 0.000) trail MARS by 7.2 and 6.0 points.
• Relay behaviour: Teams contain one, two, or three agents on 1.8%, 15.8%, and 82.4% of task-runs; an average of 1.35 specialists change the code. The 2.3 recorded stages include the final sanitizer/fixer record and therefore measure pipeline-history depth, not specialist turns. The gate reverted 4.4 ± 0.9% of 697 self-check decisions.
• Decision breakdown (Appendix D, 697 decisions): 38.4 ± 1.0% accepted a repair, 55.4 ± 1.4% kept the draft unchanged, 4.4 ± 0.9% proposed a repair the gate rejected and reverted, and 1.7 ± 0.8% were compile failures the specialist did not repair.
• Multi-topic vs. single-topic: 88% of tasks are multi-topic, needing no reconciliation because specialists edit one shared draft sequentially. Pass rate is 0.612 ± 0.010 on multi-topic and 0.719 ± 0.030 on single-topic tasks.
• Infrastructure-fixer is nearly inert: It produced a substantive edit in a single task (≈0.2% of task-runs), so the headline 0.624 is independent of it; in the ablation without RAG it edited ≈1.2% of task-runs. The only failing task it edited stayed failing.
• Worked example: On Codeforces problem 1620_B "Triangles on a Rectangle", MARS selects MathematicsAgent, GeometryAgent, and ConstructiveAlgorithmsAgent; the first draft fails the public sample because rectangle height and width are swapped for two sides, and the same specialist repairs it after seeing the report.

Methodology in Plain English

The system starts with a pool of eleven specialist agents, each defined by a topic description and a tag set. Given a problem, every specialist retrieves topic-matched context from a shared corpus of algorithm theory and answers two questions: does this problem match my expertise, and should I start the relay? The harness shortlists up to three matches by tag overlap, retrieval coverage, confidence, and retrieval quality, then elects a starter with a separate probe that must name one narrow first sub-problem and one concrete first step.

The chosen team then relays a single shared C++17 program. Each turn has two model calls. The first writes a draft from the current code, the assigned subtask, the starter contract, a compact summary of the previous relay state, and retrieved context. That draft is executed against the public examples in a sandbox. The second call sees the report and decides to keep the code, repair it, or make no change, while filling in structured handoff fields (completed scope, remaining scope, known risks, an explicit instruction for the next agent). A repair is rerun on the public examples and accepted only if it compiles and does not reduce the passing public tests; otherwise the draft is restored. The relay ends on an explicit stop signal, when no unused selected specialist remains, at the eight-step budget, or at the no-progress cutoff. Afterwards the code is sanitized, and a fixer touch‑up runs only for boilerplate-level failures.

Evaluation uses 165 tasks from the CodeContests test split with instruction-tuned Gemma 4 (gemma-4-31B-it), temperature 0.0, top-p 0.95, and a 4096-token budget. Transfer runs follow each model's and method's recorded API settings. All Table 1 systems use Gemma 4, temperature 0.0, and a 4096-token budget; MARS, the Parallel ensemble, Base relay, and CodeSIM use top-p 0.95 while the logged Direct and Single-RAG runs use 1.0. CodeSIM's open-source harness was adapted to the same 165 tasks; its published GPT-4 result uses a 156-task subset and is stated as not directly comparable.

Why This Matters

Impact on research. The paper shifts the axis of multi-agent design from generic role decomposition (planner, coder, debugger) to topical specialization, and it does so without fine-tuning — the framework is prompt-only. It also supplies a concrete, reproducible cost-per-accuracy comparison on a standard benchmark, including a within-paper RAG ablation, per-tier difficulty breakdowns, and relay decision statistics, and it documents which competing systems could not be ported and why (LDB, LPW, MapCoder, MaintainCoder, Xolver). As a scale reference, Xolver's LiveCodeBench protocol averages over 32 inference runs, which for 165 tasks would be 5,280 multi-agent executions per model, and the authors' own CodeSIM rerun averages ≈817 s per task.

Real-world applications (as suggested by the setting, not by deployments reported in the paper):

• Automated assistance for contest and interview-style algorithmic problem solving, where the technique choice matters more than boilerplate.
• Sandboxed code-generation tooling that can self-check against visible examples before a human reviews a candidate.
• Portfolio-style routing in developer assistants that pick a domain expert module rather than a single general-purpose prompt.
• Building low-cost verification loops into code generation pipelines, since public-test execution is deterministic and cheaper than extra model calls.

Industry relevance. The reported economics are the selling point: 3.3× lower wall-clock cost than CodeSIM at 0.624 vs. 0.731, plus markedly lower variance in per-task token spend (reported as ~7× smaller standard deviation), which matters for budgeting inference. The paper also shows the ordering Direct < Single-RAG < MARS holds on three backbones, including a small proprietary model (GPT-5.4-mini) and an open-weight model (Qwen3.5-27B), suggesting the recipe is not tied to one vendor. The counterpoint is that PairCoder, a heavier multi-plan search system, still reaches 0.705 ± 0.009 in Python.

Future Directions

• Cross-specialist comparison. The local gate rejects only same-turn public-test regressions; it misses hidden tests and comparisons between specialists. A better-accepted option would let later specialists challenge earlier code under the same execution-based evidence.
• Isolating the contribution of each component. Base relay and MARS share a subtask graph and starter contract, so the jump from 0.552 to 0.624 mixes public-test self-check, subtask tracking, and final infrastructure handling; the paper states this comparison does not isolate the contribution of each change. Generalists-without-RAG similarly trades both specialization and retrieval at once.
• Broader language and corpus coverage. Evaluation covers 165 CodeContests tasks, three backbones, two languages, one corpus, and Codeforces tags. Python reuses the same corpus and index; further languages would need their own prompts, extraction, sandbox, and infrastructure. Transfer beyond C++17 and Python remains untested.
• Porting remaining baselines. CodeSIM is the only stage-aligned comparison and PairCoder remains Python-only; the appendices list concrete obstacles for LDB, LPW, MapCoder, MaintainCoder, and Xolver, each of which would need provider adaptation, response-parsing validation, and token-budget alignment.

Target Audience

Researchers and engineers working on LLM-based code generation, multi-agent orchestration, and retrieval-augmented generation will get the most from this paper, particularly those interested in benchmark design and honest cost accounting. Practitioners building coding assistants who need a concrete comparison of relay, ensemble, and single-specialist architectures will find the ablation and routing statistics directly useful. Readers need working familiarity with pass-rate evaluation on competitive programming datasets and with agent prompting patterns; the algorithmic content of the benchmark problems themselves is not the focus.

Authors’ abstract

Large Language Models excel at code generation, yet competitive programming exposes a persistent failure mode: existing multi-agent pipelines distribute work over generic planner, coder, and debugger roles and delegate the choice of algorithmic technique to the backbone alone. We present MARS (Multi-Agent Relay of Specialized LLMs), a prompt-only framework in which each agent is a topic specialist---dynamic programming, graphs, strings, geometry, and so on---grounded by retrieval-augmented generation over an algorithm-theory corpus. Given a problem, retrieval selects a small team of relevant specialists; a starter writes an initial C++17 solution, and each subsequent turn runs the candidate against public examples in a sandbox, lets the active specialist keep, repair, or hand off the draft, and forwards a structured packet to the next specialist. A single infrastructure-fixer pass normalizes boilerplate at the end. On the CodeContests test split with Gemma 4, MARS reaches $0.624 \pm 0.006$ pass rate at $2.3$ recorded pipeline stages per task ($+14.4$ percentage points over direct prompting), closing most of the gap to CodeSIM ($0.731$) at $3.3{\times}$ lower wall-clock cost and substantially smaller variance in per-task token spend. The source code is available on GitHub: https://github.com/fckand/mars.