Implement Vector Top-k Retrieval with Cosine Similarity

Free with account Updated Nov 16, 2026 · 4 min read
On this page

    Problem statement

    Implement top_k_cosine(query, docs, k) in NumPy. query is an embedding vector of length D and docs is an (N, D) matrix of document embeddings. Return the indices and cosine similarity scores of the k most similar documents, best first. It should be fast for N in the millions on one machine.

    The retrieval step of every RAG system, in miniature. Interviewers use it to check vectorisation, numerical care and complexity, and as a lead-in to approximate search.

    Example

    Cosine ranks documents by direction; length doesn't matter.
    Cosine ranks documents by direction; length doesn't matter.
    docs  = [[1,0,0], [0.9,0.1,0], [0,1,0], [0.7,0.7,0], [-1,0,0]]
    query = [1, 0.2, 0]
    top_k_cosine(query, docs, 3) → indices [1, 0, 3], scores [0.996, 0.981, 0.832]

    Constraints (assumed)

    • N up to a few million, D between 64 and 4,096, float32.
    • k much smaller than N.
    • NumPy only.

    What this question tests

    • Vectorising the similarity computation.
    • Knowing cosine vs dot product and when they're the same.
    • Selection in O(N) instead of a full O(N log N) sort.
    • Thinking about scale: memory, batching queries, and when to use an ANN index.

    Questions to ask first

    1. Are the embeddings already normalised? (Assume not.)
    2. One query or a batch? (One; batching is a follow-up.)
    3. Is k ever larger than N? (Clamp it.)
    4. Do we need filters (tenant, date)? (Not here.)
    5. Exact results, or is approximate acceptable? (Exact here.)