1. 论文基本信息

1.1. 标题

MuxServe: Flexible Spatial-Temporal Multiplexing for Multiple LLM Serving （MuxServe：面向多大型语言模型服务的灵活时空复用）

1.2. 作者

Jiangfei Duan, Runyu Lu, Haojie Duanmu, Xiuhong Li, Xingcheng Zhang, Dahua Lin, Ion Stoica, Hao Zhang。 作者来自多个机构，包括上海人工智能实验室 (Shanghai AI Laboratory)、香港中文大学 (CUHK Interdisciplinary AI Research Institute)、加州大学伯克利分校 (UC Berkeley) 等。

1.3. 发表期刊/会议

该论文目前作为预印本 (preprint) 发布在 arXiv 上，尚未在正式期刊或会议上发表。其发布时间为 2024-04-02T14:56:43.000Z。

1.4. 发表年份

2024年。

1.5. 摘要

大型语言模型 (LLM) 展现了卓越的性能，各组织正竞相将其各种尺寸的 LLM 作为端点 (endpoints) 进行服务，以支持聊天、编程和搜索等用例。然而，由于 LLM 流行度的差异，高效服务多个 LLM 对现有方法构成了巨大挑战。本文提出 MuxServe，一个灵活的时空复用 (spatial-temporal multiplexing) 系统，用于高效服务多个 LLM。其核心思想是：根据 LLM 的流行度将其并置 (colocate)，以复用内存资源 (memory resources)；同时利用预填充 (prefill) 和解码 (decoding) 阶段的特性，将它们分离并灵活并置，以复用计算资源 (computation resources)。MuxServe 正式地形式化了复用问题，并提出了一种新颖的放置算法 (placement algorithm) 和自适应批调度策略 (adaptive batch scheduling strategy)，以识别最优并置并最大化资源利用率。MuxServe 设计了一个统一资源管理器 (unified resource manager) 来实现灵活高效的复用。评估结果表明，MuxServe 在 99% 的服务水平目标 (SLO) 达成率下，可实现高达 $1.8 \times$ 的吞吐量提升或处理 $2.9 \times$ 更多的请求。

1.6. 原文链接

• 原文链接: https://arxiv.org/abs/2404.02015
• PDF 链接: https://arxiv.org/pdf/2404.02015v2.pdf

2. 整体概括

2.1. 研究背景与动机

2.1.1. 论文试图解决的核心问题

论文旨在解决在 GPU 集群上高效服务多个大型语言模型 (LLMs) 的挑战。由于 LLMs 规模庞大、推理成本高昂，且不同 LLMs 的用户请求量和流行度差异巨大，现有服务方法往往导致 GPU 资源利用率低下。

2.1.2. 问题的重要性及现有挑战

LLMs 在人工智能行业中扮演着越来越重要的角色，各种规模和版本的 LLMs 被开发出来以支持多样化的应用场景。将这些 LLMs 作为服务端点提供给用户是业界的一个核心需求。然而，LLMs 的推理成本极高（例如，一个 175B 参数的 LLM 需要 8 块 A100 80GB GPU），同时服务多个 LLM 的成本更是天文数字。现有方法主要面临以下挑战：

• 空间划分 (Spatial Partitioning)：为每个 LLM 分配独立的 GPU 组。这种方法简单直观，但当 LLM 的请求率较低时，会导致其分配到的 GPU 闲置，资源利用率极低（参见原文 Figure 1a 和 Figure 2）。而流行度高的 LLM 可能会因资源不足而成为性能瓶颈。
• 时间复用 (Temporal Multiplexing)：多个模型共享一组 GPU，通过交错调度请求来共享计算和内存资源。这种方法可以处理突发工作负载，但它忽略了 LLM 推理的预填充 (prefill) 和解码 (decoding) 阶段的独特特性。解码阶段通常计算需求较少，导致 GPU 利用率呈波浪状变化，大部分时间处于低谷（参见原文 Figure 1b 和 Figure 3）。

2.1.3. 论文的切入点或创新思路

MuxServe 的创新点在于提出了灵活的时空复用 (flexible spatial-temporal multiplexing) 策略，以提高 GPU 利用率。其核心思路基于两个关键洞察：

1. 流行度感知的内存资源复用 (Popularity-aware Memory Multiplexing)：根据 LLM 的流行度将它们并置，以更有效地共享和复用内存资源，尤其是庞大的 KV 缓存 (KV cache)。
2. 预填充/解码阶段分离的计算资源复用 (Prefill/Decoding Phase Separation for Computation Multiplexing)：利用预填充和解码阶段不同的计算特性，将它们视为不同的任务，并灵活地并置来自不同 LLM 的预填充或解码任务，从而复用计算资源。例如，当一个 LLM 处于计算需求较低的解码阶段时，可以调度另一个 LLM 的请求，以填充计算资源的空闲。

2.2. 核心贡献/主要发现

2.2.1. 主要贡献

1. 首次探索 LLM 服务的时空复用并形式化问题 (First to explore spatial-temporal multiplexing for LLM serving and formally formulate the problem)：MuxServe 是第一个探索并正式形式化 LLM 服务中时空复用问题的系统，打破了传统空间划分和单纯时间复用的局限性。
2. 新颖的放置算法和自适应批调度策略 (A novel placement algorithm and adaptive batch scheduling strategy)：提出了一个基于枚举的贪婪放置算法来确定 LLM 的最佳并置，以及一个自适应批调度 (ADBS) 策略来最大化单元内吞吐量并确保 LLM 间的公平性。
3. 可行的系统设计与实现及统一资源管理器 (A viable system design and implementation with unified resource manager)：设计并实现了一个具有统一资源管理器的系统，能够高效、灵活地复用 LLM，并通过全面的评估验证了其有效性。

2.2.2. 关键结论或发现

MuxServe 在实际工作负载和合成工作负载下的评估结果显示出显著的性能提升：

• 与现有最先进系统相比，MuxServe 可以实现高达 $1.8 \times$ 的吞吐量提升。
• 在 99% 的服务水平目标 (SLO) 达成率下，MuxServe 能够处理高达 $2.9 \times$ 更多的请求。
• 消融实验 (Ablation Studies) 验证了其放置算法、自适应批调度机制和统一资源管理器的各个组件的有效性。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 大型语言模型 (Large Language Models, LLMs)

LLMs 是指拥有数亿甚至数千亿参数的深度学习模型，通常基于 Transformer (Transformer) 架构。它们通过在海量文本数据上进行预训练，学习语言的统计规律和知识，从而能够执行各种自然语言处理任务，如文本生成、问答、翻译和代码编写等。LLMs 的强大能力使其在人工智能领域引起了革命性的变革，但也带来了巨大的计算和内存开销。

3.1.2. Transformer 架构

Transformer 是一种由注意力机制 (attention mechanism) 驱动的神经网络架构，它完全摒弃了传统的循环神经网络 (RNN) 和卷积神经网络 (CNN) 结构。LLMs 大多基于 Transformer 架构构建。Transformer 的核心组件是：

• 多头注意力 (Multi-head Attention)：允许模型在处理序列时，同时关注输入序列的不同部分，并从不同表示子空间学习信息。
• 前馈网络 (Feed-Forward Networks)：对注意力机制的输出进行非线性变换。 每个 Transformer 块由多头注意力和前馈网络组成，LLMs 通过堆叠大量的 Transformer 块来实现其强大的能力。

3.1.3. LLM 推理阶段：预填充与解码 (Prefill and Decoding)

LLMs 的自回归 (autoregressive) 推理过程通常分为两个主要阶段：

• 预填充阶段 (Prefill Phase)：在生成第一个输出词元 (token) 之前，模型需要一次性处理整个输入提示 (prompt)。这个阶段通常涉及对长输入序列的并行计算，因此对计算资源 (computation resources) 的需求非常高。
• 增量解码阶段 (Incremental Decoding Phase)：生成第一个词元后，模型会根据当前已生成的序列逐步生成后续的词元，每次生成一个词元。这个阶段的核心特点是迭代 (iterative)。虽然每次迭代的计算量相对较小，但由于需要生成较长的输出序列，且每次迭代都需要访问并更新键值缓存 (KV cache)，因此总体上在推理过程中占据了大量时间，并且对内存带宽 (memory bandwidth) 和 KV 缓存管理有较高要求，但往往无法充分利用 GPU 的计算单元 (Streaming Multiprocessors, SMs)。

