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

ArXiv: 2008.12260

🎯 Pitch

By introducing a new metric—goodput—that combines throughput with statistical efficiency, Pollux automatically and dynamically re-allocates GPUs and re-tunes batch sizes for each deep learning job, cutting completion times nearly in half compared to even perfectly-configured static schedulers.

---

1. Executive Summary

Pollux introduces a co-adaptive cluster scheduler for deep learning that jointly optimizes both per-job training configuration and cluster-wide resource allocation by maximizing a novel metric called goodput — the product of system throughput and statistical efficiency (measured via the pre-conditioned gradient noise scale). The scheduler deploys a PolluxAgent alongside each job to fit predictive models of throughput and efficiency from observed training behavior, while a centralized PolluxSched periodically re-allocates GPUs across all jobs by maximizing a tunable fairness-sensitive fitness function over predicted speedups, explicitly co-adapting batch size, learning rate, gradient accumulation, and GPU placement as interdependent variables. Evaluated on a 64-GPU testbed with a workload derived from Microsoft cluster traces spanning six model types (ResNet-50, YOLOv3, DeepSpeech2, BERT, ResNet-18, NeuMF), Pollux reduces average job completion time by 37–50% relative to state-of-the-art schedulers even when those baselines are supplied with manually-tuned ideal resource and batch-size configurations for every job, and by 72–73% under realistic user configurations. The scheduler also improves finish-time fairness by 1.5×–5.4× over the same baselines, establishing that goodput-driven co-adaptation substantially outperforms throughput-only or static allocation approaches across a wide range of cluster loads.

2. Context and Motivation

The Core Problem: Manual Configuration of DL Jobs in Shared Clusters Is Fundamentally Broken

The central problem Pollux addresses is deceptively simple to state but enormously complex in practice: how should a shared cluster scheduler automatically configure deep learning training jobs so that all jobs complete as quickly and fairly as possible? This matters because deep learning training has become a dominant workload in datacenters and cloud environments, yet the process of configuring these jobs for efficient execution remains a manual, error-prone, and fundamentally suboptimal practice.

The paper identifies a specific configuration trilemma that makes manual configuration especially problematic. Three inter-dependent variables jointly determine training performance:

1. Resource allocation (number of GPUs, their placement across nodes)
2. Batch size (both per-GPU batch size and total batch size across all GPUs)
3. Learning rate (which must be scaled in response to batch size changes)

These variables cannot be chosen independently because they interact through two competing forces. First, system throughput — the number of training examples processed per wall-clock second — generally increases with more GPUs and larger batch sizes. Figure 1a illustrates this: larger batch sizes enable higher utilization of more GPUs by increasing the ratio of computation time (T_grad) to synchronization time (T_sync). Second, statistical efficiency — the amount of training progress made per example processed — generally decreases as batch size grows. Figure 1b shows that the optimal tradeoff between these forces depends on both the number of allocated GPUs and the current stage of training, since models in later training stages can tolerate much larger batch sizes without degrading statistical efficiency.

The consequence is that a user submitting a job must make decisions with imperfect information about cluster load, hardware performance characteristics, and their model's statistical behavior — all of which change dynamically during training. The paper states this explicitly in Section 1:

"allocating too many GPUs may result in long queuing times and inefficient resource usage, while allocating too few GPUs may result in long runtimes and unused resources. Such decisions are especially difficult to make in a shared-cluster setting, since optimal choices are dynamic and depend on the cluster load while a job is running."

Why This Problem Matters: Real-World Consequences

The practical significance of this configuration problem is twofold.

First, the cost of misconfiguration is enormous. In production clusters, deep learning jobs are resource-intensive and long-running. The Microsoft cluster trace that Pollux uses for evaluation (Jeon et al., 2019) reveals jobs spanning from under 1 GPU-hour to over 100 GPU-hours, with the largest jobs consuming computational resources equivalent to weeks of single-GPU training. When such jobs are misconfigured — using too few GPUs and thus running unnecessarily long, or too many GPUs with poor utilization — the waste multiplies across hundreds of jobs sharing a cluster. The paper's evaluation demonstrates that even rational, knowledgeable users who manually tune their configurations leave 37–50% performance on the table compared to what Pollux achieves automatically (Table 2). Under more realistic assumptions where users do not perfectly tune their jobs, the gap widens to 72–73%.

Second, the problem is getting worse, not better. As model sizes grow and training datasets expand, the configuration space becomes more complex. Different model architectures exhibit dramatically different scaling behavior — some benefit substantially from co-locating GPUs on the same node (YOLOv3, BERT, as shown in Figure 3), others scale well across nodes (ImageNet/ResNet-50), and some require gradient accumulation to achieve batch sizes large enough to overcome synchronization overhead. A one-size-fits-all configuration strategy is doomed to fail across this diversity.

Prior Approaches and Where They Fall Short

The paper categorizes existing DL schedulers into two broad families, identifying specific limitations in each.

Non-Scale-Adaptive Schedulers: Static Allocation, No Awareness of Job Scalability

These schedulers treat the number of GPUs as a fixed property specified by the user at submission time. Tiresias (Gu et al., 2019) is the primary example evaluated in the paper. It uses a two-level priority queue to schedule jobs based on their service-level objectives but makes no attempt to determine whether the specified GPU count is appropriate. The paper notes:

"Tiresias requires users to specify the number of GPUs at the time of job submission, which will be fixed for the lifetime of the job."

Gandiva (Xiao et al., 2018) goes further by enabling fine-grained time-sharing and job packing, dynamically changing GPU assignments opportunistically. However, the paper emphasizes that Gandiva "does so opportunistically and not based on knowledge of job scalability" — it may move GPUs between jobs to improve packing efficiency but has no model of whether those GPUs actually help the receiving job complete faster.

The fundamental limitation of non-scale-adaptive schedulers is that they decouple the decision about how many GPUs to use from the question of how well those GPUs can be utilized. A user might request 8 GPUs for a job that saturates at 4 (wasting half the allocation) or request 2 GPUs for a job that could effectively use 16 (leaving performance on the table). The scheduler has no mechanism to detect or correct either case.

Scale-Adaptive Schedulers: Resource Elasticity Without Training Re-Optimization

A more recent line of work attempts to automatically determine resource allocations. Optimus (Peng et al., 2018) learns a predictive model of system throughput for each job as a function of GPU count and optimizes cluster-wide allocations to minimize average job completion time. SLAQ (Zhang et al., 2017) takes a similar approach but targets general ML training rather than deep learning specifically. Gavel (Narayanan et al., 2020) extends the idea to heterogeneous accelerator types. AntMan (Xiao et al., 2020) combines dynamic scaling with fine-grained GPU sharing. Themis (Mahajan et al., 2020) introduces finish-time fairness as an explicit scheduling objective.

These schedulers represent a significant advance over static allocation. However, the paper identifies a critical oversight common to all of them:

"Crucially, existing schedulers are agnostic to the statistical efficiency of DL training and the inter-dependence of resource decisions and training parameters."

The key insight is that allocating more GPUs without also adjusting the batch size and learning rate is often counterproductive. Consider a concrete scenario: Optimus decides to give a ResNet-50 training job 8 GPUs instead of 4, based on a throughput model that predicts higher examples-per-second. But if the job's batch size remains fixed at, say, 256 images total, then the per-GPU batch size drops from 64 to 32. This reduces T_grad relative to T_sync (by Amdahl's Law, the synchronization time becomes the bottleneck), meaning the throughput improvement from adding GPUs is significantly less than the model predicted. Worse, if the learning rate is not adjusted to account for the changed per-GPU batch size, the model may converge more slowly or to a worse final quality — a cost that throughput-based schedulers completely ignore.

Even when a scale-adaptive scheduler correctly identifies that more GPUs would help, it has no mechanism to re-optimize the training procedure itself to make effective use of those additional resources. The paper emphasizes:

"Some recent schedulers choose job resources for users, but do so without awareness of how DL training can be re-optimized to better utilize the provided resources."

This is the gap that Pollux fills: the scheduler must not only decide how many GPUs to allocate but also how the training procedure should change to extract value from that allocation.

The Missing Piece: Statistical Efficiency and Training Progress

The paper identifies the gradient noise scale (GNS), originally introduced by McCandlish et al. (2018), as the key concept that prior schedulers ignore. The GNS measures the noise-to-signal ratio of stochastic gradients — intuitively, how much random variation exists in the gradient estimates relative to the true gradient direction:

"When the stochastic gradient has low noise, adding more training examples to each mini-batch does not significantly improve each gradient estimate, which lowers statistical efficiency. When the stochastic gradient has high noise, adding more training examples to each mini-batch reduces the noise of each gradient estimate, which maintains high statistical efficiency."

This explains why the optimal batch size changes during training. Early in training, gradients are noisy (high GNS), so larger batches provide genuine statistical benefit. Near convergence, gradients have lower signal relative to noise, so larger batches are again useful. The GNS can vary by 10× or more over the course of training (Section 2.2), meaning that a batch size that is optimal at epoch 10 may be substantially suboptimal at epoch 90.

The paper generalizes the GNS to pre-conditioned gradient noise scale (PGNS) to support adaptive optimizers like Adam and AdaGrad, which are more commonly used in practice than vanilla SGD. The PGNS captures the same noise-to-signal concept but in the pre-conditioned gradient space, enabling the framework to apply across optimizer choices.

Conflicting Prior Evidence on Batch Size and Learning Rate Adaptation

The paper builds on a substantial body of work on adaptive batch size training. AdaBatch (Devarakonda et al., 2017) increases batch size at predetermined iterations. Smith et al. (2017) propose increasing batch size instead of decaying learning rate. CABS (Balles et al., 2016) adaptively tunes batch size and learning rate using gradient statistics. AdaScale (Johnson et al., 2020) provides a scale-invariant learning rate adaptation rule based on the GNS.

However, these works share a critical assumption that does not hold in shared cluster environments:

"These works have a common assumption that extra computing resources are available to parallelize larger batch sizes whenever desired, which is rarely true inside shared-resource environments."

In other words, prior adaptive training methods assume they can choose their resource allocation. In a shared cluster, the scheduler assigns resources based on contention, and the training procedure must adapt to whatever resources are provided. Pollux inverts this relationship: the scheduler actively considers how the training procedure would adapt when deciding what allocations to make.

How Pollux Positions Itself

Pollux's positioning can be understood as bridging the gap between adaptive training algorithms and resource schedulers. The paper frames this through a co-adaptive architecture (Figure 4):

• PolluxAgent (per-job): Runs alongside each training job, profiling throughput and statistical efficiency, fitting predictive models, and re-tuning batch size and learning rate based on currently allocated resources. This component embodies the adaptive training literature but with awareness that resource allocations come from an external scheduler, not from an unlimited pool.

• PolluxSched (cluster-wide): Periodically re-allocates GPUs across all jobs by maximizing a fitness function over predicted speedups, where speedups are computed using the goodput functions supplied by each PolluxAgent. This component embodies the scale-adaptive scheduling literature but with awareness that jobs can re-optimize their training procedures in response to allocation changes.

The two components co-adapt: PolluxAgent tells PolluxSched how well each job would utilize different resource allocations (via the goodput function), and PolluxSched tells PolluxAgent what allocation it actually receives (so the agent can re-tune accordingly). Neither component works in isolation — the agent without the scheduler would just optimize for whatever fixed allocation it happens to have, and the scheduler without the agent would make allocation decisions assuming jobs can't re-optimize.

The paper draws a direct parallel between this co-adaptive approach and the traditional notion of goodput in computer networks — the useful portion of throughput as benchmarked by actual progress. This analogy is deliberate: just as network goodput subtracts retransmissions and protocol overhead from raw throughput, Pollux's goodput subtracts the "wasted" computation from examples that don't efficiently contribute to training progress. This reframing converts the scheduling problem from "maximize examples processed per second" to "maximize training progress per second," which is what users actually care about.

3. Technical Approach

3.1 Reader Orientation

This paper presents an architecture paper — it describes and evaluates a complete system (Pollux) that combines predictive modeling, per-job optimization, and cluster-wide scheduling into a co-adaptive framework for deep learning clusters. The core idea is that by explicitly modeling the interaction between system throughput (examples processed per second) and statistical efficiency (training progress per example), the system can simultaneously tune per-job configurations (batch size, learning rate, gradient accumulation) and cluster-wide GPU allocations in a mutually-informed way, maximizing a unified metric called "goodput" that captures useful training progress per wall-clock second.

The system solves the problem of resource allocation in shared DL clusters where users cannot be expected to manually configure the interdependent variables of GPU count, batch size, and learning rate — especially since optimal values change dynamically with training progress and cluster load. Rather than treating resource allocation and training configuration as separable decisions (as prior schedulers do), Pollux fuses them into a single optimization loop where the scheduler's allocation decisions account for how each job would adapt its training procedure, and each job's local optimizer adapts to whatever resources it receives.

3.2 Big-Picture Architecture (Diagram in Words)

Pollux has two primary components that communicate bidirectionally:

1. PolluxAgent (per-job): A library imported into each DL training job's code. It profiles the job's execution — measuring iteration times under various (GPU allocation, per-GPU batch size, gradient accumulation steps) configurations and computing the pre-conditioned gradient noise scale (PGNS) — then fits predictive models for both throughput and statistical efficiency. Using these models, it continuously re-tunes the job's batch size, gradient accumulation, and learning rate to maximize goodput given the current GPU allocation. It periodically reports its fitted throughput parameters and current PGNS value to PolluxSched.

2. PolluxSched (cluster-wide): A centralized service (deployed in Kubernetes) that periodically receives updated goodput models from all PolluxAgents. It searches over possible GPU allocation matrices — respecting node capacity constraints, interference avoidance rules, and a configurable fairness parameter — to maximize a fitness function defined as a generalized power mean of per-job speedups (where speedup is the predicted goodput under a candidate allocation relative to a fair-share baseline). The optimizer penalises re-allocations to avoid thrashing, then applies the chosen allocations by creating or terminating Kubernetes Pods.

Information flows in a closed loop: PolluxAgent $\rightarrow$ (throughput params $\theta_{\text{sys}}$, PGNS $\phi_t$) $\rightarrow$ PolluxSched; PolluxSched $\rightarrow$ (new allocation vector $a$) $\rightarrow$ PolluxAgent; PolluxAgent then re-optimizes $(m, s)$ for the new $a$.

3.3 Roadmap for the Deep Dive

• First, the Goodput formulation (Section 3.4.1): We define goodput as the product of throughput and statistical efficiency, formalize the configuration parameters $(a, m, s)$, and explain the plug-in learning rate scaling mechanism. This is foundational because every other component exists to optimize goodput.

• Second, the statistical efficiency model (Section 3.4.2): We derive the pre-conditioned gradient noise scale (PGNS) and the efficiency function $\text{EFFICIENCY}_t(M)$, and explain how Pollux estimates $\phi_t$ during training. This is the novel half of the goodput equation that prior schedulers ignored.

• Third, the system throughput model (Section 3.4.3): We walk through the parametric model for $T_{\text{grad}}$, $T_{\text{sync}}$, and their combination with a soft-overlap parameter $\gamma$, plus the treatment of gradient accumulation. This provides the predictable, hardware-sensitive half of goodput.

• Fourth, PolluxAgent's job-level optimization (Section 3.4.4): We explain how the agent fits the throughput model online from observed iteration times, uses prior-driven exploration to avoid getting stuck, and re-tunes $(m, s)$ for its current allocation.

• Fifth, PolluxSched's cluster-wide optimization (Section 3.4.5): We walk through the fitness function, the generalized power mean and its fairness knob $p$, the re-allocation penalty, interference avoidance, and the population-based search procedure.

This order builds from the mathematical definition of the objective through the predictive models that enable optimization, to the two optimization agents that operate at different scales.

3.4 Detailed, Sentence-Based Technical Breakdown

This is an architecture and systems paper whose core idea is that a unified goodput metric, enabled by on-the-fly statistical efficiency estimation and throughput profiling, allows a scheduler to co-adapt per-job training configuration and cluster-wide resource allocation in a mutually-informed feedback loop, yielding substantially lower job completion times than treating these as separable decisions.

---

3.4.1 The Goodput Formulation and Configuration Space

Definition and intuition. Pollux defines the goodput of a DL training job at iteration $t$ as:

$\text{GOODPUT}_t(\star) = \text{THROUGHPUT}(\star) \times \text{EFFICIENCY}_t(M(\star))$

