Architecture & Design Analysis

Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning

Source: Qiao, A.; Choe, S. K.; Subramanya, S. J.; Neiswanger, W.; Ho, Q.; Zhang, H.; Ganger, G. R.; Xing, E. P. 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI '21), July 14-16, 2021. ISBN 978-1-939133-22-9. Affiliations: 1 = Petuum, Inc.; 2 = Carnegie Mellon University; 3 = UC Berkeley; 4 = MBZUAI. Qiao (1,2), Choe (2), Subramanya (2), Neiswanger (1,2), Ho (1), Zhang (1,3), Ganger (2), Xing (4,1,2). Code: https://github.com/petuum/adaptdl — artifact branch osdi21-artifact; raw testbed logs at https://github.com/petuum/pollux-results Reader: Direct PDF text extraction (pdftotext -layout and -raw), cross-checked page-by-page. Analyst: Vishwakarma Date: 2026-09-01

Conventions. Fig N with a ^ caption is a diagram drawn in this document; Figure N / paper Fig. N refers to the Pollux paper. Paper Figures 1, 2, 3, 5, 6, 7, 8 and 9 are plots whose numeric axis values are not recoverable from the text layer — this document reports only what the caption or body text states. No axis value has been invented and no bar label fitted against a table. Anything that is my own inference rather than a paper claim is marked [derived inference].

Table of Contents

1. System Architecture (PolluxAgent + PolluxSched)
2. System-Under-Test Architecture (testbed, workload, simulator)
3. Design-Space Diagram (axes swept, axes held fixed)
4. Algorithm & Control-Flow Diagrams (key procedures)
5. Quantitative Results — Empirical Findings by Regime
6. Configuration-Regime Trade-off Tables
7. Bottlenecks & Insights Surfaced by the Measurements
8. Limitations of the Methodology
9. Note on NCCL Tuning
10. Analogy

1. System Architecture (PolluxAgent + PolluxSched)

1.1 The central abstraction: goodput

Everything in Pollux is downstream of one scalar per job.

Def. 3.1 (Goodput). "The goodput of a DL training job at iteration t is the product between its system throughput and its statistical efficiency at iteration t,"

GOODPUT_t(*) = THROUGHPUT(*) x EFFICIENCY_t(M(*)) (Eqn. 4)

where * "represents any configuration parameters that jointly influence the throughput and batch size during training, and M is the total batch size summed across all allocated GPUs." Footnote 2 grounds the name: "Our notion of goodput for DL is analogous to the traditional definition of goodput in computer networks, ie. the useful portion of throughput as benchmarked by training progress per unit of wall-clock time." Pollux instantiates * = (a, m, s):

with M(a, m, s) = SUM(a) x m x (s + 1).

+-------------------------------------------------------------------+
|                     GOODPUT_t(a, m, s)                            |
|   +--------------------------+     +--------------------------+   |
|   |  THROUGHPUT(a, m, s)     |  x  |  EFFICIENCY_t(M(a,m,s))  |   |
|   |  (system-side factor)    |     |  (statistics-side factor)|   |
|   |  = M(a,m,s) / T_iter     |     |  = (phi_t + M0)          |   |
|   |            (Eqn. 7)      |     |    / (phi_t + M)  (Eq. 6)|   |
|   |  fitted from theta_sys   |     |  driven by PGNS phi_t    |   |
|   |  (7 params, Eqn. 12)     |     |                          |   |
|   +--------------------------+     +--------------------------+   |
|      grows with GPUs and batch size    falls with batch size      |
+-------------------------------------------------------------------+
^ Fig 1: The goodput product. The two factors pull in opposite
  directions along the batch-size axis, which is why a scalar
  maximum exists and why it moves as phi_t drifts during training.

The paper bounds it: "Pollux only considers batch sizes that are at least the initial batch size, ie. M >= M0... Therefore, goodput can be interpreted as the portion of the throughput that is useful for training progress, being equal to the throughput if and only if perfect statistical efficiency is achieved."

1.2 The efficiency model — pre-conditioned gradient noise scale

Pollux generalizes the gradient noise scale so it covers adaptive optimizers, defining the pre-conditioned gradient noise scale (PGNS):

                    tr( P Sigma P^T )
        phi_t  =   -------------------                          (Eqn. 5)
                        | P g |^2

  g      = the true gradient
  P      = the pre-conditioning matrix of the adaptive SGD algorithm
  Sigma  = the covariance matrix of per-example stochastic gradients

It is "derived by closely following the original derivation of the GNS ('simple' noise scale in [46]) starting from pre-conditioned SGD rather than vanilla SGD," and "is mathematically equivalent to the GNS for the special case of vanilla SGD." Because "it takes 1 + phi_t/M training iterations to make a similar amount of training progress across different batch sizes M":

                              phi_t + M0
        EFFICIENCY_t(M)  =  --------------                      (Eqn. 6)
                              phi_t + M

