Verify Until Decided: Exact Early Stopping for Weighted Voting

Test-time reasoning systems sample multiple solutions, score them with a verifier, and select the parsed answer with the largest aggregate score. Dense execution verifies every solution even when the remaining scores cannot change the decision. We introduce Verify Until Decided (VUD), a sparse executor that avoids unnecessary verification while preserving the weighted-vote decision. For a fixed candidate pool, VUD uses a tie-aware certificate that is necessary and sufficient for winner invariance under all bounded assignments to the unseen verifier scores. A signed certificate extends this guarantee to candidates not yet generated, while a deferred controller preserves the dense finite-budget decision without increasing candidate generation or verifier calls on any instance. Across three public 8–9B generators and six reasoning benchmarks, covering 2,304 model–question instances, VUD reproduces every dense ThinkPRM decision at N = 8 for the same verifier-score realization while using 52.4% fewer verifier calls than a matched dense executor. One full-matrix online pass reduces verifier-only wall time by 18.8–40.3% across three scorer interfaces. With CISC, FutureCert saves 15.3% of candidates, and the full two-layer executor saves 9.1–17.5% of generation-plus-scoring wall time across generators. Prospective ThinkPRM runs save up to 48.7% end-to-end wall time at N = 16. VUD changes execution, not the scoring rule, terminal budget, or decision for a fixed realization.