How Much of the Routing Gap Is Real? Decomposing the Router-to-Oracle Gap into Reproducible Specialist Advantage and Single-Draw Label Noise

• URL: http://arxiv.org/abs/2607.03436v2
• Date: Tue, 07 Jul 2026 05:35:41 GMT
• Title: How Much of the Routing Gap Is Real? Decomposing the Router-to-Oracle Gap into Reproducible Specialist Advantage and Single-Draw Label Noise
• Abstract summary: Single-draw noise is a substantial minority of the gap, larger on unsaturated benchmarks and approaching half on the hardest queries.<n>We release a multi-sample oracle protocol that routing benchmarks can adopt.
• Score: 0.10152838128195468
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: On real open-model pools, 12--36% of the reported router-to-oracle gap is single-draw label noise that no single-commit router can capture, while the majority is genuine, recoverable specialist advantage; this work proves why (a recoverability asymmetry) and releases a protocol to measure it. Routing among large language models (LLMs) trades cost for quality, motivated by the gap between learned routers and a per-instance oracle. But under stochastic decoding that oracle is a single Bernoulli draw, not a reproducible property. We recast the question structurally: the expected oracle decomposes as $O^{\exp}=O^{\mathrm{repro}}+Δ$, into reproducible single-commit headroom $O^{\mathrm{repro}}$ and a non-negative single-commit selection floor $Δ$. Our main result is a recoverability asymmetry: this floor is closed by no single-commit router (deterministic or randomized), yet is provably recovered by test-time sampling: best-of-$K$ on the committed model, at the oracle's own budget, dominates the independent-pool single-draw oracle. This cap needs no cross-model independence, pinning "not recoverable" to single-commit selection, not to information. The floor's magnitude is a prospective, conservative localization, not an audit: LLMRouterBench (33 models, 391,645 instances) builds its oracle as a per-query union of single $T=0.2$ draws, so its 20-point gap is by construction a union of stochastic draws; since $O^{\mathrm{repro}}$ is non-identifiable at $k=1$, we re-estimate by fresh $k\ge20$ resampling under one-sided, dependence-corrected bounds. Across three controlled open-model re-generations (arithmetic, competition math, and non-math science), single-draw noise is a substantial minority of the gap, larger on unsaturated benchmarks and approaching half on the hardest queries. We release a multi-sample oracle protocol that routing benchmarks can adopt.

Related papers

• An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order [6.657272312990604]
  Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle.<n>We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set or reports non-realizability.
  arXiv  Detail & Related papers  (2026-09-09T14:02:47Z)
• Opportunity Is Not Realizability: Selection-Valid Diagnostics for Multi-LLM Routing [0.9558392439655014]
  Oracle routing measures how much a pool of language models could gain from per-query selection.<n>We prove selection-valid confidence intervals that survive choosing the best fixed model or the best member of a router family.<n>The realizable share of oracle opportunity is small and certifiable.
  arXiv  Detail & Related papers  (2026-08-08T17:53:43Z)
• Lower Bounds for PIR with Preprocessing from Blackbox Cryptography [57.20693707878285]
  We study the limits of single-server private information retrieval (PIR) with preprocessing.<n>Our work presents computation lower bounds for any single-server PIR with preprocessing.
  arXiv  Detail & Related papers  (2026-07-07T16:12:48Z)
• Cluster, Route, Escalate: Cascaded Framework for Cost-Aware LLM Serving [69.5155152169752]
  We propose a two-stage cascaded solution for large language models (LLMs)<n>Stage 1 clusters incoming queries and assigns each cluster to its most cost-effective model.<n>Stage 2 adds a quality estimation (QE) cascade; when an output from Stage 1 is judged low-quality, the query is escalated to a stronger model.<n>On the test datasets, the cascaded system retains 97-99% of the strongest model's accuracy while reducing Time Per Output Token (TPOT)<n>It requires only task-correctness labels and adapts to changes in the model pool without manual reconfiguration.
  arXiv  Detail & Related papers  (2026-06-25T18:29:24Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Representation Without Reward: A JEPA Audit for LLM Fine-Tuning [1.2691047660244335]
  Joint-embedding predictive architectures (JEPAs) propose that a model should learn more useful abstractions when trained to predict latent representations rather than observed outputs.<n>For autoregressive language-model fine-tuning the principle entails a stricter requirement: the induced hidden-state geometry must reach the language-model head emphand improve the decoded task metric.<n>We test that requirement under a fixed Llama-3.2-1B-Instruct LoRA harness on natural-language-to-regex generation.
  arXiv  Detail & Related papers  (2026-05-14T20:27:32Z)
• Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning [37.15283418677639]
  Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner.<n>We replace the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization oracle.<n>We show that our algorithm reduces the total query complexity down to $O(Td_mathrmVC+1)$ while perfectly preserving near-optimal expected regret.
  arXiv  Detail & Related papers  (2026-05-08T02:41:23Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  We study running time, in terms of first order oracle queries, of differentially private empirical/population risk of Lipschitz losses.<n>We show that expected running time $(minfracsqrtd2, fracdlog(1/))$ is necessary to achieve $$ excess risk on problems of dimension $d when $dgeq 1/2$.
  arXiv  Detail & Related papers  (2025-11-17T23:58:11Z)
• DISCO: Diversifying Sample Condensation for Efficient Model Evaluation [59.01400190971061]
  Costly evaluation reduces inclusivity, slows the cycle of innovation, and worsens environmental impact.<n>We argue that promoting diversity among samples is not essential; what matters is to select samples thatmaximise diversity in model responses.<n>Our method, $textbfDiversifying Sample Condensation (DISCO)$, selects the top-k samples with the greatest model disagreements.
  arXiv  Detail & Related papers  (2025-10-09T08:53:59Z)
• Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning [17.389446817000945]
  We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles.
  arXiv  Detail & Related papers  (2025-05-30T18:11:58Z)
• The Projected Covariance Measure for assumption-lean variable significance testing [3.8936058127056357]
  A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. We study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests.
  arXiv  Detail & Related papers  (2022-11-03T17:55:50Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)

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.