Stated properties: "If EFFICIENCY_t(M) = E, then (1) 0 < E <= 1, and (2) training using batch size M will need to process 1/E times as many training examples to make the same progress as using batch size M0."

Estimation of phi_t follows "Appendix A.1 of [46], except using the pre-conditioned gradient Pg... efficiently when there are multiple data-parallel processes by using the different values of g_k already available on each GPU k." The single-GPU, no-accumulation case (s = 0) breaks that estimator, so "Pollux switches to a differenced variance estimator [63]." Learning-rate rescaling is delegated to a plug-in, SCALE_LR(M0, M) -> lambda, "called before every model update step," implementable as "AdaScale, square-root scaling [40], linear scaling [21] and LEGW [69]."

1.3 The throughput model — a placement-aware parametric fit

  THROUGHPUT(a, m, s) = M(a, m, s) / T_iter(a, m, s)            (Eqn. 7)

  T_grad(m) = alpha_grad + beta_grad * m                        (Eqn. 8)

                 |  0                                    if K = 1
  T_sync(a,m) = <   alpha_sync^local + beta_sync^local * (K-2)  if N=1, K>=2
                 |  alpha_sync^node  + beta_sync^node  * (K-2)  otherwise
                                                                 (Eqn. 9)

  T_iter(a,m,0) = ( T_grad^gamma + T_sync^gamma )^(1/gamma)     (Eqn. 10)

  T_iter(a,m,s) = s * T_grad
                  + ( T_grad^gamma + T_sync^gamma )^(1/gamma)   (Eqn. 11)

  K = SUM(a) = number of allocated GPUs
  N = number of physical nodes occupied by at least one replica

  theta_sys = ( alpha_grad, beta_grad, alpha_sync^local,
                beta_sync^local, alpha_sync^node,
                beta_sync^node, gamma )                         (Eqn. 12)

gamma is the compute/communication overlap dial: "Eqn. 10 has the property that T_iter = T_grad + T_sync when gamma = 1, and smoothly transitions towards T_iter = max(T_grad, T_sync) as gamma -> inf" — a stand-in for partial overlap whose "degree... depends on structures in the specific DL model being trained, like the ordering and sizes of its layers." The (K - 2) slope exists "to account for performance retrogressions associated with using three or more GPUs, such as increasing likelihood of stragglers or network delays." The local/node branch is the topology hook, and "can be extended to account for rack-level locality by adding a third pair of parameters." Together, (theta_sys, phi_t, M0) "fully specify the DL job's GOODPUT function at its current training progress."

1.4 The two-component architecture

+===================================================================+
|  PolluxSched   (one per cluster; Kubernetes service)              |
|  +-------------------+   +----------------------------------+     |
|  | Goodput registry  |-->| Population-based search over     |     |
|  | (theta_sys,phi_t, |   | allocation matrices A maximizing |     |
|  |  M0) per job j    |   | FITNESS_p(A)                     |     |
|  +-------------------+   +----------------------------------+     |
|   constraints inside the search: node capacity; interference      |
|   avoidance (<= 1 distributed job per node); REALLOC_FACTOR_j     |
+---------|-------------------------------------------|-------------+
          ^ every 30s: (theta_sys, phi_t)              | every 60s:
          | reported upward                            v apply A via
+---------|-------------------------------------------|-------------+
|  PolluxAgent  (one per job; Python library imported  | Kubernetes  |
|  into the training code)                             | Pod churn   |
|  +-----------------+  +------------------+  +-----------------+    |
|  | Profiler        |  | Model fitter     |  | Tuner           |    |
|  | - T_iter per it |->| - L-BFGS-B on    |->| (m*,s*) =       |    |
|  | - tuples        |  |   RMSLE vs Eq.11 |  |  argmax GOODPUT |    |
|  |   (a,m,s,T_iter)|  | - alpha,beta >=0 |  |  (Eqn. 13)      |    |
|  | - noise phi_t   |  | - gamma in [1,10]|  +--------+--------+    |
|  +-----------------+  | - prior-driven   |           v             |
|                       |   exploration    |  +------------------+   |
|                       +------------------+  | SCALE_LR(M0,M)   |   |
|                                             | -> lambda plug-in|   |
|                                             +------------------+   |
+===================================================================+
     runtime below:  PyTorch + NCCL 2.7.8 all-reduce;
                     Kubernetes 1.18.2 + CephFS 14.2.8 checkpoints
^ Fig 2: Pollux's two-granularity control loop. The narrow waist
  between components is the triple (theta_sys, phi_t, M0) going up
  and the allocation matrix A coming down; neither side sees the
  other's internals.

