Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Locality-aware Fair Scheduling in LLM Serving

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read DLPM is the first LLM-serving scheduler that keeps prefix-cache locality while proving a constant bound on the service gap between backlogged clients.

desk verdict The DLPM fairness theorem is not proven: the refill trigger ignores clients whose requests are in the running batch, so the equal-refill-count step fails and the advertised bound can be violated even in synchronous execution. read the letter →

arxiv 2501.14312 v1 pith:4OWXBMWV submitted 2025-01-24 cs.DC cs.LG

Shiyi Cao , Yichuan Wang , Ziming Mao , Pin-Lun Hsu , Liangsheng Yin , Tian Xia , Dacheng Li , Shu Liu
show 5 more authors
Yineng Zhang Yang Zhou Ying Sheng Joseph Gonzalez Ion Stoica
This is my paper · ORCID
classification cs.DCcs.LG
keywords LLMservingfairschedulingprefixcachingdeficitroundrobinlocality-awaredistributed
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that an LLM inference server can keep the throughput benefits of prefix-cache locality without giving up fairness among clients. It introduces DLPM, a single-GPU scheduler that groups requests by longest matching prefix like locality-aware schedulers do, but inserts deficit counters that force the server to periodically serve less-served clients. The central result is a fairness bound: over any time interval, two continuously backlogged clients receive service that differs by at most a constant, independent of how long the interval runs. The paper extends the same idea to multi-GPU serving with D2LPM, where per-worker deficit counters bound how sticky a client becomes to one GPU. A sympathetic reader would care because it offers a concrete knob for the locality-fairness trade-off that previous fair or locality-aware schedulers handled only one-sidedly.

What carries the argument

The load-bearing mechanism is a deficit counter per client, borrowed from deficit round robin, overlaid on LPM's prefix-sorted dispatch order. In DLPM, the scheduler sorts waiting requests by matched prefix length; a request is added to the batch only if its client's deficit counter is positive, and the counter is decremented by the weighted service the request consumes, with all non-positive counters replenished by Qu when no active client can proceed. This preserves the local ordering that LPM exploits for prefix sharing while occasionally interrupting it to serve under-served clients. The distributed D2LPM keeps a second set of deficit counters, one per client per worker, so the global scheduler can decide whether to send a request to the worker with the longest matching prefix or to a less-used worker, balancing locality, load, and fairness.

What would settle it

Run the DLPM scheduler in the real asynchronous SGLang implementation with a continuously backlogged client whose requests arrive in bursts just after refill checks, and compute the service gap between that client and another continuously backlogged client over a long interval: if the gap exceeds 2(U + Qu) on a single GPU, or 2|W|(U + Qu) with |W| workers, then the theorem's precondition is violated in practice.

Watch

Extended reading notes

Core claim

The paper claims that combining longest-prefix-match scheduling with a deficit-round-robin quantum mechanism yields both high prefix-cache hit rates and approximate max-min fairness. Formally, for any two clients f and g that are continuously backlogged, the difference in their received service over any interval is |W_f(t1,t2) - W_g(t2,t1)| ≤ 2(U + Qu), where U = we·Linput + wq·M is the maximum service a single request can consume, and Qu is the per-client service quantum. The distributed variant, D2LPM, with |W| workers, bounds the gap between the most- and least-served backlogged clients by 2|W|(U + Qu) (Theorem 5.1). The paper also proves that a backlogged client is not served less than a non-backlogged client by more than the same order of constant, and that both algorithms are work-conserving: no GPU sits idle while requests are queued. On measured workloads, DLPM/D2LPM achieve up to 2.87x higher throughput than VTC and up to 7.18x lower latency for well-behaved clients than Preble and RR+LPM.

Load-bearing premise

The proof assumes that every continuously backlogged client has a request waiting in the scheduler queue at every deficit-refill moment, so all backlogged clients are replenished in lockstep; if requests arrive asynchronously, a client can miss a refill and the advertised bound is not shown to hold.

Editorial extensions

