Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving

Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving Muhammad Adnan† ∗ Rohan Mahapatra‡ Prashant Nair† Daniel Berger‡ Pantea Zardoshti⋄ Rodrigo Fonseca‡ Esha Choukse‡

arXiv:2608.06557v1 [cs.DC] 6 Aug 2026

†

The University of British Columbia

‡

Microsoft Azure Research

Abstract—The reasoning and agentic capabilities of large language models have expanded the range of applications they support, from short interactive exchanges to long, computeheavy requests. LLM serving platforms today define responselatency service-level objectives, even though requests within the same service can differ by orders of magnitude in input length, generation length, execution cost, and the availability of reusable KV-cache state. As a result, requests governed by the same service level objective have different urgency: after accounting for the time required to execute them, some have substantial latency headroom while others have almost none. We define this headroom—the difference between a request’s service level objective and its predicted remaining service time—as its perrequest latency budget. We present C ASCADE, an LLM serving system that estimates and continuously updates this budget from request characteristics, KV-cache state, and current system load. Unlike prior SLOaware schedulers that use deadlines to govern request ordering alone, C ASCADE uses a single per-request budget to jointly coordinate request scheduling and KV-cache management across the memory hierarchy. Its scheduler prioritizes requests with little remaining budget, while its memory manager uses the same budget to decide whether non-resident KV state should be restored or prefetched from a deeper tier, retained in HBM, or recomputed. By directing queueing and data-movement overhead toward requests that can absorb it, C ASCADE improves SLOsatisfied goodput while preserving fairness across heterogeneous request classes. On production traces across three large language models, C ASCADE improves goodput by up to 2.4× and reduces SLO violations by 40% relative to the default vLLM first-come, first-served scheduler.

I. I NTRODUCTION Production LLM serving increasingly multiplexes heterogeneous applications [8], [14] over shared model deployments. A single cluster may concurrently serve interactive chat, coding assistants, search, tool-using agents, and multi-step reasoning workloads. While consolidating these services can help improve the utilization of expensive accelerators, it also places requests with widely different execution demands on the same hardware. Thus, providers need to balance two goals; they must satisfy the latency service level objective (SLO) of each service while keeping shared accelerators efficiently utilized. Although the SLO is defined at the service level, the work required to serve a request is inherently request-specific. Requests within the same service can differ substantially in prompt length, generation length, and model execution time. ∗ Work done while interning at Microsoft Azure Research.

⋄

NVIDIA

Fig. 1: Goodput and fairness trade-offs across scheduling policies. We compare normalized goodput relative to FCFS with cross-class fairness, measured using Jain’s Fairness Index over input-length classes [17], under a mixed production trace [36]. C ASCADE improves SLO-satisfied goodput while preserving fairness across request sizes.

Their cost also depends on runtime state. For instance, a request may reuse the Key-Value (KV) state already resident in high-bandwidth memory (HBM), retrieve it from CPU DRAM or NVMe, or recompute the corresponding prefix. Moreover, output length is unknown when a request arrives, and reasoning or agentic requests may generate substantially more work than their inputs suggest. Thus, requests governed by the same service-level SLO can have very different execution costs and, therefore, very different urgency. Model execution is also only one component of response latency. A request may wait in an admission queue, contend with active prefill and decode operations, and stall while reusable KV state is restored into HBM. Existing systems [14], [26] address these delays through largely independent mechanisms. vLLM [20], for example, combines continuous batching and chunked prefill [3], [40] with first-come, first-served (FCFS) scheduling. FCFS preserves arrival order, but allows expensive requests to create severe head-of-line blocking. Shortest-job-first (SJF) scheduling reduces such blocking by advancing shorter requests, but can systematically deprioritize long-context code and reasoning workloads. Earliest-deadlinefirst (EDF) [24] scheduling incorporates service deadlines, but cannot distinguish requests that share a deadline while requiring substantially different amounts of remaining work.

KV-cache management is typically handled separately from request scheduling. Prefix-caching systems extend effective KV capacity by retaining reusable state across requests and spilling it from HBM into deeper memory tiers [25], [31], [43]. These systems commonly decide what to retain, evict, or restore based on cache capacity, reuse probability, and transfer cost. Such criteria indicate whether a cached object is beneficial in aggregate, but not whether the request that reuses it can tolerate the resulting delay. A deep-tier KV-cache hit may therefore avoid expensive prefill computation while still causing an SLO violation because restoring the state takes longer than the request can afford. We observe that scheduling and KV-cache management consume a common resource. The difference between a request’s SLO and its predicted remaining service time is a per-request latency budget. Queueing, contention, preemption, and KV-cache movement all spend from this same budget. Because requests are heterogeneous, the same absolute delay may consume only a small fraction of one request’s budget while causing another request to violate its SLO. A serving system can therefore reduce violations not only by decreasing total overhead, but also by directing unavoidable overhead toward requests with budget to spare and protecting requests that can tolerate little additional delay. Our work. We present C ASCADE, an LLM serving system that makes the per-request latency budget an explicit runtime quantity to coordinate request scheduling with KV-cache management. C ASCADE predicts each request’s remaining service time using its input length, predicted output length, available prefix KV state, and current system load. It then derives the request’s remaining budget from its service-level SLO and continuously updates the estimate as the request waits, executes, and encounters changes in system and cache state. C ASCADE’s scheduler prioritizes requests based on their remaining budget rather than by arrival order, deadline, or input size. Requests with little remaining budget advance ahead of requests that can safely tolerate added delays. This reduces head-of-line blocking without assuming that shorter requests are always more urgent and, unlike size-based scheduling, does not systematically deprioritize long-context requests. The same budget governs KV-cache decisions across HBM, DRAM, and NVMe. When reusable KV state is not resident in HBM, C ASCADE compares the cost of restoring the state with both the request’s remaining budget and the cost of recomputation. It restores, or prefetches state from a deeper tier only when the request can absorb the transfer delay; otherwise, it recomputes the corresponding prefix. The budget also informs which KV state should be retained or placed in deeper tiers. Because scheduling and KV movement draw on the same budget, C ASCADE prevents either subsystem from consuming latency headroom required by the other. We implement C ASCADE using the vLLM [20] serving engine and extend Vidur [2] to model cluster-scale scheduling and multi-tier KV movement using profiles collected on NVIDIA GB200 NVL72 hardware. We evaluate production traces containing ChatBot, Tool&Agent, Coder, and Reason-

Chat Code

Global Scheduler

Agent Calls

Users

Agents Fairness

Goodput

SLO

…. Serving Instances in a Cluster

Fig. 2: Workload heterogeneity in multi-instance LLM clusters. Interactive chat, agentic tool calls, code generation, and multi-step reasoning issue requests with widely varying execution demands under service-specific latency SLOs.

ing requests [36] across Qwen-2.5-72B, Llama-3-70B, and Llama-3-405B. As Figure 1 shows, C ASCADE improves SLOsatisfied throughput (goodput) while maintaining high fairness across request classes. Overall, our evaluations show that C ASCADE improves goodput by up to 2.4× and reduces SLO violations by 40% relative to the default vLLM FCFS scheduler. Summary. This paper makes the following contributions: • We identify the per-request latency budget as the common resource consumed by request scheduling and KV-cache movement. We show why service deadlines, request size, and cache state alone do not capture how much additional serving overhead a request can tolerate. • We present C ASCADE , an LLM serving system that maintains and updates a per-request latency budget and uses it to coordinate request ordering with KV restoration, prefetching, placement, and recomputation across the memory hierarchy. • We design a budget-based scheduler that reduces head-ofline blocking while preserving fairness across heterogeneous request sizes, without systematically starving longcontext requests. • We evaluate C ASCADE on production traces across three LLMs and show that it improves goodput by up to 2.4× and reduces SLO violations by 40% relative to vLLM’s default FCFS scheduler. II. BACKGROUND A. LLM Inference Large Language Model (LLM) inference executes in two asymmetric phases that govern system-level bottlenecks: Prefill Phase is when the model processes the entire input prompt in a single parallel pass to generate the initial Key-Value (KV) cache. This phase is highly compute-intensive, dominated by dense matrix multiplications. Decode Phase is when the model auto-regressively generates output tokens one-by-one, appending each new token’s keys and values to the active KV cache. This sequential, token-by-token execution is heavily memory-bandwidth bound.

