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

Jiachen Zhang; Yu Tang; Li Zhu

cs.AISep 12, 2026

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

Authors: Jiachen Zhang, Yu Tang, Li Zhu

Organizations: Department of Computer Science University of Oregon · City University of Hong Kong

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.

Figures & tables

ID	Benchmark	#inst.	#alg.	#fam.	Domain	Native metric
B1	TabZilla	133	22	4	tabular ML	accuracy
B2	TabRepo (cls.)	202	11	4	tabular ML	1 $-$ error rate
B3	TALENT (cls.)	200	34	4	tabular ML	accuracy
B4	MAXSAT-PMS-2016	556	19	4	combinatorial search	PAR10
B5	PROTEUS-2014	3565	22	4	combinatorial CSP/SAT	runtime

Table 1: Benchmark registry. Native metrics are converted to per-instance utility (App. A ). B5 retains the common valid-instance set after dropping all-timeout rows from

4021

raw PROTEUS-2014 instances.

Figure 1: Deployment-fidelity gap

G(R)=S_{\mathrm{part}}-S_{\mathrm{e2e}}

for every (benchmark, decomposition) cell. Bars show

95\%

percentile-bootstrap confidence intervals on the per-instance gap. All decomposed pipelines exhibit positive gaps; flat baselines are included as controls. The singleton-flat invariant enforces

G(F)=0

for every flat baseline by using identical missing-value fallback on partition and end-to-end singleton scores.

ID	Pair	$A_{\mathrm{part}}$	$A_{\mathrm{e2e}}$	$G(R_{1})$	$G(R_{2})$	$\rho$	Regime
B1	mc vs flat	$+0.0145$	$+0.0024$	$0.0121$	$0.0000$	$0.835$	high absorption
B1	pw vs flat	$+0.0143$	$+0.0013$	$0.0130$	$0.0000$	$0.912$	high absorption
B2	mc vs flat	$+0.0446$	$-0.0077$	$0.0523$	$0.0000$	$1.172$	sign change
B2	pw vs flat	$+0.0471$	$-0.0037$	$0.0507$	$0.0000$	$1.078$	small sign change
B3	mc vs flat	$+0.1069$	$+0.0316$	$0.0752$	$0.0000$	$0.704$	partial absorption
B3	pw vs flat	$+0.1079$	$+0.0372$	$0.0707$	$0.0000$	$0.655$	partial absorption

Table 2: Decomp-vs-flat advantage transfer. “pw” = pairwise OVO, “mc” = multiclass softmax.

\rho>1

marks sign change relative to the partition-level advantage; small end-to-end margins should be read as point estimates rather than large-margin reversals. All quantities are recomputed on the four-way intersection of finite values for the specific pair, so the gap values in this table need not match the per-cell marginal gaps in Table 12 ; on each pair,

A_{\mathrm{part}}-A_{\mathrm{e2e}}=G(R_{1})-G(R_{2})

holds exactly (Lemma 2 ). Pairwise vs. multiclass comparisons all have

|A_{\mathrm{part}}|<5\times 10^{-3}

and are reported in Appendix O (Table 13 ).

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Research question	Metric	Why
Is the family partition useful in principle?	$S_{\mathrm{part}}$ + VBS upper bound	measures whether the selected family contains strong algorithms
Is the system deployable?	$S_{\mathrm{e2e}}$	deployment uses a learned within-family selector, not an oracle
Does method $R_{1}$ beat $R_{2}$ ?	both $A_{\mathrm{part}}$ and $A_{\mathrm{e2e}}$	B2/B4 show sign-changing point estimates; B1/B5 show strong absorption
Is the within-family selector adequate?	$G(R)$ with CI	Lemma 1 : $G$ equals within-family regret
Is partition advantage reliable?	$\rho$	quantifies absorption / reversal

Appendix

Table 3: Metric-reporting decision framework grounded in our findings.

Figure 2: Left: per-benchmark within-family regret on the predicted family against

G(R)

(Lemma 1 ). Right:

A_{\mathrm{part}}-A_{\mathrm{e2e}}

versus

G(R_{1})-G(R_{2})

