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

cs.LGMar 25, 2026

Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

Authors: Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu, Zhengze Zhou, Zhipeng Wang, Rahul Mazumder

Organizations: LinkedIn · MIT

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.

Figures & tables

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.

Figure 2. Comparison of cost inference of each batch for per-query routing ( 1 ), for different values of

\lambda

. Routing is performed using MIRT, with batches are constructed either randomly to yield approximately uniform difficulty (left) or adversarially to create difficult and easy batches (right).

Panel of Figure 3 — Figure 3. Average test set performance as a function of log total cost under per-query optimization for the two datasets. Each curve corresponds to a different performance estimator and shows the trade-off across varying $\lambda$ parameter. The robust estimators are calculated based on 10% quantile ( $Q=10$ ). We also include individual LLMs in the plots; these points correspond to benchmark-reported performance and cost values used as baselines in the simulation. For plot readability, we restrict these to models whose average test performance exceeds 70% on Dataset 1 and 60% on Dataset 2.

Table 1. Comparison of prediction interval (PI) lengths for the LLMs selected by the main (non-robust) method versus the PI lengths of the LLMs selected by its robust version, shown as percentages of all queries.

<

Rob. PI: percentage of queries where the non-robust PI is shorter than the robust PI;

=

Rob. PI: percentage where they are equal;

>

Rob. PI: percentage where the non-robust PI is longer than the robust PI.

Panel of Figure 4 — Figure 4. Average test performance versus maximal batch-level average per-query cost across batches, comparing per-query optimization and batch-level optimization for both datasets. Results are shown for randomly constructed batches (left) and adversarial batches (right).

Panel of Figure 5 — Figure 5. Average test performance versus GPU budget, comparing data-dependent (optimized) allocation with fixed (pre-specified) numbers of open-source model instances. Colors indicate different bounds on the average cost per query $C$ .

Panel of Figure 6 — Figure 6. Average test performance as a function of the GPU budget for different LLM performance estimation methods after full optimization under cost and resource constraints on Dataset 1. We report results for both low-cost (top) and high-cost (bottom) scenarios. We also include individual LLMs with test performance above 70%; these points correspond to benchmark-reported performance and cost values used as baselines in the simulation. Open-source models require non-zero GPU resources, while closed-source models incur no GPU requirements as per our simulation setup.

Panel of Figure 7 — Figure 7. Full optimization results on Dataset 2; see the caption of Figure 6 for a detailed description.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

LLM	Input $/1M tokens	Output $/1M tokens
DeepSeek-Chat	0.14	0.28
DeepSeek-Coder	0.14	0.28
Gemini-1.5-Flash	0.075	0.30
GLM-4-Air	0.137	0.137
GLM-4-Flash	0.0137	0.0137
GLM-4-Plus	6.85	6.85

Appendix

Table 2. Dataset 1: Pricing of LLMs in USD per million tokens taken directly from Song et al. (2025) .

LLM	Average Cost Per Query
WizardLM-13B-V1.2	0.0001417
Claude-Instant-V1	0.0012362
Claude-V1	0.0058702
Claude-V2	0.0061528
GPT-3.5-Turbo-1106	0.0007086
GPT-4-1106-Preview	0.0079425

Appendix

Table 3. Dataset 2: Average cost per query for each model, with the individual costs for each query-LLM pair taken directly from Hu et al. (2024) .

