Error-Budgeted Parallelism Search: Choosing How to Split Each Layer and How Coarsely to Send Its Messages Together

Large models are trained across many GPUs. Every layer must be split across devices somehow: copying the layer and averaging gradients (data parallelism), cutting its weight matrices into pieces (tensor parallelism), or assigning whole groups of layers to different devices (pipeline parallelism). Automatic planners already choose a different split for each layer by predicting how long the arithmetic and the network traffic will take. A separate line of work shrinks that traffic by sending numbers at fewer bits. The two efforts are developed independently, and they interact in a specific way. The split decides which tensor crosses the network: gradients under data parallelism, partial activations under tensor parallelism, boundary activations under pipelining. Each kind of tensor tolerates rounding differently. The cheapest split for a layer can therefore change once compression is allowed, and the safe amount of compression depends on the split.

We propose a planner that makes both decisions jointly. The user gives a total error budget, meaning how much the training gradient may deviate from the full-precision gradient. The planner then picks, for every layer, a parallel split and a bit-width for every message that split creates, so that step time is as low as possible while the summed error stays within the budget. Bits per element grow only logarithmically with the inverse of the allowed rounding error. That makes "spend error where it buys the most bandwidth" a well-posed, solvable allocation problem rather than a hand-tuned heuristic. The target regime is bandwidth-starved multi-node training, where communication dominates step time.

Core Claim

Our claim is that the unit of precision in distributed training should be the communicated tensor induced by a parallel strategy, not the layer. Given that unit, a joint search over (split, message bit-width) under a global error budget finds plans that reach a target validation loss faster than two alternatives: choosing the split at full precision and compressing afterward, or compressing everything uniformly. The claim is falsifiable in a simple way. If the joint planner essentially never picks a different split than the full-precision planner, the idea collapses into "compress after planning," and we will report that.

Relation to Prior Work

Three automatic planners supply the search machinery we extend. Galvatron runs dynamic programming over layers, choosing among data, sharded-data, tensor and pipeline parallelism. It includes the cost of re-laying-out tensors between adjacent layers and a measured 1.3× slowdown when computation and communication overlap. AutoDDL uses a calibrated latency-plus-bandwidth communication model with coordinate descent. DeePa searches sample, channel and spatial splits for CNNs. All three treat message size as fixed by the model's datatype. We reuse Galvatron's layer-wise dynamic program and transformation costs and add a message bit-width and an error-budget state.

Three works compress distributed traffic, and each motivates the gap. TAH-QUANT quantizes only pipeline-boundary activations to 3–4 bits over slow links, reporting up to 4.3× end-to-end speedup, but its pipeline cuts are fixed in advance and all other traffic stays at full precision. DreamDDP staggers which layers synchronize when, but sends everything in FP16/FP32. Distributed low-precision training without mixed precision halves synchronization bandwidth with uniform FP16 under pure data parallelism.

Two works constrain our design. Stochastic layer-wise precision found that learning gradient precision was unstable, so we fix bit-widths per plan rather than learn them during training, and we keep a floor on gradient bits. Quantization Error Propagation shows that below 4 bits, errors in layer-wise post-training quantization compound through depth: perplexity on Llama-2-7B rose to 17,783 without correction. This directly threatens the additive error model below, so we test additivity explicitly and restrict the search to 3 bits or more.

The closest joint work, the FPGA mixed-dataflow mixed-precision design, couples a per-layer dataflow choice with weight bit-widths, but only for single-chip inference using offline Bayesian optimization. It has no collectives, no gradients, and no analytical cost model. Layer-parallel MGRIT training trades solver accuracy for depth parallelism, which is a different kind of precision; we do not build on it.

Research Program

The planner rests on two models: a cost model and an error model.

For the cost model, a layer $l$ under strategy $s$ emits a set of messages $k$, each with $n_{l,s,k}$ elements. Sending message $k$ at $b_k$ bits costs

$$T_{l,s}(b) = C_{l,s} + \sum_k \left(\alpha_k + \beta_k \, n_{l,s,k}\, b_k\right) + Q_{l,s}(b),$$

where:

  • $C_{l,s}$ is compute time;
  • $\alpha_k$ and $\beta_k$ are the latency and per-bit cost of the link the message uses;
  • $Q_{l,s}(b)$ is the measured cost of quantization kernels, including scale computation and packing.

The cost of re-laying-out tensors between adjacent layers is carried over from Galvatron, now also priced in bits. The overlap slowdown is kept as well.

For the error model, we profile once with a short run. We inject quantization at bit-width $b$ into each message type and record the relative deviation of the full gradient. We then fit a per-message sensitivity $\sigma_{l,s,k}$ such that the squared deviation is approximately $\sigma_{l,s,k}\, 2^{-2b_k}$. This form follows from uniform rounding, whose error variance shrinks fourfold per added bit. The planner solves

