Algorithm selection scores can mislead deployment performance estimates
Partition Scores Are Not System Scores: Deployment-Fidelity Gaps in Decomposed Algorithm Selection
Artificial IntelligenceMachine Learning
Summary
When choosing the best algorithm to solve a problem, people often use scores that assume perfect choices within groups of algorithms. The paper finds that these group-level scores overestimate how well a deployed system will perform because real systems must learn to select algorithms within each group. The authors define a measure to capture this gap and show it exists on real benchmark datasets. They recommend reporting both group-level and end-to-end performance scores so users understand the difference.
What this means in practice
- •For machine learning engineers: Assess algorithm selectors with both partition-level and full-system scores to better predict real-world performance.
- •For software developers for optimization tools: Identify when multi-level algorithm selection pipelines may overestimate performance and improve deployment reliability.
Authors
Jiachen Zhang, Yu Tang, Li Zhu
Abstract
Oracle-style quantities, including virtual best solvers, selected-portfolio VBS, virtual-best encodings, and best-in-family summaries, are widely reported as upper bounds on what a deployable selector could achieve. In decomposed algorithm selection, an analogous partition-level score grants an oracle choice of the best algorithm within the selected family; once the family selector is fixed, the deployable system must replace that within-family oracle with a learned within-family selector. We define the deployment-fidelity gap G(R) as the difference between partition-level and deployable end-to-end utility and derive two accounting consequences: a per-instance margin-regret stability condition that tells us when a partition-time family choice is deployment-optimal, and a sharp partition-only identification interval that, when it strictly crosses zero, prevents the partition-level report from certifying the deployable winner. Across five public algorithm-selection benchmarks spanning tabular AutoML and combinatorial CSP/SAT, every decomposed pipeline has positive G(R), ranging from 0.012 on TabZilla to 0.13 on PROTEUS-2014. Four of ten decomposed-versus-flat decisions have sign-changing point estimates; on PROTEUS-2014, a 33-point partition advantage shrinks to a 20-point end-to-end advantage. A training-side validation gap-correction diagnostic recovers the point-estimate deployable sign on all four sign-changing cells; it is a reporting aid, not a substitute for direct end-to-end evaluation. Partition and end-to-end scores should be reported side by side.