6.2 — ANN đồ thị: từ small world tới HNSW (và sau HNSW)

Ba mục liên quan, ba tầng khác nhau. Mục này nói thuật toán hoạt động thế nào. Muốn biết chọn cấu hình nào cho hệ của bạn: B.5 — ANN & hạ tầng vector. Muốn biết tham số thật trong Qdrant và bẫy filter: 7.7, 7.8. Mục này không nói về nén vector — đó là 6.1.

---

1. Bài toán, và bốn lối thoát

Tìm k vector gần nhất trong N vector D chiều, chính xác tuyệt đối, tốn O(N·D). Với 1 triệu chunk × 1536 chiều:

mỗi truy vấn = 1.000.000 × 1536 ≈ 1,5 tỉ phép nhân-cộng
             + đọc 6,1 GB từ RAM

SIMD và nhiều luồng làm việc này khả thi (Qdrant có exact: true), nhưng không phải ở mức vài chục ms cho hàng trăm QPS. Nên ta chấp nhận gần đúng — ANN.

Có đúng bốn họ ý tưởng, và tất cả đều làm cùng một việc: giảm số ứng viên phải chấm điểm.

Họ	Cơ chế	Ví dụ	Điểm yếu quyết định
Hash	Băm sao cho vector gần nhau rơi cùng bucket	LSH: SimHash, MinHash, E2LSH (§1.4)	Data-oblivious — không học gì từ dữ liệu; cần rất nhiều bảng mới đủ recall, RAM có thể vượt cả đồ thị
Cây	Chia không gian bằng siêu phẳng / vòng tròn	KD-tree, FLANN, Annoy (§1.5)	KD-tree sập ở ~10–30 chiều; bản dùng được ở chiều cao phải dựng rừng, và index bất biến sau khi build
Phân cụm	k-means thành nlist cụm, chỉ quét nprobe cụm gần nhất	IVF, IVF-PQ, ScaNN, SPANN (§1.1)	Phải train trước khi dựng; ứng viên sát biên cụm bị bỏ; centroid lệch dần khi dữ liệu đổi
Đồ thị	Đi bộ trên đồ thị lân cận theo hướng giảm khoảng cách	NSW, HNSW, Vamana	Ngốn RAM; xoá/cập nhật khó; nhạy với filter

Hai trục độc lập — đừng lẫn. Bốn họ trên giảm số lần tính khoảng cách. Quantization (6.1) giảm giá của mỗi lần tính. Hệ production thật gần như luôn dùng cả hai: HNSW + scalar/TurboQuant.

Từ khoảng 2018 trở đi, họ đồ thị thắng gần như toàn bộ benchmark ở dải recall cao — và HNSW là bản cài đặt phổ biến nhất của nó. Nhưng “thắng benchmark” không phải “thắng mọi tình huống”, và đối thủ gần nhất của nó — IVF — thua ở đúng một trục (recall/latency khi mọi thứ vừa RAM) mà thắng ở bốn trục khác. Ba tiểu mục sau bóc IVF ra đủ sâu để so sánh cho đàng hoàng; §1.4–1.5 làm cùng chuyện đó cho hai họ còn lại — ít dùng hơn trong RAG hôm nay, nhưng mỗi họ vẫn giữ một chỗ mà không họ nào thay được; §1.6 gom cả bốn vào một bảng. Từ mục 2 trở đi mới quay về đồ thị.

1.1 IVF — bên trong

IVF hai tầng — truy vấn, chi phí, và bẫy biên cụmMở toàn màn hình

IVF là inverted index của 3.2/3.3 đem sang không gian vector: chỗ nào inverted index dùng term làm khoá, IVF dùng centroid làm khoá; postings list đổi tên thành inverted list. Toàn bộ thuật toán là ba bước.

Bước dựng (cần train trước):

1. train:  k-means trên (một mẫu của) dữ liệu → nlist centroid c₁…c_nlist
           ← đây là "coarse quantizer"
2. assign: mỗi vector x → cụm có centroid gần nhất
           inverted_list[i] = [id của mọi x thuộc cụm i]

Bước 1 là một thuật toán riêng, đủ nhiều chi tiết để có mục riêng ở cuối tiểu mục này: k-means — cái máy sinh ra centroid.

Bước truy vấn — hai tầng:

tầng 1:  tính d(q, cᵢ) cho TẤT CẢ nlist centroid → chọn nprobe cụm gần nhất
tầng 2:  quét ĐẦY ĐỦ (brute force) mọi vector trong nprobe cụm đó → top-k

Không có greedy, không có đồ thị, không có tầng ngẫu nhiên. Đây là lý do IVF dễ hiểu, dễ cài, dễ debug hơn HNSW rất nhiều — và cũng là lý do nó có những tính chất mà HNSW không có (mục 1.3).

Tính bằng tay — và một quy tắc tự rơi ra. N = 1.000.000, D = 1536, nlist = 4.000, nprobe = 16:

tầng 1:  4.000 centroid          × 1536 ≈    6,1 triệu phép nhân-cộng
tầng 2:  16 cụm × (1M/4.000=250) × 1536 ≈    6,1 triệu
                                  tổng ≈   12,3 triệu
brute force                            ≈ 1.536   triệu
                                  →  ít hơn ~125×

Để ý hai tầng có chi phí bằng nhau. Đó không phải trùng hợp — tổng chi phí là nlist + nprobe·N/nlist, cực tiểu tại:

$$\mathrm{nlist} = \sqrt{\mathrm{nprobe} \times N}$$

nprobe	N	nlist cực tiểu
16	1M	4.000 = $4\sqrt{N}$
256	1M	16.000 = $16\sqrt{N}$

Và đây đúng là khoảng mà Faiss khuyến nghị: nlist từ 4√N đến 16√N. Quy tắc ngón tay ấy không phải kinh nghiệm dân gian — nó là điểm cân bằng giữa hai tầng, ứng với nprobe bạn dự định dùng.

Ba tham số:

Tham số	Lúc nào	Khoảng	Đổi gì
nlist	train, bất biến	4√N – 16√N	kích thước mỗi cụm; đặt sai thì một trong hai tầng thành cổ chai
nprobe	runtime	1 – nlist	núm recall/latency — vai trò y hệt ef của HNSW
kích thước tập train	train	30×nlist – 256×nlist vector	chất lượng centroid

Dòng cuối là chỗ IVF khác HNSW về bản chất vận hành: nlist = 4.000 đòi 120.000 – 1.024.000 vector để train. Nghĩa là IVF không dựng được từ một index rỗng — bạn phải có dữ liệu trước. HNSW thì chèn từ điểm đầu tiên cũng chạy. Với hệ RAG mà corpus lớn dần theo thời gian, đây là khác biệt thật, không phải chi tiết kỹ thuật.

Đọc thêm

• [EN] Faiss wiki — Guidelines to choose an index — nguồn của mục 1.1 và 1.3: khoảng nlist 4√N–16√N, tập train 30×K–256×K, công thức RAM HNSW d×4 + M×2×4, và câu “HNSW does not support removing vectors from the index”
• [EN] Douze et al. — The Faiss library (arXiv 2401.08281) — bản mô tả có hệ thống của cả họ IVF: coarse quantizer, nprobe, và cách các thành phần lắp vào nhau
• [EN] Nearest Neighbor Indexes for Similarity Search — Pinecone Learn — IVF-Flat / IVF-PQ / HNSW trên cùng một dataset với code Faiss; tốt để lấy trực giác về nprobe trước khi vào paper
• [VI] Cách triển khai Vector Database thực tế bằng FAISS — ducxinh.com — nguồn tiếng Việt gần nhất tìm được có chạm tới IndexIVFFlat và index.train(...) trong code thật. Lưu ý: nó chỉ đặt nlist = 100 mà không giải thích nprobe hay bước train — phần cơ chế phải đọc nguồn EN ở trên.

k-means — cái máy sinh ra centroid

Bước train ở trên là một thuật toán riêng, và nó quyết định chất lượng của mọi thứ phía sau: centroid tồi thì cụm tồi, cụm tồi thì nprobe bao nhiêu cũng không cứu được. Đây là chỗ duy nhất trong IVF có học, nên đáng bóc riêng.

Nó tối thiểu hoá cái gì. k-means không đi tìm “cụm đúng”. Nó tìm K điểm c₁…c_K sao cho tổng bình phương khoảng cách từ mỗi điểm tới centroid gần nhất là nhỏ nhất — đại lượng đó gọi là distortion (scikit-learn gọi là inertia_):

$$J(c_1, \dots, c_K) = \sum_i \min_j \bigl\lVert x_i - c_j \bigr\rVert^{2}$$

