arXiv AI

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

The paper argues that partition-level scores used in decomposed algorithm selection overestimate what a deployable selector can achieve. It introduces the deployment‑fidelity gap, G(R), which measures the difference between partition‑level and end‑to‑end utility, and derives conditions under which a partition choice is truly deployment‑optimal. Experiments on five public benchmarks show that every decomposed pipeline has a positive gap, with some cases where the partition advantage disappears or reverses when evaluated end‑to‑end, highlighting the need to report both partition and end‑to‑end scores.

arXiv AI
Aug 25

Right-Sizing LLM-Agent Decomposition in VAT Determination: A Pilot Controlled Sweep

The study evaluates how to best split tasks among large‑language‑model agents for cross‑border VAT determination, comparing one broad agent to configurations ranging from one to five narrow agents. Across 4,400 runs—including token‑matched and failure‑injection scenarios—the intermediate configurations achieved the highest accuracy but did not surpass the fine‑endpoint benchmark, leaving the optimal decomposition hypothesis unconfirmed. The pilot provides a preregistered heuristic for right‑sizing decomposition, along with an oracle, dataset, and analysis pipeline.

By Pedro Santos
arXiv AI
Sep 7

Atlas: Optimizing Deployment of Compound AI Workflows on Heterogeneous Clusters

Atlas is a framework that optimizes the deployment of compound AI workflows on heterogeneous clusters by selecting execution plans that satisfy service level objectives (SLOs). It introduces MAP, a Markovian Accuracy Predictor, which estimates configuration accuracy using local conditional accuracy transitions between adjacent workflow stages, avoiding exhaustive end‑to‑end profiling. Atlas formulates plan selection as a mixed‑integer linear program, achieving near‑oracle accuracy while reducing deployment cost by up to 42% and profiling cost by up to 2.6×.

By Milos Gravara, Andrija Stanisic, Stefan Nastic
arXiv Machine Learning
3d ago

When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming

The paper introduces the Weighted Variability Score (WVS), a metric that aggregates dispersion in runtime, optimality gap, LP iterations, and branch‑and‑bound nodes across repeated runs of MIP solvers. Experiments on 100 randomized runs of MIPLIB 2017 instances show a right‑skewed distribution, with many instances stable but some exhibiting large variability not explained by basic properties. A tree‑based predictor using static and root‑level features achieves a mean absolute error of 0.058 and Spearman rank correlation of 0.65, with root degeneracy, matrix structure, coefficient ranges, and presolve reductions identified as key drivers of high WVS.

By Mourchid Adegbindin, Brenda Dietrich, Jamol Pender, Andrea Lodi
arXiv Machine Learning
Sep 21

Available Guardrails: Certifying Selective Prediction across ML Systems

The paper introduces a method to certify selective prediction in machine learning systems by computing the availability of safety gates through exact-binomial inversion and dynamic programming. It demonstrates that a truth-informed planner can significantly improve mean coverage over naive approaches, and that reallocating error budgets further enhances coverage across diverse applications such as LLM tool‑calling, content moderation, lesion classification, and recommendation. The study highlights the importance of planning and finite‑sample estimation in ensuring reliable, granular deployment of selective predictors.

By Parivesh Priye, Yufeng Wang, Haibin Ling, Michael Chaykowsky
arXiv AI
Aug 20

Selection, Recombination, or a Fresh Solve? A Candidate-Free Control for Single-Pass Test-Time Aggregation

The paper investigates whether providing candidate solutions during test‑time aggregation improves or harms accuracy compared to a fresh solve that does not use any candidates. Using Qwen3‑4B on AIME‑2025 and HMMT‑2025, the authors find that conditioning on multiple correct candidates boosts accuracy (+0.290), while conditioning on an all‑wrong candidate pool reduces accuracy (−0.123); the effect for a single correct candidate remains unclear. The study also explores structured interventions and placebo controls, but the underlying mechanisms of these effects are not resolved.

By Guiv Farmanfarmaian