If this is right

  • On a single GPU, a server can keep LPM-like throughput while bounding the service gap between continuously backlogged clients by 2(U + Qu), a value independent of time.
  • In a distributed deployment, D2LPM gives a global fairness bound that scales linearly with the number of workers, while preserving per-GPU prefix locality and avoiding the synchronization overhead of centralized global scheduling.
  • Compared with fairness-only VTC, DLPM/D2LPM improve throughput by up to 2.87x across the tested workloads; compared with locality-only Preble and RR+LPM, they reduce well-behaved client latency by up to 7.18x and 9.55x respectively.
  • The quantum parameters Qu and Qw act as a dial: increasing them improves throughput and locality at the cost of looser fairness, so operators can choose an operating point on a new Pareto frontier.
  • Both algorithms are work-conserving, meaning the fairness guarantee is enforced by reordering dispatch rather than by idling hardware.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same quantum-vs-locality mechanism could apply to other per-client affinities in LLM serving, such as adapter (LoRA) locality or model-replica affinity, wherever a scheduler reorders requests to exploit reuse.
  • The constant 2(U + Qu) grows with the maximum input length and batch token capacity, so for very long-context workloads the slack in the fairness guarantee widens; the paper's own S2@Long-Context QA result shows locality pressure overtaking fairness in that regime.
  • The theorems assume synchronised refill of backlogged clients' counters; if the live SGLang implementation refills asynchronously, an adversarial arrival pattern could produce a service gap larger than the stated bound, so a formal analysis of asynchronous refill would be a natural next step.
  • A direct way to test Theorem 4.1 in practice is to instrument the deployed scheduler to record per-client weighted service at fixed intervals and plot the max-minus-min service over time, checking whether the curve stays under 2(U + Qu).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes DLPM, a single-worker LLM serving scheduler that combines Longest Prefix Match (LPM) request ordering with per-client deficit counters, and D2LPM, a distributed extension with per-client-per-worker deficits. The central advertised contribution is a fairness guarantee: for continuously backlogged clients, the difference in weighted service is bounded by 2(U + Qu) in the single-worker case (Theorem 4.1) and by 2|W|(U + Qu) in the distributed case (Theorem 5.1), while preserving high prefix-cache locality. The evaluation on top of SGLang with four workloads reports up to 2.87x higher throughput than VTC and up to 7.18x lower victim-client latency than Preble and RR+LPM.

Significance. If the fairness bounds were valid, the paper would make a useful contribution: adapting the deficit-round-robin mechanism to prefix-locality-aware scheduling is a natural and plausible way to navigate the fairness-locality trade-off, and the empirical results suggest practical benefits over existing schedulers. The theoretical guarantees are, however, the paper's headline claim and appear in the abstract and contributions. The proofs are informal, contain arithmetic errors, and rely on an unstated synchronous-refill assumption; as stated, the single-worker bound is not established and admits a counterexample within Algorithm 1. The paper does not provide an artifact or machine-checked proofs, so the informal proofs are the only evidence for the central guarantee.

major comments (3)
  1. [Sec. 4.2, Theorem 4.1; Algorithm 1, Lines 3-8] The first bullet of the proof of Theorem 4.1 assumes that two continuously backlogged clients f and g 'have been replenished the same k number of times in Line 7 since t1.' Algorithm 1 does not guarantee this. The CHECK_REFILL procedure (Lines 3-8) scans only clients with requests in the dispatch Queue; a client whose request is in the running batch B is invisible to that scan. If such a client has positive qi at a refill event, it is not replenished, and its positive qi does not block other clients from being replenished. With the stress-test parameterization Qu=10000, M=1010, we=1, wq=2, so U=2030, let f have a request with 10 input and 1000 output tokens in B while also having a nonempty dispatch queue (so f is backlogged under Definition 3.1), and let g continuously have small requests in Queue. After the initial refill, f's qi stays near 7990 during its long decode; g's qi repeatedly falls to at most 0 and is replenished roughly every 10000/30 small requests, giving g about 75000 service over 1000 decode steps while f receives about 2010. Then |Wf - Wg| is far larger than 2(U + Qu) = 24060, and the gap grows with the number of refills. The equal-k assumption is load-bearing for Theorems 4.1, 4.2, 5.1, and 5.2; the authors must either prove equal-k under the stated backlog definition or amend Definition 3.1 and Algorithm 1 and re-derive the bounds.
  2. [Appendix A.1, Theorem A.1] The induction proving the invariant qi(t) > -U has a double error in the decode step. First, the statement 'the number of decoded tokens cannot exceed the server's maximum token capacity M, so n * |{r | client(r)=i, r in B}| <= M' is false when n > 1 decode steps occur: a client with k tokens in the batch consumes n*k output tokens over n steps, which can exceed M. Second, from qi(t) > -U one cannot conclude qi(t) - wq*M > -U; the inequality goes in the opposite direction. Because the invariant is not preserved, the bound |Wi(t1,t2) - Ki*Qu| <= max(Qu,U) is unproved, and Theorem 4.1's final inequality, which invokes Theorem A.1, is unsupported.
  3. [Sec. 5.2, Theorem 5.1 and Appendix A.2] The proof of Theorem 5.1 states that a backlogged client 'will have a request and hence be backlogged in all workers' and that 'requests will be distributed to all workers and credit for each worker is exhausted, before replenishing the credits for all workers.' Nothing in Algorithm 2 ensures this. SELECT_WORKER dispatches each request to a single worker (Lines 13-15), and the per-worker deficit qi,w of a worker that receives no traffic from client i can remain positive while other workers are refilled; there is no mechanism that exhausts every worker's credit for a client before refilling. Thus the |W| factor in the distributed bound is unsupported independently of the single-worker flaw in Theorem 4.1.
