← Về danh sách
AI & Dữ liệu
#ANN#벡터인덱스#HNSW#IVF-PQ#벡터검색
Cập nhật lần cuối · 2026-11-11

Tìm kiếm láng giềng gần gần đúng (ANN) và chỉ mục vector (HNSW·IVF·PQ)

1. Tổng quan

A. Định nghĩa

Tìm kiếm láng giềng gần gần đúng (Approximate Nearest Neighbor, ANN) là kỹ thuật tìm kiếm mà khi tìm K vector gần nhất với vector truy vấn trong không gian vector nhiều chiều, nó từ bỏ tìm kiếm vét cạn (brute-force, tính khoảng cách tới từng vector một) và thay vào đó hy sinh một chút độ chính xác (recall) để thu hẹp đáng kể không gian tìm kiếm, qua đó giảm độ trễ truy vấn hàng chục đến hàng nghìn lần; cấu trúc dữ liệu tổ chức sẵn các vector dưới dạng đồ thị, cụm hay mã lượng tử hóa cho mục đích này gọi là chỉ mục vector (vector index).

Câu hỏi ANN trả lời là "K mục tương tự nhất về ngữ nghĩa với vector truy vấn này là gì." Các vector tài liệu, hình ảnh, người dùng được biểu diễn bằng [[embedding]] thường đạt hàng trăm đến hàng nghìn chiều, và độ tương tự được định nghĩa bằng độ tương tự cosine hoặc khoảng cách Euclid giữa các vector đó. Để trả lời chính xác thì phải tính khoảng cách tới toàn bộ N vector cho mỗi truy vấn, nên chi phí tăng tuyến tính theo O(N·d). Với các dịch vụ [[rag]], gợi ý và tìm kiếm phải tra cứu hàng trăm triệu vector trong vài mili giây, tìm kiếm vét cạn này là bất khả thi trên thực tế. ANN định nghĩa lại bài toán thành tìm "không phải hạng 1 chính xác mà là các ứng viên có khả năng cao nằm trong top K, một cách nhanh chóng."

Ở đây điều quan trọng là không nhầm ANN với [[vector-database]]. Cơ sở dữ liệu vector là hệ thống (sản phẩm) chịu trách nhiệm lưu trữ, cập nhật, lọc, sao chép và giao dịch trên vector, còn ANN là tầng thuật toán/chỉ mục cốt lõi đảm nhận "làm thế nào thu hẹp nhanh các ứng viên gần một truy vấn cho trước" bên trong nó. Nghĩa là động cơ quyết định thực chất hiệu năng tìm kiếm của vector DB chính là chỉ mục ANN, và dù dùng cùng một embedding, recall, độ trễ, bộ nhớ và chi phí hiện ra hoàn toàn khác nhau tùy theo cấu hình chỉ mục nào với tham số nào.

B. Bối cảnh ra đời và sự cần thiết

Khi học biểu diễn sâu trở nên phổ biến, văn bản, hình ảnh, giọng nói và nhật ký hành vi đều được quy về vector embedding nhiều chiều, và tìm kiếm vector—tìm kiếm, gợi ý và phát hiện bằng "tương tự ngữ nghĩa" thay vì "khớp từ khóa"—trở thành tính năng cốt lõi của dịch vụ. Trong thời đại AI tạo sinh, [[rag]] chèn các tài liệu liên quan truy xuất dưới dạng vector từ cơ sở tri thức ở mỗi truy vấn để giảm ảo giác của LLM, nên độ trễ và recall của tìm kiếm vector trực tiếp chi phối cả chất lượng và tốc độ phản hồi. Vấn đề là quy mô. Khi tài liệu, sản phẩm và người dùng toàn công ty đạt hàng chục triệu đến hàng tỷ vector, tìm kiếm vét cạn mất vài giây mỗi truy vấn và vượt ngân sách độ trễ của dịch vụ tương tác.

Chính sự kiện nhiều chiều làm bài toán khó hơn. Vì lời nguyền chiều (curse of dimensionality), các chỉ mục không gian truyền thống chia không gian thành lưới (họ cây k-d, cây R của [[multidimensional-index]]) thấy hiệu quả cắt tỉa giảm mạnh khi vượt hàng trăm nghìn chiều, trở nên về cơ bản không khác tìm kiếm vét cạn. Nghĩa là tìm nhanh láng giềng gần "chính xác" ở chiều cao về cơ bản là tốn kém, đã được xác nhận ở cả lý thuyết lẫn thực tiễn. ANN tận dụng về mặt kỹ thuật thực tế vận hành rằng "dù 1~2% kết quả tìm kiếm không phải láng giềng gần thật thì cũng hầu như không ảnh hưởng chất lượng gợi ý hay RAG," đổi một nhượng bộ nhỏ về độ chính xác lấy giảm lớn về độ trễ và chi phí.

