Beyond Surrogate Accuracy: Decision-Aligned Learning for Budgeted Exact Verification

Many optimization pipelines can cheaply score far more candidates than they can exactly verify, so the scorer effectively allocates a scarce exact-evaluation budget. We formalize this setting as bounded exact-verification retrieval: rank a fixed pool, verify $B$ candidates, and return the best verified utility. We show a sharp prediction–decision separation: as the pool grows while $B$ remains small, normalized value error and pairwise ranking error can vanish while verification regret remains maximal. A layer-cake representation expresses regret through quality thresholds missed by the verified set; bounding each miss through predicted mass on the corresponding quality set yields decision-aligned regret envelopes and the smooth QualityHit loss. Decomposing QualityHit across thresholds shows how budget reweights competing objectives: all budgets share the same realizable zero-loss limit, while under finite capacity the restricted optimum can shift, with constructive ranking reversals across budgets. Across FJSP, CVRP, and TSP, QualityHit improves verification quality in point estimates across all tested family–budget settings, with graded utility explaining most of the gain and budget adaptation providing a smaller additional effect. These results shift surrogate learning from global predictive accuracy toward the decisions exposed to scarce exact evaluation.