Source-linked AI summary
Autellix: An Efficient Serving Engine for LLM Agents as General Programs
Michael Luo, Xiaoxiang Shi, Colin Cai, Tianjun Zhang, Justin Wong, Yichuan Wang, Chi Wang, Yanping Huang, Zhifeng Chen, Joseph E. Gonzalez, Ion Stoica
TL;DR
Existing LLM serving systems overlook dependencies and program-level context in dynamic agentic workloads, contributing to call- and program-level head-of-line blocking. Autellix treats programs as first-class entities, using program-level scheduling and locality-aware distributed serving. It reports 4×–15× higher program throughput at the same latency than systems such as vLLM.
Problem
Existing LLM schedulers ignore dependencies between calls and program-level statistics, while dynamic agentic workloads experience call-level and program-level head-of-line blocking.
Method
Autellix uses cumulative program-level service statistics to schedule single-threaded and multi-threaded programs and routes calls across engines with locality awareness.
Results
4×–15× higher program throughput at the same latency than state-of-the-art systems such as vLLM is reported across diverse LLMs and agentic workloads.
Takeaways & Limitations
Treating programs rather than individual calls as the serving unit reduces waiting and improves end-to-end response times and throughput.
Takeaways & Limitations
Autellix dynamically constructs execution graphs at runtime and defers branch prediction and speculative execution based on anticipated next steps to future work.
Abstract
from arXiv · showhide
Large language model (LLM) applications are evolving beyond simple chatbots into dynamic, general-purpose agentic programs, which scale LLM calls and output tokens to help AI agents reason, explore, and solve complex tasks. However, existing LLM serving systems ignore dependencies between programs and calls, missing significant opportunities for optimization. Our analysis reveals that programs submitted to LLM serving engines experience long cumulative wait times, primarily due to head-of-line blocking at both the individual LLM request and the program. To address this, we introduce Autellix, an LLM serving system that treats programs as first-class citizens to minimize their end-to-end latencies. Autellix intercepts LLM calls submitted by programs, enriching schedulers with program-level context. We propose two scheduling algorithms-for single-threaded and distributed programs-that preempt and prioritize LLM calls based on their programs' previously completed calls. Our evaluation demonstrates that across diverse LLMs and agentic workloads, Autellix improves throughput of programs by 4-15x at the same latency compared to state-of-the-art systems, such as vLLM.
1 Introduction
Agentic programs are dynamic DAG-based workflows whose growing numbers of LLM calls expose program-level blocking that call-centric serving systems do not address. Autellix schedules calls using program-level execution history and reports substantially higher throughput.
- Agentic programs scale LLM calls and output tokens to improve reasoning, planning, search, reflection, collaboration, and tool-based task solving.
- Agentic programs are dynamic DAGs of LLM calls and external interrupts, with invocation patterns emerging only at runtime.
- 18 units of waiting arise under both FCFS and MLFQ in the illustrated workload, while PLAS reduces waiting to 12 units by prioritizing shorter programs.
- Existing serving engines optimize individual calls but ignore dependencies and program-level statistics, producing suboptimal end-to-end performance for complex programs.
- Autellix prioritizes calls by their programs’ previously completed execution time, deprioritizing long programs so shorter programs can complete first.
- 4-15x higher throughput than vLLM is reported across different LLMs and four representative agentic workloads.
2 Background & Related Work
LLM serving systems execute and route calls for agentic programs, while agentic applications orchestrate agents, tools, humans, and increasingly parallel or search-based inference workflows. These workloads vary dynamically and can increase call volume and waiting pressure.
- LLM Serving Layer: LLM serving systems route calls across engines and execute them within engines using cache, memory, kernel, and scheduling optimizations.
- Agentic Layer: Agentic programs orchestrate interactions among agents, tools, and humans, with external interrupts enabling control over databases, robots, and the internet.
- Agentic Applications: Agentic applications automate complex tasks such as web navigation, issue resolution, mathematical problem solving, fact-checking, and robotic control.
- Agentic Applications: Inference-time techniques increase the number of LLM calls and decode tokens, including parallel planning, self-reflection, best-of-N sampling, beam search, and lookahead.
- System Behavior: Across workloads, most program time is spent waiting as load increases, and the waiting duration depends on the workload.
3 Motivation
Agentic programs spend much of their end-to-end time waiting, while existing call-level schedulers miss program dependencies and data locality. Autellix addresses these bottlenecks by reducing wait times, using program-level scheduling context, and exploiting shared KV cache.
- Waiting-time motivation: As load increases, most agentic-program time is spent waiting across chatbot, ReAct, and MCTS workloads.Autellix therefore targets program-level waiting time as a primary optimization objective.
- Waiting-time motivation: 10 additional concurrent LLM calls are handled by Autellix compared with vLLM’s FCFS policy in a one-hour LLaMA-3.1-8B chatbot trace.The additional concurrency creates more batching opportunities and improves throughput.
- Call-level blocking: Long-decoding LLM calls cause call-level head-of-line blocking because vLLM waits for ongoing calls to finish before scheduling new ones.MLFQ reduces waiting-to-execution ratios for short decodes, but preemption alone does not fully address program-level blocking.
- Program-level blocking: Short programs experience high waiting-to-execution ratios under FCFS and MLFQ when program-level context is absent.MLFQ can prioritize new calls from long programs, starving shorter programs despite being preemptive.
- Data locality: Within a program, KV-cache hit rates remain above 90%, while across programs they decay exponentially with input length.The contrast indicates strong within-program data locality and limited sharing beyond common system prompts.
- Autellix’s approach: Autellix prioritizes LLM calls using program-level execution statistics, allowing shorter programs to complete before longer programs’ subsequent calls.Its architecture tracks stateful sessions in a global process table to inform load balancing and scheduling.
4 Autellix Design
Autellix treats agentic programs as first-class serving units, using program-aware scheduling and data-locality-aware routing to reduce end-to-end latency and blocking. PLAS and ATLAS prioritize calls using accumulated service and critical-path information without prior workload knowledge.
- 4.1 Overview: Autellix combines a program-aware scheduler with a data locality–aware load balancer for agentic programs.The architecture targets program end-to-end latency, GPU utilization, and starvation mitigation.
- 4.1 Overview: Autellix is non-clairvoyant: it dynamically constructs each program’s execution representation as the workflow runs.The system assumes no prior knowledge of arrivals, workflow structure, or workload distributions.
- 4.2.1 Program-level Prioritization: PLAS prioritizes single-threaded calls using each program’s cumulative execution time from previously completed calls.Higher attained service means lower priority, favoring programs that have received less service.
- 4.2.1 Program-level Prioritization: Ignoring critical paths increases the DAG makespan from 11 to 14 units.ATLAS maintains the longest observed critical path so parallel stragglers do not delay program completion.
- 4.2.1 Program-level Prioritization: ATLAS prioritizes multi-threaded calls using recursively accumulated service along parent dependencies to estimate each program’s critical path.The approach addresses dynamic DAGs whose completion time is determined by the longest dependent call chain.
- 4.3 Load Balancer: Autellix routes short calls to the least-loaded engine and pins longer calls to their program’s engine.This balances load while preserving prefix and conversation-state locality for longer requests.
5 Implementation
The prototype extends vLLM with a stateful frontend, modified scheduler, and multi-engine coordination layer. Sessions and identifiers connect calls to programs and threads, while replicas communicate through a coordinating meta-engine.
- Architecture: Autellix comprises a frontend, scheduler, and load balancer implemented in about 5k lines of Python and CUDA/C++ code.It builds on vLLM v0.6.1 and localizes changes primarily to scheduling policies.
- Frontend: The frontend exposes a stateful session interface while transparently annotating calls with session, program, and thread identifiers.Session entries are created at initialization and removed when programs complete or encounter errors.
- Multi-engine: AsyncMultiLLMEngine coordinates dedicated Python-process replicas through inter-process communication.A meta-engine assigns incoming requests to appropriate engine replicas.
6 Evaluation
The evaluation studies Autellix across four agentic workloads with varied call and token distributions. The workloads span conversational, tool-use, computationally intensive, and mixed program classes.
- Workloads: Autellix is evaluated across four representative agentic workloads and ablated against alternative design choices.The workloads vary in decode tokens, prefill tokens, and numbers of LLM calls.
- ShareGPT: ShareGPT programs average 6.66 LLM calls and can reach 80 calls, with decode-heavy calls averaging 277 decode tokens.The experiments replay entire conversations as programs rather than only the first turn.
- BFCL: BFCL programs average 10.75 calls and reach 70 calls, with prefill-heavy calls averaging 735.06 tokens and 34.14 decode tokens.The workload represents multi-turn, multi-step tool-usage tasks.
- LATS: LATS programs average 159.7 LLM calls, about an order of magnitude more than ShareGPT or BFCL.Its computationally intensive MCTS workload contains many parallel calls and averages 467.2 prefill and 72.6 decode tokens per call.
- Mixed: The mixed workload samples equally from ShareGPT, BFCL, and LATS to stress-test performance across program classes.Program arrivals are generated using a Poisson process after randomly sampling complete programs.
6.2 Experimental Setup
The experimental setup spans three LLMs and multiple GPU configurations, and evaluates program-level latency rather than only request-level token metrics. Baselines share the same maximum batch size.
- Models & Testbed: Experiments use LLaMA-3.1-8B, LLaMA-3.1-70B, and Falcon-180B on 1, 4, and 8 GPUs, respectively.The testbed is an eight-A100 GCP instance connected via NVLink.
- Metrics: Program-level token latency is total program response time divided by generated tokens.For multi-threaded programs, response time is the critical-path response time divided by total tokens across threads.
- Baselines: The evaluation compares Autellix with vLLM, vLLM-opt, and MLFQ using the same maximum batch size.vLLM uses continuous batching and PagedAttention; vLLM-opt adds chunk-prefill, prefix-caching, and multi-step scheduling.
6.3 End-to-End Single-Engine Performance
Across single-engine workloads, Autellix improves throughput by addressing both call-level and program-level head-of-line blocking, with gains sustained under heavy load and heterogeneous workloads.
- Autellix achieves up to 8× the throughput of vLLM, 2× vLLM-opt, and 1.5× MLFQ under heavy load.
- MLFQ mitigates call-level head-of-line blocking but still suffers from program-level blocking at high load.
- Multi-threaded workloads: On LATS, Autellix outperforms vLLM, MLFQ, and vLLM-opt by up to 5×, 2.5×, and 2×, respectively.
- Mixed workloads: On mixed workloads, Autellix achieves up to 15× higher throughput than vLLM, 5.5× than MLFQ, and 4× than vLLM-opt.
- Tail latency: Autellix maintains lower tail latencies than MLFQ and vLLM-opt in 7 of 8 scenarios while improving P95/99 throughput by up to 1.7×.
6.4 End-to-End Multi-Engine Performance
Autellix’s data-locality-aware load balancing maintains low latency and improves throughput across multi-engine configurations, while scaling linearly with the number of replicas.
- Load balancing policies: Round Robin and Least Used neglect data locality, causing costly KV-cache misses and frequent recomputation.
- Autellix delivers up to 1.4× higher throughput than Round Robin and Least Used across multi-engine configurations.
- Autellix maintains low average and tail latencies across configurations using four LLaMA3.1-8B replicas and two LLaMA3.1-70B replicas.
- Scalability: Autellix’s maximum arrival rate scales linearly with the number of replicas at the same SLO.
- Offline batch inference: Autellix decreases the makespan required to process offline batches of programs.
6.5 Ablations
Ablations show that Autellix reduces makespan, wait time, swap overhead, and scheduling cost, while remaining below the idealized performance of clairvoyant scheduling.
- Offline batch inference: Autellix decreases average offline-batch makespan by 10–40% and completes workloads where MLFQ fails at 4000 programs.
- Inference overheads: Autellix reduces wait and swap times, although preemption introduces higher scheduling time than vLLM-OPT’s naive FCFS.
- Inference overheads: Autellix incurs lower scheduling overhead than MLFQ through program-level priorities and more efficient distribution across priority queues.
- Optimal scheduling comparison: Autellix outperforms FCFS and other preemptive schedulers in simulation but remains below the optimal SRPT policy.
- Swap kernel: Autellix’s swap kernel reduces swaps by up to 18×, swap times by 3–7×, and achieves 1.3× higher throughput than vLLM’s kernel.
7 Discussion & Future Work
Autellix dynamically constructs execution graphs at runtime, while future work could use predicted immediate steps to enable compiler optimizations; improved scheduling may also benefit distributed reinforcement-learning workloads.
- Graph Optimizations: Autellix constructs a program’s execution DAG dynamically because it assumes no prior knowledge of the full graph.
- Graph Optimizations: Future compiler optimizations could use anticipated immediate steps for branch prediction and speculative execution, but the paper defers them.
- Post-Training: More effective scheduling can reduce batch-sampling makespan for each distributed reinforcement-learning iteration.
8 Conclusion
Autellix serves highly dynamic general programs as first-class workloads, using program-level scheduling and locality-aware load balancing to improve program performance. It improves program throughput by 4×–15× at the same latency as systems such as vLLM.
- Autellix is a distributed LLM serving system designed for highly dynamic, general programs rather than individual LLM calls.
- Program-level statistics, two scheduling algorithms, and locality-aware load balancing reduce programs’ waiting and execution times.
- 4×–15× higher program throughput at the same latency is achieved compared to state-of-the-art systems such as vLLM.