NCCL-BOT: Closing the Loop on NCCL's Cost Model with Online Bandits

NCCL-BOT: C LOSING THE L OOP ON NCCL’ S C OST M ODEL WITH O NLINE BANDITS Hanan Shteingart * Amedeo Sapio * Chen Avin Devendar Bureddy Manjunath Gorentla Venkata Srivatsan Krishnan Shie Mannor Sreeram Potluri Gil Shabat Zsolt-Alon Wertheimer

arXiv:2611.11303v1 [cs.DC] 8 Nov 2026

NVIDIA A BSTRACT NCCL picks an algorithm–protocol pair for every collective from an analytic cost model (AUTO) that never sees a measured latency. The model is a strong prior but a brittle final decision: priced on forced-arm runs, its choice is exact on most contexts and badly wrong in a few. We built NCCL-BOT, a tuner plugin that closes the loop: a per-context bandit, warm-started from the model, learns from measured latencies. We replay a forced-arm H100 sweep, tuned at 4–8 nodes and scored at 16–32, and price the model’s choice on the same forced arms; that sweep has no stock-NCCL run. The bandit cuts the contexts where the model’s choice loses more than 10% from 19 to 1 (p99 103% to 9.9%, mean 6.1% to 1.6%; p=0.047 over nine scenarios after Holm correction, three of them unshifted trace scenarios; on the six scale-shifted ones the three bandit comparisons reach the smallest attainable p=0.031, 0.125 after Holm). The prior and continued learning both matter: cold-started bandits, and committing after one probe of each arm, lose more on the mean in every scenario. Supervised selectors fit once on the same data and tuned with the same budget match the mean, and their heavier tail is not significant (7 against 1 contexts above 10%, p=0.06); at seen scales they match or beat online selection. With hyperparameters frozen from H100, UCB1 cuts AUTO’s p99 from 60% to 23% and from 56% to 15% on two GB200 fabrics, but its contexts above 10% go from 16 to 8 on one and from 10 to 13 on the other, and scenario-level tests do not separate the two. Live, on two latency-emulated node sets of one H100 system with one run per policy, the learners repair most of a gross AUTO error on one (selection loss 31% to 6–8% for deterministic Greedy and UCB1; average all-reduce bandwidth 1.18–1.24× stock) but average 0.94–0.99× stock on the other, and on both lose to stock below 1 MiB (on the first through plugin overhead); on H100 the cost model is exact there offline, so small sizes can be left to it. We do not show a net end-to-end win. 1

I NTRODUCTION

Distributed training and inference rest on collective operations (all-reduce, all-gather, reduce-scatter), which the NVIDIA Collective Communications Library (NCCL) (23; 40; 59) implements on GPU clusters. For every collective NCCL chooses, in real time, among many algorithm– protocol pairs (Ring, Tree, and NVLink-SHARP variants crossed with the LL, LL128, and Simple protocols) (23). The default selector is an analytic cost model, NCCL AUTO (Automatic Cost-Model Selection) (40; 58), that predicts the elapsed time of each pair from GPU, topology, network, and protocol properties and plays the argmin. It is calibrated before deployment and then frozen: a Day-0 policy in the Day-0/1/2 taxonomy of Section 2. On our measurements AUTO is exact on most contexts, but when the target fabric, topology, scale, or contention dif*

Equal contribution. Correspondence to: Hanan Shteingart <hshteingart@nvidia.com>. Preprint.

fers from its calibration it mis-ranks the arms on a minority of contexts, and the loss on those contexts is not small. We call a context x = (collective, P, n) a collective type, rank count, and message size. In our replay on a held-out, largerscale split, the model’s choice, priced on forced-arm runs, loses 6.08% of latency on average but 103% at the 99th percentile: the mean hides a thin catastrophic tail (Section 3). Neither AUTO nor the upstream tuner-plugin interface can repair this, because NCCL never returns a chosen pair’s measured latency to the plugin (58). We therefore keep the cost model as a prior and add online feedback (Section 4). NCCL-BOT (Bandit Online Tuning) runs one independent Multi-Armed Bandit (MAB) per context. The cost model plays three roles: it filters implausible arms, warm-starts each arm’s statistics, and scales the reward. We implement the loop inside NCCL with a tuner plugin whose profiler returns measured latency to the policy and whose state is synchronized across ranks.

Thesis and claim boundaries. On a forced-arm sweep, NCCL’s cost-model argmin is exact on most contexts and badly wrong on a few. A per-context bandit seeded by the model removes most of that tail in replay; against fit-once supervised selectors tuned with the same budget it has a similar mean and a narrow tail edge under scale extrapolation, and with hyperparameters frozen it cuts AUTO’s p99 by 2.6–3.7× on two GB200 fabrics, though not its exceedance count on one, at a mean cost on that fabric. We do not establish that stock NCCL has this tail (forcing an arm can change its latency), a mean advantage over supervised selection, a tail advantage over it at seen scales, or that the deployed system is a net win. Seven boundaries apply wherever the result is quoted. (i) AUTO’s tail is 19 of 154 held-out contexts in 7 of 9 (collective, nodes) scenarios; contexts within a scenario are not independent, so we test at the scenario level, where nine clusters limit the resolution (Sections 3 and 6.1). (ii) The mean difference to AUTO (3.99 pp over scenarios, 4.5 pooled) passes our primary scenario-level test, but on the contexts where AUTO is already exact UCB1 pays a small exploration tax (median 0.98%), and on GB200 with MNNVL on the mean is worse than AUTO’s (Sections 6.1 and 6.3). (iii) Supervised selection is matched on the mean, and the tail edge over it is narrow. The strongest supervised selector (gradient boosting with the cost-model prediction as a feature, tuned with the learners’ 151-trial budget; lowest held-out mean and p99 of the eight fits) exceeds 10% on 7 contexts to UCB1’s 1 (p=0.06 at the scenario level); the edge depends on the threshold and holds against UCB1 only (Section 6.1). On same-scale and leave-one-collective-out splits, with a small labelled target-scale sweep, or fit on 4/8/16 nodes and tested at 32, the static fits match or beat UCB1 on the mean (Section 6.1, Appendices I.4 and I.12). (iv) The prior claim is about the leading cold bandits at T =100 under pull-count replay, and about the mean (Section 6.2). (v) The offline replay does not charge the measured NVLS setup stall (5.7–7.8 s on H100) or the plugin’s profiling and synchronization cost (Sections 6.5–8). (vi) The live evidence is two latency-emulated closed-loop campaigns on H100 configurations (one collective, one run per policy), not independent systems. The tuned UCB1 champion ran live and lost several times its offline loss, and in both campaigns the learners lose to stock below 1 MiB, partly to state sync (Section 6.5). (vii) Every offline number is one hardware campaign under a deliberate scale shift, priced on forced-arm jobs (one per arm), so between-job variation is not measured; on H100-B, forced prices were within 1.18× of tuner selection except NVLS and stock differed from both, so the AUTO row is not shown to be stock’s loss (Section 8).

Contributions.

1. A closed-loop tuner plugin returning profiler latency to a per-context bandit that reuses the cost model as filter, warm start, and reward scale (Section 4). 2. A failure mode: on forced arms, AUTO is exact on about 80% of contexts but has a thin tail of misplaced protocol and algorithm crossovers (Section 3). 3. A realized-latency, scale-OOD evaluation against fixed, supervised, and online baselines, showing online selection matching equally tuned supervised selectors on the mean with a narrow tail edge under scale extrapolation, beating commit-once probing (ETC), and a frozen-hyperparameter GB200 replication (Sections 5– 6.3). 4. Deployment lessons from two live H100 campaigns: selection quality, plugin overhead, setup cost, and persize speed against stock (Sections 6.5 and 7).

2

BACKGROUND AND RELATED WORK

We organize prior work by when the selection policy is fixed. Day 0 is the shipped default (AUTO); Day 1 is a onetime calibration fit at deployment and then frozen; Day 2 is continuous adaptation from runtime feedback. We target Day 2 and reuse the Day-0 model as its prior (Appendix Table 27). Our evidence covers short horizons (T =100, one synthetic change), so it supports in-job repair of a misplaced crossover more than long-run adaptation. NCCL cost model and tuner plugins. AUTO ranks pairs by predicted elapsed time from topology and protocol terms at initialization (40; 59; 23; 58). Williams et al. (58) note that the shipped model is calibrated for isolated collectives and recommend external tuner plugins when defaults underperform; vendor plugins do so with fixed rules, e.g. the AWS OFI tuner picks a pair from measured regions over message size and rank count (3). Since NCCL 2.22 the tuner interface (v3) passes the callback getCollInfo the collective type, message size, and a per-collective cost table of predicted times for every algorithm–protocol pair, which the plugin edits to select a pair (39). It passes no measured latency, so a plugin can keep state but NCCL never reports the realized cost of its choice. By design our plugin selects through the cost table and changes only algorithm and protocol, leaving the channel count the v3 interface also returns at NCCL’s default. NCCL also exposes operator-level controls over the same arm set (NCCL ALGO, NCCL PROTO, including exclusion lists such as allreduce:ˆnvlstree), a profiler plugin interface, and NCCL RUNTIME CONNECT, which connects peers at init rather than on first use (40); the profiler and tuner are separate plugins. We have not established which parts of our reward channel and state synchronization could be reproduced without modifying NCCL (Appendix F).

2 / 46

MPI and GPU collective autotuning. Offline MPI autotuners freeze a lookup table (Open MPI’s tuned decision rules (41; 42)), a task-level cost model (HAN (36)), or a supervised predictor after a benchmark campaign (26; 56; 57); our fit-once regressors are Day-1 baselines of this kind, including a variant that takes the cost model’s own prediction as a feature. Online systems tuners adapt from runtime feedback: STAR-MPI (18) selects among MPI collective algorithms by measured performance inside a running application, OMPICollTune (25; 50) does so incrementally, and AutoCCL (61) tunes NCCL’s algorithm, protocol, and resource parameters (channels, chunk size, threads) during the early iterations of a training job. None seeds a regret-minimizing policy from a shipped cost model. We search only algorithm–protocol pairs, so composing with AutoCCL’s resource parameters is untested. TACCL (47), MSCCLang (15), TE-CCL (35), ForestColl (63), and MSCCL++ (27) synthesize or program schedules and TCCL (29) profiles ring paths, which enlarges the arm set rather than selecting among NCCL’s fixed pairs, and production stacks such as NCCLX (48) extend NCCL itself at 100k-GPU scale. Conservative bandits (60) formalize “never fall far below a default policy,” which is the role AUTO plays here; our warm start and filter are a pragmatic version of it, without that guarantee. Seeding a learner from a prior has theory for supervised-data warm starts (62) and for hints of unknown quality (9); our pseudo-count is the corresponding trust knob, tuned and not derived. Our claim is about the tail of the loss, a risk criterion in the sense of risk-averse bandits (43; 12), yet every policy here is tuned on the mean loss, not on the tail. The Day-0 prior descends from Hockney/LogP models (21; 16).

Explore-then-commit for NCCL. Madan et al. (37), in a course project report that we cite as prior art and not as a peer-reviewed comparison, describe a live NCCL plugin that explores pairs round-robin, commits to the IQRtrimmed fastest pair, and falls back to AUTO through a 5% safety gate. They report 25–42% latency gains on A100. Their design is explore-then-commit with a permanent commit, and the gate is not a warm start. We include a re-implemented, search-tuned round-robin row (Table 1); it is not a matched head-to-head with their live plugin, and our results neither reproduce nor validate theirs.

Bandits. We use UCB1 (5), KL-UCB (19), Softmax, Gaussian Thompson sampling (52), and adversarial variants (6; 46; 64; 22), and discuss discounting for nonstationarity (30; 20) in Section 7. Appendix C specifies every family.

3

FAILURE MODE : ON FORCED ARMS , AUTO IS USUALLY EXACT, WITH A THIN TAIL

We audit AUTO’s argmin against measured sweeps on the H100 grid (n=300 contexts with at least two measured arms). AUTO picks the measured-best arm on about 80% of contexts (pooled error rate 20.0%), so its typical loss is exactly zero. The errors are not benign: over all contexts AUTO’s selection-priced TRLT is 5.04% on average and 75.4% at p99, and a wrong choice can cost more than the best arm’s entire latency. The cost model exposes a decision-time confidence signal, the predicted runner-up margin m = µ̂(2) /µ̂(1) − 1 between its two best predictions. Appendix Figure 13 audits it as a gate. Retaining only contexts with m ≥ 0.50 keeps 45.3% of them and cuts the error rate to 3.7%, the mean to 0.49%, and the p99 to 16.4%. So the model knows when it is unsure, and the low-margin contexts carry disproportionate tail loss. But a static selector must still decide on those contexts, and its margin cannot reveal the penalty of a wrong choice; only a measurement can. Learning a static selector offline closes the gap only in part: a gradient-boosted selector fit with fixed settings on the training contexts with the cost model’s prediction as a feature nearly eliminates training error (0.04% TRLT) yet pays 1.76% mean and 36.9% p99 on the larger-scale test (selection-priced; Appendix D). Where the tail lives. AUTO loses more than 10% on 19 of the 154 held-out contexts, in 7 of the 9 (collective, nodes) scenarios (Appendix Tables 29 and 30). On all 19 the forced-arm sweep measures a protocol or algorithm crossover at a different message size than the cost model predicts (predicted margins 0.06–0.57). These are forcedarm prices, not stock’s (Section 8). Within-pool sampling noise does not explain them (Appendix I.1).

4

M ETHOD

Problem. Each collective request arrives with context x = (collective, P, n). The action space is a finite set of algorithm–protocol arms A(x); pulling arm a yields latency Ta with unknown mean µa (x). A policy π maps x to an arm A ∈ A(x). Fixed selectors (AUTO, supervised regressors) ignore feedback; online bandits consume measured latency and revise future choices. Production jobs revisit few contexts: a Llama3-8B torchtitan training trace from CCL-Bench (17) collapses 719 collective calls onto only nine contexts (80× mean reuse), two of which carry 90% of the calls (Appendix B). We therefore run an independent bandit per context with no parameter sharing, instantiated lazily on the first visit; contextual alternatives are

3 / 46

Algorithm 1 Per-context bandit loop for fixed x = (collective, P, n) Require: A, {µ̂(a)}, ρmax , T , policy π, reward r(·) 1: µ̂min ← min{µ̂(a) : µ̂(a) defined} 2: A′ ← {a ∈ A : µ̂(a) undefined or µ̂(a) ≤ ρmax µ̂min } ▷ Eq. (2) 3: Initialize π from {r(µ̂(a))}a∈A′ ▷ warm start 4: for t = 1, . . . , T do 5: At ← π.S ELECT(A′ ); observe Xt ; π.U PDATE(At , r(Xt )) 6: end for

in Appendix G. Reward and cost-model priors. The cost model plays three roles: arm filter, warm-start prior, and reward scale. Bandits maximize the scale-free ratio µ̂min r(t) = , t

(1)

where µ̂min = min{µ̂(a) : µ̂(a) defined} is the best costmodel prediction on the offered set, so r=1 means “as fast as AUTO expected,” not oracle-optimal. The arm filter ρmax =2 drops arms with µ̂(a) > ρmax µ̂min (undefined predictions are kept): A′ = {a ∈ A : µ̂(a) ≤ ρmax µ̂min or µ̂(a) undefined} . (2) Warm start seeds each arm’s statistics from {r(µ̂(a))} with a tuned pseudo-count before the first pull; cold start omits it. Featured policy: deterministic p UCB1. The   policy plays At = arg maxa∈A′ r̂a + α 2 ln Nt /na (Appendix C), with r̂a a clipped-SGD mean reward and na its count, seeded by warm start. It departs from textbook UCB1 (tuned α, pseudo-count, and decaying step size), so the regret theory of Appendix C does not apply to it. With a warm-start pseudo-count no arm is unexplored, so the choice is a deterministic function of the replicated statistics. Every rank therefore selects the same arm without shared randomness, provided the statistics stay replicated and the update predicate is collectively agreed (Appendix F; fallback untested, and not verified live), and replay has zero seed variance. The tuned champion has α=0.093 and a pseudo-count of 2.89 (Appendix E). Trainmean selection ranks KL-UCB first (0.845%), then UCB1 (0.864%) and Softmax (0.868%): a tight cluster, so we feature UCB1 on systems grounds (deterministic, simplest to reason about in a plugin), not because it won; the choice was made before realized accounting existed and is not a pre-registration. Softmax and KL-UCB are reported beside it in every table, and re-tuning on the realized objective leaves the three within noise (Appendix I.13). Plugin. Appendix Figure 10 shows the deployed loop. NCCL invokes the tuner with the cost table and job dimensions; the bandit selects an arm and its parameters flow

back to the collective; the profiler returns the measured latency as the reward; and state is synchronized across ranks. Upstream NCCL provides the per-call cost-table override; the profiler→tuner reward channel, durable percontext state, and a cross-rank synchronization API are our additions in SPCX, the unreleased NVIDIA Spectrum-X NCCL environment plugin (Appendix F). The offline evaluation updates the policy after every collective and treats synchronization as free; its measured live cost is reported separately (Sections 6.5 and 7).

5

E VALUATION PROTOCOL

Data and replay. The primary ground truth is an openloop, forced-arm NCCL sweep (one job per arm, the arm forced through NCCL ALGO and NCCL PROTO, every other NCCL parameter at its default) on Dell HGX H100 nodes with Spectrum-X Ethernet (8 GPUs per node; NCCL 2.30.4): three collectives (all-gather, all-reduce, reduce-scatter) at 4, 8, 16, and 32 nodes over 26 message sizes from 512 B to 16 GiB, with 100 measured iterations for every offered arm (Appendix Tables 26 and 6); its cost tables come from the same system. Each iteration’s latency is the per-collective time that GPU 0 of the job reports in the sweep’s nccl-tests output (not the maximum over ranks); which nodes each per-arm job ran on, and when, was not recorded. Whether forcing an arm prices it as tuner selection does is untested on this sweep (on H100-B they agreed except NVLS; Appendix I.1); the live campaigns (Section 6.5) select through the cost table. The cost model marks CollNet, pure NVLS, and PAT not applicable on this fabric, so the arms are Ring×{LL, LL128, Simple} on every collective plus Tree×{LL, LL128, Simple} and NVLSTree/Simple on all-reduce; AUTO and the bandits draw from the same set. We replay each arm’s measurement pool sequentially in iteration order, one pull per step for T =100 steps (the pool depth). Sequential replay preserves NCCL’s lazy-initialization transient, which makes the first ∼10 samples of an arm heavy-tailed (Appendix B), so the first pulls of an arm replay it. Metrics. We score in the time domain. With µ̄a the steady-state mean latency of arm a (iterations 11–99) and a⋆ = arg mina µ̄a , the per-step Relative Lost Time (RLT) and path Total Relative Lost Time (TRLT) of a selection trace (A1 , . . . , AT ) are RLTi =

µ̄Ai − µ̄a⋆ , µ̄a⋆

PT ⋆ i=1 µ̄Ai − i=1 µ̄a . PT ⋆ i=1 µ̄a

PT TRLT =

(3) This selection-priced TRLT charges every step at the chosen arm’s steady mean, so it under-charges the cost of switching to a cold arm. The realized TRLTPinstead sums the latencies the policy was actually served, t Xt , against

4 / 46

a realized sequential oracle, the measured-best arm replaying its own pool for the same T steps pay P (so both P sides ⋆ the transient once): TRLTreal = t Xt / t Xt − 1. The two biases point in opposite directions: selection pricing under-charges arm switches, and realized replay overcharges them. In realized replay a policy’s k-th pull of an arm is served that arm’s k-th swept sample however late it occurs, so a rarely played arm keeps paying lazyinit samples that production would have warmed. Realized TRLT is the headline; selection-priced values are secondary columns. The learners maximize a reward proportional to 1/X while TRLT ranks arms by mean latency; over all 306 grid contexts the two pick a different best arm on 2, at most 0.3% apart. Neither accounting charges the one-time NVLS setup stall that the live campaigns measured (5.7–7.8 s on H100, Section 6.5); we re-price the H100 replay separately with a sensitivity range (Section 7).

Table 1. H100 sweep, scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Realized TRLT charges the latencies actually served, first-use transients included; selection-priced TRLT charges each step the chosen arm’s steady-state mean. AUTO is the cost model’s choice priced on forced-arm runs. The realized columns are the headline. Mean ± SEM over contexts; p99 is the 99th percentile over contexts and n>10 the number of contexts whose TRLT exceeds 10%. Supervised rows are fit once on the train contexts, with fixed settings or tuned with the learners’ 151-trial budget (Appendix Table 41); “+cost” adds the cost model’s predicted latency as a feature. Bold: best value per column (lower is better). Random is a reference and is not bolded. Selection TRLT Policy

Split and replication. The split is deliberately scaleout-of-distribution. Hyperparameters are tuned only on the 146 contexts at 4 and 8 nodes; the 154 test contexts are all 16/32-node contexts plus eight Llama3 trace contexts mapped onto 4-node pools. Optuna’s TPE sampler tunes each of 14 online families for 151 trials on mean train selection-priced TRLT, and the frozen winner is replayed once on test (Appendix E). The tuning objective is selection-priced train TRLT; we do not re-tune on the realized metric we report, and we show both. The unit of replication is the context, not a training job. Stochastic policies are averaged over 20 seeds per context; tables report mean ± SEM over contexts, p99 is the percentile across the 154 contexts, and intervals are bootstrap resamples of contexts (each context its own cluster). The 154 contexts are not independent, however: they come from nine (collective, nodes) scenarios with adjacent message sizes, so we also resample whole scenarios and blocks of four adjacent sizes (Appendix Table 35). Our inferential test is an exact signflip test over the nine scenarios (Section 6.1). Context-level paired statistics (Wilcoxon signed-rank, exact McNemar on exceedance counts, CVaR5% , quantile profiles; Appendix Table 34) treat contexts as exchangeable, so every p-value from them in this paper is descriptive. We report them, with interval estimates and full distributions, in the spirit of (1). Baselines. AUTO; uniform Random; fit-once supervised regressors (linear, random forest, gradient boosting) trained on the train contexts, with and without the cost model’s own prediction log µ̂(a) as a feature (“+cost”); the tree models appear with fixed sklearn settings (300 depth-4 trees at rate 0.08, 400 forest trees with leaf size 2) and tuned like the learners, with 151 TPE trials (trial 0 the fixed settings) minimizing selection-priced loss on validation folds inside the train partition that copy the held-out shift (here, leave one train node count out; Appendix I.6); explore-

NCCL AUTO Supervised GBM+cost, fixed Supervised GBM+cost, tuned ETC (m=1, k=1) Softmax UCB1 KL-UCB Random

Realized TRLT

mean (%)

mean (%)

p99 (%)

n>10%

5.99±1.58 1.76±0.51 1.30±0.42 2.70±0.49 0.93±0.11 1.00±0.13 1.18±0.24 45.22±3.72

6.08±1.58 1.78±0.50 1.37±0.43 4.74±0.75 1.75±0.22 1.61±0.19 2.11±0.36 46.85±3.79

103.3 32.2 27.3 63.0 11.9 9.9 22.7 190.3

19 10 7 11 5 1 4 125

then-commit (ETC, m=1) and the round-robin variant of Madan et al.; and the 14 tuned online families.

6

R ESULTS

6.1

H100: AUTO, supervised, and online selection

Table 1 and Figure 1 give the headline. AUTO has no realized loss on 79% of the 154 held-out contexts (85% for GBM+cost; a realized TRLT can be slightly negative when a non-oracle arm happens to serve less time than the oracle’s pool), but its realized TRLT is 6.08% on average and 103.3% at p99, and it loses more than 10%, 50%, and 100% on 19, 6, and 2 contexts, in 7 of the 9 (collective, nodes) scenarios. Warm-started UCB1 lowers the mean to 1.61% and the p99 to 9.9% and never loses more than 50%; it exceeds 10% on one context, in 1 of 9 scenarios (Appendix Table 32). Softmax reaches 1.75% and 11.9%. Contexts are not independent units, so our primary test procedure is the exact sign-flip test over the nine (collective, nodes) scenarios, for the mean difference and for the difference in contexts above 10%. It rejects for both. The mean difference AUTO−UCB1 is 4.46 pp over contexts (scenario-clustered bootstrap CI [2.8, 6.3]) and 3.99 pp over the nine equally weighted scenario means, which the sign-flip tests (p=0.016; a wild-cluster bootstrap-t (10) on the context-weighted mean agrees), and the exceedance difference has the same p=0.016; the 10% threshold was chosen after seeing the results, and at 20% the counts are

5 / 46

probe per arm, no margin) coincides with ETC below when NVLS is offered, 4.74% mean and 11 contexts above 10%, worse than UCB1 in all nine scenarios (p=0.004; 3.21% against 1.23% with NVLS excluded; 3.26% with ETC’s adaptive-observed-max reward wrapper), and variants that keep AUTO’s arm unless another is 5% faster do no better (Appendix Table 38).

Figure 1. Realized TRLT survival function P (TRLT > τ ) over the 154 held-out contexts (logarithmic axes; seeds averaged per context; shaded: 95% bootstrap CI over contexts). Circles on the left axis give P (TRLT > 0), counting values above 10−9 % so that floating-point round-off is not counted as loss; a realized TRLT can be negative (a non-oracle arm luckier than the oracle’s pool; 13% of AUTO’s contexts) and then counts as no loss. The online policies pay a small exploration cost on many contexts but cap the tail, while AUTO’s tail passes 100%.

