Recall@K and Median Rank Together
Problem Statement
Image-text retrieval papers report a bundle of metrics: R@1, R@5, R@10 and the median rank. Compute all four from the ranked-id lists in a single pass over the queries.
Background
For each query with a single correct item, its rank is the 1-based position of that item in the ranked list (or len(list) + 1 if absent). Then:
- R@K is the fraction of queries whose rank <= K, reported as a percentage rounded to 2 decimals.
- The median rank is the median of all per-query ranks (lower is better). For an even number of queries use the average of the two middle values.
Your Task
Implement:
def retrieval_report(rankings, relevant, ks=(1, 5, 10)):
Return a dict:
- "recall": dict mapping each K to its R@K percentage (2 decimals).
- "median_rank": the median rank (a float; use .0 for integers, halves for even counts).
Input Format
- rankings: list of ranked-id lists.
- relevant: list of correct ids.
- ks: tuple of cutoffs.
Output Format
- A dict with "recall" and "median_rank".
Sample
print(retrieval_report([[1, 2, 3], [4, 5, 6], [9, 8, 7]], [1, 6, 7]))
Output:
{'recall': {1: 33.33, 5: 100.0, 10: 100.0}, 'median_rank': 3.0}
Example:
print(retrieval_report([[1, 2, 3], [4, 5, 6], [9, 8, 7]], [1, 6, 7]))
{'recall': {1: 33.33, 5: 100.0, 10: 100.0}, 'median_rank': 3.0}Ranks are 1, 3, 3. R@1 = 1/3 = 33.33%. R@5 and R@10 catch all three = 100%. Median of [1,3,3] is 3.0.
Constraints:
len(rankings) == len(relevant),1 <= Q <= 5000.- Rank is 1-based; a missing item ranks
len(list) + 1. - R@K is a percentage rounded to 2 decimals; median uses the two-middle average for even Q.
1. Background Knowledge
Recall@K is a standard metric in information retrieval and image-text retrieval. For a query with a single relevant item, the item has a rank equal to its 1-based position in the ranked list of candidates. If the relevant item is not present in the list at all, its rank is defined as len(list)+1. Recall@K for a single query is 1 if rank≤K, otherwise 0. The overall R@K is the mean of these binary indicators across all queries, expressed as a percentage.
The median rank provides a complementary view. While R@K only tells you whether the relevant item made it into the top-K, the median rank tells you how far the relevant item typically sits in the ranking. For an even number of queries, the median is the arithmetic mean of the two middle ranks after sorting. A lower median rank indicates better retrieval quality.
In vision-language model (VLM) evaluation, these metrics are computed over a held-out test set where each query image (or text) has exactly one ground-truth match. The "ranked-id list" represents the model's ordering of all candidate items by similarity score.
2. Algorithm Approach
This is a single-pass aggregation problem. You iterate over each query once, compute its rank, and accumulate:
- A counter for each K∈ks: increment if rank≤K.
- A list (or running structure) of all ranks for the median computation.
After the loop, divide each counter by the total number of queries to get the percentage, and compute the median from the collected ranks. No sorting of the original rankings is needed since they are already sorted by the model.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.