🤖 machine learning

LLM Serving Optimization with Variable Prefill and Decode Lengths

This paper addresses the NP-hard problem of offline LLM serving scheduling under fixed KV-cache constraints with heterogeneous request lengths by proposing the Sorted-F algorithm, which achieves a constant-factor approximation guarantee and significantly reduces end-to-end latency compared to standard baselines.

Original authors: Meixuan Wang, Yinyu Ye, Zijie Zhou

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Meixuan Wang, Yinyu Ye, Zijie Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a very busy, high-tech kitchen (the AI server). Your job is to cook meals (generate answers) for customers (users) as fast as possible.

In this kitchen, every meal has two parts:

Prep Work (Prefill): Reading the recipe and chopping ingredients. This takes up counter space immediately.
Cooking (Decode): Actually cooking the dish. This happens step-by-step, and as you cook, you keep the pot on the stove, which continues to take up space.

The big problem? Your kitchen has a fixed amount of counter space (KV-cache memory). You can’t just throw every order onto the counter at once; you have to manage who gets space and when.

The Old Way vs. The New Problem

Previously, researchers assumed all recipes were roughly the same size. If everyone had similar prep work and cooking times, the best strategy was simple: "Shortest Job First." You’d cook the quick meals first to clear the counter.

But in the real world, orders are messy.

Order A: A tiny recipe (short prep) but takes forever to simmer (long cooking). It takes up little space but stays on the stove for a long time.
Order B: A massive recipe (huge prep) but cooks in seconds (short cooking). It hogs the counter instantly but clears out quickly.

The paper shows that if you stick to the old "Shortest Job First" rule in this messy environment, you can make a huge mistake. You might pick Order A because it’s "short" to cook, but it blocks the counter for ages, preventing you from handling the quick, space-hogging Order B. The authors prove that this old method can perform terribly—mathematically speaking, its performance can get infinitely worse than the best possible schedule.

The Solution: The "F-Metric"

The authors propose a new scheduling algorithm called Sorted-F. Instead of just looking at how long the cooking takes, it uses a new score called the F-Metric.

Think of the F-Metric as a "Throughput Density" score. It asks: "How many meals can we finish per unit of time, given how much counter space we’re using?"

It balances batch size (how many orders we can fit on the counter at once) against cooking time (how long they stay there).
It prefers batches that are "efficient"—meaning they pack a lot of work into the available space without clogging the kitchen for too long.

Why It Works

The authors prove that this new method is mathematically robust. Even in the worst-case scenarios, Sorted-F will never be more than 48 times worse than the absolute perfect schedule (which is impossible to calculate in real-time because the problem is too complex). In practice, it performs much better than that, often coming very close to the theoretical best.

Real-World Test

They tested this on real data, mixing short chat messages with long document summaries.

The Result: Sorted-F was significantly faster than the old methods.
The Insight: The biggest gains happened when the workload was mixed (some short, some long) and the kitchen was nearly full. If everyone had similar orders, the old methods were okay. But when orders varied wildly, Sorted-F shone.

Practical Tweaks

Since calculating the perfect "F-Metric" batch for thousands of orders is hard, they also provided simpler, faster versions for different situations:

Exact Method: For small batches, calculate the perfect score.
Local Swap: For medium batches, make a good guess and then swap orders around to improve it.
Quantile Greedy: For huge batches, use a quick statistical shortcut to pick the best candidates.

They also addressed the fact that we don’t always know exactly how long an answer will be. They integrated a "safety valve" system that starts with an optimistic guess but adjusts in real-time if an answer turns out to be longer than expected, kicking out the least efficient orders to make room.

The Bottom Line

This paper says: Don’t just look at how long an AI answer takes to write. Look at how much memory it uses while writing. By balancing the "prep space" and "cooking time" with the new F-Metric, AI servers can handle mixed workloads much more efficiently, reducing wait times for everyone.

Technical Summary: LLM Serving Optimization with Variable Prefill and Decode Lengths

1. Problem Statement and Motivation
This paper addresses the offline scheduling of Large Language Model (LLM) inference on a single computational worker with a fixed Key-Value (KV) cache memory budget. The core challenge arises from heterogeneous request lengths, where requests possess varying prompt (prefill) sizes ( $s_i$ ) and response (decode) lengths ( $o_i$ ).

In modern LLM serving, inference consists of two phases: prefill (processing the input prompt) and decode (autoregressively generating output tokens). The KV cache memory consumption grows linearly during the decode phase as each generated token requires additional memory. While prior work (e.g., Jaillet et al. 2025) established scheduling policies for uniform input sizes, this paper argues that relaxing the uniform input size assumption fundamentally alters the problem landscape. In mixed workloads (e.g., combining short conversational prompts with long-document summarization), the trade-off between immediate memory availability and future decode duration becomes complex. The objective is to minimize Total End-to-End Latency (TEL), defined as the sum of completion times for all requests in a backlogged queue.

2. Theoretical Challenges and Negative Results
The authors first establish the hardness of the generalized scheduling problem:

