acceptodds
Under review as a conference paper at ICLR 2027

Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits

Abstract

Explosive demands for LLMs often cause user queries to accumulate in server queues, requiring efficient routing (query-LLM matching) and scheduling (query prioritization) mechanisms. Several online algorithms are being deployed, but they overlook the following two key challenges inherent to conversational LLM services: (1) unsatisfied users may retry queries, increasing the server backlog, and (2) requests for "explicit" feedback, such as ratings, degrade user experiences. In this paper, we develop a joint routing and scheduling algorithm that leverages "implicit" feedback inferred from user retrial behaviors. The key idea is to propose and study the framework of contextual queueing bandits with multinomial logit feedback (CQB-MNL). CQB-MNL models query retrials, as well as context-based learning for user preferences over LLMs. Our algorithm, anytime CQB (ACQB), achieves efficient learning while maintaining queue stability by combining Thompson sampling with forced exploration at a decaying rate. We show that ACQB simultaneously achieves a cumulative regret of for routing and a queue length regret of for any large . For experiments, we refine query embeddings via contrastive learning while adopting a disjoint parameter model to learn LLM-specific parameters. Experiments on synthetic data, offline routing datasets (SPROUT, EmbedLLM, and RouterBench), and real user conversation logs (WildChat-1M) confirm that our methods improve routing, scheduling, and queue stability against strong online and offline-trained baselines.

Primary area:
reinforcement learning
Keywords:
contextual bandits, logistic bandits, queueing bandits, LLM routing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_7sPGOpenReview ↗
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
  1. 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.
  2. The proposed algorithm achieves regret guarantees without requiring prior knowledge of the time horizon or traffic slackness, which is useful for continuous LLM services.
  3. The experiments cover multiple datasets and show promising improvements over existing methods.
Critical weaknesses
  1. My most critical concern is the validity of Assumption 2. Consider any nonzero feature vector x−jx_{-j}. By choosing θ=−cx−j\theta=-c x_{-j} and letting c→∞c\to\infty, we obtain pj(x,S,θ)p0(x,S,θ)=exp⁡(−c∣x−j∣2)(1+∑k∈Sexp⁡(x−k⊤θ))2≤exp⁡(−c∣x−j∣2)→0.p_j(x,S,\theta)p_0(x,S,\theta)=\frac{\exp(-c\\|x_{-j}\\|^2)}{\left(1+\sum_{k\in S}\exp(x_{-k}^{\top}\theta)\right)^2} \leq \exp(-c\\|x_{-j}\\|^2) \to 0. This contradicts the strictly positive lower bound required by Assumption 2. One possible fix is to restrict the infimum to ∣θ∣2≤1\\|\theta\\|_2\leq1. However, it seems that the MLE in Equation (1) is optimized over the entire Rd\mathbb R^d, so it does not guarantee that ∣θ^t∣2≤1\\|\widehat{\theta}_t\\|_2\leq1. 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.
  2. The experimental settings are inconsistent with the theoretical assumptions. Under Assumption 1, ∣x−j∣2≤1\\|x_{-j}\\|_2\leq1 and ∣θ∗∣2≤1\\|\theta^\ast\\|_2\leq1, which imply that the departure probability is bounded by R(x,S,θ∗)≤Ke/(1+Ke)R(x,S,\theta^\ast)\leq Ke/(1+Ke). Thus, the maximum departure probabilities are approximately 0.73 for K=1K=1 and 0.84 for K=2K=2. However, Section 5.2 considers arrival rates as high as λ=0.9\lambda=0.9 for K=1K=1 and λ=0.95\lambda=0.95 for K=2K=2. These settings cannot satisfy Assumption 4, which requires R(x,S,θ∗)≥λ+ϵR(x,S,\theta^*)\geq\lambda+\epsilon for some SS. Moreover, the experiments construct departure probabilities as high as 0.99 (Appendix B.5), which violates the bound in Assumption 1.
  3. 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
  1. 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?
  2. 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?
  3. 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 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

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 x−jx_{-j}. By choosing θ=−cx−j\theta=-cx_{-j} and letting c→∞c\to\infty, we obtain pj(x,S,θ)p0(x,S,θ)=exp⁡(−c∣x−j∣2)(1+∑k∈Sexp⁡(x−k⊤θ))2≤exp⁡(−c∣x−j∣2)→0.p_j(x,S,\theta)p_0(x,S,\theta) =\frac{\exp(-c\\|x_{-j}\\|^2)}{\left(1+\sum_{k\in S}\exp(x_{-k}^{\top}\theta)\right)^2} \le\exp(-c\\|x_{-j}\\|^2)\to 0. This contradicts the strictly positive lower bound required by Assumption 2. One possible fix is to restrict the infimum to ∣θ∣2≤1\\|\theta\\|_2\le 1. However, it seems that the MLE in Equation (1) is optimized over the entire Rd\mathbb R^d, so it does not guarantee that ∣θ^t∣2≤1\\|\hat\theta_t\\|_2\le 1. 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 SS and κ\kappa.

  • In Assumptions 1--2, we now require ∥θ∗∥2≤S\lVert\theta^{\ast}\rVert_2\leq S and take the infimum only over ∥θ∥2≤S\lVert\theta\rVert_2\leq S. We also compute θ^t=arg,min⁡∥θ∥2≤SLt(θ)\widehat\theta_t=\operatorname*{arg\\,min}_{\lVert\theta\rVert_2\leq S}\mathcal L_t(\theta) 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 ⟨∇Lt(θ^t),θ∗−θ^t⟩≥0\langle\nabla\mathcal L_t(\widehat\theta_t),\theta^{\ast}-\widehat\theta_t\rangle\geq0. Together with Assumption 2 on the bounded set, it gives ∥θ^t−θ∗∥Vt≤αt\lVert\widehat\theta_t-\theta^{\ast}\rVert_{V_t}\leq\alpha_t in Lemma 34. The subsequent regret analysis remains the same.

