TLDR: A new algorithm, Sorted-F, is proposed to efficiently schedule Large Language Model (LLM) requests with varying input and output lengths, minimizing total completion time. It uses a novel “F-metric” to prioritize requests, outperforming traditional methods like First-Come-First-Serve and Shortest-First, which struggle with heterogeneous workloads. The algorithm achieves a constant competitive ratio, and practical approximation methods are also developed, demonstrating significant latency reduction in real-world simulations.
Large Language Models, or LLMs, are at the heart of many modern AI applications, from chatbots to content generation. However, making these powerful models respond quickly and efficiently, especially when handling many user requests at once, is a significant challenge. A new research paper titled LLM Serving Optimization with Variable Prefill and Decode Lengths by Meixuan Wang, Yinyu Ye, and Zijie Zhou tackles this very problem, proposing a novel approach to optimize how LLMs serve these diverse requests.
When you interact with an LLM, your input (the prompt) is processed first. This is called the ‘prefill’ phase. After that, the model generates its response token by token, which is the ‘decode’ phase. The length of your prompt (prefill length) and the length of the model’s response (decode length) can vary greatly. For example, a short question has a small prefill and decode, while summarizing a long document involves a large prefill and potentially a long decode. This variability creates a headache for LLM servers because each token generated or processed consumes memory in what’s called the Key-Value (KV) cache.
The core issue is how to schedule these diverse requests to minimize the total time it takes for all of them to complete. Traditional scheduling methods, like First-Come-First-Serve (FCFS) or Shortest-First (prioritizing requests with shorter outputs), struggle when both input and output lengths are highly variable. The paper demonstrates that these common strategies can perform very poorly in real-world scenarios where memory demand is high. This is because a short output request might have a very long input, consuming a lot of initial memory, or vice-versa, making simple prioritization ineffective. The researchers even prove that this generalized scheduling problem is incredibly complex, falling into a category known as NP-hard, meaning there’s no easy, fast way to find the absolute best solution.
To overcome these limitations, the authors introduce a new algorithm called ‘Sorted-F’. This algorithm is designed to efficiently form batches of requests over time. At its heart is a unique ‘F-metric’ that evaluates each request by considering both its input and output characteristics. A smaller F-metric value indicates higher scheduling priority. This metric helps the system balance the size of the batch (how many requests can be processed together) and the expected response lengths, leading to better overall efficiency.
The paper illustrates the power of Sorted-F with a simple example: imagine a scenario where a traditional ‘shortest-first’ method would prioritize a single, very short output request that has a large input, blocking many smaller, quicker requests. Sorted-F, using its F-metric, would instead prioritize a batch of many small requests, leading to a significantly faster total completion time. This demonstrates how the F-metric intelligently guides the scheduler to make more optimal decisions by considering the full picture of memory usage and processing time.
Sorted-F operates in two phases: first, it constructs optimal batches using the F-metric, sorting requests within each batch by their output length. Then, it executes these batches in real-time, dynamically admitting new requests as memory becomes available. The algorithm is proven to achieve a ‘constant competitive ratio’, which is a strong theoretical guarantee meaning its performance is always within a predictable, small factor of the absolute best possible schedule, regardless of the complexity of the requests.
Recognizing that finding the absolute optimal batch using the F-metric can still be computationally intensive for very large numbers of requests, the researchers also developed several practical approximation methods. These include exact and scaled dynamic programming for smaller to moderate workloads, a ‘local swap search’ heuristic for larger sets, and a ‘quantile greedy selection’ for very large-scale systems. Each method offers a different trade-off between solution quality and computational speed, providing system designers with flexible options.
Also Read:
- Optimizing Language Model Compression with Selective Reflection Distillation
- Language Models Compete to Reveal Their Strengths and Weaknesses: An Overview of SKATE
Furthermore, the paper explores extensions using Linear Programming (LP) formulations, which are mathematical optimization techniques. They introduce ‘Sorted-LP’, which uses insights from a relaxed LP solution to prioritize requests, and ‘LP-Swap’, a hybrid approach that combines Sorted-LP’s initial ordering with the F-metric-guided local swaps. Numerical experiments using real-world datasets (combining short conversational prompts with long document summarization tasks) show that Sorted-F and LP-Swap significantly outperform traditional methods like FCFS and MC-SF, validating the effectiveness of their proposed F-metric and scheduling strategies in handling diverse LLM workloads.
