PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Distributed Inference Serving for Large Language Models

Bingyang Wu, Yinmin Zhong, Zili Zhang, Shengyu Liu, Fangyue Liu, Yuanhang Sun, Gang Huang, Xuanzhe Liu, Xin Jin

arXiv:2305.05920v3cs.LGcs.DC

TL;DR

Interactive LLM applications require low-latency inference, but run-to-completion serving suffers from head-of-line blocking. FastServe enables token-level preemption with skip-join MLFQ scheduling and proactive KV-cache management, improving throughput over vLLM by up to 31.4× and 17.9× under average and tail latency requirements, respectively.

  • Problem

    Existing LLM serving systems use run-to-completion processing, causing head-of-line blocking and long latency for interactive workloads.

  • Method

    FastServe combines token-level preemption, input-length-guided skip-join MLFQ scheduling, and proactive KV-cache offloading between GPU and host memory.

  • Results

    31.4× and 17.9× throughput improvements over vLLM are reported under the same average and tail latency requirements, respectively.

  • Takeaways & Limitations

    FastServe provides distributed LLM inference serving that addresses latency from head-of-line blocking while managing the memory overhead introduced by preemption.

  • Takeaways & Limitations

    Under insufficient GPU memory, deferring new jobs can degenerate MLFQ to FCFS, reintroducing head-of-line blocking.

Abstract

from arXiv · show

Large language models (LLMs) power a new generation of interactive AI applications exemplified by ChatGPT. The interactive nature of these applications demands low latency for LLM inference. Existing LLM serving systems use run-to-completion processing for inference jobs, which suffers from head-of-line blocking and long latency. We present FastServe, a distributed inference serving system for LLMs. FastServe exploits the autoregressive pattern of LLM inference to enable preemption at the granularity of each output token. FastServe uses preemptive scheduling to minimize latency with a novel skip-join Multi-Level Feedback Queue scheduler. Based on the new semi-information-agnostic setting of LLM inference, the scheduler leverages the input length information to assign an appropriate initial queue for each arrival job to join. The higher priority queues than the joined queue are skipped to reduce demotions. We design an efficient GPU memory management mechanism that proactively offloads and uploads intermediate state between GPU memory and host memory for LLM inference. We build a system prototype of FastServe and experimental results show that compared to the state-of-the-art solution vLLM, FastServe improves the throughput by up to 31.4x and 17.9x under the same average and tail latency requirements, respectively.

1 Introduction

LLM serving must reduce queuing delay because run-to-completion FCFS processing lets long jobs block short ones. FastServe uses token-level preemption, skip-join MLFQ scheduling, and proactive cache management to address latency and memory constraints.

  • Motivation: Long LLM jobs block incoming short jobs under existing FCFS run-to-completion serving, causing head-of-line blocking.Existing systems cannot expand a processing batch arbitrarily while it is running.
  • Motivation: Up to 90% of total latency is queuing delay in real-world LLM workloads, making execution-time optimization insufficient.Skewed output lengths create long queuing delays, especially as load approaches capacity.
  • FastServe: FastServe preempts jobs after each generated output token, choosing whether to continue the current job or run another queued job.This granularity follows LLM inference’s autoregressive, iteration-based execution pattern.
  • FastServe: Skip-join MLFQ assigns arrivals to queues using known input length and skips higher-priority queues to reduce demotions.The first output token can dominate execution for jobs with long inputs and short outputs.
  • Memory management: FastServe proactively offloads low-priority jobs’ intermediate state to host memory when GPU cache capacity nears exhaustion.Preemptive scheduling otherwise requires cache state for all started but unfinished jobs, unlike FCFS.
  • Evaluation: 31.4× and 17.9× throughput improvements over vLLM are reported under the same average and tail latency requirements, respectively.The evaluation includes OPT-175B on 16 NVIDIA A100 GPUs.

2 Background and Motivation

LLM inference generates tokens autoregressively, creating opportunities for iteration-level scheduling but also challenges from unknown output lengths and substantial KV-cache memory use. These properties motivate preemptive serving designs such as FastServe.

  • LLM inference: LLM inference repeatedly generates one output token per iteration until an end token or maximum output length is reached.The first generated token is appended to the prompt for subsequent iterations.
  • LLM inference: KV caching separates inference into initialization, which caches prompt tokens, and decoding, which computes only the newly generated token.The cache avoids recomputing preceding keys and values across iterations.
  • Existing systems: Iteration-level scheduling executes one iteration at a time, allowing completed jobs to return earlier and new jobs to enter between iterations.This improves on job-level execution, where early-completed jobs and arrivals wait for the batch.
  • Opportunities: Existing FCFS run-to-completion serving suffers severe head-of-line blocking, with queuing delay reaching up to 90% of total latency in real workloads.Preemptive scheduling is identified as an opportunity because each job consists of multiple token-generating iterations.
  • Challenges: SRPT cannot be directly applied because output length is unknown while real workloads have long-tailed input and output lengths.Iteration time is predictable, but the total number of iterations depends on job semantics.
  • Challenges: Preemptive scheduling must retain KV caches for pending preempted jobs, creating substantial GPU memory overhead.The cache itself grows with sequence length, while GPU capacity is also constrained by model weights.

3 FastServe Overview