Paper Figure 4 ("Co-adaptive scheduling architecture of Pollux") is schematic with no numeric labels. The contract: "While PolluxAgent adapts each training job to make efficient use of its allocated resources, PolluxSched dynamically re-allocates each job's resources, taking into account the PolluxAgent's ability to tune its job."

1.5 The cluster-wide objective

                             ( 1   J                     )^(1/p)
   FITNESS_p(A)  =           ( - SUM  SPEEDUP_j(A_j)^p   )       (Eqn. 14)
                             ( J  j=1                    )

                          max_{m,s} GOODPUT_j(A_j, m, s)
   SPEEDUP_j(A_j)  =    ----------------------------------       (Eqn. 15)
                          max_{m,s} GOODPUT_j(a_f, m, s)

A is "an allocation matrix with each row A_j being the allocation vector for a job j... and J is the total number of running and pending jobs sharing the cluster." The denominator baseline a_f is "a fair resource allocation for the job, defined to be an exclusive 1/J share of the cluster." Footnote 5 draws the boundary against Themis: "SPEEDUP is related to training performance at a moment in time, whereas finish-time fairness is related to end-to-end job completion time."

On the exponent: "When p = 1, FITNESS_p is the average of SPEEDUP values across all jobs. This causes PolluxSched to allocate more GPUs to jobs that achieve a high SPEEDUP when provided with many GPUs... However, as p -> -inf, FITNESS_p smoothly approaches the minimum of SPEEDUP values, in which case maximizing FITNESS_p promotes equal SPEEDUP between training jobs, but ignores the overall cluster goodput and resource efficiency. Thus, p can be considered a 'fairness knob', with larger negative values being more fair." Chosen operating point: "p = -1 achieves most goodput improvements and reasonable fairness."

1.6 Re-allocation penalty, interference avoidance, non-adaptive jobs

Re-allocation penalty. "Using the popular checkpoint-restart method, we measured between 15 and 120 seconds of delay depending on the size of the model being trained and other initialization tasks in the training code."

   SPEEDUP_j(A_j)  <--  SPEEDUP_j(A_j) x REALLOC_FACTOR_j(delta)

                              T_j - R_j * delta
   REALLOC_FACTOR_j(delta) = -------------------
                              T_j + delta

     T_j = age of the job;  R_j = re-allocations so far;
     delta = estimate of the re-allocation delay

"Intuitively, REALLOC_FACTOR_j(delta) scales SPEEDUP_j(A_j) according to the assumption that the historical average rate of re-allocations for job j will continue indefinitely into the future" — so a job with a higher historical re-allocation rate is penalized more.

Interference avoidance. "Xiao et al. [66] report up to 50% slowdown for DL jobs which compete with each other for network resources. PolluxSched mitigates this issue by disallowing different distributed jobs (each using GPUs across multiple nodes) from sharing the same node" — "implemented as a constraint in Pollux's search algorithm."

Non-adaptive jobs. For a job with fixed batch size (M = M0), PolluxSched "simply fixes EFFICIENCY_t for that job to 1 and can continue to adapt its resource allocations based solely on its system throughput."

2. System-Under-Test Architecture

2.1 Testbed

"We conduct experiments using a cluster consisting of 16 nodes and 64 GPUs. Each node is an AWS EC2 g4dn.12xlarge instance with 4 NVIDIA T4 GPUs, 48 vCPUs, 192GB memory, and a 900GB SSD. All instances are launched within the same placement group."

+--------- Testbed: 16 x g4dn.12xlarge = 64 NVIDIA T4 GPUs ---------+
|   Node 0            Node 1          ...           Node 15         |
| +-------------+  +-------------+              +-------------+     |
| | 48 vCPUs    |  | 48 vCPUs    |              | 48 vCPUs    |     |
| | 192 GB RAM  |  | 192 GB RAM  |              | 192 GB RAM  |     |
| | 900 GB SSD  |  | 900 GB SSD  |              | 900 GB SSD  |     |
| | 4x T4 GPU   |  | 4x T4 GPU   |              | 4x T4 GPU   |     |
| +------+------+  +------+------+              +------+------+     |
|        +================+============================+            |
|          AWS EC2 network, single placement group                  |
|          (link bandwidth NOT STATED in the paper)                 |
|  Kubernetes 1.18.2 control plane; CephFS 14.2.8 for checkpoints   |
|  Separate testbed used ONLY for HPO (§5.4.2):                     |
|    2 x NVIDIA DGX A100 nodes, 8 A100 GPUs each                    |
+-------------------------------------------------------------------+
^ Fig 3: System under test. The 4-GPU node boundary is the single
  most important structural fact: it is the discontinuity Eqn. 9's
  local/node parameter split exists to represent, and the cause of
  the "sharp increase beyond 4 GPUs" noted in paper Fig. 3.

2.2 Workload (paper Table 1, verbatim)

