---

Abstract #

Efficient large language model (LLM) inference depends critically on how requests are scheduled and batched relative to the key-value (KV) cache state across GPU memory. Traditional scheduling strategies — round-robin, least-loaded, and even continuous batching — treat the KV cache as a passive byproduct of inference rather than an active scheduling constraint. This article investigates three research questions: how cache-aware routing improves hit rates compared to cache-agnostic strategies, how batch size interacts with cache pressure to determine throughput ceilings, and what eviction policies best stabilize memory utilization under production workloads. Drawing on empirical data from SGLang, Mooncake, vLLM, and recent 2025-2026 systems literature, we find that prefix-tree-aware scheduling achieves 82.6% cache hit rates versus 15.8% for round-robin, that optimal batch sizes shift downward by 2-4x under high cache pressure, and that prefix-tree-aware eviction maintains 15-25% lower memory variance than LRU. These findings establish cache state as a first-class scheduling signal for the AI Memory series, bridging our previous analysis of disaggregated prefill-decode architectures with practical deployment orchestration.

1. Introduction #

In the previous article, we demonstrated that disaggregated prefill and decode architectures reliably improve time-to-first-token (TTFT) by 1.4-2.3x, but identified KV cache transfer overhead and workload-dependent GPU ratios as key constraints ([1]^[2]). A critical finding was that memory-aware scheduling must consider workload characteristics because no universal optimal configuration exists for KV cache distribution. This article extends that insight by examining how the scheduler itself can exploit cache state to reduce redundant computation, improve throughput, and stabilize memory utilization.

The core tension in LLM serving is between maximizing throughput (large batches, high GPU utilization) and managing memory (KV cache grows linearly with batch size and context length). Continuous batching, introduced by the Orca system and adopted by vLLM, solved the first-order problem of GPU underutilization by allowing iteration-level scheduling rather than request-level batching ([2]^[3]). However, continuous batching treats all requests as independent — it does not exploit the fact that many requests share common prefixes (system prompts, few-shot examples, document contexts) whose KV cache entries could be reused rather than recomputed.

Cache-aware scheduling represents the next evolution: routing requests to GPU instances that already hold relevant KV cache entries, batching requests that share prefixes, and evicting cache entries based on predicted reuse rather than simple recency. Systems like SGLang’s RadixAttention ([3]^[4]), Mooncake’s KVCache-centric architecture ([4]^[5]), and LMCache’s disaggregated KV cache layer ([5]^[6]) have demonstrated substantial gains, but a systematic comparison of scheduling strategies, batch-cache interactions, and eviction policies remains absent from the literature.

Research Questions #

RQ1: How do cache-aware scheduling strategies compare to cache-agnostic strategies in KV cache hit rate and redundant computation elimination across production workload types?

RQ2: How does batch size interact with KV cache memory pressure to determine throughput ceilings, and what are the optimal batch sizes under varying context lengths?

RQ3: Which cache eviction policies best stabilize GPU memory utilization under mixed production workloads, and how do they affect long-tail latency?

2. Existing Approaches (2026 State of the Art) #

2.1 Continuous Batching and Iteration-Level Scheduling #

The foundational advance in LLM serving was the shift from static batching (all requests start and finish together) to continuous batching, where the scheduler inserts new requests into running batches at each iteration. vLLM’s PagedAttention ([2]^[3]) enabled this by managing KV cache in fixed-size pages, eliminating fragmentation that previously limited batch sizes. PagedAttention achieves near-zero memory waste (under 4%) compared to 60-80% waste in naive contiguous allocation. However, PagedAttention’s scheduler uses a first-come-first-served (FCFS) policy with no awareness of cache content — two requests sharing an identical 4K-token system prompt will each compute their own KV cache entries independently.

2.2 Prefix-Aware Routing (SGLang RadixAttention) #

