PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems
PROTEUS uses Lagrangian RL for SLA-aware multi-LLM routing, achieving 94.0% accuracy and 89.8% cost savings.
Key Findings
Methodology
PROTEUS employs Lagrangian dual control, where a learned λ variable dynamically adjusts the policy network to meet runtime accuracy targets τ. Key components include DeBERTa-v3 encoder, quality preference μ output, and dynamic routing score formula.
Key Results
- On RouterBench, PROTEUS achieves 90.1% accuracy, 1.3% below Oracle, with 89.8% cost savings.
- On SPROUT, it achieves 94.0% accuracy, 4.6% below Oracle, while dynamically adapting across a 9.5× cost range.
- Compared to OmniRouter, PROTEUS maintains 100% floor compliance across all τ values, while OmniRouter achieves only 22%.
Significance
This study addresses the inability of multi-LLM systems to directly specify accuracy targets, providing a novel solution for dynamic SLA adaptation, significantly enhancing flexibility and efficiency.
Technical Contribution
Introduces τ-conditioned policy networks and Lagrangian constraint feedback, enabling a single model to adapt dynamically across multiple accuracy targets, outperforming static or parameter-tuning methods.
Novelty
PROTEUS is the first routing system to support runtime accuracy target specification, combining Lagrangian optimization and RL for dynamic model selection.
Limitations
- High costs for extreme accuracy targets (e.g., τ > 0.95).
- Performance prediction relies on training data distribution, potentially degrading under distribution shift.
Future Work
Future work could explore more efficient constraint feedback mechanisms and extend to additional dynamic SLA scenarios like real-time load changes.
AI Executive Summary
PROTEUS is a novel multi-LLM routing system designed to meet dynamic SLA targets. Existing routing methods fail to directly specify accuracy targets, forcing operators to rely on indirect parameter tuning, which is inefficient and inflexible.
Using Lagrangian reinforcement learning, PROTEUS enables runtime adaptation, allowing users to specify accuracy targets τ. The system dynamically adjusts its policy network via a learned λ variable, outputs quality preference μ, and selects optimal models using a routing score formula.
Experiments show PROTEUS achieves significant accuracy and cost optimization on RouterBench and SPROUT datasets, reaching 94.0% accuracy and saving 89.8% in costs. Its innovation and flexibility offer critical insights for the future of multi-LLM service systems.
Deep Analysis
Background
Multi-LLM serving systems must balance quality and cost across diverse customer tiers and query complexities. Existing methods like OmniRouter and CARROT rely on indirect parameter tuning, which cannot dynamically adapt to SLA targets.
Core Problem
Traditional routing systems cannot directly accept accuracy targets, forcing operators to infer results through complex parameter tuning. This indirect control is inefficient and hard to scale in multi-tier service scenarios.
Innovation
Key innovations include: 1) Lagrangian dual control mechanism for dynamic constraint feedback; 2) τ-conditioned policy networks for runtime target adaptation; 3) dynamic routing score formula combining quality preference μ and cost weighting.
Methodology
- �� DeBERTa-v3 encoder generates query embeddings.
- �� Policy network outputs quality preference μ based on embeddings and τ.
- �� Routing score formula combines predicted performance pi, quality preference μ, and cost ci to select optimal models.
- �� Lagrangian variable λ dynamically adjusts during training to ensure accuracy targets are met.
Experiments
Experiments use RouterBench and SPROUT datasets to evaluate performance across accuracy targets τ. Baselines include OmniRouter and CARROT, comparing accuracy, cost, and SLA compliance.
Results
PROTEUS achieves 90.1% accuracy on RouterBench (1.3% below Oracle, 89.8% cost savings) and 94.0% accuracy on SPROUT (4.6% below Oracle, 100% floor compliance).
Applications
Applicable to multi-tenant SaaS architectures, real-time query routing, and dynamic load management scenarios, significantly improving service quality and cost efficiency.
Limitations & Outlook
High sensitivity to costs for extreme accuracy targets; reliance on training data distribution for model performance prediction may degrade under distribution shift.
Plain Language Accessible to non-experts
Imagine a restaurant with multiple chefs, each specializing in different dishes but varying in cost and speed. PROTEUS acts like a smart manager, dynamically assigning chefs based on customer preferences (e.g., high quality or low cost). It learns customer needs and dish complexity to ensure every assignment meets expectations while saving resources.
ELI14 Explained like you're 14
Imagine you're playing a video game with lots of characters to choose from, each with different skills and gear. PROTEUS is like a super captain who picks the best character for each mission based on difficulty and your goal (like winning or saving resources). Cool, right?
Glossary
Lagrangian variable
A variable used in constrained optimization to dynamically adjust constraint pressure.
Used to train the policy network to meet accuracy targets.
Quality preference
Represents the tradeoff between quality and cost, ranging from [0,1].
Used in the routing score formula for model selection.
Accuracy target
The minimum acceptable accuracy specified by users to guide routing decisions.
Input as τ to the policy network.
Dynamic routing score
A formula combining model performance, quality preference, and cost to select optimal models.
Used to compute model scores at runtime.
RouterBench
A benchmark dataset with 405K queries and 11 models for evaluating routing performance.
Used to test PROTEUS's accuracy and cost optimization capabilities.
Open Questions Unanswered questions from this research
- 1 How to further optimize costs for extreme accuracy targets?
- 2 How to address distribution shift in model performance prediction?
Applications
Immediate Applications
Multi-tenant SaaS services
Dynamically adjust model selection based on customer tiers to improve service quality and cost efficiency.
Real-time load management
Adapt to query traffic spikes dynamically to ensure service stability.
Long-term Vision
Fully automated AI service routing
Achieve fully autonomous dynamic routing systems adaptable to more complex scenarios.
Abstract
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.