# Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking

arXiv: https://arxiv.org/abs/2510.03149 · HTML: https://mlsanity.com/paper/2510.03149/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- First posted on arXiv 3 Oct 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Built on by (most cited first, 14 of 14)

- [PivotRL: High Accuracy Agentic Post-Training at Low Compute Cost](https://mlsanity.com/paper/2603.21383/) (2026)
- [On the Power of (Approximate) Reward Models for Inference-Time Scaling](https://mlsanity.com/paper/2602.01381/) (2026)
- [Steering diffusion models with quadratic rewards: a fine-grained analysis](https://mlsanity.com/paper/2602.16570/) (2026)
- [Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum](https://mlsanity.com/paper/2603.18325/) (2026)
- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification](https://mlsanity.com/paper/2605.17609/) (2026)
- [Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently](https://mlsanity.com/paper/2606.22938/) (2026)
- [Temper-Then-Tilt: Principled Unlearning for Generative Models through Tempering and Classifier Guidance](https://mlsanity.com/paper/2602.10217/) (2026)
- [The Power of Test-Time Training for Approximate Sampling](https://mlsanity.com/paper/2606.11437/) (2026)
- [VGB for Masked Diffusion Model: Efficient Test-time Scaling for Reward Satisfaction and Sample Editing](https://mlsanity.com/paper/2606.28301/) (2026)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)
- [Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models](https://mlsanity.com/paper/2603.22784/) (2026)
- [PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search](https://mlsanity.com/paper/2604.14345/) (2026)
- [Uniform Race: Parameter-Free Approximate Rejection Sampling](https://mlsanity.com/paper/2609.34639/) (2026)

## Abstract (arXiv)

Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for eliciting new reasoning capabilities, but the algorithmic design space and computational scaling properties of such approaches are still opaque, and their benefits are far from apparent when one accounts for the cost of learning a high-quality verifier. Our starting point is the observation that seemingly benign errors in a learned verifier can lead to catastrophic failures for standard decoding techniques due to error amplification during the course of generation. We then ask: can this be improved with more sophisticated decoding strategies? We introduce a new process-guided test-time sampling algorithm, VGB, which uses theoretically grounded backtracking to achieve provably better robustness to verifier errors. VGB interprets autoregressive generation as a random walk on a tree of partial generations, with transition probabilities guided by the process verifier and base model; crucially, backtracking occurs probabilistically. This process generalizes the seminal Sinclair-Jerrum random walk (Sinclair & Jerrum, 1989) from the literature on approximate counting and sampling in theoretical computer science, and a conceptual contribution of our work is to highlight parallels with this literature. Empirically, we demonstrate on both synthetic and real language modeling tasks that VGB outperforms baselines on a variety of metrics.