HNSW چیست و چرا در Vector Search استفاده می‌شود؟

مقدمه

اگر تعداد بردارهای شما کم باشد، می‌توانید nearest neighbors را با جستجوی کامل پیدا کنید. اما وقتی corpus به صدها هزار یا میلیون‌ها بردار برسد، این روش دیگر عملی نیست. HNSW یکی از محبوب‌ترین روش‌های Approximate Nearest Neighbor یا ANN برای حل همین مشکل است.

مسئله اصلی

در Dense Retrieval، برای هر query باید نزدیک‌ترین بردارها را پیدا کنیم. جستجوی کامل دقت بالایی دارد، اما هزینه‌اش با بزرگ شدن corpus زیاد می‌شود. ANN می‌گوید به‌جای اینکه بهترین جواب را با قطعیت کامل پیدا کنیم، جواب تقریباً بهترین را خیلی سریع‌تر پیدا کنیم.

HNSW یکی از موفق‌ترین ساختارها برای این کار است.

HNSW به زبان ساده

HNSW مخفف Hierarchical Navigable Small World است. ایده اصلی آن ساختن یک گراف چندلایه بین بردارها است تا بتوان با traversal سریع به نزدیک‌ترین بردارها رسید.

به‌جای scan همه نقاط، الگوریتم از یک نقطه ورودی شروع می‌کند و به‌صورت گرافی به سمت همسایه‌های بهتر حرکت می‌کند.

چرا HNSW محبوب است؟

• کیفیت خوب در برابر latency پایین
• پیاده‌سازی‌های بالغ و widely used
• مناسب برای query-time سریع
• trade-off قابل تنظیم بین speed و recall

HNSW در مقابل exact search

Exact Search:

• recall کامل
• latency بالاتر در مقیاس زیاد
• هزینه بیشتر

HNSW:

• recall خیلی خوب اما نه همیشه 100٪
• سرعت بسیار بالاتر
• مناسب production scale

تجربه ما در ماژول

در hardening ماژول، متوجه شدیم صرف داشتن کلاس HNSW کافی نیست. اگر search engine به‌اشتباه predicate یا filter را طوری پاس بدهد که backend مجبور به fallback شود، HNSW عملاً bypass می‌شود.

این تجربه مهم بود، چون نشان داد integration correctness به‌اندازه خود الگوریتم مهم است.

پارامترها و trade-off

HNSW معمولاً پارامترهایی برای ساخت graph و search دارد که روی این موارد اثر می‌گذارند:

• recall
• RAM
• build time
• query latency

تیم‌ها باید این پارامترها را با benchmark واقعی روی دیتای خود تنظیم کنند.

HNSW و security/filtering

یکی از پیچیده‌ترین موضوعات، فیلترهای metadata و ACL است. اگر filtering به‌صورت نامناسب اعمال شود، ممکن است search به exact fallback برگردد یا candidate quality کاهش یابد. به همین دلیل filtered ANN موضوع مهمی در production است.

جمع‌بندی

HNSW یکی از ستون‌های اصلی Vector Search در مقیاس بالا است. اگر corpus شما کوچک است، شاید لازم نباشد؛ اما برای retrieval جدی و production-scale معمولاً یکی از انتخاب‌های اول است. فقط یادتان باشد ارزش واقعی HNSW زمانی مشخص می‌شود که integration، filtering و benchmark آن هم درست طراحی شده باشد.

به‌روزرسانی: ۲۷ شهریور ۱۴۰۵

←همهٔ نوشته‌ها