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

Annette Taberner-Miller

cs.LGMar 31, 2026

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

Authors: Annette Taberner-Miller

Organizations: Independent Researcher.

Abstract

Multi-model LLM serving operates in a non-stationary, noisy environment: providers revise pricing, model quality can shift or regress without notice, and new models arrive regularly. More than a dozen recent methods have proposed learned routers to navigate the resulting quality--cost tradeoff across portfolios spanning a $\sim$ 530 $\times$ cost range. Despite this activity, two gaps in the current solution space limit routing effectiveness under these conditions: no existing router enforces a dollar-denominated cost ceiling in closed loop over an open-ended request stream, and none provides principled online adaptation to post-deployment shifts in pricing or model quality. We present ParetoBandit, an open-source adaptive router built on cost-aware contextual bandits that addresses both gaps. Its core contributions are: (1) an online primal--dual budget pacer that enforces a per-request cost ceiling without a known horizon, and (2) geometric forgetting on sufficient statistics that gives the bandit bounded memory for tracking quality and cost shifts. A hot-swap model registry further supports runtime model changes with budget-controlled exploration. On 1,824 benchmark prompts with a three-model portfolio, the router maintains budget compliance within 0.4%, adapts to price and quality shifts with up to +0.071 quality lift, and integrates a cold-started model within $\sim$ 142 steps.

Figures & tables

Model	Tier	Cost ($/req)
Llama-3.1-8B	Budget	$\$ 2.9{\times}10^{-5}$
Mistral-Large	Mid-cost	$\$ 5.3{\times}10^{-4}$
Gemini-2.5-Pro	Frontier	$\$ 1.5{\times}10^{-2}$
Budget	Target $B$	Regime
Tight	$\$ 3.0{\times}10^{-4}$	Llama-dominant
Moderate	$\$ 6.6{\times}10^{-4}$	Llama–Mistral mix

Table 1: Model portfolio and budget targets. The

530{\times}

cost spread stresses the router’s quality–cost tradeoff. Three budgets span the full operating range.

Figure 1: Quality–cost Pareto frontier under stationary conditions ( $K{=}3$ , 20 seeds). (a) ParetoBandit with BudgetPacer (blue curve) traces a continuous quality–cost frontier by accepting a dollar budget ceiling. Fixed single-model baselines shown as stars. (b) Budget compliance: realized cost vs. ceiling. Green band marks $\pm 5\%$ . (c) Model allocation shifts from Llama-dominant at tight budgets to Gemini-heavy at loose budgets.

Budget	Condition	Phase 1	Phase 2	Phase 3
Tight ( $\$ 3.0{\times}10^{-4}$ )	Naive Bandit	$\mathbf{1.07\times}$	$0.89\times$	$1.09\times$
	Recalibrated	$\mathbf{1.07\times}$	$\mathbf{0.99\times}$	$1.44\times$
	Forgetting Bandit	$2.62\times$	$0.88\times$	$5.50\times$
	ParetoBandit	$\mathbf{1.01\times}$	$0.95\times$	$\mathbf{1.04\times}$
Moderate ( $\$ 6.6{\times}10^{-4}$ )	Naive Bandit	$0.57\times$	$0.40\times$	$0.61\times$
	Recalibrated	$0.57\times$	$0.44\times$	$2.14\times$

Table 2: Budget compliance under cost drift (20 seeds). Each cell shows realised cost as a multiple of the ceiling (

1.00{\times}

= at ceiling); 95% bootstrap CIs are reported inline for key claims in the text. Bold : within 5% of ceiling.

Figure 2: Adaptation dynamics under cost drift ( $K{=}3$ , 20 seeds, 95% bootstrap CI). Normal pricing $\to$ Gemini price drop at prompt $608$ $\to$ price restored at prompt $2{\times}608$ . (a) Gemini-Pro selection fraction: all budget tiers surge toward Gemini during the price drop, then revert when pricing is restored. (b) Windowed mean reward: all conditions improve during Phase 2 as Gemini becomes budget-accessible. (c) Windowed average cost per request (dotted = budget ceilings): ParetoBandit tracks the ceiling in all three phases; the Forgetting Bandit overshoots from Phase 1 onward.

