Recall@K

Recall@K (written R@K) scores a retrieval system by asking, for each query, whether a correct item appears among the first $K$ results, and reporting the fraction of queries for which one does. It is the headline number of image–text retrieval, of deep metric learning on image collections, of visual place recognition, and, as the cumulative matching characteristic, of person re-identification. The name is misleading: in most of these papers R@K is a hit rate, not the recall of information retrieval, which counts how many of the relevant items were found. The two coincide only when each query has exactly one correct item. This article gives both definitions, the rank statistics and protocols reported with them, how the value depends on the size of the gallery, and the measures proposed because R@K stops looking after the first hit.

Formula

A query $q$ is scored against every item of a gallery of $N$ items, and the gallery is sorted by decreasing score. Let $\mathcal{R}_q$ be the set of relevant items, with $m_q = |\mathcal{R}_q|$, let $h_q(K)$ be the number of them in the top $K$, and let $r_q$ be the rank (1 = best) of the highest-ranked relevant item. Over $Q$ queries:

$$\text{R@}K = \frac{100}{Q} \sum_{q=1}^{Q} \mathbb{1}\left[r_q \le K\right], \qquad \text{recall@}K = \frac{100}{Q} \sum_{q=1}^{Q} \frac{h_q(K)}{m_q}, \qquad \text{P@}K = \frac{100}{Q} \sum_{q=1}^{Q} \frac{h_q(K)}{K}.$$

The first is the hit rate that retrieval papers call R@K; the second is recall at cut-off $K$ as information retrieval defines it; the third is precision at $K$ (P@K), the fraction of the top $K$ that is relevant (Manning, Raghavan & Schütze, 2008, §8.4).

Three relations follow from the definitions. With one relevant item per query ($m_q = 1$), the hit rate and recall@K are the same number. Precision at 1 equals the hit rate at 1 for any $m_q$, which is why Musgrave et al. (2020) call the metric-learning “Recall@1” Precision@1. With $m_q > 1$, recall@K is at most the hit rate, and $\text{P@}K = (m/K)\,\text{recall@}K$ when every query has the same $m$.

Two rank statistics accompany R@K. The median rank (MedR, “Med r”) is the median of $r_q$ over queries and the mean rank its mean; lower is better for both. The rsum adds R@1, R@5 and R@10 in both directions of a cross-modal benchmark, a number from 0 to 600 (the image–text retrieval article covers the cross-modal formulas). In the official VSE++ evaluation code, the image-to-text rank of an image is the best rank among its five captions, the median rank is $\lfloor \operatorname{median}(r_q - 1) \rfloor + 1$, the mean rank is computed beside it, and the rsum is printed for each run (Faghri, evaluation.py at commit abe382f); Faghri et al. (2018) chose the training snapshot with the highest sum of recalls on the validation set.

Intuition

As a function of $K$, the hit rate is the cumulative distribution of the first-correct rank $r_q$ over queries. Jégou, Douze and Schmid (2011) made the point for their recall@R curve, which they described as the distribution function of the ranks. Every summary of the rank distribution can be read from that curve: the median rank is where it crosses 50%, and the mean rank is the area above it, $\bar r = \sum_{K \ge 0} \left(1 - \text{R@}K/100\right)$ (the tail-sum formula for a positive integer variable; our derivation). A mean rank much larger than the median signals a tail of queries whose correct item sits far down the list, which R@10 cannot see.

The hit rate stops at the first correct item. A query whose first result is right scores 1 at every $K$, whatever the rest of the list holds; Musgrave et al. (2020) note that 100% R@1 implies 100% R@K for every larger $K$.

Interpretation

• Range. 0 to 100 (or 0 to 1); higher is better, and the value can only grow with $K$.
• Chance level depends on the gallery. A random ranking places a single relevant item in the top $K$ with probability $K/N$; with $m$ relevant items the probability is $1 - \binom{N-m}{K}/\binom{N}{K}$ (counting argument, ours). An R@10 of 50% is excellent against a million items and poor against 20.
• The gallery is part of the metric. Every added item is one more candidate that can outrank the correct one, so for fixed queries R@K cannot rise as the gallery grows. Karpathy and Fei-Fei (2015) reported one COCO model on a 1,000-image subset and on all 5,000 test images: image annotation R@1 was 38.4 and 16.5, and image search R@1 27.4 and 10.7 (Table 1, averages of the five best validation models), noting that the 5K numbers are lower because Recall@K depends on test-set size. Zheng et al. (2015) observed the same for re-identification: adding about 500,000 distractor images to Market-1501 lowered the mAP of one of their methods (BoW + MultiQ max, with approximate nearest-neighbor search) by a relative 69.7%, a gallery effect on a different ranking measure. Numbers are comparable only on the same gallery.
• Cross-modal directions differ. Image-to-text queries on COCO and Flickr30K have five correct captions, text-to-image queries one correct image, so the image-to-text hit rate is easier to score by construction.

