Skip to content
Road to Intelligence

Concept · Chapter 12: Embeddings, RAG & the LLM Application Stack

Approximate Nearest-Neighbour Search

Must knowKnow well16 minDifficulty

Approximate nearest-neighbour indexes find the vectors most similar to a query without comparing it to every stored vector, by searching only promising clusters (IVF) or walking a proximity graph (HNSW), giving up a little recall for a large speed-up.

The problem

Exact search compares the query with every stored vector: fine for thousands, too slow and memory-hungry for hundreds of millions.

The solution

Organise the vectors in advance: cluster them and probe only the nearest few clusters (IVF), or link each vector to its neighbours in a layered graph and descend greedily (HNSW); compress vectors (product quantization) to fit more in memory.

The consequence

Vector search over millions or billions of items became fast and cheap enough for interactive use, at the price of occasionally missing a true neighbour and of tuning knobs (lists probed, graph width) that trade recall for latency.

You should understand first

  1. Vectors
  2. Dot Product
  3. Embeddings
  4. Attention
  5. Probability and Distributions
  6. Softmax
  7. Self-Attention
  8. Multi-Head Attention
  9. Causal Masking
  10. Positional Encoding
  11. Residual Connections
  12. Layer Normalization
  13. Feed-Forward Sublayer (MLP)
  14. The Transformer Block
  15. Encoder, Decoder & Encoder–Decoder
  16. Text Embeddings
  17. Text as Data
  18. Keyword Search and BM25
  19. Semantic and Hybrid Search
  20. The Turing Test
  21. Symbolic AI
  22. Logic and Rules
  23. Expert Systems
  24. Knowledge Representation
  25. The Knowledge-Acquisition Bottleneck
  26. From Rules to Learning
  27. Supervised, Unsupervised and Self-Supervised Learning
  28. k-Means Clustering
  29. Approximate Nearest-Neighbour Search

The cost of looking everywhere

Exact search computes one dot product per stored vector. With 10 million passages of 768 dimensions, that's 7.7 billion multiply-adds per query (our arithmetic), and the vectors themselves take about 31 GB in 32-bit floats. Fine for a batch job, slow for a chat box, and every additional user multiplies it. The way out is the same as for a database: build an index in advance so a query only touches a small part of the data.

IVF: search the nearest clusters only

An inverted-file index clusters the vectors with k-means into, say, 1,000 lists. Each list has a centroid. To search:

  1. Compare the query with the 1,000 centroids.
  2. Pick the nprobe closest lists.
  3. Scan only the vectors in those lists.

With nprobe = 10, a query scans about 1% of the collection. It can miss a true neighbour that sits just across a cluster boundary, so recall rises with nprobe and so does the work. The lab below runs this on this site's own chunk embeddings.

HNSW: walk a graph of neighbours

Hierarchical Navigable Small World graphs build a multi-layer structure of proximity graphs over nested subsets of the stored elements; each element's maximum layer is chosen randomly with exponentially decaying probability, and search starts from the top layer, which allows logarithmic complexity scaling Established.

Think of a skip list, or of flying, then driving, then walking: the sparse top layer has long links that cover the space in a few hops; each lower layer is denser and refines the position; the bottom layer contains every vector. A search moves greedily to whichever neighbour is closest to the query, layer by layer. A search-width parameter keeps several candidates alive to avoid dead ends, trading speed for recall.

Compressing the vectors

Memory is often the limit. Product quantization splits each vector into, say, 8 pieces and replaces each piece by the index of the nearest of 256 learned centroids: 8 bytes instead of 3 KB for a 768-dimensional float vector. Jégou, Douze and Schmid showed that distances can be estimated directly from such codes Established. The FAISS paper's GPU implementation made nearest-neighbour search 8.5× faster than the previous GPU state of the art and built a k-NN graph over 1 billion vectors in under 12 hours on four GPUs Established. Chapter 11's quantization is the same trade: fewer bits, a little error.

What a "vector database" is

These indexes plus the database parts: storage, updates and deletes, filtering by metadata (only this user's documents, only after this date), replication. Filtering interacts with the index, since a cluster or graph built for all documents isn't built for a filtered subset; that interaction is a common source of surprising misses.

Why should I care?

As a researcher

The recall–latency trade-off of an index is part of every retrieval result; a retrieval paper's numbers depend on whether the search was exact.

As an engineer

Index type, its parameters and vector compression decide your search latency, memory bill and how often the right passage is silently missed.

Modern systems that depend on it

  • vector databases
  • RAG at scale
  • recommendation systems
  • deduplication of embeddings

Historical context

Before

Every query scanned every stored vector, so cost grew linearly with the collection.

After

A query touches a small fraction of the vectors (a few clusters, or a short path through a graph) and still finds most of the true nearest neighbours.

Used today

Vector databases and libraries such as FAISS offer IVF, HNSW and product quantization; HNSW is a common default for in-memory search.

What to remember

  • Exact search: one dot product per stored vector per query.
  • IVF: k-means clusters; probe the nprobe nearest clusters. More probes, more recall, more work.
  • HNSW: layered neighbour graph, greedy descent from coarse to fine; logarithmic scaling.
  • Product quantization compresses vectors to a few bytes for memory-bound search.
  • Measure recall@k against exact search; 'approximate' means it can miss.

Key papers

Important

Product Quantization for Nearest Neighbor Search

Hervé Jégou, Matthijs Douze, Cordelia Schmid · 2011 · IEEE TPAMI

Showed how to compress high-dimensional vectors to a few bytes each and still estimate distances, the basis of billion-scale vector search.

~1 h readdoi:10.1109/TPAMI.2010.57✓ verified 2026-10-05
Important

Billion-scale similarity search with GPUs

Jeff Johnson, Matthijs Douze, Hervé Jégou · 2017

The paper behind FAISS, the library that made exact and compressed vector search fast on GPUs and that many RAG systems still use.

~45 min readarXiv:1702.08734✓ verified 2026-10-05