Certifying When to Stop: Exact Early Stopping for PRM-Based Reasoning Selection

Selecting among generated reasoning traces with a process reward model (PRM) usually requires scoring every trace, even when the remaining scores cannot change the selected answer. We introduce exact sequential certification, a training-free procedure that avoids such redundant verification without changing the output of the full, verify-all selector. The method reveals PRM scores incrementally and maintains lower and upper bounds on the final PRM-weighted vote of each answer group. It stops once one group's lower bound strictly exceeds every competitor's upper bound; if this never occurs, it scores all traces and applies the original selector. The returned answer is therefore identical to verify-all for any reveal order and positive batch size. Across seven mathematics benchmarks and $k\in \{4,8,16,32\}$, all fully evaluated policies produce zero answer mismatches on the same $6,628$ item–configuration cells. With leader-first ordering and batch size one, the method reduces PRM calls by $54.8\%$, estimated PRM tokens by $54.6\%$, and estimated end-to-end tokens by $29.4\%$ under the audited aggregate accounting. At $k=32$, it averages $2.38$–$18.26$ PRM calls instead of $32$ and saves $22.9$–$52.6\%$ end-to-end tokens across benchmarks. A matched audit of three additional 7B generator pools likewise finds zero mismatches over $4,788$ generator–item–budget cells and $19.4$–$52.7\%$ end-to-end savings at $k=32$. Exact unanimity, including the corresponding branch of Sensitivity-Aware Verification Allocation (SAVA), is the zero-call special case of the certificate.