Clustering Embedding Tables, Without First Learning Them
Authors: Henry Ling-Hei Tsang
Thomas Dybdahl Ahle
Venue: Submitted to ICLR 2023 (2023)
Keywords: Clustering
Sketching
Recommendation Systems
Embeddings
Sparse Matrices

Abstract: Machine learning systems use embedding tables to work with categorical features. These tables may get extremely large in modern recommendation systems, and various methods have been suggested to fit them in memory.

Product- and Residual Vector Quantization are some of the most successful methods for table compression. They function by substituting table rows with references to ``codewords'' picked by k-means clustering. Unfortunately, this means that they must first know the table before compressing it, thus they can only save memory at inference time, not training time. Recent work has employed hashing-based approaches to minimize memory usage during training, however the compression obtained is poorer than that achieved by ``post-training'' quantization.

We demonstrate that combining hashing and clustering based algorithms provides the best of both worlds. By first training a hashing-based ``sketch'', then clustering it, and then training the clustered quantization, our method may achieve compression ratios close to those of post-training quantization with the training time memory reductions of hashing-based methods. We prove that this technique works rigorously in the least-square setting.

CLUSTERING EMBEDDING TABLES, WITHOUT First LEARNING THEM.
Anonymous authors Paper under double-blind review
ABSTRACT
To work with categorical features, machine learning systems employ embedding tables. These tables can become exceedingly large in modern recommendation systems, necessitating the development of new methods for fitting them in memory, even during training.
Some of the most successful methods for table compression are Product- and Residual Vector Quantization (Gray & Neuhofi 1998). These methods replace table rows with references to k-means clustered "codewords." Unfortunately, this means they must first know the table before compressing only save memory during inference, not training. Recent work has used hashing- based approaches minimize memory usage during training, but the compression obtained is inferior to that obtained by "post-training" quantization.
they
We show that the best of both worlds may be obtained by combining techniques based on hashing and clustering. By first training hashing- based "sketch", then clustering it, and then training the clustered quantization, method achieves compression ratios close to those of post-training quantization with the training time memory reductions of hashing- based methods.
We show experimentally that our method provides better compression and/or accuracy that previous methods, and we prove that our method always converges to the optimal embedding table for least-squares training.
INTRODUCTION
Machine learning can model variety of data types, including continuous, sparse, and sequential features. Categorical features are especially noteworthy since they necessitate an "embedding" of (typically vast) vocabulary into smaller vector space in order to facilitate further calculations. IDs of different types, such as user IDs, post IDs on social networks, video IDs, or IP addresses in recommendation systems, are examples of such features.
Natural Language Processing is another prominent use for embeddings (usually word embeddings such Mikolov et al. 2013), however in NLP the vocabulary can be significantly reduced by consid- ering "subwords" or byte pair encodings". In recommendation systems like Matrix Factorization or DLRM (see fig. 2 is typically not possible factorize the vocabulary this way, and embedding tables end up very big, requiring hundreds of gigabytes of GPU memory (Naumov et al.) 2019). This effect forces models be split across may GPUs which is expensive and creates a communication bottleneck during training and inference.
The traditional solution has been hash the IDs down manageable universe size using the Hashing Trick (Weinberger et al. 2009), and accepting that unrelated IDs may wind up with the same representation. Too aggressive hashing naturally hurts the ability of the model distinguish its inputs by mixing up unrelated concepts and reducing model accuracy.
Another option is to quantize the embedding tables. Typically, this entails rounding each individual parameter to 4 or 8 bits. Other quantization methods work in many dimensions the same time, such as Product Quantization and Residual Vector Quantization. (See Gray & Neuhoff (1998) for survey of quantization methods.) These multi-diimnniooal methods typically rely clustering (like k k-means) to find a set of representative "code words" to which each original ID is assigned. For example, vectors representing "red", "orange" and "blue" may be stored simple "dark orange"

---

