LLM Serving Optimization with Variable Prefill and Decode Lengths

Meixuan Wang, Yinyu Ye, Zijie Zhou · 2025

Read LLM Serving Optimization with Variable Prefill and Decode Lengths by Meixuan Wang, Yinyu Ye, Zijie Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06133.txt.

Introduction

Meixuan Wang, Yinyu Ye, and Zijie Zhou study scheduling for language model serving in a 2025 paper. Each request needs a reading phase for its prompt and a writing phase for its reply, and lengths vary widely. With a fixed memory budget, the order of batching requests sets total waiting time.

They show that varied prompt lengths make the problem formally hard, and that simple rules like shortest-first can fail badly. Their Sorted-F method builds batches by a score that weighs batch size against later writing cost. It carries a proven quality bound in a clean model and runs well in tests on chat and document workloads, landing close to the best bound known.

Catalog record

CREATORMeixuan Wang, Yinyu Ye, Zijie Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06133

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LLM Serving Optimization with Variable Prefill and Decode Lengths Meixuan Wang, Yinyu Ye, Zijie Zhou Abstract We study the problem of serving LLM (Large Language Model) requests where each request has heterogeneous prefill and decode lengths. In LLM serving, the prefill length corresponds to the input prompt length, which determines the initial memory usage in the KV cache. The decode length refers to the number of output tokens generated sequentially, with each additional token increasing the KV cache memory usage by one unit. Given a set of n requests, our goal is to schedule and process them to minimize the total completion time. We show that this problem is NP-hard due to the interplay of batching, placement constraints, precedence relationships, and linearly increasing memory usage. We then analyze commonly used scheduling strategies in practice, such as First-Come-First-Serve (FCFS) and Shortest-First (SF), and prove that their competitive ratios scale up sublinearly with the memory limit—a significant drawback in real-world settings where memory demand is large. To address this, we propose a novel algorithm based on a new selection metric that efficiently forms batches over time. We prove that this algorithm achieves a constant competitive ratio. Finally, we develop and evaluate a few algorithm variants inspired by this approach, including dynamic programming variants, local search methods, and an LP-based scheduler, demonstrating through comprehensive simulations that they outperform standard baselines while maintaining computational efficiency. † † authors: Department of Computer Science and Technology, Tsinghua University, [email protected] Department of Management Science and Engineering, Stanford University & Department of Industrial Engineering and Decision Analytics, HKUST, [email protected] Department of Industrial Engineering and Decision Analytics, HKUST, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction Modern large-scale language models ( Brown et al. 2020 , Chowdhery et al. 2023 , OpenAI 2023 , Kaplan et al. 2020 , Wei et al. 2022 ) have revolutionized artificial intelligence by demonstrating unprecedented capabilities in natural language generation across diverse linguistic domains and situational contexts. These sophisticated neural networks, trained on extensive corpora of textual data, now serve as foundational components for numerous real-world applications. Their deployment spans conversational agents ( Anthropic 2023 , Character 2021 , OpenAI 2019 , OpenAI 2023 ) , information retrieval systems ( Microsoft 2023 , Google 2023 , Komo 2023 , Perplexity 2022 , You.com 2020 ) , programming aids ( Amazon 2023 , GitHub 2021 , Replit 2018 ) , and even clinical decision support tools ( Cascella et al. 2023 , Peng et al. 2023 , Sallam 2023 ) , demonstrating remarkable versatility in professional and consumer domains alike. Efficient inference represents a fundamental challenge in large language model deployment, focusing on how models process input prompts and generate responses with minimal latency. The inference pipeline consists of two distinct phases. (1) Prefill: processing the input prompt (a user-submitted text sequence), and (2) Decode: autoregressively generating output tokens (where each token typically corresponds to a word or sub-word unit). Modern LLMs universally employ the Transformer architecture ( Vaswani et al. 2017 ) for this process. For instance, when processing the prompt “Why is the sea blue?”, the model first tokenizes it into discrete units (“Why”, “is”, “the”, “sea”, “blue”, “?”), then sequentially generates output tokens (e.g., beginning with “Because”) while considering both the prompt and previously generated tokens at each step. The core computational challenge emerges in multi-request scenarios, where the system must optimally schedule numerous concurrent inference tasks. This scheduling problem requires careful balancing of computational resources to minimize user-perceived latency, particularly given the autoregressive nature of token generation and the variable length of both input prompts and output responses. The scheduling problem in LLM inference presents unique challenges that distinguish it from traditional scheduling tasks, primarily due to its dynamic memory constraints. During inference, each computational worker maintains a fixed Key-Value (KV) cache memory capacity, where keys and values represent contextual embeddings derived from both input tokens and autoregressively generated output tokens. The memory capacity depends on the hardware of each worker and the complexity of the LLM used. This memory system exhibits two critical behaviors: (1) it must retain all processed tokens from the prefill input prompt, and (2) its consumption grows linearly during decode generation as each newly generated output token requires additional KV cache allocation. The memory growth pattern creates complex scheduling dynamics when combined with parallel processing requirements. Unlike traditional systems where task resource demands remain static, LLM inference exhibits variable memory pressure - the number of concurrent requests a worker can handle fluctuates dynamically based on each request’s generation progress. This nonlinear relationship between sequence length and memory consumption fundamentally transforms the scheduling task. The challenge is further compounded by the need to balance immediate memory availability against anticipated future demands as generation progresses across multiple concurrent requests. Jaillet et al. 2025 established a theoretical model for LLM inference scheduling on a single computational worker, proposing a shortest-first scheduling policy that prioritizes requests with fewer output tokens. Their approach dynamically batches requests while respecting memory constraints, demonstrating both theoretical and numerical effectiveness under the condition of uniform input sizes. However, this condition may not always hold in practice, where workers typically handle mixed workloads (e.g., combining short conversational prompts with lengthy document summarization tasks). Relaxing this condition fundamentally changes the scheduling problem. With variable prefill input sizes, the relationship between processing time, memory usage, and optimal scheduling becomes significantly more complex. For instance, a request with a large input but small output may consume substantial memory yet finish quickly, while one with a small input but long output may occupy a small memory for an extended period. This trade-off makes prioritization non-trivial, as the previously effective shortest-first heuristic becomes inadequate. In Section 2.1 , we formally analyze these challenges and demonstrate that the generalized scheduling problem is NP-hard and that existing algorithms perform poorly without the uniform input size assumption. 1.1 Main Contribution In this section, we introduce the main contributions and the roadmap of this paper. Negative Results for Existing Scheduling Algorithms and NP-hardness. In Section 2 , we first establish fundamental limitations of current methods by analyzing the model in Jaillet et al. 2025 under realistic conditions. Our key theoretical findings reveal that: (1) without uniform input sizes, both first-come-first-serve and shortest-first scheduling yield unbounded competitive ratios (regardless of using output length or total sequence length as the metric), and (2) the general scheduling problem is NP-hard. These results formally justify the challenge need for new scheduling approaches. Polynomial Time Scheduling Algorithm with Constant Competitive Ratio. In Section 3 , we introduce Sorted-F , a novel scheduling algorithm that achieves both computational efficiency and provable performance guarantees. The algorithm operates through three key steps: (1) it first evaluates each request using our designed quality metric, which comprehensively considers both input and output characteristics; (2) it then partitions requests into prioritized batches based on this metric; and (3) within each batch, it applies shortest-output-first prioritization. Crucially, we prove that Sorted-F maintains a constant competitive ratio of at most 48, independent of problem scale – a significant improvement over existing approaches that suffer from unbounded ratios in general cases. The proof, presented in

Read the complete text