Who Slows Whom: Learning Asymmetric Interference from Passive Job Progress

When jobs share a machine, they slow each other down through caches, memory bandwidth, PCIe buses and network links. This is the noisy neighbor effect. The slowdown is lopsided: an aggressive "bully" job can evict a quiet job's cache contents without being hurt in return, as documented for GPU thread scheduling in CIAO. Schedulers therefore need to know, for every pair of jobs, how much job A hurts job B. Nobody can afford to measure this directly. Exhaustive co-location sweeps grow combinatorially, and dedicated profiling runs are exactly the kind of synthetic overhead that passive monitoring tries to avoid. Every cluster, however, already records a free signal: how fast each job made progress, such as its iteration time or its per-request latency, while it ran next to whatever neighbors the scheduler happened to give it.

We propose to recover a job-by-job interference model from that passive progress data alone. The model gives each job two learned vectors: a pressure vector describing how hard it pushes on shared resources, and a sensitivity vector describing how much it suffers from pressure. A job's slowdown is then a saturating function of the summed pressure of its neighbors, weighted by its own sensitivity. The work sits on three questions the literature leaves open. First, this interference matrix is square, indexed by the same jobs on both sides, but it is not symmetric; does tying the two vectors together, which the matrix-symmetry literature suggests should help, improve recovery from very sparse observations? Second, can a model trained on pairwise co-locations extrapolate to three, four or five neighbors once saturation is modeled? Real resources hit capacity cliffs that break simple additivity. Third, how badly does the scheduler's own biased placement, which avoids known-bad pairs, corrupt what can be learned, and how much deliberate exploration repairs it?

Core Claim

The measurement model is the following. Let $y_{i,N}$ be the log slowdown of job $i$ relative to running alone, observed passively while it shares a machine with the neighbor set $N$. We model

$$y_{i,N} = g\Big(\textstyle\sum_{j \in N} s_i^\top p_j\Big) + \varepsilon,$$

In this equation, $s_i \in \mathbb{R}^r$ is job $i$'s sensitivity, $p_j \in \mathbb{R}^r$ is neighbor $j$'s pressure, $g$ is a learned monotone function with $g(0)=0$ that is allowed to saturate or to steepen at a cliff, and $\varepsilon$ is noise. When $g$ is the identity and every $N$ holds a single neighbor, this reduces to asymmetric low-rank matrix completion of the pairwise matrix $S_{ij} = s_i^\top p_j$. The claim has three parts.

The first part is that the aggregation plus the link $g$ let pairwise data predict multi-neighbor slowdowns that a pairwise matrix cannot express at all.

The second part concerns how the two vectors relate. Because both come from the same job's resource footprint, a partial symmetry tie $s_i = W p_i + \delta_i$, with $\delta_i$ penalized, cuts the effective number of parameters. That should matter most at the sub-1% observation rates real schedulers produce. The tie should help when the symmetric part of $S$ dominates, and it should hurt when bully–victim asymmetry dominates. Measuring which regime real hardware is in is itself a result.

The third part is that the observations are chosen by the scheduler, not sampled at random. Because of this, a small, uncertainty-guided exploration budget is needed to keep the model from going blind on the pairs it has learned to avoid.

Where This Sits

The closest work is Pitot. Pitot predicts edge runtimes under interference by completing a workload × hardware matrix with a two-tower factorization and a log-residual objective, and it wraps the predictions in conformal intervals. We reuse its log-residual target, its feature towers for jobs never seen before, and its conformal calibration. We differ from it in three ways. Our matrix is job × job, so its two sides refer to the same objects and a symmetry question arises. Our observations are set-valued and passive rather than individual profiled cells. And we model non-additive aggregation across several neighbors, which Pitot's formulation cannot represent.

Two other systems predict interference but depend on deliberate profiling or offline training. iGniter splits GPU sharing into scheduling delay, L2 contention and power capping, and fits an analytical model from 11 profiling points per model. GOGH refines throughput predictions across GPU types using neural networks and a catalog. Both motivate our task. Both also set the accuracy bar for the setting in which profiling is allowed, which we must approach without it.

On the passive side, the work motivates rather than supplies our method. NetMax already treats worker iteration times as a proxy for link quality. It openly assumes that network transit dominates, an assumption that fails when local compute contention dominates. Our per-neighbor attribution is a direct attempt to separate these causes. NETSTORM identifies the "avalanche effect", in which abandoned links stop producing measurements. It patches the problem by sending small chunks over auxiliary paths, and it reports that auxiliary paths added a further 65% speedup on top of passive awareness alone. That is evidence that some exploration is not optional. We recast its ad hoc remedy as exploration guided by the model's calibrated uncertainty.

The matrix theory both supplies methods and constrains what we can claim. Park et al. show that rectangular Burer-Monteiro factorization has no spurious local minima if one adds a balancing penalty $\lambda\|U^\top U - V^\top V\|_F^2$ and the measurements satisfy a restricted isometry property. We use the balancing penalty. Scheduler-chosen observations will not satisfy that property, so we treat the absence of spurious minima as an empirical question and do not assume it. Jiang, Chen and Ding show that gradient descent from a small random initialization recovers singular values one at a time, which regularizes toward low rank without an explicit penalty. Their result holds only for fully observed matrices. Whether this staircase recovery survives sparse, biased, set-aggregated sensing is one of our measurements.

On the nonlinear side, the relevant lesson from control is a negative one. Data-driven predictive control built on Willems' lemma depends on superposition, and superposition fails at saturation. We make no stability claims about a closed-loop scheduler. Our "nonlinear generalization" is confined to the measurement model, and we test it directly by extrapolating to more neighbors than were seen in training.

Research Program

