Abstract
Deep learning models for recommendation systems are often dominated by massive input and output layers, which can account for over 99.9% of total model parameters. This paper introduces Bloom Embeddings (BE), a novel compression technique inspired by Bloom filters. By mapping high-dimensional sparse vectors to a compact binary space via hashing, BE achieves up to 5x compression with minimal accuracy loss and significant training speedups. In some cases, the method even acts as a regularizer, improving predictive performance over uncompressed baselines.
Introduction
Modern recommendation systems (e.g., Netflix, Spotify) face a scalability crisis. Because they handle millions of unique items, their input and output layers are represented as massive one-hot encoded vectors. This creates three primary challenges: memory bottlenecks on standard GPUs, difficulties in mobile deployment, and high computational costs during training.
While embedding inputs into lower dimensions is common, doing so for outputs in a fast, reversible, and memory-efficient way remains difficult. Bloom Embeddings (BE) address this by using an unsupervised hashing approach that requires zero storage for the embedding matrix itself.
Methodology
Bloom Embeddings utilize the logic of the Bloom filter data structure to represent sparse data.
- Encoding: Instead of a single active bit in a million-dimensional vector, BE uses $k$ independent hash functions to map an item to $k$ positions in a much smaller bit array of size $m$.
- Zero-Space Requirement: Because the embedding is computed on-the-fly via hashing, it eliminates the need to store a massive $d \times m$ weight matrix.
- Reversible Outputs: To generate recommendations, the model applies a softmax activation to the $m$ dimensions. The likelihood of an original item is then calculated as the product of probabilities at its $k$ hashed positions.
- Co-occurrence-based Bloom Embedding (CBE): An extension that uses data statistics to steer hash collisions, forcing items that frequently appear together to share bits, thereby minimizing the negative impact of random collisions.
Experimental Evaluation
The researchers evaluated BE across seven diverse tasks, including recommendation (MovieLens 20M, Million Song Dataset, Amazon Book Reviews, Book Crossing), session-based recommendation (YooChoose), and NLP/Text categorization (Penn Treebank, CADE).
Results and Discussion
Compression vs. Accuracy
BE consistently demonstrated the ability to reduce input/output dimensionality by 5x ($m/d = 0.2$) while maintaining over 92% of the original accuracy.
As shown in the figure above, for many datasets such as the Million Song Dataset (MSD) and Amazon Book Reviews (AMZ), the performance remains remarkably close to the baseline even at high compression ratios. Interestingly, BE improved accuracy over the baseline in 3 out of 7 tasks, likely because the $k$-bit activation provides a richer gradient signal, acting as a form of beneficial regularization.
Training Speedup
By significantly reducing the parameter count, BE facilitates faster computation. The authors observed a 3x speedup in training time for a 5x compression ratio.
This speedup, visualized above, makes the training of massive recommender systems more feasible on standard hardware and accelerates the research cycle.
Conclusion
Bloom Embeddings offer a powerful, architecture-agnostic solution for scaling deep recommenders. By leveraging hashing to create compact, unsupervised embeddings, the method provides a path toward deploying high-performance models on resource-constrained devices without sacrificing accuracy. Future work will explore "Counting Bloom Filters" and optimized retrieval methods for the $m$-dimensional output space.
Summary updated