Abstract
Dense embedding models are commonly deployed in commercial search engines, wherein all the document vectors are pre-computed, and near-neighbor search (NNS) is performed with the query vector to find relevant documents. However, the bottleneck of indexing a large number of dense vectors and performing an NNS hurts the query time and accuracy of these models. In this paper, we argue that high-dimensional and ultra-sparse embedding is a significantly superior alternative to dense low-dimensional embedding for both query efficiency and accuracy. Extreme sparsity eliminates the need for NNS by replacing them with simple lookups, while its high dimensionality ensures that the embeddings are informative even when sparse. However, learning extremely high dimensional embeddings leads to blow up in the model size. To make the training feasible, we propose a partitioning algorithm that learns such high dimensional embeddings across multiple GPUs without any communication. This is facilitated by our novel asymmetric mixture of Sparse, Orthogonal, Learned and Random (SOLAR) Embeddings. The label vectors are random, sparse, and near-orthogonal by design, while the query vectors are learned and sparse. We theoretically prove that our way of one-sided learning is equivalent to learning both query and label embeddings. With these unique properties, we can successfully train 500K dimensional SOLAR embeddings for the tasks of searching through 1.6M books and multi-label classification on the three largest public datasets. We achieve superior precision and recall compared to the respective state-of-the-art baselines for each of the tasks with up to 10 times faster speed.
Introduction
In modern search engines and recommendation systems, dense embeddings have become the industry standard. Typically, items such as documents, products, or labels are represented as dense, low-dimensional vectors (e.g., 128 or 1024 dimensions). To find matches for a query, systems perform a Nearest-Neighbor Search (NNS). However, as datasets scale to millions or billions of items, dense models face significant challenges:
- Retrieval Bottleneck: NNS is computationally expensive and requires complex indexing that can compromise speed or accuracy.
- Model Size: Learning high-dimensional dense representations for millions of labels causes a parameter explosion, making training on standard hardware difficult.
- Communication Overhead: Distributed training of massive models often requires heavy data synchronization between GPUs.
SOLAR (Sparse Orthogonal Learned and Random Embeddings) addresses these issues by utilizing high-dimensional (e.g., 500,000-D) but ultra-sparse vectors, replacing NNS with efficient lookups.
Methodology
SOLAR introduces an asymmetric approach to embedding learning. Unlike traditional models that optimize both query and label embeddings, SOLAR fixes label embeddings as random, sparse, and near-orthogonal vectors. Only the query embeddings are learned. This "one-sided" learning is mathematically justified by the "Law of Deferred Orthogonality," proving it equivalent to learning both sides.
To manage the massive dimensionality, SOLAR employs Zero-Communication Partitioning. The 500K-dimensional vector is divided into $K$ independent components (e.g., 16 chunks of 30,000 dimensions). Each chunk is trained on a separate GPU as an independent classifier, eliminating the need for inter-GPU communication during training.
Retrieval is performed using an Inverted Index, a technology common in traditional text search but adapted here for ultra-sparse embeddings. Because the embeddings are sparse, retrieval involves simple lookups rather than expensive NNS. Furthermore, the random design of label vectors ensures load balancing across the index "buckets," preventing performance bottlenecks caused by popular items.
Evaluation
The researchers evaluated SOLAR on four massive benchmarks: the Amazon Book Dataset (1.67M books), Wiki-500K, Amazon-670K, and Amazon-3M. SOLAR consistently outperformed industry-standard baselines, such as Amazon’s DSSM and state-of-the-art tree-based models like Parabel. For instance, on the Amazon-670K dataset, SOLAR achieved a Precision@1 of 34.37%, surpassing DSSM's 31.34%.
Beyond accuracy, SOLAR demonstrated significant efficiency gains:
- Speed: Training was up to 10x faster than dense counterparts. Inference was 2x to 5x faster, even when comparing SOLAR on a CPU to dense models on a GPU.
- Memory Efficiency: By storing only the indices of non-zero entries (e.g., 16 integers per label) instead of 1,000 floating-point numbers, SOLAR drastically reduces the RAM footprint for deployment.
Discussion and Conclusion
SOLAR demonstrates that sparsity is a powerful feature in high-dimensional spaces. Extreme sparsity (e.g., 0.05% non-zeros) can be more informative and efficient than low-dimensional density if the dimensionality is sufficiently high. By fixing label vectors as random and orthogonal, the optimization problem is simplified into independent "learning to hash" tasks.
While SOLAR is highly efficient on CPUs due to its reliance on lookups, its practical gains are currently constrained by the lack of specialized hardware acceleration for sparse operations on GPUs/TPUs. Future work may involve extending this paradigm to other NLP tasks, potentially challenging established dense models like BERT in areas such as translation or sentence embedding.
Summary updated