Recall@K for Image-Text Retrieval

mediumFREERetrieval & Zero-Shot TransferVision-Language ModelsVLM 1: Vision-Language Models

Problem Statement

Given a query-by-gallery similarity matrix and the index of the correct gallery item for each query, compute Recall@K for several values of K.

Background

Recall@K is the standard retrieval metric for CLIP-style models on COCO and Flickr30k: the fraction of queries whose ground-truth match appears anywhere in the top K results.

For query i, sort the gallery by descending similarity and find the 0-indexed position of ground_truth[i]:

$\text{rank}_i = \left|\{\, j : \text{sim}[i][j] > \text{sim}[i][g_i] \,\}\right| \quad\text{(with ties broken by index)}$

$\text{R@}K = \frac{1}{n}\sum_{i=1}^{n} \mathbb{1}\!\left[\text{rank}_i < K\right]$

Two details decide whether your number matches a published one. First, ranks are 0-indexed against K, so R@1 means rank == 0. Second, ties must be broken deterministically - here, toward the lower gallery index - otherwise a model that returns identical scores appears to score differently on every run.

Recall@K is monotone non-decreasing in K, and R@m over an m-item gallery is always 1.0.

Your Task

Implement:

def recall_at_k(sim_matrix, ground_truth, ks):

Return a list of floats, one per entry of ks in the given order, each rounded to 4 decimals.

Input Format

sim_matrix - n x m nested list of floats, row i scoring query i against every gallery item
ground_truth - list of n ints, the correct gallery index per query
ks - list of positive ints (not necessarily sorted)

Output Format

A list of floats rounded to 4 decimals, same length and order as ks.

Sample

sims = [[0.9, 0.2, 0.1], [0.3, 0.4, 0.8], [0.5, 0.7, 0.6]]
print(recall_at_k(sims, [0, 2, 0], [1, 2]))

Output:

[0.6667, 0.6667]

Example

Input

sims = [[0.9, 0.2, 0.1], [0.3, 0.4, 0.8], [0.5, 0.7, 0.6]]
print(recall_at_k(sims, [0, 2, 0], [1, 2]))

Output

[0.6667, 0.6667]

Reasoning

Inputs: a $3 \times 3$ similarity matrix (row $i$ = query $i$ scored against gallery items 0, 1, 2), the correct gallery index for each query ( $g = 0, 2, 0$ ), and the cutoffs $K = 1$ and $K = 2$ .
Query 0: its answer (item 0) scores $0.9$ , and no other item beats it, so $\text{rank}_0 = 0$ .
Query 1: its answer (item 2) scores $0.8$ , above $0.3$ and $0.4$ , so $\text{rank}_1 = 0$ .
Query 2: its answer (item 0) scores $0.5$ , but items 1 and 2 score $0.7$ and $0.6$ . Two items beat it, so $\text{rank}_2 = 2$ .
R@1 counts ranks $< 1$ : queries 0 and 1, giving $2/3 \approx 0.6667$ . R@2 counts ranks $< 2$ : still only queries 0 and 1, since rank 2 is not below 2. That gives $0.6667$ again.
Output: [0.6667, 0.6667], one value per cutoff in the order given. Notice R@K never drops as $K$ grows, and with $K = 3$ (the whole gallery) it would reach $1.0$ .

Constraints

1 <= n <= 200, 1 <= m <= 200
Ranks are 0-INDEXED; a query counts toward R@K when rank < K
Break similarity ties toward the LOWER gallery index (stable sort of negated scores)
Preserve the order of ks in the output
Round each recall to 4 decimals

Learn this in

Contrastive Learning & CLIPVLM Study Plan

More from VLM 1: Vision-Language Models

Visual Token Pruning by Attention Masshard CHAIR-i and CHAIR-s Hallucination Ratesmedium Merge a LoRA Update into the Base Weightmedium QLoRA Memory Footprint Estimatemedium POPE Precision, Recall, and F1medium

Concept primer

1. Background Knowledge

Recall@K is a fundamental evaluation metric in information retrieval and vision-language models (VLMs) like CLIP. It measures the effectiveness of a retrieval system by calculating the fraction of queries for which the ground-truth item appears within the top $K$ results. In the context of image-text retrieval, this translates to checking if the correct image is ranked among the most similar images to a given text query.

