Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving¶
会议: NeurIPS 2025
arXiv: 2509.02718
代码: https://github.com/fzwark/PORT
领域: LLM效率
关键词: LLM路由, 在线优化, 近似最近邻搜索, 对偶优化, 多模型服务
一句话总结¶
提出首个无需训练的在线 LLM 路由算法 PORT，通过近似最近邻搜索估计查询特征，并在少量初始查询上一次性优化对偶变量作为路由权重，在有限 token 预算下实现接近离线最优 (\(1-o(1)\) 竞争比) 的路由性能，平均较基线提升 3.55× 性能、1.85× 成本效率和 4.25× 吞吐量。
研究背景与动机¶
- 领域现状：LLM 服务提供商面临海量用户查询（如 OpenAI 峰值 12k QPS），不同 LLM 擅长不同领域且成本各异，将查询路由到最合适的模型是降低成本的关键手段。
- 现有痛点：现有路由方法要么依赖训练模型预测器（如 Roberta-based），计算开销大且部署变更需重训；要么依赖精确 KNN，复杂度高（\(O(|D|)\)），无法满足在线低延迟需求。
- 核心矛盾：现有方法均基于离线假设——假设所有查询同时到达可全局优化，但现实中查询顺序到达、未来查询未知，且 token 预算有限，离线 MILP 不可解。
- 本文要解决什么？ (a) 如何在线场景下不训练模型进行高效路由？(b) 如何在有限预算约束下最大化整体服务质量？(c) 如何适应动态 LLM 部署配置变化？
- 切入角度：作者观察到路由问题的 LP 松弛对偶问题在最优解处可由单一对偶变量 \(\gamma\) 完全参数化，\(\gamma\) 实质是各 LLM 的路由权重。因此只需从少量初始查询学习 \(\gamma^*\) 即可指导后续路由。
- 核心idea一句话：用 ANNS 估计查询特征 + 对偶变量一次性优化 = 无训练、高效、有理论保证的在线路由。
方法详解¶
整体框架¶
PORT 算法分两阶段：(1) 探索阶段：对前 \(\epsilon|Q|\) 个查询（约 250 个）随机路由并记录特征，一次性优化求解对偶路由权重 \(\gamma^*\)；(2) 利用阶段：对后续所有查询，用 ANNS 估计其在各 LLM 上的性能和成本，按 \(\arg\max_i(\alpha \hat{d}_{ij} - \hat{g}_{ij}\gamma_i^*)\) 路由。
关键设计¶
- 基于 ANNS 的特征估计:
- 做什么：快速估计每个查询在每个 LLM 上的性能 \(\hat{d}_{ij}\) 和成本 \(\hat{g}_{ij}\)
- 核心思路：维护历史数据集 \(D = \{j, a_j, d_j, g_j\}\)，对新查询用 HNSW 在嵌入空间找 \(k\) 个近邻 \(R_j\)，取均值估计：\(\hat{d}_{ij} = \frac{1}{|R_j|}\sum_{q \in R_j} d_{iq}\)
-
设计动机：相比训练预测器，ANNS 无需训练、更新历史数据即可适应部署变化，搜索复杂度仅 \(O(\log|D|)\) 远优于 KNN 的 \(O(|D|)\)
-
对偶驱动的路由权重学习:
- 做什么：将路由 MILP 松弛为 LP，求其对偶问题，学习最优路由权重 \(\gamma^*\)
- 核心思路：由互补松弛条件，最优路由规则为 \(x_{ij} > 0 \Leftrightarrow j\) 被分配到 \(\arg\max_i(\alpha\hat{d}_{ij} - \hat{g}_{ij}\gamma_i)\)。将对偶目标参数化为 \(F(\gamma) = \sum_i \gamma_i B_i + \sum_j \max_i(\alpha\hat{d}_{ij} - \hat{g}_{ij}\gamma_i)\)，在探索阶段的小样本上最小化 \(F(\gamma, P)\) 求 \(\gamma^*\)
-
设计动机：对偶变量 \(\gamma\) 本质是各 LLM 预算的"影子价格"，学好后可直接将预算约束转化为简单的线性评分规则
-
控制参数 \(\alpha\) 与 PAC 随机路由:
- 做什么：引入控制参数 \(\alpha\) 缩放目标函数；探索阶段采用随机路由
- 核心思路：\(\alpha\) 不改变最优解结构但控制未来查询的性能偏差（连接成本与性能）；随机路由保证无偏采样，使 \(\gamma^*\) 对后续查询具有泛化性（PAC 学习思想）
- 设计动机：解决在线学习的泛化问题——从小样本学到的权重必须对大量未见查询有效
训练策略¶
无需任何模型训练。仅对 \(\epsilon|Q|\)（约 2.5%）个初始查询做一次凸优化求 \(\gamma^*\)，计算开销可忽略不计。
实验关键数据¶
主实验¶
| 算法 | RouterBench Perf | RouterBench PPC | SPROUT Perf | SPROUT PPC | OpenLLM Perf | OpenLLM PPC |
|---|---|---|---|---|---|---|
| Random | 1384.3 | 3243.3 | 2827.6 | 3927.3 | 953.0 | 1284.4 |
| Greedy-Cost | 1626.3 | 3534.5 | 3934.7 | 4630.4 | 1051.0 | 1371.3 |
| BatchSplit | 1838.1 | 4005.9 | 3975.5 | 4784.5 | 1059.0 | 1392.1 |
| Roberta-Cost | 481.4 | 3738.9 | 3996.2 | 4709.2 | 1044.0 | 1362.5 |
| PORT (Ours) | 2718.6 | 6075.6 | 4513.1 | 5536.7 | 1465.0 | 2060.3 |
| 离线近似最优 | 3211.4 | 6975.2 | 5939.0 | 6986.5 | 1910.0 | 2493.7 |
PORT 在三个 benchmark 上相对近似最优分别达到 84.66%、75.99%、76.7%。
鲁棒性分析¶
| 实验维度 | 关键发现 |
|---|---|
| 查询量 4k→12k | PORT 优势随量增大而扩大，最高领先 BatchSplit 50% |
| 100 次随机查询顺序 | 各次运行一致优于所有基线，方差小 |
| LLM 数量 2→16 | 不同部署配置下均保持最优 |
| 预算倍率 0.25×→2× | 极端低预算下仍最优 |
| 极端预算分配 (80/20) | 单模型获 80% 预算时仍 2× 于 BatchSplit |
| 历史数据量 5k→25k | 对数据量不敏感 |
| 搜索候选数 3→10 | 3 个候选即可超越所有基线 |
亮点与洞察¶
- 无训练 + 有理论保证的在线路由：这是首个同时满足"无需训练"和"可证明竞争比 \(1-o(1)\)"的在线 LLM 路由算法，实用性极强。对偶视角将复杂的在线 MILP 简化为"一次优化 + 线性评分"。
- ANNS 替代 KNN 的巧妙设计：用 HNSW 图索引将搜索从 \(O(n)\) 降到 \(O(\log n)\)，且历史数据可动态增量更新，完美适配 LLM 部署的动态性。
- PAC 随机路由保证泛化：探索阶段不做贪心路由而是随机路由，牺牲少量（2.5%）查询的最优性换取权重的无偏估计，是经典在线学习思想的巧妙应用。
- 可迁移性：对偶分解 + ANNS 的框架可迁移到其他资源受限的在线分配问题（如广告投放、云资源调度）。
局限性 / 可改进方向¶
- 仅建模性能和成本：未考虑查询流量、系统负载等动态运营因素，这些与负载均衡相关但被排除在当前 MILP 之外。
- Assumption 1 的实际满足：假设嵌入距离近的查询具有相似的 LLM 性能/成本，对跨域查询或 OOD 场景可能不成立。
- 探索阶段的冷启动：需要积累历史数据集 \(D\)，对全新部署场景不适用。
- 单查询单 LLM：未考虑 ensemble 或级联策略，可能错过多模型协作的收益。
评分¶
- 新颖性: ⭐⭐⭐⭐ 对偶视角 + ANNS 的在线路由方案很新颖，但基本工具（ANNS、LP对偶）均为成熟技术
- 实验充分度: ⭐⭐⭐⭐⭐ 3 个 benchmark、8 个基线、极其全面的鲁棒性分析
- 写作质量: ⭐⭐⭐⭐ 理论部分清晰严谨，但符号较多，入门门槛较高
- 价值: ⭐⭐⭐⭐ 解决了实际的在线 LLM 路由问题，有理论+工程双重价值
与相关工作的对比¶
| 方法类别 | 代表工作 | PORT 优势 |
|---|---|---|
| 模型预测器路由 | RouteLLM, CARROT (Roberta-based) | 无需训练，部署变更无需重训，延迟更低 |
| KNN 路由 | RouterBench (精确 KNN) | ANNS 搜索 \(O(\log n)\) vs KNN \(O(n)\)，延迟降低数量级 |
| 级联/集成 | FrugalGPT, AutoMix | 单次路由 vs 多次调用，延迟和成本更低 |
| 在线 MILP | Cerebrum, On-the-fly | 对偶分解避免逐批求解 LP，一次优化后线性评分 |
| BatchSplit | 小批量 LP | PORT 利用全局对偶信息，性能高 33%、吞吐高 24% |
核心区别：PORT 是唯一同时满足"无训练"、"在线"、"有理论保证"三个条件的路由算法。其他方法至少缺少其中一项。
启发与关联¶
- 对偶分解的通用性：将在线资源分配问题转化为"学习对偶变量 → 线性评分"的范式，可迁移到广告竞价、云资源调度、CDN 路由等场景。关键洞察是对偶变量本质是资源的影子价格，学好后可实现去中心化决策。
- ANNS 作为通用特征估计器：不依赖任务特定的训练模型，而是用近邻检索做非参数估计，天然支持增量更新和分布漂移。这种思路可应用于任何需要实时特征估计的在线系统。
- 与 MoE 路由的关联：PORT 的路由权重学习与 MoE 的 gating 机制有相似之处（都是学习将输入分配到不同专家/模型），但 PORT 在系统级而非层级做路由，且有预算约束。
- 探索-利用的工程化：2.5% 探索比例 + PAC 随机路由是经典在线学习理论的工程化实践，为在线 ML 系统设计提供了参考范式。