acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 , all fully evaluated policies produce zero answer mismatches on the same item–configuration cells. With leader-first ordering and batch size one, the method reduces PRM calls by , estimated PRM tokens by , and estimated end-to-end tokens by under the audited aggregate accounting. At , it averages – PRM calls instead of and saves – end-to-end tokens across benchmarks. A matched audit of three additional 7B generator pools likewise finds zero mismatches over generator–item–budget cells and – end-to-end savings at . Exact unanimity, including the corresponding branch of Sensitivity-Aware Verification Allocation (SAVA), is the zero-call special case of the certificate.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, efficient inference, process reward models, answer selection, exact certification, early stopping

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_RTW3OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper reduces PRM evaluation on a fixed pool of reasoning traces while preserving the answer selected by full verification. It maintains lower and upper bounds on each answer group's weighted vote and stops once one group must win under every completion of the unseen scores. Otherwise it falls back to full verification. The certificate is training-free and independent of reveal order. Experiments measure answer agreement and verification savings across seven benchmarks, with additional generator and verifier audits.

Critical strengths
  1. The exactness guarantee is useful and straightforward to inspect.
  2. The savings extend substantially beyond the existing zero-call shortcut.
Critical weaknesses
  1. The algorithmic novelty is modest. The central stopping condition is an application of bounded partial aggregation, and the paper already connects it to classical threshold algorithms in Section 8. The main contribution is a useful formulation and evaluation for PRM-weighted answer selection, rather than a new general certification principle.
  2. The headline end-to-end token reduction relies on an approximation in the primary study. Equation 7 in Appendix C estimates each trace's PRM tokens from its relative step count and benchmark-level token metadata.
Questions for authors
  1. Can the main study report the additional cost reduction over an exact-unanimity-then-verify-all baseline under the same aggregate convention?
  2. How closely does the step-weighted estimator in Equation 7 match actual PRM input lengths? C
Reviewer_wePmOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a training free stopping criterion for PRM scoring. The authors introduce an approach to prevent redundant verification and match full verification of a set by maintain the upper and lower bounds of the PRM-weighted vote and stopping early if the lower bound exceeds each competitor's upper bound.

Critical strengths
  • Are able to get some gains in sampling by computing a simple upper and lower bound for voting, preserving the exact selection from voting over the full sample set.
Critical weaknesses
  • The PRM is used strictly in an outcome setting (relying on answer clusters), leaving a lot of efficiency gains out for partial responses.
  • Very limited baselines used in the evaluation setting and only evaluated on a fixed candidate set and not for search.
Questions for authors

Look at weaknesses above.

Reviewer_moUsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper is situated in the context of evaluating the confidence of alternative responses generated by an LLM. During the reasoning process, multiple chains-of-thought (CoT, or traces) are generated, requiring substantial computation to evaluate each trace. The authors propose an algorithm that prunes traces certified not to be the winning answer.

Critical strengths
  • The core idea is interesting and timely.
  • The empirical evaluation demonstrates a significant reduction in the number of tokens consumed during the reasoning process.
Critical weaknesses
  • The paper is difficult to follow and heavily geared toward specialized LLM researchers. While the concept is promising, the problem formulation lacks clarity: I had to consult several state-of-the-art papers simply to understand the precise problem being tackled.
  • Consequently, the incomplete formalization makes it difficult to verify the mathematical validity of the proposed certification claims.
  • While the algorithm achieves the same accuracy as the baseline on the tested datasets with fewer tokens, and the appendices contain supplementary details to support reproducibility, the source code is not provided.
  • A step-by-step running example (at least in the appendices) would greatly help in understanding both the problem setting and the certification mechanism.
  • The proposed pruning approach is not thoroughly benchmarked against established search and pruning techniques, such as Monte Carlo Tree Search (MCTS). The authors justify this omission by arguing that different methods optimize different resources; however, evaluating their method on top of or alongside existing optimization techniques would be necessary to demonstrate the actual net gain.
Questions for authors

Minor comment (Page 3): In the statement "At this exponent, a score of 0.99 contributes approximately 0.92, whereas 0.18 = 10^{−8};", the role and meaning of 10^(-8) are unclear, as this value is not referenced or leveraged later. The notation also seems confusing.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.