Label-Efficient Risk Certification for Medical Question Answering and Triage via Predictive Calibration Ordering

Approving medical AI policies for repeated use can require a high-confidence population-error certificate, even when expectation-based methods offer higher yield. With scarce calibration labels, however, these strict certificates often force low release rates. We introduce Predictive Calibration Ordering (PCO), which forecasts dependent certification outcomes from development data and uses exact dynamic programming to optimize a first-failure testing sequence, preserving the finite-sample selected-risk guarantee of Learn then Test. We evaluate PCO across medical question answering (HealthAdvice and 1,000 MedQA questions) and current-action triage (CARE-Bench). Across 80 target-averaged settings, Exact PCO achieves higher useful yield than Holm-certified adaptations of SCoRE, LEC and SCRC. At 20 labels and 90% certification confidence, MedQA useful yield reaches 51.52% and 43.12% for two models, versus 18.68% and 12.20% for SCoRE+Holm. Matched controls isolate joint planning, with small-budget gains across all three benchmarks of up to 2.4 percentage points over marginal ordering and up to 7.8 over Learn then Test. By increasing certified yield from scarce labels, PCO could help clinical AI systems release more answers to patient questions and triage recommendations without individual review.