Figure 3: Silent quality degradation dynamics (20 seeds, 95% bootstrap CI). Mistral-Large degrades at prompt $608$ and recovers at $2{\times}608$ ; cost is unchanged. (a) Gemini-Pro selection fraction rises modestly under budget constraints and sharply ( ${\sim}17$ pp) without one. (b) Windowed reward: loose and unconstrained conditions recover fully in Phase 3; tighter budgets are still converging at the horizon limit (Appendix G ). (c) Cost per request (dotted lines = ceilings): ParetoBandit holds compliance throughout, confirming that the degradation is invisible to the cost signal.

Figure 4: Model onboarding ( $K{=}3\to K{=}4$ ; 20 seeds, 95% bootstrap CI). Flash windowed selection fraction across four budget levels after cold-start addition. (a) Good & cheap: Flash is adopted at all budgets. (b) Good & expensive: the BudgetPacer suppresses Flash under tight budgets. (c) Bad & cheap: the bandit correctly rejects Flash in every seed.

Figure 5: Budget–quality trade-off during model onboarding (Good & Cheap; 20 seeds, 95% bootstrap CI). (a) Running cost per request (dotted = targets). Tight and moderate track their ceilings through the $K{=}3\to K{=}4$ transition; loose settles below target as its constraint is only weakly binding. (b) Cumulative reward. Tight dips briefly at the Phase 2 boundary (20 forced-exploration pulls) before recovering; moderate rises as Flash fills a quality niche previously inaccessible at that cost tier.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Variant	Method	$\boldsymbol{\alpha}$	$\boldsymbol{n_{\text{eff}}}$	$\boldsymbol{\gamma}$	BP AUC	P2 Reward
ParetoBandit	AUC-only	$0.01$	$500$	$1.0$	$0.928$	—
ParetoBandit	Knee-point	$0.01$	$1164$	$0.997$	$0.928$	$0.7312$
Tabula Rasa	AUC-only	$0.10$	—	$1.0$	$0.925$	—
Tabula Rasa	Knee-point	$0.05$	—	$0.997$	$0.923$	$0.7287$

Appendix

Table 3:

T_{\text{adapt}}

-constrained Pareto knee-point selection. The knee-point method selects moderate forgetting (

\gamma{=}0.997

0.997

) for both variants, while AUC-only optimisation favours near-stationary

\gamma

. Warmup priors yield higher AUC, higher Phase-2 reward, and lower variance than the cold-start baseline. Grid:

6

\alpha

\times

7

\gamma

values; val split, 20 seeds.

$\boldsymbol{T_{\text{adapt}}}$	$\boldsymbol{\alpha}$	$\boldsymbol{\gamma}$	$\boldsymbol{n_{\text{eff}}}$	BP AUC $\uparrow$	P2 Reward $\uparrow$
$250$	$0.01$	$0.996$	$431$	$0.9255$	$0.7934$
$500$	$0.01$	$0.997$	$1164$	$0.9277$	$0.7933$
$1000$	$0.01$	$0.994$	$68298$	$0.9267$	$0.7945$

Appendix

Table 4:

T_{\text{adapt}}

sensitivity analysis. Pareto knee-point selection repeated for

T_{\text{adapt}}\in\{250,500,1000\}

, re-deriving

n_{\text{eff}}

from

\gamma

at each value. Grid:

\alpha\in\{0.01,\ldots,1.0\}

(

6

values)

\times

\gamma\in\{0.994,\ldots,1.0\}

(

7

values), val split, 20 seeds.

Figure 6: Cost heuristic validation: realised cost distributions. Panel (a) shows per-request realised cost distributions for the $K{=}3$ portfolio on the shared validation subset, and panel (b) shows the same diagnostic for the $K{=}4$ portfolio. In both cases the violin plots are ordered by the static log-normalized heuristic $\tilde{c}_{a}$ , illustrating that the major cost tiers are cleanly separated, with only the Mistral-Large and Gemini-Flash distributions showing substantial overlap.

