기술 요약: 경쟁 프로그래밍을 위한 에이전틱 검증기(Agentic Verifier) 스케일링

문제 정의

대규모 언어 모델(LLM)은 프로그램 합성 분야에서 강력한 능력을 입증해 왔으나, 단 한 번의 시도로 경쟁 프로그래밍 문제를 정확하게 해결하는 데에는 자주 어려움을 겪습니다. 정확도를 높이기 위한 일반적인 전략은 **테스트 시간 스케일링(test-time scaling)**으로, 여러 후보 솔루션을 샘플링하고 검증기가 최적의 솔루션을 선택하도록 하는 것입니다.

기존의 검증 방법들은 경쟁 프로그래밍 맥락에서 다음과 같은 중대한 한계에 직면해 있습니다:

1. 전체 테스트 케이스 생성: 완전한 테스트 케이스(입력값 + 정답 출력값)를 생성하는 것은 원래의 문제를 푸는 것만큼이나 어렵기 때문에, 계산 비용이 많이 들고 신뢰도가 낮습니다.
2. 입력 전용 실행(Input-Only Execution): 최근의 접근 방식들은 유효한 테스트 입력만을 생성하고 출력 일치 여부(투표)를 기반으로 솔러션을 선택합니다. 그러나 이러한 방법들은 대개 무작위 입력 샘플링에 의존합니다.
3. 무작위 샘플링의 비효효율성: 경쟁 프로그래밍에서 유효한 입력 공간은 매우 방대하지만, 그중 "판별력 있는(discriminative)" 입력(즉, 올바른 솔루션과 잘못된 솔루션 간의 행동 차이를 드러낼 수 있는 입력)은 극히 일부에 불과합니다. 본 논문의 예비 실험은 무작위 입력의 수를 늘리는 것이 수확 체감의 법칙을 따르며, 정답 테스트 케이스와의 성능 격차를 좁히는 데 실패함을 보여줍니다.

방법론: 에이전틱 검증기 (Agentic Verifier)

저자들은 프로그램의 동작을 능동적으로 추론하고, 후보 솔루션들 사이의 불일치를 드러낼 수 있는 고도로 판별력 있는 테스트 입력을 탐색하도록 설계된 LLM 기반 에이전트인 **에이전틱 검증기(Agentic Verifier)**를 제안합니다.

핵심 메커즘

맹목적인 무작위 샘플링 대신, 검증기는 코드 실행 환경과 **다회차 상호작용(multi-turn interaction)**을 수행합니다:

1. 태스크 정식화: 문제 $Q$와 후보 솔루션 쌍 $(C_a, C_b)$가 주어졌을 때, 에이전트의 목표는 $Exec(C_a, x) \neq Exec(C_b, x)$를 만족하는 유효한 입력 $x$를 생성하는 입력 생성 프로그램 $G$를 만드는 것입니다.
2. 상호작용 루프: 에이전트는 입력을 반복적으로 제안하고, 후보 솔루션을 실행하며, 피드백(런타임 에러, 출력값)을 조사하고, 반례를 발견하기 위해 자신의 가설을 정교화합니다.
3. 선택 전략: 추론 시점에, 학습된 검증기는 후보 솔루션 쌍을 위한 타겟팅된 테스트 입력을 생성합니다. 이 입력들은 실행 기반 투표 전략에 사용되어 최종 솔루션을 선택합니다.

학습 파이프라인

검증기는 확장 가능한 3단계 파이프라인을 통해 학습됩니다:

1. 대규모 데이터 합성: 저자들은 레이블이 지정된 솔루션을 포함하는 경쟁 프로그래밍 문제 데이터셋을 구축합니다. 정답 테스트 케이스가 없는 문제의 경우, 신뢰성을 보장하기 위해 여러 참조 솔루션에 걸친 합의 기반 다수결 메커즘을 사용하여 고품질 테스트 스위트를 합성합니다.
2. 리젝션 미세 조정(Rejection Fine-Tuning): 강력한 교사 모델(Qwen3-235B)을 사용하여 에이전트가 구별되는 입력을 성공적으로 생성한 성공적인 다회차 상호작용 궤적을 수집합니다. 베이스 모델은 이러한 고품질 궤적을 바탕으로 미세 조정되며, 이때 초기 프롬프트와 피드백은 마스킹 처리하여 효과적인 상호작용 패턴을 학습합니다.
3. 에이전틱 강화 학습(Agentic Reinforcement Learning): 검증기는 GRPO(Group Relative Policy Optimization)를 사용하여 추가로 최적화됩니다. 보상 함수는 희소(sparse)하며 결과 기반입니다:
   • $+1$: 두 솔루션을 구별하는 유효한 입력.
   • $0$: 두 솔루션을 구별하지 못하는 유효한 입력(솔루션들이 일치함).
   • $-1$: 유효하지 않은 입력 또는 빈 생성기.
     학습 커리큘럼은 구별되는 입력이 드문 "하드 네거티브(hard negative)" 쌍을 우선시하여, 에이전트가 타겟팅된 생성 동작을 학습하도록 유도합니다.

