Top-K Retrieval Implementation
What You'll Learn
You'll learn how to efficiently retrieve the k most similar items from a collection of embeddings using sorting and heap-based approaches.
The Challenge of Finding the Best Matches
After computing cosine similarities between a query embedding and thousands (or millions) of document embeddings, you need the top k most similar results—not all of them. For example, a user searches and wants the 5 most relevant documents, not all 10,000 similarities ranked.
Two Practical Approaches
Sorting Approach (Simple)
The straightforward method: compute all similarities, sort them in descending order, and take the first k items.
Analogy: Like grading all exam papers, sorting them from highest to lowest score, then announcing the top 5 students.
This works well for smaller datasets (thousands of items) but requires sorting the entire list—potentially wasteful when you only need a handful of results.
Heap Approach (Efficient)
Use a min-heap of size k. As you scan similarities, maintain only the k largest values seen so far. When you encounter a larger value, replace the smallest item in your heap.
Analogy: Like keeping only the 5 highest exam scores in your hand as you grade papers. When you find a better score, drop the lowest one you're holding.
This approach uses less memory and avoids sorting everything—you only maintain k items at a time.
When to Use Each
- Small datasets or infrequent queries: Sorting is fine and simpler to implement
- Large datasets or real-time systems: Heap-based retrieval reduces computational overhead
- Production systems: Consider approximate nearest neighbor libraries for even faster retrieval at massive scale
Key Takeaway: Top-k retrieval efficiently surfaces the most relevant results by using sorting for simplicity or heaps for memory efficiency, avoiding the cost of ranking every single similarity score.