Figure 7: Cost heuristic validation: ranking preservation. Panel (a) shows pairwise ranking preservation for the $K{=}3$ portfolio on the shared validation subset, and panel (b) shows the same diagnostic for the $K{=}4$ portfolio. The heuristic preserves the full per-request cost ordering on 100.0% of shared-subset $K{=}3$ prompts and ${\sim}$ 79.7% of shared-subset $K{=}4$ prompts; the Mistral-Large vs. Gemini-Flash comparison is the only source of inversions.

Budget	Condition	Regret (95% CI)	Std	R@200 (95% CI)	Rwd	Cat.	$p_{\text{sign}}^{*}$	$p_{\text{Fisher}}^{*}$
None	Warmup	$\mathbf{55.0}$ [54.3, 55.7]	$1.6$	$\mathbf{6.2}$ [5.8, 6.6]	$\mathbf{0.933}$	0/20	—	—
	Tabula Rasa	$87.0$ [77.1, 99.0]	$24.8$	$16.2$ [11.9, 20.8]	$0.916$	2/20	${<}10^{-5}$	$0.974$
	Random	$146.5$ [144.4, 148.8]	$5.0$	$16.0$ [15.1, 17.0]	$0.883$	—	—	—
Tight	Warmup	$\mathbf{161.2}$ [159.1, 163.1]	$4.6$	$\mathbf{19.5}$ [18.0, 21.0]	$\mathbf{0.875}$	0/20	—	—
	Tabula Rasa	$213.3$ [195.8, 232.1]	$41.8$	$29.2$ [26.4, 31.9]	$0.846$	0/20	$0.004$	$1.000$
Moderate	Warmup	$\mathbf{133.9}$ [129.2, 138.8]	$11.0$	$\mathbf{14.7}$ [12.9, 16.6]	$\mathbf{0.890}$	0/20	—	—

Appendix

Table 5: Warmup-prior ablation results across budget regimes (20 seeds, held-out test split,

n{=}1824

). Warmup priors are compared against Tabula Rasa and a random baseline (unconstrained only). Regret is cumulative over all 1824 test steps; R@200 is cumulative regret at test step 200. CIs are 95% percentile-bootstrap (10,000 resamples). ∗ Holm–Bonferroni corrected. Cat. = catastrophic failures (regret

>2{\times}

pooled median of all conditions in each budget regime).

Figure 8: Per-seed cumulative regret distributions for warmup priors (blue) vs. Tabula Rasa (orange) across four budget regimes ( $K{=}3$ , 20 seeds, held-out test split). Both conditions share $\gamma{=}0.997$ but differ in prior strength and exploration rate (deployment-level comparison). Gray star: Random baseline median (unconstrained only). Warmup priors yield tight, unimodal distributions; Tabula Rasa exhibits heavier tails under budget constraints. Statistical tests in Table 5 .

Figure 9: Total cumulative regret for ParetoBandit across the prior-quality vs. prior-strength grid (20 seeds, unconstrained, test split). All conditions use the same ParetoBandit router; only the warmup prior varies. Tabula Rasa is the independently optimised no-prior baseline. Bold cells exceed the Tabula Rasa median; normal-weight cells fall below it.

Figure 10: Per-seed regret distributions across prior-quality levels at each $n_{\mathit{eff}}$ value (20 seeds, unconstrained). Tabula Rasa is the independently optimised no-prior baseline.

Judge	Gemini-Pro	Mistral-Large	Llama-8B
DeepSeek-R1	0.935	0.923	0.798
GPT-4.1-mini	0.964	0.952	0.857
Claude-3.7-Sonnet	0.928	0.915	0.779

Appendix

