Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

Each language version is independently generated for its own context, not a direct translation.

这篇论文主要解决了一个在大模型（LLM）应用中非常现实的问题：如何既省钱、又不卡顿，还能把任务分配给最合适的模型？

想象一下，你是一家大型物流公司的调度中心，你的任务是处理成千上万个包裹（用户提问）。你手上有不同档次的卡车车队（各种大语言模型）：

小卡车：便宜、速度快，但只能运小件或普通货物（小模型，适合简单问题）。
大卡车：昂贵、耗油，但能运重型货物或精密仪器（大模型，适合复杂难题）。
仓库限制：你的停车场（GPU 资源）有限，不能无限停放大卡车。
预算限制：每天运货的总油费（成本）不能超过老板定的上限。

这篇论文就是为了解决如何在这个复杂的限制下，把包裹分派得最完美。

1. 以前的做法有什么问题？（“单兵作战”的弊端）

以前的调度员（现有的路由方法）是**“见一个包，分一个车”**。

做法：来了一个包裹，调度员看一眼，觉得“这个简单，用小卡车”；来了一个难包，觉得“这个难，用大卡车”。
问题：
- 预算失控：如果突然有一批难处理的包裹（比如全是数学题）一起涌进来，调度员全部分给了大卡车。结果瞬间油费爆表，或者大卡车不够用，导致后面简单的包裹也排队等死（延迟）。
- 抗风险差：如果调度员看走眼了（预测不准），把难包分给了小卡车，结果货没送好（回答质量差），这就叫“翻车”。

2. 这篇论文的新方案：批量调度 + 稳健策略

作者提出了一套**“批量调度 + 稳健防御”**的新系统。

A. 批量调度（Batch-Level Routing）：像“拼车”一样统筹

不再是一个个看，而是把一批包裹（比如 100 个）放在一起看。

比喻：就像拼车软件。系统会看这 100 个订单，发现其中有 20 个是急件（难问题），80 个是普通件。
操作：系统会计算：“如果我把 20 个急件分给大卡车，剩下的 80 个普通件分给小卡车，总油费刚好在预算内，而且所有车都坐满了，效率最高。”
优势：即使遇到“恶意”的一批全是难包的订单，系统也能通过调整比例，确保总成本不超标，不会像以前那样瞬间崩溃。

B. 稳健策略（Robust Optimization）：给预测加个“安全垫”

调度员在判断“这个包裹难不难”时，可能会看走眼（预测不准）。

比喻：以前是“我觉得这货重 10 公斤，就派 10 公斤载重的车”。如果实际是 12 公斤，车就爆了。
新做法：系统会想：“虽然我觉得这货重 10 公斤，但万一有误差，它可能重到 12 公斤。为了保险起见，我按最坏情况（12 公斤）来派车。”
效果：这就像开车时预留了更多的刹车距离。虽然有时候可能稍微保守了一点（没完全利用小卡车的潜力），但在面对突发状况或预测不准时，能保证绝不翻车，回答质量更稳定。

C. 离线资源分配（Offline Instance Allocation）：提前规划停车场

在开始运货之前，先决定买多少辆大卡车，多少辆小卡车。

比喻：以前是老板拍脑袋决定：“我们要 10 辆大车，10 辆小车”。
新做法：系统先分析过去一年的订单数据，算出：“如果我们把大车减到 5 辆，把省下的钱和车位多买 20 辆小车，整体效率反而更高。”
优势：根据实际数据动态调整车队配置，避免资源浪费或不够用。

3. 实验结果：真的好用吗？

作者在两个大型测试集上做了实验，结果非常亮眼：

更省钱、更聪明：在同样的预算下，他们的系统比老方法（单兵作战）的回答质量提高了 1% 到 14%。
抗揍：如果遇到“恶意”的一批全是难题的订单，他们的系统比老方法好 24%。
稳如泰山：加上“安全垫”（稳健策略）后，即使预测不准，表现也比那些盲目自信的系统好得多。

总结

这篇论文的核心思想就是：别一个个地瞎忙，要成批地统筹规划；别盲目相信预测，要留好安全余地；别拍脑袋定资源，要看数据做分配。

这就好比一个高明的物流经理，不仅知道怎么省钱，还知道怎么在堵车、暴雨（预测不准）和突发大批量订单（对抗性批次）的情况下，依然能把货准时、完好地送到客户手中。这对于现在企业大规模使用大模型来说，是既经济又可靠的“生存指南”。

Each language version is independently generated for its own context, not a direct translation.

1. 问题背景 (Problem Statement)

随着大语言模型（LLM）在工业界的广泛应用，如何在保证响应质量的同时控制推理成本（货币成本）和硬件资源（如 GPU 容量、并发数）成为关键挑战。

现有方法的局限性：
- 单查询路由（Per-query Routing）的缺陷：现有的路由方法通常针对单个查询独立决策（即公式 1： $\max l(q, m_j) - \lambda \cdot c(q, m_j)$ ）。这种方法在**批量推理（Batched Inference）**场景下表现不佳。
- 成本失控：由于缺乏对批次的整体约束，单查询路由难以严格控制单个批次的总成本。在遇到“对抗性批次”（即多个高难度/高成本查询集中到达）时，容易导致成本激增或超出预算。
- 忽略容量约束：现有方法往往忽略了本地部署模型（受限于 GPU 数量）与云端模型（受限于货币成本）之间的异构性，以及模型实例的并发容量限制。
- 估计不确定性：性能预测器（Estimator）在测试时存在噪声，单点估计可能导致过于自信或保守的路由决策，缺乏鲁棒性。
核心目标：设计一种批量级（Batch-Level）的路由框架，在满足严格的货币成本预算和GPU 容量限制的前提下，最大化批次的平均查询质量，并具备应对性能估计不确定性的鲁棒性。

2. 方法论 (Methodology)

作者提出了一套基于**整数线性规划（Integer Linear Programming, ILP）**的优化框架，包含三个核心组成部分：

2.1 批量级路由优化 (Batch-Level Routing Optimization)

将路由问题建模为一个约束优化问题（公式 2），旨在为批次中的 $N$ 个查询分配 $M$ 个模型。

决策变量： $x_{i,j} \in \{0, 1\}$ ，表示查询 $i$ 是否分配给模型 $j$ 。
目标函数：最大化批次内的平均预测性能 $\frac{1}{N}\sum \sum a_{i,j} x_{i,j}$ 。
约束条件：
1. 成本约束：批次总成本不超过预算 $N \cdot C$ 。
2. 容量约束：每个模型 $j$ 被分配的查询数不超过其实例数 $I_j$ 乘以单实例并发能力 $l_j$ 。
3. 分配约束：每个查询必须且只能分配给一个模型。
求解：使用现成的 ILP 求解器（如 SCIP）在毫秒级时间内求解，适合实时部署。

2.2 鲁棒优化 (Robust Optimization)

为了应对性能估计 $a_{i,j}$ 的不确定性，引入了鲁棒优化变体。

原理：不直接使用点估计值，而是利用**预测区间（Prediction Interval）**的下界 $\underline{a}_{i,j}$ 作为目标函数中的性能值。
实现：通过Bootstrap 重采样生成多个训练集，拟合多个模型，从而构建预测值的分布。鲁棒路由选择该分布的特定分位数（如 10% 分位数，即 $Q=10$ ）作为保守估计。
效果：确保在最坏情况（Worst-case）的估计误差下，系统仍能保持可接受的性能，避免路由到实际表现不佳的模型。

2.3 离线实例分配优化 (Offline Instance Allocation)

在推理之前，预先优化本地部署的模型实例数量 $I_j$ （即分配多少 GPU 给哪些模型）。

问题：在有限的总 GPU 预算下，是部署更多的小模型（提高吞吐量但可能牺牲质量），还是部署少量大模型（保证质量但吞吐量低）？
方法：构建一个离线优化问题（公式 4），利用历史校准批次数据，联合优化实例分配变量 $I_j$ 和路由变量 $x_{i,j}$ ，以最大化模拟环境下的平均性能。
流程：先离线求解最优的 $I_j$ ，固定后，再在线进行实时的批量路由。

2.4 性能估计器

框架兼容多种性能估计方法，文中对比了：

MIRT (Multidimensional Item Response Theory)：基于神经网络的 SOTA 方法。
XGBoost：基于梯度提升树，适合表格数据，训练和推理速度快。
kNN (k-Nearest Neighbors)。
上述方法的鲁棒变体（结合 Bootstrap）。

3. 主要贡献 (Key Contributions)

识别现有缺陷：指出了单查询路由在批量推理和严格资源约束下的根本性不足（成本波动大、无法处理对抗性批次）。
提出鲁棒批量路由框架：基于 ILP 的框架，显式地同时优化成本、硬件容量和查询质量，并引入鲁棒性以应对估计不确定性。
联合优化部署规划：首次将离线资源分配（GPU 实例数量）与在线批量路由结合，填补了离线规划与在线执行之间的空白。
广泛的实证验证：在两个多任务 LLM 基准数据集上进行了全面实验，证明了该方法在稳定性、准确性和资源效率上的优势。

4. 实验结果 (Results)

实验在两个数据集（Dataset 1: 20 个模型，24k+ 查询；Dataset 2: 11 个模型，25k+ 查询）上进行。

鲁棒性提升：
- 相比非鲁棒方法，鲁棒路由（Robust Routing）在准确率上提升了 1% - 14%（取决于估计器和数据集）。
- 鲁棒方法倾向于选择预测不确定性更低（预测区间更短）的模型，从而降低了风险。
- XGBoost 的鲁棒变体在多个场景下表现最佳，甚至优于 SOTA 的 MIRT 路由器和单个最强模型。
批量级 vs. 单查询级：
- 在随机批次下，批量路由比单查询路由提升最高 4%。
- 在对抗性批次（困难查询集中）下，批量路由提升高达 24%。
- 批量路由能严格将每批次成本控制在预算内，而单查询路由在对抗性场景下会导致成本剧烈波动。
实例分配优化：
- 通过离线优化 GPU 实例分配，相比固定分配策略，性能额外提升了 3% 左右。
- 在低预算下，优化器倾向于分配更多小模型实例以维持吞吐量；在高预算下，则分配更多大模型实例以提升质量。
计算效率：
- 使用 SCIP 求解器，处理大规模批次（如 $B=400$ ）仅需 0.4 秒 以内，证明了该方法在实际生产环境中的可行性。

5. 意义与影响 (Significance)

工业级适用性：该研究直接针对工业界（如 LinkedIn、Apple 等）面临的实际痛点：如何在混合云/本地部署架构下，平衡成本、延迟和质量。
资源效率：通过显式的容量约束和实例优化，避免了资源浪费（如过度使用昂贵模型或 GPU 闲置），显著降低了推理成本。
稳定性保障：鲁棒优化机制确保了系统在模型预测不准或遇到极端查询分布时，仍能保持服务质量的底线，这对生产环境至关重要。
方法论创新：将整数规划引入 LLM 路由，并成功解决了其计算复杂度问题，为后续研究提供了新的范式（从单点决策转向全局批量优化）。

局限性：
论文也承认了当前方法的局限，包括假设查询是独立的（未考虑多轮对话的上下文切换开销）、假设分布是静态的（未考虑分布漂移）、以及基于离线基准的评估可能与实时动态流式请求存在差异。未来的工作将致力于解决动态流式处理和分布适应问题。