Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling Dayi Yao University of Washington, ydy@uw.edu

Zijie Zhou IEDA, HKUST, jerryzhou@ust.hk Abstract. This paper studies a resource-allocation inefficiency in batched large language model (LLM) serving: heterogeneous requests that share a decode batch impose max-driven computational

arXiv:2608.02244v1 [cs.DC] 3 Aug 2026

costs on one another. Because the wall-clock cost of a batch step is largely governed by the largest active KV-cache footprint, a short request co-batched with a long request can experience latency and GPU-resource consumption disproportionate to its own token workload. We formalize this phenomenon as a resource-fair scheduling problem. We develop a mathematical scheduling model that connects within-batch resource fairness to system throughput. The proposed fairness constraint bounds the disparity in decode progress, equivalently KV-cache footprint, among co-batched requests. Based on this model, we design the Insert-ShortJobs-with-Limit (ISJL) algorithm, a parameterized hybrid batching policy. We prove that ISJL achieves a global competitive-ratio lower bound of 3/4 and further characterize how the worstcase guarantee varies with the fairness budget. Empirical evaluations show that ISJL improves throughput and end-to-end latency relative to standard scheduling baselines. We further examine the profit implications of resource-fair scheduling under the token-metered pricing convention used by commercial LLM APIs. In this environment, for a fixed accepted workload, revenue is additive in token counts and is independent of the scheduling policy; scheduling affects profit through inference cost. We prove a cost decomposition showing that inference cost consists of an intrinsic workload term, a time/overhead term, and a schedule-induced batching externality term. The fairness constraint bounds the batching externality, while the ISJL throughput guarantee controls the time/overhead component. Numerical experiments show that ISJL occupies a favorable middle ground between FCFS, which has large batching externalities, and LJF, which is cost-aligned but sacrifices batching flexibility. Thus, ISJL provides a bi-criterion scheduling policy: it maintains high throughput while aligning max-driven batch cost with token-metered revenue. Keywords: scheduling, computational fairness, LLM serving

1

Introduction

Large language models (LLMs) (Brown et al. 2020, Chowdhery et al. 2023, OpenAI 2023) now underpin a wide range of information (Anthropic 2023, OpenAI 2019, 2023), assistants (Amazon 2023, 1

GitHub 2021), and decision-support applications (Huang et al. 2025, Cascella et al. 2023, Sallam 2023). LLM inference is the dominant, recurring cost for operators: requests arrive online and are served on GPU workers that exploit batching for throughput. The mechanics are distinctive. Each request is processed in two phases (Kwon et al. 2023): a prefill pass over the input tokens, followed by an autoregressive decode phase that generates output one token at a time. During decode, each step reuses the key–value (KV) cache from previously generated tokens; the compute and memory required per step therefore increase with a request’s accumulated context length. Modern systems (Kwon et al. 2023, Agrawal et al. 2023) explicitly manage KV memory and construct batches across heterogeneous requests to raise utilization, making batching a first-order operational lever at inference time. This batching lever creates a subtle externality. When a very long request and a very short request decode in the same batch, the short request “pays” latency to the long one: the per-step FLOPs and memory footprint are driven by the longest context in the batch. In effect, short jobs subsidize long jobs through shared compute and KV memory. The phenomenon is well documented in Sheng et al. (2024), Khan et al. (2024), Wei et al. (2025) that measures lower GPU utilization in decode, sensitivity to sequence length, and the benefits of uniform micro-batches, but it has not been formalized as a resource fairness problem in service operations. We take that step: rather than defining fairness through outcomes or service guarantees, we define fairness directly in terms of consumed computational resources within a batch—proxied by each request’s current decode progress (i.e., number of generated tokens and associated KV cache). Resource fairness as an operational batching discipline. The fairness notion we study is distinct from the ethical or equity-based fairness concepts prevalent in operations management and algorithm design (e.g., group or individual parity in predictive systems, egalitarian welfare). We study resource-consumption fairness: a batching discipline requiring co-batched requests to have comparable decode progress, or equivalently, comparable KV-cache footprints. The purpose of this discipline is to limit the extent to which a request with a small resource footprint is served in a batch whose resource profile is determined by much larger requests. This perspective leads to a cost–efficiency frontier. Tighter resource homogeneity improves cost alignment by reducing extreme within-batch heterogeneity, but it can also restrict batching flexibility. Our model therefore treats α as a resource-homogeneity budget and asks how much throughput can be retained while respecting that budget. This differs from the classical fairness– efficiency tradeoff in service operations: fairness here is not an outcome-parity requirement, but an operational control that limits the batching externality described above. Resource-fair scheduling improves cost alignment under token-metered pricing. A second managerial implication concerns the profit consequences of scheduling under prevailing API pricing practice. Commercial LLM providers typically use token-metered contracts: model-specific rates are quoted for input, output, and sometimes cached tokens, usually per one million tokens (OpenAI 2026, Anthropic 2026, DeepSeek 2026, Google 2026). These contracts are not decisions made by the scheduler; they form an external pricing environment. Consistent with the token-level 2

abstraction in Section 2, we represent this environment by a single effective linear charge pi = p0 oi P for request i. Once a set of requests has been accepted, total revenue i pi is fixed and additive in token counts. Scheduling affects profit through inference cost. This creates an operational tension. Token-metered revenue is additive across requests, whereas the per-step cost of a batch is driven by the largest active resource footprint in the batch. Heterogeneous co-batching can therefore create a schedule-induced excess cost: short requests may be processed in steps whose cost is determined by longer co-batched requests. Resource-fair scheduling addresses this cost-alignment problem. By requiring co-batched requests to have comparable decode progress, or equivalently comparable KV-cache footprints, the scheduler bounds the gap between max-driven batch cost and the additive token workload measured by pricing. Thus, our economic analysis is not a pricing-design model. Rather, it evaluates the profit and cost-alignment implications of resource-fair scheduling under exogenous token-metered prices.

1.1

Main Contributions

A formal model linking fairness and throughput in LLM inference.

In Section 2, we

develop a single-worker scheduling model that explicitly captures the dynamics of LLM inference. The model assumes that a decision-maker receives n heterogeneous requests, each requiring sequential token generation, and that the worker can process at most B tokens concurrently. To maximize throughput, the worker naturally seeks to form full batches of size B at each step. However, such batching can create substantial unfairness in resource consumption. To address this inefficiency, we introduce a parametric fairness constraint indexed by α, which bounds the disparity in resource consumption (measured by decoding progress or KV-cache footprint) among co-batched requests. This model enables a quantitative characterization of the tradeoff between throughput and fairness, and provides a tractable foundation for algorithmic design. Fair and efficient scheduling algorithms with provable guarantees.

In Section 3, we

design and analyze algorithms that achieve both fairness and high throughput under the proposed constraint. We begin with a baseline policy—Longest-Job-First (LJF)—which is universally fair B for any α. We prove in Theorem 1 that LJF attains a competitive ratio of at most 2B−1 . We then

introduce a refined parameterized algorithm, Insert-Short-Jobs-with-Limit (ISJL), which explicitly incorporates the fairness parameter α. Theorems 2 and 3 establish that ISJL achieves a competitive ratio of at least 0.77 when B = 2, and a uniform lower bound of 3/4 for all B ≥ 2. These results provide the first approximation guarantees for resource-fair scheduling in LLM inference settings. In Section 3.4, we further extend ISJL to the practically important setting where output token lengths are unknown at arrival time. The proposed Robust-ISJL algorithm enforces the fairness constraint using only observed runtime progress, requiring no knowledge of true output lengths, and retains a competitive guarantee that degrades gracefully with prediction error, recovering the 3/4 bound exactly when predictions are perfect. Competitive Ratio Lower Bound as a Function of α In Section 4, we sharpen the guarantees

3

by characterizing how the worst-case competitive ratio varies with the fairness budget. Let γ = α/o1 ∈ (0, 1) denote the normalized fairness parameter (relative to the longest job). For all B ≥ 2, the overall worst-case lower bound takes the single piecewise form  1+γ   , 2γ CR(γ) = 12+ −γ   , 3 − 2γ

0 < γ ≤ 21 , 1 2 ≤ γ < 1,

which is strictly decreasing on (0, 12 ], strictly increasing on [ 21 , 1), and attains a unique global minimum of 34 at γ = 21 ; moreover, CR(γ) → 1 as γ → 0+ or γ → 1− . This parameterized bound, obtained by analyzing over- and under-inserting adversaries, both explains when the 34 limit is tight and clarifies the fairness–efficiency trade-off induced by α. Profit and cost alignment under exogenous token-metered pricing. Section 5 connects the scheduling analysis to the token-metered pricing convention used in commercial LLM APIs. We treat pricing as exogenous and use profit as an evaluation dimension of scheduling, rather than as a pricing decision. For a fixed accepted workload, linear token revenue is independent of the schedule, so profit differences across schedulers arise from inference cost. We prove a cost decomposition showing that the total inference cost of a schedule can be written as CA (I) = τ Q(I) + cTA (I) + τ EA (I), where Q(I) is an intrinsic workload term independent of scheduling, TA (I) is the makespan, and EA (I) is the schedule-induced batching externality generated by max-driven batch cost. We show that any α-fair schedule satisfies EA (I) ≤ αO(I), where O(I) is the total token workload. Combining this externality bound with the throughput guarantee of ISJL yields an additive profit guarantee relative to the optimal α-fair profit schedule. The numerical experiments then decompose profit into intrinsic workload cost, time/overhead cost, and batching-externality cost. They show that ISJL substantially reduces FCFS’s externality cost while preserving much of the batching flexibility that LJF sacrifices. We also explicitly discuss the scope of the demand specification: customer acceptance is modeled as exogenous to realized waiting times, so the results quantify cost alignment under a fixed pricing environment rather than endogenous pricing or demand response. System efficiency on real workloads.

Section 6 benchmarks schedulers on a fixed arrival se-

quence drawn from LMSYS-Chat-1M. Using throughput and Average End-to-end Latency (AEL) as metrics under B ∈ {16, 32}, ISJL dominates these baselines, simultaneously increasing throughput and reducing AEL across tested α ∈ {50, 100, 150}, with α offering a tunable efficiency–latency trade-off. These controlled results complement the revenue findings, showing ISJL delivers balanced performance with near top profit and markedly better efficiency on realistic, heterogeneous workloads.

4

1.2

Other Related Works

LLM Inference and Fair Serving. Enhancing the efficiency of LLM inference is essential, as it involves considerable computational and financial overhead. Most prior studies emphasize systemlevel engineering approaches to speed up inference in deployed environments, typically lacking theoretical performance assurances. For example, Patel et al. (2023), Zhong et al. (2024) design architectures that decouple the processing of prompts and tokens, whereas Yu et al. (2022), Agrawal et al. (2023, 2024) develop integrated designs that jointly process both—an architecture consistent with the setting analyzed in this work. Moreover, there are some recent works focusing on the service level fairness in LLM inference Sheng et al. (2024), Khan et al. (2024). More recently, several studies have begun to establish theoretical underpinnings for LLM inference. The mathematical formulation adopted in this paper extends the framework of Jaillet et al. (2025). Wang et al. (2025), Chen et al. (2025) improve the efficiency and robustness of this theoretical model. Ao et al. (2025) investigate inference scheduling problems with multiple objectives and design algorithms that provide formal performance guarantees. Scheduling Optimization.

The scheduling problem—widely explored in prior research (Al-

lahverdi et al. 2008, Chen et al. 1998, Albers 2009, Mak et al. 2015, Kong et al. 2013)—concerns a decision-maker responsible for processing numerous incoming tasks, either sequentially or in groups. The key difficulty is to determine an efficient order and timing for execution, typically formalized as an integer optimization problem. In our setting, inspired by LLM inference, multiple jobs can be executed simultaneously in batches, connecting our formulation to batch scheduling frameworks studied in (Chen and Lee 2008, Liu and Lu 2015, Li et al. 2020). Moreover, LLM inference introduces an inherent sequential dependency—subsequent tokens cannot be processed until the current ones are completed—thereby creating precedence constraints. Related studies on scheduling under such constraints include (Shahout et al. 2024, Garg et al. 2019, Azar and Epstein 2002, Robert and Schabanel 2008). Nonetheless, these works differ fundamentally from ours, as our formulation uniquely incorporates a fairness constraint on resource usage arising specifically from the LLM inference context.

2

Model

In this paper, we study a scheduling problem for large language model (LLM) inference on a single computational worker. A total of n prompt requests await processing. Each request i ∈ [n] is characterized by a parameter oi , where oi denotes the total number of tokens in the prompt input and corresponding model-generated output. For each request, the chunked input technique from (Agrawal et al. (2023)) processes tokens sequentially, one at a time. Once the first output token is generated, the remaining tokens follow in the same manner. Thus, each request completes within oi units of time, processing oi tokens sequentially.

Throughout the main analysis we assume oi is known to the scheduler at the time

of admission, which is a standard assumption in the offline scheduling literature (Jaillet et al. 5

2025, Wang et al. 2025). In Section 3.4, we remove this assumption and extend the model to the non-clairvoyant setting, in which only a prediction interval [ℓi , ui ] with ℓi ≤ oi ≤ ui is available. The computational worker processes requests in batches, with a maximum batch size of B requests. Each batch may consist of tokens from different requests, but not multiple decoding tokens from the same request, as these are generated sequentially. After processing a batch, each request included in it advances by generating its next output token. The model uses a logical token-step abstraction: one service step advances each active request by one token. Thus, the makespan TA (I) counts the number of scheduling steps rather than calibrated GPU milliseconds. We adopt this abstraction deliberately. In deployed LLM serving systems, the wall-clock time of a batch step depends on hardware and system choices, and there is no universal closed-form latency function that is valid across serving architectures. The batching externality motivates the fairness constraint below, while the profit and cost-alignment implications of max-driven batch cost are developed separately in Section 5. Fair Serving Metric.

