When the Cheapest Feasible Router Fails: Auditing Deployment Commitments in Cost-Aware LLM Routing
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
| Procedure | Deploy | D&F | Fail D |
| Audit winner | 91.82 | 29.63 | 32.22 |
| Independent gate | 63.00 | 12.38 | 21.08 |
| Point margin | 91.82 | 22.25 | 24.40 |
| Fixed margin | 87.72 | 6.06 | 7.25 |
| Fixed margin | 86.32 | 1.43 | 1.78 |
| Fixed margin | 82.74 | 0.29 | 0.38 |
| Objective | Winner | Fixed | MARC-P | |
| Mean cost | 29.52 | 29.17 | -0.35 | 0.77 |
| Tail cost | 29.74 | 15.33 | -14.41 | 0.48 |
| Procedure | Retain | Replace | Defer |
| Audit winner | 91.82 | 0.00 | 8.18 |
| LTT-Holm | 8.64 | 69.74 | 21.62 |
| MARC-P .05 | 8.68 | 77.11 | 14.21 |
| MARC-S .02 | 8.46 | 63.46 | 28.07 |
| Pareto | 17.81 | 66.60 | 15.59 |
| Full frozen grid ( ) | Illustrative strict contract ( ) | ||||||
| Procedure | Deploy | D&F | Fail D | Fail/dep. | Deploy | Fail D | Fail/dep. |
| Audit winner | 81.92 | 27.83 | 33.98 | 334/983 | 67.50 | 41.48 | 56/135 |
| Fixed | 76.83 | 9.42 | 12.26 | 113/922 | 62.50 | 20.00 | 25/125 |
| MARC-P | 69.00 | 2.58 | 3.74 | 31/828 | 45.50 | 8.79 | 8/91 |
| Pareto Testing | 58.25 | 0.50 | 0.86 | 6/699 | 25.50 | 0 obs. | 0/51 |
| LTT-Holm | 51.33 | 0.17 | 0.32 | 2/616 | 21.00 | 0 obs. | 0/42 |
Appendix figures & tables25 assets
Supplementary material from the paper’s appendix.
Appendix
| Procedure | Deploy | D&F | Fail D |
| Audit winner | 91.82 | 29.63 | 32.22 |
| Independent gate | 63.00 | 12.38 | 21.08 |
| Fixed .00 | 91.82 | 22.25 | 24.40 |
| Fixed .02 | 89.89 | 14.04 | 15.86 |
| Fixed .05 | 87.72 | 6.06 | 7.25 |
| Fixed .08 | 86.93 | 2.66 | 3.32 |
| Procedure | Deploy (%) | D&F (%) | Fail D (%) | Selected cost (trace units/query) |
| Audit winner | 91.82 | 29.52 | 32.14 | 0.000438 |
| Independent gate | 62.98 | 12.43 | 21.28 | 0.000328 |
| Fixed | 91.82 | 29.17 | 31.78 | 0.000448 |
| Fixed | 89.89 | 18.33 | 20.46 | 0.000431 |
| Fixed | 87.72 | 7.94 | 9.36 | 0.000592 |
| Fixed | 86.93 | 3.33 | 4.08 | 0.000808 |
| Procedure | Deploy (%) | D&F (%) | Fail D (%) | Selected cost (trace units/query) |
| Audit winner | 91.82 | 29.74 | 32.30 | 0.000749 |
| Independent gate | 63.03 | 12.32 | 20.91 | 0.000554 |
| Fixed | 91.82 | 15.33 | 17.01 | 0.000833 |
| Fixed | 89.89 | 9.74 | 11.25 | 0.000763 |
| Fixed | 87.72 | 4.19 | 5.14 | 0.000978 |
| Fixed | 86.93 | 2.00 | 2.55 | 0.001238 |
| Procedure | Deploy (%) | D&F (%) | Fail D (%) | Deployments | Failures |
| Audit winner | 88.64 | 28.86 | 33.81 | 2,021 | 658 |
| Fixed | 85.09 | 7.94 | 10.16 | 1,940 | 181 |
| MARC-P | 83.07 | 0.79 | 1.04 | 1,894 | 18 |
| MARC-S | 68.82 | 0.18 | 0.50 | 1,569 | 4 |
| MARC-S | 64.69 | 0.00 | 0.00 | 1,475 | 0 |
| LTT-Bonf. | 75.26 | 0.09 | 0.13 | 1,716 | 2 |
| Procedure | Risk only | Cov. only | Both | D&F |
| Audit winner | 10.83 | 16.64 | 2.15 | 29.63 |
| Independent gate | 2.85 | 9.22 | 0.31 | 12.38 |
| Fixed | 3.42 | 2.52 | 0.12 | 6.06 |
| MARC-P | 0.54 | 0.09 | 0.00 | 0.63 |
| MARC-S | 0.11 | 0.02 | 0.00 | 0.13 |
| LTT-Holm | 0.09 | 0.00 | 0.00 | 0.09 |
| Procedure | Deploy | D&F | Fail/dep. |
| Audit winner | 81.32 | 42.89 | 652/1236 |
| LTT-Holm | 50.79 | 0.00 | 0/772 |
| MARC-P .05 | 65.00 | 0.53 | 8/988 |
| MARC-S .02 | 39.47 | 0.00 | 0/600 |
| Pareto | 63.16 | 0.26 | 4/960 |
| Dataset | Win D | Win D&F | P D | P D&F |
| arc-challenge | 100.00 | 30.00 | 100.00 | 0.00 |
| chinese_zodiac | 85.83 | 42.50 | 65.83 | 0.00 |
| consensus_summary | 64.58 | 29.17 | 48.33 | 0.21 |
| grade-school-math | 33.33 | 4.17 | 33.33 | 0.00 |
| hellaswag | 100.00 | 20.00 | 100.00 | 0.00 |
| mbpp | 90.83 | 47.50 | 66.67 | 1.67 |
| Procedure | Deploy (%) | D&F (%) | Severity (pp) |
| Audit winner | 91.82 [83.46, 98.03] | 29.63 [24.34, 35.53] | 1.03 [0.70, 1.38] |
| MARC-P | 85.79 [75.92, 94.08] | 0.63 [0.26, 1.06] | 0.01 [0.01, 0.02] |
| MARC-S | 71.93 [62.89, 80.79] | 0.13 [0.02, 0.26] | 0.00 [0.00, 0.01] |
| MARC-S | 68.03 [58.55, 77.28] | 0.00 [0.00, 0.00] | 0.00 [0.00, 0.00] |
| LTT-Holm | 78.38 [67.85, 88.20] | 0.09 [0.00, 0.22] | 0.00 [0.00, 0.00] |
| Pareto Testing | 84.41 [74.85, 92.76] | 0.49 [0.16, 0.92] | 0.01 [0.00, 0.02] |
| Method vs winner | Outcome | LODO min | LODO max |
| MARC-P .05 | D&F | -30.38 | -26.98 |
| MARC-P .05 | Deploy | -6.37 | -4.98 |
| Fixed .10 | D&F | -29.54 | -26.39 |
| Fixed .10 | Deploy | -5.81 | -4.51 |
| Pareto | D&F | -30.52 | -27.07 |
| Pareto | Deploy | -7.82 | -6.34 |
| Procedure | D10 | D20 | D40 | DF10 | DF20 | DF40 |
| MARC-P .05 | 83.55 | 85.83 | 86.58 | 1.34 | 0.77 | 0.42 |
| Fixed 0.00 | 92.76 | 92.11 | 91.07 | 23.60 | 20.09 | 17.60 |
| Fixed 0.02 | 91.47 | 90.00 | 88.77 | 16.96 | 12.59 | 9.86 |
| Fixed 0.05 | 89.50 | 87.94 | 87.02 | 10.73 | 6.15 | 3.16 |
| Fixed 0.08 | 88.00 | 87.19 | 86.80 | 6.61 | 3.11 | 1.17 |
| Fixed 0.10 | 86.62 | 86.21 | 86.47 | 4.01 | 1.51 | 0.44 |
| Procedure | Deploy (pp) | D&F (pp) | Severity (pp) | common cost | supported-set size |
| MARC-P | +3.03 | -0.92 | -0.030 | -0.000193 | +1.49 |
| Fixed | -2.48 | -7.58 | -0.356 | +0.000082 | -0.57 |
| Fixed | -0.15 | -3.57 | -0.147 | +0.000129 | -0.65 |
| Fixed | +2.28 | -1.21 | -0.044 | +0.000198 | +0.15 |
| A40–A10 | Mean | 95% CI | tasks |
| Deployment (pp) | +3.03 | [+1.01, +5.44] | 9/2/8 |
| Deploy-and-fail (pp) | -0.92 | [-1.67, -0.22] | 3/10/6 |
| Supported-set size | +1.49 | [+1.04, +1.95] | 17/2/0 |
| Dataset | Win D | Win DF | P D | P DF |
| aime | 100.00 | 34.17 | 86.67 | 11.67 |
| arenahard | 100.00 | 32.50 | 90.00 | 0.00 |
| gpqa | 100.00 | 30.00 | 97.50 | 3.33 |
| hle | 24.17 | 20.00 | 0.00 | 0.00 |
| livecodebench | 100.00 | 34.17 | 100.00 | 1.67 |
| livemathbench | 100.00 | 25.00 | 80.00 | 4.17 |
| Dataset | Winner D | Winner D&F | MARC-P D | MARC-P D&F | LTT D | Pareto D |
| aime | 100.0 | 34.2 | 86.7 | 11.7 | 18.3 | 48.3 |
| arenahard | 100.0 | 32.5 | 90.0 | 0.0 | 68.3 | 77.5 |
| gpqa | 100.0 | 30.0 | 97.5 | 3.3 | 70.0 | 73.3 |
| hle | 24.2 | 20.0 | 0.0 | 0.0 | 0.0 | 0.8 |
| livecodebench | 100.0 | 34.2 | 100.0 | 1.7 | 100.0 | 100.0 |
| livemathbench | 100.0 | 25.0 | 80.0 | 4.2 | 44.2 | 60.0 |
| Task ( opportunities each) | Winner | MARC-P | MARC-S | LTT-Holm | Pareto |
| aime | 120/41 | 104/14 | 38/2 | 22/0 | 58/3 |
| arenahard | 120/39 | 108/0 | 98/0 | 82/0 | 93/0 |
| gpqa | 120/36 | 117/4 | 87/1 | 84/0 | 88/1 |
| hle | 29/24 | 0/0 | 1/1 | 0/0 | 1/1 |
| livecodebench | 120/41 | 120/2 | 120/2 | 120/2 | 120/1 |
| livemathbench | 120/30 | 96/5 | 64/0 | 53/0 | 72/0 |
| Procedure | Mean objective | Tail objective |
| Audit winner | 0.000438 | 0.000749 |
| Fixed | 0.000592 | 0.000978 |
| Fixed | 0.001014 | 0.001449 |
| Fixed | 0.001455 | 0.001910 |
| MARC-P | 0.001071 | 0.001511 |
| MARC-S | 0.001125 | 0.001516 |
| Objective | Comparison (MARC-P vs.) | Shared | 95% cluster interval | |
| Mean | Winner | 3912 | +0.000844 | [+0.000408, +0.001444] |
| Mean | Fixed .10 | 3912 | +0.000070 | [-0.000019, +0.000159] |
| Mean | Pareto | 3841 | -0.000243 | [-0.000429, -0.000069] |
| Mean | LTT-Holm | 3574 | -0.000517 | [-0.000770, -0.000295] |
| Tail | Winner | 3912 | +0.001105 | [+0.000495, +0.002032] |
| Tail | Fixed .10 | 3912 | +0.000082 | [-0.000016, +0.000187] |
| Objective | Method | Cost | 95% dataset interval |
| Mean | Winner | 0.000438 | [0.000185, 0.000752] |
| Mean | MARC-P .05 | 0.001071 | [0.000563, 0.001750] |
| Mean | Pareto | 0.001297 | [0.000781, 0.001968] |
| Mean | LTT-Holm | 0.001391 | [0.000774, 0.002177] |
| Tail | Winner | 0.000749 | [0.000319, 0.001283] |
| Tail | MARC-P .05 | 0.001511 | [0.000749, 0.002620] |
| Failure penalty | Defer penalty | Winner | MARC-P | Pareto | LTT-Holm |
| 0.001 | 0.0001 | 0.000696 | 0.000892 | 0.001083 | 0.001094 |
| 0.001 | 0.01 | 0.001506 | 0.002299 | 0.002626 | 0.003235 |
| 0.1 | 0.0001 | 0.029918 | 0.001652 | 0.001604 | 0.001181 |
| 0.1 | 0.01 | 0.030728 | 0.003059 | 0.003147 | 0.003322 |
| Procedure | Deploy | D&F | |
| LTT-Holm | 0.10 | 78.38 | 0.09 |
| LTT-Bonf. | 0.10 | 78.38 | 0.09 |
| Pareto | 0.10 | 84.41 | 0.49 |
| LTT-Holm | 0.05 | 76.75 | 0.00 |
| LTT-Bonf. | 0.05 | 76.75 | 0.00 |
| Pareto | 0.05 | 82.83 | 0.37 |
| Menu size | Deploy | Fail D | D&F |
| 7 | 66.67 | 9.62 | 6.42 |
| 14 | 66.67 | 7.25 | 4.83 |
| 21 | 66.67 | 5.25 | 3.50 |
| 28 | 66.67 | 2.50 | 1.67 |
| 35 | 66.67 | 0.00 | 0.00 |
LLM Routing
Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.
See all 382 papers