[W2] The experimental settings are inconsistent with the theoretical assumptions. Under Assumption 1, ∣x−j∣2≤1\\|x_{-j}\\|_2\le 1 and ∣θ∗∣2≤1\\|\theta^{\ast}\\|_2\le 1, which imply that the departure probability is bounded by R(x,S,θ∗)≤Ke/(1+Ke)R(x,S,\theta^{\ast})\le Ke/(1+Ke). Thus, the maximum departure probabilities are approximately 0.73 for K=1K=1 and 0.84 for K=2K=2. However, Section 5.2 considers arrival rates as high as λ=0.9\lambda=0.9 for K=1K=1 and λ=0.95\lambda=0.95 for K=2K=2. These settings cannot satisfy Assumption 4, which requires R(x,S,θ∗)≥λ+ϵR(x,S,\theta^{\ast})\ge\lambda+\epsilon for some SS. 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 θ∗\theta^{\ast} 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, ∥θ∗∥2=1.8≤S=2\lVert\theta^{\ast}\rVert_2=1.8\leq S=2, i.i.d. arriving contexts, and positive definite feature covariance. We generate feedback from pj(x,St,θ∗)p_j(x,S_t,\theta^{\ast}) and set

    λ=min⁡x in the test poolmax⁡S′∈CR(x,S′,θ∗)−0.01,\lambda=\min_{x\text{ in the test pool}}\max_{S'\in\mathcal C}R(x,S',\theta^{\ast})-0.01,

    so every context has traffic slack at least ϵ=0.01\epsilon=0.01. Both K=1K=1 and K=2K=2 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 K=1K=1 and K=2K=2. Full results are in Sections C.4--C.5 and Figures 11--12.

Reviewer_iHucOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the Contextual Queueing Bandits with Multinomial Logit Feedback (CQB-MNL) framework, which jointly handles LLM routing and scheduling and infers implicit feedback from user retries. It introduces the anytime CQB (ACQB) algorithm, which combines Thompson sampling with forced exploration at a decaying rate, and claims to achieve both O~(t)\widetilde{O}(\sqrt{t}) cumulative regret and O~(t−1/4)\widetilde{O}(t^{-1/4}) queue-length regret simultaneously, without requiring prior knowledge of the time horizon or the traffic slackness parameter. Experiments validate the approach on synthetic data, offline routing datasets, and real conversation logs.

The problem formulation is clear, and modeling user retries as an MNL outside option is a natural idea. The anytime property of ACQB—its independence from the horizon TT is a substantial improvement over prior work and is handled well in theory. In LLM services, the observation that users are unwilling to rate but express dissatisfaction through “retries” is realistic and has been underexploited. The CQB-MNL framework formalizes this observation, and the anytime nature of ACQB addresses the problem of unknown priors in continuous service.

Critical strengths
  1. This work addresses a problem of practical relevance. In real-world LLM services, user satisfaction is often not explicitly expressed. The motivation for inferring implicit feedback from retries is novel and practical, capturing a genuine pain point in LLM services. It proposes CQB-MNL to model query retries and the contextual learning of user preferences across LLMs, and further introduces an anytime CQB method that requires no prior knowledge of quantities such as the time horizon, thereby expanding the method’s practical applicability.

  2. The experiments cover a wide range, and the engineering details are relatively complete. The experiments are conducted on synthetic data, real offline routing datasets, and real conversation logs, and the results effectively validate the claimed algorithmic performance.

Critical weaknesses
  1. There may still be room for improvement in the theoretical results. The order in dd in the paper’s regret bounds is inferior to the tight results for LinUCB and Logistic Bandits. The theoretical bounds exhibit a relatively strong polynomial dependence on dd. In large-scale real-world applications, the dimension dd may be very large; consequently, the performance of the proposed method may be limited in high-dimensional regimes.

  2. The real LLM conversation data in Section 5.3 is somewhat limited. The paper points out that the validation on WILDCHAT-1M is in fact a replay simulation of retry chains inferred using a heuristic threshold (0.995); the retrials are not real labels, which undermines validation for real-world deployment.

Questions for authors
  1. Regarding the theoretical part of the paper, is here any analysis of a lower bound on regret to show that the algorithm achieves the optimal regret bound?

  2. The paper mentions that in the real-data experiments, user retries on WILDCHAT-1M are annotated through cosine-similarity inference. Semantic similarity is error-prone; for example, two queries that are semantically similar but reflect different user intents may be misclassified as a retry. Is there any evidence supporting the reasonableness of adopting the modeling approach used in the paper for the real-data experiments, as well as the robustness of the conclusions to changes in the threshold (e.g.0.999)?

4 comments

[W1] There may still be room for improvement in the theoretical results. The order in (dd) in the paper's regret bounds is inferior to the tight results for LinUCB and Logistic Bandits. The theoretical bounds exhibit a relatively strong polynomial dependence on (dd). In large-scale real-world applications, the dimension (dd) may be very large; consequently, the performance of the proposed method may be limited in high-dimensional regimes.

[Q1] Regarding the theoretical part of the paper, is here any analysis of a lower bound on regret to show that the algorithm achieves the optimal regret bound?

We provide below a comparison with standard cumulative regret rates and recent queue length regret lower bounds. Our UCB variant matches the standard cumulative regret rate, while our queue length guarantee holds without prior knowledge of TT or traffic slackness.

  • For cumulative regret, the UCB variant achieves O~(dT)\widetilde O(d\sqrt T) (Section 3). Our context set X\mathcal X may be infinite, and this matches the rate in dd and TT for linear and logistic bandits with infinite action sets.

  • For queue length regret, the UCB variant currently achieves O~(d5/2T−1/4)\widetilde O(d^{5/2}T^{-1/4}) (Section 3). We expect that the dependence on dd can be improved to linear, as in the average regret per round O~(d/T)\widetilde O(d/\sqrt T), because queue length regret is governed by the per-round gaps in departure rate.

  • For horizon dependence, Bae and Lee (2026, Theorems 10 and 5) [1] establish Ω(T−1/2)\Omega(T^{-1/2}) lower and O~(T−1/2)\widetilde O(T^{-1/2}) upper bounds for logistic feedback (our K=1K=1 case). However, their upper bound requires a known horizon and does not directly apply to our anytime setting.

