AdversariaLLM
All About LLMs, from AI to Z· Lesson 31 of 80

RAG & Knowledge Systems · 7 min

Embeddings as a Search Index: Dense Vectors and Approximate Nearest Neighbors

How an embedding model becomes a retrieval index, why brute-force cosine search stops scaling, and how HNSW and FAISS trade a sliver of recall for orders-of-magnitude speed.

You met embeddings in Module 1 as the model's internal handle on meaning: a chunk of text goes in, a fixed-length vector comes out, and texts that mean similar things land near each other. Here we put that property to work as an index. The move is almost embarrassingly simple. Encode every chunk in your corpus once, store the vectors, and at query time encode the user's question with the same model. Retrieval becomes geometry. Find the stored vectors closest to the query vector, return the chunks they came from.

That "same model" clause carries the whole idea. Query and documents have to live in one shared space, or the distances mean nothing. This is the dense-retrieval framing that Karpukhin et al. formalized as DPR (Dense Passage Retrieval): two BERT-based encoders, one for passages and one for questions, trained so a real question sits close to the passage that answers it. The output is a 768-dimensional vector, and relevance is scored by dot product between question and passage. Their headline result is the reason this module exists. On open-domain QA, dense retrieval beat a tuned Lucene BM25 keyword system by 9 to 19 percentage points of absolute top-20 accuracy. Matching on meaning rather than shared tokens finds the passage that says "the capital was moved to Ankara in 1923" for a query about "Turkey's seat of government," where lexical search sees no overlapping words at all.

Similarity: dot product and cosine

Two metrics dominate, and they are closely related.

  • Dot product: a·b = Σ aᵢbᵢ. Sensitive to vector magnitude as well as direction.
  • Cosine similarity: the dot product of the normalized vectors, a·b / (‖a‖‖b‖). Pure direction, range −1 to 1.

If you L2-normalize every vector to unit length at index time (a one-line preprocessing step), dot product and cosine produce the same ranking, and Euclidean distance orders results the same way too. Most systems do exactly that, then use whichever metric their index library optimizes. Watch one trap: check what your embedding model was trained with. DPR wants raw dot product. Many sentence-embedding models want cosine. Mix them and nothing errors, results just quietly get worse.

Why exact search stops scaling

Brute force is honest and, for a while, fine. To find the nearest neighbors you compute the query's similarity against every stored vector and keep the top k.

query q (768-d)                corpus matrix  N × 768
   [····]           ·           [row 0  ····]
                                [row 1  ····]   →  N dot products
                                [ ...       ]   →  sort, take top-k
                                [row N-1····]

The cost is O(N · d). With d = 768 and a modest million chunks, that is roughly 768M multiply-adds per query: tens of milliseconds on a CPU with a good BLAS library, and it grows linearly. At 100M vectors you are into seconds per query and hundreds of gigabytes of RAM just to hold the float32 vectors (100M × 768 × 4 bytes ≈ 300 GB). Exact search never breaks. It just gets too slow and too expensive to serve interactively. That is the wall approximate nearest-neighbor (ANN) structures exist to climb over.

Builder: below a few hundred thousand vectors, don't reach for an ANN index. Flat brute-force search (FAISS IndexFlatIP) is exact, has zero tuning knobs, and is often faster end to end than you would guess. Add approximation when latency, not correctness, becomes the problem.

The trade you're actually making

ANN buys speed by giving up the guarantee that you found the true top-k. You measure the loss as recall@k: of the k items exact search would return, what fraction did the approximate index return? Recall of 0.95 at k=10 means it missed roughly one true neighbor in twenty, in exchange for a 10 to 100× speedup. Whether that is a good deal is a product question. For RAG feeding an LLM, near-miss neighbors are usually still relevant, so slightly imperfect recall costs little.

HNSW: navigate a graph of neighbors

Hierarchical Navigable Small World graphs (Malkov and Yashunin) are the workhorse. Build a graph where each vector links to its near neighbors, then stack it in layers. The top layer is sparse, a few long-range links spanning the whole space. Each layer down is denser and more local. Search enters at the top, greedily hops toward the query, drops a layer, refines, and repeats.

Layer 2   A -------------- G            sparse, long hops
              \           /
Layer 1   A --- C --- E --- G           medium
             \   |     |   /
Layer 0   A-B-C-D-E-F-G-H-I-J           dense, every node
          entry → greedy hop → descend → local refine → top-k

It has the feel of binary search in high dimensions: coarse jumps first, fine steps last. Search cost scales roughly logarithmically with corpus size instead of linearly, and that property is what keeps 100M-vector search interactive. Three knobs matter. M, links per node, trades memory and build time for recall. efConstruction sets how hard the builder works. efSearch is the runtime dial: raise it and the greedy search explores more candidates, recall climbs, and latency climbs with it. That last one is your live recall-versus-latency lever in production.

Now the honest costs. HNSW lives in RAM, and the graph overhead can rival the vectors themselves. Deletes are awkward too. Most implementations tombstone rather than truly remove, so churn-heavy corpora need periodic rebuilds.

FAISS: quantize and shortlist

FAISS (Johnson, Douze, Jégou) attacks the other bottleneck, memory and raw distance cost. Two ideas you will actually configure:

  • IVF (inverted file): cluster the corpus into, say, 4096 cells with k-means. At query time, probe only the nprobe nearest cells instead of all N vectors. nprobe is the recall dial. Set it to 1 and search is fast and lossy; set it to 64 and it is slower and thorough.
  • PQ (product quantization): chop each 768-d vector into subvectors and replace each with a small codebook id. A vector that took 3072 bytes compresses to about 64, and distances are computed on the compressed codes with lookup tables. That compression is how the paper searched a billion vectors on a handful of GPUs. Without it, the data simply would not fit.

PQ makes distances approximate twice over, once from quantization and once from cell pruning. So pipelines often over-fetch compressed candidates, then re-rank the shortlist against full-precision vectors.

Defender: the index is an exfiltration surface. Anyone who can query it can attempt embedding-inversion attacks, reconstructing recognizable source text from returned vectors, or membership inference to confirm a specific document is in the corpus. Treat stored embeddings as about as sensitive as the plaintext they encode: same access controls, plus per-tenant index isolation so one customer's query can't surface another's chunks.

What actually goes wrong

  • Silent metric mismatch. A cosine model indexed under raw dot product, or normalization skipped. No error, just mediocre results everyone blames on "the LLM."
  • Chasing recall@k against the wrong ground truth. Recall is measured against exact search, which is itself only as good as your embedding model. 0.99 recall on a weak encoder still retrieves weak chunks.
  • Dimension and model drift. Re-embed the corpus with a new model but keep serving old query vectors and the geometry turns to nonsense. Any model change means a full re-index, so version your embeddings.
  • Cold-start latency. HNSW graphs load into RAM at startup. A 50 GB index means a slow, memory-hungry boot. Budget for it.

Researcher: the classic recall benchmarks (SIFT1M, GIST) use image descriptors whose geometry differs from text embeddings, so a published recall/latency curve on them may not transfer. Newer suites like VIBE build their ground truth from modern text and multimodal embedding models specifically. Reach for those before trusting a number for your workload.

This lesson gets candidates onto the table fast. It says nothing about whether the top hit is the best answer, because approximate ranking is coarse by design. That is the next lesson's job (reranking), where a slower cross-encoder rescores the shortlist that HNSW or FAISS hands it.

Sources