PaperlayerView exact revision on arXiv

Source-linked AI summary

Fairness in Serving Large Language Models

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

arXiv:2401.00588v2cs.AIcs.LGcs.PF

TL;DR

Request-rate limits can protect clients from overload but waste capacity when demand is low, and LLM serving adds uncertainty from variable costs and request lengths. The paper defines token-based service fairness and proposes VTC, a scheduler integrated with continuous batching. It proves a fairness bound within 2× of optimal and reports fair, work-conserving behavior in evaluation.

  • Problem

    Request-rate limits can waste resources when capacity is available, while unknown output lengths, unequal token costs, and variable server capacity complicate fair LLM scheduling.

    Source: §1 · p. 1, §2.3 · p. 4

  • Method

    VTC tracks service for each client and prioritizes those with the least service, updating counters at token-level granularity within continuous batching.

    Source: §1 · p. 2

  • Results

    Within 2× of the optimal bound, VTC's fairness guarantee is proved, and evaluations confirm that the algorithms are fair and work-conserving.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper applies fair sharing to LLM serving at token granularity to provide performance isolation across clients sharing a server.

    Source: §7 · p. 14

    Tightening the fairness bound by restricting each client's running-batch memory may compromise work conservation, creating a trade-off between the two.

    Source: §4.1.1 · p. 7

Abstract

from arXiv · show

High-demand LLM inference services (e.g., ChatGPT and BARD) support a wide range of requests from short chat conversations to long document reading. To ensure that all client requests are processed fairly, most major LLM inference services have request rate limits, to ensure that no client can dominate the request queue. However, this rudimentary notion of fairness also results in under-utilization of the resources and poor client experience when there is spare capacity. While there is a rich literature on fair scheduling, serving LLMs presents new challenges due to their unpredictable request lengths and their unique batching characteristics on parallel accelerators. This paper introduces the definition of LLM serving fairness based on a cost function that accounts for the number of input and output tokens processed. To achieve fairness in serving, we propose a novel scheduling algorithm, the Virtual Token Counter (VTC), a fair scheduler based on the continuous batching mechanism. We prove a 2x tight upper bound on the service difference between two backlogged clients, adhering to the requirement of work-conserving. Through extensive experiments, we demonstrate the superior performance of VTC in ensuring fairness, especially in contrast to other baseline methods, which exhibit shortcomings under various conditions. The reproducible code is available at https://github.com/Ying1123/VTC-artifact

1 Introduction

LLM serving must balance client isolation with efficient resource use: request-per-minute limits can waste capacity, while request lengths and token costs vary. The paper defines fairness around token-level service and proposes VTC, a fair scheduler designed for continuous batching.

1 Introduction

  • Request-per-minute limits can restrict high-rate clients even when the system is underutilized, wasting scarce GPU resources.The paper seeks a solution that provides both isolation and high resource utilization.Source: §1 · p. 1
  • Fairness should be measured at token rather than request granularity because requests can consume very different resources.The paper illustrates this with requests of 2K versus 200 tokens, counting both input and output tokens.Source: §1 · pp. 1–2
  • LLM serving complicates fair scheduling through unknown output lengths, variable token costs, and changing server capacity.Longer input sequences can constrain batch size and reduce processing rate.Source: §1 · p. 2
  • VTC tracks service received per client and prioritizes clients with the least service, updating counters at token-level granularity.The scheduler is designed to integrate with continuous batching and adapt to different service cost functions.Source: §1 · p. 2
  • The paper presents VTC as fair and work-conserving, with a fairness bound within 2× of the optimal bound.The introduction identifies fair LLM serving, the VTC algorithm, and its fairness proof as contributions.Source: §1 · p. 2

2 Background

LLM serving uses concurrent request streams and continuous batching, while existing fairness approaches draw on rate limits and fair queueing. The paper identifies why these approaches do not transfer directly: serving has variable token costs and capacity, and output lengths are unknown before completion.

2.1 Large Language Models Serving

  • Continuous batching enqueues arriving requests and adds queued requests when execution finishes others, supporting concurrent processing for throughput.The scheduling policy can be integrated into the request-selection function.Source: §2.1 · p. 3