When to Use It

R@K suits tasks where a user, or a later stage such as a reranker or geometric verification, inspects only a short list, and where finding one correct item is enough. The conventions differ by field:

• Image–text retrieval. R@1, R@5 and R@10 in both directions with the median rank, on Flickr30K and on COCO 1K and 5K; the image–text retrieval article describes the splits. In the VSE++ code the COCO 1K folds are consecutive blocks of 1,000 test images (Faghri, evaluation.py at commit abe382f).
• Deep metric learning. Song et al. (2016) trained on the first half of the classes and tested on the rest; each test image retrieves its $K$ nearest neighbors among the test images and scores 1 if one shares its class. Their Stanford Online Products dataset has 120,053 images of 22,634 products, split into 59,551 training images of 11,318 classes and 60,502 test images of 11,316 classes. With classes as relevance, R@1 equals the leave-one-out accuracy of a 1-nearest-neighbor classifier, the k-NN evaluation of self-supervised features (our observation).
• Visual place recognition. In the standard protocol that NetVLAD follows, a query photo is correctly localized if at least one of the top $N$ database images lies within 25 m of its true position, and the percentage of such queries is plotted as Recall@N against $N$ (Arandjelović et al., 2016). Relevance comes from GPS distance, not labels.
• Person re-identification. The cumulative matching characteristic (CMC) curve gives the probability that the query identity appears among the top $k$ candidates; its rank-$k$ value is the hit rate. Zheng et al. (2015) argued that CMC is fair only when each query has one ground-truth match, and with 14.8 cross-camera matches per Market-1501 query on average they reported mean average precision beside it.
• Approximate nearest-neighbor search. Jégou et al. (2011) defined recall@$R$ as the proportion of queries whose exact nearest neighbor is ranked within the first $R$ positions of the approximate search. Here the “relevant” item is the true nearest neighbor, not a semantic match. Song et al. (2016) cite this paper for their Recall@K, although their relevant items are all images of the query’s class.

Failure Cases

• Blind beyond the first hit. Musgrave et al. (2020, Table 3) list four results lists for a query with $R = 10$ relevant items: only the first correct, the first and tenth correct, the first two correct, and all ten correct. Recall@1 is 100 for all four, R-precision 10, 20, 20 and 100, and MAP@R 10, 12, 20 and 100. In their Figure 1, three toy embeddings score R@1 of 99 to 100 while MAP@R ranges from 71.4 to 99.8. The example below builds the same failure from images.
• Missing positives. Benchmarks with one labeled match count correct but unlabeled results as errors. On human-verified COCO positives, Chun et al. (2022) found that model rankings by COCO 1K R@1 agreed poorly with rankings by mAP@R on their corrected set; the image–text retrieval article gives their numbers.
• Mixed protocols. A 1K number and a 5K number differ by tens of points for the same model, as above; rsum inherits this, and adding six correlated recalls makes a gain at R@10 count as much as one at R@1.
• Ties. When scores tie, the rank of the correct item depends on the tie rule: counting tied items against it, in its favor, or in whatever order the sort returns. Real-valued embeddings rarely tie, but binary codes, quantized distances and duplicate images do. The VSE++ code ranks with numpy.argsort, so tied items keep an order set by the sort rather than by the model. One remedy, by our reasoning, is to report the expected value under random tie-breaking, which does not depend on the order.
• Selection on the test set. Musgrave et al. (2020) found that most metric-learning papers had no validation set and reported the best test accuracy seen during training, then measured, with cross-validated hyperparameters, improvements they described as marginal at best. A small R@K gain under such selection says little (benchmark overfitting).

Variants

R-precision and MAP@R. R-precision is the precision of the top $R = m_q$ results (Manning, Raghavan & Schütze, 2008, §8.4); a perfect ranking scores 1 for any $m_q$, unlike P@K. Musgrave et al. (2020) proposed MAP@R, which also rewards the order within those $R$ results:

