PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems
This addresses the need for operators in production LLM deployments to specify accuracy targets directly rather than inferring them from opaque settings, though it is incremental as it builds on Lagrangian optimization methods.
The paper tackles the problem of LLM routers not accepting latency SLOs directly, requiring operators to tune parameters offline, by introducing PROTEUS, a router that accepts accuracy targets as runtime input and uses Lagrangian dual control to achieve consistent floor compliance with target-response correlations of 0.97-0.98, achieving 90.1% accuracy on RouterBench and 94.0% on SPROUT, within 1.3% and 4.6% of oracle respectively, with cost savings up to 89.8%.
Production LLM deployments serve diverse workloads where cost and quality requirements vary by customer tier, time of day, and query criticality. Model serving systems accept latency SLOs directly. LLM routers do not. They force operators to tune parameters offline and guess what accuracy might result. The relationship between parameters and outcomes is indirect, non-monotonic, and dataset-dependent. Operators need to specify accuracy targets, not infer them from opaque settings. We present PROTEUS (Polymorphic Router for Operational Target Enforcement with Unified SLA), a router that accepts accuracy targets tau as runtime input. PROTEUS uses Lagrangian dual control. A learned dual variable lambda tracks constraint violations during training and conditions the policy network. This lets the router translate specified tau values into routing decisions that satisfy them. A single trained model serves the full accuracy spectrum without retraining.We evaluate on RouterBench (11 models, 405K queries) and SPROUT (14 models, 45K queries). PROTEUS achieves consistent floor compliance where accuracy meets or exceeds tau. The target-response correlation reaches 0.97 to 0.98. The closest baseline, OmniRouter, meets floors only 22% of the time despite also using Lagrangian optimization. PROTEUS operates across tau in [0.85, 0.95] from a single model. On RouterBench it achieves 90.1% accuracy, within 1.3% of oracle. On SPROUT it achieves 94.0% accuracy, within 4.6% of oracle. Cost savings reach 89.8% versus the best fixed model.