2.2 Existing Fairness Approaches

  • Rate limits can leave capacity underused, while fair-queueing methods schedule based on service tags or virtual time.Fair-queueing approaches generally depend on knowing packet lengths in advance; CFS schedules the task with the smallest vruntime.Source: §2.2 · pp. 3–4

2.3 Challenges

  • LLM fairness needs a request-cost definition because input and output tokens have different processing costs.Input tokens can be processed in parallel, whereas output tokens are generated sequentially.Source: §2.3 · p. 4
  • Unknown output lengths prevent direct adaptation of SFQ and DRR, while variable request mixes make server capacity fluctuate.The paper argues for token-granularity fairness because frequent preemption is not possible.Source: §2.3 · p. 4

3 Definition of Fairness in LLM Serving

The paper defines LLM serving fairness using a measure of service that can account for input and output token costs. It then frames fairness around backlogged and non-backlogged clients, alongside work conservation.

3 Definition of Fairness in LLM Serving

  • The algorithm does not consider preemption.The paper leaves investigation of preemption as future work.Source: §3 · p. 4

3.1 Measurement of Service

  • Service can be measured by input and output tokens, FLOPs, or a weighted combination of input and output tokens.The paper uses the weighted-token measure extensively and allows other monotonically increasing cost functions.Source: §3.1 · p. 5
  • Weighted token service distinguishes input-token and output-token costs using weights w_p and w_q.The measure is W(t1,t2) = w_p · n_p(t1,t2) + w_q · n_q(t1,t2).Source: §3.1 · p. 5

3.2 Fairness in LLM Serving

  • Fairness requires backlogged clients to receive equal service and continuously backlogged clients to receive at least as much as non-backlogged clients.The idealized properties also require the server not to idle while requests remain queued.Source: §3.2 · p. 5
  • A practical scheduler approximates these properties with service-difference bounds independent of the interval length.The paper's method provides formal guarantees for this bounded-difference notion.Source: §3.2 · p. 6

4 Achieving Fairness

Section 4 presents VTC, a continuous-batching scheduler that tracks client service with virtual counters and can be adapted to different fairness criteria. It proves fairness guarantees for backlogged and non-backlogged clients and introduces weighted and length-prediction variants.

4.1 Virtual Token Counter (VTC)

  • VTC maintains client virtual counters, selects requests from the client with the smallest counter, and updates counters for input and generated output tokens.When a client newly enters the queue, its counter is lifted to avoid carrying over credits from a low-load period; the scheduler is mostly work-conserving because it changes dispatch order without rejecting requests that fit.Source: §4.1 · pp. 6–7

4.1.1 Fairness for backlogged clients in VTC

  • For backlogged clients, VTC's fairness bound is tight within a factor of 2 for work-conserving schedulers without preemption; when wq > wp, the upper bound is 2wq·M.The upper bound is twice the lower bound in this setting.Source: §4.1.1 · p. 7

4.1.2 Fairness for non-backlogged clients in VTC

  • For non-backlogged clients, VTC bounds a new request's response time independently of other clients' request rates and dispatches all requests from a client whose rate stays below its share with a constant gap.The dispatch guarantee applies under the stated demand condition over the interval.Source: §4.1.2 · p. 8

4.2 Adapt to Different Fairness Criteria

  • VTC adapts to alternative fairness criteria by changing counter updates to use the chosen service function, with the fairness bound changing accordingly.For service measured by h of input and output tokens, the bound is the maximum aggregated h value for requests fitting in one running batch, assuming output tokens cost more.Source: §4.2 · p. 8

4.3 Weighted VTC

  • Weighted VTC assigns clients service weights, so a client with twice another client's weight is expected to receive twice its service.The virtual-token updates can be modified to implement the weights.Source: §4.3 · pp. 8–9

4.4 VTC with Length Prediction

  • Length prediction charges predicted output-token costs when requests are selected and later adjusts counters to actual output, which may reduce average-case service discrepancy but does not change the theoretical worst case.Its effectiveness depends on workload and prediction accuracy.Source: §4.4 · p. 9