3.1.4. 分布式 LLM 推理 (Distributed LLM Inference)

当 LLM 的规模过大，无法在单个 GPU 上容纳或需要加速推理时，会采用分布式推理技术，主要包括：

• 算子内并行 (Intra-operator Parallelism)：将单个 LLM 层内部的操作（如矩阵乘法）拆分到多个 GPU 上并行执行。例如，将一个大的权重矩阵分成多个小块，由不同的 GPU 分别计算，然后通过集体通信 (collective communications) 同步结果。这能显著减少推理延迟，但会引入额外的通信开销。
• 算子间并行/流水线并行 (Inter-operator Parallelism/Pipeline Parallelism)：将 LLM 的不同层（或阶段）分配到不同的 GPU 上，形成一个处理流水线 (pipeline)。每个 GPU 负责流水线中的一个阶段，数据流经整个流水线。这种方法开销较小，但可能不会直接减少单个请求的延迟，而是通过提高吞吐量来提升效率。

3.1.5. 复用 (Multiplexing)

复用是一种资源共享技术，允许多个任务或模型共享同一组硬件资源，以提高效率和利用率。

• 空间复用 (Spatial Multiplexing)：将 GPU 资源（如内存或流式多处理器 SMs）划分为多个独立的逻辑分区，每个分区分配给不同的任务并行执行。NVIDIA 的 多实例 GPU (Multi-Instance GPU, MIG) 允许将一个物理 GPU 划分为多个独立的 GPU 实例，每个实例拥有独立的内存和计算资源。
• 时间复用 (Temporal Multiplexing)：多个任务轮流占用整个 GPU 的计算资源，但在不同的时间段执行。通过快速切换任务，可以在宏观上实现资源的共享，适用于突发性工作负载。
• NVIDIA CUDA MPS (Multi-Process Service)：一种允许多个 CUDA 进程同时运行在同一个 GPU 上的机制。MPS 可以将 GPU 的 SMs 资源分配给不同的进程，从而实现计算资源的共享。

3.1.6. 键值缓存 (Key-Value Cache, KV Cache)

在自回归生成过程中，Transformer 模型的自注意力层会计算输入词元序列的键 (key) 和值 (value) 矩阵。为了避免在每个解码步骤中重新计算整个序列的键和值，这些矩阵会被缓存起来，称为 KV 缓存。KV 缓存的大小随着生成词元的数量线性增长，对于长输出序列，KV 缓存会占用大量 GPU 内存，成为 LLM 服务中的主要内存瓶颈之一。

3.1.7. 服务水平目标 (Service Level Objective, SLO)

服务水平目标是衡量服务性能的关键指标，通常以延迟 (latency) 为标准。例如，一个 SLO 可能要求 99% 的请求在 100 毫秒内完成响应。SLO 达成率 (SLO Attainment) 则衡量实际完成时间满足 SLO 要求的请求所占的百分比。

3.2. 前人工作

3.2.1. 传统 DL 服务系统

传统的深度学习 (Deep Learning, DL) 服务系统（如 Clipper, Nexus, INFaaS 等）通常通过时间复用、更好的批处理 (batching) 和调度策略来提高 GPU 利用率并满足 SLO。然而，这些系统主要关注中小型 DNN 模型，并未充分考虑 LLM 带来的大规模并行需求和独特的推理阶段特性。

3.2.2. LLM 服务系统

近年来，涌现了大量专注于优化 LLM 推理的系统：

• 优化 Transformer 内核 (Optimized Transformer Kernels)：如 TensorRT-LLM (NVIDIA, 2023b) 和 LightSeq (Wang et al., 2021b)，它们通过定制 GPU 内核来加速 Transformer 模型的推理。
• 并行化 (Parallelism)：如 FasterTransformer (NVIDIA, 2021), DeepSpeed-Inference (Aminabadi et al., 2022), vLLM (Kwon et al., 2023) 和 TGI (Huggingface, 2023)，这些系统通过结合算子内并行和算子间并行来加速多 GPU 上的 LLM 推理。
• 内存管理 (Memory Management)：vLLM (Kwon et al., 2023) 提出的 PagedAttention 机制，通过将 KV 缓存以页 (page) 的形式管理，显著提高了单个 LLM 服务的内存利用率，减少了内存碎片。
• 其他优化技术 (Other Optimization Techniques)：包括卸载 (offloading) (Sheng et al., 2023), 迭代级批处理 (iteration-level batching) (Yu et al., 2022), 推测解码 (speculative decoding) (Miao et al., 2023) 和廉价实例 (cheap instances) (Miao et al., 2024) 等，这些都旨在提升单个 LLM 的吞吐量和降低成本。 MuxServe 与这些工作正交 (orthogonal)，因为它关注的是如何高效地同时服务多个 LLM，而非仅仅优化单个 LLM 的推理。

3.2.3. GPU 共享

GPU 共享技术主要分为时间共享和空间共享：

• 时间共享 (Temporal Sharing)：如 Salus (Yu & Chowdhury, 2019) 提出的快速作业切换和内存管理，用于促进时间共享。
• 空间共享 (Spatial Sharing)：NVIDIA 的 MIG (NVIDIA, 2022a) 和 MPS (NVIDIA, 2022b) 是原生的 GPU 复用支持。GSLICE (Dhakal et al., 2020) 提出了一个动态 GPU 资源分配和管理框架。
• 混合时空共享 (Mixed Spatial-Temporal Sharing)：Gpulet (Choi et al., 2022) 引入了混合时空共享来复用作业。 这些现有工作主要针对复用小型 DNN 作业，而 MuxServe 则专注于在新兴的 LLM 服务应用中探索灵活的时空复用。

3.2.4. AlpaServe (Li et al., 2023)

这是与 MuxServe 最为相关的工作之一。AlpaServe 探索了并行性 (parallelism) 空间，并使用时间复用技术来服务多个大型 DNN 模型。然而，AlpaServe 并非专为 LLM 设计，它忽略了 LLM 推理阶段（预填充和解码）的独特特性。如图 3 所示，当分配给主导解码阶段的计算资源减少时，延迟或吞吐量不会大幅下降。此外，多 GPU 并行化进一步降低了 LLM 的计算需求。因此，时间复用会导致严重的资源利用率不足。MuxServe 正是为了解决这一问题而设计的。

3.3. 技术演进

LLM 服务技术的发展历程大致如下：

1. 早期 DL 服务系统：关注通用 DNN 模型，主要通过批处理和简单的调度优化 GPU 利用率。
2. 单 LLM 优化：随着 LLM 规模增大，出现专门针对单个 LLM 推理的优化，包括定制内核、各种并行策略、高效内存管理（如 PagedAttention）、推测解码等，以提升单个模型的吞吐量和降低延迟。
3. 多模型服务挑战浮现：当需要同时服务多个不同 LLM 时，传统的空间划分和单纯的时间复用暴露出效率瓶颈，尤其是在 LLM 流行度差异大和推理阶段特性未被充分利用的情况下。
4. MuxServe 的提出：MuxServe 代表了向更高级别的多 LLM 服务优化迈进，它综合考虑了 LLM 的流行度、预填充/解码阶段差异，并结合时空复用策略，旨在解决现有方法的局限性，实现更极致的资源利用率。

3.4. 差异化分析

MuxServe 与上述现有工作的核心区别和创新点在于：

• 对 LLM 推理阶段的深度洞察：MuxServe 明确区分了计算密集型预填充阶段和内存/带宽密集型解码阶段，并在此基础上设计了灵活的计算资源复用策略，这是 AlpaServe 等时间复用方法所忽视的。
• 流行度感知的内存资源复用：MuxServe 认识到不同 LLM 流行度的差异会导致空间划分的低效，并提出根据流行度进行 LLM 并置，从而更高效地复用内存资源，这在现有工作中是独有的。
• 统一的头级 KV 缓存 (Head-wise KV Cache)：MuxServe 提出的统一 KV 缓存和头级缓存机制，允许不同 LLM 在统一空间内共享 KV 缓存，并能动态调整分配，这与 vLLM 的 PagedAttention 专注于单个 LLM 内存优化的场景不同。
• 系统级的时空复用：MuxServe 不仅在概念上提出了时空复用，更通过其放置算法、ADBS 调度器和统一资源管理器在系统层面实现了这一复杂的复用策略，以在多 LLM 服务场景中同时优化吞吐量、延迟和资源利用率。

