Communication Compression via Shared Randomness

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 116 papers22 conceptsfrozen 2026-10-04

In distributed machine learning, the primary bottleneck is often not computation, but communication. As models grow to billions of parameters, transmitting gradients or weight updates between a client and a server becomes, as Xiao Yan and Xinyan Dai describe it in Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning, like trying to push a grand piano through a garden hose.

A growing body of research suggests a radical solution: instead of trying to squeeze the piano through the hose, the sender and receiver should both own an identical, infinite warehouse of pianos. To communicate, the sender simply points to the specific piano they want. This "warehouse" is built using shared randomness.

The Virtual Codebook

The core intuition behind this research direction is the use of synchronized Pseudo-Random Number Generators (PRNGs). If two parties agree on a single integer—a random seed—they can locally generate the exact same sequence of "random" numbers.

In the context of compression, this sequence acts as a virtual codebook. Rather than transmitting a high-dimensional vector $v$, the sender searches through a locally generated set of candidate vectors until they find one that closely approximates $v$. They then transmit only the index of that candidate. Because the receiver has the same seed, they can reconstruct the identical vector using that index.

This mechanism effectively decouples the communication cost from the dimensionality of the data. As Abhin Shah and Johannes Ballé demonstrate in Optimal Compression of Locally Differentially Private Mechanisms, shared randomness allows a sender to transmit a selected candidate index rather than the full data vector, bypassing the traditional "trilemma" of privacy, utility, and communication cost.

Getting Bits Back from Distributions

The idea of shared randomness is taken a step further in Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters. Here, Marton Havasi and José Miguel Hernández-Lobato introduce MIRACLE, which shifts the focus from encoding deterministic weights to encoding a sample from a variational distribution.

By using the "bits-back" argument, they show that if the sender and receiver share a source of randomness, the cost of communicating a sample can be significantly reduced. This approach treats the random generator as an algorithmic lookup table, allowing for compression rates as high as 1110x on standard architectures.

Similarly, Berivan Isik and Deniz Gunduz propose the KLMS framework in Adaptive Compression in Federated Learning via Side Information. They exploit "side information"—the fact that the server already knows the global model distribution—to generate candidate updates. By sending just the index of a shared random sample, they achieve a 2,650x overall compression rate without sacrificing accuracy.

Scaling to Billion Parameter Models

The most striking evidence of this technique's power is its application to Large Language Models (LLMs). In Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytes, Zhen Qin and Daoyuan Chen show that full-parameter tuning of billion-parameter models can be done with updates smaller than 18KB.

They achieve this by compressing updates into a small set of seed indices and corresponding scalar gradients. Because the seeds generate the high-dimensional basis for the update locally on both sides, the communication overhead becomes independent of the total number of model parameters.

Reconstructing Sparsity and Implicit Representations

Shared randomness also solves the "indexing problem" in sparse communication. Normally, if you only want to send the top 1% of gradient values, you also have to send a "map" of where those values belong in the original vector.

In CocktailSGD: Fine-tuning Foundation Models over 500Mbps Networks, Jue Wang and Beidi Chen use synchronized seeds to reconstruct the positions of sparse updates. The server and client use the same seed to determine which indices to update, meaning only the values themselves need to be transmitted.

This concept extends to Implicit Neural Representations (INRs) as well. Dhananjaya Jayasundara and Vishal M. Patel present SINR in SINR: Sparsity Driven Compressed Implicit Neural Representations, where they use a shared seed to generate a high-dimensional random sensing matrix. This allows the encoder and decoder to synchronize their basis sets using just a single integer, eliminating the need to transmit heavy dictionaries for sparse reconstruction.

Why It Works: The Information Theory Perspective

The success of these methods rests on a fundamental shift in how we view model updates. Instead of treating an update as a unique point in a high-dimensional space that must be described perfectly, these researchers treat it as a selection from a shared, pre-existing distribution.

As Maximilian Egger and Rawad Bitar argue in Bi-Directional Communication-Efficient Stochastic FL via Remote Source Generation, by sharing a common random seed to generate a codebook of potential updates, the "heavy lifting" of defining the model's structure is moved to the local PRNG. The communication channel is then reserved for the only thing that truly matters: the choice of which random sample best fits the local data.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_communication_compression_via_shared_ran_bd99d443,
  title = {Communication Compression via Shared Randomness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-compression-via-shared-randomness/rdr_bd99d4431c8549fa9319366e4373f8b8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_communication_compression_via_shared_ran_bd99d443_v1,
  title = {Communication Compression via Shared Randomness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-compression-via-shared-randomness/rdr_bd99d4431c8549fa9319366e4373f8b8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}