Autellix: An Efficient Serving Engine for LLM Agents as General Programs

发表时间: 2025-02 · arXiv:2502.13965 (UC Berkeley / Google)

文章标题: Autellix: An Efficient Serving Engine for LLM Agents as General Programs
作者/机构: Michael Luo (UC Berkeley, Google DeepMind), Xiaoxiang Shi (Shanghai Jiao Tong University), Colin Cai (UC Berkeley), Tianjun Zhang (UC Berkeley), Justin Wong (UC Berkeley), Yichuan Wang (UC Berkeley), Chi Wang (Google DeepMind), Yanping Huang (Google DeepMind), Zhifeng Chen (Google DeepMind), Joseph E. Gonzalez (UC Berkeley), Ion Stoica (UC Berkeley)

A1 主要贡献

大型语言模型（LLM）应用正从简单的聊天机器人演变为动态、通用的智能体程序，这些程序通过扩展LLM调用和输出Token来帮助AI智能体进行推理、探索和解决复杂任务。然而，现有的LLM服务系统忽略了程序与调用之间的依赖关系，错失了重要的优化机会。分析表明，提交给LLM服务引擎的程序会经历很长的累积等待时间，这主要是由单个LLM请求和程序两个层面的队头阻塞（head-of-line blocking）造成的。

核心问题与研究目标：
本文旨在解决现有LLM服务系统在处理由多个LLM调用组成的复杂智能体程序时效率低下的问题。这些系统将每个LLM调用视为独立的请求，忽略了它们所属的程序上下文，导致了两个层面的队头阻塞（HoL Blocking）：
1. 调用级HoL阻塞：长时间运行的LLM调用会阻塞后续的短时间调用。
2. 程序级HoL阻塞：拥有大量LLM调用的长程序会持续占用资源，延迟短程序的执行，即使使用了抢占式调度也无法完全避免。

为了解决这些问题，本文提出了Autellix，一个将程序作为一等公民对待的LLM服务系统，其核心目标是最小化程序的端到端延迟。

创新点与主要贡献：
本文的主要贡献如下：
* 首次将智能体程序形式化：本文首次将智能体程序（agentic programs）形式化为由LLM调用和外部中断组成的动态、不确定的有向无环图（DAG）。这为从系统层面优化这类程序提供了理论基础。
* 提出程序感知的非预见性调度器：Autellix利用程序级别的统计信息（如程序内已完成LLM调用的累积服务时间）来指导其调度器。这种非预见性（non-clairvoyant）调度器不需要预先了解程序的工作负载或结构。
* 提出数据局部性感知的负载均衡策略：Autellix利用一个简单的负载均衡策略，在多个引擎间平衡数据局部性和KV缓存的重新计算开销，从而优化多引擎部署下的性能。
* 实现并验证了高效的系统：Autellix作为一个易于部署的系统，通过有状态API与现有编程和智能体框架无缝集成，并在评估中展示了显著的吞吐量提升。与vLLM等最先进系统相比，在相同延迟下，Autellix可将程序吞吐量提高4-15倍。


图1：智能体程序的执行工作流。智能体程序是遵循有向无环图（DAG）的高度动态的执行工作流。它由一个或多个LLM智能体的LLM调用和外部中断（即工具调用、人类输入）组成。


图2：LLM服务引擎上LLM调用执行的甘特图，最大批处理大小（BS）为2（Y轴），时间为解码步数（X轴）。(a) 四个程序的LLM调用次数和每次调用的解码步数不同。显示了长程序（A, B）和短程序（C, D）。(b) 先来先服务（FCFS）因长LLM调用延迟短LLM调用而导致队头阻塞，总等待时间为18个单位。(c) 多级反馈队列（MLFQ）通过抢占减少了阻塞，但仍存在程序级阻塞。程序A和B的新LLM调用被置于最高优先级队列，延迟了程序D，导致等待时间为18个单位。(d) 程序级已达服务（PLAS）利用程序级统计信息，延迟A和B的后续调用以优先处理程序C和D，将等待时间减少到12个单位。

A3 背景知识与关键观察

2 背景与相关工作

为了详细介绍Autellix的相关背景，我们简要概述了新兴的AI智能体基础设施及其应用，分为LLM服务层（§ 2.1）和更高级别的智能体层（§ 2.2），如图3所示。

2.1 LLM服务层

LLM推理过程。驱动聊天机器人和AI应用的大型语言模型（LLM）主要使用Transformer架构【71，Attention is all you need, 2023】，包括GPT、Claude和LLaMA等仅解码器模型【10，Language models are few-shot learners, 2020；28，Mistral 7b, 2023；69，Llama: Open and efficient foundation language models, 2023；70，Llama 2: Open foundation and fine-tuned chat models, 2023】。对于每个请求，LLM推理分为两个阶段：预填充（prefill）阶段，将输入提示转换为中间Token状态；以及解码（decoding）阶段，基于先前的Token序列自回归地逐个生成新Token。为了减少计算量，LLM服务系统利用KV缓存来存储中间Token状态，以加速Token生成【36，Efficient memory management for large language model serving with pagedattention, 2023；86，Orca: A distributed serving system for Transformer-Based generative models, 2022】。