Caption: "Models and datasets used in our evaluation workload. Each training task achieves the provided validation metrics. The fraction of jobs from each category are chosen according to the public Microsoft cluster traces."

2.3 Trace construction and the "TunedJobs" baseline

"We randomly sampled 160 jobs from the busiest 8-hour range (hours 3-10) in the deep learning cluster traces published by Microsoft [31]. Each job in the original trace has information on its submission time, number of GPUs, and duration. However, no information is provided on the model architectures being trained or dataset characteristics." Substitution is by GPU-time bucket: "Small (0-1 GPU-hours), Medium (1-10 GPU-hours), Large (10-100 GPU-hours), and XLarge (100-1000 GPU-hours). For each job in the trace, we picked a training job from Table 1 that is in the same category."

The tuned-baseline construction is the methodological centrepiece, because it deliberately biases against Pollux: "We considered a number of GPUs valid if using the optimal batch size for that number of GPUs achieves 50% - 80% of the ideal (i.e., perfectly linear) scalability versus using the optimal batch size on a single GPU. For each job submitted from our synthetic workload, we selected its number of GPUs and batch size randomly from its set of valid configurations." The authors' own framing: "this assumption of uniformly sophisticated users is unrealistically biased in favor of the baseline schedulers and only serves for comparing Pollux with the ideal performance of baseline systems."

The second, realistic arm removes that bias: GPU count "exactly as specified in the Microsoft cluster trace. The batch size was chosen to be the baseline batch size M0 times the number of GPUs, which is how we expect most users to initially configure their distributed training jobs. We find that these jobs typically use fewer GPUs and smaller batch sizes than their well-configured counterparts."

2.4 Baseline configuration

LR handling is equalized across all three: "for all three schedulers, we scale the learning rate using AdaScale for SGD, and the square-root scaling rule for Adam and AdamW." Authority differs: "Optimus+Oracle uses the batch size specified, but determines the number of GPUs dynamically. Each job uses gradient accumulation if they are allocated too few GPUs to support the specified batch size."

2.5 The simulator

Fidelity claim: "our simulator obtains similar factors of improvement, showing that Pollux reduces the average JCT by 48% and 32% over Optimus+Oracle+TunedJobs and Tiresias+TunedJobs."

3. Design-Space Diagram (axes swept, axes held fixed)

+===================== POLLUX DESIGN SPACE =========================+
|  SWEPT — evaluated experimentally                                 |
|  ---------------------------------------------------------------  |
|  A1. SCHEDULER POLICY (7 testbed configurations, Table 2):        |
|      Pollux p in {-1,+1,-10}; Optimus+Oracle+TunedJobs;           |
|      Tiresias+TunedJobs; Optimus+Oracle; Tiresias                 |
|  A2. USER-KNOWLEDGE REGIME (2): TunedJobs (50-80% of ideal        |
|      linear scalability) vs Realistic (trace GPUs, M0 x nGPU)     |
|  A3. FAIRNESS KNOB p (3):  [+1]  [-1]  [-10]                      |
|  A4. WORKLOAD INTENSITY (paper Fig. 8a; levels NOT NUMERICALLY    |
|      STATED — "increasing... rate of job submissions")            |
|  A5. SCHEDULING INTERVAL (Fig. 8b; only the qualitative           |
|      breakpoint "up to 2 minutes" is stated)                      |
|  A6. INJECTED INTERFERENCE SLOWDOWN (Fig. 8c; text names 0%, 50%) |
|  A7. INTERFERENCE AVOIDANCE  [on] [off]                           |
|  A8. PRIOR-DRIVEN EXPLORATION  [from scratch] [offline-seeded]    |
|  A9. MODEL / TASK (6 levels, Table 1)                             |
|  A10. AUTO-SCALER POLICY (2): Pollux goodput-driven vs            |
|       Or et al. throughput-driven                                 |
|                                                                   |
|  HELD FIXED — not swept anywhere in the evaluation                |
|  ---------------------------------------------------------------  |
|   - Accelerator type (T4 only; A100 only for the HPO run).        |
|     Footnote 1: "Pollux's current throughput model does not       |
|     consider accelerator heterogeneity."                          |
|   - Parallelization strategy: synchronous data parallelism only.  |
|   - Gradient synchronization library: NCCL 2.7.8, at its own      |
|     internal defaults. No algorithm / protocol / channel sweep.   |
|   - Cluster size: 16 nodes / 64 GPUs throughout.                  |
|   - Elasticity mechanism: checkpoint-restart only.                |
|   - LR scaling rule: fixed per optimizer (AdaScale for SGD,       |
|     square-root for Adam/AdamW).                                  |
|   - delta in REALLOC_FACTOR: 30s;  reporting interval: 30s.       |
|   - Compression / quantization: absent entirely.                  |
+===================================================================+
^ Fig 4: Ten swept axes, eight fixed. The fixed list is where the
  scope boundary lives: everything below the "data-parallel job with
  a batch size" abstraction is a constant in this paper.

