1 Introduction↩︎

Unlike LLM training, which is a one-time cost, LLM inference is an ongoing and significantly more expensive process due to high GPU costs and energy consumption. For instance, ChatGPT approximately receives 4.6 billion user visits per month and 2.5 billion prompts per day¹, incurring GPU expenses that might exceed $160 million monthly². Our back-of-the-envelope calculation also expects millions of dollars for monthly GPU expenses³. Recent advancements, such as OpenAI’s o1/o3 models, Deep Research⁴, and agentic frameworks, further underscore the rising demands of LLM inference, as these models extend inference time to enhance reasoning capabilities. Meanwhile, open-source models like Llama and DeepSeek enable broader adoption of LLM inference. Reducing LLM inference latency is thus crucial for both economic and environmental sustainability, given the substantial CO2 emissions associated with GPU usage [1], [2].

LLMs are also increasingly making synergies with database systems and applications in either LLM4DB or DB4LLM fashion [3], alongside the recent proliferation of AI4DB and DB4AI studies [4]. For LLM4DB, LLMs are used in complex data management [5], [6], database administration [7], [8], query optimization [9], [10], text-to-SQL translation [11], and semantic operators that extends relational operators to use LLMs [12].

For DB4LLM, researchers have focused on designing more efficient LLM inference systems utilizing database and operating systems techniques [13]–[24]. The least recently used (LRU) cache replacement policy is widely adopted in many inference systems [14], [25]–[27] as for the buffer management in database systems [28].

DB4LLM and system development efforts often involve redesigning and reconstructing entire system stacks. Such systems are labor- and hardware-intensive, requiring extensive analysis, implementation, and GPU usage. System development typically focuses on the final deliverable in terms of GPU hour savings in online workloads [14], [24], [25], but often ignores the GPU hours and costs spent in the development and analysis phase. A recent study [29] shows that just finding the best set of system configuration knobs can take 42K GPU hours with an estimated cost of $218K, while the GPU hours spent on development and analysis can cost much more.⁵ Moreover, it remains unclear whether existing systems are fully utilized, potentially leaving untapped optimization opportunities. A more cost-effective, goal-oriented approach is needed instead of relying on a naive trial-and-error process consuming extensive GPU hours.

As a first step toward a cost-effective approach, we adapt simulation-based LLM inference based on simple cost models, like the ones used in DMBSs, to predict inference performance without extensive use of GPUs, following the principles of [29]. However, unlike [29] that uses simulation to tune system configuration knobs, we use simulation to (a) analyze LLM inference performance, including a what-if analysis that assumes unlimited hardware capacity to estimate performance upper bounds, and (b) develop new strategies that can optimize the performance when deployed to actual LLM inference systems. Hence, we focus on saving GPU hours in both pre-deployment (development and analysis) and post-deployment phases. We also show that simpler cost models, even linear ones, are effective enough to reveal interesting insights to derive such strategies, and their closed-form formula and monotonicity property enable principled and theoretical analysis in contrast to typical empirical evaluations.

In this paper, we specifically target request preemption and cache replacement policies under high request contention. LLM inference systems cache each request’s intermediate results in GPU memory whose size grows over time, as more output tokens are generated and their results are cached. Therefore, when the contention is high, the limited cache size may preempt some running requests and restart them later, freeing their cached data to prioritize running other requests. While most studies focus on scheduling requests (forming batches of requests and deciding when to launch each batch, analogous to multi-query optimization in DBMS), preemption and cache replacement policies remain largely underexplored. Existing systems typically rely on simple heuristics: using LRU on request completion to manage cached data, and preempting the newest request first (called NRF) when preemption occurs [14], [25]. Moreover, systems typically avoid preemption altogether by delaying request scheduling, striving to reduce contention and improve inference performance.

Contrary to popular belief, preemption should not be avoided. Our analysis based on theoretical and actual evaluations reveals a counterintuitive insight: harnessing preemption can improve performance more than conservatively avoiding any preemption, particularly for short requests. We prove the optimality of preemption and non-preemption theoretically, depending on the request length, including when to preempt a request and which requests to preempt in order to improve performance. First, we apply the five-minute rule [30] in DBMSs to LLM inference and calculate the break-even intervals of keeping cache items in GPU memory before evicting them, to determine which requests or data are immediately preemptable. We conclude that this rule justifies the non-preemption of any requests, but is insufficient to tell which requests should be preempted to improve performance. Instead, we define a concept of progress and propose a progress-aware preemption and cache replacement policy, which we call shortest-request first (SRF) policy. The progress reflects the cost of processing a batch of request (lower the better) and the number of tokens generated from the batch (larger the better), considering the restarting overhead of requests. We show that this progress is large for preempting short requests.

Regarding the workloads, we first target general LLM inference workloads with high demands such as conversations and text generations in this paper for maximum and universal GPU hour savings, not database-specific workloads in LLM4DB applications. When deployed to a real-world LLM inference system, our policy consistently reduces inference latencies by up to 15% without performance regression or losing fairness in serving concurrent requests, where the estimated optimal reduction is 40% with an infinite cache size. From a simple calculation, this indicates the potential for significant economic and environmental savings, for example, more than $24 million per month for ChatGPT. We also observe that LLM inference has hit a memory wall as in analytical query processing in DBMSs [31], where the bandwidth matters. This calls for a better implementation of hardware-conscious LLMs and algorithms inside LLMs to resolve the memory-boundness of LLM inference and hide data transfer overheads.

In summary, our contributions are as follows.

• We provide a comprehensive survey of LLM inference systems from the perspective of data management.

• We show that simulations based on simple cost models are sufficient to yield meaningful insights that lead to the development of new inference performance optimization techniques without requiring many GPU hours during the development and analysis phase.

• We find that preempting short requests under high memory contention can improve performance by 2x when compared to the common practice of avoiding preemption altogether. The reason is that short requests incur low restart overheads and hence generate output tokens faster despite being preempted. We prove our findings through theoretical formulations.

• We apply Gray and Putzolu’s five-minute rule to cache management in LLM inference, and show that the break-even interval for keeping cache items in GPU memory varies from sub-second to a few minutes, depending on the request length, exceeding the actual reuse intervals.

• We propose a new preemption and cache replacement policy that preempts the shortest requests first. It improves inference performance by up to 15% under high contention compared to preempting newest requests first in a real-world inference system, vLLM[14], and also improves performance in other systems, SGLang[25], and Dynamo[27], by up to 20%. Our policy is easy to implement with a few lines of code in actual systems and shows no performance regression or losing fairness. These indicate a safe approach to substantial GPU cost savings without extensive development overheads.

The rest of the paper includes background through a survey of LLM inference systems focusing on data management (Section 2), an overview of our simulation-based analysis and actual system integration framework (Section 3), the simulation design (Section 4) and results (Section 5), a five-minute rule for LLM inference (Section 6), a theoretical analysis and our new cache replacement policy (Section 7), the evaluation of our policy in actual LLM inference systems (Section 8), and a conclusion (Section 9).

2 Background↩︎

This section provides background information about processing LLM inference requests and cache management, analogy between LLM inference systems and DBMSs, and a comprehensive survey of related work.

2.1 LLM Inference Request Lifetime and Cache Management↩︎

As shown in Figure 1, when an LLM inference request arrives to an inference system, it is first kept in a waiting queue until the request scheduler launches a batch containing this request. In the prefill phase, the request’s input tokens or prompt tokens are processed by an LLM. The prompt can be chunked and processed in multiple steps/batches. If the prefill is done, it generates a new output token and transits to the decode phase. In each decode step, the last generated token is processed to generate another one. When the available resources fall short, some running requests can be preempted to prioritize running others. These are restarted or refilled later. When the last generated token is EOS (end-of-sequence) token or the output length reaches a specified limit, the request is completed.

In the mainstream LLM models, which are autoregressive Transformer-based models we consider in this paper, each attention operation inside a model’s layer produces one key-value (KV) tensor for each processed token [32]. These KVs are maintained in the KV cache [20] in GPU memory and reused for all subsequent decode steps, since 1) processing later tokens requires the KVs of all preceding tokens, and 2) it is more efficient to cache and reuse KVs than recomputing them every step. The attention can be expressed mathematically as

\[\label{eq:attention95formula} \begin{align} & Q_{i} = f_Q(x_{i}), K_{1:i} = f_K(x_{1:i}), V_{1:i} = f_V(x_{1:i}), \\ & z_{i} = Attention(Q_{i}, K_{1:i}, V_{1:i}), \end{align}\tag{1}\]

