더 많은 추론 시간은 오히려 해가 될 수 있습니다: LLM 빔 서치의 과대 추정 편향

More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

더 넓은 빔 서치는 LLM의 추론 능력을 향상시켜야 하지만, 언제까지 빔 폭을 넓혀야 할까요? 기존의 빔 폭 선택 연구는 추론 효율성에 초점을 맞추어 왔습니다 extit{[참고 문헌]}, 하지만 더 넓은 검색이 출력 품질을 extit{악화시킬} 수 있는지에 대한 분석은 부족했습니다. 본 연구에서는 극단값 이론에 기반하여 이 질문에 대한 분석을 제시합니다. 노이즈가 많은 스코어링 결과에 대한 빔 선택은 후보 집합 크기가 증가함에 따라 체계적인 과대 추정 편향을 유발하며, 이 편향으로 인해 성능이 저하되는 최대 유효 빔 폭 $\hat{k}$를 도출했습니다. 이 중요한 빔 폭은 스코어러의 신호 대 잡음 비율에 따라 달라지며, $\hat{k}$는 올바른 경로와 잘못된 경로 간의 품질 차이 $\Delta (>0)$와 스코어러의 노이즈 $\sigma$에 따라 지수적으로 증가합니다. 우리는 세 개의 7B 파라미터 모델과 MR-BEN 데이터셋(5,975개 질문)의 열 가지 도메인에서 퍼플렉서티 기반 빔 서치와 PRM 기반 빔 서치를 비교하여 이 이론을 검증했습니다. 높은 노이즈를 갖는 퍼플렉서티 스코어링은 $\hat{k} = 1$을 나타내며, 테스트된 모든 빔 폭에서 검색이 이점을 제공하지 못합니다. 반면, 낮은 노이즈를 갖는 PRM 스코어링은 $\hat{k} \geq 4$를 나타내며, 최대 8.9%p의 성능 향상을 보였습니다. 동일한 모델과 알고리즘을 사용했지만, 스코어러가 다르면 $\hat{k}$ 값이 빔 폭 범위의 반대 끝에 위치합니다. 본 연구는 스코어러의 신호 대 잡음 비율이 빔 폭 선택을 결정하는 핵심 요소임을 밝히고, 실제 빔 폭 선택을 위한 진단 지표를 제안합니다.

Wider beam search should improve LLM reasoning, but when should you stop widening? Prior work on beam width selection has focused on inference efficiency \citep{qin2025dsbd, freitag2017beam}, without analyzing whether wider search can \emph{hurt} output quality. We present an analysis, grounded in Extreme Value Theory, that answers this question. Beam selection over noisy scorer outputs introduces a systematic overestimation bias that grows with the candidate pool size, and we derive a maximum useful beam width $\hat{k}$ beyond which search degrades performance. This critical width depends on the signal-to-noise ratio of the scorer: $\hat{k}$ grows exponentially with $(Δ/σ)^2$, where $Δ> 0$ is the quality advantage of correct paths over incorrect ones and $σ$ is the scorer noise. We validate this theory by comparing perplexity-guided and PRM-guided beam search across three 7B-parameter models and ten domains on MR-BEN (5,975 questions). Perplexity scoring, with its high noise, yields $\hat{k} = 1$: search provides no benefit at any width tested. PRM scoring, with lower noise, yields $\hat{k} \geq 4$, with gains of up to 8.9 percentage points. The same model, the same algorithm, but different scorers place $\hat{k}$ at opposite ends of the beam width range. Our analysis identifies the scorer's signal-to-noise ratio as the key quantity governing beam width selection, and we propose diagnostic indicators for choosing the beam width in practice.