Source-linked AI summary
Online Learning with LLM Experts from Limited Feedback
Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt, Ryan A. Rossi, Branislav Kveton, Hoda Eldardiry
TL;DR
Prompt routing must balance response quality against expensive, limited feedback when prompts arrive online and their rewards are usually unobserved. The paper develops contextual-bandit algorithms that choose when and where to collect feedback, and reports high-quality routing across popular LLM experts, with full-information regret uniformly lower than bandit regret in experiments.
Problem
The paper studies how to route each arriving prompt to the highest-mean-reward LLM when rewards are generally unobserved and costly feedback is available only m≪T times.
Source: §1 · p. 1Method
It models routing as a contextual bandit over prompt embeddings and develops algorithms that strategically select past prompts for feedback, separately by expert in the bandit setting.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
The paper concludes that choosing when and where to observe feedback supports adaptive prompt routing under limited feedback.
Source: §6 · p. 8Feedback may require retrospective storage of model outputs and noisy human or LLM judgments, and static benchmark experiments may not capture non-stationary user behavior or deployment constraints.
Source: Limitations · p. 9
Abstract
from arXiv · showhide
We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback. We formulate it as a bandit problem with $K$ actions that represent experts and $d$ features that encode prompts, over a horizon of $T$ rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of $\tilde{O}(d T / \sqrt{m})$, while in the bandit setting we achieve $\tilde{O}(d T \sqrt{K / m})$, where $m \ll T$ is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.
1 Introduction
LLMs differ in cost and capability, motivating prompt-by-prompt routing when response rewards are costly to observe. The paper frames this as online contextual-bandit learning and proposes limited-feedback algorithms with theoretical guarantees and empirical evaluation.
1 Introduction
- Full-information routing selects past prompts with high information gain for feedback and achieves regret ˜O(dT/√m), matching a lower bound up to a stated factor.The supplied contribution text truncates the lower-bound comparison.Source: §1 · p. 2
- In the bandit setting, the algorithm progressively observes rewards with high information gain separately for each expert; its regret has an additional K factor because feedback is K times scarcer.The supplied passage truncates the displayed bandit regret bound.Source: §1 · p. 2
- The paper also extends the bandit setting to experts with non-uniform evaluation costs.This result is located in Section A.Source: §1 · p. 2
- The paper evaluates its algorithms on Nectar and reports learning high-quality routing agents across popular GPT-3.5, GPT-4, LLaMA, and Mistral experts.The cited contribution identifies the dataset and model families but gives no numerical benchmark comparison.Source: §1 · p. 2
- The analysis addresses regret for prompts without feedback by periodically selecting past prompts that maximize the covariance determinant, reducing uncertainty in important directions.Periodic feedback selection performs nearly as well as hindsight-optimal choices, and the bandit method uses separate confidence sets per expert.Source: §1 · p. 2
2 Problem Setting
The problem setting models prompt routing as a linear contextual bandit: each expert scores prompt embeddings, while feedback is costly and can be requested retrospectively within a limited budget. Actions are made online before any feedback query for that round.
2 Problem Setting
- The model assumes expert parameters lie in the d-dimensional unit ball and prompt contexts are bounded; reward noise is independent across experts and rounds and sub-Gaussian with variance proxy 1.The noise assumption appears in the supplied passage fragment.Source: §2 · p. 2
- Each round supplies a prompt embedding, and an expert’s expected reward is the inner product of its unknown parameter vector and that embedding.The model treats the embedding as a frozen-transformer representation with a linear reward head.Source: §2 · pp. 2–3
- The algorithm chooses its expert before deciding whether to query feedback, so current prompts cannot trigger look-back evaluations without violating the budget.The formulation makes routing decisions using information learned up to that round; the paper compares this constraint with a NoLookBack baseline.Source: §2 · p. 3
- Feedback is limited to at most m<T observations, and the algorithm can choose which eligible past prompt to evaluate and when to request it.An observation may be the full reward vector or only the selected expert’s reward; evaluation incurs time or monetary cost.Source: §2 · p. 3
3 Full-Information Feedback
LimFullFeed uses scheduled feedback and selects informative past prompts to learn expert rewards under a limited observation budget. Its full-information guarantee incurs a T/m factor for limited feedback, while unknown prompts leave a gap between the upper and lower bounds.
3.1 Algorithm
- At roughly T/m-round intervals, the algorithm observes one previously unobserved round and obtains the reward vector for all experts.The schedule satisfies the observation budget, and each round can be observed at most once.Source: §3.1 · pp. 3–4
- LimFullFeed selects the past prompt that maximally increases the covariance determinant, reducing uncertainty across previously observed directions.The paper states that this determinant-based choice yields sub-linear regret.Source: §3 · p. 3, §3.1 · p. 4
3.2 Main Results
- When m = T, the regret guarantee is O(d T log T); limited feedback adds a multiplicative T/m factor.In full information, feedback covers all experts jointly, so the regret guarantee does not depend on K.Source: §3.2 · p. 5
- Unknown prompts create a gap between the upper and lower bounds; knowing prompts in advance removes the extra d factor from the upper bound.Without advance knowledge, the analysis must bound estimation error for all prompts in R^d, leading to a union bound over dimensions.Source: §3.2 · p. 5
4 Bandit Setting
LimBanFeed routes prompts using upper confidence bounds and selectively requests feedback on informative past prompts. It guarantees sublinear regret under the feedback budget, with a bound that worsens with the number of experts.
4 Bandit Setting
- Bandit feedback reveals only the chosen expert’s reward, and different experts can receive different numbers of feedback observations.The algorithm sets z to the average interval T/m between feedback requests and resets an expert’s counter after requesting feedback.Source: §4 · p. 5, §4.1 · p. 6
4.1 Algorithm
- LimBanFeed selects an expert by its upper confidence reward, then solicits feedback after that expert has been used z times.It selects an unevaluated past prompt for that expert to maximize the covariance determinant increase.Source: §4.1 · p. 6
4.2 Main Results
- O(dT sqrt(K/m) log(TL)) is the stated regret bound for LimBanFeed.The setting has K experts, d features, horizon T, and feedback budget m < T.Source: §4.2 · p. 6
- The bandit guarantee has a gap from the lower bound; the stated d factor can be removed when the algorithm knows the prompts.The remaining d/K gap is attributed to a lower-bound analysis based on hypothesis testing with K vectors and may be improved.Source: §4.2 · p. 7
5 Experiments
On RouterBench and Nectar, the limited-feedback methods achieve lower regret than NoLookBack, while AllFeedback has lower variance with more observations. Regret falls as the feedback budget grows, and runtime scales approximately linearly with the horizon.
Datasets and Baselines
- The evaluation uses RouterBench and Nectar, samples prompts into an online stream, and averages cumulative regret over five runs.NoLookBack queries feedback only for the current round, whereas AllFeedback assumes feedback every round.Source: §5 · p. 7
Main Results
- LimFullFeed and LimBanFeed consistently achieve lower regret than NoLookBack, while AllFeedback has smaller variance and full-information regret is lower than bandit regret.The reported comparisons include RouterBench and Nectar; LimFullFeed’s advantage over NoLookBack is noticeable by T = 60000.Source: §5 · pp. 7–8, Figure 1 · p. 8
Effect of the Feedback Budget
- Regret decreases as the feedback budget m increases on Nectar.Table 1 reports cumulative regret by m on Nectar with K=6, d=40, and T=60000.Source: §5 · p. 8, Table 1 · p. 8
Runtime Analysis
- Both methods scale approximately linearly with T; LimBanFeed scales linearly with K, while LimFullFeed is largely independent of K.Source: §5 · p. 8
6 Conclusions
The paper frames adaptive prompt routing as online learning with limited feedback and proposes algorithms for full-information and bandit settings. It reports regret guarantees and empirical effectiveness, with several extensions left for future work.
6 Conclusions
- The paper introduces algorithms for full-information and bandit feedback, with expert-dependent feedback selection in the bandit setting.Source: §6 · p. 8
- The authors report theoretical regret guarantees and empirical effectiveness for their methods.Source: §6 · p. 8
- Future work could study dynamic expert availability, varying prompt distributions, and tighter bandit-setting lower bounds.Source: §6 · pp. 8–9
Limitations
The section identifies constraints of retrospective feedback and static-benchmark experiments, then extends bandit feedback to experts with different evaluation costs.
Limitations
- Retrospective feedback may require storing model outputs and using noisy human or LLM judgments; static benchmarks may not capture non-stationary users or deployment constraints.These are stated as limitations of the setting and experiments.Source: Limitations · p. 9
A Bandit Feedback with Variable Costs
- With a total cost budget m, the evaluation cost of expert j is denoted z_j, and that expert is evaluated after z_j·e_z uses.The costs are assumed ordered z_1 ≥ z_2 ≥ ··· ≥ z_K.Source: A Bandit Feedback with Variable Costs · p. 12
- Evaluation frequency is made proportional to expert cost by using expert-specific intervals z_j·e_z and choosing e_z to keep total evaluation cost within budget m.The number of evaluations for an expert depends on its uses over the horizon and its cost.Source: A Bandit Feedback with Variable Costs · p. 12
- When all expert costs are 1, the variable-cost setting recovers the regret guarantee of Theorem 4.1.The analysis otherwise proceeds as in Theorem 4.1 with non-uniform update rates.Source: A Bandit Feedback with Variable Costs · p. 12
B.1 Proof of Theorem 3.2
The proof bounds full-information regret by tracking feedback rounds and covariance updates, using determinant-based prompt selection and a high-probability confidence event.
B.1 Proof of Theorem 3.2
- The proof tracks rounds with feedback through O_t, evaluated prompts through S_t, and the most recent feedback update through τ_t.The sets of feedback rounds are cumulative over time.Source: §B.1 · p. 12
- The regret analysis conditions on a high-probability confidence event, bounds regret on that event, and accounts separately for its complement.The complement contributes 2T·Pr(E^c), yielding the stated decomposition Reg(T) = Reg(T)|E + o(T^-1).Source: §B.1 · pp. 13–14
- At feedback collection, the algorithm updates the covariance matrix using the selected past prompt that most increases its determinant.The proof compares this selection with prompts in the intervening rounds.Source: §B.1 · p. 13
- Because covariance remains unchanged between feedback collections, and prompts lie in the unit ball, the proof bounds cumulative uncertainty using trace and AM-GM arguments.The analysis uses at most m feedback rounds and Tr(x_t x_t^T) ≤ 1.Source: §B.1 · pp. 13–14
B.2 Proof of Theorem 4.1
The proof analyzes bandit feedback with separate covariance updates for each expert, bounding regret through confidence sets and expert-specific feedback intervals.
B.2 Proof of Theorem 4.1
- The proof tracks feedback rounds and the latest update separately for each expert using O_t,a and τ_t,a.The feedback-round sets are cumulative over time.Source: §B.2 · p. 14
- At each round, the algorithm selects the expert with the largest upper-confidence reward for the arriving prompt.The proof uses this choice to establish that the selected expert’s upper-confidence reward is at least that of the optimal expert.Source: §B.2 · p. 14
- Each expert’s covariance matrix is updated separately, and feedback for an expert is collected after it has been used z times since its previous update.The selected feedback prompt maximizes the determinant increase for that expert’s covariance matrix.Source: §B.2 · p. 15
- The proof uses z ≥ T/m to keep feedback rounds within budget, then applies trace and AM-GM bounds and conditions regret on a high-probability event.The final theorem statement follows by substituting the value of β.Source: §B.2 · pp. 14, 16
B.3 Proof of Theorem 3.3
The proof constructs nearby prompt instances with binary features and compares the algorithm’s error events across instances using a KL-based inequality.
B.3 Proof of Theorem 3.3
- The lower-bound construction uses Gaussian unit-variance observations, prompts in {−1,+1}^d, and expert features in {−δ,+δ}^d.The allowed expert features are restricted by Hamming distance from a chosen prompt.Source: §B.3 · p. 16
- It compares d+1 instances whose prompt vectors lie within Hamming distance 1 of a reference, while keeping the expert-feature set fixed.The proof defines events based on whether the algorithm’s chosen expert differs from the prompt on a coordinate.Source: §B.3 · pp. 16–17
- The proof relates error probabilities across neighboring instances using the Bretagnolle–Huber inequality and Kullback–Leibler divergence.It also extends the comparison to prompts other than the reference instance.Source: §B.3 · p. 17
B.4 Proof of Theorem 4.2
The proof constructs bandit instances with a single repeated prompt and uses their limited-feedback information to derive a lower bound. The related work distinguishes this agent-controlled observation setting from prior bandit and LLM model-selection approaches.
B.4 Proof of Theorem 4.2
- The lower-bound construction repeats one prompt across rounds and varies expert features among the first K coordinates, leaving the remaining d − K coordinates inconsequential.The proof assumes feedback is provided only for the expert used to generate each response.Source: §B.4 · p. 18
- With δ = 1/√m, the bandit-instance data distributions have KL divergence O(exp(−mδ²)), which the proof uses to derive its lower bound.The proof applies the Bretagnolle–Huber inequality before substituting δ = 1/√m.Source: §B.4 · p. 18
C Related Work
- The agent chooses which past rewards to observe and uses a selected subset when periodically updating its model.Unlike delayed-feedback settings where delay is uncontrolled, this setting lets the agent control observation timing.Source: C Related Work · p. 19
- The paper treats response labeling as the cost, distinct from LLM model-selection work focused on inference cost.Inference cost may reflect token use or compute for hosting and serving models.Source: C Related Work · p. 19
- Unlike prediction-based LLM routing, this work learns routing online by selectively obtaining labels for queries.Prior routing methods described here predict absolute or relative model quality for a query.Source: C Related Work · p. 19
- The cited closest stochastic-bandit work proposes an unanalyzed contextual algorithm that subtracts costs from rewards, which the authors say does not fit their setting.The authors state that they both propose a practical algorithm and analyze it.Source: C Related Work · p. 20
D Implementation Details
The implementation uses a 10,000-prompt subset of RouterBench to fit expert parameters, and reports runtime scope and regret comparisons on Nectar.
D Implementation Details
- The RouterBench setup uses 10,000 prompts, 11 LLM experts, and 40-dimensional embeddings retaining 50% of feature variance; GPT-4 rankings provide labels for OLS expert estimates.Prompts are embedded at 384 dimensions before PCA reduces them to 40.Source: D Implementation Details · p. 20
- Table 2 reports runtime in seconds on Nectar with respect to K, d, and T.The supplied caption identifies the table's scope but not its individual runtime values.Source: Table 2 · p. 20
- LimFullFeed has better regret guarantees than NoLookBack, while AllFeedback has the smallest regret due to observing feedback at all rounds.NoLookBack evaluates the prompt at the round when feedback is requested.Source: Figure 2 · p. 21