Vector Databases — FAISS, HNSW, tìm nearest neighbor trong triệu vector

Giải mã cơ chế tìm kiếm vector tương tự trong triệu embedding chỉ trong miliseconds — từ HNSW graph đến Product Quantization, và tại sao RAG không thể tồn tại thiếu chúng.

Mỗi khi ChatGPT trả lời câu hỏi về tài liệu nội bộ của bạn, hoặc khi Spotify gợi ý bài hát tiếp theo, phía sau đang diễn ra một phép tính geometry ở quy mô khổng lồ: tìm vector "gần nhất" trong hàng triệu, thậm chí tỷ embedding, chỉ trong vài chục miliseconds. Đây không phải là "tìm kiếm thông thường" — đây là nghệ thuật nén không gian chiều cao vào cấu trúc dữ liệu đặc biệt, nơi đánh đổi 5% độ chính xác để đổi lấy tốc độ tăng 100 lần.

Vấn đề

Tưởng tượng bạn có 10 triệu tài liệu, mỗi tài liệu được biến thành một vector 768 chiều (embedding) bằng model như BERT hoặc E5. Người dùng gõ câu hỏi, bạn cũng embed nó thành vector 768 chiều. Bài toán: tìm tài liệu nào "gần nhất" với câu hỏi trong không gian 768 chiều.

Cách đơn giản nhất — linear scan: tính khoảng cách Euclidean hoặc cosine similarity với từng vector trong 10 triệu tài liệu. Độ phức tạp O(n). Với 10 triệu vector, trên CPU tốt nhất cũng mất vài giây. Với 1 tỷ vector? Quên đi.

Curse of dimensionality (lời nguyền chiều cao): Trong không gian 2D hoặc 3D, khoảng cách giữa các điểm có ý nghĩa rõ ràng. Nhưng trong 768 chiều, mọi khoảng cách đều "tụt lại" gần nhau — chênh lệch giữa khoảng cách max và min có thể chỉ là 1%. B-tree, inverted index, hay bất kỳ cấu trúc dữ liệu truyền thống nào đều trở nên vô dụng vì không thể "cắt" không gian một cách hiệu quả.

RAG (Retrieval-Augmented Generation) đòi hỏi retrieval phải xảy ra trong < 100ms trước khi LLM bắt đầu generate. Linear scan không thể đáp ứng. Chúng ta cần một cách để tìm "gần đúng" (approximate) thay vì "chính xác tuyệt đối" — và đây là nơi Vector Database sinh ra.

Ý tưởng cốt lõi

The "Highway System" Insight.

Thay vì so sánh câu hỏi với từng tài liệu, hãy xây dựng một hệ thống "đường cao tốc" trong không gian vector. HNSW (Hierarchical Navigable Small World) làm điều này bằng cách xây dựng đồ thị phân tầng:

Tầng trên cùng: Mỗi node (vector) chỉ kết nối với vài "người bạn" xa — như đường cao tốc liên bang, cho phép nhảy vượt qua nửa bản đồ chỉ trong một bước.
Các tầng dưới: Dần dần thêm các kết nối "địa phương" — như đường phố trong thành phố.
Tầng đáy: Mỗi node kết nối với hàng xóm gần nhất.

Khi tìm kiếm, bạn bắt đầu từ một node ngẫu nhiên ở tầng cao nhất, "nhảy" theo cạnh dẫn đến node gần target nhất, rồi đào sâu xuống tầng dưới khi không còn cải thiện được nữa. Thay vì so sánh 10 triệu lần, bạn chỉ đi qua ~log(10 triệu) ≈ 24 node. Đây là lý do HNSW đạt độ phức tạp O(log n).

Tại sao không dùng cây (k-d tree)? Trong không gian cao chiều, mọi hyperplane cắt ngang đều chia dữ liệu thành hai phần có mật độ gần như nhau — bạn không thể "cắt bỏ" một nửa không gian như trong 2D/3D. Đồ thị linh hoạt hơn: nó không cố gắng partition không gian, mà chỉ cần đảm bảo tính "navigable" — từ bất kỳ đâu cũng có đường đến đích trong vài bước nhảy.

Product Quantization (PQ) — nén 768 số float32 thành 96 byte: Thay vì lưu trữ vector đầy đủ (3KB), PQ chia vector thành 96 sub-vector nhỏ (mỗi 8 dims), rồi thay thế mỗi sub-vector bằng index của centroid gần nhất trong một codebook nhỏ (256 centroids). Khi tìm kiếm, bạn tính khoảng cách approximate bằng lookup bảng thay vì tính toán đầy đủ, giảm memory bandwidth đi 32 lần với chỉ ~3-5% mất mát recall.

