Vector Search and Hybrid Ranking
Lesson 4 of 4 in RAG Mechanics: Embeddings and Search.
Nearest-neighbor search sounds finished the moment you say it: compare the query vector with every stored vector, sort, take the top k. That exact search is correct by definition and perfectly fine for a corpus of tens of thousands of chunks — modern hardware chews through a few million dot products without complaint. But it is linear in corpus size, per query. At tens or hundreds of millions of vectors, times your dimensionality, times your queries per second, brute force becomes a hardware bill with no ceiling.
The escape is to stop demanding perfection. Approximate nearest-neighbor (Approximate nearest neighbor (ANN)) search builds a data structure at ingest time that lets a query inspect a tiny, well-chosen fraction of the corpus and still find almost all of the true nearest neighbors — trading a little recall for orders-of-magnitude less work. Every serious Vector database is built around some ANN index, and the canonical one is HNSW — Hierarchical Navigable Small World graphs (Malkov & Yashunin, 2016).
A vertical stack of three layers illustrating an HNSW index. The top layer is labeled as a sparse few vectors with long-range highway links and is the search entry point. The middle layer holds a larger sample of vectors with medium-range links for regional navigation. The bottom layer, layer zero, contains every vector with dense short-range links, where the final careful neighborhood walk happens.
The “navigable small world” idea is that a graph mixing long-range and short-range links can be traversed greedily — always hop to whichever neighbor is closest to the query — and still reach the right neighborhood fast. The hierarchy adds coarse-to-fine routing: top layers make continent-scale jumps, the bottom layer walks the street. Three parameters matter conceptually: how many links each node keeps (more links, better navigation, more memory), how much effort construction spends wiring good neighborhoods (paid once, at ingest), and the query-time beam width — often called efSearch — which sets how many candidates the search keeps alive as it explores. That last one is the dial you will actually turn in production: widen it for recall, narrow it for speed. The paper reports search cost scaling roughly logarithmically with corpus size — which is the entire miracle: from linear to log-ish, at the price of “almost all” instead of “all”.
HNSW is not alone. Partition indexes cluster the space and probe only a few cells per query; compression schemes like product quantization shrink each vector so more corpus fits in memory, trading precision for footprint. You meet these as configuration options in the tools: FAISS, the library that popularized many ANN methods; pgvector, which puts vector indexes inside Postgres next to the relational metadata you already trust; OpenSearch and its relatives, which bolt ANN onto a classic search engine — convenient, as you are about to see, for hybrid. Cloud-managed vector stores exist on every platform; the LLMs on the Cloud domain carries those specifics.
Recall@k versus latency — the curve you are actually tuning
Recall@k is the honest score for an ANN index: of the k true nearest neighbors (as exact brute-force search would return them), what fraction did the approximate search find? Recall 0.95 at k = 10 means that, on average, half a relevant neighbor per query silently went missing. Measuring it is cheap enough to be mandatory: run exact search over a sample of a few hundred real queries as ground truth, compare, done. No leaderboard can tell you this number — it depends on your vectors’ geometry.
Plot recall against query latency as you widen the search beam and you always get the same shape: a steep climb, then a plateau that bends into a wall. Early effort is cheap — recall leaps from 0.8 to 0.95 for small latency. The last few points are brutal: pushing 0.99 toward 1.0 can cost multiples of the latency budget, because the search must effectively stop trusting the graph and inspect ever-larger candidate pools. Where you sit on the curve is an engineering decision, not a correctness one — and it should be made looking at end-to-end answer quality, since a missing neighbor only matters when it was the evidence.
One more wrinkle: metadata filters interact with the graph. “Only 2025 contracts this user may read” shrinks the eligible set, and a graph traversal that keeps landing on filtered-out nodes wastes its beam — or worse, gets stranded in an ineligible region. Engines differ in strategy: post-filtering results (fast, but can return fewer than k), pre-filtering into a temporary candidate set, or checking the filter during traversal. Highly selective filters are where ANN indexes get embarrassed; test yours with the filters your product will really use.
Now bring back lesson 1’s two signals. Hybrid search runs dense ANN retrieval and lexical BM25 retrieval in parallel and merges the lists — because embeddings find the paraphrases and BM25 finds the error codes, and your users will send you both in the same afternoon. The merge has a subtlety: cosine similarities and BM25 scores live on incomparable scales, so naive score-mixing rewards whichever scale runs hotter. The standard fix is rank-based fusion — combine each document’s positions in the two lists rather than its raw scores; reciprocal rank fusion, which scores each document by summing the reciprocal of its rank in every list, is the common recipe precisely because it needs no score calibration at all.
Two closing notes on where this machinery hands off. The fused shortlist is still bi-encoder-and-keyword quality — the next module’s Reranking lesson puts a Cross-encoder on top of it to re-judge the top few dozen candidates properly. And metadata filters doing security work — tenant isolation, per-user document permissions — are load-bearing: retrieval that ignores ACLs is a data leak with extra steps, a thread the Security & Risk domain picks up.
In production
Managed platforms differ in branding, but each sells the same triangle: recall, latency, and cost. The index type and its parameters decide which corner you sit in — and the dials in this lesson are exactly the dials the consoles expose.
AWS
Amazon OpenSearch Service exposes ANN indexes (including HNSW-style graphs) alongside classic BM25 scoring, making hybrid ranking a single-system exercise; pgvector on RDS and Aurora puts vectors next to the relational metadata you filter on; Bedrock Knowledge Bases packages the chunk–embed–index–retrieve loop as a managed pipeline. Under every option the same mechanisms hold: memory scales with dimensions × rows, and your recall target sets your latency and instance footprint.
Azure
Azure AI Search treats hybrid as a first-class posture: HNSW-based vector search with tunable graph parameters, fused with BM25 full-text ranking, plus an optional reranking stage on top. The mapping to this lesson is one-to-one — graph parameters trade recall for latency, and filterable metadata fields decide which documents enter the candidate set at all.
Google Cloud
Vertex AI Vector Search is a managed ANN service aimed at high recall at large scale: you choose an operating point on the recall/latency curve and the platform manages index infrastructure; pgvector on Cloud SQL and AlloyDB covers the Postgres path. Whichever route you take, re-embedding after a model change and index rebuilds remain your costs to plan — the LLMs on the Cloud domain prices these paths out.
Interactive checkpoint quiz (1 questions) — open this page in a browser to take it.