Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

Hanzhang Qin; Sophie H. Yu; Yuewei Zhang; Zhi-Hai Zhang

cs.LGNov 4, 2026

Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

Authors: Hanzhang Qin, Sophie H. Yu, Yuewei Zhang, Zhi-Hai Zhang

Organizations: Department of Industrial Systems Engineering and Management, National University of Singapore · The Wharton School of Business, University of Pennsylvania, Philadelphia PA, USA · Department of Industrial Engineering, Tsinghua University, Beijing, China

Abstract

Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with $2^K$ intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing $K$ reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.

Figures & tables

Panel of Figure 1 — Figure 1: Decision flow of the task stream under the budget $B$ .

Figure 2: Performance on MATH500 and GPQA streams.

Figure 3:

K

-sweep in Experiment 1.

Figure 4: Comparison on RouterBench .

Budget (USD)	K-Bit	Continuous Mean	Mean-Adjusted
5.00	15,989.4 (770.9)	14,774.2 (768.9)	15,502.3 (416.7)
8.86	18,397.6 (462.3)	16,923.7 (1,589.2)	17,419.5 (1,048.8)
10.00	18,673.3 (376.0)	17,248.3 (1,359.2)	17,446.2 (1,199.9)
13.34	18,931.1 (515.2)	17,851.0 (1,330.5)	17,762.9 (1,310.1)
20.00	18,996.2 (532.9)	18,771.0 (883.9)	18,668.4 (992.8)
40.02	19,888.3 (315.2)	20,072.6 (151.7)	20,054.0 (188.7)

Table 2: Cost-head comparison on RouterBench .

Figure 5: Commercial-router comparison on the common 844-problem LiveCodeBench stream.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	MATH500	GPQA
Seeds, warm/test split	$42$ – $46$ , $20\%/80\%$	$42$ – $46$ , $20\%/80\%$
Warm-start, retry upper bound	Greedy infinite-budget replay, $H=4$	Greedy infinite-budget replay, $H=4$
Embedding and grader	BGE-small-en-v1.5, GPT-OSS-120B	BGE-small-en-v1.5, GPT-OSS-120B
Arms	Qwen3-8B, Phi-4, Gemini-Flash-Lite, DeepSeek-V3.2, GPT-5-mini
Budgets (USD)	$0.025,0.05,0.075,0.125,0.30,0.45,0.60$	MATH grid plus $0.80,1.00$
$K$ , mesh edges, $d_{0}$	$2$ , warm-start quantiles, $8$	$2$ , warm-start quantiles, $8$

Appendix

Table 3: Experiment 1 implementation settings.

Model	Input price	Output price
qwen/qwen3-8b	$5.0\times 10^{-8}$	$4.0\times 10^{-7}$
microsoft/phi-4	$6.5\times 10^{-8}$	$1.4\times 10^{-7}$
google/gemini-2.5-flash-lite	$1.0\times 10^{-7}$	$4.0\times 10^{-7}$
deepseek/deepseek-v3.2	$2.6\times 10^{-7}$	$3.8\times 10^{-7}$
openai/gpt-5-mini	$2.5\times 10^{-7}$	$2.0\times 10^{-6}$

Appendix

Table 4: Model identifiers and configured token prices (USD/token).

Budget	ADP-HT	BA	PA	ParetoBandit	Greedy
$0.500$	$2{,}745.2$	$2{,}083.4$	$2{,}192.2$	$1{,}714.7$	$330.8$
$1.000$	$5{,}616.6$	$4{,}120.2$	$4{,}720.7$	$2{,}564.3$	$1{,}137.2$
$1.500$	$9{,}827.2$	$6{,}601.7$	$6{,}982.4$	$3{,}389.5$	$1{,}283.0$
$2.000$	$11{,}142.8$	$8{,}234.4$	$8{,}664.6$	$4{,}242.6$	$1{,}361.9$
$2.500$	$12{,}157.7$	$9{,}309.8$	$9{,}891.7$	$5{,}992.2$	$1{,}545.0$
$3.500$	$13{,}731.9$	$13{,}375.3$	$13{,}586.9$	$9{,}041.4$	$1{,}857.7$

Appendix

Table 5: RouterBench cumulative scores, with five-seed means and budgets in USD.

