Locality-aware Fair Scheduling in LLM Serving

• URL: http://arxiv.org/abs/2501.14312v1
• Date: Fri, 24 Jan 2025 08:12:47 GMT
• Title: Locality-aware Fair Scheduling in LLM Serving
• Authors: Shiyi Cao, Yichuan Wang, Ziming Mao, Pin-Lun Hsu, Liangsheng Yin, Tian Xia, Dacheng Li, Shu Liu, Yineng Zhang, Yang Zhou, Ying Sheng, Joseph Gonzalez, Ion Stoica,
• Abstract summary: Large language model (LLM) inference workload dominates a wide variety of modern AI applications. Balancing fairness and efficiency is critical for managing diverse client workloads with varying prefix patterns. This paper introduces the first locality-aware fair scheduling algorithm, Deficit Longest Prefix Match (DLPM)
• Score: 28.707749238946253
• License:
• Abstract: Large language model (LLM) inference workload dominates a wide variety of modern AI applications, ranging from multi-turn conversation to document analysis. Balancing fairness and efficiency is critical for managing diverse client workloads with varying prefix patterns. Unfortunately, existing fair scheduling algorithms for LLM serving, such as Virtual Token Counter (VTC), fail to take prefix locality into consideration and thus suffer from poor performance. On the other hand, locality-aware scheduling algorithms in existing LLM serving frameworks tend to maximize the prefix cache hit rate without considering fair sharing among clients. This paper introduces the first locality-aware fair scheduling algorithm, Deficit Longest Prefix Match (DLPM), which can maintain a high degree of prefix locality with a fairness guarantee. We also introduce a novel algorithm, Double Deficit LPM (D$^2$LPM), extending DLPM for the distributed setup that can find a balance point among fairness, locality, and load-balancing. Our extensive evaluation demonstrates the superior performance of DLPM and D$^2$LPM in ensuring fairness while maintaining high throughput (up to 2.87$\times$ higher than VTC) and low per-client (up to 7.18$\times$ lower than state-of-the-art distributed LLM serving system) latency.

Related papers

• Efficiently Serving Large Multimodal Models Using EPD Disaggregation [24.05805398635414]
  We introduce Encode-Prefill-Decode Disaggregation, a novel framework that separates the encoding, prefill, and decode stages onto dedicated resources. We show substantial gains in memory efficiency (up to 15$times$ less utilization), batch sizes (up to 22$times$ larger), 10$times$ more images/request, and 2.2$times$ larger KV caches.
  arXiv  Detail & Related papers  (2024-12-25T10:11:31Z)
• Progressive Mixed-Precision Decoding for Efficient LLM Inference [49.05448842542558]
  We introduce Progressive Mixed-Precision Decoding (PMPD) to address the memory-boundedness of decoding. PMPD achieves 1.4$-$12.2$times$ speedup in matrix-vector multiplications over fp16 models. Our approach delivers a throughput gain of 3.8$-$8.0$times$ over fp16 models and up to 1.54$times$ over uniform quantization approaches.
  arXiv  Detail & Related papers  (2024-10-17T11:46:33Z)
• VinePPO: Unlocking RL Potential For LLM Reasoning Through Refined Credit Assignment [66.80143024475635]
  We propose VinePPO, a straightforward approach to compute unbiased Monte Carlo-based estimates. We show that VinePPO consistently outperforms PPO and other RL-free baselines across MATH and GSM8K datasets.
  arXiv  Detail & Related papers  (2024-10-02T15:49:30Z)
• FedBiOT: LLM Local Fine-tuning in Federated Learning without Full Model [48.33280660752336]
  Large language models (LLMs) show amazing performance on many domain-specific tasks after fine-tuning with some appropriate data. Many domain-specific data are privately distributed across multiple owners. We introduce FedBiOT, a resource-efficient LLM fine-tuning approach to federated learning.
  arXiv  Detail & Related papers  (2024-06-25T16:45:47Z)
• Preble: Efficient Distributed Prompt Scheduling for LLM Serving [8.706905652975554]
  This paper proposes Preble, the first distributed LLM serving platform that targets and optimize for prompt sharing. We designed a distributed scheduling system that co-optimizes KV state reuse and computation load-balancing with a new scheduling algorithm and a hierarchical scheduling mechanism. Our evaluation of Preble with real workloads and request arrival patterns on two open-source LLMs shows that Preble outperforms the SOTA serving systems by 1.5X to 14.5X on average latency and 2X to 10X on p99 latency.
  arXiv  Detail & Related papers  (2024-05-08T06:30:58Z)
• CALF: Aligning LLMs for Time Series Forecasting via Cross-modal Fine-Tuning [59.88924847995279]
  We propose a novel Cross-Modal LLM Fine-Tuning (CALF) framework for MTSF. To reduce the distribution discrepancy, we develop the cross-modal match module. CALF establishes state-of-the-art performance for both long-term and short-term forecasting tasks.
  arXiv  Detail & Related papers  (2024-03-12T04:04:38Z)
• HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM Inference [68.59839755875252]
  HiRE comprises of two novel components: (i) a compression scheme to cheaply predict top-$k$ rows/columns with high recall, followed by full computation restricted to the predicted subset, and (ii) DA-TOP-$k$: an efficient multi-device approximate top-$k$ operator. We demonstrate that on a one billion parameter model, HiRE applied to both the softmax as well as feedforward layers, achieves almost matching pretraining and downstream accuracy, and speeds up inference latency by $1.47times$ on a single TPUv5e device.
  arXiv  Detail & Related papers  (2024-02-14T18:04:36Z)
• SpotServe: Serving Generative Large Language Models on Preemptible Instances [64.18638174004151]
  SpotServe is the first distributed large language models serving system on preemptible instances. We show that SpotServe can reduce the P99 tail latency by 2.4 - 9.1x compared with the best existing LLM serving systems. We also show that SpotServe can leverage the price advantage of preemptive instances, saving 54% monetary cost compared with only using on-demand instances.
  arXiv  Detail & Related papers  (2023-11-27T06:31:17Z)
• Cache me if you Can: an Online Cost-aware Teacher-Student framework to Reduce the Calls to Large Language Models [13.799197575126442]
  Small and medium-sized enterprises (SMEs) cannot afford the cost of creating large task-specific training datasets. Third-party services that allow them to prompt Large Language Models currently require a payment per call. We propose a framework that allows reducing the calls to LLMs by caching previous responses and using them to train a local inexpensive model.
  arXiv  Detail & Related papers  (2023-10-20T10:05:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.