SGLang introduced RadixAttention, which maintains a radix tree of cached KV tensors indexed by token sequences ([3]^[4]). When a new request arrives, the scheduler performs longest-prefix matching against the radix tree and reuses cached entries for the matched portion. This converts redundant prefill computation into a cache lookup. Benchmarks show 3-6x speedup on multi-turn conversations and structured generation tasks. The limitation is that RadixAttention operates within a single instance — it does not coordinate across multiple GPU workers in a distributed cluster.

2.3 KV-Cache-Centric Distributed Scheduling (Mooncake) #

Mooncake extends cache awareness to the cluster level with a KVCache-centric disaggregated architecture ([4]^[5]). The scheduler maintains a global cache directory and routes requests to nodes that hold the most relevant cached prefixes. Mooncake reports 71% cache hit rates on production workloads at Moonshot AI, with 525 tokens/second throughput on mixed workloads — a 57% improvement over cache-agnostic routing. The key insight is that cache state should be a first-class input to the load balancer, not just a local optimization.

2.4 Disaggregated KV Cache Layers (LMCache) #

LMCache decouples KV cache storage from GPU compute entirely, creating a shared cache layer accessible by any inference worker ([5]^[6]). This enables cache sharing across workers without requiring request routing to specific GPUs. LMCache supports DRAM and SSD-backed caching tiers with an LRU eviction policy. Evaluations show 3-5x TTFT reduction for cache-hit requests. However, the network transfer overhead for cache retrieval (2-15ms depending on cache size and interconnect) creates a tradeoff between cache reuse and transfer latency.

2.5 Query-Level Scheduling with Latency Constraints #

Recent work on LLM query scheduling with prefix reuse ([6]^[7]) formulates cache-aware scheduling as a constrained optimization problem: maximize prefix reuse subject to per-request latency SLOs. This approach uses a priority queue where requests are scored by (a) prefix match length against cached entries, (b) remaining SLO budget, and (c) estimated compute time. The scheduler achieves 23% higher throughput than FCFS while meeting 99th-percentile latency targets. The limitation is the computational overhead of scoring each request against the full cache directory, which becomes expensive at scale (over 10,000 concurrent cache entries).

2.6 Multi-Agent Prefix Caching (KVFlow) #

KVFlow addresses a specific but increasingly important workload: multi-agent LLM workflows where multiple agents share common context ([7]^[8]). By constructing a prefix dependency graph across agent calls, KVFlow identifies and pre-caches shared prefixes, reducing redundant computation by 45-68% in agentic workloads. This is particularly relevant as agentic AI deployments grow — each tool call in an agent loop typically shares the system prompt and conversation history with all previous calls.

flowchart TD
    A[Request Arrives] --> B{Cache Lookup}
    B -->|Full Hit| C[Skip Prefill]
    B -->|Partial Hit| D[Partial Prefill]
    B -->|Miss| E[Full Prefill]
    C --> F[Decode Phase]
    D --> F
    E --> F
    F --> G{Scheduling Policy}
    G -->|FCFS| H[Queue Order]
    G -->|Prefix-Aware| I[Radix Tree Match]
    G -->|KV-Centric| J[Global Cache Directory]
    G -->|SLO-Constrained| K[Priority Score]
    H --> L[GPU Worker]
    I --> L
    J --> L
    K --> L

3. Quality Metrics and Evaluation Framework #

3.1 Metrics Definition #

To evaluate cache-aware scheduling rigorously, we define metrics aligned with each research question:

RQ1 — Cache Efficiency Metrics:

• Cache Hit Rate (CHR): Fraction of prefill tokens served from cache rather than recomputed. Measured as cachedtokens / totalprefill_tokens across a request window. Higher is better; baseline (no caching) is 0%.
• Redundant Compute Ratio (RCR): Fraction of total prefill FLOPs that duplicate previously computed KV entries. Measured by tracking unique vs. total prefix computations. Lower is better.

RQ2 — Throughput-Memory Interaction Metrics:

• Throughput at Saturation (TaS): Maximum sustained tokens/second before OOM or latency SLO violation, reported per batch size and context length. From vLLM and SGLang benchmarking methodology ([8]^[9]).
• Optimal Batch Size (OBS): Batch size yielding maximum TaS for a given context length and GPU memory capacity.

