Most compression algorithms are designed for sequences. They assume that if you have a list of items, the specific order of those items is part of the information that must be preserved. However, many modern data structures—sets of image features, database rows, graph edges, or clusters of vectors—are inherently unordered.
When we use a sequence-based compressor on unordered data, we pay an "order tax." For a set of $n$ unique items, there are $n!$ possible permutations. By picking one specific permutation to store, a standard compressor implicitly encodes $\log_2(n!)$ bits of information that the receiver doesn't actually need. As Vivek K Goyal pointed out in Benefiting from Disorder: Source Coding for Unordered Data, this mismatch forces systems to encode positional information that has no functional utility, leading to significant storage overhead.
Recent research has developed a way to "refund" this tax, achieving theoretical optimality by treating the data's ordering as a storage resource rather than a waste.
The Bits-Back Intuition
The core breakthrough in this field is the application of bits-back coding to permutations. The intuition is simple: if the order of elements doesn't matter, we can use the choice of a specific permutation to "hide" other data.
Imagine you need to send a set of three items $\{A, B, C\}$ and also a separate bitstream of auxiliary data. There are $3! = 6$ ways to order your set. You can use your auxiliary bitstream to decide which of those six orders to send.
- The encoder "decodes" a value from the auxiliary bitstream to pick a permutation (e.g., $B, C, A$).
- The encoder then compresses this sequence using a standard method.
- The decoder first recovers the sequence $B, C, A$.
- Because the decoder knows the set is unordered, it can look at the specific permutation $B, C, A$ and "re-encode" the choice to recover the original auxiliary bits.
In effect, the bits used to specify the order are "given back" to the user. As Daniel Severo explains in Random Permutation Codes: Lossless Source Coding of Non-Sequential Data, this allows the final message length to reflect only the information content of the items themselves, effectively subtracting the $\log_2(n!)$ order cost from the total bit-rate.
Compressing Graphs and Multisets
This mechanism has been generalized into a framework for "permutable classes"—data structures invariant under specific permutations. In Entropy Coding of Unordered Data Structures, Julius Kunze, Daniel Severo, and James Townsend demonstrate that this approach can reduce file sizes by 26% to 47% across diverse datasets by eliminating the redundancy of arbitrary ordering.
A prominent application is Random Edge Coding (REC), introduced in One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding. Graphs are mathematically defined as unordered sets of edges, but digital storage usually requires an edge list. REC treats the edge sequence as a latent variable. By using bits-back coding with a parameter-free Pólya’s Urn model, Severo and Ashish Khisti achieve near-optimal compression that scales linearly with the number of edges, making it practical for massive social networks.
Applications in Vector Databases and Retrieval
The "order tax" is particularly heavy in large-scale retrieval systems. In Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search, researchers including Matthijs Douze and Giuseppe Ottaviano target the auxiliary data—vector IDs and neighbor lists—that often dominate storage. By treating these lists as unordered sets, they achieve up to a 7x reduction in ID storage.
Similarly, Random Cycle Coding (RCC), detailed in Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding, compresses cluster assignments by "hiding" them in the ordering of the data itself. By treating clusters as cycles within a permutation, Alireza Makhzani and colleagues show that cluster membership can be stored at near-zero bit cost, slashing metadata overhead in vector databases by up to 70%.
Scaling to Massive Alphabets
Early attempts at multiset compression often struggled with large "alphabets" (the range of possible values for each item). Compressing Multisets with Large Alphabets solved this by integrating Asymmetric Numeral Systems (ANS) with the bits-back mechanism. This decoupling of computational complexity from alphabet size allows the method to work on complex data like JSON files or high-resolution image collections.
To make these techniques viable for billion-edge graphs, Practical Shuffle Coding by Julius Kunze and others introduced an autoregressive approach that approximates object symmetries. This framework acts as a modular wrapper, allowing any existing statistical model for sequences to be transformed into an optimal compressor for unordered data, running orders of magnitude faster than previous iterations.