Replica Scheduler Replica ServingScheduler Engine

Tool& Agent

ChatBot

Users

queries

Global Scheduler

Code

GPU 1

GPU 2

GPU 3

HBM

HBM

HBM

NVLink C2C

CPU 1

GPU 4

GPU 1 GPU 1

GPU 2

GPU 3

HBM

HBM HBM

HBM

HBM

NVLink C2C

GDS

DRAM

Reasoning

Replica Scheduler Replica ServingScheduler Engine

NVMe

NVLink C2C

CPU 2

CPU 1

DRAM

DRAM

GPU 4

HBM NVLink C2C

GDS

CPU 2

DRAM NVMe

Fig. 3: System view of LLM Serving system. User requests encompassing multiple tasks are routed to an instance within the cluster via the global scheduler. Each instance processes the requests through the serving engine. All serving instances’ GPUs can communicate with each other through 1 multi-node NVLink (MNNVL). Each GPU can communicate with respective CPU DRAM through 2 NVLink-C2C while SSD can be reached via 3 GPU-Direct Storage protocol via PCIe Gen5.

a) Service Level Objectives (SLO): Service providers define phase-specific Service Level Objectives (SLOs) to maintain user interactivity across distinct execution phases. The prefill phase is governed by Time to First Token (TTFT)—the latency between request arrival and first token generation—while the decode phase is bounded by Time Per Output Token (TPOT), the latency between successive tokens. In multi-tenant datacenters, these SLOs must be met across heterogeneous workloads with highly varied context and generation lengths, including short-context API calls, multi-turn ChatBot conversations, long-context Code generation, and deep Reasoning tasks. Consequently, the primary objective of datacenter-scale LLM serving is to maximize goodput – defined as the volume of request throughput that strictly adheres to these interactive TTFT and TPOT SLO thresholds. b) Prefix Caching: Beyond intra-request reuse, prefix caching enables KV cache sharing across distinct requests that share common token sequences. For instance, these could be system prompts, Retrieval-Augmented Generation (RAG) context, or shared code repositories. In multi-turn interactive conversations, prefix caching avoids redundant context computation by storing the concatenated inputs and outputs of previous turns in deeper memory tiers for subsequent requests [25]. By serving shared prefixes directly from memory rather than recomputing them, this technique shifts the bottleneck of identical context segments from compute-intensive prefill to memory retrieval. This helps to substantially reduce TTFT and increase overall serving throughput. B. Datacenter-Scale Serving As shown in Figure 3, datacenter-scale serving systems deploy multiple model instances to handle diverse user workloads. A centralized Global Scheduler routes incoming queries

to specific instances based on real-time load balancing and localized HBM prefix cache affinity. a) Prefill-Decode Co-location: Throughout this paper, we focus on co-located LLM serving, where prefill and decode execution share the same serving instances. Although prefill-decode (PD) disaggregation has recently emerged to isolate resource contention across specialized instances [16], [29], [44], PD co-location remains an important deployment paradigm in production environments [39]. Co-located architectures eliminate complex instance-role management, and avoid the high network transfer overheads of migrating KV caches across physical nodes [21], [22]. Our findings and policies are generally orthogonal to the choice of co-location and the disaggregation of prefill and decode. b) Serving Engine and Instance: An instance is the minimum hardware unit that serves requests and host one complete copy of the LLM’s parameters, potentially spanning multiple GPUs to accomodate model parameters on GPU HBM and serving engines mostly used engines like vLLM [20] and SGLang [43] once an incoming request is pushed into the queue of the instance, queued request is batch and executed efficiently on the same instance utilizing chunked prefills [3]. By partitioning resource-intensive prefill requests into equalsized chunks, the engine co-schedules prefill chunks alongside active decode steps without inducing execution pauses. This approach eliminates scheduling bubbles, balancing the tradeoff between serving latency and system throughput. c) Multi-Tier KV Cache Memory Hierarchy: To satisfy stringent latency SLOs, traditional prefix KV reuse mechanisms [12], [34], [43] have primarily relied on local GPU HBM and host CPU DRAM. However, emerging long-context workloads [15], such as RAG and multi-step coding agents, rapidly exceed local memory capacity, driving the adoption of

Fig. 4: Impact of deep-tier KV retrieval on TTFT for a 64k context synthetic request (Qwen-2.5-72B). Fetching prefix state from NVMe reduces prefill compute but introduces high transfer latency, turning naive deep-tier hits into TTFT SLO violations.

global, multi-tier KV memory pools [41] that extend across NVMe storage and disaggregated network memory [25], [31]. Modern AI cluster architectures facilitate this transition by incorporating ultra-high-bandwidth intra- and inter-node interconnects to accelerate cross-tier state movement. For instance, rack-scale architectures like NVIDIA’s GB200/GB300 NVL72 [28] feature Multi-Node NVLink (MNNVL) [27] across all 18 compute nodes alongside NVLink-C2C for direct host-to-device memory access. Figure 3 illustrates a multiinstance LLM serving system leveraging this deep memory hierarchy, pooled KV storage, and high-bandwidth interconnect fabric. III. M OTIVATION A request’s SLO must cover not only model execution but also the queueing, batching, and KV cache retrieval that serving adds on top of it. The room an SLO leaves for this overhead is the request’s latency budget. Current serving systems do not track this budget: they let queueing consume it, spend it on KV cache transfers that exceed it, and report aggregate SLO attainment that hides which requests run out of it. In this section, we characterize and examine each of these effects in turn. A. Structural Fairness in Multi-Class Request Scheduling While policies such as Shortest Job First (SJF) minimize total SLO violations by prioritizing short-context queries, they introduce severe starvation for long-context requests (refer Figure 12). A single cluster-wide SLO number hides this bias, because the many short requests that succeed outweigh the long-context requests that fail, such as coding agents and multi-turn reasoning. Therefore, a robust scheduler must maintain cross-class fairness, ensuring equitable service quality across all context lengths. To quantify cross-class fairness, we employ Jain’s Fairness Index (JFI) [17] over request context length bins. Specifically, we partition incoming traffic into six input sequence length percentile ranges: p0 –p50 , p50 –p75 , p75 –p90 , p90 –p95 , p95 –p99 , and p99+ . Let N denote the set of percentile bins (n = |N |).

Fig. 5: Impact of Head-of-Line (HOL) blocking under FCFS scheduling for mixed trace with same distribution of all workloads. FCFS queuing introduces severe HOL blocking delays for arriving requests, rapidly consuming their latency headroom. In contrast, evaluating requests without HOL delay reveals substantial intrinsic budget that can be exploited for SLO-compliant KV prefetching and request scheduling. For each bin i ∈ N , we define its SLO attainment rate as Ai = max(0, 100−Vi ), where Vi represents the SLO violation rate of class i. The overall fairness index J is formulated as: Pn 2 ( i=1 Ai ) (1) J = Pn n i=1 A2i The index spans J ∈ [ n1 , 1.0], where J = 1.0 represents ideal fairness (identical SLO attainment across all context length bins), whereas J = n1 indicates maximum unfairness, where a single bin monopolizes all successful completions while others suffer total non-compliance. Takeaway 1. A high overall SLO attainment can still hide starved request classes. A scheduler can meet its SLO for most requests while failing nearly all long-context requests, because short requests dominate the count. Measuring SLO attainment separately for each prompt-length range exposes this gap, which a single cluster-wide number conceals. B. The Deep-Tier KV Fetch Dilemma While extending prefix KV caching to deep memory tiers (e.g., NVMe drives and disaggregated storage) expands cache capacity for long-context workloads, it introduces a fundamental tension between prefill compute savings and state restoration latency. Figure 4 shows this tension for a 64ktoken prefix on Qwen-2.5-72B. Reusing the prefix from a highspeed tier (HBM or DRAM) reduces GPU prefill compute by up to 75% with negligible transfer cost, which leaves most of the TTFT SLO unspent. Retrieving the same prefix from NVMe, however, adds transfer delay along the NVMe to CPU DRAM to GPU path that exceeds the TTFT SLO, even with LMCache batched prefetching [25], an effect also reported in prior work [32]. A runtime that admits every deep-tier hit therefore converts some cache hits into SLO violations. Takeaway 2. Deep-tier prefix caching requires budget-aware restore admission. To safely harness disaggregated KV memory pools, serving schedulers must dynamically assess whether

