Pith. sign in

REVIEW 4 major objections 6 minor 28 references

Pending GPU jobs split into two kinds: those with bounded wait under stability, and those that never finish without reconfiguration.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 14:09 UTC pith:KWKQ6GGO

load-bearing objection Honest systems-theory note that frames a real Kueue gap well, but the wait-time theorems stay conditional on an unproven domination assumption. the 4 major comments →

arxiv 2607.28223 v1 pith:KWKQ6GGO submitted 2026-07-30 cs.DC

Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters

Sohan Kunkerkar This is my paper
classification cs.DC
keywords GPU cluster admissionmulti-resource queueingeffective server countvector packingwait time boundsKueueM/G/kquotable workloads
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

GPU cluster operators today cannot say whether a pending job will wait minutes or forever. This paper argues that the missing piece is not better heuristics but a structural split of the pending queue. Workloads that can eventually fit if others finish are quotable and admit classical multi-server wait bounds; workloads that exceed potential capacity even after everything else drains are unfeasible and have no finite wait bound without reconfiguration. For the quotable side, the author reduces multi-resource packing to an effective server count and, under a stated domination assumption, gets the familiar O(1/(1−ρ)) wait scaling plus a practical Erlang-C style estimate. Optimal ordering of admissions is shown NP-hard once demands are multi-dimensional. Validation on Kueue with CPU, memory, and GPU resources shows the vector effective-server count finds the true bottleneck and that the approximation overestimates wait in a conservative direction.

Core claim

The pending admission queue of a multi-tenant GPU cluster decomposes into quotable workloads, which have finite expected wait under stability, and unfeasible workloads, which have none without reconfiguration. Any wait estimator that mixes the two partitions has unbounded error. For quotable work, modeling each queue as an M/G/k system whose k comes from a vector-packing reduction yields O(1/(1−ρ)) wait scaling under an explicit stochastic-domination assumption, while optimal multi-resource admission ordering is NP-hard.

What carries the argument

The quotable/unfeasible partition (by potential available capacity) together with the effective server count k_eff: the minimum, over resource dimensions and compatible flavors, of floor(capacity/demand). That scalar k turns multi-dimensional packing into an M/G/k reference used for finiteness and wait scaling.

Load-bearing premise

The real system’s wait for quotable jobs is assumed never worse than a simple multi-server queue with the same effective server count; that comparison is stated as an assumption, not a fully proved coupling, and is restricted to certain scheduling and preemption regimes.

What would settle it

Run BestEffortFIFO Kueue (or equivalent) under stable load with checkpoint-style preemption and measure whether mean quotable wait stays finite and tracks O(1/(1−ρ)) as utilization approaches one; if measured wait systematically exceeds the M/G/k reference or diverges while ρ_eff < 1, the domination-based bounds fail.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Wait-time UIs and capacity planners must classify jobs as quotable vs unfeasible before quoting any finite ETA.
  • Scalar CPU-only or GPU-only capacity estimates miss binding dimensions; vector k_eff is required for non-vacuous delay prediction.
  • Erlang-C style formulas can serve as a priori conservative bounds without historical waits, while history-based averages remain better for live point estimates.
  • Hardness of optimal admission ordering comes from multi-dimensional packing, not from fixed-profile MIG partitioning alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Production schedulers that only expose a single Pending state will keep producing misleading average wait numbers until they surface the unfeasible partition explicitly.
  • Tightening the bound likely needs either a BestEffortFIFO-specific analysis or a mix-aware k_eff, both left open and directly testable against the same Kueue traces.
  • The same partition-plus-k_eff pattern should transfer to other multi-resource batch queues (CPU/memory/disk fleets) even without GPUs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper formalizes multi-tenant GPU cluster admission (à la Kueue) as a multi-class, multi-resource queueing system. It introduces a quotable/unfeasible partition of the pending queue (Definition 4, Theorem 1), reduces multi-dimensional capacity to an effective server count k_eff via min-dimension vector packing (Definition 5), and—under an explicit stochastic-domination Modeling Assumption 1—transfers M/G/k positive recurrence and Li–Goldberg O(1/(1−ρ)) wait-time scaling to quotable workloads (Theorems 2–3). It also proves NP-hardness of optimal multi-resource admission ordering by reduction from vector bin packing (Theorem 4), while showing fixed-profile MIG packing is polynomial (Proposition 2). Evaluation on Kueue (kind cluster; CPU/memory and DRA GPU) reports exact Little’s Law consistency, correct bottleneck identification by vector k_eff, and conservative Erlang-C overestimation (2.3–18×) versus observed waits.