where $\star$ represents any configuration parameters that jointly influence the throughput and total batch size. The paper focuses on three configuration parameters of particular impact for resource scheduling, so $\star = (a, m, s)$:

• $a \in \mathbb{Z}^N$: the allocation vector, where $a_n$ is the number of GPUs allocated from node $n$ (and $N$ is the total number of nodes in the cluster).
• $m \in \mathbb{Z}$: the per-GPU batch size, i.e., how many training examples each GPU processes in one forward-backward pass.
• $s \in \mathbb{Z}$: the number of gradient accumulation steps, which allows the effective batch size to exceed what fits in a single GPU's memory (explained fully in Section 3.4.3).

What it computes: Given a concrete configuration of how many GPUs are placed on which nodes, how many examples each GPU processes per step, and how many accumulation steps are used, goodput is a scalar measured in "effective training examples processed per unit wall-clock time." The throughput factor $\text{THROUGHPUT}(a, m, s)$ is the raw rate of examples pushed through the system. The efficiency factor $\text{EFFICIENCY}_t(M)$ is a number between 0 and 1 that scales the raw throughput down to account for the fact that larger batch sizes yield less statistical progress per example.

Why this form: This multiplicative decomposition separates two phenomena that prior schedulers conflated or ignored. Throughput is a function of hardware, network topology, and batch size — it can be profiled and modeled from system measurements alone. Statistical efficiency is a function of the model architecture, optimizer, and current training progress — it can be estimated from gradient statistics. Multiplying them yields a single scalar that reflects useful training progress, which is what users actually care about. The paper explicitly draws an analogy to network goodput:

"Our notion of goodput for DL is analogous to the traditional definition of goodput in computer networks, i.e. the useful portion of throughput as benchmarked by training progress per unit of wall-clock time."

The total batch size. The total number of examples used in one optimizer step is:

$M(a, m, s) = \text{SUM}(a) \times m \times (s + 1)$

where $\text{SUM}(a) = \sum_n a_n$ is the total number of allocated GPUs. The factor $(s+1)$ accounts for the fact that with $s$ accumulation steps, each GPU accumulates local gradients over $s$ mini-batches before one synchronization step, making the effective batch size $(s+1)$ times larger than a single forward-backward pass would provide.

Statistics Efficiency, relative to initial configuration. Pollux defines $\text{EFFICIENCY}_t(M)$ relative to an initial batch size $M_0$ and learning rate $\eta_0$ selected by the user at job submission time. The initial configuration is $M = M_0$ (on a single GPU, with $m = M_0$ and $s = 0$), and $\text{EFFICIENCY}_t(M_0) = 1$ by definition. For any $M > M_0$, $\text{EFFICIENCY}_t(M)$ is a fraction between 0 and 1. This means goodput can be interpreted operationally as the portion of raw throughput that contributes to training progress — it equals throughput if and only if the job maintains perfect statistical efficiency at its current batch size.

Plug-in learning rate scaling. When the batch size changes from $M_0$ to $M$, the learning rate $\eta$ must also be adjusted, otherwise the model may converge more slowly or to a worse final quality. The paper notes that different optimizers and models require different scaling rules: linear scaling for SGD ($\eta \propto M$), square-root scaling for Adam ($\eta \propto \sqrt{M}$), and adaptive rules like AdaScale that compute a scale factor from gradient statistics.

Rather than hard-coding a specific rule, Pollux provides a plug-in interface:

$\text{SCALE\_LR}(M_0, M) \rightarrow \lambda$

This function is called before every model update step. The implementation can use any metrics collected during training (such as the gradient noise scale). The returned $\lambda$ is used by Pollux to scale the learning rate: $\eta \leftarrow \lambda \cdot \eta_0$. Using this interface, one can implement AdaScale, square-root scaling, linear scaling, LEGW, or any custom rule — but the paper explicitly notes that the user must supply an implementation appropriate for their optimizer and model.

Upper batch size limit. In some cases, LR scaling rules break down before statistical efficiency drops to zero, causing degraded final model quality. The paper addresses this with a user-defined maximum batch size limit that Pollux respects. The authors report that a batch size up to 32× larger than $M_0$ works well in most cases, and that limits for common models are well-studied for popular scaling rules.

---

3.4.2 Modeling Statistical Efficiency via the Pre-Conditioned Gradient Noise Scale

Theoretical foundation. The statistical efficiency model is grounded in the concept of the gradient noise scale (GNS), originally introduced by McCandlish et al. (2018) for vanilla SGD. The GNS measures the ratio of gradient variance to gradient magnitude — intuitively, it quantifies how much random noise exists in stochastic gradient estimates relative to the true gradient signal. When the GNS is high (noisy gradients), larger batch sizes reduce the variance of the gradient estimate, providing genuine statistical benefit per additional example. When the GNS is low (clean gradients), adding more examples to a batch contributes diminishing statistical returns.

The original derivation shows that for vanilla SGD, it takes approximately $1 + \text{GNS}/M$ training iterations to make equivalent progress across different batch sizes $M$. More precisely, the statistical efficiency — the training progress per example processed — scales as $(\text{GNS} + M_0)/(\text{GNS} + M)$ when comparing batch size $M$ to a baseline $M_0$.

Generalizing to adaptive optimizers. Since modern DL training predominantly uses adaptive optimizers like Adam, AdaGrad, and AdamW rather than vanilla SGD, the paper generalizes the original GNS derivation to pre-conditioned SGD. In pre-conditioned SGD, the optimizer applies a pre-conditioning matrix $P$ (which in adaptive optimizers is a diagonal approximation to the inverse square root of the Fisher information matrix) to the gradient before updating parameters. This is mathematically equivalent to optimizing the loss function in a transformed parameter space.

The result is the pre-conditioned gradient noise scale (PGNS), denoted $\phi_t$:

$\phi_t = \frac{\text{tr}(P \Sigma P^T)}{|P g|^2}$

where:

• $g$ is the true gradient of the loss function at iteration $t$ (the gradient one would compute over the entire training dataset),
• $\Sigma$ is the covariance matrix of per-example stochastic gradients, i.e., $\Sigma = \mathbb{E}_{x_i}[(g_{x_i} - g)(g_{x_i} - g)^T]$ where $g_{x_i}$ is the gradient computed on a single example $x_i$,
• $P$ is the pre-conditioning matrix of the adaptive SGD algorithm at iteration $t$,
• $\text{tr}(\cdot)$ denotes the matrix trace (sum of diagonal entries), and $|\cdot|^2$ denotes the squared Euclidean norm.

What it computes: The numerator $\text{tr}(P \Sigma P^T)$ is the total variance of the pre-conditioned per-example gradients, summed across all parameter dimensions. It measures how much the pre-conditioned stochastic gradient fluctuates around the true pre-conditioned gradient. The denominator $|P g|^2$ is the squared length of the true pre-conditioned gradient — the signal strength. The ratio $\phi_t$ therefore measures the noise-to-signal ratio in the pre-conditioned gradient space: how many training examples would need to be averaged together for the stochastic gradient estimate to have the same squared length as the true pre-conditioned gradient.

Why this form: The trace-of-covariance formulation captures variance across all parameter dimensions without assuming any particular correlation structure. The pre-conditioning matrix $P$ appears both in numerator and denominator — in the numerator it transforms the per-example stochastic gradients before computing variance, and in the denominator it transforms the true gradient before computing magnitude. This ensures that $\phi_t$ is invariant to invertible linear transformations of the parameter space, which is precisely the property that makes the GNS the right statistic for vanilla SGD. For the special case of vanilla SGD ($P = I$, the identity matrix), $\phi_t$ reduces exactly to the original GNS from McCandlish et al. (2018).

From PGNS to statistical efficiency. Following the same derivation pattern as the original GNS paper, the number of training iterations needed to make equivalent progress using batch size $M$ versus baseline batch size $M_0$ is $1 + \phi_t/M$ versus $1 + \phi_t/M_0$, respectively. Therefore, the statistical efficiency — the amount of progress made per training example at batch size $M$ relative to $M_0$ — is:

$\text{EFFICIENCY}_t(M) = \frac{\phi_t + M_0}{\phi_t + M}$

What it computes: Given an estimated PGNS $\phi_t$ at the current iteration and the baseline batch size $M_0$, this function predicts the relative statistical efficiency at any candidate batch size $M \geq M_0$. A value of $\text{EFFICIENCY}_t(M) = 0.5$ means that training with batch size $M$ will require processing twice as many examples (i.e., $1/0.5$ times as many) to achieve the same training progress as with batch size $M_0$.

Why this form: The function has several desirable properties. First, $\text{EFFICIENCY}_t(M_0) = 1$ by construction — the baseline is self-consistent. Second, as the PGNS $\phi_t$ grows large (noisy gradients, typically later in training), $\text{EFFICIENCY}_t(M)$ approaches 1 even for large $M$, meaning large batch sizes become nearly as efficient as small ones. Third, as $\phi_t$ approaches 0 (clean gradients, typically early in training for some models), efficiency drops sharply with $M$. Together, these properties capture the key empirical observation from Figure 2: batch sizes that are inefficient early in training can become efficient later, and this transition is governed by the PGNS.

Estimating $\phi_t$ during training. When a job uses multiple data-parallel GPUs, each GPU $k$ already computes a local gradient estimate $\hat{g}_k^{(t)}$ on a different subset of the mini-batch. Pollux leverages these different gradient estimates — which are already available at no extra computational cost — to estimate the variance of the per-example gradients and thus $\phi_t$, following the procedure in Appendix A.1 of McCandlish et al. (2018) but applied to pre-conditioned gradients $P\hat{g}_k^{(t)}$ rather than raw gradients. This works when there are at least two independent gradient estimates, i.e., when the job uses multiple GPUs or gradient accumulation.

When the job uses only a single GPU and gradient accumulation is off ($s = 0$), there is only one gradient estimate per iteration, making the multi-replica variance estimator inapplicable. In this special case, Pollux switches to a differenced variance estimator (Wang and Yu, 2017) which uses the difference between consecutive gradient estimates $\hat{g}^{(t-1)}$ and $\hat{g}^{(t)}$ to estimate the variance, under the assumption that the true gradient changes slowly between consecutive iterations (which holds for small learning rates).

Validation of the efficiency model. Figure 2 provides empirical validation across all six model types in Table 1. The top row shows validation metrics versus training progress in "statistical epochs" (defined as $\frac{M}{|X|} \sum_t \text{EFFICIENCY}_t(M)$ where $|X|$ is the training dataset size) for three different batch sizes. The validation curves largely overlap, achieving similar best values across different batch sizes (±1% relative difference for all tasks except DeepSpeech2 at ±4%). The middle row shows measured statistical efficiency during training. The bottom row shows that $\text{EFFICIENCY}_t$ predicted from $\phi_t$ measured at one batch size accurately matches the measured efficiency at other batch sizes — meaning Pollux can predict efficiency at batch size $M'$ without ever training at $M'$.

---

3.4.3 Modeling System Throughput

Overall structure. The system throughput model predicts the time per training iteration $T_{\text{iter}}$ as a function of the resource allocation $a$, per-GPU batch size $m$, and gradient accumulation steps $s$. The throughput is then:

$\text{THROUGHPUT}(a, m, s) = \frac{M(a, m, s)}{T_{\text{iter}}(a, m, s)}$

where $M(a, m, s)$ is the total batch size defined earlier.

Modeling gradient computation time. In data-parallel training, each GPU computes a local gradient estimate using back-propagation over its partition of the mini-batch. The run-time of back-propagation scales linearly with the number of examples processed, so $T_{\text{grad}}$ is modeled as:

$T_{\text{grad}}(m) = \alpha_{\text{grad}} + \beta_{\text{grad}} \cdot m$

where $\alpha_{\text{grad}}$ is a constant overhead per iteration (model loading, kernel launch, etc.), $\beta_{\text{grad}}$ is the incremental time per additional training example, and $m$ is the per-GPU batch size.

What it computes: Given a batch size $m$, this function predicts the wall-clock time one GPU spends in forward and backward passes. It is a simple linear model with two fittable parameters.

Why this form: Back-propagation has a fixed computational graph traversal cost (the $\alpha$ term) plus per-example matrix multiplications (the $\beta$ term). The linear assumption holds well for modern DL frameworks because the computation graph structure is independent of batch size — only the tensor dimensions scale. This is the simplest model that captures the essential scaling behavior.

Modeling gradient synchronization time. After each GPU computes its local gradient, the gradients must be averaged across all GPUs. For synchronous data-parallel training using all-reduce (as implemented by PyTorch with NCCL), each GPU sends and receives gradient data proportional to the total model size — independent of the batch size. The synchronization time $T_{\text{sync}}$ is therefore modeled as a function only of the number of GPUs and their placement across nodes:

$T_{\text{sync}}(a, m) = \begin{cases} 0 & \text{if } K = 1 \\ \alpha_{\text{sync}}^{\text{local}} + \beta_{\text{sync}}^{\text{local}} \cdot (K - 2) & \text{if } N = 1, K \geq 2 \\ \alpha_{\text{sync}}^{\text{node}} + \beta_{\text{sync}}^{\text{node}} \cdot (K - 2) & \text{otherwise} \end{cases}$

where:

• $K = \text{SUM}(a)$ is the total number of GPUs allocated to the job,
• $N$ is the number of distinct physical nodes occupied by at least one GPU replica,
• $\alpha_{\text{sync}}^{\text{local}}$ and $\beta_{\text{sync}}^{\text{local}}$ are the constant and retrogression parameters when all GPUs are co-located on a single node,
• $\alpha_{\text{sync}}^{\text{node}}$ and $\beta_{\text{sync}}^{\text{node}}$ are the analogous parameters when GPUs span multiple nodes (using inter-node network communication).

What it computes: The time spent in gradient synchronization for a given GPU placement. When $K = 1$ (single GPU), no synchronization is needed and $T_{\text{sync}} = 0$. When multiple GPUs share a single node, synchronization uses intra-node communication (typically NVLink or PCIe). When GPUs span multiple nodes, inter-node communication (typically Ethernet or InfiniBand) is required, which is slower and represented by different $\alpha$ and $\beta$ values. The $K - 2$ term (rather than $K$) means the model parameterizes the incremental cost beyond two GPUs, which captures performance retrogressions like straggler effects or network congestion at larger scales.

Why this form: In data-parallel all-reduce, each GPU sends exactly one gradient-sized message regardless of batch size or GPU count (the all-reduce communication volume per GPU is $O(\text{model size})$, not $O(K \times \text{model size})$). The linear-in-$K$ term captures fixed overhead (the $\alpha$ parameters) plus per-GPU contributions (the $\beta$ parameters). The distinction between local and node-level parameters is critical because the performance gap between intra-node and inter-node communication can be substantial — Figure 3 shows a sharp increase in iteration time when GPUs exceed 4 (the per-node limit in the testbed), reflecting the transition from NVLink to Ethernet. The paper notes that the model could be extended to account for rack-level locality by adding a third pair of parameters.

Combining computation and communication. Modern DL frameworks (including PyTorch with NCCL) can overlap gradient computation with communication by starting the all-reduce of layer $i$'s gradients while still computing the backward pass for layer $i-1$. The degree of overlap depends on the model's layer structure (ordering and sizes of layers). To capture this, Pollux models the total iteration time using a soft combination parameterized by $\gamma$:

$T_{\text{iter}}(a, m, 0) = \left( T_{\text{grad}}(a, m)^\gamma + T_{\text{sync}}(a)^\gamma \right)^{1/\gamma}$

What it computes: A smooth interpolation between two extremes. When $\gamma = 1$, the expression reduces to $T_{\text{grad}} + T_{\text{sync}}$ (perfect serial execution, no overlap). As $\gamma \to \infty$, the expression approaches $\max(T_{\text{grad}}, T_{\text{sync}})$ (perfect overlap, total time equals the slower of the two phases). Realistic overlap falls between these extremes, and $\gamma$ is a learnable parameter fitted for each job.

Why this form: The $\ell_\gamma$-norm formulation provides a continuous, differentiable interpolation between sum and max with a single parameter. This is more parsimonious than modeling the overlap percentage explicitly (which would require knowing the layer-wise timing structure), and the fitted $\gamma$ value can be interpreted as an "overlap quality" score. The paper constrains $\gamma \in [1, 10]$ during fitting.

Gradient accumulation. GPU memory limits the maximum per-GPU batch size $m$. Many DL models hit this limit before $T_{\text{grad}}$ becomes large enough to overcome $T_{\text{sync}}$ (or before batch sizes reach the point of diminishing statistical returns), resulting in suboptimal scalability. Gradient accumulation addresses this by performing $s$ forward-backward passes with local gradient accumulation before one synchronization step. Specifically:

• For $s$ steps, each GPU computes $T_{\text{grad}}(m)$ without synchronizing, accumulating gradients locally.
• On the $(s+1)$-th step, the accumulated gradients are synchronized across all GPUs (incurring $T_{\text{sync}}$ plus overlap with the computation).

The total iteration time becomes:

$T_{\text{iter}}(a, m, s) = s \times T_{\text{grad}}(a, m) + \left( T_{\text{grad}}(a, m)^\gamma + T_{\text{sync}}(a)^\gamma \right)^{1/\gamma}$

What it computes: The wall-clock time for one complete SGD step (one gradient synchronization) when using $s$ accumulation steps. The first term $s \times T_{\text{grad}}$ is the time for the pure-accumulation steps (no synchronization). The second term is the time for the synchronization step, identical to the $s=0$ case. The effective total batch size is $M = K \times m \times (s+1)$.

Why this form: Gradient accumulation decouples the total batch size from the per-GPU memory limit. Without it, the maximum batch size is bounded by $K \times m_{\max}$ where $m_{\max}$ is the largest per-GPU batch that fits in memory. With accumulation, the effective batch size can be arbitrarily large (at the cost of additional computation time for the accumulation steps), enabling jobs to reach batch sizes where $T_{\text{grad}}$ overcomes $T_{\text{sync}}$ and where statistical efficiency is still acceptable.

Model fitting and validation. The full throughput model is parameterized by the 7-tuple:

$\theta_{\text{sys}} = \left( \alpha_{\text{grad}}, \beta_{\text{grad}}, \alpha_{\text{sync}}^{\text{local}}, \beta_{\text{sync}}^{\text{local}}, \alpha_{\text{sync}}^{\text{node}}, \beta_{\text{sync}}^{\text{node}}, \gamma \right)$

The paper validates this model against measured throughput for all six model types across a range of GPU allocations (1–64 GPUs), placements (single-node, multi-node), and batch sizes with and without gradient accumulation (Figure 3). The average fitting error was at most 10% across all configurations. Key qualitative patterns captured by the model include: the sharp increase in iteration time beyond 4 GPUs for models like YOLOv3 and BERT (indicating sensitivity to inter-node synchronization), the benefit of gradient accumulation for YOLOv3 and BERT to reach efficient batch sizes, and the smooth throughput-versus-batch-size curves for all models.

Modularity of the throughput model. The paper explicitly acknowledges that the linear assumptions in this model may not hold for specialized hardware (TPUs), sophisticated synchronization algorithms, different parallelization strategies (model parallelism, pipeline parallelism), very large scales, or hidden resource contention. Rather than attempting a universal model, the paper designed $\text{GOODPUT}_t$ to be modular: different equations for $\text{THROUGHPUT}$ may be plugged in without affecting the rest of the Pollux architecture.

---

3.4.4 PolluxAgent: Job-Level Optimization

PolluxAgent is a Python library imported into each training job's code. It performs three core functions: online model fitting, goodput maximization for the current allocation, and periodic reporting to PolluxSched.

Online model fitting for throughput. During training, PolluxAgent measures the time taken per iteration, $T_{\text{iter}}$, and records the tuple $(a, m, s, T_{\text{iter}})$ for every combination of resource allocation $a$, per-GPU batch size $m$, and gradient accumulation steps $s$ that the job encounters. Periodically (every 30 seconds in the evaluation), PolluxAgent fits the parameters $\theta_{\text{sys}}$ to all throughput data collected so far by minimizing the root mean squared logarithmic error (RMSLE) between the predicted $T_{\text{iter}}$ from Equation 11 and the observed values:

$\text{RMSLE} = \sqrt{\frac{1}{n} \sum_{i=1}^n \left( \log(T_{\text{iter}}^{\text{predicted}, i}) - \log(T_{\text{iter}}^{\text{observed}, i}) \right)^2}$

What it computes: The RMSLE penalises relative errors rather than absolute errors — a 10% over-prediction of iteration time is treated equivalently whether the iteration takes 10ms or 1 second. This is appropriate because throughput scales superlinearly with iteration time (throughput $\propto 1/T_{\text{iter}}$).

Why this form: Using log-space error ensures the model fits well across orders of magnitude of iteration time (single-GPU vs. multi-node configurations can differ by 10–100×). The paper uses L-BFGS-B for optimization with constraints: all $\alpha$ and $\beta$ parameters must be non-negative (negative overheads are physically meaningless), and $\gamma$ must be in $[1, 10]$ (corresponding to the range from no overlap to near-perfect overlap).

Prior-driven exploration. At the beginning of each job, throughput data has not yet been collected for most configurations. To prevent Pollux from getting stuck with suboptimal allocations due to missing information, the paper imposes priors on $\theta_{\text{sys}}$ that bias the model toward the belief that throughput scales perfectly with more resources until those configurations are actually explored:

• $\alpha_{\text{sync}}^{\text{local}} = 0$ while the job has not used more than one GPU.
• $\alpha_{\text{sync}}^{\text{node}} = \beta_{\text{sync}}^{\text{node}} = 0$ while the job has not used more than one node.
• $\beta_{\text{sync}}^{\text{local}} = \beta_{\text{sync}}^{\text{node}} = 0$ while the job has not used more than two GPUs.

These priors create a systematic exploration behavior: each job starts with one GPU and is initially assumed to scale perfectly. PolluxSched, seeing high predicted goodput at larger allocations, is encouraged to allocate more GPUs to the job. As the job experiences larger allocations, the PolluxAgent records actual iteration times, and the fitted parameters converge to reality. The paper also restricts the maximum number of GPUs that can be allocated to a job to at most twice the maximum number it has been allocated in its lifetime, preventing unbounded exploration. Section 5.3.2 reports that this simple prior-driven strategy performs within 2–5% of an idealized scenario where the throughput model is fitted offline before job submission.

Training job tuning. Once $\theta_{\text{sys}}$ is fitted (or priors are in place) and the PGNS $\phi_t$ is computed, the PolluxAgent has a fully specified $\text{GOODPUT}$ function. Given its current resource allocation $a$, it finds the most efficient per-GPU batch size and gradient accumulation steps by solving:

$(m^*, s^*) = \arg\max_{m, s} \text{GOODPUT}(a, m, s)$

What it computes: For the fixed GPU allocation $a$, search over possible $(m, s)$ pairs to find the combination that maximizes goodput — the product of throughput (which generally increases with larger $m$ and $s$) and statistical efficiency (which generally decreases with larger total batch size $M = K \times m \times (s+1)$).

Implementation of the search. The paper describes the implementation: "sampling a range of candidate values for the total batch size $M$, then finding the smallest $s$ such that $m = \lceil M/s \rceil$ fits into GPU memory according to a user-defined upper-bound, and finally taking the configuration which results in the highest GOODPUT value." The user must specify the GPU memory limit, enabling the search to respect hardware constraints.

Learning rate adaptation. Once a new $(m^*, s^*)$ is chosen, PolluxAgent calls the plug-in $\text{SCALE\_LR}$ function with the old and new total batch sizes to obtain a scaling factor $\lambda$, and updates the learning rate to $\lambda \cdot \eta_0$. This happens before every model update step.

Periodic reporting. Every 30 seconds (in the evaluation), PolluxAgent sends the latest fitted $\theta_{\text{sys}}$ and the current PGNS $\phi_t$ to PolluxSched. Together with the user-specified $M_0$, this triple $(\theta_{\text{sys}}, \phi_t, M_0)$ fully specifies the job's current $\text{GOODPUT}$ function, enabling PolluxSched to evaluate the fitness of candidate allocations.

---

3.4.5 PolluxSched: Cluster-Wide Optimization

PolluxSched is a centralized service deployed in Kubernetes that periodically (every 60 seconds in the evaluation) re-allocates GPUs across all jobs in the cluster. Its optimization problem has three components: a fitness function measuring how "good" a candidate allocation is, a search procedure for finding high-fitness allocations, and constraints to ensure practical feasibility.

The Fitness Function. PolluxSched evaluates a candidate allocation matrix $A$ (where row $A_j$ is the allocation vector for job $j$, and $A_{jn}$ is the number of GPUs on node $n$ allocated to job $j$) using a generalized power mean of per-job speedup factors:

$\text{FITNESS}_p(A) = \left( \frac{1}{J} \sum_{j=1}^J \text{SPEEDUP}_j(A_j)^p \right)^{1/p}$

where:

• $J$ is the total number of running and pending jobs in the cluster,
• $p \in \mathbb{R}$ is the fairness parameter (the "fairness knob"),
• $\text{SPEEDUP}_j(A_j)$ is the predicted speedup factor for job $j$ under allocation $A_j$.

What it computes: A scalar aggregate of how much each job benefits (relative to a fair-share baseline) under the proposed allocation. The power mean smoothly interpolates between different notions of "aggregate benefit."

Why this form: The parameter $p$ controls the fairness-efficiency tradeoff through a single tunable knob. When $p = 1$, $\text{FITNESS}_p$ is the arithmetic mean of speedups — this maximizes total cluster goodput but allows some jobs to achieve very high speedups at the expense of others. As $p \to -\infty$, $\text{FITNESS}_p$ approaches the minimum of speedups — maximizing this promotes equal speedups across all jobs (i.e., max-min fairness) but ignores overall cluster efficiency. Intermediate values like $p = -1$ (the harmonic mean, which the paper uses as default) balance these extremes. The paper explicitly notes:

"a cluster operator may select a suitable value, based on organizational priorities."

The Speedup Definition. The speedup for job $j$ under allocation $A_j$ is defined as:

$\text{SPEEDUP}_j(A_j) = \frac{\max_{m,s} \text{GOODPUT}_j(A_j, m, s)}{\max_{m,s} \text{GOODPUT}_j(a_f, m, s)}$

where $a_f$ is the fair-resource allocation: an exclusive $1/J$ share of the cluster. Specifically, $a_f$ is defined such that the job receives exactly $\text{total\_GPUs} / J$ GPUs (placed as efficiently as possible).

What it computes: The numerator is the maximum goodput job $j$ can achieve under the candidate allocation $A_j$ (after the PolluxAgent optimizes its $(m, s)$ for that allocation). The denominator is the maximum goodput under a fair-share baseline. A speedup of 2 means the job performs twice as well under the candidate allocation as it would under an equal partition — it benefits from receiving more resources. A speedup below 1 means the job is performing worse than fair-share. The max-over-$(m,s)$ inside both numerator and denominator means each allocation is evaluated assuming the job's own PolluxAgent would optimize its training configuration for that allocation.

Why this form: Normalizing by fair-share performance makes speedup comparable across jobs of different sizes, models, and training stages. A job that would take 10 hours under fair-share might be accelerated to 5 hours (speedup 2) with 8 extra GPUs, while a tiny job that would take 10 minutes under fair-share is unbounded in speedup because it can be given many more GPUs than its fair share. The speedup metric captures the benefit of deviation from fairness, not the absolute allocation size, which is what the fairness knob operates on.

Re-allocation penalty. Each time a job's GPU allocation changes, it incurs a delay for checkpoint-restart (measured between 15 and 120 seconds depending on model size). To prevent excessive re-allocations, PolluxSched applies a multiplicative penalty to each job's speedup before evaluating fitness:

$\text{SPEEDUP}_j(A_j) \leftarrow \text{SPEEDUP}_j(A_j) \times \text{REALLOC\_FACTOR}_j(\delta)$

where:

$\text{REALLOC\_FACTOR}_j(\delta) = \frac{T_j - R_j \delta}{T_j + \delta}$

• $T_j$ is the age of job $j$ (time since submission),
• $R_j$ is the number of re-allocations the job has experienced so far,
• $\delta$ is an estimate of the re-allocation delay.

What it computes: The penalty factor scales the predicted speedup based on the historical re-allocation rate. If a job has been re-allocated $R_j$ times over its lifetime $T_j$, the factor estimates the fraction of the job's remaining time that will be spent productively (not restarting), assuming the historical re-allocation rate continues.

Why this form: The expression equals 1 when $R_j = 0$ (no penalty for first re-allocation), decreases linearly with $R_j$, and approaches 0 as $R_j \to T_j/\delta$ (the point where the job spends all its time restarting). Jobs that have historically experienced frequent re-allocations are penalized more heavily for future re-allocations, discouraging thrashing. This is a heuristic — the true expected re-allocation rate is not known — but the paper reports it effectively limits re-allocation frequency to an average of once every 7 minutes in the testbed experiments.

Interference avoidance. When multiple distributed DL jobs share a single node, their gradient synchronization network traffic can interfere, causing both jobs to experience significant slowdowns (up to 50% has been reported). To mitigate this, PolluxSched enforces a hard constraint: at most one distributed job can be allocated to each node, where a distributed job is defined as one that uses GPUs across multiple nodes. This constraint is incorporated into the search algorithm by rejecting allocation matrices that violate it.

Search procedure. Finding the allocation matrix $A$ that maximizes $\text{FITNESS}_p$ subject to node capacity constraints, interference avoidance, and the maximum-allocation-doubling rule from PolluxAgent is a combinatorial optimization problem. The paper uses a population-based search algorithm that:

1. Maintains a population of candidate allocation matrices.
2. Perturbs and combines candidates to produce new candidates.
3. Evaluates each candidate's fitness (including the re-allocation penalty).
4. Modifies candidates to satisfy constraints (node capacity, interference avoidance).
5. Keeps the highest-fitness candidates for the next generation.
6. Returns the highest-fitness allocation matrix overall.

The search runs for each 60-second scheduling interval, taking an average of 1 second on 1 vCPU in the paper's evaluation.

Supporting non-adaptive jobs. For jobs that specify a fixed batch size ($M = M_0$) and do not wish Pollux to tune their training configuration, PolluxSched can still adapt their resource allocations based solely on throughput. In this case, the PolluxAgent fixes $\text{EFFICIENCY}_t \equiv 1$ for that job, and the goodput reduces to pure throughput. The scheduler can then allocate GPUs based on scalability alone, without statistical efficiency considerations.

What happens to pending jobs. Newly submitted jobs are included in the fitness function alongside running jobs. Since pending jobs have $T_{\text{iter}}$ widely unknown (no throughput data collected yet), the prior-driven exploration mechanism ensures they are initially assumed to scale perfectly. PolluxSched is thus encouraged to allocate GPUs to pending jobs — naturally integrating admission control with resource re-allocation in a single optimization.

4. Key Insights and Innovations

Innovation 1: Goodput as a Unified Metric That Bridges System Throughput and Statistical Efficiency

Before Pollux, the DL resource scheduling literature treated system throughput and training convergence as fundamentally separate concerns — the former was the scheduler's responsibility, the latter was the user's problem. Optimus (Peng et al., 2018) and SLAQ (Zhang et al., 2017) modeled throughput as a function of GPU count but had no language for expressing that throughput gains from larger batch sizes come at the cost of statistical efficiency. Gavel (Narayanan et al., 2020) improved throughput modeling across heterogeneous accelerators but remained agnostic to convergence behavior. On the other side, the adaptive training literature (AdaBatch, CABS, AdaScale) developed principled methods for tuning batch size and learning rate using gradient statistics, but assumed they controlled their resource allocation — a false assumption in shared clusters. These two communities spoke different languages and optimized disjoint objectives.

The conceptual contribution of goodput is that it fuses these two objectives into a single, measurable, predictable scalar that captures what users actually care about: training progress per wall-clock second. The multiplication THROUGHPUT × EFFICIENCY is deceptively simple, but its power comes from what it makes possible: it renders the tradeoff between "process more examples faster" and "get more progress per example" commensurable. A configuration that halves statistical efficiency but triples throughput produces 1.5× the goodput and is therefore preferable — and the scheduler can evaluate this tradeoff across heterogeneous jobs (image classifiers, speech recognizers, recommenders) with entirely different throughput and efficiency curves using the same objective function.

This is more than a new metric; it is a diagnostic framing shift. Prior work implicitly treated statistical efficiency as a binary constraint ("don't degrade final model quality") rather than a continuous function that varies with batch size and training progress. Pollux's goodput formulation reveals that batch size selection is not about staying below some maximum-acceptable value, but about finding the sweet spot where the marginal throughput gain from a larger batch size equals the marginal efficiency loss. This reframing converts batch size selection from a safety check into an optimization problem, which is what enables the co-adaptive architecture. The evidence that this reframing is not obvious comes from the paper's own baselines: even when Optimus is given oracle knowledge of each job's convergence curve (Optimus+Oracle, Section 5.2), it underperforms Pollux by 37–50% because it cannot adapt batch sizes in response to allocation changes — it lacks the conceptual framework to even express the optimization.