for the pairwise-vs-multiclass comparison on every benchmark (Lemma 2 ; residuals

\leq 5\times 10^{-16}

Figure 3: Gap-corrected vs. raw partition advantage on all

15

pairwise comparisons. (a) crosses are raw

A_{\mathrm{part}}

, filled circles are corrected

\widehat{A}_{\mathrm{corr}}

; corrected points are closer to the

y=x

identity than the raw partition estimates. (b) MAE reduction (%) for each decomp-vs-flat comparison; gain is positive on B2–B5 and negative on the B1 high-absorption cells, where the deployable advantage is close to zero and validation-side gap estimates can over-correct.

Figure 4: Family-mapping sensitivity on B4. Bars are

G(R)

A_{\mathrm{part}}

, and

A_{\mathrm{e2e}}

per partition kind. B4 fails the decomp-vs-flat safety condition

A_{\mathrm{part}}>G(R)

for every partition tested, showing that the gap magnitude is not driven solely by the default taxonomy. B5 mapping sensitivity beyond the primary semantic PROTEUS partition is not used for paper claims.

ID	Partition	$K$	$A_{\mathrm{part}}$	$A_{\mathrm{e2e}}$	$G(R)$	safe?
B4	P1 default	$4$	$+0.0202$	$-0.0047$	$0.0248$	no
B4	P2 coarse	$2$	$+0.0254$	$-0.0038$	$0.0291$	no
B4	P3 performance-cluster	$4$	$+0.0216$	$-0.0047$	$0.0262$	no
B4	P4 random placebo (mean of 5)	$4$	$+0.0163$	$-0.0042$	$0.0205$	no
B5	P1 semantic (CSP-native + 3 SAT enc.)	$4$	$+0.3333$	$+0.1973$	$0.1360$	yes

Appendix

Table 4: Family-mapping sensitivity. Each row is one (benchmark, partition) cell with the resulting gap and decomp-vs-flat advantages. “safe” = general safety condition

A_{\mathrm{part}}>\Delta G

where

\Delta G=G(R)-G(F)

. P4 (random) is averaged over five seeds. B4 fails the safety condition under every partition we test (default, coarse, performance-cluster, random placebo); B5 (PROTEUS-2014) reports the primary semantic partition

\Pi_{\text{P1}}

only — coarser K-sensitivity for B5 is in the companion reproducibility package. Family mapping changes the gap magnitude but does not remove it.

ID	$S_{\mathrm{e2e}}^{\mathrm{O}}$	$S_{\mathrm{e2e}}^{\mathrm{DA}}$	$\Delta S_{\mathrm{e2e}}$	$G^{\mathrm{O}}$	$G^{\mathrm{DA}}$	$\Delta G$	Sign chg. O / DA
B1	$0.9165$	$0.9174$	$+0.0009$	$0.0121$	$0.0114$	$-0.0006$	no / no
B2	$0.8961$	$0.9007$	$+0.0046$	$0.0523$	$0.0504$	$-0.0019$	yes / yes
B3	$0.7605$	$0.7658$	$+0.0053$	$0.0752$	$0.0723$	$-0.0029$	no / no
B4	$0.9700$	$0.9710$	$+0.0011$	$0.0248$	$0.0240$	$-0.0008$	yes / yes
B5	$0.8129$	$0.8085$	$-0.0045$	$0.1365$	$0.1286$	$-0.0079$	no / no

Appendix

Table 5: Deployment-aware family selector (DA) vs. oracle-trained family selector (O), with both sharing PerAlgRegressionWithin .

\Delta_{X}=X_{\mathrm{DA}}-X_{\mathrm{O}}

. DA shrinks

G(R)

on every benchmark; it improves

S_{\mathrm{e2e}}

on B1–B4 and trades off slightly on B5 PROTEUS-2014, where the within-family utility range is large enough that targeting deployable utility moves family decisions toward families with smaller oracle margin. Sign-changing point estimates relative to flat persist on B2 and B4 — the safety condition remains the primary diagnostic.

Feature policy	Pipeline	$S_{\mathrm{part}}$	$S_{\mathrm{e2e}}$	$G$
csp ( $36$ ) primary	pairwise	$0.954$	$0.820$	$0.134$
csp ( $36$ ) primary	multiclass	$0.951$	$0.816$	$0.135$
csp ( $36$ ) primary	flat	$0.622$	$0.622$	$0.000$
all ( $198$ ) sensit.	pairwise	$0.945$	$0.845$	$0.100$
all ( $198$ ) sensit.	multiclass	$0.938$	$0.840$	$0.098$
all ( $198$ ) sensit.	flat	$0.669$	$0.669$	$0.000$

Appendix

Table 6: PROTEUS-2014 feature-policy sensitivity. Headline pipeline quantities under (a) the primary csp feature step (

36

features) and (b) the all-feature (

198

) sensitivity. The csp setting is the deployment model (encoding-conditional features are not visible to the family selector); the all-feature setting is a stronger-information setting that shows what would happen if the family selector could see encoding features computable only after an encoding has been chosen.

Cutoff	Pipeline	$S_{\mathrm{part}}$	$S_{\mathrm{e2e}}$	$G$
$3600$ s (primary)	pairwise	$0.954$	$0.820$	$0.134$
$3600$ s (primary)	multiclass	$0.951$	$0.816$	$0.135$
$3600$ s (primary)	flat	$0.622$	$0.622$	$0.000$
$1800$ s sensitivity	pairwise	$0.953$	$0.819$	$0.134$
$1800$ s sensitivity	multiclass	$0.948$	$0.812$	$0.136$
$1800$ s sensitivity	flat	$0.616$	$0.616$	$0.000$

Appendix

Table 7: PROTEUS-2014 cutoff sensitivity. Headline pipeline quantities under the

3600

s scenario cutoff (primary) and a

1800

s sensitivity in which any ok run exceeding

1800

s is re-classified as a timeout and penalised at PAR10. We do not extrapolate beyond the scenario cutoff because uncensored raw run logs are not available.

ID	Pair	$A_{\mathrm{part}}^{\mathrm{mm}}$	$A_{\mathrm{e2e}}^{\mathrm{mm}}$	$A_{\mathrm{part}}^{\mathrm{rank}}$	$A_{\mathrm{e2e}}^{\mathrm{rank}}$
B4	mc vs flat	$+0.020$	$-0.0047$	$+0.086$	$-0.162$
B4	pw vs flat	$+0.022$	$-0.0031$	$+0.087$	$-0.160$
B5	mc vs flat	$+0.328$	$+0.192$	$+0.237$	$-0.0004$
B5	pw vs flat	$+0.333$	$+0.197$	$+0.243$	$+0.0047$

Appendix

Table 8: Metric-transform sensitivity for decomp-vs-flat advantage transfer on B4–B5. Positive advantages favour decomposition. Min–max is the headline utility; rank utility maps the best algorithm on an instance to

1

and the worst to

0

. Rank utility confirms the B4 sign change and the strong B5 absorption pattern, although B5’s multiclass rank end-to-end margin is effectively zero.

Figure 5:

G(R)

averaged over family-selector choice, by within-family selector class. B1–B3 sweep four classes (per-algorithm GBDT, multiclass, pairwise OVO, single-best); B4–B5 sweep three (pairwise OVO is omitted on ASlib due to its

\mathcal{O}(|F|^{2})

solver-pair cost). Family-selector class changes

S_{\mathrm{part}}

negligibly (within

5\times 10^{-3}

), while within-family selector class shifts

G

by up to

2.2\times

on TALENT (B3) and produces a

0.21

gap on B5 under the main-sweep single-best-on-train selector.

ID	Fam. / Within	$S_{\mathrm{part}}$	$S_{\mathrm{e2e}}$	$G$
B1	PW / GBDT	$0.9284$	$0.9154$	$0.0130$
B1	PW / MC	$0.9284$	$0.9141$	$0.0143$
B1	PW / PW	$0.9284$	$0.9180$	$0.0104$
B1	PW / SB	$0.9284$	$0.9169$	$0.0115$
B1	MC / GBDT	$0.9286$	$0.9165$	$0.0121$
B1	MC / MC	$0.9286$	$0.9143$	$0.0143$

Appendix

Table 9: Within-family selector robustness sweep on B1–B3. Abbreviations: family selectors PW = pairwise OVO, MC = multiclass softmax; within-family selectors GBDT = per-algorithm gradient-boosted regressor, MC = multiclass classifier, PW = pairwise OVO classifier, SB = single-best-on-train. Each row is computed on its row-specific common valid-instance mask;

G=S_{\mathrm{part}}-S_{\mathrm{e2e}}

holds before rounding.

Figure 6: Deployment-safety plot for the

10

decomp-vs-flat comparisons. By Corollary 2 (general form), the partition-level advantage transfers iff

A_{\mathrm{part}}>\Delta G

, where

\Delta G=G(R)-G(F)

, i.e. below the dashed

y=x

line. B1, B2, B4 occupy distinct absorption regimes: B2 and B4 lie in the unsafe (red) region and have sign-changing point estimates; B1 remains deployment-safe but is almost erased. B3 and B5 (PROTEUS-2014) are deployment-safe but partially absorbed; B5’s

33

-point partition advantage shrinks to a

20

-point end-to-end advantage,

\rho\approx 0.41

. All flat controls have

G(F)=0

ID	Pairs	Crosses 0	Median $\bar{W}$	Mean $\|A_{\mathrm{part}}\|$
B1	3	3	$0.363$	$0.010$
B2	3	3	$0.102$	$0.031$
B3	3	3	$0.233$	$0.066$
B4	3	3	$0.134$	$0.014$
B5	3	3	$0.378$	$0.221$

Appendix

Table 10: Partition-only identification intervals (Theorem 2 ) summary. “Crosses 0” counts the fraction of pairs whose interval strictly crosses zero, i.e. the fraction of comparisons on which the partition-level report alone (with selected-family range information) does not certify a deployable winner. Median interval width

\bar{W}=(W_{R_{1}}+W_{R_{2}})/2

is the half-interval that the partition-level report cannot resolve.

ID	$n$	pairwise	multiclass
B1	$133$	$0.248$	$0.263$
B2	$202$	$0.391$	$0.371$
B3	$192/191$	$0.557$	$0.545$
B4	$556$	$0.228$	$0.234$
B5	$3565$	$0.381$	$0.387$

Appendix

Table 11: Per-instance margin–regret diagnostic rates for decomposed pipelines. The reported quantity is the selected-family existential violation rate from Theorem 1 ; bootstrap intervals are omitted here for space and are included in results/exp9_margin_regret .

Figure 7: Partition-level advantage

A_{\mathrm{part}}

against end-to-end advantage

A_{\mathrm{e2e}}

across all

15

pairwise method comparisons (color by benchmark, shape by pair type). The dashed diagonal is full transfer (

A_{\mathrm{part}}=A_{\mathrm{e2e}}

); points near the horizontal axis indicate absorption; points in opposite quadrants indicate sign changes. These cells are outlined in red. (a) full range showing B5’s outlier position; (b) zoom on the central region containing the four sign-changing cells (decomp-vs-flat on B2 and B4 — all in the lower-right quadrant, where partition prefers decomposition but e2e prefers flat), the high-absorption B1 cells, and the near-origin pairwise-vs-multiclass comparisons.

ID	Decomposition	$S_{\mathrm{part}}$	$S_{\mathrm{e2e}}$	$G$	$95\%$ CI	$p$	$n$
B1	pairwise	$0.9284$	$0.9154$	$0.0130$	$[0.0091,\,0.0176]$	$8.15{\times}10^{-17}$	$133$
B1	multiclass	$0.9286$	$0.9165$	$0.0121$	$[0.0087,\,0.0162]$	$5.57{\times}10^{-17}$	$133$
B1	flat	$0.9141$	$0.9141$	$0.0000$	$[0.0000,\,0.0000]$	$1$	$133$
B2	pairwise	$0.9508$	$0.9001$	$0.0507$	$[0.0401,\,0.0625]$	$1.96{\times}10^{-30}$	$202$
B2	multiclass	$0.9484$	$0.8961$	$0.0523$	$[0.0414,\,0.0645]$	$4.37{\times}10^{-30}$	$202$
B2	flat	$0.9037$	$0.9037$	$0.0000$	$[0.0000,\,0.0000]$	$1$	$202$

Appendix

Table 12: Full deployment-fidelity-gap table by (benchmark, decomposition).

G=S_{\mathrm{part}}-S_{\mathrm{e2e}}

; CI is a

95\%

percentile-bootstrap interval over per-instance gaps;

p

is the paired Wilcoxon

p

-value comparing

u_{\mathrm{part}}

u_{\mathrm{e2e}}

on the same instances.

ID	Pair	$A_{\mathrm{part}}$	$A_{\mathrm{e2e}}$	$G(R_{1})$	$G(R_{2})$	$\rho$	Sign chg.
B1	pw vs mc	$-0.0002$	$-0.0011$	$0.0130$	$0.0121$	NA	no
B1	mc vs flat	$+0.0145$	$+0.0024$	$0.0121$	$0.0000$	$+0.835$	no
B1	pw vs flat	$+0.0143$	$+0.0013$	$0.0130$	$0.0000$	$+0.912$	no
B2	pw vs mc	$+0.0024$	$+0.0040$	$0.0507$	$0.0523$	NA	no
B2	mc vs flat	$+0.0446$	$-0.0077$	$0.0523$	$0.0000$	$+1.172$	yes
B2	pw vs flat	$+0.0471$	$-0.0037$	$0.0507$	$0.0000$	$+1.078$	yes

Appendix

Table 13: Full advantage-transfer table: all

15

(benchmark, pair) comparisons. “pw” = pairwise OVO, “mc” = multiclass softmax.

\rho=(G(R_{1})-G(R_{2}))/A_{\mathrm{part}}

marked NA when

|A_{\mathrm{part}}|<5\times 10^{-3}

. The final column marks sign-changing point estimates, not a large-margin decision threshold.

Algorithm Selection

Algorithm selection predicts which solver, model, or strategy will work best for a given instance, context, or computational budget.

See all 50 papers

Deployment-complete benchmarking
May 25, 2026El Mustapha Mansouri, Keigo AraiBenchmark Auditing Benchmark Construction
School of Engineering, Institute of Science Tokyo, Yokohama, Kanagawa 226-8501, Japan
Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
Oct 10, 2026Yuhe Sui, Yingzhi TangDecision-Making under Uncertainty Adaptive Sampling
Quantitative Research Society, Singapore · Nanyang Technological University, Singapore · The Chinese University of Hong Kong, Shenzhen, China
Pareto-Optimal Anytime Algorithms via Bayesian Racing
Mar 9, 2026Jonathan Wurth, Helena Stegherr, Neele Kemper +2Algorithm Selection Pareto Optimization
Universität Augsburg, Augsburg, Germany

May 25, 2026J/K move · Enter open · S save

Deployment-complete benchmarking

El Mustapha Mansouri, Keigo Arai

School of Engineering, Institute of Science Tokyo, Yokohama, Kanagawa 226-8501, Japan

Benchmark Auditing Benchmark Construction Benchmark Design Benchmark Validity

Open paper AskPDF arXiv

Benchmarks increasingly guide deployment, procurement and scientific screening, yet a score supports only the response it records, not necessarily the deployment action. We introduce deployment-complete benchmarking, which tests whether benchmark evidence determines a deployment action. A benchmark is complete for a claim exactly when the action is constant on each evidence fiber; mixed fibers expose missing deployment information, and completion curves quantify the evidence required to resolve ambiguity. In controlled response spaces, benchmark-channel conformal coverage of 94.98% transferred poorly to an unmeasured deployment channel (10.07%), whereas response-rank intervals achieved 94.91% coverage; even zero benchmark error certified only 45.4% of candidates at the largest residual size. Public audits revealed incompleteness, including 97.9% mixed Tox21 fibers and zero median certifiable fraction in main Matbench and JARVIS audits. In held-out replays, certify-then-acquire reduced false decisions from 1.19% to 0.027% in Tox21 and from 20.3% to 0.128% in JARVIS, while changing model choice and identifying deployment-relevant probes. Deployment-ready benchmarks should report evidence, supported actions, ambiguity and completion cost rather than scores alone.

Abstract

Algorithm Selection

Explore similar work

Deployment-complete benchmarking

Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

Pareto-Optimal Anytime Algorithms via Bayesian Racing