Sự cần thiết rõ ràng qua con số. Vét cạn 100 triệu vector 768 chiều cần khoảng 10^11 phép tính dấu phẩy động mỗi truy vấn, mất hàng giây trên một lõi đơn. Ngược lại, một chỉ mục đồ thị như HNSW đạt recall trên 95% trong vài mili giây chỉ với vài nghìn phép tính khoảng cách mỗi truy vấn. Khoảng cách tốc độ bốn đến năm bậc này chính là lý do ANN trở thành kỹ thuật tìm kiếm tiêu chuẩn trên thực tế cho các dịch vụ vector quy mô lớn.

C. Đặc điểm

Hiệu năng ANN được biểu đạt không phải bằng một con số mà bằng sự đánh đổi bốn chiều giữa recall, độ trễ (latency/QPS), bộ nhớ và thời gian xây dựng. Trong khi vét cạn bảo đảm recall 100% với chi phí cao, ANN chọn một điểm trên đường cong đánh đổi này bằng cách điều chỉnh tham số. Do đó câu "ANN nhanh" luôn phải được diễn giải cùng điều kiện "ở recall bao nhiêu," và một con số độ trễ không báo cáo recall là vô nghĩa—đó là nguyên tắc số một của lĩnh vực.

Một đặc điểm khác là ba trục thiết kế trực giao với nhau. Chỉ mục ANN về cơ bản được cấu thành từ các kết hợp của ① tìm kiếm đồ thị (HNSW), ② thu hẹp ứng viên dựa trên phân cụm (IVF), và ③ nén vector (PQ), vốn giải các bài toán khác nhau là "thu hẹp thế nào," "thu hẹp bao nhiêu," và "lưu nhỏ đến đâu." Vì vậy chỉ mục thực tế thường không phải một kỹ thuật đơn lẻ mà kết hợp nhiều trục, như IVF+PQ hay HNSW+PQ, để đáp ứng đồng thời yêu cầu bộ nhớ, recall và độ trễ.

Cuối cùng, phải vận hành ANN trên tiền đề rằng nó nhạy với phân phối dữ liệu và truy vấn. Dù cùng thuật toán và tham số, recall thay đổi theo số chiều của embedding, mức độ các vector tụ lại trong không gian (tính cụm), và truy vấn giống phân phối dữ liệu đến đâu. Vì vậy "cấu hình tốt ở dịch vụ A" không chuyển nguyên vẹn sang dịch vụ B, và ngay cả những con số đã kiểm chứng qua benchmark cũng phải đo lại trên dữ liệu của chính mình. Sự phụ thuộc dữ liệu này là tiền đề cốt lõi được bàn lặp lại ở các mục thiết kế tham số và giám sát vận hành phía sau.

2. Cấu trúc và nguyên lý hoạt động

Cấu trúc tổng thể của ANN trở nên rõ ràng khi hiểu như một đường ống hai giai đoạn: "khi truy vấn đến, ① chỉ mục nhanh chóng thu hẹp về một tập nhỏ ứng viên (candidate generation), ② tính khoảng cách chính xác chỉ xếp hạng các ứng viên đó (reranking), và ③ trả về top K." Thu nhỏ bao nhiêu tập ứng viên mà trên đó tính khoảng cách trong toàn bộ N chính là tốc độ, và có bao nhiêu láng giềng gần thật nằm trong tập ứng viên đó chính là recall.

flowchart TB
    Q["vector truy vấn q (d chiều)"] --> IDX["tìm kiếm chỉ mục vector (đồ thị·cụm·lượng tử hóa)"]
    IDX --> CAND["tập ứng viên (một số ít trong toàn bộ N)"]
    CAND --> RR["tính lại khoảng cách chính xác·xếp hạng lại (reranking)"]
    RR --> TOPK["trả về kết quả top-K"]
    subgraph BUILD["xây dựng chỉ mục ngoại tuyến"]
      V["N vector embedding"] --> B["xây dựng chỉ mục (nối đồ thị·k-means·huấn luyện codebook)"]
      B --> IDX
    end

Chỉ số cốt lõi trong đường ống này là Recall@K. Nếu G là tập K láng giềng gần thật của một truy vấn và R là K mà chỉ mục trả về, thì Recall@K = |G ∩ R| / K. Ví dụ Recall@10 = 0.98 nghĩa là "trung bình 9.8 trong top 10 khớp với kết quả vét cạn." Một dịch vụ thường điều chỉnh tham số hướng tới "độ trễ tối thiểu thỏa mãn Recall@10 ≥ 0.95," và recall mục tiêu này chính là điểm xuất phát của thiết kế ANN.