The generality of the goodput formulation is also distinctive. The paper explicitly designs it to be modular: the THROUGHPUT function can be swapped out for different parallelization strategies (model parallelism, pipeline parallelism) or hardware (TPUs, heterogeneous accelerators) without touching the EFFICIENCY model or the scheduling architecture. This separation of concerns — throughput as a profiled system characteristic, efficiency as an estimated statistical property — is a conceptual decomposition that the field had not previously articulated, and it provides a template for extending Pollux's approach to training modalities beyond synchronous data-parallel SGD.

Innovation 2: Difficulty-Aware, Live Statistical Efficiency Estimation via PGNS

The field's understanding of how batch size affects training dynamics has a substantial theoretical foundation — McCandlish et al. (2018) derived the gradient noise scale (GNS) and showed it governs the statistical efficiency of SGD. But this theory had two critical gaps that prevented it from being used in a production scheduler. First, it applied only to vanilla SGD, while real-world training predominantly uses adaptive optimizers like Adam and AdamW, which apply per-parameter pre-conditioning that changes the noise structure. Second, prior work treated GNS as a property to be measured offline or assumed constant, while Figure 2 shows it varies dramatically during training (by up to 10× or more), meaning that a static measurement would be obsolete for most of a job's lifetime.

The pre-conditioned gradient noise scale (PGNS) is a theoretical advance that extends the GNS derivation from vanilla SGD to the pre-conditioned setting, showing that the same functional form EFFICIENCY(M) = (φ + M₀)/(φ + M) holds when the gradient and covariance are transformed by the pre-conditioning matrix P. This is not an ad-hoc generalization — it follows directly from re-deriving the "simple noise scale" starting from pre-conditioned SGD rather than vanilla SGD, making it mathematically principled rather than heuristic. For the special case of P = I (vanilla SGD), it reduces exactly to the original GNS, providing backward compatibility.

But the deeper innovation is live estimation from already-available data. Every data-parallel training job with multiple GPUs already computes independent gradient estimates ĝ_k on each GPU. The PGNS estimator re-uses these — which exist regardless of whether anyone is measuring statistical efficiency — to estimate gradient variance and thus φ_t, with zero additional forward-backward passes. This is what makes the approach practical for a scheduler: the statistical efficiency model doesn't require dedicated profiling runs, offline characterization, or user expertise. It piggybacks on computation that is already happening. The differenced variance estimator for the single-GPU case (when the multi-replica approach is unavailable) provides a graceful fallback, ensuring that even small or initial allocations can contribute useful efficiency estimates.

The validation in Figure 2 (bottom row) confirms that this estimator works across heterogeneous model types — ResNet, YOLOv3, DeepSpeech2, BERT, NeuMF — with different optimizers, architectures, and convergence dynamics. The predicted efficiency at one batch size accurately matches the measured efficiency at other batch sizes, meaning Pollux can predict the statistical consequences of a batch size change without ever running at that batch size. This predictive capability is what enables PolluxSched to evaluate candidate allocations in the optimization loop: when considering whether to give a job 8 GPUs instead of 4, the scheduler can compute what batch size the agent would choose for 8 GPUs, then predict the statistical efficiency at that batch size using φ_t measured at the current 4-GPU configuration. Neither the agent nor the scheduler needs to actually try the 8-GPU configuration to evaluate its goodput — making the cluster-wide optimization computationally tractable.

Innovation 3: Co-Adaptive Architecture That Fuses Local Tuning with Global Scheduling in a Closed Feedback Loop

Existing approaches to DL cluster management separate the "what resources does this job need?" question (answered by the user, a heuristic, or a standalone profiler) from the "how should the cluster allocate resources?" question (answered by the scheduler). This separation creates an information asymmetry: the scheduler allocates GPUs without knowing how the job will capitalize on them, and the job tunes its training without knowing what resources it might receive in the future. Tiresias, Optimus, Gandiva, and AntMan all operate under this separation — even the scale-adaptive ones make allocation decisions based on predicted throughput curves without considering that jobs could re-tune their batch sizes and learning rates in response.

Pollux's architecture breaks this separation by establishing a closed feedback loop between the per-job agent and the cluster-wide scheduler. The PolluxAgent tells PolluxSched: "here is my full goodput function — for any allocation a, this is the maximum goodput I can achieve by optimizing (m, s)." The PolluxSched tells the PolluxAgent: "given everyone's goodput functions and the fairness knob, here is your new allocation a." The agent then re-optimizes (m, s) for the new a, measures new throughput data and φ_t, and updates its goodput function — closing the loop. This is not merely two optimizers running side by side; it is co-adaptation in the strict sense that each component's behavior influences the other's optimization landscape.

What makes this architecture distinctive is not any individual component — per-job profiling agents and centralized schedulers both exist in prior work — but the bidirectional information flow that enables the scheduler to reason about the consequences of its allocation decisions at the training-algorithm level. When PolluxSched evaluates whether to take GPUs from job A and give them to job B, it computes what would happen to A's batch size (the agent would reduce it), what that does to A's statistical efficiency (the PGNS model predicts the change), and what happens to A's goodput (the throughput model predicts the new iteration time). This is a level of cross-layer reasoning — from cluster topology down to stochastic gradient statistics — that no prior scheduler attempted.

The architectural innovation also manifests in prior-driven exploration. Rather than requiring users to specify resource requirements or running expensive offline profiling, Pollux starts each job with a single GPU and an optimistic prior (the model initially believes it scales perfectly), then lets the scheduler's own optimization pressure drive exploration. When PolluxSched sees a job that appears highly scalable (because the prior hasn't been disconfirmed yet), it allocates more GPUs to that job, which generates data that refines the model, which in turn informs future allocation decisions. This exploration is not a separate mechanism bolted onto the scheduler — it emerges naturally from the co-adaptive loop.

Section 5.3.2 provides evidence that the co-adaptive architecture's benefits are not trivially achievable: seeding jobs with offline-fitted throughput models (simulating perfect prior knowledge) only improves short-job completion time by 2–5%, indicating that the online fitting and co-adaptation recovers most of the information that would otherwise require expensive offline profiling. The architecture is robust to scheduling interval (Figure 8b, stable up to 2-minute intervals) and to interference (Figure 8c, the interference avoidance constraint does not degrade performance in the zero-interference case), suggesting the co-adaptive loop is not brittle to implementation details.

Innovation 4: A Tunable Fairness Mechanism Operating on Speedup Rather Than Resource Share

Cluster schedulers must balance two competing objectives: maximizing aggregate efficiency (finish jobs as quickly as possible) and ensuring fairness (no job is starved or disproportionately delayed). Prior DL schedulers have taken various approaches: Tiresias uses priority queues with service-level objectives, Optimus attempts to equalize job completion time improvements, and Themis (Mahajan et al., 2020) introduces finish-time fairness as an explicit metric and a two-level scheduling architecture to enforce it. These approaches share a common assumption: fairness is about resource quantities (equal GPU shares, equal completion time improvements) or about priorities assigned by users or operators.

Pollux's fairness mechanism operates on a fundamentally different object: speedup relative to fair-share performance. The speedup SPEEDUP_j(A_j) measures how much better a job performs under allocation A_j compared to how it would perform under an equal partition of the cluster. This is not the same as measuring resource quantity — a job that achieves 2× speedup with 2× its fair-share GPUs is operating at perfect scalability, while a job that achieves only 1.2× speedup with 2× its fair-share GPUs is using those extra resources inefficiently. The fitness function FITNESS_p, a generalized power mean over these speedups with tunable parameter p, then controls how aggressively the scheduler favors efficient resource users versus equalizing speedups.

The intellectual advance here is decoupling the fairness mechanism from resource allocation and attaching it to outcomes. When p = 1 (arithmetic mean), the scheduler maximizes total goodput — it gives GPUs to whichever jobs can use them most efficiently, potentially starving poorly-scaling jobs. When p = −∞ (min), the scheduler maximizes the minimum speedup — it equalizes performance across jobs regardless of total cluster goodput, akin to max-min fairness but defined on benefit rather than allocation. Intermediate values like p = −1 (harmonic mean, the default) balance these extremes. This single-parameter interpolation between pure efficiency and pure fairness is both theoretically elegant and practically useful: a cluster operator can set p based on organizational priorities without needing to understand per-job scalability characteristics.

The evidence that this mechanism produces meaningful fairness improvements comes from Figure 7. Pollux with p = −1 achieves finish-time fairness (ρ) where 99% of jobs have ρ < 2, compared to long tails of ρ > 4 for Tiresias+TunedJobs and Pollux with p = 1. The max-ρ improvements are 1.5× and 5.4× over Tiresias and Optimus, respectively. Crucially, Pollux achieves this fairness without sacrificing aggregate performance — p = −1 actually improves average job completion time relative to p = 1 in the paper's workload (Table 2), because preventing a few highly-scalable long jobs from monopolizing GPUs allows many shorter jobs to finish sooner, reducing the mean. This is a non-obvious interaction that a resource-quantity-based fairness mechanism would not capture: fairness in outcome space (speedup) indirectly optimizes for the metric users actually care about (time-to-completion) in ways that fairness in allocation space does not.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper constructs a synthetic workload derived from the Microsoft cluster traces (Jeon et al., 2019). Specifically, the authors randomly sampled 160 jobs from the busiest 8-hour range (hours 3–10) of the public deep learning cluster traces. Each job in the trace contains information on submission time, number of GPUs, and duration, but does not include details about model architectures or datasets. To fill this gap, the authors categorize each trace job by total GPU-time (Small: 0–1 GPU-hours, 36% of jobs; Medium: 1–10 GPU-hours, 20%; Large: 10–100 GPU-hours, 6%; XLarge: 100–1000 GPU-hours, 2%) and assign a representative training task from Table 1 matching the same category. The workload thus consists of a heterogeneous mix of six model types (ResNet-50/ImageNet, YOLOv3/PASCAL-VOC, DeepSpeech2/CMU-ARCTIC, BERT/SQuAD, ResNet-18/CIFAR-10, NeuMF/MovieLens) with realistic submission patterns and duration distributions.

• Base model(s). The evaluation uses six distinct model architectures spanning major DL domains: ResNet-50 on ImageNet (image classification, SGD with AdaScale LR scaling), YOLOv3 on PASCAL-VOC (object detection, SGD with AdaScale), DeepSpeech2 on CMU-ARCTIC (speech recognition, SGD with AdaScale), BERT fine-tuning on SQuAD (question answering, AdamW with square-root LR scaling), ResNet-18 on CIFAR-10 (image classification, SGD with AdaScale), and NeuMF on MovieLens (recommendation, Adam with square-root LR scaling). The diversity of optimizers (SGD, Adam, AdamW), LR scaling rules (AdaScale, square-root), and model architectures is deliberate — it demonstrates that Pollux's goodput formulation and PGNS estimation work across fundamentally different training regimes, not just SGD-based classifiers. Each job is trained to a target validation metric (e.g., 75% top-1 accuracy for ImageNet, 84% mAP for YOLOv3, 88% F1 for BERT, 69% hit rate for NeuMF).

• Metrics. The primary metric is job completion time (JCT) — wall-clock time from job submission to when the job reaches its target validation metric. The paper reports average JCT, 99th percentile (tail) JCT, and makespan (time from first job submission to last job completion). For fairness evaluation, the paper uses finish-time fairness (ρ) from Mahajan et al. (2020), defined as the ratio of a job's JCT when running on shared resources to its JCT when running in an isolated, equally-partitioned cluster. A job with ρ < 1 has been treated better-than-fair; ρ > 1 indicates worse-than-fair treatment. For the cloud auto-scaling experiment, the metric is training cost (total GPU-time) adjusted for completion time.

• Baselines. The paper compares Pollux against two state-of-the-art DL schedulers: Tiresias (Gu et al., 2019), a non-scale-adaptive scheduler that uses two priority queues with service-level objectives and requires users to specify fixed GPU counts, and Optimus (Peng et al., 2018), a scale-adaptive scheduler that learns throughput models and dynamically re-allocates GPUs but does not adapt batch sizes. To account for differences in throughput modeling (Optimus was designed for parameter-server architectures while Pollux uses all-reduce), the authors implement an enhanced baseline called Optimus+Oracle that uses Pollux's own throughput model (Section 3.2) and is provided with the exact number of training iterations until convergence for each job (hence "oracle"). This baseline represents an idealized version of Optimus with perfect convergence information and Pollux-quality throughput predictions, making it a stronger comparison point than the original Optimus. Both Tiresias and Optimus+Oracle are evaluated under two configuration scenarios: TunedJobs, where every job is manually configured with a well-chosen GPU count and batch size (described below), and the default realistic scenario where jobs use the GPU count from the Microsoft trace and batch size M₀ × number_of_GPUs.

• Manually-tuned job configurations for baselines. To avoid unfairly penalizing baseline schedulers that cannot adapt training configurations, the paper constructs a set of "well-tuned" configurations that assume expert users. For each model in Table 1, the authors measured iteration times across a range of GPU allocations and batch sizes, and fully trained each model at different batch sizes. A GPU count is considered valid if using the optimal batch size for that GPU count achieves 50–80% of ideal (perfectly linear) scalability versus the optimal batch size on a single GPU. For each job in the synthetic workload, the number of GPUs and batch size are randomly selected from the job's valid configurations. The paper emphasizes that "less than 50% of the ideal scalability would lead to under-utilization of resources, and more than 80% of the ideal scalability means the job can still utilize more GPUs efficiently." This is explicitly acknowledged as unrealistically biased in favor of the baselines: it assumes "users are highly rational and knowledgeable about the scalability of the models they are training." The Tesla experiments using realistic configurations (GPU count from trace, batch size = M₀ × number_of_GPUs) represent how the authors expect most users to initially configure jobs without expert assistance.

• Generation budget / compute accounting. Test-time compute is not the central axis of comparison in this systems paper — the resource is GPU allocation over time. All comparisons are made on the same 64-GPU cluster (16 nodes, 4 GPUs per node), meaning all schedulers have access to identical hardware. Job completion time is the integrated outcome of how each scheduler allocates GPUs to jobs over the workload duration. The key accounting difference between schedulers is that Pollux can dynamically change per-job GPU allocations and batch sizes, Optimus+Oracle can only change GPU allocations (batch sizes are fixed), and Tiresias fixes both. In the workload, jobs are categorized by total GPU-hours (Small: 0–1, Medium: 1–10, Large: 10–100, XLarge: 100–1000), representing the computational "budget" each job requires to complete.

• Cross-validation / statistical protocol. For testbed experiments (Section 5.2), each scheduler configuration is run once on the 160-job synthetic workload on the physical 64-GPU cluster. For simulator experiments (Section 5.3), each experiment is repeated on 8 different workload traces generated using the same duration, number of jobs, and job size distributions, with results reported as averages across all 8 traces with 95% confidence intervals (shown as error bars in Figure 8). The simulator itself is constructed by profiling each model under 146 different GPU allocation+placement configurations in the 64-GPU cluster, measuring iteration times across batch sizes up to GPU memory limits, and measuring (pre-conditioned) gradient noise scale across epochs for a range of batch sizes — effectively creating a high-fidelity replay engine validated against physical testbed results (the simulator achieves similar factors of improvement as the testbed, with Pollux reducing average JCT by 48% and 32% over Optimus+Oracle+TunedJobs and Tiresias+TunedJobs respectively, versus 50% and 37% in the physical testbed).

Main Quantitative Results

Testbed Macrobenchmark: Pollux vs. Baseline Schedulers with Well-Tuned Jobs (Table 2, Figure 5)

The headline result is that Pollux (p = −1) reduces average job completion time by 50% relative to Optimus+Oracle+TunedJobs and 37% relative to Tiresias+TunedJobs, even when both baselines are provided with manually-tuned, expert-level GPU and batch size configurations for every job. Specifically, from Table 2: Pollux achieves 0.76h average JCT, 11h tail JCT, and 16h makespan, compared to Optimus+Oracle+TunedJobs at 1.5h average JCT (1.97× worse), 15h tail JCT (1.36× worse), and 20h makespan (1.25× worse), and Tiresias+TunedJobs at 1.2h average JCT (1.58× worse), 15h tail JCT (1.36× worse), and 24h makespan (1.5× worse). The 27% improvement in tail JCT over both baselines indicates that Pollux's benefits are not concentrated only on easy-to-schedule jobs but extend to the most challenging cases.

