On the Power of (Approximate) Reward Models for Inference-Time Scaling: Sequential Monte Carlo and Beyond

Inference-time scaling has recently emerged as a powerful paradigm for improving the reasoning capability of large language models. Among various approaches, \emph{Sequential Monte Carlo (SMC)} has become a particularly important framework, enabling iterative generation, evaluation, rejection, and resampling of intermediate reasoning trajectories. A central component in this process is the \emph{reward model}, which evaluates partial solutions and guides the allocation of computation during inference. However, in practice, true reward models are never available. All deployed systems rely on \emph{approximate reward models}, raising a fundamental question: \emph{Why and when do approximate reward models suffice for effective inference-time scaling?} In this work, we provide a theoretical answer. We identify the \emph{Bellman error} of the approximate reward model as the key quantity governing the effectiveness of SMC-based inference-time scaling. For a reasoning process of length $T$, we show that if the Bellman error of the approximate reward model is bounded by $O(1/T)$, then combining this reward model with SMC reduces the computational complexity of reasoning from exponential in $T$ to polynomial in $T$. This yields an \emph{exponential improvement} in inference efficiency despite using only approximate rewards.

Large language models can often solve harder problems by spending more computation at test time: instead of producing only one answer, they generate many possible reasoning paths, compare partial solutions along the way, and focus more effort on the most promising ones. A key component in this process is a scoring model that judges whether a partial reasoning path looks useful. In practice, however, such scoring models are never perfect. They are learned from data and inevitably make mistakes. This raises an important question: why can imperfect scoring models still help language models reason more efficiently? This paper gives a theoretical answer for a class of inference-time algorithms that repeatedly generate, score, discard, and copy candidate reasoning paths. We identify the kind of scoring error that matters most and show that if this error is small enough at each reasoning step, then the amount of computation needed can drop from growing exponentially with the reasoning length to growing only polynomially. In other words, even approximate scoring models can provide a dramatic efficiency gain, as long as their step-by-step errors are sufficiently controlled.