15 against 0 (p=0.016), at 5% 25 against 13 (p=0.062; Appendix Table 39). Over the four comparisons our claims rest on (these two, warm against cold-tuned UCB1, and tuned GBM+cost against UCB1 on exceedance) Holm’s correction gives p=0.047, 0.047, 0.016 and 0.062 (Appendix Table 33). Three of the nine scenarios are the 4-node trace contexts, which are not scale-shifted; restricted to the six 16/32-node scenarios, the first three each reach the smallest p six clusters allow (0.031), 0.125 after Holm, so no scale-shifted comparison survives correction, although all six scenarios favor UCB1 on the mean. Choosing the oracle on odd iterations and pricing on even ones leaves AUTO at 6.0% and 18 contexts above 10% and UCB1 at 1.0% and none. The same test does not separate AUTO from ETC (p≈0.4; Appendix Table 31). On individual contexts AUTO is usually the better policy: it has no loss on most of them, so UCB1’s median exploration tax of 0.98% makes AUTO better on 40% of contexts and UCB1 on 16% (62 against 24 contexts; descriptive, since contexts within a scenario are not independent). McNemar on the counts and CVaR5% (77.2% against 9.1%) assume exchangeable contexts and are descriptive (Appendix Table 34). The same scenario-level test finds no UCB1-overAUTO difference on either GB200 fabric (p=0.91, 0.81), so the cross-platform support for the tail claim is thin. UCB1 is close to AUTO plus a safeguard: it plays AUTO’s arm on 85% of steps, leaves it on 56% of contexts (a mean of 1.6 distinct arms), and plays the measured-best arm over its last 20 steps on 82% of contexts against AUTO’s 79%. Continued learning still matters: the train-best of 24 probeand-commit settings (one transient sample discarded, one

Supervised selection is the harder comparison. With fixed settings the strongest fit, GBM+cost, ties the mean (+0.17 pp over contexts, +0.05 over scenarios, p=0.88), is exact on 85% of contexts, and exceeds 10% on 10 contexts to UCB1’s one (p=0.031; Appendix Table 48). Tuned like the learners, GBM+cost improves to 1.37% mean, 27.3% p99, and 7 contexts above 10%: 0.24 pp below UCB1 on the context mean but 0.07 pp above it on the scenario mean the primary test uses (p=0.91), with an exceedance difference the primary test only borderline separates (p=0.06; Appendix Table 41). Resampling scenarios, its p99 and CVaR5% exceed UCB1’s by 17.5 ([2.6, 35.9]) and 11.3 pp ([3.3, 21.6]), but the edge is specific to UCB1: against Softmax and KL-UCB these intervals include zero (Appendix Tables 40 and 39). With NVLS excluded (an exploratory comparison outside the Holm family), tuned GBM+cost has 1.46% mean, 38.6% p99 and 9 contexts above 10% against UCB1’s 1.23%, 11.2% and 2 (exceedance p=0.031, mean p=0.42; Appendix Table 37). Tuning mostly drops the node-count feature, which trees cannot extrapolate; the other fits are worse (Appendix Table 55). On H100, then, online selection matches supervised selection on the mean, with a narrow tail edge at the held-out scales. Once they see near-target scale, static fits match or beat the online policy, which needs no target-scale labels: one sample of every arm at every fourth 16/32-node size gives GBM+cost 1.01% mean against UCB1’s 1.68% (p99 25% against 10%; Appendix I.12), and fit on 4/8/16 nodes and tested at 32 it reaches 0.47% and 7.1% against 1.89% and 11.0% (Appendix Table 46). The commit-once policies do less well on the realized tail. ETC (m=1 with the first sample discarded; the tuned Madan round-robin champion coincides with it) is cheap selection-priced (2.70% mean, 8.7% p99) but costs 4.74% mean and 63.0% p99 on realized latency with 11 contexts above 10% (paired p99 difference to UCB1 53.1 pp, context-bootstrap CI [4.8, 61.7], scenariobootstrap [0.6, 61.4]). It is the train-best of an 18-point (m, k) grid, and Madan-style round-robin does no better (5.9–13.3% mean; Appendix Table 43). With NVLS excluded, ETC’s tail falls to 13.8% (Section 7). The three leading online policies are mutually within noise (other families: Appendix Table 55). Robustness to the split and to tuning. Re-tuning on nine further splits and seeds (Appendix Table 36) keeps

6 / 46

UCB1 well below AUTO (0.76–2.68% against 3.96–6.08% mean). On same-scale random splits, however, the best tuned static fit has the lower mean (0.64–0.76% against UCB1’s 1.24–1.69%) and a comparable tail (9.6–13.3% p99 against 9.5–15.2%), and it also has the lower mean when one collective is held out (Appendix Table 41). The tail edge over supervised selection is therefore a scale-shift result. Re-tuning on the realized objective leaves the leaders within noise (Appendix I.13). 6.2

The prior: matched, independently tuned, and transient-controlled cold ablations

Table 2 toggles only the cost-model prior for each tuned family on realized TRLT, at the warm-tuned knobs. That handicaps the cold arm: UCB1’s α=0.093 and pseudocount 2.89 only make sense with a prior, so “cold 8.82%” partly measures an untuned policy. We therefore also tuned every warm-capable family cold: a separate Optuna study with warm start pinned off, on the same split, objective, sampler seed, and 151-trial budget (Appendix Table 42). Tuning helps the cold arm (UCB1 8.82% → 4.84%, Softmax 6.71% → 4.77%), but the warm champions stay better. Warm UCB1 has 1.61% against 4.84% (paired ∆= − 3.22 pp, CI [−4.76, −1.97]) and is lower in all nine scenarios, so the primary sign-flip test gives its minimum p=0.004, as it does for Softmax and KL-UCB (Appendix Table 48). The five leading cold families keep 4.27–4.97% mean and 33.9–64.5% p99 against 1.61–2.17% and 9.9– 23.3% warm. The cold-tuned UCB1 is near-greedy after one pull per arm and shares ETC’s 63.0% p99, and a 50– 100× wider search over three seeds finds the same champion (Appendix Table 45). So the warm start, on top of the arm filter that cold policies also use, is necessary at T =100 for these families, but the untuned-cold gap overstated it: the paired warm advantage is about 3 pp, not 7 pp. Realized replay serves a cold policy’s early pulls each arm’s lazy-init samples, so we controlled for that artifact three ways (Appendix Tables 43 and 44). (i) Selectionpriced accounting, which charges no transient, still favors the warm champions by 1.6–1.8 pp (UCB1 1.00% against the cold-tuned 2.78%; paired CIs exclude zero). (ii) With NVLS excluded, the realized advantage is 1.6– 2.1 pp (UCB1 1.23% against 3.31%, lower in all nine scenarios, p=0.004), but the tail gap disappears. Cold UCB1’s and Softmax’s p99 falls from 63% to 12%, and both warm and cold have two contexts above 10%, so the cold tail of 34–65% above is largely NVLS first-touch contamination, not worse decisions. (iii) Discarding k≥2 first samples is worse than k≤1 for ETC and every cold family, because a discarded pull is still a served step. So the prior is necessary for the mean at T =100, not a replay artifact, while its realized-tail effect is mostly an NVLS effect. This holds for the leading families: FPL, EXP3, Tsallis-Inf, UCB-V

Table 2. Warm versus cold start for the three champion families on the H100 sweep, scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). Only the cost-model prior is toggled, at the warm champion’s hyperparameters. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Realized TRLT charges the latencies actually served, first-use transients included. Mean ± SEM and p99 (99th percentile) over contexts; ∆ is the paired per-context warm−cold mean in percentage points, with a Wilcoxon signedrank p over contexts (descriptive, since contexts are not independent; the scenario-level test is in Appendix Table 48). All families, selection-priced: Appendix Table 7. Bold: best value per column (lower is better). Cold (no prior) Family

mean (%) p99 (%)

UCB1 8.82±1.42 Softmax 6.71±0.90 KL-UCB 4.94±0.73

Warm (prior)

Warm−cold

mean (%) p99 (%) ∆ mean (pp) Wilcoxon p

98.7 1.61±0.19 49.5 1.75±0.22 40.8 2.11±0.36

9.9 11.9 22.7

-7.20 -4.96 -2.83

<0.001 <0.001 <0.001

and UCB-tuned are nearly insensitive to the prior (at most 0.72 pp; Appendix Table 7). 6.3

GB200: cross-architecture replication with frozen hyperparameters

Table 3 reruns the policy ladder on GB200 sweeps with every hyperparameter frozen from the H100 tuning (train: 4/8 nodes; test: 16/32 nodes), once per fabric configuration, now with realized accounting and paired tests. After the same filter the arms are Ring and Tree pairs, plus PAT/Simple (all-gather, reduce-scatter; MNNVL off) and NVLSTree/Simple (all-reduce; MNNVL on). What reproduces is weaker than on H100. With MNNVL off, UCB1 has 2.59% realized mean and 23.1% p99 against AUTO’s 3.80% and 60.1% (8 against 16 contexts above 10%, McNemar p=0.057; paired mean difference 1.2 pp, CI [−0.3, 3.1]; these context-level p-values are descriptive). With MNNVL on, AUTO is not worse: its realized mean (2.65%) is below UCB1’s (3.54%) and its count of contexts above 10% is lower (10 against 13). Only the p99 favors UCB1 (15.2% against 56.3%), and Softmax (2.61%, 5 contexts) is the only learner that is not worse than AUTO on the mean. Commit-once ETC is worse than UCB1 with MNNVL off (20 against 8 contexts above 10%, McNemar p=0.008, descriptive) and indistinguishable with MNNVL on. Against AUTO, online selection is a tail safeguard with MNNVL off; with MNNVL on it is worse on the mean and on contexts above 10%, with a smaller p99. At scenario level UCB1 vs. AUTO is null on both fabrics (mean p=0.91, 0.81; n>10% p=0.13, 0.72). Two caveats bound this result. First, the GB200 AUTO row

7 / 46

Table 3. GB200 sweeps, scale-out-of-distribution split (train 4/8 nodes, test 16/32 nodes: 164 held-out contexts with multi-node NVLink (MNNVL) off, 158 with it on). Online hyperparameters are frozen from the H100 tuning. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Realized TRLT charges the latencies actually served, first-use transients included; selection-priced TRLT charges each step the chosen arm’s steady-state mean. Columns: selection-priced (sel.) and realized (real.) mean, realized p99 (99th percentile over contexts), and n>10 , the number of contexts with realized TRLT above 10%. AUTO is a cost-model-decision replay over forced-arm measurements. Bold: best value per column (lower is better). MNNVL-off

MNNVL-on

sel. mean real. mean real. p99 n>10 sel. mean real. mean real. p99 n>10

Policy NCCL AUTO ETC (m=1) Softmax UCB1 KL-UCB

3.43 3.42 1.22 1.07 1.03

3.80 5.47 2.86 2.59 2.58

60.1 40.5 22.8 23.1 20.3

16 20 7 8 5

2.02 2.55 1.63 2.46 2.21

2.65 3.60 2.61 3.54 3.35

56.3 27.1 25.8 15.2 23.2

10 9 5 13 7

is also priced on forced arms; the dataset’s notes record contexts where an unpinned AUTO run and the forced arm differ by more than 50%, but those runs were excluded from the processed data and are not analysed here. Second, each fabric has a single sweep. 6.4

Workload weighting: Llama3 trace replay

Replaying two cycles of the Llama3 CCL-Bench trace (nine contexts), warm UCB1 finishes at 0.22% cumulative relative lost time against 1.08% for AUTO (selectionpriced, one 16-GPU trace; Appendix H). The per-context tail above is unweighted, whereas a real job weights contexts by call count. Its 4-GPU groups are mapped onto 4node pools by rank count, so the replay weights contexts realistically but not their intra-node arm landscape, and its test contexts are not scale-shifted. 6.5

Two closed-loop campaigns on H100

The live evaluation is limited to H100: two node sets of the Spectrum-X H100 system that also ran the primary sweep, so they are not independent systems (SPCX plugin, AllReduce only, one run per policy). H100-A is 8×HGX H100 (64 GPUs) on Spectrum-X Ethernet with a development build of NCCL 2.30.7; H100-B is the same hardware over RoCE with NCCL 2.32.0a4, on the nodes of a forced-arm sweep. Both ran NCCL’s long-haul latency emulation (NCCL IB LH LATENCY=40), which the primary sweep’s metadata do not record (Appendix F). UCB1, Softmax and Thompson ran the warm-started offline champions (UCB1 with its clipped-SGD mean); Greedy (ε=0 from the cost-model prior) and ETC with one sample per arm are implemented in the plugin itself, and ε-greedy ran an outdated ε=0.033 (decaying) instead of its tuned ε=0. No run

used the constant-gain mean or excluded NVLS; Appendix Table 20 separates selection, overhead and setup cost. Selection quality. Priced by a profiler against a reconstructed oracle (setup excluded; Appendix Table 21), AUTO pays 31.4% mean selection TRLT on H100-A (worst size 77.3%), committing to NVLS TREE SIMPLE across 256 MiB–4 GiB where ring pairs win. On H100-B, with the same flag but one long-haul queue pair per connection instead of ten, the same choice at 256 MiB–2 GiB is within 8.2% of the best forced arm, so the flag alone does not produce the error. Every learner but ETC (22.0%) repairs most of it; UCB1 leaves AUTO’s loss after about 30 collectives per size and plays the oracle arm over the last 100 (Figure 2). Over all 26 sizes UCB1 reaches 8.28%, the thirdlowest mean of six learners (mean rank 4.0), behind εgreedy (2.85%; stochastic, with an untuned ε) and Greedy (6.43%), with Thompson and Softmax at 8.49–9.00%. On H100-B (no AUTO profiler trace) UCB1 is fourth of six (2.18%; best Greedy, 0.59%). So the offline champion kept its relative cut over AUTO (74% live, 80% offline) but not its loss level (1.53% against AUTO’s 7.83% on the primary sweep’s 8-node contexts of the same sizes) or its rank. Against stock. On H100-A, wall-clock bus bandwidth averaged over the 26 sizes rises 1.18–1.24× over stock for the adaptive learners (1.28× for ETC), carried by the sizes of AUTO’s error. Below 1 MiB every adaptive learner is slower than stock at all 11 sizes (median +11 to +14%), and not by selection: there they play AUTO’s arm on 93– 100% of timed collectives with no higher kernel time than the plugin run with AUTO’s selection, and a state sync every 16 collectives, their inferred period, alone adds 13% host time (4% every 64; Appendix F). On H100-B, against its only stock run (a separate job), every learner is faster at 1–8 MiB (median 1.21–1.31×), on par from 16 MiB and slower below 1 MiB (0.59–0.65×; Appendix Table 17); the 1–8 MiB gain is not selection either, since the forced run of the argmin the learners play is itself 1.26–1.51× faster than stock. Overhead and setup. With AUTO’s selection untouched, profiling alone costs 2.1% of average bus bandwidth on H100-A and a sync every four collectives 7.5% (one run each; Appendix Tables 18 and 19). Both campaigns stall once on the first use of NVLS TREE SIMPLE (median 6.6 s on H100-A, 5.8 s on H100-B), which the offline harness under-charges about 580-fold or more (Appendix F). Reading. Good selection is needed but is not enough on its own, and the live evidence does not show a net win. On H100-A, where AUTO makes a gross error at large sizes on an emulated configuration, the learners beat stock on average bandwidth while losing at every small size to plugin

8 / 46

Figure 2. The offline UCB1 champion learning live (H100-A, 8 nodes, AllReduce, back-to-back, the 11 sizes from 16 MiB, where AUTO’s error lies; one run). Left: bus bandwidth per window of the 400 collectives at each size (error bars: SEM over the window’s collectives), beside the oracle and AUTO. Right: lost bandwidth against the oracle per collective, averaged over the 11 sizes (band: SEM across sizes). Collectives 1–10 replay AUTO’s arm (warm start); the loss averages 20.6% over collectives 11–30, 6.9% over 31–100 and 0.2% over the last 100, against 18.8% for AUTO throughout. Each collective is charged its arm’s profiler mean latency pooled over all runs, the learners’ included; “AUTO” is the plugin run with AUTO’s selection. Over all 26 sizes this run ranks third of six learners (Appendix Table 21).

cost; on H100-B they win at 1–8 MiB, where stock is itself slow. These are deployment lessons, not a replication; we have no end-to-end step-time measurement and no test under CUDA graphs, multiple communicators, or overlap.

7

D ESIGN LESSONS

Do not learn where the model is right. Our offline results assume synchronization is free, but a live sync costs about 0.5–0.9 ms regardless of message size (Section 6.5), which matters where collectives are short, also where learning has least to find. The cheapest update is none: on the H100 sweep AUTO is exact on every held-out context below 1 MiB, and a size gate that leaves those contexts to AUTO (threshold chosen on train) lowers UCB1’s test mean from 1.61% to 1.15% at a p99 of 9.5% (better in 5 of 9 scenarios, worse in none, p=0.06). Below the gate the plugin would skip timing and sync, a saving not measured live. The gate is platform-specific: on GB200 AUTO errs at small sizes too (Appendix I.11).

Filter, forget, and the filter’s cost. The ρmax =2 arm filter never removed a measured-best arm and leaves test TRLT unchanged (1.00% vs. 1.01%) while nearly halving exploration (Appendix Table 13). Under a synthetic bestto-worst pool swap, a frozen cost model pays 45% dynamic TRLT, ETC 50.9%, plain Softmax 31.6%, discounted Softmax 5.96%, and UCB1 is already robust (6.60%). This is bound to T =100 and one change (Appendix Table 8).

Price setup and transition costs. The NVLS stall is the clearest deployment lesson, and we price it three ways (Table 23). Charged once per context replay, the ranking inverts (realized mean 546% for AUTO, 1,210% for UCB1, 61% for GBM+cost), an upper bound because a communicator pays the stall once. Charged once per communicator size, every NVLS-touching policy pays the same two tolls and the ranking becomes that of the traffic-weighted pooled TRLT: at V =103 visits per context it is 1.8–1.9% for UCB1, Softmax, and KL-UCB, 2.1% for ETC, 2.4% for GBM+cost, and 4.1% for AUTO. Excluding the setup arm from the plugin’s arm set is the recommended configuration (NCCL ALGO=allreduce:ˆnvlstree would remove it from selection; whether that also avoids the setup is untested), chosen after seeing the test results. AUTO stays at 6.3% mean and 111% p99, so its tail is not an NVLS effect; UCB1 reaches 1.23% and 11.2%, Softmax 1.22% and 8.6%, and ETC 3.26%, its tail falling from 63.0% to 13.8% (ETC−UCB1 2.0 pp, all nine scenarios, p=0.004; 3 against 2 contexts above 10%). With a constant-gain mean r̂a ← (1 − η)r̂a + ηr (η=0.1 chosen on train), the estimator we recommend for a long-lived tuner, UCB1 has 1.21% mean and 5.7% p99, not separated from the champion here (mean p=0.89); its case is drift (Appendix I.10). Train preferred a 1 ms flush (1.11%, 8.0%); we keep the percollective schedule. Against commit-once, learning lowers the mean but not the tail; the realized-tail gap in Table 1 is largely NVLS first observation. Pre-warming such arms instead (perhaps with NCCL RUNTIME CONNECT=0) is untested.

9 / 46

8

L IMITATIONS AND ARTIFACT AVAILABILITY

Evidence scope. The primary replay is one hardware campaign (H100, Spectrum-X Ethernet, three collectives) chosen as a domain-shift stress test of the shipped model; the finding may be specific to the NCCL 2.30.4 model on Spectrum-X. Each arm’s pool is 100 iterations from one isolated forced-arm job, so job-to-job variation is not measured, and the AUTO row is the cost model’s choice priced on forced arms. Stock and repeated jobs, repeated or nonemulated live runs, and a live run of the recommended configuration or a size gate need new runs we have not done. On H100-B (all-reduce, 8 nodes, separate jobs) the learners started every size on the exported argmin, and arms they kept for a whole size cost 1.02–1.18× their forced runs except NVLSTree/Simple (0.70–0.98×), consistent with forcing slowing only NVLS among the arms checked; stock (no plugin) differed from both (unlogged choice or channels, or job variation). So there the AUTO row is the cost model’s choice applied through the tuner, not necessarily stock’s, and an operator should compare a pass-through plugin with stock before crediting gains to learning (Appendix I.1). This qualifies the offline magnitudes, not the mechanism: a deployed learner scores the arms it actually runs, so if forcing changes an arm’s latency the loop learns the deployed latency, while the cost model’s choice stays fixed. The horizon is a data limit (T =100), the ranking is horizon-bound (Appendix Table 11), and the drift evidence is one synthetic swap, so behavior at T ≥104 is untested. The search space is algorithm–protocol pairs only (a median of two arms after filtering). Replay fidelity. The sweeps are isolated microbenchmarks: no cross-arm connection reuse, no compute– communication overlap or concurrent communicators, and measurement noise independent across arms, whereas real noise is correlated in time. The reward is collective latency, not step time, so we cannot say how selection gains translate into job throughput. Pull-count replay is a simulator built from forced-arm pools, not an unbiased replay estimator in the sense of Li et al. (33). Live campaigns and deployability. The two H100 campaigns each cover one collective at one scale, one run per policy, and latency emulation, with oracles pooled across the scored runs. The plugin builds used live were not recorded with the runs, so we cannot tie them to a source revision; its interface version, sync rule and transport, how the stochastic learners shared draws, and how UCB1’s clipped-SGD state was reconciled across ranks are unknown; with data checking off, no learner’s rank consistency is verified, and the stochastic Softmax and Thompson rows may not have been rank-consistent. The live reward

is the cross-rank maximum time, the offline one GPU 0’s; we have not quantified how they differ. Action consistency across ranks rests on a deterministic policy over replicated statistics with an AUTO fallback (Appendix F); we have not fault-injected the fallback or verified bitwise-identical reductions. Under CUDA-graph capture the choice is fixed at capture, so learning applies only to eager collectives or across recaptures. Accounting and comparators. Realized TRLT overcharges exploration and selection-priced TRLT undercharges it, so we report both. Neither charges the NVLS stall, which we re-price separately, and both weight contexts equally, not by call frequency. The supervised comparators are fit-once selectors; the tree models were tuned with the learners’ budget on the H100 splits and with NVLS excluded (Appendix Table 37), but the GB200, label-budget and largest-scale static rows use fixed settings. We do not claim superiority over supervised methods in general, and we did not run active-learning selectors such as ACCLAiM or FACT. We ran no head-to-head against other online collective tuners (STAR-MPI, OMPICollTune, AutoCCL), so the cost-model prior, our only differentiator from them, is untested against them. Tuning used the selection-priced objective; re-tuning five families on the realized objective did not change the picture (Appendix I.13), but ETC and the supervised models were not re-tuned on it. Artifact availability. The NCCL tuner plugin is planned for release inside SPCX (we cannot give a date or terms); release of the evaluation harness, policy code, and processed data is under consideration, not committed, so a reader cannot yet re-run the tables.

9

C ONCLUSION AND FUTURE WORK

On a forced-arm sweep of Spectrum-X H100 nodes under a scale shift, the argmin of NCCL’s cost model is exact on most contexts and badly wrong on a few, where it misplaces a protocol or algorithm crossover. A per-context bandit seeded by that model cuts the contexts losing more than 10% from 19 to 1 (p99 103% to 9.9%); with hyperparameters frozen, on two GB200 fabrics it cuts p99 but not reliably the count (16 to 8, 10 to 13), and scenario-level tests are null. Against fit-once supervised selectors tuned with the same budget, online selection has a similar mean and, under scale extrapolation, a narrow tail edge (7 against 1 contexts above 10%, p=0.06); at seen scales the static fits match or beat it. Next are a shared contextual bandit and channel-count arms. GB200 is evaluated offline only, and a live GB200 run is future work: we lacked the resources to complete a verified one before the deadline.

10 / 46

R EFERENCES [1] Agarwal, R., Schwarzer, M., Castro, P. S., Courville, A., and Bellemare, M. G. Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021. [2] Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A next-generation hyperparameter optimization framework. In Proc. ACM SIGKDD, pp. 2623–2631, 2019.

[12] Cassel, A., Mannor, S., and Zeevi, A. A general approach to multi-armed bandits under risk criteria. In Proc. Conference on Learning Theory (COLT), volume 75 of PMLR, pp. 1295–1306, 2018. [13] Clopper, C. J. and Pearson, E. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934. [14] Cohen, J. Statistical Power Analysis for the Behavioral Sciences. Lawrence Erlbaum Associates, 2nd edition, 1988.

[3] Amazon Web Services. AWS OFI NCCL plugin: algorithm and protocol tuner. https://github. com / aws / aws - ofi - nccl, 2026. Accessed Nov. 2026.

[15] Cowan, M., Maleki, S., Musuvathi, M., Saarikivi, O., and Xiong, Y. MSCCLang: Microsoft collective communication language. In Proc. ACM ASPLOS, pp. 502–514, 2023. doi: 10.1145/3575693.3575724.

[4] Audibert, J.-Y., Munos, R., and Szepesvári, C. Exploration–exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876–1902, 2009.

[16] Culler, D. E., Karp, R. M., Patterson, D., Sahay, A., Schauser, K. E., Santos, E. E., Subramonian, R., and von Eicken, T. LogP: A practical model of parallel computation. Communications of the ACM, 39(11): 78–85, 1996.

[5] Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3):235–256, 2002. [6] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. doi: 10.1137/S0097539701398375. [7] Auer, P., Gajane, P., and Ortner, R. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proc. COLT, volume 99 of PMLR, pp. 138–158, 2019. [8] Avin, C., Lotker, Z., Mannor, S., Shabat, G., Shteingart, H., and Yadgar, R. Adversarial bandit over bandits: Hierarchical bandits for online configuration management. In Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2026. Applied Data Science Track, to appear. [9] Bhaskara, A., Cutkosky, A., Kumar, R., and Purohit, M. Online learning with imperfect hints. In Proc. International Conference on Machine Learning (ICML), volume 119 of PMLR, pp. 822–831, 2020. [10] Cameron, A. C., Gelbach, J. B., and Miller, D. L. Bootstrap-based improvements for inference with clustered errors. The Review of Economics and Statistics, 90(3):414–427, 2008. doi: 10.1162/rest.90.3. 414. [11] Cao, Y., Wen, Z., Kveton, B., and Xie, Y. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In Proc. AISTATS, volume 89 of PMLR, pp. 418–427, 2019.

[17] Ding, E., Oh, B., Kataria, B., Guo, K., Gvero, J., Kumar, A. V., Devraj, A., Bowen, L., Sonwane, A., Manzoor, E., and Singh, R. CCL-Bench 1.0: A trace-based benchmark for LLM infrastructure. arXiv:2605.06544, 2026. [18] Faraj, A., Yuan, X., and Lowenthal, D. STAR-MPI: Self tuned adaptive routines for MPI collective operations. In Proc. ACM International Conference on Supercomputing (ICS), pp. 199–208, 2006. doi: 10.1145/1183401.1183431. [19] Garivier, A. and Cappé, O. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proc. COLT, volume 19 of PMLR, pp. 359–376, 2011. [20] Garivier, A. and Moulines, E. On upper-confidence bound policies for switching bandit problems. In Proc. Algorithmic Learning Theory (ALT), volume 6925 of LNCS, pp. 174–188, 2011. [21] Hockney, R. W. The communication challenge for MPP: Intel Paragon and Meiko CS-2. Parallel Computing, 20(3):389–398, 1994. [22] Honda, J., Ito, S., and Tsuchiya, T. Followthe-perturbed-leader achieves best-of-both-worlds for bandit problems. In Proc. ALT, volume 201 of PMLR, pp. 726–754, 2023. [23] Hu, Z., Shen, S., Bonato, T., Jeaugey, S., Alexander, C., Spada, E., Hammond, J., and Hoefler, T. Demystifying NCCL: An in-depth analysis of GPU communication protocols and algorithms. arXiv:2507.04786, 2025.

11 / 46

[24] Huber, P. J. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964. [25] Hunold, S. and Steiner, S. OMPICollTune: Autotuning MPI collectives by incremental online learning. In Proc. IEEE/ACM PMBS@SC 2022, pp. 123–128. IEEE, 2022. [26] Hunold, S., Bhatele, A., Bosilca, G., and Knees, P. Predicting MPI collective communication performance using machine learning. In Proc. IEEE CLUSTER, 2020. [27] Hwang, C., Cheng, P., Dathathri, R., Jangda, A., Maleki, S., Musuvathi, M., Saarikivi, O., Shah, A., Yang, Z., Li, B., Rocha, C., Zhou, Q., Ghazimirsaeed, M., Anantharamu, S., and Jose, J. MSCCL++: Rethinking GPU communication abstractions for AI inference. arXiv:2504.09014, 2025. [28] Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005. [29] Kim, H., Ryu, J., and Lee, J. TCCL: Discovering better communication paths for PCIe GPU clusters. In Proc. 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), volume 3, pp. 999– 1015, 2024. doi: 10.1145/3620666.3651362. [30] Kocsis, L. and Szepesvári, C. Discounted UCB. In 2nd PASCAL Challenges Workshop, 2006. [31] Kruschke, J. K. Doing Bayesian Data Analysis: A Tutorial with R, JAGS, and Stan. Academic Press, 2nd edition, 2015. [32] Kuleshov, V. and Precup, D. Algorithms for multiarmed bandit problems. arXiv:1402.6028, 2014. [33] Li, L., Chu, W., Langford, J., and Wang, X. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proc. ACM International Conference on Web Search and Data Mining (WSDM), 2011. doi: 10.1145/1935826.1935878. [34] Liu, F., Lee, J., and Shroff, N. A changedetection based framework for piecewise-stationary multi-armed bandit problem. In Proc. AAAI, pp. 3651–3658, 2018. [35] Liu, X., Arzani, B., Kakarla, S. K. R., Zhao, L., Liu, V., Castro, M., Kandula, S., and Marshall, L. Rethinking machine learning collective communication as a multi-commodity flow problem. In Proc. ACM SIGCOMM, pp. 16–37, 2024. doi: 10.1145/3651890. 3672249.

