SOLAR: Sparse Orthogonal Learned and Random Embeddings

Tharun Medini, Beidi Chen, Anshumali Shrivastava

In the world of search engines and recommendation systems, "dense embeddings" have long been the gold standard. Whether it's an e-commerce platform suggesting your next book or a search engine matching a query to a webpage, the underlying mathematics usually involves projecting items into a low-dimensional, dense vector space.

But as datasets grow to include millions of products and billions of queries, these dense models are hitting a wall. The paper "SOLAR: Sparse Orthogonal Learned and Random Embeddings" argues that we have been looking at the problem backward. Instead of squeezing information into small, dense vectors, we should embrace "ultra-sparse," high-dimensional spaces to achieve massive scalability without sacrificing accuracy.

The Dense Bottleneck

Modern Information Retrieval (IR) relies heavily on Near-Neighbor Search (NNS). To find a relevant document, a system computes the dot product between a query vector and millions of document vectors. This approach introduces three major pain points:

  1. The NNS Bottleneck: Performing NNS at scale is computationally expensive. Systems often have to sacrifice accuracy for speed by using approximate nearest neighbor techniques.
  2. Memory Bloat: Dense models require storing millions of high-precision vectors in GPU memory, which scales poorly as catalogs grow.
  3. Training Friction: Training these models across multiple GPUs usually requires heavy communication to synchronize gradients, significantly slowing down the process.

The authors identify a fundamental tension: we want embeddings to be highly informative (which typically requires high dimensionality) but also computationally efficient (which requires sparsity).

Introducing SOLAR Embeddings

To resolve this tension, the authors introduce SOLAR: Sparse, Orthogonal, Learned, and Random embeddings. The architecture is built on a few radical design choices that flip traditional embedding learning on its head.

Fixed, Random Labels and One-Sided Learning

Unlike standard models that simultaneously learn embeddings for both queries and labels (e.g., products or documents), SOLAR pre-computes label embeddings as random, ultra-sparse vectors and fixes them. Because the labels are fixed, the model only needs to learn how to project the query into that same sparse space. The authors provide a mathematical proof showing that if labels are orthogonal, this "one-sided" learning is equivalent to learning both sides.

Zero-Communication Parallelism

The high-dimensional space (e.g., 500,000 dimensions) is partitioned into $K$ independent components. Each component can be trained on a separate GPU without ever needing to communicate with the others.

SOLAR Architecture showing parallel classifiers and sparse label matrix

As shown in the architecture above, the tokenized input is fed into multiple independent classifiers. The true labels are mapped to a sparse, partitioned matrix, allowing the model to scale across hardware seamlessly.

Inverted-Index Lookup and Inference

Instead of relying on expensive matrix multiplications for NNS, SOLAR uses an Inverted Index. During inference, the model predicts which "buckets" a query belongs to, and then simply looks up which labels reside in those buckets.

Inference process using sparsification and score summation

By forcing query embeddings to be sparse, the model essentially "learns to hash." As illustrated above, the sparsified outputs from the independent classifiers are simply summed up. The label with the highest aggregated score is selected, bypassing the need for an exhaustive search.

Key Insights and Performance

The researchers evaluated SOLAR on massive, real-world datasets, including an Amazon Book Dataset (1.67 million books) and the three largest public Extreme Multi-label Classification (XML) datasets (Wiki-500K, Amazon-670K, and Amazon-3M).

  • The Power of Orthogonality: In high-dimensional space, random vectors are naturally "near-orthogonal." SOLAR exploits this to ensure that different labels are easily distinguishable, simplifying the classifier's job.
  • Load Balancing by Design: Traditional inverted indexes often suffer from "lopsided" buckets where popular items clog the system. SOLAR’s random assignment ensures every bucket is equally filled, leading to consistent, predictable inference times.
  • Speed and Accuracy: SOLAR consistently outperformed industry-standard models like Amazon’s DSSM. It trained 10x faster on the 1.6M book dataset and achieved 2x to 5x faster inference speeds while running primarily on a CPU. On the Amazon-3M dataset, SOLAR achieved a Precision@1 of 44.89%, significantly outperforming other embedding-based methods.
  • Tail Robustness: SOLAR proved much better at handling "tail queries" (rare or infrequent searches) where dense models often falter.

Limitations and Future Work

While SOLAR is a powerhouse for retrieval, it has some constraints. To handle massive vocabularies, the model uses feature hashing, which can lead to collisions and minor information loss. Additionally, its performance is sensitive to hyperparameters like the number of partitions ($K$) and buckets per partition ($B$), requiring careful tuning to balance speed and precision.

Despite these limitations, SOLAR represents a compelling shift toward "sparse-first" architectures. It proves that sometimes, the best way to handle massive-scale data isn't to compress it into dense bottlenecks, but to spread it out intelligently.

Summary updated

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 task with up to 10 times faster speed.
BibTeX
@inproceedings{medini2021solar,
  author = {Tharun Medini and Beidi Chen and Anshumali Shrivastava},
  title = {{SOLAR: Sparse Orthogonal Learned and Random Embeddings}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=fw-BHZ1KjxJ},
}
Figure