HAServe: Horizon-Aware Scheduling and Memory Co-Design for Efficient LLM Serving

The gist The PRISM architecture co-designs request scheduling and KV-cache management to optimize fast online LLM serving for segmented and skewed workloads, achieving significant reductions in tail latency and improvements in cache hit rates across RAG and agent tasks.

How it works

PRISM introduces a Query-Aware Scheduler (QAS) which tracks reusable-segment counters across the request lifecycle to generate order-sensitive bucket signatures The QAS uses these segment priorities to create bucket scores, where Score(b) = αsizeT [b] + βutilU(b), and then fills hot lanes by scanning buckets in descending Score(b) order. This mechanism groups requests with the same reusable segments into hot lanes to improve KV-cache locality.

Demand-Aware Radix Tree (DART)

DART integrates these QAS metadata into a radix KV-cache tree, annotating selected boundary nodes with QAS metadata. DART then uses the dispatch-batch priority to decide which resident KV-cache anchors should survive memory pressure, protecting high-value shared prefixes. The eviction ordering is defined by EvictKey(u) = 0, last(u), u is a private-suffix node, 1, Pbt(seg(u)), last(u), u is a reusable node with u /∈ Ft, 2, last(u), u ∈ Ft is a protected reusable anchor.

Bottleneck Analysis and Queueing Model

The paper provides a bottleneck analysis linking TTFT behavior to admission wait, exact-prefix prefill work, KV pressure, and service-knee behavior on a single GPU. The performance is modeled using an approximate M/G/1 queueing model where the request-level sustainable arrival rate equals µπ requests/s. Theorem 1 shows that if the realized full-prompt token-level exact-prefix hit-rate gap ∆h is nonnegative, then µPRISM − µLRU ≥ 0, with equality iff ∆h = 0.

Experimental Results and Performance Gains

The experimental results show strong performance across different datasets and models. PRISM reduces average per-QPS P99 TTFT by 23.3% on Qwen3-4B-Instruct-2507 and 37.1% on Llama2-13B versus the strongest baseline. PRISM achieves the highest KV-cache hit rate across all methods and reduces P99 TTFT by 63.5% and 80.8% relative to native SGLang.

Robustness and Generalization

PRISM's advantage is not specific to segment-based RAG prompts, as it also performs well on agent-style workloads. The results support the intended scope of PRISM, showing that the system does not assume that reusable prefixes correspond to retrieved passages but only that near-future demand over repeated, token-identical prompt regions can be estimated at admission time. The evaluation also shows that PRISM can improve KV-cache hit rate and lower tail TTFT across various workloads, rather than depending on a specific hotspot distribution.

The PRISM architecture successfully co-optimizes request scheduling and KV-cache management to reduce tail latency and improve cache utilization in online LLM serving systems.

--- Page 1 ---

PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design

Xingyu Qu, School of Computer Science, Wuhan University, whu-quxy@whu.edu.cn Tianhao Lin, School of Computer Science, Wuhan University, lintianhao@whu.edu.cn Yiqi Li, School of Computer Science, Wuhan University, bruceprofession@whu.edu.cn Zhiyu Chen Amazon zhiyuche@amazon.com Sheng Wang, School of Computer Science, Wuhan University swangcs@whu.edu.cn

--- Page 2 ---

PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design

KV-Cache-oblivious retention root sys A p1 p2 arriving request cold cold MISS the arriving request follows the matching path but the path breaks at evicted anchor A Demand-aware retention root sys A p1 p2 arriving request cold cold MATCH the arriving request follows the same path and matches protected anchor A protected root: radix root sys: system prefix A: reusable anchor pi: request-specific leaf q1: sys+A + p1 q2: arriving request sys+A + p2 containing A Figure 1 Demand-aware retention in a radix KV-cache tree.

--- Page 3 ---

PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design

