PaperlayerView exact revision on arXiv

Source-linked AI summary

NanoFlow: Towards Optimal Large Language Model Serving Throughput

Kan Zhu, Yufei Gao, Yilong Zhao, Liangyu Zhao, Gefei Zuo, Yile Gu, Dedong Xie, Tian Tang, Qinyu Xu, Zihao Ye, Keisuke Kamahori, Chien-Yu Lin, Ziren Wang, Stephanie Wang, Arvind Krishnamurthy, Baris Kasikci

arXiv:2408.12757v2cs.DC

TL;DR

LLM serving is often assumed to be memory-bound, although whole workloads are often compute-bound and existing engines underutilize compute by executing heterogeneous operations sequentially. NanoFlow overlaps such operations through intra-device nano-batch pipelines and automatically searches their schedules. Across evaluated popular models, its pipelines reach 50%-72% of optimal throughput and average 2.66× throughput gain over vLLM.

  • Problem

    LLM serving is commonly assumed to be memory-bandwidth-bound, while existing engines execute heterogeneous operations sequentially and achieve only 40% total compute utilization.

    Source: §1 · p. 2, §3.6 · p. 7

  • Method

    NanoFlow splits batches into independent nano-batches and uses auto-search to schedule overlapping operations while profiling and accounting for kernel interference.

    Source: §1 · p. 2

  • Results

    Across evaluated popular models, NanoFlow-generated pipelines reach 50%-72% of optimal throughput and average 2.66× throughput gain over vLLM.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For many common workloads and LLMs, total compute operations dominate network and memory I/O even though self-attention is memory-bound.

    Source: §1 · p. 2

    Interference modeling uses GEMM performance as a proxy for physical resource allocation, assuming compute dominates because compute optimization is NanoFlow’s goal.

    Source: §4.1.1 · p. 8

Abstract

from arXiv · show

Large Language Models (LLMs) have resulted in a surging demand for planet-scale serving systems, where tens of thousands of GPUs continuously serve hundreds of millions of users. Consequently, throughput has emerged as a key metric that determines serving systems' performance. Due to large model sizes and memory-intensive self-attention, LLM serving has been commonly assumed to be memory-bound. Through a detailed analysis, we show that despite having memory-intensive components, end-to-end LLM serving is compute bound for most common workloads and LLMs. Alas, most existing serving engines fall short from optimal compute utilization, because the heterogeneous operations that comprise LLM serving--compute, memory, networking--are executed sequentially within a device. We propose NanoFlow, a novel serving framework that exploits intra-device parallelism, which overlaps the usage of heterogeneous resources within a single device. NanoFlow splits inputs into smaller nano-batches and duplicates operations to operate on each portion independently, enabling overlapping. NanoFlow automatically identifies the number, size, ordering, and GPU resource allocation of nano-batches to minimize the execution time, while considering the interference of concurrent operations. We evaluate NanoFlow's end-to-end serving throughput on several popular models such as LLaMA-2-70B, Mixtral 8x7B, LLaMA-3-8B, etc. With practical workloads, NanoFlow provides 1.91x throughput boost compared to state-of-the-art serving systems achieving 50% to 72% of optimal throughput across popular models.

1 Introduction

LLM serving throughput matters amid resource-intensive models and growing demand, yet whole-workload compute often dominates despite memory-bound attention. NanoFlow targets underutilization by overlapping heterogeneous operations within a device, and its evaluation reports throughput gains over existing systems.

1 Introduction

  • For many common workloads and LLMs, total compute operations dominate network and memory I/O even though self-attention is memory-bound.Batching prefill and decode amortizes weight loading for compute-bound GEMMs; grouped-query attention can reduce decode KV-cache loads, while larger models increase GEMM compute relative to attention.Source: §1 · p. 2
  • Existing engines execute heterogeneous operations sequentially, leaving total compute utilization at 40% despite individual operations reaching about 80% utilization of their bottlenecked resource.Memory-bound attention and network communication accompany compute-bound operations, so sequential execution leaves the compute resource underused.Source: §1 · p. 2
  • NanoFlow splits batches into independent nano-batches and duplicates operations so compute-, memory-, and network-bound work can overlap within one device.The added weight-loading I/O can be hidden by pipelining when the workload is compute-bound overall; operations can also receive fractions of GPU resources.Source: §1 · p. 2
  • NanoFlow’s auto-search constructs pipelines by first scheduling nano-operations without interference, then profiling concurrent-kernel interference and replanning.The search addresses choices of nano-batch count, size, ordering, and GPU resource allocation; the runtime forms nano-batches and manages GPU resources and KV-cache.Source: §1 · p. 2
  • NanoFlow averages 1.91× greater throughput than state-of-the-art frameworks on practical LLaMA-2-70B workloads, reaching 68.5% of theoretical optimal throughput.Across other evaluated models, generated pipelines reach 50%-72% of optimal throughput and average 2.66× throughput gain over vLLM.Source: §1 · p. 2

