PaperlayerView exact revision on arXiv

Source-linked AI summary

Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve

Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov, Ramachandran Ramjee

arXiv:2403.02310v3cs.LGcs.DC

TL;DR

LLM serving must reconcile batching’s throughput benefits with latency requirements across prefill and decode phases. Sarathi-Serve uses chunked-prefills and stall-free batching to add requests without pausing decodes and to reduce pipeline imbalance. It reports higher serving capacity across models and hardware, including up to 5.6× for Falcon-180B.

  • Problem

    Existing LLM schedulers face a throughput-latency tradeoff because batching and prefill/decode interleaving can favor one objective over the other.

  • Method

    Sarathi-Serve splits prefills into chunks and uses stall-free schedules that admit new requests while ongoing decodes continue.

  • Results

    Sarathi-Serve improves serving capacity across models, hardware, and parallelism strategies, reaching up to 5.6× for Falcon-180B on 8 A100 GPUs.

  • Takeaways & Limitations

    Chunked-prefills and stall-free batching provide a scheduling approach that supports high throughput with low TBT latency and fewer pipeline bubbles.

  • Takeaways & Limitations

    Token-budget selection must balance pipeline bubbles from large chunks against overhead from very small chunks.

Abstract

from arXiv · show

Each LLM serving request goes through two phases. The first is prefill which processes the entire input prompt and produces the first output token and the second is decode which generates the rest of output tokens, one-at-a-time. Prefill iterations have high latency but saturate GPU compute due to parallel processing of the input prompt. In contrast, decode iterations have low latency but also low compute utilization because a decode iteration processes only a single token per request. This makes batching highly effective for decodes and consequently for overall throughput. However, batching multiple requests leads to an interleaving of prefill and decode iterations which makes it challenging to achieve both high throughput and low latency. We introduce an efficient LLM inference scheduler, Sarathi-Serve, to address this throughput-latency tradeoff. Sarathi-Serve introduces chunked-prefills which splits a prefill request into near equal sized chunks and creates stall-free schedules that adds new requests in a batch without pausing ongoing decodes. Stall-free scheduling unlocks the opportunity to improve throughput with large batch sizes while minimizing the effect of batching on latency. Furthermore, uniform batches in Sarathi-Serve ameliorate the imbalance between iterations resulting in minimal pipeline bubbles. Our techniques yield significant improvements in inference performance across models and hardware under tail latency constraints. For Mistral-7B on single A100 GPUs, we achieve 2.6x higher serving capacity and up to 3.7x higher serving capacity for the Yi-34B model on two A100 GPUs as compared to vLLM. When used with pipeline parallelism on Falcon-180B, Sarathi-Serve provides up to 5.6x gain in the end-to-end serving capacity. The source code for Sarathi-Serve is available at https://github.com/microsoft/sarathi-serve.

1 Introduction

LLM inference schedulers must balance throughput, which batching improves, against latency, which scheduling choices can degrade. Sarathi-Serve addresses this tradeoff with chunked-prefills and stall-free scheduling, improving serving capacity across models and hardware.

  • Motivation: LLM inference has compute-bound prefill and memory-bound decode phases, so batching benefits decodes substantially more than prefills.Prefill processes prompt tokens in parallel, while decode processes one token per request at a time.
  • Throughput-Latency Trade-off: Existing schedulers trade throughput against latency because prefill- and decode-prioritizing policies favor different objectives.Prefill prioritization can improve throughput but interfere with ongoing decodes, while decode prioritization favors TBT latency.
  • Existing Limitations: Generation stalls in prefill-prioritizing systems can last over several seconds when long prefills interfere with ongoing decodes.Reducing batch size can mitigate latency spikes but adversely affects throughput.
  • Sarathi-Serve: Sarathi-Serve splits prefills into compute-sized chunks and admits them alongside ongoing decodes without pausing those decodes.Its stall-free scheduler constructs batches by coalescing decodes with prefill chunks within a configured token budget.
  • Sarathi-Serve: Uniform hybrid batches reduce pipeline bubbles and improve GPU utilization, supporting scalable pipeline-parallel deployments.The batches combine prefill and decode tokens with near-uniform compute requirements.
  • Results: 5.6× gains in end-to-end serving capacity are reported for Falcon-180B with pipeline parallelism, alongside up to 3.7× for Yi-34B and 2.6× for Mistral-7B.The evaluation spans multiple models, hardware configurations, and parallelism strategies.

2 Background

