Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910046063951872 |
|---|---|
| author | Golowich, Noah Chen, Fan Rohatgi, Dhruv Singhal, Raghav Domingo-Enrich, Carles Foster, Dylan J. Krishnamurthy, Akshay |
| author_facet | Golowich, Noah Chen, Fan Rohatgi, Dhruv Singhal, Raghav Domingo-Enrich, Carles Foster, Dylan J. Krishnamurthy, Akshay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_07887 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference Golowich, Noah Chen, Fan Rohatgi, Dhruv Singhal, Raghav Domingo-Enrich, Carles Foster, Dylan J. Krishnamurthy, Akshay Machine Learning Artificial Intelligence Computation and Language Statistics Theory 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. |
| title | Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference |
| topic | Machine Learning Artificial Intelligence Computation and Language Statistics Theory |
| url | https://arxiv.org/abs/2603.07887 |