Initial random table with 2K rows.
Concatenate with new random table
After training for epoch.
Expand rows using hashing.
Cluster table to rows
Repeat from step 1...
Two random hash functions
Single pointer to Nearest cluster center
Figure I: Single iteration of Clustered QR. Starting from random embedding table, each ID is hashed to vector each of 2 small tables (left), and the value (shown in the middle) is taken to be the mean of the vectors. After training for epoch, the large (implicit) embedding table is (sub-sampled and) clustered. This leaves a new small table which similar IDs are represented by the same vector. We can choose combine the cluster centers with new random table (and new hash function), after which the process can be repeated for an increasingly better understanding of which ID should be combined.
and "blue" with the two first concepts pointing to the same average embedding. See fig, for an example. Even in the theoretical literature on optimal vector compression, such clustering plays crucial role (Indyk & Wagner 2022). All these quantization methods share one obvious drawback compared hashing: the model only quantized after training, thus memory utilization during training is unaffected. (Note: While is common to do some "finetuning" of the model after, say, product quantization, the method remains primarily a "post-training" approach.)
Recent authors have considered more advanced ways to use hashing to overcome this problem: Tito Svenstrup et al. (2017); (). [hi et (2020): [Dsaa al. (2022); Yin al. (202T): Kang et al. (202T). The common theme has been using multiple hash functions which allow features to take different representations with high probability, while still mapping into a small shared table parameters. While these methods work better than the hashing trick in some cases, they still fundamentally mix up completely unrelated concepts in a way that introduces large amounts of noise into the remaining machine learning model.
Clearly there is an essential difference between "post-training" compression methods like Product Quantization which utilize similarities between concepts and "during training" techniques based on hashing, which are forced to randomly mix up concepts. This paper's 's key contribution is to bridge that gap: We present novel compression approach we call "Clustered Compositional Embeddings" (or CQR for short) that combines hashing and clustering while retaining the benefits of both methods. By continuously interleaving clustering with training, we train recommendation models with accuracy matching post-training quantization, while using fixed parameter count and computational cost throughout training, matching hashing based methods.
In spirit, our effort can be likened to methods like Rigl. (Evci et al. 2020), which discovers the wiring of a sparse neural network during training rather than pruning dense network post training. Our work can also be seen form of "Online Product Quantization" though prior work like Xu et al. (2018) focused only on updating code words already assigned to concept. Our goal is more ambitious: We want to learn which concepts to group together without knowing the "true" embedding for the concepts.
Why is this hard? Imagine you training your model and at point decide the same vector for IDs and j. For the remaining duration of the training, you can never distinguish the two IDs again, and thus any decision you make is permanent. The more you cluster, the smaller your
2

---

Numerical features
Bottom MLP
Top MLP
Click prob- ability
Categorical feature
Embedding table
Pairwise Interaction
Categorical feature M
Embedding table M
Figure 2: Typical Recommendation System Architecture: The DLRM model Naumov et al. (0019) embeds each categorical feature separately and combines the resulting vectors with pair- pair-wise wise dot
products. Other architectures different interaction layers single embedding table for all categorical features, but the central role the embedding table universal.
table gets. But interested in keeping constant number of parameters throughout training, while continuously improving the clustering.
In summary, our main contributions are:
We show that it is possible use clustering at training time, even though don't don't have memory enough to learn or even store the concepts be clustered.
Our method bridges the state of the for quantizing "post-training" (clustering based methods) and during training (hashing methods).
We show experimentally that our technique allows training the Deep Learning Recommen- dation System (DLRM) baseline accuracy with less than 50% of the table parameters of the best previously suggested methods.
We prove theoretically that a version of our method always succeeds in finding the optimal embedding table in the context of Least Squares learning.
BACKGROUND AND RELATED WORK
We show how most previous work table compression can be seen in the thcoretical framework of linear dimensionality reduction. This allows us to generalize many techniques and guide our intuition on how to choose the quality and number of hash functions in the system.
We omit standard common preprocessing tricks, such as weighting entities by frequency, using separate tables and precision for common uncommon elements, or completely pruning rare entities. We also don't cover the background of "post training" quantization, but refer to the survey, Grry & Neuhoff (1998). Finally, we keep things reasonably heuristic, but for deep theoretical understanding of metric compression, we recommend Indyk & Wagner 2022)
2.1 EMBEDDING TABLES AS LINEAR MAPS
embedding table is typically expressed as a tall skinny matrix T RR xd2, where each ID i e [d1] is mapped to the i-th row, T'i). Alternatively, i can be expressed as one-hot row-vector e E 13d: which case T = e,T' e d2
Most previous work in the area of table compression is based on the idea of sketching: We introduce a (typically sparse) matrix E {0, 1]dd x and a dense matrix E R where << d1, and take T HMM. In other words, to compute T[ compute (c,H)M. Since H and e, are both sparse, this requires very little memory and takes only constant time. The vector e, e R is called "the sketch of i" and M is the "compressed embedding table" that is trained with gradient descent.

---

16
(a) The Hashing Trick: Each ID is hashed to one loca- tion in table (here with 1000 rows) and it is assigned the embedding vector stored at the location. Many IDs are likely to share the same vector.
(b) Hash Embeddings: Each ID is hashed to two rows. one per each table, and its embedding vector is assigned to be the sum those two vectors. Here, we use two separate tables unlike in Tito Svenstrup et al. (2017).
Figure 3: The Hashing Trick and Hash Embeddings shown side by side with equal amount of parameters.
In this framework we can also express most other approaches to training-time table compression:
The Hashing Trick (Weinberger et al. 2009) is normally described by a hash function h : [di] - [k), such that i is given the vector M [h(),, where M is a table with just << di rows. Alternatively we can think of this trick as multiplying e; with random matrix H E fo. 1] xk which has exactly one 1 in each row. Then the embedding of is M[h(i) = M,HM where HM Rd4
Hash Embeddings TTito Svenstrup et al., 2017) map each ID E to the sum of a few table rows. For example, if i is mapped to two rows, then its embedding vector is = Mh,, (i) M (i)). Using the notation of И e {0, 13 1mmxx, one can check that this corresponds to each row having exactly two Is. In the paper, the authors also consider weighted combinations, which simply means that the non-zero entries H can be some real numbers.
Compositional embeddings (or QR embeddings, Shi et al. 2020 define (1) = |t/pl and h2( = mod p for integer p. and then combines T [i) and (() in various ways. As mentioned by the authors, this choice is, however, not of great importance, and more general hash functions can also used, which allows for more flexibility in the size and number of tables. Besides using sums, like Hash Embeddings, the authors also propose element- wise multiplication! and concatenation. Concatenation [T [T),, Th2 (i)]] can again be described with matrix H E (0, 1 x where each row has exactly one 1 in the top half of H and one in the bottom half of H, as well as a block diagonal matrix M. While this restricts the variations in embedding matrices T that are allowed, we usually compensate by picking larger m, so the difference in entropy is not much different from Hash Embeddings, and the practical results very similar as well.
ROBE embeddings (Desai et al., 2022) are essentially compositional embeddings with concatena- tion as described above, but adds some more flexibility in the indexing, including the ability for chunks to "wrap around" the embedding table. In our experiments ROBE was near indistinguishable from QR-concat for large models, though it did give some measurable improvements for very small tables.
Deep Hashing Embeddings DHE (Kang al. 2021) picks 1024 hash functions h....., 11124 [d]] + [-1, 1] and feed the vector (h1 (1)) into a multi-layer perceptron. While the idea of using MLP to save memory the cost of larger compute is novel and parts from the sketching framework, the first hashing step of DHE is just sketching with a
While combining vectors with element wise multiplication is not linear operation. from personal commu- nication with the authors, it is unfortunately hard to train such embeddings in practice. Hence we focus the two linear variants.
4

---

1000
(a) QR with concatenation: In the hashing version of compositional embeddings (QR), each ID hashed location each of, say, different tables. The four vectors stored there are concatenated into the final embedding vector. Given the large number of possible combinations (here 1000*) ), it is unlikely that two IDs get assigned the exact embedding vector, even if they may share each part with some other IDs.
(b) QR hybrid: We can combine the sum hashing method of Tito Svenstrup al. 2017) with the concate- nation method of Shi al. (020)). Each then gets assigned a vector that is the concatenation of smaller sums, In itself this method is not particularly interest- ing. but it is essential step towards the Clustered QR methad describe in this paper.
Figure 4: Compositional Embeddings with concatenation and the Hybrid method which will introduce later on.
dense random matrix H E [-1, 1024, While this is less efficient than a sparse matrix, it can still be applied efficiently to sparse inputs, ei, and stored in small amounts of memory. Unfortunately, in experiments, DHE did not perform as well the other methods, unless the MLP was taken to have just one layer, in which case just a linear transformation, e M, and we end up with more expensive version of Hash Embeddings. See fig. 8b for the details.
Tensor Train (Yin et al. 2021 doesn't 't use hashing, but like QR it splits the input a deterministic way that can be generalized to random hash function if so inclined. Instead of adding or concatenating chunks, Tensor Train multiplies them together as matrices, which makes not strictly linear operation. However, like DHE, the first step reducing the input size is some kind of sketching.
See Appendix C for comparisons to a few more related methods.
Our algorithm is the first that deviates from random sketching the main vehicle of compression. However, as we replace it by learned sketching, we can still express the embedding process as e, for sparse matrix H and small dense matrix M. The difference is that learn H from the data instead using a random or fixed matrix. Experimentally and theoretically this allows better learning the memory usage.
In section we give the practical description of the algorithm, and section 3 we analyze mathematically in simplified setting.
ANALYSIS
We consider simplified model of the setup, where X E gaad, and Y guxdd and we want to find the T E [g [gdx x that minimizes |XT Y In our setup n > di >> d2. (Here || || is the Frobenius norm, defined by |||| E.,
Obviously we can easily retrieve from (X, Y) solving the least squares problem. Let's call this optimal solution T E Rdixds, However, we want to save memory, we instead pick sparse random matrix Ho 12d1x2k and solve
Mo arg min || Y
2
5

---

10000, d0-0000, d2-10 1D,
1o000000 di 1000, d2-1 ke100
MoMonn BUBT
K-Moans
K-Meana topo T1e
K-Maana log2
rolio
800
kmeere toych spiltaa
600
702
400
LPP 300
10'
22'
Gustor Leam Boladora
Gustor Jearn Bonador3
(a) Dense CQR: Repeatedly concatenating T; with ran- dom Gaussian noise quickly recovers the optimal T" solution to the least squares problem. This matches
(b) Multi-step CQR: Repeatedly running k-means and concatenating with Count Sketch finds solution, T. that is as good as a k-means clustering of the optimal T" after just 100 iterations. If we continue training it eventually finds one that is as good as "top 2" k-means, even though it only uses normal k-means itself. We chose X and the same as on the left.
closely the exponential convergence we show in The-
orem 1 For this plot we sampled X ~ [00 1) 1)nxd;, XT. The result
(0, 1)d1 xda and let would be similar Y had noise added on top.
Figure 5: Empirically comparing the (slower) Dense CQR analyzed in this section with the (faster) K-Means approach in fig. I
Then To Mo is approximation T in far as Ho preserves the column space of T Woodruff (2014) showed that this is indeed likely, if k >> d2 even if Ho has just one non-zero per row. For technical reasons we will let Ho be the horizontal concatenation of two Count Sketch matrices. so it has 2k columns with 2 non-zeros per row.
improve over Count Sketch by analyzing Tg. The classical i-means algorithm can be seen to find the optimal factorization To = H'M where H' E {0, 1] has just one 1 per row. So we have saved a bit of space. We could stop here and declare victory, but we want to improve further. To do this we take Hi = [H'] C"] the concatenation of H' with new Count Sketch matrix. We can now repeat the optimization M1- = arg min ||XH, M Y and rinse and repeat:
The idea
Multi-step CQR:
Let Ho = 0 E R4 x2k My = 0 E R 2kxx; then repeat for i 2
T; H,M,
H411 = kk (T-means(T.) new-count-sketch() e Rdx22
M,+1 = arg min XH - Y E 22xxd M
Note that only ever use the "assignment matrix" from k-means, not the actual cluster centers found by Lloyd's algorithm. One could use a different approximation to Ti's column space instead, trading of the sparsity for convergence in fewer steps. Indeed we will now modify the algorithm to dense version that is more amendable to theoretical analysis.
Instead of k-means and Count Sketch, define H [T, N(O 1)dx x*). That is, H2 is the previous T; concatenated with a random normal matrix. In appendix B we show experimentally that this algorithm (which uses dense 11, rather than sparse, and thus slower than what we propose above) behaves nearly identically to the multi-step CQR.
We show that for this version of the algorithm:
Theorem 1.
F|IIT
1I < (1 p) XIT + |XT -YIl

---

where p= | ///222/|1-3 ||
1/d1 is the smallest singular value of X squared divided by the sum of singular values squared This means that after: O d log([[X7*||p/ee iterations we have approximation to the optimal solution.
Note that the standard least squares problem can be solved O(ndid2) time, but one iteration of our algorithm only takes (nkd22 time. Repeating it for d1 /k iterations is thus no slower than the default algorithm for the general least squares problem, but using less memory.
IMPLEMENTATION OF CLUSTERED COMPOSITIONAL EMBEDDINGS (CQR)
We now describe the CQR method used in our experiments. The description here differs from fig. ii two main aspects: 1) We build 4 separate tables, and concatenate the output. And 2) We only do one iteration of the "learning, clustering, learning" loop.
For illustration purposes, we use the setup of one of our experiments on the Kaggle dataset, where the embedding dimension 16 and the number of parameters is 1000.
Step 1:
We start as in QR hybrid (see fig. 4b). with times tables Ti.... T. and T ...... ...TTy each of size 500 x 4. We also pick random hash functions h1,... h4, h1 Then the embedding
R4: [n] [500].
E [x]] defined to the concatenation
T (1)
T (2))
Ta(hs(t)]
Ta(ha(t)) +
(1)
(H))(())
TH)G(()
T((())
We then train the embedding tables for either half an epoch or a full epoch.
Step 2: Following fig. D we now cluster the large implicit table for each column j = 1...4. We pick sub-sample S [n]] of |S| 256 k IDs, and compute the vectors for each of them to obtain a table 7 of 1000 centroids. We define hf: [n]] [1000] to send i E [n] to the nearest centroid of T, [hy (f) + (t)).
Step 3: We retrain the model with the new Iearned hash function. The embedding vector of each e (n] is now assigned to
(T(M((()
(())(1)
Tg(h(())
THA(()))
Note this similar to the QR concat method (fig. 4a but with a learned hash function.
One may wonder about how best to store the learned hash functions Ng. We give more details on this in appendix E
EXPERIMENTS
The main experimental finding is shown in fig. 6 The CQR method allows training model with the baseline Binary Cross Entropy (BCE) using third of the parameters needed with the hashing trick, and 1.5 times less than with the QR concat method. If given the optimal amount of parameters and trained till convergence, it can give a measurably lower BCE.
In this section we explain the experimental setup used, and show the results of various other experiments highlighting the strengths and weaknesses of the CQR method.
5.1 EXPERIMENTAL. SETUP
We follow the setup of the open-sourced DLRM code of Naumov al. (201))
Dataset.
We Critco's Kaggle dataset and Critco's 's Terabyte dataset of click logs. Both public datasets and were used for benchmarking in DLRM (Naumov et al. (2019). our backbone recommendation model. Each dataset has 13 dense features and 26 categorical features.
In the appendix also show how modify the algorithm get p 1/d, exactly.

---

0.460
Baseline
Hashing
0.458
get the actual QR concat
CQR
QR hybrid
0.456
BCE
0.454
0.452
0.450
10a
10a
10f
Number of parameters
Figure 6: Clustered QR outperforms Hashing and Compositional methods. We trained DLRM on the Kaggle dataset with different table compression algorithms and different table sizes for 10 epochs and picked the best validation loss. Our method was able to reach the baseline (trained for epoch with 16 10 parameters, see section with just over 4000 total parameters. Mcanwhile, the best previously published method (QR concat, (Shi al. (2020)) needed more than 6000. Our QR hybrid method also slightly outperform QR concat.
The Kaggle dataset has about 45 million samples over 7 days, where each categorical feature has most 10 million possible values.
The Terabyte dataset has about billion samples over 24 days. our experiments, we sub-sam sampled one-eighth of the data and pre-hashed them with simple modulus such that each categorical feature has at most 10 million possible values, as recommended by the default benchmarking setting in the DLRM code.
We use data from the days prior to the last day the training set. The data of the last data is split into a validation set and test set.
Evaluation Metric. We use Binary Cross-Entrope (BCE) to evaluate the performance of the recom- mendation model. This metric is also used in Shi et (2020) for evaluating the performance of the QR methods. A small BCE means the prediction probability is close to the actual result.
Epochs.
Recommendation systems are typically just trained for one epoch since they are prone to over-fitting, It has however been observed (e.g. by Desai et al. (2022h) that compressed embedding tables benefit from multi-epoch training. We thus give results both for epoch training, epoch training and "best of 10 epochs" (in fig. 6), making best possible model performance.
Backbone Recommendation Models. We adopt the deep learning recommendation model (DLRM) from Naumov et al. (2019) the backbone recommendation model; fig. The DLRM takes dense and sparse features as inputs, where a full embedding table (i.c., one with [ many rows) is used for each categorical feature. Since the model has an open-sourced implementation, we only have to modify the embedding table part of the code to implement our methods.
Number of runs of each model. models are run 3 times. On the Terabyte dataset, each model is run once.
Kaggle dataset, PQ inference run once, while all other
5.2 BASELINE: FULL EMBEDDING TABLE
Full embedding table means that for each categorical feature, train embedding table of the size of the number of categorical values. Then a categorical value mapped uniquely to a row in the table. For example, if feature has 10 million possible values, then its embedding table would have
8

---

10 million row of embedding vectors. The embedding table is then trained for epoch. However, using a full embedding table is usually not practical.
0.4730
0.464
9.4650
0.450
9.4625
6,100
0.466
0.1550
0.42
9.4525
(a) Kaggle dataset, epoch: Since CQR, as defined, clusters the table after first epoch, we here suggest "CQR half" which clusters after only half an epoch. While this outperformed the previous methods (Hash- ing and QR concat) it was slightly worse than just keeping our own sketching method (QR hybrid) for the entire epoch.
(b) Kaggle dataset, 2 epochs: Training for two epochs enough for CQR outperform QR hybrid as well as the methods from previous papers, though not by as much as in fig. where we trained till convergence.
Figure 7: All methods trained for or 2 epochs Kaggle
5.3 PQ INFERENCE
As described in the introduction, the CQR method mimics Product Quantization (PQ) on the full embedding table. For that reason, PQ is strong baseline which we compare with in fig. 7a and fig. Sa. As turns out we mostly able outperform this baseline, which while surprising may be explained by our PQ not being "finetuned" after clustering. We tried training full table, PQ clustering and training this clustering for an epoch, but this approach immediately overfit and gave terrible results. Interestingly this suggests CQR works regularization method for PQ.
0.1225
Baseline
Sase ine
Rishing
COA half
GR concat
OR hybrdd
COR hall
0.40
DHE
CR hybiid
3.129
PO inffrrrnnce
0.455
0.3250
0.3275
0.400
0.2270
10P
Number srammtes
Number paramate
(a) Terabyte dataset, 1 epoch: Like on the Kaggle dataset, running for just 1 epoch was not enough to show improvement
(b) DHE, Kaggle dataset, epoch: Using the sug- gested MLP setup from Kang al. (2021) we were able get competitive performance when fixing the number of layers match the desired number of parameters. This is surprising, so we have opted to not include DHE on the other plots.
sketching method, QR hybrid, but enough to beat QR concat and the Hashing method.
Figure 8: Experiments on Terabyte dataset and with Deep Hashing Embeddings.

---

6 CONCLUSION
We have shown the feasibility of compressing embedding tables at training time using clustering. While there is still work be done in expanding theoretical understanding and testing the method in more situations, we believe this shows an exciting new paradigm for dynamic sparsity in neural networks and recommender systems in particular.
Some previous papers have made wildly different claims in terms of the possibility of compressing embedding tables. We believe fig. fig- and fig. 6 help explain some of that confusion: With standard learning rates, it is not possible to improve over the DLRM baseline much. if at all, at I epoch of training. This matches the results Naumov et al. (2019). However, if you train till convergence, you can match the baseline with 1000x times fewer parameters than the default. Even if you just use the simple hashing trick. This matches the results Desai et al. (2022).
In all experiments, except fig. 8a on the Terabyte dataset, our method, CQR, outperforms all other methods we tried. We believe likely would better on the Terabyte dataset as well, if given time to train until convergence.
Training to convergence is however not very common practical recommendation systems. Our experiment in fig. may offer an explanation why: Most methods overfit if given too large embedding tables(!) This is quite shocking, since the common knowledge is that bigger is always better and concepts should ideally have their own private embedding vectors. We believe these experiments call for more investigation into overfitting in DLRM style models.
REPRODUCIBILITY STATEMENT
The backbone recommendation model, DLRM by Naumov et al. (2019), has an open-sourced PyTorch implementation of the model available on github, with instructions on how to use them in the benchmarking folder. also has instructions on how to download the public datasets. We follow very closely to their instructions, reproducing the baseline result should be straightforward.
For the QR methods, we only need to change two functions the code: create and apply.emb. We suggest using class for each QR method; see fig. 4 For the random hash function, one could use a universal hash function or numpy. random. randint.
For the CQR method, apart from using the classes for the QR concat method and the QR hybrid method, we also need to add a section in the code for k-means clustering after some training. We recommend using the open-sourced k-mmaas clustering algorithm by Johnson al. (2019), since it is much faster than Scikit-learn's 's k-means clustering algorithm (Pedregosa et al. 2011).
REFERENCES
Andrew R Barron, Albert Cohen, Wolfgang Dahmen, and Ronald A DoVore. Approximation and learning by greedy algorithms. The annals of statistics, 36(1 ((11))64-999) 94, 2008
J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing, pp. 106-112, 1977.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Michael Cohen, TS Jayram, and Jelani Nelson. Simple analyses of the sparse johnson-lindenstraue transform. In 1st Symposium Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl- Zentrum fuer Informatik, 2018
Aditya Desai, Li Chou, and Anshumali Shrivastava. Random offset block embedding (robe) for compressed embedding tables in deep learning recommendation systems. Proceedings Machine Learning and Systems, 4:762-778, 2022.
Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable random- ized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19-51, 1997.
10

---

Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. PMLR, 2020.
Benjamin Ghaemmaghami, Mustafa Ozdal, Rakesh Komuravelli, Dmitriy Korchev, Dheevatsa Mudi- gere, Krishnakumar Nair, and Maxim Naumov. Learning to collide: Recommendation system model compression with learned hash functions. arXiv preprint arXiv:220..1883,, 2022.
Robert M. Gray and David L. Neuhoff. Quantization. IEEE transactions on information theory, 44 (6):2325-2383, 1998.
Piotr Indyk and Tal Wagner. Optimal (euclidean) metric compression. SIAM Journal Computing, 31(3):677499) 2022.
Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning- low-rank approximations. Advances in Neural Information Processing Systems, 32, 2019.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions Big Data, (3)):3355547 2019.
Wang-Cheng Cheng Kang. Derek Zhiyuan Cheng, Tiansheng Yao, Xinyang Yi, Ting Chen, Lichan Hong, and H Chi. Learning to embed categorical features without embedding tables for recommendation. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 840-850, 2021.
Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, and David P Woodruff. Learning the positions in countsketch. arXiv preprint arXiv:2007.088 09890, 2020.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation word representa- tions in vector space. arXiv preprint 1rXiv:1301.378. 2013.
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sundaraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G Azzolini, et al. Deep learning recommendation model for personalization and recommendation systems. arXiv preprint arXiv:1966.00091 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang. Compositional embeddings using complementary partitions for memory-efficien recommendation systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 165-175, 2020.
Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. Hash embeddings for efficient word representa- tions. Advances in neural information processing systems, 30, 2017.
Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning, pp. 1113-1120, 2009.
David P. Woodruff. Sketching tool for numerical linear algebra. Found. Trends Theor. Comput. Sci., 10(1-2) 2014. doi: /04000000000 URL http:: http:///oo...r/11.1..5....
04C00000601
Donna Xu, Ivor W Tsang, and Ying Zhang. Online product quantization. IEEE Transactions on Knowledge and Data Engineering, 30(1 1):2155-2198, 2018.
Chunxing Yin, Bilge Acun, Xing Liu, and Carole-Jean Wu. Tt-rec: Tensor train compression for deep learning recommendation models. CoRR, abs/2101.117144 2021. URL http::ttps//.....t. //ttpp::://xiyy arq/abs/210 htc/abb/21001.1177
11

---

CONTENTS
Introduction
Background and Related Work
2.1
Embedding Tables as Linear Maps
3
Analysis
Implementation of Clustered Compositional Embeddings (CQR)
5
Experiments
5.1
Experimental Setup
5.2
Baseline: Full embedding table
5.3
PQ Inference
6
Conclusion
10
What didn't work
12
Proof of the main theorem
13
B. Technical lemmas
18
Other Related Work
19
Hashing
20
E How to store the bash functions)
20
Graphs using AUC as the metric
20
Table Collapse
21
G.1 What entropies are expected?
22
A
WHAT DI WORK
Here the ideas we tried but didn't work the end.
Using multiple helper tables a natural idea use more than one helper table. However, in our experiments, the effect of having more helper tables is not apparent.
Circular clustering Based on the QR concat method, the circular clustering method would use information from other columns do clustering. However, the resulting index pointer functions are too similar to each other, meaning that this method is essentially the hashing trick. We further discuss this issue in appendix G
Continuous clustering We originally envisioned our methods in tight loop between training and (re)clustering. turned out that reducing the number of clusterings didn't impact perfor- mance, eventually reduced it all the way down to just one. In practical applications, with distribution shift over time, doing more clusterings may still useful, as we discuss in section 3
12

---

Changing the number of columns In general, increasing the number of columns leads to better results. However the marginal benefits quickly decrease, and as the number of hash functions grow, so does the training and inference time. We found that columns / hash-functions was good spot.
Residual vector quantization The CQR method combines Product Quantization (PQ) with the QR concat method. We tried combining Residual vector quantization (RVQ) with the Hash Embeddings method from Tito Svenstrup et al. (2017). This method does not perform significantly better than the Hash Embeddings method.
Seeding with PQ We first train full embedding table for one epoch, and then do Product Quantiza- tion (PQ) on the table to obtain the index pointer functions.
We then use the index pointer functions instead of random hash functions in the QR concat method. This method turned out performing badly: The training loss quickly diverges from the test loss after training on just few batches of data.
Here some variations of the CQR method:
Earlier clustering We currently have two versions of the CQR method: CQR half, where clustering happens at the middle of the first epoch, and CQR, where clustering happens the end of the first epoch. We observe that when we cluster earlier. the result is slightly worse Though in case the CQR half method still outperforms the QR concat method.
More parameters before clustering The CQR method allows using two number of parameters, one in Step where we follow the QR hybrid method get a sketch, and one in Step 3 where we follow the QR concat method. We thought that by using more parameters at the beginning. we would be able to get better set of index pointer tables. However, the experiment suggested that the training is faster but the terminal performance is not significantly better.
B PROOF OF THE MAIN THEOREM
Let's remind ourselves of the "Dense CQR algorithm" from section Given X E Ruxd and Y E RRadd, pick & such that > d1 > k d2. We want to solve find matrix T" of size di d2 such that ||XT* || is minimized - the classical Least Squares problem. However, we want to memory less than the typical nd?. We thus this algorithm:
Dense CQR Algorithm: Let To = E Rd xd2 For = 1 to m:
Sample
G, ~ (0, 1) 1)dx
Compute
H, [Ti-1 Gi] E RR xk
M, ing HXH YI E ggxds M
T; HIM,,
We will now argue that Tm, is good approximation T in the sense that || Y is not much bigger than |XT* - Y
Let's consider a non-optimal choice of M, first. Suppose we set M, = ['' Log where M is chosen such that ||H,M, - || i is minimized. By direct multiplication, we have H,M, = Ti-1 + G.M,, Hence in this case minimizing ||H,M; - T' is equivalent to finding M/ at each step such that ||G,M|- - (T - T1-1)llF is minimized.
In other words, are trying estimate T with E, G,M,, where each G, is random and each M! is greedily chosen at each step. This is similar to, for example, the approaches in Barron et al. (2008), though they use conerete list of G!'s. In their case, by the time have d1 /k such G, s, multiplying X with a dj x dj random Gaussian matrix, which of course will have full rank, and so the concatenated M matrix can basically ignore it. However, in optimization over the M,.
just
we do local, not global
Recall the theorem:
13

---

10000, 1900 62-10,
1000000 1000 02-10 6-100
100
1000
200
Frsseed
10 hathe
bariee
(a) Multi-step CQR with steps: methods, dense as sparse, get nearly the same error after the zero steps. This means we haven't 't done any clustering, but simply run more or less sparse Count Sketch. At 1 step all sparsities still do quite well, which is why the real CQR method proposed hash functions per column.
Multi-step CQR with 200 steps: sparse meth- ods converge before reaching zero loss. This is ex- pected, since the k-means baseline run on the true, op- timal 7" matrix also doesn't achieve zero loss. Mean- while, the dense method analyzed in this section does eventually achieve zero loss as predicted by the theo- rem.
paper uses just
Interestingly k-means stopped being an effective CQR sparsification algorithm at higher number of steps, and here instead assign each the nearest codewords from a random Gaussian codebook.
Figure 9: Multi-step CQR Least Squares: We compare the Multi-stey CQR method with sparse И (n hashes per row) with the dense model analyzed in theorem [ We also show a baseline of first solving for the optimal T and then running k-means to reduce the space usage. As hoped, and expected, they all quickly improve with more iterations, though the more sparse version eventually converge.
Theorem 1. Given X E gaxd and Y E B2xdd, Let T arg minTeR4: xd2 |XT - YI be optimal solution to the least squares problem. Then
E [IXT: - | s < ())(kad))) do) 1 |XT - -
where p = ||
Here we use the notation that [ is the smallest singular value of X. Corollary 1. In the setting of the theorem, all singular values of X are equal, then
[ - 1 se- - |XT* + |XT Y
Proof of Corollary 7 Note that || the sum of the di singular values squared:
Since all singular values equal, say E IR, then | dio?. Similarly in this setting, || 2 2² so p 1/d1. Using the inequality 1 1/d, S e 1114 gives the corollary.
First split Y into the part that's in the column space of and the part that's not, Z. We have Y XT + Z, where T arg | - Y| is the solution to the least squares problem. By Pythagoras theorem we then have
Proof of Theorem 7
E [[XT - Y
XT; (XT" +2)
E [T) T 1Z
so it suffices show
E -
<
() XTT
14

---

We will prove the theorem by induction over i. In the case i = 0 have T, 0. [T
T = E trivially. For 2 we insert T; = H,M, and optimize over M,:
11 = HH, - [[
EIIXXHH M1] )
+ |
EIIX - (7 -T:-1)) (T=--
= E|EIIIX(G,M - - T--1ll
S (1 p)* X - --
S (1 [(k d2) |T
where the last step followed by induction. The critical step here bounding
Ealin[]X((M - T) < (1- - (1-0)* |XT|E
for fixed T. We will do this in series of lemmas below.
We show the lemma first in the "vector case", corresponding to = 2, d2 = 1. The general matrix case follow below, and is mostly case of induction the vector case.
Lemma 1. Let X E Raxd be matrix with singular values d1 oa 0. Define p o Σ, o, then for any t E Rd.
1(0.1
inf mER
|X - -t)11 S1 <1-
Proof. Setting (Xt,Xg)/|lxg)) get
|| - 1)113 m X| 1g + ||x1112 - (x,, X1)
(1)
(Xt, xg)²
Xt Xgl3 ||
(2)
We use the singular value decomposition of X UEV Since g N NO, 1)d and V unitary, we have Vag ~ (O, 1)dd and hence we can assume V = 1. Then
(Xt,
(t (gg)
(3)
| x
||
(4)
1 Eg
(E, 1.02g.22
(5)
E o
where eq. 4 follows from UTU = 7 in the SVD. We expand the upper sum to get
Σn, 4l,ofo3999
Ey
= Egg
(6)
Σ, Got
= E
(7)
- of
Here we use the fact that the 's are symmetric, so the cross terms of the sum have mean 0. By scaling, we can assume E, of = and define p. = ?, Then the sum is just convex combination:
ofg0
Σ Ps Eg
(8)
Σ, of
15

---

Since o; da and g are IID, by direct comparison have
o 02yI
Fgg
Fig
Σ
Σ o9g
Hence
0993
Eg
Σ Pi
Eig
E o.
E.0999
remains to bound
o999 Σ, of
0
Eg
E.o
P:
(9)
but this follows from cute, but rather technical lemma, which we will postpone the end of this section. (lemma 3
is interesting notice how the improvement we make each step (that p) could be increased to 1/d by picking G from distribution other than IID normal.
If X ULVT, we can also take VV- g', where g' ~ (O, 1) 1)dh (ddx((k-da) da), In that case we get
(Xt,
+VVVVT 2
VVV
VItV 1 di X di
1
E
[X
=E E
= E
=
1X || S 1/d1. Of course comes with the negative side of having to compute the SVD of X. But since this is just theoretical algorithm, it's still interesting and shows how we would ideally update T,. See fig. 10 for the effect of this change experimentally.
So this way we recreate the ideal bound from corollary
Note that
It's an interesting problem how it might inspire better CQR algorithm. Somehow we'd have get information about the the SVD of X into our sparse super-space approximations.
We now show how to extend the vector case to general matrices.
Lemma 2. Let X E Raxd1 be matrix with singular values 2 ... 2 od, 2 0. Define
p == o2 E, oZ then for any T E IRddd
FG~N(0.1))xx
inf MERAXdd
|X(GM-
T) S (1-p))
Proof. The case l = 1, d2 = is proven above in lemma 1
Case h = 1: We first consider the case where i 1, but d2 can be any positive integer (at most k). Let T = [2] [x,,] be the columns of T and M = [m] [m2l...|ma, be the columns of M. Then the ith column of X (GM - T) is X X(Gm 44), and since the squared Frobenius norm of matrix is simply the sum of the squared column 12 norms, we have
E E - -D
E
E [
de
<
(1 p) X
(10)
1=1
d2
(1 p) E
X
p) XT
where in 11)) applied the single vector case.
16

---

n=625, d1=125, d2=5, k=25
0.0175
noise
smart noise
0.0150
half smart noise
half noise
0.0125
0.0100
MSE
0.0075
0.0050
0.0025
0.0000
0
5
10
15
25
30
Cluster Learn itarations
Figure 10: SVD aligned noise converges faster. In the discussion we mention that picking the random noise in H, as VV-1g' g'. where g' ~ (0, 1)4h (k-dd), can improve the convergence rate from - ik (1 - 1/d)ik, which is always better. this graph we experimentally compare this approach (labeled "smart noise") against the IID gaussian noise (labeled "noise")) and find that the smart noise indeed converges faster least once we get close to zero noise. The graph is over 40 repetitions where X is random rank-10 matrix plus some low magnitude noise. also investigate how much we lose in the theorem by only considering rather than a general M that could take advantage of last rounds T. The plots labeled "half noise" and "half smart noise" are limited in this way, while the two others are not. We observe that the effect of this is much larger in the "non-smart" case, which indicates that the optimal noise distribution found might accidentally be tailored to our analysis.
on the form [7]
17

---

Exponential Distribution
ChiSquare Distribution
0.2
when æ, y are IID with Exponential (blue) or Chi Square distribution (Orange). In both cases the expectation is when p 1/22, just as lemma predicts.
Figure 11: Expectation, E
pz+ (1 p-y
Case & > 1: This time, let 91, .a......... Ik the columns G and let m m ....... m be the rows of M.
We prove the lemma by induction over We already proved the base-case k = so all we need is the induction step. We use the expansion of the matrix product GM as a sum of outer products G. = Σ g.m!
G -
= E
X
Σ gmm
-T)
-T)
1=1
k +
E
X
gime
Σ gam
x=2
T >1:
Σ gem?
S p) E
X
(II)
< (1 p)* []
where 11] used the & = 1 case shown above, and 12 used the inductive hypothesis. This completes the proof for general and d2 that we needed for full theorem.
B. TECHNICAL LEMMAS
It remains to show an interesting lemma used for proving the vector case in lemma [
Lemma 3. Let 01 ... an 2 0 be IID random variables and assume some values p; 2 0t. Σ, Pr and Prs 1/n. Then
On Σe
E
2 1.
Piai
This completes the original proof with p;
a²
and a; = 92
Σ, o7
18

---

Proof. Since the a, are IID, it doesn't matter if permute them. In partieular, if π is random permutation of f1....,W -1}.
an
ap
E
Es
En
(12)
Σ; pias
Pn + >i Pia
an
2 Fa
(13)
Ex Pnan + Eien
an
Ea
(14)
Pn + DienPel Pel I2inn
On
Eg
(15)
Pnan + (1 - Pn.) Eien
where eq. 13
uses Jensen's incquality on the convex function 1/2.
Now define a E
Oj. By permuting a, with the other variables, we get:
On
On
Eu
Eg
(16)
Pnan + (1 - Pn) icn
Pn
L-pu n-1
(a
an)
E.
(17)
i=1 Pna + 1-Pu n-1
(a ai)
a:/a I-pa
Eg
(18)
1-Dm n-1
Pa Pn)a
i=1 n-1
Eg
pla:/al
(19)
i=
where
((g:)
q1
I-Pa
11-pa
pm)g:
is convex whenever I- カ- means can use Jensen's again:
Pn)
1-p I-np
> 1, which is true when 0 S Ps. 1/n. That
ola,/a)
20
a:
= =
1
1,
11
a
which is what wanted to show.
C OTHER RELATED WORK
Recent parallel work by Ghaemmaghami al. (2022) presents a different way to learn a clustering without having to learn the exact embedding tables first. Instead of using hashing as "pseudo table" for clustering work on, they train a model with a lower dimensional table. They run special clustering algorithm designed for low dimensional data on this table, and then retrain the model with the clustering known. It is interesting future work to better compare the strengths and weaknesses of two methods against each other.
Other people have looked at "Learning CountSketch" such as Liu et al. (2020) who gave a formulation in the learning- barning-based sketching paradigm proposed by Indyk et al. (2019). However, these algorithms require repeatedly retraining the model, which for big recommendation systems would be much too slow.
19

---

D HASHING
If h : [n] - [m] and [n] - {-1,1} are random functions, Count Sketch is a matrix H e {0,- - mxmm where Ha, = =(1) h(i) = j and otherwise. Charikar et al. 22002) showed that if m is large enough, the matrix H is dimensionality reduction in the sense that the norm ||a||2 of any vector in R" is approximately preserved, ||H|||2 = ||
This gives simple theoretical way to think about the algorithms above: The learned matrix T H" is simply a lower dimensional approximation to the real table that we wanted to learn. While the theoretical result requires the random "sign function" for the approximation to be unbiased, in practice this appears to not be necessary when directly learning T'. Maybe because the vectors can simply be slightly shifted to debias the result.
There are many strong theoretical results on the properties of Count Sketches, For example, Woodruff (2014) showed that they are so called "subspace embeddings" which means the dimensionality reduction is "robust" and doesn't 't have blind spots that SGD may accidentally walk into. However, the most practical result is that one only needs be a "universal hash function" ala Carter & Wegman (177), which can be as simple and fast as the "multiply shift" hash function by Dietztelbinger et al. (997).
If Count Sketch shows that hashing each i [m]] to a single row in [m]] we may wonder why methods like Hash Embeddings use multiple hash functions (or DHE uses more than a thousand.) The answer can be seen in the theoretical analysis of the "Johnson Lindenstrauss" transformation and in particular the "Sparse Johnson Lindenstrauss" as analyzed by Cohen et al. (2018). The analysis shows that if the data being hashed is not very uniform, it is indeed better to more than hash function (more than non-zero per column in H.) The exact amount depends on characteristics in the data distribution, but one can always get away with sparsity of when looking for 1 + dimensionality reduction. Hence we speculate that DHE could in general replace the 1024 hash functions with something more like Hash Embeddings with MLP top. Another interesting part of the CCohe et al. (2018) analysis is that one should ideally split [m]] in segments, and have one hash function into each segment. This matches the implementations based our work below.
E How TO STORE THE HASH FUNCTIONS
We note that unlike the random hash functions used in Step 1, the index pointer functions obtained from clustering takes space linear in the amount of training data or at least in the ID universe size. At first this may seem like major downside of our method, and while it isn't different from the index tables needed after Product Quantization, it definitely something extra not needed by purely sketching based methods.
We give three reasons why storing this table is not an issue in practice:
The index pointer functions can be stored on the CPU rather than the GPU, since they are used as the first step of the model before the training/inferencee data has been moved from the CPU to the GPU. Furthermore the index lookup is typically done faster on CPUs, since it doesn't 't involve any dense matrix operations.
2. The index pointers can replace the original IDs. Unless we are working in a purely streaming setting, the training data has to be stored somewhere. If IDs are 64 bit integers, replacing them with four 16-bit index pointers net neutral.
3. Some hashing and pruning can be used as a prepossessing step, reducing the universe size of the IDs and thus the size of the index table needed.
F GRAPHS USING AUC AS THE METRIC
We also evaluate the models using AUC, another often employed metric for gauging the effectiveness
of a recommendation model. For example, it was used in (Kang et al. 2021). It provides the
TThis also implies that inner products approximately preserved by the dimensionality reduction.
20

---

probability of getting correct prediction when evaluating test sample from balanced dataset. Thus, a better model is implied by a larger AUC. In this section, we plot the graphs again using AUC.
Baseline
0.806
Hashing
QR concat
0.804
CQR
QR hybrid
0.802
AUC
0.800
0.796
10a
10a
10
10c
Number of parameters
Figure 12: Clustered QR outperforms Hashing and Compositional methods. This figure is fig. plotted with AUC.
0.8000
0.822
0.7955
0.800
3.7955
9.7900
0334
3.7025
107
124
10a
12"
107
124
10a
Number paramsta's
Number paramate
(a) Kaggle dataset, 1 epoch: This figure is fig. plotted with AUC.
7a
(b) Kaggle dataset, epochs: This is fig. 7b plotted with AUC.
Figure 13: All methods trained for or epuchs on Kaggle using AUC as the metric.
G TABLE COLLAPSE
Table collapsing was a problem we encountered for the circular clustering method as described in appendix A. We describe the problem and the metric used to detect it here, since think they may be of interest to the community.
Suppose doing k-means clustering table of 3 partitions in order obtain 3 index pointer functions hg. These functions can be thought as table, where the (i.j)-entry is given by (())).
There multiple failure modes have to be aware of. The first is column-wise collapse:
21

---

3.6000
3.7975
0.00
0.7550
0775
0.790
0.7500
3.7875
Baselie
Hashing
0,7850
GR
CQR
GR hybiff
GR hebrdd
PO Inference
105
100
Number paramate
Number
(a) Terabyte dataset, epoch: This figure is fig.
8a
(b) DHE, Kaggle dataset, I epoch: This figure is
plotted with AUC.
fig. 8b plotted with AUC.
Figure 14: Experiments on Terabyte dataset and with Deep Hashing Embeddings using AUC as the metric.
2
In this table the first column has collapsed to just one cluster. Because the way k-means clustering works, this exact case of complete collapse isn't actually possible, but we might get arbitrarily low entropy as measured by H1, which we define follows: For each column j. column entropy is defined to be the entropy of the probability distribution P, h]([n)) - [0, 1] defined by
# h5(1) x)
D3 (x)
Then we define H1 to be the minimum entropy of the (here 3) column-entropies.
The second failure mode is pairwise collapse:
1
0
1
2
3
1
3
3
0
2
1
In this case the second column is just a permutation the first column. This means the expanded set of possible vectors is much smaller than would expect. We measure pairwise collapse by computing the entropy of the histogram pairs, where the entropy of the column pair (fi,j2 is defined by the column entropy of hg, (+) + max (4, (-). Then define H2 to be the minimum of such aaireentoopies for all (3) pairs of columns.
Pairwise entropy be trivially generalized to triple-wis wise and If we have columns may compute each of H,.... H.. In practice H, and H2 may contain all the information we need.
G.1 WHAT ENTROPIES ARE EXPECTED?
The maximum value for Hi is log kt in the case of a uniform distribution over clusters. The maximum value for H2 is log (5) x 2 log k. (Note log n also an upper bound, where n the number of points in the dataset rows in the table.)
22

---

With the QR method expect all the entropies to be near their maximum. However, for the Circular Clustering method this is not the case! That would mean we haven't been able to extract any useful cluster information from the data.
Instead we expect entropies close to what one gets from performing Product Quantization (PQ) on complete dataset. In short:
1. Too high entropy: We are just doing QR more slowly.
2. Too low entropy: We have table collapse.
3. Golden midpoint: Whatever entropy normal PQ gets.
23


Reviews:
[{"review_id": "ABHx8ybZMxr", "reviewer": "Reviewer_ZdXj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors point out the pros and cons of two existing methods for table compression. Authors demonstrate that combining hashing and clustering based algorithms provides the best of both worlds. Authors prove that this technique works rigorously in the least-square setting. ", "summary_of_the_review": "\n1) \"Unfortunately, in our experiments, DHE did not perform as well as the other methods\": Have authors tried other deep hashing methods [1-4]?\n\n2) There is a big jump from section 3 to section 4. What is X and what is Y in the context of hashing or clustering embedding tables that authors talked about in the section 3? It is left to the reader to make the connection. \n\n3) \"We thus give results both for 1 epoch training, 2 epoch training and “best of 10 epochs”: Can authors define what's best here? Is it on a validation set or test set?\n\n4) Figure 5 shows the results with respect to the number of parameters. Would it be possible to share actual computation time comparison?\n\n5) How was hyperparameter selection done for each of the methods, if any? For example, learning rate. \n\n6) Is BCE the right metric in this case? As it is a click data, it would be too imbalanced. Can authors share more details here?  \n\n7) Most of the plots contain standard deviations. What are these? Were each of the experiments done multiple times? \n\n8) \"We prove that this technique works rigorously in the least-square setting\": How is BCE loss used in experiments related to this claim? \n\n8) Writing: Each section seems disconnected from other sections. Section 2 gives a good overview of existing literature and sets up the proposed method introduced in section 3. But there is a huge jump from section 3 to 4. Section 4 looks like a completely new paper. Start of section 5 is abrupt too and it is not clear what authors are trying to convey without knowing details of the exact dataset and how evaluations of each of the methods are done. Some of the dataset details are missing and not connected to variables used in section 4 where actual optimization is described. Writing should be improved so that readers can easily understand what authors are trying to convey. \n\n[1] Cao, Yue, Mingsheng Long, Bin Liu, and Jianmin Wang. \"Deep cauchy hashing for hamming space retrieval.\" In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1229-1237. 2018.\n[2]Jang, Young Kyun, Geonmo Gu, Byungsoo Ko, Isaac Kang, and Nam Ik Cho. \"Deep Hash Distillation for Image Retrieval.\" In European Conference on Computer Vision, pp. 354-371. Springer, Cham, 2022.\n[3] Boyles, Levi, Aniket Anand Deshmukh, Urun Dogan, Rajesh Koduru, Charles Denis, and Eren Manavoglu. \"Semantic Hashing with Locality Sensitive Embeddings.\" (2020).\n[4] Hoe, Jiun Tian, Kam Woh Ng, Tianyu Zhang, Chee Seng Chan, Yi-Zhe Song, and Tao Xiang. \"One loss for all: Deep hashing with a single cosine similarity based learning objective.\" Advances in Neural Information Processing Systems 34 (2021): 24286-24298.\n\n", "strength_and_weaknesses": "Strengths:\n1) Authors give thorough literature survey and give intuition on how they proposed their method\n2) Authors have strong empirical evidence on datasets used \n\nWeaknesses: \n1) Paper is poorly written. Each of the sections separately can be well written but it is hard to get a connection between each section.\n2) Some of the details are missing to properly evaluate the paper \n3) It is not clear if some of the claims are supported by empirical evidence (e.g. least square setting) and it is also not clear if the evaluation metrics used are the right ones for the imbalanced dataset (e.g. BCE). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6DE7MyMEt7P", "reviewer": "Reviewer_7zzb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposed a new method called Clustered Compositional Embeddings (CQR) for learning compressed embedding tables. The method is a QR concat method with a set of specially initialized embedding tables and carefully chosen hash functions. The authors claim that CQR may achieve compression ratios close to those of post-training quantization with the training time memory reductions of hashing-based methods.", "summary_of_the_review": "The proposed method may be useful in practice. However, I wish the authors can address the issues mentioned above.", "strength_and_weaknesses": "**Strength**\n1. The authors propose a simple method to bridge the gap between post-training quantization and hashing-based methods for embedding compression.\n2. Existing methods are fully surveyed and introduced in the paper.\n\n**Weaknesses**\n1. The empirical comparisons are incomplete.\n(a) The Tensor Train method (Yin et al., 2021) is not compared in the experiments.\n(b) The results of PQ is missing in Figure 5 and Figure 6(b).\n2. The step-1 of CQR still requires firstly training the embedding tables, and hence the current paper title and the statement, \"Our algorithm is the first that deviates from random (or fixed) sketching as the first step of embedding\", are both imprecise.\n3. Figure 1 is confusing and cannot help understanding the proposed method.\n4. Why are the results of PQ in Figure 6(a) and Figure 7(a) so different? It seems that PQ was not correctly applied to the Terabyte dataset.\n\n**Minor problem**\n\n\"increases\" -> \"decreases\", end of page 6.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3JWCnxLRT8I", "reviewer": "Reviewer_ZrK7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new quantization method to deal with high dimensional categorical features in recommendation systems. \n", "summary_of_the_review": "I missed several key points of the paper: \n1) how CQR works overall from the paper. I think the authors can clarify because the related work section was very well explained. \n2) The link of theorem 1 for a random matrix instead of à learned one with CQR\n", "strength_and_weaknesses": "Strengths:\n\nThe background and related work parts are very well written. It is easy to understand the different approaches, even a bit easier than the proposed approach itself.\n  \nThe method is supported by experiments made on two publicly available datasets. \n\nFigure 5 with accuracy against the number of parameters serves as complexity analysis of the cost of storage.\n\nI liked the authors also explain what they tried and did not work.\n\nWeaknesses:\n\nI think the clarity of the paper can be improved for the part describing the model itself:\n\nFigure 1 is supposed to describe the proposed model “Clustered Compositional Embeddings” (CQR) but in the caption the model is denoted as Cluster QR. Two different nominations can be misleading. \n\nFigure 1 and Figure 4 (b) which refer both to CQR do not seem to show the same model.\n\nIn Figure 6, “CQR half” is mentioned before introduction (definition is done only in Appendix). \n\nThere are several references to training time but it is unclear to me whether this is the one to obtain the embeddings or the one for training the recommender system. \n\nWhat would be missing is a complexity analysis of the computation time? Figure 6 shows only the impact of 1 ou 2 epochs on the accuracy (depending on the number of model parameters).\n\nI have several questions:\n\nQ1: p.6: How many samples are considered for step 2? 256 * k but how is k defined?\n1000 cluster points: is 1000 the size of S? Are the cluster points the centroids so k = 1000? A diagram flow of the 3 steps would be helpful to understand. \n\nQ2: Where does fit the analysis (section 4) compared to the 3 steps described before? It seems the result of the clustering is used for sparse approximation of $T_i$ but the authors say later: “it could also be done in other ways”. And theorem 1 which follows brings guarantees for a random $H_i$.\n\nQ3: p.7: Figure 5 is with which Criteo dataset? Two are introduced. \n“Our method was able to reach the baseline”: what is the baseline? We have to wait for paragraph 5.2 for a description of the baseline. Can we have a reference in the caption for clarity? Or indicate that dashed points are for the baseline? \n\nQ4: p.8: Dataset paragraph: How the pre-hashing is made for Terabyte dataset?\n\nQ5: Do you have reference(s) on the fact recommendation systems are not trained until convergence? \n\nMinor (typos):\n-p.3, fig.2: missing bracket for reference to the DLRM model \\citep instead of \\cite?\n-p.9, fig 6 (b): missing “s” to “2 epoch”.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject