Bài 17: Index types: HNSW vs IVF vs Flat

Sau bài này, bạn cần:

• Mô tả được cơ chế hoạt động của Flat, IVF và HNSW — không cần chứng minh toán học, nhưng phải giải thích được tại sao mỗi loại nhanh hay chậm.
• Biết ý nghĩa và tác động của các tham số: nprobe (IVF), M, ef_construction, ef_search (HNSW).
• Hiểu quantization (PQ, SQ8) là gì và khi nào cần dùng.
• Chạy được code FAISS để tạo 3 loại index và đo recall@K.
• Chọn được index phù hợp cho các tình huống dataset nhỏ / vừa / lớn.

Cho N vectors trong ℝ^d và một query vector q, bài toán là tìm top-K vectors gần nhất theo distance metric (L2 Euclidean, cosine similarity, hoặc dot product). Exact search (linear scan) có complexity O(N×d) — với N = 1 triệu và d = 768, mỗi query tốn hàng trăm ms trên CPU. Approximate Nearest Neighbor (ANN) giảm complexity xuống O(log N) hoặc O(√N) bằng cách chấp nhận recall < 100%, tức có thể miss một vài vector trong top-K thực sự. Mức recall bao nhiêu là "đủ" phụ thuộc vào use case — RAG thường chấp nhận recall@10 ≥ 0.95.

Flat index không xây cấu trúc dữ liệu phụ. Khi query, nó tính distance giữa q và từng vector trong store rồi lấy top-K nhỏ nhất. Đây là cách duy nhất đảm bảo recall = 100% (kết quả exact).

Đặc điểm kỹ thuật

• Recall: 100% — exact, không approximate.
• Query complexity: O(N×d). Không có shortcut.
• Build time: O(N) — chỉ cần lưu vector vào mảng liên tiếp, không cần train.
• Memory: N × d × 4 bytes (float32). 1 triệu vector × 768 chiều = ~3 GB.

Khi nào phù hợp

• Dataset nhỏ (dưới ~10k vectors) — ở quy mô này O(N) không đáng kể.
• Làm ground truth khi đo recall của ANN index khác.
• Prototype nhanh không cần tuning.

Trong FAISS, Flat index tương ứng với faiss.IndexFlatL2 (L2) hoặc faiss.IndexFlatIP (inner product / cosine nếu vector đã normalize). ChromaDB nhỏ dùng HNSW nhưng có thể fall back sang brute-force khi collection quá nhỏ.

Giới hạn

Ở N = 100k+ và d = 384+, latency mỗi query bắt đầu leo vào vùng chậm cho realtime. Flat không scale — không có hyperparameter nào để trade off recall lấy tốc độ. Đây là lý do cần IVF hoặc HNSW.

IVF (Inverted File Index) chia toàn bộ vector thành nlist cụm bằng k-means. Mỗi cụm có một centroid. Khi query:

1. Tính distance từ q đến tất cả nlist centroid — O(nlist × d).
2. Chọn nprobe cụm có centroid gần nhất.
3. Brute-force tìm top-K chỉ trong các cụm đó.

Thay vì scan N vectors, IVF chỉ scan trung bình nprobe × (N / nlist) vectors. Với nlist = √N, mỗi cụm có ~√N vector; scan nprobe cụm là O(nprobe × √N).

Tham số quan trọng

• nlist: số cụm k-means. Rule of thumb: nlist ≈ 4×√N đến 16×√N. Quá nhỏ — mỗi cụm lớn, không giảm được scan; quá lớn — centroid table lớn, khó tìm cụm đúng.
• nprobe: số cụm scan khi query. Tuning realtime không cần rebuild. nprobe=1 → nhanh nhất nhưng recall thấp; nprobe=nlist → giống Flat (recall 100% nhưng mất lợi thế). Thực tế dùng nprobe = 8-64 tùy yêu cầu recall.

Build time và memory