[36] Luo, X., Wu, W., Bosilca, G., Pei, Y., Cao, Q., Patinyasakdikul, T., Zhong, D., and Dongarra, J. HAN: a hierarchical AutotuNed collective communication framework. In Proc. IEEE International Conference on Cluster Computing (CLUSTER), pp. 23–34, 2020. doi: 10.1109/CLUSTER49012.2020. 00013. [37] Madan, V. and Raigosa, A. Bandit-guided NCCL tuning for multi-node GPU clusters. CS244C course project, Stanford University, Winter, 2026. [38] Neu, G. and Bartók, G. An efficient algorithm for learning with semi-bandit feedback. arXiv:1305.2732, 2013. [39] NVIDIA Corporation. Memory efficiency, faster initialization, and cost estimation with NVIDIA collective communications library 2.22. NVIDIA Technical Blog, 2024. URL https://developer. nvidia.com/blog/memory- efficiencyfaster - initialization - and - cost estimation - with - nvidia - collective communications-library-2-22/. [40] NVIDIA Corporation. NVIDIA Collective Communications Library (NCCL) documentation, 2026. URL https : / / docs . nvidia . com / deeplearning/nccl/. Accessed 2026. [41] Pješivac-Grbović, J., Fagg, G. E., Angskun, T., Bosilca, G., and Dongarra, J. J. MPI collective algorithm selection and quadtree encoding. In Proc. EuroPVM/MPI, volume 4192 of LNCS, pp. 40–48. Springer, 2006. [42] Pješivac-Grbović, J., Angskun, T., Bosilca, G., Fagg, G. E., Gabriel, E., and Dongarra, J. J. Performance analysis of MPI collective operations. Cluster Computing, 10(2):127–143, 2007. doi: 10.1007/s10586007-0012-0. [43] Sani, A., Lazaric, A., and Munos, R. Risk-aversion in multi-armed bandits. In Advances in Neural Information Processing Systems (NIPS), volume 25, pp. 3275–3283, 2012. [44] Sankararaman, A. and Narayanaswamy, B. Online robust non-stationary estimation. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023. [45] Schwarz, G. Estimating the dimension of a model. The Annals of Statistics, 6(2):461–464, 1978. [46] Seldin, Y. and Slivkins, A. One practical algorithm for both stochastic and adversarial bandits. In Proc. International Conference on Machine Learning (ICML), volume 32, pp. 1287–1295, 2014.

12 / 46

[47] Shah, A., Chidambaram, V., Cowan, M., Maleki, S., Musuvathi, M., Mytkowicz, T., Nelson, J., Saarikivi, O., and Singh, R. TACCL: Guiding collective algorithm synthesis using communication sketches. In Proc. USENIX NSDI, 2023. [48] Si, M., Balaji, P., Chen, Y., Chu, C.-H., Gangidi, A., Hasan, S., et al. Collective communication for 100k+ GPUs. arXiv:2510.20171, 2025. [49] Slivkins, A. Introduction to multi-armed bandits. arXiv:1904.07272, 2019. [50] Steiner, S. Online algorithm selection of MPI collective communication operations. Diploma thesis, Technische Universität Wien, 2023. [51] Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018. [52] Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294, 1933. [53] Vehtari, A., Gelman, A., and Gabry, J. Practical Bayesian model evaluation using leave-one-out crossvalidation and WAIC. Statistics and Computing, 27 (5):1413–1432, 2017. arXiv:1507.04544. [54] Watanabe, S. Asymptotic equivalence of Bayes cross validation and widely applicable information criterion in singular learning theory. Journal of Machine Learning Research, 11:3571–3594, 2010. [55] Wei, C.-Y. and Luo, H. Non-stationary reinforcement learning without prior knowledge: An optimal blackbox approach. In Proc. COLT, volume 134 of PMLR, pp. 4300–4354, 2021. [56] Wilkins, M., Guo, Y., Thakur, R., Hardavellas, N., Dinda, P., and Si, M. A FACT-based approach: Making machine learning collective autotuning feasible on exascale systems. In Proc. ExaMPI Workshop, pp. 36–45. IEEE, 2021. [57] Wilkins, M., Guo, Y., Thakur, R., Dinda, P., and Hardavellas, N. ACCLAiM: Advancing the practicality of MPI collective communication autotuning using machine learning. In Proc. IEEE CLUSTER, pp. 161– 171. IEEE, 2022. [58] Williams, B., Mubarak, M., Caton, K., and Nicely, M. Understanding NCCL tuning to accelerate GPU-to-GPU communication. NVIDIA Technical Blog, July 2025. URL https://developer. nvidia.com/blog/understanding-nccltuning - to - accelerate - gpu - to - gpu communication/#nccl_cost_model.

[59] Woolley, C. NCCL: Accelerated multi-GPU collective communications. NVIDIA presentation at SC15, 2015. [60] Wu, Y., Shariff, R., Lattimore, T., and Szepesvári, C. Conservative bandits. In Proc. International Conference on Machine Learning (ICML), volume 48 of PMLR, pp. 1254–1262, 2016. [61] Xu, G., Le, Z., Chen, Y., Lin, Z., Jin, Z., Miao, Y., and Li, C. AutoCCL: Automated collective communication tuning for accelerating distributed and parallel DNN training. In Proc. USENIX NSDI, 2025. [62] Zhang, C., Agarwal, A., Daumé III, H., Langford, J., and Negahban, S. N. Warm-starting contextual bandits: Robustly combining supervised and bandit feedback. In Proc. International Conference on Machine Learning (ICML), volume 97 of PMLR, pp. 7335– 7344, 2019. [63] Zhao, L., Maleki, S., Wang, Y., Wang, Z., Yang, Z., Pourreza, H., and Krishnamurthy, A. ForestColl: Throughput-optimal collective communications on heterogeneous network fabrics. arXiv:2402.06787, 2024. [64] Zimmert, J. and Seldin, Y. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1–49, 2021.

AI U SAGE D ISCLOSURE We used LLM-based coding agents in the Cursor IDE (Anthropic Claude Opus and OpenAI GPT models) throughout this work, always directed and reviewed by the authors. Code: the agents wrote most of the offline emulation harness, the bandit policy implementations, the hyperparameter search drivers, the data-processing, analysis, plotting and table-generation scripts, and their unit tests; the authors specified the designs and reviewed the code. The tuner and profiler plugin was developed by the authors. Experiment design and analysis: the agents proposed and ran ablations and robustness analyses (for example the transient, split-robustness, NVLS-exclusion and largest-scale holdout studies) and summarized their outputs; the authors chose which analyses to run, what to report and how to interpret it. Data: no data were generated by AI. Every latency measurement comes from NCCL runs on the hardware described in the paper; the synthetic workloads are seeded generators written as code. Literature: the agents helped search for and summarize related work; the authors checked every cited reference against its source. Writing: the agents drafted and edited prose, captions and the appendices. Numbers in the text were copied from analysis-script

13 / 46

output (generated tables or their CSVs); reviewer rounds checked prose against the tables and found and corrected mismatches, so some may remain. Internal review: before submission, LLM agents acting as reviewers critiqued successive drafts in repeated rounds, and we revised the paper in response to each. The authors take full responsibility for all content, including the correctness of every claim and citation.

A

N OTATION AND ACRONYMS

Table 4 collects the symbols and acronyms used in the paper; each is also defined at first use.