where \(x_i\) is the hidden state of the \(i\)-th token of a request, \(Q_{i}\) is the query tensor for the token, and \(K_{1:i}\)/\(V_{1:i}\) is the key/value tensors for the first to \(i\)-th tokens. Each \(f\) denotes a matrix multiplication. \(Attention\) is the attention operation generating another hidden state, \(z_i\), for downstream intra-layer operations. Note that \(K_{1:i}\) and \(V_{1:i}\) can be reused for processing any subsequent \(j\)-th token \(x_j (j > i)\). \(z_i\) is transformed into the input hidden state \(x_i\) of the next layer, making the computation of \(x_i\) autoregressive (depending on all preceding tokens). We detail the model layers in Section 4.2.

Since every running request appends one KV to the cache in GPU memory at each decode step, where the GPU memory has limited capacity, some requests may be preempted and their KVs freed if the cache becomes full. When a request is completed, its KVs can be kept for future requests with the same prefix and replaced under the LRU policy [14], [25].

Refilling the KVs can be done either by 1) recomputing KVs in GPU or 2) offloading KVs to secondary storage (e.g., CPU memory, SSD) and swapping in when they are needed. While the offloading requires fast interconnects between hardware devices, low PCIe bandwidths compared to the high computational capacity of GPUs often increase the end-to-end latencies of inference requests. A popular inference system, vLLM[14], deprecates offloading because of higher latencies and complex data management. Offloading can be a reasonable option [26], [27] with faster interconnects, newer hardware chips (e.g., Grace-Hopper superchips), or to avoid refilling long inputs where prefill/refill takes quadratic time to request lengths (Section 4.2), reduce GPU usage [27], and reuse KVs across requests and GPUs [26]. The overhead of transferring KVs may dominate runtime if not overlapped carefully [33].

We develop our ideas in Section 7.4 based on that both recomputation and swapping-in costs monotonically increase with the number of KVs (Sections 4.2 and 5.3).

Other than the attention operation and KVs, the matrix multiplications in each LLM model layer require loading model weights (matrices) from GPU memory. To amortize this overhead, the request scheduler (simply scheduler) batches multiple requests together.

2.2 Analogy between DBMSs and LLM Inference Systems↩︎

Before we survey related work, we set an analogy between LLM inference systems and DBMSs for a better understanding of inference systems and clarification of our scope. Here, we consider online inference systems that schedule concurrent requests from multiple users, not pre-planned offline inference systems that are specialized in certain optimizations, such as supporting LLMs larger than the GPU memory [34], partial KV offloading to quickly approximate the attention operation [16], and KV quantization [35].

Figure 2 shows five planes – application, decision, operator, data, and hardware – in both types of systems. At the highest level, applications refer to the services accessible to users. The decision plane corresponds to request scheduling for processing concurrent requests while maximizing system performance, considering the available hardware and software resources. This is similar to the query optimization in DBMSs. For the operator plane, the attention operation and optimized decoding strategies are analogous to physical operator implementations in DBMSs. For the data plane, KV cache management is akin to the buffer management, LRU being the dominant strategy to maintain the completed requests’ KVs. Hardware includes utilizing available resources.

This paper focuses on request preemption (decision plane) and KV cache replacement policies (data plane), the decode-to-preempt transition in Figure 1. This scope is largely orthogonal to other extensively-studied scheduling techniques (decision plane) that consider the waiting-prefill-decode transitions in Figure 1, but can be plugged in to any preemptive schedulers. The following section explains each plane in detail.

2.3 Related Work↩︎

This section surveys LLM inference systems through the lens of the five planes in Figure 2 and summarizes them in the taxonomy in Table ¿tbl:tab:llm-taxonomy?. From the database domain, our what-if analysis in Section 5 resembles the one in [36], but ours focuses on LLM inference. We focus on the closest domains since LLM inference system and optimization is a very broad field [3], [37]. We also focus on systems with open-sourced implementations whenever possible to facilitate transparent reproducibility and robust follow-up research.

Overall, we observe that the first wave of general-purpose, open-source inference engines such as vLLM[14], SGLang[25], Sarathi[22], and DistServe[15] has largely defined the baseline system design space. Subsequent systems tend to introduce incremental scheduling or KV-management techniques on top of these baselines, but there is still no widely accepted, ground-breaking redesign of the serving stack. In particular, preemption and KV-cache replacement under contention are much less explored than batching and operator-level optimizations. Our work targets exactly these two aspects (decision and data planes) and shows that even simple, theoretically grounded policies can still yield substantial GPU-hour savings when integrated into these mature stacks.

2.3.1 Application Plane↩︎

At the application plane, LLM inference systems serve diverse workloads such as conversational assistants, code assistants, RAG pipelines, and data-centric applications such as semantic query processing and agents over databases [12]. These applications impose heterogeneous service-level objectives (SLOs): interactive chat requires low time-to-first-token (TTFT) and low time-per-output-token (TPOT); batch analytics workloads emphasize throughput and GPU-hour cost; and multi-tenant deployments must ensure fairness across users and models. LLM4DB applications mentioned in Section 1 fall into this plane. Our work is mostly orthogonal to application-level design: we do not change the user-visible interface or the semantics of the LLM outputs.

2.3.2 Decision Plane: Scheduling and System Orchestration↩︎

At the decision plane, the main goal is to schedule concurrent requests and orchestrate model execution to maximize throughput and SLO attainment under hardware constraints. Most existing systems focus on batching and phase scheduling.

Continuous and hybrid batching. Orca[13] introduces continuous batching, which breakdowns a request lifetime into multiple steps in Figure 1 and schedules requests step-wise. Sarathi[22], [23] and DeepSpeed[24] propose chunked prefill and hybrid prefill–decode batching: large input prompts are processed in chunks, and prefill and decode tokens are interleaved in the same batch to better utilize GPU resources.

Prefill–decode disaggregation. DistServe[15], Dejavu[38], Splitwise[1], ExeGPT[39], and Dynamo[27] disaggregate the prefill and decode phases across GPUs. Prefill GPUs handle heavy one-shot context processing, while decode GPUs specialize in long auto-regressive decodes. These systems must decide how to route KVs between prefill and decode workers.

Pipelining and intra-batch parallelism. NanoFlow[17] further partitions each batch into nano-batches to overlap operators within a layer and across requests, while Medha[40] adopts sequence pipeline parallelism and adaptive prefill chunking.

Fairness and predictive scheduling. FastServe[41] proposes multi-level-queue scheduling with proactive KV offloading for latency-critical requests. ConServe[42] designs SLO-aware token-level scheduling with layer-wise preemption. D²LPM[43] focuses on locality-aware fair scheduling, while SynergySched[44] combines predictive models with a two-layer scheduler. These works emphasize fairness and SLO satisfaction but do not deeply study the interaction between preemption and KV-cache replacement.

Output-length-aware scheduling. Several studies predict or rank output lengths to improve scheduling [45]–[47], which is out of our scope. Our approach complements such work: through simulation and hypothetical schedulers that leverage exact output lengths, we quantify the performance upper bound of such predictors can provide, similar to evaluating the impact of perfect cardinality estimates on query plans before designing new estimators [48]. Furthermore, our findings also apply to scenarios where requests have identical lengths.

Across these systems, the preemption policy under KV-cache contention is typically very simple: most open-source implementations adopt newest-request first (NRF) for preemption and keep completed requests’ KVs under the LRU policy (Table ¿tbl:tab:llm-taxonomy?). To the best of our knowledge, our work, starting from our technical report [49], is the first to propose the shortest-request-first (SRF) preemption and cache replacement policy.

4pt

4pt

2.3.3 Operator Plane: Attention and Decoding Optimization↩︎

At the operator plane, LLM inference systems optimize attention and decoding kernels, which are analogous to physical operator implementations in DBMSs.

A large body of work focuses on more efficient attention kernels. FlashAttention[63]–[65] avoids unnecessary data movements during the attention computation without affecting attention outputs, which is now widely adopted and are enabled by default in systems such as vLLM. Sparse attention variants [66]–[68] and state-space models (SSMs) [69] change the attention structure and outputs to reduce complexity, but may degrade LLM accuracy [70]–[72]. We restrict ourselves to full-attention transformer models with FlashAttention-style kernels, since 1) a survey [73] shows that transformer alternatives including SSM and hybrid models remain niche, and 2) sparse attention and SSMs simplify the KV management where requests may keep a constant number of KVs during the lifetime.

Speculative decoding techniques [74] maintain a smaller proxy model that proposes candidate tokens, which the large model then verifies. This is akin to a work in DBMSs [75]. The efficiency gains depend on the proxy model’s accuracy and the composition of accepted versus rejected tokens. While speculative decoding can substantially improve efficiency, it complicates cost modeling and cache-management analysis, since speculative tokens may be discarded. We focus on single-model decoding and leave the integration of speculative decoding into our simulation and theoretical analysis as future work.