a request’s remaining latency budget can absorb transfer delays, falling back to GPU prefill recomputation whenever transfer overhead threatens SLO compliance. C. Reclaiming Intrinsic Request Latency Budget Conventional LLM serving schedulers rely on First-ComeFirst-Served (FCFS) or size-agnostic queuing, subjecting arriving requests to severe Head-of-Line (HOL) blocking delays. As shown in Figure 5 (left), FCFS queuing introduces massive delays—frequently exceeding tens of seconds—that rapidly exhaust a request’s Service Level Objective (SLO) headroom before GPU execution even commences. However, evaluating these requests in isolation reveals a crucial opportunity: requests inherently possess substantial latency budget, defined as the margin between a request’s target Time-To-First-Token (TTFT) SLO and its intrinsic GPU prefill execution time (Budget = TTFTSLO − Tprefill ). As shown in Figure 5 (right), unblocked requests across Qwen-2.5-72B, Llama-3-70B, and Llama-3-405B exhibit intrinsic latency budget ranging from 2 seconds to over 20 seconds. Rather than allowing HOL queuing to squander this budget, an efficient serving runtime should explicitly model and exploit per-request latency budget – reordering execution queues and orchestrating deep-tier KV state transfers without violating downstream SLO contracts. Takeaway 3. SLO violations stem from HOL blocking, not a lack of intrinsic budget. Requests across model scales possess multi-second latency budget (TTFTSLO − Tprefill ) that legacy FCFS schedulers waste in queues; available budget-aware scheduling reclaims this headroom to coordinate request dispatching and deep-tier KV cache management. IV. C ASCADE : D EADLINE D RIVEN LLM S ERVING State-of-the-art LLM serving schedulers rely on rigid, static policies that fail to adapt to dynamic workload fluctuations and system overload. When cluster utilization spikes, legacy schedulers either selectively favor short requests at the expense of long-context workloads or induce severe Head-ofLine (HOL) blocking—driving up queuing delays and triggering widespread Time-To-First-Token (TTFT) SLO violations. Simultaneously, naive prefix KV cache retrieval introduces exposed transfer overheads that stall prefill execution and delay co-located decode batches, degrading Time-Per-OutputToken (TPOT). Under GPU HBM exhaustion, standard tailpreemption heuristics further compound latency by indiscriminately evicting recently scheduled requests. Resolving these intertwined bottlenecks requires a requestaware serving system that holistically coordinates request dispatch, state movement, and context preemption. Based on these observations, we introduce C ASCADE, an adaptive LLM serving system centered around per-request latency budgets. C ASCADE defines a request’s latency budget as the difference between its overall SLO target and its intrinsic execution time, safely co-allocating this budget across queuing delays, prefix KV transfers, and preemption decisions to preserve strict SLA compliance while maximizing cluster goodput.

Scheduling Queue - Tier 1 (Positive Budget)

SLOs

requests

TTFT Estimator Prefix KV Hit HBM: 4k DRAM: 1k NVMe: 20k

Actual Load

Latency Budget Scheduled during idle time

Reorder

Scheduling Queue - Tier 2 (Negative Budget)

Remaining Budget KV Memory Pool

Serving Instance

Prefix KV Hit HBM: 4k DRAM: 1k NVMe: 5k

Prefetch KV

Fig. 6: Overview of Cascade.

Figure 6 shows the overall architecture of the C ASCADE LLM serving system. Upon arrival at a serving node, an incoming request is evaluated by the 1 TTFT Estimator, which models prefill latency using active queue state and multi-tier prefix KV hit information. The 2 Latency Budget Engine then computes the request’s budget as the margin between its class SLO and predicted TTFT. Requests possessing positive budgets join the Tier-1 scheduling queue. Requests yielding negative budgets are demoted to a Tier-2 queue rather than being dropped outright. To prevent Tier-2 starvation under sustained overload, C ASCADE reserves a fixed fraction of each batch for Tier-2 requests and re-estimates their budget as load falls, promoting a request back to Tier-1 once its budget turns positive. Across chunked iteration cycles ( 3 , 4 ), C ASCADE continuously updates remaining request budgets, prioritizing requests with the tightest remaining budget while prefetching required prefix KV states within their budget bounds. Below, we formalize the serving problem before detailing each system component. A. Problem Formulation We consider an LLM serving cluster servicing heterogeneous workloads categorized into a set of request classes C (e.g., interactive chat, agentic tool use, code generation, and complex reasoning). Each class c ∈ C is bound by a class-level ), Service-Level Objective target Sc = (TTFTtarget , TPOTtarget c c defining strict thresholds for Time-To-First-Token (TTFT) and Time-Per-Output-Token (TPOT). We deliberately define SLO targets at the workload class level rather than per individual request, as intra-class variance in prompt and generation lengths renders request-specific targets noisy and impractical to enforce online. To support large-scale prefix KV reuse, the system aggregates cluster memory into a disaggregated hierarchy denoted by tiers K = {0, 1, 2}, corresponding to GPU HBM (0, execution tier), host CPU DRAM (1, warm capacity tier), and local/networked NVMe storage (2, deep capacity tier). State movement and placement operate on discrete KV blocks b of size mb bytes, where each block belongs to a request class c(b) ∈ C. Retrieving a block b from tier k ∈ {1, 2} into GPU

execution memory introduces a transfer latency δk→0 (mb ) governed by interconnect bandwidth constraints. a) Optimization Objective: Given active request set R, our goal is to co-design the request scheduling policy σ (dispatch order and batching) alongside the prefix retrieval policy ϕ (tier restoration decisions). We formulate this as a multi-objective optimization problem to maximize overall cluster goodput while enforcing both TTFT and TPOT SLO compliance: max σ,ϕ

s.t.

 X  TTFT TPOT I TTFTr ≤ Sc(r) ∧ TPOTr ≤ Sc(r) r∈R

X

mb ≤ MGPU ,

∀t,

(2)

Fig. 7: Validation of estimated latency (Lr ) against actual execution TTFT (Tprefill ) on Qwen-2.5-72B. Performance is evaluated across the Mixed trace using Mean Absolute Error (MAE) and Pearson correlation (R).

b∈HBM

BWk→0 (t) ≤ Bk ,

∀k ∈ {1, 2}

where I(·) is an indicator function evaluating to 1 when both latency objectives are met, and MGPU and Bk represent the physical memory capacity and interconnect transfer bandwidth bounds, respectively. B. TTFT Latency Estimator and Latency Budget To accurately compute available request budgets, C ASCADE incorporates a TTFT Latency Estimator that projects prefill latency based on a request’s context length, prefix KV cache hit profile across the memory pool, and the serving instance’s active load (specifically, active decode-phase requests). Using runtime system state, an offline-trained predictive model—calibrated via execution profiling and simulation frameworks such as Vidur [2]—evaluates prefill execution recomp : zero queue under four operational regimes: (1) Lzero r recomp load with full GPU recomputation; (2) Lact : actual r : actual instance load with full GPU recomputation; (3) Lactual r instance load with tier-aware prefix KV hit reuse; and (4) Lmax r : maximum instance load (Bmax −1 concurrent decode requests) with prefix reuse. The budget is only as reliable as this estimate: an optimistic Lr inflates the budget and lets the request accept queuing and transfer delay it cannot actually afford, causing an SLO violation. C ASCADE therefore estimates conservatively, computing an effective latency Lr by averaging the predicted latencies under actual load (Lactual ) and maximum capacity r (Lmax ), scaled by an empirical guardband factor γ ≥ 1.0: r
1 actual Lr = Lr + Lmax ·γ r 2

(3)

Here, γ absorbs latency estimation errors, memory bus contention, and queuing variance that occur between request arrival and batch execution. We set γ to a single value per model, fixed offline from profiling and held constant across all traces and load levels. The budget defined here bounds TTFT; C ASCADE preserves TPOT through chunked prefill, which caps the prefill work admitted per iteration so that budgetdriven dispatch and prefetching do not stall the decode steps of co-located requests.

Figure 7 illustrates the prediction fidelity of our estimator, reporting Mean Absolute Error (MAE) and correlation (R) across individual requests in the Mixed production trace on Qwen-2.5-72B across the four operational regimes. Once the estimated TTFT Lr is determined, C ASCADE derives the request’s latency budget Br relative to its target Service Level TTFT Objective (Sc(r) ): TTFT Br = Sc(r) − Lr ,

