# Vector Indexing with HNSW and IVF Explained | llmnet

[Skip to content](#lm-inhoud)Network/[NL](/en/vector-indexering-hnsw-ivf)EN[Hubhub.llmnet.nlCompare models on task, language, cost and license.](https://hub.llmnet.nl/en/)[Communitycommunity.llmnet.nlPrompt techniques, patterns and system prompts.](https://community.llmnet.nl/en/)[APIapi.llmnet.nlLLMs in production: rate limits, routing, structured output.](https://api.llmnet.nl/en/)[Consultancyconsultancy.llmnet.nlRolling out AI in an organization, pilot to production.](https://consultancy.llmnet.nl/en/)[Newsnieuws.llmnet.nlAI developments, explained for the Netherlands.](https://nieuws.llmnet.nl/en/)[Benchmarkbenchmark.llmnet.nlMeasure AI quality yourself, on your own tasks.](https://benchmark.llmnet.nl/en/)[Careersvacatures.llmnet.nlAI roles, salaries and career paths in the Netherlands.](https://vacatures.llmnet.nl/en/)[Learnleren.llmnet.nlAI concepts in plain language, beginner to builder.](https://leren.llmnet.nl/en/)[Guidegids.llmnet.nlRun AI privately on your own Mac, PC, NAS or home server.](https://gids.llmnet.nl/en/)[Directorydirectory.llmnet.nlMapping the AI ecosystem: tools, models, companies.](https://directory.llmnet.nl/en/)[Radarradar.llmnet.nlSignals from X, research and communities for indie developers.](https://radar.llmnet.nl/en/)[Appsapps.llmnet.nlReviews of AI apps and open-source repos, with tips for builders.](https://apps.llmnet.nl/en/)[llmnet.nl — main site](https://llmnet.nl/en/)[](https://x.com/intent/post?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf&text=Vector%20Indexing%20with%20HNSW%20and%20IVF%20Explained)[](https://www.linkedin.com/sharing/share-offsite/?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf)[](https://www.reddit.com/submit?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf&title=Vector%20Indexing%20with%20HNSW%20and%20IVF%20Explained)[](#)[](https://x.com/intent/post?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf&text=Vector%20Indexing%20with%20HNSW%20and%20IVF%20Explained)[](https://www.linkedin.com/sharing/share-offsite/?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf)[](https://www.reddit.com/submit?url=https%3A%2F%2Fleren.llmnet.nl%2Fen%2Fvector-indexering-hnsw-ivf&title=Vector%20Indexing%20with%20HNSW%20and%20IVF%20Explained)[](#)

# Vector Indexing with HNSW and IVF Explained

By Ivo Donker — compiled with AI support (Claude & Gemini) · Last updated: 6 August 2026

## Introduction and the role of embeddings

In modern AI applications, embeddings form the mathematical representation of text, images, or audio. An embedding model converts unstructured data into a series of numbers, known as a vector. This vector often has hundreds or even thousands of dimensions. In this multidimensional space, concepts with similar meaning are located close together, while unrelated concepts are further apart. If you want to learn more about generating these vectors, read the overview on [embeddings explained](https://leren.llmnet.nl/en/embeddings-uitgelegd).

When you search based on meaning, such as with [Retrieval-Augmented Generation (RAG)](https://leren.llmnet.nl/en/rag-voor-beginners), you first translate the search query into a search vector. You then compare this search vector to all the stored vectors in your database. The best-matching results are the vectors with the smallest distance to the search vector, measured for example with cosine similarity or Euclidean distance. Efficiently finding these nearest neighbors is the central challenge of vector indexing.

## The scaling problem in meaning-based search

Calculating the exact distance between a search vector and every vector in a database is called the exact k-Nearest Neighbors (k-NN) approach, also known as a brute-force search. For small collections of a few thousand vectors, this works fine. However, the computing power required for this grows linearly with the number of vectors ($N$) and the dimensionality of the data ($d$). The time complexity of a full search is $O(N \cdot d)$.

Once a collection grows to hundreds of thousands or millions of documents, a brute-force search grinds to a halt. If you search a dataset of one million vectors with 1536 dimensions each, a single search requires more than one and a half billion multiplications and additions. When multiple searches come in per second, the server's memory and compute resources quickly become overloaded. To keep vector databases usable at scale, a different approach is needed.

## Why approximate search is accepted

The solution to this scaling problem is to switch from exact search to approximate search, referred to as Approximate Nearest Neighbor (ANN) search. Instead of guaranteeing that you will always find the absolute best $k$ vectors, you accept a small chance that a search result is the second- or third-best match. In exchange for this negligible deviation, search time drops from a linear scale to a logarithmic or sublinear scale.

The essence of ANN: You trade a fraction of theoretical accuracy for an enormous difference in processing speed and computing cost. For virtually all practical applications, from search engines to recommendation systems, this is an excellent trade.

In semantic search, after all, the definition of the "absolute best" outcome is rarely absolute. The quality of the text embeddings themselves already has a small margin of error. A vector that mathematically ranks eleventh instead of tenth contains essentially the same information in substance. As long as the system reliably surfaces the most relevant results, it is acceptable that the mathematically perfect neighbor is missed on rare occasions.

## What recall means for vector indexing

To determine how well an approximate index performs, the metric recall is used. Recall expresses what percentage of the true top-$k$ nearest neighbors is found by the index, compared to an exact brute-force search.

If you ask for the 10 nearest neighbors ($k=10$), and the approximate algorithm returns a list of which 9 are identical to the results of an exact brute-force calculation, the recall at that specific point is 90% (or 0.90). Recall is the most important dial for tuning a vector index:

- High recall (e.g., > 95%): The index almost always returns the exact results, but requires more computing power and memory during search.

- Lower recall (e.g., 80% - 90%): The search processes considerably faster and consumes less computing power, but the chance increases that a relevant document is skipped.

Tuning a vector index is a continuous balancing act between recall, latency (search time per query), and memory usage. Algorithms such as IVF and HNSW offer specific settings to configure this balance as desired.

## Inverted File Index (IVF) in plain language

One of the most widely used methods for approximate search is the Inverted File Index (IVF). IVF divides the entire multidimensional vector space in advance into a number of regions, also known as cells or Voronoi diagrams.

The IVF process works in two steps:

- Training and clustering: Using a clustering algorithm (usually $k$-means), the dataset is divided into $N$ clusters. The center of each cluster is called a centroid . Each vector in the database is then assigned to the nearest centroid and stored in the list for that specific cluster.

- Querying: When a search vector comes in, the system does not calculate the distance to all vectors in the database. It only calculates the distance between the search vector and the centroids. The system then searches only the vectors that fall within the nearest clusters.

With IVF, a search only needs to scan a small portion of the total database. Two important settings determine how IVF operates:

- nlist: The total number of clusters into which the space is divided in advance. A higher nlist results in smaller cells with fewer vectors per cell, which makes training take longer but reduces the search space per cell.

- nprobe: The number of cells that are actually searched during a query. This is the primary dial for setting the balance between speed and recall.

### The boundary problem of IVF

IVF has a well-known theoretical and practical problem: the boundary issue. Suppose a search vector is located right near the border of cell A. A stored vector that is very close in substance to the search vector may just happen to fall on the other side of the border, in cell B.

If the parameter nprobe is set to 1, the algorithm looks only within cell A. As a result, the vector in cell B is completely skipped, even though it is physically closer than most vectors in cell A. To fix this, you increase nprobe. If you set nprobe to, for example, 5 or 10, the system searches not only the nearest cluster but also the neighboring clusters. This significantly increases recall, but also increases the number of vectors to compare.

## Hierarchical Navigable Small World (HNSW) in plain language

An alternative and very popular approach is Hierarchical Navigable Small World (HNSW). Where IVF works with spatial division via clusters, HNSW builds a network of connections between vectors, known as a graph.

HNSW is inspired by the "small world" phenomenon from network theory and the data structure of a skip list. The index consists of multiple layers of graphs stacked on top of each other:

- Top layers: These layers contain a small number of vectors with long connections spanning large distances. Here, the algorithm makes big jumps through the vector space to quickly land in the right region.

- Middle layers: Contain more vectors and shorter connections to progressively refine the search.

- Bottom layer (Layer 0): Contains all vectors from the database, interconnected in a dense network of local neighbors. Here the algorithm performs the final refinement to identify the precise neighbors.

During a search, HNSW starts in the top layer at a fixed entry point. It navigates from node to node in the direction of the search vector as long as the distance decreases. As soon as no better neighbor can be found at that layer, the algorithm descends to the layer below and repeats this process. In this way, it quickly descends to the bottom layer, right in the correct region of the space.

### The most important settings of HNSW

The behavior and size of an HNSW index are controlled by three crucial parameters:

- M: The maximum number of connections (edges) a vector may have with other vectors per layer. A higher value for M results in a denser network. This increases recall on complex datasets, but increases memory usage per vector proportionally.

- efConstruction: The depth of the search used when building the graph when a new vector is added. A higher value produces a better-optimized graph with higher recall, but significantly extends the index build time.

- efSearch: The size of the dynamic candidate list while performing a search. This is the dial you use during querying. A larger efSearch increases the recall of the results at the cost of a longer search time per query.

## Practical trade-off between HNSW and IVF

Both indexing techniques have clear advantages and disadvantages. The choice between HNSW and IVF mainly depends on the available hardware, the size of the collection, and the required search performance.

Property | 
HNSW | 
IVF | 

Search Speed (Latency) | 
Very low at high recall | 
Moderate to low (depending on nprobe) | 

Memory Usage (RAM) | 
High (graph structure requires a lot of RAM) | 
Low to medium | 

Build Time (Indexing) | 
Slower (intensive graph building) | 
Faster (computing clusters) | 

Scalability on Disk | 
Poor (requires random RAM access) | 
Combines well with compression and disk storage | 

Suitable for | 
Real-time systems with high recall requirements | 
Large-scale datasets with a limited budget | 

In practice, HNSW often delivers better performance when it comes to the combination of low search time and high recall. The price you pay for this is memory usage. Because each vector in the graph must keep track of multiple pointers to neighbors, an HNSW index can require significantly more working memory than the raw vectors themselves. IVF, by contrast, has a much smaller memory footprint and can be trained faster.

If you want to configure a solution yourself, you can consult the guide on [setting up a vector database locally](https://gids.llmnet.nl/en/lokale-vector-database-opzetten). For a broad overview of which software solutions support which indexes, you can view the overview of [vector databases compared](https://directory.llmnet.nl/en/vector-databases-vergeleken) .

## Vector Compression: Quantization

In addition to how the search space is structured (via clusters or graphs), memory footprint plays a decisive role. Floating-point numbers (float32) take up 4 bytes per dimension. A vector with 1536 dimensions therefore costs just over 6 kilobytes of RAM. With one hundred million vectors, this adds up to hundreds of gigabytes of working memory.

To solve this, vector compression is often applied, also known as quantization . This is a separate technique that can be applied on top of both IVF and HNSW:

- Scalar Quantization (SQ): Converts 32-bit floating-point numbers into, for example, 8-bit integers (SQ8). This reduces the memory usage of the vectors by nearly 75%, with only a small loss of precision.

- Product Quantization (PQ): Splits the vector into smaller sub-vectors and replaces each sub-vector with a reference to a representative codebook value. This achieves even stronger compression, allowing large-scale databases to fit entirely in RAM or be read quickly from SSD.

When you combine IVF with Product Quantization (IVF-PQ), you get an index structure that handles memory very efficiently, although this results in a slightly lower maximum recall than an uncompressed HNSW index.

## Mutations in the index: Adding and removing

A static dataset is easy to index, but in practice data changes continuously. What happens when you add or remove vectors?

In HNSW adding new vectors is relatively straightforward. The new vector searches the existing graph to find its nearest neighbors and immediately forms connections with them there. Removing, however, is more complex: when a node is deleted from a graph, the surrounding connections must be restored to prevent gaps in the network. Many implementations therefore use 'tombstones' (soft deletes) and only clean up the graph later.

In IVF adding a new vector requires determining the nearest centroid, after which the vector is added to that specific cell. If the distribution of the data changes significantly over time (data drift), the original centroids can end up poorly positioned. Some cells become too large while others remain empty.

In both cases, continuous mutations lead to fragmentation and quality loss of the index. To keep tuning times and quality optimal, periodic maintenance is necessary. More technical information about this can be found in the article on [vector index maintenance](https://api.llmnet.nl/en/vector-index-onderhoud).

## How do you choose the right strategy yourself?

Selecting and tuning the right vector index requires a structured approach. Follow these steps when setting up your production environment:

- Analyze the size and available hardware: Determine how many vectors you expect and how much RAM is available on the servers. Can the full set, including the graph structure, fit in RAM? If there is enough memory, choose HNSW. If memory is limited, consider IVF or a compressed index (SQ/PQ).

- Set up a representative test dataset: Don't just use random test data; instead, gather a set of real search queries from your application. Create an exact 'ground truth' by running a brute-force k-NN search on a small portion of the data.

- Measure and optimize recall: Adjust the settings (such as efSearch for HNSW or nprobe for IVF) step by step and compare the results with your 'ground truth'. Determine which setting delivers the minimum required recall (for example, 95%).

- Only then measure latency and throughput: Once the desired recall has been established, measure the average search time and the number of searches processed per second under load. If necessary, adjust the build parameters (such as M or nlist) to find the optimal balance for your infrastructure.

## Further reading

- [Embeddings Explained: The Basis of Semantic Search](https://leren.llmnet.nl/en/embeddings-uitgelegd)

- [From Text to Numbers: Embeddings in Practice](https://leren.llmnet.nl/en/van-tekst-naar-getallen-embeddings-praktisch)

- [RAG for Beginners: An Introduction to Information Retrieval](https://leren.llmnet.nl/en/rag-voor-beginners)

- [Guide: Setting Up a Local Vector Database](https://gids.llmnet.nl/en/lokale-vector-database-opzetten)

- [Comparison of Popular Vector Databases and Providers](https://directory.llmnet.nl/en/vector-databases-vergeleken)

- [API & Best Practices for Vector Index Maintenance](https://api.llmnet.nl/en/vector-index-onderhoud)

llmnet.nl - learning and explanations about language models