超越准确性与成本：面向动态工作负载的延迟感知LLM查询路由

# 延迟感知的LLM查询路由：面向动态工作负载 来源：https://arxiv.org/html/2607.18253 \\NAT@set@cites ## 超越准确性与成本：面向动态工作负载的延迟感知LLM查询路由 Akaash R\. Parthasarathy\*卡内基梅隆大学Ankur Mallick微软Gauri Joshi卡内基梅隆大学 ###### 摘要 现代语言查询路由器通过将每条查询分配给能够平衡响应质量与货币成本的模型，来提高推理效率。然而，当前的查询路由器在很大程度上是延迟不可知的，并未考虑模型实例上查询所经历的生成延迟。在实践中，延迟通常由轮询或最短队列优先等负载均衡策略控制，而这些策略并未考虑模型准确性或推理成本。将查询延迟纳入路由具有挑战性，因为它不仅取决于查询的提示长度，还取决于模型实例当前的预填充和解码工作负载，以及服务框架的调度和批处理策略。我们设计了一个轻量级延迟估计器，它模拟服务框架中的自回归令牌批处理过程，并估计查询的首令牌时间（TTFT）。我们将此延迟估计器集成到*一个延迟感知的路由器中，该路由器在为查询分配模型实例时联合优化延迟、准确性和成本*。实验结果表明，这种联合优化在保持与标准负载均衡方法相同延迟的同时，准确-成本效用提升高达40%40\\%。 ## 1 引言 跨大型语言模型（LLM）池路由用户查询是迈向高效利用LLM的有前景的解决方案。给定一个提示或查询，语言查询路由器选择一个模型实例，以最大化预期响应质量，同时控制货币成本（向用户收取的每令牌价格）。例如，简单的查询被发送到较小且更便宜的模型，而较难的查询则被发送到较大且更昂贵的模型。大量工作\[24 (https://arxiv.org/html/2607.18253#bib.bib15),36 (https://arxiv.org/html/2607.18253#bib.bib12),11 (https://arxiv.org/html/2607.18253#bib.bib11),12 (https://arxiv.org/html/2607.18253#bib.bib17),38 (https://arxiv.org/html/2607.18253#bib.bib14)\]研究查询路由，通过使用在池中模型上训练的校准正确性和成本预测器，来在准确性和成本之间取得良好权衡。 #### 延迟感知查询路由的必要性。 除了平衡准确性和成本外，响应生成还应满足基于下游使用或服务级别目标（SLO）的*延迟约束*。大多数现有查询路由器\[36 (https://arxiv.org/html/2607.18253#bib.bib12),11 (https://arxiv.org/html/2607.18253#bib.bib11),24 (https://arxiv.org/html/2607.18253#bib.bib15),12 (https://arxiv.org/html/2607.18253#bib.bib17),38 (https://arxiv.org/html/2607.18253#bib.bib14),10 (https://arxiv.org/html/2607.18253#bib.bib16)\]基于准确性和成本进行模型选择，但延迟不可知。因此，它们可能将查询路由到过载的模型实例，导致排队延迟过长和延迟约束违规。通过跨模型实例的查询负载均衡进行延迟优化通常留给底层系统层处理。系统级延迟优化考虑为查询固定选择语言模型，并专注于将查询分配到同一语言模型的副本。如\[23 (https://arxiv.org/html/2607.18253#bib.bib25),45 (https://arxiv.org/html/2607.18253#bib.bib28),9 (https://arxiv.org/html/2607.18253#bib.bib45)\]等工作在异构硬件上对跨模型部署的请求进行负载均衡。其他工作设计调度策略，根据延迟约束、预测输出长度或模型实例上剩余的解码工作对请求进行优先级排序\[20 (https://arxiv.org/html/2607.18253#bib.bib30),41 (https://arxiv.org/html/2607.18253#bib.bib31),15 (https://arxiv.org/html/2607.18253#bib.bib32),43 (https://arxiv.org/html/2607.18253#bib.bib33),39 (https://arxiv.org/html/2607.18253#bib.bib29)\]。这些系统级路由方法改善了延迟和资源利用率，但它们在固定的查询到模型分配下运行，因此对准确性和成本不可知。在本工作中，我们旨在弥合准确性感知和成本感知路由（延迟不可知）与系统级延迟优化（准确性和成本不可知）之间的差距。*我们设计了一个基于准确性-成本-延迟联合优化的路由框架。* #### 延迟估计的挑战。 将准确性-成本路由扩展到*延迟感知*路由并非易事。虽然现有查询路由器\[24 (https://arxiv.org/html/2607.18253#bib.bib15),38 (https://arxiv.org/html/2607.18253#bib.bib14),11 (https://arxiv.org/html/2607.18253#bib.bib11)\]提供了可靠的准确性和成本估计，但延迟感知路由需要可靠估计将查询分配到模型实例时所经历的延迟。与成本（向用户收取的金额，通常是令牌计数的确定性函数）或准确性（可从历史查询-模型评估中学习）不同，*生成延迟取决于模型实例当前正在服务的查询工作负载*。现代LLM服务框架（例如，vLLM\[26 (https://arxiv.org/html/2607.18253#bib.bib1)\], Sarathi-Serve\[2 (https://arxiv.org/html/2607.18253#bib.bib2)\]）使用连续批处理执行*多个并发请求*，导致在提示令牌KV缓存计算阶段（预填充阶段）和顺序解码令牌生成阶段（解码阶段）中序列的同时处理。查询在模型实例上经历的响应生成速率和延迟取决于 (i) 硬件规格和语言模型架构，(ii) 当前查询的预填充与解码工作负载组成，以及 (iii) 服务框架的批处理和调度策略。 #### 我们的延迟感知路由框架。 我们提出一个路由框架，通过整合每个模型实例上的查询工作负载信息以及底层服务框架使用的调度策略，来估计查询延迟并做出路由决策。我们提出的基于服务框架模拟（SFS）的*首令牌时间*（TTFT）延迟估计器模拟了模型实例在自回归生成过程中令牌批处理组成的演变，并预测新查询产生的延迟。实验表明，我们的延迟感知路由框架实现了有利的准确性-成本-延迟权衡，并优于现有的延迟不可知路由器以及准确性和成本不可知的负载均衡方法。与我们的设置最接近的先前工作是\[27 (https://arxiv.org/html/2607.18253#bib.bib35)\]，它考虑了基于输出长度的延迟估计器，并联合优化响应质量和生成延迟。然而，它没有考虑变化的预填充和解码组成、服务框架策略以及模型实例上的当前工作负载。我们在附录̃A (https://arxiv.org/html/2607.18253#A1)中提供了更详细的先前工作讨论。 #### 论文组织。 本文的其余部分组织如下：第2节 (https://arxiv.org/html/2607.18253#S2)介绍了自回归生成和服务框架的相关背景，第3节 (https://arxiv.org/html/2607.18253#S3)形式化了我们的路由目标和符号，第4节 (https://arxiv.org/html/2607.18253#S4)提出了我们的延迟估计方法，第5节 (https://arxiv.org/html/2607.18253#S5)对延迟感知路由器进行了实证评估，第6节 (https://arxiv.org/html/2607.18253#S6)总结我们的工作并讨论未来方向。 ## 2 LLM服务框架背景 #### 自回归生成。 大多数基于Transformer的语言模型以自回归方式生成序列，通过注意力机制\[47 (https://arxiv.org/html/2607.18253#bib.bib55)\]从输入提示和所有先前生成的令牌预测每个令牌。在计算上，生成分为两个阶段\[40 (https://arxiv.org/html/2607.18253#bib.bib56)\]：*预填充*阶段，输入提示令牌被并行处理以计算键值状态并初始化KV缓存；以及*解码*阶段，输出令牌被顺序生成，新的键值状态被追加到缓存中以供未来的注意力计算。预填充阶段通常是计算密集型，因为提示令牌可以并行处理，而解码阶段通常是内存密集型，因为每一步都需要读取先前令牌的缓存键值状态\[2 (https://arxiv.org/html/2607.18253#bib.bib2),26 (https://arxiv.org/html/2607.18253#bib.bib1)\]。虽然存在其他生成范式，包括基于扩散的生成和非自回归精炼\[18 (https://arxiv.org/html/2607.18253#bib.bib59),28 (https://arxiv.org/html/2607.18253#bib.bib58),30 (https://arxiv.org/html/2607.18253#bib.bib57)\]，我们的分析专注于流行的基于注意力的自回归设置。 #### 批处理组成与生成吞吐量。 为响应查询而生成的计算工作负载批处理是利用GPU并行计算能力的关键方面。朴素的序列级批处理收集查询，并为批处理中的每个查询生成新令牌直到完成。这导致硬件利用率低下，因为批处理中较短的序列需要等待较长的序列完成生成。为了克服这一点，现代服务框架使用连续批处理（ORCA\[50 (https://arxiv.org/html/2607.18253#bib.bib7)\], vLLM\[26 (https://arxiv.org/html/2607.18253#bib.bib1)\]等），其中新提示在生成阶段的令牌迭代（通常简称为“令牌批处理”）边界被接纳，而非朴素批处理中的序列级批处理边界。这意味着新序列的自回归生成可以在其他序列仍在生成时开始。连续批处理带来更好的硬件利用率和更高的吞吐量。 #### 服务框架中的内存与调度机制。 连续批处理需要仔细管理序列中预填充和解码令牌的多样化组成，使得内存分配对于确保高效计算利用至关重要。早期解决方案，如ORCA\[50 (https://arxiv.org/html/2607.18253#bib.bib7)\]，为每个被服务序列的KV缓存保留尽可能最大的上下文长度内存。这导致了过度配置，因为大多数序列并未达到最大上下文长度，导致硬件利用率不佳和吞吐量降低。PagedAttention（用于vLLM）\[26 (https://arxiv.org/html/2607.18253#bib.bib1)\]将虚拟内存风格的分页应用于KV缓存，避免了大型连续预分配，而是动态地为序列分配固定大小的KV缓存块。预填充和解码阶段的异构计算和内存需求允许进一步细化批处理策略。分块预填充\[2 (https://arxiv.org/html/2607.18253#bib.bib2)\]通过将长预填充拆分为更小的块来平衡令牌批处理中的预填充和解码工作，提高硬件利用率和吞吐量，同时避免解码停顿。我们的延迟估计器考虑了这些方面，以产生查询的准确TTFT估计。 ## 3 问题形式化 #### 系统模型与符号。 我们将每个部署的LLM，连同其相关的硬件分配和服务框架，称为一个*模型实例*，索引为j∈Jj\\in\\mathcal\{J\}。对于每个新到达的查询qiq\_\{i\}，路由器估计每个候选模型实例的准确性、成本和首令牌时间（TTFT）延迟，并根据所需的路由目标选择一个实例m\(i\)∈Jm\(i\)\\in\\mathcal\{J\}。我们考虑TTFT延迟，因为它捕获了用户和交互式应用感知到的响应能力。参见说明图1：自回归生成中的TTFT（首令牌时间）。一个新序列（查询）qiq\_\{i\}在时间tt到达模型实例jj（*左*），其预填充计算在时间t\+Wi,jt\\\!\+\\\!W\_\{i,j\}开始（*中*），第一个解码令牌在时间t\+Wi,j\+Pi,jt\\\!\+\\\!W\_\{i,j\}\\\!\+\\\!P\_\{i,j\}生成（*右*）。新序列被排队，直到正在生成的序列释放模型实例上的内存。 #### 生成延迟。 从序列（查询）进入系统到完成生成（通过生成一个<eos>令牌或达到模型上下文长度限制）之间的时间包括三个阶段：排队延迟、预填充时间和解码时间。排队延迟或等待时间是查询预填充计算开始前的空闲期，在此期间它等待先前查询占用的计算和内存资源变得可用。预填充时间表示查询处理和填充KV缓存所需的时间，解码时间表示自回归生成时间。我们考察首令牌时间（TTFT），它表示从查询到达到第一个输出令牌生成的时间。因此，对于模型实例jj上的查询qiq\_\{i\}，TTFT可以表示为Li,jttft=Wi,j\+Pi,j\\displaystyle L^\{\\text\{ttft\}\}\_\{i,j\}\\;=\\;W\_{i,j\}\\;\+\\;P\_\{i,j\}\(1\)其中Wi,jW\_\{i,j\}表示在队列中花费的等待时间，Pi,jP\_\{i,j\}是预填充和第一个解码令牌的计算时间。我们在图̃1 (https://arxiv.org/html/2607.18253#S3.F1)中展示了连续批处理策略下的延迟分解。需要在每个模型实例jj上对给定查询qiq\_\{i\}进行TTFT估计（L^i,jttft\\widehat\{L\}^\{\\text\{ttft\}\}\_\{i,j\}），以便跨模型实例执行延迟感知的路由决策。 #### 准确性与成本估计器。 利用查询在语言模型上的历史评估，我们为未见过的查询训练响应质量和服务成本的估计器（详细信息在第̃B.4节 (https://arxiv.org/html/2607.18253#A2.SS4)中介绍）。对于每个查询qiq\_\{i\}和模型实例jj，我们生成一个准确性估计acc^i,j\\widehat\{\\textrm\{acc\}\}\_\{i,j\}和一个成本估计cost^i,j\\widehat\{\\textrm\{cost\}\}\_\{i,j\}。响应准确性广义上指任务相关的质量度量（如正确性、ROUGE\[32 (https://arxiv.org/html/2607.18253#bib.bib49)\]或BARTScore\[51 (https://arxiv.org/html/2607.18253#bib.bib50)\]）。我们在分析中使用归一化的LLM-as-a-judge\[29 (https://arxiv.org/html/2607.18253#bib.bib42)\]质量分数，范围在\[0,1\]\[0,1\]。我们使用每个模型的每令牌定价来计算生成成本。我们将准确性-成本效用\[24 (https://arxiv.org/html/2607.18253#bib.bib15),38 (https://arxiv.org/html/2607.18253#bib.bib14),19 (https://arxiv.org/html/2607.18253#bib.bib13)\]定义为：U^i,j\(λ\)=acc^i,j−λcost^i,j,\\displaystyle\\widehat\{U\}\_\{i,j\}(\\lambda\)\\;=\\;\\widehat\{\\textrm\{acc\}\}\_\{i,j\}\\-\\lambda\\widehat\{\\textrm\{cost\}\}\_\{i,j\},\(2\)其中λ≥0\\lambda\\geq 0控制响应质量与货币成本之间的权衡。 #### 路由目标与评估协议。 在实际部署中，查询根据下游任务受限于生成延迟要求。因此，我们将主要路由目标定义为最大化准确性-成本效用U^i,j\\widehat\{U\}\_\{i,j\}，同时满足每条查询的首令牌时间（TTFT）约束。令τi\\