Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding

Authors: daniel  severo
ashish  khisti
alireza  makhzani
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 17:25:13

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.

Main paper: 
 introduction: 
 A clustering is a collection of pairwise disjoint sets, called clusters, used throughout science and engineering to group data under context-specific criteria. A clustering can be decomposed conceptually into two parts of differing nature. The data set, created by the set union of all clusters, and the assignments, indicating which elements belong to 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 as a fundamental problem in modern vector similarity databases such as FAISS [Johnson et al., 2019] . FAISS is a database designed to store vectors of large dimensionality, usually representing pre-trained embeddings, for similarity search. Given a query vector, FAISS returns a 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 a coarse and fine grained set of database vectors. The database undergoes a training phase where vectors are clustered into sets and assigned a representative (i.e., a centroid). FAISS first selects the k ′ -nearest clusters, k ′ < k, based on the distance of the query to the centroids, and then performs an exhaustive search within them to return the approximate k-nearest neighbors.The cluster assignments must be stored to enable cluster-based approximate searching. In contrast to a class, a cluster is distinguishable only by the elements it contains, and is void of any labelling. However, cluster assignments are often stored alongside the data set in the form of artificially 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 Figure 1 : High-level description of our method, Random Cycle Coding (RCC). RCC encodes the clustering ( X , Π) as cycles in the permutation σ induced by the relative ordering of objects. Left: Indices represent the rankings of objects in X according to the total ordering of X . Middle: One of two permutations will be randomly selected with bits-back coding to represent the clustering (σ, shown in cycle-notation). Then, Foata's Bijection is applied to yield σ ′ , shown in line-notation, which is encoded into the ANS stack. Right: The final ANS stack containing σ ′ in line-notation. from 4 to 16 bytes, while ids are typically stored as 8-byte integers. Therefore, labelling, for the sake of clustering, can represent the majority of bits spent for communication and storage in a 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 as 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 no training or machine learning techniques.An overview on lossless compression, permutations, and bits-back coding is given in Section 2. Our method is presented and analyzed in Section 3. To the best of our knowledge, no current method exists to optimally store cluster assignments. In Section 4 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.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 is the compression algorithm which is provably Shannonoptimal, 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 in 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 as long as it is clear that these goals are not attained by the paper. 