4. 方法论

MuxServe 旨在通过灵活的时空复用（spatial-temporal multiplexing）来高效服务多个大型语言模型（LLMs）。其核心思想是根据 LLM 的流行度（popularity）来并置（colocate）它们，以复用内存资源；同时利用预填充（prefill）和解码（decoding）阶段的特性，将它们分离并灵活并置，以复用计算资源。

4.1. 方法原理

MuxServe 的方法原理基于以下两个关键洞察：

1. LLM 流行度差异导致内存复用机会：不同 LLM 的请求到达率差异巨大，热门 LLM 和非热门 LLM 同时存在。如果将热门 LLM 与非热门 LLM 并置，可以在内存资源分配上进行更细致的权衡和共享，提高整体内存利用率。

2. 预填充与解码阶段计算特性差异导致计算复用机会：LLM 推理的预填充阶段通常是计算密集型的，需要大量流式多处理器（SMs），而增量解码阶段虽然在整个推理过程中耗时较长，但每次迭代的计算量相对较小，往往无法充分利用 GPU 的所有 SMs。这为在解码阶段的空闲 SMs 上调度其他 LLM 的预填充或解码任务提供了机会，从而实现计算资源的灵活复用。

   MuxServe 将这些洞察转化为一个系统性的解决方案，通过形式化问题、设计放置算法、自适应调度策略和统一资源管理器来最大化 GPU 利用率和吞吐量。

4.2. 核心方法详解

4.2.1. 问题形式化 (Problem Formulation)

MuxServe 首先将多 LLM 服务问题形式化为一个优化问题。 假设我们有一个集群 $C$ 和一组需要服务的 LLM 集合 $M$ 及其对应的工作负载 $W$。MuxServe 的一个核心洞察是根据 LLM 的流行度进行并置，以提高资源利用率。为此，引入了LLM 单元 (LLM unit) 的概念，它指的是一组将并置在一起的 LLM，以及它们被分配到的 GPU。目标是找到最优的 LLM 单元组 $B^*$，以最大化 GPU 利用率（即吞吐量）。

该问题形式化为： $$B ^ { * } = \underset { B \in \mathbb{B} } { \arg \operatorname* { m a x } } \sum _ { b \in B } F ( b , W _ { b } )$$ 其中：

• $B^*$：最优的 LLM 单元组。

• $\mathbb{B}$：所有可能的 LLM 单元组的集合。

• $B$：一个具体的 LLM 单元组。

• $b \in B$：LLM 单元组 $B$ 中的一个 LLM 单元。

• $F(b, W_b)$：估计 LLM 单元 $b$ 在工作负载 $W_b$ 下的吞吐量。

  在一个 LLM 单元内部，MuxServe 利用预填充和解码阶段的特性，将它们分离为预填充作业 (prefill jobs) 和解码作业 (decoding jobs)。每个作业占用固定数量的 SM 资源，并为 LLM 的一批请求执行预填充或解码步骤。不同的作业可以灵活并置，以共享计算和内存资源。然而，由于多个 LLM 具有不同的工作负载特性，不同的批处理和调度策略会导致不同的吞吐量，并且不同 LLM 之间也可能存在资源竞争。因此，给定一个包含并置 LLM $b_{llm}$ 的 LLM 单元 $b$，需要找到最优的批处理和调度策略 $S$，以最大化整个单元的吞吐量，同时确保单元内 LLM 之间的公平资源共享。

单元内吞吐量最大化问题 $\mathbb { E } ( b , W _ { b } )$ 形式化为： $$\begin{array} { r l r } { F ( b , W _ { b } ) = \operatorname* { m a x } _ { S } \sum _ { m \in b _ { l l m } } \mathrm { t p t } _ { S } ( m , b , W _ { b } ) \quad s . t . } \\ & { } & \\ & { | \mathrm { R } ( m _ { i } , W _ { m _ { i } } ) - \mathrm { R } ( m _ { j } , W _ { m _ { j } } ) | \le \epsilon , \forall m _ { i } , m _ { j } \in b _ { l l m } } \end{array}$$ 其中：

• $F(b, W_b)$：LLM 单元 $b$ 在工作负载 $W_b$ 下的吞吐量。
• $S$：批处理和调度策略。
• $b_{llm}$：LLM 单元 $b$ 中并置的 LLM 集合。
• $\mathrm{tpt}_S(m, b, W_b)$：使用策略 $S$ 时，LLM 单元 $b$ 中 LLM $m$ 在工作负载 $W_b$ 下的吞吐量。
• $R(m, W_m)$：LLM $m$ 在工作负载 $W_m$ 下的归一化计算或内存资源消耗。这个值用于衡量公平性，因为它考虑了不同 LLM 的规模和流行度。
• $\epsilon$：一个很小的正数，确保单元内不同 LLM 之间的公平资源共享，即它们的归一化资源消耗差异不超过 $\epsilon$。

4.2.2. 放置算法 (Placement Algorithm)

确定最优的 LLM 单元组是一个具有挑战性的组合优化问题，因为设备和 LLM 的数量增加会导致组合数量呈指数增长。MuxServe 设计了一个基于枚举的贪婪算法来高效解决 Equation (1)，其核心思想是优先处理计算需求大的 LLM（综合考虑模型规模和流行度）。

以下是放置算法的伪代码，来源于原文 Algorithm 1：

$$Algorithm 1 Enumeration-based Greedy LLM Placement Input: LLM list M, cluster C, workload W Output: The optimal group of LLM unit best_units 1: M̂ ← llm_parallel_candidate(M, W ) // Algorithm 2 2: D ← get_potential_device_mesh_groups(C, M) 3: best_tpt, best_units ← 0, None 4: for D ∈ D do // Greedily place LLMs on mesh group D 5: M′=sort(M̂, key=computation, descend=True) 6: for m ∈ M′ do 7: best_mesh, max_delta ← None, -1 8: for d ∈ D do 9: u = make_unit(m, d) 10: delta = F(u, W_u) - F(d.u, W_{d.u}) 11: if delta > max_delta then 12: best_mesh, max_delta = d, delta 13: end if 14: end for 15: best_mesh.u = make_unit(m, best_mesh) 16: end for 17: tpt = sum(F(d.u, W_{d.u}) for d ∈ D) 18: if tpt > best_tpt then 19: best_tpt, best_units = tpt, D 20: end if 21: end for 22: return best_units$$ 算法步骤详解：

1. 并行候选生成 (Line 1)：MuxServe 首先调用 llm_parallel_candidate(M, W) (Algorithm 2) 来为每个 LLM $m$ 生成所有可能的并行化配置候选 $\hat{M}$。一个并行化候选是指一个在满足工作负载要求的同时，使用最少 SMs 数量的配置。

   Algorithm 2 LLM Parallel Candidate Generation
   Input: LLM list M, workload W 
   Output: The parallel candidate M̂
   
   1: M̂ ← []
   2: for m ∈ M do
   3:     sm_list ← get_potential_sm_list(m)
   4:     tp_list ← get_potential_tp_degree(m)
   5:     for p ∈ tp_list do
   6:         for num_sm ∈ sorted(sm_list) do
   7:             tpt, bs ← estimate_throughput(m, num_sm, p)
   8:             // Add (m, num_sm, p, tpt, bs) as a candidate to M̂ if optimal
   9:         end for
   10:    end for
   11: end for
   12: return M̂
   

   对于每个 LLM $m$，get_potential_sm_list(m) 返回可能的 SM 数量列表，get_potential_tp_degree(m) 返回可能的算子内并行度列表。然后，MuxServe 枚举这些组合，并调用 estimate_throughput 来评估在不同 SM 数量和并行度下的吞吐量和批处理大小。最终，为每个 LLM 生成满足工作负载要求的最优并行化配置候选。

