Searching the tower (Algorithm 5) & the recall payoff·25 min

K-NN-SEARCH

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage knn-search-build --watch

Algorithm 5 ties the tower together. From the entry point, greedy-descend at ef = 1 through the upper layers to reach layer 0's local region, then run SEARCH-LAYER(q, ep, efSearch, 0) and return the top-K of the result set. This is the public query API of your vector DB.

Algorithm 5 skeleton

ep <- [entryPoint]
for lc from topLayer down to 1:          // cheap descent, ef=1
  ep <- [ nearest of SEARCH-LAYER(q, ep, 1, lc) ]
W <- SEARCH-LAYER(q, ep, efSearch, 0)    // the wide search, layer 0 only
return top-K nearest of W

What to build

Your task

Implement runKnnSearch

Implement HNSW.search(q, k, efSearch). The adapter rebuilds the deterministic graph from the base vectors + params in the inputs, then searches one fixed query and returns the top-k node ids, nearest-first.

tests/adapters.ts

export function runKnnSearch(base: number[][], query: number[], k: number, params: Params): number[] {
  // buildIndex(fromRows(base), params), then index.search(query, k, params.efSearch)
}

Only layer 0 gets the wide search

Do not run SEARCH-LAYER at efSearch on every layer — upper layers use ef = 1. Running the wide search up top wastes comparisons and does not improve recall. The whole point of the hierarchy is a cheap descent followed by one thorough search at the bottom.

How it's graded

Adapter mode: your top-10 id list is compared exactly to the reference. Same seed ⇒ same graph ⇒ one answer, so a correct implementation matches the reference id-for-id — no tolerance needed.

Reading the graph Recall@10 under a budget