lossless compression: 
 Lossless compression aims to find a code C : X → {0, 1} ⋆ for an infinite i.i.d. sequence of elements X (i) ∼ P X that can be decoded with perfect fidelity. Lossless decoding requires restricting C such that the extended code C(X (1) )C(X (2) ) . . . , created via concatenation, is uniquely decodable. It is known that E X∼P X [C(X)] ≥ H(P X ) for any uniquely decodable code, and any code with average-length close to H(P X ) must obey C(x) ≈ -log P X (x) [Shannon, 1948 , Cover, 1999] . It is possible to construct C using entropy coders such as Asymmetric Numeral Systems [Duda, 2009] , Arithmetic Coding [Witten et al., 1987] , or Huffman Codes [Huffman, 1952] .A common way of designing efficient codes is to guarantee the code-word C(x) carries some meaningful semantics for x that allows for an efficient implementation. Semantic codes can be constructed by introducing an intermediate sequence of random variables Z n , acting as a proxy for X 1 , which is entropy coded autoregressively in n steps. The code-word for x is the binary representation of the final state of the chosen entropy coder (e.g., ANS [Duda, 2009] ). Unfortunately, semantic entropy coding can lead to sub-optimal performance due to the non-uniqueness of the mapping between X and Z n , 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 ∈ N 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-likelihood), 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 a stack-like fashion. Symbols are decoded in reverse order in which they where encoded. Due to this stack-like 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 s (see Townsend et al. [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.Bits-back Coding [Frey and Hinton, 1996, Townsend et al., 2019] is an entropy coding method for latent variable models P X,Z . The bit-rate achieved is equal to the cross-entropy E X [-log P X (X)], where the expectation is taken with respect to the true data distribution of X, despite not having direct access to the marginal P X needed for entropy coding. Given the posterior P Z | X , prior P Z , and conditional likelihood P X | Z of the model, bits-back coding using ANS to perform invertible sampling from P Z | X to obtain Z. Then, X is encoded with P X | Z , conditioned on the sampled Z. Finally, Z is encoded with the prior P Z . Decoding from the stack reduces the ANS integer state by log P Z | X while encoding increases it by -log P Z P X | Z , resulting in a net increase equal to the cross-entropy. An approximate posterior can be used when the exact posterior P Z | X is not available, resulting in the net increase being equal to the Negative Evidence Lower-Bound (NELBO) [Townsend et al., 2019] .ROC [Severo et al., 2023] is an algorithm for losslessly compressing multisets2 . A sequence can be seen as a multiset, representing the frequency count of symbols, together with a 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 Q Z | X = P Z | X . The exactness of the posterior implies the number of bits used by ROC to encode the multiset is equal to the cross-entropy of the multiset with respect to the true data distribution.ROC applies a 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 i times, ROC saves exactly -log P Z | X = log n n1,...,n k ≤ log(n!) bits, where the quantity in parentheses is the multinomial coefficient.A permutation, in this work, is a bijective function σ : [n] → [n] used to define arrangements of elements from arbitrary sets. Permutations are usually expressed in one-line notation σ = [i 1 , i 2 , . . . , i n ] where σ(j) = i j . The symmetric group S n on n elements is the set of all permutations of [n].A cycle (c 1 . . . c k ), of a permutation σ, is the sequence constructed from the repeated application of σ, to some elementc 1 ∈ [n], until c 1 is recovered, i.e., c k+1 = c 1 , c i = σ(c i-1 ), for i ≥ 2.Example 2.1. The cycles of σ = [3, 1, 2, 5, 4] are 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 σ 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 c 1 1 2 3 4 5 cycle (1 3 2) (2 1 3) (3 2 1) (4 5) (5 4) until all elements appear in exactly one cycle. Concatenate cycles to form the representation. Every permutation has a unique representation through the concatenation of disjoint cycles. For example, 3, 1, 2, 5, 4] = (1 3 2)(4 5),  (1)σ = [where the right-hand side is called the cycle notation of σ. Lemma 2.2 (Foata's Bijection [Foata, 1968] ). The following sequence of operations defines a bijection between permutations on n elements. Write the permutation in disjoint cycle notation such that the smallest element of each cycle appears first within the cycle. Order the cycles in decreasing order based on the first/smallest element in each cycle. Remove all parenthesis to form the one-line notation of the output permutation.Example 2.3. Applying the steps in the construction of Foata's bijection to [3, 1, 2, 5, 4] = (3 2 1)(5 4)yields (1 3 2)(4 5) → (4 5)(1 3 2) → [4, 5, 1, 3, 2].Cycles can be recovered by scanning from left to right and keeping track of the smallest value.Question: Does the paper discuss the limitations of the work performed by the authors?Justification: There is an entire section in the paper about the limitations and comparisons to current baselines.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 n = (X 1 , . . . , X n ) be a sequence of random variables X i with common, but arbitrary, alphabet X . Throughout we assume that a total ordering can be defined for X , i.e., elements of the set can be compared and ranked/sorted according to some predefined criteria (e.g., lexicographical ordering).We assume no repeats happen in 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 n are grouped into pair-wise disjoint sets known as clusters. Clusters can be represented by a collection of indicator random variables Π = (Π ij ) 1<i<j<n where Π ij = 1 if X i , X j are in the same cluster and Π ij = 0 otherwise. Conditioned on the sequence X n = x n the clustering Π defines a partition of the data set X = {x 1 , . . . , x n }. The size of the alphabet of Π is 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 irrelevant 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 a particular ordering such that it implicitly encodes the clustering information.We associate a permutation σ x n to each of the possible n! orderings of X based on sorting. Let S n ( X ) be the set of all possible orderings of X , and s n a reference sequence created by sorting the elements in X according to the total ordering of X ,EQUATIONEQUATIONFor any x n ∈ S n ( X ), the induced permutation σ x n is defined as that which permutes the elements of the reference s n such that x n is obtained. Under this definition the permutation can also be constructed by directly substituting x i for its ranking in X .The induced permutations allow us to redefine Π as a random equivalence class taking on values in the quotient set, S n ( X )/∼, of the equivalence relation described next. Note the quotient set is finite even if X is uncountable as only the relative ordering between elements is needed to define the equivalence relation.Definition 3.1 (Cycle-Cluster-Equivalence). Two sequences in S n ( X ) are equivalent (∼) if the disjoint cycles of their induced permutations contain the same elements. Given a sequence, two 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 x n = (4, 6, 2, 8) and z n = (6, 2, 4, 8) induce permutations σ [3, 1, 2, 4] . The sequences are equivalent as the disjoint cycles of the induced permutations contain the same elements: σ x n = (4)(1 2 3), σ z n = (4)(1 3 2). For both sequences, elements 2, 4, and 6 are in the same cluster, while 8 is in a cluster of its own. The partition, viewed as an equivalence class, is equal to Π = {x n , z n }, as there are no other permutations over X that are equivalent to the two shown.x n = [2, 3, 1, 4] and σ z n =Given ( X , Π), Random Cycle Coding (RCC) uses bits-back coding to send the elements of X in an ordering which corresponds to a sequence in Π. The receiver decodes the elements X i , in the order sent, and recovers Π by computing the cycles of the induced permutation. The clustering information Π is communicated via the cycles of the permutation. See Figure 1 for a high-level description.Every sequence in Π maps to the same clustering over X . The log of the number of elements in the equivalence class equals the redundancy discussed in Section 2.1, which is known to beEQUATIONwhere n i is the number of elements in the i-th cycle of the induced permutation. An optimal bits-back method must remove exactly log|Π| bits from the stack during encoding. RCC achieves these savings by selecting an element from X , using an ANS decode operation, and then encoding it onto the stack.Interleaving decoding/sampling and encoding avoids the initial bits issue [Townsend et al., 2019] resulting from the initially empty ANS stack.Random Order Coding [Severo et al., 2023] (ROC) performs a similar procedure for multiset compression where elements are also sampled without replacement from X . However, there, the equivalence classes consist of all permutations over X , and therefore sampling can 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 Bijection [Foata, 1968] . Definition 3.3 (Foata's Canonicalization). The following steps map all sequences in the same equivalence class, x n ∈ Π, to the same canonical sequence c n ∈ Π. 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 on the first (i.e., smallest) element, in descending order. Example 3.4. The set composed of permutations σ = (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 5)(1 3), which is equal to σ.Algorithm RCC encodes a 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 a 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. Permuting the remaining elements in the cycle spans all permutations in Π. For the i-th cluster with n i elements the savings from encoding n i -1 elements with ROC is equal to log((n i -1)!). The total savings is equal to (4), implying RCC saves log|Π|.The probability model Q Π | X is indirectly defined by the savings achieved by RCC. The set of elements and clustering assignments ( X , Π) are encoded via a sequence x n ∈ Π. We can assume some lossless source code is used for the data points, requiring -log Q X n (x n) bits to encode the sequence. The cost of encoding the dataset and cluster assignments equals the cost of encoding a sequence minus the discount given by bits-back,-log Q X ,Π ( X , Π) = -log Q X n (x n ) -log|Π|.(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,EQUATIONFrom this, we can write,EQUATIONThe implied probability model only depends on the cluster sizes, and assigns higher likelihood when there are few clusters with many elements,EQUATIONwhere n i is the size of the i-th cluster, and k the total number of clusters.Complexity The complexity of RCC will vary significantly according to the number of clusters and elements. Initializing RCC requires sorting elements within each cluster, which can be done in parallel, followed by a sort across clusters. ROC is used as a sub-routine and has both worstand average-case complexities equal to Ω(n i log n i ) for encoding and decoding the i-th cluster. The total computational complexity of our method, RCC, adapts to the size of the equivalence class: Ω ( i n i log n i ) = Ω(log|Π|). When only one permutation can represent the cluster assignments, i.e., n = k, implying log|Π| = 0, then RCC has the same complexity as compressing a sequence: Ω(n). Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The data is already public and the code is in the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 a 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 i !) to the bits-back savings of ROC, resulting in a reduction in bit-rate ofEQUATION)where k is the number of clusters,N i = i-1j=1 n j counts the number of encoded elements before step i, and log(n -N i ) is the cost of encoding the size of the i-th cluster. The gap to optimality increases with the number of clusters, while RCC is always optimal as it achieves log|Π| for any configuration of elements and clusters.ROC-2 This variant views the clusterings as a set 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 of this step scales quasi-linearly with the number of clusters, Ω(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 isEQUATION)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 to 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 1 to n, which explains why it achieves a sub-optimal rate savings. 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. 
minimum and maximum achievable savings: 
 In applications targeted by our method (see Section 5.3) the cluster size is set according to some budget and elements are allocated into clusters via a training procedure. For a fixed number of elements (n) and clusters (k) the savings for ROC-1, ROC-2, and RCC will depend only on the cluster sizes (n 1 , . . . , n k ). We empirically analyzed the minimum and maximum possible savings as 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,i n i !, constrained to i n i = n and n i ≥ 1. The maximum is achieved when n -k elements fall into one cluster, n j = n -k + 1, and all others are singletons: n i = 1 for i ̸ = j. Savings are minimized when all clusters have roughly the same size:n i = (n ÷ k) + 1{i ≤ n mod k} 3 .All methods provide similar savings when k ≪ 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-1 achieving negative savings when the number of clusters k is large. RCC savings converge to 0 bits as the number of clusters approaches the number of elements, as expected. As k approaches n, ROC-2 also suffers from negative savings, but the values are negligible compared to those of ROC-1.Figure 2 shows the total encoding plus decoding time as a function of number of elements and clusters. RCC outperforms both variants of ROC in terms of wall-time by a 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|Π|. ROC-2 is slower than ROC-1 due to the extra bits-back step needed to select clusters with ANS.We experimented applying ROC and RCC to FAISS [Johnson et al., 2019] databases of varying size. Results are shown in Table 1 . Scalar quantization [Cover, 1999 , Lloyd, 1982] 1 . For external ids, 8 bytes are added to 1 8n log|Π| to compute the total size per element, as well as to the cost under RCC. Meanwhile, log(n) bits are added to 1 8n log|Π| 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 a full discussion. 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 in Figure 2 .The total savings will depend on the cluster sizes, the number of bytes used to encode each element (i.e., FAISS vector/embedding), as well as the size of id numbers in the database. Cluster sizes are often set to √ n resulting in log|Π| = √ n log(( √ n -1)!) [Johnson et al., 2019] . A vast literature exists on encoding methods for vectors [Chen et 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 4 to 8 for SIFT1M. Typically 8 bytes are used to store database ids when they 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 is 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 k ≈ √ n clusters. 
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 to assign meaningless labels for storage purposes.A random clustering can be decomposed into 2 distinct mathematical quantities, the data set of objects present in the clusters (i.e., the union of all clusters), and an equivalence class representing the cluster assignments. For a 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 is exactly the number of bits needed to 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 a 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|Π| 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 to that of compressing a sequence when all clusters are atomic.The savings for RCC scales quasi-linearly with the cluster sizes, and is independent of the representation size of the data. The experiments on real-world datasets from vector similarity search databases showcases where we think our method is most attractive: clusters of data requiring few bytes per element to communicate, where the bits-back savings can represent a significant share of the total representation size.A Python code for RCC # Insert element into sorted list. The resulting list is sorted as well.# This operation is in-place bisect.insort(cluster, element) uniform_codec_decode samples an integer from state between 0 and precision-1. append_to_cluster_and_sort inserts an element into a sorted list such that the resulting list is also sorted.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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 of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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?Justification: There are no 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Yes, it 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a lossless compression algorithm. There is no major concern on 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or 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 nor research with human subjects. • Depending on 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).From here on we drop the superscript on X (i) and focus on a single X, without loss of generality.Multisets are sets that allow repetition of elements but have no ordering between elements.÷ represents integer division, n mod k is the remainder, and 1{} is the indicator function that evaluates to 1 if the expression is true. 
 
 Appendix:  


Decision: 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).

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Why does the encode + decode time for RCC in Fig. 2 decrease as 'k' increases?

2. 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?

3. 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

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? 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?
questions: questions: See weakness
limitations: limitations: See weakness
paper_summary: paper_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. 
It is shown that the method outperforms other baseline methods while requires less computational complexity and memory.
strength_weakness: strength_weakness: 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.
questions: 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? 
2. Is ROC only existing baseline method?
3. 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? 
4. 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: limitations: N/A
paper_summary: paper_summary: ## Summary
* 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.
strength_weakness: strength_weakness: ## Weakness
* 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).
* 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.
questions: questions: ## Questions
* What is the common practical #clusters compared with #samples? Is that common to have #clusters close to #samples?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: No. The limitations are not discussed explicitly.

Comments: title: Thank the authors for the rebuttal.
Response to rebuttal
comment: The rebuttal addresses my major concerns and I raise the score accordingly.
Thank you for addressing my concerns. As I had already recommended accepting the paper, I will keep my score.
Thank the authors for the rebuttal. The rebuttal answers my questions, and I have no further questions. Accordingly, I will raise my score.
Thanks for answering my questions. I have no further comments and questions. I will raise my rating.