Payload filtering (the Qdrant problem)·22 min

Filtered HNSW search

0 / 1

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

Extend knnSearch into filteredSearch. Traverse the full graph for connectivity, but only push a node into the result set W if it matches the filter. And implement the planner fallback: if the matching-point count is below fullScanThreshold, do a filtered brute-force scan instead.

What to build

Your task

Implement runFilteredSearch

Implement HNSW.filteredSearch(q, k, efSearch, matches, matchCount, fullScanThreshold). When matchCount <= fullScanThreshold, scan the matching subset exactly. Otherwise traverse layer 0 expanding every node's neighbors, but only keep matches in W.

tests/adapters.ts

export function runFilteredSearch(
  base, query, k, params, payloads, filter, fullScanThreshold,
): number[] {
  // build index; matchCount = #payloads satisfying filter;
  // return index.filteredSearch(query, k, params.efSearch,
  //   id => matches(payloads[id], filter), matchCount, fullScanThreshold)
}

Admit-to-results is NOT restrict-traversal

You must still expand non-matching nodes' neighbors — they are bridges. You just do not keep them in the result set. Restricting traversal to matches is the pre-filter fragmentation bug from the chapter intro.

The tie-break applies inside filtered search too

When two admitted candidates tie on float32 distance, keep the one with the smaller node id, and apply the same rule in W's eviction — the same ascending-id tie-break as unfiltered K-NN-SEARCH. If you only put it in unfiltered search, filtered results can flip ids versus the reference.

How it's graded

Adapter mode: your id list is compared exactly to the reference for a fixed (query, filter) pair. Same graph + same predicate ⇒ one answer.

The filter predicate Filtered recall@10