Significance. If the framework holds under the stated restrictions, it supplies the first usable queueing foundation for cluster-level admission wait estimation—a gap production systems (Kueue, KEP-168) have explicitly left open. The quotable/unfeasible split and the k_eff reduction are practically useful modeling devices; the hardness result cleanly separates MIG profile packing from multi-dimensional packing as the source of intractability. Strengths include explicit labeling of Modeling Assumption 1, restriction of the domination claim to BestEffortFIFO and mild preemption, and empirical checks that are independent of free fitted parameters (k_eff and Erlang-C from quotas and measured λ, S). The main limitation is that the transferable formal guarantees for real Kueue-like systems remain conditional on an unproved coupling.

major comments (4)
  1. [§3.4, Theorems 2–3, Abstract] §3.4 Modeling Assumption 1 / Theorems 2–3: The central transferable claims (finite E[W] and O(1/(1−ρ)) for the real system) are proved only for an M/G/k reference and pushed to W_real by stochastic domination. The manuscript states that a formal coupling is open and gives only a plausibility argument restricted to BestEffortFIFO, checkpoint-based or low-rate preemption, and near-Poisson arrivals; it also notes that under StrictFIFO the reference is optimistic and that restart-from-scratch preemption can violate the direction. The abstract and §1 currently state the scaling as established for cluster admission without always carrying these restrictions. Either prove domination under a clearly stated coupling (even for a restricted discipline), or systematically rephrase abstract/intro/conclusion so that Theorems 2–3 are explicitly conditional on Assumption 1 and the sufficient conditions
  2. [§5, Tables 2–4] §5 Evaluation does not test stochastic order or the domination direction. Tables 2–4 show mean-wait overestimation by a modified Erlang-C formula and Little’s Law identity under BestEffortFIFO with light/no preemption on a kind cluster (80 jobs/level; 30 for GPU). That is consistent with a conservative approximation but is not evidence that W_real ≤_st W_M/G/k, nor that the O(1/(1−ρ)) transfer holds under StrictFIFO or high-rate restart preemption—the regimes the paper itself flags as risky. At minimum, add (i) a head-to-head BestEffortFIFO vs StrictFIFO comparison at matched ρ, (ii) a controlled preemption-feedback sweep, and/or (iii) distributional comparisons (e.g., CDF or quantile plots of wait) against the M/G/k reference, and state clearly what is and is not validated.
  3. [§3.2, Theorem 1] Theorem 1 (Partition Necessity) is essentially immediate from Definition 4 once unfeasible workloads have W=∞: any finite-capped estimator that ignores feasibility incurs error growing with the unfeasible fraction (or diverges). The result is still a useful systems framing, but it should not be presented as a deep theorem on equal footing with the scaling claims. Tighten the statement to a proposition about estimator necessity, and avoid implying that the partition alone yields quantitative wait bounds for quotable work.
  4. [§3.5 Eq. (7), §5.4 Table 2] Approximation 1 / Eq. (7) and Table 2: the practical estimator overestimates by 2.3–18× and is undefined for transient ρ_obs>1, while EMA wins on point MAE. The paper correctly calls Erlang-C an a priori conservative estimate, not a proven upper bound. For a journal contribution centered on wait-time guarantees, either derive a tighter discipline-aware bound, calibrate/correct the Cosmetatos–Tijms factor under BestEffortFIFO and truncated service, or demote Eq. (7) more clearly to a capacity-planning heuristic and lead with what is proved (scaling under Assumption 1) versus what is observed (conservative bias).
