PaperlayerView exact revision on arXiv

Source-linked AI summary

LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention

Shang Yang, Junxian Guo, Haotian Tang, Qinghao Hu, Guangxuan Xiao, Jiaming Tang, Yujun Lin, Zhijian Liu, Yao Lu, Song Han

arXiv:2502.14866v2cs.CLcs.AIcs.DCcs.LGcs.PF

TL;DR

Long-sequence LLM serving is constrained by attention computation during prefilling and KV-cache demands during decoding. LServe unifies structured sparse attention patterns and combines static and dynamic sparsity. It reports faster prefilling and decoding while preserving long-context capabilities.

  • Problem

    Long-sequence LLM serving faces costly attention computation during prefilling and large KV-cache memory demands during decoding.

    Source: §1 · p. 1

  • Method

    LServe unifies hardware-friendly block-sparse attention patterns for prefilling and decoding, combining static and query-centric dynamic sparsity.

    Source: §1 · p. 2

  • Results

    Up to 2.9× prefilling speedup and 1.3×–2.1× average decoding speedup over vLLM, while preserving long-context capabilities.

    Source: §7 · p. 11

  • Takeaways & Limitations

    Static and dynamic sparsity can be combined with minimal accuracy impact while preserving long-context document and complex-reasoning capabilities.

    Source: §7 · p. 11

Abstract

from arXiv · show

Large language models (LLMs) have shown remarkable potential in processing long sequences and complex reasoning tasks, yet efficiently serving these models remains challenging due to the quadratic computational complexity of attention in the prefilling stage and the large memory footprint of the KV cache in the decoding stage. To address these issues, we introduce LServe, an efficient system that accelerates long-sequence LLM serving via hybrid sparse attention. This method unifies different hardware-friendly, structured sparsity patterns for both prefilling and decoding attention into a single framework, where computations on less important tokens are skipped block-wise. LServe demonstrates the compatibility of static and dynamic sparsity in long-context LLM attention. This design enables multiplicative speedups by combining these optimizations. Specifically, we convert half of the attention heads to nearly free streaming heads in both the prefilling and decoding stages. Additionally, we find that only a constant number of KV pages is required to preserve long-context and reasoning capabilities, irrespective of context length. We then design a hierarchical KV page selection policy that dynamically prunes KV pages based on query-centric similarity. On average, LServe accelerates LLM prefilling by up to 2.9x and decoding by 1.3-2.1x over vLLM, maintaining long-context accuracy. Code is released at https://github.com/mit-han-lab/omniserve.

1 INTRODUCTION

LServe targets long-context serving costs in prefilling and decoding by unifying structured block sparsity with static and dynamic attention optimizations. It reports speedups in both stages while preserving long-context capabilities.

1 INTRODUCTION

  • LServe combines hardware-friendly structured sparsity patterns in a block-sparse framework, skipping KV blocks to reduce sequential iterations in both stages.Prior approaches described in the introduction often address only one efficiency dimension or stage.Source: §1 · p. 2
  • Converting half the attention heads to streaming heads and fusing them with standard attention in GPU kernels yields up to 1.7× measured speedup.The streaming heads use Λ-shaped masks in both prefilling and decoding.Source: §1 · p. 2
  • A query-centric selector preserves long-context capabilities with a constant KV-token budget (e.g., 4096) and cuts page-selection overhead by 4× through reuse.The selector identifies important KV pages for each query token and reuses selection results across tokens.Source: §1 · p. 2
  • Static and dynamic sparsity are orthogonal and, when unified with KV-cache quantization in one GPU kernel, provide compounded decoding-attention efficiency benefits.The paper presents these optimizations as compatible rather than mutually exclusive.Source: §1 · p. 2
  • Up to 2.9× prefilling speedup and 1.3×–2.1× average decoding speedup over vLLM, while preserving long-context capabilities.Benchmarks span three long-sequence models and context lengths up to 512k tokens.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

The background describes LLM inference, attention complexity, and paged KV-cache management. The motivation explains why long-sequence serving needs attention optimizations that skip whole KV blocks and complement quantization.

