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

Amit Singh Bhatti, Vishal Vaddina, Dagnachew Birru · 2026

Read PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems by Amit Singh Bhatti, Vishal Vaddina, Dagnachew Birru (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19402.txt.

Introduction

Amit Singh Bhatti, Vishal Vaddina, and Dagnachew Birru route queries across many language models with service promises attached. Live deployments serve mixed workloads where cost and quality needs vary by customer tier, hour, and how critical the query is. Serving systems take latency promises directly, but model routers do not.

Operators must tune router knobs offline and guess the accuracy that will result, since knobs and outcomes link in indirect ways. Their system, PROTEUS, uses Lagrangian reinforcement learning to route with the promise in the loop. Routers that honor stated service levels would make multi model serving far easier to run.

Catalog record

CREATORAmit Singh Bhatti, Vishal Vaddina, Dagnachew Birru
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19402

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems Amit Singh Bhatti, Vishal Vaddina, Dagnachew Birru 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 service-level objectives (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 ( P olymorphic R outer for O perational T arget E nforcement with U nified S LA), 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 τ ∈ [ 0.85 , 0.95 ] \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. 1 Introduction Production LLM serving systems must balance conflicting objectives, maximizing response quality while minimizing operational costs under varying workload requirements. Existing routing approaches optimize this tradeoff indirectly through tunable parameters such as confidence thresholds, routing percentages, or constraint weights, but these parameters have a non-monotonic, dataset-dependent relationship with actual quality outcomes ( 9 ; 10 ) . Operators cannot directly specify quality requirements as service-level objectives (SLOs), even though traditional serving systems let you specify latency or throughput targets directly ( 6 ; 19 ) . This indirect control becomes operationally infeasible as deployments scale across differentiated service tiers with distinct quality and cost requirements. Production deployments exhibit heterogeneous quality requirements across workload classes, as evidenced by OpenAI’s API offering differentiated service tiers with per-request service_tier selection ( 18 ) , AWS identifying multi-tenant SaaS architectures as a primary routing use case ( 4 ) , and Microsoft’s production traces revealing workload classes with conflicting latency and quality SLAs ( 12 ) . In these systems, customer tier metadata or SLA contracts determine quality requirements, where a premium customer subscribing to high-accuracy service expects 95% quality while an economy customer with cost-optimized access expects 75% quality. Although these platforms accept latency and availability targets directly, quality requirements remain indirectly controlled, and batch analytics workloads may tolerate lower accuracy for significant cost reduction while customer-facing queries require high reliability regardless of cost. Current routers force operators to infer which parameter settings might achieve desired accuracy levels rather than specifying accuracy targets directly. LLM routing should solve this problem, given that models span four orders of magnitude in cost ( 9 ; 15 ) and effective routing reduces costs by 80 to 90% ( 22 ; 7 ) , but current routers control outcomes indirectly. Cascade methods ( 5 ; 1 ) route through models until confidence thresholds are met, while learned predictors ( 17 ; 22 ; 7 ) require threshold calibration. RouteLLM ( 17 ) asks operators to “calibrate thresholds using a sample of queries” to estimate what accuracy a given parameter produces, meaning operators must deploy separate configurations per tier or retune parameters when requirements change. RL methods ( 16 ; 26 ) optimize with constraint weights, but the relationship between parameters and outcomes remains indirect, non-monotonic, and dataset-dependent ( 9 ; 10 ) . Model serving systems solved the analogous problem for latency, with Clipper ( 6 ) accepting latency SLOs directly via additive increase multiplicative decrease (AIMD) control, INFaaS ( 19 ) accepting accuracy requirements such as 70% target accuracy specified via the command-line flag -A 70 and selecting model variants accordingly, and Proteus ( 2 ) scaling accuracy reactively under load. However, none of these systems address multi-LLM routing with learned policies, as INFaaS selects among variants of one architecture and Proteus’s scaling is system-driven rather than operator-specified. What is missing is a router that accepts accuracy targets directly and learns to satisfy them across heterogeneous LLMs. This problem is harder than threshold tuning because the policy must generalize across continuous \tau values without memorizing operating points, and static model bucketization fails when query difficulty varies within each tier. For example, a premium customer asking a simple factual question should be routed to a cheap model that satisfies the 95% target, whereas the same customer asking a complex reasoning question needs an expensive model. The router therefore needs per-query adaptation conditioned on both target accuracy and query difficulty, making a global threshold shift or fixed tier-to-model mapping insufficient. Our approach uses constrained RL with \tau -conditioned networks, where a learned Lagrangian dual variable \lambda enforces constraints during training by penalizing accuracy shortfalls. The policy outputs a continuous quality preference \mu\in[0,1] , which allows smooth interpolation across operating points and eliminates manual tuning. Contributions. We formalize SLA-adaptive routing as constrained optimization with \tau as runtime parameter. We present PROTEUS, which combines \tau -conditioned networks with Lagrangian dual control to enable a single trained model to serve the full accuracy spectrum. We demonstrate consistent floor compliance on two benchmarks where baselines fail, while matching or exceeding their standard routing metrics. 2 Method 2.1 Problem Formulation A routing system receives queries x and must select from a pool of K models with varying capabilities and costs, where each model m_{i} has per-query performance p_{i}(x)\in[0,1] representing the correctness probability and a cost c_{i} in dollars per query. The operator specifies an accuracy target \tau representing the minimum acceptable accuracy derived from customer SLA contracts or service tier metadata, and the router must minimize cost while meeting this target. \min_{\pi_{\theta}}\;\mathbb{E}_{x,m\sim\pi_{\theta}(x,\tau)}[c_{m}]\quad\text{s.t.}\quad\mathbb{E}_{x,m\sim\pi_{\theta}(x,\tau)}[p_{m}(x)]\geq\tau (1) Unlike prior work ( 17 ; 22 ; 16 ) , we condition the policy on \tau as runtime input, allowing a single deployed model to serve specified accuracy requirements without retraining or parameter sweeping. Runtime Adaptation: One Policy Serves All SLA Tiers Simultaneously Dynamic Multi-Tier Workload SLA Contracts: Premium \rightarrow 0.95 | Standard \rightarrow 0.88 | Economy \rightarrow 0.75 Premium ( \tau{=}0.95 ) “Assess credit risk for portfolio” Standard ( \tau{=}0.88 ) “Summarize earnings report” Economy ( \tau{=}0.75 ) “Calculate compound interest” Query Difficulty Adaptation Easy Premium \rightarrow Llama3-8B | Hard Premium \rightarrow GPT-4 Same \tau , different models Temporal SLA Dynamics .95 .88 .75 Adapts to load patterns without retraining All queries (x,\tau) PROTEUS Policy \pi_{\theta}(\mu\,|\,x,\tau) Single trained model \tau\in[0.75,0.95] routing decision Routing Outcomes Examples: “Assess credit risk” (Prem, .95) GPT-4 “Calculate interest” (Econ, .75) Llama3-8B Aggregate: Economy (.75) acc: 76.8% | cost: 94% \downarrow Standard (.88) acc: 88.5% | cost: 74% \downarrow Premium (.95) acc: 95.2% | cost: 15% \downarrow cheap mid frontier Floor compliance: 100% | Same trained model Learned Constraint Mechanism \tau input \lambda

Read the complete text