Organizations: Cornell University · Marquette University · University of Texas at Austin · University of Southern California · Georgia Institute of Technology · Nanyang Technological University · Johns Hopkins University
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
Figure 1: MARC overview. Frozen policies are audited against a fixed risk–coverage contract; evidence and cost tolerance determine whether to retain, replace, or defer. Schematic estimates and intervals.
Procedure
Deploy
D&F
Fail ∣ D
Audit winner
91.82
29.63
32.22
Independent gate
63.00
12.38
21.08
Point margin .00
91.82
22.25
24.40
Fixed margin .05
87.72
6.06
7.25
Fixed margin .10
86.32
1.43
1.78
Fixed margin .15
82.74
0.29
0.38
Table 1: RouterBench full-grid results (dataset-equal percentages). D&F: deploy-and-fail; Fail ∣ D: dataset-averaged conditional failure, not necessarily D&F/Deploy. MARC suffixes denote buffers δ ; guarantee scopes differ. Binary-only exact tests appear in Appendix E .
Objective
Winner
Fixed .00
Δ
MARC-P .05
Mean cost
29.52
29.17
-0.35
0.77
Tail cost
29.74
15.33
-14.41
0.48
Table 2: Deploy-and-fail by optimization objective (percent). Δ is fixed .00 minus the audit winner, in percentage points.
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
Table 3: RouterBench commitment actions (percent of all decision opportunities; dataset-equal).
Figure 2: Mean-cost RouterBench operating points: (a) deployment versus deploy-and-fail; (b) selected serving cost versus deploy-and-fail. Costs are trace units per incoming query among deployed policies. Dashed lines connect frozen parameter sweeps, not interpolated policies; deferral costs are unmeasured.
Figure 3: Nested-audit comparison at 10%, 20%, and 40%: (a) deployment and (b) deploy-and-fail, with between-dataset intervals. MARC-P and the fixed-margin controls keep their settings unchanged. Paired audit-size effects appear in Appendix G .
Table 5: Full-grid RouterBench results (dataset-equal percent; α=.10 when applicable).
Figure 4: RouterBench operating rates across the six prespecified risk–coverage contracts.
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 .00
91.82
29.17
31.78
0.000448
Fixed .02
89.89
18.33
20.46
0.000431
Fixed .05
87.72
7.94
9.36
0.000592
Fixed .08
86.93
3.33
4.08
0.000808
Appendix
Table 6: RouterBench mean-cost optimization: full configuration grid (dataset-equal rates across six contracts and applicable score channels). Cost per incoming query, conditional on commitment.
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 .00
91.82
15.33
17.01
0.000833
Fixed .02
89.89
9.74
11.25
0.000763
Fixed .05
87.72
4.19
5.14
0.000978
Fixed .08
86.93
2.00
2.55
0.001238
Appendix
Table 7: RouterBench tail-cost optimization: full configuration grid (dataset-equal rates across six contracts and applicable score channels). Cost per incoming query, conditional on commitment.
Procedure
Deploy (%)
D&F (%)
Fail ∣ D (%)
Deployments
Failures
Audit winner
88.64
28.86
33.81
2,021
658
Fixed .05
85.09
7.94
10.16
1,940
181
MARC-P .05
83.07
0.79
1.04
1,894
18
MARC-S .02
68.82
0.18
0.50
1,569
4
MARC-S .05
64.69
0.00
0.00
1,475
0
LTT-Bonf.
75.26
0.09
0.13
1,716
2
Appendix
Table 8: Binary-score RouterBench comparison under the mean-cost objective (dataset-equal rates; pooled counts; nominal α=.10 ).
Figure 5: Distribution of held-out contract-violation severity among failed commitments.
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 .05
3.42
2.52
0.12
6.06
MARC-P .05
0.54
0.09
0.00
0.63
MARC-S .02
0.11
0.02
0.00
0.13
LTT-Holm
0.09
0.00
0.00
0.09
Appendix
Table 9: Mutually exclusive risk-only, coverage-only, and joint held-out contract violations, as a percentage of all RouterBench decision opportunities, dataset-equal. The components sum to deploy-and-fail before display rounding.
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
Appendix
Table 10: RouterBench strict (r⋆,c⋆)=(.30,.60) contract. Dataset-equal rates and observed counts use distinct denominators.
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
Appendix
Table 11: Full-grid per-dataset deployment and deploy-and-fail percentages (winner versus MARC-P), each dataset weighted equally in primary aggregates.
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 .05
85.79 [75.92, 94.08]
0.63 [0.26, 1.06]
0.01 [0.01, 0.02]
MARC-S .02
71.93 [62.89, 80.79]
0.13 [0.02, 0.26]
0.00 [0.00, 0.01]
MARC-S .05
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]
Appendix
Table 12: RouterBench dataset-bootstrap 95% intervals over 19 task families. Severity is the maximum contract violation, with zero assigned to nonviolations.
Figure 6: Frozen audit-size results for MARC-P and fixed margins. Fixed .15 also gains deployment as audit evidence grows.
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
Appendix
Table 14: Nested-audit deployment ( D ) and deploy-and-fail ( DF ) rates at 10/20/40% audit; fixed method settings.
Procedure
Δ Deploy (pp)
Δ D&F (pp)
Δ Severity (pp)
Δ common cost
Δ supported-set size
MARC-P .05
+3.03
-0.92
-0.030
-0.000193
+1.49
Fixed .05
-2.48
-7.58
-0.356
+0.000082
-0.57
Fixed .10
-0.15
-3.57
-0.147
+0.000129
-0.65
Fixed .15
+2.28
-1.21
-0.044
+0.000198
+0.15
Appendix
Table 15: Nested-audit paired A40–A10 changes (dataset-equal). Serving-cost differences use common deployments.
A40–A10
Mean
95% CI
+/−/0 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
Appendix
Table 16: MARC-P .05 paired A40–A10 changes over 19 RouterBench datasets. Descriptive dataset-cluster percentile intervals use 20,000 bootstrap resamples of the paired results.
Figure 7: Learned-router deployment and deploy-and-fail by dataset, using the frozen KNN menu.
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
Appendix
Table 17: Learned-router deployment and unconditional deploy-and-fail by dataset (percent; pooled within task).
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
Appendix
Table 18: Learned-router deployment ( D ) and deploy-and-fail (D&F) by dataset, averaged over 20 seeds and six fixed contracts (percent).
Task ( 120 opportunities each)
Winner
MARC-P .05
MARC-S .02
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
Appendix
Table 19: Learned-router deployment/failure counts by dataset, over 20 seeds and six fixed contracts (mean-cost objective). A 0/0 entry indicates no deployment.
Procedure
Mean objective
Tail objective
Audit winner
0.000438
0.000749
Fixed .05
0.000592
0.000978
Fixed .10
0.001014
0.001449
Fixed .15
0.001455
0.001910
MARC-P .05
0.001071
0.001511
MARC-S .02
0.001125
0.001516
Appendix
Table 20: RouterBench selected-policy cost by optimization objective (trace units per incoming query; dataset-equal, conditional on commitment).
Objective
Comparison (MARC-P .05 vs.)
Shared N
ΔJ
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]
Appendix
Table 21: Matched RouterBench serving-cost differences for MARC-P versus each comparator on their jointly deployed opportunities. Dataset-equal means and 95% dataset-bootstrap intervals; positive ΔJ indicates higher MARC-P cost. Comparator rows use distinct matched populations.
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]
Appendix
Table 22: Selected-policy serving cost by optimization objective, conditional on deployment. Dataset-equal means and descriptive 95% bootstrap intervals over 19 tasks.
Failure penalty
Defer penalty
Winner
MARC-P .05
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
Appendix
Table 23: Illustrative mean-cost decision penalties over the fixed 4×4 failure/deferral grid. The scenario objective is E[DJtrace+λF1{D∩F}+λD(1−D)] ; penalty values are hypothetical.
Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.
Inference costs for large language model (LLM) applications are rapidly growing, driven by surging demand and rising infrastructure cost. Users expect high-quality responses, and in commercial settings this is formally codified in Service Level Agreements (SLAs), creating a fundamental tension between cost and quality. Recent progress on cost-aware LLM request routing has shown potential to resolve this tension, but existing approaches rely on complete feedback signals, offline training, extensive per-workload tuning, and most lack SLA guarantees or inference-time adaptivity. We introduce SLARouter, an online routing algorithm that learns a cost-optimal policy from the sparse, one-sided user feedback available in production systems. SLARouter provides theoretical guarantees for both cost optimality and strict SLA compliance. Experiments across a wide range of LLM benchmarks show that SLARouter satisfies SLA constraints without the need for per-benchmark tuning, reducing operating cost by up to 2.2x over existing baselines.
Herbert Woisetschläger, Arastun Mammadli, Ryan Zhang +1
Technical University of Munich Germany · University of Exeter United Kingdom · Horace Greeley High School United States
No single large language model (LLM) is optimal across all queries and budget constraints, making model routing essential for cost-effective deployment. Existing routers adopt diverse formulations and implementations, making fair comparison and extension difficult. We present a unified formulation of LLM routing as a sequential decision process characterized by five components: context encoders, model encoders, scoring functions, decision rules, and learning signals, covering single-turn, multi-turn, and personalized routing. Based on this formulation, we develop an automated pipeline for constructing routing supervision and evaluating routers jointly on response quality and inference cost. The resulting benchmark, xRouteBench, spans generic LLM, memory-augmented, vision, time-series, and personalized routing tasks. We further introduce LLMRouter, an open-source modular infrastructure with more than 16 representative routers. Our empirical study shows that learned routers outperform the strongest fixed-model baseline by 14.6% relatively, lightweight routers become more competitive under tight cost constraints, and user-conditioned routing consistently improves personalization.
Tao Feng, Fangxu Yu, Haozhen Zhang +9
University of Illinois Urbana-Champaign · University of Maryland, College Park · 3Nanyang Technological University +2
Dynamic LLM routers promise to cut inference costs by sending each query to the cheapest model that can answer it correctly. We analyze six commercial routers across 14 settings on a diverse benchmark spanning eight task categories, finding that none of them outperforms a router that randomly selects between two well-chosen models at matched cost. Some underperform by more than 10 percentage points. We trace this gap to four patterns prevalent across routers: difficulty blindness, length reversal, semantic matching, and roster suboptimality. We show that the first three are what the standard objective rewards: cost-accuracy Pareto efficiency on realized costs favors escalating moderately hard queries over the hardest ones, shorter queries over longer ones, and routing by a query's source over its difficulty. We also argue that the two assumptions that would justify large rosters, model granularity and model specialization, do not hold empirically. We propose an alternative evaluation methodology that does not reward these patterns, and as a proof of concept, we design a simple two-model router that avoids all four. Nevertheless, its gain over random routing is limited, because a well-chosen roster leaves little to route.