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

• URL: http://arxiv.org/abs/2606.19376v1
• Date: Fri, 12 Jun 2026 08:50:46 GMT
• Title: Cost-Optimal LLM Routing with Limited User Feedback under User Satisfaction Guarantees
• Abstract summary: We introduce SLA, an online routing algorithm that learns a cost-optimal policy from the sparse, one-sided user feedback available in production systems.<n> Experiments show SLAference satisfies SLA constraints without the need for per-benchmark tuning, reducing operating cost by up to 2.2x over existing baselines.
• Score: 11.389402303822635
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 show that SLARouter satisfies SLA constraints without the need for per-benchmark tuning, reducing operating cost by up to 2.2x over existing baselines.

Related papers

• Online Linear Programming for Multi-Objective Routing in LLM Serving [9.541681114575812]
  We study the online routing problem in large language model serving.<n>We introduce a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards.<n>A big picture from our result: a science-based approach outperforms others based on millisecond decodes.
  arXiv  Detail & Related papers  (2026-07-04T16:48:37Z)
• $π$-StepNFT: Wider Space Needs Finer Steps in Online RL for Flow-based VLAs [64.60188746073904]
  Flow-based vision-language-action models excel in embodied control but suffer from intractable likelihoods during multi-step sampling.<n>We propose textbftextit$boldsymbol$-StepNFT (Step-wise Negative-aware Fine-Tuning), a critic-and-likelihood-free framework that requires only a single forward pass per optimization step.
  arXiv  Detail & Related papers  (2026-03-02T17:04:49Z)
• Reliable LLM-Based Edge-Cloud-Expert Cascades for Telecom Knowledge Systems [54.916243942641444]
  Large language models (LLMs) are emerging as key enablers of automation in domains such as telecommunications.<n>We study an edge-cloud-expert cascaded LLM-based knowledge system that supports decision-making through a question-and-answer pipeline.
  arXiv  Detail & Related papers  (2025-12-23T03:10:09Z)
• Conformal Constrained Policy Optimization for Cost-Effective LLM Agents [27.37909142846675]
  Large language models (LLMs) have recently made tremendous progress towards solving challenging AI problems.<n>We propose a novel strategy where we combine multiple LLM models with varying cost/accuracy tradeoffs in an agentic manner.<n>Our approach provides a principled and practical framework for deploying LLM agents that are significantly more cost-effective while maintaining reliability.
  arXiv  Detail & Related papers  (2025-11-14T19:39:28Z)
• xRouter: Training Cost-Aware LLMs Orchestration System via Reinforcement Learning [104.63494870852894]
  We present x, a tool-calling-based routing system in which a learned router can either answer directly or invoke one or more external models.<n>Our implementation encompasses the full reinforcement learning framework, including reward and cost accounting.<n>Across diverse benchmarks, x achieves strong cost-performance trade-offs.
  arXiv  Detail & Related papers  (2025-10-09T16:52:01Z)
• Dynamic Speculative Agent Planning [57.630218933994534]
  Large language-model-based agents face critical deployment challenges due to prohibitive latency and inference costs.<n>We introduce Dynamic Speculative Planning (DSP), an online reinforcement learning framework that provides lossless acceleration with substantially reduced costs.<n>Experiments on two standard agent benchmarks demonstrate that DSP achieves comparable efficiency to the fastest acceleration method while reducing total cost by 30% and unnecessary cost up to 60%.
  arXiv  Detail & Related papers  (2025-09-02T03:34:36Z)
• Cost-Aware Contrastive Routing for LLMs [57.30288453580456]
  We introduce Cost-Spectrum Contrastive Routing (CSCR), a lightweight framework that maps both prompts and models into a shared embedding space.<n>CSCR consistently outperforms baselines, improving the accuracy-cost tradeoff by up to 25%.
  arXiv  Detail & Related papers  (2025-08-17T20:16:44Z)
• Aligning LLMs on a Budget: Inference-Time Alignment with Heuristic Reward Models [23.37504394417425]
  We propose HIA (Heuristic-Guided Inference-time Alignment), a tuning-free, black-box-compatible approach that uses a lightweight prompt.<n>We find that HIA is effective under low-inference budgets with as little as one or two response queries.
  arXiv  Detail & Related papers  (2025-08-07T08:54:27Z)
• MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees [17.478510146434218]
  Open-weight large language model (LLM) zoos provide access to numerous high-quality models.<n>Most users simply want factually correct, safe, and satisfying responses without concerning themselves with model technicalities.<n>We introduce MESS+, an optimization algorithm for cost-optimal LLM request routing.
  arXiv  Detail & Related papers  (2025-05-26T13:11:08Z)
• MixLLM: Dynamic Routing in Mixed Large Language Models [57.309520357563215]
  Large Language Models (LLMs) exhibit potential artificial generic intelligence recently, however, their usage is costly with high response latency.<n>We develop MixLLM, a dynamic contextual-bandit-based routing system for query-LLM assignment.
  arXiv  Detail & Related papers  (2025-02-09T02:26:15Z)
• Doing More with Less: A Survey on Routing Strategies for Resource Optimisation in Large Language Model-Based Systems [1.430963201405577]
  Large Language Model (LLM)-based systems are usually designed with a single, general-purpose LLM to handle all user queries.<n>These systems may be inefficient as different queries may require different levels of reasoning, domain knowledge or pre-processing.<n>A routing mechanism can therefore be employed to route queries to more appropriate components, such as smaller or specialised models.
  arXiv  Detail & Related papers  (2025-02-01T12:08:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.