Near-Optimal Online Deployment and Routing for Streaming LLMs
Authors: Shaoang Li
Jian Li
Venue: ICLR 2026 Poster (2026)
Keywords: online learning
bandits
LLM routing
staged deployment
streaming model arrivals
regret bounds
budget/capacity constraints
Primary area: foundation or frontier models, including LLMs
TL;DR: StageRoute periodically redeploys LLMs and cost-aware routes queries online to track a streaming model frontier with near-optimal regret.

Abstract: The rapid pace at which new large language models (LLMs) appear, and older ones become obsolete, forces providers to manage a streaming inventory under a strict concurrency cap and per-query cost budgets. We cast this as an online decision problem that couples *stage-wise deployment* (at fixed maintenance windows) with *per-query routing* among live models. We introduce *StageRoute*, a hierarchical algorithm that (i) optimistically selects up to $M_{\max}$ models for the next stage using reward upper-confidence and cost lower-confidence bounds, and (ii) routes each incoming query by solving a budget- and throughput-constrained bandit subproblem over the deployed set. We prove a regret of $\tilde{\mathcal{O}}(T^{2/3})$ with a matching lower bound, establishing near-optimality, and validate the theory empirically: *StageRoute* tracks a strong oracle under tight budgets across diverse workloads.

Published as a conference paper at ICLR 2026
NEAR-OPTIMAL ONLINE DEPLOYMENT AND ROUT- ING FOR STREAMING LLMs
Shaoang Li, Jian Li Stony Brook University
ABSTRACT
The rapid pace at which new large language models (LLMs) appear, and older ones become obsolcte, forces providers to manage streaming inventory under a strict concurrency cap and per-query cost budgets. We cast this as an online decision problem that couples stage-wise deployment (at fixed maintenance win- dows) with per-query routing among live models. We introduce StageRoute, hierarchical algorithm that (i) optimistically selects up to Maax models for the next stage using reward upper-confidence and cost lower-confidence bounds, and (ii) routes each incoming query by solving a budget- and throughput-constrrine bandit subproblem over the deployed set. We prove a regret of ((T2/3) with a matching lower bound, establishing near-optimality, and validate the theory em- pirically: StageRoute tracks a strong oracle under tight budgets across diverse workloads.
INTRODUCTION
The proliferation of LLMs has transformed broad array of applications, delivering unprecedented advances in natural- caturalllanguur language understanding and generation (Radford et al. [019 Brown et al. 2000)] Wang al. 2023b [2023 Chowdhery et al. 22023] Touvron et al. 2023). Yet LLMs differ markedly in both performance and cost: some offer state-of-ther the-art capabilities at premium, while others are more affordable but less effective. Practitioners therefore face continual accuracy-expendee
tradeoff when deciding which models to operate and when to use them. This has motivated I.I. routing (Ding et al. 2024 Hu al., 2024). where a system chooses, query by query, which model to invoke to maximize task quality under cost constraints. However, focusing solely on per-query routing overlooks a more fundamental decision that precedes it: which models are deployed at all.
In practice, the operational landscape is unusually fluid. New models arrive continuously with dis- tinct accuracy, latency, and pricing profile (Feng et al. 2025), while production systems must respect hard limits such rate ceilings and deployment quotas. For example, Azure OpenAl Service caps each resource at 32 standard and fine-tuned deployments by default, and enforces model-specific rate ceilings (e.g., for GPT-441: 1, 1,000 requests per minute (RPM) and 1M tokens per minute (TPM)) dynamic model pool and strict operational caps re-
(Microsoft Azure 2025). This confluence casts the problem into two timescales: a slower stage-wise deployment process that decides which models stay alive under concurrency cap, and a faster per-query routing process that assigns each request among the currently deployed models while meeting budget and throughput constraints. The deployment choice is foundational, since it determines the entire action space for any routing policy. Table maps recent LLM routing systems to three axes and highlights gap in current approaches.
We study this setting as an online decision problem that couples two intertwined choices (Figure I): (1) stage-wise deployment at fixed update points, where the operator decides which models to deploy for the next stage subject to a hard concurrency cap and deployment costs. This high-stakes decision defines the action set for the subsequent execution of (2) per-query routing, where each incoming query is sent one of the currently deployed models to maximize quality while obeying long-term cost budget and modem throughput limits. Unlike approaches that assume a static model pool or rely fully offline retraining, active-set replacement: admitting a newcomer may require evicting an incumbent for the rest of the stage. This mirrors real service constraints while enabling continual adaptation.
framework admits streaming arrivals of new LLMs and enforces

---

