Latency budget in LLM serving changes the priorities of scheduling. CASCADE demonstrates how to link scheduling and KV-cache for increased goodput.
The problem arises when all requests are formally equal in SLO, but in reality, they are not. In one cluster, chat, code generation, and reasoning coexist simultaneously. Their costs differ by orders of magnitude: prompt length, generation length, and the presence of KV-cache. Classic policies like FCFS or SJF do not account for the actual “urgency” of a request. As a result, head-of-line blocking occurs: a heavy request blocks the queue, consuming the latency budget of others. Even cache hits from NVMe can worsen the situation—compute savings translate into increased latency due to transfer costs. The system loses goodput not because of insufficient resources, but because it misallocates delays.
CASCADE makes a pragmatic shift: it introduces per-request latency budget as the primary control signal. This is the difference between SLO and the predicted execution time. Unlike deadline-based approaches, the budget considers not only the deadline but also the remaining work. This allows for comparing the “urgency” of heterogeneous requests. The key trade-off is the accuracy of estimation. An error in prediction leads to incorrect delay allocation: overestimating the budget provides false confidence and results in SLO violation. Therefore, the system uses a conservative estimate with a guardband.
Architecturally, CASCADE combines two previously independent loops: request scheduling and KV-cache management. The scheduler employs a least-remaining-budget-first strategy—requests with the smallest remaining budget are executed first. This reduces head-of-line blocking without systematically starving long requests, as in SJF. Simultaneously, the same budget manages the movement of KV-cache between HBM, DRAM, and NVMe. If cache recovery does not fit within the budget, the system prefers recompute. This is an important compromise: more GPU compute, but less latency risk. Thus, CASCADE does not minimize delays globally but redistributes them where they are safe.
The implementation is built on top of vLLM without changing the model. Three components have been added: TTFT estimator, latency budget engine, and dual-queue scheduler. The queue is divided into Tier-1 (positive budget) and Tier-2 (negative budget). The latter are not discarded but processed opportunistically. The budget is recalculated at each step, making the system adaptive to the current load. KV-cache is integrated through LMCache and multi-level memory (HBM, DRAM, NVMe). Prefetch is limited to the volume that “fits” within the remaining budget. Even preemption follows the same logic: requests with the maximum time buffer are displaced.
Results show that the key issue is not computation, but inefficient use of latency headroom. CASCADE increases SLO-compliant goodput by up to 2.4× compared to FCFS and reduces SLO violations by 40%. At the same time, fairness between request classes is maintained, which is typically broken in SJF. Improvements are particularly noticeable with long requests and mixed workloads. When resources are reduced, the system continues to maintain an acceptable level of SLO, unlike the baseline, where queue growth becomes avalanche-like. Importantly, these metrics are achieved without changing hardware or the model—only through coordination of scheduling and memory.
In a broader context, CASCADE reflects an industry trend: the shift from static policies to runtime-adaptive strategies, where the key resource becomes not CPU or GPU, but latency budget. This is especially relevant for LLM inference, where the cost of a request is unpredictable, and tail latencies are critical. The approach does not eliminate all limitations—it depends on the quality of predictions and complicates scheduling—but it provides more resilient behavior under load.
Information source
arXiv is the largest open preprint repository (since 1991, under the auspices of Cornell), where researchers quickly post working versions of papers; the materials are publicly accessible but do not undergo full peer review, so results should be considered preliminary and, where possible, checked against updated versions or peer‑reviewed journals. arxiv.org