To ensure equitable resource allocation, we impose a fairness constraint

based on the number of tokens held in the key-value (KV) cache: At any time t, let S (t) denote (t)

∈ [0, oi ] denote the number of decoding tokens (t) (t) generated for request i ∈ S . The memory footprint of request i at time t is thus ai . We require the set of requests being processed, and let ai

that: (t)

(t)

max {ai } − min {ai } ≤ α

i∈S (t)

(1)

i∈S (t)

for some fixed constant α. To motivate constraint (1), it is important to understand why the computational cost of a batch step is driven by the longest KV cache in the batch rather than by the sum or average. At each decode step, two GPU operations dominate cost. First, the (t)

attention operation for request i scales with its current KV cache size ai ; however, since GPU cores can process attention heads in parallel, the wall-clock time for this operation is approximately (t)

proportional to maxi∈S (t) ai , not the sum. Second, the feed-forward layers compute a joint matrix product over all tokens in the batch, and the projection matrices are loaded from GPU highbandwidth memory once for the entire batch regardless of its size. Due to GPU parallelism, the wall-clock time for this shared computation is approximately constant over a wide range of batch sizes (Chen 2023). Both mechanisms imply that a short request co-batched with a long one pays latency proportional to the long request’s KV footprint, not its own. This is the batching externality: long jobs impose a negative external cost on short jobs by inflating the per-step compute time they experience. Constraint (1) directly bounds this resource heterogeneity. When the max–min progress gap is at most α, all co-batched requests have KV caches within α tokens of each other, so the largest active footprint in the batch remains close to each request’s own footprint. In this sense, α controls the schedule-induced gap between individual token progress and the resource profile of the batch. Section 5 uses this observation to formalize the resulting cost-alignment implication under maxdriven batch cost.

6

Scheduling Policy. A scheduling policy is an event-driven rule that, at each decision epoch t, determines the active batch S (t) ⊆ [n] subject to: (i) the capacity constraint |S (t) | ≤ B, and (ii) the fairness constraint (1). Crucially, a policy is not restricted to static batching, in which a fixed set of B requests is locked together until every member finishes. A policy may instead implement continuous batching: whenever a request completes and frees a slot, the policy may immediately admit a new request into the active batch—provided the fairness constraint remains satisfied—without waiting for any other running request to complete. Continuous batching is the default operation mode of modern LLM serving systems such as the First-Come-First-Serve (FCFS) scheduling framework in Orca (Yu et al. 2022) and vLLM (Kwon et al. 2023), which will be introduced in Section 2.1 in detail. Objective and Performance Metric. Our objective is to design a scheduling algorithm that maximizes throughput, defined as the total number of tokens processed per unit time: Pn Throughput(A; I) =

i=1 oi

TA (I)

where TA (I) is the makespan of algorithm A on instance I, and

,

Pn

i=1 oi is fixed for a given instance.

Note that not every batch can process B requests: when the fairness constraint (1) is active, it may not be possible to find B requests whose current decode progress falls within a window of size α, and the scheduler must form a smaller batch or admit only requests that satisfy the constraint. The throughput objective therefore captures the tension between batch fullness and fairness enforcement. Proposition 1 (NP-hardness). Assume n > B. Finding a schedule that maximizes throughput subject to the fairness constraint (1) is NP-hard. Proposition 1 follows straightforwardly by setting α = maxi∈[n] oi . With this choice, the fairness constraint in Equation (1) becomes trivially satisfied for all possible schedules. In the absence of fairness constraints, prior work by Lee and Chen (2001) establishes that throughput maximization is strongly NP-hard. Consequently, the problem necessitates the design of approximation algorithms. To evaluate the performance of an approximation algorithm, we use the competitive ratio. Given a request instance I, let OPT(I) denote the optimal throughput achievable by any fair schedule (obtainable via the integer program in Appendix EC.1). The competitive ratio of algorithm A is defined as: CR(A) = inf I

Throughput(A; I) . OPT(I)

A competitive ratio of 1 means the algorithm always achieves optimal throughput; a ratio of c < 1 means the algorithm’s throughput is guaranteed to be at least a c fraction of optimal on every instance. Bicriteria interpretation of the constrained objective. The formulation above should be interpreted as a constrained bicriteria optimization problem. The operator cares about both cost alignment and system efficiency. The parameter α controls the first dimension by imposing a 7

resource-homogeneity budget on each active batch; conditional on this budget, the scheduler optimizes the second dimension, namely throughput, or equivalently makespan. This constraint-andoptimize formulation is common in multi-objective online decision problems: rather than specifying a single scalar weight across objectives, one objective is parameterized as a constraint and the other is optimized. A related philosophy appears in the consistency–robustness literature for online algorithms with predictions, where a tunable parameter is used to trace a Pareto frontier between two performance notions (Lykouris and Vassilvitskii 2021, Golrezaei et al. 2023). Remark 1 (Offline snapshot model and online arrivals). The main theoretical model is an offline backlog model: all requests in I are available at time 0. This formulation should be interpreted as a snapshot approximation of a congested serving system, in which the operator periodically faces a large queue of pending requests and must prioritize them under a batch-capacity constraint. This model does not claim to solve the fully online arrival problem. In a production system, new requests continue to arrive while the current backlog is being served, and the scheduler must make causal decisions without knowing future arrivals. This introduces a distinct information-structure problem: whether to serve currently available requests immediately or wait for future requests that may form better resource-homogeneous batches. The competitive-ratio results in Sections 3.1–3.4 are therefore offline guarantees for backlogged instances. Section 3.5 discusses how to adapt our offline algorithms under online arrivals and why the offline competitive guarantee does not directly extend to adversarial release times. Remark 2 (Compute-bound vs. memory-bound constraints in LLM inference). LLM inference systems face two distinct resource constraints that can each become the binding bottleneck depending on hardware configuration and workload characteristics. The memory-bound constraint limits the total number of KV-cache tokens that can be held in GPU high-bandwidth memory (HBM) simultaneously. When sequences are very long, GPU HBM fills up before compute is saturated, forcing the system to pause or preempt active requests. This constraint is the focus of recent theoretical work by Jaillet et al. (2025), and is also the engineering motivation for systems such as PagedAttention (Kwon et al. 2023), which manages KV memory via virtual paging to delay the onset of memory-bound behavior. The compute-bound constraint limits the number of requests that can be processed concurrently by GPU compute throughput. When sequences are short-to-medium in length, the system can hold all active KV caches in memory simultaneously, and the binding constraint is the number of requests B that can be batched in a single compute step. This is the formulation adopted by Orca (Yu et al. 2022), Sarathi-Serve (Agrawal et al. 2024), and Sheng et al. (Sheng et al. 2024), all of which use a maximum concurrent sequence count as the primary scheduling constraint. It is also the regime described by the GPU batching analysis in Chen (2023): the observation that MLP compute time is approximately constant across a wide range of batch sizes holds precisely because in the computebound regime, the GPU is underutilized at small batch sizes and parallelizes additional tokens at near-zero marginal wall-clock cost. Our model adopts the compute-bound formulation, constraining each batch to at most B con8

current requests. This is also consistent with the fair serving constraint described above: when GPU compute drives batch cost, the per-step wall-clock time is determined by the longest KV cache in the batch, creating the cross-subsidization of short requests by long ones. Extending the model to the memory-bound regime can be an interesting direction for future work.

2.1

Examples of Unfair Schedules

Example 1. First-Come, First-Served (FCFS) scheduling policy can lead to highly unfair and inefficient outcomes, as demonstrated in the Figure below. The scenario depicts three requests with demands o1 > o2 ≫ o3 arriving in sequence. Under FCFS, r3 is batched with request 1’s long tail. This forces r3 , which has a negligible resource requirement, to endure a latency comparable to r1 , severely inflating its completion time and leading to inefficient resource utilization.

Example 2. Shortest First (SF) scheduling, while often efficient for average latency, introduces a different form of unfairness that can lead to starvation (Figure below). Consider five requests arriving in sequence with demands o1 > o2 > o3 > o4 > o5 . For request 3, 2, and 1: each is forced to batch with a progressively larger tail to complete. As the executing batch aggregates more and larger jobs, its prolonged execution time exacerbates the unfairness for subsequent requests.

Remark 3 (Continuous batching in FCFS and SJF). Both FCFS and SJF operate under continuous batching: whenever a request completes and frees a processing slot, the next request (in arrival order under FCFS, or by shortest remaining length under SJF) is immediately admitted to the active batch without waiting for other running requests to finish. The unfairness illustrated in the examples above therefore arises not from static batch assignments, but from the head-of-line externality that persists even under continuous batching: as long as a long request remains active, every short request admitted to share its batch is forced to advance in lockstep with it, paying a per-step cost proportional to the long request’s KV footprint rather than its own.

9

3

Fair Scheduling Algorithms

This section presents two fair scheduling algorithms: Longest Job First (LJF) and Insert Short Jobs with Limit (ISJL). LJF provides absolute fairness, satisfying the fairness constraint for any α ≥ 0, but achieves poor throughput, serving as a benchmark for worst-case throughput. To address this limitation, we design ISJL, a parametric algorithm that accepts a fairness parameter α and provides a tunable trade-off, guaranteeing fairness for the given α while significantly improving throughput.

3.1

Longest Job First (LJF)

First, we propose the Longest Job First (LJF) scheduling algorithm. LJF operates in discrete batches. It begins by selecting the B longest requests from the queue to process simultaneously. The system then idles until the longest request in the current batch completes, upon which the entire batch is considered finished. Only then does LJF select the next B longest requests to form a new batch. This process repeats indefinitely. Figure 1 provides an example of how LJF processes each batch of requests.

Figure 1: An example of LJF Proposition 2. Algorithm LJF is fair, which satisfies the constraint (1) for any α > 0. Proposition 2 states that LJF is fair for any α > 0. The proof is straightforward: within any batch S (t) , all requests start simultaneously. Therefore, the instantaneous acceleration for each (t)

request is equal, i.e., maxi∈S (t) ai

(t)

= mini∈S (t) ai , satisfying the fairness condition. However, a

significant drawback of LJF is its poor throughput. The algorithm does not admit new requests into a batch until the entire batch completes, even if resources are released early when shorter jobs finish. This leads to unavoidable resource idling. The following theorem quantifies this inefficiency. Algorithm 1 Longest Job First (LJF) 1: o = {o1 ≥ o2 ≥ · · · ≥ on } 2: for i = 1 . . . ⌊n/B⌋ do 3: run {o(i−1)B+1 , . . . , oiB } 4: run the remaining jobs in another batch Remark 4 (LJF as a static-batching baseline). Algorithm 1 is the only static-batching algorithm in this paper: it forms a complete batch of the B longest requests and holds it until every member 10

finishes, tolerating resource idling whenever shorter jobs complete early, since no new request is admitted until the entire batch is done. Theorem 1 (Competitive Ratio of Algorithm LJF). For any B ≥ 1, we have CR(LJF) ≥

B . 2B − 1

Proof of Theorem 1. We begin with a trivial lemma states that maximizing throughput is equivalent to minimizing the makespan since we cannot cancel any request in our model. Lemma 1 (Makespan-Throughput Correspondance). Define the makespan of Algorithm A under the arrival instance I is TA (I). Then, maximizing throughput is equivalent to minimizing makespan. i.e., min TA (I) Proof of Lemma 1

⇐⇒

max Throughput(A; I)

For the given n jobs in an arrival instance I, Throughput(A; I) satisfies Pn Throughput(A; I) =

where

i=1 oi , TA (I)

Pn

i=1 oi is unchanged within the same instance, which completes the proof.

■

B Then, we show that the competitive ratio of LJF is lower bounded by 2B−1 .

W.L.O.G., let nB jobs have processing times o1 ≥ o2 ≥ · · · ≥ onB , and Algorithm 1 produces the makespan TLJF (I) = o1 + oB+1 + o2B+1 + · · · + o(n−1)B+1 . Set L := o1 , O :=

PnB

i=1 oi and TOP T (I) to be the makespan of optimal scheduling for instance I.

Any feasible schedule must process the longest job and must split the total work over batch size B, hence TOP T (I) ≥ L,

TOP T (I) ≥

O . B

B Case 1: L ≥ 2B−1 TLJF (I).

2B−1 Then TLJF (I) ≤ 2B−1 B L ≤ B TOP T (I).

B Case 2: L < 2B−1 TLJF (I).

Decompose

TLJF (I) = L + Omod1 ,

where Omod1 := oB+1 + o2B+1 + · · · + o(n−1)B+1 .

B−1 The assumption yields that Omod1 > 2B−1 TLJF (I). Because o(k−1)B+2 ≥ o(k−1)B+3 ≥ · · · ≥ okB ≥

okB+1 for all k > 0, therefore Omod2 := o2 + oB+2 + · · · + o(n−1)B+2 ≥ Omod1 >

11

B−1 TLJF (I). 2B − 1

Omod3 := o3 + oB+3 + · · · + o(n−1)B+3 ≥ Omod1 >

B−1 TLJF (I). 2B − 1

.. . Omod0 := oB + o2B + · · · + onB ≥ Omod1 >

B−1 TLJF (I). 2B − 1

Consequently, O = TLJF (I) + Omod2 + Omod3 + · · · + Omod0 > TLJF (I) + =⇒

TOP T (I) ≥

(B − 1)2 B2 TLJF (I) = TLJF (I), 2B − 1 2B − 1

O B > TLJF (I). B 2B − 1

In both cases TLJF (I) ≤ 2B−1 B TOP T (I), completing the proof.

■

