Adaptive Knowledge Routing for Complex Reasoning in LLMs¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/fckand/mars
Area: LLM Reasoning
Keywords: Large Language Models, Competitive Programming, Multi-Agent Relay Systems, Retrieval-Augmented Generation, Dynamic Specialist Routing
TL;DR¶
This paper proposes MARS (Multi-Agent Relay of Specialized LLMs), a prompt-only framework replacing stage-aligned planner-coder-debugger roles with topic specialists grounded by algorithmic-theory RAG, achieving a 0.624 pass rate on CodeContests with 3.3× lower wall-clock latency than heavy-search baselines.
Background & Motivation¶
Large Language Models (LLMs) have achieved impressive milestones in everyday software engineering and boilerplate code generation, yet competitive programming continues to expose critical structural vulnerabilities in automated systems. Contest tasks present an unforgiving testbed: they provide sparse or absent verification signals during inference, enforce strict runtime and memory budgets, and demand sophisticated combinations of deep theoretical insights—spanning dynamic programming, graph theory, computational geometry, number theory, and combinatorics. The prevailing paradigm in multi-agent systems (MAS) addresses software tasks by decomposing workflows into generic developmental stages, assigning distinct agents to roles such as Planner, Coder, and Debugger. However, this decomposition operates under the unverified assumption that generic pre-training enables deep algorithmic specialization to emerge spontaneously across all subdomains.
The core tension in this stage-aligned decomposition lies in its treatment of agent roles as content-agnostic abstractions rather than vehicles of concrete domain mastery. When algorithmic choice is delegated entirely to an unguided backbone, the pipeline frequently adopts fundamentally flawed algorithmic paradigms at the planning stage and subsequently degenerates into superficial, trial-and-error patching during the debugging phase. Meanwhile, conventional retrieval-augmented generation (RAG) techniques for code focus almost exclusively on syntax-level documentation, concrete API signatures, or local repository context, providing virtually no grounding in abstract mathematical properties, invariant proofs, or algorithm design templates. Furthermore, parallel ensemble approaches that merge disparate candidate solutions impose prohibitive latency and token costs while struggling to reconcile conflicting program architectures, whereas simulation-heavy planning-debugging loops (such as CodeSIM) burn immense inference budgets in open-ended iteration.
This paper tackles the challenge from a distinct conceptual angle: because competitive programming is fundamentally governed by the composition of distinct theoretical concepts, multi-agent systems should be organized along topical knowledge boundaries rather than generic software lifecycle stages. The authors introduce MARS (Multi-Agent Relay of Specialized LLMs), where each agent operates as a focused algorithmic specialist grounded in a dedicated slice of an algorithm-theory corpus (cp-algorithms). Core idea: transition multi-agent programming from stage-driven pipelines to a topic-aligned relay of theory-grounded specialists, combining self-assessed dynamic team recruitment, in-loop execution self-checks with deterministic regression gates, and single-draft sequential refinement.
Method¶
Overall Architecture¶
The MARS framework coordinates a self-organized team of topic-specialized agents that iteratively evolves a single shared C++17 solution. The pipeline unfolds across four sequential phases: specialist pool self-assessment, starter contract negotiation, an execution-gated intra-step relay loop, and lightweight infrastructure fixing. First, all specialists in the pool evaluate the problem against their respective theory corpus slices, allowing the system to shortlist a compact team of at most three relevant agents. Next, a targeted probe selects the starter agent and establishes an immutable starter contract governing early-stage scope. The active specialist then writes a draft, executes it against public test cases in an isolated ExecEval sandbox, performs an execution-aware self-check to repair or retain the draft under a deterministic regression gate, and forwards a structured handoff packet to the next specialist. Finally, once relay termination criteria are met, an infrastructure fixer repairs template-level compilation and I/O wiring without perturbing core algorithmic logic.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}}%%
flowchart TD
A["Contest Problem Specification<br/>(Natural Language + Public Examples)"] --> B["Stage 1: Algorithmic Specialist Pool & Self-Assessment<br/>11 topic specialists retrieve corpus slices and score relevance"]
B --> C["Stage 2: Starter Probe & Immutable Starter Contract<br/>Elect starter agent and define bounded first-step scope"]
C --> D["Stage 3: Single-Draft Execution-Gated Relay Loop<br/>In-loop public-test execution with deterministic rollback gate"]
D -->|Stop signal / Budget limit / No-progress cutoff| E["Stage 4: Post-Relay Infrastructure & Template Normalization<br/>Intervenes strictly on I/O boilerplate and header failures"]
E --> F["Final Verified C++17 Solution"]
Key Designs¶
1. Algorithmic Specialist Pool & Self-Assessment: Grounding Heterogeneous Agents in Theory Slices
To address the lack of domain-specific algorithmic grounding in generic roles, MARS constructs a pool of eleven specialized agents covering core competitive programming domains (including Dynamic Programming, Graph Theory, Computational Geometry, Data Structures, Mathematics, and Constructive Algorithms). Each specialist is indexed to a distinct topical slice of the cp-algorithms theory repository encoded with Jina Embeddings v2. Upon receiving a task, the framework bypasses centralized hard-coded dispatching; instead, every candidate specialist performs a local retrieval step over its corpus slice and answers a structured self-assessment probe. The specialist outputs boolean indicators for domain match (can_solve) and relevance (is_relevant_to_specialty), accompanied by a scalar confidence score \(c \in [0, 1]\) and explanatory reasoning. The harness ranks candidates via a combined score reflecting tag overlap, retrieval coverage, and self-assessed confidence, shortlisting a task-tailored team of up to three specialists. This grounds problem analysis in curated theoretical proofs and algorithmic invariants from the outset.
2. Starter Probe & Immutable Starter Contract: Bounding Initial Scope and Hand-off Boundaries
In multi-agent collaborative generation, ambiguous division of labor frequently causes agents to duplicate effort or prematurely attempt full-program synthesis. Once the specialist team is shortlisted, MARS executes a dedicated First-Agent Probe among the selected members. Each shortlisted agent assesses whether the problem should properly originate within its domain and defines a single, tightly constrained initial contribution. The winning specialist generates a formal Starter Contract specifying its owned subproblem (owned_subproblem), the exact first action (what_would_you_do_first), and an explicit exclusion list (out_of_scope). This contract serves as an immutable operational anchor that is injected into all subsequent prompt contexts across the relay, ensuring the first specialist focuses strictly on establishing core mathematical reductions or primary data structures while preserving clear boundaries for downstream specialists.
3. Single-Draft Execution-Gated Relay Loop: Coupling In-Loop Self-Checking with Deterministic Non-Regression
To eliminate the friction of post-hoc multi-candidate merging and blind debugging loops, MARS introduces an intra-step execution-aware relay protocol operating over a single evolving codebase. Each relay turn comprises two sequential LLM interactions: the first call generates an initial code draft \(C_{\text{draft}}\) conditioned on the current code, the active specialist's assigned subtask, the starter contract, and retrieved RAG context. The sandbox immediately executes \(C_{\text{draft}}\) against public test cases \(S\), generating a runtime diagnostic report \(R_{\text{before}}\). In the second call, the same specialist reviews \(R_{\text{before}}\) and selects one of three actions: keep_code, repair_code, or no_change. If a repair \(C_{\text{repair}}\) is proposed, it is evaluated in the sandbox to produce \(R_{\text{after}}\). The environment enforces a strict deterministic local gate:
This gate grounds code modifications in verifiable execution signals, successfully rejecting regressions and reverting 4.4% of ill-fated repairs. The specialist then outputs a structured handoff payload (containing completed scope, remaining goals, and subtask dependencies) and assigns the next unvisited specialist. The relay is bounded by a maximum of 8 steps, terminating early on explicit completion signals, specialist exhaustion, or a strict no-progress cutoff (rerouting at a streak of two and terminating at three).
4. Post-Relay Infrastructure & Template Normalization: Decoupling Boilerplate Fixes from Algorithmic Logic
Synthesizing multi-step C++ solutions often introduces low-level template defects—such as missing standard headers (e.g., <algorithm>, <numeric>), fast I/O stream synchronization errors (cin.tie(NULL)), or integer width mismatches (long long vs int)—that trigger catastrophic compilation or runtime failures despite sound algorithmic design. MARS decouples algorithmic problem solving from template compliance. After the relay loop concludes, a deterministic sanitization step strips stray markdown artifacts and enforces clean syntax enclosures. An isolated Infrastructure-Fixer is invoked exclusively if the program exhibits template-level compilation or I/O wiring failures. This agent is strictly instructed never to alter algorithmic control flows or data structures, confining its edits to headers, I/O formatting, and variable width casting, ensuring compute is not wasted on surface-level repairs during the core relay.
Benchmark & Evaluation Protocol¶
Evaluation is conducted on the standard CodeContests test split comprising 165 competition-level problems drawn from Codeforces across varying difficulty tiers (Easy \(n=56\), Medium \(n=39\), Hard \(n=70\)). The primary generator backbone is instruction-tuned Gemma 4 (31B-it) operated at temperature 0.0, top-p 0.95, and a 4096-token completion budget. Retrieval operates over the cp-algorithms corpus utilizing Jina Embeddings v2. Evaluated baselines include: (1) Direct zero-shot generation; (2) Single-RAG utilizing the single highest-scoring specialist; (3) Parallel ensemble with manager aggregation; (4) Base relay omitting execution self-checks and subtask tracking; (5) CodeSIM re-evaluated under identical conditions on Gemma 4; and (6) PairCoder on Python. All primary metrics represent the mean and sample standard deviation across 3 independent runs.
Key Experimental Results¶
Main Results¶
Primary performance comparisons on the full 165-task CodeContests test split with Gemma 4:
| Method | Pass Rate | Wall-Clock Time (s) | Token Usage (k) | LLM Calls | Gain vs Direct |
|---|---|---|---|---|---|
| Direct | \(0.480 \pm 0.020\) | \(34.9 \pm 49.6\) | \(1.8 \pm 1.2\) | \(1.0 \pm 0.0\) | — |
| Single-RAG | \(0.529 \pm 0.010\) | \(59.8 \pm 21.2\) | \(25.0 \pm 3.2\) | \(12.0 \pm 0.0\) | +4.9% |
| Parallel ensemble | \(0.564 \pm 0.000\) | \(360.9 \pm 172.9\) | \(29.8 \pm 5.1\) | \(17.6 \pm 0.8\) | +8.4% |
| Base relay | \(0.552 \pm 0.000\) | \(191.6 \pm 91.5\) | \(34.1 \pm 10.2\) | \(17.1 \pm 1.7\) | +7.2% |
| MARS (Ours) | \(\mathbf{0.624 \pm 0.006}\) | \(\mathbf{244.3 \pm 154.4}\) | \(\mathbf{40.3 \pm 8.1}\) | \(\mathbf{16.6 \pm 1.3}\) | +14.4% |
| CodeSIM* (Heavy Search) | \(0.731 \pm 0.009\) | \(817.5 \pm 1358.5\) | \(32.2 \pm 54.8\) | \(10.2 \pm 14.2\) | +25.1% |
Cross-backbone and cross-language transfer evaluation across identical test splits:
| Backbone & Target Language | Method | Pass Rate | Wall-Clock Time (s) | Token Usage (k) | LLM Calls |
|---|---|---|---|---|---|
| Qwen3.5-27B (C++17) | Direct | \(0.192 \pm 0.018\) | \(27.2 \pm 74.6\) | \(1.7 \pm 2.2\) | \(1.0 \pm 0.0\) |
| Single-RAG | \(0.264 \pm 0.004\) | \(71.0 \pm 57.1\) | \(26.5 \pm 4.0\) | \(12.0 \pm 0.0\) | |
| MARS | \(\mathbf{0.297 \pm 0.012}\) | \(109.7 \pm 99.7\) | \(40.5 \pm 18.7\) | \(15.3 \pm 3.3\) | |
| GPT-5.4-mini (C++17) | Direct | \(0.149 \pm 0.019\) | \(3.4 \pm 2.3\) | \(1.2 \pm 0.5\) | \(1.0 \pm 0.0\) |
| Single-RAG | \(0.364 \pm 0.024\) | \(49.7 \pm 26.3\) | \(24.7 \pm 3.2\) | \(12.0 \pm 0.1\) | |
| MARS | \(\mathbf{0.503 \pm 0.043}\) | \(92.2 \pm 61.1\) | \(36.8 \pm 7.4\) | \(15.8 \pm 1.8\) | |
| Gemma 4 (Python/PyPy3) | Direct | \(0.485 \pm 0.000\) | \(70.0 \pm 137.8\) | \(1.6 \pm 1.0\) | \(1.0 \pm 0.0\) |
| MARS | \(\mathbf{0.622 \pm 0.015}\) | \(307.6 \pm 215.7\) | \(42.9 \pm 9.1\) | \(17.1 \pm 1.4\) | |
| PairCoder | \(0.705 \pm 0.009\) | \(426.7 \pm 451.7\) | \(27.6 \pm 20.9\) | \(7.6 \pm 5.4\) |
Ablation Study¶
Systematic ablation of architectural components and protocol variants on Gemma 4:
| Config | Pass Rate | \(\Delta\) | Note |
|---|---|---|---|
| MARS (full) | \(\mathbf{0.624 \pm 0.006}\) | — | Full framework with RAG grounding and execution gate |
| w/o RAG grounding | \(0.604 \pm 0.007\) | -0.020 | Disables retrieval from the cp-algorithms corpus |
| Generalists, no RAG | \(0.615 \pm 0.013\) | -0.009 | Generic agent personas without RAG (+31% runtime: 319.8s) |
| Earlier Base relay | \(0.552 \pm 0.000\) | -0.072 | Removes public-test execution self-check and subtask graph |
| Parallel manager | \(0.564 \pm 0.000\) | -0.060 | Independent parallel synthesis aggregated by manager LLM |
Key Findings¶
- Dominance Among Prompt-Only Architectures: MARS establishes a new state of the art among prompt-only systems with a 0.624 pass rate, outperforming direct generation by +14.4%, Single-RAG by +9.5%, and parallel ensembling by +6.0%.
- Disproportionate Gains on Hard Problems: While competitive baselines plateau near ceiling on Easy problems (0.80–0.93), MARS doubles the pass rate of Direct prompting on Hard tasks (\(n=70\)), escalating from 0.18 to 0.40, where prompt-only baselines typically stall between 0.18 and 0.26.
- Superior Efficiency and Cost Predictability: While CodeSIM achieves 0.731 pass rate through unconstrained simulation and extensive debugging loops, it requires 817.5s per task (3.3× slower than MARS at 244.3s) and exhibits massive variance in token consumption (\(\sigma = 54.8\text{k}\) vs \(8.1\text{k}\) for MARS), demonstrating MARS's practical viability under tight latency and budget limits.
- Reliability of the Deterministic Execution Gate: Across 697 recorded self-check decisions, 38.4% of proposed repairs were accepted, 55.4% preserved the existing draft, and 4.4% were explicitly rejected and reverted by the gate due to test regressions, verifying that empirical sandbox signals protect sound partial solutions from regression.
Highlights & Insights¶
- Topic Alignment Over Lifecycle Roles: Rather than forcing LLMs into abstract software engineering roles (Planner/Coder/Debugger), aligning agent specialization with domain-specific algorithmic theory (cp-algorithms) directly supplies the requisite mathematical invariants and techniques.
- Shared-Draft Sequential Evolution: Maintaining a single evolving codebase across heterogeneous agents avoids the syntactical fragmentation and merge conflicts endemic to parallel multi-candidate consensus frameworks.
- Deterministic Empirical Local Guard: Coupling intra-step LLM self-reflection with physical sandbox execution checks guarantees that an agent cannot degrade public test pass counts, creating a reliable fail-safe for iterative code refinement.
Limitations & Future Work¶
- Blindness to Hidden Test Suites: The intra-step regression gate relies exclusively on sparse public sample cases, making it vulnerable to edge-case bugs, hidden time-limit penalties, and subtle integer overflows that do not trigger public sample failures.
- Absence of Global Multi-Turn Rollback: The deterministic gate only compares the repaired candidate against the same-turn draft; if an early specialist introduces a latent logical error that still passes public samples, later specialists cannot roll back to prior historical checkpoints.
- Language-Specific Harness Dependencies: While demonstrated on C++17 and Python, transferring MARS to additional programming languages requires developing customized AST parsing, sandbox drivers, and language-specific infrastructure repair heuristics.
Related Work & Insights¶
- vs CodeSIM & MapCoder: CodeSIM relies on generic simulation-driven planning and up to 45 iterative debugging loops per hard task; MARS replaces generic debugging with topic-specialized RAG grounding, closing most of the performance gap with 3.3× lower wall-clock latency and 7× lower token variance.
- vs Parallel Ensemble: Parallel ensemble generates isolated candidate solutions across multiple specialists and merges them via a manager LLM, incurring heavy latency (360.9s); MARS routes a single draft sequentially, improving accuracy by 6.0 points while reducing runtime by 32%.
- vs PairCoder: PairCoder implements a Navigator/Driver architecture with dense plan clustering using proprietary embeddings in Python; MARS achieves competitive performance using open-weights models and a lightweight relay protocol without requiring expensive embedding-based candidate clustering.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ [Pioneers topic-specialized RAG multi-agent relays for algorithmic reasoning, replacing conventional lifecycle role decomposition with domain-theory grounding]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Rigorous evaluations across three LLM backbones, two programming languages, difficulty strata, and detailed gate transition statistics]
- Writing Quality: ⭐⭐⭐⭐⭐ [Exceptionally clear problem formulation, precise pseudocode specifications, and transparent documentation of baseline integration constraints]
- Value: ⭐⭐⭐⭐☆ [Provides an efficient, low-variance blueprint for combining retrieval-augmented domain theory with execution-grounded multi-agent reasoning]