Choosing neighbors (Algorithms 3 & 4)·35 min

SELECT-NEIGHBORS-HEURISTIC

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage select-heuristic --watch

Algorithm 4 — the subtle one, and the difference between a working HNSW and a great one. Process candidates nearest-first. Add a candidate e to the result set only if e is closer to q than to any already-selected neighbor — otherwise it is redundant, because some kept neighbor already covers that direction.

Algorithm 4, paraphrased

R <- {}                          // selected
W <- candidates (min-heap by dist to q)
if extendCandidates:             // seed pool with candidates' neighbors
  for each cand, add its neighbors to W (dedup)
while |W| > 0 and |R| < M:
  e <- extract-nearest(W)
  good <- true
  for r in R:
    if dist(e, r) < dist(e, q): good <- false; break   // r occludes e
  if good: R <- R ∪ {e}
  else:    discarded <- discarded ∪ {e}
if keepPrunedConnections:        // top up if R fell short of M
  while |discarded| > 0 and |R| < M: R <- R ∪ {extract-nearest(discarded)}
return R

What to build

Your task

Implement runSelectHeuristic

Implement selectHeuristic(q, candidates, M, extendCandidates, keepPrunedConnections). Support both flags. With keepPrunedConnections, top the result back up to M from the pruned set when the occlusion test left you short.

tests/adapters.ts

export function runSelectHeuristic(
  q: number[], candidates: Cand[], M: number,
  extendCandidates: boolean, keepPrunedConnections: boolean,
): number[] {
  // accept e only if dist(e,q) < dist(e,r) for EVERY already-selected r
}

The acceptance test is the #1 bug magnet

Accept e only if it is closer to the query than to every already-selected r: dist(e, q) < dist(e, r) for all r ∈ R. hnswlib writes the rejection form: set good = false the moment dist(e, r) < dist(e, q) for some kept r. Get the inequality direction backwards and you have built SIMPLE with extra steps.

How it's graded

Adapter mode: your id list is compared exactly to the reference on a clustered fixture where SIMPLE and HEURISTIC disagree. Because the fixture is constructed so the two answers differ, a heuristic-stubbed (SIMPLE-fallback) solution is detectably wrong — you cannot pass by faking it.

Why closest-M isn't enough The heuristic test