Định nghĩa khoảng cách/độ tương tự cũng ảnh hưởng thiết kế. Khoảng cách Euclid (L2), tích vô hướng (inner product) và độ tương tự cosine chủ yếu được dùng; cosine trở nên tương đương với tích vô hướng khi vector được chuẩn hóa, nên nhiều động cơ xử lý nó như tích vô hướng sau chuẩn hóa. Vì ranh giới cụm và kết nối đồ thị của chỉ mục thay đổi tùy khoảng cách nào được dùng, việc khớp khoảng cách mà mô hình embedding được huấn luyện với khoảng cách của chỉ mục là tiền đề ẩn của recall. Trong thực tế, sự bất khớp "embedding huấn luyện bằng cosine nhưng chỉ mục xây bằng L2" là nguyên nhân phổ biến làm giảm recall, nên an toàn hơn là ghi lại cài đặt metric khoảng cách cùng quy ước embedding khi tạo chỉ mục.

Hiệu quả của giai đoạn sinh ứng viên cũng quan trọng vì nó chi phối toàn bộ. Xếp hạng lại (reranking) chỉ rẻ khi ứng viên nhỏ—hàng trăm đến hàng nghìn—nên một thiết kế chỉ mục "chứa láng giềng gần thật trong một tập ứng viên nhỏ với xác suất cao" là bản chất của ANN. Ba thuật toán ở mục sau chính là các câu trả lời khác nhau cho bài toán "tạo ứng viên tốt một cách rẻ tiền" này.

Ở đây phải nắm vì sao đồ thị, cụm và lượng tử hóa được dùng thay cho chỉ mục không gian truyền thống. Ở chiều thấp (tọa độ địa lý 2~3 chiều), cây k-d và cây R cắt tỉa không gian tìm kiếm hiệu quả bằng cách chia luân phiên các trục. Nhưng ở hàng trăm chiều, do hiện tượng tập trung khoảng cách (distance concentration), nơi mọi điểm nằm ở khoảng cách tương tự nhau, việc cắt tỉa "chỉ nhìn nhánh gần và bỏ nhánh xa" ngừng hoạt động. Nghĩa là điều kiện phân nhánh của cây rốt cuộc mở gần như mọi nhánh, thoái hóa thành vét cạn. Họ ANN né tránh giới hạn này bằng cách "từ bỏ bảo đảm ranh giới chính xác và chỉ gom các ứng viên gần về mặt thống kê," đó là lý do căn bản buộc phải chọn gần đúng (approximate) ở chiều cao.

3. Các thuật toán chỉ mục chính — HNSW · IVF · PQ

Ba thuật toán tiêu biểu mỗi cái xử lý không gian tìm kiếm bằng một chiến lược khác nhau là đồ thị·phân hoạch·nén. Thay vì chỉ liệt kê, hiểu "mỗi cái cố giải quyết điều gì" mới xác lập được căn cứ cho việc kết hợp và chọn tham số.

flowchart LR
    subgraph HNSW_G["HNSW (đồ thị phân tầng)"]
      L2["tầng trên (cạnh thưa·tầm xa)"] --> L1["tầng giữa"]
      L1 --> L0["tầng đáy (cạnh dày·tầm gần)"]
    end
    subgraph IVF_G["IVF (tệp đảo·cụm)"]
      C["truy vấn → chọn nprobe cụm gần nhất"] --> CELL["chỉ tìm vector của ô đó"]
    end
    subgraph PQ_G["PQ (lượng tử hóa tích)"]
      SUB["chia vector thành m vector con"] --> CODE["nén mỗi phần thành ID codebook"]
    end

A. HNSW (Hierarchical Navigable Small World, đồ thị thế giới nhỏ điều hướng được phân tầng). HNSW xếp thành nhiều tầng một đồ thị lân cận trong đó các vector là nút và "các vector gần được nối bằng cạnh." Các tầng trên có ít nút và cạnh dài để nhảy xa, càng xuống dưới càng dày để tiếp cận tinh vi. Truy vấn bắt đầu từ một điểm vào ở tầng trên cùng và đi xuống các tầng bằng cách lặp lại tìm kiếm tham lam "di chuyển tới láng giềng của nút hiện tại mà gần truy vấn hơn." Điều này giống như đi đường cao tốc tới vị trí đại khái rồi tìm đích qua đường nhánh và ngõ hẻm, giảm phép tính khoảng cách mỗi truy vấn xuống gần quy mô logarit thay vì toàn bộ N. Các tham số cốt lõi là số cạnh mỗi nút M (mật độ đồ thị·bộ nhớ), bề rộng tìm kiếm lúc xây efConstruction (chất lượng đồ thị·thời gian build), và bề rộng tìm kiếm lúc truy vấn efSearch (recall·độ trễ). Đặc biệt efSearch là "kích thước danh sách ứng viên giữ cho mỗi truy vấn"; tăng nó làm recall tăng và độ trễ tăng tỉ lệ, trở thành núm chính điều chỉnh recall-độ trễ theo thời gian thực. HNSW thuộc trục có đường cong recall-độ trễ tốt nhất, nhưng vì phải lưu cạnh đồ thị ngoài các vector gốc, nó thường tốn thêm 30~50% bộ nhớ so với các vector.