2.1 Background

  • Attention complexity is O(N(S + N)HD): quadratic in sequence length during prefilling and linear during decoding.For long contexts, attention bounds both stages.Source: §2.1 · p. 3
  • PagedAttention stores KV caches in fixed-size pages and uses a block table for indirect retrieval, reducing waste and fragmentation from variable sequence lengths.Pages typically hold 16 to 64 consecutive tokens.Source: §2.1 · p. 3

2.2 Motivation

  • For Llama-3-8B at batch size 1, attention accounts for at least 50% of runtime above 64k tokens, rising to 75% at 128k.The profile is measured on an A100 GPU.Source: §2.2 · p. 3, Figure 2 · p. 3
  • GPU attention processes KV-token blocks sequentially; skipping work inside a block gives little speedup because warp lockstep makes faster threads wait.Reducing sequential iterations along the KV dimension motivates block-sparse attention.Source: §2.2 · p. 3, Figure 3 · p. 3
  • KV-cache quantization and block sparsity are orthogonal: quantization reduces each iteration’s runtime, while sparsity reduces the number of iterations.The distinction is especially relevant because decoding is memory-bound.Source: §2.2 · p. 3

3 LSERVE: LONG-SEQUENCE SERVING WITH UNIFIED SPARSE ATTENTION

LServe unifies static and dynamic sparsity in block-sparse attention for prefilling and decoding. Its design combines streaming heads, query-driven KV-page selection, and kernel support intended to preserve accuracy while reducing computation and selection overhead.

3.1 Unified Block Sparse Attention

  • Block-sparse attention skips whole tiles, while streaming and dynamic page sparsity provide complementary patterns for prefilling and decoding.Streaming attention uses a fixed pattern; page sparsity selects pages dynamically and bounds decoding complexity to a constant number of KV tokens per query.Source: §3.1 · p. 4

3.2 LServe System Overview

  • The system uses separate KV paging systems for streaming and dense heads, with fused sparse attention in prefilling and selected-page loading for decoding.The overview omits normalization layers and residual connections.Source: Figure 5 · p. 5

3.3 Prefilling Stage: Sparsity Determination

  • Head gates and a sparsity-quantile threshold classify attention heads as retrieval or streaming heads, with a 50% target assigning half to each group.The threshold is the median gate value when target sparsity is 50%.Source: §3.3 · p. 5

3.4 Prefilling Stage: Kernel Implementation

  • An iterator-based abstraction loops only over blocks requiring computation, computing offsets from successive iterator positions to skip unnecessary blocks.For fixed streaming patterns, iterators are set outside the attention kernel.Source: §3.4 · p. 5

3.5.1 Challenge: the Page Size Dilemma; 3.5.2 Hierarchical Paging: Mitigating the accuracy-efficiency tradeoff

  • Larger KV pages suit bandwidth utilization but impair query-aware selection, so hierarchical paging estimates importance on logical pages while retaining physical-page memory layout.Logical pages use channel-wise key minima and maxima as representative vectors; physical-page importance is the maximum score among their logical pages.Source: §3.5.1 · p. 6, §3.5.2 · p. 6

3.5.3 Reducing sparse attention overheads with locality

  • Although scattered important logical pages can require selecting more physical-page tokens, spatial locality clusters salient pages, preserving accuracy at the same token budget; temporal locality supports reusing selections across queries.The selector runs at the start of each predefined chunk, and later tokens in that chunk reuse its page-selection results.Source: §3.5.3 · pp. 6–7
  • When history exceeds 64K tokens, the naïve page selector becomes a bottleneck, while reusable page selection alleviates the problem.The method activates the selector at the beginning of predefined chunks and reuses its results for consecutive tokens.Source: §3.5.3 · p. 7

3.6 Decoding Stage: Kernel Implementation

  • A two-level index maps GPU iteration positions to KV-cache token positions, enabling one decoding kernel to support dynamic page selection and streaming heads.Streaming heads use an index table containing only sink and local pages.Source: §3.6 · p. 7

4 EVALUATION

