Research map / Large language models / Reasoning and chain of thought
Preble: Efficient Distributed Prompt Scheduling for LLM Serving
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.
Preble is a distributed LLM serving platform that schedules requests with prefix-cache awareness, using a two-level (global request-level, local iteration-level) design and the E2 exploitation/exploration algorithm to balance KV-cache reuse against load.
Problem
Single-GPU prefix KV caching systems (SGLang, vLLM) do not account for prompt sharing in distributed serving; round-robin or load-only distribution splits shared prefixes across GPUs, wasting prefill computation, while naively pinning shared prefixes to one GPU causes load imbalance.
Approach
E2 scheduling chooses between exploiting the GPU with the longest cached prefix and exploring the GPU with the lowest prompt-aware load cost (windowed compute load + eviction cost + new-request prefill cost), combined with post-assignment rebalancing, prefix autoscaling, prefill-decode mixing by cache hit ratio, and a priority-based waiting queue for fairness.
Key results
- Preble improves average latency over SGLang by 1.5x to 14.5x and p99 latency by 2x to 10x across five workloads, two LLMs, and two GPU clusters.
- Preble's global scheduler sustains a processing rate of 245 requests/s (ToolBench) and 2931 requests/s (VideoQA), supporting at least 70 to 391 A100 GPUs by its estimate.
- On the programming workload Preble still achieves 1.56x to 1.8x average latency improvement and 3x to 4x p99 improvement over SGLang.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Preble's distributed prompt-aware scheduling instead of round-robin SGLang | SGLang serving across GPUs · Five real-world workloads | average request latency: 1.5× to 14.5× | Helped |
| Use Preble's distributed prompt-aware scheduling instead of round-robin SGLang | SGLang serving across GPUs · Five real-world workloads | p99 request latency: 2× to 10× | Helped |
| Add per-request E2 scheduling (ablation) | SGLang round-robin baseline · Tool use workload with Zipf-1.1 prompt popularity | average request latency | Helped |
| Add per-request E2 scheduling (ablation) | SGLang round-robin baseline · Tool use workload with Zipf-1.1 prompt popularity | p99 request latency | Helped |
| Add post-assignment global rebalancing and prefix autoscaling (ablation) | E2 scheduling · Tool use workload with Zipf-1.1 prompt popularity | p99 request latency | Helped |
| Add post-assignment global rebalancing and prefix autoscaling (ablation) | E2 scheduling · Tool use workload with Zipf-1.1 prompt popularity | average request latency | Helped |
| Add prefill/decode-aware request handling (ablation) | E2 with post-assignment rebalancing and autoscaling · Tool use workload with Zipf-1.1 prompt popularity | average request latency | Helped |
| Add prefill/decode-aware request handling (ablation) | E2 with post-assignment rebalancing and autoscaling · Tool use workload with Zipf-1.1 prompt popularity | p99 request latency | Helped |
| Add priority-based local wait-queue scheduling (ablation) | Preble with prefill/decode-aware handling · Tool use workload with Zipf-1.1 prompt popularity | p99 request latency | Helped |
| Add priority-based local wait-queue scheduling (ablation) | Preble with prefill/decode-aware handling · Tool use workload with Zipf-1.1 prompt popularity | average request latency | No clear effect |
Surprising findings
- Prompts are 4x to 2494x longer than outputs, so optimizing prefill rather than decoding matters most for these workloads.
- Priority-based waiting-queue ordering improves p99 latency but not average latency, since its goal is fairness.
Limitations
- Decoding performance is not improved, so gains shrink for long-decoding workloads such as programming.
- Evaluation uses only two open-weight LLMs and five workloads; vLLM results use an older prefix caching beta.
- Load estimates rely on offline profiling and regression functions per GPU type.
Experimental setup
Datasets: ToolBench ALFWorld APPS NExT-QA LooGLE Azure LLM Inference Trace
Benchmarks: ToolBench ALFWorld APPS NExT-QA LooGLE Azure LLM Inference Trace
Metrics: requests per second average end-to-end latency p99 latency TTFT TPOT
Baselines: SGLang vLLM
Builds on: SGLang vLLM Sarathi chunked prefill
Closest papers by meaning
- DON’T STOP ME NOW: EMBEDDING BASED SCHEDULING FOR LLMS (ICLR 2025 · similarity 0.89)
- Efficient LLM Scheduling by Learning to Rank (NeurIPS 2024 · similarity 0.88)
- PARALLELPROMPT: Extracting Parallelism from Large Language Model Queries (NeurIPS 2025 · similarity 0.87)
- HeraSys: Collaborative Serving of Multiple LLM Workflows via Fine-Grained End-to-End Optimization (ICML 2026 · similarity 0.86)
- OServe: Accelerating LLM Serving via Spatial-Temporal Workload Orchestration (ICML 2026 · similarity 0.86)
- DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving (ICLR 2026 · similarity 0.86)
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.