TL;DR
Recommendation systems rely on massive embedding tables that can consume hundreds of gigabytes of GPU memory during training. This paper introduces Clustered Compositional Embeddings (CQR), an approach that marries the training-time memory efficiency of hashing with the compression quality of clustering-based quantization (like Product Quantization). By training a compact hashing sketch, clustering its implicit representations, and retraining using the learned cluster assignments, CQR matches post-training quantization accuracy with less than half the parameters required by prior training-time compression techniques.
What Problem Does This Paper Address?
Modern deep recommendation systems (such as Meta's DLRM) spend the vast majority of their memory footprint on embedding tables that map high-cardinality categorical IDs (like user, post, or ad IDs) into dense vector spaces.
Existing solutions fall into two flawed camps:
- Post-training quantization (e.g., Product Quantization / PQ): Uses clustering to group similar embedding vectors into shared "codewords." While highly accurate and compact, it requires fully training the uncompressed tables first, offering no GPU memory relief during training.
- During-training hashing (e.g., the Hashing Trick, QR embeddings, Hash Embeddings): Projects IDs into smaller tables using fixed or random hash functions. While this saves memory during training, random collisions force unrelated concepts to share representations, introducing permanent noise and degrading model quality.
The authors set out to achieve the best of both worlds: group semantically similar concepts together via clustering during training, without ever holding the full-sized embedding table in memory.
Methods
The proposed approach, Clustered Compositional Embeddings (CQR), executes in three main phases:
-
Train a Hash-Based Sketch (QR Hybrid): Instead of allocating a full table, the model starts with a compact sketching structure. For each feature slice (e.g., 4 columns), an ID is hashed into two separate sub-tables using random hash functions, and its representation is the sum of the two vectors. The model trains these small tables for an initial phase (half an epoch or one epoch).
-
Subsample & Cluster the Implicit Embeddings: Without materializing the entire billion-row table, the algorithm takes a representative subsample of IDs ($S = 256 \cdot k$), computes their implicit representations from the trained sketch, and runs $k$-means clustering to find representative centroids. Each ID in the universe is then mapped to its nearest centroid via a learned assignment function $h_j^c$.
-
Train Clustered Quantization (QR Concat with Learned Hashes): The initial random hash functions are replaced by the learned cluster assignment functions. The model then finishes training using concatenated centroid vectors, operating like Product Quantization but discovered entirely within a small memory envelope.
The authors also analyze this framework theoretically, proving that an iterative variant of CQR on linear least-squares problems exhibits geometric convergence to the optimal solution.
Datasets
The authors evaluated CQR using the open-sourced DLRM architecture on standard public click-through rate (CTR) benchmarks:
- Criteo Kaggle Dataset: ~45 million samples across 7 days, containing 13 continuous dense features and 26 categorical features (with up to 10 million unique values per feature).
- Criteo Terabyte Dataset: ~4 billion samples across 24 days. The authors sub-sampled one-eighth of the data and pre-hashed categorical values to at most 10 million per feature, mirroring DLRM’s default benchmark settings.
Key Insights and Ideas
- Learned Sketches vs. Random Sketches: Standard training-time compression methods rely on fixed, random sketching matrices $H$ ($T = HM$). CQR demonstrates that $H$ can be iteratively learned from data via intermediate clustering, bridging sketching theory with vector quantization.
- Clustering Needs Only a Coarse "Pseudo-Table": You do not need converged, ground-truth embeddings to find good cluster groupings. A lightly trained, noisy hash-based sketch contains enough relative geometric structure for $k$-means to identify semantic clusters.
- One Clustering Step is Enough in Practice: While the theoretical formulation operates in a multi-step loop, empirically, a single clustering step (after half an epoch or one epoch) was sufficient to achieve peak performance.
- CQR Regularizes Against Overfitting: Surprisingly, CQR often outperformed standard uncompressed Product Quantization (PQ) inference baselines. Deep recommendation models are prone to overfitting when given massive embedding tables; CQR's parameter sharing acts as an implicit regularizer.
Key Results
- Kaggle Benchmark: When trained to convergence (10 epochs), CQR matched the baseline model’s Binary Cross-Entropy (BCE) using just over 4,000 parameters (down from $16 \cdot 10^7$ parameters in the baseline). In comparison, standard hashing required roughly $3\times$ more parameters, and QR-concat required more than $1.5\times$ more parameters (>6,000) to reach the same loss.
- Single/Two-Epoch Regimes: In standard 2-epoch training on Kaggle, CQR outperformed both previous hashing approaches and QR concatenation. In 1-epoch settings ("CQR half"), it beat QR-concat and hashing baselines.
- Terabyte Dataset: At 1 epoch, CQR outpaced standard hashing and QR-concat, closely trailing the uncompressed hybrid sketch baseline while preserving memory.
Limitations and Future Work
- Storing Index Pointer Functions: The learned cluster assignments $h_j^c(i)$ require storing explicit indices for each ID in the vocabulary (linear in dataset size), unlike purely random hash functions. The authors note these can be stored cheaply on host CPU memory or directly substitute 64-bit feature IDs in disk storage.
- 1-Epoch Recommendation Dynamics: In practical settings where models train for only a single pass over streaming data, the clustering step must occur mid-epoch, slightly diminishing its performance edge relative to multi-epoch training.
- Exploration of Non-Random Sketches: The authors note that aligning noise distributions with the singular value decomposition (SVD) of the input data dramatically accelerates theoretical convergence, pointing toward future work on SVD-informed sparse sketches.
Summary updated