LServe preserves accuracy across long-context and reasoning evaluations while improving prefilling and decoding efficiency. It also outperforms Quest on both stages in the tested comparison.

4.1 Evaluation Setup

  • Experiments use Llama-3-8B, Llama-2-7B, Minitron-4B, and Gradient, primarily on 8 A100 GPUs; TTFT and per-token latency measure prefilling and decoding.The study also evaluates some workloads on a single L40S GPU.Source: §4.1 · p. 8

4.2 End-to-end Accuracy

  • LServe preserves dense-baseline accuracy across LongBench, Needle-in-a-Haystack, RULER, AIME2024, and MATH500, including complex reasoning tasks.The default configuration converts half of the heads to streaming heads and uses a 4096-token dynamic-sparsity budget.Source: §4.2 · p. 8, Table 2 · p. 8, Figure 9 · p. 8

4.3 End-to-end Efficiency

  • On Llama-3-8B and Minitron-4B, LServe averages 1.5× speedup over vLLM; on Llama-2-7B it is more than 2.0× faster than baselines on average.On L40S, it achieves up to 1.7× speedup over vLLM.Source: Figure 10 · p. 9, §4.3 · p. 9
  • On Llama-2-7B, LServe achieves an average of 1.8× higher prefilling throughput than vLLM.The evaluation compares prefilling speed across sequence lengths and also activates MInference dynamic sparsity beyond 128K.Source: §4.3 · p. 9

4.4 End-to-End Comparison with Quest

  • Against Quest, LServe achieves 1.6-2.1× speedup in prefilling and 1.3-1.5× in decoding across sequence lengths.The comparison uses Llama-2-7B because Quest does not support GQA models.Source: Table 5 · p. 9, §4.4 · p. 9

5 ANALYSIS

The analysis measures kernel and end-to-end gains, tests hierarchical paging and page-selection reuse, and compares static and dynamic decoding sparsity across settings.

5.1 Prefilling Stage Sparse Attention Kernel

  • At the same sparsity level, LServe’s prefilling attention kernel achieves 1.3× speedup over MInference.The paper defines Oracle as the theoretical upper-bound speedup ratio based on sparsity.Source: Figure 12 · p. 10, §5.1 · p. 10

5.2 Effectiveness of Hierarchical Paging

  • With page size 64 and the same token budget, hierarchical paging matches the accuracy of token-granularity-16 pruning while decoupling pruning granularity from KV memory layout.The evaluation uses Needle-in-a-Haystack; hierarchical paging maintains long-context capability without increasing the token budget.Source: Figure 13 · p. 10, §5.2 · p. 10

5.3 Mitigating Page Selection Overhead

  • At 128K with a 4K-token budget, page selection takes 0.24 ms versus 0.12 ms for the attention kernel; reuse cuts selection overhead by 4× at interval 4.No significant performance degradation appears until the reuse interval exceeds 8, and the reusable selector preserves long-context accuracy.Source: Figure 14 · p. 10, §5.3 · p. 10, Table 6 · p. 10
  • A single min-max context-pooling kernel takes under 1 ms, compared with approximately 17 seconds for prefilling at 128K context, making pooling overhead negligible.Source: §5.3 · p. 10

5.4 Sparse Attention Kernel for Decoding Stage

  • Converting 50% of heads to streaming heads yields 1.3-1.7× speedup across input lengths; dynamic sparsity with a fixed 4096-token KV budget makes decoding-attention complexity constant.Static sparsity helps more at shorter contexts, while dynamic sparsity offers greater benefits at longer contexts.Source: §5.4 · p. 10, Figure 15 · p. 11

5.5 End-to-End Speedup Breakdown

  • At 256K, dynamic sparsity yields 7.7× generation-latency speedup; Figure 16 reports up to 4.5× end-to-end dynamic speedup, while static sparsity reaches 1.7× over dense.Offline profiling avoids slowdowns from dynamic sparsity at shorter contexts.Source: Figure 16 · p. 11, §5.5 · p. 11

6 RELATED WORK