5 Evaluations

Across synthetic and real workloads, VTC confirms the paper’s fairness properties, while every alternative fails in at least one workload. The evaluations also examine the setup, workload conditions, and how memory-pool size and request length affect fairness.

5 Evaluations

  • VTC confirms the proposed fairness properties, while every alternative fails in at least one workload.The evaluation covers different workloads.Source: §5 · p. 9

5.1 Setup

  • The evaluation implements VTC as a thin layer over continuous batching and PagedAttention in S-LoRA, measuring weighted input/output tokens with prompt-token weight 1 and output-token weight 2.Baselines include FCFS, RPM, and LCF; experiments use synthetic workloads and traces from LMSYS Chatbot Arena.Source: §5.1 · pp. 9–10

5.2 Results on Synthetic Workloads

  • With constant request rates and both clients overloaded, VTC keeps their service difference small, whereas FCFS favors the higher-rate sender.VTC also gives the two clients the same service level across measured time intervals.Source: §5.2 · p. 10, Figure 3 · p. 10
  • With Poisson arrivals and unequal input/output lengths, VTC keeps service differences bounded while FCFS loses fairness; under overload, a below-share client's response time stays roughly unchanged.The variable-length workloads include short and long requests as well as differing input/output length combinations.Source: §5.2 · p. 11
  • VTC reallocates unused capacity to demand and keeps equal service for backlogged clients; after distribution shifts, LCF carries an earlier deficit into overload.When a client is below its share, it can be served immediately and another client can use remaining capacity.Source: §5.2 · pp. 10–12

5.3 Results on Real Workloads

  • On real traces, FCFS sharply increases response times for all clients, while VTC concentrates drastic increases among clients sending above their share.The trace workload uses requests from 27 clients drawn from LMSYS Chatbot Arena.Source: §5.3 · pp. 12–13
  • At RPM=5, throughput is ≈340 output tokens per second versus ≈779 tokens per second in VTC or FCFS; higher limits increase throughput but weaken fairness.Throughput rises to 747 tokens per second as the rate limit increases, while response times grow and eventually converge to FCFS.Source: §5.3 · p. 13, Figure 14 · p. 13

5.4 Ablation Study

  • With clients backlogged, a 65000 versus 35000 memory pool and longer requests increase variation in the absolute difference of accumulated services; unknown output lengths overcompensate the smallest counter, while 512*2 and 768*2 have the same variance.The evaluated request lengths were 256*2, 512*2, and 768*2 for the 35000 KV-cache setting; both clients used uniform arrival patterns and different request rates.Source: §5.4 · pp. 13–14, Figure 15 · p. 14

6 Related Works

Prior work studies fairness in resource scheduling, ML training, and LLM serving, but the paper identifies batching and unknown request lengths as distinct challenges for fair LLM serving.

Fairness in scheduling

  • Fair-queuing algorithms address resource sharing, but LLM serving must account for cross-client batching, unknown request lengths, and flexible fairness across performance and GPU consumption.Related approaches include deficit round robin, stochastic fair queuing, WFQ, and SFQ.Source: §6 · p. 14

Fairness in ML training

  • ML-training schedulers consider placement sensitivity and goodput, whereas LLM-serving fairness must also design request batching across clients for GPU utilization.The cited work discusses finish-time fairness and goodput-based scheduling.Source: §6 · p. 14

LLM Serving Systems

  • LLM-serving systems have explored batching, memory and kernel optimizations, parallelism, parameter sharing, speculative execution, and preemption, but the cited works do not consider client fairness [9] [28] [49].The paper's implementation builds on continuous batching and PagedAttention.Source: §6 · p. 14

7 Conclusion

The paper studies fairness in LLM serving and distinguishes its challenges from traditional fairness problems. It defines fairness and proposes a token-granularity fair scheduler.