minor comments (6)
  1. [§3.3, §5.6] Definition 5 vs Eq. (4): single-class k_eff is clean; the multi-class dominant-resource extension is stated but explicitly “not separately tested” (§5.6). Flag this earlier when Eq. (4) is introduced.
  2. [Table 2] Table 2 † rows: reporting Erlang-C as “—” under overload is fine, but briefly state how operators should treat ρ_eff≥1 (e.g., only the partition + instability signal).
  3. [§5.1, §7] §5.1 uses kind and synthetic Poisson/exponential jobs; note external validity limits relative to production burstiness and AFS (already in §7) in the evaluation discussion itself.
  4. [§4 Theorem 4] Proof of Theorem 4 is labeled “proof sketch”; for NP-hardness via vector bin packing a short full reduction (instance map and correctness) would meet standard theory expectations.
  5. [Abstract] Minor consistency: abstract says validation “using CPU, memory, and GPU (via DRA)” and “Little’s Law holds exactly,” which matches §5, but the opening abstract sentence of the preprint body also mentions “in the moderate utilization regime”—align wording across abstract versions.
  6. [References] References [18] “2026 state of…” and several 2025–2026 arXiv items: verify bibliographic details at camera-ready time.

Circularity Check

1 steps flagged

No material circularity: wait-time claims are conditional on an explicit open assumption, not forced by fit or self-citation; only Theorem 1 is partly definitional.

specific steps
  1. self definitional [§3.2 Theorem 1 / Definition 4]
    "For w∈P_U, W(w)=∞ by Definition 4: no amount of waiting yields admission without reconfiguration. If Ŵ has a finite cap M, then for unfeasible workloads |Ŵ(w)−W(w)|=∞, and the expected error over a random workload is at least α·∞=∞."

    Unfeasible is defined so that wait is infinite; the ‘proof’ that any estimator ignoring the partition has unbounded error then follows immediately from that definition rather than from an independent dynamical argument. The operational PotAvail test is still useful, but the necessity claim is largely tautological once W=∞ is built into the label.

full rationale

The load-bearing wait-time results (Theorems 2–3) do not reduce to their inputs by construction. They transfer classical M/G/k positive recurrence and the Li–Goldberg O(1/(1−ρ)) bound to the real system only under Modeling Assumption 1 (W_real ≤_st W_M/G/k), which the paper states is unproven and restricted to BestEffortFIFO, mild/checkpoint preemption, and near-Poisson arrivals. That is a conditional/open-coupling weakness, not circularity: the target is not fitted from the same data that defines the claim, and no author self-citation carries the argument. k_eff is computed from quotas and demand vectors (Definitions 5, Eqs. 3–4); the modified Erlang-C estimate (Eq. 7) is then compared to independently instrumented Kueue wait times and systematically overestimates—an a-priori check, not a fitted-input-called-prediction. Little’s Law holding is a consistency check on measured L, λ, W, not a free parameter. NP-hardness is a standard reduction from vector bin packing. The only mild definitional step is Theorem 1: once unfeasible is defined so that W=∞ (Definition 4), any estimator that does not separate that class has unbounded error by construction. That is a legitimate necessity remark, not a hidden fit, and does not underwrite Theorems 2–3. No self-citation chain, uniqueness import, or ansatz smuggling appears. Score 1 for the partly tautological partition theorem; central derivation is otherwise self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

2 free parameters · 7 axioms · 2 invented entities

Load-bearing content rests on classical queueing and packing results plus one explicit unproved domination assumption and standard modeling choices (Poisson arrivals, BestEffortFIFO, dominant-resource mix). No numerical constants are fitted to force the main theorems; Erlang-C is used as a known approximation, not recalibrated. Invented entities are definitional partitions and reductions, not new physical objects.