2.3.4 Data Plane: KV Cache Management↩︎

The data plane in LLM inference systems is centered around the KV cache: how KVs are allocated, laid out, evicted, recomputed, offloaded, and reused across requests and devices. This plane is directly analogous to buffer and result-cache management in DBMSs, where LRU and its variants dominate.

Paged and prefix-aware KV caches. vLLM[14] introduces paged attention and a paged KV cache, which manage KVs with fixed-size pages, improving serving throughput. vTensor[18] decouples the KV cache allocation and attention computation in vLLM. SGLang[25] proposes radix attention, which effectively reuses the KVs and attention computations over the shared prefixes among multiple requests. These systems use LRU for completed requests and a simple NRF heuristic for preemption (Table ¿tbl:tab:llm-taxonomy?).

Offloading during request lifetime vs. completion. It is useful to distinguish two different roles of KV offloading. (i) Offloading during a request’s lifetime is used to temporarily free GPU memory under contention and later swap KVs back to continue the same request. Due to the low PCIe bandwidth between CPU and GPU that makes KV offloading a critical bottleneck, InfiniGen[16] offloads KVs to CPU memory and streams back only the most important tokens to approximate the full attention result. InstInfer[19] offloads KVs to flash storage, and NanoFlow[17] uses offloading as part of its intra-batch pipelining strategy. These techniques trade PCIe or NVMe bandwidth against GPU memory capacity and are highly sensitive to interconnect characteristics. (ii) Offloading after request completion aims at KV reuse across future requests or across GPUs. vLLM and SGLang can store completed prefixes for multi-turn conversations or for global prefix sharing. LMCache[57] builds a distributed KV cache layer; KVShare[58] shares KVs across tenants; and Mooncake[26] maintains a disaggregated KV pool with prediction-based early rejection of low-value prefixes. Our work targets case (i): we focus on what to preempt and evict during a request’s lifetime, while remaining compatible with post-completion KV reuse mechanisms.

Hybrid, layered, and token-level policies. AptServe[21] proposes a hybrid cache of KVs and the input activations for computing KVs to reduce memory footprint, but it can rather increase the footprint under grouped-query attention where KVs are smaller than activations [76]. FastSwitch[55] groups KV pages to improve spatial locality; LayerKV[56] allocates KVs layer-wise to better match memory hierarchies; MemServe[51] and LMCache[57] manage distributed KV pools across GPUs; and KVPR[60] and HeadInfer[61] explore hybrid recomputation-offloading and head-wise KV placement. HashEvict[53] uses locality-sensitive hashing to evict tokens that receive low attention, effectively moving from request-level to token-level eviction.

Compression and quantization. To further reduce memory footprint, KIVI[35] applies 2-bit quantization to KVs, and KVzip[59] performs query-agnostic KV compression based on importance. These techniques are orthogonal to scheduling and cache replacement decisions and can be combined with our policies.

Despite this rich space of mechanisms, replacement policies under contention remain simple. As summarized in Table ¿tbl:tab:llm-taxonomy?, open-source systems with online schedulers typically use (i) NRF for preemption and (ii) LRU for completed requests. To our knowledge, no prior work systematically studies the interaction between request length and preemption, nor proposes our SRF policy in [49]. Our SRF fills this gap: it chooses victims based on a progress metric that jointly captures KV size, restart overhead, and contribution to throughput, and it can be plugged into any preemptive scheduler and KV representation without changing other planes.

2.3.5 Hardware Plane: Hardware, Simulation, and Cost Modeling↩︎

The hardware plane concerns the underlying compute and memory hierarchy (GPUs, CPUs, interconnects, and storage) and how they are modeled. LLM-Viewer[62] derives theoretical operator-level cost models directly from hardware roofline parameters (FLOPs/s and bandwidth) and model structure, and shows that such models generalize well across GPUs. However, it analyzes only single batches without scheduling, does not model chunked prefill or preemption, and does not connect its estimates back to end-to-end workload behavior.

Vidur[29] is the first to provide a full-fledged LLM inference simulator with learned cost models based on measured GPU times. It allows service providers to explore hardware and system configurations under budget constraints, but its sklearn-based models (e.g., random forests) are not theoretically grounded, and their non-monotonicity makes it difficult to embed them into formal optimization frameworks such as our constraint satisfaction problem (CSP) [77] in Section 7.1. ExeGPT[39] also uses simulation to decide how to assign GPUs to prefills and decodes in a disaggregated setup. However, these focus primarily on configuration search rather than deriving new scheduling or cache replacement policies.

Our work connects these lines of research. We start from roofline-style theoretical models as in LLM-Viewer, derive simple linear cost models in terms of token counts and KV sizes (Section 4.2), and then fit their coefficients using a few hours of profiling data as in Vidur. We show that these linear models are accurate enough (6% average error in Section 5) to capture end-to-end performance, generalize across GPU types, and, importantly, are closed-form and monotone. These properties allow us to translate scheduling into CSP to predict performance upper bounds and conduct theoretical analysis to derive new policies that can actually save GPU hours in online inference. Not only the schedulers in existing systems, we also use hypothetical ones to predict performance upper bounds as mentioned earlier.

3 Overview↩︎

This section introduces an overview of our approach to reduce GPU hours spent in both pre-deployment (development and analysis) and post-deployment (inference request serving) phases in LLM inference systems.

Figure 3 illustrates this. The inference simulator captures and abstracts schedulers in real-world online inference systems, launching a batch of inference requests at each step. Each batch progresses the involving requests’ states by one arrow in Figure 1. Instead of using actual GPUs to process the batches, the simulator increments the global timer by the batch execution times estimated by the cost models. The estimation can be conducted in CPUs without using GPUs. As each workload run can take hours of GPUs [78], this approach can save significant amount of GPU hours.

The cost models are learned from performance profiling results [29] or theoretically built from hardware characteristics [62]. We take a hybrid approach, starting from linear theoretical models and learn the coefficients from profiling results without altering the model structure. Both learning and estimation occur in CPUs.

While existing simulators focus on deployable schedulers, i.e., implemented in inference systems, we also propose to use hypothetical schedulers that allow estimating performance upper bounds leveraging the workloads information which is unknown in advance in online serving scenarios. For example, we can leverage the output lengths of requests to better schedule them considering their exact resource demands, preventing unnecessary resource contentions, and the resulting scheduler acts as a performance upper bound of the output-length-prediction schedulers in Section 2.3. We can also conduct diverse what-if analyses, for example, decreasing or increasing the GPU memory size or bandwidth considering multi-tenancy and next-generation GPUs, which also act as performance lower and upper bounds.

A benefit of using simulation is that the development overhead is much smaller inside simulators than in actual inference systems. For instance, the scheduler implementation of vLLM[14] is around 2.1K lines of python code, which can be abstracted into 0.2K lines in simulators [29].

By using simulations, we first show that we can save GPU hours in the development and analysis phase, where simple linear cost models are enough to capture actual inference performance and provide meaningful insights. They also provide a closed-form of cost estimation and monotonicity property, which allow translating optimal scheduling into a mathematical optimization problem, i.e., constraint satisfaction problem (CSP) [77]. This is unachievable with the random forest-based models in [29]. Based on these, we propose new effective preemption and cache replacement policies.

Our final goal is to save GPU hours in the actual inference serving workloads outside the simulations. This corresponds to our inference system part in Figure 3. We integrate/deploy our ideas into actual systems, including vLLM, and prove that these can actually save GPU hours in online workloads, where requests may continuously arrive, without performance regression and losing fairness in request serving. We use vLLM as the main inference system, and the monitored performance can be sent to the simulator to calibrate the cost models.

4 Simulator Design↩︎

This section explains our simulator design: schedulers (Section 4.1) and cost models (Section 4.2).

4.1 Schedulers↩︎

As mentioned in Section 2, we focus on preemptive schedulers in open-source online inference systems. Their schedulers behave quite similarly, serving requests in first-come-first-serve (FCFS) manner. Still, each batch can contain requests in different phases (prefill or decode), and schedulers may prioritize different phases. We pick two representative schedulers from vLLM[14] and Sarathi[22], [23], each of which prioritize running prefill and decode requests, respectively. Sarathi further enables chunked prefill and hybrid batching as explained in Section 2.3. These correspond to deployable schedulers in Figure 3.

For a request having \(I\) input tokens and generating \(O\) output tokens, its peak number of KVs in the KV cache is \(I + O - 1\) considering that the last token does not need to be stored to generate another one. Since the output length \(O\) is unknown in advance, the cache initially allocates \(I\) tokens for the request [14] or with some margin. Each new KV generated in the decode step is appended to the cache. When output sizes are large, high contention can occur among concurrent requests competing for appending their KVs to the cache, resulting in request preemptions.

