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:
- 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.
- 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), andE5-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