# Preble: Efficient Distributed Prompt Scheduling for LLM Serving

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

## Key facts

- Cited by 70 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 36 of its 69 references that are in the map.
- First posted on arXiv 8 May 2024.

## Placed in

- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

## Builds on (most cited first, 30 of 36)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Taming Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2012.09841/) (2020)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [NExT-QA:Next Phase of Question-Answering to Explaining Temporal Actions](https://mlsanity.com/paper/2105.08276/) (2021)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Ring Attention with Blockwise Transformers for Near-Infinite Context](https://mlsanity.com/paper/2310.01889/) (2023)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedback](https://mlsanity.com/paper/2309.10691/) (2023)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [DeepSpeed Ulysses: System Optimizations for Enabling Training of Extreme Long Sequence Transformer Models](https://mlsanity.com/paper/2309.14509/) (2023)
- [ToolkenGPT: Augmenting Frozen Language Models with Massive Tools via Tool Embeddings](https://mlsanity.com/paper/2305.11554/) (2023)
- [Agent Hospital: A Simulacrum of Hospital with Evolvable Medical Agents](https://mlsanity.com/paper/2405.02957/) (2024)
- [Self-Chained Image-Language Model for Video Localization and Question Answering](https://mlsanity.com/paper/2305.06988/) (2023)
- [LooGLE: Can Long-Context Language Models Understand Long Contexts?](https://mlsanity.com/paper/2311.04939/) (2023)
- [Leave No Context Behind: Efficient Infinite Context Transformers with Infini-attention](https://mlsanity.com/paper/2404.07143/) (2024)

## Built on by (most cited first, 30 of 70)

- [Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving](https://mlsanity.com/paper/2407.00079/) (2024)
- [Autellix: An Efficient Serving Engine for LLM Agents as General Programs](https://mlsanity.com/paper/2502.13965/) (2025)
- [Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live](https://mlsanity.com/paper/2511.02230/) (2025)
- [TAPAS: Thermal- and Power-Aware Scheduling for LLM Inference in Cloud Platforms](https://mlsanity.com/paper/2501.02600/) (2025)
- [BlendServe: Optimizing Offline Inference for Auto-regressive Large Models with Resource-aware Batching](https://mlsanity.com/paper/2411.16102/) (2024)
- [METIS: Fast Quality-Aware RAG Systems with Configuration Adaptation](https://mlsanity.com/paper/2412.10543/) (2024)
- [Interactive Speculative Planning: Enhance Agent Efficiency through Co-design of System and User Interface](https://mlsanity.com/paper/2410.00079/) (2024)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [TokenCake: A KV-Cache-centric Serving Framework for LLM-based Multi-Agent Applications](https://mlsanity.com/paper/2510.18586/) (2025)
- [TraceLab: Characterizing Coding Agent Workloads for LLM Serving](https://mlsanity.com/paper/2606.30560/) (2026)
- [CONCUR: High-Throughput Agentic Batch Inference of LLM via Congestion-Based Concurrency Control](https://mlsanity.com/paper/2601.22705/) (2026)
- [Nexus:Proactive Intra-GPU Disaggregation of Prefill and Decode in LLM Serving](https://mlsanity.com/paper/2507.06608/) (2025)
- [TraCT: Disaggregated LLM Serving with CXL Shared Memory KV Cache at Rack-Scale](https://mlsanity.com/paper/2512.18194/) (2025)
- [AdaSkip: Adaptive Sublayer Skipping for Accelerating Long-Context LLM Inference](https://mlsanity.com/paper/2501.02336/) (2025)
- [Agent.xpu: Efficient Scheduling of Agentic LLM Workloads on Heterogeneous SoC](https://mlsanity.com/paper/2506.24045/) (2025)
- [HyGen: Efficient LLM Serving via Elastic Online-Offline Request Co-location](https://mlsanity.com/paper/2501.14808/) (2025)
- [DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving](https://mlsanity.com/paper/2602.06502/) (2026)
- [SPAD: Specialized Prefill and Decode Hardware for Disaggregated LLM Inference](https://mlsanity.com/paper/2510.08544/) (2025)
- [Arrow: Adaptive Scheduling Mechanisms for Disaggregated LLM Inference Architecture](https://mlsanity.com/paper/2505.11916/) (2025)
- [TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving](https://mlsanity.com/paper/2508.17219/) (2025)
- [CoDec: Prefix-Shared Decoding Kernel for LLMs](https://mlsanity.com/paper/2505.17694/) (2025)
- [Sparse Prefix Caching for Hybrid and Recurrent LLM Serving](https://mlsanity.com/paper/2605.05219/) (2026)
- [Towards Efficient Large Language Model Serving: A Survey on System-Aware KV Cache Optimization](https://mlsanity.com/paper/2607.08057/) (2026)
- [ShadowServe: Interference-Free KV Cache Fetching for Distributed Prefix Caching](https://mlsanity.com/paper/2509.16857/) (2025)
- [Diffusion Templates: A Unified Plugin Framework for Controllable Diffusion](https://mlsanity.com/paper/2604.24351/) (2026)
- [Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches](https://mlsanity.com/paper/2605.18825/) (2026)
- [ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving](https://mlsanity.com/paper/2607.00466/) (2026)
- [Staggered Batch Scheduling: Co-optimizing Time-to-First-Token and Throughput for High-Efficiency LLM Inference](https://mlsanity.com/paper/2512.16134/) (2025)
- [Simple is Better: Multiplication May Be All You Need for LLM Request Scheduling](https://mlsanity.com/paper/2603.15202/) (2026)
- [A Policy-Driven Runtime Layer for Agentic LLM Serving](https://mlsanity.com/paper/2605.27744/) (2026)

## Abstract (arXiv)

Prompts to large language models (LLMs) have evolved beyond simple user questions. For LLMs to solve complex problems, today's practices are to include domain-specific instructions, illustration of tool usages, and/or long context such as textbook chapters in prompts. As such, many parts of prompts are repetitive across requests. Recent works propose to cache and reuse KV state of prompts. However, they are all confined to a single-GPU optimization, while production LLM serving systems are distributed by nature. This paper proposes Preble, the first distributed LLM serving platform that targets and optimizes for prompt sharing. We designed a distributed scheduling system that co-optimizes KV state reuse and computation load-balancing with a new scheduling algorithm and a hierarchical scheduling mechanism. Our evaluation of Preble with real workloads and request arrival patterns on two open-source LLMs shows that Preble outperforms the SOTA serving systems by 1.5X to 14.5X on average latency and 2X to 10X on p99 latency.