Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving

Q1: The experiments mainly use the pre-existing ground truth and lack of robustness evaluation against noisy quality labels.

A: Thank you for your comments. To demonstrate the robustness of our algorithm under noisy historical labels, we conduct experiments in a noisy setting where two types of strong noise are introduced simultaneously. Specifically, for each performance label $d_{ij}$, we randomly flip its value with a probability of 20%. For each cost label $g_{ij}$, we apply multiplicative, mean-preserving noise consisting of two components: (i) log‑normal jitter $\left(\log \mathcal{N}(0, \sigma^2) - \frac{1}{2} \sigma^2\right)$ with $\sigma = 0.25$, and (ii) a spike factor of 3.0 applied with probability 2%.

We compare our algorithm against all baseline methods on RouterBench under the main experimental setting. As shown in the results below, our method consistently outperforms all baselines under noisy historical labels. It achieves the highest overall performance, the highest throughput, and the best cost efficiency, demonstrating the strong robustness of our algorithm under noisy conditions.

Table 1. Routing performance under noisy historical data. Comparison between our algorithm and baselines on RouterBench.

Q2: The baseline methods are somewhat weak.

A: Thank you for your suggestions. To the best of our knowledge, our work is the first to focus specifically on training-free online multi-LLM routing, and there are currently no existing methods that directly target the same setting. To provide further meaningful comparisons, we additionally include and adapt three local routing baselines adapted from two related works: RouteLLM (MF) and RouteLLM (BERT) from [1], and CARROT (RoBERTa) from [2]. Literature [1] is a well-known two-model routing approach, while [2] represents the current state-of-the-art in offline multi-LLM routing, with the goal of balancing cost and performance. Since [1] only handles two-model routing, we extend it to the multi-model case by training multi-label predictors for win rates and applying a cheapest feasible model strategy: routing to the cheapest model whose predicted win rate logit exceeds a threshold $\alpha$. Furthermore, as all three baselines are originally intended for local or offline routing, we adapt them to our online setting. We use $20\%$ historical data to search the threshold $\alpha$ (for RouteLLM) and the cost-efficiency coefficient $\mu$ (for CARROT) over the range [0, 1] with step size of 0.1 to maximize performance under a fixed budget.

We present comparisons on the most representative benchmark, RouterBench, under the main experimental setting. Our algorithm outperforms all three additional baselines across all key metrics while maintaining the lowest routing latency. Notably, it achieves over 1.5$\times$ higher throughput than all baselines and a routing latency of just 0.64 seconds, which is over 200× faster than the state-of-the-art CARROT method:

Table 2. Comparison results with 3 additional baselines on RouterBench

Q3: The theoretical proof relies on strong assumptions including the existence of at least one close neighbor in the log and that generation quality and cost are smoothly tied to prompt embeddings. The evaluation is mainly conducted with an in-distribution setting, and it is unclear if the proposed method is robust enough to handle the out-of-distribution challenge and drifting query patterns in dynamic online settings.

A: Thank you for your comments. We believe there may be a misunderstanding, and we would like to clarify that the assumptions we make, which are discussed in detail in Appendix B.1, are all natural and mild. In particular, Assumption 1 is grounded in the core idea of informative query routing: we assume that there exist historical data points that are informative for routing future queries. This aligns with the core intuition behind nearly all prior predictive LLM routing methods [1, 2, 3, 4], which assume that some queries in the training or historical data share similar routing-relevant features with future queries. If no such informative historical data exists, then leveraging training/historical data for predictive routing becomes impossible, and all previous methods, whether training language models or low-rank models on the historical data, would reduce to random routing, as discussed in Appendix B.1. In such a case, no meaningful inference can be made without directly querying the LLMs. One must query all LLMs to make informed routing decisions. This is because, in the worst case, under an adversary query targeting the LLM query order in the system, all LLMs may present extremely low performance, except the last LLM. This underscores the importance of Assumption 1, which connects historical data to future queries, enabling meaningful routing and improved performance.