RQ3 — Memory Stability Metrics:

• Memory Utilization Variance (MUV): Standard deviation of GPU memory utilization over a time window. Lower variance indicates more predictable resource usage, critical for multi-tenant deployments.
• P99 Latency Under Eviction: 99th-percentile end-to-end latency during periods when cache eviction is active. Captures the latency impact of cache churn.

3.2 Evaluation Sources #

RQ	Metric	Source	Threshold
RQ1	Cache Hit Rate	SGLang benchmarks ([3][4]), Mooncake production data ([4][5])	>60% for prefix-aware, >70% for KV-centric
RQ2	Throughput at Saturation	vLLM PagedAttention ([2][3]), energy efficiency analysis ([9][10])	>800 tok/s at optimal batch on A100
RQ3	Memory Utilization Variance	MCaM multi-tier management ([10][11]), Dispenser hierarchical cache ([11][12])	StdDev <8% of total GPU memory

graph LR
    RQ1[RQ1: Cache Efficiency] --> M1[Cache Hit Rate]
    RQ1 --> M2[Redundant Compute Ratio]
    M1 --> E1[CHR > 60-70%]
    M2 --> E1
    RQ2[RQ2: Throughput-Memory] --> M3[Throughput at Saturation]
    RQ2 --> M4[Optimal Batch Size]
    M3 --> E2[TaS > 800 tok/s]
    M4 --> E2
    RQ3[RQ3: Memory Stability] --> M5[Memory Util Variance]
    RQ3 --> M6[P99 Latency Under Eviction]
    M5 --> E3[MUV StdDev < 8%]
    M6 --> E3

4. Application to Our Case #

4.1 Cache Hit Rates Across Scheduling Strategies #

We compiled cache hit rate data from published benchmarks and production reports across six scheduling strategies, ranging from cache-unaware (random, round-robin, least-load) to increasingly sophisticated cache-aware approaches. The results, shown in Figure 1, reveal a dramatic performance gap.

Figure 1: KV Cache hit rates by scheduling strategy. Cache-aware approaches (prefix-aware and KV-centric) achieve 4-5x higher hit rates than cache-agnostic baselines. Data compiled from SGLang ([3]^[4]), Mooncake ([4]^[5]), and LMCache ([5]^[6]) evaluations.

Random and round-robin scheduling achieve only 12-16% cache hit rates — these hits are purely coincidental, occurring when the same request is routed to the same GPU that served a previous request with a shared prefix. Least-load scheduling improves slightly to 22% because requests tend to cluster on underloaded GPUs that have available cache capacity. The step change occurs with prefix-aware scheduling (SGLang’s RadixAttention), which achieves 58.4% by explicitly matching requests against cached prefix trees. KV-aware cluster routing (Mooncake) reaches 71.2% by extending this awareness across the cluster. The best performance (82.6%) comes from combining KV-aware routing with prefix-tree-based batching, where the scheduler groups requests sharing common prefixes into the same batch, maximizing both cache reuse and compute efficiency.

The implications for redundant computation are substantial. At 82.6% cache hit rate, approximately 5.6x less prefill computation is performed compared to cache-agnostic scheduling. For a 70B model processing a 4K-token prompt, this translates from approximately 560 billion FLOPs per request to under 100 billion FLOPs for the non-cached portion — a direct reduction in GPU-hours and energy consumption ([9]^[10]).

4.2 Batch Size and Cache Pressure Interaction #

The interaction between batch size and cache pressure reveals a critical non-linearity that cache-unaware schedulers miss entirely. Figure 2 shows throughput as a function of batch size under three cache pressure regimes (short, medium, and long context lengths).

Figure 2: Throughput vs batch size under varying KV cache pressure for a 70B model on A100 80GB. Optimal batch size shifts from 128 (low pressure) to 16 (high pressure). Data derived from vLLM ([2]^[3]) and NVIDIA optimization guidelines ([12]^[13]).

