# PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems

arXiv: https://arxiv.org/abs/2601.19402 · HTML: https://mlsanity.com/paper/2601.19402/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 27 Jan 2026.

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [DeBERTaV3: Improving DeBERTa using ELECTRA-Style Pre-Training with Gradient-Disentangled Embedding Sharing](https://mlsanity.com/paper/2111.09543/) (2021)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Clipper: A Low-Latency Online Prediction Serving System](https://mlsanity.com/paper/1612.03079/) (2016)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Router-R1: Teaching LLMs Multi-Round Routing and Aggregation via Reinforcement Learning](https://mlsanity.com/paper/2506.09033/) (2025)
- [RouterEval: A Comprehensive Benchmark for Routing LLMs to Explore Model-level Scaling Up in LLMs](https://mlsanity.com/paper/2503.10657/) (2025)
- [CARROT: A Cost Aware Rate Optimal Router](https://mlsanity.com/paper/2502.03261/) (2025)
- [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025)
- [Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs](https://mlsanity.com/paper/2510.07429/) (2025)

## Built on by (most cited first, 4 of 4)

- [ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving](https://mlsanity.com/paper/2604.00136/) (2026)
- [Cost-Optimal LLM Routing with Limited User Feedback under User Satisfaction Guarantees](https://mlsanity.com/paper/2606.19376/) (2026)
- [SeqRoute: Global Budget-Aware Sequential LLM Routing via Offline Reinforcement Learning](https://mlsanity.com/paper/2605.25424/) (2026)
- [The Workload-Router-Pool Architecture for LLM Inference Optimization: A Vision Paper from the vLLM Semantic Router Project](https://mlsanity.com/paper/2603.21354/) (2026)

## Abstract (arXiv)

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.