To evaluate the robustness of our algorithm, we construct a challenging out-of-distribution setting using RouterBench, which consists of 13 distinct datasets with substantially different distributions (see Table 2 in the Appendix). We use a single dataset (MMLU) in RouterBench as historical data and treat the remaining 12 datasets (including Chinese, GSM8K, and so on) as the test set. We compare our algorithm against all baselines under the main setting in both the OOD and noisy settings. The detailed results are as follows:

Table 3. Routing performance in the out-of-distribution setting: Comparison between our algorithm and baselines on RouterBench

As shown in the Table, even under this challenging OOD setting, our algorithm consistently outperforms all baselines. It achieves the highest overall performance, the best performance-per-cost ratio, and the greatest throughput. These results highlight the strong robustness of our method to distribution shift and changing query patterns.

Q4: What is the query-level latency? How does it compare to other routing strategies including trained lightweight routers?

A: Thank you for raising this point. We provide a detailed comparison of query-level routing latency on RouterBench under varying numbers of test queries. All implementations are in Python, and each method is executed using a single CPU thread. For model-based methods that require GPU computation, we follow the same setup as in [1] and use a single NVIDIA L4 GPU (24GB). Across all methods, we fix the processing batch size to 256 for consistency. The detailed latency results are summarized below, where our method achieves the fastest routing among all baselines (except the random routing strategy, which exhibits significantly poorer performance).

Table 4. Per-query routing latency (ms) of different algorithms on RouterBench under varying numbers of queries

These results clearly demonstrate that our algorithm consistently achieves the lowest per-query routing latency across all settings, significantly outperforming all baselines. Notably, compared to model-based routers, our method achieves over 200$\times$ speed-up. Note that our current implementation, which is written in Python and runs on a single CPU thread, can be further optimized. Since it requires no GPU operations and handles queries independently, it can be easily reimplemented in a lower-level language such as C++ and parallelized to achieve even greater speed-ups in practice.

[1] Ong, Isaac, et al. "Routellm: Learning to route llms with preference data." arXiv preprint arXiv:2406.18665 (2024).

[2] Somerstep, Seamus, et al. "Carrot: A cost aware rate optimal router." arXiv preprint arXiv:2502.03261 (2025).

[3] Hu, Qitian Jason, et al. "Routerbench: A benchmark for multi-llm routing system." arXiv preprint arXiv:2403.12031 (2024).

[4] Wang, Xinyuan, et al. "Mixllm: Dynamic routing in mixed large language models." arXiv preprint arXiv:2502.18482 (2025).

Q1: While the paper claims low-latency routing, it doesn’t provide absolute latency measurements (e.g., milliseconds per query) or breakdowns.

A: Thank you for raising this point. We provide a detailed comparison of per-query routing latency on RouterBench under varying numbers of test queries. All methods are implemented in Python and executed using a single CPU thread. For model-based approaches requiring GPU computation, we follow the same setup as in [1], using a single NVIDIA L4 GPU (24GB). To ensure consistency, we fix the processing batch size to 256 across all methods. The latency results are summarized below, showing that our method achieves the fastest routing among all baselines (except the random routing strategy, which exhibits significantly poorer performance).

Table 1. Per-query routing latency (ms) of different algorithms on RouterBench under varying numbers of queries

These results clearly demonstrate that our algorithm consistently achieves the lowest per-query routing latency across all settings, significantly outperforming all baselines. Notably, compared to model-based routers, our method achieves over 200$\times$ speed-up, highlighting its strong routing efficiency. Furthermore, our current implementation, which is written in Python and executed on a single CPU thread, can be further optimized. Since the algorithm requires no GPU operations, it can be easily reimplemented in a lower-level language such as C++ for further improvement. Additionally, because routing decisions for individual queries are made independently, the algorithm is inherently parallelizable and well-suited for multi-threaded execution. These optimizations can lead to substantial additional speed-ups in real-world deployments.

Q2: How sensitive is the routing performance to the quality and size of the historical dataset?

A: Thanks for your comments. We have already included detailed experiments on the impact of historical data size on routing performance in Appendix C.5 (see Figure 11). The results show that varying the amount of historical data has a negligible effect on our algorithm’s performance. Across all data sizes and settings, our method consistently and significantly outperforms all baselines, demonstrating strong robustness. Notably, even with as few as 5,000 historical records, our algorithm remains highly effective for routing. To assess sensitivity to data quality, we consider two challenging settings: noisy labels and out-of-distribution (OOD) historical data.