Figure 3. CCL-Bench Llama3-8B torchtitan training trace (17) (Perlmutter, 16 GPUs): collective-call counts per bandit context (collective type, trace process-group size g, message size n). 719 calls over nine contexts (80× mean reuse (#calls/#contexts)); log-scale x-axis.

Table 4. Notation and acronyms (defined at first use in the body). symbol / acronym

meaning

MAB AUTO KPI SEM ETC FPL KL-UCB GBM+cost

multi-armed bandit NCCL’s static cost-model selector (baseline) key performance indicator standard error of the mean explore-then-commit follow-the-perturbed-leader Kullback–Leibler upper confidence bound gradient-boosted regressor with the cost-model prediction as a feature cost model’s predicted latency for arm a best predicted latency, min{µ̂(a) : µ̂(a) defined} predicted runner-up margin µ̂(2) /µ̂(1) − 1 reference-sweep mean latency of arm a measured-best (oracle) arm, arg mina µ̄a arm selected at iteration t pull reward µ̂min /t (ratio to predicted best) number of ranks participating in the collective message size (bytes) number of (filtered) arms in a context horizon (iterations per context replay; T =100 main) Relative Lost Time (per iteration) Cumulative Relative Lost Time Total Relative Lost Time (per context replay; headline accounting is realized latency)

µ̂(a) µ̂min m µ̄a a⋆ At r(t) P n K T RLT CRLT TRLT

B

without hundreds of learners. This small, heavily reused context set is why we run one independent bandit per context (Section 4): with so few contexts, cross-context generalization is unnecessary. B.2

E MPIRICAL MOTIVATION : FIGURES AND ANALYSIS

This appendix gives the figures and analysis behind the failure-mode and design motivation of Sections 3 and 4. B.1

Few recurring contexts

Production LLM training jobs revisit a modest set of collective communication contexts. In a representative Llama38B torchtitan training trace from CCL-Bench (17) (public Kineto workload on Perlmutter, 16 GPUs), 719 collective calls collapse to only nine distinct (collective, g, messagesize) contexts (80× mean reuse (#calls/#contexts); g is the trace process-group size, e.g. four ranks on tensor-parallel groups, distinct from the measurementside rank count P ); the two dominant contexts (64 MiB all gather and reduce scatter with g=4) account for 90% of calls (Figure 3). Long jobs therefore revisit the same contexts often, which amortizes in-job exploration

Non-stationarity and steady-state arm evaluation

Defining the measured-fastest arm is itself non-trivial. Figure 4 pools every arm’s per-iteration relative duration, defined as latency divided by that arm’s Huber location (a robust mean that down-weights outliers (24)) over the full trace, and column-normalizes each iteration into a distribution, with color encoding probability mass (log-scaled). Early iterations concentrate mass well above 1×: iteration 0 (the perf binary’s warmup, dropped from the pools) and the next several pulls are heavy-tailed outliers, after which the mass collapses onto the steady-state band near 1× within the first 10 pulls (the lower panel traces the pooled mean and standard deviation). NCCL lazily initializes connections and related state on first use of each (collective, nodes, algo-proto) combination, so this transient is not only job-start remanence: it recurs when switching to an algo-proto not exercised before in the same process (and may be absent when an algo-proto was already warmed by a prior collective at that size). That the transient is lazy initialization is inferred from its dependence on the iteration index within each arm’s isolated job, not shown by a controlled experiment such as connecting peers at init (NCCL RUNTIME CONNECT=0), which we did not run. These outliers motivate robust (Huber) location estimates. To locate the transient-to-steady boundary instead of judging it by eye, we fit a Bayesian switchpoint model to the pooled relative-duration trace. The model is one versus two Gaussian segments with a discrete-uniform prior on the change point τ (sampled with PyMC), and we compare the two by leave-one-out cross-validation (LOO) and WAIC (predictive model-comparison criteria that estimate out-ofsample fit (53; 54)), with a fast BIC grid (Bayesian Information Criterion, a likelihood score penalized for model

14 / 46

arms; Cohen’s d′ (a standardized effect size (14)) measures their separation in pooled-standard-deviation units as d′ =

Figure 4. Pooled column-normalized heatmap of per-arm relative duration (latency divided by the arm’s Huber location over iterations 0, . . . , 99) vs. iteration on the H100 sweep grid. Early iterations concentrate probability mass above steady state (≫1× Huber mean), motivating the transient window excluded before ranking measured-best arms (Figure 5).

complexity (45)) as a companion check. The two-segment model is decisively favored (LOO weight 1.00), with an elevated transient segment (µ1 =1.13× the Huber mean) dropping to a steady segment (µ2 =1.00×); the posterior concentrates the change point at iteration τ =8 with a posterior standard deviation of only 0.2 iterations. Its 90% highest-density interval (HDI), the shortest interval containing that share of the posterior mass (31), lies within a single iteration. We therefore conservatively begin the steady-state window one transient beyond that estimate and rank algorithm–protocol arms by mean latency over iterations 11, . . . , 99 (iteration 0 dropped; iterations 1–10 excluded as the lazy-init transient). The early transient therefore sets two evaluation choices used throughout: robust (Huber) location estimates to blunt transient outliers, and ranking arms by steady-state performance over iterations 11–99 instead of by final-iteration or naive-mean latency. The same transient also constrains the online learner, not only the offline ground truth. After first pulling an arm, a policy must either skip the initial lazy-init samples (the cold-start window) or apply robust online updates (e.g. clipped-SGD-style estimation (44)) that down-weight the early heavy-tailed outliers, so that a handful of transient samples do not corrupt its arm-value estimates. B.3

Cost-model error analysis

NCCL’s shipped selector plays arg mina µ̂(a) on exported cost tables; we audit that fixed choice against the same open-loop, forced-arm sweep measurements used in emulation, ranking the measured-best arm on the steady-state window (iterations 11–99) established above. At each scenario (collective × node count × message size) let µbest and µ2nd denote the means of the fastest and second-fastest

µ2nd − µbest , spooled

(4)

where spooled is the standard two-sample pooled standard deviation of the per-iteration latency samples for those two arms (spooled = p 2 2 ((n1 −1)s1 + (n2 −1)s2 )/(n1 +n2 −2)). Across n=300 contexts with both measurements and cost predictions, the model’s predicted-best arm matches the measured fastest arm in roughly four of five cases (the pooled error rate of Section 3 is 20.0%). Figure 5 overlays empirical CDFs of Cohen’s d′ for cost-model-correct and incorrect scenarios, log-normal fits to each (R2 =0.96 / 0.99), the decile-binned P (incorrect) (the fraction where arg min µ̂(a) differs from the measured-best arm), and a Bayes posterior derived from the fitted class-conditional densities (R2 =0.87 vs. bin medians). Two fitted model families summarize this figure. First, for each subgroup we fit a class-conditional log-normal to d′ by maximum likelihood, taking µ and σ as the mean and standard deviation of ln d′ over that
subgroup’s scenarios; the fitted CDF is Φ (ln d′ − µ)/σ (Gaussian in ln d′ , i.e. log-normal in d′ ), and the reported R2 values compare each fit against its empirical CDF evaluated at the observed d′ . Second, the gray P (inc | d′ ) curve is not fit to the binned points separately; it is derived from the fitted log-normal densities fc , fi (correct/incorrect) and the empirical class priors πc , πi (correct/incorrect; empirically πc ≈ 0.8, πi ≈ 0.2, the split above) via Bayes’ rule, P (inc | d′ ) =

πi fi (d′ ) , πi fi (d′ ) + πc fc (d′ )

(5)

which is exactly the likelihood-ratio (signal-detectiontheory) classifier for the two classes; its R2 =0.87 is measured against the decile-binned empirical P (incorrect) at bin medians. Smaller d′ coincides with higher P (incorrect): when the two leading arms are close in latency, a small prediction error flips the ranking, so a static analytic model’s argmin is least reliable in this neartie regime. This explains the error rate, not the tail: a near-tie flip costs little, and the contexts that dominate the loss in Section 3 are not near-ties (their measured gaps are large and survive within-pool resampling). We do not claim the gap is irreducible for a static selector in general: a supervised fit with the cost-model prediction as a feature matches the online mean on H100 (Section 6.1). The pooled-standard-deviation d′ also treats the 89 steady iterations as independent, which overstates separation if they are autocorrelated. Unlike the main-text runner-up margin (Figure 13), d′ uses measured means and variances and is therefore a post-hoc separation diagnostic, not a decision-

15 / 46

Figure 5. When the two best arms are close in latency (small Cohen’s d′ ), the cost model is most likely to mis-rank them, making static arg min µ̂(a) selection unreliable; online measurement can break such near-ties. H100 sweep grid (n=300 contexts with cost tables; measured-best ranked on iterations 11–99). Light/dark green: empirical CDF of Cohen’s d′ (4) for cost-model-correct and incorrect contexts (markers) with log-normal fits in log-d′ (R2 =0.96 / 0.99). Gray: empirical P (incorrect) in equal-count deciles of d′ (triangles; x-axis at bin median d′ ; shaded band: 95% Clopper–Pearson (13) CI) and Bayes posterior from the fitted class-conditional log-normal densities and empirical priors (R2 =0.87).

Figure 6. Choosing the predicted-cost filter threshold in excessratio units, δ = µ̂(a⋆ )/µ̂min − 1 (Equation (2)): probability of retaining the measured-best arm (solid green, left) and mean offered-arm count K=|A′ | (dashed, right) with a 5th–95th percentile ribbon across contexts, vs. δ. H100 sweep grid (n=300 contexts with cost tables; measured-best on iterations 11–99). The measured-best arm’s predicted-cost excess never exceeds δ = 0.80 (vertical gray dashed line); the unchanged ρmax =2 filter appears as ρmax − 1 = 1.0 (solid green) and keeps P (keep best)=100% with mean K≈2.56 of ∼4 arms (5th–95th percentile [2, 5]). This retrospective measured-best excess ratio is not the observable runner-up margin in Figure 13.

time signal. It complements the observable audit by explaining why measured near-ties are fragile; that figure shows directly that the model’s own small predicted margin does not bound realized TRLT. B.4

Cost-model arm filter threshold

Filter (2) prunes arms whose predicted cost exceeds ρmax times the model minimum. Figure 6 shows the safety– pruning tradeoff on the H100 sweep grid in excess-ratio units δ = µ̂(a⋆ )/µ̂min − 1: the measured-best arm’s predicted cost has empirical maximum excess δ = 0.80, so P (keep best) reaches 100% at that floor. The configured ρmax =2 is unchanged and appears as ρmax − 1 = 1.0, a round value just above it that retains a mean of ≈2.56 of ∼4 offered arms (5th–95th percentile [2, 5] across contexts). This retrospective ratio evaluates where the measured-best arm falls in the predicted ordering; it is distinct from the observable runner-up margin m = µ̂(2) /µ̂min − 1 in Figure 13.

C

BANDIT POLICY SPECIFICATIONS

All policies share the loop in Algorithm 1: maintain perarm statistics, select At , observe reward Rt , update. Let µ̂R a denote the running P mean reward on arm a, na its pull count, and Nt = a na . Unpulled arms (na = 0) are explored first where noted. Selection rules below are implementation-agnostic; champion hyperparameters are documented in Appendix E (Table 16), and the train/test holdout in Section 5.

Warm start seeds sufficient statistics per family. Warm start converts the cost-model reward guess r(µ̂(a)) = µ̂min /µ̂(a) into each policy’s own initial statistics, weighted by a per-family tuned pseudo-count ν (equivalently n0 ; a number of virtual prior pulls). Mean-based policies (UCB1, UCB-V, UCB-tuned, Gaussian Thompson, ε-greedy, KL-UCB, Softmax) initialize the running mean reward µ̂R a ← r(µ̂(a)) backed by na ← ν virtual pulls (the Gaussian-Thompson form is stated in its algorithm block below); loss-based policies (EXP3, Tsallis-Inf, FPL) instead seed the cumulative loss L̂a (0) = ν (1 − r(µ̂(a))). In every family ν=0 recovers the cold start exactly, so a champion tuned to ν=0 (EXP3, FPL) is cold even when the warm flag is set, which is why the ranking table’s “(warm)”/“(cold)” suffix and Table 16 agree per family. The three families whose implementations expose no such seeding (EXP3++, ETC, Madan RR-ETC) are always cold. C.1

NCCL cost model (AUTO)

Non-learning baseline: always play At = arg mina∈A′ µ̂(a) matching NCCL’s built-in cost-model selector (minimum predicted elapsed time) (40; 58). The policy does not update from observations; it fixes the same argmin arm at each context.

16 / 46

C.2

Uniform random

C.8

At ∼ Uniform(A′ ); ignores rewards. It is an unstructured lower reference. C.3

UCB1 " At = arg max′ a∈A

r µ̂R a +α

# 2 ln Nt , na

with exploration coefficient α > 0 (5). Unpulled arms are chosen uniformly at random until each arm has at least one pull (cold start only). C.4

For m rounds per arm, pull each a ∈ A′ exactly m times, then commit to arg maxa µ̂R a . During exploration, each pull selects uniformly among arms with fewer than m observations (m exploration rounds). C.9

(6)

Explore-then-commit (ETC)

Madan et al. round-robin (deterministic ETC)

Following Madan et al. (37), this policy uses fixed roundrobin exploration, IQR-trimmed commit, and an AUTO safety gate. Arms A′ are sorted lexicographically once per context (same order as the emulation environment). Let m be the number of exploration rounds and B=m |A′ |.

UCB-V

Uses empirical variance σ̂a2 (Welford) and Bernstein-style bounds (4):   s 2 2σ̂a ζ ln Nt c ζ ln Nt  , (7) + At = arg max′ µ̂R a + a∈A na na

Exploration (p < B inner updates). While the exploration counter p < B, play At = A′ [p mod |A′ |] (the index advances only on an inner-policy update). Each observed pull stores harness reward Rt ; define per-pull cost ct = −Rt (higher reward ⇔ lower cost under (1)).

with parameters ζ > 0, c > 0. Unpulled arms are chosen uniformly at random until each arm has at least one pull.

Commit. For each arm a, let Ca be the costs from its exploration pulls. Compute the Tukey IQR-trimmed mean c̄a : drop samples outside [Q1 − 1.5 IQR, Q3 + 1.5 IQR] (linear interpolation for quartiles), then average the remainder. Let a⋆ = arg mina c̄a and aAUTO be the cost-model arm (arg min µ̂). With c̄AUTO and c̄a⋆ , define relative improvement ι = (c̄AUTO − c̄a⋆ )/c̄AUTO when c̄AUTO > 0; else ι = +∞ if c̄a⋆ < c̄AUTO , and ι = 0 otherwise. Let γ be the safety-gate margin. If ι < γ, commit to aAUTO ; else commit to a⋆ .

C.5

UCB-tuned

Variance-aware UCB p of Auer et al. (5): with empirical variance Va = σ̂a2 + 2 ln Nt /na , # " r
ln N t At = arg max′ µ̂R min 14 , Va . (8) a + a∈A na Unpulled arms are chosen uniformly at random until each arm has at least one pull. C.6

Play the committed arm on every subse-

KL-UCB

Bernoulli KL-UCB of Garivier and Cappé (19): each arm is pulled once, then  At = arg max′ max q ∈ [µ̂R a , 1] : a∈A

na KL(µ̂R a , q) ≤ c ln Nt ,

(9)

with exploration constant c > 0 (bisection on q). Empirical means are clamped to [0, 1] for the Bernoulli KL (harness rewards occasionally exceed 1). Warm start seeds per-arm mean/count from cost-model guesses when enabled. C.7

Exploitation. quent pull.

ε-greedy

√ With exploration rate εt (fixed or decayed as εt = ε0 / t when enabled), explore with probability εt (At uniform on A′ ), else At = arg maxa µ̂R a (5).

C.10

Follow the perturbed leader (FPL)

We use the best-of-both-worlds FPL of Honda et al. (22), which operates in loss space with a Fréchet-tailed perturbation. Let ℓs = 1−Rs and maintain an importance-weighted estimate L̂a of the cumulative loss of arm a. Each round draw ra ∼ F2 i.i.d. from the Fréchet distribution with 2 shape α = 2 (c.d.f. F (x) = e−1/x , x ≥ 0) and play √ At = arg mina [L̂a − ra /ηt ] with learning rate ηt = η/ t (22). The unknown selection probability wt,At is estimated without bias by geometric resampling (38; 22): resample perturbations until the perturbed arg min matches At ; the number of draws m estimates 1/wt,At , and L̂At += √ ℓt,At m. The heavy Fréchet tail is what yields the O( KT ) adversarial and O(log T ) stochastic regret bounds; an exponential perturbation on cumulative rewards (28) does not. Warm start seeds L̂a (0) = ν (1 − r(µ̂(a))).

17 / 46

C.11

EXP3

Classic adversarial bandit with exponential weights (6): loss ℓt = 1 − Rt (optionally clipped at 0), exploration rate γ ∈ [0, 1], and learning rate η > 0. Maintain weights wa > 0; each round wa γ πt (a) = (1 − γ) P + ′ , w |A | b b

At ∼ πt ,

(10)

then update wAt ← wAt exp(−η ℓt /πt (At )). Warm start sets wa ∝ exp(η r(µ̂(a))) when enabled. C.12

EXP3++

EXP3++ augments EXP3 with arm-specific exploration rates derived from empirical loss-gap estimates (46). It retains adversarial robustness while reducing exploration when stable gaps emerge. Our implementation maintains importance-weighted cumulative losses, samples from the mixture of exponential weights and per-arm exploration rates, and searches its α, β, and reward-clipping parameters. Unlike EXP3, this implementation does not use a cost-model warm start. C.13

Softmax (Boltzmann)

Sample At ∼ πt ,

exp(µ̂R a /τ ) , R /τ ) exp(µ̂ ′ b∈A b

πt (a) = P

(11)

with temperature τ > 0 (32). With temperature decay, use √ τt = τ / Nt with Nt the number of softmax selections after cold-start exploration. Unpulled arms are chosen uniformly at random until each arm has at least one pull (cold start only). C.14

stationary. We therefore fix the parent family to adversarial EXP3 and let Optuna choose the child from Gaussian Thompson, UCB1, and Softmax. Adversarial robustness is the appropriate conservative model for this endogenous reward schedule; it is not the only possible solution, since a non-stationary stochastic parent could model the same coupling explicitly. Warm start splits r(µ̂(a)) across levels when enabled; with best-in-group parent aggregation, the parent group prior is the maximum child r(µ̂(a)) in that group. Algorithm 3 Hierarchical step (benchmark champion: EXP3 parent, Softmax child, algorithm grouping) Require: Parent policy πp over groups G, child policies {πc }c∈G over arms in each group 1: Gt ← πp .S ELECT() 2: At ← πGt .S ELECT() 3: Observe reward Rt from arm At 4: πGt .U PDATE(At , Rt ); πp .U PDATE(Gt , Rt )

Gaussian Thompson sampling

2 σ02 applies until Maintain (µ̂R a , σ̂a , na ); prior variance p na < 2. Posterior scale sa = σ̂a2 /na ; each step draw 2 µ̃a ∼ N (µ̂R a , sa ) and play At = arg maxa µ̃a (52). Un2 der robust estimation, µ̂R a and σ̂a come from clipped-SGD mean/variance instead of Welford.

C.15

Algorithm 2 Gaussian Thompson sampling with warm start (sketch) Require: Arms A, priors {r(µ̂(a))}, pseudo-count ν, prior variance σ02 1: for each a ∈ A do 2: µ̂R a ← r(µ̂(a)); na ← ν 3: end for 4: for t = 1, 2, . . . do 5: for each a ∈ A do 6: Update σ̂a2 via Welford; draw µ̃a ∼ R N (µ̂a , σ̂a2 /na ) 7: end for 8: At ← arg maxa µ̃a ; observe Rt ; update statistics for At 9: end for

Hierarchical bandit (EXP3 parent / searched child)

Arms partition into groups G by their algorithm/protocol structure: grouping by protocol or by algorithm. A parent policy selects Gt ∈ G; the child policy for Gt selects At ∈ Gt ; both receive the same Rt (8). Because each child learns online, the arm mixture within group g changes with time. The parent’s reward sequence for “arm” g is therefore induced by the evolving child policy and need not be i.i.d. or stationary even when each physical NCCL arm is

C.16

Tsallis-Inf

Loss ℓt = 1 − Rt (optionally clipped at 0). Maintains importance-weighted cumulative losses and sampling weights wa on the simplex via optimistic mirror descent with Tsallis entropy; step size α ∈ (0, 1) (64). Each step samples At ∼ w; after observing Rt , update losses and recompute w by solving the dual OMD problem (fixed Tsallis order 1/2 in the implementation; α is the OMD step size) (64). Warm start sets wa ∝ r(µ̂(a)) when enabled.

D

E XTENDED RESULTS AND SENSITIVITY

This appendix holds the full policy ranking, the 32-node bandwidth slice, the ablation suite (warm start, horizon, drift, update frequency, secondary knobs), and support-

18 / 46

Algorithm 4 End-to-end pipeline for one context (n, P ) Require: Latency pools {Da }, cost model µ̂, threshold ρmax , policy π, horizon T 1: A′ ← F ILTER A RMS(A, µ̂, ρmax ) ▷ Eq. (2) 2: Build prior rewards r(µ̂(a)) on A′ 3: Initialize π with warm-start priors and ν if enabled 4: for t = 1, . . . , T do 5: At ← π.S ELECT(); draw Xt ∼ DAt 6: Rt ← µ̂min /Xt ; π.U PDATE(At , Rt ) 7: end for 8: Report CRLT, TRLT, RLTi , and RLBi

Table 6. Fabric summary. H100 node entries use 8 GPUs per node; sweeps are isolated micro-benchmark jobs.

component

specification

Node Intra-node NIC Network NCCL Scale Sweep

Dell HGX H100 Gen-11; 8× H100 NVLink BlueField-3 SuperNIC Spectrum-X Ethernet 2.30.4 (CUDA 13.0) 4–32 nodes (32–256 GPUs) Isolated jobs

ing analyses behind Section 6. None of these replaces the realized-latency comparison in Table 1; the tables below are selection-priced unless stated otherwise.

D.2

Fabric summary

D.3

32-node bandwidth slice

D.1

D.4

Ablations and sensitivity

Full policy ranking

Table 5. Grouped method comparison on the holdout harness (train: 4/8-node contexts excluding the replay holdout; test: all 16/32-node grid contexts plus eight test-only CCL-Bench replay contexts mapped to 4-node measurement pools, P =4; T =100 sequential replay; train n=146, test n=154 contexts). Train and held-out test mean TRLT (%) are reported as mean±SEM across contexts; test p99 is the context-level 99th-percentile point estimate with a 95% bootstrap CI (contexts resampled with replacement; Section 5). Thus, ± values quantify uncertainty in a mean, whereas brackets quantify uncertainty in p99. Rows grouped as Fixed / Supervised / Bandits and sorted by test p99; bold marks the best per column (lower is better). Per-champion hyperparameters in Table 16; full protocol in Appendix E. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. TRLT (%) policy

train

test

Fixed NCCL AUTO (cost model) Random

4.04 ±0.99 39.73 ±2.95

5.99 ±1.58 45.22 ±3.72

Supervised Linear regression + cost Gradient boosting + cost Gradient boosting Random forest Random forest + cost Linear regression

2.94 ±0.48 2.04 ±0.47 28.68 [17.02, 42.58] 0.04 ±0.03 1.76 ±0.51 36.89 [17.77, 40.37] 0.18 ±0.10 4.70 ±1.35 76.41 [39.77, 129.99] 0.22 ±0.11 6.79 ±1.86 102.44 [66.16, 184.75] 0.29 ±0.14 3.90 ±1.44 103.25 [27.35, 134.61] 78.90 ±14.38 66.31 ±12.39 600.45 [556.59, 706.16]

Bandits Softmax (warm) 0.87 ±0.17 KL-UCB (warm) 0.85 ±0.18 UCB1 (warm) 0.86 ±0.18 ETC (cold) 2.43 ±0.24 Madan RR-ETC (cold)† 2.42 ±0.24 UCB-tuned (warm) 4.34 ±0.21 Gaussian Thompson (warm) 1.25 ±0.25 Hierarchical EXP3/Softmax (warm) 2.75 ±0.36 UCB-V (warm) 6.58 ±0.38 ε-greedy (warm) 1.07 ±0.27 Tsallis-Inf (warm) 6.98 ±0.43 EXP3 (cold) 7.52 ±0.49 FPL (cold) 8.52 ±0.61 EXP3++ (cold) 26.03 ±1.72 †

0.93 ±0.11 1.18 ±0.24 1.00 ±0.13 2.70 ±0.49 2.70 ±0.49 4.38 ±0.20 1.45 ±0.27 3.23 ±0.36 6.66 ±0.37 1.52 ±0.43 7.59 ±0.46 8.41 ±0.52 9.91 ±0.72 27.74 ±1.85

test p99 [95% CI] 103.25 [46.48, 134.61] 190.30 [147.02, 195.35]

6.59 7.63 7.97 8.68 8.68 11.60 16.94 17.30 18.81 22.15 24.20 24.23 35.55 89.95

[4.26, 7.62] [4.31, 32.72] [5.58, 9.39] [7.57, 71.39] [7.57, 71.39] [9.52, 12.48] [7.59, 22.20] [13.80, 18.47] [16.51, 19.87] [10.36, 51.66] [20.38, 28.36] [21.95, 26.32] [31.85, 41.05] [76.39, 102.15]

search-tuned to m=1, 1% safety gate on our offline harness; not the published live m=10 configuration.

Each ablation below changes exactly one design choice. Warm start and horizon run on the same holdout harness as Table 5 (Section 5); the drift and diluted-update experiments use targeted sensitivity harnesses whose numbers are therefore not comparable with held-out test TRLT, and are noted as such where they appear. D.4.1

Cost-model prior and learning horizon

Warm start. (Realized-latency version: Table 2.) Table 7 toggles cost-model warm start off vs. on for every warm-capable champion at otherwise frozen hyperparameters (top-level and, for the hierarchical policy, nested per level); the three families whose implementations do not support warm start (EXP3++, Madan RR-ETC, ETC) are omitted. Warm start seeds each arm’s sufficient statistics with a per-family tuned pseudo-count n0 of virtual observations at the cost-model reward guess µ̂min /µ̂(a) (Section 4), so a champion tuned to n0 =0 is effectively cold even with the flag on. The search varied warm/cold jointly per bandit, so this table isolates the warm-start effect at fixed knobs. Warm start helps most families and matters most where learning is coupled: cold Hierarchical EXP3 / Softmax reaches 44.0% test TRLT, which warm start collapses to 3.23%. One plausible explanation is short-horizon coupling: with uninformative priors at T =100 the EXP3 parent can move across algorithm groups before the Softmax children stabilize. The remaining families are nearly prior-insensitive on this scale-OOD test (UCB-tuned, UCB-V, Tsallis-Inf, EXP3, and FPL each move by <0.6 pp), and two do not improve at all: UCB-V worsens slightly (+0.21 pp) and FPL is unchanged.1 1 The FPL champion is tuned cold with pseudo-count n0 =0 (Table 16); toggling the warm flag on while n0 =0 leaves the seeded cumulative losses at zero, a literal no-op, so its paired ∆ is exactly 0.00.

19 / 46

Figure 7. HGX H100 offline emulation at 32 nodes (T =100 sequential replay), using the held-out 32-node slice of the holdout harness; the three featured policies (oracle, AUTO, and the deterministic UCB1 champion) are seed-independent under sequential replay. On this slice, the UCB1 champion reduces TRLT from 4.67% mean / 78.0% p99 for NCCL AUTO to 1.09% mean / 9.39% p99. Columns are the three collectives. Top: steady-state bus bandwidth vs. message size (black = oracle, gray = AUTO, green = UCB1 champion); the green band is the central 95% of observed bandwidth, not a seed-level CI. Bottom: sequential learning at the worst AUTO message size (gray dashed marker above); dashed black = oracle.

Horizon. Held-out test TRLT improves monotonically through T =100 for every learning champion, computed post-hoc from the same benchmark run at T ∈{10, 20, 50, 100} (Appendix D, Table 11). Sequential replay preserves lazy-init overhead on first arm pulls, so short horizons are pessimistic; deterministic fixed selectors such as AUTO are horizon-invariant, choosing the same arm at every pull. D.4.2

Non-stationarity: discounted forgetting

Regime construction. Our main harness is piecewise stationary: within a job the best arm is fixed and a policy need only identify it once. Production is not always so benign: a routing or congestion change, compute– communication overlap, or a co-scheduled job can make a previously poor arm the new winner mid-run (37; 61). Adapting to such change is what a bandit should add over a static cost model, so we test it explicitly. The space of non-stationary environments is unbounded (what changes, how, how much, how often); non-stationary bandit the-

ory collapses it into switching and slowly-varying families (49), and we take one worst-case instance of each, built from real measurements instead of synthetic magnitudes. On the held-out test contexts (154 jobs, 10 seeds, T =100) we identify each context’s measured best arm a⋆ and worst arm a◦ from its real steady-state pools (iterations ≥ 11; Section 5), and define a regime by a time-varying map from each offered arm to the pool it samples from: unswapped, every arm draws its own pool; swapped, a⋆ and a◦ exchange pools, so the former winner becomes a “trap” and the former worst the new winner. Rewards are bootstrap draws from the mapped pool, converted to the harness reward r=µ̂min /t (Section 4). Stationary never swaps; abrupt swaps for all steps t ≥ 50; gradual crossfades by swapping with probability 1−pold (t), where pold ramps linearly 1 → 0 over steps 35–65. The regime trajectory is drawn from a policy-independent RNG stream, so all policies face the identical realized drift within a (context, seed). One caveat: a best↔worst swap makes the new optimum the previously least-sampled arm, which favors optimism-under-uncertainty exploration, so this is a

20 / 46

Table 7. Warm-start ablation on the holdout harness, selectionpriced TRLT (each step priced at the chosen arm’s steady mean; the realized-latency version is Table 2): search champion hyperparameters per family, only warm start toggled off vs. on. Heldout test TRLT (%) at T =100; columns report mean±SEM across the test context pool (n=154 contexts). Underlined = setting Table 5 used for that champion. ∆ is paired true−false per context (not independent-column propagation). Key: TRLT is the latency served over T =100 steps of a context in excess of the measuredbest arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better).

Table 8. Non-stationarity ablation: mean dynamic TRLT (% ± SEM, lower is better); best per drift column in bold. Stationary is the sequential CV holdout replay—the same harness as Table 5 (T =100, 154 held-out test jobs, NCCL lazy-init cold start included), so the plain rows match Table 5 and the plain→discounted change is the true stationary cost of forgetting. Abrupt (best↔worst pool swap at step 50) and gradual (crossfade over steps 35–65) are the bootstrap steady-pool drift replay against a dynamic oracle (T =100, 154 × 10 runs). Discounting (γ selected leakage-free on the drift train partition) cuts drift TRLT several-fold while adding <0.2 pp on the stationary metric. Per-regime p99 and the purpose-built adversarial baselines (EXP3, EXP3++, Tsallis-Inf, FPL) are in Appendix D (Table 12).

TRLT (%) warm start policy

false

true

∆ (true−false)

Softmax 5.45±0.87 0.93±0.11 −4.53±0.88 UCB1 7.68±1.46 1.00±0.13 −6.68±1.46 KL-UCB 3.71±0.69 1.18±0.24 −2.52±0.68 Gaussian Thompson 2.87±0.50 1.45±0.27 −1.42±0.49 ε-greedy 5.43±1.25 1.52±0.43 −3.91±1.35 Hierarchical EXP3/Softmax 44.03±3.85 3.23±0.36 −40.80±3.85 UCB-tuned 4.94±0.21 4.38±0.20 −0.56±0.09 UCB-V 6.44±0.32 6.66±0.37 0.21±0.10 Tsallis-Inf 7.71±0.45 7.59±0.46 −0.12±0.07 EXP3 8.41±0.52 7.89±0.50 −0.52±0.10 0.00±0.00 FPL 9.91±0.72 9.91±0.72

targeted stress test, not a claim of adversarial-worst-case robustness. Dynamic oracle and leakage-free forgetting rate. Because the optimal arm now moves, static regret (against the single best fixed arm in hindsight) is meaningless: we score against a dynamic oracle (a time-varying, per-step-optimal comparator) that plays whichever arm currently draws the best pool and report dynamic CRLT/TRLT against that time-varying denominator (the stationary regime reduces to ordinary TRLT). The mechanism we ablate is exponential forgetting: discount each arm’s running sufficient statistics by γ ∈ (0, 1] per update, capping the effective sample size at 1/(1 − γ) (γ=1 recovers plain means, which react to a switch only once fresh samples dilute the stale ones). This is not a new mechanism: it is Discounted UCB (30; 20), whose sliding-window sibling SW-UCB replaces the geometric weights√with a hard window of the last τ samples; both attain Õ( ΓT ) dynamic regret over Γ breakpoints, and both require γ (or τ ) to be matched to an unknown switching rate, which we select below. Applied to our Softmax champion, whose estimator is an ordinary sample mean, γ yields the discounted mean of that literature verbatim. Applied to our UCB1 champion it does not: that champion’s mean is the clipped-SGD estimator (44), so γ discounts only its counts (both the confidence radius’ na

Policy

stationary

abrupt

gradual

NCCL AUTO (static) Softmax (plain) Softmax (γ=0.85) UCB1 (plain) UCB1 (γ=0.995)

5.99 ±1.58 0.93 ±0.11 1.07 ±0.12 1.00 ±0.13 1.16 ±0.13

45.01 ±3.93 31.57 ±2.63 5.96 ±0.29 6.60 ±0.61 5.88 ±0.54

44.60 ±3.89 31.99 ±2.65 13.11 ±1.17 10.93 ±0.87 10.68 ±0.87

and the estimator’s effective sample size), leaving a hybrid, not textbook D-UCB. We select γ for each of the two champions on the train partition only before freezing it for test; the train/test context split, not the seeds, prevents leakage. The three regimes’ TRLT scales differ by more than an order of magnitude, so a plain average would be swamped by the drift numbers and ignore the stationary cost. We therefore sweep γ over an 18-point grid and minimize the mean competitive ratio: each regime’s mean dynamic TRLT divided by the best any grid point achieves for that regime, which puts every regime on a “fraction of its own best” scale. The sweep selects Softmax γ=0.85 (aggressive forgetting) and UCB1 γ=0.995 (essentially plain). Forgetting helps under drift at negligible stationary cost. Under the abrupt swap, discounting cuts Softmax’s dynamic TRLT from 31.6% (plain) to 5.96% (5.3×), and under gradual drift from 32.0% to 13.1% (2.4×); the static AUTO cost model pays about 45% in both because it never re-selects (Table 8). The stationary column re-measures each policy on the sequential harness of Table 5, so its plain rows reproduce those numbers exactly and the cost of forgetting is directly readable: +0.14 pp for Softmax (0.93→1.07%), whose p99 even improves (6.59→5.34%), and +0.16 pp for UCB1 (1.00→1.16%). UCB1 needs less help because its clipped-SGD robust mean already tracks a moving target part of the way: its step size is λ/npa with a tuned p≈0.47, which is 5× the sample average’s 1/na at 100 pulls, so a fresh observation still moves the estimate long after a sample mean has stopped responding. Plain UCB1 is therefore strong under drift (6.60% abrupt, 10.9% gradual) and extra forgetting adds little (5.88%/10.7%), which is why its selected γ sits near 1. The step size still decays to zero, so the estimate keeps responding for longer but has no bounded memory; that difference shows

21 / 46

only over horizons far longer than the T =100 evaluated here (see the caveat below). Figure 8 shows the mechanism: the two flipping arms’ true rewards cross at the change point, and each policy’s CRLT departs from the oracle only around that crossing, with faster forgetting closing the gap sooner. The four purpose-built adversarial champions (EXP3, EXP3++, Tsallis-Inf, FPL) are the weakest learners in every regime here, at or above static AUTO under the abrupt swap, because this environment is stochastic and only piecewise non-stationary, not adversarial (Appendix D).

Commit-once explore-then-commit cannot recover. The explore-then-commit (ETC) family, of which Madan et al.’s round-robin plugin (Section 2) is an instance, shows the linear-regret argument in practice. We evaluate our tuned ETC champion (m=1, selected on the same CV harness as the bandit champions, so the comparison is matched). In the stationary control it is cheap (2.2% dynamic TRLT, near the adaptive champions and well below the static AUTO cost model’s 6.0%), because it commits almost immediately to the cost-model-filtered best arm. But having committed it has no mechanism to re-rank: under the abrupt swap it stays on the now-“trap” arm (postchange oracle-selection rate 1.2%), and its dynamic TRLT is the worst of all policies (50.9% abrupt, 50.5% gradual, exceeding even the static cost model’s 45.0%), while the discounted adaptive champions stay near 6% (Figure 8). This is the empirical counterpart of the commit-once failure of Section 2: after a permanent commit, dynamic regret grows linearly in the horizon, and since the stationary cost is negligible, no exploration budget fixes it.

Alternatives we do not evaluate, and why. Geometric discounting is the cheapest of several standard responses to a moving optimum. Change-detection methods run a statistical test alongside the bandit and reset the affected statistics on an alarm (CUSUM-UCB (34) and M-UCB (11)), while parameter-free methods such as AdSwitch (7) and the MASTER black-box reduction (55) remove the need to know the switching rate at all. Both families are a poor match for our horizon, though not for our problem. A detector must distinguish a real shift from sampling noise, and M-UCB’s own tuning rule prescribes a window of several hundred to over a thousand samples per arm for reward changes of the magnitude our swap induces, alongside forced uniform sampling at a rate that saturates when the horizon is short. At T =100 collectives per context the prescribed window exceeds the entire run. These methods become the natural choice at horizons of 104 collectives and beyond, which is also where the parameter-free guarantees start to pay for their constants.

Caveat: these conclusions are horizon-bound. Our regimes contain a single change within T =100, which is the deployment horizon of Table 5 but far short of a longlived communicator. Two asymptotic effects are invisible at this scale. First, any estimator whose step size decays (a sample mean, and more slowly the clipped-SGD mean) eventually stops responding on the arm it is currently playing: after na pulls a fresh observation moves µ̂a by O(1/na ), so the arm with the most data adapts the slowest, and a degraded incumbent is never re-ranked. Second, p UCB1’s radius revisits a neglected arm only when α 2 ln Nt /na regrows past the gap, which caps that arm’s lifetime pulls at O(ln Nt ) and spaces retests by a constant factor in Nt . Bounded-memory estimators—D-UCB, SWUCB, or a constant-gain filter—address both, and the nearunity γ selected for UCB1 here should therefore be read as “discounting does not pay for itself within 100 steps”, not as evidence that a long-running tuner can keep a sample average. We replayed the constant-gain filter on this same swap and on the stationary, NVLS-excluded split (Appendix I.10); like everything here, that evidence stops at T =100 with one change. Within that horizon, forgetting is a cheap, leakage-free safeguard: it recovers most of the mid-run-switch loss while leaving the stationary common case essentially untouched. D.4.3

Update frequency

Diluted updates. Every accepted update triggers a crossrank synchronization of sufficient statistics plus O(K) policy arithmetic, a fixed cost independent of message size (about 0.5–0.9 ms per sync on H100-A, Appendix Table 19). That is disproportionate for small payloads: on our H100 grid the measured-best arm completes in 39– 458 µs for all-reduce and 46–996 µs for all-gather and reduce-scatter up to 32 MiB, comparable to a single sync round, so a practical deployment must amortize learning over many fast collectives. We therefore decouple selection from learning: the policy still selects an arm on every collective, leaving stochastic exploration intact, but the harness accumulates per-arm rewards and observed collective time and, once the accumulated time reaches an interval τ , applies one update per observed arm using that arm’s mean reward over the window (τ =0 recovers per-collective updates). Diluting does not simply discard information: aggregating m observations into one mean-reward update trades update frequency for update quality, since the batch mean has variance σ 2 /m rather than σ 2 . The policy therefore sees fewer but cleaner updates, most valuable at small message sizes, where latency is noisiest relative to its mean (Section 3) and many measurements accumulate per flush.

22 / 46

Figure 8. Non-stationarity ablation on the held-out test contexts (154 jobs, 10 seeds, T =100). Columns are three regimes: stationary control, an abrupt best↔worst arm-pool swap at step 50, and a gradual crossfade over steps 35–65 (gray dashed = abrupt change point; gray dotted = gradual window). Top: true policy-independent reward of the two flipping arms (÷ cost-model best), showing the underlying regime change. Bottom: mean dynamic CRLT (%) vs. step against a dynamic oracle (lower is better); each curve’s endpoint equals its dynamic TRLT, shaded bands are 95% CI across contexts × seeds. Discounting (Softmax γ=0.85, UCB1 γ=0.995, selected leakage-free on the train partition by a three-regime competitive-ratio grid sweep) cuts drift TRLT several-fold below plain Softmax and far below the static NCCL AUTO cost model, while leaving the stationary control essentially unchanged. These panels are the bootstrap steady-pool replay; the stationary column of Table 8 instead re-measures on the sequential Table 5 harness for direct comparability. The tuned explore-then-commit champion (ETC, m=1, dotted; Madan et al.’s plugin is an instance of this family) is shown as the non-adaptive commit-once foil: cheap in the stationary control but the worst policy under both drift regimes, exceeding even the static cost model, because it commits and cannot re-rank. Purpose-built adversarial bandits (EXP3, EXP3++, Tsallis-Inf, FPL) are omitted for clarity and discussed in Appendix D.

It still works at a low update rate. Table 9 sets τ =1 ms and replays the featured UCB1 champion across the full grid (all collectives × node counts × message sizes) for T =200 sequential collectives, wrapping the steady-state tail so the NCCL lazy-init transient is replayed only on first exposure. Diluting cuts the median update count from 200 to 51 yet leaves mean TRLT unchanged (0.69→0.68%) and even improves p99 (9.20→6.56%), both far below NCCL AUTO (5.04% mean). The effect concentrates at small, sub-millisecond sizes and is a no-op at large ones, whose single-collective latency already exceeds τ . Under this time-based rule, which batches mainly the small sizes, learning survives a lower update rate. This is a single-seed sensitivity run, not the holdout harness, and the headline results do not batch.

D.4.4

Secondary design checks

Three further knobs move the held-out test result little, and we report them in full in Appendix D. The cost-model arm filter is neutral for the featured UCB1 champion (1.00% on vs. 1.01% off at T =100) even though disabling it nearly doubles the average offered arm count (2.56→4.01), so pruning pessimistic arms costs nothing and keeps selection cheap (Table 13). Clipped-SGD robust mean estimation does not help and usually hurts (Softmax 0.93→1.36%, UCB-tuned 4.38→6.18%, UCB-V 6.66→8.23%), because at K≤5 arms and T =100 the bias from clipping outweighs its variance reduction (Table 14). The featured UCB1 champion nonetheless carries robust estimation on because Optuna selected it on the train objective; on test this is a within-noise +0.06 pp change (0.94→1.00%, paired SEM 0.06), so on the stationary test it is a harmless tuning artifact and no evidence that robustness helps. Under drift it may matter: Appendix D.4.2 attributes plain UCB1’s

23 / 46

Table 9. Update-frequency ablation: featured UCB1 champion across the full grid (all collectives × node counts × message sizes; 300 contexts, T =200 sequential with the steady-state tail wrapped so the NCCL lazy-init transient is replayed only on first exposure). Selection runs on every collective; only the update() cadence changes. “updates” is the median batched updates per context; TRLT columns report mean±SEM and p99 with 95% bootstrap CI across contexts. Diluting to τ =1 ms batches updates at small (sub-ms) sizes and is a no-op at large sizes where a single collective already exceeds τ . Single-seed sensitivity run, not the holdout harness. TRLT (total relative lost time) is the latency a policy serves in excess of the measured-best arm’s, relative to the latter. Bold: best value per column (lower is better).

Table 10. Conditional TRLT (%) on the contexts where NCCL AUTO mis-ranks arms (measured-best ̸= predicted-best; exploratory stratification, all holdout partitions pooled). Rows are the cost model and the four warm-start champions discussed in the main text; the full policy set is in the benchmark CSV. TRLT (total relative lost time) is the latency a policy serves in excess of the measured-best arm’s, relative to the latter. Bold: best value per column (lower is better).

policy NCCL AUTO Softmax (warm) UCB1 (warm) Gaussian Thompson (warm) Hierarchical EXP3/Softmax (warm)

TRLT (%) policy

updates

NCCL AUTO (cost model) UCB1, update every collective UCB1, update every ≥1 ms

mean

26.08 2.38 2.82 4.76 7.76

p99 [95% CI]

— 5.04±0.94 75.01[50.93, 131.74] 200 0.69±0.10 9.20[5.53, 14.59] 51 0.68±0.09 6.56[3.61, 9.26]

form context reuse, while conditional TRLT isolates recovery where static selection fails. D.6

drift robustness to the clipped-SGD step size, but we did not replay a sample-mean UCB1 under drift, so that attribution is a mechanism argument, not a measurement. The adaptive observed-max wrapper is essentially a no-op, since rewards r=µ̂min /t rarely exceed their early running maximum: most families move by 0.00 pp and only the coupled hierarchy is materially worse (3.23→3.81%; Table 15). The champions’ gains therefore come from costmodel warm start and exploration control; reward renormalization adds almost nothing. D.5

conditional TRLT (%)

Population vs. conditional TRLT

Uniform job pooling (Section 8) weights all 300 multi-arm contexts equally (12 scenarios × up to 26 message sizes; the full sweep grid holds 306 measured cells, but 6 largesize cells offer only a single measured arm and admit no selection, Section 5). NCCL AUTO attains RLT=0 on roughly 80% of contexts (matching its static P (best arm)), so its 5.99% held-out test mean is driven by the remaining roughly 20% where the cost model mis-ranks arms. Table 10 restricts to the contexts where AUTO has positive normalized regret; this is an exploratory stratification with all partitions pooled, not a held-out measurement, which is why the headline stays with Table 5. On those failing contexts AUTO averages 26.1% TRLT at T =100 against 2.4% for Softmax, 2.8% for UCB1, and 4.8% for Gaussian Thompson, a 9.2–11.0× conditional gap, wider than the 6.4× population-mean ratio for Softmax (6.0× for the featured UCB1 champion); these ratios are selection-priced, unlike the realized headline. Learning policies still pay a small exploration tax on easy contexts (0.2% mean TRLT where AUTO is already oracle-equivalent). Both views matter: population TRLT is deployable overhead under uni-

Learning horizon

Table 11 reports held-out test TRLT at T ∈{10, 20, 50, 100} for each search champion, computed post-hoc from the same benchmark run (Section D.4.1). Every learning champion improves monotonically with T , so the T =100 ranking is not an artifact of a horizon sweet spot; sequential replay preserves lazy-init overhead on first arm pulls, which is why short horizons look pessimistic. The two fixed selectors bracket the range: AUTO is horizoninvariant at 5.99%, while uniform random stays high across horizons (46.8% at T =10, 45.2% at T =100) because it keeps sampling bad arms. D.7

Non-stationarity: full table and adversarial baselines

Table 12 gives the per-regime p99 alongside the means summarized in Table 8, under the construction and γselection protocol of Section D.4.2. Purpose-built adversarial bandits underperform here. One might expect algorithms designed for adversarial or non-stationary rewards to dominate this benchmark. They do not. When we evaluate the tuned holdout champions of EXP3 (6), EXP3++ (46), Tsallis-Inf (64), and FPL (22) on the same replay, all four are the weakest learners in every regime. Under the abrupt swap their mean dynamic TRLT is 30–45% (EXP3 40.5%, EXP3++ 45.2%, TsallisInf 33.1%, FPL 30.1%), at or above the static AUTO cost model (45.0%) and 5–8× worse than the discounted stochastic champions (5.9%); on the stationary control they lose 6.3–26.6% against roughly 1% for the champions on the same harness. This is not because the environment is easy. It is stochastic and only piecewise non-stationary,

24 / 46

Table 11. Held-out test TRLT (%) vs. horizon on the holdout benchmark harness (search champion per family; Table 5). Deterministic fixed selectors (e.g. NCCL AUTO) are horizon-invariant: the same arm is chosen every pull. Key: TRLT is the latency served over T =100 steps of a context in excess of the measuredbest arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better).

epoch length T policy

10

NCCL AUTO (cost model) Random

20

50

100

5.99 5.99 5.99 5.99 46.83 44.52 44.94 45.22

Softmax (warm) 5.76 3.22 1.52 0.93 UCB1 (warm) 3.73 2.73 1.42 1.00 KL-UCB (warm) 4.96 3.01 1.74 1.18 Gaussian Thompson (warm) 5.95 3.88 2.10 1.45 ε-greedy (warm) 4.58 2.92 1.88 1.52 Madan RR-ETC (cold) 22.16 11.35 4.86 2.70 ETC (cold) 22.16 11.35 4.86 2.70 Hierarchical EXP3/Softmax (warm) 12.48 9.98 5.29 3.23 UCB-tuned (warm) 11.91 9.21 6.12 4.38 UCB-V (warm) 20.89 16.15 10.20 6.66 Tsallis-Inf (warm) 28.41 20.47 12.17 7.59 EXP3 (cold) 28.57 19.98 12.44 8.41 FPL (cold) 29.05 22.24 14.55 9.91 EXP3++ (cold) 44.33 41.28 33.85 27.74

not truly adversarial, and four properties of these policies cost them here: (i) their minimax regret guarantees carry loose finite-time constants that have not amortized at T =100; (ii) they enforce a uniform exploration floor that wastes pulls with only K≤5 arms; (iii) they take no costmodel warm start, so they start cold where the stochastic champions start from the AUTO prior; and (iv) their loss scaling is tuned for adversarial [0, 1] losses rather than our cost-normalized rewards. On switching stochastic environments, discounted stochastic estimators are nearoptimal (20) and a robust worst-case policy pays for insurance it never uses. We therefore keep them out of Figure 8 for clarity. D.8

Secondary configuration checks

Arm filter (matched UCB1 champion; holdout harness). Table 13 compares filter-on (the holdout benchmark UCB1 champion, ρmax =2) against a matched filteroff rerun with the same hyperparameters and holdout split. Held-out test TRLT at pulls 50/100 is unchanged within display precision (1.42/1.00% on vs. 1.41/1.01% off) while the average offered-arm count rises from 2.56 to 4.01

(max 5 to 7): the filter buys a smaller action space at no measured accuracy cost on this policy. Robust estimation (holdout harness; search champions). Table 14 toggles clipped-SGD robust mean estimation off vs. on for every robust-capable champion, applying defaults when enabling it on a champion that ran without it. Robust estimation does not help on the held-out test suite and usually hurts: it raises test TRLT for Softmax (0.93→1.36%), UCB-tuned (4.38→6.18%), UCB-V (6.66→8.23%), and Gaussian Thompson (1.45→1.49%), and is roughly neutral for the UCB1 champion (0.94→1.00%). These variants are empirical clipped-SGD estimators rather than exact ones; at K≤5 arms and T =100 the extra bias from clipping outweighs its variance reduction, so plain sample means are preferable here. Adaptive observed-max (reward renormalization; holdout harness). Table 15 toggles the adaptive observedmax wrapper off vs. on for every learning champion. The wrapper divides cost-model-normalized pull rewards by their running maximum, rescaling inner statistics when a new maximum appears. On this harness it is essentially a no-op: rewards r=µ̂min /t rarely exceed their early running maximum, so the divisor stays near its initial value and test TRLT is unchanged to two decimals for most families (Softmax, UCB1, KL-UCB, ε-greedy, Gaussian Thompson, Madan RR-ETC, ETC). It is mildly harmful where it does fire: Hierarchical 3.23→3.81%, FPL 9.91→10.45%, EXP3++ 27.74→28.68%. D.9

Extended ranking notes

Hierarchical parent choice. The tuned hierarchy uses an EXP3 parent over algorithm groups and a Softmax child within each selected group (3.23% held-out test mean TRLT, 17.30% p99). The child policy changes as it learns, so the reward the parent observes for a fixed group is generated by a changing within-group action distribution rather than a stationary arm distribution. We therefore use an adversarial parent, whose update does not assume stationary group rewards. This is a robustness choice, not a necessity: a non-stationary stochastic meta-bandit would also serve, but a stationary UCB or Thompson interpretation at the parent level is misspecified for the coupled learner. ETC and Madan RR-ETC coincide at m=1. Both search champions tuned to a single exploration round, and Table 5 therefore renders them identically (2.70% test mean, 8.68% p99; their train TRLT is bit-identical and their test values differ only beyond two-decimal display, 2.699 vs. 2.698). When each arm contributes one learning update before commit, the 1% safety gate rarely overrides AUTO

25 / 46

Table 12. Non-stationarity ablation, full detail (compact version: Table 8): dynamic TRLT (%, lower is better). Stationary is the sequential CV holdout replay—the same harness as Table 5 (T =100, 154 held-out test jobs, NCCL lazy-init cold start included), so the plain rows match Table 5 and the plain→discounted change is the true stationary cost of forgetting. Abrupt (best↔worst pool swap at step 50) and gradual (crossfade over steps 35–65) are the bootstrap steady-pool drift replay against a dynamic oracle (T =100, 154 × 10 runs). Values are job-pool mean ± SEM and p99; best per drift column in bold. Discounting (γ selected leakage-free on the drift train partition) cuts drift TRLT several-fold while adding <0.2 pp on the stationary metric. Purpose-built adversarial baselines (EXP3, EXP3++, Tsallis-Inf, FPL) are discussed in Appendix D. Stationary (seq., cf. Table 5) Policy NCCL AUTO (static) Softmax (plain) Softmax (γ=0.85) UCB1 (plain) UCB1 (γ=0.995)

1.42 1.41

1.00 1.01

2 2

p99

mean

p99

mean

p99

5.99 ±1.58 0.93 ±0.11 1.07 ±0.12 1.00 ±0.13 1.16 ±0.13

103.25 6.59 5.34 7.97 7.59

45.01 ±3.93 31.57 ±2.63 5.96 ±0.29 6.60 ±0.61 5.88 ±0.54

197.46 128.39 15.70 33.71 30.32

44.60 ±3.89 31.99 ±2.65 13.11 ±1.17 10.93 ±0.87 10.68 ±0.87

195.36 133.57 58.12 44.31 43.15

2.00 3.00

5 7

2.56 4.01

at these short horizons (|A′ |∈{2, . . . , 5} on most contexts), so both commit to the same empirical best. They remain distinct policies, not a duplicated row.

E

Gradual

mean

Table 13. Cost-model arm filter ablation on the UCB1 champion (holdout harness: filter-on from Table 5 benchmark vs. matched filter-off rerun). T50/T100 are held-out test TRLT (%) at pulls 50/100; K columns summarize offered-arm counts after filtering. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). config T50 T100 Kmin Kmed Kmax Kavg On (ρ max=2) Off

Abrupt

H YPERPARAMETER TUNING

Table 14. Robust-estimation ablation on the holdout harness: search champion hyperparameters per robust-capable family, only robust (clipped-SGD) mean estimation toggled off vs. on (defaults used when enabling on a champion that ran without it). Held-out test TRLT (%) at T =100; columns report mean±SEM across the test context pool (n=154 contexts). Underlined = setting Table 5 used for that champion. ∆ is paired true−false per context. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). TRLT (%)

