3 papers
cs.DS2026
General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing
Yiding Feng, Siyu Liu, Zonghan Yang +1
We study non-clairvoyant scheduling for batched Large Language Model (LLM) inference under a hard Key-Value (KV) cache memory budget. Each request has a known prompt length but an…
cs.DS2026
Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
Yutong Geng, Enze Sun, Zonghan Yang +1
This paper studies the online scheduling problem of minimizing total flow time for jobs on identical machines. A classical lower bound shows that no deterministic s…
cs.DS2026
Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference
Yiding Feng, Zonghan Yang, Yuhao Zhang
Large Language Model (LLM) inference presents a unique scheduling challenge due to the Key-Value (KV) cache, where a job's memory footprint grows linearly with the number of decode…