r∈R

(4)

This budget Br is attached to the request as metadata and governs its admission into C ASCADE’s dual-tier queuing framework. Requests yielding a positive budget (Br > 0) are admitted to the primary Tier-1 queue for priority dispatching. Conversely, requests yielding a negative budget (Br ≤ 0) indicate an imminent SLO violation under current cluster load. Rather than dropping or rejecting these requests outright, C ASCADE routes them to a secondary Tier-2 queue, where they are executed opportunistically on a best-effort basis during cluster idle periods. C. Dynamic Budget Tracking and Feasible Prefix Restoration At each chunked iteration of the scheduler, C ASCADE dynamically updates the remaining latency budget Brrem for every request r in scheduling queues (Tier-1 and Tier-2) based on its initial allocated budget Br , arrival timestamp ar , and the current system time tcurr : Brrem = Br − (tcurr − ar )

(5)

This remaining budget Brrem serves as the dynamic prioritization variable for the primary (Tier-1) execution queue, where requests are dispatched in ascending order of remaining headroom (least-remaining-budget-first). Because each request’s budget already subtracts its own execution time Lr , ordering by remaining budget does not systematically deprioritize longcontext requests: a long request with a loose class SLO retains positive budget and is not starved the way shortest-job-first would starve it. Simultaneously, C ASCADE’s asynchronous prefix prefetcher evaluates prefix KV cache availability across the multi-tier memory hierarchy to determine budget-feasible state transfers.

Let P (k) denote the multi-hop transfer path from memory tier k ∈ {1, 2} to GPU HBM (tier 0)—for instance, P (1) = {DRAM → HBM} and P (2) = {NVMe → DRAM, DRAM → HBM}. For each interconnect link ℓ ∈ P (k), let Bℓeff denote its effective operational bandwidth under load and δℓ represent its fixed per-transfer overhead. The total time Tk (x) required to restore x bytes of prefix KV state from tier k to HBM is modeled as: X X 1 Tk (x) = δℓ + x (6) Bℓeff ℓ∈P (k)

ℓ∈P (k)

This conservative upper bound charges each link along the path, ensuring that transfer delays are not underestimated. A deep-tier prefix restore from tier k is deemed SLOfeasible for request r only if its total transfer time Tk (x) fits within the request’s remaining budget Brrem . By inverting Equation 6, we derive the maximum volume of prefix KV state Mr,k (in bytes) that can be safely fetched from tier k without violating the request’s SLO: h i+ P Brrem − ℓ∈P (k) δℓ P (7) Mr,k = eff ℓ∈P (k) 1/Bℓ Equation 7 establishes a strict admission bound on deep-tier prefix hits: C ASCADE restores prefix blocks up to Mr,k bytes, falling back to GPU prefill recomputation for any remaining context that exceeds this budget threshold. Finally, under severe memory pressure where limited GPU HBM capacity forces request preemption, C ASCADE uses Brrem as the governing preemption metric. By selectively preempting active requests possessing the largest remaining latency budgets (i.e., those with maximal headroom to absorb re-execution latencies), C ASCADE ensures that preemption overheads do not trigger downstream SLO violations. A preempted request returns to its queue with its remaining budget recomputed by Equation 5, so its re-execution is scheduled against the budget it has left; preempting the highest-budget request is safe precisely because that budget covers the added re-execution latency. Algorithm 1 presents the C ASCADE scheduling and restoration procedure. D. Implementation We implement C ASCADE on top of vLLM [20] and use LMCache [25] for KV block placement and movement across the HBM, DRAM, and NVMe tiers. We reuse vLLM’s continuous batching, chunked prefill, paged KV allocation, and prefixcache block hashing unchanged, and add only the budget machinery on top: the TTFT estimator, the latency budget engine, the dual-tier queues, the budget-feasible prefetcher, and the budget-aware preemption path. C ASCADE requires no changes to model weights and no additional hardware. The rest of this section describes these additions: the state each request carries, how the scheduler consumes it, how prefix state is placed and promoted across the memory hierarchy, and how requests are preempted under memory pressure. In each case we describe only what C ASCADE adds; the underlying mechanism is vLLM’s unless noted.

Algorithm 1: C ASCADE Budget-Aware Scheduling and Prefix Restoration Input: Class SLO targets {Sc }, Arriving requests R, Memory tier paths {P (k)}, Link bandwidths {Bℓeff }, Guardband γ Output: Execution batch B, Prefix fetch allocations {Mr,k } /* Phase 1: Latency Estimation & Queue Admission */ foreach arriving request r ∈ R do
+ Lmax ; // Estimate TTFT Lr ← γ2 Lactual r r via Eq. (2) Br ← Sc(r) − Lr ; // Compute Latency Budget via Eq. (3) if Br > 0 then Q1 .enqueue(r) ; // Admit to Tier-1 Priority Queue else Q2 .enqueue(r) ; // Demote to Tier-2 Opportunistic Queue /* Phase 2: Chunk Iteration Scheduling & Prefix Prefetching */ while GPU Has Capacity() and (Q1 ̸= ∅ or Q2 ̸= ∅) do tcurr ← getCurrentTime(); /* Update remaining budgets for active Tier-1 requests */ foreach r ∈ Q1 do Brrem ← Br − (tcurr − ar ) ; // Update Remaining Budget Q1 .sortByAscending(Brrem ) ; // Least-Remaining-Budget-First r ← (Q1 ̸= ∅) ? Q1 .pop() : Q2 .pop(); /* Calculate budget-feasible prefix fetch volume from tier k */ P [Brrem − ℓ∈P (k) δℓ ]+ ; // Max restorable Mr,k ← P 1/B eff ℓ∈P (k)

ℓ

bytes TriggerPrefetch(r, Mr,k ) ; // Asynchronously restore up to Mr,k bytes B ← B ∪ {r}; /* Budget-aware preemption under HBM memory pressure */ if IsHBMFull() then rpreempt ← arg maxr′ ∈B Brrem ′ ; Preempt(rpreempt ) ; // Evict request with largest headroom return B;

a) Per-request state: Alongside vLLM’s execution state (token sequence and paged KV block table), C ASCADE threads a small metadata record through the queues, holding the request’s class SLO Sc(r) , estimated latency Lr , allocated budget Br , arrival timestamp ar , and matched prefix-hit profile. The scheduler derives Brrem from Br and ar on demand (Equation 5) each iteration rather than storing it, so the only per-iteration write is the priority key. These few scalar fields add negligible overhead over vLLM’s request object. b) Scheduling: The estimator and budget engine run on the CPU over live queue occupancy and per-tier prefix-hit metadata, adding no GPU work on the critical path. Each

chunked-prefill iteration recomputes Brrem (Equation 5) for the Tier-1 queue and dispatches least-remaining-budget-first; because prefill chunks are co-scheduled with active decode steps, the budget only reorders which prefill enters the batch next and never stalls in-flight decodes. The update and sort overlap with the current batch’s GPU execution, so the added cost is negligible relative to a decode step. c) Memory management and HBM allocation: Reused prefix state stays in the deeper tiers and is promoted toward HBM only when a request will consume it. On a hit, the prefetcher computes the budget-feasible bound Mr,k (Equation 7) for the holding tier k; a deep- or remote-tier hit is staged NVMe to DRAM to HBM, and C ASCADE allocates HBM only at the final DRAM-to-HBM hop, keeping scarce HBM free while the slow transfer is in flight rather than pinning it for the full multi-hop latency. d) Prefix hit detection: On top of vLLM’s per-block prefix hashing, C ASCADE maintains a cluster-wide index that records, for each cached block, the deepest tier holding it. A request’s matched prefix length and per-block tiers form the prefix-hit profile that the estimator consumes (Section IV-B) and that sets the byte bound Mr,k . Free blocks are reclaimed least-recently-used within each tier, so hot prefixes stay in the fastest tiers and cold ones spill deeper. e) Preemption under HBM pressure: With continuous batching and chunked prefill, batch composition changes only at chunk boundaries, so C ASCADE never interrupts a running kernel: it preempts at the same boundary where vLLM admits the next chunk. When admitting a chunk would exceed HBM capacity, it evicts the resident prefill-stage request with the largest remaining budget (Algorithm 1), never a decode-stage request, so in-progress token generation is untouched. The victim’s KV state is spilled to DRAM when that fits its remaining budget and recomputed otherwise, and its budget is recomputed on requeue (Equation 5); choosing the highestbudget victim makes the added re-execution the least likely to cause a new violation. V. E VALUATION A. Methodology a) Models and Serving Cluster: We evaluate C ASCADE across three representative LLM architectures: Qwen-2.572B [1], Llama-3-70B, and Llama-3-405B [5], served with a tensor parallelism (TP) degree of 4 [10]. Model weights are quantized to NVFP4 precision, while Key–Value (KV) cache blocks are maintained in FP8. While all three models natively use Grouped-Query Attention (GQA) [6], we evaluate Qwen2.5-72B under Multi-Head Attention (MHA) configurations to demonstrate the generality of our design across diverse attention mechanisms (Table I). All hardware profiling is conducted on NVIDIA GB200 NVL72 nodes interconnected via Multi-Node NVLink (MNNVL) [27], [28]. To evaluate large-scale production traces across multi-replica clusters, we extend the Vidur simulator [2] to model multi-tier memory hierarchies and LMCache [25] for optimized KV cache data movement. We populate the simulator using data-movement