2. 设备网格组枚举 (Line 2)：MuxServe 调用 get_potential_device_mesh_groups(C, M) 来获取所有潜在的设备网格组 $D$。每个网格由多个 GPU 组成，用于同时服务一组 LLM。

3. 贪婪放置 (Lines 4-16)：对于每一个潜在的设备网格组 $D$：

   • 排序 LLM (Line 5)：将 LLM 候选 $\hat{M}$ 按照计算需求（包括模型规模和流行度）降序排列，得到 $M'$。这是因为计算需求大的 LLM 在放置时更具约束性，优先放置可以最大化整体服务利用率。
   • 迭代放置 (Lines 6-16)：对于 $M'$ 中的每个 LLM $m$：
     • 寻找最佳网格 (Lines 7-14)：MuxServe 迭代所有可用的网格 $d \in D$，并近似计算将 LLM $m$ 放置在该网格上所带来的预期吞吐量增量 delta。delta 的计算方式是：将 LLM $m$ 放置在网格 $d$ 后单元 $u$ 的吞吐量 $F(u, W_u)$ 减去网格 $d$ 原有单元 d.u 的吞吐量 $F(d.u, W_{d.u})$。
     • 放置 LLM (Line 15)：LLM $m$ 被放置在能带来最大吞吐量增量 max_delta 的网格 best_mesh 上。
   • 评估总吞吐量 (Line 17)：在所有 LLM 都放置完毕后，计算当前设备网格组 $D$ 下所有 LLM 单元的总吞吐量 tpt。

4. 选择最优组 (Lines 18-20)：比较不同设备网格组的总吞吐量 tpt，选择能提供最佳服务吞吐量的设备网格组作为最优的 best_units。

算法复杂度与剪枝： 该算法的复杂度为 $O(MCD)$，其中 $M$ 是 LLM 的数量，$C$ 是设备的数量，$D$ 是潜在设备网格组的数量。对于大型集群，$D$ 可能会很大，因此 MuxServe 采用以下启发式方法有效剪枝搜索空间：

• 算子内并行 (Intra-operator parallelism) 通常在节点内部采用。
• 工作负载 (workload) 对可能的网格大小施加了约束。

4.2.3. 最大化单元内吞吐量 (Maximize Intra-unit Throughput)

当一个 LLM 单元内并置了多个 LLM，且请求到达时间动态变化时，找到最优的调度策略并非易事，主要挑战包括：不同 LLM 的请求无法批处理在一起；单元内的 LLM 具有不同的工作负载特性；不同 LLM 之间存在资源竞争。

1. 资源消耗度量 $R(\cdot, \cdot)$：为了解决这些挑战，MuxServe 将 $R(\cdot, \cdot)$ 定义为 LLM 的词元块使用量 (token block usage) (Sheng et al., 2024)。这是基于 KV 缓存大小是 LLM 服务中显著的性能瓶颈的观察。MuxServe 为每个 LLM 分配一个词元块配额 (token block quota) 以确保公平共享。通过计算词元块，可以更直观地考虑不同 LLM 的规模，因为不同 LLM 的词元消耗的 KV 缓存量不同。此外，$R(\cdot, \cdot)$ 还通过请求率进行归一化，以考虑工作负载特性的变化。

2. 调度策略：MuxServe 通过探索预填充-解码并置 (prefill-decoding collocation) 和解码-解码并置 (decoding-decoding collocation) 来最大化单元内吞吐量。MuxServe 优先处理预填充作业 (prefill jobs)，然后用解码作业 (decoding jobs) 填充剩余资源。这是因为单个 LLM 的解码作业通常只需要较少的计算资源，并且可以批处理。优先处理预填充作业可以最大化并置和批处理的机会。

   以下是自适应批调度 (Adaptive Batch Scheduling, ADBS) 算法的伪代码，来源于原文 Algorithm 3：

Algorithm 3 Adaptive Batch Scheduling (ADBS)   
Input: LLM list M

1: prefill_waiting ← false
2: quota ← init_token_block_quota(M)
3: while True do
4:     if no prefill jobs in execution then
5:         prefill_waiting ← True
6:         m ← round-robin a prefill job from M
7:         if resource_enough(m, quota) then
8:             execute_and_update(m, quota)
9:             prefill_waiting ← False
10:        end if
11:    end if
12:    if not prefill_waiting then
13:        m ← round-robin a decoding job from M
14:        while resource_enough(m, quota) do
15:            execute_and_update(m, quota)
16:            m ← round-robin a decoding job from M
17:        end while
18:    end if
19: end while

ADBS 算法步骤详解：

1. 初始化 (Line 1-2)：prefill_waiting 标志设置为 false。quota 被初始化为每个 LLM 的词元块配额。
2. 主循环 (Line 3)：算法在一个无限循环中运行，持续调度作业。
3. 预填充作业调度 (Lines 4-11)：
   • 如果当前没有预填充作业在执行 (no prefill jobs in execution)，则将 prefill_waiting 设置为 True。
   • 通过轮询 (round-robin) 方式从 LLM 列表 $M$ 中选择一个预填充作业 $m$。
   • 检查资源是否充足 (resource_enough(m, quota))。如果资源充足，则执行作业 (execute_and_update(m, quota)) 并更新资源使用情况，然后将 prefill_waiting 设置为 False。
4. 解码作业调度 (Lines 12-17)：
   • 如果 prefill_waiting 为 False（即有预填充作业在执行或刚刚执行完毕），或者即使有预填充作业在执行，但计算资源仍有空闲，则开始调度解码作业。
   • 通过轮询 (round-robin) 方式从 LLM 列表 $M$ 中选择一个解码作业 $m$。
   • 只要资源充足 (resource_enough(m, quota) )，就持续执行解码作业并更新资源，然后继续选择下一个解码作业，直到资源不足以调度更多解码作业。

动态配额调整： 为了进一步提高利用率，ADBS 会周期性地调整每个 LLM 的词元块配额。在运行时，MuxServe 监控 KV 缓存的利用率。它识别低利用率的 LLM，并主动将这些 LLM 的 KV 缓存块转移给高利用率的 LLM。这种 KV 缓存块的动态重新分配确保了资源的优化利用和 LLM 单元内的有效共享。

吞吐量估计器 (Throughput Estimator)： 由于在没有实际运行的情况下难以获得准确的吞吐量 $\mathrm{tpt}_S(\cdot, \cdot, \cdot)$，MuxServe 构建了一个简单而有效的分析估计器来估计 LLM $m$ 的吞吐量： $$\mathsf { t p t } _ { S } ( m , b , W _ { b } ) = \min \left\{ \frac { b ^ { m } } { \sum _ { i \in b } t _ { p } ^ { i } + t _ { d } ^ { m } \cdot l _ { o } ^ { m } } , W _ { b } \right\}$$ 其中：

• $b^m$：LLM $m$ 的批处理请求大小。
• $t_p^i$：单元 $b$ 中 LLM $i$ 的预填充延迟。
• $t_d^m$：LLM $m$ 的解码延迟。
• $l_o^m$：LLM $m$ 的平均生成长度（输出词元数量）。
• $W_b$：LLM 单元 $b$ 的工作负载（请求到达率）。
• $\sum_{i \in b} t_p^i$：单元内所有 LLM 预填充阶段的延迟总和。
• $t_d^m \cdot l_o^m$：LLM $m$ 的解码阶段的总延迟。

公式解释： 这个公式基于以下观察：

1. 不同 LLM 的预填充阶段通常是顺序执行 (sequentially executed) 的。
2. 解码阶段可以在一定程度上并发执行 (concurrently executed)。
3. 不同阶段是交错 (interleaved) 的。 因此，一批请求的延迟近似等于所有预填充阶段的延迟总和加上该 LLM 的解码阶段延迟。预填充和解码延迟可以通过预先进行性能分析 (profiling) 获得。平均生成长度可以从历史请求数据或特定数据集（如 ShareGPT）中估计。给定请求到达率 $W_b$，可以通过二分搜索 (binary search) 来找到满足流量的批处理大小 $b^m$。