IVF cần train — bước k-means chạy trên tập training data trước khi add vector. Build time O(N × nlist × iterations) — có thể từ vài phút đến vài giờ với dataset 10M+. Sau khi train, add vector O(N). Memory chính là lưu N vector + nlist centroid (nlist × d × 4 bytes — không đáng kể so với N).

Giới hạn

Cluster boundary là điểm yếu của IVF: nếu vector query nằm gần biên giữa hai cụm, cụm đúng có thể không nằm trong nprobe được chọn → recall giảm. Tăng nprobe giảm vấn đề này nhưng tăng latency. Ngoài ra, centroid được tính 1 lần khi train — nếu data distribution thay đổi nhiều theo thời gian, cần rebuild index.

HNSW (Hierarchical Navigable Small World) — Malkov & Yashunin, arXiv:1603.09320 (2016) — tổ chức vector thành một đồ thị có cấu trúc phân cấp:

• Layer 0: chứa toàn bộ N vector, mỗi node kết nối với tối đa M neighbors gần nhất.
• Layer 1, 2, ...: mỗi lớp là subset ngẫu nhiên của lớp dưới (xác suất theo phân phối hàm mũ). Lớp càng cao càng thưa.

Khi query, HNSW bắt đầu tại entry point ở lớp cao nhất, greedy traverse về phía vector gần nhất, rồi xuống lớp thấp hơn khi không còn cải thiện được. Layer cao (thưa) giúp "nhảy" nhanh qua không gian; layer 0 (dày) cho kết quả chính xác cục bộ.

Ba tham số chính

• M (số neighbor mỗi node, default 16–32): tăng M → graph dày hơn → recall cao hơn nhưng memory và build time tăng tuyến tính. M=16 là điểm cân bằng phổ biến; M=32 khi cần recall cao hơn và RAM dư.
• ef_construction (candidate set khi build, default 100–200): số node được xem xét khi thêm mỗi vector vào graph. Tăng ef_construction → graph chất lượng cao hơn → recall cao hơn, nhưng build chậm hơn. Ảnh hưởng chỉ ở build time, không ảnh hưởng query sau khi index đã xây.
• ef_search (candidate set khi query, default = topK): số node được duyệt trong beam search khi query. Tăng ef_search → recall cao hơn, latency cao hơn. Đây là tham số duy nhất có thể tune realtime không cần rebuild. ef_search phải ≥ K (số kết quả cần).

Complexity và memory

• Build: O(N × log N × M). N = 1M, M = 16 → vài phút trên CPU.
• Query: O(log N) — sub-linear, nhanh hơn IVF trong nhiều benchmark.
• Memory: đáng kể hơn IVF. Mỗi vector cần lưu thêm graph edges: ≈ M × 2 × d × 4 bytes per vector ngoài vector data. Với d=768, M=16 → overhead ~50 MB trên mỗi 1M vector (graph edges thôi, chưa tính vector data).

Recall thực tế với ef_search hợp lý (ef_search = 64–256, K = 10): thường 97–99% trên các benchmark ANN phổ biến (ann-benchmarks.com).

Incremental insert

HNSW hỗ trợ thêm vector mới mà không cần rebuild toàn bộ index — mỗi vector mới được insert vào graph theo cùng thuật toán. IVF không hỗ trợ tốt: thêm vector mới không thay đổi centroid, nên nếu data thay đổi nhiều theo thời gian thì cluster lệch và recall giảm.

Khi dataset đạt hàng chục triệu vector, lưu toàn bộ float32 tốn quá nhiều RAM. Quantization nén vector để giảm memory với trade-off recall nhỏ.

Product Quantization (PQ)

PQ chia vector d chiều thành M sub-vector, mỗi sub-vector được quantize sang 1 code 8-bit (256 codeword). Thay vì lưu d × 4 bytes, chỉ lưu M bytes per vector — giảm memory 8–32× tùy cấu hình.