TABLE I: Model Configurations and Hardware Setup Model

Weights Precision

KV Cache Precision

GPU (Tensor Parallelism)

Attention Mechanism

Qwen-2.5-72B Llama-3-70B Llama-3-405B

NVFP4 NVFP4 NVFP4

FP8 FP8 FP8

GB200 (4) GB200 (4) GB200 (4)

MHA used GQA GQA

TABLE II: Traces used in evaluation Trace

No. of Requests

Average QPS

Input Sequence Length p50 p95 p99

Output Sequence Length p50 p95 p99

ChatBot Tool&Agent Coder Reasoning

43,058 172,800 43,011 10,812

5.98 24.0 5.97 1.5

1,046 574 4,540 3,680

8,808 2,491 13,406 16,221

14,364 6,294 14,406 24,972

375 39 469 1,665

1,032 328 2,699 12,669

1,641 1,006 5,842 34,686

Mixed ChatBot Heavy Tool&Agent Heavy Coder Heavy Reasoning Heavy Uniform

269,681 54,390 73,965 54,345 23,756 41,923

37.46 7.55 10.27 7.55 3.3 5.82

886 1,016 627 2,883 1,298 1,430

10,749 9,086 3,281 13,264 13,421 13,034

13,792 14,188 11,183 14,311 22,301 19,081

86 328 47 348 425 390

1,478 1,095 546 2,465 8,477 5,028

4,812 2,178 1,671 5,711 22,248 14,630

profiles measured directly on physical GB200 NVL72 hardware across NVLink-C2C and MNNVL interconnects. b) Workloads and Traces: To evaluate C ASCADE under realistic multi-tier KV caching dynamics, we utilize opensourced production traces collected from a Qwen model serving cluster on Aliyun Bailian [7]. The dataset consists of a twohour sampled trace containing real request arrival timestamps and exact prefix block hash matches, capturing four dominant LLM application classes: ChatBot (interactive conversation), Tool&Agent (agentic function calls), Coder (code generation copilots), and Reasoning (multi-step thinking workloads). Using these base application traces, we construct five workload mixtures to evaluate diverse deployment scenarios: (1) Mixed, preserving the authentic production distribution across all four classes; (2) four App-Heavy workloads, where a target application accounts for 50% of total traffic and the remaining 50% is split evenly among the other three; and (3) Uniform, containing an equal 25% split per application class. Table II summarizes the key characteristics of each trace, including input/output token length distributions, total request counts, and average arrival rates over the two-hour window. c) Service Level Objective (SLO) Targets: To provide rigorous quality-of-service assurances, serving systems must satisfy strict latency targets defined by service level agreements (SLAs). Following prior work [31], we define the 90th-percentile Time-to-First-Token (TTFTp90 ) and Time-PerOutput-Token (TPOTp90 ) SLOs relative to isolated baseline execution delays. Specifically, we set the normalized targets to TTFTp90 = 10× and TPOTp90 = 5×, meaning 90% of requests in a given class must achieve a TTFT and TPOT within 10× and 5× of a single request executing on identical hardware without batching or cross-tenant interference. TABLE III: SLO target Model Qwen-2.5-72B Llama-3-70B Llama-3-405B

ChatBot 1.83 2.60 6.20

TTFT (s) Tool&Agent Coder 0.35 0.83 1.60

3.49 6.08 14.50

Reasoning 4.23 9.88 21.70

TPOT (ms) 50 100 200

Fig. 8: System goodput and SLO violation rate across all three models and ten workload traces. Goodput (output tokens per second, left axis) is normalized to the FCFS baseline per trace; scatter markers report SLO violation rate (right axis).

Fig. 9: Time-To-First-Token (TTFT) tail latency distribution for Qwen-2.5-72B across application classes in the Mixed workload trace. While FCFS and EDF induce high tail latencies across all classes and SJF starves long-context tasks (Coder and Reasoning), C ASCADE maintains low tail latencies across all request sizes by scheduling requests just-in-time based on remaining latency budget.

Table III summarizes the resulting absolute TTFT and TPOT SLO targets for each model architecture and workload trace. d) Baselines: We implement C ASCADE on top of the V LLM-v1 inference engine [20] and evaluate it against three state-of-the-art policies: (1) FCFS, the default V LLM scheduler, which dispatches requests across all workload classes in First-Come, First-Served order; (2) EDF, an Earliest Deadline First policy that introduces deadline awareness by prioritizing requests based on their target TTFT SLO deadlines; and (3) SJF, a Shortest Job First policy that prioritizes requests with shorter input sequence lengths to minimize prefill compute overhead. For a fair comparison, all policies and C AS CADE are evaluated under identical cluster settings within our extended Vidur simulator framework. All configurations use the same global scheduler, which routes requests based on HBM prefix cache hits [34] and GPU prefill load, and enforces prefill-decode (PD) co-location with chunked prefills [3] (chunk size of 512 tokens, maximum batch size of 128) to balance TTFT and TPOT SLO trade-offs. Unless otherwise

stated, our evaluation on the Mixed workload trace deploys a cluster capacity comprising 9 instances of Qwen-2.5-72B, 6 instances of Llama-3-70B, and 12 instances of Llama-3-405B. B. Serving Efficiency under Production Traces We first evaluate C ASCADE against the baselines using the arrival timestamps from the production traces, then decompose the result to show which serving overheads it removes. 1) Goodput and SLO Violations: Figure 8 shows goodput and SLO violation rate for the three models on the ten traces. The x-axis lists the traces (refer V-A). The left y-axis is goodput,the output tokens per second from requests that meet both the TTFT and TPOT target, normalized to FCFS per trace. The markers are the violation rate, the fraction of requests that miss either target. On average C ASCADE attains 2.4× the goodput of FCFS and 40% fewer violations, and it has the highest goodput of the four policies on every trace. The gain is largest on traces with many long prompts, such as Mixed (2.7×) and Coder Heavy on Llama-3-405B. In

Fig. 10: Jain’s Fairness Index (J ) across all workloads and models. C ASCADE achieves uniformly high fairness across all workloads.

Fig. 11: SLO violations grouped by cause for the three models, on a log scale. The causes are head-of-line (HOL) queueing delay, prefix KV restoration delay, HBM-pressure preemption, and compound cases. C ASCADE removes the HOL and preemption causes and keeps restoration within the budget.

these traces a long prompt blocks the short requests behind it under FCFS and EDF. C ASCADE orders requests by remaining budget, so a short request runs before a long one that still has budget to spare, and the wait is moved onto the requests that can afford it. On traces with lighter load, such as Tool&Agent Heavy and Reasoning Heavy, the baselines already meet most targets and the gain is 1.1× to 1.5×, which comes from prefetching reused prefixes rather than from reordering. 2) Sources of SLO Violation: To understand why C ASCADE lowers the SLO violations, Figure 11 groups the SLO violations by cause for the three models. The y-axis is the violation count on a log scale. Each bar is split into four causes: HOL queueing delay, prefix KV restoration delay from a deep tier, HBM-pressure preemption of a prefill-stage request, and cases that combine these. The main cause differs by model. For the Llama models, most baseline violations are HOL delay, because their KV cache is small and requests spend their time in compute and in the queue. For Qwen-2.5-72B, restoration and preemption make up a larger share, because MHA stores more KV per token, which raises both the data moved on a restore and the pressure on HBM. C ASCADE lowers the total violation count significantly across the three models, for example from 1.5 × 105 to 4 × 103 on Qwen-2.5-72B. This is because ordering by budget removes the HOL delay that

