Khi bạn tìm kiếm trên Google hay hỏi ChatGPT một câu, hệ thống phải tìm trong hàng tỷ vector để trả kết quả liên quan nhất. Tìm chính xác thì chậm kinh khủng, và đó là lúc Approximate Nearest Neighbor (ANN) xuất hiện.
Approximate Nearest Neighbor (ANN) Là Gì?
Approximate Nearest Neighbor, viết tắt ANN, là một thuật toán tìm kiếm lân cận cho phép bạn tìm ra các vector gần giống nhất với vector truy vấn, nhưng không cần duyệt qua toàn bộ cơ sở dữ liệu.
Thay vì kiểm tra từng vector một (brute-force), ANN chia dữ liệu thành các cụm, xây dựng cấu trúc chỉ mục (index) và chỉ tìm trong những cụm có khả năng cao nhất. Kết quả là tốc độ tăng hàng nghìn lần, đổi lại một chút độ chính xác bị giảm.
Nói đơn giản: ANN giống như bạn tìm sách trong thư viện. Thay vì lật từng cuốn, bạn đi thẳng đến kệ “Công nghệ” rồi tìm trong đó. Có thể bỏ sót vài cuốn nằm sai chỗ, nhưng bạn tìm được sách nhanh hơn rất nhiều.
Tại Sao ANN Quan Trọng Trong AI?
Trong các ứng dụng AI hiện đại như RAG, semantic search, hay hệ thống gợi ý, dữ liệu được chuyển thành vector có hàng nghìn chiều. Để tìm vector gần nhất, phương pháp truyền thống là tính khoảng cách từ vector truy vấn đến từng vector trong database.
Với 1 triệu vector, điều này ổn. Nhưng với 1 tỷ vector như các hệ thống production thực tế, brute-force trở nên bất khả thi. ANN giải bài toán này bằng cách hy sinh một chút độ chính xác để đổi lấy tốc độ khủng khiếp.
Mình thấy ANN là xương sống của hầu hết hệ thống tìm kiếm hiện đại. Không có ANN, ChatGPT không thể tìm context nhanh, Google không thể trả kết quả trong mili giây, và Spotify không thể gợi ý nhạc theo thời gian thực.
Cách ANN Hoạt Động Như Thế Nào?
ANN không phải một thuật toán đơn lẻ mà là một họ các kỹ thuật. Dưới đây là những phương pháp phổ biến nhất:
1. LSH (Locality-Sensitive Hashing)
LSH băm các vector gần nhau vào cùng một bucket. Khi tìm kiếm, bạn chỉ cần tính hash của vector truy vấn và tìm trong bucket tương ứng. Nhanh, đơn giản, nhưng độ chính xác không cao.
HNSW xây dựng một đồ thị nhiều tầng, trong đó mỗi node là một vector. Tìm kiếm bắt đầu từ tầng trên cùng (ít node nhất) rồi đi xuống từng tầng để tinh chỉnh. Đây là thuật toán được dùng phổ biến nhất hiện nay vì cân bằng tốt giữa tốc độ và độ chính xác.
3. IVF (Inverted File Index)
IVF chia vector thành các cụm bằng K-Means. Khi tìm, trước tiên xác định cụm gần nhất, rồi chỉ tìm trong cụm đó. Đơn giản, hiệu quả, dễ triển khai.
4. PQ (Product Quantization)
PQ nén vector từ hàng nghìn chiều xuống thành vài byte. Điều này giảm đáng kể bộ nhớ cần thiết, cho phép lưu trữ hàng tỷ vector trong RAM.
Đánh Giá ANN: Recall vs Speed
Khi dùng ANN, bạn luôn phải cân bằng giữa hai yếu tố:
Recall là tỷ lệ kết quả đúng được tìm thấy so với tìm kiếm chính xác (brute-force). Recall 95% nghĩa là ANN tìm được 95/100 kết quả mà brute-force trả về.
Speed đo bằng số query xử lý được mỗi giây (QPS). ANN có thể nhanh hơn brute-force 100 đến 1000 lần.
Thực tế, mình thấy recall 90-95% là đủ cho hầu hết ứng dụng. Người dùng hiếm khi nhận ra kết quả thứ 96 và 97 bị thiếu, nhưng họ chắc chắn sẽ nổi giận nếu phải đợi 5 giây cho mỗi câu trả lời.
ANN vs Brute-Force: Khi Nào Dùng Cái Nào?
Brute-force (tìm chính xác) phù hợp khi dataset nhỏ, dưới 100.000 vector. Ở quy mô này, tốc độ vẫn đủ nhanh và bạn có recall 100%.
ANN là lựa chọn duy nhất khi dataset lớn hơn. Với 10 triệu vector, brute-force mất vài giây mỗi query, trong khi ANN trả kết quả trong mili giây.
Một cách tiếp cận phổ biến là dùng ANN để lọc top-K ứng viên, rồi dùng brute-force trên tập nhỏ này để xác nhận. Cách này gọi là hybrid, kết hợp tốt nhất của hai thế giới.
Các Vector Database Sử Dụng ANN
Hầu hết vector database hiện đại đều tích hợp ANN ở cấp độ lõi:
Milvus hỗ trợ nhiều loại index bao gồm HNSW, IVF, và DiskANN. Phù hợp cho dataset lớn, enterprise-grade.
Pinecone tự động chọn thuật toán ANN tối ưu dựa trên dataset, không cần cấu hình thủ công.
Weaviate dùng HNSW mặc định, có thêm module hybrid search kết hợp keyword và vector.
Qdrant implement HNSW với filter support, cho phép lọc metadata trong lúc tìm kiếm vector.
FAISS của Meta là thư viện open-source, không phải database nhưng cực kỳ phổ biến cho việc build hệ thống ANN từ đầu.
Tham Số Quan Trọng Khi Cấu Hình ANN
Khi thiết lập ANN, bạn sẽ gặp một số tham số ảnh hưởng trực tiếp đến recall và speed:
efSearch (HNSW) là số láng giềng được khám phá khi tìm kiếm. Tăng lên = recall cao hơn nhưng chậm hơn. Mình thường đặt 50-200 tùy use case.
nprobe (IVF) là số cụm được tìm kiếm. Tăng nprobe = recall cao hơn. Thường đặt 8-32.
M và efConstruction (HNSW build) ảnh hưởng đến chất lượng index. M cao hơn = index tốt hơn nhưng tốn RAM hơn. Thường M=16 hoặc 32.
Ứng Dụng Thực Tế Của ANN
Semantic search là ứng dụng lớn nhất. Khi bạn gõ “cách pha cà phê ngon”, hệ thống chuyển câu thành vector, rồi dùng ANN tìm các bài viết có vector gần nhất, bất kể dùng từ ngữ gì.
RAG (Retrieval-Augmented Generation) phụ thuộc hoàn toàn vào ANN để tìm relevant context trong knowledge base trước khi đưa cho LLM tạo câu trả lời.
Hệ thống gợi ý của Netflix, Spotify, Amazon đều dùng ANN để tìm user hoặc item tương tự trong thời gian thực.
Phát hiện trùng lặp hình ảnh, video, văn bản cũng dùng ANN. Google Image Search, Shazam, hệ thống anti-piracy đều dựa vào kỹ thuật này.
Kết Luận
ANN là kỹ thuật then chốt giúp các hệ thống AI vận hành ở quy mô lớn. Không có ANN, vector database chỉ là lý thuyết trên giấy, và RAG sẽ chậm đến mức không thể dùng được.
Nếu bạn đang xây dựng bất kỳ hệ thống nào liên quan đến embedding, semantic search, hay RAG, hiểu về ANN là bắt buộc. Bạn không cần implement từ đầu, nhưng cần biết chọn đúng thuật toán và tham số cho use case của mình.
Nhớ nguyên tắc: recall 90%+ với tốc độ cao luôn tốt hơn recall 100% với tốc độ chậm. Trong production, người dùng không đợi được.