The most consequential fixed axis is the gradient-synchronization layer, named exactly once: "Gradients are synchronized with NCCL 2.7.8, which uses either ring all-reduce or tree all-reduce depending on the detected GPUs and their placements and its own internal performance estimates." That is the paper's entire treatment of collective-algorithm selection — the decision is part of the environment being measured, absorbed into Eqn. 9's constants.

4. Algorithm & Control-Flow Diagrams

4.1 PolluxAgent's inner loop

  JOB START  (a = 1 GPU, m = M = M0, s = 0, eta = eta0)
       |
       v
  (1) [training iteration] measure T_iter; record (a,m,s,T_iter);
       |  accumulate gradient statistics for phi_t; before every
       |  model update apply lambda <- SCALE_LR(M0, M)
       v
  (2) 30s elapsed since last fit? --no--> back to (1)  --yes-->
       v
  (3) FIT theta_sys: minimize RMSLE between Eqn. 11 and all
        collected tuples via L-BFGS-B; alpha,beta >= 0;
        gamma in [1,10]; unexplored sync params pinned to 0 (4.2)
        [measured cost: avg 0.2 s]
       v
  (4) REPORT (theta_sys, phi_t) --> PolluxSched
       v
  (5) RETUNE for the *current* allocation a:
        (m*, s*) = argmax_{m,s} GOODPUT(a, m, s)        (Eqn. 13)
        procedure: sample candidate total batch sizes M; for each,
        find the smallest s such that m = ceil(M/s) fits GPU memory
        per the user-defined bound; take the highest-GOODPUT config
        [measured cost: avg 0.4 ms]
       v
  (6) adopt (m*, s*), rescale eta ------------------> back to (1)
^ Fig 5: PolluxAgent control flow. Step (5) runs against whatever
  allocation the scheduler last handed down; the agent never proposes
  one of its own. The model fit is ~500x more expensive than the
  configuration search (0.2 s vs 0.4 ms), so it sets the loop period.

4.2 Prior-driven exploration

"we impose several priors which bias theta_sys towards the belief that throughput scales perfectly with more resources, until such resource configurations are explored." Verbatim, as printed:

"In particular, we set alpha_sync^local = 0 while the job had not used more than one GPU, alpha_sync^local = beta_sync^local = 0 while the job had not used more than one node, and beta_sync^local = beta_sync^node = 0 while the job had not used more than two GPUs."

[derived inference] The clauses as printed overlap on alpha_sync^local / beta_sync^local and never pin alpha_sync^node; the structurally natural reading is one pin per not-yet-visited regime — my reading, not a paper claim.

  Regimes a job has NOT yet visited  -->  parameters pinned to 0
  +--------------------------------------------------------------+
  | never used > 1 GPU   -->  intra-node sync cost assumed 0      |
  | never used > 1 node  -->  inter-node sync cost assumed 0      |
  | never used > 2 GPUs  -->  retrogression slope assumed 0       |
  +--------------------------------------------------------------+
        |  "each job starts with a single GPU and is initially
        |   assumed to scale perfectly to more GPUs. PolluxSched
        |   is then encouraged to allocate more GPUs and/or nodes"
        v
  GUARD: "we restrict the maximum number of GPUs that can be
  allocated to at most twice the maximum number of GPUs the job has
  been allocated in its lifetime."
^ Fig 6: Optimism-under-uncertainty implemented as a parameter
  prior, with a doubling cap as rate limiter. Explicitly not a
  principled explorer: "Although other principled approaches to
  exploration can be applied (e.g., Bayesian optimization), we find
  that this simple prior-driven strategy is sufficient."

4.3 PolluxSched's outer loop

  every 60 s:
       v
  (1) collect latest (theta_sys, phi_t, M0) for all J jobs
      (running AND pending)
       v
  (2) POPULATION-BASED SEARCH over allocation matrices A, which
       |   "perturbs and combines candidate allocation matrices to
       |    produce higher-value allocation matrices, and finally
       |    modifies them to satisfy node resource constraints and
       |    interference avoidance"
       |   per candidate A, per job j:
       |     SPEEDUP_j(A_j) = maxGOODPUT_j(A_j)/maxGOODPUT_j(a_f)
       |     if job j must move: *= REALLOC_FACTOR_j(delta = 30s)
       |   FITNESS_p(A) = power-mean_p over SPEEDUP_j
       |   [measured cost: avg 1 second on 1 vCPU]
       v
  (3) "The allocation matrix with the highest fitness score is
       applied to the jobs running in the cluster."
       v
  (4) APPLY: create/terminate Kubernetes Pods; workers resume from
      CephFS checkpoints
       v
  (5) each affected PolluxAgent re-runs Eqn. 13 against its new a
      -- and its next report at (1) already reflects that ability
