Reproduce “Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Noah Golowich, Fan Chen, Dhruv Rohatgi, Raghav Singhal, Carles Domingo-Enrich, Dylan J. Foster, Akshay Krishnamurthy
The authors analyze sequential Monte Carlo (SMC) for steering partial solutions toward high-reward answers using process reward model scores. They prove sampling guarantees under coverage and value-estimation conditions, and introduce rejection-sampling SMC, which is exact with one particle when the value function is exact. On Math500, SMC beats Best-of-N on most, but not all, problems; sampling error need not predict accuracy.
Key insights
- The accuracy of SMC in sampling from a target distribution is provably dependent on the 'action-level coverage' (how much the target distribution deviates from the reference model) and the $\chi^2$-divergence of the Process Reward Model (PRM).
- Standard SMC inherently requires $\Omega(\sqrt{H})$ particles for non-trivial accuracy, even with a perfect PRM; SMC-RS, by incorporating rejection sampling, can overcome this, achieving $o(1)$ sampling error with $O(1)$ particles for near-perfect PRMs.
- Myopic particle filtering algorithms have a fundamental lower bound, requiring at least $\Omega(\log H / \log \log H)$ particles, suggesting inherent computational complexity or the need for non-myopic strategies.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.