🤖 AI

MARS: Margin-Adversarial Risk-controlled Stopping for Parallel LLM Test-time Scaling

이 논문은 선두 답변이 통계적으로 안정된 상태를 유지할 것이라고 보장되는 즉시 병렬적인 LLM 추론 궤적을 동적으로 중단하는 마진-적대적 정지 규칙인 MARS를 소개하며, 이를 통해 전체 예산 추론 대비 정확도를 희생하지 않으면서 계산 비용을 25~47% 절감한다.

원저자: Wenbo Chen, Puheng Li, Mengyang Liu, Weijie Su, Tianpei Xie

게시일 2026-06-12

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Wenbo Chen, Puheng Li, Mengyang Liu, Weijie Su, Tianpei Xie

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

매우 어려운 수학 문제를 풀려고 한다고 상상해 보세요. 한 사람에게 생각할 시간을 주는 대신, 512명의 서로 다른 사람들(또는 AI '트레이스')을 고용하여 동시에 문제를 풀게 합니다. 이것을 **병렬 테스트 타임 스케일링(parallel test-time scaling)**이라고 부릅니다.

보통은 512명 모두가 에세이를 다 쓸 때까지 기다린 후에야 투표를 집계하고 누가 정답을 맞혔는지 확인할 수 있습니다. 이는 많은 시간과 비용(연산 능력)이 소모되는 일입니다. 하지만 많은 문제의 경우, 모든 사람이 글쓰기를 마치기 훨씬 전부터 이미 승자가 명확해지곤 합니다.

이 논문은 MARS(Margin-Adversarial Risk-controlled Stopping)라는 새로운 방법을 소개합니다. MARS를 똑똑한 심판이라고 생각해 보세요. 이 심판은 주자들이 글을 쓰는 도중에 중간 점검을 하여, 잘못된 승자를 뽑을 위험 없이 경기를 조기에 종료할 수 있는지 결정합니다.

작동 방식은 다음과 같습니다.

1. 문제점: "거짓 합의(False Consensus)"의 함정

89%의 주자들이 현재 빨간색 셔츠(오답)를 입고 있고, 11%만이 파란색 셔츠(정답)를 입고 있는 경주를 상상해 보세요.

기존 방식 (합의 중단/Consensus Stopping): 미숙한 심판은 빨간 팀이 엄청난 차이로 앞서고 있는 것을 보고 "좋아, 빨간 팀이 확실히 이기고 있으니 경기를 멈추자!"라고 말합니다. 하지만 나중에 파란 팀원들이 더 나은 전략을 깨닫고 파란색으로 갈아타면서, 빨간 팀을 추월하게 됩니다. 심판이 너무 일찍 멈춰서 잘못된 승자를 선택한 것입니다.
논문의 관찰: 단순히 지금 이기고 있다고 해서 안전한 것은 아닙니다. 우리는 지고 있는 팀에게 아직 따라잡을 수 있는 '연료'가 남아 있는지 알아야 합니다.

2. MARS의 해결책: "안전 마진" 체크

MARS는 단순히 현재 점수만 보는 것이 아니라, 미래에 발생할 수 있는 최악의 시나리오를 계산하는 신중한 심판처럼 행동합니다.

정기적인 간격(체크포인트)마다 심판은 주자들을 잠시 멈춰 세우고 "현재 답이 무엇입니까?"라고 묻습니다 (이를 프로빙/probing이라고 합니다). 그런 다음 MARS는 두 가지 일을 수행합니다.

단계 A: 변화 예측하기 (누가):
MARS는 각 주자의 이력을 살펴봅니다. 이전에 생각을 바꾼 적이 있나요? 확신을 가지고 있나요? 이를 바탕으로 특정 주자가 나중에 답을 바꿀 확률을 추정합니다.
- 비유: 코치가 주자의 땀과 호흡을 보고 "이 주자는 포기하거나 마음을 바꿀 가능성이 높다"와 "이 주자는 꾸준하다"를 예측하는 것과 같습니다.
단계 B: 적대적 안전망 (얼마나 나쁜가):
MARв는 무서운 질문을 던집니다: "지는 팀이 할 수 있는 최악의 상황은 무엇인가?" 이는 만약 어떤 주자가 마음을 바꾼다면, 승리를 훔치기 위해 가장 강력한 라이벌 팀으로 갈아탈 것이라고 가정하는 것입니다.
- 비 by: 심판이 이렇게 계산한다고 상상해 보세요. "빨간 팀이 100점 차로 앞서고 있다. 하지만 만약 아직 결정되지 않은 주자 중 50명이 파란 팀으로 옮겨가고, 빨간 팀 중 20명이 파란 팀으로 옮겨간다면, 파란 팀이 이길 수도 있다."
- MARS는 현재 선두의 리드가 너무 커서, 설령 모든 미결정 주자가 가장 강력한 라이벌 팀으로 옮겨가는 최악의 상황이 발생하더라도 선두가 여전히 승리할 수 있을 때에만 경기를 중단합니다.

