Distributed training sends gradients between machines after every step. When the network is slow, this communication dominates training time, so a natural fix is to compress gradients into a few levels. The simplest version is the sign bit. Better versions use multi-threshold quantization: several cut points, with a "near zero" bucket and denser levels where gradients actually concentrate. The catch is systemic. Low-bit codes from different machines cannot simply be added together inside the standard ring all-reduce, the collective operation that sums gradients across machines by passing chunks around a ring so each machine sends only about twice the gradient size regardless of cluster size. Methods therefore fall back to all-gather, where every machine receives every other machine's code. That costs traffic and buffer memory that grow linearly with the number of workers, and it is part of why compression so rarely pays off in practice.
This note proposes multi-threshold codes designed to be added. Every worker quantizes onto the same shared grid of levels, and those levels are small integer multiples of one scale. Partial sums of codes then remain exact integers that need only a few more bits as they travel around the ring. The reduction can run as an ordinary integer ring all-reduce, even through the library's native 8-bit integer sum when the cluster is small enough. The summed result is re-quantized to two bits before it is broadcast back. The claim is that this keeps the accuracy benefits of non-uniform, distribution-aware thresholds while restoring ring scaling, which is the property all-gather-based schemes give up.
Core Claim
Three existing systems frame the problem. BitDP quantizes large language model (LLM) gradients into ternary $\{-1,0,1\}$ codes using analytically derived thresholds. It reports that native low-bit all-reduce overflows on accelerators, so it replaces all-reduce with all-gather plus local decoding, and its buffer memory grows linearly in the worker count $K$. NUQSGD uses logarithmically spaced, unbiased levels that are dense near zero, but it explicitly restricts itself to all-to-all reduction and leaves ring topologies open. On the Utility of Gradient Compression shows why this matters. Compression gave end-to-end speedups in only 6 of 200+ configurations, partly because compressed formats cannot use ring all-reduce. Those three papers motivate this proposal.
The proposal's starting observation is that the summing problem comes from the encoding, not from multi-threshold quantization itself. If worker $k$ maps each gradient coordinate to $q_k = s \cdot m_k$, where $s$ is a scale shared by all workers in a bucket and $m_k$ is an integer drawn from a small set $\mathcal{L}$, then the sum is exactly $s \sum_k m_k$. Here $\mathcal{L}$ is chosen so that its spacing is non-uniform, for example $\{0, \pm1, \pm2, \pm4\}$. After $j$ ring hops, the partial sum lies in $[-jL, jL]$, where $L = \max |\mathcal{L}|$. It therefore needs $\lceil \log_2(2jL+1) \rceil$ bits, and overflow is avoided by design.
Per-worker data received is then roughly the following, where $n$ is the gradient length, $\bar w$ is the average integer width used during the reduce-scatter phase, and $b$ is the width of the re-quantized code broadcast in the all-gather phase:
$$ B_{\text{ring}} \approx \tfrac{K-1}{K}\, n\,(\bar w + b), \qquad B_{\text{gather}} \approx (K-1)\, n\, b_{\text{in}}, $$
$B_{\text{gather}}$ is the all-gather cost when each worker sends a $b_{\text{in}}$-bit code. The ring cost is essentially flat in $K$, apart from the logarithmic growth of $\bar w$. The gather cost grows linearly. With $b_{\text{in}} = 2$, $b = 2$ and $\bar w \approx 8$, the two cross over near $K \approx 5$. Beyond that point, the ring version should transfer fewer bytes and hold an $O(1)$ buffer instead of an $O(K)$ one.
Research Program
The method has four pieces.
The first is choosing the integer level set, or lattice. Uniform ternary is the special case BitDP uses. The aim is to find the integer level sets of small magnitude $L$ that best approximate the variance-optimal non-uniform levels. We will fit them per layer, using the same expected-variance objective that Adaptive Gradient Quantization for Data-Parallel SGD minimizes with ALQ, but now constrained to integer ratios. ALQ supplies the adaptation method here. Its finding that gradient statistics shift sharply at learning-rate milestones is why the lattice and thresholds are re-fit online rather than fixed analytically.
The second is agreeing on a shared scale. Additivity requires every worker to use the same scale $s$ per bucket. We will obtain it with a tiny all-reduce, a max or root-mean-square over local bucket norms, carrying one 16-bit value per bucket of roughly a thousand coordinates. Encoding uses stochastic rounding onto the shared lattice, which keeps the quantizer unbiased in the way NUQSGD's is. The pseudo-random generation is fused into the encode kernel.
The third is the reduction itself, in two variants. The simple variant runs the stock NCCL all-reduce on 8-bit integers whenever $KL \le 127$; this requires no custom collective. The full variant is a custom ring in which reduce-scatter widens from 4 to 16 bits as partial sums grow. The shard owner then re-quantizes the averaged gradient to a 2-bit code with error feedback, meaning the rounding residual is stored and added back at the next step, and all-gathers that code.
The fourth is controlling the overlap paradox. Agarwal et al. show that encoding work competes with backpropagation for the GPU. For that reason, encode, scale agreement and decode will be single fused kernels. We will report encode time against the available communication slack per layer, not only total throughput.
The analysis side has two parts. First, we will derive the variance of the two-stage scheme, which combines per-worker stochastic lattice rounding with a final requantization under error feedback, and compare it with NUQSGD's bound. Second, we will measure how much accuracy is lost by restricting levels to an integer lattice instead of free log spacing.
Baselines
The naive reference point is uncompressed synchronous training with native ring all-reduce in BF16, and also in FP32 to match prior reports. Agarwal et al. find this is usually the winner on fast fabrics, so any claim must be checked against it at every bandwidth tested. Beating it means higher end-to-end tokens or images per second at equal final quality.
The strongest existing method is BitDP-2bit, ternary codes with all-gather and two-stream synchronization. It is the closest system to this proposal and reports the most aggressive gains in the file. On GPT-13B, BitDP-1bit reports a 5.15x speedup on InfiniBand and 7.47x on Ethernet over FP32. On GPT-350M, BitDP-2bit reaches validation perplexity 22.74 against 22.17 for FP32 (BitDP). We will reimplement it with the same buckets, the same data (OpenWebText as in BitDP, plus a FineWeb run via FineWeb), the same token budget, and the same learning-rate schedule. Our method beats it if it matches BitDP-2bit's perplexity to within 0.1 at $K \le 16$ and is strictly faster, with lower peak communication buffer memory, at $K \ge 32$. If BitDP stays faster at large $K$, the ring argument is wrong.
For the vision setting, the accuracy baselines are ALQ and QSGDinf on ResNet-18 ImageNet. Faghri et al. report 3-bit ALQ at 67.72% top-1, QSGDinf at 66.35%, and full precision at 68.93%. NUQSGD is run on the same setup in all-to-all mode, since that is what its authors support.
Two ablations isolate the key ingredient. The first is the same integer lattice with per-worker scales, which forces an all-gather. This separates the gain from additivity from the gain from the levels. The second is uniform ternary on the shared scale through the ring. This separates the value of non-uniform levels from the value of ring compatibility.
Why not just…?
Why not just all-reduce in BF16 or FP8, which NCCL supports natively? This is the most serious threat on fast fabrics. It gives 2–4x compression over FP32 with essentially no encoding cost, and Agarwal et al. show that low overhead is what usually decides the outcome. Our int8 ring variant transmits about the same bytes as FP8 during reduce-scatter. The proposal's advantage has to come from the 2-bit all-gather phase and from unbiased, distribution-matched rounding. The experiments therefore include an FP8 ring all-reduce baseline at every bandwidth. If FP8 matches our throughput and quality on Ethernet, the honest conclusion is that only the variable-width version adds value, and we will report that.
Why not just keep BitDP's all-gather, since clusters are often small? Below roughly eight workers, all-gather of 2-bit codes is competitive, and the crossover equation above says so. The case for the proposal rests entirely on scaling. The decisive run is therefore a sweep of $K$ from 8 to 128 measuring bytes received, buffer memory and step time. If the crossover does not appear where the equation predicts, the proposal fails.
Why not just use low-rank compression such as PowerSGD, which already works with all-reduce? Agarwal et al. find PowerSGD was the method behind the few speedups they observed, so it is a real competitor. They also report about 45 ms of encoding overhead for ResNet-50, which exceeded the communication slack at 10 Gbps. We will include rank-4 PowerSGD under the same overlap measurement. The expectation is that a fused lattice encoder costs a small fraction of that time. This is a prediction to test, not a reported result.
Proposed Experiments
The LLM study trains GPT-350M and GPT-2.7B, the configurations BitDP used, on OpenWebText and FineWeb. Runs use 8, 16, 32, 64 and 128 GPUs, over InfiniBand and over commodity Ethernet. We report validation perplexity, tokens per second, bytes per step, peak communication buffer memory, and per-layer encode time against communication slack. The vision study runs ResNet-18 on ImageNet and ResNet-110 on CIFAR-10, reporting top-1 accuracy against the ALQ, QSGDinf and NUQSGD figures above.
Four checks decide whether the idea works. The bytes-received and buffer-memory curves must stay flat in $K$ for our method while BitDP's grow linearly. The shared-lattice codes must cost at most 0.3 perplexity relative to free non-uniform levels in the per-worker-scale ablation, which shows that integer spacing does not give up NUQSGD-style accuracy. The method must deliver a net speedup over both the BF16 and FP8 ring all-reduce on Ethernet at $K \ge 32$. And with fused kernels, encode time must stay inside the communication slack, the specific failure Agarwal et al. identified. If the third check fails on InfiniBand but passes on Ethernet, that is an acceptable and informative scope result. If it fails on both, the integer-lattice idea does not earn its complexity.