[W2] The real LLM conversation data in Section 5.3 is somewhat limited. The paper points out that the validation on WILDCHAT-1M is in fact a replay simulation of retry chains inferred using a heuristic threshold (0.995); the retrials are not real labels, which undermines validation for real-world deployment.

[Q2] The paper mentions that in the real-data experiments, user retries on WILDCHAT-1M are annotated through cosine-similarity inference. Semantic similarity is error-prone; for example, two queries that are semantically similar but reflect different user intents may be misclassified as a retry. Is there any evidence supporting the reasonableness of adopting the modeling approach used in the paper for the real-data experiments, as well as the robustness of the conclusions to changes in the threshold (e.g.0.999)?

We do not have ground-truth retrial labels and have not manually checked the identified retrials, so we cannot verify them directly. However, we address this limitation in three ways. First, the rule requires more than similarity: a conversation counts as a retrial only if it comes from the same hashed IP, its estimated arrival time is after the earlier conversation, and its first prompt has cosine similarity above the threshold (Section B.4). Second, we test whether the conclusions depend on this rule by varying the threshold (Section C.13). Third, we add ACQB-DNF for delayed and noisy feedback (Section B.8, Algorithm 4), which waits WW rounds, a known upper bound on retrial delay, before updating and corrects labels using supplied error rates. We evaluate it in controlled simulations and on WildChat (Sections C.7--C.12).

  • For threshold sensitivity, ACQB achieves the lowest mean queue length at 0.9950.995 and 0.9990.999. Under exact matching of first prompts, FIFO and RANDOM have lower mean queue length than ACQB. Full results are in Section C.13, Figure 20, and Table 13.
Algorithm0.9950.9950.9990.999Exact matching
ACQB812.83±0.18\mathbf{812.83\pm0.18}922.20±0.25\mathbf{922.20\pm0.25}1764.87±0.331764.87\pm0.33
FIFO966.68±0.00‾\underline{966.68\pm0.00}1034.06±0.00‾\underline{1034.06\pm0.00}1663.53±0.00\mathbf{1663.53\pm0.00}
RANDOM977.72±2.67977.72\pm2.671049.95±2.621049.95\pm2.621673.01±3.47‾\underline{1673.01\pm3.47}
LIFO1544.05±0.001544.05\pm0.001612.35±0.001612.35\pm0.001868.12±0.001868.12\pm0.00
  • For delayed feedback, ACQB-DNF uses a response to update the likelihood and VtV_t only after observing the next WW rounds. It records rejection if a retrial is identified within this period and acceptance otherwise, and serves other queries while waiting. This follows the idea of learning from available feedback in Joulani et al. (2013) [2].

  • For unobserved retrials (or noisy feedback), ACQB-DNF corrects labels using supplied error rates. We include missed retrials in ρ0\rho_0, the probability of recording rejection as acceptance. Let ρ1\rho_1 be the probability of recording acceptance as rejection, with ρ0+ρ1<1\rho_0+\rho_1<1. For a response served by LLM jij_i at round ii, we replace the observed acceptance label y~i,ji\widetilde y_{i,j_i} with y‾i,ji=y~i,ji−ρ01−ρ0−ρ1\overline y_{i,j_i}=\frac{\widetilde y_{i,j_i}-\rho_0}{1-\rho_0-\rho_1}. Following Natarajan et al. (2013, Lemma 1) [3], this gives an unbiased logistic loss under this error model.

  • For evaluation, ACQB-DNF has lower cumulative regret and queue length regret in all three simulation settings below. Retrial delays are uniform on 1,…,W\\{1,\ldots,W\\}. On WildChat, it also achieves the lowest mean queue length among all five methods with delayed retrials, including when 20% are recorded as new queries. Full results are in Sections C.7--C.12 and Figures 14--19.

