Loading...
System Design and AI Engineering, by Roni Das. 980 interactive lessons.
Start LearningAI Engineering · Advanced · LLM and GenAI Ops
Search that finds vectors close to a query without scanning every item, trading a small chance of missing a true neighbor for a large gain in speed. HNSW and IVF are the common indexes.
In short
Approximate nearest neighbour (ANN) search finds the stored vectors closest to a query without comparing it with every one. It does far less work per query, in exchange for sometimes missing a true neighbour, so you must measure what it misses.
In short
Approximate nearest neighbour (ANN) search finds the stored vectors closest to a query without comparing it with every one. It does far less work per query, in exchange for sometimes missing a true neighbour, so you must measure what it misses.
Learn it in the course
This page is the free part.
₹999 in India$49 everywhere elseonce, for the whole course
The AI Engineering course covers ANN across a run of lessons, not one page. These 4 alone are about 243 minutes of step-by-step reading, every one with code you run in the browser, all with a quiz.
Exact search compares a question with every stored piece. Clustered search groups the pieces first and looks only in the nearest groups. Measured on 470 quiz questions and 1,823 pieces with nomic-embed-text and 32 clusters: searching 8 clusters, about a third of the comparisons, found 94 to 95% of the exact top 5 and kept 429 to 430 of 441 right lessons. Searching 1 cluster did 6% of the work and found the right lesson in the top 5 for 338 to 349 of 470.
How embeddings become searchable points in space, why exact nearest-neighbor search breaks at scale, and how ANN indexes like HNSW, IVF, and PQ make retrieval fast enough to serve.
Every labelled dataset has some wrong labels. On 1,797 real handwritten digits, a lab makes up to 40 percent of the training labels wrong, randomly or by swapping look-alike digits, and trains four kinds of model. Nearest neighbour copied mistakes straight through, while a forest and 15 nearest neighbours barely noticed random ones. From 20 percent up, look-alike mistakes did far more damage. Flagging every row where an out-of-fold prediction disagreed with its label found almost all the random mistakes, but was fooled by repeated confusions. A random forest asked about the rows it trained on flagged none of them, and wrong labels in the test set lowered an unchanged model's score by about the same share.
The whole fine-tuning decision in the order you would make it, each step backed by a result this chapter stored, plus one new measurement: what a ticket costs. On quality, the fine-tuned 1.5B could not be told apart from the prompted 14B, on the 131 test messages (102 against 93, p 0.1628) or on 53 new ones (21 against 25, p 0.4240). On cost, the fine-tune read 54 prompt tokens a call against 642, and in an interleaved timing on one laptop the 14B took 3.63 times as long per message. My first timing failed its own drift check, and the lesson shows why a timing needs a control. The price of the fine-tune: data work, training, a new test after every change, and far less resistance to an attack without a schema (102 to 23).
all part of
AI Engineering
210 lessons · about 219 hours · 10 free to read
₹999in India, by UPI
$49everywhere else, by PayPal
pay once,
yours for life
Vector search answers one question: which stored embeddings are closest to the query's embedding? The simplest way, called exact or brute-force search, compares the query with every stored vector. It never misses. Its cost is one comparison per stored vector, and each comparison multiplies every number in the two lists.
Count it. With 768 numbers per vector and 1,823 stored pieces of text, exact search does 1,823 x 768 = 1,400,064 multiplications per question, which a laptop finishes in a fraction of a second. With one million pieces, it becomes 768,000,000 multiplications per question, and you pay that again for every user asking at the same time. The work grows in a straight line with the data.
Approximate nearest neighbour search, or ANN, is the answer. It spends some work once, in advance, to organise the vectors, so each question can skip most of them. The price is that it may skip a true neighbour. It is like a library sorted by subject: you walk to the right shelf, and you can miss a good book that was put on an unexpected shelf.
A clustered index, called IVF (inverted file), first groups the vectors with k-means: pick some vectors as centres, give every vector to its nearest centre, move each centre to the average of its group, and repeat. At query time, it compares the question with the centres, keeps the nearest few clusters, and searches only inside them. The number of clusters searched is called the probes, and it is the dial you turn.
A graph index, HNSW, links each vector to a few of its near neighbours in several layers, and a search walks along those links towards the query. Its dial is ef_search, the size of the candidate list kept during the walk. A third family, product quantization (PQ), is compression rather than a search method: it shrinks each vector to a short code so many more vectors fit in memory, and it is usually combined with IVF.
Every ANN index has such a dial. Turn it up, and the search looks at more of the data, so it misses less but takes longer. Turn it down, and it is faster but misses more. The number that measures this trade is recall: of the results exact search would return, the share the fast search also found.
In a measured lab run, 1,823 pieces of text from 112 lessons were embedded with nomic-embed-text, grouped into 32 clusters, and searched with 470 quiz questions. k-means was run from three different random starts. Work was counted as comparisons, including the 32 comparisons with the centres.
Searching 1 cluster took about 105 comparisons, 6 percent of exact search, and found 53 to 59 percent of the exact top 5. Searching 8 clusters took about 584 comparisons, 32 percent of the work, and found 94 to 95 percent. Searching 16 took about 1,085, 60 percent of the work, and found about 99 percent. Exact search put the right lesson in the top 5 for 441 of 470 questions; 8 probes managed 429 to 430, and 16 probes 439 to 440.
Two details surprise people. Searching all 32 clusters cost 1,855 comparisons, slightly more than exact search's 1,823, because the centres are extra work, so clustering only pays when you search a fraction of the clusters. And with 1 probe, the random start mattered a lot: the three starts found the right lesson for 349, 343 and 338 questions, while at 16 probes they differed by one.
The index is built once, and that is real work. Building the 32 clusters above took 1,823 x 32 = 58,336 comparisons per round for 25 rounds, 1,458,400 in all, about as much as 800 exact searches. As new vectors arrive, the clusters slowly stop fitting the data, so an IVF index needs rebuilding from time to time. HNSW grows as you insert, but keeps its graph in memory on top of the vectors.
Misses are silent. A search that skipped the right cluster still returns results and no error. A piece at the edge of a cluster can be closer to the query than its cluster's centre suggests, and that is exactly the kind of piece that gets missed. In a nine-text example, a text about a token bucket, which is a rate-limiting method, landed in a cluster with caching texts and was never compared with a rate-limiting question.
The dial does not stay tuned as data grows. For HNSW, a setting that reaches a target recall on one million vectors can reach less on ten million, because the walk visits a smaller share of a bigger graph. Filters add another trap: if a store fetches the top results and then filters by category, you can get back far fewer rows than you asked for. Measure recall against exact search on a sample of real queries, and measure it again as the index grows.
Start with exact search. For a few thousand vectors it is already fast and never misses, and an index only adds a training step, a random start and a new way to lose answers. A common rule of thumb says brute force is fine up to around ten thousand vectors. Switch when exact search becomes slower than your users will wait.
Then turn the dial on purpose. Raise the probes or ef_search until misses are rare enough for you, and always report speed together with recall. A pure-Python measurement of 30 indexes built with locality-sensitive hashing (LSH), a method that sorts vectors into buckets with random cuts, over 20,000 generated vectors shows why: its fastest setting ran 858 times faster than brute force and returned 0.4 percent of the right answers.
Be careful where every match must be found, such as a legal search where missing one document is a real failure. Use exact search there, or a very high dial setting. To measure your own trade, take a few dozen questions, save exact search's top 5 for each, and count, for each setting, how many of those the fast search also finds.
FAISS
Meta's open-source library for vector search, which provides flat, IVF, product quantization and HNSW indexes.
Annoy
An open-source ANN library released by Spotify, built for music recommendation lookups.
hnswlib
An open-source C++ and Python library that implements the HNSW graph index.
pgvector
A PostgreSQL extension that offers two ANN index types, ivfflat and hnsw, alongside exact search.
Exact search compares the query with every stored vector and never misses. Approximate search organises the vectors in advance and compares the query with only some of them, so it is much faster but can miss a true neighbour. You choose how much it may miss with a dial.
Recall is the share of the true nearest neighbours, as found by exact search, that the approximate search also returned. Recall of 0.95 at 10 means it found 95 percent of the true top 10. Measure it by running the same queries through both searches.
There is no fixed number, but for a few thousand vectors exact search is usually fast enough, and some teams use around ten thousand as a rule of thumb. Switch when exact search becomes slower than your latency budget, not before.
HNSW builds a layered graph and walks it towards the query; it usually gives the best recall for the time spent but keeps its graph in memory. IVF groups vectors into clusters with k-means and searches only the nearest clusters; it needs a training step and can miss neighbours near cluster edges.
The store may fetch the nearest results first and filter them afterwards, so most of the nearest can be dropped. Use a store that applies the filter during the search, or settings such as pgvector's iterative index scan in version 0.8 and later.
Vector Databases and Approximate Nearest Neighbor Search
How embeddings become searchable points in space, why exact nearest-neighbor search breaks at scale, and how ANN indexes like HNSW, IVF, and PQ make retrieval fast enough to serve
Approximate Nearest Neighbor (ANN)
The algorithms that make vector search fast. HNSW, IVF, LSH, and how they trade accuracy for speed
Business Continuity Planning
Keep the business running during disruptions, beyond IT into organizational resilience
Capacity Planning
Forecast resource needs before you run out, load testing, traffic modeling, and growth projection
Vulnerability Scanning
Automated detection of known weaknesses in systems, networks, and applications
Vector Database
A database that stores embeddings, lists of numbers that capture the meaning of text or images, and finds the ones closest to a question's embedding. It powers semantic search and RAG.
HNSW
Hierarchical Navigable Small World, a graph-based nearest neighbor index that gives high recall at low latency by navigating layers of links, at the cost of more memory than IVF.
Embedding
A list of numbers that represents the meaning of a piece of text, so that similar meanings sit close together in vector space. The same model must embed both the corpus and the query.
RAG (Retrieval-Augmented Generation)
A pattern that retrieves relevant text from an external index and puts it in the model's prompt so the answer is grounded in current, verifiable facts rather than the model's memory.
Agentic RAG
Agentic RAG is RAG where a language model runs the search in a loop. It decides whether to search, what to search for and where. Then it checks if the text it found answers the question.
Reranking
A second retrieval stage where a cross-encoder scores each candidate chunk against the query directly. Slower than the first-stage retriever but far more precise, so it runs only over the top few dozen results.
This page explains the idea. The "Finding Neighbours Fast: Search a Few Clusters Instead of Everything" lesson builds it up step by step, with diagrams. It is part of the AI Engineering course, which has 210 lessons. 10 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Finding Neighbours Fast: Search a Few Clusters Instead of Everything lessoncourse 2
Take models from notebook to production, with labs on real models.