MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees¶

会议: NeurIPS 2025
arXiv: 2505.19947
代码: GitHub
领域: 优化
关键词: 成本优化, LLM路由, 虚拟队列, SLA保证, 在线学习

一句话总结¶

MESS+是首个将LLM请求路由形式化为带SLA约束的随机优化问题的框架，通过在线学习的请求满足度预测器+虚拟队列机制动态选择模型，在3个推理和5个问答基准上以满足SLA约束的前提下实现平均2倍的成本节省，并提供成本最优性和约束满足的理论保证。

研究背景与动机¶

领域现状：开源LLM生态（Llama、Qwen、Granite）提供多个不同规模的模型，形成"模型zoo"。每个模型家族至少有3个模型（如1B/8B/70B），性能和成本差异巨大。用户面临模型选择困难，且常规做法是选最大模型——既浪费资源，成本也不可控。

现有痛点：现有路由方案各有局限——RouteLLM仅支持2个模型的路由、Zooter和RouterDC缺乏形式化的成本保证、所有方法都没有SLA合规的理论保证。用户需要的是"保证至少X%请求被满意回答"的硬性承诺。

核心矛盾：三方需求的冲突——(1)用户要高质量回答但不懂技术；(2)服务商要最小化运营成本；(3)企业客户需要SLA保证。这三者需要在一个统一框架中同时优化。

本文目标 如何设计一个LLM路由算法，在最小化运营成本的同时严格保证SLA合规（即随时间推移的最低请求满足率）？

切入角度：借鉴Lyapunov drift-plus-penalty框架，将SLA约束编码为虚拟队列，将请求满足度预测作为在线学习问题集成到逐请求优化中。

核心 idea：用虚拟队列追踪累积SLA违反，用在线学习的满足度预测器估计各模型表现，每个请求求解一个简单的优化问题实现成本最优选择。

方法详解¶

整体框架¶

将问题形式化为约束随机优化：目标函数是最小化平均运营成本 \(\frac{1}{T}\sum_t\sum_m \mathbb{E}[y_{m,t}E_{m,t}]\)，约束是请求满足率不低于目标 \(\alpha\)：\(\frac{1}{T}\sum_t\sum_m \mathbb{E}[y_{m,t}s_{m,t}] \geq \alpha\)，其中 \(y_{m,t} \in \{0,1\}\) 是模型选择变量，\(E_{m,t}\) 是成本，\(s_{m,t} \in \{0,1\}\) 是未知的满足度标签。系统在线运行，每个请求到达时做出路由决策。

关键设计¶

虚拟队列机制:
- 功能：将长期SLA约束转化为逐步可操作的信号
- 核心思路：维护一个虚拟队列 \(Q_{t+1} = \max\{0, Q_t + \alpha - s_{m^*,t}\}\)，直观含义是累积的SLA违反量。当 \(Q_t\) 较大时（SLA被大量违反），优化问题自动偏向选择更可能满足请求的大模型；当 \(Q_t\) 较小时（SLA富余），允许选择更便宜的小模型
- 设计动机：灵感来自Lyapunov drift-plus-penalty框架，但进行了关键扩展——整合了在线学习的满足度预测器（原框架不涉及学习预测器）
在线请求满足度预测器:
- 功能：在发送请求到模型之前，预测每个模型是否能满足该请求
- 核心思路：使用ModernBERT作为冻结backbone + 可训练多标签分类器（SGD训练）。输出为每个模型的满足概率 \(\hat{s}_{m,t} \in [0,1]\)。通过概率性探索策略（概率 \(p_t = \min(1, c/\sqrt[4]{t})\) 随时间衰减）平衡探索与利用——探索时查询所有模型获取真实标签来更新预测器。训练损失为正则化交叉熵
- 设计动机：\(p_t \propto 1/\sqrt[4]{t}\) 的衰减速度关键——太快则预测器不准确，太慢则探索成本过高。四次根衰减在预测精度和探索开销间取得最优平衡（有理论保证）
逐请求优化问题:
- 功能：对每个到达的请求做出成本最优的路由决策
- 核心思路：\(m^* = \arg\min_m V \cdot E_{m,t} + Q_t(\alpha - \hat{s}_{m,t})\)。第一项是加权成本（V控制成本权重），第二项是SLA违反的惩罚（队列长度乘以预测满足缺口）。当队列长时，惩罚项主导，倾向选高满足率的大模型；当队列短时，成本项主导，倾向选便宜的小模型
- 设计动机：V参数控制收敛速度和成本之间的tradeoff——V大时成本更优但SLA收敛慢，V小时SLA快达标但成本高。理论表明约束违反为 \(O(V/T + 1/\sqrt{T})\)，成本差距为 \(O(M/\sqrt[4]{T} + 1/V)\)