free parameters (2)
  • EMA smoothing α = 0.3
    Baseline comparator uses α=0.3 chosen by hand; not used in the theoretical claims, only in the point-prediction comparison.
  • Dominant-resource class proportions φ_j
    Multi-class k_eff (Eq. 4) weights demands by arrival proportions; treated as known/measurable, not fitted to wait data, but the approximation quality depends on the mix.
axioms (7)
  • ad hoc to paper Modeling Assumption 1: real quotable wait is stochastically dominated by M/G/k with k=k_eff, λ_eff=λ+μ_p, under BestEffortFIFO and mild preemption.
    Stated explicitly in §3.4; formal coupling left open; entire finiteness and scaling transfer depends on it.
  • standard math Li–Goldberg multi-server Kingman-type bound: E[W]=O(1/(1-ρ)) for FCFS M/G/k with finite (2+ε) service moments.
    Invoked for Theorem 3; external published result.
  • standard math M/G/k positive recurrence and finite wait moments when ρ<1 (Kiefer–Wolfowitz / standard multi-server theory).
    Used in Theorem 2 proof.
  • standard math d-dimensional vector bin packing is strongly NP-hard for d≥2 (Chekuri–Khanna).
    Reduction source for Theorem 4.
  • domain assumption Arrivals approximately Poisson; service times i.i.d. with finite (2+ε) moment; preemption either checkpointed or μ_p≪λ.
    Required for M/G/k reference and domination justification; limitations §7 notes burstiness and AFS violations.
  • domain assumption Cosmetatos–Tijms / Erlang-C form is an acceptable practical estimator (no error guarantee).
    Approximation 1; paper correctly reports it is unproven and empirically loose.
  • domain assumption Potential available capacity (nominal + max borrow) correctly classifies eventual admissibility without reconfiguration.
    Definitions 3–4; ignores some dynamic cohort and topology effects noted in limitations.
invented entities (2)
  • Quotable / unfeasible partition of the pending queue independent evidence
    purpose: Separate workloads with finite wait under stability from those with no finite wait without reconfiguration, so wait estimators have bounded error.
    Definitional relative to potential available capacity; useful operational concept mapped partly onto Kueue's inadmissible set, but not an external physical entity.
  • Effective server count k_eff via min-dimension vector packing reduction independent evidence
    purpose: Collapse multi-dimensional quota/demand into a scalar server count for M/G/k analysis.
    Standard packing upper bound rebranded for queueing; validated empirically as bottleneck detector on Kueue.

pith-pipeline@v1.2.0-daily-grok45 · 17807 in / 4211 out tokens · 83084 ms · 2026-07-31T14:09:43.739357+00:00 · methodology