The core concept relies on ranking. For each query, the model produces a similarity score for every item in the gallery. To determine the rank of the ground-truth item, we must sort the gallery items based on these scores in descending order. The position of the ground-truth item in this sorted list is its rank. Crucially, ranks are typically 0-indexed in this specific problem formulation, meaning the best match has rank 0. Therefore, Recall@1 checks if the rank is 0, and Recall@K checks if the rank is less than $K$ .

A critical detail in ranking algorithms is tie-breaking. When multiple gallery items have identical similarity scores, the order in which they appear affects the rank of the ground-truth item. To ensure deterministic and reproducible results, ties must be broken consistently. In this problem, ties are broken by the lower gallery index. This means that if two items have the same score, the one with the smaller index is considered "better" (higher rank) and appears earlier in the sorted list. This deterministic rule prevents variance in metrics due to arbitrary sorting behaviors.

2. Algorithm Approach

The general approach involves processing each query independently to determine the rank of its corresponding ground-truth gallery item. Since the input is a similarity matrix, each row represents the scores for a single query against all gallery items.

Iterate through Queries: Loop through each row of the sim_matrix.
Determine Rank: For each query, identify the position of the ground_truth index when the gallery items are sorted by similarity score (descending) and then by index (ascending) for ties.
Calculate Recall: For each $K$ in the ks list, count how many queries have a rank strictly less than $K$ . Divide this count by the total number of queries to get the recall value.
Format Output: Round the results to 4 decimal places and return them in the same order as the input ks.

The key algorithmic pattern here is ranking with stable sorting. You need to sort pairs of (score, index) to correctly handle ties according to the specified rule.

3. Step-by-Step Strategy

Initialize Variables: Get the number of queries $n$ from the length of sim_matrix. Initialize a list to store the ranks for each query.
Compute Ranks:

For each query index $i$ from 0 to $n-1$ :
Extract the similarity scores for this query: scores = sim_matrix[i].
Identify the ground-truth index: gt_idx = ground_truth[i].
Create a list of tuples combining scores and their original indices: items = [(scores[j], j) for j in range(len(scores))].
Sort items in descending order of score. If scores are equal, sort in ascending order of index. In Python, you can achieve this by sorting with a key that negates the score (for descending) and uses the index (for ascending): key=lambda x: (-x, x).
Find the position (index) of the tuple containing gt_idx in the sorted list. This position is the rank for query $i$ .
Store this rank.

Calculate Recall@K:

Initialize an empty list results.
For each $K$ in the input ks:
Count the number of queries where rank < K.
Compute the recall: count / n.
Round the result to 4 decimal places using round(value, 4).
Append to results.

Return Results: Return the results list.

4. Common Pitfalls

Incorrect Tie-Breaking: Failing to break ties by the lower gallery index will lead to incorrect ranks. Standard sorting might not be stable or might not prioritize the index correctly. Ensure your sort key explicitly handles both score and index.
1-Indexed vs. 0-Indexed Ranks: The problem specifies 0-indexed ranks. Recall@1 means the ground truth is at rank 0 (the very top). If you use 1-indexed ranks, you would check rank <= K, which is a common source of off-by-one errors.
Sorting Order: Remember that higher similarity scores are better. Therefore, you must sort in descending order of scores. Sorting in ascending order will invert the ranks.
Efficiency: While sorting each row is $O(m \log m)$ , doing this for all $n$ queries is acceptable for typical gallery sizes. However, avoid re-sorting for each $K$ . Compute the ranks once, then evaluate for all $K$ values.
Rounding: Ensure you round to 4 decimal places as specified. Using round() in Python is generally sufficient, but be aware of floating-point precision issues if exact equality checks are needed later (though not required here).

5. Time & Space Complexity

Time Complexity: Let $n$ be the number of queries and $m$ be the number of gallery items. For each query, we sort $m$ items, which takes $O(m \log m)$ . Doing this for all $n$ queries results in $O(n \cdot m \log m)$ . Calculating the recall for each $K$ takes $O(n)$ per $K$ , and if there are $k$ values in ks, this adds $O(n \cdot k)$ . The dominant term is usually the sorting, so the overall time complexity is $O(n \cdot m \log m)$ .
Space Complexity: We need to store the ranks for $n$ queries, which takes $O(n)$ space. During sorting, we create a list of $m$ tuples for each query, which takes $O(m)$ space. Thus, the auxiliary space complexity is $O(m)$ (excluding the input and output storage).

solution.py

Python 3.13

Test results