Recall at k
Implement an exact baseline, compute recall at k and explain approximate search and high-dimensional difficulty.
THE IDEA
Recall at k
Recall@k is the fraction of the true k nearest neighbours that the index returned. If the true three neighbours are {A, B, C} and the index returns {A, C, E}, recall@3 = 2/3. Use ground truth computed under the same metric on the same data, handle exact ties explicitly, and say what you do when fewer than k candidates exist.
The exact (brute-force) answer is the target: the true 3 nearest are A, B and C. Click to choose what an approximate index returned.
Recall needs an exact target on the same data and metric. If two candidates tie exactly for the last place, accept either as correct (tie-aware recall), and say how you handle fewer than k candidates.
Predict first. Two of three true neighbours are returned. What is recall@3?
Chapter context
An exact search compares every candidate under a defined metric. Approximate indexes reduce work by choosing promising candidates, accepting that some true nearest neighbors may be missed.
TRY IT YOURSELF
Part 1. Do it hands-on
Compute recall by hand, then write recall with a tie-aware version.
The exact (brute-force) answer is the target: the true 3 nearest are A, B and C. Click to choose what an approximate index returned.
Recall needs an exact target on the same data and metric. If two candidates tie exactly for the last place, accept either as correct (tie-aware recall), and say how you handle fewer than k candidates.
- To do: The true three neighbours are {A, B, C}; the index returned {A, C, E}. recall@3 (3 decimals)?
- To do: True top-10 has 10 ids; the index returned 10 ids of which 8 are in the true set. recall@10?
- To do: Two candidates B and C are exactly tied for third place. The index returns {A, D?…} no: it returns B instead of C as its third result. If a tie-aware recall accepts either tied item as correct, is that a hit? Type yes or no
Part 2. Do it in code
- recall_at_k(returned, truth): the fraction of the true neighbours that appear in the returned ids (0 if truth is empty).
- mean_recall(all_returned, all_truth): the average over queries.
- tie_aware_truth(distances, k, tol=1e-12): given the exact distances of ALL candidates to a query, return the set of ids that count as correct: every id whose distance is at most the k-th smallest distance (plus tol). It can contain more than k ids when there are ties.
- tie_aware_recall(returned, distances, k): the fraction of the k slots filled by acceptable ids: |returned ∩ acceptable| / k, where returned has at most k ids.
- precision_vs_recall_note(returned_count, correct_count, truth_count): return a dict with precision = correct/returned_count (0 if none returned) and recall = correct/truth_count.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Two of three true neighbors are returned; what is recall@3?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
An exact dense dot-product scan over N vectors of dimension d needs Nd coordinate products plus reductions.
This assumes k ground-truth eligible neighbors. In a d-dimensional unit box, a sub-box spanning fraction r of every axis occupies fraction of the volume.
Worked example
Scanning 1000 vectors of dimension 128 uses 128,000 coordinate products, before selection and other overhead. If the true three neighbors are {A,B,C} and the returned set is {A,C,E}, recall@3 is 2/3. A sub-box spanning 0.1 of each of ten axes occupies only 10^-10 of the unit-box volume.
Reference code
The following example uses the Python standard library and does not call a remote service.
from math import isclose
assert 1000*128 == 128000
truth,returned={'A','B','C'},{'A','C','E'}
assert isclose(len(truth & returned)/3,2/3)
assert isclose(.1**10,1e-10)
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
Index recall is not the same as judged semantic relevance. High-dimensional behavior depends on the data manifold. Tie policies can affect reported recall for identical distances.