4.2.4. 资源管理器 (Resource Manager)

在确定了最优的 LLM 单元和批处理调度策略后，MuxServe 需要一种新的机制来支持 LLM 的灵活高效时空复用。这主要面临以下挑战：

• 不同的预填充和解码作业需要灵活共享计算资源。

• 需要共享模型权重和 KV 缓存，以减少内存浪费和碎片。

  为了应对这些挑战，MuxServe 提出了一个统一资源管理器 (unified resource manager)。每个 LLM 单元都运行一个统一资源管理器。下图（原文 Figure 4）展示了一个 LLM 单元中 GPU 资源管理的概览。

  该图像是示意图，展示了LLM单元中的GPU资源管理。内存空间被划分为统一KV缓存、模型权重和激活，底部展示了并行运行时。图中标示了SM资源的动态分配过程。步骤1和步骤2分别显示了资源分配的不同状态。

Figure 4. Overview of GPU resource management in an LLM unit. The memory is divided into 3 partitions to store KV cache, weights and activations, respectively. The parallel runtime partitions SM dynamically to different jobs.

图 4 解释：

• 内存分区 (Memory Partitions)：GPU 内存被分为三个分区，分别用于存储 KV 缓存、模型权重和激活 (activations)。
• 并行运行时 (Parallel Runtime)：负责管理计算资源，并动态地将流式多处理器 (SMs) 分配给不同的作业。

详细管理机制：

1. 计算资源管理 (Computation Resource Management)：

   • 并行运行时 (parallel runtime) 基于 NVIDIA MPS (Multi-Process Service) 以 SM 为粒度管理 LLM 单元的计算资源。
   • MuxServe 使用 ADBS 算法调度来自并置 LLM 的预填充和解码作业，然后并行运行时在运行时动态地为每个作业分配 SMs，而不是静态分配。这使得 MuxServe 能够灵活地复用不同 LLM 的执行。
   • 动态 SM 分配示例 (图 4 右侧)：
     • Step 1：一个作业由于其计算强度大，所有 SMs 都被分配给它。
     • Step 2：执行完成后，MuxServe 调度两个可以并发执行的作业来共享 SM 资源。这展示了如何根据作业需求动态调整 SM 分配。

2. 内存资源管理 (Memory Resource Management)：

   • 主要挑战是减少内存浪费和碎片。LLM 权重和 KV 缓存消耗大量内存，需要跨作业共享。此外，KV 缓存动态增长，不同 LLM 由于注意力头 (attention heads)、隐藏层 (hidden layers) 和隐藏维度 (hidden sizes) 的差异，其 KV 缓存大小也各不相同。

   • 为了高效共享内存资源，MuxServe 将内存分为三个分区：

     • 统一 KV 缓存空间 (Unified KV cache space)：通过头级缓存 (head-wise cache) 实现。基于观察到每个注意力头的大小在不同 LLM 中通常一致或变化有限（例如 LLaMA 和 GPT-3 都使用 128），MuxServe 将 KV 缓存表划分为小的块 (blocks)，每个块保存多个词元的一个头的 KV 缓存。这种头级粒度使得 MuxServe 能够在一个统一的空间内容纳不同 LLM 的 KV 缓存，从而实现内存共享。
     • LLM 权重单一副本 (Single replica of LLM weights)：存储模型权重，可在预填充和解码作业之间共享，以减少冗余。
     • 激活空间 (Activation space)：用于在推理运行时存储激活值。

   • 动态 KV 缓存调整：MuxServe 采用统一 KV 缓存，而不是为每个 LLM 保留独立的 KV 缓存。这种共享缓存使得 MuxServe 能够在运行时以最小开销动态调整缓存分配。因此，MuxServe 能够更好地处理突发和变化的工作负载。

   • 与 vLLM 的 PagedAttention 对比：vLLM (Kwon et al., 2023) 提出的 PagedAttention 旨在通过提高单个 LLM 服务的内存利用率来解决内存碎片问题。而 MuxServe 的统一 KV 缓存解决了不同的场景：多个不同大小、流行度和配置的 LLM 需要共享缓存。

     实现细节 (Implementation Details)：

• MuxServe 构建在 vLLM (Kwon et al., 2023) 之上，vLLM 是一个基于 PyTorch (Paszke et al., 2019) 的高效单 LLM 服务系统。
• 利用 NVIDIA MPS (NVIDIA, 2022b) 来划分 SM 资源。
• 主要组件是一个全局调度器 (global scheduler)，它运行在每个 LLM 单元上，管理请求队列并运行 ADBS 算法来调度请求。
• MuxServe 将预填充和解码阶段解耦 (disaggregates)，并启动独立的 vLLM 进程作为它们的运行时引擎 (runtime engines)，这些进程通过 NVIDIA MPS 配置不同的 SM 资源数量。
• 全局调度器通过 Python 多进程共享内存 (python multiprocessing shared memory) 将预填充或解码作业调度到运行时引擎进程。
• MuxServe 额外运行一个内存管理器进程 (memory manager process) 来管理统一内存空间。运行时引擎通过 CUDA IPC handler 访问内存空间。
• 当运行时引擎需要为执行分配 KV 缓存时，它向内存管理器请求新的缓存块，并将 KV 缓存填充到分配的块中。
• 预填充作业执行后，内存管理器会维护已分配的 KV 缓存块，供后续的解码作业使用。KV 缓存仅在请求完成后才释放。
• 内存管理器使用 C++ 实现，以优化块分配的开销。

5. 实验设置

5.1. 集群 (Cluster)

实验在由 4 个节点组成的集群上进行。每个节点配备 8 块 NVIDIA A100 (80GB) GPU。节点内连接带宽为 600GB/s NVLink，节点间连接带宽为 200Gbps IB。

5.2. 评估指标

对论文中出现的每一个评估指标，按照概念定义、数学公式和符号解释三段结构提供完整说明。

5.2.1. 聚合吞吐量 (Aggregated Throughput)

• 概念定义 (Conceptual Definition): 聚合吞吐量衡量系统在单位时间内处理的总请求量。由于不同 LLM 的请求到达率（即流行度）不同，这个指标通常会进行加权平均，以更准确地反映系统在实际多模型服务场景下的整体效率和 GPU 利用率。较高的聚合吞吐量意味着系统能够更好地利用资源来满足多样化的服务需求。
• 数学公式 (Mathematical Formula): 虽然原文未直接给出其精确的数学公式，但根据描述，可以理解为： $$\text{Aggregated Throughput} = \sum_{m \in M} w_m \cdot \text{TPT}_m$$
• 符号解释 (Symbol Explanation):
  • $M$: 待服务 LLM 的集合。
  • $w_m$: LLM $m$ 的权重，通常与其请求到达率或重要性成正比。
  • $\text{TPT}_m$: LLM $m$ 的实际吞吐量（每秒请求数）。

5.2.2. SLO 达成率 (SLO Attainment)

• 概念定义 (Conceptual Definition): SLO 达成率衡量的是在预定义的延迟目标（Service Level Objective）内完成的请求所占的百分比。这个指标是衡量服务质量和用户体验的关键，因为它直接反映了系统满足性能承诺的能力。论文中，延迟目标被定义为单设备执行延迟的某个倍数（SLO scale）。
• 数学公式 (Mathematical Formula): $$\text{SLO Attainment} = \frac{\text{Number of requests completed within SLO latency target}}{\text{Total number of requests}} \times 100\%$$
• 符号解释 (Symbol Explanation):
  • $\text{Number of requests completed within SLO latency target}$: 在给定延迟目标内完成的请求数量。
  • $\text{Total number of requests}$: 总请求数量。
  • SLO latency target: 延迟目标，通常是 SLO scale 乘以单设备执行延迟。

5.2.3. P99 延迟 (P99 Latency)