As noted in Section 2.3, most systems adopt newest-request first (NRF) preemption policy. In subsequent sections, we show that preempting long requests leads to suboptimal performance, and preempting shortest requests first (SRF) improves performance without performance regression while preserving fairness.

For hypothetical schedulers, we consider preemption-free (PF) schedulers that reserve the peak KV usage (\(I + O - 1\)) when starting a request, assuming that the output size \(O\) is known in priori. An arbitrary preemptive scheduler can be converted into a preemption-free counterpart.

4.2 Cost Models↩︎

This section explains the cost models for estimating batch execution times. We primarily consider GPU time as the main overhead as in [29]. CPU overheads such as scheduling can be largely overlapped, e.g., with asynchronous scheduling, leaving GPU computation as the critical path [17]. In databases, this is analogous to first focusing on the query optimization performance in terms of execution time savings, rather than the query optimization time itself, which is out of our scope.

Processing a batch of requests consists of feeding the embeddings of tokens to process in requests to the first LLM layer and consecutively feeding the previous layer’s outputs as the inputs to the next layer. The final layer’s outputs are fed to the softmax function to generate an output token.

Figure 4 shows the intra-layer operators of the Transformer architecture. For non-attention operators including matrix multiplications (matmuls), all requests’ tokens’ intermediate results (activation values) are concatenated and processed together, since the operators have distributivity over concatenation, and the overhead of loading the model weights (matrices) can be amortized across the requests in the same batch. This is represented as \(\sum_{r \in \mathcal{B}} r.c = \sum c\) in Figure 4 where \(r.c\) denotes the number of tokens to process for a request \(r\), and \(\mathcal{B}\) is a batch of requests. \(h\) denotes the embedding dimension, the size of embedding for a single token that is input to a layer.

Q_proj, K_proj, and V_proj (QKV_proj) denote the matmuls \(f\) in Equation (1 ). Q_proj generates the same-size output as the input (by multiplying \((h \times h)\)-size matrix), while K_proj and V_proj may generate smaller-size outputs. Here, \(\alpha \, (\leq 1)\) denotes the degree of grouped query attention (GQA) [76], and the resulting KV for a token has the size of \(2\alpha h\). This is a standard technique to reduce the size of KVs. The generated KVs are stored in the KV cache. Note that these matmuls are pre-attention operators, not part of the attention.

Regarding the attention operator, the prefill- and decode-attention in Figure 4 perform the attention of the same-phase requests together (but using the same kernel implementation) [14]. Attention operators read the KVs of prior tokens specific to each request. In the standard multi-headed attention [32], each attention head has dimension \(H = h/N_Q\) where \(N_Q\) is the number of query heads. Since \(H\) is the same for K and V, the number of KV heads, \(N_{KV}\), is equivalent to \(\alpha N_Q\) from \(H = \alpha h / N_{KV}\).

The following operators including three matmuls, O_proj, UG_proj, and D_proj, generate the same-size output (\(h\) per token) as the input embedding to the layer and pass it to the next layer. \(h'\) denotes the hidden dimension, typically larger than \(h\) [79]. When tensor parallelism is enabled, model weights are equi-partitioned to multiple GPUs, and All_Reduce (element-wise) adds the broadcasted outputs from other GPUs.

Now, to build the cost models for intra-layer operators, we start from theoretical cost models [62] that are solely based on the LLM and hardware characteristics instead of actual operator execution times. The LLM determines the number of floating point operations (FLOPs) and amount of data read/write (RW) per intra-layer operator.

Table ¿tbl:table:flops95and95data? shows the variables that determine FLOPs and RW. Here, we consider a single request’s input \(c\) tokens instead of \(\sum c\) for simplicity. For example, for a matmul between \((c \times h')\) and \((h' \times h)\)-size matrices (D_proj in Figure 4), it takes \(2ch'h\) FLOPs [17], loading \(h'h\) model parameters and \(ch'\) inputs, and storing \(ch\) outputs. Therefore, both FLOPs and RW are linear to \(c\), and the bias term captures the cost of loading model weights since both \(h'\) and \(h\) are fixed. In case of tensor parallelism, the amount of data to transfer between GPUs in All_Reduce is also linear to \(c\).

For attention, we enable the standard FlashAttention technique [63]–[65] and calculate its FLOPs and RW as in [62], which is more complicated than matmuls. If all \(B\) requests in a batch have the same number of input tokens \(c\) and \(m\) KVs to read from the KV cache, and \(H\), \(N_Q\), and \(N_{KV}\) denote the head dimension, number of query heads, number of KV heads, then

\[\label{eq:attention95flops} \begin{align} \text{FLOPs} = 4 c (c+m) B H N_Q, \end{align}\tag{2}\]

\[\label{eq:attention95data} \begin{align} \text{RW} = & 2 c H N_Q + 2 c (c+m) B N_Q \\ + & 2 \ceil{c/H} (c + m) B H N_{KV}. \end{align}\tag{3}\]

The hardware (GPUs) determines the FLOPS (computational capacity of GPUs in terms of operation throughput, in FLOPs/s) and bandwidth (in byte/s), we can compute an operator’s theoretically optimal execution time as:

\[\label{eq:latency95flops95data} \begin{align} T_{opt} = max\Big(\frac{\text{FLOPs}}{\text{GPU\_FLOPS}}, \frac{\text{RW}}{\text{GPU\_bandwidth}}\Big), \end{align}\tag{4}\]

assuming complete overlap between computation and data transfer, which leads to discrepancies with practice (we show these in Section 5.2).

Still, the theory well explains the linearity of actual operator times in Figure 5, where x-axes show the representative variables from Table ¿tbl:table:flops95and95data?. Note that non-attention operators largely depend on the number of tokens to process, \(c\), as both FLOPs and RW are linear to \(c\). The decode-attention is bottlenecked by reading KVs from GPU memory, whose time is therefore correlated with \(m\), the number of KVs to read from the cache. The prefill-attention time scales with \(c^2\) due to the quadratic complexity of attention, but more importantly, the quadratic amount of data transfer (we show in Section 5.2). Given an LLM and GPU setup, we train linear cost models, the coefficients of all variables in Table ¿tbl:table:flops95and95data? (theory), using actual operator times as labels (practice), over diverse number of tokens to process \(c\), number of KVs to read \(m\), and batch size \(B\).

To predict batch execution times, we sum the predicted execution times of all intra-layer operators and multiply by the number of layers. In our comparison with actual end-to-end workload runtimes in Section 5, the average and maximum relative error of the predictions is 6% and 12%, showing that simple linear models are effective enough to capture inference performance.

Note that our focus is not on building near-perfect cost models, but to 1) save GPU hours in the development and analysis phase and 2) explain the phenomena in LLM inference and derive meaningful insights to develop new techniques in actual inference systems. In contrast, Vidur[29] focuses on accurate predictions, reporting the maximum error of 9% using random-forest models. Its cost models are not theoretically grounded, nor closed-form or monotonic, thus it is unable to perform our theoretical analysis in Section 7 including the CSP. Furthermore, its goal is to find the best system configurations for specific workloads with exhaustive search, not to develop new techniques.

5 Simulator Results↩︎

This section shows that the simulation can save GPU hours in the development and analysis phase in LLM inference systems, proving it as an effective tool. By comparing with actual inference performance, we also address research questions that have received limited attention or generated misbelieved answers.

After our setup in Section 5.1, Sections 5.2-5.3 are based on theoretical cost models and actual measurements, and Sections 5.4-5.6 are based on hybrid cost models (learned coefficients on top of theoretical models), and Section 5.7 is based on actual measurements to confirm the simulation results.

5.1 Setup↩︎

Model and Hardware. We follow the default configuration of [29], using the Llama-2-7B model on an A100 or H100 GPU with 80GB memory and the KV cache size to 100K as default. In Section 8 on real-world systems, we scale up to Llama-3-70B model with context size \(S\) of 128K, on four GPUs to show that the insights found in this section generalize to other hardware-model configurations. We use 4 GPU hours to calibrate our cost models.

Metrics. We mainly use the end-to-end latency and time-per-output-token (TPOT) that measure the system-side and user-side inference performance. Tokens-per-second (TPS), the number of generated tokens divided by latency, and time-to-first-token (TTFT), the delay to generate the first token, follow similar trends with the latency. The latency is critical for measuring GPU hour savings in online serving, and data analytics workloads using LLMs [12] consider latency as the primary metric as in the database OLAP workloads. TPOT is an indicator for service-level objective (SLO) attainment similarly to constant-delay algorithms in databases [80]; larger TPOT indicates less interactivity in user experience.