Công thức này không phải giống mục tiêu của quantization ở 6.1 — nó chính là mục tiêu đó. Bài báo khai sinh thuật toán, Lloyd — Least squares quantization in PCM (1982) — viết về nén tín hiệu chứ không về phân cụm; “centroid” ở đó là mức lượng tử. Vì vậy gọi centroid của IVF là coarse quantizer là đúng theo nghĩa chữ, không phải ẩn dụ. PQ ở 6.1 chạy đúng thuật toán này, chỉ khác: trên từng đoạn chiều, với K = 256.

Thuật toán Lloyd — hai bước, lặp.

khởi tạo: chọn K centroid ban đầu
lặp niter vòng (hoặc tới khi nhãn không đổi):
  1. assign:  mỗi x  →  cụm j có ‖x − c_j‖ nhỏ nhất          ← O(N·K·d)  ← đắt
  2. update:  c_j    ←  trung bình cộng của mọi x trong cụm j  ← O(N·d)

Mỗi bước đều không làm tăng J. Bước 1 giữ nguyên centroid, chỉ đổi nhãn sang chỗ tốt hơn. Bước 2 giữ nguyên nhãn, và trung bình cộng đúng là điểm làm nhỏ nhất tổng bình phương khoảng cách tới một tập điểm (lấy đạo hàm theo c_j, cho bằng 0). Vì J ≥ 0 và số cách chia N điểm thành K cụm là hữu hạn, thuật toán chắc chắn dừng.

“Chắc chắn dừng” không phải “tìm được đáp án tốt nhất”. Bài toán k-means là NP-hard (Aloise et al., 2009 — kể cả với d = 2), và Lloyd chỉ là leo đồi: nó dừng ở một cực tiểu địa phương, và cực tiểu nào thì phụ thuộc hoàn toàn vào khởi tạo. Đó là lý do tồn tại tham số nredo.

Tính bằng tay — vì sao tập train phải bị chặn. Vẫn N = 1.000.000, d = 1536, nlist = 4.000. Faiss chặn tập train ở max_points_per_centroid = 256:

tập train:                 256 × 4.000                   = 1.024.000 vector
1 vòng, bước assign:  1.024.000 × 4.000 × 1.536  ≈  6,3 × 10¹²  phép nhân-cộng
niter = 25 vòng:                                 ≈  1,6 × 10¹⁴

Đặt cạnh hai mốc đã tính ở trên: một truy vấn IVF ≈ 12,3 triệu phép, một lần quét brute force cả corpus ≈ 1,5 tỷ phép. Nghĩa là train một lần ≈ 13 triệu truy vấn ≈ 100.000 lần quét toàn corpus. Đây là số dẫn ra từ công thức, không phải số đo trên máy — nhưng nó đủ để thấy hai chuyện: (a) vì sao Faiss lấy mẫu bớt tập train thay vì dùng hết, và (b) vì sao bước assign được cài bằng một phép nhân ma trận (N_train × d) · (d × K) để đẩy sang BLAS/GPU, chứ không phải hai vòng for lồng nhau.

Bảy mặc định thật của Faiss (đọc từ faiss/Clustering.h, không phải từ blog):

Tham số	Mặc định	Nghĩa
niter	25	số vòng Lloyd. So với max_iter=300 của scikit-learn: Faiss không cần hội tụ, chỉ cần một quantizer đủ tốt
nredo	1	chạy lại toàn bộ k-means mấy lần, giữ bộ centroid có J nhỏ nhất
init_method	RANDOM	ba lựa chọn: RANDOM, KMEANS_PLUS_PLUS, AFK_MC2
min_points_per_centroid	39	dưới mức này → cảnh báo; dưới 1 điểm/centroid → ném exception
max_points_per_centroid	256	trên mức này → lấy mẫu bớt tập train
spherical	false	có L2-normalise centroid sau mỗi vòng hay không
seed	1234	cố định → train hai lần trên cùng dữ liệu ra cùng centroid

Hai dòng giữa là nguồn gốc thật của khoảng 30×nlist – 256×nlist trong bảng tham số ở trên: 256 là trần lấy mẫu, và 39 là sàn cảnh báo. Cảnh báo bạn sẽ thấy trong log có dạng WARNING clustering 618 points to 500 centroids: please provide at least 19500 training points — và 19500 = 500 × 39. Quy tắc ngón tay ấy là hai hằng số trong code, không phải kinh nghiệm dân gian.

Khởi tạo: chỗ scikit-learn và Faiss chọn khác nhau.

• RANDOM — lấy K điểm ngẫu nhiên. Rẻ, O(K), nhưng dễ rơi vào cực tiểu tồi: hai centroid khởi tạo cạnh nhau trong cùng một vùng dày thì suốt các vòng sau chúng vẫn chia nhau vùng đó, còn một vùng khác không có centroid nào.
• KMEANS_PLUS_PLUS (Arthur & Vassilvitskii, SODA 2007) — D² seeding: c₁ lấy đều; mỗi centroid sau được chọn với xác suất tỉ lệ với D(x)², trong đó D(x) là khoảng cách từ x tới centroid gần nhất đã chọn. Điểm ở xa mọi centroid hiện có → xác suất cao. Đảm bảo lý thuyết: J kỳ vọng chỉ cách tối ưu O(log K) lần. Giá phải trả: O(N·K·d) — đắt bằng đúng một vòng Lloyd — và bản chất tuần tự (K lượt quét dữ liệu).
• AFK_MC2 (Bachem et al., NeurIPS 2016) — xấp xỉ D² seeding bằng MCMC để tránh K lượt quét, giữ được đảm bảo lý thuyết mà không cần giả định gì về phân bố dữ liệu.

Đáng chú ý: scikit-learn mặc định init='k-means++' với n_init='auto' = 1 lần chạy; Faiss mặc định RANDOM với nredo = 1. Faiss chọn thế vì bối cảnh khác: K cỡ hàng nghìn, tập train hàng triệu, và nó không cần cụm “đúng” — chỉ cần cụm đủ chặt (xem đoạn cuối). Nếu recall của IVF thấp bất thường mà nprobe tăng không cứu được, hai núm đáng thử đầu tiên chính là init_method = KMEANS_PLUS_PLUS và nredo = 3–5.

spherical: cái bẫy khi embedding dùng cosine. Gần như mọi embedding trong RAG được normalise và so bằng cosine / inner product. Nhưng trung bình cộng của các vector đơn vị không có chuẩn 1: cụm nào phân tán rộng thì ‖c_j‖ càng nhỏ. Nếu metric là inner product mà centroid không normalise, tầng 1 chấm điểm ⟨q, c_j⟩ sẽ thiên vị cụm chặt và dìm cụm rộng — một lỗi lệch hệ thống, không phải nhiễu. spherical = true L2-normalise centroid sau mỗi vòng; mục tiêu đổi từ “nhỏ nhất tổng bình phương khoảng cách” thành “lớn nhất tổng cosine”. Dùng cosine thì bật nó.

k-means không hứa cụm bằng nhau — và IVF phải trả giá. Mục tiêu là distortion, không có một chữ nào về kích thước cụm. Kết quả: vùng dày dữ liệu bị chia thành nhiều cụm nhỏ, vùng thưa gom thành cụm rất to. Với IVF, chi phí tầng 2 là tổng độ dài của nprobe list đó, nên con số N/nlist = 250 ở phần tính tay là trung bình, không phải điều mọi truy vấn gặp: p99 latency do những cụm to nhất quyết định. Đây chính là lý do SPANN không dùng k-means thuần (xem “Bẫy cố hữu” ngay dưới).

Centroid lệch dần (drift). Centroid học từ một snapshot dữ liệu tại thời điểm train. Corpus đổi — thêm domain mới, đổi model embedding, dữ liệu theo mùa — thì phân bố đổi, và centroid không còn đại diện. Recall tụt âm thầm: không exception, không log, chỉ là ứng viên đúng ngày càng rơi ra ngoài nprobe cụm được probe. Không có cách “sửa dần” từng centroid; phải train lại và index lại, tức là dùng đúng quy trình alias ở 3.12. HNSW không có lớp lỗi này vì nó không học gì từ phân bố (§1.3).

Khi K quá lớn, tầng 1 tự nó thành cổ chai — và họ đồ thị vào cứu. Với N cỡ tỷ, Faiss khuyến nghị nlist = 1.048.576. Lúc đó:

tầng 1:  1.048.576 centroid × 1.536  ≈  1,6 tỷ phép nhân-cộng

— tức là đắt bằng quét brute force cả một corpus 1 triệu vector. Công thức nlist = √(nprobe × N) ở trên giả định tầng 1 là quét thẳng toàn bộ centroid; ở quy mô này giả định đó vỡ. Faiss chữa bằng cách dựng HNSW trên chính bảng centroid — tên index là IVF1048576_HNSW32. Nghĩa là họ đồ thị đi làm coarse quantizer cho họ phân cụm, ở cả lúc train (assign cho từng vector) và lúc truy vấn. Và điều đó gỡ luôn trần 16√N: một khi tầng 1 không còn tuyến tính theo nlist, nlist được phép lớn hơn nhiều.

