mlsanityData to 7 Oct 2026

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

arXiv 2603.07887 ↗First posted 9 Mar 2026cs.LG cs.AI cs.CLcited by 2

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 36 of its 47 references that are in the map. First posted on arXiv 9 Mar 2026.

Builds on

36 of 47 references.

Closest ancestors · 9

Same direction, newest first

  1. 2026On the Power of (Approximate) Reward Models for Inference-Time Scaling1 Feb
  2. 2025On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference4 Dec
  3. 2025Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking3 Oct
  4. 2025Rethinking Thinking Tokens: LLMs as Improvement Operators1 Oct
  5. 2025Deep Think with Confidence21 Aug
  6. 2025Value-Guided Search for Efficient Chain-of-Thought Reasoning23 May
  7. 2025A*-Decoding: Token-Efficient Inference Scaling19 May
  8. 2025Self-Steering Language Models9 Apr
  9. 2025On the Query Complexity of Verifier-Assisted Language Generation17 Feb

Other references · 27

  1. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  2. 2023Let's Verify Step by Stepcited by 3,598
  3. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 946
  4. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 895
  5. 2025The Lessons of Developing Process Reward Models in Mathematical Reasoningcited by 402
  6. 2021FUDGE: Controlled Text Generation With Future Discriminatorscited by 374
  7. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  8. 2025A General Framework for Inference-time Scaling and Steering of Diffusion Modelscited by 201
  9. 2023Controlled Decoding from Language Modelscited by 133
  10. 2025ReSum: Unlocking Long-Horizon Search Intelligence via Context Summarizationcited by 132
  11. 2024Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Modelscited by 91
  12. 2024Probabilistic Inference in Language Models via Twisted Sequential Monte Carlocited by 85
15 more
  1. 2025Feynman-Kac Correctors in Diffusion: Annealing, Guidance, and Product of Expertscited by 85
  2. 2025Reasoning with Sampling: Your Base Model is Smarter Than You Thinkcited by 84
  3. 2023Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programscited by 79
  4. 2025The Majority is not always right: RL training for solution aggregationcited by 46
  5. 2025Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlocited by 45
  6. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
  7. 2025The Coverage Principle: How Pre-Training Enables Post-Trainingcited by 25
  8. 2022SIXO: Smoothing Inference with Twisted Objectivescited by 22
  9. 2024From Calculation to Adjudication: Examining LLM judges on Mathematical Reasoning Taskscited by 22
  10. 2024Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlocited by 21
  11. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 20
  12. 2025Guided Speculative Inference for Efficient Test-Time Alignment of LLMscited by 9
  13. 2016High-dimensional Filtering using Nested Sequential Monte Carlocited by 8
  14. 2025Sequences of Logits Reveal the Low Rank Structure of Language Modelscited by 8
  15. 2024Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decompositioncited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Explorationcited by 0
  2. 2026Characterizing a Configuration Where Inference-Time PRM-Pruned Fragment Grafting Is Inert: Evidence from Three Reasoning LMscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Self-Rewarding Sequential Monte Carlo for Masked Diffusion Language Models
  2. 2026Sample Where You Struggle: Sharpening Base Model Reasoning via Entropy-Guided Power Sampling
  3. 2025Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods
  4. 2026Discrete Diffusion Inference-Time Control with Nested Sequential Monte Carlo
  5. 2025When Life Gives You Samples: The Benefits of Scaling up Inference Compute for Multilingual LLMs
  6. 2025Mitigating Premature Exploitation in Particle-based Monte Carlo for Inference-Time Scaling
  7. 2026Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models
  8. 2024Keep Guessing? When Considering Inference Scaling, Mind the Baselines