• 概念定义 (Conceptual Definition): P99 延迟是指在所有请求中，有 99% 的请求的响应时间都低于或等于这个值。它是一个衡量系统在最差情况（不包括极少数异常值）下性能的指标，对于评估用户体验的稳定性至关重要。较低的 P99 延迟意味着绝大多数用户都能获得快速响应。
• 数学公式 (Mathematical Formula): P99 延迟是一个统计学上的百分位数，其公式不是一个简单的计算式，而是从一组延迟样本中确定。给定一组按升序排列的延迟样本 $L = \{l_1, l_2, \dots, l_N\}$，P99 延迟是第 $\lceil 0.99 \times N \rceil$ 个延迟值。 $$\text{P99 Latency} = l_{\lceil 0.99 \times N \rceil}$$
• 符号解释 (Symbol Explanation):
  • $l_k$: 经过升序排序后的第 $k$ 个延迟值。
  • $N$: 样本中的请求总数。
  • $\lceil \cdot \rceil$: 向上取整函数。

5.3. 对比基线 (Baselines)

MuxServe 与两种主要基线进行比较：

1. 空间划分 (Spatial Partitioning)：这是目前广泛使用的方法。它为每个 LLM 分配一组独立的 GPU 进行服务。论文中使用的是 vLLM (Kwon et al., 2023) 作为底层服务框架来运行每个 LLM，vLLM 是一个最先进的单 LLM 服务框架。
2. 时间复用 (Temporal Multiplexing)：这种方法类似于 AlpaServe (Li et al., 2023)。由于 AlpaServe 不直接支持多个 LLM 的复用，论文作者自行实现了这个基线。实现方式是：
   • 使用 MuxServe 自己的放置算法优化 LLM 的并置。
   • 采用先来先服务 (first-come-first-serve, FCFS) 的时间调度方式。
   • 对每个 LLM 的请求进行连续批处理 (continuous batching)。
   • 使用了 MuxServe 的统一 KV 缓存。

5.4. 模型 (Models)

论文主要使用 LLaMA (Touvron et al., 2023) 系列模型进行实验，因为 LLaMA 是最流行的 LLM 架构之一。根据 LLaMA 模型的规模，LLM 被划分为四个大小区间（buckets）。

以下是原文 Table 1 的结果：

表格解释： 该表格显示了在实验中使用的不同 LLM 规模区间的模型数量。例如，有 12 个参数量在 4B 到 8B 之间的 LLM，以及 1 个参数量在 41B 到 70B 之间的 LLM。这种多样性确保了 MuxServe 在处理不同规模 LLM 时的有效性评估。

5.5. 工作负载 (Workloads)

5.5.1. 合成工作负载 (Synthetic Workloads)

• 请求率生成：每个 LLM 的请求率使用幂律分布 (power-law distribution) 生成，其中包含一个指数 $\alpha$。通过改变 $\alpha$，可以模拟不同流行度分布的场景：
  • 小 $\alpha$ 值：请求率分布更均匀，即不同 LLM 的流行度差异不大。
  • 大 $\alpha$ 值：少数 LLM 占据了绝大部分请求量，即流行度差异显著。例如，当 $\alpha = 0.9$ 或 2.1 时，分别表示 20% 的 LLM 接收总请求量的 50% 或 90%。
• 请求到达时间：每个请求的到达时间通过泊松过程 (Poisson processes) 进行采样。
• 请求内容：请求内容（即输入提示和输出长度）从 ShareGPT (ShareGPT-Team, 2023) 数据集中采样。
• 评估范围：通过改变 $\alpha$ 和速率尺度 (rate scales)，评估 MuxServe 在各种工作负载下的性能。

5.5.2. 真实工作负载 (Real Workloads)

为了在更接近实际的场景中评估 MuxServe，实验还使用了真实工作负载。

• 数据来源：从 ChatLMSYS 跟踪 (trace) 中采样 LLM 和工作负载。ChatLMSYS 是一个提供多种规模 LLM 服务的网络应用。
• 配置：在 32 块 GPU 上服务 16 个 LLM。
• 流行度分布：在这个真实工作负载中，20% 的热门 LLM 占据了 50% 的请求流量。
• 速率调整：对采样到的请求率进行重新缩放 (rescale)，以评估 MuxServe 在不同负载强度下的表现。

6. 实验结果与分析

6.1. 核心结果分析

MuxServe 在合成和真实工作负载下都表现出优于现有基线的性能。

6.1.1. 合成工作负载的端到端结果

以下是原文 Figure 5 的结果：

该图像是图表，展示了不同 $ext{α}$ 值下 MuxServe、空间分区和时间复用的吞吐量与 SLO 达成率。图中显示随着速率尺度的增加，MuxServe 在吞吐量方面表现优于其他方法，且在 SLO 达成率上也取得较好的效果。

Figure 5. Throughput and SLO atainment on synthetic workloads.

图 5 解释： 该图展示了在不同 $\alpha$ 值和平均速率 (average rates) 下，MuxServe、空间划分 (Spatial Partitioning) 和时间复用 (Temporal Multiplexing) 的吞吐量和 SLO 达成率。

• 吞吐量 (Throughput)：左侧图显示，在所有场景下，MuxServe 的吞吐量均优于两种基线，最高可达 $1.8 \times$ 的提升。这表明 MuxServe 的时空复用策略能够更有效地利用 GPU 资源。
• SLO 达成率 (SLO Attainment)：右侧图显示，MuxServe 在 99% 的 SLO 达成率下，可以处理多达 $2.9 \times$ 的请求。
• $\alpha$ 的影响：
  • 小 $\alpha$ (请求率更均匀)：MuxServe 可以高效地并置预填充-解码和解码-解码作业以提高利用率。但是，并置带来的干扰也可能导致在小 SLO 尺度下 SLO 达成率略低。
  • 大 $\alpha$ (流行度差异显著)：热门 LLM 可以与非热门 LLM 并置，从而复用内存资源，利用更多 SMs 和更大的 KV 缓存，实现更高的吞吐量。这使得热门 LLM 可以处理更多请求，从而实现更高的 SLO 达成率。结果表明，当 LLM 之间的流行度差异更大时（即 $\alpha$ 更大），MuxServe 的改进更为显著。

6.1.2. LLM 流量分布随 $\alpha$ 变化

以下是原文 Figure 6 的结果：

该图像是图表，展示了在不同 eta 值下的累积分布率。横轴为 Top-k 模型的比例，纵轴为累积分布率百分比，各条曲线对应 eta = 0.7, 0.9, 1.3, 1.7, 2.1 的不同情境。

Figure 6. Cumulative rate distribution as we vary $\alpha$ .

图 6 解释： 该图展示了随着 $\alpha$ 值的变化，LLM 流量的累积分布。横轴表示 Top-k LLM 的比例，纵轴表示累积请求率的百分比。

• 不同的曲线对应不同的 $\alpha$ 值。
• 当 $\alpha$ 较小时（例如 $\alpha = 0.7$），流量分布相对平坦，表明所有 LLM 的流行度接近。
• 当 $\alpha$ 较大时（例如 $\alpha = 2.1$），曲线变得陡峭，表明少数热门 LLM 占据了绝大部分流量。例如，在 $\alpha = 2.1$ 时，约 20% 的 LLM 接收了超过 90% 的总请求率。 这张图直观地展示了 MuxServe 所面对的真实世界中 LLM 流行度差异巨大的挑战，并验证了其根据流行度进行资源分配的动机。

6.1.3. 真实工作负载的端到端结果

以下是原文 Figure 7 的结果：

该图像是图表，展示了在不同平均请求速率下，Spatial、Temporal 和 MuxServe 方法的吞吐量与 SLO 达成率。左侧显示吞吐量 (req/s)，右侧为 SLO 达成率 (%)，可以看出 MuxServe 在各个速率下表现良好。

Figure 7. Throughput and SLO attainment as we vary the rates on real workloads.

图 7 解释： 该图展示了在 ChatLMSYS 真实工作负载下，MuxServe、空间划分和时间复用方法在 SLO scale 8 时的吞吐量和 SLO 达成率，随着平均请求率 (average rates) 的变化。

• 吞吐量：MuxServe 实现了高达 $1.38 \times$ 和 $1.46 \times$ 的吞吐量提升，分别优于空间划分和时间复用。
• SLO 达成率：随着平均速率的变化，MuxServe 始终保持更高的 SLO 达成率。
• 特定场景：当平均速率为 4.8 时，一些中等速率的 LLM 并置在一个大型网格上。在这种情况下，时间复用无法有效复用这些 LLM，因此表现相当差。这进一步凸显了 MuxServe 灵活时空复用的优势。