Con đường còn lại là mini-batch k-means (Sculley, WWW 2010): mỗi vòng chỉ lấy một lô nhỏ ngẫu nhiên và cập nhật centroid bằng trung bình chạy — nhanh hơn nhiều bậc, distortion tệ hơn một chút. Faiss không đi đường này: nó lấy mẫu bớt tập train một lần (max_points_per_centroid) rồi chạy Lloyd đầy đủ.

Cuối cùng: đừng chọn K bằng elbow. Mọi tài liệu ML dạy chọn K bằng elbow hoặc silhouette, vì ở đó mục tiêu là tìm số cụm thật của dữ liệu. Với IVF thì không. K = nlist được chọn từ cân bằng chi phí hai tầng — √(nprobe × N) ở phần tính tay — chứ không từ cấu trúc dữ liệu. IVF không cần cụm “đúng”; nó chỉ cần đúng một điều: láng giềng thật của q nằm trong một trong nprobe cụm được probe. Distortion thấp là proxy cho điều đó (cụm chặt hơn → láng giềng ít bị biên cắt hơn), không phải chính điều đó. Thước đo cuối cùng vẫn là recall@k trên golden set — mục 11.

Bẫy cố hữu: biên cụm. Query nằm sát ranh giới hai cụm thì láng giềng thật của nó có thể nằm trong cụm không được probe — và không có cách nào biết. Ba cách chữa, theo thứ tự tăng dần độ tinh vi:

1. Tăng nprobe — thô, tuyến tính, hiệu quả tới một mức.
2. Spilling / gán trùng lặp: cho mỗi vector nằm trong nhiều cụm. Google làm chuyện này trong ScaNN với SOAR (Spilling with Orthogonality-Amplified Residuals, NeurIPS 2023): cụm phụ hoạt động như “cụm dự phòng” khi cụm chính chấm điểm kém, đổi lấy index to hơn một chút.
3. Phân cụm cân bằng thay cho k-means thuần. k-means cho cụm lệch kích thước rất mạnh → latency dao động theo cụm mà query rơi vào. SPANN (NeurIPS 2021) dùng hierarchical balanced clustering + mở rộng inverted list bằng closure của cụm.

Đọc thêm

• [VI] Bài 4: K-means Clustering — machinelearningcoban.com — nguồn tiếng Việt tốt nhất cho phần Lloyd ở §1.1: hàm distortion, hai bước lặp, lập luận hội tụ, và các giới hạn (cụm phải “tròn”, phải cân kích thước) kèm code NumPy. Lưu ý: không có k-means++, mini-batch hay elbow — ba thứ đó phải đọc nguồn EN dưới đây.
• [VI] Các bước của thuật toán k-Means Clustering — Deep AI KhanhBlog — đọc kèm bài trên: có phần lấy đạo hàm chứng minh vì sao centroid tối ưu đúng là trung bình cộng, và có elbow method kèm code. Cũng không nhắc k-means++.
• [EN] faiss/Clustering.h + faiss/impl/ClusteringInitialization.h — nguồn của bảng bảy mặc định ở §1.1: niter = 25, nredo = 1, min_points_per_centroid = 39, max_points_per_centroid = 256, seed = 1234, và ba ClusteringInitMethod. Cần con số chính xác thì đọc code, đừng đọc blog
• [EN] Faiss wiki — Faiss building blocks: clustering, PCA, quantization — API faiss.Kmeans thật: nredo, tuỳ chọn spherical (L2-normalise centroid sau mỗi vòng — bẫy cosine ở §1.1), và gpu=True
• [EN] Arthur & Vassilvitskii — k-means++: The Advantages of Careful Seeding, SODA 2007 (PDF) — mục 1–2 là đủ: D² seeding và chứng minh cận O(log K)
• [EN] Bachem, Lucic, Hassani & Krause — Fast and Provably Good Seedings for k-Means, NeurIPS 2016 (PDF) — AFK-MC²: vì sao k-means++ không scale (tuần tự, K lượt quét dữ liệu) và cách MCMC thay nó
• [EN] Aloise, Deshpande, Hansen & Popat — NP-hardness of Euclidean sum-of-squares clustering, Machine Learning 75 (2009) — bốn trang chứng minh k-means là NP-hard kể cả khi d = 2; đây là lý do Lloyd chỉ cho cực tiểu địa phương và vì sao nredo tồn tại
• [EN] scikit-learn — Clustering: K-means và MiniBatchKMeans — để đối chiếu mặc định với Faiss (init='k-means++', n_init='auto' → 1 lần chạy, max_iter=300, algorithm='lloyd'), và phần mini-batch của Sculley (WWW 2010; bản ghi dblp — ACM và trang tác giả đều chặn curl)
• [EN] Lloyd — Least squares quantization in PCM, IEEE Trans. Inform. Theory 28(2):129–137 (1982) — bài gốc của thuật toán, viết về nén tín hiệu: lý do “centroid” và “mức lượng tử” là cùng một thứ, và vì sao gọi centroid của IVF là coarse quantizer là đúng nghĩa chữ. Có phí; IEEE trả 202 với curl nhưng mở được trên browser — phần cơ chế đã có đủ ở hai nguồn VI trên.
• [EN] SOAR: New algorithms for even faster vector search with ScaNN — Google Research — mục 1.1: gán trùng lặp (“cụm dự phòng”) chữa bẫy biên cụm như thế nào
• [EN] Chen et al. — SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (arXiv 2111.08566) — mục 1.1 và 1.3: centroid ở RAM, inverted list ở disk; phân cụm cân bằng thay k-means thuần

1.2 IVF-PQ (IVFADC) — vì sao nén residual chứ không nén vector

IVF-Flat giữ vector nguyên trong inverted list: nhanh, chính xác, nhưng không tiết kiệm RAM (vẫn N × D × 4 byte). Muốn tiết kiệm thì ghép IVF với PQ (6.1) — và cách ghép có một chi tiết đáng học:

x  →  cụm i  →  lưu PQ(x − cᵢ)         ← nén RESIDUAL, không nén x

Vì sao: x − cᵢ có phương sai nhỏ hơn nhiều so với x (mọi điểm trong cụm đã gần cᵢ). Cùng một số bit, codebook PQ mô tả residual chính xác hơn hẳn mô tả vector gốc. Nói cách khác: coarse quantizer đã “gánh” phần thô của tín hiệu, PQ chỉ còn phải mã hoá phần tinh.

Chữ ADC trong tên IVFADC (Inverted File with Asymmetric Distance Computation) là chi tiết thứ hai: khi chấm điểm, query giữ nguyên full precision, chỉ vector trong index là bản nén. Đối xứng (nén cả query) thì rẻ hơn chút nhưng đo được là kém chính xác hơn. Đây cũng chính là mặc định bất đối xứng của TurboQuant trong Qdrant (B.5) — cùng một lý do.

Đọc thêm

• [EN] Jégou, Douze & Schmid — Searching with quantization (bản mô tả IVFADC) — nguồn của mục 1.2: vì sao nén residual x − cᵢ chứ không nén x, và vì sao ADC chính xác hơn SDC

1.3 IVF vs HNSW — bảng so, và chỗ hai họ gặp nhau

	IVF	HNSW
Cơ chế	phân vùng + quét tuyến tính trong vùng	đi bộ greedy trên đồ thị
Cần train?	có — k-means, 30–256 × nlist vector	không
Dựng từ index rỗng?	không	có
Chi phí truy vấn	nlist + nprobe·N/nlist — √N	log N
Núm runtime	nprobe	ef
RAM thêm ngoài vector	nlist × D × 4 (centroid) + id — nhỏ	M × 2 × 4 byte/vector (công thức Faiss: d×4 + M×2×4) — lớn
Index thực tế (pgvector, cùng dữ liệu)	cơ sở	to hơn ~2–5×, build chậm hơn
Xoá 1 vector	xoá khỏi inverted list — rẻ	tombstone; Faiss ghi thẳng: HNSW không hỗ trợ xoá
Thêm vector mới	rẻ (assign vào cụm)	rẻ, nhưng làm xấu đường đi của điểm cũ
Dữ liệu drift	centroid lệch dần → phải train lại	không có centroid nên không có vấn đề này
Đưa xuống disk	thuận — inverted list là khối liên tục, đọc tuần tự	khó — mỗi hop là một lần đọc ngẫu nhiên
Recall cao (>0,95)	phải tăng nprobe mạnh → chi phí tuyến tính	thắng rõ, chi phí logarit

Bốn kết luận đọc ra được từ bảng:

1. √N vs log N là toàn bộ câu chuyện về tốc độ. Ở 100k vector, khác biệt nhỏ. Ở 100 triệu, nprobe phải tăng theo để giữ recall và IVF tụt lại. Đây là lý do HNSW là mặc định đúng cho phần lớn hệ RAG.
2. IVF thắng ở vòng đời dữ liệu. Xoá rẻ, đưa xuống disk thuận, index nhỏ, build nhanh. Đúng những chỗ HNSW đau nhất (mục 9.1).
3. IVF thắng khi có filter chọn lọc mạnh. Vì tầng 2 là quét tuyến tính, áp thêm điều kiện filter không phá cấu trúc gì cả — thậm chí có thể gắn nhãn cho centroid để bỏ hẳn những cụm không chứa vector nào thoả filter. Đồ thị thì ngược lại: filter càng chọn lọc, đồ thị con của các điểm thoả filter càng rời rạc và greedy càng vô nghĩa. Nghiên cứu thực nghiệm về filtered ANN cho một ngưỡng thô đáng nhớ: **dưới ~1% độ chọn lọc, pre-filter
   • brute force thường thắng cả đồ thị.** So thêm ở 7.8.
4. Hai họ không loại trừ nhau. Tầng 1 của IVF là “tìm nprobe centroid gần nhất trong nlist centroid” — bản thân nó là một bài toán kNN. Với nlist lớn, Faiss khuyên dùng HNSW làm coarse quantizer (IVF65536_HNSW32 cho dải 1M–10M vector). SPANN cũng cùng ý tưởng: centroid nằm RAM, inverted list nằm disk. Câu hỏi thật vì thế không phải “IVF hay HNSW” mà là “cấu trúc nào ở tầng nào”.

Nếu chỉ nhớ một dòng: HNSW là mặc định đúng khi index vừa RAM và bạn cần recall cao. Chuyển sang IVF/IVF-PQ khi ràng buộc đổi từ latency sang dung lượng, chi phí build, tần suất xoá, hoặc filter chọn lọc mạnh — chứ không phải vì nó “chậm hơn một chút”.

Đọc thêm

• [EN] Faiss wiki — Faiss indexes — tên đầy đủ của từng biến thể (IVF…,Flat / ,PQ / IVF…_HNSW32) để đối chiếu khi đọc code
• [EN] Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study (arXiv 2508.16263) — mục 1.3 kết luận 3: nguồn của ngưỡng ~1% độ chọn lọc, và vì sao đồ thị con thoả filter bị rời rạc
• [EN] HNSW vs IVFFlat: How to Choose the Right Vector Index — BigData Boutique — góc vận hành pgvector: nguồn của con số index HNSW to hơn IVFFlat ~2–5× và build chậm hơn

1.4 LSH — đúng về lý thuyết, thua trên thực tế (nhưng vẫn sống)

Hash thường tối thiểu hoá collision. LSH làm ngược lại: một họ hàm băm là locality-sensitive nếu P(h(x) = h(y)) là hàm giảm theo d(x, y) — tức nó cố ý cho các điểm gần nhau đụng nhau. Bucket vì thế trở thành “vùng lân cận” mà bạn tra được trong O(1).

Bản cụ thể dễ hình dung nhất — siêu phẳng ngẫu nhiên (SimHash, Charikar 2002):

$$\begin{aligned} r &\sim \mathcal{N}(0, I) && \text{một siêu phẳng ngẫu nhiên qua gốc} \\[2pt] h_r(x) &= \mathrm{sign}(r \cdot x) && \text{1 bit: } x \text{ nằm phía nào của siêu phẳng} \\[2pt] P\bigl(h_r(x) = h_r(y)\bigr) &= 1 - \frac{\theta}{\pi} && \theta = \text{góc giữa } x \text{ và } y \end{aligned}$$

Nhìn kỹ đẳng thức đó: nó chính là công thức đã dùng ở 6.1 để giải thích binary quantization. Nói cách khác — binary quantization là LSH siêu phẳng ngẫu nhiên dùng đúng một bảng và không amplification. Hai mục tưởng rời nhau, thực ra là một cơ chế ở hai chế độ.

Amplification: một bit thì vô dụng, phải ghép hai tầng AND rồi OR.

$$\begin{aligned} \text{AND (trong một bảng):}\quad & g(x) = \bigl(h_1(x), \dots, h_k(x)\bigr) && \Rightarrow\; P(\text{cùng bucket}) = p^{k} \\[2pt] \text{OR (giữa các bảng):}\quad & L \text{ bảng độc lập} && \Rightarrow\; P(\text{gặp} \ge 1 \text{ bảng}) = 1 - (1 - p^{k})^{L} \end{aligned}$$

k cắt false positive (nhưng cắt cả recall), L mua recall trở lại. Toàn bộ nghệ thuật của LSH nằm ở việc chọn cặp (k, L).

Tính bằng tay. Hai vector “gần” cách nhau θ = 30° → p = 1 − 30/180 = 0,8333. Hai vector “xa” θ = 90° → p = 0,5.

	cặp gần (θ=30°)	cặp xa (θ=90°)
k=16, L=1	0,8333¹⁶ = 0,054 → 5,4% (thảm hoạ)	0,5¹⁶ = 0,0015%
k=16, L=50	1 − (1 − 0,054)⁵⁰ = 93,8%	≈ 0,076%

Đẹp: recall 93,8% cho cặp gần, false positive 0,076% cho cặp xa. Nhưng đếm cái giá: L = 50 bảng nghĩa là mỗi vector được lưu 50 lần (50 khoá 16 bit + 50 con trỏ id).

50 × (2 byte khoá + 8 byte id) = 500 byte/vector
   so với HNSW M=32            = 320 byte/vector

LSH tốn RAM hơn cả đồ thị HNSW — và đó là điểm yếu quyết định, không phải chuyện tốc độ. Độ phức tạp truy vấn của LSH là n^ρ với ρ = ln(1/p₁)/ln(1/p₂): dưới tuyến tính nhưng là đa thức, không phải log n.

Vì sao nó thua — một chữ: data-oblivious. Hàm băm của LSH rút ngẫu nhiên, không nhìn dữ liệu một lần nào. IVF học centroid bằng k-means; đồ thị học từ chính các đường đi. Lý thuyết cũng đứng về phía data-dependent: Andoni & Razenshteyn (2015) chứng minh hashing phụ thuộc dữ liệu đạt ρ = 1/(2c² − 1) cho không gian Euclid — với c lớn là cải thiện bậc hai về thời gian truy vấn so với mọi thuật toán LSH data-oblivious tốt nhất có thể — và biên đó là tối ưu. Các phân vùng thu được “thích ứng với hình học của tập dữ liệu cụ thể”, đúng thứ LSH cổ điển từ chối làm.

Nhưng LSH vẫn sống, và bạn sẽ dùng nó — chỉ là không để làm ANN.

• Chống trùng lặp (dedup) là chỗ LSH không có đối thủ. Bài toán ở đây là tập hợp — Jaccard trên shingle n-gram — không phải vector dense, và MinHash + banding giải nó ở quy mô hàng chục tỉ document, thứ mà đồ thị hay IVF không với tới. Recipe điển hình trong pipeline dedup corpus LLM: shingle n-gram → 128 permutation → ngưỡng Jaccard 0,8 → banding. Milvus 2.6 đã đưa MinHash LSH vào thẳng lớp index.
• Áp vào repo này: dedup chunk trước khi index. Chunk trùng làm hỏng cả hai phía — idf của BM25 bị bóp méo (3.4b) và top-k vector bị vài bản sao của cùng một đoạn chiếm chỗ.
• Streaming / sketching: không cần train, không cần giữ toàn bộ dữ liệu, ghép được (mergeable). Không họ nào khác có tính chất này.
• Phân tán dễ nhất trong bốn họ: bucket là một khoá → shard theo khoá, không cần đồ thị toàn cục hay centroid toàn cục.

MinHash hay SimHash? MinHash cho Jaccard trên tập hợp (document, shingle, token); SimHash cho cosine trên vector dense. Dùng lẫn là sai bài toán, không phải sai tham số.

Đọc thêm

