Exact versus approximate nearest-neighbor audit

Last updated: 7 Oct 20265 min read

tutorial

Approximate nearest-neighbor retrieval trades some exact-neighbor agreement for latency and memory; measure that trade on the same frozen embedding gallery.

Define two different recalls

Neighbor recall at K asks whether an approximate index returns the exact index’s top-K vector IDs. Task recall at K asks whether those results include a correct defect-family reference. They can move differently because the encoder’s nearest vector may itself be wrong. Report both. Embedding retrieval evaluation defines the task-level metric.

Benchmark the actual serving shape

Measure index build time, resident memory, p50 and p95 query latency, and concurrent throughput on deployment hardware. Include vector loading, eligibility filtering, deletion state and any exact rerank stage. One parameter setting may be fast on a small gallery and poor after a tenfold growth in reference photos. Device profiling sets the measurement boundary.

Treat permissions and deletion as correctness

A retrieved photo may be withdrawn, superseded or restricted. Filter at the serving boundary and ensure deletion propagates to the index. If filtering removes many approximate hits, oversample before the final top K and measure recall after filtering. Index lifecycle is part of correctness, not housekeeping.

Build a paired audit

For each held-out query, store exact top-K IDs and approximate top-K IDs from the same gallery and encoder version. Count overlap, then compute task recall on both lists. Slice by rare defect, camera and gallery age. The code audits two small result packets; no specific indexing library is required.

Choose an operating point, not an index name

Keep only candidates that meet minimum task recall, permission checks and latency budget. Among them, compare memory and rebuild time. Record the parameter setting so a future rebuild can reproduce it. The release project makes the decision explicit.

Implementation

reference_results = {
    "seal-47": ["cut-a", "cut-b", "wear-c"],
    "seal-24": ["pit-d", "pit-e", "wear-c"],
}
candidate_results = {
    "seal-47": ["cut-a", "wear-c", "cut-b"],
    "seal-24": ["wear-c", "pit-d", "pit-e"],
}

def neighbor_recall_at_k(reference, candidate, cutoff):
    if cutoff < 1 or reference.keys() != candidate.keys():
        raise ValueError("paired queries and positive cutoff required")
    fractions = []
    for query_id, exact_ids in reference.items():
        expected = set(exact_ids[:cutoff])
        observed = set(candidate[query_id][:cutoff])
        if len(expected) != cutoff:
            raise ValueError("reference list shorter than cutoff")
        fractions.append(len(expected & observed) / cutoff)
    return sum(fractions) / len(fractions)

assert neighbor_recall_at_k(reference_results, candidate_results, 2) == 0.5
assert neighbor_recall_at_k(reference_results, candidate_results, 3) == 1.0

Performance and operating cost

Paired top-K overlap costs O(Q times K) expected time and O(K) temporary memory per query. Constructing the exact oracle still costs O(Q times G times D). Approximate search adds index construction, RAM and update costs that this overlap function does not measure; profile the full path before promotion.

Common Mistakes

Do not call exact-neighbor overlap task accuracy.
Do not compare indexes built from different gallery or encoder versions.
Do not measure retrieval before eligibility filtering and then claim the result is safe to serve.