Controlled simulation with W=20W=20 and λ=0.6\lambda=0.6.

Error rates (ρ0,ρ1)(\rho_0,\rho_1)MetricACQBACQB-DNF
(0,0)(0,0)Cumulative regret5197.20±198.73‾\underline{5197.20\pm198.73}2760.45±23.37\mathbf{2760.45\pm23.37}
(0,0)(0,0)Queue length regret911.13±89.79‾\underline{911.13\pm89.79}22.40±4.80\mathbf{22.40\pm4.80}
(0.1,0.2)(0.1,0.2)Cumulative regret5548.45±222.99‾\underline{5548.45\pm222.99}3057.03±27.16\mathbf{3057.03\pm27.16}
(0.1,0.2)(0.1,0.2)Queue length regret1718.90±66.96‾\underline{1718.90\pm66.96}930.46±41.43\mathbf{930.46\pm41.43}
(0.2,0.1)(0.2,0.1)Cumulative regret5567.30±167.53‾\underline{5567.30\pm167.53}3546.25±35.86\mathbf{3546.25\pm35.86}
(0.2,0.1)(0.2,0.1)Queue length regret487.55±57.13‾\underline{487.55\pm57.13}19.23±4.17\mathbf{19.23\pm4.17}

Mean WildChat queue length at W=20W=20.

AlgorithmDelayed retrialsDelayed retrials, 20% recorded as new
ACQB1548.16±1.031548.16\pm1.031506.61±1.681506.61\pm1.68
ACQB-DNF814.43±0.21\mathbf{814.43\pm0.21}829.92±1.69\mathbf{829.92\pm1.69}
FIFO967.05±0.12‾\underline{967.05\pm0.12}967.05±0.12‾\underline{967.05\pm0.12}
RANDOM979.00±2.69979.00\pm2.69979.00±2.69979.00\pm2.69
LIFO1353.34±6.701353.34\pm6.701353.34±6.701353.34\pm6.70

References

[1] Bae and Lee, "Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret", arXiv, 2026.

[2] Joulani et al., "Online Learning under Delayed Feedback", ICML, 2013.

[3] Natarajan et al., "Learning with Noisy Labels", NeurIPS, 2013.

Dear Reviewer iHuc, Thank you for your careful review. We have addressed each of your comments and questions in our rebuttal and would be grateful if you could take a look when you have a chance. Thanks, Authors

Reviewer_uXN6OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CQB-MNL models joint LLM routing and scheduling with user retrials as multinomial-logit feedback. ACQB combines Thompson sampling with arrival-triggered exploration, and the paper derives routing and queue-length regret bounds. ACQB uses disjoint parameters in the synthetic and offline-routing simulations, while ACQB-CL is evaluated on the offline routing datasets. A separate fixed-model WildChat replay evaluates scheduling.

Critical strengths
  1. Jointly modeling routing, scheduling, and retrial-induced congestion addresses an important limitation of evaluating LLM routing independently of queue dynamics.
  2. Arrival-triggered exploration provides an anytime design, supported by detailed regret analysis and experiments with multiple baselines and scheduling/exploration ablations.
