Search papers, labs, and topics across Lattice.
This paper addresses the inefficiencies in batched large language model (LLM) serving caused by heterogeneous requests that lead to disproportionate computational costs. By formalizing this issue as a resource-fair scheduling problem, the authors develop the Insert-Short-Jobs-with-Limit (ISJL) algorithm, which balances decode progress among co-batched requests while optimizing system throughput. The results demonstrate that ISJL achieves a competitive-ratio lower bound of 3/4, effectively aligning batching costs with token-metered revenue without sacrificing throughput.
ISJL strikes an optimal balance between throughput and cost alignment, outperforming traditional batching methods in LLM serving.
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.