LLM	Profile / Description
gpt-3.5-turbo-1106	Released by OpenAI in November 2023, GPT-3.5-turbo-1106 is a proprietary chat-optimized large language model in the GPT-3.5 family, designed for efficient conversational and general text generation tasks. It supports function calling and improved JSON-structured outputs, and is trained on a mixture of licensed data, human-created data, and publicly available text.
claude-instant-v1	Released by Anthropic in 2023, Claude-Instant-v1 is a proprietary lightweight conversational language model designed for low-latency and cost-efficient deployments. It emphasizes fast response times, summarization, document analysis, and general dialogue capabilities, while maintaining Anthropic’s “helpful, honest, and harmless” alignment philosophy.
claude-v1	Introduced by Anthropic in March 2023, Claude-v1 is a proprietary large language model designed for conversational AI, reasoning, summarization, and instruction following. It was among the first models trained using Anthropic’s constitutional AI framework, prioritizing safety and controllability.
claude-v2	Released by Anthropic in mid-2023, Claude-v2 improves upon Claude-v1 with stronger reasoning, coding ability, and longer context handling. It supports larger context windows and delivers improved performance on math, logic, and complex instruction-following tasks.
gpt-4-1106-preview	Released by OpenAI in November 2023, GPT-4-1106-preview is a proprietary preview model from the GPT-4 Turbo family, optimized for faster inference and lower cost while retaining GPT-4-level reasoning. It supports function calling and improved JSON output reliability.
llama-2-70b-chat	Released by Meta AI in 2023, LLaMA-2-70B-Chat is an open-weights 70B-parameter model fine-tuned for dialogue using supervised fine-tuning and reinforcement learning from human feedback. It is widely adopted due to open licensing and competitive performance.

Appendix

Table 4. Dataset 2: Profiles of the language models used in experiments.

Panel of Figure 8 — Figure 8. Performance versus cost of robust versions of kNN-5, kNN-40 and XGBoost under per-query optimization across different quantile levels $Q\in\{5,10,20,30\}$ .

Panel of Figure 9 — Figure 9. Average test performance vs. maximum batch-level average per-query cost across batches, comparing per-query optimization with batch-level optimization. Results are reported for Dataset 1 using robust XGBoost Q10 as the performance estimator, under randomly constructed batches (left) and adversarial batches (right).

Panel of Figure 10 — Figure 10. Average test performance vs. maximum batch-level average per-query cost across batches, comparing per-query optimization with batch-level optimization. Results are reported for Dataset 2 using robust XGBoost $Q=10$ as the performance estimator, under randomly constructed batches (left) and adversarial batches (right).

Table 5. Pricing and GPU requirements of LLMs across both datasets for the experimental deployment setup.

Panel of Figure 11 — Figure 11. Performance as a function of the GPU budget for optimized and fixed model instances, shown for varying batch sizes and cost budgets.

Panel of Figure 12 — Figure 12. Performance as a function of the GPU budget for optimized and fixed model instances, shown for varying batch sizes and cost budgets.

Panel of Figure 13 — Figure 13. Full optimization results for Dataset 1 under varying batch sizes and cost budgets.

Panel of Figure 14 — Figure 14. Full optimization results for Dataset 2 under varying batch sizes and cost budgets.

LLM Routing

Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.

See all 349 papers

WISERouter: LLM Routing with Workload Budget Constraint
Jul 26, 2026Yifei Li, Zihui Gao, Laks V. S. LakshmananLLM Routing Contextual Bandits
The University of British Columbia
Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools
May 13, 2026Shivam Patel, Akaash R. Parthasarathy, Akash Dhasade +2LLM Serving LLM Routing
Carnegie Mellon University · Microsoft
RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models
Feb 20, 2026Sai Hao, Hao Zeng, Hongxin Wei +1Set-Valued Prediction LLM Routing
Southern University of Science and Technology, China · The Chinese University of Hong Kong, Shenzhen, China · Shenzhen Loop Area Institute, China

Jul 26, 2026J/K move · Enter open · S save

WISERouter: LLM Routing with Workload Budget Constraint

Yifei Li, Zihui Gao, Laks V. S. Lakshmanan

The University of British Columbia

LLM Routing Contextual Bandits

Open paper AskPDF arXiv

Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of

O(\sqrt{T})

over a time horizon

T

. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.

Abstract

LLM Routing

Explore similar work

WISERouter: LLM Routing with Workload Budget Constraint

Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools

RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models