mlsanityData to 14 Oct 2026

LLM Serving Optimization with Variable Prefill and Decode Lengths

arXiv 2508.06133 ↗First posted 8 Aug 2025math.OC cs.AI cs.LGcited by 7

On the map: Efficient LLM inference and serving → Serving systems and request scheduling

Abstract (arXiv)

We study offline scheduling for large language model (LLM) serving under a fixed KV-cache memory budget, where requests have heterogeneous prompt (prefill) and response (decode) lengths. Given a backlog of requests available at time zero, the scheduler forms mixed prefill/decode batches over time to minimize total end-to-end latency. We show that heterogeneity in prompt lengths fundamentally changes the problem: minimizing total latency is NP-hard, and standard policies that prioritize short outputs or small total sequence sizes can have unbounded approximation ratios. We propose Sorted-F, which repeatedly selects feasible batches using an F-metric that balances batch cardinality against downstream decode cost. With exact batch selection, Sorted-F achieves a constant-factor approximation guarantee in the unit-time, uninterrupted-decoding model with known output lengths; the guarantee also holds under a static peak-memory batch constraint. We develop an exact pseudopolynomial dynamic program for this static subproblem, scalable local-search and greedy heuristics, LP-guided variants, and a receding-horizon online extension. Experiments on public conversational and long-document summarization workloads show that F-metric-based scheduling substantially reduces latency relative to standard baselines and remains close to the LP relaxation lower bound on tractable instances.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving. Builds on 21 of its 51 references that are in the map. First posted on arXiv 8 Aug 2025.

Builds on

21 of 51 references.

Closest ancestors · 7

Same direction, newest first

  1. 2025Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents10 Apr
  2. 2024Efficient LLM Scheduling by Learning to Rank28 Aug
  3. 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction12 Apr
  4. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve4 Mar
  5. 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving18 Jan
  6. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills31 Aug
  7. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline22 May

Other references · 14

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2020Scaling Laws for Neural Language Modelscited by 6,586
  4. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  5. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  6. 2023Splitwise: Efficient generative LLM inference using phase splittingcited by 558
  7. 2018A Discourse-Aware Attention Model for Abstractive Summarization of Long Documentscited by 478
  8. 2023LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Datasetcited by 461
  9. 2023A Study of Generative Large Language Model for Medical Research and Healthcarecited by 163
  10. 2024Vidur: A Large-Scale Simulation Framework For LLM Inferencecited by 117
  11. 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 35
  12. 2025Online Scheduling for LLM Inference with KV Cache Constraintscited by 19
2 more
  1. 2025Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraintscited by 19
  2. 2019Non-clairvoyant Precedence Constrained Schedulingcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 6.

7 papers.

  1. 2025Adaptively Robust LLM Inference Optimization under Prediction Uncertaintycited by 10
  2. 2026A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraintscited by 2
  3. 2026Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristicscited by 1
  4. 2026SISA: A Scale-In Systolic Array for GEMM Accelerationcited by 0
  5. 2026Flow-Controlled Scheduling for LLM Inference with Provable Stability Guaranteescited by 0
  6. 2026Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scalecited by 0
  7. 2026Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practicecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Apt-Serve: Adaptive Request Scheduling on Hybrid Cache for Scalable LLM Inference Serving
  2. 2026AlignedServe: Orchestrating Prefix-aware Batching to Build a High-throughput and Computing-efficient LLM Serving System
  3. 2024Llumnix: Dynamic Scheduling for Large Language Model Serving
  4. 2026PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design
  5. 2026Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling
  6. 2026Towards Multi-Model LLM Schedulers: Empirical Insights into Offloading and Preemption
  7. 2025Hybrid Offline-online Scheduling Method for Large Language Model Inference Optimization
  8. 2025Ranking Before Serving: Low-Latency LLM Serving via Pairwise Learning-to-Rank