Transcending Cost-Quality Tradeoff in Agent Serving via Session-Awareness

作者/机构: Yanyu Ren (清华大学), Li Chen (清华大学, 钟关村实验室), Dan Li (清华大学, 钟关村实验室), Xizheng Wang (清华大学), Zhiyuan Wu (清华大学), Yukai Miao (钟关村实验室), Yu Bai (钟关村实验室)

A1 主要贡献

本文针对大型语言模型（LLM）Agent服务中现有模型服务系统效率低下的问题，旨在超越传统的成本-质量权衡。

• 核心问题：与经典的LLM服务相比，Agent服务具有可预测的请求模式、不断增长的质量要求和独特的提示格式（如中段截断）等特点。现有的LLM服务系统缺乏会话感知能力，导致KV缓存管理效率低下，并且无法在会话的每个轮次中精确选择成本最低且能力足够的模型，从而陷入了成本与质量之间的权衡困境。

• 研究目标：设计一个名为AGSERVE的敏捷Agent服务系统，通过利用会话的可预测性来降低推理延迟，并在会话的不同阶段应用不同规模的模型来降低成本，从而超越成本-质量权衡。

• 创新点：

  1. 会话感知服务器（Session-Aware Server）：通过引入基于预计到达时间（ETA）的驱逐策略和原地位置嵌入校准技术，提升了在Agent服务中（特别是中段截断场景下）的KV缓存重用率。
  2. 质量感知客户端（Quality-Aware Client）：通过实时质量评估实现会话感知的模型级联。它能评估任务难度以选择合适的初始模型，并在会话期间持续监控响应质量，以做出明智的模型升级决策。
  3. 动态资源调度器（Dynamic Resource Scheduler）：根据模型的需求和供给统计数据，动态分配GPU资源，从而最大化GPU利用率。

通过这三者的协同优化，AGSERVE允许Agent在会话生命周期内选择和升级模型，以更低的成本实现与顶尖模型（如GPT-4o）相当的质量。

A3 背景知识与关键观察

2.1 LLM Agent 基础

LLM Agent通常使用结构化提示与模型交互，该提示由共享前缀、任务特定模板和可用工具的引用组成，使其能够迭代地执行任务。共享前缀解释工具并提供少样本示例【5，Language models are few-shot learners，2020，arXiv】，而任务模板则给出具体任务。在每一轮中，Agent请求LLM的思维链（CoT）【54，Chain-of-thought prompting elicits reasoning in large language models，2022，NIPS】响应，执行其中的操作，并附加观察结果。由于上下文长度的限制，LLM Agent可能会截断交互历史，但会保留共享前缀（SP）和任务特定模板（TST）以维持正确的行为。

2.2 LLM 服务系统不足以支持 Agent 服务

为了更好地理解 AGSERVE 设计背后的动机，我们首先研究了经典 LLM 服务与 Agent 服务之间的关键差异。

工作流差异。我们在图2中展示了它们的工作流差异。主流的LLM服务系统提供特定模型的推理服务【24，Efficient memory management for large language model serving with pagedattention，2023，SOSP；21，Inference without interference: Disaggregate llm inference for mixed downstream workloads，2024，NSDI】，它们在每个节点中调度和运行序列，不考虑质量问题。据我们所知，目前没有专门为Agent服务设计的系统。我们认为，Agent服务系统应该超越传统的LLM服务系统，因为它们的任务是提供有质量保证的动作。它们需要一个额外的透明层来从模型池中选择一个LLM，然后执行请求路由和调度。

行为差异导致现有系统性能不佳。

B1 Agent服务在每轮中表现出频繁且规律的请求模式。如图3(a)所示，token数量在不同轮次中呈阶梯状增长。同一会话下下一个请求的到达时间是可预测的【50，Kvcache cache in the wild: Characterizing and optimizing kvcache cache at a large cloud provider，2025，USENIX ATC】。与面向人类的LLM服务【44，Fairness in serving large language models，2024，OSDI】相比，图3(b)显示Agent请求的输出长度更短，请求间隔也更短。这表明Agent服务是一种重预填充（heavy-prefill）、轻解码（light-decode）的工作负载。现有的预填充-解码分离系统，如MoonCake【41，Mooncake: Trading more storage for less computation — a KVCache-centric architecture for serving LLM chatbot，2025，FAST】和DistServe【63，Distserve: disaggregating prefill and decoding for goodput-optimized large language model serving，2024，OSDI】，是为解码密集型任务优化的，对Agent服务的益处不大【21，Inference without interference: Disaggregate llm inference for mixed downstream workloads，224，NSDI】。

