PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordination-Free Workload Regularization for Variable-Cost Distributed Training

Tao Huang, Chen Zhu, Antonio Alonso, Daming Li, Adarsh Goura, Jaideep Ray, Yitong Zhou

arXiv:2610.21162v1cs.DCcs.LG

TL;DR

Variable-length workloads can make equal-count batches unequal in cost, leaving idle time when synchronized training waits for its slowest rank. BCL rebalances bounded rank-local windows into fixed-cardinality packs; simulations and H200 evaluations report lower modeled variability and faster execution, with memory feasibility remaining a boundary.

  • Problem

    Variable-length records can require different amounts of work despite equal record counts, creating idle time because synchronous steps wait for the slowest rank.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    BCL repartitions a bounded rank-local window into fixed-cardinality packs with balanced estimated cost, without exchanging cross-rank metadata or changing the trainer interface.

    Source: §1 · pp. 1–2

  • Results

    Across 13 NeMo-RL SFT corpora, rank-local BCL improves wall-clock step time by 1.050–1.167× over pooled MFFD; internal H200 measurements show 1.197–1.343× speedup over packed execution from one to four nodes.

    Source: §10 · p. 9

  • Takeaways & Limitations

    BCL can remove substantial variable-cost imbalance at the data-loader boundary while preserving fixed-cardinality training, but some workloads require length capping or broader coordination.

    Source: §4.1 · p. 4, §10 · p. 9, §9 · p. 9

    BCL cannot make an individually infeasible record fit, so the length policy must be established before scheduling.

    Source: §4.4 · p. 5

Abstract

from arXiv · show

Synchronous data-parallel training usually assigns every rank the same number of records, even when record costs vary by orders of magnitude. For variable-length models, this converts input variation into idle time because each step waits for its most expensive rank-local batch. We present Batch Cost Lookahead (BCL), a coordination-free data-loading policy that buffers a bounded rank-local window and repartitions it into fixed-cardinality packs with balanced estimated cost. BCL preserves the trainer's record-count contract and requires neither cross-rank metadata exchange nor runtime modification. In simulation over public workload distributions, enabling BCL reduces per-rank estimated batch-cost variability by up to 82.8%. Across 13 NeMo-RL SFT corpora on eight H200 GPUs, rank-local BCL runs 1.050 to 1.167 times faster than pooled MFFD. Compiled H200 measurements on an internal sequence workload show speedups of 1.197 to 1.343 times over packed execution from one to four nodes. We also identify a memory-feasibility boundary: a p99 cap for high-variance or OOM-prone data bounds outliers before BCL balances the rest. These results show that substantial variable-cost imbalance can be removed at the data-loader boundary, while clarifying when data preparation or broader coordination is still necessary.

1 INTRODUCTION

Variable-length records make equal-count batches unequal in cost, creating idle time when synchronized steps wait for the slowest rank. BCL uses bounded rank-local lookahead to rebalance fixed-cardinality packs without exchanging cross-rank metadata or changing the trainer interface.

1 INTRODUCTION

  • Equal record counts can still yield unequal work for variable-length sequences, and synchronous steps wait for the slowest rank, leaving faster ranks idle.Token-wise work grows with sequence length, while dense self-attention has a quadratic sequence-length component.Source: §1 · p. 1
  • BCL buffers K future fixed-cardinality batches and repartitions their KB records into K packs of B records, minimizing the maximum estimated pack cost independently on each reader.Readers exchange neither record costs nor other metadata, and the model and distributed collectives remain unchanged.Source: §1 · pp. 1–2
  • BCL preserves the fixed-record-count trainer contract and complements packing, which removes within-pack padding waste rather than balancing work across packs.The paper frames rank-local scheduling as an operating point with fixed cardinality and bounded reordering.Source: §1 · pp. 1–2
  • BCL reduces estimated per-rank batch-cost variability by up to 82.8% in simulation, improves NeMo-RL step time by 1.050–1.167× over pooled MFFD across 13 corpora, and is 1.197–1.343× faster than packed execution on one to four H200 nodes.The NeMo comparison includes both scheduling and input-path differences.Source: §1 · p. 2
  • BCL cannot split an overlong record, so length caps are set before comparing packers; every NeMo comparison arm uses the same per-corpus cap.The stated regimes include proactive p99 caps for high variability and caps enabling runs that had OOMed uncapped.Source: §1 · p. 2

2 MOTIVATION AND COST MODEL

Fixed record counts do not fix computational work, so unequal sequence lengths can create synchronization imbalance. The section distinguishes this cross-rank problem from padding waste and defines cost estimates and critical-path metrics for analyzing it.