• IVF_PQ: IVF kết hợp PQ. Vector trong mỗi cluster được quantize. Memory giảm 8–32×, recall giảm ~2–5% so với IVF_Flat.
• HNSW + PQ: graph giữ cấu trúc HNSW nhưng distance tính trên vector đã quantize. Memory thấp hơn HNSW thuần; recall hơi giảm.

Scalar Quantization (SQ)

Chuyển float32 (4 bytes/chiều) sang int8 (1 byte/chiều) — giảm memory 4×. Recall hầu như không thay đổi với SQ8 vì phạm vi lượng tử hóa đủ dày cho embedding thực tế. Đây là option dễ dùng nhất khi cần giảm RAM mà không muốn mất recall.

Binary Quantization (BQ)

Mỗi chiều chuyển thành 1 bit (dương → 1, âm → 0). Giảm memory 32×, tính Hamming distance cực nhanh. Nhưng recall giảm mạnh với embedding thông thường — chỉ hiệu quả với embedding được huấn luyện riêng cho BQ (ví dụ: Matryoshka binary embedding). Thường dùng cho bước coarse retrieval rồi rerank bằng float32.

Cài đặt: pip install faiss-cpu (hoặc faiss-gpu nếu có CUDA). FAISS là thư viện của Meta Research, hỗ trợ cả 3 loại index và variants PQ/SQ.

import faiss
import numpy as np

# Dataset ngẫu nhiên — thay bằng embedding thực tế
d = 384          # số chiều (phù hợp all-MiniLM-L6-v2)
N = 100_000      # số vector trong store
xb = np.random.random((N, d)).astype("float32")   # vector database
xq = np.random.random((10, d)).astype("float32")  # 10 queries

# ----------------------------------------------------------------
# 1. Flat (brute-force, exact)
# ----------------------------------------------------------------
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)                                # không cần train
D_flat, I_flat = index_flat.search(xq, k=5)      # D: distances, I: indices
print("Flat top-5:", I_flat[0])

# ----------------------------------------------------------------
# 2. HNSW
# ----------------------------------------------------------------
M = 32                                            # neighbors per node
index_hnsw = faiss.IndexHNSWFlat(d, M)
index_hnsw.hnsw.efConstruction = 200             # candidate set khi build
index_hnsw.add(xb)                               # không cần train
index_hnsw.hnsw.efSearch = 64                    # candidate set khi query
D_hnsw, I_hnsw = index_hnsw.search(xq, k=5)
print("HNSW top-5:", I_hnsw[0])

# ----------------------------------------------------------------
# 3. IVF (cần train trước)
# ----------------------------------------------------------------
nlist = 100                                       # số cluster, ~4*sqrt(N) đến 16*sqrt(N)
quantizer = faiss.IndexFlatL2(d)                  # quantizer tính distance đến centroid
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist)
index_ivf.train(xb)                              # k-means — bắt buộc
index_ivf.add(xb)
index_ivf.nprobe = 10                            # số cluster scan khi query
D_ivf, I_ivf = index_ivf.search(xq, k=5)
print("IVF top-5:", I_ivf[0])

# ----------------------------------------------------------------
# 4. IVF_PQ — giảm memory với Product Quantization
# ----------------------------------------------------------------
M_pq = 16        # số sub-quantizer (phải chia hết d; d=384, M_pq=16 → 24 chiều/sub)
nbits = 8        # bits per code (8 = 256 codeword per sub)
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, M_pq, nbits)
index_ivfpq.train(xb)
index_ivfpq.add(xb)
index_ivfpq.nprobe = 10
D_pq, I_pq = index_ivfpq.search(xq, k=5)
print("IVF_PQ top-5:", I_pq[0])

Lưu ý: IndexHNSWFlat không hỗ trợ remove_ids trong FAISS — nếu cần delete vector, dùng IndexIDMap wrapper hoặc chuyển sang IndexHNSWSQ. Các vector DB như Qdrant/Milvus handle delete ở tầng storage của họ, không bị giới hạn này.