• [VI] MinHash — Phạm Duy Tùng ML Blog — nguồn tiếng Việt cho ý tưởng MinHash ở mục 1.4: signature từ min của nhiều hàm băm ngẫu nhiên. Lưu ý: bài dừng ở mức khái niệm — không có phần banding (k, L) hay siêu phẳng ngẫu nhiên, hai thứ đó phải đọc MMDS ch.3 bên dưới.
• [EN] Leskovec, Rajaraman & Ullman — Mining of Massive Datasets, ch.3 (Finding Similar Items) — nguồn chuẩn của mục 1.4: shingling → minhashing → banding; §3.4.2 là chỗ có đúng công thức 1 − (1 − p^k)^L và đường cong chữ S
• [EN] Locality Sensitive Hashing: The Illustrated Guide — Pinecone Learn và Random Projection for LSH — hai bài có hình cho AND/OR và siêu phẳng ngẫu nhiên, đọc trước khi vào MMDS
• [EN] Charikar — Similarity Estimation Techniques from Rounding Algorithms, STOC 2002 — nguồn của P(h(x)=h(y)) = 1 − θ/π; cùng một đẳng thức mà 6.1 dùng cho binary quantization
• [EN] Andoni & Razenshteyn — Optimal Data-Dependent Hashing for Approximate Near Neighbors (arXiv 1501.01062) — nguồn của lập luận data-oblivious vs data-dependent ở mục 1.4: ρ = 1/(2c² − 1) và vì sao phân vùng “thích ứng với hình học của dữ liệu” thắng
• [EN] Andoni et al. — Practical and Optimal LSH for Angular Distance (arXiv 1509.02897) — bản LSH tốt nhất thực dụng cho cosine (cross-polytope, thư viện FALCONN); đọc nếu bạn thật sự cần LSH thay vì đồ thị
• [EN] Shrivastava & Li — In Defense of MinHash Over SimHash (arXiv 1407.4416) — vì sao chọn MinHash hay SimHash là chọn theo bài toán (Jaccard vs cosine), không phải theo sở thích
• [EN] Data Deduplication at Trillion Scale — Zilliz — mục 1.4: recipe MinHash-LSH thật (shingle, 128 permutation, ngưỡng Jaccard 0,8) và việc Milvus 2.6 đưa nó vào lớp index

1.5 Họ cây: từ KD-tree tới Annoy

KD-tree chia không gian bằng siêu phẳng vuông góc trục, luân phiên từng chiều. Tìm kiếm chính xác đòi backtracking: nếu bán kính kết quả hiện tại còn cắt qua siêu phẳng của node cha thì buộc phải xét cả nhánh bên kia. Ở chiều cao, gần như mọi nhánh đều bị cắt → duyệt gần hết cây. Ngưỡng thực nghiệm: cây thoái hoá thành quét tuyến tính ở khoảng 10–30 chiều, tuỳ phân bố; từ D > 20 trở lên coi như hết tác dụng. Embedding 384–1536 chiều thì KD-tree thuần không có ý nghĩa gì.

Họ cây sống sót ở chiều cao bằng cách đổi đúng hai thứ:

1. Siêu phẳng ngẫu nhiên thay cho vuông góc trục.
2. Rừng thay cho một cây, duyệt bằng một priority queue chung.

FLANN đi đường đó với randomized KD-forest: chia tại mean, và chiều chia chọn ngẫu nhiên trong top-5 chiều có phương sai lớn nhất — tức đã data-dependent một phần, khác LSH.

Annoy (Approximate Nearest Neighbors Oh Yeah, Spotify) là bản gọn nhất của ý tưởng này:

xây một cây:  lấy 2 điểm ngẫu nhiên trong tập con
              → siêu phẳng cách đều hai điểm đó   ← điểm chia lấy TỪ dữ liệu
              → chia đôi, đệ quy tới khi lá còn ≤ K điểm
xây rừng:     n_trees cây độc lập
truy vấn:     đi xuống mọi cây bằng một priority queue chung,
              thu tới search_k node → hợp ứng viên → chấm điểm thật → top-k

Đúng mô hình hai núm như ba họ kia: n_trees (build — lớn hơn thì chính xác hơn và index to hơn) và search_k (runtime — lớn hơn thì chính xác hơn và chậm hơn).

Cái Annoy có mà HNSW và IVF không có: index là một file read-only, mmap được.

• Nhiều process chia sẻ đúng một bản trong bộ nhớ — quan trọng với deployment nhiều worker.
• “Load” = mmap → truy vấn được ngay, không có bước deserialize.
• RAM thực tế do OS page cache quản, nên dấu chân bộ nhớ rất nhỏ.
• Hỗ trợ Euclid, Manhattan, cosine, Hamming, và dot product.

Giá phải trả, ghi thẳng trong README của nó: build() xong là không thêm được item nào nữa. Đây không phải thiếu sót — chính tính bất biến đó là thứ làm mmap an toàn và làm file chia sẻ được. Nó cũng ép một quy trình vận hành cụ thể: rebuild theo lô (Spotify rebuild định kỳ cho recommendation), chứ không phải cập nhật tại chỗ.

→ Annoy vẫn là câu trả lời đúng khi: corpus tĩnh hoặc rebuild theo lô, nhiều worker process, RAM hẹp, và bạn muốn deploy một file thay vì một service.

Đọc thêm

• [EN] spotify/annoy — README — nguồn của mục 1.5: đánh đổi n_trees/search_k, danh sách metric, khẳng định mmap chia sẻ giữa nhiều process, và câu “After calling build, no more items can be added”
• [VI] Nhận dạng khuôn mặt real-time (P1): làm quen ANN với Annoy — Viblo — đọc để thấy họ cây (mục 1) làm gì và vì sao nó phải dựng nhiều cây mới đủ recall

1.6 Bốn họ, một bảng — và một sợi chỉ

	Hash (LSH)	Cây (Annoy)	Phân cụm (IVF)	Đồ thị (HNSW)
Học từ dữ liệu?	không (data-oblivious)	một phần (điểm chia lấy từ dữ liệu)	có (k-means)	có
Cần train riêng?	không	không (nhưng cần toàn bộ dữ liệu để build)	có	không
Dựng từ index rỗng?	có	không	không	có
Thêm sau khi build	được	không được	được	được
Xoá một vector	rẻ	không được	rẻ	đau (§9.1)
Chi phí truy vấn	n^ρ (đa thức)	~log n × n_trees	√N	log N
RAM thêm ngoài vector	cao (~500 B/vector với k=16, L=50)	thấp (mmap, OS quản)	thấp (nlist × D × 4)	cao (M × 8–10 B)
Núm runtime	số bảng / multi-probe	search_k	nprobe	ef
Đưa xuống disk	dễ	thiết kế sẵn cho nó	thuận	khó
Còn là câu trả lời đúng khi	dedup, Jaccard, streaming, sketching	tĩnh + nhiều process + RAM hẹp	dung lượng, xoá nhiều, filter chọn lọc mạnh	recall cao và index vừa RAM

Ba điều rút ra:

1. Cả bốn họ có đúng một cặp núm: một lúc build, một lúc truy vấn. (k, L) / (n_trees, search_k) / (nlist, nprobe) / (M+efConstruction, ef). Chọn họ không phải chọn “cái nào nhanh nhất” mà là chọn bạn muốn trả giá ở đâu: RAM (LSH), tính bất biến (Annoy), bước train và √N (IVF), hay RAM và xoá khó (HNSW).
2. Hai họ thua là hai họ không học từ dữ liệu. LSH bốc hàm băm ngẫu nhiên; KD-tree chia theo trục toạ độ chứ không theo hình dạng dữ liệu. Hai họ thắng đều thích ứng với phân bố thật — và cả lý thuyết (mục 1.4) lẫn benchmark đều nói cùng một điều. Đây chính là sợi chỉ xuyên suốt Phần 3 nhìn từ một góc khác: quyết định về dữ liệu quan trọng hơn quyết định về thuật toán.
3. “Thua” ở bài toán ANN không có nghĩa là vô dụng. LSH vẫn là công cụ dedup không thay thế được, và Annoy vẫn là cách deploy nhẹ nhất. Đừng loại một họ khỏi hộp công cụ chỉ vì nó không thắng đường cong recall/QPS.

---

Đọc thêm

• [EN] Li et al. — Approximate Nearest Neighbor Search on High Dimensional Data: Experiments, Analyses, and Improvement (arXiv 1610.02455) — so LSH / cây / phân cụm / đồ thị trên cùng khung thực nghiệm; đây là loại bằng chứng đứng sau kết luận 2 của mục 1.6

2. Trực giác nền: “small world” và greedy routing

Thí nghiệm Milgram (six degrees of separation): trong mạng xã hội, hai người bất kỳ cách nhau khoảng 6 bước — dù mỗi người chỉ biết vài trăm người. Mạng như vậy gọi là small world: đường kính nhỏ theo log N dù bậc trung bình rất nhỏ.

Nhưng “tồn tại đường ngắn” không đồng nghĩa “tìm được đường ngắn bằng thông tin cục bộ”. Đây là điểm Kleinberg (2000) làm rõ, và là nền lý thuyết của cả họ đồ thị:

Nếu các cạnh dài được rút theo phân bố lũy thừa P(u→v) ∝ d(u,v)^(-α) với α bằng đúng số chiều của không gian nhúng, thì greedy routing — mỗi bước nhảy sang láng giềng gần đích nhất — tìm được đích trong số bước polylog. Với bất kỳ α khác, độ dài đường đi thoái hoá thành hàm lũy thừa của N.