Remark 5. For B ≥ 2, the competitive ratio of LJF decreases monotonically as the batch size B increases. The competitive ratio upper bound achieves its maximum value of 23 when B = 2.

3.2

Better Algorithm: ISJL (Warm-Up case, B=2)

Motivated by the trade-off between the absolute fairness of LJF (fair for any α ≥ 0) and its severe throughput limitations, we propose a parametric algorithm that permits a bounded fairness violation (within a parameter α ≥ 0) to achieve significant throughput gains. This algorithm, called Insert Short Jobs with Limit (ISJL), takes α as its input parameter. Given the complexity of ISJL, we first describe and analyze it for the warm-up case of B = 2. The algorithm consists of two phases. Phase One (Batch Initialization): The algorithm first selects the longest waiting job, denoted o1 . To determine which jobs can be batched with o1 without exceeding the allowed fairness violation, a threshold is calculated: q = min{o1 − o2 + β, 2α}, where o2 is the second longest waiting job, and β is a parameter related to α, with β ∈ [0, 2α]. The algorithm then prioritizes selecting the longest jobs whose processing time is less than or equal to q to run concurrently with o1 . This process continues until adding the next available job would cause the cumulative size of the batched short jobs to exceed the threshold q. At this point, the algorithm proceeds the second longest job, o2 , alongside o1 . Since Phase One does not guarantee that o1 and o2 will finish simultaneously, a Phase Two is required to schedule new jobs as resources become available. Exceptionally, when o2 is less or equal to α, which allows for o3 , the third longest waiting job to be processed right after o2 and in parallel with o1 , Phase TWO is triggered directly. Phase TWO (Batch Finalization): This phase is triggered when a resource is freed, either by the completion of a job, or by the length of o2 . The algorithm checks the current decode length of the occupied resource, denoted by am . As long as am ≤ α, the algorithm assign the longest unprocessed job to the freed resource. The algorithm then iterates between Phase One and Phase Two, dynamically forming new

12

batches or adding jobs to existing ones as resources become available, until all requests are completed. The complete formal procedure for ISJL is presented in Algorithm 2. Next, Theorem 2 shows√ that the lower bound of competitive ratio of ISJL is √ a function of β, with the best choice β=

17−1 α ≈ 0.78α gives the maximum lower bound at 25+38 17 ≈ 0.77. 4

Algorithm 2 Insert Short Jobs with Limit (ISJL) √

α ≥ 0, β = 17−1 α. 4 2: Phase ONE 3: Denote o = {o1 ≥ o2 ≥ · · · ≥ on } for all undo jobs 4: if o2 ≤ α then 5: goto Phase TWO 6: ok ← max{oi ∈ o | oi ≤ min{o1 − o2 + β, 2α}} 7: oarray ← [ ] 8: for i = k, . . . , n do P 9: if oi + oarray > min{o1 − o2 + β, 2α} then 10: continue 11: else 12: Pappend oi to oarray 13: if oarray > α then P 14: run oarray alone for oarray − α 15: run o1 with the rest part of oarray 16: run o2 with the rest part of o1 17: Phase TWO 18: while One of the resource is freed do 19: om ← max{oi ∈ o | ai = 0} 20: am ← the current output length on the occupied resource 21: if am ≤ α then 22: run om until one of the resource is freed 23: else 24: break 25: repeat from step 1 1: Input:

Remark 6 (ISJL as a hybrid continuous-batching policy). ISJL occupies a deliberate middle ground between static and continuous batching. Phase ONE is semi-static: it constructs a structured shortjob pack around the longest active request o1 and holds this configuration for a bounded period, ensuring that all co-batched requests enter the decode phase with KV caches within α tokens of each other. Phase TWO is fully event-driven and implements continuous batching: the moment a processing slot is freed and the current maximum progress satisfies Amax (t) ≤ α, the next longest unprocessed request is immediately admitted. This hybrid design is intentional. The semi-static Phase ONE enforces the fairness constraint by carefully controlling the initial KV-cache spread of each new cohort of requests. The continuous-batching Phase TWO then recaptures efficiency by eliminating idle time as soon as fairness permits new admissions.

13

Theorem 2 (Competitive ratio of Algorithm 2). For B = 2, we have

CR(ISJL) ≥

Proof of Theorem 2.

 α+2β 4α  }, min{ α+3β , 6α−β

β ∈ [0, α]

  2α+β 4α , 6α−β }, min{ 2α+2β

β ∈ (α, 2α]

Let TISJL (I) be the makespan produced by Algorithm 2 and let TOP T (I)

be the optimal makespan for the same input instance. Then by Lemma 1, it suffices to show that  α+2β 4α  }, min{ α+3β , 6α−β

TOP T (I) inf =  I TISJL (I)  2α+β 4α min{ 2α+2β , 6α−β },

β ∈ [0, α] β ∈ (α, 2α]

We first quantify the loss in Phase ONE, starting by define a term stage: Definition 1. A stage is initiated whenever line 2 of Algorithm 2 is reached. For the rth stage, denote the current largest two undo jobs by Lr (length o1 ) and Sr (length o2 ), and the pack of short jobs by Pr . One stage in Phase ONE is formally defined by the following sequence of actions: i) Execute Pr alone if Pr > α for Pr − α tokens; ii) Execute Lr in parallel with Pr until Pr finishes; iii) Execute Lr in parallel with Sr until either Lr or Sr finishes. Next, we point out that the loss in any stage of Phase ONE can produce loss from two aspects: over-inserting or under-inserting (See Figure 2 for intuition). Lemma 2 quantify the worst competitive ratio in Phase ONE under the over-inserting case, while Lemma 3 provides a property to bound the competitive ratios in the under-inserting case.

Figure 2: Over and Under Inserting

Lemma 2 (Cost of over-inserting 2). For any stage r of Phase ONE, the worst competitive ratio

14

caused by over-inserting is given by:  α + 2β    α + 3β , CR(ISJL) ≥  2α + β   , 2α + 2β Proof of Lemma 2.

β ∈ [0, α] β ∈ (α, 2α]

Denote Qr as the package of small jobs that could be executed in parallel with

Pr in optimal scheduling. Underlying constraints for over-inserting are Lr ≥ Sr ≥ Pr ≥ Qr ≥ 0, Pr ≤ min{Lr − Sr + β, 2α}, Lr > min{2α, Pr + α}, Sr + Pr > Lr . Because CR(ISJL) =

Lr + Pr Sr + Pr + Qr

strictly increases in Lr and strictly decreases in Sr and Qr , the minimum is approached at the boundary Sr = Lr and Qr = Pr . The constraints reduce to 0 < Pr ≤ β,

Pr ≤ 2α,

Lr > min{2α, Pr + α}.

For fixed Lr the function (Lr + Pr )/(Lr + 2Pr ) decreases in Pr , so we take Pr as large as allowed; for fixed Pr it increases in Lr , so we take Lr as small as allowed. Two cases: • If 0 ≤ t ≤ α, then Pr < t ≤ α, hence min{2α, Pr + α} = Pr + α and the smallest admissible Lr is Lr ↓ Pr + α. Letting Pr ↑ β gives inf CR(ISJL) =

α + 2β . α + 3β

• If α < β ≤ 2α, we can choose Pr with α ≤ Pr < β, so min{2α, Pr + α} = 2α and the smallest admissible Lr is Lr ↓ 2α. Letting Pr ↑ β gives inf CR(ISJL) =

2α + β 2α + β 3 = ≤ , 2α + 2β 2(α + β) 4

matching continuously the first case at β = α. The overall infimum decreases from 1 (β = 0) down to 2/3 (β = 2α), completing the proof. Lemma 3 (Cost of under-inserting). In any stage r of Phase ONE, we have CR(ISJL) ≥ Proof of Lemma 3.

4α 6α − β

Underlying constraints for under-inserting are Lr ≥ Sr ≥ Pr ≥ 0, Lr − Sr + β < Pr ≤ 2α. 15

■

From Lr − Sr + β < Pr we have Lr < Sr + Pr − β. For fixed Sr , Pr , CR(ISJL) = (Sr + Pr )/(Lr + Pr ) is minimized by taking Lr as large as allowed, i.e., Lr ↑ Sr + Pr − β. Hence CR(ISJL) ≥

Sr + Pr . Sr + 2Pr − β

For fixed β, Pr with Pr > β, the right-hand side increases in Sr , so the minimum over Sr ≥ Pr occurs at Sr = Pr : CR(ISJL) ≥

2Pr . 3Pr − β

For fixed β, this expression decreases in Pr , so using the bound Pr ≤ 2α and feasibility Pr > β gives CR(ISJL) ≥

4α . 6α − β

The bound is tight: it is approached by choices Sr = Pr = 2α and Lr arbitrarily close to Sr + Pr − β from below. When β = 0, this yields CR(ISJL) ≥ 2/3.

■

Therefore, with Lemmas 2 and 3, we obtain the adversarial competitive ratio in Phase ONE:  4α α + 2β   min{ α + 3β , 6α − β },

TOP T (I) ≥  TISJL (I) 2α + β 4α  min{ , }, 2α + 2β 6α − β

β ∈ [0, α] β ∈ (α, 2α]

Consider Phase TWO, we introduce the following proposition proved in Graham (1969): Proposition 3 (Theorem 2 in Graham (1969)). Without the limit α, the makespan of Phase TWO 1 is at most ( 34 − 3B ) TOP T (I).

Noticing that the competitive ratio in Phase TWO is larger than that obtained in Phase ONE, for B = 2. Therefore, in both Phase ONE and Phase TWO we have  α + 2β 4α   min{ , },  α + 3β 6α − β TOP T (I) ≥  TISJL (I) 2α + β 4α  min{ , }, 2α + 2β 6α − β which completes the proof.

β ∈ [0, α] β ∈ (α, 2α] ■

Remark 7. The best choice for parameter β can be obtained by solving the inequality. Noticing the monotony of the two functions, the best β solves α + 2β 4α = . α + 3β 6α − β √

Therefore, β = √

17−1 α ≈ 0.78α gives the maximum lower bound for the competitive ratio at 4

25+ 17 ≈ 0.77. 38

16

Remark 8. A naive choice for β is β = α, which gives a competitive ratio of 45 in under-inserting and a competitive ratio of 34 in over-inserting. Therefore, the overall competitive ratio of this simplified choice is bounded by 34 = 0.75.

3.3

Generalization (B ≥ 2)

Motivated by the fact that the competitiveness of the insertion rule used in Phase TWO approaches 3/4 as B grows, as shown in Proposition 3, and to keep the mechanism simple, we generalize ISJL by fixing β = α. Let the unprocessed job lengths be ordered o = {o1 ≥ o2 ≥ · · · ≥ on }. For B ≥ 2 workers, define M = min{B, |{i : oi > α}|}. If o2 ≤ α, we immediately invoke Phase TWO; otherwise we build a batch around o1 by allocating short jobs to accompany each of the next M − 1 longest “long” jobs. For each j ∈ {2, . . . , M } set a per-worker packing budget capj = min{2α, o1 − oj + α}. Let ok be the largest job length not exceeding min{2α, o1 − oM + α}; we then scan the jobs oi for i ≥ k in decreasing order and greedily assign each to the largest index j ∈ {2, . . . , M } whose current packed total plus oi stays within capj . This produces disjoint P j j }M warray ≤ capj by construction. short-job packs {warray j=2 with Scheduling proceeds in two stages while holding o1 on worker 1. First, on each worker j ∈ {2, . . . , M } we run a prefix of its packed short jobs of total length exactly α in parallel; this ensures that no worker advances more than α units ahead of the slowest active job and thus bounds the fairness violation by α. Second, we continue on each worker j with the remaining tail of its pack, P j − α}, still in parallel with o1 . These two stages constitute Phase of length tailj = max{0, warray ONE for the current batch. Phase TWO handles fill-in while any resources are idle. Let Amax be the maximum remaining processing time across all jobs currently running. As long as Amax ≤ α, we place the longest unprocessed job on any idle worker; if Amax > α, we stop admitting new jobs and return to Phase ONE to rebuild packs around the current longest jobs. The algorithm alternates between these two phases, rebuilding batches as the set of unprocessed jobs changes, until all work completes. With β = α, the packing budgets capj and the α-prefix rule together enforce the α-bounded fairness constraint while exploiting the available parallelism across B workers. Theorem 3 (Competitive ratio of Algorithm 3). For any B ≥ 2, we have 3 CR(ISJL) ≥ . 4 Proof of Theorem 3.

By Proposition 3, we know that the competitive ratio of Phase TWO is

3B bounded by 4B−1 > 34 . Consider two cases in Phase ONE:

i) (Under-inserting) Inserting algorithm is not optimal in Phase ONE, i.e., |Pr | < |Popt |. ii) (Over-inserting) Inserting P causes additional idle time, i.e., another job that could have been run in parallel is now running after L and S (which requires that Lr < Sr + |Pr |).

17

Algorithm 3 Generalized Insert Short Jobs with Limit (ISJL, B ≥ 2) 1: Input: α ≥ 0, number of workers B ≥ 2 2: Phase ONE 3: Denote o = {o1 ≥ o2 ≥ · · · ≥ on } for all undo jobs  4: M ← min B, |{i | oi > α}| , ok ← max{oi | oi ≤ min{2α, o1 − oM + α}} 5: for j = 2, . . . , B do j 6: warray ← [] 7: for j = 2, . . . , M do 8: capj ← min{2α, o1 − oj + α} 9: for i = k, . . . , n do 10: assigned ← false 11: for j = M + 1, . . . , B do P j 12: if assigned = false and oi + warray ≤ α then j 13: append oi to warray ; assigned ← true 14: for j = M, . . . , 2 do P j ≤ capj then 15: if assigned = false and oi + warray j 16: append oi to warray ; assigned ← true 17: for j = 2, . . . , B do j of length 18: run a prefix of warray P α on worker j in parallel 19: idle worker 1 for min{max{ oM array − α, 0}, α} 20: for j = 2, . . . , B do j 21: run the remaining part of warray of length tailj on worker j, in parallel with o1 22: Phase TWO 23: while a resource is idle do 24: Amax ← current maximum output length among all running jobs 25: om ← max{oi ∈ o | oi is undo} 26: if Amax ≤ α then 27: run om on an arbitrary idle worker 28: else 29: break 30: repeat from Phase ONE with the remaining undo jobs