6.2. 消融实验/参数分析

论文通过消融实验 (Ablation Studies) 验证了 MuxServe 各个组件的有效性：放置算法、自适应批调度 (ADBS) 机制和统一资源管理器。

6.2.1. 放置算法的有效性 (Effectiveness of Placement Algorithm)

以下是原文 Figure 8 的结果：

该图像是一个图表，展示了在不同 GPU 数量下，采用我们的方法与贪婪算法的吞吐量对比。左侧图为 8 个 GPU 和 4 个 LLMs 的情况，右侧图为 16 个 GPU 和 7 个 LLMs 的情况。可以看出，我们的方法在吞吐量上表现更优。

Figure 8. Ablation study of placement algorithm.

图 8 解释： 该图比较了 MuxServe 的放置算法与一个简单的贪婪算法在吞吐量上的表现。贪婪算法优先放置请求率高的 LLM，并将其贪婪地分配给可用空闲内存最大的网格。实验在两个规模下进行：8 个 GPU 服务 4 个 LLM，以及 16 个 GPU 服务 7 个 LLM。在这两种场景下，50% 的 LLM 是热门模型，占据了超过 70% 的请求流量。

• 结果：在右侧的 16 GPU 和 7 LLM 的场景中，MuxServe 的放置算法比贪婪算法实现了 $1.3 \times$ 的吞吐量提升。
• 洞察验证：优化后的放置算法验证了 MuxServe 的洞察——优先选择那些计算需求大的 LLM（结合模型规模和流行度）进行放置。
  • 8 GPU 和 4 LLM 的案例：MuxServe 将两个热门的小型 LLM 与一个不那么热门的小型 LLM 并置在 4 块 GPU 上，同时将另外 4 块 GPU 分配给不那么热门的大型 LLM。
  • 16 GPU 和 7 LLM 的案例：MuxServe 将两个请求率较低的大型 LLM 并置在 4 块 GPU 上，并将剩余（大部分）的 GPU 划分为 2 或 4 块 GPU 的组。MuxServe 根据计算需求将另外 5 个请求率较高的 LLM 放置在不同的组中。
• 反例分析：如果优先考虑内存需求大的 LLM（例如试图平衡 GPU 间的内存消耗），大型 LLM 可能会被优先放置在大型 GPU 组上，而不考虑其流行度。这样，小型 LLM 将被放置在剩余的 GPU 内存空间中。这与直觉相悖，因为热门的小型 LLM 可能需要大量 GPU 来满足请求流量。MuxServe 的策略避免了这种低效。

6.2.2. ADBS 的有效性 (Effectiveness of ADBS)

以下是原文 Figure 9 的结果：

该图像是图表，展示了不同调度方法在四个 GPU 上的缓存使用情况，包括 FCFS、Round-Robin 和 ADBS 调度。图中分别描绘了三和两个 LLM 的服务效果，并标注了每种方法下不同时间段的 token 块使用比例。

Figure 9. Comparison of cache usage of different schedule approaches on 4 GPUs. The relative proportion of token block usage is annotated in the figure. FCFS: First Come First Serve, ADBS: ADaptive Batch Size. (a) Request rate: $2 { : } 8 { : } 8 \ r e q / s$ . Throughput $( r e q / s )$ : FCFS (3.8), Round-Robin (4.1), ADBS (6.2). (b) Request rate: 1:8 req/s. Throughput (req/s): FCFS (3.2), RoundRobin (4.9), ADBS (6.6).

图 9 解释： 该图比较了 MuxServe 的自适应批调度 (ADBS) 算法与先来先服务 (FCFS) 和轮询 (Round-Robin) 调度在两种服务设置下 KV 缓存使用情况和吞吐量。

• 图 9a：平均请求长度比例为 LLaMA-30B : LLaMA-13B : LLaMA-7B 为 2:1:1。请求率为 2:8:8 req/s。
  • 吞吐量 (req/s)：FCFS (3.8)，Round-Robin (4.1)，ADBS (6.2)。
• 图 9b：平均请求长度比例为 LLaMA-65B : LLaMA-30B 为 4:1。请求率为 1:8 req/s。
  • 吞吐量 (req/s)：FCFS (3.2)，Round-Robin (4.9)，ADBS (6.6)。
• 缓存使用与公平性：在两种场景中，ADBS 的词元块使用量与请求到达率的分布更紧密对齐，从而实现了更公平的内存资源共享。
• 吞吐量表现：ADBS 相较于 Round-Robin 和 FCFS 调度分别实现了 $1.43 \times$ 和 $1.85 \times$ 的吞吐量提升。
• 原因：基线方法中 KV 缓存块的不公平共享损害了热门 LLM 的性能。此外，FCFS 无法有效复用不同的 LLM。

6.2.3. 资源管理器的有效性 (Effectiveness of Resource Manager)

以下是原文 Figure 10 的结果：

该图像是图表，展示了不同方法在不同参数 eta 下的吞吐量（左）和 SLO 达成率（右）。左侧图中，MuxServe 达到最高的吞吐量，而右侧图中，MuxServe 的 SLO 达成率保持在较高水平，展示了其在多模型服务中的优势。

Figure 10. Ablation study of the unified resource manager.

图 10 解释： 该图研究了 MuxServe 统一资源管理器的有效性，通过逐步启用计算和内存管理功能进行对比。实验在 4 块 GPU 上服务 4 个 LLM，并使用幂律分布生成请求到达率。

• 分离预填充/解码 + 计算资源管理：通过分离预填充和解码阶段并进行计算资源管理，吞吐量提高了 $1.7 \times$。这表明动态分配 SMs 和灵活调度作业的重要性。
• 添加统一内存管理器：在此基础上，引入统一内存管理器后，MuxServe 又实现了 $1.2 \times$ 的吞吐量提升，并将 SLO 达成率提高了 $3.6 \times$。这强调了统一 KV 缓存和头级缓存机制在减少内存浪费和碎片方面的关键作用。

6.3. P99 延迟比较 (P99 Latency Comparison)

以下是原文 Appendix A.1 中的 Figure 11 的结果：

该图像是示意图，展示了不同速率比例下，平均延迟、TPOT和TTF的性能对比。可以观察到，随着速率比例的变化，MuxServe（绿色线）的表现相较于空间划分（蓝色线）和时间复用（橙色线）有明显优势，特别是在 ext{avg latency} 和 ext{TPOT} 指标上。

.

图 11 解释： 该图展示了在不同 $\alpha$ 值下，MuxServe、空间划分和时间复用的 P99 TTFT（Time To First Token，首词元时间）延迟。

• MuxServe 的 P99 TTFT 延迟：当 $\alpha$ 较小时（即 LLM 流行度分布更均匀），MuxServe 的 P99 TTFT 延迟显著降低，远低于空间划分和时间复用。这表明 MuxServe 能够有效减少请求的排队时间，即使在请求分布均匀的情况下也能保持低延迟。
• 大 $\alpha$ 时的 P99 TTFT 延迟：当 $\alpha$ 较大时（即少数 LLM 非常流行），P99 TTFT 延迟主要由最流行的模型主导。在这种情况下，时间复用由于减少了排队时间，相较于空间划分能获得更低的 P99 TTFT 延迟。MuxServe 在此场景下也表现出优越性。

6.4. 吞吐量估计器的执行时间线

以下是原文 Appendix A.2 中的 Figure 12：

该图像是一个示意图，展示了MuxServe在稳定服务环境下的执行时间线。在该图中，资源被有效地分配给不同的请求，特别注意了各个请求的处理时间。如在图中所示，资源的分布与相应的请求时间 $t^m_d imes l^m_o$ 有关，累加和表示为 $extstyle orall i ext{ in } b ightarrow extstyle ext{s}^i_p$。

Figure 12. Execution timeline of MuxServe in a stable serving setting. $R$ eent theequest he a.

