Partition Scores Are Not System Scores: Deployment-Fidelity Gaps in Decomposed Algorithm Selection
Jiachen Zhang, Yu Tang, Li Zhu
cs.AI · cs.LG
Quick verdict
Partition-level oracle scores overstate decomposed AS systems; simple but sound math, convincing 5-benchmark evidence; formal novelty thin.
Summary
The paper studies decomposed algorithm selection, where a family selector first picks an algorithm family (e.g., tree ensembles or SAT encodings) and a learned within-family selector then picks the concrete algorithm. It observes that the commonly reported partition-level score grants an oracle choice within the predicted family, and defines the deployment-fidelity gap G(R) = S_part − S_e2e to quantify that overstatement, supported by two accounting lemmas, a per-instance margin-regret stability condition (Theorem 1), and a partition-only identification interval (Theorem 2). Across five public benchmarks — TabZilla, TabRepo, TALENT, MAXSAT-PMS-2016, PROTEUS-2014 — all 15 decomposed cells show positive G(R) (0.012 to about 0.13) with Wilcoxon p < 1e-15 and bootstrap CIs excluding zero. Four of ten decomposition-vs-flat decisions flip sign end-to-end (B2/B4), though with small margins (-0.0031 to -0.0077); PROTEUS' 33-point partition advantage shrinks to 20 points (rho about 0.41). All 15 identification intervals cross zero, so partition reports alone cannot certify a deployable winner. A training-side gap-correction diagnostic recovers the sign on all four flipping cells, and a deployment-aware family selector shrinks G everywhere. Limitations: the formal results are definitional rather than deep; small-margin sign flips are sensitive to the within-family selector; the identification interval is empirically almost always uninformative; and no public code URL is stated.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Partition-level scores in decomposed algorithm selection are oracle-assisted upper bounds, and the deployment-fidelity gap G(R) = Spart − Se2e quantifies their overstatement of deployable end-to-end utility.
- Across five public benchmarks, all 15 decomposed cells have positive G(R), from 0.012 (TabZilla) to about 0.13 (PROTEUS-2014), with CIs excluding zero and Wilcoxon p < 1e-15.
- Four of ten decomp-vs-flat decisions have sign-changing point estimates (B2 and B4), though with small end-to-end margins of -0.0031 to -0.0077.
- Partition-only reports, even augmented with selected-family utility ranges, cannot certify the deployable winner because all 15 identification intervals strictly cross zero.
- A training-side gap-correction diagnostic recovers the point-estimate deployable sign on all four sign-changing cells, and a deployment-aware family selector shrinks G(R) on every benchmark.
Strengths
Carefully scoped, non-accusatory literature audit
Appendix R (Table 14) states explicitly that it does not allege misuse by any cited work — VBS, selected-portfolio VBS, virtual-best encoding, and best-in-family reporting are documented as explicit upper bounds (e.g., Proteus reports VB-CSP/VB-SAT alongside its deployable row); the contribution is framed as constructing the missing deployable counterpart, not attacking prior papers.
Unusually thorough robustness battery for a methodology claim
Family-mapping sensitivity on B4 including a random-placebo partition (App. J: safety condition fails under all four partitions), PROTEUS feature-policy (36 vs 198 features: G 0.134→0.100) and cutoff (3600s vs 1800s: essentially unchanged) checks (App. L), rank-utility transform sensitivity (App. M), and a 7-class within-family selector sweep where learned selectors keep G in 0.133–0.143 on B5 (App. S).
Common-instance discipline with machine-precision identity checks
Actionable deliverables with stated failure modes
Weaknesses
Formal results are definitional rather than deep
Headline '4/10 sign changes' rests on small, selector-sensitive point estimates
Theorem 2's identification-interval diagnostic is empirically vacuous
No public code URL stated
G(R) is conditional on modest inner-selector tuning
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets an evaluation-methodology problem in algorithm selection (AS): when a pipeline decomposes selection into family-then-algorithm (tree ensembles vs. classics in tabular AutoML; CSP-native vs. three SAT encodings in combinatorial search), a common reported score — the partition score — grants an oracle pick of the best member of the predicted family. The authors formalize the overstatement as the deployment-fidelity gap G(R) = S_part(R) − S_e2e(R) (Eq. 1), prove two accounting lemmas (Lemma 1: G equals within-family regret; Lemma 2: Ae2e = Apart − (G(R1) − G(R2))), derive a per-instance margin-regret stability condition (Theorem 1) and a partition-only identification interval (Theorem 2), and quantify everything on five public benchmarks (Table 1). Headline claims: all 15 decomposed cells have positive G(R) (0.012 on TabZilla to ~0.13 on PROTEUS-2014); 4/10 decomp-vs-flat decisions flip sign end-to-end; partition reports cannot certify deployable winners because all identification intervals cross zero. Notably, Appendix R's audit (Table 14) is explicitly non-accusatory — the target is a reporting object, not any cited paper.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the deployment-fidelity gap G(R) in algorithm selection?
In decomposed algorithm selection, a pipeline first picks an algorithm family and then a concrete algorithm within it. The partition-level score grades the family using an oracle pick of its best member; the end-to-end score uses the learned within-family selector that actually ships. G(R) = Spart − Se2e is the difference: it measures how much the oracle-assisted partition score overstates the deployable system, and it is always non-negative.
What did this paper find across its benchmarks?
On five public benchmarks — TabZilla, TabRepo, TALENT (tabular AutoML) and MAXSAT-PMS-2016, PROTEUS-2014 (combinatorial CSP/SAT) — every decomposed pipeline showed a positive gap, from 0.012 on TabZilla to about 0.13 on PROTEUS-2014. Four of ten decomposition-vs-flat comparisons flipped sign end-to-end (with small margins), and PROTEUS' 33-point partition advantage shrank to 20 points.
Does this paper accuse prior papers of wrong evaluation?
No. The literature audit in Appendix R explicitly states it does not allege misuse: cited works such as AutoFolio, ASlib, and Proteus report oracle quantities as clearly labeled upper bounds alongside deployable systems. The contribution is defining the deployable counterpart (the within-family selector) and measuring the previously unsurfaced gap between the two.
What should authors of algorithm-selection papers report?
Per the paper's checklist (Appendix E): partition and end-to-end scores side by side, the gap G(R) with a bootstrap CI, advantage transfer quantities (Apart, Ae2e, rho), the identification interval, and documentation of the within-family selector class, family mapping, feature-availability policy, timeout/PAR10 conventions, and the common valid-instance set used for comparisons.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The metadata-supplied abstract cuts off mid-sentence ('direct end-t'), but the embedded full text contains the complete abstract, so no content loss affects this review; the extracted text runs cleanly through Appendix S with no truncation at the true end.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.