Research map / Learning theory and algorithms / Combinatorial and search optimization
Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back 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 Random Cycle Coding (RCC), a training-free bits-back method that losslessly encodes cluster assignments by embedding them as permutation cycles, achieving the optimal log-cluster-permutation savings for vector database ids.
Problem
Lossless storage of cluster assignments (e.g., inverted lists in FAISS vector databases) currently costs many bytes per element in artificial integer labels; prior multiset methods (ROC) are suboptimal for clusterings.
Approach
Encode data sequentially with bits-back so that the clustering is implicitly carried by the cycle structure of the permutation induced by the encoding order; cycles correspond to clusters, and the savings equal log of the number of sequences sharing that clustering, which is shown to be optimal and to outperform ROC-based variants.
Key results
- RCC achieves the optimal savings (0.00% gap to the bound log|Pi|) on SIFT1M and BigANN configurations, while ROC-1 has gaps up to 76.28% and ROC-2 up to 2.07%.
- RCC saves up to 2 bytes per element in vector databases, with savings up to 70.1% of storage for 1B elements with 4-byte sequential ids.
- RCC has lower encoding plus decoding time than both ROC variants, with time independent of the number of clusters when log|Pi|=0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RCC instead of ROC-1 for lossless cluster-assignment compression | Cluster assignments on SIFT1M and BigANN · SIFT1M and BigANN configurations in the byte-savings table | gap to optimal savings (%) | Helped |
| Use RCC instead of ROC-2 for lossless cluster-assignment compression | Cluster assignments on SIFT1M and BigANN · SIFT1M and BigANN configurations in the byte-savings table | gap to optimal savings (%) | Helped |
| Encode cluster sizes as in ROC-1 without exploiting random cluster order | ROC-1 · Large numbers of clusters | bit savings | Hurt |
| Add bits-back selection of cluster ordering as in ROC-2 | ROC-1 · Cluster-assignment compression | bit-rate reduction | Helped |
| Add bits-back selection of cluster ordering as in ROC-2 | ROC-1 · Cluster-assignment compression | encoding and decoding time | Hurt |
| Use RCC rather than ROC variants | Cluster-assignment compression · Encoding and decoding across element and cluster counts | wall-time | Helped |
| Use RCC rather than ROC-2 | FAISS inverted lists · FAISS databases with scalar-quantized clusters | compute | Helped |
| Represent cluster assignments with RCC and omit sequential ids | FAISS vector databases · Sequential ids, 1B elements, 4-byte vectors | percentage savings: 70.1 | Helped |
Surprising findings
- ROC-1 yields negative savings when the number of clusters is large, because encoding cluster sizes costs more than the bits-back gain.
Limitations
- Assumes no repeated elements and a total ordering over the data alphabet.
- Savings depend on cluster sizes and are small when clusters are many and singletons (savings approach zero as k approaches n).
- Evaluated only on SIFT1M and BigANN-style FAISS inverted lists with scalar quantization partitioning.
Experimental setup
Datasets: SIFT1M BigANN FAISS inverted lists
Benchmarks: SIFT1M BigANN
Metrics: byte savings per element gap to optimal savings (%) encoding plus decoding wall-time percent savings of vector database storage
Baselines: ROC-1 ROC-2 Random Order Coding
Builds on: Random Order Coding bits-back coding Asymmetric Numeral Systems Foata's bijection
Closest papers by meaning
- Entropy Coding of Unordered Data Structures (ICLR 2024 · similarity 0.85)
- Practical Shuffle Coding (NeurIPS 2024 · similarity 0.83)
- Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework (NeurIPS 2024 · similarity 0.82)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.81)
- Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks (ICLR 2025 · similarity 0.81)
- Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth (ICML 2024 · similarity 0.81)
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.