In the noisy setting, we introduce two types of strong noise simultaneously. For each performance label $d_{ij}$, we randomly flip its value with a probability of 20%. For each cost label $g_{ij}$, we apply multiplicative, mean-preserving noise consisting of: (i) log-normal jitter $\left(\log \mathcal{N}(0, \sigma^2) - \frac{1}{2}\sigma^2\right)$ with $\sigma = 0.25$, and (ii) a spike factor of 3.0 applied with 2% probability.

In the OOD setting, we construct a distribution shift using RouterBench, which contains 13 diverse datasets (see Table 2 in the Appendix). We use MMLU as the historical dataset and evaluate on the remaining 12 datasets, which differ significantly in data distribution. In both settings, our algorithm consistently outperforms all baselines under the main evaluation protocol. The detailed results are as follows:

Table 2. Routing performance under noisy historical data: our algorithm v.s. baselines on RouterBench

Table 3. Routing performance in the out-of-distribution setting: Comparison between our algorithm and baselines on RouterBench

As shown in the above tables, our algorithm consistently outperforms all baselines under both noisy historical labels and out-of-distribution settings. In both cases, it achieves the highest overall performance, best performance-per-cost ratio, and greatest throughput, demonstrating strong robustness to label noise and varying distribution shift.

Q3: How often should γ∗ be re-learned in a real system?

A: Thank you for the question. In our approach, the routing weights $\gamma^\star$ are learned based on the number of upcoming queries to be routed and the chosen fraction ratio $\epsilon$. For example, with $\epsilon = 0.025$ and a total query batch of 10000, only 250 initial queries are needed to learn the routing weights $\gamma^\star$. In practice, incoming queries can be divided into sequential chunks (e.g., of size 10000), and $\gamma^\star$ is relearned for each chunk. Specifically, after finishing routing one chunk, we relearn $\gamma^\star$ for the next chunk. The overhead of this learning process is negligible, where it takes approximately 0.03s on 250 samples and 0.05s on 500 samples, and can be further improved. This means that, even in high-throughput scenarios (e.g., 10000 queries per second), this routing weight optimization only adds negligible overhead (0.03s), making the relearning process both efficient and practical for real systems.

Q4: Could reinforcement learning improve the second-stage routing?

A: Thanks for your suggestion. Using reinforcement learning (RL) for improving the second-stage routing is indeed an interesting direction. In our current design, we learn the routing weights efficiently via a one-shot optimization of the dual LP, which is highly efficient and requires no costly online training process. While RL could offer benefits such as continual adaptation to changing query patterns and integration of richer feedback signals, it also introduces extra complexity and exploration overhead. We consider RL-based routing a promising avenue for future work.

Q5: Can the proposed method be applied for VLM (vision language model)?

A: Thanks for the question. Our routing framework is largely modality‑agnostic and only requires that the processed queries can be mapped into a vector space (embedding). In a VLM scenario, one can first encode each image (and its accompanying text, if any) into a joint embedding (e.g., via CLIP or another vision–language encoder). With this joint embedding, our algorithm can be naturally extended to the VLM setting by applying the same procedure: using ANNS to retrieve informative historical data points and performing online cost-efficient routing accordingly. We view this extension as an exciting future direction.

[1] Ong, Isaac, et al. "Routellm: Learning to route llms with preference data." arXiv preprint arXiv:2406.18665 (2024).

Q1: Such approximate nearest neighbor methods highly rely on the training data. E.g. Routerbench has 36,497 examples. The paper uses 26,497 queries as historical data to construct the search examples and 10,000 queries for testing.

A: Thanks for the comments. We would like to clarify that our algorithm does not rely heavily on historical data. As we already showed in Appendix C.5 (Figure 11), varying the amount of historical data used for ANNS has minimal impact on performance. Our method consistently and significantly outperforms all baselines across all data sizes, demonstrating strong robustness. Notably, even with as few as 5000 historical records, our algorithm remains highly effective for routing.

