ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← RAG & Agents

AI Builder

FAISS - Tìm kiếm tương tự siêu nhanh

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Thư viện mã nguồn mở của Meta dùng để tìm kiếm vector tương tự hiệu quả trên quy mô lớn.

lesson94 minRAG & AgentsAI Engineer

Dự đoán

Chatbot pháp luật lưu 10 triệu điều luật dưới dạng vector 768 chiều. Tìm kiếm brute-force mất 5 giây mỗi truy vấn; khách hàng muốn dưới 50 ms. Ý tưởng nào thực tế nhất?

Khám phá — ba họ index

Bảng dưới tóm tắt các họ index, cùng khi nào nên chọn từng loại. Các tham số nlist, nprobe, M và efSearch là các núm điều chỉnh trade-off giữa recall và độ trễ.

IndexÝ tưởngKhi nào dùng
IndexFlatL2 / IndexFlatIPBrute-force, chính xác tuyệt đốiDưới 1 triệu vector, hoặc làm chuẩn so sánh
IndexIVFFlatPhân cụm K-means, quét flat trong cụm; tham số nlist và nprobeNhanh hơn nhiều, recall vẫn cao
IndexIVFPQIVF kết hợp nén Product QuantizationTiết kiệm RAM khoảng 50 đến 100 lần
IndexHNSWFlatĐồ thị phân tầng, không cần huấn luyệnRecall cao nhất trên CPU; tốn RAM cho đồ thị

Khoảnh khắc aha

FAISS giống tìm một người quen trong sân vận động 80 nghìn chỗ. Flat hỏi từng người: chính xác tuyệt đối nhưng mất cả ngày. IVF chia sân thành các khu rồi chỉ đến vài khu gần nhất. HNSW có sẵn bản đồ đường đi giữa các hàng ghế, bạn đi theo hàng xóm và mỗi bước gần đích hơn. Cả ba đều cho kết quả đủ gần, nhưng chi phí giảm từ O(N) xuống O(N/nlist) hoặc O(log N).

Thử thách

Bạn chạy IVF với nlist = 1000 và nprobe = 1 trên 10 triệu vector. Có 5% truy vấn trả về kết quả sai hoàn toàn, và đều là truy vấn nằm giữa hai cụm. Khắc phục hợp lý nhất?
Bạn triển khai HNSW với M = 8 và efSearch = 10 trên 5 triệu vector, đo recall chỉ đạt 78% trong khi khách cần từ 95%. Phương án tối ưu đầu tiên?

Giải thích sâu

FAISS (Facebook AI Similarity Search) là thư viện C++ có binding Python cho tìm kiếm vector quy mô lớn. Thường đứng sau các vector database, chịu trách nhiệm lập chỉ mục và truy vấn vector. Khác B-tree hay hash, FAISS tối ưu cho approximate nearest neighbor (ANN), nơi recall 95 đến 99% là đủ và đổi lại độ trễ nhỏ hơn nhiều.

Product quantization

PQ chia vector thành m sub-vector và lượng tử hoá mỗi sub-vector về một trong k tâm:

x∈Rd  ⟶  (q1,q2,…,qm)∈{1,…,k}m\mathbf{x} \in \mathbb{R}^{d} \;\longrightarrow\; (q_1, q_2, \ldots, q_m) \in \{1,\ldots,k\}^m

Với d = 768, m = 8, k = 256: mỗi vector còn 8 byte (thay vì 3072 byte). Khi truy vấn, tính một bảng tra (LUT) kích thước 8 × 256 với query, rồi cộng 8 giá trị cho mỗi vector trong cụm. Nhanh và thân thiện với cache.

HNSW

HNSW xây đồ thị nhiều tầng. Mỗi node được chèn ở tầng ℓ với xác suất P(ℓ) = e^(−ℓ/m_L). Truy vấn bắt đầu ở tầng cao nhất rồi đi greedy xuống dần; ở tầng 0 chạy beam search với ef. Tính chất đồ thị small-world cho độ phức tạp kỳ vọng O(log N), với số cạnh trung bình mỗi node là M.

Ví dụ với FAISS Python API

FAISS Python API - từ Flat tới IVFPQ

import faiss
import numpy as np

# ------------------------------------------------------------------
# Bối cảnh: chatbot pháp luật Việt Nam, 10 triệu đoạn văn 768-d
# ------------------------------------------------------------------
d = 768                        # dimension (e.g. BGE-m3 VN)
n = 10_000_000                 # số vector
xb = np.random.random((n, d)).astype("float32")   # dữ liệu mẫu
xq = np.random.random((1, d)).astype("float32")   # 1 query

# ------------------------------------------------------------------
# 1. Flat (exact search) - baseline, chậm nhưng đúng 100%
# ------------------------------------------------------------------
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)                              # không cần training
D, I = index_flat.search(xq, k=10)              # ~5 s cho 10M trên CPU

# ------------------------------------------------------------------
# 2. IVFFlat - phân cụm, ~100x nhanh hơn
# ------------------------------------------------------------------
nlist = 1000
quantizer = faiss.IndexFlatL2(d)
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist)
index_ivf.train(xb[:200_000])                   # K-means trên sample
index_ivf.add(xb)
index_ivf.nprobe = 10                           # quét 10/1000 cụm
D, I = index_ivf.search(xq, k=10)               # ~50 ms, recall ~95%

