PaperlayerView exact revision on arXiv

Source-linked AI summary

Partition Scores Are Not System Scores: Deployment-Fidelity Gaps in Decomposed Algorithm Selection

Jiachen Zhang, Yu Tang, Li Zhu

arXiv:2609.13785v1cs.AIcs.LG

TL;DR

In decomposed algorithm selection, a partition-level score grants an oracle choice within the selected family, although deployment must use a learned within-family selector. The paper formalizes this gap and its implications for comparing systems; across five public benchmarks, every decomposed pipeline has a positive gap, and some partition-level comparisons change sign end to end.

  • Problem

    Partition-level evaluation can grant the best algorithm in the selected family even though deployment must use a learned within-family selector.

    Source: §1 · p. 1

  • Method

    The paper defines the deployment-fidelity gap and derives a margin–regret stability condition and a partition-only identification interval for deployable comparisons.

    Source: §1 · p. 2

  • Results

    Across five public benchmarks, every decomposed pipeline has a positive gap, from 1.2 points on TabZilla to 13 points on PROTEUS-2014.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Partition and end-to-end scores should be reported together because partition-only reports can fail to certify the deployable winner when the identification interval crosses zero.

    Source: §4.3 · p. 6

    The training-side validation gap-correction diagnostic assumes validation represents the test distribution and was not evaluated under explicit covariate shift.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Decomposed algorithm selection evaluates a family choice before selecting an algorithm within that family, but partition-level evaluation can substitute an oracle for the deployable inner selector. The paper formalizes this deployment-fidelity gap and shows that it can change comparisons with flat selection.

1 Introduction

  • Partition-level evaluation grants the best algorithm within the selected family, whereas deployment must use a learned within-family selector.The partition score is therefore an oracle-assisted upper bound, not an end-to-end system score.Source: §1 · p. 1
  • The deployment-fidelity gap G(R) is the difference between partition-level utility and deployable end-to-end utility.It measures the utility lost when the within-family oracle is replaced by the available selector.Source: §1 · p. 2
  • Across five public benchmarks, every decomposed pipeline has a positive deployment-fidelity gap, from 1.2 points on TabZilla to 13 points on PROTEUS-2014.The safety condition fails in 4/10 decomposed-versus-flat deployment decisions.Source: §1 · p. 2
  • The contribution differs from prior oracle and benchmarking critiques by studying a within-family oracle introduced after a family selector has acted.The paper's novelty is that this substitution can change comparisons through differences in deployment-fidelity gaps.Source: §1 · p. 2
  • The paper derives a margin–regret stability condition and a partition-only identification theorem for when partition reports cannot certify the deployable winner.Theorems 1 and 2 respectively address deployment-optimal family choices and identification intervals that cross zero.Source: §1 · p. 2

2 Related Work

Prior algorithm-selection work reports several oracle-style upper bounds and studies benchmarking pitfalls, while decomposition has mainly been examined as a training strategy. This paper focuses on the evaluation of a decomposed system when its inner decision is learned at deployment.

2 Related Work

  • Oracle-style reporting includes full-portfolio VBS, selected-portfolio and subportfolio virtual-best scores, virtual-best encodings, and best-in-family comparisons.Examples span algorithm selection, hierarchical solver portfolios, encoding selection, and tabular benchmarking [Xu et al., 2008; Bach et al., 2022; Hurley et al., 2014; Stojadinović and Marić, 2014; McElfresh et al., 2023].Source: §2 · pp. 2–3
  • Tornede et al. [2023] study an oracle over complete selectors, whereas this paper studies an oracle over algorithms inside an already-chosen family.The latter produces the within-family deployment-fidelity gap.Source: §2 · p. 3
  • Leave-instance-out splits and scale-sensitive performance targets address different benchmarking choices from the system evaluated here.Petelin and Cenikj [2025] address which instances are held out and the numeric target; the deployment-fidelity gap concerns replacing a deployable stage with an oracle.Source: §2 · p. 3
  • Pairwise, multiclass, and family-level decompositions are established training strategies, while this paper examines their evaluation when the inner decision is learned at deployment.Prior analyses often place decomposition within the error-correcting-output-code framework.Source: §2 · p. 3

