PaperlayerView exact revision on arXiv

Source-linked AI summary

Preble: Efficient Distributed Prompt Scheduling for LLM Serving

Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, Yiying Zhang

arXiv:2407.00023v2cs.DCcs.LG

TL;DR

Long, partially shared prompts are common in LLM workloads, motivating distributed serving that can reuse prompt state. Preble combines distributed scheduling with KV reuse and load balancing, and outperforms existing serving systems on latency across the evaluated workloads.

  • Problem

    Long prompts and shared context are common in LLM workloads, motivating distributed serving that can exploit prompt sharing.

    Source: §1 · pp. 1, 3

  • Method

    Preble uses E2 to schedule requests with prompt-aware GPU load estimates, alongside hierarchical per-GPU scheduling, rebalancing, and fairness quotas.

    Source: §1 · pp. 2–3

  • Results

    1.5×–14.5× on average and 2×–10× on p99 average request latency versus SGLang, with similar results versus vLLM.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Preble improves LLM serving performance while ensuring request fairness and controlling tail latency.

    Source: §6 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

Long prompts with short generations make prefill performance central, while repeated prompt prefixes offer opportunities for KV reuse. Preble combines distributed prefix-aware scheduling with load balancing to address the tension between reuse and GPU utilization.

1 Introduction

  • Distributed serving can separate requests with shared prefixes across GPUs, while sending them all to one GPU can create load imbalance and low cluster utilization.Existing prefix-cache approaches focus on a single GPU, whereas production serving typically uses distributed GPUs.Source: §1 · pp. 1–2
  • Across five workloads, prompts are 37× to 2494× longer than generated sequences, and 85% to 97% of prompt tokens are shared with other prompts.Requests can share multiple prefixes at different lengths, and Azure request arrival speeds vary over time and across usages.Source: §1 · p. 2
  • E2 exploits cached prefixes when saved recomputation exceeds new computation; otherwise, it explores other GPUs using a prompt-aware load estimate.That estimate accounts for recent computation, KV eviction, and the cost of running the new request, treating reusable computation as zero cost.Source: §1 · p. 2
  • Preble combines E2 with request redirection and prefix replication when load changes make a cached prefix too popular for one GPU.It also prioritizes waiting requests by prefix-cache hit ratio while giving each priority group a quota to support fairness.Source: §1 · pp. 2–3
  • 1.5× to 14.5× lower average latency and 2× to 10× lower p99 latency than SGLang; Preble shows similar improvements over vLLM.The evaluation covers five workloads, Azure request arrivals, two open-source LLMs, and two GPU environments.Source: §1 · p. 3

2 Real-World Long and Shared Prompts

The study examines five LLM workloads and an Azure usage trace to characterize prompt length, sharing, and request arrivals. It finds long prompts and substantial sharing, alongside variable arrival patterns that complicate distributed scheduling.

2 Real-World Long and Shared Prompts

  • Across five workloads and the Azure trace, prompt lengths range from 4× output length for Azure chat to 2494× for video QA.Source: §2 · p. 3
  • Prompt sharing ranges from 85% to 97% across the five workloads, and a common sequence is shared by an average of 8.6 to 126 requests.Embodied agents and program generation have the highest sharing amount.Source: §2 · pp. 3–4
  • Azure request inter-arrival times range from 2 microseconds to 217 seconds, reflecting substantial variation in total request load.Source: §2 · p. 4
  • The study concludes that these workloads call for prefill optimization, with prefix caching and sharing as a viable approach, but workload and arrival variation complicate distributed serving.Source: §2 · p. 4

3 Preble Design

Preble combines a global request-level scheduler with per-GPU iteration-level scheduling. Its E2 algorithm balances prefix reuse against GPU load, while additional global and local mechanisms respond to changing load and resource constraints.

3.1 Overall System Architecture

  • Preble supports data and model parallelism, using a global request-level scheduler and per-GPU iteration-level schedulers to manage distributed serving.The global scheduler maintains cluster-wide load and cache information, while local schedulers adapt to GPU resources and request availability.Source: §3.1 · p. 4, Figure 2 · p. 4

3.2 E2 Global Scheduler

  • E2 exploits a cached prefix when its matched tokens outnumber the remaining prompt tokens; otherwise, it explores GPUs using the lowest prompt-aware load cost.The load cost combines recent computation, KV eviction cost, and the new request’s prefill cost; reusable computation is treated as zero cost.Source: §3.2 · pp. 5–6
  • The recent GPU computation load estimates prefill from uncached prompt tokens and decoding from the average output length observed during a default three-minute history window.The estimates use regression functions profiled offline for each GPU type.Source: §3.2 · p. 5
  • When post-assignment load becomes uneven, Preble redirects future requests from a heavily loaded GPU; if rebalancing is insufficient, it replicates the prefix and splits its subtree by load.The replication trigger is average queueing time doubling over the history window.Source: §3.2 · p. 6
  • For exploration, E2 can direct a request to a GPU heavily loaded with decoding, treating the new uncached request as prefill work; local chunked prefill is also used.This policy is prioritized when decoding-prefill loads are imbalanced.Source: §3.2 · p. 6