B. IVF (Inverted File Index, chỉ mục tệp đảo). IVF trước tiên phân hoạch toàn bộ vector thành nlist cụm (ô) bằng k-means và đặt tâm (centroid) của mỗi ô làm "bộ lượng tử hóa thô (coarse quantizer)." Khi truy vấn đến, nó chỉ mở nprobe ô gần truy vấn nhất—không phải toàn bộ vector—và chỉ tính khoảng cách tới các vector bên trong chúng. Với nlist=10.000 và nprobe=16, trung bình chỉ khoảng 0,16% toàn bộ được tìm, nên phép tính khoảng cách giảm hàng trăm lần. Ở đây nprobe là núm chính của recall-độ trễ. Mở ít thì nhanh nhưng có thể bỏ lỡ láng giềng gần thật khi truy vấn ở gần ranh giới ô và nó nằm ở ô kề; mở nhiều thì recall tăng nhưng độ trễ tăng. IVF có cấu trúc đơn giản và chi phí bộ nhớ nhỏ, nên được dùng rộng rãi kết hợp với PQ trong môi trường quy mô lớn, ràng buộc bộ nhớ.

C. PQ (Product Quantization, lượng tử hóa tích). PQ không phải chiến lược tìm kiếm mà là kỹ thuật nén vector giảm đồng thời bộ nhớ và chi phí tính khoảng cách. Nó chia một vector d chiều thành m vector con rồi thay mỗi không gian con bằng ID của một codebook (thường 256 vector đại diện) huấn luyện bằng k-means. Khi đó một vector được nén thành m mã 1 byte, chẳng hạn giảm một vector float 768 chiều (3.072 byte) xuống 96 byte ở m=96—khoảng 32 lần. Lúc truy vấn, khoảng cách giữa mỗi vector con của truy vấn và các vector đại diện codebook được tính trước thành bảng (tính khoảng cách bất đối xứng, ADC), và khoảng cách của một vector ứng viên được xấp xỉ bằng cộng các mục bảng qua ID mã của nó, nên tính khoảng cách cũng rất nhanh. Cái giá là recall giảm do sai số lượng tử hóa, và để bù, một thiết kế lọc ứng viên giai đoạn đầu bằng PQ rồi xếp hạng lại bằng các vector gốc thường được dùng.

Kết hợp ba kỹ thuật là chuẩn thực tế. Vì nén là thiết yếu để nhét hàng tỷ vector vào bộ nhớ, IVF+PQ trở thành tổ hợp chủ lực cho quy mô lớn, còn HNSW (và HNSW+PQ khi cần) được dùng khi recall-độ trễ là ưu tiên hàng đầu và bộ nhớ dư dả. Nói cách khác, cốt lõi của thiết kế ANN là lắp ráp các trục sao cho "IVF hay HNSW đảm nhận thu hẹp bao nhiêu, còn PQ đảm nhận lưu nhỏ đến đâu."

Một biện pháp điển hình để khôi phục recall trong chỉ mục nén là xếp hạng lại hai giai đoạn. Ở giai đoạn một, xấp xỉ khoảng cách bằng mã PQ thu hẹp rẻ tiền về hàng nghìn ứng viên; ở giai đoạn hai, khoảng cách chính xác được tính lại bằng vector gốc (hoặc độ chính xác cao) chỉ cho các ứng viên đó để chốt top K. Vì ứng viên nhỏ, chi phí tính chính xác của giai đoạn hai nhỏ, và nó sửa thứ hạng bị nhiễu bởi sai số lượng tử hóa, nâng recall. Cấu trúc "thu hẹp bằng gần đúng rẻ và chốt bằng chính xác đắt" này là mẫu thiết kế cốt lõi của ANN lấy được cả nén lẫn độ chính xác.

4. So sánh và thiết kế tham số

Chọn thuật toán không phải "cái gì nhanh nhất" mà "cái gì tối ưu dưới yêu cầu bộ nhớ và recall cho trước." Bảng dưới sắp xếp sự khác biệt tính chất của ba trục, nhưng giá trị của nó thay đổi theo phân phối dữ liệu, số chiều và phần cứng, nên luôn phải đo đường cong recall-độ trễ trên dữ liệu của mình.