0 comments
read the original 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, multi-resource 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/k system where the effective server count k is determined by a vector packing reduction; under an explicit stochastic domination assumption, we establish O(1/(1-rho)) 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, using CPU, memory, and GPU (via Dynamic Resource Allocation) resources. The vector k_eff correctly identifies bottleneck resource dimensions, Little's Law holds exactly, and the Erlang-C approximation consistently overestimates observed wait times in the conservative direction.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 2 linked inside Pith

  1. [1]

    Mitzenmacher and N

    M. Mitzenmacher and N. Shahout. Queueing, predictions, and LLMs. Stochastic Systems, 2025. arXiv:2503.07545

    Pith/arXiv arXiv 2025

  2. [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

    Pith/arXiv arXiv 2025

  3. [3]

    Wang and I

    Z. Wang and I. Grosof. Novel lower bounds on M/G/k scheduling. arXiv:2502.08804, 2025

    arXiv 2025

  4. [4]

    Kueue: Kubernetes-native job queueing.https:// kueue.sigs.k8s.io/, 2024

    Kubernetes-sigs. Kueue: Kubernetes-native job queueing.https:// kueue.sigs.k8s.io/, 2024

    2024

  5. [5]

    A. B. Yoo, M. A. Jette, and M. Grondona. SLURM: Simple Linux utility for resource management. InJSSPP, 2003

    2003

  6. [6]

    Chekuri and S

    C. Chekuri and S. Khanna. On multidimensional packing problems. SIAM J. Comput., 33(4):837–851, 2004

    2004

  7. [7]

    Kiefer and J

    J. Kiefer and J. Wolfowitz. On the theory of queues with many servers. Trans. Amer. Math. Soc., 78:1–18, 1955

    1955

  8. [8]

    Gupta and T

    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

    2011

  9. [9]

    Gupta, M

    V. Gupta, M. Harchol-Balter, J. G. Dai, and B. Zwart. On the inapprox- imability of M/G/K: Why two moments of job size distribution are not enough.Queueing Systems, 64(1):5–48, 2010

    2010

  10. [10]

    Li and D

    Y. Li and D. A. Goldberg. Simple and explicit bounds for multiserver queues with1/(1−𝜌)scaling.Math. Oper. Res., 50(2):813–837, 2024

    2024

  11. [11]

    H. C. Tijms.A First Course in Stochastic Models. Wiley, 2003

    2003

  12. [12]

    J. Gu, M. Chowdhury, K. G. Shin, et al. Tiresias: A GPU cluster manager for distributed deep learning. InNSDI, 2019

    2019

  13. [13]

    H. Zhao, Z. Han, Z. Yang, et al. HiveD: Sharing a GPU cluster for deep learning with guarantees. InOSDI, 2020

    2020

  14. [14]

    Zheng, et al

    P. Zheng, et al. Shockwave: Fair and efficient cluster scheduling for dynamic adaptation in machine learning. InNSDI, 2023

    2023

  15. [15]

    Villarrubia, L

    J. Villarrubia, L. Costero, F. D. Igual, and K. Olcoz. Leveraging multi- instance GPUs through moldable task scheduling.J. Parallel Dis- trib. Comput., 204, 2025

    2025

  16. [16]

    Zhang, A

    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. InATC, 2025

    2025

  17. [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. InEuroSys, 2026

    2026

  18. [18]

    2026 state of Kubernetes optimization report

    Cast AI. 2026 state of Kubernetes optimization report. Technical report, 2026

    2026

  19. [19]

    Kubernetes Enhancement Proposal, 2023

    KEP-168: Workload visibility. Kubernetes Enhancement Proposal, 2023

    2023

  20. [20]

    com/kubernetes-sigs/kueue/issues/13159, 2026

    Kueue Issue #13159: Workload wait time estimation.https://github. com/kubernetes-sigs/kueue/issues/13159, 2026

    2026

  21. [21]

    Kueue Issue #10124: Users need wait time.https://github.com/ kubernetes-sigs/kueue/issues/10124, 2025

    2025

  22. [22]

    Kueue Issue #10614: Admission estimation for MultiKueue.https: //github.com/kubernetes-sigs/kueue/issues/10614, 2025

    2025

  23. [23]

    kind: Kubernetes in Docker.https://kind.sigs.k8s.io/, 2024

    Kubernetes-sigs. kind: Kubernetes in Docker.https://kind.sigs.k8s.io/, 2024

    2024

  24. [24]

    Ghodsi, M

    A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple re- source types. InNSDI, 2011

    2011

  25. [25]

    W. Xiao, R. Bhardwaj, R. Ramjee, M. Sivathanu, et al. Gandiva: Intro- spective cluster scheduling for deep learning. InOSDI, 2018

    2018

  26. [26]

    Narayanan, K

    D. Narayanan, K. Santhanam, F. Kazhamiaka, A. Phanishayee, and M. Zaharia. Heterogeneity-aware cluster scheduling policies for deep learning workloads. InOSDI, 2020

    2020

  27. [27]

    Mahajan, A

    K. Mahajan, A. Balasubramanian, A. Singhvi, S. Venkataraman, et al. Themis: Fair and efficient GPU cluster scheduling. InNSDI, 2020

    2020

  28. [28]

    A. Qiao, S. K. Choe, S. J. Subramanya, W. Neiswanger, et al. Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning. InOSDI, 2021

    2021