Which Ordering Matters for Backfilling? Decision-Local Rank Correlation for Runtime Predictors

HPC clusters, the shared supercomputers that run batch jobs over many processors, rely on backfilling to keep machines busy. The first job in the queue gets a reservation, a promised start time. Backfilling lets later jobs jump ahead into idle processors, provided the scheduler believes they will finish before that reservation begins. Sorting these backfill candidates shortest-first, using machine-learned runtime predictions, gives large gains: EASY-SJBF (shortest job backfilled first) improved average bounded slowdown by 28% across six production logs and by 86% on Curie (Improving backfilling by using machine learning to predict running times). Bounded slowdown is roughly how much longer a job spends in the system than its runtime alone, with very short jobs floored so they do not dominate. The broader literature says that what really matters for size-based scheduling is the order of predictions, not their accuracy. That is the thesis behind Scheduling with Predictions and the Price of Misprediction. Recent systems therefore report rank correlations such as Spearman's $\rho$ or Kendall's $\tau$ as their headline predictor quality.

We argue that the rank correlation people measure is the wrong one for backfilling, and that fixing the measurement tells us what to train. A global correlation over a whole trace mostly compares jobs that never competed for the same slot. It is also blind to scale: multiplying every prediction by ten leaves $\tau=1$ but stops all backfilling. The quantity that should govern backfilling quality has two parts. The first is decision-local concordance, meaning agreement in order among jobs that actually sat in the queue together when a backfill decision was made. The second is a boundary error: how often the predictor gets "does this job fit before the reservation?" wrong. This note proposes to measure that decomposition on production logs, test whether it explains slowdown better than global $\tau$ or MAE, and train predictors directly for it.

Core Claim

Our hypothesis is that, across a wide family of runtime predictors, average bounded slowdown under EASY-SJBF is explained mainly by two statistics computed at actual scheduling decisions. One is a Kendall-style concordance restricted to co-queued, processor-feasible candidate pairs. The other is the misclassification rate of "fits in the window" at the windows that actually occurred. Global Spearman/Kendall and MAE should be weak proxies. The practical consequence is a predictor built as two separate pieces. An ordering score is trained with a smooth pairwise Kendall surrogate on co-queued pairs only. A monotone calibration map sets its scale to a chosen quantile, so the fit decisions are conservative. Because the map is monotone, calibration cannot disturb the learned order.

The claim is new because three lines of work each stop short of it. Mitzenmacher's analysis motivates ordering, but it is set in a single-server queue with no reservations. Gaussier et al. found that MAE does not track slowdown, but they answered with a pointwise asymmetric loss (E-Loss) and never analyzed candidate-queue ordering. Efficient LLM Scheduling by Learning to Rank trains a listwise ranker (ListMLE) and validates with Kendall's $\tau$. Its setting is LLM serving, where scheduling happens per token-generation iteration and preemption is available, so there is no fit constraint and scale never matters. ATLAS reports Spearman 0.912 but trains regression and quantile models and does not implement backfilling.

Research Program

The first component is measurement. We will replay each Parallel Workload Archive log used by Gaussier et al. (KTH-SP2, CTC-SP2, SDSC-SP2, SDSC-BLUE, Curie, Metacentrum) through an EASY backfilling simulator. At every backfill decision $t$ we log three things: the candidate set $C_t$, the free processors, and the window $W_t$. The window $W_t$ is the time until the head job's reservation, which is itself computed from the predicted remaining times of running jobs. For each decision we define the local concordance

$$\tau_{loc} = \frac{\sum_t \sum_{i,j \in F_t} w_{ij}\,\mathrm{sgn}(\hat y_i - \hat y_j)\,\mathrm{sgn}(x_i - x_j)}{\sum_t \sum_{i,j \in F_t} w_{ij}},$$

where $F_t \subseteq C_t$ is the set of candidates whose processor request fits, $x$ is true runtime, $\hat y$ is the prediction, and $w_{ij}=|\log x_i - \log x_j|$ gives more weight to inversions between very different jobs. We also define the boundary error $\beta$ as the fraction of $(t, i\in F_t)$ where $\mathbb{1}[\hat y_i \le W_t] \neq \mathbb{1}[x_i \le W_t]$. We split $\beta$ into two cases: predicted-fit-but-overran, which delays the reservation, and predicted-too-long-but-would-fit, which wastes an idle gap. The decisions depend on the predictor, so these statistics are computed per predictor under its own replay.

The second component is a controlled test of the tension between rank and scale that the research file identifies. Starting from true runtimes, we construct synthetic predictors in two ways. One applies order-preserving distortions such as global scaling, compression, and monotone warps, which keep $\tau=1$. The other applies scale-preserving local swaps, which lower $\tau_{loc}$ while keeping calibration fixed. Real predictors such as MAE regression, E-Loss, quantile regression, ListMLE, and our method are added to the pool. We then regress each log's slowdown on each candidate statistic and compare how much variance each explains.