B2 Agent会话通过将新响应附加到交互历史（IH）来持续增长，并在需要时强制进行中段截断。现有系统采用基于前缀的缓存重用【19，Prompt cache: Modular attention reuse for low-latency inference，2024，MLSys】，这种方法假定前缀必须严格匹配。中段截断破坏了前缀模式，使得像CachedAttention【17，Cost-efficient large language model serving for multi-turn conversations with cachedattention，2025，USENIX ATC】这样的技术失效。同时，现有系统如vLLM【24，Efficient memory management for large language model serving with pagedattention，2023，SOSP】和SGLang【62，Sglang: Efficient execution of structured language model programs，2024，NeurIPS】采用LRU（最近最少使用）策略来管理缓存驱逐。LRU策略不感知会话语义，可能会驱逐即将再次请求的会话缓存，从而进一步导致低缓存命中率。

B3 随着Agent会话的进行，任务复杂性增加，对更大模型的需求也随之增长。图4通过单一模型满意度下降的趋势捕捉了这一点。较小的模型倾向于生成无效动作或违反预设规则，如附录§B所示。现有的路由系统【37，RouteLLM: Learning to route LLMs from preference data，2025，ICLR】和级联系统【13，Hybrid llm: Cost-efficient and qualityaware query routing，2024，arXiv】通过独立处理每个请求而忽略了这一趋势，导致模型选择脆弱且迁移成本高昂。

A2 方法细节

3 AGSERVE 概览

AGSERVE 架构。如图6所示，AGSERVE由三个部分组成：服务器、客户端和调度器。我们如下描述每个组件的角色和子模块：

• 会话感知服务器（Session-Aware Server, SAS, §4）：管理会话缓存并执行LLM推理。SAS维护一个会话ID-序列表（Session ID-Sequence Table, SIST），该表将话ID映射到其最新的序列。当来自现有会话的新请求到达时，SAS从内存中提取其会话缓存，并在需要时执行原地位置嵌入校准。在GPU内存过载的情况下，SAS维护基于预计到达时间（ETA）的缓存驱逐（ECE）策略。
• 会话守护客户端（Session Guard Client, SGC, §5）：为Agent提供观察结果，并确保整个会话的服务质量。客户端监控会话的生命周期并决定采用哪个LLM。为此，SGC使用一个Q-Judge来为会话选择最具成本效益的模型。它还运行一个守护进程R-Judge来定期检查响应质量，并在出现质量问题时决定缓解措施。
• 资源调度器（Resource Scheduler, RS, §6）：将LLM分配到GPU上，并根据系统范围内的实时供需比动态调整配置。

AGSERVE 工作流。当一个新的Agent启动时，SGC使用Q-Judge评估任务的难度。SGC与一个为给定模型提供服务的SAS实例或外部API建立会话。在会话中，Agent随后与LLM进行多轮交互。

会话过程中的质量监控与调整。在整个会话期间，SGC使用R-Judge监控推理质量。如果性能低于预定阈值，SGC会启动重试或请求迁移到更强大的模型实例。在迁移的情况下，SGC终止当前会话，并与一个更强大模型的SAS或API建立新会话。此外，RS会关注每个模型处理的请求，并动态调整跨模型的GPU资源分配。

4 在 SAS 中会话化 KV 缓存以最大化缓存命中率

PagedAttention与SIST集成。AGSERVE遵循vLLM和SGLang的实践，采用PagedAttention。如图5所示，我们将SIST（Session ID-Sequence Table）集成到块表中。SIST通过维护每个会话的块ID，为KV缓存引入了会话感知能力。我们接下来的两个创新利用了SIST。

原地KV缓存校准。现代LLM采用旋转位置嵌入（Rotary Positional Embedding, RoPE）【46，Roformer: Enhanced transformer with rotary position embedding，2024，Neurocomput.】来嵌入token。CachedAttention【17，Cost-efficient large language model serving for multi-turn conversations with cachedattention，2025，USENIX ATC】提出了分离式KV缓存。然而，分离式缓存消耗两倍的空间，一个用于保存分离的KV缓存，另一个用于解码的普通缓存。相反，AGSERVE采用原地校准来支持中段截断。原地校准将原始的键缓存乘以$e^{i \cdot \delta_p \theta}$，其中$\delta_p = p' - p < 0$是被截断token数量的相反数。此操作将位置嵌入从$e^{ip\theta}$校准到$e^{ip'\theta}$。在实践中，SAS执行以下操作以重用RoPE模块的余弦-正弦缓存，进一步减少计算时间。