Nói cách khác: đồ thị nào cũng đi được, chỉ đồ thị navigable mới đi nhanh — và navigable đòi cạnh phải trải đều trên mọi thang khoảng cách, không chỉ cạnh ngắn.

NSW (Malkov & cộng sự, Information Systems 2014) biến nhận xét đó thành thuật toán, với một mẹo đẹp: chèn điểm tuần tự, mỗi điểm nối tới các láng giềng gần nhất mà nó tìm được tại thời điểm đó. Những điểm chèn đầu tiên, khi đồ thị còn gần như trống, tạo ra các cạnh “sai” — nối hai vùng cách nhau rất xa. Chính những cạnh sai đó là long-range links. Paper đo được độ dài đường đi greedy tăng theo log N — bằng chứng thực nghiệm rằng cấu trúc thu được là navigable small world.

---

Đọc thêm

• [EN] HNSW giải thích bằng hình — Pinecone Learn — lấy trực giác trước khi vào paper; có hình cho phần greedy descent

3. NSW thiếu gì → vì sao phải có tầng

HNSW greedy descent — đi qua từng tầngMở toàn màn hình

NSW trộn mọi thang khoảng cách vào một đồ thị. Hệ quả: giai đoạn đầu của mỗi lần tìm kiếm — lúc còn cách đích rất xa — phải quét qua những node bậc rất cao mới nhảy được một bước dài, và điểm vào chọn ngẫu nhiên nên số bước phụ thuộc N mạnh hơn mong muốn.

HNSW sửa đúng một chỗ: tách cạnh theo thang khoảng cách đặc trưng, mỗi thang một tầng.

tầng 2   A ─────────────────────────── D          ← thưa, bước dài, "đi máy bay"
              │                    │
tầng 1   A ───── B ────── C ────── D ────── E     ← trung bình, "đi tàu"
         │   │   │   │   │   │   │   │   │
tầng 0   A─a─B─b─C─c─… mọi điểm đều có mặt …      ← dày, bước ngắn, "đi bộ"

Cấu trúc này là skip list đem sang không gian metric: tầng của mỗi điểm rút ngẫu nhiên theo phân bố suy giảm hàm mũ, y như skip list.

Tìm kiếm = greedy descent: vào từ điểm vào ở tầng đỉnh, greedy tới điểm cực tiểu cục bộ của tầng đó, tụt xuống tầng dưới tại chính điểm đó, lặp lại. Chỉ ở tầng 0 mới mở rộng tìm kiếm theo chùm (beam) rộng ef.

→ Tầng trên làm việc “định vị thô”, và vì nó thưa nên định vị thô rất rẻ.

---

Đọc thêm

• [VI] Hiểu và ứng dụng HNSW trong tìm kiếm ngữ nghĩa với embedding — Viblo — bản tiếng Việt của mục 3: cấu trúc nhiều tầng và vai trò “đường ngắn / đường dài”, có hình
• [EN] Malkov, Ponomarenko, Logvinov & Krylov — Approximate nearest neighbor algorithm based on navigable small world graphs, Information Systems 45 (2014) — NSW, tiền thân không phân tầng; đọc để thấy đồ thị đo được log N hop từ trước khi có tầng

4. Bốn thuật toán, viết ra cho rõ

Paper gốc có 5 thuật toán. Bốn cái sau là toàn bộ nội dung thật của HNSW.

SEARCH-LAYER(q, ep, ef, lc) — beam search trên một tầng. Đây là hạt nhân, dùng cả khi xây lẫn khi truy vấn:

visited  ← ep                      # đã thăm
cand     ← ep                      # min-heap theo d(·, q)   — ứng viên để mở rộng
W        ← ep                      # max-heap theo d(·, q)   — ef kết quả tốt nhất

while cand ≠ ∅:
    c ← ứng viên gần q nhất trong cand;  cand.pop(c)
    if d(c, q) > d(xa nhất trong W, q):  break        # ← điều kiện dừng
    for e in neighbours(c, tầng lc):
        if e ∉ visited:
            visited.add(e)
            if d(e,q) < d(xa nhất trong W, q)  or  |W| < ef:
                cand.add(e);  W.add(e)
                if |W| > ef: W.pop(xa nhất)
return W

Đọc kỹ dòng break: khi ứng viên tốt nhất còn lại đã xa hơn kết quả tệ nhất đang giữ, dừng. ef vì thế không phải “số node sẽ thăm” mà là độ rộng của vùng ta chịu giữ mở — ef lớn thì điều kiện dừng khó thoả hơn, nên đi xa hơn, nên recall cao hơn và chậm hơn.

KNN-SEARCH(q, k, ef):

ep ← điểm vào cố định của index;   L ← tầng cao nhất hiện có
for lc = L … 1:
    W  ← SEARCH-LAYER(q, ep, ef=1, lc)      # ef=1: greedy thuần, chỉ để định vị
    ep ← phần tử duy nhất của W
W ← SEARCH-LAYER(q, ep, ef, 0)              # chỉ tầng 0 mới dùng ef thật
return k phần tử gần nhất trong W

INSERT(x, M, Mmax, efConstruction):

l ← ⌊ −ln(U(0,1)) · mL ⌋                    # tầng của x, xem mục 5
ep ← điểm vào;  L ← tầng cao nhất
for lc = L … l+1:      ep ← greedy 1 bước xuống (như trên)
for lc = min(L, l) … 0:
    W  ← SEARCH-LAYER(x, ep, efConstruction, lc)
    nb ← SELECT-NEIGHBORS(x, W, M, lc)
    nối x ↔ nb  (hai chiều)
    for e in nb:                            # cắt tỉa lại phía láng giềng
        if |neighbours(e, lc)| > Mmax:
            neighbours(e, lc) ← SELECT-NEIGHBORS(e, neighbours(e,lc), Mmax, lc)
    ep ← W
if l > L: cập nhật điểm vào ← x

Ba chi tiết dễ bỏ qua nhưng quan trọng:

• Cạnh là hai chiều. Nối x vào e cũng làm bậc của e tăng → phải cắt tỉa lại phía e. Đây là lý do việc chèn có thể làm xấu đường đi của các điểm đã có.
• efConstruction chỉ xuất hiện ở bước xây. Nó không phải núm runtime.
• Mmax ở tầng 0 thường bằng 2M, các tầng trên bằng M. Tầng 0 là nơi thật sự quyết định độ chính xác, nên nó phải dày hơn.

SELECT-NEIGHBORS-HEURISTIC(q, C, M) — mục 6 dành riêng cho nó.

---

5. Tính bằng tay: một điểm nằm ở tầng nào, và index nặng bao nhiêu

Tầng của mỗi điểm:

$$l = \left\lfloor -\ln\bigl(U(0,1)\bigr) \times m_L \right\rfloor, \qquad m_L = \frac{1}{\ln M}$$

Với M = 16: ln 16 = 2,7726 → mL = 0,3607.

Điểm rơi lên tầng ≥ 1 khi −ln(U) × 0,3607 ≥ 1, tức U ≤ e^(−2,7726) = 0,0625 = 1/16. Tổng quát: P(l ≥ j) = (1/M)^j — mỗi tầng lên cao lại thưa đi đúng M lần. (Đây cũng là lý do mL = 1/ln M là lựa chọn “tối ưu” trong paper: nó cân giữa số tầng và trùng lặp giữa các tầng.)

Với N = 1.000.000, M = 16, số điểm kỳ vọng mỗi tầng:

Tầng	Số điểm	Ý nghĩa
0	1.000.000	mọi điểm
1	62.500
2	3.906
3	244
4	15
5	~1	thường là tầng đỉnh

→ Khoảng 6 tầng cho 1 triệu điểm. Giai đoạn descent (tầng 5→1) chỉ phải xử lý vài chục nghìn điểm trong tổng số một triệu — đó chính là chỗ tiết kiệm.

Bộ nhớ của đồ thị. hnswlib ghi: xấp xỉ M × 8–10 byte mỗi phần tử (mỗi cạnh là một id 4–8 byte; tầng 0 có 2M cạnh, tầng trên M, trung bình ~1,5M).

M = 16, N = 1M   →  ~160 byte/vector  →  ~0,16 GB    chỉ riêng đồ thị
M = 32, N = 1M   →  ~320 byte/vector  →  ~0,32 GB

So với 6,1 GB vector float32 thì đồ thị là phần nhỏ — nhưng nó không nén được bằng quantization. Nén vector 32× rồi thì đồ thị trở thành phần lớn nhất: 0,19 GB vector nén

• 0,32 GB đồ thị. Đây là lý do các biến thể “bỏ tầng” ở mục 9.4 lại đáng chú ý.

---

