General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing
2026-07-10 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to schedule multiple LLM requests in batches when the total memory for caching is limited and the response lengths of requests are unknown. Each request uses fixed memory for the prompt and increasing memory as its response grows during decoding. They design an algorithm that works without knowing response lengths ahead of time and achieves good performance compared to an ideal scheduler that does. Their method uses different specialized schedulers for different memory usage patterns and a meta-scheduler to allocate memory and route jobs dynamically as more information becomes available.
non-clairvoyant schedulingLLM inferencebatch schedulingKey-Value cachememory budgetcompletion timeclairvoyant schedulingmakespanonline algorithmmeta-scheduler
Authors
Yiding Feng, Siyu Liu, Zonghan Yang, Yuhao Zhang
Abstract
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 unknown response length, and its memory footprint comprises a fixed prompt component together with a response component that grows with each decoded token. At each decoding round, the scheduler chooses a feasible batch of active requests; evicting a request discards its accumulated cache states, wasting prior computation. The goal is to minimize total completion time against the optimal clairvoyant schedule that knows all response lengths. We present the first constant-competitive algorithm for arbitrary prompt lengths and arbitrary response lengths with no additional assumptions. Rather than relying on a single universal scheduling policy, our algorithm is built on a novel regime-aware routing framework. Specialized sub-schedulers handle different memory-growth geometries, while a meta-scheduler time-shares the memory budget across them and dynamically routes each job as its execution progressively reveals its behavior. This framework also yields constant-competitive guarantees for makespan and for total completion time under online arrivals.