Preble: Efficient Distributed Prompt Scheduling for LLM Serving
Authors: Vikranth Srivatsa
Zijian He
Reyna Abhyankar
Dongming Li
Yiying Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: LLM prefix caching
LLM serving
Distributed systems for ML
Primary area: infrastructure, software libraries, hardware, systems, etc.
TL;DR: This paper proposes Preble, the first distributed LLM serving platform that targets prompt sharing and improves SOTA serving systems by up to 14.5× on average latency.

Abstract: 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 op-
timizes 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 re-
quest arrival patterns on two open-source LLMs shows that Preble outperforms the SOTA
serving systems by 1.5× to 14.5× on average latency and 2× to 10× on p99 latency.

Published as a conference paper ICLR 2025
PREBLE: EFFICIENT DISTRIBUTED PROMPT SCHEDULING FOR LLM SERVING
Vikranth Srivatsa" Zijian He Reyna Abhyankar', Dongming Li', Yiying Zhang University of California, San Diego, "GenseeAl Inc.
ABSTRACT
Prompts to large language models (LLMs) have evolved beyond simple user questions. For LLMs to solve complex problems, today's '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 op- timizes 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 hierarchical scheduling mechanism. Our evaluation of Preble with real workloads and re- quest 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
Recently, new capabilities and use cases of LLMS have created two common features not seen in traditional LLM usages. First, prompts to LLMs are significantly longer than generated sequences. For example, questions about a long document (Li et al., 2023a) or a video clip Xiao et al. (2021) are answered by LLMs with short answers. As another example, detailed instructions and illustrations for LLMs are vital in accomplishing complex tasks like solving advanced math problems Yao et al. (2023b). The latest LLMs like OpenAl ol have built-in reasoning capabilities; even though the end users' prompts do not need to be long, these models internally add more context like chain-of-thouge prompting Wei et al. (2024), lengthening the total context length OpenAl (2024a). As demonstrated by ol and other model usage, oftentimes, the longer a prompt is, the better quality the model prefill phase significantly outweighs the decoding phase. Thus, improving the prefill phase performance crucial to the overall performance of LLM serving systems.
generate. Long prompts with short generations imply that the
Second, prompts are partially shared across requests. For example, a long document or video is often queried many times with different questions Li et al. (2023a); different requests using the same tools share tool instructions in tool-augmetted LLMs Hao et al. (2023); chain- or tree-structured prompting calls an LLM in steps, with each subsequent step reusing context from previous steps Yao al. (2023b); Zhang et al. (2023); Yao et al. (2023a). Real-world production systems like Anthropic have also reported the wide existence of long and shared prompts Anthropic (2024).
Recent works Zheng et al. (2023b); Gim et al. (2024) propose to cache computed key-value (KV) state in GPU memory and reuse the cached KV when new request sharing a prompt prefix arrives. These works aim to improve the serving performance of LLMs with long and shared prompts in a single model replica.
"Equal contribution

---

Published as a conference paper at ICLR 2025
However, in-production LLM serving systems typically utilize a distributed set of GPUs to serve user re- quests. Current distributed LLM serving systems are not prompt-cache-aware they attempt to distribute LLM computation load equally across GPUs to achieve high cluster-level GPU utilization. Yet, this distri- bution could result in requests with shared prefixes being sent to different GPUs, causing KV computation at all these GPUs that could otherwise be avoided if prefixes are cached and reused on the same GPU. On the other hand, naive solution that always sends requests with shared prefixes to the same GPU would result in imbalanced loads and low overall GPU utilization because the GPU that initially serves a request with a popular prefix will accumulate a huge load of new requests all trying to reuse the calculated prefix K.V.
To properly design a distributed LLM serving system for long and shared prompts, we first perform a com- prehensive study of five typical LLM workloads: LLM with tool calling Guo et al. (2024), LLM as embodied agents in virtual environments Huang et al. (2022), LLM for code generation Nijkamp et al. (2023), embed- ded video QA Xiao al. (2021), and long document QA Li et al. (2023a). We find their prompts to be x to 2494x longer than generated sequences, and 85% to 97% tokens in a prompt are shared with other prompts. Additionally, a request often shares prompts with multiple other requests at different amounts (e.g. one prefix sharing being the initial system prompt, one sharing being the system prompt plus tool A's demon- stration, and one being the system prompt plus tool A and tool B's demonstrations), We also analyze the Azure LLM request trace Patel et al. (2024) and found these end-user traces to have large prompt-toouuppe ratios as well. Additionally, this trace shows that requests arrive at varying speeds over time and across LLM usages, making designing a distributed LLM serving system challenging.
Based on our findings, we propose a distributed LLM request scheduling algorithm called E2 (standing for Exploitation + Exploration) that co-designs model computation load-balancing and prefix-cache sharing. E2 allows requests to exploit (i.e., reuse) computed prompt prefixes on the same GPU but also gives chances for requests with shared prefixes to explore other GPUs. E2 chooses exploitation when the amount of recomputation saved is larger than that of new computation, which happens when the number of shared prefix tokens is larger than the remaining non-shared tokens. Otherwise, E2 chooses exploration. For exploitation, we send the request to the GPU that caches the longest-matched prefix.
When E2 decides to explore GPUs, it chooses the GPU with the lightest "load", using prompt- load definition we propose. This prompt-aware load includes three parts all calculated as GPU computation time. The first part is GPU's computation load in a recent time window H, which is measured by the total prefill time and decode time incurred by all the requests in H. The second part is the cost of evicting existing KVs on the GPU to make memory space run the new request. The third part the cost of running the new request on the GPU. When calculating these three parts, we account for prompt sharing that have or would occur on the GPU by treating the reusable computation as zero cost. E2 picks the GPU with the lowest sum of the three parts to explore, which balances loads while accounting for cached prompt behavior.
Centered around the E2 scheduling algorithm, we build Preble, a distributed LLM serving system that aims to provide high serving throughput and low request average and tail latency for long and shared prompts. Preble consists of global, request-level scheduler and a per-GPU, iteration-level scheduler. Apart from E2, Preble incorporates several novel designs to tackle practical LLM challenges. First, with the basic E2 algorithm, a prefix is cached at a GPU after its initial assignment until its eviction. However, the amount of requests sharing it change over time, which can cause load imbalance. To mitigate this issue, Preble detects load changes and redirects requests from a heavily loaded GPU to a light GPU. If the load hitting a popular prefix increases beyond what a single GPU can handle, Preble automatically scales (autoscales) the prefix by replicating it on multiple GPUs
Second, prefill and decoding phases have different computation needs, as discovered and tackled by set of recent works Zhong et al. (2024); Patel et al. (2024); Agrawal et al. (2024). We propose a new way to solve this problem based on our insight that a prompt hitting a cached prefix can be treated as decoding- phase computation, while a missed prompt can be treated as prefill-phase computation because of the high
2

---

