Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference

This research paper investigates Sequential Monte Carlo (SMC) and other particle filtering algorithms as a theoretical framework for improving large language model (LLM) inference. The authors introduce a principled approach to analyze inference-time interventions, such as parallel reasoning and pruning, by utilizing process reward models to steer generation. Their findings establish non-asymptotic guarantees for SMC based on criteria like bounded action-level coverage and divergence between true and approximate reward distributions. To address limitations in standard SMC, they propose SMC with Rejection Sampling (SMC-RS), which maintains high accuracy even when reward models are nearly perfect. Empirically, the study demonstrates that...