5.2 What Makes a Batch Compute-Bound?↩︎

Previous studies [22]–[24] have shown that matmuls (‘*_proj’ in Figure 4) take the majority of the runtime for both prefill- and decode-batches despite the quadratic complexity of the attention computation, for diverse \((c, m)\) values (\(c\): number of tokens to process, \(m\): number of KVs to read) and batch sizes. The quadratic computation is what has been believed to make prefill-attention compute-bound and decode-attention memory-bound [17], determining the resource utilization of a batch.

However, we show that there are misbelieves. We first breakdown and compare the operator times in Figure 6: the theoretical batch execution times with Equation (4 ) and actual times. It also shows that matmuls are the major bottleneck. However, while the complexity of prefill-attention is quadratic to \(c\) (Table ¿tbl:table:flops95and95data?), the attention becomes the actual bottleneck for decodes with \(c=1\), not prefills, for larger batch sizes and \(m\). Furthermore, attentions have a larger gap between theoretical times and actual ones than the other operators.

To clarify these, we adapt the roofline analysis [62] in Figure 7. The roofline shows the hardware characteristic; it is a union of the left memory-bound region with increasing performance bound (slope is the GPU bandwidth) and the right compute-bound region with fixed performance bound (of GPU FLOPS) with a turning point in between. An operator’s intensity (FLOPs/RW) determines its compute-/memory-boundness, and performance is the achieved throughput of FLOPs. Note that all attention points are memory-bound, even for the prefills. Hence, the attention time scaling with \(c^2\) in Figure 5 (c) is due to the quadratic data transfer cost in Equation (3 ), not its computation. Attentions are also distant from the roofline, indicating the severe under-utilization of GPU bandwidth due to interleaved (not overlapped) computations. This explains the gap with theoretical times in Figure 6, and justifies fitting the cost models with actual times in Section 4.2.

Remark. Attentions are memory-bound. Only matmuls can be compute-bound, when the number of tokens to process, \(c\), is large enough to surpass the cost of loading fixed-size model weights. The whole batch can be compute-bound when 1) matmuls are compute-bound, and 2) the number of KVs to read, \(m\), is not large enough to make the attention dominate the batch time. Decode-batches can also be compute-bound (Figure 7).

Because of the sequential nature of intra-layer operators, we need to make every operator balance compute and memory to make the whole batch balanced, more than simply batching prefill- and decode-requests together as in [23]. The challenge is in achieving the balance for attentions. In Figure 7, prefill-/decode-attention batches converge to certain points close to the roofline, as \(c, m\), and \(B\) (batch size) increase. From Equations (2 ) and (3 ), the intensity (FLOPs/BW) converges to \(2 / (1/H + \ceil{c/H} N_{KV} / (c N_Q))\). For the Llama-2-7B model, \(H = 128\) (head dimension) and \(N_{Q} = N_{KV} = 32\) (number of query and KV heads). For prefills with large \(c\), the intensity becomes \(2 / (1/128 + 1/128) = 128\). For decodes with \(c=1\), it becomes \(2 / (1/128 + 1) \approx 2\). Therefore, to balance attentions, either the model should have higher \(H\) and \(N_Q/N_{KV}\) values or the GPU bandwidth should be higher to push the turning point leftwards.

5.3 Should We Recompute or Swap KVs?↩︎

In case of preemptions, when evicting KVs from GPU memory and refilling them, two representative options are: (1) recomputing KVs and (2) swapping in the offloaded KVs from DRAM. Without specialized techniques (Section 2), (2) is largely inefficient than (1) due to the low PCIe bandwidth [14], [16].

Figure 8 shows the measured points for (1) and theoretically optimal performance for (2) over varying number of KVs. When # KVs is large, (1) is more efficient than (2). But when # KVs is small, (2) can be more efficient since (1) suffers from a fixed cost of loading model weights. Still, the turning point is small (less than 100 KVs) compared to the full KV cache size (100K KVs). The cost for loading KVs from GPU memory shows the advantage of using KV cache than recomputing KVs every time.

Remark. While the recomputation is more efficient than swapping in general, swapping could improve efficiency with future PCIe generations, in small-cache environments such as end-devices, or when sharing GPU memory with other applications (multi-tenancy). As shown in Section 5.2, the bandwidth is crucial in LLM inference efficiency.

5.4 Preemptive Schedulers (Simulation)↩︎

Now we consider preemptive schedulers in open-source inference systems and focus on the effect of preemption on inference performance. We show the results on A100 where the results on H100 are similar (while faster), and use KV recomputation to refill KVs in case of preemption. Note that previous analyses [14], [22]–[24] have largely focused either on the single-batch cases or simple trade-offs between latency and TPOT for multi-batch cases without focusing on preemption.

Workloads. For the analysis purpose, long, complex workloads with varying input and output lengths make it difficult to understand the behaviors of schedulers and discover new insights for improving them. Hence, to simply the analysis, here we use offline workloads that all requests arrive at time zero, with the same input size \(I\) and output size \(O\). Still, we later remove this assumption and use online workloads (continuously arriving requests) and heterogeneous \(I\) and \(O\) values in Section 8. Please refer to our technical paper [49] that simulates and compares the schedulers prioritizing requests based on their lengths under heterogeneous requests. We vary the \(I\) and \(O\) values from 1 to 1024 to cover a wide range of workloads where each request cannot be longer than Llama-2-7B’s context length, 4096. This range covers short-answer questions to long-text generations⁶. We later use longer requests in Section 8. We fix the number of requests to 1024 to represent high-contention scenarios.

Schedulers. As noted in Section 4.1, we employ the schedulers of vLLM[14] and Sarathi[23] as representative preemptive schedulers that show the best inference performance in [29]. Table 1 shows the schedulers we compare, including the variants of the two but excluding the ones that either performed similarly or worse in our experiments.

We group the schedulers in Table 1 based on their performance into: 1) Sarathi, 2) Sarathi\(_{C=S}\) and Sarathi\(_{nocp}\), and 3) vLLM and vLLM\(_{hy}\). Figure 9 shows the results for Sarathi, Sarathi\(_{C=S}\), and vLLM as representatives.

Latency and TPOT. Overall, as the input size \(I\) and output size \(O\) increase, latency increases across all schedulers. vLLM shows the lowest latency by prioritizing prefill requests and batch processing decodes in parallel, resulting in large batch sizes, except when high \(O\) values lead to frequent preemptions. Preemption rates increase with \(O\) because each request competes to keep more tokens in the KV cache. Sarathi generally has the highest latency (up to 13% higher than vLLM) but achieves a stable TPOT (up to 5.3x lower than vLLM) due to balanced handling of prefill and decode phases through hybrid batching and a smaller batch-wise token limit \(C\). This shows the trade-off between latency and TPOT as in [22], [23]. Sarathi\(_{C=S}\) resembles vLLM as it processes up to the same \(C\) prefill tokens per batch, matching vLLM’s prefill speed by managing up to \(C/I\) new running requests per batch. TPOT increases with \(C\) due to larger number of tokens to process, larger batches from higher prefill speed, and more KVs read in subsequent decode steps.

An interesting point is that TPOT decreases beyond a certain value of \(I\). For large \(O\) (e.g., 1024), frequent preemptions cause refills to dominate runtime, while larger \(I\) limits batch sizes and reduces preemptions. This reduces time intervals between token generations. For small \(O\), refills have a smaller impact.

Preemption. The key distinction between the input size \(I\) and output size \(O\) in terms of their effect on preemption is that \(I\) represents the immediate memory reserved, whereas \(O\) determines the peak memory usage after approximately \(\Omega(O)\) batches have been processed. Consequently, schedulers that only consider \(I\) but not \(O\) risk overloading the system by batching requests with their long-term memory demands underestimated. As \(O\) increases, this can lead to a significant increase in the number of preemptions.

Memory (KV Cache) Usage. Because Sarathi gradually adds running requests, it maintains stable memory consumption for KVs. However, for \(O = 1024\), Sarathi experiences high memory demand, occupying more than 90% of the KV cache alike other schedulers.

Remark. Schedulers face a basic latency-TPOT trade-off [22], [23]. Sarathi maintains a balanced latency and TPOT across varying \(I\) and \(O\) values. Other schedulers excel with moderate values but encounter preemption spikes under high memory demands due to aggressive batching. Sarathi mitigates this with a smaller max number of tokens per batch, \(C\). High TPOT results primarily from preemption, with batch size and KV load as secondary factors. Preemption increases with larger \(O\) values, while \(I\) acts as both a limiting factor (as new running requests are bounded by \(C/I\)) and an increasing factor (by raising memory demands).

