Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding
Authors: Daniel Severo
Ashish J Khisti
Alireza Makhzani
Venue: NeurIPS 2024 poster (2024)
Keywords: compression
vector databases
clustering
permutations
Primary area: other
TL;DR: We encode cluster assignments, indicating which cluster a data point belongs to, without creating labels. The information is implicit in the ordering of the dataset. This results in significant memory savings for vector database and applications.

Abstract: We present an optimal method for encoding cluster assignments of arbitrary data sets. Our method, Random Cycle Coding (RCC), encodes data sequentially and sends assignment information as cycles of the permutation defined by the order of encoded elements. RCC does not require any training and its worst-case complexity scales quasi-linearly with the size of the largest cluster. We characterize the achievable bit rates as a function of cluster sizes and number of elements, showing RCC consistently outperforms previous methods while requiring less compute and memory resources. Experiments show RCC can save up to $2$ bytes per element when applied to vector databases, and removes the need for assigning integer ids to identify vectors, translating to savings of up to $70\%$ in vector database systems for similarity search applications.

Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding
Daniel Severo
Ashish Khisti
Alireza Makhzani
University of Toronto
Department of Electrical and Computer Engineering
{d. severo@mail, akhistiß, a a.makhzani @) utwronto.coom ca
Abstract
We present an optimal method for encoding cluster assignments of arbitrary data sets, Our method, Random Cycle Coding (RCC), encodes data sequentially and sends assignment information cycles of the permutation defined by the order of encoded elements. RCC does not require any training and its worst-case complexity scales quasi-linee linsill with the size of the largest cluster. We characterize the achievable bit rates function of cluster sizes and number of elements, showing RCC consistently outperforms previous methods while requiring less compute and memory resources. Experiments show RCC can save up to 2 bytes per element when applied to vector databases, and removes the need for assigning integer ids identify vectors, translating to savings of up to 70% in vector database systems for similarity search applications.
Introduction
clustering is collection of pairwise disjoint sets, called clusters, used throughout science and engineering group data under context-specific criteria. A clustering be decomposed conceptu- ally into two parts of differing nature. The data set, created by the set union of all clusters, and the assignments, indicating which elements belong which cluster. This work is concerned with the lossless communication and storage of the assignment information, for arbitrary data sets, from an information theoretic and algorithmic viewpoint.
Communicating clusters appears a fundamental problem in modern vector similarity databases such as FAISS [Johnson et al., 2019]. FAISS is database designed store vectors of large dimensionality. usually representing pre-trained embeddings, for similarity search. Given a query vector, FAISS returns set of the k-nearest neighbors [Lloyd, 1982] available in the database under some pre-defined distance metric (usually the L2 distance). Returning the exact set requires an exhaustive search over the entire database for each query vector which quickly becomes intractable in practice. FAISS can instead return an approximate solution by performing a two-stage search on coarse and fine grained set of database vectors. The database undergoes training phase where vectors clustered into sets and assigned a representative (i.e., a centroid). FAISS first selects the k' -'-nerrest clusters, < k based the distance of the query to the centroids, and then performs exhaustive search within them to return the approximate ic ieneerest neighbors.
The cluster assignments must be stored to enable cluster-based approximate searching. In contrast class, a cluster is distinguishable only by the elements contains, and is void of any labelling. However, cluster assignments generated labels. Lossy compression techniques for storing the vectors themselves is an active area of research [Chen et al., 2010, Martinez et al., 2016, Babenko and Lempitsky, 2014, Jegou et al., 2010, Huijben et al., 2024]. In this literature, the number of bits used to store the vector embedding ranges
often stored alongside the data set in the form of artificially
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(I.
d'
ANS stack
(2 53))
24153
N
(2 4))135) [24135]
Figure 1: High-level description of our method, Random Cycle Coding (RCC). RCC encodes the clustering (X,, II) cycles in the permutation induced by the relative ordering of objects. Left: Indices represent the rankings of objects in X according the total ordering of X. Middle: One of two permutations will be randomly selected with bits-back coding to represent the clustering (a, shown in
Then, Foata's 's Bijection is applied yield o'. shown in line-notation, which encoded into the ANS stack. Right: The final ANS stack containing o' in line-notation.
from 4 to 16 bytes, while ids are typically stored as 8-byte integers. Therefore, labelling, for the sake of clustering, represent the majority of bits spent for communication and storage in typical use case, and will become the dominating factor as the performance of these compression algorithms improves.
In this work we show how to communicate and store cluster assignments without creating artificial labels, providing substantial storage savings for vector similarity search applications. Assignments are implicitly represented by a cycle of a permutation defined by the order between encoded elements. Our method, Random Cycle Coding (RCC), uses bits-back coding [Townsend et al., 2019] to pick the order in which data points are encoded. The choice of orderings is restricted to the set of permutations having disjoint cycles with elements equal to some cluster. RCC is optimal it achieves the Shannon bound [Cover, 1999] in bit savings. The worst-case computational complexity of RCC is quasi-linear in the largest cluster size and requires training machine learning techniques.
An overview on lossless compression, permutations, and bits-back coding is given Section 2. Our method is presented and analyzed in Section 3. To the best of our knowledge, current method exists to optimally store cluster assignments. In Section we provide two strong baselines based on the work of Severo et al. [2023] for compressing multisets. Section 5 showcases RCC on real-world databases from a well known vector database called FAISS [Johnson et al., 2019], achieving savings of up to 70% in the best case.
2 Background
2.1 Lossless Compression
Lossless compression aims to find code C: C:X- X {0, 1)* for infinite i..dd sequence of elements ( Px that can be decoded with perfect fidelity. Lossless decoding requires restricting C created via concatenation, is uniquely decodable. known that Ex [C(X) 2 H(Px) for any uniquely decodable code, and any code with average-length close to ((Px) must obey C(x) R log (x [Shannon, 1948, Cover, 1999]. It is possible to construct using entropy coders such as Asymmetric Numeral Systems [Duda, 2009], Arithmetic Coding [Witten et al., 1987], or Huffman Codes [Huffman, 1952].
such that the extended code C(x()) (xx())
common way of designing efficient codes is guarantee the code-word C(x) carries some meaningful semantics for æ that allows for an efficient implementation. Semantic codes can be constructed by introducing an intermediate sequence of random variables 2 acting as a proxy for X which is entropy coded autoregressively in n steps. The code-word for is the binary
From here drop the superscript X (+) and focus single X, without loss of generality.

---

representation of the final state of the chosen entropy coder (e.g.. ANS [Duda, 2009]), Unfortunately. semantic entropy coding can lead sub-optimal performance due the con-uniqueness of the mapping between X' and 2", limiting their practical use in applications where this redundancy is large. This is the case for large structured data types such as clusters of high-dimensional embeddings.
Asymmetric Numeral Systems (ANS) [Duda, 2009] is an entropy coder that stores data to an integer state s E IN using the PMF and CDF of some probability model over the data. When data is encoded the integer state increases by approximately the information content under the model (i.e., the negative log- rogllikeihhood, which equals the entropy of the source on average. The final value of the integer state is then serialized to disk using approximately log s bits. ANS operates on s in stack-like fashion. Symbols are decoded in reverse order in which they where encoded. Due to this -tke- nature ANS can be used as an invertible sampler. by initializing the stack to a random integer and performing a decode operation. Under mild initialization conditions for 8 (see Townsend et [2019], Severo et al. [2023]), the decoded sample will be distributed according to the probability model used for decoding. Decoding reduces the number of bits required to represent the stack by the information content of the sampled symbol. The randomly initialized stack can be recovered by encoding the sampled symbol back into the stack using the same distribution.
2.2 Bits-back Coding with ANS
Bits-back Coding [Frey and Hinton, 1996, Townsend et al., 2019] is an entropy coding method for latent variable models Px, z. The bit-rate achieved equal the cross-entropy Ex log Px (X)]. where the expectation is taken with respect to the true data distribution of X, despite not having direct access to the marginal Px needed for entropy coding. Given the posterior Pzix. prior Pz. and conditional likelihood Px z of the model, bits-back coding using ANS to perform invertible sampling from P2|x to obtain Z. Then, is encoded with Px|2. conditioned on the sampled Z. Finally, Z is encoded with the prior Pz. Decoding from the stack reduces the ANS integer state by - log P x while encoding increases it by - log PxPx Px| 2. resulting a net increase equal to the cross-entropy. An approximate posterior can be used when the exact posterior Pz x is not available, resulting in the net increase being equal to the Negative Evidence Sower-Bound (NELBO) [Townsend et al., 2019].
2.3 Random Order Coding (ROC)
ROC [Severo et al., 2023] is an algorithm for losslessly compressing multisets?. sequence can be seen as a multiset, representing the frequency count of symbols, together with permutation defining the ordering. ROC uses bits-back coding with the ordering as a latent variable Z, and the multiset as the observation X, together with an exact posterior Qz x Pz x- The exactness of the posterior implies the number of bits used by ROC to encode the multiset equal to the cross-entropy of the multiset with respect to the true data distribution.
ROC applies similar procedure to our method to select a random element in the multiset which is then encoded with a symbol codec using ANS. For a multiset with k unique elements, each appearing n, times, ROC saves exactly log Pz x = log (m.."... S log(n!) bits, where the quantity in parentheses the multinomial coefficient.
2.4 Permutations and Cycles
A permutation, in this work, is a bijective function a [m] + [n]] used to define arrangements of elements from arbitrary sets. Permutations are usually expressed in one-line notation a
[i, f2,..., in] where (j) = ij. The symmetric group S,, on n elements is the set of all permutations of [n].
cycle (c1 ... ck). of a permutation o, is the sequence constructed from the repeated application of
to some element C₁ E [r]], until e₁ is recovered, i.c., Ck+1 C1. G (G--1), for i > 2.
Example 1. The cycles of [3. 1, 2, 4) shown below.
A permutation can be represented by its cycles with the following procedure. Pick any element in
[n] and compute its cycle by applying o successively. Next, choose another element in [n], that did not show up in any of the previously computed cycles, and compute its cycle. Repeat this procedure
Multisets are sets that allow repetition of elements but have ordering between elements.
3

---

2 cycle (1 (213)
3
4 5 (45)
(321)
(54)
until all elements appear in exactly one cycle. Concatenate cycles to form the representation. Every permutation has unique representation through the concatenation of disjoint cycles. For example,
[3, 1, 2, 5, 4] (1 (1
where the right-hand side is called the cycle notation of a.
Lemma 2.2 (Foata's Bijection [Foata, 1968]). The following sequence of operations defines bijection between permutations on elements. Write the permutation in disjoint eycle notation such that the smallest element of each cycle appears first within the cycle. Order the cycles in decreasing order based on the firt/smallest element each eycle. Remove all parenthesis to form the one-line line notation of the output permutation.
Example 2.3. Applying the steps in the construction Foata's bijection to [3. 1, 2, ( () 4)
yields (1 3 (4 5) + (4 51 3 2) + [4, 5, 3, 2]. Cycles can be recovered by scanning from left to right and keeping track the smallest value.
3 Method
In this section we develop our method, Random Cycle Coding (RCC), which encodes clusters of data points as disjoint permutation cycles. In what follows, we first describe the coding procedure and then show the model resulting from our procedure assigns likelihood proportional to the product of cluster sizes.
Let X (XI,......... X,) be a sequence of random variables X; with common, but arbitrary, alphabet X.. Throughout assume that lotal ordering can be defined for X, i.e., elements of the set be compared and ranked/sorted according to some predefined criteria (e.g.. lexicographical ordering). We assume no repeats happen the sequence. This is motivated by applications where elements are high-dimensional vectors such as embeddings or images where repeats are unlikely to happen.
We are interested in the setting where the elements of X are grouped into pair-wise disjoint sets known as clusters. Clusters can be represented by a collection of indicator random variables = (II,) I<is<<n where II; if X,, X, are in the same cluster and Hl 0 otherwise. Conditioned on the sequence X x" the clustering ll defines a partition of the data set X ( The size of the alphabet of equal to the number of ways in which X can be partitioned; known as the n-th Bell number [Bell, 1934]. The order between elements in a cluster is imrlevant and clusters are void of labels.
The objective is to design a lossless code for the assignments that can be used alongside any codec for the data set X. Our strategy will be to send the elements of X in particular ordering such that it implicitly encodes the clustering information.
We associate permutation x² to each of the possible n! orderings of X based on sorting. Let (x)) be the set of all possible orderings of X, and s" reference sequence created by sorting the elements in X according to the total ordering of X,
S,) = fa": Iz E E and x # 2j for * j}. S" E S, s.t. <
(2)
For any x" E S., (2²), the induced permutation a.." is defined as that which permutes the elements of the reference s such that x is obtained. Under this definition the permutation also be constructed by directly substituting 2; for its ranking in &.
The induced permutations allow us to redefine as a random equivalence class taking on values in the quotient set, S, (& of the equivalence relation described next. Note the quotient set finite even if X' is uncountable as only the relative ordering between elements is needed to define the cquivalence relation.
Definition 3.1 Byyyle-Cluteer-Euuivlllee disjoint cycles of their induced permutations contain the same clements. Given a sequence, two
Two sequences in Sa() are equivalent (~) if the

---

elements of X' are in the same cluster if their rankings appear in the same disjoint cycle of the induced permutation.
Example 3.2. Let X' be the set of even integers under the usual ordering for natural numbers.
Sequences xn (4, 2. 8) and x" (6, 2, 4, 8) induce permutations 'xn [2. 1, 4] and 0- [3, 1, 4). The sequences are equivalent as the disjoint cycles of the induced permutations contain the same elements: TR- = (4) 3). -T = (4) 3 2). For both sequences. elements 2, 4, and are in the same cluster, while 8 is in cluster of its own. The partition, viewed as equivalence class, is equal to II {x", 2*) }. as there are no other permutations over X' that are equivalent to the two shown.
Given (X, II), Random Cycle Coding (RCC) uses bits-back coding to send the elements of X' in an ordering which corresponds to sequence in IT. The receiver decodes the elements X,, in the order sent, and recovers IT by computing the cycles of the induced permutation. The clustering information is communicated via the cycles of the permutation. See Figure for a high-level description.
Every sequence in II maps to the same clustering over X. The log of the number of elements the equivalence class equals the redundancy discussed in Section 2.1, which is known to be
#cycles Σ
log
log((n; - 1)!).
where n; is the number of elements in the i-th cycle of the induced permutation. An optimal bits-back method must remove exactly log/I[| bits from the stack during encoding. RCC achieves these savings by selecting an element from X', using ANS decode operation, and then encoding it onto the stack. Interleaving samplligg and encoding avoids the initial bits issue [Townsend et al., 2019] resulting from the initially empty ANS stack.
Random Order Coding [Severo al., 2023] (ROC) performs similar procedure for multiset compression where elements also sampled without replacement from X. However, there, the equivalence classes consist of all permutations over X,, and therefore sampling be done by picking any element from X' uniformly at random. RCC requires sampling without replacement from X non-uniformly such that the resulting permutation has a desired cycle structure. To do so, we define the following procedure, reminiscent of Foata's 's Bijection [Foata, 1968].
Definition 3.3 (Foata's Canonicalization). The following steps map all sequences in the same equivalence class, x= E II, the same canonical sequence c II. First, write the permutation in disjoint cycle notation and sort the elements within each cycle, in ascending order, yielding a new permutation. Next, sort the cycles, based the first (i.e., smallest) element, in descending order.
Example 3.4. The set composed of permutations a (3 1)(5 2 4) and π = (3 1)(2 5 4) is an equivalence class. Applying Foata's Canonicalization to either or π yields (2 4 51 3), which is equal to o.
Algorithm RCC encodes permutation using the procedure outlined in Algorithm 1. The elements of X are inserted into lists according to their clusterings. The clustering is canonicalized according to Definition 3.3. The encoder starts from the last, i.e., right-most, list. The list is encoded as set using ROC, with the exception of the smallest element, which is held-out and encoded last. This procedure repeats until all lists are encoded. Decoding is shown in Algorithm 2. During decoding the first element is known to be the smallest in its cycle. The decoder then decodes the remaining cycle elements using ROC, and stops when it sees an element smaller than the current smallest element. This marks the start of a new cycle and repeats until all elements are recovered. Python code for encoding and decoding are given in Appendix A.
Savings Encoding the smallest value last guarantees that the cycle structure is maintained. Per- muting the remaining elements the cycle spans all permutations in II. For the i-th cluster with n; elements the savings from encoding n, elements with ROC is equal to log((n; - 1)!). The total savings is equal to (4), implying RCC saves II]
Implied Probability Model The probability model Qn is indirectly defined by the savings achieved by RCC. The set of elements and clustering assignments (&L, II) are encoded via a se- quence z" II. We can assume some lossless source code is used for the data points, requiring
5

---

Algorithm 1: Pscudo-code for encoding with RCC.
Inputs: (1) Clustering as set of sets ((=),...,"), } (2f.
(1)
o }:: (2)
Initial ANS state; (3) Symbol codec
Sort the clustering into list of lists, with elements yf, according to Definition 3.3, such that (yf..... vn.)) is an increasing sequence, and (vi...., vf is decreasing.
for c= m=c==,,... l,.., do -un. with ROC using the given symbol codec
Encode Encode yf with symbol codec
end
return Final ANS state
Algorithm 2: Pseudo-code for decoding with RCC.
Inputs:
Total number of elements
Final ANS state, constructed from Figure 4
Symbol Codec
Initialize IT = =]
while total number of elements in IT is less than do
Decode yf with the symbol codec
Decode elements yf with ROC until an element smaller than yf is seen Add all decoded elements to II as a list ,.f,....
Increment e
end
return IT, Initial ANS state
- log Qx (x*) ) bits to encode the sequence. The cost of encoding the dataset and cluster assignments equals the cost encoding a sequence minus the discount given by bits-back,
log Q Q
log Qx (x") log/II|.
(5)
From Severo et al. [2023] we know the cost of encoding the set X' is that of the sequence minus the cost of communicating an ordering,
log Qx(x) - log Qx= loognn))................
(6)
From this, we can write.
- log Qu & (IT) X = log Qx log Qx (x") - log IT| log(n!) - log TT|
The implied probability model only depends on the cluster sizes, and assigns higher likelihood when there are few clusters with many elements,
-
(n; 1)!
Qu & 2 (II
(8)
n!
where n; is the size of the i-th cluster, and the total number of clusters.
Complexity The complexity of RCC will vary significantll according to the number of clusters and elements. Initializing RCC requires sorting elements within each cluster, which can be done in parallel, followed by sort across clusters. ROC used as a sub-routine and has both worst- and average-case complexities equal to Ω(n, log n.) for encoding and decoding the i-th cluster. The total computational complexity of our method, RCC, adapts to the size of the equivalence class: 2 (EE; n4 logm:) m4) IT) When only one permutation can represent the cluster assignments, i..., n k. implying log ((n).
0, then RCC has the same complexity as compressing sequence:

---

Encude + decode time
10
n.. m 100
1000
3.5
35
350
RCD
ROC-1
Mierawoods
ROC-2
lng (T)
2.5
26
250
2.0
200
130
1.0
10
100
5
50
100
500
1000
Number clusters (I)
Figure 2: Median encoding plus decoding times, across 100 runs, for Random Order Coding (ROC) [Severo et al., 2023] and our method Random Cycle Coding (RCC). The number of elements increases from left-to-right across plots. Clusters are fixed to have roughly the same size, n/ kk mirroring vector database applications discussed in Section 5.3. Reported times representative of the amount of compute needed to sample the permutation in the bits-back step as data vectors are encoded with ANS using uniform distribution.
Related Work
To the best of our knowledge there is no other method which can perform optimal lossless compression of clustered high-dimensional data.
Severo et al. [2023] presented method to optimally compress multisets of elements drawn from arbitrary sets called Random Order Coding (ROC). ROC can compress clusterings by viewing them as sets of clusters, but is sub-optimal as it requires encoding the cluster sizes. We compare RCC against the following two variants of ROC next and provide experiments in Section 5.
The cluster sizes are communicated with a uniform distribution of varying precision and clusters are then encoded into a common ANS state. Each cluster contributes log(n,!) the bits-back savings of ROC, resulting in reduction in bit-rate of
ROC-1
AROC-1
(log(n:!) - log(n N:))
(9)
log
+ log III
(10)
N;
I log IT]
(11)
where k is the number of clusters, N₂ = ビ n, counts the number of encoded elements before step i, and log(n N;) is the cost of encoding the size of the i-th cluster. The gap to optimality increases with the number clusters, while RCC always optimal it achieves log/TT for any configuration of elements and clusters.
ROC-2 This variant views the clusterings as of sets. The cluster sizes are communicated as in ROC-1. However, an extra bits-back step is done to randomly select the ordering in which the k clusters are compressed, resulting in further savings. The complexity this step scales quasi-linearly with the number of clusters, O[k log k), and requires sending the number of clusters (log(n) bits), which is also the size of the outer set. The total reduction in bit-rate
AROC AROC- log(k:) log(n).
(12)
This method achieves a better rate than ROC-1, but can require significantly more compute and memory resources due to the extra bits-back step to select clusters compared both ROC-1 and RCC. Conditioned on knowing the cluster sizes, ROC-2 compresses each cluster independently. Intuitively, the method does not take into account that clusters are pairwise disjoint and their union equals the interval of integers from to which explains why it achieves sub-optimal rate savings.
7

---

Maximum savings
Minimum savings
Bytes Bytee-per-- element (Bpe)
102
RCC
10a
ROC
10a
6
4
7
Number of clusters (10*)
Figure 3: Maximum (left) and minimum (right) byte savings per element function of the number of clusters and elements. Savings are maximized when one cluster contains most elements and all others are singletons. The minimum is achieved if clusters have roughly the same number of elements. Two variants of Random Order Coding (ROC) [Severo et al., 2023] are shown (see Section 4) with dashed lines. Random Cycle Coding (RCC) achieves higher savings than both variants of ROC while requiring less memory and computational resources.
5 Experiments
5.1 Minimum and maximum achievable savings
In applications targeted by our method (see Section 5.3) the cluster size set according to some budget and elements are allocated into clusters via training procedure. For fixed number of elements (n) and clusters (k) the savings for ROC-1, 1, ROC-2, and RCC will depend only on the cluster sizes (M1,... n₂)). We empirically analyzed the minimum and maximum possible savings a function of these quantities. Results are shown in Figure 3.
The term dominating the bit savings of all algorithms is the product of the factorials of cluster sizes, II n²4, constrained to E; n4 n and ni Z 1. The maximum is achieved when n - k elements fall into one cluster, fl minimized when all clusters have roughly the same size:
k + 1, and all others are singletons: nG for / j. Savings are (n k) fi S mod k)3..
All methods provide similar savings when & n. RCC has better maximal and minimal savings than both ROC-1 and ROC-2 in all settings considered. The need to encode cluster sizes, without exploiting the randomness of cluster orders as in ROC-2, results in ROC-I achieving negative savings when the number of clusters is large. RCC savings converge to 0 bits the number of clusters approaches the number of elements, as expected. As approaches n, ROC-2 also suffers from negative savings, but the values are negligible compared to those of ROC-1.
5.2 Encoding and decoding times
Figure 2 shows the total encoding plus decoding time as a function of number elements and clusters. RCC outperforms both variants of ROC in terms of wall-time by wide margin, while achieving the optimal savings. RCC is compute adaptive and requires the same amount of time to encode a sequence when log 0. The compute required for ROC variants increases with the number of clusters, correlating negatively with log II]. ROC-2 is slower than ROC-1 due to the extra bits-back step needed select clusters with ANS.
5.3 Inverted-lists of Vector Databases (FAISS)
We experimented applying ROC and RCC FAISS [Jonsson et al., 2019] databases of varying size. Results are shown in Table 1. Scalar quantization [Cover, 1999, Lloyd, 1982] was used to partition the set of vectors into disjoint clusters. This results in clusters of approximately the same number of
3 represents integer division, n mod & is the remainder, and 1(} is the indicator function that evaluates to I if the expression is true.

---

Savings
Dataset
Elements
Clusters
Max.
Min.
log|11
RCC
ROC-2
ROC-1
500
2.31
1.19
1.20
0.00
0.00
0.04
1000
2.31
1.06
1.08
0.00
0.00
0.10
4,973
2.30
0.77
0.81
0.00
0.04
0.86
SIFTIM
1,000,000
9,821
2.29
0.65
0.71
0.00
0.12
2.17
46,293
2.20
0.37
0.48
0.00
1.28
18.28
95,284
2.07
0.24
0.30
0.00
2.07
61.43
1,000
2.31
1.06
1.07
0.00
0.00
0.10
1,000,000
10,000
2.29
0,65
0.66
0.00
0.01
2.27
99,946
2.06
0.23
0.25
0.00
0.79
76.28
BigANN
1,000
2.73
1,48
1.49
0.00
0.00
0.01
10,000,000
10,000
2.72
1.06
1.07
0.00
0.00
0.14
99,998
2.70
0.65
0.66
0.00
0.01
2.89
Byte savings, per element, from compressing SIFTIM [Jegou et al., 2010] and BigANN [Jégou et al., 2011] as a function of number of elements and clusters. Values in columns RCC, ROC-2, and ROC-1, indicate the gap, in percentage (lower is better), to the optimal savings in bytes-per-eiement, in column J log [[]. value of 0.00 indicates the method achieves the maximum bit savings shown in column
Table 1:
An
1 log/ Columns Max. and Min. show the theoretical maximum and minimum savings discussed in Section 5.1.
8y.
Savings
Sequential ids
External ids
1.
log
4
16
Br
1M
1.06
54.8
33.9
19.2
8.9
6.7
4.4
10M
1.27
60.5
38.3
22.1
10.6
8.0
5.3
100M
1.48
65.6
42.4
24.9
12.3
9.3
6.2
1B
1.69
70.1
46.2
27.5
14.1
10.6
7.0
Table 2: Columns under "% Savings" show the savings, in percentage. for the setting of Johnson et al. [2019] where the number clusters is held fixed to approximately vn. Savings are shown in the second column, where log| external ids, 8 bytes are added to 8n log IT| to compute the total size per element, as well as to the cost under RCC. Meanwhile, log(n) bits are added to 8n: log/Il| for sequential ids, but not to the cost under RCC, as RCC does not require ids to represent clustering information. See Section 5.3 for full discussion.
/n log((v/ 1)!). and agree with Table 1. For
elements, which is the worst-case savings for both ROC and RCC. RCC achieves optimal savings for all combinations of datasets, number of elements, and clusters. ROC-2 has similar performance to RCC but requires significantly more compute as shown Figure 2.
The total savings will depend on the cluster sizes, the number of bytes used to encode each element (i.e., FAISS vector/embeddingg, as well as the size of id numbers in the database. Cluster sizes are often set to vni resulting in log/ [1| = /n log(( (v 1)!) [Johnson et al., 2019]. A vast literature exists on encoding methods for vectors [Chen al., 2010, Martinez et al., 2016, Babenko and Lempitsky, 2014, Jegou et al., 2010. Huijben et al., 2024] with typical values ranging from 8 to 16 bytes for BigANN and come from an external source and have semantics beyond the vector database itself. Alternatively, ids are assigned sequentially taking up log(n) bits each when their only purpose to be stored as sets to represent clustering information. These ids can be removed if vectors are stored with RCC as the clustering information is represented by the relative orderings between objects without the need for ids. Table 2 shows savings for RCC for the setting of Johnson et al. [2019] with & /n clusters.
for SIFTIM. Typically bytes are used store database ids when they

---

Discussion
This work provides an efficient lossless coding algorithm for storing random clusters of objects from arbitrary sets. Our method, Random Cycle Coding (RCC), stores the clustering information in the ordering between encoded objects and does away with the need assign meaningless labels for storage purposes.
random clustering can be decomposed into distinct mathematical quantities, the data set of objects present the clusters (i.e., the union of all clusters), and an equivalence class representing the cluster assignments. For given clustering, the equivalence class contains all possible orderings of the data that have cycles with the same elements as some cluster. The logarithm of the equivalence class size exactly the number of bits needed communicate an ordering of the data points, with the wanted permutation cycles, which we refer to as the order information. This quantity was previously defined by Varshney and Goyal [2006] as the amount of bits required to communicate an ordering of sequence if the multiset of symbols was given, and equaled log n! when there are no repeated symbols. In the cluster case, the order information log II| is strictly less than log n! as the clustering carries partial information regarding the ordering between symbols in the following way: given the clustering, only orderings with the corresponding cycle structure will be communicated.
The savings achieved by RCC equals exactly the assignment information of the data, implying RCC is optimal in terms of compression rate for the probability model shown in Equation (8). The computational complexity of RCC scales with the number of bits recovered by bits-back, and reverts back that of compressing sequence when all clusters are atomic.
The savings for RCC scales quasi-linearly with the cluster sizes, and is independent of the representa- tion size of the data. The experiments on real-world datasets from vector similarity search databases showcases where we think our method most attractive: clusters of data requiring few bytes per element to communicate, where the bits-back savings can represent significant share of the total representation size.
10

---

References
A. Babenko and V. Lempitsky. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 931-935 2014.
E. T. Bell. Exponential polynomials. Annals of Mathematics, pages 258-277, 1934.
Y. Chen, T. Guan, and C. Wang. Approximate nearest neighbor search by residual vector quantization. Sensors,
2010.
T. M. Cover. Elements of information theory. John Wiley & Sons, 1999.
J. Duda. Asymmetric numeral systems. arXiv preprint (rXXiv:0022.0271, 2009.
D. Foata. On the netto inversion number of sequence. Proceedings of the American Mathematical Society, 19(1):236-2444 1968.
B. J. Frey and G. E. Hinton. Free energy coding. In Proceedings of Data Compression Conference- DCC'96, pages 73-81, IEEE, 1996.
D. A. Huffman. A method for the construction of minimum-rreunndany codes. Proceedings of the IRE, 40(9)) 1952.
I. Huijben, M. Douze, M. Muckley, R. van Sloun, and J. Verbeek. Residual quantization with implicit neural codebooks. arXiv preprint arXiv:2401.1473: 2024.
H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE transactions pattern analysis and machine intelligence, 33(1):117-128 2010.
H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg. Searching in billion vectors: re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 861-864. IEEE, 2011.
Johnson, M. Douze, and H. Jégou. Billion-scale similarity search with gpus, IEEE Transactions on Big Data, 7(3):535-547, 2019.
S. Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Martinez, Clement, H. H. Hoos, and J. J. Little. Revisiting additive quantization. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part I1 14, pages 137-153. Springer, 2016.
D. Severo, J. Townsend, A. Khisti, A. Makhzani, and K. Ullrich. Compressing multisets with large alphabets. IEEE Journal on Selected Areas in Information Theory, 2023.
C. Shannon. A mathematical theory communication. The Bell system technical journal,, 27(3): 379 423, 1948.
J. Townsend, T. Bird, and D. Barber. Practical lossless compression with latent variables using bits back coding. arXiv preprint arXiv:1901. 04866, 2019.
L. R. Varshney and K. Goyal. Toward a source coding theory for sets. In Data Compression Conference (DCC106), pages 13-22. IEBE, 2006.
I. H. Witten, R. M. Neal, and J. G. Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520-544 1987.

---

A Python code for RCC
def element_ ltr_c_cococccdeeeeeeeeeeee (state: int, element, precision: int) -> int:
rrr Encodes "element" into the ANS state using codec 11
... definition of codec goes here return next_state
def uniform_ cadee_eoocceeeeeeeeeeeeeeeeee
index cooeccdeeodeeeeeeeeeeeeeeeeeeece (state: int, precision: int) -> (int, int): precision
8 previous_ state state // precision
9 return index, previous_state
def encode (clusterrn set[set]] state: int) int: clustering sorted(map(sorted, clustering), reverse-True)
for cluster in reversed(clustering)) 13
smallest_elle element cluster (luster.pop(0) # pop the first (smallest) element while cluster: Imp Implement ROC: encode remaining elements set precision (elcuutee))
17
index, state uniform, uniform_codec_____. codec_decode
precision)
18
element cluster. Sluster.pop(idde.. pop(index)
state #lement_codee encode (element, state)
state element_codec encode sectaalestteeeemeeee state)
return state
import bisect
def wwwee/eeeeeeddsttaaaaeeeeeeeeeee int, element, preciaion: int):
Decodes "element" from the ANS state using some codec ". definition of codec goes here return element, previous_state
def uniform_ next_state state precision index
coctorrm_cod_______ encode (state: int, index: int, precision: int) int:
10 return next_state
def append_to. clo_strserr_..eeeeee and sort list, element) list:
Insert element into sorted list. The resulting list sorted well. 14 This operation is in-place
ienettiinsottcuuuseesc element) return cluster
18 (state:: int, n: int) -> (list [list] int): clustering = list()
19
mmallest_element float('inf')
while (mapp(een,, clustering)) < loop until all elements element, state
dececdddecdeessstttt (state)
23
if element emallest_element:
24
ttnluntttt_tttt____emeeooaoo cluster append_ popped_too__e cluster cataster_an____ee and_ssrr((ei sort (cluster, element)
index cluster index (element) get inder of element in sorted cluster state uniform_codie encode (state, index, precision=len (clustee)) else:
27
28
cluster [element]
clustering append (cluster)
calllest_elemeee element
return clustering, state
Pseudo-code for encoding (top) and decoding (bottom) a clustering of n elements with our method, Random Cycle Coding (RCC). uniform_ decode samples an integer from state between 0 and precision-11 append_tod to_ cluster and_sord inserts an element into sorted list such that the resulting list is also sorted.
Figure 4:
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contribution the compression algorithm which provably Shannon- optimal, as well as the application to vector databases.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: There is entire section in the paper about the limitations and comparisons to current baselines.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer:
[Yes]
Justification:
There is only one proof and it is short. All assumptions are stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: There models in this paper, only algorithm. All experiments discussed in detail and python code given.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The data already public and the code in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss cttpssccccpbccccccceececcecccccc /ttpg/eeeeeeeeeeemiiieeeee /Cooeeeooiissseeeeeee cessionnoocyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
There are no models in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are models in this paper and the algorithm is provably optimal (the best you can do).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
There are wall-time plots in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https pestps://neet http:///neuuppeeeeeee wwtppbbicc/thiisauiiiiiiiiioieei
Answer: [Yes]
Justification: Yes, does.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper gives lossless compression algorithm. There is no major concern societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: There are no models in this paper. The data is already public from previous work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All python libraries used for compression and plotting are adequately cited, as well as the data. There are no models in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There are no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No human subjects were used in the studies of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects were used in the studies of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "Pcpa7tgSRG", "reviewer": "Reviewer_h1ae", "summary": "The paper introduces Random Cycle Coding (RCC), a method for lossless compression of cluster assignments in data sets. RCC encodes data sequentially, representing cluster assignments as cycles in permutations, which eliminates the need for artificial labels. The method is shown to achieve the Shannon bound in bit savings, and scales quasi-linearly with the largest cluster size. Empirical results show optimal byte savings across a range of cluster sizes for multiple datasets.", "questions": "1. Why does the encode + decode time for RCC in Fig. 2 decrease as 'k' increases?\n\n2. If the elements in each cycle are sorted (line 188) then how can the original order of the elements be recovered? If it cannot be recovered, then is this approach only limited to settings where the ordering of database elements is not important?\n\n3. How is the centroid to cluster mapping information stored? I believe it will be needed to identify the clusters in which to search for the k nearest neighbors in the second stage of FAISS right?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm for encoding cluster assignments is novel and elegantly leverages the properties of clusterings and permutations to achieve theoretically optimal compression.\n\n2. The approach also shows significant savings in experiments including on vector databases which can translate into gains across all machine learning approaches that rely on retrieval from vector databases.", "weaknesses": "Some of the technical details are not clearly explained (see question below) and overall, the details of the approach may be difficult to follow for audiences not familiar with the relevant source coding literature. I would recommend adding an example to illustrate how Algorithm 1 works end-to-end and why it works, either in the main paper or in the appendix, to remedy this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestion. An example of encoding and decoding a cluster assignment has been added to the appendix to further clarify the algorithm.\n\n> Why does the encode + decode time for RCC in Fig. 2 decrease as 'k' increases?\n\nThis can be understood by noting that, in the experiment, as the number of clusters $k$ increases, the number of elements in each cluster $n_i = \\frac{n}{k}$ decreases.\n\nThe total complexity of RCC can be read from Algorithm 1, lines 2 and 3. The subroutine that encodes a single cluster of size $n_i$ (i.e., line 2 of Algorithm 1) has complexity $O(n_i \\cdot \\log n_i) = O(\\frac{n}{k} \\cdot \\log \\frac{n}{k})$. Line 3 encodes a single element, which is very fast, for every cluster, adding complexity $O(k)$. As $k$ increases, more and more time is spent on line 3 than line 2 of Algorithm 1.\n\nThe total complexity of RCC is $O(k + n \\cdot \\log\\frac{n}{k})$. If $k=1$, then all elements are in a single cluster, and the complexity is $O(n \\cdot \\log(n))$. At the other extreme, $k=n$, each element is in its own cluster, and the complexity is $O(n)$. In between these extremes, as $k$ increases, there will be more clusters (more time spent on line 3 of Algorithm 1), but every cluster will be smaller (less time spent on line 2 of Algorithm 1), and the latter is computationally more expensive.\n\nWe will add this discussion to the camera-ready.\n\n> If the elements in each cycle are sorted (line 188) then how can the original order of the elements be recovered? If it cannot be recovered, then is this approach only limited to settings where the ordering of database elements is not important?\n\nThis is correct: the order can never be recovered, but note this is by design. We assume clusters are sets of objects, i.e., unordered collections. The fact that elements have some order is due to the nature of how we represent information on a computer (i.e., memory is inherently sequential).\n\nThis is the case for similarity search databases such as FAISS, for example, where the freedom to reorder vectors in a cluster/voronoi cell, as well as reordering the centroids (as long as it still aligns with the correct cluster).\n\nWe will highlight this point in the camera-ready.\n\n> How is the centroid to cluster mapping information stored? I believe it will be needed to identify the clusters in which to search for the k nearest neighbors in the second stage of FAISS right?\n\nThis is an important practical consideration, which is compatible with RCC. Line 1 in Algorithm 1 sorts the elements according to Foata’s Canonicalization (Definition 3.3). The centroids must be re-ordered to align with the respective centroid.\n\nWe will add a discussion on what quantities we assume can be re-ordered to the introduction in the camera-ready.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hHkJbaORxR", "reviewer": "Reviewer_BkEs", "summary": "This paper proposes a coding scheme for lossless compression of cluster assignments. The proposed coding scheme is based on random order coding (ROC) with bits-back coding. Analysis and experiments show that it outperforms two variants of ROC in complexity and compression rate.", "questions": "See weakness", "limitations": "See weakness", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The presentation and research methodology presented in this paper are good, and a comparison with baseline methods is included. Examples are provided for clear explanation.", "weaknesses": "After carefully reading this work, I believe it is out of the scope of NeurIPS. This work applies the Random Order Coding (ROC) with bits-back coding for encoding clustering assignments. The main contribution is on the way to adapt the ROC to clustering assignment encoding, which does not include any discussion or consideration on the topics listed on NeurIPS 2024 Call For Paper. \n\nAdditionally, the paper does not provide any literature on clustering assignment compression. I am not a database researcher, but is the clustering assignment a significant overhead in practice? According to the author, \"the number of bits used to store the vector embedding ranges from 4 to 16 bytes, while ids are typically stored as 8-byte integers\" It is very unexpected that, in practice, the id takes up more than half of the storage. Could the author provide more references or elaborate more on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> After carefully reading this work, I believe it is out of the scope of NeurIPS. [...] does not include any discussion or consideration on the topics listed on NeurIPS 2024 Call For Paper.\n\nThis work fits in the call for papers under “Infrastructure”, in the sub-category “improved implementation and scalability”. Furthermore, there have been many papers on this exact topic at NeurIPS, in the category of “Probabilistic methods”, as well as at sister conferences such as ICML and ICLR (see references).\n\nThe target application of this compression algorithm is for vector databases, which are widely used in practice for embedding retrieval in foundation models, as well as similarity search, the most famous of which is FAISS [1]. Vector databases provide fast similarity search via efficient KNN search on accelerated hardware (e..g, GPUs). There is an extensive list of applications currently using vector databases such as for augmenting LLMs with memory (see [3] for an extensive discussion); as well as companies providing vector databases as a service such as Pinecone (https://www.pinecone.io/), Milvus (https://milvus.io/), Amazon Web Services (AWS, https://aws.amazon.com/what-is/vector-databases/), Zilliz (https://zilliz.com/), and many others.\n\nFrom a theoretical perspective, the main ideas of this paper advance the line of research on bits-back coding—an approach that was invented and has deep roots in the \"probabilistic methods\" community of NeurIPS; and adapts it to practical settings. See [4, 5, 6, 7, 8, 9, 10,11,12] for papers recently published at NeurIPS, as well as other venues, on bits-back coding\n\nReducing the memory footprint of vector databases is important for many reasons, and has been highlighted in the official documentation of production-level vector databases [2, 3]. We highlight 2 of these reasons. First, it enables the use of better search algorithms in real-time which require more memory to run. Second, similarity search is usually done on batches of queries in practice; and, therefore, reducing the memory footprint of the database index enables us to increase the batch size and speed up the throughput of retrieval.\n\n- [1] https://github.com/facebookresearch/faiss\n- [2] https://github.com/facebookresearch/faiss/wiki/Indexes-that-do-not-fit-in-RAM\n- [3] (The Faiss library)[https://arxiv.org/abs/2401.08281]\n- [4] (ICLR 2019) [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://arxiv.org/abs/1901.04866)\n- [5] (NeurIPS 2021) [Variational Diffusion Models](https://proceedings.neurips.cc/paper/2021/hash/b578f2a52a0229873fefc2a4b06377fa-Abstract.html)\n- [6] (NeurIPS 2021) [Maximum Likelihood Training of Score-Based Diffusion Models](https://proceedings.neurips.cc/paper/2021/hash/0a9fdbb17feb6ccb7ec405cfb85222c4-Abstract.html)\n- [7] (NeurIPS 2019) [Integer Discrete Flows and Lossless Compression](https://proceedings.neurips.cc/paper/2019/hash/9e9a30b74c49d07d8150c8c83b1ccf07-Abstract.html)\n- [8] (NeurIPS 2020) [Improving Inference for Neural Image Compression](https://proceedings.neurips.cc/paper/2020/hash/066f182b787111ed4cb65ed437f0855b-Abstract.html)\n- [9] (ICLR 2020) [HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models](https://arxiv.org/abs/1912.09953)\n- [10] (ICLR 2021) [IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression](https://arxiv.org/abs/2006.12459)\n- [11] (NeurIPS 2019) [Compression with Flows via Local Bits-Back Coding](https://proceedings.neurips.cc/paper/2019/hash/f6e794a75c5d51de081dbefa224304f9-Abstract.html)\n- [12] (NeurIPS 2021) [iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder](https://proceedings.neurips.cc/paper/2021/hash/2e3d2c4f33a7a1f58bc6c81cacd21e9c-Abstract.html)\n- [13] (NeurIPS 2021) [Your Dataset is a Multiset and You Should Compress it Like One](https://openreview.net/forum?id=vjrsNCu8Km) - Best paper award NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications.\n\n> Additionally, the paper does not provide any literature on clustering assignment compression. I am not a database researcher, but is the clustering assignment a significant overhead in practice? [...] It is very unexpected that, in practice, the id takes up more than half of the storage. [...]?\n\nThe size of the index is composed of the number of bits required to represent the ids plus the number of bits required to represent the vectors. Currently, there is a vast literature on lossy compression of vector databases (see [14] and [15] for a survey), which significantly reduces the size of these high-dimensional vectors to a few bytes. In many cases, the vectors can be reduced to less than 8 bytes per vector (note, not *per-dimension*, but 8 bytes to represent the entire vector) while still maintaining search performance useful for many applications (e.g., see Figure 3 of [14] where Deep1M is compressed to less than 8 bytes per vector). In extreme cases, such as [4], Table 2, the authors show that 4 bytes can be enough to maintain some level of recall performance.\n\nWhile lossy vector compression has been reasonably explored, very little to nothing has been done for the indices. Typically, users store custom indices together with the vectors (e.g., in FAISS this is done through the `index.add_with_ids` method where `index` is some inverted index). These indices can be of arbitrary size, and are commonly 32 bit (4 byte) or 64 bit (8 byte) integers. The indices therefore can represent a significant share of the memory required to store these databases.\n\nWe will add a discussion to the introduction during the camera-ready to highlight that the lossy compression of vectors to less than 8 bytes increases the relevance of the index compression.\n\n- [14] (ICML 2024) [Residual Quantization with Implicit Neural Codebooks](https://arxiv.org/abs/2401.14732)\n- [15] https://github.com/erikbern/ann-benchmarks", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lm3ZUrkqXW", "reviewer": "Reviewer_rKbY", "summary": "This paper study the problem of cluster assignments of datasets, the goal of which is encoding datasets along with their cluster information. The authors propose Random Cycle Coding method that utilizes cycle representation of permutation as indicators for cluster. The cycle is formed by a sequence of numbers and it represents a cluster of the data samples corresponding to the numbers in the cycle. \nIt is shown that the method outperforms other baseline methods while requires less computational complexity and memory.", "questions": "1. What are the differences between RCC and ROC in cluster assignment problem? From my understanding, RCC stores cluster information by permutation. Then, how ROC-1 and ROC-2 store the clusterings? \n2. Is ROC only existing baseline method?\n3. To leveraging permutation, it seems sequential stacking is required, and parallel stacking or decoding is not allowed. If it is, are there any problems or disadvantages caused by not using parallel operations? \n4. When extremely many data samples are stored, it seems that retrieving a cluster information for a data sample requires decoding every data sample if the sample is stacked first. Is this correct?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea in employing the cycle representation of permutation to assign data to cluster is simple yet effective. The authors formalize the idea and show the effectiveness of their proposed method. The performance of the method is consistently outperforming others.", "weaknesses": "Although the main idea is simple to understand, it is quite hard to grasp the underlying techniques like ANS, ROC and bit-back coding from the paper. This paper compares their method only with ROC, which I think is not sufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> What are the differences between RCC and ROC in cluster assignment problem? From my understanding, RCC stores cluster information by permutation. Then, how ROC-1 and ROC-2 store the clusterings?\n\nThat is correct, RCC stores the cluster information in the disjoint cycles of the permutation. ROC-1 and ROC-2 compress each cluster separately as a set of objects, so the clustering assignment is implicitly stored by knowing which set you are decoding.\n\n> Is ROC only existing baseline method?\n\nTo the best of our knowledge, there is no existing method that addresses compression of clustering assignments. However, a cluster can be seen as a collection of disjoint sets. It is therefore natural to adapt set compression algorithms, such as ROC, to compress clusters.\n\n> To leveraging permutation, it seems sequential stacking is required, and parallel stacking or decoding is not allowed. If it is, are there any problems or disadvantages caused by not using parallel operations?\n\nThis is correct: RCC does not allow “random access” to elements in the clusters. This is a limitation of all bits-back coding techniques. We will highlight this point in the camera-ready.\n\n> When extremely many data samples are stored, it seems that retrieving a cluster information for a data sample requires decoding every data sample if the sample is stacked first. Is this correct?\n\nThis is partially correct. Since encoding requires randomizing the order, the element you are searching for can be in any position of the stack with equal probability. However, it is not necessary to decode the entire stack to retrieve the element, decoding can be stopped as soon as the element is found.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lI8Fh49DPB", "reviewer": "Reviewer_CCTj", "summary": "## Summary\n* This paper propose an entropy coding technique named RCC, which is the first one to achieve the optimal rate for cluster assignment. Theoretical and empirical results show that the rate saving and speed up of the proposed approach over previous suboptimal work ROC is evident when the number of cluster is close to sample size.", "questions": "## Questions\n* What is the common practical #clusters compared with #samples? Is that common to have #clusters close to #samples?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "## Strength\n* The paper presents a entropy coding technique that achieve optimal rate for cluster assignment, which is a step forward the previous work on multiset.", "weaknesses": "## Weakness\n* Despite its theoretical optimality, the bitrate saving of RCC over ROC is a bit of marginal, especially when the number of clusters are not so large compared with number of elements. For a less extreme case when number of cluster is much smaller than number of elements (~\\sqrt{n}), the difference between RCC and ROC can be quite small. (See Fig 3, n=10^7, cluster = 10^7 and cluster = 10^3.5).\n* Similarly, the RCC approach has obviously better complexity compared with ROC, only when we have number of clusters close to number of samples. For the case when #cluster ~\\sqrt{n}, the difference of temporal complexity can be less significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the relevant practical questions.\n\nMost questions center around a comparison to ROC. Indeed there is a regime where the compression gain our method provides, RCC, is marginal over ROC (when $k$ is small). However, there are regimes where the gain is substantial (when $k$ is large). In all regimes, our method outperforms ROC while also being faster.\n\nGiven that RCC provides both better compression rates and, guaranteedly, better wall-times, as well memory and computational complexities, the message we would like to highlight is: **in all regimes of $k$, there is no reason to use ROC over our method.**\n\n> Despite its theoretical optimality, the bitrate saving of RCC over ROC is a bit of marginal, especially when the number of clusters are not so large compared with number of elements. For a less extreme case when number of cluster is much smaller than number of elements (~\\sqrt{n}), the difference between RCC and ROC can be quite small. (See Fig 3, n=10^7, cluster = 10^7 and cluster = 10^3.5).\n\nThe performance of RCC is comparable to that of ROC-2, but RCC significantly outperforms ROC-1. In the regime of $k \\approx \\sqrt(n)$, where $k$ is the number of clusters, the RCC can provide gains of up to 20% with respect to ROC-1 on benchmark datasets such as SIFT1M.\n\n> Similarly, the RCC approach has obviously better complexity compared with ROC, only when we have number of clusters close to number of samples. For the case when #cluster ~\\sqrt{n}, the difference of temporal complexity can be less significant.\n\nIndeed RCC is always better, both in terms of compression ratio and speed of execution, than ROC for any configuration of clusters. The difference in performance diminishes as the number of clusters decreases, and achieves equality at the extreme $k=n=1$ where all elements are in the same set/cluster. For the typical scenario of vector databases, where $k \\approx \\sqrt(n)$, RCC is at least 20% faster (according to the experiments in Figure 2) than ROC, while achieving the same or better compression ratio.\n\n> What is the common practical #clusters compared with #samples? Is that common to have #clusters close to #samples?\n\nIn FAISS [1] the practical regime is $k = c \\cdot \\sqrt(n)$, where $c$ is some constant. The actual value will depend on the specific nature of the database and the algorithm used to perform vector compression.\n\nWhile this regime for $k$ is the desired one, in practice, there are distribution shifts that happen in production. Initially, the assignment algorithm, i.e., the algorithm that decides where a new vector should be placed in the database, is trained on some training set targeting $k = c \\cdot \\sqrt(n)$. During deployment, when a new vector needs to be added, if the real-world distribution changes, there is no guarantee that this target will be met. The number of clusters can drift over time to have significantly more, or less, cluster. RCC provides a way to robustly compress the database, irrespective of this distribution shift, while ROC does not.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jMQtbaM9Pr", "reviewer": "Reviewer_MJQw", "summary": "This paper proposes the random cycle coding that achieves optimal rate by bits-back coding techniques for cluster assignments. In addition, the newly proposed algorithm requires less computing resources, making it more practical.", "questions": "This paper stresses the application in cluster assignments. Is there any other potential application? What is the special feature in cluster assignment that is compatible with RCC?", "limitations": "No. The limitations are not discussed explicitly.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "For the cluster assignments, this paper proposes an optimal compression coding by bits-back coding techniques. In the coding view, the result is significant due to the optimal property. The RCC algorithm needs less computing and memory costs, making it more practical.", "weaknesses": "This paper borrows bits-back coding techniques and random order coding, making this paper quite incremental in the view of techniques. The difficulty in combing these two techniques is not clearly presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> This paper borrows bits-back coding techniques and random order coding, making this paper quite incremental in the view of techniques. The difficulty in combing these two techniques is not clearly presented.\n\nRCC is a very different algorithm from ROC.\n- ROC is a cluster-compression method, and was readapted to be used as baselines, as there are currently no baselines for optimal cluster compression.\n- ROC is the only existing optimal set compression algorithm, to the best of our knowledge, while RCC compresses arbitrary clusters, or partitions, of datapoints. \n- RCC efficiently maps each possible partitioning of datapoints to a subset of permutations with a common cycle structure. ROC does not in any way utilize the cycle structure of permutations to communicate information.\n\n\nThe fact that RCC can re-use ROC is a feature and not a limitation of the contribution. A significant effort was made to understand and bridge both methods, so that RCC could be built on top of the efficient implementations available for ROC.\n\n> This paper stresses the application in cluster assignments. Is there any other potential application? What is the special feature in cluster assignment that is compatible with RCC?\n\nIn its most general form, RCC is an algorithm for compressing random partitions of arbitrary sets (see [1] for background). The insight provided by this paper is that it is possible to map cluster assignments to the cycle structure of permutations, where each disjoint cycle defines one of the sets in the cluster. \n\nWe will add an example to the appendix highlighting how cycles can be used to store the information of cluster membership for arbitrary data.\n\n[1] https://www.stat.uchicago.edu/~pmcc/pubs/partition10.pdf", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of compressing cluster assignments of arbitrary data sets. In other words, given that a clustering algorithm was run on a dataset and partitioned the datapoints into clusters, the proposed method compresses the clustering assignment information (the cluster labels). The paper proposes a compression algorithm called Random Cycle Coding (RCC), which encodes assignment information by viewing the clusters as cycles of a permutation (with respect to the natural ordering of the objects), and then "canonizes" the ordering within clusters and between the clusters. Experiments compare the performance of RCC with a similar method (but not specialized for clustering) called ROC. Practical gains over ROC are achieved when the number of clusters is large (e.g., ~sqrt{n}).

The reviewers agree that the proposed algorithm is elegant and interesting. RCC is faster than ROC and provides some compression gains (although only for very large values of k).
Decision: Accept (poster)