J5EasyPart J · RecSys & Search Metrics

Cosine Similarity & Vector Top-K Retrieval

⚡Flashcard Drill➔

L2-normalize embeddings and use dot-product GEMM + `argpartition` for fast Top-K cosine retrieval.

⏱️ Time: O(N * M * D + N * M)
💾 Space: O(N * M)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def vector_topk_retrieval(
queries: np.ndarray, # (N, D)
corpus: np.ndarray, # (M, D)
top_k: int = 5
) -> tuple:
# 1. L2 范数归一化 (防除零)
q_norm =
c_norm = corpus / np.maximum(np.linalg.norm(corpus, axis=-1, keepdims=True), 1e-12)
# 2. 批量点积计算相似度: (N, D) @ (D, M) -> (N, M)
scores = q_norm @ c_norm.T
# 3. 使用 argpartition 快速提取 top_k (比全排序快数倍)
topk_indices = np.argpartition(-scores, kth=top_k-1, axis=-1)[:, :top_k]
# 局部按相似度精确降序排序
row_indices = np.arange(len(queries))[:, np.newaxis]
part_scores = scores[row_indices, topk_indices]
sort_order = np.argsort(-part_scores, axis=-1)
final_indices = np.take_along_axis(topk_indices, sort_order, axis=-1)
final_scores =
return final_indices, final_scores
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Why is HNSW in vector databases dramatically faster than brute-force matrix search?
Next: BM25 (Okapi BM25) Ranking Algorithm →
💡

Core Mental Anchor / Mnemonic

Unit-normalize first so dot product = cosine similarity, then extract Top-K via argpartition.

📐 Mathematical Derivation & Core Formula

cos⁡(θ)=u⋅v∥u∥2∥v∥2=(u∥u∥)(v∥v∥)⊤\cos(\theta) = \frac{u \cdot v}{\|u\|_2 \|v\|_2} = \left(\frac{u}{\|u\|}\right) \left(\frac{v}{\|v\|}\right)^\top
### Normalized Inner Product & Top-K Extraction
Cosine similarity measures the angle between vectors independent of magnitude: cos⁡(θ)=⟨u,v⟩∥u∥2∥v∥2∈[−1,1]\cos(\theta) = \frac{\langle u, v \rangle}{\|u\|_2 \|v\|_2} \in [-1, 1].
Pre-normalizing corpus vectors to unit L2 norm reduces cosine similarity to a plain dot product ⟨u~,v~⟩\langle \tilde{u}, \tilde{v} \rangle, allowing batched GEMM scoring followed by argpartition / heap selection for Top-KK retrieval.

🔄 Tensor Dimensions & Shape Flow

queries (N, D), corpus (M, D) -> unit L2 norm -> matmul (N, M) -> argpartition top_k -> sort slice

🛡️ Numerical Stability & Pitfalls Checklist

  • Clamp vector norms with np.maximum(norm, 1e-12) to prevent NaNs on all-zero vectors.
  • Use np.argpartition (O(M)) plus small local sort over K items instead of full O(M log M) sort.

💻 Reference Code Implementation

import numpy as np

def vector_topk_retrieval(
    queries: np.ndarray,      # (N, D)
    corpus: np.ndarray,       # (M, D)
    top_k: int = 5
) -> tuple:
    # 1. L2 范数归一化 (防除零)
    q_norm = queries / np.maximum(np.linalg.norm(queries, axis=-1, keepdims=True), 1e-12)
    c_norm = corpus / np.maximum(np.linalg.norm(corpus, axis=-1, keepdims=True), 1e-12)
    
    # 2. 批量点积计算相似度: (N, D) @ (D, M) -> (N, M)
    scores = q_norm @ c_norm.T
    
    # 3. 使用 argpartition 快速提取 top_k (比全排序快数倍)
    topk_indices = np.argpartition(-scores, kth=top_k-1, axis=-1)[:, :top_k]
    
    # 局部按相似度精确降序排序
    row_indices = np.arange(len(queries))[:, np.newaxis]
    part_scores = scores[row_indices, topk_indices]
    sort_order = np.argsort(-part_scores, axis=-1)
    
    final_indices = np.take_along_axis(topk_indices, sort_order, axis=-1)
    final_scores = np.take_along_axis(part_scores, sort_order, axis=-1)
    
    return final_indices, final_scores

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
corpus = np.array([[1.0, 0.0], [0.0, 1.0], [-1.0, 0.0]])
query = np.array([[0.9, 0.1]]) # 明显与第 0 个最像
idx, scores = vector_topk_retrieval(query, corpus, top_k=1)
assert idx[0, 0] == 0
assert scores[0, 0] > 0.9
print("✓ 向量余弦 Top-K 检索自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:Why is HNSW in vector databases dramatically faster than brute-force matrix search?
Brute-force compares against all MM vectors (O(M)O(M)). HNSW builds a multi-layer navigable small-world graph (resembling skip lists), jumping long distances in upper layers before local greedy search, achieving sub-linear query latency on million-vector indexes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Confusion Matrix, Precision, Recall & Macro/Micro F1Back to Part J & All 105Next: BM25 (Okapi BM25) Ranking Algorithm →