LLM服务。LLM服务系统管理着LLM调用在多个引擎间的路由以及在单个引擎内的执行（图3）。在引擎内部，LLM服务的最新创新反映了传统操作系统（OS）中的概念，如内存管理、内核优化和调度【43，Aios: Llm agent operating system, 2024；67，Llumnix: Dynamic scheduling for large language model serving, 2024】。现有解决方案，如vLLM，集成了虚拟内存和分页技术以减少KV缓存碎片【36，Efficient memory management for large language model serving with pagedattention, 2023】，引入共享内存以在LLM请求间缓存前缀【41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024；90，Sglang: Efficient execution of structured language model programs, 2024】，并管理GPU、CPU和磁盘之间的缓存层次结构【62，S-lora: Serving thousands of concurrent lora adapters, 2024；63，Flexgen: High-throughput generative inference of large language models with a single gpu, 2023；94，Nanoflow: Towards optimal large language model serving throughput, 2024】。其他技术改进了GPU内核实现以加速自注意力【16，Flashattention: Fast and memoryefficient exact attention with io-awareness, 2022】，对不同操作符进行流水线处理【94，Nanoflow: Towards optimal large language model serving throughput, 2024】，并实现更好的张量或流水线并行【39，Alpaserve: Statistical multiplexing with model parallelism for deep learning serving, 2023；77，Fast distributed inference serving for large language models, 2024】。最后，LLM引擎可以利用更好的调度策略，如将预填充和解码打包在一起【2，Taming throughput-latency tradeoff in llm inference with sarathi-serve, 2024】和抢占LLM请求【77，Fast distributed inference serving for large language models, 2024】，以改善响应时间。在多个LLM引擎之间，服务系统采用负载均衡技术，如实时迁移【68，Llumnix: Dynamic scheduling for large language model serving, 2024】，分离预填充和解码【57，Mooncake: A kvcache-centric disaggregated architecture for llm serving, 2024】，构建前缀树【66，Preble: Efficient distributed prompt scheduling for llm serving, 2024】，并在引擎间迁移KV缓存【41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024】，以满足请求的服务等级目标（SLO）并改善尾部延迟。总的来说，上述技术优化的是独立的LLM请求，相当于通用程序中的一个函数调用。而Autellix则专注于程序级别的优化，特别是调度——类似于传统操作系统管理CPU核心上的整个进程。


图3：AI智能体基础设施。上层：开发者和用户构建并执行智能体程序，这些程序协调执行，并在智能体、工具和人类之间持久化全局累积历史。下层：LLM服务系统处理智能体的LLM调用，并在一个或多个LLM引擎之间路由这些调用。

2.2 智能体层

智能体程序。在LLM推理层之上，开发者构建复杂的智能体程序来协调智能体、工具和人类之间的交互（图3）。具体而言，本工作关注LLM智能体，其定义为一个元组，包含指定智能体角色的系统提示和LLM模型类别。与传统操作系统的进程和中断类似，智能体程序要么通过LLM调用直接与LLM服务层交互，要么参与外部中断——即在LLM引擎之外花费的时间。具体来说，智能体可以与工具交互以执行通用函数或外部API，从而能够控制数据库、机器人系统或互联网等环境【6，Digirl: Training in-the-wild device-control agents with autonomous reinforcement learning, 2024；54，Gorilla: Large language model connected with massive apis, 2023；59，Toolformer: Language models can teach themselves to use tools, 2023；60，Lm-nav: Robotic navigation with large pretrained models of language, vision, and action, 2022；83，Webshop: Towards scalable real-world web interaction with grounded language agents, 2023；93，Llm-enhanced data management, 2024】。最重要的是，像LangChain【15，Langchain: Building applications with llms through composability, 2023；37，Langgraph: A library for building stateful, multi-actor applications with llms, 2024】和Autogen【78，Autogen: Enabling next-gen llm applications via multi-agent conversation, 2023】这样的智能体编排框架为开发者提供了管理程序控制流的原语，决定何时执行智能体、调用工具或请求人类输入。这些原语遵循通用的编程语义，包括条件语句、循环、错误处理和终止条件【32，Dspy: Compiling declarative language model calls into self-improving pipelines, 2023；37，Langgraph: A library for building stateful, multi-actor applications with llms, 2024；78，Autogen: Enabling next-gen llm applications via multi-agent conversation, 2023；90，Sglang: Efficient execution of structured language model programs, 2024】。最后，程序会维护一个全局历史记录，记录智能体、工具和人类的输出【37，Langgraph: A library for building stateful, multi-actor applications with llms, 2024；41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024；53，Memgpt: Towards llms as operating systems, 2024；81，Buffer of thoughts: Thought-augmented reasoning with large language models, 2024】。例如，基于LLM的聊天机器人会累积LLM智能体输出和人类输入之间的消息【48，Gpt-4 technical report, 2023】。重要的是，Autellix不修改程序层。相反，它在程序运行时动态构建程序执行图（DAG）的内部状态，并将其存储在进程表中（§5）。

