Speaker: Yiding Feng 助理教授，香港科技大学

Inviter: 王长军

Title: When Jobs Grow as They Run:Non-Clairvoyant Scheduling for LLM Inference

Language: English

Time & Venue: 2026.09.03 10:30-11:30 N602

Abstract: We study non-clairvoyant scheduling for batched large language model inference under a hard Key-Value (KV) cache memory constraint. Each request has a known prompt length and an unknown response length. During decoding, its memory usage grows linearly with its accumulated processing, and evicting an active request discards its progress. Our objective is to minimize total completion time relative to the optimal clairvoyant schedule.

Our starting point is a memory-time area interpretation of KV-cache consumption. In the identical-prompt setting, this perspective leads to a geometric slicing algorithm that combines staggered execution with geometrically increasing time budgets. Staggering smooths the aggregate memory profile, while geometric slicing limits the computation lost through restarts. Together, these ideas yield an explicit constant competitive ratio and substantially improved approximation guarantees in the clairvoyant setting.

For heterogeneous prompt lengths, a single global priority rule is insufficient: prioritizing small jobs can cause severe memory underutilization, whereas prioritizing large jobs can delay many short requests. We therefore decompose requests into large, prompt-heavy, and response-heavy regimes. Each regime is handled by a specialized non-clairvoyant scheduler, and a routing meta-scheduler dynamically transfers requests between regimes as their unknown response lengths are progressively revealed. This establishes the first constant-competitive algorithm for arbitrary prompt and response lengths, with extensions to makespan and online arrivals.

This talk is based on joint work with Siyu Liu, Zonghan Yang, and Yuhao Zhang.