acceptodds
Under review as a conference paper at ICLR 2027

Certificate Stopping: Exact Verifiers and a Per-Request Cost Cap for Language Models

Abstract

A service that bills per request must guarantee two things on every request: a correct answer and a bounded cost. A verifier, such as a proof checker, an instruction checker, a schema validator or a code test, can check an answer before delivery. Routers and cascades reduce cost by choosing which model answers, but they estimate quality, so a wrong estimate can deliver an incorrect answer, and they bound cost only on average, so no single request's cost is bounded. We propose certificate stopping to close both gaps. A small model, the certifier, answers first and an exact verifier checks its answer; if accepted, the answer is delivered, otherwise the large model runs within the remaining budget, the cap minus what the certifier spent, which bounds every request's cost. The remaining question is what such a policy costs. The rule is simple, but its cost is not obvious: rejected requests are the hard ones, a rejection leaves the large model a smaller budget, and several certifiers draw on one budget. Our first theorem resolves the three effects exactly, as a cost identity whose terms are measured on an earlier run and which gives the cost ratio of a new large model before it runs when its cost is proportional to the old one's. Our second theorem gives the acceptance rate above which adding a certifier lowers the expected cost under the shared budget, with no assumption on costs or on dependence between certifiers; choosing the set exactly is NP-hard, so the order is fitted, not derived. We also bound the accuracy lost when the verifier may accept wrong answers. The policy requires no training. On eight benchmark subsets whose pass criteria were fixed before their test requests were opened, the policy uses 0.274 to 0.654 of Qwen3-32B's parameter-weighted tokens and is 0.75 to 8.32 points more accurate, with a positive lower bound on seven, and three of them repeat under three seeds; the verifier there is the official scoring metric, so accepted answers pass by construction. Cost ratios predicted before large models from four further families ran meet the registered band on 23 of 24 cells, and a rule fixed in advance limits the claim to the small model's own family. No evaluated learned router or cascade is more accurate on held-out requests, and an uncapped control exceeds the cap on 212 of 10,040 request evaluations, the policy on none. Where no verifier exists, the policy has no certificate to stop on, and on one official routing pool a trained cascade router is more accurate and cheaper than the policy.

Primary area:
foundation or frontier models, including LLMs
Keywords:
language model routing, model cascades, exact verifiers, per-request cost guarantees, training-free model composition, inference efficiency, cost prediction

Reviews

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

The paper addresses the problems of verifying correctness and bounding the per-query cost when using a service that routes/cascades to multiple language models.

They propose using exact verifiers to check correctness and stopping whenever an acceptable answer is found. If the budget is not exhausted, the policy may continue and query another model. They further analyze the cost of such a strategy and identify when an escalation decision is beneficial.

Critical strengths

Cost-efficient cascade policy design is a timely and important research question.

Critical weaknesses
  • Verification-based acceptance and stopping upon success already appear in the cascading literature. For example, Section 5.2 in A Unified Approach to Routing and Cascading for LLMs (the header "Accurate quality estimation") uses SWE-Bench unit tests as accurate quality estimates to showcase a scenario where accurate quality estimates are provided. Section 3 in Computational Arbitrage in AI Model Markets similarly uses SWE-Bench; it stops upon a successful solution being found. Appendix B.1, setup 1 in Efficient Contextual LLM Cascades through Budget-Constrained Policy Learning explicitly analyzes a cascade with a correct oracle. The paper's claim that "none of the existing methods stops on an exact verifier's acceptance" hence needs revision.

  • Generally, the verifiable case can be viewed as a special case of the approaches that try to learn a correctness estimator, such as FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance and When Does Confidence-Based Cascade Deferral Suffice, or approaches that learn it from noisy verification such as AutoMix: Automatically Mixing Language Models. I believe that the correct framing of the paper should be that it considers a restricted setup (verifiable domain), not that it addresses the central challenges in those works.

  • Presentation needs improvements. Some parts are written unclearly. Particularly Part 9 of Definition 1 and the last sentences of the paragraph titled "The rule" in the same section. The abstract also needs improvement.

  • Some theoretical results seem to follow directly from definitions or assumptions. For example, Theorem 1 follows by writing the total cost as the sum of the certifier model's cost and the cost incurred upon rejection. Proposition 6 says that when an acceptable answer is found, the system has to stop rather than escalate; this is an immediate consequence of the assumption that further calls have non-negative cost. I hence have some concerns about the significance of the theoretical contributions.