Critical weaknesses
  1. The choice of Thompson sampling needs stronger justification. Section 3 states that replacing it with UCB improves both regret bounds, but no contextual MNL-UCB comparison with the same arrival-triggered exploration is reported.
  2. The specific contribution of contrastive learning is not isolated. ACQB-CL is not compared with direct utility-prediction pretraining using the same offline labels, projection architecture, and ACQB backend, leaving the benefit of the objective in Section 4.2 unclear.
  3. The guarantees for the disjoint extension need justification. Remark 7 establishes a model reparameterization, but updating only the parameter blocks in the current assortment need not recover Algorithm 1's joint regularized MLE when K > 1, because historical MNL likelihood terms couple model parameters.
  4. The link to resource-constrained LLM serving needs clearer qualification. Section 2 assumes one query-service attempt per slot and measures congestion by the number of pending queries, without modeling query/model-dependent generation times or individual LLM service capacities.
  5. Routing gains are not isolated on the offline datasets. Section 5.2 pairs offline routers with FIFO while ACQB jointly schedules and routes; the synthetic scheduling ablation in Figure 3 does not replace a comparison using the same scheduler on these datasets.
  6. The supplied WildChat implementation uses future outcome information. ACQB receives total/remaining chain length and terminal-node status before service, although terminal status determines departure, undermining the online interpretation of Section 5.3 (real_mnl_acqb_policy.py; real_queue_env.py).
  7. The simulated departure probabilities are specified inconsistently. Section 5.2 and Appendix B.5 normalize utilities across models separately for each prompt, whereas queue_env.py uses extrema over the entire prompt-model matrix passed to the environment, leaving the actual experimental environment unclear.
Questions for authors
  1. What advantage does Thompson sampling offer over contextual MNL-UCB under the same arrival-triggered exploration and joint selection rule?
  2. Does ACQB-CL outperform a utility-regression projection trained with the same offline data and architecture while keeping the ACQB backend fixed?
  3. What argument extends the regret guarantees to updates restricted to the parameter blocks in the current assortment when K > 1?
  4. Under what serving conditions is the one-slot abstraction appropriate, and how do the scheduling gains change with heterogeneous service times?
  5. Do the routing gains persist when ACQB and the offline routers use the same scheduling policy on the offline datasets?
  6. Did the supplied implementation produce the reported WildChat results, and do the gains persist after removing realized total/remaining chain length and terminal-node indicators from the scheduler's inputs?
  7. Which normalization produced the reported results, and how sensitive are the conclusions to this choice?
3 comments

[W1] The choice of Thompson sampling needs stronger justification. Section 3 states that replacing it with UCB improves both regret bounds, but no contextual MNL-UCB comparison with the same arrival-triggered exploration is reported.

[Q1] What advantage does Thompson sampling offer over contextual MNL-UCB under the same arrival-triggered exploration and joint selection rule?

We added a comparison between TS and UCB in Section C.4. Although UCB has better dependence on dd (Section 3), we chose TS for its strong empirical performance reported in prior work (Oh and Iyengar, 2019 [1]). Under the same exploration and selection rules, neither method consistently outperforms the other, confirming that both can be used in our framework. Representative results are below, with full results in Figure 11 and Table 9.

Dataset, KKAlgorithmCumulative regretQueue length regret
SPROUT, 11ACQB-TS237.89±34.30‾\underline{237.89\pm34.30}3.13±1.30‾\underline{3.13\pm1.30}
SPROUT, 11MNL-UCB208.69±31.55\mathbf{208.69\pm31.55}2.18±0.63\mathbf{2.18\pm0.63}
EmbedLLM, 22ACQB-TS61.49±11.01\mathbf{61.49\pm11.01}1.14±0.50\mathbf{1.14\pm0.50}
EmbedLLM, 22MNL-UCB80.49±14.44‾\underline{80.49\pm14.44}1.51±0.50‾\underline{1.51\pm0.50}

[W2] The specific contribution of contrastive learning is not isolated. ACQB-CL is not compared with direct utility-prediction pretraining using the same offline labels, projection architecture, and ACQB backend, leaving the benefit of the objective in Section 4.2 unclear.

[Q2] Does ACQB-CL outperform a utility-regression projection trained with the same offline data and architecture while keeping the ACQB backend fixed?