$$\begin{aligned} \begin{aligned} K_{p', 2i}' &= cos(-\delta_p \theta_i) K_{p, 2i} + sin(-\delta_p \theta_i) K_{p, 2i+1} \\ K_{p', 2i+1}' &= cos(-\delta_p \theta_i) K_{p, 2i+1} - sin(-\delta_p \theta_i) K_{p, 2i} \end{aligned} \end{aligned}$$

ECE驱逐策略。由于在线服务中内存有限，SAS需要驱逐KV缓存。为了形式化这个问题，我们假设有n个会话按照其待处理请求的到达时间排序，记为$sc_0, sc_1, ..., sc_n$。如果下一个请求尚未到达，SAS会预测其到达时间。会话$sc_i$的缓存大小为$l_i$。我们分两步来审视SAS的ECE驱逐策略。

等大小缓存情况下的最优策略。首先，我们假设所有会话缓存的大小相同。受CPU缓存中OPT策略【40，Min—an optimal variable-space page replacement algorithm，1976，Communications of the ACM】的启发，我们按照从n到1的顺序移除$sc_i$。我们在附录§A.2中证明了其最优性。

不同大小缓存情况下的动态规划策略。然而，会话缓存的大小是不同的，这意味着驱逐一个会话可能无法为另一个会话腾出足够的空间，上述解决方案无法达到全局最优。为了解决这个问题，我们引入一个新符号$T^{(k)}$，表示仅考虑$sc_{n-k}$到$sc_n$时的最优总TTFT。为了为前k个待处理会话腾出足够的空间，我们需要决定一个要驱逐的会话缓存集合E。驱逐$sc_i$会产生$P \cdot l(sc_i)$的重计算成本，并影响其后的$n-i+1$个会话，导致$(n-i+1)P l(sc_i)$的惩罚。因此，$T_k(n) = \Sigma_{i \in E_k} (n - i + 1)P \cdot l_i + (n-k)D_k + T^{(n-k)}$，其中$D_k$是并行处理k个请求时的平均解码时间消耗。P是单个token的预填充开销相对于平均解码时间成本的倍数，被视为驱逐会话缓存的惩罚。对于每个k，SAS使用动态规划找到使$T_k(n)$最小化的$E_k$，并忽略$T^{(n-k)}$以避免过度驱逐。最后，SAS在所有k中找到最小的$T_{\hat{k}}(n)$并驱逐$E_{\hat{k}}$。每个SAS根据会话的请求轨迹预测ETA，并基于ETA做出驱逐决策。我们在附录§D中讨论了ECE策略的详细算法和效率。

其他实现细节。SAS不会将缓存交换到CPU，因为这种交换在长上下文场景下会引入高昂的开销并阻塞批处理中的其他序列。SAS采用先到先服务（First-Come-First-Served）的方式调度每个序列，而不是SGLang的基数方法，以避免饥饿问题。

5 在 SGC 中利用会话级级联以最小化成本

SGC利用Q-Judge评估任务难度，并为Agent与能力匹配的模型建立会话。Q-Judge $Q_J(t, p)$将Agent任务t和观察p作为输入。$Q_J(\cdot)$为每个任务分配一个难度标签，分为0、1和2。SGC利用R-Judge进行质量监控。

5.1 减少任务的“过度处理”和“处理不足”

问题定义。Q-Judge不可避免地会与真实情况存在偏差，导致“处理不足”（underkill）或“过度处理”（overkill）。在“处理不足”的情况下，SGC需要多次迁移才能达到能够胜任的模型，浪费了SAS的资源。如果“过度处理”，SGC将面临不可逆转的成本。我们观察到，SGC宁愿选择“处理不足”也不愿“过度处理”。

优化损失函数。我们如下优化$Q_J(\cdot)$的损失函数，其中p, q分别是真实概率和预测概率，g是真实标签。

$$f(p, q, g)=-\sum_{i=1}^{n} p\left(x_{i}\right) \log \left(q\left(x_{i}\right)\right)+\beta \cdot \sum_{i=1}^{n}\left(x_{i}-g\right)^{2} \cdot \frac{\alpha_{i}}{1-q\left(x_{i}\right)}$$

其中，如果$x_i > g$（过度处理），则$\alpha_i = 1$；如果$x_i < g$（处理不足），则$0 < \alpha_i = \alpha < 1$，$x_i$是第i个标签的值。函数的第一部分是传统的交叉熵损失。第二部分对远离或大于真实标签的错误标签施加额外的损失。

训练细节。我们在一个定制的Chatbot-Arena数据集【8，Chatbot arena: An open platform for evaluating llms by human preference，2024，arXiv】上训练该裁判。详细信息在附录§C中披露。

5.2 针对长上下文的实时响应质量监控和问题缓解

质量问题类型。我们观察到Agent服务中存在四种典型的质量问题：服务失败、违反预设规则、无效操作和低推理质量。前三种很容易通过算法方法识别。对于第四个问题，SGC以用户自定义的频率ν调用R-Judge分类器来评估推理质量。

设计和训练R-Judge。提示长度很容易超过现代分类器的上下文窗口，可能超过一千个token。因此，我们只从上下文中选择部分元素输入以减少工作负载。R-Judge $RJ_\theta(m, r, t, e)$接收四个参数。m表示模型大小，它为R-Judge提供了服务质量相对于模型大小的偏见。r是CoT响应的思考部分。如果实现不采用CoT，R-Judge将整个响应作为r。t是Agent的任务。e是AGSERVE发送请求时的最新动作和观察。$RJ(\cdot)$根据r在e的条件下对t任务的辅助程度进行判断，涵盖了回避和冗余回复的情况。$\theta$反映了裁判的严格程度。$\theta=0$是最严格的，总是认为响应不合格；$\theta=1$则允许所有响应通过测试。用户可以根据自己的质量要求或工作负载特性调整此阈值。我们在附录§C中披露了R-Judge的训练细节。

解决质量问题。SGC采用重试或迁移来缓解质量问题。重试策略利用随机性重新运行响应生成。但是，如果响应仍然存在质量问题，SGC会强制进行服务升级迁移。迁移将话路路由到另一个服务实例。SGC实现了两种类型的迁移：服务升级迁移将话路路由到更大的LLM实例或API；通用迁移则决定模型选项，在服务失败（如超时或网络问题）的情况下可能会选择更小的模型。

会话恢复。SGC还支持某些Agent的恢复功能。恢复功能将会话恢复到上一个检查点，缩短聊天历史以降低推理复杂性并提高性能。

6 在 RS 中跨 GPU 进行模型分配以最大化硬件效用

高效的模型分配对于优化Agent服务系统中的资源使用至关重要。AGSERVE采用动态分配策略以确保高资源利用率。

模型实例。我们将模型分为两类：可调整模型（adjustables）和预设模型（presets）。可调整模型适合单个节点，而预设模型必须跨多个节点。RS将可调整实例限制在单个节点内，以最小化通信延迟。对于每个模型m，RS会分析其推理所需的最小GPU数量，表示为$w_m$。每个实例使用$w_m$的倍数个GPU。由于预设模型初始化开销巨大，RS依赖手动操作进行配置。

动态分配。RS根据模型需求和资源可用性动态分配模型。RS跟踪每个模型所有实例的推理请求频率，并通过求和调用频率来计算其需求。调度器通过所有实例中KV缓存可保留的token数量来确定供应。RS优先考虑需求供应比较高的模型，扩大其的实例，同时减少比例较低模型的实例。RS重新分配可用节点上的模型实例以优化资源使用。RS尽可能将相同模型的实例整合在一起以利用并行性。例如，如果为一个$w_m=1$的模型分配了7个相同设备的GPU，RS会启动三个实例，分别使用1、2和4个GPU。

A4 实验环境

• 数据集：

  • 主要使用 AgentBench 【29, Agentbench: Evaluating llms as agents, 2023, arXiv】进行评估。
  • 多Agent负载测试使用了合成的请求轨迹，包括均匀分布、突发分布、泊松分布和伽玛分布。

• 模型架构：

  • 采用三层级联结构：Llama-3 8B、Llama-3 70B 【14, The llama 3 herd of models, 2024, Meta】 和 GPT-4o 【1, Gpt-4 technical report, 2023, OpenAI】。

• 硬件配置：

  • 测试平台1：两个节点，每个节点配备4个NVIDIA A6000 GPU（每卡48GB显存）。
  • 测试平台2：两个节点，每个节点配备8个NVIDIA A800 GPU（每卡80GB显存），通过PCIe互连。

• 软件配置：

  • AGSERVE使用Python实现，其会话感知服务器（SAS）基于vLLM 【24, Efficient memory management for large language model serving with pagedattention, 2023, SOSP】。
  • 实现了定制的CUDA内核以支持批处理原地KV缓存校准。
  • 适配了四种Agent进行评估：AlfWorld (AW)、Card Game (CG)、Knowledge Graph (KG) 和 Mind2Web (M2W)。

A4 实验结果

7.2 端到端级联服务

实验设置：在A6000测试平台上运行Llama-8B和Llama-70B两个实例，禁用动态分配。
基线方法：vLLM+（单模型服务）、Cascade（无智能判断的级联）、RouteLLM（基于路由器的模型选择）。
实验结果（图8）：

• AGSERVE在所有四种Agent上都成功打破了成本-质量权衡。
• 在AW Agent上，AGSERVE以GPT-4o 16.5%的成本达到了相似的质量。
• 在同等成本下，AGSERVE的质量比权衡曲线高出1.8倍。
• 相比之下，Cascade策略效果不显著，而RouteLLM的表现均低于成本-质量权衡曲线，原因可能是其设计不适用于长输入Agent服务且缺乏会话感知能力。

7.3 端到端多Agent服务

实验设置：在A800测试平台上进行分布式服务场景评估，使用四种不同的请求到达分布（Uniform, Burst, Gamma, Poisson）。
基线方法：Llumnix++（一个基于vLLM的先进LLM服务系统，集成了AGSERVE的质量维护模块）、RouteLLM。
实验结果（图9）：
* 在高频Agent服务场景下，AGSERVE相比Llumnix++成本降低了64%，同时质量提升了1.6倍。
* RouteLLM由于将大部分请求路由到GPT-4o，延迟较低但成本高昂。AGSERVE以其81%的成本实现了与之相当的质量。

7.4 消融研究与微基准测试

7.4.1 SAS会话缓存性能

正确性（图10）：与vLLM相比，AGSERVE在AW Agent上实现了高达2倍的加速，且质量得分无明显差异，验证了其正确性。

效率（图11, 12）：在内存和上下文窗口受限的情况下，AGSERVE的ECE驱逐策略相比LRU，在批处理大小为8时缓存命中率提升了2.86倍。其首token延迟（TTFT）显著低于vLLM，这得益于ECE策略和原地校准带来的高缓存重用率。

7.4.2 SGC 质量维护模块（QMM）性能

R-Judge正确性（图13, 表3）：R-Judge在识别不满意结果方面达到了95.2%的召回率。表3展示了不同严格度阈值$\theta$下的假阳性和假阴性率。

Q-Judge正确性（表1）：Q-Judge在任务难度判断上实现了70.4%的准确率，并且相比其他方法，“过度处理”（预测难度高于实际）的情况显著更少，符合设计目标。

效率（图14）：QMM在常规交互中引入的开销可忽略不计，在需要进行路由决策时开销也可接受。

表1：路由模型性能。S/M/L代表小/中/大标签。

表3：不同θ下R-Judge的假阳性和假阴性率。

7.4.3 RS 动态分配性能

实验设置：在一台A800节点上，通过调整R-Judge的阈值$\theta$来模拟需求不平衡的场景。
基线方法：两种固定分配策略，FS1（4个GPU给8B模型，4个给70B模型）和FS2（8个GPU全给70B模型）。
实验结果（表2）：AGSERVE的动态分配策略相比FS1，P90延迟降低了14%；相比FS2（一种传统的LLM服务方式），平均端到端延迟降低了49%，展示了动态资源分配的显著优势。

表2：动态和静态分配策略的延迟比较。Average、P90和P50分别表示端到端延迟的平均值、90百分位数和中位数。

A7 补充细节

8 局限性与讨论

R-Judge 敏感性。AGSERVE的级联效果依赖于R-Judge。当$\theta \equiv 0$时，AGSERVE退化为始终使用GPT-4o；当$\theta \equiv 1$时，退化为§7.2中的Cascade策略。尽管附录§E.8显示R-Judge的性能与人类相当，但我们承认，用更充分的数据训练的裁判可能会更好地服务于Agent。

节点路由。先进的LLM服务框架如SGLang 【62, Sglang: Efficient execution of structured language model programs, 2024, NeurIPS】和MoonCake 【41, Mooncake: Trading more storage for less computation — a KVCache-centric architecture for serving LLM chatbot, 2025, FAST】通过前缀匹配来决定请求的机器路由。由于测试平台规模有限，AGSERVE将每个会话绑定到一个特定实例（即首次调度时最空闲的实例）。我们认识到未来有两个值得探索的方向：（1）迁移正在运行的会话以平衡负载；（2）利用图4(a)中提示长度的可预测性来匹配实例。

大规模Agent服务。先前的工作【48, Llumnix: Dynamic scheduling for large language model serving, 2024, OSDI；42, Toward inference delivery networks: Distributing machine learning with optimality guarantees, 2023, IEEE/ACM Transactions on Networking】表明，分布式调度在大规模环境中表现更优。我们在附录§F中提供了一个关于分布式AGSERVE进行大规模服务的理论模拟，展示了AGSERVE的潜在应用。

更广泛的影响。AGSERVE中使用的技术使Agent服务更便宜、更高效，并且除了现有Agent和LLM的影响外，不带来额外的社会影响。我们依赖外部保障措施，如红队测试，来最小化负面影响。

A5 结论

我们提出了AGSERVE，这是首个旨在克服Agent服务中固有的成本-质量权衡的Agent服务系统。AGSERVE解决了Agent服务的独特需求，包括可预测的请求模式、不断增长的推理复杂性和动态的资源需求。它结合了会话感知的KV缓存管理、质量感知的模型级联和自适应的资源调度，以支持跨Agent会话的高效、高质量交互。实验结果表明，AGSERVE在保持与最先进LLM服务系统相媲美的服务质量的同时，显著降低了延迟和资源成本。

A6 附录

A 理论证明

A.1 原地KV缓存校准

RoPE原理。RoPE是一种相对位置编码方法，使用循环函数进行位置编码。形式上，我们有一个相对于token位置p的旋转矩阵：

$$\begin{aligned} R(p)=\begin{pmatrix} \cos(p\theta_0) & -\sin(p\theta_0) & 0 & \cdots & 0 \\ \sin(p\theta_0) & \cos(p\theta_0) & 0 & \cdots & 0 \\ 0 & 0 & \cos(p\theta_1) & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \cos(p\theta_{N/2-1}) \end{pmatrix} \end{aligned}$$

其中$\theta_i$是一个与维度相关的参数。RoPE对token $x_p$执行$Q_p = R(p)(x_p W_Q)$和$K_p = R(p)(x_p W_K)$。我们记$\hat{K}_p = x_p W_k$。换句话说：

校准过程。当发生截断时，我们仍然有$\hat{K}'_{p'} = \hat{K}_p$，这部分不改变。

$$\begin{aligned} K_{p^{\prime}}^{\prime}=\begin{pmatrix}\cos(p^{\prime}\theta_{0})*\hat{K}_{p,0}-\sin(p^{\prime}\theta_{0})*\hat{K}_{p,1}\\\sin(p^{\prime}\theta_{0})*\hat{K}_{p,0}+\cos(p^{\prime}\theta_{0})*\hat{K}_{p,1}\\\cos(p^{\prime}\theta_{1})*\hat{K}_{p,2}-\sin(p^{\prime}\theta_{1})*\hat{K}_{p,3}\\\vdots\\\sin(p^{\prime}\theta_{N/2-1})*\hat{K}_{p,N-2}+\cos(p^{\prime}\theta_{N/2-1})*\hat{K}_{p,N-1}\end{pmatrix} \end{aligned}$$

这里，我们验证公式1的正确性。对于$K'_{p', 2i}$：

