acceptodds
Under review as a conference paper at ICLR 2027

The Price of Waiting: Budgeted Online Routing for Latency-Tiered LLM Services

Abstract

Interactive large language model (LLM) applications must trade off response quality, latency, and the cost of premium compute. A routing platform with a limited budget must decide which LLM to query and when to pay for faster delivery, all while learning from feedback that may be arbitrarily delayed or censored. We formulate this challenge as an online routing problem with immediate and delayed service modes under a hard premium budget. For a given LLM, both modes share the same response-quality distribution, but delayed service postpones feedback and discounts the response value. To address this, we bound the remaining value of any pending request using its current age and a known discount kernel. By combining these envelopes with completed observations, we construct confidence intervals that accommodate arbitrary reward–delay dependence without requiring known delay distributions or bounded delays. We propose DC-LADA for cost-penalized objectives and EQF-LADA for hard-budget constraints. The latter integrates optimistic allocation with quantized updates and deterministic local credit. Under stationary outcomes and deterministic costs, EQF-LADA strictly satisfies the budget on every realized sequence and achieves a regret bound that disentangles standard learning error, uncertainty from premium observations, and uncertainty in pending values. For a finite action space, summable pending-value envelopes guarantee sublinear regret without relying on raw-delay bounds. Trace-replay experiments on MMLU and HellaSwag demonstrate that EQF-LADA consistently outperforms evaluated baselines in mean discounted reward across various budget and discount settings while strictly adhering to spending constraints.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Routing, Budgeted Bandit, LLM

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_FygHOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper models the online LLM routing in the serving system as a multi-arm bandit problem. Deriving learning-based policy and a square root regret bound. Then, they run some model-based simulation to verify the theory.

Critical strengths
  1. The writing is clear.
  2. The theoretical analysis is rigorous.