3.3 Local Scheduler

  • The local scheduler forms batches from a priority-based waiting queue that accounts for cached-token percentage and proportionally selects requests across priority groups.It can chunk long non-shared prompts and evict least-recently-used prefix-tree nodes when GPU memory is insufficient.Source: §3.3 · p. 7

4 Implementation and Evaluation Results

Preble is evaluated across five LLM workloads, two model and GPU environments, and distributed SGLang and vLLM baselines. It improves latency across the tested workloads, while ablations and scheduler measurements examine feature contributions and scalability.

4.1 Implementation

  • Preble is a standalone distributed-serving layer supporting vLLM and SGLang backends, with asynchronous global scheduling and background rebalancing and eviction bookkeeping.The global radix tree is lock-free for read-mostly request handling, with atomic updates for assignments and request counts.Source: §4.1 · p. 7

4.2 Workloads and Environments

  • The evaluation uses five LLM workloads, Poisson arrivals except for Azure-trace experiments, two open-source models, and round-robin distributed SGLang and vLLM baselines.Metrics include serving capacity, average end-to-end request latency, and p99 latency.Source: §4.2 · pp. 7–8

4.3 End-to-End Workload Performance

  • For programming workloads, Preble improves average latency by 1.56× to 1.8× and p99 latency by 3× to 4× over SGLang, less than on four other workloads.The paper attributes the smaller headroom to longer decoding, which dominates latency and is not improved by Preble.Source: §4.3 · p. 8
  • Preble’s relative improvement stays similar from two to four A6000 GPUs, while latency remains similar as request rate doubles; relative improvement increases on eight H100 GPUs with Llama-3 70B.The Figure 3 configurations distinguish the A6000/Mistral runs from the H100/Llama-3 run.Source: §4.3 · pp. 8–9, Figure 3 · p. 9
  • Preble improves average latency by 1.5× to 14.5× and p99 latency by 2× to 10× over SGLang across the tested settings.Figure 3 covers Mistral 7B on two and four A6000 GPUs and Llama-3 70B on eight H100 GPUs.Source: §4.3 · p. 8, Figure 3 · p. 9
  • With Azure-trace arrivals and mixed tool-use and video-QA workloads, Preble improves average and p99 latency, as well as average TTFT and TPOT.Figure 4 evaluates the mixed workloads on four A6000 GPUs.Source: §4.3 · p. 9, Figure 4 · p. 10

4.4 Deep Dive

  • In the ToolBench Zipf-1.1 ablation, E2 improves average and p99 latency, while rebalancing, autoscaling, and prefill/decode-aware handling add further gains; priority-based wait-queue scheduling improves p99 but not average latency.The tested sequence starts from round-robin SGLang and adds features incrementally; Figure 5 depicts the ablation setup.Source: §4.4 · p. 10, Figure 5 · p. 10
  • The global scheduler processes 245 ToolBench and 2931 VideoQA requests per second, with one scheduler estimated to sustain at least 70 to 391 concurrent A100 GPUs.The estimate uses Mistral 7B decoding rates and workload output lengths; network processing was not the bottleneck.Source: §4.4 · p. 10

5 Related Works

Prior long-prompt approaches address prefill/decode imbalance, while existing prefix-sharing systems are single-GPU solutions. Preble targets distributed prompt sharing and fairness, complementing some techniques and differing from lossy non-prefix sharing.

5 Related Works

  • Chunked prefill and separating prefill from decoding target long-prompt imbalance, but do not consider prompt sharing; Preble adds a sharing-based approach on top of chunked prefill.The cited approaches include Agrawal et al. (2023; 2024), Zhong et al. (2024), and Patel et al. (2024).Source: §5 · pp. 10–11
  • SGLang and vLLM support prefix sharing but are single-GPU solutions; distributing them with standard parallelism misses cluster-level prompt-sharing opportunities, which Preble targets.Preble also improves prefix-caching fairness through a different waiting-request ordering policy.Source: §5 · p. 11
  • Prompt Cache shares arbitrary user-defined subsequences through mismatched positional encodings and incomplete attention, a lossy process that can lower generation quality; Hydragen’s attention-kernel optimization is orthogonal to Preble.Prompt Cache Gim et al. (2024); Hydragen Juravsky et al. (2024).Source: §5 · p. 11