2.1 Fixed cardinality is not fixed work

  • Equal record counts do not guarantee equal work: variable-length records can leave faster ranks idle while a synchronized step waits for its slowest rank.The paper's formal metrics use fixed B, while noting variable-record-count batches can also exhibit synchronization imbalance.Source: §2.1 · p. 2

2.2 Padding waste and synchronization imbalance

  • Packing and variable-length kernels reduce intra-batch padding waste, but BCL targets the distinct residual imbalance between packs that execute at the same synchronization boundary.The paper reports packed baselines separately rather than attributing padding removal to BCL.Source: §2.2 · p. 2

2.3 Per-record and per-pack cost

  • The cost model uses effective sequence length and linear and quadratic terms for token-wise work and dense self-attention; the cap and coefficients are workload policy.The public-distribution simulation uses capped L2 cost, and hardware step time also depends on kernels, communication, data loading, and compilation.Source: §2.3 · pp. 2–3

2.4 Critical-path metrics

  • Pack-cost variability measures temporal spread within each rank, whereas the straggler ratio measures the synchronized cross-rank penalty; only part of the latter's excess may be removable by rank-local scheduling.A straggler ratio of 1 is perfect modeled balance; 1.10 means the bottleneck pack averages about 10% more cost than the average pack.Source: §2.4 · p. 3

3 BCL DESIGN AND IMPLEMENTATION

BCL stages a bounded window from each rank-local stream and assigns its records to fixed-cardinality packs using a makespan objective. Its scheduling and streaming procedures preserve records and cardinality while avoiding cross-rank exchange.

3.1 Rank-local deployment boundary

  • Each rank-local worker stages W = KB records from its own stream, assigns them to K packs, and resumes with the next bounded window without reading or exchanging other ranks' records.The deployment contract emits each staged record once, exactly B records per pack, and limits reordering to the current window.Source: §3.1 · p. 3

3.2 Fixed-cardinality objective

  • BCL minimizes the maximum estimated cost among K packs, a cardinality-constrained makespan objective aimed at the pack that may become a synchronized straggler.The paper evaluates balance empirically rather than claiming a classical LPT approximation bound for this setting.Source: §3.2 · p. 3

3.3 Bounded scheduling procedure

  • The bounded procedure uses deterministic tie-breaking, assigns each record to the least-loaded non-full pack, then accepts heavy–light exchanges only when they strictly reduce the maximum pack cost.Exchange-based refinement preserves pack cardinality.Source: §3.3 · p. 4

3.4 Streaming integration

  • In the NeMo input path, each GPU worker schedules its own shards; the pooled MFFD reference repacks global input, so measured speedups reflect both packing and input-pipeline costs.The rank-local worker schedules KB records into K packs of exactly B without exchanging records or cost metadata.Source: §3.4 · p. 4

3.5 Cost and systems overhead

  • Larger K stages more host records, delays the first emitted pack, and permits farther reordering, but cannot make an infeasible record fit or remove shared kernel and communication work.For W = KB, sorting costs O(W log W), pack scanning costs O(WK), and storage is O(W).Source: §3.5 · p. 4

4 REDUCIBILITY AND COORDINATION BOUNDARIES

BCL’s reducibility is bounded by single-record cost and by differences in total cost across rank-local windows. Lookahead can reduce assignment-induced imbalance, but memory feasibility and information available within each rank determine when broader intervention is needed.

4.1 A single-record lower bound

  • When η ≥ 1, one record costs at least an average pack, imposing a normalized maximum of at least η even under optimal scheduling.When η ≪ 1, the window is potentially reducible by assignment, but this lower bound is not a complete attainability test: multiple large records, exact-cardinality constraints, or a small window can leave additional imbalance.Source: §4.1 · p. 4

4.2 Why bounded lookahead helps

  • Under independent costs and near-equal-cost packing, dividing a rank’s KB records into K packs brings pack costs toward that rank-window mean.The order-statistics rationale is approximate; its value depends on the cost distribution, and correlated streams or scheduling-dependent pack costs can change the suggested diminishing gains as K grows.Source: §4.2 · p. 5

4.3 The rank-divergence floor

  • Local permutations cannot lower the block’s normalized average critical path below δ because they cannot move cost between rank windows.When shards or user populations differ systematically, δ grows and the missing information is cross-rank; a global scheduler may improve balance by exchanging metadata or moving samples, at the cost of broader communication and tighter runtime coupling.Source: §4.3 · p. 5