$$\min_{s_l,\, b} \sum_l T_{l,s_l}(b) + \text{transitions} \quad \text{s.t.} \quad \sum_{l,k} \sigma_{l,s_l,k}\, 2^{-2b_k} \le \varepsilon^2,$$

where $\varepsilon$ is the user's gradient error budget. Because the error term is additive, the budget can be discretized into a state of Galvatron's dynamic program. This multiplies the search by the number of budget levels rather than exponentially, which addresses the combinatorial explosion noted for extended search axes.

Concretely, we will build three things: the extended planner on top of a Galvatron-style dynamic program; a runtime with quantized collectives at 3, 4, 6, 8 and 16 bits for gradient all-reduce, tensor-parallel activation all-reduce and pipeline send/receive; and the profiler. The analysis has two parts. First, we check whether the additive error model predicts actual gradient error when many messages are compressed at once. Second, we check whether gradient-error budgets map monotonically to final validation loss.

Baselines

The naive reference point is Galvatron's plan at uniform BF16/FP16 with no compression. Every speedup is reported relative to it. This anchors what the joint planner adds over not compressing at all.

The strongest existing parallelism method is Galvatron itself. Its paper reports up to 338% higher throughput than pure-strategy baselines and a 55% speedup over DeepSpeed 3D on 8 GPUs, and notes 15% cost-estimation error if the overlap slowdown is ignored (Galvatron). We run it with the same cluster, model, data, batch size and profiling budget as our planner.

The strongest existing compression method is TAH-QUANT, which reports up to 4.3× end-to-end speedup over slow networks (TAH-QUANT). The file contains no exact final perplexity for it, so we will reproduce it. We run it in its native setting, fixed pipeline cuts on GPT-2XL and Qwen2.5-3B over 100 Mbps–1 Gbps links, and also on top of Galvatron's best plan.

The key-ingredient ablation is "plan-then-compress." It takes Galvatron's full-precision plan, freezes the splits, and then runs our same error-budgeted bit allocation over the messages that plan happens to create. This isolates the value of letting compression change the split. A second ablation is a bytes-only planner that compresses every message to the minimum bit-width with no error model. This isolates the value of the budget.

To count as beating these baselines, the joint planner must cut wall-clock time to a fixed target validation perplexity by at least 15% versus plan-then-compress. Fifteen percent matches the cost-model error scale Galvatron reports, so smaller gaps are not distinguishable from modeling noise. It must do so in at least one bandwidth regime while matching the full-precision baseline's final perplexity within run-to-run variance across three seeds.

Why not just…?

Why not just run everything in FP8 and plan as usual? Uniform low precision ignores that sensitivity differs sharply by layer and tensor. The learned allocations in stochastic layer-wise precision beat uniform bit-widths at equal budget, at 2.32% versus 3.73% error on MNIST. Uniform FP16 data parallelism also degrades at very large batches (pure FP16 training). Still, on fast intra-node links uniform 8-bit communication may capture nearly all the benefit. We include uniform-8-bit-on-Galvatron as an arm and expect to lose to it on NVLink. The claim is limited to bandwidth-starved links.

Why not just plan at full precision and compress afterward? This is the real threat, which is why it is our central ablation. It loses only if the cheapest split changes when bytes shrink. An example would be a layer where tensor parallelism's activation all-reduce, compressed to 4 bits, becomes cheaper than data parallelism's gradient all-reduce that stays at 8 bits because gradients are more sensitive. We will report how often the joint plan's splits differ from Galvatron's. If they rarely differ, we will conclude that two-stage planning suffices.

Why not just quantize pipeline activations, as TAH-QUANT does? Pipeline boundaries are a small share of total traffic when tensor or data parallelism spans slow links, and TAH-QUANT leaves gradient and tensor-parallel collectives at full precision. Our message-level breakdown of measured traffic will show what fraction of bytes it leaves untouched in each configuration.

Proposed Experiments

We train GPT-2-scale and Qwen2.5-3B models on C4, evaluating perplexity on WikiText-2, and BERT-Large on C4 with GLUE fine-tuning. This follows the TAH-QUANT and Galvatron settings. Runs use 16–32 GPUs across nodes, with inter-node bandwidth throttled to 1, 10 and 100 Gbps. The primary metric is time to target validation perplexity. Secondary metrics are steady-state throughput, final perplexity or GLUE score, and the planner's predicted versus measured step time.

The first decisive check is whether the additive error model holds. We compare predicted against measured gradient deviation when all messages are compressed at once, at 3, 4 and 8 bits. If the model under-predicts at 3 bits, as the snowball effect reported in QEP suggests it might, we raise the floor and report it.

The second check is whether gradient-error budgets translate monotonically into final-loss gaps. If they do not, the budget is the wrong control knob.

The third check, and the one that decides the proposal, is the joint-versus-plan-then-compress comparison across the three bandwidths, together with the count of changed splits. We expect the joint planner's advantage to grow as bandwidth falls and to vanish at 100 Gbps. A flat result at every bandwidth would refute the core claim.