智能体应用。除了标准的聊天机器人（图1a），智能体应用（即程序的实例化）可以自动化或辅助完成复杂任务，包括网页或用户界面（UI）导航（例如OpenAI的Operator）【6，Digirl: Training in-the-wild device-control agents with autonomous reinforcement learning, 2024；27，A real-world webagent with planning, long context understanding, and program synthesis, 2024；47，Openai operator: Computer using agent, 2025；92，Webarena: A realistic web environment for building autonomous agents, 2024】、解决Github问题【29，SWE-bench: Can language models resolve real-world github issues?, 2024；74，Openhands: An open platform for ai software developers as generalist agents, 2024；80，Swe-agent: Agent-computer interfaces enable automated software engineering, 2024】、解决IMO级别的数学问题【18，Ai solves imo problems at silver medal level, 2024；35，Leanagent: Lifelong learning for formal theorem proving, 2024】、从多个来源进行事实核查和总结（图1c）【23，Genspark: The ai agent engine, 2024；41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024】以及实现精确的机器人控制【58，Two heads are better than one: Collaborative llm embodied agents for human-robot interaction, 2024】。许多应用通过扩展推理时计算——即LLM调用的数量以及相应的总解码Token数——来提高其在复杂任务上的性能。这些测试时方法包括：通过分步推理来分解任务【55，Measuring and narrowing the compositionality gap in language models, 2023；76，Chain-of-thought prompting elicits reasoning in large language models, 2023】，通过显式注入思想来引导推理【85，React: Synergizing reasoning and acting in language models, 2023】，通过规划或搜索来探索可能的解决方案【8，Graph of thoughts: Solving elaborate problems with large language models, 2024；84，Tree of thoughts: Deliberate problem solving with large language models, 2023；91，Language agent tree search unifies reasoning acting and planning in language models, 2024】，通过自我批判来评估行动【42，Stylus: Automatic adapter selection for diffusion models, 2024；89，Judging llm-as-a-judge with mt-bench and chatbot arena, 2023】，通过自我反思从失败中学习【34，Training language models to self-correct via reinforcement learning, 2024；64，Reflexion: Language agents with verbal reinforcement learning, 2023】，以及多智能体协作【21，Improving factuality and reasoning in language models through multiagent debate, 2023；78，Autogen: Enabling next-gen llm applications via multi-agent conversation, 2023】。特别是，结合了思维链（CoT）技术的单线程推理与行动（ReAct）智能体（图1b），最近被集成到Deepseek风格（或o1风格）的LLM之上，以实现自动推理和工具调用【19，Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025；74，Openhands: An open platform for ai software developers as generalist agents, 2024；75，Ragen: A general-purpose reasoning agent training framework, 2025】。一个多线程程序，蒙特卡洛树搜索（MCTS）【91，Language agent tree search unifies reasoning acting and planning in language models, 2024】，则集成了并行规划、自我批判、自我反思和多智能体协作（图1d）。除了MCTS，分布式程序还可能包含best-of-N采样、波束搜索、前瞻技术和遗传算法，以探索和发现最优解【13，Inference-aware fine-tuning for best-of-n sampling in large language models, 2024；17，Networks of networks: Complexity class principles applied to compound ai systems design, 2024；38，Evolving deeper llm thinking, 2025；65，Scaling llm test-time compute optimally can be more effective than scaling model parameters, 2024】。鉴于LLM的概率性，这些推理时技术的广度表明智能体程序及其应用具有三个特性：（1）动态性，因为同一程序对于不同的用户提示可能产生完全不同的执行模式；（2）不确定性，因为未来是未知的，例如程序何时决定终止；（3）分布式，许多程序利用并行调用。因此，Autellix是“非预见性”的（non-clairvoyant），在对程序的工况或执行图没有任何先验知识的情况下运行。

3 动机

当前AI智能体基础设施的局限性。如今的AI智能体基础设施将LLM服务系统与智能体程序解耦（§2）。随着组织从服务LLM查询转向更高级别的AI应用，LLM引擎必须针对程序级目标进行优化，例如响应时间或端到端延迟【41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024】。一个单线程程序的端到端延迟由三个部分组成：（1）等待时间，即程序LLM调用在引擎上的总排队时间；（2）执行时间，即LLM调用的累积前向传播时间；（3）中断时间，即等待外部中断（如工具调用或人类输入）的时间。由于第三部分与LLM服务无关，本节旨在识别并解决减少等待时间（§3.1）和执行时间（§3.2）的问题与机遇，这些问题将在Autellix的调度策略设计中得到解决（§4）。

3.1 程序级等待时间

等待时间是主要瓶颈。图5显示，在各种智能体工作负载中——从经典的聊天机器人到ReAct和MCTS程序——随着负载增加，程序的大部分时间都花在等待上。因此，Autellix优先减少等待时间，这不仅能改善程序的延迟，还能提高LLM引擎的吞吐量。调用完成得越快，程序发出后续调用的速度就越快，从而增加了LLM调用的到达率。图4展示了在使用LLaMA-3.1-8B【24，The llama 3 herd of models, 2024】在单个A100-80GB GPU上运行一小时的聊天机器人对话【1，Sharegpt, 2023】的稳态行为。与vLLM的先来先服务（FCFS）策略相比，Autellix能持续多处理10个并发LLM调用，为提高吞吐量提供了更多的批处理机会。


图5：不同程序和系统负载下的程序执行与等待时间。在中等负载下，程序大部分时间都在等待。等待时间的长短取决于工作负载。


