Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs

Wang Wei, Tiankai Yang, Hongjie Chen, Yue Zhao, Franck Dernoncourt, Ryan A. Rossi, Hoda Eldardiry

Abstract

Efficient use of large language models (LLMs) is critical for deployment at scale: without adaptive routing, systems either overpay for strong models or risk poor performance from weaker ones. Selecting the right LLM for each query is fundamentally an online decision problem: models differ in strengths, prices fluctuate, and users value accuracy and cost differently. Yet most routers are trained offline with labels for all candidate models, an assumption that breaks in deployment, where only the outcome of the chosen model is observed. We bridge this gap with BaRP, a Bandit-feedback Routing with Preferences approach that trains under the same partial-feedback restriction as deployment, while supporting preference-tunable inference: operators can dial the performance/cost trade-off at test time without retraining. Framed as a contextual bandit over prompt features and a user preference vector, our method simulates an online feedback setting during training and adapts its routing decisions to each new prompt, rather than depending on full-information offline supervision. Comprehensive experiments show that our method consistently outperforms strong offline routers by at least 12.46% and the largest LLM by at least 2.45%, and generalizes robustly for unseen tasks.

Introduction

Deploying large language models (LLMs) at scale is a complex balancing act. High-end models offer superior accuracy but come with significant costs, while smaller models are economical but prone to errors. An ideal routing system should dynamically select the most appropriate model for each prompt. However, existing routing solutions face two primary hurdles: the "feedback gap," where training relies on full-information labels unavailable in real-world deployment, and "static trade-offs," where cost-performance balances are fixed during training.

Methods: Bandit-feedback Routing with Preferences (BaRP)

We introduce BaRP, a framework that frames LLM routing as a multi-objective contextual bandit problem. Unlike traditional routers that require expensive labels for every candidate model, BaRP learns from the outcome of the chosen model alone (bandit feedback), mirroring actual deployment conditions.

The BaRP architecture: A query and preference vector are encoded and fed into a router, which selects an LLM and receives bandit feedback to update the policy.

The system architecture consists of several key components:

  • Contextual Input: The router processes the prompt's semantic embedding (via a frozen MiniLM) alongside a 2D user preference vector representing the relative weight of accuracy versus cost.
  • Policy Network: A small Multi-Layer Perceptron (MLP) outputs a probability distribution over available LLMs.
  • Optimization: The model is trained using the REINFORCE policy gradient algorithm, enhanced with entropy regularization to encourage exploration and a baseline for variance reduction.

Experimental Results

BaRP was evaluated using RouterBench logs across five in-distribution tasks and three out-of-distribution (OOD) tasks to test generalization capabilities.

Radar chart comparing BaRP against baselines across in-distribution and out-of-distribution tasks, highlighting its superior performance and generalization.

Superior Accuracy and Generalization

On in-distribution tasks, BaRP outperformed the best individual LLM by 3.81% and the best full-information offline routers by 12.46%. Notably, on OOD tasks, BaRP's performance advantage over offline routers grew to 25.99%. This suggests that training on partial bandit feedback acts as a natural regularizer, preventing the overfitting common in full-information supervision and making the model more robust to unseen tasks.

Preference-Tunable Inference

A core innovation of BaRP is its "control knob" effect. By conditioning the policy on a preference vector, operators can adjust the performance-cost trade-off at test time without retraining. This allows for immediate adaptation to changing budget constraints or quality requirements. Furthermore, BaRP's non-linear MLP architecture significantly outperformed linear bandit models, indicating that the relationship between prompt semantics and optimal model selection is highly complex.

Conclusion

BaRP bridges the gap between router training and real-world deployment. By learning from bandit feedback and supporting dynamic preference tuning, it provides a robust, efficient, and flexible solution for large-scale LLM orchestration. Future work will explore continuous learning from live user interactions and incorporating multi-turn conversational context into the routing logic.

Summary updated

Abstract

Efficient use of large language models (LLMs) is critical for deployment at scale: without adaptive routing, systems either overpay for strong models or risk poor performance from weaker ones. Selecting the right LLM for each query is fundamentally an online decision problem: models differ in strengths, prices fluctuate, and users value accuracy and cost differently. Yet most routers are trained offline with labels for all candidate models, an assumption that breaks in deployment, where only the outcome of the chosen model is observed. We bridge this gap with BaRP, a Bandit-feedback Routing with Preferences approach that trains under the same partial-feedback restriction as deployment, while supporting preference-tunable inference: operators can dial the performance/cost trade-off at test time without retraining. Framed as a contextual bandit over prompt features and a user preference vector, our method simulates an online feedback setting during training and adapts its routing decisions to each new prompt, rather than depending on full-information offline supervision. Comprehensive experiments show that our method consistently outperforms strong offline routers by at least 12.46% and the largest LLM by at least 2.45%, and generalizes robustly for unseen tasks.
BibTeX
@misc{wei2025learning,
  author = {Wang Wei and Tiankai Yang and Hongjie Chen and Yue Zhao and Franck Dernoncourt and Ryan A. Rossi and Hoda Eldardiry},
  title = {{Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs}},
  year = {2025},
  eprint = {2510.07429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.07429},
}
Figure