NP-Hardness: They prove that minimizing TEL with heterogeneous input and output lengths is NP-hard via a reduction from the restricted 3-Partition problem.
Failure of Standard Policies: They demonstrate that standard heuristics, including First-Come-First-Served (FCFS), Shortest-Output-First (MC-SF), and total-size-based prioritization, suffer from unbounded approximation ratios when input sizes vary. Specifically, MC-SF can perform arbitrarily poorly because it fails to account for the memory pressure exerted by large prefill sizes relative to decode duration.

3. Methodology: The Sorted-F Algorithm
To address these challenges, the paper proposes Sorted-F, a scheduling algorithm that achieves a constant-factor approximation guarantee. The algorithm operates in two phases:

Phase 1 (Batch Construction): The algorithm constructs an ordered list of requests by iteratively selecting feasible batches that minimize a quality metric $F(X)$ . For a batch $X$ , the metric is defined as:
$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$
This metric balances batch cardinality ( $|X|$ ) against the total decode cost ( $\sum o_i$ ). Minimizing $F(X)$ is equivalent to maximizing "throughput density" (requests completed per unit of average decode time). Ties are broken by preferring larger batches.
Phase 2 (Execution): The algorithm executes the schedule over discrete time steps. It maintains sets of pending, active, and newly admitted requests. At each step, it admits requests from the ordered list generated in Phase 1, subject to dynamic memory feasibility checks that account for the growing KV cache usage of active requests.

4. Theoretical Guarantees
The authors prove that Sorted-F achieves a constant approximation ratio of at most 48 against the optimal offline schedule. The proof involves a series of transformations:

Separation: Transforming the schedule to enforce non-overlapping batches.
Grouping: Aggregating batches into groups that nearly saturate memory.
Alignment: Aligning response lengths within terminal batches.
Comparison: Comparing the transformed Sorted-F schedule against a similarly transformed optimal schedule.

5. Practical Implementations and Approximations
Since the exact batch selection in Phase 1 is combinatorially hard, the paper develops three practical solvers for different scale regimes:

Exact Dynamic Programming: An $O(n^2M)$ algorithm suitable for small instances ( $n \le 100$ ).
Local Swap Search: A heuristic with $O(n^2)$ complexity that refines an initial greedy solution via pairwise exchanges, suitable for moderate scales ( $n \le 500$ ).
Quantile Greedy Selection: A linear-time $O(n)$ heuristic that uses statistical sampling to filter outliers and fill capacity, suitable for large-scale deployments ( $n \ge 1000$ ).

Additionally, the paper introduces Sorted-LP and LP-Swap, heuristics derived from the Linear Programming (LP) relaxation of the integer programming formulation. Sorted-LP uses the LP solution’s expected start times to order requests, while LP-Swap combines this ordering with F-metric-guided local swaps.

6. Handling Prediction Uncertainty
Recognizing that output lengths are often predicted rather than known, the paper integrates an adaptive refinement strategy (from Chen et al. 2025) into Sorted-F, termed Sorted-F+Amin. This approach starts with optimistic lower-bound predictions and dynamically updates estimates based on actual generation progress. If memory overflow is projected, it employs ordered eviction, removing requests with the smallest current estimates first to minimize wasted computation.

7. Experimental Results
The authors evaluate their methods on mixed workloads combining the LMSYS-Chat dataset (short conversations) and the Arxiv long-document summarization dataset.

Performance: Sorted-F (using Local Swap Search) consistently outperforms baselines (FCFS, MC-SF, Sorted-LP). In an 80/20 short/long mixture with $n=2000$ , Sorted-F reduced average latency by 4.87 $\times$ compared to FCFS and 2.09 $\times$ compared to MC-SF.
Optimality Gap: On smaller tractable instances, Sorted-F’s performance remained within 1.03–1.09 of the LP relaxation lower bound, significantly tighter than the worst-case theoretical bound of 48.
Sensitivity: The benefits of heterogeneous scheduling are most pronounced in mixed workloads with high dispersion in request lengths. In homogeneous workloads, simpler policies perform comparably.
Online Regime: A preliminary experiment with Poisson arrivals showed that a receding-horizon variant (Sorted-F-Online) significantly outperformed MC-SF and FCFS in overloaded regimes (normalized load $\rho > 1$ ), reducing mean latency by up to 40% compared to MC-SF at high loads.

8. Significance and Contributions
The paper claims the following key contributions:

Theoretical Characterization: It formally establishes that heterogeneous prefill lengths make LLM scheduling NP-hard and render standard priority rules ineffective, justifying the need for new approaches.
Algorithm Design: It introduces Sorted-F, the first algorithm with a provable constant-factor approximation guarantee for this generalized problem.
Practical Scalability: It provides a suite of scalable heuristics (DP, Local Swap, Quantile Greedy) tailored to different deployment scales, along with LP-guided variants.
Empirical Validation: It demonstrates through extensive experiments that F-metric-based scheduling significantly reduces latency in realistic, mixed workloads and remains robust under prediction uncertainty and online arrival patterns.

The paper concludes that memory-aware scheduling is critical for LLM serving systems handling heterogeneous workloads, particularly when operating near KV-cache capacity limits.