Questions for authors

Could you please address my first two points in the "Weaknesses" section? In particular, to what extent can your setup be viewed as a special case of the existing cascading framework, in which the quality estimator is replaced by an exact verifier? Do you think current methods could be directly applied under this assumption? If not, could you please identify the challenges introduced by your setting and how your approach addresses them beyond the existing literature?

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

The paper’s main contribution is Certificate Stopping, a language model cascading strategy, a small model is run first, and its answer is returned if it passes an exact verifier; otherwise, a large model generates an answer within the remaining budget. As secondary contributions, the paper analyzes the cost of rejected requests and the effects of budget-induced truncation. It provides a cost decomposition, a prediction under a proportional-cost assumption, and conditions under which adding an additional stage reduces cost. The authors evaluate the strategy on instruction-following, structured-output, and formal theorem-proving tasks. On some subsets, its token cost is 0.274–0.654 times that of the large-model baseline, while accuracy improves by 0.75–8.32 percentage points. The paper also reports settings in which the method does not offer an advantage.

Critical strengths

The paper addresses a practically relevant problem with a training-free strategy that explicitly accounts for the per-request budget and stops further model calls when an answer passes an exact verifier. Several instruction-following and structured-output subsets show both cost reductions and accuracy improvements. The cost analysis is useful. Requests rejected by the small model may also be those on which the large model incurs higher generation costs. In addition, the budget consumed by the small model limits subsequent generation. Theorem 1 provides a useful analysis of these effects, showing that the same acceptance rate does not imply the same cost savings.

Critical weaknesses

My main concern is that the contribution beyond prior work remains limited. Cascade-routing already studies decisions about whether to stop or invoke another model based on model outputs, ThriftLLM studies model ensemble selection under budget constraints. The proposed method combines stopping upon acceptance by an exact verifier with fallback generation within the remaining budget. The distinction appears limited, and the strategy is relatively straightforward. I am not yet convinced that the paper provide sufficiently substantial new insights. The paper’s narrative is difficult to follow, and the exposition does not clearly connect the main contributions. In particular, the advantages of the additional budget mechanism over simple alternatives are not sufficiently established under matched constraints. The same-verifier control in Table 21 already recovers nearly all of the reported accuracy and average-cost advantages; the clearest benefit of the additional mechanism is the elimination of budget violations. However, the repeated-sampling control and some three-stage experiments do not consistently enforce the same per-request budget constraints ( Tables 14–15 and 19). A clearer account of these differences, together with comparisons using the same verifier and budget, is good to help assess the mechanism’s incremental contribution.

Questions for authors

Would the accuracy and cost comparison in Table 14 still hold if the same per-request budget checks were applied to the repeated-sampling control? Are corresponding budget-check results available for MiniF2F? Why did the three-stage strategy in Table 19 not enforce the check in Algorithm 1 that a stage is run only when its cost cap fits within the remaining budget? If this check were enforced, would the conclusions about whether adding the intermediate stage is beneficial still hold?

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

This paper proposes Certificate Stopping, a verifier-based model cascade policy for reducing language-model inference cost under a strict per-request budget. The proposed policy first queries a smaller model and returns its answer if an exact verifier accepts it. Otherwise, it retries with the smaller model and then queries a larger model using the remaining budget, after deducting the cost of earlier attempts. The total query cost is therefore capped at the total permitted cost of both smaller-model (certifier) and larger-model. The paper derives a cost decomposition theoretically for predicting costs with another large model under proportional-cost assumptions, and a criterion for determining whether an additional small-model attempt reduces expected cost. Finally, the paper builds upon a policy for request serving.