Kỹ thuật Chiến lược cốt lõi Tham số chính Điểm mạnh Giới hạn
HNSW tìm kiếm đồ thị lân cận phân tầng M, efConstruction, efSearch recall-độ trễ tốt nhất, cập nhật tương đối dễ chi phí bộ nhớ đồ thị (30~50% của vector)
IVF phân ô k-means rồi chỉ tìm nprobe ô nlist, nprobe hiệu quả bộ nhớ, hợp quy mô lớn recall giảm ở truy vấn ranh giới ô
PQ nén codebook vector con m, kích thước codebook nén 32 lần trở lên, tăng tốc tính khoảng cách recall giảm do sai số lượng tử hóa
IVF+PQ kết hợp phân hoạch + nén nlist, nprobe, m xử lý quy mô tỷ trong bộ nhớ tinh chỉnh phức tạp, cần xếp hạng lại

Điểm xuất phát của thiết kế tham số luôn là recall mục tiêu. Ví dụ nếu yêu cầu là "Recall@10 ≥ 0.95 với độ trễ tối thiểu," quy trình điển hình ở HNSW là xây đồ thị với M=16 và efConstruction=200, rồi đo recall trong khi tăng efSearch từ 64 đến 512, và chọn efSearch nhỏ nhất vượt mục tiêu. Tăng M từ 16 lên 32 làm bộ nhớ đồ thị tăng khoảng gấp đôi nhưng chỉ đem lại lợi ích giảm dần vài % recall, và đặc biệt M một khi đã đặt thì không thể thay đổi mà không xây lại, nên phải cố định cẩn thận.

Ở IVF, quy tắc kinh nghiệm là đặt nlist gần khoảng √N. Với 100 triệu vector, đặt nlist ở mức vài nghìn đến mười nghìn và khớp recall-độ trễ bằng cách tăng nprobe. Nếu nlist quá nhỏ, một ô đơn lớn lên và khối lượng tìm kiếm tăng; nếu quá lớn, chi phí huấn luyện và quản lý tăng và recall bất ổn vì có ít vector mỗi ô. Ở PQ, m (số vector con) lớn hơn làm hạ tỉ lệ nén (số byte = m) nhưng giảm sai số lượng tử hóa và nâng recall, nên đặt m bằng cách tính ngược từ ngân sách bộ nhớ và bù recall thiếu bằng xếp hạng lại.

Làm ước tính bộ nhớ bằng con số sẽ xây được trực giác thiết kế. Giữ 100 triệu vector float32 768 chiều nguyên trạng là khoảng 307GB, vượt bộ nhớ một nút đơn. Thêm HNSW (M=16) lên trên chất thêm hàng chục GB nữa cho cạnh đồ thị, nên chi phí vọt lên. Ngược lại, áp PQ với m=96 (codebook 256) giảm mỗi vector xuống 96 byte, khiến toàn bộ còn khoảng 9,6GB, và thu hẹp ô tìm kiếm bằng IVF cho phép xử lý cả quy mô tỷ trên một nút đơn. Vì vậy ước tính "bộ nhớ gốc → bộ nhớ sau nén → chi phí đồ thị/chỉ mục" bằng con số trước và tính ngược số nút và chi phí là bước phải trải qua trước khi chọn chỉ mục.

Thời gian xây dựng (build time) cũng là biến thiết kế không được bỏ qua. Tăng efConstruction của HNSW cải thiện chất lượng đồ thị và nâng recall ở cùng efSearch, nhưng thời gian build tăng phi tuyến—trong một số trường hợp gấp đôi efConstruction làm gấp bốn thời gian build. Huấn luyện codebook của IVF/PQ cũng là k-means lặp trên toàn bộ mẫu dữ liệu, nên có thể mất hàng giờ ở quy mô lớn. Do đó hãy tính sớm trong thiết kế rằng không chỉ "hiệu năng truy vấn" mà cả "chu kỳ xây lại × thời gian xây" phản ánh trực tiếp vào chi phí vận hành, và dịch vụ càng thay đổi dữ liệu thường xuyên càng nên ưu tiên các chỉ mục cho phép cập nhật tăng dần (HNSW, FreshDiskANN, v.v.).

Điểm phải lưu ý là sự bất đối xứng rằng các tham số này chỉ điều chỉnh được một phần sau khi chỉ mục đã xây. efSearch·nprobe có thể đổi tự do lúc truy vấn để điều chỉnh recall-độ trễ theo thời gian thực, nhưng M·nlist·m·codebook được cố định lúc xây và cần xây lại toàn bộ để thay đổi. Do đó hãy phân biệt "núm lúc truy vấn" với "hằng số lúc xây," và quyết định cái sau với tầm nhìn về vòng đời dịch vụ và tăng trưởng dữ liệu.

