Conservative Aggregation Trees for Compressed Gradient Sync on Irregular Networks

Training a large model across several clusters means repeatedly summing gradients over a network whose links are wildly uneven. There are fast connections inside a machine, slower ones inside a datacenter, and thin, asymmetric links between sites. Today's compressed synchronization methods quietly force that irregular network into a fixed shape, a ring or a butterfly, and then compress every hop the same way. This proposal treats the choice of shape as a lossy graph-to-tree conversion, in the sense semantic parsers use when they squeeze a multi-parent meaning graph into a tree. Two lessons carry over from that field. The first is that you can measure the loss of a conversion offline, before training, by running a "round-trip oracle" on logged data. The second is that "conservative" conversions, which intervene only where a known structure demands it, beat "radical" uniform ones.

Concretely, we would build a planner that takes a measured network graph and a gradient-compression budget. It picks an aggregation tree, meaning a routing pattern in which each machine adds its gradient to a partial sum and forwards it toward a root. It then assigns a bit-width to each tree edge, compressing only where the link is a bottleneck. The claim is that on irregular networks this reaches a target loss faster than the best fixed-topology compressed all-reduce, and that a cheap offline fidelity score predicts which plans will converge well.

Core Claim

The strongest compressed multi-hop method in the file, DynamiQ, synchronizes over rings and butterflies. It uses shared-seed correlated rounding to cancel error across hops, and it reaches target accuracy 40.8% faster than uncompressed BF16 while keeping 99.9% of baseline accuracy. Its authors explicitly leave irregular network fabrics open. Marsit likewise fixes a ring or 2D torus and shows that re-compressing partial sums at every hop compounds error. Neither paper asks which tree to aggregate over, or which hops deserve compression at all.

We claim that tree shape and per-edge precision should be chosen jointly. The planner should use an explicit error model in which each compressed edge contributes error in proportion to the size of the partial sum crossing it. The model can be written as

$$\epsilon(P) = \sum_{e \in T} \omega(q_e)\,\frac{\|S_e\|^2}{\|S\|^2}, \qquad \tau(P) = \max_{e \in T} \frac{d\, q_e\, x_e}{b_e},$$

where $P$ is a plan made of a tree $T$ over the machines, a bit-width $q_e$ per tree edge, and a fraction $x_e$ of the gradient vector routed over edge $e$. The quantity $\omega(q)$ is the relative variance of a $q$-bit unbiased quantizer. $S_e$ is the partial gradient sum crossing $e$, $S$ is the full sum, $d$ is the number of parameters, and $b_e$ is the measured bandwidth of $e$. The error term follows from summing independent unbiased quantization noise along the tree. The time term assumes the slowest edge dominates a pipelined reduction. The planner minimizes $\tau$ subject to $\epsilon \le \epsilon^\ast$.

Two predictions follow. First, precision should vary across the tree, because edges near the root carry large partial sums. Second, full precision on fast links is nearly free, which also reduces the GPU contention that Agarwal et al. show can erase compression gains.

What the parsing literature contributes

The semantic-parsing work supplies method, not application. Copenhagen-Malmö converts semantic graphs to trees either by pruning edges or by packing them into compound labels. Before training any parser, it computes the conversion's ceiling by round-tripping gold graphs, reporting a 99.6% upper-bound F1 for packing. We import this directly. We log real gradients from a short warm-up run and push them through each candidate plan offline, comparing the result against the exact sum. We then use that "oracle fidelity" to calibrate $\epsilon^\ast$ and to rank plans, with no training.

Agic, Koller and Oepen show that cycles in semantic graphs are not random: they come from specific linguistic constructions. Trimming only those constructions, rather than overloading labels everywhere, gives over 81% labeled F1. By analogy, we compress only edges where the time model says a link is binding, rather than applying BitDP-style uniform low-bit communication.

Peking found that the traversal used to extract the tree matters: DFS kept every edge encodable, while BFS lost some systematically. This motivates treating traversal as an experimental variable. Our candidate trees include BFS from high-degree hubs, which Nyers and Jelasity found minimizes scalar aggregation error because tree cost scales with network diameter. They also include DFS-like chains, which resemble rings, and maximum-bandwidth spanning trees.

Finally, packing has a network analogue. A machine can split its vector across two parents instead of dropping a redundant fast link. That turns the tree into a DAG in which each coordinate still follows a single tree, much like re-entrancy in a semantic graph.

Research Program

We would build three components. The first is a profiler that measures pairwise bandwidth and latency on the actual cluster. The second is the planner, which enumerates candidate trees and two-parent packed variants, then solves the per-edge bit allocation. The bit-width choice is small and discrete ({1, 2, 4, 8, 16} bits) and is solved by greedy relaxation on the binding edge. The third is a runtime that executes the plan with DynamiQ's fused decompress-accumulate-recompress kernel on compressed edges and plain BF16 on the rest, so that quantizer quality is held constant across comparisons.

