Online Learning with LLM Experts from Limited Feedback
Abstract Overview
This paper studies online prompt routing among multiple LLM experts when response-quality feedback is available only for a limited number of rounds. The authors formulate the problem as a contextual bandit with prompt embeddings as contexts, LLMs as actions, and a feedback budget m much smaller than the horizon T. They develop separate algorithms for full-information feedback, where rewards for all experts can be queried for a past round, and bandit feedback, where only the chosen expert's reward can be queried. In both cases, the methods periodically look back over past prompts and select feedback points that maximize information gain through the covariance determinant. The paper combines regret analysis with experiments on RouterBench and Nectar to evaluate whether this selective-feedback strategy improves routing under constrained supervision.
Novelty
The distinctive contribution is an online LLM-routing framework in which the learner can adaptively choose not only whether to request feedback, but also which past prompt to evaluate under a hard feedback budget. The proposed feedback policy selects past prompts that maximally increase the determinant of the covariance matrix, extending from a shared full-information setting to a bandit setting with expert-specific confidence sets.
Results
The paper proves regret bounds of O(dT m^-1/2 log(TL)) in the full-information setting and O(dT sqrt(K/m) log(TL)) in the bandit setting, along with corresponding lower bounds. Empirically, the proposed methods learn effective routing policies on Nectar and RouterBench and outperform the NoLookBack baseline in the bandit setting across all evaluated budgets. For instance, on Nectar with K=6, d=40, and T=60000, LimBanFeed achieves a cumulative regret of 1567.9±13.4 compared to 2090.7±21.2 for NoLookBack at m=20000.
Key Points
- The work formalizes adaptive online routing to LLM experts with delayed, budgeted feedback as a contextual bandit problem.
- Its core algorithmic idea is to query feedback retrospectively for past prompts that maximize information gain via covariance determinant maximization.
- Theoretical bounds and empirical results show that selective retrospective feedback reduces regret compared to querying feedback only at current rounds, with bandit feedback incurring an additional sqrt(K) factor over full-information feedback.