General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing

Jul 16, 2026

Studies non-clairvoyant scheduling for batched Large Language Model (LLM) inference under a strict KV-cache memory budget, where each request’s prompt length is known but response length is unknown. During decoding, cache usage combines a fixed prompt component with a response-driven component that grows per generated token. The scheduler selects feasible active batches while eviction discards accumulated cache, wasting prior work. The method introduces the first O(1)-competitive regime-aware routing framework with constant-factor guarantees for completion time, makespan, and online arrivals.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages41

Reading Time1 h 43 min

Abstract

Introduction

arXiv :2607 .09248v 1 [ cs .DS] 10 Jul 2026 General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing 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 O(1)-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-factor guarantees for makespan and for total completion time under online arrivals. 1 Introduction Large Language Model (LLM) inference has become a cornerstone of modern computing infrastructure, supporting interactive assistants, automated workflows, and agentic applications at massive scale. As these workloads shift from short exchanges toward longer and more computation-intensive tasks, the inference phase has become a major contributor to operational cost and energy consumption [Luccioni et al. , 2024 , Stojkovic et al. , 2025a,b] . Meeting quality-of-service requirements under these resource pressures calls for careful scheduling across the serving stack, from cluster-wide request routing to the memory management logic on individual serving instances. This work focuses on replica-level scheduling inside an LLM inference service. In modern LLM serving stacks, a routing layer assigns each incoming request to one of many parallel serving instances, known as replicas; within each replica, the local scheduler decides which requests to process together and how to manage the finite memory budget [Yu et al. , 2022 , Kwon et al. , 2023 , Zheng et al. , 2024 , Sun et al. , 2024] . The central challenge arises from the Transformer architecture, whose self-attention mechanism stores intermediate states in a per-request Key-Value (KV) cache to avoid quadratic recomputation during decoding [Vaswani et al. , 2017 , Pope et al. , ∗ Hong Kong University of Science and Technology. Email: [ydfeng@ust.hk](ydfeng@ust.hk) †Shanghai Jiao Tong University. Email: [williamliusy@sjtu.edu.cn](williamliusy@sjtu.edu.cn) ‡Shanghai Jiao Tong University. Email: [fstqwq@sjtu.edu.cn](fstqwq@sjtu.edu.cn) §Shanghai Jiao Tong University. Email: zhang [yuhao@sjtu.edu.cn](yuhao@sjtu.edu.cn) 2023] . Processing a request involves a prefill phase that encodes the input prompt and initializes the cache, followed by a decode phase that generates response tokens autoregressively, appending new KV entries at each step. The memory footprint of a request therefore has a fixed component from the prompt and a component that grows linearly with the response length. Modern systems manage this dynamic growth through two mechanisms: continuous batching [Yu et al. , 2022], which updates the active batch at the granularity of individual decoding iterations, and block-based cache management [Kwon et al. , 2023 , Zheng et al. , 2024], which allocates and recycles memory across requests. When the budget is exhausted, active requests must be killed, discarding the KV-cache entries accumulated during decoding. The scheduler must therefore balance high concurrency

FAQs

What makes the scheduling problem non-clairvoyant in this work?

Response lengths are not known in advance and are only revealed after completion, while KV-cache usage grows with each decoded token.

How does KV-cache memory usage evolve during inference?

A request has a fixed cache component from the prompt and an additional component that increases linearly with the number of decoded response tokens.

What is the key idea of the proposed regime-aware routing framework?

Instead of a single universal scheduling rule, specialized sub-schedulers handle different memory-growth geometries, and a meta-scheduler time-shares the memory budget while dynamically routing each job as its behavior becomes known.

Jul 16, 2026

Upload by Seraphina