RewardPartial: A Completion Potential Evaluation Framework for Truncated Best-of-N Paradigm
Abstract
AbstractTraditional decoding-time alignment methods, such as Best-of-N sampling, enhance output quality by selecting high-reward responses from multiple candidates. However, these approaches incur substantial computational overhead, which limits their practicality. Recent advances aim to mitigate this inefficiency by scoring and filtering partial generations early in the decoding process. However, these methods face a critical challenge: conventional reward models (RMs), optimized to assess complete responses, exhibit poor performance when evaluating truncated text. To address this, we introduce RewardPartial, a novel evaluation paradigm that shifts the focus from superficial partial-text quality to estimating a response’s completion potential. We provide theoretical analysis for this paradigm through the perspective of Markov Decision Process and construct TruncEval, a specialized dataset for training RewardPartial models to accurately predict this potential. Our evaluation on the TruncEval test set demonstrates that RewardPartial models deliver significant performance gains over conventional reward models. When deployed in early-filtering pipelines, our method achieves superior alignment performance compared to Best-of-N sampling, offering a more efficient solution for high-quality text generation.