Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference
This work provides a principled theoretical framework for understanding the accuracy-cost tradeoffs of parallel reasoning methods in language models, which is important for researchers and practitioners developing and applying these techniques. It is an incremental step towards a deeper understanding.
This paper investigates the accuracy-cost tradeoffs of inference-time methods that aggregate and prune multiple samples from large language models by framing them as particle filtering algorithms. It theoretically identifies criteria for non-asymptotic guarantees, proposes algorithmic improvements, and establishes a fundamental limit for these methods. Empirically, the theoretical criteria are shown to govern sampling error but not necessarily final accuracy.
Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of their accuracy-cost tradeoffs. In this paper, we introduce a route to rigorously study such approaches using the lens of *particle filtering* algorithms such as Sequential Monte Carlo (SMC). Given a base language model and a *process reward model* estimating expected terminal rewards, we ask: *how accurately can we sample from a target distribution given some number of process reward evaluations?* Theoretically, we identify (1) simple criteria enabling non-asymptotic guarantees for SMC; (2) algorithmic improvements to SMC; and (3) a fundamental limit faced by all particle filtering methods. Empirically, we demonstrate that our theoretical criteria effectively govern the *sampling error* of SMC, though not necessarily its final *accuracy*, suggesting that theoretical perspectives beyond sampling may be necessary.