Metraipolis › archive › dc_c02871b7ea34

Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint — arXiv:2611.04807

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04807
License (as archived): CC0-1.0
Archived: 2026-11-04T18:37:19.091Z
SHA-256 of the archived text: 0ecfec73edb75084fa5b1827883fba8139c7c17679d5accf8ea4813275881ee6
Stable URL of this page: https://metraipolis.com/documento/dc_c02871b7ea34

How to cite

Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint — arXiv:2611.04807 — arXiv (en), https://arxiv.org/abs/2611.04807 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c02871b7ea34 (Metraipolis archive dc_c02871b7ea34, sha256 0ecfec73edb75084fa5b1827883fba8139c7c17679d5accf8ea4813275881ee6)

BibTeX

@misc{dcc02871b7ea34,
  title = {Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint — arXiv:2611.04807},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04807},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c02871b7ea34; sha256 0ecfec73edb75084fa5b1827883fba8139c7c17679d5accf8ea4813275881ee6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04807. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Large language model (LLM) inference, the process by which a pre-trained model receives an input prompt and generates output tokens sequentially, has become increasingly important with the widespread deployment of LLM-based applications. As inference workloads continue to scale, GPU memory has emerged as a critical bottleneck: the long input prompts and generation sequences common in agentic and reasoning workloads lead to substantial key-value (KV) cache usage. In this paper, we study the resulting online scheduling problem from a queueing perspective. Requests arrive stochastically with heterogeneous prompt and output lengths, undergo prefill and autoregressive decode, and compete for a finite KV-cache capacity. Unlike classical queueing models, the duration of a processing step depends on both prefill computation and KV-cache I/O, so service capacity is jointly determined by computation, memory access, and memory occupancy. We develop a fluid model that reduces the system to a multiclass single-server queue with effective service rates capturing computation, memory access, and memory capacity. This fluid analysis yields a $c\mu$ priority rule, where the effective service rate $\mu$ is jointly determined by computational speed, memory bandwidth, and memory capacity. We prove that this rule minimizes cumulative holding cost in the fluid model and, for a finite workload, also minimizes completion time and maximizes full-run output-token throughput. We then construct a feasible scheduling policy for the original finite system and prove that its scaled dynamics converge to the optimal fluid policy. Finally, experiments on a real LLM serving engine using an NVIDIA H800 show that practical implementations of the proposed priority rule substantially reduce average latency while maintaining high throughput relative to existing scheduling policies.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.04807 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:32:37.465Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).