3. "캘리브레이션(조정)" 기술

이 논문은 모든 사람이 최악의 라이벌 팀으로 바뀔 것이라고 가정하는 것이 너무 무섭다(너무 보수적이다)는 점을 인정합니다. 그렇게 되면 심판은 결국 마지막까지 기다려야 하므로, 조기 종료의 목적을 달öss게 됩니다.

그래서 MARS는 먼저 작은 "연습 경기"(웜업 트레이스/warmup traces)를 실행합니다. 연습에 참여한 주자들이 실제로 얼마나 자주 마음을 바꾸는지, 그리고 어디로 옮겨가는지를 관찰합니다. 이를 통해 MARS는 자신의 "무서운 계수"(감마/gamma)를 조정합니다.

비유: 연습 경기를 통해 주자들이 라이벌 팀으로 거의 옮겨가지 않는다는 것을 알게 되면, 심판은 규칙을 약간 완화합니다. "좋아, 우리는 절대적인 최악의 상황까지 기다릴 필요는 없다. 그저 매우 발생 가능성이 높은 나쁜 상황까지만 기다리면 된다." 이를 통해 MARS는 안전을 유지하면서도 더 일찍 경기를 끝낼 수 있습니다 다.

4. 결과

논문은 세 가지 서로 다른 AI 모델이 어려운 수학 경시 대회(AIME, HMMT 등)를 푸는 과정을 대상으로 MARS를 테스트했습니다.

절감 효과: MARS는 모든 사람이 글을 마칠 때까지 기다리는 것에 비해 컴퓨팅 시간(토큰)을 25%에서 47%까지 절약했습니다. 이미 효율적인 방법을 사용하던 다른 스마트한 방법들과 비교했을 때도, MARS는 추가로 14%에서 29%를 더 절약했습니다.
정확도: 결정적으로, MARS는 정확도를 낮추지 않았습니다. 모든 사람이 끝날 때까지 기다렸을 때와 동일한 빈도로 정답을 맞혔습니다.
비교: "패럴렐 프로브(Parallel-Probe)"라는 다른 방법은 다수가 안정적으로 보일 때까지 기다려 조기에 중단하려고 시도했습니다. 논문은 이 방법이 어려운 문제에서 처참하게 실패했음을 보여줍니다(정확도가 절반으로 떨어짐). 왜냐하면 "틀린" 답이 안정적으로 보일 때 너무 일찍 멈췄기 때문입니다. MARS는 단순히 현재 점수만 보는 대신 "안전 마진"을 체크함으로써 이 문제를 피했습니다.

요약

MARS는 AI 추론을 조기에 종료하는 똑똑한 방법입니다. 모든 사람이 에세이를 다 쓸 때까지 기다리는 대신, 초안을 확인하고, 누가 마음을 바꿀지 예측하며, 패자들이 최선을 다해 따라잡더라도 현재의 승자가 안전할지를 계산합니다. 만약 승자가 안전하다면, MAR스은 정답을 놓치지 않으면서도 엄청난 시간과 비용을 아끼며 경기를 중단합니다.

기술 요약: MARS (Margin-Adversarial Risk-controlled Stopping)

1. 문제 정의

병렬 테스트 타임 스케일링(Parallel test-time scaling)은 여러 추론 트레이스(reasoning traces)를 샘플링하고 이들의 답변을 다수결(예: Self-Consistency)로 집계함으로써 복잡한 추론 작업에서 대규모 언어 모델(LLM)의 정확도를 향상시킵니다. 그러나 이러한 방식은 모든 트레이스가 완료될 때까지 실행되어야 하므로 상당한 계산 오버헤드를 발생시킵니다. 특히, 승리하는 답변이 조기에 결정되는 경우에도 모든 트레이스를 끝까지 실행해야 한다는 점이 문제입니다.

