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

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "HAServe: Horizon-Aware Scheduling and Memory Co-Design for Efficient LLM Serving".

Jane: The gist The PRISM architecture co-designs request scheduling and KV-cache management to optimize fast online LLM serving for segmented and skewed workloads,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper, "HAServe: Horizon-Aware Scheduling and Memory Co-Design for Efficient LLM Serving." It sounds like they're trying to fix a problem where online LLM services, especially with RAG or agent systems, have two main issues: prompt segmentation and hotspot skew.

Jane: Prompt segmentation means the text is broken into pieces, like system instructions or retrieved passages, and hotspot skew means a small set of those pieces gets used over and over again by many different requests.

Lu: They're tackling this by trying to use both request scheduling and KV-cache management together instead of doing them separately. That sounds like the core idea here.

Meng: So what does that mean in practice? Does it just make things faster, or are we looking at a fundamental shift in how we run these models at scale?

Lalam: I'm seeing that they are aiming to reduce tail latency and improve cache hit rates across RAG and agent tasks by addressing those patterns simultaneously, which is what this paper is about.

The paper's summary: Tom: The paper introduces a co-design approach involving a Query-Aware Scheduler and a Demand-aware Radix Tree for KV-cache management, which they call PRISM. This system aims to optimize fast online LLM serving by aligning request admission with exact-prefix KV retention.

Jane: That means the scheduler reorders requests based on reusable segments, and then the cache manager makes smart decisions about which parts of the KV-cache to keep when memory is tight. It’s about making sure hot shared prefixes stay in memory even under pressure.

Lu: They build a Query-Aware Scheduler that tracks reusable segment counters to generate order-sensitive bucket signatures, which helps group requests with the same segments into what they call hot lanes, improving KV-cache locality.

Meng: I like the idea of grouping requests; that sounds like it could help us manage GPU memory better when we have a skewed workload hitting our system. But how do you handle the actual decision-making when things get crowded?

Lalam: The Demand-aware Radix Tree, or DART, integrates this scheduling metadata into a KV-cache tree, using dispatch-batch priority to decide which resident KV-cache anchors should survive memory pressure, protecting those high-value shared prefixes.

The paper's improvements: Tom: One major improvement they highlight is that they provide a bottleneck analysis linking TTFT behavior to admission wait, exact-prefix prefill work, KV pressure, and service-knee behavior on a single GPU. They model performance using an approximate M/G/one queueing model <ref:2605.08581#pg1>.

Jane: That analysis shows that if the realized full-prompt token-level exact-prefix hit rate gap is non-negative, then the PRISM system's performance, measured as µPRISM, is greater than or equal to the performance of a standard LRU cache, µLRU.

Lu: The equality holds only when that exact-prefix hit rate gap is exactly zero. This suggests that for PRISM to be better than a simpler method, you need some actual reuse in the data structure.

Meng: So what are the practical results on models? Are we talking about measurable improvements in latency under real load, or just theoretical gains? I need to know how much work this actually saves us at scale.

Lalam: Experimentally, they show that PRISM reduces average per-QPS P99 TTFT by twenty-three point three percent on Qwen3-4B-Instruct-two thousand five hundred seven and by thirty-seven point one percent on Llama2-13B compared to the strongest baseline methods.

Conclusion: Tom: So, to wrap up, PRISM is a co-design between a query-aware scheduler and demand-aware KV-cache management that jointly optimizes request scheduling and memory management. This leads to significant reductions in tail latency and improvements in cache utilization across RAG and agent tasks.

Jane: It means we can achieve higher exact-prefix KV-cache hit rates, which is really important for RAG applications where you're relying on retrieving specific passages. The paper shows that the system performs well even when the reusable prefixes don't perfectly match retrieved passages, as long as demand hints are available at admission time.

Lu: The key implication is that we need to move toward a design where segment-level management tracks reusable context pieces rather than just whole requests because segments recur more often across users or sessions.

Meng: I think the practical value is seeing those measurable latency reductions, like the twenty-three point three percent on Qwen3-4B-Instruct-two thousand five hundred seven because that shows a tangible benefit for deployment performance under skewed segment arrivals.

Lalam: For agent systems specifically, they suggest treating things like domain policies or tool schemas as reusable segments so the scheduler can estimate their near-future demand at admission time. This whole HAServe work is about co-optimizing scheduling and memory to get better serving efficiency.