^ Fig 7: PolluxSched control flow. The re-allocation penalty is
  evaluated *inside* the fitness function, so churn control is part of
  the objective, not a post-hoc filter. Step (5) closing into step (1)
  is the co-adaptation loop: the scheduler optimizes over jobs that
  will re-tune themselves in response.

4.4 The auto-scaling policy (§5.4.1)

  scale UP the number of nodes whenever:

     max_{m,s} GOODPUT_t(a, m, s)
     ---------------------------- >  U * max_{m,s} GOODPUT_t(1, m, s)
              SUM(a)

  i.e. "the goodput exceeds some fraction U of the predicted ideal
  goodput assuming perfect scalability".   U = 2/3 trigger; L = 1/2
  target ("increased to a number of nodes such that the predicted
  goodput is approximately L = 1/2 of the predicted ideal goodput")

The paper labels this preliminary: "a full design of an auto-scaling system based on goodput may be the subject of future work."

5. Quantitative Results — Empirical Findings by Regime

5.1 Testbed macrobenchmark (paper Table 2, verbatim)

Caption: "Summary of testbed experiments."

5.2 Percentage improvements as stated in the text

The abstract's headline — "reduces average job completion times by 37-50% relative to state-of-the-art DL schedulers, even when they are provided with ideal resource and training configurations for every job" — is the first two rows; the introduction's "up to 73%" is the fourth. Why the realistic arm hurts Optimus specifically: "Even though Optimus+Oracle can dynamically increase the GPU allocation of each job, it still only slightly outperforms Tiresias because it does not also increase the batch size to better utilize those additional GPUs."

5.3 Model-fit accuracy and batch-size headroom

The transfer claim that makes prediction possible without probing: "phi_t measured using batch size M can be used by Pollux to predict the value of EFFICIENCY_t at a different batch size M' without needing to train using M' ahead of time."

Headroom: the GNS "is non-constant and tends to gradually increase during training, by up to 10x or more [46]"; "a job in a later stage of training can potentially tolerate 10x or larger batch sizes without degrading statistical efficiency [46]"; "a batch size up to 32x larger works well in most cases."

5.4 System overheads (§5.2, verbatim)

5.5 Scheduling fairness (§5.3.1)

Finish-time fairness rho is "the ratio of a job's JCT running on shared resources to that of the job running in an isolated and equally-partitioned cluster"; rho < 1 is better-than-fair. Paper Fig. 7 is a CDF with no recoverable axis values.

The abstract's "1.5x-5.4x" is located by the text: "The max-rho improvements (1.5x and 5.4x) over Tiresias and Optimus are also similar" — framed as consistent with the ranges reported for Themis, since "their Themis system is not available for direct comparison."

5.6 Sensitivity analyses (§5.3.2)

Paper Fig. 8's three panels have "error bars and bands represent 95% confidence intervals." Sweep levels for panels (a) and (b) are not stated numerically in the text; only the findings below are.

(a) Job load. "As expected, all three scheduling policies suffer longer average JCT and makespan as the load is increased. Across all job loads, Pollux maintains similar relative improvements over the baselines."

(b) Scheduling interval. "Pollux performs similarly well in terms of average JCT for intervals up to 2 minutes, while longer intervals result in performance degradation... queuing contributed to roughly half of the performance degradation observed."

(c) Interference.

Prior-driven exploration ablation. "We observed minor (2-5%) reduction in JCT for short jobs like CIFAR10, but no significant change for longer running jobs." §4.1 restates the bound: it "performs close (within 2-5%) to an idealized scenario in which the model is fitted offline for each job before being submitted to the cluster."

5.7 Cloud auto-scaling (§5.4.1)

"Overall, compared to Or et al.'s throughput-based auto-scaling, Pollux trains ImageNet with 25% cheaper cost, with only a 6% longer completion time." Paper Fig. 9's panels carry no numeric labels; the only qualitative claim is "Pollux maintains a high statistical efficiency throughout training."

5.8 Hyper-parameter optimization (paper Table 3, verbatim)

Setup: ResNet18 on CIFAR10 under the Tree-structured Parzen Estimator (TPE) [5]; "the search space covers the learning rate and annealing, momentum, weight decay, and network width hyper-parameters... 4 trials run concurrently with each other, and 100 trials are run in total. The testbed consists of two NVIDIA DGX A100 nodes, each with 8 A100 GPUs. The baseline scheduler assigns a static allocation of 4 GPUs (all on the same node) to each trial and uses a fixed per-GPU batch size for every trial." Conclusion: "similar accuracy values are achieved, but Pollux completes HPO 30% faster."

5.9 The co-adaptation trace (paper Figs. 5 and 6)

Paper Fig. 6 is a four-row time series for one ImageNet job (LEFT) and two YOLOv3 jobs (RIGHT): "ROW 1: number of jobs actively sharing the cluster. ROW 2: number of GPUs allocated to the job. ROW 3: batch size (images) used. ROW 4: statistical efficiency (%)." No axis values are recoverable. The narrated behaviour, in the paper's words:

  (A) low contention   more GPUs --> larger batch --> LOWER efficiency
                       (accepted: higher goodput overall)
        |
  (B) high contention  fewer GPUs --> smaller batch --> HIGHER efficiency
        |
  (C) contention drops more GPUs, larger batch, BUT "the batch size per
                       GPU is much higher than in the first low-contention
                       period, since the job is now in its final,
                       high-statistical-efficiency phase of training"
^ Fig 8: The three-phase narrative of paper Fig. 6 (LEFT). Phase (C)
  is the load-bearing observation: the same cluster state produces a
  different optimum than it did earlier, because phi_t has drifted.
  A time-invariant policy cannot produce this trace.

Paper Fig. 5 shows "TOP: average cluster-wide allocated GPUs over time. BOTTOM: average cluster-wide statistical efficiency over time," with the same (A)/(B) annotations, plus one baseline artifact: "Tiresias+TunedJobs dips between hours 16 and 20 due to a 24-GPU job blocking a 48-GPU job."

6. Configuration-Regime Trade-off Tables

6.1 Fairness knob p (testbed, Table 2 + §5.3.1)

The paper's reconciliation: "introducing a moderate degree of fairness (p = -1) improved the average job completion time (JCT) but degraded the tail JCT. This is because, in our synthetic workload, the tail JCT comprises of long but scalable jobs (i.e. ImageNet), which take a large number of GPUs away from other jobs in the absence of fairness (p = 1). However, further increasing fairness (p = -10) degraded performance in average JCT, tail JCT, and makespan." Footnote 6 adds: "p = -1 (harmonic mean over speedups) may be more suitable than p = 1 (arithmetic mean) when optimizing for the average JCT."

Regime rule: p = -1 is a genuine interior optimum for average JCT and makespan; only the tail favours p = +1.

6.2 Adaptation authority granted to the scheduler

[derived inference] The swing between Tiresias's tuned (1.2h) and realistic (2.8h) columns — 2.3x, from user configuration quality alone — is larger than the gap between Tiresias-tuned and Pollux (1.6x). The dominant term here is whether the configuration is good, not which scheduler assigns it; Pollux's contribution is removing the user from that path.

6.3 Throughput-only vs goodput-driven adaptation

Regime rule: goodput and throughput agree whenever EFFICIENCY_t is flat and diverge exactly where phi_t drifts — which is why the auto-scaling result, a single long job observed over its full lifetime, shows the largest qualitative behavioural difference in the paper.

6.4 Elasticity mechanism cost and scheduling interval

Regime rule: the 8% overhead is the standing tax for elasticity, and the 37-50% improvements are net of it. The interval sits an order of magnitude above the re-allocation delay and three orders above the scheduler's own compute cost — the binding constraint is the restart, not the search.

7. Bottlenecks & Insights Surfaced by the Measurements

7.1 The system rests on one product of two curves. SPEEDUP is a ratio of goodputs; FITNESS_p a power mean of speedups; the auto-scaler a threshold on goodput per GPU; the agent's retune an argmax of goodput. So either factor can be replaced without touching the rest — "we designed GOODPUT_t (Eqn. 4) to be modular so that different equations for THROUGHPUT may be easily plugged in."

7.2 T_sync encodes exactly one topology boundary. On a 16-node / 4-GPU-per-node testbed, Eqn. 9's three branches capture the dominant discontinuity — paper Fig. 3's caption confirms placement "in as few 4-GPU nodes as possible... causes a sharp increase beyond 4 GPUs." Who cares: "all models we measured except ImageNet exhibited high sensitivity to inter-node synchronization."

7.3 Gradient accumulation is the decoupling operator. Without it, total batch size is pinned to SUM(a) x m and m is capped by GPU memory: "many DL models hit this limit before the batch size is large enough for T_grad to overcome T_sync (or experience diminishing statistical efficiency), resulting in suboptimal scalability."

With s = 0 the total batch size is f(GPU count), so returning GPUs forces a smaller batch and leaves the Amdahl floor: "no matter how many GPUs are used, the run-time of each training iteration is lower bounded by T_sync." With s >= 1 it becomes f(GPU count, s), so PolluxSched can shrink an allocation without disturbing the batch size or LR schedule — at a cost of s extra T_grad terms per iteration (Eqn. 11). Empirically: "YOLOv3 and BERT benefit from using gradient accumulation to increase their total batch sizes."

7.4 Interference is eliminated by constraint, not by modelling. PolluxSched does not predict interference slowdown; it forbids the configuration that causes it. §5.3.2 justifies this: at 50% injected slowdown, avg JCT is unaffected with the constraint on and 1.4x longer with it off, and at 0% slowdown it costs nothing measurable. Free in the good case and worth 1.4x in the bad case dominates a model needing calibration in both.

7.5 The scheduler's compute is not the bottleneck; the restart is. One second of vCPU per 60-second interval is a 1.7% duty cycle on one core, while the 8% run-time overhead comes entirely from checkpoint-restarts. Pollux is bounded by its mechanism, not its policy: a better elasticity mechanism (in-place resize, migration) converts directly into headroom, while a faster search buys nothing.

7.6 Optimism-under-uncertainty is a parameter prior, not an explorer. Pollux zeroes the not-yet-identifiable synchronization parameters so the fit claims perfect scaling, lets PolluxSched act on the claim, and lets the resulting measurements correct it, with a doubling cap as rate limiter. The 2-5% gap to an offline-fitted oracle — short jobs only — is the measured price of that simplicity.

7.7 The p = -1 sweet spot is a real interior optimum with two distinct failure modes on either side. Both neighbours are worse on average JCT (0.83h, 0.84h vs 0.76h) and worse on fairness, but by different mechanisms: at p = +1 a scalable job monopolizes GPUs; at p = -10 the scheduler churns. One scalar exponent controls both.

7.8 Pollux is evaluated partly on an axis it introduced. [derived inference] Paper Fig. 5's bottom panel plots "average cluster-wide statistical efficiency over time" — a quantity that exists only once EFFICIENCY_t is defined. Tiresias and Optimus have no such observable, so they can be scored on it only retroactively, through the simulator's replayed PGNS measurements.

8. Limitations of the Methodology

9. Note on NCCL Tuning

Pollux's T_sync model (Eqn. 9) is a two-branch linear function fitted per job, and the thing being fitted includes a decision Pollux does not control: "Gradients are synchronized with NCCL 2.7.8, which uses either ring all-reduce or tree all-reduce depending on the detected GPUs and their placements and its own internal performance estimates." So the four alpha_sync / beta_sync constants are not properties of the network — they are properties of the network as filtered through whatever collective algorithm was selected for that shape, and they shift if that selection shifts, with nothing in the model able to notice. The paper's limitations paragraph anticipates this by listing "sophisticated synchronization algorithms" among the regimes where the linear form "may diverge from reality." A job-level performance model and a collective-level configuration policy are therefore stacked estimators of the same quantity: whichever adapts faster silently absorbs the other's variance, and the "at most 10%" average fit error in §3.2 is the observed size of that residual on this testbed and library version.

10. Analogy

Pollux is a freight railway that lets each train renegotiate its own car count and load-per-car every time the dispatcher re-cuts the schedule.

Conventional DL schedulers assign track slots to trains of fixed length: the shipper declares "eight cars" at booking time, and the dispatcher's only lever is when and where those cars run. That is Tiresias. Optimus may add or remove cars but cannot change how much each carries — lengthening the train past a point adds coupling slack without moving more freight, which is exactly the observation that Optimus "only slightly outperforms Tiresias because it does not also increase the batch size to better utilize those additional GPUs."

Pollux changes the contract. Each train carries its own loadmaster (PolluxAgent) measuring two things: how fast the train moves given its length (THROUGHPUT, from theta_sys) and how much of each car's cargo is genuinely useful rather than packing material (EFFICIENCY_t, from phi_t). Their product — useful tonnage per hour — is goodput. Critically, the packing-material fraction changes over the journey: early on, stuffing more into each car dilutes what arrives; later the cargo has consolidated and the same car carries far more useful weight. That is the PGNS rising "by up to 10x or more" during training, and why paper Fig. 6's phase (C) shows the same train taking a bigger per-car load than in phase (A) under comparable yard congestion.

The dispatcher (PolluxSched) no longer optimizes track occupancy but a power mean of every train's useful-tonnage-per-hour relative to that train's fair share of the yard — FITNESS_p over SPEEDUP_j — with p as the dial between "run whatever moves the most freight" (p = +1) and "do not starve the slowest shipper" (p = -10), measured best at p = -1. Two rules round it out: no two long-haul trains may share a siding, and re-cutting a train already re-cut many times costs more than re-cutting a stable one, because every re-cut costs 15 to 120 seconds in the yard.

The analogy makes obvious why the improvement is larger against realistically-configured baselines (72-73%) than expertly-configured ones (37-50%): a dispatcher who cannot change train composition is at the mercy of how well the shipper guessed at booking time, and most shippers guess by multiplying their single-car load by the number of cars they asked for. Pollux's real claim is not that it dispatches better — it is that it removes the shipper's guess from the critical path, and keeps re-making that guess as the cargo changes character mid-journey.