- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies joint LLM routing and scheduling in a queueing system where unsatisfied users may retry their queries. The authors formulate the problem as contextual queueing bandits with multinomial logit (MNL) feedback and propose ACQB, which combines Thompson sampling with decaying forced exploration. They establish sublinear cumulative regret and decaying queue length regret without requiring prior knowledge of the time horizon or traffic slackness. The paper also introduces disjoint parameterization and contrastive learning for query representations. Experiments on synthetic data, three LLM routing datasets, and WildChat conversation logs demonstrate improvements over several baselines.
Critical strengths
- This paper proposes a new bandit formulation that jointly considers LLM routing, scheduling, and congestion caused by user retrials. The integration of queueing dynamics with contextual MNL feedback is interesting and practically motivated.
- The proposed algorithm achieves regret guarantees without requiring prior knowledge of the time horizon or traffic slackness, which is useful for continuous LLM services.
- The experiments cover multiple datasets and show promising improvements over existing methods.
Critical weaknesses
- My most critical concern is the validity of Assumption 2. Consider any nonzero feature vector . By choosing and letting , we obtain This contradicts the strictly positive lower bound required by Assumption 2. One possible fix is to restrict the infimum to . However, it seems that the MLE in Equation (1) is optimized over the entire , so it does not guarantee that . Therefore, simply restricting Assumption 2 to the unit ball may not be sufficient to justify the MLE confidence bounds used in the regret analysis. The authors should clarify how this issue can be resolved.
- The experimental settings are inconsistent with the theoretical assumptions. Under Assumption 1, and , which imply that the departure probability is bounded by . Thus, the maximum departure probabilities are approximately 0.73 for and 0.84 for . However, Section 5.2 considers arrival rates as high as for and for . These settings cannot satisfy Assumption 4, which requires for some . Moreover, the experiments construct departure probabilities as high as 0.99 (Appendix B.5), which violates the bound in Assumption 1.
- The model assumes that each response immediately produces an observable acceptance or rejection outcome. However, this assumption is unrealistic in practical LLM services, since users typically do not explicitly indicate whether they are satisfied with a response. In the experiments, the dataset also does not provide explicit acceptance or rejection feedback, so the authors infer retrials from similar queries and assume that the last query in each chain is successfully completed. These assumptions may not accurately reflect user satisfaction.
Questions for authors
- Could the authors clarify whether Assumption 2 holds as stated? If it does not, how can the issue be resolved without affecting the theoretical guarantees?
- Could the authors clarify why the experiments use departure probabilities and arrival rates that are incompatible with Assumptions 1 and 4? Can the theoretical guarantees be extended to these experimental settings?
- How would the proposed algorithm handle delayed or unobserved retrial feedback in practical LLM services?
I would be willing to reconsider my rating if the authors address these concerns.
5 comments
Dear Reviewer,
We apologize for the delay in preparing our rebuttal. The experiments took longer than expected, which caused the delay.
We have now completed the experiments, and only the writing of the rebuttal remains.
Thank you for your consideration. We will do our best to provide a thorough response to your concerns.
Best regards, Authors
[W1] My most critical concern is the validity of Assumption 2. Consider any nonzero feature vector . By choosing and letting , we obtain This contradicts the strictly positive lower bound required by Assumption 2. One possible fix is to restrict the infimum to . However, it seems that the MLE in Equation (1) is optimized over the entire , so it does not guarantee that . Therefore, simply restricting Assumption 2 to the unit ball may not be sufficient to justify the MLE confidence bounds used in the regret analysis. The authors should clarify how this issue can be resolved.
[Q1] Could the authors clarify whether Assumption 2 holds as stated? If it does not, how can the issue be resolved without affecting the theoretical guarantees?
We thank the reviewer for identifying this error. We have corrected Assumptions 1--2 and Equation (1) and revised the confidence proof in Lemma 34. In the original version, we adopted Assumption 2 of Oh and Iyengar (2019) [1] to simplify the analysis. Although the original condition does not hold as stated, this issue is resolved through the standard analysis of constrained maximum likelihood estimation on a bounded parameter set. These corrections preserve the regret orders in Theorems 5--6 for fixed and .
-
In Assumptions 1--2, we now require and take the infimum only over . We also compute in Equation (1). Thus both the true parameter and the MLE satisfy the norm bound.
-
For the confidence bound, we use the standard first-order optimality condition for constrained minimization . Together with Assumption 2 on the bounded set, it gives in Lemma 34. The subsequent regret analysis remains the same.
[W2] The experimental settings are inconsistent with the theoretical assumptions. Under Assumption 1, and , which imply that the departure probability is bounded by . Thus, the maximum departure probabilities are approximately 0.73 for and 0.84 for . However, Section 5.2 considers arrival rates as high as for and for . These settings cannot satisfy Assumption 4, which requires for some . Moreover, the experiments construct departure probabilities as high as 0.99 (Appendix B.5), which violates the bound in Assumption 1.
[Q2] Could the authors clarify why the experiments use departure probabilities and arrival rates that are incompatible with Assumptions 1 and 4? Can the theoretical guarantees be extended to these experimental settings?
We have clarified in Section B.5 why the original experiments in Section 5.2 do not follow our theoretical assumptions and why empirical evaluations need not satisfy these assumptions. We also added experiments satisfying Assumptions 1--4 in Sections B.6 and C.4--C.5. The original departure probabilities are computed directly from benchmark utilities, rather than from a fixed satisfying Assumption 1. These experiments assess empirical performance, but Theorems 5--6 do not apply to this setting.
-
For the additional environment, we use unit-norm features, , i.i.d. arriving contexts, and positive definite feature covariance. We generate feedback from and set
so every context has traffic slack at least . Both and use the joint constrained MLE. Full settings are in Section B.6 and Table 8.
-
In this environment, ACQB achieves the lowest cumulative regret and queue length regret among all seven routing methods under the same FIFO scheduler on all three datasets. The TS/UCB comparison also covers both and . Full results are in Sections C.4--C.5 and Figures 11--12.
Dear Authors,
Are you still preparing your rebuttal? I think this paper's idea is interesting, and it is also one of the few papers in my review batch that does not exhibit extensive signs of AI-generated writing. I would like to increase my score if you can address my concerns. However, these concerns relate to the correctness of the results, so I cannot recommend acceptance directly unless they are resolved.
I will wait until the rebuttal deadline.
Best regards,
Reviewer 7sPG