另一方面，对于$K'_{p', 2i+1}$：

A.2 ECE策略在特定设置下的最优性

证明思路。在本节中，我们证明了在每个会话缓存大小相同的情况下，SAS的ECE策略的最优性。假设存在另一种驱逐策略A，它在某个会话访问序列上实现了比ECE更高的会话缓存命中率。设$H_{ECE}$是ECE在会话访问序列S上实现的命中率，而$H_A$是A产生的命中率。根据假设，$H_A > H_{ECE}$。
$H_{\mathrm{A}}>H_{\mathrm{ECE}}$
反证法。考虑A和ECE在时间t第一次做出不同驱逐决策的时刻。设时间t之前的缓存中会话相同，且当前访问需要驱逐。ECE驱逐会话$sc_o$，而A驱逐另一个不同的会话$sc_a \neq sc_o$。由于ECE的定义是驱逐未来最长时间内不会被使用的会话，因此在完美预知未来访问的情况下，$sc_o$是最佳选择。
两种情况分析：
1. 如果$sc_a$在未来比$sc_o$更早被使用，那么A的决策将比ECE更早导致缓存未命中，从而降低$H_A$。
2. 如果$sc_a$比$sc_o$更晚被使用或再也不被使用，那么ECE本应选择$sc_a$，这与ECE的定义相矛盾。
在任何一种情况下，A都不能产生比ECE更高的缓存命中率，这与我们的假设相矛盾。因此，在这种情况下，SAS的ECE策略的最优性得以证明。

