- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes SLARouter, an online LLM routing method that aims to minimize inference cost while maintaining a target average satisfaction level with limited feedback. It combines single-model exploration, an online satisfaction predictor, and a virtual queue to guide model selection. The authors present theoretical bounds on satisfaction and cost under stated assumptions. Experiments across 11 benchmarks and five LLMs use correctness as a proxy for satisfaction and report cost reductions over existing routing baselines.
Critical strengths
-
The paper addresses a practical problem: reducing LLM routing costs with limited feedback. Its single-model exploration strategy avoids querying every candidate model, reducing exploration overhead.
-
Evaluation across 11 benchmarks and five LLMs shows reported cost savings over several routing baselines while meeting average accuracy targets, providing empirical support across different tasks.
Critical weaknesses
-
The central satisfaction guarantee is not fully established. The step leading to Eq. (A.35) appears to use population cross-entropy as a pointwise bound on individual-request loss. This requires justification, since the resulting high-probability bound is used in Theorem 1.
-
The benefit over simpler policies remains unclear. Table 2 shows a cheaper, more accurate fixed model for each benchmark. For example, on ACPBench, the 70B model achieves 76.7% at 0.304, versus SLARouter’s 70.3% at 0.566. Although selecting these models requires prior information, an equal-feedback-budget baseline that explores and then commits to one model is missing, leaving the practical value of adaptive routing insufficiently demonstrated.
Questions for authors
- Could you justify the step leading to Eq. (A.35), particularly the transition from population loss to a pointwise bound, and clarify its implications for Theorem 1?
- Given the fixed-model results in Table 2, what evidence supports an advantage over an equal-feedback-budget policy that explores and then commits to one model?
- How are request arrivals and feedback delays modeled? Was performance evaluated across different QPS levels and concurrency settings?
3 comments
Response to Reviewer 7CT3 (part 2 of 2)
Q2 (equal-feedback-budget baseline). This part continues part 1 with the experiments. The new Explore-then-Commit learner uses the exploration schedule of SLARouter and receives the same revealed labels for every seed, so its feedback budget equals that of SLARouter. It commits to the cheapest model whose empirical satisfaction reaches after 5 labels. The UCB learner instead serves the cheapest model whose upper confidence bound reaches and re-evaluates this choice at every step. Both learners select a single model and do not use the request text (new section "Baselines and Predictor Training" in the paper). Under the per-benchmark targets of Table 2, Explore-then-Commit costs \ 1.615 ± 0.063 at 75.1 ± 0.2%. SLARouter is cheaper on 6 benchmarks and Explore-then-Commit on 5. We agree with the observation behind the question. If every benchmark carries its own target, Llama 3.3 70B meets on all 11 benchmarks, and a learner that identifies it is close to optimal. The hindsight per-request oracle shows that routing has headroom on these streams (e.g., \ 0.304 for the 70B model on ACPBench). SLARouter does not capture this headroom there. Exploration alone accounts for 12% (MMLU) to 73% (GPQA) of its operating cost (new section "Relative Cost Overhead" in the paper).
Per-request routing pays off if a single SLA covers heterogeneous traffic. On the pooled stream of the 11 benchmarks with a single target (28,737 requests, three seeds, ten for the two bandits), the results are as follows:
- SLARouter reaches 74.9 ± 0.5% at $0.851 ± 0.075, the lowest mean cost of all routers.
- Explore-then-Commit reaches 74.9 ± 0.9% at $2.207 ± 0.267, UCB reaches 75.1 ± 0.4% at \ 1.436 ± 0.194.
- CARROT and the Causal router reach 75.0 ± 2.4% and 74.8 ± 1.7% at \ 1.087 ± 0.138. Both need a training set labeled by every model, and the cost of this one-time training is not included. The difference between SLARouter and CARROT is about 1.3 combined standard deviations.
- Among the single models, only the 35B, 70B, and 122B models meet the target, and the cheapest of them is the 70B model at \$ 1.189 and 79.0%, which is 40% above SLARouter.
A learner that serves a single model on its exploitation steps can meet the target on this stream only with these three models. SLARouter is below the cost of all three models, because its predictor sends the requests that a cheap model solves to that model, and the single queue lets the resulting surplus offset the requests that need a larger model.
Q3 (arrivals, delays, and load). Requests arrive sequentially (IID across time slots), and the queue is indexed by request instead of wall-clock time. In Table 2, the label of a served request, if revealed, arrives before the next request. The new section "Feedback Delay" in the paper draws the delay from an exponential distribution with a mean of 5, 20, or 50 requests. On ACPBench, GPQA, and WinoGrande, the cost and the satisfaction of SLARouter stay within a standard deviation of the case without delay. We did not evaluate QPS or concurrency. The decision for a request depends only on the queue and the predictor state, so concurrent requests are routed with a state that lags by the requests in flight, which is the situation that the delay experiment emulates. The routing latency is a ModernBERT forward pass of 39 to 157 ms per request, and a predictor update takes 2.0 s per batch of 16 labels on a CPU, which amortizes to 3.1 ms per request on the pooled stream (new section "Relative Cost Overhead" in the paper). The revised paper lists load experiments as a limitation.
We hope that these answers address the concerns of the reviewer, and we are happy to provide further details.
Thank you for correcting the step leading to Eq. (A.35) and for adding the Explore-then-Commit comparison with the same feedback budget. This answers my baseline question. Under the per-benchmark targets, the two methods have nearly identical total costs. On the pooled stream, both reach 74.9% mean satisfaction, while SLARouter costs $0.851 compared with $2.207 for Explore-then-Commit.
My main remaining question concerns the conditional error bound in Theorems 1 and 2. I appreciate that the revision states this assumption explicitly. I understand that the model used for exploration is sampled independently of the virtual queue. However, the trained predictor and the queue both depend on past observations. Could you clarify why you expect the error bound to hold for the online predictor after conditioning on the queue state?
I also appreciate the delayed-feedback experiments. If feasible, could you use the existing serving simulator to compare the two methods at two or three request rates? Reporting satisfaction and simulated end-to-end latency would help clarify how they behave as load increases.
Given the remaining uncertainty about how the theoretical guarantees apply to the online predictor, I maintain my weak-reject recommendation.
Response to Reviewer 7CT3 (part 1 of 2)
We thank the reviewer for their constructive review. Our answers in brief are as follows:
Q1 in detail. Lemma 2 has two statements. The first statement bounds the expected error, and its proof is correct. For a 0/1 label, ∣s^−s∣≤−log(1−∣s^−s∣), which is the cross-entropy of the request, and at is independent of zk, so E[Wt]≤M,E[F(zk)]≤Wˉt for Wt:=maxm∣s^m,t−sm,t∣ and Wˉt:=βFmin+O(β(1+σ2)/(t3/4ϕ)). The second statement applied Markov's inequality to F(zk)−Fmin in (A.33) and then bounded the loss of request t by MF(zk) in (A.35) of the submitted version. As the reviewer notes, this bound holds in expectation over at and fails for an individual request. Markov's inequality applied to the nonnegative variable Wt instead gives, with probability at least 1−δ, Wt≤δWˉt=δβFmin+O(t3/4ϕ,δβ(1+σ2)). The transient is the same as in the submission, and the floor is now divided by δ. Theorem 1 is the only result that uses the second statement. Its proof takes δ=ρ with ρ=(q−α−(1−ϕ)βFmin)/2 and needs Wt≤1/3 on this event for t≥ψ, i.e., Wˉt≤ρ/3. The condition βFmin<1/3 of Assumption 3 therefore becomes βFmin<ρ/3, which is equivalent to (7−ϕ)βFmin<q−α and implies both conditions of the submitted Assumption 3. The warm-up becomes ψ=Θ(max(β(1+σ2)/(ϕ(ρ/3−βFmin)))4/3,,c4/ρ4). The second term accounts for exploration steps, which serve a uniformly random model and which the submitted drift step treated as exploitation steps. The bounds of Theorem 1 are unchanged. The proof of Theorem 2 gains an exploration term of order T−1/4 that the stated bound absorbs, and Corollary 1 is unchanged. The drift arguments of Theorems 1 and 2 use the first statement conditionally on the queue, i.e., E[Wt∣Qt]≤Wˉt. The revised paper states this as an assumption and lists it as a limitation. It holds if the predictor error at request t is independent of the queue length. The training scheme supports this independence, since the predictor learns only from exploration samples, whose model is drawn uniformly and independently of the queue, and since the request at is independent of the past. The analysis of MESS+ uses the predictor error in expectation in the same way. A new section in the paper, "Extended Analysis for Stochastic Satisfaction", measures the error against the conditional satisfaction probability and replaces the conditional bound by an assumed tail bound on the excess loss of the predictor, which we do not prove. Its guarantees are correct but likely too conservative to guide the choice of the parameters, so the experiments use the expressions of the main text. The experiments support the conclusion of Theorem 1 in practice, since SLARouter meets α on all 11 benchmarks of Table 2 with a predictor trained online from sparse labels, and the queue settles after a warm-up (new section "Queue Behavior and Statistics" in the paper).