# ------------------------------------------------------------------
# 3. IVFPQ - IVF + compression, tiết kiệm RAM 50-100x
# ------------------------------------------------------------------
m = 8                                           # 8 sub-vectors
bits = 8                                        # 256 centroids / sub
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, m, bits)
index_ivfpq.train(xb[:200_000])
index_ivfpq.add(xb)
# RAM: 10M * 8 byte = 80 MB (so với 30 GB của Flat!)
index_ivfpq.nprobe = 16
D, I = index_ivfpq.search(xq, k=10)

# ------------------------------------------------------------------
# 4. HNSW - đồ thị, recall cao nhất trên CPU
# ------------------------------------------------------------------
M = 32                                          # hàng xóm/node
index_hnsw = faiss.IndexHNSWFlat(d, M)
index_hnsw.hnsw.efConstruction = 200            # build-time
index_hnsw.add(xb)                              # không cần train
index_hnsw.hnsw.efSearch = 64                   # query-time
D, I = index_hnsw.search(xq, k=10)              # ~5 ms, recall ~99%

# ------------------------------------------------------------------
# 5. Factory string (khuyên dùng khi làm production)
# ------------------------------------------------------------------
index = faiss.index_factory(d, "IVF1024,PQ16x8", faiss.METRIC_L2)
index.train(xb[:200_000])
index.add(xb)

# ------------------------------------------------------------------
# 6. GPU (nếu có)
# ------------------------------------------------------------------
res = faiss.StandardGpuResources()
gpu_index = faiss.index_cpu_to_gpu(res, 0, index_flat)
D, I = gpu_index.search(xq, k=10)               # ~30x nhanh hơn CPU

# ------------------------------------------------------------------
# 7. Lưu / tải index
# ------------------------------------------------------------------
faiss.write_index(index, "law_vn.index")
loaded = faiss.read_index("law_vn.index")

Đo trade-off recall và độ trễ

Benchmark recall vs latency - sweep nprobe

import time
import numpy as np
import faiss

def eval_index(index, xq, gt, k=10, nprobes=(1, 4, 8, 16, 32, 64)):
    """Sweep nprobe, đo recall@k và latency trung bình."""
    results = []
    for np_ in nprobes:
        index.nprobe = np_
        t0 = time.time()
        D, I = index.search(xq, k)
        lat = (time.time() - t0) / len(xq) * 1000   # ms/query
        recall = (I == gt[:, :k]).any(axis=1).mean()
        results.append((np_, recall, lat))
    return results

# ground truth bằng Flat
flat = faiss.IndexFlatL2(d)
flat.add(xb)
_, gt = flat.search(xq, 10)

ivf = faiss.index_factory(d, "IVF1024,Flat")
ivf.train(xb[:200_000])
ivf.add(xb)

for np_, r, lat in eval_index(ivf, xq, gt):
    print(f"nprobe={np_:<3d}  recall={r:.3f}  latency={lat:.2f} ms")

# Ví dụ output:
# nprobe=1    recall=0.612  latency=0.41 ms
# nprobe=4    recall=0.842  latency=1.03 ms
# nprobe=8    recall=0.925  latency=1.72 ms
# nprobe=16   recall=0.974  latency=2.95 ms
# nprobe=32   recall=0.993  latency=5.44 ms

Vì sao FAISS nhanh?

  • Lệnh SIMD (AVX2, AVX-512): một lệnh CPU so sánh 8 đến 16 float32 cùng lúc; FAISS có kernel riêng cho khoảng cách L2 và tích trong.
  • Bố cục bộ nhớ thân thiện cache: vector lưu liên tiếp; với PQ, bảng LUT 256 × m byte vừa trong L1.
  • Song song OpenMP hoặc TBB: khi tìm kiếm theo lô, mỗi truy vấn chạy một luồng; tỷ lệ tăng tốc gần tuyến tính theo số nhân.

Trên GPU, FAISS dùng kernel CUDA tuỳ chỉnh cho bước chọn top-k trong warp, nên các baseline ANN trên GPU hiện nay vẫn dùng FAISS làm chuẩn so sánh.

Trade-off recall và latency

Chi phí trung bình của IVF, bỏ qua overhead của centroid:

TIVF≈nprobenlist⋅N⋅dT_{\mathrm{IVF}} \approx \frac{n_{\mathrm{probe}}}{n_{\mathrm{list}}} \cdot N \cdot d

Recall xấp xỉ bằng xác suất top-k thật nằm trong các cụm đã chọn:

Recall@k≈1−(1−nprobenlist)nneigh\mathrm{Recall@}k \approx 1 - \left(1 - \frac{n_{\mathrm{probe}}}{n_{\mathrm{list}}}\right)^{n_{\mathrm{neigh}}}

Tăng gấp đôi nprobe không luôn tăng gấp đôi recall; đường cong bão hoà, tạo hình 'đầu gối' của trade-off.

Tóm tắt

  • FAISS là thư viện C++ và Python của Meta cho tìm kiếm tương đồng trên hàng tỷ vector, hỗ trợ CPU, GPU và xử lý theo lô.
  • Flat là chuẩn chính xác với độ phức tạp O(N). IVF chia cụm K-means, giảm chi phí xuống khoảng O(N · nprobe / nlist).
  • HNSW xây đồ thị phân tầng, đạt khoảng O(log N) với recall 95 đến 99% khi tinh chỉnh efSearch.
  • Product quantization nén vector khoảng 10 đến 100 lần: 768 float (3 KB) thành 8 đến 64 byte mỗi vector.
  • nprobe (IVF) và efSearch (HNSW) là hai núm chính đánh đổi giữa recall và độ trễ.
  • FAISS không thay thế vector database khi cần lưu bền, lọc metadata hay đa khách hàng.

Continue the module

Lesson 4 of 16