Symphony: Improving Memory Management for LLM Inference Workloads

A decoder-only transformer serves as the foundational building block of popular LLMs [7]. Each decoder block comprises a self-attention layer and an MLP layer. During next-word prediction, an input token passes through the decoder block. The self-attention layer utilizes the query (Q), key (K), and value (V) vectors associated with the current token, which are computed via linear projections of the input using the block’s query, key, and value weight matrices.

To formally define Multi-Head Attention (MHA), let $H$, $T$, and $d$ be positive integers, where $H$ denotes the number of attention heads, $T$ the sequence length, and $d$ the model dimension. Let $x\in\mathbb{R}^{T\times d}$ represent the input to the MHA layer. For a single attention head $h$, the corresponding key, query, and value vectors are computed as follows:

$$\mathbf{K}^{h}=x\mathbf{W}_{K}^{h},\quad\mathbf{Q}^{h}=x\mathbf{W}_{Q}^{h},\quad\mathbf{V}^{h}=x\mathbf{W}_{V}^{h}.$$

The attention matrix for head $h$ is then calculated as:

$$A_{h}=\sigma(\frac{1}{\sqrt{d}}Q^{h}K{{}^{h}}{{}^{T}})$$

The output of MHA is denoted by:

$$y=A_{0}V_{0}\oplus A_{1}V_{1}\oplus A_{2}V_{2}\oplus\cdot\cdot\cdot\oplus A_{H}V_{H}$$

This output is then passed to a Fully Connected Layer, which processes the result before forwarding it to the next decoder block. Large LLMs typically consist of hundreds of such decoder blocks, enabling their sophisticated capabilities.

For inference, self-attention requires access to the current query vector as well as all keys and values associated with prior tokens. To avoid re-computation, inference-serving systems store these prior tokens in a structure known as the K,V cache [28]. The size of the K,V cache has been rapidly growing due to increases in both model size and supported context length. For instance, the latest LLaMa models now support up to 128K tokens. For a medium-sized model like LLaMa-70B, a full 128K context length results in a maximum K,V cache size of 40 GB.

The prefill phase processes the user prompt and generates the K,V caches associated with it. This phase can efficiently utilize GPU compute resources, as the K,V cache entries for the prompt can be computed in parallel.

The decode phase generates output tokens iteratively. It uses the latest generated token and all prior K,V caches within the model’s context length to perform an auto-regressive decoding step. This process continues iteratively until either an end-of-sequence token is produced or a user-defined limit on the number of tokens is reached.

These two phases have distinct resource requirements: the prefill phase is compute-bound, while the decode phase is memory-bound [2, 18, 38, 1, 14, 36, 24, 37].

Given the unique resource requirements of the prefill and decode phases, several prior works have explored strategies to enhance hardware utilization [52, 37]. Research has also extensively examined scheduling techniques for LLM requests [2, 16, 37, 52]. For instance,  [52, 37] investigated the disaggregation of the prefill and decode phases to optimize hardware usage, while  [2] focused on scheduling prefill and decode requests to minimize end-to-end latency. In addition,  [36] introduced a fairness-oriented scheduler for LLM inference. Similarly, works such as  [14, 38] proposed intelligent mechanisms for batching LLM requests by predicting their compute and memory requirements.

All these works assume that requests are stateless, i.e., each incoming request is treated independently, with no prior associated state. However, in the next section, we demonstrate that this assumption does not hold for the majority of LLM workloads.

To avoid recomputation, some systems [13, 51] retain the previous K,V cache in GPU memory. However, this quickly leads to the exhaustion of the GPU’s high-bandwidth memory (HBM). For example, when serving LLaMa-8b with just 36 requests from the ShareGPT dataset, we observed that the GPU HBM became saturated.

Existing systems like vLLM and Tensor-RT LLM treat each request as a new, independent request, meaning they recompute the K,V cache for prior tokens every time a new request arrives. This results in redundant computation. In Figure 6, we show the number of wasted pre-filled tokens in the ShareGPT dataset. We observe that, as the number of conversation turns exceeds 3, more than 50% of the pre-filled tokens are wasted.

Some recent systems [1, 9] implement mechanisms to swap K,V caches between GPU memory and host memory, migrating them back to the GPU when the next request in the session arrives. In Figure 7, we present the breakdown between Swap and Recompute, for serving 1000 samples from the ShareGPT dataset on an A100 GPU. We observe that using Swap reduces total pre-fill time by a factor of 4.9 and decode time by a factor of 1.68 for LLaMa-7B. The reduction in decode time is due to continuous batching, which accelerates pre-fill and allows a larger number of requests to be processed simultaneously, thereby reducing overall decode time as well.

