cs.LGNov 16, 2026

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

Authors: Minxuan Hu, Qishi Zhan, Ziheng Chen, Zhengtao Yao, Zihan Dong, Jiayu Yi, Wenxi Sun

Organizations: Cornell University · Marquette University · University of Texas at Austin · University of Southern California · 

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.

Figures & tables

Appendix figures & tables25 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Cost-Optimal LLM Routing with Limited User Feedback under User Satisfaction Guarantees

    Jun 12, 2026Herbert Woisetschläger, Arastun Mammadli, Ryan Zhang +1Cost-Aware InferenceLLM Routing

  2. LLMRouter: Unified Infrastructure for Developing, Evaluating, and Deploying LLM Routers

    Aug 7, 2026Tao Feng, Fangxu Yu, Haozhen Zhang +9LLM EvaluationLLM Routing

  3. Dynamic LLM Routers are Often Misguided

    Oct 2, 2026Sam Wang, Julia White, Sahibzada Allahyar +3LLM RoutingCost-Aware Inference