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

§1 TL;DR #

现有LLM serving引擎将agentic program的每次LLM call视为独立请求调度，导致program-level head-of-line blocking。Autellix将OS的Least Attained Service调度提升到program级别（PLAS/ATLAS），按program累计服务时间排优先级，配合anti-starvation和locality-aware load balancing，在相同延迟下实现4-15×吞吐提升。

Agent scope #

• Task class: 通用agent serving基础设施——覆盖single-turn chatbot、multi-step ReAct、parallel Map-Reduce、tree-search MCTS等所有DAG模式的agentic program。不限定具体task domain。
• Interaction pattern: 多轮sequential（chatbot/ReAct）和高并行multi-threaded（MCTS数十到数百并行线程）混合。Program结构仅在运行时逐步揭露。
• Autonomy: Autellix本身是serving层，不参与agent决策。所服务program从human-in-the-loop（chatbot）到fully autonomous（MCTS search）全覆盖。系统对program结构zero knowledge——non-clairvoyant设计。

§2 Q1 痛点 / Q2 方法 / Q3 结果 #

Q1 痛点 #

现有LLM serving系统（vLLM、SGLang）将每次LLM call视为独立请求调度，完全忽略同一agentic program内call之间的依赖和program-level统计。这导致两层HoL blocking：

1. Call-level HoL blocking：长decode call阻塞短call——已知问题，MLFQ preemption可缓解。
2. Program-level HoL blocking：更隐蔽且更致命。长program（如100-call MCTS）每完成一个call就提交新call，新call在MLFQ中被放入最高优先级队列，反复挤占短program（如2-call chatbot）。实测中MLFQ在program级别的表现 ≈ FCFS甚至更差。



Paper's Figure 5 (caption: "Program execution and wait times, over different programs and system loads. With moderate loads, programs spend the most time waiting.").

Fig. 5展示了在Chatbot、ReAct、MCTS三类workload下，wait time随负载增加迅速主导program总延迟。中等负载下program等待时间已超过执行时间数倍。减少wait time既降低延迟，又通过加速program完成提高后续call的到达率，形成正反馈循环提升GPU utilization。

Q2 方法 #

Problem formulation. 给定 $N$ 个program以未知模式到达serving系统，每个program $i$ 是一个动态DAG，由LLM call和external interrupt（tool call/human input）交替组成。DAG结构仅在运行时逐步揭露（non-clairvoyant）。目标：

$$\min \frac{1}{N}\sum_{i=1}^{N} W_i$$

其中 $W_i$ 是program $i$ 所有LLM call的累计等待时间。同时追求GPU利用率最大化和公平性（p95/p99延迟可控）。

核心机制：将Least Attained Service (LAS) 从per-request提升到per-program。新call的初始优先级继承program已消耗的累计服务时间，而非从最高优先级开始。

Aspect	Before: LAS/MLFQ per-request	After: PLAS/ATLAS per-program
Priority unit	单个LLM call	Program（所有call共享state）
新call初始队列	最高优先级 $Q_1$	按program累计service分配
Service metric	本call已用时间	PLAS: $\sum t_k$; ATLAS: $\max s_i$
跨call状态	无	Global process table

PLAS（单线程program）：

$$p(c_j) = \sum_{k < j,\; c_k.\text{id} = c_j.\text{id}} t_k$$

物理意义：program消耗的总服务越少，优先级越高——偏好短/新program。在DHR分布（Pareto/log-normal）下，LAS最小化mean response time。

ATLAS（多线程program）：

$$p(c_j) = \max_{T_i \in \text{program}(c_j)} s_i$$

物理意义：以critical path（最长线程）的累计服务作为program优先级。用max而非sum避免高并行度program（MCTS数十线程）的priority被过度膨胀。同时在program内部优先调度critical path上的call以缩短makespan。

Anti-starvation：当program的wait/service ratio超过阈值 $\beta$，call被提升到 $Q_1$：

$$\frac{W_{\text{total}}}{S_{\text{total}}} \geq \beta \implies \text{promote to } Q_1$$

Promote后reset wait和service，防止oscillation。