Q2: Stronger model-based methods like BERT can be added.

A: We appreciate the suggestion. Following the main setting in the paper, we train two separate BERT-based models to predict the generation performance score and cost for each query, resulting in two additional BERT-based routing baselines: (i) BERT-perf-routing, which routes each query to the model with the highest predicted performance; (ii) BERT-cost-routing, which routes each query to the model with the greatest available budget. We compare our algorithm with these two baselines on RouterBench under the main experimental setting. The detailed results are as follows:

Table 1. Comparison of Our Routing Algorithm with BERT‑Based Methods on RouterBench

As shown in the above results, our method achieves >4$\times$ higher Performance and >3$\times$ higher Throughput than the strongest BERT‑based baseline, while maintaining favorable cost efficiency.

Q3: The router running time of these methods can also be compared.

A: Thank you for raising this point. We provide a detailed comparison of routing latency on RouterBench under varying numbers of test queries. All implementations are in Python, and each method is executed using a single CPU thread. For model-based methods that require GPU computation, we follow the same setup as in [1] and use a single NVIDIA L4 GPU (24GB). Across all methods, we fix the processing batch size to 256 for consistency. The detailed latency results are summarized below, demonstrating the routing efficiency of our algorithm: our method achieves the fastest routing among all baselines (except the random routing strategy, which exhibits significantly poorer performance):

Table 2. Total routing latency (s) comparison of routing algorithms on RouterBench under varying numbers of queries

These results clearly show that our algorithm consistently achieves the lowest routing latency across all settings, outperforming all baseline methods. This demonstrates the strong routing efficiency of our approach. Furthermore, we note that our current implementation of our algorithm, which is written in Python and runs on a single CPU thread, can be further optimized. Since the algorithm does not require any GPU resources or operations, it can be easily reimplemented in a faster programming language such as C++ for better performance. In addition, because routing decisions for individual queries are made independently based on learned routing weights, the algorithm is naturally parallelizable and well-suited for multi-threaded execution. Applying these optimizations can further provide substantial speed-ups in practice.

Q4: Experiments are only on simulated traces.

A: Thank you for your comment. To the best of our knowledge, we have evaluated our method on almost all publicly available multi-LLM routing benchmarks [2, 3, 4] that are widely used in the literature and research community. We are not aware of any additional public datasets in this space. If the reviewer has any pointers to specific labeled traffic traces, we would be happy to incorporate them into further experiments.

Q5: Move Table 1 to the next page

A: Thank you for the suggestion. We will move Table 1 to an appropriate position on the next page in the revised version.

[1] Ong, Isaac, et al. "Routellm: Learning to route llms with preference data." arXiv preprint arXiv:2406.18665 (2024).

[2] Hu, Qitian Jason, et al. "Routerbench: A benchmark for multi-llm routing system." arXiv preprint arXiv:2403.12031 (2024).

[3] Open llm leaderboard v2. https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard, 2024.

[4] Somerstep, Seamus, et al. "Carrot: A cost aware rate optimal router." arXiv preprint arXiv:2502.03261 (2025).

Q: Instead of BERT, if training on bge-base model, such a method can have the same latency as the proposed method?

A: Thank you for the question. If we fine-tune the same bge model used for embedding as a router, the overall latency would indeed be similar to our method. However, the performance would be much worse since our method is already improving over Bert based routers. In fact, imagine an extreme case where we make random decisions. Then our latency is effectively 0 but the performance is reduced significantly (see our Table 1 in the submission).

Furthermore, as discussed above, any model-based routers still face several key limitations in online settings (even if we imagine using a hypothetical model that has 0 latency but somehow magical performance):

(1) Lack of adaptability. Model-based routers must be retrained whenever the model pool or budget constraints change, which makes them hard to maintain in dynamic deployment environments.

(2) Limited cost-efficiency. Such routers often optimize for a fixed objective (performance or cost) and struggle to adapt to dynamic query arrivals.

(3) No modular reuse. The model-based router is tightly coupled with the router and cannot be reused for other tasks. In contrast, our embedding module is decoupled, allowing the same embeddings to be shared across routing, retrieval, logging, and other downstream tasks.

