Learn · Pictures Are Not Words

budding

Neighbors Without Looking Everywhere

Approximation buys fewer distance computations by spending a measured recall budget.

search, approximate-nearest-neighbor, hnsw, vector-search, recall, latency, memory, learn

“We present a new approach for the approximate K-nearest neighbor search.”

— Yu. A. Malkov and D. A. Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using HNSW Graphs

This is the thirty-first chapter in a book about search from first principles. You will define exact top-k before approximation; derive neighbor recall@k; trace hierarchical graph navigation; identify how construction degree and query frontier affect cost; and evaluate latency, distance computations, resident bytes, filters, deletions, and rebuilds as one frontier. You will keep empirical scaling separate from worst-case guarantees. The next chapter asks how results from several media relations can share one ordered surface.

Begin with the answer we are approximating

Let a frozen representation map a corpus (X) and query (q) into a metric or scored space with stable tie-break order. The exact answer is

$E_k(q)=\operatorname*{arg\,top}_{x\in X}^{k} \big(-\delta(q,x),id(x)\big).$

An approximate algorithm returns (A_k(q)). Its neighbor recall is

$Recall@k(q)=\frac{|A_k(q)\cap E_k(q)|}{k}.$

Average this only after preserving query slices and the distribution. A mean of (0.98) can hide a class of queries with zero recall. If fewer than (k) eligible items exist, define the denominator against the exact eligible answer size rather than manufacturing misses.

Neighbor recall is not relevance recall. It asks whether execution recovered the geometry's exact neighbors, not whether that geometry answers a person's question. Chapter 30 supplied the second evaluation.

Prediction — identify what approximation can promise.

Navigate a hierarchy of proximity graphs

Exhaustive search measures the query against every vector. A graph index stores links intended to make nearby regions navigable. Hierarchical Navigable Small World graphs, introduced by Malkov and Yashunin, place all indexed points in a dense bottom layer and progressively fewer points in upper layers.

A query starts from an entry point in a sparse upper layer. Greedy movement follows a neighbor that improves the query distance until no local improvement remains. The search descends and repeats. At the bottom, it maintains a wider candidate frontier rather than one path, visiting promising neighbors until the bounded frontier settles.

The hierarchy is an analogy to progressively more local guides. It is not a proof that every route reaches the true nearest point. The graph was built from finite choices, and greedy search can enter a basin whose outgoing links do not lead to the global answer within the work budget.

Approximate nearest-neighbor search (ANN) returns near points while deliberately avoiding some work required by exhaustive search. Its quality is defined against exact neighbors under the same frozen representation and tie order.

The parameters spend different resources

Common HNSW-style controls have distinct roles:

Control	Increased value usually buys	Cost paid
graph degree (M)	more navigable alternatives	resident bytes and construction work
construction frontier	better candidate links	build time and temporary work
query frontier	higher neighbor recall	distances, latency, and scratch
retained layers	long-range entry routes	metadata and construction complexity

“Usually” is empirical, not a monotonic theorem for every finite graph and implementation. Measure the actual corpus, distance, hardware, concurrency, and update regime. Increasing a frontier can reveal more candidates while cache effects or contention worsen latency nonlinearly.

The result receipt records representation identity, corpus generation, metric, (k), graph construction parameters, query frontier, filter strategy, and settlement. Without these, two numbers named recall@10 may describe different experiments.

Reveal — widen the right resource.

A bounded search makes the bargain visible

Algorithm — bounded graph frontier with exact receipt

GRAPH-NEIGHBORS(QUERY, GRAPH, ENTRY, LIMIT, FRONTIER)
Input:  normalized QUERY, frozen layered GRAPH, ENTRY, positive LIMIT and FRONTIER
Output: approximate top LIMIT with visited-work receipt

current ← ENTRY
for layer ← TOP-LAYER(GRAPH) downto 1
    current ← GREEDY-CLOSEST(QUERY, GRAPH, current, layer)
candidates ← MIN-QUEUE(current)
best ← MAX-QUEUE(current, FRONTIER)
visited ← SINGLETON(current)
while not EMPTY(candidates)
    candidate ← POP-CLOSEST(candidates)
    if WORSE-THAN-FARTHEST(candidate, best) and SIZE(best) = FRONTIER
        break
    for each neighbor in STABLE-NEIGHBORS(GRAPH, candidate, 0)
        if not CONTAINS(visited, neighbor)
            visited ← ADD-BOUNDED(visited, neighbor)
            score ← DISTANCE(QUERY, neighbor)
            candidates ← ADMIT-PROMISING(candidates, neighbor, score)
            best ← KEEP-CLOSEST(best, neighbor, FRONTIER)