2 Background

The background describes the prefill and decode workflow, distinguishes operations by their resource demands, and outlines how multi-GPU serving combines parallelism approaches.

2.1 LLM Inference Workflow

  • LLM inference has prefill, which processes the prompt and initializes the KV-cache, followed by autoregressive decode that generates tokens one at a time.Requests traverse decoder layers that apply attention and feed-forward operations to produce subsequent tokens.Source: §2.1 · p. 3

2.2 Operation Characteristics

  • Dense operations are compute-bound through batching, while attention is compute-bound in prefill but memory-bound in decode; collective communication is network-bound, and other operations are comparatively short.Dense operations include KQV generation and O, Up, Gate, and Down projections; other operations include layer norms and position embeddings.Source: §2.2 · p. 3

2.3 Serving LLMs at Scale

  • Serving large models across GPUs commonly combines tensor parallelism within a node with pipeline parallelism across nodes.Tensor parallelism splits weight matrices across GPUs and requires collective communication; pipeline parallelism divides model layers into stages processing different micro-batches.Source: §2.3 · pp. 3–4

3 Analysis

The analysis models LLM serving costs and finds that common modern workloads are generally compute-bound, despite memory-intensive operations. It uses this finding to motivate NanoFlow’s intra-device parallelism and nano-batching.

3.1 Key Factors of Serving Throughput

  • Throughput depends on hardware, model configuration, user queries, and batch size; the optimal-throughput analysis assumes the largest batch that fits model weights and KV caches in memory.Larger batches amortize weight loading and increase execution-unit occupancy for compute-bound dense operations.Source: §3.1 · p. 4

3.2 Cost Model of LLM Serving

  • The cost model estimates memory, compute, and network iteration times; memory content is loaded once per iteration, while dense-operation compute scales with batch size and model parameters.Tensor parallelism adds collective communication, modeled from the dense-operation inputs and model dimensions.Source: §3.2 · pp. 4–5

3.3 Classification of LLM Serving Workloads

  • The cost model and workload comparisons indicate that modern LLM serving is generally compute-bound, with long decode on LLaMA-3 8B near parity and accelerator ratios stable across vendors and generations.For large models and data-center GPUs, compute takes more time than network.Source: §3.3 · p. 6

3.4 Validation of the Cost Model

  • Cost-model estimates align with measured runtimes for most operations; prefill attention is slower because kernel-launch overhead dominates its runtime.The validation used LLaMA-2 70B on eight A100 GPUs with a dense batch of 2048 requests.Source: §3.4 · p. 6

3.5 Optimal Serving Throughput

  • For LLaMA-2 70B on eight A100 GPUs, the estimated optimal throughput is 1857 tokens/s/GPU.The calculation uses profiled peak compute of 280 TFLOPS for FP16 and a 70B-parameter model.Source: §3.5 · p. 7

3.6 Gap to Optimal Throughput

  • vLLM, DeepSpeed-FastGen, and TensorRT-LLM achieve 22.0%, 22.9%, and 37.8% of optimal throughput, respectively, on offline requests.The analysis attributes the gap to sequential execution that creates pipeline bubbles and leaves compute underutilized.Source: §3.6 · p. 7

3.7 Intra-device Parallelism

  • 1.91× greater average throughput than existing serving frameworks is reported for NanoFlow, despite repeated model-weight loading.The comparison covers practical workloads; the passage also says this further closes the gap to optimal throughput.Source: §3.7 · p. 7
  • NanoFlow splits batches into independent nano-batches so operations using different resources can overlap within a device, targeting higher compute utilization.For a batch of 2048, the example divides work into ranges 0–768 and 768–2048; the operations may reload weights.Source: §3.7 · p. 7

4 Design

NanoFlow’s design has two key components: an auto-search engine that computes nano-batch pipelines and a runtime that executes them.