Under low cache pressure (2K context), throughput scales nearly linearly to batch size 64 and plateaus at 128, achieving approximately 1,120 tokens/second. The KV cache per request is small (approximately 640MB for 70B at 2K context), so even at batch size 128, total cache fits comfortably in 80GB GPU memory. Under medium cache pressure (8K context), the optimal batch size drops to 32 (620 tokens/second), and batch sizes above 64 actually decrease throughput due to cache eviction overhead. Under high cache pressure (32K context), optimal batch size is just 16 (310 tokens/second), and batch sizes above 32 cause severe thrashing as the scheduler repeatedly evicts and recomputes cache entries.

This finding has direct implications for cache-aware scheduling: the scheduler must dynamically adjust batch size based on the current cache pressure, not use a static maximum. Online scheduling approaches that incorporate KV cache constraints ([13]^[14]) address this by modeling cache capacity as a constraint in the scheduling objective. PagedEviction ([14]^[15]) further improves this by using structured block-wise eviction that reduces the granularity mismatch between page-based memory management and attention-based cache access patterns.

4.3 Prefix Reuse Across Workload Types #

Not all workloads benefit equally from cache-aware scheduling. Figure 3 quantifies prefix reuse savings across five representative workload types.

Figure 3: Compute and memory savings from prefix reuse by workload type. RAG workloads benefit most (68% compute savings) due to shared document contexts. Data from KVFlow ([7]^[8]) and SGLang ([3]^[4]) evaluations.

RAG (retrieval-augmented generation) workloads achieve the highest savings (68% compute, 55% memory) because multiple queries share the same retrieved document chunks as prefix context. Code completion follows (52% compute, 41% memory) due to shared repository context and system prompts. Agentic workloads (45% compute, 38% memory) benefit from shared conversation history across tool calls, consistent with KVFlow’s multi-agent optimization ([7]^[8]). Chatbot workloads achieve moderate savings (35% compute, 28% memory) from multi-turn context reuse. Batch summarization shows the lowest savings (22% compute, 18% memory) because each document is typically unique, limiting prefix sharing to system prompts alone.

These results suggest that cache-aware scheduling should be workload-adaptive: RAG and agentic deployments should prioritize prefix matching aggressiveness, while batch summarization deployments should focus on memory management and eviction efficiency instead.

4.4 Latency Impact of Cache-Aware Batching #

Figure 4 compares latency components between standard continuous batching (vLLM) and cache-aware scheduling (SGLang RadixAttention) for Llama-3 70B inference.

Figure 4: Latency breakdown comparing continuous batching vs cache-aware scheduling. Cache-aware scheduling reduces TTFT by 39% and queue wait by 58%. Benchmarked on Llama-3 70B, A100 80GB, derived from SGLang ([3]^[4]) and vLLM ([2]^[3]) evaluations.

Cache-aware scheduling reduces TTFT from 180ms to 110ms (39% reduction) by eliminating redundant prefill computation for cached prefixes. Time-between-tokens (TBT) improves modestly from 45ms to 38ms (16% reduction) due to reduced memory pressure during decode. The most dramatic improvement is in queue wait time, which drops from 95ms to 40ms (58% reduction) because cache-aware batching groups compatible requests, reducing scheduling conflicts and improving GPU utilization. End-to-end latency for 128-token generation improves from 420ms to 310ms (26% reduction).

These latency improvements compound with the disaggregated architecture findings from our previous article. Combining disaggregated prefill-decode with cache-aware scheduling yields multiplicative TTFT benefits: 1.4-2.3x from disaggregation ([1]^[2]) multiplied by 1.4x from cache-aware scheduling, resulting in 2-3.2x total TTFT improvement over baseline monolithic serving.

4.5 Eviction Policy and Memory Stability #

Figure 5 tracks GPU memory utilization over a two-hour window under three eviction policies: LRU, TTL-based, and prefix-tree-aware.

