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 [1]–[3]. 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 [4]–[7]. 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 [8], [9]. 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 [4], which updates the active batch at the granularity of individual decoding iterations, and block-based cache management [5], [6], 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, which improves throughput, against the cost of kills that waste prior computation.

This tension is compounded by a second critical difficulty: the scheduler is non-clairvoyant. Response lengths are not known in advance but are determined by the model’s generation process and revealed only at completion. The autoregressive and stochastic nature of text generation makes exact prediction inherently impossible, even with dedicated predictors [10]–[12]. In classical non-clairvoyant scheduling, a job of unknown size occupies a fixed amount of resource whenever it runs; here, uncertainty in response length directly translates into uncertainty in future memory demand, because the cache grows with every decoded token. The scheduler must therefore manage dynamically growing resource requirements under incomplete information—a doubly constrained trade-off between latency and memory safety.

This places the problem in the non-clairvoyant setting of scheduling theory [13], [14], with the additional feature that the resource demand of a job increases during its execution. For this problem, a recent line of theoretical work [15]–[19] has established guarantees for the single-replica model under restricted regimes, such as clairvoyant scheduling, identical prompt lengths, or large-memory settings. Removing these restrictions, we ask:

Can a non-clairvoyant scheduler perform comparably to the optimal schedule computed with full knowledge of all response lengths?

To make this question concrete, we adopt the standard offline batch model studied in recent theoretical work on LLM inference scheduling [16]–[19]. A single serving instance, or replica, has a hard memory budget \(M\). A set of jobs (inference requests) arrives at time zero. Each job has a known prompt length \(s_i\) and an unknown response length \(o_i\). Time proceeds in discrete rounds. In each round, the scheduler chooses a batch of unfinished jobs to process; every job in the batch decodes one token. The memory consumed by a job equals its prompt length plus the number of tokens it has already decoded in its current uninterrupted attempt. The total memory of all active jobs must not exceed the budget \(M\). The scheduler may also kill an active job, discarding all progress from that attempt and forcing a restart. The objective is to minimize total completion time—the sum of the completion times of all jobs—measured against an optimal clairvoyant schedule that knows all response lengths in advance. A non-clairvoyant algorithm is competitive if its total completion time is at most a constant factor times this optimum on every instance.

Compared to classical non-clairvoyant scheduling, the defining feature of our model is that resource demands are dynamic rather than static. A batch that is feasible at the start of a round may become infeasible as its members grow, forcing the scheduler to kill jobs to free memory or to run fewer jobs in parallel.

1.1 Our Results and Techniques↩︎

We answer the aforementioned question affirmatively. In a nutshell, we give the first constant-competitive non-clairvoyant scheduling algorithm for the offline batch model with arbitrary prompt lengths and arbitrary response lengths, requiring no additional assumptions on the problem instances. Formally, our main result is as follows.

Beyond satisfying the competitive guarantee stated in the theorem, our algorithm runs in polynomial time and is also constant-competitive for the alternative objective of makespan.⁵

In the remainder of this section, we give an overview of the key challenges and the main technical ingredients of our algorithm: regime decomposition, which partitions jobs into geometric regimes; budget-doubling, which handles unknown response lengths within each regime; and a routing meta-scheduler, which combines the regimes with only constant-factor overhead.

  A natural starting point is the clairvoyant setting, where the scheduler knows all response lengths in advance. Following prior work [18], we define the (memory-time) area of a job as its total memory occupation over a successful run, i.e., \(A_{i}\triangleq s_i\cdot o_i + o_i(o_i+1)/2\). Below, we refer to memory-time area simply as area. Note that the optimal total completion time can be lower bounded by sorting all jobs by nondecreasing area and charging each job for the cumulative area that must be supplied before it can finish: the \(r\)-th smallest job cannot complete before the system has delivered the total area of the first \(r\) jobs, which takes time proportional to the sum of their areas divided by the memory budget (see 1). This bound holds because the system can supply at most \(M\) units of memory-time area per round, so the aggregate area of all jobs must be paid for in time.

The area lower bound not only provides a tractable way to characterize the optimal clairvoyant benchmark; more importantly, it also suggests a sufficient condition for a constant approximation or competitiveness:

• (High memory utilization) the schedule should keep a constant fraction of the memory occupied; and

• (Area-order completion) the completion order should be close to nondecreasing memory-time area order.

One might hope to achieve both with a single priority rule over job types—for example, greedy scheduling by area.⁶ Indeed, all known non-clairvoyant algorithms in the related restart and KV-cache scheduling models, and the majority of clairvoyant KV-cache scheduling algorithms, derive their schedules from a global ordering criterion [15], [17]–[20]. However, we show that this is impossible even with full knowledge of all response lengths in 1. The obstruction has two complementary forms. If the scheduler prioritizes small-area jobs, it may leave the memory severely underutilized while a long small-prompt job monopolizes the batch. If it prioritizes large-area jobs, it may block many small-area jobs behind a few large-prompt jobs that must run serially. These two failure modes impose opposite pressures: high utilization and area-consistent ordering cannot be reconciled by one global priority. This motivates a decomposition into geometric regimes that are treated separately.

We partition the jobs using a prompt cutoff \(\Lambda= M/4\) into three regimes:

• (Large jobs) \(s_i > \Lambda\). These jobs are so wide that each one nearly fills the memory budget alone.

• (Small prompt-heavy jobs) \(s_i \le \Lambda\) and \(o_i \le s_i\). The response is no longer than the prompt, so the memory footprint stays within a constant factor of the prompt length.

• (Small response-heavy jobs) \(s_i \le \Lambda\) and \(o_i > s_i\). The memory footprint grows well beyond the prompt, and the area is dominated by the response length.

This three-way partition is the regime decomposition used by the algorithm: jobs are classified by their geometric properties and sent to distinct scheduling pipelines, each specialized to a particular memory-growth profile.

Each regime, taken in isolation, admits a constant-competitive non-clairvoyant algorithm, which we describe in the next two parts. The remaining challenge is that the non-clairvoyant scheduler does not know which regime a job belongs to, because the distinction between prompt-heavy and response-heavy depends on the unknown response length. We explain how to resolve this difficulty when we discuss the meta-scheduler below.

  For large jobs and prompt-heavy jobs, the KV-cache footprint grows by at most a constant factor during execution. Specifically, if \(o_i \le s_i\), then the memory usage at every timestep lies between \(s_i + 1\) and \(2s_i\). This allows us to abstract each job as a rectangle of fixed width \(w_i\triangleq 2s_i\) and unknown processing time \(p_i\triangleq o_i\), where killing an active attempt discards all progress.⁷ To our knowledge, this non-clairvoyant version of rectangle strip scheduling has not been studied in the literature, and our results here may be of independent interest.

Our scheduler \(\mathrm{\mathrm{\small Rect}}\) ([alg:rectangle-strip]) maintains a priority queue of attempts ordered by their area budget \(w_i \cdot 2^r\), where \(2^r\) is the geometrically increasing length cap for the \(r\)-th attempt of job \(i\). At each event time, the scheduler greedily admits the minimum-budget attempt if it fits in the remaining memory. If an attempt reaches its cap without completing, it is killed and replaced by a doubled attempt, which is added back to the priority queue with the updated area budget.

The analysis rests on a queue monotonicity (4): the minimum area budget among pending attempts is weakly increasing over time, and every active attempt has area budget no larger than every pending attempt. This invariant lets us split the completion time of each job into active time and waiting time. The active time—the total time during which some (possibly unsuccessful) attempt of job \(i\) is executing, so that no attempt of that job is waiting in the queue—is bounded by \(4p_i\) because the geometric caps up to and including the first successful one sum to less than \(4p_i\). The waiting time—the total time during which an attempt of job \(i\) is in the priority queue—is controlled by a utilization bound: when all rectangle widths lie in a bounded range \([\delta, \Delta]\), every waiting round has active memory of at least \(\max\{\delta, M-\Delta\}\). For large jobs, \(\delta= 2\Lambda= \Omega(M)\), so utilization is constant, as desired; for prompt-heavy jobs, \(\Delta= 2\Lambda\), and utilization is at least \(M- 2\Lambda= \Omega(M)\), again as desired. Moreover, the queue monotonicity ensures that the completion order approximately follows the area order. Consequently, the scheduler \(\mathrm{\mathrm{\small Rect}}\) ([alg:rectangle-strip]) is \(36\)-competitive when all jobs are large, and also when all jobs are small prompt-heavy.

Remarkably, even a few small response-heavy jobs suffice to break the guarantee: memory may still be well utilized, but jobs can now finish in the wrong order—with large-area jobs completing before small-area ones—because the queue monotonicity no longer holds. This ordering failure makes the competitive ratio unbounded.

  When the response length dominates the prompt, the memory footprint grows far beyond the prompt length, so the fixed-width rectangle view no longer applies. Instead, the area of a response-heavy job is governed by its response length: for each job \(i\), the area \(A_{i}\triangleq s_i\cdot o_i + o_i(o_i+1)/2\) lies between \(o_i^2/2\) and \(2o_i^2\). Thus response-length order and area order agree up to a constant factor.

We handle these jobs with a scheduler \(\mathrm{\mathrm{\small Response}}\) ([alg:response-heavy]) that extends the geometric-slicing approach of [18] from identical to non-identical prompt lengths. The algorithm proceeds in phases \(r= 0, 1, \dots\) with geometrically increasing response caps \(\tau_{r} = 2^{r}\). In each phase, every unfinished job with \(s_i \le \tau_{r}\) becomes eligible. All eligible jobs are then scheduled using the SPS (Staggered Pipeline Scheduling) subroutine of [18], which packs jobs with identical prompt and response lengths into a high-utilization batch. We invoke SPS by treating all eligible jobs as sharing a common proxy prompt \(\bar{s}_{r} = \min\{\tau_{r}, M-\tau_{r}\}\) and the current cap \(\tau_{r}\) as their common response length.

The key insight is that within a phase, the shared proxy prompt lets SPS guarantee high memory utilization. Moreover, since the caps grow geometrically, each job completes in the first phase whose cap exceeds its true response length. This means the completion order induced by the phases approximately follows the response-length order, which in this regime is close to the area order. Consequently, the scheduler is \(236/3 \approx 78.67\)-competitive when all jobs are response-heavy.

Remarkably, even a few prompt-heavy jobs are enough to break the guarantee. If we keep the same phase-based eligibility (i.e., admitting a job whenever its prompt fits under the current response cap), the SPS schedule can leave memory underutilized because prompt-heavy jobs consume far less cache than their proxy length suggests. In addition, response-length order and area order can diverge dramatically for such jobs: a short-response job with a long prompt may have large area, while a long-response job with a short prompt may have small area. Either mismatch alone makes the competitive ratio of our scheduler \(\mathrm{\mathrm{\small Response}}\) ([alg:response-heavy]) unbounded.

  So far, we have described separate schedulers for large jobs, small prompt-heavy jobs, and small response-heavy jobs. From an engineering perspective, if we had three replicas—each with its own memory budget of \(M\)—we could route each regime to a dedicated replica and immediately obtain an \(O(1)\)-competitive guarantee, provided the jobs were partitioned correctly. The remaining challenge is to achieve the same guarantee on a single replica, without knowing the partition in advance.

If the three-way partition were known, we could combine the sub-schedulers via a black-box meta-scheduler. The meta-scheduler \(\mathrm{\mathrm{\small BlackBoxMeta}}\) ([alg:black-box-meta]) runs the sub-schedulers in round-robin order over doubling stages of length \(2^r\). Each sub-scheduler receives a fresh copy of its job set in each of its allotted rounds. Completed jobs are treated as dummy jobs in later stages. A per-job completion bound shows that this time-sharing loses only a constant factor relative to running each sub-scheduler in isolation.

In the non-clairvoyant setting, however, the partition is not known: for a job with small prompt, the scheduler cannot tell whether \(o_i \le s_i\) or \(o_i > s_i\) without running it. We therefore use a routing meta-scheduler \(\mathrm{\mathrm{\small Route}}\) ([alg:white-box-meta]). Small jobs are initially assigned to the prompt-heavy branch. If a job completes before generating \(s_i\) tokens, it is finished; if it reaches \(s_i\) tokens without completing, it is certified as response-heavy and routed to the response-heavy branch. Large jobs are sent directly to the large-job branch.

The routing meta-scheduler uses the same doubling stages as the black-box version. In each stage, it runs the prompt-heavy branch, then the response-heavy branch (which now includes any newly certified jobs), then the large branch. The key observation is that a job certified in the prompt-heavy branch during stage \(r\) is available to the response-heavy branch in the same stage, and the doubling lengths ensure that both certification and completion are accommodated within a constant factor of their isolated completion times (11). Combining the three branch guarantees yields the final \(O(1)\)-competitive guarantee for all instances with arbitrary prompt lengths and arbitrary response lengths stated in [thm:main].

  Beyond our main non-clairvoyant result stated in [thm:main], we establish several complementary guarantees using our algorithmic framework to chart the broader landscape of KV-cache scheduling. First, in the clairvoyant setting, our framework yields a \(16\)-approximation algorithm for all instances with arbitrary prompt lengths and arbitrary response lengths (4), and a \((3+o(1))\)-approximation for the large-memory regime where every job satisfies \(s_i + o_i = o(M)\) (2).⁸ Second, the same routing algorithm yields an \(O(1)\)-competitive ratio for the makespan objective (6), showing that the structural benefits of regime decomposition extend beyond total completion time. Third, we extend our results to online arrivals, where jobs arrive over time and reveal their prompt lengths upon arrival: we give an online variant of our routing meta-scheduler that remains \(O(1)\)-competitive for total completion time (7).⁹

  Modern LLM inference systems already allow global request routing across different replicas. Our results provide a principled foundation for how this routing should be done: partition jobs according to their geometric structure—large jobs, small prompt-heavy jobs, and small response-heavy jobs. This partition can be implemented at the global router level, where prompt lengths are known and response-based classifications can be updated dynamically as execution reveals job behavior. Once jobs are routed to separate replicas, each local scheduler can simply run the corresponding sub-scheduler from our framework. This avoids the overhead of the theoretical meta-scheduler, which must time-share a single memory budget across heterogeneous classes. Consequently, such an implementation achieves a better competitive ratio than the single-replica theoretical bound, while remaining easy to deploy.

The geometric regime decomposition explains why the existing separation between routing and local scheduling is algorithmically useful. Simple local rules, properly routed by geometric class, can achieve both worst-case robustness and practical efficiency.

1.2 Organization↩︎

2 defines the scheduling model and develops an area-based lower bound on the optimal completion time. 3 classifies jobs into three regimes—large, prompt-heavy, and response-heavy—and motivates treating them separately through explicit hard instances. 4 gives the rectangle scheduler \(\mathrm{\mathrm{\small Rect}}\) ([alg:rectangle-strip]), which handles large and prompt-heavy jobs by exploiting their nearly constant memory footprint, while 5 gives the response scheduler \(\mathrm{\mathrm{\small Response}}\) ([alg:response-heavy]), which handles the growing footprint of response-heavy jobs through area-geometric slicing with doubling response caps. 6 presents the black-box meta-scheduler \(\mathrm{\mathrm{\small BlackBoxMeta}}\) ([alg:black-box-meta]) that time-shares the memory budget across independent sub-schedulers, and extends it to the routing meta-scheduler \(\mathrm{\mathrm{\small Route}}\) ([alg:white-box-meta]) that resolves the unknown job partition during execution, completing the proof of [thm:main]. Finally, [sec:clairvoyant,sec:rectangle-strip-complete,sec:response-heavy-constant,sec:alternative-objectives] contain the clairvoyant approximation guarantees, deferred analyses for the rectangle and response-heavy schedulers, and extensions to makespan and online-arrival completion time.

1.3 Related Work↩︎

  [15] initiate the theoretical study of KV-cache scheduling for LLM inference by formulating the scheduling model, proving an \(\Omega(\sqrt{n})\) lower bound for deterministic algorithms under adversarial online arrivals, and giving the Memory-Constrained Shortest-First rule which achieves a \(9216\)-approximation in the offline identical-prompt clairvoyant setting. In the clairvoyant setting, [16] study the large-memory regime with heterogeneous prompt and response lengths and give a polynomial-time \((48+\varepsilon)\)-approximation for any fixed \(\varepsilon>0\). Recently, concurrent work by [19] improves the approximation ratio for the clairvoyant large-memory regime to \(3+o(1)\). For non-clairvoyant settings, [17] study scheduling under output-length uncertainty and give an \(O(\log M)\)-competitive algorithm in the large-memory regime. [18] give a non-clairvoyant geometric-slicing algorithm for the identical-prompt offline batch model, with a competitive ratio of at most \(61.92\) in general and \(32\) in the large-memory regime. Parallel lines of work [23], [24] study stochastic arrivals through fluid-guided online scheduling and queueing-throughput viewpoints with different optimization objectives.

  Classical non-clairvoyant scheduling is mainly studied in a preemptive pause-and-resume model, where processing times are unknown until completion and a suspended job keeps its completed work. [13] introduced this model and gave deterministic and randomized upper and lower bounds; [14] developed randomized multilevel-feedback algorithms for total flow time on single and parallel machines. Later variants add limited side information, including approximate processing-time classes [25], job-size predictions [26], predictions for only a subset of jobs [27], and progress-bar feedback [28]. [29] introduce the packing/polytope scheduling framework, where active jobs receive processing rates subject to packing constraints on the rate vector, and give non-clairvoyant algorithms including a constant-competitive guarantee for total weighted completion time. [30] sharpen the proportional-fairness analysis for this framework, including important monotone special cases, under the same total weighted completion-time objective.

Another line of research studies restart models, where interrupting a job destroys its accumulated progress. In clairvoyant online settings, restarts have been studied for single-machine total completion time and for completion-time and flow-time lower bounds [31], [32]. [20] study single-machine scheduling with a weighted completion-time objective in a non-clairvoyant restart model, prove lower bounds for deterministic restart strategies, and give tight analyses for geometric restart strategies.

  Total and weighted completion time are central min-sum objectives in scheduling. For the basic single-machine weighted case, [33] gives an exact ordering principle by sorting jobs according to processing time per unit weight. For richer machine environments, [34] develop general offline and online approximation techniques for completion-time objectives, using linear-programming relaxations to guide list scheduling. [35] give ordering and rounding methods for average completion time with release dates, parallel machines, and precedence constraints; their algorithms derive an order from a preemptive or linear-programming relaxation and round it into a nonpreemptive schedule. More recently, [36] shows the strength of time-indexed linear-programming relaxations for total weighted completion time, including precedence-constrained machine scheduling; using completion-time structure as a guide, [37] give a gradient-descent meta-algorithm based on the residual weighted completion-time optimum and obtain scalable algorithms for weighted flow time.

  The memory-time view represents executions as growing geometric regions packed under a fixed memory width. The KV-cache regions in this model are trapezoidal, while related geometric-packing literature studies rectangles and more general polygons, often with objectives such as the number of bins or the strip length. [21] survey two-dimensional packing models, including bin packing and strip packing variants. [38] prove APX-hardness for strip packing, including the case with polynomially bounded input data. [39] gives a \(2\)-approximation for rectangle strip packing. [40] give a \((3+\epsilon)\)-approximation for maximum-profit rectangle packing in a bounded rectangle. More general polygon packing has also been studied: [41] give approximation algorithms for packing convex polygons into minimum-area containers, and [42] improve approximation guarantees for translational packing of convex polygons, including polygon strip packing.

Resource-constrained scheduling gives a closely related strip view: a job with processing time and resource demand occupies a rectangle in the time-resource strip, so makespan corresponds to strip length and total completion time corresponds to the sum of rectangle endpoint times. Under this view, [22] give a tight \((3/2+\epsilon)\)-approximation for the unweighted makespan objective on identical machines with one shared renewable resource, while [43] give constant-approximation algorithms for the weighted total completion-time objective on capacitated parallel machines, using volume-by-weight ordering and a hybrid treatment of large resource demands.

2 Preliminaries↩︎

In this section, we define the scheduling model, the non-clairvoyant information structure, the total completion-time objective, and the benchmark bounds used throughout the paper. Our notation mostly follows the offline batch setting studied in the recent line of work on LLM inference scheduling [15], [18].

  The system has a single serving instance with a KV-cache memory budget \(M\in\mathbb{N}^{+}\). There are \(n\) jobs, denoted by \(\mathcal{J}\triangleq[n]\). Job \(i\in\mathcal{J}\) has a known prompt length \(s_i\in\mathbb{N}^{+}\) and an unknown response length \(o_i\in\mathbb{N}^{+}\). We assume that each job is individually feasible: \[\begin{align} s_i+o_i\le M, \qquad \forall i\in\mathcal{J}. \end{align}\] All jobs arrive at time zero. Time is discrete and proceeds in rounds \(t=0,1,2,\ldots\), where time \(t\) denotes the beginning of round \(t\). At time \(t\), each unfinished job is either active in a current attempt or inactive. For each active job \(i\), let \(u_{i,t}\) denote the number of response tokens already decoded in its current uninterrupted attempt before round \(t\) begins. For notational convenience, define \(u_{i,t}=0\) when job \(i\) is inactive. At the beginning of each round \(t\), the scheduler chooses an active batch \(\mathcal{B}_t\subseteq\mathcal{J}\) of unfinished jobs. Every job \(i\in\mathcal{B}_t\) receives one unit of processing during the round. If \(u_{i,t}+1=o_i\), then job \(i\) completes at the end of round \(t\), and its completion time is \(t+1\). Before deciding \(\mathcal{B}_t\), the scheduler may kill any active unfinished job \(i\), discarding all progress in its current attempt and setting \(u_{i,t}=0\); every unfinished job in \(\mathcal{B}_{t-1}\setminus\mathcal{B}_t\) is implicitly killed.

  If job \(i\) is active in round \(t\), its KV-cache memory usage is \[\begin{align} s_i+u_{i,t}+1, \end{align}\] where the term \(+1\) accounts for the token being decoded in the current round. A schedule is feasible if every active batch satisfies \[\begin{align} \sum\nolimits_{i\in\mathcal{B}_t} \left(s_i+u_{i,t}+1\right) \le M, \qquad \forall t\ge 0 . \end{align}\] In other words, the total memory occupied by all active jobs (i.e., their fixed prompts \(\sum\nolimits_{i\in\mathcal{B}_t}s_i\) plus the KV entries generated so far \(\sum\nolimits_{i\in\mathcal{B}_t}u_{i,t}\) plus the tokens currently being decoded \(|\mathcal{B}_t|\)) must never exceed the memory budget \(M\).

  The non-clairvoyant scheduler knows the number of jobs \(n\), memory budget \(M\), and the prompt lengths \(\{s_i\}_{i\in\mathcal{J}}\). It does not know the response lengths \(\{o_i\}_{i\in\mathcal{J}}\) in advance. The value of response length \(o_i\) is revealed only when job \(i\) completes. The benchmark scheduler is clairvoyant and knows all response lengths in advance.

The objective is to minimize total completion time, i.e., the sum of the completion times of all jobs. We evaluate non-clairvoyant algorithms against the optimal clairvoyant schedule, which knows all response lengths in advance. Let \(\mathrm{\mathrm{\small Opt}}(\mathcal{J})\) denote the minimum total completion time achievable by such a clairvoyant schedule¹⁰ on the full instance \(\mathcal{J}\).¹¹ For an algorithm \(\mathrm{\mathrm{\small Alg}}\), let \(\mathrm{\mathrm{\small Alg}}(\mathcal{J})\) denote its total completion time on \(\mathcal{J}\) starting from time \(0\). We say that \(\mathrm{\mathrm{\small Alg}}\) is \(\Gamma\)-competitive for \(\Gamma\geq 1\) if, for every feasible instance, \[\begin{align} \mathrm{\mathrm{\small Alg}}(\mathcal{J}) \le \Gamma\cdot \mathrm{\mathrm{\small Opt}}(\mathcal{J}) . \end{align}\]

For the analysis, we extend these definitions to any subset \(\mathcal{J}'\subseteq\mathcal{J}\). Let \(\mathrm{\mathrm{\small Opt}}(\mathcal{J}')\) denote the minimum total completion time achievable by a clairvoyant schedule that processes exactly the jobs in \(\mathcal{J}'\), and let \(\mathrm{\mathrm{\small Alg}}(\mathcal{J}')\) denote the total completion time of \(\mathrm{\mathrm{\small Alg}}\) on \(\mathcal{J}'\) starting from time \(0\).

An important concept in our algorithms and analysis is the memory-time area, which we abbreviate simply as area when the context is clear.

In addition to its role in our algorithms, the memory-time area provides a clear lower bound on the optimal total completion time. The intuition is that the system can supply at most \(M\) units of memory-time area per round, so the aggregate area of all jobs must be paid for in time; placing smaller-area jobs earlier minimizes the resulting sum of completion times.

We also use the following two standard lower bounds.

3 From Area Order to Three Scheduling Cases↩︎

In the previous section we derived the area-order lower bound, which gives a tractable benchmark for the optimal clairvoyant completion time. A natural next step is to ask whether a simple scheduling policy can simultaneously achieve high memory utilization and a completion order consistent with this lower bound. In this section we show that, outside the large-memory regime, no single priority rule can satisfy both requirements. This structural impossibility motivates our main algorithmic idea: a decomposition of the job set into three geometric regimes that are handled by specialized sub-schedulers.

The area lower bound in 2 suggests that two properties are sufficient for a constant approximation in the clairvoyant setting:

• (High memory utilization) the schedule should keep a constant fraction of the memory occupied; and

• (Area-order completion) the completion order should be close to nondecreasing memory-time area order.

High memory utilization ensures that the system delivers \(\Omega(M)\) units of memory-time area in every round, so the total area of all jobs is paid for within a constant factor of the time needed in the optimal schedule. Area-order completion ensures that the schedule respects the ordering that minimizes the weighted sum in the area lower bound (1). Together, they guarantee that the total completion time is bounded by a constant multiple of the lower bound, yielding a constant approximation.

In the clairvoyant large-memory setting where each job satisfies \(s_i+o_i=o(M)\), these two properties can be achieved by area-order greedy, which gives a \(3+o(1)\) approximation; see 2 in 8.1.

  Outside the large-memory setting, a single global priority order cannot simultaneously preserve an area-consistent completion order and high memory utilization.

The proposition rules out any single priority order, including natural global orders such as response-length order and area order. In the non-clairvoyant setting, the obstruction is further compounded because response lengths are unknown and a killed attempt loses all accumulated progress. The two cases impose opposite pressures on a non-clairvoyant scheduler. On one hand, small-prompt jobs must sometimes yield memory to large-prompt jobs; otherwise short large-prompt jobs may remain undiscovered. On the other hand, large-prompt jobs cannot be run too aggressively, because one such attempt may already fill the cache and block many small-prompt jobs. The fundamental obstacle is serving both geometries without letting either monopolize the memory budget. This points to a decomposition into geometric regimes: we first ask whether each regime, taken independently, admits a constant-factor guarantee.¹²

  For jobs whose prompt length dominates the response length, the growing memory use is close to a fixed width. If \(o_i\le s_i\), then during a successful attempt, \[s_i+1 \le s_i+u_{i,t}+1 \le 2s_i .\] Hence the dynamic KV-cache memory use is within a constant factor of a fixed rectangle width. This motivates the rectangle strip abstraction: job \(i\) is represented by a fixed rectangle width \(w_i\), and the scheduler packs active rectangle widths under the same memory budget.

The fixed-width view gives good utilization when rectangle widths are uniformly small or uniformly large.

1. Suppose every relevant rectangle width is at most \(\Delta\). Then utilization comes from greedy packing: if a waiting job cannot be inserted, then the active rectangles already use more than \(M-\Delta\) memory. Therefore the schedule has high utilization whenever \(M-\Delta= \Omega(M)\).

2. Suppose every relevant rectangle width is at least \(\delta\). Then any non-idle round uses at least \(\delta\) memory. Therefore any work-conserving schedule has constant utilization whenever \(\delta=\Omega(M)\).

Mixing these widths in one schedule can destroy the utilization lower bound. We therefore separate jobs by the prompt length first, using a prompt cutoff \(\Lambda\in (0,M/2)\): large jobs with \(s_i>\Lambda\) are separated first, and the other small jobs have bounded rectangle widths under the fixed-width view when \(o_i \le s_i\).

  When \(o_i > s_i\) instead, the memory footprint grows well beyond the prompt length and the fixed-width view no longer applies. For these jobs, the area is controlled by the response length: \[\frac{o_i^2}{2} \le A_{i} \le 2o_i^2 .\] Thus response-length order and area order agree up to constant factors.

  The above discussions give the following three regimes:

• (Large jobs) \(s_i > \Lambda\). These jobs are so wide that each one nearly fills the memory budget alone.

• (Small prompt-heavy jobs) \(s_i \le \Lambda\) and \(o_i \le s_i\). The response is no longer than the prompt, so the memory footprint stays within a constant factor of the prompt length.

• (Small response-heavy jobs) \(s_i \le \Lambda\) and \(o_i > s_i\). The memory footprint grows well beyond the prompt, and the area is dominated by the response length.

Each regime, taken in isolation, admits a constant-competitive non-clairvoyant algorithm. Specifically, [sec:rectangle-strip,sec:response-heavy] give constant-competitive algorithms for these regimes ([prop:rectangle-large-guarantee,prop:rectangle-prompt-heavy-guarantee] and [thm:response-heavy-ratio]). The remaining challenge is that the non-clairvoyant scheduler does not know which regime a job belongs to, because the distinction between prompt-heavy and response-heavy depends on the unknown response length. We explain how to resolve this difficulty when we discuss the meta-scheduler below.

If the three-way partition were known in advance, one could simply run each sub-scheduler on a dedicated replica (a three-fold resource augmentation) and obtain an \(O(1)\)-competitive guarantee immediately. Without resource augmentation, the black-box meta-scheduler of 6 time-shares a single memory budget across the three sub-schedulers, losing only a constant factor. In the non-clairvoyant setting, the additional difficulty is that the partition is not known: the scheduler cannot distinguish small prompt-heavy jobs from small response-heavy jobs without executing them. We resolve this by routing jobs dynamically as their response lengths reveal themselves, using the routing meta-scheduler described in 6.

4 Non-Clairvoyant Rectangle Strip Scheduling↩︎

This section analyzes two of the three branches: large branch and prompt-heavy branch. These two branches share the following useful property: for each job, its memory growth can be bounded by a constant factor of its prompt length. In particular, in large branch, the rectangle width is at most \(M\), which is \(O(s_i)\) when the prompt cutoff \(\Lambda\) satisfies \(\Lambda=\Theta(M)\). In prompt-heavy branch, the width is at most \(2 s_i\).

This property allows us to reduce the analysis of these two branches to a non-clairvoyant rectangle strip scheduling problem. In this problem, each job is represented by a rectangle with a known fixed width and an unknown processing time. The clairvoyant counterpart of this problem has been studied in [43]. To the best of our knowledge, the non-clairvoyant version has not been investigated before. We prove an \(O(1)\)-competitive algorithm for this problem, which may also be of independent interest. Next, we define the non-clairvoyant rectangle strip scheduling problem.

4.1 The Rectangle Strip Scheduling Problem↩︎

An instance of the rectangle strip problem consists of a job set \(\mathcal{J}\), a memory budget \(M\), a known width \(w_i \leq M\), and an unknown processing time \(p_i\) for each job \(i\in\mathcal{J}\). At every round, the total width of the active attempts must be at most \(M\). An active attempt of job \(i\) uses width \(w_i\) and completes the job after receiving \(p_i\) consecutive processing rounds. If an attempt is stopped earlier, its progress is lost. The processing time \(p_i\) is not known to the scheduler. Let \(\mathrm{\mathrm{\small Opt}}_{\mathrm{rect}}(\mathcal{J})\) denote the optimal clairvoyant total completion time for this rectangle strip instance.

4.2 The Rectangle Strip Scheduler and Analysis↩︎

The scheduler Rect processes each job through a sequence of capped attempts with geometrically increasing length caps. Since \(p_i\) is unknown, this prevents the schedule from spending too much time on any single job. If the job does not complete within this cap, the attempt expires and is killed. The next attempt restarts the job from zero progress with the doubled cap. Thus the level-\(r\) attempt of job \(i\) can run for at most \(2^r\) rounds.

Based on this doubling rule, Rect is a greedy allocator over attempts. For attempt \((i,r)\), define its area budget by \[B_{i,r} \triangleq w_i2^r.\] This is a doubling estimate of the true rectangle area \(A_{i}^{\mathrm{\mathrm{\small Rect}}}\triangleq w_ip_i\). A pending queue \(\mathcal{Q}\) is maintained, containing all job attempts waiting to be started. At every event time, the scheduler checks whether the pending attempt with the minimum area budget (\(\min\mathcal{Q}\)) can fit into the remaining memory. If so, it starts the attempt and repeats the scan; otherwise, the scan stops.

The critical events are time \(0\), a job completion, and an attempt expiration. Without loss of generality, simultaneous events in [alg:rectangle-strip] are processed one at a time under an arbitrary fixed tie-breaking order: each event time after time \(0\) contains only one completion or one expiration. The pseudocode is given in [alg:rectangle-strip].

  In the analysis, we decompose the completion time of each job into its active time and queue waiting time. The active time is immediate: the total active time of job \(i\) over all its attempts is at most \(4p_i\); it remains to bound the queue waiting time. To relate the waiting time to the optimal solution, we use a memory-area argument, extending the clairvoyant argument from 3. This argument relies on the following two properties maintained by [alg:rectangle-strip]:

1. attempts are processed in order of nearly nondecreasing rectangle area budget; and

2. every round with a nonempty queue uses a constant fraction of the memory.

Property (ii) turns queue waiting time into an area charge: whenever an attempt waits, the greedy scan and the width conditions ensure that a constant fraction of the memory is occupied by active attempts. Property (i) makes this charge compatible with the area order: the active area charged to a waiting attempt must come only from attempts with no larger budget. This condition lets us bound the total waiting contribution by the area-order lower bound.

The difficulty in proving property (i) is that attempts are created over time. Although the greedy scan always starts a minimum-budget pending attempt when it fits, a replacement attempt \((i,r)\) appears only when \((i,r-1)\) expires. While \((i,r-1)\) is active, the scan may have admitted other attempts whose budgets are larger than the budget of the replacement. If \((i,r)\) remained pending, those active attempts would have a larger budget than a pending attempt, violating the desired order.

We rule out this situation using a crucial property of the rectangle strip model: the width of each job is fixed across all attempts, even though the length cap \(2^r\) increases with the level \(r\). When \((i,r-1)\) expires, it releases a block of memory of width \(w_i\). The replacement \((i,r)\) has the same width \(w_i\), so this released memory is enough to run the replacement. If the replacement budget is small enough to threaten the budget order, then it has priority over every older pending attempt. The following greedy scan therefore starts the replacement immediately, before any older pending attempt can use the released memory. The approximate budget order is formalized by queue monotonicity (4): every pending attempt has budget at least that of every active attempt in each settled state.

This fixed-width argument is specific to the rectangle strip regime, which captures both large branch and prompt-heavy branch. In contrast, in the response-heavy regime, the effective width of a job may continue to grow, and therefore the reduction to fixed-width rectangle scheduling no longer applies. For this reason, 5 uses a different approach to maintain a good competitive ratio. This separation explains why the branches require different scheduling policies.

To precisely state the property of our algorithm, we index completion and expiration events by \(\ell=1,2,\dots\), and let \(\ell=0\) denote the initial event at time \(0\). We call a state settled when the greedy admission scan has stopped. Let \(S_\ell\) denote the settled state at the end of the outer for loop in [alg:rectangle-strip] after event \(\ell\), and let \(\mathcal{Q}(S_\ell)\) denote the pending queue in \(S_\ell\).

Write \(A_{i}^{\mathrm{\mathrm{\small Rect}}}\triangleq w_ip_i\) for the rectangle area of job \(i\). Let \(r_i \triangleq \min\{r:2^r\ge p_i\}\) be the first successful level. Then \[A_{i}^{\mathrm{\mathrm{\small Rect}}} \le B_{i,r_i} < 2A_{i}^{\mathrm{\mathrm{\small Rect}}} .\]

4.3 Applying to Homogeneous KV-Cache Regimes↩︎

The large branch and the prompt-heavy branch are both applications of Rect to homogeneous KV-cache regimes. When every job satisfies the same regime condition, the corresponding branch is an ordinary rectangle strip schedule with a direct completion-time guarantee. They are defined as follows.

• Large branch. Use \(\mathrm{\mathrm{\small Rect}}\) with rectangle width \(w_i=M\) and processing time \(p_i=o_i\).

• Prompt-heavy branch. Use \(\mathrm{\mathrm{\small Rect}}\) with rectangle width \(w_i=2s_i\) and processing time \(p_i=o_i\).

5 Area-Geometric Slicing for Response-heavy Jobs↩︎

Response-heavy jobs create a different obstacle from the rectangle strip setting of 4. Their memory footprint can grow far beyond the prompt length, so the fixed-width queue-monotonicity argument from 4 no longer applies.

This section uses a structural fact absent from the prompt-heavy regime: response length determines area up to constant factors. Every job \(i\) considered in this section satisfies \[\begin{align} s_i<o_i, \qquad s_i+o_i\le M. \end{align}\] Under this condition, memory-time area and the squared response length are equivalent up to constants: \[\begin{align} \frac{o_i^2}{2} \le A_{i} \le 2o_i^2 . \end{align}\] Thus ordering jobs by response caps also orders their area scales within constant factors. This equivalence permits each phase to replace the true prompts with a common prompt upper bound with only a constant-factor loss.

The scheduler \(\mathrm{\mathrm{\small Response}}\) uses geometric slicing to exploit this equivalence. The geometric slicing approach of [18] was developed for the identical-prompt setting. Although prompts may differ across jobs here, the area equivalence above allows each phase of \(\mathrm{\mathrm{\small Response}}\) to impose a common response cap and replace heterogeneous prompts with a common proxy prompt. The resulting proxy jobs are scheduled by the \(\mathrm{\mathrm{\small SPS}}\) subroutine described below. This construction realizes the two sufficient conditions from 3: \(\mathrm{\mathrm{\small SPS}}\) provides high memory utilization within each phase, and the geometric response caps ensure that the completion order is consistent with nearly nondecreasing area.

  The Staggered Pipeline Schedule (\(\mathrm{\mathrm{\small SPS}}\)) is a deterministic subroutine from [18] for scheduling an ordered batch of identical jobs. An \(\mathrm{\mathrm{\small SPS}}\) instance consists of \(m\ge1\) identical jobs, each with common prompt length \(s\ge0\) and slice length \(\tau\ge1\). Given a degree of parallelism \(k\ge1\), the schedule assigns the job of rank \(j\in\{0,\ldots,m-1\}\) the start offset \[S_{j} = \floor{\frac{j\tau}{k}},\] and runs that job for \(\tau\) rounds. Consecutive jobs are therefore spaced roughly \(\tau/k\) rounds apart, so at most \(k\) jobs overlap at any time. The key property is efficiency: by staggering the start times, \(\mathrm{\mathrm{\small SPS}}\) can choose a nearly optimal parallelism.

The Response scheduler ([alg:response-heavy]) uses geometrically increasing response caps. Fix a scaling factor \(\alpha>1\). Let \(L\triangleq\ceil{\log_{\alpha}M}\). In phase \(r\), the response cap is \[\tau_{r} = \min\{\ceil{\alpha^{r}},M\}.\] For each phase \(r\), define the proxy prompt \[\bar{s}_{r} = \min\{\tau_{r},M-\tau_{r}\}\] and choose the maximum feasible proxy parallelism \(k_{r} = k^*(\tau_{r}, \bar{s}_{r})\). The SPS call uses the induced order on its current job set from a deterministic order on the input job set; a job that reaches the cap without completing is killed.

The following theorem gives the response-heavy guarantee used by the meta-scheduler.

  Let \(\tau_{-1}=0\), and let \(\mathcal{J}_{r}=\{i\in\mathcal{J}:\tau_{r-1}<o_i\le\tau_{r}\}\) and \(n_{r}={\left|\mathcal{J}_{r}\right|}\) for \(r=0,1,\ldots,L\). Write \(N_{\ge r}\triangleq\sum_{q=r}^{L}n_{q}\) for the number of jobs in classes \(r,r+1,\ldots,L\). By 9, every job in \(\mathcal{J}_{r}\) completes in phase \(r\). Let \(D_{r}\) denote the duration of phase \(r\). By the start-offset rule of \(\mathrm{\mathrm{\small SPS}}\), the last start time in phase \(r\) is less than \(\tau_{r}N_{\ge r}/k_{r}\). Thus \[D_{r} \le \tau_{r} + \frac{\tau_{r}}{k_{r}}N_{\ge r}.\] The lower bound on \(k^*\) implies \(k_{r}=\Omega(M/\tau_{r})\) when \(\tau_{r}\le M/2\), while \(k_{r}=1\) when \(\tau_{r}>M/2\). The choice of \(k_{r}\) gives \(\tau_{r}/k_{r}=O(\tau_{r}^2/M)\), so \[\mathrm{\mathrm{\small Response}}(\mathcal{J}) = O\left( \sum_{r=0}^{L} \tau_{r}N_{\ge r} + \frac{1}{M} \sum_{r=0}^{L} \tau_{r}^2N_{\ge r}^2 \right).\] The linear sum is charged to the processing lower bound because the caps grow geometrically. For the quadratic sum, expand the square over ordered pairs of jobs and charge each pair to the smaller response class. Response dominance gives \(A_{i}=\Theta(o_i^2)\), so this pairwise charge is bounded by the area-order lower bound.

The complete proof is deferred to 10.

6 Meta-Scheduling with Routing↩︎

If the cases in 3 were known in advance, the scheduler could run the corresponding sub-schedulers through a black-box meta-scheduler on one shared memory resource. This known-partition reduction is given in 6.1. The black-box meta-scheduler runs the sub-schedulers in a round-robin order over doubling stages and preserves the total completion-time objective up to a constant factor.

The non-clairvoyant setting, however, does not directly provide this partition. For jobs with \(s_i\le\Lambda\), the distinction between \(o_i\le s_i\) (prompt-heavy) and \(o_i>s_i\) (response-heavy) depends on the unknown response length. The meta-scheduler therefore needs to route small jobs between sub-schedulers: a small job first enters the prompt-heavy branch; this branch either completes the job or reaches the boundary \(s_i\) and certifies \(o_i>s_i\). Certified jobs are then routed to the response-heavy branch. The routing meta-scheduler in 6.2 uses the same doubling stages as the black-box meta-scheduler to combine these two events and gives a constant-competitive guarantee.

6.1 The Black-Box Meta-Scheduler↩︎

The meta-scheduler in [alg:black-box-meta] merges a constant number of job partitions into one schedule and loses only a constant factor in the competitive guarantee. In each fresh invocation of a sub-scheduler, every job that has already completed in the meta-scheduler is still included as a dummy job. They follow exactly the schedule produced by the sub-scheduler, but their scheduled processing is ignored. This allows the meta-scheduler to invoke each sub-scheduler as an unchanged black box, without requiring any modification or any structural assumptions about its behavior.

6.2 The Routing Meta-Scheduler↩︎

The black-box reduction assumes that every job is already assigned to the correct sub-scheduler. The non-clairvoyant algorithm does not have this partition: for jobs with \(s_i\le\Lambda\), it must decide online whether a job is prompt-heavy or response-heavy.

The large branch and prompt-heavy branch use the rectangle strip scheduler \(\mathrm{\mathrm{\small Rect}}\) defined in 4. They differ only in how completion in the rectangle strip instance is interpreted in the original KV-cache instance.

• Large branch\(\mathcal{L}\). Jobs with large prompts are run by the full-width rectangle scheduler; every rectangle completion is true completion.

• Prompt-heavy branch\(\mathcal{P}\). Jobs in the prompt pool are run by the capped rectangle scheduler. In each run, the current pool \(\mathcal{P}\) is represented by the capped instance \(\widehat{\mathcal{P}}\), with the original prompt lengths and response lengths capped at \(\min\{o_i,s_i\}\). Completion in \(\widehat{\mathcal{P}}\) is either true completion in the original instance or certification that \(o_i>s_i\); certified jobs move to \(\mathcal{R}\).

• Response-heavy branch\(\mathcal{R}\). Certified response-heavy jobs are run by the response-heavy scheduler \(\mathrm{\mathrm{\small Response}}\).

\(\mathcal{L}\) is known in advance; \(\mathcal{P}\) is initialized to \(\{i\in\mathcal{J}:s_i\le\Lambda\}\) and \(\mathcal{R}\) is initially empty. During the algorithm, certified but unfinished jobs move from \(\mathcal{P}\) to \(\mathcal{R}\). As in the black-box meta-scheduler, completed jobs remain in their branch pool and are treated as dummy jobs in fresh runs; their scheduled processing is idle.¹³

  For the analysis, define \[\mathcal{S} \triangleq \mathcal{J}\setminus\mathcal{L} = \{i\in\mathcal{J}:s_i\le\Lambda\} , \qquad \mathcal{P}^* \triangleq \{i\in\mathcal{S}:o_i\le s_i\}, \qquad \mathcal{R}^* \triangleq \{i\in\mathcal{S}:o_i>s_i\}.\] Let \(\widehat{\mathcal{S}}\) denote the auxiliary capped instance on \(\mathcal{S}\): it has the same jobs and prompt lengths as \(\mathcal{S}\), and response length \(\min\{o_i,s_i\}\) for each job \(i\). Thus every capped prompt-pool instance \(\widehat{\mathcal{P}}\) that appears during the algorithm is a subinstance of \(\widehat{\mathcal{S}}\). The instance \(\widehat{\mathcal{S}}\) is a relaxation of \(\mathcal{S}\): every feasible schedule for \(\mathcal{S}\) is feasible for \(\widehat{\mathcal{S}}\), so \(\mathrm{\mathrm{\small Opt}}(\widehat{\mathcal{S}})\le\mathrm{\mathrm{\small Opt}}(\mathcal{S})\).

The branch calls made by the meta-scheduler are controlled by bounds defined on the corresponding full sets.

• For the rectangle branches, let \(C^\mathrm{\mathrm{\small L}}_i\) (\(i\in\mathcal{L}\)) and \(C^\mathrm{\mathrm{\small P}}_i\) (\(i\in\mathcal{S}\)) be the per-job bounds from 5 for the large branch instance on \(\mathcal{L}\) and the capped instance \(\widehat{\mathcal{S}}\), respectively. The sum in 5 only decreases under job deletion, so these bounds remain valid for every rectangle branch call on a current subset.

• For the response-heavy branch, let \(C^\mathrm{\mathrm{\small R}}_i\) be the completion time of \(i\) in \(\mathrm{\mathrm{\small Response}}(\mathcal{R}^*)\). By 15, \(C^\mathrm{\mathrm{\small R}}_i\) also bounds the completion time of \(i\) in every response-heavy branch call on a certified subset containing \(i\).

7 Conclusion and Discussion↩︎

We have presented the first constant-competitive non-clairvoyant scheduling algorithm for batched LLM inference under a hard KV-cache memory budget with arbitrary prompt lengths and arbitrary response lengths. The core algorithmic idea is a regime-aware routing framework that decomposes jobs into three geometric regimes—large jobs, small prompt-heavy jobs, and small response-heavy jobs—and handles each with a specialized sub-scheduler. A meta-scheduler time-shares the memory budget across these regimes and dynamically routes jobs as their execution reveals their true geometric class. This yields an \(O(1)\)-competitive guarantee for total completion time, and the same framework extends to other variants and extensions such as makespan minimization and online arrivals.

From a systems perspective, our results provide a principled foundation for a design principle already present in modern serving stacks: global request routing across replicas. Rather than introducing routing complexity inside a single replica, our framework shows that partitioning jobs by their geometric structure—large jobs, prompt-heavy jobs, and response-heavy jobs—and dispatching each class to a dedicated replica with a simple specialized local scheduler can simultaneously achieve worst-case robustness and practical efficiency. Because the theoretical meta-scheduler must time-share a single memory budget across heterogeneous classes, a multi-replica implementation actually attains a better competitive ratio than our single-replica bound, while remaining relatively simpler to deploy with existing continuous-batching and block-based cache managers. In this sense, simple local rules, properly routed by geometric class, suffice for both theoretical and practical performance.

8 Clairvoyant Scheduling Guarantees↩︎

The clairvoyant benchmark has three useful forms. Area-order greedy is nearly optimal when every job is small compared with the memory budget. For general instances, splitting jobs by full rectangle width and combining the two resulting schedules gives a constant approximation. A direct rectangle packing argument gives a smaller constant by using a known strip packing guarantee as a black box. The schedules below reserve the full rectangle width of each active job: \[\ell_{i} \triangleq s_i+o_i,\] i.e., reserving the full rectangle of each job.

8.1 Large-Memory Case↩︎

The large-memory case is a KV-cache analogue of the small-demand WSVF guarantee for capacitated machines [43].

8.2 General Case via Black-Box Meta-Scheduling↩︎

For a general clairvoyant instance, view each job as a rectangle with width \(\ell_{i}\) and height \(o_i\). The jobs are separated by rectangle width. The small-width part uses Greedy with the true full widths. The large-width part uses the same Greedy routine on an auxiliary instance in which every job reserves rectangle width \(M\). The two schedules are merged by the black-box meta-scheduler of 6.1.

8.3 General Case with Direct Rectangle-Packing↩︎

This subsection gives a second clairvoyant bound using a stronger geometric primitive. The previous two subsections use area-order scheduling directly; here we call a strip packing algorithm as a black box, which gives a stronger makespan guarantee for each stage. The conversion from stage makespan guarantees to total completion time follows the doubling framework of the single-machine capacitated scheduling algorithm of [43]. Two simplifications apply in the present unweighted rectangle instance:

• The knapsack selection step for weighted rectangles becomes the exact prefix after sorting by rectangle area.

• For rectangles with width at most \(M\), height at most \(L\), and total area at most \(ML\), the \(2\)-approximation algorithm by [39] packs them in height at most \(2L\).

These two changes give an \(8\)-approximation for the rectangle instance, improving the \(12+\varepsilon\) factor from the corresponding framework of [43]. The conversion from KV-cache jobs to rectangles loses another factor of \(2\) against the area lower bound, yielding the \(16\)-approximation below.

9 Complete Non-Clairvoyant Rectangle Strip Scheduling↩︎

The rectangle strip guarantee in 1 assumes a useful width range. This section removes that assumption by mixing two rectangle strip schedulers through the black-box meta-scheduler.

10 Competitive Ratio for the Response-heavy Scheduler↩︎

This appendix proves the explicit constant used in [thm:response-heavy-ratio]. For the rest of the appendix, fix \(\alpha=2\) and a response-heavy job set \(\mathcal{J}\); for every fixed \(\alpha>1\), the same argument gives the stated \(O_{\alpha}(1)\) bound. Let \(L\triangleq\ceil{\log_2M}\). Let \(\tau_{-1}=0\) and define the phase classes \[\mathcal{J}_{r} = \{i\in\mathcal{J}:\tau_{r-1}<o_i\le\tau_{r}\}, \qquad n_{r}={\left|\mathcal{J}_{r}\right|}, \qquad N_{\ge r}=\sum_{q=r}^{L}n_{q}, \qquad N_{> r}=\sum_{q=r+1}^{L}n_{q}\] for \(r=0,1,\ldots,L\). Let \(\underline{\tau}_0\triangleq1\) and \(\underline{\tau}_{r}\triangleq\tau_{r-1}\) for \(r\ge1\). Then every job \(i\in\mathcal{J}_{r}\) satisfies \[o_i\ge\underline{\tau}_{r}, \qquad \tau_{r}\le2\underline{\tau}_{r} .\]

Define the class-area lower-bound quantity \[A_{\mathrm{LB}} \triangleq \sum_{r=0}^{L} \underline{\tau}_{r}^2 \left( \frac{n_{r}(n_{r}+1)}{2} + n_{r}N_{> r} \right).\]

11 Alternative Objectives↩︎

This appendix gives two extensions of the meta-scheduling framework.

• 11.1 shows that the same algorithm is also constant-competitive for makespan.

• 11.2 extends the routing framework to total completion time with online arrivals.

For online arrivals, the natural latency objective is total flow time. Under (oblivious) adversarial arrivals, however, online KV-cache scheduling admits an \(\Omega(\sqrt{n})\) lower bound on the competitive ratio for total flow time, even in the identical-prompt special case [15], [18]. Total completion time is the closest feasible alternative: for a fixed arrival instance, the two objectives induce the same optimal schedules. Online completion-time objectives have also been studied in classical scheduling [31], [32].

11.1 Makespan↩︎

For a job set \(\mathcal{J}'\subseteq\mathcal{J}\), let \(\mathrm{\mathrm{\small Opt}}_{\mathrm{span}}(\mathcal{J}')\) be the optimal clairvoyant makespan for scheduling exactly the jobs in \(\mathcal{J}'\). For a schedule produced by an algorithm \(\mathrm{\mathrm{\small Alg}}\), let \({\mathrm{\mathrm{\small Makespan}}}\!\left[\mathrm{\mathrm{\small Alg}}(\mathcal{J}')\right]\) denote its makespan.

The first bound is the processing requirement of the longest job. The second follows because all memory-time areas of jobs must be supplied. We use the branch sets and capped small instance from 6.2.

The following theorem gives the makespan extension.

11.2 Total Completion Time with Online Arrivals↩︎

Each job \(i\) now has an arrival time \(a_i\in\mathbb{N}\). Before time \(a_i\), job \(i\) is not visible to the scheduler. At time \(a_i\), its prompt length \(s_i\) becomes known, while its response length \(o_i\) is still unknown until completion. Let \(\mathrm{\mathrm{\small Opt}}_{\mathrm{arr}}(\mathcal{J})\) be the optimal total completion time of a clairvoyant schedule that knows all jobs and response lengths in advance, but may process job \(i\) only after time \(a_i\).

The first bound follows by removing arrival constraints. The second follows because job \(i\) cannot complete before time \(a_i+o_i\).

The online scheduler uses the same pool convention: newly arrived jobs enter either \(\mathcal{L}\) or \(\mathcal{P}\), certified but unfinished jobs move to \(\mathcal{R}\), and completed jobs are removed from their branch pools.

The following theorem gives the online-arrival extension.

References↩︎