3 Setup

The setup represents algorithms as partitioned families and a decomposed selector as an outer family choice followed by an inner algorithm choice. It distinguishes an oracle-assisted partition score from the deployable end-to-end score and defines their gap.

3 Setup

  • The setup defines instances, a finite algorithm pool, a partition into disjoint families, and per-instance utility where higher values are better.Native regret or runtime metrics are mapped by a per-instance monotone transformation to normalized utility, preserving within-instance algorithm order.Source: §3 · p. 3
  • A decomposed selector first predicts a family and then uses a within-family selector to choose an algorithm from that family.The outer selector is h_R and the inner selector for family k is g_R,k.Source: §3 · p. 3
  • Partition-level evaluation grants an oracle choice within the predicted family, while end-to-end evaluation uses the available within-family selector.These scores distinguish the family-level choice's oracle-best member from the algorithm the system can actually deploy.Source: §3 · p. 3
  • G(R) is the partition score minus the end-to-end score, and pipeline advantages compare the corresponding scores on the same test distribution.The setup names these advantages A_part and A_e2e.Source: §3 · p. 3

4 From Partition Scores to Deployment Stability

The section formalizes how replacing a within-family oracle with deployable selection affects decomposed-pipeline comparisons. It gives accounting conditions, an instance-level stability test, and an interval criterion for when partition reports cannot certify a winner.

4.1 Accounting lemmas

  • G(R) measures within-family suboptimality, independent of global family correctness; a partition win transfers iff its advantage exceeds the differential gap ∆G.Source: §4.1 · p. 4

4.2 Margin–regret stability of family selection

  • At instance x, selected family s is deployment-optimal iff its oracle-utility margin over every competitor covers its differential within-family regret.Source: §4.2 · p. 5
  • The deployment-optimal outer target is v_k(x)=m_k(x)−r_k(x), not oracle family utility m_k(x).Source: §4.2 · p. 5

4.3 Why partition-level reports cannot certify deployable winners

  • Partition scores plus admissible gap envelopes bound deployable advantage in a sharp interval; if it is strictly one-sided, its sign is certified for every admissible selector.Source: §4.3 · pp. 5–6
  • A zero-crossing interval blocks certification from the report, not knowledge of the winner; evaluating a fixed within-family selector gives a definite end-to-end score.Source: §4.3 · pp. 5–6
  • The conditions become empirical diagnostics: a margin–regret violation rate and a partition-only interval with its cross-zero count, computed on a common valid-instance set.Source: §4.3 · p. 6

5 Empirical Results

Across five public benchmarks, decomposed pipelines have positive deployment-fidelity gaps, and partition-level comparisons sometimes change sign when evaluated end to end. The section tests when these conclusions transfer, diagnoses the gaps, and checks their robustness to selector choices.

5.1 Benchmarks and protocol

  • The study covers three tabular AutoML and two combinatorial-search benchmarks, using 5 seeds × 5-fold stratified CV and per-instance utilities in [0, 1].The default within-family selector is a per-algorithm gradient-boosted regressor; diagnostics aggregate predictions per test instance before instance-cluster bootstrap.Source: §5.1 · p. 6

5.2 RQ1: Do partition scores overstate deployable performance?

  • Gaps range from 0.012 on TabZilla to approximately 0.13 on PROTEUS-2014, with confidence intervals excluding zero for all decomposed cells.Flat baselines are controls; the singleton-flat invariant gives them zero gap.Source: §5.2 · p. 6, Figure 1 · p. 7

