How Vector Embeddings Actually Work: High-Dimensional Geometry, Dot Products, and HNSW Indexing

In classical database engineering, information retrieval relies on exact keyword matching, inverted B-Tree indexes, and boolean algebra. However, human language and sensory perception are continuous and non-deterministic: the queries "cardiac arrest symptoms" and "signs of a heart attack" share zero matching tokens yet express identical semantic intent.

Vector embeddings solve this by projecting arbitrary unstructured data—source code, audio waveforms, camera pixels, and technical prose—into continuous vectors in high-dimensional Euclidean space $\mathbb{R}^d$ ($d \in [768, 3072]$). In this space, semantic similarity is mathematically equivalent to geometric proximity.

1. The Strange Geometry of High-Dimensional Spaces ($d = 1536$)

Human intuition is forged in three-dimensional physical space. In 1,536 dimensions, geometry behaves counter-intuitively due to the Curse of Dimensionality and the Concentration of Measure phenomenon:

All Points Lie on the Thin Outer Shell

Consider a $d$-dimensional hypersphere of radius $R$. The volume of a hypersphere scales proportionally to $R^d$. If we calculate the fraction of volume residing in an infinitesimal outer shell between radius $R - \epsilon$ and $R$:

For $d = 1,536$, even if the shell thickness $\epsilon$ is merely $1\%$ of the radius ($\epsilon = 0.01R$), the fraction of volume inside this paper-thin shell is:

In high-dimensional space, the interior of the sphere is empty. Almost the entirety of the volume resides on the outer surface.

Almost All Random Vectors Are Mutually Orthogonal

If you sample two random vectors $\mathbf{u}, \mathbf{v}$ uniformly from a high-dimensional unit hypersphere, their expected dot product is $0.0$, and the distribution of angles between them concentrates sharply around $\theta = 90^\circ$ ($\frac{\pi}{2}$ radians). Two vectors only have a high cosine similarity ($> 0.8$) if a neural network deliberately aligned them through supervised contrastive loss.

2. Distance Metrics: Dot Product vs. Cosine Similarity vs. L2

In vector search, three metrics quantify similarity:

3. The Approximate Nearest Neighbor (ANN) Problem

Given a query vector $\mathbf{q} \in \mathbb{R}^d$ and a database of $N$ vectors, finding the true exact nearest neighbor (Exact $k$-NN) requires computing $N$ dot products:

For a database of 50 million documents with $d=1,536$, answering a single search query requires $7.68 \times 10^{10}$ floating-point operations, which takes several seconds per query. This computational cost is unviable for interactive applications.

The industry resolves this via Approximate Nearest Neighbor (ANN) algorithms: trading an insignificant fraction of accuracy (e.g. achieving 98% Recall@10 instead of 100%) to reduce query latency by 1,000x down to sub-5 milliseconds.

4. Hierarchical Navigable Small World (HNSW)

Introduced by Yury Malkov and Dmitry Yashunin in 2018, HNSW is the state-of-the-art graph-based ANN algorithm powering modern enterprise vector search engines.

The Skip-List Graph Architecture

HNSW generalizes William Pugh's probabilistic Skip-List data structure to multi-dimensional graphs. An HNSW index consists of multiple hierarchical layers of graphs:

Layer 2 (Top Layer):     [Node A] ---------------------------> [Node Z]   (Long-Range Highways)
                              |                                    |
Layer 1 (Middle Layer):  [Node A] ---------> [Node K] -------> [Node Z]   (Regional Roads)
                              |                 |                  |
Layer 0 (Base Layer):    [Node A] -> [B] -> [C] -> [K] -> [M] -> [Z]     (All Vectors, Dense Streets)

• Layer $L_{max}$ (Top): Contains very few nodes with long-range edges spanning the entire vector space. Allows the search algorithm to take massive strides across the hypersphere.
• Layer 0 (Bottom): A dense Delaunay-like proximity graph containing every vector in the database, with short-range edges connecting nearest neighbors.

The Greedy Search Routing Algorithm

1. Search begins at an entry point node in the topmost layer $L_{max}$.
2. At each layer, the algorithm evaluates the distance between the query vector $\mathbf{q}$ and all neighbors of the current node, greedily hopping to the closest neighbor.
3. When no neighbor is closer to $\mathbf{q}$ than the current node (a local minimum in that layer), the algorithm drops down to the corresponding node in layer $L-1$.
4. This process repeats until layer 0, where a bounded beam search explores local neighbors within candidate pool $efSearch$, returning the top $k$ closest vectors.

5. Vector Quantization: Scalar (SQ8) vs. Product Quantization (PQ)

Memory consumption is the primary cost driver of vector databases. Storing 100 million 1,536-dimensional vectors in standard 32-bit floats requires:

Vector quantization compresses these embeddings while preserving relative distance rankings:

Scalar Quantization (SQ8)

Maps each 32-bit float linearly into an 8-bit unsigned integer ($[0, 255]$). Reduces memory by 75% (to ~153 GB) with negligible (<1%) recall degradation, allowing the entire graph to fit on a single workstation.

Product Quantization (PQ)

Divides the 1,536-dimensional vector into $M = 96$ sub-vectors of 16 dimensions each. For each sub-space, k-means trains a codebook of 256 cluster centroids. Each original sub-vector is replaced by an 8-bit byte representing the index of its nearest centroid. This achieves an astonishing 16x to 32x memory reduction, allowing billions of vectors to be queried from SSDs with minimal RAM footprints.

6. Vector Index Comparison Matrix

7. Python HNSW Traversal Simulation

The following Python snippet demonstrates the core greedy search routing step across a single proximity graph layer:

import numpy as np
from typing import Dict, List, Tuple

def greedy_search_layer(query: np.ndarray, 
                        entry_node: int, 
                        graph: Dict[int, List[int]], 
                        vectors: Dict[int, np.ndarray]) -> int:
    """
    Greedy search on a single HNSW graph layer.
    Traverses neighboring nodes until reaching the local minimum.
    """
    current_node = entry_node
    current_dist = np.linalg.norm(vectors[current_node] - query)
    
    while True:
        changed = False
        neighbors = graph.get(current_node, [])
        
        for neighbor in neighbors:
            dist = np.linalg.norm(vectors[neighbor] - query)
            if dist < current_dist:
                current_dist = dist
                current_node = neighbor
                changed = True
                break # Greedy step to first strictly closer neighbor
                
        if not changed:
            # Reached local minimum for this layer
            break
            
    return current_node