Neural Search & Vector Embeddings: Approximate Nearest Neighbors (ANN) and HNSW

While lexical search engines powered by BM25 excel at exact keyword and Boolean matching, they remain fundamentally blind to semantic concepts, synonyms, and natural language intent. A search for "portable power source for remote camping" may completely fail to retrieve articles discussing "outdoor solar generators and lithium battery packs" if exact keywords do not overlap. Neural search resolves the vocabulary mismatch problem by transforming queries and documents into continuous, high-dimensional dense vector embeddings using deep transformer encoders. Finding relevant documents shifts from set intersection to Approximate Nearest Neighbor (ANN) vector search across billions of dimensions using HNSW (Hierarchical Navigable Small World) graphs.

1. Lexical Search vs. Dense Vector Retrieval

Contrasting sparse lexical retrieval against dense neural vector representations:

2. Hierarchical Navigable Small World (HNSW) Graphs

Originally formulated by Malkov and Yashunin, HNSW is the state-of-the-art vector indexing algorithm utilized in Milvus, Qdrant, Pinecone, and Weaviate. HNSW organizes multi-dimensional vectors into a multi-layered geometric graph inspired by probabilistic skip-lists:

• Multi-Layer Skip-Graph Hierarchy: The top layers contain sparse graphs with long-distance links spanning across distant semantic clusters. Lower layers contain increasingly dense graphs with localized neighbor connections.
• Logarithmic Search Traversal: Query routing starts at the top entry point. The search engine performs a greedy search to find the closest vector in the sparse layer, drops to the corresponding node in the layer below, and repeats. This achieves $O(log N)$ search complexity instead of $O(N)$ linear scans.
• HNSW Hyperparameters:
  • M: The maximum number of bi-directional connection links per node (typically $16$ to $64$). Higher $M$ increases recall and graph build time at the expense of memory.
  • efConstruction: The size of the dynamic candidate list evaluated during index construction (typically $100$ to $400$).
  • efSearch: The candidate list depth maintained during active query evaluation. Higher values improve recall at the cost of query throughput.

3. Vector Quantization: Inverted File with Product Quantization (IVF-PQ)

While HNSW offers exceptional query speed and recall ($ge 98%$), it requires storing full floating-point vectors and graph links in memory. Storing 100 million 1536-dimensional vectors (at 6KB per vector) requires over 600 GB of RAM. For massive scale, systems adopt IVF-PQ:

• Inverted File (IVF): The vector space is partitioned into $K$ Voronoi cells using $k$-means clustering. At query time, only the centroids nearest the query vector are searched, pruning $95%$ of vectors from evaluation.
• Product Quantization (PQ): Vectors are sliced into $m$ smaller sub-vectors (e.g., eight 192-dimensional chunks). Each chunk is quantized into an 8-bit codebook centroid. This compresses a 1536-dimensional 32-bit float vector (6,144 bytes) into an 8-byte integer array—a staggering $768 imes$ compression ratio that enables memory-resident search across billions of embeddings.

4. Hybrid Search Architecture: Reciprocal Rank Fusion (RRF)

Because dense neural retrieval excels at semantic intent while sparse BM25 excels at exact keyword matches, production search systems deploy Hybrid Search, merging both candidate lists via Reciprocal Rank Fusion (RRF):

ext{RRF_Score}(d) = sum_{m in { ext{BM25}, ext{Dense}}} rac{1}{k + r_m(d)}

Where $r_m(d)$ is the ordinal ranking position of document $d$ within retriever $m$, and $k$ is a smoothing constant (standardly $60$). RRF normalizes distinct score scales without requiring complex cross-model calibration, surfacing documents that perform well across both lexical and neural models.

5. Production Implementation: Cosine Distance & RRF Merger

The following TypeScript blueprint demonstrates calculating normalized Cosine similarity across high-dimensional vector embeddings, alongside a Reciprocal Rank Fusion merger for hybrid search:

export function cosineSimilarity(a: Float32Array, b: Float32Array): number {
  if (a.length !== b.length) throw new Error('Vector dimensions must match');
  let dotProduct = 0;
  let normA = 0;
  let normB = 0;

  for (let i = 0; i < a.length; i++) {
    dotProduct += a[i] * b[i];
    normA += a[i] * a[i];
    normB += b[i] * b[i];
  }

  const denominator = Math.sqrt(normA) * Math.sqrt(normB);
  return denominator === 0 ? 0 : dotProduct / denominator;
}

interface RankedResult {
  docId: string;
  score: number;
}

// Reciprocal Rank Fusion (RRF) to merge BM25 and Neural Vector results
export function reciprocalRankFusion(
  bm25Results: RankedResult[],
  denseResults: RankedResult[],
  k: number = 60
): { docId: string; rrfScore: number }[] {
  const rrfScores = new Map<string, number>();

  // Process BM25 ranked list
  bm25Results.forEach((hit, rank) => {
    const current = rrfScores.get(hit.docId) || 0;
    rrfScores.set(hit.docId, current + 1 / (k + (rank + 1)));
  });

  // Process Dense Vector ranked list
  denseResults.forEach((hit, rank) => {
    const current = rrfScores.get(hit.docId) || 0;
    rrfScores.set(hit.docId, current + 1 / (k + (rank + 1)));
  });

  // Sort descending by merged RRF score
  return Array.from(rrfScores.entries())
    .map(([docId, rrfScore]) => ({ docId, rrfScore }))
    .sort((a, b) => b.rrfScore - a.rrfScore);
}