We will build three things.

The first is a co-location corpus with ground truth. The file names no public dataset that provides k-way neighbor sets with slowdowns. The Gavel dataset as used by GOGH gives pairwise co-location slowdowns for deep-learning jobs across six GPU types, which serves our pairwise experiments. For k-way data, we will run two sweeps ourselves. One follows the design of Pitot's 24-device testbed, using its Polybench/MiBench kernels compiled to WebAssembly on a subset of x86, ARM and RISC-V devices. The other is a GPU sweep under NVIDIA Multi-Process Service (MPS, NVIDIA's mechanism for letting several processes share one GPU concurrently) with the AlexNet, ResNet-50, VGG-19 and SSD models used by iGniter, co-locating one to five tenants. We will randomize a held-out slice of the placements so that we have unbiased ground truth.

The second is a passive observation simulator. It replays the ground truth through a scheduler, either greedy interference-aware or contention-oblivious, and exposes only the progress of jobs under the placements that scheduler actually chose. The simulator reproduces biased sampling and blind spots, and it lets us control the observation rate.

The third is the estimator. It fits the equation above with pressure and sensitivity produced by feature towers, a monotone spline for $g$, Park's balancing penalty, and an optional symmetry tie. It is trained by gradient descent from a small random initialization, and conformal intervals are calibrated on held-out placements. An exploration rule then spends a fixed budget of placements on the pairs with the widest intervals. The analysis side estimates the split of $S$ into symmetric and antisymmetric energy on each hardware class, and tracks whether the staircase recovery is visible when observations are partial.

Baselines

The naive reference point assumes no interference and predicts solo runtime. It is paired with a contention-oblivious scheduler in the placement experiments. It sets the floor that iGniter's reported 35% ResNet-50 latency increase under five co-located tenants shows is far from harmless.

The strongest learned competitor is Pitot's two-tower factorization with its log-residual objective, run on the job × job pairwise matrix. For k-way prediction we give it the most charitable additive extension, summing its predicted pairwise log slowdowns. It receives the same passive observations, the same feature towers and the same hyperparameter search budget as our model. Pitot reports 5.2% mean absolute percent error (MAPE) on its own 24-device testbed with profiled data (Pitot). That figure comes from a different observation regime, so we treat it as context and not as a target to match.

The profiling-based ceiling is iGniter's analytical model. It is given its 11 active profiling points per model, and it reports 1.53% to 5.02% error on co-located latency (iGniter). On Gavel, GOGH's pipeline reports a validation mean absolute error (MAE) of about 0.062 (GOGH), and we will rerun it on our splits.

We add a flexible black box: a permutation-invariant set network that maps job features plus the neighbor set to a slowdown, given the same data and tuning budget. We also include gradient-boosted trees on hand-built features, the model family behind the strongest duration predictor in ATLAS (Spearman 0.912 on job duration, a different task). The file reports no result on Lacuna for any of these methods on passive k-way co-location prediction.

Ablations isolate each ingredient. We remove the link ($g$ set to identity), remove the symmetry tie, force full symmetry ($s_i = p_i$), remove the balancing penalty, and remove exploration.

Beating the baselines means lower error on held-out k ≥ 3 placements than additive Pitot and the set network when trained only on pairs, at equal passive data. It also means coming within a stated margin of iGniter's profiled accuracy without any profiling.

Why not just…?

Why not just run Pitot on the pairwise matrix and add up the effects? This is the most serious threat, and for pairwise prediction it may match us. The difference can appear only when neighbors pile up and resources saturate, where additive log slowdowns should overshoot. The train-on-pairs, test-on-k-way experiment settles it. If additive Pitot matches us at k = 5, the link $g$ contributes nothing, and we will report that.

Why not just profile every new job the way iGniter does? Eleven points and roughly four minutes per model is cheap for a small catalog of inference models. It is not cheap for the long tail: ATLAS jobs range from 3 seconds to 7 days, and about 81% of them recur, which means many jobs finish before profiling pays off. We compare the two approaches on accuracy at matched cost, counting profiling runs against our exploration placements.

Why not just train a set network on neighbor sets and skip the matrix structure? Given enough data it may win in distribution. Our bet is that low-rank structure plus a single monotone link extrapolates better to unseen pairs and to larger neighbor sets at sub-1% observation rates. The learning curves across observation rate show where each method wins. If the set network dominates everywhere, the structural claim fails.

Why not just use a symmetric model and skip the asymmetry? A symmetric model would be simpler, and theory handles symmetric factorization more cleanly. CIAO's bully–victim evidence, however, predicts a large antisymmetric component. We measure that component directly and include the fully symmetric model as an ablation.

Decisive Checks

Four experiments decide the claims.

The first is extrapolation. We train on pairwise observations only and report MAPE and coverage of the conformal intervals for k = 3, 4 and 5 on the MPS and Wasm sweeps, comparing link against no link and against additive Pitot. We predict that the gap will widen with k, because saturation compounds as neighbors are added.

The second is the symmetry sweep. We vary the observation rate from 10% down to 0.1% and compare the tied, untied and symmetric models, alongside the measured antisymmetric energy fraction on each hardware class. We predict that the tie helps only below some observation rate and only on hardware where the symmetric component dominates. A uniform benefit or a uniform harm would both falsify this more specific claim.

The third is biased sampling. We compare error on pairs the scheduler never chose, with and without the exploration budget. Success requires recovering most of that error with a budget of a few percent of placements.

The fourth is closed-loop placement. We compare total completion time and service-level-objective violation rates when a greedy scheduler uses each predictor. The comparison uses the Gavel and MPS workloads, not ATLAS, because we have not established that ATLAS records neighbor sets.