Reasoning search stops voting only after the fact: VGSC resamples steps during decoding and reaches 63.1% average accuracy
Synopsis
Test-time search for multi-step LLM reasoning has long traded between two imperfect signals: post-hoc voting keeps diversity but cannot steer generation toward correct paths, while beam-style verifier guidance intervenes early but over-concentrates and amplifies verifier errors. VGSC multiplies step-level correctness with a future-outcome prediction into an acceptance weight, applies bounded rejection-resampling to candidate steps during decoding, and keeps multiple trajectories for final self-consistency voting. Across five reasoning benchmarks with the Qwen2.5 Math 1.5B Instruct generator and Qwen2.5 Math PRM 7B verifier, VGSC reaches 63.1% average accuracy at verifier-trust exponent 10, above the strongest non-VGSC baseline BS+SC-Future at 60.7%.
Interpretation
Test-time reasoning gains a decoding mode in which the verifier no longer only ranks or reweights complete chains after generation, but takes part in deciding which candidate step to keep at each step. Post-hoc aggregation samples complete trajectories from the base model and uses the verifier only after generation, so it cannot recover when the generator rarely samples a correct trajectory; beam-style guidance intervenes during decoding, but deterministic pruning over-concentrates on a narrow trajectory set and amplifies verifier errors. On five benchmarks, MATH, OlympiadBench, ScienceQA, CommonsenseQA and Knights&Knaves, with the Qwen2.5 Math 1.5B Instruct generator and Qwen2.5 Math PRM 7B verifier, VGSC reaches 63.1% average accuracy at verifier-trust exponent 10, versus 60.7% for the strongest non-VGSC baseline BS+SC-Future and 59.4% for weighted self-consistency at a similar nominal budget.
At each step the base language model proposes candidate next steps, and an acceptance weight decides whether to take one; a rejected proposal is replaced by a new one until the per-step proposal cap is reached. The acceptance weight multiplies two probability-valued signals: the step verifier's probability that the current step is correct, and the future-outcome predictor's probability that the resulting prefix can reach a correct final answer, each raised to the verifier-trust exponent. The future-outcome predictor is initialized from the same PRM checkpoint and trains LoRA adapters only in the last four of its 28 Transformer layers, with labels from the fraction of 10 sampled continuations per PRM800K prefix that reach the correct answer; if every proposal in a step is rejected, one cached candidate is selected by weight, and fallback occurs in about one in ten decoding steps at trust exponent 5 and stays below two in ten under stronger guidance.
Perspective
The demonstrated scope is five reasoning benchmarks with extractable final answers: MATH and OlympiadBench for mathematics, ScienceQA for science, CommonsenseQA for commonsense, and Knights&Knaves for logic; the main experiments use the Qwen2.5 Math 1.5B Instruct generator with the Qwen2.5 Math PRM 7B verifier, and the appendix reports results for Llama 3.2 3B Instruct, Gemma3 4B Instruct and the ReProbe verifier family.
VGSC depends on the quality and task alignment of the learned guidance signals, and gains may be smaller when the verifier is weak, miscalibrated or poorly matched to the target domain, as the CommonsenseQA results with ReProbe illustrate; the verifier-trust exponent is a method-specific hyperparameter, and although a default range works well across datasets, the best setting may vary with verifier quality, generator behavior and task domain, so new settings may need validation or tuning.