request admission (Dexter et al., 2025; Jiang et al., 2026). Under KV-cache pressure, however, a hot prefix may still be evicted before the next matching request arrives. KV-cache retention should therefore make demand-aware decisions to distinguish hot shared prefixes from cold private suffixes, which come from user input. As Figure 1 illustrates, without demand hints, cold branches may displace anchor A before the next matching request arrives. Instead, demand-aware retention protects A and evicts a cold branch, preserving an exact-prefix hit. This reduces prefill computation and, when coupled with hints from scheduling, lowers TTFT for subsequent hot-segment requests. This gap leads to three design requirements for online LLM serving (1) Segment-level management: the system should track reusable context pieces rather than only whole requests, because segments are more likely to recur across users or sessions when derived from the same source (2) Query-aware scheduling: the scheduler should use reusable-prefix information to reorder requests, improve KVcache locality, and pass this information to the KV-cache backend (3) Demand-aware KV retention: under memory pressure, the KV-cache manager should protect prefixes that are active or likely to be reused soon.

--- Page 4 ---

PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design

We first develop a bottleneck analysis showing how admission control and KV-cache hit rate affect TTFT in different load regimes. Guided by this analysis, we present PRISM (Prefix Reuse Optimization Integrated Scheduling and Memory), which co-designs a query-aware scheduler (QAS) with a demand-aware radix tree (DART) to align request admission with exact-prefix KV retention. Overall, our contributions are threefold: • We provide a bottleneck analysis that links TTFT behavior to admission wait, exact-prefix prefill work, KV pressure, and service-knee behavior on a single GPU, motivating the need to optimize scheduling and KV-cache management jointly • We introduce PRISM, which optimizes online LLM serving with request scheduling and KV-cache management co-design • The experimental results show strong performance across different datasets and models.

--- Page 5 ---

PRISM: Fast Online LLM Serving via Scheduling-Memory Co-design

2.1 LONG-PREFIX REQUESTS AS A COMMON SERVING ABSTRACTION Many online LLM services share the same structure as Eq. 1 once segments have been serialized into prompt tokens (1) where xsys is a shared system prompt, ri,j is a reusable-segment identity, mi is the number of reusable segments in qi, and xprivi is the request-specific suffix, which depends on user input (2) We refer to each identifiable reusable context piece as a segment. Second. Second accesses to these segments are often highly non-uniform and temporally local. Recent studies have shown that a small set of hot segments may recur across many requests within short windows (Wang et al., 2025; Li et al., 2025). These properties have motivated two lines of serving optimizations. Systems that optimize KV-cache memory management (Jin et al., 2026; Yao et al., 2025a; Jiang et al., 2026; Kwon et al., 2013; Zheng et al., 2014) exploit prompt structure to improve cache hit rate, while scheduling-oriented systems (Yu et al., 2013; Wu et al., 2014; Agrawal et al., 2024; Dexter et al., 2025) reorder admission and batching to place requests with shared prefix closer in time. However, optimizing scheduling and KV-cache management independently can leave substantial reuse unrealized under skewed segment arrivals. Scheduling can create prefix locality by reordering (1) but KV-cache retention should make demand-aware decisions to distinguish hot shared prefixes from cold private suffixes, which come from user input.

1. Continuous batching and chunked-prefill mechanisms can be refined by integrating a Query-Aware Scheduler (QAS) that uses segment priorities to generate order-sensitive bucket signatures, allowing requests to be grouped into hot lanes based on shared reusable segments, which directly improves KV-cache locality.

2. Demand-aware retention in the KV-cache should be implemented using a mechanism like DART, which uses dispatch-batch priority to decide anchor survival, ensuring that hot prefixes may still be evicted before the next matching request arrives is mitigated by protecting anchors with the strongest demand in the current dispatch batch.

3. The serving system can achieve higher throughput and lower tail latency by implementing a co-design where the scheduler and memory management are jointly optimized, as demonstrated by PRISM's results showing a reduction of average per-QPS P99 TTFT by 23.3% on Qwen3-4B-Instruct-2507.

4. For RAG applications, the system can exploit hotness-aware prefix sharing by aligning KV retention with admission, as PRISM achieves a higher exact-prefix KV-cache hit rate compared to baselines across different workloads.

5. Agent systems can be improved by treating components like domain policies, tool schemas, database records, and deterministic tool observations as reusable segments, allowing the scheduler to estimate their near-future demand at admission time.