5. Trường hợp áp dụng

ANN thấm vào gần như mọi dịch vụ phải "tính độ tương tự ngữ nghĩa nhanh ở quy mô lớn." Các trường hợp dưới đây, dù khác lĩnh vực, đều chia sẻ cùng bộ khung "embedding nhiều chiều → ANN sinh ứng viên → xử lý chính xác," và đáng chú ý là chỉ thứ tự ưu tiên giữa recall, độ trễ và bộ nhớ được đặt khác nhau trong từng trường hợp.

Đường ống RAG của AI tạo sinh là nơi dùng tiêu biểu của ANN. [[rag]] nhúng câu hỏi người dùng, truy xuất top-K tài liệu tương tự từ cơ sở tri thức bằng ANN, rồi chèn vào prompt của LLM. Vì độ trễ truy xuất cộng trực tiếp vào tổng độ trễ phản hồi, việc lập chỉ mục hàng chục triệu đoạn bằng HNSW để đạt Recall@10 ≥ 0.95 trong vài ms chi phối cả chất lượng lẫn tốc độ cảm nhận. Nếu recall thấp, bằng chứng liên quan bị bỏ sót và LLM ảo giác, nên recall của ANN trực tiếp chuyển thành tính sự thật của câu trả lời RAG.

Trong hệ thống gợi ý, cốt lõi của giai đoạn sinh ứng viên là nhúng người dùng và sản phẩm rồi rút "K sản phẩm gần vector người dùng này" bằng ANN. Chuẩn là cấu trúc hai giai đoạn sinh hàng trăm ứng viên trong vài mili giây từ một danh mục hàng trăm triệu sản phẩm rồi xếp hạng lại bằng một mô hình xếp hạng chính xác. Ở đây ANN biến "chi phí đưa toàn bộ sản phẩm vào mô hình xếp hạng" thành "chi phí chỉ đưa vài ứng viên," tạo thành mẫu kết hợp gần đúng-chính xác điển hình nắm được cả độ chính xác lẫn độ trễ/chi phí cùng lúc.

Tìm kiếm hình ảnh·đa phương tiện và phát hiện trùng lặp cũng là lĩnh vực ứng dụng ANN lâu đời. Tìm ảnh tương tự bằng embedding ảnh, nhận diện cùng nguồn âm thanh bằng dấu vân âm thanh, và loại đạo văn/trùng lặp bằng embedding tài liệu đều cần tìm kiếm láng giềng gần của vector nhiều chiều. Ở quy mô hàng trăm triệu mục, một thiết kế nén vector 32 lần trở lên bằng IVF+PQ để nhét vào bộ nhớ một nút đơn và xếp hạng lại ứng viên PQ bằng bản gốc để khôi phục recall được dùng rộng rãi. Thư viện FAISS của Meta trở thành chuẩn ngành bằng cách cung cấp các chỉ mục nén quy mô lớn này như công dân hạng nhất.

Phát hiện bất thường·an ninh cũng là ứng dụng hiệu quả của ANN. Nếu nhúng hành vi, nhật ký và lưu lượng mạng bình thường rồi tích vào chỉ mục, thì khi một sự kiện mới đến bạn có thể nhanh chóng lấy "khoảng cách tới láng giềng bình thường gần nhất" bằng ANN và phán là ngoại lệ nếu khoảng cách đó lớn. Vì so sánh hàng trăm triệu mẫu bình thường với mỗi sự kiện bằng vét cạn là bất khả thi, lấy chỉ khoảng cách láng giềng gần gần đúng trong thời gian gần hằng số bằng ANN là tiền đề của phát hiện thời gian thực. Ở đây, dù recall hơi thấp, "bất thường hiển nhiên" xa mọi láng giềng và bị lọc ra, nên tham số ưu tiên độ trễ là hợp lý.

Về mặt sản phẩm hóa nền tảng·DBMS, HNSW và họ DiskANN đang lan nhanh. pgvector thêm chỉ mục HNSW/IVF vào PostgreSQL để cho phép tìm kiếm vector bên trong một DB quan hệ, và Milvus, Elasticsearch, OpenSearch và những hệ khác chọn HNSW làm chỉ mục mặc định. DiskANN của Microsoft lưu đồ thị trên SSD để vượt giới hạn bộ nhớ và xử lý quy mô tỷ trên một nút đơn, trở thành nền tảng của nhiều sản phẩm như Azure Cosmos DB và pgvectorscale. Như vậy ANN không còn là thuật toán nghiên cứu mà đã định vị như một khối xây dựng cơ bản của hạ tầng dữ liệu.

6. Chuyên sâu — Xu hướng mới nhất và tìm kiếm dựa trên đĩa·có lọc