Published as a conference paper ICLR 2025
tool Use
(8R5AZ 8596;
program generation
1871:180 97%;
1IM
User
LLM
parallll code genaention
System:
progaane eecmmpa:
Pangrammin
You hane access the tollnning scole:
[purametura: (hppll lolject
Tool parameters
dala..?
Use....
prockem, drput-y dulpu cnampte cods Horn aoother ecamppe
User Protle
Problom
coda generation
and paralla
ppammatennt
video QA
9865-4 88%
LLM
arowen
virtual environment
97%;
Vhai happened buty.... away,
"ou
kischen Your task to Hom are ham accrmples.
call LLT
numbor
RC1 by
of Alppp deppende on LLM geowwiisr
col
Triestored Video
Long Socumen
"Wy de the woman bard down.. pamp.. RacandRn
Ga LUM
answer escerchia
200 pan
document QA
23474-18 C 91% 18
Figure 1: Prompt Sharing Features of Five Workloads. Green boxes represent shared prefixes. Grey boxes are non-shared prompts. White boxes are output generation. Red boxes contain statistics in average values: "prompt- length:ouiput-lere lenghh;; shared token percenlage; number of requests sharing sequence".
prompt-to-decoding token length ratio. Thus, our global scheduler tries to mix the two types of requests on a GPU to balance prefill and decoding computation needs.
Finally, unlike existing works that either honor request faimess or maximize prefix matching, Preble aims to achieve high prefix reusing while ensuring fairness, which important in multi-tenance environments. We achieve this by assigning priorities to waiting requests based on their prefix cache hit ratio and giving each priority their respective quota of requests to serve.
We implement Preble a standalone layer on top of slightly modified vLLM Kwon et al. (2023) and SGLang Zheng et al. (2023b), two popular open-source LLM serving systems both supporting single-GPU prefix caching. We evaluate Preble using our studied five workloads and the Azure request arrival pat- tern with the Mistral 7B model Jiang et al. (2023) and the Llama-3 70B model Meta (2024) on a four- Iwidia-A6000 GPU cluster and Light-viidi-HHO0 GPU server. Our results show that Preble outper- forms SGLang by 11.55 x and 2x-10x on average and p99 average request latency and similarly when compared to v..LM.
Overall, this paper makes the following key contributions: (1) The first study of LLM workloads with long and shared prompts, resulting in four key insights. (2) E2, new LLM request scheduling algorithm with the idea of exploitation and exploration integration. (3) Preble, the first distributed LLM serving system that targets long and shared prompts. (4) A comprehensive evaluation of Preble and SOTA LLM serving systems on two popular open-source LLMs, five real workloads, and two GPU clusters. Preble is publicly available https://github.co htt.gghhhh......w.ee WukLab/prebbe.
2 Real-World Long and Shared Prompts
This section briefly presents our study results of five LLM use cases and an end-user LLM use trace: tool use Schick et al. (2023), embodied agent in a virtual environment Hao et al. (2023), software program gen- eration Nijkamp et al. (2023), video QA Xiao et al. (2021), long document QA Li et (2023a), and the Azure LLM usage trace Patel et al. (2024) (which contains chat and five workloads to study and evaluate, as they resemble long-and-shared- ppreeppppppptt use cases reported in pro- duction Anthropic (2024). Figure 8 demonstrates the prompt usages and overall features of these workloads. Appendix A presents our full study methodology and results.
usages). We pick the
Overall, our study shows that prompts are significantly longer than output lengths in the five workloads and the Azure trace, ranging from 4x (Azure chat) to 2494x (video QA). Morcover, prompt sharing ranges from 85% (ie., 85% prefix tokens in prompt are shared with least one more request) to 97% across the five workloads, with embodied agents and program generation having the highest sharing amount. Additionally, common sequence in workload is shared by 8.6 to 126 requests on average, with different deviations
3

---

Published as a conference paper ICLR 2025
across workloads. Finally, the Azure trace indicates high variations in total request loads manifested as different end-user request anrivalrrival times that range from 2 microseconds to 217 seconds.
Our study results indicate that LLM serving systems for such workloads should focus on optimizing prefill computation, and viable way is to cache and share prefixes. However, the variations in prompt-sharing features and request arrival patterns make challenging to build an efficient distributed serving system.
3 Preble Design
We now present the E2 algorithm and the design of Preble, beginning with the overall system architecture of Preble, followed by its global scheduler and local scheduler designs. Preble significantly improves serving speed and reduces request latency for workloads with long and shared prompts. For workloads without any shared prompts, its behavior and performance are the same as SOTA LLM serving systems like vLLM.
3.1 Overall System Architecture
Preble is distributed GPU-based LLM serving system supporting both data parallelism and model parallelism. While its model parallelism support standard (e.g., tensor parallelism), Preble's scheduling of requests on data-parallel GPUs is designed specifically for long and shared prompts.
incoming request
We propose two-level scheduling system where global scheduler performs request-level scheduling decisions and orchestrates the overall load balanc- ing across GPUs, while a per-modellinstance local scheduler performs iteration-level scheduling for requests assigned to the GPU, as shown in Figure 2. Depending on the GPU cluster topology, the global scheduler may be deployed on separate server for multi-server GPU cluster or on the same server as mnggleseeverrmulti-Gre
Tokenizer
global radix free
[OPUt 7rec Gre, (Pt-tt/ieee]
[GPUUT Awey
CPLP Sreal)
Scheduler:
E2 Scheduling
[CPPLI:
scheduled
[CPLE
reqq jeete
node evict
tree
[Trec]
Local: Priority
Local
[trea]
Local
Scheduler
Scheduler
[4roc]
cluster. The local sched- uler manages one model instance (multiple GPUs when using model parallelism, single GPU when not) and runs on the CPU of the same server as the GPUs. Our current implementation of Preble scales to at least 70 to 391 GPUs. To offer larger, data-center-level scales, one can deploy several Preble clusters, each having one global scheduler.
[Treq]
Scheduling
[2rac]
(model
GPU4
GPU
GPU
[rea]]
malt rog
GPU1
[Broa]
priciiyy
Imodel copy
imoce paralibiis
model copy 3)
Broq]
Figure 2: Preble Architecture.
This design offers several benefits: 1) by having all requests in a cluster go through the global scheduler, we have centralized place maintain global view of cluster load and caching information, both being essential for E2; 2) by performing coarse-grained, request-level scheduling, a single global scheduler can scale to hundreds of GPUs, avoiding the complexity of maintaining multiple distributed global schedulers for cluster; and 3) by performing fine-grained, iteration-level scheduling at each GPU, the local scheduler can quickly adapt to GPU resource and request availability changes and make precise decisions.
3.2 E2 Global Scheduler
We now present our global scheduler design, which centers around the E2 distributed scheduling algorithm.
Global scheduler data structures. The global scheduler maintains several data structures assist its prompt-aware request scheduling. The primary data structure is global prefix trees, implemented as radix trees Wikipedia (2024). Each tree has distinct root storing the shared prefix of all prompts under the tree.
4

---

Published as a conference paper at ICLR 2025
When inserting new request to the tree, we match its tokens from the beginning (i.e., prefix matching) until no mathh exists, and we insert the remaining tokens as new leaf node. If no match exists at all, we create a new tree with this request's 's prompt as the root node. If an existing tree node only matches partially to the new request (i.e., the prefix of a node matches sub-sequence of the new request), we split the node into the matched part and the remaining part. For each tree node, we record three pieces of information: the number of tokens in the tree node, the set of GPUs caching the tree node KVs, and the per-GPU number of requests sharing the tree node in a history window H. When a tree node has no caching GPU and there is no request within the window H in the whole system sharing it, we remove it from the tree.
Per-request scheduling policy. To schedule a request, the global scheduler uses our proposed E2 scheduling algorithm, illustrated in Algorithm 1. It first matches the request's 's prompt in the global prefix trees. When the amount of recomputation saved (number of tokens in the matched prefix) is larger than the amount of new computation (number of tokens in the remaining prompt), we favor exploitation over exploration because the gain of saved GPU resources (computation for matched tokens) is higher than the load (computation for unique tokens) that can potentially be balanced in the GPU cluster. For such requests, E2 exploits existing cache by assigning the request to the GPU that caches the tree node with the longest tokens in the matched prefix. If multiple such GPUs exist, E2 chooses the GPU with the lightest request load using the load calculation to be introduced next.
If the matched prefix shorter than the remaining tokens, E2 explores the best GPU to run the request based on our proposed new prompt-aware "load cost" definition. Exploration gives E2 a chance to distribute load to different GPUs, which is the key to striking long-term cluster execution efficiency. E2 unifies three types of costs when calculating the per-GPU load: the computation cost aggregated across all requests within a time window, the recomputation cost needed for evicting memory to run the new request, and the computation cost of the new request. E2 calculates all three costs GPÜ computation time and finds the GPU with the lowest sum. Instead of profiling the actual computation time, we only maintain token counts at the global scheduler, which largely reduces the system overhead. We leverage cansformer-based LLMs' properties that the computation amount of prefill and decoding are proportional to the number of prompt tokens and generated tokens (Figures 9 and 10). Below and in Algorithm we detail the three calculations for scheduling a new request Rs.
The first cost is the overall GPU computation load L, for GPU, We capture a recent load history on GPU; with time window H with a default value of 3 minutes (we test different H lengths and find the results insensitive to it). We do not use GPU,'s 's load the exact request scheduling time for two reasons: 1) a GPU's load can change between the time of scheduling R3 to the time of running it, and 2) the placement of a prefix has a longer-term effect than a single load in time because of other requests' future exploitation of it. For each request R, in the history, we estimate its prefill time PT, with regression function using the number of tokens in R, that do not match any prefixes on GPU;; we estimate its decoding time DT, with another regression function using the average request output length observed on GPU, in window H. We have the first category of load, L, = Erew (PT, + DT+,, where W is the set of requests in the window H. The regression functions used in this calculation Note that even though the number of output tokens is not known a priori, our workload study (Appendix A) shows that it is small and similar across type of workload. Thus, we use the average output length in H as the estimated decoding length for DT,-
captured from offline profiling for cach GPU type.
The second cost is the potential cost free GPU memory so that the new request, Rg, can run. Given that GPUs run at full capacity with our and existing serving policies Agrawal et al. (2023), we expect this cost always occur. Intuitively, the more tokens in a sequence that are shared and by more requests, the more costly it is to evict the sequence. Thus, to calculate the eviction cost, M,. the global scheduler first uses the eviction algorithm to be discussed in Section 3.3 to find the tree nodes on GPU, that would be evicted to run Rg. For each such tree node j. its eviction cost is the recomputation time of the evicted tokens multiplied by the hit rate of the node, Ny. Thus, we have Mi- Σjer. PT, x N₂ where the eviction node set, PT,
5

---

Published as a conference paper at ICLR 2025
is the prefill time for the length of tree node j. and N, is the the number of requests sharing tree node j in history H over the total number of requests on GPU, in H. Note that we do not include the decoding time, as a request's 's decoding time unaffected by prefix cache eviction, and decoding costs have already been counted in L,
The third cost is the actual cost, P.. to run the new request R₂ on GPUs, which simply the prefill time of the missed tokens in request Rg- We do not count its decoding time, as it is the same across GPUs, and our goal is to compare the per-GPU load across GPUs.
The total cost of assigning the current request to GPU, is L, + M, + P. and we choose the GPU with the lowest total cost to assign the request to.
Post-assignment load adjustment. With the above algorithm, after the global scheduler assigns request a GPU, its prefix lives there until its eviction. This greedy approach works well cases where the load prefix is relatively stable but not otherwise. We propose two ways of managing post-assignment load changes. The first way shifts load between GPUs and is applicable when the load surge can be handled by a single GPU in the cluster. The global scheduler maintains per-GPU load discussed above. If the most heavily loaded GPU's load is more than Thear times higher than the lightest GPU, it shifts load from the former to the latter until their difference is below Theal- Thaal configurable and can be deducted from profiling GPU and LLM types. To perform this load rebalancing, we direct future requests that are supposed exploit the heavy GPU to the light GPU.
The second way is to auto-scale a prefix by replicating it and splitting its subtree by load when we detect that a certain prefix's 's request load is still too high (average queueing time doubles over H) even after the above load rebalancing. We calculate the subtrec's 's load using Algorithm 2.
Prefill-deoddng balancing, From our study results in Appendix A and reported by others, LLM prefill has a larger compute-to -ommory ratio than decoding, causing inefficient GPU resource utilization and perfor- mance degradation. While various recent works tackle the prefill-dcoodin prefills Agrawal et al. (2023) and prefill-deoddig disaggregation Zhong et al. (2024); Patel et al. (2024); Strati et al. (2024); Hu et al. (2024); Qin et al. (2024a), we propose a new way of solving the problem lever- aging prompt sharing features at cluster level. Our insight is that a request with its entire prompt shared and cached would only perform the decoding phase. Thus, can be treated as a decoding- phase comput- ing unit. Meanwhile, request with long prompt not cached and short output length can be treated as a prefill-phase computing unit. A partially cached prompt can be treated as being between the prefill- and decoding- -hasse units. Thus, prompt sharing instead of or in addition to existing balancing techniques.
imbalance problem by chunking
balance -ecodind by combining requests with more less
Specifically, when request is about to be explored, the global scheduler first considers the prefill and de- coding balancing for each GPU. If GPU is heavily loaded with decoding- paaldinng-hheeeeeee computing units, the global scheduler directs the current request it, as a request to be explored will incur recomputation for prompt and is considered a prefill-phase unit. We prioritize this policy over the load-cost comparison (Algorithm 2) because a GPU with heavy decoding has unused computation capacity that we can almost freely use. The global scheduler performs the load-cost comparison if all GPUs have relatively balanced decoding prefill loads. Apart from this prefill-decodig balancing performed at the global scheduler, our local scheduler also performs traditional chunked prefill for each GPU (Section 3.3).
3.3
Local Scheduler
Local scheduler mechanism. The local scheduler schedules the requests that the global scheduler assigns to its managed GPU(s). Similar to existing LLM serving systems Yu et al. (2022); Kwon et al. (2023); Zheng al. (2023b); Aminabadi et al. (2022), we run local scheduler per GPU and schedule requests the iteration level. Each local scheduler maintains a request wait queue, a prefix (radix) tree, and the number of active requests sharing each prefix tree node.
6

---

Published as a conference paper ICLR 2025
When a new request arrives, the local scheduler matches to the local prefix tree and updates the tree accordingly. It also inserts the request into the waiting queue. After each model iteration, the local scheduler forms the next batch by selecting waiting requests using priority- based algorithm to be discussed next. If a selected request has long and non-shared prompt, we chunk the prompt similar to Sarathi Agrawal et al. (2023). If the GPU memory is not enough to run the batch, the local scheduler selects a tree node(s) or part of tree node (if a part is enough) to evict based on the request accessing time (LRU) of tree nodes. The local scheduler then asynchronously informs the global scheduler about the eviction, and the latter processes it in the background.
Waiting queue request ordering, Today's LLM serving systems schedule requests in the waiting queue according to FCFS Kwon al. (2023) prefix sharing Zheng et al. (2023b) (serve the request with the highest sharing amount the first). The former ignores prompt sharing and results in more recomputation; the latter ignores fairness and could result in starvation Wu et al. (2023). We propose priority-based wait queue scheduling policy that considers both prefix sharing and fairness. Specifically, we create P (a configurable parameter) priority groups and assign a request the priority group according to its cached token percentage. For example, if 63 out of 100 tokens in request's prompt are cached on the GPU and P is 10, it will be assigned priority six. When selecting requests to form the next batch, the scheduler proportionally selects requests from each priority group, with the higher priority group getting more requests selected than lower priority ones. For example, if 55 requests are to be selected to form a batch, the scheduler picks ten from priority group 10, nine from priority 9, etc.
4
Implementation and Evaluation Results
4.1 Implementation
We implemented Preble standalone layer to perform distributed LLM serving, As such, Preble can be added to any existing serving systems with no or minimal changes we currently support vLLM Kwon al. (2023) and SGLang Zheng et al. (2023b) as two backends.
Global scheduler scalability. In implementing the global scheduler, we use a few techniques to improve its scalability. Incoming requests are first tokenized by parallel tokenization layer. Afterward, the global scheduler spawns asynchronous request handlers to schedule requests. Access to the global radix tree during request handling is lock-free, as most operations are read-only. The only exceptions to be assigned to a tree node and the increment of request count hitting the tree node, both of which can be expressed as atomic instructions. Additionally, the global scheduler maintains current load count for each GPU by updating it every time new request is assigned to it or when it evicts tree node. Thus, our realization of the E2 algorithm is cetttormmanne-fffffiieeeee Finally, to ensure foreground request performance, the global scheduler runs non-request- scheduultss tasks such as rebalancing and eviction bookkeeping in the background with separate threads.
updating GPU
4.2 Workloads and Environments
Workloads, We evaluate our results on five LLM use cases: LLM generation with tool demonstration and calling Schick et al. (2023), LLM interacting with virtual environments as an embodied agent Hao et al. (2023), LLM for program generation Nijkamp et al. (2023), answering questions about videos Xiao et al. (2021), and answer questions about long documents Li et al. (2023a). Their properties are in Appendix A.
For each workload, we sample enough requests to fulfill the request-per-secome (RPS) needs and GPU setup (e.g., larger GPU or more GPUs can handle more). For experiments other than the ones using the Azure Inference Trace, we set the inter-arrival time using a Poisson distribution with a mean that around the RPS (X-axis in most figures). We then the experiments until stable state is reached and for significant length.
7

---

Published as a conference paper ICLR 2025
LLMs and environments. We test Preble and baselines using two popular open-source LLMs, the Mistral 7B model Jiang et al. (2023) and the Llama-3 70B model Meta (2024). We run our experiments in one of the two environments: two-server cluster with two NVidia A600 GPUs and one eight Niidia-
Baseline, Our baselines are serving systems that support single-GPU prefix sharing, including SGLang Zheng et al. (2023b) and vLLMM (which recently added a beta feature for prefix sharing Moore & Li (2024)). To run SGl.ang and vL..M in a distributed fashion, we set up a load balancer that sends requests in round-robin fashion individual LGL.an/vLLLMM instances (i.e., con-prompt-awars data paral- lelism). As round- robin distributes requests evenly, these baselines capture a distributed serving system that balances request loads and then performs prefix sharing within each parallel instance.
Metries. We use three key metrics: request per second, which measures serving capacity; average end-to- end request latency (including scheduling time, queueing time, prefill, and decoding time); and p99 request latency. Note that our metrics differ slightly from some existing LLM serving works Kwon et al. (2023); Yu et al. (2022), as we do not use TPOT (time per output token) or TTFT (time to first token) as key metrics. This is because our target L.L use has short output lengths, rendering TPOT not meaningful and TTFT close to the request latency. We consider p99 latency since it is important to control the tail latency in LLM serving as with all other user-facing services DeCandia et al. (2007); Ongaro et al. (2011).
4.3 End-to-End Workload Performance
We first present the overall performance of Preble and the baselines. Below, we focus on the comparison with SOTA SGLang it is specifically designed for (single-GPU) prefix sharing. We provide Preble's comparison to vLLM and to different SGLang versions in the Appendix D.
Single workload results. We now present the average and p99 latency against increasing requests arriving per second (RPS) of Preble and SGLang on the five workloads, two LLMs, and two GPU environments, shown in Figure 3. Overall, Preble significantly outperforms the data mata-parallel SGLang baseline for all settings, as can be seen from Preble's lower average and p99 latency, especially under higher RPS (or the other way around, for the same latency target, Preble serve higher RPS). Our improvements over SGLang range from 1.5x to 14.5x in terms of average latency and 2 to 10x in p99 latency.
Comparing across workloads, we see bigger improvements Preble over SGLang on the Toolbench, em- bodied agent, video QA, and LooGLE workloads than the programming workloads. The programming workload has the longest decoding length among all the workloads. As decoding time starts dominate total request latency, and we do not improve decoding performance, the room for improvement for Preble is smaller. Nonetheless, Preble still achieves 1.56x 1.8x improvement in average latency and 3x to 4x in p99 latency over SGLang in the programming workload.
Comparing across the number of GPUs, Preble's relative improvement over the baselines stays similar when going from 2 to 4 A6000 GPUs. Considering absolute values, we see Preble successfully maintain similar latency even as RPS doubles, showing its strong scalability. When changing from A6000 to 8 H100 and switching the Mistral 7B to Llama-3 70B, we find relative improvements of Preble to increase.
Azure trace and mixed workloads. Our experiments above use a Poisson request arrival distribution (which is the same most existing LLM works' experimental methodology Kwon al. (2023); Li et al. (2023b)). To understand Preble's s performance under real-world request load, we run the tool use and video QA workloads using Azure's LLM request arrival pattern (Appendix A.6) instead of Poisson distributions. Here, we mix the two workloads to mimic Azure's mixed chat and code traces. As shown in Figure 4, Preble has significant improvements in average and p99 latencies and on average TTFT and TPOT.
8

---

Published as conference paper ICLR 2025
Piebl
S0tang
Tool Use
Embodied Agent
Programming
Video
LooGLE
200
400
130
2U50000
10
5-
102
22
40
03-
890
60-
102
336200
200-
40-
400
100
209
50-
0.50
40N020 leg
15-
130
02-
75
10+
100
50
30
20-
25-
10
7.5
18.0
1.0
440020 p9a 30
600
150
3000
42-
600
200-
608
70-
20
7.2
10.2
0.5
1.0
15
10.0
15-
10+
20-
2.5-
20
0.4
0.0
0.8
30
30-
300
30-
200
20
100
100
10
15
1.0
0.4
0.5
0.9
(mog]t
Rate [meg]]
Rate (mrgge)
Figure 3: End-to-end Workload Performance The top and middle
2-4 A6000s with Mistral 7B.
The bottom two rows run on 8 H100s set as 4-GPU tensor parallelism plus data parallelism with Llama-3 70B.
4.4 Deep Dive
We now provide detailed analysis of Preble, including an ablation study and global scheduler scalability test. Because H100 GPUs' high cost and low availability, we run all experiments in below with A6000s.
Ablation study. To understand where the benefits of Preble come from, we evaluate Preble by incrementally adding features presented in Section 3. We chose the tool workload with Zipf-1.1 popularity distri- bution among the prompts in the dataset to represent real-life skewed tool popularity. Other workloads and of techniques. We start with using the SGLang round-robin base- distributions benefit from a different line. We first add the per-request E2 policy (Section 3.2), which results in improvement on both average and p99 request latency because of E2's dynamic load partitioning. rebalancing and autoscaling, which successfully balances out load more, resulting in further improve- ment, especially with p99. Further adding the prefilldecode-awwe both average and p99, since it considers the current batch composition and is able to better utilize the GPU resources. Finally, we add the local-scheduler priority-bare based wait-queue scheduling ($3.3), which, as expected, improves p99 but average latency, as its goal is fairness.
then add the post-assignment global
handling results in more improvement
9

---

Published as conference paper ICLR 2025
p29 avg
330
0.30
320-
0.45
08-
230
Litencyts
0.20
200-
TFPT
0.6
0.15
2,42
0.10
6.02x
10
0.05
no to adeatheed
Solang Pieble
kng
Frefie
5G ang
Pieble
knlang Poble
Figure 4: Mixed Workload With Azure Trace mix of Tool and Video workloads with Azure arrival trace on A6000s.
Figure 5: Ablation Results Running ToolBench with 7ipf-1. I.J running on 4 A6000s
Global scheduler performance and scalability. We measure Preble's 's global scheduler max throughput by sending large (c.g.. 50,000) requests at once, climinating arrival pattern effects and ensuring saturation. Since the global prefix tree search is the most time-consuming task at the global scheduler, we test the Toolbench and VideoQA workloads, which have the most complex and simplest prefix tree structures in five workloads. Preble's ' global scheduler achieves a processing rate of 245 and 2931 requests per second for Toolbench and VideoQA. We also measure the network processing speed and find it not to be the bottleneck. With the peak GPU processing rate (30-150 tokens per second decoding speed with Mistral 7B on A A100) and workloads' output length (Table 1), Preble global scheduler can sustain least 70 391 concurrent A100s. If accounting for prefill time or bigger models, our scheduler would sustain even more GPUs.
5 Related Works
LLMs' usages shifting to be more prompt-heavy. As result, the problem of prefill and decoding having different compute-to compute-to-memrry
memory ratios is exacerbated. Several recent works have targeted LLM usages with long prompts and proposed solutions to solve the imbalance problem. The first approach, called chunked prefill, chunks prompt and runs each chunk with other decoding requests a batch single iteration reduce waiting Agrawal et al. (2023; 2024). The second approach is separate prefill and decoding to different GPUs to avoid prefill-decodin target long prompts but ignore prompt sharing. Preble consider prompt length and sharing, and we use novel sharing- -haseng-based approach on top of chunked prefill to solve the
interference Patel et al. (2024); Zhong et al. (2024). These solutions
imbalance problem.
Many state-of-art LLM inference systems Zheng et al. (2023b); Moore & Li (2024) enable prefix sharing improve KV cache reuse. However, these systems limit the sharing at the scale of individual model instance, overlooking the cluster-level prefix- sharing opportunities and challenges. More recent works Hu et al. (2024); Qin et al. (2025) corroborate our insight in adding prompt-sharing awareness to the cluster-leve scheduler. Unlike Preble, MemServe et al. (2024) prioritizes cache reuse regardless current loads and thus could result in imbalanced and inefficient GPU usage. Mooncake Qin et al. (2025) is concurrent work of Preble and similarly balances cache exploitation and load distribution. Differently, Preble factors the potential KV eviction in the load estimation. which can be more accurate. Moreover, Preble also improves fairness in prefix-caching with better waiting request ordering.
6 Conclusion
This paper identified the problem of distributed serving for long and sharing prompts. To solve this problem, performed study on five LLM workloads and one real LLM trace. We presented E2, distributed LLM request scheduling algorithm targeting LLM usages with long and shared prompts. We built Preble, a distributed LLM serving system top of the E2 algorithm and a hierarchical scheduling architecture. Our results show that Preble significantly improves LLM serving performance over SOTA serving systems while ensuring request fairness and controlling the tail latency.
10

---

Published as a conference paper ICLR 2025
Acknowledgment
We would like to thank the anonymous reviewers for their tremendous feedback and comments, which have substantially improved the content and presentation of this paper. We are also thankful to Yufei Ding and Geoff Voelker for their support and feedback of this work. This material is based upon work supported by gifts from AWS, Google, and Meta. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of these institutions.
References
Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, and Ramachandran Ramjec. Sarathi: Efficient Ilm inference by piggybacking decodes with chunked prefills. arXiv preprint arXiv:2308. 16369, August 2023.
Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming prroughput-latenne tradeoff in Ilm inference with sarathi-serve, Proceedings of 18th USENIX Symposium Operating Systems Design and Implementation, 2024, Santa Clara, 2024.
Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, et al. Deepspeed-inference: enabling efficient inference of transformer models unprecedented scale. In SC22: International Conference for High Performance Computing, Networking, Storage and Analysis, Dallas, Texas, November 2022. IEEE
Anthropic. Prompt caching with elaude.
caching, 2024.
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon's 's highly available key-value store. ACM SIGOPS operating systems review, 2056-220-- oct 2007.
Patrick Esser, Robin Rombach, and Björn Ommer. Taming transformers for high-resolution image synthesis. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Los Alamitos, CA, June 2020.
In Gim, Guojun Chen, Seung scob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. In Proceedings of the 7th MLSys Conference, Santa Clara, CA, May 2024.
Zhicheng Guo, Sijie Cheng, Hao Wang, Shihao Liang. Yujia Qin, Peng Li, Zhiyuan Liu, Maosong Sun, and Yang Liu. Stabletoolbench: Towards stable large-scale benchmarking on tool learning of large language models. arXiv preprint arXiv:2403.0777: 077444 Mar 2024.
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings. In Advances in Neural Information Processing Systems 36, New Orleans, Louisiana, De- cember 2023. URL http://poccediiigg.nui...p.p Coppe-Conference,rr pdf.
flles/puper/202///////f6l. http:///w......aaaa.occccccc.... 185222244446666055552333333a
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Pu- ranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with apps. Pro- ceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, December 2021.
Cunchen Hu, Heyang Huang, Junhao Hu, Jiang Xu, Xusheng Chen, Tao Xie, Chenxi Wang, Wang, Yungang Bao, Ninghui Sun, and Yizhou Shan. MemServe: Context Caching for Disaggregated LLM Serving with Elastic Memory Pool, arXiv preprint arXiv:2406.1 7565,, June 2024. URL https://arxiv.wrr/ab//4466.. 11144066..766 17565.
Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodicd agents. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (cds.), Proceedings of the 39th International Conference on Machine Learning, Hon- olulu, volume 162 of Proceedings of Machine Learning Research, pp. 9118 1949177. PMLR, 17-23 Jul 2022. URL https//proccediing... mlr, press/y 62/huang 22a.aang2aahhmn html.
11

---

Published as a conference paper at ICLR 2025
Sam Ade Jacobs, Masahiro Tanaka, Chengming Zhang, Minjia Zhang. Shuaiwen Leon Song, Samyam Rajihandari. and Yuxiong He. Deepspeed ulysses: System optimizations for enabling training of extreme long sequence transformer models. arXiv preprint arXiv:2309. 14509, October 2023.
Albert Q. Jiang, Alexandre Sablayrolles. Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b. arXiv preprint 136.0025,, October 2023.
Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y. Fu, Christopher Ré, and Azalia Mirhoseini. Hydragen: High- throughput IIm inference with shared prefixes. arXiv preprint (.xXxx:2422.000900 May 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, Koblenz, Germany, October 2023.
Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. Loogle: Can long-context language models understand long contexts? arXiv preprint 1xXX::3311.04993 Novemher 2023a.
Junkai Li, Siyu Wang, Meng Zhang, Weitao Li, Yunghwei Lai, Xinhui Kang, Weizhi Ma, and Yang Liu. Agent hospital: A simulacrum of hospital with evolvable medical agents. arXiv preprint arXiv:240..02957, May 2024a.
Junyou Li. Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. More agents is all you need. arXiv preprint 2xXv:2402.055200 February 2024b.
Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. AlpaServe: Statistical multiplexing with model parallelism for deep learning serving. In 17th USENIX Symposiun on Operating Systems Design and Implementation (OSDI 23), Boston, MA, July 2023b.
Hao Liu, Matei Zaharia, and Pieter Abbeel. Ringattention with blockwise transformers for near-infinite context. In Proceedings of the 12th International Conference on Learning Representations, Vienna, 2024. URL. htips: V/apenrevieennetffommmkddb wiioooummmmdddsWRPPhaae
Meta. Meta Ilama 3. https://llama. www.mmeeee.mmmmaammmmmmmm com/llama3// 2024.
Sage Moore and Zhouhan Li. Automatic prefix caching. https://gtthu..com/// wtwpr//ooooooooooooo///liiiiiiie 1 March 2024.
Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal. Leave no context behind: Efficient infinite context transformers with infini-attention. arXiv preprint arXiv:2404.07144 April 2024.
Erik Nijkamp, Hiroaki Hayashi, Caiming Xiong, Silvio Savarese, and Yingho Zhou Codegen2: Lessons for training Ilms on programming and natural languages. arXiv preprint arXiv:2305. 02009, July 2023.
Diego Ongaro, Stephen M. Rumble, Ryan Stutsman, John Ousterhout, and Mendel Rosenblum. Fast Crash Recovery RAMCloud. Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP '17), Cascais, Portugal, October 2011.
OpenAI. Learning to reason with 1lms.
weastoooorrr--eeeee with Iims/, September 2024a.
OpenAI. Video generation models as world simulators. http:///ww....oooee///////////ne wewpoo---eeeerattooooeeeeeeeeeee world- simulators, 2024b.
Pratyush Patel, Esha Choukse, Chaojic Zhang, Aashaka Shah, fñigo Goiri, Saced Maleki, and Ricardo Bianchini. Split- wise: Efficient generative IIm inference using phase splitting In 2024 ACM/IEEE 51 Annual International Sympo- sium on Computer Architecture (ISCA), pp. 118-132. IEEE, 2024.
Ruoyu Qin, Zheming Li, Weiran He, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: A kveache-centric disaggregated architecture for Ilm serving, arXiv preprint arXiv:2407.000 200.00099 Jul 2024a. URL htapss//arxiv.rrgaas///000/
12

---

Published as a conference paper ICLR 2025
Ruoyu Qin, Zheming Li, Weiran He, Jialei Cui, Feng Ren, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: Trading more storage for less computation - a KVCache-centrie architecture for serving LLM chatbot. In 23rd USENIX Conference on File and Storage Technologies (FAST 25), pp. 155-170, Santa Clara, CA. February 2025. USENIX Association. ISBN 378-1-939133-45-4 URL. https://www.sseiiit. www.emiii..oroomeeeeccc///issia presentation/gin.
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan. Yaxi Lu, Yankai Lin, Xin Cong. Xiangru Tang, Bill Qian, Sihan Zhao, Lauren Hong, Runchu Tian, Ruobing Xie, Jic Zhou, Mark Gerstein, dahai li, Zhiyuan Liu, and Maosong Sun. TooILLM: Facilitating large language models to master 16000+ real-world APIs. In The Twelfth International Conference on Learning Representations, Vienna, 2024b. URL https://openreview nwt/forum hiwfrrommmmddddn200iiii
Timo Schick, Jane Dwivedi-YY Yu, Roberto Dessi, Roberta Railcanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves use tools. Thirty- seventh Conference on Neural Information Processing Systems, New Orleans, 2023. URL https://openreview.nrr net/ forum?id= Yacmpp884TT......
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Cote, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. HALFWWorld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations, Virtual, 2021. URL. https://openrewieww https://opemeeeee...e////mmmmmme
Foteini Strati, Sara Mcallister, Amar Phanishayee, Jakub Tarnawski, and Ana Klimovic. Déjävu: KV-cache streaming for fast, fault-tolerant generative LLM serving. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver. Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 46745-46771, Vancouver, Canada, 21-27 Jul 2024. PMLR. URL https:/pproccedings.. mlr pressii355/sttrti22aaa. pesa
FlashInfer Team. Flashiafer, October 2024a. URL https://githubb.co htwp://......tssssiaeaaaalaaaaaa
SGLang Team. SGLang, October 2024b. URL
htgp://boooooggg-oppcsslglggggg project/sglang.
Xingyao Wang, Zihan Wang, Jiateng Liu, Yangyi Chen, Lifan Yuan, Hao Peng, and Heng Ji. Mint: multi-turn interaction with tools and language foodback. The Twelfth International Conference on Learning Representations, Vienna, Austria, May 2024.
Evaluating ilms
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi. Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consisteney improves chain of thought reasoning language models. The Eleventh International Conference on Learning Representations, 2023. URL https:/openreviiew wwt.//ert////ee wtt. INL.MM.M.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia. Ed H. Chi, Quee V. Le, and Denny Zhou. of-in-of-thougll prompting elicits reasoning large language models. Proceedings of 36th Interna- tional Conference on Neural Information Processing Systems, New Orleans, LA, November 2024.
Wikipedia. Radix tree. https://en. wikkpeeia.org/wili/Reee. tree, 2024. [Online; accessed 1-October-2024).
Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distrihuted inference serving for large language models. arXiv preprint arXiv:2305.055920 May 2023.
Qingyun Wu, Gagan Bansal, Jicyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W White, Doug Burger, and Chi Wang. Autogen: Enabling next-ger gen LLM applications via multi-agent conversation. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, Vienna, 2024. URL http://ppeeeveeeee.eee//oonnmdmd
Junbin Xiao, Xindi Shang, Angela Yao, and Tat-Seng Chua. Next-qa: Next phase of muestion-answering to explaining temporal actions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9777-9786, June 2021.
13

---

Published as a conference paper ICLR 2025
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), seirth-seventh Conference on Neural Information Processing Systems, volume 36, New Orleans, Louisiana, December 2023a. URI. Pale---aapep--eeeeeeeeee
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference Learning Representations, Kigali, Rwanda, April 2023b. URL https://ppenrevieww wed/forummid-WE.llur
Gycong-In Yu, Joo Scong Joong, Geon-Woo Woo Kim, Soojeong Kim, and Byung-Gov Gon Chun. Orca: A Distributed Serving System for Transformer Based Generative Models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI '2),, Carlsbad, CA, July 2022.
Shoubin Yu, Jaemin Cho, Prateek Yadav, and Mohit Bansal. Self-chained image-language model video localization and question answering. In Thirty-seventh Conference on Neural Information Processing Systems, New Orleans, Louisiana, December 2023.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations, Kigali, Rwanda, May 2023, URL hutp://openreview..o https//appmeeewwww.elelommm/mmi wwt.//nnnmidddNNNTSSSSHHHHH
Lianmin Zheng. Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging LLM-as-a-judge with MT-bench chatbot arena. Thirty-seventh Conference on Neural Information Processing Systems Datasets Benchmarks Track, New Orleans, Louisiana, December 2023a. URL https://openreviiw. nwt/ffrrum Hlaaoo.
Lianmin Zheng, Liangsheng Yin. Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Efficiently programming large language models using sglang. arXiv preprint urXiv:2312.07100 December 2023b.
Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin and Hao Zhang. Distllm: Disaggregating prefill and decoding for goodput-optimizze large language model serving. In Proceedings of the 18th USENIX Symposium Operating Systems Design and Implementation (OSDI '24), Santa Clara, CA. July 2024.
14

---

Published as a conference paper ICLR 2025
7 Appendix
A
Study on LLM Prompts
Today's LLM usage goes beyond simple chatting. As LLM usage becomes more commercialized, LLM prompts become more structured and complex. outshadowing the text an LLM generates. This section presents our study results of five popular new LLM use cases: tool (or API, agent) use Schick et al. (2023), interacting with virtual environments as embodied agent Hao et al. (2023); Huang al. (2022), software program generation Nijkamp et al. (2023), answering questions about videos Xiao et al. (2021), and answer questions about long documents Li et al. (2023a). Figure 8 demonstrates the prompt usages of these work- loads. We study each case with real public datasets and understand their prompt features from a systems perspective. For datasets that do not provide outputs, use Llama-3 7B model as the LLM to generate outputs. For each dataset, we construct a prefix tree for all the requests in the dataset (i.e. assuming an infinite prefix cache).
Table and Figure summarize our study results, including prompt and decoding (output) length, amount of sharing in a prompt, key portion size in prompt, and number of requests sharing a key portion. We define the "key portion" of a request as the deepest node in a path that has more tokens than the sum of its predecessors.
To understand real-world LLM user request features, we study a recently released public cloud LLM trace.
This section ends with our summary insights.
Workload
Prompt Len
Output Len
Shared Prefix
KeyPort. Prompt
Req Share KeyPort.
in Prompt (85%, 13%)
Toolbench
(1835, 742)
(43, 16)
(76%, 16%)
(39, 64)
Embodied Agent
(2285, 471)
(16, 13)
(97%, 14%)
(76%, 12%)
(48, 8)
Programming
(3871, 1656)
(190, 343)
(97%, 7.4%)
(78%, 13%)
(126, 2157)
Video QA
(9865. 5976)
(4, 1.5)
(88%, 32%)
(99%, 0.2%)
(8.6, 2)
LooGLE
(23474, 6105)
(16, 9.9)
(91%, 24%)
(94%, 15%)
(18, 8.6)
Table 1: LLM Prompt Properties Each cell except for number of requests shows (mean, standard deviation). Length represented using number of tokens. "KeyPort." stands for Key Portion.
A.1 Tool Use
Today, LLMs are often augmented by various tools such as calculators and web searches. To equip a model with the ability to invoke a tool, it must be given the correct syntax for querying the tool, along with examples (or "demonstrations") of tool use. We evaluate the Toolbench Guo al. (2024) dataset, which consists of more than 210k queries that call over 16k unique tools. Each query shares the same system prompt followed by tool-specific instructions. The final part of the query is the user's specific question task. These are all concatenated together to form the final prompt. We find that most of the sharing comes from queries that all share the same tool, and these instructions can be 43x longer than the output length. The Toolbench workload is also representative of other tasks that "prep" an LLM in similar fashion. For example, instead of tool-calling, LLMs can have roles layered on top of the system prompt, which is popular in emerging systems that utilize the same LLM with multiple roles to create an ensemble Wu et al. (2024): Li et al. (2024b;a).
A.2 Embodied Agents
LLMs are increasingly found in agents that can interact with environments, such player in role-playing game or controlling a robot. In this scenario, the LLM receives feedback from the environment, forms an action, and then "performs" the action. This is conducted in loop until the model has achieved the goal.
15

---

Published as a conference paper ICLR 2025
Toolbench
Embodied Agent
Programming
Video QA
LonGLE
0.6
0.6
0.4
04-
0.4
02-
0.2
02-
0.-
00
10
1000
10000
0.0
0.0
0.2
2.1
0.8
1.0
0.0
0.2
0.1
0.8
1.0
6.
50
150
150 250 250
Prompt-to Decade Ratio
Shared Prefix in Prompl
Key Portion Prompl
Req Share Key Portion
Figure 6: CDF Plot of Key Metries Showing CDF for all five workloads prompt-to-decode ratio, shared prefix
The workload we utilize is sourced from the ALFWorld Shridhar et al. (2021) dataset and has 7.5k requests. Prompts first describe the environment and the task, followed by a demonstration of steps to solve the task. The model then solves its given task by looping over planning step followed by an action step. After each action, the text-based environment returns an observation that the model incorporates into next planning step. Every new invocation to the LLM in this loop is treated as new request, resulting in each step sharing the context of previous steps. Interestingly, the number steps is determined by LLM generation, creating unpredictable sharing pattern. Because steps chained together, prompts are still 157x longer than output tokens.
The embodied agent workload represent wide variety of other use cases, such chain of thought Yao et al. (2023b); Wei et al. (2024), multi-turn tool usage Wang et al. (2024); Qin et al. (2024b), and chat- bots Zheng et al. (2023a). Any dependency between the model and the outside environment can be consid- ered an agent receiving feedback.
A.3 Program Generation
One of the popular uses of LLMs is to generate software programs Nijkamp et al. (2023). We study the APPS competitive programming dataset Hendrycks et al. (2021), dataset of programming problems. To generate better-quality programs, an approach taken by a recent paper Juravsky et al. (2024) is to add a demonstration of several generic code examples before the the same across all problems and becomes the system prompt. Following the system prompt is the program- ming problem description. Afterward, this approach invokes the LLM several times parallel generate multiple candidate programs, out of which the best is chosen to return to the user. As generated code is relatively long (compared to outputs of other workloads we study), the prompt-to-output ratio (20x) is rel- atively low. Prompt sharing comes from two places: the system prompt of code demonstration is shared across all requests, and the programming problem is shared across all parallel generations. Depending on how complex the problem is, its description could be longer or shorter than the system prompt; prob- lem description can also partially the same as another problem description. Such complexity results in competitive programming having diverse key-portion properties. Such example demonstration and parallel generation technique is common in recent prompt engineering, for example, with ReAct Yao et al. (2023b), Tree-of-Thoughe Yao et al. (2023a), and Self Consistency Wang et al. (2023).
problem to instruct an LLM. This added demonstration is
A.4
Video Question and Answer
The advent of video models like OpenAl Sora OpenAl (2024b) has created explosion of interest in multi- modal models. The use of LLMs, then, goes beyond natural language. A recent usage to answer questions about videos by tokenizing video segment and inputting it to an LLM Yu et al. (2023); Esser et al. (2020).
To study this, we analyze the NExT-QA benchmark Xiao et al. (2021), which consists of 8.5K questions for 1000 video segments. Prompts the LLM consist of tokenized video followed by multiple-choic question. Because of the multiple-choice nature, the outputs this dataset only have six tokens. Long tokens for representing videos plus short outputs result in this dataset having the highest pompt-to-decodiee token
16

---

Published as conference paper ICLR 2025
1.0
1.0
Conversation
0.8
0.8
Programming
0.4
0.4
0.2
0.2
0.0
0.01
100
10000
100
1000
Inter-Arrival Time (ms)
Prompt-to-Decode Ratio
Figure 7: Azure LLM Trace Analysis Results.
ratio of all workloads we explored, with nearly x more prompt tokens. Apart from videos, images and audio can also be tokenized to have LLMs answer questions, and we expect them to have similar properties video QA.
A.5 Long Document Question and Answer
With newer models, the maximum context length has increased substantially Munkhdalai et al. (2024); Liu et al. (2024); Jacobs et al. (2023), with the latest development supporting 1M tokens Munkhdalai et al. (2024). Longer contexts enable new LLM applications such asking questions about a long document even a book. We evaluate this usage with the LooGLE dataset Li et al. (2023a), a collection of 776 long documents and over 6.4k questions. LooGLE has small system prompt of 13 tokens followed by long document and then a question about the document. As a common practice, a user or multiple users often ask multiple questions the same document, resulting in large amounts shared tokens. Meanwhile, the answers are usually short (e.g., a true or false). These features result in high prompt-to-decode ratio and high sharing ratio LooGLE.
A.6 LLM Usages in the Wild
To understand LLM usage in the wild, we analyze the recently released Azure LLM Inference Trace Patel et al. (2024). The trace includes two types LLM usages: program generation and chat conversation. It provides request arrival time, prompt length, and decode length. As it does not provide actual request content, is not feasible for us to evaluate prompt content or sharing. Figure plot our analysis results in CDF. We find that the arrival rate is approximately requests per second for chat conversation and 7 requests per second for programming. On average, chat requests arrive 1 118 ms apart while programming requests arrive 63 apart. The mean prompt-to-decode ratio for chat conversations is 4. Since we have no details about shared context from follow-up conversations, this number is expected to be much lower. For the longest 20% of all chat prompts, the mean prompt-to-decode ratio is 175, which is consistent with our observations on other workloads. For programming, the mean prompt-to-deen -odeede ratio is 92 for all prompts. This falls within the range of all the workloads we evaluated.
A.7 Summary Insights
Our analysis of the five real-world LLM workloads and real user LLM request trace reveals several key findings.
Insight 1: Contrary popular belief. prompts significantly longer than output lengths because LLMs support longer context and new LLM usages keep emerging. We believe this trend will continue as LLMs are augmented with more capabilities. Implication 1: Optimizing prefill computation can largely improve over- all application performance, and imbalanced prefill and decoding computation features should considered in LLM serving.
17

---

Published as a conference paper ICLR 2025
tool use
User. Could provide duily data....
Gall LLM
Syster: You are AutoGPT, you can use manyy toois...
frenccill statement. ('parameters":
WAF
You have access of the following tools:
Tool 2. (paaraeeenn'
Tool (parametensss
User
virtual environment
number of stops dipands on LLM generation
room with kitchen items
feedback
erlv
cal
final action
Your task to:
The
pan from stove
back
program generation
User
ULM
call
1t parallel code generation
"You are a computer science programmer
Programming
Hore an excmmpe::
Problom
parallal code generation
problom, -Ipput- outpuu example code another example:
User Problem
video QA
"What happened the baby...?
call LLM
answer: O. away
awayy.
Tokenized Video
"hhy did the woman bend down.??
call LLM
ansHwer: 1.
jump.,
document
call LLM
QA
Long Dacument
Question: How many people...? 1, soven, 2. sik,
six
Please question the long texts below..
which year did...?
Long
1962
Doc
Figure 8: Workload Demonstration. Green boxes represent shared prefixes. Grey boxes are non-shared prompts. White boxes are output generation. Yellow star represents key portions that always happen fixed parts; pink stars non-fixed paris. Blue clouds reprexent the parts that would be used for distributing prefixes knowwigg the oracle.
Prompt sharing, or reuse, is common, and the sharing amount is high. Sharing can come from different requests needing the same tools or instructions to solve task. It can come from user asking multiple questions about the same document or video. Context sharing can also happen within the same user task that is solved with chain tree of steps. Implication 2: Reuse computation across shared prefixes can largely improve real workloads' performance and should be efficiently supported by distributed LLM serving systems.
Insight 2:
Insight 3: Most requests have a portion of the prompt sequence that gets a different degree of sharing and is longer than its prefix, reflected key portion in prefix trees. Key portions account for the majority of prompts and are shared by significant amount of requests. Implication 3: Identifying the key portion of prompts and optimizing the placement requests according their key portions a viable way of reducing the complexity of scheduling while achieving good performance.
Insight Real-world LLM usages have varying load intensity, and different usages (programming vs. conversation) have different loads. Real-world prompts are also much longer than decoding length, but different usages have different prompt-to-decode ratios. Still, the longest prompts are significantly longer. Implication 4: An efficient LLM serving system should consider complex, mixed-usage scenarios and factor in both load and prompt sharing variations.
18

---

Published as conference paper ICLR 2025
Linear Layers
Self-Attention
Execution time (ms)
Linear Layers
Execution time
1.5
Total
40
Self-Altention
1.0
20
0.0
Prompt Length (x1000 @token)
Context length (x1000 #tokens)
Figure
Prefill Time Decompusition
Figure 10:
Decoding Time
B Prefill/Decoding Times
The prefill and decoding stages exhibit different computation behaviors, with the former being computation- bound and the latter being memory bandwidth bounded. To understand their behaviors and to acquire pre- filldecoding computation time functions to be used by E2, we profile the prefill and decoding stage per- formance with Mistral 7B on the A6000 GPU. Figure 9 plots the prefill time and its breaking downs when prompt length increases. As seen, longer prompts increase prefill time, suggesting that the more savings we can get from prefix sharing, the lower prefill time will be. Moreover, since the linear layer dominates the model forwarding at the prefill stage, the prefill time overall linear the prompt length. Figure 10 shows the performance of single request's decoding performance with varying context lengths (the length of the prompt sequence plus the sequence generated thus far). We observe a similar linear relationship to context token length. Overall, these profiling results suggest that attention computation is regular. Thus, we could use the token length with a profile regression function estimate computation time.
memory-bandwidthh
19

---

Published as conference paper ICLR 2025
C
Algorithms
Below, we provide the global and local scheduling algorthim used by Preble.
Algorithm 1 E2 Global Scheduling Algorithm
function CCHEDULEREQQEES((B),
Match R& global radix tree Jec + sum of matched length messedlen - prompt_en cached_en
missed len < cached len then
Exploit Rg
K < GPUs with longest node in matched path for each GPU i K do
Cost: < LOADCOST(i, R&)
end for
return with lowest Cost; else
b Explore Rg
for each GPU i in all GPUs do
Ratio, <- DECODERATIO()
end for
> IMBALR: cale based on GPU type and LLM if highest Ratiomar IMBALR then
return max end if
for each GPU i all GPUs do Cost, LOADCOST(i, Rx)
end for return with lowest Cost; end end function
20

---

Published as conference paper ICLR 2025
Algorithm 2 GPU Load Cost Calculation
p Load cost calculation for GPU and request Rs function LOADCOST(i, R2) - 0; M - 0: P
& Calculate total load on GPU for each R in history H do missed_len + non-cached prompt length for
L PREFLLLIIEE(mmssedd
decode_len t average request output length in H < DECODEETIMEddecooee.oo
end for
& Calculate eviction cost
+ tree nodes to evict on GPU i to run Rs for each j in E' do
Nj f number of requests sharing j in H number of total requests in
M < M+ PREFILLTIMEE(lenthh of f) N,
end for
b Calculate cost to run R2
missed_len_k non-cached prompt length for Rg
P + (misseed (en.k)
return L + M + P
end function
Algorithm 3 E2 Local Scheduling Algorithm function SCHEDULEREQUESTS
for all requests in waiting queue do
Determine prefix hit ratio
Assign to priority group based on hit ratio
end for
Process groups in round-robin fashion with limits
end function
21

---

Published as conference paper ICLR 2025
Preble
SGLang
200
400
Avg Latency
300
100
200
50
100
0
0
4
4
Rate (req/s)
Rate (req/s)
Figure 11: vLLM Backend Performance Evaluated on the Video QA workload using the Mistral 7B model on GPUs.
Preble
SGLang
LooGLE
2xA6000 Avg (5)
30
Mistral 78
40
20
10
8
10
12
14
0.4
0.6
0.8
80
200
2XA6000 p99 (s)
78
60
150
40
100
10
12
0.4
Rate (req/s)
Rate (reg/s)
SGLang v0.3
Figure 12: Latest SGLang v0.3 and Flashinfer 0.1.6
Comparison with vLLM and Other SGLang Versions
To demonstrate Preble's versatility with multiple LLM backends, evaluate Preble vLLM with the vanilla vLLM as the bascline. vLLM recently added support for prefix caching, which we include in the slightly different version of the Mistral 7B model (v0.2) for this experiment, vLLMM only supports this version. Figure 11 plots the results of running the VideoQA workload on 2 GPUs and the Mistral 7B v0.2 model for both Preble and vLLMM Compared to SGLang backend, vLLM backend
baseline. We
22

---

Published as conference paper ICLR 2025
MemServe
Preble
Tool Use
LooGLE
2xA6000 Avg (5)
100
400
75
Mistral
200
50
25
0
5
10
15
0.3
0.4
0.5
0.6
0.7
300
Mistral 7B
200
1000
4xA6000
500
100
10
20 Rate (req/s)
30
0.6
0.8
1.0
1.2
1.4
Rate (req/s)
Figure 13: Compare with MemServe Evaluated on the Tool Use and Video QA workloads using the Mistral 7B model with TP=1.
gives Preble less relative improvement for several reasons: 1) local-GPU prefix sharing is beta version and not as performant SGLang: 2) vLLM does not the flash-infer kernel which makes prefix sharing more efficient; and 3) vLLM does not support chunked prefill together with prefix caching. 4) vLLM has significant scheduling delay
To demonstrate Preble's versatility across multiple SGL.ang versions, we evaluate the latest SGL.ang version (v0.3) Team (2024b) and the latest FlashInfer kernel (v1.6) Team (2024a) in addition to the v0.1.12 we used in Section 4. SGLang made two major changes between these two versions: 1) the new FlashInfer kernel improved the performance of sharing 32K context length in the same batch, and 2) SGLang reduced its scheduling overhead and applied other engine optimizations. Figure 12 plots the results of running LooGLE and Toolbench with SGLang v0.3 and Preble. Overall, Preble's improvements over SGLang persist across SGLang versions.
Comparison with Memserve
We also provide comparison against MemServe, distributed serving system with prefix awareness, in Figure 13. Preble achieved significantly better average latency in all scenarios. This due the over- exploitation of prompt sharing in MemServe's scheduler policy as they route requests based on the longest- prefix-mated regardless the existing load on that node.
23

---

Published as conference paper ICLR 2025
Preble
LoOGLE sustainable RPS under latency target
LoaGLE
SGLang Proble
150
0665000 A0g
50
RP5
1.5
2.0
30
3.5
TEMGG000 Aug 03
15
25
Figure 14: Mixed Workload With Azure Trace A mix of Tool and Video workloads with Azure arrival frace 4 A6000s.
Figure 15: Ablation
Instances
Running ToolBench
with Zipf-1.1 1.1 running A6000s
Preble
Preble Dynamic
Tool Use
LooGLE
15.
Mistral
10
5-
10
0.2
0.4
0.6
30
Mistral 708
Avg
20-
15
10
100
15
20
0.5
1.0
Figure 16: GPU Utilization Based Dynamic E2 Algorithm
F
Scheduler Scalability
As the number of GPUs and unique prefixes increases, the global prefix tree (and thus the amount of work that the global scheduler needs handle) also grows. To verify Preble's scalability, test the system using an 8-GPU and a 16-GPU cluster with proportionally more unique prefixes from the LooGLE workload. We provide the average latency in Figure 14. We also show the max sustainable RPS with the 20-second latency requirement of Preble and Round Robin baseline in Figure 15. Based on the results, we can see that there's a linear scalability as instances increase.
G Dynamic E2 Scheduling
We also provide experiment with dynamically selecting exploitation exploration based on the total load of the cluster as well as token count in Figure 16. The results between the two approaches are relatively similar. In LooGLE dataset, the default Preble performs (min: -4%, max: 9.2%, avg: 3%) better than the knob based Preble. In the Toolbench dataset, the default Prebleperforms (min: -1.6%, max: 15%, avg: 5.43%) than the dynamic knob based Preble.
24

---

Published as conference paper ICLR 2025
Prabie
Dracke partiton
Sulang
Tool Use
Embodied Agent
Programming
Video
LooGLE
200
100
3-
50-
20
20-
04
100
800
800
100
KIN 78
600-
60-
400
000-
700
50
0--
10
0.2
100
Hatal 25
000-
13-
150
50-
75
10
100
75
30
20
30
10
30
2.5
5.0
7.5
10.0
0.50
0.75
1.00
3.25
400
80
800
1asi TV
000-
40-
600
400
000-
200
50
200
3.0
20
30
10
30
2.5
5.0
7.5
10.0
0.50
0.75
1.00
1.25
15-
5e0300 Avg
10.0
60-
60-
7.5-
10-
6-
2.5-
10
15
10
15
2
0.4
0.6
08
330
Liam 776
300
20-
20-
200
1.00
10-
30
100
Forts Trooist
Rate (neus)
Rate (regs)
Rote Oreaps
Rate (egg)
Figure 17: End-to-end Workload Performance The top and middle two rows run on 2-4 A6000s with Mistral 7B. The bottom two rows run on 8 H100s set up 4-GPU tensor parallelism plus data parallelism with Llama-3 70B.
H Oracle Baseline
We provide an Oracle Partitioning baseline inspired by consistent hashing, Unlike partitioning requests, an- other way of distributing load is partition state (i.e., prefix trees in our case). As prefix trees are dynamic, and perfect partitioning requires solving an NP-hard problem, we use oracle approach to construct this baseline. Specifically, at offline time, we combine all requests in a workload examine the key-portion tree layer, and partition the tree into K (number of data-parallel instances) subtrees by evenly splitting this layer (e.g., with hash values tokens). For certain workloads, no single layer clearly always the key portion; tion. The blue clouds Figure mark the tree node layers that we manually choose as the partitioning layer for this oracle baseline. Note that such oracle information cannot be acquired in real serving system. After a tree has been partitioned, we let the online serving system consistently send requests hitting a partition to the corresponding GPU
single prefix tree, manually
then partition the tree according to the top layer that be key por-
25

---

Published as conference paper ICLR 2025
From the results in 17, we can see that Preble is better or on par with the oracle partition baseline for all setups. This because key portions cannot always be easily identified and partitioned statically and because even when tree can be evenly partitioned by size, requests hitting each partition can be different and can change over time.
Preble has more improvements over the Oracle baseline on the VideoQA and Programming workloads than the other three workloads. The VideoQA workload has more questions for longer videos, causing non-even distribution of request load across videos. Even though the Oracle can evenly split videos, the load is not evenly split. The Programming workload's Oracle split is at the layer of user problem, which is not a good, stable indicator of the key portion the request load. Thus, for these two workloads, Oracle performs much worse than Preble. On the other hand, the embodied agent workload's 's key portion is the initial instruction, and each request has different instruction. Thus, by splitting the initial instruction, Oracle almost perfectly split the load and cache prefixes. The Tool workload has a relatively uniform request distribution across different tool uses, allowing Oracle partition load evenly.
26


Reviews:
[{"review_id": "1P4EZ1H3Rs", "reviewer": "Reviewer_rygC", "summary": "The paper introduces Preble, a distributed LLM serving system specifically designed to handle long-context prompt workloads. The authors propose a tree-based prefix-matching algorithm and an online workload-balancing algorithm that combines exploration and exploitation strategies. Preble demonstrates the ability to reduce P99 latency for the Mistral 7B and LLaMA-3-70B models on video QA workloads, using Azure’s LLM request arrival patterns, compared to SGLang and vLLM.", "questions": "In Section 3.1, it states, “Our current implementation of Preble scales to at least 70 to 391 GPUs.” Based on my understanding, Preble is designed as a single model serving system. Why, then, does it require such a large number of GPUs to serve a single model? I can serve a LLaMA-3-70B model using just four A100 80GB GPUs. \nHow does Preble compare to vLLM?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "The scheduling algorithm seems interesting. The authors introduce a lot of background of LLM in the appendix.", "weaknesses": "I think the major problem is that the authors mix the concept of high-level cluster scheduling with low-level GPU kernel design, which is very confusing. In Section 3.1, the overall design, the term “data parallel” is used inaccurately. Typically, data parallelism refers to the process of dividing data into chunks and distributing these chunks across blocks and threads in low-level kernel design, instead of splitting data to different servers at a high level.\n\nThe statement in the abstract, “production LLM serving systems are distributed by nature,” is misleading. Whether a production LLM requires distributed serving depends on the model size. For instance, in the evaluation section, it’s unclear why the Mistral 7B model is split across multiple servers, as it can easily fit and run inference on a single A100 GPU.\n\nThe authors claim to have implemented their scheduling system on top of vLLM, but there is no explanation of this implementation, nor does vLLM appear in any of the evaluation results. To my knowledge, vLLM supports distributed serving and leverages Ray for efficient workload balancing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8m7ofvbpKG", "reviewer": "Reviewer_ck7x", "summary": "The paper presents Preble which optimize for prompt sharing in distributed LLM serving system. More specifically, the paper proposed some load-balancing mechanism that takes considerations into prompt sharing and fairness for large language model in multi-GPU setting, and designed global and local scheduler for coarse assignment and fine-grained scheduling and eviction policy. Experiments show the performance gain comparing to vLLM and SG-lang based baseline.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper achieved performance improvements comparing to prompt caching mechanisms (vLLM and SG-lang).\n\nThe paper further considered fairness into scheduling process in the optimization in prompt cache.", "weaknesses": "The major concern is that contribution and novelty of this paper is limited. \n\nDistributed prompt sharing optimization across GPUs: Optimize the inference among multiple GPUs (even in cluster level system) is previously studied by various work. As some of the previous work has been cited by the paper, mem-serve[1], inference without interference [2], mooncake[3] are all large scale systems serves beyond a single GPU. Those systems all considered shared prompts, and can be used with long context in production level. In those papers, global scheduling algorithms are already proposed to route the request with minimal re-computation. Yet, the method is only compared with vLLM and SG-Lang. The paper didn’t discuss the difference between those serving system, as well as considering them as baselines to discuss. \n\nThe localized fine-grained local scheduler: The design of the local scheduler is mainly based on Radix-tree scheduling (SG-Lang), considering fairness added on.\n\nThe scenario of the prompt sharing: Previous literature SG-Lang[4], CacheBlend[5] and Prompt Cache[6] have all mentioned the cache reuse opportunity.\n\n[1] MemServe: Context Caching for Disaggregated LLM Serving with Elastic Memory Pool  \n[2] Inference without Interference: Disaggregate LLM Inference for Mixed Downstream Workloads\n[3] Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving  \n[4] SGLang: Efficient Execution of Structured Language Model Programs  \n[5] CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion  \n[6] Prompt Cache: Modular Attention Reuse for Low-Latency Inference", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NEc5TfXXUu", "reviewer": "Reviewer_tC1t", "summary": "The paper presents a distributed serving system designed to handle large language models (LLMs) with long and shared prompts efficiently. Preble aims to improve the reuse of computed key-value (KV) state across multiple GPUs, overcoming the limitations of current systems that primarily focus on single-GPU optimization. The authors introduce a new distributed scheduling algorithm called E2 (Exploitation + Exploration) to balance the reuse of shared prompt prefixes while managing GPU load effectively. Evaluations using real-world workloads demonstrated that Preble outperforms existing state-of-the-art systems by reducing average latency and p99 latency.", "questions": "- What are potential unobserved/unexpected bottlenecks when the systems scales to hundreds or even thousands of machines? Wiil they significantly limit the scalability of the system?\n\n- Given that prompt-sharing can vary beyond exact prefixes, can Preble be extended to support non-prefix caching mechanisms?\n\n- How does Preble’s fairness mechanism prioritize requests if there are multiple users with varying priorities?\n\n- Is there any Trade-off between Cache Utilization and Load-Balancing in E2 Scheduling?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors propsed a first system to address efficient prompt-sharing in distributed LLM environments. \n- The proposed E2 scheduling algorithm seems to effectively balance prefix cache sharing and computation load across GPUs and the authors show significant performance gain compared to SGLang.", "weaknesses": "- Althought the paper claim strong scalability, it is only partially supported by experiments on two four-GPU machines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ac1hoLtItm", "reviewer": "Reviewer_3qUC", "summary": "This paper introduces a distributed LLM inference framework, Preble, which is specifically designed for long and sharing prompts. Before diving into the solution, the paper first characterizes a wide range of LLM applications and production LLM inference traces that motivate the problems. By designing E2, a distributed LLM request scheduling algorithm, the paper aims to improve LLM usage with long and sharing prompts. Extensive experiments are performed against two popular LLM inference systems: SGLang and vLLM. By running real-world applications, workloads, and GPU testbeds, Preble outperforms existing baselines by significantly improving LLM serving performance.", "questions": "Please see questions in weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1 - The paper is well-written and well-organized. I appreciate the intuitive diagrams and figures in the paper.\n\n2 - Motivations and characterizations are clear and inspiring.\n\n3 - The design and analysis are technically clear and sound.\n\n4 - The proposed framework is implemented and evaluated against two popular LLM inference systems, vLLLM and SGLang.\n\n5 - Extensive experiments are conducted, and real-world LLM inference applications are used in the evaluation, which is comprehensive.", "weaknesses": "1 - E2 determines whether it's exploration or exploitation by measuring the computation for matched tokens and computation for unique tokens. This simple design is intuitive enough but remains fixed across different cases. It might be better to make this design dynamic with a knob with load-awareness, where we measure the ratio alpha = (computation for matched tokens / computation for unique tokens) as the knob. For example, if the overall GPU load is quite low (e.g., request rate is low), it would make sense to favor exploitation more by setting this knob alpha lower than 1. This retreats to your fixed design when alpha = 1.\n\n2 - \" E2 calculates all three costs as GPU computation time and finds the GPU with the lowest sum.\" Would it be better if this could be designed as a weighted sum to prevent any dominant components out of the three parts?\n\n3 - The paper mentions that it provides prefill-decoding balancing. How does Preble interact with or integrate with existing continuous batching [1] and chunked prefill [2, 3] techniques?\n\n4 - Minor writing issues: in Appendix C, Figure 11, SGLang should be vLLM in the legends?\n\n[1] Kwon, Woosuk, et al. \"Efficient memory management for large language model serving with pagedattention.\" Proceedings of the 29th Symposium on Operating Systems Principles. 2023.\n\n[2] Zhong, Yinmin, et al. \"{DistServe}: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.\" 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 2024.\n\n[3] Agrawal, Amey, et al. \"Taming {Throughput-Latency} Tradeoff in {LLM} Inference with {Sarathi-Serve}.\" 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ckE5Ksk98Z", "reviewer": "Reviewer_NYyJ", "summary": "In some applications of LLMs, prompts can be much longer than decode length and could be potentially shared across requests. \nHowever, existing works on KV cache sharing only target a single GPU setting, lacking a cache-aware system for distributed LLM serving.\nThis paper proposes Preble, a distributed LLM serving platform that utilizes prompt sharing efficiently. \nThe core of Preble is a two-level scheduler containing a global request scheduler and a local iteration scheduler.\nThe global scheduler schedules requests based on exploitation and exploration, trading off between load balancing and prefix sharing.\nThe local iteration scheduler performs priority-based scheduling to ensure fairness.\nEvaluations show that Preble can improve greatly on average and p99 request latency compared to SOTA systems.", "questions": "Thank you for submitting the work to ICLR 2025! I enjoy reading it. \nI think the problem statement is clear, the design and implementation of the scheduler make sense on a high level, and the evaluation results show clear performance benefits. \nTherefore, I would recommend an accept for this paper. I do have a few questions though and it would be great if the authors could address them.\n\nIn terms of the global scheduler for scheduling requests, I am a bit confused about why Preble chooses to favor exploitation over exploration on the point when the amount of recomputation saved (i.e. number of tokens in the matched prefix) is larger than the amount of new computation (i.e. number of tokens in the remaining prompt). \nAs far as I am concerned, if a request has a partial overlapping prompt with the prefix cache, it seems to always be beneficial to use the prefix.\nThis is because, as pointed out in the paper, the prefill latency grows roughly linearly with the number of tokens, so saving the number of tokens needing to compute could reduce prefill latency.\nIt is true that doing so naively may lead to load imbalance between GPUs, but my feeling is that the load within different GPUs holding the same prefix should play a part in determining whether the scheduler should explore or exploit, instead of merely using the number of tokens as the determining condition.\n\nI am also not sure if the workloads chosen in the paper could fully reflect the real-world distributed LLM serving setting.\nHow would the sharing ratio be on some chat datasets such as ShareGPT or LMSYS?\nIn addition, the current evaluation is done on the five datasets respectively. \nHowever, in a real serving scenario, there may be a set of LLM applications running on top of the same LLM backend at the same time. \nIt may be beneficial to show how Preble performs when requests are drawn from different datasets.\n\nOther questions:\n1. In Sec 3.2, it says \"If an existing tree node only matches partially to the new request, we split the node into the matched part and the remaining part.\" How often does this happen and would this split incur much overhead?\n2. For the case of \"exploitation\", the algorithm first selects GPUs that have the tree node with the longest tokens in the matched prefix, then selects the GPU with the lightest request load among them. Is this always optimal? What about the case that you have a GPU that has the second longest tokens in the matched prefix but an even lighter load?\n3. I find it a bit unintuitive that the value of time window H does not affect the end-to-end results. Have any evaluations been done to evaluate the effect of different time window values?\n4. In Sec 4.4, it says \"Other workloads and distributions benefit from a different set of techniques.\" What do you mean by that?\n5. In Sec 4.4, it says \"One Preble global scheduler can sustain at least 70 to 391 concurrent A100 GPUs\", Could you kindly explain how these numbers are calculated and obtained?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Good observation that the prefix sharing ratio is high among popular LLM applications.\n2. The two-level scheduling algorithms overall make sense.\n3. The evaluation results show solid improvement in request latency compared to SOTA systems.", "weaknesses": "1. Lack of justification for some scheduling decisions made in the paper.\n2. The workload may not reflect the real distributed LLM serving scenario.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)