图4：稳态下一小时内LLM服务引擎中的LLM调用数量。优化程序的等待时间可以增加稳态下的LLM调用量。

调用级阻塞。第一个挑战是LLM调用级的队头阻塞（HoL）。解码时间长的LLM调用会延迟解码时间短的调用，导致显著的等待时间【77，Fast distributed inference serving for large language models, 2024】。这个问题在像vLLM【36，Efficient memory management for large language model serving with pagedattention, 2023】这样的服务引擎中很明显，它们会等待正在进行的调用完成解码后才调度新的调用。在我们评估的工作负载中，由于解码步数存在长尾分布（图11），HoL阻塞问题非常严重。为了衡量阻塞，图6测量了Chatbot和MCTS工作负载中LLM请求的等待时间与执行时间之比，作为输出Token数的函数。对于FCFS策略，HoL阻塞增加了短LLM调用的等待时间，从而增加了该比率。抢占机制，类似于操作系统调度器中断长时间运行的进程，通过偏向较短的LLM调用来缓解HoL阻塞。图6显示，多级反馈队列（MLFQ）这种抢占式算法，使得短解码请求的比率更小。然而，没有程序级统计信息的抢占可能无法完全解决问题，原因如下。


图6：LLM调用和程序的等待时间与执行时间之比。当短LLM调用和程序的等待时间远超其执行时间时，发生队头阻塞。

程序级阻塞。第二个挑战是程序级的队头阻塞，即包含大量LLM请求的长程序会延迟短程序的执行。现有的LLM调度器是程序无关的；它们在调度单个LLM请求时不考虑其在整个程序中的位置，导致次优决策。我们的评估显示，每个程序的LLM调用数量呈长尾分布，这加剧了程序级阻塞（§6）。为了量化程序级阻塞，图6测量了程序的等待时间与执行时间之比，相对于LLM调用的数量。对于两种工作负载，当LLM调用数量较少时，FCFS和MLFQ的比率都较高，表明短程序等待了很长时间。因此，像MLFQ这样的抢占式调度策略的性能可能接近甚至差于FCFS（§6）。在没有程序级上下文的情况下，MLFQ盲目地优先处理新的LLM请求，当长程序的新LLM调用被优先处理时，会导致短程序的饥饿。

3.2 程序级执行时间

执行时间的优化。一个程序的执行时间在很大程度上取决于LLM引擎管理预填充和解码阶段的效率。在通常具有长累积预填充的智能体工作负载中，Autellix专注于优化预填充性能。具体来说，通过前缀缓存可以消除大部分预填充计算。该技术存储和重用相关的键值（KV）缓存条目——例如系统提示——以在不同LLM请求之间共享【41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024；90，Sglang: Efficient execution of structured language model programs, 2024】。

数据局部性。图7展示了平均缓存命中率随输入长度的变化。缓存命中率定义为传入的LLM调用在LLM引擎的KV缓存中预计算输入Token的百分比。值得注意的是，在单个程序内部，所有输入长度的缓存命中率都保持在90%以上，这表明同一程序内的LLM调用共享相同的上下文。相比之下，当考虑不同程序时，缓存命中率随输入长度呈指数级衰减，这表明程序之间通常只共享系统提示。这些结果表明，跨引擎的LLM服务系统应考虑程序的数据局部性，因为其大部分KV缓存可以被未来的LLM请求重用。


图7：程序内部和跨程序的LLM调用的前缀缓存命中率。同一程序内的LLM调用通常共享KV缓存，而跨程序的LLM调用通常不共享。

A2 方法细节

4 Autellix设计

我们首先介绍Autellix的整体架构（§4.1），然后探讨其两个关键组件：（1）旨在减少调用级和程序级阻塞的程序感知调度器（§4.2），以及（2）数据局部性感知的负载均衡器（§4.3）。

4.1 概述

Autellix的核心定位与目标。Autellix是一个为智能体程序而非单个LLM请求设计的高级服务引擎。Autellix专注于三个主要目标：（1）为用户改善程序的整体端到端延迟，（2）为提供商最大化GPU利用率，以及（3）通过改善第95和第99百分位延迟来缓解程序饥饿，提高公平性。

假设。Autellix是非预见性的（non-clairvoyant）；它假设对程序到达、执行工作流的结构或一般工作负载分布没有任何先验知识。当一个程序到达时，其执行DAG最初是未知的；Autellix在程序运行时动态构建其内部表示（IR）。这种灵活性使Autellix能够泛化到任何在底层引擎上调用LLM的程序。与先前工作【41，Parrot: Efficient serving of llm-based applications with semantic variable, 2024】将静态LLM应用提交给引擎不同，Autellix假设用户在本地机器上运行通用的Python程序，这些程序调用Autellix的后端（§5）。

架构。图8展示了Autellix的整体架构。与假定LLM调用是无状态的现有LLM引擎不同，Autellix是有状态的：程序从用户的本地机器执行，与Autellix建立一个会话，并随时间使用关联的会话ID发出LLM调用。我们将在第5节中进一步详细介绍底层实现。当会话开始时，Autellix会在一个全局进程表中添加一个相应的条目（§4.2）。该表跟踪程序元数据，包括总服务时间、线程级元数据以及程序LLM调用的等待时间。引擎级调度器（§4.2）和有状态负载均衡器（§4.3）都利用该表来为下一个解码批次调度LLM调用，并根据程序的数据局部性将LLM调用路由到某个引擎。