현대의 추론 모델들은 생성 과정을 방해하지 않으면서도 **프로빙(probing)**을 통해 중간 "사고 과정(thinking traces)"에서 부분적인 답변을 추출할 수 있는 기능을 제공합니다. 기존의 조기 종료(early-stopping) 방식은 합의 휴리스틱(consensus heuristics)(예: 다수결 답변이 $u$ 번 연속으로 안정될 때까지 대기)에 의존합니다. 본 논문은 이러한 휴리스틱이 어려운 문제에 대해 근본적으로 결함이 있다고 주장합니다. 즉, 초기에 안정적으로 보이는 잘못된 답변에 고착되었다가, 더 많은 트레이스가 추론을 수정함에 따라 나중에 정답에 의해 역전되는 경우가 빈다는 것입니다. 핵심 과제는 토큰을 절약하면서도 전체 예산(full-budget) 투표 결과를 확실하게 보존할 수 있는 시점에 언제 병렬 생성을 중단할 것인가를 결정하는 것입니다.

2. 방법론: MARS

저자들은 과거의 안정성이 아닌 미래의 리스크에 초점을 맞춘 원칙적인 조기 종료 규칙인 **MARS (Margin-Adversarial Risk-controlled Stopping)**를 제안합니다.

핵심 통찰

안전성은 투표 결과가 변했는지 여부가 아니라, 더 이상 변할 수 있는지 여부에 의해 결정됩니다. 선두(lead)가 안전하려면, 현재의 마진이 모든 도전 과제(challenger)에 대한 최악의 경우의 피해를 초과해야 합니다.

중단 규칙

각 체크포인트 $t$ 에서, MARS는 모든 활성 트레이스 $j$ 와 모든 잠재적 도전 과제 $k$ (새로운 답변을 나타내는 합성된 "미보이지 않은" 도전 과제 $\perp$ 포함)를 평가합니다. 알고리즘은 다음 조건을 만족할 때 중단됩니다:
모든 도전 과제 $k$ 에 대하여:
$M_k(t) \ge \Gamma_k(t) + \epsilon(N, \delta)$
여기서:

$M_k(t)$ : 선두 $L(t)$ 가 도전 과제 $k$ 에 대해 가지는 현재 투표 마진입니다.
$\Gamma_k(t)$ : 예상되는 **적대적 전환 피해(adversarial switch damage)**입니다. 이는 활성 트레이스들이 선두에게 가장 불리한 목적지로 전환될 때 발생하는 예상 투표 손실의 합입니다.
- 만약 선두를 지지하던 트레이스가 전환된다면, $2w_j$ 의 피해(선두의 $w_j$ 손실 및 도전 과제의 $w_j$ 이득)를 입힙니다.
- 만약 중립적인 옵션을 지지하던 트레이스가 전환된다면, $w_j$ 의 피해를 입힙니다.
- 만약 도전 과제를 지지하던 트레이스가 전환된다면, 이는 오히려 선두에게 도움이 됩니다(음의 피해).
$\epsilon(N, \delta)$ : 선두가 바뀔 확률을 리스크 수준 $\delta$ 미만으로 보장하는 집중 경계(concentration bound, Hoeffding 부등식에서 유도됨)입니다.

두 부분 모델링

규칙을 실용적으로 만들기 위해, MARS는 불확실성을 두 가지 구성 요소로 분리합니다:

전환 확률 ( $q_j$ ): 트레이스가 답변을 바꿀지 여부입니다. 이는 소수의 "웜업(warmup)" 트레이스로 학습된 가벼운 5개 피처 로지스틱 회귀 모델을 사용하여 학습됩니다. 피처에는 체크포인트 위치, 프로브 신뢰도, 답변 반전 횟수, 스트릭(streak) 길이, 신뢰도 추세 등이 포함됩니다.
목적지 행동 (Destination Behavior): 전환되는 트레이스가 어디로 갈 것인가 하는 문제입니다. 미래의 정확한 답변 문자열을 예측하는 것은 불가능하므로, MARS는 이를 **적대적(adversarially)**으로 처리합니다(모든 전환이 선두를 공격하기 위해 협력한다고 가정하여 지나치게 보수적이 되는 것을 방지하기 위함). 이를 위해 MARS는 웜업 트레이스를 통해 훈련된, 실제 환경에서 전환되는 질량이 얼마나 적대적으로 행동하는지를 추정하는 수축 파라미터(contraction parameter) $\gamma \in [0.5, 1]$ 를 도입합니다.

알고리즘 흐름