The mechanism behind these improvements is visible in Figure 5, which tracks cluster-wide GPU allocation and average statistical efficiency over time during the synthetic workload execution. During periods of low cluster contention, Pollux allocates more GPUs and uses larger batch sizes to boost throughput, accepting lower statistical efficiency because the throughput gain outweighs the efficiency loss — the goodput calculation makes this tradeoff explicit and optimizable. During periods of high cluster contention (many jobs competing), Pollux reduces per-job allocations and uses smaller batch sizes to increase statistical efficiency — getting more training progress from each scarce GPU. The paper labels these two regimes explicitly: point (A) shows high-GPU, low-efficiency operation during low contention, while point (B) shows low-GPU, high-efficiency operation during high contention. Baseline schedulers cannot make this tradeoff because they either fix both GPU count and batch size (Tiresias) or fix batch size while adapting GPU count (Optimus) — they miss the dimension of statistical efficiency entirely.

A revealing detail in Figure 5: Tiresias+TunedJobs shows a dip in allocated GPUs between hours 16 and 20, which the paper attributes to "a 24-GPU job blocking a 48-GPU job from running" — a fragmentation problem that Pollux's dynamic re-allocation avoids by continuously repacking jobs onto available GPUs.

Testbed Macrobenchmark: Pollux vs. Baselines with Realistic Job Configurations (Table 2)

When jobs are configured as the authors expect typical users would — using the GPU count exactly as specified in the Microsoft trace and batch size M₀ × number_of_GPUs — the gap widens dramatically. Pollux achieves 72% and 73% shorter average JCT, 50% and 56% shorter tail JCT, and 43% and 48% shorter makespan compared to Optimus+Oracle and Tiresias respectively. The realistic-configuration baselines perform substantially worse than their tuned counterparts: Optimus+Oracle drops from 1.5h to 2.7h average JCT (1.8× degradation), and Tiresias drops from 1.2h to 2.8h (2.3× degradation). Critically, Optimus+Oracle with realistic configurations performs only marginally better than Tiresias despite its ability to dynamically increase GPU allocations — the paper explains that Optimus+Oracle "only slightly outperforms Tiresias because it does not also increase the batch size to better utilize those additional GPUs." This is direct evidence for the paper's central claim that resource elasticity without training re-optimization is insufficient.

Co-Adaptation Over Time: Qualitative Evidence (Figure 6)

Figure 6 provides a detailed trace of how Pollux co-adapts one ImageNet job (LEFT) and two YOLOv3 jobs (RIGHT) as cluster load changes. The four rows show: (1) number of active jobs sharing the cluster, (2) GPUs allocated to the target job, (3) batch size in images, and (4) statistical efficiency as a percentage.

For the ImageNet job: During an initial low-contention period (A), the job receives many GPUs, uses a large batch size (~4096 images), and operates at roughly 60% statistical efficiency. When cluster contention increases (B), the job's GPU allocation drops, its batch size decreases to ~1024 images, and statistical efficiency rises to ~90%. When contention subsides (C), the job again receives more GPUs and increases batch size — but notably, the per-GPU batch size is much higher than in the first low-contention period because the job has entered its final, high-statistical-efficiency phase of training (φ_t has increased, making large batch sizes more efficient). This demonstrates the co-adaptation of both allocation and training configuration in response to both cluster state and training progress.

For the two YOLOv3 jobs: The figure shows them trading off resources as cluster contention fluctuates, with corresponding adjustments to batch size and statistical efficiency. When one YOLOv3 job receives more GPUs (around t=6), its batch size increases and efficiency decreases; when it loses GPUs (around t=9–11), the reverse occurs.

Effect of the Fairness Knob (Table 2)

Pollux with three values of p reveals a non-monotonic relationship between fairness and performance. With p = 1 (arithmetic mean, no fairness), average JCT is 0.83h, tail JCT is 10h, and makespan is 16h. With p = −1 (harmonic mean, moderate fairness), average JCT improves to 0.76h (8.4% better), but tail JCT degrades to 11h (10% worse). With p = −10 (strong fairness), average JCT degrades to 0.84h (10.5% worse than p = −1), tail JCT worsens to 12h (20% worse than p = 1), and makespan increases to 18h.

The paper explains the counterintuitive improvement in average JCT from adding fairness: "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)." Moderate fairness prevents a few highly-scalable long jobs from monopolizing GPUs, allowing many shorter jobs to complete faster, which reduces the mean despite (slightly) delaying the longest jobs. Further increasing fairness (p = −10) degrades both average and tail because the scheduler over-prioritizes equalizing speedups at the cost of excessive re-allocations.

Scheduling Fairness: Finish-Time Fairness (Figure 7)

Figure 7 presents the CDF of finish-time fairness (ρ) for Pollux with three p values, Optimus+Oracle+TunedJobs, and Tiresias+TunedJobs. The key finding: Pollux with p = −1 provides the best fairness, with 99% of jobs achieving ρ < 2, compared to long tails of ρ > 4 for Tiresias+TunedJobs and Pollux with p = 1. Optimus+Oracle+TunedJobs achieves intermediate fairness, which the paper attributes to its allocation algorithm that attempts to equalize JCT improvement for each job.

The max-ρ improvements are 1.5× over Tiresias and 5.4× over Optimus. Pollux with p = −10 shows slightly worse fairness than p = −1 overall, caused by "PolluxSched incurring a larger number of re-allocations due to ignoring the cost in favor of equalizing speedups at all times." The paper contextualizes these results by noting that the ρ curves for Tiresias and Optimus are consistent with those reported by Mahajan et al. (2020) for different workloads, and that the ρ range for Pollux with p = −1 is similar to the range reported for Themis — suggesting Pollux achieves comparable fairness to a dedicated fairness-oriented scheduler while simultaneously improving efficiency.

System Overheads (Section 5.2)

The paper quantifies Pollux's runtime costs: during each 60-second scheduling interval, PolluxSched spends an average of 1 second on 1 vCPU computing cluster allocations via population-based search. Each job is re-allocated resources once every 7 minutes on average, incurring an average 8% run-time overhead from checkpoint-restart operations. Each PolluxAgent fits its throughput model parameters every 30 seconds, taking 0.2 seconds on average. Finding the optimal per-GPU batch size and gradient accumulation steps by optimizing GOODPUT takes 0.4 milliseconds on average. These overheads are small relative to the 37–73% improvements in JCT, confirming that the co-adaptive optimization loop is computationally lightweight enough to be practical.

Sensitivity to Workload Intensity (Figure 8a)

Using the simulator, the paper evaluates Pollux, Optimus+Oracle+TunedJobs, and Tiresias+TunedJobs under varying job submission rates (from 0.5× to 2.0× the baseline rate). All three schedulers suffer longer average JCT and makespan as load increases — this is expected since more jobs compete for fixed resources. Across all load levels, Pollux maintains similar relative improvements over the baselines, with the average JCT gap remaining roughly constant in proportional terms. This indicates that Pollux's co-adaptive strategy is not specific to a particular load level and would generalize to clusters with different utilization profiles.

Sensitivity to Scheduling Interval (Figure 8b)

Pollux's performance as a function of the scheduling interval (the period at which PolluxSched re-optimizes allocations) shows that performance is stable for intervals up to 2 minutes, then degrades. At a 60-second interval (the default), average JCT is normalized to 1.0. At 120 seconds, average JCT is approximately 1.05 (5% degradation). At 240 seconds, average JCT is approximately 1.12 (12% degradation). At 300 seconds (5 minutes), the degradation is more pronounced. The paper decomposes this degradation: "queuing contributed to roughly half of the performance degradation observed, indicating that Pollux still benefits from a relatively frequent adjustment of resource allocations." Even with 2–4 minute intervals, Pollux substantially outperforms the baselines (which have no dynamic re-allocation capability comparable to Pollux's), but very long intervals allow inefficient allocations to persist.

Sensitivity to Interference and Interference Avoidance (Figure 8c)

To evaluate the impact of PolluxSched's constraint that at most one distributed job can occupy each node, the simulator artificially injects various degrees of slowdown (0% to 50%) for distributed jobs that share a node without the constraint. Three configurations are compared: Pollux with interference avoidance enabled, Pollux without interference avoidance, and an ideal scenario with zero interference.

With interference avoidance enabled, average JCT is unaffected by even severe (50%) artificial slowdowns, because network contention is completely prevented — distributed jobs never share nodes. Without interference avoidance, the average JCT is 1.4× longer when interference slowdown is 50%, showing that unmanaged interference can substantially degrade cluster performance. In the ideal scenario of zero natural interference, PolluxSched performs similarly with or without interference avoidance, indicating that the constraint does not overly restrict the scheduler's ability to find efficient allocations — the optimization can work around the constraint without significant degradation. This is an important robustness result: the interference avoidance constraint is a safety measure that costs little when interference is absent but prevents large degradations when interference is present.

Impact of Prior-Driven Exploration (Section 5.3.2)

To evaluate the cost of Pollux's exploration strategy (starting with optimistic priors and learning throughput models online), the simulator compares default Pollux against an idealized variant where jobs are "seeded" with throughput models fitted offline from historical data. The result: "minor (2–5%) reduction in JCT for short jobs like CIFAR10, but no significant change for longer running jobs." This indicates that the prior-driven exploration strategy recovers throughput information quickly enough that even short jobs (CIFAR-10, categorized as Small with 0–1 GPU-hours) are not substantially penalized by learning from scratch, and long-running jobs have ample time to refine their models during training. The 2–5% overhead for short jobs is small relative to the overall 37–73% improvement over baselines.

Cloud Auto-Scaling Application (Figure 9, Section 5.4.1)

The paper presents a preliminary experiment on using Pollux's goodput function for cloud auto-scaling, comparing against the throughput-based auto-scaler proposed by Or et al. (2020). The auto-scaling policy scales up the number of nodes whenever the goodput per node exceeds a fraction U = 2/3 of the predicted ideal goodput (assuming perfect scalability), and scales to a number of nodes such that the predicted goodput is approximately L = 1/2 of the predicted ideal.

Figure 9a shows the number of nodes over time for ImageNet training. The throughput-based auto-scaler (Or et al.) quickly scales to many nodes (approximately 8–10) early in training and maintains that level throughout, because system throughput does not change with training progress. The goodput-based auto-scaler (Pollux) starts with a small number of nodes (~2) and gradually increases to approximately 8 nodes by the end of training, because the PGNS φ_t increases during training, making larger batch sizes more statistically efficient later on.

Figure 9b shows that Pollux maintains high statistical efficiency (~90–100% for most of training), while the throughput-based approach operates at much lower efficiency (~40–60%) early in training when large batch sizes are statistically wasteful. The result: Pollux trains ImageNet with 25% cheaper cost, with only a 6% longer completion time compared to throughput-based auto-scaling. This is a meaningful cost reduction at modest completion-time penalty — the 6% extra wall-clock time is the price of waiting until the model is statistically ready to efficiently use the larger resource pool.

Hyper-Parameter Optimization Application (Table 3, Section 5.4.2)

In a hyper-parameter optimization (HPO) experiment using Tree-structured Parzen Estimator (TPE) to tune a ResNet-18 on CIFAR-10 (searching over learning rate, annealing, momentum, weight decay, and network width), Pollux completes 100 trials (4 concurrent) on a 2-node DGX A100 cluster (16 A100 GPUs total) with 30% faster average JCT and 40% shorter makespan compared to a baseline that assigns a static 4-GPU-per-trial allocation with fixed per-GPU batch size. The achieved accuracy of the top 5 trials is essentially identical: Pollux at 95.4 ± 0.2% versus baseline at 95.5 ± 0.3%, confirming that Pollux's adaptive resource re-allocation and batch size tuning does not sacrifice final model quality. The baseline is 34 minutes average JCT and 14h makespan; Pollux achieves 25 minutes average JCT and 10h makespan.

Ablation Studies and Robustness Checks

System throughput model fitting accuracy (Section 3.2, Figure 3): The 7-parameter throughput model (Equation 11) is validated by fitting it to "a diverse set of GPU placements and batch sizes in a 64-GPU cluster." Across all six DL tasks, the average error of the fitted model was at most 10%, indicating that the linear assumptions for T_grad and T_sync, combined with the soft-overlap parameter γ, are sufficient to represent observed throughput measurements across heterogeneous models and hardware configurations. Figure 3 provides qualitative evidence: the fitted curves closely track measured data points across 1–64 GPU allocations and batch sizes spanning an order of magnitude. The model captures sharp increases in iteration time at the inter-node boundary (4 GPUs) for models like YOLOv3 and BERT, as well as the benefit of gradient accumulation for those models.

Statistical efficiency model validation (Figure 2): The PGNS-based EFFICIENCY function is validated by comparing training runs at three different batch sizes (baseline M₀, intermediate, and maximum) for all six model types. The top row shows validation metrics versus "statistical epochs" — a normalized training progress measure that should align curves if the efficiency model is correct. For ImageNet, YOLOv3, CIFAR-10, and Recommendation, the curves largely overlap at comparable statistical epochs. For DeepSpeech2 and BERT, there are larger differences (±4% for DeepSpeech2), which the paper acknowledges but notes are "within the plateau of high-quality models expected from large-batch training." The bottom row directly validates the predictive capability: φ_t estimated at one batch size is used to predict EFFICIENCY at other batch sizes (log-scaled range), and the predicted values closely match measured values across all models. This is critical because the entire PolluxSched optimization relies on the ability to predict goodput at candidate allocations without running them.

Plug-in LR scaling rule generality: The paper does not ablate specific LR scaling rules in isolation, but the evaluation's design implicitly validates the plug-in interface by using two fundamentally different rules: AdaScale for SGD-based training (ImageNet, YOLOv3, CIFAR-10, DeepSpeech2) and square-root scaling for Adam/AdamW (BERT, NeuMF). The fact that Pollux achieves consistent improvements across both categories without per-rule tuning suggests the goodput framework is agnostic to the specific scaling rule, as claimed.

Effect of the fairness knob p on completion time fairness (Figure 7, Table 2): This is an ablation on the scheduling objective. With p = 1 (pure efficiency, arithmetic mean), fairness is poor — a long tail of jobs with ρ > 4, similar to Tiresias+TunedJobs. With p = −1 (harmonic mean), fairness improves substantially — 99% of jobs achieve ρ < 2 — while average JCT actually improves (0.83h → 0.76h). With p = −10 (strong fairness), fairness slightly degrades relative to p = −1 (more jobs with ρ > 2) and average JCT worsens to 0.84h. The non-monotonicity in fairness is explained by excessive re-allocations at p = −10: the scheduler re-allocates GPUs more aggressively to equalize speedups, but the re-allocation overhead negates the fairness benefit.

Interference avoidance constraint (Figure 8c): Ablating the constraint shows it is a low-cost safety mechanism. Without interference avoidance, average JCT is 1.4× longer at 50% interference — confirming that unmanaged interference can cause severe degradation. With the constraint, performance is unaffected by interference — confirming the constraint is effective. In the zero-interference scenario, the constraint imposes no measurable performance penalty — confirming it does not over-restrict the scheduler.

Prior-driven exploration vs. offline fitting (Section 5.3.2): Ablating Pollux's online exploration strategy against idealized offline-fitted models shows only 2–5% JCT reduction for short jobs and no significant change for long jobs. This validates that the simple prior strategy (optimistic scaling, maximum-doubling rule) is sufficient to explore the allocation space efficiently.

Simulator fidelity (Section 5.3): The simulator is validated against the physical testbed results. In the testbed, Pollux with p = −1 achieves 50% and 37% shorter average JCT compared to Optimus+Oracle+TunedJobs and Tiresias+TunedJobs respectively. In the simulator, the corresponding improvements are 48% and 32%. The close agreement confirms that the simulator's profiling-based replay approach (interpolating measured throughput and PGNS from 146 GPU configurations per model) captures the relevant system and statistical behaviors.

Re-allocation penalty REALLOC_FACTORj(δ) (Section 4.2): The paper does not provide a dedicated ablation varying δ, but reports that with δ = 30s, jobs are re-allocated once every 7 minutes on average, resulting in 8% overhead. This suggests the penalty mechanism effectively limits re-allocation frequency without a separate quantitative ablation. A more thorough analysis would have shown JCT as a function of δ or the re-allocation frequency directly.

Critical Assessment