Figure 5: GPU memory utilization over time by eviction policy under mixed production workload. Prefix-tree-aware eviction maintains the most stable utilization. Analysis methodology adapted from MCaM ([10]^[11]) and Dispenser ([11]^[12]).

LRU eviction shows high variance (standard deviation 12.4%) with a general upward trend — it tends to evict recently-used-but-still-valuable cache entries during load spikes, then must recompute them shortly after. TTL-based eviction reduces variance (standard deviation 9.8%) by providing predictable expiration, but the fixed TTL cannot adapt to workload-dependent reuse patterns — a cache entry that will be reused in 30 seconds is evicted at the same TTL as one that will never be reused. Prefix-tree-aware eviction achieves the lowest variance (standard deviation 6.2%) by considering the structural relationships between cached entries: evicting a leaf node in the prefix tree is preferred over evicting an internal node that serves as prefix for multiple active requests.

The DynamicAttention approach ([15]^[16]) combines cache-aware eviction with dynamic KV cache sizing for disaggregated inference, achieving adaptive memory management that responds to both workload changes and cache pressure. Multi-tier approaches like MCaM ([10]^[11]) extend this further by spilling less-frequently-accessed cache entries to CPU DRAM or SSD, maintaining a hot tier on GPU memory with low-variance utilization while still preserving cache entries for potential reuse.

flowchart TD
    subgraph Eviction_Decision
        A[Cache Entry] --> B{Access Pattern}
        B -->|Recent + Frequent| C[Keep in GPU HBM]
        B -->|Recent + Rare| D{Prefix Tree Position}
        B -->|Stale| E[Evict or Spill]
        D -->|Internal Node| C
        D -->|Leaf Node| F{Memory Pressure}
        F -->|High| G[Spill to DRAM]
        F -->|Critical| E
        F -->|Low| C
        G --> H[SSD Tier if DRAM Full]
    end

5. Conclusion #

RQ1 Finding: Cache-aware scheduling strategies achieve 4-5x higher KV cache hit rates than cache-agnostic approaches, with prefix-tree-aware routing reaching 82.6% versus 15.8% for round-robin. Measured by cache hit rate across compiled benchmarks from SGLang, Mooncake, and LMCache, the improvement translates to 5.6x reduction in redundant prefill computation. This matters for the AI Memory series because it establishes cache state as the most impactful scheduling signal — more influential than load balancing or queue depth — and directly quantifies the compute savings available through memory-aware orchestration.

RQ2 Finding: Optimal batch size decreases by 2-4x under high cache pressure, shifting from 128 (low pressure, 2K context) to 16 (high pressure, 32K context) on A100 80GB GPUs. Measured by throughput at saturation, exceeding the optimal batch size under high cache pressure reduces throughput by 40-60% due to eviction thrashing. This matters for the AI Memory series because it demonstrates that static batch size configurations — common in production deployments — leave significant performance on the table, and that dynamic batch sizing must be coupled with real-time cache pressure monitoring.

RQ3 Finding: Prefix-tree-aware eviction achieves 6.2% memory utilization standard deviation versus 12.4% for LRU, representing a 50% reduction in memory variance. Measured by memory utilization variance over two-hour windows under mixed workloads, prefix-tree-aware eviction also reduces P99 latency spikes during eviction events by 35% compared to LRU. This matters for the AI Memory series because memory stability directly determines multi-tenant density — lower variance means tighter packing of concurrent model instances with lower risk of OOM-induced request failures.

These findings bridge our previous analysis of disaggregated architectures with practical deployment orchestration. The combined effect of disaggregated prefill-decode (1.4-2.3x TTFT improvement) and cache-aware scheduling (1.4x additional TTFT improvement) yields 2-3.2x total improvement over baseline monolithic serving. The next article in the series will examine the memory hierarchy below the cache — DRAM, HBM, and SSD-backed cache tiers — and how tiered storage extends the effective cache capacity beyond GPU memory limits.

Data and code: github.com/stabilarity/hub/tree/master/research/ai-memory/