주요 기여

1. 경험적 분석: 본 논문은 입력 전용 실행 기반 검증에서 무작위 입력 생성이 매우 비효율적임을 경험적으로 입증하며, 판별력 있는 테스트 입력과 비교했을 때 상당한 성능 격차가 있음을 밝혀냈습니다.
2. 에이전틱 검증기: 정적인 방식이나 무작위 샘플링을 넘어, 다회차 상호작용을 통해 고도로 판별력 있는 테스트 입력을 능동적으로 생성하는 에이전트를 도입했습니다.
3. 확장 가능한 학습 파이프라인: 데이터 합성, 리젝션 미세 조정, 에이전틱 강화 학습을 결합하여 검증기를 학습시키는 새로운 파이프라인을 제시했습니다.
4. 테스트 시간 스케일링: 제안된 방법이 후보 솔루션의 수와 생성된 입력의 수 모두에 따라 효과적으로 확장되며, 테스트 시간 계산량 증가에 따라 지속적으로 이득을 얻는다는 것을 입증했습니다.

실험 결과

이 접근 방식은 두 가지 정책 모델(Qwen3-30B 및 Qwen3-235B)을 사용하여 다섯 가지 경쟁 프로그래밍 벤치마크(USACO, LiveCodeBench, OJBench, ICPC-Eval, 그리고 새로운 CodeForces 벤치마크)에서 평가되었습니다.

• 성능 향상: 에이전틱 검증기는 무작위 입력 생성, 모델 생성 테스트 케이스(CodeT, CodeRM), 보상 모델 기반 선택을 포함한 강력한 베이스라인들을 일관되게 능가했습니다.
  • 강력한 실행 기반 베이스라인 대비 Best@k 정확도에서 **+10~15%**의 절대적 이득을 달성했습니다.
  • OJBench "Hard" 서브셋에서, 학습된 30B 검증기는 베이스라인 대비 **+34.1%**의 성능 향상을 보였으며, 이는 제로샷(zero-shot) 235B 모델을 크게 상회하는 수치입니다.
• 스케일링 동작: 조기 포화 현상을 보인 베이스라인들과 달리, 에이전틱 검증기는 테스트 입력의 수가 증가함에 따라 성능이 꾸준히 향상되는 명확한 테스트 시간 스케일링 동작을 보여주었습니다.
• 제로샷 vs. 학습 모델: 제로샷 LLM도 어느 정도의 개선을 제공했지만, 학습된 태스크 특화 검증기는 제로샷 모델보다 7배 더 작음에도 불구하고 이를 훨씬 뛰어넘는 성능을 보여주었습니다.

의의 및 주장

본 논문은 실행 기반 투표의 효과가 테스트 입력의 단순한 양보다는 판별력의 품질에 의해 주로 결정된다고 주장합니다.

Best-of-N 선택 성능을 개선하는 것을 넘어, 저자들은 더 넓은 함의를 강조합니다: 벤치마크 테스트 스위트는 불완전한 검증기입니다. 고정된 테스트 스위트는 유효한 입력 공간의 제한된 부분만을 커버하므로, 잘못된 솔루션이 모든 벤치마크 테스트를 통과하는 거짓 양성(false positive) 문제를 야기합니다. 에이전틱 검증기는 타겟팅된 반례를 찾아냄으로써 이러한 실패를 능동적으로 드러낼 수 있습니다. 따라서 저자들은 이 검증기를 단순한 재순위화(reranking) 도구가 아니라, 입력 커버리지를 확장하고 대규모 코드 평가에서의 벤치마크 유도 노이즈를 완화할 수 있는 보완적인 정답 확인 메커니즘으로 포지셔닝합니다.