FS-Cert-U: Risk Certification Before Utility Optimization for Non-Monotonic Two-Stage Model Routing

Two-stage model routing trades answer coverage against inference cost, but the system-level selection-conditioned error rate (SCER) need not vary monotoni- cally with either routing threshold. Moreover, searching and certifying policies on the same evidence can invalidate fixed-policy guarantees. We introduce FS- Cert-U, which separates policy construction, ordering, certification, and utility selection: design data freeze a finite policy family, screening data fix its order, and independent certification applies exact candidate-wise tests with fixed-sequence stopping. Utility is optimized only within the resulting certified set. We prove finite-sample family-wise safety of the certified policy set without requiring in- dependence across candidate tests, together with a utility-regret bound relative to the best certified policy. Across 33 QA routing configurations, FS-Cert-U shows a systematic certification-power advantage over matched Bonferroni correction: dataset-level utility gains persist across all six evaluated risk targets, while all 33 paired gains are positive at the primary operating point. The advantage also persists across four Guardian-cost weights. Controlled-population experiments directly probe false certification and confirm the predicted decrease in post-certification utility regret with increasing certification data