Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling
2026-08-03 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors studied how serving multiple language model requests together in batches can be inefficient when the requests have very different lengths. They show that a short request paired with a long one ends up taking more time and resources than it needs because the batch cost depends on the largest request. To fix this, they created a new scheduling method called ISJL that tries to keep resource use fair among requests and improve overall system speed. Their experiments show ISJL balances efficiency and cost better than common methods. They also prove ISJL has strong performance guarantees and fits well with pay-per-token pricing.
Large Language ModelsBatchingResource AllocationKV-cacheScheduling AlgorithmsLatencyThroughputToken-metered PricingCompetitive RatioHybrid Batching Policy
Authors
Dayi Yao, Zijie Zhou
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.