nucleation

QUESTION-230: Do the released HNSW, NSG and fast-preprocessing DiskANN builds, run independently on Indyk and Xu's published hard instances at the stated parameters, need a search queue of about a tenth of the points before recall@5 rises above zero, and does the same trap appear on natural data with adversarially chosen queries?

1 min read

Properties4
StatusOpen
Tagsdatabases, information-retrieval
Linedistributed-agency
RefinesQUESTION-114 — Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?

Graph View

Why it is a question

THEORY-368 holds Indyk and Xu’s measurement on two-dimensional point sets built to trap best-first search. On those sets, the authors’ code for fast-preprocessing DiskANN, HNSW and NSG in most cases found none of a query’s five nearest neighbours until the queue held about 10% of the points. At that queue length ten graph indexes averaged recall@5 between 0.0 and 0.42. That is one study, with one query per instance. Until 2026-10-20 an independent run was THEORY-368’s promote_when.

An answer is an independent run of the published instances, which are on the authors’ GitHub, with the released HNSW, NSG and DiskANN code at the stated parameters. It should report recall@5 against queue length. A second answer, which the authors list as open, is the same failure on natural data with adversarially chosen queries. A proof of a linear lower bound for one of these builds would be a different and stronger result. Benchmarks on natural queries cannot settle it.

Backlinks