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

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.