We added a comparison between contrastive learning and utility regression in Section C.6. ACQB-CL outperforms utility regression in both cumulative regret and queue length regret on EmbedLLM. Utility regression achieves competitive performance on SPROUT and RouterBench and can also be a useful option for pretraining the query representation. Representative results are shown below, with full results in Figure 13 and Table 10.

DatasetAlgorithmCumulative regretQueue length regret
SPROUTACQB-CL1039.86±90.45‾\underline{1039.86\pm90.45}66.94±25.68‾\underline{66.94\pm25.68}
SPROUTUtility regression1026.25±75.74\mathbf{1026.25\pm75.74}59.43±18.90\mathbf{59.43\pm18.90}
EmbedLLMACQB-CL3056.99±18.35\mathbf{3056.99\pm18.35}74.98±10.28\mathbf{74.98\pm10.28}
EmbedLLMUtility regression3117.01±19.95‾\underline{3117.01\pm19.95}106.10±12.18‾\underline{106.10\pm12.18}

[W3] The guarantees for the disjoint extension need justification. Remark 7 establishes a model reparameterization, but updating only the parameter blocks in the current assortment need not recover Algorithm 1's joint regularized MLE when K>1K>1, because historical MNL likelihood terms couple model parameters.

[Q3] What argument extends the regret guarantees to updates restricted to the parameter blocks in the current assortment when K>1K>1?

We thank the reviewer for pointing out that the original Remark 7 did not justify the updates in Algorithm 2. We have clarified in Remark 8 in Section B.1 that our regret guarantees hold for the disjoint model when the joint constrained MLE is used, and the added experiments in Sections C.4--C.5 use this estimator.

  • Under Assumptions 1--4, Algorithm 1 applied to the vectorized features of Remark 7 retains its regret guarantees with dd replaced by dNdN. The added experiments use this joint constrained MLE, including for K=2K=2 (Section B.6).

  • The separate updates and confidence radii in Algorithm 2 are a simpler per-LLM implementation that our analysis does not cover. To inherit these guarantees, Algorithm 2 would need to compute the joint constrained MLE Θ^t=arg,min⁡∥vec(Θ)∥2≤SLt(Θ)\widehat\Theta_t=\operatorname{arg\\,min}_{\lVert\text{vec}(\Theta)\rVert_2\leq S}\mathcal L_t(\Theta) over all LLM parameters, and set αt,j=αt\alpha_{t,j}=\alpha_t for every LLM jj, using the confidence radius of Algorithm 1 with dd replaced by dNdN. These changes implement Algorithm 1 in the disjoint model.

  • When K>1K>1, updating only the selected LLM parameters need not recover this joint MLE, as the reviewer notes, because the historical MNL likelihood couples the LLM parameters.

[W4] The link to resource-constrained LLM serving needs clearer qualification. Section 2 assumes one query-service attempt per slot and measures congestion by the number of pending queries, without modeling query/model-dependent generation times or individual LLM service capacities.

[Q4] Under what serving conditions is the one-slot abstraction appropriate, and how do the scheduling gains change with heterogeneous service times?

The one-slot model in Section 2 is appropriate when service attempts take approximately equal time and the system serves one query with its selected LLM assortment per slot. Our results concern congestion from retrials under this assumption. We have not evaluated query- or model-dependent service times or separate LLM service capacities, so the scheduling gains in these settings remain an open question.

[W5] Routing gains are not isolated on the offline datasets. Section 5.2 pairs offline routers with FIFO while ACQB jointly schedules and routes; the synthetic scheduling ablation in Figure 3 does not replace a comparison using the same scheduler on these datasets.

[Q5] Do the routing gains persist when ACQB and the offline routers use the same scheduling policy on the offline datasets?

We added a routing comparison under the same scheduler in Section C.5. The routing gains persist when all methods use FIFO, and ACQB achieves the lowest cumulative regret and queue length regret among all seven methods on all three datasets. The comparison uses prompts from the three offline datasets and feedback sampled from the MNL model (Section B.6). Representative SPROUT results for all baselines are shown below, with full results in Figure 12.

