StageFrontier: Synchronization-Aware Stage Accounting for Distributed ML Training
arXiv:2606.06751v1 [cs.DC] 4 Jun 2026
Boram Yoon NVIDIA [email protected]
Wei Chen NVIDIA [email protected]
Ville Kallioniemi NVIDIA [email protected]
Abstract When a distributed training job slows down, the hard part is knowing where to look. Synchronization hides the cause: a stall on one rank shows up as a wait on the others, so a data delay on a single rank can surface as backward time across the group. The cheap dashboards that run all the time — per-stage averages and maxima — misread this, double-counting the same exposed delay or burying the slow rank in an average, while full profilers see it clearly but are far too heavy to leave on. StageFrontier is an always-on signal that closes this gap. Each rank reports only a short ordered vector of coarse stage durations — data, forward, backward, and so on — timed with CPU wall-clock, with no synchronized clocks and no kernel tracing. At each stage boundary, StageFrontier takes the cumulative time of whichever rank is furthest along; the increments of this frontier form an exact, additive accounting of the step’s exposed time and point to the stage and rank where group-visible delay first appears, telling an operator where to aim a heavy profiler, not which fix to make. The accounting is exact, but the coarse signal alone cannot tell whether a leading stage truly caused the slowdown or merely ran alongside it; StageFrontier labels the windows where that distinction needs more evidence instead of guessing. A PyTorch implementation adds under 0.2% throughput overhead through 128 ranks on Gloo and NCCL, places injected faults among its top two suspects on all 50 rows of a hidden-rank DDP test, and recovers the same top-stage routing as PyTorch Profiler, HTA, and Nsight Systems once their traces are reduced to the same coarse stages — from a 0.11 MB summary instead of a 15.81 GB trace.
1
Introduction
When a distributed training job is slow, the first question is where the delay actually originated, not just where it appears in stage timers. Synchronization displaces visible symptoms: a slow data stage on one rank surfaces as backward wait on the others, so the stage with the largest timer is often downstream from the real cause. The exposed delay — the portion not hidden under overlap, which genuinely adds to step time — could be anywhere in the pipeline: data loading, forward/loss, backward, callbacks, or optimizer work, on any rank. A wrong first answer is expensive: operators collect heavy traces, drain nodes, or rerun a multi-thousand-GPU job before discovering the symptom was a synchronization-displaced reflection of an upstream stall on a different rank. Modern systems make this harder: DDP overlaps gradient communication with backward through CUDA streams, FSDP-style sharding inserts all-gather and reduce-scatter boundaries that absorb sibling skew, and pipeline, tensor, and expert parallelism add role-specific dependencies that mix into one global rank index [15, 22, 24]. Gradient accumulation hides which microbatch waited, and asynchronous CUDA execution means CPU wall-clock time records when work becomes host-visible, not where it launched [20]. A rank that looks slow in backward may simply be waiting for a sibling whose input pipeline stalled; scalar stage timers alone cannot separate these executions.
1
Existing tools sit at the two ends of a cost/coverage curve. Throughput dashboards that aggregate per-stage maxima or averages run continuously but are ambiguous on displaced work: maxima can add an upstream stall and a downstream duplicate wait, averages hide rare rank tails, and a slowest-rank breakdown can blame a victim. Heavyweight profilers [19, 23, 28] and trace analyzers [18] resolve this ambiguity by directly observing waits, idle gaps, and timeline dependencies, but at much higher overhead and storage cost; HPC critical-path and wait-state analyzers [4, 9, 12, 27] produce richer attribution still but require event traces or full operator graphs. The missing layer is a profiler-router: low enough volume to run continuously, structured enough to tell the operator which rank, stage, and role to investigate first, and labeled clearly enough that downstream automation can decide when to invoke the heavier tools. Frontier accounting closes the gap. The key insight is simple: at each stage boundary, track how far the furthest-along rank has progressed. The increments of this running maximum form an exact, additive decomposition of the step’s exposed time, and each increment points to the stage where group-visible delay first appeared — with no synchronized clocks and no per-stage torch.cuda.synchronize() (see Section 3 and Figure 2). Where heavyweight profilers observe idle gaps, synchronization events, and dependency edges directly, StageFrontier sees only per-rank stage durations in which any wait is mixed into the stage where the host observed it. From how those progress curves cross, it recovers the same decomposition exactly — cheaply enough to run all the time. Bottleneck-cause attribution additionally requires an explicit synchronization-wait exposure model, which holds most cleanly for homogeneous synchronous DDP-style training. Outside that model (MoE, model-parallel roles, heavy overlap), StageFrontier emits a downgrade label — co_critical (the lead stage may merely run alongside the bottleneck rather than cause it), role_aware_needed (ranks play different parallelism roles so global aggregation is unsafe), or telemetry_limited (the signal is incomplete) — and leaves the cause open. Contributions. 1. A minimal telemetry contract for ordered, residual-closed (stage durations sum back to the measured step time), clock-independent distributed stage vectors collected without per-stage CUDA synchronization. 2. Frontier accounting with exact telescoping, a slack identity that prevents downstream double-charging, and formal min(𝑅, 𝑆) overcounting / 𝑅 undercounting bounds against max/average summaries. 3. Evidence semantics that distinguish accounting, synchronization-wait attribution, direct exposure, cocriticality, and telemetry limits. 4. A PyTorch implementation and confirming evaluation: compact fault routing (injected stage lands in the top-two candidate stages on all 50 test rows; metric defined in Section 4) at sub-percent always-on overhead through 128 ranks on Gloo and NCCL, broad-stage agreement with PyTorch Profiler, HTA (Holistic Trace Analysis), and Nsight on a selected window, and removed-injection, gradient-accumulation, and FSDP/ZeRO-1 spot checks. Five field cases (Section 6.5) and a recorded set of failure modes (Section 6.6) show how the routing signal maps to operator action and where it breaks.
2
Motivating Example
Figure 1 shows the displacement pattern that motivates the accounting model. Rank 𝑟 0 reaches its data boundary late; the other two ranks arrive at the backward synchronization point early and observe the same group delay as backward wait. Host-visible scalar timers therefore report a large backward time on 𝑟 1 and 2
fwd
data
bwd
host-visible sync wait
fwd
data tail
𝑟0
bwd
𝑟1
data
fwd
wait in bwd
bwd
𝑟2
data
fwd
wait in bwd
bwd
frontier after data 𝐹𝑡 ,1 = 6.0 per-stage max: 6.0 + 1.0 + 6.2 = 13.2 s
naive scalar timer: charges ≈ 5 s wait to bwd on 𝑟 1 , 𝑟 2
rank-local elapsed time exposed step time 𝐹𝑡 ,𝑆 = 8.2
(upstream data max + downstream wait duplicate)
frontier: 𝑎 data + 𝑎 fwd + 𝑎 bwd = 6.0 + 1.0 + 1.2 = 8.2 s
(matches exposed makespan)
Figure 1: Synchronization displacement in one logical step. Per-rank scalar timers duplicate the same 5 s group wait across the waiting ranks’ backward spans. A per-stage maximum then selects one downstream backward duplicate and adds it to the upstream data maximum, inflating the attributed total to 13.2 s; the frontier identity charges the first exposed advance to the upstream data boundary and recovers the actual exposed makespan, 8.2 s. Stage abbreviations data, fwd, bwd denote the data-loading, forward-pass, and backward-pass stages (formal names in Section 3). 𝑟 2 even though no rank performed extra backward work — the slowdown originated in 𝑟 0 ’s data stage. On the host-visible durations 𝑟 0 = (6.0, 1.0, 1.2), 𝑟 1 = (1.0, 1.0, 6.2), 𝑟 2 = (1.1, 1.0, 6.0) for (data, fwd, bwd), per-stage maximum totals 6.0 + 1.0 + 6.2 = 13.2 s, selecting the upstream data maximum and also a duplicate downstream backward wait; per-stage average smears the duplicates while hiding 𝑟 0 ’s tail; the frontier (the running maximum over ranks of cumulative stage time; defined precisely in Section 3) charges 6.0 to data, 1.0 to forward, 1.2 to backward, summing to exactly the exposed makespan 8.2 s and pointing to the upstream boundary that first exposes it. The production setting drives every design choice: • Continuous measurement with no per-step barriers and no explicit CUDA synchronization on the hot path. • Stable broad stage semantics comparable across models, with deeper probes as side evidence only. • Rank-safe aggregation: any monitoring collective is opt-in and may fail without failing training. • Prefetch-aware alignment that charges a data wait to the step that consumes the batch rather than the loop iteration that called next. • Evidence-scoped output that separates accounting, model-scoped attribution, and telemetry quality so automation does not add unsupported assumptions. Stage taxonomy and ordered-stage contract are in Appendix A. We use three terms precisely: low-volume is a structural property of the telemetry, low-overhead is a measured property of an implementation, and always-on additionally requires bounded queues, symmetric failure-safe collection, and conservative downgrades.
3
Frontier Accounting
StageFrontier records a fixed list of non-overlapping trainer-stage spans per rank using CPU wall-clock time. The six default stages are data.next_wait, model.fwd_loss_cpu_wall, model.backward_cpu_wall, 3
callbacks.cpu_wall, optim.step_cpu_wall, and a residual step.other_cpu_wall that absorbs closure error (Appendix A). For step 𝑡, rank 𝑟, and ordered frontier stage 𝑠, let 𝑑𝑡 ,𝑟 ,𝑠 ≥ 0 be the measured duration. Define the rank-local prefix and the max-prefix frontier: ∑︁ 𝑃𝑡 ,𝑟 ,𝑠 = 𝑑𝑡 ,𝑟 , 𝑗 , 𝐹𝑡 ,𝑠 = max 𝑃𝑡 ,𝑟 ,𝑠 , 𝑎 𝑡 ,𝑠 = 𝐹𝑡 ,𝑠 − 𝐹𝑡 ,𝑠−1 . (1) 𝑟∈R
𝑗 ≤𝑠
Set 𝐹𝑡 ,0 = 0, so 𝑎 𝑡 ,1 = 𝐹𝑡 ,1 . Because rank-local prefixes are nondecreasing, the frontier is nondecreasing and 𝑎 𝑡 ,𝑠 ≥ 0. For a window T of 𝑁 = |T | steps, the reported stage share is step-time weighted: Í 𝑎 𝑡 ,𝑠 𝐴𝑠 = Í 𝑡 ∈ T . (2) 𝑡 ∈ T 𝐹𝑡 ,𝑆 The accounted quantity is the maximum rank-local exposed duration for an aligned logical step, 𝐹𝑡 ,𝑆 , not a wall-clock span from earliest host start to latest finish; the method therefore needs only step-index agreement and rank-local monotonic durations, not synchronized host clocks. Cross-step prefetch and run-ahead break that alignment; StageFrontier then either reassigns data.next_wait to the consuming step (Appendix A) or, when reassignment is unsafe, emits a telemetry-quality downgrade rather than an attribution. Figure 2 illustrates the construction where a different rank bounds the frontier at each boundary. prefix time (s) 𝑟0
𝑟1
𝑟2
frontier 𝐹𝑡,𝑠
8
𝑎 bwd = 2.5 s (from 𝑟 2 ) 6
𝑎 fwd = 2.0 s (from 𝑟 1 ) 4
𝑎 data = 4.0 s (from 𝑟 0 ) Í 𝑠 𝑎 𝑠 = 𝐹𝑡 ,𝑆 = 8.5 s
2
data
fwd
bwd
Figure 2: Max-prefix frontier accounting on a three-rank scenario where a different rank bounds the frontier at each boundary. Each rank’s prefix curve 𝑃𝑡 ,𝑟 ,𝑠 is drawn at every boundary; the frontier 𝐹𝑡 ,𝑠 = max𝑟 𝑃𝑡 ,𝑟 ,𝑠 (purple) takes the latest rank: 𝑟 0 at data, 𝑟 1 at fwd, 𝑟 2 at bwd. The vertical advances form the additive decomposition 𝐹𝑡 ,𝑆 = 4.0 + 2.0 + 2.5 = 8.5 s, attributing each increment exactly once to the rank attaining the frontier. This is an accounting identity; reading it as a cause requires the model of Section 4. The accounting core is a single pass over steps, ranks, and stages: for t in window: F_prev = 0 for s in ordered_stages: F = max over r of prefix_sum(d[t,r,1:s]) a[t,s] = F - F_prev; F_prev = F This performs 𝑂 (𝑅𝑁 𝑆) arithmetic per window and streams one step at a time in 𝑂 (𝑅𝑆) memory once that step’s rank-stage matrix is available. Edge cases are explicit: with 𝑅 = 1 the frontier reduces to the rank’s 4
ordered vector and gives no cross-rank evidence; below a small window-denominator floor the implementation emits raw advances rather than percentages; missing stages, mismatched schemas, or mixed world sizes close the current window. Í Theorem 1 (Additive exposed-makespan accounting). For any aligned nonnegative stage vectors, 𝑆𝑠=1 𝑎 𝑡 ,𝑠 = 𝐹𝑡 ,𝑆 . Í Proof. Telescoping: 𝑠 (𝐹𝑡 ,𝑠 − 𝐹𝑡 ,𝑠−1 ) = 𝐹𝑡 ,𝑆 − 𝐹𝑡 ,0 = 𝐹𝑡 ,𝑆 . □ Slack identity.
Define rank-𝑟 slack at boundary 𝑠 as 𝜆 𝑡 ,𝑟 ,𝑠 = 𝐹𝑡 ,𝑠−1 − 𝑃𝑡 ,𝑟 ,𝑠−1 ≥ 0. Then 𝑎 𝑡 ,𝑠 = max 𝑑𝑡 ,𝑟 ,𝑠 − 𝜆 𝑡 ,𝑟 ,𝑠 ,
(3)
𝑟
so a rank that arrives early at 𝑠 − 1 has its current-stage duration discounted by exactly the prior slack it owes the group. This is why a slow data step that forces others to wait is charged once to the data boundary, not again to backward on the ranks that waited. Comparison with per-stage max and average.
Let 𝑀𝑡 =
Í
𝑠 max𝑟 𝑑 𝑡 ,𝑟 ,𝑠 and 𝑀 𝑡 =
Í
𝑠𝑅
−1 Í 𝑑 𝑟 𝑡 ,𝑟 ,𝑠 .
Proposition 1 (Per-stage max overcounting). 𝐹𝑡 ,𝑆 ≤ 𝑀𝑡 ≤ min(𝑅, 𝑆) 𝐹𝑡 ,𝑆 ; the upper bound is tight. Proposition 2 (Per-stage average undercounting). 𝑅 −1 𝐹𝑡 ,𝑆 ≤ 𝑀 𝑡 ≤ 𝐹𝑡 ,𝑆 ; the lower bound is tight. Per-stage maxima can charge the same exposed second up to min(𝑅, 𝑆) times; per-stage averages can hide rank tails by a factor of 𝑅. Proofs and a companion measurement-error stability result (errors of order 𝑠𝜖 on prefixes and (2𝑠 − 1)𝜖 on advances) are in Appendix D. For accumulation factor 𝑚, the ordered list is expanded by accumulation index before the frontier is taken, and semantic reporting groups are aggregated only afterward so repeated microsteps are not collapsed prematurely; changed factors or sync patterns close the window.
4
Synchronization-Wait Model and Evidence
The frontier is always an accounting signal; bottleneck routing requires an explicit synchronization-wait exposure model, since the same scalar matrix can represent sync wait or independent overlapped work. Write 𝑑𝑡 ,𝑟 ,𝑠 = 𝑥 𝑡 ,𝑟 ,𝑠 + 𝑞 𝑡 ,𝑟 ,𝑠 , with 𝑥 productive rank-local work and 𝑞 host-visible waiting charged to the stage in which the host observes it (a kernel launched in forward but observed in backward is recorded in backward; a collective wait is recorded in its enclosing trainer stage). Profilers and wait-state analyzers observe parts of 𝑞 directly — as idle, synchronization, or communication events with dependency edges — and attribute them. StageFrontier instead treats 𝑞 as latent, reasoning only from the ordered progress matrix 𝑑 in which 𝑞 is lumped with productive work 𝑥. It recovers the part of 𝑞 that is exposed in the makespan without ever separating 𝑞 from 𝑥 or observing it as a typed event. A wait segment 𝑞 𝑡 ,𝑟 ,𝑠 has a dependency edge to another rank’s completion of an earlier ordered boundary and shrinks only when that predecessor prefix advances. Under the assumptions of Table 1 — residual closure, aligned steps, common boundary semantics, monotonic timing, wait-dependency charging, homogeneous productive work (or role-aware grouping), and a sufficient dominance margin — the slack identity implies that the only newly exposed group time at a boundary is the amount by which some rank’s prefix exceeds the previous frontier, so frontier advances identify the earliest measured boundary at which delay becomes exposed. The table also gives the evidence label emitted when an assumption is doubtful. The causal reading — that this time was caused by an upstream straggler rather than independent overlapped work — follows from wait-dependency charging plus rank comparability; when either is questionable the 5
Table 1: Assumptions of the synchronization-wait exposure model and the evidence label emitted when one is doubtful (deterministic gates in Appendix C). Assumption
If doubtful
Residual closure and aligned logical steps Common ordered boundary semantics Rank-local monotonic timing Wait-dependency charging Homogeneous productive work or role-aware grouping Sufficient dominance margin
telemetry_limited role_aware_needed telemetry_limited co_critical role_aware_needed co_critical
labeler emits co_critical or role_aware_needed. As a sharp case, the two-rank matrix 𝑟 0 = (10, 0), 𝑟 1 = (0, 10) gives 𝐹data = 𝐹bwd = 10 and charges 10 to data and 0 to backward, but is equally consistent with 𝑟 1 waiting on 𝑟 0 ’s data (data causal) or with two independent co-critical paths; StageFrontier emits the model-scoped attribution only when workload semantics support it, and otherwise carries a co_critical ambiguity set such as {data, backward}, reported as the machine-readable co_critical_stages field. A complementary direct-exposure score replaces stage 𝑠 with a clipped baseline and recomputes the frontier. Let 𝑏˜ 𝑡 ,𝑟 ,𝑠 be a candidate baseline for stage 𝑠 — a per-rank window median, cohort median, or no-stall reference — clipped to 𝑏 𝑡 ,𝑟 ,𝑠 = min(𝑑𝑡 ,𝑟 ,𝑠 , 𝑏˜ 𝑡 ,𝑟 ,𝑠 ) so the replacement never exceeds the observation: Í 𝐺 𝑠 (𝑏) =
𝑡
𝐹𝑡 ,𝑆 − 𝐹𝑡(𝑠←𝑏) ,𝑆 Í ≥ 0. 𝑡 𝐹𝑡 ,𝑆
(4)
For a feasible baseline whose stage-𝑠 reduction also removes the downstream wait it induces, 𝐺 𝑠 lower-bounds the model-scoped gain; otherwise it is a conservative sensitivity score, not an intervention estimate, since the recomputation leaves any non-removable downstream wait in place. High 𝐴𝑠 with high 𝐺 𝑠 supports direct_exposure; high 𝐴𝑠 with low 𝐺 𝑠 supports sync_wait_dependent when workload semantics agree and co_critical otherwise. For localization the labeler reports the latest-rank tie set, the lag 𝐿 𝑡 ,𝑠 = max𝑟 𝑃𝑡 ,𝑟 ,𝑠 − median𝑟 𝑃𝑡 ,𝑟 ,𝑠 and its increment, and the max-minus-secondmax gap, counting switches only between confident unique leaders. Labels (Table 2) describe orthogonal evidence axes, not a flat confidence ladder; the full label set and deterministic downgrade gates are in Appendices B–C. The routing candidate set 𝐶route is the smallest leading-share prefix whose cumulative share reaches 𝜏𝐶 (default 0.80); the evaluation reports top-2 (seeded stage among the two highest shares) and candidate hit (anywhere in the prefix), always paired with candidate-set size. The routing set is kept separate from the ambiguity set (co_critical), so a row can route to a compact set while still flagging the stages that remain jointly plausible. Table 2: Core diagnosis labels emitted in the main pipeline. Label
Meaning
frontier_accounting direct_exposure sync_wait_dependent co_critical role_aware_needed telemetry_limited
Additive exposed-makespan decomposition; base claim. Raw duration, spread, and clipped static gain agree with the frontier stage. Frontier share high but static gain low; actionability depends on the wait model. Multiple stages or ranks can plausibly remain bottlenecks after optimizing one stage. Rank roles differ; global rank aggregation is unsafe. Residuals, gather failures, or missing probes cap confidence.
6
5
PyTorch Implementation
The minimal integration wraps the logical optimizer step with one step context and ordered, non-overlapping stage contexts: with perf.step(): with perf.stage("data.next_wait"): batch = next(data_iter) with perf.stage("model.fwd_loss_cpu_wall"): with perf.cuda_event_sample("model.fwd_loss_cuda_event_ms"): loss = forward_loss(batch) with perf.stage("model.backward_cpu_wall"): loss.backward() with perf.stage("callbacks.cpu_wall"): run_callbacks() with perf.stage("optim.step_cpu_wall"): optimizer.step() For DDP — and for the PyTorch ZeroRedundancyOptimizer spot check (ZeRO-1-style optimizer-state sharding, distinct from DeepSpeed ZeRO) — this placement includes reducer activity and exposed collective waits in the backward stage; for FSDP FULL_SHARD, all-gather, reduce-scatter, and parameter materialization are charged to the broad forward, backward, or optimizer region in which the host observes them. StageFrontier avoids torch.cuda.synchronize() on the hot path so monitoring does not perturb overlap; the price is that stage timing follows host-visible exposure, which is exactly what the frontier identity decomposes, while kernel-level attribution remains the profiler’s job. An optional CUDA-event forward channel, sampled at deterministic fraction 𝑞 ∈ {0, 0.05, 1}, records two timing events around the forward/loss region and polls readiness at later safe points [21]; the event value is side evidence only, never enters the prefix vector, and can support a forward_device_supported label or suggest host overhead when CPU-wall forward is high but event time is low. A window-boundary collective gathers the per-rank [𝑁, 𝑆] buffer to rank 0 over a separate Gloo or NCCL telemetry process group; a failed or timed-out gather records gather_ok=false, emits any safe local summary, and downgrades distributed labels to telemetry_limited, never failing training. For rank count 𝑅, 𝑁 steps, 𝐾 ordered stage fields, and 𝑏 bytes, the dense root-visible payload is 𝐵root = 𝑅𝑁𝐾 𝑏 (≈ 0.61 MB at 𝑅=128, 𝑁=100, 𝐾=6, 𝑏=8; the 32-rank E9 evidence packets of Section 6.3 measure 0.11 MB); fractional overhead is the gather-path time divided by training time in the window, so longer windows amortize it.
6
Evaluation
We evaluate StageFrontier with the stagefrontier-artifact repository. Cluster experiments use bf16 transformer training in the NVIDIA PyTorch 24.12 container; DDP is the main validation path, Gloo telemetry gather is the main backend, and the overhead matrix additionally evaluates NCCL. The main E0–E5 routing/overhead matrix disables gradient accumulation; E6 is a removed-injection A/B/A check, E7 a fixed-factor gradient-accumulation spot check, E8 a scope-extension spot check for PyTorch FSDP FULL_SHARD and ZeroRedundancyOptimizer ZeRO-1, and E9 a 32-rank selected-window comparison against PyTorch Profiler, HTA, and Nsight Systems. Faults are host-side delays injected into the CPU-wall span of one rank (12–360 ms depending on scenario); most rows surface the delay as host-visible time, and only the synchronization-bearing rows additionally place a torch.distributed.barrier() in the affected span so the delay is exposed rather than absorbed. Windows span 120–600 measured steps after 20 warmup steps, the fractional overhead 𝜌 divides gather-path time by training time in the window, and the paired bootstrap resamples whole run/window blocks rather than individual steps. Experiment groups are defined in Appendix F (Table 16); per-group model and hardware configuration, exact step counts, and bootstrap scripts are recorded in the artifact’s structured rows and Slurm wrappers. Table 3 maps each research question to its supporting evidence. 7
Table 3: Evidence and supporting sections for each research question (RQ1–RQ5). RQ
Evidence
Section
RQ1
Telescoping identity at floating-point roundoff; max/avg bounds; 100% sync-wait fixture recovery vs. 0% for max/average. Five fault classes 50/50 top-2 (40/50 top-1) at 8/32 ranks plus 64/128-rank spot checks; event channel separates forward-device vs. host; 32-rank selected windows agree with PyTorch Profiler / HTA / Nsight on 12/12 positive rows under a shared reducer. Fixed-factor grad-accum spot check passes; FSDP FULL_SHARD and ZeRO-1 route 90/90 sync-bounded rows top-2, 87/90 top-1. 95% CI upper bound ≤ 0.181% CPU-wall and ≤ 0.043% event-channel through 128 ranks on Gloo and NCCL. Five field deployments routed investigators to dataloader, callback, post-op, and QAT actions; two corroborated by a profiler trace and an op-level ablation.
6.1, 6.2
RQ2
RQ3 RQ4 RQ5
6.2, 6.3
6.4 6.4 6.5
The evaluation addresses five research questions: RQ1 Does StageFrontier handle synchronization displacement better than existing rank-local stage summaries? RQ2 Can it route bottlenecks to a compact candidate stage and rank without a full profiler? RQ3 Does it remain valid under modern distributed training regimes such as gradient accumulation and FSDP/ZeRO sharding? RQ4 Is the overhead low enough for always-on deployment? RQ5 Does the routing signal translate to operational value on real workloads?
6.1
Algorithmic validation (RQ1)
The artifact CPU validation suite covers properties independent of the cluster campaign. The telescoping identity holds to floating-point roundoff (8.88 × 10−16 max error); the formal max/average bounds of Propositions 1–2 are satisfied on random and tight fixtures (0 violations); measurement-error stability holds (observed/bound ≤ 0.9998). On the sync-wait fixture (𝑛 = 120), StageFrontier recovers the upstream boundary in 100% of rows while per-stage max and average recover it in 0%; direct-exposure recovery is 100% (𝑛 = 240); and four downgrade fixtures (co-critical, role-heterogeneous, telemetry-limited, two-stage tied) all trigger their expected labels.
6.2
Hidden-rank candidate routing and baselines (RQ1/RQ2)
E3 injects 120 ms delays into one rank in five hidden-rank scenarios (data, backward, backward/comm, forward/device, forward/host) at 8 and 32 ranks (5 seeds each), plus a callback-sync pilot. Figure 3 summarizes the two headline results — compact-routing counts against baselines and the data-tail detectability transition — and Table 4 gives the exact counts. Each baseline applies one stage-attribution rule to the same [𝑁, 𝑅, 𝑆] window matrix used by StageFrontier, sharing windowing, schema validation, and tie tolerance, so the counts isolate the scoring rule. Per-stage max Í and average rank stages by their max/mean share; raw rank spread ranks by 𝑡 (max𝑟 𝑑𝑡 ,𝑟 ,𝑠 − median𝑟 𝑑𝑡 ,𝑟 ,𝑠 ), a dispersion heuristic with no stage-attribution semantics; slowest-rank breakdown reports the largest stage of the per-step slowest rank; rank-0 local total ignores all other ranks. StageFrontier routes 50/50 rows into the top-2 candidate set and 40/50 into top-1. Per-stage max ties on top-2 but misses 28 top-1 calls because downstream exposed waits dominate the raw maximum, and the same summary overcounts 𝐹𝑡 ,𝑆 by up to min(𝑅, 𝑆) (Proposition 1); mean, slowest-rank, and rank-0 summaries miss 8
top-1
top-2
candidate hit 8 ranks
32 ranks
0.5 40 / 50 / 50 detectability cutoff (≈ 0.43)
data.next_wait frontier share
count out of 50
50
40
30
20
10
0
0.4
0.3
0.2
0.1
0.0 SF
max
avg
spread
slow
r0
12
30
60
120
(b) Detectability vs. injected data-tail delay (ms)
(a) Routing counts by scoring rule (𝑛 = 50; SF = StageFrontier)
Figure 3: Headline empirical results for the hidden-rank routing matrix. (a) Routing counts across five E3 injection scenarios (𝑛=50); candidate-hit counts should be read with the candidate-set sizes in Table 4. (b) Mean data.next_wait frontier share vs. injected data-tail delay shows a detectability transition: the dotted line marks the empirical single-stage data share (≈ 0.43, at 120 ms) above which data.next_wait enters the compact 𝜏𝐶 =0.80 candidate prefix. Table 4: Routing on E3 120 ms DDP injection rows (5 scenarios × 2 rank counts × 5 seeds = 50). Candidate-hit counts are paired with average/maximum candidate-set size. StageFrontier is the only method that both exactly decomposes exposed makespan and keeps the candidate set size two on every row. Forward/device CPU-wall routing and event side evidence are separated in Table 5. Method StageFrontier Per-stage max Per-stage average Raw rank spread Slowest-rank breakdown Rank-0 local total
Exact acct.
Top-1
Top-2
Cand. hit
Avg cand.
Max cand.
yes no no no no no
40/50 22/50 20/50 40/50 20/50 20/50
50/50 50/50 40/50 40/50 40/50 40/50
50/50 50/50 40/50 50/50 46/50 40/50
2.00 2.40 2.30 2.20 2.40 2.16
2 3 3 3 3 3
data- and rank-tail cases more often. Raw rank spread ties StageFrontier on top-1 but misses 10 top-2 cases, reaches its candidate-hit count only with a larger emitted set, and still has no stage-attribution semantics under the non-identifiability example of Section 4. The headline advantage is therefore the combination of exact additive accounting, compact top-2 candidate routing, and labels that scope the interpretation. The candidate set is size two on all 50 rows (Table 14), and the candidate hit is stable for 𝜏𝐶 ∈ [0.70, 0.90] (Table 15). Lower-magnitude data tails fall below the compact-routing threshold rather than being misattributed: the mean data.next_wait share rises 0.06 → 0.43 from 12 to 120 ms at 8 ranks (Figure 3b). A profiler-enabled calibration places the cumulative-prefix crossing of 𝜏𝐶 =0.80 between the 120 and 180 ms magnitudes (0.795 → 0.823 at 8 ranks, 0.790 → 0.818 at 32), grounding the detectability threshold in measured shares. Selected 64/128-rank spot checks route communication and 180 ms data-tail injections into the top-2 in all checked seeds, while the 120 ms data row at 128 ranks (Delay/p50 ≈ 0.21) likewise falls below the threshold rather than misrouting. Forward/device injections are not claimed as a CPU-wall top-1 attribution: forward CUDA work launched on the main stream commonly becomes host-visible later in backward, so the broad-stage prefix legitimately ranks backward first. The row counts as a successful profiler routing only when the seeded forward stage stays 9
Table 5: Forward/device claim separation. CPU-wall frontier accounting supplies compact routing; optional CUDA-event side evidence supplies device support. Fault family
CPU-wall top-1
CPU-wall top-2
Event evidence
Forward/device
not claimed (0/10 E3)
10/10 E3
Forward/host
10/10 E3
10/10 E3
forward_device_supported on event-enabled E5 rows forward_host_overhead_suspected when CPU-wall is high and event time is low
Table 6: E9 selected-window profiler comparison at 32 ranks (three seeds per scenario; inner 20 of 40 captured steps scored). Top-1/top-2 are computed after reducing each trace to the same max-prefix frontier shares; artifact size, step overhead, and postprocessing are medians from no-fault selected-window rows; StageFrontier scores inline and runs no trace-postprocessing pass (shown as none). HTA consumes the PyTorch Profiler Kineto trace and so repeats its capture/runtime/storage cells. †: within run-to-run noise; use the paired E1 bound (Table 7) for continuous StageFrontier overhead. Tool StageFrontier PyTorch Profiler HTA on Kineto Nsight Systems
Pos. rows Top-1 Top-2 Cand. hit Cand. avg/max 12 12 12 12
12/12 12/12 12/12 12/12
12/12 12/12 12/12 12/12
12/12 12/12 12/12 12/12
Artifact No-fault overhead Postproc.
2.00/2 0.11 MB 2.25/3 15.81 GB 2.25/3 15.81 GB 2.00/2 1.22 GB
within noise† 36.6% 36.6% 50.3%
none 43.5 s 43.5 s 2.59 s
in the compact top-2 and the sampled event channel (𝑞 ∈ {0.05, 1}) emits forward_device_supported (Table 5). The synchronization-bearing callback rows show a magnitude boundary: 0/3 top-1 at 60 and 120 ms (top-2 3/3), then 3/3 top-1 at 180 and 240 ms; the magnitude calibration plus the A/B/A check below carry that family’s claim.
6.3
Selected-window profiler comparison (RQ2)
E9 compares StageFrontier with PyTorch Profiler, HTA, and Nsight Systems on the same fixed 32-rank DDP window definition, as a router-vs-trace tradeoff study rather than a replacement claim: the heavier tools reproduce StageFrontier’s broad-frontier ranking on a selected window, at much higher selected-window cost. Each tool is replayed on the same selected window so routing and trace costs are measured on identical work (three seeds per scenario, 180 ms hidden-rank injections, the inner 20 of 40 captured steps scored). To keep the comparison about the paper’s claimed quantity, each heavy-profiler trace is reduced to the same ordered broad-stage matrix — Kineto record_function ranges for PyTorch Profiler and HTA, host-side NVTX ranges for Nsight — and scored with the max-prefix frontier recurrence of Section 3; kernel, CUPTI, and NCCL timelines remain complementary origin/overlap evidence. The positive denominator covers four sync-bounded rows (data_tail, comm_delay, fwd_cuda_compute, callback_sync_tail) over three seeds. The fwd_cuda_compute row’s 180 ms injection is large enough that broad CPU-wall forward dominates the frontier and is recovered top-1 here, unlike the lower-magnitude 120 ms E3 forward/device rows, which are not claimed as a CPU-wall top-1 attribution (Table 5). Under the shared reducer, StageFrontier, PyTorch Profiler/HTA, and Nsight all recover the four positive broad stages top-1 and top-2 across all three seeds (Table 6), and the ratio vector agrees closely: the largest single-stage share difference from StageFrontier on any of the six broad stages (worst case over the per-seed share vectors and the four positive scenarios) is 0.039 for PyTorch/HTA and 0.024 for Nsight, below the default share tie tolerance 𝜂 𝐴 = 0.05 (Table 13), so the candidate-routing result is unchanged. StageFrontier produces this from a median 0.11 MB evidence packet, versus a 15.81 GB Kineto trace (PyTorch Profiler/HTA, 10
Table 7: E1 overhead scale; 95% CI upper bounds on throughput overhead (%). Each rank/backend/mode cell uses five paired submitted runs with 400-step windows; ≤ 0 denotes a bound at or below zero (overhead within run-to-run noise). Ranks
Gloo CPU-wall
Gloo event-inc
NCCL CPU-wall
NCCL event-inc
8 16 32 64 128
0.019 0.160 0.047 ≤0 0.107
0.004 0.043 0.023 ≤0 ≤0
0.098 0.181 0.155 0.083 0.131
≤0 ≤0 ≤0 ≤0 ≤0
raising no-fault step time 36.6% during capture) and 1.22 GB of Nsight reports (50.3%). Perfect 12/12 top-1 agreement is partly structural — each tool’s output is collapsed onto the same broad-stage matrix and scored by the same recurrence — so this tests whether each heavy trace’s stage-range evidence is faithful enough to reproduce StageFrontier’s exposed-makespan ranking, not whether the tools’ native workflows agree end to end; those native analyses (operator/kernel drill-down, temporal/idle/overlap breakdowns) remain complementary. The host-only callback_host_tail control is excluded because no tool routes a callback without a synchronization boundary into the top-2 under this reducer: the cost is visible to the traces but not exposed as group delay, so the frontier correctly leaves it unranked.
6.4
Overhead, removed-injection, and scoped checks (RQ4/RQ3)
E1 measures overhead with paired runs inside the same submitted workload and backend; the resampling unit is the paired run/window block, so the bound respects within-run dependence. Table 7 reports 95% CI upper bounds on throughput overhead through 128 ranks for Gloo and NCCL gather. Every positive upper bound is below the pre-registered 3% (CPU-wall) and 1% (event-channel) gates; the maxima are 0.181% (16-rank NCCL CPU-wall) and 0.043% (16-rank Gloo event). Across 105 no-fault rows and 315 windows all gathers completed and no row emitted a strong bottleneck label or downgraded to telemetry_limited; the one-sided 95% upper bound on the strong-label rate from 0/105 is 2.81%, a sanity check at this scale rather than a fleet-grade false-alarm budget. Scale beyond 128 ranks, window-length sensitivity, and long-run gather backpressure are left to future evaluation. Removed-injection consistency. E6 runs three A/B/A windows per seed (3 seeds, 8 ranks, 200 steps each): baseline A1, a window B with a 120 ms callback-sync injection, and a removed-injection A2 under the same seed and allocation. Median step time goes 207.81 → 294.12 → 208.02 ms and callback frontier share goes 1.75% → 41.06% → 1.75%, returning step time to within 0.21 ms of baseline (recovery ratio 0.998, well under the 8.63 ms tolerance). The callback is a stable top-2 candidate (0/3 top-1 at this magnitude), so the result reads as removed-injection consistency for a top-2 candidate, not a top-1 intervention attribution. Gradient-accumulation and sharding scope checks (RQ3). A fixed-factor gradient-accumulation check (factor four, DDP no_sync, 8 ranks, 5 seeds, ordered accumulation-indexed substages) routes data and backward top-1/top-2 on all rows; forward/device stays top-2 (co-critical with backward host time) with the event channel still emitting forward_device_supported, and ordered-vs-broad throughput ratios fall in [0.999, 1.001]. A sharding check wraps the same transformer in PyTorch FSDP FULL_SHARD and ZeroRedundancyOptimizer ZeRO-1 (8/16/32 ranks, seeds 0–2, 180 ms injections): all 90 sync-bounded positive rows route top-2 and 87/90 top-1 (the three misses are 32-rank ZeRO-1 callback/sync rows), while a host-local optimizer control without an adjacent barrier is 0/18 top-1/top-2: work visible to a rank but not
11
Table 8: Representative operational diagnoses. Frontier share is exposed-makespan share from max-prefix accounting; the claim level is the strongest evidence the follow-up established, not a throughput attribution. Case
Frontier signal
Follow-up evidence
Operator action
Claim level
Vision-A
Data-tail from random ranks (small median, large tail) fwd 44%, data 27%, callback 24%, bwd 5% Data 90% with large delta-lag fwd 76%, bwd 15%, data 5%, callback 4% fwd ≈67%, bwd ≈22%, data ≈10%
Dataloader worker-to-main IPC stall
Main-process prefetch
Consistency
pin_memory off, worker count, image logging every 10 steps Post-op CPU/numpy/I/O paths (op ablation) QAT fake-quant dominates forward (no separate profiler capture) Profiler: fake-quant op with sync, transfers, many tiny kernels
Pin memory, worker tuning, reduced logging Post-op relocation/vectorization QAT/forward overhead
Consistency
Forward/QAT overhead
Profilercorroborated routing
Vision-B Mixed-A QAT-A QAT-B
Attributionconfirmed routing Consistency
exposed as group delay is correctly left unrouted.
6.5
Operational evidence for monitoring (RQ5)
Since March 2026, StageFrontier has been enabled by default in a production NVIDIA AV training environment covering multiple model pipelines. Of five anonymized field deployments (Table 8), the two strongest were checked against ground truth: QAT-B against a PyTorch Profiler capture and Mixed-A against an operator ablation (both detailed below). The deployments span sync-wait exposure (Vision-A), direct exposure (QAT-A, QAT-B), and mixed or substage-deep cases (Vision-B, Mixed-A). Two also recorded a post-fix throughput improvement (Vision-A 230 → 340 samples/s at 8 nodes, Vision-B 63 → 85 samples/s single-node). Two cases were checked against ground truth. In QAT-B, because a high CPU-wall forward share can reflect host overhead rather than device compute, the routing call was corroborated with a short PyTorch Profiler capture that placed the cost in genuine forward device work — the quantization-aware-training fake-quant modules, whose per-element scalar synchronizations and tens of thousands of sub-50 𝜇s kernels dominate the trace. The always-on signal selected the stage and the heavy trace identified the operator-level cause (the intended router-to-profiler relationship); the suggested fusion and sync-removal optimizations were measured offline but judged too invasive to ship. In Mixed-A, the broad data ≈ 90% frontier might be read as a dataloader problem, but the ordered sub-stage breakdown showed the workers essentially idle and the cost in a GPU post-processing stage; an op-level ablation found it was almost entirely one data-transform operator, about 27.7 s on the profiled step. Disabling that operator cut it to about 1.3 s but exposed a second transform of similar magnitude behind it, so the stage cost did not drop — though the ablation still confirmed which operator the routing pointed to. Vision-B also shows how a periodic stage cost hides from the median summaries common in throughput dashboards (Table 9). The callback stage had a per-step median of about 2 ms — roughly 0.13% of the 1.526 s median step — because its cost was concentrated in a spike that recurred every ten steps and reached a 7.17 s maximum, so a median dashboard reports it as negligible. Frontier accounting sums the per-step exposed advances and assigns the callback a 24% exposed-makespan share, with the straggler summary flagging a single intermittent rank, and routes the investigator to it; a max or p95 view would reveal the magnitude but not its share of exposed step time. Configuration inspection confirmed the cause: an image-logging callback firing every ten steps.
12
Table 9: Vision-B callback stage under three views on the same field window. The median view, common in throughput dashboards, hides the periodic spike; a max/p95 view shows magnitude but not exposed-makespan share; frontier accounting reports the share and routes to it. The cause was confirmed by configuration inspection. View
Callback stage reported as
Operator verdict
Median (p50) dashboard Max / p95 view
≈ 2 ms (0.13% of the 1.526 s median step) 7.17 s spike visible, but not its exposed-makespan share 24% exposed-makespan share; single intermittent straggler rank
negligible magnitude only
StageFrontier frontier
6.6
routed to callback
Observed failure modes and negative cases
The cases above are positive routing outcomes; the complementary failure modes follow from a broad-stage, passive signal. The labeler gates (Table 13) surface most of them as conservative labels rather than confident calls, but one is a confident misroute that the contract handles only with corroboration. • Confident misroute on displaced work. When forward CUDA work becomes host-visible downstream, the broad CPU-wall frontier confidently ranks the exposed stage (backward) ahead of the origin stage (forward), yielding 0/10 top-1 in Section 6.2: a correct exposed-time call but a misleading origin, so forward/device is reported at top-2 with CUDA-event corroboration. • Unlocalized slowdowns. Host CPU contention, a scheduling stall, or a filesystem hang can inflate total step time without concentrating in any one stage; StageFrontier then reports a slow step with no confident stage, and node-list or GPU-utilization evidence is the next step. • A recurrent rank is not a node. A persistent frontier-leader rank localizes a rank, not a host; acting on it (e.g. draining a node) without rank-to-host mapping can target the wrong resource. • Threshold sensitivity and non-portable fixes. Near a dominance or tie threshold, the leading stage can flip between windows, emitted as leader-switch or tie evidence; a correctly routed bottleneck can still lack a general remedy — one field case routed correctly to a forward quantization cost with no low-overhead fix, and a data-prefetch change that recovered one workload left two others unchanged. Apart from the forward/device misroute, no field diagnosis in Section 6.5 was overturned by a later heavy trace — a consistency observation across the deployments, not a measured false-positive rate. The remaining cases downgrade to telemetry_limited, co_critical, or role_aware_needed rather than a single-stage call.
7
Related Work
Prior approaches localize distributed-training slowdowns from rich inputs: trace and wait-state tools measure wait, idle, and synchronization explicitly, while replay and causal methods infer impact from event-trace critical paths, operator graphs, or virtual-speedup experiments. StageFrontier needs neither: it infers the exposed-makespan attribution from a passive ordered vector of lumped stage durations — no event trace, operator graph, or synchronized clock — trading direct observability for an always-on signal cheap enough to leave running.
13
Framework profilers and trace analyzers. Framework profilers (PyTorch/TensorFlow Profiler, Nsight Systems [19, 23, 28]) and trace analyzers (HTA over Kineto [18]) give operator-, memory-, and CUDA-timeline resolution per trace and can attribute a stall causally by following a late rank back to the delaying event; that input is a captured trace too heavy to run continuously, so StageFrontier sits one layer below, emitting a routing packet that says which window and stage class to ask a profiler about. Instrumentation and straggler systems. Graph-replay systems (dPRO [12], Chakra [27]) build a global dataflow graph and search optimizations, whereas StageFrontier shows that ordered rank-local stage vectors alone — not graphs, wait events, or synchronized clocks — recover exact additive exposed-makespan accounting, small enough to leave on. Large-scale straggler platforms (FALCON [29], GREYHOUND [30], MegaScale [13], what-if analyses [16]) target >10 000-GPU clusters and can ingest the StageFrontier packet as a per-window signal alongside fleet state, while finer-grained Horovod/DeepSpeed and DDP/FSDP instrumentation [7, 8, 11, 15, 25] exposes communication detail below the broad contract; Plumber [14] diagnoses input-pipeline internals, whereas StageFrontier only routes whether a data tail is exposed as synchronized step time and worth pulling such evidence on. HPC wait-state and causal profiling. HPC wait-state and critical-path tools (Scalasca [9, 10], HPCToolkit [1], TAU [26], wait-state/critical-path methods [3, 4]) attribute wait time on richer typed events than StageFrontier collects, letting them separate independent co-critical paths from genuine wait; frontier accounting deliberately trades direct wait observation for an input of six floats per rank-step and a contract needing no event-tracing infrastructure, surfacing co_critical, role_aware_needed, or telemetry_limited where such a tool would split the path with side evidence. SyncPerf [2] targets lock/condvar callsites in multithreaded programs. Causal profiling (Coz [5]) estimates impact via virtual speedups and tail-at-scale [6] explains how rare component delays dominate; StageFrontier borrows the goal of linking local slowdowns to throughput but injects no virtual speedups and claims no intervention impact from passive timers. MLPerf [17] measures workload-level performance, while StageFrontier targets the layer below — which stage, rank, role, or data path to investigate when a workload deviates from its expected throughput.
8
Conclusion
Frontier accounting is a general identity: it applies to any training loop that reports an aligned ordered stage vector. We demonstrate it on homogeneous synchronous DDP transformer training through 128 ranks, with scoped FSDP FULL_SHARD and ZeRO-1 checks; broader regimes are left to future evaluation. The one thing the signal does not do, by design, is assign root cause: it accounts for exposed time exactly and routes a heavier profiler to the window, stage, and rank to examine, and a frontier advance reads as a cause only under the synchronization-wait model of Section 4, which the evidence labels flag where it does not hold. The analytic core is unconditional: frontier advances telescope to the observed exposed step time for aligned stage vectors, and per-stage maxima and averages have formal min(𝑅, 𝑆) overcounting and 𝑅 undercounting failure modes against it. The reference 𝑂 (𝑅𝑁 𝑆) window payload is small enough to run continuously and structured enough that heavier profiler collection fires only when the labels mark a window actionable — a profiler-router that decides when, where, and for which rank a heavy trace is worth its cost.
14
Table 10: Default broad stage taxonomy. Categories are intended for continuous accounting and diagnosis routing, not kernel-level attribution. Stage
Meaning
data.next_wait model.fwd_loss_cpu_wall model.backward_cpu_wall
Main-process wait for the batch consumed by this logical step. Forward pass and loss construction as exposed to the host. Backward pass and exposed distributed communication or synchronization. Callback, logging, checkpoint, and hook work around the step. Optimizer step and related host-visible work. Residual: step wall time not covered by explicit spans.
callbacks.cpu_wall optim.step_cpu_wall step.other_cpu_wall
Table 11: Ordered-stage contract checks and conservative fallback behavior. Check
Fallback if violated
Only one ordered frontier stage active per rank Common schema version, ordered stage list, and stage-order hash inside a diagnosis group All ranks in the diagnosis group present at the window boundary Residual closure and overlap error within configured thresholds Role metadata sufficient for the chosen group
Reject nested ordered spans; keep nested measurements only when declared side_channel=true. Close the current window and emit telemetry_limited; do not merge mismatched rows.
A
Emit local summaries if safe, but downgrade distributed labels to telemetry_limited. Keep frontier_accounting if the vector is usable, but suppress stronger diagnosis labels. Emit role_aware_needed rather than applying a global frontier across incompatible roles.
Stage Taxonomy and Ordered-Stage Contract
StageFrontier records a fixed list of non-overlapping trainer-stage spans on each rank using CPU wall-clock time (Table 10). The forward/loss row may carry an optional side-channel metric model.fwd_loss_ cuda_event_ms, a sampled device-stream elapsed time with a ready/missing state that is not an ordered stage and never enters the prefix vector, preserving exact exposed-makespan semantics. Í Let 𝑤 𝑡 ,𝑟 be the rank-local step wall time. The signed closure error is 𝑒 𝑡 ,𝑟 = 𝑤 𝑡 ,𝑟 − 𝑠≠other 𝑑𝑡 ,𝑟 ,𝑠 , the residual stage is 𝑑𝑡 ,𝑟 ,other = max(0, 𝑒 𝑡 ,𝑟 ), and the overlap error is 𝑜 𝑡 ,𝑟 = max(0, −𝑒 𝑡 ,𝑟 ); large positive residual means the taxonomy is missing exposed work, large overlap error means spans are nested or double-counted, and both can downgrade a diagnosis to telemetry_limited. Frontier accounting requires a common ordered boundary list within each diagnosis group: a stage may be broad but must be a contiguous, non-overlapping interval, and the instrumentation distinguishes ordered frontier stages (in the prefix vector), side-channel probes (nested but never in the prefix vector), and refined ordered schemas (substages that replace a broad parent). Table 11 lists the contract checks and conservative fallbacks. StageFrontier also records a data wait on the logical step that consumes the batch, not the loop iteration that called next(dataloader), so a step-𝑡+1 data stall is not shifted into step-𝑡 compute.
B
Full Diagnosis Label Table
Table 12 lists every label emitted by the deployed labeler, including the forward-event variants and the gradient-accumulation ambiguity label.
15
Table 12: Full diagnosis labels and downgrade triggers. Label
Axis
Meaning
Downgrade trigger
frontier_accounting
Accounting
likely_sync_wait
Model fit
Additive exposed-makespan decomposition only. Frontier, lag, and workload semantics support upstream wait-induced delay.
sync_wait_dependent
Model fit
Frontier share is high but static direct gain is low; actionability depends on the wait model.
direct_exposure
Direct gain
Raw duration, spread, and clipped static sensitivity agree with the frontier stage.
forward_device_supported
Device evidence
forward_spillover_suspected
Device evidence
forward_host_overhead _suspected
Device evidence
Forward/loss frontier evidence is accompanied by high sampled CUDA-event forward time. Forward CUDA-event time is high, but host-visible exposed cost appears later, often in backward. CPU-wall forward/loss is high while sampled CUDA-event forward time is low.
forward_event_scope _limited
Device evidence
None; this is the base claim. Weak role metadata, high closure error, or low dominance margin. Direct evidence or traces show independent productive work. Static gain small relative to frontier share. Event samples are missing, low, or scope-limited. Profiler or stream evidence places the work elsewhere. Event scope misses side-stream work or host evidence points elsewhere. Stream coverage or readiness improves.
co_critical
Ambiguity
gradient_accumulation _ambiguous
Ambiguity
role_aware_needed
Role clarity
telemetry_limited
Telemetry
Event ready ratio is low or the trainer uses streams not covered by the event markers. Multiple stages or ranks can plausibly remain bottlenecks after optimizing one stage. Accumulation microsteps were collapsed or mixed; data/backward displacement cannot be separated. Rank roles differ enough that global rank aggregation is unsafe. Residuals, overlap error, gather failures, metadata gaps, or missing probes cap confidence.
16
Side evidence separates the paths. Collect unfolded accumulationindexed substages. Role grouping becomes available. Telemetry quality is restored.
C
Labeler Default Gates
The labeler is deterministic given the stage matrix, schema metadata, optional side evidence, and threshold configuration: it validates the ordered-stage contract and schema/world membership, computes prefixes, frontier advances, shares, and the routing set, computes lag/delta-lag/tie/leader-switch evidence and clipped direct-exposure gain, applies telemetry-quality and role-aware gates, evaluates optional CUDA-event or communication side evidence, and emits labels, the routing set, the ambiguity evidence set, and downgrade reasons. Table 13 lists the default gates. The co-criticality logic uses an ambiguity set 𝐸 amb = 𝐶 𝐴 ∪ 𝐶𝐺 (top stages by frontier share and by clipped static gain): a window is sync_wait_dependent when 𝐴𝑠1 > 𝛾 𝐴, 𝐺 𝑠1 < 𝛾𝐺 , and a caller-supplied model-fit indicator 𝑊𝑠1 = 1; the same low-gain configuration with 𝑊𝑠1 = 0 is co_critical, and near-tied or high-leader-switch windows are likewise downgraded. The artifact labeler uses the safe default 𝑊𝑠 = 0. Table 13: Default labeler gates used as conservative starting points. Gate
Default
Purpose
Closure residual share
≤ 0.05
Overlap error share Missing-rank count
≤ 0.01 0
Event-ready ratio
≥ 0.8
Minimum event samples
≥5
Frontier-share dominance
𝛾 𝐴 = 0.4
Static-gain threshold
𝛾𝐺 = 0.1
Share/gain tie tolerance Leader-switch tolerance
𝜂 𝐴 = 𝜂𝐺 = 0.05 𝜂𝑄 , 𝛾switch , 𝛾elig
Candidate cumulative threshold Model-fit indicator
𝜏𝐶 = 0.80 default 𝑊𝑠 = 0
Suppress strong labels when explicit spans do not close the step. Detect nested or double-counted ordered stages. Require complete distributed evidence for distributed labels. Permit forward-event support labels only when enough sampled pairs complete. Avoid device-evidence labels from a single ready event. Require a leading exposed-makespan share for strong stage labels. Separate direct exposure from wait-dependent frontier share. Emit co-critical evidence for near ties. Count switches only between confident unique leaders. Define compact candidate routing set. Do not infer sync-wait dependence without workload or side evidence.
D
Frontier Bounds and Measurement-Error Stability
Notation matches Section 3. Proof of Proposition 1. Let 𝑢 𝑠 = arg max𝑟 𝑑𝑡 ,𝑟 ,𝑠 and regroup the stage maxima by maximizing rank: 𝑀𝑡 = Í Í Í Í 𝑟 𝑠:𝑢𝑠 =𝑟 𝑑 𝑡 ,𝑟 ,𝑠 . For each rank 𝑟, 𝑠:𝑢𝑠 =𝑟 𝑑 𝑡 ,𝑟 ,𝑠 ≤ 𝑠 𝑑 𝑡 ,𝑟 ,𝑠 ≤ 𝐹𝑡 ,𝑆 , so summing over the at most 𝑅 ranks gives 𝑀𝑡 ≤ 𝑅 𝐹𝑡 ,𝑆 ; the trivial per-stage bound gives 𝑀𝑡 ≤ 𝑆 𝐹𝑡 ,𝑆 , hence 𝑀𝑡 ≤ min(𝑅, 𝑆) 𝐹𝑡 ,𝑆 . Also Í Í 𝐹𝑡 ,𝑆 = max𝑟 𝑠 𝑑𝑡 ,𝑟 ,𝑠 ≤ 𝑠 max𝑟 𝑑𝑡 ,𝑟 ,𝑠 = 𝑀𝑡 . The ratio min(𝑅, 𝑆) is reached by assigning duration 𝐷 to each of min(𝑅, 𝑆) distinct rank-stage pairs and zero elsewhere, with no rank receiving more than one nonzero duration. □ Proof of Proposition 2. Since each rank total is at most 𝐹𝑡 ,𝑆 , the average rank total is at most 𝐹𝑡 ,𝑆 ; since the maximum rank total is at most the sum of rank totals, the average is at least 𝐹𝑡 ,𝑆 /𝑅. The lower bound is reached when one rank has total 𝐷 and all others zero. □ 17
Proposition 3 (Measurement-error stability). If every measured stage duration has absolute error at most 𝜖, then each prefix frontier has error at most 𝑠𝜖 and each frontier advance has error at most (2𝑠 − 1)𝜖. Window shares are stable when the leading-stage margin is large compared with these errors and the denominator Í 𝑡 𝐹𝑡 ,𝑆 is bounded away from zero. Proof. Each prefix sums at most 𝑠 perturbed durations, so its error is at most 𝑠𝜖, and the max of values changes by no more than the maximum perturbation, so 𝐹𝑡 ,𝑠 changes by at most 𝑠𝜖. Since 𝑎 𝑡 ,𝑠 = 𝐹𝑡 ,𝑠 − 𝐹𝑡 ,𝑠−1 , its error is at most (2𝑠 − 1)𝜖 by the triangle inequality. Normalized shares divide by the window denominator; when that is near zero the implementation reports raw advances or downgrades percentage labels. □
E
Extended Routing Results
Table 14: Full hidden-rank routing summary. E3 rows use DDP without gradient accumulation and five seeds per rank count; callback rows use a three-seed synchronization study. The daggered callback/host row is a host-only scope-boundary control with no immediate barrier. Delay/p50 normalizes by the median no-fault step p50 for the matching rank count. Scenario
Ranks
Delay
Delay/p50
Rows
Top-1 match
Top-2 routing
Cand. hit
Cand. size
Data Data Backward Backward Backward/comm Backward/comm Forward/device Forward/device Forward/host Forward/host Callback/sync Callback/host†
8 32 8 32 8 32 8 32 8 32 8 8
120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms 120 ms
0.58 0.51 0.58 0.51 0.58 0.51 0.58 0.51 0.58 0.51 0.58 0.58
5 5 5 5 5 5 5 5 5 5 3 3
5/5 5/5 5/5 5/5 5/5 5/5 0/5 0/5 5/5 5/5 0/3 0/3
5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 3/3 0/3
5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 5/5 3/3 0/3
2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0
18
Table 15: Sensitivity of the E3 StageFrontier routing candidate set to the cumulative threshold 𝜏𝐶 , recomputed from the stored stage scores for the same 50 rows as Table 4. Higher thresholds preserve candidate hit but reduce compactness.
F
𝜏𝐶
Cand. hit
Avg cand. size
Max cand. size
0.70 0.75 0.80 0.85 0.90
50/50 50/50 50/50 50/50 50/50
2.00 2.00 2.00 2.20 3.00
2 2 2 3 3
Artifact Reproducibility
The evaluation is backed by the stagefrontier-artifact repository. Validation-cluster rows use the NVIDIA PyTorch 24.12 container (PyTorch 2.6.0a0, CUDA 12.6), NCCL 2.23.4 for training, Gloo telemetry gather for the main routing matrix (Gloo and NCCL for the overhead-scale matrix), bf16 transformer runs, deterministic seeds recorded in each structured row, and the default labeler gates of Table 13. E8 additionally records the sharding wrapper, FSDP strategy, ZeRO stage, and CUDA memory counters; E9 records the selected-window tool mode, capture mode, Kineto/Nsight artifact sizes, and HTA ingestion status. Local CPU smoke tests exercise the command surface but do not regenerate paper tables; E0–E9 paper rows require GPU Slurm allocations. The artifact’s paper_outputs snapshots archive the validated structured summary files and provenance hashes for the CSV tables, and an artifact_manifest.csv maps each evaluation table to its source artifact and regeneration command (checked-in Slurm wrappers for E0–E9 and the callback synchronization study).
19
Table 16: Experiment groups referenced by the evaluation. All groups except E7 disable gradient accumulation; E9 is a selected-window profiler comparison, not a continuous deployment. Group
Configuration
Role
E0
8 ranks, no fault, 𝑞 ∈ {0, 0.05}, 600 steps
E1 E2 E3 E4
8–128 ranks, seeds 0–4, Gloo and NCCL gather, paired logger-off / CPU-wall / 𝑞=0.05 rows 8 ranks, seeds 0–2, 120 ms data, comm, and forward injections 8 and 32 ranks, seeds 0–4, 12/30/60/120 ms hidden-rank delays 8 and 32 ranks, profiler spot checks, 150/180 ms data-tail
E5
8 and 32 ranks, 𝑞 ∈ {0, 0.05, 1} CUDA-event side channel
Callback
8 ranks, seeds 0–2, 60–240 ms sync-bearing and 120 ms host-only rows
E6 E7
8 ranks, seeds 0–2, A/B/A with a 120 ms sync callback in B only 8 ranks, seeds 0–4, accumulation factor 4 with DDP no_sync
E8 E9
8/16/32 ranks, seeds 0–2, FSDP FULL_SHARD and ZeroRedundancyOptimizer ZeRO-1, 180 ms faults 32 ranks, seeds 0–2, 40-step capture (inner 20 scored), 180 ms faults
Telemetry completeness; no stray sleeps or CUDA syncs Paired-bootstrap overhead through 128 ranks Small-scale routing pilot Detectability curve; top-1/top-2 routing Separates candidate-boundary effects from data-stage attribution Forward-device vs. forward-host side evidence Sync vs. host-only callback; top-1/top-2 boundary Removed-injection consistency Gradient-accumulation ordered-stage check Sharded-data-parallel scope spot check
Scale
64/128 ranks, 120 ms comm and 120–360 ms data-tail faults
StageFrontier vs. PyTorch Profiler, HTA, and Nsight cost Routing persistence beyond 8/32 ranks
References [1] L. Adhianto, S. Banerjee, M. Fagan, M. Krentel, G. Marin, J. Mellor-Crummey, and N. R. Tallent. HPCTOOLKIT: Tools for performance analysis of optimized parallel programs. Concurrency and Computation: Practice and Experience, 22(6): 685–701, 2010. doi: 10.1002/cpe.1553. [2] M. M. U. Alam, T. Liu, G. Zeng, and A. Muzahid. Syncperf: Categorizing, detecting, and diagnosing synchronization performance bugs. In Proceedings of the Twelfth European Conference on Computer Systems, pages 298–313. ACM, 2017. doi: 10.1145/3064176.3064186. [3] D. Böhme, M. Geimer, F. Wolf, and L. Arnold. Identifying the root causes of wait states in large-scale parallel applications. In Proceedings of the 39th International Conference on Parallel Processing, pages 90–100, 2010. doi: 10.1109/ICPP.2010.18. [4] D. Böhme, B. R. de Supinski, M. Geimer, M. Schulz, and F. Wolf. Scalable critical-path based performance analysis. In Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium, 2012. [5] C. Curtsinger and E. D. Berger. Coz: Finding code that counts with causal profiling. In Proceedings of the 25th Symposium on Operating Systems Principles, pages 184–197, 2015. doi: 10.1145/2815400.2815409. [6] J. Dean and L. A. Barroso. The tail at scale. Communications of the ACM, 56(2):74–80, 2013. doi: 10.1145/2408776.2408794. [7] DeepSpeed Contributors. DeepSpeed communication logging. https://www.deepspeed.ai/tutorials/comms-logging/, 2026. Accessed 2026-05-10. [8] DeepSpeed Contributors. DeepSpeed flops profiler documentation. https://deepspeed.readthedocs.io/en/latest/flops-profiler.html, 2026. Accessed 2026-05-10. [9] M. Geimer, F. Wolf, B. J. N. Wylie, and B. Mohr. The scalasca performance toolset architecture. In International Workshop on Scalable Tools for High-End Computing, pages 51–65. Springer, 2008. doi: 10.1007/978-3-540-68564-7_5. [10] M. Geimer, F. Wolf, B. J. N. Wylie, E. Ábrahám, D. Becker, and B. Mohr. The Scalasca performance toolset architecture. Concurrency and Computation: Practice and Experience, 22(6):702–719, 2010. doi: 10.1002/cpe.1556. [11] Horovod Contributors. Horovod Timeline: Analyze performance. https://horovod.readthedocs.io/en/stable/timeline_include. html, 2026. Accessed 2026-05-10. [12] H. Hu, C. Jiang, Y. Zhong, Y. Peng, C. Wu, Y. Zhu, H. Lin, and C. Guo. dPRO: A generic performance diagnosis and optimization toolkit for expediting distributed DNN training. In Proceedings of Machine Learning and Systems, volume 4, 2022. URL https://proceedings.mlsys.org/paper_files/paper/2022/hash/b422680f3db0986ddd7f8f126baaf0fa-Abstract.html. [13] Z. Jiang, H. Lin, Y. Zhong, Q. Huang, Y. Chen, Z. Zhang, Y. Peng, X. Li, C. Xie, S. Nong, Y. Jia, S. He, H. Chen, Z. Bai,
20
Q. Hou, S. Yan, D. Zhou, Y. Sheng, Z. Jiang, H. Xu, H. Wei, Z. Zhang, P. Nie, L. Zou, S. Zhao, L. Xiang, Z. Liu, Z. Li, X. Jia, J. Ye, X. Jin, and X. Liu. Megascale: Scaling large language model training to more than 10,000 gpus. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pages 745–760. USENIX Association, 2024. URL https://www.usenix.org/conference/nsdi24/presentation/jiang-ziheng. [14] M. Kuchnik, A. Klimovic, J. Simsa, V. Smith, and G. Amvrosiadis. Plumber: Diagnosing and removing performance bottlenecks in machine learning data pipelines. In Proceedings of Machine Learning and Systems, volume 4, pages 33–51, 2022. URL https://proceedings.mlsys.org/paper_files/paper/2022/hash/d0e90e9a9310570dfa643aa3b2da6e89-Abstract.html. [15] S. Li, Y. Zhao, R. Varma, O. Salpekar, P. Noordhuis, T. Li, A. Paszke, J. Smith, B. Vaughan, P. Damania, and S. Chintala. Pytorch distributed: Experiences on accelerating data parallel training. Proceedings of the VLDB Endowment, 13(12):3005–3018, 2020. doi: 10.14778/3415478.3415530. URL https://arxiv.org/abs/2006.15704. [16] J. Lin, Z. Jiang, Z. Song, S. Zhao, M. Yu, Z. Wang, C. Wang, Z. Shi, X. Shi, W. Jia, Z. Liu, S. Wang, H. Lin, X. Liu, A. Panda, and J. Li. Understanding stragglers in large model training using what-if analysis. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pages 483–498. USENIX Association, 2025. URL https: //www.usenix.org/conference/osdi25/presentation/lin-jinkun. [17] P. Mattson, C. Cheng, C. Coleman, G. Diamos, P. Micikevicius, D. Patterson, H. Tang, G.-Y. Wei, P. Bailis, V. Bittorf, D. Brooks, D. Chen, D. Dutta, U. Gupta, K. Hazelwood, A. Hock, X. Huang, A. Ike, B. Jia, D. Kang, D. Kanter, N. Kumar, J. Liao, G. Ma, D. Narayanan, T. Oguntebi, G. Pekhimenko, L. Pentecost, V. J. Reddi, T. Robie, T. St. John, T. Tabaru, C.-J. Wu, L. Xu, M. Yamazaki, C. Young, and M. Zaharia. Mlperf training benchmark. In Proceedings of Machine Learning and Systems, volume 2, pages 336–349, 2020. URL https://arxiv.org/abs/1910.01500. [18] Meta Platforms, Inc. Holistic Trace Analysis / TraceInsight documentation. https://hta.readthedocs.io/en/latest/, 2026. Accessed 2026-05-11. [19] NVIDIA. NVIDIA Nsight Systems user guide. https://docs.nvidia.com/nsight-systems/UserGuide/index.html, 2026. Accessed 2026-05-10. [20] PyTorch Contributors. CUDA Semantics. https://docs.pytorch.org/docs/2.6/notes/cuda.html, 2026. Accessed 2026-05-30. [21] PyTorch Contributors. torch.cuda.Event documentation. https://docs.pytorch.org/docs/2.6/generated/torch.cuda.Event.html, 2026. Accessed 2026-05-30. [22] PyTorch Contributors. DistributedDataParallel documentation. https://docs.pytorch.org/docs/2.6/generated/torch.nn.parallel. DistributedDataParallel.html, 2026. Accessed 2026-05-30. [23] PyTorch Contributors. torch.profiler documentation. https://docs.pytorch.org/docs/2.6/profiler.html, 2026. Accessed 2026-05-30. [24] S. Rajbhandari, J. Rasley, O. Ruwase, and Y. He. ZeRO: Memory optimizations toward training trillion parameter models. arXiv preprint arXiv:1910.02054, 2020. URL https://arxiv.org/abs/1910.02054. [25] A. Sergeev and M. Del Balso. Horovod: Fast and easy distributed deep learning in tensorflow. arXiv preprint arXiv:1802.05799, 2018. URL https://arxiv.org/abs/1802.05799. [26] S. S. Shende and A. D. Malony. The TAU parallel performance system. International Journal of High Performance Computing Applications, 20(2):287–331, 2006. doi: 10.1177/1094342006064482. [27] S. Sridharan, T. Heo, L. Feng, Z. Wang, M. Bergeron, W. Fu, S. Zheng, B. Coutinho, S. Rashidi, C. Man, and T. Krishna. Chakra: Advancing performance benchmarking and co-design using standardized execution traces. arXiv preprint arXiv:2305.14516, 2023. doi: 10.48550/arXiv.2305.14516. URL https://arxiv.org/abs/2305.14516. [28] TensorFlow Contributors. TensorFlow Profiler: Optimize tensorflow performance. https://www.tensorflow.org/guide/profiler, 2026. Accessed 2026-05-10. [29] T. Wu, W. Wang, Y. Yu, S. Yang, W. Wu, Q. Duan, G. Yang, J. Wang, L. Qu, and L. Zhang. FALCON: Pinpointing and mitigating stragglers for large-scale hybrid-parallel training. arXiv preprint arXiv:2410.12588, 2024. doi: 10.48550/arXiv.2410.12588. URL https://arxiv.org/abs/2410.12588. [30] T. Wu, W. Wang, Y. Yu, S. Yang, W. Wu, Q. Duan, G. Yang, J. Wang, L. Qu, and L. Zhang. GREYHOUND: Hunting Fail-Slows in Hybrid-Parallel training at scale. In 2025 USENIX Annual Technical Conference (USENIX ATC 25), pages 731–747, Boston, MA, 2025. USENIX Association. URL https://www.usenix.org/conference/atc25/presentation/wu-tianyuan.
21