MARS: Multi-Specialist LLM Relay System for Competitive Programming
Andrei Mikhailov, Mikhail Burtsev, Alsu Sagirova
EMNLP 2026
cs.AI, cs.MA, cs.PL
2026-08-25
MARS relays up to three algorithm specialists over one C++17 draft. On Gemma 4 CodeContests (165), pass rate is 0.624, +14.4 pp vs direct, 3.3× lower wall-clock than CodeSIM.
Competitive programming is a harsh stress test for code LLMs: sparse specs, hidden tests, and problems that mix graphs, DP, and constructive tricks in one statement. Existing multi-agent pipelines still cut roles by stage (planner, coder, debugger) and leave the choice of algorithm to the backbone. MapCoder and CodeSIM treat contest tasks as generic code generation. Nothing in the team structure says "this is a shortest-path problem" versus "this is interval DP."
MARS changes the cut from stage to topic. Each agent owns one algorithmic area, retrieves from that slice of theory, and edits a single shared draft.
A pool of eleven specialists, each with a topic blurb and tags, self-assesses against the cp-algorithms corpus filtered by its own tags: in-scope, relevant, confidence. Up to three matches are shortlisted; a separate can-start probe picks the starter. Retrieval uses Jina Embeddings v2.
Each turn is two LLM calls. The first writes a draft from current code, the assigned subtask, the starter contract, a compact prior-state summary, and RAG context. The draft runs on public examples in ExecEval. The second call sees the report and returns keep, repair, or no-change plus structured handoff fields. A repair is rerun; if it fails to compile or passes fewer public tests than that turn's draft, the gate restores the draft. Confidence scores enter only at team selection. The keep/repair decision is execution, not self-report.
The relay is budgeted: at most three unique specialists and eight steps. It stops on an explicit stop signal, when no unused selected specialist remains, at the step cap, or after a no-progress cutoff (reroute at two, stop at three). An infrastructure-fixer runs only when boilerplate fails (I/O wiring, includes, integer width). Prompts are frozen. No fine-tuning.
Baselines are matched. Direct is one call. Single-RAG keeps the top-scoring specialist. Parallel ensemble merges independent specialist candidates. Base relay keeps teaming and the shared draft but drops public-test self-check, subtask tracking, and the fixer. CodeSIM is rerun from its open harness on the same 165 tasks and the same Gemma 4.
The split is 165 CodeContests test tasks. The main backbone is instruction-tuned Gemma 4, temperature 0, 4096-token budget. Figures are means over three runs.
| Method | Pass rate | Sec/task | Tokens k | Calls |
| Direct | 0.48 ± 0.02 | 34.9 | 1.8 | 1.0 |
| Single-RAG | 0.53 ± 0.01 | 59.8 | 25.0 | 12.0 |
| Parallel ensemble | 0.56 ± 0.00 | 360.9 | 29.8 | 17.6 |
| Base relay | 0.55 ± 0.00 | 191.6 | 34.1 | 17.1 |
| MARS | 0.624 ± 0.006 | 244.3 | 40.3 | 16.6 |
| CodeSIM (rerun) | 0.731 ± 0.009 | 817.5 | 32.2 | 10.2 |
That is +14.4 points over Direct, +6.0 over Parallel, +7.2 over Base relay. On Hard (n=70) MARS is about 0.40 against Direct's 0.18; Medium 0.72 vs 0.59; Easy sits in the 0.80–0.93 band for everyone. CodeSIM leads every tier, with up to 45 debug iterations on Hard, at 3.3× the wall-clock and about 7× the per-task token standard deviation.
The ordering Direct < Single-RAG < MARS holds on other backbones: Qwen3.5-27B 0.192 / 0.264 / 0.297, GPT-5.4-mini 0.149 / 0.364 / 0.503. On Python (PyPy 3) MARS is 0.622 against Direct 0.485, matching the C++17 numbers within uncertainty. PairCoder reaches 0.705 in Python at about 1.4× the wall-clock; its plan clustering still uses a proprietary embedding.
Ablations tell a sharper story than the specialist branding. Dropping RAG costs 2.0 points (0.604). Generalists with no RAG sit at 0.615, inside one standard deviation of full MARS, but slower (319.8 s vs 244.3 s). Teams hit three agents on 82.4% of task-runs; only 1.35 specialists actually change the code. The reported 2.3 stages also count the final sanitizer record. Multi-topic tasks are 88% of the split (pass 0.612) versus 0.719 on single-topic. The fixer edited one task (about 0.2% of task-runs), so 0.624 does not depend on it. Of 697 self-check decisions, 38.4% accepted a repair, 55.4% kept the draft, 4.4% were reverted by the gate.
If you are building a contest or tightly verified code agent, the portable pieces are public tests inside every turn and a local rerun before accepting a repair. Personality-style extra roles are not. Single-RAG plateaus at 0.529: one specialist, no test signal, no recovery from an algorithmic miss. Parallel spends 360.9 s per task and still loses to a test-gated relay.
Do not over-read the specialist story. Generalists without RAG lose only 0.9 points. Protocol and execution feedback do more work than "this one is the DP expert." Against CodeSIM and PairCoder this is the lighter prompt-only option that closes most of the gap without matching the heavy-search systems. It is usable on Gemma 4. On Qwen3.5-27B the absolute pass rate is still 0.297; a weak backbone is not rescued by topical routing.
The authors are explicit. Coverage is 165 tasks, three backbones, two languages, one corpus, Codeforces tags. Python reuses the same index; further languages need their own prompts, extraction, sandbox, and infrastructure. The local gate only rejects same-turn public-test regressions. It does not see hidden tests and does not compare specialists against each other. Generated code needs a sandbox.
The comparison set is uneven. CodeSIM is the only stage-aligned rerun; PairCoder is Python-only; MapCoder, LDB, and Xolver stay out of the main table for language or budget reasons. The "generalist" ablation also turns RAG off, so it does not isolate specialization from retrieval. Public examples sit inside the training loop. There is a real risk of polishing to visible tests and still failing hidden ones; the paper does not report public-pass versus hidden-pass separately.