TL;DR
This paper introduces Tetris, a novel LLM serving system that tackles the challenge of efficiently handling long-context requests by employing "Chunkwise Dynamic Sequence Parallelism" (CDSP). CDSP fine-grains parallelism allocation within a single request, allowing for dynamic adjustment of resources across different parts of the input, leading to significant improvements in latency and throughput compared to existing methods.
What Problem Does This Paper Address?
Large Language Models (LLMs) are increasingly being used for tasks requiring long contexts (e.g., summarizing lengthy documents, analyzing codebases). This necessitates LLM serving systems that can efficiently process these long sequences. Existing systems often struggle with this due to:
- Rigid Parallelism: Sequence Parallelism (SP), a common technique for handling long contexts, is often applied uniformly across all tokens of a request or statically configured for the entire cluster. This inflexibility fails to adapt to the varying computational demands of different parts of a long sequence (e.g., the initial prompt vs. later generated tokens) or the diverse needs of different requests.
- Latency Degradation: Static or coarse-grained SP can lead to either underutilization of resources (if SP is too large for short segments) or excessive latency (if SP is too small for long segments), particularly impacting the time-to-first-token (TTFT) and time-between-tokens (TBT) metrics crucial for interactive services.
- Resource Fragmentation: In dynamic environments with varying request lengths, static parallelism can lead to fragmented resources that are difficult to utilize efficiently.
Methods
The paper proposes Chunkwise Dynamic Sequence Parallelism (CDSP) as the core innovation. Instead of applying a single SP size to an entire request, CDSP:
- Divides Requests into Chunks: Each request's prompt is broken down into smaller segments or "chunks."
- Dynamic SP Allocation per Chunk: Different SP sizes are assigned to different chunks. The strategy is to use smaller SP sizes for earlier chunks to allow for earlier execution and leverage available resources, and progressively larger SP sizes for later chunks to accommodate their higher computational demands and reduce latency. This is likened to filling Tetris blocks.
- Tetris System: The authors build a serving system called Tetris around CDSP. Key components include:
- Prefill-Decoding Disaggregation: Separating prefill (processing the initial prompt) and decoding (generating tokens sequentially) stages onto different sets of model instances to optimize resource allocation for each.
- Fine-grained Scheduling: A load-aware scheduler that dynamically determines the optimal chunking strategy and SP allocation based on real-time system load and request arrival pressure. This involves a latency model to predict performance and a recursive search for the best chunking plan.
- Optimized Cache Management: Techniques to efficiently transfer KV cache data between prefill and decoding instances, including a handshake mechanism to prevent backend starvation and layer-wise overlap to hide cache balancing latency.
Datasets
Not explicitly discussed in terms of training datasets. For evaluation, the authors used real-world request traces collected from a production LLM service, categorized into:
- Short: Sequence length from 4k to 95k, average 23.6k.
- Medium: Sequence length from 8k to 142k, average 32.8k.
- Long: Sequence length from 16k to 190k, average 50.1k.
The models used for evaluation were LLaMA3-8B and LLaMA3-70B.
Key Insights and Ideas
- The "Tetris" Analogy: The core idea of fitting different SP sizes to different "chunks" of a request, like fitting Tetris blocks, is a powerful way to visualize and understand how to optimize resource utilization and latency.
- Prefill vs. Decoding Needs: Different stages of LLM inference have fundamentally different parallelism requirements. Prefill benefits from more flexible SP allocation, while decoding benefits from larger Tensor Parallelism (TP) for lower latency. Tetris explicitly addresses this by disaggregating these stages.
- Dynamic Load Awareness is Crucial: Simply applying the "best" SP size for a request in isolation isn't enough. The system needs to be aware of overall system load and request arrival rates to make optimal scheduling decisions, preventing over-provisioning or under-provisioning.
- Fine-grained Control Unlocks Performance: Moving beyond request-level or static SP allocation to chunk-level dynamic allocation is key to achieving significant gains in both latency and throughput for long-context LLMs.
Key Results
Tetris demonstrated substantial improvements over state-of-the-art baselines (Fixed SP, LoongServe, LoongServe Disaggregated):
- Reduced TTFT: Up to 4.35x lower time-to-first-token (TTFT) under maximum sustainable loads.
- Reduced TBT: Median time-between-tokens (TBT) reduced by up to 40.1%.
- Increased Capacity: Maximum request capacity increased by up to 45%.
- Improved Throughput: Throughput increased by 1.24-3.38x for LLaMA3-8B and 1.15-1.81x for LLaMA3-70B.
- Efficient Overhead: CDSP's cache balancing and handshake mechanisms introduced minimal overhead (e.g., cache transfer overhead averaged 2.1%).
Limitations and Future Work
- Latency Model Accuracy: The performance of the scheduling heavily relies on the accuracy of the latency model. While shown to be effective, its accuracy might degrade with significant changes in hardware or model architecture.
- Simulator-based Profiling: The improvement rate for the scheduler is determined offline via simulation. While robust, adapting to rapid, unforeseen changes in request patterns might require more dynamic online adaptation.
- Future Work: The paper suggests exploring more sophisticated scheduling strategies and potentially extending CDSP to other parallelism techniques beyond sequence parallelism. Further investigation into optimizing the trade-off between TTFT and TBT across a wider range of workloads and model sizes would also be valuable.
Summary updated