Question

During HNSW graph construction for vector search, why does increasing the &#x27;M&#x27; parameter improve recall at the cost of both search latency and memory usage?

Accepted Answer

In HNSW, or Hierarchical Navigable Small World graphs, the M parameter defines the maximum number of bidirectional edges each node can create with its neighbors in the graph. Increasing M improves recall because it increases the connectivity of the graph, which creates more paths for the search algorithm to explore. With more paths available, the algorithm is significantly less likely to get trapped in a local optimum or miss the true nearest neighbors of a query vector, leading to higher precision in retrieval. However, this comes at the cost of search latency because each step of the search process involves calculating the distance between the query vector and every neighbor connected to the current node. When M is higher, the algorithm must perform more distance calculations at every hop through the graph, which directly increases the time required to complete the search. Furthermore, increasing M raises memory usage because each node in the graph must store a larger list of identifiers for its neighbors. Since these neighbor lists are stored in memory for every node across all layers of the graph, a higher M parameter results in a larger total memory footprint for the entire index structure.

Home → All Courses → Programming Courses → Large Language Model (LLM) Engineering → Flashcard

During HNSW graph construction for vector search, why does increasing the 'M' parameter improve recall at the cost of both search latency and memory usage?