return RECEIPT(TAKE-CLOSEST(best, LIMIT), SIZE(visited), FRONTIER)

This pedagogical algorithm exposes the invariant: best holds at most the frontier's best visited candidates, and visited prevents repeated work. Production HNSW has additional construction and neighbor-selection details. The bounded language is a model, not a claim of byte-for-byte implementation.

Plot a frontier, not a winner

For each pinned query set and configuration, record:

neighbor recall@k against exhaustive search;
task relevance separately;
distance computations and visited vertices;
p50, p95, and p99 latency under declared concurrency;
resident index bytes and peak construction memory;
build and update time;
result stability across repeated deterministic runs; and
filter selectivity, deletions, and corpus generation.

Sweep query frontier and graph degree. The output is a Pareto curve: a setting is dominated if another has at least as much recall with no more latency or memory and is strictly better on one dimension. The deployment policy chooses from the nondominated set according to its workload; the benchmark does not produce one universal winner.

Malkov and Yashunin report strong empirical efficiency and recall for evaluated datasets. That evidence does not create a general worst-case sublinear guarantee. Later worst-case analysis constructs difficult inputs for popular graph-based implementations. Therefore the book says “measured on this corpus,” not “HNSW is logarithmic” without qualifications.

Filters, deletions, and updates change the graph problem

A tenant or category filter can be applied before, during, or after graph navigation. Post-filtering may return too few results because ineligible points consume the frontier. Restricting traversal can disconnect useful routes. Overretrieval is a heuristic whose cost and survival distribution must be measured; it is not an authorization boundary.

Deleted vertices may remain as routing tombstones, be disconnected, or wait for rebuild. Each policy changes memory, reachability, and revocation behavior. Insertions depend on the graph generation they joined. A result receipt must name that generation so evaluation and replay do not compare moving targets.

Authorization is stricter than a categorical preference filter. Ineligible vectors must not become observable through results, counts, timing, completion, or shared caches. Chapter 35 will carry that law through every derived media artifact.

Wrong turns

Advertise one latency number

It hides recall, memory, build cost, concurrency, and tail behavior. ANN is a multi-resource trade, not a stopwatch contest.

Measure relevance but not neighbor recall

Then a representation improvement can conceal a worse index, or an index improvement can conceal a worse representation. Keep both oracles.

Assume a wider frontier always helps monotonically

Theoretical set inclusion does not automatically describe a production implementation with bounded queues, floating ties, filters, or concurrency. Test monotonicity; do not borrow it from intuition.

Filter forbidden items after ANN

This both starves the result set and exposes forbidden artifacts to intermediate work. Eligibility must shape the searchable universe under a non-disclosure contract.

Transfer — diagnose the two-stage miss.

Several senses now need one surface

We can retrieve exact text, transcripts, transformed copies, repeated instances, and semantic vector neighbors. Their scores have different units and their candidate sets may obey different eligibility rules. Adding the raw numbers would invent a comparison no provider defined.

The next chapter composes those senses only after eligibility, using calibrated probabilities or rank-based fusion and preserving a receipt for each provider.

Lessons

Exact top-k under a frozen representation and tie order defines the oracle.
ANN neighbor recall measures execution, not task relevance.
HNSW navigates progressively denser proximity graphs.
Graph degree, construction effort, and query frontier spend different resources.
Approximate search needs a recall–latency–memory–build frontier.
Empirical scaling is not a worst-case guarantee.
Filters, deletions, insertions, and generations alter reachability.
More ANN effort cannot repair representation error.
Eligibility is not a post-filtering convenience.

Practice

Compute recall@5 when approximate and exact lists share four identities.
Explain why task recall can rise while neighbor recall falls.
Design a sweep over query frontier with a fixed graph generation.
Give a case where post-filtering starves a top-k result.
List the fields in an ANN result receipt.
Separate resident index bytes from peak construction memory.
Write a claim about HNSW that the proposed experiment can actually support.

References

Yu. A. Malkov and D. A. Yashunin. “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 42.4, 2020.
Piotr Indyk and Rajeev Motwani. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.” Proceedings of STOC, 1998.
Subramanya et al. “Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations.” 2024.

To find a nearby house, ask a guide for the right region, then a more local guide, then inspect a small neighborhood. The shortcut is useful only when its misses are measured against the map it was meant to navigate.