6. Vì sao phải cắt tỉa bằng heuristic, không phải lấy M cạnh gần nhất

Cách hiển nhiên (SELECT-NEIGHBORS-SIMPLE): giữ M ứng viên gần nhất. Cách này hỏng.

Hình dung corpus có hai cụm rất xa nhau — ví dụ chunk pháp luật và chunk y tế. Với mọi điểm trong cụm A, M láng giềng gần nhất đều nằm trong A. Không điểm nào giữ cạnh ra khỏi cụm → đồ thị vỡ thành hai thành phần liên thông rời. Greedy search bắt đầu ở A không bao giờ tới được B. Recall sập, không có lỗi nào được báo.

SELECT-NEIGHBORS-HEURISTIC sửa bằng một điều kiện “che” (blocking):

R ← ∅                                     # tập được chọn
for e in C theo thứ tự gần q dần:
    if ∀ r ∈ R :  d(e, q) < d(e, r)       # e không bị r nào "che"
        R.add(e)
    if |R| = M: break

Diễn giải điều kiện: nếu tồn tại r đã chọn mà d(e, r) < d(e, q), thì e gần r hơn là gần q — đi từ q sang r rồi mới sang e cũng không đắt hơn nối thẳng q→e. Cạnh q→e là dư. Bỏ nó, dành slot cho một ứng viên ở hướng khác.

Kết quả: M cạnh giữ lại phân tán về nhiều hướng và nhiều thang khoảng cách thay vì dồn cả vào một cụm — đúng thứ mục 2 nói là điều kiện để đồ thị navigable. (Đây xấp xỉ relative neighborhood graph; Vamana ở mục 10 nới cùng điều kiện này bằng hệ số α.)

Paper ghi hiệu quả của heuristic rõ nhất ở: dữ liệu chiều thấp, dải recall cao với dữ liệu chiều trung bình, và dữ liệu phân cụm mạnh.

Áp vào tiếng Việt. Corpus doanh nghiệp Việt thường là hợp của vài cụm rất tách biệt (nội quy, hợp đồng, tài liệu kỹ thuật, FAQ khách hàng) — tức đúng ca “phân cụm mạnh”. Nếu bạn tự cài HNSW, đây là chỗ không được cắt góc.

---

Đọc thêm

• [EN] Malkov & Yashunin — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320) — nguồn của mục 4–6: đọc Algorithm 1–5 và §4.1 (chọn mL = 1/ln M, và vì sao Mmax0 = 2M)

7. Ba tham số, một bảng chẩn đoán

Tham số	Lúc nào	Khoảng hợp lý	Đổi gì
M	build, bất biến	2–100; 12–48 cho đa số ca	RAM đồ thị (M×8–10 B/vector) và recall trần
efConstruction	build, trả giá một lần	100–500	chất lượng đồ thị; tới một mức thì tăng nữa vô ích
ef / efSearch	runtime	≥ k, thường 64–512	núm recall/latency duy nhất không cần build lại

Ba câu hướng dẫn đáng nhớ, lấy từ tài liệu hnswlib:

• M cao có lợi khi intrinsic dimensionality cao hoặc khi bạn cần recall rất cao; M thấp tốt hơn cho dữ liệu chiều nội tại thấp / recall vừa phải.
• Cách kiểm tra efConstruction đã đủ chưa: đặt ef = efConstruction rồi đo recall@M. Nếu recall < 0,9 thì đồ thị còn xây kém — tăng efConstruction. Đây là phép thử tách bạch “index xây tệ” khỏi “truy vấn tìm hẹp”, hai thứ hay bị lẫn.
• ef không được nhỏ hơn k. Đặt ef = 10 rồi hỏi top-100 là tự bắn vào chân.

Bảng chẩn đoán:

Triệu chứng	Nguyên nhân khả dĩ	Việc phải làm
Recall thấp đều ở mọi truy vấn, ef tăng cũng không cứu	Đồ thị xây kém, hoặc M quá nhỏ cho dữ liệu này	Đo recall@M với ef = efConstruction; nếu <0,9 → tăng efConstruction, sau đó mới tăng M (phải build lại)
Recall thấp chỉ khi có filter	Đồ thị bị filter làm rời rạc	7.8 — không phải chuyện của ef
Recall tốt trên bộ test, tệ trên truy vấn thật	Query lệch phân bố so với corpus (OOD)	mục 9.3
Latency dao động, p99 gấp nhiều lần p50	Segment chưa index xong / optimizer	7.6 — không phải chuyện của HNSW
Recall tụt dần theo thời gian	Xoá/cập nhật làm hỏng topology	mục 9.1

Trước khi xoay bất kỳ núm nào: chạy exact: true (brute force) trên cùng bộ truy vấn để có baseline recall = 1,0. Không có baseline thì bạn đang tối ưu một con số không biết trần của nó ở đâu.

---

Đọc thêm

• [EN] hnswlib — ALGO_PARAMS.md — nguồn của mục 7: khoảng M 2–100, công thức RAM M × 8–10 byte/phần tử, và phép thử ef = ef_construction → recall < 0,9 thì tăng
• [VI] Nhận dạng khuôn mặt real-time (P2): hệ hoàn chỉnh với hnswlib — Viblo — code hnswlib thật bằng tiếng Việt: M, ef_construction, set_ef xuất hiện ở đâu trong một hệ đang chạy

8. O(log N) — và bốn giả định ẩn trong nó

Paper phát biểu độ phức tạp tìm kiếm là logarit theo N. Điều đó đúng, nhưng có điều kiện, và mọi vấn đề thực tế của HNSW đều là một trong các điều kiện này bị vỡ:

1. Dữ liệu có intrinsic dimensionality thấp — vector 1536 chiều nhưng thực sự nằm trên một manifold ít chiều hơn nhiều. Với dữ liệu ngẫu nhiên đều thật sự 1536 chiều, không thuật toán ANN nào thắng brute force.
2. Query cùng phân bố với corpus. Vỡ → mục 9.3.
3. Toàn bộ tập điểm đều tìm kiếm được — không có node bị cô lập. Vỡ khi xoá → mục 9.1.
4. Không có ràng buộc ngoài khoảng cách. Vỡ khi thêm filter → 7.8.

Build là O(N log N) — và trên thực tế, chi phí build (nhân efConstruction) là thứ quyết định bạn có dám reindex hay không, tức quyết định luôn cả chiến lược vận hành ở mục 9.1.

---

9. Bốn chỗ HNSW đau

9.1 Xoá và cập nhật — chỗ đau nhất

HNSW không có phép xoá trong paper gốc. Mọi hệ thật đều xử lý bằng tombstone (xoá mềm): đánh dấu “không được trả về”, vector vẫn nằm trong đồ thị và vẫn được đi qua khi tìm kiếm. Cùng cơ chế với inverted index (3.12), nhưng hệ quả nặng hơn nhiều, vì:

• Tầng trên rất thưa (mục 5: tầng 4 chỉ có ~15 điểm trên 1 triệu). Xoá thật một node ở tầng cao có thể ngắt kết nối cả một nhánh bên dưới nó.
• Xoá mềm liên tục làm tỉ lệ node “chết mà vẫn phải đi qua” tăng dần → mỗi truy vấn tốn thêm bước, và các node sống có thể trở thành unreachable (không còn đường greedy nào tới). Đây là hiện tượng được mô tả và định lượng trong paper 2024 về cập nhật realtime.
• Sửa “đúng cách” (tìm cạnh vào, nối lại láng giềng của node bị xoá) làm latency xoá tăng; sửa “lười” giữ latency thấp nhưng để topology hỏng dần. Đây là đánh đổi trung tâm của mọi dòng nghiên cứu về xoá in-place (FreshDiskANN, MERIT).
• Có cả hệ quả bảo mật/tuân thủ: vector xoá mềm vẫn nằm trong index và vẫn tái tạo lại được — nghĩa là “đã xoá theo yêu cầu người dùng” ở tầng API không đồng nghĩa đã xoá ở tầng lưu trữ.

Quy tắc vận hành thực dụng: coi index HNSW như cấu trúc gần bất biến — ghi thêm thì rẻ, xoá/sửa nhiều thì phải rebuild định kỳ rồi đổi qua alias (3.12, 7.6). Và đo recall theo thời gian, không chỉ đo lúc mới build: đây là loại suy giảm không phát ra lỗi nào.

Đọc thêm

• [EN] Subramanya et al. — FreshDiskANN (arXiv 2105.09613) — mục 9.1: kiến trúc buffer RAM + index disk và merge, tức cách một hệ đồ thị thật sự nhận cập nhật liên tục
• [EN] Xu et al. — Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation (arXiv 2407.07871) — mục 9.1: hiện tượng node sống nhưng không còn đường tới, được định lượng
• [EN] Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases (arXiv 2606.18497) — mục 9.1: vì sao “xoá” ở tầng API không phải xoá ở tầng lưu trữ — đọc nếu bạn có ràng buộc về dữ liệu cá nhân