B 背景补充细节

模型能力与会话轮次的关系。正如R-Judge所观察到的，一个Agent在最终成功或达到轮次限制之前，可能会面临无效操作或违反预设规则的情况。我们在表4中展示了20个Alfworld Agent案例的结果详细分析。可以看出，在后期阶段和使用较小模型时，出现无效操作或格式错误的趋势会增加。

表4：Llama-8B和Llama-70B之间的结果比较。

C 训练补充细节

数据集。Chatbot-Arena数据集包含33k对人类标记的偏好数据，涉及的模型包括fastchat-t5-3b、gpt-3.5-turbo、gpt-4等。

C.1 Q-Judge 训练

数据处理。为便于训练，我们将竞技场中的模型按模型大小和排名递增分为三层。如果较小模型的响应胜过或与较大模型的响应持平，则该问题被归类为可由较小模型解决；否则，它被认为足够具有挑战性，需要更强大的模型。
训练过程。我们在BERT【22, Bert: Pre-training of deep bidirectional transformers for language understanding, 2019, NAACL-HLT】之上训练Q-Judge 10个epoch，批处理大小为16，预热步骤为500，使用一个A6000 GPU。选择BERT作为骨干网络是因为Q-Judge调用频率较低，且路由任务需要高精度。训练耗时2.9小时。在自定义损失下，Q-Judge在评估集上达到52%的准确率。请注意，这里的准确率定义与§7.4.2中的不同，后者由于标注困难定义了更宽松的限制。Q-Judge训练集和评估集上的标签分布如表5所示。

