Source-linked AI summary
VPP: Virtual Pipeline Parallelism for Efficient Chunked Prefill in Long-Context LLM Inference
Yan Shi, Xiaochao Wang, Jingchun Gao, Jintao Luo, Xinyi Zhou, Feng Liu, Kui Luo, Xushi Li, Xinjie Guo, Liangjun Feng
TL;DR
Long-context chunked prefill suffers from unequal fixed-chunk latency and pipeline bubbles, while dynamic resizing can incur unfavorable overhead on long sequences. VPP keeps chunks fixed and uses virtual-stage scheduling plus communication and packing optimizations. Across three MoE models, it improves throughput over DCPP on long and mixed workloads and sharply reduces bubbles on a 512K-token workload.
Problem
Equal-size prefill chunks incur increasing latency as prefix KV caches grow, while DCPP’s resizing overhead can outweigh its load-balancing benefit on long sequences.
Method
VPP keeps chunk sizes fixed and reshapes the pipeline with V-shaped virtual stages, asynchronous communication reordering, and pipelined packing.
Results
VPP improves throughput by up to 13.1% over DCPP on long workloads and 6.7% on mixed workloads, while preserving short-sequence performance.
Takeaways & Limitations
On a 512K-token DeepSeek-V3.1 prefill workload, VPP reduces the pipeline bubble ratio from 6.4% to 0.1%, a 98.0% reduction versus DCPP.
Takeaways & Limitations
VPP exposes 7.95 s more communication on the critical path than DCPP, mainly from additional AllGather auxiliary overhead.
Abstract
from arXiv · showhide
Chunked prefill pipeline parallelism (CPP) is a key technique for LLM inference. However, equal-size chunks exhibit imbalanced latency, as later chunks attend longer prefix KV caches and incur higher attention costs, leading to pipeline bubbles. Existing approaches mitigate this imbalance through dynamic chunk resizing (Dynamic CPP, DCPP), but our measurements show that this trades scheduling overhead for load balancing, which becomes unfavorable on long sequences. In this study, we propose Virtual Pipeline Parallelism (VPP), which keeps chunk sizes fixed and optimizes the pipeline layout through virtual stages. A V-shaped virtual-stage traversal overlaps each chunk's expensive middle stages with the lighter head and tail stages of its neighbors, while asynchronous communication and pipelined packing further reduce communication stalls and cross-request drain bubbles. We implement VPP in vLLM-Ascend and evaluate it on three MoE-based LLMs with sequences up to 1M tokens on 16 Ascend 910C NPUs. VPP improves throughput by up to 13.1% over DCPP on long sequences and 6.7% on mixed workloads, while preserving performance on short sequences. On a 512K-token DeepSeek-V3.1 prefill workload, VPP reduces the pipeline bubble ratio from 6.4% to 0.1%, achieving a 98.0% reduction compared with DCPP.
1 INTRODUCTION
Long and variable contexts make LLM serving vulnerable to blocking, utilization loss, and memory pressure, especially during compute-intensive prefill. VPP addresses unequal fixed-chunk latency without resizing by reshaping pipeline stages and overlapping communication and drain periods.
- Long and variable contexts increase head-of-line blocking, accelerator underutilization, and memory pressure in LLM serving.
- Chunked prefill interleaves prompt chunks with decoding and other requests, mitigating head-of-line blocking and improving utilization.
- DCPP dynamically resizes chunks to balance execution time, but its fragmentation overhead can outweigh bubble-reduction benefits as sequences grow.
- VPP keeps chunk sizes fixed and uses V-shaped virtual-stage traversal to pair heavy middle stages with lighter neighboring stages.
- VPP additionally uses asynchronous communication and pipelined packing to reduce communication stalls and cross-request drain bubbles.
- VPP evaluation on three MoE models covers short, long, and mixed workloads using vLLM-Ascend.
- VPP improves throughput by up to 13.1% on long workloads and 6.7% on mixed workloads over DCPP while preserving short-sequence performance.
2 BACKGROUND
Transformer inference combines causal self-attention, feed-forward computation, and distinct prefill and decode phases. Pipeline parallelism and chunked prefill distribute this work, but unequal chunk costs create execution-imbalance bubbles that DCPP seeks to reduce dynamically.
- Transformer Architecture: Self-attention projects inputs into queries, keys, and values, while causal attention restricts each token to itself and preceding tokens.
- Transformer Architecture: Self-attention computation scales as O(L^2d), making long contexts increasingly expensive.
- Inference Phases: Prefill processes prompt tokens in parallel and populates the KV cache, whereas decode generates tokens autoregressively and accesses that cache.
- Inference Phases: Long prompts can increase TTFT and interfere with concurrent requests because prefill is compute-intensive.
- Parallelism: Pipeline parallelism partitions layers across devices and transfers intermediate activations between neighboring stages.
- Pipeline Parallelism: Pipeline bubbles arise from fill and drain dependencies or unequal processing times across chunks and micro-batches.
- Chunked Prefill Pipeline Parallelism: Chunked prefill splits long prompts into scheduling units that can be interleaved with decoding, while DCPP changes chunk boundaries to equalize execution times.
3 RELATED WORK
Prior work reduces pipeline bubbles through microbatching, flexible scheduling, stage partitioning, computation reordering, and dynamic sequence or chunk partitioning. Serving systems increasingly use runtime profiling, while some approaches do not explicitly model context-dependent attention costs.
- Pipeline Scheduling: GPipe introduced microbatching, while PipeDream, Hanayo, and Zero Bubble Pipeline Parallelism explored flexible schedules, stage partitioning, and computation reordering.
- Serving Load Balancing: gLLM balances computation primarily through token throttling without explicitly modeling context-dependent attention costs.
- Dynamic Partitioning: TeraPipe and Seq1F1B dynamically partition sequences or adjust boundaries to balance execution time.
- Dynamic Partitioning: SGLang and vLLM-Ascend use runtime profiling and online calibration to predict chunk latency and adapt chunk boundaries.
4 MOTIVATION
DCPP improves CPP on shorter long-context workloads but loses its advantage at 512K tokens. The reversal reflects growing invocation and fragmentation costs that outweigh its bubble-reduction savings.
- Experimental Setup: DCPP is evaluated against CPP on DeepSeek-V3.1 sequences from 64K to 512K using multiple chunk-size budgets.
- End-to-End Comparison: DCPP outperforms CPP by 1.6–3.6% in throughput and TTFT on 64K–256K sequences.
- End-to-End Comparison: At 512K, DCPP reverses to a 4.4% throughput loss and a 4.6% TTFT increase relative to CPP.
- Per-Chunk Scheduling: On a 128K prompt with 32K chunks, CPP exhibits approximately linear per-chunk latency growth and substantial load imbalance, while DCPP reduces bubbles through resizing.
- Cost Breakdown: At 512K, DCPP uses 97 invocations versus CPP’s 22, or 4.4× as many, while reducing bubble time by 47.0%.The bubble ratio falls from 12.5% to 6.4%, but computation time rises by 10.5% (+26.48 s).
- Interpretation: DCPP trades scheduling overhead for load-balancing gains, and fragmentation eventually outweighs bubble-reduction benefits as sequence length grows.
5 VPP: DESIGN AND IMPLEMENTATION
VPP treats fixed-size chunk latency growth as a pipeline-layout problem, using virtual stages and V-shaped traversal to balance execution. Asynchronous communication and pipelined packing further reduce communication stalls and cross-request drain bubbles.
- 5.1 VPP: V-shaped pipeline scheduling: VPP keeps chunk sizes fixed and reshapes the pipeline with virtual stages arranged in a V-shaped fold-back layout.Chunks traverse forward across the first virtual stages and backward across the remaining stages.
- 5.1 VPP: V-shaped pipeline scheduling: Near-linear latency growth lets neighboring chunks’ head and tail work fill the middle-stage execution window of a current chunk.For chunk Ck, τk−1 + τk+1 approximately equals 2τk, matching the two middle stages’ work.
- 5.1 VPP: V-shaped pipeline scheduling: VPP’s balance depends on attention-dominated execution with expert-parallel MoE; otherwise, steady-state bubbles may reappear.The design also leaves synchronous handoff stalls and a final drain bubble for subsequent optimizations.
- 5.2 VPP-Async: communication-computation overlap: VPP-Async reorders local stages so bidirectional transfers overlap with useful computation instead of remaining on the critical path.The reordering swaps the tail stage of Ck−1 with the head stage of Ck+1 once the required prefix KV cache is available.
- 5.3 VPP-Async with Pipelined Packing: cross-request bubble compression: Pipelined packing uses a request’s tail drain window to process leading chunks of the next request, reducing cross-request bubbles.Early chunks have the lowest latency and can fit into shrinking tail windows; insufficient windows still reduce the effective drain bubble.
- 5.4 Implementation: The implementation adds virtual-stage scheduling, fold-back layer assignment, and a per-batch pipeline state machine to vLLM-Ascend.Optimized attention and MoE kernels are reused without modification, with support for uneven layer partitioning and user-specified layer ranges.
6 EVALUATION
Across short, long, and mixed workloads, VPP generally matches or exceeds DCPP, with its strongest gains on long and heterogeneous workloads. Profiling attributes the gains to reduced fragmentation, fewer bubbles, improved communication overlap, and better use of idle windows, while sparse attention limits scaling at longer contexts.
- Short sequences: VPP preserves short-sequence performance, with results generally similar to DCPP across the three evaluated models.On DeepSeek, VPP’s largest advantage over DCPP reaches 10.8% at 4K chunk size.
- Long sequences: VPP improves long-sequence throughput over DCPP by 3.7%–8.7% on Qwen and 2.6%–13.1% on DeepSeek across reported context lengths.On GLM, the gain peaks at 8.5% at 64K and narrows at longer lengths.
- Mixed sequences: VPP improves mixed-workload throughput over DCPP by 0.8% on Qwen, 6.7% on DeepSeek, and 1.3%–1.6% on GLM.The mixed workload combines heterogeneous request lengths, allowing VPP to exploit fragmented idle slots.
- Source of gains: On the 512K DeepSeek-V3.1 workload, VPP reduces TTFT by 12.53% (40.36 s) versus DCPP while reducing computation time by 10.1% and noncomputing overhead by 28.1%.DCPP executes 4.8× more kernels and 4.7× more host launches, whereas VPP’s attention time is 4.96 s longer.
- Source of gains: VPP reduces the bubble ratio from 6.35% to 0.14%, a 98.04% reduction, by using V-shaped scheduling to fill idle windows with useful computation.DCPP has 18.61 s of free idle time, compared with 0.39 s for VPP.
- Source of gains: VPP increases communication overlap from 0.01 s to 32.86 s and raises the overlap ratio from 0.05% to 51.75%, despite higher exposed communication overhead.The exposed communication increase is 7.95 s, mainly due to additional AllGather auxiliary overhead.
- Ablation study: VPP-Async and pipelined packing reduce the bubble ratio from 11.0% in vanilla VPP to 8.3% and 2.4%, respectively.The improvements primarily come from reducing cross-request idle periods; pipelined packing further reduces cross-request bubble latency by 33.2%.
- Design sensitivity: A 24K chunk size performs best in most configurations because its final smaller chunk overlaps pipeline drain, while sparse attention causes VPP efficiency to degrade at longer contexts.For GLM, DSA weakens the near-linear chunk-latency scaling assumed by VPP and allows bubbles to re-emerge in later chunks.
7 CONCLUSION AND DISCUSSION
VPP keeps chunk sizes fixed while using virtual-stage layouts and communication optimizations to reduce computation imbalance, communication stalls, and cross-request drain bubbles. Across diverse MoE workloads, it improves throughput and sharply reduces pipeline bubbles, but its effectiveness depends on regular chunk-latency growth.
- VPP design: VPP keeps chunk sizes fixed and uses V-shaped stage traversal to match computation across pipeline ranks.The layout exploits approximately linear latency growth from causal attention.
- VPP design: Asynchronous communication reordering and pipelined packing reduce exposed communication stalls and cross-request drain bubbles.Pipelined packing fills otherwise idle drain periods with leading chunks from the next request.
- Performance: 13.1% throughput improvement over DCPP on long sequences and 6.7% on mixed workloads were achieved while preserving short-sequence performance.These gains were observed across three MoE models and diverse workloads on vLLM-Ascend.
- Performance: 98.0% pipeline-bubble reduction was achieved on a 512K-token DeepSeek-V3.1 prefill workload, lowering the ratio from 6.4% to 0.1%.This result is reported as a comparison with DCPP.
- Discussion and limitations: VPP's effectiveness depends on regular chunk-latency growth, while sparse attention reduces this regularity and limits achievable bubble reduction.Extending the layout to sparse-attention models and more heterogeneous scenarios remains future work.