🤖 machine learning

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

Cascade is an LLM serving system that leverages a dynamic, per-request latency budget to jointly optimize scheduling and KV-cache management, thereby significantly improving SLO-satisfied goodput and fairness while reducing violations compared to traditional first-come-first-served approaches.

Original authors: Muhammad Adnan, Rohan Mahapatra, Prashant J. Nair, Daniel Berger, Pantea Zardoshti, Rodrigo Fonseca, Esha Choukse

Published 2026-08-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Muhammad Adnan, Rohan Mahapatra, Prashant J. Nair, Daniel Berger, Pantea Zardoshti, Rodrigo Fonseca, Esha Choukse

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling, high-speed train station where thousands of passengers are trying to board different trains at the exact same time. Some passengers have just a single backpack (a short, quick question), while others are dragging massive, heavy suitcases filled with years of memories (a long, complex story or a deep reasoning task). In the world of Artificial Intelligence, these "trains" are Large Language Models (LLMs)—the super-smart computers that power chatbots, coding assistants, and reasoning agents. The "passengers" are the requests we send them.

For these systems to feel fast and helpful, they have to promise to deliver answers within a specific time limit, known as a Service Level Objective (SLO). Think of this like a ticket that says, "You must be on the train and moving within 5 seconds." The problem is, the station managers have been using a very old rule: "First come, first served." This means if a passenger with a giant suitcase arrives first, everyone else has to wait behind them, even if the person behind them only has a tiny backpack and could be served in a split second. This causes a massive traffic jam. Furthermore, the station has a limited amount of high-speed storage (like a VIP waiting room) for the passengers' luggage. If the luggage is stored in a slow, distant warehouse, fetching it takes time. If the station manager doesn't know how much time each passenger has left before their train leaves, they might waste precious seconds fetching luggage for someone who is already late, while someone else who is on time gets left behind.

This is the challenge tackled by a new system called CASCADE, described in a recent paper by researchers from the University of British Columbia, Microsoft Azure Research, and NVIDIA. The researchers realized that every request has a hidden "time budget"—the difference between the time it needs to finish its job and the time it is allowed to take. Some requests have a huge budget (lots of extra time), while others have almost none. The paper argues that instead of just looking at who arrived first or how big the request is, the system should look at this remaining time budget to decide who goes next and how to handle their data.

The core idea of CASCADE is to treat this time budget as a shared currency for two different jobs: deciding the order of requests and managing where their data lives. In the paper's simulations, which used real-world traffic data from production servers and tested on three different giant AI models (Qwen-2.5-72B, Llama-3-70B, and Llama-3-405B), CASCADE showed impressive results. By constantly calculating how much "time headroom" each request had left, the system could prioritize those running out of time while letting requests with plenty of time wait a bit longer or fetch their data from slower, cheaper storage.

The findings suggest that this approach is a game-changer for efficiency. In their tests, CASCADE improved the number of successful requests the system could handle (called "goodput") by up to 2.4 times compared to the standard "first-come, first-served" method used by popular systems like vLLM. More importantly, it cut the number of requests that missed their time limits (SLO violations) by 40%. Perhaps most creatively, it did this without making long, complex requests suffer. Unlike other methods that might rush short requests and starve long ones, CASCADE kept the experience fair for everyone, ensuring that both the "backpack" and the "giant suitcase" passengers got served on time. The system achieved this by dynamically deciding whether to fetch data from fast memory, slower storage, or just re-calculate it, based entirely on whether the specific request had enough time budget to absorb the delay.

Technical Summary: CASCADE

Problem Statement

Large Language Model (LLM) serving platforms currently face a fundamental mismatch between Service Level Objectives (SLOs) and the heterogeneous nature of incoming requests. While SLOs (specifically Time-to-First-Token [TTFT] and Time-Per-Output-Token [TPOT]) are defined at the service level, the execution cost of individual requests varies by orders of magnitude due to differences in input length, generation length, and the availability of reusable Key-Value (KV) cache states.

Current serving systems, such as vLLM, typically employ First-Come-First-Served (FCFS) scheduling or simple size-based heuristics (e.g., Shortest Job First). These approaches fail to account for the "latency budget" of individual requests—the difference between a request's SLO deadline and its predicted execution time. Consequently:

Head-of-Line (HOL) Blocking: Long-context requests can block short, urgent requests, causing SLO violations for the latter.
Inefficient KV Management: Systems often retrieve KV states from deep memory tiers (e.g., NVMe) to save compute time. However, without considering the specific latency budget of the requesting task, these transfers can introduce delays that exceed the request's remaining SLO headroom, turning a cache hit into an SLO violation.
Unfairness: Policies that prioritize short jobs (SJF) systematically starve long-context workloads (e.g., coding agents, reasoning tasks), while FCFS fails to distinguish between requests that have ample budget and those that are critically urgent.

