MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees
Authors: Herbert Woisetschläger
Ryan Zhang
Shiqiang Wang
Hans Arno Jacobsen
Venue: NeurIPS 2025 poster ()
Keywords: inference optimization
model routing
stochastic optimization algorithms
convergence analysis
Primary area: general_machine_learning
TL;DR: We propose a new algorithm that introduces guarantees for minimum user satisfaction rates in language model zoos while optimizing for operating cost, which can be practical for inference endpoint services.

Abstract: Open-weight large language model (LLM) zoos provide access to numerous high-quality models, but selecting the appropriate model for specific tasks remains challenging and requires technical expertise. Most users simply want factually correct, safe, and satisfying responses without concerning themselves with model technicalities, while inference service providers prioritize minimizing operating costs. These competing interests are typically mediated through service level agreements (SLAs) that guarantee minimum service quality. 
We introduce MESS+, a stochastic optimization algorithm for cost-optimal LLM request routing while providing rigorous SLA compliance guarantees. MESS+ learns request satisfaction probabilities of LLMs in real-time as users interact with the system, based on which model selection decisions are made by solving a per-request optimization problem. Our algorithm includes a novel combination of virtual queues and request satisfaction prediction, along with a theoretical analysis of cost optimality and constraint satisfaction.
Across a wide range of state-of-the-art LLM benchmarks, MESS+ achieves an average of $2\times$ cost savings compared to existing LLM routing techniques.

MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees
Herbert Woisetschläger Technical University of Munich h. woissttschlaegerotu..
Ryan Zhang Horace Greeley High School ryzhangofficiaa@@@aal..c com
Shiqiang Wang
Hans-Arno Jacobsen University of Toronto
IBM Research shiqiang. wangSieee.
jacobsenβeecg. toronto. edu
Abstract
Open-weight large language model (LLM) zoos provide access to numerous high- quality models, but selecting the appropriate model for specific tasks remains challenging and requires technical expertise. Most users simply want factually correct, safe, and satisfying responses without concerning themselves with model technicalities, while inference service providers prioritize minimizing operating costs. These competing interests are typically mediated through service level agreements (SLAs) that guarantee minimum service quality. We introduce MESS+, stochastic optimization algorithm for cost-optimal LLM request routing while providing rigorous SLA compliance guarantees. MESS+ learns request satisfaction probabilities of LLMs in real-time users interact with the system, based on which model selection decisions are made by solving a per-request optimization problem. Our algorithm includes novel combination of virtual queues and request satisfaction prediction, along with a theoretical analysis of cost optimality and constraint satisfaction. Across wide range of state-of-the-art LLM benchmarks, MESS+ achieves an average of 2 cost savings compared to existing LLM routing techniques.
Introduction
As the number of open- large language models (LLMs), such as Llama (8). Granite 11
Qwen [19], increases rapidly, deep learning infrastructure providers and end users are confronted with an abundance of models (model zoo) for their language processing tasks. Typically, each LLM family comes with at least three models, each with different capabilities and resource requirements (Figure T). Sometimes, there is an update to the model weights that released as minor checkpoint (e.g., Llama 3.1 70B and Llama 3.3 70B). This leaves many users questioning what is the best model use and whether common benchmark results apply their specific needs [16]. Currently, the best way to approach model selection is educated guessing, using LIM benchmarks as proxy to estimate model performance, or spending significant efforts to curate human- premannpeeeerece datasets for request routing [18). Since working with L.MSs can be expensive (22,, minimizing costs is an equally high priority for end users and inference endpoint operators. This leaves us with the following tri-fold problem.
End-users primarily care about factually correct and safe model output. When inquiring about text information, e.g., by asking questions or requesting language translation, end users are mostly interested in obtaining factually correct and sufficiently clear language output [26]. Additionally, many users are unfamiliar with the technical details of LLMs, making it challenging for them to select the right model for the job, i.e., their primary references are domain-specific benchmark
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

rankings 19 10]. However, there is no intuitive method to compare the complexity of individual requests with benchmark tasks. Thus, we require a method that learns over time whether a model can satisfy an incoming request as users interact with L.MSs.
Inference endpoint providers prioritize low operating costs, and emerging AI legislation requires sustainable computing best practices. Operating infrastructure that
80
70B models
models
Opan LLM Lockubbard Boarn (Aug.)
40
can run state-of-the-art LLMs can be costly. Microsoft has announced it will acquire a stake in the Three Mile
3B models
Island nuclear power plant in the United States to satisfy the energy demand of its planned data center in Pennsylva- nia, which has two reasons: consistent energy delivery and
50
1B models
Model Family
low energy cost [0]. At the same time, globally emerging Al regulation (e.g., EU AI Act Article 95) [6] emphasizes energy monitoring and compliance with sustainable com- puting best practices. Taken together, tighter regulation and ever increasing cost underpin the necessity of energy- optimal service operations. The current operating model of many inference service providers where only a single model is served per dedicated endpoint does not offer the necessary flexibility to keep cost in check. When aiming to provide cost optimal inference endpoints, need method that can choose the most efficient model that is likely to satisfy incoming request.
GoogiaCarmma
IBMCrerile3.
I0MIGrante-3
MetalUama 3.3
Metailaama 3.1
Owan/Owen-2
10"
10"
10"
No. Model Parameters (og)
Figure 1: OpenLLM-Leaderboar per-
formance comparison of popular LLM families. Each family typically consists of minimum of three models with dis- tinct capabilities and cost characteristies.
Enterprise use-cases require a consistently high-quality model inference output while keeping costs in check. This unites the requirement for high-quality model outputs and price sensitivity. Thus, commercial players typically rely on service-level agreements (SLAs) when sourcing services for their own products. An example of an SLA is one that specifies percentage of requests to be automated by LLM-powered AI agents, while the remaining requests need to be handled by human experts. Typically, different SLA levels offer different quality standards at different prices. However, to date, it is usually up to end users to decide which models to use for their requests without any lower bounds on request satisfaction guarantees. As such, this is neither cost effective for the inference endpoint provider nor for the end user as both tend to overpay on operating costs and inference response costs, respectively. Thus, we require method that minimizes operating costs while guaranteeing SLA compliance, i.e., a minimum request satisfaction rate over time.
In summary, we ask the fundamental question:
How can we design algorithm for selecting LLMs from model zoo that mini- mizes the operating cost while providing rigorous SLA compliance guarantees?
This problem is challenging in several aspects. First, we need to find a way to learn whether an LLM can satisfy incoming request as users interact with an inference endpoint over time. Second, we require a method to guarantee SLA compliance over time, while allowing the inference service provider to minimize their operating costs. Taken together, we have guarantee that our per-request routing decisions rigorously satisfy an SLA requirement while ensuring cost optimality.
Contributions. Our paper introduces MESS+ (Model SElection with Cost-optimal Service-level GuaranteeS), new stochastic optimization framework for minimizing operating costs and rigorously guaranteeing SLAA compliance. Compared to existing LLM request routing techniques, we offer solution to cost optimal request routing and provide a lower bound request satisfaction guarantee. Our approach dynamically learns request satisfaction probabilities in an online fashion users interact with the system and makes routing decisions based on operating cost and request satisfaction over time. We provide theoretical guarantees for cost-optimal SLA compliance with model zoos.
Related Work. While prior works in LLM request routing have made significant contributions in various directions (Table MESS+ distinguishes itself through its formal optimization approach to cost efficiency with rigorous SLA guarantees. Specifically, RouteLLM 18] Zooter [15], and Rou- terDC 3 focus on optimizing routing decisions based on model capabilities and query characteristics without formal SLA guarantees. through ensembling and selffverification approaches, respectively, without providing guarantees for
[12] and AutoMix (1 emphasize quality improvement

---

Table Related work overview. We are the first introduce cost-optimal stochastic optimization framework for LLM request routing with SLA guarantees.
Apprach
Technique
# of LLMS 7oa
Cost-
Service Level Guarantee
Source
LLM-Blender
LLM Ensemble
2
Jiang al.
12
AutoMix
Sell Verification
2
Aggarwal et
11
Hybrid-LLM
Preference Duta
Ding et al.
Zooter
Reward-Model Labels
Lu
RouterDC
Contrastive Leaminng
>2
Chen al.
TensorOpera Router
BertSim Scores
>2
Stripelis al.
24
RouteLLM
Preference Data
2
Ong ct al.
[8
MESS (ours)
Satisfaction Scores & Online Optimization
>2
This paper
lower bound request satisfaction rate time. Similarly, Hybrid-LLLM introduces quality-aware routing between models of different sizes, and TensorOpera Router [24] balances performance metrics empirically. In contrast, MESS+ uniquely formulates request routing stochastic optimization problem that minimizes operating costs while providing a minimum request satisfaction guarantee over time, adapting dynamically through online learning as users interact with the system. This optimization- approach with provable guarantees positions MESS+ as the first framework to deliver cost-optimal SLA compliance in LLM zoos.
MESS+: Model Selection with Cost-Optimal Service Level Guarantees
The overall goal of MESS+ is to find the most suitable LLM for each inference request t E 21, ..... T} to minimize the operating cost Em,t, while conforming to model performance con- straints defined by an SLA over time to ensure contractual compliance.
2.1 Problem Formulation
Consider language model zoo with M different L.LMs. For every request I, each model associated with user satisfaction 8m,t E (0, }} indicating whether model m can satisfy the 1-th request, where m E , The value sm,t is unknown before request t arrives.
Inference Cost (Objective). Each model in a zoo incurs certain amount of cost Em,e (e.g., cost for an API call, energy consumption of inference request), which can vary greatly based on the model and inference request size. For instance, a zoo can include models with 1B, 8B, and 70B parameters. These differences size make costs volatile. unsure which model fits their request, they are likely to always choose the largest model, making model serving expensive, rendering costs even more volatile and overall hard to predict.
scenario where users can choose the model and are
Service-Level Agreement (Constraint). Typically, contracts related to a service contain a list of requirements, including an SLA defining minimum service quality. The SLA functions as measurable control system with defined input variables, output metrics, and acceptable tolerance ranges. We define requests that need to be served with a satisfactory LLM response over time.
be the target request satisfaction rate over time i.e., the relative share of
Control Problem. Taking the objective and constraint together, can formalize the following problem of minimizing the average operating cost per request under a minimum performance requirement defined via SLA over time:
min (ym.
E MM E Jym,t Fmme] 1 Er MM
(1a)
s.t.
E ym, 2 a,
(1b)
M
Um,t = 1, Vt E (l,...,TT.
(1c)
Um.1 E {0, 1), Vt E (1....,T).. (1,...,
(1d)
where Um. = model m is chosen and ym,t = 0 otherwise.
In practice, a should be chosen with certain safety margin from the SLA requirement such that we do not violate the SLA even if the average request satisfaction is slightly below

---

Challenges. Our optimization problem involves an inherent trade-off between request satisfaction and operating cost, since larger LLMs, and thus more capable ones. typically yield higher satisfaction rates while consuming more resources at the same time. As such, we see correlation over time between the objective and constraints. Further, optimizing the operating cost involves a time average that hard to predict priori as the properties of future requests are generally unknown and heterogeneous.
2.2 Online Decision Making
Algorithm 1: Model SElection with Cost-optimal Service-level GuaranteeS (MESS+)
We introduce online decision making process that addresses the aforementioned challenges. The quantities Em. and 8m,t are captured for every request without knowledge of future statis-
Iaput: 2, V. learning rate f). > 0, V
Output: (ulm,t:
dutputs chosen models for Initialize Q2 <- 0, random vector
ties. The full procedure of MESS+ is described in Algorithm
2 for z to T
Compute Pt min (1,
Sample X2 Bernoulli(p)):
Methodology. Our approach is inspired by the Lyapunov drift-plus-penalty framework [17]. with novel extensions to support a request sat- isfaction predictor that is learned in an online manner and used in per-request model selection decisions.
Xt Lor = then
// Explore model zoo Mou.t 4- 1, Vim; all models queried foreach m E 2,.,, M) do Obtain true request satisfaction am (t):
1.
+ T/ FF.,, ax): // SGD using request content at m2" - max $m,.2
10
11
else
Request Satisfaction Prediction. Since sm,t is only known after invoking model m, we need mechanism that predicts whether model m will meet the request satisfaction requirements, so that can select an appropriate LLM for every incoming request before the request is sent any LLM. We learn a predictor Sm,t E [0, 1] online that predicts the probability that model m can satisfy an incoming request for all request-
// Online decision making user satisfaction predictor
12
Predict request sotisfaction probubility &mc Vms arg min V Fim.t + Qi(a Am,
// Solve Problem
B
14
Um + 1,9m' <- 0, Van of m²: Mi - ns5
15
16 Get output from model mn" and accuracy 8n." 6 Que <- max(U, Qs + smtt..; // Virtual quoue update
model combinations. The predictor takes the request as input and extracts useful information of the request using a lightweight model to make the prediction. For different requests, the prediction S,,, is usually different. The detailed procedure of this prediction is described in Section 2.3
Virtual Queues. We capture SLA violations, i.e., accumulated undershooting of a, in virtual queue Q with the following update procedure after receiving and processing request t:
Q++1 = max { (0,Q0 a Um...m,f
where for / t 1, we initialize Q = 0. Intuitively, this captures the cumulative constraint violations, which can be seen by comparing (bb) and (2). Hence, we aim to collectively minimize our objective
Ia and the queue l
Decision Problem for Each Request. We aim to minimize the operating cost of every inference request i while complying with our SLA requirement a. This trade-off is formulated as follows:
M da Emmiimm.Em.. + Qe (a EM Bm.t
min Yom (Vmm
(3a)
S.t. Constraints Ic.. (Tc)
(3b)
As SLAS come in various configurations, we introduce the parameter V > 0 in (3) that controls the speed at which we reach a and the trade-off between operating cost and time at which we can guarantee constraint (SLA) satisfaction. The effect of V will be further discussed in both theory and experiments in later sections. In particular, constraint satisfaction is theoretically guaranteed for large enough 7" (see Section 3). When V is small, the constraint violation decreases faster in T,, i.c., we achieve the SLA requirement a more quickly, but the cost is higher, and vice versa. In practice, see that fixed V obtained from coarse tuning works reasonably well across wide range of benchmarks (see Section 4).
We note that the average satisfaction rate over requests needs to be greater than or equal to a in the constraint, so the direction of inequalities in the constraint is opposite to [17] thus our queue update equation in ? is slightly different from that in [17].

---

Note that we assume that the user satisfaction is captured immediately after the LLM response is generated. In practice, users would be shown feedback prompt assess the response quality or request human assistance if the response is unsatisfactory. Therefore, in 2 we use 8m, to update the virtual queue length to capture the actual constraint satisfaction, but we use 8,,t, Vm, to solve the
per-request optimization problem (3) We consider the operating cost per request Em, Vm, f, to be known once we receive the request and obtain some of its basic information, e.g., number of tokens in the prompt.
2.3 Request Satisfaction Prediction
We now describe how to obtain the predicted request satisfaction probability &m,,. Vm, 1, which is required to solve 33. To facilitate the description, let z, denote the parameter vector of the lightweight request satisfaction predictor used for request t, and a, ~ A denote the t-th input request sampled from some distribution A. The predictor provides an M-dimensional output á(z,, ar), which includes {sm.s. Vm]. We write the m-th component of the output vector as $(z,, at)m = Sm.e. We omit the subscript in z in the following when it is unnecessary to specify the request index t.
We define the regularized cross entropy objective of request satisfaction predictions for over all possible incoming requests and for all models:
F(z) == -1 Ma
Em= (sm, log 8(2, a m + (1-88,;) log(1 8(2, an) )m) + ||]| (4)
M
where the last term is regularization term when μ > 0.
We learn z through a probabilistic exploration and update procedure. To explore the model zoo, we query all model with the same input request to obtain their actual request satisfaction 8m.t. allowing us to learn z. More specifically, as shown in Algorithm we sample from a distribution X, ~ (ernoullippt). where the exploration probability Pt = min(1, V and > 0 is parameter that adjusts this probability. The probability Pt decays over time as the estimation $,,t improves with each exploration and update step. The larger c, the more likely it is to perform an exploration step over time. When exploring, we always use the output from the largest model as the final model output as we have already incurred operating cost to query the largest model, i.e., we do not use the solution from (3) in this case and return the output of the largest model. Especially for the first few arriving requests, when we do not know how to choose the optimal LLM for request t, we must explore each m in the model zoo for the best-performing model for each request. In this way, we capture the actual user preference 5m,t of each m, which we use to learn z.
We note that the predictor we train here only predicts whether each model m can produce satisfactory response to an incoming request. Different from related works such as [3] [8]. we do not use this trained predictor as a router directly. Instead, the output of the predictor is fed into the per-request
optimization problem (3), and the model selection decision is obtained by solving (3).
Key Insight. The key idea behind exploration and predictor update with a probability ps that decreases in is to strike a balance between obtaining an accurate predictor and limiting the additional cost incurred due exploration. If p, decreases too fast in it will take long time to obtain accurate predictor although the cost overhead due to exploration is low. In contrast, if pr decreases too slowly in 4, we obtain an accurate predictor quickly, but the cost overhead is also high since do many more exploration steps than it is actually needed. By choosing pt = min (1, री ). we have a good balance between the predictor accuracy and exploration cost overhead, as also confirmed by our theoretical analysis in the next section.
Performance A Analysis
In this section, we provide a theoretical performance analysis of our proposed MESS+ algorithm. We focus on showing constraint satisfaction and optimality of our solution. Since SLAs are often volume-basede service quality guarantees are typically given for specific number of requests or
Practically, this can be done by profiling the cost of inference calls before adding model the zoo. for all m to reflect that all the models are queried during
'In Line 6 of Algorithm| we set Vo.. exploration. This is with slight abuse of notation, since this choice of {Um,.} does not satisfy (Ic). However, we this configuration to indicate that cost has been incurred for querying all the LLMs.
5

---

transactions. Thus, we focus on obtaining results that hold for any T 1 in our analysis, instead of only considering oc as in [7]. As commonly done in the literature, our analysis relies on some reasonable assumptions to make the problem mathematically tractable. The full proofs for all the following theorems are provided the appendix.
3.1 Constraint Satisfaction
Assumption 1. Let vi := arg máX 8m,t and vi 2 0 be some constant independent of the total number of requests T and 1b < T. We assume that, when / v,, there exist / > 0 and q E (0, 1], such that for any m (inclusive of m) with - - Sm. S B, we have Pr(sm. = 1] 2 > a.
This assumption states that, after finite number of requests v our request satisfaction predictor becomes accurate enough, so that models within a certain range 3 of the maximum predicted satisfaction guarantees that the minimum probability of actual satisfaction
least q >
Theorem 1. For any t 2 1, we have the following upper bounds on the virtual queue length:
E [Q+] S max { cnp; VAR +Vt and +E=nE(QQ S mmax an/;;
VAR 3
(5)
where AE :- Emax Emin- in which Emax and Emin are the maximum and minimum operating costs of any model, respectively.
The proof for Theorem is based on a unique observation that, when Qi > max {arh; /Ag/B)
). the
solution to 3 guaranteed satisfy $ &m-.t .t S 3, where m denotes the solution to (3) such
that Vm st 1. The final result is then obtained by bounding the Lyapunov drift of an auxiliary queue capturing how much Qi exceeds max {aob; VAn/p]. Based on the queue update in (2), it is easy to obtain the following corollary.
Corollary 1. We have the following upper bound of constraint violation (averaged over time):
a E EM= [8m,)
B[Qr] max
VAB
O
(6)
T
We observe that the constraint violation is guaranteed to be arbitrarily small when T is sufficiently large. If full SLA compliance (denoted by a') needs to be guaranteed after a finite number To of requests,
choose be slightly larger than a', so that max oat VAg 7o 3Tb
+ aa
which holds for a = a' VAE + vTh when To
or < VAg practice, as we see in our experiments
3Th
3To
in Section 4 our MESS+ algorithm satisfies the constraint empirically after a relatively small number (e.g., slightly more than thousand) of requests even if we use as the SLA requirement directly.
3.2 Cost Optimality
Assumption 2.
We assume that both the input request content a, and cost Em,., Ym are i.i.d. across while for the same t, Emmt may be dependent a,.
Assumption& 3. The predictor training loss F(z) is L-smooth. It also satisfies the -oabykk--ojasiwiizz (PL) condition with parameter 1a > 0 (and < L), i.e., _ [[))(2 2 (F((() - Fmiu). Vz, where Fmin == min, Fz)). Its stochastic gradient is unbiased and has a bounded variance of o² i.e.,
Fz a) | v (z) and EE| [ a) VF(2)]1 |z] < a2, Vz, where VF(z, a) denotes the stochastic gradient of Fzz) sample A.
Assumption is commonly used in the Lyapumov drift-plus- tluu--penatty framework [17 and Assumption 3 is common stochastic gradient descent (SGD) convergence analysis. In our experiments, empirically show that MESS+ also works well in non-i.idd settings (Appendix (C..2).
Theorem 2. For {ym.t : Vm, 1) obtained from the MESS+ algorithm (Algorithm)) 7 there exists learning rate schedule [m Vt), such that we have
E
T 11=1
EM- Umn Emm.)
EOPT O
+ +
MFmin).
VT
where FOOT is the optimal solution to T that is obtained from an idealized stationary policy which assumes full statistical knowledge of requests in (I....

---

The proof of Theorem 2 jincludss key novel steps to capture the joint effect of per-request optimization in (3), the error of the request satisfaction predictor, and the additional cost incurred due to exploration for training the predictor. The latter two aspects do not exist in the framework in 17 In particular,
we first bound the drift-plus-penalty expression and obtain term E. [Qt] E[[ max m | 8m,
in the bound. Then, we further bound the prediction error E maxm / ||mm.t - Sm,a ]] using SGD
convergence analysis while considering properties of the cross-entropy loss 4.. where the number of SGD steps for predictor training (Line A Algorithm| D is related to the exploration probability Pt O1/4). We also incorporate the cost overhead for exploration that is ((M//T) Combining these and using the average queue length bound in Theorem 1 we obtain the result.
We have several important observations from Theorem 2 First, combining with Theorem I we can confirm that V controls the trade-off between cost optimality and constraint satisfaction, where a larger V boosts cost optimality but slows down constraint satisfaction, and vice versa. Second, the cost optimality gap depends on M Finu. where we recall that M is the number of LLMs in the zoo and Fiin is the minimum loss that can be obtained for training the request satisfaction predictor. When the predictor is capable, Fmin is small, which is what we also observe in the experiments in Section Finally, when we choose V = vT, we can observe from Theorems | and 2 that, as T co, MESS+ guarantees full SLA satisfaction and approximate cost optimality up to M Fiin. i.e, the minimum loss of the predictor times the number of LLMs in the zoo.
4 Experiments
We demonstrate the effectiveness of MESS+ across a set of experiments with state-of-the-are LLM benchmarks. Our code is publicly available and we provide full experimental details in the appendix.
4.1 Setup
Language Model Zoo & Benchmarks. Our model zoo is comprised of three models: Llama 3.2 1B
(LIB), Llama 3.1 8B (L8B), and Llama 3.3 70B model (L70B).. We use the LM-Eval Harness [10] and deploy three reasoning benchmarks (ARC Easy, ARC Challenge, and Winogrande) [S] 21 as well as five Q& benchmarks (BoolQ, LogiQA, PIQA, SciQ, and SocialIQA) 12 13 14 23 All
benchmarks are evaluated zero-shot. On per-sample basis, the benchmarks generate binary feedback signals that indicate whether request has been satisfied. These binary signals are used as labels for training our request satisfaction predictor.
Request Satisfaction Predictor. In line with related work [18), we choose ModernBERT 255 as a transformer backbone and implement a multi-label classifier on top of it, where each label corresponds to whether a model can satisfy a user request. We freeze the transformer parameters and only train the classifier with SGD. The classifier is trained online while running each benchmark as described in our algorithm. We set 0.1, if not specified otherwise.
User & Service Provider Requirements. For each benchmark, we consider a pre-defined a stating the minimum request satisfaction rate over time. In practice, this is specified in the SLA between the user and service provider. The value of a in our experiments is set individually for every benchmark, based on the capabilities of the models in our zoo. To complete the SLA, a user and service provider need to agrec on the cost of an inference service, i.c., they need to negotiate how many SLA violations are acceptable in the beginning. The service provider sets V accordingly, minimize operating costs over time. Regardless of V. MESS+ will eventually converge towards a, as our theory has shown; V only defines how long may take. We set V 0.0001 by default. Since SLA metries are usually measured over period of time instead of instantaneously, it is sufficient to satisfy SLA requirements after a pre-defined number of requests.
Objective. We measure the effectiveness of MESS+ by its ability to meet a at minimal operating cost. In our experiments, we the per-request energy consumption when querying an LLM (measured in megajoule, MJ) as the cost metric. We also present the model call ratio, i.c., the share of benchmark requests routed to each model.
Baselines. We first look at each individual LLM with regard to their operating cost and request satisfaction capabilities. Then, we compare MESS+ with three adaptive routing baselines, namely
MESS+ code repository: https//ggttub..oo//mmmnni/t//
7

---

Table 2: Main results. Performance across three reasoning and five Q&A benchmarks. Green highlights all methods that satisfy the service level requirement a and red all violations. The most cost efficient single model satisfying a underlined and the most efficient adaptive method is highlighted in bold. We report operating costs in megajoule (MJ) energy consumption. For a full overview with more a variations please see the appendix.
Benchmark
ARC Challenge (a= 50%)
ARC Easy (a
15%)
BookQ (or -00%)
Method
Openating
Satistaction (in
Request.
Model Rutio
01770B1L/8111111
Cost do MJ) Satisfactios (on
Operzting
Request.
(177081L/111111
Rutio
Operzting (In
Sansfaction dn
Reguest.
(1.701/L/111111)
Model Rato
Liama 5.2 18 only
57 7788
0% 10% / 100%
62 62.76
0% /0% / 100%
0.14 0.4
69.17
0% / 100%
1lam 5.1 8B only
54. 54.44xx
0% 100% 10%
0.97
79, a2
0% 100% 10%
84. 16
0% 100% 1009%09 0%
Llama 3.3 708 only
2.35
60.84.a.a
100% 10% 00%
83.12
100% 10%
3,40-am0
88.78-2.0
100% 10%
Educsted Cuunseing
51.65
35% 31% 14%
2.
74.00z
31% 5256 166k
53% 54%% 53%
RouteLLM [X]
51.17-250
50%
22.54.2.2
2,96
26.83
87%
70% 13%
RouterDC B
2,03.
60.94.a.
899%
1255 008
3.61
22.30
85% 1596
2.14
87.06
5898
0%
MISS- (wurs)
0.83 o
53. 13.64.mm x9
41%%
/419%/
18%
1.74 90
22% /61% 18%
0.90
82. 16 Pm
31% /45%
/24%
Benchmark
LogiAA (o-
40%)
PIQA (o 78%0
SeiQ (n 9650
Method
Openstin
Request
di
Model S82.1R)
Opensing
Request
Model 883.1R)
Openatiag Cool Satisautiun Jn
Reguest
Model
Llama 3.2 1B only
0.17uuu
27.19 w7.
0% 00% / 100%
0.07
74.05...m
0% /0% / 100%
0.10
93. 93.80
0% 186/00%// / 100%
Llama 5.1 88 only
29 03
0% / 100% 1 10%
0,36
79.33
D% / 100% / 00
0.44
97.00g2..
OS6 / 100% 0%
Lluma 3.3 708 only
4.11
39.31...0
100% 10% 10%
1.84
N2.70
100% UU%
2.23
47..00
0/%
Educated Guuessing
22%
0.76
34% 5256 34%
515 3666 52%
Rounel 1.M [X]
10%
78. 15
00% 54%
2.
95%
(9%
RouterDC
[]
70%
/
2..4
97.95-a.u
$256
0%
MKSS (ours)
11102 00
5998 / 1778 23%
2.67
79.20 34
35%
/4556 19%
96.01.a.e
27% / 5.95 54%
Renchmark
SociallQA to-
44%)
Winogradde (tr
70%)
Avg. armoas all Reschmarke (o - 6668
Method
Opecating
Requeet
Upecaning (in
Request
Upecating
Requeet
Model
(170BB 282))10)
Satisfctton (in
300.19)
Satisfaction din
(1:70M
Llama 3.2 1B only
0.13-aum
41.7
10% / 100%
59.67
0% 10% / 100%
0.12
58.28-444
0r&/O0% / 100%
Llama 5.1 8B only
48. 1
0% 100% 10%
0.25 a.25
73 6444
0% / 100% 0%
0.54
68 20
0% / 100% 0
Llama 3.3 708 unly
3,00
48 67.7
100% /0%//0%
1.29
79 29.08
100% 0% 00
291
73,70
100% /0%
Educated Guescing
..22
47.7
33% / 32% /35%
70.67...
35% / /00 35%%
67.47-am
36% / /31% 33%
RouneL [8]
44
65%
3356
1.27
97%
2,04-0aa
71.19-a.4
82% 1.0 1856
RouterDC g]
2.89
46.76-2
95%
7.5%
80.6--21
1001
10% 106
2,11-6as
73.17-20
85%
155% 0%
MRSS- (murs)
0.67. m
45 88 14
2258. / 3886 /415
0.52 14
73.572414
43% /400
17%
1,08 46
68.44_a
34% /40% 22/5
RouteLLM 18. RouterDC 3], and "educated guessing". We configure RouteLLM with their BERT-based router model configuration. Note that L only supports routing between two models, so we set the small and large model to L1B and L.70B, respectively. RouterDC supports routing between multiple L.LMs, i.e., can route our entire model zoo. We adopt the configuration from the RouterDC paper [3]. Additionally, we employ an "educated guessing" baseline that randomly chooses an LLM by assuming the availability of prior knowledge on the probability that each LLM satisfies the request, while conforming to our SLA requirements over time. For all the baselines, we tune available hyperparameters so that the baselines satisfy the SLA requirement while being the most cost efficient. We provide further details on all the baselines in the appendix.
4.2 Results
We divide our evaluations into four main segments and an addendum focused on practical aspects. First, we evaluate at the overall cost optimality objective. Second, we look at the request satisfaction rate. Third, we explore the control dynamics of V. Fourth, we explore the routing overhead and how to train the predictor. We then evaluate the characteristics of MESS+ by looking into sparse user feedback and increasing the number of models in a zoo.
Cost Optimality. The main results are shown in Table 2 where we set individual SLA constraints per benchmark. Our key observation is that, among all the adaptive methods, MESS+ is consistently the cost optimal solution for achieving target request satisfaction rate, which is due to its effective model choice. While the baselines prefer choosing larger and more expensive LLMs from our zoo, our approach tends to rely more cost effective and smaller models, while providing satisfactory responses at the rate specified by a. By selecting larger models, the baselines overshoot our SLA requirement the expense of a notable cost overhead. Overall, MESS+ is about 2x more cost efficient than existing model routing techniques and 20% more efficient than our random baseline that knows average benchmark statistics when routing request.
Request Satisfaction. For users, is key that their requests are getting responses with a guaranteed minimum satisfaction rate, so that they can reliably offload tasks to an Al co-pilot. When looking
8

---

(V-0
(V--50220)
Edu
RowesLM
RouterDC
Aug Cost (J) Ren Saisdection
80%
80%
60%
605
SLA caidial ora 653
60%
SIA anstied
500
1000
500
1000
1000
1000
1000
1000
0
500
1000
500
1000
500
1000
Request
Request
Request
Figure 2: We run several experiments on the Winogrande benchmark with varying a and V configura- tions to show the request satisfaction and cost dynamics over time. With MESS+, the average request satisfaction rate always converges toward a. We further report the first step at which the highest V value satisfies our SLA requirement. Other benchmarks are in the appendix.
Table 3: Routing overhead compared to the average per inference call cost per benchmark. The routing overhead remains well below 10% of the average inference call cost and depend largely on the sequence length of incoming requests. The average inference call costs per benchmark are computed
across all LLMs in a ZOO.
ARC Challenge
Easy
BaolQ
LogiQA
SciQ
SeciallQA
Winegrande
Avp
Avg. Predicter
5.75.m
5.89
16,00
13
15.12amas
26.6
1.89
18.4
Aug. LLM ())
236.17
273.44
263 aa
30..50.
434.69
Prodiction Overhead (%)
1.15
a.
5.12
4.
at how precisely an adaptive routing technique approaches the SLA requirement o, MESS+ usually shows the smallest margin, ie., with MESS+ routing the LLM z0o provides responses that are closely matching the SLA requirement and therefore cost optimal. All other dynamic routing techniques tend to overshoot a and prefer the strongest model the zoo to satisfy responses. Our "educated guessing" baseline also undershoots in some cases, which renders it impractical for minimum service level guarantees, in addition to its requirement of prior statistical knowledge that is usually impractical to obtain. In general, overshooting a naturally means higher per-request operating cost. Practically, MESS+ needs a pre-defined number of steps to converge towards a, which is acceptable from an SLA perspective as discussed earlier.
Effect of V. As discussed in previous sections, V controls the trade-off between the speed of convergence to constraint satis- faction and cost efficiency. Figure[showe shows that choosing a large V leads to longer convergence times for constraint satisfaction, regardless of the value of a. Conversely, a small value of yields constraint satisfaction within a short amount of time at the expense of increased operating costs. This manifests the varying operat- ing costs per request over time. When comparing to our baselines, we observe that MESS+ offers the lowest per-request operating cost among the dynamic routing approaches by a large margin.
Training Log
2
D.1
1.0
1000 Request
2000
Exploration Cost (in MJ)
0.4
0.35
Routing Overhead. Adaptive routing incurs a cost overhead for routing an incoming request to an LLM within a zoo. We measure the cost to make this decision with MESS+ across benchmarks (Table 3. For incoming request, obtaining satisfaction prob- abilities from our predictor incurs a minimal cost overheud of 4.65% on average, compared to the cost for making an inference call to an LLM. Overall, the cost for making a request satisfaction prediction depends on the length of the incoming request.
0.2
0.04
0.01
0.01
0.1
1.0
Figure 3: Predictor training per- formance, averaged across all benchmarks. We control the ex- ploration probability of MESS+ with c. Our predictor learns ef- fectively with a small c already.
Predictor Training. As MESS+ requires online learning of predictor that predicts the request satisfaction for every LLM in the zoo, we study how the rate of exploration that parameterized with e affects both the predictor training convergence and cost overhead incurred by exploration and training. Our study shows that a relatively small value of e already leads to sirong predictor within shori amount of time (Figure 33, as shown by the training loss. The lower we choose e the faster we move from exploring the model zoo in the beginning towards using the MESS+ objective (3 for model selection decision making.

---

Table 4: MESS+ provides strong performance even when users provide sparse feedback (i.e., only when a user sends a feedback signal).
Benchmark
ARC C. (a 50%)
ARC (a 75%) 20%
BoolQ (n 20%
20%) 100%
LogiQA 20%
40%) 100%
Feedback Density
20%
100%
100%
Request Satisfaction %))
50 10.20ga
70.64
15 1.69
75.66
17 0.87
20
40.22.00s 2.47.0.00
Cost (in MJ)
2.79
0.83..mm
1.74
0.90
2.
Benchmark Feedback Density
PIQA
78%))
SciQ
96%)
SociallQA
44%)
Winogrande (a 70% 20%
20%
100%
20%
100%
20%
100%
100%
Request Satisfaction (in %))
18.48
96.08 1.
96. L..ce
44.24
70.97 10.53
30.36
Cost (in MJ)
0.64-c.o
0.67
0.81 +0.02
1.83
0.66
0.67-mmm
0.50-m..
0,52
Sparse User Feedback. MESS+ relies on online user feedback. We evaluate how the performance of MESS+ varies when only a fraction of users actually provides feedback for requests that would normally be used to train our predictor. We compare perfect conditions (full feedback) to sparse feedback with 20% of requests receiving user feed- back. Our approach maintains strong performance when introducing sparsity (Table (4)
Over time, both the dense feedback and sparse scenario provide strict SLA compliance and in- cur similar operating cost. The operating cost for the sparse feedback are slightly lower than with dense feedback. This is because of Q re- ceiving fewer updates and a prolonged time to stabilize, which leads to higher favorability of smaller and cheaper models in the zoo in the beginning (avg. 1.05 MJ vs. 1.08 MJ across benchmarks).
Table 5: Main results with larger model zoo containing models from the Qwen 2/2.5 family. MESS+ scales well as the number of models grows and shows effective routing capabilities. Detailed results can be found in the appendix.
Calegury
Menn 67%)
Subcategory
Operating Cost
Request Sutisfaction
(328:076/QU.SB/QU
Model Call Ratio
Qwen2 0.58
0.12
54, 14.12246
USS 70% / UFS / 100%
Qwen2 1.5B
0.16
61.13
0%% / (S% / 100% 70%
Qwen2
0.40
67.07
101%
Larger Model Zoo. To demonstrate the scala- bility of MESS+, we deploy a larger model zoo containing four models: Qwen 2.5 32B (Q32B), Qwen 2 7B (Q7B), Qwen 1.5B (Q1 (B), and Qwen 2 0.5B (Q0.5B). The zoO not only is larger but also contains models that have more similar cost characteristics than our LLama3 model zoo. This makes routing in our case more difficult. Our approach exhibits strong performance and strictly maintains SLA compliance under these more challenging conditions (T. Specifically, our routing approach outperforms existing baselines in terms of cost efficiency by a factor of up to 1.6x, demonstrating the suitability of MESS+ for providing the most appropriate models for any incoming user request even in larger model zoos.
Qwen2.5 328
1.60 km
70.91 2
100% 0%%
0
Educated Guessing
0.99
67.02 am
53% / 266% / 111% 10%
RouteLLM
1.37
69.01
83% (0% / //2/ 17%
RouterDC
1.13
69.17-2.0
17% 9% 11%%
MESS+ (ours)
0.84 1.:00
67.55 1.00
48% / 266% 110% 16%
Conclusion
We have presented MESS+, which is a novel theoretically grounded method for automatic model selection in language model zoos. On average, our approach reduces operating costs by 2 compared to well-established adaptive routing baselines in the literature, while still satisfying SLA requirements. Overall, MESS+ shows strong generalization across various state-of-the-art benchmarks and the first approach to optimizing operating costs while providing rigorous service level guarantees, when serving user requests with model zoo. Further, our online-learning based approach to model selection removes the need for curating routing preference datasets. Our technique can be particularly useful for cost-aware systems that serve seasity-sensitive workloads and require a lower-bound on user satisfaction rate.
While our work shows strong performance across a wide range of tasks, we observe some practical limitations that can be addressed in future work. Our approach expects readily available user satisfaction labels for any request. In reality, user feedback may be only sparingly available. This would require a modified strategy for virtual queue update and zoo exploration based on feedback availability. In addition, our predictor training approach expects complete request satisfaction labels for each model during exploration. Practically, this can be challenging as showing multiple outputs to users and requesting feedback may be confusing. Nevertheless, is worth pointing out that our work serves an important foundation for these extensions in the future.
10

---

Acknowledgements
This work is supported by the Bavarian Ministry of Economic Affairs, Regional Development and Energy (Grant: DIK0446/01).
References
[1] P. Aggarwal, A. Madaan, A. Anand. S. P. Potharaju, S. Mishra, P. Zhou, A. Gupta, D. Rajagopal, K. Kappaganthu, Y. Yang. S. Upadhyay, M. Faruqui, and M. Automix: Automatically mixing language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httpp:://openreeiee net/
[2] Y. Bisk, R. Zellers, R. Le bras, J. Gao, and Y. Choi. Piqa: Reasoning about physical com- monsense in natural language. Proceedings of the AAA/ Conference on Artificial Intelligence, 34(05):7432-7433) 7439, Apr. 2020. ISSN 2159-5399. doi: 10.1609/aaai, v34i05.6239 URL http://dx. dtt.//xxdooo..ooo org/ 10. 1609/ v34105. 6239
[3] S. Chen, W. Jiang, Lin, Kwok, and Y. Zhang. RouterDC: Query-based router by dual contrastive learning for assembling large language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL /ttlps/////opeeeeiiie net/forum?1d-7RQvjpo
[4] C. Clark, K. Lee, M.-W. Chang, T. Kwiatkowski, M. Collins, and K. Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. In NAACL, 2019.
[5] P. Clark, I. Cowhey, O Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord. Think you have solved question answering? try are, the ai2 reasoning challenge. wxXiv1800.0054570 2018.
[6] Council of the European Union Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules artificial intelligence and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 201 8/858, (EUU 2018/1 139 and (EU) 201 2019/1144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2020/1822 (Artificial Intelligence Act) with EEA relevance., jul 2024. URL Document 32024R1689.
Sttps://eete www.weew.peee.....o.. www.ee/eellleo
[7] D. Ding, A. Mallick, C. Wang, R. Sim, S. Mukherjee, V. Rühle, L. V. S. Lakshmanan, and A. H. Awadallah. Hybrid LLM: Cost-efficient and qualety query routing. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreviee. net//torum?ddd02ffSuUttttt
[8] A. Dubey, A. Jauhri, et al. The Llama 3 herd of models, 2024. URL https::/arxiv.corm aba/2407 21783
[9] C. Fourrier, N. Habib, A. Lozovskaya, K. Szafer, and T. Wolf. Open Ilm leaderboard v2. https //huggingface wwwpppace/////cccocooocccc...eee wawpicee/opee-mmmmmeeeee- httpa-lllm--addebbrrrrrrrreee 11m_ 1lm__eeadrbboard 2024.
[10] L. Gao, J. Tow, et framework for few-shot language model evaluation, Sept. 2021. URL
/ttps:///ol..rg/10..22222 0ttg//0.521//eeodo 5371628
[11] I. Granite Team. Granite 3.0 language models, Oct. 2024. URL https://github...... com/
1m com-granite// hete//rrantteeteee ttt.://tttettttaaaaeeeeeeeeeaaee
pdf
[12] D. Jiang, X. Ren, and B. Y. Lin. LLM-blender: Ensembling large language models with pairwise ranking and generative fusion. In A. Rogers, J. Boyd-Graber, and N. Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14165-14178, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 18653// (11653//11202...o acl.o....loooon.....m Intpe://aclaathologg/ www///////22222 acl long. 792/
URL
[13] M. G. Johannes Welbl, Nelson F. Liu. Crowdsourcing multiple choice science questions. 2017.

---

[14] J. Liu, L. Cui, H. Liu, D. Huang, Y. Wang, and Y. Zhang. Logiqa: A challenge dataset for machine reading comprehension with logical reasoning. In Proceedings of the Twenty- Ninth International Joint Conference Artificial Intelligence, IICAI-RIICA1-2020, page 3622-3628. International Joint Conferences on Artificial Intelligence Organization, July 2020. doi:
2020/501. URL http://áx: http:://xx..o..... doi. org/ 10. 24963/ ij cai 2020/501
[15] K. Lu, H. Yuan, R. Lin, J. Lin, Z. Yuan, C. Zhou, and J. Zhou. Routing to the expert: Efficient reward-guided ensemble of large language models. K. Duh, H. Gomez, and S. Bethard, editors, Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan Language Technologies (Volume 1: Long Papers), pages 1964-1974, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10. 10.18653/v1/2024..eem htw.l//2.....aaloooo...... 109. URL halp::::/aaaaathhologggo org 2024 naacl- 109/
[16] H. Naveed, A. U. Khan, S. Qiu, M. Saqib, S. Anwar, M. Usman, N. Akhtar, N. Barnes, and A. Mian. A comprehensive overview of large language models, 2023. URL. https //arxiv http:/org///a////////e ab3/ 06435
[17] M. Neely. Stochastic network optimization with application communication and queueing systems. Springer Nature, 2022.
[18] I. Ong, A. Almahairi, V. Wu, W.-L. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica. Routellm: Learning route iIms with preference data. arXiv preprint arXiv:2406. 012224406.66666 18665, 2024.
[19] Qwen, A. Yang, B. Yang. B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, Huang, H. Wei, H. Lin, J. Yang. J. Tu, J. Zhang, J. Yang. J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang. T. Xia, Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu. Qwen2.5
technical report, 2024. URL WtRLhhtps:///ant
wrg. http:/bbs/212.... 15115
[20] Reuters.
Microsoft deal propels three mile island restart, with key permits still needed.
https://www.i http:///wwwrrrttereeeeeee reuters wwwpttterr..o/oommraaeaea wwtaa//aakets//e seaaarkets/daassssssse.s
constellation
-ot [Accessed 24-09-2024).
2024.
[21] K. Sakaguchi, R. Le Bras, C. Bhagavatula, and Y. Choi. Winogrande: An adversarial winograd schema challenge at scale. Proceedings of the AAAI Conference on Artificial Intelligence,
34(05):8732-87400 Apr. 2020. ISSN 2159-5399, doi: 10. 10.1609/aaai v34105.6399, URL
http://dx http://xdddoooog//////oooo owt/ooog///ooo 10. 1609/ aaai v34105. 6399
[22] S. Samsi, D. Zhao, J. McDonald, B. Li, A. Michaleas, M. Jones, W. Bergeron, J. Kepner, D. Tiwari, and V. Gadepally. From words to watts: Benchmarking the energy costs of large language model inference. In 2023 IEEE High Performance Extreme Computing Conference (HPEC), pages 9, 2023. doi: 10. 111109HPPEES88622222206666
[23] M. Sap, H. Rashkin, D. Chen, R. LeBras, and Y. Choi. Socialiqa: Commonsense reasoning about social interactions, 2019. URL http::::/aaxxvv..o/ www.ooggg/bbbbbbeeeeoeoeee 1904. 09728
[24] D. Stripelis, Z. Xu, Z. Hu, A. D. Shah, H. Jin, Y. Yao, J. Zhang, T. Zhang. S. Avestimehr, and C. He. TensorOpera router: A multi-model router for efficient L.M inference. In F. Dernoncourt, D. Preottuc-Piettro and A. Shimorina, editors, Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, pages 452-462, Miami, Florida, US. Nov. 2024. Association for Computational Linguistics. doi: 10. 0t6666//1//024.mmllpplo wttp://.....e.eemmmmmeeeeeee.eee
34. URL
emnle industriidustry.... 34/
[25] B. Warner, A. Chaffin, B. Clavié. O. Weller. O. Hallström, S. Taghadouini, A. Gallagher, R. Biswas, F. Ladhak, T. Aarsen, N. Cooper, G. Adams, J. Howard, and I. Poli. Smarter, better, faster, longer: A modern bidirectional encoder for fast, memory efficient, and long context finetuning and inference, 2024. URL htt.tttst///ai...rrtrt http://rxii...o/ga//////// 241.//6611.11133333
[26] A. Wettig, A. Gupta, S. Malik, and D. Chen. QuRating: Selecting high-quality data for training language models. In R. Salakhutdinov, Z. Kolter, Heller, Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference Machine Learning,
12

---

volume 235 of Proceedings of Machine Learning Research, pages 52915- PMLR, 21-27
Jul 2024. httpps//prroceddng.........p mlr ptt..peeee////2///ta222....... html
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We propose new algorithm that introduces guarantees for minimum user satisfaction rates language model zoos while optimizing for operating cost, which can be practical for inference endpoint services.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations are discussed at the end of the conclusion section (Section 5
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide formal proofs for all our theorems in the supplementary material.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our codebase will be made public (for now: anonymized for review) and is based on the widely used LM-Eval harness for better usability by others. We describe our algorithm detail the main paper and provide extensive details on the technical implementation in the appendix.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: All code repositories and benchmarks we use are open-source. Our code (incl. that to reproduce our data) will be made public, if accepted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: provide high-level overview the experimental setup the main paper and discuss all remaining details in the appendix.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our experiments have been repeated multiple times and all reported results are based on the mean observations.
8. Experiments compute resources
14

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide full details of our hardware setup the appendix.
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htte::///nuiipppeeee htttp:::hhaurips.cccpppliloooooe httprr/s...cpbiiic/hhhhceeeeeeeo
Answer: [Yes]
Justification: Our work adheres the NeurIPS ethical guidelines.
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work focuses on cost efficiency. In case of language models, this can have substantial positive effects on the energy consumption, which reduces the environmental burden AL other regards, our work bears the same risks and safeguards as the underlying models used in the language model zoo.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work provides the same safeguards as those implemented in the models in our language model zoo.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have credited the authors of all code libraries, datasets, and models used in our paper.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our code repository will be made openly available once the paper is accepted.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
15

---

Answer: [NA]
Justification:
16. Declaration LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: have only used LLMs to improve writing on a sentence level.
16

---

Appendix
A Proofs
18
Proof of Theorem
18
Proof of Theorem
19
B Experimental Details
25
Additional Evaluations
27
C.1 Additional Results Related to Our Main Findings
27
The relationship between a and
27
Predictor Training Evaluation
28
Additional Experiments on Larger Model Zoos
28
17

---

A Proofs
A.1 Proof of Theorem 1
Let max anp; VAg B f. For any given let m² denote the selected model obtained from the solution to 33) i.c. ym ,t = 1 and V/m', 0 for m' of m².
We first prove that, when Qr > y, we have Sm.= 5m S 3, where in Assumption [ The proof is by contradiction. Suppose $m.t Sm,,t ,, > 8, then choosing m instead of m² i.e., letting yia,t 1 and Um=,1
arg maXm 6m, as defined
will reduce the second term of the objective (3a) by Qe..
The increase in the first term of (3a) due to this change is at most V Våg. Since Q > ? 2 VAs we know that this alternative model choice decreases the objective Gap. which contradicts that mn* the optimal model choice from
From Assumption 1 we then have Pr(sm=. 1} 2 9 > when Qe V. We also note that the queue arrival at step is a Sm*, E (0, 1).
Let Z4 max {0, Q 7 We have
1
Z
z77
Zz
2
(max(0, (0, Ze 20 +0 -mmm,,,)) sm,,))² 22 Ze
E
(7+ + a 8x==,) 2 777 7
S
E
1
S
Ze (a 8m .1) +
(a - 8m .)) 2
2
S Zu (a )m))
7t
1 < 7c (a 9) + 2'
where the last inequality is because, as shown above, Pr(sm-,e 13 2 q when Qe > ? which is equivalent to Z, > O.
Taking total expectation gives
E
Zet
z3
S
-)
Since Z1 0, telescoping gives
t-1
E
z2
< -2
E (2) 1), Σ
(A.1)
for >>
Then, noting that q > a and Z₁ 2 0, by Jensen's 's inequality, we have
E
Z < [
Vt,
(A.2)
for 2 1.
In addition, from A.1
also have
[-1
E at)
st-1
Therefore, after replacing 1 with t,
Σ E[Z 5 2(g - a)
(A.3)
18

---

fort 2 1.
The final result then follows by combining Qr S 7 Z4 with (A.2) and A.3 giving the two bounds.
A.2 Proof of Theorem
We prove Theorem 2 by first introducing few lemmas.
Lemma A.1. Choosing ahe min
p(s+i] }.. after l 2 1 steps of predictor training using SGD
with the loss function defined in (4). we have
[((x)] Fmin S 0
(A.4)
Proof. Let & denote the index of exploration steps. The SGD update of predictor training is
Zk++1 f- Zz
1/6 V F F(zz, an)
(A.S)
Let gi V Zg: Fzt ax) for convenience.
By L-smoothness, we have
L
F(zx+1)] 2/
1 F(zs) 7)k FF(()))
gA 2x)
+
||g&e||
2k
2
< F(zs) Mm 1 [F
([VF(Z)))1 +
+
2
Lik
Lino²
=((x))
116
|| 1?
(A.6)
2
2
From PL condition, we have FZ(2)) on both sides of (A.6) and plugging in the PL inequality gives
2 2μ (F(z) - Fmin), Vz. When Te < subtracting Fmin
Lafe
Innoz
E F(z++1) Finn Zb
I (F(z+) - Fmin)) 2p
(F(zs) Fmiu) +
2
2
=(1 2pmt (1-
Litke
(F(zs) - -Fmia) + LnRO2
(A.7)
2
2
Let 17 < 1.- We have
E F(ze+1) Fmin zb S (1 pms) (F(zz) Fmin) LNiE0²
(A.8)
Taking total expectation gives
F [2 Fiin 5 (1 wmnn (E [F(z)) -Fmin) + InnR2
E
(A.9)
Let Fg == E [F(x)]]
Fmin- We have
Lnfo²
F2 S (1 pm Fi +
2
Fa (1 (1 - 1mm + Lo 602((1- - 1112) 1/)
2
F4 < (1 mm)(1 (1 - 1m (ma + Lo pmm) (1 mmm)) + prjs 1
2
19

---

Therefore,
Lo Ek=1 1x
2111== (1 mm))))
pm)) + F& S Fi k=1
(A.10)
2
Recall that 7/ min
[((+1)) Σ }.. We note that, due L-smoothness, we have μ S L, because
otherwise the L-smoothness contradicts with the PL condition. Therefore, 2/. 2 We have TJks = +
24 when & S k
- -1-. For k k, we have 7 u(k+Ij and in this case, 1 μm7k k+1
k-1
We first consider the second term of (A.10) For &e S Re + 1,
k-1
G(k)
Σ
The
II (1 - (m))
Σ
1 T,2
7.
L.p.
-1=+1
Let kg == k + 1. From the above, we have G(lko)
S
1
For ko, we note that
LH
G(k + (1 - pogn G(:) + n
2
= k 1
G(k) +
1P 1)a
4-1
4
G(k)
++1
12 + 1)2
Thus,
G(ko + 1) $
+
Lu(Ku + 1) 1² 1)2
kko
4ko
4
G(ko + +2) -
Lu(ko + 1ki +
1k2 + +k) +
p²2 2)²
4ki
4(ko + 1)
G(ko + $
Lu(Ko + 2) (ko +3 +
12 + 1) + ()o +3) +
1² + 2ko + +3)
4
120 + 3)2
liki
4ko
4(ko 1) 1² + 2ko + 3) 44
G(ko + 4) $
+ 12 + +kko + ()u +4) +
Lu(Ku + 3) (Kg + 4)
4(ku + 2)
+
+ 1² + 4)2
μ² + (ki + 44)
For general & ko, after upper bounding some terms, we have
ieko
k-2
4x
4
G(k) - Lp(k
+
1)k
112
(x +
()
1)k
k2
k=
ioko
1
k-2
4
4
Lp(k - 1)k:
112
(k:
1)k
42h22
x=
kko
4
Lpukk - 1)k:
1.2k
1 1
(A.11)
where the last equality is because is and ko are constants as they only depend on L and μ.
20

---

Next, consider the first term of A.10). When k S Ko.
k-1
-1--
k-1
(kk) = II pmm)) =
x=1
For ko, have
1e
Hkk 1) (kk))
ko +
kko
H(ko + 2) ((o))
(Ni + 1)(kk + 2)
kiko
H(ko 3) H(ko)
(Ro + (Ro + 3)
kkin
H(ko + -4) ((ko))
(ko + 3ko + 4)
For general & 2 ko.
H(k)
(1
11
lko (lc
o
( 122
(A.12)
L
1)
because i and ky are constants as they only depend on and μ.
Combining (A.IT) and A.12 with A.10 we obtain
1
F [F(z))] Fmin S 0
(A.13)
k:
L
Lemma A.2. Choosing The min of predictor training has occurred. We have
p(k+ij + } for any 2 assume that after & requests, ls steps
M k
max 1m, Sm,el
MM +0
(A.14)
m
Proof. For the ease of discussion, let e denote the upper bound of E [F(z))] according to Lemma A.
Fuin so that c = O (1)
When E [F(z=)] Fmin S e, from (4) and noting that the cross entropy non-negative, we have
E
max m
- Sm,r log 8m, - 8m,e) 80,.)loo(111
(1gg - 8m,r))
M
E
Sm, log 8m,t (1 - sm,) log(1 8m,t))
m=1
x ME [F(z)]]
< M Fmin + eM.
(A.15)
For arbitrary sample a, and model m, let
Sm,t log 8m, - (1 - Sm.e) log(1 sm,)).
We consider cases follows.
When Sm,t 0, we have
T= - log(11 8m,))
21