Nominal $B$	ADP-HT solved	ADP-HT spend	Errors	Auto-CS solved	Auto-CS spend	Auto-default (spend)
$0.202$	244	$0.2024$	0	86	$0.2020$	8 ( $0.5013$ )
$0.404$	436	$0.4041$	0	166	$0.4116$	8 ( $0.5013$ )
$0.8081$	682	$0.8084$	0	372	$0.8092$	15 ( $0.8190$ )
$5.710$	704	$5.7103$	1	732	$1.6161$	154 ( $5.7851$ )
$11.430$	628	$7.4154$	137	732	$1.6161$	298 ( $11.4701$ )
$17.140$	710	$15.5118$	36	732	$1.6161$	420 ( $17.3688$ )

Appendix

Table 6: Commercial comparison on the common 844-problem LiveCodeBench order.

Dataset	Budget	Greedy	B-aware	P-aware	Pareto	ADP-HT	Gap
MATH500	0.025	31.0 $\pm$ 14.8	96.6 $\pm$ 8.0	100.8 $\pm$ 16.8	79.6 $\pm$ 13.0	216.2 $\pm$ 83.8	115.4
	0.050	53.0 $\pm$ 18.8	197.0 $\pm$ 22.0	191.0 $\pm$ 21.6	151.0 $\pm$ 23.3	261.4 $\pm$ 67.7	64.4
	0.075	69.4 $\pm$ 19.8	263.4 $\pm$ 18.8	257.8 $\pm$ 23.1	252.2 $\pm$ 33.6	300.4 $\pm$ 29.1	37.0
	0.125	103.0 $\pm$ 30.9	313.8 $\pm$ 7.7	329.2 $\pm$ 8.0	329.6 $\pm$ 30.9	339.0 $\pm$ 22.4	9.4
	0.300	249.8 $\pm$ 67.5	332.4 $\pm$ 13.5	369.4 $\pm$ 5.8	370.8 $\pm$ 8.8	371.4 $\pm$ 17.5	0.6
	0.450	353.8 $\pm$ 76.6	344.6 $\pm$ 23.0	381.2 $\pm$ 3.4	380.6 $\pm$ 7.0	386.2 $\pm$ 5.3	5.0

Appendix

Table 7: Experiment 1 solved counts (mean

\pm

sample standard deviation over five seeds). Budgets are in USD.

Dataset	Baseline	Mean diff.	$95\%$ CI	$p$ -value (one-sided)
GPQA	Budget-aware	$40.3$	[27.4, 54.2]	$<10^{-4}$
GPQA	Position-aware	$37.4$	[19.6, 54.2]	$<10^{-4}$
GPQA	ParetoBandit	$27.9$	[11.3, 46.3]	$<10^{-4}$
MATH500	Budget-aware	$51.1$	[31.5, 80.4]	$<10^{-4}$
MATH500	Position-aware	$35.4$	[7.1, 71.3]	$0.001$
MATH500	ParetoBandit	$44.8$	[8.1, 88.2]	$0.002$

Appendix

Table 8: Experiment 1 hierarchical-bootstrap gaps over each dataset’s budget grid.

Panel A, mean budget utilization on MATH500 (%)
Policy	ADP-HT	BA	PA	ParetoBandit
Realized spend / nominal budget	93.4	75.7	77.2	81.5
Panel B, maximum-budget task profiles for ADP-HT
Dataset ( $B$ )	Profiles	Unsolved (%)	Unsolved spend (%)	Mean cost, solved / unsolved
MATH500 ( $0.60$ )	2,000	3.25	20.2	$0.926/6.989$
GPQA ( $1.00$ )	1,784	24.72	53.9	$1.331/4.732$

Appendix

Table 9: Experiment 1 operational-path summaries from the five-seed main-frontier runs.

Dataset	Budget	$K=1$	$K=2$	$K=3$	$K=4$	$K=5$
MATH500	0.05	273.8 $\pm$ 49.3	270.2 $\pm$ 67.8	265.4 $\pm$ 75.3	266.4 $\pm$ 75.7	245.8 $\pm$ 83.8
MATH500	0.3	370.4 $\pm$ 17.9	371.0 $\pm$ 16.2	367.0 $\pm$ 19.4	334.4 $\pm$ 88.3	335.0 $\pm$ 91.0
GPQA	0.05	124.6 $\pm$ 11.7	138.6 $\pm$ 13.2	135.0 $\pm$ 6.7	131.8 $\pm$ 10.5	129.4 $\pm$ 9.8
GPQA	0.3	232.8 $\pm$ 15.2	243.2 $\pm$ 3.9	241.8 $\pm$ 9.8	239.8 $\pm$ 7.3	240.0 $\pm$ 7.2

Appendix

