Compressing High-Dimensional Embeddings for Scalable Vector Search

216 concepts181 papers1 proposal

Modern information retrieval has shifted from exact keyword matching to semantic vector search. By mapping text, images, or user profiles into high-dimensional vector spaces, deep learning models capture rich conceptual relationships. However, this semantic fidelity comes at a steep cost: storage scalability.

When deploying retrieval-augmented generation (RAG) or nearest-neighbor language models (Urvashi Khandelwal et al.), systems must store dense floating-point vectors for millions or billions of tokens or documents. As Matthijs Douze et al. highlight in their overview of the Faiss library, storing these raw embeddings quickly exceeds the RAM capacity of standard hardware, creating a massive "memory wall."

Why can't we rely on standard database compression? As Anna Pavlenko et al. demonstrate, high-dimensional machine learning embeddings consist of high-entropy floating-point values. Traditional columnar formats like Parquet or ORC rely on patterns, repetition, or low entropy to compress data; they fail when faced with the pseudo-random distribution of dense neural vectors. To scale vector search, researchers must design compression techniques that explicitly exploit the underlying geometry of the embedding space.

Quantization and Binarization: Trading Precision for Scale

The most direct way to compress a vector is to reduce the precision of its individual components. Instead of representing each dimension with a 32-bit floating-point number, we can map the continuous space into discrete codes.

In its most extreme form—binarization—each floating-point coordinate is reduced to a single bit (0 or 1) based on its sign. The intuition here is that the direction of a vector in a high-dimensional semantic space carries far more information than its exact magnitude. By converting vectors into binary strings, the distance calculation shifts from expensive floating-point dot products to bitwise XOR operations followed by a population count (Hamming distance). This process can be executed natively in hardware using SIMD instructions.

Ikuya Yamada et al. leveraged this in their Binary Passage Retriever, compressing open-domain question answering indices from 65GB down to 2GB with minimal loss in accuracy. Similarly, Yukang Gan et al. demonstrated that recurrent binarization allows billion-scale production systems to slash storage and latency by up to 50% while maintaining backward compatibility with older indices.

Continuous Vector:  [ 0.45, -0.12,  0.89, -0.34 ]
                          │      │      │      │   (Sign Function)
                          ▼      ▼      ▼      ▼
Binary Vector:      [   1,     0,     1,     0 ]  --> Stored as compact bits

For scenarios where 1-bit quantization discards too much information, researchers use Product Quantization (PQ). PQ splits a high-dimensional vector into several smaller sub-vectors, clusters each sub-vector space independently, and stores only the integer index of the nearest cluster centroid.

To prevent compression from degrading search quality, Jingtao Zhan et al. showed that jointly optimizing the query encoder alongside product quantization codebooks ensures that the compression process explicitly preserves retrieval performance rather than just minimizing geometric distortion. Jianyang Gao further refined this space by introducing asymptotically optimal quantization frameworks that achieve flexible compression rates (such as 4x or 8x) while maintaining strict theoretical bounds on search error.

Sparsification: Leveraging Inverted Indexes

An alternative to making dense vectors smaller is to make them sparse. Traditional search engines scale effortlessly to billions of documents because they use inverted indexes: a mapping from discrete words to the documents containing them. If we can map dense neural representations back into a sparse token vocabulary, we can inherit decades of database optimization.

Carlos Lassance et al. proposed using Composite Code Sparse Autoencoders to transform dense BERT embeddings into balanced, sparse inverted index codes. By regularizing the autoencoder to distribute codes uniformly, they avoid the computational bottlenecks associated with highly frequent tokens.

In the multi-modal domain, Bowen Zhang et al. introduced STAIR, which projects both text and images into a sparse, high-dimensional token space. This allows cross-modal retrieval to run at twice the speed of dense models like CLIP by executing directly over standard inverted indexes, while simultaneously providing human-readable token "explanations" for why an item was retrieved.

Adaptive and Multi-Granular Search Funnels

Not every query requires the highest level of precision immediately. A search pipeline can be thought of as a funnel: we need to filter down billions of candidates to a few hundreds quickly, and only then apply high-fidelity representations to find the absolute best matches.

Aniket Rege et al. addressed this with AdANNS, a framework built on Matryoshka Representations. Instead of treating a vector as an indivisible unit, Matryoshka embeddings are trained such that their early dimensions (e.g., the first 64 dimensions of a 2048-dimensional vector) contain a highly accurate, low-resolution snapshot of the semantics. The initial search pass can happen entirely using these tiny, memory-efficient sub-vectors, drastically reducing RAM overhead and accelerating candidate generation before scaling up to higher dimensions for final precision.

Matryoshka Vector: [ x₁, x₂, ..., x₆₄ | x₆₅, ..., x₂₅₆ | x₂₅₇, ..., x₁₀₂₄ ]
                   └──────┬──────┘   └───────┬───────┘   └───────┬───────┘
                          ▼                  ▼                   ▼
                   Coarse Search       Medium Search        Fine Search
                   (Low Memory)       (Medium Memory)      (Full Precision)

Taking a structural approach to this funnel, Hao Sun et al. developed a bi-granular document representation (BiDR). They split the storage architecture entirely: lightweight sparse embeddings live permanently in RAM to handle global candidate filtering, while the heavy, full-precision dense embeddings are relegated to cheaper disk storage, fetched only during the final re-ranking phase. This hybrid architecture breaks the memory wall, allowing billion-scale vector search to operate without requiring terabytes of expensive distributed RAM.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_embedding_storage_overhead_f97f29b5,
  title = {embedding storage overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/embedding-storage-overhead/rdr_f97f29b561394149a5f7bbf66e8743d8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_embedding_storage_overhead_f97f29b5_v1,
  title = {embedding storage overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/embedding-storage-overhead/rdr_f97f29b561394149a5f7bbf66e8743d8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake