acceptodds
Under review as a conference paper at ICLR 2027

Cost-Optimal LLM Routing with Limited Feedback under User Satisfaction Guarantees

Abstract

Inference costs for large language model (LLM) applications are rapidly growing, driven by surging demand and rising infrastructure cost. Users expect high-quality responses, and in commercial settings this is formally codified in Service Level Agreements (SLAs), creating a fundamental tension between cost and quality. Recent progress on cost-aware LLM request routing has shown potential to resolve this tension, but existing approaches rely on complete feedback signals, offline training, extensive per-workload tuning, and most lack SLA guarantees or inference-time adaptivity. We introduce SLARouter, an online routing algorithm that learns a cost-optimal policy from the sparse, one-sided user feedback available in production systems. SLARouter provides theoretical guarantees for both cost optimality and strict SLA compliance. Experiments across a wide range of LLM benchmarks using a mixed-family model zoo show that SLARouter satisfies SLA constraints without the need for per-benchmark tuning, reducing operating cost by an average of over existing baselines. We further introduce a data-driven method that optimizes the warm-up cost of SLARouter, further reducing the cost for budget-constrained workloads as well as an LLM-judge-based mechanism that ensures smooth predictor training over time.

Primary area:
optimization
Keywords:
routing, optimization, LLM, inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_7CT3OpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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?
  2. 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?
  3. How are request arrivals and feedback delays modeled? Was performance evaluated across different QPS levels and concurrency settings?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 7CT3 (part 1 of 2)

We thank the reviewer for their constructive review. Our answers in brief are as follows:

  • Q1. The reviewer is right that the step leading to (A.35) uses the population cross-entropy as a bound on the loss of a single request. Applying Markov's inequality to the error of the request itself gives a valid high-probability bound, in which the floor βFmin⁡\beta F_{\min} is also divided by δ\delta. For Theorem 1, this changes a constant in Assumption 3 and in the warm-up ψ\psi, and the bounds of the theorem keep their form.
  • Q2. We added an Explore-then-Commit learner with the same feedback budget as SLARouter, together with a UCB learner. Under the per-benchmark targets, Explore-then-Commit and SLARouter cost the same in total. Under a single target on mixed traffic, SLARouter is cheaper than both learners and than every single model that meets the target.
  • Q3. Requests arrive as a sequential stream in a randomly shuffled order (IID). We added experiments with delayed feedback, and we did not evaluate QPS or concurrency.

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∣)|\hat s-s|\le-\log(1-|\hat s-s|), which is the cross-entropy of the request, and ata_t is independent of zk\mathbf z_k, so E[Wt]≤M,E[F(zk)]≤Wˉt\mathbb E[W_t]\le M\\,\mathbb E[F(\mathbf z_k)]\le \bar W_t for Wt:=max⁡m∣s^m,t−sm,t∣W_t:=\max_m|\hat s_{m,t}-s_{m,t}| and Wˉt:=βFmin⁡+O(β(1+σ2)/(t3/4ϕ))\bar W_t:=\beta F_{\min}+O(\beta(1+\sigma^2)/(t^{3/4}\phi)). The second statement applied Markov's inequality to F(zk)−Fmin⁡F(\mathbf z_k)-F_{\min} in (A.33) and then bounded the loss of request tt by MF(zk)M F(\mathbf z_k) in (A.35) of the submitted version. As the reviewer notes, this bound holds in expectation over ata_t and fails for an individual request. Markov's inequality applied to the nonnegative variable WtW_t instead gives, with probability at least 1−δ1-\delta, Wt≤Wˉtδ=βFmin⁡δ+O(β(1+σ2)t3/4ϕ,δ).W_t\le\frac{\bar W_t}{\delta}=\frac{\beta F_{\min}}{\delta}+O\Big(\frac{\beta(1+\sigma^2)}{t^{3/4}\phi\\,\delta}\Big). The transient is the same as in the submission, and the floor is now divided by δ\delta. Theorem 1 is the only result that uses the second statement. Its proof takes δ=ρ\delta=\rho with ρ=(q−α−(1−ϕ)βFmin⁡)/2\rho=(q-\alpha-(1-\phi)\beta F_{\min})/2 and needs Wt≤1/3W_t\le1/3 on this event for t≥ψt\ge\psi, i.e., Wˉt≤ρ/3\bar W_t\le\rho/3. The condition βFmin⁡<1/3\beta F_{\min}<1/3 of Assumption 3 therefore becomes βFmin⁡<ρ/3\beta F_{\min}<\rho/3, which is equivalent to (7−ϕ)βFmin⁡<q−α(7-\phi)\beta F_{\min}<q-\alpha and implies both conditions of the submitted Assumption 3. The warm-up becomes ψ=Θ(max⁡(β(1+σ2)/(ϕ(ρ/3−βFmin⁡)))4/3,,c4/ρ4)\psi=\Theta\big(\max\\{(\beta(1+\sigma^2)/(\phi(\rho/3-\beta F_{\min})))^{4/3},\\,c^4/\rho^4\\}\big). 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/4T^{-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\mathbb E[W_t\mid Q_t]\le \bar W_t. The revised paper states this as an assumption and lists it as a limitation. It holds if the predictor error at request tt 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 ata_t 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 α\alpha 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).

