AI
New Scheduling Algorithm Cuts LLM Serving Latency by Optimizing Mixed Prefill-Decode Batches
Researchers develop an approximation algorithm that addresses the NP-hard problem of scheduling language model requests with varying prompt and response lengths.
Large language model serving faces a fundamental scheduling challenge: how to batch requests efficiently when both prompts and responses vary in length, all within a fixed memory constraint. A new paper from arXiv tackles this problem head-on, showing that traditional scheduling approaches fall short and proposing a solution that meaningfully reduces end-to-end latency.
The Core Problem#
When an LLM processes user requests, each query involves two computational phases. During prefill, the model ingests the user's prompt (which can range from a few words to thousands of tokens). During decode, it generates the response one token at a time. Both phases compete for the same memory pool—the KV-cache—which stores attention weights for acceleration.
The challenge emerges because prefill and decode have opposite cost profiles. A batch with many long prompts burns memory quickly during prefill but uses little during subsequent decode. Conversely, a batch with short prompts but long responses is cheap at first but expensive later. The scheduler must decide which requests to batch together and when to execute each batch to minimize total latency across all requests.
Why Standard Approaches Fail#
Researchers proved that minimizing latency with heterogeneous prompt and response lengths is NP-hard—there's no known polynomial-time algorithm guaranteed to find the optimal solution. More surprisingly, greedy heuristics commonly used in practice can perform arbitrarily badly. Policies that prioritize short outputs or small total sequence sizes can have unbounded approximation ratios, meaning they may do exponentially worse than the optimal schedule.
The Sorted-F Algorithm#
To address this gap, the team proposes Sorted-F, a scheduling algorithm that repeatedly selects feasible batches using a custom metric balancing two competing objectives: the number of requests in a batch against the downstream decode cost they will incur.
The algorithm achieves a constant-factor approximation guarantee—a formal promise that its latency is no more than some fixed multiple of the optimal schedule—under the unit-time, uninterrupted-decoding model with known output lengths. This theoretical guarantee also holds under static peak-memory batch constraints, a practical setting for production systems.