7 Conclusion

  • The paper frames its subject as fairness in the service received by each LLM client.This focus differs from fairness problems in networking and operating systems.Source: §7 · p. 14
  • It identifies unique challenges for LLM-serving fairness compared with traditional fairness problems in networking and operating systems.Source: §7 · p. 14
  • It defines fair sharing for LLM serving at token granularity and proposes a fair scheduler based on that approach.Source: §7 · p. 14

A Missing Proofs in Proving Fairness of VTC

The appendix states VTC invariants and theorem conditions for fairness and dispatch guarantees, then outlines experiments on advanced variants, including weighted VTC and length prediction.

A Missing Proofs in Proving Fairness of VTC

  • Lemma A.1 states that the minimum client counter in Q is non-decreasing while Q is nonempty.The proof lists counter increases and client removal as the relevant cases.Source: A Missing Proofs in Proving Fairness… · p. 18
  • Theorem 4.11 gives a response-time bound for a new request when its client was not backlogged and had no running-batch requests at the interval's start.The statement assumes a lower bound on capacity and n clients.Source: A Missing Proofs in Proving Fairness… · p. 19
  • For a client initially not backlogged, Theorem 4.13 guarantees dispatch of all requests in the interval under its stated demand bound.The condition relates the client's requests to total service, the number of active clients, and the stated upper bound U.Source: A Missing Proofs in Proving Fairness… · p. 20

B Advanced VTC Variants

  • Appendix B covers weighted VTC, tailoring VTC to a profiled service cost, and length-prediction analysis, reporting improved service discrepancy with length prediction.The listed experiments use Llama-2-7b on an A10G with a 10,000-token KV-cache memory pool.Source: B Advanced VTC Variants · p. 20

B.1 VTC for Weighted Fairness

Weighted VTC differentiates service by client priority: in a synthetic overloaded workload, service closely followed assigned weights, unlike standard VTC's comparable service levels.

B.1 VTC for Weighted Fairness

  • Weights 1:2:3:4 yielded service distribution closely adhering to those ratios under weighted VTC, while standard VTC gave four overloaded clients comparable service.Figure 16 compares received service over a 10-minute synthetic overloaded workload with input and output lengths of 256.Source: Figure 16 · p. 20, §B.1 · p. 20

B.2 VTC with Profiled Cost Function

With a profiled cost function, VTC maintains low response times for low-rate clients in real traces, unlike most baselines; LCF instead penalizes consistently high-rate clients. The profile is nonlinear, and choosing an optimal production cost or pricing model remains outside this evaluation.

B.2 VTC with Profiled Cost Function

  • The profile measures per-request prefill and decode time for Llama-2-7b on an A10G, using the largest batch that fills the memory pool.Shorter input and output lengths permit larger batches; the reported per-request times divide batch times by batch size.Source: §B.2 · p. 20, Figure 17 · p. 21
  • Decode time for all-output-token scenarios is about 2 to 5 times prefill time for all-input-token scenarios with the same total token count.The profiled cost function is nonlinear and was fitted to the measured data points.Source: §B.2 · p. 20
  • VTC maintains low response times for low-rate clients, unlike other baselines except LCF, which gives consistently high-rate clients excessively high response times.In the real-trace results, starvation of low-rate clients does not substantially affect overall service difference.Source: §B.2 · pp. 20–21
  • The evaluation shows VTC can achieve fairness with a customized cost function, but does not determine an optimal production cost function or pricing model.Those choices may vary across production environments and change over time, so their investigation is left for future work.Source: §B.2 · p. 21

B.3 VTC with Length Prediction

In synthetic workloads where all clients are overloaded, length prediction reduces service discrepancies compared with standard VTC. The reduction persists with output-length predictions that can err by 50%.

B.3 VTC with Length Prediction

  • VTC with length prediction precomputes cost using predicted output tokens, then adjusts cost to reflect the actual output length produced.The algorithm describes the prediction-based cost calculation and subsequent correction for actual output.Source: §B.3 · p. 21
  • Length prediction significantly lowers client service discrepancies throughout the test, even with a 50% output-length prediction error margin.Standard VTC keeps absolute service differences bounded rather than growing over time; the comparison uses overloaded synthetic workloads.Source: §B.3 · p. 21
  • The ±50% predictor randomly selects an output length up to 50% above or below the actual length; the oracle predictor is 100% accurate.Figure 19 compares these prediction settings with standard VTC for overloaded clients.Source: §B.3 · p. 21

C.1 VTC Integration in Real Systems

VTC can be integrated into a serving system by updating client counters and selecting requests according to those counters. The discussion also identifies possible conflicts with performance-oriented scheduling and a potential switching policy.

C.1 VTC Integration in Real Systems

  • Figure 18 tracks 27 clients’ response times over a 10-minute real-trace simulation; disconnected curves indicate periods when a client receives no service.The VTC-style schedulers use the profiled cost function.Source: Figure 18 · p. 22
  • Integration adds counter lifting on arrivals, cost-based counter updates as tokens are processed, and selection of the queued request from the client with the lowest counter.The authors describe these as additive modules to an existing serving system.Source: §C.1 · pp. 21–22
  • VTC may conflict with schedulers that favor performance over fairness, such as cache-aware scheduling; switching schedulers at tolerable fairness bounds is proposed for future exploration.The counter-maintenance and request-selection modules could otherwise be additive features of an existing system.Source: §C.1 · p. 22
  • The synthetic evaluation examines maximum accumulated-service differences over 10 minutes for two and eight continuously backlogged clients, with both token lengths set to 256.The real-trace workload has average input and output lengths of 136 and 256 tokens, respectively, with ranges [2,1021] and [2,977].Source: Figure 19 · p. 22, Figure 20 · p. 22

C.2 Adapted Deficit Round Robin

The paper adapts Deficit Round Robin (DRR) for LLM serving and shows that it is equivalent to VTC. Its debt accounting addresses unknown output lengths, while small-quantum repeated round-robin is inefficient to simulate.

C.2 Adapted Deficit Round Robin

  • The adapted DRR scheduler is equivalent to the proposed VTC scheduler.The paper presents the adaptation as an alternative description of VTC.Source: §C.2 · pp. 22–23
  • DRR cannot directly choose how many requests to schedule under its cost limit because output-token counts are unknown in advance.The adaptation accounts for prompt cost when scheduling and deducts each decoded token’s cost from client debt, which can remain negative across rounds.Source: §C.2 · pp. 23–24
  • With quantum Q = ε smaller than a single prompt-token cost, adapted DRR functions like VTC: the client with the highest debt has received the least service.A smaller Q tightens the fairness constraint, though fairness is no longer strictly bounded by Q.Source: §C.2 · p. 24
  • Repeated round-robin simulation with a small quantum is inefficient, so the paper focuses its analysis on VTC.When a client leaves the queue, its debt is no longer refilled once nonnegative; a later arrival starts with debt in (0,ε], mirroring VTC’s counter lift.Source: §C.2 · p. 24

C.3 Future Work

Future work considers preemption as a way to address fairness-bound looseness, distributed deployment, and combining VTC with auto-scaling. These directions involve trade-offs or unresolved implementation challenges.

C.3 Future Work

  • Without preemption, accumulated requests from one client can occupy memory and constrain the fairness bound; investigating preemption is left as orthogonal future work.The worst case is tied to underestimating future token counts.Source: §C.3 · p. 24
  • Per-client limits on running-batch memory can improve the bound but may reduce throughput; preemption could swap in requests from clients with lower counters.The proposed trigger is a service difference exceeding a threshold.Source: §C.3 · p. 24
  • Distributed VTC could use a central dispatcher to maintain token counters, but its bound depends on aggregate serving-engine memory and concurrent counter updates raise synchronization challenges.The distributed integration is identified as future work.Source: §C.3 · p. 24
  • VTC does not require constant capacity, though adding or removing GPUs may call for a hierarchical virtual counter; combining VTC with auto-scaling remains future work.Auto-scaling may mitigate RPM-related throughput degradation, but brings operational cost, workload-prediction, and responsiveness challenges.Source: §C.3 · p. 24
Loading 2401.00588v2…