How does the ANN (Approximate Nearest Neighbor) works?

If you are working with the RAG applications then you would have heard this terminology a lot, but what exactly is ANN.

ANN stands for Approximate Nearest Neighbor

It is a technique which is used to find the points which are “close” to the given point in a high-dimensional space.

Let’s start with an example,

Imagine a number line:

• Adi is standing at 1
• Arvind is standing at 4
• Ankur is standing at 5.

If Ankur wants to find the nearest person, he will find that Arvind is closer than Adi because.

• Distance between Ankur and Arvind = |5 - 4| = 1
• Distance between Ankur and Adi = |5–1 |= 4

In this scenario finding the nearest neighbor is easy because we are dealing with only one dimension.

Now imaging instead of the number line we have have the documents represent as vectors.

A sentence such as:

“Cats are pets.”

might be converted as an embedding model into something like:

[0.54, -0.76, 0.45, .....]

Similarly

“Dogs are not pets.” will be another vector.

Modern embedding models produces the vectors of 768, 1024, 1536, or even more dimensions which can be pretty hard for us to visualize but mathematically we can calculate ‘How close which vector is to each other’.

The problem with Exact Search

Let’s say we have a vector database which contains

• 1000 vectors
• 100000 vectors
• 10 million vectors

When a user asks a question then the embedding of the question will be generated and system tries to find the most similar vectors.

The common approach will be .

1. Compare the query vector with every vector in the db.
2. Calculate the similarity score.
3. Return the closest match.

This is called Exact Nearest Neighbor Search

The issue with this as the number of vectors grows, the search becomes more expensive.

For a db with millions of vector this will be absolute nightmare to compare every vector against the query. It will lead to the slow and costly computation.

Enters ANN

ANN solves this exact problem by trading a tiny amount of accuracy for a huge gain in speed.

Instead of checking every vector, ANN uses specialized algo and data structure to quickly narrow down the space search.

Think of something like finding a book in the library.

Exact Search

You inspect every book one by one until you find the best book.

ANN Search

You first go the correct floor of the library. Then go the correct section then go the self, and then inspect the few books.

You may or may not find the exact match, but will find the extremely close match at much faster speed.

But why Approximate??

Because ANN does not guarantee the returned vector is the closest one.

Instead it guarantee like, “I found a vector which is extremely close to the nearest neighbor with 99% confidence, but I did at much faster speed.”

For most of the RAG application this tradeoff is acceptable.

Popular ANN Algorithms

HNSW (Hierarchical Navigable Small Worlds)

One of the most popular ANN algo today.

It creates multiple graph layers where vectors are connected to the nearby vectors.

When searching:

1. Start from the high level overview graph
2. Move towards the similar nodes
3. Descend to the more detailed layers
4. Reach the closest candidates quickly.

There are others such as IVF (Inverted File Index) and Product Quantization (PQ)

How ANN Fits into RAG

A typical RAG pipeline looks like this:

User Query
    ↓
Embedding Model
    ↓
Query Vector
    ↓
ANN Search
    ↓
Top Relevant Chunks
    ↓
LLM
    ↓
Final Response

when a user asks:

“What is the refund policy?”

the system:

1. Converts the question into an embedding.
2. Uses ANN to find similar document chunks.
3. Retrieves the top-k relevant chunks.
4. Sends them to the LLM as context.
5. Generates the answer.

Without ANN, retrieval over millions of chunks would be too slow for real-time applications.

Why ANN Matters

ANN is one of the key technologies that makes modern RAG systems practical.

Without it:

• Vector databases would be slower.
• Retrieval latency would increase.
• Costs would rise significantly.
• User experience would suffer.

With ANN, we can search through millions (or even billions) of embeddings in milliseconds while maintaining high-quality retrieval.

In the next blog we will be exploring the ANN algos individually.

Untill then cheers!