---

8m, = 1 - -
1m, Sm,il 1
When Sm,t 1, we have
log 8m,t
7 s = --
= 1mm Sm,i
= 1-6- -
Noting the elementary inequality e-
2 1 r, we obtain
, - 8m.t S
Because this relation holds for any sample and the corresponding defined on the sample, the expectation of the cross-entropy loss cannot be smaller than the expectation of the absolute difference. Combining with (A.15). we have
E max Bm, Sm,t/ < Fmn + eM = Fin + O
(A.16)
Lemma A.3. Let & denote the random variable of the number of predictor training steps after processing requests. We have
k 1 (1)) and EE
(A.17)
K
Proof. Recall that X, Bernoulli(p:) is indicator denoting whether SGD step for predictor training occurs when processing request I. In the following, we assume that k is the total number of SGD steps after processing l requests. We have
=
Σ X
Σ 7=1
Pr
min
1,
c {x VF
θ (t#)
(A.18)
7=1
This proves the first result. Considering 1 f we note that
1 k
=
122/22
+
1<x//2
$ A
+
1CCA/2
(A.19)
k
k
where 1e is an indicator function of whether the condition C holds.
We now consider the last term in (A.19). The multiplicative Chernoff bound shows that
Pr(k S 8)2) -e-
for < 1. Choosing 8
2 gives
d 5 Pr
Pr
2
Because k 2 1,
1
1<<a/2
< E
1<ea/2
(A.20)
1
X
8
where the last inequality is due the elementary relation that ex > for any Combining (8.18). (A.19) and (A.20), we obtain
E
<
0
(A.21)
k
22

---

Based on these lemmas, we are now ready to prove Theorem
Proof of Theorem We first consider any such that X; 0, i.e., no exploration or predictor training. For the ease of presentation, let m" denote the optimal solution to (3) for some given t, i.e. ,t and Um for m' * m", where is inferred from the context. We consider the following Lyapunov drift of the queue length:
E Q
07 Q.
E
(max{0, Qr am
8m- sm) Qt 0.
a-m0-mmm1 (Q: + ---a-am 8m .m= Q8 Q:
_ E8
$
E
2Qi(a - sm + Q1
Q:(a - Sm + 8m - sm .e) Qt + 1
=
Qi(a 3m (1) Q:
+E Qe(smm Sm- ,e) 1 Q:
s Qr(a - 8m)+)) Q:
max + Q.E
18m, - 8m,
+ 2'
(A.22)
m
where the second inequality follows from expanding the square and (a _m )
1
Let fymmt fm} denote the result of an optimal stationary policy to ①T. For our online decision- B). we get
making problem
V Fm a + Qe (a - m Qi
M V
M
Umnt F,, + Qt
Σ
Um, (a - 8,,)) Qt
T
m=1
M
V
Im, Fi,, Qt
Σ
Um (a Sm + Smit 8mm,t)
Qt
M VE
M
OPT Umn
Em,
+ QUIE
Σ
Um (Sm,z 8,,ee
Q.E
Umn (a smi,)
V OPT
Q
max ( [mmm
Sm.ee
(A.23)
where the last inequality because the optimal stationary policy satisfies the constraint (Tb) and the cost minimized when the constraint holds with equality, thus E. EM OPT (a sm,,) 0.
Combining A.22 and A.23 we obtain
M Im, Fym.t
1 Pi - Qr + VI
Qe
2
m=1
M Σ
< E Qi(a 8m (1) Qc + QiIE
max 1mm,t - sm,el
+ + VE
Um, Em,t Qt
m
2
m=1
= E Vmm,, a + Qe (a- 1 8m),,) Qi
+ Q.E
max Sm, sm.el
+
1
2
< OPT + +,E max{ 18,, - sm,rc3
+ Q,E
max m
1m,, sm.el
+
23

---

VE + =Q
max
Sm,t Sm B
m
2
Taking total expectation, we obtain
M Um, mmme
E
Di+1 -Q7 + VE
2
m=1
< V EOPT
+ 2B [Qr] E
max 8m, - smel)
+
Therefore,
M
E
Dra,t E
m=1
2 E
OPPT
[Q.]
E
max
8m,t - Sm,
+
+
E
Qi 0i+1
V
2V
2V
< OPT
2
EIQ
IE
O
M
+ M F Fiin
+
+
Ot 0i+1]
1:
2V
2V
< OPT
2 V
(7+
vijo
+ M Pmnn [Q:]
+
E
Oi
Pin1]
2V
2V
where the second inequality uses Lemma A.2 and the last inequality uses Theorem and y
max any; 3
VAe
For any t with X, = 1, we note that the maximum cost due to exploration when processing such requests is M Emaxx-
now include where either X. X, 1. Then,
E
Ym, E,mt
T
1=1
m=1
<
OPP
+ V
2
T
l7
ViO
M
MF
T Σ t=1
E [Q.]
+
+
E
|0P
02+1
T
T
2V
2VT
1=1
[ M Emaa
+
T
1 T
M
M
< EPT +0
+ MF
+ V +
T
T
tml
M
MF Fmin + )
OPT +0
+
VT
where the second inequality uses Theorem and Lemma A.3
24

---

B Experimental Details
In this section we provide full details for our experimental design.
Datasets & Benchmarks. We use the LM-Eval Harness basis for all of our evaluations. We use zero-shot setting for each benchmark. Our evaluations are based on default configurations provided by LM Eval. We use vLLM v0.8.4 the inference backend for LM Eval.
LLM Zoo. Our ZoO coniststs of three Llama models, namely Llama 3.2 IB, Llama 3.1 8B, and Llama 3.3 70B. We use publicly available model checkpoints available on the HuggingFace Hub, specifically, meta-llama/Llanct 1--B--ie 2-1B-Instruct, unsloth/Meta-Llama- 1--aa-aaaaaa-------------e-- L--B--nnstruct--nb-eee and unsloth/Llama-3. S---O--Inntrutt--aaaa
Request Satisfaction Predictor. We design a predictor model based on the ModernBert transformer and implement classification head top of Before we pass the final-EERT-layer outputs into the classification layer, we pool the outputs and use a drepout (= 0.1) for better training effectiveness. We first have linear layer, followed by a layer norm operation, followed by ReLU activation, another dropout (= 0,1,, and then a final linear layer. We use sigmoid function to compute the classifier logits. For each benchmark in our main paper, we ran hyperparameter sweep identify the most effective hyperparameter combinations. They are listed in Table O
Table Predictor model hyperparameter configurations across benchmarks.
Benehmark
Leaming Rate
Weight Decay
Momentum
Max. Seq. Len.
Dropout
ARC Challenge
0.0606
0.01
0.90
256
0.1
ARC Easy
0.0826
0.01
0.90
256
BoolQ
0.0767
0.01
0.95
128
LogiQA
0,0272
0.01
0.90
256
0.1
PIQA
0.0367
0.01
0.90
64
0.1
SciQ
0.0596
0.01
0.95
64
0.1
SocialIQA
0.0542
0.01
0.95
64
0.1
Winogrande
0.0660
0.01
0.90
Random Baseline with Constraint Satisfaction. We implement random baseline that follows constraint satisfaction, or in other words, SLA compliance. We use the following implementation to facilitate the baseline.
def calculate_probabillie o*n
(model_accuraccie) list
alpha: float);
Function to compule priori probabilities for baseline
model selection process that provides SLA compliance over time.
accuracies up. array (model_ = len (eccuraacies)
# Check if possible
if alpha max max(accuracies):: raise ValueError Alpha_too_high" high""
p ap. op. (n) /
for in range (5000):
current_ acc = np. dot (p. accuracies)
if current_ard ace >= alpha le-6: return p
# Simple update for in range (n):
if accuracies [i] current_acc:
pli] == 1.01 # Increase good models
25

---

else: pli] == 0.99 Decrease bad models
# Normalize
p np. sum
idx_sorted up. argsort (accuracies [[:--]] -]]
Calculate minimum probability for best model best acc accuracies iidx sorted[O]]
worst_acc accuracies [id
Start with minimum probabilities for all min_prob 1e-10 = up. full (n, min_prob)
remaining 1.0
min_prob
# Distribute remaining probability for i in range(n): idx idx sorted
if =-n- 1: plidx] += remaining
else:
# Give more to better models weight = (accuracies [idx] worst_acc) / (best_ace worst_ace)
allocation = remaining * weight 0.8
p[idx] += allocation
remaining allocation
p p=pA np.sum (p)
return p
Lou To reproduce the RouteLLMM results, we integrated the RouteLLMM controller into our existing evaluation pipeline. RouteLLM supports only two models: weak and a strong model. We configured these the Llama 3.2 IB (weak) and 70B (strong) models, respectively. We chose to use the BERT-based router of RouteLLM. We swept the routing threshold from 0. to 0.9 in increments of 1. As shown in Table 7 RouteLLM requires careful tuning of the routing threshold to achieve desired performance, which lacks a direct mapping to user-specified service level requirements.
Table 7: Mapping from MESS+ a to RouteL decision threshold.
Datasct
ds
Thresh;
02
Thresh,
Og
Thresby
ARC Challenge
0.7
0.5
0.6
0.7
0.4
ARC Easy
0.8
0.7
0.6
0.75
BoolQ
0.5
0.8
0.5
0.85
0.6
0.7
LogiQA
PIQA
0.6
0.75
0.5
0.81
0.6
0.78
SocialIQA
0.7
0.44
0.7
0.46
0.7
0.42
Winogrande
0.75
0.6
0.5
0.7
RouterDC. To reproduce RouterDC, we trained its routing module our benchmark tasks. The router encodes each query using the pretrained encoder mi crosoft/debert.... tertta----bbee and com- pares its representation to a set of trainable expert embeddings, one for each model in the ensemble. Cosine similarity is used to produce logit vector over the experts, and the router is optimized to prefer more accurate models via contrastive losses. In our setup, the candidate experts were Llama Instruct models with 1B, 8B, and 70B parameters. Training was performed for 1,000 steps using the Adam W optimizer, with batch size of 64 and learning rate of 5 10-5 The training set consisted
26

