New sampler + verifier *drastically* improves tiny 0.5b model coding performance
Summary
The paper introduces VGB, a process-guided sampling algorithm with probabilistic backtracking, which significantly improves coding performance on tiny 0.5B models by being robust to verifier errors.
View Cached Full Text
Cached at: 06/25/26, 11:10 AM
# Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking Source: [https://arxiv.org/abs/2510.03149](https://arxiv.org/abs/2510.03149) [View PDF](https://arxiv.org/pdf/2510.03149) > 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\. ## Submission history From: Dhruv Rohatgi \[[view email](https://arxiv.org/show-email/1dd6f5a9/2510.03149)\] **\[v1\]**Fri, 3 Oct 2025 16:21:14 UTC \(525 KB\)
Similar Articles
2-bit copy in VRAM + exact residual in system RAM as the verifier: speculative decoding for models that don't fit your GPU
A hobbyist researcher proposes a speculative decoding scheme where a 2-bit model copy on GPU drafts tokens while the full residual (6-8 bit) in system RAM verifies them, only exchanging activations over PCIe. Early measurements suggest 2-bit + 8-bit residual outperforms Q8_0 quality and the 2-bit drafter beats Gemma 4's official drafter on acceptance rate.
Sample Where You Struggle: Sharpening Base Model Reasoning via Entropy-Guided Power Sampling
This paper introduces Entropy-Guided Power Sampling (EGPS), a training-free and verifier-free sampler that improves the efficiency of power sampling for enhancing base language model reasoning. EGPS achieves up to 12.6x speedup over standard Metropolis-Hastings sampling while reaching best or tied-best accuracy on benchmarks like MATH500, HumanEval, and GPQA.
@dair_ai: NEW paper worth reading. GPT-5.4 nano plus a critic-comparator orchestration loop hits 76.4% on SWE-bench Verified, mat…
A new paper shows that using a weak model with k=8 proposals and a critic-comparator selection loop can match frontier model performance on SWE-bench Verified, reaching 76.4% accuracy. The key insight is that correct patches are often already present in a weak model's top-k candidates, and the challenge is effective selection using execution verification.
ProVe: Proposer-Verifier Decoding
ProVe reverses speculative decoding roles by fine-tuning a large model to propose token blocks verified by a smaller or identical model, achieving up to 2.7x throughput with adjustable speed-accuracy tradeoffs across six benchmarks.
Open-sourced my deterministic coding agent kernel — same behavior from 1B to 500B models
Istar Code v5.0.0 is an open-sourced deterministic coding agent kernel that ensures consistent behavior across models from 1B to 500B parameters, using explicit rules, workflow phases, and verification gates.