Building a Vector Search Engine from Scratch: The Math and Mechanics of HNSW

"Redis In-Memory Cache" → [ 0.01249, -0.04581, 0.08914, ..., -0.00312 ]  // 3072 dimensions
"PostgreSQL Database"   → [ 0.01183, -0.04491, 0.08877, ..., -0.00298 ]  // 3072 dimensions
"PyTorch Model"         → [-0.09214,  0.07321, -0.03812, ...,  0.06441 ]  // 3072 dimensions

cos(θ) = (A · B) / (|A| × |B|)

A · B = Σ(Aᵢ × Bᵢ)

d(A, B) = √(Σ(Aᵢ - Bᵢ)²)

Complexity: O(D × N)  — where D = dimensions, N = document count

LAYER 2 (Sparse Highway) ─── node_A ──────────────────── node_B ───
LAYER 1 (Intermediate)   ─── node_A ─── node_C ─── node_B ─── node_D
LAYER 0 (Dense Ground)   ─ ALL nodes fully connected to neighbors ──

Brute Force: O(N)         → Linear — fails at scale
HNSW:        O(log N)     → Logarithmic — sub-5ms at 10M+ docs

class HNSWIndex {
  private layers: Map<string, string[]>[] = [];
  private vectors: Map<string, number[]> = new Map();
  private readonly maxLayers: number;
  private readonly maxConnections: number;

  constructor(maxLayers = 4, maxConnections = 16) {
    this.maxLayers = maxLayers;
    this.maxConnections = maxConnections;
    this.layers = Array.from({ length: maxLayers }, () => new Map());
  }

  private cosineSimilarity(a: number[], b: number[]): number {
    const dot = a.reduce((sum, ai, i) => sum + ai * b[i], 0);
    const magA = Math.sqrt(a.reduce((sum, ai) => sum + ai * ai, 0));
    const magB = Math.sqrt(b.reduce((sum, bi) => sum + bi * bi, 0));
    return magA === 0 || magB === 0 ? 0 : dot / (magA * magB);
  }

  private getRandomLayer(): number {
    let layer = 0;
    while (layer < this.maxLayers - 1 && Math.random() < 0.5) {
      layer++;
    }
    return layer;
  }

  insert(id: string, vector: number[]): void {
    this.vectors.set(id, vector);
    const assignedLayer = this.getRandomLayer();

    for (let level = 0; level <= assignedLayer; level++) {
      if (!this.layers[level].has(id)) {
        const candidates = this.searchLayer(vector, level, this.maxConnections);
        this.layers[level].set(id, candidates.map(c => c.id));
      }
    }
  }

  search(queryVector: number[], k: number): { id: string; score: number }[] {
    let candidates = this.getEntryPoints(queryVector);

    for (let level = this.maxLayers - 1; level >= 0; level--) {
      candidates = this.searchLayer(queryVector, level, k, candidates);
    }

    return candidates
      .sort((a, b) => b.score - a.score)
      .slice(0, k);
  }

  private searchLayer(
    query: number[],
    level: number,
    k: number,
    entryPoints: { id: string; score: number }[] = []
  ): { id: string; score: number }[] {
    const visited = new Set<string>();
    const results: { id: string; score: number }[] = [...entryPoints];
    const queue = [...entryPoints];

    while (queue.length > 0) {
      const current = queue.shift()!;
      if (visited.has(current.id)) continue;
      visited.add(current.id);

      const neighbors = this.layers[level].get(current.id) ?? [];
      for (const neighborId of neighbors) {
        if (!visited.has(neighborId)) {
          const vec = this.vectors.get(neighborId)!;
          const score = this.cosineSimilarity(query, vec);
          queue.push({ id: neighborId, score });
          results.push({ id: neighborId, score });
        }
      }
    }

    return results
      .sort((a, b) => b.score - a.score)
      .slice(0, k);
  }

  private getEntryPoints(query: number[]): { id: string; score: number }[] {
    const entries: { id: string; score: number }[] = [];
    for (const [id, vec] of this.vectors) {
      entries.push({ id, score: this.cosineSimilarity(query, vec) });
      if (entries.length >= 3) break;
    }
    return entries;
  }
}