The experiments provide strong and mutually-reinforcing evidence for the paper's central claims, but the evaluation has several important limitations that qualify the scope of those claims.

Claim: Pollux reduces average JCT by 37–50% relative to state-of-the-art schedulers even when they are provided with ideal resource and training configurations.

The testbed experiments (Table 2) unambiguously support this claim for the specific workload, cluster, and model mix tested. The 50% reduction over Optimus+Oracle+TunedJobs is particularly convincing because the baseline is unrealistically strong — it uses Pollux's own throughput model (removing any advantage from better throughput prediction) and has oracle knowledge of each job's training duration (removing any advantage from convergence prediction). The 37% reduction over Tiresias+TunedJobs similarly benefits from expert-level manual configuration. The realism of the workload construction, derived from production traces and covering heterogeneous model types, strengthens the claim's external validity.

However, the supporting evidence is specific to the workload mix and cluster size tested. The 160-job workload, while derived from real traces, represents only one 8-hour slice of one cluster. The job size distribution (36% Small, 20% Medium, 6% Large, 2% XLarge) may not be representative of other production clusters. The 64-GPU, 16-node homogeneous cluster with T4 GPUs is a single hardware configuration — Pollux's behavior on larger clusters (100s–1000s of GPUs), heterogeneous hardware (different GPU types, TPUs), or different network topologies is untested. The paper acknowledges that the throughput model's linear assumptions "may diverge from reality for specialized hardware, sophisticated synchronization algorithms, different parallelization strategies, at larger scales, or hidden resource contention" (Section 3.2), but these scenarios are not evaluated. A cluster with 1000+ GPUs might exhibit fundamentally different contention patterns, straggler effects, or communication bottlenecks that Pollux's models do not capture.

Claim: Pollux's co-adaptation of batch size and resource allocation is what enables these improvements, and scale-adaptive schedulers that only adjust GPU count (like Optimus) inherently leave performance on the table.

The evidence for this claim comes from the gap between Optimus+Oracle+TunedJobs (which adapts GPU count with fixed batch sizes) and Pollux (which adapts both). The 50% JCT reduction is substantial and the qualitative behavior in Figure 5 and Figure 6 — where Pollux shifts between high-throughput/low-efficiency and low-throughput/high-efficiency modes based on cluster contention — directly illustrates the claimed mechanism.

A missing experiment that would strengthen this claim is: what if Optimus were enhanced with a heuristic batch-size scaling rule, such as linearly scaling batch size with GPU count? This would not be as sophisticated as Pollux's goodput optimization but would test whether the specific mechanism (PGNS-based efficiency modeling) is necessary, or whether any batch-size adaptation yields most of the benefit. The realistic-configuration results (where Optimus+Oracle performs only marginally better than Tiresias because it doesn't increase batch size) partially address this — they show that no batch size adaptation is clearly harmful — but don't distinguish between Pollux's principled adaptation and a simpler rule.

Claim: Pollux promotes fairness while improving performance, based on a more meaningful measure of useful job progress (speedup relative to fair-share goodput).

The finish-time fairness analysis (Figure 7) convincingly shows Pollux with p = −1 achieves substantially better fairness than Tiresias and similar fairness to the Themis system's reported range. The max-ρ improvements of 1.5× and 5.4× are well-supported. The non-monotonic relationship where moderate fairness (p = −1) improves average JCT relative to no fairness (p = 1) is an interesting finding that could be workload-dependent — in workloads with very different job size distributions, the benign interaction between fairness and average JCT might not hold.

A missing analysis is sensitivity to the choice of p across different workload compositions. The paper evaluates three p values on one workload, but doesn't explore whether p = −1 would remain a good default for substantially different job mixes (e.g., all large jobs, all small jobs, different scalability distributions). The statement that "a cluster operator may select a suitable value" suggests that p should be tuned per-deployment, but no guidance is given on how to select it.

Claim: Goodput-driven auto-scaling based on Pollux can potentially reduce the cost of training large models by 25%.

The cloud auto-scaling result (Figure 9) is the least thoroughly evaluated claim, as the paper itself acknowledges: "a full design of an auto-scaling system based on goodput may be the subject of future work" (Section 5.4.1). The evidence is a single experiment on ImageNet training comparing Pollux's goodput-based scaling against the throughput-based approach of Or et al. The 25% cost reduction with 6% completion time increase is promising, but this is one model, one dataset, one auto-scaling policy (U = 2/3, L = 1/2 with specific scaling logic), and one comparison point. The sensitivity to the auto-scaling thresholds U and L is not explored, nor is the comparison to other auto-scaling strategies or to fixed-resource training at different scales.

Claim: The PGNS-based statistical efficiency model is accurate enough to drive scheduling decisions across heterogeneous model types.

Figure 2 provides validation across six model types, showing predicted and measured EFFICIENCY align well across batch sizes. The validation metric curves (top row) show some divergence for DeepSpeech2 (±4% relative difference in best validation metric) and BERT (visible differences early in training), which the paper acknowledges. The claim is that these differences are "within the plateau of high-quality models expected from large-batch training" — but this is an assertion, not a measurement. A stricter validation would quantify the sensitivity of final model quality to the specific batch size trajectory chosen by Pollux versus a ground-truth optimal trajectory. If Pollux occasionally selects slightly suboptimal batch sizes due to PGNS estimation error, does this accumulate into meaningful differences in final accuracy or training time? The evaluation shows that Pollux achieves the target validation metrics (all jobs complete successfully), but doesn't compare Pollux's chosen batch size trajectories against retrospectively optimal ones.

Simulator-based experiments and statistical rigor. The simulator experiments (Section 5.3) use 8 workload traces with 95% confidence intervals, which is appropriate for the scale of cluster scheduling experiments. However, the testbed experiments (Section 5.2) — which produce the headline 37–50% numbers — appear to be single runs per configuration. Cluster scheduling experiments on a 160-job workload involve substantial stochasticity (job submission order, exact timing of scheduling decisions, checkpoint-restart timing overlap), and single-run results may not capture variance. The paper does not report confidence intervals for the testbed experiments, making it difficult to assess whether the differences between, say, Pollux with p = −1 (0.76h) and p = 1 (0.83h) are statistically significant or within run-to-run noise.

The manual tuning baseline, while explicitly biased toward baselines, may exaggerate the comparison in both directions. For jobs where the manual configuration happens to be near-optimal, the baseline performs well and the gap to Pollux represents the true benefit of co-adaptation. But for jobs where the manual configuration is suboptimal even by the 50–80% scalability criterion, Pollux's advantage partly reflects the difficulty of manual tuning rather than the inherent superiority of goodput-driven scheduling. The 72–73% improvement under realistic configurations suggests that poor manual tuning is common in practice, which strengthens the practical case for Pollux but doesn't isolate what fraction of the benefit comes from better resource allocation versus better batch size selection versus better learning rate adaptation.

Missing comparisons. The paper does not compare against several relevant systems: Gavel (Narayanan et al., 2020), which addresses heterogeneous accelerators — Pollux's modular throughput model is claimed to be extendable to heterogeneity but this is not demonstrated; AntMan (Xiao et al., 2020), which uses dynamic scaling and fine-grained GPU sharing — Pollux does not use GPU sharing and the interaction between Pollux's scheduler and AntMan-style fine-grained sharing is unexplored; and Themis (Mahajan et al., 2020), which is discussed qualitatively but not implemented for comparison despite finish-time fairness being a primary evaluation metric. The paper notes Themis is "not available for direct comparison" but compares Pollux's ρ range to Themis's reported range — this is suggestive but not a controlled comparison on the same workload.

Scale limitations. All experiments are on a 64-GPU cluster. Modern production DL clusters can be 100–1000× larger (thousands to tens of thousands of GPUs). At such scales, the centralized PolluxSched architecture — receiving updates from all agents, running population-based search, and applying allocations within 60 seconds — may face scalability challenges not visible at 64 GPUs. The paper does not discuss how PolluxSched's computational cost scales with cluster size or number of jobs, and the reported 1 second per scheduling interval is for the 160-job workload on 64 GPUs.

6. Limitations and Trade-offs

The Throughput Model Assumes Synchronous Data-Parallel Training with All-Reduce and Linear Scaling

The assumption or constraint. Pollux's system throughput model (Equation 11, Section 3.2) is architected specifically for synchronous data-parallel training using all-reduce gradient synchronization. The model decomposes iteration time into T_grad (linear in per-GPU batch size), T_sync (linear in GPU count, with separate parameters for intra-node vs. inter-node communication), and a soft-overlap parameter γ combining them. The paper is explicit about the scope of this model in Section 3.2:

"The simple linear assumptions made in Eqn. 11, although sufficiently accurate for the settings we tested, may diverge from reality for specialized hardware [33], sophisticated synchronization algorithms [7, 65, 72], different parallelization strategies [28, 47, 58, 59], at larger scales [6, 68], or hidden resource contention not related to network used for gradient synchronization."

The paper claims the goodput formulation is modular and that "different equations for THROUGHPUT may be easily plugged in" (Section 3.2), but this modularity is asserted, not demonstrated. No experiments show Pollux operating with model parallelism, pipeline parallelism, parameter-server architectures, asynchronous SGD, or hybrid parallelism strategies — all of which are common in large-scale production training.

The consequence. A practitioner deploying Pollux on a cluster where jobs use model parallelism (e.g., Megatron-LM for large language models), pipeline parallelism (e.g., GPipe, PipeDream), or parameter-server architectures (common in earlier TensorFlow deployments) cannot rely on the reported 37–73% JCT improvements. The throughput model would produce incorrect predictions for these jobs, and the PolluxSched's allocation decisions — which depend on accurate goodput estimates — would be based on systematically wrong information. For example, model-parallel jobs exhibit fundamentally different scaling behavior: adding GPUs may reduce per-GPU memory pressure rather than reducing per-GPU computation, and synchronization patterns involve layer-wise communication rather than gradient all-reduce. The linear-in-batch-size and linear-in-GPU-count assumptions would not capture these dynamics. More subtly, the interference avoidance constraint in PolluxSched — which disallows multiple distributed jobs from sharing a node — assumes all-reduce communication patterns and may be either unnecessarily restrictive or insufficiently protective for jobs using other parallelism strategies with different network utilization profiles.

What evidence exists in the paper. The paper provides no experimental evidence with non-data-parallel training. All six model types in Table 1 (ResNet-50, YOLOv3, DeepSpeech2, BERT fine-tuning, ResNet-18, NeuMF) are trained with synchronous data-parallel all-reduce using PyTorch with NCCL. The 10% average fitting error reported for the throughput model (Section 3.2) is measured exclusively on these data-parallel configurations. The claim that the model is modular and extensible is purely architectural — it is not validated by plugging in a different throughput model and showing that PolluxSched's optimization and PolluxAgent's tuning still produce the claimed benefits.

Mitigation status. The paper acknowledges this as a scope limitation but does not mitigate it. The suggestion that different throughput models "may be easily plugged in" is forward-looking design guidance, not a validated capability. A practitioner would need to develop and validate a throughput model for their specific parallelism strategy, and there is no evidence about how Pollux's co-adaptive loop would behave with a model of different parametric form — for instance, whether the prior-driven exploration strategy (which assumes monotonic throughput scaling with GPU count) would still guide effective exploration for pipeline-parallel jobs where throughput is non-monotonic in the number of pipeline stages.

---

The Statistical Efficiency Model Depends on a Plug-In Learning Rate Scaler That Users Must Provide, and Its Accuracy Varies Across Tasks

The assumption or constraint. Pollux's goodput formulation critically depends on the SCALE_LR plug-in function that adjusts the learning rate when the batch size changes. The paper states this interface is flexible — AdaScale, square-root scaling, linear scaling, or LEGW can be implemented — but it fundamentally assumes that an appropriate LR scaling rule exists for the user's model and optimizer, that the user implements it correctly, and that this rule maintains acceptable model quality across the range of batch sizes Pollux might select. The paper acknowledges that LR scaling rules can "break down before the statistical efficiency decreases, which degrades the final model quality" (Section 3.1) and addresses this with a user-defined maximum batch size limit, but this shifts the burden to the user: they must know (or discover through experimentation) the batch size at which their chosen LR scaling rule fails.

The PGNS-based efficiency model (Equation 6) is derived from theoretical properties of pre-conditioned SGD and validated in Figure 2 by showing that validation curves across different batch sizes largely overlap when training progress is measured in statistical epochs. However, this validation does not isolate the contribution of the LR scaling rule from the contribution of the PGNS model. If a different LR scaling rule were used, the efficiency curves might diverge — the PGNS derivation predicts how batch size affects gradient estimate quality, but the LR scaling rule determines whether the optimizer actually converges well with that batch size. These are coupled in practice but treated as independent in Pollux's architecture: the PGNS model predicts EFFICIENCY, and the LR scaler is a separate user-supplied function that Pollux calls but does not model or validate.

The consequence. A user who provides an inappropriate LR scaling rule — or who uses a model architecture / optimizer combination for which no well-studied scaling rule exists — may experience degraded final model quality even though Pollux's goodput predictions suggest the chosen batch size should be efficient. The "within the plateau of high-quality models" characterization in Section 3.1 is a post-hoc observation from the six models tested, not a guarantee. For novel architectures or training recipes, the user would need to empirically determine both the maximum batch size limit and the correct LR scaling rule before Pollux could safely operate — which partially defeats the purpose of automatic configuration, since determining these values requires exactly the kind of expert experimentation Pollux aims to eliminate.

Even for models where the scaling rule is well-established, the efficiency predictions have task-dependent accuracy. Figure 2 shows that DeepSpeech2 exhibits ±4% relative difference in best validation metric across batch sizes, compared to ±1% for the other tasks. The paper frames this as acceptable, but a 4% relative degradation in word error rate for a speech recognition system may be unacceptable in production — and Pollux provides no mechanism for the user to specify a tolerance on final model quality degradation below which Pollux should not trade efficiency for throughput.

What evidence exists in the paper. The validation in Figure 2 uses AdaScale for SGD-based models and square-root scaling for Adam/AdamW models — these are among the best-studied LR scaling rules in the literature. The paper shows that under these well-tuned rules, the PGNS efficiency model predicts observed efficiency accurately and validation curves overlap. However, there is no ablation showing Pollux's performance with different LR scaling rules on the same model (e.g., linear scaling vs. AdaScale for ResNet-50), which would reveal how sensitive the overall scheduling outcomes are to LR scaler choice. The HPO experiment (Table 3) does not vary the LR scaling rule — it searches over other hyperparameters while using the same LR scaler throughout.

Mitigation status. The paper's mitigations are partial. The plug-in interface at least separates the LR scaling concern architecturally, making it possible to swap in new rules as they are developed. The maximum batch size limit provides a safety valve. However, neither mechanism eliminates the user expertise requirement — they only make it explicit. The paper does not propose methods for automatically selecting or validating LR scaling rules, detecting when a rule is failing, or bounding the model quality degradation that Pollux's decisions might cause.

---

Difficulty Estimation for Scheduling Decisions Relies on Online Exploration That Is Inefficient for Short Jobs and Potentially Harmful Under High Cluster Load

The assumption or constraint. Pollux uses prior-driven exploration (Section 4.1) to build throughput models for each job from scratch during training. New jobs start with a single GPU and optimistic priors — the model initially assumes perfect scalability to more GPUs. PolluxSched, seeing high predicted goodput at larger allocations, is encouraged to allocate more GPUs to the unexplored job. As the job experiences larger allocations, the PolluxAgent records actual iteration times and the throughput model converges to reality. The paper reports (Section 5.3.2) that this strategy performs within 2–5% of an idealized scenario where throughput models are fitted offline before submission.

This finding, however, applies to the paper's specific workload and must be understood in context. The "2–5% reduction in JCT for short jobs like CIFAR10" is measured against Pollux's own relatively strong performance — it means that even with offline models, short jobs would only complete marginally faster. But this does not mean exploration is costless. The cost is distributed across the workload: when PolluxSched allocates extra GPUs to a new job to explore its scalability, those GPUs are unavailable to other running jobs that might use them more efficiently. In the paper's workload (36% Small jobs averaging <1 GPU-hour, 64-GPU cluster), the exploration overhead amortizes well because GPUs are relatively abundant compared to the number of tiny jobs. In a more heavily loaded cluster where GPU demand consistently exceeds supply, the opportunity cost of exploratory allocations could be substantially larger — the GPUs given to an unknown job for exploration could have instead accelerated a known-scalable job.

