Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks

Joan Serrà, Alexandros Karatzoglou

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.

Relative performance ($S_i/S_0$) across various datasets as the compression ratio ($m/d$) varies.

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.

Training time reduction ($T_i/T_0$) relative to the uncompressed baseline as a function of the compression ratio ($m/d$).

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

Abstract

Recommendation algorithms that incorporate techniques from deep learning are becoming increasingly popular. Due to the structure of the data coming from recommendation domains (i.e., one-hot-encoded vectors of item preferences), these algorithms tend to have large input and output dimensionalities that dominate their overall size. This makes them difficult to train, due to the limited memory of graphical processing units, and difficult to deploy on mobile devices with limited hardware. To address these difficulties, we propose Bloom embeddings, a compression technique that can be applied to the input and output of neural network models dealing with sparse high-dimensional binary-coded instances. Bloom embeddings are computationally efficient, and do not seriously compromise the accuracy of the model up to 1/5 compression ratios. In some cases, they even improve over the original accuracy, with relative increases up to 12%. We evaluate Bloom embeddings on 7 data sets and compare it against 4 alternative methods, obtaining favorable results. We also discuss a number of further advantages of Bloom embeddings, such as 'on-the-fly' constant-time operation, zero or marginal space requirements, training time speedups, or the fact that they do not require any change to the core model architecture or training configuration.
BibTeX
@inproceedings{serra2017getting,
  author = {Joan Serrà and Alexandros Karatzoglou},
  title = {{Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks}},
  booktitle = {RecSys},
  year = {2017},
  url = {https://openreview.net/forum?id=QllaWJ80NK},
}
Figure