When the Cheapest Feasible Router Fails: Auditing Deployment Commitments in Cost-Aware LLM Routing

Minxuan Hu, Qishi Zhan, Ziheng Chen, Zhengtao Yao, Zihan Dong, Jiayu Yi, Wenxi SunarXiv 2026 · arXiv

This paper tackles a critical but often overlooked problem in the operational lifecycle of Large Language Models (LLMs): deployment commitment. When we build a system to route queries between expensive and cheap models, how do we know the router we’ve chosen will actually honor its performance guarantees once it hits production?

TL;DR

Even when LLM routers are audited on independent data, the "cheapest feasible" option frequently fails to meet its service-level agreements (SLAs) on new traffic due to selection bias and sampling noise. The authors introduce Menu-Aware Routing Commitment (MARC), a framework that uses uncertainty-aware auditing to decide whether to deploy the apparent winner, swap it for a safer alternative, or defer deployment entirely, reducing failure rates from ~32% to less than 1%.

What Problem Does This Paper Address?

In cost-aware LLM routing, an operator typically defines a "contract"—for example, "the system must maintain at least 80% accuracy (risk ceiling) and answer at least 70% of queries (coverage floor)." To save money, the operator picks the cheapest routing policy that appears to satisfy these constraints during an audit.

The authors identify a "hidden" failure mode: optimism bias. Because cost optimization favors policies that sit right on the edge of feasibility, small sampling fluctuations in the audit data can make a failing policy look successful. Even if you use a separate validation set to pick the winner, the "point-estimate" (a single number like 80.1% accuracy) is often a "lucky" fluke. In their study, the cheapest audit-feasible router violated its contract in 32.22% of deployments.

Methods

The authors propose MARC (Menu-Aware Routing Commitment), a post-construction interface that qualifies policies based on statistical evidence rather than just point estimates.

Key components include:

  • Evidence-Aware Qualification: Instead of checking if a policy is feasible, MARC checks if there is enough evidence that it is feasible. It uses two main variants:
  • MARC-P (Policywise): Uses bootstrapping to create one-sided confidence bounds for each policy, adding a fixed safety margin ($\delta$).
  • MARC-S (Simultaneous): A more rigorous approach that applies a "menu-level" correction to account for the fact that you are testing many policies at once (addressing the multiple testing problem).
  • Cost-Tolerant Selection: MARC identifies an "affordable subset" of qualified policies—those within a cost tolerance ($\kappa$) of the cheapest one.
  • Three Operational Actions:
    1. Retain: Deploy the cheapest winner if it has strong evidence.
  • Replace: Deploy a slightly more expensive policy that has much stronger evidence of safety.
  • Defer: Refuse to deploy any policy if none meet the evidence threshold.

Datasets

The study utilizes two primary benchmarks:

  1. RouterBench: 19 task families (including MMLU subdomains) with deterministic menus of simple and selective routing policies.
  2. LLM-RouterBench: Used for a "learned semantic routing" study involving 10 datasets, 12,444 queries, and 11 different models. This tested whether the problem persists in more complex, KNN-based routing architectures (it does).

Key Insights and Ideas

  • The "Cheapest" is a Trap: Selecting for the lowest cost naturally selects for the most "optimistic" error in the audit. This connects classical model-selection bias to the specific economics of LLM inference.
  • Point Feasibility is Insufficient: Simply adding an "independent gate" (a separate validation split) only reduced the failure rate to 21%. You cannot "validate" your way out of this without accounting for uncertainty.
  • Reliability vs. Availability: A policy can "cheat" on accuracy by abstaining from hard questions, but this might violate the "coverage" part of the contract. MARC treats risk and coverage as a joint constraint.
  • The Power of Replacement: MARC-P doesn't just withhold service; in 77% of cases, it replaces the risky winner with a safer alternative. This shows that the "right" policy is often already in your menu, just hidden by noise.

Key Results

  • Failure Reduction: On RouterBench, the baseline "Audit Winner" deployed 91.82% of the time but failed in 32.22% of those cases. MARC-P (.05) reduced the conditional failure rate to just 0.73% while still deploying 85.79% of the time.
  • Violation Severity: When the baseline failed, it wasn't by a hair; the average violation was 3.15 percentage points beyond the allowed threshold.
  • Learned Routers: In the semantic routing study, the "winner" failed 33.98% of the time. MARC-P reduced this to 3.74%, proving the framework works for learned models, not just simple heuristics.
  • Data Scaling: As the audit sample size grows (from 10% to 40% of the data), MARC-P automatically becomes more "confident," increasing deployment rates while further reducing failures.

Limitations and Future Work

  • Static Environments: The study uses cached benchmark data. It does not account for distribution shift (where the type of queries changes over time) or model updates.
  • Unpriced Deferral: The framework decides when to "defer," but the paper doesn't assign a specific economic cost to that deferral (e.g., the cost of falling back to a human or a default expensive model).
  • Bootstrap Asymptotics: While MARC-S provides a simultaneous validity proof, it relies on asymptotic assumptions that might be stressed by very small audit samples or highly "kinked" policy menus.

This summary is based on the paper "When the Cheapest Feasible Router Fails: Auditing Deployment Commitments in Cost-Aware LLM Routing" (arXiv:2611.20417v1).

Summary updated

Abstract

Cost-aware LLM routing often selects the cheapest policy meeting empirical risk and coverage constraints. Yet a router that passes an audit can violate its fixed service contract on new requests, even when candidate policies are constructed independently. We study this deployment-commitment decision with disjoint construction, audit, and test samples. Across 19 RouterBench task families, the cheapest audit-feasible router deploys in 91.82% of opportunities but violates the held-out contract in 32.22% of deployments. We introduce Menu-Aware Routing Commitment (MARC), which qualifies policies using audit evidence and a serving-cost tolerance to retain the apparent winner, deploy a supported alternative, or defer. Its practical policywise variant (MARC-P) reduces observed conditional failure to 0.73% at 85.79% deployment, with higher serving cost; fixed-margin and formal risk-control procedures provide competitive alternatives. Nested audits show how added evidence changes deployable policy sets, and learned semantic routing exhibits the same commitment failure. These results establish deployment commitment as a distinct operational decision connecting router evaluation, service reliability, and inference cost.
BibTeX
@misc{hu2026when,
  author = {Minxuan Hu and Qishi Zhan and Ziheng Chen and Zhengtao Yao and Zihan Dong and Jiayu Yi and Wenxi Sun},
  title = {{When the Cheapest Feasible Router Fails: Auditing Deployment Commitments in Cost-Aware LLM Routing}},
  year = {2026},
  eprint = {2611.20417},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20417},
}
Figure