AlgorithmCumulative regretQueue length regret
ACQB250.94±27.81\mathbf{250.94\pm27.81}2.96±0.70\mathbf{2.96\pm0.70}
CARROT750.33±8.30‾\underline{750.33\pm8.30}90.83±10.70‾\underline{90.83\pm10.70}
KNN754.50±8.31754.50\pm8.3194.74±11.3794.74\pm11.37
MLP888.43±6.06888.43\pm6.06151.31±10.81151.31\pm10.81
RouterDC858.02±6.92858.02\pm6.92138.09±11.39138.09\pm11.39
UMR785.21±4.66785.21\pm4.66103.14±9.11103.14\pm9.11
ZERO910.27±4.23910.27\pm4.23163.27±10.76163.27\pm10.76

[W6] The supplied WildChat implementation uses future outcome information. ACQB receives total/remaining chain length and terminal-node status before service, although terminal status determines departure, undermining the online interpretation of Section 5.3 (real_mnl_acqb_policy.py ; real_queue_env.py).

[Q6] Did the supplied implementation produce the reported WildChat results, and do the gains persist after removing realized total/remaining chain length and terminal-node indicators from the scheduler's inputs?

We thank the reviewer for identifying this implementation issue. We removed the total and remaining numbers of attempts and terminal status from the scheduler's inputs and reran the WildChat experiments (Section B.4). The gains persist after removing these inputs, and ACQB still has the lowest mean queue length in the comparison with FIFO, RANDOM, and LIFO at similarity thresholds 0.9950.995 and 0.9990.999. The table below shows the results at threshold 0.9950.995 (Section 5.3, Figure 5); other thresholds are in Section C.13.

AlgorithmMean queue length
ACQB812.83±0.18\mathbf{812.83\pm0.18}
FIFO966.68±0.00‾\underline{966.68\pm0.00}
RANDOM977.72±2.67977.72\pm2.67
LIFO1544.05±0.001544.05\pm0.00

[W7] The simulated departure probabilities are specified inconsistently. Section 5.2 and Appendix B.5 normalize utilities across models separately for each prompt, whereas queue_env.py uses extrema over the entire prompt-model matrix passed to the environment, leaving the actual experimental environment unclear.

[Q7] Which normalization produced the reported results, and how sensitive are the conclusions to this choice?

We thank the reviewer for identifying this inconsistency. We corrected the normalization formula in Sections 5.2 and B.5 to match the implementation. The experiments normalize raw utilities ujraw(ξ)u_j^{\mathrm{raw}}(\xi) using one minimum and maximum across all prompts ξ′\xi' and LLMs kk in the environment, rather than separately for each prompt.

ujnorm(ξ)=ujraw(ξ)−min⁡ξ′,kukraw(ξ′)max⁡ξ′,kukraw(ξ′)−min⁡ξ′,kukraw(ξ′).u_j^{\mathrm{norm}}(\xi)=\frac{u_j^{\mathrm{raw}}(\xi)-\min_{\xi',k}u_k^{\mathrm{raw}}(\xi')}{\max_{\xi',k}u_k^{\mathrm{raw}}(\xi')-\min_{\xi',k}u_k^{\mathrm{raw}}(\xi')}.

The implementation and reported results are unchanged. In the additional FIFO comparison, ACQB also achieves lower cumulative regret and queue length regret than all six offline routers with feedback generated directly from the MNL model, without this normalization (Section C.5, Figure 12).

References

[1] Oh and Iyengar, "Thompson Sampling for Multinomial Logit Contextual Bandits", NeurIPS, 2019.

Dear Reviewer uXN6, Thank you for your careful review. We have addressed each of your comments and questions in our rebuttal and would be grateful if you could take a look when you have a chance. Thanks, Authors

Comments on the paper

1 comment

We apologize for posting our rebuttal later than planned. The additional experiments required more time than we had anticipated. We have carefully addressed each of your comments and questions, and we would appreciate it if you could read our response when you have a chance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.