- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies online LLM selection when repeated interactions improve model quality but users prioritize immediate rewards. It models this setting using parametric stochastic rising bandits and proposes GAP-UCB, which fits saturation curves and compares models at a common prospective adaptation state. It further introduces iGAP-UCB, a fee-and-compensation mechanism with ex-post budget balance. The paper presents regret guarantees and evaluates both methods through simulations based on four LLMs’ GSM8K fine-tuning trajectories.
Critical strengths
-
The formulation captures a useful interaction between learning and incentives: selecting a model both reveals its quality and improves its future performance, while individual users may not benefit from supporting this improvement. Connecting these effects provides an informative perspective on dynamic model selection.
-
The combination of prospective reward estimation and budget-balanced intervention is appealing. The stated analysis separates statistical uncertainty from delayed-adaptation costs, while the experiments provide encouraging evidence that the incentive mechanism can closely track the platform-controlled policy.
Critical weaknesses
-
The headline regret claim needs clearer qualification. Theorem 3.3 includes a growth-dependent term, and Corollary 3.5 contains an additional term proportional to (T^{1-a_{\mathrm{poly,min}}}), which can dominate the square-root statistical term. The abstract and conclusion should specify the conditions under which the stated square-root regret rate applies. This matters because the improved regret guarantee is a central contribution.
-
The empirical support has a limited scope. The experiments simulate selection using four models’ fine-tuning trajectories on a single task, with user choices following the assumed utility model. These results support the framework within the evaluated setting, but provide limited evidence about robustness to imperfect saturation fits or deviations from the assumed user behavior. This limits the strength of the practical applicability claims.
Questions for authors
-
What restrictions on the candidate family library are required for the overall square-root regret rate, and which parameter ranges were used in the experiments?
-
How sensitive are the reported gains to trajectory misspecification and observation noise? Please clarify whether rewards are drawn directly from empirical trajectories or from fitted curves, and report variability across repeated simulations.
3 comments
Response to Reviewer Yr9b (2/2)
Q1: Conditions for Square-Root Regret and Experimental Parameter Ranges
The overall square-root regret rate, up to logarithmic factors, holds when the reward-growth-dependent term satisfies . As characterized in Corollary 3.5, this condition is satisfied by exponential and hyperbolic saturation families, as well as polynomial saturation with exponent . For polynomial saturation with , the additional growth-dependent term may dominate, resulting in an overall regret bound of .
Regarding the experimental parameter ranges, we use:
-
GSM8K: , .
-
XSum text summarization: ,
These ranges specify the feasible parameter domains used for online fitting. In particular, the polynomial fitting ranges include exponents below ; therefore, the overall square-root regret guarantee does not hold uniformly over these parameter domains. Nevertheless, the complete family-dependent bound in Theorem 3.3 remains applicable under its stated assumptions.
Q2: Model Misspecification, Observation Noise, and Experimental Robustness
We thank the reviewer for this question. We clarify the reward generation process and the robustness of our approach as follows.
Reward observations. In the GSM8K experiments, rewards are taken directly from the empirical fine-tuning trajectories, where each adaptation step is evaluated on 273 held-out problems. We do not generate rewards from fitted saturation curves. Similarly, in the additional XSum text summarization experiments (Appendix E.4), we use reward trajectories digitized from Xia et al. (2024), with their late-stage segments repeated to construct a longer simulation horizon. The saturation families are used only for online reward estimation and model selection, not for generating the experimental rewards.
Model misspecification and observation noise. Our stochastic reward model accommodates observation noise under the assumed sub-Gaussian noise conditions. To further investigate deviations from the candidate saturation families, we have added a robustness analysis in Appendix F, establishing that bounded model misspecification of magnitude introduces an additional regret term. In particular, when , the additional regret is , preserving the original square-root regret order whenever the family-dependent growth term satisfies . Moreover, when , the additional regret is only .
Our empirical results provide complementary evidence of robustness to imperfect saturation fits. For example, Table 2 reports a best-fitting of 0.368 for Yi-6B, yet GAP-UCB achieves favorable performance on the empirical trajectories. This suggests that accurate fitting of every observed reward fluctuation is not necessary for effective finite-horizon model selection.
Variability across simulations. Our experiments replay fixed empirical reward trajectories rather than generating new fine-tuning trajectories for each simulation. Consequently, repeated runs with identical reward sequences and algorithmic randomness produce identical results. We clarify this experimental setup and distinguish variability in online model selection from variability arising from independent LLM fine-tuning runs.
References
[1] Yu Xia, Fang Kong, Tong Yu, Liya Guo, Ryan A. Rossi, Sungchul Kim, and Shuai Li. Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits. Proceedings of the ACM Web Conference (WWW), 2024.
Follow-up on Our Rebuttal
Dear Reviewer Yr9b,
Thank you again for your careful and constructive comments. We hope that our revisions and additional analysis have addressed your main concerns. We would be happy to provide further explanations or analyses where helpful.
We look forward to your feedback and appreciate your time and consideration. Thanks.
Best Regards,
Authors of Submission43597
Response to Reviewer Yr9b (1/2)
W1. Qualification of the Regret Guarantee.
We thank the reviewer for this careful observation. As already characterized in Corollary 3.5, exponential and hyperbolic saturation contribute only logarithmic growth-dependent terms, whereas polynomial saturation introduces an additional O(Kapoly,minT1−apoly,min) term when apoly,min<1. When apoly,min≥1/2, this additional term does not dominate the square-root statistical term (for fixed K), and the overall regret achieves O(T). For 0<apoly,min<1/2, the growth-dependent term may dominate, and the overall guarantee becomes O(T1−apoly,min).
We have revised the Abstract and Conclusion to explicitly state the complete regret bound and clarify the reward-family-dependent conditions under which the overall square-root regret rate holds and present them below as well. These revisions are highlighted in blue in the updated manuscript.
W2: Experimental Scope and Robustness
We thank the reviewer for this important concern. We have substantially extended our evaluation and theoretical analysis in three aspects.
(1) Additional task and LLMs. We conduct additional model-selection experiments using reward trajectories of five candidate LLMs from an independent text summarization task reported by Xia et al. (2024). The trajectories are digitized from their published results and extended for longer-horizon online simulations. We evaluate both platform-controlled and user-driven settings, with detailed results presented in Appendix E.4.
(2) Heterogeneous user preferences. We extend the baseline user model to allow individual valuations to deviate from the platform's published estimates. We consider two scenarios: random preferences and model-specialized preferences, in which arriving users may favor different LLMs. As shown in Figure 12(b) of Appendix G.4, at p=0.1, iGAP-UCB maintains a final regret of approximately 155 across all tested heterogeneity levels ζ∈[0,0.2] under random preferences. Under model-specialized preferences, its regret increases only slightly, from approximately 155 to 159, whereas iRedUCB's regret increases from approximately 206 to 337, shown in Figure 13(b). Moreover, at p=0.15, iGAP-UCB maintains nearly constant regret across both scenarios (Figure 13(c)). These results demonstrate its empirical robustness to heterogeneous user valuations under sufficiently large fee caps. The corresponding theoretical guarantee is established in Theorem G.2.
(3) Robustness to model misspecification. We further relax the exact realizability assumption by allowing the true expected reward trajectories to deviate from the candidate saturation families by at most ϵ. The robustness analysis in Appendix F establishes an additional O(ϵT) regret term, explicitly quantifying the effect of model misspecification. Moreover, our empirical trajectories are not perfectly fitted by the candidate families. For example, Table 2 reports a best-fitting R2 of 0.368 for Yi-6B, yet GAP-UCB achieves favorable performance on these trajectories. This provides empirical evidence that accurate curve fitting is not a prerequisite for favorable finite-horizon performance.
Together, these additions provide broader experimental evidence and theoretical robustness guarantees beyond the original single-task setting, while acknowledging that the experiments remain simulation-based rather than a deployed human--AI system.
References
[1] Yu Xia, Fang Kong, Tong Yu, Liya Guo, Ryan A. Rossi, Sungchul Kim, and Shuai Li. Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits. Proceedings of the ACM Web Conference (WWW), 2024.