Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference
Yiding Feng, Zonghan Yang, Yuhao Zhang · 2026
Read Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference by Yiding Feng, Zonghan Yang, Yuhao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22996.txt.
Introduction
Yiding Feng, Zonghan Yang, and Yuhao Zhang schedule the memory that language models use while answering. That memory, the KV cache, grows with every token a model writes. A scheduler must cut waiting time under a hard memory cap, yet reply lengths are unknown in advance.
That non-clairvoyant setting is the core difficulty: choices must be made without knowing job sizes. The authors study competitive scheduling rules for this setting. Better cache scheduling means cheaper, faster service for chatbots and coding tools. The hard memory budget is non-negotiable at serving time, so schedules must stay feasible even when lengths surprise.
Catalog record
| CREATOR | Yiding Feng, Zonghan Yang, Yuhao Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-22996
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference Yiding Feng, Zonghan Yang, Yuhao Zhang Abstract 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 decoded tokens. This growth couples scheduling decisions with feasibility: a scheduler must minimize latency under a hard memory budget, yet the response lengths of requests are inherently unknown. While recent works have explored this problem either assuming clairvoyance—exact knowledge of response lengths—or relying on machine-learned predictions, obtaining robust performance guarantees without any prior knowledge of job sizes remains a theoretically fundamental and practically important open problem. In this work, we propose the Geometric Slicing Algorithm (GSA), the non-clairvoyant policy to achieve the first constant competitive ratio for this problem in the offline batch setting . GSA manages uncertainty through a geometric phase structure that periodically restarts jobs to bound memory exposure, combined with a staggered pipeline mechanism that enables high concurrency by smoothing aggregate memory consumption. We prove that GSA achieves a competitive ratio of at most 61.92 61.92 for general instances, improving to 32 32 in the large-memory regime. Our algorithmic framework also yields a clairvoyant counterpart, the Geometric Batching Algorithm (GBA), which achieves an approximation ratio of 10.67 10.67 for general instances and 6.75 6.75 in the large-memory regime—significantly improving upon the best previously known bound of over 9000 9000 . Numerical experiments on real request traces demonstrate that our algorithms perform robustly while preserving these worst-case guarantees. keywords KV-cache, non-clairvoyant scheduling, approximation algorithm, combinatorial optimization † † runningauthor: Feng, Yang, Zhang † † runningtitle: Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference † † authors: Hong Kong University of Science and Technology, China, [email protected] Shanghai Jiao Tong University, China, [email protected] Shanghai Jiao Tong University, China, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction Figure 1 : The diagram illustrates the LLM inference process flowing from top to bottom. First, the user message is tokenized. Next, the prefill phase processes the prompt to generate the first decode token. Then, the decode phase generates output tokens auto-regressively until the End-Of-Sequence token. Note that the KV-cache (colored context) grows linearly with each step. Large Language Models (LLMs) have emerged as the cornerstone of modern AI, powering chat assistants, search engines, and developer tools ( Brown et al. 2020 ; OpenAI 2023 ; Microsoft 2023 ; Google 2024b ) . While training remains a massive undertaking, the inference phase increasingly dominates operational costs—a trend amplified by the rise of reasoning-enhanced models that trade extensive Chain-of-Thought computation for improved capabilities ( Wei et al. 2022 ; Jaech et al. 2024 ; Guo et al. 2025 ) . These escalating resource demands strain deployment infrastructure significantly, impacting not only capital expenditures but also environmental sustainability ( Strubell et al. 2019 ; Luccioni et al. 2024 ; Li et al. 2025a ) . Consequently, optimizing system efficiency without compromising quality-of-service requirements—such as latency—has become an operational imperative. Virtually all foundation LLMs are built upon the Transformer architecture ( Vaswani et al. 2017 ) , whose self-attention mechanism computes dependencies across input tokens. To avoid quadratic recomputation at each decoding step, modern inference systems universally employ a Key-Value (KV) cache to store intermediate attention states ( Kwon et al. 2023 ; Zheng et al. 2024b ; Hooper et al. 2024 ) . While this optimization reduces computational complexity to linear time, it introduces a critical resource trade-off: execution progress becomes tightly coupled with GPU memory consumption. This coupling has shifted attention toward systems-level optimization, especially KV-cache management. As illustrated in Figure 1 , when a user request arrives, it is tokenized and processed by the LLM in two phases. The decode phase then produces subsequent tokens auto-regressively, appending a new KV pair to the cache for each generated token. Consequently, the memory footprint of a request is not static but grows linearly with its response length. This dynamic memory growth—where a request’s memory footprint increases linearly with its accumulated processing time—introduces a first fundamental challenge for LLM inference scheduling: temporal coupling between concurrency and feasibility . Unlike classical scheduling models that assume static resource requirements, the KV cache in LLMs expands as decoding progresses. Consequently, a batch of jobs that fits within memory at the start of execution may inevitably violate memory constraints later. This forces the scheduler to balance high concurrency against the risk of memory overflows, which trigger costly preemptions under kill-and-restart semantics—the core tension in efficient LLM serving. Compounding this issue is a second critical challenge: non-clairvoyance . Because termination is governed by model-generated stop conditions rather than an externally specified job size, the final response length is not determined a priori and only gradually reveals itself during execution. 1 1 1 Some practical systems introduce response-length predictors to inform batching, admission control, or memory reservation. However, these predictors provide only noisy, workload-dependent estimates rather than oracle knowledge, and they lack guarantees that would eliminate non-clairvoyance ( Zheng et al. 2023 ; Jin et al. 2023 ; Fu et al. 2024 ) . This direction has been explored in recent prior work ( Chen et al. 2025 ) . See more discussion in related work ( Section 1.3 ). This uncertainty renders the processing time of each job unpredictable until completion, placing the problem squarely in the non-clairvoyant setting of classical scheduling theory. The lack of foresight harms average latency, as traditional clairvoyant strategies become brittle. Moreover, because the KV cache grows dynamically with generated tokens, uncertainty in response length directly translates into uncertainty in future memory footprints—a difficulty absent in classical models. Thus, the scheduler must simultaneously manage both temporal resource coupling and incomplete information, navigating a doubly constrained trade-off between latency and memory safety. Motivated by these challenges and the critical importance of efficient LLM inference scheduling, we ask: Can we design effective batching policies for LLM inference requests that remain robust to the risk of infeasibility caused by dynamic memory growth, even in non-clairvoyant environments? To address this question, we adopt the offline batch scheduling model studied in recent literature ( Jaillet et al. 2025 ; Wang et al. 2025 ; Chen et al. 2025 , e.g.,) . In this model, all inference requests arrive simultaneously at time zero and are processed on a single GPU under a hard KV-cache memory budget. Each request consists of a fixed-length prompt followed by an unknown number of output tokens (i.e., response length) generated autoregressively, creating a non-clairvoyant environment. Since our focus is exclusively on scheduling the decode phase, the prefill phase---which initializes the KV cache from the prompt and generates the first token---is assumed to be completed in a single time step (i.e., the duration of decoding one token) 2 2 2 This assumption is justified as practical systems often handle the prefill phase separately via prefill/decode disaggregation ( Zhong et al. 2024 ; Choukse et al. 2025 ) . . During decoding, a request’s memory footprint grows linearly with its progress: each generated token appends to the KV cache, increasing total memory consumption. At every round, the scheduler must decide which subset of unfinished requests to process