Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints
Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu, Zhengze Zhou, Zhipeng Wang, Rahul Mazumder · 2026
Read Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints by Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu, Zhengze Zhou, Zhipeng Wang, Rahul Mazumder (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26796.txt.
Introduction
Markovic-Voronov and co-authors route language model queries batch by batch under cost and hardware limits. Per-query routing can lose control of total spend when batches arrive in skewed mixes. Their framework assigns each batch jointly, respecting price caps and each model's capacity. A robust variant hedges against errors in predicted model quality. An offline step also spreads running copies across models for balance. On two multi-task benchmarks, robust routing lifts accuracy by 1 to 14%, and batch routing beats per-query picks by up to 24%.
Catalog record
| CREATOR | Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu, Zhengze Zhou, Zhipeng Wang, Rahul Mazumder |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54957 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26796
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu, Zhengze Zhou, Zhipeng Wang, Rahul Mazumder Abstract . We study the problem of routing queries to large language models (LLMs) under cost, GPU resources, and concurrency constraints. Prior per-query routing methods often fail to control batch-level cost, especially under non-uniform or adversarial batching. To address this, we propose a batch-level, resource-aware routing framework that jointly optimizes model assignment for each batch while respecting cost and model capacity limits. We further introduce a robust variant that accounts for uncertainty in predicted LLM performance, along with an offline instance allocation procedure that balances quality and throughput across multiple models. Experiments on two multi-task LLM benchmarks show that robustness improves accuracy by 1–14% over non-robust counterparts (depending on the performance estimator), batch-level routing outperforms per-query methods by up to 24% under adversarial batching, and optimized instance allocation yields additional gains of up to 3% compared to a non-optimized allocation, all while strictly controlling cost and GPU resource constraints. 1. Introduction Large Language Models (LLMs, ( 7 ; 1 ; 16 ) ) have become a central component of modern machine learning systems. Their strong performance is driven in part by substantial computational resources, particularly at inference time. However, allocating more inference resources does not always yield significantly better outputs, especially for simple queries ( 4 ) . This observation has motivated LLM routing ( 6 ; 12 ; 20 ; 26 ) , which aims to balance response quality and computational cost by routing easy queries to cheaper models and hard queries to more capable ones. LLM routing has become a major component of industrial agentic applications ( 18 ; 21 ; 27 ) . Most existing routing methods operate on a per-query basis. Given a query q and a pool of M models m_{1},\ldots,m_{M} , per-query routing methods estimate a quality score of how well model m_{j} will work for query q , denoted as l(q,m_{j}) and the cost of responding to query q using model m_{j} , denoted by c(q,m_{j}) . Then, the routing is performed by solving (1) \max_{j\in[M]}\;l(q,m_{j})-\lambda\cdot c(q,m_{j}), where the hyperparameter \lambda\geq 0 controls the cost–quality tradeoff. Prior work largely focuses on improving the estimator l(q,m_{j}) using techniques such as neural networks, matrix factorization, k-nearest neighbors (kNN), or lightweight LLMs ( 19 ; 12 ; 20 ; 26 ; 9 ; 33 ) . In practice, however, LLM inference systems rely heavily on (dynamic) batching to improve hardware utilization, which inherently couples the cost, latency, and capacity usage of queries that arrive close in time ( 32 ; 14 ) . This exposes several limitations of per-query routing in ( 1 ). First, cost is only indirectly controlled through \lambda , making it difficult to enforce strict batch-level budget constraints. Second, per-query routing ignores batch-level effects: when multiple difficult queries arrive together, it may oversubscribe expensive or capacity-limited models, causing cost spikes or delays. Third, per-query routing does not account for heterogeneous serving setups, such as locally deployed models with limited capacity versus cloud-based models with higher cost but greater scalability ( 31 ; 22 ) . Such serving settings have become increasingly common in industrial applications; For example, Apple ( 10 ) adopted a two-model approach, with a smaller model served on-device and a larger model served in the cloud. Finally, performance estimates l(q,m_{j}) can be noisy at test time, leading to over- or under-confident routing decisions. We refer to Section 2.1 for an example demonstrating the shortcomings of per-query routing discussed here. Figure 1 . Batch-level LLM routing framework assigns an LLM to each query within a batch by solving a constrained optimization problem that maximizes average per-query performance. The formulation enforces both a global monetary cost budget on total inference cost and individual capacity constraints for each LLM. Each query is assigned to exactly one LLM, so among x_{i,1},\ldots,x_{i,M} only one equals 1 and the rest are 0. Since the true performance of an LLM on a new query is unknown at decision time, it must be estimated via a_{i,j} . To account for estimation uncertainty in a_{i,j} , the robust variant replaces the point performance estimates in the objective with the lower bounds \underline{a}_{i,j} of their corresponding prediction intervals, thereby optimizing for worst-case performance within the estimated uncertainty range. To address these issues, we propose a batch-level routing framework based on Integer Linear Programming (ILP, ( 29 ) ), as illustrated in Figure 1 . Our formulation is designed to maximize the average routing quality across queries while explicitly enforcing both cost and hardware capacity constraints, which are critical in practical deployment scenarios. To account for uncertainty in the estimated performance l(q,m_{j}) of model m_{j} on query q , we introduce a robust optimization ( 2 ) variant that ensures strong performance even under worst-case estimation errors. Importantly, the framework is model-agnostic and compatible with standard performance estimators such as XGBoost or k-nearest neighbors, and we demonstrate that the resulting ILPs can be solved efficiently using existing off-the-shelf solvers, enabling practical deployment for large-scale query batches. Beyond inference-time routing, we further investigate optimal allocation of on-premise computational resources (e.g., GPUs) to available models prior to inference. This pre-deployment decision involves balancing accuracy and capacity across multiple models, ensuring that the system can handle incoming query batches without exceeding resource constraints. Unlike prior work on LLM routing, which typically assumes unlimited capacity or focuses solely on per-query performance, our framework explicitly integrates deployment planning, bridging the gap between offline resource allocation and online batch-level routing to achieve both efficient and high-quality inference. Contributions We summarize the key contributions of this work as follows: (i) We identify fundamental shortcomings of existing per-query LLM routing, particularly under batched inference and strict cost or capacity constraints. (ii) We introduce a robust batch-level routing framework that explicitly enforces cost and hardware constraints while accounting for uncertainty in performance estimates. (iii) We study the optimal allocation of local computational resources to models prior to inference. (iv) Extensive experiments on two multi-task LLM benchmarks show that our approach achieves more stable and higher routing accuracy than per-query methods while satisfying all constraints. Specifically, robustness improves accuracy by 1–14% over non-robust counterparts, batch-level routing outperforms per-query methods by up to 24% under adversarial batching, and optimized model instance allocation yields gains of up to 3% compared to non-optimized model allocation, all while strictly controlling cost and GPU resources. 1.1. Related Work Most existing LLM routing methods follow a two-stage framework in which they first estimate the performance of each LLM on a given query and then optimize a per-query objective, as in ( 1 ), to balance expected performance against cost. The primary distinction across prior work therefore lies in how LLM performance is modeled. For example, RouterBench ( 12 ) estimates per-query performance using either k-nearest neighbors or a multilayer perceptron (MLP), with a separate model trained for each LLM. UniRoute ( 13 ) extends this approach by incorporating k-means clustering to enhance generalization to previously unseen LLMs. IRT-Router ( 26 ) employs a lightweight neural network that jointly encodes query features and LLM profile embeddings to produce performance estimates. GraphRouter (