Recall@k of an approximate index

Approximate vector indexes are fast because they skip most of the data. The price is that sometimes they skip a true neighbour. Recall@k measures that price, and it’s the number you tune an index against.

Write recall_at_k(queries, docs, approx, k):

• queries and docs are lists of float vectors, all the same length.
• approx[i] is the list of doc indices an approximate index returned for queries[i], best first. It can be shorter or longer than k.
• For each query, compute the exact top k docs by cosine similarity. Ties go to the lower index. A zero vector has similarity 0 with everything. If k > len(docs), the exact list has every doc.
• That query’s recall is the number of exact top-k indices that appear in the first k entries of approx[i], divided by the length of the exact list.
• Return the mean recall over all queries, as a float. With no queries, return 0.0.

>>> docs = [[1, 0], [0, 1], [1, 1]]
>>> recall_at_k([[1, 0.1]], docs, [[0, 1]], 2)   # exact top-2 is [0, 2]
0.5

Approach

Brute-force the ground truth, then count overlaps.

import math


def recall_at_k(queries, docs, approx, k):
    if not queries:
        return 0.0

    def norm(v):
        return math.sqrt(sum(x * x for x in v))

    dnorms = [norm(d) for d in docs]
    total = 0.0
    for q, got in zip(queries, approx):
        qn = norm(q)
        scores = []
        for d, dn in zip(docs, dnorms):
            if qn == 0 or dn == 0:
                scores.append(0.0)
            else:
                scores.append(sum(a * b for a, b in zip(q, d)) / (qn * dn))
        exact = sorted(range(len(docs)), key=lambda i: (-scores[i], i))[:k]
        if not exact:
            continue
        found = set(got[:k])
        total += sum(1 for i in exact if i in found) / len(exact)
    return total / len(queries)

Only the first k approximate results count. Otherwise an index could score perfect recall by returning everything. The set also means a duplicate in the approximate list can’t be counted twice.

Complexity

O(q·n·d) to score q queries against n docs of dimension d, plus O(q·n log n) for the sorts. That is exactly the cost the approximate index exists to avoid, which is why you compute ground truth once, offline, on a sample of queries.

Why this matters

Every vector index has knobs: ef_search in HNSW, nprobe in IVF. Turning them up raises recall and latency together. You pick a setting by plotting recall@k against queries per second, and this function gives you the recall axis. In a RAG system, recall at the retrieval step caps answer quality. A chunk that was never retrieved can’t be cited, however good the model is.