表5：Q-Judge训练集的数据分布

C.2 R-Judge 训练

数据处理与训练。我们在DistilBERT【43, Distilbert, a distilled version of bert: Smaller, faster, cheaper and lighter, 2019, arXiv】之上，使用Chatbot-Arena数据集的另一个定制版本训练R-Judge。选择DistilBERT作为骨干网络是因为R-Judge调用更频繁，其效率至关重要。我们将获胜者的响应标记为“有能力”，失败者的响应标记为“无能力”。对于平局，我们只将较小模型的响应视为“有能力”，并丢弃较大LLM的响应。我们训练R-Judge 10个epoch，权重衰减为1e-2，预热步骤为500。训练耗时17分钟。RJ0.5在评估集上与人类选择的偏好达到82.8%的一致率。R-Judge训练集和评估集上的标签分布如表6所示。

表6：R-Judge训练集的数据分布

D AGSERVE 额外实现细节

代码实现。我们用大约数千行Python和CUDA代码实现了AGSERVE系统。AGSERVE为自动Agent编程提供了一个接口，并支持模型层次结构定制和敏捷的Agent服务。
LLM服务。AGSERVE的SAS部分基于先进的LLM服务系统vLLM【24，Efficient memory management for large language model serving with pagedattention，2023，SOSP】。AGSERVE支持会话缓存管理器和实例上的两级负载均衡以加速推理。我们扩展了API来记录每个请求的会话ID和会话缓存重用模式信息（用于截断和恢复），并提供了更多API来支持动态模型分配和主动会话缓存释放。AGSERVE支持通过Ray【35，Ray: A distributed framework for emerging {AI} applications，2018，OSDI】启动预设模型的会话感知实例。
ECE驱逐决策算法。算法1展示了驱逐决策中使用的伪代码。L1-L15采用类似背包的算法，根据实际释放的块数和被驱逐的会话数，给出最优的重计算开销。L18-L19计算每个会话的重计算惩罚。L20-L26遍历不同的i，定义实际要驱逐的会话数。AGSERVE通过维护每个会话的元数据（包括最近几轮的持续时间、上次到达时间等）来预测ETA，并使用平均轮次持续时间计算ETA。该预测对意外行为和工作负载变化具有鲁棒性。