This appendix records the Optuna search procedure and frozen champion settings behind Table 5. The train/test context split, sequential replay harness, and reporting protocol are defined in Section 5; headline rankings use heldout test realized TRLT. Train columns and Figure 9 are search diagnostics only.

robust estimation policy UCB1 Softmax Gaussian Thompson UCB-tuned UCB-V

Search objective and harness. Each Optuna trial runs the same emulation job as the main benchmark (Section 5): one independent bandit per context, T =100 sequential replay, base seed 42, pull reward Rt = µ̂min /Xt from (1), cost-model filter (2) with ρmax =2, and TRLT denominators from arm means over iterations ≥ 11. The objective is mean train-partition TRLT only (146 contexts); test is never used for selection. 26 / 46

false 0.94±0.13 0.93±0.11 1.45±0.27 4.38±0.20 6.66±0.37

true ∆ (true−false) 1.00±0.13 1.36±0.28 1.49±0.31 6.18±0.35 8.23±0.52

0.06±0.06 0.43±0.23 0.05±0.17 1.80±0.20 1.57±0.17

Table 15. Adaptive-observed-max (reward renormalization) ablation on the holdout harness: search champion hyperparameters per learning family, only adaptive observed-max toggled off vs. on. The wrapper divides cost-model-normalized pull rewards by their running maximum, rescaling inner statistics when a new maximum appears. Held-out test TRLT (%) at T =100; columns report mean±SEM across the test context pool (n=154 contexts). Underlined = setting Table 5 used for that champion. ∆ is paired true−false per context. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). TRLT (%) adaptive observed-max policy

false

true ∆ (true−false)

Softmax 0.93±0.11 0.93±0.11 UCB1 1.00±0.13 1.00±0.13 KL-UCB 1.18±0.24 1.18±0.24 Gaussian Thompson 1.45±0.27 1.45±0.27 ε-greedy 1.52±0.43 1.52±0.43 Madan RR-ETC 2.70±0.49 2.70±0.49 ETC 2.70±0.49 2.70±0.49 Hierarchical EXP3/Softmax 3.23±0.36 3.81±0.46 UCB-tuned 4.38±0.20 4.62±0.19 UCB-V 6.66±0.37 6.87±0.37 Tsallis-Inf 7.59±0.46 7.59±0.47 EXP3 8.41±0.52 8.58±0.52 FPL 9.91±0.72 10.45±0.70 EXP3++ 27.74±1.85 28.68±1.93

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.58±0.26 0.23±0.05 0.21±0.06 0.01±0.03 0.17±0.03 0.53±0.11 0.94±0.23

Figure 9. Per-bandit hyperparameter search progress on the holdout tuning objective (train Total Relative Lost Time (TRLT), lower is better). Lines show the best-so-far configuration for the five strongest families among the available trial histories (including every family that held the global record); distinct dash patterns make traces readable without color. The dotted near-black staircase is the global best-so-far across bandits.

first-k rewards → optional adaptive observed-max. Adaptive observed-max divides cost-model-normalized pulls by the running maximum observed ratio and rescales inner statistics when a new maximum appears. Warm start seeds r(µ̂(a)) with pseudo-count ν; hierarchical warm start honors either the root or the nested per-level settings. Robust estimation uses clipped-SGD means with a clip threshold and learning rate.

F Optuna search. We run 14 independent Optuna (2) studies (one per learning family in Table 16); AUTO and Random are baselines without search. Each study runs 151 trials on the train partition with the TPE sampler: 1 educatedguess seed (trial 0) +50 random startup trials +100 TPE trials, sampler seed 42. We use TPE (2) because it natively models hierarchical, conditional search spaces: parameters that only exist when a parent choice is active. Our spaces are strongly conditional: the robust-SGD clip threshold and learning rate exist only when robust estimation is on, the warm-start pseudo-count only when warm start is on, and the hierarchical family has per-level (parent/child) subspaces. TPE handles these tree-structured dependencies directly (unlike samplers that assume a fixed-dimension continuous cube, e.g. CMA-ES or a plain Gaussian-process surrogate), which is why we prefer it here. Table 16 summarizes, per family, the trial index at which the champion was found, its search-objective improvement over the educated-guess default, and the hyperparameters tuning changed from that default. The winning trial per bandit is frozen and replayed once with no further tuning. Wrappers and warm start (champion replay). Each champion is assembled as inner policy → optional skip-

D EPLOYMENT: PLUGIN ARCHITECTURE AND MEASURED OVERHEAD

Scope. This appendix documents the NCCL tuner-plugin architecture used for the live closed-loop study in Section 6.5 (illustrated for Spectrum-X; the same feedback hooks apply on other fabrics). The interface mechanisms below are absent from upstream NCCL; we implemented them in the SPCX environment plugin, which is what let the bandit run in-loop on real hardware. The measured profiling and cross-rank synchronization overhead is reported in Table 18. Architecture. Figure 10 shows the deployed plugin stack. NCCL’s cost model supplies per-arm predicted latencies to the tuner callback; a profiler observes collective completion times and returns rewards to a multi-arm bandit over algorithm–protocol pairs (one instance per context). The bandit selects parameters for the next collective invocation; a new API synchronizes bandit state across ranks when an update is accepted. This mirrors the offline loop (Algorithm 1) but executes inside the training job rather than via offline replay. On each pluginGetCollInfo invocation, NCCL supplies collective type, communicator size P , and message size n; the plugin looks up (or

27 / 46

Table 16. Per-family hyperparameter-search summary (Appendix E), merging reproducibility and champion configuration. Each of the 14 learning families runs an independent Optuna study on the train partition of the holdout harness (1 educated-guess seed at trial 0 +50 random startup +100 TPE trials; sampler seed 42; objective mean train TRLT). best trial is the trial index at which the champion was found. train TRLT default→best shows the search-objective improvement over the trial-0 educated guess (with speedup factor). The trials ran 99 steps per context and Table 5 100, with identical choices over the shared steps, so the values differ slightly (UCB1 0.84% here, 0.86% there). search changes lists only the knobs tuning moved from that default. AUTO and Random are baselines without search. EXP3++’s champion is its trial-0 educated-guess default (best trial 0; 22.2→22.19 over 151 trials): no sampled configuration improved on it, which we read as an ineffective search space for that family on this scale-OOD harness rather than a strong default—consistent with EXP3++ being the weakest learner in the full policy ranking. Abbreviations: pc = warm-start pseudo-count ν (virtual prior pulls); pv = Gaussian-Thompson prior variance; ign-k = skip-first-k learning updates per arm; AOM = adaptive observed-max reward wrapper; warm = cost-model warm start; lr and ηr are the distinct robust clipped-SGD learning rate and step-size decay exponent (e.g. UCB1: lr→0.468 vs. ηr →0.467); clip = robust clip threshold λ; clipR = clip loss/reward to [0, 1]; gate = Madan safety-gate margin; εdec = ε decay; decay = Softmax temperature decay; m = ETC exploration rounds. A “→value” entry with no left-hand side is a conditional knob that was inactive at the trial-0 default (its governing flag was off) and that tuning switched on at the stated value. policy Softmax UCB1 KL-UCB Gaussian Thompson ε-greedy Madan RR-ETC ETC Hierarchical EXP3/Softmax UCB-tuned Tsallis-Inf EXP3 UCB-V FPL EXP3++

best trial

train TRLT default→best (%)

144 135 146 123 53 48 58 144 143 122 90 138 146 0

29.8→0.82 (37×) 9.9→0.84 (12×) 2.4→0.85 (3×) 4.0→0.99 (4×) 1.4→1.07 (1×) 11.1→2.44 (5×) 10.0→2.44 (4×) 12.4→2.86 (4×) 5.1→4.36 (1×) 7.4→5.35 (1×) 14.8→5.48 (3×) 21.2→6.60 (3×) 10.3→8.27 (1×) 22.2→22.19

search changes (init→best) τ 1→0.089; decay F→T; pc →1.24; warm F→T robust F→T; clip →0.389; lr →0.468; ηr →0.467; α 0.05→0.0928; pc →2.89; warm F→T c 0.217→0.0373; pc →1.56; warm F→T ign-k 0→1; pv 0.002→0.000301; pc →0.491; warm F→T; AOM F→T pc →0.892; warm F→T; AOM F→T ign-k 0→1; m 10→1; gate 0.05→0.0102; pc →0 ign-k 0→1; AOM F→T; pc →0 ign-k 0→3 pc →2; warm F→T α 0.85→0.883; clipR F→T; loss estimator iw→rv; warm F→T γ 0.1→0.0523; η 0.1→1.51; pc →0 ζ 1→0.501; c 3→1.02; pc →1.73; warm F→T η 1→4.85; pc →0 warm →F; pc →0

lazily creates) the bandit for that context key and writes algo/proto costs into the returned table, matching our offline lazy per-(collective, P, n) instances rather than one global policy across all sizes. Interface inventory (upstream vs. implemented). The deployment relies on one upstream mechanism and three we added. Upstream: the per-call cost-table override in getCollInfo (tuner interface v3, NCCL 2.22 and later (39)), which changes the next collective’s algo/proto. Implemented in the SPCX plugin: (i) a profiler→tuner reward-feedback channel returning each collective’s measured latency, aggregated across ranks (each rank times only its own completion); (ii) durable per-context bandit state across revisits (the callback otherwise has no memory of past latencies); and (iii) a cross-rank statesynchronization API so all ranks share one policy and agree on the selected arm. Upstream NCCL ships none of (i)– (iii) as a supported path between its tuner and profiler plugins, so we built them in the SPCX plugin environment, and the live study of Section 6.5 exercises all three. Upstream NCCL does document a profiler plugin interface, and one library can export both plugin types, so (i) in particular may be reproducible without modifying NCCL. We have not established which of (i)–(iii) strictly require NCCL changes. In outline, and without a formal specification: (i) the channel delivers, per collective, the measured latency in µs together with the communicator, collective type, message

size, and the algorithm–protocol pair that was played, to the tuner before its next call for that context; (ii) the state is a per-context table keyed by (collective, ranks, message size) holding per-arm counts, reward means (and the second moments some policies use), created on first sight and kept for the life of the communicator; (iii) in the intended design, the synchronization is an all-reduce of the per-arm reward sums and counts accumulated since the last flush, after which every rank applies the same update. Sums and counts reproduce a sample mean exactly; the clipped-SGD and constant-gain estimators depend on the order of individual samples, so with them every rank must apply the same flushed samples in the same order (an all-gather) or update once per flush from the batch mean; which the live UCB1 build did is not recorded. The sync rule differs between what we evaluated and what ran: the offline evaluation updates after every collective and charges no sync cost; the live overhead runs synchronized every 4, 16 or 64 collectives; and the rule the live learners used is not recorded in the run metadata we hold. The run metadata we hold does not record which tuner interface version the plugin was built against. The plugin is planned for release (Section 8); this outline is not a substitute for its interface. Percontext state is O(K) words (counts, means, last arm), so thousands of contexts are kilobytes to megabytes, but we have not measured footprint or the cost of synchronizing many contexts.

28 / 46

NCCL Core Cost Model AR 1K Ring Tree LL 3.2 5.0 LL128 5.2 6.2 Simple 10.0 17.3

2

Collective

1

cost table + msg size + job dims

provide params

4

Tuner

Bandit (rank r+1) new online-sync API 7

3

synchronize state across ranks

5

collective events

Profiler

online parameter selection

6

reward

Per-Context Multi-Arm Bandit (one instance per (collective, size, scale); arms = Algo / Proto)

SPCX NCCL Plugin

Figure 10. Tuner-plugin architecture. Green: NCCL core (cost model, collective execution). Blue: SPCX plugin (tuner, profiler); orange: the per-context bandit. (1) the collective triggers the cost model; (2) NCCL invokes the tuner with the cost table, message size, and job dimensions; (3) the bandit selects an algorithm– protocol pair; (4) parameters return to NCCL; (5)–(6) the profiler returns the measured latency as the reward; (7) bandit state is synchronized across ranks.

Rank synchronization and action consistency (sketch). NCCL requires identical algo/proto choices on every participating rank, which needs two distinct synchronizations. First, inputs must agree: each rank times only its own completion and cannot observe when the collective globally finished, so the reward must be a cross-rank aggregate. We take the all-reduced maximum completion time as a proxy for the application-visible collective latency (the last rank to finish); the mean or a leader’s local time are possible alternatives we leave to future work. The perarm sufficient statistics must likewise be replicated; without this each rank’s estimates diverge and even a pure arg max selection can pick different arms, so state synchronization is required for all policies, deterministic or stochastic. Second, the decision must be reproducible given identical statistics: a stochastic policy (Softmax, Gaussian Thompson, EXP3/EXP3++, Tsallis-Inf, or a hierarchical child) draws from the shared distribution π independently on each rank and can still sample different arms. That is an NCCL correctness violation, not a performance issue, so a stochastic policy additionally needs shared randomness (a communicator-shared RNG seed synchronized with π, or a leader rank that samples and broadcasts the arm). A policy that is a deterministic function of the shared statistics avoids this second step; UCB1 and ε-greedy qualify only once their cold-start/tie-break exploration (“unpulled

arms chosen uniformly at random”) is likewise derandomized (a fixed order) or seeded. In the intended design (we cannot verify that the build that ran followed it), the plugin replicates bandit sufficient statistics rather than raw latency traces: per-arm pull counts, empirical reward means (and variances where used), and the last committed arm. It allreduces a fixed-size vector whenever the flush rule accepts an update for a context (collective, P, n), so every rank enters the next selection with the same π (and, for stochastic or seeded policies, the same drawn arm). The decision of whether to update and sync on a given collective must itself be a collectively-agreed predicate (leader-gated, or derived from communicator-wide agreed context keys), so that divergent lazy context creation or update gating across ranks cannot deadlock the sync all-reduce, with some ranks entering it while others skip, before the AUTO fallback can trigger. NCCL’s current tuner interface falls back to its default selection for a collective when getCollInfo returns an error, so a per-call fallback to AUTO is available when a rank detects disagreeing context keys (the same safety pattern as Madan et al.’s commit gate). A failed synchronization all-reduce, by contrast, is a communicator error that a tuner cannot recover from per call, so the predicate has to prevent it, not recover from it. Measured sync cost. By design the per-update sync is a small collective: each update all-reduces an O(K)-word state vector (≪1 KiB for K≤5 arms, independent of n), and C concurrently active contexts batch into one O(C·K)word collective. We measure its cost directly with plugin runs that profile and synchronize state but leave AUTO’s selection untouched, so any bandwidth gap versus stock NCCL is pure overhead (Table 18). Profiling alone (sync off) costs 2.1% of average bus bandwidth; adding crossrank sync every 4/16/64 collectives costs 7.5/3.5/2.3%. Frequency dominates: the most frequent sync (every 4) is costliest, and batching to a longer period amortizes it. Each figure is one run; the same policy run in the two spacing modes, separate jobs, differs by a median 0.4– 1.5% at ≥64 MiB (Table 19). The average hides where the cost lands. Profiling alone adds 0.6% per collective below 1 MiB and 5.7% at 64–512 MiB, so it is not a fixed per-call cost, and we do not know its mechanism. The sync cost does behave like a fixed per-call cost: each period implies about 0.5–0.9 ms per sync below 1 MiB, which the near-zero small-size bandwidth hides from the average. The diluted-update ablation (Section D.4.3) shows learning survives such batching essentially unchanged. On H100A this overhead (2.1–7.5%) is between about a tenth and two fifths of the 18–24% average-bandwidth gain of the adaptive learners. That average is over 26 sizes and dominated by the large ones: per size, every adaptive learner is slower than stock at all 11 sizes below 1 MiB (median +11 to +14% out-of-place time, against +0.3% for profil-

29 / 46

Table 17. H100-B learners against the companion sweep’s stock run (a separate job), per size band: median over sizes of stock time over learner time (above 1: learner faster), per-size range in parentheses; nccl-tests out-of-place timed pass, host clock. Each run’s NVLS-stall size is removed (ETC’s lies below 1 MiB, the others’ at 1–8 MiB), leaving 10–11, 3–4 and 11 sizes. Softmax’s 0.11 at 64 MiB is a second first-touch gap (≈0.64 s, Ring/LL128) in its timed pass. One run per policy. Bold: best (highest) per column. Policy Greedy ETC (m=1) UCB1 Softmax Thompson ε-greedy

<1 MiB

1–8 MiB

16 MiB–16 GiB

0.64 (0.54–0.89) 0.65 (0.61–0.90) 0.65 (0.56–0.88) 0.61 (0.42–0.87) 0.59 (0.33–0.87) 0.64 (0.45–0.89)

1.27 (1.23–1.42) 1.31 (1.20–1.45) 1.29 (1.27–1.41) 1.22 (1.19–1.40) 1.29 (1.26–1.40) 1.21 (1.00–1.24)

0.98 (0.93–1.03) 0.97 (0.82–1.07) 0.97 (0.86–1.02) 0.97 (0.11–1.03) 0.98 (0.91–1.01) 0.99 (0.90–1.03)

ing alone on that measure and +0.6% on the in/out mean above), and gains only at the large sizes of AUTO’s error. On H100-A the NVLS stall falls in the warm-up pass of nccl-tests in every run, AUTO’s included, so these averages exclude it. H100-B has no plugin-off run, but its forced-arm companion sweep on the same nodes has one stock run (a separate job). Against it the 26-size average bus bandwidth of every H100-B learner is 0.94–0.99× stock (removing the stalled size changes this by at most 0.02), an average the large sizes dominate; Table 17 splits it by size band. Every learner is more than 5% faster than stock at each 1–8 MiB size except ε-greedy at 1 MiB, and more than 5% slower at every size below 1 MiB. Below 8 MiB the learners play the cost-model argmin on ≥99.8% of timed collectives. At 1–8 MiB the forced Tree/LL128 run, that argmin, is 1.26–1.51× faster than stock, and the learners are 0.88–0.94× that forced run, so the band’s gain is a gap between the stock run and the forced arms, not a selection gain. Below 1 MiB the sync explains only part of the loss. The median slowdown (0.59–0.65×, i.e. +54– 69% time) is far above H100-A’s +13–15%. Against the forced sweep’s run of the same arm the learners are still 0.76–0.86×, while that forced run is itself 0.97–1.70× stock’s time. ETC, whose H100-B re-exploration setting is not recorded, shows the loss too, unlike H100-A’s commitonce ETC. In the back-to-back H100-A runs with AUTO’s selection fixed (the mode H100-B ran), a sync every 64 collectives costs +4% host time below 1 MiB over stock and +2% over profiling alone, against +13% every 16 (Table 19). In both campaigns every arm switch of UCB1, Softmax, Thompson and ε-greedy falls on one phase of a 16-call counter per size, and every one of Greedy’s on another phase; ETC’s are spread. Table 21 lists the H100-A policies, including the timedpass bandwidth column behind the ETC comparison above; the text quotes its values. The H100-A row of Table 20 is computed from the same profiler data by a separate

Figure 11. H100-A live arm choices at the largest AUTO gap (AllReduce, 4 GiB, back-to-back): one facet per policy, fastest first, each of the 400 collectives placed at accumulated collective time, with colour and marker giving the selected arm. Solid green: policy finish; dashed: oracle latency and finish; dotted: AUTO’s finish. Every learner leaves AUTO’s arm within 31 collectives; reaching the oracle depends on when it samples RING SIMPLE, whose latency drifts early (probe means 28.9– 40.4 ms vs. 25.9 ms settled) while RING LL128 holds 30.5 ms. Greedy (ε-greedy with ε=0) samples it at collective 17, measures 31.6 ms, and never returns; Thompson likewise: its stationary posterior on RING SIMPLE concentrates on the drift-inflated 36.6 ms, so although every arm keeps non-zero probability, a revisit is ∼10−25 likely per decision and a longer run would not rescue it. ETC (m=1) reaches the oracle only because it samples RING SIMPLE fifth (28.9 ms); sampled first, it would likely have committed to RING LL128. Finish times include the drift, so they exceed TRLT. One run per policy: this illustrates the mechanism, not a ranking.

30 / 46

Table 18. Measured profiling + cross-rank sync overhead at fixed AUTO selection (H100-A: 8 nodes, 64 ranks, back-to-back). All rows make NCCL’s default selection, so bandwidth lost relative to stock NCCL is the cost of running the plugin: profiling every collective and all-reducing bandit state every state sync period. Bus bandwidth is the nccl-tests average over 26 sizes. AUTO plugin (sync off) prices profiling alone; the sync/k rows add cross-rank state exchange every k collectives. Frequency, not payload (<1 KiB), dominates: sync/4 is costliest and the overhead shrinks as the period grows, so batching updates amortizes it (Section 7). On this fabric the average overhead is smaller than the average-bandwidth gain of the adaptive learners (Table 21), which comes from the large sizes; below 1 MiB the learners are slower than stock, and the overhead is not size-independent (Table 19). Each row is one run. Bold: best per column (highest bandwidth, lowest overhead).

configuration

state sync

bus bw (GB/s)

overhead (%)

— off 4 16 64

73.0 71.5 67.5 70.5 71.3

— (ref.) 2.1 7.5 3.5 2.3

Stock NCCL NCCL AUTO AUTO + sync/4 AUTO + sync/16 AUTO + sync/64

Table 19. Per-size plugin overhead on H100-A (back-to-back, AUTO’s selection fixed): median per-collective time overhead against stock (%) per size bin, with the bin’s share of the 26-size average-bus-bandwidth drop in parentheses; “1 ms flush” is the number of collectives per sync that the 1 ms rule would imply at stock latency (median over the bin). The last row compares each run with the same policy’s run in the other spacing mode (a separate job) at ≥64 MiB, as a single-run noise yardstick. One run per column. Bold: best per row among the policies. Size bin

n

<1 MiB 1–32 MiB 64–512 MiB ≥1 GiB

11 +0.6 (0) +61.6 (1) +13.4 (1) +4.3 (1) 6 +1.4 (5) +41.8 (32) +10.1 (19) +3.8 (13) 4 +5.7 (80) +13.0 (40) +7.6 (58) +6.0 (69) 5 +0.4 (14) +2.9 (27) +1.2 (22) +0.7 (17)

avg. bus bw drop 26 run-to-run, ≥64 MiB 9

no sync

2.1 0.4

sync/4

7.5 1.5

sync/16

3.5 1.3

sync/64 1 ms flush: coll./sync 3 2 1 1

2.3 0.5