The consequence. A practitioner deploying Pollux in a heavily oversubscribed cluster (e.g., a cloud environment where GPU quota is always fully utilized and queues are deep) may find that prior-driven exploration causes larger-than-expected performance degradation for running jobs while new jobs are being profiled. The mechanism is: each new job submission temporarily diverts GPUs from running jobs (which have well-characterized throughput models and known goodput) to the new job (which has an optimistic, potentially incorrect model). The PolluxSched, maximizing the fitness function, will allocate some GPUs to the new job because its predicted speedup is artificially high. As the new job's throughput model converges to reality — which may require experiencing several different allocation sizes — these allocations may be revealed as inefficient, but the GPUs have already been committed for that scheduling interval. This "exploration tax" is paid by every running job whenever new jobs arrive, and its magnitude depends on (a) how far the optimistic priors are from reality, (b) the cluster load, and (c) the scheduling interval.

The paper also restricts maximum GPU allocation to at most twice the maximum a job has experienced, which limits how fast Pollux can scale up a genuinely scalable job. If a job could efficiently use 64 GPUs but has only been tested at 2 GPUs, it will take at least log₂(64/2) = 5 re-allocations (each permitting doubling) to reach 64 GPUs, even if the throughput model has already converged. This is a deliberate tradeoff to prevent over-allocation to poorly-understood jobs, but it means that highly scalable, long-running jobs may spend substantial time at sub-scale allocations while the scheduler cautiously permits scaling.

What evidence exists in the paper. The sensitivity analysis in Section 5.3.2 reports the 2–5% JCT reduction for short jobs and no significant change for long jobs when offline-fitted models replace online exploration. However, this experiment only varies the quality of the throughput model (online-fitted vs. offline-fitted) — it does not isolate and measure the exploration cost borne by other jobs. Specifically, the experiment does not compare Pollux with naive exploration against a hypothetical Pollux that knows all throughput models perfectly from the start, measuring the JCT of running jobs when new jobs arrive. The workload-level metrics (average JCT, tail JCT, makespan) aggregate across all jobs and may hide the fact that specific running jobs are slowed down by exploratory allocations to new arrivals. A job-level analysis — showing the JCT distribution stratified by submission order or showing the per-job re-allocation frequency — would reveal whether early-submitted jobs suffer disproportionately from the exploration of later-submitted jobs.

The sensitivity to workload intensity (Figure 8a) shows that Pollux maintains similar relative improvements over baselines as load increases from 0.5× to 2.0×, but this only measures aggregate metrics, not the exploration-specific overhead. At 2.0× load, the cluster is more congested and the opportunity cost of exploratory allocations is higher, but this effect is not separately measured.

Mitigation status. The paper acknowledges the exploration challenge implicitly by proposing and evaluating prior-driven exploration, but it does not treat exploration cost as a first-class limitation or propose mechanisms to reduce it. Possible mitigations — such as sharing throughput models across jobs of the same model type, using offline profiling as a seed, or adaptively reducing exploration when cluster load is high — are not explored. The maximum-doubling rule is a crude safety mechanism and may be overly conservative for long-running jobs or overly permissive for very short jobs that complete before exploration converges.

---

The Centralized PolluxSched Architecture Assumes a Homogeneous Cluster and Single-Tenant Scheduling, with Scalability and Heterogeneity Limitations

The assumption or constraint. PolluxSched is a single centralized service that collects goodput models from all PolluxAgents, runs a population-based search over the allocation space, and applies allocations by creating or terminating Kubernetes Pods (Section 4.2–4.3). This architecture assumes: (a) the cluster is homogeneous — all GPUs are identical (the testbed uses uniform g4dn.12xlarge instances with 4 NVIDIA T4 GPUs each), (b) the cluster is single-tenant for DL training — Pollux controls all GPU allocations and there is no competition from non-DL workloads, (c) the scheduling interval (60 seconds) is short enough that PolluxSched's computation and the application of allocations complete within the interval, and (d) all nodes run the same DL framework (PyTorch) with the same synchronization library (NCCL).

The paper explicitly acknowledges the homogeneity assumption: a footnote in Section 2.3 states that "Pollux's current throughput model does not consider accelerator heterogeneity" and that extending with Gavel's (Narayanan et al., 2020) metric "would allow Pollux to co-adapt for goodput in heterogeneous DL clusters." However, this extension is not implemented or evaluated. The paper does not discuss scalability of the centralized scheduler to larger clusters, nor multi-tenancy.

The consequence. At larger scales (hundreds to thousands of GPUs, hundreds to thousands of concurrent jobs), several aspects of the architecture may break. First, the computational cost of PolluxSched's search: the paper reports 1 second on 1 vCPU for the 160-job, 64-GPU scenario. The population-based search over allocation matrices has complexity that likely grows with the number of jobs and GPUs — at 1000+ GPUs and 500+ jobs, the search may not complete within a 60-second scheduling interval, or may require substantially more CPU resources. The paper does not characterize this scaling behavior.

Second, the communication pattern: every PolluxAgent reports updated models to PolluxSched every 30 seconds, and PolluxSched sends new allocations back. With 500+ agents, this is 500+ bidirectional messages per scheduling cycle, plus the Pod creation/termination overhead for every job that is re-allocated. The paper does not measure network overhead or Kubernetes API server load.

Third, heterogeneous hardware (different GPU generations, different accelerator types, different network interconnects) would require a fundamentally different throughput model — one that can predict iteration time as a function not just of GPU count and placement but also of GPU type, interconnect bandwidth, and possibly CPU/memory configuration. While the paper claims the throughput model is modular, the T_sync model (Equation 9) with its three-case structure (single GPU, single-node multi-GPU, multi-node) assumes uniform GPU types and uniform interconnects within each case. A heterogeneous cluster with mixed GPU types (e.g., some nodes with V100, some with A100) would require extending this model substantially, and the prior-driven exploration strategy — which assumes all GPUs are interchangeable — would need revision.

Fourth, multi-tenancy: if the cluster runs non-DL workloads or if multiple DL frameworks are in use, PolluxSched's assumption of full control over GPU allocation breaks down. The interference avoidance constraint (preventing distributed jobs from sharing nodes) assumes Pollux can choose which nodes each job occupies, which may conflict with Kubernetes' native scheduling or with node taints/tolerations set for other workloads.

What evidence exists in the paper. There is no evaluation of Pollux at scales beyond 64 GPUs and 160 jobs, on heterogeneous hardware, or in multi-tenant settings. The scalability experiments (Section 5.3.2) vary workload intensity but keep cluster size fixed. The scheduling interval experiment (Figure 8b) shows performance degrades at intervals longer than 2 minutes, but this is tested on the same 64-GPU cluster — the relationship between scheduling interval and cluster size is unexplored. The interference experiment (Figure 8c) simulates network contention between distributed jobs on the same node but does not introduce non-DL workloads or heterogeneous hardware.

The specific overhead numbers (1 second for PolluxSched, 0.2 seconds per PolluxAgent fitting, 8% re-allocation overhead) are all measured at the single scale tested. Extrapolating these to larger clusters is not supported by the data.

Mitigation status. The paper does not address scalability, heterogeneity, or multi-tenancy beyond the forward-looking footnote about Gavel and the architectural claim that the throughput model is modular. A practitioner managing a cluster with heterogeneous GPUs or at larger scale would need to validate (and likely modify) Pollux's architecture before deployment, with no guidance from the paper on which components would need to change or where the bottlenecks would appear.

---

The Evaluation Is Limited to a Single 64-GPU Testbed, Six Model Types, and One Workload Construction Methodology

The assumption or constraint. All empirical claims about Pollux's performance — the 37–73% JCT reductions, the fairness improvements, the auto-scaling cost savings — are derived from experiments on a single hardware configuration (16 × g4dn.12xlarge AWS instances, 64 T4 GPUs total) running a synthetic workload of 160 jobs constructed from one 8-hour slice of the Microsoft cluster traces (Jeon et al., 2019). The workload construction methodology (Section 5.1) maps each trace job to one of six model types based on GPU-hour category, randomly selecting configurations from a predetermined set of valid GPU count and batch size combinations (for the TunedJobs baseline) or using the trace's original GPU count (for realistic baselines).

This evaluation, while careful and well-documented, cannot establish that Pollux's benefits generalize to different hardware (GPU architectures, network topologies, cluster sizes), different workload compositions (different job size distributions, different model-type mixtures, different arrival patterns), or different training characteristics (models with different scalability profiles, statistical efficiency curves, or LR scaling requirements). The paper does not claim universality, but it also does not systematically analyze which properties of the workload or cluster drive Pollux's benefits, making it difficult for a practitioner to predict whether Pollux would help in their specific environment.

The consequence. A practitioner with a substantially different cluster — for instance, one with A100 GPUs (which have different compute-to-communication ratios than T4s), InfiniBand interconnects (which have different T_sync scaling than the Ethernet in g4dn instances), or a workload dominated by large language model training (where model parallelism is common and the data-parallel throughput model does not apply) — cannot reliably extrapolate from the paper's results. The paper provides no sensitivity analysis over hardware characteristics. Similarly, a cluster whose job size distribution differs markedly from the Microsoft trace (e.g., many small fine-tuning jobs and a few very large pretraining jobs) might see different fairness-efficiency tradeoffs at the same p = −1 setting, but the paper's fairness analysis (Figure 7) is presented for only one workload.

The 8-trace averaging used in the simulator experiments (Section 5.3) provides within-workload variance but does not address across-workload generalization. The 95% confidence intervals in Figure 8 show that Pollux's performance is stable across different random seeds of the same workload generation process, but all 8 traces share the same job size distribution, model type mix, and arrival pattern characteristics derived from the same 8-hour trace slice. A different trace slice (e.g., a weekend period, a different cluster, a different organization's workload) could yield different results.

What evidence exists in the paper. The experimental design includes some diversity: six model types spanning image classification, object detection, speech recognition, question answering, and recommendation, with different optimizers (SGD, Adam, AdamW) and LR scaling rules (AdaScale, square-root). The workload intensity sweep (Figure 8a, 0.5× to 2.0× submission rate) shows Pollux's relative improvements are stable across load levels. The sensitivity to scheduling interval (Figure 8b) and interference (Figure 8c) are tested. These analyses partially address generalization but remain within the same cluster, workload family, and model set.

What is missing is an analysis of which workload characteristics determine Pollux's benefit: does Pollux help more when jobs are more heterogeneous in scalability? When job sizes are more skewed? When cluster load is more variable? When models have more variable statistical efficiency curves? Without this decomposition, the paper's results are a point estimate — compelling for the tested configuration but not diagnostic for others.

Mitigation status. The paper does not claim to have solved generalization and does not propose a methodology for predicting Pollux's benefit in new environments. The workload derivation from public Microsoft traces is a strength in terms of realism and reproducibility, but the paper does not test on multiple trace sources or cluster types. The modular architecture (pluggable throughput model, pluggable LR scaler) is intended to facilitate adaptation to new settings, but the paper provides no case study or guidance on how to perform such adaptation.

---

The Re-Allocation Overhead Model Is a Heuristic That May Under-Penalize Frequent Re-Allocations for Short Jobs or Over-Penalize for Long Jobs

The assumption or constraint. PolluxSched's fitness function applies a re-allocation penalty factor REALLOC_FACTOR_j(δ) = (T_j − R_j δ) / (T_j + δ) (Section 4.2) to each job's predicted speedup before evaluating the fitness of a candidate allocation that would require re-allocating that job. This factor is designed to discourage excessive re-allocations by estimating what fraction of the job's remaining time would be productive (not spent restarting), assuming the historical re-allocation rate R_j / T_j continues. The parameter δ is an estimate of the re-allocation delay, set to 30 seconds based on measured checkpoint-restart times ranging from 15 to 120 seconds.

This penalty model has several structural limitations. First, it is memoryless with respect to job phase: a job that has experienced few re-allocations early in its life is penalized lightly for a re-allocation late in its life, even if that late re-allocation would be disruptive (e.g., near convergence). Second, it is linear in the re-allocation count R_j, meaning the penalty for the 10th re-allocation is computed the same way as for the 1st, even though frequent re-allocations may have non-linear effects (e.g., cache invalidation, learning rate schedule disruption). Third, the penalty depends on the estimate δ, which is a single global value, while actual re-allocation delays vary from 15 to 120 seconds (8× range) depending on model size — large models like ResNet-50 experience much longer checkpoint-restart delays than small models like ResNet-18, but Pollux uses the same δ = 30s for both.

The consequence. For short jobs (e.g., CIFAR-10, <1 GPU-hour), the penalty may be too lenient. A job that has run for 5 minutes (T_j = 300s) with one prior re-allocation (R_j = 1) would have REALLOC_FACTOR = (300 − 30)/(300 + 30) ≈ 0.82, meaning the predicted speedup is only reduced by 18% to account for a 30-second restart on a job that will finish in a few more minutes. If the re-allocation actually takes 120 seconds (not 30), the effective speedup would be much lower than predicted, and the scheduler may make allocation decisions that look beneficial under the model but are harmful in reality. The paper reports an average 8% run-time overhead from re-allocations (once every 7 minutes), but this is an average — short jobs that happen to be re-allocated may experience substantially higher overhead.

For long jobs, the penalty accumulates with R_j. A job that runs for 10 hours (T_j = 36,000s) with 50 prior re-allocations (R_j = 50) would have REALLOC_FACTOR = (36,000 − 1,500)/(36,000 + 30) ≈ 0.96. This is a modest 4% penalty that may not sufficiently discourage further re-allocations, even though the job has already lost 50 × 30 = 1,500s = 25 minutes to restart overhead. The scheduler sees only the incremental penalty, not the cumulative cost.

What evidence exists in the paper. The paper reports "on average, each job was re-allocated resources once every 7 minutes, resulting in an average 8% run-time overhead due to checkpoint-restarts" (Section 5.2). This aggregate statistic is provided but not broken down by job duration, model size, or re-allocation frequency. There is no ablation of the re-allocation penalty — for instance, comparing δ = 15s, 30s, 60s, 120s, or comparing the linear penalty model against a no-penalty baseline or a more sophisticated model (e.g., one that accounts for job phase or model size). The paper does not report the distribution of re-allocation counts per job, the relationship between re-allocation frequency and JCT, or whether some jobs experienced disproportionately high re-allocation overhead.

The sensitivity to scheduling interval (Figure 8b) is the closest proxy for a re-allocation frequency experiment — longer scheduling intervals reduce re-allocation frequency — but this conflates reduced re-allocations with slower response to cluster load changes, so it does not isolate the re-allocation overhead effect.

Mitigation status. The re-allocation penalty is a heuristic that works adequately in the paper's setting (8% average overhead), but it is not validated across different job durations, model sizes, or re-allocation patterns. The paper does not discuss alternatives (e.g., exponential backoff, cost-aware penalties based on model size, phase-aware penalties, or hard limits on re-allocation frequency) or characterize when the linear penalty model might fail. The use of a single δ for all jobs is a practical simplification, but its sensitivity is untested — a cluster with more heterogeneous model sizes might require per-job δ estimates.

7. Implications and Future Directions

How This Work Changes the Landscape

Pollux represents a reframing of the DL cluster scheduling problem from a purely resource-allocation exercise into a joint optimization over both cluster-level resources and job-level training configurations. This is not a paradigm shift in the sense of inventing a new class of algorithms — the individual components (throughput modeling, gradient noise scale estimation, population-based search) are drawn from prior work — but it is a diagnostic and architectural shift that changes what information schedulers are expected to reason about and how they should be designed.

Before Pollux, the dominant mental model in the DL scheduling community treated the scheduler's job as answering "how many GPUs should each job get?" and the user's (or training algorithm's) job as answering "what batch size and learning rate should I use?" This separation was so deeply ingrained that even scale-adaptive schedulers like Optimus and Gavel, which dynamically re-allocate GPUs, made no attempt to adjust training hyperparameters in response — they assumed the job would use whatever batch size the user specified, and that throughput would scale accordingly. Pollux demonstrates that this separation is not merely suboptimal but conceptually inconsistent: the answer to "how many GPUs should this job get?" depends on what batch size the job will use if given those GPUs, which in turn depends on the job's current statistical efficiency, which depends on the PGNS φ_t — a quantity that changes during training and that no prior scheduler measured.

The paper's re-conceptualization of the scheduler's role has several concrete implications for the field:

First, schedulers should be expected to model training dynamics, not just hardware performance. Prior work treated throughput as the sole bridge between resource allocation and training speed — more GPUs → more examples/second → faster completion. Pollux shows that this bridge is incomplete because examples are not fungible: an example processed at batch size 4096 may contribute less to training progress than an example processed at batch size 256, and this ratio changes over the course of training. The goodput metric makes this explicit and measurable. Future DL schedulers that ignore statistical efficiency will be, by Pollux's own evidence, leaving 37-73% of performance on the table relative to what is achievable with goodput-aware co-adaptation. This raises the bar for what constitutes a competitive scheduler.

Second, the paper reconciles a subtle tension in the adaptive training literature. Methods like AdaBatch, CABS, and AdaScale developed principled ways to adjust batch size and learning rate during training using gradient statistics, but they assumed they controlled their resource allocation — a false assumption in any shared cluster. On the other side, cluster schedulers assumed training configurations were fixed. These two communities were talking past each other: adaptive training researchers assumed infinite resources, and scheduling researchers assumed fixed training configurations. Pollux's co-adaptive architecture shows that both assumptions can be relaxed simultaneously: the PolluxAgent embodies adaptive training logic but operates under resource constraints determined by PolluxSched, and PolluxSched makes allocation decisions knowing that jobs will adapt their training to whatever resources they receive. This synthesis makes both lines of work more practical — adaptive training algorithms can now be deployed in shared clusters, and cluster schedulers can now leverage adaptive training to improve utilization.

Third, the paper establishes that verifier/estimator quality (in this case, the PGNS and throughput models) is the bottleneck for co-adaptive scheduling, not search algorithm sophistication. PolluxSched uses a relatively simple population-based search over allocation matrices, yet achieves substantial improvements because its objective function — the fitness over goodput-based speedups — accurately captures the consequences of allocation decisions. If the PGNS model were inaccurate or the throughput model failed to predict scaling behavior, no amount of search sophistication would recover the lost performance. This redirects research attention: improving the fidelity and generality of the predictive models (throughput across parallelism strategies, statistical efficiency across optimizer types) is likely more impactful than designing more sophisticated scheduling algorithms for the same models.

Fourth, the paper makes scaling up cluster size a less attractive direction relative to improving per-job efficiency. The finding that Pollux achieves 72-73% reduction in average JCT under realistic configurations — without increasing the number of GPUs in the cluster — means that many clusters are operating far below their hardware's potential due to configuration inefficiency. For a cluster operator deciding between buying more GPUs and deploying a better scheduler, the Pollux results suggest the latter is dramatically more cost-effective: a scheduler that extracts 2-4× more useful work from existing hardware effectively multiplies the cluster's capacity at software cost. This does not make scaling cluster size irrelevant — for workloads where demand genuinely exceeds capacity even after optimization — but it changes the default assumption that adding GPUs is the primary lever for reducing job completion times.

Follow-Up Research This Work Enables

Extending the throughput model and PGNS estimation to model parallelism, pipeline parallelism, and hybrid parallelism strategies. Pollux's current throughput model (Equation 11) and interference avoidance constraint assume synchronous data-parallel training with all-reduce — the dominant paradigm for models that fit on a single GPU but not for large language models, vision transformers, or other architectures that require model parallelism to distribute parameters across devices. A natural follow-up would measure Pollux's performance when the throughput model is replaced with one that captures pipeline-parallel execution (bubble overhead, micro-batch scheduling), tensor/model parallelism (communication patterns for layer-wise distribution), or hybrid strategies like ZeRO. The key experiment: take a GPT-2 or BERT-large pretraining workload on a cluster with high-speed interconnects (e.g., A100 GPUs with NVLink and InfiniBand), implement or fit a throughput model appropriate for model parallelism, and measure whether PolluxSched can effectively allocate GPUs and tune per-GPU micro-batch sizes to maximize goodput when jobs use diverse parallelism strategies. A negative result — Pollux's centralized allocation search failing to handle the discrete constraints of pipeline stage counts or tensor-parallel degrees — would be equally informative, as it would clarify the architectural limits of the co-adaptive approach.

On-the-fly detection of LR scaling rule breakdown and automatic maximum batch size selection. Pollux currently requires the user to specify a maximum batch size limit and to implement the correct SCALE_LR function for their optimizer and model. Both requirements demand expert knowledge and experiments that Pollux is supposed to eliminate. A follow-up could instrument the PolluxAgent to detect when the LR scaling rule begins to fail — for instance, by monitoring the loss trajectory or gradient norm statistics after batch size changes and flagging configurations where the loss diverges, oscillates, or plateaus at a worse value than smaller-batch training. Combined with online hyperparameter optimization (the paper's own HPO experiment in Section 5.4.2 suggests this is feasible), the agent could automatically determine the batch size range over which the chosen LR scaler maintains acceptable model quality, removing the user-specified limit. The key experiment: run Pollux on the same six-model workload but without providing the maximum batch size, and measure whether the automatic detection correctly identifies safe batch size ranges without exceeding them, and what fraction of the manually-specified limit's performance is recovered. A strong result would show the automatic limit achieving comparable final model quality to the manual limit while enabling Pollux to explore batch sizes the manual setting might have excluded.

Combining Pollux's goodput-driven allocation with fine-grained GPU sharing and time-slicing (AntMan-style). Pollux allocates whole GPUs to jobs and uses interference avoidance to prevent distributed jobs from sharing nodes — a conservative approach that leaves GPU memory and compute underutilized when jobs do not saturate their allocated GPUs. AntMan (Xiao et al., 2020) demonstrated that fine-grained GPU sharing (multiple jobs co-located on the same GPU, with dynamic memory allocation and compute time-slicing) can improve cluster utilization and reduce JCT. Combining these approaches raises a specific technical challenge: Pollux's goodput model assumes dedicated GPU access, so it would over-predict throughput for co-located jobs. A follow-up could extend the throughput model with an interference factor that depends on the number and type of co-located jobs (e.g., measured by observing throughput degradation when multiple PolluxAgents share a node, with the interference avoidance constraint relaxed), then evaluate whether PolluxSched's allocation search can balance the benefits of higher GPU utilization from sharing against the throughput degradation from interference. The key experiment: run Pollux with and without GPU sharing on a workload with many small jobs (where GPU sharing would provide the most benefit) and measure the average JCT. A finding that GPU sharing helps primarily for small jobs but hurts large distributed jobs would provide actionable guidance for hybrid scheduling policies.

Goodput-aware scheduling across heterogeneous accelerator types using Gavel-like throughput normalization. The paper explicitly notes (Section 2.3 footnote) that extending Pollux with Gavel's (Narayanan et al., 2020) throughput metric "would allow Pollux to co-adapt for goodput in heterogeneous DL clusters." This is a well-scoped engineering extension with clear evaluation criteria. Gavel normalizes throughput across accelerator types by measuring each job's throughput on each accelerator relative to a reference accelerator, enabling the scheduler to compare the benefit of giving a V100 vs. an A100 to different jobs. Pollux's goodput function adds a second dimension: the statistical efficiency at the batch size each accelerator type would support (since different GPUs have different memory capacities and hence different maximum per-GPU batch sizes). A follow-up would implement this combination, deploy on a cluster with mixed GPU types (e.g., T4, V100, A100), and measure whether goodput-aware heterogeneous scheduling outperforms both Pollux with homogeneous assumptions and Gavel with throughput-only metrics. The key experiment: a workload where some jobs benefit disproportionately from A100s due to memory capacity (enabling larger batch sizes without gradient accumulation, improving goodput through higher efficiency at larger M), while other jobs are compute-bound and benefit equally from any GPU type. Goodput-aware scheduling should route memory-hungry jobs to high-memory GPUs even if they have similar compute throughput to lower-memory alternatives.

Characterizing the exploration cost in heavily oversubscribed clusters and developing load-aware exploration strategies. Section 6 of this analysis identified the exploration tax — the opportunity cost of allocating GPUs to new jobs with optimistic priors while running jobs with well-characterized models are deprioritized — as an unmeasured limitation. A specific follow-up experiment would instrument Pollux to track, per scheduling interval, how many GPUs are allocated to jobs whose goodput predictions are based on priors (unexplored regions) versus measured data. Run this on workloads with varying submission rates (0.5×, 1.0×, 2.0×, 4.0× the baseline rate) and measure the average JCT of running jobs conditioned on whether a new job arrived during their lifetime. The hypothesis: at high submission rates, running jobs experience measurable slowdowns when new jobs arrive and receive exploratory allocations. If confirmed, the follow-up could propose and evaluate mitigation strategies: load-aware exploration (reduce prior optimism or delay exploration when cluster utilization exceeds a threshold), shared priors across jobs of the same model type (a new ResNet-50 job inherits the throughput model from a previously-profiled ResNet-50), or progressive exploration (start with a small number of GPUs, collect throughput data, scale up gradually — which Pollux's maximum-doubling rule already approximates but could be made more aggressive for common model types).

Evaluating Pollux on production-scale clusters with production workloads. The paper's evaluation, while thorough for a systems paper, is limited to a 64-GPU homogeneous cluster with a synthetic workload derived from one 8-hour trace slice. A critical follow-up — ideally by a team with access to a large production cluster — would deploy Pollux on a cluster with 1000+ GPUs, a real workload mix (including model-parallel jobs, interactive notebook workloads, and jobs using different frameworks), and measure Pollux's performance over weeks of operation. Key metrics beyond average JCT: PolluxSched's CPU and memory usage as a function of cluster size and job count; the distribution of re-allocation delays at scale (do large-model checkpoint-restarts cause cascading delays?); whether the interference avoidance constraint becomes overly restrictive when many jobs request distributed execution; and whether the 60-second scheduling interval remains sufficient when Pod creation/termination latency dominates. This is an engineering evaluation rather than a research contribution, but it is essential for establishing the practical viability of co-adaptive scheduling beyond the prototype scale. A negative result — PolluxSched failing to complete its search within the scheduling interval at 1000+ GPUs — would motivate research into hierarchical or decentralized scheduling architectures that preserve the co-adaptive principle while distributing the optimization.

Practical Applications and Downstream Use Cases

Managed DL training platforms (cloud ML services, internal cluster schedulers). The most direct application is integrating Pollux (or its goodput-driven co-adaptation approach) into the scheduler of a managed DL platform — for instance, Amazon SageMaker, Google Vertex AI, or an organization's internal Kubernetes-based DL cluster. The benefit is quantifiable from the paper's realistic-configuration results: average job completion times improve by 72–73% compared to the status quo where users specify GPU counts and batch sizes manually (Table 2). In a platform serving hundreds of users, this translates to either (a) serving the same workload with half the GPU capacity, reducing infrastructure costs proportionally, or (b) completing user jobs twice as fast, improving user experience and enabling faster experimentation cycles. The paper's fairness knob (p = −1) provides a operational lever for platform administrators to balance efficiency against fairness without per-user configuration. The 8% average re-allocation overhead and 1-second scheduling computation cost (Section 5.2) suggest the approach is lightweight enough for production deployment.

Cost-efficient cloud training of large models using goodput-driven auto-scaling. Section 5.4.1 demonstrates a specific cost optimization: for a large ImageNet training job, Pollux's goodput-driven auto-scaling reduces cloud GPU cost by 25% compared to throughput-based auto-scaling (Or et al., 2020), with only a 6% increase in wall-clock completion time. The mechanism is intuitive and general: start training with a small number of GPUs when the model's statistical efficiency is low (large batch sizes are wasteful early in training), and scale up gradually as the PGNS increases and larger batches become more efficient. This applies to any long-running training job where statistical efficiency improves over time — which, per Figure 2, includes image classification, object detection, and speech recognition (less so for BERT fine-tuning and recommendation, where efficiency changes little). For organizations training large models on cloud instances (where GPU-hours directly determine cost), implementing Pollux's goodput-based auto-scaling could yield double-digit percentage cost savings with minimal engineering effort (the auto-scaling policy in Section 5.4.1 is described in a few sentences and requires only the goodput function, which PolluxAgent already computes). The specific parameters U = 2/3 and L = 1/2 are starting points that could be tuned per-model, but the paper's results suggest the approach is robust to these choices.

Hyperparameter optimization (HPO) services. The HPO experiment in Section 5.4.2 shows Pollux completing 100 trials of TPE-based hyperparameter optimization 30% faster (25 min vs. 34 min average JCT) and with 40% shorter makespan (10h vs. 14h) compared to a static 4-GPU-per-trial baseline, while achieving equivalent final model accuracy (95.4% vs 95.5% top-5). For HPO services like Google Vizier, Katib (Kubeflow), or Ray Tune — where many short-lived training trials compete for a shared GPU pool — Pollux's co-adaptive scheduling is particularly well-suited: trials have diverse scalability characteristics, their training duration is unknown a priori (matching Pollux's online learning approach), and reducing total HPO time directly accelerates the model development cycle. The finding that Pollux re-allocates GPUs "once every 7 minutes on average" (Section 5.2) suggests that even relatively short HPO trials (tens of minutes) would benefit, provided the checkpoint-restart overhead (15–120 seconds) is small relative to trial duration. A specific deployment scenario: an HPO service with 64 GPUs processing a mix of trial types (some using ResNet, some using transformers, some with custom architectures) where Pollux automatically allocates GPUs and tunes batch sizes per trial, reducing the total time-to-result for hyperparameter searches without requiring users to specify per-trial resource requirements.

When to Prefer This Method

Pollux's co-adaptive scheduling approach is positioned against two categories of alternatives discussed explicitly in the paper: non-scale-adaptive schedulers where users specify fixed GPU counts and batch sizes (e.g., Tiresias, Gandiva) and scale-adaptive schedulers that automatically adjust GPU counts but not training configurations (e.g., Optimus, Gavel, AntMan). Based on the paper's evaluation and analysis, the decision conditions are:

Prefer Pollux when:

• The workload consists primarily of data-parallel DL training jobs with synchronous SGD (or adaptive variants like Adam/AdamW) using all-reduce gradient synchronization, since Pollux's throughput model is validated specifically for this regime and the PGNS derivation applies to pre-conditioned SGD.
• Users cannot or should not be expected to manually tune per-job GPU counts, batch sizes, and learning rates — either because the cluster has many users with varying expertise (realistic-configuration experiments show 72-73% improvement over baselines in this scenario, Table 2), or because optimal configurations change dynamically with cluster load and training progress.
• Statistical efficiency varies substantially across jobs or over the course of training, since this is the dimension that throughput-only schedulers ignore. Jobs with highly variable PGNS (e.g., ImageNet, DeepSpeech2, YOLOv3 in Figure 2) benefit more than jobs with flat efficiency curves (e.g., BERT fine-tuning, NeuMF recommendation).
• GPU memory limits constrain per-GPU batch sizes before reaching throughput saturation, making gradient accumulation necessary — Pollux explicitly optimizes gradient accumulation steps alongside batch size and GPU count (Equation 13).
• The cluster is homogeneous (all GPUs of the same type) or the throughput model has been extended to handle heterogeneity — the paper's current implementation and evaluation assume uniform GPU types.
• Fairness is an explicit operational requirement, since Pollux provides a tunable knob (p) that enables the cluster operator to balance efficiency against fairness, and achieves finish-time fairness comparable to Themis (Figure 7) while also improving efficiency.

Prefer Optimus, Gavel, or Tiresias (or simpler alternatives) when:

• The workload uses parallelism strategies other than or in addition to synchronous data-parallel all-reduce (model parallelism, pipeline parallelism, parameter-server architectures, asynchronous SGD) — Pollux's current throughput model does not apply, and the paper provides no validation in these regimes.
• All jobs have fixed, well-understood batch size requirements that cannot be changed without degrading model quality (e.g., some contrastive learning objectives, certain RL training algorithms) — Pollux's ability to co-adapt batch size provides no benefit, and the additional complexity of the PolluxAgent may not be justified.
• The cluster is heterogeneous (mixed GPU types, TPUs, different network interconnects) and extending Pollux with Gavel-style heterogeneity support is not feasible — simpler schedulers that treat each GPU type as a separate resource pool may be more practical.
• Jobs are extremely short (seconds to a few minutes) relative to the checkpoint-restart delay (15-120 seconds), since Pollux's re-allocation mechanism requires checkpointing for migration and the 8% average overhead may become prohibitive for very short jobs.
• Re-allocation is infeasible (e.g., training frameworks or storage systems that do not support checkpoint-restart, or jobs with strict data locality constraints that prevent migration) — Pollux's dynamic GPU re-allocation is a core mechanism, and without it only the per-job tuning (PolluxAgent without PolluxSched) would remain.