LLM serving alternates between prefill and autoregressive decode, with throughput shaped by batching and deployment shaped by parallelism. Existing batching policies improve either utilization or latency, motivating careful scheduling choices.

  • Inference Phases: Prefill processes all prompt tokens in parallel, whereas decode generates one token per iteration and therefore has lower compute utilization.This phase difference explains why batching affects the two phases differently.
  • Scheduling Policies: Request-level batching waits for all requests to finish decoding before admitting new prefills, optimizing TBT but wasting compute in small decode-only batches.Variation in request input and output lengths contributes to inefficient resource utilization.
  • Model Parallelism: Tensor parallelism shards layers and KV-cache across GPUs but incurs critical-path all-reduce communication, making it preferable within high-bandwidth single-node interconnects.Pipeline parallelism instead splits layers across GPUs and uses microbatches with point-to-point communication.
  • Performance Metrics: Capacity is the maximum request load a system can sustain while meeting specified latency targets, and higher capacity reduces serving cost.The principal latency metrics are TTFT and TBT.
  • Throughput Characteristics: Batching boosts decode throughput almost linearly but has only a marginal effect on prefill throughput for Mistral-7B on a single A100 GPU.The experiments use a prompt length of 1024 for both phases, with different y-axis scales.
  • Scheduling Policies: Iteration-level batching lets requests enter and exit after each model iteration, increasing throughput by avoiding request-level batching inefficiencies.Orca introduced this mechanism, which is used by systems including vLLM, TensorRT-LLM, and LightLLM.
  • Scheduling Policies: Prefill-prioritizing iteration-level schedulers eagerly admit new requests, increasing later decode batch sizes but potentially causing generation stalls.These stalls arise because prefills can take arbitrarily long depending on prompt length.

3 Motivation

LLM inference schedulers face a throughput–latency tradeoff because prefills and decodes have different compute characteristics, while pipeline parallelism introduces bubbles. Sarathi-Serve addresses these issues by combining chunked-prefills, stall-free scheduling, and uniform-compute batches.

  • Cost Analysis of Prefill and Decode: Prefill batches are compute-bound and nearly saturated with one request, whereas decode throughput increases roughly linearly with batch size.Decode iterations process one token per request and benefit strongly from batching; prefills process all prompt tokens in parallel.
  • Cost Analysis of Prefill and Decode: Decode batches are memory-bound, so additional tokens can be processed with little latency increase while GPU compute remains underutilized.Low arithmetic intensity makes decode operations bottlenecked by memory fetch time.
  • Throughput-Latency Trade-off: Existing schedulers trade throughput against latency: prefill-prioritizing policies cause generation stalls, while decode-prioritizing policies preserve low TBT latency but reduce throughput.Smaller batches can reduce latency spikes but adversely impact throughput.
  • Throughput-Latency Trade-off: Sarathi-Serve splits large prefills into chunks and combines them with ongoing decodes to form stall-free, balanced batches.The design targets both GPU utilization and uninterrupted decode progress.
  • Pipeline Bubbles waste GPU Cycles: Pipeline bubbles arise because consecutive inference micro-batches have different compute requirements based on their prefill and decode composition.Sarathi-Serve minimizes these bubbles by creating uniform-compute batches.

4 Sarathi-Serve: Design and Implementation

Sarathi-Serve combines chunked-prefills with stall-free batching to improve throughput while limiting decode latency. Its token-budget selection balances TBT requirements, chunking overhead, hardware effects, and pipeline-bubble costs.

  • Design overview: Sarathi-Serve uses chunked-prefills and stall-free batching to provide high throughput with predictable tail latency.Chunked-prefills split prefills across iterations, while stall-free batching coalesces them with ongoing decodes.
  • Chunked-prefills: Chunked-prefills split large prompts into smaller compute-sized chunks that can use decode-batch slack without violating the TBT SLO.The chunks remain large enough to saturate GPU compute while limiting the latency impact of co-running prefills.
  • Stall-free batching: Stall-free batching fills each batch with ongoing decodes, then partial prefills and new requests within a token budget, preventing generation stalls.The scheduler restricts computational load per iteration so co-running prefill chunks do not delay ongoing decodes.
  • Pipeline parallelism: Sarathi-Serve’s hybrid batches have near-uniform compute requirements, reducing pipeline bubbles and improving GPU utilization with pipeline parallelism.Coalescing chunked prefills with ongoing decodes helps avoid latency spikes while supporting scalable deployments.
  • Token-budget selection: Token-budget selection balances TBT SLOs against chunking overhead, including repeated KV-cache reads, lower GPU utilization, tile quantization, and pipeline bubbles.One-time profiling can select the maximum batch token count that meets the TBT SLO; deployment hardware and parallelism also affect the choice.

5 Evaluation

The evaluation examines Sarathi-Serve’s capacity under SLO constraints and across tensor- and pipeline-parallel deployments, using multiple models, GPU configurations, and baselines.

  • Evaluation scope: The evaluation compares Sarathi-Serve with vLLM and Orca across multiple models, GPU configurations, and two datasets.The study considers maximum replica load under SLO constraints and how capacity changes with different SLO targets.
  • Parallel deployments: The evaluation tests Sarathi-Serve under both tensor parallelism and pipeline parallelism deployments.A dedicated question examines performance across these deployment strategies.

3. What is the overhead of chunked-prefills? (§5.4.1)