The proposed policy was evaluated on a set of different tasks that includes instruction-following, JSON-schema conformance, and formal-proof tasks. On eight held-out benchmark subsets using Qwen3 4B as the smaller model and Qwen3 32B as the larger model, the paper reports cost ratios of 0.274-0.654 in tokens and accuracy improvements of 0.75-8.32 percentage points, with positive lower confidence bounds on seven subsets. The paper also evaluates cost predictions across model families and examines limitations arising from frequent verifier rejections, imperfect verification, and truncation of the larger model’s output.

Critical strengths

The paper has the following strengths:

  1. The paper addresses a timely cost-control and reduction problem and provides encouraging empirical evidence. It studies how to reduce LLM inference costs while enforcing a spending limit on each request. On eight held-out benchmark subsets, the paper reports using 27.4%–65.4% of the baseline’s parameter-weighted token cost, with positive accuracy gains. These results support the potential practical value of the proposed approach on tasks with suitable verifiers.

  2. The core approach has a clear and well-established technical basis under its stated assumptions. An exact verifier allows the system to return a small-model answer that satisfies the checked property, while deducting earlier spending from the fallback’s allowance enforces the model-cost cap. The cost analysis accounts for the expense of rejected requests and shortening of the fallback, providing a useful explanation of the tradeoffs introduced by cascading model routing and shared budget.

Critical weaknesses

The paper has the following critical weaknesses:

  1. The terminology and language used significantly obscure the main ideas, methodology, and results, requiring significant cleanup and improvements. The paper uses non-standard terminology and overloaded sentences. For example, §3 states: "The confirmation role, opened at most once per registered policy and comparator and read only after a sealed authorization has fixed the configuration (Appendix A.4), yields every confirmed number; if its gate fails, the cell is a frozen negative, thereafter served byte for byte as the large model alone." Similarly, §4 describes an experiment by stating that "its sealed authorizations allowed the mechanism role but no confirmation role, so a passing gate there adds no certified claim." These passages require the reader to repeatedly translate terms such as "roles," "gates," "sealed authorizations," and "frozen negatives" to understand the experimental procedure and the status of the results. Unfortunately, the mathematical presentation compounds this difficulty. Although several symbols are formally defined, the paper does not explain their meaning or relationship to the method at the point of use. Following the formulas requires substantial effort to trace definitions and infer how the different variables relate to one another. These presentation issues limit the reader's ability to assess the contributions, methodology, and supporting evaluations, even after careful reading. I strongly recommend that the authors substantially rewrite the paper to improve flow and clarity.

  2. The significance of the contribution beyond prior work is insufficiently established. The related-work section acknowledges existing approaches to cascading, verification, and budget control, and identifies exact-verifier stopping under a shared per-request budget as the proposed distinction. However, the discussion mainly contrasts the guarantees provided by different methods without sufficiently establishing the depth of the methodological advance. The cost decomposition and admission criterion offer useful analysis, but I remain unconvinced they provide substantial new insights beyond adapting an existing cascade to enforce a spending cap. Although the empirical savings are encouraging, the paper needs a stronger justification or clearer upfront explanation of why this combination constitutes a substantial contribution.

Questions for authors
  1. Clarification of novelty and practical contribution. Beyond combining exact-verifier stopping with a shared per-request budget, what substantive methodological advance distinguishes this work from the approaches discussed in §5? In particular, how was Theorem 4 used to select the evaluated policies, and which reported results demonstrate its value beyond explaining the costs of policies already selected?

  2. Clarification of the cost-prediction claim. Proposition 2 assumes proportional scaling of large-model costs to new large models. How well do these assumptions and formulation hold in the evaluated within-family transfers? Does this require using the same tokenizer? Please identify the existing measurements supporting these assumptions and the corresponding prediction errors, since these determine how broadly the claimed contribution applies.

  3. Clarification of generation settings and robustness. What temperatures and, where applicable, reasoning modes or effort settings were used for both the smaller and larger models, including the standalone baselines? How were these settings selected, and do existing results establish sensitivity to these choices? These settings can affect the smaller model's acceptance rate, both models' token consumption, and the larger model's performance as both the fallback and the baseline. Consequently, the spending cap can still hold while the reported cost–accuracy advantage changes.

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