5.3 RQ2: When do partition-level conclusions transfer?

  • The 15 comparisons split into decomp-vs-flat deployment decisions and decomp-vs-decomp outer-selector comparisons, which behave differently.Source: §5.3 · p. 7

5.3.2 Decomp-vs-decomp: do outer selectors differ?

  • All pairwise-vs-multiclass comparisons have |Apart| < 5 × 10−3; on B5, all-feature access reduces G, while a shorter cutoff leaves it essentially unchanged.With all 198 features, pairwise G falls 0.134 → 0.100 and multiclass G falls 0.135 → 0.098; at 1800 s, the respective gaps are 0.134 and 0.136.Source: §5.3.2 · pp. 7–8

5.3.1 Decomp-vs-flat: is decomposition deployment-safe?

  • 4/10 decomp-vs-flat comparisons change sign: B2/B4 favor decomposition by partition score but flat selection end to end; B5 shrinks 33 pp to 20 pp.The B2 and B4 end-to-end margins are small point estimates: −0.0037, −0.0047, and −0.0031.Source: §5.3.1 · p. 7, Table 2 · p. 8

5.4 RQ3: Theorem 1/2 diagnostics

  • Violation rates are 0.23–0.56 for decomposed pipelines; all 15 identification intervals cross zero, including B5 (Apart = +0.33, WR ≈ 0.75).The interval is a conservative certificate, not a predictor; direct end-to-end reporting remains necessary.Source: §5.4 · p. 8

5.5 RQ4: Robustness to within-family selector class

  • Across selector classes, G varies 1.28×–2.23× by benchmark; realistic selectors retain 87–100% of default G on four benchmarks, with RF on B1 the lone sub-80% outlier.B2/B4 reruns keep G positive, though the strict sign of their small end-to-end margins is selector-sensitive; exhaustive HPO or task-specific meta-learners could still reduce the gap.Source: §5.5 · p. 8

6 Correction and Practical Guidance

A training-side validation diagnostic corrects partition advantages using estimated gap differences, while a deployment-aware family selector offers another way to shrink gaps. The guidance pairs these measures with direct end-to-end scores and documentation of the evaluation setup.

6 Correction and Practical Guidance

  • On B2–B5 decomp-vs-flat cells, gap correction reduces MAE by 25–88% and recovers the deployable point-estimate sign on all four sign-changing cells.It can over-subtract on B1 and assumes training-side validation represents the outer test distribution; it does not replace direct end-to-end evaluation.Source: §6 · p. 9
  • Training the outer selector on cross-fitted deployable utility shrinks G on every benchmark and improves Se2e on B1–B4.On B5 it shrinks G by 0.008 with a small Se2e trade-off (−0.005).Source: §6 · p. 9
  • Reports should pair partition and end-to-end scores with G(R), advantages, ρ, and the identification interval, while documenting selectors, family mapping, feature policy, and the common valid-instance set.Source: §6 · p. 9

7 Limitations and Conclusion

The paper concludes that partition-level scores are upper bounds on family quality, not system scores, and recommends reporting partition and end-to-end metrics together. Its conclusions are bounded by mapping and pipeline choices, with validation gap correction remaining diagnostic rather than a replacement for direct end-to-end evaluation.

7 Limitations and Conclusion

  • The partition-level report does not certify a deployable winner when its identification interval strictly crosses zero; report partition and end-to-end scores, the gap, and comparison diagnostics together.The checklist also calls for the within-family selector, family mapping, feature policy, runtime conventions, common valid-instance set, and identity residuals.Source: §7 · p. 9, E Reporting checklist and decision… · p. 14
  • The study is pipeline- and mapping-dependent, excludes continuous black-box optimisation, and does not test gap-correction robustness under explicit covariate or task-distribution shift.Stronger within-family models or domain-specific meta-learners may shrink the gap, but should still be evaluated end-to-end.Source: §7 · p. 9

