mediumRAGRetrievalEmbeddings
Top-K Similar Documents
Return the indexes of the k document embeddings most similar to a query embedding, the core of the retrieval step in a RAG system, with a stable tie-break.
JavaScript or Python
The retrieval step of a RAG system embeds the user's question and finds the stored chunks whose embeddings are most similar. Given a query vector, a list of document vectors docs and an integer k, return the indexes of the k documents with the highest cosine similarity to the query, most similar first.
If two documents have exactly the same similarity, the one with the smaller index comes first. A zero vector has similarity 0 with everything. If k is larger than the number of documents, return all of them.
Examples
Example 1
Input: query = [1, 0], docs = [[0, 1], [1, 0], [1, 1]], k = 2 Output: [1, 2] Why: Doc 1 is identical in direction (1.0); doc 2 is at 45 degrees (0.707)
Example 2
Input: query = [1, 1], docs = [[2, 2], [1, 1], [1, 0]], k = 2 Output: [0, 1] Why: Docs 0 and 1 tie at 1.0; the smaller index wins
Constraints
1 <= docs.length <= 10^41 <= query.length == docs[i].length <= 10241 <= k
Hints
Hint 1
Score every document with cosine similarity, keeping its index.
Hint 2
Sort by score descending, then index ascending, and take the first k.
Solution
Show the solution (try it yourself first)
Compute each document's cosine similarity with the query, pair it with its index, and sort by similarity (highest first) with the index as the tie-breaker. Slicing the first k handles a k larger than the list automatically.
def top_k_similar(query, docs, k):
def cos(a, b):
dot = sum(x * y for x, y in zip(a, b))
na = sum(x * x for x in a) ** 0.5
nb = sum(y * y for y in b) ** 0.5
return 0.0 if na == 0 or nb == 0 else dot / (na * nb)
scored = [(cos(query, d), i) for i, d in enumerate(docs)]
scored.sort(key=lambda t: (-t[0], t[1]))
return [i for _, i in scored[0:k]]Complexity
Time O(n × d + n log n) for n documents of dimension d; a heap brings the selection to O(n log k). Space O(n). This brute-force scan is exact and fine for thousands of chunks; vector databases use approximate nearest-neighbour indexes such as HNSW to answer the same question over millions of vectors in milliseconds, trading a little recall for speed. That trade-off is a common follow-up question.
Found a mistake in this problem, its tests or the solution?