[arXiv 2026] Reject, Resample, Repeat: The First Non-Asymptotic Theory for Parallel LLM Reasoning

TL;DR

Why does "thinking longer" or sampling more branches help LLMs solve hard problems? This paper provides the first rigorous mathematical answer by treating LLM inference as a particle filtering problem. It introduces SMC-RS, a new algorithm that handles imperfect reward models better than standard sampling, and proves that all current "myopic" search methods have a fundamental limit that can only be broken by looking ahead.

Background: Beyond Ad-hoc Scaling

We've seen models like o1 or DeepSeek-V3 exploit "inference-time compute," but the community has lacked a principled way to measure the trade-off between the number of samples (cost) and the quality of the result (accuracy). Most current techniques—like Best-of-N or simple tree searches—are heuristic. The authors bridge this gap by mapping LLM generation onto the Sequential Monte Carlo (SMC) framework, a classic tool in robotics and statistics, now repurposed for the discrete manifold of language.

The Problem: The "Imperfect Oracle" Trap

The core challenge is the Process Reward Model (PRM). We use PRMs to score partial thoughts, but PRMs are never perfect. If a PRM is slightly off at step 10, that error compounds by step 100. Previous work on "backtracking" tried to fix this, but it was slow and sequential. This paper asks: Can we achieve the same robustness with parallel sampling?

Methodology: The Anatomy of Success

The paper identifies two numbers that govern whether your LLM sampling will actually work:

1. Action-level Coverage ($C_{act}$): How much the "true" answer distribution differs from your base model's raw output at each token.
2. ${\chi }^2$-Diverence: A measure of how "wrong" your PRM is compared to the true reward.

The authors prove a powerful theorem: the error of SMC decays at a rate of $H/\sqrt{N}$, where $H$ is the length of the text and $N$ is the number of parallel samples.

Introducing SMC-RS (Rejection Sampling)

Standard SMC has a flaw: when you resample, particles "interfere" with each other through normalization. The authors propose SMC-RS, which uses local rejection sampling. This allows the model to succeed even with very few particles if the PRM is high-quality—a feat standard SMC cannot achieve.

Figure 1: Comparison of SMC vs. Best-of-N on Math500. Most points fall below the $y=x$ line, proving SMC's superior efficiency per unit of compute.

Experiments: Theory Meets Math500

The researchers tested their theory on the Math500 and AIME benchmarks using a Qwen-2.5-1B base model and a 7B PRM.

• Consistency: SMC outperformed the standard "Best-of-N" baseline across almost all problem types.
• The Divergence Paradox: Interestingly, the authors found that sometimes a higher divergence (more aggressive PRM scoring) actually led to higher accuracy, suggesting that for hard math, "weeding out" bad thoughts is more important than perfectly approximating the reward distribution.

Figure 2: Empirical validation showing how Action-level Coverage and KL-Divergence accurately predict the sampling error of the model.

Critical Insight: The Myopic Limit

Perhaps the most profound theoretical contribution is Theorem 3.9. The authors prove that any "myopic" method (one that only looks at current rewards and doesn't "look ahead" to the end of the sentence) requires at least $\Omega (\log H/\log \log H)$ particles to remain accurate. Takeaway: To truly scale inference compute to the next level, we must move beyond simple step-by-step resampling and develop models that can anticipate future rewards.

Conclusion

This work transforms inference-time steering from a "black art" of prompting and resampling into a rigorous discipline of particle filtering. By identifying the specific bottlenecks (Horizon $H$ and Coverage $C_{act}$), it provides a roadmap for building more compute-efficient reasoners that don't just "repeat" samples, but intelligently "reject and resample" their way to the truth.