WISERouter: LLM Routing with Workload Budget Constraint

As organizations scale their use of Large Language Models (LLMs), they face a critical trade-off: using the most capable models for every query is prohibitively expensive, while smaller models may lack the necessary performance for complex tasks. Existing routing methods often fail to enforce global, workload-level budget constraints (e.g., a monthly API quota) or require expensive, dense supervision to train routing policies. This paper asks: how can we perform efficient LLM routing that respects a global budget while learning from sparse, real-time interactions?

The authors formulate LLM routing as a Constrained Contextual Multi-Armed Bandit (CCB) problem. They introduce WISERouter (WR), which uses Adaptive Linear Programming (ALP) to translate a global budget into dynamic per-query constraints.

• WR-Offline: For data-rich environments, it uses historical interaction data to estimate reward and cost statistics, then solves an LP to determine optimal routing probabilities.
• WR-Online: For data-scarce environments, it employs an epsilon-first exploration strategy to learn reward and cost statistics online, proving a sublinear regret bound of O(sqrt(T)) for the entire process.

To bridge the gap between continuous query embeddings and the discrete requirements of ALP, the authors use clustering to group queries into a finite set of contexts, allowing the router to make decisions based on the expected performance and cost of each model within that cluster.

Empirical evaluations on RouterBench and SWE-Bench show that WISERouter consistently outperforms existing baselines. In data-rich scenarios, WR-Offline improves average response quality by 14% over the best baseline on SWE-Bench under tight budget constraints. In data-scarce scenarios, WR-Online achieves performance comparable to offline methods while requiring 90% less exploration data. The framework is also significantly faster to train than neural-network-based routing approaches, as it avoids complex model retraining when budget constraints change.