Swap, however, has two key limitations: (i) Offloading from GPU HBM introduces statefulness into the workload, requiring future requests in the same session to be handled by the same machine. (ii) It only allows offloading to host memory, as transferring the caches to lower-level storage (e.g., disk or remote storage) incurs significant overhead when serving requests. We observe that these limitations are significant. In Figure 1, we show that making machine assignments stateful leads to load imbalances, which negatively affect throughput (Figure 2). To assess the impact of load imbalance, we ran an experiment with 8 A100 GPUs, each serving an instance of LLaMa-3.2 8B with a swapping baseline (InferCept [1]). We ensured that each new request was routed to the same GPU that had previously handled the request in the session. In Figure 8, we observe that the swapping baseline takes 1.7 times longer than the Recompute baseline, despite the reduction in compute. This performance degradation is primarily due to load imbalance, where some GPUs are idle while others are overloaded, resulting in reduced overall throughput.

One way to address this load imbalance is by migrating the K,V caches to balance the load across GPUs. We conducted a similar experiment, as described in the previous paragraph. However, in Figure 8, we observe that migrating the K,V cache further increases the time required to serve requests. The cost of migration is significant, leading to a reduction in throughput as requests must wait for the cache to be migrated.

Additionally, the ability to offload to main memory is limited by the finite amount of available memory. For example, when serving LLaMa-3.1 8B, each token requires approximately 1.1 MB of K,V cache. A system with 256 GB of main memory can support only about 238K tokens. Given that the average session in the ShareGPT dataset is around 2.2K tokens, a single A100 GPU can serve a maximum of 108 concurrent sessions if offloading to host memory. This limitation further restricts the number of users that can be served effectively.

As illustrated in Figure 9, the Symphony scheduler functions as a top-level scheduler and provides two public-facing interfaces: (i) An interface for accepting LLM inference requests, and (ii) An interface for accepting advisory requests.

Upon receiving an advisory request, the Symphony scheduler performs request-level scheduling. Based on the scheduling policy, it augments the advisory request with information about the existing K,V cache location (i.e., the node storing the cache) and forwards it to a Symphony node manager. Additionally, the scheduler updates its internal state to reflect the new K,V cache location. When the actual inference request arrives, the Symphony scheduler routes it to the node identified during the processing of the corresponding advisory request.

In this work, Symphony employs a straightforward load-balancing policy, which distributes requests evenly across nodes. However, as discussed in Section 3.5, Symphony can support a variety of customizable policies tailored to different workloads and system configurations.

The Symphony node manager resides on each node and oversees Symphony ’s hierarchical memory system, which stores K,V caches. It exposes an interface to handle three types of requests: (i) advisory requests forwarded by the Symphony scheduler, (ii) LLM inference requests, and (iii) K,V cache fetch requests from other Symphony node managers.

An advisory request received from the scheduler contains two pieces of information: the session ID of the expected inference request and the current location of the associated K,V cache. Upon receiving an advisory request, the node manager verifies the cache’s location. If the cache resides on a different node, the node manager issues an RPC call to retrieve it. If the cache is locally available, the node manager, subject to memory constraints, moves it to the fastest memory tier possible. We describe how Symphony manages hierarchical memory tiers in nthe ext section.

When an LLM inference request arrives, it is routed to the underlying serving library, such as vLLM or TensorRT-LLM. Section 3.3 discusses how the Symphony node manager interfaces with these schedulers (vLLM and TensorRT-LLM) to efficiently manage GPU high-bandwidth memory (HBM) cooperatively.

When utilizing storage mediums such as host memory or disks, which exhibit significantly higher access latencies, reading and writing K,V caches can introduce substantial overhead. This slow access latency can block inference operations, resulting in performance slowdowns.

Deep neural networks (DNNs) inherently process data layer by layer, requiring access to K,V caches only for the current layer being computed. Leveraging this property, we implement layerwise asynchronous reads and writes, allowing the system to load and store K,V caches in parallel with inference execution.

To support disk writes, we run a background thread that continuously updates the disk with newly generated K,V caches. In Symphony, we always maintain one copy of the K,V cache in the slowest memory hierarchy (disk). This design ensures data persistence, enabling us to perform on-demand evictions from higher memory tiers without risking data loss. For example, if high GPU HBM demand necessitates immediate memory clearance, we can safely purge data from the HBM, knowing that a complete copy of the K,V cache exists on disk.

