RPSC: Robust LLM Scheduling by Tolerating Prediction Inaccuracy and Mitigating Tail Latency

High-concurrency LLM serving requires inference systems to balance execution efficiency with stringent performance guarantees. While Shortest Remaining Processing Time (SRPT) is theoretically optimal for minimizing average job completion time, its practical application is hindered by the autoregressive nature of generative inference. Specifically, inherent length prediction inaccuracies trigger frequent, redundant preemptions, leading to excessive KV Cache swapping and recomputation penalty. Moreover, strict SRPT scheduling inherently sacrifices tail latency, failing to meet consistent SLOs. We first establish an analytical system model to characterize LLM inference through task execution states, compute and memory constraints, and preemption penalty, providing a theoretical foundation for analyzing performance trade-offs. Based on this foundation, we propose Resident Protection & Sojourn Compensation (RPSC), a robust scheduling algorithm designed to tolerate prediction inaccuracy and mitigate tail latency. RPSC introduces two synergistic mechanisms: (1) Resident Protection (RP), which shields running tasks from inaccuracy-driven preemptions to minimize redundant KV Cache swapping and recomputation overhead; and (2) Sojourn Compensation (SC), which dynamically reconciles the priority distribution based on sojourn time to prevent starvation and mitigate tail latency. Experimental results demonstrate that RPSC reduces redundant preemptions by 33.6% and improves P99 JCT by 20.3% compared to SRPT. Our work provides an efficient and robust solution for managing high-concurrency inference workloads in production environments.