Research map / Federated learning and privacy / Communication-efficient FL
Universal Sample Coding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes universal sample coding, which communicates multiple i.i.d. samples from an unknown discrete distribution by running channel simulation in O(log n) rounds while updating the reference distribution with a KL-optimal estimator, and applies it to federated learning and LLM sample communication.
Problem
Communicating multiple i.i.d. samples from an unknown distribution P to a decoder using as few bits as possible, when encoder and decoder only share a reference distribution Q that is updated over time.
Approach
Run channel simulation (ordered random coding) in rounds with exponentially growing batch sizes, and after each round update the reference Q with the add-1/2, add-3/4, add-1 Braess-Sauer estimator so the KL divergence to P shrinks and later rounds are cheaper; the total cost matches the universal source coding redundancy lower bound up to a constant factor.
Key results
- In federated learning with FedPM (CONV-6, CIFAR-10), universal sample coding with 7 samples per client reduces bits per parameter from 0.3955 to 0.2482 at similar accuracy (~0.80), a 37% reduction versus using only the prior.
- For remote LLM sampling, estimated sample communication cost per token from OPT-13B with OPT-6.7B as reference is 0.266 bits versus 15.617 for plain text and 4.315 for estimated entropy, up to 16x reduction vs entropy coding.
- Theoretical upper bound V_k(c) log(n) matches the lower bound (k-1)/2 log(n) up to a factor that approaches 1 as k grows; the gap is about 9x at small k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use universal sample coding with prior θ instead of coding multiple samples using only prior θ | FedPM · CIFAR-10, 1 client per round and 7 samples per client | communication load: 37% reduction | Helped |
| Communicate 7 samples per client instead of 1 (ablation) | FedPM · CIFAR-10, 1 client per round | final test accuracy: 0.7516 -> 0.8028 | Helped |
| Add USC when communicating 7 samples per client (ablation) | FedPM · CIFAR-10, 1 client per round | final test accuracy: 0.8028 -> 0.8039 | Helped |
| Add USC when communicating 7 samples per client (ablation) | FedPM · CIFAR-10, 1 client per round | # bits per parameter: 0.3955 -> 0.2482 | Helped |
| Use sample communication with an OPT 125M reference model rather than entropy coding | OPT 13B remote generation · OpenbookQA-conditioned tokens | # bits per token: 4.315 -> 1.014 | Helped |
| Increase the reference model size from OPT 125M to OPT 6.7B (ablation) | OPT 13B sample communication · OpenbookQA-conditioned tokens | # bits per token: 1.014 -> 0.266 | Helped |
| Use the largest tested reference model, OPT 6.7B, rather than entropy coding | OPT 13B remote generation · OpenbookQA-conditioned tokens | communication rate: up to 16 times | Helped |
Surprising findings
- For a single token (B=1), source coding is more efficient than sample communication because the constant overhead of channel simulation (about 5 bits) exceeds the source-coding cost.
Limitations
- Lower and upper bounds scale linearly with alphabet size k, so the method does not directly apply to continuous variables.
- Counting-based estimation fails for very large discrete spaces such as text, motivating model-based references.
- The constant overhead of channel simulation makes sample communication worse than source coding for single-token groups.
Experimental setup
Datasets: CIFAR-10 OpenbookQA
Benchmarks: CIFAR-10
Metrics: KL divergence communication cost in bits test accuracy bits per token communication cost per token
Baselines: FedPM source coding (Huffman, entropy coding) Choi and Li (2021)
Builds on: Li and Anantharam channel simulation bound Braess and Sauer estimator Davisson et al. universal source coding redundancy FedPM ordered random coding
Closest papers by meaning
- Channel Simulation and Distributed Compression with Ensemble Rejection Sampling (NeurIPS 2025 · similarity 0.87)
- List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression (NeurIPS 2025 · similarity 0.86)
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning (ICML 2025 · similarity 0.85)
- LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression (ICLR 2025 · similarity 0.85)
- Progressive Compression with Universally Quantized Diffusion Models (ICLR 2025 · similarity 0.85)
- FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.