AuthorsOpenReview ↗

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 pt=min⁡(1,c,t−1/4)p_t=\min(1,c\\,t^{-1/4}) 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 α\alpha after 5 labels. The UCB learner instead serves the cheapest model whose upper confidence bound reaches α\alpha 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.614±0.042intotalat75.0±0.1 1.614 ± 0.042 in total at 75.0 ± 0.1%, and SLARouter 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 α\alpha 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.066against 0.066 against \\ 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 α=74.6\alpha=74.6\\% (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.680±0.171,andMESS+reaches75.1±3.0 1.680 ± 0.171, and MESS+ reaches 75.1 ± 3.0% at \\ 1.436 ± 0.194.
  • CARROT and the Causal router reach 75.0 ± 2.4% and 74.8 ± 1.7% at \1.006±0.094and 1.006 ± 0.094 and \\ 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.

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

This paper introduce SLARouter, a online LLM routing system that route requests between different LLMs to minimize the cost while guarantee user satisfaction. The signal from users are sparse feedback. It use Lyapunov drift plus penalty of MESS+ for satisfaction predictor and virtue queue when missing feedback.

The theory part proved an O(1/(ϕt 3/4 )) predictor error bound, a queue bound, constraint violation converging to a floor and a cost gap. Experiments were conducted with 11 benchmarks with 5 models pool. Compared with baseline CARROT and causal LLM routing, we can see 10% and 18% cost saving.

Critical strengths
  1. Relevant problem. Cost-aware routing under quality targets with sparse, partial feedback is a practically relevant problem, and the paper frames it clearly.
  2. Simple, interpretable algorithm. The method is a direct extension of drift-plus-penalty. In the full-feedback case (φ = 1) the analysis recovers the MESS+ result.
  3. Useful judge analysis. The study reports false-positive and false-negative rates with and without reasoning, not just agreement. Reproducibility. Code and the data pipeline are released.
Critical weaknesses
  1. Oracle cost information at decision time. In the released code (router_lib/routers/mess_plus/slarouter.py, _select_model → BaseRouter.compute_cost), the routing score uses each candidate's realized prompt and completion token counts for the current request, read from pre-collected logs. Output length is unknown before generation and observable only for the invoked model. It is also correlated with quality: expensive models may solve a task in fewer tokens, and failed responses are often longer. This contradicts the paper's one-sided-observation premise. The formulation treats C as known and exogenous. A faithful formulation would use a cost predictor, with its error reflected in the analysis. Additionally, ΔC for the data-driven V is computed from dataset-wide means, including future requests.
  2. W1. Routing is not shown to beat the per-benchmark cheapest compliant single model; in fact it is consistently more expensive. Because α is set per benchmark, the relevant comparison is the cheapest single model that meets α on that benchmark. From Table 2 such a model exists on every benchmark, and it is cheaper than SLARouter (and all routers) in all 11 cases. Averaged over the 11 benchmarks, the per-benchmark best single model costs about $0.108, versus $0.258 for SLARouter (about 2.4×). The statement that "no single model achieves α across all benchmarks" compares against a single average α, which is not the problem the router actually solves. A natural and missing baseline is a simple online bandit over fixed models (e.g., explore-then-commit or UCB with a constraint), which would likely identify these models with far less exploration cost than uniform exploration at rate t−1/4t^{-1/4} (roughly 20% to 30% of requests at these horizons).
  3. "Satisfaction" and "SLA" are not modeled realistically, and practical claims are not supported. Satisfaction is benchmark correctness, and feedback is IID-simulated. Graded, noisy, or negativity-biased feedback, which the paper itself motivates, is never tested. Production SLAs usually concern latency and availability, which are absent here. The paper repeatedly claims production-realistic operation, yet all experiments are offline replays of logged benchmark outputs. There is no deployment, no real user feedback, and no measurement of router overhead (a ModernBERT forward pass per request), multi-turn or session handling, or load. The judge is a reasoning-enabled GPT-5.4, likely more expensive per call than the routed models, but its cost is not included in operating cost. The repository contains a load-aware serving simulator (serving.py) and a feedback-delay scheduler (feedback_delay.py), but no corresponding results are reported.
Questions for authors
  1. Please add the per-benchmark cheapest-compliant-single-model baseline and a constrained bandit baseline over fixed models. Why should per-request routing be preferred here?
  2. Please confirm whether _select_model uses realized per-request token counts for all candidates, and whether the baselines receive the same information. What are the results with predicted or expected costs?
  3. Please report per-head predictor AUC and calibration, and the exploitation-phase routing distribution over time. How often is QtQ_t=0, and how often does the cost term change the decision?
  4. How are the high-probability step in Lemma 2 and the conditioning issues in Theorems 1–2 resolved? What is the resulting condition on FminF_{min}, and can it hold under stochastic satisfaction?
5 comments
AuthorsOpenReview ↗

Response to Reviewer 93n3 (part 1 of 4)

We thank the reviewer for the constructive feedback on our paper, and the released code. Our answers in brief are as follows:

  • W1/Q2. We confirm this point. The submitted code let every method, including the baselines, decide with realized token counts. All methods now decide with one-sided cost estimates, and the believed and realized costs differ by at most \0.009overthe24pairsofmethodandbenchmarkthatwecompared.Thedata−driven0.009 over the 24 pairs of method and benchmark that we compared. The data-drivenV$ uses future requests, and the paper now says so.
  • W2/Q1. This is true. Under per-benchmark targets, the cheapest compliant single model is cheaper than every router. We added Explore-then-Commit and UCB learners and a single-SLA experiment on mixed traffic, on which SLARouter is cheaper than every single model that meets the target.
  • W3. We removed the claims of production realism and added the judge cost, feedback delay, label noise, and a non-stationary stream. Latency and availability SLAs are outside our scope, and the paper now states this (part 3).
  • Q3. We report how frequently the queue is empty and how frequently the cost term changes the decision, and we add the per-head AUC and calibration error on three benchmarks (part 3).
  • Q4. The step (A.35) needs Markov's inequality applied to the error of the individual request, which changes a constant in Assumption 3. Part 4 explains the derivation, the conditioning, the resulting condition on Fmin⁡F_{\min}, and why this condition requires satisfaction that is close to deterministic, which the revised paper states as a limitation and which the experiments do not need. A new section in the paper extends the analysis to stochastic satisfaction.

W1/Q2 (cost information) in detail. The reviewer is right that _select_model used the realized prompt and completion token counts of every candidate, taken from the logs, and that the baselines received the same information. In the revision, every method decides with the same one-sided estimate, namely the prompt token count under the tokenizer of the candidate, which is known before generation, and a running mean of the completion lengths observed for that model on the requests that it served. The reported operating cost is the realized cost of the served model, including exploration. The new section "Cost Mode Comparison" in the paper compares the believed and the realized cost on ACPBench, GSM8K, GPQA, and WinoGrande over 24 pairs of method and benchmark. The gap is at most $0.009 (e.g., $0.473 ± 0.028 believed against $0.480 ± 0.040 realized for SLARouter on ACPBench), and the ranking of the methods is the same under both costs. On GPQA and WinoGrande the gap is zero, since the output length on these benchmarks is known before generation.

We agree that the analysis should reflect the estimate, and it extends directly. If the estimate satisfies ∣C^m,t−E[Cm,t∣at]∣≤εC|\hat C_{m,t}-\mathbb E[C_{m,t}\mid a_t]|\le\varepsilon_C for every model, then Theorem 2 holds with an additional term 2εC2\varepsilon_C, because the cost enters the proof only through the comparison of the decision of the router with the stationary policy. Theorem 1 holds with ΔC\Delta_C taken over the estimated costs. The revised paper states this as a remark after the proof of Theorem 2.

The reviewer is also right about ΔC\Delta C in the data-driven VV. It averages over the whole benchmark, including requests that have not arrived, so this variant is not online, and the revised paper states this. The main results in Table 2 use a fixed VV and do not depend on ΔC\Delta C. We now present the rule as a calibration tool that is applied once data about model capability has been collected, separate from the online algorithm (footnote in Section 4).

AuthorsOpenReview ↗

Response to Reviewer 93n3 (part 2 of 4)

W2/Q1 (cheapest compliant single model and bandit baselines). This part continues from part 1 with the comparison against fixed models, where we agree with the analysis of the reviewer. In the revised Table 2, Llama 3.3 70B meets α\alpha on all 11 benchmarks at a total cost of \1.189,whereasSLARoutercosts 1.189, whereas SLARouter costs \\ 1.615 ± 0.063 and the other routers cost between \1.614±0.042(Explore−then−Commit)and 1.614 ± 0.042 (Explore-then-Commit) and \\ 2.279 ± 0.081 (MESS+). The cheapest compliant model per benchmark costs \1.150intotal.Ourstatementthatasinglemodelcannotmeet1.150 in total. Our statement that a single model cannot meet\alphaoneverybenchmarkcomparedthemodelsagainstasingleaverageon every benchmark compared the models against a single average\alpha$, as the reviewer notes, and we removed it.

We added the two baselines that the reviewer proposes (new section "Baselines and Predictor Training" in the paper):

  • Explore-then-Commit commits to the cheapest model whose empirical satisfaction reaches α\alpha after 5 labels.
  • UCB serves the cheapest model whose upper confidence bound reaches α\alpha and re-evaluates this choice at every step.

Both learners use the exploration schedule of SLARouter and the same revealed labels for every seed, so the comparison isolates the predictor and the queue. Under per-benchmark targets their totals are $1.614 ± 0.042 and $1.684 ± 0.065, at a satisfaction of 75.0 ± 0.1% for both learners.

Why per-request routing. Under per-benchmark targets, our results do not favor per-request routing over a fixed model. A fixed model is cheaper if the cheapest compliant model is known in advance, and a fixed-model learner is competitive if it is unknown. The revised paper states this. Per-request routing pays off if a single SLA covers heterogeneous traffic, e.g., an endpoint that serves several workloads under a single agreement. On the pooled stream of the 11 benchmarks with a single target α=74.6\alpha=74.6\\% (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,UCBreaches75.1±0.4 2.207 ± 0.267, UCB reaches 75.1 ± 0.4% at \\ 1.680 ± 0.171, and MESS+ reaches 75.1 ± 3.0% at \$ 1.436 ± 0.194.
  • CARROT and the Causal router cost \1.006±0.094and 1.006 ± 0.094 and \\ 1.087 ± 0.138, without the one-time cost of their training (new section "Relative Cost Overhead" in the paper).
  • The single models that meet the target cost \1.189(70B), 1.189 (70B), \\ 2.226 (35B), and \$ 4.289 (122B), while the 2B and 8B models reach 57.4% and 67.8%. SLARouter is 28% below the 70B model.

The best fixed model per benchmark costs \0.617andtheper−requestoraclecosts 0.617 and the per-request oracle costs \\ 0.225, so SLARouter remains \0.23abovetheformerand 0.23 above the former and \\ 0.63 above the latter.

Exploration cost. The reviewer estimates that pt=min⁡(1,c,t−1/4)p_t=\min(1,c\\,t^{-1/4}) explores on 20% to 30% of the requests at these horizons, which holds for the smaller benchmarks. With our setting c=1.0c=1.0, 14% (MMLU) to 29% (GPQA) of the steps explore. The submitted text stated c=0.1c=0.1 by mistake. The section "Relative Cost Overhead" in the paper reports the share of the operating cost spent on exploration for every method and benchmark, which lies between 12% and 73% for SLARouter. A bandit with its own exploration rule can explore less than our shared schedule, and under per-benchmark targets its cost approaches the 70B row of Table 2. On the pooled stream, the cost of the 70B model bounds from below every learner that serves a single model, and SLARouter is below this bound.

AuthorsOpenReview ↗

Response to Reviewer 93n3 (part 3 of 4)

W3 (satisfaction, SLA, and realism).

  • Claims. We removed the statements that the experiments are production-realistic. The paper now states that all results are offline replays of benchmark data with simulated or judge-based feedback, and that SLARouter enforces a satisfaction target without latency or availability targets (new section "Limitations and Scope" in the paper).
  • Feedback behavior. The revised paper covers delayed feedback with a mean delay of up to 50 requests and symmetric label noise with up to 20% of the revealed labels flipped. On ACPBench, GPQA, and WinoGrande, the cost and the satisfaction of SLARouter stay within a standard deviation of the case without delay or noise. We also test negativity-biased feedback (reveal probability 0.4 for negative and 0.05 for positive labels) on the same three benchmarks. Biased labels push satisfaction 4.7 and 5.8 points above α on ACPBench and GPQA at 26% and 9% higher cost, and 1.4 points below α on WinoGrande at 15% higher cost. Inverse propensity weighting partly mitigates this on ACPBench (1.5 points above α, lower cost) but does not generally improve performance, and WinoGrande stays below α in both variants.
  • Stochastic and graded satisfaction. The guarantees of the main text require satisfaction that is close to deterministic given the request (part 4), and the new section "Extended Analysis for Stochastic Satisfaction" in the paper removes this requirement with more conservative constants. The algorithm itself does not require it, as the label-noise experiment above shows with randomly flipped labels. Graded feedback in [0,1][0,1] enters the queue update and the cross-entropy loss without a change of the algorithm, and we did not evaluate it.
  • Judge cost. The section "LLM Judge Feedback" in the paper (paragraph "Cost") reports the judge calls, the tokens, and the API cost. At a target feedback rate of 20%, the judge costs $0.747 ± 0.091 on ACPBench and \0.116±0.017onGPQA,againstanoperatingcostwithjudgefeedbackof 0.116 ± 0.017 on GPQA, against an operating cost with judge feedback of \\ 0.482 ± 0.027 and \$ 0.059 ± 0.009 (155% and 197%). The estimate of the reviewer is therefore correct, and the paper now states that the judge removes the burden on users but adds API cost.
  • Overhead and load. The section "Relative Cost Overhead" in the paper reports a routing latency of 39 to 157 ms per request for the ModernBERT forward pass and a predictor update time of 2.0 s per batch of 16 labels on a CPU. We did not evaluate load, QPS, or multi-turn sessions. Our experiments rely on offline replay of benchmark data. A live serving setup with six models, including a 122B and a 70B model, is very expensive and not feasible within the rebuttal period, and the revised paper lists this as a limitation.

Q3 (diagnostics).

  • Queue. On the pooled stream, the queue is empty at decision time in 6.3 ± 0.7% of the 28,737 time slots. On exploitation steps, the cost term changes the decision, i.e., the selected model differs from arg⁡max⁡ms^m,t\arg\max_m\hat s_{m,t}, on 9.7 ± 1.6% of the steps on the pooled stream (3.4% on LAMBADA to 40.6% on SciQ, new section "Queue Behavior and Statistics" in the paper).
  • Routing over time. The section "Routing Trajectories Over Time" in the paper shows the cumulative cost and the running satisfaction of every method on ACPBench, GPQA, and WinoGrande, and the non-stationary experiment reports the call ratios at the end of every segment. The model call ratio of each head at five points of the stream is in the table of the next bullet.
  • Predictor. The section "Predictor Exploration, AUC, and Calibration" in the paper reports the ROC AUC, the ECE (10 bins), and the cumulative model call ratio (MCR) of each of the six heads on ACPBench, GPQA, and WinoGrande at five points of the stream, with the per-head values at every checkpoint. We did not run it on the other 8 benchmarks. The table below shows the macro average over the six heads and the MCR of the 70B and 2B models, from the first checkpoint to the end of the stream. The AUC starts near chance and rises as labels arrive, the ECE falls from about 0.14 to about 0.03 to 0.04, and the router shifts calls to the 70B model and away from the 2B model as the predictors improve. The MCR is cumulative from the start of the stream, so it understates the shift in the current routing. The AUC of a head ranks requests only within that head, whereas routing compares different heads, so we report the calibration alongside it.
BenchmarkMacro AUC / ECE, step 0Macro AUC / ECE, endCumulative MCR of 70B (%), first checkpoint → endCumulative MCR of 2B (%), first checkpoint → end
ACPBench0.506 / 0.1470.738 / 0.03923 → 2814 → 12
GPQA0.510 / 0.1400.670 / 0.03119 → 3715 → 8
WinoGrande0.516 / 0.1330.704 / 0.03019 → 4015 → 8
Reviewer_cnqmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents SLARouter, an online LLM routing method that aims to reduce inference costs while maintaining a target average user satisfaction level under limited feedback. The method combines single-model exploration, an online satisfaction predictor, and a virtual queue within a Lyapunov drift-plus-penalty framework. It learns routing decisions from sparse feedback available only for the selected model and uses predicted satisfaction to update the queue when feedback is missing. The authors analyze satisfaction constraints and cost performance under stated assumptions, and introduce data-driven parameter selection and an LLM judge mechanism to supplement feedback. Experiments across multiple benchmarks and a heterogeneous model pool use task correctness as a proxy for satisfaction. The reported results indicate that SLARouter can meet the specified quality targets while reducing operating costs relative to existing routing baselines.

Critical strengths
  1. The problem formulation has practical value. The paper brings inference cost and long-term response quality into a shared model-selection objective under limited feedback, accounting for settings where evaluations are available for only a subset of responses.

  2. The decision mechanism is clear and interpretable. The virtual queue tracks satisfaction shortfalls and uses them to guide model selection, providing an intuitive basis for balancing cost and quality. Under full feedback, the theoretical results connect back to MESS+, maintaining consistency with the established framework.

Critical weaknesses
  1. The current evaluation does not isolate the additional benefit of request-level routing. Table 2 contains a lower-cost single-model option that meets the quality requirement for each benchmark. Although identifying these options requires information that is unavailable initially, the paper does not evaluate a simple policy that learns a suitable model through limited exploration and then continues using it. Consequently, the results do not distinguish gains from adapting model selection to individual requests from gains obtained by identifying a suitable model for the workload.
Questions for authors
  1. With the same feedback budget, does continued routing adaptation outperform selecting a fixed model after exploration? Could the authors include a baseline that first gathers feedback and then selects the least expensive model estimated to meet the quality target, counting exploration calls toward its total cost? Comparing cumulative cost and quality-target attainment over the full request sequence would help establish the conditions under which request-level routing offers an advantage.
2 comments
AuthorsOpenReview ↗

Response to Reviewer cnqm (part 1 of 2)

We thank the reviewer for the constructive review. Our answer in brief is as follows:

  • The revision adds the baseline that the reviewer describes. Explore-then-Commit gathers feedback with the same budget as SLARouter, commits to the cheapest model whose estimated satisfaction reaches α\alpha, and pays for its exploration calls in its total cost. A UCB learner that re-evaluates its choice at every step complements it.
  • Under per-benchmark targets, continued routing does not outperform the fixed model selected after exploration, and Explore-then-Commit and SLARouter cost the same in total.
  • Under a single target on mixed traffic, SLARouter costs \$ 0.851 ± 0.075, the lowest mean cost of all routers and 28% below the cheapest single model that meets the target. The revised paper reports both views.

The baseline. Explore-then-Commit uses the exploration schedule pt=min⁡(1,c,t−1/4)p_t=\min(1,c\\,t^{-1/4}) of SLARouter and receives the same revealed labels for every seed, so its feedback budget equals that of SLARouter. As soon as a model with at least 5 revealed labels reaches an empirical satisfaction of α\alpha, the learner commits to the cheapest such model and serves it on every later exploitation step. Its exploration calls count toward its operating cost. The section "Baselines and Predictor Training" in the paper gives the protocol, and the section "Relative Cost Overhead" reports the share of exploration in the cost of every method.

Per-benchmark targets. The totals over the 11 benchmarks in Table 2 are \1.614±0.042at75.0±0.1 1.614 ± 0.042 at 75.0 ± 0.1% for Explore-then-Commit and \\ 1.615 ± 0.063 at 75.1 ± 0.2% for SLARouter. SLARouter is cheaper on 6 benchmarks and Explore-then-Commit on 5. The new section "Routing Trajectories Over Time" in the paper plots the cumulative cost and the running satisfaction over the full request sequence on ACPBench, GPQA, and WinoGrande. At the end of the sequence the two methods compare as follows:

  • On ACPBench, SLARouter costs \0.480±0.040at69.4±1.6 0.480 ± 0.040 at 69.4 ± 1.6%, and Explore-then-Commit costs \\ 0.515 ± 0.019 at 69.2 ± 0.2%.
  • On GPQA, SLARouter costs \0.058±0.003at47.3±0.8 0.058 ± 0.003 at 47.3 ± 0.8%, and Explore-then-Commit costs \\ 0.054 ± 0.002 at 47.1 ± 0.4%.
  • On WinoGrande, SLARouter costs \0.013±0.002at78.6±2.1 0.013 ± 0.002 at 78.6 ± 2.1%, and Explore-then-Commit costs \\ 0.012 ± 0.004 at 78.3 ± 0.2%.

Cost and satisfaction include all requests of the sequence. As the reviewer anticipates, these targets bind a single benchmark at a time. Llama 3.3 70B meets α\alpha on all 11 benchmarks at a total cost of \$ 1.189, so identifying a suitable model is sufficient there.

AuthorsOpenReview ↗

Response to Reviewer cnqm (part 2 of 2)

Mixed traffic under a single target. On the pooled stream of the 11 benchmarks with α=74.6\alpha=74.6\\% (28,737 requests, three seeds, ten for the two bandits), SLARouter reaches 74.9 ± 0.5% at \0.851±0.075,whereasExplore−then−Commitreaches74.9±0.9 0.851 ± 0.075, whereas Explore-then-Commit reaches 74.9 ± 0.9% at \\ 2.207 ± 0.267 and UCB reaches 75.1 ± 0.4% at \1.680±0.171.Onlythe35B,70B,and122Bmodelsmeetthistargetalone,andthecheapestofthemisthe70Bmodelat 1.680 ± 0.171. Only the 35B, 70B, and 122B models meet this target alone, and the cheapest of them is the 70B model at \\ 1.189, which is 40% above SLARouter. A learner that meets this target with a fixed model selected after exploration therefore pays at least the per-request cost of the 70B model after its commitment. Our Explore-then-Commit keeps exploring after it commits, since the shared schedule keeps the labeled stream identical across methods, and a variant that stops exploring after the commitment is subject to the same bound.

Conditions for an advantage. Our results indicate two conditions. The per-request optimum must lie well below the best fixed model, and the predictor must recover enough of this headroom to pay for its exploration and its errors, which correspond to the terms O(βT−1/4)O(\beta T^{-1/4}) and βFmin⁡\beta F_{\min} of Theorem 2. Under per-benchmark targets the headroom exists (e.g., \0.066forthehindsightper−requestoracleagainst 0.066 for the hindsight per-request oracle against \\ 0.304 for the 70B model on ACPBench), and SLARouter does not recover enough of it on our benchmarks. On the pooled stream, the oracle costs \0.225,thebestfixedmodelperbenchmarkcosts 0.225, the best fixed model per benchmark costs \\ 0.617, the best single model costs \1.189,andSLARoutercosts 1.189, and SLARouter costs \\ 0.851. It recovers part of this headroom and remains \0.23abovetheassignmentboundand 0.23 above the assignment bound and \\ 0.63 above the oracle. Its advantage over the 70B model is that it needs no prior knowledge of the best model, which is known only in hindsight. The revised paper states both conditions in Section 5.2. The general comment above summarizes the other changes of the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.