The analysis centers on one question: does offline oracle fidelity $\epsilon(P)$, measured on warm-up gradients, rank plans by final loss gap? If it does, plan selection becomes a pre-training computation, as tree-approximation ceilings are in parsing. If it does not, the error model is wrong and we learn where: for instance, whether correlated rounding breaks the independence assumption, or whether gradient statistics drift during training.

Baselines

The naive reference point is uncompressed BF16 all-reduce using the library's default ring or tree over the same machines. Xiao et al. report that this kind of synchronization can take up to 50% of training time, and Zhao et al. report up to 92% on bandwidth-constrained links. It sets the loss curve every method must match.

The strongest existing method is DynamiQ on its native ring and butterfly topologies. It is the only method in the file built for compressed multi-hop sums with error cancellation, and it reports 99.9% of baseline accuracy and 40.8% faster time-to-target than BF16. We run it with its own bit-allocation, on the same machines, emulated links, data and step budget as our planner. Its tuning budget matches ours: the same number of warm-up runs used to set its compression level.

We also include BitDP as the uniform ultra-low-bit reference. It reports GPT-350M perplexity of 22.74 at 2 bits against 22.17 uncompressed, and our GPT-350M-scale runs let us compare directly. Marsit serves as the 1-bit multi-hop reference. It reports 74.35% ImageNet top-1 with ResNet-50, against 74.87% at full precision and 72.74% for plain signSGD. We rerun it for the ResNet-50 setting.

Beating DynamiQ means reaching BF16's final loss within DynamiQ's own reported 0.1% accuracy tolerance, in measurably less wall-clock time, on irregular fabrics. Merely matching it there does not count, and neither does winning only on rings.

Three ablations isolate the ingredients. The first uses our optimized tree with uniform bits across edges, which isolates selective ("conservative") compression. The second uses our bit allocation on DynamiQ's ring, which isolates tree choice. The third uses a single tree versus the two-parent packed DAG, which isolates packing versus pruning of redundant links.

Why not just…?

Why not just use hierarchical all-reduce and compress only the cross-datacenter links? On a clean two-level network, our planner should essentially reproduce this, and we will report that as a sanity check rather than a win. The threat is real: if our gains appear only there, the contribution is small. The proposal's bet is on networks without a clean hierarchy, such as three or more sites with asymmetric links, or a site where one rack has a much thinner uplink. The irregular-topology experiments settle whether a planner beats the hand-built hierarchy there.

Why not just sync rarely with DiLoCo? Charles et al. show DiLoCo needs 10x to 100x less bandwidth while keeping compute utilization above 80%, which is a serious alternative. But DiLoCo still performs an all-reduce of its pseudo-gradients, on exactly the irregular links where it is deployed. Our planner applies to that outer sum. We therefore test DiLoCo with default all-reduce against DiLoCo with planned aggregation. If DiLoCo's infrequent syncs make aggregation cost negligible, we will report that as the regime where this work does not matter.

Why not just gossip instead of a tree? Nyers and Jelasity found spanning-tree aggregation beats gossip on low-diameter networks. Gossip won only under continuous churn, and even there their comparison covered scalar averages, not compressed gradients. Our fabrics are static during training, so we include one gossip baseline mainly to confirm that result carries over to gradients.

Why not just apply MXFP8 uniformly? DynamiQ reports accuracy drops of up to 2.5% for MXFP8 and similar schemes in multi-hop settings. It is subsumed by our uniform-bits ablation.

Proposed Experiments

We would pretrain GPT-style decoders at roughly 350M and 1B parameters on FineWeb-Edu, following EDiT's setup, and also on C4. We would train ResNet-50 on ImageNet to compare against Marsit's numbers. Runs use 16 to 64 GPUs grouped into emulated sites with traffic-shaped links. The topologies are a two-level hierarchy (sanity check), a three-site asymmetric wide-area network, a star of sites with one thin spoke, and random irregular graphs with log-normal bandwidths.

Metrics are wall-clock time to BF16's validation loss, final perplexity or top-1 accuracy, bytes sent per step, and GPU time spent in compression kernels. That last metric tests the contention concern raised by Agarwal et al.

The first decisive check is the rank correlation, across at least twenty plans per topology, between warm-up oracle fidelity $\epsilon(P)$ and final loss gap. A strong correlation validates plan selection before training; a weak one falsifies the error model. The second is whether the planner beats DynamiQ's time-to-target on the irregular topologies while matching its accuracy tolerance. The third is whether the packed two-parent variant beats the best single tree on networks with redundant fast links, the setting where the parsing analogy predicts that pruning costs capacity.