图8：Autellix的系统架构。用户在本地运行他们的程序，这会启动一个有状态的会话并向Autellix的后端提交LLM调用。Autellix利用一个全局进程表来跟踪会话，并更好地为其自定义负载均衡器和调度器提供信息。

4.2 程序感知调度器

调度器设计目标。我们提出了一个通用的、高效的调度器，旨在在没有先验知识的情况下最小化程序的响应时间或端到端延迟。为了缓解程序级和调用级的队头阻塞，Autellix根据程序级统计信息（例如，总累积运行时间，§4.2.1）为调用分配优先级，并动态抢占调用（§4.2.2）。完整的调度算法如算法1所示。

1: procedure UPDATE_PROCESS_TABLE(Call c, Table pt)
2:     pd = pt[c.pid]
3:     // Total service time (PLAS), max critical path (ATLAS)
4:     pd.service = max(pd.service, c.service + c.model_time)
5:     // Update other metrics...
6:     . . .
7: end procedure
8: procedure SCHEDULER(Queues Q1,..., QK, Table pt)
9:     for c ∈ Carrived do ▷ Arriving LLM calls
10:        // Fetch priority with program ID
11:        c.service = pt[c.pid].service
12:        c.q_idx = i, s.t. Qlowi ≤ c.service ≤ Qhii
13:        Qc.q_idx.append(c), c.quanta = Qc.q_idx.quanta
14:    end for
15:    for c ∈ {Q1, Q2, ..., QK } do
16:        if c.finished() then ▷ Finished jobs update table
17:            UPDATE_PROCESS_TABLE(c, pt)
18:            Qc.q_idx.remove(c)
19:        end if
20:        if c.quanta ≤ 0 then ▷ Call demotion
21:            Qc.q_idx.remove(c), Qc.q_idx+1.append(c)
22:            c.q_idx+ = 1, c.quanta = Qc.q_idx.quanta
23:        end if
24:        wait = pt[c.pid].wait + c.wait
25:        service = pt[c.pid].service + c.model_time
26:        if wait/service ≥ β then ▷ Anti-Starvation
27:            Qc.q_idx.remove(c), Q1.append(c)
28:            // Reset waiting and model execution times
29:            c.wait = 0, c.model_time = 0
30:        end if
31:    end for
32:    Bout = [] ▷ Schedule next batch of LLM calls
33:    for c ∈ {Q1, Q2, ..., QK } do
34:        if engine.can_fit(c) then
35:            Bout .append(c)
36:        else
37:            break
38:        end if
39:    end for
40: end procedure

算法1：Autellix的调度器

4.2.1 程序级优先级划分

利用全局进程表进行优先级划分。为了有效地实现程序级优先级划分，Autellix依赖一个全局进程表来跟踪关键的程序指标，从而能够在单线程和多线程程序中做出更明智的调度决策。

进程表。受传统操作系统的启发，Autellix维护一个全局进程表，记录所有正在运行的程序的状态。当一个新程序到达时，Autellix会添加一个相应的条目；当程序完成时，该条目被移除。进程表中的每个程序条目跟踪以下指标：
* 服务时间：对于单线程程序，这是所有已完成调用在LLM引擎模型执行器上的累积执行时间。对于多线程程序，这是观察到的最长关键路径的执行时间。
* 等待时间：在LLM引擎调度器队列中花费的时间——用于反饥饿机制。
* 引擎ID(s)：程序当前正在运行的引擎——用于Autellix的负载均衡器（§ 4.3）。
* 线程元数据：每个线程对应一个活跃的LLM调用。因此，我们跟踪程序的活跃LLM调用及其各自的到达、等待和服务时间。
* 最近调用到达时间：该程序新LLM调用的最后到达时间——用于跟踪陈旧的程序。
* 最近调用完成时间：LLM调用最后完成的时间——用于检测长的外部中断。
当一个程序的LLM调用完成时，该表会相应更新。有了进程表，调度器可以推理每个程序的全局状态来调度LLM调用。

单线程程序。像最短作业优先（SJF）和最短剩余处理时间（SRPT）这样的调度策略在单服务器和多服务器环境中能最优地最小化响应时间【4，An optimized shortest job first scheduling algorithm for cpu scheduling, 2015；25，Srpt for multiserver systems, 2018】。然而，这些策略需要精确了解程序运行时间，这违反了Autellix的非预见性假设。相反，最少已达服务（Least-Attained-Service, LAS）算法【45，The foreground–background queue: A survey, 2008】在信息不可知设置中被广泛使用，例如数据中心网络【7，Information-Agnostic flow scheduling for commodity data centers, 2015；14，Efficient coflow scheduling without prior knowledge, 2015】和深度学习集群【26，Tiresias: A gpu cluster manager for distributed deep learning, 2019】，提供了一个实用的替代方案。我们引入了程序级已达服务（Program-Level Attained Service, PLAS），将LAS扩展到程序。对于一个单线程程序，其服务时间是所有先前已完成LLM调用的总运行时间。形式上，如果提交了第j个LLM调用$c_j$，其程序ID为$http://c_j.id$，PLAS会根据所有具有相同ID的先前LLM调用的运行时间$t_k$的总和，为$c_j$分配一个优先级$p(c_j)$：