Serving turn-by-turn workloads presents challenges due to limited information about the order and timing of requests. For instance, in chatbot scenarios, advisory requests indicate, with high probability, that a request associated with a specific session ID is likely to arrive. However, these advisory requests do not provide details about the order of requests or their precise arrival times. In agent workloads, where requests are sent by preceding agents, it is possible to estimate a minimum arrival time. Even so, this limited information complicates decisions about which K,V caches to prioritize, especially under memory constraints.

To illustrate the underlying issue, consider a high-load scenario where an LLM is being served. Suppose an advisory request is received for Session ID-2, prompting the movement of its K,V cache into the GPU HBM. This action fully utilizes the GPU memory. Subsequently, another advisory request arrives for Session ID-3, but the GPU HBM is already full. Without additional information–specifically, whether the inference request for Session ID-2 or Session ID-3 will arrive first–it is unclear which request should take priority.

The prioritization scheme builds on an observation like above - that, like other deep neural networks (DNNs), LLMs perform computations in a layerwise manner. If the K,V cache for the first few layers is available, the model can begin autoregressive decoding immediately while simultaneously prefetching the K,V cache for later layers.

In this scheme, K,V caches are assigned priorities based on their corresponding layers. When inserting K,V caches into the GPU HBM, blocks associated with lower layers are given higher priority, as they are required earlier in the computation. This prioritization ensures that critical portions of the cache are readily available, minimizing delays in inference. In the above example of multiple advisory requests arriving for different sessions, the priority-based approach would result in KV cache from lower layers of both sessions being moved to HBM, while other layers will be moved once the request arrives.

The GPU memory required to serve an LLM request primarily depends on the number of prompt tokens and the number of generated tokens. Estimating the memory requirements for an LLM request is challenging [14, 16], as the number of tokens generated by a request is not known a priori. This uncertainty makes it difficult to accurately determine the amount of free GPU memory, complicating GPU memory management.

Consider the following example: a GPU is serving an LLM request associated with Session ID: 1. While this request is being processed, an advisory request arrives for Session ID: 2. Based on the current free GPU memory, the system decides to prefetch the K,V cache for Session ID: 2 onto the GPU in anticipation of the actual inference request. However, as the inference for Session ID: 1 continues, the size of its K,V cache grows, eventually consuming all available GPU memory. This situation leaves no memory for the decoding process of the ongoing LLM request, causing a bottleneck.

In this scenario, the optimal decision would have been to avoid prefetching the K,V cache for Session ID: 2. However, the information needed to take this action was not available beforehand.

In cooperative memory management, the Symphony node manager greedily transfers the K,V cache to occupy available GPU memory whenever it is free. However, under increased memory pressure, the underlying serving library can overwrite this memory by purging parts of the K,V cache. Since a copy of the K,V cache is already stored in host memory, this operation requires no additional data transfer. Since K,V cache blocks are overwritten based on their assigned priority. Blocks associated with later layers in the network are given the lowest priority, followed by K,V caches with the smallest size, which are assigned the second-lowest priority. We would like to highlight we use cooperative memory management only for managing GPU HBM. For

Symphony scheduler provides a flexible interface that allows cluster administrators to implement any desired scheduling policy atop the building block of request-level scheduling. To demonstrate this flexibility, beyond load balancing, we also implement request prioritization. This helps serve a common requirement in LLM serving, namely user prioritization; for instance, users on a paid plan for a chatbot might be given higher priority than free-tier users. An approach to achieve this would involve preempting low-tier requests on a node when a new prioritized request arrives and then running the priority request. However, this approach can lead to significant slowdowns if multiple high-priority requests arrive on the same node, leading to poor load balancing. Additionally, prioritizing one request can negatively impact the latency of other non-priority requests. Using Symphony, we can migrate high-priority requests evenly across nodes based on advisory requests and selectively pause low-priority requests only when their execution impacts latency. We implement a request prioritization scheduler and evaluate it in Sec 4.5.

Symphony performs scheduling transparently, i.e., it does not change the underlying model or the data. It only provides a mechanism to manage K,V caches when serving multi-turn LLM workloads. However, Symphony can be easily made compatible with approximation-based methods like  [21, 20] which compress the K,V cache.

