Khi bạn đặt một câu hỏi trên ChatGPT và hệ thống tìm tài liệu liên quan trong vài mili-giây, đằng sau đó rất có thể là HNSW, thuật toán tìm kiếm vector gần nhất (approximate nearest neighbor, viết tắt ANN) phổ biến nhất hiện nay. Từ Pinecone, Milvus đến pgvector của PostgreSQL, hầu hết vector database đều dùng HNSW làm chỉ mục mặc định. Vậy nó hoạt động ra sao?

Bài toán gốc: tìm hàng xóm gần nhất

Giả sử bạn có 10 triệu vector embedding (mỗi vector 768 chiều). Khi nhận một query vector, bạn cần tìm 10 vector gần nhất. Quét toàn bộ (brute-force) tốn O(n), quá chậm cho production. Các cấu trúc cây như KD-tree gần như vô dụng ở không gian nhiều chiều. HNSW giải bài toán này bằng cách xây một đồ thị đặc biệt, cho phép tìm kiếm với độ phức tạp O(log n).

Navigable Small World: ý tưởng nền tảng

Ý tưởng xuất phát từ lý thuyết "thế giới nhỏ" (small world): trong một đồ thị mà mỗi nút kết nối với cả hàng xóm gần lẫn vài nút xa, bạn có thể đi từ bất kỳ nút nào đến bất kỳ nút nào khác chỉ qua vài bước nhảy. Navigable Small World (NSW) graph áp dụng nguyên lý này cho vector: mỗi vector là một nút, các cạnh nối nó với M hàng xóm gần nhất cộng thêm vài liên kết tầm xa. Tìm kiếm thực hiện bằng greedy traversal: bắt đầu từ một nút bất kỳ, nhảy sang hàng xóm nào gần query nhất, lặp lại cho đến khi không cải thiện được nữa (local minimum).

Thêm tầng: từ NSW lên HNSW

NSW thuần có nhược điểm: khi dữ liệu lớn, greedy search dễ kẹt ở local minimum vì thiếu liên kết tầm xa. HNSW (do Yury Malkov và đồng nghiệp đề xuất năm 2016) giải quyết bằng cách xếp nhiều tầng NSW chồng lên nhau, tương tự cấu trúc skip list. Tầng trên cùng chỉ chứa rất ít nút với các liên kết dài, cho phép "nhảy xa" nhanh chóng. Mỗi tầng thấp hơn chứa nhiều nút hơn với liên kết ngắn hơn, giúp tinh chỉnh kết quả. Tầng dưới cùng (layer 0) chứa tất cả vector.

Quá trình tìm kiếm bắt đầu từ entry point ở tầng cao nhất. Tại mỗi tầng, thuật toán chạy greedy search cho đến khi tìm local minimum, rồi "rơi xuống" tầng ngay bên dưới tại cùng vị trí đó và tiếp tục. Khi đến tầng 0, kết quả cuối cùng được trả về. Cách phân tầng này đảm bảo các bước nhảy xa xảy ra sớm (khi còn ở tầng thưa), còn tinh chỉnh xảy ra muộn (khi ở tầng dày), cho độ phức tạp O(log n).

Hai tham số quan trọng: M và efConstruction

M là số cạnh tối đa mỗi nút trên mỗi tầng. M lớn hơn cho recall cao hơn nhưng tốn bộ nhớ, M nhỏ thì tiết kiệm nhưng dễ bỏ sót. Giá trị phổ biến là M = 16 hoặc 32. efConstruction kiểm soát chất lượng đồ thị khi xây dựng: con số này quyết định bao nhiêu ứng viên được xét khi chèn một nút mới. efConstruction = 200 cho đồ thị chính xác hơn nhưng xây chậm hơn efConstruction = 100. Khi truy vấn, tham số efSearch tương tự cho phép đánh đổi giữa recall và latency: efSearch = 64 nhanh nhưng recall thấp hơn efSearch = 256.

Khi nào dùng, khi nào không

HNSW phù hợp nhất khi bạn cần tìm kiếm nhanh trên tập dữ liệu vừa và lớn (từ vài trăm nghìn đến hàng trăm triệu vector) với yêu cầu recall trên 95%. Nhược điểm lớn nhất là bộ nhớ: toàn bộ đồ thị phải nằm trong RAM. Với tập dữ liệu tỷ vector, các kỹ thuật như IVF-PQ (product quantization) có thể tiết kiệm bộ nhớ hơn, dù recall thấp hơn. Trong thực tế, nhiều hệ thống kết hợp cả hai: HNSW cho hot data, IVF-PQ cho cold data. Hiểu rõ cách HNSW phân tầng và đánh đổi giữa M, efConstruction, efSearch sẽ giúp bạn tinh chỉnh hệ thống vector search hiệu quả hơn nhiều so với việc chỉ dùng cấu hình mặc định.