$$\text{MAP@R}_q = \frac{1}{R} \sum_{i=1}^{R} P(i)\,\mathbb{1}[\text{item } i \text{ is relevant}],$$

with $P(i)$ the precision of the top $i$. It is mean average precision with the list cut at $R$ and the divisor fixed at $R$ rather than the number of correct retrievals. With one relevant item it reduces to R@1 (our observation); Chun et al. (2022) note that earlier image–text benchmarks could not use it because $R$ is 1, and applied it to COCO only after collecting more positives.

Mean average precision. Re-identification reports mAP beside CMC, in the information-retrieval form that average precision describes. A cut-off version, mAP@K, stops the list at $K$. Sources differ on the divisor: Manning et al. divide by all relevant items, while Musgrave et al. describe the usual mean average precision as dividing by the number of correct retrievals, so the code behind a reported mAP@K must be checked.

NDCG@K. For graded relevance, Järvelin and Kekäläinen (2002) proposed cumulated-gain measures that discount each result’s relevance by its rank and compare the total with that of an ideal ordering. In the form given by Manning et al. (notation changed here), with $g_j(i)$ the relevance grade of the result at rank $i$ for query $j$,

$$\text{NDCG}(Q, k) = \frac{1}{|Q|} \sum_{j=1}^{|Q|} Z_{kj} \sum_{i=1}^{k} \frac{2^{g_j(i)} - 1}{\log_2(1 + i)},$$

where $Z_{kj}$ normalizes a perfect ranking to 1. It suits retrieval in which relevance is graded rather than binary.

CMC and Recall@N curves. Plotting the hit rate against $K$ instead of fixing three values shows the whole rank distribution, as re-identification and place-recognition papers do.

Example

The script renders 5,000 grayscale $16 \times 16$ images, each a smooth random template of one of 50 classes plus instance detail plus pixel noise. Untrained random projections stand in for the encoders: an image embeds its pixels, and each of its five “captions” embeds the noise-free content plus caption noise. It computes the cross-modal metrics on 1K folds and on the 5K gallery, compares the four “recalls” for image-to-text queries, ranks with 32-bit binary codes to create ties, and finally retrieves same-class images with two embeddings: raw pixels and the shift-invariant Fourier magnitude, on 500 images in 20 classes, each circularly shifted by one of four offsets. It runs in about 2 seconds with NumPy 2.3; the seed is the first command-line argument.

import sys
import numpy as np

SEED = int(sys.argv[1]) if len(sys.argv) > 1 else 0
rng = np.random.default_rng(SEED)
S, C, N, CAPS, D = 16, 50, 5000, 5, 64
unit = lambda v: v / np.linalg.norm(v, axis=-1, keepdims=True)

def smooth_noise(n):
    """n random 16x16 patterns, low-pass filtered in the Fourier domain, unit std."""
    f = np.fft.fftfreq(S)
    lowpass = np.exp(-(f[:, None] ** 2 + f[None, :] ** 2) / (2 * 0.12 ** 2))
    z = np.fft.ifft2(np.fft.fft2(rng.standard_normal((n, S, S))) * lowpass).real
    return z / z.std(axis=(1, 2), keepdims=True)

# 5,000 grayscale 16x16 images: class template + instance detail + pixel noise
templates = smooth_noise(C)
cls = rng.integers(0, C, N)
content = templates[cls] + 0.6 * smooth_noise(N)        # what the captions describe
images = content + 0.8 * rng.standard_normal((N, S, S))

# Random-feature stand-ins for trained encoders (nothing is learned): the image
# embedding projects the pixels; each of 5 captions projects the noise-free
# content and adds its own noise.
P = rng.standard_normal((S * S, D)) / np.sqrt(S * S)
img = unit(images.reshape(N, -1) @ P)
cap = unit(np.repeat(content.reshape(N, -1) @ P, CAPS, 0)
           + 0.9 * rng.standard_normal((N * CAPS, D)))
cap_of = np.repeat(np.arange(N), CAPS)                  # caption -> its image

def t2i_ranks(img, cap, cap_of):
    """Rank (1 = best) of each caption's one correct image; ties counted in its favour."""
    ranks = np.empty(len(cap), int)
    for s in range(0, len(cap), 2500):
        sim = cap[s:s + 2500] @ img.T
        own = sim[np.arange(len(sim)), cap_of[s:s + 2500]]
        ranks[s:s + 2500] = 1 + (sim > own[:, None]).sum(1)
    return ranks

