The correctness of HNSW implementation for HNSW::upper_beam != 1

[alexanderguzhva]

Summary

I wonder whether this (

faiss/faiss/impl/HNSW.cpp

Line 893 in f821704

int candidates_size = upper_beam;

) branch in HNSW is designed in the way as it is implemented.

Currently, it seems that HNSW may use a beam search, which is controlled by a field HNSW::upper_beam. According to the code, upper_beam serves not only as a beam search parameter, but as a replacement of ef parameter, so it is used across all HNSW levels. Logically speaking, I would expect upper_beam to control upper levels only, and leave ef for the last level. So,

MinimaxHeap candidates_upper_levels(upper_beam);
for (int level = max_level; level >= 1; level--) {
    // use `upper_beam`
}

// last level uses `ef`
MinimaxHeap candidates_last_level(ef);
candidates_last_level.copy_from(candidates_upper_levels);
...

@mdouze Could you please comment on the topic? Thanks.

[asadoughi]

Closing as it was addressed in #3692.