MARS: Multi-Specialist LLM Relay System for Competitive Programming

기술 요약: MARS – 전문화된 LLM들의 다중 에이전트 릴레이 (Multi-Agent Relay of Specialized LLMs)

문제 정의
경쟁 프로그래밍은 정밀한 구현, 희소한 신호 하에서의 검증, 그리고 심도 있는 알고리즘 이론의 통합을 요구하기 때문에 대규모 언어 모델(LLM)에 대한 엄격한 스트레스 테스트 역할을 합니다. 기존의 코드 생성용 다중 에이전트 파이프라인은 일반적으로 작업을 일반적인 역할(기획자, 코더, 디버거)로 분해하며, 백본 LLM의 사전 학습에 의존하여 필요한 도메인 전문 지식을 제공하도록 합니다. 저자들은 이러한 "콘텐츠 불가지론적(content-agnostic)" 접근 방식이 복잡한 문제에 필요한 구체적인 알고리즘 전문 지식을 공급하는 데 실패하며, 이로 인해 주제적 역량이 명시적으로 근거를 갖추기보다는 단순히 나타나기를 기대해야 하는 지속적인 실패 모드가 발생한다고 주장합니다.

방법론: MARS
본 논문은 일반적인 역할 분해를 대신하여 주제와 정렬된 전문가 팀을 도입하도록 설계된 프롬프트 전용 프레임워크인 **MARS (Multi-Agent Relay of Specialized LLMs)**를 소개합니다. 시스템은 다음 메커니즘을 통해 작동합니다:

• 전문화된 에이전트 풀 (Specialized Agent Pool): 시스템은 각 에이전트가 단일 알고리즘 주제(예: 동적 계획법, 그래프, 기하학, 문자열)의 도메인 전문가로 정의된 에이전트 풀을 유지합니다.
• RAG 근거 설정 (RAG Grounding): 각 전문가는 큐레이션된 알고리즘 이론 코퍼스(구체적으로 cp-algorithms 코퍼스)에 대한 검색 증강 생성(RAG)을 통해 근거를 갖습니다. 이는 에이전트가 파라미터 메모리에만 의존하는 대신 관련 이론적 지식에 접근할 수 있도록 보장합니다.
• 동적 팀 구성 (Dynamic Team Formation): 문제를 받으면 모든 에이전트는 공유된 검색 코퍼스를 대상으로 자기 평가를 수행하여, 해당 작업이 자신의 전문 분야와 일치하는지, 그리고 솔루션을 초기화할 수 있는지 판단합니다. 관련성 및 신뢰도 점수를 기반으로 최대 3개의 에이전트로 구성된 소규모 팀이 선정됩니다.
• 릴레이 실행 (Relay Execution):
  • 스타터 선택 (Starter Selection): "스타터(starter)" 에이전트가 선출되어 초기 C++17 솔루션을 작성합니다.
  • 반복 릴레이 (Iterative Relay): 솔루션은 팀을 통해 순차적으로 전달됩니다. 각 턴에서 활성화된 에이전트는 현재의 초안, 할당된 하위 작업, 스타터 계약, 그리고 RAG 컨텍스트를 전달받습니다.
  • 실행 게이트 피드백 (Execution-Gated Feedback): 결정적으로, 모든 초안은 샌드박스 내에서 공개 테스트 케이스에 대해 실행됩니다. 그 후 에이전트는 자기 점검을 수행합니다: 코드를 유지할지, 수정할지, 또는 다음에게 넘길지를 결정합니다. 수정은 코드가 컴파일되고 해당 턴의 초안과 비교했을 때 통과하는 공개 테스트의 수가 감소하지 않는 경우에만 수락됩니다.
  • 종료 (Termination): 에이전트가 완료를 신호하거나, 팀이 소진되거나, 진전이 없는 컷오프(no-progress cutoff)가 트리거되면 릴레이가 중단됩니다.
• 인프라 픽서 (Infrastructure Fixer): 특정 실패가 감지된 경우에만 보일러플레이트(I/O 연결, include, 타입 너비 등)를 정규화하는 최종 패스를 수행합니다.

주요 기여

1. 주제 정렬 전문화 (Topic-Aligned Specialization): 일반적인 페르소나나 백본의 다양성을 사용하는 이전 연구들과 달리, MARS는 에이전트의 전문화를 작업의 주제 구조와 직접 결합하며, 각 전문가를 주제적 지식 코퍼스에 근거하게 합니다.
2. 루프 내 실행 신호 (In-Loop Execution Signal): 이 프레임워크는 공개 테스트 실행을 매 릴레이 단계마다 결정론적 신호로 통합하여, 활성화된 전문가가 사후 디버깅이나 자기 보고된 신뢰도에 의존하는 대신 자신의 초안을 검증하고 수정할 수 있도록 합니다.
3. 프롬프트 전용 효율성 (Prompt-Only Efficiency): 이 시스템은 복잡한 학습이나 강화 학습 없이, 오직 프롬프트 엔지니어링, RAG, 실행 피드백에 의존하여 높은 성능을 달-성합니다.

결과
Gemma 4 백본을 사용하여 CodeContests 테스트 스플릿의 165개 작업에 대해 평가한 결과:

• 성능 (Performance): MARS는 0.624 ± 0.006의 통과율을 달성하였으며, 이는 직접 프롬프팅(0.48) 대비 +14.4 퍼센트 포인트 향상된 수치이며, Single-RAG(0.53) 및 병렬 앙상블(0.56)보다 유의미한 이득을 보여줍니다.
• 최신 기술과의 비교 (Comparison to State-of-the-Art): MARS는 더 무거운 탐색 시스템인 CodeSIM(0.731)과의 격차를 좁혔습니다. CodeSIM이 앞서기는 하지만, MARS는 **3.3배 낮은 실제 시간 비용(wall-clock cost)**과 훨씬 작은 태스크당 토큰 소비 편차를 유지하며 이 성과를 달성했습니다.
• 견고성 (Robustness): 이 방법은 다양한 백본(Qwen3.5, GPT-5.4-mini)과 언어(Python)에 걸쳐 유지되며, 일관되게 베이스라인을 능가합니다.
• 난이도 확장성 (Difficulty Scaling): 직접 프롬프팅 대비 이점은 Medium 및 Hard 난이도 계층에서 크게 확대되며, Hard 작업에서 MARS는 직접 프롬프팅의 통과율(0.18)보다 두 배 이상 높은 성능(0.40)을 보입니다.
• 절제 실험 (Ablation): RAG 근거 설정을 제거하면 성능이 2.0 포인트 감소합니다. 실행 기반 자기 점검(Base relay)을 제거하면 성능이 7.2 포인트 감소하여, 루프 내 피드백 메커니즘의 중요성을 강조합니다.

의의 및 주장
본 논문은 주제 정렬 전문화와 결정론적 실행 피드백의 결 조합이 일반적인 다중 에이전트 분해나 대규모 샘플링보다 경쟁 프로그래밍에 더 효과적인 전략임을 입증한다고 주장합니다. 에이전트를 일반적인 코더가 아닌 이론에 근거한 도메인 전문가로 취급함으로써, MARS는 더 계산 집약적인 시뮬레이션 기반 접근 방식(CodeSIM 등)과의 성능 격차를 줄이는 동시에 더 단순하고 비용 효율적인 프로토콜을 유지합니다. 저자들은 MARS를 모델 재학습 없이도 고수준 문제 해결에 필요한 심도 있는 알고리즘 콘텐츠를 처리할 수 있는, 스스로 조직화된 도메인 전문가 팀을 향한 단계로 규정합니다.