Navigable Proximity Graphs for High Dimensional Vector Search

This direction is merged into another direction: approximate nearest neighbor search. Its last version stays readable and citable here.

Version 1 of 199 papers117 conceptsfrozen 2026-10-04

In the early days of information retrieval, finding similar items was a matter of keyword matching. But as we moved toward "dense" representations—where words, images, and even entire tables are mapped into high-dimensional vector spaces—the problem shifted. We no longer look for exact matches; we look for the "nearest neighbors" in a vast, multi-dimensional sea.

Finding these neighbors is computationally brutal. A naive search across a billion vectors is an $O(n^2)$ nightmare that, as James Gorman and James R. Curran noted in Scaling Distributional Similarity to Large Corpora, breaks down as datasets grow. While traditional spatial structures like kd-trees or ball trees work in low dimensions, they fall victim to the "curse of dimensionality" in high-dimensional AI applications, where every point eventually appears equidistant from every other point.

The solution that has come to dominate the field is the Navigable Proximity Graph.

The Intuition: Greedy Navigation

The core idea is to treat the dataset not as a set of points in a coordinate system, but as a social network. In a $k$-nearest neighbor ($k$-NN) graph, every vector is a node connected to its most similar peers.

To find a query's neighbor, you don't scan the whole list. You start at a random entry point and ask: "Which of my neighbors is closest to the target?" You move to that neighbor and repeat the process. This "greedy" traversal continues until you reach a node whose neighbors are all further away than itself.

As Kohei Sugawara and Hayato Kobayashi demonstrate in On Approximately Searching for Similar Word Embeddings, this graph-based approach consistently offers a superior trade-off between search speed and accuracy compared to older hashing or tree-based methods.

Hierarchical Navigable Small Worlds (HNSW)

The most influential implementation of this idea is the Hierarchical Navigable Small World (HNSW) graph. As explained by Yanjie Fu and Yuanchun Zhou in A Comprehensive Survey on Vector Database, HNSW solves a major problem with simple greedy search: getting stuck in "local optima" or taking too many steps to cross the graph.

HNSW organizes the graph into layers, much like a skip-list:

  1. Top Layers: Contain only a few "hub" nodes with long-range edges. This allows the search to "zoom" across the vector space to the general vicinity of the query.
  2. Bottom Layers: Contain all the nodes with short-range edges for fine-grained local refinement.

This architecture allows for logarithmic scaling. Grace Fan and Yuliang Li 0001 showed in Semantics-aware Dataset Discovery from Data Lakes that HNSW can achieve a 3,000x speedup over traditional methods when searching through millions of tables in a data lake.

The Hub Highway Hypothesis

While the "Hierarchy" in HNSW is the industry standard, recent research suggests that high-dimensional geometry might do some of the work for us. Blaise Munyampirwa and Benjamin Coleman proposed the Hub Highway Hypothesis in Down with the Hierarchy. They argue that in high dimensions, certain nodes naturally become "hubs" with high centrality. These hubs act as a built-in routing system, allowing a flat graph to perform nearly as well as a hierarchical one while using 40% less memory.

Other variations focus on the mathematical properties of the edges. In Fast Approximate Nearest Neighbor Search With Navigating Spreading-out Graphs, Cong Fu and Deng Cai 0001 introduced the NSG, which ensures that paths are "monotonic"—meaning every step in the search strictly reduces the distance to the query, preventing the "detours" that slow down retrieval.

Scaling to Billions

As vector search becomes the "long-term memory" for Large Language Models, these graphs must scale to billions of points across distributed systems.

  • Distributed Routing: Shiyuan Deng and Xiao Yan developed Pyramid, which uses a meta-index to route queries to specific machines in a cluster, preventing the need for every machine to search its entire local graph.
  • Cloud-Native Storage: To handle the I/O latency of distributed storage like S3, Kun Yu and Lei Chen 0002 proposed DSANN, which keeps the navigation graph in memory while storing the heavy raw vectors on disk.

Beyond Euclidean Distance

One of the most powerful facets of graph-based search is its flexibility. Unlike many spatial indexes that require the "triangle inequality" to hold, graphs can be built using almost any similarity metric. Artem Babenko and Stanislav Morozov demonstrated in Non-metric Similarity Graphs for Maximum Inner Product Search that by building the graph using the target similarity function (like Inner Product) directly, you can achieve 10x speedups over methods that try to force the data into a standard metric space.

By shifting from "partitioning space" to "navigating a network," researchers have turned the curse of dimensionality into a manageable topological problem, enabling the real-time semantic search that powers modern AI.

Papers in this version

Showing 60 of 99 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_navigable_proximity_graphs_for_high_dime_8fd88cc6,
  title = {Navigable Proximity Graphs for High Dimensional Vector Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/navigable-proximity-graphs-for-high-dimensional-vector-search/rdr_8fd88cc677544a06b6e1365cdf35a093},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_navigable_proximity_graphs_for_high_dime_8fd88cc6_v1,
  title = {Navigable Proximity Graphs for High Dimensional Vector Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/navigable-proximity-graphs-for-high-dimensional-vector-search/rdr_8fd88cc677544a06b6e1365cdf35a093/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}