Modern recommendation systems process billions of users and items daily. To handle this massive scale of categorical data, models rely on embedding tables that map discrete identifiers (like a user ID or an item ID) into dense, continuous vectors.
While neural network layers are computationally heavy, their parameter footprint is relatively small. Embedding tables are the exact opposite: they are computationally simple but memory-intensive. Because the size of an embedding table scales linearly with the number of unique categories ($O(N \times D)$, where $N$ is the number of entities and $D$ is the vector dimension), these tables routinely balloon into hundreds of gigabytes or even terabytes.
As highlighted by Hongzhi Yin et al. in their comprehensive overview, On-Device Recommender Systems: A Tutorial on The New-Generation Recommendation Paradigm, this memory footprint creates a severe bottleneck. It prevents high-performance recommendation models from running locally on resource-constrained edge devices like smartphones, and forces cloud infrastructure into expensive, distributed training setups as detailed by Shiwei Li et al. in Adaptive Low-Precision Training for Embeddings in Click-Through Rate Prediction.
To overcome this bottleneck, researchers have developed a variety of compression paradigms. Rather than simply compressing a static model after training, modern techniques rethink how embeddings are represented, allocated, and learned from the ground up.
Combinatorial Weight Sharing: The Power of Composition
The most direct way to break the linear memory scaling of embedding tables is to force items to share parameters. However, naive weight sharing (like simple hash-bucketing) causes collisions, where completely different items are forced to share the exact same representation, destroying model accuracy.
Compositional embeddings solve this by using complementary partitions. Instead of mapping an ID to a single row in a massive table, the ID is decomposed into multiple sub-IDs, each indexing into a much smaller, distinct base table. The final embedding is generated by combining the vectors from these base tables (e.g., via addition or concatenation).
Naive Embedding: [ ID 12345 ] ──> 1x10,0000 Table ──> [ Unique Vector ] (High Memory)
Compositional: [ ID 12345 ] ──> Split via Quotient/Remainder
├──> Table A (Size 100) ──> [ Vector A ]
└──> Table B (Size 100) ──> [ Vector B ]
Combine (A + B) ──────────> [ Unique Composite Vector ] (Low Memory)
In Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems, Hao-Jun Michael Shi et al. demonstrate that by using quotient and remainder functions as complementary partitions, two tables of size $\sqrt{N}$ can represent $N$ unique items without a single full-vector collision. This reduces the storage requirement from $O(N)$ to $O(\sqrt{N})$.
Other variations of this structural decomposition include:
- Binary Slicing: Bencheng Yan et al. introduce Binary Code based Hash Embedding (BH) in Binary Code based Hash Embedding for Web-scale Applications, which represents each feature ID as a deterministic binary string. This string is sliced into flexible code blocks that index into small base tables, allowing up to a 1000x reduction in parameters.
- Dynamic Clustering: Instead of relying on static hash functions, Henry Ling-Hei Tsang et al. propose Clustered Compositional Embeddings (CCE) in Clustering the Sketch: Dynamic Compression for Embedding Tables. CCE interleaves training with periodic K-means clustering steps, dynamically grouping similar IDs together in the codebook space during the training loop itself, as further explored in Clustering Embedding Tables, Without First Learning Them.
Exploiting the Power Law: Multi-Granular and Mixed-Dimension Allocation
In real-world recommendation datasets, item popularity follows a long-tail power-law distribution. A tiny fraction of items (the head) appears in millions of interactions, while the vast majority of items (the tail) appear only a handful of times.
Standard embedding tables assign the same vector dimension $D$ to every single item. This is fundamentally inefficient:
- Tail items overfit: There is not enough data to learn a high-dimensional representation for an item that only appears twice.
- Head items are bottlenecked: Popular items require high capacity to capture nuanced user interactions.
Standard Allocation: [ Popular Item ] ──> [████████████████] (16-dim)
[ Rare Item ] ──> [████████████████] (16-dim, Overfits & Wastes RAM)
Adaptive Allocation: [ Popular Item ] ──> [████████████████] (16-dim)
[ Rare Item ] ──> [████] (4-dim, Saves RAM)
To exploit this insight, Wang-Cheng Kang et al. propose Multi-Granular Quantized Embeddings (MGQE) in Learning Multi-granular Quantized Embeddings for Large-Vocab Categorical Features in Recommender Systems. MGQE automatically allocates larger parameter budgets and finer quantization levels to high-frequency items, while assigning highly compressed, shared representations to the long tail.
Taking this concept to its logical conclusion, Tong Chen et al. develop a reinforcement learning framework called CIESS in Continuous Input Embedding Size Search For Recommender Systems. Instead of picking from a few pre-defined dimensions, CIESS searches a continuous space to customize a unique, optimal embedding size for every individual user and item, slashing memory usage by up to 95% while maintaining accuracy.
Pruning and Sparsification: Eliminating Redundant Parameters
Another major angle of attack is pruning—identifying and removing parameters or feature interactions that do not contribute significantly to the model's predictive power.
In Click-Through Rate (CTR) prediction, models often compute explicit interactions between different feature fields (e.g., User Age $\times$ Item Category). Wei Deng et al. introduce DeepLight in A Sparse Deep Factorization Machine for Efficient CTR prediction, which applies structural pruning across neural network layers, field interactions, and embedding layers simultaneously to accelerate inference. Rather than pruning as a post-processing step, Yun Yue et al. show in Adaptive Optimizers with Sparse Group Lasso for Neural Networks in CTR Prediction that incorporating a Sparse Group Lasso penalty directly into the optimization step forces the model to learn sparse embedding structures natively during training.
Single-Shot Pruning via Game Theory
Traditional pruning techniques require slow, iterative cycles of training, pruning, and retraining to recover lost accuracy. To bypass this overhead for on-device deployment, Hung Vinh Tran et al. introduce Shaver in On-device Content-based Recommendation with Single-shot Embedding Pruning: A Cooperative Game Perspective.
Shaver models the parameters of an embedding table as players in a cooperative game. By calculating the Shapley Value of parameter groups in a single pass, the framework quantifies the exact marginal contribution of each weight to the final recommendation accuracy. This allows developers to instantly prune a model down to any arbitrary hardware memory budget on the fly, completely eliminating the need for retraining.
Cloud-Edge Collaboration: Shifting the Storage Paradigm
When an embedding table is too large to be compressed down to a few megabytes, researchers alter the system architecture itself through cloud-edge collaboration, as surveyed by Hongzhi Yin et al. in Special topic on cloud-edge collaboration for on-device recommendation.
Instead of forcing the edge device to maintain the entire global item space, systems can stream parameters dynamically. In EdgeRec: Recommender System on Edge in Mobile Taobao, Yu Gong et al. design an architecture where the master high-dimensional embedding matrices reside in the cloud. When a user makes a request, the cloud pre-filters a candidate pool and transmits only the specific embedding slices relevant to those candidates down to the device. The smartphone then performs real-time, ultra-low-latency reranking locally based on immediate user actions, bypassing the local storage bottleneck.
[ Cloud Server ] ── Stores Terabyte Global Embedding Table
│
│ 1. User requests page
│ 2. Cloud filters top 100 candidates
│ 3. Cloud transmits ONLY those 100 embedding slices
▼
[ Mobile Device ] ── Receives small slice ──> Runs local real-time re-ranking
Similarly, in privacy-preserving federated learning scenarios where devices should not download global tables, Liang Qu et al. propose SemiDFEGL in Semi-decentralized Federated Ego Graph Learning for Recommendation. By introducing a semi-decentralized architecture that leverages "fake common items" to bridge isolated user graphs, they eliminate the requirement for edge hardware to download or store massive global item tables, drastically reducing both memory and communication overhead.
Summary of Compression Paradigms
As synthesized in the comprehensive survey by Shiwei Li et al. (Embedding Compression in Recommender Systems: A Survey) and the empirical benchmarks of Hailin Zhang et al. (Experimental Analysis of Large-scale Learnable Vector Storage Compression), embedding table compression has evolved from a simple post-processing trick into a core architectural consideration. Whether through mathematical decomposition, power-law exploitation, game-theoretic pruning, or distributed cloud-edge execution, these techniques ensure that recommendation models can scale to billions of items without overwhelming the hardware they run on.
Key Foundational Work
EdgeRec: Recommender System on Edge in Mobile Taobao (2020) — contributed 2 concept elements to this direction.
Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems (2020) — contributed 2 concept elements to this direction.
Deep Hash Embedding for Large-Vocab Categorical Feature Representations (2020) — contributed 1 concept elements to this direction.