图 12 解释： 该图描绘了 MuxServe 在稳定服务设置下的执行时间线。它直观地展示了吞吐量估计器（Equation (3)）所基于的假设。

• 图中的不同颜色块代表不同 LLM 或不同阶段的执行。
• $R$ 代表请求，$a$ 代表到达。
• 时间线显示，预填充阶段（prefill phases）通常是顺序执行的，而解码阶段（decoding phases）则可以并发执行或与预填充阶段交错执行。
• 公式 (3) 中的 $\sum_{i \in b} t_p^i$ 对应了在一个批次内，所有 LLM 的预填充阶段的总时间，这些阶段是串行的。$t_d^m \cdot l_o^m$ 对应了 LLM $m$ 的解码阶段的总时间。 这张图为吞吐量估计公式的合理性提供了可视化依据。

7. 总结与思考

7.1. 结论总结

本文提出了 MuxServe，一个针对多大型语言模型 (LLM) 服务的灵活时空复用系统。MuxServe 的核心思想在于结合 LLM 的流行度进行内存资源复用，并利用 LLM 推理过程中预填充和解码阶段的不同计算特性，将它们分离并灵活并置以复用计算资源。该系统通过形式化多 LLM 服务问题，提出了一个基于枚举的贪婪放置算法和自适应批调度 (ADBS) 策略，旨在识别最优并置并最大化资源利用率。MuxServe 还设计了一个统一资源管理器，通过 NVIDIA MPS 进行动态 SM 分配，并采用头级缓存实现统一 KV 缓存空间，从而实现高效灵活的内存共享。

实验结果表明，MuxServe 在合成和真实工作负载下均显著优于传统的空间划分和时间复用方法，实现了高达 $1.8 \times$ 的吞吐量提升，并在 99% 的服务水平目标 (SLO) 达成率下处理 $2.9 \times$ 更多的请求。消融实验也独立验证了其放置算法、ADBS 机制和统一资源管理器各个组件的有效性。

7.2. 局限性与未来工作

论文在“影响声明 (Impact Statement)”部分提到，其工作目标是推动机器学习领域的发展，但并未明确指出 MuxServe 自身的具体局限性或未来的研究方向。然而，从论文内容和领域挑战中可以推断出一些潜在的局限性和未来工作方向：

潜在局限性：

• 放置算法的复杂度与扩展性：虽然论文提到通过启发式方法剪枝了搜索空间，但 $O(MCD)$ 的复杂度对于 M 和 D 极大的超大规模集群仍然可能面临挑战。如何进一步优化或采用更高效的近似算法，以在数十甚至数百个 LLM 和数千个 GPU 的场景下快速找到高质量的放置方案，可能是一个问题。
• 吞吐量估计的准确性：论文使用的吞吐量估计器是一个简化模型，它基于预填充阶段顺序执行和解码阶段并发执行的假设。在非常动态和复杂的实际工作负载下，特别是在资源竞争激烈或网络通信成为瓶颈时，这个估计器的准确性可能会受到影响。
• 公平性参数 $\epsilon$ 的调优：确保 LLM 之间公平性的参数 $\epsilon$ 的选择和动态调整可能是一个敏感且复杂的任务，需要根据实际业务需求进行精细平衡。
• 异构硬件支持：论文在 NVIDIA A100 GPU 上进行实验。对于更异构的硬件环境（例如不同代次或型号的 GPU），统一资源管理和性能估计可能会面临新的挑战。
• 系统实现开销：NVIDIA MPS、多进程共享内存和 CUDA IPC handler 等机制虽然提供了灵活性，但也可能引入一定的系统开销，尤其是在高频调度和细粒度资源管理时。
• 冷启动延迟：虽然论文关注吞吐量和 SLO 达成率，但对于新模型加载或长时间不活跃模型再次被请求时的冷启动延迟问题未深入探讨。

未来工作方向：

• 更先进的放置和调度算法：可以探索基于强化学习或更复杂的在线优化技术，以应对更动态的 LLM 流行度变化和更多维度的资源约束。
• 跨节点细粒度资源管理：当前资源管理主要侧重于节点内 GPU 资源分配，未来可以研究更细粒度的跨节点资源协同和调度。
• 更精准的性能预测模型：开发能够实时适应工作负载变化、并考虑网络拓扑和硬件异构性的更精准的 LLM 性能预测模型。
• 成本优化与弹性伸缩：结合云环境中的抢占式实例或动态资源池，实现更具成本效益的 LLM 服务弹性伸缩。
• 与其他 LLM 优化技术的集成：MuxServe 与许多单 LLM 优化技术正交。未来可以探索如何将 MuxServe 与推测解码、更高效的量化技术等进一步结合，以实现协同效应。

7.3. 个人启发与批判

7.3.1. 个人启发

MuxServe 的工作提供了几个重要的启发：

1. 分阶段优化 (Phase-aware Optimization) 的重要性：LLM 推理的预填充和解码阶段具有截然不同的计算和内存特性。MuxServe 明确区分并利用这些特性进行资源复用，这是一个非常巧妙且有效的思路。这提醒我们，在设计复杂系统的优化策略时，深入理解其内部子过程的特点至关重要。
2. 流行度感知 (Popularity-aware) 的资源管理：现实世界中，服务的模型流行度并非均匀分布。MuxServe 将这一实际情况纳入其优化目标，通过智能并置来复用资源，这比简单平均分配或静态分配资源更高效。这种“智能匹配”的策略在其他多任务、多租户系统中也具有广泛的借鉴意义。
3. 统一 KV 缓存和头级粒度 (Unified KV Cache and Head-wise Granularity) 的创新：针对多 LLM 服务的内存瓶颈，MuxServe 提出的头级缓存思想非常新颖。它利用了不同 LLM 内部注意力头维度可能一致的特点，打破了传统上为每个模型保留独立 KV 缓存的局限，实现了更灵活、更细粒度的内存共享，有效解决了内存碎片和浪费问题。这对于未来多模型、多租户的 AI 服务具有很强的指导价值。
4. 系统级集成能力：MuxServe 不仅提出了理论框架，还将其成功集成到 vLLM 和 NVIDIA MPS 等现有工具之上，构建了一个可行的系统。这展示了将理论洞察转化为实际高效解决方案的强大工程能力。

7.3.2. 批判性思考

尽管 MuxServe 取得了显著的成就，但也存在一些值得深思和未来改进的地方：

1. “Computation” 的定义与排序基准：在放置算法中，LLM 按照 $key=computation$ 降序排列。这里的 computation 是一个综合了模型规模和流行度的指标。如何精确且动态地量化这个“计算需求”是关键。如果其估计不准确，可能会影响放置算法的效率。此外，这种静态排序在 LLM 流行度快速变化时（如突发流量高峰）可能需要频繁重新计算，带来额外开销。
2. 调度策略的复杂性与公平性：ADBS 算法在单元内调度时，通过轮询和词元块配额来确保公平性。但在实际系统中，公平性往往是多维度的（例如，P50 延迟、P99 延迟、吞吐量等）。目前的公平性定义主要关注资源消耗的差异，未能完全捕捉用户体验上的公平性。如何在保证高吞吐量的同时，更精细地平衡不同 LLM 甚至不同用户的多维度公平性需求，是一个持续的挑战。
3. 对底层硬件的依赖：MuxServe 严重依赖 NVIDIA MPS 进行 SM 划分，以及 CUDA IPC handler 进行内存访问。这在很大程度上限制了其在非 NVIDIA GPU 或其他异构计算平台上的通用性。未来的研究可以探索更通用的硬件抽象和资源管理接口。
4. “灵活”的边界：MuxServe 强调“灵活”，但这种灵活性在多大程度上能够应对极端动态的流量模式（例如，短时间内 LLM 流行度突然剧烈变化，甚至模型需要动态加载卸载）仍有待进一步探讨。频繁的模型重放置或 KV 缓存的剧烈再分配可能会引入不可忽略的系统开销。
5. 模型兼容性：头级缓存的成功部分依赖于不同 LLM 具有相似的注意力头维度。如果未来出现大量 LLM 使用高度异构的头维度配置，这种统一缓存的优势可能会减弱，或者需要更复杂的转换机制。