LLM Query Scheduling with Prefix Reuse and Latency Constraints
Gregory Dexter, Shao Tang, Ata Fatahi Baarzi, Qingquan Song, Tejas Dharamsi, Aman Gupta
Abstract
The efficient deployment of large language models (LLMs) in online settings requires optimizing inference performance under stringent latency constraints, particularly the time-to-first-token (TTFT) and time-per-output-token (TPOT). This paper focuses on the query scheduling problem for LLM inference with prefix reuse, a technique that leverages shared prefixes across queries to reduce computational overhead. Our work reveals previously unknown limitations of the existing first-come-first-serve (FCFS) and longest-prefix-match (LPM) scheduling strategies with respect to satisfying latency constraints. We present a formal theoretical framework for LLM query scheduling under RadixAttention, a prefix reuse mechanism that stores and reuses intermediate representations in a radix tree structure. Our analysis establishes the NP-hardness of the scheduling problem with prefix reuse under TTFT constraints and proposes a novel scheduling algorithm, -LPM, which generalizes existing methods by balancing prefix reuse and fairness in query processing. Theoretical guarantees demonstrate that -LPM achieves improved TTFT performance under realistic traffic patterns captured by a data generative model. Empirical evaluations in a realistic serving setting validates our findings, showing significant reductions in P99 TTFT compared to baseline methods.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve cites Splitwise: Efficient Generative LLM Inference Using Phase Splitting
- Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve cites DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
- Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve cites Orca: A Distributed Serving System for Transformer-Based Generative Models
- Splitwise: Efficient Generative LLM Inference Using Phase Splitting cites Orca: A Distributed Serving System for Transformer-Based Generative Models
- DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving cites Splitwise: Efficient Generative LLM Inference Using Phase Splitting
- DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving cites Orca: A Distributed Serving System for Transformer-Based Generative Models
- SGLang: Efficient Execution of Structured Language Model Programs cites Orca: A Distributed Serving System for Transformer-Based Generative Models
Builds on6
- SGLang: Efficient Execution of Structured Language Model ProgramsLianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun et al.NeurIPS 2024 · 1,586 citations
- Orca: A Distributed Serving System for Transformer-Based Generative ModelsGyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim et al.OSDI 2022 · 690 citations
- DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model ServingYinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu et al.OSDI 2024 · 646 citations
- Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-ServeAmey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan et al.OSDI 2024 · 537 citations
- Splitwise: Efficient Generative LLM Inference Using Phase SplittingPratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah et al.ISCA 2024 · 282 citations
Related papers
- Compute or Load KV Cache? Why Not Both?Shuowei Jin, Xueshen Liu, Qingzhao Zhang, Zhuoqing MaoICML 2025
- Online Context Caching for Distributed Large Language Models ServingBin Gao, Zhuomin He, Yizhen Yao, Zhanzhi Lou Lou et al.INFOCOM 2025 · 2 citations
- IMPRESS: An Importance-Informed Multi-Tier Prefix KV Storage System for Large Language Model InferenceWeijian Chen, Shuibing He, Haoyang Qu, Ruidong Zhang et al.FAST 2025 · 40 citations
- HotPrefix: Hotness-Aware KV Cache Scheduling for Efficient Prefix Sharing in LLM Inference SystemsYuhang Li, Rong Gu, Chengying Huan, Zhibin Wang et al.SIGMOD 2026 · 9 citations
- DeFT: Decoding with Flash Tree-attention for Efficient Tree-structured LLM InferenceJinwei Yao, Kaiqi Chen, Kexun Zhang, Jiaxuan You et al.ICLR 2025