4 Design

  • Auto-search computes nano-batch pipelines, and the serving runtime executes them.These are NanoFlow’s two key components.Source: §4 · p. 7

4.1 Automated Pipeline Search

NanoFlow’s auto-search uses mixed integer linear programming and a two-stage approximation to construct intra-device pipelines. It profiles kernel interference, searches pipeline structure, then refines resource allocation and provides model-specific schedules.

4.1 Automated Pipeline Search

  • The search uses MILP with a two-stage approximation to find an intra-device pipeline while accounting for kernel interference.Stage I searches pipeline structure; Stage II refines GPU resource allocation.Source: §4.1 · p. 7, §4.1.3 · p. 9

4.1.1 Kernel Profiling and Interference Modeling

  • NanoFlow profiles GEMM, GEMV, and network kernels, modeling pairwise interference with GEMM performance as a proxy for resource utilization.The resulting R-to-P mapping is consistent across evaluated model shapes and 64 batch-size combinations, with standard deviation within 5% of the mean.Source: §4.1.1 · pp. 7–9
  • NanoFlow profiles a reduced set of kernel combinations and maps resource utilization R to normalized GEMV or network performance P.It focuses on pairwise compute-memory and compute-network interference, and assumes the pairwise mapping applies when three kernels overlap.Source: §4.1.1 · pp. 8–9, Table 3 · p. 9

4.1.2 Auto-search Stage I: Pipeline Structure Search

  • Stage I uses MILP to choose nano-operation counts, batch sizes, and ordering from dependencies and interference-free profiles, aiming to remove compute pipeline bubbles.It starts with two nano-operations and increases their number near compute bubbles; batch sizes range from 128 to the dense batch size.Source: §4.1.2 · p. 9
  • Stage I restricts overlap to operations constrained by different resources and treats nano-operations as dependent when their parent operations are dependent and their input batches intersect.The search also considers alternative network collective transformations; a feasible pipeline can be found in approximately 10 minutes rather than searching for a provably optimal pipeline for hours or days.Source: §4.1.2 · p. 9

4.1.3 Auto-search Stage II: Refining the Pipeline

  • Stage II refines Stage I’s schedule by mapping GPU resource allocations to kernel performance under interference, minimizing pipeline execution time.Concurrent operations’ resource allocations must total at most 1.0; execution time is estimated as Dbest/P.Source: §4.1.3 · p. 9

4.1.4 Example Pipelines

  • Auto-search finds similar schedules for evaluated 70B models; LLaMA-2 70B uses four nano-operations during KQV generation and two for the rest of the pipeline.At the start of decoding, decode attention uses resource utilization 0.4 and reaches 80% of maximum decode-attention performance; 8B models overlap decode attention with the Up Gate Down projection, while MoE pipelines account for grouped-GEMM and gate routing.Source: §4.1.4 · p. 10

4.2 NanoFlow Runtime

NanoFlow’s runtime schedules batches asynchronously and manages KV-cache movement to support serving and multi-round conversations. Its scheduling overlaps CPU-side batch formation with GPU execution, while its cache system uses host memory and SSDs.

4.2 NanoFlow Runtime

  • The runtime executes auto-generated pipelines through asynchronous scheduling and KV-cache SSD offloading for multi-round conversations.These are the two runtime functions introduced in this section.Source: §4.2 · p. 10

4.2.1 Request Scheduling

  • Batch formation prioritizes unfinished decode requests and chunks prefill requests to fill a fixed dense-batch capacity, stabilizing the request mix across iterations.NanoFlow predicts peak future memory use and prefills new requests only when predicted use remains within GPU limits.Source: §4.2.1 · p. 10
  • Asynchronous scheduling forms the next batch before the current GPU iteration ends, hiding batch-formation overhead at the cost of one extra decode token.For typical workloads with average decode lengths over 100, that token’s overhead is less than 1%.Source: §4.2.1 · p. 10

4.2.2 KV-cache Management

  • NanoFlow offloads running requests’ KV-cache to host memory and SSDs, then loads a prior round’s cache when a new conversation round arrives.It copies KV vectors during compute-bound FFN operations; fragmented GPU pages are loaded through contiguous space before scattering, achieving 7–10× higher host-to-device copy bandwidth.Source: §4.2.2 · pp. 10–11

5 Implementation

NanoFlow is implemented for NVIDIA GPUs using CUDA and Python.

