From Coverage to Accuracy: Making Independent Sampling Competitive with Guided Search

Verifier-guided search can raise accuracy while narrowing generation onto a few reasoning paths. We ask how that narrowing changes the answer a method returns, separating coverage (a correct answer is in the pool) from selection (the decision rule returns it). On GSM8K and MATH, independent sampling covers correct answers about as often as guided search, yet turns less of that coverage into correct votes: on MATH it leads guided coverage by 6 to 11 points while its vote trails by 12 to 14. Guidance raises the share of correct candidates, and it makes wrong answers agree more often. Conditional comparisons and controlled answer-group interventions show the agreement can outweigh the enrichment for a correct minority, even while guidance lifts the vote overall. This points to improving selection as an alternative to spending compute on guided generation. We introduce certified selective verification, which returns the exact weighted-voting winner for a fixed bounded score vector while scoring only the candidates needed to decide it. In live end-to-end runs it reproduces every full-verification decision using 70 to 83% fewer verifier tokens on GSM8K, 36 to 62% on MATH. Sweeping the pool size gives certified independent sampling competitive accuracy–compute trade-offs: it matches REBASE's best observed GSM8K accuracy at about a third less compute, and reaches higher observed accuracy on MATH (62.2% versus 60.3%) at 27% less compute.