Deduplicate a Retrieval Result List

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

Problem Statement

A retrieval index built from augmented or near-duplicate images returns the same underlying item under several ids. Collapse the ranked list to unique items — keeping each item's best (earliest) position — then take the top-K.

Background

Given a ranked list of (item_id, score) results (best first) where item_id may repeat, produce the deduplicated top-K: for each distinct item_id, keep only its first occurrence (highest rank), preserve the original order, and return the first K ids. This mirrors post-processing a retrieval system before showing results to a user, so the same photo does not fill the page.

Your Task

Implement:

def dedup_topk(results, k):

results: list of (item_id, score) tuples, already sorted best-first.

Return the list of the first K distinct item ids in order.

Input Format

results: list of (item_id, score).
k (int).

Output Format

A list of item ids (length min(K, num_distinct)).

Sample

print(dedup_topk([(5, 0.9), (5, 0.8), (3, 0.7), (2, 0.6)], 2))

Output:

[5, 3]

Example

Input

print(dedup_topk([(5, 0.9), (5, 0.8), (3, 0.7), (2, 0.6)], 2))

Output

[5, 3]

Reasoning

Input: results is a ranked list of four (id, score) pairs, best first: ranks $1$ to $4$ hold ids $5, 5, 3, 2$ with scores $0.9, 0.8, 0.7, 0.6$ . k $= 2$ is how many distinct items to show.
Duplicates: id $5$ appears at rank $1$ and rank $2$ . Both are the same underlying photo, so only its best position (rank $1$ , score $0.9$ ) counts; the rank- $2$ copy is discarded.
Collapsed ranking: after removing repeats the distinct items, in their original order, are $5, 3, 2$ . Three distinct items exist, so the answer has length $\min(K, 3) = \min(2, 3) = 2$ .
Output: the top $2$ of that collapsed list is [5, 3]. Item $2$ is genuinely distinct but falls just outside the cut.
Notice: a naive top-2 of the raw list would be $[5, 5]$ , showing the same photo twice. With k $= 5$ the result would be $[5, 3, 2]$ , shorter than $K$ because only three distinct ids exist. Scores never decide anything here; the list order already encodes rank.

Constraints

0 <= len(results) <= 100000, k >= 0.
Keep each item's earliest occurrence; preserve order.
Return at most K ids.

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 primerPREVIEW

1. Background Knowledge

In retrieval-augmented generation and vision-language models, a query is matched against a large index of items (images, documents, embeddings). Because indices are often built from augmented data—cropped, resized, or slightly perturbed versions of the same source image—the top of the ranked list frequently contains multiple entries that point to the same underlying entity. If you display these raw results, the user sees the same photo five times, which is both confusing and wasteful.

The standard post-processing step is reciprocal rank fusion or, more simply, deduplication by identity. The goal is to collapse the list so each distinct item appears exactly once, at its best (earliest) rank. This preserves the ranking signal: if item 5 appears at positions 1 and 2, we keep position 1 and discard position 2. The operation is order-preserving and idempotent.

This pattern generalizes to any scenario where you have a stream of labeled records and need the first occurrence of each label. It is closely related to stable deduplication in databases and unique-by-key operations in dataframes.

2. Algorithm Approach

The problem is a classic single-pass, first-occurrence filter. Because the input is already sorted best-first, the first time you see an item_id is its optimal position. You do not need to sort, re-rank, or compare scores—only track which ids you have already emitted.

The core data structure is a set for O(1) membership testing. Iterate through the ranked list; for each (item_id, score), check if item_id is in the seen set. If not, add it to the result list and mark it as seen. Stop early once the result list reaches length K.

This is a greedy approach: at each step, you make the locally optimal choice (keep the earliest unseen id), which is globally optimal because the input order already encodes the ranking.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.