Online Learning with LLM Experts from Limited Feedback
Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt, Ryan A. Rossi, Branislav Kveton, Hoda Eldardiry
cs.LG · stat.ML
Quick verdict
Bandit algorithms route prompts to LLM experts under a feedback budget; theory is promising but proofs have gaps and Nectar Table 1 gains sit within noise.
Summary
The paper formulates routing of incoming prompts to one of K LLM experts as a contextual linear bandit in which reward feedback (human or LLM-judge) can be requested at most m ≪ T times, retrospectively, for any past round. LimFullFeed (full-information feedback) periodically selects the unlabeled past prompt that most increases the covariance determinant and observes the entire reward vector, achieving Õ(dT/√m) regret, within √d of a matching lower bound; LimBanFeed (bandit feedback) maintains per-expert confidence sets, queries feedback every T/m uses of an expert, and achieves Õ(dT√(K/m)) regret. An appendix extends this to non-uniform evaluation costs. Experiments on RouterBench (K=11, d=40, 10k prompts) and Nectar (K=6, d=40, T=60000) against NoLookBack and AllFeedback over five runs show clear bandit-setting gains (e.g., Nectar m=10000: 1839.1 vs 2538.4 regret), but in the full-information setting Table 1 shows NoLookBack ahead at small m and differences within one standard deviation elsewhere, so the stated "consistent" advantage over NoLookBack is not supported on Nectar. Limitations include proof gaps (a unit-norm trace step conflicting with the ‖x‖≤L assumption; a sketched bandit lower bound), missing Nectar configuration details and code, and reliance on stored outputs and judge quality.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 4
● low 1
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under a feedback budget m ≪ T with retrospective labeling of past rounds, LLM routing is learnable with regret Õ(dT/√m) under full-information feedback and Õ(dT√(K/m)) under bandit feedback (Theorems 3.2 and 4.1).
- The full-information upper bound matches the lower bound (Thm 3.3) up to a factor √d, and this gap is attributed to the union bound over unknown prompts.
- Selecting feedback rounds by covariance-determinant gain (looking back) beats querying only the current round (NoLookBack), with the advantage growing in m, as shown on RouterBench and Nectar.
- The framework extends to non-uniform expert evaluation costs, with evaluation frequency proportional to cost and regret O(dT·m^{−1/2}·(Σ_j z_j)^{1/2}·log T) (Appendix A).
Strengths
Genuinely new feedback model
The agent chooses retrospectively which past round to label under a global budget m≪T (§2); §C carefully distinguishes this from partial monitoring, delayed feedback, knapsack, conservative, and abstention bandits, where the observation is not agent-controlled this way.
Essentially complete full-information analysis
The determinant-greedy lookback (Eq. 4) lets B.1 restore a telescoping sum despite no per-round covariance update; AM–GM gives det(V_T) ≤ ((Tr V_0 + m)/d)^d, and the Õ(dT/√m) bound (Thm 3.2) sits within √d of the lower bound T√d·e^{−4}/(8√m) (Thm 3.3), with a G-optimal-design hindsight argument supporting near-optimality of periodic feedback.
Practical algorithmics with measured overhead
Honest limitations and clean budget accounting
Weaknesses
Headline empirical claim contradicted by own Table 1
Proof gaps in the theoretical core
Only self-constructed baselines, simulated linear rewards
Incomplete experimental specification and no code
Full-information feedback hides inference cost
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv 2609.05820; Virginia Tech + Adobe Research) studies adaptive routing of user prompts to one of K LLM experts over T rounds under the constraint that reward feedback — human labels or LLM-judge scores — can be obtained at most m ≪ T times, and, crucially, *retrospectively*: at any round the agent may label the reward of any earlier, still-unlabeled round (Section 2). Prompts are embedded and rewards modeled linearly, r_{t,a} = ⟨θ_a, x_t⟩ + η_{t,a}, with independent sub-Gaussian noise (Assumption 3.1). Two settings are analyzed: (i) full-information feedback (§3, LimFullFeed): every ⌊b(t−1)⌋ < ⌊bt⌋ trigger (roughly every T/m rounds) the agent labels the past prompt maximizing the covariance-determinant gain (Eq. 4) and observes the entire reward vector; regret Õ(dT/√m) (Thm 3.2) against lower bound T√d·e^{−4}/(8√m) (Thm 3.3) — tight within √d. (ii) bandit feedback (§4, LimBanFeed): per-expert covariances, UCB selection (Eq. 6); after each expert accumulates z = T/m uses, the most informative prompt it served is labeled; regret Õ(dT√(K/m)) (Thm 4.1) vs lower bound T√K·e^{−4}/(8√m) (Thm 4.2). Appendix A prices feedback per expert (z_j), evaluating expert j every z_j·e_z uses with e_z ≥ T/m, and derives regret O(dT·m^{−1/2}·(Σ_j z_j)^{1/2}·log T). Budget feasibility is proven by construction: Σ_a ⌊|S_{T,a}|/z⌋ ≤ T/z ≤ m (§4.1).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does this paper solve?
It studies how to route incoming user prompts to the best of K large language models in real time when evaluating responses (via humans or an LLM judge) is expensive and affordable for only m out of T rounds. It models this as a contextual bandit where the algorithm may also retroactively request evaluation labels for a small number of past prompts.
What regret guarantees are proven?
For full-information feedback (all experts' rewards observable for a labeled round), regret Õ(dT/√m), matching a lower bound up to a factor √d. For bandit feedback (only the chosen expert's reward observable), regret Õ(dT√(K/m)), with a lower bound of order T√K/√m.
Does the proposed method actually beat simpler baselines?
Clearly in the bandit-feedback setting (e.g., on Nectar with m=10000: regret 1839.1 vs 2538.4 for the naive baseline). In the full-information setting the advantage over NoLookBack is within noise on Nectar (Table 1) and NoLookBack is even better at small feedback budgets; a visible gap appears on RouterBench.
Is code or data available for this paper?
No code or data release is stated in the paper. The RouterBench pipeline (embeddings, PCA to 40 dimensions, simulated linear rewards) is described in Appendix D, but the Nectar configuration is only partially specified, so full replication currently requires reimplementation.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Mathematical notation in the Appendix B proofs is heavily garbled by PDF extraction (e.g., 'T(x)', 'y′the = xs', 'Vτt−1,a,a'); some proof-level typos I attribute to the paper may be extraction artifacts — I flagged only issues readable despite the garbling.
- Figures 1–2 appear only as captions and axis labels in the extraction; the plotted curve values could not be verified beyond the caption text, so figure-based judgments rely on Table 1 numbers.
- The provided text ends at the Figure 2 caption (page 21); any Appendix D content beyond that point (e.g., Nectar setup details) was unavailable, so 'missing Nectar configuration' applies only to the extracted text, not necessarily to the published PDF.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.