Multi-Query Fan-Out + Dedup

Background

Multi-query fan-out sends a few paraphrases of the user's question through retrieval in parallel, then merges the result lists. The merge must preserve rank order (top results stay near the top) and deduplicate by doc id so the same chunk doesn't appear twice.

Problem statement

Implement merge_dedup(result_lists, top_k). Walk each input list sequentially (first list fully, then second, etc.); track a seen set; append unseen ids in order; stop when top_k reached.

Input

• result_lists — list[list[str]], ranked doc-id lists, one per query.
• top_k — int >= 0, output cap.

Output

Returns list[str] of length $\le$ top_k, deduplicated, in merge order.

Examples

Example 1 — two lists with overlap

Input:  [["a","b","c"], ["b","d","e"]], top_k=5
Output: ["a","b","c","d","e"]

Example 2 — top-k cap

Input:  [["a","b","c"], ["d","e","f"]], top_k=2
Output: ["a","b"]

Example 3 — empty input

Input:  [], top_k=5
Output: []

Example 4 — duplicate-heavy single list

Input:  [["a","a","a"]], top_k=3
Output: ["a"]

Constraints

• Lists are processed sequentially (one then the next), not round-robin.
• Output preserves the order in which ids are first seen.
• top_k = 0 → return [].

Notes

• vs RRF. Reciprocal Rank Fusion is the alternative — weighted by rank rather than dedup-on-first-seen. RRF is better when the queries are diverse; sequential dedup is fine when the queries are paraphrases of one intent.
• Round-robin variant. Some implementations alternate list[0][0], list[1][0], list[0][1], ... for more diversity. Sequential is the simpler, more common choice.