# On the Power of (Approximate) Reward Models for Inference-Time Scaling

arXiv: https://arxiv.org/abs/2602.01381 · HTML: https://mlsanity.com/paper/2602.01381/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 30 of its 33 references that are in the map.
- First posted on arXiv 1 Feb 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 30 of 30)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review](https://mlsanity.com/paper/1805.00909/) (2018)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding](https://mlsanity.com/paper/2408.08252/) (2024)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systems](https://mlsanity.com/paper/2504.09037/) (2025)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2404.17546/) (2024)
- [Reasoning with Sampling: Your Base Model is Smarter Than You Think](https://mlsanity.com/paper/2510.14901/) (2025)
- [Inference-Time Alignment in Diffusion Models with Reward-Guided Generation: Tutorial and Review](https://mlsanity.com/paper/2501.09685/) (2025)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Efficient (Soft) Q-Learning for Text Generation with Limited Good Data](https://mlsanity.com/paper/2106.07704/) (2021)
- [Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration](https://mlsanity.com/paper/2503.07453/) (2025)
- [Hypothesis-Driven Theory-of-Mind Reasoning for Large Language Models](https://mlsanity.com/paper/2502.11881/) (2025)
- [SIXO: Smoothing Inference with Twisted Objectives](https://mlsanity.com/paper/2206.05952/) (2022)
- [Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2410.01920/) (2024)
- [Critic Sequential Monte Carlo](https://mlsanity.com/paper/2205.15460/) (2022)
- [Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking](https://mlsanity.com/paper/2510.03149/) (2025)
- [Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey](https://mlsanity.com/paper/2510.01925/) (2025)

## Built on by (most cited first, 7 of 7)

- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [SURGE: Approximation and Training Free Particle Filter for Diffusion Surrogate](https://mlsanity.com/paper/2605.18745/) (2026)
- [Simple Approximation and Derivative Free Inference-Time Scaling for Diffusion Models via Sequential Monte Carlo on Path Measures](https://mlsanity.com/paper/2605.17850/) (2026)
- [The Power of Test-Time Training for Approximate Sampling](https://mlsanity.com/paper/2606.11437/) (2026)
- [FluxLite: Inference-Time Proposal Control for Discrete Diffusion Models](https://mlsanity.com/paper/2609.35947/) (2026)
- [Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees](https://mlsanity.com/paper/2610.17579/) (2026)
- [Decoupled Marginal Sharpening for Training-Free Inference-Time Scaling](https://mlsanity.com/paper/2610.20483/) (2026)

## Abstract (arXiv)

Inference-time scaling has recently emerged as a powerful paradigm for improving the reasoning capability of large language models. Among various approaches, 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 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 approximate reward models, raising a fundamental question: Why and when do approximate reward models suffice for effective inference-time scaling? In this work, we provide a theoretical answer. We identify the 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 exponential improvement in inference efficiency despite using only approximate rewards.