minor comments (4)
  1. [Sec. 4.2, proof of Theorem 4.2] The displayed expansion of Wg - Wf in the proof of Theorem 4.2 is algebraically inconsistent with the definition Wf = qf(t1) + k_f Qu - qf(t2). As printed, the second parenthesized term contains '+ kt1_f Qu' where the preceding minus sign requires '- kt1_f Qu'; the formula therefore does not follow from the definitions.
  2. [Appendix A.1, Theorem A.1] The line-number references in the proof are stale: the decode deduction is Algorithm 1 Line 26, not Line 23; the admission deduction is Line 23. This makes the argument harder to audit.
  3. [Sec. 6.2 and Fig. 7] Several data points are absent from Fig. 7 without enough explanation: Preble at D=1 is omitted by design, but the S2@Tree-of-Thoughts D=8 point is also missing and the caption's 'takes too long' note does not state whether this is an experimental timeout or a resource limitation.
  4. [Abstract and Sec. 6.2] The abstract's 'up to 7.18x lower latency' claim should name the comparison baseline and workload explicitly; Section 6.2 reports 7.18x versus Preble and 9.55x versus RR+LPM, and the abstract's phrasing is ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the fairness bounds follow from the algorithm's deficit-counter invariants, and the empirical claims are benchmarked against external systems.

full rationale

The paper's core claims are the fairness bounds of DLPM and D2LPM (Theorems 4.1, 4.2, 5.1, 5.2), proved in Appendix A by induction on the deficit-counter invariants qi <= Qu and qi > -U. These are self-contained algebraic consequences of Algorithm 1 and Algorithm 2, not of fitting. The service measure W = we*ne + wq*nq is a stated measurement convention with weights taken from OpenAI-style pricing, and evaluating the schedulers with the same metric is an objective-consistency choice, not a prediction derived from fitted inputs. Qu and Qw are hyperparameters whose effects are swept empirically, while the fairness theorem holds for every Qu by construction, so no fitted parameter is renamed as a prediction. Although the paper cites VTC and SGLang, which share authors, those citations provide definitions and baselines rather than the load-bearing bound; the central theorems are derived in-paper from the pseudocode. Even if the equal-refresh-count assumption in Theorem 4.1 is challenged as a correctness matter, that is a proof gap, not circularity. The empirical comparisons against VTC, Preble, and RR+LPM on real workloads give the contributions independent external content. Hence no significant circularity.

Assumptions & free parameters 3 free parameters · 6 assumptions · 1 invented entities

The central fairness guarantee rests on the DRR-style deficit-counter model, a synchronous-refill model, bounded request costs (L_input, M), and the chosen cost weights (we=1, wq=2). The two hyperparameters Qu and Qw are tuned in the evaluation but do not enter the proof bounds for finite Qw.