Nghiên cứu ANN đang phát triển nhanh theo hai trục: "lớn hơn vượt bức tường bộ nhớ, và chính xác hơn với điều kiện kèm theo." Trục thứ nhất là chỉ mục dựa trên đĩa. Một đồ thị thuần trong bộ nhớ cần hàng trăm GB bộ nhớ ở một tỷ vector và hàng nghìn chiều, nên chi phí bùng nổ. DiskANN (đồ thị Vamana) của Microsoft chỉ giữ vector đã nén trong bộ nhớ và toàn đồ thị trên SSD, thiết kế đồ thị để tối thiểu hóa truy cập trang, và xử lý quy mô tỷ trên một nút đơn ở mức recall 95%. Thêm nghiên cứu cập nhật động như FreshDiskANN, hỗ trợ chèn và xóa không cần xây lại, nó cùng lúc tấn công hai bài toán khó là quy mô lớn và cập nhật thời gian thực.

Trục thứ hai là tìm kiếm có lọc (filtered ANN). Trong thực tế, điều kiện metadata và độ tương tự vector được yêu cầu cùng nhau, như "cái tương tự nhất trong các tài liệu của năm ngoái, thuộc một danh mục cụ thể, mà tôi có quyền truy cập." Áp điều kiện sau tìm kiếm (post-filtering) gây vấn đề kết quả rỗng khi mọi ứng viên bị lọc hết, còn áp trước (pre-filtering) thì chậm vì không dùng được cấu trúc đồ thị·ô của chỉ mục. Filtered-DiskANN (WWW 2023) phản ánh thông tin nhãn vào cạnh đồ thị ngay từ giai đoạn xây chỉ mục, xử lý tìm kiếm có điều kiện ở recall cao hơn các cách tiếp cận truyền thống chỉ đổi phần tìm kiếm. Tuy nhiên cách nào có lợi tùy độ chọn lọc của bộ lọc, và có báo cáo rằng họ IVF có thể có lợi khi bộ lọc loại bỏ phần lớn dữ liệu, nên tìm kiếm có điều kiện vẫn là chủ đề nghiên cứu sôi động.

Thứ ba, lượng tử hóa và tăng tốc phần cứng tiếp tục đẩy ranh giới độ chính xác-chi phí. Vượt qua PQ, OPQ (lượng tử hóa tích tối ưu), lượng tử hóa vô hướng và lượng tử hóa nhị phân đang cải thiện cân bằng giữa tỉ lệ nén và recall, và khi embedding LLM gần đây lớn lên hàng nghìn chiều, các thiết kế kết hợp giảm chiều ([[dimensionality-reduction]]) với lượng tử hóa để hạ chi phí lưu trữ và tính khoảng cách trở nên quan trọng. Tăng tốc tính khoảng cách hàng loạt bằng GPU/SIMD cũng thành chuẩn ở FAISS và những hệ khác, nâng mạnh thông lượng (QPS) ở cùng recall.

Thứ tư, tìm kiếm lai (dense + sparse) nâng chất lượng. Độ tương tự vector (dense) nắm ngữ nghĩa tốt nhưng yếu ở khớp chính xác danh từ riêng, mã và từ hiếm, còn chỉ mục đảo dựa trên từ khóa (sparse, ví dụ BM25) thì ngược lại. Vì vậy một lai chạy cả hai tìm kiếm rồi kết hợp kết quả đang thành chuẩn ở [[rag]] và tìm kiếm doanh nghiệp, hợp nhất ưu điểm cả hai bằng các kỹ thuật kết hợp như chuẩn hóa điểm và Hợp nhất thứ hạng tương hỗ (RRF, Reciprocal Rank Fusion). Vì sinh ứng viên phía dense ở đây là ANN, chất lượng của lai rốt cuộc cũng phụ thuộc recall của ANN.

Thứ năm, chuẩn hóa đánh giá đã trưởng thành. ann-benchmarks.com đã thành benchmark trên thực tế so sánh công khai đường cong recall-QPS của nhiều thư viện trên các tập dữ liệu đa dạng. Bài học cốt lõi là "không có người thắng duy nhất": vì chỉ mục tối ưu thay đổi theo phân phối dữ liệu, số chiều, ngân sách bộ nhớ và tần suất cập nhật, nguyên tắc là chọn bằng cách đo đường cong trên dữ liệu và mẫu truy vấn của mình thay vì tin nguyên các con số của nhà cung cấp.

7. Điều cần cân nhắc và hàm ý