웜업 (Warmup): 16개의 트레이스를 끝까지 실행하여 전환 확률 모델을 적합시키고 $\gamma$ 를 보정합니다.
병렬 실행 (Parallel Execution): $N$ 개의 트레이스를 실행합니다.
체크포인팅 (Checkpointing): 간격에 따라 활성 트레이스의 현재 답변을 프로브합니다.
인증 (Certification): 마진과 예상 적대적 피해를 계산합니다. 마진이 모든 도전 과제에 대한 피해 경계를 초과하면, 생성을 중단하고 현재의 선두를 출력합니다.
폴백 (Fallback): 조건이 충족되지 않으면 전체 예산까지 실행합니다.

3. 주요 기여

원칙적인 중단 기준: 단순한 히스토리 기반의 안정성 검출이 아닌, 마진 기반의 리스크 제어 중단 규칙을 도입하여, 조기 종료된 답변이 전체 예산 투표 결과와 일치한다는 높은 확률의 보장을 제공합니다.
적대적 보정 (Adversarial Calibration): 학습된 전환 확률과 보정된 적대적 경계를 결합하여, 트레이스가 어디로 전환될지에 대한 불확식성을 처리하는 방법을 개발함으로써 복잡한 목적지 분포 모델링의 필요성을 피했습니다.
실증적 검증: 단순한 로지스틱 모델이 "오라클(oracle)" 동작(미래의 전환 상태를 미리 아는 것)과 매우 유사함을 보여줌으로써, 전환 확률과 목적지 행동의 분리가 유효함을 입증했습니다.

4. 실험 결과

세 가지 모델(DeepSeek-R1-8B, Qwen3-32B, Qwen3-next)과 세 가지 경시 수학 벤치마크(AIME 2025, HMMT, BRUMO 2025)를 통해 평가되었습니다:

토큰 절감:
- 표준 Self-Consistency(SC) 대비 **25–47%**의 토큰 감소를 달성했습니다.
- 약한 트레이스를 필터링하고 절단하는 강력한 베이스라인인 DeepConf Online보다 추가로 14–29% 더 많은 절감을 달ر성했습니다.
정확도 보존:
- MARS는 18개 설정 모두에서 전체 예산 베이스라인의 정확도와 일치했습니다(차이가 발생하는 경우에도 0.6 퍼센트 포인트 이내).
- 일부 설정에서는 정확도가 최대 0.8 포인트까지 향상되었습니다 (예: SC 하에서의 Qwen3-next on AIME).
Parallel-Probe와의 비교:
- 합의 안정성(consensus stability)을 사용하는 동시 방식인 Parallel-Probe는 트레이드오프에 직면합니다: 높은 절감 효과(20–51%)를 얻으려면 상당한 정확도 손실(6–45 퍼센트 포인트)을 감수해야 합니다. 정확도를 보존하도록 튜닝할 경우, 절감 효과는 $\le 4\%$ 로 급감합니다.
- MARS는 정확도 손실 없이 높은 절감 효과를 달성하며, 이는 안정성이 아닌 마진을 인증하기 때문입니다.

5. 의의 및 주장

본 논문은 **집계된 마진 안정성(aggregate margin stability)**이 개별 트레이스의 신뢰도 필터링과는 별개인, 테스트 타임 효율성을 위한 독특하고 효과적인 원천이라고 주장합니다. 그 의의는 다음과 같습니다:

안전 보장: Hoeffding 경계를 통해 조기 종료가 최종 투표 결과를 변경하지 않는다는 이론적 보장을 제공함으로써, 어려운 문제에서 발생하는 합의 휴리스틱의 실패 모드를 해결합니다.
학습 없는 효율성: 추가적인 검증기(verifier) 학습이나 보상 모델 없이, 생성 역학을 관찰하고 프로빙함으로써 순수하게 효율성을 달성합니다.
실용성: 전환 확률에 대한 가벼운 로지스틱 모델과 보정된 적대적 경계를 결합하는 것만으로도 병렬 추론의 복잡한 역학을 포착할 수 있음을 입증하여, 실제 병렬 디코딩 시나리오에서 상당한 토큰 절약을 가능하게 했습니다.

저자들은 향후 연구로서 적응형 프로빙 간격(adaptive probing intervals)을 탐구하고, 수학적 추론을 넘어 코드 생성이나 에이전트 작업과 같은 도메인으로 프레임워크를 확장할 수 있을 것이라고 언급했습니다.