Research map / Large language models / Reasoning and chain of thought
LLM Query Scheduling with Prefix Reuse and Latency Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes query scheduling under RadixAttention prefix reuse with TTFT constraints, proves NP-hardness, and proposes k-LPM, which interpolates between FCFS and LPM and reduces P99 TTFT in SGLang experiments.
Problem
LLM query scheduling with prefix reuse (RadixAttention) under latency constraints (TTFT); existing FCFS and LPM schedulers can produce large TTFT spikes under heavy traffic.
Approach
A formal computational model of RadixAttention scheduling shows decision of TTFT feasibility is NP-hard; the k-LPM algorithm performs k greedy longest-prefix-match steps then serves the oldest query, generalizing FCFS (k=1) and LPM (k=inf) and provably lowering max TTFT on a tree-structured random arrival model.
Key results
- k=2 k-LPM achieves reduced P99 TTFT across a wide range of request rates compared to FCFS and LPM on Llama-3.1-8B-Instruct served with SGLang v0.4.1 on eight A100s.
- Theorem gives max TTFT upper bound for k-LPM of T + n(u/k + d - s/k), versus lower bounds for LPM and FCFS of order n(u/k+d) and n(u+d-s) respectively on the regular arrival shuffled queue.
- Scheduling feasibility under a TTFT constraint is NP-hard via reduction from 3-PARTITION when prefix reuse and non-uniform arrivals are present.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use k-LPM (k=4) instead of FCFS | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=1000, d=5000), 80 requests/s | Median TTFT: 3466.21 -> 1940.35 | Helped |
| Use k-LPM (k=4) instead of FCFS | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=1000, d=5000), 80 requests/s | P90 TTFT: 5604.33 -> 8610.27 | Hurt |
| Use k-LPM (k=4) instead of LPM | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=1000, d=5000), 80 requests/s | Median TTFT: 677.07 -> 1940.35 | Hurt |
| Use k-LPM (k=4) instead of LPM | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=1000, d=5000), 80 requests/s | P90 TTFT: 11297.53 -> 8610.27 | Helped |
| Use k-LPM (k=4) instead of FCFS | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=3000, d=3000), 80 requests/s | Median TTFT: 509.93 -> 177.40 | Helped |
| Use k-LPM (k=4) instead of LPM | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=3000, d=3000), 80 requests/s | Median TTFT: 176.32 -> 177.40 | Hurt |
| Use k-LPM (k=4) instead of LPM | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=3000, d=3000), 80 requests/s | P90 TTFT: 1245.15 -> 821.41 | Helped |
| Use k-LPM (k=4) instead of FCFS | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=5000, d=1000), 80 requests/s | P90 TTFT: 524.91 -> 273.55 | Helped |
| Use k-LPM (k=4) instead of LPM | LLM query scheduling with prefix reuse · Regular Arrival Shuffled Queue (u=5000, d=1000), 80 requests/s | P90 TTFT: 216.88 -> 273.55 | Hurt |
Surprising findings
- LPM, despite maximizing prefix reuse, can starve queries and yield high tail TTFT; FCFS wins at low request rates and at small prefix ratios.
Limitations
- Computational model assumes only the last processed prompt is cached and batch size one, an approximation of RadixAttention with a fixed memory pool.
- Theoretical improvement is proven only for a specific height-two tree data generative model with regular arrivals.
- Hyperparameter k must be tuned (back-testing or bandits); the paper does not provide an automatic selection method.
Experimental setup
Datasets: 360Brew industrial prompt dataset (8k context prompts)
Benchmarks: SGLang serving benchmark on 360Brew-derived prompts
Metrics: P99 TTFT P50 TTFT P90 TTFT P95 TTFT TPOT
Baselines: FCFS LPM
Builds on: RadixAttention SGLang LPM scheduler roofline model
Closest papers by meaning
- Efficient LLM Scheduling by Learning to Rank (NeurIPS 2024 · similarity 0.90)
- Fast Inference for Augmented Large Language Models (NeurIPS 2025 · similarity 0.89)
- Efficient Multi-round LLM Inference over Disaggregated Serving (ICML 2026 · similarity 0.89)
- QUEST: Query-Aware Sparsity for Efficient Long-Context LLM Inference (ICML 2024 · similarity 0.88)
- SparQ Attention: Bandwidth-Efficient LLM Inference (ICML 2024 · similarity 0.87)
- Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.