18

In case i), for any i ∈ [2, B], consider o1 and oi , idle time is bounded by Lemma 3. In case ii), for any i ∈ [2, B], consider o1 and oi , idle time is bounded by Lemma 2. Therefore, the lower bound of overall competitive ratio is given by the minimum over the two phases, 3 CR(ISJL) ≥ , 4 completing the proof.

3.4

■

Robust Scheduling under Prediction Uncertainty

In practice, the exact decoding length oi of request i is unknown upon arrival. Instead, the system may have access to a prediction interval [ℓi , ui ] such that ℓi ≤ oi ≤ ui . We define the (minimum) prediction-interval accuracy as κ := min i

Robust-ISJL (Upper-Bound ISJL).

ℓi ∈ (0, 1]. ui

We define Robust-ISJL by running Algorithm 3 using

the proxy sizes obi := ui wherever job sizes are used for sorting, forming packs, and computing quantities such as M and capj . During execution, the fairness check always uses the true runtime progress {ai (t)} (e.g., the Phase TWO condition Amax (t) ≤ α is evaluated using the current maximum progress among the active jobs, as in Algorithm 3). The following theorem shows that our Robust-ISJL satisfies the fairness constraint, and the proof can be found in Appendix EC.2. Theorem 4 (Fairness of Robust-ISJL). Robust-ISJL satisfies the fairness constraint (1) for any α ≥ 0. Why a naive κ-multiplicative bound is invalid.

A tempting approach is to prove TOPT (Iu ) ≤

ρTOPT (I) for ρ := 1/κ by time-stretching an optimal schedule for I. This is false under the tokengap fairness constraint (1): time-stretching can amplify progress gaps and violate feasibility (it would generally require relaxing α to ρα). A prediction-error dependent guarantee.

Define the request-level upper-bound slack

ei := ui − oi ≥ 0, and the aggregate upper-bound overestimation error ∆ :=

n X i=1

n X ei = (ui − oi ). i=1

Let Pα,B (I) denote the family of partitions of [n] into groups G such that |G| ≤ B and max oi − min oi ≤ α. i∈G

i∈G

19

For each request, define the upper-bound slack ei := ui − oi . The packable residual prediction error is ∆pack α,B (I, u) :=

X

min

P∈Pα,B (I)

G∈P

max ei . i∈G

Theorem 5 (Competitive guarantee of Robust-ISJL under interval uncertainty). For any B ≥ 2 and any instance with ℓi ≤ oi ≤ ui , Robust-ISJL satisfies  4 pack TRobust-ISJL (I) ≤ TOPT (I) + ∆α,B (I, u) . 3 Equivalently, TOPT (I) 3 1 ≥ · . TRobust-ISJL (I) 4 1 + ∆pack (I, u)/TOPT (I) α,B

In particular, when predictions are perfect, i.e., ui = oi for all i, we have ∆pack α,B (I, u) = 0 and recover CR(Robust-ISJL) ≥ 3/4. Proof of Theorem 5.

Let Iu denote the proxy instance whose request lengths are exactly ui .

Running Algorithm 3 on Iu yields makespan TISJL (Iu ). Executing the same batching decisions on the realized instance I cannot take longer because each request requires only oi ≤ ui service; early completions only remove jobs from the active set. Hence, TRobust-ISJL (I) ≤ TISJL (Iu ). By Theorem 3, 4 TISJL (Iu ) ≤ TOPT (Iu ). 3 We upper-bound TOPT (Iu ) using an optimal α-fair schedule for the realized instance I. After this schedule completes, request i has received oi units of service. To complete the proxy instance Iu , request i requires an additional ei = ui − oi units of service. Fix any partition P ∈ Pα,B (I). For each group G ∈ P, process all requests in G together for maxi∈G ei time steps, removing request i once it has received its additional ei units of service. Capacity feasibility follows from |G| ≤ B. We now verify fairness. At the beginning of the residual processing for group G, the progress values of requests in G are {oi : i ∈ G}. By the definition of Pα,B (I), max oi − min oi ≤ α. i∈G

i∈G

While active requests in G are processed together, their progress values increase in lockstep, so the max–min progress gap among active requests is unchanged. When a request completes its residual work and is removed, the max–min gap cannot increase. Therefore, each residual group is processed 20

by a feasible α-fair schedule. The residual tail length induced by partition P is X G∈P

max ei . i∈G

Minimizing over all feasible partitions yields TOPT (Iu ) ≤ TOPT (I) + ∆pack α,B (I, u). Combining (1)–(3) gives the stated result.

■

Corollary 1 (Scale-normalized robustness). Let O(I) :=

n X

oi ,

i=1

∆ = ε̄(I) := O(I)

Pn (u − oi ) i=1 Pn i i=1 oi

denote the total realized token workload and the average upper-bound slack per realized token. Then Robust-ISJL satisfies TOPT (I) 3 1 ≥ · . TRobust-ISJL (I) 4 1 + B ε̄(I) In particular, if ui ≤ (1 + ε)oi for all i, then TOPT (I) 3 1 ≥ · . TRobust-ISJL (I) 4 1 + Bε The proof of Corollary 1 can be found in Appendix EC.2. Remark 9 (Large-scale interpretation of the robust guarantee). Theorem 5 strengthens the aggregateerror bound by recognizing that residual overestimation errors can often be processed in fair batches. P The old aggregate term ∆ = i (ui −oi ) corresponds to the pessimistic singleton partition, in which every residual error is processed separately. When many requests have realized lengths within the same α-window, the effective residual penalty can be much smaller. For example, if all realized lengths lie within one α-window and all residual errors equal e, then ∆ = ne,

∆pack α,B =

lnm B

e,

so the aggregate-error bound can overstate the residual penalty by a factor approaching B. Corollary 1 clarifies the large-scale behavior. Although ∆ grows with the number of requests, the optimal makespan also grows with the realized token workload. For fixed batch size B, the guarantee depends on the average upper-bound slack ε̄(I) = ∆/O(I), not directly on n. Thus, large-scale operation does not by itself weaken the robustness certificate. The certificate deteriorates when prediction intervals are systematically loose relative to realized output lengths. In deployment, this means Robust-ISJL should use calibrated upper bounds with controlled average slack, rather 21

than extremely conservative global upper bounds such as the maximum context length for every request. Fairness remains robust because admission decisions are always checked using realized run-time progress; interval errors affect only the planning order and hence the efficiency guarantee.

3.5

Online Arrivals: An Extension and Its Limitation

Consider an online release-date instance I r = {(ri , oi )}ni=1 , where request i is revealed to the scheduler at release time ri . At time t, the scheduler knows only the released unfinished requests. Let Q(t) denote the queue of released requests that have not yet started service. Online-ISJL implements Algorithm 3 in a rolling manner. When Phase ONE is invoked at time t, the algorithm sorts only the currently available queue Q(t) and computes M , ok , and the packing budgets capj using this released set. Requests that arrive during execution are inserted into Q(t) but do not change the currently running batch. During Phase TWO, whenever a slot becomes free, the algorithm admits the longest currently released request in Q(t) if the usual fairness check Amax (t) ≤ α is satisfied; if the check fails, the algorithm returns to Phase ONE. If Q(t) is empty, the server waits until the next request arrives. Proposition 4 (Fairness of Online-ISJL). For any arrival sequence {(ri , oi )}ni=1 and any α ≥ 0, Online-ISJL satisfies the fairness constraint (1) at every time step. Proposition 4 states that our Online-ISJL is fair and the proof can be found in Appendix EC.2. Although it is hard to provide an upper bound of the competitive ratio of Online-ISJL, the next proposition provides a lower bound to the online setting. Proposition 5. Fix any finite α ≥ 0 and set B = 2. In the online release-date model under the same nonpreemptive service convention as the main algorithms, no deterministic online scheduling policy can guarantee competitive ratio 3/4 against a clairvoyant offline optimum that knows all release times in advance. More precisely, for every deterministic online policy and every δ > 0, there exists an online instance such that r TOPT (I r ) ≤ TAr (I r )

√ 5−1 3 +δ < , 2 4

r where TOPT is the optimal α-fair makespan respecting release times.

Proof of Proposition 5.

Fix a large length L and release one request J1 of length L at time 0. Let

s be the time at which the deterministic online policy first starts processing J1 . If the policy never starts J1 , the adversary releases no more requests and the competitive ratio is zero. Hence assume s < ∞. The adversary considers two continuations. 22

First, suppose no additional request arrives. Then the online policy completes no earlier than s + L, whereas the offline optimum starts J1 at time 0 and completes at time L. Thus, r TOPT L ≤ . r TA s+L

Second, suppose a second request J2 of length L is released at time r = s + α + ε, where ε > 0. At time r, request J1 has already advanced by α + ε tokens, whereas J2 has progress zero. Therefore J2 cannot be admitted into the same active batch as J1 without violating the αfairness constraint. Under the nonpreemptive service convention, the online policy must complete J1 before processing J2 , so TAr ≥ s + 2L. The clairvoyant offline optimum instead waits until time r and then starts J1 and J2 together. Their progress values remain equal throughout service, so the schedule is α-fair and completes at time r TOPT ≤ r + L = s + α + ε + L.

Thus,

r TOPT s+α+ε+L . ≤ r TA s + 2L

Let x = s/L and η = (α + ε)/L. Combining the two possible continuations, the adversary can force

r TOPT ≤ min TAr



1 1+x+η , 1+x 2+x

 .

Taking L sufficiently large makes η arbitrarily small. Hence the best ratio any deterministic online policy can guarantee is at most  sup min x≥0

1 1+x , 1+x 2+x

 .

The first function is decreasing in x, and the second is increasing in x. The maximum of the minimum occurs when they are equal: 1 1+x = 1+x 2+x

⇐⇒

x2 + x − 1 = 0.

√ √ Thus x = ( 5 − 1)/2, and the common value is also 5−1 2 .

■

Proposition 5 clarifies the scope of the offline competitive-ratio result. Online-ISJL remains event-driven and causal. The difficulty is the release-time information structure. A clairvoyant offline scheduler can delay an available long request to wait for a future compatible request, whereas an online scheduler does not know whether such a request will arrive. This waiting-versus-processing

23

trade-off is absent from the offline backlog model and requires a different online analysis. Accordingly, the 3/4-competitive theorem should be read as an offline guarantee for a backlogged request pool. In deployment, Online-ISJL is a natural rolling implementation: it applies the same resource-fair packing logic to the currently released queue and admits new requests whenever the runtime fairness check permits. Obtaining positive competitive guarantees under stochastic arrivals, bounded lookahead, or batching-window policies is an important direction for future work.

4

Theoretical Extensions: Tighter Competitive Ratio as a Function of α

In Section 3, we established a lower bound of 34 on the competitive ratio of Algorithm ISJL, which holds for any value of α (Theorem 3). This result prompts two natural questions: How does the competitive ratio vary with α? And for which values of α is the 34 bound tight? To address these questions, we derive a tighter, parameterized characterization of the competitive ratio. Our approach involves categorizing adversarial instances into three distinct types and then determining which type dictates the worst-case performance for a given α. For consistency with Algorithm 3, we conduct this analysis with the parameter β = α.

4.1

Adversarial Behaviors

To analyze the competitive ratio with respect to every α, we start with discussing two adversarial behaviors: over-inserting and under-inserting. Following a similar line of reasoning as in the previous proof, we begin by examining the case B = 2, and then generalize the argument to the case B ≥ 2. Over-Inserting

As illustrated in Fig. 2, the over-inserting behavior is characterized by the con-

straints o3 ≤ o1 − o2 + α, o3 ≤ 2α and o1 > min{o3 + α, 2α}. The competitive ratio is then given by CRover =

o1 + o 3 . o2 + o 3 + o 4

Lemma 4 (Over-Inserting: B = 2). For each fixed γ ∈ (0, 1), the greatest lower bound of CRover over the feasible region satisfies  1+γ   ,  1 + 2γ CRover (γ) ≥ 2−γ    , 3 − 2γ The proof can be found in Appendix EC.3.

24

0 < γ ≤ 12 , 1 2 ≤ γ < 1.

Under-Inserting

Under-inserting yields an instance in which placing o3 before o2 leads to a

shorter makespan. To construct such a case, it suffices to require o1 − o2 + α < o3 ≤ 2α. Consider o2 + o 3 . CRunder = o1 + o 3 Lemma 5 (Under-Inserting: B = 2).  1+γ   ,  1 + 2γ CRunder (γ) ≥  2(1 + γ)  ,  3+γ

0 < γ ≤ 13 , 1 3 ≤ γ < 1,

CRunder (γ) is strictly decreasing on (0, 13 ] and strictly increasing on [ 13 , 1), with a unique global minimum at γ = 31 equal to 45 ; finally, limγ→0+ CRunder (γ) = limγ→1− CRunder (γ) = 1. The proof can be found in Appendix EC.3.

Figure 3: Jigsaw Effect Jigsaw Effect

As shown in Fig. 3, the jigsaw effect arises when concatenating a set of smaller

