Co-Optimizing Request Scheduling and KV Caching for Edge LLM Serving

Abstract

Deploying large language models (LLMs) on edge nodes enables low-latency and privacy-preserving inference, but faces severe resource constraints under high-concurrence workloads. While existing inference systems leverage intranode key–value (KV) caching to improve efficiency, they largely neglect the unique complexities of multinode edge environments. Specifically, reactive KV cache eviction policies suffer from temporal uncertainty, often discarding reusable KV caches prematurely, while the tight coupling between request scheduling and cache placement often leads to myopic decisions that exacerbate load imbalance and resource contention. To address these challenges, we propose a dynamic block-level paradigm that treats KV blocks as the fundamental units for caching and scheduling, enabling dynamic sharing, generation, and eviction of arbitrary-length prefixes. We present complete modeling of the spatiotemporal coupling between scheduling and caching under block-level granularity, capturing intricate interactions overlooked by prior work. Based on this model, we design an online joint optimization algorithm, which applies to general edge LLM serving scenarios. The algorithm decouples spatiotemporal dependencies via randomized rounding over per-slot subproblems, achieving a balance between real-time responsiveness and long-term system efficiency. Theoretical analysis establishes high-probability near-optimality guarantees, and extensive experiments show that our method reduces the average time to first token (TTFT) by up to 54.02% over existing baselines.