Graph-Based ANN

The core search mechanism starts at a designated entry point and iteratively moves to the unvisited neighbor closest to the query vector. The algorithm maintains a dynamic candidate list of size ef (exploration factor) and a visited set to avoid cycles. At each step, it evaluates all neighbors of the closest unvisited candidate, updating the list. Search terminates when no unvisited candidate is closer than the furthest element in the current result set. This greedy strategy exploits the small-world property, where any node can be reached in a small number of hops.

Algorithms like HNSW organize the graph into multiple layers of decreasing density. Upper layers contain fewer nodes with long-range edges, enabling rapid coarse-grained navigation across the space. Lower layers are dense with short-range edges for fine-grained refinement. Search begins at the topmost layer, descends to the nearest neighbor, and repeats the process in the layer below. This hierarchical design provides logarithmic scaling and eliminates the need for a separate coarse quantizer, making it distinct from clustering-based indices like IVF.

Building the graph involves inserting nodes sequentially and connecting them to their approximate nearest neighbors. Key heuristics include:

• Pruning redundant edges: If a new connection creates a detour (a path through the new node is shorter than the direct edge), the direct edge is removed to maintain sparsity.
• Degree constraints: A maximum number of outgoing edges per node (M) is enforced to bound memory and search cost.
• Diversity enforcement: Connections are selected to cover different regions of space, preventing all edges from pointing to a single dense cluster.

Graph-based indices achieve high recall at the cost of significant memory overhead. Each node stores its full-precision vector plus adjacency lists of neighbor IDs. For a graph with degree M, memory is roughly O(N * (d * 4 bytes + M * 8 bytes)). This is substantially larger than compressed indices like IVFPQ. However, the raw vector storage enables asymmetric distance computation during search, yielding higher accuracy than quantized approaches. DiskANN addresses this by storing compressed vectors and graph edges on SSD, streaming only required portions into RAM.

Unlike clustering-based indices that require periodic full rebuilds, graph-based structures support online insertion of new vectors without degrading search performance. New nodes are added by finding their approximate nearest neighbors using the existing graph and establishing bidirectional edges. Lazy deletion marks nodes as removed without restructuring the graph; periodic compaction reclaims space. This property makes graph-based indices suitable for dynamic datasets where vectors are continuously added, such as real-time user content embeddings.

Graph-based methods empirically outperform LSH and tree-based structures in high-dimensional spaces (d > 100). The navigable small-world property persists even as dimensionality increases, though the distance concentration effect of the curse of dimensionality eventually degrades all ANN methods. HNSW maintains strong recall above 0.95 on benchmarks like ANN-Benchmarks for dimensions up to 960 (e.g., DPR embeddings). Beyond this, dimensionality reduction or hybrid approaches combining graph navigation with vector compression become necessary.

The most prominent graph-based ANN algorithm. It constructs a multi-layered proximity graph where sparse upper layers enable long-range jumps and dense lower layers refine the search.

• Logarithmic scaling: Search complexity scales as O(log N).
• Greedy traversal: Navigates from an entry point to the query's neighborhood.
• Trade-off: High recall with fast search speed, but memory-intensive due to storing all edges.

A critical hyperparameter defining the number of outgoing edges per node in a graph-based index. It directly controls the trade-off between search speed, memory usage, and recall.

• Higher M: Better recall and faster search, but larger memory footprint.
• Lower M: Smaller index size, but longer search paths and potential dead ends.
• Tuning: Typically set between 16 and 64 for high-dimensional embeddings.

A two-stage retrieval architecture where a fast graph-based ANN index retrieves a candidate set, and a more precise computation re-scores these candidates.

• Stage 1: ANN index returns top-K candidates (e.g., K=100).
• Stage 2: Full-precision vectors or a cross-encoder re-ranks the candidates.
• Benefit: Combines the speed of approximate search with the accuracy of exact distance computation.

The constrained search problem of finding nearest neighbors that also satisfy structured metadata filters. Graph-based indices handle this via pre-filtering or post-filtering.

• Pre-filtering: Apply metadata filter first, then search the graph subset. Risks missing results if the filter is too aggressive.
• Post-filtering: Search the graph, then discard non-matching results. Can yield empty pages if the filter is highly selective.
• Custom strategies: HNSW variants modify graph traversal to only follow edges that satisfy the filter.

The total wall-clock time required to construct a graph-based ANN data structure from a raw set of vectors. A critical operational metric for dynamic datasets.

• HNSW: Build time is O(N log N) due to hierarchical insertion.
• DiskANN: Optimized for single-pass construction on large datasets.
• Impact: Frequent re-indexing in streaming scenarios requires fast build times to maintain data freshness.