Existing schedulers treat request ordering and KV-cache management as independent problems, failing to recognize that both consume the same resource: the per-request latency budget.

Methodology: The CASCADE System

CASCADE is an LLM serving system designed to jointly coordinate request scheduling and multi-tier KV-cache management using a unified, per-request latency budget.

1. Latency Budget Definition and Estimation

CASCADE defines the latency budget ( $B_r$ ) for a request $r$ as:
$B_r = S_{TTFT}^{c(r)} - L_r$
Where $S_{TTFT}^{c(r)}$ is the class-level SLO target and $L_r$ is the estimated remaining service time.

Estimation: The system uses a TTFT Latency Estimator that models prefill latency based on input length, predicted output length, available prefix KV states across the memory hierarchy (HBM, DRAM, NVMe), and current system load.
Conservatism: To ensure reliability, the estimator averages predicted latencies under actual load and maximum capacity, scaled by an empirical guardband factor ( $\gamma$ ) to account for estimation errors and contention.

2. Dual-Tier Scheduling Architecture

CASCADE utilizes a two-tier queuing mechanism based on the calculated budget:

Tier 1 (Positive Budget): Requests with $B_r > 0$ are admitted to a priority queue. These are scheduled in Least-Remaining-Budget-First order. This ensures that requests with tight deadlines (low remaining budget) are prioritized over those with ample headroom, regardless of their input size.
Tier 2 (Negative Budget): Requests with $B_r \le 0$ are demoted to a secondary queue. They are not dropped but executed opportunistically during cluster idle periods. A fixed fraction of each batch is reserved for Tier 2 to prevent starvation, and requests are promoted back to Tier 1 if their budget becomes positive as load decreases.

3. Budget-Aware KV Cache Management

The same latency budget governs memory decisions across the hierarchy (GPU HBM, CPU DRAM, NVMe):

Feasible Restoration: When a prefix KV state is found in a deep tier, CASCADE calculates the transfer time required to restore it. Restoration is only initiated if the transfer time fits within the request's remaining budget.
Fallback to Recomputation: If the transfer delay would violate the SLO, the system bypasses the deep-tier fetch and recomputes the prefix on the GPU, avoiding an SLO violation.
Preemption: Under HBM memory pressure, CASCADE preempts active requests with the largest remaining budgets. Since these requests have significant headroom, the overhead of re-execution is unlikely to cause an SLO violation.

4. Implementation

CASCADE is implemented as an extension to the vLLM serving engine. It integrates with LMCache for multi-tier KV block placement and movement. The system adds minimal overhead by threading metadata (SLO, estimated latency, arrival time) through the existing request objects and performing budget calculations on the CPU, overlapping with GPU execution.

Key Contributions

Identification of Latency Budget as a Common Resource: The paper identifies that request scheduling and KV-cache movement compete for the same resource—the per-request latency budget. It demonstrates that service deadlines, request size, and cache state alone are insufficient to determine how much overhead a request can tolerate.
Joint Coordination Mechanism: CASCADE presents 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.
Fair, High-Goodput Scheduling: The proposed budget-based scheduler reduces HOL blocking without systematically starving long-context requests, preserving fairness across heterogeneous request classes.
Empirical Validation: The system is evaluated on production traces across three large models (Qwen-2.5-72B, Llama-3-70B, Llama-3-405B) using NVIDIA GB200 NVL72 hardware profiles.

Results

Evaluations on production traces containing ChatBot, Tool&Agent, Coder, and Reasoning workloads demonstrate the following:

Goodput Improvement: CASCADE improves SLO-satisfied goodput by up to 2.4× compared to the default vLLM FCFS scheduler.
SLO Violation Reduction: It reduces SLO violations by 40% relative to FCFS.
Fairness: CASCADE maintains a high Jain's Fairness Index (near 1.0) across different request size classes, whereas Shortest Job First (SJF) causes severe starvation for long-context requests (dropping fairness to ~0.6 in heavy workloads).
Robustness: Under high load and reduced cluster capacity, CASCADE sustains high goodput and low violation rates, whereas baselines suffer from severe HOL blocking and queue buildup.

Significance and Claims

The paper claims that the primary cause of SLO violations in current systems is not a lack of intrinsic compute budget, but rather the waste of this budget due to HOL blocking and uncoordinated KV-cache transfers. By making the latency budget an explicit runtime quantity, CASCADE directs unavoidable overheads (queuing, data movement) toward requests that can absorb them, while protecting urgent requests.

The authors assert that this approach allows providers to maximize accelerator utilization and goodput while strictly adhering to latency SLOs and ensuring fairness across diverse application types (from short chat interactions to long reasoning tasks), all without requiring additional hardware or changes to model weights. The system bridges the gap between scheduling and memory management, treating them as a unified optimization problem driven by the specific urgency of each request.