High-Dimensional Embedding Similarity

Roblox may compare high-dimensional embeddings for experiences, avatars, or recommendations. Given query embeddings and candidate embeddings, return the exact k candidates with the highest cosine similarity for every query while avoiding storage of the full query-by-candidate similarity matrix.

Implement top_k_embedding_matches(query_embeddings, candidate_embeddings, k).

Formal Specification

• query_embeddings is a non-empty list of Q vectors.
• candidate_embeddings is a non-empty list of C vectors.
• Every vector is a list of D finite numbers, and all vectors have the same dimension.
• k satisfies 1 <= k <= C.
• Return a list of Q lists. Each inner list contains exactly k pairs [candidate_index, similarity], ordered by decreasing cosine similarity and then increasing candidate index.
• Return each similarity rounded to 6 decimal places.
• The cosine similarity of any zero vector with another vector is defined as 0.0.

Your implementation must normalize each vector once, process candidates in blocks, and maintain only a bounded min-heap per query. Do not construct a Q x C matrix.