jobs that happens to produce a makespan comparable to that of another set of larger jobs. The adversarial case can be formulated as o = {2B − 1, 2B − 1, 2B − 2, 2B − 2, . . . , B + 1, B + 1, B, B, B}. 3B Recall that Proposition 3 gives a competitive ratio no less than 4B−1 under this adversary, and 3B thus the bound won’t be effective because 4B−1 > 34 , indicating that the jigsaw effect is dominated

by over-inserting.

4.2

Dominant Behavior Respecting γ and Generalization

Let γ = α/o1 ∈ (0, 1) and denote by CR(γ) the greatest lower bound of CR(ISJL) over all feasible instances with fixed γ. From the preceding analysis in Lemma 4 and Lemma 5 we have the behavior-specific bounds  1+γ  ,  1 + 2γ CRover (γ) =   2−γ , 3 − 2γ

0 < γ ≤ 12 , 1 2 ≤ γ < 1,

 1+γ   ,  1 + 2γ CRunder (γ) = 2(1 + γ)   ,  3+γ

25

0 < γ ≤ 31 , 1 3 ≤ γ < 1.

The overall worst-case lower bound is the lower envelope CR(γ) = min{CRover (γ), CRunder (γ)}. The following theorem explicitly gives the piecewise function of CRunder (γ) and proves that this lower bound is the same for B = 2 and B > 2 cases. Theorem 6 (Generalized global competitive ratio as a function of γ). ∀B ≥ 2, The overall worstcase lower bound CR(γ) admits the single piecewise description  1+γ   ,  1 + 2γ CR(γ) = 2−γ    , 3 − 2γ

0 < γ ≤ 12 , 1 2 ≤ γ < 1,

which is strictly decreasing on (0, 12 ], strictly increasing on [ 12 , 1), attains its unique global minimum CR( 12 ) = 43 , and satisfies lim CR(γ) = lim CR(γ) = 1. γ→1−

γ→0+

Proof of Theorem 6

When B = 2, it suffices to compare the behavior-specific bounds on the

relevant sub-intervals and to establish monotonicity on each branch. In this proof, we start by discussing three regimes of γ under B = 2. And in the last part of the proof, we generalize this result to B ≥ 2 cases. Small γ (0 < γ ≤ 13 ).

In this range the two adversarial patterns coincide: CRover (γ) = CRunder (γ) =

Hence CR(γ) =

1+γ . 1 + 2γ

1+γ , 1 + 2γ

which is strictly decreasing on (0, 13 ], with limγ→0+ CR(γ) = 1 and CR( 13 ) = 45 . Intermediate γ ( 13 < γ ≤ 12 ).

Here we compare the two candidate bounds:

1+γ 2(1 + γ) ≤ 1 + 2γ 3+γ

⇐⇒

1 2 ≤ 1 + 2γ 3+γ

⇐⇒

γ ≥ 13 .

Thus on γ ∈ ( 13 , 12 ] the over-inserting bound dominates, and CR(γ) =

1+γ , 1 + 2γ

which remains strictly decreasing up to CR( 12 ) = 34 by the derivative computed above.

26

Large γ ( 21 ≤ γ < 1).

For γ ≥ 12 , the over-inserting bound switches to CRover (γ) =

2−γ , 3 − 2γ

which is strictly increasing on [ 12 , 1). Moreover, 2−γ 2(1 + γ) ≤ 3 − 2γ 3+γ

⇐⇒

(2 − γ)(3 + γ) ≤ 2(1 + γ)(3 − 2γ)

⇐⇒

0 ≤ 3γ(1 − γ),

which holds for all γ ∈ [0, 1]. Hence the over-inserting bound is again the lower envelope on [ 12 , 1): CR(γ) =

2−γ . 3 − 2γ

2−γ = 1. Finally, limγ→1− CR(γ) = limγ→1− 3−2γ

Generalization.

∀i ∈ [2, B], consider o1 and oi , the total idle time is bounded by Lemma 4 and

Lemma 5. Therefore, the competitive ratio in Phase ONE of Algorithm 3 is bounded by CR(γ). Proposition 3 ensures that Phase TWO won’t make the competitive ratio worse. Combining the three regimes yields  1+γ   ,  1 + 2γ CR(γ) = 2−γ    , 3 − 2γ

0 < γ ≤ 21 , 1 2 ≤ γ < 1,

which is strictly decreasing on (0, 12 ] and strictly increasing on [ 12 , 1). Since the two branches meet continuously at γ = 12 and are strictly monotone on either side, CR attains a unique global minimum at γ = 21 with value 34 , and satisfies the boundary limits limγ→0+ CR(γ) = limγ→1− CR(γ) = 1. ■

Figure 4: Competitive Ratio as a Function of γ

27

5

Profit and Cost Alignment under Linear Pricing

The preceding adversarial analysis establishes that ISJL has a worst-case throughput guarantee under the resource-fairness constraint. We now connect this throughput analysis to the operator’s economic objective. Commercial LLM inference is typically sold through token-metered API contracts. Leading providers (OpenAI, Anthropic, Deepseek, Google Gemini) publish modelspecific unit prices for tokens, usually quoted per one million tokens (OpenAI 2026, Anthropic 2026, DeepSeek 2026, Google 2026). Thus, although providers may use different coefficients for tokens, the usage charge is linear in the realized token counts. Consistent with the token-level abstraction in Section 2, we represent this practice by a single effective linear price pi = ρ0 oi for request i for some unit token price ρ0 > 0. The economic tension studied below is that this token-metered revenue is additive across requests, whereas the cost of a batched inference step is driven by the largest active request in the batch. Resource-fair scheduling is therefore a mechanism for aligning linear token-metered revenue with max-driven batch cost. Accepted workload and linear revenue. Fix an accepted request instance I = {o1 , . . . , on } and let O(I) :=

n X

oi

i=1

denote the total token workload. Under linear token pricing, the total revenue is R(I) = p0

n X

oi = p0 O(I),

(2)

i=1

which is independent of the schedule used to serve the accepted workload. Therefore, for a fixed accepted instance, maximizing profit is equivalent to minimizing the schedule-dependent inference cost. Token-progress cost. At the beginning of service step t, let S (t) be the active batch selected (t)

by a schedule A. Recall from Section 2 that ai

is the number of tokens already processed for

(t) (t) (t) request i. Define ri := ai + 1, so that ri is the index of the token currently being processed. (t) This shift by one is only notational; it leaves the fairness gap unchanged, since maxi∈S (t) ri − (t) (t) (t) mini∈S (t) ri = maxi∈S (t) ai − mini∈S (t) ai . Thus any schedule satisfying constraint (1) also (t) (t) satisfies maxi∈S (t) ri − mini∈S (t) ri ≤ α.

We define the instantaneous cost of a nonempty batch as (t)

(t)

CA = c + τ |S (t) | max ri ,

(3)

i∈S (t)

where c ≥ 0 is the fixed cost of one service step and τ > 0 converts the max-driven resource

28

footprint into cost. The total inference cost and profit of schedule A are then TA (I)

CA (I) =

(t)

X

ΠA (I) = R(I) − CA (I).

CA ,

(4)

t=1

Theorem 7 (Profit decomposition and externality bound). For any feasible schedule A serving instance I, define Q(I) :=

oi n X X

n

k=

i=1 k=1

1X oi (oi + 1), 2

(5)

i=1

and define the batching externality of A as TA (I)

EA (I) :=

X X  t=1 i∈S (t)

(t) (t) max rj − ri (t) j∈S

 .

(6)

Then profit admits the decomposition ΠA (I) = R(I) − τ Q(I) − cTA (I) − τ EA (I).

(7)

Moreover, if A satisfies the fairness constraint (1), then EA (I) ≤ αO(I).

(8)

The proof of Theorem 7 can be found in Appendix EC.4. Theorem 7 separates profit into four terms. The revenue term R(I) and the intrinsic resource term τ Q(I) are fixed once the accepted workload is fixed. The schedule affects profit only through two terms: the time cost cTA (I) and the batching externality cost τ EA (I). The throughput analysis developed earlier controls the first schedule-dependent term, while the fairness constraint controls the second. Thus the throughput theory is not separate from the economic objective; it controls one component of profit, and resource fairness controls the other. Theorem 8 (Additive profit guarantee for ISJL). Let Fα (I) be the set of schedules satisfying the fairness constraint (1) on instance I. Define Π⋆α (I) := max ΠA (I), A∈Fα (I)

and let A⋆π ∈ Fα (I) be a profit-maximizing fair schedule with makespan Tπ⋆ (I) := TA⋆π (I). Suppose a fair algorithm A has throughput competitive ratio at least ρ ∈ (0, 1], or equivalently, TA (I) ≤

1 TOP T (I), ρ

29

(9)

where TOP T (I) = minB∈Fα (I) TB (I). Then ΠA (I) ≥ Π⋆α (I) − c



 1 − 1 Tπ⋆ (I) − τ αO(I). ρ

(10)

In particular, applying Theorem 3 to ISJL gives c ΠISJL (I) ≥ Π⋆α (I) − Tπ⋆ (I) − τ αO(I). 3

(11)

The proof of Theorem 8 can be found in Appendix EC.4. A multiplicative competitive ratio for profit is generally not the right object, because profit may be close to zero or even negative depending on the price and cost parameters. Theorem 8 instead gives an additive guarantee. ISJL can lose profit relative to the best fair profit schedule only through two channels: an overhead term caused by imperfect makespan optimality, and an externality term bounded by τ αO(I). When α is small, ISJL is close to the cost alignment of LJF; when c is large, ISJL’s throughput guarantee becomes economically valuable. Proposition 6 (Pairwise profit comparison). For any two feasible schedules A and B serving the same accepted instance I, ΠA (I) − ΠB (I) = c (TB (I) − TA (I)) + τ (EB (I) − EA (I)) .

(12)

Consequently, since LJF has zero batching externality, ΠISJL (I) − ΠLJF (I) ≥ c (TLJF (I) − TISJL (I)) − τ αO(I).

(13)

Similarly, for FCFS, ΠISJL (I) − ΠF CF S (I) ≥ c (TF CF S (I) − TISJL (I)) + τ (EF CF S (I) − αO(I)) .

(14)

The proof of Proposition 6 can be found in Appendix EC.4. Proposition 6 makes explicit the tradeoff among the three main policies. LJF is the cost-alignment benchmark because it has ELJF = 0, but it may have a large makespan. FCFS may have small makespan, but it can have a large externality term. ISJL lies between them: it allows limited heterogeneity to recover throughput, while bounding the resulting externality by αO(I). In particular, ISJL is guaranteed to be more profitable than LJF whenever c (TLJF (I) − TISJL (I)) ≥ τ αO(I), and it is guaranteed to be more profitable than FCFS whenever the right-hand side of (14) is nonnegative. Proposition 7 (FCFS can have quadratic batching externality). Consider an instance with batch size B = 2 consisting of one long request of length L and L short requests of length 1. The FCFS 30

order places the long request first, followed by the L short requests. Then TF CF S (I) = L,

L(L − 1) . 2

(15)

ELJF (I) = 0.

(16)

EF CF S (I) =

In contrast, LJF has zero batching externality and makespan  L−1 , TLJF (I) = L + 2 

Therefore   L(L − 1) L−1 ΠLJF (I) − ΠF CF S (I) = τ . −c 2 2

(17)

In particular, for any fixed c ≥ 0 and τ > 0, LJF is more profitable than FCFS on this instance for all sufficiently large L. The proof of Proposition 7 can be found in Appendix EC.4. Proposition 7 shows why a pure throughput criterion can be economically misleading. FCFS finishes the adversarial instance faster than LJF, but it creates a quadratic batching externality by repeatedly co-batching a fresh short request with the increasingly advanced long request. When the fixed per-step cost c is small relative to the max-driven cost coefficient τ , the externality term dominates the additional steps required by LJF. This explains why LJF can be the lowest-cost policy in numerical experiments with very small c, while still being unattractive as a production scheduler because of its inferior throughput and latency. Corollary 2 (Makespan minimization as certified profit maximization). Fix an accepted workload I and a fairness parameter α. For any α-fair schedule A, ΠA (I) ≥ R(I) − τ Q(I) − τ αO(I) − cTA (I). Consequently, among schedules satisfying the same α-fairness constraint, minimizing makespan maximizes this certified lower bound on profit. Corollary 2 clarifies the role of the throughput objective in Section 2. The proof can be found in Appendix EC.4. We do not claim that the operator only cares about makespan, nor that ISJL is the pure cost minimizer for a fixed workload. Instead, α specifies the operator’s acceptable resource-misalignment budget, and the scheduling problem optimizes efficiency within that budget. LJF corresponds to the strict endpoint α = 0 and is therefore a natural cost-alignment benchmark. ISJL targets the interior of the frontier: it permits a controlled amount of resource heterogeneity in order to recover the throughput and latency benefits of continuous batching.

5.1

Practical Calibration of the Fairness Parameter α

The parameter α controls how much resource heterogeneity the scheduler is allowed to pool within the same active batch. A smaller α enforces stricter homogeneity and reduces the batching exter31

nality, but may restrict continuous batching and lower throughput. A larger α increases batching flexibility, but can increase the schedule-induced externality. Thus, α is a tuning parameter for the operator’s cost–service trade-off. The theoretical results above provide two complementary calibration principles. First, the feasible set expands with α, so a larger α weakly relaxes the scheduling constraint. Let Fα denote the set of schedules satisfying the α-fairness constraint, and let Tα⋆ (I) = min TA (I),

Θ⋆α (I) =

A∈Fα

O(I) Tα⋆ (I)

denote the optimal makespan and optimal throughput under fairness budget α, where O(I) =

P

i oi

is the total token workload. Proposition 8 (Nested throughput frontier). If 0 ≤ α1 ≤ α2 , then Fα1 ⊆ Fα2 ,

