Paper deep dive
WISERouter: LLM Routing with Workload Budget Constraint
Yifei Li, Zihui Gao, Laks V. S. Lakshmanan
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2607.23765v1
- Canonical: https://arxiv.org/abs/2607.23765v1
Trouble viewing inline? Open PDF directly →
Full Text
96,086 characters extracted from source content.
Expand or collapse full text
WISERouter: LLM Routing with Workload Budget Constraint Yifei Li Zihui Gao Laks V.S. Lakshmanan The University of British Columbia Corresponding author: yfli@cs.ubc.ca Abstract 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; (i) 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(T)O( 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 (i) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data. 1 Introduction While state-of-the-art large language models (LLMs) continue to advance their remarkable capabilities, their token-wise inference cost often makes them prohibitively expensive for high-throughput workloads. Leading AI services can charge $100 per user per month [1] under business subscription; at the API billing level, frontier models like GPT-5.5 cost up to 6.7× more per token than smaller models like GPT-5.4-mini [31], pushing organizations or businesses that process high-throughput workload queries – such as customer support ticket resolution or document summarization – to inference bills exceeding thousands of dollars per month. It has been found that smaller models can often serve as effective proxies, delivering comparable performance at a fraction of cost [9, 30]. Furthermore, various benchmark leaderboards [7, 39] and empirical studies reveal that different LLMs exhibit varying strengths across different query types [38, 25], making inference-time model selection attractive for both cost saving and quality improvement. Inference-time model selection has emerged as a practical approach to this challenge. The two dominant paradigms are LLM routing [9, 30], which assigns each query directly to the most suitable model, and cascading [6, 41], which queries models sequentially and may invoke multiple models per query until a quality threshold is met. Recent work has validated inference-time LLM selection across diverse benchmarks [15, 38, 26, 6], demonstrating consistent performance-cost trade-offs. Despite this promise, current inference-time model selection methods still share two limitations. First, they do not directly enforce a workload-level budget constraint. Majority of prior works either enforce no hard budget (e.g., [9, 30, 26]) or constrain cost only per-query (e.g., [6, 8, 29]). However, real-world deployments operate under workload-level resource constraints: API token quotas or monthly subscription fees apply across an entire set of queries, not individually. LLM selection algorithms that directly reason at the workload-level can prioritize complex or high utility queries for larger and expensive models while being conservative on easier queries, something that per-query constrained algorithms cannot do by construction. Second, most algorithms need expensive supervision signals. Existing inference-time LLM selection methods typically follow a train-deploy paradigm which requires dense supervision: outputs and costs must be collected for every query-model pair before training a routing policy [9, 30], which becomes prohibitively expensive as the number of model candidates or training queries increases. We focus on LLM routing because routing each query to exactly one model avoids the redundant inference costs of cascading, enabling tighter budget constraint. LLM Routing maps naturally to the multi-armed bandit setting (Section 3.1). These limitations lead to two central questions: (1) How can we perform LLM routing w.r.t. a workload-level budget constraint? (2) How can routing be learned when query-model interactions are sparse or are gradually being observed? Figure 1: Comparison of WISERouter with previous LLM selection methods. We introduce WISERouter (Workload-Informed Sequential Efficient Router, WR for short), a unified framework that addresses both limitations by formulating LLM routing as a Constrained Contextual Bandit (CCB) [3] problem, where each query embedding is the context, the selected LLM is the action, and the observed response quality is the reward. The goal is to maximize cumulative expected reward while satisfying a workload-level expected cost budget over the horizon. WISERouter addresses the first limitation of enforcing a workload-level budget via Adaptive Linear Programming (ALP) [40], which translates the remaining budget into a per-round constraint at each query step, enabling dynamic budget allocation across queries by resolving a lightweight linear program without retraining. To address the second limitation and learn from sparse supervision signal, we propose WR-Online, which jointly learns reward and cost statistics online via an ϵε-first exploration before the ALP-based exploitation, all under a single shared budget. We prove the end-to-end regret bound for WR-Online, covering both phases under a workload level budget constraint. Figure 1 illustrates how WISERouter differs from prior methods along these two dimensions. Concretely, WISERouter operates in two stages: query embedding discretization followed by ALP-based model selection, with WR-Offline for data-rich settings (e.g., responses from all candidate models collected per query) and WR-Online for data-scarce settings (e.g., responses from only a subset of candidate models per query). On datasets RouterBench [15] and SWE-Bench [20], WR-Offline consistently matches or outperforms the baselines. WR-Offline improves average quality by 14%14\% over the best baseline on SWE-Bench at the tightest budget. WR-Offline terminates with the lowest unspent budget across most budget levels without overspending, training over 5,900×5,900× faster than neural-network based baselines for each new budget setting. In the data-scarce setting, WR-Online matches offline methods while reducing the required training data by 90%90\% on RouterBench. Our contributions are: (i) To the best of our knowledge, we are the first to formulate workload-constrained LLM routing as a CCB problem and develop WR-Offline, which enforces a global budget via solving ALP and adapts to new budget constraints without retraining. (i) We propose WR-Online, an online variant that jointly learns reward and cost statistics from sparse interactions, and prove the first end-to-end regret bound for bandit algorithm applied on LLM routing covering both exploration and exploitation under a shared workload budget. (i) We empirically validate WISERouter on RouterBench and SWE-Bench, demonstrating superior performance at tight budgets, precise budget utilization, and significant reduction in training data with WR-Online. 2 Related Work Efficient LLM inference is a central challenge in large-scale AI deployment, with recent work spanning algorithmic improvements such as speculative decoding [23, 5], pruning [14, 22], quantization [18, 37], efficient KV caching [4], and others [21, 34, 12]. Orthogonally to these techniques which have access to model internal architectures, inference-time model selection reduces inference cost by routing queries to black-box models of varying capability and price [9, 30, 26], cascading through a fixed model sequence [6, 8], or ensembling multiple outputs [19, 16]. Below, we focus on the two directions most directly related to WISERouter; a full survey appears in Appendix B. Efficient LLM Selection with Cost Constraint. Prior work on cost-aware LLM selection has addressed budget constraints in different ways, but none jointly enforces a workload-level budget across both learning and deployment. MetaLLM [29] treats model selection as a contextual bandit, using UCB [2] to satisfy per-query cost constraint by tuning a cost scaling factor in reward function. FrugalGPT [6] and CascadeRouting [8] cascade queries through increasingly capable models until a quality threshold is met, enforcing an explicit per-query budget. Such per-query constraints can be myopic, and adapting these methods to different cost constraints typically requires retraining the routing policy. PILOT [32] combines a LinUCB router with an online knapsack solver for budget enforcement, but applies the budget only during deployment: specifically, the exploration phase with LinUCB is unconstrained, and the regret analysis covers router learning alone rather than the full stages. WR-Online, the online variant of WISERouter, is the first LLM routing method to enforce a single workload-level budget across both exploration and exploitation, and to provide an end-to-end regret bound covering the complete online routing process. Constrained Contextual Bandits. Badanidiyuru et al. [3] establishes the theoretical foundation for budget-constrained contextual bandits with an O~(T) O( T) regret bound, but the proposed algorithm is computationally intractable in practice. Wu et al. [40] proposes UCB-ALP for uniform-cost settings and ϵε-first ALP for heterogeneous costs setting, both assuming cost statistics are known a priori. Our work extends the ϵε-first ALP algorithm to the regime where both reward and cost must be estimated online from sparse interactions under a single budget shared across exploration and exploitation. 3 Preliminaries 3.1 LLM routing as Constrained Contextual Bandit We consider a routing setting with K black-box LLMs, indexed by =1,…,KK=\1,…,K\, and a stream of user queries Q. At each time step t, an input prompt qt∈q_t arrives and the router selects a single model At∈A_t to generate the response. After invoking the selected model, the router can observe: (i) a performance score Yt∈[0,1]Y_t∈[0,1] that quantifies response quality (e.g., human preference, ground-truth-based metric when available), and (i) a cost score St∈[0,1]S_t∈[0,1] that measures the resources used by the selected model, normalized by a known per-query maximum. In this work, StS_t is the monetary cost computed by token-based pricing of the selected LLM. The same formulation also applies to other cost notions, such as latency or energy consumption. We formulate LLM routing as a Constrained Contextual Bandit (CCB) problem. Each incoming query provides a context, represented by its query embedding (detailed in Section 4.1), and each LLM selection is an action. The router receives bandit feedback (Yt,St)(Y_t,S_t) only for the selected model at timestep t. Our goal for a routing policy Ψ is to maximize expected cumulative performance subject to a workload-level budget: maximizeUΨ(T,B)=[∑t=1TYt]subject to[∑t=1TSt]≤B.maximize \;U_ (T,B)=E [ _t=1^TY_t ] to [ _t=1^TS_t ]≤ B. We optimize expected reward subject to expected cost to account for stochasticity in model generation, following prior work on efficient LLM selection [6, 8]. 3.2 Adaptive Linear Programming Wu et al. [40] propose ALP for constrained contextual bandits over a finite horizon T: at each step it solves a linear program that converts the remaining budget b across the remaining τ rounds into a per-round average constraint b/τb/τ, adapting to cost consumption at runtime. It operates under two assumptions: (a) a finite context space =1,…,JJ=\1,…,J\ with known context distribution πjj=1J\ _j\_j=1^J ; and (b) known reward and cost statistics uj,ku_j,k and cj,kc_j,k, denoting the expected reward and cost for each context-action pair (j,k)(j,k). Let pj,k∈[0,1]p_j,k∈[0,1] denote the probability of selecting action k given context j. A null action k=0k=0 with uj,0=cj,0=0u_j,0=c_j,0=0 (skipping the current context) guarantees a valid action always exists. At each time step, ALP solves: (LPτ,b)maxpj,k (LP_τ,b) _p_j,k ∑j=1Jπj∑k=1Kpj,kuj,k _j=1^J _j _k=1^Kp_j,k\,u_j,k (1) s.t. ∑j=1Jπj∑k=1Kpj,kcj,k≤bτ, _j=1^J _j _k=1^Kp_j,k\,c_j,k\;≤\; bτ, (2) ∑k=1Kpj,k≤ 1,∀j∈, _k=1^Kp_j,k\;≤\;1, ∀\,j , (3) pj,k∈[0,1]. p_j,k∈[0,1]. (4) ALP was designed for finite contexts with known statistics. Neither assumption holds directly in LLM routing: query embeddings are continuous and high-dimensional, and reward and cost statistics are not known a priori and must be estimated from data. Section 4 addresses both limitations. 4 Our Method WISERouter (Figure 2) addresses the two limitations identified in Section 3.2 in two steps: (1) discretize the query embedding space into a finite context set compatible with ALP (Section 4.1); and (2) perform ALP-based model selection under two regimes - WR-Offline (Section 4.2), which estimates statistics from historical data, and WR-Online (Section 4.3), which learns them online under a shared workload budget. We close with a discussion of the assumptions of our formulation. Figure 2: Overview of WISERouter workflow. 4.1 Context Discretization For the CCB formulation to be meaningful, the context must encode query-level features that explain the variation in LLM performance across queries. Since different LLMs can perform unevenly across query semantics [38], we use a pretrained encoder g(⋅)g(·) to map each query q∈q to an embedding vector x=g(q)∈ℝdx=g(q) ^d. However, ALP assumes a finite context space with an explicit context distribution, so we discretize the embedding space via clustering. Specifically, given a historical query set =qii=1nQ=\q_i\_i=1^n, we compute embeddings xi=g(qi)x_i=g(q_i) and cluster xii=1n\x_i\_i=1^n into J groups with centroids x¯jj=1J\ x_j\_j=1^J. We define the discrete context of query qiq_i as its cluster assignment σ(g(qi))∈1,…,Jσ(g(q_i))∈\1,…,J\, and estimate the context distribution empirically by πj=ℙ(X=j)=|i∈[n]:σ(g(qi))=j|/n. _j=P(X=j)=|\i∈[n]:σ(g(q_i))=j\|/n. At test time, each incoming query qtq_t is embedded as xt=g(qt)x_t=g(q_t) and assigned to its nearest centroid, yielding a discrete context Xt∈1,…,JX_t∈\1,…,J\. We assume that for each LLM, queries in the same cluster share the same expected reward and expected cost. The granularity of this approximation is controlled by J. Ablations in Appendix H.7 show stable performance across cluster counts and algorithms, with small intra-cluster reward and cost variance (Appendix H.4). 4.2 WR-Offline with Known Statistics WR-Offline addresses the data-rich regime, where a historical dataset histD_hist of query-model interactions is available. Applying the discretization from Section 4.1 to histD_hist, we estimate u^j,k u_j,k and c^j,k c_j,k as the mean reward and cost for each context-action pair (j,k)(j,k). These statistics are computed once offline and fixed at deployment. At each routing step, the router solves LPτ,bLP_τ,b via a standard LP solver with negligible additional latency and samples an action from solution probability pj,⋅(b/τ)p_j,·(b/τ) across all models under context j at per-round budget b/τb/τ. Since the budget constraint is on expected cost, remaining budget b is updated by mean cost. The full procedure is given in Algorithm 1. Algorithm 1 WR-Offline 0: Horizon T, workload budget B, model set K, encoder g, clustering map σ:ℝd→1,…,Jσ:R^d\!→\!\1,…,J\, context distribution πjj=1J\ _j\_j=1^J, historical data histD_hist 1: Init: τ←Tτ← T, b←Bb← B; for each (j,k)(j,k), compute u^j,k u_j,k and c^j,k c_j,k from histD_hist 2: for t=1t=1 to T and b>0b>0 do 3: Observe query qtq_t; assign context j←σ(g(qt))j←σ(g(q_t)) 4: Solve LPτ,bLP_τ,b using (u^j,k,c^j,k)( u_j,k, c_j,k) and πjj=1J\ _j\_j=1^J; Obtain solution probabilities pj,k(b/τ)p_j,k(b/τ) at budget b/τb/τ for each (j,k)(j,k); Sample At∼pj,⋅(b/τ)A_t p_j,·(b/τ) and route qtq_t to model AtA_t 5: b←b−c^j,Atb← b- c_j,A_t; τ←τ−1τ←τ-1 6: end for 4.3 WR-Online with Exploration When model responses have not been pre-collected across all candidate models for the historical queries, either because they are expensive or are not available beforehand, supervised learning is infeasible. WR-Online instead learns mean reward and cost online all under the same shared budget B. Both statistics must be estimated post-hoc with the generated response from each model. WR-Online extends the ϵε-first ALP in Wu et al. [40] to jointly estimate uj,ku_j,k and cj,kc_j,k online. During the exploration phase of ϵ(T)ε(T) steps, it routes each query to the least-invoked model within its context, ensuring every (j,k)(j,k) pair is visited at least ⌊ϵ(T)/K⌋ ε(T)/K times, and updates running mean estimates u¯j,k u_j,k, c¯j,k c_j,k from observed feedback. For the remaining (1−ϵ)T(1-ε)T exploitation steps, the router solves LPτ,bLP_τ,b with the estimated statistics. Section 5 derives the sufficient condition on ϵ(T)ε(T) for an O(T)O( T) end-to-end regret bound. The full procedure is in Algorithm 2. Algorithm 2 WR-Online 0: Horizon T, budget B, exploration length ϵ(T)ε(T), model set K, encoder g, clustering map σ:ℝd→1,…,Jσ:R^d\!→\!\1,…,J\, context distribution πjj=1J\ _j\_j=1^J 1: Initialize Nj,k,u¯j,k,c¯j,k←0N_j,k, u_j,k, c_j,k← 0 for all j,kj,k; b←Bb← B, τ←Tτ← T, 2: for t=1,…,ε(T)t=1,…, (T) and b>0b>0 do 3: Observe a query qtq_t; set j←σ(g(qt))j←σ(g(q_t)) 4: At=argmink∈Nj,kA_t= _k N_j,k with random tie-break; observe (YAt,t,SAt,t)(Y_A_t,t,S_A_t,t) 5: b←b−SAt,tb← b-S_A_t,t; τ←τ−1τ←τ-1; Nj,k←Nj,k+1N_j,k\!←\!N_j,k+1, u¯j,k←u¯j,k+YAt,t−u¯j,kNj,k u_j,k\!←\! u_j,k+ Y_A_t,t- u_j,kN_j,k, c¯j,k←c¯j,k+SAt,t−c¯j,kNj,k c_j,k\!←\! c_j,k+ S_A_t,t- c_j,kN_j,k 6: end for 7: for t=ε(T)+1t= (T)+1 to T and b>0b>0 do 8: Observe a query qtq_t, set j←σ(g(qt))j←σ(g(q_t)) 9: Solve LPτ,bLP_τ,b with (u¯j,k,c¯j,k)( u_j,k, c_j,k) to obtain pj,⋅(b/τ)p_j,·(b/τ); 10: Sample At∼pj,⋅(b/τ)A_t p_j,·(b/τ) and route qtq_t to model AtA_t 11: b←b−c¯j,Atb← b- c_j,A_t; τ←τ−1τ←τ-1 12: end for Practical validity of assumptions. The CCB formulation (Section 3.1) rests on three assumptions that hold under standard deployment conditions. I.i.d. contexts: queries from a stable user population are well-approximated by the stationary distribution πj _j estimated via clustering. Finite horizon T: corresponds to a planning window (e.g., a monthly API quota) estimable from historical traffic. Feedback acquisition: token-count costs are available immediately after generation; quality scores are read from histD_hist in WR-Offline and collected during exploration without blocking routing decisions in WR-Online. Appendix A discusses practical mitigation for distributional shift and reward feedback. 5 Regret Analysis for WR-Online Regret measures the cumulative expected reward gap between a bandit policy and an oracle policy with full knowledge of all statistics [40, 2]. We analyze the regret of WR-Online by first establishing an oracle upper bound, then deriving a sufficient condition on the exploration length, and finally proving an end-to-end bound that jointly covers exploration and exploitation under a shared budget. Since this condition depends on unknown ground-truth statistics, we further provide a confidence level test as a criterion for certifying when exploration is theoretically sufficient. Oracle upper bound. Let U∗(T,B)U^*(T,B) denote the cumulative expected reward of the oracle policy with knowledge of the true statistics uj,k,cj,ku_j,k,c_j,k over horizon T under budget B. We establish an upper bound via LPT,BLP_T,B which uses the same formulation as LPτ,bLP_τ,b (Section 4.2) but with a fixed per-round budget ρ=B/Tρ=B/T in place of the adaptive b/τb/τ. We prove that U^(T,B) U(T,B) is an upper bound of U∗(T,B)U^*(T,B) in Appendix C. The regret of WR-Offline is thus bounded by RALP(T,B)≤U^(T,B)−UALP(T,B)R_ALP(T,B)≤ U(T,B)-U_ALP(T,B). Restating regret of ALP. The solution of upper bound algorithm LPT,BLP_T,B has a greedy structure: given per-round budget constraint ρ, it assigns probability 1 to context-action pairs in non-increasing order using their reward-cost ratio (defined below) until the remaining budget ρ can no longer support probability 1 for the next pair’s expected cost, which then receives a fractional probability so that its expected cost exactly exhausts the budget. A budget ρ is boundary if it coincides exactly with a switching point in this ordering; otherwise it is non-boundary. ALP’s regret arises from fluctuations in b/τb/τ around ρ: for non-boundary ρ, small fluctuations leave the solution probability unchanged w.h.p., incurring O(1)O(1) regret; for boundary ρ, fluctuations may shift the probability allocation, yielding O(T)O( T) regret. We restate the ALP regret bound from [40] in Theorem 5.1. The full theorem statement and proof sketch are provided in Appendix D. Theorem 5.1. Given any fixed ρ=B/Tρ=B/T, the regret of ALP with known statistics satisfies: (1) for non-boundary cases, RALP(T,B)=O(1);R_ALP(T,B)=O(1); and (2) for boundary cases, RALP(T,B)=O(T).R_ALP(T,B)=O( T). Sufficient exploration for WR-Online. In WR-Online, uj,ku_j,k and cj,kc_j,k are unknown and estimated online. Meanwhile, the ALP solution relies on an ordered list of context-action pairs determined using the pairwise ratios ξj,k1,k2:=(uj,k1−uj,k2)/(cj,k1−cj,k2) _j,k_1,k_2:=(u_j,k_1-u_j,k_2)/(c_j,k_1-c_j,k_2). If empirical estimates u¯j,k u_j,k, c¯j,k c_j,k induce a different ordering of ξ¯j,k1,k2:=(u¯j,k1−u¯j,k2)/(c¯j,k1−c¯j,k2) ξ_j,k_1,k_2:=( u_j,k_1- u_j,k_2)/( c_j,k_1- c_j,k_2) when exploration ends, the solution during exploitation will be suboptimal compared with the ground truth solution of ALP. If exploration instead produces estimates accurate enough to recover the correct ordering, exploitation runs ALP with the right solution structure and inherits the regret bound of Theorem 5.1. Our goal is therefore to characterize how much exploration suffices to guarantee correct ordering with high probability. The following quantities characterize how difficult this ordering is to recover from finite samples. We assume cj,k1≠cj,k2c_j,k_1≠ c_j,k_2 for all j and actions k1≠k2k_1≠ k_2, and define three quantities: the minimal cost gap Δminc:=minj∈,k1≠k2∈0∪|cj,k1−cj,k2| _ ^c:= _j ,k_1≠ k_2∈\0\ |c_j,k_1-c_j,k_2 |, the minimal ratio separation Δminξ=minj1,j2∈,k11,k12,k21,k22∈0∪|ξj1,k11,k12−ξj2,k21,k22| _ ^ξ= _j_1,j_2 ,\,k_11,k_12,k_21,k_22∈\0\ | _j_1,k_11,k_12- _j_2,k_21,k_22|, and πmin:=minj∈πj _ := _j _j. Small values require longer exploration to achieve correct ordering because the tighter cost gaps and ratio separations require more samples to distinguish reliably, while rarer contexts accumulate observations more slowly. However, smaller separations also imply that the context-action pairs have similar ξ, so misorderings among them are less consequential. Lemma 5.2 shows that if ϵ(T)ε(T) is sufficient, then ϵε-first ALP recovers the correct ordering of ξj,k1,k2 _j,k_1,k_2 with high probability after exploration. Lemma 5.2 (Sufficient exploration). Let 0<δ<10<δ<1 and L:=(Δminc)2ΔminξL:=( _ ^c)^2 _ ^ξ. Under WR-Online, if ϵ(T)≥⌈K(1−δ)πmin+logT⋅max1δ2,128K(1−δ)πminL2⌉,ε(T)\;≥\; K(1-δ) _ + T· \; \ 1δ^2,\; 128K(1-δ) _ L^2 \ , (5) then for any contexts j1,j2∈j_1,j_2 and actions k11,k12,k21,k22∈0∪k_11,k_12,k_21,k_22∈\0\ , if ξj1,k11,k12<ξj2,k21,k22 _j_1,k_11,k_12< _j_2,k_21,k_22, then at the end of the ϵ(T)ε(T)-th round, ℙ[ξ¯j1,k11,k12≥ξ¯j2,k21,k22]≤(16+J)T−2.P\! [\, ξ_j_1,k_11,k_12≥ ξ_j_2,k_21,k_22 ]≤(16+J)T^-2. Moreover, the algorithm ranks all the ξj,k1,k2 _j,k_1,k_2’s correctly with probability no less than 1−(4KJ+J)T−21-(4KJ+J)T^-2. Absent in prior regret analyses with known costs, the core challenge is that both uj,ku_j,k and cj,kc_j,k must be estimated simultaneously, and errors in both propagate through the ratio ξj,k1,k2 _j,k_1,k_2. Our proof (Appendix F) reformulates ratio comparison as an equivalent sign test on the difference of their cross-products, avoiding random denominators entirely. We apply Hoeffding’s inequality to the individual empirical means u¯j,k u_j,k and c¯j,k c_j,k, and the resulting concentration bounds propagate to the cross-product difference via triangle inequality. Theorem 5.3 (End-to-end regret of WR-Online). Let 0<δ<10<δ<1. Under WR-Online, if ϵ(T)ε(T) satisfies condition (5), then the regret of WR-Online satisfies: (1) for non-boundary cases, RWR-Online(T,B)=O(logT)R_ WR-Online(T,B)=O( T); (2) for boundary cases, RWR-Online(T,B)=O(T)R_ WR-Online(T,B)=O( T). Proof sketch. When rankings are correct, the exploitation phase runs ALP with correctly ordered statistics and incurs the regret from Theorem 5.1. The exploration phase contributes an additional O(logT)O( T) regret. Combined, the total is O(logT)O( T) in the non-boundary case and O(T)O( T) in the boundary case since O(T)O( T) dominates O(logT)O( T). When rankings are incorrect, the probability of incorrect ordering is O(T−2)O(T^-2) by Lemma 5.2 that contributes a total of O(T)⋅O(T−2)=O(T−1)O(T)· O(T^-2)=O(T^-1) to regret, which is negligible. ∎ Confidence level test. We further derive a confidence level test (Appendix G) that certifies when the estimated statistics are accurate enough to guarantee correct ordering of ξj,k1,k2 _j,k_1,k_2 w.h.p., providing a theoretically grounded stopping criterion. As the test is conservative in practice because reward and cost gaps in LLM routing are often small, our experiments use a fixed exploration schedule instead. 6 Experiments We evaluate WISERouter under varying workload-level budgets. Section 4 compares WR-Offline against cost-constrained LLM selection baselines on performance, budget adherence, and latency. Section 6.3 evaluates WR-Online’s learning efficiency against offline methods and includes simulation results on empirical regret and budget consumption. Ablation study is provided in Appendix H.7. 6.1 LLM Routing Experiment Setup Datasets. We evaluate the LLM routing baselines on RouterBench [15] and SWE-Bench-verified [20] (SWE-Bench). RouterBench contains 36,49736,497 queries from eight diverse datasets, while SWE-Bench includes 500 realistic questions from real GitHub issues. All datasets use a 50:50 train-test split. Further details, including single-model performance, are provided in Appendix H.1. Implementation Details for WISERouter. We embed queries using OpenAI’s text-embedding-3-small (d=1536d=1536) and discretize via K-means [27] with J=16J=16, selected on validation sets; Appendix H.7 shows robustness to these choices. Deployment budgets range from the cost of routing all queries to the cheapest model to that of always routing all to the most expensive. For WR-Offline, T is the number of test queries with statistics estimated from the training set. For WR-Online, T spans both training and test queries; exploration is restricted to the training set for fair comparison with offline methods, with exploration length set to 1×1× – 4×4× the number of queries in training set. Unlike offline training which requires all model responses per query, each exploration step invokes only one model, keeping the total exploration cost well below the offline baseline. Evaluation Metrics. For each dataset, we use the per-query performance scores and monetary costs as the reward and cost observations; details are in Appendix H.1. Baselines. We compare WISERouter against the following baselines, all of which are inference-time LLM selection methods under cost constraints: (1) FrugalGPT [6] – an LLM cascading method that constrains on a per-query budget; (2) CascadeRouting [8] – a unified LLM cascade and routing method, with a per-query budget constraint; (3) MetaLLM [29] – a bandit-based routing method that controls the per-query cost as a cost-scaling penalty in the reward function and uses UCB [2] for model selection; (4) SingleBest – for each context j, greedily selects the highest-reward action within a per-query budget. All baseline implementation details are provided in Appendix H.2. 111PILOT [32] is not publicly available; we therefore omit it from experiments and discuss it analytically in Section 2. 6.2 Offline Baseline Comparison Table 1: Performance comparison under varying budget constraints ($). SingleBest, MetaLLM, and WR-Offline involve randomness and are averaged over five runs; FrugalGPT and CascadeRouting are deterministic and reported as single runs. Best results in bold. RouterBench SWE-Bench Method B=2.52 B=19.92 B=37.31 B=54.71 B=72.10 B=151.42 B=232.72 B=253.04 B=273.37 B=293.69 B=314.02 B=659.44 FrugalGPT 0.00 0.70 0.70 0.72 0.73 0.80 0.00 0.00 0.00 0.42 0.67 0.68 CascadeRouting 0.50 0.71 0.73 0.75 0.76 0.79 0.51 0.55 0.55 0.56 0.56 0.67 SingleBest 0.36±0.011 0.69±0.002 0.70±0.002 0.70±0.001 0.71±0.002 0.79±0.001 0.24±0.037 0.31±0.064 0.36±0.095 0.40±0.078 0.46±0.054 0.65±0.020 MetaLLM 0.55±0.003 0.70±0.004 0.72±0.020 0.74±0.003 0.74±0.003 0.81±0.001 0.51±0.035 0.51±0.035 0.52±0.103 0.61±0.057 0.65±0.018 0.65±0.018 WR-Offline 0.54±0.003 0.72±0.002 0.74±0.003 0.76±0.002 0.77±0.001 0.81±0.001 0.58±0.033 0.60±0.027 0.62±0.031 0.64±0.020 0.65±0.020 0.65±0.017 (a) Budget Utilization Analysis for RouterBench (b) Budget Utilization Analysis for SWE-Bench Figure 3: Remaining budget ratios at each budget level. Error bars show ±1± 1 std over five runs. Table 2: Latency comparison of LLM routing baselines on RouterBench dataset averaged over all budget settings. Method Train Inference Latency (s) Latency/Query (s) FrugalGPT 8.85×1038.85× 10^3 1.51×10−21.51× 10^-2 CascadeRouting 4.19×1034.19× 10^3 2.07×10−32.07× 10^-3 SingleBest 1.50 2.25×10−42.25× 10^-4 MetaLLM 1.76 5.35×10−35.35× 10^-3 WR-Offline 1.50 1.56×10−31.56× 10^-3 Figure 4: Budget consumption vs. reward gap for the static variant on SWE-Bench (5 runs); leftmost point is under the largest budget constraint. Performance comparison. Table 1 reports test performance across budget levels on RouterBench and SWE-Bench. WR-Offline consistently matches or outperforms all baselines at low-to-mid budgets. FrugalGPT fails entirely at the lowest budgets on both datasets, as its cascade policy requires invoking multiple models per query and thus cannot satisfy tight per-query cost constraints. CascadeRouting is competitive on RouterBench, where it uses test-set statistics following its original setting, but drops on SWE-Bench where only regression-based estimates are available, revealing sensitivity to estimation quality. At the highest budget, most methods converge as any model can be freely invoked. (a) Left: generous budget. Right: constrained budget. (b) Simulation experiment Figure 5: (a) WR-Online vs. offline baselines on RouterBench; vertical dashed lines mark offline training cost. (b) Cumulative cost and amortized regret of budget-aware online algorithms (5 runs). Budget Utilization. Figure 3 plots the ratio of remaining to total budget; positive values near zero indicate effective utilization without overspending, while negative values indicate violations. On RouterBench, WR-Offline maintains this ratio closest to zero across all budget levels because its adaptive re-solving with b/τb/τ at each step continuously corrects for cost consumption. FrugalGPT underutilizes the budget at mid budget levels and fails entirely at the tightest budget. CascadeRouting generally respects the budget with occasional violations at low-to-mid levels. On SWE-Bench, a medium-cost model dominates the cost-performance frontier, leaving some budget unused across methods. The exception is FrugalGPT at the highest budget, which exploits the extra slack to achieve the best performance on this dataset (see also Table 1). Latency Comparison. Table 2 reports training and per-query inference latency on RouterBench. FrugalGPT and CascadeRouting re-optimize cascade parameters per budget level, incurring high training cost. WR-Offline trains in 1.501.50s on CPU, over 5,900×5,900× faster than FrugalGPT which requires 8.85×1038.85× 10^3s on GPU because WR-Offline estimates statistics once and adapts to any budget at inference without retraining. Adaptive LP vs. Static LP constraint. To assess whether WR-Offline’s adaptive constraint is essential for budget compliance, we compare it against a static variant that solves LPT,BLP_T,B with the same estimated statistics. We focus on the more realistic SWE-Bench, where high per-query cost variance makes budget drift more likely and adaptivity more important. Each point in Figure 4 shows its budget consumption and performance difference w.r.t. WR-Offline at one budget value. Without adaptive constraint, the static variant overshoots the workload budget by >5%>5\%; such overspends may be unacceptable when compounded over long horizons or over repeated deployments. WR-Offline avoids cost violation through adaptive LP, maintaining budget compliance without sacrificing reward. 6.3 WR-Online Experiment Performance Under End-to-End Budget. We compare WR-Online with offline methods under end-to-end budgets covering both data collection and deployment, in two scenarios: generous – full training and maximum deployment budget and constrained – full training and minimum deployment budget (Figure 5(a)). In the generous setting, all offline methods converge to around 0.80.8 average quality on RouterBench. WR-Online reaches this with a single pass over training queries, reducing data collection cost by 90%90\%. This suggests that marginal gains from additional supervision diminish rapidly. On SWE-Bench (Figure 6, Appendix H.5), WR-Online improves with more exploration, reflecting that this dataset requires longer exploration to accurately estimate reward statistics. In the constrained setting, offline methods pre-commit training expense against deployment budget. WR-Online reallocates unspent exploration budget to deployment, matching the generous-setting performance under the same end-to-end budget. Appendix H.6 validates that the exploration converges accurately to ground-truth statistics. Simulation Experiment for WR-Online. To validate Theorem 5.3, we run a controlled simulation under a global budget (Figure 5(b)). WR-Online’s amortized regret decays faster than O(1/T)O(1/ T), consistent with Theorem 5.3, and nearly matches ϵε-first ALP with known costs, with the gap attributable to online cost estimation. Other algorithms under-spend significantly while WR-Online tracks the B/TB/T slope closely, incurring lower regret. See Appendix H.8 for detailed settings. 7 Conclusions and Limitations We present WISERouter, a unified LLM routing framework that formulates routing as a constrained contextual bandit under a workload-level budget. WR-Offline enforces budget via Adaptive Linear Programming and adapts to new budgets at inference without retraining; WR-Online extends this to the data-scarce setting by jointly learning reward and cost statistics online under a common shared budget. We prove the end-to-end regret bound for WR-Online covering exploration and exploitation, and demonstrate superior performance at tight budgets, precise budget utilization, and up to 90%90\% reduction in training data with WR-Online. Limitations. The i.i.d. context assumption holds in stable API query workloads but may be violated when queries exhibit dependencies or distributional shift, in which case regret bound no longer applies; see more discussion in Appendix A. We only explored monetary cost as the constraint on two datasets; extending to other cost definitions and benchmarks with larger model pools is a natural direction for future work. References [1] Anthropic (2026) Claude Team. Note: https://claude.com/pricing/teamAccessed: 2026-04-28 Cited by: §1. [2] P. Auer, N. Cesa-Bianchi, and P. Fischer (2002-05) Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47 (2–3), p. 235–256. External Links: ISSN 0885-6125, Link, Document Cited by: Appendix B, §2, §5, §6.1. [3] A. Badanidiyuru, J. Langford, and A. Slivkins (2014-13–15 Jun) Resourceful contextual bandits. In Proceedings of The 27th Conference on Learning Theory, M. F. Balcan, V. Feldman, and C. Szepesvári (Eds.), Proceedings of Machine Learning Research, Vol. 35, Barcelona, Spain, p. 1109–1134. Cited by: Appendix B, §1, §2. [4] Z. Cai, Y. Zhang, B. Gao, Y. Liu, Y. Li, T. Liu, K. Lu, W. Xiong, Y. Dong, J. Hu, and W. Xiao (2025) PyramidKV: dynamic KV cache compression based on pyramidal information funneling. In Second Conference on Language Modeling, External Links: Link Cited by: §2. [5] C. Chen, S. Borgeaud, G. Irving, J. Lespiau, L. Sifre, and J. Jumper (2023) Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318. Cited by: §2. [6] L. Chen, M. Zaharia, and J. Zou (2024) FrugalGPT: How to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research. External Links: ISSN 2835-8856 Cited by: Appendix B, §1, §1, §2, §2, §3.1, §6.1. [7] W. Chiang, L. Zheng, Y. Sheng, A. N. Angelopoulos, T. Li, D. Li, B. Zhu, H. Zhang, M. I. Jordan, J. E. Gonzalez, and I. Stoica (2024) Chatbot arena: an open platform for evaluating llms by human preference. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: §1. [8] J. Dekoninck, M. Baader, and M. Vechev (2025) A unified approach to routing and cascading for LLMs. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: Appendix B, §1, §2, §2, §3.1, §6.1. [9] D. Ding, A. Mallick, C. Wang, R. Sim, S. Mukherjee, V. Rühle, L. V. S. Lakshmanan, and A. H. Awadallah (2024) Hybrid LLM: cost-efficient and quality-aware query routing. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: Appendix B, §1, §1, §1, §1, §2. [10] D. Ding, A. Mallick, S. Zhang, C. Wang, D. Madrigal, M. D. C. H. Garcia, M. Xia, L. V. S. Lakshmanan, Q. Wu, and V. Rühle (2025) BEST-route: adaptive LLM routing with test-time optimal compute. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: Appendix B. [11] W. Ding, T. Qiny, X. Zhang, and T. Liu (2013) Multi-armed bandit with budget constraint and variable costs. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI’13, p. 232–238. Cited by: Appendix B. [12] W. Fedus, B. Zoph, and N. Shazeer (2022-01) Switch transformers: scaling to trillion parameter models with simple and efficient sparsity. J. Mach. Learn. Res. 23 (1). External Links: ISSN 1532-4435 Cited by: §2. [13] N. Gupta, H. Narasimhan, W. Jitkrittum, A. S. Rawat, A. K. Menon, and S. Kumar (2024) Language model cascades: token-level uncertainty and beyond. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: Appendix B. [14] B. Hassibi, D.G. Stork, and G.J. Wolff (1993) Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Networks, Vol. , p. 293–299 vol.1. External Links: Document Cited by: §2. [15] Q. J. Hu, J. Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay (2024) RouterBench: A benchmark for multi-llm routing system. CoRR abs/2403.12031. External Links: Link, Document, 2403.12031 Cited by: §1, §1, §6.1. [16] K. Huang, Y. Shi, D. Ding, Y. Li, Y. Fei, L. Lakshmanan, and X. Xiao (2025-09) ThriftLLM: on cost-effective selection of large language models for classification queries. Proc. VLDB Endow. 18 (11), p. 4410–4423. External Links: ISSN 2150-8097, Link, Document Cited by: Appendix B, §2. [17] Y. Huang, X. Feng, B. Li, Y. Xiang, H. Wang, B. Qin, and T. Liu (2024) Ensemble learning for heterogeneous large language models with deep parallel collaboration. In Neural Information Processing Systems, External Links: Link Cited by: Appendix B. [18] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko (2018) Quantization and training of neural networks for efficient integer-arithmetic-only inference. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Vol. , p. 2704–2713. External Links: Document Cited by: §2. [19] D. Jiang, X. Ren, and B. Y. Lin (2023-07) LLM-blender: ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), A. Rogers, J. Boyd-Graber, and N. Okazaki (Eds.), Toronto, Canada, p. 14165–14178. External Links: Document Cited by: Appendix B, §2. [20] C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. R. Narasimhan (2024) SWE-bench: can language models resolve real-world github issues?. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1, §6.1. [21] Y. Jin, C. Wu, D. Brooks, and G. Wei (2023) S3: increasing gpu utilization during generative inference for higher throughput. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: §2. [22] Y. LeCun, J. Denker, and S. Solla (1989) Optimal brain damage. In Advances in Neural Information Processing Systems, D. Touretzky (Ed.), Vol. 2. Cited by: §2. [23] Y. Leviathan, M. Kalman, and Y. Matias (2023) Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, p. 19274–19286. Cited by: §2. [24] L. Li, W. Chu, J. Langford, and R. E. Schapire (2010) A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, W ’10, New York, NY, USA, p. 661–670. External Links: ISBN 9781605587998, Document Cited by: Appendix B, §H.8. [25] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, B. Newman, B. Yuan, B. Yan, C. Zhang, C. Cosgrove, C. D. Manning, C. Re, D. Acosta-Navas, D. A. Hudson, E. Zelikman, E. Durmus, F. Ladhak, F. Rong, H. Ren, H. Yao, J. WANG, K. Santhanam, L. Orr, L. Zheng, M. Yuksekgonul, M. Suzgun, N. Kim, N. Guha, N. S. Chatterji, O. Khattab, P. Henderson, Q. Huang, R. A. Chi, S. M. Xie, S. Santurkar, S. Ganguli, T. Hashimoto, T. Icard, T. Zhang, V. Chaudhary, W. Wang, X. Li, Y. Mai, Y. Zhang, and Y. Koreeda (2023) Holistic evaluation of language models. Transactions on Machine Learning Research. External Links: ISSN 2835-8856 Cited by: §1. [26] K. Lu, H. Yuan, R. Lin, J. Lin, Z. Yuan, C. Zhou, and J. Zhou (2024-06) Routing to the expert: efficient reward-guided ensemble of large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 1964–1974. External Links: Document Cited by: Appendix B, §1, §1, §2. [27] J. B. McQueen (1967) Some methods of classification and analysis of multivariate observations. In Proc. of 5th Berkeley Symposium on Math. Stat. and Prob., p. 281–297. Cited by: §6.1. [28] K. Mei, W. Xu, M. Guo, S. Lin, and Y. Zhang (2026-12) OmniRouter: budget and performance controllable multi-llm routing. SIGKDD Explor. Newsl. 27 (2), p. 107–116. External Links: ISSN 1931-0145, Link, Document Cited by: Appendix B. [29] Q. H. Nguyen, T. Dao, D. C. Hoang, J. Decugis, S. Manchanda, N. V. Chawla, and K. D. Doan (2025) MetaLLM: a high-performant and cost-efficient dynamic framework for wrapping llms. External Links: 2407.10834, Link Cited by: Appendix B, §1, §2, §6.1. [30] I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2025) RouteLLM: learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix B, §1, §1, §1, §1, §2. [31] OpenAI (2026) API Pricing. Note: https://openai.com/api/pricing/Accessed: 2026-04-28 Cited by: §1. [32] P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma (2025-11) Adaptive LLM routing under budget constraints. In Findings of the Association for Computational Linguistics: EMNLP 2025, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 23934–23949. External Links: Document, ISBN 979-8-89176-335-7 Cited by: Appendix B, §2, footnote 1. [33] M. Poon, X. Dai, X. Liu, F. Kong, J. C.S. Lui, and J. Zuo (2026) Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40. Cited by: Appendix B. [34] N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. V. Le, G. E. Hinton, and J. Dean (2017) Outrageously large neural networks: the sparsely-gated mixture-of-experts layer. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, External Links: Link Cited by: §2. [35] R. S. Sutton and A. G. Barto (2018) Reinforcement learning: an introduction. A Bradford Book, Cambridge, MA, USA. External Links: ISBN 0262039249 Cited by: Appendix B, §H.8. [36] L. Tran-Thanh, A. Chapman, E. Munoz de Cote, A. Rogers, and N. R. Jennings (2010-Jul.) Epsilon–first policies for budget–limited multi-armed bandits. Proceedings of the AAAI Conference on Artificial Intelligence 24 (1), p. 1211–1216. External Links: Document Cited by: Appendix B. [37] V. Vanhoucke, A. Senior, and M. Z. Mao (2011) Improving the speed of neural networks on cpus. In Deep Learning and Unsupervised Feature Learning Workshop, NIPS 2011, Cited by: §2. [38] X. Wang, Y. Liu, W. Cheng, X. Zhao, Z. Chen, W. Yu, Y. Fu, and H. Chen (2025-04) MixLLM: Dynamic Routing in Mixed Large Language Models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), L. Chiruzzo, A. Ritter, and L. Wang (Eds.), Albuquerque, New Mexico, p. 10912–10922. External Links: ISBN 979-8-89176-189-6 Cited by: Appendix B, Appendix B, §1, §1, §4.1. [39] C. White, S. Dooley, M. Roberts, A. Pal, B. Feuer, S. Jain, R. Shwartz-Ziv, N. Jain, K. Saifullah, S. Dey, Shubh-Agrawal, S. S. Sandha, S. V. Naidu, C. Hegde, Y. LeCun, T. Goldstein, W. Neiswanger, and M. Goldblum (2025) LiveBench: a challenging, contamination-free LLM benchmark. In The Thirteenth International Conference on Learning Representations, Cited by: §1. [40] H. Wu, R. Srikant, X. Liu, and C. Jiang (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, Cambridge, MA, USA, p. 433–441. Cited by: Appendix B, Appendix D, Appendix D, Appendix D, Appendix E, Appendix E, §H.8, §1, §2, §3.2, §4.3, §5, §5. [41] M. Yue, J. Zhao, M. Zhang, L. Du, and Z. Yao (2024) Large language model cascades with mixture of thought representations for cost-efficient reasoning. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: Appendix B, §1. Appendix contents Appendix A Discussion of Assumptions We elaborate on the three assumptions introduced in Section 3.1 and discuss their practical validity. I.i.d. contexts. There are two distinct aspects of this assumption. First, query independence: queries arrive without state transitions between them, enabling the contextual bandit formulation. This holds in the majority of real-world LLM API usage scenarios (e.g., document summarization, customer support all treat each query as a self-contained request), and is implicit in all supervised routing baselines, which also treat queries independently. Second, stationarity: the context distribution πj\ _j\ is assumed stable within the planning horizon T. Setting T to a window that captures recurring traffic patterns (e.g., weekly business-hours cycles) makes this reasonable in practice. For longer-term drift, the context distribution and LP can be easily updated from recent traffic without re-exploring model statistics. Finite horizon T. A finite T is standard in the constrained contextual bandit literature as it makes regret analysis tractable; T can be set arbitrarily large, and the analysis characterizes how regret grows as a function of T. In practice, T is calibrated to the deployment window (e.g., a monthly API quota) using historical query volume estimates. Feedback acquisition. The monetary cost StS_t is available immediately via token-count pricing. The reward YtY_t is not restricted to ground-truth correctness: any observable scalar signal like proxy reward model scores, user thumbs-up/down feedback, or code accept rates can qualify. In WR-Offline, YtY_t is read from histD_hist and is not needed at inference time. In WR-Online, YtY_t is used during exploration to update u¯j,k u_j,k; per-cluster averaging over queries naturally absorbs observation noise, and delayed reward updates can be deferred without interrupting routing decisions. Appendix B Related Work We expand on the related work highlights in Section 2 with inference-time LLM selection and constrained bandit methods. Inference-time LLM selection. Motivated by the notable cost quality heterogeneity across today’s LLMs, recent work on efficient LLM inference has developed into three paradigms: routing, cascading and ensembling. LLM Routing aims to learn a policy that routes a query to the most suitable model from a pool of candidate LLMs. HybridLLM [9] and RouteLLM [30] focus on a two-model setting, train a router that preserves quality while reducing cost by sending easy queries to a smaller model. Subsequent work such as Zooter [26] and MixLLM [38] extends this supervise-trained router idea to larger model pools and explicitly manages the quality-cost trade-off. OmniRouter [28] predicts cost and performance for each model-query pair using a retrieval-augmented predictor, then uses Lagrangian dual optimization to minimize global cost subject to a global performance threshold. This predictor requires dense historical model-query pair statistics, collecting which can be expensive. BestRoute [10] explores best-of-n sampling to better exploit test-time compute with smaller models and shows that this leads to significant reduction in cost compared to baselines. The approach is essentially a heuristic and lacks formal guarantees. Our work focuses on the routing setting where one model is called once per query with an explicit workload-level budget, and applies online learning with exploration when dense supervision dataset is too expensive to collect. LLM Cascading method [6, 41, 13] executes a pre-defined LLM sequence: a small, cheap model answers first and the system escalates to larger ones when a learned threshold criterion fails; Dekoninck et al. [8] cast routing and cascading within one framework and enforce explicit per-query budget. While they derive optimality results, per-query constraints can be myopic and suboptimal under a workload-level budget. LLM Ensemble methods such as DeePEn [17] aligns model logits in a shared space and aggregates them at the token level, while LLMBlender [19] ensembles post hoc by training a T5-based model to fuse multiple model outputs into a refined response. These methods primarily optimize accuracy without explicit cost or latency constraints. ThriftLLM [16] enforces per-query budget and achieves cost-efficient classification. Given our focus on single-model LLM routing with workload-level budget, we do not compare with these methods further. Constrained Contextual Bandits. Contextual bandits extends the well-known multi-armed bandits (MAB) by utilizing additional context at each round, allowing the agent to choose an action conditioned on the context. Common baselines include ϵε-greedy [35], UCB [2], and LinUCB [24]. In a constrained bandit setting, an agent optimizes the cumulative reward subject to a global budget constraint. A well-known strategy for budget-constrained MAB without contexts is ϵε-first [36]. Badanidiyuru et al. [3] studies budget constrained contextual bandits and establishes an O~(T) O( T) regret bound; however, their approach is computationally expensive in practice. Following this line, [40] proposes UCB-ALP for unit-cost systems where all arms have a uniform cost and ϵε-first ALP for heterogeneous-cost systems, though rely on cost statistics being known a priori. Another line of work studies stochastic costs under budget constrained MAB using UCB-style frameworks [11]. Our work extends ϵε-first ALP to the regime where both reward and cost must be estimated online under a single shared budget covering exploration and exploitation. LLM Routing as a Bandit Problem. Several recent studies explicitly formulate LLM routing as a contextual bandits problem: each candidate model is an action, query embeddings provide context, and reward is reflected by task performance or human preference. MetaLLM [29] uses UCB to select an LLM per query, leveraging reward estimates learned from offline preference data to balance cost against performance. MixLLM [38] integrates contextual bandits and selects a model by a LinUCB-like score augmented by uncertainty and a latency penalty. Poon et al. [33] applies Greedy LinUCB to the context evolved from multi-step chat interaction under global budget. PILOT [32] initializes a LinUCB router from preference-aligned embeddings and enforces budget at deployment via an online knapsack solver; its regret analysis covers only the router learning phase, not the full exploration-to-deployment pipeline. All these works either apply budget constraints only at deployment or lack end-to-end regret guarantees jointly covering learning and routing. Appendix C Proof of U^(T,B) U(T,B) is Upper Bound Lemma C.1. For a heterogeneous cost system with K models, J discrete contexts and known true statistics, if the time-horizon is T and the budget is B, then the total expected reward U^(T,B)≥U∗(T,B) U(T,B)≥ U^*(T,B), where U^(T,B)=Tv(ρ) U(T,B)=Tv(ρ). Proof. Let Nj,kN_j,k be the number of rounds that an action k is taken under context j for any realization under any feasible algorithm with known statistics. Let pj,k:=[Nj,k]/(πjT)p_j,k:=E[N_j,k]/( _jT), which satisfies 0≤pj,k≤10≤ p_j,k≤ 1. Then the expected total reward for this feasible algorithm becomes ∑j=1J∑k=1Kuj,k[Nj,k]=T∑j=1J∑k=1Kpj,kπjuj,k. _j=1^J _k=1^Ku_j,kE[N_j,k]=T _j=1^J _k=1^Kp_j,k _ju_j,k. Moreover, because we start with a feasible algorithm, the expected budget constraint is met for all realizations, i.e., [∑t=1TSt]≤BE [ _t=1^TS_t ]≤ B, we have [∑t=1TSt]=∑j=1J∑k=1K[∑t=1TStXt=j,At=k]=∑j,kcj,k[Nj,k]=T∑jπj∑kpj,kcj,k.E [ _t=1^TS_t ]= _j=1^J _k=1^KE\! [ _t=1^TS_t 1\X_t=j,A_t=k\ ]= _j,kc_j,k\,E[N_j,k]=T _j _j _kp_j,kc_j,k. Feasibility in expectation implies ∑jπj∑kpj,kcj,k≤B/T. _j _j _kp_j,kc_j,k≤ B/T. Thus, the expected total reward obtained by any feasible algorithm, including the oracle algorithm, is upper bounded by U^(T,B) U(T,B). ∎ Appendix D Detailed Regret Bound of ALP To derive this upper bound, we need to derive the explicit solution of the upper bounding linear program LPT,BLP_T,B and analyze the regret incurred when b/τb/τ deviates from B/TB/T. The details of this derivation, following the approach in [40], are provided in Appendix E. Here, we introduce the essential concepts and quantities that will be used in the main regret bound of Theorem D.1. Deriving explicit LP solution. The goal is to rank all pairs globally by their reward rates, then apply greedy algorithm to prioritize pairs with the highest reward rates and select those actions with corresponding probabilities. We first prune the candidate sets of context-action pairs using two measurements. The reward rate ηj,k=uj,kcj,k _j,k= u_j,kc_j,k measures expected utility per unit cost for pair (j,k)(j,k). The ratio ξj,k1,k2:=uj,k1−uj,k2cj,k1−cj,k2,k1≠k2, _j,k_1,k_2:= u_j,k_1-u_j,k_2c_j,k_1-c_j,k_2,k_1≠ k_2, measures the additional expected reward per additional unit cost when switching from k2k_2 to k1k_1 under context j. We can remove certain suboptimal pairs without decreasing the LP optimum by comparing ηj,k _j,k and ξj,k1,k2 _j,k_1,k_2 (exact conditions in Appendix E). After pruning, the remaining actions within each context admit a consistent ordering w.r.t. ξj,k1,k2 _j,k_1,k_2. We then define a transformation detailed in Appendix E to obtain an equivalent linear program LP~T,B LP_T,B such that the remaining candidate pairs can be globally sorted by a transformed marginal reward ratio η~j,k η_j,k. The key requirement for this reduction is that for any context j, the ordered ratios ξj,k1,k2 _j,k_1,k_2 lead to a consistent ranking of η~j,k η_j,k. Let the pairs sorted in descending order of η~j,k η_j,k be (j(1),k(1)),…,(j(M),k(M))\(j^(1),k^(1)),…,(j^(M),k^(M))\, where M is the total number of remaining pairs after pruning. We denote η~1:=maxiη~j(i),k(i) η_1:= _i η_j^(i),k^(i) and η~M:=miniη~j(i),k(i) η_M:= _i η_j^(i),k^(i) accordingly. Boundary and non-boundary cases. The performance of ALP depends on how the average remaining budget bτ bτ evolves relative to the static B/TB/T. In particular, the regret is affected by how often b/τb/τ crosses certain critical thresholds associated with the sorted transformed pairs. We define the cumulative expected cost mass up to index i as Qi:=∑i′=1iπj(i′)c~j(i′),k(i′)Q_i:= _i =1^i _j^(i )\, c_j^(i ),k^(i ), representing the total expected cost for the first i transformed items in the ordering M. For any static per-round budget ρ∈(0,Q]ρ∈(0,Q], we define the threshold index i~(ρ):=maxi∈0,1,…,M:Qi≤ρ. i(ρ):= \i∈\0,1,…,M\:Q_i≤ρ\,\. We say that ρ is non-boundary if ρ≠Qiρ≠ Q_i for all i∈1,…,Mi∈\1,…,M\ and boundary if ρ=Qi(ρ)ρ=Q_i(ρ) for some i(ρ)i(ρ). Concentration of b. Since regret mainly occurs when the empirical average remaining budget b/τb/τ deviates from ρ, we apply Lemma 12 of [40] based on the Azuma–Hoeffding inequality to obtain the tail bound ℙ|b/τ−ρ|<δ≥e−κδ2τ,0<δ<1P\|b/τ-ρ|<δ\≥ e^-κδ^2τ,0<δ<1 for some constant κ=ρ22κ= ρ^22, which controls the probability of large deviations. The following theorem states that the ALP algorithm has a O(1)O(1) regret in the non-boundary case, and incurs an O(T)O( T) regret in the boundary case. Theorem D.1. Given any fixed ρ∈(0,1)ρ∈(0,1), there exists a positive constant κ:=ρ22κ:= ρ^22, such that the regret of ALP satisfies: (1) (Non-boundary cases) If ρ≠Qiρ≠ Q_i for any i∈1,2,…,Mi∈\1,2,…,M\, then RALP(T,B)≤η~1−η~M1−e−2κδ2,R_ALP(T,B)≤ η_1- η_M1-e^-2κδ^2, where δ=minρ−Qi~(ρ),Qi~(ρ)+1−ρδ= \ρ-Q_ i(ρ),Q_ i(ρ)+1-ρ\. (2) (Boundary cases) If ρ=Qi(ρ)ρ=Q_i(ρ) for some i∈1,2,…,Mi∈\1,2,…,M\, then RALP(T,B)≤Θ(∘)T+η~1−η~M1−e−2κδ2,R_ALP(T,B)≤ ^( ) T+ η_1- η_M1-e^-2κδ^2, where Θ(∘)=(η~1−η~M)∑τ=1Tπκτ ^( )=( η_1- η_M)Σ^T_τ=1 πκτ and δ=minρ−Qi~(ρ)−1,Qi~(ρ)+1−ρδ= \ρ-Q_ i(ρ)-1,Q_ i(ρ)+1-ρ\. Proof Sketch. The proof for Theorem D.1 follows a similar structure as the unit-cost ALP regret proof in Appendix B.2 from [40]. For the non-boundary cases, the single-round expected reward satisfies [v(b/τ)]=v(ρ)E[v(b/τ)]=v(ρ) if the threshold i~(b/τ)=i~(ρ) i(b/τ)= i(ρ) for all possible vaules of b, where v(ρ)v(ρ) is the optimal single-round value of LPT,BLP_T,B at average budget ρ=B/Tρ=B/T. The regret is then bounded by a constant because the probability of the event i~(b/τ)≠i~(ρ) i(b/τ)≠ i(ρ) decays exponentially due to the concentration bound of b. For the boundary cases, we show the theorem by expressing the regret in terms of the expected absolute deviation of the average remaining budget bτ bτ from the target value ρ, i.e., [|bτ−ρ|]E[| bτ-ρ|]. ∎ Appendix E Solution Formulation for LPT,BLP_T,B In this section, we first decompose LPT,BLP_T,B into subproblem SPjSP_j which is a constrained problem on a single context j. Secondly, we show some actions can be deleted without affecting the performance in LPT,BLP_T,B. Lemma E.1. For any given ρj≥0 _j≥ 0, there exists an optimal solution of SPjSP_j, i.e., j∗=(pj,1∗,pj,2∗,…,pj,Kj∗)p_j^*=(p_j,1^*,p_j,2^*,…,p_j,K_j^*), which satisfies: 1. For k1k_1, if there exists another action k2k_2 such that ηj,k1≤ηj,k2 _j,k_1≤ _j,k_2 and uj,k1≤uj,k2u_j,k_1≤ u_j,k_2, then pj,k1∗=0p_j,k_1^*=0; 2. For k1k_1, if there exist two actions k2k_2 and k3k_3 such that ηj,k2≤ηj,k1≤ηj,k3 _j,k_2≤ _j,k_1≤ _j,k_3, uj,k2≥uj,k1≥uj,k3u_j,k_2≥ u_j,k_1≥ u_j,k_3, and uj,k1−uj,k3cj,k1−cj,k3≤uj,k2−uj,k3cj,k2−cj,k3, u_j,k_1-u_j,k_3c_j,k_1-c_j,k_3≤ u_j,k_2-u_j,k_3c_j,k_2-c_j,k_3, then pj,k1∗=0p_j,k_1^*=0. Intuitively, the first part of Lemma E.1 shows that if an action has small normalized and original expected reward, then it can be removed. The second part of Lemma E.1 shows that if an action has small normalized expected reward and medium original expected reward, but the increasing rate is smaller than another action with larger expected reward, then it can also be removed. Detailed proof can be found in [40] With probabilities pj,k∈[0,1]p_j,k∈[0,1] of choosing action k under context j, the oracle upper bound is the optimal value v^(ρ) v(ρ) of maxpj,k _\p_j,k\~~ ∑j=1Jπj∑kpj,kuj,k _j=1^J _j _kp_j,k\,u_j,k (6) s.t. ∑j=1Jπj∑kpj,kcj,k≤ρ, _j=1^J _j _kp_j,k\,c_j,k≤ρ, (7) ∑kpj,k≤1(∀j), _kp_j,k≤ 1~(∀ j), (8) pj,k∈[0,1]. p_j,k∈[0,1]. (9) The intra-context constraint ∑kpj,k≤1 _kp_j,k≤ 1 enforces the probabilities of taking action k under context j forms a probability distribution. The constraints can be decoupled by first allocating budget for each context, and then solving a subproblem with the allocated budget constraint for each context. Specifically, let ρj _j be the budget allocated to context j, then ℒT,BLP_T,B can be decomposed as follows: maxρj _\ _j\ ∑j=1Jπjv^j(ρj), _j=1^J _j v_j( _j), s.t. ∑j=1Jπjρj≤BT, _j=1^J _j _j≤ BT, where (SPj)v^j(ρj)=maxpj,k (SP_j) v_j( _j)= _\p_j,k\ ∑k=1Kpj,kuj,k, _k=1^Kp_j,ku_j,k, (10) s.t. ∑k=1Kpj,kcj,k≤ρj. _k=1^Kp_j,kc_j,k≤ _j. (11) ∑kpj,k≤1 _kp_j,k≤ 1 (12) pj,k∈[0,1] p_j,k∈[0,1] (13) After we introduce the transformations of p~,u~ p, u, and c~ c, For each j, sort actions by ηj,k=uj,k/cj,k _j,k=u_j,k/c_j,k in descending order and introduce the transformations of p~,u~ p, u, and c~ c. Let η~j,kja=u~j,kja/c~j,kja η_j,k_j_a= u_j,k_j_a/ c_j,k_j_a be the normalized expected reward of virtual action kjak_j_a. For a=1a=1, using uj,kj1cj,kj1≥uj,kj2cj,kj2 u_j,k_j_1c_j,k_j_1≥ u_j,k_j_2c_j,k_j_2, we can show that η~j,kj1≥η~j,kj2 η_j,k_j_1≥ η_j,k_j_2. For 2≤a≤Kj−12≤ a≤ K_j-1, using uj,kja−uj,kja−1cj,kja−cj,kja−1≥uj,kja+1−uj,kja−1cj,kja+1−cj,kja−1, u_j,k_j_a-u_j,k_j_a-1c_j,k_j_a-c_j,k_j_a-1≥ u_j,k_j_a+1-u_j,k_j_a-1c_j,k_j_a+1-c_j,k_j_a-1, we can show that η~j,kja≥η~j,kja+1 η_j,k_j_a≥ η_j,k_j_a+1. In other words, we can verify that η~j,kj1≥η~j,kj2≥⋯≥η~j,kj,Kj η_j,k_j_1≥ η_j,k_j_2≥·s≥ η_j,k_j,K_j. Thus, without intra-context constraint, the optimal solution p~j∗=[p~j,k1∗,p~j,k2∗,…,p~j,kKj∗] p_j^*=[ p_j,k_1^*, p_j,k_2^*,…, p_j,k_K_j^*] automatically satisfies p~j,k1∗≥p~j,k2∗≥⋯≥p~j,kKj∗ p_j,k_1^*≥ p_j,k_2^*≥·s≥ p_j,k_K_j^*. Hence, we can remove the intra-context constraint, and thus decouple the probability constraint under a context. The global LP reduces to a threshold solution by greedy algorithm: sorting all virtual pairs (j,a)(j,a) by η~ η yields the index i~(ρ) i(ρ) and cumulative masses QiQ_i specified in the main text; the solution fully takes indices ≤i~(ρ)≤ i(ρ), partially takes i~(ρ)+1 i(ρ)+1, and rejects the rest. Step 1: Solution formulation of LPT,BLP_T,B. To simplify the LP solution, we first remove context-action pairs that do not contribute to the optimum [40]. Define the reward rate ηj,k=uj,k/cj,k _j,k=u_j,k/c_j,k. For context j, assume that the remaining candidate set j=kj1,kj2,…,kjKjA_j=\k_j_1,k_j_2,…,k_j_K_j\ has been sorted in descending order of their reward rates ηj,k _j,k. We then introduce the following transformations: pj,kja=p~j,kja−p~j,kja+1,if 1≤a≤Kj−1,p~j,kjKj,if a=Kj.p_j,k_j_a= cases p_j,k_j_a- p_j,k_j_a+1,&if 1≤ a≤ K_j-1,\\ p_j,k_j_K_j,&if a=K_j. cases u~j,kja=uj,kj1,if a=1,uj,kja−uj,kja−1,if 2≤a≤Kj, u_j,k_j_a= casesu_j,k_j_1,&if a=1,\\ u_j,k_j_a-u_j,k_j_a-1,&if 2≤ a≤ K_j, cases c~j,kja=cj,kj1,if a=1,cj,kja−cj,kja−1,if 2≤a≤Kj. c_j,k_j_a= casesc_j,k_j_1,&if a=1,\\ c_j,k_j_a-c_j,k_j_a-1,&if 2≤ a≤ K_j. cases By formulating the initial LP into the LP~T,B LP_T,B problem with transformed variables p~ p, c~ c, and u~ u, the intra-context constraint can be omitted, as it is implicitly satisfied after the transformation. This follows from the property of context–action pairs once those that never appear in the optimal solution are removed. (LP~T,B) ( LP_T,B)\; maxp~j,k∑j=1J∑a=1Kjπjp~j,kjau~j,kja _ p_j,k _j=1^J _a=1^K_j _j p_j,k_j_a\, u_j,k_j_a s.t.∑j=1J∑a=1Kjπjp~j,kjac~j,kja≤BT .t. _j=1^J _a=1^K_j _j p_j,k_j_a\, c_j,k_j_a≤ BT p~j,kja∈[0,1],∀j,and 1≤a≤Kj p_j,k_j_a∈[0,1],∀ j,and 1≤ a≤ K_j After removing the intra-context constraint, all pairs (j,kja)(j,k_j_a) can be ordered in descending order of their expected reward rate, defined as η~j,kja=u~j,kja/c~j,kja η_j,k_j_a= u_j,k_j_a/ c_j,k_j_a. The resulting sequence is denoted by their indices as (j(1),k(1)),…,(j(M),k(M))\(j^(1),k^(1)),…,(j^(M),k^(M))\. Let ρ=B/Tρ=B/T and i~(ρ)=maxi:∑i′=1iπj(i′)c~j(i′),k(i′)≤ρ i(ρ)= \i: _i =1^i _j^(i ) c_j^(i ),k^(i )≤ρ \, which represents a threshold index with cumulative cost mass under ρ. The optimal solution of LP~T,B LP_T,B can be expressed as following: p~j(i),k(i)(ρ)=1,if 1≤i≤i~(ρ),ρ−∑i′=1i~(ρ)πj(i′)c~j(i′),k(i′)πj(i~(ρ)+1)c~j(i~(ρ)+1),k(i~(ρ)+1),if i=i~(ρ)+1,0,if i>i~(ρ)+1. p_j^(i),k^(i)(ρ)= cases1,&if 1≤ i≤ i(ρ),\\[4.0pt] ρ- _i =1 i(ρ) _j^(i ) c_j^(i ),k^(i ) _j^( i(ρ)+1) c_j^( i(ρ)+1),k^( i(ρ)+1),&if i= i(ρ)+1,\\[6.0pt] 0,&if i> i(ρ)+1. cases The optimal solution of LPT,BLP_T,B can be calculated by reversing the transformation. Appendix F Proof of Lemma 5.2 Proof. Lowerbound of context-action pair. We first analyze the number of executions for each context-action pair (j,k)(j,k) in the exploration stage ϵ(T)ε(T). Let Nj=∑t=1ϵ(T)(Xt=j)N_j= _t=1^ε(T) 1(X_t=j) be the number of occurences of context j up to round ϵ(T)ε(T). Since each context XtX_t arrives i.i.d. at each timestep, we can use Hoeffding’s Inequality for each context j. ℙ[∀j∈,Nj≥(1−δ)πjϵ(T)] [∀ j ,N_j≥(1-δ) _jε(T) ] ≥1−∑j=1Jℙ[Nj<(1−δ)πjϵ(T)] ≥ 1- _j=1^JP [N_j<(1-δ) _jε(T) ] ≥1−Je−2δ2ϵ(T) ≥ 1-Je^-2δ^2ε(T) ≥1−Je−2logT ≥ 1-Je^-2 T =1−JT−2 =1-JT^-2 From Lemma 1, we have the lower bound (1−δ)πjϵ(T)≥K+128KlogTL2(1-δ) _jε(T)≥ K+ 128K TL^2. From the implementation of the exploration stage in Algorithm 2, we know that if Nj≥(1−δ)πjϵ(T)N_j≥(1-δ) _jε(T), then Nj,k N_j,k ≥⌊1+128logTL2⌋≥128logTL2,∀k∈. ≥ 1+ 128\, TL^2 ≥ 128\, TL^2, ∀ k . (14) Therefore, ℙ[∀j∈,∀k∈: [∀ j ,\,∀ k :\; Nj,k≥128logTL2]≥1−JT−2 N_j,k≥ 128\, TL^2 ]≥ 1-JT^-2 Condition on observing sign flip. Now, we want to investigate, at the end of exploration stage, the probability of having the order ξ¯j1,k11,k12≥ξ¯j2,k21,k22 ξ_j_1,k_11,k_12≥ ξ_j_2,k_21,k_22 while the ground truth order is ξj1,k11,k12<ξj2,k21,k22 _j_1,k_11,k_12< _j_2,k_21,k_22. In another word, we want to show the probability of having such flipped order is small. Define the utility and cost differences Δui u_i :=uji,ki1−uji,ki2,Δci:=cji,ki1−cji,ki2,i=1,2, :=u_j_i,k_i1-u_j_i,k_i2, c_i:=c_j_i,k_i1-c_j_i,k_i2, i=1,2, with empirical counterparts Δu¯i:=u¯ji,ki1−u¯ji,ki2 u_i:= u_j_i,k_i1- u_j_i,k_i2 and Δc¯i:=c¯ji,ki1−c¯ji,ki2 c_i:= c_j_i,k_i1- c_j_i,k_i2. In order to apply the Hoefdding’s inequality, define the estimation errors δui:=Δu¯i−Δui,δci:=Δc¯i−Δci.δ u_i:= u_i- u_i, δ c_i:= c_i- c_i. To avoid working with Hoeffding’s inequality on ratios, we apply with the cross-products and define Z Z :=Δu1Δc2−Δu2Δc1=(ξ1−ξ2)Δc1Δc2, := u_1 c_2- u_2 c_1=( _1- _2) c_1 c_2, (15) Z¯ Z :=Δu¯1Δc¯2−Δu¯2Δc¯1. := u_1 c_2- u_2 c_1. (16) Using the triangle inequality together with u,u¯∈[0,1]u, u∈[0,1] and c,c¯∈(0,1]c, c∈(0,1] gives |Z¯−Z|≤ | Z-Z|≤ (|δu1|+|δu2|)+(|δc1|+|δc2|) (|δ u_1|+|δ u_2| )+ (|δ c_1|+|δ c_2| ) +|δu1δc2|+|δu2δc1|. +|δ u_1δ c_2|+|δ u_2δ c_1|. If ξj1,k11,k12<ξj2,k21,k22 _j_1,k_11,k_12< _j_2,k_21,k_22, we have |Z|=|ξj2,k21,k22−ξj1,k11,k12||Δc1||Δc2|≥Δminξ(Δminc)2=L|Z|=| _j_2,k_21,k_22- _j_1,k_11,k_12|| c_1|| c_2|≥ ^ξ_min( ^c_min)^2=L. |Z¯−Z|<|Z|| Z-Z|<|Z| should be a sufficient condition to guarantee no flip between ground truth and estimation. Therefore, we need to bound |Z¯−Z|| Z-Z| with |Z¯−Z|<Δminξ(Δminc)2| Z-Z|< ^ξ_min( ^c_min)^2. Concentration of empirical estimates. For each context-action pair (j,k)(j,k), let u¯j,k u_j,k and c¯j,k c_j,k denote the sample means of utility and cost from Nj,kN_j,k i.i.d. observations. Since uj,k∈[0,1]u_j,k∈[0,1] and cj,k∈[0,1]c_j,k∈[0,1] for each observation s, Hoeffding’s inequality gives ℙ|u¯j,k−uj,k|≥t \| u_j,k-u_j,k|≥ t \ ≤2exp(−2Nj,kt2), ≤ 2 (-2N_j,kt^2), (17) ℙ|c¯j,k−cj,k|≥t \| c_j,k-c_j,k|≥ t \ ≤2exp(−2Nj,kt2). ≤ 2 (-2N_j,kt^2). (18) Set the threshold t:=L82.t:= L8 2. (19) Using Nj,k≥128logTL2N_j,k≥ 128 TL^2 from (14): 2exp(−2Nj,kt2) 2 (-2N_j,kt^2) ≤2exp(−2⋅128logTL2⋅L2128) ≤ 2 (-2· 128 TL^2· L^2128 ) =2exp(−2logT)=2T−2. =2 (-2 T)=2T^-2. For a ground truth order ξj1,k11,k12<ξj2,k21,k22 _j_1,k_11,k_12< _j_2,k_21,k_22, the event ξ¯j1,k11,k12≥ξ¯j2,k21,k22 ξ_j_1,k_11,k_12≥ ξ_j_2,k_21,k_22 can only occur if some context j has fewer than (1−δ)πjϵ(T)(1-δ) _jε(T) occurrences or at least one of the 88 pairs fails the concentration bound. Overall the total failure probability contributed is at most JT−2+16T−2JT^-2+16T^-2. Upper bound on |Z¯−Z|| Z-Z|. If each single estimation error satisfies |u¯j,k−uj,k|<t| u_j,k-u_j,k|<t and |c¯j,k−cj,k|<t| c_j,k-c_j,k|<t, we have |δui|≤2t,|δci|≤2t,i=1,2.|δ u_i|≤ 2t, |δ c_i|≤ 2t, i=1,2. Since utilities and costs are both in [0,1][0,1], the differences satisfy |Δui|≤1,|Δci|≤1,i=1,2.| u_i|≤ 1, | c_i|≤ 1, i=1,2. Applying the triangle inequality: |Z¯−Z| | Z-Z| ≤|δu1||Δc2|+|δu2||Δc1|+|Δu1||δc2|+|Δu2||δc1| ≤|δ u_1|| c_2|+|δ u_2|| c_1|+| u_1||δ c_2|+| u_2||δ c_1| +|δu1||δc2|+|δu2||δc1| +|δ u_1||δ c_2|+|δ u_2||δ c_1| ≤2t⋅1+2t⋅1+1⋅2t+1⋅2t+2t⋅2t+2t⋅2t ≤ 2t· 1+2t· 1+1· 2t+1· 2t+2t· 2t+2t· 2t =8t+8t2. =8t+8t^2. (20) Since |Z|≤2|Z|≤ 2 (as |Δui|≤1| u_i|≤ 1 and |Δci|≤1| c_i|≤ 1) and L≤|Z|L≤|Z|, substituting t=L82t= L8 2 from (19) yields: |Z¯−Z| | Z-Z| ≤8⋅L82+8⋅(L82)2 ≤ 8· L8 2+8· ( L8 2 )^2 =L2+L216 = L 2+ L^216 ≤L2+2L16 ≤ L 2+ 2L16 <L. <L. (21) Therefore: |Z¯−Z|<L≤|Z|.| Z-Z|<L≤|Z|. (22) For all rankings to be correct, we need each individual estimate to concentrate and enough exploration have been made to each context-action pair: ℙall rankings correct \all rankings correct\ ≥(1−JT−2)(1−4JKT−2) ≥(1-JT^-2)(1-4JKT^-2) ≥1−JT−2−4JKT−2 ≥ 1-JT^-2-4JKT^-2 =1−(4JK+J)T−2. =1-(4JK+J)T^-2. (23) ∎ Appendix G Confidence Level Test We present the Confidence Level Test (CLT) for WR-Online in Algorithm 3. At any time t, the algorithm maintains empirical means (u¯j,k,c¯j,k)( u_j,k, c_j,k) and execution counts Nj,kN_j,k for each context–action pair. Using these quantities, we form the empirical marginal reward-cost ratios ξ¯j,k1,k2:=(u¯j,k1−u¯j,k2)/(c¯j,k1−c¯j,k2) ξ_j,k_1,k_2:=( u_j,k_1- u_j,k_2)/( c_j,k_1- c_j,k_2), and adopt a fixed cost ordering so the cost difference in denominator is positive. For two ratios ξ¯j1,k11,k12 ξ_j_1,k_11,k_12 and ξ¯j2,k21,k22 ξ_j_2,k_21,k_22 at each time step, CLT runs a confidence test that checks whether the estimated order is the same as the unknown actual order determined with sufficiently high confidence given the current sample counts. Algorithm 3 iterates over all ordered pairs of ratios; if every comparison passes, the policy stops exploration and switches to exploitation using the current empirical statistics; otherwise it continues exploring. Algorithm 3 Confidence Level Test for WR-Online 1: Input: confidence target δ; empirical means u¯j,k,c¯j,k\ u_j,k, c_j,k\ and counts Nj,k\N_j,k\ 2: Output: flagSucc 3: H←log(2/δ)H← (2/δ); ru(n)←H/(2n)r_u(n)← H/(2n); rc(n)←H/(2n)r_c(n)← H/(2n) 4: flagSucc←true flagSucc← true 5: for all (j1,k11,k12,j2,k21,k22)(j_1,k_11,k_12,j_2,k_21,k_22) s.t. k11≠k12k_11≠ k_12, k21≠k22k_21≠ k_22, c¯j1,k11>c¯j1,k12 c_j_1,k_11> c_j_1,k_12, c¯j2,k21>c¯j2,k22 c_j_2,k_21> c_j_2,k_22 do 6: Δu¯1←u¯j1,k11−u¯j1,k12 u_1← u_j_1,k_11- u_j_1,k_12; Δc¯1←c¯j1,k11−c¯j1,k12 c_1← c_j_1,k_11- c_j_1,k_12 7: Δu¯2←u¯j2,k21−u¯j2,k22 u_2← u_j_2,k_21- u_j_2,k_22; Δc¯2←c¯j2,k21−c¯j2,k22 c_2← c_j_2,k_21- c_j_2,k_22 8: δu1←ru(Nj1,k11)+ru(Nj1,k12)δ u_1← r_u(N_j_1,k_11)+r_u(N_j_1,k_12); δc1←rc(Nj1,k11)+rc(Nj1,k12)δ c_1← r_c(N_j_1,k_11)+r_c(N_j_1,k_12) 9: δu2←ru(Nj2,k21)+ru(Nj2,k22)δ u_2← r_u(N_j_2,k_21)+r_u(N_j_2,k_22); δc2←rc(Nj2,k21)+rc(Nj2,k22)δ c_2← r_c(N_j_2,k_21)+r_c(N_j_2,k_22) 10: Z^←Δu¯1⋅Δc¯2−Δu¯2⋅Δc¯1 Z← u_1· c_2- u_2· c_1 11: B←δu2⋅(|Δc¯1|+δc1)+δc1+δu1⋅(|Δc¯2|+δc2)+δc2+δu1δc2+δu2δc1B←δ u_2·(| c_1|+δ c_1)+δ c_1+δ u_1·(| c_2|+δ c_2)+δ c_2+δ u_1δ c_2+δ u_2δ c_1 12: if |Z^|<2B| Z|<2B then 13: flagSucc←false flagSucc← false 14: return flagSucc 15: end if 16: end for 17: return flagSucc CLT is conservative in practice for two reasons. First, LLM pricing tiers place competing models close in cost, so the gaps Δminc _ ^c are tiny; the test must accumulate enough samples to distinguish these nearly identical costs with high confidence, requiring far more exploration than is practical. Second, the test must pass for every one of the O(J2K4)O(J^2K^4) ratio pairs, so a single hard-to-distinguish pair blocks the switch to exploitation even when all others are well-resolved. Crucially, CLT is only a sufficient condition: the exploitation phase performs well whenever the estimated ordering is approximately correct, even if the test never formally passes. We therefore use a fixed exploration schedule in our experiments. Appendix H Experimental Details H.1 Dataset RouterBench RouterBench contains 36,49736,497 unique queries each paired with responses from 11 different language models of varying sizes and capabilities. In our experiment,we take 10 models from this dataset and their accuracy and cost are shown in Table 3. The queries are drawn from eight diverse datasets(MMLU, HellaSwag, GSM8k, ARC Challenge, Winogrande, MBPP, MT-Bench, and RAG). Table 3: Average performance and cost per query across different models on RouterBench. Model Avg Perf. Avg Cost ($) gpt-4-1106-preview 0.805 7.943e-03 mixtral-8x7b-chat 0.650 4.140e-04 claude-v1 0.648 5.870e-03 llama-2-70b-chat 0.606 1.337e-03 claude-instant-v1 0.590 1.236e-03 gpt-3.5-turbo-1106 0.687 7.086e-04 WizardLM-13B-V1.2 0.539 1.417e-04 code-llama-instruct-34b-chat 0.504 5.499e-04 claude-v2 0.512 6.153e-03 mistral-7b-chat 0.500 1.388e-04 SWE-Bench For the SWE-Bench dataset, we use its verified subset. We analyze the performance and instance cost of 55 models downloaded from the benchmark’s official repository. Specifically, we include the following models • 20250511_sweagent_lm_32b, referred to as sweagent-lm-32b • 20240402_sweagent_gpt4_performance, referred to as sweagent-gpt-4 • 20240620_sweagent_claude3.5sonnet , referred to as sweagent-claude-3.5-sonnet • 20240728_sweagent_gpt4o, referred to as sweagent-gpt-4o • 20250522_sweagent_claude-4-sonnet-20250514, referred to as sweagent-claude-4-sonnet Those 55 models’ average successful rate and instance cost is shown in Table 4. Both datasets are split into training and test sets (50:50) using a fixed random seed for reproducibility, with the same split used across all methods. Table 4: Average performance and cost across different models on SWE-bench. Model Avg Perf. Avg Cost ($) sweagent-claude-4-sonnet 0.666 1.217 sweagent-lm-32b 0.402 1.039 sweagent-claude-3.5-sonnet 0.336 1.714 sweagent-gpt-4o 0.232 2.317 sweagent-gpt-4 0.224 2.418 H.2 Baseline Implementation We provide the details of our implementation for each baseline methods: • FrugalGPT: A cascading method with a per-query budget constraint. To control training time latency, we cap the cascade length to be 22, all other setting uses the default implementation. The cascade parameters are tuned on the training split to meet the target average budget ρ on test set. • CascadeRouting: We implement the method following the original paper, restricted to a cascade length of 2. The estimation strategy varies by dataset: For RouterBench, quality and cost estimators utilize ground-truth statistics with added noise. To ensure a fair comparison with baselines that lack ground-truth access, we adopt the High standard deviation setting as defined in the original work. For SWE-Bench, where we measure instance-level costs, we employ a linear regression model to estimate cost via query embeddings and a logistic regression model to predict quality. • SingleBest: For each cluster j, we select the action k⋆(j)=argmaxk:cj,k≤ρuj,k (j)= _k:\,c_j,k≤ρu_j,k,the action with the highest estimated reward subject to the per-query budget ρ. At inference, the router always chooses k⋆(j)k (j) for queries in cluster j. Budget is enforced only through the fixed average constraint ρ=B/Tρ=B/T, without adaptation over time. Use the same cluster and context-action pair statistics as WR-Offline. Since K-means clustering depends on random centroid initialization, we run five independent seeds (0–44) and report the mean and standard deviation over the resulting cluster assignments. • MetaLLM: We adapt the algorithm from the official implementation, using the same cluster and context-action pair statistics as in other baselines. Actions are selected by UCB with a Lagrangian penalty p≥0p≥ 0 in the reward function to enforce budget adherence. For each budget level, p is tuned via grid search on a held-out validation set (10% of training data), selecting the value whose total validation cost is closest to the proportionally scaled budget without exceeding it. Results are averaged over 5 random seeds (0–44), each controlling action tie-breaking and K-means initialization. H.3 Running Environment Our FrugalGPT experiments were run as Slurm jobs on a Linux GPU node, requesting one NVIDIA H100, while all other baselines were run on Slurm CPU nodes with 4 CPU tasks and 52GB host memory. H.4 Intra-Cluster Variance. The intra-cluster homogeneity assumption (Section 4.1) treats all queries in a cluster as sharing the same expected reward and cost for each model. Table 5 reports the average intra-cluster variance of reward and normalized cost at J=16J=16. Cost variance is negligible on RouterBench and modest on SWE-Bench, confirming that cost discretization introduces little approximation error. Table 5: Average intra-cluster variance of reward and normalized cost at J=16J=16. Dataset Avg. Reward Variance Avg. Normalized Cost Variance RouterBench 0.1920.192 0.000490.00049 SWE-Bench 0.1990.199 0.0650.065 H.5 WR-Offline Experiment Result on SWE-Bench We provide the performance comparison between WR-Online and other offline baselines under end-to-end budget in Figure 6. Figure 6: Performance comparison under end-to-end budget constraints on SWE-Bench. Comparison between WR-Online and offline baselines. Vertical dashed lines represent the fixed cost of collecting the complete training set for offline methods. WISERouter values are averaged over five runs. H.6 Exploration Estimation Accuracy To validate that the exploration phase of WR-Online produces reliable statistics for the subsequent LP routing policy, we compare the empirical estimates u¯j,k u_j,k and c¯j,k c_j,k at the end of exploration against ground truth statistics computed over the full horizon T (J=16J=16, exploration length 4×4× training set). Table 6 reports mean absolute error (MAE) and Pearson correlation across all context–action pairs (j,k)(j,k). Both datasets show high reward correlation, confirming that exploration recovers the relative model ordering required by the LP. Cost estimates are nearly exact on RouterBench and accurate on SWE-Bench, where higher per-instance cost variance makes estimation harder. Table 6: Estimation accuracy of WR-Online exploration phase vs. ground truth statistics (J=16J=16, normalized cost St∈[0,1]S_t∈[0,1]). Reward u¯j,k u_j,k Cost c¯j,k c_j,k Dataset MAE Pearson r MAE Pearson r RouterBench 0.0110.011 0.9970.997 2.72×10−42.72× 10^-4 1.0001.000 SWE-Bench 0.0760.076 0.8960.896 0.0410.041 0.9410.941 H.7 Ablation Study Here we present the hyperparameter tuning and ablation study result performed on the RouterBench dataset. All experiment results are conducted on RouterBench train set with cross validation and the validation set ratio is 20%. Each experiment is runned 5 times and compute the average score. We first examine the sensitivity of our embedding method generated from a commercial API OpenAI’s text-embedding-3-small and an opensource model Qwen3-Embedding-0.6B, Table 7 shows that the result on validation set over 5 runs is relatively stable, suggesting our method is robust towards the embedding methods and vector dimension choice. Table 7: Average reward across different embedding methods and PCA settings (3285 queries, 5 seeds). Embedding No PCA PCA (256 dim) Qwen3-Embedding-0.6B 2951.39 ± 22.83 2951.84 ± 21.27 OpenAI-text-embedding-3-small 2949.65 ± 18.74 2950.84 ± 22.42 We select J=16J=16 as the number of clusters for our K-means clustering method. As shown in Table 8, all values of J achieve similar average reward. However, J=16J=16 attains the highest reward (0.8083) while having the smallest standard deviation (0.0029), indicating the most stable performance across runs. Table 8: Hyperparameter selection for number of clusters J in K-means. Performance is averaged over 5 runs. J Avg Reward per Query 8 0.8083±0.00360.8083± 0.0036 12 0.8079±0.00300.8079± 0.0030 16 0.8083±0.00290.8083± 0.0029 20 0.8082±0.00300.8082± 0.0030 We also examined other density based clustering methods DBSCAN. Table 9 shows results when replacing K-means with DBSCAN. Across all ϵε values we explored, the average reward remains around 0.8080.808, consistent with our K-means results. This indicates that our method is robust to the choice of clustering algorithm and its hyperparameters. Table 9: Hyperparameter selection for DBSCAN ϵε. ϵε Avg Reward per Query 0.2 0.8083±0.00360.8083± 0.0036 0.4 0.8080±0.00290.8080± 0.0029 0.6 0.8084±0.00350.8084± 0.0035 0.8 0.8084±0.00350.8084± 0.0035 H.8 Simulation Experiment Simulation Setup. We consider a synthetic contextual decision-making environment with a finite horizon of T=1500T=1500, J=11J=11 discrete contexts, and K=11K=11 available actions. At each round t, a context j∈1,…,Jj∈\1,…,J\ is sampled independently from a fixed power-law distribution with parameter α=1.0α=1.0, inducing a skewed frequency over contexts reflecting reality. Each context–action pair (j,k)(j,k) is associated with a ground-truth expected reward uj,ku_j,k and expected cost cj,kc_j,k. The reward matrix U∈[0,1]J×KU∈[0,1]^J× K and cost matrix C∈[0,1]J×KC∈[0,1]^J× K are generated once at initialization by sampling entries independently from a uniform distribution on [0,1][0,1], and are held fixed throughout the experiment. These quantities define the expected reward and cost structure of the environment. Observed rewards and costs add noise to its expected value. Budget consumption is tracked using the expected cost cjt,ktc_j_t,k_t to ensure that the workload constraint is applies upon the expected cumulative cost. Budget construction. To characterize the feasible budget range in the simulated environment, we compute reference workload-level budgets based on the mean cost structure. Let cj,kc_j,k denote the mean cost of action k under context j, and let pjp_j be the context arrival distribution. The minimum per-step expected cost is defined as c¯=∑jpjminkcj,k, c= _jp_j _kc_j,k, corresponding to always selecting the cheapest action for each context. Similarly, the maximum per-step expected cost is c¯=∑jpjmaxkcj,k c= _jp_j _kc_j,k, which corresponds to always selecting the most expensive action. For a horizon of T=1500T=1500, these values induce a minimum feasible budget Bmin=T⋅c¯B_ =T· c and a maximum feasible budget Bmax=T⋅c¯B_ =T· c. In our simulation, we obtain the mid-level budget Bmid=12(Bmin+Bmax)=762.58B_mid= 12(B_ +B_ )=762.58, which induces meaningful trade-offs between reward maximization and budget conservation and is therefore used throughout the simulation experiments. Making Bandit Algorithms Budget-Aware. To enable a fair comparison, all baseline methods are adapted to respect the global budget constraint through an adaptive cost constraint. Specifically, at each round t, a baseline policy computes a per-round target cost b/τ,b/τ, where b is the remaining budget and τ is the remaining time step. The policy then restricts its action selection to those actions whose expected cost does not exceed b/τb/τ. If no such action exists, the policy defaults to the lowest-cost action. This mechanism ensures that even baselines that are not explicitly designed for constrained optimization are budget-aware and adapt their behavior over time as budget is consumed. Compared Methods and Evaluation Protocol. We compare WR-Online against several baselines modified with the budget aware mechanism described above, including a random policy, ε -greedy policy [35], and budget-aware LinUCB [24], all equipped with the adaptive average cost mechanism described above. We additionally evaluate a variants of WR-Online when it is provided with the true expected cost value cj,kc_j,k for all (j,k)(j,k), we call such method EFALP-known (same as the ϵε-first ALP proposed in [40]). Both variants use identical reward observations and budget accounting, differing only in their access to cost information. An oracle linear-programming policy with full knowledge of (uj,k,cj,k)(u_j,k,c_j,k) is used to compute the optimal expected reward and serves as the benchmark for regret computation. To ensure a fair comparison, all policies are evaluated on identical context sequences for each random seed. Results are reported with mean and standard deviation over multiple runs.