HNSW: cách tìm hàng xóm gần nhất trong hàng triệu vector

So sánh một vector truy vấn với một triệu vector khác theo cách vét cạn là một triệu phép tính khoảng cách cho mỗi lần tìm. Ở quy mô thật — hàng chục triệu vector, hàng nghìn truy vấn mỗi giây — cách đó không dùng được. HNSW đổi độ chính xác tuyệt đối lấy tốc độ, và tỉ lệ đánh đổi tốt đến mức nó trở thành thuật toán mặc định của gần như mọi cơ sở dữ liệu vector hiện nay.

Ý tưởng: đồ thị nhiều tầng

Cách hình dung dễ nhất mượn từ chuyện đi từ Hà Nội vào Sài Gòn: bạn không đi bộ suốt, mà trước hết bay một quãng dài, tới nơi mới bắt taxi tới gần khu, cuối cùng đi bộ tới đúng cửa nhà. HNSW dựng đúng cấu trúc phân tầng đó:

• Tầng trên cùng rất thưa, mỗi cạnh nhảy một quãng xa trong không gian vector — như chuyến bay.
• Các tầng giữa dày dần, cạnh ngắn dần — như taxi.
• Tầng đáy chứa toàn bộ điểm, các cạnh chỉ nối những điểm thật sự gần nhau — như bước chân cuối.

Tìm kiếm bắt đầu ở tầng trên, đi tham lam về phía điểm gần truy vấn nhất; khi không nhích gần thêm được nữa thì tụt xuống tầng dưới và lặp lại từ chỗ đang đứng. Nhờ mỗi tầng thu hẹp phạm vi đi một bậc, số bước tăng theo hàm lô-ga-rít của số điểm thay vì tuyến tính — đó là toàn bộ phép màu: một triệu điểm chỉ cần khoảng hai chục bước thay vì một triệu.

Hai tham số bạn sẽ phải chỉnh

M — số cạnh mỗi nút giữ lại. Lớn hơn thì đồ thị dày hơn, tìm chính xác hơn, nhưng tốn RAM hơn và dựng chậm hơn. Đây là quyết định lúc dựng chỉ mục, đổi thì phải dựng lại.

efSearch — số ứng viên giữ trong hàng đợi khi tìm. Đây là núm vặn giữa tốc độ và độ chính xác, và điểm quý là chỉnh được lúc chạy mà không cần dựng lại chỉ mục: cần nhanh thì vặn nhỏ, cần chính xác thì vặn to, tuỳ từng truy vấn.

Điều cần biết trước khi chọn

HNSW gần như luôn giữ toàn bộ chỉ mục trong RAM — đây là ràng buộc chi phí lớn nhất ở quy mô lớn, và là thứ hay khiến hoá đơn hạ tầng bất ngờ. Với hàng trăm triệu vector, lượng RAM cần có thể vượt xa dự tính ban đầu, và đó là con số cần tính trước chứ không phải phát hiện sau.

Xoá phần tử cũng khó: phần lớn hiện thực chỉ đánh dấu đã xoá chứ không thật sự gỡ khỏi đồ thị, và cần dựng lại chỉ mục định kỳ để dọn. Với dữ liệu thay đổi liên tục, đây là chi phí vận hành cần lên lịch.

Và quan trọng nhất: kết quả là gần đúng. Với tìm kiếm ngữ nghĩa — tìm tài liệu liên quan, gợi ý sản phẩm — bỏ sót một kết quả hạng tám thì không ai nhận ra, nên đánh đổi này gần như miễn phí. Nhưng với đối chiếu chính xác, nơi bỏ sót một kết quả là sai, thì đừng dùng HNSW; đó là công cụ cho bài toán "đủ gần", không phải bài toán "chính xác tuyệt đối".