Tα⋆2 (I) ≤ Tα⋆1 (I),

Θ⋆α2 (I) ≥ Θ⋆α1 (I).

The proof can be found in Appendix EC.4. Second, the externality bound in Theorem 7 gives a direct cost-based way to choose an upper range for α. Suppose the operator wants the batchingexternality cost to be no more than a fraction δ of the intrinsic workload cost: τ EA (I) ≤ δτ Q(I). Since every α-fair schedule satisfies EA (I) ≤ αO(I), it is sufficient to choose α ≤ αcost (δ) := δ (t)

Q(I) . O(I)

(t)

Under the token-level abstraction with ri = ai + 1, Q(I) =

oi n X X i=1 k=1

k=

n X oi (oi + 1)

2

i=1

,

O(I) =

n X

oi .

i=1

Thus, Q(I) = O(I)

P

i (oi + 1) i oP

2

i oi

,

which can be estimated directly from historical request logs. In large samples, if L denotes the random request length, this ratio is approximately E[L2 ] + E[L] . 2E[L] Therefore, the natural scale of α depends on the workload length distribution; the same numerical value of α need not have the same operational meaning across workloads. In practice, we recommend the following calibration procedure. The operator first estimates the 32

request-length distribution from recent logs and constructs a candidate grid G of α values, scaled by either Q(I)/O(I) or by empirical length quantiles. The operator then replays historical workloads under ISJL for each α ∈ G and records throughput, latency, and the cost decomposition CISJL (I; α) = τ Q(I) + cTISJL (I; α) + τ EISJL (I; α). Because Q(I) and revenue are fixed for the accepted workload, the profit-relevant tuning problem is α⋆ ∈ arg min {cTISJL (I; α) + τ EISJL (I; α)} , α∈G

possibly subject to service-level constraints such as ThroughputISJL (α) ≥ ΘSLA ,

Latencyq,ISJL (α) ≤ LSLA , q

where LSLA is a target quantile of end-to-end latency. Equivalently, when a throughput or latency q SLA is binding, the operator may choose the smallest α that satisfies the service target, because smaller values provide tighter cost alignment.

5.2

Numerical Evidence

The preceding results show that the economic effect of scheduling can be separated into a makespan component and a batching-externality component. We now quantify these two components in simulation. The numerical design differs from our earlier pricing-centered experiment in one important respect: the main text uses only linear token pricing, and the accepted workload is fixed before schedulers are compared. Thus, within each replication, FCFS, LJF, and ISJL face exactly the same set of accepted requests and therefore generate exactly the same token-metered revenue. Any difference in profit is consequently a cost-side effect of scheduling. Experimental design. We generate n = 400 potential requests. Each request length is drawn independently as oi ∼ Uniform{1, 2, . . . , 1000}. Consistent with the linear-pricing model in (2), request i is quoted price pi = p0 oi , where p0 = p/500 and p = 1. We retain the same length-dependent acceptance model used in the original numerical study. Specifically, requests are divided into ten length buckets [1, 100], [101, 200], . . . , [901, 1000], and a request in bucket b ∈ {1, . . . , 10} accepts with probability Pr(accept) = max{0, 1 − kb pi },

kb =

1 . p0 (2b − 1)100

After acceptance is realized, the accepted workload is held fixed and served by all scheduling policies. We compare FCFS, LJF, and ISJL with α ∈ {50, 100, 150, 250, 300, 400, 500} under batch size B = 50. The cost parameters are c = 0.0005 and τ = 10−6 . For each schedule, we compute

33

Table 1: Profit and cost decomposition under linear pricing, n = 400, B = 50 Policy

Profit

Cost

τQ

cT

τE

Throughput

Gain vs. LJF

Avg. extent

FCFS LJF ISJL(α = 50) ISJL(α = 100) ISJL(α = 150) ISJL(α = 250) ISJL(α = 300) ISJL(α = 400) ISJL(α = 500)

128.73 163.82 162.53 161.10 159.59 156.30 154.71 151.31 147.82

68.41 33.31 34.60 36.03 37.55 40.83 42.43 45.83 49.32

32.07 32.07 32.07 32.07 32.07 32.07 32.07 32.07 32.07

1.24 1.24 1.20 1.16 1.12 1.05 1.03 1.02 1.01

35.10 0.00 1.33 2.79 4.35 7.71 9.32 12.74 16.23

39.78 39.83 41.23 42.30 44.00 46.99 47.92 48.36 48.61

-0.12% 0.00% 3.50% 6.21% 10.48% 17.97% 20.31% 21.42% 22.03%

566.26 0.00 36.62 74.83 111.86 187.29 222.57 290.71 361.91

cost using (3) and report the decomposition CA (I) = τ Q(I) + cTA (I) + τ EA (I). The reported values are averages over five independent replications. Table 1 shows the three-way tradeoff among FCFS, LJF, and ISJL. First, the intrinsic workload term τ Q is identical across all policies, as predicted by Theorem 7. Thus the profit differences come only from the schedule-dependent terms cT and τ E. Second, FCFS has essentially the same throughput as LJF in this configuration, but it incurs a large batching-externality cost. Its average within-batch extent is 566.26, and its externality cost is 35.10. This explains why FCFS has substantially lower profit than the fair schedules under the same linear token-pricing rule. Third, LJF eliminates the batching externality, but it achieves this by static batching. It is therefore cost-aligned but less flexible. ISJL traces a managerial frontier between these two extremes. For small α, ISJL is close to LJF in cost alignment: at α = 50, its profit is within 0.8% of LJF while increasing throughput by 3.5%. As α increases, ISJL admits more jobs through continuous batching and obtains larger throughput improvements at the cost of a controlled increase in batching externality. At α = 300, ISJL improves throughput by 20.31% relative to LJF and still improves profit by 20.19% relative to FCFS; its profit remains within 5.56% of LJF. Larger values of α continue to improve throughput slightly, but the additional batching externality erodes profit. This pattern is consistent with the theory: the fairness constraint bounds the externality term, while relaxing α increases scheduling flexibility and reduces the makespan term. Figure 5 visualizes the same tradeoff. LJF is the cost-alignment benchmark because its batching externality is zero. FCFS is the opposite benchmark: it admits requests continuously but allows large progress heterogeneity, generating high externality cost. ISJL traces an intermediate frontier. A smaller α keeps ISJL close to LJF in profit, while a larger α gives more batching flexibility and higher throughput at the cost of a larger externality term. When does ISJL dominate LJF in profit? The pairwise comparison in Proposition 6 provides

34

Intrinsic workload Time/overhead Batching externality

60

Cost

50 40

Profit

70

30 20 10 0

FCFS

165 160 155 150 145 140 135 130

LJF

ISJL alpha=50 ISJL alpha=100 ISJL alpha=150 ISJL alpha=250 ISJL alpha=300 ISJL alpha=400 ISJL alpha=500

FCFS

40

LJF ISJL 50 ISJL 100 ISJL 150 ISJL 250 ISJL 300 ISJL 400 ISJL 500

42 44 46 Token throughput

48

Figure 5: Cost decomposition and profit–throughput frontier under linear pricing. a simple way to interpret the fact that LJF has the highest profit in Table 1. Since ELJF (I) = 0, ISJL with parameter α has higher profit than LJF exactly when its time-cost savings exceed its additional externality cost:
c TLJF (I) − TISJL(α) (I) ≥ τ EISJL(α) (I). Equivalently, the break-even fixed cost is c⋆α =

τ EISJL(α) (I) . TLJF (I) − TISJL(α) (I)

Table 2 reports the corresponding empirical break-even values. Table 2: Break-even overhead for ISJL relative to LJF α Time saving vs. LJF τ EISJL(α) c⋆α 50 100 150 250 300 400 500

83.2 147.6 235.2 380.0 414.0 437.8 444.2

1.35 2.81 4.36 7.71 9.33 12.72 16.25

0.0162 0.0190 0.0185 0.0203 0.0225 0.0291 0.0366

The baseline value c = 0.0005 is far below these break-even values. Thus LJF’s profit advantage in Table 1 is not surprising: the experiment intentionally places little weight on the number of service steps. When the fixed per-step overhead becomes economically material, ISJL’s makespan advantage can dominate its controlled externality loss. For example, ISJL with α = 50 becomes more profitable than LJF once c > 0.0162. This sensitivity result is consistent with the bi-criterion interpretation of ISJL: it sacrifices a bounded amount of cost alignment to recover throughput.

35

Profit difference vs. LJF

10 5 0

ISJL alpha=50 ISJL alpha=100 ISJL alpha=150 ISJL alpha=250 ISJL alpha=300 ISJL alpha=400 ISJL alpha=500

5 10 15 0.00

0.01 0.02 0.03 0.04 Fixed per-step overhead c

0.05

Figure 6: Profit difference between ISJL and LJF as the fixed per-step overhead c varies. The dashed vertical line marks the baseline value c = 0.0005.

5.3

Scope of the Demand Specification and Relation to the Efficiency Benchmark

The profit experiment above should be interpreted as a fixed-workload evaluation of scheduling policies, not as a model of scheduling-dependent demand. We first condition on an accepted workload I and then hold this workload fixed across all scheduling policies. Under exogenous token-metered pricing, total revenue is therefore schedule-independent: R(I) = ρO(I),

O(I) =

X

oi .

i∈I

Consequently, profit differences across FCFS, LJF, and ISJL arise from inference cost rather than from demand-side revenue changes. In particular, for any two schedulers A and B serving the same accepted workload, ΠA (I) − ΠB (I) = CB (I) − CA (I). This design isolates the operational mechanism analyzed in this paper: how a scheduler changes the composition of active batches and thereby changes the schedule-dependent cost components in Theorem 7, namely the time/overhead term cTA (I) and the batching-externality term τ EA (I). The current analysis therefore does not model a latency-sensitive demand channel. In practice, scheduling can affect future demand through service quality: lower waiting time or end-to-end latency may increase user retention, repeat usage, or willingness to pay, especially for short and interactive requests. A reduced-form latency-sensitive acceptance model might take the form vi − pi − hi E[Wi (A)] ≥ 0,

36

where vi is the customer’s value, pi is the token-metered price, hi is the customer’s delay sensitivity, and Wi (A) is the waiting time induced by scheduler A. Such a model would create a feedback loop between scheduling, expected waiting time, demand composition, and revenue. It would also require specifying the arrival process, customer beliefs about service quality, and the timing of pricing and scheduling decisions. We view this joint demand–scheduling problem as an important extension, but it is outside the scope of the present paper.

6

System Efficiency Under Resource-Fair Scheduling

The previous section quantified cost alignment and profit under exogenous token pricing. This section isolates the operational efficiency of the scheduling policies on a fixed workload from a public dataset, using throughput and average end-to-end latency. Dataset Overview. The experimental data for this study is derived from the LMSYS-Chat-1M dataset Zheng et al. (2023), a publicly available corpus containing human-chatbot interactions. This dataset was compiled from the Vicuna demo and Chatbot Arena, aggregating conversations from more than 210,000 distinct IP addresses. For the purpose of our simulations, a statistically representative subset of 2,000 conversations was randomly extracted from this larger population. To model computational demand, we characterize each conversation by its total token count. The sampled subset exhibits considerable diversity in these dimensions. The distribution of total token counts is characterized by a mean of 126, a median of 90, a max of 905, and a variance of 14938. Figure EC.1 in Appendix EC.5 illustrates the heterogeneous nature of the workload used in our analysis. Performance Metrics and Benchmark Algorithms. We evaluate the performance of the following scheduling algorithms under batch sizes of B = 16 and B = 32: • First-Come, First-Served (FCFS). • Shortest Job First (SJF), which prioritizes requests with the smallest total token count. • Longest Job First (LJF). • The proposed ISJL algorithm with fairness parameters α = 50, 100, 150. The evaluation is based on two key metrics: throughput and Average End-to-end Latency (AEL). Throughput, defined as the total number of tokens processed per unit time, is calculated as: Throughput =

Total number of tokens processed in [0, T ] , T

(18)

where T is the makespan, i.e., the time when all requests have been completed. The AEL is the averaged completion time across all requests: n

AEL =

1X ci , n i=1

37

(19)

where ci is the completion time of request i and n = 2000 is the total number of requests. Results. The performance results for all algorithms under batch sizes B = 16 and B = 32 are summarized in Table 3. Our analysis yields several key findings. ISJL dominates all baselines on both metrics simultaneously. The proposed ISJL algorithm achieves strictly higher throughput and strictly lower AEL than every baseline for all tested values of α, across both batch sizes. At B = 16, ISJL with α = 150 achieves the highest throughput (276), representing a 14% improvement over LJF (243) and a 28% improvement over SJF (196). Simultaneously, ISJL with α = 50 achieves the lowest AEL (53), a 20% improvement over LJF (66) and a 12% improvement over SJF (60). At B = 32, the same pattern holds: ISJL with α = 150 achieves throughput of 378 (+17% over LJF, +46% over SJF), while ISJL with α = 50 achieves AEL of 62 (−21% over LJF, −7% over SJF). This simultaneous improvement should be interpreted as a comparison with the evaluated benchmark policies, not with the unconstrained optimal schedule. Operationally, ISJL performs well because it combines resource-homogeneous batching with event-driven admissions: it avoids the severe progress imbalance that can arise under unrestricted continuous batching, while also avoiding the idle capacity created by fully static batching. Table 3: Throughput and AEL by Different Scheduling Algorithms Scheduling Algorithms Batch Size

Metrics

FCFS

SJF

LJF

ISJL α = 50

α = 100

α = 150

B = 16

Throughput AEL

216 62

196 60

243 66

262 53

270 56

276 54

B = 32

Throughput AEL

278 70

259 67

323 78

357 62

369 63

378 65

