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

• URL: http://arxiv.org/abs/2609.13785v1
• Date: Sat, 12 Sep 2026 07:55:42 GMT
• Title: Partition Scores Are Not System Scores: Deployment-Fidelity Gaps in Decomposed Algorithm Selection
• Abstract summary: In decomposed algorithm selection, an analogous partition-level score grants an oracle choice of the best algorithm within the selected family.<n>We define the deployment-fidelity gap G(R) as the difference between partition-level and deployable end-to-end utility.
• Score: 7.302544154053966
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds [58.529749203758634]
  Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments.<n>We introduce AlgoWorlds, a benchmark that transforms formally specified optimization problems into partially observed decision environments.<n>AlgoWorlds contains 240 environments covering ten optimization families and four workload levels.
  arXiv  Detail & Related papers  (2026-08-29T18:37:41Z)
• Contrastive Branch Policy Optimization [16.16893757028268]
  Reinforcement learning with verifiable rewards (RLVR) enables language models to learn multi-turn interaction with external tools.<n>Existing methods tend to conflate two distinct problems: allocating a fixed rollout budget and translating branch outcomes into token-level credit.<n>We introduce Contrastive Branch Policy Optimization (CBPO), which disentangles these two problems and assigns a dedicated mechanism to each.
  arXiv  Detail & Related papers  (2026-08-25T09:25:55Z)
• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• Minibatch Selection via Partition Matroid Constrained Gradient Matching [19.541112219411556]
  Training large language models (LLMs) on heterogeneous data requires selecting minibatches that balance convergence speed with coverage across domains.<n>We propose PartitionSel, a cross-domain minibatch selection approach that maximizes a validation-guided gradient-matching utility under per-domain budgets encoded as a partition-matroid constraint.
  arXiv  Detail & Related papers  (2026-06-06T03:16:19Z)
• Ternary Decision Trees with Locally-Adaptive Uncertainty Zones [0.0]
  ternary decision trees augment each split node with an uncertainty zone of half-width delta centered on the optimal threshold.<n> delta is computed locally at each node from statistics already available during standard CART split finding.<n>We evaluate five delta-estimation methods: quality-plateau, class-overlap, gain-ratio, node-bootstrap and margin.
  arXiv  Detail & Related papers  (2026-05-21T17:11:19Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• Optimal partition selection with Rényi differential privacy [24.85689199092059]
  We present an extension of our optimal algorithm tuned for $L2$ bounded partition selection.<n>We show that our primitive can be easily plugged into state of the art partition selection algorithms.
  arXiv  Detail & Related papers  (2026-03-10T04:13:38Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• Ranking Free RAG: Replacing Re-ranking with Selection in RAG for Sensitive Domains [13.58151841630302]
  We propose a novel method METEORA that replaces re-ranking in RAG with a rationale-driven selection approach.<n>We show METEORA improves generation accuracy by 33.34% while using approximately 50% fewer chunks than state-of-the-art re-ranking methods.<n>In adversarial settings, METEORA significantly improves the F1 score from 0.10 to 0.44.
  arXiv  Detail & Related papers  (2025-05-21T20:57:16Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.