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

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.