pipeline; the two differ by at most 0.1 pp and we did not reconcile them. Live campaign setup. H100-A uses 2 queue pairs per connection and 10 for long-haul links; H100-B uses 1 for both. The run metadata we hold record no longhaul emulation for the primary sweep. The variable NCCL IB LH LATENCY is not in NCCL’s public documentation, and we do not know its unit or where it injects delay; H100-A ships no cost table, so we cannot check whether its model saw the emulated latency. H100-B has no runs with AUTO’s selection fixed, so its small-size loss is attributed to the sync only in part, by analogy with H100A; diluting the sync is a straightforward mitigation, but no learner ran live with it. The first-use NVLS TREE SIMPLE

stall ranges over 6.4–7.8 s on H100-A (10 runs; 6.1% of run wall time) and 5.7–5.9 s on H100-B (6 runs); amortizing it to 1% takes about 660 s of collectives, while the offline harness charges at most the first sample’s excess (≤9.8 ms). How long live inflation lasts. The replay models the lazy-initialization transient as the first ten samples of each arm (Section 5). On H100-A (back-to-back runs, 262 (policy, size, arm) cells with at least 100 pulls, each pull divided by the cell’s settled median over pulls beyond 50), the 90th percentile of that ratio is 1.28 at the first pull, 1.09–1.12 over pulls 3–10, and at most 1.07 from pull 11 to 40, and the share of cells more than 5% above settled falls from 32% to 14% by pull 11. So the live inflation lasts about as long as the replay’s transient window; the cells are arms a policy kept playing, so arms abandoned early (RING SIMPLE under Greedy in Figure 11) are not in this sample. Relation to Madan et al. The tuned ETC (m=1) row beats AUTO on held-out test TRLT (Table 5) in the same direction as the latency reductions Madan et al. report on live A100 clusters (37), which is not a validation of their results (their report is not peer reviewed and our configuration differs). In our live study the ETC (m=1) plugin reaches 93.5 GB/s (1.28× stock) on H100, the best timedpass bandwidth of any policy (Table 21). Because that average hides exploration cost in the warm-up pass, this live result does not separate commit-once from adaptive policies. On realized offline latency ETC has a 63.0% p99 against UCB1’s 9.9% (Table 1). The residual differences reflect hardware generation (H100 vs. A100) and exploration budget: their 10 × |A′ | pulls inflate early TRLT on longer horizons. On our selection-quality metric the same commitonce policy indeed trails the adaptive bandits (22.0% vs. ϵgreedy’s 2.9%) because TRLT charges the exploration that the timed-pass bandwidth hides. Metric choice. We recommend TRLT for systems comparisons, CRLT for learning curves, and RLT for per-step gaps. Classical cumulative reward-space regret remains a useful diagnostic but can mis-rank policies when the costmodel prior skews the objective (Section 6). First-touch NVLS toll: sensitivity of the realized ranking. In the live profiler traces the stall is the single largest inter-collective gap per run (at least 1 s), attributed to the arm played right after it; we did not separate it from other arms’ lazy initialization with a controlled experiment. The live campaigns (Section 6.5) show a stall on the first use of NVLS TREE SIMPLE (median 6.6 s, range 6.4–7.8 s, on H100-A; 5.8 s, 5.7–5.9 s, on H100-B), which the pinned offline sweep never charges. Table 22 re-prices the realized TRLT by adding a one-time toll to the first NVLS collective

31 / 46

Table 20. Live decomposition across the two closed-loop H100 campaigns. Selection quality is priced by a profiler against a reconstructed oracle with setup excluded; plugin overhead is measured with AUTO’s selection fixed (profiling alone, then with state syncs at fixed periods; one run per row); the setup toll is the first-use NVLS TREE SIMPLE stall; “–” marks fields not measured. No learner’s rank consistency was verified live. Component

Campaign

Finding

selection quality plugin / sync overhead

H100-A (64 ranks) H100-B (64 ranks) H100-A (64 ranks)

one-time setup toll

H100-B (64 ranks) H100-A (64 ranks)

best learner epsilon-greedy: 2.86% mean / 8.64% p99 selection TRLT best learner greedy (epsilon=0): 0.59% mean / 1.98% p99 selection TRLT 2.1% average bus bandwidth lost vs stock with profiling only (AUTO selection, state sync off; one run per row); sync every 4 collectives is costliest and the ladder falls toward stock as the sync period grows not measured: this campaign has no plugin runs with AUTO selection fixed 6.6 s median (6.4–7.8 s over 10 runs) NVLS TREE SIMPLE first-use stall (6.1% median of run wall); ∼123,717 median steady collectives to amortize at 1% 5.8 s median (5.7–5.9 s over 6 runs) NVLS TREE SIMPLE first-use stall (6.2% median of run wall); ∼172,261 median steady collectives to amortize at 1%

H100-B (64 ranks)

Measured

of every held-out context in which a policy (or the oracle) uses an NVLS arm. This is an upper bound: in production the toll is paid once per communicator, not once per context, so a job that touches NVLS in many contexts pays it once. The fraction of contexts in which a policy touches an NVLS arm at all is 11.7% for AUTO, 3.9% for GBM+cost, 16.2% for UCB1, 21.4% for Softmax and 22.1% for Random, so exploration pays the toll more often than a static choice. At the measured toll the ordering of Table 1 inverts for any policy that explores. Arms with large onetime setup costs should therefore be excluded from exploration, or pre-warmed at communicator creation, not priced inside a T =100 horizon. Table 23 gives the two less pessimistic accountings (Section 7): the benchmark rerun with NVLSTree Simple removed from every policy’s arm set (the cost-model minimum, AUTO’s argmin, the filter, and the oracle all see the reduced set; the frozen champions and the supervised fits are otherwise unchanged), and a pooled, traffic-weighted TRLT in which the 5.8 s toll is paid once per communicator size in which a policy plays NVLS, against a pre-warmed oracle, with V visits per context. The oracle is pre-warmed and never pays. Charging it the same tolls would add a common term to every denominator and cannot reorder policies that touch NVLS in both communicator sizes, but could change their order relative to the supervised models without the cost feature, which never play NVLS (not recomputed). At V =102 , the T =100 replay, the pooled collective time is only 89 s, so a 5.8 s toll paid in two communicators moves every policy that touches NVLS by about 13 pp; at V =104 it moves them by about 0.1 pp.

G

C ONTEXTUAL BANDITS

The per-context bank of Section 4 shares nothing across contexts, which raises the question of whether a single contextual bandit that shares a model across contexts would do better. We tested this with one native LinUCB policy over the same offered arms and the same cost-model prior, and the same T =100-per-context horizon, on a balanced uniform-random workload (100 visits to each of the

✓ ✓ ✓ – ✓ ✓

154 held-out contexts, shuffled; five reshuffles). This is the friendliest workload for a shared model, because it maximizes context diversity per observation, and the least favorable to the bank; real traces revisit few contexts (Section 6.4). The features are a per-collective quadratic block in log2 message size and log2 node count plus the cost model’s predicted reward for the arm being scored and its product with log2 size (“cost” basis); the prior enters as one pseudo-observation per context–arm, injected on first sight of a context, so the policy is deployable. Without the cost-model feature LinUCB falls behind both banks, and a physics-motivated Hockney basis is worst, because the observed quantity is a latency ratio on a geometric size grid. Table 24 gives the selection-priced, per-context TRLT (the same unit as elsewhere). LinUCB with the cost feature reaches 0.61 ± 0.04% mean and 5.31% p99, below the warm bank (1.00% / 7.3–8.0%) and the supervised GBM+cost selector (1.76% / 36.9%); cold banks and AUTO are far worse. We do not promote this to a headline: it is selection-priced, one workload family, tuned with its own search, and not yet scored with realized accounting or a real trace. It does not change the thesis, since the contextual policy also depends on the cost-model prior; it indicates that the per-context bank is a conservative, easily deployed design, not the only one.

H

W ORKLOAD WEIGHTING AND CROSS - ARCHITECTURE DETAIL

Trace replay. Table 25 and Figure 12 give the Llama3 replay behind Section 6.4: two cycles of the trace, warm UCB1 state carried across cycles, sequential sampling that wraps past the lazy-init region so that repeated cycles add no cold-start cost. The statistic is cumulative relative lost time over the whole replay, which weights each context by its call count; the per-context mean used in the main text weights every context equally. Both are computed from arm means (selection pricing).

32 / 46

Table 21. Live closed-loop tuner on real hardware (8 nodes, 64 ranks, AllReduce; H100-A campaign). The bandit ran inside NCCL via the SPCX env plugin and selected the algo/proto arm online, with a per-collective profiler returning measured latency. UCB1, Softmax and Thompson ran the offline champions’ hyperparameters, warm-started from the cost model; ϵ-greedy ran an outdated constant (ϵ=0.033, decaying) instead of its tuned value ϵ=0, and no policy used the constant-gain mean we recommend as the default; Greedy (ϵ=0 from the cost-model prior) and ETC (one sample per arm) are implemented in the plugin itself. Selection quality is mean/worst-size TRLT over the 10 scorable sizes (32 MiB–16 GiB, where every arm is well sampled), priced from pooled per-arm profiler latency; “mean rank” is the average placing over those sizes (1 = best). “Bus bw” is the wall-clock average over all 26 sizes of the 100 timed iterations (after 100 warmup iterations) from the nccl-tests out tables, so it includes whatever exploration falls in the timed pass, and “vs stock” is the ratio to stock NCCL (no plugin). Bold marks the best value per column. One run per policy (no seed variance); the oracle is reconstructed by pooling every arm observation across runs of the same spacing, including the scored runs. TRLT charges exploration over all 400 collectives, so ETC (m=1) can lead on timedpass bandwidth yet trail on TRLT. No learner’s rank consistency was verified (data checking off), and the stochastic learners may not have been rank-consistent, so the ranking is indicative only. TRLT (total relative lost time) is the latency a policy serves in excess of the measured-best arm’s, relative to the latter.

TRLT (%) policy

bus bw

mean worst rank GB/s vs stock

ϵ-greedy 2.85 Greedy 6.43 UCB1 8.28 Thompson 8.49 Softmax 9.00 ETC (m=1) 21.96 NCCL AUTO 31.35

9.1 19.0 12.5 20.4 15.6 49.4 77.3

1.6 2.8 4.0 3.9 4.0 5.7 5.1

90.7 86.1 89.3 88.0 90.0 93.5 71.5

1.24× 1.18× 1.22× 1.21× 1.23× 1.28× 0.98×

GB200 train and test. The frozen H100 hyperparameters were not re-tuned on GB200. On the GB200 train partition (4/8 nodes) the supervised GBM+cost selector fits its own training contexts to 0.16% (MNNVL off) and 0.04% (MNNVL on), but on the held-out 16/32-node slice it reaches 4.41% and 3.36% mean (p99 75.3% and 59.4%, selection-priced), worse than AUTO on the mean on both fabrics: a selector fitted on small topologies does not carry to the large ones. The forced-arm pinning confound of the GB200 sweeps (Section 6.3) bounds but does not remove the comparison.

Table 22. Realized TRLT (held-out test mean, %) if the first NVLS collective of each context costs a one-time toll (upper bound; see text). “none” reproduces Table 1. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Policy none 1s 3s 5.8 s NCCL AUTO Supervised GBM+cost, fixed Supervised GBM+cost, tuned ETC (m=1, k=1) Softmax UCB1 KL-UCB Random

6.1 1.8 1.4 4.7 1.8 1.6 2.1 46.8

98.9 11.8 12.2 595.6 411.5 209.7 380.0 637.7

285.1 32.2 34.4 1779.2 1231.9 626.6 1136.9 1821.3

545.8 60.9 65.5 3436.2 2380.6 1210.3 2196.6 3478.3

Table 23. NVLS handling (held-out test, realized TRLT, %). NVLS offered: the main benchmark. NVLS excluded: NVLSTree Simple removed from every policy’s arm set and from the oracle. Pooled: traffic-weighted TRLT over all test contexts with a 5.8 s toll paid once per communicator size in which the policy plays NVLS, against a pre-warmed oracle, at V visits per context. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 heldout contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). NVLS offered NVLS excluded Pooled, 5.8 s once per comm. Policy

mean

NCCL AUTO Supervised GBM+cost ETC (m=1) Softmax UCB1 KL-UCB

6.08 1.78 4.74 1.75 1.61 2.11

p99 mean 103.3 32.2 63.0 11.9 9.9 22.7

6.27 1.79 3.26 1.22 1.23 1.90

p99 V =102 103 111.4 32.2 13.8 8.6 11.2 27.5

15.82 14.08 13.76 13.50 13.60 13.47

4.14 2.41 2.08 1.82 1.93 1.80

104 2.98 1.24 0.92 0.66 0.76 0.63

Figure 12. CCL-Bench Llama3 trace replay (two cycles). Warm UCB1 flattens after one-time exploration while AUTO repeats the same loss.

33 / 46

Table 24. Per-context TRLT (%) on the balanced uniform workload over the 154 held-out contexts (selection-priced; mean ± SD over five workload reshuffles where the policy is stochastic in the interleaving). Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 heldout contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bank: one independent bandit per context; LinUCB: one linear contextual bandit shared across contexts. Bold: best value per column (lower is better). Policy mean p99 NCCL AUTO Random Supervised GBM+cost Bank UCB1, cold Bank Softmax, cold Bank UCB1, warm Bank Softmax, warm LinUCB (cost basis), warm

5.99 45.73 1.76 7.68 5.26±0.49 1.00 1.00±0.04 0.61±0.04

I

TRLT

UCB1 NCCL cost model

0.22 1.08

Platform / coverage

Role

H100 sweep

HGX H100, Spectrum-X Ethernet, NCCL 2.30.4; 3 collectives × 4/8/16/32 nodes × 26 sizes GB200, 2 rank placements (MNNVL off: one rank per physical node; on: whole allocation); ∼310 contexts/slice Llama3 trace, nine contexts 8×HGX H100 (64 GPUs), Spectrum-X Ethernet, NCCL 2.30.7 (development build), 2 queue pairs per connection (10 long-haul), long-haul latency emulation; 22 runs, AllReduce 8×HGX H100 (64 GPUs), Spectrum-X Ethernet over RoCE, NCCL 2.32.0a4, 1 queue pair per connection, long-haul latency emulation; 6 runs, AllReduce, on the nodes and configuration of a forced-arm sweep with one stock run

primary truth

CCL-Bench H100-A live

H100-B live

ROBUSTNESS ANALYSES

This appendix collects the statistics behind the claims of Sections 3 and 6 that go beyond the headline tables: where the tail lives, tail-specific tests and scenario-level intervals, robustness to the split and to tuning, independently tuned cold champions, a margin-gated hybrid, and the full realized ranking. Every number is computed from the percontext results of the replays. I.1

Dataset

GB200 sweep

103.3 194.0 36.9 102.8 56.7 8.0 7.3 5.3

Table 25. CCL-Bench Llama3 trace replay: path TRLT (% Σµ⋆ ) over two cycles of the 719-step ordered trace (1438 steps, bandit state carried across cycles). Oracle attains 0%; the warm-started UCB1 champion and NCCL AUTO are deterministic under fixed sequential measurement pools (ten epoch replicates are identical; no SEM). AUTO loses a fixed fraction each cycle; UCB1 amortizes exploration and trends to the oracle as the workload repeats. TRLT (total relative lost time) is the latency a policy serves in excess of the measured-best arm’s, relative to the latter. Bold: best value per column (lower is better).

policy

Table 26. Datasets and their roles. The H100 sweep and the two live setups are node sets of one Spectrum-X H100 system, so the live campaigns are not independent systems.

Tail anatomy

Table 29 lists the 19 held-out contexts on which AUTO loses more than 10% realized TRLT, grouped by (AUTO’s arm, measured-best arm). In all three groups the forcedarm measurements place a protocol/algorithm crossover at a different size than the cost model, with predicted margins m of 0.06–0.57. GBM+cost removes the NVLS group and

ground

cross-architecture

workload weighting live

live, stock control

Table 27. Collective tuning approaches. Day: 0 = built-in selector, 1 = offline pre-production tuning, 2 = online production adaptation. Offline tuning covers profilers and ML tuners (e.g., FACT/ACCLAiM). CM = cost model role; bench = included in our offline benchmark. RR-ETC = round-robin explore-thencommit; † rows are emulated, not live plugin deployments.

approach NCCL AUTO Offline tuning STAR-MPI (18) AutoCCL (61) Madan RR-ETC This work

day

online

CM

bench

0 1 2 2 2 2

No No Yes Early iters Yes Live + replay

Selector No No No Gate Prior/filter

Yes No No No Yes† Yes†

leaves the other two (up to 40% and 26%), whereas UCB1 keeps every group at or below 13.5%. Table 30 splits the loss by (collective, nodes) scenario; the 4-node rows are the eight Llama3 trace contexts. Each of the six largescale scenarios contributes three contexts above 10% and between 12% and 22% of AUTO’s total test loss, so the tail is not one scenario. Splitting by NVLS involvement (AUTO’s arm or the best arm is NVLS: 19 contexts) shows AUTO at 14.8% mean there and 4.8% on the other 135, with 6 and 13 contexts above 10% respectively; UCB1 is 4.5% and 1.2%. Within-pool sampling noise does not explain these contexts. We resampled each arm’s 89 steady iterations independently (iid and 5-iteration blocks, 2000 draws). The expected exact share of AUTO is 78.1% (78.2% blocked) against the point estimate 78.6%, its mean selectionpriced loss has a 95% interval [5.92, 6.08]% and its p99

34 / 46

Table 28. Steady bus bandwidth (GB/s per GPU, nccl-tests convention) of Ring/Simple and Ring/LL128 for all-gather (AG) and reduce-scatter (RS) on the primary H100 sweep, as Simple / LL128 per node count. Each node has eight 400 Gb/s NICs, about 400 GB/s aggregate. Simple plateaus near 320 GB/s (80%) at 4 and 8 nodes, and its ramp moves to larger messages as the ring grows: at the same per-rank share (size/ranks=4 MiB) it gives 126–207 GB/s at every scale. LL128 leads by 2.3–4.1× at 16–32 nodes and 128–512 MiB, and by 1.04–1.17× at 2 GiB. Each value is the mean of one job’s steady iterations; the eight jobs per protocol (4 scales × 2 collectives) are separate. Coll. Size

4 nodes

8 nodes 16 nodes 32 nodes

AG AG AG AG AG

128 MiB 207 / 267 90 / 250 51 / 209 32 / 120 256 MiB 289 / 288 163 / 282 68 / 259 62 / 212 512 MiB 314 / 288 258 / 296 126 / 292 92 / 271 1 GiB 321 / 300 309 / 293 217 / 303 166 / 296 2 GiB 322 / 307 327 / 303 284 / 297 262 / 305

RS RS RS RS RS

128 MiB 203 / 266 91 / 250 51 / 204 33 / 127 256 MiB 289 / 288 164 / 283 68 / 262 63 / 208 512 MiB 315 / 287 259 / 297 125 / 293 93 / 272 1 GiB 321 / 298 303 / 293 216 / 303 168 / 294 2 GiB 322 / 306 327 / 302 286 / 297 264 / 306

[102.3, 104.1]%, and 18 of 18 (17 of 18 blocked) contexts above 10% keep a lower bound above 10%. The noise analysis uses selection-priced loss, where 18 contexts exceed 10% (realized accounting: 19). Because each arm’s pool is one job, this says nothing about between-job variation. The largest group, Ring/Simple chosen where Ring/LL128 is faster for all-gather and reduce-scatter, is consistent across separate jobs (Table 28). Simple reaches about 320 GB/s, 80% of the per-node NIC aggregate, at 4 and 8 nodes, so it is not throttled everywhere. Its bandwidth ramp moves to larger messages as the ring grows, as expected when each rank’s share of the message shrinks, and the crossover with LL128 moves with it. The crossover already appears at 8 nodes, a training scale, where Simple takes 2.8× LL128’s time at 128 MiB. A placement or congestion difference would have to reproduce this ordering in each of the eight jobs per protocol; repeated jobs remain the direct test. Forcing against stock. The primary sweep has no stock run. H100-B has one (all-reduce, 8 nodes, a separate job on the same eight nodes and environment as its forced runs except the pin; stock’s per-size choice was not logged), which we compare with the forced run of the exported costmodel argmin. The same nodes also ran the six live learners, which select arms through the tuner’s cost table, the interface through which a plugin applies the cost model’s choice (whether stock without a plugin runs that arm the same way is not shown); every learner’s first call at each of the 26 sizes was the exported argmin, so the cost ta-

ble NCCL handed the plugin at run time has the exported argmin. Where a learner played one arm on all 100 timed calls of a size (no setup stall), its time prices that arm under tuner selection, plugin cost included; learners tend to keep arms that did well, so this biases tuner-selected prices low, and these are separate jobs. Where that argmin is Ring/Simple (4–16 GiB), stock is within 2.3% of the forced run, and tuner-selected Ring/Simple costs 1.02–1.04× its forced run (2–8 GiB, 1–3 learners per size): forced, tunerselected and stock Ring/Simple agree within 4% where their sizes overlap (4–8 GiB, all-reduce, 8 nodes); the nine Ring/Simple tail contexts lose 16–134%. At 16–256 MiB, where the argmin is NVLSTree/Simple, stock is 11–39% faster than the forced argmin and within −13% to +10% of the forced best arm. Tuner-selected NVLSTree/Simple costs 0.70–0.98× its forced run (32 MiB–1 GiB, 2–3 learners per size), consistent with forcing slowing NVLS; the six NVLS tail contexts (12–65%) may overstate the loss of the cost model’s choice, by an amount the selection bias (which would make the NVLS ratio look lower than forcing alone causes) and job variation leave unquantified. Tuner-selected Tree/LL128 costs 1.05–1.18× its forced run (256 KiB–16 MiB, median over learners; the excess is largest below 1 MiB, where the plugin’s per-call cost is) and Ring/LL128 1.02–1.05× (64–128 MiB), so forcing makes no non-NVLS arm we can check slower than tuner selection does. Stock is the outlier: at 1–8 MiB it is 26– 51% slower than Tree/LL128 forced and 18–34% slower than Tree/LL128 selected through the tuner, and below 1 MiB it is faster than both, for a reason we cannot identify (stock’s choice and channel count were not logged). So on H100-B the AUTO row’s forced price is the cost model’s choice as a tuner plugin applies it, which differs from stock’s own run in both directions; the four Ring/LL128 tail contexts (18–26%) sit in the band where stock was slower, not faster. These checks cover AUTO’s tail arms more than the tail’s oracle arms: LL128 is checked only as Ring/LL128 at 64–128 MiB on all-reduce, whereas the Ring/Simple tail’s oracle is Ring/LL128 on all-gather and reduce-scatter at 512 MiB–2 GiB. Only if the Ring/Simple bound transferred, keeping only that group, would AUTO have 9 contexts above 10% (lowest 13.3% after a 2.3% discount; 7 after a 13% discount) to UCB1’s 0, whose one context above 10% is NVLS; all 5 scenarios that differ favour UCB1 (p=0.0625, the smallest five non-zero scenarios allow; the bounds were chosen post hoc). One of the nine is the unshifted 4-node trace context; on scale-shifted contexts the count is 8 to 0 over four scenarios. A single bound need not transfer, so we also give the discount at which each context falls to 10%: about 53% for the two 512 MiB contexts at 16 nodes, 37–38% for the 1 GiB pair at 32 nodes, 21% for the 1 GiB pair at 16 nodes, 14% for the trace context, and 5–6% for the 2 GiB pair at 32 nodes. These bound the ratio of AUTO’s to the oracle arm’s forced

35 / 46

Table 29. The 19 held-out H100 contexts (scale-out-ofdistribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size).) on which AUTO has realized TRLT above 10%, grouped by the arm AUTO plays and the measured-best arm. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. n: contexts in the group; m: AUTO’s predicted runner-up margin µ̂(2) /µ̂(1) − 1; last three columns: the largest realized TRLT in the group for AUTO, UCB1 and the supervised GBM+cost selector. AG/AR/RS: all-gather/all-reduce/reduce-scatter. Bold: best per row among the three policies. AUTO picks

best arm

Ring Simple Ring LL128 NVLSTree Simple Tree LL128 Ring LL128 Ring LL

n collectives, sizes

Table 31. Tests with the nine (collective, nodes) scenarios as the unit. “Statistic”: mean difference (pp) or exceedance-count difference (contexts above 10%) of AUTO minus the policy; sign-flip: exact two-sided over 29 sign patterns. Test

Comparison

sign-flip, scenario means wild-cluster bootstrap-t sign-flip, exceedance diff. sign-flip, scenario means wild-cluster bootstrap-t sign-flip, exceedance diff. sign-flip, scenario means wild-cluster bootstrap-t sign-flip, exceedance diff.

AUTO-UCB1 mean AUTO-UCB1 mean AUTO-UCB1 n>10 AUTO-Softmax mean AUTO-Softmax mean AUTO-Softmax n>10 AUTO-ETC mean AUTO-ETC mean AUTO-ETC n>10

Units Statistic 9 9 9 9 9 9 9 9 9

3.99 5.09 18.00 3.90 4.08 14.00 1.34 0.90 8.00

p 0.016 0.016 0.016 0.031 0.031 0.047 0.402 0.410 0.359

m AUTO UCB1 GBM+c max realized TRLT in the group (%)

9 AG/RS, 128 MiB–2 GiB 0.08–0.18 6 AR, 16 MiB–128 MiB 0.06–0.57 4 AG/RS, 4 MiB–8 MiB 0.20–0.21

134 65 26

2.9 13.5 9.1

40 0 26

I.2

Scenario-level tests and exceedance intervals

0.2 39.2 20.6 0.0 11.7 25.8 0.2 40.1 21.0

The primary test procedure is over the nine (collective, nodes) scenarios, which are fixed before looking at outcomes (Table 31): an exact sign-flip test on the scenario means and on the per-scenario difference in contexts above 10%, with a wild-cluster bootstrap-t with all 29 Rademacher sign patterns enumerated as a check (10). They give p=0.016 for AUTO−UCB1: the smallest twosided p nine clusters allow is 2/512≈0.004, and one scenario favors AUTO (Table 49). The same tests cannot separate AUTO from commit-once ETC (p≈0.4), and on GB200 they are null for UCB1 against AUTO (p=0.91, 0.81). We report about forty tests and intervals in this appendix without a multiplicity correction; only the four confirmatory comparisons of Table 33, Holm-corrected, should be read as inferential. Table 32 gives exceedance probabilities twice: the exact Clopper–Pearson interval that treats the 154 contexts as independent, which is too narrow because the failures cluster, and an exact interval on the number of scenarios with an exceedance (AUTO 7 of 9, UCB1 1 of 9), which is wide but counts the scenario as the unit. Because the sample p99 of 154 contexts lies between the second- and third-largest values, a bootstrap interval for it is bounded by the sample maximum.

latency, so they cover distortion of either arm; where H100B’s argmin is its forced-best arm, stock ranged from 41% faster than the forced run (32 KiB) to 51% slower (2 MiB), more than every break-even but the two 512 MiB contexts. The NVLS-excluded rerun (AUTO 20 contexts above 10%, UCB1 2; Section 7) changes the arm set, not the pricing, so it does not address forcing. All of this is one node set, one collective and one stock job, on another NCCL version under latency emulation; it is consistent with forcing slowing NVLSTree/Simple and not the other arms checked, finds stock without a plugin differing from the cost model’s choice by more than most tail gaps, and does not bound either effect on the primary sweep.

Table 33 gives the confirmatory family. The family is the four comparisons the claims rest on; it was chosen after the individual tests had been reported, so Holm’s step-down correction, applied within each scope, guards against multiplicity inside the family but not against choosing it. With nine scenarios the AUTO−UCB1 and warm-versus-cold claims survive it; the six 16/32-node scenarios alone (the 4-node scenarios hold only the eight trace contexts) give each the smallest p six clusters allow, 0.031, which no correction over four tests can keep below 0.05. UCB1’s count of contexts above 10% stays between one and three across three sampler seeds and the realized-objective re-tune. The split-pool rows choose each context’s oracle arm on the odd steady iterations of every pool and price every policy (selection-priced, from its pull counts) on the even ones,