Published as a conference paper at ICLR 2026
G97-49
Drm Mach
Drak-
Continouus rollouts
Map 2012
Decanbee 1,204
Je
Fébaay
Stage-olln zlle
O R
Deployed
pool
Upbrr
Wetarieea
Time horizon
Quay
2
9
10
11
12
13
14
15
8
8
8
8
StageRoune
Users
The St StageRoute workflow. Newly released LLMs (green) continually enter the can- didate pool. At each scheduled update point, St atageoou deploys up to Mmax models (blue). Between updates, each query is routed among the current deployment (orange). This two-level loop assimilates fresh models, enforces cost/throughput constraints, and adapts routing in real time.
Figure 1:
Three features make this problem technically distinct. First, the hard concurrent- depploeentteellmmentt cap induces an irrevensible exploration-exploiaae dropping a known, reliable one for an entire stage. Second, decisions occur on two timescales: infrequent, strategic deployment choices constrain frequent, tactical per-query routing. Third, the system must jointly respect a long-term cost budget and per-model throughput limits while select- ing small operational subset under uncertainty. Classical multi- armed bandits (MAB), budgeted formulations (BwK). combinatorial bandits (CMAB), and standard streaming bandits each capture parts of this picture, but none natively address the combination of dynamic availability, staged com- mitment, and an explicit concurrency cap on the active set.
tradeoff: activating an uncertain model can mean
To address these challenges, we introduce StageRoute, algorithm that mirrors the problem's hierarchy (Figure D]. At each update boundary, a deployment phase selects the active set for the next stage using optimistic estimates of model quality (UCB) and conservative estimates of cost (LCB), honoring the global budget, per-model throughput limits, and the Mmax concurrency cap. Within the stage, each query triggers a routing phase: linear program over the currently deployment returns a distribution that maximizes estimated quality under the same constraints, and the query is dispatched by sampling accordingly. This two-level loop links strategic deployment to tne-grained, adaptive routing, allowing the system to assimilate new information both across and within stages]
Our contributions in this paper are summarized as follows:
Problem formulation. To our knowledge, we are the first to formalize the online LLM deployment and routing problem with streaming arrivals, explicitly modeling a hard concurrency cap. one- time deployment costs, per-model throughput limits, and a long-term cost budget, with stage-level commitment and per-query routing.
Algorithm. We introduce StageRoute, which (i) selects an active set at each update using optimistic performance (UCB) and conservative cost (LCB) estimates under the budget, throughput limits, and the Mmax concurrency cap. and (ii) routes each query by solving thrguputh LP over the currently deployed models. The design modular: the routing step can incorporate contextual estimators when features available, while the deployment step remains unchanged; throughput limits naturally throttle load to mitigate latency spikes.
Theoretical guarantees. We prove a regret bound of ((MMaxx KT) + (NTT/(M max K)). where T, K, Mmax, N are the numbers queries, update stages. the concurrency cap and arriving models, respectively. The first term captures the statistical learning cost of routing within the de- ployed set; it grows with the number of active models M stages K, and horizon T. The second term is structural model-discovery bottleneck that quantifies the difficulty of discovering strong newcomers when only Mmax models can live across stages as N models arrive. Balancing the
Relattiee to nearby bandit frameworks: static-pool routing assumes fixed arms; BwK models consumable budgets but not stage-level active-set replacement; CMAB selects superarms from fixed base set without streaming arrivals or stage commitment; streaming bandits allow arrivals but do not couple stage-level support selection with per-query routing under both hudget and per-model capacity. See Appendix for more details.
2

---

Published as a conference paper at ICLR 2026
Table I: Comparison of LLM routing frameworks. StageRoute is the first to address the full real-world setting: a dynamic model pool with streaming arrivals, paired with dynamic stage-wise wise deployment under concurrency cap (Mmax) and cost- and throughput-aware routing.
Streaming LLM Models
Dynamic Deployment (with Mioc cap)
Cost & Budget Aware
Throughput Limits
Approach
Source
LLM-Blender
Jiang et al. 2023
AutoMix
Aggarwal a 2024
Hybrid-LI.M
Ding ct al. 2024
Zooter
Lu ct al 20.4
RouterDC
Chen el al 2024
TensorOpera Router
Sirpelis ct a. 2024
RouteLLM
Ong et al. [225
MESS+
Woisetschläger et 2225
UniRoute
Ditkritumm 2025
CSCR
Sturkavand 2025
StageRoute (ours)
This paper
two yields a near-optimal ((T2/3) order, and we give a matching D(T2/5) lower bound via a staged- arrival construction. Analytically, use LP-duality sensitivity with explicit support (active-set) constraint and a regret decomposition that separates routing and deployment across stages.
Empirical evaluation. Simulations show StageRoute tracks strong oracle under tight budgets and is robust across key parameters. We evaluate on true per-query scores and costs (RouterBench) across diverse queries, tasks, and languages, demonstrating effectiveness in realistic settings.
SYSTEM MODEL
We study an online LLM routing framework: at each round I, query arrives and must be routed to suitable LLM. New models may appear at any time, yet they can be activated only at discrete deployment intervals (Figure Ip. We describe each component of the model in detail.
Rounds (Queries). Let T denote the total number of user queries, indexed by [T] = {1, T). At each time step & E [T'] a query arrives and is immediately routed to an LLM m, chosen from the currently deployed models according to the algorithm's 's policy.
LLM Pool and Deployment Schedule. Let M₁ be the set of all LLM models that exist and could, in principle, be deployed by time t. Each model m has an availability time tmi hence m E M exactly when /. 2 lmn- Deployment changes occur only at discrete intervals, schedule determined by the algorithm. The algorithm partitions the time horizon T into K equal-length stages, where K tunable hyperparameter of the algorithm. Fach stage thus consists of T/K rounds (assuming T is divisible by K). The start of stage k is = (k: 1)T K + k = 1,..., K. Let Maax be the concurrency cap, i.e., the maximum number of models that can be deployed simultaneously. At each update point Tke the algorithm A selects a deployed set (AA S .M, such that [Dx( S Mmax, which then remains fixed for all t [Tk Tk+1). Queries arriving during that stage must be routed to models in the active set (A). Thus M, is the available pool at time I, while (A) is the active subsel that can actually serve queries during stage k.
Operational Performance and Cost. An L.M's per-prompt quality varies with the input. However, over long time horizon, it can be reasonably modeled as a random variable centered around stable mean (Ding et al. 2024). Formally, each model m has an unknown performance distribution um (-) supported on [0, IJ. When m is selected at time t, the observed score r E [0, 1] is drawn from p'm (.) with mean Pm. Ezzu,..) ())=)).)()))
[z]. Invoking model m on a query also incurs an operational cost Cma. (in)
that combines: (i) Input Cost: Cra (# tokens of input at time t) X Pin, where Pin is the per-token
input price: (ii) Output Cost: (out) = (#tokens of response by m for query t) x Pout, with output
length drawn from a model-specific distribution Em and unit price Pout-
Thus the total cost is Cm,- (in) + (out.) Because the output token count (out) depends on the specific model and query and is sampled from Em (-), the total operational cost Cm, for a query handled by model m, is itself random variable. Operational cost Cm, is inherently bounded by per-token pricing and practical limits on sequence length and generation (e.g., context-window and token caps). Hence we assume Con E [ei, 02) for known constants 0 < ci S C2 co.
3

---

Published as a conference paper at ICLR 2026
Constraints: Budget and Throughput. When query arrives time t, with stage index k such that Tк S < Th+1, the algorithm A selects a model m, E (x()). It then observes the reward rt Vm,()) (-) and incurs cost C.z.. The goal is to maximize average reward subject two main
constraints:
(1) Budget constraint: E Ei= Cm. <b+ (1). We use average constraint instead of hard budget constraint because for long-running systems, it provides degree of flexibility. From a theoretical analysis perspective, since the estimation errors for both performance and cost are gov- emed by the same concentration inequalities, the expected budget violation is upper-bounded by the order of the performance regret. This makes the average cost constraint asymptotically equivalent to hard constraint for near-optimal algorithm.
(2) Per-model throughput limit: For each deployed LLM model m. we specify throughput limit Omn Let pe (m(m be the probability that the routing policy assigns the query at time to model m. While lies stage k, the policy must satisfy (m(m) S O.m: vm E DD (A). This constraint caps the instantaneous load share each model may receive. For a deterministic decision ma. where p.(m.) = 1. the requirement reduces to Om, 2 1. Such limits reflect real-world restrictions like API rate limits (RPM/TPM), bandwidth, or licensing, preventing any single model from being overwhelmed. Hence the deployed set's s aggregate throughput must be sufficient to serve every arrival, a condition formalize next.
Assumption 1 (Feasibility), The constraints are feasible. At every time t, there exists subset S S M, with |S| S. Mmax such that Emes 4mm 2 The budget b also large enough admit non-trivial routing policy. When required, we assume Slater's 's condition holds, guaranteeing strong duality for the associated optimization problems.
Performance Maxinization and Regret. The goal is maximize the expected cumulative per-
formance, E Pm,] subject to: (i) Deployment Choice: At each update Tke select a deployed set (A) S Mr with (LA) < Mmaxi (ii) Model Selection: For t E [Tk, Tk-1), choose my E (e(A) using probabilities Pe (m) that sum to 1; (iii) Throughput Constraint: Ensure pr(m) S 0m for every deployed model m; and (iv) Budget Constraint: Maintain E[} Σ Cm.] S b+ o())
We measure the online policy's 's performance against optimal offline benchmark. The foundation of this benchmark is the Optimal Performance Rate Function, (bb,S) Given any candidate model set S and per-query budget b, let (ib, S) denote the maximum expected reward per query, which serves as an upper bound for any algorithm operating under these constraints:
V) = max
Σ (mp(mm)
Σ mES
B[cmlp(m) S b, Σ p(m) = 1,
PEA(S)
MES
mES
0 0 p(m) S am for m E S, |supp(p)] & Mmax
Here, A(S) is the set of probability distributions over S: p(m) is the probability of selecting model m;; and E[[m]] is its expected cost. The support constraint (supp(p) MMaax limits the number of models with positive probability to Mmax. capturing the combinatorial selection of the best Mmax models to use for routing from the entire available pool Mr.- If no feasible distribution exists or (S = Ø). we set S)) O.
The varyyng offline optimum is OPT" = = k= (7+41 -R)- ((b. where (Tk+1 Tk) is the length (number of queries) of stage k. The regret of an online policy A is
Regret( = OPT
Pme
i.e. the expected performance gap between A and the clairvoyant benchmark, where the expectation is over the algorithm's 's random choices and outcome variability.
3 STAGEROUTE: STAGE- LLM DEPLOYMENT AND ROUTING
We introduce St ageRoute (Algorithm D a two-level hierarchy that unifies deployment and per- query routing in algorithm: (i) Strategic layer. At each discrete update point 7k, the algorithm
4

---

Published as a conference paper at ICLR 2026
Algorithm StageRoute: stage-based LLM deployment (active-set selection) and online query routing
Require: Update points ( 7k ); budget b; concurrency cap Mmax
1: Initialize: Prior parameter estimates; 7D +- 0; (a() 0
2: /Stage-wise Deployment Phase:
for k K do
4: Incorporate newly available models {m fm S < mm + (Tx - Th 11); initialize their
parameters
5:
Solve DeployOPT 3 for d' and set (A < {m d > 0}
6: / /Perr-query Routing Phase (for query at time l):
7:
for |. == T. 7k++1 - (or to 7 if k = K) do
8:
Compute routing distribution P; by solving RouteOPT
Sample m, ~ p. and route the query to it 10: Observe reward rg and cost c;; update statistics for m,
9:
11: end for
12:
end for
decides which models to deploy, adapting to newly available LLMs while respecting the budget and operational constraints. (ii) Tactical layer. Between updates, routes every incoming query in real time among the currently deployed models. The system starts with prior parameter estimates, an empty unexplored-mon model list, To = 0, and an empty initial deployment (.()). then proceeds through K stages, and at the start of each stage & (t rk), the algorithm executes two phases in sequence: model deployment followed by request routing.
Model Deployment Phase (Stage Start). At each update point 7k: StageRoute first incorporates any newly available models (those with Tą-1 < fm S тк) and initializes their parameter estimates. With the enlarged pool Mr StageRoute solves the deployment optimization in Eq. (3) to pick the models for stage k:
DeployOPT:
max de dEA(M.))
Σ
dm
Σ mEM-2
c dm Sb.
Σ
dm 1,
McM
mEMrr
(3)
0 S dm S Om for MMa supp(d)) min(Mmmas |M
This optimization problem is a Mixed-Integer Program (MIP). The combinatorial nature arises from the cardinality constraint on the support of d, which limits the number of active models. standard way to formulate this is by introducing binary activation variable 2m E {0, 1} for each model. The full stage-k deployment problem can then be written as:
max d,
I'm dmn:
s.t.
Σ c dm Sb
> dm,=1, =1, 0. dm S am
mEM-
Σ 2m min(Mmaxe MM 1), 2m E {0,1].
Here, the binary variables pm explicitly select which models are live for the stage, while the contin- uous variables d,, represent an optimistic deployment mix. The solution to this MIP d maximizes an optimistic performance surrogate using UCBs for rewards (uI)) and LCBs for costs (c/2), which are derived from data up to тк- Specifically, let (T.(TT) and (Tx) ) be the empirical mean reward and cost of model based NT. selections observed up TR. Define the UCBs and LCBs
H fm : projjo.11 (Am (Tk) + 2frad(Am (T)) N (T&) + 1)),
(4)
2 proj .eal (cm (Tx) 2 2/ (Tk)) Nm (Tk) + 1)),
(5)
where projia. is projection function onto the interval [a, b] and frad(o, n) / 22 (for some y 0) is confidence radius function.
The deployment optimization in Eq. 33 maximizes expected utility subject to the budget b, per- model throughput limits O'm and the concurrency cap |supp(d)] max,, [M,, l). Its solution
5

---

Published as a conference paper at ICLR 2026
d' determines the active set for stage k: (a(A) {m E Mr. di >2>0 0}.
Crucially, the values dm are not used as routing probabilities; they serve only to select the most promising feasible models. The deployment set (A) remains fixed until the next update point
Tk+1-
Request Routing Phase (Intra-Stage). For each query arriving at time E [Tk. Tk+ StageRoute performs four steps: (1) Routing LP. solves the linear program (LP) Eq. 7 to compute the optimal routing distribution P. (pt (m))) over the currently deployed models DR (A).
RouteOPT:
max (AE)(D((A)
Σ
I Pmpee (m)
Σ
chPe(m) Sb,
mED (A)
mEDx(A)
(7)
Σ
Pr(m)
1,0 5 (m(m) am for m E (x()).
(ED((A)
This LP maximizes the expected reward by combining the current UCBs for reward (n and LCBs for cost (ch)) while enforcing the per-query budget b (through the cost bounds) and each model's throughput limit Omm (2) Model selection. Sample mh Pi and serve the query. (3) Feedback. stageRoute observes the realized reward rt and cost cs. (4) Update. Refresh Pm,, Cm,, Nm, and recompute " eh,, for subsequent routing and the next deployment decision.
Algorithmic Innovations. While St ageeRute builds on the principle of "optimism in the face of uncertainty". its architecture is tailored to dynamic LLM deployment and departs from standard bandit formulations. First, it imposes a hierarchical decision structure that mirrors operational prac- tice: the deployment decision is high-stakes, combinatorial choice whose consequences persist for an entire stage, a form of long-term commitment absent from standard, per-round bandits. Second, staged updates create structured delay in acting feedback. Information about non-deployed models cannot influence decisions until the next stage, inducing exploration exploitation trade- off that requires anticipating performance over the whole stage, not just the next round. Finally, StugeRoute decouples deployment from routing execution: DeployOPT determines only the active set (AA),, while the per-query policy is recomputed online via RouteOPT. This separation enables rapid query-level adaptation even when the underlying infrastructure remains fixed during stage.
ssploration-exploiaatioo
THEORETICAL RESULTS
We analyze StageRoute (Algorithm I by deriving upper bound on its cumulative regret and matching lower bound that applies to any online algorithm for this problem. Together, these results show that atageRot e is near-optimal in the worst case.
4.1 UPPER BOUND
Theorem 1. Consider St aggeRute running for T queries divided into K stages, with concur- rency cap Mmax and N = MMT total models arriving over time. Set the confidence parameter to 7 (()g(NNT/)) to obtain overall confidence 1 8. Then the expected regret is bounded by:
Regret(stageRoute) < ( MmaxxXTTlgg//
NT
+
M K
Choosing K =TT1133 and Minax = S2N22122) yields Regre((stageRoute)) < δ (N1/372/3).
The two terms in the bound reflect complementary sources of difficulty. The first term, OmM is the statistical learning cost of routing within the deployed set. The second term, (MNT/(Mmarrii is structural model-discovery bottleneck: when only Musx models can be active at time across K stages, exploration throttled. Strong late-arriving models can be missed unless sufficient deployment slots and update frequency are provisioned. Balancing these two terms gives the near-optimal ((72/3) rate, which matches the lower bound in Theorem

---

Published as a conference paper at ICLR 2026
Practical guidance. The bound yields an actionable rule: to approach the optimal rate, set the number of stages to approximately K R T1/3 (implying stage length of T2/3) and provision concurrency cap max large enough to track new arrivals (ideally Mmax x N22/3 when feasible). However, updating more frequently (K > T1/$) is also ill-advised. Even if it does not increase regret, it cannot offer further asymptotic improvement due the lower bound, while needlessly incurring significant computational and operational overhead with each additional deployment stage. This underscores that exploration capacity. defined by the concurrency cap and update frequency, is itself scarce system resource to be optimized. Relying on only few "top" models is provably suboptimal in dynamic model pool.
Why existing analyses do not apply. Classical MAB and BwK typically assumee per-round choices from a static set and lack a hard concurrency cap; CMAB selects superarms from fixed base set and does not model stage-level commitment; streaming bandits allow arrivals but do not couple stage- committed deployment with budget and per-model throughput constraints. Our setting is distinct due to: (i) concurrency cap that explicitly constrains the support of the deployment optimization, (ii) stage-committed deployment that induces a structured delay in acting on new information, and (iii) the simultancous enforcement of long-term budget and per-model throughput limits.
Proof ideas and new technical elements. Our proof introduces a virtual optimal deployment set to bridge the offline benchmark and the online policy, yielding clean regret decomposition into stage- level deployment regret and intra-stage routing regret. The routing term is handled with standard confidence arguments. The deployment term requires two new ingredients: (a) quantification of the model-discovery bottleneck caused by the limited concurrency cap and discrete updates (showing how the .T (MMaxxx term arises), and (b) support-aware sensitivity analysis of the deployment LP (via its dual). bounding how UCB/LCB estimation errors perturb the optimal active set under the concurrency constraint. Together, these yield Theorem I These elements differ fundamentally from standard parming-reeree analyses and may inform further work on staged, combinatorial online decision problems. Complete details appear in Appendix C
4.2 LOWER BOUND
Theorem 2. For any online policy A and any choice of update frequency K and concurrency cap Mmaso there exists a stochastic, piecevise-stational LLM-routing instance such that the expected regret against the time-varying oracle satisfies
Regret(A) 2 2/3
This 2(T2/3) bound captures the intrinsic difficulty of continually tracking the best model as ca- pabilities evolve. The construction mirrors real L.LM ecosystems: in each batch (newer) model marginally stronger than the rest, and the identity of the strongest model changes over batches. Importantly, the baseline level of rewards also drifts upward over time, reflecting that even "weaker" new releases can outperform old ones. This is unlike classic lower bounds that keep suboptimal arms at fixed mean (e.g., 1/2) and change only the identity of the best arm.
Proof ideas and Intuition. We construct a family of "streaming" instances that mimics a live LLM marketplace: the time horizon is split into approximately T1/3 epochs, in each batch different model is slightly better than the others, and the whole performance frontier drifts upward across batches (so even "weaker" newcomers can surpass yesterday's best). We choose the batch length and performance gaps so that any algorithm cannot reliably identify it with the limited information available before the epoch ends. Because the identity of the best model changes next batch, infor- mation gained earlier quickly goes stale. Any policy is thus forced into repeated "partial discovery", incurring a nontrivial loss in each batch, and summing over all batches yields total regret on the order 2/3 Full details are given in Appendix D
New technical elements. not use a fixed baseline where only the identity of the best arm flips. Here the entire frontier drifts, matching LLM practice; and (ii) the hardness persists even if the system redeploy every round and keep all models live, so the rate is intrinsic to tracking an evolving frontier, not an artifact of staging or capacity limits.
Two aspects differ from standard MAB/CMAB lower bounds: (i) we do
7

---

Published as a conference paper at ICLR 2026
(a) The decision heatmap of StagcRoute.
(b) The decision heatmap of the optimal Oracle.
Figure 2: Comparison of decision heatmaps for StageRoute e and the Oracle with Mmax = 5, 0.001, update interval=1000. Darker colors indicate higher selection probabilities.
Discussion. Theorem 2 conveys practical message: sets, there is a fundamental rate limit on how quickly a system can keep up as the performance frontier shifts. Our upper bound matches this lower bound up to logarithmic factors with respect to the number of queries T, establishing near-optimality.
with aggressive adaptivity and large live
EXPERIMENTS
Datasets and Candidate LLMs. We evaluate on RouterBench (Hu et al. 2024), covering 36,497 queries across eight datasets in English and Chinese (commonsense, knowledge, dialogue, math, code, and RAG). Each query includes responses from 11 LLMs with per-query scores and costs. Full dataset descriptions and the model list appear in Appendix
Baselines. We compare StageRoute against three baselines. The first is oracle that, with full knowledge of all performance and cost statistics, always selects the optimal deployment set, serving as upper bound achievable performance. The second is greedy strategy that, at each update point, selects the Mmax models with the highest utility, computed as the ratio between the UCB of performance and the LCB of cost. This approach can be viewed where selection is based on the UCB of the utility metric. The third baseline is a uniform sampling strategy, which randomly selects models for deployment and may substantially exceed the budget. To our knowledge, no existing methods are specifically designed for this LLM deployment problem.
variant of UCB algorithm
Implementation Details. We simulate total of T 36,497 rounds. In each round, query is sampled uniformly at random from the dataset. The algorithm then selects model serve the query and subsequently receives the performance score and asso- ciated cost. Initially. models are available. Thereafter, for ev- ery 5,000 queries, new model becomes eligible for deployment,
StageRoute
Cumulative Regret
Greedy
Random
following the release-date ordering Table 3] We set the con- fidence parameter 7 0.1. All reported results are averaged over 10 independent runs. The experiments involve solving mixed- integer programming (MIP) subproblems using the Gurobi Opti- mizer 1v12.0.1, academic license) on a machine equipped with a 12th Gen Intel(R) Core(TM) i9- 19-1290 processor.
Query Number K20*
Figure 3: Cumulative regret.
Computational Overhead. Our two-stage design keeps the computational overhead low, allowing the entire experimental to complete in under 10 minutes. The deployment MIP is solved only
8

---

Published as a conference paper at ICLR 2026
infrequently on small instances (taking sub-seconds), while the per-query routing involves tiny LP over the active set that executes in milliseconds. Therefore, using either Gurobi or an open- source solver (e.g., CBC, GLPK, HiGHS) is feasible. Furthermore, since parameters change only slightly between iterations, we can leverage warm-starting to further accelerate computation. For the routing L.,, can provide the prior active set as an initial feasible solution (MIP start), given the minimal changes the candidate pool (Zhang al. 2025a).
reuse the previous basis or solution; similarly, for the deployment MIP,
Overall Performance. We first present the main results under a representative setting (Mmax 5, 0.001, update interval=1000). and then conduct detailed sensitivity analysis across key hyperparameters. Figure shows the cumulative regret under this default configuration. Across all settings we test (see Figure | for full overview), our algorithm exhibits consistently slow regret growth, substantially outperforming the baselines. Notably, while the uniform sampling strategy appears to outperform the greedy baseline some cases, this is an artifact of its tendency to signifi- cantly overspend the budget, issue we will analyze further in the performance-cost evolution.
Optimal Model Set Identification. As our work emphasizes the importance of deployment, we first analyze whether StageRoute can identify the optimal model set. Figure 2 compares the decision probabilities of StageRoute and the Oracle under the representative setting mentioned above. The horizontal axis represents deployment intervals, while the vertical axis (bottom to top) corresponds to the model arrival order. It is evident that when a new model arrives, StageRoute initially explores it before quickly converging the new optimal model set, closely mirroring the Oracle's behavior. This confirms that our deployment strategy is effective at tracking the optimal available model set.
Performance-Cos
Evolution. To further validate our al- the performance-
gorithm's 's efficiency, cost trajectory for each algorithm, again under the same representative setting. Colors transition from blue (initial stages) to red (final stages). The figure shows that, except during initial exploration and periods when new mod- els arrive, the operating points of our algorithm closely track those of the Oracle. contrast, the greedy strategy proves overly conservative, while uniform sampling con- sistently violates the budget for suboptimal performance. These observations reinforce our central claim: select- ing a high-quality set of models for deployment is funda- mental achieving efficient routing, and St atutt successfully balances high performance with strict budget adherence.
0479
0.00
6435
0089
0535
1600
60025
00000
66000 00025
Auerage Conl Query cyclel
Figure 4: Performance-cost evolution of different algorithms.
Sensitivity Analysis. We now analyze StageRoute's 's sensitivity to key hyperparameters.
(1) Impact of Mmax- Figures 5a and 5b present results for different M values under budget of 6 = 0.001 and an update interval of 1000. The results demonstrate that StageRoute adapts well to this parameter, maintaining robust performance across all settings.
(2) Effect of Deployment Update Interval. Figures 3 5c and 5d illustrate the impact of varying the deployment update interval with Mmax 5 and b 0.001. An interval of 1000 rounds yields the lowest regret, highlighting the importance of selecting an appropriate update frequency.
(3) Effect of Budget Constraint. Figures 3 and 5e compare performance under different budget constraints. Counterintuitively, a more relaxed budget leads to higher regret. This phenomenon can be attributed to two factors. First, a larger budget also raises the performance of the Oracle, making the benchmark more challenging. Second, use fixed confidence radius 7 for all settings; in practice, increasing y in proportion to the budget may be beneficial.
Extending to State-of-the-Art Models. To verify that our StageRoute framework applies to the latest, most powerful models, we conduct additional simulations incorporating recent LLMs. These results, detailed in Appendix confirm that St ageRRot continues to achieve minimal regret.

---

Published as a conference paper at ICLR 2026
Gremy
Denry
CaTRATT Regret
CymAAt Rooret
Quey Mtmber
Cuary Namber
Quey Mumber
Quary Namber
Query Marber
Mmax
(b) Mmax
(c) 500 rounds.
(d) 2000 rounds.
(e) b=0.002.
Figure 5: Cumulative regret under varying hyperparameters.
The default setting is Mmax 5,
update interval 1000 rounds, and b 0.001 (Figure
CONCLUSION
In this paper, we introduced StageRoute, novel framework for online LLM deployment and routing. We are the first to formalize this problem in dynamic setting with streaming LLM model arrivals, addressing the challenge selecting an optimal deployment set under a strict concurrency cap. Our algorithm manages deployment at discrete stages while tactically routing queries in real time, respecting both budget and per-model throughput limits. We established the near-optimality of our algorithm with theoretical analysis, including matching upper and lower bounds, and demon- strated its practical effectiveness through extensive experiments on real-world benchmarks.
ACKNOWLEDGEMENTS
This work was supported in part by the National Science Foundation (NSF) grants 2148309, 231 2315614 and 2337914, and the National Institutes of Health (NIH) grant IR01HL1841394 and was supported in part by funds from OUSD R&E, NIST, and industry partners as specified in the Resilient & Intelligent NextG Systems (RINGS) program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies.
ETHICS STATEMENT
This research focuses the operational efficiency of LLM systems. By making deployment and routing more cost-effective, our work can broaden access to AI technologies and reduce energy consumption. However, we acknowledge that increased accessibility may also lower the barrier for malicious use of LLMs. Our framework does not mitigate the inherent risks of language models, such bias or misinformation generation, and should be implemented alongside robust safety and content moderation protocols.
REFERENCES
OpenAl (2023). GPT-4 technical report. CoRR, abs/2303.08774, 2023.
Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proceedings of the 30th Conference on Learning Theory, pp. 39-75, 2017.
Arpit Agarwal, Sanjeev Khanna, and Prathamesh Patil. A sharp memory-regret trade-off for multi- pass streaming bandits. In Proceedings of the 35th Conference on Learning Theory, pp. 1423- 1462, 2022.
Pranjal Aggarwal, Aman Madaan, Ankit Anand, Srividya Pranavi Potharaju, Swaroop Mishra, Pei Zhou, Aditya Gupta, Dhecraj Rajagopal, Karthik Kappaganthu, Yiming Yang, Shyam Upadhyay, Manaal Faruqui, and Mausam. Automix: Automatically mixing language models. In Advances in Neural Information Processing Systems 38, 2024.
Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Conference Economics and Computation, pp. 989-1006. ACM, 2014.
10

---

Published as a conference paper at ICLR 2026
Sepehr Assadi and Chen Wang. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-an aamee bandits. In Proceedings of the 52nd Symposium on Theory of Computing, pp. 1237-1250, 2020.
Peter Auer, Nicolo Besa-Bianchi and Paul Fischer. Finite- Time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2):235 2002.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, al. Program synthesis with large language models. arXiv preprint (axxxx:218.0077: 2021.
Moshe Babaioff, Shaddin Dughmi, Robert D. Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply. ACM Trans. Economics and Comput., (1)::4:14::266 2015.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In Proceedings of the 45th Symposium on Theory of Computing, pp- 207-216. IEFE, 2013.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. Bandits with replenish- able knapsacks: the best of both worlds. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, and Ariel Herbert- et al. Language models are few-shot learners. In Advances in Neural Infor- mation Processing Systems 33, 2020.
Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. In Proceedings of the 22nd Con-
ference on Learning Theory, 2009.
Lingjiao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.00 13330550577666 16,, 2023.
Lixing Chen, Jie Xu, and Zhuo Lu. Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. In Advances Neural Information Processing Systems 31, pp- 3251-3260, 2018
Shuhao Chen, Weisen Jiang, Baijiong Lin, James T. Kwok, and Yu Zhang. Routerde: Query-based router by dual contrastive learning for assembling large language models. In Advances in Neural Information Processing Systems 38, 2024.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. Proceedings of the 30th International Conference on Machine Learning, volume 28, pp. 151-159, 2013.
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. Chatbot arena: An open platform for evaluating Iims by human preference, 2024.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, and Sebastian Gehrmann et al. Palm: Scaling language modeling with pathways. J. Mach. Learn. Res., 24:240:1-240:11 2023.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try the ai2 reasoning challenge. arXiv preprint arXiv: 1803.05457, 2018
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichir Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2 10. 14168, 2021.
Xiangxiang Dai, Jin Li, Xutong Liu, Anqi Yu, and John Lui. Cost-effective online multi-llm selec- tion with versatile reward models. arXiv preprint arXiv:2405. /65557775 2024.
11

---

Published as a conference paper at ICLR 2026
Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks V. Lakshmanan, and Ahmed Hassan Awadallah. Hybrid LLM: cost-efficient and quality- query routing. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, Barret Zoph, Liam Fedus, Maarten P Bosma, Zongwei Zhou, Tao Wang, Emma Wang, Kellie Wehster, Marie Pellat, Kevin Robinson, Kathleen Meier-Hellstern, Toju Duke, Lucas Dixon, Kun Zhang, Quoe Le, Yonghui Wu, Zhifeng Chen, and Claire Cui. GLaM: Efficient scaling of language models with mixture-of-experts. In Proceedings of the 39th International Conference on Machine Learning, pp. 5547-5569, 2022.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter 1-120:39, 2022.
models with simple and efficient sparsity. J. Mach. Learn. Res.,
Tao Feng, Yanzhen Shen, and Jiaxuan You. Graphrouter: A graph-based router for LLM selections. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Hengquan Guo and Xin Liu. On stochastic contextual bandits with knapsacks in small budget regime. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Neha Gupta, Harikrishna Narasimhan, Wittawat Jitkrittum, Ankit Singh Rawat, Aditya Krishna Menon, and Sanjiv Kumar. Language model cascades: Token-level uncertainty and beyond. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In Proceedings of the 9th International Conference on Learning Representations, 2021.
Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shriyash Kaustubh Upadhyay. Routerbench: benchmark for multi-LLM routing system. In Agentic Markets Workshop at ICML 2024, 2024.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Ad- versarial bandits with knapsacks. In Proceedings of the 51st Symposium on Theory of Computing, pp. 202-219. IEEE, 2019.
Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. Llm- blnnbbender: Ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 14165-14178, 2023.
Tianyuan Jin, Keke Huang, Jing Tang, and Xiaokui Xiao. Optimal streaming algorithms for multi- armed bandits. In Proceedings of the 38th International Conference on Machine Learning, pp.
5045-5054, 2021.
Wittawat Jitkrittum, Harikrishna Narasimhan, Ankit Singh Rawat, Jeevesh Juneja, Zifeng Wang, Chen-Yu Lee, Pradeep Shenoy, Rina Panigrahy, Aditya Krishna Menon, and Sanjiv Kumar. Uni- versal model routing for efficient LLM inference. CoRR, abs/2502.08773, 2025.
Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In Proceedings of the 32rd Conference on Learning Theory, pp. 2286-2305, 2020.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Cynthia Dwork (ed.), Proceedings of the 40th Symposium on Theory of Computing, pp. 681-690. ACM, 2008
Shaoang Li. Lan Zhang, Junhao Wang, and Xiang- Yang Li. Tight memory lower bounds for streaming bandits. arXiv preprint NNNv:2306.07900 2023.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 pp. 1245-1253, 2016.
12

---

Published as a conference paper at ICLR 2026
Yang Li. LLM bandit: Cost-efficient LLM generation via preference-conndttonee dynamic routing. CoRR, abs/2502.02743, 2025.
Xutong Liu, Siwei Wang, Jinhang Zuo, Han Zhong, Xuchuang Wang, Zhiyong Wang, Shuai Li, Mohammad Hajiesmaili, John C. S. Lui, and Wei Chen. Combinatorial multivariant multi-armes bandits with applications episodic reinforcement learning and beyond. In Proceedings of the s International Conference on Machine Learning. 2024.
Xutong Liu, Xiangxiang Dai, Jinhang Zuo, Siwei Wang. Carlee Joe-Wong, John C. S. Lui, and Wei Chen. Offline learning for combinatorial multi-armed bandits. In Proceedings of the 42nd International Conference on Machine Learning, 2025.
Keming Lu, Hongyi Yuan, Runji Lin, Junyang Lin. Zheng Yuan, Chang Zhou, and Jingren Zhou. reward- ensemble of large language models. P Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1964-1974, 2024.
Routing to the expert:
Microsoft Azure. Azure openai service quotas and limits, 2025. URL https:
microsoft com/ en- azure
REST Accessed: 2025-05-12.
Quang Nguyen. Duy Hoang, Juliette Decugis, Saurav Manchanda, Nitesh V Chawla, and Khoa D Doan. Metallm: A high-performant and cost-efficient dynamic framework for wrapping llms. arXiv preprint arXiv:2407. 10834, 2024.
Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M Walced Kadous, and Ion Stoica. RouteLLM: Learning to route LLMs from preference data. In TProceedings of the 13th International Conference Learning Representations, 2025.
Manhin Poon, Xiangxiang Dai, Xutong Liu, Fang Kong, John C. S. Lui, and Jinhang Zuo. On- line multi-llm selection via contextual bandits under unstructured context evolution. CoRR, abs/2506. 12125506..7770.. 17670, 2025.
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pp. 461-469, 2014.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Carlos Riquelme, Joan Puigcerver, Basil Mustafa, Maxim Neumann, Rodolphe Jenatton, André Su- sano Pinto. Daniel Keysers, and Neil Houlsby. Scaling vision with sparse mixture of experts. In Advances in Neural Information Processing Systems 34, pp. 8583-8595, 2021.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adver- sarial winograd schema challenge at scale. Communications of the ACM, 64(9)999-106, 2021.
Yuming Shao and Zhixuan Fang. Linear streaming bandit: Regret minimization and fixed-budget epsilon-best arm identification. In Proceedings of the 39th Conference on Artificial Intelligence, pp. 20354-20361, 2025.
Reza Shirkavand, Shangqian Gao, Peiran Yu, and Heng Huang. Cost-aware contrastive routing for 1lms. CoRR, abs/2508. 12491, 2025.
Aleksandrs Slivkins. Introduction multi armme bandits. Foundations and Trends@ in Machine Learning. 12(1-2):1-286 2019,
Dimitris Stripelis, Zhaozhuo Xu, Zijian Hu, Alay Dilipbhai Shah, Han Jin, Yuhang Yao, Jipeng Zhang, Tong Zhang, Salman Avestimehr, and Chaoyang He. Tensoropera router: A multi-model router for efficient LLM inference. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 452 462, 2024.
13

---

Published as a conference paper at ICLR 2026
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Ar- mand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. CoRR, abs/2302.1 13971, 2023.
Chen Wang. Tight regret bounds for single-pass streaming multi-armed bandits. In Proceedings of the 40th International Conference on Machine Learning, pp. 35525-35547, 2023.
Hongyi Wang, Felipe Maia Polo, Yuekai Sun, Souvik Kundu, Eric Xing, and Mikhail Yurochkin. Fusing models with complementary expertise. arXiv preprint arXiv:2310.01542, 2023a.
Xinyuan Wang, Yanchi Liu, Wei Cheng, Xujiang Zhao, Zhengzhang Chen, Wenchao Yu, Yanjie Fu, and Haifeng Chen. Mixllm: Dynamic routing mixed large language models. arXiv preprint 1eXiv:2502.18482,, 2025.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le. Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in lan- guage models. Proceedings of the 11th International Conference on Learning Representations, 2023b.
Herbert Woisetschläger, Ryan Zhang, Shiqiang Wang, and Hans-Arno Jacobsen. Dynamically learned test-time model routing in language model zoos with service level guarantees. CoRR, abs/2505. 19947, 2025.
Murong Yue, Jie Zhao, Min Zhang, Liang Du, and Ziyu Yao. Large language model cascades with mixture of thought representations for cost-efficient reasoning, In Proceedings of the 12th International Conference Learning Representations, 2024.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can ma- chine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
Sijia Zhang, Shuli Zeng, Shaoang Li, Feng Wu, Shaojie Tang, and Xiangyang Li. Don't restart, just reuse: Reoptimizing MILPs with dynamic parameters. In Proceedings of the 42nd International Conference on Machine Learning, 2025a.
Yi-Kai Zhang, De- De-Chuan Zhan, and Han-Jia Ye. Capability instruction tuning: A new paradigm for dynamic LLM routing. In Proceedings of the 39th Conference on Artificial Intelligence, 2025b.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems 36, pp. 46595 46623, 2023.
Xiaoyi Zhu and Zengfeng Huang. Lipschitz bandits in optimal space. In Proceedings of the 13th International Conference Learning Representations, 2025.
Richard Zhuang, Tianhao Wu, Zhaojin Wen, Andrew Li. Jiantao Jiao, and Kannan Ramchandran. EmbedLLM: Learning compact representations of large language models. In Proceedings of the 13th International Conference on Learning Representations, 2025.
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK
A.1 LLM ROUTING
The central aim of LLM routing strike the best balance between task performance (e.g.. response quality or accuracy) and operational metrics such as cost and latency (Ding et al. 2024 Aggarwal al. 2024). Existing work follows three main architectural patterns. Ensemble strategies query multiple models in parallel to boost robustness, at the expense of higher cost and latency Wang et al.
(2023a): Jiang et al. (2023). Cascade strategies issue queries sequentiallyy-ttically starting with a
cheaper model and escalating only when necessary thereby reducing cost but sometimes increasing
latency (Chen et al. 2023; Gupta et al. 2024 Yue et al. 2024 Aggarwal et al. 22024) Direct-routin
strategies train policy or classifeer that selects a single LLM per query (Ong et al. 2025 Feng
ett al., 2025 Zhang et al. 20255] Zhuang et al. 2025). Benchmark suites such as RouterBench
(Hu al. 2024) facilitate systematic comparison of these approaches. Related work on mixture-of-
experts (MoE) models explores routing within a single large model (Du et al. [022]] Fedus et al.
2022 Riquelme et al.) (02I). More recently. bandit formulations have been applied static LLM
routing (Wang et al.) 2025 Dai et al.] 2024 Li 2025; Nguyen et al.] 2024 Poon et al., 2025
Most prior studies, however, assume fixed set available models and focus solely on per-query decisions. In contrast, our work model dynamic model pool with streaming arrivals and introduce staged deployment updates, where the active model set subject to online selection under strict concurrency cap, cost budget, and throughput limits. To our knowledge, we are the first to formalize and solve this more realistic and challenging problem.
A.2 MULTI-ARMED BANDITS
Our formulation builds the culti-arree-baaneee (MAB) paradigm, where agent maximizes its cumulative payoff through exploration and exploitation in online environment (Auer et al. 2002 Slivkins 2019). Three MAB extensions are especially pertinent: (i) Bandits with knapsacks (BwK).
Here each arm pull yields reward and consumes limited resources from one or more budgets; the objective is to maximize total reward without overspending (Badanidiyuru et al.) 2013 Agrawal & Devanur 2014 Immorlica et al.] 2019 Kesselheim & Singla [2200] Bernasconi et al. [2224] Guo & Liu 2025). Our long-term cost constraint fits naturally into this framework. (2) Sireaming bandits, In this setting new arms arrive over oone-often under memory or attention limits so the agent must adapt to a continually expanding action set (Assadi & Wang 2020 Jin et al., 2021, Aagawal ct al.) 2022; Wang 2023 Li et al.) 2023; Shao & Fang 2025 Zhu & Huang (022).. The steady appearance of new LLMs places our problem squarely in this category. (3) Combinatorial Multi- Armed Bandits (CMAB). The algorithm faces fixed, known set of base arms from which superarms
(subsets) are chosen in each round (Cesa-Bianchi & Lugosi 2009 Chen et al. 2013 Qin et al.,
20e9
2014
Li al. 2016 Chen et al., 2018 Liu
al.) 2024 2025
The core distinctions arise from the two-level structure and unique constraints inherent to the re- alistic online LLM deployment and routing problem. Standard models like BwK and streaming bandits lack the combinatorial selection. While CMAB addresses superarm selection, it is funda- mentally misaligned with our problem's dynamics: it assumes static set of base arms and makes per-round decisions, whereas our core challenges are a dynamic model pool and staged, irreversible commitment, where a deployed set remains fixed for long duration. The regret is thus a function not only of the chosen set but also of the tactical routing policy executed over thousands of queries within that stage. This stateful, hierarchical structure is beyond the scope of traditional bandit for- mulations. Due these fundamental differences, existing algorithms and regret analyses not applicable. Our work bridges this gap by developing a new framework and novel analytical tools tailored to the unique challenges of online LLM deployment and routing problem.
15

---

Published as a conference paper at ICLR 2026
B
SUMMARY OF NOTATION
Table Table of Notation Used in the System Model and Algorithms
Symbol
Description
General Parameters Indices
T;t [T]
Total queries (horizon T);; t is query index in [T] {I....,T}.
K; k E [K]
Total deployment stages (K)); k is stage index.
Tk
Start time step of stage k; k-th deployment update point, Th = (k: 1)T/K +1. Initial time for the algorithm, typically O. The online deployment and routing algorithm.
To
A
LLMs: Availability & Deployment
mi bm
An individual LLM mi; and its availability time 4m Set of LLMs available at time t, and specifically at start of stage Maximum number of LLMs that can be simultancously deployed.
Mr
Mmax
= (dm)
Deployment decision variable vector in Dep oyOPT over MM.. Optimal deployment decision vector from DeployOPT (Eq. 3) at 7k-
d' = (d(m)
(A)
Initial set of deployed LLMs by algorithm A (typically empty). Set of LLMs deployed by A in stage k (derived from di 0).
(A)
LLM Performance & Operational Costs
Vm vm()). (c), pmm
Performance distribution for LLM m (on [0, 1l) and its mean pm =
En-em())
rt.
Realized performance from model my for query
Umy (-).
Jmm
(TR),
U
Empirical mean performance (from N (Tk) obs. up to TK) and UCB for pmm Per-token prices for input and output.
Pin-Pous
(in] (out)
(im) + (out) for m, on query L. True (unknown) distribution of output token length for LLM m. True expected operational cost of LLM m.
Ome Cmme Crn
Input cost, output cost; and total cost Cm,
(m())
B[cm]
Em (TH)
Empirical mean operational cost of LLM m based on Nm (Tx) selections up to Tk- Lower Confidence Bound (LCB) on the expected operational cost E[cm).
cm
C1
Fixed lower and upper bounds for any Cm. 0 < S C2 < xc.
Routing & Constraints
m
LLM selected by the algorithm handle query L. Probability assigned by a routing policy to LLM m E <Dx(A) for query Optimal routing probabilities from RouteOPT (Fq. 7
(e(m)
Pī (pi(m)
b
Long-term average operational cost budget per query.
am A(S)
Throughput limit (maximum load share selection probability constraint) for LLM m.
Set of all probability distributions over set of LLMs S.
Parameter Estimation & Confidence Bounds
(m))T))
Number of times LLM has been selected and observed up to т
Seaa(v, n),7
Confidence radius function frad(U, m) / /vv/n 7/n (with parameter y > 0).
Projection of value x onto the interval [a, b].
Offline Benchmark & Regret (b,
Optimal Performance Rate Function: max expected performance from set S.
supp(p) OPT*
Support of probability distribution
Expected cumulative reward of the time-varying offline optimal policy. Regret of online algorithm A.
Regret(A4)
16

---

Published as a conference paper at ICLR 2026
C TECHNICAL ANALYSIS
In this section, we analyze the regret of StageRoute (Algorithm [ Recall that in our setting, let N = |Mrl denote the total number of models that may arrive over the course of the time horizon. We assume that is significantly larger than Mmaxs the maximum number of models that can be deployed simultaneously. Moreover, the number of update points K is assumed to be much smaller than the total number of queries T. These assumptions reflect practical constraints: it is typically infeasible deploy all available models-includee resource limitations, and continuously updating the deployed LLM pool in real time operationally impractical.
those released in the future due to
C.I CONCENTRATION INEQUALITY
We employ the following standard concentration inequality and related supporting lemmas. Lemma (Kleinberg et al. (2008); Babaioff et al. (2015). Consider a sequence of random variables
F1. I2, Tyg- Let & n Li= T. be the empirical average and n Ei= [[ I4-1 (if i = 1, the expectation is unconditional). If the values are in [0, (e.g., performance rt. or cost et under our assumption), then for each 7 > O,
PI[e - I S Sraa(T, n) and Svad n) S 3rraa(w n)] 2 - exp(-
(8)
TH 2. This result also holds if f1,...,,2 Zn are independent s where frea(u, = / n n. distribution with mean and values in [0, 1}.
For clarity and simplify the application of concentration inequalities, we assume throughout this analysis that all operational costs Cm. are bounded such that 0 < C1 S Cm, C2 S 1. This ensures that costs, like rewards (which are in [0, 1). fall within [0, 1] range (or sub-interval thereof). This assumption does not affect the order of the regret bounds, any scaling factors related to a broader cost range would typically be absorbed into the constants within the (-)) notation.
Lemma 2 (Babaioff et al. (2015), adapted). Let (x) be the sel of deployed models in stage k. For any vectors (0m)mEDe(A) and (Mm)mED((A)) where Om, 1mm
2 0,
Σ
S 7M
Om Tom mEDi(A)
Σ
+ MM,..
(A)
where M₁ = (A)).
Lemma Babaiooff et al. 2015), adapted). Let pm (1) = (Esetmm T.) (NN (1)+1) be the em- pirical average performance and ém (t) = C Cx) (N. 1) (1)+ be the empirical average cost for model m E DD(()) based on Nm,(1) (1) plays before time I within the current stage k. Then, for every m E (A) and time t E [Tk. Tk+1), with probability 1 e eQ6() (i.e., on the event E):
1i (1) Mm S 2frrad m (t), No. (1) +
(9)
1Cm 19 [cm]] $ 2frad (Cm (t), Nm. (1) +
(10)
Proof. Follows from applying Lemma to the sequence of observed performances r. (for m, m)
and observed costs C2 (for m, = m). For a fixed model m, the rewards тN (when m, = m) are i.d. samples from (.) with mean Mm. Similarly, costs c2 (when m. m) are effectivvey i..d. samples with mean B[cm]- Thus, the conditional expectation [[ ........,;. -x:-1 in Lemma becomes the true mean Am (or EE(c..). The derivation is analogous to Lemma 4.3 of Babaioff al. (2015). For instance, for performance:
(tm(t) pml Emstmmm
(Nm 1)pm
(t)++)1
Nm +
(t) + (Pmm(Pm(t). Nm (m) +
(t)
pm
(from Lemma structure)
Frad (m (t), Nm. + +1+ Nm.(t) +1
Pm
< 22 (fm (f), Nm (t) 1)
The argument for cost is similar due to the assumption em [er, 02) C 0,
17

---

Published as a conference paper at ICLR 2026
C.2 REGRET DECOMPOSITION WITH TIME- VARYING BENCHMARK
To analyze the regret of StageRoute (Algorithm D over the horizon T, decompose the total regret into components corresponding to the model deployment and request routing phases.
Definition 1 (Optimal Performance within Deployed Set). For a given stage k (time interval [Tk, Tk+1) of length T3 Tk+1 Tk) where StageRoute (during Model Deployment Phase) deploys the set Dr= = Dx(AA) S MM. (bb, Dz) represents the optimal expected reward per query achievable using only models from the deployed set Dt. The total optimal expected performance within this stage using Du is OPT; =Tp VVb, Du). Note that Dr is determined by StageRoute based on Mr, and estimates available Tu. Thus, Dy and consequently V(b, Dx) (and OPTw) are random variables, dependent the algorithm's 's choices and observations up time Ty-
Definition 2 (Algorithm Performance). Let ALGO be the total expected reward accumulated by the algorithm over the horizon T:
T
K
Te+1
ALGO
t=1
k=
T=
Let ALGO: = Eit+ Tr be the reward accumulated by the algorithm during stage k.
Lemma 4 (Regret Decomposition with Time- Vareing Benchmark). The total expected regret R(T)- OPT E[ALGO] of StageRoute, compared against the optimal time-varying bench- mark OPT = - Ein Max)), can be decomposed as:
K T-
K
R(T) = E
Σ
Σ L=T
(V D2) re)
+E
Σ
t=
Reoning (T)
Rayeoo (T)
where:
Rrouting ( is the total expected routing regret, accumulating the per-query difference be- tween the optimal expected performance with the deployed set (b,, Dx) and the realized reward Tt, summed over all queries and stages.
Rasploy (T) is the total expected deployment regret, accumulating the per-query difference in optimal expected performance achievable with the full set of available models V (b, M, versus the deployed set V(b, DR), summed over all queries and stages.
Proof. We start with the definition of the total expected regret:
R(7) = OPT - E[ALGO].
Using the definition OPT*
DK
Dk=1
11 Vbb, Mb, and ALGO ΣK
kk=l Etere
K
Th11- V(b,M,,)) - E
K Tk Σ
R(T)
Σ km
T=
Note that Mr, (the set of models available at time TH) depends on the fixed model arrival times lm and the stage start time Tı- According to the system model (Section 2 Th (k: 1)T/K and the stage length T. (Tk+1 Tk) T/K are deterministic. Consequently, the set M and the benchmark value M,, are deterministic for each stage k. The randomness in the regret decomposition arises from the algorithm's 's choices, specifically the selection of D3 (which determines (b, Dz)) and the subsequent routing decisions leading to the realized rewards rt-
Since V(b, is deterministic for each k and constant for E [Tk, Tkt1 1), the ΣK Ditt (b, is also deterministic. Thus, it can be written as
18

---

Published as a conference paper at ICLR 2026
Ek=
Eisre
V(b, M,))
We add and subtract the term
Ex
V(6, Dz)
T6+1-1
R(T)
Σ
Σ
Mik
E
T1
K
Thi1-1
E
V(b
EE
V(b.
L==1
T=Tk
K
Thi1-1
K
Thil-1
Dxb
E
1=
Now, we combine terms using the linearity of expectation:
R(T) = E
T6+1-1
(V(b Tb) -r))
E
L=
This expression matches the claimed decomposition, identifying the deployment regret Rdeploy (T) and the routing regret Rouuing (I") as defined in the lemma statement. Alternatively, letting OPT, Vb, Dx) Eist -1 ((b, D2) and ALGO, Σ re. the routing regret can be written EI (OPT, - ALGO,)] Similarly, the deployment regret can be written as BI (6, V(,,
This decomposition provides accurate picture of the algorithm's performance. The deployment regret Resploy (T') isolates the loss incurred specifically by StageRout e potentially suboptimal selection Dr (during its Model Deployment Phase) from the available set MM,,, measured against the best possible rate (b,)), achievable with those available models. Bounding Reteplay (T)) involves analyzing how effectively the Model Deployment Phase of StageRoute identifies the optimal subset of size at most Mmax from Mr, based on its estimates. The routing regret Rrouning (T") remains the sum of per-query differences between the optimal expected performance using the deployed models Dj and the actual realized rewards Lemma I1 (or subsequent analysis) addresses the
term E E -i=ttt11000 (b, Da) rt) DD,] which contributes to Rmuting (T).
(V
C.3 ANALYSIS OF DEPLOYMENT REGRET
We now analyze the deployment regret component Reeplay (T) as defined in Lemma
Reeplay (T) B Th (VO. V(b, Dw))
This quantity captures the cumulative expected performance loss across all stages, incurred when the StageRoute algorithm selects subset Dj stage l based on estimated model statistics at time The instead of deploying the optimal subset from the full set of available models Mr.
The deployment regret arises from two complementary sources:
1. Parameter Uncertainty: Inaccurate estimates of model performance (pm) and cost (E[cm)) may result in suboptimal deployment decisions. This source corresponds to models that have already been deployed in one or more of the previous k 1 stages.
2. Model Discovery Bottleneck:
The constraint that at most Mmax models can be deployed concurrently may exclude promising but underexplored models models-partie particularly newly ar- rived ones ones-from being included in Dę. This prevents timely evaluation and utilization, contributing to additional regret. This case pertains to models that have not been selected in any of the preceding stages.
19

---

Published as a conference paper at ICLR 2026
These two components complementary in nature and together constitute the total deployment regret Resploy (T). In the following analysis, we will provide regret bounds for each source.
For the analysis, recall that V(b, is the optimal performance rate for model set & (defined in Section 2). Let V = (bb, MM be the optimal rate achievable using all models available at the start of stage k and Vi V(b, Dz) be the optimal rate achievable using the subset Dr M selected by StageRoute. VE is deterministic given 7ke while V& (through D2) is a random vari- able. A key assumption for bounding the deployment regret due parameter uncertainty involves the Lagrange multipliers associated with the budget constraint in the definition of Vi= Let X 2 O be this optimal Lagrange multiplier. We assume that X uniformly bounded by a constant for all k. This is a common assumption in the analysis of learning algorithms with budget constraints and is often justified when standard regularity conditions (such as Slater's condition, which we as- sume in Assumption T hold for the underlying optimization problems, particularly given that our problem parameters (rewards, costs, Om) are bounded and expected costs E(cm] are power-bounded by c1 0.
Confidence Bounds and Good Event. Let Thk be the start of stage k. model m before Tk. Define confidence radii using Lemma I and with y ((log(NT/8))
(T,) is the play count for
rad, (m, Tk) 2 [ra (Tk), Nm (TK) 1)
(m, Tk) = 2fraa Cm (Tk), ) Nm + 1) (Since costs cm E [ci, C [0, 1J)
Let Eg be the good event at time Tk where, for all m E MM the confidence bounds based on hold:
Pm S 1m
1m (Tx) and p (Tx) S Mm + rad, (m, Tk.)
T3| [m]] - rad,(m, Tx) - <m (Tk) and (Tc) & [[((m]]
Let E=1 By union bound over all N models in the universe Mr and K stages, P(E) > 1 8. We condition the analysis on E. (Note: phe is Pm
(Tk) ( (Tx), Nm,(TT) +1 and ch
is Cm (Tk) - -2frea(Em(TT)) (Nk), +1 as per Eq. (6,7) in the algorithm description, projected onto [0, and [cI, 02] respectively. The inequalities above capture the desired properties on the good event E
Bounding the Per-Stage Deployment Gap due to Estimation Uncertainty.
Mr.) be the optimal rate with available models at stage k. Let Dr = supp(d') be the set selected by the Model Deployment Phase of StageRoute based on Mr. and estimates The via solution d' (from Eq. equation 3 Let Vx = (b, Dx). On the good event Eg, the deployment gap for stage k is bounded as:
Lemma 5 (Per-Stage Deployment Gap Bound). Let V
VE - V S
Σ
(rady(m, Th) + Nerado(m, Tk)) d'm.
mEMrr
where X is the optimal dual variable for the budget constraint in the problem defining Vg. assumed to be E
Proof. Let dpp. be optimal solution achieving VE Vbb, Mb, Let d' be the solution found by StateR Model Deployment Phase (using Eq. equation 3 at Th when optimizing over Mr. using n (TR) and ot. (Tx). Let D; supp(d"). Let Ví, Vlh, Dz).
On the event &x. the confidence bounds hold for all m E M Specifically, Pmm S (Tx(TT) S um + rad,,m,, TR) and B[cm] - rad TR) S So (TT( S B[cm]] The true optimal solution k for the set Mr, satisfies Emem., Elem] Ja < b. uses & Minax models from M etc. Since oh (Tx) S B[cm] on εs, have EmeM., ( < Emem, E[em]dm. Jd < b. Thus, dri.k a feasible solution for the optimization problem solved by StageRoute (Eq. equation 3 applied to Mr.).
By the optimality of d' for St ageeRutte's deployment objective over M
Σ
1 (Tx)dd
2
Σ
17 (Tx p.p..
(11)
MEM
mEM-
20

---

Published as a conference paper at ICLR 2026
Using the confidence bounds on Eg for E Mr.
(Tx)dm Mm
Σ
(um + rad, Tw))d
Σ
umd +
Σ
rm, Th )d)
meMrr
meMr
meMr
mEMTr
Σ
Σ
VE
MEMr
mE.Mr
Substituting these into Eq. equation
Σ mEM
pm dm +
Σ
rad (m, Tk)d 2 Vi
meM-r
Rearranging:
Σ mEM-.
Pm
VI
Σ
rad (m, The Te)dd
(12)
mEM-.
This bounds the true performance of the distribution d' chosen by the algorithm. Now we relate this V = Vb, Dx), the optimal performance within the chosen set D; supp(d") Mr The distribution d' is supported on D2 and uses at most Mmax models (due to the constraint in Eq. equation 3). We examine its feasibility w.r.t the true budget constraint. On Eq:
Σ MEDx
E[cm]d S
Σ (cth + rad,(m, m))dd bb+ Σ rad,(m, Th )d
MEDK
mEDz
Let 6e(d") = meD, rad,(m, )x)d Using sensitivity analysis/duality, relating V = V(b, Dz) to the performance of d' which feasible for budget b (c(d"):
V = DR) 2 V(b ddd)), Da) (ide(d")
where A1 S A. Since d' is feasible for V(b + (dd): Dk):
V(b o6'), 2 Σ
Um Mmd
Σ
pm Mmd
m
Combining these:
V&
2
Σ
Hm Umd
- -xpdo(d")
m.
Ve
Σ
(m, Tx) )dj
- Σ rad. Tx)d
(Using Eq. equation 12
mEMTr
mED.
Rearranging gives the result (noting di for m & Dw):
V V/ S
Σ
rad,(m, Ty ddm + x
Σ rade(m, Tx)d
mEMT
mEDi
Since d; = 0 for m DR. the second sum can also be written over M
V
V4 S Σ
(rady(m, Tk) + Agrado Tx)) d',
MEM
Cumulative Deployment Regret from Estimation Uncertainty. Summing the per-stage deploy- ment gaps caused by estimation errors gives the learning component of the deployment regret.
Lemma 6 (Deployment Regret from Estimation Uncertainty). Assume the optimal dual variables Xj are uniformly bounded by A. Let K be the total number of stages. Set the confidence parameter 7 = Olog(NT/8) where N = MMrl. Then the component of total expected deployment regret due to parameter uncertainty, denoted Ramploy (T), is bounded by:
Ream (T) < ( (T)=O(TTl))))))) (VTlog(NT/8) min(N, K Mmaaa + Mmax K log log(NT/5))
21

---

Published as a conference paper at ICLR 2026
Proof. The total expected deployment regret due parameter uncertainty is given by
lepp (2) E
Σ Th (V
where = My,) and V = (b, Dz). We condition on the good event & = 1 which holds with probability at least 1 1- 8. On this event, the confidence bounds for pm and E[cm] hold for all models m and stages k. From Lemma on event Eg:
VE V -
(radu(m, TK) + Aārado(m, rk)) dh.m
mE.Mr
Let (Tk) = rad, (m, Tk) + Arad,(m, Tk), using the uniform bound X S A. Since di.m = 0 for m & DD. supp(d?), we have:
T& V4.) S Tp E Cm(TT)de
mEDr
The term dz km represents the selection weight for model m in the deployment optimization at stage kt Thus, EmED, Cm (m())d is weighted average of the combined confidence radii for the deployed models. We are considering the case where the model has already been selected in the previous i stages. Thus, we can bound the sum of T&(VE Vi.) by terms related to Ek= EmED, nk.m (T<k). Specifically,
K
Σ T& - Vi) S 50 k=1
Σ
E
nk.m (Tk)..).
k= mEDE
Let's analyze the sum S 2 Nr, (Tx) + 1) + 2A frad (Tm)) Nn (T)) + 1). Since rewards Pm (Tk) E [0. 1] and
ΣK EmeD, M.
Recall Cm(Tk)
costs Cm(Tk) E [ei, S [0 (with ei > 0), we have Sraa(t, / + + S V + for
[0, So. Cm(TN) 2 ())++)( (V Non + N
Let C' 2(1 +
S C" Σ Σ Tkmm
(N N (T) +1
kElmED
We can rewrite the sum by first summing over all models m MM (the of all N possible models) and then over the stages k in which m was deployed and played:
S S Σ
Σ
nk. (V (T+ (T)(T))+1
ME kum ED and 30
For fixed model m, let Nm (T) be the total number of times it is played up to T. Let Am,,y be the number of times is played during the j-th stage (denoted 8,) in which it is deployed. Let (Ta,) be the total number of plays of m before stage 8y. The sum for model m is:
K
Sm Σ Tom
(VAnnTra)+ + Nm, +1)
where K", the number of stages model m is played. use the standard inequalities for such sums:
E Rem,yy Nit
VVNN (T)
Diml
V (plays of m before current block) +11
VT
2 2 (T).
ES Kh
Rem,e, Non(Ta)+1 S NT)
7
(plays of m hefore current block)+T 5 (1 In Nm (T)).
22

---

Published as a conference paper at ICLR 2026
So, S. S ((V7Nn(T) + y log Nm (T)). (We absorb constants into (-) for now, and will re- introduce C' later). Thus, S C² E'EMrs aa NM(T))O O( ON (T) + y log Nm (T)).
The sum is over models that were actually played. Let MM = fm E MM | Nm((T) > 0}. The number of models in D2 is [Dx] S Mmax. So, EmEMp V (N S (/MP/Emmeee (T)
v M| (T by Cauchy- Sehwar. Since at most Mmax models are deployed in any stage, and there are K stages, the number of distinct models ever deployed is [Mp & min(N, KMaax).
The sum EmeMp log (T). If Nm (T) 2 1, then log N.) (T) 2 O. This sum is at most Mmax log(T/Mmax/ if Miax models share T plays, or more generally bounded by Mixx K (if each of Mmax models gets played at least once in each of K stages, its log (Tm contributes, and (T') could be small). A more careful bound for the sum of log terms: Ememp log (2') s
M K log T. So, S S C" (O(V)T min(N, ) + O(y K)). The log terms are typically absorbed into the y term. The expectation B[s] includes the good event (probability
5)
and the bad event (probability o). On the bad event, the regret in one stage is at most Tk. so total T. Ream (T) E[S] + 8T. If i O(/TT), then 87' O(1). Substituting C' 2(1 + A) and y (log (NT)))), then we complete the proof.
Deployment Regret from Model Discovery Bottleneck. The constraint of deploying at most
Mmax models simultaneously, [A)( S Mmax. introduces a structural challenge, particularly when new models frequently become available or the total pool of models Mr is large. This chal- lenge is the model discovery bottleneck: identifying truly superior models among many new, un- evaluated candidates can be delayed.
The StageRoute algorithm employs UCBs for rewards (1 and LCBs for costs (ch) in its DeployOPT phase (Eq. equation 3). For a model that is newly available at stage h (i.e., im S Tk and its count of previous selections Nm. (Tи) = 0), its initial empirical averages Pm (T))T) and Em (Tk)
are set based on priors. The confidence radius frea(1; (v, Nm (Tk) + 1) V N.. (T.( (m.
becomes large for Nm (Tx) = 0. Specifically, with No. (Tx) + 1 1:
Mm (Tx) = proj (Imm(TT) + 2 V 7a (Tx) + +7))
J. (Tx) = proj (c)e))
(Tm) - 2 (Vrem(Th) (T)) + +7))
Assuming priors are chosen such that new models are treated optimistically (or if y is sufficiently large), 1 (Tx) will be close to I (c.g., if (Tk) = 0. 1h (Tx) proj (27) for appropriate 7) and oh (Tx) will be close to (e.g., (m. = C1, ch (Tx) = proj (a ((( ~ c1, noting C1. 02 E [0, 1). Let these optimistic initial values be Unni and Linit respectively.
Consider an update point Tk- Let Nnem, & C Mr, be the set of models that are new at or before T and have not yet been deployed (Nm (TR) = 0). All models in Neews, will have nearly identical, highly optimistic (nm </h) R (Uinit, Limit) values. If the number of such equally optimistic new models, [.new.kl, plus other potentially optimistic (but previously explored) models, exceeds Mmax the Deplow oyOPT phase must select only Mmax models. If the new models in N dominate the selection pool due to their optimism, DeployOPt T will choose Mmax models from Nnew., (possibly along with some already explored models). Crucially, if there are more than Muax models within Nnew,, (or a larger pool of similarly optimistic candidates) that yield effectively the same objective value for DeployOPT T (because their y ot, am are similar), the selection among these specific candidates becomes arbitrary (e.g., dependent on tie-breaking rules).
A truly superior new model m" E Neew might thus be part of a large batch of Noateh > Miax new models that all appear equally promising to DeployOPT. T. In this scenario, m" might not be selected for deployment in stage k. deferring its evaluation. This deferral means the system misses the opportunity to benefit from mn potentially high true performance pmn for the duration of stage k, which is T = T/ K rounds.
Lemma 7 (Model Discovery Bottleneck Regret). Let Mmnx be the maximum number of concur- rently deployed models, T be the lotal time horizon, and K be the number of stages, with each stage
23

---

Published as a conference paper at ICLR 2026
having Ta = T rounds. The component of expected deployment regret due the bottleneck in discovering and evaluating all N models, denoted dissooyy,iscoveryy (T), bounded by:
disppoy. (T) (T)= =0 (0 Mmax
= (
NT
Mmax K
Proof. Each of the N models in the universe My needs to be deployed at least once to gather initial empirical data and move its UCB/LCB estimates away from their initial purely optimistic values. We are interested in the total regret incurred until all N models have had at least one such initial deployment opportunity.
Due to the constraint (Dx(AA) S. Mmax. at most Mmax distinct models can be deployed and evalu- ated in any given stage k: the system prioritizes exploring previously undeployed models (which is encouraged by their optimistic UCB/LCB values), it will take a minimum of K Kezptore = [[//Maa stages to ensure that every model My (assuming all become available early enough) has been deployed at least once.
Consider a discovery period spanning these first Kezpiore effective stages. During any given stage j E [L, Kesptore] within this period, if the set of Mmax models deployed, (A),, does not include some model m E My which is (a) available (m" E M,,). (b) truly superior to at least one deployed model m' E (A),,, and (c) m" has not been deployed yet because it is waiting its turn due to the arbitrary selection among many new, equally optimistic models, then regret is incurred. The per-query regret in such case be up (if pm R 1 and umm 0).
The total number of queries over these Kezptore stages is Kexpiore Th = [N/Mmax]] (T/K)- During this cumulative period, the system effectively cycling through the N models. If the se- lection process within each stage means that, on average, the deployed set is suboptimal because truly good models are among the (N- Mmux) yet to be tried, the system incurs regret. The term (NNT (Maxx K)) represents the cumulative regret if, for duration equivalent to N/M full stages (each of length T/K), the system operates with a deployed set that is, on average, O(1) worse per query than if all models had already been evaluated. This occurs because the Mmax slots are occupied by models chosen optimistically, and a superior model might be consistently deferred if it's part of a large pool of indistinguishably optimistic new models.
More formally, consider the N models. Each requires roughly one exploration slot of duration T.. These N slots processed in parallel groups of Mmax. This implies approximately N/Mmax stages are spent ensuring all models receive initial evaluation. If, during these N/M stages, the average deployed set yields (1)) less reward per query compared an optimal deployment (had all models been known), the total regret from this discovery phase is (N/M (T/K) O(1). The expectation E[.] in Reeploy.diseewery (T) averages over the random tie-breaking in Depl DeployOPT when faced with multiple equally optimistic new models, and the stochastic arrival pattern of models. The O()) notation absorbs constants related the maximum possible per-query regret (c.g.. 1) and the precise nature of average suboptimality during this discovery period.
This component accounts for the scenarios where truly good models might be systematically delayed in their initial deployment if they frequently arrive alongside many other new models, leading to arbitrary choices among a large pool of initially indistinguishable (optimistic) candidates, subject to the M deployment limit over K stages.
Total Deployment Regret. The total deployment regret Reeploy (T)) is the of the regret from parameter uncertainty (Lemma 6) and the regret from the model discovery bottleneck (Lemma 7).
Lemma 8 (Total Deployment Regret Bound). Let N be the total number of models, Minx the maximum deployed models, T the horizon, and K the number of stages. Let y = ((log(NT/))) The total expected deployment regret Resploy (T') bounded by:
( min(N, KM + Mmax K log(NN//) + NT
Redolly (T) (T)
M K
24

---

Published as a conference paper at ICLR 2026
Proof. The total deployment regret is the sum of the bounds from Lemma 6 and Lemma
Receloy (T) Jecp (T) + Reeploy, discovery (T)
NT
0 (Tloog(NT/)) min(N, (N, K K + Miax K log((N/))) +
Mmax
NT = 0 (Toog(NT/)) (N Mmaxx + Mmax K log (og((T/6)) + M K
The total deployment regret bound in Lemma 8 highlights two distinct challenges in the deployment phase. The terms O (VVT (og(T////////
min( N, K Mmnxx) and O log capture the cost of learning the parameters of models that are considered for deployment. This cost depends on the horizon T, the number of deployment slots M Mmax- the number of stages K, and logarithmic factors related to the total number of models N and confidence The term (NNT/ (Maxx reflects the structural cost imposed by the discovery bottleneck: when the universe of models N is large compared to Maax and the number of adaptation opportunities K, there an inherent regret incurred in sequentially exploring models to identify the best ones. This term dominate if N is very large or K small, underscoring the importance of the deployment frequency and capacity in dynamic L.M environments.
C.4 BOUNDING THE TOTAL ROUTING REGRET
We now bound the total routing regret term Ryouting (7') identified in Lemma 4 This involves sum- ming the per-stage regrets incurred by the Request Routing Phase of StageRoute due to using estimated model parameters within the deployed sets Dr. This part of the proof follows similar structure to the analysis of UCB-style algorithms for the Bandits with Knapsacks problem Agrawal
Devanur 2014).
Lemma 9 (Performance Bound). Lei ALGO; = Enee-l Te be the total observed performance in stage k. With probability least (MaTh) exp(-O(1)),
Σ
00 <0(VAMMALCC + +7Ms)
Tt
(AD+(A)
Proof. The proof follows the structure of Lemma 4.4 in |Babaioff al. (2015), adapted our nota- tion for models tion De (from Eq. equation 7). and summing over & [Tk, Tk+1 - 1] (length Tk))
(A) and performance pm. UCB n (t), chosen model m, routing distribu-
We use Lemma 1 and Lemma 3 (for performance). High probability bounds analogous to (5) and (6) in the source proof hold for sums over E [Tk: Tk+1
1]:
Σ E(re pm.)
$ 5(Th fred 1
Σ Mm, Tx))
Σ
Σ (AD
1 (1)(1)
<(TT: Sraal 1
Σ
1 (1),
Ts
25

---

Published as a conference paper at ICLR 2026
And analogous to (7) in the source, using Lemma and Lemma 2
Tk41-1
T441-1
(mm, - Hmme (t))
S
Imm
- Mm (t)
T=
T=
0
Σ
frad (t), Nm. + +1)
0
Σ
Σ
Frad(Am play j), Nm (at play j) +
mEDx(AA) plays of m in stage k
00
Σ
(Vr(Nm(Teti)) Nm Nm (Tx)))mm +7)
(EDa(A)
0
MM4
Σ mEDx(()
Pm Pm(Am((Ttt1) Nu((wa)) + yada
1
5
YM,
Σ
Hmn
+ tyde
Let A= = Etstt EmED)(A)) (1)p (m). Combining these bounds using the triangle inequality
on rt. - -Em Men (1)p (m) (r+ ) + (Jum, - pmm, (1)) + (n (1) En. P (1pt (m)) similar to the source proof structure, leads to an inequality relating A and Σr, = ALGO If Er R Σ Am, and A x Σ Hm, (t), then the difference [E - Hum, (t)) dominates. This typically leads to - O(V7//A 7M)) S ALGO, (assuming n² are UCBs and A 2 Σ Ph, (f)). This implies V VALGO, Oz)) Substituting this back into the bounds for the difference |ALGO; A| yields the claimed result.
M441-1
T441-1
Σ
Σ
(m) S &WV + MM)). mEDa(A)
Σ
1=
t=Tk
Lemma 10 (Cost Bound). Let E be the total observed cost in stage k. Let B₁ b- Ta be the effective expected cost budget for the stage. With probability least (xM()(())) (i.e., on event E),
TEL
Σ t=
4 Σ (1)) (EDe(A)
+ <V
0O 5o
Proof. The proof mirrors that of Lemma
(and Lemma 4.5 in Babaioff et al. (2015)) replac- y (t) with c/ (t). and Tr with c,.
ing performance with cost, pm with E(cmu
The probabil-
ity distribution pł is from Eq. equation
7
Key steps involve bounding Σ Σ E E(cm,]1,
IΣ ch (m)) Σ ce. (t)). and
B B(Cmu,) Σ cte (t)). The last term bounded similarly
using Lemma 3 and Lemma 2
so (/
T8+1 Σ
Th-1-1 Σ Bjcme] Ea
(E(cm,)
t (1)
+ 7:Mx
Let A' Σn
11-1 Blcm..) The algorithm ensures EmEDILA) (t(pt)p(m)
each step
Summing the stage gives T EmeDiCA) tf (1) 1 b T B Let
26

---

Published as a conference paper at ICLR 2026
X. = Ei=r
- - "mED((A)
en (t)pf(m). Then Σm G. Xx I O(v)MaA' + 7Ma))
where A' is the sum true expected costs. On event &, (t) - E[ so X, < A'. Also, S X OV +2M)). Since X, I Bg, it follows that A' B₁ O +>M+)-
This implies VA'= I vBx + O(v) Substituting this back into the concentration bounds for E Xel (and noting A' = Bx in the error term's 's leading order) yields the final result.
Lemma 11 (Per-Stage Routing Regret Bound). Let OPT
maxp (EEEDLAA) (mp(m) EmED,(A) (l)m)l((m S b, Ep(m) = 1,0 p(m) S am) be the optimal expected reward rate within stage using DA(A) and true parameters. Let OPT, Tk OPT be the total optimal expected performance stage Let ALGO, Ei=ry E Tt- Assume M& S O(B)). Then, on the event & (implying high probability for the bounds within the stage), the routing regret for stage k, conditioned on Du, is bounded by:
B ALGO, D&] S O (V>M2OPT. + +MM))
(The expectation is conditioned on the choice of Di. which itself depends on information up to Tk.
Proof. On event E, the following hold:
1. pm (t) 2 Pm and cn (t) & Elcml for all relevant m, t.
2. Lemma Erere - Em w (t)pt (m)) s Ol + 7M4)-
3. Lemma 10
ct (f)pt (m)) S O(V7MrB + 7MM)) Also. Σ, ct S Ba +
O(VrMrBr + 7Mr).
From the algorithm's choice of pt (solving Eq. equation 7 and property (1):
Th41-1
Σ
Σ
(t1(p)p( R OPT
I=TE
(E))(A)
Combining this with property (2):
ALGO: = r -rre Σ
- ( 7)Mx)
m
ALGO; 2 OPT, OL + MaA
Rearranging and assuming AL.GO, S OPT; (regret nen-negative):
OPT₁ - ALGO, S M(V + +
ALGG; S OPTg, then VALGO, S VOPT
OPT, ALGO, I OV M/))
Taking expectation conditioned on D3 (and implicitly on E for the bounds to hold), the result fol- lows. The assumption M&7 I ((B)) is used concentration bounds for costs. Moreover, since the estimation enrors for both performance and cost are governed by the same concentration inequalities, the expected budget violation is on the same order as the regret.
Lemma 12 (Total Routing Regret Bound). Let K be the lotal number of stages. Let Ms. De <
Mmax- Let 8 E (0,1) be the desired overall confidence. Set = O(log(NT/8), Then the total expected routing regret is bounded by:
Σ (OPTL - ALGON) S0 ( KT + MyMmax
Reouting (T) E
Substituting O(log(NT/O)) this becomes:
Rrouning (T) < O (v [MMaxxe KT loo(NT/T)) + K Mmax log( (NT/))
27

---

Published as a conference paper at ICLR 2026
-k=1 E ALGOa) Here OPT, [b D;) and | is the algorithm's reward in stage k. The outer expectation E[I averages over all randomness, including Dx and the failure of event (which occurs with probability I 8). Using law of total expectation: IR[OPT ALGGO,] = E|E[OPT; AL.GO, D&]]]-
Proof. From Lemma 4 Recuting (T)
We apply Lemma 11 Choosing (loog ((Tog(NNT8)) ensures that event & holds with probability least 5. On 3:
B - ALGO, Da S (VMMROPT, + +yMss)
Taking expectation over D3:
E ALGO s 0o
E V MM
+>B[Mul) + Tp
Summing this bound over all K stages:
K
Reuuting (T) S Σ o B (
MrOPT
+>B[MR] + 5T
k=1
Using linearity of expectation, Mr I Mmax. Jensen's inequality [E[VX] S /E[X]), and [[M+] <
Maxxi
K
R Remning 5
Σ
R
Mmax
OPT
7 7
+ 5T
K VyMMmax
0
E[PPT Ky
+ 8T
Applying
Schwarz:
EK
S
K K [OPTT]
Thus,
ΣK /EJOPTa] S V B[OPT Since rewards in [0, 1), V(b, Dz)
1 1,
O TgV(b,D)) S Tμ. Summing over k: ΣK OPT Σ Ts T. So.
EK [[OPTk] T. Substituting this upper bound:
Rovating (T) S O 7 KT + KyMmax) + 8T
is chosen small enough, the 8T term is absorbed. This establishes the first form the bound. Substituting 7 O(log(NT/)))) yields the second form.
C.5 TOTAL REGRET BOUND
The overall regret of StageRoute accounts for several sources of suboptimality. The total ex- pected regret (T) can now be understood as the sum of two main components:
1. Rooutnn (T): The routing regret within deployed sets (Lemma) 12
Raeplny (T): The total deployment regret, encompassing both learning uncertainty and model discovery bottleneck (Lemma 8).
Summing these bounds:
R(T)= = Remating (T) + Reteploy (7)
< 0 Mmax KT log( (T + K Mmax log( (o((N)/))
NT M K
+ O (VTlog(NT/)) min(N, KM ) + M K (Ngg)) +
Combining terms, and noting that for K 2 1, / Mmax KT www.oolooo//// dominates or is equivalent to /Tlog((TT6) min(N, K. Kmaax) and K M log (og(N//5;
R(T) s O (V Ammax KT log NT/8) + M K
NT
28

---

Published as a conference paper at ICLR 2026
D LOWER BOUND FOR ONLINE LLM ROUTING
We establish a lower bound on the regret for any online LLM routing policy. The construction considers a scenario where the set of competitive models and their performances can evolve over time, divided into batches. Within each batch, the algorithm faces a sequential decision problem of selecting the best among M available models, where the identity of the best model is unknown and can change from batch to batch. To isolate the learning challenge, We assume each model invocation incurs a unit cost (Cm, = 1), rendering the budget constraint trivial if the per-query budget 2 1. We also assume that the system can always deploy any of the M models under consideration in given batch (Muax 2 M) and that there are no per-model capacity limits (amm adapting to the best- berf-performing model(s) in each batch.
make several simplifications.
for all m). The core difficulty then lies continuously learning and
The proof strategy is construct class of adversarial problem instances. We will demonstrate that any online algorithm A must incur significant regret on at least one instance within this class. This argument adapts a batch-based structure common in analyses of learning problems with non- stationary environments.
Step 1: Construction of Hard Problem Instances. Let E 0 be small parameter, which will be determined later. The total time horizon of I'' queries is partitioned into Ng contiguous batches, denoted ....... BNn- Each batch j consists of A T/NB queries. For simplicity, we assume T is an integer multiple of NB.
For each batch j These models are indexed E (1,.... M) specifically for the current batch j. The performance characteristics of these M models are defined as follows: one model is designated as the "strong" model, and the remaining M 1 models are "weak". Let 8, E {1,..., M) be the index of this strong model in batch j. chosen uniformly at random by the adversary and unknown to the algorithm. The reward rt obtained from selecting model at query E Bj is drawn from a Bernoulli distribution:
:l....:NB): we consider set of M models available to the algorithm A.
If model may (the strong model for batch j, with index 8y) is chosen, T2 Bernoulli () where the mean reward is PB (2) = je.
If any other model m, (where E (I...., and i + s;) from the set of M models for batch; is chosen, rz Bernoulli(z)))) (1))), where the mean reward is PL
(j 1)e.
Rewards from different queries are assumed to be independent. The crucial gap in expected reward between the strong model and any weak model in batch j μ =L c. To ensure that all mean (i) lie comfortably within the interval [0, 1]. we impose the condition NE < 4. (i) and ury
rewards PH
(Ns) 1 BE S 1 4 = 2/4 < 1, and the smallest mean, Pt, (1) 1 + (1-1le 2
This ensures UH also valid.
A complete problem instance is characterized by a sequence of strong model indices $2.......... ). The actual underlying LLMs corresponding these indices could differ from batch to batch, but in each batch j. the algorithm A faces a choice among M options with the specified reward structure, and 8j is unknown.
Step 2: Per-Batch Regret from Identification Difficulty. Fix a batch j E (1...., NB). and let s3 denote the true index of the strong model, unknown algorithm A. To identify m.; (mean
( from the M 1 weak models (mean / gap c) with a constant probability Psace
(e.g..
Prace 3/4), any algorithm requires a query complexity of 9(Me- Agarwal al. 201 Li
et al. (2023). This implies there is a universal constant Cs > 0 such that at least M c queries are necessary to achieve success probability Prace.
We set the batch length A = Me Since cs/2 < cs, this choice of A is insufficient for reliable identification with probability Psuce. Consequently, algorithm fails identify m,; within A queries with at least a constant probability Pfail 2 1 - Psuce (c.g., setting Psuce = 3/4 gives Pfai 1/4). Let Eail denote this event of identification failure.
29

---

Published as a conference paper at ICLR 2026
Let Nj, weak be the number of queries to weak models in batch j. Conditional on Ejstt the algorithm lacks knowledge of s7. In such a state of confusion (especially when M 2 2), it is expected to select weak models significant fraction of the time. For instance, if choices upon failure are made nearly uniformly among the M models, weak models are selected M-1 A times in expectation. Since
M 2 2, (M - 1)/M 1/2. Thus, we can state that E. EN,, NN fail 2 cr for chosen constant OF 2 1/2. By the law of total expectation, and since E[[N fait 0:
B[N = P(E R[N w.wak (Eyaa) + P(E aill) ) J.cak 2 Pfail c.
Using Prast 2 1/4 and or 2 1/2, this gives j. 2 1 14 batch j (for a fixed sj. averaged over A's randomness) is R2(s) = <R| N j.weak] 2 <AA/8). Since this lower bound does not depend on the specific index 67. and the adversary chooses 83 uniformly, the expected regret in batch j (averaged over sj and A) is Es, [Ry] 2 feA.
The expected regret in
Step 3: Regret Along the Horizon and Parameter Choice. The expected regret in each batch j is E,, [2y frA. The total expected regret over NB batches for algorithm A is (r = EN Eg 2 NB.GA. Since NB = TTA,, we have RT(A) 2 (T/A) = TT..
We have set the batch length A = (cs/2))M 2 in Step 2. The other primary constraint, from Step is NBC I 1/4, which implies (T/ I 1/4. Substituting A (cs M) 2 into this
constraint:
T
e 1
Cs.
3
(cs/2)Me
cs
87
To maximize the lower bound on regret LT, we choose e be as large as possible, subject this
constraint. We set = [7
M
1/3 This choice ensures ex cs 87
Substituting this into the total regret expression:
R 2 cs M
1 T 8
1/3
1
T
Cs
1/3
M1/S
1/3 1 les 21/372/3 Cs M1/372233
1/3
8T
8 81/371/3
8
16
Since cs > is a universal constant from the identification complexity, let C cs /16. C O. Thus, (AA) 2 /3/233
d//3/16. Then
1/3
Finally, we verify the conditions our parameter choices:
1. Value of A: e² M 87
2/3
A = (cs/2)Me (cs/2)M
C -2/3
(cs/2)M
(8792/3
(cs/2) M 2//33//3
(cs/2)M
472/3
4M11372/3
(csM))77
M2/3
09 2//3
20// M /3323/33 Let CA 20//3 So A = 1/33//332/3 We need 1 15 A for to
be a valid batch length. A < T = C <
+
2/3 < 1/3 /CA
T 2 (cAM//333 = e M. This implies T must be sufficiently large relative to M. A generally holds for large T if M 2 1.
2. Constraint Ngc < 1/4: This constraint was used to determine the choice of c. With
é = esM 87
Tea
T( cgM/8 1/8 8T
(cs/2MM (cs/2)M
M/
1/2
Thus, (T/A)<= NBC 1/4 is satisfied by this construction.
All conditions are met for suitable choices of T relative to M, given the universal constant es and our choices for Pfail (e.g.. 1/4) and er (e.g.. 1/2) which determine the factor 1/8 in the per- batch regret. Thus, for any online routing algorithm A, there exists problem instance in constructed class for which its expected regret is bounded below by (r(A) 2 CM1/372/3 for
some constant C > 0 (specifically C = 1/3 /16). For a fixed number of models M > 2. In this case, the lower bound becomes 2/72333, matching the statement in Theorem
This completes the proof.
30

---

Published as a conference paper at ICLR 2026
E
EXPERIMENTAL DETAILS
This appendix provides additional details on the experimental setup, benchmarks, and results pre- sented Section S
E.1 REAL- WORLD BENCHMARK: ROUTERBENCH
Dataset Details. Our primary evaluation is based on the RouterBench dataset (Hu et al. 2024).
comprehensive benchmark with 36,497 queries sampled from eight diverse NLP datasets. These datasets cover both Chinese and English and span a broad spectrum of tasks: commonsense reason-
ing (HellaSwag (Zellers al. 2019). WinoGrande (Sakaguchi et al. (021). ARC Challenge (Clark) et al. 2018)). knowledge-base based understanding (MMLU (Hendrycks et al. 2021)), open-domain di-
alogue (MT--Bench (Zheng al. 2023)). mathematical reasoning (GSM&K (Cobbe et al. 202
code generation (MBPP (Austin et al. (02TT), and eetrieval-augmentte generation (RAG).
Candidate LLMs and Metrics. For each query, RouterBench provides pre-computed responses from the 11 LLMs listed in Table The table shows the models ordered by their release date, along with their average performance score and average cost per query across the entire dataset.
Table 3: List of LLMs sorted by release date, along with their per-query average performance score and average cost.
Model
Avg Performance
Avg Cost
claude-instant-vl
0.5900
$0.001236
claude-v1
0.6480
$0.005870
claude-v2
0.5116
$0.006153
metw/llama-2-7b-chaa
0.6059
$0.001337
0.5392
$0.000142
neta/cwee-llamm-iistteeek----bb
0.5040
$0.000550
mistralaimmistral--bbbhhh
0.4999
$0.000139
gpt-3.5-turbo-1106
0.6867
$0.000709
gpt-4- 10044-1106-preview
0.8048
$0.007943
zero-ome-ai/Vi-44B-oo
0.7153
$0.000558
mistraliimiixrral-877bcaaat
0.6504
$0.000414
F.2 ADDITIONAL SIMULATION RESULTS
To validate our framework's 's applicability to the rapidly evolving frontier of SOTA models, we con- structed synthetic benchmark using 15 recent, high-performance LLMs.
Candidate LLMs and Metrics. We consider a set of 15 LLMs, summarized in Table 4 ordered by their official release dates. For each model, we report both performance metrics Chiang et al. (2024) and associated costs. No single metric can capture the full complexity of LLM performance. We chose Elo area scores as they are community standards (e.g., Chatbot Arena), ensuring transparency and reproducibility. Importantly, our framework is metric-agnostic. The performance signal can be replaced by any other quantifiable performance measure, such as task-specific accuracy, user satisfaction scores, composite utility function combining multiple objectives.
Note that the naming AI models can highly nuanced, and multiple versions may exist under a similar label. For example, for Gemini 2.5 Pro. we used data corresponding to the Ptti-i-----r-o--eiieee--------
version. Additionally, performance scores may fluctuate over time due to model updates, shifts in the user voting population, changes in evaluation bench- marks. Similarly, costs may vary across time or across versions. The data reported here corresponds to the specific versions and conditions used in experiments.
31

---

Published as a conference paper at ICLR 2026
StageRoute Greedy
StageRoute Greedy
Stagekoute
Cumulativv Regget
1.5
Cumulative Regret
Cumulative Regret
1.5
Greedy
Random
Random
Rendom
1.0
1.0
1.0
0.5
0.5
0.0
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1,00
Query Number (t)
x10
Query Number
x10*
Query Number (t)
x301
(a) M 3.
(b) Maxx = 5.
(c) max 10.
x10
x10
x10'
StageRoute Greedy
StageRoute Greedy
StageRoute Greedy
Cumulative neegrt
1.5
Cumulative Regret
1.5
Cumulative Regret
Random
-X-
Random
-X--
Random
1.0
1.0
0.5
0.5
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Query
x10
Query
x10*
Query x10
(t)
(d) Update interval 250 rounds.
(e) Update interval 1000 rounds.
(1) b=
Figure 6: Regret with varying parameters.
Simulation Setup. These 15 models are introduced sequentially, with the first 5 available time t 1 and one additional model becoming available every 1,000 rounds until all accessible. Each model's performance is normalized to lie within the [0, 1] interval. For each model m, we set its budget weight parameter Om 0.4, except for Yi-Lightning, for which This is because Yi-Lightning is the cheapest model initially available to the algorithm, ensuring the feasibility of the mixed-integer optimization problem in every round. At each round, if the algorithm selects a model, it receives a noisy performance and cost observation, where the noise is sampled from Gaussian distribution centered around the value. In any real-world application, LLM performance metrics are inherently bounded. Our simulation implicitly respects the [0, 1] range by clipping noisy rewards this interval, with the noise variance chosen such that the probability of generating values outside the range is negligible.
set O'm. 1.
Sensitivity Analysis. Figure presents the sensitivity analysis for StageRoute on the synthetic benchmark. The results are consistent with our findings on RouterBench, demonstrating the ro- bustness of our algorithm across different model suites and settings. ataeRoutt consistently achieves low regret, adapting effectively to the concurrency cap, update interval, and budget.
32

---

Published as a conference paper at ICLR 2026
Table 4: LLM comparison by release date: performance (Arena Score/Elo Chiang et al. 2024 and output cost (per 1M tokens).
Model
Performance
Cost
GPT-4o
1336
$10.00
Gemini-1.5-pro-007
1302
$5.00
Yi-Lightning
1287
S0.14
ol-mini
1304
S0.60
Llama 3.3 70B Instruct
1257
$0.40
DeepSeek-RI
1358
S0.55
Gemini 2.0 Flash
1380
$1.50
Claude 3.7 Sonnet
1300
$15.00
Hunyuan-turbor
1296
$0.28
Deepseek-v3
1373
$0.28
Llama---Mverric
1417
$0.82
GPT-4.1
1366
$8.00
Grok-3-preview
1403
$15.00
o3 by OpenAI
1413
$40.00
Gemini-2.5-Pro
1446
$10.00
33


Reviews:
[{"review_id": "MIk6y2pGRI", "reviewer": "Reviewer_DHJM", "summary": "The authors of this paper look at a new-ish problem - which models should be deployed given a tight budget. They introduce a new method called StageRoute, which allows incoming query to be routed to an ever-changing set of models.  The authors prove some regret bounds, establish near-optimalty and also provide experiments.", "questions": "See weaknesses", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper looks at a very practical problem, how does one choose which models to deploy in a tight setup? This is very useful for practical settings\n2. I carefully checked several theorems and lemmas (not all), they look correct. \n3. The experiments are quite comprehensive. In figure 3, it is quite clear that cumulative regret is fairly low for StageRoute. The sensitivity analysis is quite nice too.", "weaknesses": "1. The paper does not do a great job of connecting with existing explore-exploit literature. Please expand upon the section why existing analyses does not apply. This bleeds into the experiments. Why compare only with greedy and random? This to me is the biggest drawback of this paper, there is a ton of literature in the MAB space that could have been used to create stronger baselines\n2. In eq(3), it is important for the authors to describe the details of the problem. Is it a MIP? IP? LP? They briefly mention this in the experiments with MIP + Gurobi, a deeper discussion is warranted.\n3. The main body of the paper does not really talk about the cost of running optinmization. How does this optimization scale? Can you reuse solutions from previous runs? How often is the problem solved? Not everyone has access to Gurobi. This is quite important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LtVdBU3kfM", "reviewer": "Reviewer_bJS8", "summary": "This paper studies the problem of managing a streaming inventory of LLMs under concurrency and per-query cost constraints. The authors present StageRoute, a hierarchical online decision-making framework for adaptive, cost-aware, and scalable deployment and routing of large language models at scale. The algorithm achieves a regret bound of $\\tilde{O}(T^{2/3})$ and a matching lower bound, establishing near-optimality. Empirically, StageRoute tracks a strong oracle under tight budget constraints across diverse workloads.", "questions": "I do not have major concerns for this version.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses a timely and practical challenge in LLM serving systems, where cost and scalability are key bottlenecks.\n2. The theoretical analysis is rigorous and clarifies the trade-off between adaptivity and learnability.\n3. The presentation and organization have improved since the NeurIPS version, with better discussion of parameter dependencies and clearer empirical exposition.", "weaknesses": "*Disclosure:* I also reviewed this paper in its earlier NeurIPS submission. Compared with that version, I find that the current paper has made several substantial improvements:\n\n1. The authors now clearly explain why the dependence on $K$ becomes invalid when $K \\ge O(T^{1/3})$, addressing my previous concern both theoretically (line 317) and empirically (line 466).\n2. While the algorithmic design still combines several existing ideas, the paper now provides a more thoughtful discussion of how these perspectives fit together, making the unification more convincing.\n3. Although the experimental setup still involves only two relatively simple baselines, the added analysis clarifies why StageRoute can approach the optimal solution, which mitigates the earlier concern.\n\n--------------------------previous review------------------------------------------\n1. **Regret Upper Bound Interpretation**: The regret bound depends on K\\sqrt{K}, where KK is the number of deployment stages. While this appears reasonable under a fixed-stage model, it becomes problematic in fully adaptive environments where $K=T$. In that case, the regret becomes $O(T)$, which suggests linear regret—a degenerate and counterintuitive result. One would expect more adaptivity (i.e., frequent updates) to improve performance, not worsen it. Clarifying this behavior or bounding regret in fully adaptive settings would strengthen the theoretical contribution.\n2. **Algorithmic Novelty**: Although the problem is framed as hierarchical, the optimization subproblems in both stages reduce to similar formulations (e.g., Eq. (7)), and the algorithmic components largely resemble standard knapsack or budgeted bandit methods (e.g., [4]). It would be beneficial for the authors to clarify what aspects are truly novel beyond the hierarchical decomposition, such as any new learning techniques, budget handling strategies, or theoretical proof techniques introduced specifically for this setting.\n3. **Limited Empirical Comparisons**: The experimental section only compares StageRoute against two simple baselines. This is a missed opportunity, given the availability of related work on budgeted bandits (e.g., [4, 8, 19, 22]) and LLM routing (e.g., [13, 25, 27, 36]). Including stronger baselines from these domains would provide a more convincing evaluation of StageRoute’s practical advantages and generality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wTv6F6OWIe", "reviewer": "Reviewer_G3fm", "summary": "The authors introduce *StageRoute* an algorithm for LLM routing that accounts for a continually updating family of models (reflecting how LLM routing must be done in practice). The authors provide theoretical guarantees for their method and an experimental analysis performed on Routerbench.", "questions": "* Can the authors add more extensive empirical comparisons to prior work on routing?\n* Additionally, the authors might consider adding a study on the choice of $K$, since this seems to be the main guidance the theory provides.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* Adapting LLM routing to an ever-changing landscape of models is a significant contribution.\n* StageRoute includes a minimax optimality guarantee that also provides practical guidance on the selection of $K$ (the number of model deployment stages).", "weaknesses": "* The theoretical guarantees seem to require that $r_t$ and $c_t$ are drawn from model-dependendent but *query* independent distributions. It is unclear to me that this assumption makes sense in the context of studying *per-query* routing; in fact if this does hold why do any per-query routing at all?\n* The empirical base lines comparisons seem lacking, the authors only compare to a greedy and random baseline, but no prior routing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BaqW7lJgWS", "reviewer": "Reviewer_ANEN", "summary": "This paper tackles the problem of online deployment and routing for streaming large language models in a realistic cloud setting where new models arrive over time and operational constraints apply. The authors formalize a novel two-timescale decision framework: at infrequent deployment stages, the system chooses which models to keep deployed (up to $M_{\\max}$ models) and at the fine-grained level, each incoming query is routed to one of the deployed models to maximize quality under cost and throughput constraints. The paper proposes an algorithm called StageRoute, which (i) uses optimistic estimates of performance (UCB) and conservative estimates of cost (LCB) to select a near-optimal subset of models at each stage, incurring any one-time deployment costs, and (ii) routes each query among the chosen models by solving a linear program that respects the long-term budget and per-model rate limits. The authors prove a regret bound of $\\widetilde{O}(T^{2/3})$ for StageRoute (with a matching $\\widetilde{O}(T^{2/3})$ lower bound), indicating that the algorithm’s performance loss relative to an oracle is sublinear in the number of queries and essentially near-optimal for this problem setting. Empirically, StageRoute is evaluated on a benchmark (36k+ queries across 8 diverse datasets) and is shown to closely track the performance of an oracle under strict cost budgets while significantly outperforming baseline strategies, demonstrating both the practical effectiveness and robustness of the approach.", "questions": "Choosing the Update Interval: What guidance can the authors provide on setting the stage update frequency (interval length)? There is an inherent trade-off: updating deployments more frequently allows faster adaptation to new models but also incurs more frequent deployment costs and reduces per-model learning time, whereas longer stages mean more stability but risk sticking with suboptimal models. It would be useful to discuss how an operator might choose the update schedule in practice, and whether StageRoute’s performance degrades if this parameter is not well-tuned.\n\nIncorporating Contextual Information: The paper notes that the routing step can incorporate contextual estimators when features are available. Did the authors explore any form of contextual routing in their experiments, or could they provide examples of what contextual features might be useful? For instance, one could imagine features derived from the query to predict which model is likely to perform best. If context was not used in the current work, do the authors anticipate that adding context would further improve performance, and would any changes be needed in the theoretical analysis to accommodate contextual bandit estimators?\n\nDeployment Cost Parameter: The formulation includes a cost for deploying a model, presumably to discourage constantly swapping models in and out. However, the paper does not detail the values or impact of these deployment costs. Clarification on how deployment costs were set and whether they had any noticeable effect on the decisions would be helpful.\n\nAdaptation to New Models: How quickly and reliably does StageRoute adapt to a newly arrived model that has superior performance? Based on the description, the algorithm will explore new models via UCB if they appear promising, but the stage commitment means a wrong decision could delay using a good model for an entire stage. The heatmap comparison suggests StageRoute’s selection probabilities eventually align with the oracle’s optimal set. It would be insightful if the authors could elaborate on this: for example, do they observe that StageRoute sometimes sticks with an incumbent model for a stage or two before “realizing” a newcomer is better, or does the algorithm typically catch on almost immediately at the next update? Understanding this dynamic would shed light on the practical behavior of the system in a continuously evolving model pool.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel Problem Formulation: The paper identifies and formalizes a unique and important problem at the intersection of LLM systems and online learning. It is, to the best of the authors’ knowledge, the first to address online LLM deployment with streaming model arrivals while accounting for a hard concurrency cap on active models, one-time deployment costs, per-model throughput limits, and a global cost budget. This formulation fills a clear gap in prior work and it mirrors real-world constraints.\n\nWell-Designed StageRoute Algorithm: The proposed StageRoute algorithm elegantly mirrors the two-level structure of the problem. It combines strategic exploration-exploitation at deployment times with tactical optimal routing for each query. The deployment phase uses upper-confidence bounds on reward and lower-confidence bounds on cost to select a set of up to $M_{\\max}$ models, ensuring a principled trade-off between trying new models and sticking with reliable ones under uncertainty. Then, within each stage, the routing phase solves a linear programming subproblem to dispatch queries in a way that maximizes expected quality while respecting the budget and per-model throughput caps. This hierarchical approach is conceptually sound and modular – for instance, the routing step could incorporate contextual features if available, without changing the deployment step. Overall, the algorithmic design addresses the identified challenges in a logical and effective manner.\n\nTheoretical Rigor: A key strength is the thorough theoretical analysis. The authors establish an $\\widetilde{O}(T^{2/3})$ regret bound for StageRoute and also prove a matching lower bound for any policy in this setting, implying that StageRoute achieves essentially the best possible learning rate for the given problem. This is a non-trivial result, as the problem’s structure (staged decisions, streaming new arms, budget and capacity constraints) is more complex than standard bandits. The regret decomposition provides insight into the costs of limited concurrency and delayed updates. Such theoretical guarantees lend strong support to the algorithm’s reliability and novelty. It’s commendable that the paper not only proposes a solution but also proves its near-optimality, meeting a high bar of technical depth.\n\nClarity and Presentation: The paper is clearly written and well-organized, which aids in understanding a complex problem. The authors provide a helpful conceptual diagram (Figure 1) and use it to explain the StageRoute workflow intuitively. The constraints and assumptions are well-motivated by real-world examples. Each component of the solution is described with sufficient detail, and important aspects like the modularity of the design are highlighted (e.g., noting that contextual routing or other extensions can be plugged in). The combination of theoretical and empirical sections is balanced, and the contributions are explicitly itemized early on. This clarity ensures that readers can follow the motivation, the algorithm, and the significance of results without confusion.", "weaknesses": "Computational Complexity and Scalability: A potential concern is the computational overhead of StageRoute’s deployment phase. Selecting the active model set is formulated as an optimization problem with combinatorial constraints (respecting the $M_{\\max}$ cap, budget, etc.), which the authors solve using a mixed-integer programming (MIP) solver in their experiments. This approach may not scale well if the number of candidate models grows large or if deployment decisions need to be made very frequently. The paper does not report runtime or complexity analysis for this MIP step, so it’s unclear how feasible StageRoute would be in real-time or large-scale deployments without further engineering. While throughput limits help throttle query routing, the stage-wise optimization might become a bottleneck as the system scales, and discussing this would strengthen the paper.\n\nBaseline Limitations: Given the novelty of the problem setting, the baselines used for comparison are relatively simple. The paper compares StageRoute mainly against a greedy heuristic (select top-$M_{\\max}$ models by a UCB/LCB-derived utility) and a uniform random strategy, plus an oracle upper-bound. These are sensible reference points, but one might wonder how StageRoute fares against more sophisticated alternatives. For example, adapting a bandits with knapsacks approach or a standard multi-armed bandit algorithm with budget constraints could be attempted as a baseline. The absence of comparisons to any prior bandit or online learning algorithms makes it harder to pinpoint how much improvement comes from each novel aspect of StageRoute.\n\nAssumption of Immediate Reward Feedback: The framework assumes that after each query is routed to a model, the system obtains a reward/quality score for that model’s answer, which is used to update the UCB values. In the experiments, this is achieved by using a benchmark dataset where each query has pre-assessed scores for each model’s response. However, in a real deployment of LLMs serving live user queries, obtaining a numerical reward signal for each response can be challenging – user feedback may be implicit, delayed, or noisy. The paper does not discuss how robust the algorithm is to noisy feedback or how it might work with proxy metrics (like user click-through or satisfaction ratings). This is a potential gap between the experimental setup and real-world application. If the reward signal is sparse or delayed, the effectiveness of the UCB-based exploration could be affected. Clarifying this assumption and its impact would be helpful, as the need for a reliable performance metric per query could limit applicability in practice.\n\nScope of Evaluation and Real-World Factors: It would strengthen the paper to see evaluation under a wider range of conditions. For instance, how would StageRoute perform with a larger pool of models or more frequent model introductions? Similarly, the study focuses on cost and throughput constraints, but other practical considerations like variable latency or model reliability are not deeply explored. The concurrency cap $M_{\\max}$ is fixed, and it’s not fully clear how sensitive the system is to this parameter beyond what's in the theoretical bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)