Fairness in Serving Large Language Models

Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E. Gonzalez, Ion Stoica

Introduction

As Large Language Models (LLMs) become foundational to modern software, the infrastructure required to serve them must evolve to handle multi-tenant environments efficiently. Researchers from UC Berkeley, Stanford, and Duke have identified a critical gap in current serving systems: the lack of a fair scheduling mechanism that maintains high resource utilization. To address this, they introduced the Virtual Token Counter (VTC), a scheduling algorithm designed for strict client isolation and optimal GPU usage, even when request lengths are unpredictable.

The Challenge of Fair LLM Serving

Traditional scheduling methods like First-Come-First-Serve (FCFS) or Request-Per-Minute (RPM) rate limits are insufficient for LLMs. FCFS suffers from the "noisy neighbor" problem, where a single client sending long requests can monopolize the GPU, leading to increased latency for others. Conversely, RPM limits are often non-work-conserving; they may throttle clients even when the GPU has idle capacity, leading to wasted resources.

Furthermore, LLM serving presents unique technical challenges. Unlike networking packets, the final length of an LLM response is unknown until generation is complete. Additionally, the computational cost of tokens is non-uniform. The "prefill" phase (processing the input prompt) is highly parallelizable, while the "decode" phase (generating output tokens) is sequential and more expensive per token.

Throughput vs Request Length

The Virtual Token Counter (VTC) Algorithm

VTC addresses these issues by operating at a token-level granularity. It integrates with continuous batching—the standard technique for overlapping multiple LLM requests—to ensure that compute resources are distributed fairly among clients.

Key Architectural Components

The VTC system consists of a request queue, a virtual token counter for each client, and an execution engine.

VTC Architecture
  • Token-Level Granularity: VTC uses a weighted cost function to price input and output tokens differently, reflecting their actual compute costs.
  • The Counter Lift: To prevent long-silent clients from suddenly starving others by "catching up" on their accumulated fair share, VTC implements a "lift" mechanism. When a client returns to the queue, their counter is adjusted to the level of currently active clients.
  • Priority Scheduling: The scheduler prioritizes requests from clients with the lowest virtual token count, ensuring that those who have received the least service are served next.

Evaluation and Results

The researchers evaluated VTC using both synthetic workloads (to test edge cases like bursty traffic) and real-world traces from the LMSYS Chatbot Arena. The results demonstrate that VTC significantly outperforms existing baselines:

  • Strict Isolation: VTC acts as a latency shield. Even when one client floods the system with requests, the response times for other clients remain stable.
  • Improved Fairness: In real-world trace evaluations, VTC reduced the "Maximum Service Difference"—a metric for unfairness—by more than 2x compared to FCFS.
  • High Utilization: Unlike RPM-based systems, VTC is work-conserving. It achieved higher total throughput by utilizing spare GPU capacity whenever available.
  • Predictive Enhancements: A variant called VTC (predict) uses historical request data to estimate future costs, further smoothing out service discrepancies and approaching the performance of an "oracle" scheduler.

Conclusion

VTC provides a robust framework for fair multi-tenant LLM serving. By moving from request-level to token-level scheduling and providing mathematical guarantees on service distribution, it ensures that LLM providers can offer reliable performance to all users. Future work includes extending VTC to distributed multi-GPU clusters and integrating it with dynamic auto-scaling systems.

Summary updated

BibTeX
@inproceedings{sheng2024fairness,
  author = {Ying Sheng and Shiyi Cao and Dacheng Li and Banghua Zhu and Zhuohan Li and Danyang Zhuo and Joseph E. Gonzalez and Ion Stoica},
  title = {{Fairness in Serving Large Language Models}},
  booktitle = {OSDI},
  year = {2024},
  url = {https://openreview.net/forum?id=LJ8EhA4fM6},
}
Figure