5 Implementation

  • The NVIDIA GPU implementation comprises approximately 10K lines of CUDA and 6K lines of Python.These figures describe the implementation size.Source: §5 · p. 11
  • The runtime launches kernels for each nano-batch according to auto-search resource requirements and ordering constraints, enforcing dependencies with CUDA events.Source: §5 · p. 11

6 Evaluation

NanoFlow is evaluated against established serving frameworks across throughput, latency, resource use, and multiple LLMs. It leads throughput comparisons and sustains higher request rates within the tested latency SLO, with ablations examining its pipeline techniques.

6.2 Throughput

  • On dataset-derived workloads, NanoFlow averaged 4.18× vLLM, 3.45× DeepSpeed-FastGen, and 1.91× TensorRT-LLM throughput; constant-length gains were 2.62×, 2.78×, and 1.73×, respectively.NanoFlow reached 68.5% of theoretical optimal throughput in the best case.Source: Figure 7 · p. 11, §6.2 · p. 12

6.1 Experiment Setup

  • The evaluation uses LLaMA-2-70B on 8×A100 GPUs, with five other representative models also evaluated; workloads include sampled ShareGPT, LMSYS-Chat-1M, and Splitwise traces.Throughput is measured as total input and output tokens divided by execution time, against an optimal throughput of 1857 tokens/s/GPU.Source: §6.1 · pp. 11–12, §6.2 · p. 12

6.3 Latency

  • Within the 200ms normalized-latency SLO, NanoFlow sustains higher request rates across datasets, including 1.64× TensorRT-LLM’s rate on LMSys-Chat-1M.At lower rates its latency is comparable but slightly higher; near maximum throughput, its 99th-percentile latency is 1.07× average latency.Source: §6.3 · p. 12, Figure 8 · p. 13

6.4 Ablation Study

  • Overlapping network-bound kernels yields 1.07× speedup, while overlapping network- and memory-bound kernels yields 1.17× versus the non-overlapped baseline.Nano-batching alone reduces performance by 13.2%; offloading slows the pipeline by 3.0% but can reduce compute by 3.02x for multi-round LMSYS-Chat workloads.Source: §6.4 · pp. 12–13, Figure 9 · p. 13

6.5 Resource Usage

  • NanoFlow concurrently uses multiple resources and achieves 68.5% average compute utilization, while the sequential baseline mostly uses one resource at a time.Kernel interference keeps NanoFlow below optimal compute usage.Source: §6.5 · p. 13

6.6 Performance on Other LLMs

  • Across other evaluated LLMs, NanoFlow reaches 50%–72% of optimal throughput and surpasses vLLM.Evaluations use input length 1024 and output length 512; LLaMA-3-8B runs on one A100, while the other models use 8×A100 GPUs.Source: §6.6 · p. 13

7 Related Work

NanoFlow differs from prior serving and operation-level work through fine-grained intra-device resource management and nano-batching. Its framework can incorporate new operation implementations by profiling their performance and interference.

LLM serving optimizations

  • Prior serving optimizations schedule requests, phases, or chunks, whereas NanoFlow schedules operations within a device for fine-grained resource management.It can adopt new operation implementations by profiling performance and interference characteristics and integrating them into auto-search.Source: §7 · p. 13

Operation-level parallelism

  • Operation-level systems have explored functional-unit remapping, algebraic transformations, and tile-level graphs, but the cited approaches do not account for differing resource demands or retain broad parallelism.NanoFlow creates more overlapping opportunities through nano-batching.Source: §7 · pp. 13–14

Comparison with prior work

  • NanoFlow’s resource usage overlaps compute, memory, and network activity, while its throughput exceeds vLLM’s and reaches up to 78.5% of optimal throughput on other models.The resource and throughput comparisons are shown in Figures 10 and 11.Source: Figure 10 · p. 14, Figure 11 · p. 14

8 Conclusion

NanoFlow analyzes LLM-serving operations and addresses compute underutilization by constructing intra-device pipelines that overlap nano-operations.

8 Conclusion

  • NanoFlow analyzes LLM-serving operations, identifies underutilized compute from sequential heterogeneous operations, and automatically constructs adaptive intra-device pipelines that overlap nano-operations.The conclusion reports 1.91× throughput improvement over state-of-the-art frameworks, though the supplied passage truncates before naming the comparison scope.Source: §8 · p. 14

Related papers

Loading 2408.12757v2…