# Compressing Multisets with Large Alphabets using Bits-Back Coding

arXiv: https://arxiv.org/abs/2107.09202 · HTML: https://mlsanity.com/paper/2107.09202/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 15 Jul 2021.

## Builds on (most cited first, 6 of 6)

- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019)
- [HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models](https://mlsanity.com/paper/1912.09953/) (2019)
- [Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding](https://mlsanity.com/paper/2102.11086/) (2021)
- [Lossless compression with state space models using bits back coding](https://mlsanity.com/paper/2103.10150/) (2021)
- [Lossless Compression with Latent Variable Models](https://mlsanity.com/paper/2104.10544/) (2021)

## Built on by (most cited first, 4 of 4)

- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding](https://mlsanity.com/paper/2412.00369/) (2024)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)

## Abstract (arXiv)

Current methods which compress multisets at an optimal rate have computational complexity that scales linearly with alphabet size, making them too slow to be practical in many real-world settings. We show how to convert a compression algorithm for sequences into one for multisets, in exchange for an additional complexity term that is quasi-linear in sequence length. This allows us to compress multisets of exchangeable symbols at an optimal rate, with computational complexity decoupled from the alphabet size. The key insight is to avoid encoding the multiset directly, and instead compress a proxy sequence, using a technique called `bits-back coding'. We demonstrate the method experimentally on tasks which are intractable with previous optimal-rate methods: compression of multisets of images and JavaScript Object Notation (JSON) files. Code for our experiments is available at https://github.com/facebookresearch/multiset-compression.