거부, 재샘플링, 반복: 언어 모델 추론에서의 병렬 추론 이해

Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference

추론 시에 여러 샘플을 집계하고 제거하는 방법은 대규모 언어 모델을 제어하는 강력한 패러다임으로 부상했지만, 이러한 방법들의 정확성-비용 균형에 대한 체계적인 이해는 부족합니다. 본 논문에서는 순차적 몬테카를로(SMC)와 같은 *입자 필터링* 알고리즘의 관점에서 이러한 접근 방식을 엄밀하게 연구할 수 있는 방법을 제시합니다. 기본 언어 모델과 예상되는 최종 보상을 추정하는 *프로세스 보상 모델*을 기반으로, 우리는 다음과 같은 질문을 던집니다. *주어진 수의 프로세스 보상 평가를 통해, 목표 분포에서 얼마나 정확하게 샘플링할 수 있을까요?* 이론적으로, 우리는 (1) SMC에 대한 비-점근적 보장을 가능하게 하는 간단한 기준, (2) SMC 알고리즘의 개선 사항, 그리고 (3) 모든 입자 필터링 방법이 직면하는 근본적인 한계를 밝혀냅니다. 실증적으로, 우리의 이론적 기준이 SMC의 *샘플링 오류*를 효과적으로 제어한다는 것을 보여주지만, 반드시 최종 *정확성*까지 제어하는 것은 아님을 입증했습니다. 이는 샘플링 외의 이론적 관점이 필요할 수 있음을 시사합니다.

Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of their accuracy-cost tradeoffs. In this paper, we introduce a route to rigorously study such approaches using the lens of *particle filtering* algorithms such as Sequential Monte Carlo (SMC). Given a base language model and a *process reward model* estimating expected terminal rewards, we ask: *how accurately can we sample from a target distribution given some number of process reward evaluations?* Theoretically, we identify (1) simple criteria enabling non-asymptotic guarantees for SMC; (2) algorithmic improvements to SMC; and (3) a fundamental limit faced by all particle filtering methods. Empirically, we demonstrate that our theoretical criteria effectively govern the *sampling error* of SMC, though not necessarily its final *accuracy*, suggesting that theoretical perspectives beyond sampling may be necessary.