这里，大的优先级值意味着较低的优先级。为了减少计算，调度器从进程表中读取程序的总服务时间（第11行）。当一个LLM调用完成时，其程序的总服务时间会被更新（第4行）。因此，PLAS自然地偏好那些总服务时间较少的程序中的调用，帮助较短的程序更早完成，从而减少响应时间。

多线程程序。与单线程程序不同，多线程程序被建模为LLM调用的动态DAG。不幸的是，程序的完成时间由DAG的关键路径——从开始到结束最长的依赖调用序列——决定，如图9所示。无论一个引擎能处理多少并行LLM调用，程序只有在关键路径上的所有调用都完成后才能终止。此外，不考虑关键路径，调度器会得到次优的程序完成时间；在图9中，DAG的完工时间从11个单位增加到14个单位。


图9：多线程程序的关键路径。（左）DAG中关键路径的示例。（右）最佳情况下的完工时间为11个单位，而最差情况下为14个单位。

ATLAS算法。为了解决这个问题，我们引入了自适应线程级已达服务（Adaptive Thread-Level Attained Service, ATLAS），这是PLAS的一个实用泛化，它根据程序关键路径上的服务时间来优先处理调用。ATLAS旨在为每个新到达的调用$c_j$分配一个优先级$p(c_j)$，该优先级基于其在同一程序中父节点$P(c_j)$的优先级和已完成的服务时间：

这里，$t_k$是父调用$c_k$的执行时间。通过递归地结合父节点的优先级和运行时间，$p(c_j)$估算了导致$c_j$的累积服务时间最长链，从而提供了一个对关键路径的非预见性估计。

ATLAS实现。然而，同时实现两个目标——偏好短程序同时又优先处理最长的关键路径线程——并非易事。为了解决这个问题，ATLAS在其进程表中为每个程序维护一个标量：观察到的最长关键路径。程序中每个活跃的LLM调用都继承这个值作为其初始优先级，并且在调用完成时，仅当其自身的关键路径更长时才更新该标量（第4行）。这个简单的机制持续地优化程序的关键路径估计，而无需跟踪LLM调用之间的依赖关系。因此，ATLAS偏好具有较短关键路径的程序和LLM调用，有效地近似了动态DAG的“最少已达服务”策略。此外，由于一个给定程序的所有调用都从同一个条目派生其优先级，调度器自然地将一个程序的并行调用分组，防止掉队线程延迟程序的完成。

4.2.2 抢占式调度

离散化优先级。Autellix根据每个LLM调用所属程序的历史为其分配优先级。然而，基于连续优先级进行调度和抢占可能会退化为最差情况下的轮询调度（round-robin）【14，Efficient coflow scheduling without prior knowledge, 2015】，其性能比FCFS更差，并会产生不必要的上下文切换，包括CPU和GPU之间频繁的KV缓存交换【77，Fast distributed inference serving for large language models, 2024】。为了避免这种情况，Autellix将优先级离散化为一组有限的队列，类似于操作系统中的多级反馈队列（MLFQ）【5，Operating systems: Three easy pieces - cpu scheduling: Multi-level feedback queue, 2018；14，Efficient coflow scheduling without prior knowledge, 2015；26，Tiresias: A gpu cluster manager for distributed deep learning, 2019】。

基于程序的多级调度。Autellix将LLM调用的优先级分箱并离散化到K个队列（$Q_1, Q_2, ..., Q_K$）中，其中优先级从$Q_1$到$Q_K$递减。每个队列$Q_i$覆盖一个优先级范围$[Q_{lo}^i, Q_{hi}^i)$，其中$Q_{lo}^1 = 0$, $Q_{hi}^K = \infty$，且$Q_{lo}^{i+1} = Q_{hi}^i$。在图10中，当一个LLM调用到达时，Autellix根据进程表查找其程序的优先级$p(c)$（①，第11行）。与传统MLFQ中新调用都从最高优先级队列$Q_1$开始不同，LLM调用根据其离散化后的优先级$p(c) \in [Q_{lo}^i, Q_{hi}^i)$被分配到第i个队列（②，第12行）。随后，调用获得该队列的时间量（quantum），并在其队列内按FCFS顺序执行（第13、35行）。一旦调用耗尽其时间量，它将被降级到更低优先级的队列（③，第20-23行）。如果调用等待时间过长，Autellix会采用反饥饿机制，如下所述（④，第24-30行）。最后，当一个调用完成解码时，它会更新进程表（第16-18行）。


图10：基于离散化优先级的LLM调用生命周期。

反饥饿机制。离散优先级或MLFQ风格的算法会导致长时、低优先级程序的饥饿问题【14，Efficient coflow scheduling without prior knowledge, 2015；26，Tiresias: A gpu cluster manager for distributed deep learning, 2019；77，Fast distributed inference serving for large language models, 2024】。简单的反饥饿技术——例如提升等待超过阈值的调用——会将Autellix退化为朴素的MLFQ，其中长程序的LLM调用（现在位于$Q_1$）会中断短程序【5，Operating systems: Three easy pieces - cpu scheduling: Multi-level feedback queue, 2018；77，Fast distributed inference serving for large language models, 2024】。因此，我们也利用进程表来衡量程序级的饥饿。具体来说，对于一个程序p，如果其总等待时间（$W_{total} = W_p + W_c$）与服务时间（$T_{total} = T_p + T_c$）的比率超过一个阈值$\beta$，Autellix会将调用c提升到$Q_1$：