Recall@K = (số item trong top-K của ANN cũng có trong top-K của exact NN) / K. Đây là metric chính để đánh giá ANN index.

Cách đo: dùng Flat index làm ground truth, so sánh kết quả với ANN index trên cùng bộ query.

def compute_recall(index_ann, index_exact, queries, k=10):
    """
    Tính recall@K trung bình trên tập queries.
    index_ann   : ANN index cần đo (HNSW, IVF...)
    index_exact : Flat index làm ground truth
    queries     : numpy array (nq, d) float32
    k           : số kết quả top-K
    """
    _, I_ann = index_ann.search(queries, k)
    _, I_exact = index_exact.search(queries, k)

    recalls = []
    for i in range(len(queries)):
        ann_set = set(I_ann[i].tolist())
        exact_set = set(I_exact[i].tolist())
        # Loại bỏ -1 (FAISS trả -1 khi không đủ kết quả)
        ann_set.discard(-1)
        exact_set.discard(-1)
        if len(exact_set) == 0:
            continue
        recall = len(ann_set & exact_set) / len(exact_set)
        recalls.append(recall)

    return sum(recalls) / len(recalls) if recalls else 0.0


# Ví dụ đo recall HNSW với ef_search khác nhau
xq_test = np.random.random((100, d)).astype("float32")
for ef in [10, 32, 64, 128, 256]:
    index_hnsw.hnsw.efSearch = ef
    r = compute_recall(index_hnsw, index_flat, xq_test, k=10)
    print(f"ef_search={ef:4d}  recall@10={r:.4f}")

Kết quả điển hình (dataset random, d=384, N=100k, M=32, ef_construction=200):

Số liệu trên là ước tính trên dữ liệu Gaussian ngẫu nhiên. Dữ liệu embedding thực tế (text, image) thường có distribution clustering tự nhiên → recall cao hơn ở cùng ef_search. Đo trên data thực của hệ thống cụ thể trước khi quyết định ef_search.

Nếu không chắc, bắt đầu với HNSW (M=16, ef_construction=200, ef_search=64) — đây là default của hầu hết vector DB hiện đại và hoạt động tốt trên phần lớn dataset từ 10k đến vài triệu vector.

Mỗi vector DB expose index khác nhau qua config — hiểu internals giúp đọc được tài liệu của từng DB nhanh hơn:

• Dùng IVF mà không train. FAISS sẽ báo lỗi assert d == this->d hoặc kết quả không hợp lệ (index trả -1) nếu gọi add() trước train(). Kiểm tra bằng index.is_trained.
• ef_search < K. HNSW yêu cầu ef_search ≥ K. Nếu ef_search = 10 nhưng bạn query k=50, FAISS sẽ tự raise hoặc trả kết quả thiếu. Luôn set ef_search ≥ K × 4 để có recall hợp lý.
• PQ với M_pq không chia hết d. d=384 và M_pq=32 → 12 chiều/sub (OK). d=768 và M_pq=100 → 7.68 chiều/sub (lỗi). Chọn M_pq sao cho d % M_pq == 0.
• Không đo recall sau khi thay đổi index hoặc data. Tăng ef_search không đồng nghĩa recall tăng đủ; chỉ có đo thực tế mới xác nhận được. Tương tự, nâng từ Flat sang HNSW mà không đo recall có thể bỏ sót regression.
• IVF với centroid stale. Nếu 30–40% data thay đổi sau khi train, centroid không còn represent cluster tốt → recall giảm. Với data thay đổi liên tục, HNSW (incremental insert không cần rebuild) phù hợp hơn.
• BQ trên embedding thông thường. Binary quantization giảm memory 32× nhưng recall có thể rớt xuống dưới 0.7 với embedding float32 thông thường. BQ chỉ hiệu quả khi embedding model được huấn luyện cụ thể để tương thích với BQ (ví dụ: Cohere Embed v3 với input_type="search_query" + BQ mode).

Bài 18: Metadata filtering — kết hợp vector search với điều kiện