损失函数 / 训练策略¶

满足度预测器：正则化交叉熵损失 + SGD在线学习
超参数设置：V=0.0001, c=0.1，在不同基准上保持固定（无需逐任务调参）
成本指标：每个请求的能耗（MJ），通过预先profile获得

实验关键数据¶

主实验¶

8个基准的代表性结果（Llama 1B/8B/70B模型zoo）：

方法	ARC-C (alpha=50%) 成本MJ	满足率%	BoolQ (alpha=80%) 成本MJ	满足率%
L70B only	2.35	60.8%	3.40	88.8%
L8B only	0.46	54.4%	0.43	84.2%
RouteLLM	1.24	51.2%	2.96	86.8%
RouterDC	2.09	60.9%	2.14	87.1%
MESS+	0.83	53.6%	0.90	82.2%

8个基准平均（alpha=66%）：

方法	平均成本MJ	平均满足率%	模型调用比(70B/8B/1B)
L70B only	2.79	77.3%	100/0/0
RouteLLM	2.11	74.2%	75/0/25
RouterDC	2.09	76.1%	76/22/2
MESS+	1.07	67.8%	35/38/27

消融实验¶

配置	说明
探索概率c的影响	c=0.1最优；c过大探索成本高，c过小预测器不准
V参数的tradeoff	V大则成本低但SLA收敛慢；V小则SLA快速达标但成本高
预测器精度	经过初始探索阶段后预测精度快速收敛，支持理论假设
非i.i.d.设置	理论假设i.i.d.，但实验表明在非i.i.d.（按主题排序）设置下仍然有效

关键发现¶

MESS+实现约2倍成本节省：在满足SLA的前提下，MESS+平均成本仅1.07MJ，而次优的RouterDC和RouteLLM约为2.09-2.11MJ——成本减半
充分利用模型zoo的多样性：MESS+的调用比为35%/38%/27%（大/中/小），真正做到按需分配。而RouteLLM只能路由2个模型（75%/0%/25%），RouterDC几乎总是选大模型（76%/22%/2%）
SLA保证在有限请求后即可满足：理论保证需要 \(T \to \infty\)，但实际上约1000个请求后就可稳定满足SLA，实用性强
固定超参数跨任务有效：V=0.0001和c=0.1在8个基准上均无需调整，部署友好

亮点与洞察¶

理论保证是核心卖点：Theorem 1证明约束违反 \(O(V/T + 1/\sqrt{T})\)，Theorem 2证明成本差距 \(O(M/\sqrt[4]{T} + 1/V + M \cdot F_{\min})\)，这是LLM路由领域首个有严格理论保证的方法。实际意义是服务商可以签SLA合同并有数学保证不违约
虚拟队列+在线学习的结合：将Lyapunov优化与在线预测器训练统一到一个框架中，分析了预测器误差如何影响整体优化——这是对经典框架的实质性扩展
能耗作为成本指标：不仅考虑API调用费用，还考虑能耗（MJ），呼应EU AI Act Article 95的能源监控要求，有实际部署意义

局限与展望¶

模型zoo规模有限：实验仅用3个Llama模型，未验证在更大规模、异构zoo（混合不同家族）下的效果
满足度标签的获取：假设用户立即给出反馈，实际场景中反馈延迟和稀疏是常见问题
成本模型简化：假设成本在收到请求后已知（通过token数估算），实际中不同模型的生成长度不同导致成本不确定
i.i.d.假设：理论分析依赖i.i.d.假设，虽然实验表明非i.i.d.下也有效，但缺乏非i.i.d.的理论保证
无质量差异化路由：所有请求的SLA目标相同，未支持不同优先级请求的差异化服务
改进方向：扩展到异构模型zoo、支持延迟反馈、引入请求优先级、考虑生成长度不确定性

评分¶

新颖性: ⭐⭐⭐⭐ 首个形式化带SLA保证的LLM路由优化框架，理论贡献扎实
实验充分度: ⭐⭐⭐⭐ 覆盖8个基准、多基线对比、超参数分析充分，但模型zoo规模偏小
写作质量: ⭐⭐⭐⭐ 问题动机从三方需求切入很清晰，理论推导严谨
价值: ⭐⭐⭐⭐⭐ 解决LLM部署中的核心实际问题（成本vs质量），理论+实践俱佳