核心技术壁垒：将LAS从单请求扩展到program级需要两个非trivial insight的组合：(1) 新call必须继承program累计service而非从零开始——打破传统MLFQ的基本假设（新请求享受最高优先级）；(2) 多线程program的priority必须用critical-path max而非sum——sum会使MCTS等高并行program被过度惩罚。这两个选择的正确组合使ATLAS在MCTS上获得15×吞吐提升，而naive扩展无法达到。

Q3 结果 #

• Single-engine throughput：相同median latency下 Autellix vs vLLM FCFS = 4-15×（Chatbot ~4×, ReAct ~4-5×, MapReduce ~6×, MCTS ~15×）
• Multi-engine throughput：locality-aware load balancer vs round-robin = up to 1.5×
• KV-cache swap优化：batched transfer减少18× swap operations, 3-7× swap time, ~1.3× throughput
• Tail latency：anti-starvation机制使p95/p99可控，无starvation
• ATLAS vs PLAS：在MapReduce和MCTS上ATLAS优于PLAS，验证critical-path设计

---

§3 架构 / 方法图 #



Paper's Figure 8 (caption: "Autellix's system architecture. Users run their programs locally, which initiates a stateful session and submits LLM calls to Autellix's backend. Autellix leverages a global process table to track sessions and better inform its custom load-balancer and scheduler.").

Autellix在vLLM之上增加一层program-aware serving层。用户端program通过stateful session API与后端通信，每个session对应一个program在global process table中的entry。Backend包含两个核心组件：(1) Load balancer根据input length将call路由到合适engine（长call → program's primary engine保持KV-cache locality，短call → least-loaded engine均衡负载）；(2) 每个engine内的scheduler使用MLFQ + program-level priority调度。



Paper's Figure 1 (caption: "Execution workflows for Agentic Programs. Agentic programs are highly dynamic execution workflows that follow a directed acyclic graph (DAG). It consists of LLM calls from one or more LLM agents and external interrupts (i.e. tool calls, humans).").

Fig. 1展示了四类代表性program的DAG结构：(a) Chatbot为线性链，(b) ReAct在LLM call和tool call之间交替，(c) Map-Reduce在某步fork出并行线程后join，(d) MCTS形成树状结构（expand/evaluate/backpropagate）。DAG的dynamic和non-deterministic特性使scheduling必须是non-clairvoyant的。

Agent loop — 请求生命周期 #

sequenceDiagram participant P as Agentic Program participant A as Autellix Backend participant PT as Process Table participant LB as Load Balancer participant E as vLLM Engine(s) P->>A: establish_session(program_id) A->>PT: create entry (service=0, wait=0) loop Each LLM call in program DAG P->>A: llm_call(session_id, prompt) A->>PT: lookup program cumulative service A->>LB: route(long→primary engine, short→least-loaded) LB->>E: enqueue with priority = f(program_service) Note over E: MLFQ demotion within engine Note over E: Anti-starvation: wait/service ≥ β → promote E-->>A: response tokens A->>PT: service ← max(service, thread_service + model_time) A-->>P: return response opt External interrupt P->>P: tool call / human input (outside Autellix) end end P->>A: end_session A->>PT: remove entry

Planning & reasoning（被服务的program侧） #

Autellix本身不执行planning——它是serving基础设施。但其调度算法的设计充分考虑了不同planning模式产生的serving压力特征：

• ReAct (think-then-act loop)：单线程sequential call链，call长度高度可变。PLAS通过累计service自动将长conversation deprioritize。
• MCTS (tree search)：最高并行度，单engine仅能处理 ~0.2 programs/sec。ATLAS通过critical-path max精确追踪program进度，避免对并行线程数的惩罚。
• Map-Reduce：fork-join模式，critical path取决于最慢线程。ATLAS优先调度critical path上的call减少idle等待。

Autellix不限制program的decomposition方式、搜索深度、backtracking策略——这些均由program层（LangChain/AutoGen等）决定。



Paper's Figure 9 (caption: "Critical path for multi-threaded programs. (Left) Example of a critical path through a DAG. (Right) Best-case scenario makespan, 14 units, is achieved by prioritizing calls on the critical path.").

