When computers train a shared model by exchanging updates with a few neighbors, with no central server (decentralized learning), the network link is usually the slowest part. The standard fix is to send only the few largest entries of each update. That fix has a hidden cost. Every value sent must carry its position in the model, and positions are expensive. For a 10M-parameter model an absolute position takes 24 bits, while the value itself may be quantized to 4 bits, so the positions are six times larger than the data (Time-Correlated Sparsification). In server-based federated learning, positions have been measured at 89–94% of upstream traffic (SmartIdx). The best server-side remedy is to have the server broadcast a shared mask that everyone already knows, so those positions cost nothing (Time-Correlated Sparsification). Peer-to-peer networks have no server to do this broadcast.
This proposal makes one observation and builds on it. In compressed gossip, every neighbor of node $i$ already sees the full history of what node $i$ has sent. Any deterministic function of that history is therefore information the sender and all its receivers share for free. We let each sender's mask be predicted from its own past messages. Each neighbor recomputes that prediction locally, so most transmitted values need no index at all. A small coded "exploration" set lets new important coordinates enter. No node ever has to agree with the whole network.
Core Claim
Agreement on which coordinates are being sent does not need to be global. It only has to hold per sender and its receivers, and the sender's own message history already supplies it. We claim the following. Under strong non-IID data, sender-predicted masks with error feedback cut total bits-to-target-accuracy below three alternatives at equal accuracy: Top-K with entropy-coded indices, seeded random sparsification, and dense low-bit quantization. They should also keep the convergence quality of magnitude-aware selection.
The non-IID point is the sharpest difference from the closest prior work. TCS's global mask was evaluated only on IID data, and the authors note that client drift destabilizes it. A per-sender mask never has to fit other nodes' data, so drift on node $j$ cannot corrupt node $i$'s prediction.
Concretely, node $i$ keeps a public accumulator $a_i^t = \beta a_i^{t-1} + |m_i^{t-1}|$. Here $m_i^{t-1}$ is the sparse, quantized message $i$ sent last round, and $\beta \in [0,1)$ is a decay factor. Every neighbor maintains an identical copy. The predicted set $S_i^t$ is the top-$k$ coordinates of $a_i^t$. The node also sends an exploration set $E_i^t$: the top-$e$ entries of its error-compensated update outside $S_i^t$, with Elias-gamma-coded indices. The bits per round per edge are
$$ B_i^t = k\,b + e\,(b + \bar{\ell}) + h, $$
where $b$ is the value bit-width, $\bar{\ell}$ is the mean coded index length, and $h$ is a 32-bit hash of $S_i^t$ used to detect when a neighbor's copy has drifted out of sync. The intended operating point has $e \ll k$. At that point the cost per value approaches $b$, compared with $b + \bar{\ell}$ for coded Top-K.
Research Program
The method sits on top of difference-compressed gossip. Communication Compression for Decentralized Training shows why nodes must exchange compressed differences against a shared public copy rather than compressed parameters: naive compression accumulates error and diverges. That same public copy is what makes our prediction free. We reuse that design, and the error-feedback buffers of JWINS and CocktailSGD, unchanged. The new component is the mask predictor and its exploration budget.
The program has three parts.
Build. We implement the predictor in decentralizepy. This includes desynchronization recovery: when the hash mismatches, the receiver requests a one-time dense resync of the accumulator. We also handle node joins and dropped packets.
Analyze. We measure how stable the predicted set really is. Specifically, we track the fraction of each node's true Top-K that falls inside $S_i^t$, as a function of $\beta$, the local step count, and the Dirichlet heterogeneity parameter. That fraction determines how large $e$ must be. If it collapses under heterogeneity, the idea fails, and this measurement shows it early. We also adapt $e$ online from the observed miss rate.
Prove. Because $S_i^t$ is a biased, history-dependent selection, unbiased-compressor analyses do not apply. We aim for a convergence bound in the contractive-compressor style used with gradient tracking (DAMSCo / DaSHCo). The contraction constant would depend on the measured coverage of the true Top-K.
Baselines
The naive reference point is uncompressed decentralized SGD on the same topology. It defines the target accuracy and the wall-clock ceiling.
The strongest existing method on this exact question is JWINS. It is peer-to-peer, magnitude-aware (it ranks entries after a wavelet transform), uses error accumulation, and already compresses its indices with Elias gamma. Its index cost is therefore the most aggressive explicit-index competitor available. It reports a 62% to 64% traffic reduction on CIFAR-10 while staying within 3% of full-sharing accuracy, and up to 4x faster wall-clock time to target accuracy than CHOCO-SGD. We will also run a version of JWINS without the wavelet transform. That variant, spatial Top-K with Elias gamma and error feedback, isolates the index question from the transform question.
The index-free competitor is seeded random sparsification as in SAPS-PSGD, which reports 81.42% with ResNet-20 on 32 workers. We run it with error feedback, without its central tracker, so it is a fair comparison in a fully decentralized setting.
We also port CocktailSGD to gossip. It combines a seeded random subset with Top-K inside that subset and quantization. Its residual sub-indices are the closest analogue to our exploration set.
The dense-quantization reference is DCD-PSGD at 8 and 4 bits.
Every method runs on the same graphs, data partitions, model, local-step count, and value bit-width. Each gets the same hyperparameter search budget: 20 trials over its own compression knobs, selected on bits-to-target. Beating the field means two things. First, reaching JWINS's final accuracy (within 0.5 points) with fewer total transmitted bits than its 62–64% reduction implies. Second, being no slower in wall-clock time to target at 100 Mbps.
Two ablations isolate the key ingredient. The first replaces $S_i^t$ with a random set of the same size, which tests whether prediction matters beyond index-freeness. The second sets $k=0$, so everything is sent as coded exploration. That reduces the method to coded Top-K and shows how much of the gain the prediction alone buys.
Why not just…?
Why not just use seeded random sparsification, which already costs zero index bits? This is the most direct competitor, because it removes indices completely. Understanding Top-k Sparsification gives the reason to expect it to lose: gradient entries are bell-shaped with information concentrated in the tails, and Top-K's error factor $(1-k/d)^2$ beats random selection's $(1-k/d)$. JWINS likewise reports higher cumulative reconstruction error for random sampling. Error feedback could narrow this gap, however, so we treat it as an open threat. The random-$S$ ablation and the SAPS-with-feedback baseline settle it on bits-to-target.
Why not just entropy-code the Top-K indices, as JWINS does? At 1% density the gaps between selected indices average around 100. Elias gamma then spends roughly 13 bits per index, still about three times a 4-bit value. Layerwise Sparse Coding also shows that relative-index codes degrade at very high sparsity and need sequential decoding. If temporal coverage turns out to be low, our method collapses to exactly this baseline, which is the $k=0$ ablation, so the measurement is decisive either way.
Why not just quantize densely and skip sparsity? Dense quantization carries no index metadata, but in gossip it hits a wall. DCD-PSGD converged much more slowly at 4 bits and ECD-PSGD diverged (Communication Compression for Decentralized Training). CocktailSGD reports a 10–30x ceiling for either technique used alone. Our target is above 100x, where dense quantization cannot reach.
Why not just run TCS with a gossip-estimated global mask? The required consensus would cost extra rounds. TCS itself flags non-IID drift as destabilizing its global mask. Per-sender prediction needs no consensus, and the experiments sweep heterogeneity precisely to show whether that difference matters.
Proposed Experiments
The main testbed is CIFAR-10 with ResNet-18 and ResNet-20 under Dirichlet non-IID partitions. We use 16 to 64 nodes on ring, torus, and random 4-regular graphs, with simulated links of 100 Mbps and 1 Gbps at 20 ms latency, matching the setup of the DCD-PSGD study. FEMNIST and Shakespeare, both used by JWINS, add natural non-IID partitions. NanoGPT on Tiny-Shakespeare tests transformers; there, DaSHCo reports a validation loss of 1.62–1.64. We report total bits per node to target accuracy, final accuracy, wall-clock time, and the fraction of each message spent on metadata.
Three checks decide the proposal.
Coverage under heterogeneity. If the predicted set covers less than about half of the true Top-K once the Dirichlet parameter drops to 0.1, the core premise fails.
Bits-to-target against coded Top-K. At matched accuracy, the method must spend at least 2x fewer bits than JWINS-style coded Top-K. Otherwise the added complexity is not worth it.
Robustness to packet loss. At 1% packet loss, the hash-triggered resyncs must cost under 5% of total traffic. Otherwise the shared-history assumption is too fragile for real peer-to-peer links.
References
- Time-Correlated Sparsification for Communication-Efficient Federated Learning
- SmartIdx: Reducing Communication Cost in Federated Learning by Exploiting the CNNs Structures
- Communication Compression for Decentralized Training
- Get More for Less in Decentralized Learning Systems
- CocktailSGD: Fine-tuning Foundation Models over 500Mbps Networks
- Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization
- Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection
- Understanding Top-k Sparsification in Distributed Deep Learning
- Layerwise Sparse Coding for Pruned Deep Neural Networks with Extreme Compression Ratio