Algorithm 1: ECE Eviction Policy

Input: Number of ongoing sessions n, number of running sessions r, number of waiting sessions w, session cache size (can be zero) l[1 . . . n] ranked by ETA, maximum batch size K, prefilling per-block overhead P, decoding time consumption D
Output: Available session nums k, sessions to evict E

1 Function Knapsack(i, W):
2     Initialize dp[0] ← 0, dp[1 . . . W] ← ∞, S[0..W] ← [];
3     Initialize asp ← 0, aval ← ∞, as ← []; // The first i sessions cache shall remain in the cache and is not considered in eviction
4     for x ← i + 1 to n do
5         for j ← W downto W − l[x] do // for the cases where released blocks exceeds the requiring W
6             val = dp[j] + v[x];
7             if val < aval then
8                 aval ← val;
9                 as = S[j] + [x];
10                asp = j + l[x]; // No need to update dp, since no better solution comes based on asp
11        for j ← W − l[x] downto 0 do // for the cases where released blocks does not exceed the requiring W
12            val = dp[j] + v[x];
13            if val < dp[j + l[x]] then
14                dp[j + l[x]] ← val;
15                S[j + l[x]] = S[j] + [x];
16    return aval, asp, as;
17 k ← Dr · (n − r), E ← [];
18 rsp ← 0, asp ← 0; // Calculate the recomputation penalty for each session
19 for i ← 0 to n do
20    v[i] ← P · l[i] · (n − i + 1); // Walk through all possible batch size.
21 for i ← 1 to min(w, K − r) do
22    rsp ← rsp + rs[i] − l[i]; // Check if new session needs to be evicted, improve efficiency
23    if asp<rsp then
24        t, asp, Ei ← Knapsack(i,rsp);
25        val = t + Dr+i · (n − r − i);
26        if val<k then
27            k ← i, E ← Ei;
28 return k, E

算法复杂度。每个SAS独立运行其ECE算法。理论算法复杂度为O(knW)。我们用Python字典优化了大的常数W（背包大小）。由于每个会话的上下文很长，上下文中维护的会话缓存数量有限。因此，即使在最坏情况下，每个ECE决策的延迟也低于0.1毫秒，我们认为这与典型的推理延迟相比可以忽略不计。
模型层次结构。AGSERVE采用三层模型结构：Llama-3的8B和70B版本作为前两层，GPT-4o作为第三层的外部API。选择这种结构是因为测试平台的物理限制、各层模型之间显著的性能差距，以及Llama系列模型的广泛适用性。AGSERVE的级联结构是灵活的，用户可以通过自定义数据集和重新训练QMM来增减层级。
容错性。如果一个实例失败，客户端会向调度器请求重新路由。如果调度器失败，AGSERVE会退化为一个启用会话缓存的常规LLM服务系统。
Agent编程。AGSERVE提供了一套类似LangChain【25, LangChain. Build an Agent, 2025】的API，用于Agent编程，如表7所示。Agent开发者可以构建自己的实现，并指定使用的LLM、质量阈值等。

表7：AGSERVE API

E 评估补充细节

E.1 实现的Agent

我们实现了以下四种Agent来展示AGSERVE的性能：
* AlfWorld (AW)【45, Alfworld: Aligning text and embodied environments for interactive learning, 2020, arXiv】：一个在模拟环境中导航和交互的具身家庭助理。
* Card Game (CG)【29, Agentbench: Evaluating llms as agents, 2023, arXiv】：一个玩名为AquaWar的双人纸牌游戏的Agent，通过多Agent协作实现。
* Knowledge Graph (KG)【29, Agentbench: Evaluating llms as agents, 2023, arXiv】：查询知识图谱以回答问题，实现为可恢复的Agent。
* Mind2Web (M2W)【12, Mind2web: Towards a generalist agent for the web, 2024, NeurIPS】：在真实网站上导航和执行任务的Agent。