FAISS (Facebook AI Similarity Search) không chỉ là một thuật toán — đó là một "bộ công cụ" cho phép kết hợp: IVF (Inverted File Index — chỉ tìm trong 1-10 cụm gần nhất) + PQ (nén vector) + HNSW (tìm nhanh trong cụm) + GPU acceleration. Đây là lý do bạn có thể tìm kiếm trong 100 triệu vector trên một GPU chỉ trong 76ms với 99% recall.

That's it. Không có ma thuật — chỉ là đánh đổi chính xác tuyệt đối lấy tốc độ thông qua geometry của không gian cao chiều và cấu trúc dữ liệu thông minh.

Tại sao nó hoạt động

Johnson-Lindenstrauss Lemma và tính ngẫu nhiên của chiều cao.

Trong không gian 768 chiều, các vector ngẫu nhiên gần như orthogonal (vuông góc) với nhau. Khoảng cách Euclidean giữa hai vector bất kỳ có xu hướng tập trung quanh một giá trị trung bình với phương sai rất nhỏ. Điều này làm cho việc tìm "chính xác" trở nên kém ý nghĩa — vector thứ 1 gần hơn vector thứ 2 chỉ 0.1% không quan trọng bằng việc tìm được top-10 gần đúng nhanh chóng.

Small World Phenomenon.

HNSW khai thác hiện tượng "six degrees of separation" trong đồ thị ngẫu nhiên. Bằng cách thêm một số ít cạnh "dài" (long-range edges) vào đồ thị kết nối local, bạn tạo ra "navigable small world" — greedy routing (luôn đi đến neighbor gần target nhất) sẽ đến đích trong O(log n) bước. Đây là lý do tại sao một đồ thị đơn giản lại có thể tìm kiếm hiệu quả trong không gian 768 chiều mà không cần biết cấu trúc geometry đầy đủ.

Memory-Compute Tradeoff.

Vector databases hiện đại như Milvus, Weaviate, hay Pinecone tách biệt storage và compute. HNSW graph (cần 2-4x memory so với raw vectors) được giữ trong RAM để fast lookup, trong khi actual vectors được nén bằng PQ hoặc lưu trên SSD (DiskANN). Kết quả: bạn có thể serve 10 tỷ vector trên commodity hardware với độ trễ < 10ms.

Ý nghĩa thực tế

Benchmarks thực tế:

HNSW trên SIFT1M (128D, 1M vectors): ~0.8ms query latency, 99% recall@10, nhanh hơn 60 lần so với linear scan.
FAISS GPU (IVF131k_PQ16 trên 100M vectors): 76ms/query, 99% recall@100 trên Tesla V100.
ANN Benchmarks (chuẩn công nghiệp): Top indices đạt 10,000+ queries/second với recall >= 0.98 trên GloVe-100 (1.2M vectors).

Ai đang dùng:

OpenAI (ChatGPT retrieval), Meta (FAISS gốc cho content moderation), Google (ScaNN cho recommendations), Spotify (Annoy/HNSW cho music similarity), Pinecone/Milvus/Qdrant/Weaviate (production RAG stack).

Limitations quan trọng:

Approximate only: Không phù hợp cho truy vấn audit/compliance yêu cầu 100% precision (ví dụ: "tìm chính xác hợp đồng có điều khoản X").
Memory wall: HNSW in-memory giới hạn ở ~100M vectors/node; vượt qua cần sharding hoặc disk-based approximation.
Insertion pain: Thêm vector mới vào HNSW đòi hỏi graph mutability với locking; nhiều hệ thống yêu cầu rebuild định kỳ thay vì insert real-time.
High-dim breakdown: Performance giảm đáng kể khi >10k dimensions (text embeddings 768-4096 ổn, nhưng raw CNN features pixel-level sẽ struggle).

Đào sâu hơn

Paper gốc:

A Comprehensive Survey on Vector Database (2023) — Tổng quan storage và retrieval techniques.
Survey of Vector Database Management Systems (2023) — So sánh kiến trúc các hệ thống thương mại.

Cùng cụm (RAG & Retrieval):

Dense Retrieval — Hiểu bi-encoder và cách embedding được tạo ra trước khi đưa vào vector DB.
Cross-Encoder & Reranking — Tại sao cần stage 2 để rerank kết quả từ vector DB.
RAG — Pipeline end-to-end từ retrieval đến generation.

Đọc tiếp:

Word Embeddings — Nền tảng về cách text được biến thành vector.
Multi-Agent Systems — Hệ thống agent cần retrieval từ vector DB để truy cập long-term memory.