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

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 $\sim 11$ 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.