Existing schedulers like [2, 36, 38] perform scheduling for "single-request-and-response". These schedulers do not account for "mult-turn" session-based LLM workloads. Symphony on the other hand performs request-level scheduling. It can be used in conjunction with any of the existing schedulers; e.g., at the node level we can have a fairness scheduler running [38] while at the cluster level, we can have Symphony’s load balance policy running.

Symphony assumes that advisory requests arrive early enough to allow sufficient time for K,V cache migrations. However, in extreme cases where there is insufficient time between the advisory request (or there was no advisory request) and the associated inference request, performance may be impacted. We evaluate this scenario in Section 4.5 and observe that, due to asynchronous layerwise reads and writes we are able to load the K,V cache from the host memory with only 6% loss in latency when 10% of requests arrive without sending an advisory request.

In Figure 12(a), we compare Symphony with vLLM [16] and InferCept [1] while serving LLaMa-3.1 8B while varying the number of concurrent users. The results show that Symphony reduces normalized end-to-end latency by a factor of $1.4\times$ to $1.9\times$ compared to vLLM. Similarly, in Figure 13(a), we observe that when serving LLaMa-2-13B, Symphony achieves latency reductions of $1.31\times$ to $1.9\times$.

These improvements are primarily due to two factors. First, unlike vLLM, Symphony eliminates redundant computations, resulting in significant compute savings. Second, since Symphony, like vLLM, employs continuous batching, the faster prefill phase allows more requests to transition to the decode phase faster improving the overall throughput of the system. vLLM does not benefit from continuous batching during the pre-fill phase as the throughput of prefill stays constant with increased batch size.

When compared to InferCept, Symphony delivers a speedup of up to $2.5\times$. This improvement is primarily because InferCept uses a stateful serving model, which causes significant load imbalances across the cluster. In some cases, the number of requests on a single server can be as much as $2.8\times$ the median load across the cluster. This imbalance leads to severe latency increases and suboptimal hardware utilization.

In Figures 13(b) and 12(b), we observe that Symphony reduces the time to first token by up to $2.4\times$ compared to the vLLM and InferCept baselines. vLLM suffers from redundant prefill operations when recomputing KV caches of prior requests, which significantly increases the time to the first token. In contrast, while InferCept avoids wasteful decoding, it prioritizes completing the decode step on sequences whose K,V cache are stored in host memory, rather than focusing on prefill as vLLM does. On the other hand, Symphony uses vLLM’s scheduler and only manages state, avoiding redundant steps and improving time to the first token.

In Figures 12(c) and 13(c), we observe that Symphony can serve up to $8\times$ the number of users while maintaining a similar time per output token. For example, when serving 64 users, vLLM has an average time per output token of 18ms, whereas Symphony can serve 512 users with an average time per output token of 20.5ms while using the same number of GPUs. The primary reason Symphony outperforms vLLM is its ability to minimize redundant computation of K,V caches for multi-turn chatbot requests.

When compared to InferCept, Symphony can handle over $4.2\times$ the number of requests at high load (1024 users). The main reason InferCept is significantly slower is due to load imbalance, which causes poor cluster utilization.

To understand the importance of load balancing, we evaluate a new workload that should significantly benefit both InferCept and Symphony. In this "pre-fill-heavy" workload, we replace all requests with a 1024-token prompt and a 1-token response while keeping the original arrival times. This configuration benefits both systems, as they retain the K,V cache associated with previous prompts and responses. However, the key difference is load imbalance. As shown in Figure 16, despite the favorable setup, InferCept struggles to achieve high throughput due to load imbalance.

One of the key observations in Symphony is the use of advisory requests for prefetching the K,V cache. To evaluate the performance of Symphony in the absence of advisory requests, we set up an experiment where advisory requests are missed. In Figure 17, we observe that as the proportion of missed advisory requests increases, the normalized token latency also increases. For a 10% miss rate, the latency to produce one token increased from 21.3ms to 24.4ms by approximately 6% The primary reason for this increase is the inability to efficiently perform load balancing and prefetch the K,V cache.

To demonstrate that Symphony supports additional policies beyond load balancing, we implement a prioritization policy. For sessions marked as high priority, the K,V cache for the associated request is immediately moved to the GPU HBM to prevent delays in processing. We vary the percentage of high-priority requests (10%, 30%, 50%) and compare this approach with vLLM’s priority scheduling. Our results (Figure 18) show that, due to the absence of redundant computation and zero overhead in K,V cache migration, Symphony delivers better tokens per second for both prioritized and regular jobs.