Appendix

  • The appendix supplies proofs, mappings, full numerical analyses, sensitivity checks, evaluator pseudocode, and reproducibility details supporting the paper’s claims.Its materials include a reporting checklist, deployment-aware family selector, and within-family selector robustness results.Source: Appendix · p. 12

A Utility transformation

  • For B4 and B5, lower-is-better PAR10 or runtime is transformed per instance into utility, while B1–B3 use their native accuracy-like values directly.Degenerate rows with no within-instance range are excluded; B4 retains 556 of 601 instances and B5 retains 3565 of 4021 raw instances.Source: A Utility transformation · p. 12

B Algorithm-family mappings

  • The benchmark partitions group algorithms by model family for B1–B3, solver approach for B4, and CSP-versus-encoding family for B5.The B5 semantic mapping follows the original hierarchy: CSP-native solvers form one family, while the SAT-side encoding-by-solver grid forms three families.Source: B Algorithm-family mappings · pp. 12–13

C Synthetic toy example

  • The synthetic example gives R1 the larger partition advantage but higher within-family regret, reversing its end-to-end comparison with R2.The reported advantages are approximately +0.20 at partition level and −0.24 end-to-end; the identity residual is below 10^-15.Source: C Synthetic toy example · p. 13

D Reversal taxonomy

  • The taxonomy distinguishes preserved transfer, amplification, absorption, and reversal; empirically, standard-reversal point estimates occur on two benchmarks, with no observed opposite reversals.Amplification is mathematically possible when the partition winner has the smaller deployment-fidelity gap, but it is not needed for the headline findings.Source: D Reversal taxonomy · p. 13

E Reporting checklist and decision framework

  • A partition score answers questions about the family partition, but is insufficient for evaluating a deployable system or comparing decomposed methods.For a deployable comparison, the checklist includes the partition-only identification interval and whether it strictly crosses zero.Source: E Reporting checklist and decision… · p. 14

F Proofs

The proofs connect the deployment-fidelity gap to within-family regret and show how differences in that gap absorb partition-level advantages. They also establish stability and identification results for determining when partition-level choices or comparisons carry over to deployment.

Proofs

  • The expected deployment-fidelity gap equals within-family regret on the predicted family, which is nonnegative and is zero exactly when the within-family selector matches the family oracle almost surely.The pointwise difference between the best member of the selected family and the selector’s choice is nonnegative.Source: F Proofs · p. 14
  • The deployment-safety condition is that a decomposed method’s partition advantage exceed its gap difference from the comparator; against an ideal flat baseline, its partition advantage must exceed its own gap.This follows by substituting the end-to-end score identity into the pairwise advantage.Source: F Proofs · p. 14
  • A family choice is stable when its margin over alternatives accounts for the difference in their within-family regrets.The theorem expresses deployable value as family margin minus regret for each family.Source: F Proofs · p. 14
  • The partition-only identification interval is sharp because the unrestricted family-respecting selector class attains both the zero-gap and worst-case-gap endpoints.The figure caption also describes the regret-gap and advantage-gap identities visualized in Figure 2.Source: F Proofs · pp. 14–15, Figure 2 · p. 15

G Common-instance evaluation and identity residuals

The evaluation checks the accounting identities on common finite test instances, then measures gap correction and sensitivity to alternative family mappings and selector choices. Correction recovers the point-estimate deployable sign on the sign-changing cells, but remains a diagnostic rather than a substitute for direct end-to-end evaluation.

G Common-instance evaluation and identity residuals

  • Common-instance comparisons yield identity residuals at machine precision, at most 5 × 10^-16, across all five benchmarks.The protocol uses the intersection of instances with finite partition-oracle and end-to-end utility; Figure 2 visualizes both identities as sanity checks, not statistical fits.Source: G Common-instance evaluation and… · p. 15

