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.
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ưởng | Khi nào dùng |
|---|---|---|
| IndexFlatL2 / IndexFlatIP | Brute-force, chính xác tuyệt đối | Dưới 1 triệu vector, hoặc làm chuẩn so sánh |
| IndexIVFFlat | Phân cụm K-means, quét flat trong cụm; tham số nlist và nprobe | Nhanh hơn nhiều, recall vẫn cao |
| IndexIVFPQ | IVF kết hợp nén Product Quantization | Tiết kiệm RAM khoảng 50 đến 100 lần |
| IndexHNSWFlat | Đồ thị phân tầng, không cần huấn luyện | Recall 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
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:
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 msVì 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:
Recall xấp xỉ bằng xác suất top-k thật nằm trong các cụm đã chọn:
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.