Top-Down Search for Optimal Entry Points

The Strategy: From Airplanes to Local Streets

Before diving into the formal algorithm, let's build an intuition for the process. Imagine you need to travel from an airport in New York City to a specific residential address in Houston. You wouldn't take local buses the entire way; that would be incredibly inefficient. Instead, you would follow a hierarchical strategy:

1. Top Layer (Airplane): You take an airplane from NYC to Houston. This is a long-range link that quickly gets you into the correct general vicinity, bypassing thousands of irrelevant intermediate locations.
2. Lower Layers (Local Transit): Once in Houston, you might take a local train or bus to get to the correct neighborhood. These are shorter-range links.
3. Base Layer (Walking): For the final leg, you walk from the bus stop to the specific house number. This is the most granular, short-range search.

The HNSW search algorithm operates on the exact same principle. It starts at the top-most layer of the graph, which contains only a few nodes connected by long-range links. It uses a fast, greedy search to find the node in this layer that is closest to the query. This node then becomes the "airport" or entry point for the next layer down. The process repeats, descending layer by layer, until it reaches the dense base layer (layer 0), where a more thorough local search is performed.

This hierarchical traversal is visualized perfectly below. The search begins at the entry point on layer 2, finds the nearest neighbor, and uses that point as the entry for layer 1. This repeats until the final search is conducted on the dense layer 0.

Algorithm 5: K-NN-SEARCH

The original HNSW paper formalizes this process in "Algorithm 5: K-NN-SEARCH". This will be our definitive guide for implementation.

Let's break down K-NN-SEARCH(hnsw, q, K, ef) into a clear, step-by-step process.

1. Initialization (Lines 2-3): The search begins at a single, pre-defined global entry point for the entire graph. We identify this node and its level L, which is the highest layer in our HNSW structure.

2. The "Zoom-In" Phase (Lines 4-6): This is the hierarchical traversal.

   • A for loop iterates from the top layer L down to layer 1 (lc ← L ... 1).
   • Inside the loop, we call our SEARCH-LAYER function with ef=1. This is a critical detail. We are not yet trying to find the final K neighbors. We are performing a simple, extremely fast greedy search to find just one node that serves as a better entry point for the layer below.
   • The result of this search (the single nearest element found) becomes the new entry point (ep) for the next iteration of the loop.

3. The Base Layer Search Phase (Line 7):

   • After the loop finishes, ep holds the best entry point we could find for the most detailed layer, layer 0.
   • Now, we execute the final and most thorough search. We call SEARCH-LAYER one last time, on layer 0, using ep as the starting point.
   • Crucially, this time we use the full ef value provided by the user (efSearch). This value is always greater than or equal to K. This tells the algorithm to build a large dynamic candidate list to ensure high recall (accuracy) in the final result.

4. Return Results (Line 8):

   • The final SEARCH-LAYER call gives us a set W containing the ef closest neighbors found on the base layer.
   • From this set W, we select the K elements with the smallest distance to the query q and return them as the final result.

This two-phase approach—a fast zoom-in followed by a detailed local search—is the key to HNSW's remarkable balance of speed and accuracy.

C Implementation Plan

Let's sketch out what the C function for this algorithm will look like. It directly translates Algorithm 5, using the search_layer function we designed in the previous lesson.

// Represents the final results of a search
typedef struct {
    hnswNode** nodes;
    float* distances;
    int count;
} SearchResults;

SearchResults knn_search(HNSW* hnsw, const void* query, int K, int ef) {
    // 1. Initialization
    hnswNode* entry_point = hnsw->entry_point;
    int top_layer = hnsw->max_layer;

    // A temporary list to hold the entry point for search_layer
    HnswNodeList entry_point_list;
    entry_point_list.count = 1;

    // 2. "Zoom-in" phase: Traverse from top layer down to layer 1
    for (int lc = top_layer; lc >= 1; --lc) {
        entry_point_list.nodes[0] = entry_point;
        // Perform a greedy search to find the best entry point for the next layer
        SearchResults W = search_layer(hnsw, query, &entry_point_list, 1, lc);
        
        // The single best node found becomes the entry point for the next iteration
        entry_point = W.nodes[0];
        
        // Remember to free resources used by W if dynamically allocated
        free_search_results(&W);
    }

    // 3. Base Layer search phase: Perform detailed search on layer 0
    entry_point_list.nodes[0] = entry_point;
    SearchResults W_final = search_layer(hnsw, query, &entry_point_list, ef, 0);

    // 4. Return the top K results
    // The results in W_final are likely in a max-heap structure.
    // We need to sort them by distance (ascending) and take the top K.
    sort_results_by_distance(&W_final);
    if (W_final.count > K) {
        W_final.count = K;
    }

    return W_final;
}

This implementation structure is clean and directly mirrors the logic of the paper. Your search_layer function from the previous lesson is now a subroutine in this higher-level search procedure. The distinction between ef=1 for navigation and ef=efSearch for the final accurate search is the central performance-tuning mechanism.

The Payoff: Logarithmic Complexity

Why go to all this trouble? A brute-force search requires O(N*D) operations, where N is the number of vectors and D is their dimensionality. This is prohibitively slow for large datasets. The hierarchical structure of HNSW, combined with this search algorithm, allows us to achieve a search complexity of O(log N).

By intelligently skipping over vast regions of the vector space in the upper layers, we dramatically reduce the number of distance calculations needed to find the nearest neighbors. This logarithmic scaling is what makes it possible to search billions of vectors in milliseconds, a requirement for any serious high-performance search system.

Conclusion

In this lesson, you have assembled the complete HNSW search algorithm. By building on the SEARCH-LAYER function, we've created the top-level logic that navigates the graph's hierarchy to efficiently find nearest neighbors.

Key Takeaways:

• Two-Phase Search: The HNSW search consists of a fast "zoom-in" phase (ef=1) through the upper layers to find an optimal entry point, followed by a detailed, high-recall search on the base layer using a larger ef.
• Hierarchical Traversal: The algorithm starts at the single global entry point and descends layer by layer, using the best result from layer l as the entry point for layer l-1.
• Logarithmic Complexity: This hierarchical approach is the source of HNSW's O(log N) search complexity, making it suitable for massive-scale applications.
• efSearch as a Tuning Knob: The ef parameter for the final search on layer 0 provides a direct control to trade between search speed and accuracy (recall).

We have now fully specified the search half of our vector database. The next logical step is to address how the graph is built in the first place. In the upcoming lessons, we will dive into the insertion algorithm, where you'll see how the search procedure we've just designed is cleverly repurposed to find the right place to insert new vectors and connect them into the hierarchy.