4.4 Choosing the required intervention

  • Memory infeasibility must be addressed before scheduling: if one rendered record cannot fit available memory, no assignment can make it feasible.A p99 cap can reduce the dominant record cost; for capped windows with η < 1 whose packs fit memory, the single-record bound no longer forces a straggler, allowing BCL to reduce assignment-induced critical-path cost.Source: §4.1 · p. 4, §4.4 · p. 5

5 PUBLIC-DISTRIBUTION SCHEDULING SIMULATION

The simulation tests whether rank-local lookahead balances modeled pack costs on public length distributions. BCL reduces modeled variability and straggler excess across the retained distributions, while length caps bound long tails.

5.1 Question and public inputs

  • The six checked-in arrays contain 165,011 token lengths derived from public datasets, with no source text retained.The arrays’ dataset identifiers, rendering rules, sample counts, and checksums are retained with the experiment; Table 2 reports uncapped length statistics.Source: §5.1 · pp. 5–6, Table 2 · p. 6

5.2 Paired simulation design

  • The paired simulation reuses identical sampled streams across eight ranks for 1,000 steps at B=128, measuring modeled balance rather than GPU step time.The cost model is quadratic in capped length.Source: §5.1 · p. 5, §5.2 · p. 6
  • BCL uses K=32 with cardinality-constrained LPT initialization and two refinement rounds; the arrival-order control uses K=1.The final eight steps use a smaller eight-pack window because 1,000 is not divisible by 32.Source: §5.2 · p. 6

5.3 Results

  • 81.4–82.8%: BCL reduced pack-cost variability on every retained distribution; modeled straggler ratio fell from 1.050–1.345 to 1.009–1.066, removing 81.0–83.9% of modeled straggler excess.Table 3 reports the paired simulation result.Source: §5.3 · p. 6, Table 3 · p. 6
  • The 1,024-token cap limits modeled costs for CodeParrot and OpenWebMath’s long uncapped tails, after which BCL reduces remaining assignment variation.UltraChat starts closer to balance and has a smaller decrease in straggler-ratio points despite a similar proportional reduction in excess.Source: §5.3 · p. 6

6 NEMO-RL STREAMING EVALUATION

Across 13 NeMo-RL SFT corpora, rank-local BCL is faster than pooled MFFD, though that comparison includes both packing and input-path costs. The evaluation also compares per-rank input paths and applies the same per-corpus p99 cap across arms.

6.1 Setup and controls

  • All 13 public corpora use the same per-corpus p99 length cap in every arm, with overlength truncation shared across arms.The study fine-tunes Llama-3.2-1B using NeMo-RL SFT on one eight-H200 node.Source: §6.1 · pp. 6–7
  • Each worker schedules its own records with K=32 BCL lookahead, without documents or scheduling metadata passing between ranks or through the driver.Both per-rank arms use the same model, loss, optimizer, global batch size, FSDP2 path, and train microbatch size.Source: §6.1 · p. 7

6.2 Measured step time

  • +5.0% to +16.7%: rank-local BCL speedup over pooled MFFD across all 13 corpora, comparing complete input paths rather than packing algorithms alone.The measured interval between consecutive batch fetches covers input and training in both paths.Source: §6.2 · p. 7
  • The K=32 versus default-packing comparison covers 11 corpora; K=1 was not rerun on CodeParrot or OpenWebMath at B=8 after earlier oversized-row OOMs.The pooled MFFD reference is from an earlier campaign, whereas the default path was rerun in the current campaign.Source: §6.2 · p. 7, Table 4 · p. 7
  • +2.8% to +7.5%: per-rank input was faster than driver-merged input on 12 corpora, and +0.2% on Alpaca; default-path reruns differed by at most 1.5%.The rerun difference serves as a check on node drift.Source: §6.2 · p. 7

7 MULTI-NODE H200 EVALUATION

The multi-node evaluation combines a length-only scheduler probe, compiled H200 measurements, memory telemetry, and calibrated replays. BCL improves measured step time across tested topologies, while the replays and workload boundary qualify where rank-local balancing can help.

7.1 Workload and reporting boundary

  • The full characterization covers 7,187 shards and 320,137,728 records, with mean capped length 215.6 tokens and 10.44% of records at the cap.The 16-shard sample contains 327,680 records, with mean length 213.08 and 10.29% at the cap.Source: §7.1 · p. 7

7.2 Length-sample scheduler probe

  • Approximately 82% of straggler excess was removed at both eight and sixteen ranks when lookahead increased from K = 1 to K = 32; K = 64 added a smaller reduction.The probe schedules measured capped lengths, not GPU step times.Source: §7.2 · p. 7, Table 6 · p. 7

