기술 요약: LLM 추론을 위한 리셋 및 폐기 (Reset and Discard, ReD)

문제 정의

대규모 언어 모델(LLM)은 검증 가능한 작업(예: 코딩, 수학, 형식적 증명)에 대해 pass@k 메트릭을 사용하여 평가되는 경우가 늘고 있습니다. pass@k는 $k$번의 시도 내에 단일 인스스턴스를 올바르게 해결할 확률을 측정합니다. 경험적 관찰에 따르면, 많은 작업에서 실패율($1 - \text{pass@k}$)은 $k$에 대해 멱법칙(power law)을 따르며 감소합니다 (즉, $1 - \text{pass@k} \propto k^{-\alpha}$).

그러나 고정된 글로벌 예산(시도 횟수, 토큰 또는 USD로 측정됨)이 있는 실제 추론 시나리오에서 중요한 목표는 단일 문제에 대한 성공률이 아니라, 총 자원 제약 조건 내에서 해결된 고유한 문제의 기대값인 coverage@cost입니다. 표준 할당 정책인 solve-to-completion(다음 문제로 넘어가기 전에 한 문제를 해결할 때까지 반복적으로 샘플링하는 방식)은 멱법칙 난이도 분포 하에서 비효로적입니다. 어려운 문제가 불균형적으로 많은 시도를 소비하기 때문에, 이 정책은 $\alpha < 1$인 경우 coverage@cost에서 아래선형(sublinear) 성장을 초래합니다. 이는 추가적인 예산 투입이 해결된 문제 수의 증가로 이어지는 수익 체감 현상을 발생시킵니다.

방법론: 리셋 및 폐기 (Reset-and-Discard, ReD)

저자들은 추론 과정을 문제 집합에 대한 너비 우선 탐색(breadth-first search)으로 취급하여 글로벌 처리량을 최적화하는 할당 정책인 **Reset-and-Discard (ReD)**를 제안합니다.

ReD 프로토콜

1. 리셋 (Reset): 한 문제를 해결할 때까지 지속하는 대신, 시스템은 고정된 횟수의 시도 $\tau$ 동안 각 문제를 시도합니다 (최적의 경우 $\tau=1$, 즉 매 시도마다 리셋).
2. 폐기 (Discard): $\tau$번의 시도 내에 문제가 해결되면, 해당 문제는 즉시 큐(queue)에서 제거됩니다.
3. 순환 (Rotation): $\tau$번의 시도 후에도 문제가 해결되지 않으면, 해당 문제는 큐의 맨 뒤로 이동하며 시스템은 즉시 다음 가용 문제로 넘어갑니다.

이론적 프레임워크

본 논문은 재생 이론(renewal theory)을 사용하여 pass@k와 coverage@cost 사이의 수학적 매핑을 확립합니다.

• 표준 정책: 난이도 분포가 $P(p) \sim p^{\alpha-1}$인 경우(이는 멱법칙 pass@k를 유도함), 문제를 해결하기 위한 평균 시도 횟수 $E[T]$는 $\alpha < 1$일 때 발산합니다. 결과적으로 coverage@cost는 아래선형적으로 성장합니다 ($\propto t^\alpha$).
• ReD 정책: $\tau$번의 시도마다 리셋함으로써, 문제를 해결하기 위한 유효 시도 횟수 $E[T_\tau]$는 기저의 난이도 분포와 관계없이 유한해집니다.
  • $0 < \alpha < 1$인 경우, ReD는 coverage@cost의 성장을 아래선형에서 선형($\propto t$)으로 전환합니다.
  • $\alpha > 1$인 경우, ReD는 선형 성장을 유지하면서 표준 정책보다 더 가파른 기울기(더 높은 효율성)를 가집니다.
• 최적성: 저자들은 어떤 난이도 분포에 대해서도 $\tau=1$로 리셋하는 것이 문제를 해결하기 위한 평균 시도 횟수를 최소화하는 최적의 전략임을 증명합니다. 이는 거짓 음성(False Negative)과 거짓 양성(False Positive) 비율의 합이 1 미만인 불완전한 검증기(verifier)가 있는 경우에도 유효합니다.

스케일링 법칙의 추론

