# LLM Query Scheduling with Prefix Reuse and Latency Constraints

arXiv: https://arxiv.org/abs/2502.04677 · HTML: https://mlsanity.com/paper/2502.04677/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2025.

## Built on by (most cited first, 9 of 9)

- [CacheWise: Understanding Workloads and Optimizing KVCache Management for Efficiently Serving LLM Coding Agents](https://mlsanity.com/paper/2606.16824/) (2026)
- [Don't Pay Attention](https://mlsanity.com/paper/2506.11305/) (2025)
- [GORGO: Online Tuning for Cross-Region Network-Aware LLM Serving](https://mlsanity.com/paper/2602.11688/) (2026)
- [PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design](https://mlsanity.com/paper/2605.08581/) (2026)
- [RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving](https://mlsanity.com/paper/2606.17949/) (2026)
- [Scheduling Mixed RL Rollouts Beyond Prefix Locality](https://mlsanity.com/paper/2608.11152/) (2026)
- [PEEK: Predictive Queue-Informed KV Cache Management for LLM Serving](https://mlsanity.com/paper/2607.02525/) (2026)
- [Inference Auctions](https://mlsanity.com/paper/2609.40070/) (2026)
- [RadixFlow: Filling Execution Bubbles in Prefix-Cached Hybrid LLM Serving](https://mlsanity.com/paper/2610.18143/) (2026)

## Abstract (arXiv)

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, k-LPM, which generalizes existing methods by balancing prefix reuse and fairness in query processing. Theoretical guarantees demonstrate that k-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.