7.3 Compiled H200 setup

  • The compiled comparison uses BCL with K = 32 and per-rank batch size 384 against the same packed execution path with BCL disabled; global batch size rises from 3,072 to 12,288 records across one to four nodes.Reported values are post-warm-up seconds per step aggregated across repeated runs.Source: §7.3 · pp. 7–8

7.4 Compiled step-time scaling

  • 16.45%, 19.51%, and 25.52% lower step time at one, two, and four nodes, respectively, correspond to 1.197×, 1.242×, and 1.343× speedups over packed execution.Mean AUC differed from the reference by 0.07% on average, with no observed loss in that aggregate metric; BCL reorders only within bounded rank-local windows.Source: Table 7 · p. 8, §7.4 · p. 8

7.5 Peak-memory evidence

  • At B = 384, busiest-rank peak memory was 124.9 ± 4.2 GiB with BCL versus 138.7 ± 0.8 GiB for packed execution, approximately 9.9% lower.Source: §7.5 · p. 8

7.6 Calibrated sensitivity analysis

  • In calibrated replays, the modeled straggler ratio at B = 384 reached 1.027 at K = 32, with a smaller change at K = 64; larger packs moved closer to the calibrated global assignment target.From K = 32 and B = 384, increasing either parameter added little; these percentages measure proximity to a modeled target, not measured H200 speedup.Source: §7.6 · p. 8, Table 8 · p. 8

8 RELATED WORK

Related work addresses workload variation through batching, packing, scheduling, and coordination. BCL differs by retaining the existing parallel plan and exact record cardinality while making rank-local bounded-window assignments.

Batching, packing, and padding elimination

  • Token-budget or length-aware batching can reduce variation in padding or token work but may vary record cardinality, while packing and variable-length kernels remove padding work within a pack.BCL is complementary: it preserves record cardinality and changes which records share packs at a synchronization barrier.Source: §8 · pp. 8–9

Variable-length distributed training

  • Hydraulis, WLB-LLM, and DynaPipe alter parallelism, microbatch structure, or cross-worker assignment, whereas BCL keeps the existing parallel plan and collectives.BCL exposes a rank-local data-loader option with exact record cardinality.Source: §8 · p. 9

Scheduling foundations and recent approaches

  • BCL uses classical longest-processing-time initialization rather than introducing a new scheduling heuristic; its systems contribution is bounded streaming deployment and a coordination boundary.Related systems use global coordination for some workload skews, and substantially different rank-window totals may require coordination.Source: §8 · p. 9

9 DEPLOYMENT BOUNDARIES

Deployment begins with memory-feasible records and a measured choice of cap, batch size, and lookahead. BCL’s reordering and rank-local scope also impose boundaries on workload ordering, quality evidence, and restart behavior.

9 DEPLOYMENT BOUNDARIES

  • Render and tokenize records as training will consume them, then choose a length cap and batch size that fit in memory before scheduling.Raw rendered-length CV ≥2 was used as a heuristic for proactive p99 capping, but lower-CV corpora also OOMed uncapped; CV is not a feasibility test.Source: §9 · p. 9
  • The NeMo comparison holds p99 caps fixed and does not evaluate their effect on training quality.Source: §9 · p. 9
  • Workloads with ordering constraints must define legal permutations before BCL; exact mid-stream restart would need to restore reader positions, staged packs, shuffle state, and the per-rank reader merge.The current NeMo experiment does not test exact restart or held-out quality under the reordering.Source: §9 · p. 9

10 CONCLUSION

The conclusion frames BCL as rank-local fixed-cardinality balancing for unequal work, with measured gains and explicit workload boundaries. It is most useful when records fit and rank windows have similar total costs.

10 CONCLUSION

  • BCL groups bounded rank-local windows into balanced fixed-cardinality packs without exchanging cost metadata or changing the model and collectives.This addresses unequal work despite equal record counts.Source: §10 · p. 9
  • Across six public length distributions, modeled pack-cost variability fell 81.4–82.8%; across 13 NeMo-RL SFT corpora, BCL was 1.050–1.167× faster than pooled MFFD, including input-path differences.On the internal H200 workload, compiled measurements showed 1.197–1.343× speedup from one to four nodes.Source: §10 · p. 9
  • BCL is most useful when records fit and reader windows have similar total costs; outliers need capping or a representation change, while persistently heavier windows call for resharding or coordination.Source: §10 · p. 9

Related papers

Loading 2610.21162v1…