Optimizing k-NN Search with `efSearch`

The Full Search: Greedy Descent Meets Beam Search

Let's revisit the complete search process. It consists of two distinct phases:

1. Greedy Descent (Layers L -> 1): Starting from the entry point at the highest layer, we perform a fast, greedy search (ef=1) on each layer. The goal isn't to find the final neighbors, but simply to find the single best node to act as the entry point for the next layer down. This is the "airplane travel" phase, efficiently crossing vast distances in the vector space.
2. Beam Search (Layer 0): Once we arrive at the base layer (layer 0), which contains all the vectors, the strategy changes. We switch to a much more thorough search using a larger candidate list. This is often called a "beam search." The size of this candidate list, or "beam," is controlled by the efSearch parameter.

This process is beautifully illustrated in the following diagram, which you should study carefully. It clearly distinguishes the initial "Greedy descent" from the final, more intensive "Beam search".

A simplified pseudocode for this process, as seen in the "Write You a Vector Database" guide, reinforces this logic.

efSearch: The Speed vs. Accuracy Dial

The efSearch parameter (short for "effective search") is arguably the most important query-time tuning parameter in HNSW. It dictates the size of the dynamic candidate list maintained during the search on layer 0.

• A small efSearch (e.g., just slightly larger than k) results in a very fast search. The algorithm explores fewer paths and performs fewer distance calculations. However, this increases the risk of getting trapped in a "local minimum" and missing the true nearest neighbors, thus lowering recall (accuracy).
• A large efSearch (e.g., 10 * k or more) forces the algorithm to be more exhaustive. It keeps a larger pool of potential candidates, explores more branches of the graph, and is much more likely to find the true nearest neighbors. This yields higher recall but at the cost of increased computation and higher query latency.

Think of efSearch as the size of your search party. A small, agile team of scouts (efSearch = 10) can report back quickly, but they might miss something. A large, methodical search party (efSearch = 200) will be much slower, but their search will be far more thorough.

This trade-off isn't just theoretical. For a systems engineer, seeing the empirical data is crucial. The following video demonstrates a Python implementation of HNSW and presents performance graphs that visualize this exact relationship.

Finalizing the C Implementation

Let's refine the C function we sketched out in the last lesson. It will take the HNSW index, a query vector, the number of neighbors k, and the efSearch parameter as input.

/**
 * @brief Represents the results of a k-NN search.
 *
 * The results are typically returned sorted by distance, ascending.
 */
typedef struct {
    uint32_t* ids;      // Array of vector IDs
    float* distances;   // Array of corresponding distances
    size_t count;       // Number of results
    size_t capacity;
} SearchResult;

/**
 * @brief Performs a k-NN search on the HNSW graph.
 *
 * @param hnsw The HNSW index.
 * @param query_vector The vector to search for.
 * @param k The number of nearest neighbors to return.
 * @param ef_search The size of the dynamic candidate list for the search on layer 0.
 * @return A SearchResult struct containing the k nearest neighbors.
 */
SearchResult hnsw_search(HNSW* hnsw, const float* query_vector, int k, int ef_search) {
    
    // Ensure ef_search is at least k
    if (ef_search < k) {
        ef_search = k;
    }

    // Phase 1: Greedy descent from top layer to layer 1
    HnswNode* entry_point = hnsw->entry_point;
    
    for (int layer = hnsw->max_layer; layer >= 1; --layer) {
        // Here we call search_layer with a candidate list of size 1 (the current entry_point)
        // and ef=1 to perform a greedy search.
        // The result will be a single node, which becomes the entry point for the next layer.
        
        SearchResult W = search_layer(hnsw, query_vector, entry_point, /* num_candidates=*/ 1, layer, /*ef=*/ 1);
        
        if (W.count > 0) {
            // In a real implementation, you'd fetch the node pointer from the ID.
            // For simplicity, let's assume search_layer returns the node pointer directly.
            entry_point = get_node_by_id(hnsw, W.ids[0]); 
        }
        
        // Free the temporary search result from the greedy search
        free(W.ids);
        free(W.distances);
    }

    // Phase 2: Beam search on layer 0
    // The entry_point from the loop is now our highly optimized starting point for the final search.
    // We call search_layer again, but this time with the user-provided ef_search.
    SearchResult final_candidates = search_layer(hnsw, query_vector, entry_point, /*num_candidates=*/ 1, /*layer=*/ 0, ef_search);

    // The `search_layer` function (using a max-heap) will return up to `ef_search` candidates.
    // We now need to extract the best `k` from this list.
    // The elements in a heap are not fully sorted, so we must sort them.
    
    // sort_by_distance(&final_candidates); // A helper function to sort the results
    
    // Trim the results to k
    if (final_candidates.count > k) {
        final_candidates.count = k;
        // Optionally, reallocate memory to shrink the arrays if memory is critical
    }

    return final_candidates;
}

This implementation brings together everything we've discussed. It uses search_layer as a versatile subroutine, first in a "greedy" mode (ef=1) for navigation and then in a "beam search" mode (ef=ef_search) for high-recall final selection.

A key performance consideration here is the memory management for the temporary data structures used during search (candidate lists, visited sets, etc.). Since these are allocated and freed for every single query, they are prime candidates for a custom arena allocator, which you implemented in Module 1. Using an arena would significantly reduce the overhead of repeated malloc/free calls, boosting the queries-per-second (QPS) of our system.

Conclusion

In this lesson, we have finalized the design of the complete HNSW k-NN search algorithm. You now understand how the hierarchical traversal and the layer-specific search strategies combine to produce a system that is both fast and accurate.

Key Takeaways:

• Full Search Flow: The complete search algorithm combines a fast greedy descent through layers L..1 to find an optimal entry point, followed by a detailed beam search on layer 0.
• efSearch is Key: The efSearch parameter controls the size of the candidate list (beam width) on layer 0, providing a direct mechanism to tune the trade-off between search latency and recall.
• Implementation Synergy: The search_layer function is used as a building block for both phases of the search, first with ef=1 for speed, then with a larger ef for accuracy.
• Performance Tuning: Your choice of efSearch will be one of the most impactful decisions when deploying the vector database, as it directly maps to the user-facing trade-off between speed and result quality.

With the entire search mechanism now defined, our vector database can answer queries. However, it cannot yet learn. The next step is to implement the logic for building and modifying the graph. In our next module, we will begin implementing the insertion algorithm, which cleverly repurposes the search function you've just built to find the optimal connections for new vectors.