Vector Databases and ANN Indexes (HNSW, IVF-PQ) TODO
Concept
Vector search means finding items close to a query vector in embedding space; in high dimensions, exact nearest-neighbor search effectively degrades into brute-force comparison, so approximate nearest neighbor (ANN) search is used instead. An ANN index's quality is judged on the tradeoff curve between recall (accuracy) and latency/memory, and no index escapes that curve for free. HNSW builds a hierarchical proximity graph, greedily jumping far via sparse links at the top layers and refining the search at lower layers, with a search-width parameter that trades off recall against speed. IVF-PQ first partitions the vector space into clusters so a query only scans a handful of nearby lists, then compresses vectors into per-subspace codebook indices to cut memory sharply while comparing with approximate distances. Broadly, HNSW uses more memory and gives lower latency, while IVF-PQ is more memory-efficient at large scale.
The perceived quality of RAG or similar-item recommendations is usually decided by the retriever's recall, not the generation model, so if you don't understand how index parameters affect accuracy, you'll end up looking for the cause in the wrong place.
Code & Formula
# 벡터 DB와 ANN 인덱스 — 소규모 벡터 집합에 대한 브루트포스 최근접 탐색을 베이스라인으로 구현.
# 실제 HNSW/IVF-PQ 는 이 exact 결과를 근사(recall<1.0)로 더 빠르게 흉내내는 것이 목표다.
import numpy as np
rng = np.random.default_rng(42)
DIM, N = 8, 200
vectors = rng.normal(size=(N, DIM)).astype("float32")
ids = [f"doc-{i}" for i in range(N)]
def cosine_distance(a, b):
a_n = a / np.linalg.norm(a)
b_n = b / (np.linalg.norm(b, axis=1, keepdims=True) + 1e-9)
return 1.0 - b_n @ a_n
def brute_force_knn(query, k=5):
dists = cosine_distance(query, vectors) # 전수 비교: O(N*DIM)
top_k = np.argsort(dists)[:k]
return [(ids[i], float(dists[i])) for i in top_k]
query = vectors[7] + rng.normal(scale=0.05, size=DIM).astype("float32") # doc-7 근처 질의
result = brute_force_knn(query, k=5)
print("query is a noisy copy of doc-7")
print("brute-force top-5 nearest neighbors (id, cosine distance):")
for doc_id, dist in result:
print(f" {doc_id}: {dist:.4f}")
print("exact search cost: O(N * DIM) per query — ANN indexes trade this for recall < 1.0")
docs/code/algorithms/algorithms-78.py
Exercise
Build tens of thousands of embeddings, treat brute-force results as ground truth, then vary HNSW's search-width parameter and plot the recall@10 vs. query-latency tradeoff curve.
Practical Connection
Vector search on on-chain data itself is rare, but it applies directly to text assets at the service layer — deduplicating market descriptions, recommending similar markets, or searching past dispute cases.
Where it lands in Jayverse
- Verex: pick HNSW vs. IVF-PQ deliberately for market-description dedup or "similar markets" recommendation. Choose on the recall/latency/memory tradeoff this card describes, rather than defaulting to whichever library is easiest to wire up first.
- Verex/Auditor: for vector search over past dispute cases in resolution research, measure retriever recall and report it. The card's point that RAG quality is usually decided by retrieval rather than generation applies directly to a resolution-support tool — a wrong precedent surfaced is worse than none.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| degrade into | 질이 떨어져 ~로 전락하다 · "effectively degrades into brute-force comparison" |
| tradeoff curve | 하나를 얻으면 다른 게 줄어드는 상충 관계 곡선 · "the tradeoff curve between recall" |
| escape ... for free | 공짜로(대가 없이) ~을 피해가다 · "no index escapes that curve for free" |
| greedily | 탐욕적으로, 당장 최선인 선택만 반복해서 · "greedily jumping far via sparse links" |
| scan | (목록을) 훑어보다, 탐색하다 · "a query only scans a handful of nearby lists" |
| cut memory sharply | 메모리를 크게 줄이다 · "cut memory sharply while comparing with approximate distances" |
| look for the cause in the wrong place | 엉뚱한 곳에서 원인을 찾다 · "end up looking for the cause in the wrong place" |
| ANN | 근사 최근접 이웃 탐색(Approximate Nearest Neighbor) · 고차원에서 정확한 최근접 탐색이 사실상 무차별대입이 되므로 쓰는 근사 탐색 기법. "approximate nearest neighbor (ANN) search is used instead" |
| HNSW | 계층적 탐색가능 스몰월드(Hierarchical Navigable Small World) · 근접 그래프를 계층적으로 쌓아 빠르게 탐색하는 ANN 인덱스 알고리즘. "HNSW builds a hierarchical proximity graph" |
| IVF-PQ | 역파일 인덱스+곱셈 양자화(Inverted File Index + Product Quantization) · 벡터 공간을 클러스터로 나눈 뒤 서브공간별로 압축해 메모리를 줄이는 ANN 기법. "IVF-PQ first partitions the vector space into clusters" |
| RAG | 검색증강생성(Retrieval-Augmented Generation) · 검색기로 찾은 문서를 생성모델에 넣는 방식, 품질은 보통 검색기의 recall에 좌우됨. "The perceived quality of RAG or similar-item recommendations" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.