The parameter α provides a tunable efficiency–latency trade-off. Within the ISJL family, the parameter α allows operators to tune the balance between throughput and AEL. A lower value (α = 50) enforces stricter fairness, reducing the KV-cache spread within each batch and thereby minimizing the waiting time for individual requests: this configuration achieves the best AEL (53 at B = 16, 62 at B = 32). A higher value (α = 150) permits greater batching flexibility, enabling more requests to be processed concurrently and maximizing throughput (276 at B = 16, 378 at B = 32).

7

Conclusion

This paper studies resource-fair scheduling for batched LLM inference. In heterogeneous continuous batching, short requests can be served in batches whose resource profile is determined by much longer requests. We formalize this issue through a resource-homogeneity constraint and design 38

ISJL, a hybrid batching policy that preserves high throughput while respecting a tunable fairness budget. The theoretical analysis gives a 3/4 competitive-ratio guarantee for backlogged instances, and the cost-decomposition analysis shows how the fairness constraint bounds the schedule-induced batching externality under token-metered pricing. Empirically, ISJL occupies a favorable point on the cost–efficiency frontier. Relative to FCFS, it substantially reduces batching-externality cost; relative to LJF, it recovers much of the throughput and latency benefit of continuous batching. Thus ISJL should be interpreted as a bi-criterion scheduling policy: it controls cost misalignment while retaining operational efficiency. Discussion: many-server scaling at fixed batch size.

A natural question is whether the

resource-homogeneity problem diminishes in a large-scale many-server system. In such a regime, a centralized scheduler may draw from a larger pending pool at each batching epoch, making it easier to form length-homogeneous cohorts. The following simple observation formalizes this pooling effect. Suppose that, at a decision epoch, there are N unstarted pending requests with total token lengths in [0, ō]. Fix α > 0 and partition [0, ō] into K = ⌈ō/α⌉ intervals of width at most α. Within each interval, form as many full batches of size B as possible. Since all requests in the same interval have total lengths differing by at most α, each such batch is length-homogeneous. In interval k, at most B − 1 requests are left over. Therefore, across all intervals, at most K(B − 1) requests are left unmatched, and at least N − K(B − 1) requests can be assigned to full length-homogeneous batches. Consequently, for fixed B, fixed α, and bounded length support, the unmatched fraction is at most K(B − 1) , N which vanishes as the pending pool size N grows. This observation supports the intuition that large-scale pooling can mitigate the initial batchformation problem. We therefore do not claim that the performance gap between resource-aware batching and simpler length-clustering policies must persist in every many-server limit. Instead, our results should be interpreted as finite-instance and finite-pool guarantees. They are especially relevant when the pending pool is not large enough to make all batches nearly homogeneous, when workloads are heavy-tailed, when latency constraints prevent the system from waiting to accumulate a large matching pool, or when GPU routing and KV-cache locality limit global repacking. Moreover, the large-pool matching observation concerns the formation of new cohorts of unstarted requests. It does not by itself remove the dynamic issue created by continuous batching. Once an active batch has progressed beyond α, a newly arrived request with progress zero cannot be inserted into that batch without violating the fairness constraint, unless the system allows migration, preemption, or KV-cache repacking across workers. Thus, large-scale pooling can reduce

39

heterogeneity at admission, but dynamic admission decisions and finite waiting-time requirements remain operationally important. A full many-server stochastic analysis with fixed B is an interesting direction for future work.

References Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. Taming throughput-latency tradeoff in LLM inference with Sarathi-Serve. arXiv preprint arXiv:2403.02310 (2024). Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee. 2023. Sarathi: Efficient LLM inference by piggybacking decodes with chunked prefills. arXiv preprint arXiv:2308.16369 (2023). Susanne Albers. 2009. Online scheduling. In Introduction to scheduling. CRC Press, 71–98. Ali Allahverdi, Chi To Ng, TC Edwin Cheng, and Mikhail Y Kovalyov. 2008. A survey of scheduling problems with setup times or costs. European journal of operational research 187, 3 (2008), 985–1032. Amazon. 2023. Amazon CodeWhisperer. https://aws.amazon.com/codewhisperer/. Anthropic. 2023. Claude. https://claude.ai. Anthropic. 2026. Pricing — Claude API Docs. https://platform.claude.com/docs/en/about-claude/ pricing. Accessed: 2026-06-10. Ruicheng Ao, Gan Luo, David Simchi-Levi, and Xinshang Wang. 2025. Optimizing LLM Inference: FluidGuided Online Scheduling with Memory Constraints. arXiv preprint arXiv:2504.11320 (2025). Yossi Azar and Leah Epstein. 2002. On-line scheduling with precedence constraints. Discrete Applied Mathematics 119, 1 (2002), 169–180. doi:10.1016/S0166-218X(01)00272-4 Special Issue devoted to Foundation of Heuristics in Combinatoria l Optimization. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems 33 (2020), 1877–1901. Marco Cascella, Jonathan Montomoli, Valentina Bellini, and Elena Bignami. 2023. Evaluating the feasibility of ChatGPT in healthcare: an analysis of multiple clinical and research scenarios. Journal of medical systems 47, 1 (2023), 33. Bo Chen and Chung-Yee Lee. 2008. Logistics scheduling with batching and transportation. European journal of operational research 189, 3 (2008), 871–876. Bo Chen, Chris N Potts, and Gerhard J Woeginger. 1998. A review of machine scheduling: Complexity, algorithms and approximability. Handbook of Combinatorial Optimization: Volume1–3 (1998), 1493– 1641. Lequn Chen. 2023. Dissecting Batching Effects in GPT Inference. le.qun.ch. blog/2023/05/13/transformer-batching/

https://le.qun.ch/en/

Zixi Chen, Yinyu Ye, and Zijie Zhou. 2025. Adaptively Robust LLM Inference Optimization under Prediction Uncertainty. arXiv preprint arXiv:2508.14544 (2025). Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2023. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research 24, 240 (2023), 1–113.

40

DeepSeek. 2026. Models & Pricing — DeepSeek API Docs. https://api-docs.deepseek.com/quick_ start/pricing. Accessed: 2026-06-10. Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla. 2019. Non-Clairvoyant Precedence Constrained Scheduling. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece (LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 63:1–63:14. doi:10.4230/LIPICS.ICALP.2019.63 GitHub. 2021. GitHub Copilot. https://github.com/features/copilot. Negin Golrezaei, Patrick Jaillet, and Zijie Zhou. 2023. Online resource allocation with convex-set machinelearned advice. arXiv preprint arXiv:2306.12282 (2023). Google. 2026. Gemini Developer API Pricing. https://ai.google.dev/gemini-api/docs/pricing. Accessed: 2026-06-10. R. L. Graham. 1969. Bounds on Multiprocessing Timing Anomalies. SIAM J. Appl. Math. 17, 2 (1969), 416–429. http://www.jstor.org/stable/2099572 Chenyu Huang, Zhengyang Tang, Shixi Hu, Ruoqing Jiang, Xin Zheng, Dongdong Ge, Benyou Wang, and Zizhuo Wang. 2025. Orlm: A customizable framework in training large models for automated optimization modeling. Operations Research (2025). Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, and Zijie Zhou. 2025. Online Scheduling for LLM Inference with KV Cache Constraints. arXiv preprint arXiv:2502.07115 (2025). Redwan Ibne Seraj Khan, Kunal Jain, Haiying Shen, Ankur Mallick, Anjaly Parayil, Anoop Kulkarni, Steve Kofsky, Pankhuri Choudhary, Renee St Amant, Rujia Wang, et al. 2024. Ensuring Fair LLM Serving Amid Diverse Applications. arXiv preprint arXiv:2411.15997 (2024). Qingxia Kong, Chung-Yee Lee, Chung-Piaw Teo, and Zhichao Zheng. 2013. Scheduling arrivals to a stochastic service delivery system using copositive cones. Operations research 61, 3 (2013), 711–726. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles. 611–626. Chung-Yee Lee and Zhi-Long Chen. 2001. Machine scheduling with transportation considerations. Journal of scheduling 4, 1 (2001), 3–24. Wenhua Li, Libo Wang, Xing Chai, and Hang Yuan. 2020. Online batch scheduling of simple linear deteriorating jobs with incompatible families. Mathematics 8, 2 (2020), 170. Peihai Liu and Xiwen Lu. 2015. Online unbounded batch scheduling on parallel machines with delivery times. Journal of Combinatorial Optimization 29 (2015), 228–236. Thodoris Lykouris and Sergei Vassilvitskii. 2021. Competitive caching with machine learned advice. Journal of the ACM (JACM) 68, 4 (2021), 1–25. Ho-Yin Mak, Ying Rong, and Jiawei Zhang. 2015. Appointment scheduling with limited distributional information. Management Science 61, 2 (2015), 316–334. OpenAI. 2019. ChatGPT. https://chat.openai.com. OpenAI. 2023. GPT-4 technical report. arxiv 2303.08774. View in Article 2, 5 (2023). OpenAI. 2026. API Pricing. https://openai.com/api/pricing/. Accessed: 2026-06-10.

41

Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. 2023. Splitwise: Efficient generative LLM inference using phase splitting. Power 400, 700W (2023), 1–75. Julien Robert and Nicolas Schabanel. 2008. Non-clairvoyant scheduling with precedence constraints. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, Shang-Hua Teng (Ed.). SIAM, 491–500. http: //dl.acm.org/citation.cfm?id=1347082.1347136 Malik Sallam. 2023. The utility of ChatGPT as an example of large language models in healthcare education, research and practice: Systematic review on the future perspectives and potential limitations. MedRxiv (2023), 2023–02. Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, and Michael Mitzenmacher. 2024. Don’t Stop Me Now: Embedding Based Scheduling for LLMs. arXiv preprint arXiv:2410.01035 (2024). Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica. 2024. Fairness in serving large language models. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 965–988. Meixuan Wang, Yinyu Ye, and Zijie Zhou. 2025. LLM Serving Optimization with Variable Prefill and Decode Lengths. arXiv preprint arXiv:2508.06133 (2025). Zhixiang Wei, James Yen, Jingyi Chen, Ziyang Zhang, Zhibai Huang, Chen Chen, Xingzi Yu, Yicheng Gu, Chenggang Wu, Yun Wang, et al. 2025. Equinox: Holistic Fair Scheduling in Serving Large Language Models. arXiv preprint arXiv:2508.16646 (2025). Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022. Orca: A distributed serving system for {Transformer-Based} generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 521–538. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric Xing, et al. 2023. LMSYS-Chat-1M: A large-scale real-world LLM conversation dataset. arXiv preprint arXiv:2309.11998 (2023). Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. 2024. Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving. arXiv preprint arXiv:2401.09670 (2024).

42

Online Appendix EC.1

Supplementary Materials for Section 3

EC.1.1

Optimal Scheduling with Integer Programming (IP)

We index discrete time by a finite horizon H large enough to contain any feasible schedule (e.g., P H = ni=1 oi ). Let M be a big constant (e.g., M = maxi oi ). Tasks i ∈ {1, . . . , n}; time steps t ∈ {1, . . . , H}. Processing requirement oi ∈ Z+ ; parallel capacity B ∈ Z+ ; tolerance α ∈ Z+ . Decision variables are defined as follows: ui,t ∈ {0, 1}: task i starts at time t; xi,t ∈ {0, 1}: task i is executing during time t; si,t ∈ Z+ : cumulative progress of task i at the start of time t; T ∈ Z+ : makespan (last completion time step). And our objective is defined as: min T Constraints are defined as follows: (1) Each task starts exactly once: H−o i +1 X

ui,t = 1,

∀i.

t=1

(2) Start-to-occupancy linkage (contiguous processing for oi steps once started): X

xi,t =

ui,τ ,

∀i, ∀t = 1, . . . , H.

τ : τ ≤t≤τ +oi −1

(3) Parallel capacity: n X

xi,t ≤ B,

∀t = 1, . . . , H.

i=1

(4) Progress definition: si,t =

t−1 X

xi,h ,

∀i, ∀t = 1, . . . , H.

h=1

(5) Makespan definition: T ≥

H−o i +1 X

(t + oi − 1) ui,t ,

∀i.

t=1

(6) Fairness Constraint: for any time step, any two executing tasks must satisfy |si − sj | ≤ α, activated only when both tasks execute:
si,t − sj,t ≤ α + M 2 − xi,t − xj,t ,
sj,t − si,t ≤ α + M 2 − xi,t − xj,t ,

43

∀t = 1, . . . , H, ∀i < j.

EC.2

Supplementary Materials for Section 3

Proof of Theorem 4

The fairness constraint concerns only the progress values {ai (t)} of currently

active jobs. Robust-ISJL admits a new job of progress 0 only when the Phase TWO admission condition is met, i.e., when the current maximum progress among active jobs satisfies Amax (t) ≤ α; hence the new batch has range at most α at the admission time. Between admissions, all jobs in the active batch advance in lockstep, so the max–min gap is invariant. When a job completes, it is removed from the active set, and removing elements cannot increase the max–min range. Therefore the fairness constraint holds at all times. Proof of Proposition 4.

New arrivals enter the pending queue and do not affect the active set until

they are admitted. Whenever Online-ISJL invokes Phase ONE, it applies the same packing rule as Algorithm 3 to the currently released queue, so the active batch constructed by Phase ONE satisfies the α-fairness constraint. Whenever Online-ISJL admits a request during Phase TWO, the request has progress zero and is admitted only if the current maximum progress among active requests satisfies Amax (t) ≤ α; hence the progress range after admission is at most α. Between admission epochs, all active requests advance in lockstep, so the max–min progress gap is invariant. When a request completes, it is removed from the active set, and removing an element cannot increase the max–min range. Therefore the fairness constraint holds for all time steps. Proof of Corollary 1.

■

