Algorithms improve scheduling of memory use in disaggregated llm inference
Approximation Algorithms for Dual-Memory Request Scheduling in Disaggregated LLM Inference
Data Structures and Algorithms
Summary
Running large language models (LLMs) can be split into two steps—prefill and decode—using separate resources to reduce interference, but this splits memory in a tricky way. The authors identify and define a new scheduling problem that balances memory use and speeds up how fast requests finish in this setup. They prove the problem is hard to solve perfectly but create two algorithms that guarantee solutions close to the best possible in reasonable time. Tests on real hardware show these algorithms help complete requests faster than previous methods.
What this means in practice
- •For cloud infrastructure teams: Optimize scheduling of LLM requests to reduce total completion times using disaggregated GPU memory setups.
- •For machine learning platform engineers: Deploy approximation-based schedulers to improve resource efficiency in large language model serving systems.
Authors
Xin Wang, Hong Shen, Hui Tian, Ye Tao
Abstract
Disaggregated LLM inference executes the prefill and decode phases on separate resource pools, reducing interference between the two phases. However, this architecture introduces a coupled scheduling problem because a request that completes prefill retains its prompt KV cache in prefill memory until it is admitted to the decode pool. Prefill and decode admission decisions therefore jointly determine memory occupancy and request completion times. To the best of our knowledge, this problem lacks a formal formulation, and no approximation guarantees are known for request scheduling in disaggregated LLM inference. We formalize this setting as the dual-memory request scheduling (DMRS) problem, whose objective is to minimize the sum of request completion times, and prove that it is strongly NP-hard. We develop two deterministic polynomial-time approximation algorithms. The first applies to instances satisfying $α<1$ and $β<1$ and achieves an approximation ratio of $8+\frac{4}{1-α}+\frac{8}{1-β}$, where $α$ and $β$ are the maximum normalized prefill and peak decode memory demands among all requests, respectively. In particular, it yields a $32$-approximation when $α,β\leq 1/2$. The second algorithm applies to all feasible instances and achieves a uniform $36$-approximation. Finally, evaluations on two H100 GPUs using trace-derived offline workloads show that the proposed algorithms reduce the sum of request completion times relative to multiple vLLM deployment baselines.