Thanks again for your comments, and we hope this clarifies the practical advantages of our training-free approach.

Q1: The method only considers cost and efficiency as features for model selection but does not consider traffics of the queries. In a real-world setting, the traffic of queries is also important.

A: Thank you for your comments. We acknowledge that query traffic patterns play an important role in real-world systems. However, the primary goal of our work is to develop a cost-efficient online routing algorithm, a problem that has gained increasing attention in recent literature [1, 2, 3], especially given the high computational cost of LLMs. To isolate this core algorithmic problem, we adopt a standard assumption widely used in the online algorithms literature [4, 5, 6]: that incoming queries arrive in a randomly permuted order. This assumption, also discussed in detail in Appendix B.1, allows us to abstract away complex traffic dynamics and focus on the fundamental cost-efficiency routing problem.

We would like to clarify that, under this assumption, our framework is designed to operate on query-intrinsic features that are independent of time and query order, such as response performance score and cost per query across the models. In contrast, operational-state features, such as current queue lengths or system load, are beyond the scope of our current formulation and are more aligned with a related but orthogonal problem: load balancing under traffic constraints.

Still, we believe our algorithm offers a natural foundation for incorporating such traffic-aware considerations. One potential approach is to discretize time into short windows and track the per-model backlog of unserved workload. Within each time window, a corresponding "time-bucket" MILP can be solved with additional traffic constraints, and any unserved workload can be carried over to the next window. For instance, let $\ell_{ij}$ denote the service time of query $j$ on LLM $i$, $b_{it}$ be the backlog of unserved workload for LLM $i$ at the start of time window $t$, and $A_{it}$ denote the available service capacity for LLM $i$ during window $t$. Then, for each window $t$ and LLM $i$, we can add the following constraint to the MILP: $\sum_j \ell_{ij} x_{ij} \leq \max \\{ 0, A_{it} - b_{it} \\}, \quad \forall i,t$ This "time-bucket" formulation helps smooth bursts and reduce queuing delays.

In the revision, we will further explicitly clarify the scope of our current MILP formulation and also discuss such possible extensions of our algorithm.

Q2: What parameters have you set for HNSW? The number of layers of HNSW is not specified. The parameters of HNSW might impact the evaluation results. Could you add evaluations for that?

A: Thank you for pointing this out. We use the standard and recommended HNSW implementation from hnswlib with the following parameter settings in our paper: construction effort factor ef_construction=200, max number of neighbors per node M = 32, and query search breadth ef = 50. Regarding the number of layers in hnswlib, it is not a direct user-configurable hyperparameter. Instead, it is an emergent property of the graph determined during construction, which is primarily controlled by the M parameter. A smaller M tends to produce a taller, multi-layered graph, while a larger M results in a flatter, more interconnected one.

To evaluate the robustness of our algorithm to these three key parameters, we conduct ablation studies on RouterBench under the main evaluation setting. Specifically, we vary ef_construction from 100 to 900, M from 8 to 96, and ef from 32 to 384. The ablation results, shown in the following tables, demonstrate that our routing algorithm remains highly robust across a wide range of values for all three parameters:

Table 1. Performance of our algorithm on RouterBench with varying ef_construction

Table 2. Performance of our algorithm on RouterBench with varying M

Table 3. Performance of our algorithm on RouterBench with varying ef

[1] Ong, Isaac, et al. "Routellm: Learning to route llms with preference data." arXiv preprint arXiv:2406.18665 (2024).

[2] Somerstep, Seamus, et al. "Carrot: A cost aware rate optimal router." arXiv preprint arXiv:2502.03261 (2025).

[3] Hu, Qitian Jason, et al. "Routerbench: A benchmark for multi-llm routing system." arXiv preprint arXiv:2403.12031 (2024).

[4] Devanur, Nikhil R., and Thomas P. Hayes. "The adwords problem: online keyword matching with budgeted bidders under random permutations." Proceedings of the 10th ACM conference on Electronic commerce. 2009.

[5] Mehta, Aranyak, et al. "Adwords and generalized online matching." Journal of the ACM (JACM) 54.5 (2007): 22-es.

[6] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982–991, 200