6 Conclusion

The paper addresses distributed serving for long, shared prompts with E2 scheduling and Preble’s hierarchical architecture. It reports improved serving performance over state-of-the-art systems while ensuring request fairness and controlling tail latency.

6 Conclusion

  • Preble significantly improves LLM serving performance over state-of-the-art serving systems while ensuring request fairness and controlling tail latency.The system combines the E2 scheduling algorithm with a hierarchical scheduling architecture.Source: §6 · p. 11
  • E2 is a distributed request scheduling algorithm targeting LLM use with long and shared prompts.Source: §6 · p. 11
  • The paper identifies distributed serving for long and shared prompts as the problem it addresses.Source: §6 · p. 11

A Study on LLM Prompts

The study examines five LLM workloads and a public cloud inference trace to characterize prompt length, sharing, and request patterns. Across these use cases, prompts can be much longer than outputs, and shared context arises across requests and within multi-step tasks.

A Study on LLM Prompts

  • The study covers five popular use cases with real public datasets and summarizes prompt length, decoding length, sharing, key-portion size, and the number of requests sharing a key portion.A key portion is the deepest node in a request’s prefix-tree path whose token count exceeds the sum of its predecessors.Source: A Study on LLM Prompts · p. 15, Table 1 · p. 15

A.1 Tool Use

  • Toolbench requests share system prompts and tool-specific instructions; shared instructions can be 43x longer than output length.The dataset contains more than 210k queries calling over 16k unique tools.Source: §A.1 · p. 15

A.2 Embodied Agents

  • In the ALFWorld embodied-agent workload, each loop step becomes a request that reuses prior context, while LLM-generated step counts make sharing patterns unpredictable.Prompts are 157x longer than output tokens.Source: §A.2 · p. 16

A.3 Program Generation

  • In APPS program generation, prompts share code demonstrations and problem descriptions, while parallel candidate generation also shares each problem across requests.The prompt-to-output ratio is 20x, and key-portion properties vary with problem complexity.Source: §A.3 · p. 16

A.4 Video Question and Answer

  • NExT-QA video prompts combine tokenized video with a multiple-choice question, producing nearly 2500× more prompt tokens than decoding tokens.The dataset has 8.5K questions covering 1000 video segments, with six-token outputs.Source: §A.4 · pp. 16–17

A.5 Long Document Question and Answer

  • LooGLE prompts pair long documents with questions, so repeated questions about the same document yield high prompt-to-decode and sharing ratios.The dataset contains 776 documents and over 6.4k questions.Source: §A.5 · p. 17

A.6 LLM Usages in the Wild

  • In the Azure trace, mean prompt-to-decode ratios are 4 for chat and 92 for programming; the longest 20% of chat prompts average 175.Chat and programming requests arrive at approximately 5 and 7 requests per second, respectively.Source: §A.6 · p. 17

A.7 Summary Insights

  • The study summarizes four findings: prompts are long, sharing is common, key portions capture much of prompt sharing, and workloads differ in load and prompt-to-decode ratios.The authors infer that serving should account for prefill, sharing, key-portion placement, and mixed-usage variation.Source: §A.7 · pp. 17–18

B Prefill/Decoding Times

The section profiles prefill and decoding time to estimate computation costs, then presents E2’s global and local scheduling procedures and GPU load-cost calculation.

B Prefill/Decoding Times

  • Prefill and decoding time increase linearly with prompt and context length, respectively, supporting time estimation from token length and profile regression.Prefill is computation-bound and decoding is memory-bandwidth-bound; the authors attribute prefill’s overall linearity to the linear layer dominating model forwarding.Source: B Prefill/Decoding Times · p. 18, Figure 9 · p. 19, Figure 10 · p. 19
  • E2 compares cached and uncached prompt lengths: it exploits a matching GPU when cached length exceeds missed length, and otherwise explores GPUs using decoder ratios and load costs.The algorithm returns the lowest-cost GPU among the eligible choices.Source: B Prefill/Decoding Times · p. 20
  • GPU load cost combines recent prefill and decode computation, estimated KV-eviction cost, and the new request’s prefill cost.Eviction cost weights evicted prefix-node prefill time by the fraction of recent requests sharing each node.Source: B Prefill/Decoding Times · p. 21
  • The local scheduler groups waiting requests by prefix-hit ratio and processes groups round-robin with limits.Source: B Prefill/Decoding Times · p. 21

C Comparison with vLLM and Other SGLang Versions

The evaluation tests Preble with vLLM and newer SGLang components. Preble’s improvements over SGLang persist across SGLang versions, while the vLLM backend yields less relative improvement than the SGLang backend.

C Comparison with vLLM and Other SGLang Versions

Related papers

Loading 2407.00023v2…