def i2t_positions(img, cap):
    """Sorted positions (1 = best) of each image's 5 correct captions in its ranked list."""
    n = len(img)
    pos = np.empty((n, CAPS), int)
    for s in range(0, n, 250):
        sim = img[s:s + 250] @ cap.T
        idx = np.arange(s, min(s + 250, n))
        own = sim[np.arange(len(idx))[:, None], CAPS * idx[:, None] + np.arange(CAPS)]
        pos[s:s + 250] = 1 + (sim[:, None, :] > own[:, :, None]).sum(2)
    return np.sort(pos, 1)

def evaluate(img, cap, cap_of, verbose=True):
    """R@1/5/10 (hit rate), median and mean rank in both directions; returns rsum."""
    pos = i2t_positions(img, cap)
    out = []
    for name, first in (("image->text", pos[:, 0]), ("text->image", t2i_ranks(img, cap, cap_of))):
        r = [100 * (first <= k).mean() for k in (1, 5, 10)]
        out += r
        if verbose:
            print(f"{name}  R@1 {r[0]:5.1f}  R@5 {r[1]:5.1f}  R@10 {r[2]:5.1f}  "
                  f"median rank {np.median(first):3.0f}  mean rank {first.mean():5.1f}")
    return sum(out), pos

# 1. COCO-style "1K": five folds of 1,000 images and their 5,000 captions, averaged
print("1K protocol, fold 1")
rsums = [evaluate(img[1000 * f:1000 * (f + 1)], cap[5000 * f:5000 * (f + 1)],
                  cap_of[:5000], verbose=(f == 0))[0] for f in range(5)]
print(f"rsum: fold 1 {rsums[0]:.1f}, mean of 5 folds {np.mean(rsums):.1f}")

# 2. "5K": the same embeddings, one gallery of 5,000 images and 25,000 captions
print("\n5K protocol")
rsum, pos = evaluate(img, cap, cap_of)
print(f"rsum {rsum:.1f}")

# 3. Image->text has 5 correct captions: the numbers that go by "recall"
print("\nimage->text, 5K, 5 relevant captions per query")
for k in (1, 5, 10):
    found = (pos <= k).sum(1)
    print(f"K={k:2d}  hit rate {100 * (found > 0).mean():5.1f}  "
          f"recall@K {100 * found.mean() / CAPS:5.1f}  precision@K {100 * found.mean() / k:5.1f}")
j = np.arange(1, CAPS + 1)
map_r = 100 * np.where(pos <= CAPS, j / pos, 0).sum(1).mean() / CAPS
print(f"R-precision {100 * (pos <= CAPS).mean():.1f}  MAP@R {map_r:.1f}")

# 4. Ties: 32-bit binary codes give integer similarities, so many images tie
H = rng.standard_normal((D, 32))                         # signs of 32 random projections
ci, cc = np.sign(img[:1000] @ H), np.sign(cap[:5000] @ H)
sim = cc @ ci.T
own = sim[np.arange(5000), cap_of[:5000]]
above, tied = (sim > own[:, None]).sum(1), (sim == own[:, None]).sum(1) - 1
print(f"\nties, 32-bit codes, 1K text->image: mean {tied.mean():.1f} other images tie "
      f"with the correct one")
print(f"R@1 if ties go to the correct image {100 * (above == 0).mean():.1f}, "
      f"against it {100 * ((above == 0) & (tied == 0)).mean():.1f}, "
      f"expected under random order {100 * ((above == 0) / (tied + 1)).mean():.1f}")
for trial in range(3):                                   # argsort after shuffling the gallery
    perm = rng.permutation(1000)
    top = perm[np.argsort(-sim[:, perm], axis=1, kind="stable")[:, 0]]
    print(f"  gallery order {trial + 1}: argsort R@1 {100 * (top == cap_of[:5000]).mean():.1f}")