改变$\beta$值可以在程序的平均响应时间和公平性之间进行权衡。提升后，只有$W_c$和$T_c$，即调用的等待和运行时间，被设置为零，以确保程序的线程（即活跃的LLM调用）很可能一起被提升（第29行）。

内存管理。通过抢占式调度，LLM引擎必须处理大量的并发LLM调用，导致频繁的GPU-CPU传输，因为KV缓存块为了服务不同的请求而被反复交换【77，Fast distributed inference serving for large language models, 2024】。先前的工作通过在处理当前LLM请求时主动为下一轮请求交换KV缓存来减轻这种交换开销【77，Fast distributed inference serving for large language models, 2024】。然而，Autellix是同步的，需要为每个调用的时间量和进程表进行实时更新。因此，Autellix采用两种关键优化来分别减少GPU-CPU交换的频率和开销。首先，Autellix通过采用多步调度（multi-step scheduling）来减少总交换次数，即每N个解码步骤运行一次调度器，而不是每一步都运行。由于一些请求可能提前完成，我们的调度器会超额配置已在GPU上的排队请求，确保当某些请求在N步之前完成时，新请求能立即被添加。其次，Autellix采用了一个更高效的GPU-CPU交换内核。我们的内核不是为每个块单独调用异步传输，而是将所有KV块收集到一个连续的缓冲区中，并在一次操作中传输它们——通过减少碎片化来增加PCIe带宽，减少每个块的开销，并降低端到端的交换延迟（§5）。

4.3 负载均衡器

多引擎部署的挑战。随着智能体工作负载的扩展，部署多个引擎副本是必要的。然而，不考虑数据局部性地分发请求会导致次优性能【66，Preble: Efficient distributed prompt scheduling for llm serving, 2024】。

数据局部性感知的负载均衡策略。我们对智能体工作负载的分析（§3.2）突显了短请求和长请求之间的关键区别。低于2048个Token的短请求由于共享通用的系统提示，在任何引擎上都能实现高缓存命中率（≥ 75%）。对这些请求强制执行数据局部性带来的增益微不足道，并且当大型并行程序主导特定引擎时，可能会导致引擎利用率倾斜。因此，简单地将短请求均衡到负载最低的引擎可以在保持性能的同时将开销降至最低。相反，较长的请求对其程序的数据局部性要敏感得多。它们与给定程序的大量前缀重叠，当持续路由到同一引擎时，能显著减少重新计算，这证明了偶尔的排队延迟是值得的。

实现方法。虽然先前的工作依赖复杂的前缀树来量化数据局部性【66，Preble: Efficient distributed prompt scheduling for llm serving, 2024】，但我们的简单方法是动态地将短请求路由到负载最低的引擎，并将较长的请求固定到其程序对应的引擎上。算法2形式化了这种方法，我们的评估表明，Autellix的负载均衡器在异构工作负载下改善了吞吐量和延迟（§6）。

Algorithm 2 Autellix’s Load Balancer
1: procedure LOAD_BALANCER(Call c, Table pt, List Engines)
2:     if LEN(c.tokens) ≤ 2048 then ▷ Small request
3:         assigned_engine = LEAST_USED(Engines)
4:     else
5:         if c.pid ∈ pt then ▷ Program already assigned to engine
6:             assigned_engine = pt[c.pid]
7:         else
8:             // Select the least utilized engine
9:             assigned_engine = LEAST_USED(Engines)
10:            pt[c.pid] = assigned_engine
11:        end if
12:    end if
13:    return assigned_engine
14: end procedure
15: procedure LEAST_USED(List Engines)
16:    // Query engine workloads in parallel
17:    workloads = QUERY_ENGINE_WORKLOADS(Engines)
18:    least_used_engine = ARGMIN(workloads)
19:    return least_used_engine
20: end procedure

算法2：Autellix的负载均衡器

5 实现

系统概览。Autellix是一个多引擎LLM推理服务系统，包括一个前端、调度器和负载均衡器——总计5000行Python和CUDA/C++代码。

前端。Autellix的前端扩展了OpenAI的Chat Completion API【49，Chat Completions API, 2024】和vLLM的Python API【36，Efficient memory management for large language model serving with pagedattention, 2023】，提供了一个对开发者来说看似无状态的有状态接口。用户只需在他们的Python应用程序中导入Autellix的库，程序初始化时，Autellix会自动向后端发出一个start_session请求。此操作返回一个唯一的会话标识符，并在进程表中创建一个相应的条目。随后的LLM调用会被透明地标注上正确的会话、程序和线程ID，然后分派到后端。当程序完成或遇到错误时，Autellix调用end_session，从进程表中移除相关条目。作为一个研究原型，当前的前端缺乏防止用户修改底层包的保护措施；解决此限制是未来的工作。