또한 본 논문은 ReD 궤적을 사용하여 비용이 많이 드는 대규모 $k$ 평가 없이도 멱법칙 지수 $\alpha$를 추론할 수 있음을 보여줍니다. ReD가 라운드를 거치며 진행됨에 따라, 해결되지 않은 남은 문제들의 분포는 베타 분포(Beta distribution)로 수렴합니다. 라운드 간 남은 문제의 비율 $\langle R_n \rangle / \langle R_{n+1} - R_n \rangle$을 분석함으로써 $\alpha$를 선형적으로 추정할 수 있습니다.

주요 기여

1. 메트릭 연결: pass@k와 coverage@cost 사이의 정확한 매핑을 도출하여, 멱법칙 pass@k 동작($0 < \alpha < 1$)이 어떻게 표준 할당 방식에서 아래선형 성장을 유도하는지 규명했습니다.
2. ReD 알고리즘: Reset-and-Discard 전략의 최적성을 제안하고 증명했습니다. 이는 $\alpha < 1$에 대해 coverage@cost의 선형 성장을 보장하며, $\alpha > 1$일 때 효율성을 개선합니다.
3. 이론적 보장: ReD가 난이도 분포에 관계없이 시도당 기대 보상을 엄격하게 최대화하며, 검증기 노이즈에 대해 견고함을 입증했습니다.
4. 지수 추론: 비용이 많이 드는 대규모 $k$ 샘플링을 우회하여, ReD 실행으로부터 추론 스케일링 지수를 직접 추정하는 방법을 개발했습니다.
5. 실험적 검증: 세 가지 LLM(Llama-3.1-8b, Llama-3.3-70b, GPT-oss-20b)과 세 가지 벤치마크(HumanEval, GSM8K, MMLU-Pro)에 대해 상당한 개선 효과를 입증했습니다.

실험 결과

HumanEval(코딩), GSM8K(수학), MMLU-Pro(추론) 데이터셋에 대해 실험이 수행되었습니다.

• 효율성: ReD는 목표 커버리지에 도달하기 위해 solve-to-completion 방식에 비해 필요한 시도 횟수, 토큰 및 USD 비용을 크게 줄였습니다.
• 모델 비교: HumanEval 벤치마크에서, ReD를 적용한 작은 모델(Llama-3.1-8b)은 약 90% 커버리지까지 시도 횟수와 토큰 측면에서 훨씬 더 큰 모델(Llama-3.3-70b)의 표준 할당 방식보다 우수한 성능을 보였습니다. USD 비용 측면에서, 8b 모델에 적용된 ReD는 모든 커버리지 수준에서 가장 비용 효율적인 전략이었습니다.
• 스케일링 법칙 추론: 8b 모델에 ReD를 사용하여, 저자들은 고차원 $k$ pass@k 측정에서 도출된 지수와 일치하는 $\alpha \approx 0.34$의 멱법칙 지수를 성공적으로 추론했습니다.
• 견고성: 노이즈가 있는 검증기를 시뮬레이션했을 때도 ReD의 이점은 유지되었습니다.

의의 및 주장

본 논문은 ReD가 검증 가능한 작업에 대한 추론 컴퓨팅 할당 방식의 근본적인 변화를 제공한다고 주장합니다.

• "Pay-per-Token"에서 "Outcome-as-a-Service"로: ReD는 시스템이 수익 체감이 발생하는 어려운 인스턴스에 자원을 낭비하는 대신, "학습 가능성의 경계"(몇 번의 시도 내에 해결 가능한 문제들)에 컴퓨팅 자원을 집중할 수 있게 합니다.
• 계층적 라우팅: 이 방법론은 작은 모델이 ReD를 통해 대부분의 문제를 처리하고, 해결되지 않은 문제만 더 크고 비싼 모델으로 라우팅하는 효율적인 하이브리드 전략을 지원합니다.
• 일반적 적용 가능성: 이 접근 방식은 반복적인 샘플링과 검증을 지원하는 모든 파이프라인에 적용 가능하며, 모델 아키텍처나 학습의 변경 없이도 입증된 처리량 향상을 제공합니다.

저자들은 ReD가 해결의 정답 여부를 자동으로 평가할 수 있는 검증 가능한 작업에 특화되어 설계되었음을 명시하며 범위를 신중하게 제한했습니다. 이들은 비검증 생성 작업에 대한 적용 가능성을 주장하거나, 학습된 난이도 예측기를 통합하는 방식을 본 연구의 일부로 제안하지 않습니다.