MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees

Thank you for your thorough review! We will first address your questions based on their impact and then reply to the weaknesses.

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.

Part 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. We 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.

Table I: Mixed zoo with Llama 3 and Qwen 2 models.

Part 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.

Part C: We conducted additional experiments on a different, larger model zoo using the Qwen 2 model family (0.5B, 1.5B, 7B, 32B). Our 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. MESS+ 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.

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+.

Part 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. We will include these additional results in our updated paper.

Table II: Experiments on the Qwen 2 model zoo with a 2x squeezed cost ratio around the average inference cost per request

Part 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. We 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.

Table III: Exploration vs. Exploitation cost in the Qwen 2 model zoo

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. The 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.

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.

Part 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. We 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.

Part 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.

Part 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.

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.

Part 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.

Part 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.

Part C: The experimental results on the tradeoff between exploration and exploitation have been presented and discussed in our response to Q3 above. Theoretically, $\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. For 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.

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. We 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.

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. MESS+ 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. Deployment risks go beyond the scope of our work.

Thank you for your detailed review of our manuscript and your positive feedback! In the following, we will first address the weaknesses (in the original numbering in the review) and then your questions.

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.

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.

Table I: Additional experiments on a larger zoo with 4 Qwen 2 models - Avg. across 8 benchmarks ($\alpha = 0.67$)

W9) MESS+ only works when using both the predictor and the online optimization together. Without 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.

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. We 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%). Due 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. Nonetheless, 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. We 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%). Due 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. Nonetheless, MESS+ still satisfies our SLA requirement and outperforms our Educated Guessing baseline. We will include these insights in our updated paper.

Table II: Additional experiments with non-IID requests - 3 benchmarks concatenated (ARC Challenge, PiQA, Winogrande)($\alpha = 0.67$)

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.

Q3) We will make use of the extra page for a potential camera ready version to improve the readability of Table 2.

Q4) We are happy to change the title to “inference-time”.

Thank you for your positive feedback and the thorough review of our paper! We will first address the weaknesses and then your questions.

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. In 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. As 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.

Table I: Additional results when receiving sparse user feedback - Mean over 8 benchmarks ($\alpha=0.67$, 20% user participation)

Q1) Binary feedback is the most challenging data to learn from as signals are very coarse. When 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. However, 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.

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. Additional experimental results exploring different $\alpha$ values can be found in the supplementary material (Figures C.2 and C.3).

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. Even 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. This 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. When 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).

Thank you for your thorough review of our paper and the positive feedback! We first respond to the weaknesses and then to your questions. We combine answers where appropriate.

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.

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. Even 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. This 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. When 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).

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). Below, 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.

Table I: Additional experiments on a larger zoo with 4 Qwen 2 models - Avg. across 8 benchmarks ($\alpha = 0.67$)

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.

The 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.

We will make this selection process more clear in our updated paper.

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.