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 EldardirySubmission to ICLR 2026 · Rejected

TL;DR

Current LLM routers require expensive, unrealistic full-information training—measuring every prompt against every candidate model—and freeze the cost–accuracy trade-off at training time. BaRP (Bandit-feedback Routing with Preferences) frames model routing as a contextual bandit that learns strictly from single-model feedback (the model actually invoked) while accepting a dynamic preference vector, allowing engineers to dial between latency/cost and quality at runtime without retraining.

What Problem Does This Paper Address?

Deploying large language models (LLMs) at scale requires balancing output quality with API cost: simple prompts waste money when sent to frontier models like GPT-4, while complex tasks fail on lightweight open models.

Existing learned routers (such as RouterDC or GraphRouter) suffer from two major flaws:

  1. Full-Information Assumption: They rely on offline training logs containing evaluations for every candidate LLM on every prompt. In production, a router only observes feedback (accuracy and cost) for the single model it selects—a classic partial-feedback or bandit setting.
  2. Static Trade-Offs: Once trained, existing routers lock in a fixed performance-versus-cost ratio. If budget constraints tighten or quality demands rise, the system cannot adjust without being completely retrained.

Methods

BaRP models LLM selection as a multi-objective contextual bandit:

Context s_t = (Prompt x_t, Preference w_t)
                   │
                   ▼
     ┌────────────────────────────┐
     │  BaRP Router Policy π_θ    │
     │  - Frozen MiniLM Encoder   │
     │  - Preference MLP          │
     │  - MLP Decision Head       │
     └─────────────┬──────────────┘
                   │ Selects Action a_t (LLM)
                   ▼
          [ Candidate LLMs ]
                   │
                   ▼ Bandit Feedback Only: (q_t, c_t)
     ┌────────────────────────────┐
     │  Reward r_t = w^q q - w^c c│
     └─────────────┬──────────────┘
                   │
                   ▼
     REINFORCE Update with Entropy Regularization
  • Preference-Conditioned Context: The context consists of the prompt $x_t$ and a user preference vector $w_t = (w_t^q, w_t^c)$ on the 1-simplex ($w_t^q + w_t^c = 1$). The scalar reward balances normalized score $q_t \in [0, 1]$ and capped cost $\tilde{c}_t = \min(c_t / \tau, 1)$ via $r_t = w_t^q q_t - w_t^c \tilde{c}_t$.
  • Architecture: A frozen, compact sentence encoder (all-MiniLM-L6-v2) extracts prompt embeddings $h(x)$, while a small MLP projects the 2D preference vector into an embedding $\phi(w)$. The concatenated representation passes through an MLP decision head to output categorical action probabilities over the $K$ candidate models.
  • Optimization: BaRP trains via REINFORCE policy gradients with a batch-mean reward baseline for variance reduction and Shannon entropy regularization ($\beta = 0.05$) to sustain exploration under partial feedback.
  • Inference: At test time, routing is deterministic ($\arg\max_{a} \pi_\theta(a \mid x, w)$), letting operators continuously tune $w$ on the fly per query or tenant.

Datasets

The authors evaluate BaRP across eight benchmarks:

  • In-Distribution Tasks (80/20 train/test split): GSM8K (math reasoning), MMLU (multidisciplinary knowledge), ARC-Challenge (science QA), Winogrande (commonsense ambiguity), and Natural Questions (NQ).
  • Out-of-Distribution Generalization (unseen tasks): MBPP (Python code generation), HellaSwag (sentence completion), and HotpotQA (multi-hop QA).
  • Model Pool: Encompasses open and proprietary LLMs including GPT-4-1106, GPT-3.5-Turbo, Claude-v1/v2/Instant, Llama-2-70B, Llama-3.1 (8B/70B), Mistral-7B, Mixtral-8x7B/8x22B, Yi-34B, and Qwen-2.5-7B.

Key Insights and Ideas

  • Bandit feedback does not sacrifice routing performance: Despite receiving feedback for only the chosen LLM during training, BaRP surpasses offline routers trained with complete, full-matrix supervision.
  • Bigger encoders are not necessary for routing: Comparing all-MiniLM-L6-v2 (384-dim), BERT-base-uncased (768-dim), and E5-large-v2 (1024-dim), MiniLM yielded the highest average score (74.32% vs. 72.26% for BERT and 74.18% for E5) with lower compute overhead. Modern contrastive sentence embeddings already capture the semantic difficulty required for model dispatch.
  • Non-linear routing policies outclass classical linear bandits: When pitted against standard contextual bandit algorithms (LinUCB, Linear Thompson Sampling, $\epsilon$-greedy), BaRP's policy-gradient MLP outperformed the best linear baseline by nearly 9 absolute percentage points (74.32% vs. 65.56%), proving that LLM capability boundaries are non-linear across task embeddings.

Key Results

  • In-Distribution Superiority: On held-out in-distribution prompts, BaRP achieves an average score of 73.57%, outperforming the full-information baselines RouterDC (63.68%) and GraphRouter (65.42%), while exceeding the single largest LLM baseline (70.87%).
  • Zero-Shot Task Generalization: On out-of-distribution benchmarks, BaRP averages 66.08%, substantially higher than GraphRouter (52.45%) and RouterDC (44.55%), matching or edging out the Largest LLM (64.50%).
  • Holistic Cost-Effectiveness: Averaged over all eight tasks, BaRP improves accuracy by 16.84% over state-of-the-art GraphRouter while cutting monetary inference costs by 50.00%.

Limitations and Future Work

  • Simulated Offline Bandit Environment: The policy was trained on static, historical log replay rather than live, streaming interactions with non-stationary online distributions.
  • Two-Dimensional Objective Space: The current implementation only models performance and monetary cost; operational metrics like time-to-first-token (TTFT), queue latency, and rate limits are omitted.
  • Single-Turn Decision Making: The contextual bandit formulation operates per turn and does not currently extend to multi-turn dialogues where state transitions and conversational context dictate model switching.

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 performance 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 a bandit-feedback routing 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 on RouterBench show that our method consistently outperforms strong offline routers, including GraphRouter and RouterDC, in terms of performance and cost, 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},
}

Loading related content...

Figure