9.2 Filter

Đủ quan trọng để có mục riêng: 7.8 — Filterable HNSW và query planner. Một dòng để nhớ: filter làm đồ thị rời rạc, và đồ thị rời rạc thì greedy search không còn tính chất nào được bảo đảm.

9.3 Query lệch phân bố (out-of-distribution)

Gần như mọi benchmark ANN cổ điển lấy query từ chính corpus (SIFT, GloVe, GIST). Hệ RAG thật thì không: query là câu hỏi ngắn của người dùng, corpus là chunk tài liệu dài — hai phân bố khác nhau, có khi còn khác model embedding.

VIBE (2025) là benchmark dựng riêng để đo chuyện này: 21 bản cài đặt vector index, trên 12 dataset in-distribution và 6 dataset out-of-distribution, dùng embedding của các model hiện đại thay vì dataset thị giác thập niên 2010.

→ Ý nghĩa thực tế: recall bạn đo bằng query lấy từ corpus là số lạc quan. Muốn có con số dùng được, golden set phải là query thật của người dùng thật — như data/goldenset.jsonl của repo này (Phần 2).

Đọc thêm

• [EN] VIBE: Vector Index Benchmark for Embeddings (arXiv 2505.17810) — mục 9.3: 21 index, 12 dataset in-distribution + 6 out-of-distribution; benchmark hiện đại nhất để đối chiếu, thay cho SIFT/GloVe

9.4 Có thể chữ “H” không quan trọng như ta tưởng

Kết quả đáng chú ý nhất về HNSW những năm gần đây, ICML 2025 (oral): “Down with the Hierarchy: The ‘H’ in HNSW Stands for ‘Hubs’”.

Nội dung: với dữ liệu chiều cao, bỏ hẳn phân tầng — dùng một đồ thị NSW phẳng — cho latency và recall gần như y hệt HNSW, mà tốn ít bộ nhớ hơn. Bản cài đặt của họ (FlatNav) tiết kiệm khoảng 38–39% bộ nhớ đỉnh khi build so với hnswlib trên hai dataset Big-ANN.

Giải thích của tác giả — hub highway hypothesis: ở chiều cao xuất hiện hiện tượng hubness, một số ít điểm có mặt trong danh sách láng giềng của rất nhiều điểm khác. Những hub đó tự tạo thành một “đường cao tốc” liên thông tốt bên trong đồ thị phẳng — và nó đảm nhiệm đúng vai trò mà các tầng trên được cho là đảm nhiệm. Tầng, ở chiều cao, chỉ là cách nhân tạo làm ra thứ mà dữ liệu tự sinh ra.

Hai điều rút ra:

• Phân tầng vẫn có giá trị ở chiều thấp (và đây cũng là nơi heuristic ở mục 6 quan trọng nhất). Đừng đọc thành “HNSW sai”.
• Nhưng nếu RAM là ràng buộc và vector của bạn nhiều chiều — mục 5 cho thấy đồ thị trở thành phần chi phí lớn nhất sau khi nén vector — thì “bỏ tầng” là một hướng thật, không phải hiếu kỳ học thuật. Hubness cũng chính là lý do một số truy vấn (những truy vấn nhắm vào anti-hub) có p99 tệ bất thường.

---

Đọc thêm

• [EN] Munyampirwa, Lakshman & Coleman — Down with the Hierarchy: The ‘H’ in HNSW Stands for “Hubs” (ICML 2025) — nguồn của mục 9.4: hub highway hypothesis, và con số ~38–39% bộ nhớ đỉnh tiết kiệm được của FlatNav

10. Sau HNSW: Vamana / DiskANN, khi index không vừa RAM

HNSW giả định đồ thị nằm trong RAM. Vamana (nhân của DiskANN) được thiết kế cho index nằm trên SSD, và vì mỗi bước đi là một lần đọc disk, mục tiêu đổi từ “ít phép tính” sang “ít bước đi”.

Ba khác biệt cốt lõi so với HNSW:

	HNSW	Vamana / DiskANN
Hướng xây	thưa → dày: chèn dần, mỗi điểm nối M cạnh	dày → thưa: bắt đầu từ đồ thị ngẫu nhiên dày rồi cắt tỉa lặp
Cấu trúc	nhiều tầng	một tầng phẳng
Điều kiện cắt tỉa	“che” chặt (d(e,r) < d(e,q))	nới bằng α: chỉ bỏ e nếu α · d(e,r) < d(e,q), α ≈ 1,2 → giữ thêm cạnh dài
Tối ưu cho	ít phép tính, RAM	ít lần đọc disk (đường đi ngắn hơn)

Tham số điển hình trong paper: R = 70, L = 75, α = 1,2. Hệ quả của α > 1: đồ thị giữ lại nhiều cạnh “đường dài” hơn → đường đi trung bình ngắn nhất trong nhóm NSG/HNSW/Vamana ở cùng mức recall. Chạy hoàn toàn trong RAM thì Vamana và HNSW xấp xỉ nhau; khác biệt chỉ lộ ra khi index xuống disk, hoặc khi cần cập nhật streaming (FreshDiskANN, mục 9.1).

Bảng chọn:

Tình huống	Chọn	Vì sao
< ~10k vector	brute force (exact: true)	ANN không đáng; và bạn cần baseline này để đo mọi thứ khác
Index vừa RAM, cần recall cao, ghi thêm nhiều hơn xoá	HNSW	mặc định đúng; núm ef runtime
Index vừa RAM, RAM sát hạn, vector nhiều chiều	HNSW + quantization (6.1), hoặc đồ thị phẳng (mục 9.4)	đồ thị là phần không nén được
Hàng trăm triệu–tỉ vector, không thể nhét RAM	DiskANN / Vamana	tối ưu số lần đọc disk
RAM rất hẹp, chấp nhận recall thấp hơn, dữ liệu tĩnh	IVF-PQ	nén sâu nhất, train một lần → §1.2
Filter chọn lọc rất mạnh (< ~1% corpus)	IVF, hoặc pre-filter + brute force	quét tuyến tính trong cụm không bị filter phá vỡ → §1.3
Xoá rất thường xuyên, hoặc corpus lớn dần từ số 0	HNSW (dựng được từ rỗng) hoặc IVF (xoá rẻ) — xem §1.3	hai họ mạnh yếu ngược nhau ở đúng trục này
Xoá/sửa liên tục, dữ liệu “sống”	HNSW + rebuild qua alias, hoặc engine có xoá in-place	mục 9.1

---

Đọc thêm

• [EN] Vamana vs HNSW — Weaviate blog — nguồn của mục 10: hướng xây ngược nhau, vai trò của α, và cảnh báo rằng so trong RAM thì hai bên xấp xỉ
• [EN] Wang et al. — A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (arXiv 2101.12631) — survey đặt HNSW/NSG/Vamana/KGraph lên cùng một khung; đọc khi cần chọn giữa các họ đồ thị

11. Đo cái gì — vì recall@k không phải là mục tiêu cuối

Cả mục này nói về recall. Nhưng có một lưu ý mà nhóm làm RAG rất nên biết: recall@k phạt như nhau mọi lần “trượt”, dù vector trả về cách vector đúng 0,001 hay cách rất xa. Với RAG, hai trường hợp đó khác nhau một trời một vực — đổi láng giềng thứ 3 bằng một chunk gần tương đương thường không làm câu trả lời của LLM xấu đi chút nào.

Đó là lập luận của một dòng nghiên cứu 2026 đề xuất thay recall@k bằng 1/Ratio@k (tỉ số khoảng cách giữa kết quả trả về và kết quả đúng): không cần tham số, tính được từ chính dữ liệu benchmark, và đạt ngưỡng chất lượng ở chi phí tính toán thấp hơn recall@k — kèm quan sát rằng chất lượng downstream vẫn giữ ngay cả khi recall@k tụt đáng kể.

Kết luận vận hành: dùng recall@k để gỡ lỗi index (nó tách bạch, dễ đo, có baseline exact: true). Nhưng đừng tối ưu nó như mục tiêu cuối — mục tiêu cuối là số đo end-to-end ở Phần 2, đặc biệt C.4 — RAG end-to-end. Một hệ recall 0,92 với chunking tốt đánh bại hệ recall 0,99 với chunking tệ, mỗi lần.

---

Đọc thêm

• [EN] ANN-Benchmarks — đường cong recall/QPS kinh điển; hữu ích nhưng nhớ giới hạn ở mục 9.3 khi đọc nó
• [EN] ANN Search: Recall What Matters (arXiv 2606.04522) — mục 11: lập luận thay recall@k bằng 1/Ratio@k và bằng chứng chất lượng downstream không tụt cùng recall