H Decomposed pipeline pseudocode

  • The evaluator fits an outer family selector and a within-family selector per family, then records both the selected family’s oracle utility and the chosen algorithm’s utility on test instances.It repeats the procedure for five seeds and reports mean partition, end-to-end, and gap utilities with bootstrap confidence intervals.Source: H Decomposed pipeline pseudocode · pp. 15–16

I Gap-corrected reporting

  • On the four decomp-versus-flat sign-changing cells, gap correction recovers the point-estimate end-to-end sign and reduces MAE by 25–65%, but B1’s near-zero advantage is over-corrected.The authors therefore retain direct end-to-end reporting; they do not test robustness under explicit covariate or task-distribution shift.Source: I Gap-corrected reporting · p. 16, Figure 3 · p. 16

J Family-mapping sensitivity

  • B4’s positive gap and failure of the flat-deployment safety condition persist across every tested family taxonomy, although mapping changes the gap magnitude.The alternatives include a coarse collapse, a performance-cluster partition, and a random balanced partition; B5’s mapping sensitivity beyond its primary semantic partition is not used for paper claims.Source: J Family-mapping sensitivity · p. 17, Table 4 · p. 17, Figure 4 · p. 17

K Deployment-aware family selector

  • The deployment-aware family selector shrinks the gap on every benchmark and improves end-to-end utility on B1–B4, but trades off slightly on B5; sign-changing estimates remain on B2 and B4.Both selectors share the same within-family selector, so the comparison changes the family-selection objective.Source: K Deployment-aware family selector · p. 17, Table 5 · p. 18

L PROTEUS-2014 feature-policy and cutoff sensitivity

The PROTEUS-2014 primary deployment model gives the family selector only CSP-step features available before encoding selection, while an all-feature run tests a stronger-information setting. A shorter runtime cutoff preserves the directional conclusions, but the analysis does not extrapolate beyond the scenario cutoff because uncensored run logs are unavailable.

L PROTEUS-2014 feature-policy and cutoff sensitivity

  • Using all 198 features rather than the deployment-model CSP step’s 36 reduces the PROTEUS-2014 gap by roughly 25% on both selectors, through improved end-to-end utility rather than a smaller partition score.The all-feature setting exposes encoding-conditional features unavailable to the family selector at deployment time, so it is treated as a sensitivity check.Source: L PROTEUS-2014 feature-policy and… · p. 18, Table 6 · p. 18
  • Halving the PROTEUS-2014 cutoff from 3600 s to 1800 s leaves directional conclusions unchanged and makes the measured gaps essentially invariant.Fourteen all-timeout instances are dropped, and the flat baseline’s PAR10 moves slightly downward; the analysis does not extrapolate beyond the scenario cutoff because uncensored raw run logs are unavailable.Source: L PROTEUS-2014 feature-policy and… · pp. 18–19, Table 7 · p. 19

M Metric-transform sensitivity on B4–B5

The sensitivity check uses per-instance rank utility to test whether B4’s sign change and B5’s absorption depend on the headline min–max transform. It cautions that the released native diagnostic is not independent raw-second robustness evidence.

M Metric-transform sensitivity on B4–B5

  • The check tests whether the B4 sign-change and B5 absorption conclusions are artefacts of per-instance min–max utility by comparing them under per-instance rank utility.Source: M Metric-transform sensitivity on B4–B5 · p. 19, Table 8 · p. 19
  • The released native diagnostic is only a monotone −utility proxy, not independent raw-second robustness evidence, because its cache lacks a reusable raw-cost matrix aligned to recomputed masks.The authors avoid using pointwise non-negativity of a partition-oracle cost gap as robustness evidence.Source: M Metric-transform sensitivity on B4–B5 · p. 19
  • Rank utility confirms the B4 sign change and strong B5 absorption, although B5’s multiclass rank end-to-end margin is effectively zero.Positive advantages favour decomposition; rank utility maps the best algorithm on an instance to 1 and the worst to 0.Source: Table 8 · p. 19

N Within-family selector robustness sweep