Fig. 12: SLO violation rate grouped by input-sequence-length percentile for the Mixed trace. C ASCADE stays flat across every length bin, whereas SJF’s violations rise sharply on the longest requests.

dominates the Llama baselines. Admitting a restore only when it fits the budget, and holding HBM for prefixes that will be reused in time, removes the restoration and preemption seen on Qwen. One budget drives both the scheduler and the memory manager, so both causes fall together. C. Latency and Fairness Across Heterogeneous Traffic 1) Tail Latency by Application Class: Figure 9 shows the TTFT distribution of Qwen-2.5-72B for each of the four application classes in the Mixed trace. The x-axis is TTFT in seconds on a log scale. The y-axis is the request count. FCFS and EDF have two peaks in every class: a low peak near the target and a second peak at 102 to 103 seconds made up of requests that waited behind a long prompt. SJF removes the second peak for short classes but shifts it onto Coder and Reasoning, the long-prompt classes it delays. C ASCADE has a single peak near 10−1 seconds in all four classes. It dispatches each request in time to meet its own target rather than by prompt length, so a long request is rarely stuck behind a short one. 2) SLO Violations by Request Size: Figure 12 groups requests by input length and reports the violation rate in each group. The x-axis is the input-length percentile, from p0–p50 to p99+. The y-axis is the violation rate. FCFS and EDF violate 50% to 70% in every group, because they ignore prompt length. SJF violates 12% to 16% on the shortest

Fig. 13: Normalized goodput and SLO violation rate as serving instances change, for the Mixed trace. Goodput is normalized to FCFS at full capacity; scatter markers report SLO violation rate. C ASCADE sustains goodput as instances reduce.

requests but 65% to 72% at p99+, because it keeps delaying the longest requests. C ASCADE violates only 2% to 15% across every group and model, so the longest requests fail at almost the same rate as the shortest. This is because C ASCADE orders by budget rather than by length, so the goodput of Section V-B1 does not come from sacrificing long requests. 3) Fairness Across Applications: Figure 10 reports Jain’s fairness index [17] over the per-class SLO attainment. Each panel is one trace. The x-axis lists the four policies. The yaxis is the fairness index, where one means every class attains its SLO at the same rate. The three lines are the models. C ASCADE stays between 0.98 and 1.0 for all three models on every trace. SJF is the lowest on every trace and drops the furthest, to about 0.6 on Coder Heavy and ChatBot Heavy for Llama-3-405B, because it defers the long prompts and the classes that hold them miss their SLO. The drop is largest for Llama-3-405B, the biggest model, where a deferred prompt takes the longest to clear. FCFS and EDF track each other at about 0.95 to 0.99, above SJF but below C ASCADE. They stay fair because they miss the SLO at a similar rate across classes, as Figure 12 shows with their uniform 50% to 70% violations, but that even failure comes at low goodput rather than low violations. Their fairness dips only on the long-prompt traces such as Reasoning (0.91 for Qwen-2.5-72B), where blocking is most severe. C ASCADE is the only policy that is both fair and high-goodput: it serves each class against its own budget, so attainment stays high and close to equal across classes. D. Robustness to Capacity and Load 1) Sensitivity to Cluster Capacity: Figure 13 shows goodput and violation rate as we remove serving instances at fixed load. The x-axis is the instance count: 9, 8, and 7 Qwen2.5-72B instances (36, 32, and 28 GPUs) and 12, 11, and 10 Llama-3-405B instances (48, 44, and 40 GPUs). The left y-axis is goodput normalized to FCFS at full capacity. The markers are the violation rate. As instances are removed, FCFS and EDF goodput drops to 0.05× and their violation rate passes 90%, because the queues no longer drain between

Fig. 14: Goodput and SLO violation under varying load for Qwen-2.5-72B model. Goodput normalized to FCFS with QPS=32.

Fig. 15: TTFT at the p50, p90, and p95 percentiles under increasing load for Qwen-2.5-72B on the Mixed trace, log scale. The dashed line marks the TTFT SLO. C ASCADE stays under the SLO across all three percentiles, whereas FCFS and EDF cross it by 36 QPS.

arrivals and HOL delay builds up. C ASCADE still reaches 2.4× goodput at 7 Qwen-2.5-72B serving instances (28 GPUs), above FCFS at 9 instances (36 GPUs), so it serves the same load with 22% fewer GPUs and keeps violations below ∼16%. 2) Sensitivity to Offered Load: Figure 14 shows goodput and violation rate as we raise the load on one Qwen-2.5-72B deployment. The x-axis is the load from 32 to 48 QPS. The left panel is goodput normalized to FCFS at 32 QPS. The right panel is the violation rate. At 32 QPS all four policies are close. At 48 QPS, FCFS and EDF drop to 0.05× goodput with over 90% violations, because the added load turns into blocking. SJF holds 0.47× goodput at a 43% violation rate, because it still delays the long prompts. C ASCADE holds 1.5× goodput at a 14% violation rate, because it only starts work that fits the remaining budget as that budget shrinks. Figure 15 shows the TTFT behind the goodput of Figure 14. Each panel is one percentile, p50, p90, and p95, on a log yaxis against the same 32 to 48 QPS load. The dashed line is the TTFT target. FCFS and EDF cross the target by 36 QPS and reach 103 seconds at high load as blocked prompts pile up. SJF stays under the target at p50 but crosses it at p95, once the long prompts reach the tail. C ASCADE stays under the target at all three percentiles, at 3.5 seconds at p95 and 48

Fig. 16: SLO attainment per application class across models for Mixed trace. C ASCADE consistently improves the SLO attainment across all workload classes instead of favoring a certain class of workload. QPS, because it dispatches by budget and bounds the tail, not just the median. The requests under the dashed line here are the ones counted as goodput in Figure 14. 3) SLO Attainment by Application Class: Figure 16 breaks down SLO attainment across distinct application classes to evaluate whether baseline scheduling policies introduce structural biases favoring specific workload types. While existing schedulers disproportionately prioritize short-context queries at the expense of prompt-heavy or agentic tasks, C ASCADE achieves consistently superior SLO compliance across all application categories and model architectures. This equitable performance stems from C ASCADE’s fine-grained, per-request latency budget management, which evaluates execution headroom dynamically for each request rather than relying on rigid, class-wide or size-biased heuristics. VI. R ELATED W ORK Service-Level Objectives (SLOs) have long served as a foundational abstraction for resource allocation and task scheduling across diverse computing domains, including mobile application runtimes [33], data-parallel processing clusters [11], and latency-sensitive datacenter networks [37]. Applying SLO-driven scheduling to LLM serving, however, introduces distinct challenges due PD-colocation challenges. Recent works have explored this design space along several orthogonal dimensions. AlpaServe [23], Nitsum [35] optimizes model-parallelism strategies to satisfy heterogeneous SLO requirements, while Learned Best-Effort LLM Serving [19] applies reinforcement learning to route requests across model variants to balance accuracy against latency targets. C ASCADE relies on fixed model-parallelism and provides high goodput while complying with SLO requirements. a) Chunking, Opportunistic Scheduling, and KV-Aware Serving: Another line of research explores chunked execution and opportunistic batching to balance prefill throughput against decode latency bounds. Building on the chunked prefill model of Sarathi [3], frameworks such as Medha [4], PolyServe [45], and QoServe [13] adaptively scale chunk granularities to prevent accumulating attention overhead from breaching