E.2 不同Agent的质量指标

我们概述了本节中质量指标的计算方法。如果会话以COMPLETED或TASK_LIMIT_REACHED状态成功结束，则sc设为25；否则设为0。

• AW Agent质量：$Q_{AW} = sc + vc + (25 - \frac{rounds}{2})$。vc代表任务完成度（50或0），并对交互轮次进行惩罚。
  
  $$Q_{AW} = sc + vc + \left( 25 - \frac{\text{rounds}}{2} \right)$$

• CG Agent质量：基于正常游戏轮次比例、胜利轮次比例和生存轮次。
  $$Q_{CG} = \frac{\text{full\_play}}{\text{test\_times}} \times 25 + \frac{\text{harm\_on\_enemy}}{\text{total\_HP} \times \text{test\_times}} \times 50 + 25 \times \max(\frac{\text{round\_num}}{50 \times \text{test\_times}}, 1)$$
• KG Agent质量：$Q_{KG} = sc + 50 \times f1 + (25 - \frac{rounds}{2})$。基于F1分数和操作轮次数。
  $$Q_{KG} = sc + 50 \times \text{f1} + \left( 25 - \frac{\text{rounds}}{2} \right)$$
• M2W Agent质量：$Q_{M2W} = sc + element\_acc \times 25 + step\_sr \times 25 + action\_f1 \times 25$。基于元素准确率、步骤成功率和动作F1分数。
  $$Q_{M2W} = sc + \text{element\_acc} \times 25 + \text{step\_sr} \times 25 + \text{action\_f1} \times 25$$

E.3 开源模型的成本

我们使用云服务器的零售价来估算开源模型的成本。对于A6000测试平台，Llama-8B每会话成本约为$(2.17 \times 10^{-5})$/s，Llama-70B约为$(1.73 \times 10^{-4})$/s。对于A800测试平台，每会话成本约为$(2.86 \times 10^{-4})$/s。

E.4 AGSERVE 设置

我们将质量控制阈值$\theta$设为0.5。除M2W外，所有Agent的推理质量检查频率ν设为4。对于M2W，由于其会话通常在2到3轮内完成，ν设为1。

E.5 端到端级联服务细节

表8显示了在不同定价方案下，AGSERVE和其他基线操作Alfworld Agent的成本。即使在租金折扣的情况下，AGSERVE的成本优势依然显著，以GPT-4o 9.04%的成本就能达到相似性能。

表8：在不同定价方案下，Alfworld的AGSERVE和基线成本。

E.7 消融研究细节

SAS效率设置。在A6000 GPU上，我们将SAS的最大内存利用率设置为0.37，最大模型长度为4096，以促进驱逐和截断的发生，从而更好地展示SAS的能力。
QMM效率。为最小化偏见，我们逐轮向标注员展示观察和LLM的响应，他们对会话的最终结果或模型大小一无所知。我们还利用投票机制，每个标签至少由三名标注员同意。表9比较了运行Q-Judge、R-Judge和四种Agent的响应时间开销，显示QMM的开销很小。
动态分配案例研究。图15展示了动态分配实验期间不同模型的提示和生成吞吐量。AGSERVE首先因70B实例需求量大而将2个GPU从8B实例移至70B实例，之后又在8B模型需求增加时动态移回。这展示了RS根据实时负载动态调整资源的能力。

表9：QMM实时完成评估任务。

E.8 理想类人裁判的性能

在Agent服务的快节奏请求模式中，人类无法实时判断。我们的经验表明，人类需要10秒或更长时间来阅读和理解上下文，然后才能对响应进行评分。我们让一位人类专家为每个响应决定是否迁移，并评估AW Agent的成本和质量。表10显示，人类裁判的性能仅略优于AGSERVE，表明R-Judge对于三层会话生命周期管理已经足够强大。

表10：Alfworld的Agent服务中类人裁判的评估。Overhead列显示了人类判断每个请求满意度所需的时间。Gross cost显示了如果将人类判断的开销计入计算后的总成本。

F 大规模 AGSERVE

模拟设置。虽然AGSERVE采用集中式调度器，但它被设计为支持分布式调度。我们通过以下方法模拟了AGSERVE在60个节点（每节点8个GPU）的大规模集群上的性能：基于GPU设置、并发请求和模型大小的推理延迟模拟；基于LLM大小/能力的质量问题触发概率；以及一个虚拟的“待完成轮次”概念。
模拟结果。如表11所示，分布式调度版本的AGSERVE在加速调度、减少端到端延迟的同时，提高了集群的公平性。

表11：在不同Agent启动率（LR）下，集中式（C）和分布式（D）调度的端到端延迟（EL）、质量（Q）和调度延迟（SL）的比较。EL和SL单位为秒。