J5EasyPart J · RecSys & Search Metrics
Cosine Similarity & Vector Top-K Retrieval
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?
💡
Core Mental Anchor / Mnemonic
Unit-normalize first so dot product = cosine similarity, then extract Top-K via argpartition.
📐 Mathematical Derivation & Core Formula
### Normalized Inner Product & Top-K Extraction
Cosine similarity measures the angle between vectors independent of magnitude: .
Pre-normalizing corpus vectors to unit L2 norm reduces cosine similarity to a plain dot product , allowing batched GEMM scoring followed by
Cosine similarity measures the angle between vectors independent of magnitude: .
Pre-normalizing corpus vectors to unit L2 norm reduces cosine similarity to a plain dot product , allowing batched GEMM scoring followed by
argpartition / heap selection for Top- 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 vectors (). 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.