# 5. Class-level image retrieval: R@1 against MAP@R on two embeddings
lab = np.repeat(np.arange(20), 25)                       # 20 classes x 25 images
shift = rng.integers(0, 4, len(lab)) * 4                 # one of 4 horizontal shifts
base = smooth_noise(20)
shots = np.stack([np.roll(base[c], s, axis=1) for c, s in zip(lab, shift)])
shots += rng.standard_normal(shots.shape)
pixels = unit(shots.reshape(len(lab), -1))
spec = np.abs(np.fft.fft2(shots)).reshape(len(lab), -1)  # unchanged by circular shifts
spectrum = unit(spec - spec.mean(0))
print("\nclass retrieval, 500 images, R = 24 other images of the query's class")
for name, e in (("pixels  ", pixels), ("spectrum", spectrum)):
    sim = e @ e.T
    np.fill_diagonal(sim, -np.inf)                       # the query is not in its own gallery
    rel = lab[np.argsort(-sim, axis=1)[:, :24]] == lab[:, None]
    prec = np.cumsum(rel, 1) / np.arange(1, 25)
    print(f"{name}  R@1 {100 * rel[:, 0].mean():5.1f}  R@10 {100 * rel[:, :10].any(1).mean():5.1f}  "
          f"R-precision {100 * rel.mean():5.1f}  MAP@R {100 * (prec * rel).sum(1).mean() / 24:5.1f}")

1K protocol, fold 1
image->text  R@1  78.3  R@5  97.7  R@10  98.6  median rank   1  mean rank   1.6
text->image  R@1  65.7  R@5  93.6  R@10  98.1  median rank   1  mean rank   2.1
rsum: fold 1 532.0, mean of 5 folds 534.2

5K protocol
image->text  R@1  57.3  R@5  85.3  R@10  93.1  median rank   1  mean rank   3.7
text->image  R@1  42.9  R@5  74.0  R@10  85.1  median rank   2  mean rank   6.3
rsum 437.8

image->text, 5K, 5 relevant captions per query
K= 1  hit rate  57.3  recall@K  11.5  precision@K  57.3
K= 5  hit rate  85.3  recall@K  38.4  precision@K  38.4
K=10  hit rate  93.1  recall@K  53.2  precision@K  26.6
R-precision 38.4  MAP@R 31.0

ties, 32-bit codes, 1K text->image: mean 25.1 other images tie with the correct one
R@1 if ties go to the correct image 13.3, against it 6.2, expected under random order 8.9
  gallery order 1: argsort R@1 9.1
  gallery order 2: argsort R@1 8.7
  gallery order 3: argsort R@1 9.3

class retrieval, 500 images, R = 24 other images of the query's class
pixels    R@1 100.0  R@10 100.0  R-precision  25.0  MAP@R  24.4
spectrum  R@1  92.6  R@10  99.8  R-precision  77.9  MAP@R  72.8

The embeddings are identical in the 1K and 5K runs; only the gallery changes, and rsum drops by about 100 points because each query now has five times as many competitors, the effect Karpathy and Fei-Fei reported on COCO. Image-to-text scores higher than text-to-image in both protocols, largely because any of five captions counts as a hit.

For image-to-text queries the four “recalls” disagree widely. The hit rate at 10 says 93% of queries succeed, yet only about half of the relevant captions are in the top 10, and precision at 10 cannot exceed 50% with five relevant items. At $K = 5 = m$, recall, precision and R-precision coincide; MAP@R can never exceed R-precision and equals it only when the correct captions in the top five fill its first places; here they do not.

With binary codes, many images tie with the correct one, and the tie rule alone moves R@1 by a factor of two. The expected value under random order lies between the bounds, and a stable argsort on reshuffled galleries scatters around it: the score depends on the order in which images were stored.

The last block reproduces Musgrave et al.’s critique with images. Raw pixels place an image next to a same-class image with the same shift, so R@1 and R@10 are perfect; but the other three shifts of the class are far away, and R-precision is near the 25% that one shift in four implies. The Fourier magnitude ignores circular shifts and gathers each class together, so its R@1 is lower and its MAP@R three times higher. Model selection by R@1 would pick the embedding that clusters worse. Over seeds 0–9, the 5K rsum was 422.0–439.3 against 1K means of 525.4–534.2, R@1 under the favorable tie rule 13.3–16.5 against 6.2–8.0 under the unfavorable one, and pixels kept R@1 of 99.4–100.0 with MAP@R of 24.4–32.7 while the spectrum’s MAP@R was 72.8–85.3.

Related Metrics

• Precision and recall: the set-based measures that recall@K and P@K cut off at rank $K$.
• Average precision: the area under the precision–recall curve; MAP@R and re-identification mAP are its retrieval forms.
• ROC curve and AUC: verification (is this pair a match?) is scored with TAR and FAR at a threshold; searching a gallery is scored with rank-based measures such as R@K.
• Statistical significance in evaluation: R@1 on 1,000 queries is a proportion with sampling error, and differences of a point need a confidence interval.