5.5 How Good Is It to Avoid Preemption? (Simulation)↩︎

With a basic understanding of the factors affecting performance, we explore some key questions. Figure 10 provides a high-level view. We begin by comparing the schedulers in Table 1 to their hypothetical, preemption-free (PF) counterparts in Table 1. We use the output size \(O\) of 1024, a scenario with frequent preemptions, since in other cases, PF schedulers perform similarly to their original (non-PF) counterparts.

As illustrated in Figure 11, PF schedulers generally achieve better system performance, with latency reduction over their non-PF counterparts reaching up to 17%, 10%, and 14% for vLLM, Sarathi, and Sarathi\(_{C=S}\), since there is no refill overhead. However, PF schedulers exhibit higher TTFT since they try to reserve more memory in initiating requests, waiting more for the current running requests to complete and release their KVs. This TTFT increase is substantial – up to 1000x for vLLM and Sarathi\(_{C=S}\), and 1.7x for Sarathi – but is offset by lower TPOT, with reductions of up to 13x for vLLM and Sarathi\(_{C=S}\), and 7.4x for Sarathi.

Remark. There is a clear trade-off between TTFT and TPOT [22], and it is crucial to limit the number of running requests by considering the size of KV cache, \(M\), and the memory demands of requests. The effective batch size can be approximated as \(\frac{M}{I+O}\), as supported by Figure 11, where PF schedulers achieve an average batch size close to \(\frac{100K}{1+1024} \approx 98\) for \(I = 1\) and \(\frac{100K}{1024+1024} \approx 49\) for \(I = 1024\).

5.6 Is Increasing the KV Cache Size a Silver Bullet? (Simulation)↩︎

To avoid preemption and maximize the effective batch size, one might wonder if simply increasing the KV cache size, \(M\), to a sufficiently large value could solve all issues, possibly with multiple or future-generation GPUs. To explore this, we vary \(M\) from 100 to 1M, testing under different memory contention levels and hardware-model configurations to simulate lower memory budgets. Figure 12 shows results for the output size \(O\) of 32.

Interestingly, when the cache size \(M\) is small, PF schedulers actually show higher latency compared to non-PF ones, as they wait too long for running requests to release memory. In this context, preemption can rather reduce latency. As shown in Figure 12, preemption reduces latency by up to 1.9x and 2x for vLLM and Sarathi, under \(M\) = 100, and by 1.3x and 1.1x under \(M\) = 1K, mainly due to reduced TTFT. However, again these gains come with higher TPOT as a trade-off.

Remark. Preempting short requests can reduce latency by 2x compared to being too conservative to avoid any preemption under high memory contention, which we first evaluate in Section 5.7 then theoretically prove in Section 7. The results also highlight that increasing the cache size alone is not a complete solution. Enhanced memory bandwidth is essential to minimize the cost of reading KVs in memory-intensive decodes as well as the quadratic amount of data transfer in prefills (Section 5.2). In addition, Figure 12 shows that under a large cache size (1M), Sarathi and Sarathi\(_{C=S}\) utilize less than 20% of KV cache on average, even when processing numerous long requests, highlighting potential underutilization.

5.7 Results on a Real Inference System (Actual)↩︎

This section presents results from running the experiments in Sections 5.4 and 5.6 on a real LLM inference system (Figures 13 and 14). We use vLLM[14] v0.6.3 and run the generated schedules from the simulator. Later in Section 8, we integrate our new preemption and cache replacement policy in the actual system. For clarity, here vLLM refers to the scheduler as before, while vLLM-Sys denotes the inference system.

Figure 13 shows similar results with Figure 9, with the average and maximum relative error of 6% and 12% for latency.

Non-GPU time mainly consists of CPU-based scheduling and token sampling, where we leave optimizing them as an orthogonal future work. Recent inference systems and techniques, e.g., asynchronous scheduling [17] mentioned in Section 4.2, allow effective overlapping of CPU and GPU operations.

Figure 14 shows results for varying cache size \(M\). Consistent with Section 5.6, preemption decreases latency by up to 2.3x for small \(M\) values of 100 and 1K, and increases latency by up to 1.5x for larger \(M\) values.

Remark. The results on an actual inference system confirm our primary focus, that simulations can be an effective tool to save GPU hours in the development and analysis phase of inference systems, while still offering valuable insights. We re-emphasize that our focus is not on providing near-perfect simulations (e.g., less than 1% relative error) nor repeating existing findings (e.g., latency-TPOT trade-off), but on investigating new opportunities (e.g., preemptions) to develop better mechanisms in actual inference systems, ultimately reducing GPU hours in online serving. In subsequent sections, we ground our ideas in theory and then show how they deliver robust empirical results.

6 5-Minute Rule for LLM Inference↩︎

This section provides an interesting connection between databases and LLM inference from that they both maintain caches (or buffers). In Section 5.3, we have seen that it is more efficient to keep KVs in the KV cache than recomputing (or loading from DRAM), in terms of latency. However, it is unknown whether its also cost-effective in terms of GPU maintenance costs in on-demand cloud GPU environments and LLM services like ChatGPT.

That is, what is the break-even interval \(T_{break}\) for keeping the KVs in the GPU memory to be cost-effective, that if a KV is re-accessed after this interval, then it is better to discard it and recompute it later?

To answer this, we apply the five-minute rule [30] from the database domain, originally proposed for computing the break-even interval at which it becomes cost-effective to keep a data page in memory rather than fetching it from disk each time. The original formula is