Table 30. Realized TRLT (%) by (collective, nodes) scenario on the held-out H100 contexts (scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size).) for AUTO, UCB1 and the supervised GBM+cost selector. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. n: contexts; loss share: the scenario’s share of AUTO’s total test loss; mean and max over the scenario’s contexts; n>10 : contexts above 10%. 4-node rows are the Llama3 trace contexts; AG/AR/RS: allgather/all-reduce/reduce-scatter. Bold: best per row among the three policies, separately for mean and max. NCCL AUTO

UCB1

GBM+cost

Scenario

n loss share mean max n>10 mean max mean max

AG, 4 nodes AG, 16 nodes AG, 32 nodes AR, 4 nodes AR, 16 nodes AR, 32 nodes RS, 4 nodes RS, 16 nodes RS, 32 nodes

3 24 23 2 26 26 3 24 23

3% 21% 12% 0% 18% 13% 0% 22% 12%

9.5 29 8.1 131 5.0 78 0.0 0 6.3 65 4.5 50 0.0 0 8.5 134 4.9 75

1 3 3 0 3 3 0 3 3

0.67 1.3 1.08 3.3 1.19 3.7 0.00 0.0 2.81 9.9 2.84 13.5 0.43 1.3 0.43 3.0 1.50 9.1

0.08 1.83 1.63 0.00 0.94 2.35 0.05 2.91 1.61

36 / 46

Table 32. Contexts above 10% realized TRLT per policy: count (share of 154), an exact interval that treats contexts as independent, and the number of the nine scenarios with at least one such context with an exact interval on that proportion. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Policy

contexts > 10% independent-contexts interval scenarios with ≥ 1 [interval]

AUTO GBM+cost UCB1 Softmax KL-UCB ETC

19 (12.3%) 10 (6.5%) 1 (0.6%) 5 (3.2%) 4 (2.6%) 11 (7.1%)

[7.6, 18.6]% [3.2, 11.6]% [0.0, 3.6]% [1.1, 7.4]% [0.7, 6.5]% [3.6, 12.4]%

7/9 [40, 97]% 6/9 [30, 93]% 1/9 [0, 48]% 2/9 [3, 60]% 2/9 [3, 60]% 2/9 [3, 60]%

Table 34. Realized TRLT distribution (%) over the 154 held-out H100 contexts, scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32node contexts plus eight trace contexts; a context is a collective, node count and message size). TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. pq: qth percentile over contexts; CVaR5% : mean of the worst 5% (8) contexts; n>x : contexts with TRLT above x%. ETC commits after m=1 pull per arm. Bold: best value per column (lower is better). Policy

mean p50 p90 p95

NCCL AUTO Supervised GBM+cost ETC (m=1) KL-UCB Softmax UCB1

6.08 1.78 4.74 2.11 1.75 1.61

I.3 Table 33. Confirmatory family, tuning-seed variation and splitpool check (held-out test). Top: exact two-sided sign-flip p over scenario means (“mean”) or per-scenario exceedance-count differences (“contexts >10%”), realized TRLT, unadjusted and Holm-adjusted over the four rows. Middle: the UCB1 champion re-tuned with other TPE sampler seeds or on the realized objective, realized TRLT. Bottom: selection-priced TRLT with the oracle arm chosen on the odd or even steady iterations and every policy priced on the other half. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Comparison

nine scenarios p Holm p

six 16/32-node p Holm p

AUTO−UCB1, mean AUTO−UCB1, contexts >10% cold-tuned−warm UCB1, mean tuned GBM+cost−UCB1, contexts >10%

0.016 0.016 0.004 0.062

0.031 0.031 0.031 0.062

UCB1 tuning TPE seed 42 (headline) TPE seed 43 TPE seed 44 realized objective Split pool (oracle on / policy) odd / AUTO odd / UCB1 odd / GBM+cost (fixed) even / AUTO even / UCB1 even / GBM+cost (fixed)

0.047 0.047 0.016 0.062

0.125 0.125 0.125 0.125

1.61 2.05 1.53 1.62

9.9 11.3 10.7 11.4

1 2 2 3

mean (%) p99 (%) >10% 5.95 0.99 1.74 6.02 0.99 1.77

103.4 8.0 35.9 103.1 8.0 37.9

18 0 10 18 0 9

and the reverse; the ranking and the exceedance counts are unchanged, and the AUTO−UCB1 sign-flip stays at p=0.016 for mean and exceedance.

77.2 25.7 35.1 16.3 11.1 9.1

19 10 11 4 5 1

12 4 3 2 0 0

6 0 3 0 0 0

Tail statistics and scenario-clustered intervals

Table 34 gives the quantile profile, CVaR5% (mean of the worst 8 contexts), and exceedance counts. The paired exceedance comparison is exact: AUTO versus UCB1 above 10% (18 contexts only AUTO, none only UCB1, p<10−4 ), 25% (12 versus 0, p=5 × 10−4 ), and 50% (6 versus 0, p=0.03); GBM+cost versus UCB1 above 10% (10 versus 1, p=0.012); and ETC versus UCB1 above 10% (11 versus 1, p=0.006). The signed-rank test on means (p=0.34) and the sign test (24 versus 62 contexts, p=10−4 , in favor of AUTO on the typical context) answer a different question from the tail. Table 35 resamples whole scenarios (nine clusters) and blocks of four adjacent sizes (41 blocks) instead of contexts: the AUTO−UCB1 mean, p99, and CVaR5% differences keep excluding zero, and the GBM+cost p99 and CVaR differences do too while its mean difference includes zero. Nine clusters is coarse, so these intervals are indicative only. I.4

mean (%) p99 (%) >10%

p99 CVaR5% n>10 n>25 n>50

0.00 17.7 39.6 103.3 0.00 3.8 14.6 32.2 2.53 8.3 12.1 63.0 1.09 4.2 6.2 22.7 0.87 4.0 6.4 11.9 0.98 4.1 6.2 9.9

Split and tuning robustness

The main result uses one split and one sampler seed. Table 36 repeats the protocol for the reverse scale split (tune on 16/32 nodes, test on 4/8), three random 50/50 context splits (in-distribution), three leave-one-collective-out splits, and two further Optuna sampler seeds on the main split. Every row re-tunes UCB1, Softmax, KL-UCB, and ETC on that split’s train contexts (151 trials each, as in the main study), refits the supervised baselines on the same train contexts, and replays each frozen champion once on test; AUTO needs no fitting. Cells are realized test mean / p99 (%). The AUTO and GBM+cost cells of the two Optuna-seed rows repeat the main split, since those policies are deterministic, and ETC is not re-tuned in them. The tuned UCB1 champions are warm and stable across all splits (α=0.068–0.107, pseudo-count 2.20–4.45 against

37 / 46

Table 35. Paired difference (percentage points, point estimate and 95% bootstrap interval, 10,000 draws) in realized TRLT statistics under three resampling units. The first column resamples contexts as in the main text; the others resample whole (collective, nodes) scenarios or blocks of four adjacent message sizes. ◦ : the interval includes zero. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 heldout contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Contrast

statistic

AUTO−UCB1 AUTO−UCB1 AUTO−UCB1 GBM+cost−UCB1 GBM+cost−UCB1 GBM+cost−UCB1 ETC−UCB1 ETC−UCB1 ETC−UCB1

mean 4.5 [1.8, 7.8] 4.5 [2.8, 6.3] 4.5 [1.3, 8.3] p99 93.4 [36.8, 124.9] 93.4 [53.4, 128.1] 93.4 [36.9, 125.0] CVaR5% 68.1 [32.8, 102.0] 68.1 [45.4, 92.2] 68.1 [32.0, 102.3] mean 0.2 [-0.8, 1.2]◦ 0.2 [-0.8, 1.2]◦ 0.2 [-0.7, 1.2]◦ p99 22.3 [7.3, 31.3] 22.3 [10.9, 35.9] 22.3 [8.5, 31.3] CVaR5% 16.6 [5.2, 25.6] 16.6 [7.7, 27.3] 16.6 [5.8, 25.7] mean 3.1 [1.9, 4.7] 3.1 [1.4, 4.9] 3.1 [1.5, 5.2] p99 53.1 [4.8, 61.7] 53.1 [0.6, 61.4] 53.1 [0.7, 61.8] CVaR5% 26.0 [5.6, 50.5] 26.0 [2.3, 48.6] 26.0 [2.2, 49.6]

iid contexts

scenarios (9)

size blocks (41)

0.093 and 2.89 on the main split), while Softmax varies more (its tuned temperature ranges from 0.005 to 0.149) and moves its mean by up to 0.8 pp across Optuna seeds. With ten settings and few contexts per split, differences below about 1 pp in the mean or 10 pp in the p99 between the leading policies should not be read as rankings. I.5

A cost-model probe without a bandit, and other exceedance thresholds

UCB1 mostly plays AUTO’s arm, so Table 38 asks whether the bandit is needed at all. The probe plays AUTO’s arm, then every other offered arm in cost-model order; each arm’s first k samples are discarded and the next m averaged, after which it commits to the fastest, or keeps AUTO’s arm unless another beats it by a margin. A 24-point grid (k ∈ {0, 1, 2, 5}, m ∈ {1, 3, 5}, margin 0 or 5%) is scored on the train contexts and the train-best point is reported on test. Table 39 repeats the primary scenario-level test at three exceedance thresholds, and Table 37 compares the tuned static fit with UCB1 when NVLS is excluded. Under pull-count replay the train-best probe (k=1, m=1, no margin) serves exactly the samples of ETC with m=1 and one discarded sample, so its row equals ETC’s. I.6

Supervised selectors tuned like the learners

The online families get 151 TPE trials each, so Table 41 gives the tree selectors the same budget on every H100 split: 151 TPE trials (50 random start-up trials, sampler seed 42, trial 0 the fixed settings of Section 5) over the sklearn hyperparameters (gradient boosting: trees, learning rate, depth, leaf size, row and feature subsampling; random forest: trees, depth, leaf size, feature subsampling) and whether to use the node-count feature. The objective

is the mean selection-priced TRLT of the argmin choice on validation contexts inside the train partition, with folds that copy the shift each split tests: leave one train node count out for the two scale splits, leave one train collective out for the leave-one-collective-out splits, and 5-fold over contexts for the random splits. The winner is refit on the whole train partition and replayed once on test; the online cells repeat Table 36. On the main split tuning cuts GBM+cost’s validation loss from 2.05% to 0.30%, mostly by dropping the node-count feature. Its test mean drops below UCB1’s, but its tail stays heavier (7 against 1 contexts above 10%; p=0.06). Tuning is not uniformly helpful: on one random split it raises GBM+cost’s mean from 0.93% to 1.62%, and tuned gradient boosting without the cost feature reaches 6.79% on the main split against 4.76% fixed, because validation one node doubling away does not predict a test two doublings away. At seen scales, the best tuned fit has the lower mean on every random and leave-one-collective-out split, with a tail comparable to the online policies’ except when all-reduce is held out. I.7

Independently tuned cold champions

Table 42 compares, for each warm-capable family, the cold policy at the warm champion’s hyperparameters (the matched ablation of Table 2), the cold policy with its own 151-trial search (warm start pinned off, same split and sampler seed), and the warm champion. Cold-tuned train objectives are 2.3–2.5% for the five leading families against 0.82–1.07% warm (selection-priced). Paired warm−coldtuned differences are −3.2 pp (UCB1), −3.0 (Softmax), −2.8 (Gaussian Thompson), −2.9 (ε-greedy), −2.2 (KLUCB), and −0.7 (UCB-tuned), all p<0.001; UCB-V is the exception (+0.06, p=0.19). I.8

Is the prior effect a replay artifact? Commit-once and cold grids

Table 43 replays three grids on the main split with NVLS offered and with NVLS excluded: ETC with m ∈ {1, 2, 3} exploration rounds and k ∈ {0, 1, 2, 3, 5, 10} discarded first pulls per arm (the tuned champion is m=1, k=1, so it already commits on each arm’s second sample); roundrobin ETC of Madan et al. with m ∈ {1, 3, 5, 10} rounds and the 5% (their default) or 1% (tuned) safety gate, no discard; and the five leading independently tuned cold families with k ∈ {0, 1, 2, 3, 5, 10} and every other knob at its coldtuned value (k is selected on train realized TRLT). Larger k never helps in a 100-step horizon: a context has about 2.6 arms, so k=10 spends roughly 30 of the 100 steps exploring (ETC m=1: 14.3% mean), and k=2, 3 are worse than k=1 because the transient lasts about ten pulls and cannot be skipped cheaply. The only grid cell that looks past the tail is NVLS exclusion: with it, the tuned ETC (3.21%, 11.6% p99) and cold UCB1 and Softmax (3.3%, 12.0%)

38 / 46

Table 36. Realized test TRLT (mean / p99, %) on the H100 sweep per split and policy, with every learning family re-tuned and every supervised selector refit on that split’s train contexts. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Realized TRLT charges the latencies actually served; p99 is the 99th percentile over test contexts; ntest : number of test contexts. ETC is re-tuned only where listed. Bold: best mean and best p99 per row. Split scale-OOD (main) reverse scale (train 16/32, test 4/8) random 50/50, seed 42 random 50/50, seed 43 random 50/50, seed 44 leave out all-gather leave out all-reduce leave out reduce-scatter scale-OOD, Optuna seed 43 scale-OOD, Optuna seed 44

ntest

AUTO

GBM+cost

ETC

Softmax

KL-UCB

UCB1

154 154 150 150 150 98 104 98 154 154

6.08 / 103.3 3.96 / 60.7 4.43 / 74.2 5.80 / 104.0 4.62 / 74.2 4.67 / 79.9 5.66 / 50.3 4.81 / 77.1 6.08 / 103.3 6.08 / 103.3

1.78 / 32.2 1.99 / 23.8 0.75 / 13.3 0.93 / 13.0 1.10 / 10.0 0.45 / 8.2 2.34 / 43.5 0.37 / 8.4 1.78 / 32.2 1.78 / 32.2

4.74 / 63.0 4.04 / 16.9 5.07 / 51.3 4.66 / 63.2 3.73 / 18.2 2.73 / 9.0 7.61 / 71.0 2.85 / 8.0 – –

1.75 / 11.9 1.51 / 16.5 2.46 / 27.2 1.80 / 16.0 1.32 / 15.6 0.88 / 14.6 3.17 / 17.6 0.87 / 16.0 1.60 / 19.6 2.38 / 11.9

2.11 / 22.7 1.38 / 11.7 1.56 / 9.5 2.14 / 12.7 1.37 / 9.0 1.26 / 5.5 3.23 / 32.7 1.33 / 5.6 2.02 / 16.3 2.10 / 14.5

1.61 / 9.9 1.20 / 11.7 1.29 / 11.8 1.69 / 15.2 1.24 / 9.5 0.89 / 4.5 2.68 / 13.6 0.76 / 4.6 2.05 / 11.3 1.53 / 10.7

Table 37. Static fits against UCB1 with NVLS excluded, H100 test contexts. Realized TRLT charges the latencies actually served, first-use transients included; selection-priced TRLT charges each step the chosen arm’s steady-state mean. ∆scen : the equal-weight scenario-mean difference to UCB1 that the scenario sign-flip tests; p values are that test for the mean and for contexts above 10%. Policy

mean (%)

p99 (%)

n>10%

∆scen (pp)

pmean

p>10%

1.46 1.79 6.27 1.23

38.6 32.2 111.4 11.2

9 12 20 2

+0.38 +0.31 +4.36 –

0.422 0.406 0.016 –

0.031 0.031 0.016 –

GBM+cost (tuned) GBM+cost (fixed) AUTO UCB1 (champion)

Table 40. Paired tail differences of the tuned GBM+cost selector against the online champions on the H100 test contexts (realized TRLT, NVLS offered; positive: a loses more). 95% percentile intervals from 10,000 resamples of the nine (collective, nodes) scenarios, and of the 154 contexts. With nine clusters the scenario intervals are approximate. Fixed-setting GBM+cost and AUTO against UCB1 are shown for reference; their intervals come from a separate Monte Carlo run from Table 35, hence small differences.

Table 38. Cost-model probe against UCB1 on the H100 test contexts, both arm sets. Realized TRLT charges the latencies actually served, first-use transients included; selection-priced TRLT charges each step the chosen arm’s steady-state mean. “train sel.” is the selection-priced train TRLT the probe point was chosen on; p values are the scenario sign-flip against UCB1 for the mean and for contexts above 10%. Arm set

Policy

train sel.

mean (%)

p99 (%)

n>10%

pmean

p>10%

NVLS offered

AUTO Probe (k=1, m=1) UCB1 (champion)

4.04 2.42 0.86

6.08±1.58 4.74±0.75 1.61±0.19

103.3 63.0 9.9

19 11 1

0.016 0.004 –

0.016 0.500 –

NVLS excluded

AUTO Probe (k=1, m=1) UCB1 (champion)

2.17 2.36 0.56

6.27±1.66 3.21±0.22 1.23±0.18

111.4 11.6 11.2

20 2 2

0.016 0.004 –

0.016 1.000 –

Table 39. Scenario-level comparisons at several exceedance thresholds on the H100 test contexts (realized TRLT, NVLS offered). Mean: difference of the equal-weight scenario means in pp; thresholds: contexts above it for a vs b; scenario sign-flip p in parentheses. Comparison (a − b) AUTO−UCB1 GBM+cost (tuned)−UCB1 GBM+cost (tuned)−Softmax GBM+cost (tuned)−KL-UCB

mean

>5%

>10%

>20%

+3.99 (0.016) +0.07 (0.914) -0.03 (0.965) -0.25 (0.734)

25 vs 13 (0.062) 11 vs 13 (0.812) 11 vs 13 (1.000) 11 vs 12 (1.000)

19 vs 1 (0.016) 7 vs 1 (0.062) 7 vs 5 (0.844) 7 vs 4 (0.531)

15 vs 0 (0.016) 2 vs 0 (0.500) 2 vs 1 (1.000) 2 vs 2 (1.000)

have the tail of the warm champions, and the warm advantage that remains is in the mean (Table 44). The tunedETC row under NVLS exclusion (3.21%, 11.6% p99, 2 contexts above 10%) differs from Table 23 (3.26%, 13.8%, 3 contexts) only because the champion carries the reward-

Comparison (a − b)

Statistic

∆ (pp)

Scenario 95% CI

Context 95% CI

GBM+cost (tuned)−UCB1

mean p99 CVaR5%

-0.24 +17.46 +11.31

[-0.96, +0.65] [+2.62, +35.88] [+3.28, +21.58]

[-1.03, +0.73] [+1.75, +31.12] [+0.68, +22.57]

GBM+cost (tuned)−Softmax

mean p99 CVaR5%

-0.38 +15.41 +9.39

[-1.65, +0.76] [-6.12, +36.35] [-0.51, +22.45]

[-1.24, +0.61] [-5.79, +30.44] [-1.94, +21.18]

GBM+cost (tuned)−KL-UCB

mean p99 CVaR5%

-0.74 +4.64 +4.11

[-2.40, +0.56] [-22.33, +35.85] [-14.51, +22.13]

[-1.83, +0.37] [-22.05, +29.60] [-11.54, +18.15]

GBM+cost (fixed)−UCB1

mean p99 CVaR5%

+0.17 +22.32 +16.56

[-0.84, +1.22] [+10.84, +35.86] [+7.65, +27.14]

[-0.73, +1.20] [+7.54, +31.22] [+5.41, +25.41]

AUTO−UCB1

mean p99 CVaR5%

+4.46 +93.39 +68.09

[+2.81, +6.30] [+53.71, +128.48] [+45.51, +91.13]

[+1.71, +7.79] [+36.85, +125.09] [+33.60, +101.94]

renormalization wrapper (adaptive observed max) and this grid’s entry does not; we confirmed this by replaying both: with NVLS offered they agree (4.74%, 63.0%, 11), and the difference under exclusion is one context above 10%, which is what a p99 over a handful of contexts looks like. KL-UCB, whose cold search ended at k=0 and a large c, keeps a heavier tail (27.0%) with NVLS excluded, as does its warm champion (27.5%). We did not run a cold variant that visits arms in cost-model rank order: with m full rounds the order changes only when each arm is first seen, and a cost-model order would be a warm start by another name. I.9

Cold search range and the largest-scale holdout

Cold search range. The main cold-tuned UCB1 sat at the lower edge of its α range. Table 45 repeats the cold searches for UCB1 and Softmax with lower bounds 50– 100× smaller and three sampler seeds: five of six land on

39 / 46

Table 41. Supervised selectors with fixed settings and tuned like the learners (151 TPE trials, shift-matched validation folds inside the train partition), against the online champions of Table 36, on every H100 split. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Cells: realized test TRLT mean (%) / p99 (%) / n>10 , the number of test contexts above 10%; ntest : number of test contexts. Last column: exact sign-flip p over the (collective, nodes) scenarios of tuned GBM+cost against UCB1, for the mean and for n>10 . Bold: best of each of the three numbers per row. Supervised Split scale-OOD (main) reverse scale (train 16/32, test 4/8) random 50/50, seed 42 random 50/50, seed 43 random 50/50, seed 44 leave out all-gather leave out all-reduce leave out reduce-scatter

Online

ntest

GBM+cost fixed

GBM+cost tuned

RF+cost tuned

Softmax

KL-UCB

UCB1

p mean / n>10

154 154 150 150 150 98 104 98

1.78 / 32.2 / 10 1.99 / 23.8 / 12 0.75 / 13.3 / 3 0.93 / 13.0 / 5 1.10 / 10.0 / 2 0.45 / 8.2 / 0 2.34 / 43.5 / 6 0.37 / 8.4 / 0

1.37 / 27.3 / 7 1.97 / 30.7 / 7 0.64 / 13.3 / 3 1.62 / 17.7 / 11 0.77 / 9.6 / 1 0.06 / 0.4 / 0 1.64 / 24.3 / 5 0.21 / 5.9 / 0

3.23 / 76.7 / 9 1.30 / 16.0 / 6 0.69 / 16.7 / 3 0.76 / 12.7 / 4 0.75 / 9.6 / 1 0.49 / 9.1 / 1 1.72 / 24.3 / 4 0.66 / 15.2 / 2

1.75 / 11.9 / 5 1.51 / 16.5 / 10 2.46 / 27.2 / 8 1.80 / 16.0 / 10 1.32 / 15.6 / 5 0.88 / 14.6 / 3 3.17 / 17.6 / 6 0.87 / 16.0 / 3

2.11 / 22.7 / 4 1.38 / 11.7 / 3 1.56 / 9.5 / 1 2.14 / 12.7 / 5 1.37 / 9.0 / 0 1.26 / 5.5 / 1 3.23 / 32.7 / 5 1.33 / 5.6 / 0

1.61 / 9.9 / 1 1.20 / 11.7 / 3 1.29 / 11.8 / 2 1.69 / 15.2 / 6 1.24 / 9.5 / 2 0.89 / 4.5 / 0 2.68 / 13.6 / 5 0.76 / 4.6 / 0

0.91 / 0.06 0.38 / 0.12 0.01 / 1.00 0.80 / 0.25 0.10 / 1.00 0.12 / 1.00 0.38 / 1.00 0.12 / 1.00

Table 42. Realized test TRLT (mean, p99; %) of each warmcapable family cold at the warm champion’s hyperparameters, cold with its own search, and the warm champion. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Cold, warm knobs Cold, own search Warm (champion) Family

mean

p99 mean

p99 mean

p99

KL-UCB Softmax UCB1 Gaussian Thompson ε-greedy UCB-tuned UCB-V

4.94 6.71 8.82 4.93 6.63 7.07 8.65

40.8 49.5 98.7 64.5 75.0 45.6 51.7

33.9 63.0 63.0 64.5 63.5 45.6 52.2

22.7 11.9 9.9 17.8 23.3 30.1 49.8

4.27 4.77 4.84 4.93 4.97 7.07 8.80

2.11 1.75 1.61 2.17 2.12 6.35 8.86

Table 43. Commit-once and cold policies under transient controls (test, 154 contexts, %): realized mean and p99 and selectionpriced mean with NVLS offered, realized mean and p99 with NVLS excluded (restricted oracle). “Train-selected k”: the number of discarded first pulls chosen on train realized TRLT, shown as (offered/excluded). Madan rows use k=0 as in the original method; the tuned Madan champion (k=1) gives the same test numbers as the tuned ETC champion. Key: TRLT is the latency served over T =100 steps of a context in excess of the measuredbest arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). NVLS offered Policy

the same near-greedy champion (one discarded first sample, α or τ near 0.0005–0.003; 4.75–4.93% mean and 63.0% p99), and one Softmax search ends at 5.36% / 33.1% with 21 contexts above 10%. The boundary was therefore not what limited the cold policies. Largest-scale holdout. Fitting the static selectors on the 4/8/16-node contexts and testing on the 32-node contexts only (Table 46; 72–78 contexts per setting; online policies keep their frozen hyperparameters) removes most of the extrapolation: GBM+cost reaches 0.47% / 7.1% p99 on H100 against UCB1’s 1.89% / 11.0%, and 1.40% against 2.31% on GB200 MNNVL-off. With MNNVL on, AUTO (0.23%) is the best policy and GBM+cost (6.94%, 13 contexts above 10%) the worst but for linear+cost. Our reading is that the online advantage over static selectors in the main protocol is largely the cost of extrapolating two node doublings, though even with near-target data the static fit fails on one of three fabrics. GBM+cost is the better of the two static fits in every setting, so it was not chosen after the fact; the

NVLS excluded

realized p99 selection realized

p99

ETC, tuned champion (m=1, k=1) ETC m=1, k=0 ETC m=1, k=10 ETC m=3, k=10 ETC, m=1, train-selected k (offered k=1; excluded k=1) ETC, m=3, train-selected k (offered k=0; excluded k=0) Madan RR m=1, gate 1% Madan RR m=5, gate 5% Madan RR m=10, gate 5%

4.74 7.14 14.25 16.69 4.74 5.88 7.14 8.07 13.33

63.0 97.6 66.6 72.8 63.0 55.9 97.6 62.1 63.2

2.70 5.97 12.10 14.57 2.70 3.76 5.97 5.88 11.17

3.21 5.98 12.76 15.13 3.21 4.67 5.98 6.80 11.88

11.6 73.6 43.4 53.0 11.6 22.8 73.6 26.6 39.5

Cold KL-UCB, train-selected k (0/0) Cold Softmax, train-selected k (1/1) Cold UCB1, train-selected k (1/1) Cold Gauss. Thompson, train-selected k (1/1) Cold ε-greedy, train-selected k (1/1)

4.27 4.77 4.84 4.93 4.97

33.9 63.0 63.0 64.5 63.5

2.78 2.71 2.78 2.87 2.93

3.53 3.25 3.31 3.42 3.47

27.0 12.0 12.0 17.5 16.0

online champions were not re-tuned on 4/8/16 nodes. I.10

The recommended configuration, and the primary test on it

Section 7 recommends excluding the NVLS setup arm and, for a long-lived tuner, a bounded-memory mean. The headline table uses neither, so we replayed the combination on the same split and harness. Neither recommendation is pre-registered: we chose to exclude NVLS after seeing the live setup stall and the NVLS-offered test results; only the gain below is selected, on train data alone. Constant-gain mean: r̂a ← (1 − η)r̂a + ηr, the con-

40 / 46

Table 44. Warm champion versus the independently tuned cold champion (train-selected k), per family, with NVLS offered and excluded: selection-priced mean (%), realized paired mean difference warm−cold (pp, 95% bootstrap interval over contexts), realized p99 (%), and contexts above 10% (warm/cold). Bold: best value per column (lower is better). selection mean

realized p99 w/c n>10 w/c

NVLS

Family

warm

cold warm−cold [95% CI]

offered offered offered

UCB1 Softmax KL-UCB

1.00 0.93 1.18

2.78 2.71 2.78

-3.22 [-4.78, -1.97] 9.9/63.0 -3.02 [-4.42, -1.93] 11.9/63.0 -2.16 [-2.94, -1.49] 22.7/33.9

1/10 5/10 4/8

excluded UCB1 excluded Softmax excluded KL-UCB

0.77 0.70 1.37

2.24 2.19 2.63

-2.08 [-2.58, -1.60] 11.2/12.0 -2.04 [-2.44, -1.65] 8.6/12.0 -1.62 [-2.41, -0.80] 27.5/27.0

2/2 1/2 6/5

Table 45. Cold-tuned UCB1 and Softmax with an extended lower bound on α / τ and three sampler seeds (realized test TRLT, %). Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Family