Fig. 9说明ATLAS的critical-path逻辑。多线程program的makespan取决于最长线程。ATLAS通过 $\max s_i$ 识别critical path，在program内部优先调度该path上的call。右图对比：critical-path-aware调度达到最优makespan 14 units，而非critical-path-aware调度的makespan更长。

---

§4 作者证明 #

Notation table #

Symbol	Meaning
$c_j$	第 $j$ 个到达的LLM call
$c_j.\text{id}$ / $c_j.\text{pid}$	Call所属program的ID
$t_k$	已完成call $c_k$ 的执行时间
$p(c_j)$	Call的优先级（值越小优先级越高）
$T_i$	多线程program中第 $i$ 个线程
$s_i$	线程 $T_i$ 的累计服务时间 $= \sum_{c_k \in T_i} t_k$
$Q_1, \ldots, Q_K$	MLFQ的 $K$ 个优先级队列，$Q_1$ 最高
$\beta$	Anti-starvation阈值（wait/service ratio）
$W_i$	Program $i$ 所有call的累计等待时间

方程物理意义 #

PLAS priority: $p(c_j) = \sum_{k < j,\; c_k.\text{id} = c_j.\text{id}} t_k$

累计已消耗服务越多优先级越低。借鉴OS的LAS调度，但作用域从单个job扩展到program（多个sequential calls）。在DHR分布下LAS最小化mean response time（Rai et al. 2003）。

ATLAS priority: $p(c_j) = \max_{T_i \in \text{program}(c_j)} s_i$

用program中最长线程的累计服务作为优先级。Max准确捕捉program进度——critical path决定completion time；sum会使高并行program被过度惩罚。

Process table update: $\text{pd.service} \leftarrow \max(\text{pd.service},\; c.\text{service} + c.\text{model\_time})$

对单线程退化为简单累加；对多线程取max追踪critical path。

Anti-starvation condition: $W_{\text{total}} / S_{\text{total}} \geq \beta \implies \text{promote to } Q_1$

其中 $W_{\text{total}} = \text{pt}[c.\text{pid}].\text{wait} + c.\text{wait}$，$S_{\text{total}} = \text{pt}[c.\text{pid}].\text{service} + c.\text{model\_time}$。Promote后reset wait和service——不reset则service归零后立即再次被promote → oscillation。

6 base checks #

1. PLAS定义一致性：§4.2.1定义的 $p(c_j)$ 与Algorithm 1中queue assignment一致——新call被放入对应program累计service的queue，而非 $Q_1$。✓
2. ATLAS max vs sum：§4.2.1说明用max（critical path），Algorithm 1 line 4中 pd.service = max(...) 确认。✓
3. Anti-starvation不破坏correctness：promote后reset service/wait（Algorithm 1 lines 29-30），避免永久高优先级。✓
4. MLFQ demotion与program priority正交：call在queue内按quantum demotion处理call-level HoL，跨queue的初始assignment处理program-level HoL——两层机制互不干扰。✓
5. Load balancer threshold无循环依赖：input token count是call自身属性，不依赖scheduler状态。✓
6. Non-clairvoyant假设一致性：所有scheduling决策仅依赖已完成call的runtime（past），不使用future预测。✓

Agent-specific checks #

1. Success-rate model：论文不测量task success rate（如SWE-bench resolve rate），仅测量serving层指标（throughput/latency）。Autellix作为serving基础设施不改变program的output质量，仅改变完成速度——scope界定合理。但无法排除极端preemption导致cache eviction进而影响output的edge case。
2. Latency budget per turn：Fig. 5提供wait time vs execution time vs interrupt time分解。Wait time在中等负载下主导（>50% of total）。Per-turn absolute latency未给出，通过throughput-latency Pareto curves间接展示。论文未声称"interactive latency"。
3. Failure mode classification：识别三类failure mode——(a) call-level HoL blocking（已知，MLFQ解）, (b) program-level HoL blocking（本文发现，PLAS/ATLAS解）, (c) long-program starvation（anti-starvation机制解）。方法精确针对(b)，(a)(c)作为辅助机制覆盖。
4. 无形式化作者证明 — 仅实证。LAS在DHR分布下的optimality是已知结果；program-level LAS的formal competitive ratio未证明。可被bounded的metric：在特定分布假设下program-level mean response time的competitive ratio相对于clairvoyant SRPT。

理论连接 #

Autellix不证明新的optimality theorem。理论基础来自已知结果：

• Rai et al. (2003): LAS在DHR分布下non-clairvoyant optimal for mean response time。
• Kim et al. (HPCA 2010, ATLAS): per-thread attained service用于DRAM scheduling——ATLAS命名和max-across-threads思路直接受此启发。

期望但缺失的理论保证：(1) program-level LAS跨sequential calls的formal optimality条件——当call数量也服从DHR时是否仍optimal？(2) ATLAS在DAG调度下的competitive ratio vs SRPT。Fig. 18的simulation对比量化了non-clairvoyance的代价。

---

§5 实验与数据 #

实验设置 #

• Hardware：NVIDIA A100-80GB GPU
• Models：LLaMA-3.1-8B（单卡），LLaMA-3.1-70B（多卡tensor parallel）
• Baselines：vLLM FCFS, vLLM + MLFQ (FastServe-style), round-robin load balancer
• Workloads：Chatbot（多轮对话）, ReAct（tool call交替）, Map-Reduce（fork-join）, MCTS（树搜索）
• Metrics：program-level throughput, end-to-end latency (median/p95/p99), wait time breakdown

HoL blocking实证 #



Paper's Figure 6 (caption: "Ratio of Waiting to Execution Time for LLM Calls and Programs. Head-of-line blocking occurs when short LLM calls and programs wait significantly longer than their execution times.").

Fig. 6是论文最重要的diagnostic figure。横轴按decode steps（call级）或LLM call数（program级）分组，纵轴是wait/exec ratio。关键观察：(a)(c) MLFQ在call级改善了HoL（短call ratio下降），但 (b)(d) 在program级MLFQ ≈ FCFS甚至更差——短program仍被长program的高优先级新call阻塞。这直接证明了program-level scheduling的必要性。

Data locality #



Paper's Figure 7 (caption: "Prefix cache hit rates for LLM calls within and across programs. LLM calls within the same program often share KV cache, whereas LLM calls across programs typically do not.").

Intra-program cache hit rate在各input length下均 >90%，inter-program hit rate随input length指数衰减。这验证了load balancer设计的前提：长call应路由到primary engine（高cache reuse），短call可分散（仅system prompt，routing不敏感）。

主要吞吐结果 #



Paper's Figure 12: single-engine throughput-latency Pareto curves — Autellix (PLAS/ATLAS) vs vLLM (FCFS) vs MLFQ across Chatbot and ReAct workloads on LLaMA-3.1-8B, A100-80GB.

Fig. 12展示了单engine下Chatbot和ReAct的throughput-latency Pareto curves。Autellix的Pareto frontier在所有latency target下显著优于FCFS和MLFQ。MLFQ因program-level blocking几乎无法改善甚至劣于FCFS。



Paper's Figure 13: single-engine throughput-latency curves for MCTS and Map-Reduce workloads, showing 10-15× improvement for MCTS.

Fig. 13展示了MCTS和Map-Reduce的结果。MCTS获得最大提升（~15×），因为单engine仅能处理 ~0.2 programs/sec，program-level blocking极其严重，每个program含数十到数百个call。

Workload	Autellix vs FCFS	Autellix vs MLFQ	ATLAS vs PLAS
Chatbot	~4×	~4×	N/A (single-threaded)
ReAct	~4-5×	~4-5×	N/A (single-threaded)
Map-Reduce	~6×	~6×	ATLAS > PLAS
MCTS	~15×	~15×	ATLAS > PLAS

Comparison to optimal policy #



Paper's Figure 18 (caption: "Comparison to optimal scheduling policy. In simulation, Autellix outperforms other scheduling policies; however, there remains a visible gap relative to the optimal policy (SRPT).").

Fig. 18在simulation中对比Autellix与clairvoyant最优策略SRPT。Autellix优于所有non-clairvoyant baseline，但与SRPT存在明显gap——量化了non-clairvoyance的fundamental cost，指明进一步优化方向（如partial workload prediction）。