Sarathi-Serve’s chunked-prefills and stall-free batching improve serving capacity under strict and relaxed latency SLOs across models and parallelism configurations. Chunking adds moderate overhead at small token budgets but is nearly negligible at larger budgets, while the two techniques work best together.

  • Capacity evaluation: Sarathi-Serve sustains up to 4.0× higher load than Orca and 3.7× higher load than vLLM under strict SLO for Yi-34B.For LLaMA2-70B with pipeline parallelism, gains reach 6.3× over Orca and 4.3× over vLLM.
  • Capacity evaluation: Orca and vLLM usually violate the P99 TBT SLO before reaching maximum serviceable throughput.Sarathi-Serve adjusts token budgets, using smaller chunks for strict SLOs and larger chunks for relaxed SLOs.
  • Throughput-latency tradeoff: vLLM’s capacity remains largely identical across maximum batch sizes of 32, 64, and 128 because generation stalls cap capacity under stringent TBT SLOs.Thus, larger memory-efficient batches are not effectively leveraged under strict latency constraints.
  • Throughput-latency tradeoff: 3.5× higher capacity than vLLM is achieved under a 100ms strict SLO for Mistral-7B with a 512-token budget.Under a 1s relaxed SLO for Yi-34B, a 2048-token budget yields 1.65× higher capacity than vLLM.
  • Overhead of chunked-prefills: With token budget 512, chunking adds at most approximately 25% overhead to Yi-34B prefill runtime, while overhead is almost negligible at budget 2048.Smaller chunks introduce higher overhead.
  • Impact of individual techniques: Chunked-prefills-only increases TTFT, hybrid-batching-only increases TBT, and using both techniques together improves performance along both dimensions.Long prefills can still create generation stalls without chunking, while prefill chunks are slightly inefficient without hybrid batching.

6 Related Work

Related work spans general model-serving systems, transformer-specific inference optimizations, phase disaggregation, scheduling improvements, communication overlap, attention optimization, and model parallelization. These approaches address complementary serving and systems challenges.

  • Model serving systems: General serving systems study placement, caching, and batching, while newer systems target autoregressive transformer inference with domain-specific optimizations.Examples include Clipper, TensorFlow-Serving, Clockwork, Batch-Maker, Orca, vLLM, FlexGen, FasterTransformers, LightSeq, and TurboTransformers.
  • Phase disaggregation: Prefill-decode disaggregation can eliminate phase interference but requires migrating each request’s KV cache between replicas.This migration can be challenging without high-bandwidth interconnects.
  • Scheduling optimizations: Fairness and preemption-based scheduling address multi-tenant fairness and head-of-line blocking, respectively.These algorithmic optimizations are described as complementary to the paper’s approach.
  • Systems and model optimizations: Communication-compute overlap, self-attention memory optimization, and parallelization strategies target GPU utilization, memory bottlenecks, and model placement.The paper characterizes these techniques as orthogonal to Sarathi-Serve.

7 Conclusion

Existing LLM schedulers favor either throughput or TBT latency, leaving the joint objective unresolved. Sarathi-Serve addresses this tradeoff with chunked-prefills and stall-free batching, improving serving capacity across evaluated deployments.

  • Conclusion: Prefill-prioritizing schedulers generally optimize throughput, while decode-prioritizing schedulers generally optimize TBT latency; neither is ideal for both objectives.The conclusion frames this as the central limitation of existing scheduler categories.
  • Conclusion: Sarathi-Serve combines chunked-prefills with stall-free batching to add requests to running batches without pausing ongoing decodes.The approach chunks prompts into smaller units of work to create stall-free schedules.
  • Conclusion: 2.6× higher serving capacity is achieved for Mistral-7B on one A100 GPU, and up to 5.6× for Falcon-180B on eight A100 GPUs.These are reported evaluation outcomes for the two deployments.

Abstract

The open-source artifact includes Sarathi-Serve’s implementation and experiment harnesses. It is a lightweight research prototype derived from vLLM and does not provide complete feature parity.

  • Artifact: The repository contains Sarathi-Serve’s implementation plus harnesses and scripts for running and plotting the paper’s experiments.The artifact is available as an open-source repository.
  • Artifact: Sarathi-Serve is a lightweight research prototype that retains critical vLLM features but lacks complete feature parity with open-source vLLM.The codebase was adapted to support faster research iterations.

Scope

The artifact supports validation and replication of Sarathi-Serve’s reported experiments and figures.

  • The artifact enables readers to validate the paper’s figure-based claims and replicate its experiments.It includes setup for the main results and microbenchmarks.

Hosting

Sarathi-Serve artifacts are hosted through GitHub with reproducibility instructions and documented GPU and parallelism configurations.

  • The artifacts are available from the GitHub repository, whose main branch is actively updated.
  • Reproduction instructions for the OSDI experiments are provided in the osdi-sarathi-serve branch’s README files.
  • Sarathi-Serve was tested with CUDA 12.1 on A100 and A40 GPUs.The README documents the specific GPU SKUs and parallelism strategies used for the figures.
Loading 2403.02310v3…