DEV Community

kai wen ng
kai wen ng

Posted on

Speeding Up Vector Search with Quantization & Vector Indices

#vectordatabase #rag #ai #algorithms

Unlike traditional databases, vector databases do not search for exact matches. Instead, they compare the similarity between high-dimensional embedding vectors. A naive implementation would compare the query vector against every vector in the database, which quickly becomes computationally expensive as the dataset grows.

To improve search speed, vector databases use specialised indexing algorithms that significantly reduce the number of vector comparisons while maintaining high retrieval accuracy.

Flat Index

The Flat index is the simplest approach. It performs a brute-force search by calculating the similarity between the query vector and every vector stored in the database.

IVF (Inverted File Index)

IVF speeds up vector search by first clustering the dataset using algorithms such as K-Means.
Instead of searching the entire database, the query is first assigned to the nearest cluster, and only vectors within that cluster (or a few nearby clusters) are searched.
Conceptually, it behaves like an inverted index which tells the search: this cluster has this vector

Cluster A
 ├── Vector 1
 ├── Vector 5
 └── Vector 12

Cluster B
 ├── Vector 2
 ├── Vector 7
 └── Vector 20
Enter fullscreen mode Exit fullscreen mode

LSH (Locality-Sensitive Hashing)

Locality-Sensitive Hashing maps similar vectors into the same hash buckets with high probability.
Unlike traditional hash functions that minimise collisions, LSH intentionally increases collisions for similar vectors. It does this by projecting vectors onto multiple random hyperplanes and generating hash codes based on the projection results.
During retrieval, only vectors in the same hash buckets are compared instead of the entire database.

HNSW (Hierarchical Navigable Small World)

HNSW is one of the most popular vector indexing algorithms today because it offers an excellent balance between speed and accuracy.
It organises vectors into a hierarchical graph.

  • The upper layers contain only a small number of nodes connected by long-distance links, similar to highways connecting major cities.
  • Lower layers contain many more nodes with shorter connections, similar to local roads.

A search begins from the top layer and gradually moves down through increasingly detailed layers until it reaches the nearest neighbours.

Important parameters include:

  • M – Maximum number of roads connected to each city. More roads create a denser network, making it easier to find efficient routes.
  • efConstruction – Determines how thoroughly the road network is planned during construction. Higher values spend more time finding the best roads between cities, resulting in a better network.
  • efSearch – Determines how many possible routes are explored during navigation. Higher values consider more roads before deciding on the destination, improving accuracy at the cost of slightly longer search time.

Quantization

Even with efficient indexes, storing and comparing high-dimensional floating-point vectors remains expensive.
Quantization reduces both memory usage and computation by compressing vectors before indexing.

Scalar Quantization (SQ)

Scalar Quantization compresses each floating-point value individually.
For example:

  • Original: 32-bit floating-point numbers
  • Compressed: 8-bit integers

Product Quantization (PQ)

Product Quantization compresses vectors more aggressively.
Instead of compressing each value independently, it:

  1. Splits each embedding into multiple smaller sub-vectors.
  2. Runs clustering on each sub-vector independently.
  3. Stores only the centroid IDs instead of the original floating-point values.

During retrieval:

  1. The query embedding is split into the same sub-vectors.
  2. Distances are computed using the centroid codebooks instead of the original vectors.

Additional Optimisations

Vector search is rarely used alone in production systems. Several additional techniques are commonly combined to improve both performance and retrieval quality.

Metadata Filtering

Before performing vector search, metadata can eliminate documents that are impossible matches.
Examples include:

  • File type
  • Language
  • Date range
  • User permissions
  • Product category

Reducing the candidate set before vector search significantly improves efficiency.

Hybrid Search

Many production retrieval systems combine vector search with traditional keyword search.
Keyword search provides exact lexical matching, while vector search captures semantic similarity.
The results are then combined using ranking algorithms, often producing higher-quality retrieval than either approach alone.

Reference: https://www.oreilly.com/library/view/vector-databases/9781098177584/

Top comments (0)