Selective Certification for Safe Upgrade Planning

An upgrade planner should spend evaluation on plausible routes, distinguish a rejected candidate from a certified obstruction, and justify any reuse of evidence. We instantiate explore–verify in a known finite graph whose edits share unknown gain signs. The algorithm screens only labels on optimistic candidate routes, then certifies either a useful positive route or a negative blocking set. It stops with finite expected cost on every sign assignment, including infeasible ones, and attains the minimum positive-route information cost on each fixed feasible instance. Its screening cost depends on labels reached by correct optimistic search. A checkpoint contract extends the same procedure to irreversible diagnostic access. A separate packet rule permits adaptive route selection after partially validated sharing, with an explicit combined safety budget. Experiments include 160 random mixed-sign graphs, irrelevant-route and ordering controls, checkpointed deployment, and solver-certified optima on larger graphs. Selective screening removes large all-label overhead, but simpler testing often wins at moderate confidence; an optional rule retains that baseline. A code study that charges all work and matches candidate order reduces executions by 22.1% while taking longer on these cheap programs. These guarantees apply to checked upgrades, not general autonomous self-improvement.