Clustering the Sketch: A Novel Approach to Embedding Table Compression

Henry Ling-Hei Tsang, Thomas D. Ahle

TL;DR

Clustered Compositional Embeddings (CCE) is a new approach that bridges the gap between noisy "during-training" hashing and high-quality "post-training" quantization. By interleaving training with periodic clustering, CCE achieves massive memory savings—up to 11,000x fewer parameters than uncompressed models—while actually improving accuracy by acting as a regularizer.

What Problem Does This Paper Address?

In modern recommendation systems (like those powering YouTube or Facebook), categorical features—such as User IDs or Video IDs—are represented as "embeddings" (dense vectors). Because these vocabularies are astronomical, the resulting embedding tables can demand hundreds of gigabytes of GPU memory.

Engineers usually face a "pick your poison" scenario:

  1. The Hashing Trick: Map IDs to a smaller table using a random hash. It’s fast and works during training, but it’s "blind"—it forces unrelated concepts to share the same parameters, adding noise that hurts performance.
  2. Quantization: Use clustering (like K-means) to group similar IDs. This is highly efficient but typically happens after the model is already trained. This means you still need massive amounts of memory during the training phase itself.

The authors of this paper ask: Can we get the high compression of clustering while maintaining the dynamic, memory-efficient nature of hashing during training?

Methods

The authors introduce Clustered Compositional Embeddings (CCE). The core idea is to treat the embedding process as a "sketch" that evolves over time.

  • The Initialization: Start with a small embedding table and use random hash functions to map IDs to it (similar to the Hashing Trick).
  • The Training Loop: Train the model for an epoch. During this time, the model learns a rough representation of which IDs are important.
  • The Clustering Step: Periodically (e.g., every epoch), the algorithm takes the current embeddings and runs K-means clustering. This identifies which IDs are behaving similarly.
  • The Update: The random hash functions are replaced with these learned cluster assignments. Similar IDs are now explicitly mapped to the same "code word" in the table.
  • The Residual: To keep the model from getting "stuck" in a bad clustering, they add a small "helper" table with new random hashes to capture the information the current clusters might be missing.

Essentially, CCE is a "learn-then-compress-then-relearn" cycle that keeps the parameter count fixed and small throughout the entire training process.

Datasets

The researchers evaluated CCE on two massive industry-standard benchmarks for recommendation systems:

  • Criteo Kaggle: A dataset of ~45 million click logs over 7 days.
  • Criteo Terabyte: A significantly larger dataset containing approximately 4 billion samples over 24 days.

These datasets are notorious for having extremely high-cardinality categorical features, making them the perfect stress test for embedding compression.

Key Insights and Ideas

  • Bridging the Gap: CCE is the first method to successfully combine the benefits of "post-training" vector quantization with "during-training" hashing.
  • Compression as Regularization: One of the most surprising "aha moments" was that CCE actually improved the Binary Cross Entropy (BCE) by 0.66% on the Kaggle dataset. In recommendation systems, "bigger" isn't always better; huge tables often lead to overfitting on rare IDs. By forcing similar IDs to share parameters, CCE acts as a powerful regularizer.
  • Theoretical Guarantees: Beyond empirical success, the authors provide a mathematical proof that for linear least-squares problems, CCE is guaranteed to converge to the optimal codebook with a tight bound on the number of iterations required.
  • Single-Epoch Efficiency: In many industrial settings, models are only trained for a single pass (one epoch). CCE was shown to be effective even when clustering was performed just once or twice during that single epoch.

Key Results

  • Massive Compression: CCE achieved parity with baseline models while using 11,000x fewer parameters than uncompressed tables.
  • State-of-the-Art Performance: Compared to other advanced compression methods like ROBE or Compositional Embeddings (CE), CCE reached the same accuracy using less than 50% of the parameters required by those competitors.
  • Accuracy Boost: On the Criteo Kaggle dataset, CCE didn't just match the baseline; it outperformed it, reducing the test loss (BCE) significantly.
  • Training Neutrality: The computational overhead of the clustering step is minimal, and the training time remains roughly the same as standard hashing methods.

Limitations and Future Work

  • Index Pointer Storage: While the embedding table is tiny, CCE requires storing the "index pointers" (the mapping of IDs to clusters). These take up space linear to the vocabulary size. The authors argue these can be stored on the CPU to save precious GPU memory, but it remains a factor to manage.
  • Deep Learning Gap: The theoretical convergence proof is currently limited to linear models. Extending this proof to the non-linear world of deep neural networks is a clear next step.
  • Hyperparameter Sensitivity: The performance of CCE depends on how often you cluster and how many clusters you choose. While the paper provides some heuristics (like 4 columns/hash functions), more automated ways to tune these would be beneficial for production environments.

Summary updated

Abstract

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.
BibTeX
@inproceedings{tsang2023clustering,
  author = {Henry Ling-Hei Tsang and Thomas D. Ahle},
  title = {{Clustering the Sketch: A Novel Approach to Embedding Table Compression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=C4rRqkXFyC},
}
Figure