---

of 100 queries from each of ten benchmarks, totaling 1,000 samples. For evaluation, we load the trained checkpoint and integrate the router into our existing evaluation pipeline.
Code. Our code base is made fully public on GitHub. It can be found here: http://iiihh.com/aannn/n////e
Evaluation Setup. While our experiments can be run on a single GPU (with 80GB VRAM), we conducted our experiments using 2 H100 GPUs. We distribute the LLMs and the predictor as follows: The small and medium sized LLMs along with the predictor are located on I GPU and the large model is placed
the other GPU. We repeat each experiment with three different random seeds ([42, 43, 44). Since we query the LLMs sequentially, we can capture their individual energy consumption. When doing parallel calls, it is necessary to place each LLM on separate GPU and configure the Zeus monitor to properly return the energy statistics for each model.
C
Additional Evaluations
C.1 Additional Results Related to Our Main Findings
Our experimental results demonstrate that the parameter V. which controls the priority given to cost efficiency in the MESS+ routing algorithm, exhibits significant influence on both energy consumption and performance metrics across multiple benchmarks (Tables 8 and 9 In the main results with the standard V value, MESS+ achieves remarkable energy effciency with an average operating cost of 1.08 MJ while maintaining satisfactory performance (68.44% request satisfaction) across all benchmarks. When reducing V to 0.0001, thereby decreasing the emphasis on energy efficiency, we observe a 65.7% increase in operating costs to 1.79 MJ with only a marginal improvement in performance to 69.16%. Further reducing V to 0.00001 yields an additional cost increase to 1.88 MJ % higher than the standard configuration) while performance improves only slightly to 69.41 %. These diminishing returns highlight the effectiveness of our approach in balancing the performance- efficiency trade-off. Notably, the distribution of model calls shifts substantially as V decreases the utilization of the 70B model increases from 34% with standard V to 54% with V=0.00001, while mid-sized 8B model usage decreases from 40% to 23%, indicating a clear preference for higher- capacity models when efficiency constraints are relaxed. Individual benchmarks exhibit varying sensitivities to the V parameter; LogiQA shows the most substantial performance gain (41.02% to 43.89 33.89) with decreased V values, while SciQ maintains relatively stable performance (* 96%) despite significant variations in model call distribution. The ARC Easy benchmark demonstrates one of the most dramatic cost increases, from 1.74 MJ 5.39 MJ the lowest V value, emphasizing how routing decisions can substantially impact energy consumption for specific task types. Even with reduced emphasis on efficiency. MESS+ maintains competitive or superior performance compared to alternative methods like RouteLLM and RouterDC while consuming less energy on average. These findings underscore the flexibility of our approach in accommodating different deployment scenarios where either performance or energy efficiency might be prioritized, while consistently outperforming baseline single-model approaches for the same levels of request satisfaction.
C.2 The relationship between a and V
Our experimental evaluation across multiple reasoning benchmarks (ARC Challenge, ARC Easy, BoolQ, LogiQA, PiQA. SciQ, and SocialIQA) exhibits the exact relationship between a and V that we show in our theoretical analysis. The results demonstrate that lower V values (V = 0.0001) consistently achieve higher request satisfaction rates while incurring greater computational costs, exhibiting slower convergence to stability but ultimately reaching higher performance plateaus that can satisfy more demanding Service Level Agreement (SLA) thresholds. Conversely, higher V values (V = 0.01) prioritize cost efficiency, resulting in significantly lower average costs, faster initial convergence, but ultimately lower satisfaction plateaus that are very close to a. Medium V values (V = 0.001) strike a compelling balance, offering reasonable satisfaction rates with moderate computational investment. Notably, our Winogrande analysis illuminates the explicit relationship be- tween SLA satisfaction timing and both thresholds and V values, with higher requirements (0.65, 0.7, and 0.75) correspondingly satisfied at later request points (steps 740, 803, and 994, respectively). When compared against baseline methods, our approach approaches provides similar satisfaction levels like RouterDC while maintaining substantially lower computational costs, demonstrating superior efficiency in the satisfaction-cost frontier. These findings underpin that V provides an
27

---

ARC Challings
APC. Euee
Baod)
Ieg0A
P924
$:42
Ne Scund
06
100
2013
400
Praeet
100
423
Figure C.I: Full overview of predictor training cost across all benchmarks used in our paper.
intuitive and flexible mechanism for system operators to deliberately navigate performance-cost trade- off's according to ipplicatiionsseciffe requirements, enabling precise calibration between resource efficiency and quality of service in large-scale LLM deployment environments.
C.3 Predictor Training Evaluation
Our analysis of exploration-exploitatiee dynamics across eight reasoning benchmarks reveals critical insights for efficient predictive modeling (Figure C.T). We observe that the exploration parameter (c) exhibits predictable effects across benchmarks, with higher values (c = 1.0) maintaining robust exploration but at approximately ten-fold increased energy costs compared to conservative settings (c = 0.01). Notably, task complexity correlates with resource requirements, as evidenced by the significantly higher exploration costs. The predictor training loss patterns indicate that higher exploration parameters facilitate faster convergence and lower overall loss values, suggesting more robust optimization, though with diminishing returns relative to energy expenditure. These findings highlight the importance of context-award parameter selection in balancing performance gains against computational costs, particularly relevant as AI systems scale and energy efficiency becomes increasingly critical. Generally, we find that choosing c = 0.1 provides a strong basis for MESS+ across benchmarks.
Table 8: Additional results for our main results with a smaller value for V = 0.0001, which reduces the priority for cost efficiency.
Henchmark
ARL Uhdllzgge
MBS
AUCC Saey
TB5)
Methed
Openting
Royest
MakiCal de
Openiing
Requnst
Medel Call Ratie
Openning
Regana
Mudel
Liama SB
0:25
0% 7 11755 70%
0.90
IPG 1000% (0%
$4.10
0%-7 103% 2M0
Liama X0B
2.35
60 aa
10056 1FS 70%
318
1007% /066: 10%S
3-40
E00KS (0% 1.0
1,00
734%
31% 205
RestetXC
2/00-am
95% 125 70%
3.5
855 155% 10%
02.00
55% 42%
MESS+ (ours)
155
$4.50 cu
70% /21%
4.87
78.20 26
54% 28%6 19%
1.35
$1.12
35% 30% 132%
LogiQA
POAA
Openting MT)
Boaed
Noail
Opaning
Recaot
Medd
Opcrity Coe MT
Ropack
Maki
Susctatton
(370RL 4631130
(131545500.00 5000.0
Taae III
(1% 705- 1095
/S//05/ / 1095
0:10g
91.00
05: 10% 100%
1.0ma S1
0:81
(T% 7 1097 (05
1136 1.3..mm
70
DS% 11005 /0S
05: 1005 260
1.
4.15
(PS 105
1015 /0S5
3:33p
(0%
1.51
4855/115 735
705. 375
2.16p
0955 (0%.
RecartDC:
201 2004 775
1005 2055/000 /0SS
1,00p=
8356 11%8/00
MESS tornd)
1245
195/139/315
641
Congree
SocilliN 41%)
Wanggranee
Boschenekk
(655)
Sukuaggyy
Cod li Mi
Susifaticn ia 901
(L7001995 (16)
Co Mi]
CL7HK 36/1130
Gut Mi)
Liuea IB
0:13
41. al
0% 70/00/110 1006
0 0.K...
59
05/00% / 100%
0.12a
54 30.5
0%: 05) / 11005
1Jana 5B
0.59
03 23/11000 1000 700
0 22
75.5444
16/0100/// 70%
0.5
Ma
06 1075 00
73.00
Blaaned
1.2
47.7
33% 1355 735%
7065
35%
1.2k
366/ /336
ReadLLM
2.03u
65% (1// 135
1.5
40 32.
97% /00 33%
204
71. 11.10am
83% /05 1866
RecteDDC
556. 55 706
1.30
40
1015 /00 /05
2.13a
73.7amm
85%/115% /0
74.37am
19%
C.4 Additional Experiments on Larger Model Zoos
To demonstrate the performance of MESS+ even in larger 700s, we conduct addi-
tional experiments on a 7oo containing four models: Qwen 2.5 32B (Q32B), Qwen
2 7B (Q7B), Qwen 2 1.5B (QI.5B,, and Qwen 2 0.5B (Q0.5B) with the check-
28

---

Table 9: Additional results for our main results with a smaller value for V 0.00001, which reduces the priority for cost efficiency even further.
Congrey
Co
ARC Recuae
TOR)
Stbeuagary
Openatng MDn
Rosaet
Opening
Medd Cal
Cbecatte
Ropace
Make
(ax)) 5000.100
Lism 18
0109
0% 705- 100%
F0S 1097
0%s FPS 600%
Lima RB
0:45
0% z 1007 10%
(P% 1000 10%%
0433x
0%- 100% 6.6
Liana N0B
1007% (0%
00%
ReueLLM
1.2
51 Fecus
50% (9% 550%
100% 7.0 10%
205
87% /0S 115%
ResietDC
60 cu
85%, 122% 70%6
3.1
8078 (35% 10%%
585 4224 /06
MESS (ours)
60%
221%
(0% 19%
23%
LopigA
PIQA 7353)
SciQ 567))
Opering MI)
Popee
Cull
Opening
Ropaci
Navil
(is
Openias MD)
Ropect fix 10
Moked
9%)
Saidhctee
Con MI)
Satifacciee (5)
(2.700 STV 11)
1ibrr HI
0:37
19
IS /05 F1GGS
75005
IT% 105 7100
B
0%% (05 1005
1.brr RB
20 (1
IF% 1007 195
0.
79 07
ITS 1975 11%
8.58
49 20.00
CAS 10075 70%
1.brro 708
80
100% (0%.
1007
Greading
RoseLLMM
47.7
95% /05 25%
78 i
66% 34/
105 75%
RouteDDC
47. B3ack
70% 299 25
1.55axx
52 10
100% (06: 10/
1 1.M0aac
97 27.55
825 /355 10%
MESS (eurs)
2.
72% 2000//2/220 2205
10laces
20.04.2.0
51% /38 125
0.56
96.
205 (37% /43
Cangrey
Winggrnde Recaae
Ang woncs
6055) Maki
Subeuzgary
Opeating
MT
Boase
Moaat C-ll da
Opening
Medd Call Radarda
Oscratig Mnn
Ropack
N15a 5000.00
(a/8)
Lisma 18
0% 705 102%
1100
FOS 7 1077
0.22ms
09s 100%
Liaaa SB
0.99
0% 7 1007% 10%
0.25
DPa 100% 10%
0.54
0% 100%
Liana
100% (0%
132%
(33%)
ReueLLM
2/12
65% Dr5/ 735%
1.20
40.82
95% 70% 33%
204
7L.19
0256 /09 185
RecieDC
05% 5t 70%
1,30-ox
20.56-4
100% 7.0% 10%%
85% /
MESS: (ours)
45% 135% 2046
0.57
74,09
719//109 1886
09.4-amm
Table 10: Main results with the Qwen 2 model family. Specifically, we use Qwen 2.5 32B, Qwen 2 7B, Qwen 2 1,5B, and Qwen 2 O.5B. MESS+ also outperforms our Educated Guessing baseline in larger model zoos. V 0.0001.
Cangory
ARC Challerge (or 5016
ARC Eary to - 77%)
Bool) to - 83%)
Subcategory
Operaing
Cioi
Sutistacioon
Recoed.
Modal Call Ratio
Operaing
Cloi
Recoed, Satudacioo
Madel Cal Hatin
Operaing
Cooi
Requedt Sanidaction
Model Call Kaão
Qwen2 0.58
0.10vaeo
30.03
0% .0% D0% 100%
0.21
$4.88
CR /0% 70% / 100%
63
0% 00% 0%% / 100%
Qwen? 1S5
4 14gmeen
40 10
Cna /05 / 100% 7996
0.28gr
66.67
CrR /05: 10179 10%
0.12
16 76.77
09S 185 100AS DS
Qwen2 TB
0.3
50.94.a
0% 100% (0%) /O66
0,70 0.70.cas
75-42-474
OFL 100% 08 /05
0.25
84.13-am
OFL 100% 00% 0%
Qwend.5 12B
58.18,--
100FL
/0r 109%
p.73 m
1009 10%
10%%
1.83
1005 10%
Eduustal Garoeing
1:20
66.76...
92%
3.23 mm
77:46.-
76% 229 (
0.1
$2.40....
34FF 114% 1199
1.35
41 77
11%
1.4 57.31+1
Ro
58.65
89% 25%
199 /3%
4
MLSS+ (ours)
1.18
20.21
85% 2/6
1,00
77.00.
53% 442% F331
0.78
111 179
Eangrey
TagiQA to
359)
PQA
195)
Seli
90%)
Sebestegory
Operiing
Requcal
021:8:07840).55-000555
Operatng
Rececal
Mxl Raão
Operaing
Reguet
Modei Raão
Uwen2
0.tMaca
15
31
1.58
0.08
24.27..0
1009k 10%
76
/06/ 1000%
6.12
94.00..
06 / 100% 00%
Qwend
0.Manne
100% /1R
79. mM
100% 105
0.30m
100%%
Qwend.5 37B
0 3.80anen
40.86us
105 /0r 7966
1.00uren
M0.41...
1906 10%
105
1.39
56 70,
19965 195
Educated Guessing
0.59
33.08-2.0
50% 22% / 155 10%
0.71.ca0
79.02-
55% /31% / FFL /3%
0
94.35-1
25% / 24% 255% /
Reanel M
0 g.
$3,62.4m
64%6/ (7R (05) 9A66
1.01 m
79
699 rO5k (1S- / 996
0.8 m
04.72
55% /OFL (0% 747%
50%
/ 3158 1155k / 7%
0 0,74
79.86
69% / 1175k 175% 73%
0:46
04.07-
30% 16/6 1155% (4225
MENS+ (oors)
49% 535
/ 11%
8.06
79.30u2
5015 0 25% /339 2666
0.21.ca
93
1995 55% 1228//22//777
Langrey
Seciallig4 to (75)
Winogronde
T150)
Meanto 0.67)
Sahcategury
Operning Car
Sancaction
Recucd
(Q1BRE77G SE/0 mn
Madel Call Raão
Operaing
Cin
Reaeck, Sendaation
Modal Cal Raio
Operains
Doet
Sandaation
Reasnd.
(017812781)) 4B106 10)
Modd Call Raão
Qwint 4SH
4 3.2hamn
4%. 15
CPS 10% (tF / 199%
0.00ur
$5
CR /1/5:/775/ / 1095
0.12
54. 14
0% /9K//5//0 /CS 1 10015
Qwen 158
a 16
46.37xx
0P% /0% / 1007 70%
6496
(R /05: 1009 /0%)
0.16.
61 18
0% /0// 1005% 05%
Qwend TB
1.05aee
48.21
0% 100%s (18. 7066
0.23ecas
71.67-.m
0% 1005 (8% /06
0,40uc
67.07
OS 100% 10% 0S%
Owad.5 32B
50.92
100% /0rS 10%
72.30..m
1008 /0% /0%)
1.80 70.91..m
100%:
Iaticaned Guessng
1.47ame0
325/
11.59..
35,
07
22/ (199/ 10RR
2.
1:37am 69.17-24
RousaDD
48.00-2.1
10%
55% 99%
63% 177
MESS+ (ours))
1,8
47.82
78/8 / 31/4 25/2/ 179
8,51
71.04..
59% F5 776
0,44
67.55
4514 26/6 /10P 1192
unsloth/Qwen2-1 htwphh//Deee------b-bb----- Quen/Qwen2-11 5B- -B-nnurtt and Sreen/Quen-O.55--- Instrust respectively. All check- points are readily available on the HuggingFace Hub. We leave all other hyperparameters unchanged and follow the setup we use in our Llama3 model-only zoo. Aside from the Llama 3-only and Qwen 2-only model zoos, we also provide results for mixed model zoo and an evaluation of varied operating cost characteristics.
points, unsloth/(uen2.55-00 1--32--nsttruct-bbb-----
C.4.1 Supplementary Results in Support of the Main Findings with Four Qwen 2 Models
The results on the Qwen 2 only model zoo (Table 5) suggest that zoo expansion can improve cost-performance trade-offs. Increasing the number of models in a zoo has beneficial effect on overall cost effectiveness, even the cost characteristics of models are more homogeneous than in the Llama3-only model zoo. Notably, the lightweight 0.5B model in the Qwen configuration is
29

---

Method Ours [Vi. [V==0.0001]
Uurs (V-
Ours (V-0.001)
Edu. Guessing
RouDeLLM
HoutertC
Reg. Sattfactton
Veed 196
Frod
60%
60%
60%
40%
40%
40%
250
500
750
1000
0
250
300
750
1000
0
250
500
730
1000
Cost (J)
2000
2000
2000
750
Request
Request
Request
(a) ARC Challenge
Method
Ours (V-0.01)
Ours (V-D.001)
[V--0.000L)
Guessing
RouteLLM
Ro
Avg. Cost (J) Reg, Satisfaction
50%
Foed lnm
90%
90%
80%
80%
80%
70%
70%
70%
500
1000
1300
2000
0
500
1000
1500
2000
500
1000
1300
2000
2500
2500
1000
1500
Request
Request
Request
(b) ARC Easy
Mothod
(V-0.001)
(V-D.001)
(000)
Edu, Guessing
RouecLLM
RouterDC
Req. Soúsfaction
100%
100%
fow
100%
80%
80%
Avg. Cost (J)
1000
1000
500
500
1000
1500
2000
500
1000
1500
2000
1000 Request
1500
2000
Request
Request
(c) BoolQ
Method
(V-0.01)
(V-D.001)
(V=CC0000)
Edu. Guessing
RoubeLLM
RC
Aug, Cost (J) Reg Sarisfaction
F HLS (ned
k10
(oed
50%
50%
40%
40%
40%
30%
30%
30%
200
400
600
200
400
600
200
800
600
2000
2000
1000
1000
200
600
0
200
400
600
0
200
800
600
Request
Request
Request
(d) LogiQA
Figure C.2: The dynamics between and V manifest further across all benchmarks in addition to Winogrande in the main paper. Part 1.
utilized 16% of the time on average, with particularly high usage on simpler tasks like SciQ (57% of calls), demonstrating that there is substantial demand for extremely efficient inference even when larger models are available. This shows that the optimal model zoo size depends on the specific task distribution and performance requirements of the application. Furthermore, the fact that all
30

---

Mothod
Durs (V-00
Ours (V-0.001)
Ours [Viu [Vi=0.0001]
Edu. Guessing
RouDeLLM
Houter
Cost (J) Req. Satisaattion
90%
Fre
90%
1 Inal
90%
80%
80%
80%
500
1000
1500
0
500
1000
1500
500
1000
1500
1000
1000
1000
1000
1000
1500
1500
Request
Request
Request
PiQA
Method [V-=0.000L)
Ours (V-0.01)
Ours (V-D.001)
Edu. Guessing
RouBCLLM
Ro
Avg. Cost (3) Req. Saisfaction
110%
110%
110%
100%
100%
100%
200
400
600
800
200
400
600
800
200
400
600
800
600
600
Request
Request
Request
(b) SciQ
Method
Ours (V-0.01)
Ours (V-D.001)
[V--0.0001)
Edd, Guessing
RouecLLM
RouterDCC
Aug. Cost (J) Req, Satisfaction
55%
55%
55%
Ircal Irc.
Incl
50%
50%
50%
45%
45%
45%
500
1000
1500
0
500
1000
1500
500
1000
1500
1000
1000
1000
500
1000
1500
500
1000
1500
500
1000
1500
Request
Request
Request
(c) SocialIQA
Figure C.3: The dynamics between and V/ manifest further across all benchmarks in addition to Winogrande in the main paper. Part 2.
methods maintain similar relative performance rankings across both configurations indicates that routing algorithm effectiveness may be more important than model zoo size for achieving consistent performance improvements. The scalability benefits appear most pronounced for tasks with high computational variance, where the additional routing granularity can better match query complexity to model capability.
C.4.2 Results on Non-Stationary Concatenated Benchmarks
To evaluate the robustness of adaptive routing methods under more realistic conditions, we also analyze performance on non-stationary benchmark created by concatenating three distinct datasets: ARC Challenge, PiQA, and Winogrande. This configuration simulates real-world scenarios where query distributions shift dynamically, as the combined benchmark exhibits non-lID characteristics with varying difficulty levels and task types throughout the evaluation sequence (Table IT].
The non-stationary benchmark results demonstrate that MESS+ maintains its cost efficiency advantage even under distributional shifts and under strict SI.A compliance, achieving 1.40 MJ operating cost compared to RouterDC's 2.29 MJ and Routel.LM'ss 2.92 MJ representing 39% and 52% cost reductions respectively. The non-stationary results are particularly highlight the importance of an
31

---

Table 11: Results when concatenating ARC Challenge, PiQA, and Winogrande. Even though the three benchmarks exhibit distinct characteristics, MESS+ shows strong performance compared to our Educated Guessing baseline
Canegory
Non-staioniry Rerchmark 67%)
Subcategury
Uperating Cost
Request Nonafaction
Model Call Ratio
Qwen2 0.50
0.26
-4.50
10%
Qwen2 1.58
0.35
62.92
100%
Qwee2 78
0.33
69.35
0% / 100% 10% 105
Qwen2.5 5.5 326
3.12
71.94
100% (0% 10% 10%
Educated Guessing
1.64-um
68.29
45% / -41% / 66% /
RouleLLM
72.38 2.92
97% / (0% (0% 13%
Router
72.86xx.4 2.29.
/
MESS+ (ours)
1.40..
68.57ax3
/9%
Table 12: Qwen 2 model zoo with varied cost spread around the mean cost per request among models in the zoo.
Caigrey
ARC Clullinge
ABC Fasy
BoolQ
Subeslegury
Operaling
Reçues Satscaction
(Q13//0781) (B800)05110000000
Madel Cull Rañio
Operatngg
Receed Saiiactio
Madel Cal Rato
Operatng: Cwsi
Regses Satidaation
(Q138/Q78M)) 5840059)
Midel Cal Rado
Uwend aSu
0. 0.20ames
40
0r% /1F/ /1F 1896
0.21
10.85 11
CP% /1%s 1F% 1099
U96 /MS (PS 1101 0f: /06
Qwen2 1.58
9.27
40.10-sa
00% 100% 60%
0.38
66.62-14
/00/ 100% 00%
0.12
76:27-477
2.67
1099/
Educated Guessing
0.58.ox
55.91-a
75%
316
a.22
77.38-2m1 2.
201
/26
0.49-ca
50.62+1
300%
209
Reancl LM
2.67
58.16.-
100% 10% /00 70%
78.05
100% /0% / (P9 00%
L.
57. 57.3
57%
/OFL /0%/ 13%)
RouserDU
0.79amxc
56.92
55% 1356 1125 USS
1.7
$1.43..0
63% / 201 /
70%
1.40ac
58.97am
19% 1016 /O%
MLSS+ (ours)
0.49
35.09.431
05% 21%
79 771
0.31
77.55.m
77% 100% / /316
0.37.c
3010
2515 /345 /19% 225
Caugrey
LegiQA to = 35%))
PQA (n 70%)
Selq (n 10%)
Subcategory
Opersiig
Cai
Sandbeton
Regend
Medel Call Ratin
Operatin
Cort
Sombattne
Reqund
Matel Rate (GIZBIQgAaN)).uuqqu
Operatin
Del
Regans Sarofaction
Model Call Rato
Qwa2 0.5R
0.06
25.35
0% (0% /052/05//00 100%
2.
59 1015,
05 05//0% / 00% 100%s
0.
91 20100umm
0% 70F /O5i 100VS
Qwend 1.50
0.08
24
115 10% / 1007 10%
0.22 e
76
/SS/0% / 110% 70%
0.12aam
S1.40aa1
(SS (0% / 100% /ORL
Uwend 7B
0006
U15 1007 1918 7r%
0.50ae
79.89
U55 1007% USS 700
0.34amm
55 25.50aa.m
UP5 1024 10% /CF
Qwend.5 32B
0.50
40.86 in
100% 10% /OS 006
2.
$0.41..
100% 000 05 10%
56.20....
100% 70% 10% 1O%
Exhecated Caresonng
4358 /219 1889 (198
0.40 en
79
44% 1499 0.6 IvV
0.38.
211 7219% 7779 7275
RouseLLM
2.01 c1
95% 20%
94.72...44
/0% 47%
RouseDDC
0.35-a
33.0--mm
/ 23% /30%
49% /22% 1228
0.91-am
99% 1175 11%
79.0
Cauquey
SesiallQA
47%)
Wisngnake
71R)
Sabestegory
Opersting
Regara
(Q1BA77RG)) 1tigo
Madel Ratio
Operatng
Requra
(037RO27TU 5ugg 10)
Matel Raio
Operatig:
Reqana
Madel Rado
Qwen2 3.5
0.26-441
43.35-uaa
0%
100%
0.12
a5
0% /0//0/0/5
0.15-am
14
70.0000000 00% 1000%
Qwen2 1.38
46.37
015/
10%
64.6..
0% 02% 100% 10%
0.20-am
61.13emr
100%
1,0
1009
/05//00
Quen2.5 32B
3:34
50.924914
100%
32.50.am
100% 0%
10%
1.59amm
70.93as.
100% (00 005/00
Eddecated Guessing
e.16
48.21
25%
/246
71.02amm
47% 445%
0.
67.36aa
45%
1138
RosneLLM
47 47.47
(5%%000)
/0% /356
73.85
07% /0% / (R//
1.71.. 69.05...
836 /010/00/0000 (05 176
Reunent)
1:26
48 48.00
37%
3322 1999 112%
0.75amm
70.5aam
6318 7.32% 215 758
1.05amm
70.73am
7118 1719 /115 115
MESS+ (ours)
1.13-m
47.65-2
34% 199 /388//3/LL
0.29
71.05-.u
45% /424 /36
0.33-am
66.36...
/356/200// /1598/159/44
adaptive routing approach that learns from online feedback since that enables adaptation to query characteristics without requiring explicit knowledge of task boundaries or distribution shifts. This robustness under non-stationary conditions validates the practical applicability of adaptive routing methods in production environments where query distributions naturally shift over time due to changing user behaviors, seasonal patterns, or evolving application requirements.
C.4.3 Experiments on Narrow Cost Spreads
The narrowed cost ratio configuration presents a more challenging routing scenario by reducing the cost differences between models, which tests the robustness of MESS+ when cost-performance trade-offs become less pronounced (Table [2). In this configuration, the cost spread between the largest and smallest models is compressed from the original wide range much narrower band, making routing decisions more nuanced.
Under these constrained conditions, MESS+ demonstrates strong results, achieving average oper- ating cost of 0.33 MJ a notable 68% improvement over RouterDC (1.05 MJ) and 81% improvement over RouteLLM (1.71 MJ). The narrowed cost spread reveals interesting behavioral adaptations in routing patterns. MESS+ maintains a balanced distribution (33% (5%/2%%) that heavily utilizes the smallest models, with the 0.5B model receiving 24% of calls compared to only 10-16% in previous configurations. This increased reliance on ultra- litra-lightweight models indicates that MESS+ successfully identifies queries that can be handled efficiently even when cost differences are minimal.
Yet, the overall results validate the theoretical expectation that routing becomes more challenging when cost differentials decrease. Interestingly, the Educated Guessing baseline performs comparably
32

---

Table 13: Results on the Qwen 2 Model Zoo with sparse Q updates. We randomly sample whether we do Q update from a uniform distribution with a threshold of 0.2.
Caiouey
ARC Challenge 655)
ARC Easy (o 71%5
BoolQ (or 80%)
Sahcatzgory
Opersting
Regend Suttchation
Madel call Ratio
Openstig
Rejerd Soridaction
(QTHIQTAUN Suggu
Madelcal Raio
Operrtig Cont
Reqand Sortifaction
(Q178/077AN)) SHAAA
Nodel Call Rain
Qwend 0.5B
30.0% 10.0%-ma
15% tr% /05L 1005
0:21
54 66
/5// 00% / 1008
63000pmm
(1% /00% 10% 1009
Qwen2 1.58
10ws
U16 DRL 1000 USS
0.28 es
06.62
USS D3 1001s /DRE
0.32+a
76.27
05% 100% 1001 (ORL
Quen
50.94.--
(1% 100%
0.700
75422...
05/ 1009
700
0.35.....
---13
/0FS
Qwend.5 32B
L.33...
58.25 28.25
100%
/05 10%
2.73.
-8.20...4
100%//02
700%
100% 105L /0YS
Cluessng
2.2%
RoueLLM
100%
100
999
1.4
87.30
576L 70% 10% 13%
Roonet))
1:30
MP% 116 199 F096
77.66
700 /19% 795-/88 N8
39
815 /89- 4/%
MESS+ (vurs)
1.41
44% / 28/// 1998 112
1.94.
67% /109 18/8 77%
1,27
31 28
8MK 1255 115//4/
Cauguey
LugiQA to 359))
PQQA (o 70%)
SeQ 90%)
Subcategory
Operaing
Cini
Sansfaction
Suttfaction
0.58
25.35
02 /0%
70%
0% 70% 100%
Qwen? 1.50
11R 10005 10%
0.31
0% (0% / 1100% 7.0
0.32aamm
96
USS (OF% 100% /OF
Quen? 73
05% 10009 105 70%
79 19
05 10079
7.09
DS. 100%% 10% /OPS
Qwen2.5 32B
0 0.50
40.86vs.e
10015: (2%L /O5 105
$0.41+4.
1007 00% 056 70%
96.70+...
100% F0% 10% /ORL
Educsical Carceing
10.90
S0r 2279 1888 108
0.71
79 19.02....
S91 3119 6359 286
0.46 04.35
25% 1348 / 2392 /279
Reuscl LMM
0.58
6472 00%
/36ls
1.01
70 28
9558 /0% (F9 5.5
0.68
94.72
536 /0/6 (9% 1477
Roonett3C
50%k 31% 1125 7718
0:74 e1
70.86c in
6.7% 1175 177 316
0:46ue
54.97am
305 100% / 12% 1ER
MENS (surs)
0.11...
34.07
34% /3/// L0K 124%
0.70
70.43..
59% /190//99///0 1388
0.86....
2%
71/6
Categeyy
SeciallQ
Wisognande
71%)
Meea
0075)
Sabcatzgory
Operatng
Reqeea Sansbetton
Model Lall Rati
Operanng
Cin
Sonuacttre
Regerd
Madeital Kann
Operatin
Unit
Reqeod Sarufaction
Model Call Ratn
Qwend 3.5
c. e1
01 (0%/005 /08 100%
m5 et
0SS / 100R
0.32+am
0% 70%% 005 100%
Qwend 1.30
0.36
D1s (1%
10096 U9%
0:00u en
USS (t8 11016/ URR
0.36
01.13amm
0% /05 100% /OFS
Qwa2
100% /O% 1.0%
0.23
71667
06 1000% 7.%
0.40...
67.07.-
0%
7OFS
Qwend
/015
72.30am
10475-
10%
Charsinn
67077
RoseLLM
47
65%
97%
35%
1,37-am
69.01..m
93% /0% 10% 17%.
1:04
48000
47%
/259 /10P /18
0.57
71.76
685 /279 196 99%
1.83
69 69.17
61/ 17% 9996 11.5
MESS+ (ours)
0,54
47.60-244
45% / 15RL
/ 188%
0,53
7144
67% /26
0.83.mm
67.474mm
49% / 185 / 1455/ 1198
to MESS+ in satisfaction (67.36% vs 66.36%) while requiring significantly higher costs (0.59 MJ vs 0.33 MJ), indicating that MESS+ maintains its core advantage of intelligent cost- cost-performance optimization even under adverse conditions.
C.4.4 Experiments on Sparse Q updates
The sparse Q-update configuration, where feedback is provided only 20% of the time (an 80% reduction compared to perfect conditions), tests the robustness of MESS+ under severely limited feedback signals (Table 13).
This scenario simulates realistic deployment conditions where user feedback is scarce expensive to obtain. Under these constrained learning conditions, MESS+ demonstrates remarkable resilience, maintaining an average operating cost of 0.82 MJ while achieving 67.47% request satisfaction. Compared to the full-feedback Qwen configuration (0.84 MI, 67.55% satisfaction), the performance degradation is minimal- only 2% cost increase and 0.08 percentage point satisfaction decrease on average. This suggests that MESS+ can operate effectively even with severely limited feedback signals. The sparse feedback results reveal that MESS+ maintains its cost leadership over competing methods, achieving 27% cost savings over RouterDC (1.13 MJ) and 40% over RouteLLM (1.37 MJ). The routing pattern shifts toward increased reliance on smaller models (19% usage of 0.5B model vs 16% in full feedback), indicating that the algorithm becomes more conservative when learning signals are limited, defaulting to cost-efficient choices when confidence is low.
The results demonstrate that adaptive routing methods can maintain practical effectiveness under more realistic feedback constraints, with MESS+ showing particular robustness sparse learning signals. This finding has important implications for production deployments where continuous user feedback may be limited or costly to collect.
C.4.5 Results with Models from the Llama and Qwen 2 Model Families
The mixed model zoo configuration, combining models from both Llama and Qwen families (Ta- ble [4), provides additional insights into the robustness of adaptive routing approaches across heterogeneous model architectures. This configuration demonstrates that MESS+ maintains strong performance even when operating across different LLM families, achieving an average operating cost of 0.98 MJ with 67. .7.47% request satisfaction, which strictly meets our SLA requirement (a = 0.67). Comparing the mixed configuration to the homogeneous Qwen setup reveals interesting trade-offs. While the pure Qwen configuration achieves slightly better cost efficiency (0.84 MJ vs 0.98 MJ), the
33

---

Table 14: The performance of MESS+ remains strong even when mixing models from different LLM families. Our approach works independently from any model internals since we only require user requests as input and a feedback signal.
Crigrey
ARC Chillenge 505
ABC Facy
71%)
RookQ
8%%)
Seleatzoory
Operatin
Sondiattion
Operatin
Sonudaction
Operatin
Sortifaction
(0 (501
0.30
0:31
055
055 /0FL
Lioma 3.2 1B
0.27
00%
10%
0.28
(0% 100% 10%
m
76 76.27
(SS 1001/ 10%L
Loma
50 10154..11
100F F05
0.700
15
156 1007%
0.25umm
86.13
US5
/1FL
Qwan25 32B
2.67
58.25 18.28.>-
1001/ 70% 00% 10%
2.73.am:
1007 10% /05 70%
$0.60.
100% 70% /0%/
Eddecated Carssing
55 33
645
416 / 2315 8.8
1:8
77.33a21
405 515 14556 7.6%
1:35amm
X0.07 30.07a0-0
M05 1106 / 73% 1%
RM
2.67-.41
58.16
10016 /0% /O5 100
2.
77.06.22
100% 00% 00% /Drg
L
87.3
875 /06 00% 13%%
RouseDD
1:64-441
56.01-21
/ /178 74%
77.8742.4
49% 225% 19%% /916
$9.53
855 100% /3% /2%
MESS (uur))
1.66
58.44
58%
P96
1.44
77.34
45%
76/s 77%
1,30
$1.75
185% 99//
Calgueyy
LugiQA (a 385)
PQQA
70%)
5dQ
93%)
Scheslegury
Openstng
Cot
Salihattio
Regera
(Q17B007RG) 10000 1R)
Madel Cull Pato
Opensing
Cont
Sotidaction
Regend
Catel Rato
Operatng
Ooit
Regand Suriifaation
(Q138/07700) 5RAgA (8)
Mal Rain
Qwen2 0.58
25.35
0% D% /00 100%s
0.37-um
69. 10.5++a io
0% 70% 00% 1007s
91 91.20 a.
0%/70% /05 100%
Lluma JB
0.08
24.27
01% DR/ 1005 0%
0:22 es
76.05
015
1001s DDR
0.12
94.40va
0% 7.0% 100% (O%L
Usma
18
05% 1009 (095 1rk
0.50
-9.49
05 10099 7
055
Qwen2.5 32B
0.50
40.86.a.
/00
2.31.a.
$0.41.4.
100%
1.
06.70
100%
Edhccated Guesing
25.36
1178 221%
0.55
15%g
95/20a..
2015
(0%)
79.28
055,
706 (0%
Rounett)
0.50
34.43
/220 /12%
790
709
0.
55 55.00as
85% 75% 39/
MESS+ (ours)
0.34
34 26.
39% / /192/219/////// /2F6
0.54
79.49
41% 29% / 225 88%
0,33
93.45
179l 12% / 366 33%
Canguoyy
SeciallQA (o- 47%)
Wizognande
71%)
Mean
Subcategory
Operatng
Sandaction
Operaing
Sandaction
Request
0.58
0.26...
/05
16.12
0% 702
Lioma 1.2
0
11% 70%
/0% 1101 700
USS 100% /1FF
Llama 3.1 8B
48.21ss 4:
OS/ 100% O0% 10%
0.4
71667
06 06/10055 100% 05 00
0.50..m 67.07..
0% 1004 10% 70%
Qwen2.5 32B
4:
10.92+4
100% 70%L OS 10%
72.30mam
100% /0000000000 0% Dr
199 70.9
100% 10% / 00% 7D%
Edhestal Carseiing
1.37
4700
911 / 147 3118 1148
0.54gmm
10.05a
ains 119% 998 /et
1.06a 67.02-
46% 1414 7992 111
RossLLLM
2.
47.4742
655) /05s: DR. 35%
7388520
97% /01 (S% 335
L
68.93420
83% /0S 00% 1798
1.50
S4% / 169 /30%
72,6
100% 00%
1:31
69 19-17
119% 42%
MESS+ (surr))
1.6
47.81
47%
0.52
70.31..
30% /479//77//9
0.98
67.47
14R
mixed setup shows comparable performance satisfaction levels. The mixed configuration exhibits a more balanced model call distribution (42% compared to the pure Qwen setup 0/////666///6//1999////
suggesting that the Llama 3.1 8B model provides a valuable intermediate capa- bility tier that complements the Qwen models effectively. Notably, the mixed configuration maintains MESS+'s 's cost benefits over other adaptive methods, with a 25% cost advantage over RouterDC (0.98 MJ vs 1.31 MJ) and a 45% advantage over RouteLLM (0.98 MJ vs 1.79 MJ). This demonstrates that our routing algorithm's effectiveness not dependent on model family homogeneity, as the method successfully leverages diverse model capabilities based solely on user request inputs and response feedback signals rather than model internals. The cross-family results also highlight the importance of model selection within heterogeneous zoos. The mixed configuration shows that Llama 3. 8B receives 27% of routing decisions on average, significantly higher than its Qwen 7B counterpart in the pure configuration (26%), suggesting that architectural differences between families can create complementary strengths that adaptive routing can exploit.
34


Reviews:
[{"review_id": "hv9kpwKtch", "reviewer": "Reviewer_Cuig", "summary": "This paper introduces MESS+ (Model Selection with Cost-optimal Service-level Guarantees), an per-request optimization algorithm to select an LLM from a set of models at inference time. with the objective to minimize cost while meeting a given service-level agreement.  The algorithm dynamically learns the probability of an LLM satisfying a user request in real-time and uses this information to make cost-optimal model selection decisions. MESS+ is doing so by using virtual queues to track performance over time, and then choosing the best model from solving the resulting optimization problem. Experimental results using various LLM benchmarks show that MESS+ can provide an average of 2x cost savings compared to existing LLM routing techniques, achieving the targeted request satisfaction rates with minimal overshoot.", "questions": "1) How would the cost and quality results change if MESS+ aimed for a quality level comparable to what baselines actually achieve, rather than a seemingly arbitrary alpha that other systems don’t accept? Would the cost margins shrink significantly?\n\n2) Initial exploration cost is quite high when all models in a zoo are being queried to learn a predictor model. Could the exploration phase be made more efficient by warm-starting the predictor with benchmark performance data for similar tasks? Alternatively, could a larger or pretrained model with better priors be used to reduce exploration cost and improve early performance?\n\n3) The current method assumes access to full feedback from all models in the zoo. This assumption is not realistic in many practical settings. How does the system perform when only partial feedback is available during the exploration phase, e.g., querying only a subset of models per input? Can the learning algorithm be adapted to handle such incomplete supervision robustly?\n\n4) The system is currently tested on a zoo with just three highly distinct model sizes (1B, 8B, 70B). How does performance (cost, routing accuracy, SLA satisfaction) scale as the zoo expands to include more models, especially those that are closer in performance or from different families? Are there diminishing returns or increases in misrouting as model separation becomes less obvious?\n\n5) How do you choose hyperparameters apha and V for real-world deployments?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) Clear motivation and context: The motivation of the paper is clearly stated and easy to follow. The problem is well-defined, and the authors clearly explain how their approach differs from prior work, especially in terms of the tradeoffs it considers.\n\n2) Strong theoretical foundation: The algorithmic framework is grounded in stochastic control theory. The mathematical formulation provide a clear rationale for the proposed algorithm. The system offers theoretical guarantees for meeting user-defined constraints or SLAs, making it a practical option in real-world settings where users require a minimum performance level while minimizing cost.\n\n3) Careful evaluation: The system is evaluated on a diverse set of benchmarks. Results consistently show that it can reduce operating costs while maintaining target performance. Notably, it does so without relying on explicit routing preference datasets, thanks to the use of an online learning algorithm. Furthermore, the authors conduct ablations on key hyperparameters (α and V), providing insight into their influence. They also account for the cost overhead introduced by the router/predictor, which strengthens the evaluation.\n\nWeaknesses:\n1) Strong assumption on model feedback: MESS+ assumes access to feedback from all models in the zoo to train the predictor. Although the authors acknowledge this as a limitation, it remains a significant practical concern. In many real-world scenarios, such feedback may not be available, especially in the absence of a perfect automatic verifier. Despite this, the benchmarks assume full access to high-quality feedback, which may not generalize to more constrained or noisy settings.\n\n2) Unfair comparison with baselines: MESS++ is benchmarked under fixed SLA constraints, while baselines are allowed to exceed these constraints. This leads to a comparison where baselines achieve higher satisfaction rates, which is interpreted solely as inefficiency. However, this could also be the result of MESS++ choosing a more favorable point in the quality-cost tradeoff space. I understand that arriving to this tradeoff point is actually a strength of MESS++, but still this might be unfair to competing approaches.  Furthermore, this makes it difficult to isolate the true benefits of MESS+ under realistic deployment tradeoffs. One possibility would be to pick as target the request satisfaction given by competing approaches and then measure the reduction in cost achieved by MESS+ for this target.\n\n3) Limited model diversity: The evaluation uses a model zoo of only three models, with significantly different sizes (1B, 8B, 70B). This setup likely makes routing easier, as the models are highly separable in quality and cost. In real-world deployments, model zoos may include many more models with subtler differences. It is unclear how well MESS+ would perform in such cases, where the quality-cost tradeoffs are less clear-cut.\n\n4) Unclear hyperparameter choices: The paper introduces two hyperparameters that users would have to define / learn for their\nspecific routing use case, and how they might choose them is not immediately clear.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review of our paper and the positive feedback! \nWe first respond to the weaknesses and then to your questions. We combine answers where appropriate. \n\n**W1 & Q3)** We appreciate your observation and have explicitly acknowledged this limitation in our paper. The primary goal of our work is to propose a theoretically grounded routing method that can learn from online feedback. It is important to note that we do not assume access to high-quality or rich feedback. Instead, our preference estimation mechanism relies solely on binary signals, such as the thumbs-up or thumbs-down feedback provided by users interacting with LLMs through chat interfaces. Nevertheless, we agree that collecting feedback across multiple models can be impractical in some real-world scenarios. In principle, MESS+ could be adapted to handle partial feedback. Since our objective function requires a signal for the request satisfaction likelihood and the cost for an incoming request, partial feedback could be supported by swapping out our current classifier-based request satisfaction predictor for a technique that can learn from incomplete or delayed feedback. A detailed study on partial feedback is beyond the scope of this paper and thus left for future work, where our approach can serve as a well-founded starting point for such studies.\n\n**W2 & Q1)** It is true that the baselines are allowed to exceed $\\alpha$ (our SLA requirement), but we made sure to choose a configuration that is as close as possible to our problem setup. For the RouteLLM baseline, we tuned the decision threshold  to minimize the cost required to meet $\\alpha$ (Appendix B in the supplementary material, Table 2); for RouterDC that requires training a small encoder model, we performed this additional training step on the training split of our benchmark tasks based on the recommended procedure in the RouterDC paper.\nEven after these adjustments, we still observe that both RouteLLM and RouterDC have a tendency of preferring the largest model, especially in the beginning, whereas MESS+ takes a more conservative and cost-focused approach.\nThis difference is clearly rooted in the different objectives of routing approaches (max. response quality vs. appropriate response quality under a given SLA). We will better highlight the distinct objectives of RouteLLM, RouterDC, and MESS+ in the next version of our paper.\nWhen we choose a smaller $V$, MESS+ becomes more likely to also prefer the largest model in the zoo, and the cost gap towards the routing baselines becomes smaller. Our appendix includes additional experiments on various SLA requirements for a more thorough overview (Figures C.2 and C.3).\n\n**W3)** We conducted additional experiments on a larger model zoo with 4 models from the Qwen 2 family, with a smaller parameter range (0.5B, 1.5B, 7B, 32B).\nBelow, we report the average performance of MESS+ across the 8 benchmarks in our paper with $\\alpha = 0.67$. In the larger zoo, MESS+ outperforms the baselines (Table I below). This demonstrates that our approach can effectively route larger zoos with models that have less distinct energy characteristics. We will include the detailed additional results in our updated paper. \n\nTable I: Additional experiments on a larger zoo with 4 Qwen 2 models - Avg. across 8 benchmarks ($\\alpha = 0.67$)\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/Q7B/Q1.5B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.12±0.01 | 54.12±45.15 | 0% / 0% / 0% / 100% |\n| Qwen2 1.5B | 0.16±0.01 | 61.13±4.79 | 0% / 0% / 100% / 0% |\n| Qwen2 7B | 0.40±0.01 | 67.07±4.61 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 1.60±0.01 | 70.91±4.48 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 0.99±0.01 | 67.02±2.32 | 53% / 26% / 11% / 10% |\n| RouteLLM | 1.37±0.01 | 69.01±2.31 | 83% / 0% / 0% / 17% |\n| RouterDC | 1.13±0.01 | 69.17±2.47 | 63% / 17% / 9% / 11% |\n| **MESS+ (ours)** | **0.84±0.01** | 67.55±3.23 | 48% / 26% / 10% / 16% |\n\n**W4 & Q5)** In general, $\\alpha$ should be between the highest and lowest satisfaction rates of all the models in the zoo. To determine $\\alpha$ in practice, one can observe how well individual models serve user requests (e.g., based on chat feedback through a thumbs-up/-down mechanism), which can serve as a basis for estimating the performance of models. From an algorithmic perspective, $\\alpha$ is given as an input that specifies the SLA requirement, so we may tune other parameters, such as $V$, to meet $\\alpha$ after processing some pre-specified number of requests. \n\nThe parameter $V$ serves as a control parameter for scaling (or a way of normalizing) the cost to the same (or similar) order of magnitude as $\\alpha$. While having a large $V$ is generally possible, it would take an impractically long time for the average request satisfaction to converge against $\\alpha$. A good starting point for tuning $V$ is to set $V = 10^{-m}$, where $m$ is the order of magnitude of the cost per request of the largest model.\n\nWe will make this selection process more clear in our updated paper. \n\n**Q2)** Yes, pre-training the predictor on data for similar tasks and establishing strong priors can reduce the exploration cost at the start. Note, however, that a benefit of MESS+ is that it can adapt over time, i.e., some exploration over time is desirable to dynamically adapt to changing user requirements."}, {"review_id": "W9JHwaZ5bK", "reviewer": "Reviewer_tW9L", "summary": "This paper presents MESS+, a novel algorithm designed to automatically and efficiently select the best Large Language Model (LLM) from a \"zoo\" of different models. The core challenge it addresses is balancing the competing interests of end-users, who want high-quality responses, and service providers, who want to minimize operating costs.\n\nMESS+ formulates this challenge as a stochastic optimization problem. It works by learning in real-time, as users interact with the system, to predict the probability that any given LLM in the zoo can satisfy an incoming request. For each request, the algorithm then chooses the most cost-effective model that is likely to meet a predefined Service Level Agreement (SLA), which guarantees a minimum rate of user satisfaction over time.\n\nThe authors provide a theoretical analysis of the algorithm's performance and demonstrate its effectiveness through experiments. Results show that, on average, MESS+ can reduce operating costs by a factor of two compared to existing LLM routing techniques while successfully upholding the required service quality.", "questions": "- Why user satisfaction is limited to a binary value? For more open-ended queries, binary value may not capture user feedback precisely.\n- In Table 2, how are the values of $\\alpha$ determined? Does MESS+ ensure satisfaction of SLA at all different values of $\\alpha$ beyond these 3 picked points? Also, does MESS+ achieves the lowest cost among all competing methods at every point?\n- As RouteLLM and RouterDC are not designed for SLA constraints, how are their operating point selected given a specific $\\alpha$?", "limitations": "Yes, limitations are sufficiently discussed in the conclusion section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The routing problem setting with SLA constraint is novel and practical.\n- The proposed approach is grounded with solid theoretical analysis.\n- The main experiment results demonstrates the effectiveness of MESS.\n\nWeakness:\n- As acknowledged by the authors, the method requires user satisfaction labels on the fly, which is usually not a practical assumption.\n- Please see questions section.", "was_revised": true, "final_justification": "The authors sufficiently addressed my concerns, so I raised my score to 5.\n\nW1: Addition experiments make sense. \nQ1: \"We focus on binary feedback in our work because requiring users to score responses on scales such as Likert scales demands more effort and could produce even sparser feedback than simple binary signals\", I agree that binary feedback is a more practical choice, and I believe the framework can be extended to non-binary cases (adding additional experiments is beyond this paper's scope). \nQ2: Exploration of varying $\\alpha$ is in the supplement. \nQ3: The authors promise to highlight the distinct objectives of RouteLLM, RouterDC, and MESS+ in the next version of their paper.", "rebuttal": "Thank you for your positive feedback and the thorough review of our paper! \nWe will first address the weaknesses and then your questions.\n\n**W1)** When deploying inference services, monitoring the fit for purpose is an integral part of a reliable and robust pipeline. A large part typically consists of capturing SLA compliance to ensure the client receives a service they are paying for.\nIn applications with such SLA requirements, there needs to be a mechanism to log whether the AI model is able to successfully process user requests. If unsuccessful, the same request would have to be processed by other means (e.g., by a human). Therefore, such satisfaction logs would naturally exist in real systems, so we believe that it is reasonable to assume that a user satisfaction indicator is available after we get the response from the model. In addition, our MESS+ algorithm can be extended to scenarios where the feedback is sparsely available, e.g., the feedback is only collected on a uniformly randomly sampled subset of requests, and we only update the virtual queue when such feedback is available. Statistically, because such sampling is done in an IID manner, the expected SLA satisfaction would be the same as the true SLA satisfaction over all requests. We conduct an extra experiment to show this (Table I below). We sample from a uniform distribution limited to values in the range between $[0, 1]$ and set the threshold to 20% (max. rel. number of requests in an experiment that will be used for updating $Q$). We only update $Q$ whenever there is feedback available.\nAs can be seen even under sparse feedback MESS+ is still able to satisfy the SLA requirement but relies more on more cost efficient models. This is because $Q$ captures fewer SLA violations that might occur over time and stabilization of $Q$ takes longer.\n\nTable I: Additional results when receiving sparse user feedback - Mean over 8 benchmarks ($\\alpha=0.67$, 20% user participation)\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/Q7B/Q1.5B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.12±0.01 | 54.12±45.15 | 0% / 0% / 0% / 100% |\n| Qwen2 1.5B | 0.16±0.01 | 61.13±4.79 | 0% / 0% / 100% / 0% |\n| Qwen2 7B | 0.40±0.01 | 67.07±4.61 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 1.60±0.01 | 70.91±4.48 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 0.99±0.01 | 67.02±2.32 | 53% / 26% / 11% / 10% |\n| RouteLLM | 1.37±0.01 | 69.01±2.31 | 83% / 0% / 0% / 17% |\n| RouterDC | 1.13±0.01 | 69.17±2.47 | 63% / 17% / 9% / 11% |\n| **MESS+ (ours)** | **0.82±0.01** | 67.47±3.35 | 49% / 18% / 14% / 19% |\n\n**Q1)** Binary feedback is the most challenging data to learn from as signals are very coarse. \nWhen looking at practical applications (e.g., chat applications like ChatGPT) they usually have a small thumbs-up/-down button next to each generated response. Our predictor takes such feedback as an input. We focus on binary feedback in our work because requiring users to score responses on scales such as Likert scales demands more effort and could produce even sparser feedback than simple binary signals.\nHowever, our MESS+ algorithm can be directly extended to operate on more granular feedback signals and the procedure remains the same, with the only difference that the user satisfaction $s_{m,t}$ would be a non-binary value.\n\n**Q2)** The parameter $\\alpha$ serves as an input to the MESS+ algorithm. The algorithm guarantees SLA compliance for any $\\alpha$ value that falls within the performance range of the available model zoo. In our experimental setup, we selected $\\alpha$ values positioned within the model zoo's capabilities. While the selection of $V$ influences the convergence time to SLA compliance, our theoretical analysis demonstrates that the algorithm will eventually achieve the target $\\alpha$ regardless of the initial conditions.\nAdditional experimental results exploring different $\\alpha$ values can be found in the supplementary material (Figures C.2 and C.3).\n\n**Q3)** For the RouteLLM baseline, we tuned the decision threshold  to minimize the cost required to meet $\\alpha$ (Appendix B in the supplementary material, Table 2); for RouterDC that requires training a small encoder model, we performed this additional training step on the training split of our benchmark tasks based on the recommended procedure in the RouterDC paper.\nEven after these adjustments, we still observe that both RouteLLM and RouterDC have a tendency of preferring the largest model, especially in the beginning, whereas MESS+ takes a more conservative and cost-focused approach.\nThis difference is clearly rooted in the different objectives of routing approaches (max. response quality vs. appropriate response quality under a given SLA). We will better highlight the distinct objectives of RouteLLM, RouterDC, and MESS+ in the next version of our paper.\nWhen we choose a smaller $V$, MESS+ becomes more likely to also prefer the largest model in the zoo, and the cost gap towards the routing baselines becomes smaller. Our appendix includes additional experiments on various SLA requirements for a more thorough overview (Figures C.2 and C.3)."}, {"review_id": "fFQdbL6FEG", "reviewer": "Reviewer_9ALn", "summary": "As Gen AI models, including LLMs, continue to get commoditized, leveraging a plurality of models helps meet varying user/customer performance needs as well as minimize resource utilization. This paper addresses the problem of how to select the best LLM per user query by casting satisfaction of service-level agreements by model hosts and optimal resource utilization of a given query as competing objectives of an online optimization problem. The authors provide both theoretical guarantees (Section 3) as well as empirical evaluation across 8 benchmark datasets and 3 model sizes of the Llama family. Results show that the proposed approach outperforms related approaches on benchmark datasets and selected models.", "questions": "1. How would the proposed approach deal with non-stationary and open-ended task compilations?\n2. How would the approach fare in the presence of task-specific, fine-tuned models?\n3. Table 2 is too dense with tiny fonts. Is there an alternate way to present these results?\n4. Might it be better to refer to the approach as \"inference-time or deployment-time\", instead of \"test-time?\" That would also help with the clarity.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. A novel approach, supported by a combination of theoretical analysis and experimental results. The theoretical guarantees distinguish this work from related approaches.\n2. The paper writing is good, providing a good explanation of results via separate cost analysis, model call ratio, approach overhead costs, user satisfaction prediction.\n3. Good coverage of competing approaches and their use in comparative evaluation.\n4. Appreciate the clear callout of contributions at the end of section 1: many submissions miss out on this helpful practice that supports clarity.\n5. Similarly, Table 1 provides a good overview, as well as a relative comparison of baseline approaches.\n6. Publicly available code supports reproducibility.\nWeaknesses\n1. Outside of benchmarks, where ground-truth labels support model calibration, it is unclear how to learn the relative ability of the various models in the model zoo.\n2. Solution has been tested with only 3 models from the same model family.\n3. Ablation study, quantifying the relative contributions of satisfaction predictor and the quality of the online optimization, for example, is missing.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our manuscript and your positive feedback!\nIn the following, we will first address the weaknesses (in the original numbering in the review) and then your questions.\n\n**W7)** It is challenging to obtain ground truth, but our approach relies on a model that estimates the probability that a model can satisfy a user request. In practice, we learn our predictor based on online user feedback (a binary signal, which can be a thumbs up or down as frequently seen in chat interfaces). These events are collected over time and used to train the user satisfaction predictor that estimates the ability of a model. \n\n**W8)** We have conducted additional experiments on a larger model zoo. Our results on the Qwen 2 model family (0.5B, 1.5B, 7B, 32B) also demonstrate the strong performance of MESS+ compared to the baselines in our paper (Table I below). We will include detailed results in our updated paper.\n\nTable I: Additional experiments on a larger zoo with 4 Qwen 2 models - Avg. across 8 benchmarks ($\\alpha = 0.67$)\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/Q7B/Q1.5B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.12±0.01 | 54.12±45.15 | 0% / 0% / 0% / 100% |\n| Qwen2 1.5B | 0.16±0.01 | 61.13±4.79 | 0% / 0% / 100% / 0% |\n| Qwen2 7B | 0.40±0.01 | 67.07±4.61 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 1.60±0.01 | 70.91±4.48 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 0.99±0.01 | 67.02±2.32 | 53% / 26% / 11% / 10% |\n| RouteLLM | 1.37±0.01 | 69.01±2.31 | 83% / 0% / 0% / 17% |\n| RouterDC | 1.13±0.01 | 69.17±2.47 | 63% / 17% / 9% / 11% |\n| **MESS+ (ours)** | **0.84±0.01** | 67.55±3.23 | 48% / 26% / 10% / 16% |\n\n**W9)** MESS+ only works when using both the predictor and the online optimization together. \nWithout the predictor, online optimization cannot work, because the online optimization objective (3a) requires $\\hat{s}_{m,t}$ that is provided by the predictor. If we naively modify (3a) to remove the second term altogether, the algorithm would always choose the smallest model that gives the lowest cost, which obviously will not give a satisfactory performance. If we do not do the online optimization, the current algorithm does not use the predictor in any other step, so the predictor would be redundant in that case and no model choice would be made. In other words, the online optimization in (3) is the only step that decides which model to choose and it requires the predictor output as its input.\n\n**Q1)** We have conducted additional experiments where we *concatenate multiple benchmarks in a single experiment (ARC Challenge, PiQA, Winogrande)*. In doing so, we create a non-IID scenario ($\\alpha = 0.67$). The results are in Table II below.\nWe observe a slightly larger gap between $\\alpha$ and the final MESS+ accuracy than what we see for the individual benchmarks (1.57% vs. 0.55%).\nDue to the change in data distribution over time, training the predictor becomes more challenging, and we have observed slightly increased training loss fluctuation compared to the individual benchmarks in our experiments (not presented here since we cannot include plots in the rebuttal), especially at the beginning of each new benchmark.\nNonetheless, MESS+ still satisfies our SLA requirement and outperforms our Educated Guessing baseline. **Q1)** We have conducted additional experiments where we *concatenate multiple benchmarks in a single experiment (ARC Challenge, PiQA, Winogrande)*. In doing so, we create a non-IID scenario ($\\alpha = 0.67$). The results are in Table II below.\nWe observe a slightly larger gap between $\\alpha$ and the final MESS+ accuracy than what we see for the individual benchmarks (1.57% vs. 0.55%).\nDue to the change in data distribution over time, training the predictor becomes more challenging, and we have observed slightly increased training loss fluctuation compared to the individual benchmarks in our experiments (not presented here since we cannot include plots in the rebuttal), especially at the beginning of each new benchmark.\nNonetheless, MESS+ still satisfies our SLA requirement and outperforms our Educated Guessing baseline. \nWe will include these insights in our updated paper.\n\nTable II: Additional experiments with non-IID requests - 3 benchmarks concatenated (ARC Challenge, PiQA, Winogrande)($\\alpha = 0.67$)\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/Q7B/Q1.5B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.26±0.01      | 54.50±49.80 | 0% / 0% / 0% / 100% |\n| Qwen2 1.5B | 0.35±0.01      | 62.92±5.37 | 0% / 0% / 100% / 0% |\n| Qwen2 7B | 0.93±0.01      | 69.35±5.12 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 3.12±0.01      | 71.94±4.99 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 2.33±0.01      | 71.44±2.16 | 70% / 11% / 9% / 10% |\n| RouteLLM | 2.96±0.01  | 72.38±3.29 | 97% / 0% / 0% / 3% |\n| RouterDC | 2.24±0.01      | 72.36±2.46 | 68% / 15% / 4% / 13% |\n| **MESS+ (ours)** | **2.07±0.01**  | 68.57±2.28 | 66% / 19% / 8% / 7% |\n\n**Q2)** MESS+ requires the models in a zoo to have varying cost characteristics and be capable of addressing the same or overlapping tasks. When multiple models have overlapping expertise for specific tasks, regardless of whether they have been fine-tuned or not, MESS+ can effectively learn to identify the most adequate model with minimum operating cost by solving the online decision making problem (3). This is orthogonal to the problem of selecting from disjoint expert models that handle separate, non-overlapping tasks.\n\n**Q3)** We will make use of the extra page for a potential camera ready version to improve the readability of Table 2.\n\n**Q4)** We are happy to change the title to “inference-time”."}, {"review_id": "QAZ28ZMOpv", "reviewer": "Reviewer_28jX", "summary": "This paper presents MESS+, an algorithm for optimally routing requests across multiple language models (LLM zoo) while maintaining service level guarantees and minimizing operating costs. Here are the key points and contributions:\n\nMain Problem Addressed:\n- How to automatically select the most cost-efficient LLM for each request while ensuring a minimum quality level specified by Service Level Agreements (SLAs)\n- Balancing between user needs (high-quality responses) and provider needs (low operating costs)\n\nKey Components of MESS+:\n1. Online Learning System:\n- Dynamically learns which models can satisfy which types of requests\n- Uses ModernBERT-based predictor to estimate satisfaction probabilities\n- Adapts through exploration/exploitation strategy\n\n2. Cost Optimization Framework:\n- Uses virtual queues to track SLA compliance\n- Solves per-request optimization problem considering both costs and predicted satisfaction\n- Provides theoretical guarantees for both cost optimality and SLA compliance\n\n3. SLA Guarantee Mechanism:\n- Maintains minimum satisfaction rate (α) over time\n- Uses virtual queue system to track and correct violations\n- Allows configuration of trade-off between quick convergence and cost efficiency\n\nResults:\n- Achieves 2x cost savings compared to existing routing techniques\n- Successfully maintains SLA requirements across various benchmarks\n- Demonstrates effectiveness across different types of language tasks\n\nThe paper's main contribution is a theoretically grounded framework that, for the first time, provides both cost optimization and rigorous service level guarantees for LLM request routing, while learning request satisfaction patterns online without requiring pre-curated routing datasets.", "questions": "1. Predictor Architecture Details [**Good to have**]\nQuestion: Could you provide more specific details about the ModernBERT-based predictor implementation?\n- How exactly is the classifier implemented on top of ModernBERT?\n- Which layers are frozen vs. trained?\n- What is the rationale for these architectural choices?\nImpact: This information is crucial for reproducibility and understanding the method's practical requirements. A detailed response could increase the quality score by demonstrating the robustness of the technical implementation.\n\n2. Cross-Model Family Performance [**Highly Important**]\nQuestion: Have you tested MESS+ across different model families?\n- How does performance vary when mixing models from different providers?\n- Are there specific characteristics that make certain model combinations more effective?\n- What modifications might be needed for heterogeneous model zoos?\nImpact: Demonstrating broader applicability across model families would strengthen the paper's generalizability claims. Positive results could increase both significance and originality scores.\n\n3. Cost Structure Analysis [**Highly important**]\nQuestion: Could you provide more detailed analysis of:\n- How different cost structures affect routing decisions?\n- The impact of varying cost ratios between models?\n- The relationship between exploration costs and long-term benefits?\nImpact: This would help readers understand the economic implications of deployment. Clear analysis could increase the paper's practical significance score.\n\nAdditional Suggestions:\n- Consider including simple baseline comparisons (e.g., random routing, knn router, mlp router; c.f. RouterBench). Some of them can be adapted to online setting, but even comparing to the offline baseline is valuable.\n- Add analysis of failure cases or edge conditions\n- Provide guidelines for selecting hyperparameters (V, c) in practice", "limitations": "The authors have partially addressed limitations, but there are several areas that could benefit from more thorough discussion:\n\n1. Technical Limitations\nThe paper discusses some key technical limitations in Section 5:\n- Dependency on readily available user satisfaction labels\n- Challenges with multiple model exploration\nHowever, it could benefit from addressing:\n- Scalability limitations with very large model zoos\n- Performance degradation scenarios\n- Resource requirements for the prediction system\n\n2. Societal Impact\nMissing discussions on:\n- Potential misuse of cost optimization at the expense of quality\n- Privacy implications of collecting user satisfaction data\n- Fairness considerations in satisfaction prediction across different user groups\n- Potential bias of the router\n\n3. Deployment Risks\nShould address:\n- Risks of system manipulation through adversarial requests\n- Failure modes in high-stakes applications\n- Security considerations for the routing system\n\nSuggestion: Add a dedicated section discussing these aspects comprehensively, particularly focusing on the societal and ethical implications of automated decision-making in service provision.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths:\n\n1. Theoretical Foundation\n- Provides rigorous theoretical guarantees for both cost optimality and SLA compliance\n- Clear mathematical framework based on Lyapunov optimization\n- Theorems are well-stated with complete proofs referenced in appendix\n\n2. Novel Approach\n- Introduces online learning component that eliminates need for curated datasets\n- Novel integration of virtual queues with satisfaction prediction\n\n3. Empirical Validation\n- Comprehensive evaluation across 8 different benchmarks\n- Clear ablation studies showing impact of different parameters\n\n## Weaknesses:\n\n1. Implementation Details\n- Limited details about the ModernBERT predictor architecture\n- Missing specifics about classifier design on top of ModernBERT\n- Could benefit from more details about hyperparameter selection\n\n2. Practical Limitations\n- Assumes immediate availability of user satisfaction feedback\n- Requires querying all models during exploration phase, which could be expensive\n- May need significant number of requests before convergence\n- The authors acknowledge these limitations but don't propose solutions\n\n3. Experimental Scope\n- All experiments use same family of models (Llama) and only 3 models in the model zoo\n- Could benefit from testing across different model families and more models\n- Limited discussion of how performance varies with different types of requests\n\n4. Theoretical Assumptions\n- Some assumptions (like i.i.d. requests) may not hold in practice\n- Convergence guarantees require large number of requests\n- Trade-off between exploration and exploitation could be explored more thoroughly\n\n5. Comparisons\n- Could include comparison with simpler baselines (e.g., random routing with cost threshold, nearest neighbor routing, etc)\n- No discussion of failure cases or edge conditions", "was_revised": true, "final_justification": "The authors have addressed all my raised points in the rebuttal. I highly suggest the authors to include these analysis into the paper.", "rebuttal": "Thank you for your thorough review! \nWe will first address your questions based on their impact and then reply to the weaknesses. \n\n**Q2 & W3)** Our response consists of three parts. Part A addresses mixed-provider model zoos, part B specific characteristics and heterogeneous zoos, and part C weakness 3.\n\nPart A: We include a new model zoo that mixes Llama 3 and Qwen 2 models. MESS+ maintains strong performance compared to our Educated Guessing baseline. \nWe will include these results along with a full comparison against all baselines that we could not do due to time constraints in our updated paper.\n\n\nTable I: Mixed zoo with Llama 3 and Qwen 2 models.\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/L8B/L1B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.15±0.01 | 54.12±45.15 | 0% / 0% / 0% / 100% |\n| Llama 3.2 1B | 0.20±0.01 | 61.13±4.79 | 0% / 0% / 100% / 0% |\n| Llama 3.1 8B | 0.50±0.01 | 67.07±4.61 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 1.99±0.01 | 70.91±4.48 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 1.06±0.01 | 67.69±2.30 | 46% / 14% / 29% / 11% |\n| **MESS+ (ours)** | **0.98±0.01** | 67.47±3.28 | 42% / 27% / 17% / 14% |\n\nPart B: Our approach can be used with any zoo as long as there are user satisfaction feedback and operating cost measurements. Regarding specific model combinations, MESS+ works best with models that have distinct cost characteristics as our problem setting (Equation 3) optimizes for operating cost.\n\nPart C: We conducted additional experiments on a different, larger model zoo using the Qwen 2 model family (0.5B, 1.5B, 7B, 32B). \nOur additional results further underpin the performance of MESS+. In Table I (see rebuttal for reviewer 9ALn), we show the average performance across the 8 benchmarks discussed in our paper ($\\alpha = 0.67$). We will include the detailed results in our updated paper.\nMESS+ benefits from distinct models in a zoo, i.e., the more the performance and cost characteristics of models in a zoo vary, the better our routing works. This results from our objective function where we trade off model performance for operating cost. \n\n**Q3)** We answer this question in two parts. The first part (A) is a combined answer regarding varying cost structures and ratios and the second (B) outlines the exploration vs. exploitation cost when using different $c$ values for MESS+. \n\nPart A: We reduce the cost spread in the Qwen2 zoo by a factor of 2x, centering the cost closer around the mean cost per requst across models. Consequently, this also changes the cost structure in our zoo. This makes it more challenging for MESS+ to route requests. As can be seen in  Table II below, MESS+ maintains its performance even with a more homogeneous cost structure.\nWe will include these additional results in our updated paper.\n\nTable II: Experiments on the Qwen 2 model zoo with a 2x squeezed cost ratio around the average inference cost per request\n| Category | Operating Cost | Request Satisfaction | Model Call Ratio (Q32B/Q7B/Q1.5B/Q0.5B) |\n|---|---|---|---|\n| Qwen2 0.5B | 0.15±0.01 | 54.12±45.15 | 0% / 0% / 0% / 100% |\n| Qwen2 1.5B | 0.20±0.01 | 61.13±4.79 | 0% / 0% / 100% / 0% |\n| Qwen2 7B | 0.50±0.01 | 67.07±4.61 | 0% / 100% / 0% / 0% |\n| Qwen2.5 32B | 1.99±0.01 | 70.91±4.48 | 100% / 0% / 0% / 0% |\n| Educated Guessing | 0.59±0.01 | 67.36±2.46 | 45% / 29% / 13% / 13% |\n| **MESS+ (ours)** | **0.33±0.01** | 66.36±3.68 | 33% / 29% / 15% / 24% |\n\nPart B: Using models from the Qwen 2 family, we analyzed costs for exploration (querying the model zoo to train the classifier) versus LLM inference (using the trained predictor). Table III shows average results across 8 benchmarks for the first 500 requests per benchmark.\nWe found that $c=0.01$ causes slow predictor learning, requiring well beyond 500 steps to reach SLA compliance, while $c=1.0$ wastes resources on excessive training. The optimal value $c=0.1$ balances exploration and inference costs. As designed, MESS+ reduces exploration probability over time, making inference costs eventually dominate. These insights will be included in our updated paper.\n\n\nTable III: Exploration vs. Exploitation cost in the Qwen 2 model zoo\n| c | Exploration Cost @ 500 steps (in MJ) | LLM Inference (Exploitation) Cost @ 500 steps (in MJ) | Mean Benchmark Accuracy @ 500 steps ($\\alpha = 0.67$) |\n|---|---|---|---|\n| 0.01 | 0.09 ± 0.01 | 0.15 ± 0.01 | 0.40 ± 0.01 |\n| 0.1  | 0.46 ± 0.01 | 0.11 ± 0.01 | 0.68 ± 0.01 |\n| 1.0  | 0.56 ± 0.01 | 0.10 ± 0.01 | 0.70 ± 0.01 |\n\n\n**Q1 & W1)** We cited the paper that introduces the ModernBERT architecture as reference [25] in our paper. The classification layer on top of the ModernBERT transformer is described in detail in our supplementary material.\nThe exact hyperparameter choice is based on a hyperparameter sweep and is also described in our supplementary material. We included a link to our code base in the supplementary material (Appendix B at the end). The code base will be made public, if accepted.\n\n**W2)** We divide this response into three parts. The first (A) addresses sparsely available feedback and the second (B) predictor convergence, and the third (C) the limitations of our work.\n\nPart A: MESS+ can be directly extended to work on sparse feedback, i.e., only a small number of users submit (complete) feedback. We show results when only 20% of users submit feedback (Table I in response to Reviewer tW9L). We emulate this behavior by sampling from a uniform distribution with values $[0, 1]$ using a threshold of 20%. We only update $Q$ whenever there is feedback available.\nWe observer that MESS+ shows strong performance, even when feedback is only sparsely available. However, it takes longer to satisfy the SLA requirement as $Q$ captures fewer SLA violations that might occur over time and stabilization of $Q$ takes longer. This also leads to MESS+ preferring cost efficient models more than in scenarios with abundant feedback. \n\nPart B: Figure 3 in our paper shows that our predictor training quickly converges well within 100 incoming requests (avg. across 8 benchmarks), which, in practice, equals a very small cost. With $c$, we can control how often we want to update our predictor and account for the difficulty of a workload, i.e., the more difficult a workload, the more we want to train our predictor in the beginning.\n\nPart C: Yes, we outline the limitations to offer a genuine avenue for future work. Detailed solutions to address these limitations are beyond the scope of this paper.\n\n\n**W4)** We separate our response into three parts. The first (A) addresses the IIDness assumption, the second (B) discusses convergence, and the third (C) the trade-off.\n\nPart A: We conducted additional experiments concatenating multiple benchmarks (*concatenated  ARC Challenge, PiQA, Winogrande benchmarks in a single experiment*) to create a non-IID scenario (α = 0.67). Results show a slightly larger gap between α and final MESS+ accuracy (1.57% vs. 0.55% for individual benchmarks, see Table I Reviewer tW9L). The changing data distribution makes predictor training more challenging, causing increased training loss fluctuation (not presented here since we cannot include plots in the rebuttal). However, MESS+ still meets our SLA requirement and outperforms the Educated Guessing baseline. These findings will be included in our updated paper.\n\nPart B: We underpin the effectiveness of MESS+ with our experiments on evaluating a diverse set of benchmarks and verying $c$ values. Our experiments show that the predictor learns quickly (even under non-IID settings) and converges within a practical amount of time.\n\nPart C: The experimental results on the tradeoff between exploration and exploitation have been presented and discussed in our response to Q3 above.\nTheoretically, $\\psi$ (defined in Assumption 1) quantifies how long it takes to obtain a \"good enough\" predictor. As shown in Corollary 1 (first inequality, before big-O), when $\\psi$ is large (which occurs when we explore less), it takes a longer time to meet the same level of SLA satisfaction. This is validated by the results in the last column of Table II in our response to Reviewer 9ALn.\nFor the cost optimality, our upper bound on the total cost in Theorem 2 can be extended to $E^\\textnormal{OPT} +\\mathcal{O}\\left(\\frac{M\\left(\\frac{1}{c}+c\\right)}{\\sqrt[4]{T}} + \\frac{1}{V} + F_\\mathrm{min}  \\right)$ by writing out $c$ inside the big-O notation in our proof. Here, the term $\\frac{1}{c}$ captures the reduction in exploitation cost when we have a better predictor by exploring more with a larger $c$, and the term $c$ captures the added cost due to exploration. This tradeoff has also been validated in the second and third columns of Table III.\n\n\n**W5 & Additional Suggestions)** We have already included baselines that do random routing (“educated guessing”) and MLP-based routing (e.g., RouteLLM) to provide a thorough performance comparison. \nWe consider average SLA satisfaction over time, which smoothens out extreme cases. As such, the performance of MESS+ is not affected by individual failures and rare edge cases. \n\n**Limitations)** We explicitly mention user satisfaction feedback as an avenue for future work to explore partial or delayed signals. This will also address scalability challenges and performance aspects of exploration but is beyond the scope of our work.\nMESS+ adapts to user preferences through online feedback collected via standard consent-based inference endpoints and voluntary feedback mechanisms. However, learning from a data distribution typically carries some bias and fairness challenges, such as favoring frequent users over infrequent ones. We will clarify these potential bias sources in our updated paper.\nDeployment risks go beyond the scope of our work."}]

Author rebuttal:

Meta-review: **Paper summary**
The paper presents MESS+, a framework to select an appropriate LLM to call for each given input query. MESS+’s formulation, like many existing model routing works, seeks to minimize the average cost, subject to a constraint on the average quality (applied to Service Level Guarantee, or SLA in this work). What makes MESS+ unique is that it (Algorithm 1) allows learning to be done entirely in an online fashion, through stochastic optimization. 

**Reviews**
Overall, the paper received positive feedback. The reviewers noted the novelty of MESS+ [9ALn] with strong theoretical guarantees [Cuig, tW9L, 9ALn] and strong empirical results [tW9LV]. Sticky points mentioned by multiple reviewers are:

1. [Cuig, tW9L, 9ALn] Impractical feedback assumption. Specifically, MESS+ requires online feedback on user satisfaction for all models in the zoo to train its predictor. 

2. [Cuig, 9ALn] Limited model diversity. Model sizes are too separate (i.e., 1B, 8B, 70B) and so are easy to route to. Also, in experiments, MESS+ is tested on only three models from the same family.

3. [Cuig, tW9L] Potentially unfair comparison to baselines. Specifically, baselines do not have SLA guarantees like MESS+ does.

The authors submitted a strong rebuttal that sufficiently addressed the above concerns 2) and 3), convincing some reviewers to adjust ratings more positively in the process. In the AC’s view, concern 1) is already explicitly mentioned as a limitation (in the conclusion section). Also, existing model routing works tend to consider the “batch/offline” setting where one trains a routing model on an offline training set. Each example in the training set consists of an input query, and ground-truth correctness labels from all LLMs in the pool (or at least pair-wise comparison labels from a selected subset of LLMs). So, in terms of the assumption on feedback, existing works also require the same assumption. Thus, concern 1) above is not specific to the present work. A key distinguishing feature of this work is that the proposed MESS+ can learn to route queries in an online fashion. This is one of the few works that considers this online setting.
Decision: Accept (poster)