Scalable Best-of-N Selection for Large Language Models via Self-Certainty

Best-of-N selection is a key technique for improving the reasoning performance of Large Language Models (LLMs) through increased test-time computation. Current state-of-the-art methods often employ computationally intensive reward models for response evaluation and selection. Reward-free alternatives, like self-consistency and universal self-consistency, are limited in their ability to handle open-ended generation tasks or scale effectively. To address these limitations, we propose self-certainty, a novel and efficient metric that leverages the inherent probability distribution of LLM outputs to estimate response quality without requiring external reward models. We hypothesize that higher distributional self-certainty, aggregated across multiple samples, correlates with improved response accuracy, as it reflects greater confidence in the generated output. Through extensive experiments on various reasoning tasks, we demonstrate that self-certainty (1) scales effectively with increasing sample size N, akin to reward models but without the computational overhead; (2) complements chain-of-thought, improving reasoning performance beyond greedy decoding; and (3) generalizes to open-ended tasks where traditional self-consistency methods fall short. Our findings establish self-certainty as a practical and efficient way for improving LLM reasoning capabilities. The code is available at https://github.com/backprop07/Self-Certainty

한 줄 요약

Self-certainty는 LLM의 내재적 확률 분포를 활용해 외부 보상 모델 없이도 Best-of-N 선택을 효율적으로 수행하는 새로운 메트릭이다.

핵심 기여도

Self-certainty는 KL 발산을 사용해 LLM 출력 분포와 균일 분포 간의 차이를 측정함으로써 응답의 신뢰도를 평가한다.
Borda Voting 기반의 가중치 부여 방식으로, (N - ranking + 1)^p 공식을 사용해 더 신뢰도 높은 응답에 높은 가중치를 부여한다.
GSM8K, MATH, LiveCodeBench 등 다양한 추론 태스크에서 Self-consistency 대비 성능 개선을 보인다.
N=16까지 확장 가능하며, USC와 달리 컨텍스트 길이 제약 없이 일반화 가능하다.

핵심 아이디어

기존 Self-consistency와 USC는 외부 보상 없이도 Best-of-N 선택을 수행하지만, 각각의 한계가 있다. Self-consistency는 문자열 일치 기반으로 동작하여 개방형 생성 태스크에 적용이 어렵고, USC는 컨텍스트 길이와 모델 크기에 따라 성능이 감소한다. 본 연구는 LLM이 생성한 토큰의 확률 분포가 내재적으로 신뢰도를 반영한다고 가정하고, 이를 Self-certainty로 정량화한다. 이 메트릭은 KL 발산을 사용해 분포가 균일 분포에서 얼마나 벗어났는지를 측정함으로써, 더 높은 신뢰도를 가진 응답을 선택한다. 이는 외부 보상 모델 없이도 확률 분포만으로 평가가 가능하다는 점에서 혁신적이다.

기술적 접근법

**Self-certainty**: KL 발산을 사용해 토큰 분포와 균일 분포 간의 차이를 측정.
**Borda Voting 기반 가중치 부여**: (N - ranking + 1)^p 공식을 사용해 높은 순위에 높은 가중치를 부여.
**데이터셋**: GSM8K, MATH, LiveCodeBench, CRUXEval, LiveBench-Math.
**샘플 크기 N**: 최대 N=16까지 실험.
**하이퍼파라미터**: 가중치 부여에 사용된 p 값은 실험적으로 결정됨.

주요 결과

**GSM8K**: Self-certainty 기반 Best-of-N 선택이 Self-consistency 대비 +2.3% 성능 향상.
**MATH**: N=16에서 Self-certainty가 Self-consistency 대비 +4.1% 개선.
**LiveCodeBench**: Self-certainty가 USC 대비 +3.8% 성능 향상.
**USC**: N=8에서 성능이 높지만 N=16에서 감소하는 반면, Self-certainty는 N 증가에 따라 안정적으로 성능 향상.

의의 및 한계

Self-certainty는 외부 보상 모델 없이도 Best-of-N 선택을 가능하게 하며, 특히 개방형 생성 태스크에서 Self-consistency와 USC의 한계를 극복한다. 또한, Borda Voting 기반의 가중치 부여 방식은 CoT 추론을 보완해 더 높은 정확도를 달성한다. 그러나 Self-certainty는 유일한 정답을 요구하는 문제에서는 Self-consistency보다 성능이 낮은 것으로 나타났다. 또한, 평균 함수 F와 가중치 분포 공식은 최적화 여지가 있으며, 다양한 형태의 F와 가중치 함수를 탐색할 필요가 있다.

실용적 활용

Self-certainty는 LLM의 추론 과정에서 외부 보상 모델 없이도 신뢰도 높은 응답을 선택할 수 있어, 추론 시간을 줄이고 계산 비용을 절감하는 데 유용하다. 특히, 코드 생성, 수학 문제 해결, 개방형 생성 등 다양한 분야에서 적용 가능하며, 데이터 라벨링 및 강화 학습에도 활용될 수 있다.