Steady-state与ablation #



Paper's Figure 4 (caption: "Number of LLM calls in serving engine during steady state over 1 hour. Optimizing programs' wait times increases the volume of LLM calls at steady state.").

Fig. 4展示正反馈效应：减少wait time → program更快完成 → 后续call更早提交 → 稳态下GPU同时处理的call数增加 ~10个。Program-level scheduling不仅改善延迟，还通过提高到达率提升GPU utilization。

KV-cache swap：preemptive scheduling增加swap频率，Autellix通过batching parallel block transfers减少18× swap operations, 3-7× swap time, ~1.3× throughput。使preemption实际可行。

Anti-starvation $\beta$：$\beta$ 过低 → 频繁promote → 退化为FCFS；过高 → 长program饿死。有效范围：wait/service ratio 3-7。

MLFQ队列数 $K$：更多queue提供更细粒度preemption，$K = 8\text{-}16$ 后收益递减。

Tool & environment interface #

Autellix作为serving中间层的接口设计：

• API形式：Stateful session API。与OpenAI stateless API不同，program先建立session获得session_id，后续LLM call附带session_id提交。与LangChain/AutoGen等框架compatible——替换endpoint + 添加session lifecycle即可。
• Side effects：Autellix是read-only中间层——不修改program逻辑，不拦截tool call。Tool call在program端直接执行，结果作为下一次LLM call的input提交。
• Error surface：scheduling/routing failure对program透明——失败call按OpenAI error convention返回。Engine-level error（OOM, CUDA error）由vLLM处理。
• Environment contract：stateful（session间保持process table entry）但non-deterministic（scheduling依赖concurrent workload）。Engine间无shared state，靠routing维持locality。

---

§6 论证链 #

Step	Claim	Evidence	强度
1	Agentic program延迟由wait time主导	Fig. 5: 中等负载下wait >> exec across all workloads	强——直接测量，三类workload一致
2	Wait time根源是双层HoL blocking（call-level + program-level）	Fig. 6: MLFQ解决call-level但program-level不变/更差	强——MLFQ反而更差是convincing counterexample
3	按program累计service排优先级可消除program-level blocking	PLAS/ATLAS定义 + LAS在DHR分布下的已知optimality	中——理论依赖分布假设（paper未验证workload是否DHR）
4	ATLAS的critical-path max优于naive sum用于多线程program	Fig. 9 example + ATLAS vs PLAS ablation on MapReduce/MCTS	中——ablation有力但缺formal competitive analysis
5	综合系统实现4-15× throughput at same latency	§6全套实验：4 workloads × 2 models × single/multi-engine	强——多维度一致性高，MCTS 15×尤为显著
6	Intra-program KV-cache locality支持locality-aware routing	Fig. 7: intra >90% vs inter指数衰减 + multi-engine 1.5×	中——1.5× multi-engine gain相对modest
7	Non-clairvoyant scheduling仍有提升空间	Fig. 18: Autellix vs SRPT存在visible gap	信息——定量了upper bound，指明future work

---

§7 实现 cross-reference #

代码开源状态：论文未提供public repository。[实现未公开]

关键实现细节：

1. 新call的MLFQ queue assignment（Algorithm 1核心修改）：传统MLFQ将新请求放入 $Q_1$，Autellix根据process table中program的累计service time决定初始queue。这一改动是program-level scheduling生效的关键——没有它，长program的新call仍享受最高优先级。vLLM的scheduler代码（vllm/core/scheduler.py）是最接近的实现base。
1. Batched KV-cache block transfer：vLLM默认逐block swap，preemptive scheduling下频繁swap成为bottleneck。Autellix将同一call的多个KV block打包为单次PCIe transfer，减少18× operations——使preemption实际可行的实现前提。

核心技术壁垒（详述）：co-design scheduler与program-level metadata tracking。Process table必须在call completion时同步更新（Algorithm 1 line 4），且update必须用max（for ATLAS）而非sum——错误的聚合函数导致高并行program被过度惩罚。Anti-starvation的reset逻辑也是subtle：不reset则service归零 → 再次promote → oscillation。这些设计选择的组合空间大，正确组合是核心贡献。

