Searching a single layer (Algorithm 2)·35 min

Implement SEARCH-LAYER

0 / 1

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

The centerpiece build. Implement Algorithm 2 on a fixed single-layer graph. You get the adjacency, the vectors, an entry point list, and ef; return the ef nearest node ids to q, nearest-first.

What to build

Your task

Implement runSearchLayer

Implement searchLayerIds(q, eps, ef, adj, vs) in src/hnsw.ts and expose runSearchLayer. graph.adj[node] is the neighbor-id list on this single layer; graph.vectors[id] is the vector for node id.

tests/adapters.ts

export function runSearchLayer(
  graph: { adj: number[][]; vectors: number[][] },
  q: number[], ep: number[], ef: number,
): number[] {
  // return the ef nearest node ids to q, nearest first
}

How it's graded

Adapter mode: your returned id list (nearest-first) is compared exactly to the reference on a fixed 30-node single-layer graph for a fixed (q, ep, ef). Order matters.

Three classic bugs

Not marking ep visited before the loop — you re-expand the entry and double-count.
Wrong heap tops in the stop test — compare min(C) to max(W), not the other way round.
Pushing a neighbor without the visited check — the walk loops or inflates the comparison count.

The fixture's expected output catches all three. The ascending-id tie-break in your heaps makes the order deterministic.

The greedy walk What ef buys you