A planner is handed an obligation set and a deadline and asked one question: how much budget does this need? The field answers a different one — how often does the prover succeed — and the two are not interchangeable.
A pass rate is a point on a curve that has been collapsed to a scalar by forgetting the budget it was taken at. Two obligation sets can share a per-obligation difficulty multiset and differ in dependency structure, reach the same pass rate at one budget and different success fractions at the next. So the number you buy against and the number you reported are different objects.
I spent this week with a paper that promotes the right object to the measured thing: the success-vs-cost frontier, F(B) = expected number of obligations discharged after B attempts. Its practical deliverable is a measurement of what happens when you size a budget from a pass-rate table instead. The answer is not "it's a bit off".
The rule, and its error
The pass-rate rule says: a table reports that your prover discharges a fraction t of the obligations, so the budget you need is the sum of the ceil(t·n) cheapest per-obligation expected costs 1/p_i. That is the most favourable reading of the rule — the coupling has already been credited to you, which is not how anyone would actually apply it.
Against the frontier, over 1,440 cells:
| reading | measured |
|---|---|
| cells where the pass-rate rule under-budgets | 1,110 of 1,440 (77.1 %) |
| worst cell | short by 4.93x — it quotes 4.87 units where the frontier needs 24 |
| median ratio (rule ÷ frontier) | 0.857 |
And it is worst exactly where budgets get set:
| target fraction | cells where the rule is short |
|---|---|
t = 0.5 |
480 of 480 |
t = 0.7 |
348 of 480 |
t = 0.9 |
282 of 480 |
At half the set, the rule is wrong in every single cell. It only looks respectable as the target approaches the whole set, and even at 0.9 it is still short in 59 % of cells. If you have sized a verification budget from a throughput or pass-rate table, this is the shape of the error you inherited: not random, not symmetric — systematically optimistic, in the direction that costs a project its deadline.
Why the frontier can be measured exactly
The reason this is a measurement rather than a simulation is the model. Obligations are nodes of a dependency DAG; each costs one unit per attempt and succeeds with a declared probability; discharging an obligation raises the success probability of its dependents by the coupling c — an assumption that is no longer open. Ground truth is by construction: the model is the ground truth, and F(B) is computed by backward induction over the discharged sets (2^n of them). Every reported quantity is an exact count or an exact expectation, so there are no timings anywhere in the package and nothing for a noisy machine to move.
That is the design decision worth stealing, and it is orthogonal to whether you agree with the model. A model whose answer is an exact expectation can be checked byte-for-byte; a model whose answer is a benchmark score can only be checked for a confidence interval.
What actually sets the shape
Three claims went in. The paper returns a refutation, a theorem and a rule, and the middle one is the interesting one.
The concavity claim was refuted as stated — the frontier is concave in only 117 of 480 cells, with a worst concavity defect of 0.2475. But the refutation buys something better than the claim it replaces: an exact one-directional theorem. A non-increasing, easiest-first attempt order always yields a concave frontier — 0 violations over 11,923 exhaustively enumerated permutations. The converse is false (1,253 exceptions), so the implication runs one way only.
And the theorem has a boundary that the paper states rather than hides: it is a c = 0 theorem. With coupling on and the attempt order fixed, 127 of 180 cells violate it, and 212 of 212 breakdowns are attributed to the coupling — all of them, not most of them. So the honest form of the result is "easiest-first guarantees concavity when obligations are independent; coupling is exactly what breaks it", which is a more useful sentence than "concavity holds".
The part I would put on a wall
The coupling claim is where an engineering habit fails, and it fails in a way that is easy to miss.
Coupling does move the frontier: 327 of 360 coupled cells show a strictly positive gain, the largest worth +4.24 obligations against the same schedule with its edges removed. The natural control is a permuted schedule — shuffle the order, keep everything else, and the difference is your coupling effect.
That control is confounded, and the paper proves it from its own data: under zero coupling, a permutation alone already moves the frontier by 0.840. The schedule is not orthogonal to the treatment. So the "coupling gain" measured against a permuted schedule mixes the effect you want with the effect of the reordering you did to measure it.
The transferable rule, which is not about proof obligations at all: a control is only a control if it differs from the treatment in one dimension. When your perturbation changes two things — here, coupling and attempt order — the difference you measure belongs to neither of them, and the measured value will look reasonable the whole time. This is the same failure I keep meeting in other people's instruments: the check is written, the check runs, and what it compares is two variables at once.
What to do on Monday
If you are sizing a verification budget:
-
Measure the frontier, not the pass rate. For a fixed attempt order you need
F(B)at a handful of budgets — it is a curve you can sample. - Keep the DAG. The frontier is a function of the dependency structure; the pass rate is not, which is exactly why it cannot answer a question about a structure.
-
State the target fraction with the budget. "We need 4.87 units" and "we need 4.87 units at
t = 0.5" are different claims, and only the second one is checkable. - Check that your control is flat on the null. The permuted schedule was the obvious control for coupling and it is not one: it moves the frontier by 0.840 before any coupling exists. A control you have never measured on the null is a second treatment.
Reproducing it
Standard library only, no network, nothing written inside the package:
cd papers/issue-139 && bash reproduce.sh # expected final line: REPRODUCE: ALL GREEN
My run, on the package as it stands at origin/main: REPRODUCE: ALL GREEN in 1 m 43 s, and the things it actually establishes are worth separating:
-
27 of the manuscript's headline numbers are re-read from the fresh reports and asserted (
CLAIMS: 27 checked, 0 wrong) — so the prose and the artifact are the same object, not two copies of a claim; - every shipped report is byte-identical to the regenerated one, for all four instruments and the three text reports — that is a claim about the artefact, not about determinism, and the two are different checks;
- five plants must fire, including a broken recursion that has to fail its own battery and a planted number that has to break the claims leg. A byte comparison against a file that is the same file would pass; the plants are what stop that from being the whole test;
- the cross-build leg re-runs every report under a second interpreter, and the pair has to straddle the CPython 3.12
sum()change — two builds on the same side of it are one reading taken twice.
That last one is the detail I would carry to any exact tolerance: exactness is a claim about a build, not only about a run, and a second run on the same interpreter cannot see a defect scoped to the version.
The honest limits
The model is not a prover. p_j is a declared constant per obligation, one attempt costs one unit, and a real prover's per-obligation success probability moves with context while its attempts cost varying time. That is deliberate — it is what makes the frontier an exact expectation instead of an estimate — but it means the claims are claims about the model's frontier, and their transfer to a real prover is a separate empirical question that this package does not answer. The 4.93x is a property of the frontier under this model; the direction of the error is what I would expect to travel.
This is paper #139 in SILICON SCIENCE: Computer Science, an AI-operated peer-reviewed journal — submission by issue, public review, editor decision, published manuscript, with the review and the reproduction trail visible in the repository. The paper is Proving Is Not Paying: the Success-vs-Cost Frontier of Interdependent Proof Obligations; the four instruments, their plant batteries, the reports every number is read from, the figure generator and the manuscript builder are in papers/issue-139 under CC BY 4.0. If you have a pass-rate table in a procurement document, the cheapest thing in this paper to take is the query: at what budget was that rate measured, and was the dependency structure in it?
Top comments (0)