LLM backbone requirements #

• Model-agnostic：Autellix在serving层工作，不依赖特定模型能力。已验证LLaMA-3.1-8B和70B，设计上对任何decoder-only LLM适用。
• 无特殊能力要求：不要求long-context、tool-call format、structured output——这些由program层负责。
• Serving cost：MCTS workload下单A100-80GB engine ~0.2 programs/sec。以每MCTS program ~100 calls × ~1K output tokens估算，需5 engines处理1 program/sec。Multi-engine routing可近线性扩展（with locality benefit up to 1.5×）。
• Backbone sensitivity：scheduling策略不依赖model特性——PLAS/ATLAS仅依赖call runtime统计。绝对throughput随model大小变化（8B vs 70B需要不同engine数量）。

---

§8 Evaluation #

Benchmarks #

论文使用自构建synthetic workloads基于real trace distributions，而非标准agent benchmarks：

• Chatbot: 基于ShareGPT / LMSYS-Chat-1M数据集的多轮对话分布
• ReAct: 单线程agent with tool call interrupts
• Map-Reduce: parallel fork-join pattern
• MCTS: 基于LATS-style tree search

未使用SWE-bench / WebArena / AgentBench / τ-bench等task-level benchmarks。这是合理的scope界定——Autellix的贡献在serving throughput而非task success rate——但无法验证scheduling优化是否在极端条件下影响agent task quality。

Metrics #

• Primary: program-level throughput（programs completed per unit time at target latency）
• Secondary: end-to-end latency distribution (median/p95/p99)
• Diagnostic: wait time breakdown, cache hit rates, swap overhead
• Not measured: task success rate (pass@1/pass@k), cost per task, output quality

Baselines #

• vLLM FCFS (default scheduler)
• vLLM + MLFQ (FastServe-style preemption, per-request)
• Round-robin load balancer (multi-engine)
• SRPT (optimal clairvoyant, simulation only)

缺失baseline：SGLang——尽管反复引用为predecessor（有prefix caching和program-level constructs），未直接对比。SGLang的RadixAttention tree-based caching与Autellix的session-based routing可能有interesting交互。

Task difficulty distribution #

Workload分布为long-tailed（Fig. 11）：decode steps per call和calls per program均服从heavy-tail分布。这是HoL blocking严重的根本原因，也是LAS-based scheduling理论适用的前提条件（DHR分布）。但论文未formal地验证workload分布是否满足DHR。

---

§9 Multi-agent & Production readiness #

Multi-agent #

Autellix的multi-threaded program支持自然覆盖multi-agent场景：

• Topology: 评估了hierarchical（MCTS: expand → evaluate → backpropagate）和fan-out/fan-in（Map-Reduce）。通过DAG IR支持任意topology。
• Coordination: 同一program内的多个thread（agents）共享session和process table entry，通过scheduling隐式协调。无显式message passing。
• Role specialization: Autellix不区分agent角色——所有thread的LLM call统一调度。不同角色使用不同LLM model的场景（如planner用大模型、executor用小模型）提及为future work。
• Failure isolation: thread-level failure不影响其他thread的scheduling——process table仅追踪completed calls，某thread crash不污染其他thread的priority。

Production readiness #

• Sandboxing: Autellix不执行tool call或code——所有side-effect execution在用户端program内完成。LLM engine isolation依赖vLLM existing机制。Multi-engine部署中engine间无shared memory，单engine crash不影响其他engine。
• Observability: process table提供per-program实时可观测性（cumulative service、waiting time、active threads）。Stateful session API天然支持trace logging——每次call附带session_id可重建program timeline。
• Non-deterministic replay: scheduling依赖runtime statistics和concurrent workload，相同program在不同load下获得不同优先级。
• Deployment: vLLM之上的additional layer，需modified vLLM scheduler集成。Client-side需session management（替换endpoint + 添加session lifecycle），与LangChain/AutoGen compatible。
• Cost controls: anti-starvation threshold $\beta$ 是关键tuning parameter。无per-program token budget或rate limiting机制——依赖program层自行控制。