The selector sweep finds positive deployment-fidelity gaps across tested within-family classes, while family-selector choice changes partition scores little. The accompanying analyses distinguish deployment-safe comparisons from sign-changing ones and document the statistical, computational, and literature-audit scope.

N Within-family selector robustness sweep

  • G spans [0.025, 0.031] on B4 and [0.128, 0.211] on B5 across the sweep, so even the best within-family selectors retain substantial gaps.The largest main-sweep PROTEUS-2014 value is G = 0.211 under single-best-on-train.Source: N Within-family selector robustness… · p. 19
  • Family-selector class changes Spart by at most 5 × 10−3, while within-family selector class shifts G by up to 2.23× on TALENT.Pairwise OVO is omitted from the B4–B5 sweep because its O(|F|2) solver-pair cost is prohibitive on larger ASlib pools.Source: N Within-family selector robustness… · pp. 19–20, Figure 5 · p. 20

O Full numerical tables for gap and advantage-transfer analyses

  • Four of ten decomp-vs-flat comparisons have sign-changing point estimates: B2 and B4 are unsafe, B1 is safe but nearly erased, and B5’s 33-point advantage shrinks to 20 points.Table 10’s interval-crossing fraction counts comparisons where partition-level information alone does not certify a deployable winner.Source: Figure 6 · p. 21, Table 10 · p. 21, Figure 7 · p. 22

P Statistical methodology

  • Paired tests use per-instance means across seeds; the authors apply two-sided Wilcoxon signed-rank tests and bootstrap confidence intervals to the per-instance gap vectors.Holm-Bonferroni adjusted p-values remain < 10−15 for all decomposed cells; bootstrap intervals use 10 000 replicates.Source: P Statistical methodology · p. 23

Q Compute resources and reproducibility

  • Reproduction runs on a single 8-core CPU workstation without a GPU, uses less than 4 GB of memory, and takes approximately 3–4 hours across five benchmarks.The most expensive configuration is pairwise-within-family on TALENT, which trains O(|F|2 · Kcv · seeds) binary random forests per fit.Source: Q Compute resources and reproducibility · p. 23

R Literature audit of oracle-style reporting

  • The literature audit supports a narrow prevalence claim: oracle-style quantities are primary comparison objects across four sub-areas, without alleging that cited works misuse them.The paper’s contribution is to construct and measure the gap to the deployable system that inherits the family choice.Source: R Literature audit of oracle-style… · pp. 25–26

S Inner-selector stress-test full results

Across six learned within-family regressors, the gap varies modestly within each benchmark, while the non-learned SingleBest reference is notably worse on B5. Targeted stronger-selector reruns preserve positive gaps but leave small B2/B4 end-to-end margins selector-sensitive.

S Inner-selector stress-test full results

  • The full spectrum uses seven within-family selector classes under a multiclass family selector and the same five-fold split protocol, with two seeds rather than the headline runs’ five.The analysis reuses the package’s WithinFamilySelector contract; SingleBest is treated separately from the learned selector class.Source: S Inner-selector stress-test full… · p. 27
  • Stronger-selector reruns keep G(R) > 0 in every B2/B4 cell, but end-to-end advantages stay near zero and the small-margin sign remains selector-sensitive.B2 G(R) is 0.046–0.049 and Ae2e is −0.004 to +0.001; B4 G(R) is 0.024–0.027 and Ae2e is −0.006 to −0.003.Source: S Inner-selector stress-test full… · p. 28
  • Across six learned within-family regressors, G ranges from 0.0082–0.0235 on B1, 0.0453–0.0542 on B2, 0.0681–0.0808 on B3, 0.0222–0.0267 on B4, and 0.1329–0.1431 on B5.The non-learned SingleBest reference yields G = 0.2608 (26.1 pp) on B5, distinct from the 21 pp Figure 5 maximum.Source: S Inner-selector stress-test full… · p. 28
Loading 2609.13785v1…