Critical weaknesses
  1. The biggest weakness is the gap between the model and real. In real MaaS system, usually different models are deployed on different GPU groups (each GPU needs to store the model parameters and therefore it is not possible to store a lot of models' parameters on a single GPU). Therefore, in a real MaaS system, waiting is usually not a routing decision. Moreover, from the math model in the paper, I do not see a clear relationship between this model and LLM serving, and I think it can be a valid model on general learning theory and bandit literature. If the authors think this is a complete theoretical work, I suggest removing all LLM motivations, and carefully compare with bandit literatures to make the novelty and contribution clear. If the authors think this is really designed for LLM serving, we need to have some LLM serving patterns in the model. Otherwise, the gap is too huge to provide any insight. Based on my understanding, if the paper is trying to contribute to the application field (using bandit to optimize LLM routing), the authors should spend more efforts on explaining the gap between the model and real routing before deriving beautiful mathematical theorems, because even if the mathematical theorems are beautiful, due to the huge gap between the model and real, these beautiful results still become meaningless.

  2. The simulation is mainly model-based simulator, and from my perspective, it can provide few insights.

Questions for authors

Would you like to figure out the gap between your model and real LLM routing in a MaaS system?

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

This paper studies online LLM routing with immediate and delayed service modes. Immediate service incurs a premium but reveals feedback promptly, whereas delayed service is free but may produce arbitrarily delayed or permanently censored feedback, with its value discounted by waiting time. The paper constructs age-dependent upper envelopes for pending rewards and proposes DC-LADA for a cost-penalized objective and EQF-LADA for a hard-budget objective. The theoretical results include simultaneous confidence bounds, pathwise budget feasibility, regret upper bounds, and a zero-budget lower bound. Experiments replay traces from six LLM services on MMLU and HellaSwag.

The theoretical development is generally substantial, and the pending-value envelope is a clean technical idea. The pathwise prefix-budget guarantee is also stronger than an expected-cost guarantee. However, the empirical setting is heavily constructed: the immediate and delayed modes are not observations from real priority tiers, and the costs are artificially rescaled. The experiments evaluate calibrated variants that are not covered by the stated theory, without fully reporting their calibrated parameters.

Critical strengths
  • It combines response quality, latency, delayed feedback, and a limited premium budget in one formulation.

  • The paper acknowledges near ties, the reuse of fixed trace populations, and the absence of independent replication on new service populations.

Critical weaknesses
  • The paper does not observe the same model under actual standard and priority tiers. Instead, historical latency is assigned to the Delayed mode, while the Immediate mode is made artificially instantaneous. Premium costs are also obtained through linear rescaling. This validates a synthetic replay abstraction, not a deployed priority-service mechanism.

  • The paper states that the experiments use calibrated practical variants and that the theoretical confidence and regret guarantees do not apply to those settings. However, the actual confidence multipliers, quantization parameters, and calibration procedure are not fully reported.

  • PD-DC and PD-AO perform almost identically in the hard-budget experiments, providing little evidence that discount-censored estimation itself drives the improvement. The gain of EQF-LADA may instead come primarily from its frontier allocation or scheduling rule. A factorial ablation of estimator, allocator, quantization, and local credit is needed.

  • Evaluation is limited to two static multiple-choice benchmarks with binary correctness rewards. There are no open-ended generation, coding, dialogue, or real interactive workloads, and all replay seeds are sampled from the same two fixed trace populations.

  • The analysis excludes policy-induced congestion, changing loads, queue state, batching, caching, and quality differences between service modes. The contribution should therefore be positioned as an idealized learning and allocation layer rather than a complete LLM-serving model.

Questions for authors

Please refer to weaknesses

Reviewer_gsi6OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes an algorithm that routes a model zoo between an instantaneous low-latency endpoint that incurs cost or via a batched time-delayed endpoint that is free of charge. Both bound the value of pending requests from their age to get delay-robust confidence intervals, and EQF-LADA adds an optimistic LP frontier with a credit-based scheduler that never exceeds the budget. The paper provides a theoretical intuition for the effectiveness of the proposed algorithm as well as evaluation over well-established benchmarks.

Critical strengths

The paper addresses a key question in times where token cost are continuously increasing and capabilities of smaller models are quickly catching up to the frontier and where batch processing APIs oftentimes offer significant discounts at the cost of latency.

Critical weaknesses

While the paper addresses an important issue, it's contributions are quite limited in my view. Looking at the theoretical results, the confidence bounds of the bandit algorithm are in large parts a reformulation of Lancewicki et al. (2021) with an additional delay estimator. The bounds presented are near identical.

The paper also discusses budget execution based on virtual tokens. This kind of work is extensively studied by Neely (2010) and others. None of the key literature is referenced in the paper. The literature offers plenty of options for baselines that the proposed algorithm could be compared against (see list below), even if the algorithms have slightly different objectives.

To my understanding, theorem 4 simply sums up the UCB term, the sampling, delay envelope, and epoch term. There is no other relationship between budget and latency that would introduce a technical difficulty that warrants deeper analysis (this, in large parts, explains my first concern). Directly related to this, assumption 1 excludes the routing-dependent delays, which could have introduced a complex interplay between latency and budget that would be really interesting to understand.

Beyond that, there is so much related work missing on the matter that it is difficult to list it all. I would at least hoped to see a clear demarcation of what practical problem the proposed approach solves that no other algorithm solves at this point. Here is an excerpt:

Related work that might be worth discussing in the paper

Budgets / virtual queues

  • Stochastic Network Optimization with Application to Communication and Queueing Systems. Neely, 2010 (book).
  • Online Convex Optimization with Stochastic Constraints. Yu et al., 2017, NeurIPS.
  • A Low Complexity Algorithm with O(T) Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints. Yu & Neely, 2020, JMLR.
  • Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond. Guo et al., 2022, NeurIPS.
  • MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees. Woisetschläger et al., 2025, NeurIPS.

Constrained bandits using virtual queues or Lyapunov drift

  • An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints. Liu et al., 2021, NeurIPS.
  • A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback. Cayci et al., 2022, AAAI.
  • Budget-Constrained Bandits over General Cost and Reward Distributions. Cayci et al., 2020, AISTATS.

LLM routing

  • Beyond Accuracy and Cost: Latency-Aware LLM Query Routing for Dynamic Workloads. Patel et al., 2026.
  • BARouter: A Budget-adaptive Online LLM Router Framework. Zu et al., 2026, WWW.
  • PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems. Bhatti et al., 2026
  • Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs. Wei et al., 2025.
  • Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution. Poon et al., 2026, AAAI.
  • RouteLLM: Learning to Route LLMs with Preference Data. Ong et al., 2025, ICLR.
  • FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance. Chen et al., TMLR.
Questions for authors
  • How does the virtual credit mechanism differ from a virtual queue as discussed in Lyapunov optimization work?
  • Delay is measured in rounds, i.e. the number of requests, so Ψ\Psi grows with the arrival rate. How do your guarantees read in wall-clock time at realistic request rates? What happens if there is a burst or a sudden load shift from one level to another and that remains for the time being?
  • What confidence radius and quantization step do the "calibrated" variants use? How would the EQF-LADA approach discussed in the theory perform without the calibration? A clearer motivation would helpful or at least understanding the practical necessity in more detail.
  • How does the performance look like for more recent benchmarks that involve tool calling and reasoning? There may be asynchronous jobs that can fire agentic sessions whenever there is capacity on the inference endpoint.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.