A mathematical scheduling model that connects within-batch resource fairness to system throughput and provides a bi-criterion scheduling policy, ISJL, which maintains high throughput while aligning max-driven batch cost with token-metered revenue.
Abstract
This paper studies a resource-allocation inefficiency in batched large language model (LLM) serving: heterogeneous requests that share a decode batch impose max-driven computational costs on one another. Because the wall-clock cost of a batch step is largely governed by the largest active KV-cache footprint, a short request co-batched with a long request can experience latency and GPU-resource consumption disproportionate to its own token workload. We formalize this phenomenon as a resource-fair scheduling problem. We develop a mathematical scheduling model that connects within-batch resource fairness to system throughput. The proposed fairness constraint bounds the disparity in decode progress, equivalently KV-cache footprint, among co-batched requests. Based on this model, we design the Insert-Short-Jobs-with-Limit (ISJL) algorithm, a parameterized hybrid batching policy. We prove that ISJL achieves a global competitive-ratio lower bound of $3/4$. We further examine the profit implications of resource-fair scheduling under the token-metered pricing convention used by commercial LLM APIs. Numerical experiments show that ISJL occupies a favorable middle ground between FCFS, which has large batching externalities, and LJF, which is cost-aligned but sacrifices batching flexibility. Thus, ISJL provides a bi-criterion scheduling policy: it maintains high throughput while aligning max-driven batch cost with token-metered revenue.
This work presents the first constant-competitive algorithm for arbitrary prompt lengths and arbitrary response lengths with no additional assumptions, built on a novel regime-aware routing framework.
Yiding Feng, Siyu Liu, Zonghan Yang et al.· 1 citation
CELLServe formalizes SLO-constrained joint resource provisioning as an optimization problem with a dedicated algorithm, and introduces an opportunistic instance merging strategy for decode phase functions to reclaim fragmented resources.
Zejian Wang, Nan Lin, Zinuo Cai et al.· ACM Transactions on Architec...· 0 citations
The rapid expansion of Large Language Models (LLMs) has established Deep Learning Training (DLT) as a major workload in modern multi-tenant GPU clusters. While fair computational scheduling is well-studied, fair communication scheduling in handling execution-time network contention remains underexplored. Current DLT communication schedulers focus primarily on efficiency-oriented objectives, often causing disparate performance degradation or even job starvation when concurrent jobs compete for shared bandwidth. In this paper, we propose LEVELLER, the first communication scheduling system that achieves max-min fairness specifically for DLT workloads. To bridge the gap between traditional flow-level fairness and DLT job-level fairness, LEVELLER introduces a novel online metric, normalized progress rate, which quantifies training experience by measuring actual progress against a contention-free ideal. We theoretically prove that a greedy, progress-rate-aware flow scheduling strategy achieves at least a 1/2-approximation of max-min fairness for arbitrary workloads, even with lazy priority updates. Building on theoretical results, LEVELLER employs preemptive, dynamic-priority scheduling to achieve near-optimal fairness on commodity infrastructure without hardware or protocol modifications. We prototype LEVELLER on both RDMA and TCP, evaluating it through a physical GPU cluster and trace-based simulations. Experimental results on 10 LLMs show that LEVELLER improves the minimum progress rate by 57% and fairness by 17% compared to state-of-the-art solutions (including CASSINI, CRUX, Symphony and Sincronia), while maintaining competitive cluster efficiency.
Geng Li, Yang Li, Mingyuan Zang et al.· Conference on Applications,...· 0 citations
GPU cluster operators cannot predict how long pending workloads will wait for admission. Existing systems use greedy heuristics with no formal wait time guarantees. We formalize GPU cluster admission as a multi-class, multi-resource queueing network and prove a structural decomposition: the pending queue partitions into quotable workloads (bounded wait time under stability) and unfeasible workloads (no finite bound without reconfiguration). For quotable workloads, we model each cluster queue as an M/G/k system where the effective server count k is determined by a vector packing reduction; under an explicit stochastic domination assumption, we establish O(1/(1-rho)) wait time scaling. We prove that optimal admission ordering is NP-hard under multi-dimensional resource demands via reduction from vector bin packing. We validate on Kueue, the standard Kubernetes workload queuing system, using CPU, memory, and GPU (via Dynamic Resource Allocation) resources. The vector k_eff correctly identifies bottleneck resource dimensions, Little's Law holds exactly, and the Erlang-C approximation consistently overestimates observed wait times in the conservative direction.
This work presents a robust KV cache management framework for LLM serving that jointly optimizes GPU parallelism configuration, KV cache reservation per request class, request routing across heterogeneous serving groups, and prefix caching for shared prompts that incorporates latency SLO constraints and captures the interaction between memory allocation, throughput, and queueing delay.
Jiaming Cheng, Duong The Do, D. Nguyen· arXiv.org· 1 citation· ⚡1
LazyTrain is proposed, an optimization layer over a layer-streaming executor that formulates checkpoint selection, activation placement, recomputation, and CPU-GPU-NVMe communication overlap as a mixed-integer scheduling problem, then executes the solved policy during training.
Xiao-Jun Wu, Cehao Yang, Honghao Liu et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