free parameters (3)
  • Qu (per-client quantum) = not reported for main results; swept 1000-32000 in Fig. 1
    Controls the fairness-locality trade-off in DLPM and appears in the fairness bound 2(U+Qu). Larger Qu improves throughput at the cost of fairness.
  • Qw (per-client-per-worker quantum) = not reported for main results; swept 2000-40000 in Fig. 10
    Controls the stickiness of a client to a worker in D2LPM. Larger Qw improves locality but reduces load balance and slightly lowers Jain's index.
  • we, wq cost weights = we=1, wq=2
    Weights for extend-token and output-token service accounting, set to OpenAI's GPT-4 pricing ratio. The fairness guarantee is relative to this cost model, so the weights are a modeling choice.
assumptions (6)
  • ad hoc to paper Synchronous refill rounds: every continuously backlogged client has a request in the scheduler queue whenever deficit counters are refilled.
    Algorithm 1 Lines 3-8 refill based on the current queue. The proofs of Theorems 4.1 and 4.2 assume all backlogged clients are included in the same refill rounds; asynchronous arrivals in the real system can violate this.
  • domain assumption The batch capacity M is a constant upper bound on the number of tokens that can be decoded in a running batch.
    Used to bound qi(t) > -U in Theorem A.1 and A.3; M is the maximum tokens in a running batch.
  • domain assumption Request cost is bounded: at most L_input input tokens and M output tokens per request.
    U = we*Linput + wq*M bounds the single-request overshoot in the deficit proofs.
  • domain assumption LPM ordering and RadixTree prefix matching are available at each batching step.
    The algorithm assumes sorting by matched prefix length and exact prefix-match lookups, as provided by SGLang [58].
  • domain assumption Max-min fairness as defined by the three VTC properties is the correct fairness criterion.
    The paper adopts the VTC fairness properties from [42]; all guarantees are relative to this criterion.
  • standard math Classic Deficit Round Robin analysis (Shreedhar and Varghese 1996) provides the kernel of the deficit-counter bound.
    The proofs in Appendix A.1 adapt the classic DRR bound to LPM ordering.
invented entities (1)
  • Per-client and per-client-per-worker deficit counters (qi, qi,w)
    purpose: Track each client's received service to enforce fairness while allowing locality-preserving reordering.
    These are internal algorithmic ledger entries introduced by this paper. They have no falsifiable handle outside the algorithm's behavior, but they are bookkeeping, not physical postulates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Locality-aware Fair Scheduling in LLM Serving." pith.science (2026). https://pith.science/paper/4OWXBMWV

@misc{pith2026250114312,
  author       = {Pith},
  title        = {Pith review of: Locality-aware Fair Scheduling in LLM Serving},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4OWXBMWV}},
  note         = {Machine review of arXiv:2501.14312}
}
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.

Figures

Figures reproduced from arXiv: 2501.14312 by the authors.

Figure 1
Figure 1. DLPM achieves a new Pareto frontier considering locality and fairness in LLM serving. Q is a hyper-parameter in DLPM, indicating how much we relax the fairness bound of DLPM. Results are obtained in a single A10 GPU. posing substantial barriers to their broad adoption. On the one hand, service providers need to provide isolation between con￾current tasks to ensure stable and predictable performance for all clients [… view at source ↗
Figure 3
Figure 3. This paper addresses the conflict between fairness and locality through the DLPM mechanism (§4). It further addresses the conflict between locality and load balancing in distributed settings with the D2LPM mechanism (§5). distributed settings can be combined to maintain global fair￾ness effectively. In the remainder of the paper, we begin by discussing preliminary concepts related to fairness in LLM serving (§3), th… view at source ↗
Figure 4
Figure 4. Global scheduler overhead breakdown w.r.t data paral￾lelism degree and global queue size. The time for one decode step with bs=25 is also reported for reference. Existing serving engines such as vLLM [22] and SGLang [58] normally perform a continuous batching step after multiple (e.g., 10 in SGLang) decoding steps. dispatch time ti−1 and the current time ti . MKV indicates the current available KV cache memory. Upon… view at source ↗
Figures from the paper (7 more)
Figure 6
Figure 6. Figure 6: Illustration of the execution graphs of different workloads in our benchmark. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: Summary of results across three datasets and two types of misbehaving clients on up to 8 A100 GPUs (8B model). The reported latency represents the average latency for well-behaved clients. The data point for S2@Tree-of-Thoughts with D = 8 is omitted, as it takes too lo…
Figure 8
Figure 8. Figure 8: Fairness and performance visualization for the real-world multi-turn conversation workload (D = 2). Clients 2 and 3 send requests at a much higher rate than Clients 0 and 1. Jain’s Fairness Index Analysis From the second column in [PITH_FULL_IMAGE:figures/full_fig_p01…
Figure 9
Figure 9. Figure 9: Fairness and performance visualization of different sched￾ulers on Tree-of-Thoughts workloads with D = 4 (3B model + 4 A10G GPUs). The maximum value on the X-axis represents the end-to-end completion time for each scheduler. The actual service is calculated using the c…
Figure 11
Figure 11. Figure 11: , DLPM consistently achieves a service rate compara￾ble to LPM, even as the number of clients increases, whereas VTC consistently underperforms. 5 10 50 Number of Clients 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 Service (tokens/s) LPM DLPM VTC [PITH_FULL_IMAGE:…
Figure 10
Figure 10. Figure 10: Impact of Q w on throughput under different workloads (D = 4). The solid line represents throughput, while the dashed line represents Jain’s Index. The fairness index in (b) is omitted as it consistently equals 1. We now examine the trade-off between locality and fair…
Figure 12
Figure 12. Figure 12: Mix of workloads among four clients: two engage in multi-turn conversations, while the other two send different pro￾grams, all within a single-GPU setup (3B model + an A10G GPU). 8 Related Work Fairness in ML Workloads ML training workloads have extensively studied th…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scheduling Mixed RL Rollouts Beyond Prefix Locality

    cs.DC 2026-08 conditional novelty 6.0 of 10

    MISA-T is a router-level admission policy that allocates KV-cache capacity per workload class and by residency time, improving mixed RL rollout throughput by 35-53% versus a tuned vLLM Router baseline.

  2. MQFQ-Sticky: Fair Queueing For Serverless GPU Functions

    cs.DC 2025-07 conditional novelty 6.0 of 10

    MQFQ-Sticky applies multi-queue fair queuing and anticipatory scheduling to GPU serverless functions, reporting 2x-20x latency reductions and fairer GPU service than FCFS, batching, or SJF policies.

Reference graph

Works this paper leans on

59 extracted references · 39 canonical work pages · cited by 2 Pith papers

  1. [1]

    Perplexity: Conversational Search Assis- tant

    Perplexity AI. Perplexity: Conversational Search Assis- tant. https://www.perplexity.ai

    work page

  2. [2]

    Fairness and load balancing in wireless lans using association control

    Yigal Bejerano, Seung-Jae Han, and Li Li. Fairness and load balancing in wireless lans using association control. In Proceedings of the 10th annual international conference on Mobile computing and networking, pages 315–329, 2004

    work page 2004

  3. [3]

    Large language monkeys: Scaling inference compute with repeated sampling

    Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirho- seini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024

    arXiv 2024

  4. [4]

    Bal- ancing efficiency and fairness in heterogeneous gpu clus- ters for deep learning

    Shubham Chaudhary, Ramachandran Ramjee, Muthian Sivathanu, Nipun Kwatra, and Srinidhi Viswanatha. Bal- ancing efficiency and fairness in heterogeneous gpu clus- ters for deep learning. In Proceedings of the Fifteenth European Conference on Computer Systems, pages 1– 16, 2020

    work page 2020

  5. [5]

    Unearthing Inter-Job Dependencies for Better Cluster Scheduling

    Andrew Chung, Subru Krishnan, Konstantinos Karana- sos, Carlo Curino, and Gregory R Ganger. Unearthing Inter-Job Dependencies for Better Cluster Scheduling. In 14th USENIX Symposium on Operating Systems De- sign and Implementation (OSDI 20), pages 1205–1223, 2020

    work page 2020

  6. [6]

    Training verifiers to solve math word problems

    Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plap- pert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021

    arXiv

  7. [7]

    Damai Dai, Chengqi Deng, Chenggang Zhao, R. X. Xu, Huazuo Gao, Deli Chen, Jiashi Li, Wangding Zeng, Xingkai Yu, Y . Wu, Zhenda Xie, Y . K. Li, Panpan Huang, Fuli Luo, Chong Ruan, Zhifang Sui, and Wen- feng Liang. Deepseekmoe: Towards ultimate expert specialization in mixture-of-experts language models. CoRR, abs/2401.06066, 2024

    arXiv 2024

  8. [8]

    Deepseek-r1-lite-preview release

    DeepSeek. Deepseek-r1-lite-preview release. https: //api-docs.deepseek.com/news/news1120, 2024. Accessed: 2024-11-20

    work page 2024

Show all 59 references
  1. [9]

    Demers, Srinivasan Keshav, and Scott Shenker

    Alan J. Demers, Srinivasan Keshav, and Scott Shenker. Analysis and simulation of a fair queueing algorithm. In Lawrence H. Landweber, editor, ACM Symposium on Communications Architectures & Protocols (SIG- COMM), pages 1–12. ACM, 1989

    1989

  2. [10]

    The llama 3 herd of models

    Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024

    2024 arXiv

  3. [11]

    Dominant resource fairness: fair allocation of multiple resource types

    Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: fair allocation of multiple resource types. In Proceedings of Networks and Systems Design and Implementation (NSDI), 2011

    2011

  4. [12]

    Github copilot: Your ai pair programmer

    Github. Github copilot: Your ai pair programmer. https://github.com/features/copilot

  5. [13]

    Jamaloddin Golestani

    S. Jamaloddin Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings IEEE INFOCOM ’94, The Conference on Computer Communications, Thirteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking for Global Comm...

    1994

  6. [14]

    Vin, and Haichen Cheng

    Pawan Goyal, Harrick M. Vin, and Haichen Cheng. Start-time fair queueing: A scheduling algorithm for in- tegrated services packet switching networks. In Confer- ence on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), pages 157–168...

    1996

  7. [15]

    Altruistic scheduling in Multi-Resource clusters

    Robert Grandl, Mosharaf Chowdhury, Aditya Akella, and Ganesh Ananthanarayanan. Altruistic scheduling in Multi-Resource clusters. In 12th USENIX Sympo- sium on Operating Systems Design and Implementa- tion (OSDI 16), pages 65–80, Savannah, GA, November

  8. [16]

    Quincy: Fair scheduling for distributed computing clusters

    Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg. Quincy: Fair scheduling for distributed computing clusters. In ACM Symposium on Operating Systems Principles (SOSP), page 261–276. Association for Computing Ma- chinery, 2009

    2009

  9. [17]

    A quantitative measure of fairness and discrimina- tion

    Rajendra K Jain, Dah-Ming W Chiu, William R Hawe, et al. A quantitative measure of fairness and discrimina- tion. Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 21:1, 1984

    1984

  10. [18]

    Mistral 7b.arXiv preprint arXiv:2310.06825, 2023

    Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b.arXiv preprint arXiv:2310.06825, 2023

    arXiv

  11. [19]

    Chase, and Jasleen Kaur

    Wei Jin, Jeffrey S. Chase, and Jasleen Kaur. Interposed proportional sharing for a storage service utility. In International Conference on Measurements and Model- ing of Computer Systems (SIGMETRICS), pages 37–48. ACM, 2004. 13

    2004

  12. [20]

    CFS Sched- uler

    The kernel development community. CFS Sched- uler. https://docs.kernel.org/scheduler/ sched-design-CFS.html

  13. [21]

    Com- pletely fair scheduler

    The Linux kernel development community. Com- pletely fair scheduler. https://docs.kernel.org/ scheduler/sched-design-CFS.html

  14. [22]

    Efficient memory man- agement for large language model serving with paged attention

    Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory man- agement for large language model serving with paged attention. In Proceedings of the 29th Symposium on Operating Systems Principles...

    2023

  15. [23]

    An axiomatic theory of fairness in network resource allocation

    Tian Lan, David Kao, Mung Chiang, and Ashutosh Sab- harwal. An axiomatic theory of fairness in network resource allocation. In 2010 Proceedings IEEE INFO- COM, pages 1–9, 2010

    2010

  16. [24]

    Loogle: Can long-context language mod- els understand long contexts? arXiv preprint arXiv:2311.04939, 2023

    Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. Loogle: Can long-context language mod- els understand long contexts? arXiv preprint arXiv:2311.04939, 2023

    2023 arXiv

  17. [25]

    {AlpaServe}: Sta- tistical multiplexing with model parallelism for deep learning serving

    Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E Gonzalez, et al. {AlpaServe}: Sta- tistical multiplexing with model parallelism for deep learning serving. In 17th USENIX Symposium on Oper- ating System...

    2023

  18. [26]

    Self- refine: Iterative refinement with self-feedback.Advances in Neural Information Processing Systems, 36, 2024

    Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self- refine: Iterative refinement with self-feedback.Advances in Neural Information Processing Systems, 36, 2024

    2024

  19. [27]

    Themis: Fair and effi- cient gpu cluster scheduling

    Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee, and Shuchi Chawla. Themis: Fair and effi- cient gpu cluster scheduling. In 17th USENIX Sympo- sium on Networked Systems Design and Implementation (NSDI 20), pages 28...

    2020

  20. [28]

    {Heterogeneity-Aware} cluster scheduling policies for deep learning workloads

    Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee, and Matei Zaharia. {Heterogeneity-Aware} cluster scheduling policies for deep learning workloads. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 481–498, 2020

    2020

  21. [29]

    Nesbit, Nidhi Aggarwal, James Laudon, and James E

    Kyle J. Nesbit, Nidhi Aggarwal, James Laudon, and James E. Smith. Fair queuing memory systems. In 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06), pages 208–222, 2006

    2006

  22. [30]

    Skeleton-of-thought: Prompting LLMs for efficient parallel generation

    Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. Skeleton-of-thought: Prompting LLMs for efficient parallel generation. In The Twelfth International Conference on Learning Rep- resentations, 2024

    2024

  23. [31]

    Gpt-4 technical report, 2023

    OpenAI. Gpt-4 technical report, 2023

    2023

  24. [32]

    Rate limit

    OpenAI. Rate limit. https://platform.openai. com/docs/guides/rate-limits?context= tier-free, 2023

    2023

  25. [33]

    Learning to reason with llms

    OpenAI. Learning to reason with llms. https://openai.com/index/ learning-to-reason-with-llms/ , 2024. Ac- cessed: 2024-11-20

    2024

  26. [34]

    Parekh and R.G

    A.K. Parekh and R.G. Gallager. A generalized pro- cessor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking, 1(3):344–357, 1993

    1993

  27. [35]

    O’Brien, Carrie J

    Joon Sung Park, Joseph C. O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In In the 36th Annual ACM Symposium on User Interface Software and Technology (UIST ’23), UIST ’23, New ...

    2023

  28. [36]

    Patil, Tianjun Zhang, Xin Wang, and Joseph E

    Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305.15334, 2023

    2023 arXiv

  29. [37]

    Efficiently scal- ing transformer inference

    Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scal- ing transformer inference. Proceedings of Machine Learning and Systems, 5, 2023

    2023

  30. [38]

    Agent q: Advanced reasoning and learning for au- tonomous ai agents

    Pranav Putta, Edmund Mills, Naman Garg, Sumeet Mot- wani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov. Agent q: Advanced reasoning and learning for au- tonomous ai agents. arXiv preprint arXiv:2408.07199, 2024

    2024 arXiv

  31. [39]

    Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning

    Aurick Qiao, Sang Keun Choe, Suhas Jayaram Subra- manya, Willie Neiswanger, Qirong Ho, Hao Zhang, Gre- gory R Ganger, and Eric P Xing. Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning. In 15th {USENIX} Symposium on Operating Systems Design and Impleme...

    2021

  32. [40]

    Toolformer: Language models can teach themselves to use tools.arXiv preprint arXiv:2302.04761, 2023

    Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Can- cedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools.arXiv preprint arXiv:2302.04761, 2023. 14

    2023 arXiv

  33. [41]

    Gonzalez, and Ion Stoica

    Ying Sheng, Shiyi Cao, Dacheng Li, Coleman Hooper, Nicholas Lee, Shuo Yang, Christopher Chou, Banghua Zhu, Lianmin Zheng, Kurt Keutzer, Joseph E. Gonzalez, and Ion Stoica. S-lora: Serving thousands of concurrent lora adapters. arXiv preprint arXiv:2311.03285, 2023

    2023 arXiv

  34. [42]

    Fairness in Serving Large Language Models

    Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica. Fairness in Serving Large Language Models. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 965–988, 2024

    2024

  35. [43]

    Shreedhar and George Varghese

    M. Shreedhar and George Varghese. Efficient fair queue- ing using deficit round-robin. IEEE/ACM Trans. Netw., 4(3):375–385, 1996

    1996

  36. [44]

    Scaling llm test-time compute optimally can be more effective than scaling model parameters

    Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Ku- mar. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024

    2024 arXiv

  37. [45]

    Preble: Efficient Distributed Prompt Scheduling for LLM Serving

    Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dong- ming Li, and Yiying Zhang. Preble: Efficient Distributed Prompt Scheduling for LLM Serving. 2024

    2024

  38. [46]

    Can Scheduling Overhead Dom- inate LLM Inference Performance? A Study of CPU Scheduling Overhead on Two Popular LLM Infer- ence Systems

    Vikranth Srivatsa, Dongming Li, Yiying Zhang, and Reyna Abhyankar. Can Scheduling Overhead Dom- inate LLM Inference Performance? A Study of CPU Scheduling Overhead on Two Popular LLM Infer- ence Systems. https://mlsys.wuklab.io/posts/ scheduling_overhead/

  39. [47]

    Earliest Eligi- ble Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation

    Ion Stoica and Hussein Abdel-Wahab. Earliest Eligi- ble Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation. Old Dominion Univ., Norfolk, VA, Tech. Rep. TR-95-22, 1995

    1995

  40. [48]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017

    2017

  41. [49]

    V oyager: An open-ended embodied agent with large language models

    Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Man- dlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and An- ima Anandkumar. V oyager: An open-ended embodied agent with large language models. arXiv preprint arXiv: Arxiv-2305.16291, 2023

    2023 arXiv

  42. [50]

    Max-min fairness

    Wikipedia. Max-min fairness. https://en. wikipedia.org/wiki/Max-min_fairness

  43. [51]

    Qwen2 technical report

    An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, et al. Qwen2 technical report. arXiv preprint arXiv:2407.10671, 2024

    2024 arXiv

  44. [52]

    Tree of thoughts: Deliberate problem solving with large lan- guage models

    Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large lan- guage models. Advances in Neural Information Pro- cessing Systems, 36, 2024

    2024

  45. [53]

    Orca: A distributed serving system for transformer-based generative mod- els

    Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soo- jeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for transformer-based generative mod- els. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, 2022

    2022

  46. [54]

    Delay Scheduling: a Simple Technique for Achieving Locality and Fairness in Cluster Scheduling

    Matei Zaharia, Dhruba Borthakur, Joydeep Sen Sarma, Khaled Elmeleegy, Scott Shenker, and Ion Stoica. Delay Scheduling: a Simple Technique for Achieving Locality and Fairness in Cluster Scheduling. In Proceedings of the 5th European conference on Computer systems, pages 265–278, 2010

    2010

  47. [55]

    Rest-mcts*: Llm self- training via process reward guided tree search

    Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mcts*: Llm self- training via process reward guided tree search. arXiv preprint arXiv:2406.03816, 2024

    2024 arXiv

  48. [56]

    BlendServe: Optimizing Offline Inference for Auto- regressive Large Models with Resource-aware Batching

    Yilong Zhao, Shuo Yang, Kan Zhu, Lianmin Zheng, Baris Kasikci, Yang Zhou, Jiarong Xing, and Ion Sto- ica. BlendServe: Optimizing Offline Inference for Auto- regressive Large Models with Resource-aware Batching. arXiv preprint arXiv:2411.16102, 2024

    2024 arXiv

  49. [57]

    P Xing, Hao Zhang, Joseph E

    Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuo- han Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena, 2023

    2023

  50. [58]

    Efficiently programming large language models using sglang

    Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Chris- tos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Efficiently programming large language models using sglang. arXiv preprint arXiv:2312.07104, 2023. 15 A Appendix A.1 Proof f...

    2023 arXiv

  51. [59]

    • Given that a is the lower bound of the server capacity, the dispatch time for f is therefore bounded: D(r f ) − A(r f ) ≤ 2 · (n − 1) · Qu+U a

    · (Qu +U), where n − 1 is the n − 1 other clients. • Given that a is the lower bound of the server capacity, the dispatch time for f is therefore bounded: D(r f ) − A(r f ) ≤ 2 · (n − 1) · Qu+U a . A.2 Proof for D 2LPM Scheduling Theorem A.3 (Service Bound). Consider any execu...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.