Time-Between-Tokens (TBT) limits, with QoServe leveraging request-level latency slack for chunk size tuning. Similarly, systems like Conserve [30] and SageServe [18] employ reactive heuristics—such as scheduling background tasks when interactive load drops below fixed thresholds (e.g., 60%) or applying reactive preemption during load spikes. However, these systems implicitly assume that incoming prompts require full GPU recomputation, treating TTFT purely as a compute-bound phase while ignoring cross-request prefix KV cache reuse and deep-tier state restoration delays. While MoonCake [31] incorporates prefix KV cache-aware scheduling in PrefillDecode disaggregated architectures, it relies on aggressive request rejection under cluster overload. C ASCADE bridges these gaps by co-designing budget-aware request dispatching with multi-tier KV state restoration, preserving high cluster goodput without resorting to request rejection. b) Multi-SLO Scheduling: A growing body of work focuses on multi-objective SLO scheduling for LLM inference. QoServe [13] leverages multi-class SLO targets to harvest (TBT) slack via dynamic chunk resizing, but lacks support for prefix cache reuse. SLO-Serve [9] formulates scheduling as a dynamic programming (DP) optimization over active and queued requests under multiple SLO constraints; however, searching this combinatorial space across chunked prefill and continuous batching parameters introduces substantial computational overhead that limits online scalability. JITServe [42] employs conservative output sequence length estimation with online refinement to maximize service utility, while FastServe [38] applies preemptive iteration-level scheduling using a multi-level feedback queue (MLFQ). In contrast to these approaches, C ASCADE uses lightweight, runtime latency budgets to jointly orchestrate request dispatching and prefix KV cache management across multi-tier memory pools in a PDcolocated architecture—bypassing the need for unscalable DP formulations or dynamic chunking heuristics. VII. C ONCLUSIONS Serving a language model request under a latency SLO involves more than running the model: the request also incurs queueing delay, batching interference, and the cost of moving reused KV cache into GPU memory, and all of it is charged against the same SLO. Problem gets exacerbated with PDcolocation with prefill and decode being served on same instances with respective SLOs. The time an SLO leaves for this overhead is the request’s latency budget, which differs by orders of magnitude across requests. We present C ASCADE, a serving system that estimates each request’s latency budget at runtime and treats it as a single quantity that governs two decisions handled in isolation today: how requests are scheduled, and how their reused KV cache is placed across the memory hierarchy. By steering overhead toward requests with budget to spare, C ASCADE improves SLO attainment and useful throughput together, across a range of models, applications, and request sizes, and without additional hardware while preserving fairness across heterogeneous request classes.

R EFERENCES [1] “Qwen2 technical report,” 2024. [2] A. Agrawal, N. Kedia, J. Mohan, A. Panwar, N. Kwatra, B. S. Gulavani, R. Ramjee, and A. Tumanov, “Vidur: A large-scale simulation framework for llm inference,” in Proceedings of Machine Learning and Systems, vol. 6, 2024, pp. 351–366. [3] A. Agrawal, N. Kedia, A. Panwar, J. Mohan, N. Kwatra, B. S. Gulavani, A. Tumanov, and R. Ramjee, “Taming throughput-latency tradeoff in llm inference with sarathi-serve,” in Proceedings of the 18th USENIX Conference on Operating Systems Design and Implementation, ser. OSDI’24. USA: USENIX Association, 2024. [4] A. Agrawal, H. Qiu, J. Chen, Íñigo Goiri, C. Zhang, R. Shahid, R. Ramjee, A. Tumanov, and E. Choukse, “No request left behind: Tackling heterogeneity in long-context llm inference with medha,” 2025. [Online]. Available: https://arxiv.org/abs/2409.17264 [5] AI@Meta, “Llama 3 model card,” 2024. [Online]. Available: https://github.com/meta-lama/llama3/blob/main/MODEL CARD.md [6] J. Ainslie, J. Lee-Thorp, M. de Jong, Y. Zemlyanskiy, F. Lebron, and S. Sanghai, “GQA: Training generalized multi-query transformer models from multi-head checkpoints,” in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, H. Bouamor, J. Pino, and K. Bali, Eds. Singapore: Association for Computational Linguistics, Dec. 2023, pp. 4895–4901. [Online]. Available: https://aclanthology.org/2023.emnlp-main.298/ [7] Bailian, “Qwen-bailian anonymous dataset,” 2025. [Online]. Available: https://github.com/alibaba-edu/qwen-bailian-usagetraces-anon [8] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba, “Evaluating large language models trained on code,” 2021. [Online]. Available: https://arxiv.org/abs/2107.03374 [9] S. Chen, Z. Jia, S. Khan, A. Krishnamurthy, and P. B. Gibbons, “Slos-serve: Optimized serving of multi-slo llms,” 2025. [Online]. Available: https://arxiv.org/abs/2504.08784 [10] S. Cheng, Z. Liu, J. Du, and Y. You, “Atp: Adaptive tensor parallelism for foundation models,” 2023. [Online]. Available: https: //arxiv.org/abs/2301.08658 [11] A. D. Ferguson, P. Bodik, S. Kandula, E. Boutin, and R. Fonseca, “Jockey: guaranteed job latency in data parallel clusters,” in Proceedings of the 7th ACM European Conference on Computer Systems, ser. EuroSys ’12. New York, NY, USA: Association for Computing Machinery, 2012, p. 99–112. [Online]. Available: https://doi.org/10.1145/2168836.2168847 [12] I. Gim, G. Chen, S. seob Lee, N. Sarda, A. Khandelwal, and L. Zhong, “Prompt cache: Modular attention reuse for low-latency inference,” 2024. [Online]. Available: https://arxiv.org/abs/2311.04934 [13] K. Goel, J. Mohan, N. Kwatra, R. S. Anupindi, and R. Ramjee, “Qoserve: Breaking the silos of llm inference serving,” in Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ser. ASPLOS ’26. New York, NY, USA: Association for Computing Machinery, 2026, p. 1492–1507. [Online]. Available: https://doi.org/10. 1145/3779212.3790206 [14] Google, “llm-d,” 2025. [Online]. Available: https://github.com/llmd/llm-d [15] C. Hooper, S. Kim, H. Mohammadzadeh, M. W. Mahoney, Y. S. Shao, K. Keutzer, and A. Gholami, “Kvquant: towards 10 million context length llm inference with kv cache quantization,” in Proceedings of the 38th International Conference on Neural Information Processing Systems, ser. NIPS ’24. Red Hook, NY, USA: Curran Associates Inc., 2024. [16] C. Hu, H. Huang, L. Xu, X. Chen, J. Xu, S. Chen, H. Feng, C. Wang, S. Wang, Y. Bao, N. Sun, and Y. Shan, “Inference without interference: Disaggregate llm inference for mixed downstream workloads,” 2024. [Online]. Available: https://arxiv.org/abs/2401.11181