Table 10: Resolution sweep with five-seed solved counts (mean

\pm

sample standard deviation) and pooled two-level bootstrap comparisons. Budgets are in USD.

Dataset	$K$	cells	Coverage	All-call gap	Cond. severity	Target-core exceedance
				( $\times 10^{-5}$ )	( $\times 10^{-4}$ )	rate
GPQA	1	10	0.960	2.40	6.08	0.0126
GPQA	2	10	0.876	4.11	3.31	0.0137
GPQA	3	10	0.807	5.56	2.88	0.0124
GPQA	4	10	0.751	5.68	2.28	0.0116
GPQA	5	10	0.715	6.53	2.29	0.0112

Appendix

Table 11: Executed-call cost-bound audit across

K

Panel A. Cumulative score, mean (sample standard deviation)
Budget (USD)	K-Bit	Continuous Mean	Mean-Adjusted
5.00	15,989.4 (770.9)	14,774.2 (768.9)	15,502.3 (416.7)
8.86	18,397.6 (462.3)	16,923.7 (1,589.2)	17,419.5 (1,048.8)
10.00	18,673.3 (376.0)	17,248.3 (1,359.2)	17,446.2 (1,199.9)
13.34	18,931.1 (515.2)	17,851.0 (1,330.5)	17,762.9 (1,310.1)
20.00	18,996.2 (532.9)	18,771.0 (883.9)	18,668.4 (992.8)

Appendix

Table 12: K-Bit, Continuous Mean, and Mean-Adjusted on RouterBench (five seeds).

Model	$p_{a,g}$	$p_{a,b}$	$p_{a}(E)$	$p_{a}(D)$	Fixed length	Tail length
$L$	0.80	0.20	0.650	0.350	2	2
$M$	0.90	0.40	0.775	0.525	3	2 (0.8), 7 (0.2)
$S$	0.95	0.55	0.850	0.650	4	2 (0.8), 12 (0.2)

Appendix

Table 13: Success probabilities and output lengths in the synthetic environment.

$B$	Cost / difficulty	$V^{*}$	ADP-HT [95% CI]	ADP/ $V^{*}$	Agreement
2,000	Fixed / iid	336.30	309.80 [306.47, 313.73]	92.12%	31.32%
2,000	Fixed / persistent	336.28	315.28 [312.97, 317.45]	93.76%	33.78%
2,000	Tail / iid	336.32	312.52 [308.10, 317.42]	92.92%	34.07%
2,000	Tail / persistent	336.31	315.48 [311.05, 319.92]	93.81%	33.70%
5,000	Fixed / iid	763.27	741.98 [734.52, 749.47]	97.21%	51.93%
5,000	Fixed / persistent	750.76	736.97 [731.97, 741.93]	98.16%	64.14%

Appendix

Table 14: Solved tasks and agreement with DP.

	$B=2{,}000$		$B=5{,}000$
Measure	DP	ADP-HT	DP	ADP-HT
Tasks served	573.15	436.03	999.85	999.83
First-call success among served tasks (%)	59.23	71.51	67.53	71.41
First-call successes	339.50	309.80	675.20	714.02
Retry calls	0.00	0.00	122.40	41.87
Retry successes	0.00	0.00	95.60	27.97

Appendix

Table 15: Behavior in the fixed-length independent environment.

Figure 6: Mean Bellman loss per stream under ADP-HT by decision type.

Figure 7: Exact policy values in panel (a) and effective cost prices in panel (b). Shading marks backlogs where

P

is optimal first. Each backlog is a separate initial state with the same budget and model distributions.

LLM Routing

Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.

See all 364 papers

WISERouter: LLM Routing with Workload Budget Constraint
Jul 26, 2026Yifei Li, Zihui Gao, Laks V. S. LakshmananLLM Routing Contextual Bandits
The University of British Columbia
ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving
Mar 31, 2026Annette Taberner-MillerAdaptive Model Routing LLM Routing
Independent Researcher.
Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets
Sep 1, 2026Cheung Hao Lee, Patrick WongCost-Aware Inference Non-Stationary Bandits

Jul 26, 2026J/K move · Enter open · S save

WISERouter: LLM Routing with Workload Budget Constraint

Yifei Li, Zihui Gao, Laks V. S. Lakshmanan

The University of British Columbia

LLM Routing Contextual Bandits

Open paper AskPDF arXiv

Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of

O(\sqrt{T})

over a time horizon

T

. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.

Abstract

LLM Routing

Explore similar work

WISERouter: LLM Routing with Workload Budget Constraint

ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving

Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets