MARS: 마진 기반 적대적 위험 제어 정지 규칙을 통한 병렬 LLM 테스트 시간 확장

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

병렬 테스트 시간 확장은 다양한 추론 과정을 실행하고 다수결 투표를 통해 답변의 정확도를 향상시키지만, 전체 추론 과정이 완료될 때까지 실행되어 상당한 계산 비용이 발생합니다. 본 논문에서는 중간 체크포인트에서 부분적인 추론 과정을 탐색하여 생성 중단 없이 현재 답변을 추출하고, 이를 통해 변화하는 집계 투표 결과를 파악할 수 있다는 점을 발견했습니다. 이러한 관찰을 바탕으로, 우리는 MARS라는 마진 기반 적대적 정지 규칙을 제안합니다. MARS는 어떤 활성 추론 과정이 답변을 변경할 가능성이 높은지를 예측하고, 선두 추론 과정이 보수적인 미래 투표 변화 범위 내에서 안전한 상태를 유지하면 중단합니다. 이 규칙은 불확실성의 두 가지 원인을 분리하여 다룹니다. 첫째, 현재 마진의 어느 정도가 유지될 가능성이 있는지 결정하는 추론 과정 수준의 전환 확률을 학습합니다. 둘째, 적대적 경계를 통해 워밍업 추론 과정을 기반으로, 어떤 추론 과정들이 전환될지를 예측하는 더 어려운 문제를 해결합니다. 정확한 전환 확률을 사용하면, MARS는 높은 확률로 조기에 중단된 답변이 전체 예산 투표와 일치함을 보장합니다. 실제로 5개의 특징을 사용하는 로지스틱 모델이 실제 전환 행동과 매우 유사하게 작동합니다. 세 가지 추론 모델과 세 가지 수학 벤치마크에서, MARS는 self-consistency 토큰의 25~47%를 절약하고, DeepConf Online이라는 강력한 가중 투표 기반 라인베이스 (이미 약한 추론 과정을 필터링하고 잘라내는 방식)에 비해 추가로 14~29%의 성능 향상을 보입니다. 동시에 해당 전체 예산 기반 모델과 동일한 정확도를 유지합니다.

Parallel test-time scaling samples many reasoning traces and majority-votes their answers, improving LLM accuracy but requiring traces to run to completion, incurring substantial computational overhead. We observe that probing partial traces at intermediate checkpoints can extract current answers without disrupting generation, revealing an evolving aggregate vote. Based on this observation, we introduce MARS, a margin-adversarial stopping rule that estimates which active traces are likely to change their answers and stops once the leader remains safe under a conservative bound on future vote movement. The rule separates two sources of uncertainty. It learns the trace-level switch probabilities that determine how much of the current margin is likely to be retained, while handling the harder question of where switching traces land through an adversarial bound calibrated from warmup traces. With true switch probabilities, MARS guarantees with high probability that the early-stopped answer matches the full-budget vote. In practice, a five-feature logistic model closely matches oracle switching behavior. Across three reasoning models and three competition-math benchmarks, MARS saves 25-47% of self-consistency tokens and 14-29% on top of DeepConf Online, a strong confidence-weighted baseline that already filters and truncates weak traces, while matching the accuracy of the corresponding full-budget baselines.