The paper introduces certificate stopping where authors run one or multiple cheap-to-run "certifier" models to get a first answer which a public verifier can accept. If the public verifier does not accept the first answer the large model is run under the per-request budget.

The paper contributes an identity to decompose cost to certifier share, acceptance rate and selection factor and its transfer to a new large model that has a proportional cost. It also gives the admission threshold for adding another certifier and the np-hardness problem of choosing the certifier set. There is also a rigorous evaluation and a well documented case studies of failures.

Critical strengths

The greatest strength of this paper is the evaluation depth and consistency, it would be great if all papers had the same honesty when presenting their results.

The cost identity can help a system to diagnose why a cascade is expensive/cheap. the identity lets users separate the succes of certifier to whether is fails costly request or due to truncation. The worked examples (ProofNet’s 0.89; the Multi‑IF turn series where only q moves) make this concrete. The observation that alpha + (1 - q) systematically underestimates cost when k > 1 is a correct and practically relevant.

The paper states the results certify cost under a verifier and it states clearly the boundary where this method stops helping.

Critical weaknesses

the 8 headline cells use class b verifiers. The policy is therefore selecting answers using the evaluation metric at serving time. The appendix does list this limitation.

The abstract’s claim that routers and cascades leave “no single request’s cost … bounded” is inaccurate as a router that picks one model has per request cost <= max_a_C_a which equals C_P when P is the most expensive option. so, any cascade could enforce the same cap by the same admission check plus truncation.

The paper is hard to read as the main text is full of protocol vocabularies, and baselines are buried deep into the appendix, it would be better to put the exact protocol details into the appendix as the main ideas can fit in 1-4 pages which gives room for expts and baselines.

Questions for authors

Can you report results where the verifier is exact but not the scoring metric, outside of Lean, so the gain is not by construction?

Reviewer_QBh2OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

From my understanding, the paper studies the problem to reducing inference time cost of language model in routing and cascades?. They propose a policy where a smaller model generates an answer first similar to cascade, the verifier checks the answer and if it accepts the system stops. else, a stronger model is used. They derive several results about the expected cost of this policy and evaluate it on a lot of different LLM benchmarks. but It is not clear what they're implementing and evaluating and there are major inconsistencies between the problem formulation and experimentation.

Critical strengths

None

Critical weaknesses

theoretical analysis serve no purpose in the experiments. they're not coherent with what is implemented in experiments.

Writing is not understandable or suited for a academic publications. Claims in the paper throughout problem formulation and theory are extremely inconsistent and do not follow to experiments. the experiments are on a lot of different unrelated benchmarks and they don't have a common theme.

It is not clear what the scope of the gaurantees are.

Questions for authors

I will provide some limited examples of the writing that i dont understand at all below, though the whole paper is not understandable or consistent.

  1. " The policy is simple; its cost is not obvious, because rejection selects the hard requests, shortens the large model and couples the certifiers through one budget." What does it mean that rejection selects the hard requests or shortens the large model? This sentence is not understandable without further explanation.

2."An acceptance is a certificate of the checked property. The verifier is exact relative to the official metric if it never accepts an answer that the metric scores as incorrect, so an accepted answer is correct under that metric, while a rejection establishes nothing." I found the terminology confusing.the paper should clearly explain why exactness is defined only in terms of accepted answers and what information a rejection provides, what does it mean rejection established nothing.

3."The policy requires no training; only the choice of certifiers uses requests set aside for fitting." What does fitting refer to here? If data is used to select the certifiers and their order, the distinction between training and fitting needs to be explained.

The paper needs substantial rewrite.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.