The related work surveys LLM serving systems and sparse-attention methods, from cache and scheduling approaches to retrieval and query-aware sparsity.

LLM Serving Systems

Sparse Attention

  • Sparse-attention work spans local, global, and random masks [Zaheer et al., 2020], cache eviction [Xiao et al., 2023; Oren et al., 2024], and query-aware methods such as Quest [Tang et al., 2024].Other approaches include retrieval or local heads, block-level gates, and profiling or compression-based selection methods.Source: §6 · p. 11

7 CONCLUSION

LServe combines unified block-sparse attention with static and query-aware dynamic sparsity, reporting speedups while preserving long-context and reasoning capabilities.

7 CONCLUSION

  • LServe reports average decoding speedups of 1.3×-2.1× and up to 2.9× prefilling speedup while preserving long-context document and complex-reasoning capabilities.The conclusion describes static and dynamic sparsity as orthogonal and combinable with minimal accuracy impact.Source: §7 · p. 11

A.1 Abstract

The artifact packages the scripts and dependencies needed to reproduce the paper’s crucial experiments, with a pre-built Docker image to simplify setup.

A.1 Abstract

  • The artifact provides scripts and dependencies to reproduce the paper’s crucial experiments.A pre-built Docker image is also provided to simplify environment setup.Source: §A.1 · p. 15
  • Running the artifact requires an x86-64 host with at least one NVIDIA A100 or L40S GPU.Source: §A.1 · p. 15
  • The artifact includes a pre-built Docker image for environment setup.Source: §A.1 · p. 15

A.2 Artifact check-list (meta-information)

The artifact supports accuracy evaluation and throughput benchmarking for LServe and baseline systems, and reports the required setup, outputs, and resource estimates.

A.2 Artifact check-list (meta-information)

  • The evaluation model is a quantized Llama-3-8B, and the datasets are included in the Docker image.The checklist also names a completed Docker compilation.Source: §A.2 · p. 15
  • Experiments use NVIDIA GPUs, with some data preprocessing on the host CPU, and require an x86-64 host with an A100 or L40S GPU.The checklist recommends an A100; it also lists a GPU-compatible Docker runtime and Docker workflow.Source: §A.2 · p. 15
  • The artifact benchmarks LServe and vLLM throughput and evaluates LServe accuracy, producing accuracy numbers and generation throughput in tokens per second.Source: §A.2 · p. 15
  • The artifact is publicly available under Apache License 2.0, with data licensed under MIT, and is archived at the listed DOI.The checklist estimates 128G disk space, about one hour for setup, and roughly three hours for benchmarks, depending on conditions.Source: §A.2 · p. 15

A.3.1 How delivered

The artifact is distributed as a Docker image and provides instructions for setting up the environment, running LongBench accuracy evaluation, and benchmarking throughput against vLLM. Reference evaluation numbers are provided, with machine-dependent timing and generation-dependent accuracy variation noted.

A.3.1 How delivered

  • The artifact is delivered as a pre-built Docker image containing LServe, vLLM, and dependencies.Source: §A.3.1 · p. 15

A.3.2 Hardware dependencies; A.3.3 Software dependencies

A.3.4 Data sets

  • LongBench datasets including 2wikimqa, dureader, and hotpotqa are publicly available and included in the Docker image.Source: §A.3.4 · p. 15

A.4 Installation

  • Users are recommended to install the environment and run experiments within the GPU-supported Docker container.Source: §A.4 · p. 15

A.5.1 LServe Accuracy Evaluation

  • Push-button scripts evaluate LServe and baseline accuracy on LongBench and save prediction results to a result file.Source: §A.5.1 · p. 15

A.5.2 Throughput Benchmark

  • Throughput instructions measure LServe and vLLM generation throughput and save results to CSV files.Source: §A.5.2 · pp. 15–16

A.6 Evaluation and expected result

  • Absolute speed measurements may vary across machine conditions, while relative acceleration ratios are expected to remain consistent.Accuracy results may also deviate slightly from reference numbers because LLM generation is random.Source: §A.6 · p. 16
Loading 2502.14866v2…