# Clustering the Sketch: A Novel Approach to Embedding Table Compression

arXiv: https://arxiv.org/abs/2210.05974 · HTML: https://mlsanity.com/paper/2210.05974/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 12 Oct 2022.

## Builds on (most cited first, 13 of 13)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Deep Learning Recommendation Model for Personalization and Recommendation Systems](https://mlsanity.com/paper/1906.00091/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems](https://mlsanity.com/paper/1909.02107/) (2019)
- [TT-Rec: Tensor Train Compression for Deep Learning Recommendation Models](https://mlsanity.com/paper/2101.11714/) (2021)
- [Hash Embeddings for Efficient Word Representations](https://mlsanity.com/paper/1709.03933/) (2017)
- [Learning to Embed Categorical Features without Embedding Tables for Recommendation](https://mlsanity.com/paper/2010.10784/) (2020)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Online Product Quantization](https://mlsanity.com/paper/1711.10775/) (2017)
- [Learning to Collide: Recommendation System Model Compression with Learned Hash Functions](https://mlsanity.com/paper/2203.15837/) (2022)
- [Optimal (Euclidean) Metric Compression](https://mlsanity.com/paper/2110.03152/) (2021)

## Built on by (most cited first, 2 of 2)

- [Two-dimensional Sparse Parallelism for Large Scale Deep Learning Recommendation Model Training](https://mlsanity.com/paper/2508.03854/) (2025)
- [Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems](https://mlsanity.com/paper/2604.18351/) (2026)

## Abstract (arXiv)

Embedding tables are used by machine learning systems to work with categorical features. In modern Recommendation Systems, these tables can be very large, necessitating the development of new methods for fitting them in memory, even during training. We suggest Clustered Compositional Embeddings (CCE) which combines clustering-based compression like quantization to codebooks with dynamic methods like The Hashing Trick and Compositional Embeddings (Shi et al., 2020). Experimentally CCE achieves the best of both worlds: The high compression rate of codebook-based quantization, but *dynamically* like hashing-based methods, so it can be used during training. Theoretically, we prove that CCE is guaranteed to converge to the optimal codebook and give a tight bound for the number of iterations required.