The third component is the training objective. A gradient-boosted or small MLP scorer $s(\cdot)$ is trained on log-runtime features, chronologically and online as in Gaussier et al. Its loss is a smooth Kendall surrogate over pairs sampled from the same queue snapshot. The surrogate uses the $\tanh$ sign approximation from Enhancing Logits Distillation with Plug&Play Kendall's τ Ranking Loss and random pair subsampling to reach linear cost as in DiffKendall. We reuse their methods, not their results, because both were validated only on vision tasks. Runtimes on these logs span seconds to days, and ATLAS reports 3s to 7d, so we apply the surrogate to differences of log-scores and check whether its gradients vanish on heavy-tailed pairs. We then fit an isotonic map $g$ from $s$ to the $q$-quantile of runtime on a held-out recent window. This map is monotone, so it cannot change the ordering. The scheduler sorts by $s$ and tests fit with $g(s)$. The quantile $q$ is chosen on validation data to trade reservation delay against wasted gaps. As in Gaussier et al., a job that exceeds its prediction has its prediction extended, not killed.

Baselines

The naive reference is standard EASY backfilling, which processes candidates in first-come order and uses user-requested walltimes. All slowdown improvements are reported relative to it, as in Gaussier et al. We also run EASY-SJBF sorted by requested walltime, which shows how much ordering helps before any learning.

The strongest existing method is EASY-SJBF with the online $\ell_2$-regularized polynomial regressor trained with E-Loss. That loss penalizes underprediction quadratically and overprediction linearly (Improving backfilling by using machine learning to predict running times). Its reported numbers are a 28% average bounded slowdown improvement over EASY across the logs and 86% on Curie. It is the strongest competitor because it was designed for this exact scheduler and these exact logs. We will reimplement it with the same features, the same online chronological retraining schedule and the same correction rule, and first confirm that we reproduce roughly those figures. Beating it means lower average bounded slowdown on a majority of the six logs, with no increase in maximum bounded slowdown and no increase in reservation delay of head jobs. Improvements must hold across at least three simulation seeds for tie-breaking.

The second learned competitor is a ListMLE ranker in the style of Fu et al. It is trained on global orderings and scaled with the same isotonic calibration, so the only difference from our method is which pairs the ranking loss sees. The third is a gradient-boosted quantile regressor with conformal calibration, following the ATLAS recipe, which gives order and scale from one model. No reported backfilling result was found on Lacuna for ListMLE or ATLAS-style models on the PWA logs. We will report their ATLAS-side numbers, Spearman 0.912 and total completion time ratio 1.106, only as context.

The key ablation keeps our isotonic calibration and fit rule but swaps the ordering score for the E-Loss regressor's output. If this ablation matches our method, then pairwise training added nothing and all of the gain came from decoupled calibration. All learned methods get the same features, the same hyperparameter search budget of equal trial counts per log, and the same retraining cadence.

Why not just…?

Why not just use E-Loss or a quantile regressor, since its outputs already define an order? This is the most serious alternative. A good pointwise regressor may already have high local concordance. The ablation above settles it directly. Whichever way it comes out, the measurement study still says why E-Loss works, through lower boundary error, lower local inversion rate, or both. That explanation is not currently known, since Gaussier et al. only report that MAE fails as a proxy. If the ablation ties, we will say the training contribution is null and present the decomposition and the calibration-only design as the result.

Why not just train a global learning-to-rank model, as in LLM serving? Fu et al. show that ListMLE plus Kendall's $\tau$ validation works when order is all that matters. In backfilling, two things differ. Most global pairs never co-occur in a queue, and a globally ranked score has no scale for the fit test. The ListMLE-plus-isotonic baseline isolates the first issue. The order-preserving distortion experiment demonstrates the second, because it produces predictors with $\tau=1$ that break backfilling.

Why not just sort by user-requested walltime, or classify jobs into short, medium and long? Requested walltimes are inflated upper bounds, and Gaussier et al.'s 86% Curie gain over requested-time scheduling measures how much that inflation costs. Coarse buckets cannot resolve which of several "short" jobs fits a 15-minute window. That is exactly the boundary error $\beta$, which we measure for a three-bucket classifier baseline.

Proposed Experiments and Decisive Checks

The first decisive check is explanatory. Across the pooled real and synthetic predictors on each PWA log, $\tau_{loc}$ together with the two parts of $\beta$ should explain substantially more of the variation in average bounded slowdown than global Kendall $\tau$, Spearman $\rho$ or MAE. We specifically expect the order-preserving distortions to show near-constant global $\tau$ alongside large slowdown differences. If global $\tau$ explains slowdown as well as the local statistics, the central claim is wrong.

The second check is the head-to-head comparison against E-Loss EASY-SJBF, with the calibration-only ablation reported alongside, on average and maximum bounded slowdown and head-job reservation delay. Following the concern ATLAS raises that stretch-type tail metrics are hypersensitive, we report max-stretch-style tails and count jobs above the 99th-percentile slowdown.

The third check is transfer. We build the same EASY simulator over ATLAS GPU jobs, treating GPU count as the processor dimension, and ask whether the local-versus-global gap persists on an ML workload. ATLAS reports 81.3% recurrent jobs there. We also stratify results by recurrent and cold-start jobs, where the relative advantage of ordering-only training may differ most.