Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters Sohan Kunkerkar Red Hat United States [email protected]
arXiv:2607.28223v1 [cs.DC] 30 Jul 2026
Abstract GPU cluster operators cannot predict how long pending workloads will wait for admission. Existing systems use greedy heuristics with no formal wait time guarantees. We formalize GPU cluster admission as a multi-class, multiresource queueing network and prove a structural decomposition: the pending queue partitions into quotable workloads (bounded wait time under stability) and unfeasible workloads (no finite bound without reconfiguration). For quotable workloads, we model each cluster queue as an M/G/𝑘 system where the effective server count 𝑘 is determined by a vector packing reduction; under an explicit stochastic domination assumption, we establish 𝑂 (1/(1 − 𝜌)) wait time scaling. We prove that optimal admission ordering is NP-hard under multi-dimensional resource demands via reduction from vector bin packing. We validate on Kueue, the standard Kubernetes workload queuing system, showing that the ErlangC approximation consistently overestimates observed wait times (a conservative direction) in the moderate utilization regime.
1
Introduction
GPU cluster utilization is low: industry reports put average utilization at 5–30% across enterprise GPU clusters [18]. Operators cannot predict whether a submitted workload will wait minutes or hours for admission. Production batch workload queuing systems—Kueue [4], Slurm [5], and proprietary schedulers—use greedy admission heuristics with no formal performance guarantees. Recent work has applied queueing theory to GPU inference serving, where request scheduling within a single model deployment benefits from classical results. Mitzenmacher and Shahout [1] survey learning-augmented scheduling with predictions, and Dai et al. [2] prove throughput-optimality for batched LLM serving. However, these results address a fundamentally different problem: scheduling requests within a serving instance, not scheduling workloads across a multitenant cluster with quotas, resource flavors, topology constraints, and preemption. The cluster admission problem is harder for three reasons. First, admission requires vector packing: each workload demands a multi-dimensional resource vector (GPU count, memory, network bandwidth), and admission requires all dimensions to fit simultaneously. Second, the pending queue
contains a mixture of workloads that can eventually be admitted (if other workloads complete) and workloads that cannot be admitted under the current cluster configuration. Third, preemption creates feedback loops where evicted workloads re-enter the queue, invalidating the independent-arrivals assumption of classical models. We address these challenges with three contributions:
1. Quotable/Unfeasible Partition Theorem. We prove that the pending queue decomposes into a quotable partition (where queueing theory applies and wait times are bounded) and an unfeasible partition (where no finite bound exists). This decomposition is necessary for accurate wait time estimation: any model that mixes both partitions produces unbounded prediction error (§3.2). 2. Wait Time Bounds. For quotable workloads, we assume stochastic domination by an M/G/𝑘 reference system with effective server count determined by vector packing (Modeling Assumption 1), establishing 𝑂 (1/(1 − 𝜌)) wait time scaling. We provide a practical modified Erlang-C approximation accounting for multi-resource packing and preemption feedback (§3.5). 3. NP-Hardness of Optimal Admission. We prove that optimal admission ordering—minimizing total weighted wait time—is NP-hard under multi-resource vector packing, and show that MIG packing alone (fixed profile sizes) is tractable (Proposition 2). This pinpoints dimensionality, not GPU partitioning, as the source of computational hardness (§4).
We validate on Kueue, the standard Kubernetes workload queuing system (§5), using CPU/memory and GPU resources via Dynamic Resource Allocation (DRA). Measurements confirm internal consistency (Little’s Law ratio = 1.000) and show that the vector 𝑘 eff correctly identifies the bottleneck resource dimension (memory or GPU), while a scalar estimate misses it entirely. The Erlang-C approximation overestimates observed wait times by 2.3–18×—conservative but too loose for point prediction. A simple EMA baseline gives better point accuracy; the Erlang-C approximation’s value is as an a priori bound requiring no historical observations.
Preprint, 2026,
Sohan Kunkerkar
2
Background and Motivation
2.3
2.1
GPU Cluster Admission Architecture
The Kubernetes Enhancement Proposal for workload visibility (KEP-168) explicitly excluded wait time estimation: “we don’t have the means to estimate wait time at the moment” [19]. Users see “Pending” with no indication of whether admission is minutes or hours away. This gap has motivated multiple community feature requests [20–22]. We show that the gap is not merely an engineering omission but a consequence of a missing theoretical foundation: without the quotable/unfeasible partition, any wait time estimate is meaningless because it averages over workloads with finite and infinite expected wait.
We describe the admission architecture of Kueue [4], the reference implementation for Kubernetes batch workload queuing, managing admission across CPU, memory, GPU, and other resource types. The architecture is representative of production batch schedulers including Slurm and proprietary cloud schedulers. Resource Model. A cluster is organized into a hierarchy of Cohorts, ClusterQueues (CQs), and LocalQueues (LQs). Each CQ has a nominal quota specifying guaranteed capacity across multiple ResourceFlavors (e.g., NVIDIA A100, H100, or MIG profiles like 1g.10gb). Each flavor-resource pair (𝑓 , 𝑟 ) defines one dimension of the capacity vector. CQs within a Cohort may borrow unused capacity from sibling CQs, subject to borrowing and lending limits. Admission Pipeline. The scheduler operates in discrete cycles. Each cycle: (1) dequeues one head workload per CQ, (2) takes an immutable snapshot of cluster state, (3) computes resource flavor assignments via greedy matching, (4) orders workloads by priority or fair-share usage, (5) admits workloads greedily in order, updating the snapshot, and (6) requeues unadmitted workloads. Two Pending Pools. Unadmitted workloads are placed in one of two pools: • The active heap: workloads eligible for the next scheduling attempt, ordered by priority and timestamp. • The inadmissible set: workloads that failed admission and will not be retried until cluster state changes (e.g., a workload completes or a CQ is reconfigured). Scheduling Disciplines. Two disciplines govern head-ofline behavior: StrictFIFO blocks all workloads behind an inadmissible head (classic head-of-line blocking). BestEffortFIFO moves inadmissible heads to the inadmissible set, allowing subsequent workloads to proceed. 2.2
Why Existing Queueing Theory Doesn’t Apply Directly
The Wait Time Estimation Gap
3
Queueing Model
3.1
System Definition
Definition 1 (GPU Cluster Admission System). A GPU Cluster Admission System is a tuple S = (Q, F , R, C, W) where: • Q = {𝑞 1, . . . , 𝑞𝑚 } is a set of cluster queues. • F = {𝑓1, . . . , 𝑓𝑛 } is a set of resource flavors. • R = {𝑟 1, . . . , 𝑟𝑑 } is a set of resource types (e.g., GPU count, GPU memory, CPU, system memory). • C : Q × F × R → R ≥0 is the capacity function, where C(𝑞, 𝑓 , 𝑟 ) is the nominal quota of resource 𝑟 in flavor 𝑓 for queue 𝑞. • W is the set of workload classes, where each class 𝑗 ∈ W is characterized by: – A resource demand function d 𝑗 : F × R → R ≥0 , specifying the resources required per flavor. – An arrival process with rate 𝜆 𝑗 . – A service time distribution 𝑆 𝑗 with mean E[𝑆 𝑗 ] and coefficient of variation 𝐶𝑆 𝑗 . Definition 2 (Admission). A workload of class 𝑗 is admitted to queue 𝑞 via flavor 𝑓 when: ∀𝑟 ∈ R :
d 𝑗 (𝑓 , 𝑟 ) ≤ Available(𝑞, 𝑓 , 𝑟 )
(1)
where Available(𝑞, 𝑓 , 𝑟 ) = C(𝑞, 𝑓 , 𝑟 )−Usage(𝑞, 𝑓 , 𝑟 )+Borrowed(𝑞, 𝑓 , 𝑟 ) is the currently unused capacity including borrowed resources from the cohort.
Definition 3 (Potential Available Capacity). The potential Classical queueing results (M/M/𝑘, M/G/1, etc.) assume: (1) scalar available capacity of queue 𝑞 for flavor 𝑓 and resource 𝑟 is: resource requirements, (2) homogeneous servers, and (3) inPotAvail(𝑞, 𝑓 , 𝑟 ) = C(𝑞, 𝑓 , 𝑟 ) + MaxBorrow(𝑞, 𝑓 , 𝑟 ) (2) dependent arrivals. GPU cluster admission violates all three: 1. Vector resources. Admission requires fitting a 𝑑-dimensionalwhere MaxBorrow(𝑞, 𝑓 , 𝑟 ) is the maximum borrowable capacity from the cohort hierarchy, bounded by lending and borrowrequest vector against a 𝑑-dimensional capacity vector. ing limits. This represents the capacity available if all other This is vector bin packing, which has no APTAS for workloads in the cohort were to complete. 𝑑 ≥ 2 [6]. 2. Heterogeneous flavors. Different ResourceFlavors have different capacity vectors and node affinity constraints. A workload may fit flavor 𝑓1 but not 𝑓2 . 3. Preemption feedback. Preempted workloads re-enter the queue with backoff counters and modified ordering metadata, creating state-dependent arrivals.
3.2
The Quotable/Unfeasible Partition
Definition 4 (Quotable and Unfeasible Workloads). A pending workload of class 𝑗 targeting queue 𝑞 is: • Quotable if there exists a flavor 𝑓 ∈ F such that d 𝑗 (𝑓 , 𝑟 ) ≤ PotAvail(𝑞, 𝑓 , 𝑟 ) for all 𝑟 ∈ R.
Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters
• Unfeasible otherwise. Theorem 1 (Partition Necessity). Let P be a pending queue where a fraction 𝛼 > 0 of workloads are unfeasible (the remainder quotable with finite expected wait 𝜇𝑊 < ∞). For any wait time estimator 𝑊ˆ : P → R ≥0 that does not distinguish quotable from unfeasible workloads (i.e., 𝑊ˆ depends only on observable queue position and resource request, not on feasibility classification), the expected mean absolute error over a random workload 𝑤 drawn uniformly from P satisfies: E |𝑊ˆ (𝑤) − 𝑊 (𝑤)| ≥ 𝛼 · (𝑀 − 𝜇𝑊 ) for any finite estimator cap 𝑀 = max𝑤 𝑊ˆ (𝑤) < ∞, and equals ∞ for estimators without a finite cap. In either case, the error grows without bound as the horizon increases.
Preprint, 2026,
For multiple workload classes, 𝑘 eff depends on the class mix. We use the dominant resource approximation: C(𝑞, 𝑓 ∗, 𝑟 ) 𝑘 eff (𝑞) = min Í (4) ∗ 𝑟 ∈R 𝑗 𝜙 𝑗 · d 𝑗 (𝑓 , 𝑟 ) Í where 𝜙 𝑗 = 𝜆 𝑗 / 𝑗 ′ 𝜆 𝑗 ′ is the class proportion and 𝑓 ∗ = arg min 𝑓 𝑘 eff (𝑞, 𝑓 ) is the bottleneck flavor. Proposition 1 (Vector Packing Loss). For 𝑑 ≥ 2 resource dimensions, the effective server count satisfies: 𝑑 1 ∑︁ 𝐶𝑟 (5) 𝑘 eff ≤ 𝑑 𝑟 =1 𝑑¯𝑟 where 𝐶𝑟 is the capacity in dimension 𝑟 and 𝑑¯𝑟 is the mean demand. Equality holds only when all demand vectors are aligned (proportional across dimensions).
Proof. Partition P into quotable set P𝑄 (fraction 1 − 𝛼) and unfeasible set P𝑈 (fraction 𝛼). For 𝑤 ∈ P𝑈 , 𝑊 (𝑤) = ∞ by Proof. By the vector packing constraint, each admitted workDefinition 4: no amount of waiting yields admission without load must fit in all dimensions simultaneously. The perreconfiguration. If 𝑊ˆ has a finite cap 𝑀, then for unfeasible dimension capacity ⌊𝐶𝑟 /𝑑¯𝑟 ⌋ is an upper bound assuming workloads |𝑊ˆ (𝑤) −𝑊 (𝑤)| = ∞, and the expected error over dimension 𝑟 is the bottleneck. The minimum over dimena random workload is at least 𝛼 · ∞ = ∞. sions gives 𝑘 eff . The arithmetic mean of per-dimension capacTo make the bound constructive, consider a truncated ities is an upper bound on this minimum, with equality only model where unfeasible workloads eventually leave the queue when all dimensions are equally constrained (proportional after a timeout 𝑇 . Then unfeasible workloads have true wait demands). □ 𝑊 = 𝑇 , and the estimator error on the unfeasible fraction is at least 𝛼 · |𝑇 − 𝑀 |. As 𝑇 → ∞ (no timeout), the error 3.4 M/G/𝑘 Domination and Wait Time Finiteness diverges. Even with a practical timeout, the error contribuModeling Assumption 1 (M/G/𝑘 Domination). tion from the unfeasible fraction is 𝛼 · (𝑇 − 𝑀) when 𝑇 > 𝑀, Let 𝑊 real denote the wait time of a quotable workwhich dominates the 𝑂 (𝜎𝑊 ) estimation error achievable on load in the real system (with vector packing, prequotable workloads. emption feedback, and scheduling policy). Let𝑊 M/G/k Alternatively, if 𝑊ˆ outputs ∞ for some workloads, it must denote the wait time in an M/G/𝑘 queue with do so without the quotable/unfeasible label (by assumption). 𝑘 = 𝑘 eff (𝑞) servers (Definition 5), arrival rate For any threshold-based strategy outputting ∞ for workloads Í 𝜆 = 𝜆 + 𝜇 where 𝜆 = 𝜆 is the total arrival 𝑝 eff 𝑗 𝑗 with resource request above some cutoff, there exist quotable rate (including preemption feedback rate 𝜇𝑝 ), and workloads with large requests (near the capacity limit) that service time distribution 𝑆. We assume: are misclassified, incurring infinite error on those quotable workloads. 𝑊 real ≤st 𝑊 M/G/k Some form of feasibility classification is therefore neceswhere ≤st denotes stochastic ordering. sary for bounded-error wait time estimation; the quotable/unfeasible partition based on potential available capacity (Definition 4) Justification. We argue that the real system is no worse is a natural such classification. □ than the M/G/𝑘 reference by examining each structural difference. A formal coupling construction on a common prob3.3 Effective Server Count ability space remains open; the following is a plausibility The key modeling challenge is determining 𝑘 eff : how many argument that we validate empirically in §5. workloads can a CQ serve simultaneously given its multi(i) Vector packing. The real system admits a workload only dimensional capacity? when all 𝑑 resource dimensions fit. 𝑘 eff is defined as the minimum over all dimensions (Definition 5), so the M/G/𝑘 Definition 5 (Effective Server Count). For a queue 𝑞 serving reference has at most 𝑘 eff servers. In the real system, some a single workload class 𝑗 with demand vector d 𝑗 , the effective workloads may fit in dimensions where others do not, allowserver count is: ing slightly more concurrent service than the worst-case 𝑘 eff . C(𝑞, 𝑓 , 𝑟 ) real ≥ 𝑘 , and M/G/𝑘 with 𝑘 = 𝑘 Thus the real system has 𝑘 eff eff eff 𝑘 eff (𝑞, 𝑗) = max min (3) d 𝑗 (𝑓 , 𝑟 ) 𝑓 ∈ F𝑗 𝑟 ∈ R dominates. where F𝑗 ⊆ F is the set of flavors compatible with class 𝑗 (ii) Preemption feedback. We account for preemption by (satisfying node affinity and taint constraints). inflating the arrival rate to 𝜆eff = 𝜆 + 𝜇𝑝 , treating preempted
Preprint, 2026,
workloads as new arrivals with i.i.d. service times drawn from the original distribution 𝑆. For workloads with checkpointing, the remaining service time after preemption is strictly shorter than a fresh draw from 𝑆, making the i.i.d. reference conservative. For restart-from-scratch workloads, the re-entering job has the same service time as before, introducing positive autocorrelation in the arrival stream. This autocorrelation can increase queue lengths beyond the i.i.d. case, potentially violating the domination direction. We restrict the domination claim to systems with checkpoint-based preemption or low preemption rates (𝜇𝑝 ≪ 𝜆); the restartfrom-scratch case requires analysis under correlated arrivals (e.g., GI/GI/𝑘) which we leave to future work. (iii) Scheduling policy. The M/G/𝑘 reference uses FCFS. Under BestEffortFIFO, blocked workloads are moved aside, avoiding head-of-line blocking—this can only reduce wait times relative to FCFS (where a blocked head delays all subsequent workloads). Under StrictFIFO, head-of-line blocking increases wait times beyond FCFS, meaning the M/G/𝑘/FCFS reference underestimates wait times for StrictFIFO queues. We restrict the domination claim to BestEffortFIFO; for StrictFIFO, the M/G/𝑘 reference is optimistic rather than conservative. Sufficient conditions. Modeling Assumption 1 is supported when three conditions hold: (1) the scheduling discipline is BestEffortFIFO (avoiding head-of-line blocking), (2) preemption is checkpoint-based or infrequent (𝜇𝑝 ≪ 𝜆), and (3) arrivals are approximately Poisson. The assumption may fail under StrictFIFO (where head-of-line blocking increases wait times beyond FCFS) or high-rate restart-fromscratch preemption (where autocorrelated re-entries can exceed i.i.d. wait times). We treat this as a modeling assumption and validate it empirically rather than claiming a formal proof. Theorem 2 (Quotable Wait Time Finiteness). For a quotable workload of class 𝑗 in queue 𝑞, under the stability condition 𝜌𝑞 < 1 where 𝜆eff · E[𝑆] 𝜌𝑞 = 𝑘 eff (𝑞) with 𝜆eff = 𝜆 + 𝜇𝑝 (preemption-adjusted arrival rate), the expected wait time E[𝑊𝑞 ( 𝑗)] is finite. Proof. Under Modeling Assumption 1, 𝑊 real ≤st 𝑊 M/G/k . Under 𝜌𝑞 < 1, the M/G/𝑘 reference queue is positive recurrent [7] and all moments of𝑊 M/G/k are finite. Stochastic domination preserves finiteness of expectations, so E[𝑊 real ] ≤ E[𝑊 M/G/k ] < ∞. □ 3.5
Wait Time Bounds
A key difficulty in multi-server queueing is that no practical closed-form upper bound on E[𝑊𝑞 ] is known for M/G/𝑘 with 𝑘 > 1. Gupta et al. [9] proved that any approximation using only the first two moments of the service distribution
Sohan Kunkerkar
√ has a worst-case ratio growing as 𝜌 − 2(𝑘+1) between the maximum and minimum achievable E[𝑊𝑞 ]—two-moment formulas are fundamentally limited for multi-server queues. Li and Goldberg [10] proved the first multi-server Kingman bound: under FCFS with finite (2 + 𝜖)-moment service times, E[𝑊𝑞 ] = 𝑂 (1/(1 − 𝜌)), but with prefactors too large for practical prediction. We therefore present a proven structural bound (Theorem 3) establishing the correct asymptotic scaling, and a practical approximation (Equation 7) for actual wait time estimation, validated empirically in §5. Theorem 3 (Wait Time Scaling). For quotable workloads in queue 𝑞 under FCFS with effective server count 𝑘 = 𝑘 eff (𝑞), utilization 𝜌 < 1, and service times with finite (2 + 𝜖)-th moment, the expected wait time satisfies: 1 (6) E[𝑊𝑞 ] = 𝑂 1−𝜌 That is, E[𝑊𝑞 ] is finite and grows at most inversely with the capacity slack 1 − 𝜌. Proof. Under Modeling Assumption 1, the quotable partition of queue 𝑞 is dominated by an M/G/𝑘 queue with 𝑘 = 𝑘 eff (𝑞) servers. Apply the multi-server Kingman bound of Li and Goldberg [10], which establishes E[𝑊𝑞 ] ≤ 𝐶 (𝜖, 𝑘)/(1 − 𝜌) for a constant 𝐶 (𝜖, 𝑘) depending on the moment index and server count. The scaling holds for the real system by stochastic domination. □ While Theorem 3 establishes the correct scaling, the constant 𝐶 (𝜖, 𝑘) is too large for prediction. For practical use, we employ the standard M/M/𝑘 correction: Approximation 1. (Modified Erlang-C Wait Time Estimate.) For quotable workloads with effective server count 𝑘, utilization 𝜌, and service time coefficient of variation 𝐶𝑆 : E[𝑆] 𝑊ˆ 𝑞 = 𝐶 (𝑘, 𝜌) · · | {z } 𝑘 (1 − 𝜌) | {z } Erlang-C
𝐶𝑆2 + 1 2 | {z }
(7)
M/M/𝑘 wait variability correction
where 𝐶 (𝑘, 𝜌) = 𝑃 (wait > 0) is the Erlang-C probability 𝐶 (𝑘, 𝜌) =
(𝑘𝜌)𝑘 /𝑘! Í −1 (𝑘𝜌)𝑘 /𝑘! + (1 − 𝜌) 𝑘𝑛=0 (𝑘𝜌)𝑛 /𝑛!
(8)
This is the Cosmetatos-Tijms approximation [11], which interpolates between the exact M/M/𝑘 result (𝐶𝑆 = 1) and the exact M/D/𝑘 result (𝐶𝑆 = 0). The approximation is wellstudied for classical M/G/𝑘 queues [11] but has no proven error guarantee. In our setting—where BestEffortFIFO departs from FCFS and 𝑘 eff is a worst-case estimate—we observe 2.3–18× overestimation (§5).
Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters
Accounting for Preemption Feedback. Preempted workloads re-enter the queue with rate 𝜇𝑝 . The effective arrival rate becomes 𝜆eff = 𝜆 + 𝜇𝑝 . Substituting into the utilization formula: (𝜆 + 𝜇𝑝 ) · E[𝑆] 𝜌 eff = (9) 𝑘 The stability condition becomes 𝜌 eff < 1, which is more restrictive than the no-preemption case. Accounting for Cohort Borrowing. When queue 𝑞 can borrow from siblings in a cohort, the effective capacity increases. Let 𝐵(𝑞, 𝑓 , 𝑟 ) denote the expected available borrowed capacity (a function of sibling utilization). The effective server count with borrowing: C(𝑞, 𝑓 ∗, 𝑟 ) + E[𝐵(𝑞, 𝑓 ∗, 𝑟 )] + 𝑘 eff (𝑞) = min (10) 𝑟 𝑑¯𝑟 This gives a tighter bound in under-utilized cohorts and degrades gracefully as sibling utilization increases. Priority Classes. For a system with 𝑃 priority classes where class 𝑝 preempts class 𝑝 ′ < 𝑝, we use the standard preemptive-priority M/G/𝑘 result: the wait time for class 𝑝 depends only on the load from classes ≥ 𝑝: Í 𝑝 ′ ≥𝑝 𝜆𝑝 ′ · E[𝑆 𝑝 ′ ] (11) 𝜌𝑝 = 𝑘
4
NP-Hardness of Optimal Admission
We now show that the admission problem is computationally hard. We first observe that MIG packing with fixed profiles is tractable, then show that adding multi-resource vectors with topology affinity makes the problem NP-hard. Definition 6 (GPU Topology-Aware Admission with Partitioning (GTAP)). Given: • A set of GPU nodes N connected by a topology graph 𝐺 = (N, 𝐸) where edges represent NVLink connections. • A set of MIG partition profiles Π for each GPU (e.g., 1g.10gb, 2g.20gb, 3g.40gb, 7g.80gb for A100). • A set of workloads W, each with a multi-dimensional resource demand vector d𝑤 ∈ R𝑑≥0 (GPU compute, GPU memory, CPU, system memory) and optional topology affinity constraints (e.g., all GPUs on the same NVLink domain). Admission consumes capacity from a shared quota pool: each admitted workload’s demand vector is subtracted from the available capacity. Decide: Can all workloads in W be simultaneously admitted? Proposition 2 (Fixed-Profile MIG Packing is Tractable). When resource demands are one-dimensional (GPU memory only), the MIG profile set |Π| is a fixed constant, and there are no topology constraints, GTAP is solvable in polynomial time.
Preprint, 2026,
Proof. With |Π| fixed profile sizes, each GPU has at most 𝑂 (|Π| |Π| ) distinct valid partitionings—a constant. The number of workload types by profile is at most |Π|. A dynamic programming formulation over (GPU index, counts of remaining workloads per type) has state space polynomial in |W|. □ Theorem 4 (NP-Hardness of Multi-Resource GTAP). GTAP is NP-hard when workloads have multi-dimensional resource demands (𝑑 ≥ 2), even without topology constraints. Proof sketch. We reduce from 𝑑-dimensional vector bin packing, which is strongly NP-hard for 𝑑 ≥ 2 [6]. Given an instance with 𝑛 items of 𝑑-dimensional sizes and 𝑚 unitcapacity bins: • Create 𝑚 GPU nodes, each with capacity vector (1, 1, . . . , 1) ∈ R𝑑 . • Create 𝑛 workloads with demand vectors matching the item sizes. • Fix a single MIG profile (full GPU, no partitioning). All workloads are simultaneously admissible iff the vector bin packing instance has a solution. Since 𝑑-dimensional vector bin packing is strongly NP-hard [6], GTAP is NP-hard. □ Corollary 1 (Topology Increases Hardness). GTAP remains NP-hard with topology affinity constraints, since the unconstrained problem is already hard. Adding constraints (e.g., requiring NVLink-connected GPUs) can only increase the hardness. Corollary 2 (Optimal Admission Ordering). In the static case where all workloads are available at 𝑡 = 0, choosing the admission sequence that minimizes total weighted wait time is NP-hard under multi-resource demands. Proof. If optimal static ordering were polynomial, we could solve GTAP by checking whether the optimal ordering achieves zero total wait (simultaneous admission of all workloads), contradicting NP-hardness. □ Proposition 2 and Theorem 4 together pinpoint the source of hardness: it is not MIG partitioning (fixed profiles, polynomial), but the multi-dimensional vector packing inherent in multi-resource admission. This is precisely the structure our queueing model captures via the effective server count 𝑘 eff (Definition 5), which reduces the multi-dimensional problem to a scalar quantity amenable to M/G/𝑘 analysis.
5
Evaluation
We validate our queueing model on Kueue v0.19.0 using controlled workload injection on a local Kubernetes cluster. 5.1
Experimental Setup
Cluster Configuration. We deploy a 4-node Kubernetes 1.36 cluster (1 control plane, 3 workers) using kind [23]. A single ClusterQueue cq-eval is configured with 2 CPU
Preprint, 2026,
Sohan Kunkerkar
Table 1. Mapping of queueing parameters to Kueue metrics. Parameter
Kueue Metric
Arrival rate 𝜆 Service time 𝑆 Queue length 𝐿𝑞 In-service 𝐿𝑠 Wait time 𝑊𝑞 Utilization 𝜌 Preemption rate 𝜇𝑝
rate(kueue_admitted_workloads_total)∗ kueue_execution_time_seconds kueue_pending_workloads{status=active} kueue_admitted_active_workloads kueue_admission_wait_time_seconds resource_usage / nominal_quota rate(kueue_preempted_workloads_total)
nominal quota and no borrowing, yielding 𝑘 eff = ⌊2.0/0.5⌋ = 4 effective servers for 500m CPU workloads. BestEffortFIFO scheduling is enabled. Workload Generator. We submit Kubernetes Jobs with Poisson inter-arrival times and exponentially distributed service times (mean 20s). Each job requests 500m CPU and 64Mi memory. We sweep the target utilization 𝜌 from 0.3 to 0.92 by adjusting the arrival rate 𝜆 = 𝜌 ·𝑘 eff /E[𝑆], submitting 80 jobs per utilization level. Metrics Collection. We extract timing data directly from Kueue Workload object conditions (creation timestamp, admission timestamp, completion timestamp), giving exact perworkload wait times without Prometheus aggregation loss. Table 1 shows the correspondence to production Prometheus metrics. ∗ In steady state (𝜌 < 1), admission throughput equals arrival rate by flow balance. We restrict our analysis to 𝜌 < 0.95. 5.2
Partition Non-Vacuity
When 5% of submitted workloads request resources exceeding the ClusterQueue’s potential available capacity (20 CPU against a 2 CPU quota), 50% of pending workloads are in Kueue’s inadmissible set at measurement time. The inadmissible set is a superset of the truly unfeasible partition (some workloads are temporarily inadmissible but quotable), so this is an upper bound on the unfeasible fraction. The nonzero fraction confirms that the quotable/unfeasible partition (Theorem 1) is non-vacuous in practice: a non-trivial fraction of pending workloads cannot be admitted without cluster reconfiguration. 5.3
Little’s Law Validation
As a consistency check, we verify that Little’s Law (𝐿 = 𝜆 ·𝑊 ) holds on observed Kueue data. We compute 𝐿obs as the timeaveraged number of waiting workloads (integrated from arrival/admission event timestamps) and 𝜆 · 𝑊 from the observed arrival rate and mean wait time. Across all utilization levels with 𝜌 obs < 0.95, the ratio 𝐿obs /(𝜆 · 𝑊 ) equals 1.000 (to three decimal places), confirming that the queueing model is internally consistent with observed Kueue behavior. At 𝜌 obs = 0.95 the ratio is 0.950,
Table 2. Wait time prediction across utilization levels. 𝑘 eff = 4, truncated exponential service times (mean 20s, observed mean 21–25s, 𝐶𝑆 ≈ 0.8–1.0), 80 jobs per level. 𝜌 tgt
𝜌 obs
𝑊ˆ 𝑞 (s)
𝑊𝑞 (s)
Ratio
Little
0.30 0.50 0.65 0.75† 0.85 0.92†
0.27 0.64 0.72 1.16 0.95 1.23
0.7 5.0 7.9 — 88.9 —
0.04 1.2 3.5 49.7 11.0 42.1
18× 4.1× 2.3× — 8.1× —
1.000 1.000 1.000 0.836 0.950 0.785
† Transient overload: 𝜌
obs > 1 over 80 jobs. Erlang-C is undefined; real system absorbs the burst through transient queueing.
and above 𝜌 = 1.0 (transient overload) the ratio degrades to 0.79–0.84, as expected when the steady-state assumption is violated. 5.4
Wait Time Prediction Accuracy
We compare predicted E[𝑊𝑞 ] from the modified Erlang-C approximation (Equation 7) against observed mean wait times, and against an exponential moving average (EMA) baseline (𝛼 = 0.3) that predicts wait time from recent history. Table 2 shows the Erlang-C approximation consistently overestimates observed wait times by 2.3–18× across the stable regime (𝜌 obs < 1). The overestimation is largest at low 𝜌 (18× at 𝜌 = 0.27, where observed waits are near zero and the model predicts 0.7s) and tightest in the moderate regime (2.3× at 𝜌 = 0.72). At 𝜌 obs > 1, the formula is undefined and the model provides no prediction. The overestimation has three sources: (1) BestEffortFIFO avoids head-of-line blocking, producing shorter waits than the FCFS assumption in M/G/𝑘; (2) the Cosmetatos-Tijms variability correction is calibrated for the M/M/𝑘 to M/D/𝑘 range, not for the truncated exponential distribution used here; and (3) the dominant-resource 𝑘 eff is a worst-case estimate that understates the actual concurrency. Why conservative, and can we do better? The overestimation is structural, not accidental: 𝑘 eff is a lower bound on actual concurrency (vector packing allows more concurrent workloads when demands are not perfectly aligned), and BestEffortFIFO produces shorter waits than the FCFS assumption in M/G/𝑘. A tighter bound would require either (a) a scheduling discipline-specific analysis (no M/G/𝑘 results exist for BestEffortFIFO), or (b) a sharper 𝑘 eff that accounts for the actual workload mix rather than the worst-case bottleneck dimension. Both are open problems. The Erlang-C approximation is not a proven upper bound—it is an empirically conservative estimate under the conditions tested. Comparison with EMA baseline. In a separate experiment at 𝜌 obs ≈ 0.9 (64 workloads, 15s mean service), the Erlang-C MAE was 18.2s versus the EMA baseline’s (𝛼 = 0.3)
Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters
Preprint, 2026,
Table 3. Vector packing: scalar vs. multi-dimensional 𝑘 eff . The scalar CPU-only estimate (𝑘 = 8) overestimates capacity and therefore underestimates queueing delay; the vector estimate (𝑘 = 4, memory-bottlenecked) correctly identifies the binding dimension. 80 jobs/level. 𝜌 tgt
𝜌 vec
𝑊ˆ 𝑘=4
𝑊ˆ 𝑘=8
𝑊𝑞
Bottleneck
0.50 0.70
0.60 0.77
3.2 10.7
0.0 0.1
2.4 2.5
memory memory
MAE of 6.8s. The EMA baseline wins on point prediction accuracy because it adapts to recent observations. However, the Erlang-C approximation is an a priori prediction requiring only the arrival rate, service time distribution, and quota—it does not need historical wait time observations. This makes it suitable for capacity planning (“what will wait times be if we add this workload class?”) where no historical data exists. The EMA is better for real-time estimation of a running system. 5.5
Scheduling Latency
The continuous M/G/𝑘 model assumes instantaneous admission decisions. In Kueue, the scheduler runs in a loop (wait.UntilWithBackoff), processing all eligible heads each iteration. The time between a workload becoming eligible and the next scheduler iteration depends on current load and is not a fixed interval. At low utilization, this scheduling latency dominates observed wait times (observed 𝑊𝑞 ≈ 0.04s at 𝜌 = 0.27). At moderate-to-high utilization, queueing delays dominate and the scheduling latency is negligible. 5.6
Vector Packing Validation
To test the multi-dimensional 𝑘 eff reduction (Definition 5), we configure a ClusterQueue with asymmetric quotas: 4 CPU and 2Gi memory. Workloads request 500m CPU and 512Mi memory, giving: 𝑘 eff (CPU) = ⌊4/0.5⌋ = 8 𝑘 eff (mem) = ⌊2048/512⌋ = 4 𝑘 eff (vector) = min(8, 4) = 4 Table 3 shows the result. The scalar CPU-only 𝑘 eff = 8 predicts near-zero wait time (𝑊ˆ < 0.1s) because 𝜌 CPU ≈ 0.3— it does not see the memory bottleneck. The vector 𝑘 eff = 4 correctly identifies memory as the binding dimension and predicts 𝑊ˆ = 3.2s at 𝜌 = 0.50, overestimating the observed 2.4s by 33%. At 𝜌 = 0.70, the overestimate widens to 4.3× (10.7s predicted vs. 2.5s observed) as the Erlang-C formula becomes more sensitive near the stability boundary. A third run at 𝜌 target = 0.85 produced 𝜌 obs > 1 and is excluded (same treatment as Table 2† ). Without the multi-dimensional 𝑘 eff reduction, the model misses the bottleneck entirely and underestimates wait times by > 95%.
Table 4. GPU resource validation via DRA. The GPUbottlenecked 𝑘 eff = 4 correctly identifies GPU as the binding dimension; the CPU-only 𝑘 eff = 16 misses the bottleneck. 30 jobs/level. 𝜌 tgt
𝜌 GPU
𝑊ˆ 𝑘=4
𝑊ˆ 𝑘=16
𝑊𝑞
Little
0.50 0.70 0.85
0.81 0.76 0.80
16.8 9.3 11.9
0.0 0.0 0.0
4.8 1.5 4.3
1.000 1.000 1.000
The 2D experiment validates the single-class 𝑘 eff (Definition 5). The multi-class dominant-resource extension (Equation 4), which weights demand by class proportion 𝜙 𝑗 , is a standard DRF-style approximation [24] not separately tested here. GPU resource validation. To validate with GPU resources, we configure Kueue’s DRA (Dynamic Resource Allocation) integration with a simulated GPU driver (dra-example-driver) providing 8 GPUs per node across 3 nodes. The ClusterQueue quota is set to 4 GPUs, 8 CPU, and 8Gi memory. Each workload requests 1 GPU (via ResourceClaimTemplate), 500m CPU, and 256Mi memory, giving 𝑘 eff (GPU) = 4, 𝑘 eff (CPU) = 16, 𝑘 eff (vector) = 4. Table 4 confirms the same pattern as the CPU/memory experiment (Table 3): the scalar CPU-only estimate misses the GPU bottleneck entirely (𝑊ˆ = 0), while the vector 𝑘 eff = 4 overestimates by 2.5–3.5× (conservative direction). Little’s Law holds exactly. The queueing model is resource-typeagnostic: the same 𝑘 eff reduction works whether the bottleneck is memory or GPU quota. MIG partitioning and NVLink topology constraints introduce additional structure not exercised here.
6
Related Work
Queueing Theory for GPU Scheduling. Mitzenmacher and Shahout [1] survey learning-augmented scheduling with predictions, identifying open problems in multi-server systems. Dai et al. [2] prove throughput-optimality for batched LLM scheduling. Wang and Grosof [3] derive novel lower bounds on M/G/𝑘 response time. All focus on inference-level scheduling; we address the cluster admission layer. GPU Cluster Schedulers. Tiresias [12] applies multilevel feedback queues from queueing theory to GPU job scheduling but does not derive wait time bounds. Shockwave [14] provides fair GPU allocation without queueingtheoretic analysis. HiveD [13] introduces topology-aware virtual private clusters but does not consider MIG or queueing models. Lu et al. [17] use predictive multi-dimensional resource scheduling for GPU utilization but rely on ML prediction rather than queueing theory.
Preprint, 2026,
Sohan Kunkerkar
Fair Resource Allocation. Dominant Resource Fairness [24] defines max-min fairness for multi-resource environments and is the theoretical basis for Kueue’s fair-sharing mechanism. Themis [27] achieves finish-time fairness for ML training. Gandiva [25] exploits GPU time-slicing for locality and packing. Pollux [28] co-optimizes cluster scheduling with per-job hyperparameters. Gavel [26] provides heterogeneityaware fair scheduling across GPU types. None derive queueingtheoretic wait time bounds.
model. Admission checks (e.g., resource flavor validation, admission webhooks) add per-workload overhead not included in service time.
MIG Scheduling. Villarrubia et al. [15] study moldable MIG scheduling with a 7/4 approximation for single-GPU packing. Our GTAP extends to multi-resource vector packing with topology. KRYPTON [16] uses MIG for isolation but does not address scheduling optimality.
8
Vector Bin Packing. Chekuri and Khanna [6] prove no APTAS exists for 𝑑 ≥ 2 dimensions. We connect this hardness to the effective server count in queueing models.
Fair-Share Convergence. Kueue’s Dominant Resource Share mechanism implements a variant of DRF. Whether the usage-based admission ordering converges under dynamic arrivals and departures is an open control-theoretic question.
7
Predictive Admission. Mitzenmacher’s framework for scheduling with predictions could be extended to admission control: given predicted service times, can we improve wait time bounds? Our model provides the foundation for such analysis.
Limitations
Our model makes several simplifying assumptions that should be understood when applying the results in practice. Poisson Arrivals. We assume Poisson arrivals (the “M” in M/G/𝑘). Real workload arrival processes exhibit burstiness (e.g., batch submissions, periodic cron jobs) that may violate this assumption. The GI/GI/𝑘 extension of Li and Goldberg [10] covers general inter-arrival times but with even larger constants. Admission Fair Sharing (AFS).. When AFS is enabled, admission ordering is by usage share rather than FIFO. This violates the FCFS assumption underlying the M/G/𝑘 model. Our bounds apply to non-AFS clusters or within a single LocalQueue (where AFS does not reorder). Extending to AFS ordering requires a processor-sharing or generalizedprocessor-sharing model. Concurrent Admission. By default, Kueue admits one workload per ClusterQueue per scheduler iteration. The alpha-stage ConcurrentAdmission feature gate allows parallel flavor assignment but does not change the per-iteration admission count. Our M/G/𝑘 model assumes continuous service; the per-iteration scheduling latency introduces additional delay at low utilization. Unmodeled Features. Several production features are outside our model’s scope: Topology-Aware Scheduling (TAS) adds placement constraints beyond vector packing. Elastic jobs have variable resource demands. waitForPodsReady adds a post-admission delay before the workload is considered running. Hierarchical cohorts create multi-level borrowing relationships not captured by our single-level borrowing
Arrival Rate Measurement. As noted in §5, we approximate arrival rate using admission throughput. This is valid under steady state but underestimates true arrivals under saturation. A dedicated arrival counter would improve accuracy for 𝜌 > 0.95.
Discussion and Open Problems
Online Competitive Admission. Our bounds are steadystate. An online competitive analysis of Kueue’s greedy admission against an optimal offline scheduler remains open.
9
Conclusion
We presented the first formal wait time bounds for GPU cluster admission control. Our central result—the quotable/unfeasible partition theorem—shows that accurate wait time estimation requires distinguishing workloads that can eventually be admitted from those that cannot. For quotable workloads, under an explicit stochastic domination assumption (Modeling Assumption 1), we modeled the system as an M/G/𝑘 reference queue with effective server count determined by vector packing, establishing 𝑂 (1/(1 − 𝜌)) wait time scaling and providing a practical modified Erlang-C approximation. We proved that optimal admission ordering is NP-hard under multi-resource vector packing, pinpointing dimensionality (not MIG partitioning) as the source of hardness. Experiments on Kueue v0.19.0 with CPU, memory, and GPU (via DRA) resources confirm that the vector 𝑘 eff correctly identifies bottleneck dimensions and that the Erlang-C approximation consistently overestimates in the conservative direction, though with 2.3–18× looseness that limits its use as a point predictor. All model parameters are derivable from existing Kueue metrics. Our work provides the theoretical foundation for practical wait time estimation in GPU clusters—a capability that production systems have lacked despite years of user demand. We hope this encourages further application of queueing theory to the cluster admission layer, where significant open problems remain.
Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters
AI Tool Disclosure. AI tools were used for literature search, prose editing, and LaTeX formatting. All theoretical contributions (proofs, model design, experimental methodology) are the authors’ original work.
References [1] M. Mitzenmacher and N. Shahout. Queueing, predictions, and LLMs. Stochastic Systems, 2025. arXiv:2503.07545. [2] J. G. Dai, T. Deng, Y. Li, and T. Peng. Throughput-optimal scheduling algorithms for LLM inference and AI agents. arXiv:2504.07347, 2025. [3] Z. Wang and I. Grosof. Novel lower bounds on M/G/k scheduling. arXiv:2502.08804, 2025. [4] Kubernetes-sigs. Kueue: Kubernetes-native job queueing. https:// kueue.sigs.k8s.io/, 2024. [5] A. B. Yoo, M. A. Jette, and M. Grondona. SLURM: Simple Linux utility for resource management. In JSSPP, 2003. [6] C. Chekuri and S. Khanna. On multidimensional packing problems. SIAM J. Comput., 33(4):837–851, 2004. [7] J. Kiefer and J. Wolfowitz. On the theory of queues with many servers. Trans. Amer. Math. Soc., 78:1–18, 1955. [8] V. Gupta and T. Osogami. On Markov-Krein characterization of the mean waiting time in M/G/k and other queueing systems. Queueing Systems, 68:339–352, 2011. [9] V. Gupta, M. Harchol-Balter, J. G. Dai, and B. Zwart. On the inapproximability of M/G/K: Why two moments of job size distribution are not enough. Queueing Systems, 64(1):5–48, 2010. [10] Y. Li and D. A. Goldberg. Simple and explicit bounds for multiserver queues with 1/(1 − 𝜌 ) scaling. Math. Oper. Res., 50(2):813–837, 2024. [11] H. C. Tijms. A First Course in Stochastic Models. Wiley, 2003. [12] J. Gu, M. Chowdhury, K. G. Shin, et al. Tiresias: A GPU cluster manager for distributed deep learning. In NSDI, 2019. [13] H. Zhao, Z. Han, Z. Yang, et al. HiveD: Sharing a GPU cluster for deep learning with guarantees. In OSDI, 2020. [14] P. Zheng, et al. Shockwave: Fair and efficient cluster scheduling for dynamic adaptation in machine learning. In NSDI, 2023. [15] J. Villarrubia, L. Costero, F. D. Igual, and K. Olcoz. Leveraging multiinstance GPUs through moldable task scheduling. J. Parallel Distrib. Comput., 204, 2025. [16] S. Zhang, A. Xu, Q. Chen, H. Zhao, W. Cui, Z. Wang, Y. Li, L. Xiao, and M. Guo. Efficient performance-aware GPU sharing with compatibility and isolation through kernel space interception. In ATC, 2025. [17] Y. Lu, D. He, T. Ma, Z. Liu, L. Ruan, J. Jiang, and Y. Wu. Bridging the GPU utilization gap: Predictive multi-dimensional resource scheduling for AI workloads. In EuroSys, 2026. [18] Cast AI. 2026 state of Kubernetes optimization report. Technical report, 2026. [19] KEP-168: Workload visibility. Kubernetes Enhancement Proposal, 2023. [20] Kueue Issue #13159: Workload wait time estimation. https://github. com/kubernetes-sigs/kueue/issues/13159, 2026. [21] Kueue Issue #10124: Users need wait time. https://github.com/ kubernetes-sigs/kueue/issues/10124, 2025. [22] Kueue Issue #10614: Admission estimation for MultiKueue. https: //github.com/kubernetes-sigs/kueue/issues/10614, 2025. [23] Kubernetes-sigs. kind: Kubernetes in Docker. https://kind.sigs.k8s.io/, 2024. [24] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, 2011. [25] W. Xiao, R. Bhardwaj, R. Ramjee, M. Sivathanu, et al. Gandiva: Introspective cluster scheduling for deep learning. In OSDI, 2018. [26] D. Narayanan, K. Santhanam, F. Kazhamiaka, A. Phanishayee, and M. Zaharia. Heterogeneity-aware cluster scheduling policies for deep
Preprint, 2026, learning workloads. In OSDI, 2020. [27] K. Mahajan, A. Balasubramanian, A. Singhvi, S. Venkataraman, et al. Themis: Fair and efficient GPU cluster scheduling. In NSDI, 2020. [28] A. Qiao, S. K. Choe, S. J. Subramanya, W. Neiswanger, et al. Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning. In OSDI, 2021.