When a screening certificate costs more than the solve it saves

The exact solver behind Which missing outcomes should you pay to recover? decides which censored outcomes to recover before a constrained portfolio is allocated. It is fast. The obvious way to make it faster is to stop solving cases that cannot matter: build a screening certificate that proves, cheaply, that a candidate evidence set cannot change the downstream decision, and skip the exact solve entirely. This paper is the report of that attempt. It did not work, and the reason it did not work is the useful part.

The three certificates

We wanted a test that is safe, meaning it never skips an evidence set that would have changed the decision, and cheap, meaning it costs materially less than the exact solve it avoids. We built three candidates, each verified for safety before it was timed:

The three certificates attack the problem from different directions. One bounds the achievable decision value, one exploits structure in how the decision responds to evidence, and one asks a geometric question about whether the chosen portfolio can move at all. The constructions are not published here. What matters for the result below is that all three are provably safe: when a certificate says the decision cannot change, it cannot.

All three are decision-aware: they reason about whether the decision moves, not whether the posterior moves. That is the right object, and each was safe because of it.

What we measured, and why it is a negative result

Safety held. The joint portfolio-support bound was strictly tighter than direct scoring in 170,212 of 170,212 comparisons, and no certificate produced a single false skip on any frozen population. On the only axis that decides whether a screen is a product, wall-clock, every certificate lost. The tightest screen ran at 0.97× the direct baseline: slower, despite rejecting most evidence sets correctly. The other two were closer but still did not clear the exact kernel they were meant to replace.

The lesson is exact and, we think, general enough to state plainly:

A decision-stability certificate is a contribution only when its arithmetic is cheaper than the exact solve it avoids. Being provably tighter and provably safe is necessary and not sufficient.

This sounds obvious in retrospect. It was not obvious going in, because the intuition from information theory and from POMDP belief compression is that a good structural bound should dominate. It does dominate, on tightness. The trap is that our exact solver already exploits the same structure the certificate exploits, so the certificate and the solve share their dominant cost. There is no cheap outer loop when the inner loop is already the cheap thing.

Where a useful certificate could still live

We are keeping this result rather than burying it because it sharpens the open question rather than closing it. A cheaper screen is still possible if it avoids re-deriving what the solver already computes. Two directions survive the negative result:

• Amortisation. A certificate paid for once and reused across many evidence sets could beat a solver that pays per case, even if a single certificate evaluation does not.
• A cheaper screen. If stability can be certified without doing the work the solver already does, the certificate would stop sharing the solver’s dominant cost. That is a novelty claim we have not proved, and it is precisely the boundary the flagship paper leaves open.

Until one of those clears an exact solver on wall-clock and on a frozen falsifier, decision-stability screening stays where it belongs on this frontier: an instructive dead end that tells the next project what “cheaper” has to mean.