Thứ nhất, thiết kế tường minh recall-độ trễ-bộ nhớ (chiến lược áp dụng). Điểm xuất phát của việc áp dụng ANN là trước hết đóng đinh "recall thấp nhất chấp nhận được" và "ngân sách bộ nhớ/độ trễ" từ yêu cầu nghiệp vụ. Nơi chi phí bỏ sót lớn, như tính sự thật của RAG, ưu tiên recall cao; nơi lỏng lẻo chấp nhận được, như gợi ý khám phá, ưu tiên độ trễ/chi phí. Từ góc nhìn của Kỹ sư chuyên nghiệp, cốt lõi là năng lực thiết kế phân rã "câu hỏi là láng giềng gần chính xác hay chấp nhận gần đúng, ràng buộc là bộ nhớ hay độ trễ" và ánh xạ nó sang chỉ mục và tham số.

Thứ hai, tách hằng số xây dựng và núm truy vấn (đánh đổi). M·nlist·m·codebook là hằng số xây dựng không thể thay đổi mà không xây lại, còn efSearch·nprobe là núm điều chỉnh lúc truy vấn. Nhầm lẫn hai cái dẫn đến sai lầm tốn kém "kích hoạt xây lại toàn bộ khi cố nâng recall trong vận hành." Hãy đặt hằng số xây dựng có dư với tầm nhìn về tăng trưởng dữ liệu và thay đổi phân phối, đồng thời tách thiết kế vận hành sao cho điều chỉnh recall-độ trễ hằng ngày được hấp thụ bằng núm truy vấn.

Thứ ba, thay đổi dữ liệu và giám sát recall (vận hành·quan sát được). Nếu thay mô hình embedding hoặc phân phối dữ liệu dịch chuyển, recall có thể giảm ngay cả ở cùng tham số. Do đó cần kiểm chứng liên tục chất lượng gần đúng—định kỳ chạy vét cạn trên một số ít truy vấn để đo Recall@K thực tế và phơi bày trên bảng điều khiển. Từ quan điểm [[observability]], lập chỉ số "chất lượng tìm kiếm đã suy giảm bao nhiêu ngay lúc này" cho phép phán thời điểm xây lại·tinh chỉnh lại chỉ mục bằng dữ liệu.

Thứ tư, khớp với kiến trúc và cấu trúc chi phí (công nghệ liên quan·triển vọng). Chọn chỉ mục chính là cấu trúc chi phí hạ tầng. HNSW trong bộ nhớ nhanh nhưng tốn bộ nhớ, họ DiskANN hạ chi phí bằng SSD nhưng tăng độ trễ, và IVF+PQ giảm số nút qua nén. Phải thiết kế toàn bộ đường tìm kiếm kết hợp với [[vector-database]], lọc và [[caching-strategy]], và triển vọng là khi dựa trên đĩa, lọc, lượng tử hóa và tăng tốc phần cứng hội tụ, ANN sẽ củng cố vị thế như động cơ tiêu chuẩn của tìm kiếm ngữ nghĩa thời gian thực quy mô hàng tỷ. Tuy nhiên vì nguyên tắc "không có chỉ mục tối ưu duy nhất" vẫn giữ, nội tại hóa năng lực benchmark·tinh chỉnh ở cấp tổ chức trở thành lợi thế cạnh tranh bền vững.

Thứ năm, an ninh·quyền riêng tư và nhất quán cập nhật (quản lý rủi ro). Vì bản thân embedding của tìm kiếm vector mang thông tin của nội dung gốc, có rủi ro rò rỉ chỉ mục khôi phục văn bản gốc·dữ liệu cá nhân qua đảo ngược embedding (embedding inversion), nên phải áp kiểm soát lưu trữ·truy cập giống như dữ liệu thông thường. Ngoài ra, để đáp ứng yêu cầu xóa (quyền được lãng quên), phải thực sự loại bỏ vector liên quan khỏi chỉ mục, nhưng nhiều chỉ mục ANN chịu độ trễ·suy giảm chất lượng phát hiện do xóa, nên cần thủ tục vận hành như xóa mềm rồi xây lại định kỳ. Trong tìm kiếm có lọc, áp điều kiện quyền sau khi thực hiện có thể phơi bày tài liệu không được phép trong ứng viên, nên quan trọng là tích hợp kiểm soát truy cập vào thiết kế chỉ mục để bảo đảm "phạm vi có thể tìm kiếm = phạm vi được phép truy cập."

Tài liệu tham khảo


Tóm tắt một câu: ANN là kỹ thuật tăng tốc tìm kiếm láng giềng gần của vector nhiều chiều hàng chục đến hàng nghìn lần bằng cách nhượng một chút recall, kết hợp ba trục trực giao là tìm kiếm đồ thị (HNSW)·phân cụm (IVF)·nén vector (PQ) và thiết kế sự đánh đổi recall-độ trễ-bộ nhớ bằng cách tính ngược từ một recall mục tiêu—động cơ cốt lõi của tìm kiếm vector quy mô lớn.