FastServe combines profiler-guided skip-join MLFQ scheduling with distributed execution and proactive KV-cache management. Its design targets high throughput and low latency for large models under constrained GPU memory.

  • Goals: FastServe targets maximum throughput under a specified latency requirement for interactive LLM applications.The system is designed around both low latency and high throughput.
  • Scheduling: A job profiler determines each arrival’s initial priority before the scheduler places it in skip-join MLFQ.This placement is intended to mitigate head-of-line blocking.
  • Execution: The scheduler forms batches by priority and dispatches one iteration to the distributed execution engine.The execution engine updates each job’s relevant distributed KV-cache tensors.
  • Memory management: FastServe proactively swaps KV tensors to address limited GPU memory capacity during inference.The cache manager is integrated with execution to manage intermediate state as jobs progress.
  • Distributed execution: Tensor parallelism and pipeline parallelism enable distributed inference for extreme large models such as OPT-175B.FastServe extends both its scheduler and KV cache to support distributed execution.

4 FastServe Design

FastServe combines token-level preemption with skip-join MLFQ scheduling and proactive KV-cache swapping to reduce latency while managing GPU memory constraints.

  • Skip-Join MLFQ Scheduler: Skip-join MLFQ uses known input length and profiled initialization time to assign arriving jobs directly to an appropriate priority queue.Jobs join the highest-priority queue whose quantum is at least the predicted initialization time, then are demoted using current priority and next-iteration time.
  • Skip-Join MLFQ Scheduler: 3.3 average latency demonstrates that skip-join MLFQ approaches SRPT’s 3 average latency, outperforming FCFS at 4.23 and original MLFQ at 5.In the example, skip-joining the long-initialization job prevents it from blocking the remaining jobs.
  • Proactive KV-Cache Management: FastServe proactively offloads low-priority state to host memory and overlaps swapping with GPU inference to keep transfer overhead out of the critical path.The system uses estimated next scheduled time to order swaps, swapping out jobs scheduled latest and swapping in jobs scheduled soonest.

5 Implementation

FastServe is implemented as a RESTful frontend, scheduler, and distributed execution engine. The prototype includes skip-join MLFQ scheduling, proactive swapping, distributed GPU workers, and evaluation materials covering model configurations and baseline comparisons.

  • FastServe comprises a RESTful API frontend, a scheduler, and a distributed execution engine.
  • The implementation section includes model configurations and a comparison between FastServe and baselines.The baseline comparison identifies iteration-level preemption, iteration-level scheduling, PagedAttention, and pipeline parallelism.
  • The frontend and scheduler use 2.9K lines of Python, while the distributed execution engine uses 8.1K lines of C++/CUDA.The frontend supports an OpenAI API-compatible interface; the scheduler implements skip-join MLFQ and proactive swapping.
  • Ray actors implement GPU workers that execute LLM inference and manage the key-value cache across GPUs.

6 Evaluation

FastServe is evaluated against existing serving systems across models, workloads, latency targets, scheduling policies, and cache-management strategies. It consistently improves throughput while reducing queuing-related latency and keeping swapping overhead small.

  • End-to-End Performance: FastServe outperforms vLLM by 2.3–18.3× on ShareGPT and 3–31.4× on Alpaca under the latency SLO.Its skip-join MLFQ reduces queuing delay compared with vLLM’s FCFS scheduling.
  • Tail Latency: FastServe improves throughput under tail-latency SLOs by up to 17.9× over vLLM and 59.8× over FasterTransformer.It also outperforms FastServe-FCFS by up to 1.5× for OPT-175B and by 2–2.8× for OPT-13B and OPT-66B.
  • Goodput: FastServe achieves the highest P95 goodput across SLOs, outperforming vLLM by 4.1× to 4.7× and FastServe-FCFS by 1.46× to 1.64×.P95 goodput counts throughput when 95% of jobs complete within initialization- and decoding-phase SLOs.
  • Scheduling Ablation: Skip-join MLFQ outperforms FCFS, naive MLFQ, and Fixed Priority by up to 8.9×, 1.87×, and 13.9×, respectively.Its semi-information-agnostic policy handles changing input-to-output length ratios more consistently than the alternatives.
  • Cache Management: Proactive swapping outperforms recomputation by 2.7×, while swapping time remains below 5% of end-to-end latency.Most swapping overlaps with other jobs’ execution, so the mechanism nearly does not affect end-to-end latency.

7 Related Work

Prior work addresses deterministic inference, autoregressive LLM serving, and memory optimization through different scheduling and model-efficiency techniques. FastServe targets LLM-serving latency with scheduling and cache management tailored to LLM characteristics.

  • Inference Serving: Traditional serving systems target relatively small models without accounting for LLM-specific characteristics.Recent systems instead optimize Transformer-based LLM serving, including autoregressive generation and fairness.
  • Memory Optimization: Memory-optimization approaches include training techniques, quantization, sparsity, and PagedAttention, but some reduce inference memory by sacrificing model accuracy.Training-focused methods are orthogonal to the serving scenario.

8 Conclusion

FastServe combines token-level preemption, skip-join MLFQ scheduling, and proactive key-value cache management for distributed LLM inference serving. Compared with vLLM, it improves throughput under both average- and tail-latency SLOs.

  • Conclusion: FastServe enables iteration-level preemption, uses skip-join MLFQ to address head-of-line blocking, and proactively manages key-value caches.The cache mechanism hides data-transmission latency with computation.
  • Conclusion: FastServe improves throughput over vLLM by up to 31.4× under average-latency SLOs and 17.9× under tail-latency SLOs.These results come from the system prototype’s experiments.
Loading 2305.05920v3…