LLM引擎。Autellix基于vLLM v0.6.1【36，Efficient memory management for large language model serving with pagedattention, 2023】构建。为了将更改局部化，我们仅修改了调度器，集成了新的策略（PLAS, ATLAS, 和 MLFQ）和高效的内存交换内核。这确保了实验的直接性和性能增益的清晰归因。调度器遵循前一节（§4）描述的算法。我们还注意到，在vLLM中，每个键值（KV）块都通过cudaMemcpyAsync单独传输，这会产生小的碎片化传输，导致PCIe带宽利用率不足，并产生高昂的开销，如重复的DMA设置。为了解决这个问题，我们分配了一个主机缓冲区，并将所有KV块合并成一个连续的块，从而实现一次批量传输。结果将在下一节（§6）中展示。

多引擎。vLLM目前缺乏同时管理多个LLM引擎的能力。为了更好地评估我们的负载均衡策略，我们在AsyncLLMEngine之上构建了AsyncMultiLLMEngine。每个LLM引擎副本运行在一个专用的Python进程中，一个协调的元引擎通过标准的进程间通信（IPC）原语（如mp.Queue和mp.Pipe）管理这些副本。当元引擎收到一个请求时，它会将请求分配给适当的副本，并向前端返回一个类似future的对象，而不会阻塞。被选中的引擎进程异步执行任务，并通过IPC通道将完成的结果发送回来。收到结果后，元引擎解析future并将输出提供给前端。这种设计允许多个请求并行处理，元引擎作为一个非阻塞的协调器，处理路由、资源分配和结果收集。

A4 实验环境

工作负载

我们的真实世界实验在四个代表性的智能体工作负载上评估了Autellix，这些工作负载在解码Token数、预填充Token数和LLM调用次数上差异很大（图11）。

  • 聊天机器人智能体：ShareGPT [1]：ShareGPT数据集包含用户生成的对话输入和输出，是聊天机器人应用的典型代表。LLM调用次数遵循长尾分布，平均为6.66次，最多为80次（图11d）。ShareGPT的对话性质体现在其重解码的调用上，平均解码Token为277个，而预填充Token为256个，即短提示生成详细响应（图11a）。我们的实验将整个对话作为程序重放，而不是仅第一轮。
  • ReAct智能体：BFCL [79]：伯克利函数调用排行榜（BFCLv3）评估LLM在多轮、多步工具使用任务上的表现。与ShareGPT相比，BFCL的LLM调用长尾效应较弱，平均每个程序10.75次调用，最多70次（图11d）。BFCL是预填充密集型的，由于长的系统提示和详细的工具签名，每次调用平均有735.06个Token，而解码很短，平均为34.14个Token（图11b）。因此，BFCL封装了在重预填充阶段和短解码与函数调用之间交替的动态工作流。
  • 蒙特卡洛树搜索：LATS [91]：LATS工作负载源于在HotpotQA【82，Hotpotqa: A dataset for diverse, explainable multi-hop question answering, 2018】上运行MCTS，计算密集且涉及大量并行LLM调用。每个程序实例平均包含159.7次LLM调用，比ShareGPT或BFCL工作负载高一个数量级（图11d）。此外，每次调用的预填充和解码阶段平均分别为467.2和72.6个Token（图11c）。这些分布突显了MCTS固有的迭代、并行特性，推动LLM服务系统高效处理大量并发调用。
  • 混合负载：我们结合了所有三种工作负载，从每种负载中等量采样以确保多样性。该工作负载旨在对Autellix在不同程序类别下的性能进行压力测试。


图11：工作负载分析。每个工作负载中程序的LLM调用统计。(a) ShareGPT, (b) BFCL, 和 (c) LATS的输入和输出长度分布。(d) 绘制了每个工作负载中LLM调用数量的分布。

实验设置

  • 模型与硬件平台：

    • 模型：LLaMA-3.1-8B, 70B 和 Falcon-180B，分别在1、4和8个GPU上运行。
    • 硬件：实验在GCP Compute Engine的a2-ultragpu-8g实例上进行，该实例配备8个通过NVLink连接的A100-SXM4-80GB GPU，1360 GB主机内存，PCIe-4.0×16，以及2 TB磁盘空间。

  • 软件配置与基线：

    • 软件：Autellix基于vLLM v0.6.1实现，使用Python和CUDA/C++。
    • 基线系统：
      1. vLLM [36]：最先进的高吞吐量LLM服务系统，使用连续批处理和PagedAttention。其默认调度策略为FCFS。
      2. vLLM-opt：vLLM的优化版本，启用了分块预填充（chunk-prefill）、前缀缓存（prefix-caching）和多步调度。其性能接近SGLang和TensorRT。
      3. MLFQ：在vLLM-opt之上实现了基于多级反馈队列的抢占式调度算法。

  • 评估指标：

    • 程序级Token延迟：定义为总程序响应时间除以生成的Token总数。该指标衡量了整个程序的端到端性能，而非单个请求的性能。为简洁起见，后文简称为“延迟”。

A4 实验结果

端到端单引擎性能

平均延迟与吞吐量：如图12所示，在ShareGPT、BFCL、LATS和混合四种工作负载上，Autellix在相同的Token延迟下始终实现了最高的吞吐量。vLLM由于缺乏前缀缓存，导致对同一程序内LLM调用的累积状态进行昂贵的重计算，因此性能最差。vLLM-opt、MLFQ和Autellix之间的相对性能因工作负载而