Locality-aware Fair Scheduling in LLM Serving
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912202789748736 |
|---|---|
| author | Cao, Shiyi Wang, Yichuan Mao, Ziming Hsu, Pin-Lun Yin, Liangsheng Xia, Tian Li, Dacheng Liu, Shu Zhang, Yineng Zhou, Yang Sheng, Ying Gonzalez, Joseph Stoica, Ion |
| author_facet | Cao, Shiyi Wang, Yichuan Mao, Ziming Hsu, Pin-Lun Yin, Liangsheng Xia, Tian Li, Dacheng Liu, Shu Zhang, Yineng Zhou, Yang Sheng, Ying Gonzalez, Joseph Stoica, Ion |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14312 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Locality-aware Fair Scheduling in LLM Serving Cao, Shiyi Wang, Yichuan Mao, Ziming Hsu, Pin-Lun Yin, Liangsheng Xia, Tian Li, Dacheng Liu, Shu Zhang, Yineng Zhou, Yang Sheng, Ying Gonzalez, Joseph Stoica, Ion Distributed, Parallel, and Cluster Computing Machine Learning 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. |
| title | Locality-aware Fair Scheduling in LLM Serving |
| topic | Distributed, Parallel, and Cluster Computing Machine Learning |
| url | https://arxiv.org/abs/2501.14312 |