[17] R. Jain, D. Chiu, and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” 1998. [Online]. Available: https://arxiv.org/abs/cs/9809099 [18] S. Jaiswal, K. Jain, Y. Simmhan, A. Parayil, A. Mallick, R. Wang, R. S. Amant, C. Bansal, V. Ruhle, A. Kulkarni, S. Kofsky, and S. Rajmohan, “Sageserve: Optimizing llm serving on cloud data centers with forecast aware auto-scaling,” Proc. ACM Meas. Anal. Comput. Syst., vol. 9, no. 3, Dec. 2025. [Online]. Available: https://doi.org/10.1145/3771576 [19] S. Jha, C. Hooper, X. Liu, S. Kim, and K. Keutzer, “Learned best-effort llm serving,” 2024. [Online]. Available: https://arxiv.org/abs/2401.07886 [20] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica, “Efficient memory management for large language model serving with pagedattention,” in Proceedings of the 29th Symposium on Operating Systems Principles, ser. SOSP ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 611–626. [Online]. Available: https://doi.org/10.1145/3600006.3613165 [21] R. Lai, H. Liu, C. Lu, Z. Liu, S. Cao, S. Shao, Y. Zhang, L. Mai, and D. Ustiugov, “Tokenscale: Timely and accurate autoscaling for disaggregated llm serving with token velocity,” 2025. [Online]. Available: https://arxiv.org/abs/2512.03416 [22] J. Li, Y. Zhu, B. Chen, E. K. Lee, and K. Nahrstedt, “Revisiting disaggregated large language model serving for performance and energy implications,” in Proceedings of the Sixth European Workshop on Machine Learning and Systems, ser. EuroMLSys ’26. New York, NY, USA: Association for Computing Machinery, 2026, p. 397–406. [Online]. Available: https://doi.org/10.1145/3805621.3807662 [23] Z. Li, L. Zheng, Y. Zhong, V. Liu, Y. Sheng, X. Jin, Y. Huang, Z. Chen, H. Zhang, J. E. Gonzalez, and I. Stoica, “AlpaServe: Statistical multiplexing with model parallelism for deep learning serving,” in 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). Boston, MA: USENIX Association, Jul. 2023, pp. 663–679. [Online]. Available: https://www.usenix.org/ conference/osdi23/presentation/li-zhouhan [24] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, no. 1, p. 46–61, Jan. 1973. [Online]. Available: https://doi.org/10.1145/321738.321743 [25] Y. Liu, Y. Cheng, J. Yao, Y. An, X. Chen, S. Feng, Y. Huang, S. Shen, R. Zhang, K. Du, and J. Jiang, “Lmcache: An efficient kv cache layer for enterprise-scale llm inference,” 2025. [Online]. Available: https://arxiv.org/abs/2510.09665 [26] NVIDIA, “Ai-dynamo,” 2025. [Online]. Available: https://github.com/ aidynamo/dynamo [27] NVIDIA, “Nvidia gb200 nvl partition,” 2025. [Online]. Available: https: //docs.nvidia.com/multi-node-nvlink-systems/partition-guide-v1-2.pdf [28] NVIDIA, “Nvidia gb200 nvl72 delivers trillion-parameter llm training and real-time inference,” 2025. [Online]. Available: https://developer.nvidia.com/blog/nvidia-gb200-nvl72-deliverstrillion-parameter-llm-training-and-real-time-inference/ [29] P. Patel, E. Choukse, C. Zhang, A. Shah, I. n. Goiri, S. Maleki, and R. Bianchini, “Splitwise: Efficient generative llm inference using phase splitting,” in Proceedings of the 51st Annual International Symposium on Computer Architecture, ser. ISCA ’24. IEEE Press, 2025, p. 118–132. [Online]. Available: https://doi.org/10.1109/ISCA59077.2024.00019 [30] Y. Qiao, S. Anzai, S. Yu, H. Ma, S. Yang, Y. Wang, M. Kim, Y. Wu, Y. Zhou, J. Xing, J. E. Gonzalez, I. Stoica, and H. Xu, “Conserve: Fine-grained gpu harvesting for llm online and offline co-serving,” 2025. [Online]. Available: https://arxiv.org/abs/2410.01228 [31] R. Qin, Z. Li, W. He, J. Cui, F. Ren, M. Zhang, Y. Wu, W. Zheng, and X. Xu, “Mooncake: trading more storage for less computation — a kvcache-centric architecture for serving llm chatbot,” in Proceedings of the 23rd USENIX Conference on File and Storage Technologies, ser. FAST ’25. USA: USENIX Association, 2025. [32] S. Qiu, Y. Hu, X. Wang, W. Zhu, J. Yan, H. Chen, K. Xu, K. Chen, and Y. Zhang, “Tutti: Making ssd-backed kv cache practical for long-context llm serving,” 2026. [Online]. Available: https://arxiv.org/abs/2605.03375 [33] L. Ravindranath, J. Padhye, R. Mahajan, and H. Balakrishnan, “Timecard: controlling user-perceived delays in server-based mobile applications,” in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. New York, NY, USA: Association for Computing Machinery, 2013, p. 85–100. [Online]. Available: https://doi.org/10.1145/2517349.2522717 [34] V. Srivatsa, Z. He, R. Abhyankar, D. Li, and Y. Zhang, “Preble: Efficient distributed prompt scheduling for llm serving,” 2024. [Online]. Available: https://arxiv.org/abs/2407.00023

[35] V. Srivatsa, Z. He, P. Guo, D. Li, and Y. Zhang, “Nitsum: Serving tiered llm requests with adaptive tensor parallelism,” 2026. [Online]. Available: https://arxiv.org/abs/2605.05467 [36] J. Wang, J. Han, X. Wei, S. Shen, D. Zhang, C. Fang, R. Chen, W. Yu, and H. Chen, “Kvcache cache in the wild: Characterizing and optimizing kvcache cache at a large cloud provider,” in 2025 USENIX Annual Technical Conference (USENIX ATC 25). USENIX Association, Jul. 2025. [Online]. Available: https://www.usenix.org/ conference/atc25/presentation/wang-jiahao [37] C. Wilson, H. Ballani, T. Karagiannis, and A. Rowtron, “Better never than late: meeting deadlines in datacenter networks,” in Proceedings of the ACM SIGCOMM 2011 Conference, ser. SIGCOMM ’11. New York, NY, USA: Association for Computing Machinery, 2011, p. 50–61. [Online]. Available: https://doi.org/10.1145/2018436.2018443 [38] B. Wu, Y. Zhong, Z. Zhang, S. Liu, F. Liu, Y. Sun, G. Huang, X. Liu, and X. Jin, “FastServe: Iteration-Level preemptive scheduling for large language model inference,” in 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 26). Renton, WA: USENIX Association, May 2026, pp. 57–74. [Online]. Available: https://www.usenix.org/conference/nsdi26/presentation/wu-bingyang [39] Y. Xiang, X. Li, K. Qian, Y. Yang, D. Zhu, W. Yu, E. Zhai, X. Liu, X. Jin, and J. Zhou, “Aegaeon: Effective gpu pooling for concurrent llm serving on the market,” in Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, ser. SOSP ’25. New York, NY, USA: Association for Computing Machinery, 2025, p. 1030–1045. [Online]. Available: https://doi.org/10.1145/3731569.3764815 [40] G.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, “Orca: A distributed serving system for transformer-based generative models,” in 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). Carlsbad, CA: USENIX Association, Jul. 2022, pp. 521–538. [Online]. Available: https://www.usenix.org/ conference/osdi22/presentation/yu [41] J. Yu, M. Hu, Z. Lin, and M. Zhang, “Superinfer: Slo-aware rotary scheduling and memory management for llm inference on superchips,” 2026. [Online]. Available: https://arxiv.org/abs/2601.20309 [42] W. Zhang, Z. Wu, Y. Mu, R. Ning, B. Liu, N. Sarda, M. Lee, and F. Lai, “Jitserve: Slo-aware llm serving with imprecise request information,”

2025. [Online]. Available: https://arxiv.org/abs/2504.20068 [43] L. Zheng, L. Yin, Z. Xie, C. Sun, J. Huang, C. H. Yu, S. Cao, C. Kozyrakis, I. Stoica, J. E. Gonzalez, C. Barrett, and Y. Sheng, “Sglang: efficient execution of structured language model programs,” in Proceedings of the 38th International Conference on Neural Information Processing Systems, ser. NIPS ’24. Red Hook, NY, USA: Curran Associates Inc., 2024. [44] Y. Zhong, S. Liu, J. Chen, J. Hu, Y. Zhu, X. Liu, X. Jin, and H. Zhang, “Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving,” in 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). USENIX Association, 2024, pp. 193–210. [Online]. Available: https://www.usenix.org/conference/osdi24/presentation/zhong-yinmin [45] K. Zhu, H. Shi, L. Xu, J. Shan, A. Krishnamurthy, B. Kasikci, and L. Xie, “Polyserve: Efficient multi-slo serving at scale,” 2025. [Online]. Available: https://arxiv.org/abs/2507.17769

AI U SE We acknowledge the use of AI in the preparation of this submission. AI assistants were used in two settings. First, during system implementation, we used AI coding assistants to help write and debug parts of the codebase, including the scripts that generate the figures. The system design and experimental methodology were our own, and we analyzed, validated, and interpreted all results ourselves. No measured result, figure, or numerical value in this paper was produced by AI. Second, during writing, we used AI to revise text, organize the structure of sections, and perform copy-editing such as grammar, wording, and consistency of terminology. We directed the content of every section, verified claims, and edited the output.

Related documents

• Beyond Greedy Chunking: SLO-Aware Sliding-Window Scheduling for LLM Inference#259421
• Scheduling the Unschedulable: Taming Black-Box LLM Inference at Scale#2550
• SiFAR: Synchronization-Free All-Reduce for Low-Latency LLM Inference#361431
• Latency Prediction for LLM Inference on NPU Systems#282761
• HeteroMosaic: Exposing and Exploiting Heterogeneous Execution Opportunities for Energy-Efficient Edge LLM Inference#366223