By Theorem 5, TOPT (I) 3 1 ≥ · . TRobust-ISJL (I) 4 1 + ∆/TOPT (I)

Any feasible schedule processes at most B tokens per time step. Therefore, TOPT (I) ≥ It follows that

O(I) . B

∆ ∆ ≤B = B ε̄(I). TOPT (I) O(I)

Substitution gives the first claim. If ui ≤ (1 + ε)oi for all i, then ui − oi ≤ εoi for all i, and hence ε̄(I) ≤ ε. The second claim follows.

EC.3

■

Supplementary Materials for Section 4

Proof of Lemma 4

Let α ∈ (0, o1 ), set γ = α/o1 ∈ (0, 1), and normalize xi = oi /o1 . In the

Over-Inserting regime, the feasible region is 1 ≥ x2 ≥ x3 ≥ x4 > 0,

x3 < 1 − x2 + γ,

x3 < 2γ,

44

1 > min{2γ, x3 + γ},

x2 + x3 > 1,

and the competitive ratio equals CRover =

1 + x3 . x2 + x 3 + x 4

For fixed γ, minimizing CR amounts to maximizing the denominator x2 + x3 + x4 for each fixed x3 . Maximizing the denominator for fixed x3 . Since x2 ≥ x3 ≥ x4 > 0, the optimal choice is x⋆4 = x3 . From x2 ≤ 1,

x3 < 1 − x2 + γ ⇐⇒ x2 < 1 + γ − x3 ,

together with x2 ≥ x3 and x2 + x3 > 1, the largest admissible x2 is x⋆2 = min{1, 1 + γ − x3 }. Hence the maximized denominator for fixed x3 is  1 + 2x , 3 D(x3 ) = x⋆2 + x3 + x⋆4 = min{1, 1 + γ − x3 } + 2x3 = 1 + γ + x , 3

x3 ≤ γ, x3 ≥ γ.

Define Φ(x3 ) := (1 + x3 )/D(x3 ); then  1+x 3  , x3 ≤ γ,  1 + 2x3 Φ(x3 ) =   1 + x3 , x3 ≥ γ. 1 + γ + x3 Feasible values of x3 . Besides x3 > 0, feasibility requires x3 < 2γ and 1 > min{2γ, x3 + γ}. This yields: 
 (0, γ) ∪ γ, min{2γ, (1 + γ)/2} , 0 < γ < 21 ,    x3 ∈ (0, 12 ), γ = 21 ,     1 (0, 1 − γ), 2 < γ < 1. One-dimensional minimization. Case 0 < γ ≤ 12 . On x3 ≤ γ, Φ′ (x3 ) =

(1 + 2x3 ) − 2(1 + x3 ) 1 =− < 0, 2 (1 + 2x3 ) (1 + 2x3 )2

so Φ decreases; on x3 ≥ γ, Φ′ (x3 ) =

γ > 0, (1 + γ + x3 )2

so Φ increases. Therefore the infimum occurs at the junction x3 = γ: inf CRover =

1+γ 1 + 2γ

45

(0 < γ ≤ 21 ).

Case 21 ≤ γ < 1. Only the branch x3 ∈ (0, 1 − γ) ⊆ (0, γ] is feasible, where Φ(x3 ) =

1 + x3 , 1 + 2x3

Φ′ (x3 ) < 0.

Thus the infimum is attained as x3 ↑ (1 − γ): inf CRover =

1 + (1 − γ) 2−γ = 1 + 2(1 − γ) 3 − 2γ

( 12 ≤ γ < 1).

Dependence on γ and global minimum. Let f1 (γ) = (1 + γ)/(1 + 2γ) for γ ∈ (0, 21 ] and f2 (γ) = (2 − γ)/(3 − 2γ) for γ ∈ [ 12 , 1). Then f1′ (γ) = −

1 < 0, (1 + 2γ)2

f2′ (γ) =

1 > 0, (3 − 2γ)2

so f1 is strictly decreasing and f2 strictly increasing. At γ = 21 ,
3
f1 12 = = f2 21 , 4 hence CRover is continuous with a unique global minimum 3/4. Moreover, lim

1+γ

γ→0+ 1 + 2γ

= 1,

lim

2−γ

γ→1− 3 − 2γ

= 1.

Attainability by feasible sequences. Because the constraints are strict, the minimizers lie on the boundary but are approached by feasible sequences: 1+γ 1+x3 ↓ 1+2γ . • If 0 < γ ≤ 12 , take x2 = 1, x4 = x3 , and let x3 ↑ γ with x3 < γ to get CRover = 1+2x 3

• If 12 ≤ γ < 1, take x2 = 1, x4 = x3 , and let x3 ↑ (1 − γ) with x3 < 1 − γ to get CRover = 2−γ 1+x3 1+2x3 ↓ 3−2γ .

This completes the proof. Proof of Lemma 5

■

By scale invariance of CRunder under a common scaling of (o1 , o2 , o3 , α), nor-

malize xi = oi /o1 . The feasibility constraints then read 1 − x2 + γ < x3 ≤ 2γ,

1 ≥ x2 ≥ x3 > 0,

where the order x2 ≥ x3 entails no loss for an adversarial analysis. For f (x2 , x3 ) := we first observe that for fixed x2 ,

x2 + x3 , 1 + x3

∂f 1 − x2 = ≥ 0, ∂x3 (1 + x3 )2 46

with equality only when x2 = 1. Hence, for x2 < 1, the function is strictly decreasing in x3 ; therefore, minimizing f pushes x3 to its largest feasible value, namely x3 = min{ 2γ, x2 }. This leads to two regimes, according to which the upper bound is active. Regime A: 2γ ≤ x2 . Feasibility also requires 1 − x2 + γ < 2γ, i.e. x2 > 1 − γ. Thus x2 ∈  max{1 − γ, 2γ}, 1 , and x2 + 2γ f (x2 , 2γ) = 1 + 2γ is strictly increasing in x2 . The infimum is attained in the limit at the smallest feasible x2 :  1+γ  ,  1 + 2γ inf f =   4γ , 1 + 2γ

0 < γ ≤ 13

(here 1 − γ ≥ 2γ),

1 3 ≤γ <1

(here 1 − γ ≤ 2γ).

Regime B: x2 ≤ 2γ. The lower bound 1 − x2 + γ < x3 = x2 forces x2 > (1 + γ)/2, so x2 ∈  (1 + γ)/2, 2γ , which is nonempty exactly when γ ≥ 31 . With x3 = x2 we have f (x2 , x2 ) =

2x2 , 1 + x2

strictly increasing in x2 , hence minimized in the limit as x2 ↓ (1 + γ)/2: inf f =

2(1 + γ) . 3+γ

When 0 < γ ≤ 13 , Regime A is the only feasible one, yielding CRunder (γ) =

1+γ . When 1 + 2γ

1 3 ≤ γ < 1, both regimes are feasible; comparing the two values,

2(1 + γ) 4γ ≤ ⇐⇒ (1 + γ)(1 + 2γ) ≤ 2γ(3 + γ) ⇐⇒ γ ≥ 31 , 3+γ 1 + 2γ so Regime B dominates on [ 13 , 1). The two expressions match at γ = 13 with common value 4/5. Tightness in each regime follows by taking feasible limits to the identified boundary points. Finally, the piecewise expression is unimodal in γ: on (0, 31 ], d 1+γ 1 =− < 0, dγ 1 + 2γ (1 + 2γ)2 and on [ 13 , 1), d 2(1 + γ) 4 = > 0. dγ 3 + γ (3 + γ)2

47

Thus CRunder (γ) strictly decreases on (0, 31 ], strictly increases on [ 13 , 1), achieves its unique global minimum 4/5 at γ = 13 , and satisfies lim

γ→0+

1+γ = 1, 1 + 2γ

lim

γ→1−

2(1 + γ) = 1. 3+γ ■

EC.4

Supplementary Materials for Section 5

Proof of Theorem 7.

For each service step t, write (t)

m(t) := max rj . j∈S (t)

Then |S (t) |m(t) =

X

m(t) =

i∈S (t)

(t)

X

ri +

i∈S (t)

X 

(t)

m(t) − ri



.

i∈S (t)

Substituting this identity into (3) and summing over t = 1, . . . , TA (I) yields TA (I)

CA (I) = cTA (I) + τ

TA (I)

X X 

(t) ri + τ

X X t=1 i∈S (t)

(t)

m(t) − ri



.

t=1 i∈S (t)

The last term is exactly τ EA (I). The middle term is schedule-independent: request i must process token indices 1, 2, . . . , oi exactly once before completion, regardless of the other requests with which it is batched. Therefore TA (I)

X X

(t) ri =

t=1 i∈S (t)

oi n X X

k = Q(I).

i=1 k=1

Thus CA (I) = cTA (I) + τ Q(I) + τ EA (I). Combining this equality with ΠA (I) = R(I) − CA (I) gives (7). It remains to prove the externality bound. If A is fair, for every active i ∈ S (t) , (t)

0 ≤ m(t) − ri ≤ α. Hence TA (I)

EA (I) ≤

TA (I)

X X t=1 i∈S (t)

48

α=α

X t=1

|S (t) |.

At each service step, every active request processes exactly one token, so TA (I)

X

(t)

|S | =

t=1

n X

oi = O(I).

i=1

Therefore EA (I) ≤ αO(I). Proof of Theorem 8.

■

By Theorem 7, revenue and intrinsic resource cost cancel when comparing

two schedules on the same accepted instance. Hence
Π⋆α (I) − ΠA (I) = c (TA (I) − Tπ⋆ (I)) + τ EA (I) − EA⋆π (I) . Since TOP T (I) ≤ Tπ⋆ (I), the competitive ratio condition (9) implies TA (I) ≤

1 1 TOP T (I) ≤ Tπ⋆ (I), ρ ρ

and therefore TA (I) − Tπ⋆ (I) ≤



 1 − 1 Tπ⋆ (I). ρ

Moreover EA⋆π (I) ≥ 0, and because A is fair, Theorem 7 gives EA (I) ≤ αO(I). Thus Π⋆α (I) − ΠA (I) ≤ c



 1 − 1 Tπ⋆ (I) + τ αO(I), ρ

which proves (10). Setting ρ = 3/4 for ISJL by Theorem 3 gives (11). Proof of Proposition 6.

■

Equation (12) follows immediately by subtracting the decompositions

in (7) for A and B; the fixed terms R(I) and τ Q(I) cancel. Under LJF, each static batch starts with equal progress on all active requests, and no new request is admitted into that batch before the batch is rebuilt. While requests in a batch are active, their progress values are equal; when shorter requests complete, removing them from the active set cannot create a positive max–min gap among the remaining active requests. Thus ELJF (I) = 0. Taking (A, B) = (ISJL, LJF ) in (12) and using EISJL (I) ≤ αO(I) gives (13). Taking (A, B) = (ISJL, FCF S) and again using EISJL (I) ≤ αO(I) gives (14). Proof of Proposition 7.

■

Under FCFS, the long request occupies one server for L service steps.

Since there are exactly L short requests and each has length 1, FCFS places one short request on the other server in each of these L steps. Hence all work is completed when the long request completes, so TF CF S (I) = L. At the kth service step, k = 1, . . . , L, the long request processes token index k, while the short request processes token index 1. Therefore the externality in step k is (k − k) + (k − 1) = k − 1.

49

Summing over k = 1, . . . , L gives EF CF S (I) =

L X

(k − 1) =

k=1

L(L − 1) . 2

Under LJF, the long request and one short request are placed in the first static batch. They have equal progress during the first step; after the short request completes, the long request runs alone until completion. The remaining L − 1 short requests are then processed in batches of size two, requiring ⌈(L − 1)/2⌉ additional steps. Thus TLJF (I) = L + ⌈(L − 1)/2⌉. Since every LJF batch starts with equal progress and admits no new request while the batch is active, ELJF (I) = 0. Finally, (17) follows from the pairwise comparison identity (12). Because the positive term in (17) grows quadratically in L, whereas the negative term grows only linearly, LJF is more profitable than FCFS for all sufficiently large L. Proof of Corollary 2

■

By Theorem 7, the profit of schedule A can be written as ΠA (I) = R(I) − τ Q(I) − cTA (I) − τ EA (I).

If A is α-fair, then EA (I) ≤ αO(I). Substituting this bound into the profit decomposition gives ΠA (I) ≥ R(I) − τ Q(I) − τ αO(I) − cTA (I). For a fixed workload I and fixed α, the first three terms on the right-hand side are independent of the schedule. Therefore, maximizing the certified profit lower bound over α-fair schedules is equivalent to minimizing TA (I). Proof of Proposition 8

■

Any schedule satisfying the α1 -fairness constraint has within-batch progress

gap at most α1 at every time step. Since α1 ≤ α2 , the same schedule also satisfies the α2 -fairness constraint. Hence Fα1 ⊆ Fα2 . Minimizing makespan over the larger feasible set cannot yield a larger optimum, so Tα⋆2 (I) ≤ Tα⋆1 (I). Since O(I) is fixed for the instance, throughput O(I)/Tα⋆ (I) is weakly increasing in α.

EC.5

■

Supplementary Materials for Section 6

Figure EC.1 displays the distribution of the number of tokens.

50

Figure EC.1: Distribution of the Number of Tokens

51

Related documents

• Fairness-Aware and Latency-Controllable Scheduling for Chunked-Prefill LLM Serving#267618
• AlignedServe: Orchestrating Prefix-aware Batching to Build a High-throughput and Computing-efficient LLM Serving System#224488
• Kalypso: Relational LLM Serving#411157
• FASER: Fine-Grained Phase Management for Speculative Decoding in Dynamic LLM Serving#124010
• Segment Routing Replication for Multipoint Service Delivery#136674