Table 6: Expected reward ordering under each judge (

n=2{,}000

prompts; Bonferroni-corrected bootstrap CIs, 9 comparisons,

B=10{,}000

Train $\downarrow$ / Eval $\rightarrow$	R1	GPT-4.1-mini	Claude-3.7
R1	0.966 (100%)	0.955 ( 97.5% )	0.923 ( 97.4% )
GPT-4.1-mini	0.926 (95.8%)	0.979 (100%)	0.915 (96.6%)
Claude-3.7-Sonnet	0.926 (95.8%)	0.953 (97.3%)	0.948 (100%)

Appendix

Table 7: Cross-judge routing evaluation. Each cell reports the mean reward achieved by following the row judge’s oracle, evaluated by the column judge’s scores. Parenthetical values show the fraction of the column judge’s own oracle reward captured (

B=10{,}000

bootstrap resamples).

Metric	GPT-4.1-mini	Claude-3.7-Sonnet
Spearman’s $\rho$	0.658	0.633
Kendall’s $\tau_{b}$	0.547	0.528
MAD	0.074	0.075
Mean bias (judge $-$ R1)	$+0.039$	$-0.012$
95% Bland–Altman LoA	[ $-0.23$ , $+0.37$ ]	[ $-0.36$ , $+0.24$ ]

Appendix

Table 8: Per-response agreement with DeepSeek-R1 (

6{,}000

scored pairs per judge). All measures are rank-based or distribution-independent to avoid attenuation from ceiling-compressed rewards.

			Best-model agr. vs. R1
R1 gap range	$n$	Kendall $W$	GPT-mini	Claude
$[0.00,0.05)$	603	0.17	57.5%	48.3%
$[0.05,0.10)$	367	0.29	37.6%	37.9%
$[0.10,0.20)$	294	0.43	44.9%	39.5%
$[0.20,0.30)$	184	0.57	53.3%	49.5%
$[0.30,1.00)$	552	0.71	56.3%	58.0%

Appendix

Table 9: Routing agreement conditioned on R1’s inter-model gap. Kendall’s

W

measures three-judge concordance on the full model ranking. Conditioning on R1’s gap bins when validating R1 can introduce selection bias; we verify in the reproducibility code that the same monotonic trend holds when conditioning on the consensus (panel-median) gap.

Figure 12: Cold-start bandit regret under three judges (1328 test prompts drawn from the 2000-prompt judge-robustness sample). (A) R1: 52% regret reduction. (B) GPT-4.1-mini: 54% reduction. (C) Claude-3.7-Sonnet: 61% reduction. Shaded bands show 95% bootstrap CIs over 20 seeds. Tabula Rasa bands are wider than the Random baseline’s due to higher per-seed variance from cold-start exploration. The paired difference (Random $-$ Tabula Rasa) is significant for all three judges (bootstrap 95% CI excludes zero). The summary table reports Tabula Rasa cumulative regret (mean $\pm$ 95% bootstrap CI) across all four budget regimes with the supplementary/R1 ratio.

	Route ( $\mu$ s)		Update ( $\mu$ s)		Throughput
Configuration	p50	p95	p50	p95	(req/s)
Production (full router with locks, pacing, forgetting)
ParetoBandit ( $d{=}26$ )	22.5	26.5	20.4	23.0	22199
ParetoBandit ( $d{=}385$ )	163.0	234.5	456.9	539.0	1582
Algorithmic isolation (identical route() , only update() differs)
Bare SM ( $d{=}26$ )	5.8	6.2	8.1	8.4	70459

Appendix

Table 10: Per-request routing latency (

\mu

s) and throughput (

K{=}3

arms, 4,500 measured cycles). Configuration groups are described in the text.

Figure 13: Route latency (left), update latency (centre), and throughput (right) for eight router configurations on a log scale. Bare SM and Cached Inv. share identical route() code, so the route panel confirms they are equivalent; the update panel exposes Sherman-Morrison’s actual contribution ( $O(d^{2})$ vs. $O(d^{3})$ ). ParetoBandit bars quantify the additional cost of production features.

Stage	p50	p95	% of total
Embed (MiniLM-L6-v2, CPU)	$8.8$ ms	$9.3$ ms	$98.0\%$
PCA + whitening	$0.11$ ms	$0.15$ ms	—
route()	$0.056$ ms	$0.072$ ms	$0.6\%$
Total E2E (CPU)	$\mathbf{9.0}$ ms	$\mathbf{9.4}$ ms	$100\%$

Appendix

Table 11: End-to-end latency breakdown for ParetoBandit’s production CPU pipeline. Reported values are p50 and p95 over 200 measured iterations after a 50-iteration warmup; percentages are computed relative to the p50 total.

Figure 14: End-to-end routing latency (p50, single query) for published routing systems vs. LLM inference time (shaded region).

LLM	Prompt	TTFT (ms)	Total (ms)	Routing / Total
Llama-3.1-8B	short	$820$	$7,001$	$0.13\%$
Llama-3.1-8B	medium	$607$	$9,958$	$0.09\%$
Llama-3.1-8B	long	$684$	$7,235$	$0.12\%$
Mistral-Large-2512	short	$1044$	$5,811$	$0.16\%$
Mistral-Large-2512	medium	$665$	$6,442$	$0.14\%$
Mistral-Large-2512	long	$636$	$8,445$	$0.11\%$

Appendix

Table 12: Routing overhead as a fraction of LLM inference latency (

K{=}4

portfolio, 20 streaming API calls via OpenRouter). TTFT = time to first token. Routing overhead is the

9.0

ms end-to-end CPU critical path (embedding + PCA + route() ).

Figure 15: Recovery limit under quality degradation (moderate budget, 20 seeds, 95% bootstrap CI). (a) P3/P1 reward ratio vs. degradation severity; dotted line = 97% full-recovery threshold. (b) Phase-3 recovery dynamics (50-prompt rolling window) at the extended horizon for four severity levels.

Adaptive Model Routing

Adaptive model routing selects models or specialized experts per input to balance prediction quality, computational cost, latency, and resource constraints.

See all 91 papers

Jul 26, 2026

WISERouter: LLM Routing with Workload Budget Constraint

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.

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

The University of British Columbia

LLM Routing Contextual Bandits

Ask PDF

May 29, 2026

OrcaRouter: A Production-Oriented LLM Router with Hybrid Offline-Online Learning

The rapid development of large language models, each with distinct capabilities and inference costs, raises a practical deployment question: given an incoming request, which model should handle it? We present OrcaRouter, a production-oriented LLM router that combines a LinUCB-based contextual bandit over lexical and sentence-embedding features with a hybrid offline-online learning protocol. Offline, OrcaRouter obtains full-information feedback by evaluating each candidate model on a curated set of routing prompts, yielding a reward matrix used to fit one ridge regressor per arm. At deployment time, it initializes from these parameters and can optionally continue learning from bandit feedback, updating only the selected model's arm after observing its reward. At the time of our RouterArena submission (May 20, 2026), OrcaRouter-Adaptive ranked second on the public RouterArena leaderboard with an arena score of 72.08, achieving 75.54% accuracy at a cost of USD 1.00 per 1,000 queries.

Zhenghua Bao, Fengya Tian, Chris Zhang +3

Continuum AI

Model Selection LLM Routing LLM Request Scheduling Offline-to-Online Contextual Bandits

Ask PDF

Oct 15, 2026

Chance-Constrained Personalized LLM Routing with Online Preference Learning

We study personalized LLM routing, where a router selects among heterogeneous models with different costs and capabilities. The router must minimize cumulative inference cost while ensuring reliable realized response quality, even though user preferences are unknown and must be learned from feedback during deployment. We formulate this problem as a constrained contextual bandit and develop an algorithm that learns preferences while balancing cost and quality. Under a logistic preference model and a strict-feasibility condition, we establish sublinear expected cost regret relative to an optimal stationary randomized contextual oracle and a high-probability guarantee on realized cumulative satisfaction. The framework extends beyond LLM routing to broader online model-selection problems with reliability requirements.

Ameya Anjarlekar, Rasoul Etesami, R Srikant

LLM Routing Cost-Aware Inference Contextual Bandits Personalized Language Models

Ask PDF

Abstract

Adaptive Model Routing

Explore similar work

WISERouter: LLM Routing with Workload Budget Constraint

OrcaRouter: A Production-Oriented LLM Router with Hybrid Offline-Online Learning

Chance-Constrained Personalized LLM Routing with Online Preference Learning