Recall@K for Image-Text Retrieval

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.

1. Iterate through Queries: Loop through each row of the sim_matrix.
2. 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.
3. 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.
4. 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

1. Initialize Variables: Get the number of queries $n$ from the length of sim_matrix. Initialize a list to store the ranks for each query.
2. 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.

3. 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.

4. 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).