Research map / Large language models / Reasoning and chain of thought

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes VGB, a value-guided sampler that performs a lazy Sinclair-Jerrum-style random walk with stochastic backtracking over the generation tree, proving robustness to imperfect process verifiers (value functions) where action-level rejection sampling amplifies errors.

Problem

Learned process verifiers (approximate value functions) are imperfect, and errors compound over long generation horizons when using standard decoding/sampling such as action-level rejection sampling, which can fail catastrophically for test-time alignment.

Approach

Views autoregressive generation as a random walk on the tree of partial generations, with transitions guided by the base model and approximate value function, allowing probabilistic backtracking; generalizes the Sinclair-Jerrum random walk so the stationary distribution matches the tilted target at leaves, with guarantees under uniform and average-case value error.

Key results

• On the ABC task, VGB incurs lower KL-divergence to the target than ActionLevelRS, with benefits growing with horizon H.
• On the Python test case task, VGB substantially improves over ActionLevelRS on test-case length histogram error (69.75 vs 92.20) and is comparable on other metrics.
• On letter avoidance, VGB achieves superior coherence (GPT-4o-mini winrate) and log-probabilities over ActionLevelRS across a range of backtracking weights alpha.

Surprising findings

• Action-level rejection sampling with a small multiplicative value error can degrade catastrophically with horizon, with TV distance growing as sqrt(H) times error.

Limitations

• Runtime overall O~(H^3) to output a leaf, with quadratic/cubic overhead in horizon
• Requires non-trivial value-function approximation and tail control of errors; alternative error conditions are insufficient
• Practical implementation uses heuristics (stop at leaf, heuristic rejection sampling), which can bias the distribution

Experimental setup

Datasets: Dyck grammar sequences (synthetic) Python test case generation prompts

Benchmarks: ABC task parity task Dyck grammar Python test case generation letter avoidance

Metrics: KL divergence accuracy diversity (number of correct responses) l1 distributional error length histogram error type histogram error fraction distinct generations winrate coherence log-probability

Baselines: ActionLevelRS OutcomeLevelRS Block Best-of-N Block Rejection Sampling locally constrained decoding beam search

Builds on: Sinclair-Jerrum random walk action-level rejection sampling locally constrained decoding

Closest papers by meaning

• On the Query Complexity of Verifier-Assisted Language Generation (ICML 2025 · similarity 0.88)
• Variation in Verification: Understanding Verification Dynamics in Large Language Models (ICLR 2026 · similarity 0.88)
• GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning (AAAI 2026 · similarity 0.88)
• Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression (ICML 2026 · similarity 0.87)
• Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning (ICLR 2025 · similarity 0.87)
• Consilience for Verifier-Free Test-Time Scaling (NeurIPS 2026 · similarity 0.87)