Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking

• URL: http://arxiv.org/abs/2510.03149v1
• Date: Fri, 03 Oct 2025 16:21:14 GMT
• Title: Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
• Authors: Dhruv Rohatgi, Abhishek Shetty, Donya Saless, Yuchen Li, Ankur Moitra, Andrej Risteski, Dylan J. Foster,
• Abstract summary: Test-time algorithms that combine the generative power of language models with process verifiers offer a promising lever for eliciting new reasoning capabilities.<n>We introduce a new process-guided test-time sampling algorithm, VGB, which uses theoretically grounded backtracking to achieve provably better robustness to verifier errors.
• Score: 54.43083499412643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• PROMISE: Process Reward Models Unlock Test-Time Scaling Laws in Generative Recommendations [52.67948063133533]
  Generative Recommendation has emerged as a promising paradigm, reformulating recommendation as a sequence-to-sequence generation task over hierarchical Semantic IDs.<n>Existing methods suffer from a critical issue we term Semantic Drift, where errors in early, high-level tokens irreversibly divert the generation trajectory into irrelevant semantic subspaces.<n>We propose Promise, a novel framework that integrates dense, step-by-step verification into generative models.
  arXiv  Detail & Related papers  (2026-01-08T07:38:46Z)
• The Double Life of Code World Models: Provably Unmasking Malicious Behavior Through Execution Traces [0.0]
  Large language models (LLMs) increasingly generate code with minimal human oversight.<n>We present a novel AI control framework that verifies untrusted code-generating models through semantic analysis.
  arXiv  Detail & Related papers  (2025-12-15T19:05:37Z)
• VERIRL: Boosting the LLM-based Verilog Code Generation via Reinforcement Learning [32.974199255760944]
  We introduce a reinforcement learning framework tailored for Verilog code generation.<n>To tackle the problem of sparse and noisy reward signals, we propose a Trace-back based Rescore mechanism.<n>To mitigate catastrophic forgetting and overfitting during RL fine-tuning, we introduce a sample-balanced weighting strategy.
  arXiv  Detail & Related papers  (2025-08-25T20:20:44Z)
• Taming Polysemanticity in LLMs: Provable Feature Recovery via Sparse Autoencoders [50.52694757593443]
  Existing SAE training algorithms often lack rigorous mathematical guarantees and suffer from practical limitations.<n>We first propose a novel statistical framework for the feature recovery problem, which includes a new notion of feature identifiability.<n>We introduce a new SAE training algorithm based on bias adaptation'', a technique that adaptively adjusts neural network bias parameters to ensure appropriate activation sparsity.
  arXiv  Detail & Related papers  (2025-06-16T20:58:05Z)
• Exploring Training and Inference Scaling Laws in Generative Retrieval [50.82554729023865]
  Generative retrieval reformulates retrieval as an autoregressive generation task, where large language models generate target documents directly from a query.<n>We systematically investigate training and inference scaling laws in generative retrieval, exploring how model size, training data scale, and inference-time compute jointly influence performance.
  arXiv  Detail & Related papers  (2025-03-24T17:59:03Z)
• Learning to Solve and Verify: A Self-Play Framework for Code and Test Generation [69.62857948698436]
  Recent advances in large language models (LLMs) have improved their performance on coding benchmarks.<n>However, improvement is plateauing due to the exhaustion of readily available high-quality data.<n>We propose Sol-Ver, a self-play solver-verifier framework that jointly improves a single model's code and test generation capacity.
  arXiv  Detail & Related papers  (2025-02-20T18:32:19Z)
• On the Query Complexity of Verifier-Assisted Language Generation [35.43462431990329]
  We develop a framework for reasoning about constrained generation using a pre-trained language model generator oracle.<n>Access to a verifier can render an intractable problem (information-theoretically or computationally) to a tractable one.<n>We show even simple algorithms, like tokenwise rejection sampling, can enjoy significant benefits from access to a verifier.
  arXiv  Detail & Related papers  (2025-02-17T18:46:32Z)
• BRiTE: Bootstrapping Reinforced Thinking Process to Enhance Language Model Reasoning [78.63421517563056]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in complex reasoning tasks.<n>We present a unified probabilistic framework that formalizes LLM reasoning through a novel graphical model.<n>We introduce the Bootstrapping Reinforced Thinking Process (BRiTE) algorithm, which works in two steps.
  arXiv  Detail & Related papers  (2025-01-31T02:39:07Z)
• Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines [74.42485647685272]
  We focus on Generative Masked Language Models (GMLMs) We train a model to fit conditional probabilities of the data distribution via masking, which are subsequently used as inputs to a Markov Chain to draw samples from the model. We adapt the T5 model for iteratively-refined parallel decoding, achieving 2-3x speedup in machine translation with minimal sacrifice in quality.
  arXiv  Detail & Related papers  (2024-07-22T18:00:00Z)
• Quantifying Contamination in Evaluating Code Generation Capabilities of Language Models [27.24738197172374]
  Large language models have achieved remarkable performance on various code generation benchmarks. There have been growing concerns regarding potential contamination of these benchmarks as they may be leaked into pretraining and finetuning data. We show that there are substantial overlap between popular code generation benchmarks and open training corpus, and models perform significantly better on the subset of the benchmarks where similar solutions are seen during training.
  arXiv  Detail & Related papers  (2024-03-06T21:45:35Z)
• On the Reliability and Explainability of Language Models for Program Generation [15.569926313298337]
  We study the capabilities and limitations of automated program generation approaches. We employ advanced explainable AI approaches to highlight the tokens that significantly contribute to the code transformation. Our analysis reveals that, in various experimental scenarios, language models can recognize code grammar and structural information, but they exhibit limited robustness to changes in input sequences.
  arXiv  Detail & Related papers  (2023-02-19T14:59:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.