sampler seed

α / τ k train sel. obj. test realized mean / p99 n>10

UCB1 Softmax UCB1 Softmax UCB1 Softmax

42 42 43 43 44 44

0.0033 0.0005 0.0030 0.2072 0.0029 0.0007

1 1 1 0 1 1

2.41 2.41 2.41 2.26 2.41 2.41

4.75 / 63.0 4.93 / 63.0 4.76 / 63.0 5.36 / 33.1 4.76 / 63.0 4.93 / 63.0

10 11 10 21 10 11

stant step-size estimator for non-stationary problems (51) that discounted and sliding-window UCB (20) build on (the first observation of an arm initializes it; a warm-started prior counts as that observation), replacing the clippedSGD mean of UCB1 and the sample means of Softmax and KL-UCB; all other knobs stay at the champions’ values, which were tuned with NVLS offered and the original estimator. η ∈ {0.05, 0.1, 0.2, 0.3, 0.5} is chosen per family on the train contexts (selection-priced train TRLT, the tuning objective of the main protocol), with and without the 1 ms update flush of Appendix D.4.3. Table 47 gives the train-selected variants. Train selects η=0.1 for UCB1 with and without the flush, so the recommended configuration is UCB1 with η=0.1 and no flush: 1.21% mean, 5.7% p99 and no context above 10%, against 1.23%, 11.2% and two for the champion. Train prefers the flush (0.45% against 0.58% selection-priced TRLT; 1.11%, 8.0% and none on test), but that objective charges no sync cost, and on H100A the measured cost of a sync (Section 7) makes a 1 ms flush, one sync every 1–3 small collectives, far more expensive than its 0.13 pp train gain, so we report it without recommending it. The deployment default of our policy library (η=0.2) was not chosen this way: we picked it on the drift replay below, which runs on the test con-

texts, so it is not a held-out choice. On this stationary test replay it is worse without the flush (1.45%, 10.6%, two contexts) and better with it (0.97%, 7.1%, one). We therefore recommend the train-selected η=0.1, accepting a larger abrupt-drift loss than η=0.2 (4.38% against 2.92% below). The ordering of the two gains also depends on the harness: in the drift replay’s stationary column (bootstrap steady-pool sampling, NVLS offered) η=0.2 beats η=0.1 (0.96% against 1.20%), and in this sequential replay with NVLS excluded the reverse holds. A plausible reason is that only sequential replay serves the lazy-initialization transient, so a gain chosen offline depends on how that transient is modelled. With the flush, train selects η=0.3 for Softmax (0.92%, 5.9%, none); KL-UCB does not improve (1.83–1.90%), and the offline replay sees only how a batched update changes learning, not what its sync costs. We did not isolate why the flush helps slightly at T =100; a batched update averages several samples, including lazyinitialization samples, into one. Table 48 applies the primary test of Section 6.1 to the comparisons the paper had tested only per context. The sign-flip statistic is the absolute unweighted mean of the nine perscenario mean differences, compared with all 29 sign patterns (two-sided); the wild-cluster bootstrap-t instead tests the context-pooled mean, which weights scenarios by their 2–26 contexts, with a cluster-robust standard error. The two reach the same conclusion in every row. GBM+cost against UCB1 is not separated on the mean in any variant (p=0.28– 0.88; Table 49 gives the per-scenario differences), and its excess of contexts above 10% is (p=0.031 in every variant, the smallest value its five or six differing scenarios allow). With NVLS excluded, AUTO versus UCB1 still rejects (p=0.016 for the mean and for the exceedance count, with the champion or the constant-gain UCB1). ETC and the cold-tuned UCB1 are worse than the warm champion in all nine scenarios on the mean (p=0.004, the smallest value nine clusters allow) but not on the exceedance count (p=1). With NVLS offered the warm champions beat their independently cold-tuned counterparts in all nine scenarios for UCB1, Softmax and KL-UCB (p=0.004), so the prior claim of Section 6.2 holds at the scenario level for the mean; its effect on the exceedance count is not significant at that level (p=0.5). Under drift (Table 52; the best↔worst swap of Appendix D.4.2, NVLS offered, bootstrap steady-pool replay, so the stationary column is not the sequential one of Table 8), the constant gain is what the drift appendix’s horizon caveat asks for: UCB1 with η=0.2 pays 2.92% dynamic TRLT under the abrupt swap against 5.88% for the discounted champion and 6.60% for the champion, with p99 9.6% against 30.6% and 34.4%. With η=0.1 it pays 4.38%. Under the gradual crossfade the UCB1 variants are within 2 pp of each other (9.1–10.9%). This is the same

41 / 46

Table 46. Largest-scale holdout: supervised selectors fit on the 4/8/16-node contexts; every policy scored on the 32-node contexts only (72 H100, 78 GB200 MNNVL-off, 74 MNNVL-on); online policies keep their hyperparameters tuned on H100 4/8 nodes. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. Realized TRLT (%, latencies actually served): mean, p99 (99th percentile over contexts), and n>10 , the number of contexts above 10%. MNNVL: multi-node NVLink. Bold: best value per column (lower is better). H100

GB200 MNNVL-off

mean

p99

n>10

mean

p99

n>10

mean

p99

n>10

AUTO ETC Softmax UCB1 KL-UCB GBM+cost linear+cost

4.80 4.73 2.30 1.89 3.06 0.47 1.99

76.2 33.7 14.5 11.0 34.7 7.1 24.5

9 7 4 1 3 1 4

3.38 4.63 2.56 2.31 2.19 1.40 4.72

51.4 28.1 13.9 18.1 16.6 18.3 87.3

8 5 1 4 2 3 6

0.23 2.72 1.61 2.76 2.47 6.94 10.50

5.4 12.4 7.9 11.7 10.7 70.0 83.0

0 1 0 6 2 13 16

Table 47. The recommended configuration on the H100 sweep, scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). NVLS is excluded from every policy and from the oracle. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measuredbest arm’s, relative to the latter. Test columns are realized TRLT (%, latencies actually served): mean, p99 (99th percentile over contexts) and n>10 , the number of contexts above 10%. “gain” is the constant-gain η selected on train; “train sel.” is the selectionpriced train TRLT (each step charged the chosen arm’s steady mean) used to select it, which for GBM+cost is its fitting error. Bold: best per test column (lower is better). Policy (NVLS excluded) AUTO Supervised GBM+cost UCB1 champion Softmax champion KL-UCB champion KL-UCB constant gain Softmax constant gain UCB1 constant gain KL-UCB constant gain, 1 ms flush Softmax constant gain, 1 ms flush UCB1 constant gain, 1 ms flush

gain train sel. test mean

p99 n>10

– – – – –

2.17 0.04 0.56 0.68 0.60

6.27 111.4 1.79 32.2 1.23 11.2 1.22 8.6 1.90 27.5

20 12 2 1 6

0.1 0.1 0.1 0.1 0.3 0.1

0.73 0.52 0.58 0.54 0.46 0.45

1.90 1.16 1.21 1.83 0.92 1.11

3 3 0 3 0 0

19.1 11.0 5.7 19.1 5.9 8.0

single-swap, T =100 test as the drift appendix, with gains read off on test contexts. The recommended configuration (NVLS excluded, constant gain) has been evaluated only in this offline replay, which updates after every collective and charges no sync cost, never live. I.11

GB200 MNNVL-on

Policy

A size gate: leaving small messages to the cost model

Below 1 MiB the live learners play AUTO’s arm on 93– 100% of timed collectives and still pay the plugin’s profiling and sync cost (Section 6.5). A size gate removes that cost where learning has nothing to find: contexts below a message-size threshold keep AUTO’s choice with the plugin passive, and the bandit runs only at or above it. Of-

fline, a gated context takes AUTO’s realized and selectionpriced TRLT and an ungated one the UCB1 champion’s (headline arm set, NVLS offered). The threshold is chosen from {none, 64 KiB, 256 KiB, 1, 4, 16, 32 MiB} by mean selection-priced TRLT on the train contexts, the tuning objective of the main protocol; train selects 1 MiB (Table 50). On the held-out H100 test contexts AUTO is exact on all 58 contexts below 1 MiB, where UCB1 pays only exploration, and all 19 of AUTO’s contexts above 10% are at 4 MiB or more. The gated policy has a 1.15% mean, 9.5% p99 and one context above 10%, against 1.61%, 9.9% and one for UCB1 everywhere. At the scenario level it is better in five scenarios, worse in none and tied in four, so the mean improvement has p=0.06 under the sign-flip test. Against the tuned GBM+cost selector (1.37%, 27.3%, seven contexts; Appendix I.6) the gated policy is not separated on the mean (p=0.41) and has six fewer contexts above 10% (p=0.06); against AUTO it is better on both (p=0.016). Test would have preferred 4 MiB (1.03%); we report the train choice. The gate does not transfer. On GB200 AUTO is not exact at small sizes (a mean of 3.2 and 2.1%, worst contexts 56 and 72%, below 1 MiB on MNNVL off and on), so the frozen H100 threshold raises UCB1’s p99 from 23.1 to 46.2% and from 15.2 to 31.3%. Chosen on each fabric’s own train contexts, as the frozen-hyperparameter protocol otherwise forbids, the threshold falls to 64 and 256 KiB and the gate changes little (2.50% and 26.3% against 2.59% and 23.1% on MNNVL off; 3.01% and 15.2% against 3.54% and 15.2% on MNNVL on). A deployment would therefore need the threshold from a sweep of the target platform, at the scale that is available. That the gate removes the plugin cost is a design property, not a measurement: NCCL still calls the profiler for gated collectives, the plugin has to return without timing or counting them, and no live run with a gate exists.

42 / 46

Table 48. Scenario-level tests with the primary procedure (realized TRLT, held-out test): exact sign-flip over the nine (collective, nodes) scenario means of a−b and over the per-scenario differences in contexts above 10%, and the wild-cluster bootstrap-t on the contextpooled mean, all two-sided; “pooled” is the context-weighted mean difference (pp), “scen.-mean” the unweighted mean of the nine scenario means that the sign-flip tests; “scen. a/b better” counts scenarios by the sign of their mean difference (ties omitted). “Recommended” is UCB1 with the train-selected constant gain η=0.1 (Table 47). Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Arm set

a vs. b

NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS excluded NVLS offered NVLS offered NVLS offered NVLS offered NVLS offered NVLS offered

AUTO vs. UCB1 (champion) GBM+cost vs. UCB1 (champion) AUTO vs. UCB1 (recommended) GBM+cost vs. UCB1 (recommended) UCB1 (champion) vs. UCB1 (recommended) GBM+cost vs. UCB1 (recommended, 1 ms flush) UCB1 (recommended) vs. UCB1 (recommended, 1 ms flush) ETC (m=1) vs. UCB1 (champion) UCB1 cold-tuned (k=1) vs. UCB1 (champion) AUTO vs. UCB1 (champion) GBM+cost vs. UCB1 (champion) UCB1 cold-tuned vs. UCB1 (champion) Softmax cold-tuned vs. Softmax (champion) KL-UCB cold-tuned vs. KL-UCB (champion) UCB1 cold (warm knobs) vs. UCB1 warm (warm knobs)

pooled a−b

scen.-mean a−b

scen. a/b better

p (sign-flip)

p (wild-t)

n>10 a/b

p (n>10 )

+5.04 +0.56 +5.06 +0.58 +0.02 +0.68 +0.10 +2.03 +2.08 +4.46 +0.17 +3.22 +3.02 +2.16 +7.20

+4.36 +0.31 +4.34 +0.28 -0.03 +0.38 +0.10 +1.92 +1.95 +3.99 +0.05 +2.71 +2.57 +1.92 +5.64

1/7 3/5 1/7 4/4 5/2 3/5 3/5 0/9 0/9 1/7 4/4 0/9 0/9 0/9 1/8

0.016 0.406 0.016 0.461 0.891 0.281 0.203 0.004 0.004 0.016 0.883 0.004 0.004 0.004 0.008

0.016 0.141 0.016 0.195 0.922 0.195 0.312 0.004 0.004 0.016 0.719 0.004 0.004 0.004 0.008

20/2 12/2 20/0 12/0 2/0 12/0 0/0 3/2 2/2 19/1 10/1 10/1 10/5 8/4 24/1

0.016 0.031 0.016 0.031 1.000 0.031 1.000 1.000 1.000 0.016 0.031 0.500 0.500 0.500 0.031

Table 49. Per-scenario mean differences a−b (percentage points of realized TRLT, H100 held-out test) behind the primary test, for AUTO and the supervised GBM+cost selector against UCB1 on both arm sets (“offered” is the headline arm set, “excl.” excludes NVLS); “rec.” is the recommended constant-gain UCB1, “+flush” with the 1 ms update flush. Negative favours a. AG/AR/RS: allgather/all-reduce/reduce-scatter. n is the number of contexts; the 4-node rows are the Llama3 trace contexts. The last row is the sign-flip statistic. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Scenario

n

AUTO−UCB1, offered

GBM+cost−UCB1, offered

AUTO−UCB1, excl.

GBM+cost−UCB1, excl.

GBM+cost−rec., excl.

GBM+cost−rec.+flush, exc

AG, 16 nodes AG, 32 nodes AG, 4 nodes AR, 16 nodes AR, 32 nodes AR, 4 nodes RS, 16 nodes RS, 32 nodes RS, 4 nodes

24 23 3 26 26 2 24 23 3

+6.98 +3.84 +8.86 +3.50 +1.69 +0.00 +8.07 +3.38 -0.43

+0.75 +0.43 -0.60 -1.87 -0.49 +0.00 +2.48 +0.10 -0.38

+6.98 +3.84 +8.86 +4.78 +3.80 +0.00 +8.07 +3.38 -0.43

+0.75 +0.43 -0.60 +0.10 -0.14 +0.00 +2.48 +0.10 -0.38

+0.27 -0.19 -0.83 +0.62 +0.98 +0.00 +2.35 -0.31 -0.38

+0.1 -0.1 -0.8 +0.9 +1.2 +0.0 +2.2 -0.2 +0.0

+3.99

+0.05

+4.36

+0.31

+0.28

+0.3

unweighted mean

I.12

A labelled target-scale sweep for the static selectors

The remaining argument for online selection is that it needs no labelled sweep at the deployment scale, while the static selectors are fit on 4/8 nodes and extrapolate. Table 51 gives the static selectors a labelled mini-sweep at the target scale and scores them on the target-scale contexts that were not labelled, against the frozen UCB1 champion on the same contexts. The mini-sweep labels every j-th message size of each 16/32-node scenario (j=8, 4, 2), every measured arm, with k post-warm-up samples (k=1, 10, 89; iterations 11..10+k, what a sweep with warm-up would record), averaged over the j offsets of the labelled sizes; the models, features and fit are those of the harness, refit on train plus labels. Without labels the script reproduces the

harness’s GBM+cost choices on the 16/32-node contexts. GBM+cost uses the labels well. With one sample per arm at every fourth size it beats UCB1’s mean on H100 and GB200 MNNVL-on; on MNNVL-off it matches UCB1 only with every second size labelled with all 89 samples (2.31% against 2.63%). Its p99 stays heavier than UCB1’s at every budget except on H100 with every second size labelled (8% against 10%). Three caveats: only these strides and budgets were tried, the static models use fixed settings, and the mini-sweep’s own cost (a warm-up per arm, including the NVLS setup stall, at every labelled size) is not charged. The bandit’s TRLT charges nothing for labels either, since its exploration is part of its served steps.

43 / 46

I.14

Table 50. Size gate: AUTO below the threshold, the UCB1 champion at or above it. scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measured-best arm’s, relative to the latter. “train sel.” is the mean selection-priced train TRLT used to choose the threshold (⋆: chosen); test columns are realized TRLT (%): mean, p99 (99th percentile over contexts) and n>10 , contexts above 10%. GB200 rows replay the frozen H100 hyperparameters; “own-train gate” chooses the threshold on that fabric’s train contexts. Bold: best per column within each block of policies (the threshold grid is not bolded). Gate threshold

train sel. mean

test mean

test p99

0.86 0.82 0.80 0.63 1.02 1.29 1.84

1.61 1.46 1.35 1.15 1.03 1.36 1.64

9.9 9.9 9.9 9.5 9.5 20.8 23.3

Held-out test, H100 (gate at the starred threshold) NCCL AUTO GBM+cost (tuned) UCB1 UCB1, size-gated

6.08 1.37 1.61 1.15

103.3 27.3 9.9 9.5

none 64 KiB 256 KiB 1 MiB⋆ 4 MiB 16 MiB 32 MiB

Margin-gated hybrid

Figure 13. AUTO confidence audit with the observable runner-up margin m. Threshold τ retains contexts with m ≥ τ . Top: con1 1 ditional mis-ranking probability (dashed, left) and retained frac1 tion P (m ≥ τ ) (green, right). Bottom: mean (dashed) and p99 1 (green) AUTO TRLT over the retained contexts. Over all con1 5 texts the error rate is 20.0%, the mean TRLT 5.04%, and the p99 6 75.4%; at τ ≃ 0.50 the retained 45.3% have 3.7%, 0.49%, and 16.4%. H100 sweep, n=300 contexts, measured-best on itera19 tions 11–99; selection-priced.

n>10

7 1 1

Figure 13 suggests a cheap policy: trust AUTO when its predicted runner-up margin is at least τ and run the ban3.80 60.1 16 2.59 23.1 8 dit only on the rest. Because bandits are independent per 2.53 46.2 10 context, the hybrid’s per-context result is exactly AUTO’s 2.50 26.3 8 or UCB1’s, so Table 54 evaluates it post hoc. Choosing Held-out test, GB200 MNNVL on τ on the train contexts gives τ =0.5, which hands 52% of NCCL AUTO 2.65 56.3 10 UCB1 3.54 15.2 13 test contexts to the bandit and reaches 1.43% mean but a UCB1, H100 gate (1 MiB) 3.24 31.3 12 17.9% p99 and three contexts above 10%, a tail between UCB1, own-train gate (256 KiB) 3.01 15.2 12 UCB1’s and AUTO’s. Margin alone does not separate the contexts AUTO gets wrong, since its catastrophic contexts have margins up to 0.57. A larger τ =0.75, which the train I.13 Tuning on the realized metric contexts did not select, matches UCB1 (1.40%, 9.9%, one The main study tunes on selection-priced train TRLT but context above 10%) while handing 72% of test contexts reports realized TRLT. We repeated the search for five famto the bandit; this is a post-hoc observation, not a recomilies with the realized train TRLT as the objective (same mended threshold. A gated ETC does not help (best train split, harness, sampler seed, search spaces, and 151 triτ =0.3: 3.09% mean, 63.0% p99). als), replayed the frozen winners once on test, and report them beside the main champions in Table 53. The I.15 Full realized ranking three leaders are not separated by the change: UCB1 stays Table 55 lists every policy on realized TRLT, with the train at 1.62% mean (p99 11.4%, three contexts above 10% mean, the p99 interval, and exceedance counts. The trainagainst one), Softmax moves to 1.63% (19.6%), Gausrealized means rank KL-UCB (1.35%), UCB1 (1.39%), sian Thompson improves (2.17% → 1.80%) and KL-UCB and Softmax (1.43%) as the selection-priced train objective is flat (2.11% → 2.20%). The realized search did not did, within noise; for the supervised rows the train column beat the main champions on train realized TRLT for Softis an in-sample fit. max and KL-UCB (1.57% against 1.43%, 1.68% against 1.35%). This shows that the 151-trial TPE search is noisy, not that either objective is better. Every realized-tuned winner is warm. ETC is unchanged (m=1 with the first sample discarded). Because the leaders stay within noise, the featured-policy choice does not depend on the tuning metric, but UCB1’s one-context tail (Table 1) is partly a property of the selection-priced champion we chose. Held-out test, GB200 MNNVL off NCCL AUTO UCB1 UCB1, H100 gate (1 MiB) UCB1, own-train gate (64 KiB)

44 / 46

Table 51. The supervised GBM+cost selector refit on the 4/8-node train contexts plus a labelled target-scale mini-sweep, against the frozen UCB1 champion (no labels), both scored on the unlabelled 16/32-node contexts. Cells: realized TRLT mean / p99 (%; TRLT is the latency served over T =100 steps in excess of the measured-best arm’s, relative to it; p99 over contexts). “1/j, k” labels every j-th size of each target-scale scenario, all measured arms, k post-warm-up samples each; values average the j offsets. The cell counts give labelled against all target-scale (context, arm) cells. Bold: the better of the two policies per platform and column, for mean and p99 separately. none

1/8, k=1

1/4, k=1

1/2, k=1

1/2, k=89

H100

labelled (context, arm) cells GBM+cost UCB1 (no labels)

0/590 1.87 / 33 1.68 / 10

74/590 1.25 / 28 1.68 / 10

148/590 1.01 / 25 1.68 / 10

295/590 0.67 / 8 1.68 / 10

295/590 0.68 / 8 1.68 / 10

GB200 MNNVL-off

labelled (context, arm) cells GBM+cost UCB1 (no labels)

0/672 4.80 / 83 2.63 / 25

84/672 3.78 / 49 2.64 / 27

168/672 3.40 / 39 2.64 / 28

336/672 2.96 / 35 2.63 / 26

336/672 2.31 / 28 2.63 / 26

GB200 MNNVL-on

labelled (context, arm) cells GBM+cost UCB1 (no labels)

0/602 3.02 / 57 3.59 / 15

75/602 2.98 / 40 3.59 / 15

150/602 2.45 / 30 3.59 / 15

301/602 2.30 / 33 3.58 / 19

301/602 2.32 / 33 3.58 / 19

target-scale labels (sizes, samples per arm)

Table 52. Constant-gain means under the drift replay (dynamic TRLT mean, p99 in parentheses, %; 154 test contexts, 10 seeds, T =100, NVLS offered). Gains are a fixed grid, not train-selected. Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Policy AUTO UCB1 champion UCB1, γ=0.995 UCB1, gain 0.1 UCB1, gain 0.2 Softmax champion Softmax, γ=0.85 Softmax, gain 0.1 Softmax, gain 0.2

stationary

abrupt

gradual

5.99 (131.7) 0.87 (6.5) 1.05 (6.3) 1.20 (7.9) 0.96 (6.5) 0.75 (9.4) 0.84 (6.2) 1.13 (16.0) 0.86 (9.0)

45.01 (200.4) 6.60 (34.4) 5.88 (30.6) 4.38 (15.5) 2.92 (9.6) 31.57 (134.6) 5.96 (19.1) 8.10 (24.8) 4.97 (22.1)

44.60 (199.8) 10.93 (47.7) 10.68 (46.8) 9.35 (37.4) 9.13 (41.3) 31.99 (139.4) 13.11 (77.5) 11.15 (39.7) 9.79 (39.2)

Table 54. Hybrid that plays AUTO when its predicted runner-up margin m=µ̂(2) /µ̂(1) −1 is at least τ and UCB1 otherwise, H100 sweep, scale-out-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). “to bandit”: share of test contexts handed to UCB1. TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measuredbest arm’s, relative to the latter. Realized TRLT (%, latencies actually served): mean, p99 (99th percentile over contexts), max, and n>10 , contexts above 10%. ∗ : τ selected on train+eval. Bold: best value per column (lower is better). train

Table 53. Champions tuned on selection-priced train TRLT (main study) and on realized train TRLT: train realized mean, held-out test realized mean and p99, and contexts above 10% (%). Key: TRLT is the latency served over T =100 steps of a context in excess of the measured-best arm’s, relative to it; realized pricing charges the latencies actually served, selection pricing the chosen arm’s steady-state mean; test is the 154 held-out contexts (16/32 nodes plus eight trace contexts) of policies tuned on 4/8 nodes; p99 is over contexts; pp: percentage points. Bold: best value per column (lower is better). Tuned on selection-priced train TRLT (main) Tuned on realized train TRLT Family

train

test

p99

n>10 train

test

p99

n>10

UCB1 Softmax Gaussian Thompson KL-UCB ETC

1.39 1.43 1.66 1.35 4.16

1.61 1.75 2.17 2.11 4.74

9.9 11.9 17.8 22.7 63.0

1 5 11 4 11

1.62 1.63 1.80 2.20 4.74

11.4 19.6 16.3 13.0 63.0

3 6 5 3 11

1.17 1.57 1.57 1.68 4.15

45 / 46

test (154 contexts)

τ

to bandit

mean

mean

p99

max

n>10

0 (AUTO) 0.1 0.2 0.3 0.5∗ 0.75 1.0 (UCB1)

0% 13% 24% 40% 52% 72% 100%

3.98 2.44 1.57 1.08 1.01 1.22 1.39

6.08 2.83 2.01 1.59 1.43 1.40 1.61

103.3 41.4 37.6 27.6 17.9 9.9 9.9

134 50 50 43 33 13 13

19 13 7 4 3 1 1

Table 55. All policies on realized TRLT (%), H100 sweep, scaleout-of-distribution split: tuned or fit on the 4/8-node contexts, scored on the 154 held-out contexts (all 16/32-node contexts plus eight trace contexts; a context is a collective, node count and message size). TRLT (total relative lost time, %) is the latency a policy serves over T =100 steps of a context in excess of the measuredbest arm’s, relative to the latter. Realized TRLT charges the latencies actually served. Columns: train (train+eval) mean, an insample fit for supervised rows; test mean ± SEM over contexts; test p99 (99th percentile over contexts) with its 95% bootstrap interval; n>10 and n>50 , the contexts above 10% and 50%. Supervised rows without “+cost” lack the cost-model prediction as a feature. Rows sorted by test mean; bold: best per test column (Random excluded). train

test, realized TRLT (%)

Policy

mean mean ± SEM

Supervised GBM+cost, tuned UCB1 Softmax Supervised GBM+cost KL-UCB ε-greedy Supervised linear+cost Gaussian Thompson Supervised random forest+cost Hierarchical EXP3/Softmax Madan RR-ETC ETC Supervised GBM NCCL AUTO UCB-tuned Supervised random forest UCB-V Tsallis-Inf EXP3 FPL EXP3++ Random Supervised linear

– 1.37±0.43 1.39 1.61±0.19 1.43 1.75±0.22 0.04 1.78±0.50 1.35 2.11±0.36 1.42 2.12±0.46 2.96 2.14±0.49 1.66 2.17±0.34 0.29 3.97±1.44 4.97 4.60±0.72 4.15 4.74±0.75 4.16 4.74±0.75 0.19 4.76±1.36 3.98 6.08±1.58 6.32 6.35±0.54 0.17 6.85±1.87 9.54 8.86±0.77 9.72 9.77±0.86 9.99 10.57±0.89 11.27 12.05±1.04 28.92 29.58±2.01 42.30 46.85±3.79 77.54 65.35±12.30

p99

p99 95% CI n>10 n>50

27.3 [12.7, 40.1] 9.9 [7.6, 13.5] 11.9 [7.5, 22.2] 32.2 [18.3, 40.1] 22.7 [8.1, 38.5] 23.3 [13.1, 53.4] 29.3 [18.0, 42.8] 17.8 [15.1, 22.9] 103.3 [27.3, 134.2] 42.4 [16.8, 72.5] 63.0 [15.3, 71.2] 63.0 [15.3, 71.2] 76.7 [39.7, 129.8] 103.3 [46.3, 134.2] 30.1 [14.4, 66.8] 102.5 [67.9, 184.5] 49.8 [22.2, 77.9] 57.4 [27.4, 82.6] 57.6 [27.4, 81.3] 66.3 [37.3, 83.8] 101.9 [80.6, 104.1] 190.3 [145.7, 197.3] 596.9 [549.9, 705.0]

7 1 5 10 4 7 8 11 9 21 11 11 18 19 16 21 41 37 55 72 122 125 43

0 0 0 0 0 1 0 0 4 2 3 3 5 6 1 8 2 2 2 3 34 53 33

46 / 46

Related documents

• Agentic Empirical Asset Pricing: Methodological Foundations#820744
• Circumventing the Computational Hardness of Computational Arbitrage#1533683
• AutoSciBench: Autonomous Benchmark Generation for Evaluating Scientific Agents#1201153
• Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits#1122820
• Same Pieces, Different Servers: A Tetris Benchmark for AI Agents as Served#1200869