\[\label{eq:five95minute95original} \begin{align} T_{break} & = \frac{\text{\# pages per MB of RAM}}{\text{\# accesses per second per disk}} \\ & \times \frac{\text{\$ per disk}}{\text{\$ per MB of RAM}}, \end{align}\tag{5}\]

when the price for cache memory ($/page/s) matches the savings in disk accesses per second ($/access/s). Similarly, in our case, the price for KV cache memory ($/KV/s) should match the savings in KV recomputation per second ($/recomputation/s), where the price terms cancel (both measured in GPU-seconds):

\[\label{eq:five95minute95llm} \begin{align} & T_{break} \\ & = \frac{\text{\# KVs per MB}}{\text{\# recomputations per second}} \times \frac{\text{KV cache size}}{\text{\# KVs per MB}} \\ & = t^1_{recom} \times M. \end{align}\tag{6}\]

Here, \(M\) is the KV cache size and \(t^1_{recom}\) is the time for recomputing 1 KV. For \(m\) KVs of a request, it becomes \(t^m_{recom} \frac{M}{m}\) where \(t^m_{recom}\) is the time for recomputing \(m\) KVs. With \(M\) = 100K and \(t^m_{recom}/m\) values obtained from Figure 8, we can compute that \(T_{break} \in [0.33\text{s}, 130\text{s}]\), with smaller values for larger \(m\)’s.

While the KVs of longer requests (larger \(m\)) have smaller break-even intervals (\(T_{break}\)’s), it does not indicate that that they need to be evicted more quickly than the shorter requests. It does not tell which requests to preempt but whether it is cost-effective to preempt a request after a certain interval. If a KV is actually reused after its break-even interval, then it would have been more cost-effective to discard it from the cache and recompute later.

Figure 15 shows the distribution of the reuse intervals for all workloads in Section 5.4 and compares it with the break-even intervals. The batch times or TPOTs are reuse intervals as each batch re-accesses the stored KVs of running requests. All reuse intervals are smaller than the break-even intervals, indicating that it is more cost-effective to keep all KVs in the cache. This, however, shows that all KVs are important, and we need a different approach to select which requests to preempt.

7 Theoretical Analysis and Shortest-Request First Replacement Policy↩︎

This section provides theoretical analyses based on previous sections, starting from a global optimization problem for inference scheduling to deriving a new cache replacement policy for improving LLM inference performance.

7.1 Which Schedules are Optimal?↩︎

This section applies constraint satisfaction problem (CSP) [77] to find optimal schedules and prove the insights found in the previous analysis in Section 5. To the best of our knowledge, this is the first attempt to apply CSP to LLM inference scheduling. The closest work, ExeGPT[39], regards scheduler as a black box and searches for the best scheduling parameters out of the box, while we formulate the scheduling itself into CSP. This is a more fine-grained approach, allowing higher flexibility and performance upper bounds, but with a trade-off of higher computational complexity. As CSP utilizes the output lengths of requests, it is hypothetical. Unlike other schedulers that specify how to schedule requests algorithmically, solving CSP gives what: one or more schedules that 1) satisfy constraints to construct valid schedules and 2) achieve the best performance objectives, as well as the achievable performance bounds.

Performance upper bounds allow for a more goal-oriented development of efficient inference techniques, determining promising ideas that are worth developing, unlike naively seeking a better scheduling algorithm without assured performance improvements, or sweeping parameters to find the best system or scheduler configuration [29]. For instance, we can validate whether a better schedule exists that could reduce the latency of current schedules by 10% for specific workloads, and this schedule may not be generated from any existing schedulers. The optimization target can be adjusted to meet objectives such as latency, throughput, or fairness, if these can be represented in a formula.

In our CSP formulation, we first establish key notations. The index \(i \geq 1\) and \(j \geq 1\) represent the \(i\)-th request \(r_i\) and \(j\)-th batch \(\mathcal{B}_{j}\) (each batch is a set of requests). We also use \(j = 0\) as a virtual index to denote the initial system state, \(I_i\) and \(O_i\) as input and output sizes of \(r_i\), and \(\mathbb{I}_{cond}\) as the indicator variable, which is 1 if a condition \({cond}\) is true and 0 otherwise. We use \(C\) as the maximum number of tokens to process per batch and \(M\) as the KV cache size. Now we explain the three parts of our CSP: variables, constraints, and objectives.

Variables. \(s_{i,j}\) represents the number of all input and generated tokens for \(r_{i}\) after processing \(\mathcal{B}_{j}\), with \(s_{i,0} = I_i\).

\(m_{i,j}\) denotes the number of KVs stored in the cache for \(r_i\) after processing \(\mathcal{B}_{j}\), with \(m_{i,0} = 0\). \(c_{i,j}\) denotes the number of tokens to process for \(r_i\) at \(\mathcal{B}_{j}\), which is 0 if \(r_i \not\in \mathcal{B}_{j}\). \(g_{i,j} = \mathbb{I}_{r_i \text{ generates a token at } \mathcal{B}_{j}}\) and \(e_{i,j} = \mathbb{I}_{r_i \text{ is preempted at } \mathcal{B}_{j}}\).

Constraints. The constraints establish the interactions between variables and the conditions necessary for a valid schedule.

Termination: Each request \(r_i\) must generate \(O_i\) output tokens, thus

\[\forall i: \sum_{j} g_{i,j} = O_{i}.\]

Per-Request Progress: For the number of total input and generated tokens,

\[\forall i, j: s_{i,j} = s_{i,j-1} + g_{i,j}.\]

Memory Management: The number of KVs stored should be 0 if \(r_i\) is preempted or increase by the number of processed tokens, \(c_{i,j}\).

\[\forall i, j: m_{i,j} = \begin{cases} 0 & \text{if } e_{i,j} = 1 \\ m_{i,j-1} + c_{i,j} & \text{otherwise} \end{cases} \label{eq:mem}\tag{7}\]

Tokens to Process: The number of tokens to process should be 0 if \(r_i\) is preempted or not exceed available tokens to process.

\[\forall i, j: c_{i,j} = \begin{cases} 0 & \text{if } e_{i,j} = 1 \\ \leq s_{i,j-1} - m_{i,j-1} & \text{otherwise} \end{cases} \label{eq:c}\tag{8}\]

Token Generation: The output token can only be generated if all input and generated tokens are processed, for both (chunked) prefill and decode steps.

\[\forall i, j: g_{i,j} = \begin{cases} 1 & \text{if } c_{i,j} = s_{i,j-1} - m_{i,j-1} \\ 0 & \text{otherwise} \end{cases} \label{eq:g}\tag{9}\]

Batch Constraints: Ensures global constraints per batch.

\[\label{eq:global} \begin{align} \forall j: \sum_{i} c_{i,j} \leq C, \sum_{i} m_{i,j} \leq M \end{align}\tag{10}\]

The inequality in Equation (8 ) allows partial processing of the available tokens as in chunked prefill [22]. For implementing the conditional constraints in Equations (7 )-(9 ), we use the Big-M method [84] to linearize them, since linear programs are more efficient than non-linear ones [85]. For example, Equation (7 ) is linearized as: \[\begin{align} m_{i,j} & \leq \text{\boldsymbol{M}} \, (1 - e_{i,j}), \\ m_{i,j} & \leq m_{i,j-1} + c_{i,j} + \text{\boldsymbol{M}} \, e_{i,j}, \\ m_{i,j} & \geq m_{i,j-1} + c_{i,j} - \text{\boldsymbol{M}} \, e_{i,j}, \end{align}\] where is a sufficiently large constant. We implement our CSP using Gurobi⁷.

Objective. The objective can be set to minimize the total latency using our cost models in Section 4.2, summing up all batch times. Since the cost models are monotonic, they prefer a lower number of batches and smaller number of tokens to process and KVs to read per batch. Instead of retrieving the minimum latency, one can simply opt for the existence of a better schedule, for example, by running a scheduler whose latency is \(L\) and adding a constraint that the latency should be less than \(0.9L\) to guarantee 10% improvement. Furthermore, one can optimize latency under throughput constraint, e.g., making TPOT or each batch time less than a predefined threshold.

Online Setting. Supporting the online setting, where each request \(r_i\) has an arrival time \(T_i\), is straightforward: add a variable \(Acc_{j}\) to track accumulated batch times and set \(s_{i,j} = m_{i,j} = 0\) if \(Acc_{j} < T_{i}\) to indicate that there is no token to process or processed before \(T_{i}\).

Challenge. A primary challenge in CSP is its limited scalability, as it is generally NP-complete [86]. The complexity grows with the number of requests and batches, reaching millions of variables for thousands of requests and batches. Consequently, we primarily use CSP on small workloads that are enough to explain the phenomena found in the analysis and initialize the variables with outputs from other schedulers, rather than using all-zero or random values. We leave optimizing CSP for larger scales as a future work with possibly approximation approaches [87], [88].

7.2 Can Preemption Be Optimal?↩︎

As noted in Section 5.6, preemption can enhance system performance. We use our CSP first as a proof-by-example approach. We use four requests, set their output size \(O\) to 4, and vary their input size \(I\) from 1 to 1024, with the KV cache size \(M\) of \(max(2I, I+O-1)\). This allows schedules to initiate prefills for two requests (\(2I\)) while ensuring that only one request can retain its KVs to generate the final token (\(I+O-1 \leq M < 2(I+O-1)\)). The objective is to minimize latency.

Interestingly, the CSP also opts to preempt requests. For small input sizes (\(I \leq 32\)), CSP chooses to preempt short requests as illustrated in Figure 16 (a), since it is faster to complete short prefills, making a progress of a token generation, and decreasing the number of batches by one, rather than waiting for another batch to retain memory. Each batch has an inevitable cost of loading model weights. This approach can reduce latency by up to 17% compared to preemption-free schedules as \(I\) decreases. However, for large input sizes (\(I \geq 64\)), CSP avoids preemption, as the later refill cost increases with the input size. Here, avoiding preemption can reduce latency by up to 40% as \(I\) increases. Among the schedulers, vLLM and its preemption-free variant exhibit latency results close to the CSP’s results, for \(I \leq 32\) and \(I \geq 64\), respectively.

Remark. While it is counterintuitive that preemption improves performance, we prove that it is true and find a relationship between sequence length and performance improvement by preemption. Preempting short requests can help, but preempting long requests degrades performance due to high refill costs. Furthermore, Figure 16 shows that the cache is underutilized as in Figure 12, leaving an additional room for improvement.

7.3 When Can Preemption Be Optimal?↩︎

Due to the limited scalability of CSP, it is nearly infeasible to list all cases when preemption is optimal. This section takes the insight from Section 7.2 and solely focuses on it, that when preempting and reprocessing requests later can reduce the number of batches, leading to reduced latencies.

We consider (1) processing \(x\) tokens of a prefill request to generate an output token, (2) preempting the request, and (3) later refilling it. We can compute the increased overhead in this preemptive schedule compared to the corresponding non-preemptive schedule that does not process this request until there is enough space in the cache. First, for both schedules, (1) is an inevitable cost in processing the request. (2) adds no overhead to the preemptive schedule. (3) adds an overhead of processing \(x+1\) tokens. Therefore, the increased cost is \(F_{p}(x+1)\) where \(F_p\) is the cost function for a prefill request in Section 4.2.

Note that (3) also produces an output token, reducing one decode step for this request. Hence, we need to compute the saved cost from reducing one decode batch. This decode step in the non-preemptive schedule reads \(x\) KVs from the memory and processes one token. The cost of this decode step is \(F_d(x)\) where \(F_d\) is the cost function for a decode request.

By comparing the two costs – increased and saved – in preemptive schedule, we can compute the range of \(x\) that makes the preemptive one more efficient than the non-preemptive counterpart. This is equivalent to computing the range of \(x\) such that \(F_p(x+1) < F_d(x)\). This range is \(x < 47\) for the setup in Section 7.2, consistent with the results that preempting a request with input size \(I = 32\) leads to a better efficiency.

7.4 Which Requests to Preempt?↩︎

The previous section focused on processing and preempting the same request, identifying when it is helpful to preempt a request. This section targets which requests to preempt if we have multiple candidates.

Based on the insight that preempting short requests can be helpful, we generalize this to prioritizing the preemption of short requests, while existing LLM inference systems simply preempt newest requests first, as shown in Table ¿tbl:tab:llm-taxonomy?. Here, we prove that our shortest-request first (SRF) policy is more efficient than their newest-request first (NRF) policy. SRF prioritizes running long requests (having large number of KVs in the KV cache) and preempts short requests if the KV cache reaches its limit.

To determine which schedule is more efficient, we further abstract the cost-based analysis in Section 7.3 and introduce a concept called batch-wise progress, which we define as the number of tokens generated over the batch execution time. Since the batch time monotonically increases with the number of tokens (Section 4.2), we can simplify the progress as the number of tokens generated over the number of tokens to process. Further, as the number of total tokens to generate is fixed across the schedules, maximizing the progress improves the efficiency of a schedule. If we preempt a request with \(m\) KVs in the cache and \(1\) output token generated but not processed, the progress of this request in the batch that refills this request, is \(\frac{1}{m+1}\), from reprocessing \(m\) KVs and \(1\) last output token, and generating a new output token. Therefore, preempting a short request with small \(m\) increases the progress, proving that the progress of using SRF is higher than using NRF. For the example in Figure 17, NRF’s progress for refilling the newest request \(r_4\) is \(\frac{1}{9+1}\), while SRF’s progress for refilling \(r_1\), \(r_2\), and \(r_3\) are \(\frac{1}{5+1}\), \(\frac{1}{2+1}\), and \(\frac{1}{4+1}\).

8 Evaluation of SRF in Actual Inference Systems↩︎

This section evaluates our shortest-request first (SRF) preemption and cache replacement policy in Section 7.4 on actual inference systems and online workloads. From Table ¿tbl:tab:llm-taxonomy?, we choose three systems, vLLM for the main system, SGLang for prefix-sharing scenarios, and Dynamo for disaggregation and KV offloading to DRAM. The first two are popular and open-sourced, implement all stacks in Figure 2, and often used as backends of other systems, including the last one.

SRF is easy to implement in inference systems with just a few lines of code (order requests by the number of KVs in the cache) without any fine-tuning or training an ML model, not even our cost models (but still being cost-aware considering the progress defined).

At the point of cache insertion, we further maintain an optional, online histogram to estimate the output lengths of requests given their input lengths, predict if any preemption would occur for long-output requests, and defer scheduling those requests to later batches. We call this SRF+Hist.

Table ¿tbl:table:deploy95workloads? shows the workloads we used. AzureConv[78] is an 1-hour online trace of conversations, LongForm[89] is a long-form text generation dataset to generate human-like texts, and SelfConsistency[90] is a prefix-sharing workload where each prompt generates multiple answers. Reason2 and Chat15 are production traces provided from Alibaba [91].

Since the request lengths exceed the context size of Llama-2-7B, here we use Llama-3-8B and Llama-3-70B with the context size of 128K and set the KV cache size to 100K as before. This also shows the generalizability of our methodologies to other models.

8.1 Evaluation in vLLM↩︎

This section presents the results on vLLM, the main system we have used from Section 3 and compared with the simulation results in Section 5. SRF and SRF+Hist each required 6 and 24 lines of Python code to implement. Figure 18 shows the results for vLLM, using Llama-3-8B on 1 A100. We also use the output length \(O\) scale of 2x and KV cache size \(M\) scale of 1/2x to evaluate on longer-generation and higher-contention scenarios. The results for Sim shows that our simulation is accurate enough (up to 2% difference). Compared to NRF, SRF and SRF+Hist improve performance by up to 8% and 15% without performance regression. Note that these numbers are critical, indicating substantial savings in GPU hours and operational costs for high-demanding LLM inferences as mentioned in Section 1. For our offline simulation workloads in Section 5, SRF improves performance by up to 40% without regression due to higher arrival rates (all requests arrive at time zero) and higher contentions.

The last two policies in Figure 18 represent performance upper bounds, each for enhanced memory capacity and bandwidth utilization. While an infinite KV cache would save the latency up to 40%, maximum bandwidth utilization would save up to 55%. Furthermore, note that for AzureConv, both NRF and SRF have similar latencies to the performance bounds, which is due to the low arrival rate that requests are processed without much contention. This highlights that simulation-based analysis allows identifying the workloads to optimize further or not, without spending extensive GPU hours.

While increasing memory capacity and request concurrency reduces latency, it incurs an undesirable side effect. Figure 19 shows the schedules on LongForm, where for Infinite M, batching a large number of requests together leads to heavy batches as seen in Section 5 and large request completion times. The figure also shows that SRF preserves fairness as in NRF, completing early-arrived requests first. This is because, SRF is a preemption and cache replacement policy, where we still launch earliest requests first.

Figure 20 shows the results for Llama-3-70B on 4 A100. Both SRF and SRF+Hist improve performance by up to 13% without regression. For Infinite M and Theoretical, increasing the memory capacity results in a larger performance improvement than increasing the bandwidth utilization, which is an opposite result from Figure 18. This is due to the higher batch latencies that increase the contention level, where the arrived requests are not processed as promptly as in the 8B model, making the KV cache as the critical bottleneck.

When we switched from A100 to H100, the contentions were largely resolved for the 8B model due to larger memory bandwidths, where SRF showed similar performance with NRF. For the 70B model, due to a higher contention level, SRF and SRF+Hist improved performance by up to 6% and 11%, and again, without performance regression. We omit the figures due to space limitations.

Remark. SRF is easily deployable to an actual inference system and shows better performance than NRF without regression or losing fairness. As shown in Section 5, GPU bandwidth is a primary factor affecting performance, and increasing it can reduce batch times. Under high contention due to large batch times, the capacity also matters.

8.2 Evaluation in SGLang↩︎

We compared NRF vs. SRF in SGLang, a popular system optimized for prefix-sharing scenarios. SRF and SRF+Hist each required 7 and 27 lines of Python code to implement. We used the SelfConsistency workload in Table ¿tbl:table:deploy95workloads? with prefix-shared requests. SGLang maintains a prefix tree of requests and preempts non-prefixes (leaf nodes in the tree, owned by a single request) first. If a non-prefix (and the owning request) is preempted, its parent node may become a new non-prefix which can be preempted. SRF sorts non-prefixes w.r.t. their lengths and preempts the shortest ones first.

SRF reduced the latency by 12% and 16% compared to NRF for Llama-3-8B on A100 and H100, and by 14% and 17% for Llama-3-70B on 4 A100 and 4 H100, respectively. SRF+Hist showed similar performance with SRF, and again, without performance regression compared to NRF.

Remark. SRF is easily deployable to prefix-sharing scenarios and improves performance there. The larger performance gain of SRF compared to Section 8.1 is mainly due to the increased request output sizes of the workload that lead to higher contentions.

8.3 Evaluation in Dynamo↩︎

We also deployed our SRF to Dynamo under the prefill-decode disaggregation setup, using Llama-3-8B on two prefill and two decode A100. SRF preempts requests in the decode side, and again, required less than 10 lines to implement. We also enabled KV offloading to DRAM using LMCache[57].

We used two production traces, Reason2 and Chat15 from Table ¿tbl:table:deploy95workloads?, where the numbers indicate request-per-second. SRF improved performance by 7% and 20%, respectively.

Remark. SRF improves performance in a production-scale, disaggregated system without modifying other stacks (e.g., request scheduling, disaggregation, or offloading policy). Only a few lines in the preemption rule are changed, demonstrating the same lightweight integration and practical benefits highlighted from Section 8.1.

9 Conclusion↩︎

In this work, we show how we can save GPU hours spent in both pre-deployment (development and analyis) and post-deployment (online inference serving) phases in LLM inference systems. We show that cost-based simulations are effective enough to provide meaningful insights and theoretical analyses, including that harnessing request preemptions can save GPU hours. We translate these into an effective preemption and cache replacement policy that can be easily deployed to actual systems and substantially save GPU hours for online workloads, which we expect greater benefits from longer-output requests with even higher contentions. Considering the significant amount of inference usage, and as we target general inference workloads not specific to data analytics, we believe our work has a large impact to the community. We note that our work was inspired by the cost models, simple yet effective buffer management policies such as LRU, and the five-minute rule in DBMSs, and provides interesting connections between the database and LLM worlds.

References↩︎